Super-Acceleration with Cyclical Step-sizes

Baptiste Goujaud, Damien Scieur, Aymeric Dieuleveut, Adrien B. Taylor, Fabian Pedregosa
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:3028-3065, 2022.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-goujaud22a, title = { Super-Acceleration with Cyclical Step-sizes }, author = {Goujaud, Baptiste and Scieur, Damien and Dieuleveut, Aymeric and Taylor, Adrien B. and Pedregosa, Fabian}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {3028--3065}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/goujaud22a/goujaud22a.pdf}, url = {https://proceedings.mlr.press/v151/goujaud22a.html}, 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. } }
Endnote
%0 Conference Paper %T Super-Acceleration with Cyclical Step-sizes %A Baptiste Goujaud %A Damien Scieur %A Aymeric Dieuleveut %A Adrien B. Taylor %A Fabian Pedregosa %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-goujaud22a %I PMLR %P 3028--3065 %U https://proceedings.mlr.press/v151/goujaud22a.html %V 151 %X 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.
APA
Goujaud, B., Scieur, D., Dieuleveut, A., Taylor, A.B. & Pedregosa, F.. (2022). Super-Acceleration with Cyclical Step-sizes . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:3028-3065 Available from https://proceedings.mlr.press/v151/goujaud22a.html.

Related Material