Universal Average-Case Optimality of Polyak Momentum

Damien Scieur
Proceedings of the 37th International Conference on Machine Learning, Proceedings of Machine Learning Research (2020)

Abstract

Polyak momentum (PM), also known as the heavy-ball method, is a widely used optimization method that enjoys an optimal worst-case complexity on quadratic objectives. However, it's remarkable empirical success is not fully explained by this optimality, as the worst-case analysis is not representative of the typical complexity of an algorithm. In this work we establish a novel link between PM and the average-case analysis, which contrary to worst-case, is representative of the typical complexity of an algorithm. Our main contribution is to prove that \emph{any} method that has optimal complexity in the average-case analysis, converges under mild assumptions in the number of iterations to PM. This brings a new perspective on this classical method, showing that PM is both worst-case and (asymptotically) average-case optimal.