Last Iterate Convergence of Incremental Methods as a Model of Forgetting
Authors: Xufeng Cai
Jelena Diakonikolas
Venue: ICLR 2025 Poster (2025)
Keywords: incremental methods
last-iterate convergence
proximal methods
continual learning
Primary area: optimization
TL;DR: We provide the first convergence results for the last iterate of incremental methods and study the incremental proximal method as a mathematical abstraction of continual learning, formally characterizing the effect of regularization on forgetting.

Abstract: Incremental gradient and incremental proximal methods are a fundamental class of optimization algorithms used for solving finite sum problems, broadly studied in the literature. Yet, without strong convexity, their convergence guarantees have primarily been established for the ergodic (average) iterate. We establish the first nonasymptotic convergence guarantees for the last iterate of both incremental gradient and incremental proximal methods, in general convex smooth (for both) and convex Lipschitz (for the proximal variants) settings. Our oracle complexity bounds for the last iterate nearly match (i.e., match up to a square-root-log or a log factor) the best known oracle complexity bounds for the average iterate, for both classes of methods. We further obtain generalizations of our results to weighted averaging of the iterates with increasing weights and for randomly permuted ordering of updates. We study last iterate convergence of the incremental proximal method as a mathematical abstraction of forgetting in continual learning and prove a lower bound that certifies that a large amount of regularization is crucial to mitigating catastrophic forgetting---one of the key considerations in continual learning. Our results generalize last iterate guarantees for incremental methods compared to state of the art, as such results were previously known only for overparameterized linear models, which correspond to convex quadratic problems with infinitely many solutions.

Published as a conference paper at ICLR 2025
LAST ITERATE CONVERGENCE OF INCREMENTAL METHODS AS A MODEL OF FORGETTING
Xufeng Cai Jelena Diakonikolas
Department of Computer Sciences, University of Wisconsin-Madison xca i 74@wi sc edu, je ena@cs. wisc. edu
ABSTRACT
Incremental gradient and incremental proximal methods are a fundamental class of optimization algorithms used for solving finite sum problems, broadly stud- ied in the literature. Yet. without strong convexity, their convergence guarantees have primarily been established for the ergodic (average) iterate. We establish the first nonasymptotic convergence guarantees for the last iterate of both incremental gradient and incremental proximal methods, general convex smooth (for both) and convex Lipschitz (for the proximal variants) settings. Our oracle complex- ity bounds for the last iterate nearly match (i.c., match up to a square-root-log log factor) the best known oracle complexity bounds for the average iterate, for both classes of methods. We further obtain generalizations of our results to weighted averaging of the iterates with increasing weights and for randomly per- muted ordering of updates. We study last iterate convergence of the incremental mathematical abstraction of forgetting in continual learn- ing and prove a lower bound that certifies that a large amount of regularization is crucial to mitigating catastrophic forgetting-ont of the key considerations continual learning. Our results generalize last iterate guarantees for incremen- tal methods compared to state of the art, as such results were previously known only for overparameterized linear models, which correspond to convex quadratic problems with infinitely many solutions.
proximal method
INTRODUCTION
We study the last iterate convergence of incremental (gradient and proximal) methods, which apply to problems of the form
T min {f(z) Σ 1 f((a)
(I)
t=1
As is standard, we assume that each component function fe is convex and either smooth or Lipschitz- continuous and that minimizer x. arg min (ax) exists.
Incremental methods traverse all the component functions fe in a cyclic manner, updating each it- erate by taking either gradient descent step (in the case of incremental gradient methods) proximal-point step (in the case of the incremental proximal method) with respect to the individ- ual component functions fc- For a more precise statement of these two classes of methods, see Sections 2 and 3. Same prior work (Bertsekas et al., 2011; Bertsekas, 2011; Li et al., 2019; Mishchenko al., 2020; Cai al., 2024), we define oracle complexity of these methods as the number of first-order or proximal oracle queries to individual component functions fi required to reach solution x with optimality gap f(x) f(..) S 6 on the worst-case instance from the considered problem class, where > 0 is a given
parameter.
Our main motivation for studying the last iterate convergence of incremental methods comes from its intrinsic abstraction of the catastrophic forgetting in continual learning (CL) with cyclic task re- playing. In particular, CL represents a sequential learning setting, where machine learning model gets updated over time, based on the changing or evolving distribution of the data passed to the learner. A major challenge in such dynamic learning settings is the degradation of model perfor- mance previously seen data, known as the catastrophic forgetting (McCloskey & Cohen, 1989;

---

Published as a conference paper at ICLR 2025
arg miny fi()+ + Ixx-xil'
arg miny f2(x) +
Ix-x=ll 2n
arg miny fx(x) + 2n
[xx-xel
X1
X2
Xr+1
Figure 1: Illustration of both continual learning over tasks (s)) (cyclic replay regularization) and incremental proximal method 21,1+ = prox (xe.)) = arg min g (f((r)
+ 2n || xx,(l²)
Goodfellow et al., 2013), which has been well-documented in various empirical studies; see, e.g.- recent surveys (Parisi et al., 2019; De Lange et al., 2021). On the theoretical front, however, much is still missing from the understanding possibilities and limitations related to catastrophic forgetting, with results for basic learning settings being obtained only very recently (Balcan et al., 2015; Evron al., 2022; Peng & Risteski, 2022; Chen al., 2022: Cao et al., 2022: Evron al., 2023; Lin al., 2023b; Goldfarb & Hand, 2023; Peng et al., 2023; Goldfarb et al., 2024). Our work contributes to this line of theory research, focusing on more general convex settings compared to prior work.
While there are different learning settings studied under the umbrella of CI. following recent work Evron et al. (2022: 2023), we focus on the CL settings with cyclic replaying of tasks. Such settings arise in applications that naturally undergo cyclic changes in the data/tasks, due to diur- nal or seasonal cycles (e.g., agriculture. forestry, e-commerce, astronomy, etc.). For instance, e-commerce platforms like Amazon have predictable seasonal changes in website traffic and pur- chases around holidays and during promotional periods such as Prime Days.
Given T tasks associated with the loss functions {fi] we illustrate the correspondence between the incremental proximal method (IPM) and CL in Fig. 1, where H, denotes the model parameter in CL or the last iterate of IPM at time The proximal step of the IPM can be abstraction of the training process (minimizing the loss function, with fgrreuularization enforcing closeness to previous model parameters) on each task. We note in passing that which training al- gorithm is used to minimize the loss has no bearing on this model, as we are interpreting cyclic replaying of tasks in CL as an optimization algorithm over discrete set of tasks, similar previous theoretical work on CL (Evron et al., 2022; 2023; Goldfarb et al., 2024).
mathematical
The forgetting over T tasks after K epochs/cycles in CL with cyclic replaying of tasks is defined by (Doan et al., 2021; Evron et al., 2022; 2023)
T fk fx( == Σ ((
(2)
where 21.11,441 is the model parameter vector after 1hhh cycle/epoch. Forgetting is catastrophic if fx (1 k 0.
Observe that Eq. (2) corresponds to the value of the objective function from Eq. (1) at the final iterate FK -K-1, Prior work (Evron et al., 2022) that obtained rigorous bounds for the forgetting as in Eq. (2) applied to the problems where each ft is a convex quadratic function minimized by the same æ, such that f((x..) fxx.) O. By contrast, we consider more general convex functions that are either smooth or Lipschitz continuous, and make no assumption about x. beyond being a minimizer of the (average) function f. Since we are not assuming that f(x.) O, our focus is on bounding the excess forgetting fK (*x) fxx), equivalently the optimality gap for the last iterate in Eq. (1).
The method considered in Evron et al. (2022) minimized each component function exactly, out- putting the solution closest the previous iterate in each iteration, using implicit regularization properties of SGD. To obtain the results, it was then crucial that the component functions were quadratic (so that there an explicit, closed-form solution for each subproblem) and that all com- ponent functions shared nonempty set of minimizers with value zero (so that forgetting can be controlled despite aggressive adaption to the current task). Our work using the IPM instead consid- ers explicit regularization to enforce closeness of models on differing tasks. This could potentially degrade the performance on the current task, but as a trade-off can control forgetting and addresses much broader class of loss functions, without any shared minima assumptions. Such explicit reg- ularization is also motivated by the existing CL practice (Heckel, 2022; Li et al., 2023), as one of major empirical approaches mitigating catastrophic forgetting (De Lange et al., 2021).
2

---

Published as a conference paper at ICLR 2025
Due to space constraints, further discussion of related work is provided in Appendix A.
1.1 CONTRIBUTIONS
Our contributions are twofold. First, we derive the first results for the last iterate convergence rate of standard incremental methods'. Second, our results for convergence of the IPM have a direct impli- cation on the catastrophic forgetting in CL, and we formally characterize the effect of regularization on forgetting. Below, we summarize our main contributions, where o² == + Σ [x.)))) denotes the gradient variance at I.. The quantity o² is intrinsic to oracle complexity of incremental methods (Mishchenko et al., 2020; Nguyen et al., 2021; Cai et al., 2024; Cha et al., 2023).
Last iterate convergence of Incremental Gradient Descent (IGD). We provide the first or- acle complexity guarantees for the last iterate of standard variants of IGD with either deter- ministic randomly permuted ordering of the updates, applied to convex L-smooth objectives. Up to a square-root-log factor, our oracle complexity bounds in Theorem I and Corollary 2-
which are Ō TI + TL 2/2
= for the deterministic variant and Ö TLillo-=. +
vTLo, 1|20 1120==..1l)) for the randomly permuted variant-match the best known oracle complexity bounds for these methods, previously known only for the (uniformly) average iterate (Mishchenko et al., 2020; Nguyen et al., 2021: Cai et al., 2024; Cha et al., 2023). We further extend our results to increasing weighted averaging of the iterates in Corollary which places more weight the more recent iterates, removing the excess square-root-log factor in the resulting oracle complexity bound.
23/2
Last iterate convergence of Incremental Proximal Method (IPM). We provide the first oracle complexity guarantees for the last iterate of IPM applied to convex and either smooth or Lipschitz- continuous objectives. When each component function is convex and L-smooth, we show (in The-
orem 2) that IPM has the same Ö TL] =1 +
oracle complexity as IGD. This result is new for any variant of this thethod-witd average or last iterate as its output. When component functions
convex and G-Lipschitz, our oracle complexity Ō GGT in The- orem 4 matches the best known oracle complexity bound up to a log factor, which was previously known only for the (uniformly) average iterate (Bertsekas, 2011; Li et al., 2019). We further argue (in Corollary 3 and Corollary 4) that for both settings our analysis can be extended to admit inexact proximal point evaluations an important setting not addressed by prior work on general IPM.
IPM as model of CL. We initiate the study of IPM as model of CL, corresponding to sequential ridge-rgullarized model training commonly used practice. On the positive side, our last-iterate convergence results for IPM in Theorem 2 and Theorem 3 demonstrate that forgetting (correspond- ing to the optimality gap at the last iterate) can be effectively controlled if the amount of employed regularization is sufficiently high. On the negative side, we show that for any constant amount of regularization, forgetting always catastrophic, even for least squares problems. In particular, provide univariate quadratic example such that for any constant regularization parameter, the asymptotic limit of (excess) forgetting is non-zero. Further, we prove that for forgetting to be made smaller than some target e, the regularization must be sufficiently high and depend polynomially on 1/c, T, and σ.. These results are summarized in Theorem 3 and highlight the limitations of regularization black-box tool for controlling forgetting in CL.
1.2 PRELIMINARIES
We consider the d-dimensional real vector space (Rdd || II), where | Il is the &s norm. We de- note [T'] := {1, 2, ... T). Given a proper, convex, lower semicontinuous function f. its proximal operator and Moreau envelope are defined by
prox,, = arg min { (,,, lly x12 + f(v)}. Mnf(2)) = min {2, lly - x11
111y=x12-2 + f(y)),
'An independent concurrent work to ours (Liu Zhou, 2024b) studied the last iterate convergence of shuffled SGD for composite (strongly) convex smooth/Lipschitz optimization. For the same problems as studied in our Section 2. they obtained the same convergence results. The remaining results in (Liu & Zhou, 2024h) and our work are not directly comparable, as the motivation for the two papers and the studied settings different; for more detailed discussion, see Liu & Zhou (2024b, Section 2) and Appendix A.
3

---

Published as a conference paper at ICLR 2025
Algorithm 1 Incremental Gradient Descent (IGD)
Input: initial point Zp. number of epochs K, step size {nk}
for = 1: K do
1 1
for 1
22-1, 22-1, 7i fi (2
F4 = 2R-1,7
return KK
respectively, for parameter "f 0. The Moreau envelope is 7 ---smooh with the gradient (2) = (x - prox,,(a)) (x)) E 0 (z)), where Of(-) is the subdifferential of f-
We make the following assumptions. The first one is made throughout the paper. Assumption 1. Each Js is convex and there exists a minimizer v. E arg min (ar).
By Assumption f is also convex. In nonsmooth settings, we make an additional standard assump- tion that the component functions are Lipschitz-continuuu
Assumption 2. Each ft is G-Lipschitz, i.e., lft(z) fo(w) s Gl x - yll for any x, y E R.: thus
[z))( < G for all ge (x(x)) 0f((z))
For the smooth settings, we make the following assumption. Assumption 3. Each is L-smooth, i.e., [V)((x) ff(())ll < L|x for any x, Rd.
We remark that Assumptions 2 and 3 imply that f is also G-Lipschitz and I-smooth, respectively. These two assumptions can also generalized to with distinct Lipschitzssmotthnss constants, and our results would scale with the average Lipschitzsmmoothness constant using the techniques from Cai et al. (2024), which we omit to keep the focus on the intricacies of the last iterate conver- gence. When f is L-smooth and convex, we will often make use of the following standard inequality that fully characterizes the class of L-smooth convex functions:
2L [Vv(()) - 2 < f(y) - f()) (V (V(()) y-x) x) Vx, y E Rd.
(3)
Finally, when each Jr. is smooth, we assume bounded variance at w., same as all prior work that considered the same settings of IGD/shuffled SGD as we do (Mishchenko et al., 2020; Nguyen et al., 2021; Tran et al., 2021; 2022: Cai et al., 2024).
Assumption 4, The quantity of == 1 ΣTn [+((,,)) is bounded.
LAST ITERATE CONVERGENCE OF INCREMENTAL. GRADIENT DESCENT
In this section, we introduce our techniques for analyzing the last iterate guarantee and bound the oracle complexity for the last iterate of incremental gradient descent (IGD), assuming component functions are smooth and convex. In the context of CL. this corresponds to a simplified setup where the learner incrementally performs a single gradient step on each task and cyclically replays the T tasks. Nevertheless, this setup serves as a warmup the proximal setup we discuss in the next section. Additionally, it is of independent interest as incremental gradient methods are widely used in the optimization and machine learning literature, where despite the lack of prior theoretical justi- fication, it is typically the last iterate that gets output by the algorithm in practice.
We summarize the IGD method in Alg. 1, assuming the incremental order 1,2, T in each epoch for simplicity and without loss of generality. The oracle complexity for the (uniformly) average iterate of IGD has been shown to be O TL + TVLo=> for an e-optimality gap (Mishchenko et al., 2020; Cai et al., 2024) under the same assumptions we make here (Assumptions 1, 3, and 4), while, as discussed before, there were no guarantees for either the last iterate or even a weighted average of the iterates. The main result of this section is that the same oracle complexity applies to the last iterate of IGD, up to a gquare-root-loy factor. We further generalize this result to weighted averages of iterates with increasing weights and to variants with randomly permuted order of cyclic updates.
4

---

Published as a conference paper at ICLR 2025
We begin the analysis by deriving bound on the gap with respect to arbitrary but fixed reference point 2, as summarized in the following lemma, whose proof is in Appendix B. This stands in con- trast to arguments deriving bounds the average iterate, which take like a minor difference, it affects the analysis non-trivially: a direct extension of prior arguments would require replacing Assumption 4 4-which imposes bound on + Ei= f( || w a bound on T Ei= [()((2) for an arbitrary 2, which would be a much stronger requirement.
2.. While this may seem
Lemma 1. Under Assumptions 1 and 3, for any IRd that is fixed in the k-th cycle of Alg. I and any a, B > 0 such that + 8 S 2. if I VBT1. then for all k E [K],
((J(#)) (=)) R L Ei
(ar.) || [T(((=) f(x.))
24p || x1|
| - =1
Our next step is to specify our choice of the reference point x for each epoch. In particular, we consider a sequence of points {=x) that is recursively defined as a convex combination of the algorithm iterate 2& and the previous reference point #k-1i
Zk = (1 Aa)ara + \
(4)
for k 2 0 with 2-1 = x- and d E [0. 1] to be set later. Observe that z can also be written as convex combination of the points (2z
} 1=0 and x, by unrolling the recursion, i.e.,
Zk (1 A + (II At)ar. + En= (IL= )1 >y)aa..
= If we set A = for all k, then we have 2/z- = x. and recover the bound f(x)) - f(x.) in Lemma 1, which leads to the average iterate guarantee. For general {)e), we obtain the following lemma to relate the function value gap f(x)) (1z to the optimality gap [(xx) - f(x.), whose proof is deferred to Appendix B. Lemma 2. Let z be defined by Eq. (4) for a given sequence of parameters A E (0, where k 2 0 and 2 x.. Under Assumption 1, if there exists a sequence of nonnegative weights wn such that ug S for le E [K- 1). for all is [K]:
where (1 - Ax) +
Ej= A
(II=
1. wk w ((x))) < EY= wy (f(r,)) - (ax.));
2. Wx- (x-1(f(xxs) - --a---(aa 1)) 2 WK- ( - f(xx)) - E5= w1 ()) -
The role of the sequence of weights {wx} in Lemma to ensure that we can telescope the terms || 1 || = in Lemma 1, when summing the weighted per-epoch recursion Wk (f - f()x-1) over l E [K] and deriving the convergence results. On the other hand, to succinctly see why such { could lead to the desired last iterate guarantees, we note that the second part of Lemma 2 indicates that (f - f (2x-1)) intrinsically includes retraction terms of the optimality gaps at the previous iterates. Thus, we can deduct Wk-1(f (Ixx) fxx)) from Σ wk-1 (f (xxx - f(zx-1) by properly choosing A and wi to cancel out the optimality gap terms at the intermediate iterates. In this case, the convergence rate for the last iterate would be characterized by O( E wx-1/Wx-1i)
Our choice of {2x} } is inspired by the recent work (Zamani & Glineur, 2023; Liu & Zhou, 2024a) on last iterate guarantees for subgradient methods and SGD with X 11-11 However, their proof wx
techniques are not directly applicable to incremental methods, due to technical obstacles including additional nontrivial error terms of the form gT(J(z+) f(x.)) in Lemma 1 arising from the incremental gradient steps using reference points other than æ.. Further discussion is in Appendix A. Such error terms inherently deteriorate the growth rate of }w and could lead to a worse last iterate rate compared to the rate on the average iterate. In the following theorem, we calibrate such degradation on the last iterate guarantees, and show that with slightly smaller step size one can still achieve essentially the same rate as for the average iterate. The proof is provided Appendix B. Theorem 1. Under Assumptions 1, 3, and 4 and for positive parameters o., B > 0 such that 1 + S
}.8 if the step size is fixed and satisfies 17p- = 7) S VBIL the output æ of Alg. 1 satisfies
f(xx) f(x.) S TT 3// 3/aa)
1T77 + e|I20 -0,
eig
(6)
24077
5

---

Published as a conference paper at ICLR 2025
In particular. for a 4,3 4 log K, and 17 min 21/3Te22
1000
2/33
2/3
Li/ag //////////114 (1++og KY1/8 2/log KTL
f(xx) f(xx) = 0 0 1,113022 1120 m. (1 k)1/3
T. m. Vog R and thus f(xx)
K3ya
f(x.) S after Ö( (Lillle -0. 11= + TL TL
210 2.
individual gradient evaluations.
The error term f(*k-1) (xx)) in Lemma I plays the role of slowing the last iterate rate, as calibrated by the dependence on a/3 3 in Eq. (6). To remedy such degradation compared to the average iterate rate (Mishchenko et al., 2020; Cai et al., 2024), one natural thought to make a/B sufficiently small. In particular, choose a/B 1/ log K and show that the last iterate rate nearly matches the best known rate on the average iterate, with the trade-off of requiring order- vlog smaller step sizes in comparison with Mishchenko et al. (2020); Cai et al. (2024). This translates into the oracle complexity that is larger by at most a / (1/e) factor. For most cases of interest, this quantity can be treated as a constant: for example, for 10-8, Vlog(1/e) 4.29.
On the other hand, with A = 1 and constant wg. Lemmas and directly imply the average iterate guarantee, as sanity check. Additionally, instead of zeroing the weights the optimality gap terms f*xx) f fxx.) for l E [K - 1] to obtain the last iterate guarantee, one can deduce the convergence rate on the increasing weighted averaging that places more weight on later iterates, as formalized in the following corollary. The proof is deferred to Appendix B.
Corollary (Increasing Weighted Averaging). Under Assumptions 1, and 4 and for parameters
a,8 O such that 1 1/2 S 3. if the step size nj is fixed and such that 1) S VBTT.' then for any
constant c E (0, and increasing sequence {wx) with we = (L+a/8)(K (-)))((Kk)+( kk+1-c - Wk-1, Alg. (L+a/3)(KR)
outputs kk- = Ek=
satisfying
EK m
f(xx) f(x.){ T +
|| 2enTKK
In particular, taking 3 = (1) and the step size min VBTL f(xx) f(x.) s after O (T
10--0 2. 2T
1/33, we have
T..00-..1 + TL 11m0--..11 individual gradient evaluations. 0////12
CE
We remark that increasing weighted averaging shaves off the (at most) qquare-root-log term appear- ing in the last iterate rate above and recovers the best known rate for the average iterate (Mishchenko et al., 2020; Cai al., 2024). The parameters a, 3 are included in the weights wp controlling the growth rate of the increasing sequence {wk}- When a/3 - oc, increasing weighted averaging reduces to the uniform weighted average.
Shuffled SGD. We extend analysis to handle the case with possible random permutations on the task ordering in each epoch, showing order-v/T improvements in complexity if involving domness. We consider two main permutation strategies of particular interests in the literature on shuffled SGD): (i) random reshuffling (RR): randomly generate permutations at the beginning of each epoch; (ii) shuffle-once (SO): generate a single random permutation at the beginning and use it in all epochs. Those strategies lead order-(1/T) improvements in bounding the vari- Vfa(x.)))'
ance term D E'n V results with permutations in the following corollary. The proof deferred to Appendix B. Our last iterate guarantee nearly matches the best known average iterate convergence rate for shuffled SGD (Mishchenko et al., 2020; Nguyen et al., 2021: Cai al., 2024) and the lower bound results for the RR scheme (Cha et al., 2023), with slightly (order-( ((ogk))) smaller step size.
from Lemma 1, and we state the improved convergence
Corollary (Shuffled SGD (RR/SO)). Under Assumptions 1, 3 and 4 and for positive parameters a, 3 > 0 such that 1 + < 3. if the step size is fixed and such that v S 1 the oulput k of Alg. with uniformly random (SO/RR) shuffling satisfies
JBTL
[[((0k) - [xx)) S enjo + B/a)K 140/8
el1zo 11
2T 140/0"
-o-0 2_ 2//
With = 4, = 4log K and 17 = min 21/372/33 (9 + Hog KY1/5* 2,log KTL.) 3: we have [(f(#x) f(xx)) after 5 TL Rg 11 /TLo, 11 2, 112)
individual gradient evaluations.

---

Published as a conference paper at ICLR 2025
Algorithm 2 Incremental Proximal Method (IPM)
Input: initial point Zo. number of epochs K, step size {nk}
for = 1: K do
1 22k-1
for =
22-1, = fe (x arg min
2qpe ||
T xx-1,el1 f((x))
Fh = 2R-1,7
return 2K
It is worth noting here that the analysis of shuffled SGD is technically disjoint from the traditional analysis of SGD, which relies on sampling with replacement. (By contrast, shuffled SGD employs sampling without replacement.) As a consequence, the last iterate results for SGD are not applicable to incremental methods (nor shuffled SGD), as discussed in more details in Appendix A.
3 INCREMENTAL PROXIMAL METHOD
In this section, we leverage the proof techniques developed in the previous section and derive the last iterate convergence bounds for the IPM, summarized Alg. 2. While the IPM is a fundamental method broadly studied in the optimization literature-ant thus its last iterate convergence bounds are of independent interest-oul main motivation for considering this method comes from using mathematical abstraction of CL, discussed in the introduction. Thus we begin this section by briefly explaining this connection and reasoning.
The considered setup is motivated by the general fz-regularized CL setting (Heckel, 2022; Li al., 2023). In particular, each proximal iteration 1 = prox (.%-1,e) can be interpreted as minimizing the &2 (a. ridge) regularized loss fa(()) + 2nx || 1 corresponding to the current task t, which aligns with the common machine learning practice of using regularization to improve the generalization error and prevent forgetting. When 7 + 0o, the proximal point step reduces the CL setting where the learner exactly minimizes the loss of the current task, i.e., 2k-1,1+1 = arg min fe(x), while the regularization effect vanishes and causes larger forgetting on previous tasks. When тi small, the proximal point step is easier to compute with larger quadratic regularization and prevents deviating from the previous iterate thus causing less forgetting. However, in this case the plasticity of the model may be deteriorated.
We also note that our analysis of IPM is related to previous work on cyclic replays for overparame- terized linear models with (S)GD (Evron al., 2022: Swartworth et al., 2024), as (S)GD in this case acts as an implicit regularizer (Gunasekar et al., 2018; Zhang et al., 2021) (whereas proximal point update acts as an explicit regularizer). The two lines of work are not directly comparable: Evron et al. (2022); Swartworth et al. (2024) considers exact minimization of component/task loss function and bounds the forgetting, but only addresses convex quadratics where the component loss functions have a nonempty intersecting set of minima (which implies hand, our work addresses much more general (not necessarily quadratic) convex functions and does not require a. 0, but instead relies sufficiently large regularization.
O in Assumption 4). On the other
3.1 SMOOTH CONVEX SETTING
We first study the setting where the loss of each task is convex and smooth, for which show faster convergence and which covers many regression tasks studied prior CL work; see e.g., Evron et al. (2022); Goldfarb et al. (2024). In contrast, prior work either only focused nonsmooth settings for IPM (Bertsekas, 2011; et
et al., 2019; 2020) or studied different algorithms without component-wise proximal steps for smooth settings (Bertsekas, 2015; Mishchenko et al., 2022).
Under component smoothness, the proximal iteration is equivalent to the backward gradient step:
F = I4-1,1 - 7a Vf
Hence, much of the analysis from Section 2 can be adapted here, and the main difference lies in bounding the gap f(x2 f(z) within each epoch with decomposition w.r.t. 1,41 instead of
7

---

Published as a conference paper at ICLR 2025
2k-1.1 in comparison to Lemma 1. Then choosing 2k-1 defined by Eq. (4) and mimicking the proof of Theorem 1, we obtain the following theorem, whose proof is in Appendix C. Theorem 2. Under Assumptions 1, 3, and 4 and for parameters a, B > 0 such that 1 + 3 S if
the step size is fixed and such that n S /ØTI. the output æ of Alg. 2 satisfies
a/a f(xk) - fxxx)=))=-)))))))))))())) S on T0, L1 W7B
+ el|00-
2rTK
|100 200-21 2. 1|2/3
With a 4,3 4log K and 11 min 22/3T03
K)L/81 2vlog KTL) we have
f(zx) - f(x.) = 0 10L44822 20:00 (1+Hog Kyt/a
+ L||ma
=.I2/log ). and thus f
=_1
K2/3
K
f(x)) S after 3(TLllee =..1l Tz a. ||:00 =. individual gradient evaluations.
A few remarks are in order here. First, the last iterate convergence rate of IPM matches the rate of IGD for the last iterate. This is also the first convergence result for IPM (with component- wise proximal updates) in smooth convex settings, in comparison with the prior results for convex Lipschitz setups (Bertsekas, 2011; Li et al., 2019; 2020). Second, the extensions to the increasing weighted averaging and RR/SO shuffling discussed Section also apply to this setting, which we omit for brevity. Lastly, the step size constraint in Theorem 2 may seem surprising, given that the proximal point method (corresponding to IPM with T = 1) couverges for any positive step size. However, as show in the following theorem, such step size restriction is necessary for IPM (with T 2 2) to reach the target optimality gap, highlighting challenges arising from incremental updates. We provide proof sketch below, while the complete proof is in Appendix C.
Theorem 3. Given I. > O and T 2 2, let Fr,I. be the class of finite-sum functions f(x) = T Et= fe(æ)), with each component Se being L-smooth and convex. Then:
1. For any fixed step size 17, there exists a function f E Fr.L such that the iterates æ& of Alg.
satisfy f(zx)= f(x.) + 0 as k + co. As a consequence, the forgetting is catastrophic.
2. For any fixed step size 1y that only depends on the parameters of the problem class (I., T, error e), there exists a function f E FT.L such that the iterates Ty Alg. satisfy lim f(xx) - f (x.) > 1.
k-+
3. Given >> O, if the fixed step size satisfies 1j 2 min { 16VE
1 then there exists function f E FT,L such that the iterates 2% of Alg. 2 satisfy f(xx) - f(x.) > e for all sufficiently large k.
VTLo.'
Proof sketch. For all parts of the proof, we consider 1-dimensional quadraties
f(x) = 7 Et Se(x), where fe(x)) _ (x - 5,)2 (1 (T))
for L > 0 and (dther S R. is immediate that f(x is minimized at x. = + + 8, this case, Alg. 2 using a fixed step size v) performs closed-form updates on f, i.e. 1R+1 = xx + (1
7) Σ --1 T where y = 7 E (0, 1). Given any initial point zo. by iterating we have
Ik- - I. = g KT x0 + Σim1 (2
(1-"0---0---"" MT) - 4) k ΣT (يسي - 4)6e.
1-7"
For 1), since 7 E 10, 1
1
Σl x - 7 > 0 at = T. As k + 0o, for {8g hetr) with
T
(1-)) 1- +), we have f f(x) - -f(x)) = 1/4 (x )² N ( + 87 > O.
sgn(6,) sgn
For 2), further observe that as 7 E (0, 1), (112 $ - Tzd. As k xa, for |6 < 1/2
1-77"
11-1)
(1 E [T - 1)) and 8f > 222/L)2/2 f(xx - f(x.) > 1/2 (G -))- -) البيي 16.1 = 1.
For 3), the case 17 2 TL
1 can be handled similarly as in 1), so we assume w.l.o.g. that 7 2 1 T+1-
Let 7 1 K. where 0- < 1 < J. Further noticing that (1 - x)T 2 KT + x x2
T+I
for T > 2 and KT < 1, then we have that the coefficient of sy is
1-y
x) 4 2 RT
< 2
2 8.
1-
T
47
8

---

Published as a conference paper at ICLR 2025
Error (Avg)
Reg Error (Max)
Optimality
100
T 100
150
30
10
10
10
10
10
10-3
10-2
10
10
10-3
10-2
10
Step Size
Step
Size
Step Size
(a) Forgetting
(b) Regularization error (avg)
(c) Regularization error (max)
Figure 2: Numerical results for performing IPM on T component least square functions, correspond-
ing to the fz-regularized CL. setting with 7 linear regression tasks with cyclic replays.
If 2
16v2 VTLa." since of < LT 1=1 / in this example, =
اا g.+ 16VE
16
VEL
8 3e/LL with choosing large enough Σ 82. Then for sufficiently large & and (ōeheetz such
VEEN of that 67. Et= of and sgn(..) sgn (1-2) +): ((x) f(x.) 2
21. 3287
LE o8
Regularization effect. We now discuss how the regularization parameter (the inverse step size of IPM) affects the loss the current task and (excess) forgetting, based the above convergence results for IPM. An interesting aspect of our result in Theorem is that there is a critical value
- P00-0 m. 2/3
min 21/3TO7 123KK3
VSTT
such that decreasing 7) beyond n)., both the regularization error on the current task and our upper bound on the forgetting increase. For 17 7)x (i.e., when we decrease the regularization error), Theorem shows that the forgetting would increase, least in some regimes of the problem param- eters. Moreover, Theorem 3 demonstrates that polynomial dependence on other parameters like e and 1/a, necessary in the choice for 7j. other words, strong regularization is needed to control the forgetting to target error in general smooth convex settings. Another direct implication of The- orem is that if no assumptions such as similarity are made on the tasks, then any lg fz-regularized model using finite regularization parameter would suffer catastrophic forgetting, i.e., the forgetting would not be approaching zero as the number of epochs tends to infinity.
We further provide illustrative numerical results in Fig. 2 to facilitate our discussion. In particular, we choose = 2, T E {100, 150, 200}, 5, = 1/t (t E [T 1)) and 6n T for the example f(x) L Σ (x 8 used in the proof of Theorem 3. In Fig. 2(a), we plot the optimality gap at the last iterate, i.e., the excess forgetting, against the step sizes after K = 10a epochs. It can be observed that the forgetting first decreases with reducing the step size, then increases beyond some critical value. Note that the critical values
27
around 10-5, which is nontrivially smaller than 1/L= = 1/2, while a larger T leads to a smaller such critical value. These numerical examples corroborate results from Theorems and 3, which jointly suggest that the step size (amount of regularization) can neither be too small nor too large. On the other hand, in Fig. 2(b)-(c) we show the final stagnated average and maximum regularization error, i.c., + ET= f( 1 fe(x..) and m (#++), fo (x...) over T tasks. where v.,t the minimizer of ft- We thus conclude from Fig. 2 that as the step size increases (equivalently, regularization parameter decreases), the
regularization error decreases as well, but the forgetting increases.
To conclude, our results demonstrate that there is an inherent trade-off between forgetting and regu- larization error in CL with cyclic replaying regularized smooth convex tasks. It is an interesting question for future research how incorporating task similarity into the analysis and even into the employed regularizing function might affect the conclusions.
3.2 CONVEX LIPSCHITZ SETTING
We now further relax the smoothness assumption and consider the convex Lipschitz setting, with applications such linear classification tasks considered in Evron et al. (2023). To carry the

---

Published as a conference paper at ICLR 2025
analysis, leverage the standard fact that the proximal iteration is equivalent to the gradient step with respect to the Moreau envelope, i.e.,
-k- - 15- 7h V f f
while the gradient of the Moreau envelope V.M. / (#x=1.t) belongs (f (f5-1111)))) thus is
bounded by the Lipschitz constant of ft. We use these observations to bound the gap f( - f())
for each epoch and then use the sequence {zx } defined in Eq. (4) to deduce the last iterate rate. The results are summarized in the following theorem, while the proofs are deferred to Appendix C.
Theorem 4. Under Assumptions and 2, the outpur a of Alg. satisfies
f(ak) f(x.)
27 1 x. 1 G Σ
Moreover, given > 0, there exists a constant step size 1 xx such that f(xx)= f(xx) S after Ö G2 m.1l²) individual proximal oracle queries.
GTvR
The last iterate rate we obtained in Theorem 4 matches the best known prior results for the average iterate of incremental proximal methods in nonsmooth settings (Bertsekas, 201 10 Li al., 2019), up
to logarithmic factor. Further, we take the O vK step size only for analytical simplicity, while the diminishing step sizes 77 = 0 v
will yield the same rate via a similar analysis.
3.3 INEXACT PROXIMAL POINT EVALUATIONS
In the last two subsections, we derived our results assuming that the proximal point operator can be evaluated exactly. However, computing the proximal point corresponds solving strongly convex problem, which is generally possible to do only up to a finite accuracy. In the context of CL. it is also more realistic to assume that the loss of each task is minimized to certain accuracy, rather than exactly. Thus, we now consider the case where 1g-1, is an approximation of prox fi (2x-1,)) with solving the corresponding strongly convex problem to Ek-1, Equivalently, using strong convexity and denoting 9k- = m7 (x - Fx-1,t+1,, we have
/ -pptimmtty gap for 6k-1,
|, m. (ax-1,))))))))) Ek-1,t 11 Mm. (#x S 1.-1. (8)
We note that direct extensions of the previous analysis would not work, because inexact evaluations give rise to additional positive terms | = that cause issues for telescoping. However, we observe that the coefficients of these terms admit additional slackness, i.e., (Xe wk-1) zk-1l/2, while Lemma only requires w & W Thus, as long as the approximation error at each iteration is small, we can still maintain the convergence rate of the IPM with exact proximal point evaluations. With these insights, we extend our convergence results to admit inexact proximal point evaluations as summarized in the following corollaries, with proofs Appendix
Corollary (Convex Smooth). Under Assumptions 1 and 3, 4 and for parameters 3 such that 1 + S 3, if the step size fixed and satisfies т7 S VBTL. the output æK of Alg. 2 with
inexact proximal point evaluations as in Eq. (8) with Σ Ek- S T+(1+a/A)(K k+1J satisfies
/n
f(œK) f(xx)
ollma-m. m.112
o/3 + 2 2L B/a) 11770
24T EKEE Ee
2Tc2. VVnEn
2T I1aj3
(K (K-k)
Given é > 0, if E'= Ek- S / mintt, 3(K-k }. there exists y such that [(xx) - f(x.) S
after 3( Tillia--..11 + TIV2 a.1/. -1110o--111 = individual inexact proximal point evaluations.
63/2
Corollary (Convex Lipschitz). Under Assumptions I and 2, the output æ of Alg. 2 with inexact
proximal point evaluations as in Eq. (8) with ΣT Ek-1. S
ne ,GT
satisfies
Ex
f(ØK) f(xx) S
2T EK
1100 1
+
G G
o E + +EK E
a E
3GEn-1
ΣK
Given e > 0, if //=1|E-1
Ek-1. I
K-k+1
2nGT there exists a constant step size n such that f(xk)
f(x.) < after 3 To
individual inexact proximal point evaluations.
Due to space constraints, conclusions and discussions of future directions appear in Appendix D.
10

---

Published as a conference paper at ICLR 2025
ACGNOWLEDGMENNTS
This research was supported in part by the U.S. Office of Naval Research under contract number N00014-22-1-2348 and by the NSF CAREER Award CCF-2440563.
REFERENCES
Kwangjun Ahn, Chulhee Yun, and Suvrit Sra. SGD with shuffling: optimal rates without component convexity and large epoch requirements. In Proc. NeurlPS'20, 2020.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovie. Qsgd: Communication--ffiienn sgd via gradient quantization and encoding. Proc. NewrlPS' 17, 2017.
Haruka Asanuma, Shiro Takagi, Yoshihiro Nagano, Yuki Yoshida, Yasuhiko Igarashi, and Masato Okada. Statistical mechanical analysis of catastrophic forgetting in continual learning with teacher and student networks. Journal of the Physical Society of Japan, 90(10): 104001, 2021.
Maria-Florina Balcan, Avrim Blum, and Santosh Vempala. Efficient representations for lifelong learning and autoencoding. In Proc. COLT 15, 2015.
Mehdi Abbana Bennani, Thang Doan, and Masashi Sugiyama. Generalisation guarantees for con- tinual learning with orthogonal gradient descent. arXiv preprint arXiv:2006. /1942, 2020.
Dimitri Bertsekas. Incremental proximal methods for large scale convex optimization. Mathemat- ical Programming, 129(2):163-195, 2011.
Dimitri Bertsekas. Incremental aggregated proximal and augmented lagrangian algorithms. arXiv
preprint arXiv: arXiv: 00.5500999995. 2015.
Dimitri P Bertsekas et al. Incremental gradient, subgradient, and proximal methods for convex optimization: A survey. Optimization for Machine Learning, 2010(1-38):3, 2011.
Léon Bottou. Curiously fast convergence of some stochastic gradient descent algorithms. In
Proc. Symposium on Learning and Data Science, Paris' '09, 2009.
Xufeng Cai, Chaobing Song, Stephen J Wright, and Jelena Diakonikolas. Cyclic block coordinate descent with variance reduction for composite nonconvex optimization. In Proc. ICML,'3,, 2023.
Xufeng Cai, Cheuk Yin Lin, and Jelena Diakonikolas. Tighter convergence bounds for shuffled SGD via primal-dual perspective. In Proc. NeurlPS 2024.
Xinyuan Cao, Weiyang Liu, and Santosh Vempala. Provable lifelong learning of representations. In Proc. AISTATS'22 22, 2022.
Jaeyoung Cha, Jaewook Lee, and Chulhee Yun. Tighter lower bounds for shuffling SGD: Random permutations and beyond. arXiv preprint arXiv:2303.071660 2023.
Xi Chen, Christos Papadimitriou, and Binghui Peng. Memory bounds for continual learning. In 2022 IEEE 63rd Annual Symposium Foundations of Computer Science (FOCS), 2022.
Flavia Chorobura and Ion Necoara. Random coordinate descent methods for nonseparable compos- ite optimization. SIAM Journal on Optimization, 2023.
Matthias De Lange, Rahaf Aljundi, Mare Masana, Sarah Parisot, Xu Jia, Aleš Leonardis, Gregory Slabaugh, and Tinne Tuytelaars. A continual learning survey: Defying forgetting classification tasks. IEEE Transactions Pattern Analysis and Machine Intelligence, 44(7):3366-333) 2021.
Thang Doan, Mehdi Abbana Bennani, Bogdan Mazoure, Guillaume Rabusseau, and Pierre Alquier A theoretical analysis of catastrophic forgetting through the NTK overlap matrix. In Proc. AIS- TATS'21, 2021.
Itay Evron, Edward Moroshko, Rachel Ward, Nathan Srebro, and Daniel Soudry. How catastrophic can catastrophic forgetting be in linear regression? In Proc. COLT'22, 2022.

---

Published as a conference paper at ICLR 2025
Itay Evron, Edward Moroshko, Gon Buzaglo, Maroun Khriesh, Badea Marjieh, Nathan Srebro, and Daniel Soudry. Continual learning in linear classification on separable data. Proc. ICML'23, 2023.
Daniel Goldfarb and Paul Hand. Analysis of catastrophic forgetting for random orthogonal transfor- mation tasks in the overparameterized regime. In Proc. AISTATS'23, 2023.
Daniel Goldfarb, Itay Evron, Nir Weinberger, Daniel Soudry, and Paul Hand. The joint effect of task similarity and overparameterization on catastrophic forgetting an analytical model. In Proc. ICLR 24, 2024.
Ian Goodfellow, Mehdi Mirza, Da Xiao, Aaron Courville, and Yoshua Bengio. An empiri- cal investigation of catastrophic forgetting in gradient-based neural networks. arXiv preprint arXiv: 1rXivv13/..6211, 2013.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. Proc. ICMI.' 18, 2018.
Mert Gürbüzbalaban, Asu Ozdaglar, and Pablo A Parrilo. Why random reshuffling beats stochastic gradient descent. Mathematical Programming, 186:49-84, 2021.
Jeff Haochen and Suvrit Sra. Random shuffling beats SGD after finite epochs. In Proc. ICML'19, 2019.
Reinhard Heckel. Provable continual learning via sketched jacohian approximations. In Proc. AIS- TATS 22, 2022.
Prateek Jain, Dheeraj M Nagaraj, and Praneeth Netrapalli. Making the last iterate of SGD informa- tion theoretically optimal. SIAM Journal on Optimization, (1)) 108-1130, 2021.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei A Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska Baraannakkk,, al. Overcom- ing catastrophic forgetting in neural networks. Proceedings of the National Academy of Sciences, 114(13):321-3356, 2017.
Sebastian Lee, Sebastian Goldt, and Andrew Saxe. Continual learning in the teacher-student setup: Impact of task similarity. In Proc. ICML'21 21, 2021.
Haoran Li, Jingfeng Wu, and Vladimir Braverman. Fixed design analysis of regularization-based continual learning. arXiv preprint arXiv:2303. 10263, 2023.
Jijjin Li, Caihua Chen, and Anthony Man-Cho So. Fast epigraphical projection- based incremental algorithms for wasserstein distributionally robust support vector machine. In Proc. NeurIPS 20, 2020.
Xiao Li, Zhihui Zhu, Anthony Man-Cho So, and Jason D Lee. Incremental methods for weakly 2019.
convex optimization. arXiv preprint
Zhize Li. Anita: An optimal loopless accelerated variance-reduced gradient method. arXiv preprint arXiv:2103. 1000..1133.. 2021.
Thize Li and Peter Richtárik. Canita: Faster rates for distributed convex optimization with commu- nication compression. In Proc. NeurIPS'21, 2021.
Cheuk Yin Lin, Chaobing Song, and Jelena Diakonikolas. Accelerated cyclic coordinate dual aver- aging with extrapolation for composite convex optimization. In Proc. ICML '2, 2023a.
Sen Lin, Peizhong Ju, Yingbin Liang, and Ness Shroff. Theory on forgetting and generalization of continual learning, arXiv preprint arXiv:2302.05836 2023b.
Zijian Liu and Zhengyuan Zhou. Revisiting the last-iterate convergence of stochastic gradient meth- ods. In Proc. ICLR 24, 2024a.
Zijian Liu and Zhengyuan Zhou. On the last-iterate convergence of shuffling gradient methods. In Proc. ICMI. '2, 2024b.
12

---

Published as a conference paper at ICLR 2025
Sharon L Lohr. Sampling: design and analysis. CRC press, 2021.
David Lopez-Paz and Marc Aurelio Ranzato. Gradient episodic memory for continual learning. In Proc. NeurlPS'17, 17, 2017.
Michael McCloskey and Neal Cohen. Catastrophic interference in comnectionist networks: The sequential learning problem. In Psychology of Learning and Motivation, volume 24, pp. 109-165. Elsevier, 1989.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik, Random reshuffling: Simple analysis with vast improvements. Proc. NeurIPS'20, 2020.
Konstantin Mishchenko, Ahmed Khaled, and Peter Richtárik. Proximal and federated random reshuffling. In Proc. ICML'22 22, 2022.
Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. SGD without replacement: Sharper rates for general smooth convex functions. In Proc. ICML'19 19, 2019.
Lam M Nguyen, Quoc Tran-Dinh, Dzung T Phan, Phuong Ha Nguyen, and Marten Van Dijk. A uni- fied convergence analysis for shuffling-type gradient methods. The Journal of Machine Learning Research, 22(1):9397-944) 2021.
German Parisi, Ronald Kemker, Jose Part, Christopher Kanan, and Stefan Wermter. Continual lifelong learning with neural networks: A review. Neural Networks, 1 11::4477,, 2019.
Binghui Peng and Andrej Risteski. Continual learning: feature extraction formalization, effi- cient algorithm, and fundamental obstructions. In Proc. NeurlPS'22. 2022.
Liangzu Peng, Paris Giampouras, and René Vidal. The ideal continual learner: An agent that never forgets. In Proc. ICML'25 23, 2023.
Shashank Rajput, Anant Gupta, and Dimitris Papailiopoulos. Closing the convergence gap of SGD without replacement. In Proc. ICML'20, 2020.
Anthony Robins. Catastrophic forgetting, rehearsal and pseudorchearsal. Connection Science, 7(2): 123-146, 1995.
David Rolnick, Arun Ahuja, Jonathan Schwarz, Timothy Lillicrap, and Gregory Wayne. Experience replay for continual learning. Proc. NeurlPS' 19, 2019.
Andrei A Rusu, Neil C Rabinowitz, Guillaume Desjardins, Hubert Soyer, James Kirkpatrick, Koray Kavukcuoglu, Razvan Pascanu, and Raia Hadsell. Progressive neural networks. arXiv preprint 1606.06606. 2016.
Itay Safran and Ohad Shamir. How good is SGD with random shuffling? In Proc. COLT" 2020.
Ohad Shamir. Without-replaemment sampling for stochastic gradient methods. In Proc. NewrlPS 16, 2016.
Ohad Shamir and Tong Zhang. Stochastic gradient descent for non-smooth optimization: Conver- gence results and optimal averaging schemes. In Proc. ICML' 18, 2013.
Chaobing Song and Jelena Diakonikolas. Cyclic coordinate dual averaging with extrapolation. SIAM Journal on Optimization, 33(4):2935-2961. 2023, doi: 10.1137/22M1400004
William Swartworth, Deanna Needell, Rachel Ward, Mark Kong, and Halyun Jeong. Nearly optimal bounds for cyclic forgetting. In Proc. NeurlPS'24, 2024.
Trang H Tran, Lam M Nguyen, and Quoc Tran-Dinh. SMG: A shuffling gradient-based method with momentum. In Proc. ICMI.211 2021.
Trang H Tran, Katya Scheinberg, and Lam M Nguyen. Nesterov accelerated shuffling gradient method for convex optimization. In Proc. ICML 22, 2022.
13

---

Published as a conference paper at ICLR 2025
Jachong Yoon, Eunho Yang, Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint arXiv:1708.01547, 2017.
Hengxu Yu and Xiao Li. High probability guarantees for random reshuffling. arXiv preprint arX1v:2311.11841, 2023.
Chulhee Yun, Shashank Rajput, and Suvrit Sra. Minibatch local SGD with shuffling: Tight convergence bounds and beyond. In Proc. ICLR 2022.
Moslem Zamani and François Glineur. Exact convergence rate of the last iterate in subgradient methods. arXiv preprint arXiv:2307.11134, 2023.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning (still) requires rethinking generalization. Communications of the ACM, 64(3):107- 115,202, 2021.
14

---

Published as a conference paper at ICLR 2025
Table I: Comparison of our results with state of the art, in terms of individual gradient/proximal oracle complexity required to output Tout with f(oo f f(x.) S c (IGD and IPM) or [
f(x,) } I c (RR/SO), where 0 is the target error and æ. the optimal solution. Here, o²
E (e..,) D = ||00 - a. 1|2, and (.) suppresses up to square-root-log factors of 1/e.
PAPER
ASSUMPTION
AVERAGE ITERATE COMPLEXITY
LAST ITERATE COMPLEXITY
MISICHENKO BT AL. (2020)
NGUYEN (2021)
(IGD)
fe: L-SMOOTHL
O TLD2
TVEo, 372
CAL ET AL. (2024)
[Ours]
(IGD)
fo: S-OOOOHH CONVEX
O TLD
TyTr 02
O TLD
T.r. 3/2
3/2
MISHICHENKO BT AL. (2020)
CHA ET AL. (2023)
NGUYEN AL. (2021)
(RR/SO)
L-SMOOTH CONVEX
O TLD
+ VTL.,
3/2
CAI ET AL. (2024)
[Ours]
(RRISO)
L-SMOOTH, CONVEX
TLL22
TTL 3/2
O TLD2 3/2
NTI,,
BERTSEKAS (2011)
(IPM)
J:: LILISCHITZ CONVEX
O
LI (2019)
[Ours]
(IPM)
f:: L-MOOOTH CONVEX
O TLD2
Tvlaa n2
6 TLD2 TvLa, n2
[Ours]
(IPM)
f:: G-LUSCHITZ, CONVEX
O T2222
O (2
A RELATED WORK
We first provide Table 1 for comparison of our results on incremental methods with the state-of- the-art on average iterate convergence.
To remedy catastrophic forgetting, various empirical approaches have been proposed, corresponding to three main categories: (i) memory-based approaches, which store samples from previous tasks and reuse those data for training the current task (Robins, 1995; Lopez-Paz & Ranzato, 2017; Rolnick et al., 2019); (ii) expansion-basee basud approaches, which progressively expand the model size to accommodate new tasks (Rusu al., 2016; Yoon et al., 2017); and (iii) regularization-basee approaches, which regularize the loss of the current task to ensure the new model parameter vector close to the old ones (Kirkpatrick al., 2017); for more complete survey, we refer to De Lange et al. (2021). Our focus in this work is on (i) and (iii).
On the theoretical front, the majority of existing work for the settings consider has studied catastrophic forgetting for overparameterized linear models (Evron et al., 2022; 2023; Lin et al., 2023b; Goldfarb & Hand, 2023; Goldfarb al., 2024; Swartworth al., 2024) or under the neural langent kernel regime (Bennani et al., 2020; Doan et al., 2021). Another related line of work studied the task similarity in CL under the teacher-student learning framework (Asanuma al., 2021; Lee et al., 2021). A recent work showed that an algorithm recursively minimizing the loss of the current task over the solution space of the previous task, named the ideal continual learner, never forgets, assuming all tasks share a common global minimizer (Peng et al., 2023).
When it comes to the eyclic forgetting that this paper focuses on, theoretical results have only been established for linear models (Evron et al., 2022; 2023; Swartworth et al., 2024). In particular, the analysis for linear regression tasks Evron et al. (2022); Swartworth et al. (2024) crucially relies on the exact minimization of each task using (S)GD to have closed-form updates between tasks, while Evron et al. (2023) uses alternating projections to analyze linear classification tasks. It is unclear how to extend either of these results to general convex loss functions that consider.
On a technical level, our results are most closely related to 1) the literature on last iterate conver- gence guarantees for subgradient-based methods and stochastic gradient descent (SGD) and 2) the
15

---

Published as a conference paper at ICLR 2025
literature incremental gradient methods and shuffled SGD. For 1), we draw inspiration from the recent results (Zamani & Glineur, 2023; Liu & Zhou, 2024a), which rely on a clever construction of reference points &5 with respect to which gap quantity f(æx) - f gets bounded to deduce a bound for the optimality gap I (xxx - f(x..) of the last iterate I.. For the latter line of work 2), generalize the analysis used exclusively for the optimality gap of the (uniformly) average iter- ate (Mishchenko et al., 2020; Nguyen et al., 2021: Cha et al., 2023; Cai et al., 2024) to control the gap-like quantities f(xx) f(=x-1), which require more careful argument for controlling all er- ror terms introduced by replacing æ. by 2k-1 without introducing spurious unrealistic assumptions about the magnitudes of the component functions' gradients.
For further comparison with the works on last iterate guarantees (Zamani & Glineur, 2023; Liu & Zhou, 2024a), we note that Zamani & Glineur (2023) study subgradient methods for a single deter- ministic objective function in convex Lipschitz settings. Since the work is not dealing with finite sum objectives and incremental updates, the foeus is different and the algorithms are not directly comparable, barring for trivial cases (e.g., setting T = 1 in our results). Further, Liu & Zhou (2024a) study the last-iterate convergence for classical SGD with replacement sampling, in stochas- tic convex settings. The major challenge in setting is that the functions are accessed in cyclic order, as opposed to being randomly sampled as in Liu & Zhou (2024a). We note that analyzing SGD with cyclic ordering of component gradients (as opposed standard SGD that uses random sampling with replacement) was a major open problem for decades (Bottou, 2009), while existing results rely on completely different analysis. For additional results on the last iterate convergence of classical SGD, which is less relevant to this work, we direct the reader to the references in Jain al. (2021); Liu & Zhou (2024a).
We finally note that both these related lines of work concern problems on which progress was made only in the very recent literature. In particular, while the oracle complexity upper bound for the aver- age iterate of SGD in convex pepschitzzcontinune
settings has been known for decades and its anal- ysis routinely taught in optimization and machine learning classes, there were no such results for the last iterate of SGD until 2013 (Shamir & Zhang, 2013) with improvements and generalizations to these results obtained as recently as in the past several months (Liu & Zhou, 2024a). Regarding 2), obtaining any nonasymptotic convergence guarantees for incremental gradient methods/shufiled SGD had remained open for decades (Bottou, 2009) until a recent line of work (Gürbüzbalaban et al., 2021; Shamir, 2016; Haochen & Sra, 2019; Nagaraj et al., 2019; Ahn et al., 2020; Rajput et al., 2020; Yun et al., 2022; Safran & Shamir, 2020). For nonconvex problems, Yu & Li (2023) proposed a stopping criteria for shuffled SGD and proved the high-probability guarantee for the ex- iting point, which is technically disjoint from our work. For smooth convex problems we consider, the convergence results were obtained only in the past few years (Mishchenko et al., 2020: Nguyen et al.. 2021; Cha et al., 2023) and improved in Cai et al. (2024) using a fine-grained analysis in- spired by the recent advances in cyclic methods (Song & Diakonikolas, 2023; Cai et al., 2023; Lin et al., 2023a). However, all those results are for the (uniformly) average iterate, while obtaining convergence results for the last iterate had remained open until this work.
An independent and concurrent work to ours (Liu & Zhou, 2024b) studied the last-iterate conver- gence of shuffled SGD for composite (strongly) convex amoothh/Lipschiin optimization. For the same problems as studied in our Section 2, they obtained the same convergence results. The remaining results in Liu & Zhou (2024b) and our work are not directly comparable, as the motivation for the two works and the studied settings are diffferen: we do not consider composite optimization settings for shuffled SGD/incremental gradient nor strong convexity of component functions, while Liu & Zhou (2024b) did not consider the incremental proximal method (our Section 3). It is of note that while Liu & Zhou (2024b) used proximal steps to handle the nonsmooth portion of the objective in their composite setting, the proximal maps are not applied component-wise, but the end of cycle, to only one (regularizer) function.
Further discussion on other related topics. In the context of more general finite-sum minimiza- tion, one interesting application of our results is in federated learning, where most of the existing results are proved for the average iterate; see e.g., Alistarh et al. (2017). Last-iterate results in fed- erated learning have only been obtained for different algorithms without incremental updates over component gradients, see e.g., Li (2021); Li & Richtárik (2021). Hence, our last-iterate results are still new, even to the field of federated learning.
16

---

Published as a conference paper at ICLR 2025
Incremental methods this work focuses on also have natural connection to cyclic coordinate meth- ods. However, the results for cyclic coordinate methods are not directly applicable to deriving convergence guarantees for incremental methods. For the direct reformulation of finite sum mini- mization to 2i... + Σi zt; s.t. 24 (z) (t E [2') with introducing additional vari- ables, one needs to handle nonseparable constraints associated with generic functions 2, f.))). These constraints are nonconvex unless ft's are linear. In most works on cyclic block coordinate methods for composite optimization (see e.g.. Cai et al. (2023) and references therein), the regular- izer assumed be convex and generally cannot enforce such hard constraints. It is worth noting that Chorobura & Necoara (2023) derive convergence results for the last iterate of cyclic coor- dinate method applied to problems with nonseparable constraints. However, Chorobura Necoara the regularizing function, such either being weakly con- vex with easy proximal steps or being concave along coordinates with additional assumptions made about its Hessian. Their last iterate result also depends uniform bound the iterate distance to optima, which would be ill-defined if ported to the setting of incremental methods.
(2023) require additional assumptions
B OMITTED PROOFS FROM SECTION
Lemma 1. Under Assumptions 1 and 3, for any IR that is fixed in the k-th cycle of Alg. I and any a, B > O such that + S 2' if S VBT1. then for all k E [K].
T(f(x)) f(z)) S nhL Σi=l ET= Vf((a=)) [T(((z) - f(xx))
1n (1 2112 ||>0 =1(2).
Proof.
Since each ft is convex and L-smooth, we have for E [T] (see Eq. (3)):
1
f((xx) - fe( (Vf((z)), x - xk-1,1)
Vf((2x)
(9)
21
1
f((0-11)-- (V 26-11
Vf(
Vf(2))]
(10)
2L
On the other hand, letting .)-1,(<)) (Vfi(Ex-1,t) + 2n x x x1 we have
V V by the update 24-1,111 21-1,1 7p (2 in Alg. 1. Observe
that 4 111 is -strong convex, and thus also have t
1
$ (z))( 2 D (2-11((1-1441)
||z 24-1,14112
(11)
27k
Summing Eq. (9) and (10) and using Eq. (11), we conclude that for E [T].
f - fe(z) S (Vi((a)), Tn 1,)) + (V Vi 1,r): D6- - 2h- 1.
1
Vf((
1f((
Vf((
f2((2))12
2L
21
1
|
24-1,112
(||
=11
| 11441 - =1112
2m7
2nk
17

---

Published as a conference paper at ICLR 2025
Decomposing V/d we recall 1k-1 = 2k-1,1 and Zyz = 24-111+++ we have
and summing over [T]
where
1
T(f(x)) f(()) 5
1.)) 22 12-11+1)
2 1,+-1,01111
11e1 ?1
2TT
Ti
Vf((())) (f(( 2h x2-1,17
T2
T
T
Vf(()))) - Vf((
-
2L
2L
1
(| - =|12-1|a>; =11)).
2TjE:
For the term Ti, we recall that by the IGD update, V (x =
(ak- - Ik--1,)) and
E (2R-1,541 - 1,),, and thus we have
Cg 1,141
1
Ti
(00--1244 1,411 Lk- LR 22-1-111 1,811 10k-1,))
02-1,1+1 1
27Th
T
(o (x1-1.0+1
1---1a
||00
xx x211 S..
21jR
21/2
t=1
For the term T2. noticing that I6 - 1k- = - Σ Vf. (x and decomposing
==
(z (Vf. - fz())) + (Vf((z) -Vf(z)) + Vf.)), we use Young's
inequality with parameters a >> 0 and B > 0 to obtain
T2 [((()))) - Vfi( The
V (
(=1
1
[1(x))) - (++
2T.
a
3
T
amp
L
Σ ([((=))-(a((..)))
+ m
Σ v sa (xx) 1
2
3n
L
T
Σ
T
(V (fa==)
2
s=t
Further using that we obtain
|
1
<
Σ -
|| and combining the above bounds on Ti and T2.
1
1
T(S(#k) - [(z))
S
+
[((()))) - V
21.
a
2
T2
+
2T.
2m221 L
T
T
T
[1) - vf((x))) )1 + n
Σ
v fa (z.)
2
a=t
+ 2m
(1
2112
1| 2112),
18

---

Published as a conference paper at ICLR 2025
To make the first two terms on the right- hand side both nonpositive, choose
1
1
1
+
-
7he =
3
2
VBTL
We further bound the term Σ [Vf((z) vf((a.)) by the smoothness and convexity of each
fi as follows:
T
T
- ((d(z)-VA((x)))
< 2L t=1
Σ (Je(z)-Jeca4) - -e((e)) (V((a.)(VV((xx.)) --xx) x.,)
= 2 - f(xx)).
where in the last equation we used Vi((x.)
0. Hence, we finally obtain
T
T
T(f(xx) f())) - D
V fz(
)|
m ff(x)))
1=1
8=1
(1|=)~-1
x1|² 1 -1 -2 -213)
217
T
S mh
L
Σ (ax)))) 1|
+ a
3z TT((() - ((x)))
(1|0 z1| 2||--1 1
=1
21/R
where we used yis S VOTE
1 in the last inequality, thus completing the proof.
Lemma 2. Let 2k be defined by Eq. (4) for given sequence of parameters d E (0, where 2 O and 2-1 = v.. Under Assumption 1, if there exists a sequence of nonnegative weights wa such that 7 wk-1 for k E [K 1). then for all k [K]:
Wk- 1 (f(xx f(x))) S Ei-o wy (f) f(x:));
2. Wk-
wk-1 1 (f(xz) -f f(zb-1)) 2 w)-1(f(xx)) f((x))()))))))))))))){)}{))))- - - (1 - (f)(f(z)) - f(xx)).
Proof.
1. Using Eq. (5) and the convexity of f, we have
f(zx-1) f(x.)
k-2 k-1
s (1 (1- (1--x-1) (1- f(x)))
f=0
1=/+1
It remains to multiply by wk-1 on both sides and notice that by the lemma assumption
k-1
k-2
Wh-1( II x1 A1) S wk
II
x))1 ())- ())--)) ....ssus 51 Az).
1=1+1
i=$+1
2. This follows from the first part of the lemma, by decomposing f(xx) f(xx-1) f(xx)
f(x.) (f(* - fx.)).
Theorem 1. Under Assumptions 1, 3, and 4 anr positive parameters a, 3 0 such that
+ 5
2. if the step size is fixed and satisfies Tp-- = 1) Σ VBTL the output æ of Alg. I satisfies
f(xx) f(x.) < TT [(1 k//0 K1
0ig
e e| x.
(6)
2n7 14973
19

---

Published as a conference paper at ICLR 2025
In particular, for a = =,3 4 loog K, and 17 = min {
L //a////////// KY1/8 2/log KTL }
1100 20 2/33
2///Te22 2/3
f(xk) f(xx) = 0 - [1'1902 1,20 m. (1//(1 kY1/S ml ma 1 Mog R f(x.) S after Ö( [Lille =. + TL TL
and thus fxxx)
K3y3
2 20, 1 individual gradient evaluations.
Proof. Plugging - defined by Eq. (4) into Lemma and using the inequality || -
E== ||2 to bound the term Σi=1 EEe1 fz. obtain
T(f(ms) f(2x-1) T m + T (f(= f(xx))
27/ || - z 1x11 1121112-1200 -
1|200
112)
where : + 1 - 2- Multiplying 1 on both sides with wy such that 2x S wk-1 and noticing B
that 1| - 1| A xx-1 2x by Eq. (4), we have
T THawk-1 (S(zz) f(zx-1)) S T 11 Luck + TT.uR- (J(Zx-1) f(x.))
w 1 - 22-2 Wk
1| 1k-
zk- 11?)
We then sum over k E [K] and use Lemma 2 to obtain
K
R-1
T
Thk
Wh wk-1 ( (f(xx) - f(xx)) - Σ (95(11;;)6
(f)=(())) f(xx))
k=1
1=0
(12)
K
k-
S ST
Σ
lie Wk
+
w-1 2
100
2.112 +
I
Σ
Tkk
Σ (f)(((())()))) - f(x.)),
-
k=1
k=1
1=0
where we also use 2-1 = v. Unrolling the terms w.r.t. f(x)) - ((x)) (k E [K]) we get
Wk-1 (f(zz) - f(x))) - k-1
Σ wy(l
- -(a)))))
m
7 m T (f(xx) - f(xx)) -wo(1 - (o)(f((0)) - -(xx)) Σ
(13)
k=
K-1
K Σ (F)((())) - f(xxa)
mkwk-1 - wx(l As)
1=1
$=++1
and
K
K
Σ
- 11, Σ ww >xa Σ 11) f(x)))
Th
0=
j=k+1
Plugging back into Eq. (12), grouping the like terms, and choosing do = 1, we obtain
Tykwk-1 (fxx) - (xx)))
K
K
+T
m Wk - (1+ a ) (1 - Xx)
Σ
no (f(xx)) - -f(x))
3
(14)
km1
jmk+1
K
<T 0 L
mh Wk
+
W-
xD xz 12
2
To obtain the last iterate guarantee, it suffices to choose wi and 2 such that
W S wh-1, 0 O K
(15)
K
7 7h - (1+ a g) wu As)
3
Σ
m 20
1
(16)
j=k+1
20

---

Published as a conference paper at ICLR 2025
Noticing that Eq. 16 is equivalent to X at the same time, it suffices that
1-
The Wk
to have both inequalities satisfied
(1+
wh ΣK p 75
Th + (1+ () K 25 13 Wk
Wk-1
Wk-1-
(1 + 3) wk 2j=k+1 ?2j
Wk
(1 +1+ 3) Ej=k+1 f3/
The (1+ 3 k11 25
To maximize the growth rate of {w we let wk
(1+ 23 2 +1 nij Wk-1- Without loss of (1+)) 73
generality, we take w-1 wp I + () Σ ビ %
and thus WK-1 1. Hence, dividing
both sides of Eq. (14) by Wn and choosing the constant step size TBs = 1 for all E [K], we obtain
K
f((k)- f(xx) S 17 2222002
o.
Wk-1+
+
W-1
-x.112
(17)
2T
We first bound w-1 = I +) ing the natural logarithm of w-1, we have
K-1 (1+ k))
K
(1+
with the constant step size. Tak-
k=
I+(1+
K
K-1
K K-1 1
log (1 (1- (1-I+(1+9))
1+ (1+ k
k+1
k=
where for (i) we use the fact that log(1 + 2) S for x > -1 Further noticing that Σ 1 k+1
>x kml - 2 log(K) + K - 1, then we have
1
e1/(1+a/3)
log(w--) 1) 1 B
log( K) + 1
w w- S
KIru/
KIFaT
(1+ (1+))(-1)
K-* (1+3))
On the other hand, we note that wa-1 I1 I+ KK--
I+(1+3) for 1 S k: s
K 1 and WK-1 = 1, then we follow the above argument and obtain
K
K-1K-k
(1+
Σ
Wk-1
1+
Σ
II
1++1+ })1
< 1+
K-1
Σ
c
(0) e(1 + a/3)
K Ki-018
ai8
a/3
(K - + 1) 140/8
k=
where (i) is due the final bound:
2k=2 19
1
52
K+1
(x-1)5 dr 11-9-1
1-9
for any 0 q < 1. Hence, obtain
f(xx) f(x.) S 2T L + 3/a)
1777
a/a
c||20 x. 12
2T 140
To analyze the oracle complexity, we take
|00 12/3
" min 21/3To2 11ak://11// 8/o) VBTL
and analyze the two possible cases depending which term in the min is smaller. If the first term in the min is smaller (which we can equivalently think of as K being "large"), we get
3.5(1 + 1//a) 1/3 1/3/3 2/3 Imo x. 11,11/3
f(øK) - f(x.) <
K 1773
Alternatively, if 17 "small" K), obtain
1100 22 2/3
(which we can think of as having
VBTI.
21 21/3To2
11/3 (1+8//))1/
1.8(1+ 3/a) // L 1/3 2/3
2 1//3
1.4/BL 2D x. 12
f((x) - f(x,) <
K 14073
K 1+175
21

---

Published as a conference paper at ICLR 2025
Hence, combining these two cases, we have
f(æK) f(x+)( 3.5 18 2/3
20 120 x. 1//11//3
1.4vBL| x xx 11
K KT4073
K 14077
In particular, we choose a and [ log K, assuming without loss of generality that log > w/9
1, then we have K K1ta/8
KLE [acKF S e and thus
9.4L 4o x. x.1 f(Øx) - f(x,)
log K)*
7.4L zo
x. Vog
K á
K
To guarantee f(xx) - f(x.)= < given > O, the total number of individual gradient evaluations will be
TK δ x0 x.
TL x xt 112
3/2
Corollary (Increasing Weighted Averaging). Under Assumptions 1, 3, and 4 and for parameters a, such that 1
3 S 1. if the step size yj is fixed and such that S JBTI' then for any
constant e E (0, 1] and increasing sequence {wx 1k=) with (1+a/D)(K -k)-K-k)------------ (1+a/8)K wk-1. Alg.
oulputs dK =
We 14
satisfying
Er= 1
f(xx) f(x.) S 2222 +
11 2enlKK
In particular, taking 8 = ((1) and the step size min f(ok) f(x.) S after O (L
1000000 11 )2/33, we have
VBTL
2
22.1" + T 12, w. 332212
individual gradient evaluations.
oE
Proof. We follow the proof of Theorem 1 up to Eq. (14) with constant step size f). then we instead take d wk-1/wg and w/ (1+3)(K-X)
(1K -k)+1-c
uk to obtain
T Σ WR w (f((s) f(xx)) S TT L Σ Wk + w-1
||00 - x.1
Since convex, we have f((x) f(x)) S
EK wy
where ox
ΣK Wh-1
ΣK
W2-1 is the increasing weighted averaging of (#x E WE-1
) k= thus (cf. Eq. (17))
T2o2 +
||00 x. 1.1
T2o2n2 +
Do x.11
f(ix) f(xx){
f(xx)
2CT Σx= Wk-1
2enIK
where the last step is due to ΣX_ Wk-1 2 Kw-1- Then we follow the proof of Theorem 1 and
choose 7 = minf VBTL (29 LK
x.l"
}1/37 to obtain
/BL| - x.I2
1/3
0. 20 x. 4//
2/3
f(Øx)-f(an - f(xx)= <
2cK
ck2/3
To guarantee f(xx)- f((x))) S e for > O, we choose O(1) and the total number individual
gradient evaluations will be
TL [o xx 12
1/2 0 1 x.. 1
TK = 0
3/2
thus finishing the proof.
22

---

Published as a conference paper at ICLR 2025
Corollary (Shuffled SGD (RR/SO)). Under Assumptions 1, 3 and 4 and for positive parameters a, B > such that :/ + I 2. if the step size is fixed and such that rj S VBTL' the output æ of
Alg. I with uniformly random (SO/RR) shuffling satisfies
2/8 B[f(zk) f(x))) 2 onfoTTL(1 8/a)
14078
el x
2Tnk 11773
With = 4,3 4log K and 17 min {
200 22
L1/B (1+tg K)a/s* 2//og KTL) }. have
||//a
21/312/30
B[f(ox) - f(x,)] S e after Ö [ m.ll TTL.,
|| =. e3/2
individual gradient evaluations.
Before proceeding the proof of Corollary 2, it helpful first introduce a lemma to bound the term Ei Σx=t (x.))l) in Lemma 1.
Lemma 3. Under Assumptions 4 and for Alg. with uniformly random (SO/RR) shuffling, we have
a (fa(x.))11 < T(T+1) 02
6
Proof. We first consider the case of random reshuffling strategy. Conditional on all the randomness up to but not including k-tth epoch, the only randomness of EE(Ei=> || Σ Vf((a))) comes from the permutation (k) at k-th epoch. Further noticing that each partial sum Ei=r (ar.) can be seen as a batch sampled without replacement from { (V (xx,)) (ax)))))) we have
T
T
T
Ex
V (z.
Σ
Σ amt
V fe x
|
Σ
T
(T 11- 1)2B
| 1
Σ
T
V (x.)))
17
T-1+1
t=1
8=
t-1
Σ
(T ++ 1)2
(T (1- 1)(T - 0
t=1
T(T + 2
where (i) is due to ET, (z(x)) 0 and sampling without replacement (see e.g., (Lohr, 2021, Section 2.7)). It remains to take expectation w.r.t. all randomness on both sides and use the law of total expectation. For the case of shuffle-once variant, we can directly take expectation since the randomness only comes from the initial random permutation, and the above argument still applies.
Proof of Corollary This follows the analysis the proof of Theorem 1, with taking expectation w.r.t. all the randomness on both sides of the inequality in Lemma I and using Lemma 3.
L
C OMITTED PROOFS FROM SECTION 3
C.I CONVEX SMOOTH SETTING
Lemma 4. Under Assumptions I and for any R.d that is fixed in the k-th cycle Alg. 2 and
1. if the step sizes satisfy m JJTT. then we have for for > 0,3 > O such that 1 + 2,
[K]
T(f(#u) f(x)) S T Σ
Σ
+ -(((())-((
s=t+1
(18)
+ 21)k
[1
2|12 - || =1
23

---

Published as a conference paper at ICLR 2025
Proof. Since each fi is convex and L-smooth, we have for t [T]
f((2x) f1(00x11141) v (Vf((x))) 02 - xx-1,++)
[V(((x)) V
21.
1
f((=x-1,++)) fz(=) S (
Vf((
-
Vf((2)]
2L
Following the proof Lemma 1, we add and subtract Ene
F 1,a =|
on the right-hand side of
the second inequality and combine the above two inequalities to obtain
- 5 (Vf((zx), xk-1,++)
2k-1,0+1 2x-1.e
2TJ
2T. (IVf(((a))
V 1]1
[[V V=(())11))
1
(11 =112
2 xt- 1,441 -
21RR
Decomposing Vf(((x))= = (((())) (1( +V (=x and summing over & [7),
we note that x = 1,1 and Fg 1x-177+1 and obtain
T(f(*;) - f()))
T
T
V ( 2k-1,141)
1+-11 217
(V(((a))) (1
,), ax xx- 1,441
(1 - =112 ==|²-110 -1|arx =11²)
21T6
T5
T
1
2L. [f(((x) - Vi(
2T
For the term Tr, we follow the argument from the proof of Theorem obtain
Ti =
|| D3
xx-1 s O.
21Tx
For the term T2, noticing that 2. -,,, Σ Σーー (I for - decomposing (T = (V (f. + vf. (z.().),
we use Young's 's inequality with parameters a > and 8 > 0 to obtain
T
===
=
(((s)) (f( -76
Σ
(f
==t+1
1
+
[((x)) Vf(
21 2
3
an
L.
T-1
T-1
Σ (V((()-v\.(a))
mLL
Σ vfs(z.)
3n T
T
24

---

Published as a conference paper at ICLR 2025
Further using the fact that and T2, we obtain
|E
æill?
n
Ei=1
|æ, and combining the above bounds Ti
T
1
1
1
T(f(=)) f(x)) = 2L
+
(Vf((a)) V=((==-1,0)1
a
2
T
[V V.f(()I1
am
L
T
T
Vf((z)) Vf((x.)) + nパ
Σ
f.
2
s=++1
(1 - 2112 - ||00g =1
27t
The rest of the proof is the same as the proof of Lemma and is thus omitted.
Theorem 2. Under Assumptions 1, 3, and 4 and for parameters a, B > 0 such that + the step size is fixed and such that S VQTI. the output æ of Alg. 2 satisfies
B 2 if
f(xk) - f(xx) S T oZ + 10/8 +
elI
24/K 14978
With 4,3 4log K and 17 min
a. 1//3
/////////11111 log K) 2v/nng KTT, }. we have + Li
21/3T 273
f(Øk) - f(xx) = 0 1.10 1 1am0-mm111 (1 Hog K)J/a
Alog and thus f(xx)
K2/3
K
f(x.) c after Ō( TTTllk00-a 1. o2. |120 x. I1²) individual gradient evaluations.
Proof. This follows Lemma and the proof of Theorem 1.
Theorem 3. Given L and T 2 2, let FI.L be the class of finite-sum functions f(x) 1 Ei= fc(x), with each component ft being L-smooth and convex. Then:
For any fixed step size 1), there exists a function f E FT.L such that the iterates æy of Alg. satisfy f(xx)= f(xx) + 0 as + As consequence, the forgetting is catastrophic.
For any fixed step size 13 that only depends on the parameters of the problem class (L, T, error E), there exists function f E FT.L such that the iterates æa of Alg, 2 satisfy lim f(xx) - f(x.) > 1.
3. Given >> 0, if the fixed step size satisfies 1) 2 min { 16V5 Fr.L such that the iterates 3i of Alg. 2 satisfy f(xx) - f(x.) > e for all sufficiently large
VTLL. TL then there exists function
Proof. For all parts of the proof, we consider I-dimensional quadratics
T
f(x) = Σ [((x), where f((x) = 1/1 (xr -,,)
6z)²
fort E [T]. L > and appropriately chosen sequences of ( C IR.
It is immediate that f(r) is minimized at x, 7 ET= 8,. Observe that Alg. 2 using a constant step size 17 > 0 has closed-fom updates on f. i.e.,
T
Ik+1 " (1
7)
Σ
T T-(
1=1
25

---

Published as a conference paper at ICLR 2025
where 7 n1.11 (0, 1). Given any initial point Tu, by iterating have
T
1 (11
7)(1
AT)
1
Iz 7
KT
2o
+
1 1-72
T
67
(19)
t=1
T T- -7)
1
bc.
(20)
1
7
T
1. Consider the weight 8T in Eq. (20). Since y E (0, 1). we have
1-7 1
21 7d T > 0.
g0 T
Then for any (5. (ET)) such that sgn();) = sgn
-
(1-2)
7)
and 8r > 0, we know that
1-q²
lim f(#x) - f(x.) ( lim (Tx-
/ 1 7
1 2
2 k-000
x.)²
2 1 --
T
84 > 0,
where (i) is due to f being both L-strongly convex and L-smooth.
Consider the weights of 6, in Eq. (20). Since y E (0, 1), we have
0 -- - 7)
1 9- < ---
T- $
thus for any & E [T- 1]
3 (1 7)
1 T-1)
E
T
T
For 6- = T, given any fixed 7 < 1, we have
1-7
T 0.
1- T
Et=0
7t
Hence, for the sequence {ō.} such that
T/2/L
2 2/L
|&|| < (T 1)² (TE 1]), 8r >
then combining the bounds on the weights of with Eq. (20) obtain
T- -7)
1 6,
lim TK
x
Σ
1-
1=1
T-1 T
1 1-9
1
T
6T
Σ
18cl
T
22
Since f is L-smooth and L-strongly convex, we know that
lim f(xx) - f(xw) = lim (I+ - =x,)²> > 1, k-000
2 k
thus finishing the proof of the second part. We note in passing that I on the right-hand side can be replaced by any constant using simple rescaling.
26

---

Published as a conference paper at ICLR 2025
3. Observe that given fixed step size n > 0, we choose sequence {oe hE(T such that
sgn(6;) sgn (1)()))) 1-7" +) for all t [T] thus for any initial point zo x,:
f(xx) f(x.)= = L ( (zo - xx) + (1 x RT) Σ
(1 7) } 2
2
1-
T
1=1
(1 2
TT- 7) )
1-77 T 0g
2
1-1 -7)
- 1 1) (" 7-77 T o,ōr. )opo.
n7 T- (1-)) 7)
1
+ 2
1-
(1-2/\3 T
Without loss of generality, taking a sufficiently large
we obtain
T
(xx.) 2
2L 5
7)
7
1
o9.
7-
t=1
Then for any step size 2 1/TL, we have ?
1
<
T
Consider t = T, we can bound
nLI1
T+I
1 1-7 1
T
1
1
-1)>
c-1
1 1-7 T
T
(1
7)
T
V5TVE 12(
Thus, for 67 2
we have
2L
1 1-7
7
2
f(zx)- 2
7T T
07 >E E.
5
1
On the other hand, recalling the definition in Assumption 4, we have in this example that
2
dc
2
2
1t=1
T
6,)2
EE 5,)2
T
o:
5z
I
ST
T
T
T
T
T
t=1
Thus for any step size 1 2
16VE
2
16vE
we have 7= nL+1
of
VTLo. 13/2
57'
16 T++ v /ET 69
We now proceed by bounding the weight of &r. particular, let x. for some k > and assume that I T+I
< T without loss of generality by the discussion above. Since xT < 1 and
1
T 1 2, we have
R TT
(I= 21- xT
4
which leads to
2
TT 1)
1 - TT 1 - (1 k)T s KT
4
Hence, we have
1-7 7
2
1 7T
KT
T (-11)
T 1 - R(T - 1)/4
Further noticing that
21 <(T 1)
RT
1 +
I 1- -[" - 1)/4
4
8
for T 2 2 and K < 1 then we have
1-7
1 1
KT
1
1
-- T
T
8
T
27

---

Published as a conference paper at ICLR 2025
VE of 16 16 // E/-1 of
Recall that 7
then obtain
1 -
2
L
1 77
16 L/L V V 67
V o8
for ( such that V E of 2 16 16 + v3) V Thus, for the sequence (deher such
that 67 2 Ex= of and (g,) = sgn 2 1-9"
(1-7) 7). . we have
2L
(1 (1-7)
f(xn) - ((x.) 2
7 87
5
1 -
2L
3:8
5 L E 87
6,
completing the proof.
C.2 CONVEX LIPSCHITZ SETTING
Lemma 5. Under Assumptions I and 2, for any x E IRd that is fixed the k-th cycle of Alg. we
have for l [K]
(11=111- - x112 -| - -21 T(T 1)G2TH np
T(f(xx) - f(z)) - 2//x
(21)
2
Proof. Since Se is convex and closed, we have
1
M Is (xt=
(I=-1,1 xx-1.441 E 0ft (T)
Thk
By G-Lipschitzness of each component function, we have that for / E [7
fx f((xx-1,0+1)
(22)
S G| I4-1,4+1l S G& Σ | (Ix-1,0) (T -
On the other hand, using convexity of ft, we have that for 1 E [T] fz(z) 2 fo f((xx11041) + MMM (xx-1,t); xk-1.44))
Expanding the inner product in the above inequality leads to
f((2x-1,141) fz(z)
1 (0 -k-1.++1 2 - xk-1,
<
7
1
1
27j (1 211² 2 1,1+1 =113)
| 14-111+1 21,11
(23)
2n
Combining Eq. (22) and (23) and noticing that 24-11744 inequalities over t E [T] and obtain
x and Øg-1,1 2k-11 the
1
T(T - -1)Gamm
T(f(#)) f(z)) <
(1 - 2/|2-
| x21²)
2Tp
2
1
xx-1,141
12-1
21T
1
T(T 1)G2m m
5
(|
2112-
| =113)
277
28

---

Published as a conference paper at ICLR 2025
Theorem 4. Under Assumptions I and 2, the output œx of Alg. 2 satisfies
f(xx) f(x+) 2T 1100 I.
G
Dk=1 Ejzt
1000- such that [(xx) - -(x)) Se
Moreover, given 0, there exists a constant step size r
GTVK
after 0
---ll individual proximal oracle queries.
2
Proof. Plugging -k-1 defined in Eq. (4) into Eq. (21) and multiplying 7/-0k-1 on both sides, we obtain
Tna ux (f(#x) f(2
Wk 2 - #k- zk-2l1 wk-1 2 zk-1l13) + T(T 1)G 1)
2
Summing over k E [K] and using the second part of Lemma 2, we have
Trk (ux=1(f(xx)) - f((x))
Σ (1(1- -)) f
k=
T(T I)G?
K
Σ k=
2 Th wk +
w-1
2 - x=1²
2
where we also recall that _-1 = I. Unrolling the terms on the left-hand side as Eq. (13) and choosing do = 1, we obtain
Wnkwk- 1 (f(xx) - f(xx))
K
T
M= - - Ax)
Σ
?i
(f(#x) - f(x.))
(24)
k=1
Ø=
T(T - l)
K
+ W
100 - xc 1|
2
2
To obtain the last iterate guarantee, we choose d and wp such that
AR S wh-1, 0 K 1,
K
JRAWk- Wp(1 (1-
AR)
Σ j=k+1
11 2,
15ksk-1.
For simplicity and without loss generality, we make both inequalities tight and choose WR Σ ΣK Ej=e+1 ni Wk-1- In particular, we choose w/k =
for S k K such that wx = 1,
Σズ Σイ=.+1 n
then we divide Tyk on both sides of Eq. (24) and obtain
GT K
f(zx)- - f(x,) S
w-1
-000-
xx
112
Mi
Wk-1
2Tnk
2n
km
G2T
1100 x.
2T E
K
2
K
k= 7k
j== T
Finally, choosing 77 = | -to-w.1 w-1l
we get
GTVK
f(xx)- - f(x)) < Gl|z00 - x.I|
K
Gl Øo
x (1 + log K/2)
(1+ Σ
I
2
K -
VK
k=1
Hence, given > 0. to guarantee f(ØK) f(x.) S the total number of individual gradient
evaluations will be
G2T [8n x=
TK = 5
é²
completing the proof.
29

---

Published as a conference paper at ICLR 2025
C.3 INEXACT PROXIMAL POINT EVALUATIONS
We first prove the convergence results for convex smooth settings. The following techical lemma bounds (xxx) [(z within each epoch with inexact proximal point evaluations.
Lemma 6. Under Assumptions I and 3, for any IR that is fixed in the k-th cycle of Alg. 2 and for a > 0, > such that 1 +
if the step sizes satisfy Th JOTE then we have for
kE [K]
+ a -((())- +
T Σ
T(((ax) - [(=)) S 2
1
T/p tm1
1
1 (1
Et= 1 )|10 =112 1
Σt= t= ER-1,
+ 21/l:
x1|²
21/Kc
T
2 2//T
Proof. Since each f, is convex and L-smooth, have for t E [T]
1
f((œx) f((0x-1.441) & (Vf((z)), zy - xk-1,0+) [f(x
Vf((
2L
1
(1(0)-1,411- f1() & (V (+1111 11-1 2)
V ( -//=)))
21
Following the proof of Lemma 1, we add and subtract of the second inequality and notice that (gk-1,0, 2)
xk - =112 on the right-hand side
2T
1
- =112 2 1 +
2nz
Zype | 2h 1.+1111 + 2ne | =1 then we combine the above inequalities to obtain
f((x)) f((z) (xxs), Itk xx-1)1+) (((
- 2k-1,
[V - Vs + - {=(()))?
2L
1
|k-1,e+1
2z 12-1.112 2T
|| -1
2 =11²).
217
We decompose fa( fa(xa) V (f + V (f
-k-1. 1. + Ik-1, in the
first inner product term on the right-hand side, and sum the incqualities over E [2'] with noticing fk-1 1x1 and 2g 2+7+1 and obtain
T(((xx) [(=)) <
g 10-,,, a2 08 18-1,111
2 P
11-1
2M t=1
V(((a)) (/(((11 16-1,141)
1
[e(( 1.21 2k 2) + (1 - =112-11 - =1(²)
21
Ta
T
2L
For the term Tı, we follow the argument from the proof of Theorem to obtain
Ti =
|| I
23 2 11250 0.
21T/
For the term T2, noticing that ø6 Db 1,411 -1j6 D' 9k-1, for < 1 T and
- 9k-1,s 1,411) (1 ( Vf((..) + Vfs(..),
30

---

Published as a conference paper at ICLR 2025
use Young's 's inequality with parameters >> 0 and B > 0 to obtain
T-1
T2
V.f((a)))
Vf(( - 7
Σ
9k-1,8
==++1
T
1
1
1
1
$
+
[f(=))) - 1.+1
2L
2
3
1=1
on
T.
T-1
Σ
T
(V)((2) v(((==)) 1| + +2
Σ
2
s=++1
s=t+1
Bm
L
T
T
-
-
2
2
T.
Σ
*=++1
For the term Tz. we use
inequality and Young's inequality to get
T
(f((E-11441) - 2k - z)
VTk T
S [i 11-1,ell| =112 +
(i(((a- 11
2//RK 1=1
2
Further using the fact that || E
11
S n
Di=1 ||> and combining the above bounds on Ti,
T2 and Ta with 11gh-1,t Vf
<
for t [27. we obtain
1
T(((#)) - f()) S
[[(())) V
2T 1
3
2
B L
-
2
2L
am L
L
T
[z)(
vf((,))) + 277
T
V f (a.))
2
1=1
s=1+1
T
T
T
1
+ 2T L
Ek-1,el|=33 20 - 2|12 +
Ek-1,t
2
3/2
2
Th
1=1
1=1
t=1
1
[|
=2122 2||2-||220 ||>
z ==1²).
2TT
remains to follow the proof of Lemma 1 and use m S राा. S ZTI for 3 2 4 to obtain
T-1
T
Vis(wz)) )|² + a r((()) - -s(x.)) + T T
T([(#)) - [(x)) < 2m
L
Σ
3
1.1
1/1 1=1
s=++1
+
1
|
-
=x1/2=
_(11-111111111 21=1 - || - =2112 + Lt=1 Ek-1,
1
(1
211k
211k
Wike
2 Th
thus finishing the proof.
Corollary 3 (Convex Smooth). Under Assumptions and 3, 4 and for parameters 3 such that
1 1 S 1. if the step size fixed and satisfies m7k 17 S VBTL. the output 3K of Alg. 2 with
inexact proximal point evaluations as in Eq. (8) with Σ
St Ek-11 S
k+Ij satisfies
I=(1+a/B]
f(œx) f(x.) <
01 +
+ B/a) 116
2/2
24 E
ΣT (K (K)
2T
2rTKI4af
31

---

Published as a conference paper at ICLR 2025
Given e 0, if Ei= Ek-1, S Vnmiffe, 3(K-k+1) ). there exists 7 such that f S
- f(xx)
after ( Th Till=a-a.11" + TIM Il -mm-=))l))) individual inexact proximal point evaluations.
6/2
Proof. Using Lemma 6 and following the proof of Theorem 1 with multiplying m- on both sides, we have
Tnkwk-(f(ar.) - [(2x-1))
< 2T 1k- 10 (Ppew)-(((EE-1)) f(xx)) Twn--
Wk 1
k.t 2
6k-1,
2 Wk-1
2| wk-1(1 Ei=1 6k- 6k-1,t/ /11e)
+
2xx zk-1 111..
2
Then we sum the above inequality over k E [K] and follow the proof of Theorem 1. To telescope
the terms a 2k-1 112., need Et= 1 ITk S Ax for S k K such that
T ck- VTx)
Xbwr S ALUFE (1- Σ Ek-- VTk) S wk-1 (1 (
t=1
In this case, we maintain the same requirements { and {wx) to obtain the guarantee the last iterate as in Theorem 1. In particular, we take the same choices with constant step sizes
such that A
1
(KK-) for S < K - 1, so it suffices to Σ Ek-1, S
(1+ ()KK)(K)))
1+ () ++I for 11sk S K. Following the proof of Theorem 1, we obtain
K
f(Øx) f(xx) -
W-1
xD 12
+
22
0.
Wk-1
27
k=
K
1
Wk 1-
Wk 1k-1Ek-1,t-
2/1
k=1
Plugging in the choice that wk-1 <
for < k < K
and wk-1 1, we then
(K (K-
have
c1 x.
K-1 T
2T (K k) 1-078
f(zk) f(xx)) <
KT + 2m 202TTo, 3/a)
+
Σ R 1=1
2nTK* K 1-078
2n
Hence, given E > 0, to maintain the convergence rate with exact proximal point evaluations, suffices to take Σ 1= 1 S mini K). I+ (((+))KK44)) for x k < K. Indeed, we have
K
e||20 - 1.112
2
f(øK) - f(x.)
+ 2n 2T + B/o)
Tr 1+0/9
(K - k)) 144/0
k=0
ell0co
12 TTTK 14077
a/3
w/8
+
205 + -3/aa) Ila75
remains follow the proof of Theorem and we choose Σ Ek- min 3( 3K- assuming without loss of generality that e < Ko]
We then come to prove the convergence with inexact proximal point evaluations for convex Lipschitz settings.
32

---

Published as a conference paper at ICLR 2025
Lemma 7. Under Assumptions 1 and 2, for any IR that is fixed in the k-th cycle of Alg. have for l E [K]
T(f(=)) f(z)) -
1 (1+
Ek-
1
-211?
=/12
-11--
|
z11
277
2mp.1
27T
(25)
T(T GP
T
r
+
1 + 3GT
Ek-
Ek
1=1
Proof. By Lipschitzness of each component function, have for t [T -1
f((*x) - f((2x-11441) S G|| - 22-1,0+11 GTlle
Σ
gh 0k-1.a
==++1
Decomposing 9k-1, = 1k- (3)-1,)) + V. ities, have
(Ia) and using triangle inequal-
f((xx) - fe(30x-1.041)
T
$ M&
Σ
(199-110
V ( 1 (I (3
s=t+1
G
Ek-1.e +0) (T ST- +G
Σ s=t+1
Ek-1,81
(26)
Tlk
where we use Eq. (8) and the fact that A. (xR-1,s) E 0f (prox fo (xx-1,1)) for (i). On the other hand, using convexity of fe, we have for & [T] that
f((z) 2 (( (
xk-1,1+1
= = + (gk-1,1, 2 1 + (V (VM (0x) 9k-1,t, xx-1.0+))
Expanding the inner product in the above quantity and using Soucch-Schwaazzinn inequality with Eq. (8) leads to
fel fe( f((2)
s (0k- - 1k-1,1+1) +
V Manth (x0x-1.e) + gh 1 |||= -1-1-
1/k
- (112X-1,1 2112 1|2=110x-1.441 - 211?) 1 ||xx-1,0+1 - 2|1.
1
(27)
2mj
Using triangle inequalities and decomposing 1k-1,t+1 0k-1 = Mi Σ.= 9N 1,-
V M f. (x*= + ((x-I. we bound the term T = Σt Ek-1,1 | 2 z|| in
Eq. (27) as follows
T
Ek-1. ( (1 - || - =11)
T
17 Σ
(11g5-1.0 - VMnas (2x-1,0)) + VM (2x- + || =11)
<
Ek-1,1
1=1
5=1
T
Ek-1,
Σ
Ek 1ks + (M& + +AGGT++|=--1- -=]] xll)
Σ
Ek-1,t
1=1
#=1
t=1
2 + GT E
Σ
1
Ek-1,
Ek 1 - 2|1
GT&
1=
1=1
1=1
33

---

Published as a conference paper at ICLR 2025
where use Young's inequality for (t). Combining Eq. (26) and (27) with the above bound on T and noticing that 2k-1,T+1 = Ty and 2;-1,1 = 2k-1, we sum the inequalities over [T] and obtain
T
277 (1
T(((x)) - [(z)) -
1
1
|a
- -212-
=11
2m GT
277
1=1
+ T(T G)G²M
T
T
Σ
Ek
+ 3GT
Σ
Ek-1,
2
77
tm1
thus finishing the proof.
Corollary (Convex Lipschitz). Under Assumptions 1 and 2, the output Øk of Alg. 2 with inexact proximal point evaluations as in Eq. (8) with Et= 1k- I 1- satisfies
2 76
f(zx) - f(xx)) S
1000 100-0.11 2i-1 n
+ GT EK Σ
+ + Et
3GEk-1,1 %o
2T ES
Σ5 11
Given e > 0, if Et= Ek- S
2nGT K-k+1 there exists constant step size such that f(xk)
f(x.) c after Ō GT
individual inexact proximal point evaluations.
Proof. Using Lemma 7 with = zk-1 defined by Eq. (4) and multiplying m on both sides,
we have
Tyy WT (J((x)) ((=k-1))
w/h 12 + Gg Et=1 Ex-1,1)
2x-2
Wk-1
Bx Zk- 112
2
T(T - 11)G2npuk- + 2
T
Wk-1
+ +3GTmmue ma
Σ
Ck 1k-1,
2
Then we sum the inequalities over h: E [K] and follow the proof of Theorem 4. To telescope the
terms ||0x -4-1 112, we need Ak-1 S
It 2n El 56-1. k K- such that
T
Wkk 1
1
ck-1,) Σ
S Wk Wk-1At-1- S Wk-2;
GT
t=1
while we maintain other requirements on {Ae} and {wx} to obtain the last iterate convergence as in Theorem 4. In particular, we take the same choice that wk
Σ EE Y
5 Σx 19 and A
for
Σ
0 < k K 1, so it suffices to let Σ Ek-1,1 S
2 Exm
So we arrive at
GTT
K
f(œk) - f(xx)( 5
W
200
12112
m
Wk
2T'T
21
3G K
+
Wk-1 176
Ek-1,
Ek-1,
Wk-1
2TT
k=1
t=1
1
|1000
12.12
G2T
Tlk
2T >
K
T7k
jj=k MJ
K
T
1
K
1= 1
+ 3G
2T
2jzk
k=
ビj=k" D
Hence, given E > 0 and taking the constant step size m
Ig -. for simplicity, to maintain
GT
the convergence rate in Theorem 4 with inexact proximal point evaluations, suffices let
34

---

Published as a conference paper at ICLR 2025
E Ek-1,1 S
2nG k+1
Indeed, we have
K
T
Lk
E 1-
5G Fo x.1
3G
3G
K
k +1
VK
j
k=
and
1=
Ek-1,1)
20
x.1l
Σ
K
2.5G 200
V.
27
VK
(K +
vK
f2j
remains follow the proof of Theorem 4, thus finishing the proof.
D CONCLUSION
This work provides the first oracle complexity guarantees for the last iterate standard incremental (gradient and proximal) methods, motivated by catastrophic forgetting considerations in continual learning. The obtained complexity bounds nearly match the best known oracle complexity bounds that in the same settings were previously known only for the (uniformly) average iterate. Our re- sults for the incremental proximal method further characterize the effect of regularization and its limitations in controlling catastrophic forgetting in continual learning applications. Our results com- plement prior thcoretical findings in continual learning (CL) on linear models (Evron et al., 2022), where the authors enforce high task similarity in their setup and assume all tasks share common set of loss minima. They further rely on implicit regularization to enforce closeness of models cor- responding subsequent tasks, arguing that this is sufficient for ensuring that forgetting will not be catastrophic. Our work explores the other side of the spectrum: if one does not assume tasks are "similar" (i.e., they do not necessarily have shared loss minima) but still enforces closeness of mod- els using explicit regularization, it is impossible to prevent catastrophic forgetting entirely; however, one can ensure that forgetting is controlled using sufficient regularization. For future directions, would be interesting to study what lies between the setups of prior work (Evron et al., 2022) and this work; particular, to formally and quantitatively characterize the impact of (appropriately de- fined) task similarity on forgetting. Other possible future directions include 1) deriving last-iterate guarantees of incremental methods for nonconvex tasks; 2) obtaining convergence results match- ing in smooth convex settings while employing diminishing step sizes; and 3) deriving more fine-grained oracle complexity bounds by considering low-level stochastic oracles for each task and possible similarity between consecutive tasks.
35


Reviews:
[{"review_id": "JxkeCrMMzs", "reviewer": "Reviewer_WMon", "summary": "This paper studies the convergence of the last-iterate of incremental optimization methods (more specifically, incremental gradient descent and incremental proximal point methods) over convex functions, either Lipschitz smooth or Lipschitz continuous. Moreover, the paper proposes the setting of cyclic optimization of a finite-sum convex function with regularization as a theoretically-tractable model of Continual Learning with cyclic task replay to theoretically study the phenomenon of *forgetting* in CL. \n\nOn the optimization front, the authors show last-iterate convergence rates for both incremental methods they consider (only for smooth functions in the case of gradient descent, and for both non-smooth and smooth functions for the proximal method). The convergence rates they show nearly match the best-known rates for the convergence of the *average* iterate of these methods. When interpreting the proximal-point results as a model of CL, the authors", "questions": "- I am not sure if I got all the conclusions that the authors wanted to convey (or could convey) about the meaning of these results for CL. Are the main conclusions that catastrophic forgetting is inevitable in this setting (fixed step-size on cyclic IPM) and that there is a critical step-size to control forgetting, and anything smaller/bigger is worse? Does the work of Evron et al. (2022) reach different conclusions? (If I understood correctly, it likely does and it may have to do with similarity of the functions and shared minima).\n\n- This might be way off since I only skimmed Evron et al. (2022), but they make a point of there being a distinction between the convergence to the offline optimum and forgetting, and I think I could not identify this distinction in this model. If I had more time I certainly could try to understand this by myself, but is there such a distinction on the model your paper studies? \n\n- A small technical question, but I was curious whether the results of IPM on Lipschitz continuous functions could also be true for Incremental (sub)Gradient Descent. Is the main roadblock that the analysis for IPM follows from the connection to the gradient of the Moreau envelope?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Convergence rate of incremental/shuffled methods has been an active area of interest in the optimization for ML community, and last-iterate convergence is usually harder to pin-down if compared to the average iterate. Thus, the convergence results are certainly of interest to this community, and the proof techniques seem to involve some interesting techniques to get these rates;\n- I am quite far from the Continual Learning community, but from my point-of-view it seems like an interesting theoretical proxy to study when and how catastrophic forgetting can happen, and the last-iterate convergence does yield some interesting insights;\n- The presentation of this paper is very good. This is not a comment simply made to pad the \"strengths\" section: the authors do an amazing job in thoroughly discussing related work in a very instructive manner, bringing the reader up-to-speed on some of the most relevant results and settings quite fast, and most of the paper is quite well-organized and written.", "weaknesses": "I believe the weaknesses I found are somewhat minor, and some of them might be due simply to misunderstanding from my parts due to the fact that I did not have the time to really the paper very deeply (partially this is my own fault, since ICLR's reviewers this year had a light load). \n\n- I think the main conclusion from the on the context of CL were too \"isolated\" from the rest of the literature. For example, it would have been interesting if the authors knew whether the behaviour of forgetting described in Theorem 2 (and by the discussion on regularization) was seen in empirical studies, or if there seems to be a disconnect (maybe due to the issue of task similarity that the authors mentioned). On a similar line, even though I haven't read the work of Evron et al. (2022), it seems like a discussion of the message in terms of CL should have been discussed and compared to the message from this paper. I understand that right before Sec 3.1 the authors do say that the work of Evron et al. is in a more restricted setting, while their results are more general but rely on regularization. Yet, I believe both try to study the same phenomenon (catastrophic forgetting in cyclic CL), and thus it seems that there could have been a discussion comparing these high-level conclusions between those two papers. This would be a necessarily speculative discussion, but it seems that there are more conclusions to be drawn from these results beyond the fact that the step-size cannot be too big nor too small to better control forgetting. If the authors believe I missed the main conclusion you wanted to draw from the CL connection, feel free to let me know; \n\n- This is a minor point on presentation, but the proof sketch of Theorem 3 is quite crammed (most lines are stretched out because of the fraction being drawn inline) and it didn't seem to yield interesting insights about the proof strategy of Theorem 3. In fact, even though I didn't read in details, I decided to go to the appendix and skim the full proof of Theorem 3 instead of looking at the proof sketch in the main body, and I found it to be easier to read than the sketch, which is counter-intuitive. I am not sure what would be the ideal change in this case, and the authors should take the opinions of a time-constrained reviewer with a huge grain of salt. \n\n---\n\n**Summary of review**: I believe this paper is a solid contribution to the optimization literature in ML. Last-iterate convergence are at times technically challenging, and this paper presents interesting results on last-iterate convergence of incremental GD and proximal methods. Even though I don't feel confident to judge the relevance of the contributions on the CL part, the authors do a great job of describing the relevance of the model to CL and some of the conclusions we can draw from the theoretical results. Even though I felt the conclusions to CL could have been better developed, this is still a solid contribution and an easy accept on my opinion.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pQHIsFYwcl", "reviewer": "Reviewer_jyZz", "summary": "This paper investigates the convergence properties of the last iterate in incremental methods. Specifically, it provides non-asymptotic convergence rates for the last iterate of incremental gradient descent and incremental proximal methods, with bounds that closely match those established for the average iterate. Additionally, the work characterizes the influence of regularization on the rate of forgetting within the convergence analysis of the incremental proximal method.", "questions": "1. **Lemma 1**: What is the role of $\\alpha$? Given that the choice of step size does not depend on $\\alpha$, it seems feasible to set $\\alpha$ as a constant throughout the paper.\n\n2. **Lemma 2**: Is there a restriction on $\\lambda_k$, similar to the restriction mentioned in line 238? After Lemma 2, it is stated that \"the convergence rate for the last iterate is characterized by the growth rate of $\\{w_k\\}$”; however, this connection does not appear to be clearly reflected in the main results, such as Theorem 1. Moreover, lines 252-255 are hard to understand for me.\n\n3. **Shuffled SGD**: Intuitively, random reshuffling and shuffling once generally do not yield similar convergence rates—random reshuffling reduces variance in gradient estimates each epoch, leading to faster and more stable convergence. In contrast, shuffling once fixes the sample order, lacking this ongoing variance reduction and potentially slowing convergence. Could the authors clarify why both random reshuffling and shuffling once are expected to yield similar rates?\n\n4. **Theorems 2 & 3**: The proof for Theorem 2 is missing. Additionally, the current presentation of Theorems 2 and 3 suggests that a constant step size may not achieve the desired trade-off, implying a preference for a varying step size. Could similar results to those in Corollary 1 be established with a varying step size?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper presents novel results on the last-iterate convergence rates of incremental methods, which closely match the rates for average iterates. Additionally, it characterizes the effect of regularization on forgetting within the incremental proximal method.", "weaknesses": "The presentation of the paper requires improvement. Specifically, the explanation of the main proof techniques (Lemmas 1 and 2) is difficult to follow. Additionally, some of the parameter choices in the theorem statements are incomplete. Further details can be found in the Questions section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "VHqA7ThlsX", "reviewer": "Reviewer_4LtA", "summary": "The authors provide non-asymptotic finite-time optimality gap bounds for the final iterate of incremental gradient descent and incremental proximal method. These bounds match or improve on the sample complexity of the previous results obtained via a Polyak-Ruppert type iterate averaging.", "questions": "- There is a very minor notation inconsistency between Eq. (2) and Alg. 1 -- I think all the \"k-1\" subscripts in Alg. 1 can be \"k\" instead?\n\n- In the two main theorems, I'd suggest stating the tuned gap bounds $ f(x_K) - f(x^*) \\le $ [a decreasing function of $K$] as well.\n\n- A clear comparison of results in a tabular form would contextualize the paper better.\n\n- ''There were no guarantees for either the last iterate or even a weighted average of the iterates\". Mishchenko et al.'s Section 3.1 provides a few bounds for the last iterate but these are in terms of the iterate error bounds instead of the optimality gap, right?\n\n- The authors might want to comment after Cor. 2 on why the randomized version has a seemingly faster rate of convergence compared to its deterministic counterpart.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "- The authors address a fairly important setting in optimization and the last iterate optimality gap bounds are indeed new. In particular, the $\\sqrt T$-improvement in sample complexity for IGD is a very nice result.", "weaknesses": "- I'm fairly sure this is standard and non-technical, but it would be great if bounds for decreasing step size without knowing the total number of rounds $K$ in advance were provided (at least in the appendix)\n\n- The simulations are not entirely informative. Would it be possible to highlight the $\\sqrt T$ improvement for IGD (I assume it might be possible since the authors' analysis indicates a different step size scheme compared to Mishchenko et al.)? Either way, I feel that removing the simulations and adding more summary/comparison/discussion for the theoretical results will strengthen the presentation of the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lwuIjMMX6G", "reviewer": "Reviewer_kK5z", "summary": "This paper addresses incremental gradient and proximal methods for optimization in convex settings, particularly focusing on the last-iterate convergence guarantees. Traditionally, convergence results for these methods have primarily focused on the average iterate. The authors present novel complexity bounds for the last iterate, which closely match those for the average iterate, extending these bounds to both incremental gradient descent (IGD) and incremental proximal methods (IPM) across various setups, including randomly permuted updates and weighted averaging schemes.", "questions": "- Why the last iterate convergence of the incremental proximal method is a good mathematical abstraction of forgetting in continual learning?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- The paper is clearly structured, with each theorem building on the previous results to form a coherent narrative.\n\n- The paper provides novel non-asymptotic last-iterate convergence guarantees for incremental gradient and proximal methods without requiring strong convexity.", "weaknesses": "- While the paper discusses forgetting in the context of continual learning, the model of catastrophic forgetting is somewhat simplified (see questions).\n\n- The paper presents theoretical contributions with lack of accompanying numerical experiments (only one with least square functions).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)