PaperlayerView exact revision on arXiv

Source-linked AI summary

Revisiting AdaGrad in Stochastic Convex Optimization: Last Iterates, High Probability, and Lower Bounds

Weiming Ou, Xiao Wang

arXiv:2609.32729v1math.OCcs.LG

TL;DR

The paper asks whether standard AdaGrad methods admit reliable stochastic guarantees for last and averaged iterates under common noise and stability assumptions. It constructs lower bounds across output and noise settings and analyzes an ABC condition under bounded iterates. The results rule out uniform last-iterate rates and identify a bounded-iterate setting with noise-adaptive average-error bounds.

  • Problem

    Existing average-iterate guarantees under particular tail or bounded-domain assumptions do not establish a vanishing rate for the final point returned by standard updates.

    Source: §1 · p. 3

  • Method

    The paper constructs fixed-instance and horizon-dependent lower-bound examples under conditional-oracle assumptions, then applies regret analysis to derive an ABC upper bound under bounded iterates.

    Source: §2 · p. 6, §3.2 · p. 8, §4 · p. 12

  • Results

    The methods lack a universal vanishing expected last-iterate rate and, under finite variance, lack polynomial average-iterate rates with only polylogarithmic confidence dependence.

    Source: §4 · p. 12

  • Takeaways & Limitations

    Under bounded iterates, classical regret analysis gives noise-adaptive ABC average-error bounds; without a common radius, finite variance permits constant worst-case expected average error.

    Source: §4 · p. 12

    The high-probability average-iterate lower bound does not rule out vanishing error at fixed confidence or almost-sure convergence on its hard instance.

    Source: §3.2 · pp. 8–9

Abstract

from arXiv · show

AdaGrad and AdaGrad-Norm are widely used adaptive methods, but their precise behavior in stochastic convex optimization remains less understood. We first show that AdaGrad-Norm and AdaGrad do not admit any universal \textbf{last-iterate} rate, even under sub-Gaussian noise and bounded iterates. We then prove that bounded variance alone is too weak: even with bounded iterates, it cannot yield \textbf{high-probability average-iterate} rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight $\Omega(\log T/\sqrt T)$ lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that $\log T$ in existing average-iterate upper bounds is unavoidable. Finally, we show that this $\log T$ loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates ${O}(1/\sqrt{T})$.

1 Introduction

The paper examines whether standard AdaGrad methods have uniform stochastic guarantees across different outputs, noise assumptions, and iterate-stability conditions. It gives lower bounds for last and averaged iterates, then identifies bounded iterates under an ABC condition as a setting with explicit noise-adaptive average-error bounds.

1.1 Our contributions

  • Every prescribed vanishing expected last-iterate rate is violated along a subsequence on one fixed sub-Gaussian instance, although the instance still converges.The construction keeps all iterates within an arbitrarily prescribed radius; its bounded pulses delay accumulator growth.Source: §1.1 · pp. 3–4
  • Theorem 3.5 rules out polynomial-in-T rates with only polynomial dependence on log(1/δ) for uniform averaging on one fixed infinite-horizon finite-variance instance within any prescribed radius.The fixed-instance quantifiers, averaged output, and arbitrary stability radius distinguish this statement from the last-iterate lower bound of Chezhegov et al. [5].Source: §1.1 · p. 4
  • Without a common stability radius, finite variance permits constant worst-case expected average error, while bounded noise yields an Ω(log T/√T) lower bound for fixed-parameter updates.The logarithmic bound also applies to inverse-square-root SGD; it is not a lower bound for every SGD schedule.Source: §1.1 · p. 4
  • Under bounded iterates, Theorem 3.14 gives an explicit noise-adaptive ABC expected average-error bound of O(T^-1 + C/T), including O(T^-1) when C = 0.This extends classical regret and self-bounding analysis [22] [43] and assumes trajectory stability rather than proving it.Source: §1.1 · p. 4

1.2 Related work

  • The average-output lower bound directly controls f(¯xT) − f(x⋆), unlike Chezhegov et al. [5], whose cited result concerns a last-iterate event.The proof keeps post-cascade iterates on the same side of the minimizer, so averaging cannot cancel the displacement.Source: §1.2 · p. 5
  • The Ω(log T/T) lower bound addresses uniformly averaged unprojected SGD on smooth convex objectives with bounded noise and a fixed inverse-square-root schedule, not all SGD schedules.The paper distinguishes this setting from Harvey et al. [14], whose logarithmic lower bound concerns a nonsmooth last iterate.Source: §1.2 · p. 5
  • Prior log-free noise-adaptive bounds include bounded-domain results [22] and bounded-iterate component-function results [43]; Theorem 3.14 instead gives explicit constants under a global conditional ABC model.Coordinate-wise adaptation under anisotropic smoothness and noise is studied by Liu et al. [28].Source: §1.2 · p. 5

2 Preliminaries and setup

The setup uses an oracle whose conditional assumptions are defined relative to the history before each query, while distinguishing fixed infinite-horizon instances from horizon-dependent families. It considers unprojected updates and introduces an ABC noise condition alongside the other moment assumptions.

2 Preliminaries and setup

  • At each iterate, the oracle returns the true gradient plus noise; the filtration F_t records gradients through time t, making x_t measurable before the next query.The oracle may depend on time and history; independent identically distributed noise is imposed only where stated.Source: §2 · p. 6
  • The analysis distinguishes a single fixed infinite-horizon instance from a family whose objective or oracle changes with the horizon.The notation explicitly marks horizon-dependent objectives and minima as f_T and f*_T.Source: §2 · p. 6
  • The ABC condition includes bounded-variance noise as (A, B, C) = (0, 1, σ²), and C = 0 still permits state-dependent noise.The text states that the preceding noise models imply or are included in the ABC framework.Source: §2 · p. 6
  • Both updates are unprojected and include the current gradient in their denominators; in one dimension they coincide when their initial accumulators agree.Lower bounds use this shared scalar update, while the upper bound treats the normalizations separately.Source: §2 · p. 7

3 Main results

The results distinguish output and stability regimes: bounded iterates do not ensure a universal last-iterate rate or polynomial-in-T average-iterate rates with only polynomial dependence on log(1/δ). Under bounded iterates and the conditional ABC model, both methods instead admit noise-adaptive expected average-error bounds.

3.1 No universal vanishing last-iterate rate

  • For any prescribed vanishing rate, a fixed smooth convex quadratic and conditional sub-Gaussian oracle make both methods’ expected last-iterate error exceed it unboundedly along a subsequence, despite bounded iterates.The instance is selected after the proposed rate and then held fixed; the result does not assert one instance is slower than every vanishing sequence.Source: §3.1 · p. 7

3.2 A high-probability limitation even for the average iterate

  • On one fixed finite-variance instance within any prescribed trajectory radius, uniform averaging still admits no polynomial-in-T rate with only polynomial dependence on log(1/δ).The construction directly targets the averaged output; its designated cascade event leaves a displacement that persists across a substantial fraction of the horizon.Source: §3.2 · pp. 8–9

3.3 Finite variance permits constant worst-case average error

  • Without a common stability radius, bounded variance permits constant worst-case expected average error, but this lower bound uses a horizon-dependent family rather than one fixed instance.The construction has independent identically distributed additive noise and keeps the initial distance fixed across the family.Source: §3.3 · pp. 9–10

3.4 A logarithmic average-error lower bound under sub-Gaussian noise

  • Both methods have a logarithmic average-error lower bound under sub-Gaussian noise, but the result does not extend to all schedules, suffix averages, or projected variants.A scalar, fixed-magnitude-noise construction establishes the lower bound; no horizon-independent bounded-iterate radius is assumed.Source: §3.4 · pp. 10–11

3.5 Noise-adaptive upper bounds under the ABC condition

  • Under the conditional ABC model and bounded iterates, both methods have noise-adaptive expected average-error bounds; with bounded variance these specialize to O(T^-1 + σT^-1/2).The theorem assumes stability, while the lower bounds without a common trajectory radius do not.Source: §3.5 · pp. 11–12

4 Conclusion

The conclusion gathers the paper’s rate limitations and contrasts them with average-error bounds available under bounded iterates. The appendix follows the order of the main results, with proofs of the lower bounds followed by the two noise-adaptive upper bounds.

4 Conclusion

  • AdaGrad-Norm and AdaGrad have no prescribed uniform vanishing expected last-iterate rate under conditional sub-Gaussian oracles, even when all iterates stay within an arbitrarily small radius.A single fixed instance violates the proposed rate along a subsequence while still converging.Source: §4 · p. 12
  • Finite variance permits a fixed infinite-horizon instance that defeats polynomial average-iterate rates with polylogarithmic confidence dependence, even within any prescribed radius.The conclusion distinguishes this rate-confidence failure from convergence at fixed confidence and from Markov bounds.Source: §4 · p. 12
  • Without a common stability radius, horizon-dependent families yield constant worst-case expected average error under finite variance or a logarithmic lower bound under bounded noise.The logarithmic result also applies to fixed inverse-square-root SGD, not every stepsize or output; bounded iterates instead permit noise-adaptive ABC upper bounds.Source: §4 · p. 12

APPENDIX

  • The appendices prove the fixed-instance last-iterate result first, then the fixed-instance averaged-output confidence result, horizon-dependent average-error lower bounds, and finally the SGD consequence and two noise-adaptive upper bounds.AdaGrad’s lower-bound constructions are scalar, so both algorithms have the same trajectory.Source: APPENDIX · p. 16

A Proof of Theorem 3.1

The proof constructs a fixed infinite-horizon oracle whose delayed, bounded pulse can reveal slow last-iterate convergence at arbitrarily late times. The resulting instance still converges, so the construction obstructs a rate rather than convergence itself.

A Proof of Theorem 3.1

  • A bounded pulse can arrive arbitrarily late because the accumulator remains unchanged while the iterate stays at zero before the first pulse.The construction chooses curvature and pulse size to respect the prescribed stability radius and make subsequent noise-free updates contract.Source: A Proof of Theorem 3.1 · p. 16
  • At scheduled active times, the oracle draws a symmetric pulse or zero, and after the first nonzero pulse it returns zero noise permanently.This specifies one fixed infinite-horizon oracle; the pulse schedule is chosen independently of later evaluation times.Source: A Proof of Theorem 3.1 · pp. 16–17
  • The fixed displacement after a first pulse yields the lower bound at selected evaluation times, whose schedule can be chosen for any proposed vanishing rate.An explicit schedule uses τ_n = ⌈exp(exp n)⌉; for an arbitrary r_T → 0, the times can instead be selected recursively.Source: A Proof of Theorem 3.1 · p. 17
  • Every path has at most one nonzero pulse, and subsequent contraction makes the constructed iterate and its expected error converge to zero.This verifies convergence for the constructed instance, not a general fixed-instance convergence theorem.Source: A Proof of Theorem 3.1 · p. 17

B Proof of Theorem 3.5

The proof builds a fixed finite-variance instance with a bounded trajectory, using a finite cascade to increase normalization and preserve displacement through uniform averaging. Rare designated-sign paths then produce the confidence lower bound while the oracle remains fixed for the whole trajectory.

B Proof of Theorem 3.5

  • A finite cascade raises the normalization without exceeding a prescribed radius, leaving a displacement that persists through uniform averaging.The construction uses alternating small displacements and fixes their law independently of the eventual evaluation horizons.Source: B Proof of Theorem 3.5 · p. 17
  • The oracle is active only while designated signs occur before a finite random cutoff; after deviation or cutoff it permanently returns the deterministic gradient.Thus one law specifies the full infinite trajectory, with no later choice of T_n changing it.Source: B Proof of Theorem 3.5 · p. 18
  • Every path remains within radius D, as the only undesignated sign makes at most the specified small displacement and deterministic-gradient updates contract.The proof checks the active and inactive branches to verify stability and the oracle assumptions globally.Source: B Proof of Theorem 3.5 · p. 18
  • On rare designated-sign events, the iterate stays nonpositive through T_n, yielding a confidence failure whose probability and horizon are related by the constructed sequence.The sequence is eventually strictly increasing after relabeling, and the resulting impossibility holds on one fixed bounded instance.Source: B Proof of Theorem 3.5 · pp. 18–19
  • The rate-confidence failure is compatible with almost-sure and expected convergence of both the iterate and its uniform average on the constructed instance.Noise switches off almost surely after a finite time, after which the iterates contract toward zero.Source: B Proof of Theorem 3.5 · p. 19

C Proof of Theorem 3.8

The proof gives a horizon-dependent family of smooth convex objectives and iid finite-variance noise for which the averaged output has constant worst-case expected error. A rare-correction construction keeps the misleading-gradient event likely over the selected horizon.

C Proof of Theorem 3.8

  • Rare corrections make the gradient unbiased while leaving probability at least 1/4 that the first T noise values are all −2a.The correction probability is q = 1/T, and the noise values and probabilities remain fixed over time for each instance.Source: C Proof of Theorem 3.8 · pp. 19–20
  • On the no-correction event, the iterates remain in the linear region and move right, while the objective is nonnegative off that event.Multiplying the event’s probability by the lower bound on its objective value establishes the claimed average-error bound.Source: C Proof of Theorem 3.8 · p. 20
  • The construction uses a horizon-dependent family, so its lower bound does not establish nonconvergence of one fixed instance as T grows.The noise is iid on each chosen instance, with a variance bound common to the family.Source: C Proof of Theorem 3.8 · p. 20

D Proof of Theorem 3.10

The proof uses a constant-magnitude scalar oracle to expose harmonic accumulation of fluctuations and establish a logarithmic average-error lower bound for both AdaGrad methods. It also extends the lower-bound construction to SGD and contrasts it with a finite-time guarantee for a specified SGD setting.

D Proof of Theorem 3.10

  • A constant-magnitude oracle makes the adaptive accumulator deterministic, so the recursion has nonrandom weights and exposes harmonic fluctuation accumulation.The proof bounds a mean-zero martingale fluctuation and compares its positive part with the restoring drift and smoothing interval.Source: D Proof of Theorem 3.10 · pp. 20–21
  • The same scalar objective and oracle establish the logarithmic average-error lower bound for both AdaGrad-Norm and AdaGrad.The proof chooses a shallow linear region and smooths its junction with the minimum region.Source: D Proof of Theorem 3.10 · pp. 20, 22
  • The independent-noise SGD extension keeps its stepsize schedule and noise distribution fixed across horizons, while only the hard objective changes with T.The proof also gives a separate conditional-oracle version by making the SGD and scalar AdaGrad trajectories coincide.Source: D Proof of Theorem 3.10 · pp. 22–23
  • For constant-step SGD with α ≤ 1/(2L), the finite-time comparison follows from a distance-recursion calculation and is not a guarantee for every SGD schedule.The proof establishes finite-time moment existence before summing the recursion and applying convexity.Source: D Proof of Theorem 3.10 · p. 23

E Proof of Theorem 3.14

The proof combines expected averaging, bounded iterates, and the conditional ABC condition using a regret and self-bounding approach. Shared second-moment and integrability estimates justify the expectation and Jensen steps used later.

E Proof of Theorem 3.14

  • The proof combines expected averaging with bounded iterates and the conditional ABC condition, following a regret and self-bounding approach [22] [43].It establishes shared estimates before giving separate proofs for the two algorithms.Source: E Proof of Theorem 3.14 · p. 23

E.1 Shared self-bounding and integrability estimates

  • The shared estimates establish finite terms and uniform conditional second-moment bounds under ABC.Smoothness and bounded iterates bound the objective gaps; the resulting bounds make the accumulators and inner products integrable.Source: §E.1 · pp. 23–24
  • These integrability bounds justify martingale cancellation and the later applications of Jensen’s inequality.The proof records these justifications before using the shared estimates in either algorithm-specific argument.Source: §E.1 · pp. 23–24

E.2 AdaGrad-Norm

The AdaGrad-Norm proof uses a scalar Euclidean distance identity and delays taking expectations until after summing it pathwise. This preserves the dependence between the current gradient and its accumulator while closing a quadratic inequality.

E.2 AdaGrad-Norm

  • Summing the scalar distance identity pathwise before taking expectations avoids discarding the dependence between g_t and b_t.Scalar normalization makes a single Euclidean distance identity available.Source: §E.2 · p. 24
  • For the current-gradient update, bounded iterates and conditional unbiasedness cancel the noise inner product before convexity and Jensen’s inequality are applied.Jensen’s inequality is applied only after the pathwise estimate.Source: §E.2 · p. 24
  • The resulting quadratic inequality is squared and solved to establish (3.11).The proof uses the nonnegativity of S_T before solving the inequality.Source: §E.2 · p. 24

E.3 Coordinate-wise AdaGrad

The coordinate-wise AdaGrad proof bounds regret separately by coordinate, then combines the bounds into a scalar quadratic inequality. This establishes the result using only the global ABC condition, without requiring coordinate-wise ABC assumptions.

E.3 Coordinate-wise AdaGrad

  • Separate scalar regret bounds for each coordinate combine through summation and Cauchy–Schwarz, without coordinate-wise ABC assumptions.This yields a scalar quadratic inequality.Source: §E.3 · p. 25
  • The martingale terms cancel after the pathwise estimate because each bounded coordinate iterate is measurable with respect to the prior history.The proof then applies the global estimate and Cauchy–Schwarz.Source: §E.3 · p. 25
  • Solving the quadratic inequality and using convexity gives (3.12) under only the global ABC condition.The intermediate bound (E.7) retains more coordinate-wise second-moment information when available.Source: §E.3 · p. 25

E.4 Noise specializations and the role of stability

The noise specialization yields simplified bounds when the ABC residual coefficient C is zero, while the guarantees require a common almost-sure stability radius. They do not extend to last-iterate or polynomial high-probability bounds with polylogarithmic confidence dependence.

E.4 Noise specializations and the role of stability

  • When C = 0, the simplified bounds are (Γ2Q + Γb0)/T and (Λ2Q + Λβ0)/T, despite differing geometric constants.This case permits nonzero state-dependent noise and excludes only an additive residual term in the ABC model.Source: §E.4 · p. 26
  • Under conditional unbiasedness and bounded variance, the specialization has (A, B, C) = (0, 1, σ2) and Q = 2L.For AdaGrad, the analogous substitution is (Γ, b0) → (Λ, β0).Source: §E.4 · p. 26
  • The guarantees assume a common almost-sure stability radius and therefore do not contradict horizon-dependent lower bounds without such a radius.They also imply neither a last-iterate rate nor polynomial high-probability bounds with polylogarithmic confidence dependence; Markov’s inequality gives the weaker 1/δ dependence in (3.5).Source: §E.4 · p. 26

Related papers

Loading 2609.32729v1…