Finite-sum optimization: Adaptivity to smoothness and loopless variance reduction
Preprint
Abstract
For finite-sum optimization, variance-reduced gradient methods (VR) compute at each iteration the gradient of a single function (or of a mini-batch), and yet achieve faster convergence than SGD thanks to a carefully crafted lower-variance stochastic gradient estimator that reuses past gradients. Another important line of research of the past decade in continuous optimization is the adaptive algorithms such as AdaGrad, that dynamically adjust the (possibly coordinate-wise) learning rate to past gradients and thereby adapt to the geometry of the objective function. Variants such as RMSprop and Adam demonstrate outstanding practical performance that have contributed to the success of deep learning. In this work, we present AdaLVR, which combines the AdaGrad algorithm with loopless variance-reduced gradient estimators such as SAGA or L-SVRG that benefits from a straightforward construction and a streamlined analysis. We assess that AdaLVR inherits both good convergence properties from VR methods and the adaptive nature of AdaGrad: in the case of $L$-smooth convex functions we establish a gradient complexity of $O(n+(L+\sqrt{nL})/\varepsilon)$ without prior knowledge of $L$. Numerical experiments demonstrate the superiority of AdaLVR over state-of-the-art methods. Moreover, we empirically show that the RMSprop and Adam algorithm combined with variance-reduced gradients estimators achieve even faster convergence.
Keywords
All Related Versions
This publication has 9 references indexed in Scilit:
- SVRG meets AdaGrad: painless variance reductionMachine Learning, 2022
- Accelerating mini-batch SARAH by step size rulesInformation Sciences, 2021
- Stochastic quasi-gradient methods: variance reduction via Jacobian sketchingMathematical Programming, 2020
- Katyusha: the first direct acceleration of stochastic gradient methods2017
- Semi-Stochastic Gradient Descent MethodsFrontiers in Applied Mathematics and Statistics, 2017
- A Convergent Incremental Gradient Method with a Constant Step SizeSIAM Journal on Optimization, 2007
- A class of gradient unconstrained minimization algorithms with adaptive stepsizeJournal of Computational and Applied Mathematics, 2000
- Two-Point Step Size Gradient MethodsIMA Journal of Numerical Analysis, 1988
- Minimization of functions having Lipschitz continuous first partial derivativesPacific Journal of Mathematics, 1966