Accelerating variance-reduced stochastic gradient methods
Publication Date
2022Journal Title
Mathematical Programming
ISSN
0025-5610
Publisher
Springer Science and Business Media LLC
Volume
191
Issue
2
Pages
671-715
Language
en
Type
Article
This Version
VoR
Metadata
Show full item recordCitation
Driggs, D., Ehrhardt, M., & Schönlieb, C. (2022). Accelerating variance-reduced stochastic gradient methods. Mathematical Programming, 191 (2), 671-715. https://doi.org/10.1007/s10107-020-01566-2
Description
Funder: Gates Cambridge Trust (GB)
Abstract
<jats:title>Abstract</jats:title><jats:p>Variance reduction is a crucial tool for improving the slow convergence of stochastic gradient descent. Only a few variance-reduced methods, however, have yet been shown to directly benefit from Nesterov’s acceleration techniques to match the convergence rates of accelerated gradient methods. Such approaches rely on “negative momentum”, a technique for further variance reduction that is generally specific to the SVRG gradient estimator. In this work, we show for the first time that negative momentum is unnecessary for acceleration and develop a universal acceleration framework that allows all popular variance-reduced methods to achieve accelerated convergence rates. The constants appearing in these rates, including their dependence on the number of functions <jats:italic>n</jats:italic>, scale with the mean-squared-error and bias of the gradient estimator. In a series of numerical experiments, we demonstrate that versions of SAGA, SVRG, SARAH, and SARGE using our framework significantly outperform non-accelerated versions and compare favourably with algorithms using negative momentum.</jats:p>
Keywords
Full Length Paper, Stochastic optimisation, Convex optimisation, Variance reduction, Accelerated gradient descent, 90C06, 90C15, 90C25, 90C30, 90C60, 68Q25
Sponsorship
Engineering and Physical Sciences Research Council (EP/M00483X/1)
Engineering and Physical Sciences Research Council (EP/N014588/1)
European Commission Horizon 2020 (H2020) Marie Sk?odowska-Curie actions (691070)
European Commission Horizon 2020 (H2020) Marie Sk?odowska-Curie actions (777826)
EPSRC (EP/S026045/1)
Engineering and Physical Sciences Research Council (EP/H023348/1)
Leverhulme Trust (PLP-2017-275)
Alan Turing Institute (Unknown)
Identifiers
s10107-020-01566-2, 1566
External DOI: https://doi.org/10.1007/s10107-020-01566-2
This record's URL: https://www.repository.cam.ac.uk/handle/1810/334374
Rights
Licence:
http://creativecommons.org/licenses/by/4.0/
Statistics
Total file downloads (since January 2020). For more information on metrics see the
IRUS guide.
Recommended or similar items
The current recommendation prototype on the Apollo Repository will be turned off on 03 February 2023. Although the pilot has been fruitful for both parties, the service provider IKVA is focusing on horizon scanning products and so the recommender service can no longer be supported. We recognise the importance of recommender services in supporting research discovery and are evaluating offerings from other service providers. If you would like to offer feedback on this decision please contact us on: support@repository.cam.ac.uk