Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
Authors: Amit Attia
Matan Schliserman
Uri Sherman
Tomer Koren
Venue: NeurIPS 2025 poster ()
Keywords: last-iterate
low-noise
interpolation
realizable
sgd
stochastic
convex
smooth
Primary area: optimization
TL;DR: We present a sharp last-iterate analysis of SGD on smooth convex losses in the interpolation regime, extending prior results beyond linear regression and improving known rates for large, constant stepsizes.

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}(\tfrac{1}{\eta (2-\beta \eta) T^{1-\beta\eta/2}} + \tfrac{\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 $O(1/\sqrt T)$ with $\eta=1/\beta$, improving upon the best-known $O(T^{-1/4})$ rate recently established by Evron et al. (2025) in the special case of realizable linear regression.

Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime
Amit Attia"
Matan Schliserman'
Uri Sherman
Blavatnik School of Computer Science and Al
Tel Aviv University
urrishemmnne@mll tau. ac. i1
Tomer Koren
Blavatnik School of Computer Science and AI
Tel Aviv University and Google Research tkorenStauez. tau. aau ac
Abstract
We study population convergence guarantees of stochastic gradient descent (SGD) for smooth convex objectives in the interpolation regime, where the noise optimum is zero or near zero. The behavior of the last iterate of SGD in this particgular with large (constant) stepsizes- has received growing atten- tion in recent years due to implications for the training of wver-parameterized models, as well standing the convergence of the randomized Kaczmarz method for solving lin- ear systems. We establish that after 7' steps of SGD on B-smooth convex loss functions with stepsize 0 < < 2/8, the last iterate exhibits expected excess risk O (122-B)7'-ppn"" + (2- ByBByz2 (2-8n)= TB) where of denotes the variance of the 2/12 stochastic gradients at the optimum. In particular, for well-tuned stepsize tain near optimal ((1T + rv+)VT) rate for the last iterate, extending the results of Varre et al. [202T] beyond least squares regression; and when o = 0 we obtain a rate ((1/ vT) with 17 = 1/8. improving upon the best-known ((T-1/4) rate recently established by Evron al. [2025) in the special case of realizable linear regression.
analyzing forgetting in continual learning and under-
ob-
Introduction
We study the convergence of Stochastic Gradient Descent (SGD) for smooth convex objectives in the low-noise and interpolation regimes. Concretely, we consider optimization problems the form
min F(x) = =Ez--l/(x; xeRd
where Z a distribution over sample space Z, and f(:z): Rd R is convex and 8-smooth for all Z. In the low-noise regime, the gradient noise at the optimum, defined as of = V. [x=; for + E arg min F(x), assumed to be small or even zero. The special case where or known the interpolation regime, in which x* minimizes f(,z) for almost all Z. We seek bounds on the expected excess risk SGD, that given an i.i.d. sample Zi...., 2r Z performs the following updates, starting from an initialization x1 Rd:
Xy+1
1/ f(ri)))
(I=1,....T
Equal contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Standard convergence bounds of SGD apply to an average (possibly weighted) of the iterates. It is by now a classical result that in the smooth low-noise regime, the average iterate of SGD with a constant stepsize 7 = (11 converges at a fast rate of O o /vT [Srebro et al. 2010 Ma et al. 2018), as compared to the slower 0(1/ VT) rate that holds more generally. In this work, we study last-iterate bounds for SGD, namely bounds that apply to the expected loss [[F(x)) of the
last SGD iterate rather than to an average of the iterates. Somewhat surprisingly. despite long line of
work on last-iterate bounds [Rakhlin et al. 2012 Shamir and Zhang 2013 Jain et al.) 2019 Harvey
et al. [2119] Varre et al., 2021] Zamani and Glineur [203]] Liu and Zhou| 2024a Evron et al. [025 ,
it has remained unknown whether fast rates in the smooth low-noise regime are also attained by the last iterate. Our goal in this paper is to fill in this gap.
There are several compelling reasons to study last-iterate bounds in low-noise regimes. First, as argued by Ma et al. [2018], the fast empirical convergence of SGD in training deep models, which is often run with a fixed constant stepsize, can be attributed to the fact that modern overparameterizeed networks are typically powerful enough to interpolate the data and reach zero loss, placing their optimization naturally in the interpolation regime. Second, it has been established that classical methods for solving ordinary least squares (OLS) problems and underdetermined systems of linear equations, such as the (randomized) Kaczmarz method, are instances of last-iterate SGD in the smooth interpolation regime [c.g.. Needell et al., 2014). Third, it has been recently demonstrated that last-iterate bounds for SGD in this regime are beneficial for analyzing catastrophic forgetting in a
certain class of realizable continual learning problems [Evron et al. 2022 2025),
and this observation
has led to improved analyses.
Crucially, however, some of the aforementioned applications of SGD in the interpolation regime hinge on a specific choice of a stepsize: 17 = I/B. We refer to this as the "greedy stepsize" since, in the case of least squares (and in particular, in the Kaczmarz method), it leads to update that steps directly to a minimizer of the instantaneous loss. Curiously though, previous analyses of SGD (either for the last or the average iterate) have not been able to treat the greedy choice 17 1/B P and have only provided bounds for stepsizes of the form 17 = c/B. for a constant c strictly smaller than one (Srebro et al., 2010 Lan 2012, Varre et al., 202 Needell et al.] [014 Liu and Zhou 2024a). Thus, these analyses do not transfer to applications like continual learning and the randomized Kaczmarz method, which do require the exact setting of ' = 1/B. Very recently, |Evron et al. 20225] revisited this issue and established last-iterate bounds for SGD with 1) 1/B in the pure interpolation regime (or, 0), that scale O(1/T//4) but hold only for OLS. Thus, there is still quite a significant gap between the best last-iterate bounds in this case and the fast O(1/T) rate achieved by the average iterate of SGD with general smooth and convex losses
directly
In this work, we provide the first (nearly-) )optimal last-iterate convergence rate for SGD in the low-n setting, significantly generalizing previous results limited to the OLS case in the pure interpolation regime with 0* O. Furthermore, we establish the first last-iterate guarantce with a constant "greedy" stepsize 1 1/B in the interpolation regime and, consequence, substantially improve upon the best known rates for randomized Kaczmarz and realizable continual learning (in the condition-independenl setting, not relying on strong convexity).
1.1 Summary of contributions
In more detail, in this paper we make the following contributions:
We establish a convergence rate of
TB 022
(2 - B1) Bulz (2 -2-
for the last iterate of Ttstpss SGD with stepsize 0 < < 2/ on convex and 8-smooth objectives, where o is the variance of the stochastic gradients at the optimum. When 17 s
While not stated explicitly in their paper, Bach and Moulines (2013) did provide bound for y = 1/B, but only in the context of OLS and only for the average iterate of SGD.
We remark that even for the average iterate, existing analyses not directly apply to the greedy stepsize
? =
1/B: we provide a more refined argument treating this case in Appendix [ The same applies to the
last- -terait bounds in the strongly convex case derived in Needell et al. [2014]. which also hold only for 17 x 1/B: we complement these results with analysis for any stepsize 1) < 2/5. see details in Appendix

---

Table 1: Convergence bounds for SGD in smooth convex settings. The table considers the dependence on the number of iterations T, global noise bound o² sup, - (x af = f 2) VF(x*)]I The step size the algorithm denoted by 17. OLS stands for Ordinary I Least Squares. Dependence on other parameters (c.g., the distance to the optimal solution), constants, and logarithmic factors is omitted for clarity. Only cumension-indeeendeen guarantees are included in the table.
and variance at the optimum
ADDITIONAL. ASSUMPTIONS
OUTPUT
CONVERGENCE
SETTING
REFERENCE
ITERATE
RATE
Lan 2012
Average
1/T + o INT O/T
B-smooth, convex 7 optimally tuned
Srebro et al.
2010
Average
Liu and Zhou
2024a
Last
1/T
This paper
Last
1/T+0=/VT
B-smooth, convex realizable (o, 0) 7 optimally tuned
Srebro al.
2010
Average
1/T
Varre al.
2021
OLS
Last
1/T
This paper
Last
1/T
B-smooth, convex realizable (OT, 0)
Bach and Moulines 2013
OLS
Average
1/T
Evron et al. 2025
OLS
Last
1/T1/4
17 = 1/B
This paper
Last
1/VT
Srebro et al. 2010 established slightly weaker guarantee that scales with the approximation error instead of (Tx. but can be refined to O(1/" + /VT).
Bach and Moulines [2013) also established convergence rate for ordinary least squares in the non-realizable
setting; however, the result is cimensionndependdn and therefore omitted from the table.
1/ log 7), our guarantee translates to ((1((17) + n providing the first fast last-iterate convergence rate the low-noise regime (i.e., when i+ < 1). In particular, through an appropriate tuning of the stepsize we obtain near optimal O(1/T+ o, vT) rate for the last iterate, extending the results of Varre et al. [202]] beyond least squares regression.
(ii In the interpolation regime (i.e., when o+ 0), we provide the first last-iterate convergence guarantee with "greedy" constant stepsize = B/B, achieving a rate of O(1/VT) and improving upon the best-known rate of 1/4 in the special case of linear regression due to Evron (et al. 2025). This improved rate leads better performance guarantees in applications such as continual linear regression and the randomized Kaczmarz method, via recent reductions to SGD with 17- = 1/B.
(iii) Finally, extend our result in the interpolation regime to without- rethout-replacemeett SGD, achieving a similar O(1/T) fast rate and improving upon prior work where multiple passes over the samples were required for providing meaningful bounds (Cai and Diakonikolas 2025 Liu and
Zhou 2024b).
See Table I for a summary of our results compared to existing art. We remark that while the improved O(1/VT) rate we establish in the greedy case л 1/B is likely not tight (we discuss optimality more below), it does not follow from the general ( (T) rate for the last iterate of SGD in the convex and Lipschitz (non-smooth) case [c.g.. Shamir and Zhang 2013 Liu and Zhou 2024a]. Indeed, the latter convergence results require a non-constant stepsize of order = OIIVTT) whereas our goal is specifically address the particular choice of r = 1/B.
Open problems. Our work leaves several interesting questions for further investigation. Most notably, our rate in the regime where o, 0 and f = 1/B is O(I/TT), whereas the best known lower bound in this setting is Q(1/T) re.g./Zhang et al. 2023), which also matches the upper bound for the average-iterate of SGD (see details in Appendix BB. Closing this gap remains an open question for future work. As noted above, such an upper bound would also yield improved guarantees in continual learning and the Kaczmarz method. Notably, those settings as well, the best known lower bound is 2(1/T) [Evron et al. 2022). Moreover, when the step size 17 is optimally tuned, we obtain nearly optimal convergence rates up to logarithmic factors. Eliminating this remaining gap is left for future work. Finally, our convergence guarantee under without-replacement sampling currently holds
3

---

only in the interpolation regime. Whether this guarantee can be established in the low-noise regime remains an open question.
1.2 Related work
Last-iterate analysis of SGD. There is a rich line of work studying last-iterate convergence of
SGD, most of which focuses on the convex Lipschitz setup in the gradient oracle model [Rakhlin
al. 2012 Shamir and Zhang 2013 Jain et al., 2019, Harvey et al., 2019, Zamani and Glinneur Liu and Zhoo 2024a]. Surprisingly, this line of work has reached fruition with near-optimal bounds all but the low-noise regimes. While the recent work of oi and Zhou (2024a] additionally establishes last-iterate convergence for smooth convex objectives which may be applied in our setting, their bounds depend on a global noise parameter that can be arbitrarily larger than d. In particular, in the interpolation regime, their result translates to a suboptimal convergence rate of (1/ VT), whereas average-iterate -etrage bounds are known to achieve the faster rate of ((//T) (Srebro et al. 2010 Moreover, their analysis does not establish convergence of SGD with the "greedy" stepsize 1 I/B. which is of particular importance due to the connection to continual learning and the Kaczmarz method [e.g., Needell et al. 2014 (vvon et al. 2022 2025]. By considering only the restricted class of ordinary least squares (OLS), several works have established last-iterate convergence results (see Table [oor details). In contrast, we do not assume loss functions have any specific parametric form, nor do we assume the full objective is strongly convex.
2023
Overparametrization in deep learning. Our work is additionally motivated by modern machine learning setups, where heavily over-parameterizee deep neural networks are trained via SGD to perfectly fit the training data. Recent research connects over vve-parramttiization with the ability to interpolate the training data, i.e., realizability of the empirical risk, and further, realizability with the fast convergence of SGD observed in practice [Ma et al.] 2018). In accordance, a growing line of work studies convergence behavior of SGD in the interpolation regime [e.g.. Ge al.
2019 Vaswani eet al.] 2019 [Berthier et al.] 2020 Varre et al. 202T Wu et al. [022]] Liu et al. 2023] typically for under-determined linear regression problems, or under the assumption that component losses are convex and smooth and the full objective is strongly convex.
The Kaczmarz method. It is by now well-known that several variants of the (randomized) Kacz- marz method for solving underdetermined linear systems can be cast as instances of stochastic gradient descent [Needell et al.) 2014]. Typical convergence bounds for the Kaczmarz method depend on the condition number of the coefficient matrix A; when the minimal singular value of A is strictly positive, various variants of the method are known to converge linearly to the minimum-nome solution x* [Gower and Richtárik 2015 Han and Xie, 2024, Needell and Tropp 2014]. However, the convergence rates in these settings can be arbitrarily slow, depending on the condition number of A, which is potentially arbitrarily large. Our results extend these findings by providing bounds that apply even when min O, independently of the condition number of A. Our guarantees in this case are in terms of the squared error, rather than of the Euclidean distance to a solution.
A key idea introduced by Strohmer and Vershynin 2009) in the context of the Kaczmarz method is to sample rows uniforrll,,, with probabilities proportional to their squared norms. This sampling strategy fits naturally within the SGD framework, allowing us to analyze norm-based variants and derive sharper bound (Corollary 44. where the bound depends on the average rather than the maximum row norm. In the block setting, both uniform and weighted sampling approaches have been explored (Needell and Tropp) 2014 Gower and Richtárik, 2015). Similar to the single-row case, our results indicate that assigning sampling probabilities based on block norms can improve the analysis in similar way, and imply better bounds through the average rather than the maximum block norm.
Continual linear regression. Prior work in continual learning has extensively studied the problem of catastrophic forgetting, demonstrating that the extent of forgetting is influenced by factors such as task similarity, model overparameterization,, and the basticittysstabille trade-off [Goldfarb et al.) 2024, Mermillod et al. 2013). A growing body of theoretical and empirical research has shown that forgetting can diminish over time when tasks are presented cyelic or random orderings [Evronn et al. 2022 2023 Kong et al. 2023. Jung et al.) 2025 Cai and Diakonikolas, 2025 Lesort et al. 2023 Hemati et al.] 2024 Evvro al. [2025). J. Such orderings have been studied as mechanisms for
mitigating forgetting, either through explicit control of learning environments or by modeling naturally

---

recurring patterns (e.g., seasonality in real-world domains), A recent line of work (Evron et al. 2022 2025] demonstrated that convergence bounds for convex, B-smooth realizable optimization such as those considered in our setting can be applied to continual linear regression, where each task is regression problem learned to convergence. Our more general results yield state-of-the-art bounds when applied in this setting. Concurrently to this work, Levinsteen et al. [2025] showed that optimal O(1/T) bounds in continual linear regression can also be achieved using a different approach: instead
of fully optimizing each task, they present two methods- that minimizes regularized loss per task and another that performs a finite number of optimization steps.
With vs. without--replacement sampling. Our analysis of SGD without-repllaemment relates to prior work average iterate convergence [e.g.. and Ré 2012b Nagaraj et al. 2019 Safran
and Shamir 2020 Rajput et al.] [020] Mishchenko et al. 2020 Cha et al., [023]
Cai et al. 2023
For smooth, non-strongly convex objectives, near-optimal bounds have been established Nagaraj
iet al. 2019 Mishchenko et al. 2020), with refined parameter dependence in the realizable case by
Cai et [ [2033] Last-iterate guarantees have more recently been studied by Liu and Zhou| 2024b),
Cai and Diakonikolas [2025), though these results assume non-constant step sizes and provide rates in terms of epochs, limiting their applicability to our setting. Specifically, in a realizable B- B-smooth setup, after / authoou--replaemeee
SGD epochs over a finite sum of size n. Mishhhenno et al. (2020). Cai et al. (2023) obtained an ((BJJ bound for the average iterate with step size 1) = 1/(Bm) and
Liu and Zhou [2024b), Cai and Diakonikolas [025 derived similar bounds for the last iterate up
to logarithmic factors. addition, EEron et al. [025 recently analyzed the OLS setting with large
step sizes, showing a last-iterate rate of ((1/T) for optimally tuned step sizes, and O(1/T1/+) for
7 = I/B. We extend those results to general convex B-smooth realizable objectives, obtaining similar rates under optimal tuning and an improved V(I/VT) rate for 17 1/B under without-replacemment sampling.
The role of sampling order has also been studied in the context of the Kaczmarz method, where without--eplacemment sampling can lead to faster convergence. Recht and R$ 2012aa conjectured that noncommutative arithmetic-geomerrie mean inequality could explain this advantage, but this was later disproven by Lai and Lim| [2020), with further clarification by De Sa 2020]. Empirical work has shown that row-shufiling and cyclic orderings can perform comparably to r.ddd. sampling [Oswald and Zhou 2015), aligning with broader observations in shuffled SGD [Bottou| 2009| Yun et al. 2021]. Our results support those of Evron et al. [2025) that suggests that with- and without-replacemmnt sampling yield comparable performance up to constant factors. Thus, our analysis does not reveal a theoretical preference for one strategy over the other, leaving open the question of whether practical advantages can be gained through ordering.
Concurrent work. Following the initial publication of the present manuscript on arXiv [Atiia et al., 2025). an independent work was released [Garrigos al. [2025), which investigates the last-iterate convergence of SGD for convex and smooth objectives and establishes results closely related to ours. For properly tuned stepsize. Garrigos et al. [2025] achieves the same nearly-optimal convergence rate of 0 + /./ /T). On the other hand, their result does not support for large stepsizes in the range 1/B I 17 < 2/B (in particular, it does not accommodate the "greedy" choice 17 = 1/B) and, compared with Theorem provides weaker convergence rates for stepsizes of the form 17 = c/B for a constant e < 1. In addition, the very recent work of Cortild et al. [2025), brought to our attention after the initial publication of our manuscript on arXiv, establishes average- -iterte guarantees for SGD in the convex and smooth setting for any stepsize 1) < 1/(2/), results that closely mirror those we include in Appendix B
2 Last-iterate analysis in low-noise regimes
This section presents our main results concerning last-iterate convergence of SGD in the interpolation and low-noise regimes: in the interpolation regime, all functions share common minimizer; while in the low-noise regime, the objective F(x) admits a minimizer, and the variance of the stochastic gradients at that minimizer is small. Subsequently, we provide overview of our analysis technique.
5

---

Problem setup. Let Z be an index set for convex loss functions f(::2): R - R. and Z E A(Z) be an arbitrary distribution over We consider the unconstrained stochastic optimization problem:
min (F(x) =x;-z((x;)) xe
(I)
under the assumption that the loss functions are individually smooth. Specifically, assumee that for all 2 E Z, the function f(:2)) is B-smooth, namely that [VV((;;z) - fx; all x, E Rd. (Throughout, ||-]| refers to the 6 norm.) We further assume that the objective F admits a minimizer, denoted by x* E arg min gd F(x), and that the variance of the stochastic gradients at xxx is bounded, o == E f =x < so The special case where o is referred to as the interpolation regime, which x* minimizes ((,z) for almost all Z.
s flly xI| for
Throughout the paper, we consider the fixed stepsize SGD algorithm, which given an initialization E Rd stepsize 17 > O, number of steps T and an i.id. sample 2T, performs at each step f == ... the update
x -NZf(x))
where fi(x) = f(x;z))
2.1 Main results
We next state main results. We begin with the guarantee in the interpolation regime.
Theorem 1 (last-iterate convergence in the interpolation regime). Let f: Rd x Z - R be such that f(;;z) is B-smooth and convex for every 2. Assume there exists x* Rd such that x* arg meny fxx; 2) for all z Z. Then. for SGD initialized at X1 Rd with step size n B/ where T 2 2, we have the following last iterale guarantee:
311x1 - 11
E{F(xT) FFx))]
1)22 - T-
Bnn
In particular:
1. it holds that E[F(xT) - F] 5 30
(i) when 17 B.
VT
(ii when 17 (T5. it holds that E[F(xT) - F(x*) x 6f1lx)-- (ogg, (7)
In comparison the average-iterate guarantee of SGD (Srero et al. 2010 , the last-iterate guarantee in Theorem I lincurs a suboptimal factor of 7 by choosing 17 I/(B logg 7), this suboptimality is reduced to logarithmic factor and the bound nearly matches the average-iterate performance.
We further extend the above last-iterate convergence guarantee to the more general low-noise regime, where the noise the optimum is small but nonzero.
Theorem 2 (last-iterate convergence in the low-noise regime). Let f: Rd Z R be such that f(+2)) is B-smooth and convex for every z. Assume there exists a minimizer x* E arg yed F(x), and that o² < co. Then, for T Tiseeps SGD initialized al xı E RRd with step size < 2/B, where 2 2, we have the following last iterate guarantee:
12 - 1+1
24n
E(F(XT) F(x*)] S
11(2 B +
22TB1/2 log, (T +2)
(2 (2-Bn)²
In particular, when min {1/Blog, ||x] 1 1o lo 2)
E[F(t)) F(x*) s 24 xx 11
120 || x*1 |l Togg (T (T+2)
T
VT
Theorem is essentially extension Theorem I (where had or, = 0), albeit with larger constant factors that stem from the discrepancy between || z) and ( - vf(xx in the low-noise case, when x is not necessarily minimizer of 2))
*I case of multiple minima, a+ can be defined with respect one of them and in fact, its value can be shown to be the same across all minimizers; for additional details, Appendix

---

2.2 Proof outline
Here we give an outline of the proof of Theorem containing the main components of our analysis; for the full proof of Theorems 2nd see Appendix G While the outline is stated for the interpolation setting and with replacement sampling, the core components discussed also play a central role in our low-noise (Theorem 2) and sampling without-replacemmnt (Theorem 3 results.
A natural starting point for obtaining last-iterate guarantees in the interpolation regime is through the analysis technique of Shamir and Zhang (2013), who provided the first last-iterate convergence guarantee in the general convex (non-smooth) setting. Recent previous work extended the technique to the interpolation regime [Evron et al. 2025). but was limited to linear regression and only achieved a suboptimal O(1/T1/4 rate for 17 = 1/B An alternative approach, which was also taken by Liu and Zhou| [0224a]. , is based powerful technique introduced by Zamani and Glineur [2023] for analyzing the subgradient method for deterministic (non-smooth) convex optimization, which they used for obtaining min-max optimal rates.
Starting point: the Zamani & Glineur technique. The starting point of our analysis is the technique Zamani and Glineur [023] for deriving last-iterate convergence bounds for the (deter- ministic) subgradient method in nonsmooth convex optimization. Starting at x1 e R and performing the deterministic update steps over convex and differentiable function F with fixed stepsize, X,+1 = X, n (xx) for = 1.2..... T, it follows from their analysis that
V2 ||I1 x xx1
n Σ (IVF(()))) 2
Σ (F(x,) - =(x*)) =
2
where c; = (v; (v,-1,-1) >T Vss and 0 vo Vi ... S vT are arbitrary non-decreasing weights.
By carefully selecting the weights such that cT > and c, = 0 for s 1 T, one can obtain convergence bound for the last iterate xy:
1 2nCT
F(XT) - F(x) s
|| - -x*11 11+
2CT
Step (i): from deterministic to stochastic smooth optimization. Our first step is to generalize the analysis to the stochastic case, in which the update step step r is X,+1 X, fx;s),)))) where Z. Extending the analysis, we obtain that
7 Σ n c(E(F(x) F(x*)] = 6 || =11
2
Using the inequality (x) 2x)) F(x*), which is result of standard properties of convex and smooth functions, gives
v2 2 ||x 11
c, Bny? (IF(x)-F(x))
n
Step (ii): modifying the weights Fly..., PT. The bound in the above display cannot yield meaningful bound for 7 = 1/B, since the leading coefficient is negative: - 12 < 0. Even with 7 1/8, the previously specified weights which satisfy C, for 1 S < T lead to a vacuous 1-89
inequality. Using instead the weights setting v, (T r 2) T-pn for < T and vy VT-1, for which one can show that c, -nyy 2 0, we can establish that
E(F(xT) Fxx* 0 - -
(2)
which is still vacuous for 17 1/B, but is strong enough for obtaining a rate of O(1/T) for stepsize 77 = (T)
*In Appendix we provide simplified analysis using the technique of Shamir and Zhang 2013 the general convex and smooth setting: while the analysis achieves optrmaptimal guarantees for small stepsizes, does not yield guarantee for the choice = 1/B and provides weaker rates for large stepsizes = c/B (for constant < 1).
7

---

Step (iii): tightening the regret analysis. To further support the greedy setting 1/B and to improve the above bound for general 17 1/B, we further tighten the analysis, obtaining
nT 2
r
C2 (x) -f - vollxi - -x111 11
(
r=1
Σ - 1 1=1 .=1
V1
2B
This is achieved by replacing the use of the gradient inequality, f()) 2 f(x) (Vf(x). in the analysis of for general convex functions with the tighter lower bound for convex and smooth functions: f(y)= f(x) + (VS()),y x) 2p VV
Step (iv): handling the cross terms. new challenge now arises from handling the cross terms
[[V - (xxx)) A basic approach will be to use Young's inequality to bound
[V, - v fi (x z (1+ fI (1+ 1/1)II (x,
After rearranging the terms and carefully optimize over A, one can already obtain bound of
- - =
0 [111x] x 11 1-100in2600
achieving a rate of 2/5) with stepsize 17 1/B.
Step (v): step-dependent Young's inequality. We further tighten our analysis by carefully modi- fying the above Young's inequality parameter A for each X, pair. This leads us to the improved bound Theorem with a rate of O(1/VT). Additionally, for a stepsize of n 1/2B, our improved analysis achieves a rate of O(T-3/4), compared the of (TT-1/3) achieves by Eq. (2).
3 Extensions and implications
In this section, we show how our improved last-iterate convergence guarantees for SGD in the realizable setting, presented in Theorem leads sharper convergence in several key settings studied the literature. In particular, we extend our analysis to without-rrplacemmen SGD, and derive new results continual learning, leveraging the improved guarantees for both with and without- replacement sampling. These include the block Kaczmarz method, continual linear regression as well continual linear classification and projection onto convex (for the latter, Appendix A
3.1 Without-replaaemeen SGD
We first extend our result to a rapheeet sampling variant of the optimization problem Eq. (I) For this, assume the instance set Z is finite with == IZ). and consider the empirical risk minimization objective:
min F2(x) - xeRd
n E f(x:))
which we will optimize by stochastic gradient descent w.r.t. uniformly random shuffle of the training examples. For initialization X1 E Rd, step size O, without-replacement SGD samples a uniformly random permutation Unif([n] <+ Z), and iterates:
Xr+1
(x;i))))))
(4)
We achieve the following convergence result,
Theorem Let f: Rd x - be such that f(: B-smooth and convex for every z. Assume fur- ther that there exists joint minimizer x* e Ozez arg minxeRa f(x;2). Then, for without-replacemn SGD (Eq. 44) initialized at E &dd with step size 2/B. we have the following last iterate guar- antee for all S n:
91|11 x 11
+ 482 - 11
E(F2(xT) Fz(x*)] S 1/22 B1)
Bn/2 1-7/2
T
8

---

In particular, for 17 B we obtain (xF2 -22 & 13 - /x"1////,, and for n Blog. we obtain, (XT) [x(x))] - 22 log T||x -x*1|
1
To prove Theorem 3 we first establish bound on ([f(()))=f+xx')) in the with-replacement case.
We then apply the without-replacemmet algorithmic stability for smooth and realizable objectives provided by Evron al. 2025]. The full proof appears in Appendix H
3.2 The randomized (block- Jaackaaa method
method is a classical algorithm for solving underdetermined linear systems of the form Ax = b [Kaczmarz] 1937 Elfving. 1980]. The method initializes x1 0, and at each iteration f, samples, with or without replacement, a random block (Az(1), br(1)) from the matrix A and performs the update:
(5) where the solution returned is the last iterate, xy. The choice c = 1 corresponds to the standard Kaczmarz method, while values < 1 are also of interest in certain settings (e.g., Needell et al.) 2014).
X,+1 - X4 - cA (Azcr)i- - br(1)),
In contrast to previous works (see discussion in Section 1.2 which consider the case where A is full-rank matrix and derives upper bounds on the distance between X7 and the unique solution, xx, that depend on the condition number of A (see Section 1.2 for detailed discussion), our analysis evaluates the algorithm's 's performance using the average loss the proposed solution, i.c.,
F(XT) 2m Σー= || byll? Following is the guarantee for the Koccmaazz method.
Corollary 4. Let 2 2, c S 1, and let Ax = be an equation system. Let be such that Ax* method (Eq. (5) for iterations satisfies,
Assume that ||A||2 R. Then, the
R² ||x
EE [F((T]] = 0
T1-cB12
In particular, for the standard method (c 1) we obtain E[F(xt) - F(x))] s O(R21x**1///T))) and for lo(Blog7] T) obtain, [[[((xT) [[xx*]== O(R')Ix*1))))))
The bound given in Corollary 4 iimproves upon the result 0(1/T1/4) given by Evron et al. 2025 for the standard method (c 1), and matches their bound when using the optimal choice c 1/log T The full proof appears in Appendix[] We remark that even in the extensively studied well-conditioned case, the = 1/B: we complement these results with a general analysis for any 0 < < 2/B, see details in Appendix
case was not covered by existing results, as corresponds with SGD stepsize
3.3 Continual linear regression
Continual linear regression has been studied extensively in recent years [c.g.. Doan et al. 202 Evron et al. 2022 Lin et al.] [223] Peng et al. 2203 Goldfarb and Hand 2023 Li et al. 2023 Goldfarb ct al. 2024 Hiratani 2024 Evron et al. 2025 In this setting, the learner is provided with sequence of regression tasks, where each task is represented by dataset (Aj, by) for j I,..., m, with
Aj E Ra bj R
The learner initializes with x = and, at each iteration, receives a task (Ar()) b br()) that sampled uniformly at random (with or without replacement) and minimizes the squared loss for the current task by performing the update
X,+1 {minimize ||x 11
Ar()x=
(6)
After T iterations, the algorithm returns the final model XT+1. We assume that ||A,|| s for all j [m], and we focus on the realizable case, where there exists a vector x* R such that A,x*
by for all j E [m]. We consider two performance metries: the forgetting, defined as (XT+1) ==
27 ΣT [|Ar(x*T+ br())l 2 and the population loss, F(XT=1) == Im Σn ||AjxT+1 bj 11
'A more general definition of forgetting is (xT+1) - (1 - - ((A
br(1)ll IP2, but under Eq. O and realizability, the two definitions coincide.

---

Table 2: Comparison of forgetting and loss rates for continual lincar regression. The hold for block Kaczmarz with = I. Notation: tasks, 7 iterations, d' dimensionality. F, Tmax average and maximum data-matrix ranks, A b min(a, b). We omit multiplicative factors of ||x R|
RANDOM ORDERING
RANDOM ORDERING
REFERENCE
BOUND
WITH REPLACEMENT
w/O REPLACEMENT
d-F
Evron et al.
2022
Upper
V
VM
d-F
Evron et [2025]
Upper
VT
T
T
VT
This paper
Upper
VT
VT
1.
Evron et al.
[022
Lower
T
T
Can be obtained by their construction for 2.
Previous work [Evron et al. 2022 2023
2025
has shown that the update rule in Eq. 66 can be modified loss functions. By leveraging this
reduced to SGD update with step size 7 reduction and applying our main result for the last iterate of SGD (Theorem [ we derive improved convergence guarantees for continual linear regression. In particular, using the convergence rate of SGD on B-smooth functions with step size n from Theorem |
we obtain the following result:
Corollary 5. Suppose tasks are sampled uniformly at random, either with or without replacement, from a collection of m jointly realizable tasks. Then, after T 2 2 iterations, the expected population loss and forgetting of the continual linear regression algorithm in Eq. (6) satisfy
E, [F (XT+1)] 0 01211xx*11////
E, [F[[(x++))] 0 (R2
The result in Corollary improves the best known purameter-independee rates for continual linear regression from Evron al. 2025 (see Table 2 for more detailed comparison to previous work). For the proof of Corollary
see Appendix
Acknowledgements
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement No. 101078075). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority be held responsible for them. This work received additional support from the Israel Science Foundation (ISF, grant numbers 2549/19 and 3174/23), a grant from the Tel Aviv University Center for AI and Data Science (TAD), from the Len Blavatnik and the Blavatnik Family foundation, from the Prof. Amnon Shashua and Mrs. Anat Ramaty Shashua Foundation, and a fellowship from the Israeli Council for Higher Education.
References
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.
Bach and E. Moulines. Non-strongly-conwee smooth stochastic approximation with convergence rate O(1/n). Advances in neural information processing systems, 26. 2013.
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: 2576-2586, 2020.
10

---

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.
Boyd, Dattorro, et al. Alternating projections. EE392o, Stanford University, 2003.
X. Cai and Diakonikolas. Last iterate convergence of incremental methods and applications in continual learning. In The T'hittenthh International Conference on Learning Representations, 2025.
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. (2t.:233...24488, 2023.
Cha, 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.
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.
C. M. De Sa. Random reshuffling is not always better. Advances in Neural Information Processing Systems, 33:5957-5967, 2020.
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.
T. Elfving. Block-iterative methods for consistent and inconsistent linear equations. Numerische Mathematik, 35(1):1-12, 1980.
I. Evron, E. Moroshko, R. Ward, N. Srebro, and D. Soudry. How catastrophic can catastrophic forgetting in linear regression? Conference on Learning Theory (COLT), pages 4028 4079. PMLR, 2022.
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.
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 25Xiv:2504.04599 2025.
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.
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.
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.
D. Goldfarb, I. Evron, N. Weinberger, D. Soudry, and Hand. The joint effect of task similarity and overparameteriizatoo on catastrophic forgetting an analytical model. In The Twelfth International Conference on Learning Representations, 2024.
R. M. Gower and P. Richtárik. Randomized iterative methods for linear systems. SIAM Journal on Matrix Analysis and Applications, 36(4):1660) 1660)1966-16 2015.
L. Gubin, T. Polyak, and E. Raik. The method of projections for finding the common point of convex sets. USSR Computational Mathematics and Mathematical Physics, 7(6):1244, 1967.
D. Han and J. Xie. A simple linear convergence analysis of the reshuffling kaczmarz method. arXiv preprint arXiv:2410.01 140, 2024.
N. 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.

---

H. Hemati, L. Pellegrini, X. Duan, Z. Zhao, F. Xia, M. Masana, B. Tscheschner, E. Veas, Y. Zheng. S. Zhao, al. Continual learning in the presence of repetition. In CVPR Workshop on Continual Learning in Computer Vision 2024.
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.
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.
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.
S. Kaczmarz. Angenaherte auflosung von systemen linearer glei-chungen. Bull. Int. Acad. Pol. Sic. Let., Cl. Sci. Math. Nat., pages 355-357, 1937.
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.
Z. Lai and L..H. Lim. Recht-ré noncommutative arithmetic-geomene mean conjecture is false. In International Conference Machine Learning, pages 5608-5611 PMLR, 2020.
G. Lan. An optimal method for stochastic composite optimization. Mathematical Programming, 133 (1):365-397, 2012.
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. Conference on Lifelong Learning Agents, pages 43 65. PMLR, 2023.
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.06500/ 2025.
H. Li, J. Wu, and V. Braverman. Fixed design analysis of regularization-basse continual learning. In Conference on Lifelong Learning Agents, pages 513-533, PMLR, 2023.
Lin, P. Ju, Y. Liang, and N. Shroff. Theory on forgetting and generalization of continual learning. In International Conference on Machine Learning, pages 21078-2072 21 100. PMLR, 2023.
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 2023.
systems, 36:60748-600
Z. Liu and Z. Zhou. Revisiting the last-iterate convergence of stochastic gradient methods. In The Twelfth International Conference on Learning Representations, 2024a.
Z. Liu and Z. Zhou. On the last-iterate convergence of shuffling gradient methods. In Forty-first International Conference Machine Learning, 2024b.
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.
M. Mermillod, A. Bugaiska, and Bonin. The stability- plasticity dilemma: Investigating the continuum from catastrophic forgetting to age-limited learning effects, 2013.
K. Mishchenko, A. Khaled Ragab Bayoumi, and P. Richtárik. Random reshuffling: Simple analysis with vast improvements. Advances in Neural Information Processing Systems, 33, 2020.
D. Nagaraj, Jain, and Netrapalli. Sgd without replacement: Sharper rates for general smooth convex functions. In International Conference on Machine Learning, pages 4703-4711 PMLR, 2019.
D. Needell and J. A. Tropp. Paved with good intentions: analysis randomized block kaczmarz method. Linear Algebra and its Applications, 441:199-220
2014. 2014,
12

---

D. Needell, R. Ward, and N. Srebro. Stochastic gradient descent, weighted sampling, and the randomized kaczmarz algorithm. Advances neural information processing systems, 27:1017- 1025, 2014.
Y. Nesterov. Introductory lectures on convex programming volume i: Basic course. Lecture notes, 3 (4):5, 1998.
P. Oswald and W. Zhou. Convergence analysis for kaczmarz-type methods in a hilbert space framework. Linear Algebra and its Applications, 478:131-161, 2015.
L. Peng, P. Giampouras, and R. Vidal. The ideal continual learner: An agent that never forgets. In International Conference on Machine Learning, 2023.
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.
A. Rakhlin, Shamir, and K. Sridharan. Making gradient descent optimal for strongly convex stochastic optimization. In International Conference on Machine Learning, pages 449-4566 456. PMLR, 2012.
B. Recht and C. Ré. Beneath the valley of the noncommutative arithmetic-geomeene mean inequality: conjectures, case-studies, and consequences. In Conference on Learning Theory (COLT), 201 2a.
B. Recht and Ré. Toward noncommutative arithmetic-gcometric mean inequality: conjectures, case-studies, and consequences. In Conference on Learning Theory, pages 11-1. JMLR Workshop and Conference Proceedings. 2012b.
I. Safran and O. Shamir. How good is SGD with random shuffling? In Conference on Learning Theory, pages 3250-3284. PMLR, 2020.
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 Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 71-79. PMLR, 2013.
N. Srebro, K. Sridharan, and A. Tewari. Smoothness, low noise and fast rates. Advances in neural information processing systems, 23, 2010.
Strohmer and R. Vershynin. A randomized kaczmarz algorithm with exponential convergence. Journal of Fourier Analysis and Applications, 15(2):262-273 2009.
A. V. Varre, L. Pillaud-Viviee Vivien, and N. Flammarion. Last iterate convergence of SGD for least-squares in the interpolation regime. In A. Beygelzimer, Y. Dauphin, Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021.
S. Vaswani, F. Bach, and M. Schmidt. Fast and faster convergence of sgd for wer-paraaeterizze mod- els and an accelerated perceptron. In The 22nd international conference on artificial intelligence and statistics, pages 1195-1204 PMLR, 2019.
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.
C. Yun, 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.
M. Zamani and F. Glineur. Exact convergence rate of the last iterate in subgradient methods, arXiv preprint 3rXiv:2307.11134 2023.
Zhang, J. Teng, and J. Zhang. Lower generalization bounds for gd and sgd in smooth stochastic convex optimization. arXiv preprint arXiv:2303.1073 2023.
13

---

A Additional extensions: Projection Onto Convex Sets (POCS) and continual linear classification
Here we provide additional extensions of our previous last iterate convergence result for SGD to other well-researched settings, Projection Onto Convex Sets (POCS) and continual linear classification. Comparison of bounds in those regime previous work appears Table
Table Forgetting Rates in Weakly-Regularized Continual Linear Classification Separable Data. We omit multiplicative factors of [Xx R2?
Random with Replacement
Random w/o Replacement
Reference
Evron et al.
2023
exp
4m 4m||w |I | R2
Evron et al.
2025
VT
VT
This paper (2025)
Continual binary classification 2 2 jointly separable tasks [e.g.. Evron et al. 2025 2023). where task j is specified by dataset
is setting of continual learning where the goal learn across
Sj = ((x1) y0))
(0) e Rdd y0) (-1,+1).
and there exists a common separator x* satisfying (2(0, for every example in every task. At each iteration, the learner updates its weight vector by minimizing classification loss on the current task. Concretely, the procedure is:
Algorithm Regularized Continual Classification
Initialize x = O.
For each iteration I....,T: Sample a dataset S, uniformly from [ (with or without replacement).
Σ e-xx'2 ||x x
X1+1 arg min
xaRd (2,y)eS,
Output X7
The performance the algorithm is measured by its forgetting, defined as,
I |xt (x))l
F+(xT)
Σ
2T
We get the following result,
Corollary Under a random ordering, with or without replacement, over m jointly separable tasks, the expected forgetting of the weakly-regulariee Algorithm (at - 0) after T 2 literations is bounded as
18| 11
E. [-[[+xx)]]
VT
As discussed in Exron al. [2023), when the magnitude of the regularization goes to this setting can be reduced for the setting of projections convex sets, which is detailed below.
14

---

Projection Onto Convex Sets (POCS) is method for solving feasibility problem defined by m closed convex sets ر (e.g Boyd 1m
2003 Gubin 1967]). At each iteration r I.....T.
we sample one constraint set index T(7) Unif( mm) (with or without replacement) and project the
current iterate X, onto the set C, (1). Namely,
Algorithm 2 Projections onto Convex Sets (POCS)
Initialize: X1
2: For/= I to 7:
3: Sample r(7) Unif( [m]).
4: - (x, a arg min xeCro)) ||x - xell
5: Xr
We assume 0fm1 Cj * (i.e. joint realizability), and measure performance by the average distance to projections on all sets:
1
F(WT)=
1WT (1
2m f=l
Using the reduction from SGD last-iterate bounds to sequential projections developed in Evron et al. [2025]. can plug in Theorem | and get the following results for continual linear classification and POCS,
Corollary Consider m arbitrary (nonempty) closed convex sets Ct...., Cms initial point w1 Rd and assume nonemply intersection Mj= Cj + Ø. Then, under random ordering with without replacement, Algorithm
7 (and Algorithm achieves,
& 7 min ||x] - x11?. VT xccc,
E
ww - 11
2m
f=1
The result given in Corollary 7 improves the best known parameter- inn.teeerr-iddeedednet rates for the loss continual linear classification and POCS method from Evron et al. [2025). (see Table ()) The proof builds results for with and withouttreplacemmett SGD in the realizable setting (Theorems) [ 3). combined with the reductions introduced by Evron et al. [2025] 2023 which relates last-iterate guarantees of SGD to performance guarantees in those regimes.
A.1 Proof of Corollary
In the proof, we use the following lemmas from Evron et al. [2025).
Lemma (Reduction in Evron et al. (2025)). Consider m arbitrary (nonempty) closed conver sets
CI...., Cm, initial point x1 E Rd, and ordering t. Define fi(x) = -11x - I1(x)11 vi e [m]. Then,
(i) fi convex and 1-smooth.
(i) The POCS update is equivalent an SGD step: X/+1 (x,) (x)r
Lemma 2 (From Proposition 17 in Evron et al. 2025 ). Under random ordering without replacement, the iterates of Algorithm (POCS) satisfy:
FF
7 E [F. (x,)
T-
Ir() E, (r,)) (xx))...
2T
Proof of Corollary 7 Let r be any random ordering, Rd initialization, and X1, .I, be the corresponding iterates produced by Algorithm By Lemmal [ these are exactly the SGD iterates produced when initializing xı and using step size of n 1, on the 1-smooth loss sequence (r()...., defined by:
1 -1--11))111
fi(x =
15

---

Since fi is convex and 1-smooth, we can apply Theorem for 17 1 and get, for the with-replacement case,
FFF(xT) & min |x - x*1
VT x
where the minimum is since Theorem D is valid for any x* E n C. For the without replacement case, by combining Theorem and Lemma
7
E,F(x)
min ||x - x²1
vT x
A.2 Proof of Corollary 6
In the proof, we use the following lemma from Evron et al. 2025
Lemma (Lemma 38 in Evron et al. 2025)) ) Consider SGD with step size nj S 2/B. For all $ T, the following holds:
EF, s 2EF((T) 4B2n||xx 11
T
Proof of Corollary 0 For the with-replacement case, the proof is implied by Corollary 7 and
Lemma For the without replacement, the proof is implied by Corollary and Theorem
B Average-iterate convergence of SGD in the low-noise regime
In this section provide average-iterate convergence guarantee for SGD with fixed stepsize, supporting any stepsize 7 < 2/B, and in particular, = 1/B. The original analysis in this setting due Srebro et al. [2100) only allowed for stepsizes 1) 1/8; more recently, more refined analysis was provided by Cortild et al. [2025] that supported large stepsizes 1/B S r < 2/B, but at the price of a bias term that grows exponentially with 7 when 1/B.
Theorem 8. Let f: Rd x Z - R be such that f(-:2) is B-smooth and corvex for every 2. Z distribution over Z, and denote F(x) Ex-zf(x; Assume there exists a minimizer x* arg min F Fxx), and that of EE--ZIVV((x
< co. Then, for T-steps SGD initialized at
xx e Rd with step size n 2/B. it holds that
E[F(X) F(x*)] = 2||x1 x=1
8no
(2 - BT)nTT (2- 2
where x = ET. X,, In particular, when 17 mint Br V4o27
| }.
E[F(X) - F(x))] 2,811,1 - 11
8||i| x 110+
T
vT
Proof. We begin with standard regret analysis. As Xr41 = - fxxx). ||x+1 xx 112 ||x, x+ 11 -
Rearranging, and summing for / I.....T,
Σ (ff(()). - ||x| x+1 2 1|
-x1112
17 r 2 1=1
Σ
V (1
20
Taking expectation and removing the ||XT4] xx112 term.
x -x, ||xi - x11
T Σ
"
(l)
2n
2 -
16

---

By Young's s inequality, for any A > 0
[+ & -
standard property of convex and B-smooth function le.g.. Nesterov 1998 is that for any
x, E R
B [lV((x) vh(y)l (Vh(2) v1())x->)-
Thus,
[v) B(1 + ))(V((())) V,(x*),, -x²) + 1/10)
(7)
Taking expectation and noting that since xx a minimizer of F(x), EV (x*) =0,
(x,,)l B(1 V)
(1+ 1/2)
Plugging back to the regret analysis and rearranging,
(1
Br( +
2)
Σ
T
x
-
||.1 - 1x
+ 171 + 1/2)
Σ
T
Eli EI
2
2m
2
T=1
Setting A and noting that (x
2-81 261
_ (2 (2 Br) Σ E(VA(s).,;x'))
||x|- - 11
2+
T.
(8)
2nj
2(2 BB))
Thus, by a standard application of convexity and Jensen's inequality,
E[ F(x*)] < 2||x| x 12
2(2 (1)
(2 (2-Br)2 no s 21|x] - x11
8n
(2 - BT) +
(2 - BTDNUT
(2 - B1))
In particular, setting 17 min(
1x1-x"11 ).
Ba V
2B - x=1
8||21 - x 10
([F -
T
C Last-iterate convergence of SGD in the strongly convex case
Here we show, for completeness, that in the fow-noise strongly convex case, the last iterate of SGD converges at a linear rate for any stepsize 0 17 2/B. Early results [Needell et 2014] achieved convergence only for stepsizes !) < 1/8, and in particular, did not explicitly give bounds for the greedy choice 7 = 1/B. Cortild al. (2025) has recently provided rates for any 0 < n 2/B. under the stronger assumption that f(,, z) strongly convex for (almost) all rather than in expectation. We remark that achieving last-iterate bounds (as opposed
-errage bounds) in the strongly convex case is entirely standard, and the only challenge here is to do while accommodating large stepsizes.
Theorem 9. Let Rd x Z R be such that f(;;2) is convex and B-smooth for every z, let Z distribution over Z, and denote F(x) = (=-zz((x;z) Assume that is a-strongly convex, minimized at x* = arrg minxeRd F(x), and that 2 = ( z)ll < co. Then, for T-step SGD initialized at Xı Rd with stepsize 0 < < 2/B. it holds that
8n0
El[XT=1 - 1 s expl -xp 18)
x+11
a(2 - n1)
In particular:
(i) for the greedy stepsize = 1/B, we obtain:
aT
802
17+1 11 s exp
||x] - x* x1
2B
aB
17

---

(ii) when o = 0 (the interpolation regime), the bound is convergent for any 0 < nf < 211B and optimized when 1j = 1/B.
Proof. We follow the standard analysis of SGD: since X,+1 =x-=(())(((x)))
|eeet -I+1|==== = ||x, x= ( ( -1
Using Eq. 7 we can bound, for any p > 1,
|| x=11 ||x,, x* () -
(B(V - -V xx)+ - [V p-
Taking expectations, we obtain
E||x++11 - -x*1| & El|x, - x11 2 xx
- + + -
P P0²
p p-
E|j,, x=12 - - -
p- _110
17202
On the other hand, since F is a-strongly convex, we have [V -xx) 2 al|xx, x 11
We then
obtain, whenever 2 png 0, that
E| E| xx1 s (1 (2 pnB) x=1
p p-1
Now set 1/(1B) 1/2 for which < 2/ (11B) required, as < 1 2/B. We obtain
2 n/ 11 202
(1- E| E||x,11 - -x11 < (1- - m2 - nB) ) - x=1 + 2- 2-n
Unfolding the recursion results with
E||xT+1- -x 12= s (1 fn - (2)))= (18))/11x) - 417202 20
Σ
m2 - -n1))²
2 nB 1=0
8no a(2 njss
s expl- - -
11 11
D Simpler last-iterate analysis for small stepsizes
Here we present an alternative analysis technique for the last-iterate convergence of SGD in the low-noise regime with small stepsizes 17 < 1/B, that in particular recovers the near-optimal rates in the regime y s 1/BB log established in Theorem 2 The proof technique builds upon the earlier last-iterate approach of Shamir and Zhang (2013) and provides for a considerably simpler analysis; however, for large stepsizes (i.e.,) 17 = 2 ((1)))), yields inferior convergence rates as compared the more intricate analysis of Theorem 2
Theorem 10. Let f: Rd x Z - R be such that f(;zz) is B-smooth and convex for every Assume there exists a minimizer x* arg min F(x), and that 02 co. Then, for T-steps SGD initialized we have the following last iterate guarantee:
at X1 Rd with step size 0 17 1/8, where
16|| - 1
64n
E[F(XT) - F(x))
o 2 (2-(2-188p InT.
(2111(2-811p)
1-nB
In particular, when min (1/(Bln(T)) ||a x oo
14481n(7)lxa
720 [| x (|v/nn(T)
[[F(x)) - F(x)}
vT
18

---

Note that the bound above becomes non-convergent as m/B - 1, as opposed to the bound in Theorem 2 and in the interpolation regime it is dominated by the latter: e.g., for 17 = 1/(2)) the bound above yields rate 7 compared to the T-4 rate in Theorem 2
Proof. Let y E Rd, Since (x,,, - >) 2 f1xx;) - -y)) and, by Young's inequality, for every A > 0, it holds that (x, s
(1+ 1/x0lVV
||x+=1 - y11 = ||x; - -
< ||x, yl1 - (x)(f( - + (1+ (1++))) Vf((" 1+ 1 1f f(
2
Taking expectation and noting that f/ V/60 1 2 - fx(x we get
E| El|x,+1 y11 < El|xx - 2 (x,, f((0) + (1+2) - (1+ no
-
=E||x, - y11 21 (1 1) -
+ +2(1 + 1) - -((xx) + 1 2 0²
where of = (x: =) Summing for 1 = T- - -k.....T
Σ (lf
E| > s El|xy- y11 0 2n711 - (1+1) BT)
1=
1
+ +11 + 2)Bn
E(f(r) fi(x*] [
=
17 + 1).2
d
f=T-k
Setting y = wr-k and rearranging, we obtain, since (x((x=+)) = f for 1 2 T - k.
T
(1 - (1 1))
Σ
E[F(x)) - F(x)) s (k + ()E[ -
+ 2 |+ 17( + 1)
1=T
Now, denoting Sn 1)S² - KSL-1,
उ+ - E(F(x)) - F(x*)] and noticing that E(F(xT-1) F(x))] = (k
I Σ
|+ 1 2 no?
(1 (1- (1+ 1)mB) Sx s (k 1)5x 1-
+ 2
Rearranging,
S S |+ (1+ 2)
( |+ 1 2 0z.
Sk + 2k
k
Unfolding the recursion and setting d ==1
1-
n18. we obtain
(1 11n
17
(1 +1)B
So s ST
2
k=l
[T-1
(1 + +))n
T-1
(1 (1+1)8n)
< -ST-1exp
2
1+
2
cxp
k
A=1
1
S ST exp((1 + A)Bn
In(eT))
2/2
|+
0,
+ (0(1
k
ST +
1+ d
o In(eT)
2
$
Sr-1 +1
0f In(eT)
(e7)
(1 1 - nBnnB < 1)
1 nB
19

---

where the third and fourth inequalities follow by Ei=n I 1 In(N) In(eN). By applying convexity and using the average- convergence rate Eq. we know that
Σ E[F(x,) -F(x)] - 7 (2-Bm) x( ST T
2||x1 - 11
2(2+ (n)
2||x1 - 11
110 1
+
6n
117
2- Bm
1/
where the first and last inequalities use 1j - 1/B. Then, we get
2||x| - xx
E[F(xT) F(x))] So s
6no + 1 I- nB
0 In(eT) (eT)
1/
1/ (2- 22n1/ + 64n o In (2(7)) 1818
16|[xr - x=1
1-nB
In partieular, when 77 min (1/(BI(TT), 11 In()).
EF - F(x*) N (nT)ll - 720 ||x1 x ll (n(T)
E Multiple minimizers in the low-noise regime
In this section we show that assuming f(::z) convex and smooth for any 2 Z, the variance at the optimum x* arg yi F(x) (assuming one exists) is the same, no matter which optimum is selected. Following
result.
Theorem 11. Let f: d x 7. - RR be such that f(=:z) is B-smooth and convex for every and Z be a distribution over Z. Assume there exists a minimizer x² arg minyead F(x) fx; 2). and that E f
co. Then for any x E arg min F(x),
E
E Z
Proof. A standard property of convex and ß-smooth function h [e.g.. Nesterov 1998 is that for any x, E IR.".
[Vh(+) vh())1 -h()))
Thus,
- -
= (VF((x)) xx5) =0.
where the last equality follows since x are minimizers of F(x). The random variable |V =x is therefore non-negative and has expectation zero, implying that =f(x;==) = Vf(x;zz) almost surely and thus concluding our proof.
Technical lemmas
Lemma 4. Let (0, 1), and E N. Then
1 (n+c) (1+c) 10+ S 1-a
Proof. As (u + c)-a monotonically decreasing, bounding by integration,
(1++))a ΣS" (m+c)= du ('" (u+c)-add -d 1
I-a ( (n+tcll-a -dd-o)
We conclude by noting that for 1 and (0. 1), cl 8010/1(111 a) a (1+c)-
20

---

Lemma 5. Letx 2 1 and a E (0, 1). Then
- (x+ 2
x(x 1)a²
Proof. The inequality follows directly from Bernoulli's inequality, (1 xx) & + for E [0, 1J and x 2 -1. Using the inequality,
+rx rx, which holds
x - (x+ (x+ 1)-0
(1 [1
1 x
-1)
a
x(x+ + 1)
G Proofs of Section 2
In this section we give formal proofs of Theorems and
G.1 Regret analysis for stochastic convex smooth optimization
We first present a key lemma, which may be of independent interest. The lemma establish a regret bound, which is improved version of Lemma 2.1 Zamanii and Glineur [003], , specialized for stochastic optimization with smooth objectives. The result holds in general setting that accommo- dates both with-replacement and withouf-replacemennn sampling schemes, under unified sampling assumption stated in the lemma.
Lemma 6. Let f: Rd - R be such that f(::z) is B-smooth and convex for every z. Further, let Zl.....21 2T ZT) where Z(T) is distribution over Z" that satisfies the following: for any S t. conditioned on 21..... 2x-1, holds that 2, and 2 are identically distributed. Then for any x* Rdd
and any weight sequence 0 < VO I V1 S ... S running SGD with initialization
Rd and
stepsize sequence M71 1T
== 1, I....,T T Xy+1 = X2 - n: fx()), where fi = f(;z)),
it holds that
I
C E(f((x)) - f((5)s 2 2/lllx - 1x11
Σ
n (
T
(vx - V.- Σ
V1
2B
1=1
5=1
where c == 12 (V, - 11-1) Ete V.
Proof. Define yI...., yr recursively by =o= x* and for / 1:
Vr-1 V,
F1-1 (1- Vr-1
y,
xr.
V1
Observe that:
v?
|| 11+1
||x++1 yrl12
||x, 17, fx(x)x - -yll
2
7+]
i+1
2
(Ilx, y211 27, (V -
Thus, by rearranging, obtain
1 n f
n (Vf((x))x,, - y,) Summing over = 1....,T yields
= -r.llx, yr112 - "/ yrmull +
T
n (V - -rd 2 vollxr - 1x=1 Σ 1=1
Σ 1=1
m 2
(9)
21

---

where we used that
vo
vo V1
|| yill
V1 yoll = ||]
||-]
x=1
On the other hand, yr can be written directly as a convex combination of ,7. and x², as follows:
VO
Vx Vs-1
Y/
Ns.
Vf
Using a standard property of convex and smooth functions [e.g..
Nesterov 1998 for any x Rd
(V - x) 2 fx(x)) - fi(x) + - -Vf(())
1
2B
Hence, as V, 2 Vs-1+
xx Σ Vss V--1 x, VO (V
V1
Vs Vx-1 (x(x)) - -f((x) 1
[x)(xx)) vf((x,)11)
V1
2B
Vo
1 [V,)((;,)) vf((++))1
fi(x)) - f((x*) +
V/
2B
= fi(x)) Σ V---sin - Vs-1
-v-1 f((x,)
vn fi(x*) +
1
Vs Vs-1 (V((z) V)((,))11
V2
V
2/3
V1
vo [V,( (1
2BV,
Multiplying by nu? and plugging back to Eq. 99)
2 Volle - 1x=11= +
2
Σ
T
n. f
2
Σ noy
T
(x
Σ (v..v,,)).f.c.) - voll((t))
1=1
s=1
Σ V/
Σ
+
(vs v. (
2B
1=1
s=1
7
Σ
nrV ( ff(x))
Σ (v. (1--s)))(((ss))1((
1=1
\(.-v))1/A v((x,))11 + vollV -
V
2B
Taking expectation, noting that for all / 2 s. Effxx)) f((x==x+==++--)+)) =ff - fx*) (since fr, fo are identically distributed condition on X, and x fixed), and rearranging the terms,
T m. ?
2 E( - (6007) n.
2 Falla - x+11
Σ T=1
(v, - -v--v
Σ
us
2
x=1
Σ (v.- (
- (oE -V T.COSPP)
1 t=1
2B
We conclude by rearranging the terms and plugging Cr-
G.2 Proof of Theorem I
We now give the formal proof of Theorem In addition to Lemma 6 we will use the following lemma, which handles the cross terms (x)V)((x,) - f((xx)) which are introduced by the regret
bound of Lemma 6 See Appendix G.4 for the proof.
22

---

Lemma 7. Let f: R x Z - RR be such that f(::2) is B-smooth and convex for every z. Further, let Z1......2. 2T Z(T) where Z(T) is distribution over Z" that satisfies the following: for any $ t, conditioned on ....... 2s-1, it holds that and are identically distributed, Let (0, (), let V, ( - for any E [ 1], and let vr V1-1. Then for any x* Rd, running SGD with initialization X1 Rd and stepsize sequence I!..... > O,
I=
Xrt1 = 11r (x+), where ft = f(iz)),
holds that
[=1
S=1
(1-220))(EIV(((()))77>})) Σ (1-4)),+++
Σ Vi V/
We proceed prove Theorem
!
Proof of Theorem 1 Let a (0, f). v, (T- for [T- 1]. Vr VT-1. and denote
(x) == fx(x - (V fxx)),x) such that (x) (x) (x*)x) By Lemma with fixed stepsize
M). 1 and weights
vy, which is applicable under with-replacement sampling,
2 2ollee -x*11
Σ 1 )
Σ ((f(()) fx(xx)
nv (u, v2-1) Σ nqvs
T 2B
Vvs v, [v))) Vf v
+
1
s=1
where substituted (x,) Vf((z,)) - (x,) Dividing by 17. plugging vy VT-1. and denoting a, =V,, - 1111) Σx= Vs.
I
0 |||| - x11
7 Σ
o fi
- - + Σ E(f((,) -(()))) ar)
217
T
1
V1 Σ (vs --- P-- EII
2B
The technical Lemmas 4 and 5 which are proved in Appendix state that for any c 2 1, a E (0, I),
and n E N, it holds that (1 c) + Σn (i c) I - (n ())++=+ 1) and that for any x 2 1, and (0, 1), it holds that
1) x(x+laa Using these, for T,
a
a 2
4t TT -- (T 3 -T-
where used the fact that (0. Hence, apply the standard inequality for convex smooth functions [c.g., Nesterov 1998). (x) fx s 2x(f((x) - (x*))x).xx -x*)),
and after taking expectation and substituting (x,) Vf(x) (f((x) for any [7].
((x))) = 28E(()(x)) - f((x*) -v)))(((==) -x))] 2,(
- f((*)), (10)
where we used that fi independent of x, and is minimizer of F(x), obtaining that
T
T-1
||-|
7 x 11 +
-
Σ
EE (x)) - -+()))
ENVA()) -a))
21
2 1=1
2B 1=1
Σ
+
(v. V.-
2B
1=1
1=1
23

---

Plugging Lemma 7 (and substituting - -
0 ||
x x²11²
+ !
EEIV (X) 2 (x)( (r('))
211
2 ==1
2 1=1
Σ
T
(1
(11
(1- (r- (v,-v,11 Σ
(v,
2B
Rearranging the terms and using the definition of a₁
V |a +1+++
T-1 (x))1
Σ
Σ
(1 20 v ,
&
2n
ra1
r-1
222 - 2c)) fz
TT
2B
By Eq.
10). - ((T) fr(xx)] - EIi EI (xT)))
1-20
Adding to the above display,
20v (x))))
|x| - -x+
Σ
f()))
2n7
1=1
(11)
Σ (1 - 2
7=1
As As E arg min f(x;z) for every 6 Z, (x,,x, = fx(xx,, and by setting a --1 E (0. 4)
- Bn (() [x(x)] < y ||-1 x11
2
2n
Substituting vo (f and vy = = 3- and rearranging.
320 - x111
Elfr(xT) - fr(())] -
17(2 (T) + 2)22a
Hence, substituting a 2-8n and since 2a s
3||x| - 11
31 - 11
Elfr(xT) fr(x*) s
17(2 - (T) 2) 1-1-12 5
(12)
11(2 11
We conclude by noting that ([fr(x)) ((F()) F(x*)].
G.3 Proof of Theorem
Note that Lemmas 6 and used prove Theorem | hold without the assumption that x* is the
minimizer of each function. Hence, the argument in the proof of Theorem I up to the point of Eq. (11 applicable in the setting Theorem 2 showing that
0
||] x1
Σ v {
27
(13)
Σ (1 (
Let 2a fg 0, restricting a (2- (m) /4. By Young's inequality,
EIVV
2c (1+
(1
B1
EIIV
El|
Bn
2e
24

---

Thus, as E 1 22 Bn
2 for any E [T].
4 (( 2:2
2c
(x) + |+ Bn
El EIV
|+
Bn
2e
v 2 4a
V (x,) + 7/ By
Bn
2c
(1 - 2 + [ + B7
VE fxx*))
2B
2
Plugging back to Eq.
13 and substituting E[fr(xT) - fr((*] = Elʃ(xT) f(x)),
0 4rj
[x| x 2 1+
B1
2E
0
x 1| + 7
Bn
|x|
0
V
41
2
where the last equality follows from ( = E.-zIIV/(xx:2)) = o². Lemma which
is proved in Appendix [. state that for any c 2 1, (0, 1), and N, it holds that (1 c)
>1 (i (i+e) () z T-a cn+ 1-a 1- Hence,
7 Σ
V S
(T 12
(T 12
1- 20
2a
1=1
Thus,
11
An 2e
2T 2) 1-2
12
([F()( =((*)]
[x]
+11
4n
4(1 22x
Substituting Vy = 2 1/v3 (since ) (T 2) a and 2-Bn-2e and rearranging, 4
31|x1 - -x*112
3T + 2) Dn +c
E[F(xT) - F(x*)] 1
(2- 22) 2) 1-1--1- (2- Bn 22)E
Now set a 2-Bn 2-8y (T+2
2-Bn E (0, 1) for which 2 (T+2) and note that (T + 2) z
4-
(T (T+) 2 and (2 - Bn 22e 2-Bn T 2. Thus,
E[F(x)) - F(x*)] 5 12 - 12
24n (T 2) 8y log, (T +
112 Bn) (T 2)
(2 Bn)
x2||x: - 11
48no 8n log +)
11(2 B1)T m7
(2 Br)
where that last inequality follows by T 2 2 and Bn
2. The second claim, for when
|x x
min (T)
(as logg(T) 2 I since T 2 2)
T. To +2)
B
follows by noting that TBn/2 < (/2logg = V2 < 2, so that
12||x 1
E(F(x)) - F(x*)) S
48no 2h
logo + 2)
1/7" 4g
24 x x+1 log (T)
120G, |x
xx 1 11
VT
25

---

Vvs V - 7tl.a/17771.7100.1.1-11.0i7-i---
G.4 Proof of Lemma] 7
Let fi(x) = f((x) - (V 1 and note that Vx(x) Hence, as
it holds that
- -
V1
-
(14)
(EW- ((G)))
[=1
Next, we will focus on the summations of (x)) (x,)))) Rearranging,
vr(rs v.--- (..
Σ
vr(vs -.---
r=1
sa1 7
- Vf(x))
where the last incquality follows by VT = 17 For / E [T] and s E [T - 1], let
A (TT -+ 1) 0.5 -T- 2) -.5)
V,
(T (1-1+ 1) 0.5
Vs3 V--1
where 0 will be determined later. Noting that v, V--1 and using Young's 's inequality,
T vr(v, - V. =
T-1
G
vy(v, - -v-iii 21
(15)
1
s=1
where G (x,)), such that &² Ex,V1 EIIV (1,,))1 for s S 1, Sr and f, are
identically distributed conditioned on X5. Denoting NG,7 = O,
T
T
Pr(v, v,-1) G
Σ
Vr - V,- 11. G3
Σ
Pr(Vs- -vs-1)
x=1
[=1 s=1
(T - 11 1)
Σ
(TT st 1) 0.5 (T - (5+++2) 2)+
s
c
T=l
5=1
$ c
1=1
(16)
and
T-1 T
6² T-1
(v, - vy-1)2
Σ
Σ
vv vv-1)
62
(T - 1 ++ 1) 0.5
4
(T- -.55
0.5 (T (T-S5 S -.0
0.5
s=1 1wg
s=l
t
2
(v3 122
0.5 (T- 5 1)50,5 (T 8 2) 0.5 62 + 1)0.5
03(y, -2-1)) (T- () 5 2).
(T- (T- - - -T-s+ 1)0.5
T-1
O.(v, - Vs- ( s s+ ( s s+ + (T - s + 1).5)
s=l
s=1
26

---

and where we bounded
r 11 Σ
T-1 1++
[ ( 11 -05
Σ (T (T-
(I (I-
$ 27 - s 1)0.
Note that by Lemma
a²v2 5-1 (T- 2)
(V's (Vs-V=-1)2
a
(T- 2) -++33
Thus.
Σ
vv 1--
G
4a
T-1
4a T-1
Σ
G2
(v' 2 2s-1)
At,s
s
5-1
sml
sml
sml
Together with Eq. (16), plugging to Eq.
15
and setting c 2a,
T-1
Σ
vr(v, E.V s 07 + Σ
2
t= s=l
1=
Returning to Eq.
14
Uss - V.(())11 vo (oE
Vi
[=1
s=l
V.G. + Σ (v. - vv--)=-))03
22
Σ G2. 1=1
where we used the fact that EIJV distributed conditioned on x, (which implies that fr. and fa are identically distributed conditioned in xy). Rearranging the terms,
E G3 for s S r as fr and fs are identically
(vs Vs- -. V
Vr
(1 v Gz
Σ (1 4m) (v, V₁-1)
Gr
Vs
where again we used the fact that vy vy-1- We conclude by substituting = fx(x) = (f(x))
H Proofs of Section 3.1
H.1 Proof of Theorem
The proof is based on the following two lemmas. The first is a convergence bound for E(fr(xT) fr(x)),, which is an extension of Theorem to SGD with sampling without replacement. Note that (xT( not equal (x)(x)) (in general) when sampling without replacement due to the correlations between fr and X7-
Lemma 8. Let f: Rdd x - R be such that f(::2) is B-smooth and convex for every z. Assume Z(T) is distribution over ZT that satisfies the following: For Zi....,27 ZT Z(T), conditioned on Zh.... Iz-b, Is for S I it holds that zs and 2, are identically distributed. Assume there exists joint minimizer x* E ZZ arg min fx: 2). Then, for SGD on Zi...., (T) initialized at e Rdd with step size n 2/B:
== 1 T: Neal =X, f, where fr = f(:2),
27

---

where T 2 2, we have the following last iterate guarantee:
3|121 - 1x
- -
112 B1))
301|*|=**11" vT
In particular, when
- - 5
The second is without-replacemmnt generalization upper bound in the smooth realizable setting established in Lemma 34 of Evron et al. [2025).
Lemma 9 (Evron et al. (2025). ). For aethout-replacement SGD Eq. 4 with step size n s 2/B. for all
S T $ n, we have that the following holds:
Σ 1=1
1/2 1x
E
f(x [x)] ((T:A)) [x)=;,)) (Ex[ -(=
T
T
We note that the above statement is minor adjustment of the original one, and follows from the last line the proof given by Evron et al. 2025
Proof of Theorem 3
By Lemma 9 have for all T
EFz(XT)
(x
T-1
I-
f(x;; - ff(x;
--I++E [((x):T)) - f(x:;a))
n
T-1
E
(xT: f(xx; + (rx)
7-1
3E [(x);a)) ;(x+=x))) 4121||x1 -
1+1
T
Now, since π is uniformly random permutation, ......, By satisfy that conditioned on Ti... .,.....,................ we have that n, n, are identically distributed for s r, as both are uniform over Z {2i,.... 25-13 Hence Lemma applies, and we have the that,
311x1 x11
E[f(xT:
:)) S
1/2 BT) 22
Combining both upper bounds, the result follows.
H.2
Proof of Lemma 8
The proof is identical to the proof of Theorem beside the following points:
Lemmas and are applicd under the general sampling scheme of Lemma g which the
same sampling scheme of Lemmas 6 and instead of under the with-replacement sampling assumption of Theorem L
2.
The bound E|I (x,, & (x) - f(x))], which is established in Eq. (10) using the with with-replacement assumption, established instead using the realizability assumption (under which V (x*) = 0) by the following argument,
= - (x) s 2FE(()(x,) f((x = 2xE(S((x,) fe(x
As the rest of the argument does not exploit the with-replacement assumption up to (and including) Eq. (12). Eq. (12) holds and
(lfr - (x*)] 3||x1 1
11(2 BT) 00
1-
The second inequality follows immediately by setting 77 1
28

---

I Proofs of Sections 3.2 and 3.3
L.1 Lemmas from Evron et al. 2025
The proofs in this section use the following lemmas from Evron et al. [2025].
Lemma 10 (Analogous to Reduction 2 in Evron et al.
[225 1) In the realizable case, under any
ordering T, the block Kaczmarz method is equivalent to SGD with a step size of = c, applied w.r..
convex, 1-smooth least squares objective: (x) & (Axx))xbb
That is, the iterates
. XT of Eg. and SGD with slep-size
coincide.
Lemma 11 (Lemma 6 in Evron et al. 2025 ). Consider any realizable task collection such that Axx* = b; for all E [m]. Define fi(x) A b,)ll. Then, Vi [m],x E Rd
(i) Upper bound: A1l b,1l f(x).
(i) Gradient:
V fx)i A Aiw Aib.
(iii) Convexity and Smoothness: fi is convex and 1-smooth.
1.2 Proof of Corollary 4
Now, turn to the proof of Corollary 4
Proof of Corollary 4 First, for the with-replacement setting, let r a random with-replacement ordering, and let ... denote the iterates generated by Eq. ( By Lemma [0] these iterates
coincide with those of SGD initialized at w1, using step size 1j = c, on the sequence of loss functions fr()..... where
fi(x) = -1
Moreover, by Lemmal
11 for any Rd. F satisfies:
F(x) R² (m)
Thus, it suffices analyze last-iterate convergence of with-replacement SGD on F. Again by Lemma IT each fi is 1-smooth. so we may invoke Theorem T gradient steps with step size 1) c, it holds that,
| This theorem guarantees that after
311x1 - -x*1 x111
E [m)) fx())
1711-187
Combining this with the earlier inequality yields:
3R 11*
FFF(x)) S 1)
For the wiihout--relaccmmen case, the proof is analogous and obtained by using Theorem instead of Theorem [ (the constant in the bound will be 13 instead of 3).
I.3 Proof of Corollary 5
We use the following lemma from Evron et al. 22025]
Lemma 12 (Reduction in Evron et al. (0055) In the realizable case, under any ordering T, continual linear regression learned convergence equivalent the block Kaczmarz, method with
= 1. That is, the iterates XI, of Eqs. (5) and (6 coincide.
Now, we can turn the proof of Corollary We prove for xy and the bounds for X7+1 can be obtained by another sampling from the distribution.

---

Proof of Corollary 5 By Lemma 12 for 1, the iterates of Eqs. and (6) concide. Then, by we get that in both regimes, with and without replacement, it holds that,
Corollary
13 VT
FxT() &
For the forgetting, in the with-replacement case, by Lemma we get that,
ErF+(xT) 30R | II
VT
In the without-replacement case, by Lemmas 8
and get that,
10R² ||x ||
E,Fr(xT) 5
VT
30

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
The abstract and introduction highlight the main contributions of the paper, including the improved convergence rate for the last iterate of SGD in the interpolation and low-noise regimes, as well as extensions and applications to other settings. The claims match the theoretical results established in the paper.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The paper is theoretical and in sections 1-2 we discuss the assumptions that we make and their significance.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
31

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We provide complete and correct proofs for all the results presented. Ad- ditionally, the assumptions used in each proof are explicitly stated in the corresponding theorem.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [NA]
Justification: The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access hosted model (e.g.. in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
32

---

5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https for more details.
7 //nips. hwcp//blccggudeeeeeeeeeeee/eeeee
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
33

---

The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (c.g. negative emror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics Sthics/https://
Answer: [Yes]
Justification: The paper is theoretical and conforms with the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is no socictal impact of the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
34

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
35

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
36

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: This research does not involve LLMs any important, original, non- standard components.
Guidelines:
The answer NA means that the method development in this research does involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy for what should or should be described.
37


Reviews:
[{"review_id": "KIMIA7i0Bq", "reviewer": "Reviewer_54Za", "summary": "This paper provides a significantly improved last-iterate convergence analysis of SGD for smooth, convex functions in the interpolation and low noise regimes. This is the first result showing a $1/T$ last-iterate rate in the interpolation regime (previous results had achieved this rate only for ordinary least squares), and this is the first result showing a $1/\\sqrt{T}$ last-iterate rate with a greedy stepsize $\\eta = 1/\\beta$ (where $\\beta$ is the smoothness constant), where previous work had shown a $1/T^{1/4}$ rate and only for ordinary least squares.", "questions": "1. Can you explain what exactly is the low-noise regime? The introduction (line 62) says that $\\sigma_* \\ll 1$, but the statement of Theorem 2 only requires that $\\sigma_* < \\infty$. Assuming that low-noise refers to $\\sigma_* < \\infty$, why call this low-noise? Bounded variance (or bounded variance at optimum) is a common assumption in optimization, but is this condition often referred to as low-noise?\n2. Liu and Zhou [22] have results for both in-expectation and high-probability. Do you think your techniques can be easily extended to allow for high-probability guarantees, assuming say sub-gaussian noise as they do?", "limitations": "Yes", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. This is an important problem: the last-iterate convergence of SGD (especially under interpolation) is fundamental for optimization with clear motivation for machine learning.\n2. The improvement over previous work is clear. Better rates are established and in more general settings (see Table 1).\n3. The paper is very well-written and clearly communicates the novelty in the analysis compared to previous work. I think the proof outline and proof itself (sections 3.1 and 3.2) are informative and transparent about the ideas.\n\nWeaknesses:\n1. The $1/T^{1/4}$ rate for greedy stepsize with interpolation does not match lower bounds ($1/T$) or upper bounds for the average iterate ($1/T$), though I think this is fine. The authors acknowledge this gap as an open problem (line 77) and I think this is gap is totally reasonable: you can't solve everything in one paper.", "was_revised": true, "final_justification": "After my initial review, I did not have any major concerns about the paper, just a few small questions which the authors answered with the rebuttal. I believe that this is a strong theoretical work, clearly worthy of publication.", "rebuttal": "Thank you for reviewing our work and providing us with your strong support. It is highly appreciated and encouraging. Please see below our responses to the points you raised. \n\n> “Can you explain what exactly is the low-noise regime? The introduction (line 62) says that $\\sigma_\\star \\ll 1$, but the statement of Theorem 2 only requires that $\\sigma_\\star < \\infty$. … Bounded variance (or bounded variance at optimum) is a common assumption in optimization, but is this condition often referred to as low-noise?”\n\nYou are correct to note that our results only require an assumption of bounded variance at the optimum, leading to a rate of $\\widetilde{O}(1/T + \\sigma_\\star / \\sqrt{T})$ for an optimally tuned stepsize. The term “low-noise” in this context (originally coined by Srebro et al (2010), to our knowledge) refers to cases where $\\sigma_\\star = o(1)$ (in terms of $T$), in which case a convergence rate strictly better than $1/\\sqrt{T}$ rate is possible. Thanks for this comment - we will try to make this terminology clearer in the final version.\n\n> “Liu and Zhou [22] have results for both in-expectation and high-probability. Do you think your techniques can be easily extended to allow for high-probability guarantees, assuming say sub-gaussian noise as they do?”\n\nThis is a very interesting question we have yet to thoroughly explore. While the results of Liu and Zhou [22] suggest that high-probability last-iterates bounds of this form are achievable, the interplay between the concentration and the weaker noise assumption (bounded variance at the optimum instead of a global variance bound) seems to lead to several technical challenges that we do not yet know how to circumvent."}, {"review_id": "jVBBoVzAxU", "reviewer": "Reviewer_ixqP", "summary": "The paper studies population convergence guarantees of stochastic gradient descent (SGD) for smooth convex objectives in the interpolation (low noise) regime.\n\n- The paper establishes a convergence rate of $\\widetilde{O}(1/(\\eta T^{1-\\beta\\eta/2}) + \\eta T^{\\beta\\eta/2}\\sigma_{\\star}^2)$ for the last iterate of SGD with step-size $\\eta \\leq 1 /\\beta$ on $\\beta$-smooth convex loss functions, where $\\sigma_{\\star}^2$ is the variance of the stochastic gradients at the optimum. With a well-tuned stepsize, this translates to a $\\widetilde{O}(1/T + \\sigma_{\\star}/\\sqrt{T})$ rate.\n\n- The paper further extends the analysis to without-replacement SGD, block Kaczmarz method, and continual linear regression, leading to some better convergence rates.", "questions": "- See the weakness part.\n- Is there any connections between the Zamani and Glineur technique with [1, Theorem 2]?\n- How can the result from Srebro et al. (2010), which uses an approximation error rather than $\\sigma^*$, be refined to obtain the error bound presented in Table 1.\n\n\n[1] Francesco Orabona. Last iterate of sgd converges (even in unbounded domains), 2020. URL\nhttps://parameterfree.com/2020/08/07/last-iterate-of-sgd-converges-even-in-unbounded-domains/.", "limitations": "probably yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- The paper derives a $\\widetilde{O}(1/T + \\sigma_{\\star}/\\sqrt{T})$ rate for the last iterate of SGD with a well tuned step-size on smooth convex loss functions. It improves previous result by replacing the global noise variance bound with the variance at the optimum, or under the same set-up, it extends convergence guarantees for averaged iterates  to the last iterate of SGD, matching (up to logarithmic factors) the optimal rates achieved by averaging.\n\n- The paper further extends the analysis to other settings.\n\n- The paper is in general clearly written.\n\n**Weakness**\n\n- I agree with that  deriving convergence results for the last iterate, rather than the averages, of SGD is interesting. Given that the connection between the last iterate and averages has been extensively explored in the literature, the contribution feels somewhat incremental to me.\n- Could the theoretical results of this paper offer practical insights into the numerical experiments? For instance, Theorem 1 suggests that the step-size in case (ii) should outperform the choice in (i). Is this actually observed in practical applications or numerical simulations?\n- While the paper focuses on the convex setting—a reasonable starting point for theoretical analysis—this is somewhat limiting given the prevalence and importance of nonconvex optimization in modern machine learning applications.\n-  As the authors acknowledge, when $\\eta = {1\\over \\beta}$, the convergence rate is $1/\\sqrt{T}$ in the interpolating regime, which falls short of the optimal $1/T$ rate achievable with averaged SGD.  Moreover, what is the theoretical motivation for considering this particular step-size setting?", "was_revised": true, "final_justification": "I keep my positive support.", "rebuttal": "Thank you for your thoughtful review—we hope that the below will successfully address all your concerns, in which case we hope you could acknowledge that by updating your score. If any concern still remains however, we will be glad to try and clarify further in the discussion.\n\n> “I agree with that deriving convergence results for the last iterate, rather than the averages, of SGD is interesting. Given that the connection between the last iterate and averages has been extensively explored in the literature, the contribution feels somewhat incremental to me.”\n\nWe actually believe the fact that a lot of effort has been put into last-iterate analyses over the past decade, while still leaving this fundamental gap open, only emphasizes the significance of our results. In addition, obtaining the new result required new technical innovations, as described in Section 3.1, beyond the techniques already explored in the literature.\n\n> “... Theorem 1 suggests that the step-size in case (ii) should outperform the choice in (i). Is this actually observed in practical applications or numerical simulations?”\n\nThe gap between cases (i) and (ii) is intriguing. From a theoretical perspective, it remains an open question whether this gap is real, as it is possible that case (i) already achieves the optimal $1/T$ rate. And in practice, even if the gap exists, observing it empirically would be challenging since the number of steps $T$ is usually fixed, making it difficult to distinguish between a $\\Theta(1/\\beta)$ stepsize and a $\\Theta(1/(\\beta\\log{T}))$ stepsize.\n\n> “While the paper focuses on the convex setting---a reasonable starting point for theoretical analysis---this is somewhat limiting given the prevalence and importance of nonconvex optimization in modern machine learning applications.”\n\nThe fundamental convex case is the focus of the extensive literature on last-iterate guarantees of SGD, and we have yet to reach a full understanding of convergence and rates even in this case. And indeed, the progress we made in the convex case already required nontrivial technical innovations that will likely be crucial for further advances.\n\nAs an aside, it is a folklore fact that meaningful last-iterate guarantees are generally not possible in the non-convex smooth setting, even without noise. (There are simple examples of smooth problems where the norm of the gradient actually increases with time, rather than decreases.)\n\n> “As the authors acknowledge, when $\\eta=\\frac{1}{\\beta}$, the convergence rate is $1/\\sqrt{T}$ in the interpolating regime, which falls short of the optimal $1/T$ rate achievable with averaged SGD. Moreover, what is the theoretical motivation for considering this particular step-size setting?”\n\nAs we explain in the paragraph starting at line 40 and elaborate in Section 5, the choice $\\eta=\\frac{1}{\\beta}$ is crucial in several applications of SGD related to continual learning and the Kaczmarz method, which were actually our main motivation for studying this problem. See Sections 5.2 and 5.3 for more details on these applications.\n\n> “Is there any connections between the Zamani and Glineur technique with [1, Theorem 2]?”\n\nTheorem 2 in [1] is based on the Shamir & Zhang analysis technique that, as we discuss in Section 3.1, was used in previous work that was only able to achieve a weaker $1/T^{1/4}$ rate for $\\eta=1/\\beta$, compared to the $1/\\sqrt{T}$ we establish here. \n\nThe Zamani and Glineur technique can be seen as an intricate adaptation of Shamir & Zhang, that instead of using the standard SGD potential analysis with relation to previous iterates of the algorithm, it uses such an analysis with respect to certain **convex combinations** of previous iterates. \n\n> “How can the result from Srebro et al. (2010), which uses an approximation error rather than $\\sigma_\\star$, be refined to obtain the error bound presented in Table 1.”\n\nIn Appendix I we provided the refined analysis you seem to allude to, which provides the error bound presented in Table 1. In addition, this analysis applies to a wider range of stepsizes (including $\\eta=\\frac{1}{\\beta}$) compared to the original analysis of Srebro et al. (2010)."}, {"review_id": "JVIZj0495O", "reviewer": "Reviewer_4zP2", "summary": "This paper studies the last-iterate convergence of SGD. For the general smooth convex setting with optimally tuned learning rates, it obtains an improved instance dependent bound which replaces the uniform noise bound in the previous work by the variance at optimum. This directly implies an improved bound for the realizable setting, that goes beyond the OLS regime. For the realizable setting with the greedy stepsize $1/\\beta$, it obtains a strictly improved convergence guarantee which has a faster rate and goes beyond OLS.", "questions": "I wonder if last-iterate convergence guarantees can be potentially obtained for the agnostic setting with the natural $\\eta=1/\\beta$ choice. If it's not theoretically impossible, what's the main technical difficulty?", "limitations": "Yes.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths:** studying the last-iterate convergence of SGD is an important problem both theoretically and practically. This paper provides solid advancement on this problem. The technical framework and novelty are well explained: the proof outline clearly describes the roadmap, making it easier for the readers to tell which parts (step 0,1,3) mostly follow from the literature and which (step 2,4,5) are novel technical contributions. In my opinion, the overall approach still lies in the classic framework, but the technical contributions are solid and necessary for obtaining the improved rates. Hence I recommend accept.\n\n**Weaknesses:** the improvement is mainly in the realizable setting with the greedy stepsize. For the general setting, the improvement is somewhat minor, but it's still a strict improvement since the algorithm requires no knowledge of the variance at optimum.", "was_revised": true, "final_justification": "Author's response addressed my question, and I will maintain my score.", "rebuttal": "Thank you for reviewing our work and for your support of our work. Please see below our responses to the points you raised. \n\n> “the improvement is mainly in the realizable setting with the greedy stepsize. For the general setting, the improvement is somewhat minor, but it's still a strict improvement since the algorithm requires no knowledge of the variance at optimum.”\n\nIn the realizable setting, our improvement in fact holds for any stepsize asymptotically larger than $1/\\sqrt{T}$ and not only for the greedy stepsize $\\eta=1/\\beta$. Beyond the realizable setting, our work provides for the first time the (nearly) optimal last-iterate convergence rate of $1/T+\\sigma_\\star/\\sqrt{T}$ in the general convex and smooth case. This rate was previously known only in the special case of ordinary least squares (Varre et al [32]). We view this as a significant result. You are correct to note that none of these results require knowledge of the variance at optimum.\n\n> “I wonder if last-iterate convergence guarantees can be potentially obtained for the agnostic setting with the natural $\\eta=1/\\beta$ choice. If it's not theoretically impossible, what's the main technical difficulty?”\n\nIn the agnostic case (which is, to our understanding, the non-realizable case with $\\sigma_\\star >> 0$), the last-iterate sub-optimality of SGD $\\eta=1/\\beta$ does not diminish to zero. The best one can hope for is a rate of $O(1/T+\\sigma_\\star^2)$, and as we discuss in the paper, there is indeed still a gap between our guarantees and the best known lower-bounds in this setting.\n\nFrom a technical perspective, the main difficulty in improving the bounds is that our current analysis technique is sensitive to multiplicative numerical constants along the analysis, as they carry over to constants in the exponents and therefore translate to polynomial differences in rates. We do not know if a new and innovative new technique is necessary for closing the gap."}]

Author rebuttal:

Meta-review: The paper studies convergence of the last iterate of SGD applied to $\beta$-smooth convex functions, in the "interpolation" regime (i.e., where the variance $\sigma_*$ at the optimum is very small or zero). The results are also extended to sampling without replacement and continual learning settings. The paper obtains a bound on the optimality gap that allows for large step sizes, up to $1/\beta,$ for arbitrary value of $\sigma_*.$ For tuned fixed step size, this bound recovers known bounds, which are of the order $1/T + \sigma_*/\sqrt{T}.$ Importantly, unlike prior results (which necessarily forced the step size to be sufficiently small and dependent on $T$), this work allows for *large* step sizes and provides informative bounds even when the step size is as large as $1/\beta$, assuming $\sigma_*$ is small compared to $1/T$ (e.g., $\sigma_* = O(1/T)$).

The results are interesting, considering there has been a lot of recent interest on this topic and none of the prior results could provide informative bounds for large step sizes. The reviews were in uniform agreement about the paper's strength and thus I recommend acceptance.
Decision: Accept (poster)