REVIEW 2 major objections 5 minor 1 cited by
Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems
T0 review · 2 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read SGD's last iterate reaches O(ln T/√T) for convex smooth problems, with no uniform variance assumption.
desk verdict Solid last-iterate result that settles an open question; printed proof has a fixable sign-error in Lemma 4.3, so the paper deserves peer review after a minor correction. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The engine is a variance-transfer inequality: because the gradients ∇f_i are L-Lipschitz and the f_i are convex, E[‖∇f_i(x)‖²] ≤ 2L(1+ε)(f(x)-inf f) + (1+1/ε) σ_*² for every ε>0. This replaces a global uniform variance bound by the single constant σ_*² plus a function-gap term, which is exactly the quantity being bounded. The proof then feeds this inequality into a weighted telescoping lemma that converts pointwise descent inequalities into a last-iterate bound: it chooses convex weights α_t, telescopes the squared-distance terms in the SGD recursion, and isolates f(x_T)-inf f. The parameter ε is tuned as (1-γL)/(1+γL), making the coefficient of the function gap positive exactly when γL<1.
What would settle it
Run SGD with γ = 1/(2L√T) on any convex, L-smooth finite-sum or expectation problem satisfying σ_*² < ∞ and measure E[f(x_T)-inf f] over many seeds; if for some such problem the decay is slower than C ln(T)/√T for all constants C, the bound is false. A more targeted falsifier is an explicit, convex, L-smooth, non-interpolating example where σ_*² is finite but the last-iterate gap provably violates the stated upper bound, or a performance-estimation computation of the worst-case last-iterate gap exceeding the theorem's constant.
Extended reading notes
Core claim
The paper's central claim is that for a convex and L-smooth expected-risk problem with nonempty minimizer set, SGD's last iterate converges at the same near-optimal rate as its averaged iterates. If x* is a minimizer and σ_*² = E[‖∇f_i(x*)‖²] < ∞, then for any fixed horizon T ≥ 3 and step size with γL ∈ (0,1), E[f(x_T)-inf f] ≤ T^φ [2D²/(γ(1-γL)T) + 8γ ln(T+1) σ_*²/(1-γL)²], with φ = 2γL/(1+γL) and D² = E[‖x0-x*‖²]. Choosing γ proportional to 1/(L√T) makes T^φ a constant and yields E[f(x_T)-inf f] = O(ln T/√T). The only noise information needed is the variance at a minimizer; no uniform bound on the variance or norm of the stochastic gradients over the whole space is assumed. The paper presents these as the first such bounds while acknowledging a concurrent independent result with similar conclusions.
Load-bearing premise
The whole proof is carried by the assumption that σ_*², the expected squared norm of the stochastic gradient at some minimizer, is finite — if that single-point variance is infinite, the stated bound is vacuous — and by the step-size restriction γL < 1, so the endpoint γL = 1, which a concurrent work covers, is outside the theorem.
Editorial extensions
If this is right
- With step size γ = 1/(C L √T), C ≥ 2, the explicit corollary gives E[f(x_T)-inf f] ≤ 9 C L D²/√T + 67 ln(T+1) σ_*²/(C L √T), matching the classical ergodic SGD rate up to a logarithm.
- For any polynomial step size γ = 1/(C L T^β), β ∈ (0,1), the bound is O(D²/T^{1-β} + ln T σ_*²/T^β); β = 1/2 is the best exponent in this family.
- The same framework extends to mini-batch SGD, because minibatch sampling is SGD on a modified problem whose smoothness constant and σ_*² are explicit functions of batch size.
- A consequence is an iterate-complexity guarantee: E[f(x_T)-inf f] ≤ ε once T is of order (K/ε)^β for any β > 2, ignoring logarithms.
- The bound is adaptive to the noise constant σ_*² in the sense that the algorithm need not know it to obtain the stated rate.
Reading between the lines
- A natural next test is whether the logarithmic factor is removable: by analogy with the convex Lipschitz case, a nonstandard step-size schedule might give the exact O(1/√T) last-iterate rate; the paper leaves this as a conjecture.
- The bound is not interpolation-adaptive: when σ_*² = 0 it remains O(1/√T) rather than O(1/T), so an open extension is a step-size rule that automatically switches to the fast rate when interpolation holds, using only quantities the algorithm can estimate.
- It would be worth testing whether existing adaptive step-size rules inherit last-iterate guarantees under the same single-point variance condition; the paper notes this as an open direction.
- A high-probability version of the last-iterate guarantee without uniform noise bounds does not follow from the expectation analysis and is not claimed by the paper; that is a concrete open problem.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies constant-step-size SGD for minimizing f(x)=E[f_i(x)] where each f_i is convex and L-smooth. The main result (Theorem 3.1) states that, under Assumptions 2.1 and 2.2, E[f(x_T)-inf f] ≤ T^φ [2D^2/(γ(1-γL)T) + 8γ ln(T+1)/(1-γL)^2 σ_*^2], where φ=2γL/(1+γL) and γL∈(0,1); with γ≍1/√T this yields O(ln T/√T) last-iterate complexity. The proof combines a variance-transfer inequality at a minimizer (Lemma 4.1), a one-step recursion (Lemma 4.2), and a weighted telescoping argument (Lemma 4.3) adapted from Zamani-Glineur and Liu-Zhou. The paper also derives corollaries for polynomial step sizes and sample complexity, and acknowledges the concurrent work of Attia et al.
Significance. If the proof is made formally correct, this is a significant result: it removes the uniform gradient/variance assumption that previous last-iterate SGD bounds relied on and reduces the noise condition to finiteness of E||∇f_i(x*)||^2 at a minimizer. The paper proves its key technical lemmas in the text, gives explicit constants, and honestly describes the relation to parallel work; self-citations are used only for standard background inequalities. The O(ln T/√T) rate matches known ergodic rates up to a logarithm, and the authors correctly flag whether the logarithm is removable as open.
major comments (2)
- [Lemma 4.3 (Section 4.2)] The stated hypothesis -a < b ≤ 0 is incompatible with the application in Theorem 3.1. There a=(1-γL)/(1+γL)∈(0,1) and b=-1, so -a∈(-1,0) and the inequality -a < b becomes -a < -1, equivalently a>1, which is false for every γL∈(0,1). The proof's own construction p_t = α_{t-1}/α_t = (T-t+1+a/b)/(T-t+1) requires p_t∈[0,1]; with b<0 and a>0 this holds when 2+a/b>0, i.e. for b=-1 when 0<a<2. Thus the printed hypothesis describes the wrong side of the boundary and Lemma 4.3 cannot be invoked as stated. The algebra in the proof goes through under the corrected hypothesis b<0<a and 2+a/b>0; the authors should restate the lemma accordingly and re-verify the recurrence for α_t in that regime.
- [Lemma 4.3 and Lemma A.3 (Sections 4.2 and A)] The index ranges in the telescoping argument need to be harmonized. Lemma 4.3 defines α_t for t=1,...,T-1 via the recurrence, while the proof later sets α_T=α_{T-1} and sums the weighted inequality from 0 to T; Lemma A.3, invoked in Theorem 3.1, defines α_t for t=0,...,T with a recurrence that includes t=0. The identity α_T/α_{T-1}=1, which is used to obtain 4T^φ ln(T+1) from Lemma A.1, is not stated as part of the lemmas. Please specify the recurrence for α_0 and α_T and the exact summation range used to derive the final bound in Lemma 4.3.
minor comments (5)
- [Lemma 4.3 (Section 4.2)] The phrase 'for all zt ∈ H contained in F (x0, . . . , xt)' should be replaced by a clear measurability condition, e.g. 'for every z_t that is F(x0,...,xt)-measurable'.
- [Corollary 3.5] The sentence 'we take γ = 1/(2L√T), for some , and T (1+ln(T+1))^2 ≥ K^2/ε^2' contains a missing placeholder; it should read 'for some T' or similar.
- [Lemma A.3] The second displayed inequality is written with a parameter θ that appears to be a typo for φ; additionally, the definition 'for t=0,...,T' conflicts with the recurrence range in Lemma 4.3.
- [Theorem 3.1] The constant D^2 is not explicitly defined as an infimum over minimizers; since σ_*^2 is defined via an infimum, the bound should clarify that it holds for any x*∈argmin f with D^2=E||x0-x*||^2, or that D^2 is taken as the infimum over minimizers.
- [Proof of Lemma 4.2] The statement that z_t is 'independent from x_t' is imprecise; what is used is that z_t is measurable with respect to F(x0,...,xt), so that the conditional expectation E_t[⟨∇f_i(x_t), z_t⟩] = ⟨E_t[∇f_i(x_t)], z_t⟩ is valid.
Circularity Check
No circularity: the central bound is derived in-text from variance-transfer and weighting lemmas; self-citations are background only. The printed Lemma 4.3 has a hypothesis mismatch with Theorem 3.1, but that is a proof-gap, not circularity.
full rationale
The claimed last-iterate rate is not an input to any definition or fit. Lemma 4.1 (variance transfer) is proved in the text from a Fenchel-Young inequality plus the standard cocoercivity inequality; the citation to (Garrigos and Gower, 2024) is to a handbook sharing an author, but the lemma is restated with a self-contained proof sketch, so the self-citation is not load-bearing. Lemma 4.2 is pure algebra from Lemma 4.1. Lemma 4.3 is the Zamani-Glineur weighting technique, reproduced with a full proof in the text rather than imported by citation; its use of Jensen with b <= 0 and telescoping does not assume the theorem's conclusion. Lemma A.3 (Gamma-function bounds) is proved via Gautschi's inequality, with the sum-integral comparison standard. No parameter is fitted to data and sigma_*^2 is a problem constant, not a fitted quantity renamed as a prediction. The concurrent-work note (Attia et al., 2025) only affects novelty, not circularity. The one notable defect is formal rather than circular: Lemma 4.3 states the hypothesis -a < b <= 0, while Theorem 3.1 applies it with b = -1 and a = (1 - gamma L)/(1 + gamma L) in (0,1), for which -a < b is false; the subsequent alpha_t recurrence is consistent with the actual regime (a/b in (-1,0)), so the central claim appears correct but the printed lemma needs its hypothesis corrected before it can be invoked. Because no derivation step reduces to its own input by construction, the circularity score is 0.
Assumptions & free parameters
free parameters (1)
- step-size gamma =
gamma = 1/(C L T^beta), beta in (0,1), C >= 2
assumptions (4)
- domain assumption Assumption 2.1: each f_i is convex and L-smooth, argmin f is nonempty, and sampling is well-defined.
- domain assumption Assumption 2.2 (GV*): E[||grad f_i(x*)||^2] < infinity for some (equivalently every) minimizer x* of f, with sigma_*^2 = inf over minimizers.
- standard math Standard convex analysis tools: descent lemma for L-smooth functions, Jensen's inequality, Fenchel-Young, and Gautschi's inequality for the Gamma function.
- domain assumption Step-size restriction gamma L in (0,1) for the generic theorem.
Cite this review
Pith. "Pith review of Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems." pith.science (2026). https://pith.science/paper/R2H5UL7O
@misc{pith2026250714122,
author = {Pith},
title = {Pith review of: Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems},
year = {2026},
howpublished = {\url{https://pith.science/paper/R2H5UL7O}},
note = {Machine review of arXiv:2507.14122}
}
abstract
Most results on Stochastic Gradient Descent (SGD) in the convex and smooth setting are presented under the form of bounds on the ergodic function value gap. It is an open question whether bounds can be derived directly on the last iterate of SGD in this context. Recent advances suggest that it should be possible. For instance, it can be achieved by making the additional, yet unverifiable, assumption that the variance of the stochastic gradients is uniformly bounded. In this paper, we show that there is no need of such an assumption, and that SGD enjoys a $\tilde O \left( T^{-1/2} \right)$ last-iterate complexity rate for convex smooth stochastic problems.
Forward citations
Cited by 1 Pith paper
-
Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
The last SGD iterate converges at near-optimal rates in the smooth convex interpolation regime, including O(1/sqrt(T)) with the greedy step size eta=1/beta for general convex smooth losses.
Reference graph
Works this paper leans on
-
[1]
Alacaoglu, A., Malitsky, Y., and Wright, S. J. (2025). Towards Weaker Variance Assumptions for Stochastic Optimization . arXiv preprint arXiv:2504.09951
arXiv 2025
-
[2]
Attia, A., Schliserman, M., Sherman, U., and Koren, T. (2025). Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime . arXiv preprint arXiv:2507.11274
arXiv 2025
-
[3]
Bach, F. and Moulines, E. (2011). Non- Asymptotic Analysis of Stochastic Approximation Algorithms for Machine Learning . In Advances in Neural Information Processing Systems , volume 24. Curran Associates, Inc
work page 2011
-
[4]
Blum, J. R. (1954). Approximation Methods which Converge with Probability one. The Annals of Mathematical Statistics , 25(2):382--386
work page 1954
-
[5]
Bottou, L., Curtis, F. E., and Nocedal, J. (2018). Optimization Methods for Large - Scale Machine Learning . SIAM Review , 60(2):223--311
work page 2018
-
[6]
Cortild, D., Ketels, L., Peypouquet, J., and Garrigos, G. (2025). New Tight Bounds for SGD without Variance Assumption : A Computer - Aided Lyapunov Analysis . arXiv preprint arXiv:2505.17965
arXiv 2025
-
[7]
Garrigos, G. and Gower, R. M. (2024). Handbook of Convergence Theorems for ( Stochastic ) Gradient Methods . arXiv preprint arXiv:2301.11235
arXiv 2024
-
[8]
Gautschi, W. (1959). Some Elementary Inequalities Relating to the Gamma and Incomplete Gamma Function . Journal of Mathematics and Physics , 38(1-4):77--81
work page 1959
Show all 30 references
-
[9]
Gladyshev, E. G. (1965). On Stochastic Approximation . Theory of Probability & Its Applications , 10(2):275--278
1965
-
[10]
Gower, R., Sebbouh, O., and Loizou, N. (2021). SGD for Structured Nonconvex Functions : Learning Rates , Minibatching and Interpolation . In Proceedings of the 24th International Conference on Artificial Intelligence and Statistics , pages 1315--1323. PMLR
2021
-
[11]
M., Garrigos, G., Loizou, N., Oikonomou, D., Mishchenko, K., and Schaipp, F
Gower, R. M., Garrigos, G., Loizou, N., Oikonomou, D., Mishchenko, K., and Schaipp, F. (2025). Analysis of an idealized stochastic Polyak method and its application to black-box model distillation . arXiv preprint arXiv:2504.01898
2025 arXiv
-
[12]
M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., and Richtárik, P
Gower, R. M., Loizou, N., Qian, X., Sailanbayev, A., Shulgin, E., and Richtárik, P. (2019). SGD : General Analysis and Improved Rates . In Proceedings of the 36th International Conference on Machine Learning , pages 5200--5209. PMLR
2019
-
[13]
Harvey, N. J. A., Liaw, C., Plan, Y., and Randhawa, S. (2018). Tight Analyses for Non - Smooth Stochastic Gradient Descent . arXiv preprint arXiv:1812.05217
2018 arXiv
-
[14]
Jain, P., Nagaraj, D., and Netrapalli, P. (2019). Making the Last Iterate of SGD Information Theoretically Optimal . arXiv preprint arXiv:1904.12443
2019 arXiv
-
[15]
Kassing, S., Weissmann, S., and D \"o ring, L. (2025). Controlling the Flow: Stability and Convergence for Stochastic Gradient Descent with Decaying Regularization . arXiv preprint arXiv:2505.11434
2025
-
[16]
and Richtárik, P
Khaled, A. and Richtárik, P. (2023). Better Theory for SGD in the Nonconvex World . Transactions on Machine Learning Research
2023
-
[17]
D., Nguyen, T
Liu, Z., Nguyen, T. D., Nguyen, T. H., Ene, A., and Nguyen, H. (2023). High Probability Convergence of Stochastic Gradient Methods . In Proceedings of the 40th International Conference on Machine Learning . PMLR
2023
-
[18]
and Zhou, Z
Liu, Z. and Zhou, Z. (2023). Revisiting the Last - Iterate Convergence of Stochastic Gradient Methods . In Proceedings of The Twelfth International Conference on Learning Representations
2023
-
[19]
H., and Lacoste-Julien, S
Loizou, N., Vaswani, S., Laradji, I. H., and Lacoste-Julien, S. (2021). Stochastic Polyak Step-size for SGD: An Adaptive Learning Rate for Fast Convergence . In International Conference on Artificial Intelligence and Statistics , pages 1306--1314. PMLR
2021
-
[20]
How do you prove Gautschi's inequality for the gamma function? https://math.stackexchange.com/q/98348
Mathematics Stack Exchange (2017). How do you prove Gautschi's inequality for the gamma function? https://math.stackexchange.com/q/98348
2017
-
[21]
Needell, D., Srebro, N., and Ward, R. (2016). Stochastic gradient descent, weighted sampling, and the randomized Kaczmarz algorithm. Mathematical Programming , 155(1):549--573
2016
-
[22]
Nemirovski, A., Juditsky, A., Lan, G., and Shapiro, A. (2009). Robust Stochastic Approximation Approach to Stochastic Programming . SIAM Journal on Optimization , 19(4):1574--1609
2009
-
[23]
H., Dijk, M., Richtarik, P., Scheinberg, K., and Takac, M
Nguyen, L., Nguyen, P. H., Dijk, M., Richtarik, P., Scheinberg, K., and Takac, M. (2018). SGD and Hogwild ! Convergence Without the Bounded Gradients Assumption . In Proceedings of the 35th International Conference on Machine Learning , pages 3750--3758. PMLR
2018
-
[24]
Orabona, F. (2020). Last Iterate of SGD Converges (Even in Unbounded Domains) . https://parameterfree.com/2020/08/07/last-iterate-of-sgd-converges-even-in-unbounded-domains/
2020
-
[25]
and D'Orazio, R
Orabona, F. and D'Orazio, R. (2025). New Perspectives on the Polyak Stepsize: Surrogate Functions and Negative Results . arXiv preprint arXiv:2505.20219
2025
-
[26]
and Monro, S
Robbins, H. and Monro, S. (1951). A Stochastic Approximation Method . The Annals of Mathematical Statistics , 22(3):400--407
1951
-
[27]
M., and Defazio, A
Sebbouh, O., Gower, R. M., and Defazio, A. (2021). Almost sure convergence rates for stochastic gradient descent and stochastic heavy ball. In Conference on Learning Theory , pages 3935--3971. PMLR
2021
-
[28]
and McMahan, H
Streeter, M. and McMahan, H. B. (2010). Less regret via online conditioning. arXiv preprint arXiv:1002.4862
2010 arXiv
-
[29]
and Bach, F
Taylor, A. and Bach, F. (2019). Stochastic first-order methods: non-asymptotic and computer-aided analyses via potential functions. In Proceedings of the 32nd Conference on Learning Theory , pages 2934--2992. PMLR
2019
-
[30]
and Glineur, F
Zamani, M. and Glineur, F. (2023). Exact convergence rate of the last iterate in subgradient methods. arXiv preprint arXiv:2307.11134
2023 arXiv
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.