Universal Asymptotic Optimality of Polyak Momentum

Part of Proceedings of the International Conference on Machine Learning 1 pre-proceedings (ICML 2020)

Bibtex »Metadata »Paper »

Bibtek download is not availble in the pre-proceeding


Damien Scieur, Fabian Pedregosa


<p>We consider the average-case runtime analysis of algorithms for minimizing quadratic objectives. In this setting, and contrary to the more classical worst-case analysis, non-asymptotic convergence rates and optimal algorithms depend on the full spectrum of the Hessian through its expected spectral distribution. Under mild assumptions, we show that these optimal methods converge asymptotically towards Polyak momentum \emph{independently} of the expected spectral density. This makes Polyak momentum universally (i.e., independent of the spectral distribution) asymptotically average-case optimal.</p>