Timezone: »

 
Poster
Universal Asymptotic Optimality of Polyak Momentum
Damien Scieur · Fabian Pedregosa

Thu Jul 16 06:00 AM -- 06:45 AM & Thu Jul 16 07:00 PM -- 07:45 PM (PDT) @ Virtual
in Poster Session 41 »

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.

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

Author Information

Damien Scieur (Samsung - SAIT AI Lab, Montreal)
Fabian Pedregosa (Google)

More from the Same Authors