Why Adam Beats SGD: The Math Behind Second-Moment Normalization

Paper: 2603.03099 Authors: Ruinan Jin, Yingbin Liang, Shaofeng Zou Categories: cs.LG, cs.AI

The Gap

Everyone knows Adam converges faster than SGD in practice. But existing theory says they should perform roughly the same—both get O(1/√T) convergence rates, both need similar iteration counts. The theory-practice mismatch has been an open embarrassment: we use Adam everywhere but can’t explain why it’s actually better.

Prior work (Kingma & Ba 2015, Reddi et al. 2018, Zaheer et al. 2018) focused on expectation-based convergence guarantees. They showed Adam and SGD both achieve similar rates in expectation. The problem? Real training cares about high-probability guarantees—you want to know “with 99% confidence, my loss will be below X after T steps,” not just “on average across infinite parallel universes.”

Empirical Reality              Theoretical Void              This Paper's Bridge
                                                            
Adam trains faster    -->   Existing theory says      -->  Stopping-time analysis
in practice                 Adam ~ SGD in expectation      reveals structural difference
                                                            
                            Gap: High-probability          Second-moment normalization
                            behavior unexplained           gives δ^(-1/2) vs δ^(-1)
                                                            
                            Bounded variance model         Martingale concentration
                            insufficient                   + variance decomposition

The Increment

One sentence: Before this paper, theory couldn’t distinguish Adam from SGD; after, we have the first proof that Adam’s second-moment normalization fundamentally improves high-probability convergence by a √δ factor.

Core Mechanism

The analysis has three interlocking pieces. First, they decompose Adam’s update into a “normalized SGD” view: instead of taking gradient steps, Adam takes steps normalized by the accumulated second moment. This normalization acts as an adaptive learning rate that shrinks when gradients are large and grows when they’re small.

Second, they introduce a stopping-time argument. Traditional analysis averages over all T iterations. Instead, they track when the algorithm “stops making progress”—when the gradient norm drops below a threshold. This stopping time τ is itself a random variable that depends on the optimization trajectory.

Third, they apply martingale concentration inequalities to bound how far the actual trajectory deviates from its expected path. Here’s where the magic happens: SGD’s variance accumulates linearly with each step, but Adam’s second-moment normalization keeps the variance per step bounded. When you sum up T steps, SGD needs a δ^(-1) penalty to control tail probability, while Adam only needs δ^(-1/2).

Adam's Internal Flow:

Gradient g_t  -->  [Square & Accumulate]  -->  v_t = β*v_(t-1) + (1-β)*g_t^2
                            |
                            v
                   [Normalize Step Size]
                            |
                            v
Update: x_t - (α/√v_t) * g_t  -->  Next iterate x_(t+1)

Key: Division by √v_t keeps per-step variance bounded
     SGD lacks this, so variance grows with gradient magnitude

Think of it like driving on a winding mountain road. SGD is like maintaining constant speed—when the road gets steep (large gradients), you accelerate dangerously; when it flattens (small gradients), you crawl. Adam is like cruise control that adjusts to terrain—it automatically slows on steep sections and speeds up on flat ones. The second moment v_t is your speedometer reading the “steepness,” and dividing by √v_t is the automatic brake/accelerator.

The stopping-time analysis is like asking: “How long until I reach the summit?” Instead of averaging over all possible routes, you track the specific path you’re on and ask when you’ll hit the “gradient small enough” milestone. The martingale bound says: “Even if you hit bad weather (unlucky gradient samples), the cruise control keeps you from veering too far off course.” SGD without cruise control can veer wildly, requiring much stronger safety margins (the δ^(-1) factor).

Key Concepts

• Second-Moment Normalization: Imagine you’re adjusting a recipe. SGD says “add 1 cup of each ingredient.” Adam says “add ingredients in proportion to how much you’ve used so far.” If you’ve been heavy-handed with salt (large gradients in that direction), Adam automatically reduces the next salt addition by dividing by √(accumulated salt usage). This prevents any single ingredient from dominating. Mathematically, instead of step size α, Adam uses α/√v_t where v_t tracks the sum of squared gradients. The square root is crucial—it’s the geometric mean that balances the scale.

• High-Probability vs Expectation Guarantees: Expectation tells you the average outcome if you ran training infinite times. High-probability tells you “in 99 out of 100 runs, you’ll achieve this.” It’s the difference between “average flight time is 3 hours” and “99% of flights arrive within 3.5 hours.” The confidence parameter δ controls this: δ=0.01 means 99% confidence. SGD’s guarantee degrades as δ^(-1)—to go from 90% to 99% confidence (δ: 0.1→0.01), you pay 10× in iteration count. Adam only pays √10 ≈ 3.16×.

• Stopping-Time Analysis: Traditional convergence proofs fix T iterations upfront and bound the final error. Stopping-time flips this: define a target error ε, then bound how many iterations until you hit it. The stopping time τ is random—it depends on which gradient samples you draw. The trick is proving that even though τ is random and depends on the past, you can still get concentration bounds. It’s like proving “even though you don’t know when you’ll finish the race, you can still bound your finish time with high probability.”

Framework Shift

Before (expectation-based):        After (high-probability):

E[f(x_T) - f*] < ε                P[f(x_τ) - f* < ε] > 1-δ
      |                                    |
      v                                    v
Average over all runs              Bound on single run
                                          |
SGD: Need T = O(1/ε^2)                   v
Adam: Need T = O(1/ε^2)            SGD: T = O(1/(ε^2*δ))
                                   Adam: T = O(1/(ε^2*√δ))
No distinction!                           ^
                                          |
                                   √δ improvement!

From “what happens on average” to “what happens in your actual training run,” the core shift is exposing how variance control translates to tail probability control.

Expert Assessment

Problem choice: This is a real gap, not manufactured. The Adam-vs-SGD mystery has been a thorn in optimization theory’s side since 2015. Practitioners know Adam works better, theorists couldn’t explain it—that’s a genuine intellectual debt. The paper sits at a sweet spot: not chasing incremental improvements, but resolving a foundational mismatch.

Method maturity: The stopping-time/martingale approach is clever, not brute force. It’s a natural tool from probability theory that hasn’t been fully exploited in optimization analysis. That said, the bounded variance assumption is doing heavy lifting—real neural nets violate this regularly. The authors acknowledge this but don’t explore how far the result extends. A simpler approach might be direct concentration inequalities without stopping times, but those typically give looser bounds.

Experimental integrity: This is a theory paper—no experiments to scrutinize. The proofs appear sound (modulo detailed verification), and the authors clearly state their assumptions. The bounded variance model is classical but restrictive. A red flag: they don’t discuss what happens when variance is unbounded, which is common in deep learning. The result is clean but potentially fragile.

Writing quality: The intro and main theorem are crisp. The proof sketch in Section 3 is readable. But Section 4 (full proofs) is dense and could use more intuition. The paper would benefit from a “proof roadmap” figure showing how the lemmas connect. Also, they bury the key insight—that second-moment normalization bounds per-step variance—in the middle of a proof. That should be a highlighted remark.

Verdict: weak accept — Solves a real problem with a novel technique, but the bounded variance assumption limits practical impact and the writing doesn’t fully capitalize on the insight’s elegance.

Takeaways

If you’re designing a new optimizer, steal the “variance normalization” principle: track some measure of gradient variability and divide your step size by it. This isn’t just about Adam—any algorithm that normalizes by accumulated statistics can potentially get better high-probability guarantees.

For theorists: stopping-time analysis is underused in optimization. If you’re stuck proving high-probability bounds with standard techniques, try defining a stopping time based on your convergence criterion and applying martingale concentration. The key trick here is showing the stopped process still concentrates despite τ being random.

For practitioners: this paper won’t change what you do (you’re already using Adam), but it gives you ammunition when someone asks “why not SGD?” The answer is now precise: Adam’s high-probability guarantees are fundamentally better by a √δ factor, which matters when you care about reliability, not just average performance.

One concrete technique: the variance decomposition in Lemma 3.2 (splitting variance into “within-step” and “across-step” components) is a general proof strategy that could apply to analyzing other adaptive methods like RMSprop or AdaGrad variants.