Continuous-time Lower Bounds for Gradient-based Algorithms

Michael Muehlebach, Michael Jordan
Proceedings of the 37th International Conference on Machine Learning, PMLR 119:7088-7096, 2020.

Abstract

This article derives lower bounds on the convergence rate of continuous-time gradient-based optimization algorithms. The algorithms are subjected to a time-normalization constraint that avoids a reparametrization of time in order to make the discussion of continuous-time convergence rates meaningful. We reduce the multi-dimensional problem to a single dimension, recover well-known lower bounds from the discrete-time setting, and provide insight into why these lower bounds occur. We present algorithms that achieve the proposed lower bounds, even when the function class under consideration includes certain nonconvex functions.

Cite this Paper

BibTeX
@InProceedings{pmlr-v119-muehlebach20a, title = {Continuous-time Lower Bounds for Gradient-based Algorithms}, author = {Muehlebach, Michael and Jordan, Michael}, booktitle = {Proceedings of the 37th International Conference on Machine Learning}, pages = {7088--7096}, 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/muehlebach20a/muehlebach20a.pdf}, url = {https://proceedings.mlr.press/v119/muehlebach20a.html}, abstract = {This article derives lower bounds on the convergence rate of continuous-time gradient-based optimization algorithms. The algorithms are subjected to a time-normalization constraint that avoids a reparametrization of time in order to make the discussion of continuous-time convergence rates meaningful. We reduce the multi-dimensional problem to a single dimension, recover well-known lower bounds from the discrete-time setting, and provide insight into why these lower bounds occur. We present algorithms that achieve the proposed lower bounds, even when the function class under consideration includes certain nonconvex functions.} }
Endnote
%0 Conference Paper %T Continuous-time Lower Bounds for Gradient-based Algorithms %A Michael Muehlebach %A Michael Jordan %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-muehlebach20a %I PMLR %P 7088--7096 %U https://proceedings.mlr.press/v119/muehlebach20a.html %V 119 %X This article derives lower bounds on the convergence rate of continuous-time gradient-based optimization algorithms. The algorithms are subjected to a time-normalization constraint that avoids a reparametrization of time in order to make the discussion of continuous-time convergence rates meaningful. We reduce the multi-dimensional problem to a single dimension, recover well-known lower bounds from the discrete-time setting, and provide insight into why these lower bounds occur. We present algorithms that achieve the proposed lower bounds, even when the function class under consideration includes certain nonconvex functions.
APA
Muehlebach, M. & Jordan, M.. (2020). Continuous-time Lower Bounds for Gradient-based Algorithms. Proceedings of the 37th International Conference on Machine Learning, in Proceedings of Machine Learning Research 119:7088-7096 Available from https://proceedings.mlr.press/v119/muehlebach20a.html.

Related Material