Beyond Rate Optimality: How Polyak’s Momentum Shapes Non-Convex Optimization

Polyak's heavy-ball momentum is widely used in deep learning, where it often accelerates training, yet its advantage is not consistently reflected in standard smooth non-convex optimization theory. Since GD and SGD already attain optimal worst-case rates, any benefit of momentum within this framework must appear at a finer level. We therefore compare worst-case bounds beyond their asymptotic order, focusing on their dependence on the momentum parameter. Many existing convergence guarantees remain unfavorable to momentum, raising the question of whether this reflects loose analyses or genuine worst-case behavior. For SGD with heavy-ball momentum (SHB), SignGD with momentum (Signum), and deterministic Muon, we show that lower bounds on the respective averaged gradient norms can exceed the upper bounds for their non-momentum counterparts over commonly used ranges of $\beta$, even when each method uses its optimal constant step size. The gaps widen as $\beta$ increases and diverge in deterministic settings as $\beta \to 1$. For GD with heavy-ball momentum (HB), we further show that the same separation persists under the best-iterate squared gradient norm. These results show that the unfavorable momentum dependence in existing guarantees cannot in general be attributed solely to loose upper bounds, suggesting that the standard framework may miss key ingredients behind momentum's practical benefits, such as alternative convergence measures, structural assumptions, or a more refined treatment of stochasticity.