  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 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.
