Universal Asymptotic Optimality of Polyak Momentum

Damien Scieur, Fabian Pedregosa,


Thu Jul 16 6 a.m. PDT [ Join Zoom ]
Thu Jul 16 7 p.m. PDT [ Join Zoom ]
Please do not share or post zoom links


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 \emph{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.

Chat is not available.