Accelerating Variance-Reduced Stochastic Gradient Methods

Derek Driggs, Matthias J. Ehrhardt, Carola-Bibiane Schönlieb

Research output: Contribution to journalArticlepeer-review

6 Citations (SciVal)
55 Downloads (Pure)

Abstract

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 n, 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.

Original languageEnglish
Pages (from-to)671–715
Number of pages45
JournalMathematical Programming
Volume191
Issue number2
Early online date15 Sept 2020
DOIs
Publication statusPublished - 1 Feb 2022

Bibliographical note

Funding Information:
C.-B.S. and M.J.E. acknowledge support from the EPSRC grant No. EP/S0260 45/1. C.-.B.S. acknowledges support from the Leverhulme Trust project “Breaking the nonconvexity barrier”, the Philip Leverhulme Prize, the EPSRC grant No. EP/M00483X/1, the EPSRC Centre No. EP/N014588/1, the European Union Horizon 2020 research and innovation programmes under the Marie Skodowska-Curie grant agreement No. 777826 NoMADS and No. 691070 CHiPS, the Cantab Capital Institute for the Mathematics of Information and the Alan Turing Institute.

Funding Information:
C.-B.S. and M.J.E. acknowledge support from the EPSRC Grant No. EP/S026045/1. C.-B.S. further acknowledges support from the Leverhulme Trust project on ‘Breaking the non-convexity barrier’, the Philip Leverhulme Prize, the EPSRC grant EP/T003553/1, the EPSRC Centre Nr. EP/N014588/1, the Wellcome Innovator Award RG98755, European Union Horizon 2020 research and innovation programmes under the Marie Skodowska-Curie Grant Agreement No. 777826 NoMADS and No. 691070 CHiPS, the Cantab Capital Institute for the Mathematics of Information and the Alan Turing Institute. D.D. acknowledges support from the Gates Cambridge Trust and the Cantab Capital Institute for the Mathematics of Information.

Publisher Copyright:
© 2020, The Author(s).

Keywords

  • Accelerated gradient descent
  • Convex optimisation
  • Stochastic optimisation
  • Variance reduction

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint

Dive into the research topics of 'Accelerating Variance-Reduced Stochastic Gradient Methods'. Together they form a unique fingerprint.

Cite this