acceptodds
Under review as a conference paper at ICLR 2027

The Cube-Root Barrier for Almost-Sure Last-Iterate Convergence of SGD

Abstract

Almost-sure last-iterate convergence is the natural pathwise guarantee for stochastic gradient descent (SGD), which is typically run once with a deterministic stepsize schedule and returns its last iterate. We determine the fastest polynomial order of almost-sure last-iterate convergence that such a schedule can guarantee for smooth convex objectives under the standard conditional ABC second-moment condition, up to a slowly varying logarithmic correction. We establish a sharp cube-root barrier: the optimal polynomial exponent is , with a single schedule achieving every smaller exponent, while no deterministic schedule can guarantee a larger one. We further show that the lower bound already holds for one-dimensional smooth convex problems with fixed i.i.d. finite-variance gradient noise, and that a logarithmically corrected schedule attains this optimal cube-root order up to a polylogarithmic factor.

Primary area:
optimization
Keywords:
stochastic gradient descent, almost-sure convergence, last-iterate convergence, lower bounds, smooth convex optimization

Reviews

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

This paper investigates almost-sure last-iterate convergence rates of SGD for smooth convex optimization under the conditional ABC assumption. The authors establish a sharp cube-root barrier: a single deterministic stepsize schedule achieves every polynomial exponent below 1/31/3, while no predetermined deterministic schedule can guarantee a larger exponent. The lower bound covers arbitrary deterministic stepsize schedules by showing that the target convergence rate is either destroyed by recurrent finite-variance noise shocks or cannot be achieved due to slow progress on flat objectives.

Critical strengths
  1. Under the conditional ABC condition for smooth convex SGD, the lower bound shows that no positive deterministic stepsize schedule can guarantee an almost-sure last-iterate exponent above 1/31/3 for all admissible instances.

  2. The critical schedule αt=(t+1)−2/3\alpha_t=(t+1)^{-2/3} does not depend on the target exponent qq and attains every subcritical almost-sure last-iterate rate.

Critical weaknesses
  1. The paper states that it remains open whether stronger assumptions, such as bounded noise or a uniform sub-Gaussian tail bound, permit faster almost-sure last-iterate convergence rates. However, Liu and Zhou (2024) provide high-probability last-iterate bounds from which one can derive almost-sure convergence exponents exceeding 1/31/3 under conditional sub-Gaussian noise assumptions.

  2. Corollary 2.3 characterizes the supremal convergence exponent for polynomially decaying stepsizes, but does not clarify whether the endpoint q=2p−1q=2p-1 is admissible under the conditional ABC condition when p∈(1/2,2/3)p\in(1/2,2/3), which remains to be addressed.

  3. The proofs of Lemma A.9 and Proposition D.1 are largely similar. A more concise presentation of these proofs would reduce repetition and improve the organization of the theoretical analysis.

Questions for authors
  1. The authors should compare the assumptions and stepsize requirements more carefully and clarify both the scope of the cube-root barrier and the remaining open questions under stronger tail assumptions.

  2. Is the endpoint q=2p−1q=2p-1 admissible under the conditional ABC condition when p∈(1/2,2/3)p\in(1/2,2/3)?

  3. The paper focuses on asymptotic almost-sure last-iterate convergence but does not provide explicit finite-time guarantees. Since practical algorithms typically stop after a prescribed number of iterations, can nonasymptotic expected error bounds and corresponding iteration complexity guarantees be established for the fixed last iterate xTx_T? If so, can these guarantees match the best known rates in the literature under comparable assumptions?

5 comments
AuthorsOpenReview ↗

Response to Reviewer ygcs

  1. Thank you for your careful review and for pointing out that, under uniform conditional sub-Gaussian noise and deterministic initialization, such rates already follow from the high-probability bound of Liu and Zhou (2024). We have cited Liu and Zhou (2024) in our work now and shown how Theorem C.2 of their extended paper allows one stepsize schedule of order (t+1)−1/2(t+1)^{-1/2} for all horizons and confidence levels. In Appendix F we apply Borel--Cantelli to their bound to obtain f(xT)−f∗=o(T−q)f(x_T)-f^*=o(T^{-q}) almost surely for every 0<q<1/20<q<1/2 along the same run. This also covers uniformly bounded gradient noise as well. We have corrected Sections 1, 4.1, and 5 to clarify that our cube-root barrier concerns the larger conditional ABC class, which permits heavy-tailed noise.

  2. On your question about q=2p−1q=2p-1, we can now show that the strict inequality in Theorem 2.1 is necessary throughout 1/2<p≤2/31/2<p\le 2/3. Proposition E.1 extends our shock argument to give a one-dimensional quadratic on which t2p−1(f(xt)−f∗)t^{2p-1}(f(x_t)-f^*) is unbounded almost surely. Together with Theorem 2.1, this gives the exact range of rates in Corollary 2.4. The same construction supplies the stochastic case of Proposition 2.3 at q=1/3q=1/3 for arbitrary positive deterministic schedules. Its shocks are independent with variance one at every step, and their laws may vary as conditional ABC permits. Theorem 2.2 already gives fixed i.i.d. counterexamples for every q>1/3q>1/3. Whether one schedule guarantees the exact cube-root rate for every fixed i.i.d. finite-variance oracle remains open.

  3. The estimates we used to prove Theorem 2.1 also let us bound the expected error of the last iterate after a fixed number of steps. For the critical schedule αt=(t+1)−2/3\alpha_t=(t+1)^{-2/3}, Section 4.2 shows that E[f(xT)−f∗]≤KT−1/3\mathbb{E}[f(x_T)-f^*]\le K T^{-1/3} for every integer T≥1T\ge1 under the same conditional ABC assumptions. Thus T≥(K/ε)3T\ge(K/\varepsilon)^3 iterations suffice for expected error at most ε\varepsilon. Appendix B.3 gives KK explicitly in Proposition B.2 and derives the corresponding confidence bound at a prescribed horizon.

As for how this compares with the best known rates, Vaidyan et al. (2026) obtain a sharper O(T−1/2)O(T^{-1/2}) expected last-iterate bound by choosing their stepsizes for the prescribed horizon TT. Remark 4.1 shows that their result applies under our conditional ABC assumptions when the initialization is deterministic.

  1. Finally, we followed your suggestion to consolidate the two proofs. Lemma A.9 gives the weighted-potential argument for SGD, and Proposition C.1 (formerly D.1) now shows how to apply that proof directly to its general recursions.

In the revised paper, all edits and additions appear in blue.

I appreciate the author's response. But still why not also discuss Theorem 3.5(ii) of Vaidyan et al. (2026) in Remark 4.1, as it provides an anytime guarantee that seems more closely aligned with the setting of this paper?

In addition, the minor typos and reference errors pointed out in the original review have not yet been corrected. Please check and revise them accordingly.

AuthorsOpenReview ↗

Follow Up Response to Reviewer ygcs

Thank you for your response and your additional suggestion. We have updated Remark 4.1 to also include the explanation that Theorem 3.5(ii) gives an O(log⁡(T+1)/T)O(\log(T+1)/\sqrt{T}) expected last-iterate bound under our conditional ABC assumptions with deterministic initialization.

Regarding the minor typos and reference errors, we carefully reread the original review but could not identify any specific instances mentioned there. We have nevertheless proofread the revised manuscript and rebuttal again (and corrected a few typos on our end). If you have any particular locations in mind, we would greatly appreciate the additional pointers and will address them promptly.

Reviewer_5X9dOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies last-iterate convergence of SGD for smooth convex optimization, under the ABC condition for the stochastic gradients. There are two main results. First the paper shows a step size schedule αt=(t+1)−2/3\alpha_t = (t+1)^{-2/3}, the last iterate converges a minimizer at asymptotic rate t−qt^{-q} almost surely, for any a<1/3a<1/3. Second, the paper shows a lower bound: For any exponent r>1/3r>1/3, there exists a setting where (t+1)rf(xt)→∞(t+1)^rf(x_t) \to \infty for any fixed step size schedule. A final result is a convergence rate for exponent 1/31/3 with extra log factors. To prove the lower bound, the paper separates stepsize schedules into cases according to how frequently sufficiently large steps occur. If they occur often enough, the authors construct a noise distribution whose shocks disrupt the proposed convergence rate infinitely often. Otherwise, they show that the cumulative step sizes are too small to achieve that the rate, even without noise.

Critical strengths
  • The paper provides an almost complete characterization for the last-iterate convergence rate of fixed step size schedules (except the case when the exponent is exactly 1/3). I think the most interesting result is the lowerbound. The counterexample is also simple, even in 1 dimension.

After rebuttal: The case 1/3 has also been included with a counter example.

Critical weaknesses
  • I think the main weakness of this paper is the exact boundary. Even though the authors provide a bound for q=1/3, it's unclear whether this rate is achievable.

After rebuttal: this is addressed.

Questions for authors
  • Is it possible to show nonasymptotic rate in Theorem 2.1?
  • Apart from the model and assumption, can the authors provide a more detailed comparison with Lei, Shi, and Guo (2018) in terms of techniques to achieve the upperbound.
3 comments
AuthorsOpenReview ↗

Response to Reviewer 5X9d

  1. Thank you for the careful feedback and for drawing attention to the exact cube-root rate. We were able to resolve your endpoint question under the full conditional ABC assumptions. For every positive deterministic schedule, the new Proposition 2.3 gives a one-dimensional example in which the rescaled error t1/3(f(xt)−f∗)t^{1/3}(f(x_t)-f^*) is unbounded almost surely. The proof follows from the techniques developed previously in the paper. In particular, we use recurrent noise shocks when the steps are large enough for those shocks to disrupt the rate, and a flat objective when the cumulative steps are too small for sufficient progress. The high level explanation of the construction is given in the new Section 3.3 and Appendix E gives the fully detailed proof.

The independent shocks in our endpoint construction have mean zero and variance one at every iteration, although their distributions can change over time. The conditional ABC assumption bounds the conditional second moment at each step and permits this variation, so Proposition 2.3 settles your endpoint question for the full class studied in the paper. The technical caveat concerns the narrower class of fixed i.i.d. oracles with finite variance. It remains open whether a single deterministic schedule can guarantee an almost-sure O(t−1/3)O(t^{-1/3}) last-iterate rate for every such oracle. A related open question is whether the slowly varying factor in Proposition 2.5 is optimal.

  1. You asked whether Theorem 2.1 has a nonasymptotic version of the result. For the critical schedule αt=(t+1)−2/3\alpha_t=(t+1)^{-2/3}, we use the two recursions from our almost-sure analysis to derive an explicit finite-time bound on the expected error of the last iterate. Under the same conditional ABC assumptions, we show in Section 4.2 that E[f(xT)−f∗]≤KT−1/3\mathbb{E}[f(x_T)-f^*]\le K T^{-1/3} for every integer T≥1T\ge1. Thus, to achieve expected error at most ε\varepsilon, it suffices to run this schedule for T≥(K/ε)3T\ge(K/\varepsilon)^3 iterations. Proposition B.2 in Appendix B.3 gives KK explicitly and derives the corresponding confidence bound at each fixed horizon.

  2. Finally, you also asked how our proof compares with that of Lei, Shi, and Guo (2018). Both analyses start from bounds on the objective error and the squared distance to a minimizer. They first use martingale concentration to obtain high-probability bounds and then apply Borel--Cantelli to derive almost-sure rates. We combine the two recursions into a weighted potential and use Robbins--Siegmund and summability to derive the almost-sure rate directly. We have added this comparison at the beginning of Section 3.

In the revised paper, all edits and additions appear in blue.

Thank you for your response. My concerns have been well addressed. I will increase the score.

AuthorsOpenReview ↗

Follow Up Response to Reviewer 5X9d

Thank you for your thoughtful review and constructive feedback once more. We are glad that our responses have addressed your concerns, and we appreciate your reconsideration of the score.

Reviewer_NXzROpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

In this paper, the authors provide an asymptotic analysis of the last-iterate convergence of SGD. The main result is the cube-root barrier: a polynomial convergence rate arbitrarily close to t−1/3t^{-1/3} is achievable almost surely, while no deterministic step-size schedule can guarantee an almost-sure polynomial convergence rate with an exponent strictly greater than 1/31/3 uniformly over the considered class of problems. The authors establish both negative results (Theorem 2.2) and corresponding upper bounds on the convergence rate (Theorem 2.1 and Proposition 2.4).

Critical strengths

I can highlight following advantages:

  1. In my opinion, the strongest contribution is the matching upper and lower bounds for the almost-sure last-iterate convergence rate. In particular, the lower bound applies to arbitrary deterministic positive stepsize schedules, rather than only standard polynomial schedules. This makes the cube-root barrier a meaningful limitation of the considered SGD setting.

  2. As for me, proof techniques are interesting and may be useful. The upper-bound argument converts stochastic descent inequalities into an almost-sure rate through a carefully weighted potential and a summability argument. The lower bound is particularly compelling: it separates regimes in which occasional stochastic shocks prevent fast convergence from regimes in which stepsizes are too small to make sufficient progress on a flat objective.

Critical weaknesses

I would like to mention the following weakness:

  1. The results are entirely asymptotic. The guarantees concern almost-sure limits and limsups as t→∞t\to\infty. The paper does not provide explicit finite-time last-iterate bounds, confidence-dependent guarantees, or estimates of the iteration complexity required to reach a given accuracy. Consequently, the results establish a sharp theoretical rate barrier but offer limited guidance about finite-horizon SGD performance. Additionally, it remains unclear whether the cube root barrier persists when considering convergence in expectation or with high probability instead of almost-sure convergence.

Additionally, I would like to highlight two papers in the literature that, in my opinion, could further strengthen the authors' contribution. In [1], the authors analyzed the last-iterate convergence of SGD in expectation and obtained a rate O(T−1/3)O(T^{-1/3}) for the stochastic term without employing any averaging scheme. In [2], the authors provided a high-probability convergence analysis for the last iterate of Clip-SGD and also obtained a rate O(T−1/3)O(T^{-1/3}) under the finite-variance assumption. These results may suggest that, in the absence of averaging schemes (such as Polyak-Ruppert or primal averaging), the cube root barrier can be fundamentally unavoidable for SGD.


References

[1] A. Taylor, F. Bach (2019). Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions

[2] Chezhegov et al. (2026). High-Probability Bounds for the Last Iterate of Clipped SGD

Questions for authors
  1. Do you think the barrier could improve from t−1/3t^{-1/3} to t−1/2t^{-1/2} if some form of iterate averaging (as in [1]) were incorporated into SGD? To the best of my knowledge, in [1], the use of Polyak-Ruppert averaging and primal averaging led to the improved convergence bound O(t−1/2)O(t^{-1/2}).
1 comment
AuthorsOpenReview ↗

Response to Reviewer NXzR

  1. Thank you for your careful review and your positive assessment of the strengths of the paper. We agree with your assessment that the absence of a finite-time guarantee was a weakness of our original submission. To address this point, we added Section 4.2, where we use the two recursions from our almost-sure convergence analysis to derive an explicit bound on the expected error of the last iterate after a fixed number of steps. For the critical schedule αt=(t+1)−2/3\alpha_t=(t+1)^{-2/3} used in Theorem 2.1, Proposition B.2 shows that E[f(xT)−f∗]≤KT−1/3\mathbb{E}[f(x_T)-f^*]\le K T^{-1/3} for every integer T≥1T\ge1 under the same conditional ABC assumptions. Appendix B.3 gives KK explicitly, so for any target accuracy ε>0\varepsilon>0, running SGD for T≥(K/ε)3T\ge(K/\varepsilon)^3 iterations guarantees expected error at most ε\varepsilon. At any prescribed horizon TT, Markov's inequality bounds the error of the last iterate by KδT1/3\frac{K}{\delta T^{1/3}} with probability at least 1−δ1-\delta. Choosing T≥(Kδε)3T \ge \left(\frac{K}{\delta\varepsilon}\right)^3 makes this bound at most ε\varepsilon.

  2. Thank you for suggesting these references. We now discuss both in the introduction. Under uniformly bounded noise variance, Taylor and Bach (2019) analyze the last iterate of SGD in expectation, and Chezhegov et al. (2026) analyze the last iterate of clipped SGD with high probability. As you mentioned, both analyses give cube-root upper bounds up to logarithmic factors. These bounds leave open what other stepsize schedules might achieve. Our lower bound resolves that question for almost-sure convergence under conditional ABC by showing that no positive deterministic schedule can guarantee a faster polynomial rate for every admissible instance. We make this distinction clearer in the paper now.

  3. As for your question about whether the barrier persists in expectation or with high probability, faster rates are possible at a prescribed horizon even for the unaveraged last iterate. As we explain in Remark 4.1, with deterministic initialization our conditional ABC assumptions imply the growth condition used by Vaidyan et al. (2026). Their horizon-dependent schedule gives an O(T−1/2)O(T^{-1/2}) expected last-iterate error. Applying Markov's inequality yields an O(δ−1T−1/2)O(\delta^{-1}T^{-1/2}) error bound with probability at least 1−δ1-\delta at that same horizon.

  4. As for your question about averaging, our cube-root barrier concerns the last iterate xTx_T. Returning the arithmetic mean x‾T=T−1∑t=0T−1xt\overline{x}_T = T^{-1}\sum_{t=0}^{T-1} x_t allows almost-sure rates arbitrarily close to T−1/2T^{-1/2} under the same conditional ABC assumptions. Immediately after Lemma A.8, we now use its summability bound and convexity to show that, for each 0<γ<1/20 < \gamma < 1/2, choosing αt=(t+1)−1/2−γ\alpha_t = (t+1)^{-1/2-\gamma} gives f(x‾T)−f∗=o(T−1/2+γ)f(\overline{x}_T) - f^{\ast} = o(T^{-1/2+\gamma}) almost surely. The averaging bounds you cite from Taylor and Bach (2019) concern convergence in expectation, with logarithmic factors omitted in their Table 2.

In the revised paper, all edits and additions appear in blue.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.