2018

Inexact SARAH Algorithm for Stochastic Optimization

Nguyen, Lam M., Scheinberg, Katya, Takáč, Martin

Understand

We develop and analyze a variant of the SARAH algorithm, which does not require computation of the exact gradient.

Thus this new method can be applied to general expectation minimization problems rather than only finite sum problems.
While the original SARAH algorithm, as well as its predecessor, SVRG, require an exact gradient computation on each outer iteration, the inexact variant of SARAH (iSARAH), which we develop here, requires only stochastic gradient computed on a mini-batch of sufficient size.
The proposed method combines variance reduction via sample size selection and iterative stochastic gradient updates.

Built on

B.T. Polyak, Some methods of speeding up the convergence of iteration methods , USSR Computational Mathematics and Mathematical Physics 4 (1964), pp. 1–17
1964
Earlier work this paper cites.
Y. Nesterov, Introductory lectures on convex optimization: a basic course , Applied optimization, Kluwer Academic Publ., Boston, Dordrecht, London, 2004
2004
Earlier work this paper cites.
Y. Nesterov and B.T. Polyak, Cubic regularization of Newton method and its global performance , Mathematical Programming 108 (2006), pp. 177–205
2006
Earlier work this paper cites.
N. Le Roux, M. Schmidt, and F. Bach, A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets , in NIPS . 2012, pp. 2663–2671
2012
Earlier work this paper cites.
R. Johnson and T. Zhang, Accelerating Stochastic Gradient Descent Using Predictive Variance Reduction , in NIPS . 2013, pp. 315–323
2013
Earlier work this paper cites.
J. Konečný and P. Richtárik, Semi-stochastic gradient descent methods , arXiv:1312.1666 (2013)
Original
2013
Earlier work this paper cites.
A. Defazio, F. Bach, and S. Lacoste-Julien, SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives , in NIPS . 2014, pp. 1646–1654
2014
Earlier work this paper cites.

Similar

H. Karimi, J. Nutini, and M. Schmidt, Linear Convergence of Gradient and Proximal-Gradient Methods Under the Polyak-Łojasiewicz Condition , in Machine Learning and Knowledge Discovery in Databases , P. Frasconi, N. Landwehr, G. Manco, and J. Vreeken, eds., Cham. Springer International Publishing, 2016, pp. 795–811
2016
Cited alongside, same era.
L. Lei and M.I. Jordan, Less than a Single Pass: Stochastically Controlled Stochastic Gradient , in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics , A. Singh and J. Zhu, eds., Proceedings of Machine Learning Research Vol. 54, 20–22 Apr, Fort Lauderdale, FL, USA. PMLR, 2017, pp. 148–156
2017
Cited alongside, same era.
L. Lei, C. Ju, J. Chen, and M.I. Jordan, Non-convex finite-sum optimization via SCSG methods , in Advances in Neural Information Processing Systems 30 , I. Guyon, U.V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, eds., Curran Associates, Inc., 2017, pp. 2348–2358. Available at http://papers.nips.cc/paper/6829-non-convex-finite-sum-optimization-via-scsg-methods.pdf
2017
Cited alongside, same era.
L. Nguyen, J. Liu, K. Scheinberg, and M. Takáč, SARAH: A novel method for machine learning problems using stochastic recursive gradient , ICML (2017), pp. 2613–2621
2017
Cited alongside, same era.
L.M. Nguyen, J. Liu, K. Scheinberg, and M. Takác, Stochastic recursive gradient algorithm for nonconvex optimization , CoRR abs/1705.07261 (2017)
Original
2017
Cited alongside, same era.
M. Schmidt, N. Le Roux, and F. Bach, Minimizing finite sums with the stochastic average gradient , Mathematical Programming 162 (2017), pp. 83–112
2017
Cited alongside, same era.

Then

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…