Continuous-Time Lower Bounds for Gradient-Based Algorithms
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
Text
Muehlebach and Jordan. "Continuous-Time Lower Bounds for Gradient-Based Algorithms." International Conference on Machine Learning, 2020.Markdown
[Muehlebach and Jordan. "Continuous-Time Lower Bounds for Gradient-Based Algorithms." International Conference on Machine Learning, 2020.](https://mlanthology.org/icml/2020/muehlebach2020icml-continuoustime/)BibTeX
@inproceedings{muehlebach2020icml-continuoustime,
title = {{Continuous-Time Lower Bounds for Gradient-Based Algorithms}},
author = {Muehlebach, Michael and Jordan, Michael},
booktitle = {International Conference on Machine Learning},
year = {2020},
pages = {7088-7096},
volume = {119},
url = {https://mlanthology.org/icml/2020/muehlebach2020icml-continuoustime/}
}