acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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 **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 **high-probability average-iterate** rates, and without bounded iterates it may not even guarantee convergence in expectation. Besides, we construct tight lower bounds for both AdaGrad-Norm and AdaGrad under sub-Gaussian noise, showing that in existing average-iterate upper bounds is unavoidable. Finally, we show that this loss disappears once bounded-iterate condition is imposed: under a general ABC condition, both methods achieve rates .

Primary area:
optimization
Keywords:
AdaGrad, Stochastic convex optimization, Last iterate, High probability, Lower bounds

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_YvhUOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors provide a comprehensive analysis of AdaGrad under various settings. More specifically, they first establish negative results for last-iterate convergence (Theorem 3.1, under sub-Gaussian noise), high-probability convergence guarantees (Theorem 3.2), and lower bounds for the averaged iterate under different stochastic settings (Theorems 3.3 and 3.4). In addition, the authors derive upper bounds on the convergence of AdaGrad-Norm/AdaGrad (Theorem 3.5).

Critical strengths

I find the results of this paper extremely valuable, particularly the negative results for AdaGrad. First, some of these results appear to be novel. For instance, I am not aware of any results in the existing literature analogous to Theorem 3.1, which concerns the last-iterate convergence of AdaGrad in the stochastic case. Moreover, the result for sub-Gaussian noise in Theorem 3.4 complements the existing literature (e.g., [1], which establishes high-probability convergence guarantees for the averaged iterate).

Second, I would also like to highlight the proofs themselves, as the techniques developed in this paper may be useful for the future analysis of other adaptive methods, both in the context of high-probability and last-iterate convergence. In particular, I would like to highlight Theorem 3.1: the idea of using rare signals to push the iterate away from the neighborhood of the optimum is especially interesting.

Critical weaknesses

In my view, the only weakness of the paper is Theorem 3.5, which, as the authors themselves emphasize, extends existing results. Interestingly, the authors cannot actually obtain a stronger result than Theorem 3.5: extending the analysis to high-probability guarantees is limited by Theorem 3.2, while attempting to remove the bounded-iterates assumption runs into the lower bound established in Theorem 3.3. Nevertheless, it seems that more informative guarantees would be upper bounds that match at least the lower bounds in Theorems 3.2 and 3.3 (for Theorem 3.4, a corresponding high-probability convergence result already exists in [1]).


References

[1] Liu et al. (2023). High Probability Convergence of Stochastic Gradient Methods

Questions for authors
  1. Is it possible to establish matching upper bounds for Theorems 3.2 and 3.3?
3 comments

Thank you for your assessment. We agree that matching upper bounds would sharpen the characterization, and have clarified both the role of Theorem 3.5 and the remaining gaps. All newly added or revised text in the manuscript is highlighted in blue.

1. Role of Theorem 3.5

Theorem 3.5 provides the positive counterpart to the lower bounds: under bounded iterates, classical regret analysis yields explicit noise-adaptive expected average-error guarantees for both normalizations under the conditional ABC model, including O(T−1)O(T^{-1}) when C=0C=0.

Sections 1.2 and 3.5 now identify its contribution as this extension and its explicit constants. The paper’s principal new conclusions are the lower bounds, particularly Theorem 3.1, which excludes every prescribed vanishing expected last-iterate rate under the stated conditional-oracle assumptions. The ABC result explains why these last-iterate and confidence limitations can coexist with favorable expected average-error guarantees.

2. Matching upper bounds for Theorems 3.2 and 3.3

We have not established matching upper bounds for these two theorems. The revised discussion distinguishes the available guarantee from the unresolved sharp characterization.

For Theorem 3.2, Theorem 3.5 and Markov’s inequality give, under bounded variance and bounded iterates, a bound of orderO(1δT+σδT)O\left(\frac{1}{\delta T} +\frac{\sigma}{\delta\sqrt T}\right)with probability at least 1−δ1-\delta. Remark 3.5 and Eq. (6) state this guarantee. This bound does not contradict Theorem 3.2, which excludes polynomial decay in TT combined with polylogarithmic dependence on 1/δ1/\delta. Determining the optimal polynomial dependence on 1/δ1/\delta while retaining the stated rate in TT remains an open question.

For Theorem 3.3, the constant lower bound rules out vanishing uniform worst-case expected error. A matching constant upper bound without trajectory control requires further analysis; the lower bound alone does not establish it. Remark 3.12 now states this gap explicitly.

We hope these clarifications address your concerns. We would welcome any further questions or discussion.

Reviewer_YvhUOpenReview ↗

Response to the Authors

Dear Authors,

Thank you for your response and the additional clarifications. Based on your comments and your replies to the other reviewers, I have no further questions and am happy to maintain my positive assessment of the paper.

Best regards,

Reviewer

Thank you for your positive assessment. We sincerely appreciate the time and effort you have devoted to this discussion.

Reviewer_HyPSOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies standard unprojected AdaGrad-Norm and coordinate-wise AdaGrad for smooth convex stochastic optimization. For every prescribed vanishing rate, it constructs a fixed instance violating that expected last-iterate rate, despite sub-Gaussian noise and bounded trajectories. Under finite variance, it also constructs a bounded instance ruling out polynomial averaged-error rates with polylogarithmic confidence dependence. A separate horizon-dependent family establishes nonvanishing worst-case expected averaged error without a common trajectory bound.

The main quantitative lower bound is Ω(log⁡T/T)\Omega(\log T/\sqrt{T}) expected error at the uniformly averaged iterate under bounded noise and fixed algorithm parameters. A related construction applies to SGD with a fixed inverse-square-root stepsize schedule. Conversely, assuming bounded trajectories and a conditional ABC moment condition, the paper derives noise-adaptive expected averaged-error bounds of order O(T−1+C/T)O(T^{-1}+\sqrt{C/T}).

The contributions are theoretical, supported by explicit one-dimensional counterexamples and complete proofs. The results distinguish fixed-instance behavior from horizon-dependent worst-case guarantees and clarify how oracle assumptions, output choice, and trajectory stability affect convergence.

Critical strengths

A useful logarithmic lower bound under bounded noise. The paper gives a one-dimensional, smooth convex construction establishing Ω(log⁡T/T)\Omega(\log T/\sqrt{T}) expected error at the uniformly averaged iterate for fixed-parameter AdaGrad updates. The construction starts at a minimizer and uses bounded noise. It therefore identifies a limitation under relatively regular conditions, and its extension to fixed inverse-square-root SGD broadens the result's relevance.

A precise separation between convergence and last-iterate rates. For every proposed vanishing rate, the paper constructs one fixed infinite-horizon instance that violates that rate while still converging, with sub-Gaussian noise and bounded trajectories. Within the stated conditional-oracle model, this clarifies that qualitative convergence and trajectory stability alone do not provide a uniform quantitative last-iterate guarantee.

Critical weaknesses

Several headline claims require qualification. The abstract suggests fixed-instance nonconvergence in expectation, whereas Theorem~3.3 establishes a horizon-dependent worst-case family. The high-probability impossibility also excludes a specific combination of polynomial time decay and polylogarithmic confidence dependence, rather than all high-probability guarantees. Moreover, exact logarithmic ``tightness'' requires an identified matching upper bound; the cited unprojected analyses retain additional logarithmic factors. These statements overstate the established conclusions.

The incremental novelty of the high-probability obstruction needs clearer positioning. Chezhegov et al.\ (2025) state a last-iterate lower bound, but their zero-momentum threshold-hitting proof keeps every iterate above the threshold on the relevant event. An averaged-output obstruction therefore follows directly from that proof. The present cascade provides a useful refinement through its arbitrary prescribed trajectory radius, including D<ηD<\eta with fixed parameters.

Questions for authors
  1. Abstract and theorem quantifiers. Is the abstract's statement about convergence in expectation intended only as the absence of a vanishing uniform worst-case guarantee? Theorem~3.3 uses a horizon-dependent family and does not establish fixed-instance nonconvergence. Please also specify that Theorem 3.2 excludes polynomial time decay with polylogarithmic confidence dependence, since weaker high-probability guarantees remain possible.

  2. Exact logarithmic tightness. Which upper theorem establishes the matching O(log⁡T/T)O(\log T/\sqrt{T}) expected averaged-error bound for the stated unprojected updates, fixed parameters, and conditional sub-Gaussian model? Please retain all logarithmic factors and clarify whether the match covers both AdaGrad-Norm and coordinate-wise AdaGrad. The identified Liu et al.\ and Attia--Koren bounds do not directly provide this match.

  3. Increment over the earlier confidence lower bound. In the zero-momentum specialization of Chezhegov et al. (2025), the first-hitting-time argument keeps every iterate above the threshold on the relevant event, also obstructing uniform averaging. Which additional properties distinguish Theorem~3.2 beyond this consequence? In particular, is the primary refinement the arbitrary prescribed radius, including D<ηD<\eta with fixed algorithm parameters?

1 comment

Thank you for identifying where the headline claims required more precise qualifications. We have corrected their scope and revised the comparison with prior work. All newly added or revised text in the manuscript is highlighted in blue. These revisions retain the lower-bound conclusions proved in the paper while making their interpretation explicit.

1. Scope and quantifiers

The revised abstract and Section 3.3 now state that Theorem 3.3 excludes a vanishing uniform worst-case expected guarantee through a horizon-dependent family. The smoothness and variance bounds, initial distance, and algorithm parameters remain common across the family. This is distinct from nonconvergence on a single fixed instance; see Section 3.3 and Remark 3.6.

Theorem 3.2 excludes bounds of the form K0[T−a+P(log⁡(1/δ))T−b],a,b>0,K_0\left[T^{-a}+P\left(\log(1/\delta)\right)T^{-b}\right],\qquad a,b>0, with K0K_0 and the polynomial PP independent of T,δT,\delta. Remark 3.5 now explicitly clarifies that Theorem 3.2 excludes polynomial decay in TT combined with polylogarithmic dependence on 1/δ1/\delta, and does not rule out all high-probability rates.

2. Logarithmic lower bound and upper-bound comparison

We agree that the cited theorems do not establish the exact expected-error match requested in your question. We have therefore removed the exact-tightness wording.

The substantive conclusion of Theorem 3.4 remains: a log-free uniform O(T−1/2)O(T^{-1/2}) expected average-error guarantee is impossible for these fixed-parameter updates, even with bounded noise and initialization at a minimizer.

Remarks 3.7–3.8 now clarify the comparison with existing upper bounds. The cited analyses of Liu et al. (2023a) and Attia–Koren retain additional logarithmic dependence. We have also revised the conclusion to highlight the open question of whether the logarithmic lower bound can be matched by an O(log⁡T/T)O(\log T/\sqrt{T}) upper bound on the ordinary expected average error for both AdaGrad-Norm and coordinate-wise AdaGrad, under the same assumptions and with fixed algorithm parameters.

3. Additional contribution beyond the earlier confidence obstruction

Your observation about the zero-momentum first-hitting-time proof is correct, and we now explicitly acknowledge its averaged-output implication in Section 1.2 and Remark 3.4.

The principal refinement is the arbitrary prescribed radius at fixed algorithm parameters, established together with minimizer initialization, containment of all trajectories, and one fixed infinite-horizon construction. Appendix B shows how the accumulator can grow while all displacements remain within the prescribed radius. More precisely, for every prescribed radius D>0D>0, however small, Theorem 3.2 constructs a fixed instance on which all iterates remain within distance DD of the minimizer for all time, with the algorithm parameters held fixed. Even on this bounded instance, no high-probability guarantee with constants independent of TT and δ\delta can combine polynomial decay in TT with only polylogarithmic dependence on 1/δ1/\delta.

We hope these revisions and clarifications address your concerns. We would welcome any further questions or discussion.

Reviewer_1b5sOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

This paper studies AdaGrad's convergence in terms of the last iterate and the average iterate for stochastic convex optimization. Specifically, the authors study how the gradient noise assumption (sub-Gaussian or bounded variance) and the bounded iterate assumption could impact convergence. They first show a negative result for the last iterate: even under sub-Gaussian noise and bounded iterates, AdaGrad's last-iterate convergence can be arbitrarily slow in expectation. Then, under the bounded variance and bounded iterate assumption, they rule out high-probability bounds with poly(1/T1/T) and polylog(1/δ1/\delta) dependence. Moreover, without bounded iterates, they show a constant lower bound for the average iterate in expectation. When the bounded variance is replaced by subgaussian noise, they establish a lower bound of Ω(log⁡T/T)\Omega( \log T /\sqrt{T}). Finally, for the upper-bound side, under the ABC condition and bounded iterates, they establish a rate of O(1/T+C/T)O(1/T + \sqrt{C/T}) in expectation for the average iterate.

Critical strengths

This paper addresses several gaps in our understanding of AdaGrad's convergence in stochastic convex optimization. For instance, most of the existing results concern the average iterate, and the paper complements this by showing a negative result for the last iterate. It also clarifies the necessity of the bounded iterate assumption and the subgaussian noise assumption in the existing convergence results.

Critical weaknesses
  • My main concern is that, in its current form, the paper is not very well organized and reads more like a loose collection of convergence results regarding AdaGrad without a coherent narrative. As shown in Table 1, the authors jump between different assumptions, the last iterate and the average iterate, in-expectation convergence and high-probability convergence, making it hard for the reader to follow. Due to the lack of discussion of related work, it is also difficult to put the results in context and understand what gaps the current paper address. I would suggest the authors reorganize the results according to problem assumptions. For instance:
    • Under the subgaussian noise and bounded iterate assumptions: Levy et al. (2018) proved that the average iterate of AdaGrad achieves O(1/T+σ/T)O(1/T + \sigma / \sqrt{T}) in expectation. In contrast, this paper shows that the last iterate can converge arbitrarily slowly.
    • Under the subgaussian noise assumption only: Liu et al. (2023a) establish an average-iterate rate of O~(1/T+σ/T)\tilde{O}(1/T + \sigma / \sqrt{T}) in expectation. This paper shows a lower bound of Ω(σlog⁡T/T)\Omega(\sigma \log T / \sqrt{T}), and thus a log-free expected bound is impossible in this setting.
    • Under the bounded variance and bounded iterate assumptions: The average-iterate rate of O(1/T+σ/T)O(1/T + \sigma / \sqrt{T}) in expectation is known from Levy et al. (2018). This paper generalizes the convergence result to the ABC condition, and also shows that, unlike the subgaussian setting, it is impossible to obtain high-probability bounds with poly(1/T1/T) and polylog(1/δ1/\delta) dependence.
    • Under the bounded variance assumption only: Unlike the subgaussian case, where one can establish a O~(1)\tilde{O}(1) bound on the iterate, the authors show that the iterate of AdaGrad can grow as Θ(T)\Theta(\sqrt{T}) with constant probability, and as a result, there is a constant lower bound for the average iterate.
  • The exposition of the paper can also be much improved. The sentences in papers can be hard to parse with nonstandard terminology, and the main messages are often obscured by irrelevant technical details. As an example, for the contributions in Section 1.1, it is unclear to me what rTr_T, "delayed bounded pulses", and "pulse cascade" refer to on my first read. The authors also overly emphasized "fixed infinite-horizon instance" versus "horizon-dependent family", which distracts readers from the key assumptions in these lower-bound results, i.e., finite-variance noise.
Questions for authors

The authors should better clarify how the lower-bound constructions in this paper are related to and differ from the existing literature. For instance, how is the construction in Theorem 3.2 different from the one in Chezhegov et al. (2025)? While the lower bound in that paper is in terms of the last iterate, what are the challenges of extending it to the average iterate?

3 comments

Thank you for identifying the need for a clearer organization and comparison with prior work. We have revised the Introduction, contribution list, Table 1, and related-work discussion. All newly added or revised text in the manuscript is highlighted in blue. The revised presentation makes the central distinction explicit: assumptions sufficient for a log-free expected average-error bound can still fail to provide any prescribed vanishing expected last-iterate rate.

1. Organization and exposition

Following your suggestion, Section 1.1 and Table 1 now organize the results by four combinations of assumptions:

  • Sub-Gaussian noise with bounded iterates: log-free expected averaging versus arbitrarily slow expected last-iterate convergence.
  • Sub-Gaussian noise without an assumed trajectory radius: a logarithmic expected average-error lower bound.
  • Bounded variance with bounded iterates: a noise-adaptive expected upper bound alongside a limitation on confidence dependence.
  • Bounded variance without an assumed trajectory radius: a constant uniform worst-case expected average-error lower bound.

The table explicitly distinguishes the output and convergence criterion. We have also simplified the contribution descriptions, removed unexplained construction terminology from them, and clarified the relevant prior guarantees in Section 1.2.

This organization highlights the strength of Theorem 3.1: in the general conditional-oracle model, it excludes every prescribed vanishing expected last-iterate rate, even for a fixed-curvature strongly convex quadratic with bounded noise and an arbitrarily prescribed trajectory radius.

2. Relation to Chezhegov et al. (2025)

We now explicitly credit the averaging implication of their zero-momentum proof in Section 1.2 and Remark 3.4. On their bad event, every relevant iterate remains above the same positive threshold, so uniform averaging also remains above it. Thus, for that construction, extending the obstruction to averaging follows directly.

The additional requirement addressed by Theorem 3.2 is any prescribed radius D>0D>0, including D<ηD<\eta, with the algorithm parameters fixed, together with minimizer initialization, containment of every trajectory for all times, and one fixed infinite-horizon instance.

A sufficiently large first pulse from the minimizer produces a displacement approaching η\eta. Our construction instead increases the accumulator through small alternating displacements while preserving the prescribed radius; the resulting displacement then persists through averaging. Appendix B verifies these simultaneous requirements.

We hope the revised organization and precise comparison resolve your concerns, and would welcome any further questions or discussion.

I thank the authors for their detailed response and for reorganizing the paper according to my suggestions. The revised version has improved the clarity of the paper. However, I still find the presentation somewhat unnatural and difficult to follow.

In particular, I would appreciate more intuition behind the theoretical results. Presently, while Theorems 3.1-3.5 all include proof sketches and appear to be technically correct, even after reading them a few times, I still struggle to grasp the key ideas underlying the constructions or to understand why one should expect such results to hold. I believe the paper would benefit from a more intuitive explanation of the main ideas and the reasoning that motivates these constructions.

For these reasons, I am inclined to maintain my original score. I encourage the authors to further improve the exposition, particularly by finding more effective ways to communicate the intuition behind their theoretical results.

Thank you for your further feedback. We agree that the presentation should explain the motivation behind the constructions more explicitly. A common theme is how AdaGrad’s accumulated squared gradients interact with the trajectory: the accumulator can remain unchanged during a long quiet period, or become large while the iterates stay close to the minimizer. The following explanations clarify why we use each construction. (We have revised the manuscript with the revised text highlighted in red color. )

Theorem 3.1: waiting does not reduce the response to a first disturbance. At the minimizer, a period without noise leaves both the iterate and the accumulator unchanged. Consequently, a bounded noise event can cause the same fixed displacement however late it occurs. For any proposed vanishing rate, we choose possible first-event times sufficiently late that the proposed rate is much smaller than their occurrence probabilities. This defeats the expected last-iterate rate along a subsequence. Each trajectory nevertheless experiences at most one noise event and then converges. Averaging dilutes a late disturbance through the many preceding iterates at the minimizer.

Theorem 3.2: building a large denominator without moving far. To keep the average away from the minimizer, we need a small displacement to persist for many iterations. A large accumulator provides this persistence by making subsequent corrective updates very small. The challenge is building that accumulator within an arbitrarily small radius: a single very large gradient from the minimizer would cause a displacement close to η\eta. We therefore construct a rare sequence that moves back and forth between two nearby points. Each reversal undoes the displacement, but preserves the accumulated squared gradients. Ending at the point away from the minimizer leaves a small error that takes a very long time to correct. The large gradients are sufficiently rare to respect the variance bound. The resulting delay grows exponentially with the sequence length, whereas the logarithm of the inverse event probability grows only quadratically, yielding the stated confidence obstruction.

Theorem 3.3: unbiasedness can rely on a correction that is absent throughout a run. We arrange for the usual gradient observations to point away from the minimizer, with a rare large correction maintaining the correct mean. Over the chosen horizon, the correction is absent with constant probability. The usual gradients are small, so the accumulator remains bounded and the algorithm continues moving in the wrong direction. Balancing the correction probability and magnitude under the variance constraint leads to an objective slope of order T−1/2T^{-1/2}. The resulting displacement is of order T\sqrt T, producing a constant lower bound on expected objective error at that horizon.

Theorem 3.4: early noise is repeatedly included in the average. The stochastic gradients have fixed magnitude, giving update sizes of order s−1/2s^{-1/2}. An early noise perturbation changes the position, and that change contributes to many subsequent iterates. In the noise component of the average, a perturbation at time ss retains the factor (T−s)/T(T-s)/T of its original displacement. In particular, a perturbation from the first half of the run retains at least half of its influence. The squared contributions therefore accumulate like ∑s≤T/21/s\sum_{s\le T/2}1/s, producing fluctuations of order log⁡T\sqrt{\log T}. We choose a shallow objective so that its restoring drift cannot erase these fluctuations. A slope of order log⁡T/T\sqrt{\log T/T}, with a sufficiently small constant, achieves this balance; multiplying it by the surviving positive displacement yields the log⁡T/T\log T/\sqrt T lower bound.

Theorem 3.5: two complementary restrictions control cumulative expected error. The ABC condition bounds accumulated gradient energy through cumulative optimization error and the residual noise term. Bounded iterates, through the regret bound, then control cumulative expected error by the square root of that energy. When C=0C=0, these restrictions keep cumulative expected error bounded: the error cannot grow indefinitely when it is bounded by a quantity growing only as its square root. Dividing by TT gives the T−1T^{-1} averaged-error rate. When C>0C>0, the residual term allows additional energy proportional to CTCT, producing the C/T\sqrt{C/T} contribution.

We sincerely appreciate the time and effort you have devoted to helping us improve the presentation.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.