- 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 , 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
-
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 for all admissible instances.
-
The critical schedule does not depend on the target exponent and attains every subcritical almost-sure last-iterate rate.
Critical weaknesses
-
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 under conditional sub-Gaussian noise assumptions.
-
Corollary 2.3 characterizes the supremal convergence exponent for polynomially decaying stepsizes, but does not clarify whether the endpoint is admissible under the conditional ABC condition when , which remains to be addressed.
-
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
-
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.
-
Is the endpoint admissible under the conditional ABC condition when ?
-
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 ? If so, can these guarantees match the best known rates in the literature under comparable assumptions?
5 comments
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.
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 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.
Response to Reviewer ygcs
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 for all horizons and confidence levels. In Appendix F we apply Borel--Cantelli to their bound to obtain f(xT)−f∗=o(T−q) almost surely for every 0<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.
On your question about q=2p−1, we can now show that the strict inequality in Theorem 2.1 is necessary throughout 1/2<p≤2/3. Proposition E.1 extends our shock argument to give a one-dimensional quadratic on which t2p−1(f(xt)−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/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/3. Whether one schedule guarantees the exact cube-root rate for every fixed i.i.d. finite-variance oracle remains open.
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, Section 4.2 shows that E[f(xT)−f∗]≤KT−1/3 for every integer T≥1 under the same conditional ABC assumptions. Thus T≥(K/ε)3 iterations suffice for expected error at most ε. Appendix B.3 gives K 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) expected last-iterate bound by choosing their stepsizes for the prescribed horizon T. Remark 4.1 shows that their result applies under our conditional ABC assumptions when the initialization is deterministic.
In the revised paper, all edits and additions appear in blue.