Pith. sign in

REVIEW 5 minor 2 cited by

Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime

T0 review · 0 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read SGD's last iterate converges at rate O(1/√T) on smooth convex losses that share a minimizer, the first guarantee at the greedy step size and one that extends to Kaczmarz and continual learning.

desk verdict New last-iterate O(1/sqrt(T)) rate for SGD in the smooth interpolation regime with greedy stepsize; core proofs check out, extensions lean on overlapping-author lemmas. read the letter →

arxiv 2507.11274 v2 pith:632R7P5R submitted 2025-07-15 cs.LG math.OCstat.ML

Amit Attia , Matan Schliserman , Uri Sherman , Tomer Koren This is my paper · ORCID
classification cs.LGmath.OCstat.ML MSC 90C2568W4062L20
keywords last-iterateconvergencestochasticgradientdescentinterpolationregimesmoothconvexoptimizationlow-noiserandomizedKaczmarzcontinuallearningwithout-replacementSGD
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper asks whether the last iterate of stochastic gradient descent—the final model, not an average of iterates—can converge quickly when every sampled loss function shares the same optimum, the interpolation setting that describes over-parameterized models. The authors establish that for smooth convex losses it can: with a constant step size below twice the smoothness constant, the expected excess loss of the last iterate decays as O(1/(η(2−βη)$T^{{1−βη/2}}$)), which at the greedy step size η=1/β is O(1/√T). This is the first such general guarantee, improving on the O($T^{{−1/4}}$) rate previously known only for realizable linear regression. In the low-noise case, the same analysis yields a near-optimal O(1/T+σ⋆/√T) rate for a tuned step size. Because the result also covers step sizes up to the greedy choice and without-replacement sampling, it directly improves guarantees for randomized Kaczmarz and continual learning.

What carries the argument

The argument sharpens the weighted regret framework used for the deterministic subgradient method: it chooses non-decreasing weights v_t=(T−t+2)^{−α} with a final plateau, then replaces the ordinary convexity lower bound with the stronger smoothness lower bound f(y)≥f(x)+⟨∇f(x),y−x⟩+(1/2β)||∇f(y)−∇f(x)||². This smoothness inequality introduces cross terms ||∇f_t(x_t)−∇f_t(x_s)||², which are controlled by a step-dependent Young inequality that assigns a different split parameter to each (t,s) pair. A sampling condition—future samples are identically distributed to the current one conditioned on the past—lets the regret decomposition rewrite expected losses under future functions as losses under the current function, and the weight choice balances the resulting coefficients so that the final iterate, not an average, carries the bound.

What would settle it

Simulate SGD with step size η=1/β on a smooth convex family with a common minimizer, such as f_t(x)=½(x−z_t)² with z_t zero-mean and bounded variance, and measure the expected excess loss E[F(x_T)−F(x⋆)] at T=10³,...,10⁷; if the empirical curve decays slower than C/√T, such as a plateau or a 1/$T^{{1/4}}$ slope, Theorem 1 is false. Alternatively, an adversarial ordering of the same losses that violates the conditional-identical-distribution condition and breaks the claimed rate would pinpoint the sampling assumption as the cause.

Watch

Extended reading notes

Core claim

At the paper's core is a last-iterate convergence theorem for SGD on β-smooth convex losses with a shared minimizer x⋆: for constant step size η<2/β, E[F(x_T)−F(x⋆)] ≤ 3||x1−x⋆||^2/(η(2−βη)$T^{{1−βη/2}}$). Setting η=1/β yields O(1/√T), and η=1/(β log₂T) yields O(log²T/T); a companion theorem in the low-noise regime, where the gradient variance at the optimum is σ⋆², gives O(1/T+σ⋆/√T) after tuning η. The authors also prove the analogous guarantee for without-replacement SGD. These bounds are the first last-iterate rates in this generality, and they cover the greedy step size that prior analyses had to avoid, which is what makes them transfer to randomized Kaczmarz and continual linear regression.

Load-bearing premise

The analysis needs the sampling order to be past-independent in this sense: after conditioning on the samples seen so far, the distribution of the next sample and of any later sample is the same, which holds for i.i.d. draws and random permutations but not for adversarial or fixed orderings.

Editorial extensions

If this is right

  • At step size η=1/β, the last iterate of SGD on any smooth convex realizable objective converges at O(1/√T), so greedy updates are no longer out of reach of the theory.
  • With a tuned step size, the last-iterate rate O(1/T+σ⋆/√T) matches the average-iterate rate up to logarithmic factors, meaning practitioners need not average iterates to get fast convergence.
  • Without-replacement SGD achieves O(1/√T) at η=1/β and O((log T)/T) with smaller steps in the interpolation regime.
  • Randomized block Kaczmarz and continual linear regression inherit bounds of O(R²||x⋆||²/√T) at c=1, independent of the condition number of the data matrix.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The O(1/√T) rate at η=1/β is likely not final: the paper itself notes that the best known lower bound is Ω(1/T), so a tighter analysis might push the greedy-step rate closer to 1/T.
  • The key sampling condition is an indistinguishability property rather than a Markov property, suggesting the theorem should extend to any ordering—cyclic, reshuffled, or otherwise—whose conditional future marginals match the current one.
  • A testable extension is to probe the transition at small σ⋆: the low-noise bound predicts a graceful interpolation between 1/T and 1/√T as the noise at the optimum increases, a prediction that could be checked numerically on quadratic losses.
  • The smoothness-based regret technique is not tied to Euclidean SGD, so similar last-iterate rates may transfer to projected or mirror-descent variants in the interpolation regime.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

0 major / 5 minor

Summary. The paper studies fixed-stepsize SGD for beta-smooth convex stochastic optimization when the component losses share a common minimizer (the interpolation regime) or have small gradient variance at the optimum (the low-noise regime). Its main results are: Theorem 1, which gives a last-iterate excess-risk bound of order O(1/(eta(2-beta*eta) T^{1-beta*eta/2})) in interpolation, and in particular O(1/sqrt(T)) at the greedy step size eta=1/beta; Theorem 2, which extends the analysis to nonzero sigma_star and yields, for a suitably tuned step size, a near-optimal O(1/T + sigma_star/sqrt(T)) rate; and Theorem 3, which adapts the argument to without-replacement SGD. The paper also derives consequences for randomized block Kaczmarz, continual linear regression, continual classification, and projection onto convex sets. The proofs of Theorems 1 and 2 are self-contained and build on a weighted regret decomposition in the style of Zamani and Glineur, combined with a newly introduced step-dependent Young inequality to handle cross terms.

Significance. If correct, the paper closes a real gap in the last-iterate SGD literature: it gives the first general convex-smooth last-iterate guarantee at the greedy step size eta=1/beta, improving the earlier O(T^{-1/4}) bound of Evron et al. (2025) for realizable linear regression to O(1/sqrt(T)), and it provides a near-optimal low-noise rate that goes beyond least squares. The core derivations are transparent, and the algebra in the central steps of Theorem 1 (in particular the transition to Eq. (9) with alpha=(2-beta*eta)/4) and of Theorem 2 is internally consistent. The extensions to Kaczmarz, continual learning, and POCS are useful and are obtained by clean reductions. The paper is also honest about the remaining gap at the greedy step size, noting that the lower bound is only Omega(1/T). The main weakness is that the without-replacement result imports a stability lemma from a companion preprint, which is a local but real dependency that should be made precise in the final version.

minor comments (5)
  1. [Appendix F, Lemma 7] Lemma 7 is stated as a direct import from Evron et al. (2025), with only the remark that it is 'a minor adjustment of the original one.' Since Theorem 3 and Corollaries 5-7 rely on this lemma, please provide the exact lemma statement in the form used here and either a proof or a precise pointer to the specific proof line in Evron et al. (2025).
  2. [Theorem 2, second 'In particular'] The tuned step size eta = min{1/(beta log2 T), ||x1-x*|| / sqrt(sigma_star^2 T log2(T+2))} is undefined when sigma_star = 0, which is allowed by the theorem's assumptions. Please state the tuning for sigma_star > 0 and handle sigma_star = 0 by a separate reference to Theorem 1, or otherwise clarify the convention used.
  3. [Appendix F, proof of Theorem 3] The displayed decomposition of E[F_Z(x_T)-F_Z(x*)] into an average over the first T-1 elements and a term for pi_T uses the fact that, conditional on pi_1,...,pi_{T-1}, all remaining positions are identically distributed. This is true but is not spelled out; please add a sentence explaining this marginal-distribution argument, since it is essential for the identity.
  4. [Abstract vs. Theorem 2] The abstract states the low-noise bound as O~(... + eta/(2-beta*eta)^2 T^{beta*eta/2} sigma_star^2), while Theorem 2 contains an additional log^2(T+2) factor and different constants. The log factor is presumably absorbed by the O~ notation in the abstract, but the two displays should be explicitly reconciled for the reader.
  5. [Corollary 4 and Corollary 5] The dependence on the step-size parameter c in Corollary 4 is written as T^{1-c beta/2}, but the loss functions in Lemma 8 have smoothness 1 rather than beta; please check that the stated beta in the exponent is intentional and consistent with the proof in Appendix G.

Circularity Check

1 steps flagged · score 2.0 of 10

Central Theorems 1–2 are self-contained; a mild self-citation supports the without-replacement extension.

  1. self citation load bearing [Section 3.1, proof of Theorem 3 (Appendix F.1), Lemmas 6–7]
    "To prove Theorem 3, we first establish a bound on E[f_T(x_T)−f_T(x⋆)] as in the with-replacement case. We then apply the without-replacement algorithmic stability for smooth and realizable objectives provided by Evron et al. (2025). ... We note that the above statement is a minor adjustment of the original one, and follows from the last line of the proof given by Evron et al. (2025)."

    The paper’s without-replacement result is presented as a contribution, but the decisive step bounding E[F_Z(x_T)−F_Z(x⋆)] is not proved here. Lemma 7 is imported from Evron et al. (2025), a paper sharing three authors with the present one, and is only described as a ‘minor adjustment’ of that prior lemma. Without this self-cited stability bound, Theorem 3 does not go through. The cited lemma is not a fitted parameter and is a genuine mathematical statement, so the circularity is mild and confined to this extension; it does not infect Theorem 1 or Theorem 2.

full rationale

The core derivation chain for Theorem 1 (Lemma 1, Lemma 2, step-dependent Young’s-inequality algebra, Eq. (9), final rate with α=(2−βη)/4) is self-contained and does not use any fitted quantity or self-citation. Theorem 2 follows the same argument with a controlled Young’s gap and σ⋆ entering as a definition, not a fitted parameter. The only load-bearing self-citation appears in the without-replacement extension (Theorem 3) and the downstream corollaries, which import stability and reduction lemmas from Evron et al. (2025), a paper with overlapping authorship. Those imported lemmas are not proven in this manuscript and are explicitly described as ‘a minor adjustment’ of the prior work, so the extension carries a mild self-citation dependence. However, the main population last-iterate rates, including the greedy-stepsize O(1/√T) improvement, are derived from first principles in the present paper. The score is therefore 2 rather than 0.

Assumptions & free parameters 0 free parameters · 5 assumptions · 0 invented entities

The core theorems are parameter-free derivations from standard smooth convex assumptions; no free parameters are fitted, and no new entities are postulated. The extensions import stability and reduction lemmas from Evron et al. (2025), an overlapping-author work, which is the only mild external dependence.

assumptions (5)
  • domain assumption f(.;z) is beta-smooth and convex for every z in Z.
    Assumed in Theorem 1 and 2 statements and used throughout the proofs for the smoothness and convexity inequalities.
  • domain assumption There exists x_star minimizing f(.;z) for all z in the interpolation regime (Theorem 1), or minimizing F with sigma_star^2 < infinity in the low-noise regime (Theorem 2).
    Defines the interpolation and low-noise regimes; needed for the variance definition and for the key inequality E||grad f_t(x_t)||^2 <= 2 beta E[F(x_t)-F(x_star)].
  • domain assumption Sampling satisfies: for s <= t, conditioned on z1,...,z_{s-1}, z_s and z_t are identically distributed (Lemma 1).
    Load-bearing for the regret decomposition; holds for i.i.d. and random permutation sampling but not for arbitrary orderings.
  • standard math Standard convex analysis facts: for a convex beta-smooth function h, ||grad h(x) - grad h(y)||^2 <= beta <grad h(x)-grad h(y), x-y> and ||grad h(x)||^2 <= 2 beta (h(x)-h(x_star)) when x_star is a minimizer.
    Used in Eqs. (8), (12), and in the proofs of Lemma 1 and Theorem 1.
  • standard math Technical integral and Bernoulli-inequality estimates in Lemmas 11 and 12 bounding sums of powers.
    Used to bound weight sums a_t and the variance term in Theorem 2.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime." pith.science (2026). https://pith.science/paper/632R7P5R

@misc{pith2026250711274,
  author       = {Pith},
  title        = {Pith review of: Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/632R7P5R}},
  note         = {Machine review of arXiv:2507.11274}
}
abstract

We study population convergence guarantees of stochastic gradient descent (SGD) for smooth convex objectives in the interpolation regime, where the noise at optimum is zero or near zero. The behavior of the last iterate of SGD in this setting -- particularly with large (constant) stepsizes -- has received growing attention in recent years due to implications for the training of over-parameterized models, as well as to analyzing forgetting in continual learning and to understanding the convergence of the randomized Kaczmarz method for solving linear systems. We establish that after $T$ steps of SGD on $\beta$-smooth convex loss functions with stepsize $0 < \eta < 2/\beta$, the last iterate exhibits expected excess risk $\widetilde{O}(\frac{1}{\eta (2-\beta \eta) T^{1-\beta\eta/2}} + \frac{\eta}{(2-\beta\eta)^2} T^{\beta\eta/2} \sigma_\star^2)$, where $\sigma_\star^2$ denotes the variance of the stochastic gradients at the optimum. In particular, for a well-tuned stepsize we obtain a near optimal $\widetilde{O}(1/T + \sigma_\star/\sqrt{T})$ rate for the last iterate, extending the results of Varre et al. (2021) beyond least squares regression; and when $\sigma_\star=0$ we obtain a rate of $\smash{O(1/\sqrt T)}$ with $\eta=1/\beta$, improving upon the best-known $\smash{O(T^{-1/4})}$ rate recently established by Evron et al. (2025) in the special case of realizable linear regression.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Flat Minima and Generalization: Insights from Stochastic Convex Optimization

    cs.LG 2025-11 conditional novelty 7.0 of 10

    In smooth stochastic convex optimization, flat empirical minima can incur constant population risk while sharp minima generalize optimally, and sharpness-aware algorithms can converge to such bad flat minima.

  2. Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems

    math.OC 2025-07 conditional novelty 6.0 of 10

    SGD's last iterate reaches an O(log T / sqrt(T)) expected optimality gap for convex smooth stochastic problems under only convexity, smoothness, and finite gradient variance at a minimizer.

Reference graph

Works this paper leans on

61 extracted references · 54 canonical work pages · cited by 2 Pith papers

  1. [1]

    Attia, M

    A. Attia, M. Schliserman, U. Sherman, and T. Koren. Fast last-iterate convergence of sgd in the smooth interpolation regime. arXiv preprint arXiv:2507.11274, 2025

    arXiv 2025

  2. [2]

    Bach and E

    F. Bach and E. Moulines. Non-strongly-convex smooth stochastic approximation with convergence rate O (1/n) . Advances in neural information processing systems, 26, 2013

    work page 2013

  3. [3]

    Berthier, F

    R. Berthier, F. Bach, and P. Gaillard. Tight nonparametric convergence rates for stochastic gradient descent under the noiseless linear model. Advances in Neural Information Processing Systems, 33: 0 2576--2586, 2020

    work page 2020

  4. [4]

    L. Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In Proceedings of the symposium on learning and data science, Paris, volume 8, pages 2624--2633. Citeseer, 2009

    work page 2009

  5. [5]

    S. Boyd, J. Dattorro, et al. Alternating projections. EE392o, Stanford University, 2003

    work page 2003

  6. [6]

    Cai and J

    X. Cai and J. Diakonikolas. Last iterate convergence of incremental methods and applications in continual learning. In The Thirteenth International Conference on Learning Representations, 2025

    work page 2025

  7. [7]

    X. Cai, C. Y. Lin, and J. Diakonikolas. Empirical risk minimization with shuffled sgd: a primal-dual perspective and improved bounds. arXiv preprint arXiv:2306.12498, 2023

    arXiv 2023

  8. [8]

    J. Cha, J. Lee, and C. Yun. Tighter lower bounds for shuffling sgd: Random permutations and beyond. In International Conference on Machine Learning, pages 3855--3912. PMLR, 2023

    work page 2023

Show all 61 references
  1. [9]

    Cortild, L

    D. Cortild, L. Ketels, J. Peypouquet, and G. Garrigos. New tight bounds for sgd without variance assumption: A computer-aided lyapunov analysis. arXiv preprint arXiv:2505.17965, 2025

    2025

  2. [10]

    C. M. De Sa. Random reshuffling is not always better. Advances in Neural Information Processing Systems, 33: 0 5957--5967, 2020

    2020

  3. [11]

    T. Doan, M. Abbana Bennani, B. Mazoure, G. Rabusseau, and P. Alquier. A theoretical analysis of catastrophic forgetting through the ntk overlap matrix. In Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, pages 1072--1080, 2021

    2021

  4. [12]

    T. Elfving. Block-iterative methods for consistent and inconsistent linear equations. Numerische Mathematik, 35 0 (1): 0 1--12, 1980

    1980

  5. [13]

    Evron, E

    I. Evron, E. Moroshko, R. Ward, N. Srebro, and D. Soudry. How catastrophic can catastrophic forgetting be in linear regression? In Conference on Learning Theory (COLT), pages 4028--4079. PMLR, 2022

    2022

  6. [14]

    Evron, E

    I. Evron, E. Moroshko, G. Buzaglo, M. Khriesh, B. Marjieh, N. Srebro, and D. Soudry. Continual learning in linear classification on separable data. In International Conference on Machine Learning, pages 9440--9484. PMLR, 2023

    2023

  7. [15]

    Evron, R

    I. Evron, R. Levinstein, M. Schliserman, U. Sherman, T. Koren, D. Soudry, and N. Srebro. From continual learning to sgd and back: Better rates for continual linear models. arXiv preprint arXiv:2504.04579, 2025

    2025

  8. [16]

    Garrigos, D

    G. Garrigos, D. Cortild, L. Ketels, and J. Peypouquet. Last-iterate complexity of sgd for convex and smooth stochastic problems. arXiv preprint arXiv:2507.14122, 2025

    2025 arXiv

  9. [17]

    R. Ge, S. M. Kakade, R. Kidambi, and P. Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure for least squares. Advances in Neural Information Processing Systems, 32, 2019

    2019

  10. [18]

    Goldfarb and P

    D. Goldfarb and P. Hand. Analysis of catastrophic forgetting for random orthogonal transformation tasks in the overparameterized regime. In International Conference on Artificial Intelligence and Statistics, pages 2975--2993. PMLR, 2023

    2023

  11. [19]

    Goldfarb, I

    D. Goldfarb, I. Evron, N. Weinberger, D. Soudry, and P. Hand. The joint effect of task similarity and overparameterization on catastrophic forgetting - an analytical model. In The Twelfth International Conference on Learning Representations, 2024

    2024

  12. [20]

    R. M. Gower and P. Richt \'a rik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 36 0 (4): 0 1660--1690, 2015

    2015

  13. [21]

    Gubin, B

    L. Gubin, B. T. Polyak, and E. Raik. The method of projections for finding the common point of convex sets. USSR Computational Mathematics and Mathematical Physics, 7 0 (6): 0 1--24, 1967

    1967

  14. [22]

    Han and J

    D. Han and J. Xie. A simple linear convergence analysis of the reshuffling kaczmarz method. arXiv preprint arXiv:2410.01140, 2024

    2024 arXiv

  15. [23]

    N. J. Harvey, C. Liaw, Y. Plan, and S. Randhawa. Tight analyses for non-smooth stochastic gradient descent. In Conference on Learning Theory, pages 1579--1613. PMLR, 2019

    2019

  16. [24]

    Hemati, L

    H. Hemati, L. Pellegrini, X. Duan, Z. Zhao, F. Xia, M. Masana, B. Tscheschner, E. Veas, Y. Zheng, S. Zhao, et al. Continual learning in the presence of repetition. In CVPR Workshop on Continual Learning in Computer Vision, 2024

    2024

  17. [25]

    Hiratani

    N. Hiratani. Disentangling and mitigating the impact of task similarity for continual learning. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  18. [26]

    P. Jain, D. Nagaraj, and P. Netrapalli. Making the last iterate of sgd information theoretically optimal. In Conference on Learning Theory, pages 1752--1755. PMLR, 2019

    2019

  19. [27]

    H. Jung, H. Cho, and C. Yun. Convergence and implicit bias of gradient descent on continual linear classification. In The Thirteenth International Conference on Learning Representations, 2025

    2025

  20. [28]

    Kaczmarz

    S. Kaczmarz. Angenaherte auflosung von systemen linearer glei-chungen. Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat., pages 355--357, 1937

    1937

  21. [29]

    M. Kong, W. Swartworth, H. Jeong, D. Needell, and R. Ward. Nearly optimal bounds for cyclic forgetting. In Thirty-seventh Conference on Neural Information Processing Systems, 2023

    2023

  22. [30]

    Lai and L.-H

    Z. Lai and L.-H. Lim. Recht-r \'e noncommutative arithmetic-geometric mean conjecture is false. In International Conference on Machine Learning, pages 5608--5617. PMLR, 2020

    2020

  23. [31]

    G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133 0 (1): 0 365--397, 2012

    2012

  24. [32]

    Lesort, O

    T. Lesort, O. Ostapenko, P. Rodr \' guez, D. Misra, M. R. Arefin, L. Charlin, and I. Rish. Challenging common assumptions about catastrophic forgetting and knowledge accumulation. In Conference on Lifelong Learning Agents, pages 43--65. PMLR, 2023

    2023

  25. [33]

    Levinstein, A

    R. Levinstein, A. Attia, M. Schliserman, U. Sherman, T. Koren, D. Soudry, and I. Evron. Optimal rates in continual linear regression via increasing regularization. arXiv preprint arXiv:2506.06501, 2025

    2025

  26. [34]

    H. Li, J. Wu, and V. Braverman. Fixed design analysis of regularization-based continual learning. In Conference on Lifelong Learning Agents, pages 513--533. PMLR, 2023

    2023

  27. [35]

    S. Lin, P. Ju, Y. Liang, and N. Shroff. Theory on forgetting and generalization of continual learning. In International Conference on Machine Learning, pages 21078--21100. PMLR, 2023

    2023

  28. [36]

    C. Liu, D. Drusvyatskiy, M. Belkin, D. Davis, and Y. Ma. Aiming towards the minimizers: fast convergence of sgd for overparametrized problems. Advances in neural information processing systems, 36: 0 60748--60767, 2023

    2023

  29. [37]

    Liu and Z

    Z. Liu and Z. Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024 a

    2024

  30. [38]

    Liu and Z

    Z. Liu and Z. Zhou. On the last-iterate convergence of shuffling gradient methods. In Forty-first International Conference on Machine Learning, 2024 b

    2024

  31. [39]

    S. Ma, R. Bassily, and M. Belkin. The power of interpolation: Understanding the effectiveness of sgd in modern over-parametrized learning. In International Conference on Machine Learning, pages 3325--3334. PMLR, 2018

    2018

  32. [40]

    Mermillod, A

    M. Mermillod, A. Bugaiska, and P. Bonin. The stability-plasticity dilemma: Investigating the continuum from catastrophic forgetting to age-limited learning effects, 2013

    2013

  33. [41]

    Mishchenko, A

    K. Mishchenko, A. Khaled Ragab Bayoumi, and P. Richt \'a rik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 2020

    2020

  34. [42]

    Nagaraj, P

    D. Nagaraj, P. Jain, and P. Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703--4711. PMLR, 2019

    2019

  35. [43]

    Needell and J

    D. Needell and J. A. Tropp. Paved with good intentions: analysis of a randomized block kaczmarz method. Linear Algebra and its Applications, 441: 0 199--221, 2014

    2014

  36. [44]

    Needell, R

    D. Needell, R. Ward, and N. Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Advances in neural information processing systems, 27: 0 1017--1025, 2014

    2014

  37. [45]

    Nesterov

    Y. Nesterov. Introductory lectures on convex programming volume i: Basic course. Lecture notes, 3 0 (4): 0 5, 1998

    1998

  38. [46]

    Oswald and W

    P. Oswald and W. Zhou. Convergence analysis for kaczmarz-type methods in a hilbert space framework. Linear Algebra and its Applications, 478: 0 131--161, 2015

    2015

  39. [47]

    L. Peng, P. Giampouras, and R. Vidal. The ideal continual learner: An agent that never forgets. In International Conference on Machine Learning, 2023

    2023

  40. [48]

    Rajput, A

    S. Rajput, A. Gupta, and D. Papailiopoulos. Closing the convergence gap of SGD without replacement. In International Conference on Machine Learning, pages 7964--7973. PMLR, 2020

    2020

  41. [49]

    Rakhlin, O

    A. Rakhlin, O. Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning, pages 449--456. PMLR, 2012

    2012

  42. [50]

    Recht and C

    B. Recht and C. R \'e . Beneath the valley of the noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences. In Conference on Learning Theory (COLT), 2012 a

    2012

  43. [51]

    Recht and C

    B. Recht and C. R \'e . Toward a noncommutative arithmetic-geometric mean inequality: conjectures, case-studies, and consequences. In Conference on Learning Theory, pages 11--1. JMLR Workshop and Conference Proceedings, 2012 b

    2012

  44. [52]

    Safran and O

    I. Safran and O. Shamir. How good is SGD with random shuffling? In Conference on Learning Theory, pages 3250--3284. PMLR, 2020

    2020

  45. [53]

    Shamir and T

    O. Shamir and T. Zhang. Stochastic gradient descent for non-smooth optimization: Convergence results and optimal averaging schemes. In S. Dasgupta and D. McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Mach...

    2013

  46. [54]

    Srebro, K

    N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. Advances in neural information processing systems, 23, 2010

    2010

  47. [55]

    Strohmer and R

    T. Strohmer and R. Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15 0 (2): 0 262--278, 2009

    2009

  48. [56]

    A. V. Varre, L. Pillaud-Vivien, and N. Flammarion. Last iterate convergence of SGD for least-squares in the interpolation regime. In A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021

    2021

  49. [57]

    Vaswani, F

    S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence of sgd for over-parameterized models and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pages 1195--1204. PMLR, 2019

    2019

  50. [58]

    J. Wu, D. Zou, V. Braverman, Q. Gu, and S. Kakade. Last iterate risk bounds of sgd with decaying stepsize for overparameterized linear regression. In International Conference on Machine Learning, pages 24280--24314. PMLR, 2022

    2022

  51. [59]

    C. Yun, S. Sra, and A. Jadbabaie. Open problem: Can single-shuffle sgd be better than reshuffling sgd and gd? In Conference on Learning Theory, pages 4653--4658. PMLR, 2021

    2021

  52. [60]

    Zamani and F

    M. Zamani and F. Glineur. Exact convergence rate of the last iterate in subgradient methods. arXiv preprint arXiv:2307.11134, 2023

    2023 arXiv

  53. [61]

    Zhang, J

    P. Zhang, J. Teng, and J. Zhang. Lower generalization bounds for gd and sgd in smooth stochastic convex optimization. arXiv preprint arXiv:2303.10758, 2023

    2023 arXiv

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.