Timezone: »
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.
Author Information
Damien Scieur (Samsung - SAIT AI Lab, Montreal)
Fabian Pedregosa (Google)
More from the Same Authors
-
2023 Poster: Second-order regression models exhibit progressive sharpening to the edge of stability »
Atish Agarwala · Fabian Pedregosa · Jeffrey Pennington -
2022 Poster: Only tails matter: Average-Case Universality and Robustness in the Convex Regime »
LEONARDO CUNHA · Gauthier Gidel · Fabian Pedregosa · Damien Scieur · Courtney Paquette -
2022 Poster: On Implicit Bias in Overparameterized Bilevel Optimization »
Paul Vicol · Jonathan Lorraine · Fabian Pedregosa · David Duvenaud · Roger Grosse -
2022 Spotlight: On Implicit Bias in Overparameterized Bilevel Optimization »
Paul Vicol · Jonathan Lorraine · Fabian Pedregosa · David Duvenaud · Roger Grosse -
2022 Spotlight: Only tails matter: Average-Case Universality and Robustness in the Convex Regime »
LEONARDO CUNHA · Gauthier Gidel · Fabian Pedregosa · Damien Scieur · Courtney Paquette -
2021 Poster: Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets »
Thomas Kerdreux · Lewis Liu · Simon Lacoste-Julien · Damien Scieur -
2021 Spotlight: Affine Invariant Analysis of Frank-Wolfe on Strongly Convex Sets »
Thomas Kerdreux · Lewis Liu · Simon Lacoste-Julien · Damien Scieur -
2021 Poster: Connecting Sphere Manifolds Hierarchically for Regularization »
Damien Scieur · Youngsung Kim -
2021 Spotlight: Connecting Sphere Manifolds Hierarchically for Regularization »
Damien Scieur · Youngsung Kim -
2021 : Introduction »
Fabian Pedregosa · Courtney Paquette -
2021 Tutorial: Random Matrix Theory and ML (RMT+ML) »
Fabian Pedregosa · Courtney Paquette · Thomas Trogdon · Jeffrey Pennington -
2020 Poster: Extra-gradient with player sampling for faster convergence in n-player games »
Samy Jelassi · Carles Domingo-Enrich · Damien Scieur · Arthur Mensch · Joan Bruna -
2020 Poster: Acceleration through spectral density estimation »
Fabian Pedregosa · Damien Scieur -
2020 Poster: Stochastic Frank-Wolfe for Constrained Finite-Sum Minimization »
Geoffrey Negiar · Gideon Dresdner · Alicia Yi-Ting Tsai · Laurent El Ghaoui · Francesco Locatello · Robert Freund · Fabian Pedregosa