On the Provable Suboptimality of Momentum SGD in Nonstationary Stochastic Optimization

In this paper, we provide a comprehensive theoretical analysis of Stochastic Gradient Descent (SGD) and its momentum variants (Polyak Heavy-Ball and Nesterov) for tracking time-varying optima under strong convexity and smoothness. Our finite-time bounds reveal a sharp decomposition of tracking error into transient, noise-induced, and drift-induced components. This decomposition exposes a fundamental trade-off: while momentum is often used as a gradient-smoothing heuristic, under distribution shift it incurs an explicit drift-amplification penalty that diverges as the momentum parameter $\beta$ approaches 1, yielding systematic tracking lag. We complement these upper bounds with minimax lower bounds under gradient-variation constraints, proving this momentum-induced tracking penalty is not an analytical artifact but an information-theoretic barrier: in drift-dominated regimes, momentum is unavoidably worse because stale-gradient averaging forces systematic lag. Our results provide theoretical grounding for the empirical instability of momentum in dynamic settings and precisely delineate regime boundaries where vanilla SGD provably outperforms its accelerated counterparts.

Modern machine learning models are often trained in settings where the data they learn from keeps changing, such as recommendation systems adapting to changing user preferences or models tracking evolving financial patterns. A popular technique called momentum helps learning by building up a kind of “velocity” from previous updates, which can make training faster and smoother when the best solution is stable. Our paper shows that this stored velocity can become a weakness when the best solution itself is changing: it may continue pushing the algorithm toward where the solution used to be, causing it to lag behind. We prove that this lag is unavoidable in settings where the patterns in the data change over time, and that it becomes worse when the algorithm relies more heavily on momentum. This helps explain why momentum-based methods can sometimes become unstable or perform worse than simpler methods in dynamic settings. Our findings suggest that machine learning systems should be designed to discard stale information when the data, environment, or underlying patterns change, especially as AI systems are increasingly deployed in real-world settings that are constantly evolving.