Acceleration through spectral density estimation

Fabian Pedregosa, Damien Scieur
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:7553-7562, 2020.

Abstract

We develop a framework for the average-case analysis of random quadratic problems and derive algorithms that are optimal under this analysis. This yields a new class of methods that achieve acceleration given a model of the Hessian’s eigenvalue distribution. We develop explicit algorithms for the uniform, Marchenko-Pastur, and exponential distributions. These methods have a simple momentum-like update, in which each update only makes use on the current gradient and previous two iterates. Furthermore, the momentum and step-size parameters can be estimated without knowledge of the Hessian’s smallest singular value, in contrast with classical accelerated methods like Nesterov acceleration and Polyak momentum. Through empirical benchmarks on quadratic and logistic regression problems, we identify regimes in which the the proposed methods improve over classical (worst-case) accelerated methods.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-pedregosa20a, title = {Acceleration through spectral density estimation}, author = {Pedregosa, Fabian and Scieur, Damien}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {7553--7562}, year = {2020}, editor = {III, Hal Daumé and Singh, Aarti}, volume = {119}, series = {Proceedings of Machine Learning Research}, month = {13--18 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v119/pedregosa20a/pedregosa20a.pdf}, url = {https://proceedings.mlr.press/v119/pedregosa20a.html}, abstract = {We develop a framework for the average-case analysis of random quadratic problems and derive algorithms that are optimal under this analysis. This yields a new class of methods that achieve acceleration given a model of the Hessian’s eigenvalue distribution. We develop explicit algorithms for the uniform, Marchenko-Pastur, and exponential distributions. These methods have a simple momentum-like update, in which each update only makes use on the current gradient and previous two iterates. Furthermore, the momentum and step-size parameters can be estimated without knowledge of the Hessian’s smallest singular value, in contrast with classical accelerated methods like Nesterov acceleration and Polyak momentum. Through empirical benchmarks on quadratic and logistic regression problems, we identify regimes in which the the proposed methods improve over classical (worst-case) accelerated methods.} }
Endnote
%0 Conference Paper %T Acceleration through spectral density estimation %A Fabian Pedregosa %A Damien Scieur %B Proceedings of the 37th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2020 %E Hal Daumé III %E Aarti Singh %F pmlr-v119-pedregosa20a %I PMLR %P 7553--7562 %U https://proceedings.mlr.press/v119/pedregosa20a.html %V 119 %X We develop a framework for the average-case analysis of random quadratic problems and derive algorithms that are optimal under this analysis. This yields a new class of methods that achieve acceleration given a model of the Hessian’s eigenvalue distribution. We develop explicit algorithms for the uniform, Marchenko-Pastur, and exponential distributions. These methods have a simple momentum-like update, in which each update only makes use on the current gradient and previous two iterates. Furthermore, the momentum and step-size parameters can be estimated without knowledge of the Hessian’s smallest singular value, in contrast with classical accelerated methods like Nesterov acceleration and Polyak momentum. Through empirical benchmarks on quadratic and logistic regression problems, we identify regimes in which the the proposed methods improve over classical (worst-case) accelerated methods.
APA
Pedregosa, F. & Scieur, D.. (2020). Acceleration through spectral density estimation. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:7553-7562 Available from https://proceedings.mlr.press/v119/pedregosa20a.html.

Related Material