Universal Average-Case Optimality of Polyak Momentum
Abstract
Polyak momentum (PM), also known as the heavy-ball method, is a widely used optimization method that enjoys an asymptotic optimal worst-case complexity on quadratic objectives. However, its remarkable empirical success is not fully explained by this optimality, as the worst-case analysis –contrary to the average-case– is not representative of the expected complexity of an algorithm. In this work we establish a novel link between PM and the average-case analysis. Our main contribution is to prove that any optimal average-case method converges in the number of iterations to PM, under mild assumptions. This brings a new perspective on this classical method, showing that PM is asymptotically both worst-case and average-case optimal.
Cite
Text
Scieur and Pedregosa. "Universal Average-Case Optimality of Polyak Momentum." International Conference on Machine Learning, 2020.Markdown
[Scieur and Pedregosa. "Universal Average-Case Optimality of Polyak Momentum." International Conference on Machine Learning, 2020.](https://mlanthology.org/icml/2020/scieur2020icml-universal/)BibTeX
@inproceedings{scieur2020icml-universal,
title = {{Universal Average-Case Optimality of Polyak Momentum}},
author = {Scieur, Damien and Pedregosa, Fabian},
booktitle = {International Conference on Machine Learning},
year = {2020},
pages = {8565-8572},
volume = {119},
url = {https://mlanthology.org/icml/2020/scieur2020icml-universal/}
}