Super-Acceleration with Cyclical Step-sizes
Baptiste Goujauda b c, Damien Scieurd e, Aymeric Dieuleveutc f, Adrien Taylorg h, Fabián Pedregosad i j
- aSamsung SAIL Montreal
- bÉcole Polytechnique Institut Polytechnique de Paris Damien Scieur
- cCMAP - Centre de Mathématiques Appliquées - Ecole Polytechnique (École Polytechnique Route de Saclay 91128 Palaiseau Cedex - France)
- dMILA - Montreal Institute for Learning Algorithms [Montréal] (6666 St-Urbain, #200, Montreal, QC, H2S 3H1, Canada - Canada)
- eSamsung SAIL [Montréal] (Canada)
- fCMAP , École Polytechnique Institut Polytechnique de Paris
- gINRIA , École Normale Supérieure CNRS , PSL Research University , Paris
- hSIERRA - Statistical Machine Learning and Parsimony (France)
- iGoogle Research
- jGoogle Inc (Toronto - Canada)
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
Abstract
We develop a convergence-rate analysis of momentum with cyclical step-sizes. We show that under some assumption on the spectral gap of Hessians in machine learning, cyclical step-sizes are provably faster than constant step-sizes. More precisely, we develop a convergence rate analysis for quadratic objectives that provides optimal parameters and shows that cyclical learning rates can improve upon traditional lower complexity bounds. We further propose a systematic approach to design optimal first order methods for quadratic minimization with a given spectral structure. Finally, we provide a local convergence rate analysis beyond quadratic minimization for the proposed methods and illustrate our findings through benchmarks on least squares and logistic regression problems.