📊 statistics

On the Provable Suboptimality of Momentum SGD in Nonstationary Stochastic Optimization

This paper theoretically proves that in nonstationary stochastic optimization, momentum-based SGD variants incur an unavoidable drift-amplification penalty that causes systematic tracking lag and makes them provably suboptimal compared to vanilla SGD in drift-dominated regimes.

Original authors: Sharan Sahu, Cameron J. Hogan, Martin T. Wells

Published 2026-05-20

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Sharan Sahu, Cameron J. Hogan, Martin T. Wells

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to catch a moving target, like a frisbee being thrown by a friend who is constantly changing their throwing style and location. Your goal is to keep your hand right under the frisbee as it flies. This is what the paper calls "tracking a time-varying optimum."

In the world of machine learning, algorithms like Stochastic Gradient Descent (SGD) are the standard way to find the best solution. However, when the data changes over time (the "frisbee" keeps moving), the algorithm has to keep adjusting.

This paper investigates a popular trick used to speed up these algorithms called Momentum.

The Analogy: The Heavy Skateboard vs. The Agile Skater

To understand the paper's findings, let's use two characters:

The Agile Skater (Standard SGD): This skater reacts instantly to the ground beneath them. If the ground tilts, they lean immediately. They might wobble a bit due to bumps (noise), but they are very quick to change direction.
The Heavy Skateboarder (Momentum SGD): This skater is on a skateboard with a heavy flywheel. When they start moving, the wheel builds up speed. If they need to turn, the wheel's inertia makes it hard to stop or change direction quickly. They glide smoothly over small bumps, but if the path suddenly curves, they overshoot the turn because they are "stuck" in their old momentum.

The Core Discovery: Momentum is a Double-Edged Sword

The paper asks a simple question: When does the Heavy Skateboarder help, and when do they hurt?

The authors prove that in a stable, unchanging environment, the Heavy Skateboarder is great. The momentum helps them ignore small bumps (noise) and move faster toward the goal.

However, in a changing, drifting environment (where the target keeps moving), the paper reveals a fundamental flaw:

The "Stale" Problem: Momentum works by averaging past movements. But if the target moves, your past movements are now "stale" or outdated.
The Inertia Penalty: The paper shows that as you increase the momentum (make the skateboard heavier), the algorithm becomes slower to react to the new direction. It doesn't just wobble; it systematically lags behind the moving target.
The Divergence: If you make the momentum too strong (approaching 1.0), the lag becomes so severe that the algorithm actually performs much worse than the simple Agile Skater. The paper calls this an "information-theoretic barrier"—it's not just a math error; it's a physical limitation. You simply cannot average old, wrong information and expect to track a new, moving target perfectly.

The Three Parts of the Error

The authors break down the "tracking error" (how far off you are from the target) into three parts:

The Startup Lag: How long it takes to get moving. Momentum makes this worse because the heavy wheel takes longer to spin up.
The Noise Floor: The wobble caused by random bumps. Momentum helps smooth this out, but only up to a point.
The Drift Lag: The distance caused by the target moving. This is the killer. Momentum amplifies this lag. The faster the target moves, the more the heavy skateboarder overshoots and falls behind.

The "Inertia Window"

The paper introduces a concept called the "Inertia Window." Imagine the target suddenly changes direction.

The Agile Skater turns immediately.
The Heavy Skateboarder keeps going straight for a while because of the flywheel. The paper proves there is a specific, unavoidable amount of time (the window) where the momentum-based method must be behind the target, no matter how you tune the settings.

What the Experiments Showed

The researchers tested this on various scenarios, from simple math problems to complex neural networks (like the "teacher-student" model mentioned).

Result: When the target was moving slowly or the data was very noisy, momentum helped.
Result: When the target moved quickly (high drift) or the problem was "ill-conditioned" (like trying to slide down a very narrow, steep valley), increasing the momentum made the algorithm crash or lag significantly. The simple Agile Skater (SGD) remained stable and robust, while the Heavy Skateboarder struggled to keep up.

The Bottom Line

The paper concludes that momentum is not a magic bullet for dynamic situations.

While it is excellent for smoothing out noise in a static environment, it creates a "systematic lag" when the environment changes. If you are trying to track a moving target, using too much momentum is like trying to steer a heavy ship with a rudder that only responds to where the water was 10 seconds ago. The paper provides the mathematical proof that in these drifting scenarios, a simpler, more agile approach (Vanilla SGD) is often provably better and more stable.

Technical Summary: On the Provable Suboptimality of Momentum SGD in Nonstationary Stochastic Optimization

1. Problem Formulation

This paper addresses the problem of nonstationary stochastic optimization, where the objective is to track a time-varying minimizer $\boldsymbol{\theta}^*_t$ rather than converge to a static solution. The setting involves a sequence of strongly convex and smooth objective functions $G_t(\boldsymbol{\theta}) = \mathbb{E}_{X_t \sim \Pi_t}[g(\boldsymbol{\theta}, X_t)]$ , where the data distribution $\Pi_t$ shifts over time.

The central question investigated is: When does momentum help, and when does it provably hurt, in tracking drifting optima under strong convexity and smoothness?

While momentum methods like Polyak's Heavy-Ball (HB) and Nesterov's Accelerated Gradient (NAG) are standard for accelerating convergence in stationary settings, the authors hypothesize that in nonstationary regimes, the temporal averaging inherent in momentum may cause "stale" gradients to induce systematic tracking lag and instability.

2. Methodology and Theoretical Framework

The authors develop a unified theoretical analysis for Stochastic Gradient Descent (SGD) and its momentum variants (SGDM) under a stochastic predictability framework. Key methodological components include:

Assumptions: The analysis assumes $\mu$ -strong monotonicity and $L$ -Lipschitz continuity of the conditional mean gradient map. The noise is modeled as a martingale difference sequence with bounded second moments (and sub-Gaussian tails for high-probability bounds).
Decomposition of Tracking Error: The core analytical technique involves decomposing the tracking error $\|\boldsymbol{\theta}_t - \boldsymbol{\theta}^*_t\|^2$ $∥ θ_{t} - θ_{t}^{*} ∥^{2}$ into three distinct components:
1. Transient: Exponentially decaying initialization error.
2. Noise Floor: Irreducible error due to stochastic gradient variance.
3. Drift-Induced Lag: Irreducible error caused by the movement of the minimizer.
Extended State-Space Analysis: For SGDM, the authors transform the momentum update equations into a 2D dynamical system on extended state vectors. This allows them to analyze the coupled dynamics of the iterate and the momentum buffer using a Lyapunov function approach, revealing explicit scaling factors dependent on the momentum parameter $\beta$ .
Minimax Lower Bounds: To prove that the observed penalties are not merely artifacts of their analysis, the authors establish minimax lower bounds for dynamic regret under a gradient-variation budget. This involves constructing hard instances (localized bump functions) and using information-theoretic arguments (Fano's inequality) to demonstrate fundamental limits.

3. Key Contributions

3.1 Finite-Time Tracking Bounds with Explicit Momentum Penalties

The paper derives finite-time upper bounds for both SGD and SGDM.

SGD: The tracking error decomposes into a contraction term, a drift term scaling as $\Delta^2/(\mu^2 \gamma^2)$ , and a noise term scaling as $\sigma^2 \gamma / \mu$ .
SGDM: The bounds reveal explicit penalties introduced by momentum. As the momentum parameter $\beta \to 1$ $β \to 1$ :
- Sensitivity to initialization is amplified by a factor of $(1-\beta)^{-2}$ .
- The steady-state noise floor is inflated by a factor of $(1-\beta)^{-1}$ .
- The effective decay rate slows to $\exp(-\gamma \mu t / (1-\beta))$ .
- Stability constraints force the step size $\gamma$ to shrink as $\gamma \lesssim \mu(1-\beta)^2/L^2$ , which can further degrade drift tracking in ill-conditioned problems.

3.2 Time-Resolved High-Probability Bounds

Moving beyond expectation, the authors provide high-probability bounds that are time-resolved and drift-adaptive.

Unlike prior work relying on uniform worst-case drift bounds, these guarantees show that only recent drift significantly impacts the error due to exponential forgetting.
A critical finding is the drift-noise coupling: systematic misalignment between the iterate and the drifting minimizer amplifies the impact of stochastic gradient noise. This interaction scales as $(1-\beta)^{-2}$ , suggesting that momentum can exacerbate variance in dynamic settings.
These results motivate explicit forgetting mechanisms (e.g., restarts or windowing) to discard stale history.

3.3 Minimax Lower Bounds and the "Inertia Window"

The authors establish minimax lower bounds for dynamic regret, proving that the momentum-induced penalty is an information-theoretic barrier.

The lower bound decomposes into two regimes: a statistical regime (limited by noise/gradient variation) and an inertia-limited regime.
In the inertia-limited regime, the authors prove the existence of an unavoidable inertia window of length $\tau_\beta \approx \Omega(\kappa/(1-\beta))$ . During this period following a distribution shift, any SGDM policy must lag behind the drifting minimizer because it is forced to average stale gradients.
This confirms that in drift-dominated regimes, momentum is fundamentally worse than vanilla SGD, regardless of tuning.

4. Experimental Results

The theoretical findings are corroborated by experiments on drifting quadratics, linear/logistic regression, and a drifting teacher-student MLP.

Regime Split: In low-momentum, low-drift settings, momentum can outperform SGD by suppressing noise.
Degradation under Drift: As nonstationarity (drift magnitude), momentum ( $\beta$ ), or ill-conditioning ( $\kappa$ ) increases, SGDM performance degrades sharply.
Robustness of SGD: Vanilla SGD remains comparatively robust across varying noise levels and drift intensities, avoiding the compounded inertia and variance penalties observed in momentum methods.
Step Size Sensitivity: Increasing the step size $\gamma$ beyond conservative regimes does not recover tracking performance for SGDM; instead, it leads to orders-of-magnitude degradation, whereas SGD maintains stability.

5. Significance and Claims

The paper claims to provide the first comprehensive theoretical grounding for the empirical instability of momentum in dynamic settings.

Fundamental Trade-off: It formalizes the trade-off where temporal averaging (momentum) reduces variance in stationary settings but induces "stale-gradient averaging" that forces systematic lag in nonstationary settings.
Information-Theoretic Barrier: The work argues that the suboptimality of momentum under distribution shift is not an analytical artifact but a fundamental limitation: the "inertia window" is unavoidable for any algorithm that averages past gradients.
Practical Implications: The results delineate precise regime boundaries where vanilla SGD provably outperforms accelerated counterparts. They suggest that in dynamic environments (e.g., online forecasting, continual learning), practitioners should be cautious with high momentum values and consider explicit forgetting or restart mechanisms to mitigate the inertia penalty.

The authors conclude that while momentum accelerates convergence in static or slowly varying noise environments, it introduces a systematic fragility under distribution shift that scales inversely with $(1-\beta)$ , making it provably suboptimal in drift-dominated regimes.