Efficient Continual Finite-Sum Minimization
Authors: Ioannis Mavrothalassitis
Stratis Skoulakis
Leello Tadesse Dadi
Volkan Cevher
Venue: ICLR 2024 poster (2024)
Keywords: Finite Sum Minimization
Variance Reduction
Optimization
Primary area: optimization

Abstract: Given a sequence of functions $f_1,\ldots,f_n$ with $f_i:\mathcal{D}\mapsto \mathbb{R}$, finite-sum minimization seeks a point ${x}^\star \in \mathcal{D}$ minimizing $\sum_{j=1}^nf_j(x)/n$. In this work, we propose a key twist into the finite-sum minimization, dubbed as *continual finite-sum minimization*, that asks for a sequence of points $x_1^\star, \ldots, x_n^\star \in D$ such that each ${x}^\star_i \in D$ minimizes the prefix-sum $\sum_{j=1}^if_j(x)/i$. Assuming that each prefix-sum is strongly convex, we develop a first-order continual stochastic variance reduction gradient method ($\mathrm{CSVRG}$) producing an $\epsilon$-optimal sequence with $\tilde{\mathcal{O}}(n/\epsilon^{1/3} + 1/\sqrt{\epsilon})$ overall *first-order oracles* (FO). An FO corresponds to the computation of a single gradient $\nabla f_j(x)$ at a given $x \in \mathcal{D}$ for some $j \in [n]$. Our approach significantly improves upon the $\mathcal{O}(n/\epsilon)$ FOs that $\mathrm{StochasticGradientDescent}$ requires and the $\mathcal{O}(n^2 \log (1/\epsilon))$ FOs that state-of-the-art variance reduction methods such as $\mathrm{Katyusha}$ require. We also prove that there is no natural first-order method with $\mathcal{O}\left(n/\epsilon^\alpha\right)$ gradient complexity for $\alpha < 1/4$, establishing that the first-order complexity of our method is nearly tight.

Published as a conference paper at ICLR 2024
EFFICIENT CONTINUAL FINITE-SUM MINIMIZATION
Ioannis Mavrothalassitis; Stratis Skoulakis; Leello Tadesse Dadi, Volkan Cevher
LIONS, École Polytechnique Fédérale de Lausanne
distratios.skoulake leello.dadi, volkan.cevher) @epfl.ch
ABSTRACT
Given sequence of functions fi..... fn with f:: E. finite-sum minimiza- tion seeks point x² E DD minimizing Σj=1 fr)/nn. In this work, we propose a key twist into the finite-sum minimization, dubbed as continual fimite-sum minimiza- tion, that asks for sequence of points ii,,......... ......... 2 E DD such that each x E D min- imizes the prefix-sum Ej= (x)/i, Assuming that each prefix sum is strongly convex, we develop a first-order continual stochastic variance reduction gradient method (CSVRG) producing an e-optimal sequence with ((n/ + +1/11 over- all first-order oracles (FO). An FO corresponds to the computation of single gradient (z) at given x E D for some j E [n)]. Our approach significantly improves upon the (nn/e) FOs that MtochasteGraddeenteeeeer the On log(1/c)) FOs that state-of-the -aee----thhhtttt art variance reduction methods such as Katyusha require. We also prove that there is no natural first-order method with O (n/e") gradient complexity for a < 1/4, establishing that the first-order com- plexity of method is nearly tight.
requires and
INTRODUCTION
Given data points describing desired input and output relationship of model, cornerstone task in supervised machine learning (ML) is selecting the model's 's parameters enforcing data fidelity. In optimization terms, this task corresponds minimizing objective with the finite-sum structure.
Finite-sum minimization: Given a sequence of functions fi,..., fn with fr : D + R, let x" e arg min, (x) : Σ fz(z//n /n. Given an accuracy target > fintte sum mininization seeks an approximate solution T. such that:
g ( g(x*) Se
we call such an f an e-acourate solution. If ē is random then [I takes the form E [g({)] g(x*) S e.
In contemporary machine learning applications, n can be in the order of billions, which makes it clear that methods tackling finite-sum minimization must efficiently scale with and the accuracy >> 0.
First-order methods have been the standard choice for tackling (T) due to their efficiency and practical behavior. The complexity of a first-order method captured through the notion of overall first-order oracles (FOs) where first-order oracle corresponds to the computation of a single gradient V (z) for some E [n] and a point x E
case each function fa is strongly convex, Stochastic Gradient Descent requires ((1 /c) FOs Robbins and Monro (1951): Kiefer and Wolfowitz/ (1952) so to solve I Over the last years, the so-called variance reduction methods are able to solve strongly convex finite-sum problems with On (1/e) FOs Nguyen et al. (2017b); Johnson and Zhang (2013) Xiao and Zhang 2014); Defazio et al. (2014) Roux et al. (201 Allenn (2017).
Continual Finite-Sum Minimization: In many modern applications new data constantly arrives over time. Hence it is important that a model is constantly updated so as to perform equally well both on the past and the new data Castro et al. (2018); Rosenneld and Tsotsos (2018) Hersche al. (2022). Unfortunately updating the model only with respect to the new data can lead to a vast deterioration of its performance over the past data. The latter phenomenon is known in the context of continual learning as catastrophic forgetting Castro et al. (2018); Goodfellow et al. (0014); Kirkpatrick et al. (2017): McCloskey and Cohen 1989). At the same time, retraining the model from scratch using
"Equal contribution

---

Published as a conference paper at ICLR 2024
both past and new data comes with a huge computational burden. Motivated by the above, we study twist of ( called continual finite-sum sum minimization.
Continual Finite-Sum Minimization: Given sequence of functions fi...., for with fi : D + R. /á for all E [n]. Given an accuracy target e
let ot E arg minzeD gı(x) == -
continual sinite-sum minimization seeks sequence of approximate solutions 21, .1,-... Sn D, such that:
9: (2,) S (x(z)) We call such a sequence an e-optimal sequence. If x is random then takes the form Blg. (((x)) S
+ for each E [nx]
(2)
Remark 1. Throughout the paper assume that each function fi(.) is strongly corvex, smooth and that DD is convex and bounded. See Section for the exact definitions.
Notice that ft(-) can capture a new data point meaning that 2 guarantees that, the model (parameter- ized by .:.) is well-fitted in all of the data seen so far for each stage i E [n]]. As already discussed, since n can be in the order of millions, it is important to design first-order methods for continual finite-sum minimization that efficiently scale with and > 0 with respect to overall FOs.
(2) is via existing first-order methods for finite-sum minimization. As discussed above StochasticGradieess GerraddentDDeeeenn can guarantee accuracy >> 0 for ( using (1)e). As a result, at each stage i E [ra] one could perform (1/ee) stochastic gradient decent steps to guarantee accuracy > 0. However the latter approach would require overall (n//e) FOs. On the other hand one could use a VR methods to select Ω; E DD at each stage i E [n]. As already mentioned such methods require log (1/c)) FOs to guarantee accuracy c > 0 at stage E [n]. Thus the naive use of a VR method such as SVRG JJohnson and Zhang (2013); ; Xiao and Zhang
A first attempt for tackling
(2014) SAGA Defazio et al. 20144), SARAH Nguyen et al. (2017b) and Katyusha Allen-Zhu (0177) would require overall On log((/e)) FOs.
We remark that for large values of n and even mediocre accuracy > 0 both ((n/c) and especially On? log(1/e)) are prohibitely large. As result, the following question arises:
Question 1. Are there first-order methods for continual finite-sum minimization whose required number of FOs scales more efficiently with respect to n and e >> 0?
Our Contribution The main contribution of this work is the design of first-order method for Con- tinual finite-sum minimization, called CSVRG, with overall Ô (n/e") 13 + logn/ /C) FO complexity. The latter significantly improves upon the (n//c) FO complexity of SGD and the (n log(1 (c)
complexity of variance reduction methods. As naive baseline, also present sparse version of SGD tailored (2) with Olog e/22) ) FO complexity. The latter improves on the n dependence of SGD with the cost of worse dependence on 1/e.
Since variance-reduction methods such as Katyusha are able to achieve On log(1/e)) FO com- plexity. A natural question is whether there exists first-order method maintaining the log(1/e) dependence with subquadratic dependence on n, O (1-2- log(1/c)) We prove that the latter goal cannot be achieved for a wide class of first-order methods that we call natural first-order methods. More precisely, we establish that there is no natural first-order method for 2 requiring O(n2~a log(1/e)) FOs for any a > O. We also establish that there is no natural first-order method for 2 requiring O (n/E²) FOs for any a < 1/4. The latter lower bound implies that the Ô (n/) FO complexity of CSVRG is close to being tight. T summarizes our results.
Comparing the methods for (1//n) accuracy According to the level of accuracy c > O that requires, different methods might be more efficient than others. We remark that for the accuracy regime of c (1/nn) all previous first-order methods require O(n)) FOs while CSVRG requires only (334 FOs!
We remark that the accuracy regime c = ((1nn) for 2 is of particular interest and has been the initial motivation of this work. The reason for the latter lies on the generalization bounds in the strongly convex case. More precisely, the statistical error of empirical risk minimization in the strongly convex case is (1/nn) Shaley-Shwartee et al. (2010). Thus the accuracy of the respective finite-sum problem should be selected as e = O(I/n) so as to match the unavoidable statistical error (see Bottou and Bousquet (2077) for the respective discussion). For accuracy 0(1/n) very
2

---

Published as a conference paper at ICLR 2024
c-aceuracy at each stage E
Method StochasticCraddeenDeeenee
Number of FOs
O n/en/) o n² log
SVRG/SAGA/SARAH
e log(L/e))
Katyusha
o n² log(1/c)
V
n 3/2 log(1/c))
| 1/e²
SGD-sparse (naive baseline)
CSVRG (this work)
O
G//3
(n log n)) 1/3 /c23//////////////
L. n3/2
log n/ Vo)
Lower Bound (this work)
M (n2 log(1//)) (n/e//)
Lower Bound (this work)
Table Number of FOs for the strongly convex case for an c-accurate solution for each stage i [n]]
interesting open question is bridging the gap between the O(n\/3) FO complexity CSVRG and the 5/4) FO complexity that our lower bound suggests (setting 1/n and a = 1/4).
Our Techniques As already discussed the naive use of VR method at each stage i E [ra] results in overall (n (1)( FOs. A first approach order to alleviate the latter phenomenon is to sparsely use such a method across the stages and in most intermediate stages compute i; E 'D O(1) FOs using stochastic gradient estimator. However both the sparsity level for using VR method as well as the stochastic gradient estimator crucial design choices for establishing accuracy > 0 at each stage E [n]]
Our first-order method (CSVRG) adopts variance-reduction pipeline along the above lines. CSVRG (Algorithm maintains direction V. that stage i [n] tries approximate Σ Vf Since computing the latter direction at each stage E [ni] would lead to M(r²) FOs, CSVRG
Sets V. >1 kmm V ( only in a very sparse sub-sequence stages (i FOs)
Sets V,
7) (4 most stages FO)
In order to output an c-accurate point à, E D at stage E [n], we initialize an internal subroutine (Algorithm{)) to the previous output ž; 1 E D and perform T, stochastic gradient descent steps using the following novel gradient estimator
V -- (1- (V Vin (ppe + V--) + 7 V
where index in is selected uniformly at random in and prev is the latest stage e < - at which V. Σl= fi (&z)/E. Notice that the estimator V requires only 3 FOs. Combining all the latter, we establish that by an appropriate parametrization on the sparsity of the sub-sequence at which V. E'= ( and appropriate selection of iteration T,, first-order method CSVRG requires overall O(n log n/32/3) FOs.
1.1 RELATED WORK
Apart from the close relation of our work with the long line of research variance reduction methods (see also Appendix for a detailed discussion), the motivation of our work also relates with the line of research in incremental learning, the goal of which is adapting model to new information, data or tasks without forgetting the ones that it was trained on earlier. The phenomenon of losing sight of old information is called catastrophic forgetting Castro et al. (2018); Goodfellow et al. (2014); Kirkpatrick et al. (2017) 7): McCloskey and Cohen (1989); Mermillod et al. (2013) and it is one of the main challenges of incremental learning. There have been three main empirical approaches to tackle catastrophic forgetting, regularization based [guyen et al. (2017a). memory based Tulving (1985), architecture based Yoon al. (2017), well combination of the above Sodhani al. (2020)
3

---

Published as a conference paper at ICLR 2024
2 PRELIMINARIES
In this section we introduce some basic definitions and notation. We denote with Unif(1,..... n) the uniform distribution over {l....,m) ,.) and [n] := ,t...
Definition (Strong Convexity). differentiable funtecttt : + R is j-strongly convex in if and only for all x. V E
f(x) 2 f(v) V
P
| yl
In Problem (2) we make the assumption that D convex and compact. We denote with |D] the diameter of D. D maX || y/12- The compactness of DD also provides with the property that each fi D + R is also G-Lipschitz and L-smooth. More precisely,
((x f(y) G. || vll (G-Lipschtiz) V/(()) v - L. ||0 yll (I-smooth)
To simplify notation we denote as where max,eD [>)]l and L m
f2x())) 2
(e(x)) the prefix-function of stage i [n].
g1(x) = Σ fx(//i
We denote with x. E D the minimizer of the function gi (z), x arg min (x).. We denote the projection of x E Rd to the set D as 1I (x) := arg mingep || - =ll2. For a set S C IR, we denote (S) == (Il for all E S}. Throughout the paper we assume that each function fa(-) in continual finite-sum minimization (2) is μ-strongly convex, L-smooth and G-Lipschitz.
3
OUR RESULTS
We first state our main result establishing the existence of a first-order method for continual finite-sum minimization 2 with Ô (n/c1/3 log /() FO complexity.
Theorem 1. There exists first-order method, CSVRG (Algorithm D for continual finite- sum
minimization with O 1,2/3/2/3
plogn 1.G
log
FO complexity.
217
As already mentioned, our method admits Ô (n/cl/3 + 1/VC) first-order complexity, significantly improving upon the (n/ec) of SGD and the O (n² log(1/e)) of VR methods. The description of our method (Algorithm) T as well as the main steps for establishing Theorem Tare presented in Section
In Theorem 2 present the formal guarantees of the naive baseline result that is sparse variant of SGD for continual finite-sum minimization ( with (11c²) FO complexity.
Theorem 2. There exists first-order method, SGD-sparse (Algorithm Fy. for continual finite minimization ( with O
G
FO complexity.
Algorithm as well as the proof of Theorem are presented in Appendix
Lower Bounds for Natural First-Order Methods In view of the above, question that nat- urally arises is whether there exists method for continual finite-sum minimization (2) with log(/e) FO complexity. Unfortunately the latter goal cannot be met for a wide class of first-order methods, that call natural. The formal definition of natural first-order method is presented in Section 3.1 To this end, we remark that methods such that GD, SGD, SVRG, SAGA, SARAH, Katyusha and CSVRG (Algorithm I lie in the above class.
Theorem 3. For any a > O. there is no natural first-order method for Problem (2) with O (n2-olog(1/e) FO complexity. Moreover for any a < 1/4, there natural first-order method for continual finite-sum minimization (2) with O (n/e") FO complexity.
Due to space limitations the proof of Theorem is presented in Appendix H
Remark 2. The (/3/e2/3 + 1/ /C) FO complexity of CSVRG is close the D(n/c2/1) lower bound.

---

Published as a conference paper at ICLR 2024
3.1 NATURAL FIRST- ORDER METHODS
In this section we provide the formal definition of natural first-order method for which our lower bound stated in Theorem 3 applies. Before doing present the some definitions characterizing general first-order methods.
At an intuitive level a first-order method for continual finite-sum minimization 2 determines â; E D by only requiring first-order access to the functions fi...., fi. Specifically at each stage E [r]] first-order method makes queries of the form {V (z) for S i} and uses this information to determine é; E D. The latter intuitive description is formalized in Definition
Definition 2. Let A be a firstorder method for continual finite-sum minimization 2 At each stage i [n].
Zu "D denotes the initial point of A and i; E D denotes the outpur of A at stage i [m]]
x E D denotes the intermediate point of A at round t 2 1 of stage i [n] and T, N the number of iterations during stage E [m].
At each round E [Ti) of stage i E [n]. A performs a set of first-order oracles denotes Q!-
Each first-order oracle E O2 admits the form q (Avatues Tindex) where qualue E 'D denotes the queried point and Index S i denotes the index of the queried function.
A computes the gradients [Viqude (Avalue) for all q E Q.) and uses this information to determine x; E ED.
The FO complexity of A is thus
Eieln Σ 10%1
Example 1. Gradient Descent at stage E [n], sets x² t -;-11 for each round t E [Ti] peforms x 7 Σ - (z 1/2 Fimally it sets 3; + a7-o Thus in terms of Definition the
of +
first-order oracles of GD at round t T; are Q = [1] .......... (x)-).)))))
In Definition 3 we formally define the notion of a natural first-order method. simple terms a first-order method is called natural if during each stage i [n]] it only computes FOs of the form (z)( where x E 'D is previously generated point and j S i.
Definition 3. A first-order method A is called natural iff at each step E [Ti] stage E [n].
For any query E Q Tindex & i and qualue E pp!-1 where PP--1 U (PP!-1 stands for previous points)
(Umsi-1 UTSTm xTh) (U)Se-II)))
x E (IT((S) where S is the linear span of (UgeQ: V Sannee (Avatue) UPP!-
c. E IS) where S is the linear span of PP..:
Remark 3. Definition Q being a random set.
3 Falso captures randomized first-order methods such SGD by considering
Natural first-order methods the straightforward extension of linear-span methods Bubeck 2015 ;
Nesterov (2014) in the context of continual finite-sum minimization (2) Linear-span methods require
that for any first-order oracle V fz(x) computed at iteration t, x (zo, Ti,... .......... -t-1) .f }. Moreover & is required to lie in the linear span of the previous points and the computed gradients. Linear-span methods capture all natural first-order optimization methods and have been used establish the
well-known 2(1 Ve) and ? / LL/ulog(L/e) respectively for the convex and strongly convex (see Section 3.5 in Bubeck (2015)).
4 CSVRG AND CONVERGENCE RESULTS
In this section we present our first-order method CSVRG that is able to achieve the guarantees established in Theorem CSVRG is formally described in Algorithm
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 CSVRG
&0 E D. prev O, update false
2: $1 Dradient Vi (&i
3: for each stage = ,...., n do
4: if i prev 2 a then
5:
V 1- t - Eド= (+,(1
Compute Vgi-1(8;-1) with i FOs
6:
prev -i-1
7:
update true
8:
end if
9:
T; - O
12G p5lsive
1²6²a²
+ 1.2
b Number of iterations of Algorithm at stage E [n]
10:
i; FUM(,r v.-1,T:)
Selection of 2; D by Algorithm 2
11:
if update then
12:
V.+ + V(z(tt
Compute Vg;( with FOs
prev ti
14:
update + false
else
16:
V + (1 v-1 Vi((ppe))
Update V, with 1 FO
end if
18:
end for
Algorithm 2 Frequent Update Method (FUM)
1: 8 - 721.2 p² Z <- 2
- + (Ti + 1) - 1)
2: 2 -1-1
Initialization at d;-1 E D
3: for each round := 1,..., Ti do
4: Select ut i
5: V + (1- 1) (i (x()) - V Su, ( (ppc + V--1) + (VA(2))
> 3 FOs
6:
" - 4/(u(t+ + B))
b> Step-size selection
7:
2tt1 + UIl (17 vi)
Update xf E D
8: end for
9: Output: 2, + 1 ET-O (s + 1)x
> Final output
We first remark that the computation of the output 2 E D for each stage E [n], is performed at Step 10 of Algorithm 1 by calling Algorithm 2 performs T; stochastic gradient steps using the estimator
Then Algorithm initializes x! := L;-1 and
V (1 -
Se (x/)
V Sug (#prev) V v.-1) + V.(((t
To this end remark that in order to compute V Algorithm 2 requires just 3 FOs. Before explaining the specific selection of the above estimator start by explaining the role of V..
The role of v:: In order to keep the variance of the estimator V low, would ideally want V.-1 Vgi-1 (i) The problem is that computing V (ā:z) requires FOs meaning that performing such computation at each stage E [n]. would directly result in 2(n²) FOs. In order overcome the latter challenge, full gradient (z) is computed very sparsely by Algorithm ]
across the n stages. Specifically,
In case prev a then V E, Vis(i
(i FOs)
In case prev then V, = (1 - :) V.n (Q
(1 FO)

---

of Published as a conference paper at ICLR 2024
Thus the parameter 0 controls the number of times Algorithm reaches Steps 5 and 12 that at stage E [n]] require i FOs. The latter is formally stated and established in Lemmal []
Lemma 1. Over a sequence of n stages, Algorithm 7
reaches Step 5 and 12, [log n/a times.
Combining the latter with the fact that Algorithm 2 requires 3T, FOs at each stage i [n] and the fact that Step 5 and 12 require at most n FOs, we get that Corollary 1. Over sequence of n stages, Algorithm requires 3 E T; + 2n flo n/a] FOs.
Up next we present Theorem establishing that for specific selection of parameter > 0, Algorithm D guaranteess that each ã; E 'D is an e-optimal point for the function g((x).
Theorem 4. Let a convex and compact set DD and a sequence u-strongly convex functions f1. fi...., fnx with fo D E. Then Algorithm 1 with T, 720GL (e0GLL/(uP0) ///e////////// 9 p1)
864L² / and pu2133/ [220G2/3 L guarantees
[ggi(E:)] 9: (x²)) S ffor each stage E [n]
where iz E E is the oulput of Algorithm al Step 9 of Algorithm
The proof of Theorem directly follows by Theorem 4 and Corollary I
For completeness the proof
Theorem is presented in Appendix G In the rest of the section we present the key steps for proving
Theorem (see Appendix
F22) for the full proof.
We first explain the role of the gradient estimator V in Step 5 of Algorithm 2
This estimator V of Step in Algorithm may seem unintuitive first sight since it subtracts the term Vi,, (F )- Interestingly enough the latter estimator-selectio permits us to establish the following two key properties for V
Lemma 2 (Unbiased), Let V the gradient estimator used in Step 5 of Algorithm ee [T.]. E [ (g(()))
2 Then all
Lemma 3 (Bounded Variance). Let V the gradient estimator used in Step 5 of Algorithm 2 Then for all t E [T.].
L2G²
E
|
(=(())) s 8L'M ||=;
27 22 + 64
a²
+1662
||a
& &prev 1|2]
where a > is the parameter used Step 4 of Algorithm
The proof of Lemma 2 and Lemma 3 are respectively presented in Appendix Cld Appendix and consist one of the main technical contributions of this work. In Section
5 we explain why the specific
estimator-selectinn V is crucial for establishing both Lemma and 3
In the rest of the section, provide the main steps for establishing Theorem Let first inductively assume that E [g)( O3 (x()) S for all j < We use the latter to establish that [g. - 9: (x S c.
Notice that Step 4 of Algorithm guarantees that prev < i 1 Step 10. Hence the in- duction hypothesis ensures that EE [peev (āprev) - 9pee (srpeev) < and thus by strong convexity
E prov xppov [ < 2c/p. Thus the bound in the variance of Lemma
L²G²
I a +
E
[|V (x.)
[ < o
LEB || ||: - =t|]]]
+
(5)
122
11
Using the fact that E V V (zf) and the bound in the variance E Equation 5 in Lemma g of Appendix we establish that
|IV - (
L
0 x
112
L²G²2 a² 11
Lif
E (G:)) (x()))
ga (1
(x S 505
113
T
T
Notice that at Step 2 of Algorithm 2
xi! : 5;-1 1 E D meaning that
L |
x
12
LdG
a²
L'e
E (2.)) - (x
<
0
43
T?
1 T
nTT,
LAG22
Lt
12
Liee
<
0
+
+
15
T?
uT
3
TTT:
7

---

Published as a conference paper at ICLR 2024
where the last inequality follows by ||::-1 2il22 1 ši 1 x1-111
2 2| x =1112
1 r-- - ((ii) and ||ā;-1 - 2i-1l E e/p. As a result, by taking Ti
1²G L'G"a"
122 /!²
we gel that EE [a((E:)] gi(xt) S.
porzive
ANALYZING THE ESTIMATOR V
In this section we provide the key steps for proving Lemma and Lemma L respectively.
Unbias estimator: The basic step for showing that V of Step Algorithm an unbiased estimator, [V]] = (x)) is establishing the following property for V.-1 defined Algorithm
Lemma 4. At Step of Algorithm / it holds that v-11= Σ V& (i
The proof of Lemma 4 is presented in Appendix C and admits an inductive proof on the steps of
Algorithm 1 Once Lemma 4 is established the fact that E [V:] ff(=]] easily follows by the
selection of the estimator (see Step 5 of Algorithm 2 For the full proof of Lemma 2 we refer the reader Appendix
Bounding the Variance of Vi: The first step towards establishing Lemma is presented Lemma
providing a first bound on the variance E
|| (=)())) The proof of Lemma uses ideas
derived from the analysis of VR methods and is presented in Appendix D
Lemma 5. For all rounds E T3 of stage
[n]]
E - 8 || 2:[1]] + SL |1=; Spre 11
(6)
where prev is defined in Algorithm 7
The next step for establishing Lemma 3 is handling the term E | &prev 1 of Equation 6 In order to do the latter in we exploit the strong convexity assumption so as to establish Lemma the proof of which lies in Appendix B
Lemma 6. Let &J E DD the output of Algorithm 7 for stage E [n]. Then for all (i 1ú+1 I....n..
2 - 212
8 2
G(i ((i-)))
+ +2 - 1/
itÿ
Now by applying Lemma 6 for j = prev we get that
| &peevl
<
8
G(i - prev)
+ +2|l @ - xprev 1
112
2prev + (i - prev)
8
G(i prev) 2
2 2 "pprevl"
n22
Step 4 and 6 of Algorithm i prev S Thus,
ensure that Step 10 of Algorithm
[ (when Algorithm 2 is called),
|| - - 1 s
8 112
G(i - prev)
+ 2 f| xppeel 1|2
32G² a²
+ 2 2 xprev |
and thus E ||:0 @prew
2 <
32G² n²
a 21F
[| xppevv 11]
Combining the latter with Equation
we overall get,
| Vo.(2)))
so <0(1E
||||
x 1:
+
L2G² 42
a² + 12
|| xgrew 1²²)
8

---

Published as a conference paper at ICLR 2024
157
620 Iokyyshe
breaiccacer
China
Table 2: Optimality gap as the stages progress on ridge regression problem (averaged over 10 independent runs). CSVRG performs the exact same number of FOs with SGD and slightly less than SCD-sparse. Katyusha and SVRG perform the exact same number of FOs. CSVRC/SGD/ sparse perform roughly 4% of the FOs of patyusha//vVS
EXPERIMENTS
We experimentally evaluate the methods BSGD,SGD-sparse, Katyusha, SVRG and CSVRG) ridge regression task. Given some dataset (a:, b Rd IR, each stage E [n] we consider the the finite sum objective (z(z) := Σ 2 (a] latter setting so as to be able to compute the exact optimal solution at each stage i E [m)
by) 3 /i + A ||=1 with X = 10 We choose the
For our experiments we use the datasets found the LIBSVM packageChang and Lin 201 for which we report our results. At each stage i E [mx]. we reveal a new data point (a,, b:). In all of our experiments we run CSVRG with a 0.3 and T; 100. The inner iterations of SGD and SGD-sparse are appropriately selected so that their overall FO calls match the FO calls of CSVRG. At each stage E [n|] we run Kat yusha Allen-Zhu (017)) and SVRG Johnson and Zhang 2013 3 on the prefix-sum function (z) with 10 outer iterations and 100 inner iterations.
In Table 2 we present the error achieved by each method at each stage E [n] and the overall number of FOs until the respective stage. As our experimental evaluations reveal, CSVRG nicely interpolates between SGD/SGDDsparse and Katyusha/sVRG. More precisely, CSVRG achieves significantly smaller suboptimality gap than SGD/SGD-sparse with the comparable one with Kat yusha/SVRG with way fewer FOs. In Appendix K.2 we present further experimental evaluations well the exact parameters used for each method.
number of FOs while it achieves
CONCLUSIONS
In this work we introduce continual finite-sun optinization, tweak of standard finite-sum minimiza- tion, that given a sequence functions asks for sequence of e-accurate solutions for the respective prefix-sum function. For the strongly convex case we propose a first-order method with Ó(n/c 1/3) FO complexity. This significantly improves upon the (n/cc FOs that StochasticGradientll requires and upon the O(n² (lg(())) FOs that VR methods require. We additionally prove that no natural method can achieve (n² 2-a log(1/e)) FO complexity for any > and O (n/c²) FO complexity for 1/4.

---

Published as a conference paper at ICLR 2024
8 ACKNOWLEDGEMENTS
Authors acknowledge the constructive feedback of reviewers and the work of (C program and area chairs. This work was supported by Hasler Foundation Program: Hasler Responsible Al (project number 21043), by the Swiss National Science Foundation (SNSF) under grant number 200021 200021_20501, by the Army Research Office (Grant Number W91 INF-24---442 (4-N---4---0048) and by Innosuisse (contract agreement 100.960 IP-ICT).
Limitations: The theoretical guarantees of our proposed method are restricted to the strongly convex case. Extending our results beyond the strong convexity assumptions is very promising research direction.
Reproducibility Statement In the appendix we have included the formal proof' of all the theorems and lemmas provided in the main part the paper. order to facilitate the reproducibility of our theoretical results, for each theorem its proof. Concerning the experimental evaluations of our work, we provide the code used in our experiments well as the selected parameters in each of the presented methods.
have created separate self-contained section presenting
Ethics Statement The authors acknowledge that they have read and adhere to the ICLR Code of Ethics.
REFERENCES
Zeyuan Allen-Zhu. Katyusha: The first direct acceleration of stochastic gradient methods. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 1200- 1205, 2017.
Zeyuan Allen-Zhu. Natasha 2: Faster non-convex optimization than SGD. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 2680- 2691, 2018a.
Zeyuan Allen-Zhu. Katyusha practical momentum method for stochastic sum-ooo-ono-oooooeees opti- mization. CoRR, abs/ (ts//802.03866, 2018b. URL attp://araiv..errabb///
Zeyuan Allen-Zhu and Yang Yuan. Improved svrg for non-strongly-connex or sum-of-non-comee objectives. In International conference on machine learning, pages 1080-1089. PMLR, 2016.
Doron Blatt, Alfred O Hero, and Hillel Gauchman. A convergent incremental gradient method with constant step size. SIAM Journal on Optimization, 18(1):29 512-51, 2007.
Léon Bottou and Olivier Bousquet. The tradeoffs large scale learning. In Advances in Neural Information Processing Systems 20, Proceedings of the Twenty-Firg First Annual Conference on Neural Information Processing Systems, pages 161-168. Curran Associates, Inc., 2007.
Stephen P Boyd and Lieven Vandenberghe. Convex optimization. Cambridge university press, 2004.
Sébastien Bubeck. Convex optimization: Algorithms and complexity, 2015.
Francisco M Castro, Manuel Marín-Jiménez, Nicolás Guil, Cordelia Schmid, and Karteek Alahari. End-to-end incremental learning. In Proceedings of the European conference computer vision (ECCV), pages 233-248, 2018.
Chih- Chang and Chih-Jen Lin. Libsvm: library for support vector machines. ACM transactions on intelligent systems and technology (TIST), 2(3): 2011.
Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien. SAGA: A fast incremental gradient method with support for non-strongly convex composite objectives. In Zoubin Ghahramani, Max Welling, Corinna Cortes, Neil D. Lawrence, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 27: Annual Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec, Canada, pages 1646-1654, 2014.
10

---

Published as a conference paper at ICLR 2024
Bernard Delyon and Anatoli Juditsky. Accelerated stochastic approximation. SIAM Journal Optimization, ((4):868-888) 1993.
Benjamin Dubois-Taing Sharan Vaswani, Reza Babanezhad, Mark Schmidt, and Simon Lacoste- Julien. SVRG meets adagrad: painless variance reduction. Mach. Learn., (11(12)4339-440000 2022.
Benjamin Dubois-Taine Sharan Vaswani, Reza Babanezhad, Mark Schmidt, and Simon Lacoste- Julien. Svig meets adagrad: painless variance reduction. Machine Learning, pages 1-51, 2022.
Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 687-697, 2018a.
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. Advances in Neural Information Processing Systems, 31, 2018b.
Ian J. Goodfellow, Mehdi Mirza, Xia Da. Aaron C. Courville, and Yoshua Bengio. An empirical investigation catastrophic forgeting in gradient-based neural networks. In Yoshua Bengio and Yann LeCun, editors, 2nd International Conference Learning Representations, ICLR 2014, Banff. AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Elad Hazan. Introduction to online convex optimization, 2023.
Michael Hersche, Geethan Karunaratne, Giovanni Cherubini, Luca Benini, Abu Sebastian, and Abbas Rahimi. Constrained few-shot class-incremental learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, pages 9057-9067, 2022.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26, 2013.
Ali Kavis, Stratis Skoulakis, Kimon Antonakopoulos, Leello Tadesse Dadi, and Volkan Cevher. Adaptive stochastic variance reduction for non-convex finite-sum minimization. In NeurIPS, 2022.
Harry Kesten. Accelerated stochastic approximation. The Annals of Mathematical Statistics, pages 41-59, 1958.
Jack Kiefer and Jacob Wolfowitz. Stochastic estimation of the maximum of regression function. The Annals of Mathematical Statistics, pages 462-466, 1952.
James Kirkpatrick, Razvan Pascanu, Neil Rabinowitz, Joel Veness, Guillaume Desjardins, Andrei Rusu, Kieran Milan, John Quan, Tiago Ramalho, Agnieszka Grabska-Barwinst Barninswww et al. Overcoming catastrophic forgetting in neural networks. Proceedings of the national academy of sciences, 114 (13):3521-3526, 2017.
Suhas Kowshik, Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Near-optimal offline and streaming algorithms for learning non-linear dynamical systems. Advances Neural Information Processing Systems, 34:8518 8-331,, 2021a.
Suhas Kowshik, Dheeraj Nagaraj. Prateek Jain, and Praneeth Netrapalli. Streaming linear system identification with reverse experience replay. Advances in Neural Information Processing Systems, 2021b.
Guanghui Lan and Yi Zhou, An optimal randomized incremental gradient method. Mathematical programming, 171:167-215, 2018.
Guanghui Lan, Zhize Li, and Yi Zhou. A unified variance-reduced accelerated gradient method for convex optimization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Process- ing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 10462-10472, 2019a.
11

---

Published as a conference paper at ICLR 2024
Guanghui Lan, Zhize Li, and Yi Zhou. A unified variance-reduced accelerated gradient method for convex optimization. Advances in Neural Information Processing Systems, 32, 2019b.
Zhize and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 5569-5579, 2018.
Zhize Li and Peter Richtárik. Zerosarah: Efficient nonconvex finite-sum optimization with zero full gradient computation. CoRR, abs/2103.01447, 2021.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal probabilistic gradient estimator for nonconvex optimization. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning. ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 6286 6295. PMLR, 2021.
Hongzhou Lin, Julien Mairal, and Zaid Harchaoui. Catalyst acceleration for first-order convex optimization: from theory to practice. Journal of Machine Learning Research, 18(1))7854-7907, 2018.
Qihang Lin, Zhaosong Lu, and Lin Xiao. An accelerated randomized proximal coordinate gra- dient method and its application to regularized empirical risk minimization. SIAM Journal on Optimization, 25(4): 222122222222222--- 2015.
David Lopez-Paz and Marc' Aurelio Ranzato. Gradient episodic memory for continual learning. Advances in neural information processing systems, 30, 2017.
Michael McCloskey and Neal Cohen. Catastrophic interference in connectionist networks: The sequential learning problem. In Psychology of learning and motivation, volume 24, pages 109-165. Elsevier, 1989.
Martial Mermillod, Aurélia Bugaiska, and Patrick Bonin. The stability- plassiiityy dilemma: Investi- gating the continuum from catastrophic forgetting to age-limited learning effects, 2013.
Aryan Mokhtari, Mert Gürbüzzalaaan, and Alejandro Ribeiro. A double incremental aggregated gradient method with linear convergence rate for large-scale optimization. In 2017 IEEE Interna- tional Conference on Acoustics. Speech and Signal Processing, ICASSP 2017, New Orleans, LA, USA, March 5-9, 2017, pages 4696-4700. IEEE, 2017.
Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regres- sion with markovian data: Fundamental limits and algorithms. Advances in neural information processing systems, 33: 1ee11666616660 16676, 2020.
Yurii Nesterov. Introductory Lectures on Corvex Optimization: Basic Course. Springer Publishing Company, Incorporated, edition, 2014. ISBN 1461346916
Cuong V Nguyen, Yingzhen Li, Thang D Bui, and Richard E Turner. Variational continual learning. arXiv preprint arXiv: 1010.70000000001 2017a.
Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takác. SARAH: A novel method for machine learning problems using stochastic recursive gradient. In Doina Precup and Yee Whye Teh, editors, Proceedings of the 34th International Conference Machine Learning, ICML 2017, Sydney, NSW. Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pages 2613-2621. PMLR, 2017b.
Nhan H. Pham, Lam M. Nguyen, Dzung T. Phan, and Quoe Tran-Dinh. Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization. J. Mach. Learn, Res., 21: 110:1-110:49 2020.
12

---

Published as a conference paper at ICLR 2024
Sashank J. Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Póczos, and Alexander J. Smola. Stochastic variance reduction for nonconvex optimization. In Maria-Florina Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference Machine Learning, ICML 2016, New York Cit, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 314-323. Jog.. 2016.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pages 400-407, 1951.
Amir Rosenfeld and John K Tsotsos. Incremental learning through deep adaptation. IEEE transactions on pattern analysis and machine intelligence, 42(3): -63, 2018.
Nicolas Roux, Mark Schmidt, and Francis Bach. stochastic gradient method with an exponential convergence _raaee for finite training sets. Advances in neural information processing systems, 25, 2012a.
Nicolas Le Roux, Mark Schmidt, and Francis R. Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Peter L. Bartlett, Fernando C. N. Pereira, Christopher J. C. Burges, Léon Bottou, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 25: 26th Annual Conference Neural Information Processing Systems 2012. Proceedings of a meeting held December 3-6, 2012, Lake Tahoe, Nevada, United States, pages 2672-2680 2012b.
Paul Ruvolo and Eric Eaton. Ella: An efficient lifelong learning algorithm. In International conereereecclloffeeeneeee on machine learming, pages 507-515. PMLR, 2013.
Shai Shalev-Shwartz and Tong Zhang. Accelerated mini-batch stochastic dual coordinate ascent. Advances in Neural Information Processing Systems, 26, 2013a.
Shai Shalev-Shwartz and Tong Zhang. Stochastic dual coordinate ascent methods for regularized loss minimization. Journal of Machine Learning Research, 14(1), 2013b.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. J. Mach. Learn. Res., 11 11:2665-2670, 2010.
Shagun Sodhani, Sarath Chandar, and Yoshua Bengio. Toward training recurrent neural networks for lifelong learning. Neural computation, 32(1):1-35, 2020.
Shagun Sodhani, Mojtaba Faramarzi, Sanket Vaibhav Mehta, Pranshu Malviya, Mohamed Abdel- salam, Janarthanan Janarthanan, and Sarath Chandar. An introduction to lifelong supervised learning. arXiv preprint arXiv:2207.044 043544, 2022.
Chaobing Song, Yong Jiang, and Yi Ma. Variance reduction via accelerated dual averaging for finite-sum optimization. In Hugo Larochelle, Marc' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NewrIPS 2020, December 6-12, 2020, virtual, 2020a.
Chaobing Song, Yong Jiang, and Yi Ma. Variance reduction via accelerated dual averaging for finite-sum optimization. Advances in Neural Information Processing Systems, 33:833-844 844, 2020b.
Endel Tulving. How many memory systems are there? American psychologist, 40(4):385, 1985.
Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer, Florence d' Alché-Buc, Emily B. Fox, and Roman Garnett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2403-2413, 2019,
Lin Xiao and Tong Zhang. A proximal stochastic gradient method with progressive variance reduction. SIAM J. Optim., 24(4):205--2075 2014.
Jaehong Yoon, Eunho Yang. Jeongtae Lee, and Sung Ju Hwang. Lifelong learning with dynamically expandable networks. arXiv preprint arXiv: (.Xiv:/70..00 170..078.4444444 2017.
13

---

Published as a conference paper at ICLR 2024
Junyu Zhang and Lin Xiao. A stochastic composite gradient method with incremental variance reduction. Advances in Neural Information Processing Systems, 32, 2019.
Lijun Zhang, Mehrdad Mahdavi, and Rong Jin. Linear convergence with condition number in- dependent access of full gradients. Advances in Neural Information Processing Systems, 26, 2013.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduced gradient descent for nonconvex optimization. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 3925-39360 2018
14

---

Published as a conference paper at ICLR 2024
A FURTHER RELATED WORK
In this section we present more extensively all work related to ours. This work lies in the intersection of convex finite sum minimization and incremental learning.
Finite Sum Minimization: As already mentioned, our work is closely related with the long line of research on variance reduction methods for strongly convex Nguyen et al. (2017b); Defazio et al.
(2014); Allen-Zhu (2018)); AAllen (2017); (017)){Rom)) Roux et al. (2012b); and Zhang
(2014); (2
Mokhtari Mokhhar)
et al.
and Zhang (2013); Allen- (201 7): Allen-Zhu (2018b); Zhang al. (2013);
Shalev-Shwartz and Zhang] 20133); Nguyen et al. (201 Defazio et al. (2014); Allen-Zhu (2018);
Allen-Zhu (2017 Roox et al. (201 2b); Xiao and Zhang 2014), convex Lan al. (2019b); Dubois
Taine et al. (2022); Song et al. (2020a; Lan et al. (201 Song et al. (2020b); Lin et al. (2018 2):
Delyon and Juditsky (1993); Lin et al. (2015); Shalev- -Shartt- and Zhang (013b) Dubois- Taine et al.
(2022) and non-convex Allen Zhu and Yuan (2016): Allen- (201 : Wang et al. (2019); Pham
et al. 2020); Li and Richtárik (2021); I) et (2021; Fang et al. (2018a) Zhou et al. (2018) Reddi
et al. 2016): Li and Li (2018); Kavis et al. (2022) finite- sum minimization (see also Appendix A for
a more detailed discussion). As already mentioned the basic difference with our work comes from the fact these work concern the standard finite-sum setting while ours concerns its continual counter-part.
Our work leverages two components of variance reduction techniques. Recent works in variance reduction such as the SVRG algorithm Johnson and Zhang (2013) and the Katyusha algorithm Alleen Zhu (2017); AAlenn Zhu (2018)) primarily leverage a full gradient computation, which is essentially used substitute for the gradients that are not computed in this iteration, in order to reduce the variance of their gradient estimator. Older methods, which seek to accelerate SGD, such as the RPDG method Lan and Zhou (0018) and the SAG method Roux al. (2012a), which is randomized variant of the IAG method Blatt et al. 2007]. use stochastic average of the current gradient that it sampled and substitutes the rest of the gradients with ones computed from previous iterations. Our method seeks to utilize the first technique, but the complexity constraint does not allow for this tool. We mitigate this problem using a technique similar the incremental gradient methods. There are also several other methods and techniques that relate to accelerated stochastic gradient methods, both in the convex setting Song et al. (2020b); Allen-Zhu and Yuan [2016); Lann et al. (2019b): Lin et al. (2018); Kesten (1958): Delyon and Juditsky| (1993); Zhang et al. | (2013); Lin et al. (2015); Shalev-Shwartz and Zhang (201 3b a); Dubois- Taine et al. (2022) as well as in the non-convex setting Zhang and (2019); Fang et al. (2018b). In the past there have also been several works that focus on finite sum minimization in dynamic settings using SGD Kowshik et al. 2021b a1: Nagaraj et al.
(2020)
The other side of this work is incremental learning, the goal of which is adapting a model new information, data or tasks without forgetting the ones that it trained on earlier. The phenomenon of losing sight of old information is called catastrophic forgetting Castro al. (2018); Goodffllow et al. 2)014;;B Kirkpatrick al. (2017): ( McCloskey and Cohen (1989) and is one of the main challenges of incremental learning. The area closest to our work from the field of incremental learning is lifelong learning. In this area catastrophic forgetting expressed in the "stability-plastiiityy dilemma" |Mermillod et al.) (2013). There have been three main approaches to tackle this issue, regularization based approaches Nguyen et al. (2017a), memory based approaches Tulving (1985) and architecture based approaches Yoon et al. [2017);[Lopez) Lopez-Paz and Ranzato (0177). As shown in the current literature, combinations of these methods can be utilized in practice Sodhani et al. (2020) well. All of the previous directions are studied in depth in (Sodhani et al. (2022) and a brief overview of the techniques of the field is also presented in Castro el al. (2018). The area of lifelong learning also includes algorithms such as ELLA Ruvolo and Eaton (201))
Incremental Learning:
B PROOF OF LEMMA 6
In this section we provide the proof of Lemma 6
Lemma 6. Let d.j E 'D the ousput of Algorithm 7 for stage j E [n]]. Then all i E {j + 1, 1....,n).
8 - - 20112 <
(((--))
G(i ()i j) + 2 22 - 2;
2
itj
15

---

Published as a conference paper at ICLR 2024
The proof of Lemma follows by the proof of Lemma 7 that state and prove up next. The proof of Lemma is deferred at the end of this section.
Lemma 7. For all i (n 1] and j [n ---i
2jG (u + j)
|| - x3 12l
where x; = arg min (z( and oitj = arg meD (i)
Proof of Lemma
By the optimality of 2i+s E D for the function Jo+z (x) we get that
(V9tts ) 2 0
The inequality is shown in (Boyd and Vandenberghe 2004 equation 4.21). From the strong convexity of gi+s (2) get that
11 |+its - 0il13 s (2t5 - 9i+5 (++5())+))= (V8+)((i44): rits)
s (xt)(x;)) - (++s(2i+g)
itj
1 itj
itJ Σ fu(z;) itン
Σ
fu(2)tz)
k=
(9)(2)) (((x(+z))
(fa(z)) - fa(att)))
i+j
kmi+1
i
11
| - 2il12 (VVg: 244s z2))
it
2
itj
1
Σ
(fx(x]) Sa(1)+z))
i+j
k=it1
i+j
i
| - x111?)
itjj Σ G |
xill2
143
k=it1
jG
| - x 11g
(-2 |r4ss
p
2:112)
2
itj
We conclude the section with the proof of Lemma
Proof of 6 By the inequality ||a + b112 s 2|/a||2 2/2 1|6112 we get that
|
x
<
(11=; - =,,l + 1| - =;]l²)
8
2i + ) + ||a x311
Gj
2
n
The second inequality comes from Lemma
7 and strong convexity.
C PROOF OF LEMMA
In this section we provide the proof of Lemma 2
Lemma 2 (Unbiased), Let V the gradient estimator used in Step of Algorithm 2 t [T... E [V!] (g((x.).
Then all
16

---

Published as a conference paper at ICLR 2024
The basic step in order to establish Lemma Lemma Íis deferred at the end of the section.
2 is Lemma 4 that we present up next. The proof of
Lemma 4, At Step 10 of Algorithm
|
it holds that V 1-- Σ (i
Proof of Lemma 4 We will inductively establish Lemma Notice that after stage i = 1, Algorithm |
sets v v (ā1)) Up next show that in case the induction hypothesis holds for stage then it must essentially hold for stage i. Up next we consider the following 3 mutually exclusive cases:
1. prev 2 ar meaning that prev is updated in this stage.
2. (i 1) prev 2 a(i 1) meaning that prev was update in the previous stage.
3. prev ai and (i 1) prev a(i - 1).
For the first case Algorithm reaches Step 5 and thus V.- 2j=1 Vf (f 1)/1 - 1. At the same time prev is set to - 1 meaning that prev = i - and V = I E k= Va (Eprev).
For the second case, Algorithm [ had reached Step 12 at stage i 1 meaning that v = E ff(;--1)// - 1. At the same time prev was set to i - 1, meaning that prev = i and V Vi- - E Vde(ppe)).
For the third case, from the inductive hypothesis we have that:
1 Sa (rprev)))
2
At stage i- 1, V.-1 was calculated according to Step 16 of Algorithm
As result,
1
1 1-1 Vi--(($pro
V--1=
V 1-22
i-2
i-2
1 V f& (aprev)
i- (Spro))
i-li-
2
V Sh (aporr)
Proof of Lemma] Let Fi denote the filtration until step & [Td] of stage E [n]]
By the definition of V at Step of Algorithm 2
we know that
E F. = (1-2)
E V fur (2 - Vfn (B Fi + (..1) + 1 Vf((z))
Pr Pr(u: k) (v)a v S ((ipee))) + &..1. (
(V/+())) - (S(((pp)r)) +Ve1) + (
= Σ Vi((2)) i Σ ( + i-1 --1 VS((at)
i
17

---

Published as a conference paper at ICLR 2024
Lemma 4 ensures that i - Σ k=1
fis (c prev) meaning that
fa 1 Viiatt Vg.(z.).
D PROOF OF LEMMA 3
In this section we provide the proof of Lemma 3
Lemma 3 (Bounded Variance). Let V the gradient estimator used in Step 5 of Algorithm 2 Then for all t E [T.].
L2 4²a
E | - (=((=)))))) s & ||=;
x 21112] + 64
a² + 16L2B ||appre - &prev 1|
where o > O is the purameter used at Step 4 of Algorithm 7
In order to prove Lemma 3 we first state and establish Lemma 5
Lemma 5. For all rounds E T; of stage E [n]].
B[IV:- ( S SLLE ||a| - a s211]] + S [1ao Spre
(6)
where prev is defined in Algorithm
7
Proof of Lemma
5
By substituting the definition of V!:
E V
(xf(
[
(1- :) E
V (xtt)
fuc (f )++++++0) +,-11 Vgi- 1/2
1
2
V Vu, (Spre)) [1]] 2 (1
1 2
2 1
E
fn, (x/)
V (xc)) 6.-1
i
1
fu, (z)) - V fur (S [12]
= 2
1
E
i
1
+2
1
E
V (2por))
2
1 1
1 2
.T2.
||
t prevv
[2]]
+
1
1
2
E
(x
V prev) ))
i
(1 1)2
2
1 7
2. EE || a prevv]
12]
+
1
1-
1
E
V ($peov) 112
(i 1)22
2
1
2. E
||
2
pprev]
[2]
2
1-
1
1
2
E
[[
V f ) 112]
(i
1
1
2
1 E
||ا|
ppee
+2
1
1
2
E
[[VF
V (a (p 112]
2
2
1 11-
1
2
22 E
||
pprev] [
+
(1-
1
1
2
|| - &prev 12] IE
2
1 (1- :
1
L2E ||ا @prco|
[2]
=
2
812
(1
1
[Bl|at x + Blllot
Spree
12)
18

---

Published as a conference paper at ICLR 2024
Proof of Lemma
3 Applying Lemma
6 for j prev we get that,
E
||
& Erevv112
8
G(i prev)
2
+ 21E || Eprev 11
n
+ prev
8
G(i - prev)
Axprev 112)
+ 21F
n2a
i
Gia
2
+ 21E
||
@.reelli [
112
i
8G
a²
2EE
| - 2
The third inequality comes from the fact that i- prev as which is enforced by Step 4 of Algorithm
By Lemma 5 we get that
E
8T.
81
[1, - 1|2]
64G I,2
- x
4² a²
2 || Eprev [
which concludes the proof.
E PROOF OF LEMMA g
In this section we provide proof for Lemma 8
Lemma (Convergence Bound). EfElgg((;) - gン(r)) S e for all stages
E [i - 1] then
2) || - 23 [|]] + x a² 1 T, + 2n 1 [B ()(B 1)(8
E [g, (2;) (x(2))] < Z 8
(7)
P
where 2 T.(T--1) + (T; + 1) 1), = 6T. and 3 = T2T.2/1²²
Proof of Lemma g order to establish Lemma 8 we use Lemma 9 which is similar to (Allen-Zin 2018h Lemma 3.2). The proof of Lemma 9 is presented in Appendix E.
Lemma 9, In case E [ = (x.) then
[g(( -x())) < EE
9
V - V9( Y
14/ 1-47
||01
1/1
||
++1
11?
16
27
27t
(8)
where x/ = llp (2) - 7: V!),
m(++ and 3 = =7222/p² (see Step 1 of Algorithm
2
Lemma 2 (Unbiased). Let V the gradient estimator used in Step of Algorithm Then for all t e [T]]. E | (zr().)
Since Lemma establishes that E[V]]
Vg((=]) can apply Lemma In order bound
the variance E | (x))
appearing in the RHS of Equation 8 we use Lemma 3 (see
Appendix D for its proof).
Lemma 3 (Bounded Variance). Let V the gradient estimator used in Step of Algorithm 2 Then for all t E [T))
L2G²
E || - ( S SL ||=1 x7 112]
aa + 16L2B |1 - Spmer
+ 64
122
where > 0 is the parameter used at Step 4 of Algorithm
19

---

Published as a conference paper at ICLR 2024
As discussed above by combining Lemma 9 with Lemma 3 get the following:
1 7t. + 9L
[9.(x) - g((x]]]
1 E
||
x [12]
Yi
22112
22
2
G2
+
36
arm + 9L
= pprov
[2]
(9)
n²
By the crong-convexity of gpre (-) we get
prpeev 12 S H
2 (ppev (fprev) Iprev (1 prev)) )
and from our inductive hypothesis
E [prev (fposs - Iprev (onev(tronn (# Se
Notice that by the selection of It2 4/(u(t + B)) and 7 //22 of Algorithm 2 we get that
91 1a(1 + 3)
36L
36L2
36L2
36L2
1 2
11
1721.2/
721.2/1
Using the previous inequalities in Equation 9
we get that
[g:(#++1) - [x:(x]]
1t 11/ E
|| -0
Vt
E 211[2
-x,
2
+ 18L2
+ k² G2 2
(10)
Since x 6L/H.
Multiplying both parts of Equation 10 with (t + B 1) and substituting 7t 4/ (u(t B)) we get that
p(l - 1)((+ 8 p(t 3- 1)(( + +32
-2) B ||02 2; 2=1[]]]
(t + 3 - 1)E [9((x - (x]))
||:0
2 112
+ (22Paa +
18L² e )
(t 8 L)
mlt + 3)
where B 77222/1² By setting x 6L/P we get that,
33+ - 1)) (x - (x()) S a(l 3- 1)(1
2) R. || - x xt11]]]
8
p(t 1)( + 3)
||00
2; [12]
8
G² a² + 2n22
k
By taking the summation over all iterations
O.... Tj - 1, we get
T--1
T
Σ (++ 3 1))
(t + 3 1)(t + 2-2)EE ||00] - 17:13
8
H T:-1
Σ
(t+) 3 1)(t + 3)
| x
8
1=
G2
a² + 21?6
+
20

---

Published as a conference paper at ICLR 2024
As result, get that
T:-1
Σ
( 3 (x
96 (x;))
M (3- - 1) 2) [|a 2; =112]
8
M (T. + - 2)(T; +
1)B ||TT: x7
G² a + 2x²e
+
/b
Dividing by 2= = -1= (t+ + 3 - 1) = T((T; - 1)/2 + ( 1) and using the convexity of 9s we get that
12,11
(t
9i
T -1
(++ 3 (++ - 9i(x))
1
1 r (8 1)(3 2) || - 2il12]
G2 + k
a
2T
1
Z 1=U
Z 8
Z
+ 2x T/c
2
As result,
-
1 M z 8
1)(3 2)13 ||=| xills]
22 2x
11
E. PROOF OF LEMMA
In this section we provide the proof for Lemma Lemma 9. In case E[V:]
(zx() then
- EE
9
V
1
14/
|
2/
1
||
16
2-
2
2
(8)
where of = 1l (xf 7a V.
and $ = =7222 /22 (see Step 1 of Algorithm
((++
Proof of Lemma 9
We start with (Allen-Zhu 20186 Lemma 3.2), which we state below.
Lemma 10. Allen-Zhu 2018b) If Wf++ = arg min yin bn |Iv wxl12 + (vv) + ( w) for some
random vector V. E IRd satisfying E E
V f(w)) then for every E Rdd, we have
(FF(w++)-F(u)) SE
| ( (
||
(1- (y)) I|u w. 12
(1 + p
W 2
2(1 nT)
2n
where vb is a proximal term, P&g is its strong convexity and μ is the strong convexity of the optimization function f and q is the step of the algorithm and the function F is defined as:
F(x)) f(x) + sp(x))
For our setting the proximal term is:
(xr) 0, x E D oo, $ DD
This means that μ4p 0. The step 1) for our analysis is n. and f gi- By taking u = x = arg min (x(x)) and since due to projection on
F(x(+1)= g: (x(++)
( y (1)
21

---

Published as a conference paper at ICLR 2024
the inequality can be restated as:
Blg (1)(( E
7
V
1-44
1-
p47
2
11
||
+
2
2(1 7cL)
27
2
Notice that by the selection of n/- = 4/ (1(t + B)) simplification
Step 6 of Algorithm
2 we can do the following
18
(1 (L~ (1
aL ((++
(1
11
(1
4 72L
(1
+/2
17
which gives the theorem statement. The last part of the proof required, is to show that the following two update rules are equivalent.
" min 1 yERd
||u
-r (bv) + (V),))
2%
++1
Th
(z)
7/ V.)
which is well known fact in the literature and this concludes the proof.
F OMITTED PROOFS OF SECTION
F.1 PROOF OF LEMMA 1
In this section we prove Lemma for the sake of exposition we restate it up next.
Lemma 1, Over a sequence of n stages, Algorithm 7 reaches Step 5 and 12, [logn/o] [ times.
Proof of Lemmal
Step and 12 are only executed when the following inequality is satisfied:
- prev 2 a aa-i=
prev
(11)
Once Algorithm| reeches Step 5 and 12 it necessarily, reaches Step 13 where prev updated to i. Let 2p 1, 21,..... ..... _ky... the sequence of stages where 2μ denotes the stage which Algorithm [ reached Step and 12 for the k-th time. By Equation we get that 24+1 Z I-a
implying that
2k
Since 2µ we get that & < log
Notice that log
=-log(1 a) 2 1 - (1 a) I-a
log
log and thus & <
Using Lemma we can now also show Corollary
Corollary 1. Over sequence of n stages, Algorithm requires 3 E T, + 2n logn/ai FOs.
At each iteration of Algorithm 2 3 FOs (Step 5) and thus Algorithm requires overall 31, FOs during stage i [n]. At Step and 12 Algorithm requires at most n FOs and thus by Lemma overall requires 2n flo n/ FOs.
Proof of Corollary 7
F.2 PROOF OF THEOREM 4
In this section we provide the proof for Theorem 4 for the sake of exposition we restate it up next.
Theorem a convex and compuct sei and a sequence y-strongly convex functions f1..... In with fo D R. Then Algorithm 1 with T, 720GL" /
922/3/2/3 G2/33/e////1)//
864L2 1²2 and puel// /(20G2/3
guarantees
E [g.( (x())) S e for each stage E [n]]
where 3;; E D is the output of Algorithm 2 at Step 9 of Algorithm
22

---

Published as a conference paper at ICLR 2024
Proof of Theorem 4 At stage := 1, Algorithm I performs gradient descent using fi in order to produce 1 E D. The latter requires O (L (og((1/)))/) FOs. Let us inductively assume that,
E و (2,) 91(35) S for all j E [i.
Using the latter we will establish that Elg: (f:)] [(();) ك 6. In order to do the latter we first use Lemma The proof of which can be found Appendix Hand its proof is based on the fact that the estimator V is unbiased and admits bounded variance (see Lemma and 3
Lemma 8 (Convergence Bound).
If Ef (2,)] g)(0)) S for all stages E [i 1] then
1 E [g. (f:) - (x(2))) - 2 8
P (B - ()(B-)(B-- 2) || - 2 111
+ G2 -1, + 2n²
(7)
where T.TT,-1) + (T: + 1)(8 1), x = 6 and 7212 112².
Since the conditions of Lemma g are ensured by the induction hypothesis, we will appropriatcly select T; such that the right-hand side of Equation i is upper bound by > O.
At first, we upper bound the term E |z x [[2] appearing in the first term of the RHS of Equation
Recall that in Step 2 of Algorithm
2 we set x! t - E D. As a result,
||> x :1 = | - 2
In order to upper bound the term || - 2; 112 we use Lemma 6 the proof of which can be found in Appendix B
Lemma 6. Let 2, E D the output of Algorithm 7 for stage E [n]]. Then for all i E ti + n..
8 n22
G(i ()
| x1112 <
+ - =3
itj
Applying Lemma 6 for := i i-1 we get that
x;
[ = E [| - 2/112 11
8
2
+ +E 2E || 21
(12)
n2
2i - 1
By the inductive hypothesis we know that E [gi- convexity (-)-), we get that
( - -i-1 (z S cadd thus by the strong
E [|| -x [2]
which yields Equation 13
G
2
|| - x; 2;112] S 4
+ -
(13)
2i -
The value of can be lower bounded as follows:
z T. 1)/2 + (T, + 1)(B 1) 2 - T
So by combining Equation 7 with the previous two inequalities we get:
Elg (x7)) s
T?
4
8
M (B--1)(8
2)
122
8
2i
1
G
2
+
c
= +
4G
2E
(8 1)(8 2) + 4x² G2 a²
8k
1T - 1)2
T?
Tip
T
Now the upper bound on (2;)) - gr (z+) admits four terms all of which depend on T,. Thus we select T; so that each of the terms is upper bounded by e/4. Namely,
23

---

Published as a conference paper at ICLR 2024
2c (2- (3 1)(3 2)
102
S c//4
T7 (3 1)(3 - 2)
51/4
4k2 o²
s//4
TTi 8m2 TT
S S//4
Since 6,, we get that we can set T; as follows,
GL
1
L
T.
max
204
576
1152
/1/2///2
GL
L3
L
max
576
1152
PT
112
GL?
L
192
576
+152
11a
The proof is completed by selecting //1 (9////
G PROOF OF THEOREM
this section we provide proof for Theorem [
Theorem There exists a first-order method, CSVRG (Algorithm 7 for continual finite-sum sum minimization ( with O (,//3/2/3
(121
llgg
L²G
log
FO complexity.
el/a
25/2
v
Proof of Theorem 1 The proof of Theorem
follows by combining Theorem and Corollary and F.
Their proofs are respectively in Appendix F2
Theorem a convex and compact set and a sequence u--troogly convex functions fi.... In with fo D E. Then Algorithm 1 with T; 720GL 720GL2/(u>/Piv/) 912/3 122/8 864L2 μ² and 1/3 /20G2//2 273), guarantees
E [g, (x. (xx))
for each stage E [n]]
where i; E D is the outpur of Algorithm 2
Step 9 of Algorithm
Corollary 1. Over sequence of stages, Algorithm requires 3 E T. 2n logn/o/ FOs.
Using the selection of T. provided Theorem to Corollary we get that
720GL2 n
92/2/3
I
864
1512 Ve
e1/3
112
720GL2
922
I2
log n +
+ 864
15/2
el/31
112
At the same time, using the selection of a provided in Theorem we get
2n logn/a== = 40 2/ n log
1/3
H PROOF OF THEOREM
In this section we provide the proof of Theorem We first present an intermediate theorem that is the main technical contribution of the section.
24

---

Published as a conference paper at ICLR 2024
Theorem 5. Let natural first-order method A (even randomized) that given sequence of n strongly
convex functions fn outputs a sequence ii,.... ......,,. E DD by performing overall o(n²) FOs. Then there exists sequence of strongly convex functionss f1..... with [-1,1] + R and Jr, I. O(1) such that
[1oa((a)) -x; 2 2 (1/n*) for some stage E [ni]
The proof of Theorem lies in Section
To this end we Theorem 5 establish Theorem S
Theorem 3. For any > O, there natural first-order method for Problem (2) with O
FO complexity. Moreover for any a < 1/4, there is no natural first-order method for continual finite-sum minimization (2) with O (n/c²) FO complexity.
Proof of Theorem Let us assume that there exists a natural first order method A with overall complexity O (n= log(1/e)) for some > O. By setting O(1/n"), we get that there exists natural first-order method that for sequence fi....; : fn guarantees
E [g:( (x;)) S 2000 (1/n²)
for each stage E [n]]
with overall FO complexity O(n²~a log n.). However the latter contradicts with Theorem 5
Respectively let us assume that there exists natural first order method A with overall complexity O (n/c") for some a 1/4. By setting e O(1/n*), we get that there exists a natural first-order method that for sequence fi...-, Jn guarantees
E [g:( (x;)) (1/n²) for each stage i E [ni]
with overall FO complexity Of/4))/4) However the latter contradicts with Theorem
H.1 PROOF OF THBOREM
Proof of Theorem 5 To simplify notation, denote with [x]e the coordinate & of vector Rd. In our lower bound construction we consider == 2.
Since A performs o(n²) FOs then there exists stage i such that Eeer. 1Q i/2 (otherwise the overall number of FOs, Σie()) Σier; | n²/4). Using this specific index i E [n] we construct the following (random) sequence of functions fI....,fw where each fr [ 1, 1]2 + R:
([x)1)² + ([x]2)²
( Siik k t= k t=i
fe(x)
([r)1)² + ([x2))++ [[x]]-11000 (2)p)
--) 1)2 ([)))) ((12))
where & Unif(1,.... 1).
Before proceeding we remark that each function ft [-1, + R is G-Lipschitz, L-smooth and μ-strongly convex with G, L, (1)).
Corollary 2. Each fe: [-1, 1]2 + R is 2-strongly convex, 6-smooth and 2-1isshht
Let the initial point of A be at 6 111,13
Notice that fe, 0) (0, 0) for each fl Ef i. Since A is natural first-order method then Definition implies that A always remains that (0, 0) at all stages j S 1. The latter is formally stated and established in Lemmal []]
Lemma 11. For any stage E ji
[At]1 [ =0
[=t]] [xr]]a 0 for all rounds i [T}]-
25

---

Published as a conference paper at ICLR 2024
The proof of Lemma II lies in Section H.2 Its proof is based on the simple observation that if AA has
stayed at (0,0) at all stages E - i 2. Then at stage + 1 S - 1, Item 1 of Defimition
3 implies that A always queries (0, 0) for some j S i meaning that V f0,, 0) (0, 0). Then Item 2
and 3 of Definition 3 dirrectly imply that st = (0, 0) and ã. = (0,
Corollary 3. With probability greater than 1/2, the function fú. is never queried during state i. In other words, Iindex + for all E UbET,
Proof. By the selection of stage [n], we know that Eier, |Q S i/2. Since was sampled uniformly at random in { - 13. Pr [findex o k for all qE ULEn Q11 2 1/2.
Notice that for all & * i, fe(.,
(:.0). The main idea of the proof is that in case i is never queried during stage i, (findex # k for all E Usen 2 then all FOs during stage admit the form findexx (Ivalue) = V findes( (:; 0) (::0) 0). The latter implies that if Jindex o k for all q E Uter; Q
then [2:]2- = 0.
Lemma 12. In case quadex # for all q Usen Qi then [a,]2 =0. O.
The proof of Lemma 12 is based on the intuition that we presented above. Its proof is presented in Appendix H.2
To this end we are ready to complete the proof of Theorem 5 Combining Lemma 12 with Corollary
we get that
Pr [[::]2 = 0] 2 1/2.
(14)
Up next we lower bound the error ( - gi(x)) in case [#t]]2 = O.
By the definition of the sequence f1, ......... fk..... fi. get that
1
g((x)) == ([x)))² ([x)] 1)² + & ([x) - [xl2]] + ((x12)²
In case [ix]p = we get that
(1+
1 ((5:111) + 1 ([t=]1 1)²
g((2.)
[ [ + 1) w² (ww 1)²]
min wE[-1,1]
notice that w*
i + 2
i + 2) + (i+ 1)2 i+1
i i+1
i(i + 2)2 +
At the same time, the minimum g(xx; equals,
ge(xt) = ((x))))² + ((+)) - 1)2 + ((xح) - [xt12)² + =(x+112)
1 7 (w 2)2 2)²+ +2²
i+1
min m,,
w + (w- - 1)a² +
notice that (w*, to²,z")= =
12 + 3i
+ 1 12 + 3i +
i+1
2
1 + 32 +1 -1)
i+1
i+1
1
2
+ i
+
12 + +3+++11
12 - 3i
+1
12 +
3i
+1
12 + 3i
+1
By taking the difference (d::)
91(17) ) we get that
ge()))) (x;)
2
min
w² + (w 1)2
min
1
w + 1
(w - -1)²
+
1
(w 2)²
wE|-1,1]
w,=6
1,1
i i+1 1
i+1
i 1
i+1
1
1)
2)
12 + 3i +
12 3i
12 12+3 31 +1
72
4
1
12 + +i+1.
1
71 + 573 +72 + 2i
26

---

Published as a conference paper at ICLR 2024
We finally get that
E (o)( (x,))
= Pr Pr[ = 0] R [(( gi(,;)
[ = 0] [is]2 + 0]
Pr [[ii)] + 0] B(g((e)) ge(o;)
2 4 + 772 2i
Iv Q (1/n")
H.2 OMITTED PROOFS
Corollary 2. Each fe [-11,1]3 R is 2-strongly convex, 6-smooth and 2-isschtitz
Proof. Notice that Hessians
2
v2f((x) 0
for l + i, k. Meaning that fo is 2-strongly convex and 2-smooth.
-2
(z)((z) =
for & i, Meaning that fz is 2-strongly convex and 6-smooth.
-2 4
4
for ll + i,k Meaning that fe is 2-strongly convex and 4-smooth.
0 2
Respectively notice that the gradients
Vf(()) 1(, (z]2) and thus maxph [[ S 222 As a result, fe(#) is 2s/22-Lipschtiz in 1|.
V=x(x) = 2(2[x]] - [x]2, - [x)]1) and thus maxpe). [V/a(>)] S 6v2. As a result, fa(x) is 6 in [-1, 1]a.
fz()) 2(2[z]1 -,,((=]2) and thus max [[)((=)] 4. As result, fe(x)) is 4-Lisschtiz in 11.
Lemma 11. For any stage ji 1).
[Ey]1 [Øy]2 0
[x/]] [xr)]2 for all rounds i [T})-
Proof of Lemmal
17 By the construction of the sequence fi,..., Sax get that for all e 1,
.
Ve(()) = 2 ([=),, [x]2] for * k.
(z) (2[z)1 [z]2. 2[x] [x:]1)
Thus in case x = (0, then Vfe(z) = V/a (x) = (0,0).
Up next inductively establish Lemma 11 For the induction base first establish that stage t==11 1,
Corollary 4. For stage = 1,
क (0, for all rounds E (Ti).
27

---

Published as a conference paper at ICLR 2024
11 (0.0)
Proof. At round / ;= of stage l ;= 1, Item of Definition ensures that for all FOs E Q
Gindex 1 and Qvalue
(0,0)
Since Vz((x) 2x, the latter implies that V V. fqndexx (Avalue) = (0,0) for all E Qi. Thus Item 2 of Definition 3 @ensures that ø] (0, 0).
We prove Corollary through induction.
Induction Base: =1 (0,0)
Induction Hypothesis: 21 (0, for a {1,...,t 1).
Induction Step: of (0,0)
Item Definition 3 ensures that for all q E Qi Ivalue E (U) and thus by the inductive hypothesis Ovalue
0). Thus
V fonddxx (Ivalue) (0,0) for all (gindex Qvalue) Ur
Then Item 2 of Definition implies that 2 = (0, 0).
To this end we have established that 2f (0, 0) for all [Ti]. Then Item 3 of Definition iimpies that 21 0).
We complete the proof of Lemma 11 with a similar induction.
Induction Base: of = (0 for all 1 E [Ti] and 41 = (0,
Induction Hypothesis: z (0, 0) for all t E [Te] and it (0, 0), for all stages l e <i-2
Induction Step: 2/41 = (0, 0) for all [Te+1] and 8e+1 = (0,0)
Let us start with round == 1 of stage + 1. Item 1 of Definition 3 together with the inductive hypothesis ensure that for any FO E Q/+1+ Ovalue (0, 0). Since Gindex I l + 1 I i 1 we get
that
Si (Ivalue) = (0,0) for all queries E Q The latter together with Item 2 of Definition imply
x x = (0,0).
Let us inductively assume that 2 = 0). Then we the exact same argument as before we get that
S (gvalue) = (0, for all queries g E Q++1
To this end we have established that 2 (0, 0) for all t E [Te+1]. Thus Item 3 of Definition implies that ee+1 = (0, 0). The latter completes the induction step and the proof of Lemma Then again Item 2 of Definition implies that
x (0, 0).
Lemma 12. In case Tindex # for all E UseT, Q₁ then [i.]2 = 0.
Proof of Lemma
12 First notice that
Vf(()) = 2 ([x),, (x]2) for l + k
Vf((x) ((2 [x]22)
28

---

Published as a conference paper at ICLR 2024
Thus for any ([z]1, 0). V fe(z)) 2([z]1,0) and (f((2)
2(2/x)1 1, 1,.). Using the latter observation and the Lemma we inductively establish that in case Tindex # for all E Usen Qi then
5t = (l
We start by establishing the latter for =1 1.
Corollary 5. In case findex + k for all Uten Qi then x = ([r5)1,0)
Proof. Lemma 11 ensures that for all stages $
00 for all E [TT].
52 (0
The latter together with Item of Definition imply that Ivalue (0,0) for all q E Q, Since Baddex # lo for all Q, get that
V fandex (gvalue) (-, for all q Q!
Then Item of Definition
3 implies that s! = (,,
We complete the proof of Lemma 12 through an induction.
Induction Base: o! = (.,0)
Induction Hypothesis: xt = (.,0) for all r S--1
Induction Step: z." x (+,0)
The induction hypothesis together with Lemma IT and Item of Definition 3 imply that for each FO
q E Q Qvalue O). Since lo # qvalue for all q Q we get that
fg (Avalue) (-, 0) for all g E Q
Then Item 2 of Definition
3 implies that xt (:: 0).
To this end our induction is completed and we have established that of (1,0) for all f E [7:). Then the fact that f (- 0) is directly implied by Item of Definition
29

---

Published as a conference paper at ICLR 2024
I SPARSE STOCHASTIC GRADIENT DESCENT
In this section we present the sparse version Stochastic Gradient Descent, called SGD-Sparse (Algorithm 4) that able to ensure accuracy > at each stage i E [n]] with DDG* log FO complexity.
22
In Algorithm we first present SGD for specific stage E [nx].
Algorithm 3 StacchattiGraalinnDDecmmttiiii
1: zó - I D
2: for each round
,; do
3: Sample je ~ - 1})
4: x/ IlD (a. -1 (1)
5: end for
return 2, + ET= /
6:
SGD-sparse is presented in Algorithm Algorithm 4 tracks sparse sub-sequence of stages i E [n] (prev (1 + a)) < i) at which the returned point 2; is produced by running SGD (Algorithm 3 for T
iterations. In the remaining epochs Algorithm 4 just returns the solution of the last stage which
SGD was used è + &prev. Step Algorithm 4h. Notice that the sparsity of the SGD-call (Step 4)
0. For example for 0, Step 4 is reached at each stage E [n] while for large values of a 2 0, Step 4 might never reached.
controlled by the selection of the parameter
Algorithm 4 StochastiiGradienneeeeeessss
1: 4o E D and prev f-
2: for each stage == .....,7. do
3: if prev (1 a) < i then
4:
à; - StoclasticCraatinnnDesscdd/ 1,, # output ă, E D for stage i &prev f- 2, 6: prev t-
5:
7: else
8:
è; + Spee # output it E D for stage
9: end if
10:
end for
In the rest of the section we establish the formal guarantees of SGD that are formally stated in Algorithm We start by presented the well-known guarantees of SGD.
Theorem 6 (Hzzan 2023)). Let f; == StachhatiiCrraaeenDDecccff (1 where = 1/ T: = C and G = max,eD fx))]. Then, E (.. 9: S
Theorem Let convex and compact set D and a sequence of u-strongly convex fi....,
with f. D + R. Then Algorithm 4 with T; O _2
2لoح and 7 1/u, guarantees
E (āx)) gx(x:)) S e for each stage [n]
G logn e"
The FO complexity of Algorithm 4
30

---

Published as a conference paper at ICLR 2024
Proof. In case i = prev then by selecting T = O E [g:(4:) (x())
G and y = 1 1/4, Theorem 6 implies that
[9.(2:) (x())) S c/2. Up next we establish the claim for prev v (1 + a) prev.
E (Fpee))))) ) - ge(x0;) (#: Sprer Step of Algorithm
E
(ppee))
(xttt
prev
E pp (1 Preve
E [f (pppee))
prev
9pee (n;)(
Σ fz(t))
g p-prev++
prev
EE 19 (3 (pprev) )] 9prev (2t)) + (f ffy
j=prev+1
prev
prev
(E 1oprev (Fprev) )] Sprev (3r²)
|D|G
prev
E Upree (Fprev)) Sprev (Fpeev) Sprev (xpee) Spree (177)
+ i prev
prev
50
prev
Urrev (2 (p + |D| i- prev
E Upee (Fprev) )]
prev
prev
D
prev
DDG (1 a)prev prev
prev
DD
To this end we have established that E [px())) (x;) S for each stage [m]] We conclude the proof by upper bounding the overall FO complexity of Algorithm 4
An execution of Stochastic Gradient Decent at Step of Algorithm that calculates an e/2 optimal solution requires O (G² (uc)) FOs. Let now upper bound the required executions of SGD. Let denotes number of times Algorithm A reached Step 4 over the course n stages. Due Step 5 of Algorithm
(1+ D
In n2
Inn n
log n
< n
< 4/D|G
In(1 + 2/1G0)
T+ 21111
Thus the overall FO complexity of Algorithm
iis O
( log uee
31

---

Published as a conference paper at ICLR 2024
J EXPERIMENTAL DETAILS
In this section we present additional experimental evaluations LIBSVM datasets.
72101
Table 3: Optimality gap as the stages progress ridge regression problem (averaged over 10 independent runs). CSVRG performs the exact same number of FOs with SGD and slightly less than SGD-sparse. Katyusha and SVRG perform the exact same number of FOs. CSVRG CSVRG/SGD/SGD. sparse perform roughly 4% of the FOs of patyusha/svRC
In Table 4 and we present the parameters of the various method used in our experimental evaluations. We remind that À = 10-3
Method SGD
breast cancer
cod-rna
diabetes
step size: (tA)-1
step size: (fX)
step size: (fA)
T: 300
T: 300
T: 300
SGD-sparse
step size: (tX)-1
step size: (1A)-1
step size: (fX)
T: 414
T: 480
T: 480
0.002
a 0.002
a: 0.002
Katyusha
step size: 1/(3L)
step size: 1/(3))
step size: 1/(3L)
Outer Iterations: 10
Outer Iterations: 10
Outer Iterations: 10
Inner Iterations: 100
Inner Iterations: 100
Inner Iterations: 100
L: 0.0522
L: 0.015
L: 0.01262
SVRG
step size: 1/(3))
step size: 1/(3L)
step size: 1/(3L)
Outer Iterations: 10
Outer Iterations: 10
Outer Iterations: 10
Inner Iterations: 100
Inner Iterations: 100
Inner Iterations: 100
L: 0.0522
L 0.015
L: 0.01262
CSVRG
step size (itX)
step size i: (itA)-)
step size at i: (itX)
T. 100
T, 100
T. 100
== 0.3
0.3
0.3
Table 4: Parameters used in our experiments
32

---

Published as a conference paper at ICLR 2024
Method
german.numer
skin-nonskin
SGD
step size: (1X)-1 T: 300
step size: (tX)
T: 300
SGD-sparse
step size: (IA)-1
step size: (IA)
T: 414
T: 480
a 0.002
0.002
Katyusha
step size: L/(3L)
step size: 1/(3L)
Outer Iterations:
Outer Iterations:
Inner Iterations: 100
Inner Iterations: 100
L: 0.0317
L: 0.068
SVRG
step size: 1/(3T)
step size: 1/(3T)
Outer Iterations: 10
Outer Iterations: 10
Inner Iterations: 100
Inner Iterations: 100
L: 0.0317
L: 0.068
CSVRG
step size at i: (itX)
step size at i: (itA) 1
T, 100
T: 100
0.3
a 0.3
Table 5: Parameters used in our experiments
33

---

Published as a conference paper at ICLR 2024
K EXPERIMENTAL EVALUATIONS WITH NEURAL NETWORKS
In this section we include additional experimental evaluations CSVRG, and SVRG for the con- tinual finite-sum setting in the context of 2- 2-Layer Neural Networks and the MNIST dataset. More precisely, we experiment with Neural Networks with an input layer of size 784 (corresponds to the size of the inputs from the MNIST dataset), hidden layer with 1000 nodes and an ReLU activation function and an output layer with 10 nodes corresponding to the 10 MNIST classes. As training loss the cross-entropy between the model's s output and the one-hot encoding of the classes. We consider two different constructions of the data streams that are respectively presented in Section K.] and Section K.2 For both settings the parameters used for the various methods are presented in [ We also remark that the parameters of CSVRG, SGD were appropriately selected so to perform roughly the same number of FOs.
Method SGD
MNIST
step size: 0.001
T: 1385
SVRG
step size: 0.05
Outer Iterations: 7
Inner Iterations:
CSVRG
step size at i: 0.001 T. 600
0.01
Table 6: Parameters used for training of the neural network.
K.1 DATA STREAMS PRODUCED WITH THE STATIONARY DISTRIBUTION
In this experiment we create stream of 3000 data points where the data-point at iteration were sampled uniformly random (without replacement) from the MNIST dataset. Table iilusttatsss the training loss of each different method across the different stages, As Table reveals that in the early stages all methods achieve training loss close to by overfitting the model while in the latter stages CSVRG and SVRG are able to achieve much smaller loss in comparison to SGD. We remark that CSVRG is able meet the latter goal with way fewer FO calls than SVRG as demonstrated in Table 7
NNIST
NNIST
CVR
30
2/R0
000.7
00125
00375
03-
00325
1968
Table Training loss the stages progress on neural network training for the MNIST dataset for the setting of sampling without replacement.
K.2 DATA STREAMS WITH ASCENDING LABELS
Motivated by continual learning at which new tasks appear in streaming fashion, we experiment with sequence of MNIST data points which new digits gradually appear. More precisely, construct the stream of data points as follows:
1. For each of the classes E (0,9), randomly sample 300 data points.
34

---

Published as a conference paper at ICLR 2024
2. For the first 600 stages randomly mix 0/1 data points.
3. The stages {601 + (a 2) 300, 600 + (i - 1) 300) for i E {2,9} contain the data points category i (e.g. category appears in stages {601, 900)).
Table 8 iillustrates the training loss of CSVRG and SGD for the various stages of the above data-stream. As Table [ reveals, CSVRG is able to achieve significantly smaller loss than SGD with the same number of FOs. We also remark that that the bumps appearing in bot curves corresponds to the stages at which a new digit is introduced.
MNINT
C3PR0
00173
00153
04322
0.000
01605
01000
Table The training loss of CSVRG and SGD for the various stages.
In Table we present the classification accuracy of the models respectively produced by CSVRG and SGD for the various stages. At each stage we present the accuracy of the produced model according to the categories revealed so far. The sudden drops in the accuracy occur again at the stages where new digits are introduced. For example iteration 601, the accuracy drops from roughly roughly 0.667 due to the fact in stage 600 the accuracy is measured with respect to the 0/1 classification task while in stage 601 the accuracy is measured with respect to the 0/1/2 classification task. At stage 601 both models misclassifies all the 2 examples and thus the accuracy drops to 2/3. In the left plot, we plot the classification accuracy with respect to the data used in the training set while the right one we plot the classification accuracy unseen test data. Both plots reveal that CSVRG admits noticable advantage of SGD.
WNIST
MNIST
1.0
M
10-
CoUnS
500
D3
038
0.
0.5
CSRG
M02
500
3000
2000
2502
2000
502
3000
3900
2000
2500
3020
Skege
Stage
Table 9: Classification accuracy. For the train set the left and the test set the right. As comparison between the two algorithms.
35


Reviews:
[{"review_id": "qtbBtNJgaf", "reviewer": "Reviewer_jqUd", "summary": "The paper studies the following problem: given $n$ functions, the goal is to find $n$ points such that the $i$-th point minimizes the average of the first $i$ functions. For this problem, the paper presents a lower bound on the number of iterations for a certain class of algorithms, called natural first-order methods. They present an algorithm that achieves first-order oracle complexity which is close to the lower bound.", "questions": "Minor issues:\n\n-- Commas are missing in many places\n\n-- You mention $O(n \\log \\frac{1}{\\epsilon})$ complexity for VR methods, but isn’t the same bound achievable by trivial deterministic gradient descent, by sampling all $n$ functions at every iteration?\n\n-- Page 2: “for Problem 1 using $O(1/\\epsilon)$.” - “FOs” is missing.", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "A clearly written paper with sound results.", "weaknesses": "I have the following concerns about the paper:\n\n-- I can’t connect Problem 2 with its motivation. For example, you say that “it is important that a model is constantly updated so as to perform equally well both on the past and the new data”, but:\n1) Problem 1 achieves precisely that;\n2) in Problem 2, you train *multiple* models, with later models performing well on all data, and with older models not taking into account new data at all.\n\nTo conclude, I don’t see a motivation for the problem.\n\n-- You give lower bounds only for natural algorithms. If you don’t restrict yourself to natural algorithms (and it’s not clear to me why you consider only natural algorithms), I believe that $O(\\frac{\\log n}{\\epsilon})$ bound is possible, which outperforms all suggested methods. The idea is to run the following simple algorithm:\n\nfind $\\epsilon$-minimizer $x_n$ of $g_n$ using SGD\nfor i = n-1, n-2, …, 1:\n\tstarting from $x_{i+1}$, find $\\epsilon$-minimizer $x_i$ of $g_i$ using SGD\n\nI didn’t check the math in detail, but I believe that the proof goes like this:\n1) If $x_{i+1}$ is $\\epsilon$-minimizer of $g_{i+1}$, then $x_{i+1}$ is $(1 + 1/i) \\epsilon$-minimizer of $g_i$.\n2) The number of iterations required to find $x_i$ starting from $x_{i+1}$ is $O(\\frac{\\log (1 + 1/i)}{\\epsilon})$\n3) Summing this over all $i$, we get $O(\\frac{\\log n}{\\epsilon})$ iterations\n\n-- Experiments are only conducted in simple regression settings. Dataset statistics (e.g. the number of points) are not shown. It is unclear how exactly you execute the baselines.", "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": "uiRMiCn04B", "reviewer": "Reviewer_s2LS", "summary": "The paper introduces the following natural problem: given a sequence of n convex functions. Find a sequence of inputs that minimizes the partial sum of the functions. Standard methods such as SGD require $O(n/\\epsilon)$ first order gradient information about the functions to get error up to additive $\\epsilon$. That paper introduces a novel algorithm which obtains the same accuracy using substantially fewer number of first order gradient information. In particular, the new algorithm only requires $O(n/\\epsilon^{1/3})$  gradient calls. For small $\\epsilon$, this is a big improvement. For instance, the authors note that $\\epsilon=1/n$ and is a very common setting, in which case their algorithm gives a polynomial improvement. The authors also introduce the notion of a 'natural algorithm' and prove a lower bound of $\\Omega(n/\\epsilon^{1/4})$ gradient calls under the assumption.", "questions": "Please see above.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The introduction of the problem is a nice conceptual contribution. The new algorithm they proposed could also have other applications. In the notion of a \"natural algorithm\" is a nice contribution since it allows the analysis of algorithms and lower bounds.", "weaknesses": "A weakness is the lack of intuition about their algorithm. I mostly follow the math, however conceptually I do not know why exactly they can get an improvement in the epsilon power. It seems like the high level idea is only to compute a gradient update if we have not had an update for a long time. \n\nEstablishing that the gradient is unbiased seems fairly straightforward: it just uses the fact that the gradient at the next step is a linear combination of the new function and the previous gradient. Analyzing the variance seems like some technical work. However I did not understand the conceptual improvement. \n\nCan the authors comment more about the intuition of their algorithm?\n\nAnother weakness is the experimental setting. In the experiments, the authors analyze a version of ridge regression. They divide by $i$ for every step which seems a bit unnatural to me. It would make more sense if the $i$ term was not there. But in that case, the problem becomes very easy. By using standard rank one update formulas, the *exact* optimum can be found in $O(nd^2)$ time. Perhaps the authors divided by $i$ to make the problem `artificially' harder? In any case, testing the algorithm on other natural problems which cannot be solved by other methods would be more convincing. The authors also do not list the parameters of the dataset and the $\\epsilon$ used in the algorithm.", "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": "6ZqAg4d0yk", "reviewer": "Reviewer_zvPG", "summary": "This paper studies a new problem of efficient instance-optimal finite-sum minimization, where given a sequence of functions, the goal is to find a sequence of points $x_1^\\star, \\ldots, x_n^\\star $ such that for each $i \\in [n]$, point $x_i^\\star$ approximately minimizes $\\sum_{j=1}^{i} f_j(x) / i $, with the number of first-order oracle(FO) calls as least as possible. Given the condition that each function $f_j(\\cdot)$ is strongly convex, the proposed method SIOPT-Grad produces an $\\epsilon$-optimal sequence within $\\tilde{O}(n/ \\epsilon^{1/3} + 1/\\sqrt{\\epsilon})$ FOs. In addition, they prove a lower bound that, there is no \\emph{natural} FO methods that completes this task within $O(n/\\epsilon^{1/4}) queries.\n\nIn the regime motivated by the empirical risk minimization in the strongly convex case where statistical error is $\\epsilon = O(1/n)$,  SIOPT-Grad requires only $O(n^{4/3})$ FOs compared to all previous FO solutions.", "questions": "- The solution proposed in this paper, although is better in the number of FOs, may result in much added overall running time. Is there any practical regime where the number of FOs is expensive, compared to the efficiency of the algorithm measured by the running time?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The studied problem is well-motivated, both from the literature review on incremental learning, and from empirical estimation.\n- The theoretical analysis is complete, an upper bound and lower bound is provided for this problem, as well as compared to state of the art as in table 1.\n- The logic of this paper is easy to follow, and the assumptions/notations are presented in a clear way.\n- The paper has additional experiments on the ridge regression problem.", "weaknesses": "- The upper bound provided by the algorithm is not tight compared to the lower bound. \n- The algorithm only work in the strongly convex case. \n\nMinor Issue:\n- there is no input in the algorithm 2.\n- the value of $\\alpha$ needs to be in line 2 of algorithm 1. \n- additional \"the\" in the second line of the first paragraph of section 3.1\n- the VR is never defined. suggestion: \"variance reduction(VR)\" and then use VR afterwards", "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": "lwVk21rdtI", "reviewer": "Reviewer_FDce", "summary": "This paper considers the instance-optimal finite-sum minimization problem, where the setting is we have a sequence of functions $f_1, \\cdots, f_n$, and we need to output a sequence of points $x_1^*, \\cdots, x_n^*$, with $x_i^*$ being the minimizer of $\\sum_{j=1}^i f_j(x)/i$. This problem is inline with the modern machine learning setting as usually the training set is went through for only once, but we hope to make sure the current solution is the optimal for the current situation. \n\nFor this setting, the existing SGD or variance reduced methods are not optimal, because naively we need to call these methods $n$ times in order to find these $n$ minimizers. This paper proposed a new algorithm which finds the minimizer iteratively, which incurs $\\tilde{O}(n/\\epsilon^{1/3} + \\log n /\\sqrt{\\epsilon})$ FO complexity. The authors also show that the lower bound of this problem is $\\tilde{O}(n/\\epsilon^{1/4})$, which means the newly proposed algorithm is close to optimal.", "questions": "I do not have additional questions. I have went through the proofs in the main paper, and they look correct to me. However, I did not get time to verify the long proofs in the appendix.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "Originality: the setting is interesting, and the proposed algorithm is novel as far as I know. In their algorithm, they propose to switch between compute full gradient with $i$ FOs and compute a simple modification based on the previous gradient with 1 FO for full gradient estimation, which is a special trick. \n\nQuality: The results are nice, because the authors not only provide the convergence guarantees, but also compare it with the existing methods, and provide a very close lower bound. \n\nClarity: The overall writing of this paper is excellent. \n\nSignificance: I think the results are interesting, because this setting is an important setting to explore, and they have presented a full story about this setting.", "weaknesses": "I guess the main weakness of this paper is about the strong convexity assumption of f. This is kind of old-school assumption, because nowadays we always use deep neural networks to fit the data, and these models are almost never strongly convex.  In fact, as far as I know, variance reduced techniques are not so useful for neural networks, so I am afraid that the proposed method are not very practical for real world models.", "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)