Repository logo
 

Accelerating variance-reduced stochastic gradient methods

Published version
Peer-reviewed

Change log

Authors

Ehrhardt, MJ 
Schönlieb, CB 

Abstract

jats:titleAbstract</jats:title>jats:pVariance 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 functionsjats:italicn</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>

Description

Funder: Gates Cambridge Trust (GB)

Keywords

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

Journal Title

Mathematical Programming

Conference Name

Journal ISSN

0025-5610
1436-4646

Volume Title

191

Publisher

Springer Science and Business Media LLC
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)