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 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.
Research Areas
