Universal Asymptotic Optimality of Polyak Momentum

Damien Scieur · Fabian Pedregosa


Keywords: [ Optimization ] [ Convex Optimization ] [ Large Scale Learning and Big Data ] [ Optimization - Convex ]

[ Abstract ]
[ Slides
Thu 16 Jul 6 a.m. PDT — 6:45 a.m. PDT
Thu 16 Jul 7 p.m. PDT — 7:45 p.m. PDT


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.