Source-linked AI summary
Second-Moment Memory in Coordinatewise Adam
Jeonseong Kim
TL;DR
The paper asks whether Adam’s retained second-moment history can impede optimization despite finite-variance stochastic gradients. Using a finite-variance two-point oracle and a smooth convex embedding, it shows that positive normalized progress is O(M2^-1/2) after initialization and derives a same-order average-stationarity lower bound under stated scaling. Thus, long second-moment memory can slow optimization without infinite variance.
Problem
The optimization cost of Adam’s retained squared-gradient memory is not well understood, including under finite-variance stochastic gradients.
Method
The paper uses a finite-variance two-point oracle, bounds positive normalized updates, and embeds the construction in a smooth convex one-dimensional problem.
Results
O(M2^-1/2) is the expected positive normalized update after initialization, and the same-order effect yields an average-stationarity lower bound under the stated memory and stepsize scaling.
Takeaways & Limitations
Long second-moment memory can slow optimization even when gradient noise has finite variance.
Takeaways & Limitations
The construction works at the finite-variance endpoint p = 2 and assumes the stated parameter regime, including 1/2 ≤ β2 < 1.
Abstract
from arXiv · showhide
Adam retains a moving average of past squared gradients in its denominator, but the optimization cost of this memory is not well understood. We show that second-moment memory can itself suppress progress toward the optimum even under finite-variance stochastic gradients. For a simple two-point oracle, the expected positive normalized update is $O(M_2^{-1/2})$ after an initialization transient, where $M_2=(1-β_2)^{-1}$ is the second-moment memory length. We convert this directional bound, under the stated memory and stepsize scaling, into an average-stationarity lower bound of the same order on a smooth convex problem with normalized gap, smoothness, and variance. Long second-moment memory can slow optimization even when the gradient noise has finite variance.
1 Introduction
The paper isolates retained squared-gradient history as a source of optimization slowdown, even with finite-variance noise. It bounds the resulting directional progress and converts that bound into a stationarity lower bound on a smooth convex problem.
- Finite-variance construction: At the finite-variance endpoint p = 2, rare events with Γ = Θ(ρ^-1/2) contribute constant-order mass to the second-moment update.Choosing ρ = 1 − β2 matches the outlier recurrence time to Adam’s second-moment forgetting time.
- Motivation: Past squared gradients remain in Adam’s denominator after the gradients are no longer current, allowing rare events to suppress ordinary updates.Repeated rare events can refresh the stored square before it decays; the mechanism does not require infinite variance.
- Directional bound: O(M2^-1/2) is the expected positive normalized update after initialization in the low-signal regime, with M2 = (1 − β2)^-1.The result gives a finite-time upper bound on progress toward the optimum.
- Optimization lower bound: The paper converts the directional bound into an average-stationarity lower bound on a smooth convex one-dimensional problem with Δ = L = σ = 1.The bound applies under the stated memory and stepsize scaling.
- Comparison: A memoryless comparison has average stationarity Oκ(M2^-1/2) on the same instance, while setting M2 = T^2s yields horizon-dependent rates T^-s and T^-2s.The two updates differ through the accumulated second-moment state.
2 Effect of second-moment memory
The analysis uses a coordinatewise, finite-variance two-point oracle and controls positive normalized updates by conditioning on the age of the latest outlier. An initialization-transient bound then yields the memory-length scaling.
- Setup: Adam is analyzed in one coordinate with batch size one, fixed β1 and β2, predictable stepsizes, and nonnegative denominator offsets.The coordinatewise reduction sets d = 1 and uses zero weight decay.
- Memory length and transient: M2 = (1 − β2)^-1 is the second-moment memory length, and its geometric weights decay on that timescale.The initialization analysis controls the transient before the steady memory-length regime.
- Scale calculation: At population gradient µ > 0, the oracle writes a rare outlier into vt while unbiased compensation has only square-root scale.In the low-signal regime µ/σ ≲ √ρ, the positive numerator scale is √ρ and a remembered outlier keeps the denominator at constant order.
- Positive-update bound: The theorem bounds positive normalized updates by conditioning on the time since the latest outlier, because one surviving outlier certifies a large denominator.The proof partitions histories by outlier age and separately bounds the no-outlier event.
- Positive-update bound: The analysis focuses on (ut)+ because only positive normalized directions move the iterate toward the optimum in the corridor construction.Negative directions cannot help the iterate escape that corridor.
3 From the directional bound to optimization
The paper embeds the constant-gradient construction into a smooth convex function with a flat optimum, then uses a crossing bound to convert suppressed normalized progress into an optimization lower bound.
- Hard instance: The smooth embedding preserves derivative µ on a long interval before connecting smoothly to a flat optimum.It is convex, lower bounded, and C^1,1 with smoothness L.
- Hard instance: The constructed objective is convex, lower bounded, and L-smooth, with initialization at x_1 = W.
- Hard instance: The stochastic-gradient oracle and scaling keep the normalized initial gap equal to one while setting W at order M_2^1/2 and η at scale M_2/T.
- Hard instance: The condition M_2^3/2 ≤ T keeps the leading displacement within the initial distance scale, while initialization contributes displacement of order M_2^1/2.
- Optimization lower bound: Theorem 2 establishes the optimization lower bound under M_2^3/2 ≤ T, with normalized gap, smoothness, and variance all equal to one.
- Optimization lower bound: Remaining in the half-line x ≥ 0 for a constant fraction of the horizon forces average stationarity of order µ.
4 Memoryless comparison
The memoryless comparison removes the accumulated second-moment denominator and becomes signSGD when β_1 = 0. Its trajectory reaches the flat region much faster than the memory-limited Adam trajectory.
- Update comparison: With β_1 = 0, replacing √v_t by |g_t| yields exactly the raw signSGD update.
- Trajectory: The oracle signs are independent of the query point, so the comparison trajectory is a biased random walk.
- Trajectory: The memoryless comparison reaches the flat region after a crossing time of order T/M_2^1/2 under constant-order positive direction.
- Proof strategy: Hoeffding-based random-walk control bounds the comparison trajectory's time outside the flat region.
- Trajectory: The comparison trajectory spends only an O_κ(M_2^-1/2) fraction of the horizon outside the flat region.
5 Horizon-dependent rates
Allowing second-moment memory to grow with the horizon produces explicit horizon-dependent rates, while the memoryless comparison retains a different memory scaling.
- Rates: The horizon exponent records how memory length grows; the Adam bound scales as M_2^-1/2, while the memoryless update scales as M_2^-1.
- Scaling: For M_2 = T^2s with s ∈ (0, 1/3], the common stepsize is η = κM_2/T.
- Scaling: The condition M_2^3/2 ≤ T holds under the stated range of s, enabling the corollary's horizon-dependent rates.
- Moment extension: The oracle satisfies the centered p-th moment bound for every 1 < p ≤ 2, extending the construction beyond the finite-variance endpoint.
A Bias correction
The bias-correction analysis shows that correcting the second-moment accumulator does not remove the memory-dependent directional suppression.
- Bias correction: The paper defines a bias-corrected Adam direction for fixed β_1, β_2 and any predictable nonnegative denominator offset.
- Result: Correcting v_t contributes at most a factor one to the sum over outlier ages, and the corrected direction remains O(M_2^-1/2).
- Bias correction: Bias correction for the first moment cancels the total first-moment weight.
B Finite-p moment bound
The oracle satisfies the moment assumption across the full range 1 < p ≤2, establishing the finite-p extension beyond the endpoint p = 2.
- Lyapunov’s inequality and condition (5) establish the centered moment bound for every 1 < p ≤2.
- The oracle satisfies the moment assumption throughout the full range 1 < p ≤2.