Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization
Authors: Ali Kavis
EFSTRATIOS PANTELEIMON SKOULAKIS
Kimon Antonakopoulos
Leello Tadesse Dadi
Volkan Cevher
Venue: NeurIPS 2022 Accept (2022)
Keywords: nonconvex optimization
variance reduction
finite-sum minimization
adaptive methods

Abstract: We propose an adaptive variance-reduction method, called AdaSpider, for minimization of $L$-smooth, non-convex functions with a finite-sum structure. In essence, AdaSpider combines an AdaGrad-inspired (Duchi et al., 2011), but a fairly distinct, adaptive step-size schedule with the recursive \textit{stochastic path integrated estimator} proposed in (Fang et al., 2018). To our knowledge, AdaSpider is the first parameter-free non-convex variance-reduction method in the sense that it does not require the knowledge of problem-dependent parameters, such as smoothness constant $L$, target accuracy $\epsilon$ or any bound on gradient norms. In doing so, we are able to compute an $\epsilon$-stationary point with $\tilde{O}\left(n + \sqrt{n}/\epsilon^2\right)$ oracle-calls, which matches the respective lower bound up to logarithmic factors.

Adaptive Stochastic Variance Reduction for Non-convex Finite-Sum Minimization
Ali Kavis* LIONS, EPFL
Stratis Skoulakis' LIONS, EPFL
ali www.kkvisslll..ccm
efstratios www.lakisksppll.ccmmmm
Kimon Antonakopoulos
Leello Tadesse Dadi
LIONS, EPFL
LIONS, EPFL
kimon awooo.anttonkcooulss@epll....
leello. deello.dadi@epff medi@eppl..cc ch
Volkan Cevher
LIONS, EPFL
volkan.. cewher@epfl.ch
Abstract
We propose adaptive variance-reduction method, called ADASPIDER. for mini- mization of L-smooth, non-convex functions with finite-sum structure. In essence, ADASPIDER combines an ADAGRAD-insping [16, 40], but a fairly distinct, adap- tive step-size schedule with the recursive stochastic path integrated estimator proposed in Fang et al. [19]. To our knowledge, ADASPIDER is the first parameter- free non-convex variance-reduuction method in the sense that it does require the knowledge of groblem-dependen parameters, such as smoothness constant L, target accuracy 6 or any bound on gradient norms. doing so, we are able compute an e-stationary point with Ô (n + v oracle-calls, which matches the respective lower bound up to logarithmic factors.
Introduction
This paper studies smooth, non-convex minimization problems with the following finite-sum structure:
2
min f(x) = Σ f((x). wER'
(Prob)
where each component function Rd R is L-smooth and is possibly non-convex, and further assume f is also non-convex. We seek to find an e-approximate first-order stationary point & of f. such that [+]( < e, where is the accuracy of the desired solution.
This structure captures many interesting learning problems from empirical risk minimization to training of neural networks. First-order methods have been the standard choice for solving (Prob), due to their efficiency and favorable practical behavior. In that regard, while gradient descent (GD) requires Onn/²² gradient computations, stochastic gradient descent (SGD) requires O(1/et) overall gradient computations. In many interesting machine learning applications n tends to be large, e.g.. training neural network for image classification with very big image datasets [14], hence SGD typically leads to better practical performance.
Joint first authors
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

To leverage the best of both regimes, GD and SGD, the so-called variance reduction (VR) framework combines the faster convergence rate of GD with the low per-iteration complexity of SGD. Originally proposed for solving strongly-conva problems [24, 13, 42], variance reduction frameworks essen- tially generate low-variance gradient estimates by maintaining a balance hetween periodic full gradient computations and stochastic mnini-batch) gradients. VR methods and their theoretical behavior for convex problems have been well-studied under various problem setups and assumptions, including j--tronglyy convex functions with On + (L/u) log(1/e)) complexity [24, 42, 13]; j-sttrongly con- vex functions with accelerated O(n + /T/pllo(( /e)) complexity [2, 29, 47] and smooth, convex functions with Ö(n + 1/c) complexity [58, 47, 15]. For non-convex minimization, earlier attempts ex- tended the existing VR frameworks, achieving the first rates of order Onn+n2/3/e" with sub-optimal dependence on n [45, 55, 353. The most recent non-convex VR methods [18, 51, 36, 44, 37] close this gap and achieve the optimal gradient oracle complexity of O(n + vn/ee) [18].
Adaptivity and First-order Optimization
The selection of the step-size is of great importance in both the theoretical and practical performance of first-order methods, including the aforementioned VR methods. In the case of L-smooth minimization, first-order methods need the knowledge of L as to adequately select their step-size [41], otherwise the method is not guaranteed to be convergent and might even diverge [15, 38]. To elucidate, classical analysis relies on the (expected) descent property and guarantees that the algorithm monotonically makes progress every iteration. To enforce this property everywhere on the optimization landscape, one needs to pick the step-size as "t S O(1/L) L), which restricts the step length of the algorithm with respect to the worst-case constant T.. On the other hand, estimating the smoothness constant for an objective of interest, such as neural networks, is very hard task [21]. At the same time, using crude bounds on the smoothness constant leads to very small step-sizes and consequently to poorer convergence. In practice the step-size is tuned through an empirical search over a range of hand-picked values that adds a considerable computational overhead and burden. In order to alleviate the burden of tuning process, we need step-sizes that adjust in accordance with the optimization path.
A popular line of research studies first-order methods that adaptively select their step-size by taking advantage of the previously produced point. In many settings of interest, these adaptive methods are able to guarantee optimal convergence rates without requiring the knowledge of the smoothness constant I. while they often admit superior empirical performance due to their ability to decrease the step-size according to the local geometry of the objective function. Inspired by AdaGrad introduced in the concurrent seminal works of [16] [39], a recent line of works [31, 26, 25, 17] propose adaptive achieve accelerated rates in the
gradient methods that given access to noiseless gradiemt-estimane
case of L-smooth convex minimization without requiring the knowledge of smoothness constant L. Similarly, Ene et al. [17] and Antonakopoulos et al. [5] propose adaptive methods with optimal convergence rates for monotone variational inequalities while Antonakopoulos et al. [6] provide adaptive methods for monotone variational inequalities assuming access to relative noise gradient- estimates. Hsieh et al. [23] and Vu al. [50] study the convergence properties of adaptive first-order methods for routing and generic games.
Adaptive non-convex methods for General Noise Related to work is recent line of papers studying adaptive first-order methods under the general noise model. In this setting, a method is assumed to access unbiased stochastic estimate of the gradient with bounded variance. This is more general setting than finite-sum optimization that comes with worse lower bounds, i.e. 2(1 gradient -ettient-sstimates are needed so as to compute an e-stationary point. A recent line of works study adaptive first-order methods that are able to achieve near-optimal oracle-complexin while being oblivious to the smoothness constant L and the variance of the estimator [52, 20, 34, 27]. For example Ward et al. [52] established that the adaptive method called AdaGrad- is able to achieve O(1/ct) gradient-compe complexity in the general noise model. In their recent work, Faw et al. [20] significantly extended the results of Ward al. [52] by showing that AdaGrad- -orm achieves the same rates even in case the gradient admits unbounded norm (a restrictive assumption in [52]) while their result persists even if the variance increases with the gradient norm. the slightly more restrictive setting at which the objective function f(x)= == PE. {) where each estimate g(x, {) T-smooth with respect to x for all ç, Levy al. [32] proposed an adaptive method called STORM++ that achieves O(1/e)) groplext-complxxity and that removes the requirement of the knowledge on
We remark that in the case of finite-sum minimization there exist variance reduction methods with O(z + vn/e²) gradient complexity [19, 51].
2

---

Table 1: In the following table present the gradient computation complexity of the existing non-adaptive and adaptive variance reduction methods for both convex and non-convex finite-sum minimization. Since for there are multiple non-adaptive VR methods, we present the carliest-roppose method matching up to logarithmic factors the respective lower bounds.
f(z)
Non-Adaptive VR
Adaptive VR Complexity Lower Bound
convex
0 (n + +
On+ +
M(n +
(e-opl, solution)
[28]
[38]
[53]
convex
0 (n 0n++? :)
0 (n + :)
Q(n + V
(e-opt, solution)
[57]
[15]
[53]
non-convex
0
n [19]
vn
e²
Ó On+ [n++
vn
2
Ω
n + 62
(e-stal. point)
This work
[19]
problem parameters (e.g., smoothness constant, absolute bounds on gradient norms) that the original STORM method proposed by Cutkosky al. [12] requires. The latter meadient-compexxin matches the 22(1/e)) lower bound of Arjevani et al. [7].
Adaptivity and Finite-Sum minimization
In parallel with what we discussed earlier, existing pariance-reductto methods (VR) crucially need to know the smoothness constant L to select their step-size appropriately to guarantee their convergence. To this end, the following natural question arises
Can we design adaptive VR methods thut achieve the optimal gradient computation complexity?
Li et al. [33] and Tan al. [49] were the first to propose adaptive ceduutoe-reduction methods by using the Marzilai-Borwerr step-size [8]. Despite their promising empirical performance, these methods do not admit formal convergence guarantees. When the objective function f in (Prob) is convex, [15] recently proposed an adaptive VR method requiring O(n + 1/e) gradient computation while, shortly after, [38] proposed an accelerated adaptive VR method requiring O(n + vni Vt) gradient computations.
To the best of our knowledge. there is no adaptive VR method in the case where f is non-convex. We remark that f being non-convex captures the most interesting settings such as minimizing the empirical loss of deep neural network where each f; stands for the loss with respect to i-th data point and thus is non-convex function in the parameters of the neural architecture. Through this particular example, we could motivate adaptive VR methods two fronts: first, even estimating the smoothness constant L of a deep neural network is prohibitive [21], and at the same time, the parameter in (Prob) equals the number of data samples, which can be very large in practice and is prohibitive for the use of deterministic methods.
Contribution and Techniques In this work we present an adaptive VR method, called ADASPIDER, that converges to an e-stationary point for (Prob) by using Ö(n + /nl2/e²) gradient computations. Our gradient complexity bound matches the existing lower bounds up to logarithmic factors [19].
ADASPIDER combines an adaptive step-size schedule in the lines proposed by ADAGRAD [16] with the variance-reduction mechanism based on the stochastic path integrated differential estimator of the SPIDER algorithm [19]. More precisely, ADASPIDER selects the step-size by aggregating the norm of its recursive estimator, while following single-loop structure as in Fang et al. [19].
Our contributions and techniques can be summarized as follows:
To our knowledge, ADASPIDER is the first parameter-ine method in the sense that it is both accuracy-nndependent and is oblivious the knowledge of any problem parameters including L. Moreover, c-independence enables us to provide any-iterate guarantees. While SPIDER needs both and L to set its step-size min( /.d| 1 /./.. to achieve optimal
gradient complexity [19], all other existing non-convex methods must know at least the value of L in order to guarantec convergence [4, 51].
3

---

-1/2
where V. is the recursive variance-reduced estimator at round By identifying unique addi- tive/multiplicatiie form for integrating n, we manage to achieve optimal dependence on the number of components. We note that Adaspider can be viewed as SPIDER with the step-size of AdaGrad-Norm [20, 52, 48, 43] were the parameters are respectively selected as 77 = n 1/4 and bj == v [20].
We introduce novel step-size schedule "/ n-1
(v V.11²)
We show how to combine the above adaptive step-size schedule with the recursive SPIDER estimator in order ensure that the average variance + E Il V decays
a rate Ô (n 1///4//2 (n!/A/VT). techniques.
This might of independent interest for other variance reduction
We follow a novel technical path that uses the adaptivity of the step-size to bound the overall variance of the process. This fact differentiates approach from the previous adaptive and non adaptive VR approaches (see Section 4 for further details) and provides us a surprisingly concise analysis. Remark 1.
Our convergence results do not require bounded gradients that is typically a restrictive assumption that the analysis of the adaptive methods for stochastic optimization require. We overcome this obstacle by using the fact | -t-1l| S (due to the step-size selection) and thus | (xzz (1 < L Ft-1l S T.. The latter leads the following upper bound on the gradient norm, [V+)) & LT + [(x))l that however leads to only a logarithmic overhead in the final bound (see Lemma 2). A similar idea is used by Faw al. [20] (Lemma 2) in order to remove the bounded gradient assumption on the convergence rates of AdaGrad-None under general noise.
Setup and Preliminaries
During the whole of this manuscript, we consider that the non-convex objective function f R2d IR possesses a finite-sum structure
f(x) Σ f((
where each component function f; is L-smooth (or alternatively has L-Lipschitz gradient) and (possibly) non-convex. To quantify the performance of our algorithm within the context of non- convex minimization, we want to find an e-first order stationary point & E IRd such that
[V <.
For notational simplicity we define ||:|| as the Euclidean norm. Then, we say that a continuously differentiable function f is L-smooth if
[V - - V s L||x yll,
(2.1)
which admits the following equivalent form,
f(x) - f(v) ff()) +)+ 1 y/1 for all x. e IR..
(2.2)
Observe that smoothness of each component immediately suggests that objective f is L-smooth itself. Since we are studying randomized algorithms for finite-sum minimization problems, we do not consider any variance bounds on the gradients of components. We only assume that we have access to an oracle which returns the gradient of individual components when queried.
3 Adaptive SPIDER algorithm and convergence results
In this section, we present our adaptive variance reduction method, called AdASpider (Algorithm 1) which exploits the variance reduction properties of the stochastic path integrated differential estimator proposed [19] while combining with an AdaGrad-type step-size construction [16]. Unlike the original SPIDER method [19]. our algorithm admits anytime guarantees, i.e., we don't 't need to specify the accuracy e a priori. Additionally, our algorithm does not need to know the smoothness parameter L and guarantees convergence without any tuning procedure.

---

Algorithm Adaptive SPIDER (ADASPIDER)
Input: zo E R ,b > 0, Gb
1: G 2--0
2: for = - do
3: if' mod n = 0 then
4: V Vz(z))
5: else
6:
pick & E (1,...,m) m) uniformly at random
7:
V. - Vfi, - (z + V
8:
end if
Tt 1/ n//4 Boy n1/20g E.=oll
9:
10: Ee+1 f 2t Y:- V
end for
12:
return uniformly at random fao....,2r-11 2r-1).
Remark 2. In Algorithm I the units of Gu are the same with the units of V fxx) i.e. f/x while the units of 3o are x The latter is important so that the step-size 7 takes the right units i.e. x² o²/f.
As Algorithm indicates, ADASPIDER performs a full-gradient computation every n iterations while in the rest iterations updates the variance-reduced gradient estimator in a recursive manner, V, 4 Vi, (ar) - fi, (x+-1) V,-1- The adaptive nature of ADASPIDER comes from the selection of the step-size at Step 9 that only depends on the norms of estimates produced by the algorithm in the previous steps.
Before presenting the formal convergence guarantees of ADASPIDER (stated in Theorem 1), we present the cornerstone idea behind its design and motivate the analysis for controlling the overall variance of the process through the adaptivity of the step-size. This conceptual novelty differentiates our work form the previous adaptive VR methods [15, 38] at which the adaptivity of the step-size only used for adapting to the smoothness constant I,, and their constructions come with additional challenges in bounding the variance. As result, the following challenge is the first to be tackled by the design of VR method.
Challenge 1. Does the average variance of the estimator, + E ((()))) diminishes sufficiently fast rate?
Up next we explain why combining the variance-redducioo estimator of Step 7 with the adaptive step-size of Step provides a surprisingly concise answer to Challenge 1. We remark that SPIDER is able to control the variance at any iterations by choosing % min( LvwIiv 2/nz) ) step- size. The latter enforces the method to make tiny steps, ||æ; - xt-1ll S e/Lyn which results in e-bounded variance any iteration. The latter proposed SPIDERBOOST [51] provides the same gradient-comleextty bounds with SPIDER but through the accuracy- inneeeedeed step-size 1/L. SPIDER BoOST handles Challenge by using dense gradient-computann with amortization arguments based on the descent inequality (this is why the knowledge of L is necessary in its analysis). We remark that ADASPIDER, despite being oblivious to and accuracy c, admits significantly simpler analysis by exploiting the adaptability of its step-size.
schedule' combined
In the rest of the section present our approach Challenge and conclude the section with Theorem stating the formal convergence guarantees ADASPIDER.
Handling the variance with adaptive step-size We start with the following variance aggregation lemma that is folklore in (VR) literature (c.g. [56]).
Lemma 1. Define the gradient estimator at point x as V = f.((x) Vf(()) + V where i is sampled uniformly random from {1....,.,) n.). Then,
E [IV,
[] < I. 1 - 2 [
AADSSPDERR computes full gradient every /n steps and the intermediate steps uses batches of size Vn.
5

---

Now, let us apply Lemma on SPIDER estimator, V. = (x) (x)+ V to measure its variance at step z+--
[IV, - vf(x))
- L || - 2t
-z- [| t- - v
- E' [ (
+ [ vf(2==1)11)
L L [h-1 1
+ +... +...+ E V (- mod a) V fx+ mod n ]
Σ
LAB 1
-1 mod n)+1
where the last equality follows by the fact E v_ mod Vf(r, (t mod n )
since
Algorithm 1 performs a full- full-gradient computations for every t with mod = (Step 3 of
Algorithm 1). By telescoping the summation we get,
Σ E | V
Σ
L'E b2 VV+11 S L'n
E hh
[
1=0 7t med m)+1
t=
where the n factor on the right-hand side is due to the fact that each term E most n times in the total summation. To this end, using the structure of the stochastic path integrated differential estimator have been able to bound the overall variance of the process as follows,
V appears at
T-1 - L
T-1
L'n
Σ B
|V.11
However it is not clear at all why the above bound is helpful. At this point the adaptive selection of the step-size (Step in Algorithm 1) comes into play by providing the following surprisingly simple answer,
T-11
Σ [ V
& I E
Σ
2
|
1=0
L B
V V. Vn+ V...//
L %
log
1 E
V
c
t=
where the last inequality comes from Lemma 7. To finalize the bound, require the following expression that follows by the fact that 7 I V/ll and thus || - r1-1ll $ 1.
Lemma 2.
Let To, .1, the points produced by Algorithm Then,
T-1
Σ
1.1 <0 nT
L B
++V[(20)))
In simple terms, Lemma 2 helps avoid the bounded gradient norm assumption that is common among adaptive non-convex methods. As a result, ADASPIDER admits the following cumulative variance bound,
LLVV ( log 1 IT BB
(LL BoGo
L. + [V Go
Σ [IIV. V s SoC
(3.1)
Remark To this end one might notice that using a more aggressive dependence on % leads to smaller variance of the estimator which is obviously favorable. However more aggressive dependence on leads to smaller step-sizes and thus to sub-optimal overall gradient-computatee complexity. In Section 4, we explain why the optimal way to inject the dependence into the step-size is through the simultaneous multiplicative/addiive way described Step of ADA that may seem unintuitive the first sight.

---

We will conclude this discussion with complementary remark on the interplay between our adaptive step-size and the convergence rate, As we demonstrated in Eq. (3.1), using a data- adda-ide step-size leads to a decreasing variance bound in an amorlized sense as opposed to any iterate variance bound of SPIDER. The trade-off in our favor is the parameter-free step-size that is independent of e and For a fair exposition of our results, notice that the aforementioned advantages of an adaptive step-size comes at an additional (o'( term in our final bound due to Eq. (3.1). This has a negligible effect on the convergence as even in the large iteration regime when T is in the order billions, it amounts to a small constant factor.
We conclude the section with Theorem I that formally establishes the convergence rate of ADASPI- DER. The proof of Theorem is deferred for the next section.
Theorem 1. Let Tu, ....... TT--1 be the sequence of points produced by Algorithm I in case f()) is L-smooth. Let us also define Do == f(zo) - -f. Then,
T-1 Σ
SO 1/4 θ EIIVS
log (1+
330G (3555) + [V
L
E
T
VT
Go
1=0
where Do. Bo + Go + L/30-
+ L' (3) Overall, Algorithm I with Po == and Go
needs at most Ô (n+ Vn. + oracle calls reach an e-stationary point.
4 Sketch of Proof of Theorem
In this section we present the key steps for proving Theorem We first use the triangle inequality to derive,
T-1
T-1
T-1
Σ
EEITS
Vs( -
Σ
BII
1=
t=
t=
We have previously discussed how to bound the first term in Section 3. More precisely, by the Jensen's 's inequality and the arguments presented in Section 3, we obtain the following variance bound.
Lemma 3. Let To, ..., Fr the sequence of points produced by Algorithm 1. Then,
E [ [(()))]] so (Lm///
V V1og
1 (I+nT
(
L
(Bo
Go
We continue with presenting how to treat the term 11=0 [.ll By the smoothness of the function and through telescopic summation one can easily establish the following bound,
T Σ T |V.11
T-1
T-1
E
L
L.
E
Σ
1I.
+E
Σ Th [V V..1
1=
As we explained in Section 3, the term IE
can be upper bounded by the adapt- ability of the step-size ?t. At the same time, using the adaptability of " we are able establish that Ii E [[]v is most 1/44 VT. E EE= 7 || All the above are formally stated and established in Lemma 4 the proof of which is deferred to the appendix.
E 7 12
Lemma 4. Let To. TT-1 the sequence of points produced by Algorithm 1 and Do
fx0) f Then,
1 2ō
E
Σ
+E CrIlV(())) - -viI) I (o Bo Go + Bo
1=0
Due to the of the adaptive step-size "/t the estimator's error and the step-size itself are dependent random variables, meaning that the weighted variance term E E 7 (z))) v. cannot
be handled by Lemma To overcome the latter, we use the monotonic behavior of the step-size 7 to establish the following refinement of Lemma 1.
7

---

Lemma 5. Let To, f1.... the sequence of points produced by Algorithm 1. Then,
T- Σ
n 1.. 1o.lIl.VVyee Vf(x))1 VV-IVVe-V(xil11 LLn
V.
To this end we are ready to summarize the importance of simultaneous additive/muliplicatiee dependence of y in Step of Algorithm 1. This selection permits us to do achieve two orthogonal goals the same time,
Bounding the variance of the process, E - IV, - v((+))]] Section and Lemma 3).
< <0 =n(1/AVT) (see
Bounding the sum, E Ef Vell zō <O(n and Lemma 5).
EL 7 (()))l)) (see Lemma
The third important thing that the selection of 7 does that it permits us to upper bound the term Ö 5/4 E Ei= y v. by Ô (n) The proof of the latter upper bound can be found in the proof of Theorem that due to lack of space is deferred to appendix. is interesting that all the above three different purposes can be handled by selecting = n 1/41/// 1 Bol GB + E' V 1
5 Experiments
We complement our theoretical findings with an evaluation of the numerical performance of the algo- rithm under different experimental setups. We aim highlight the sample complexity improvements over simple stochastic methods, while displaying the advantages of adaptive step-size strategies. For that purpose design two setups; first, consider the minimization of convex loss with non-convex regularizer in the sense of Wang et al. [51] and in second part we consider an image classification task with neural networks.
5.1 Convex loss with a non-convex regularizer
We consider the following problem: min 1 - E(x, (a,, + Ag(x)) where f(x, (a, b.)) is the loss with respect to the decision variable/weights x with (a,, by) denoting the (feature vector, label)
pair. We select Di= I- similar Wang et [51]. where the subscript denotes the corre- sponding dimension of x. We compare ADASPIDER against the original SPIDER, SPIDERBOOST. SVRG, ADASvRG and two non- VR methods, SGD and ADAGRAD. We picked two datasets from LibSVM, namely ala, mushrooms. We initialize each algorithm from the same point and repeat the experiments times, then report the mean convergence with standard deviation as the shaded region around the mean curves. We tune the algorithms by executing parameter sweep for their initial step-size over an interval of values which are exponentially scaled as {10-3 10-2 ..... 102 103). After tuning the algorithms
dataset, run them with the same parameters for the others.

---

133
101
12-
16-4
12-16
563
18.40
AcoSoler
10:14
Ac4Saida
AcaGred
Acadeed
12
1P
17
10
20"
10 call
207
12
ende
(a) ala
mushrooms
127
10.
16-1
13:14
10-11
563
10
12:40
AcuSolder
Ac4Sanda
SURG
10-18
D/RS
10
Acoceod
10
10
.01
10
107
12r
1P
307
oracee
(c) a6a
(d) wla
10-4
16.5
12-
10-14
502
5G0
13-0
SURG
D/RS
AcaSVRic
Acasvit
13'
30'
stochasik
calls
wSa
(f) ionosphere-scale
Figure 1: Logistic regression with non-convex regularizer on LibSVM datasets
First, we clearly observe the difference between SGD & ADAGRAD, and the rest of the pack, which demonstrates the superior sample complexity of VR methods in general. Among VR algorithms, there does not seem to be any concrete differences with similar convergence, except for SPIDER. The performance of ADASPIDER is on par with other VR methods, and superior to SPIDER. The unexpected behavior of SPIDER algorithm has previously been documented in Wang et al. [S1]. From technical point of view, this behavior is predominantly due to the accuracy dependence in the step-size, making the step-size unusually small. We had to run SPIDER beyond its prescribed setting and tune the size-size with large initial value to make sure the algorithm makes observable progress.
5.2 Experiments with neural networks
In our second setup, we train neural networks with our variance reduction scheme. Our fo- cus is standard image classification tasks trained with the cross entropy loss [9, 10]. De- noting by C' the number of classes, the considered datasets in this section consist of n pairs (a,, b.) where a, is vectorized image and b, BC is one-hot encoded class label. A neu- ral network is parameterized with weights E Rd and its output is denoted net(x. a) E RC,

---

Advina v0p
124
To Serfood
384
dochackc cracle cs
stchackl cracle ca
MNIST
(b) Fashi onMMIST
Figure 2: Gradient norms throughout the epochs for image classification with neural networks (curves
averaged over 5 independent runs and the shaded region are the standard error).
Table 2: Algorithm parameters and test accuracies (average of 5 runs, in %)
KNIST
FashionMMIST
Batch Size 32, Car
0.03
Batch Size 128, Got 0.01
Algorithm
Parameters
Accuracy
Parameters
Test Accuracy
AdaCrad [6]
0.01,
10
97.86
0.01.
10
86, 19
4G][46]
9 0.01
98.11
0.01
85.83
KatyushaXu
7 0.005
97.93
0.01
86.27
AdaSVRG| [5]
0.1
98.03
0.1
86.82
[9
0.01, L 100.0, de
97.53
0.01,
L 50.0,
no
82.22
Spider 42]
= 200
97.01
L 120
84.42
AdaSpider
n = 60000
97.49
60000
81.09
where is the input image. The training of the network consists of solving the following op-
timization problem: min 1 > (-b, net(xr a,) + Logsumexp(nett(z a.)).. This the de- fault setup for doing image classification and [30] and Fashi onMNIST[54]] We choose 3-layer fully connected network with dimensions [28 28, 512, 512, 10). The activation function is the ELU [11].
algorithm
benchmark datasets
The initialization of the network is crucial component to guarantee good perfor- mance. We find that a slight modification of the Kaiming Uni form initialization [22] improves the stability of the tested variance reduction schemes. For each layer in the network with din inputs, the original method initializes the weights with independent uniform random variables with variance a.,. Our modification initializes with a smaller variance of Gaa with Gnit in the order of 0.01. With this den
Initialization:
I.
choice, we observed that fewer variance reductions schemes diverged, and standard algorithms like SCD and AdaGrad(for which the original method was tuned), were not penalized and performed well. This often overlooked initialization heuristic the only "tning" needed for AdaSpider.
Observations: We observe (Figure 2) that AdaSpider performs well as other variance reduction methods in terms of minimizing the gradient norm. The key message here is that does so without the need for extensive tuning. This diminished need for tuning is welcome feature for deep learning optimization, but, often the true metric of interest is not the gradient norm, but the accuracy on unseen data, and on this metric variance reduction schemes are not yet competitive with simpler methods like SCD. With AdaSpides der, the focus can go to finding the right initialization scheme and architecture to ensure good generalization without being distracted by other parameters like the step- size choice.
Acknowledgments
This project has received funding from the European Research Council (ERC) under the European Union's 's Horizon 2020 research and innovation program (grant agreement n" 725594), the Swiss National Science Foundation (SNSF) under grant number 1000211205011 and Innosuisse.
10

---

References
[1] Zeyuan Allen-Zhu. Natasha: Faster non-convex stochastic optimization via strongly non-convex parameter, 2017. URL https:/ http:///aa.voo//oeeeeiiee org/ httg/bb//702... 00763..
[2] 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, STOC 2017, page 1200-1205. Association for Computing Machinery, 2017.
[3] Zeyuan Alle Katyusha X: Practical Momentum Method for Stochastic Sum-of-Nonconvex Opti- mization. In Proceedings of the 35th International Conference on Machine Learning, ICML '18, 2018. Full version available at http: / arxiv. caarii.og//..voooo org/ vrg//ba/// abs/1802. 03866.
[4] Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. Proceedings of the 33rd International Conference on International Conference on Machine Learning- Volume 48,
ICML' 16, page 699-707. Jog,.org, 2016.
[5] Kimon Antonakopoulos, Elena Veronica Belmega, and Panayotis Mertikopoulos. Adaptive extra- -atta-gradient methods for min-max optimization and games. In 9th International Conference on Learning Representa- tions. ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
[6] Kimon Antonakopoulos, Thomas Pethick, Ali Kavis, Panayotis Mertikopoulos, and Volkan Cevher. Sifting through the noise: Universal first order methods for stochastic variational inequalities. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors. Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 13099-13111, 2021.
[7] Yossi Arjevani. Yair Carmon, John C. Duchi, Dylan Foster, Nathan Srebro, and Blake E. Woodworth. Lower bounds for non-convex stochastic optimization. CoRR, abs/1912.02
2019.
[8] Jonathan Barzilai and Jonathan M. Borwein. Two-Point Step Size Gradient Methods. IMA Journal of Numerical Analysis, 8(1):141-44, 01 1988. ISSN 0272-4979. doi: 10. 10.30///mmm.m//.. 1.144. URL
//dos. woooorg///0 11/93//mmmmm.//// 8. 1.14
[9] John Bridle. Training stochastic model recognition algorithms networks lead to maximum mutual information estimation of parameters. Advances in neural information processing systems, 2. 1989.
[10] John S Bridle. Probabilistic interpretation feedforward classification network outputs, with relationships to statistical pattern recognition. In Neurocomputing, pages 227-236, Springer, 1990.
[11] Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network learning by exponential linear units (elus). In Yoshua Bengio and Yann LeCun, editors, 4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings, 2016. URL http: bttt:://axiiv org/ aaaaabb/1111 1/111112889
[12] Ashok Cutkosky and Francesco Orabona. convex sgd. In H. Wallach, H. Larochelle. A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL https: https://proceedingg. neurips. wwtpiipp.ccpppppe/000/ /2019/ff/////// htt.e/eeeeeee8811711111111866660
Momentum- based variance reduction in non-
[13] Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems, vol- ume 27. Curran Associates, Inc., 2014.
[14] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: A large-scale hierarchical image database. In 2009 IEEE Conference Computer Vision and Pattern Recognition, pages 248-255. 2009. doi: (0..0/CVVR.200005200000
[15] Benjamin Dubois -ainee Sharan Vaswani, Reza Babanezhad, Mark Schmidt, and Simon Lacoste- Julien.
SVRG meets adagrad: Painless variance reduction. CoRR, abs/2102.09645, 2021. URL https:/ //axxiv.
org/abs/211i 2bbb/210.09965. 09645.
[16] John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(u)):212122159, 2011.
[17] Alina Ene, Huy L. Nguyen, and Adrian Vladu. Adaptive gradient methods for constrained convex optimization and variational inequalities.
Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirty-Thrrd Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAl 2021, Virtual Event, February 2-9, 2021, pages 7314-7321. AAAI Press. 2021.
[18] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: near-optimal non-convex opti- mization via stochastic
differential estimator. 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 NewrIPS 2018, December 3-8, 2018, Montréal, Canada, pages 687-697, 2018
11

---

[19] Cong Fang. Chris Junchi Li, Zhouchen Lin, and Tong Zhang. Spider: Near-optimal non-convex opti- mization via stochastic path-integrated differential estimator. In S. Bengio. I. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advancess in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https: / htRthhtp://ppooeeee /ttp///eeoconnes/eeeeeeeeee///.e neurips. cc/ pc/pappr/2018/ file/ 1511144444432222aa55e 10weeaedd5355bbbbbe Paper pdf.
[20] Matthew Faw, Isidoros Tziotis, Constantine Caramanis, Aryan Mokhtari, Sanjay Shakkottai, and Rachel Ward. The power adaptivity in SGD: self-tuning step sizes with unhounded gradients and affine variance. In Po-Ling Loh and Maxim Raginsky, editors. Conference on Learning Theory, 2-5 July 2022, London, UK, volume 178 of Proceedings of Machine Learning Research, pages 313-355, PMLR, 2022.
[21] Fabian Latorre Gómez, Paul Rolland, and Volkan Cevher. Lipschitz constant estimation of neural networks via sparse polynomial optimization. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020.
[22] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. Proceedings of the IEEE international conference on computer vision, pages 1026-1034, 2015.
[23] Yu-Guan Hsich, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium. In Mikhail Belkin and Samory Kpotufe, editors, Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado. USA, volume 134 of Proceedings of Machine Learning Research, pages 2388-2422. PMLR, 2021.
[24] Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In Proceedings of the 26th International Conference on Neural Information Processing Systems- Volume 1. NIPS' 13, page 315-323, Curran Associates Inc., 2013.
[25] Pooria Joulani, Anant Raj. Andras Gyorgy, and Csaba Szepesvari. A simpler approach to accelerated optimization: iterative averaging meets optimism. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning. volume 119 of Proceedings of Machine Learning Research, pages 4984-4993. PMLR, 13-18 Jul 2020. URL https: // /ttpc/eeeeoeneeeeeee/eeeee/e/pee mlr. press/v119/ joul coulani20a. html.
[26] Ali Kavis, Kfir Y. Levy. Francis Bach, and Volkan Cevher. Unixgrad: A universal, adaptive algorithm with optimal guarantecs for constrained optimization. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32 pages 6260 6269, Curran Associates, Inc., 2019.
[27] Ali Kavis, Kfir Yehuda Levy, and Volkan Cevher. High probability bounds for a class of nonconvex algorithms with adagrad stepsize. CoRR, abs/2204.02833. 2022.
[28] Guanghui Lan, Zhize Li, and Yi Zhou. A unified variance-reduced accelcrated gradient method for convex optimization. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelzimer. Florence d' d'Alché-Buc Emily B. Fox, and Roman Gamett, editors, Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NewrIPS 2019, December 8- 14, 2019, Vancouver, BC, Canada, pages 10462-10472, 2019.
[29] Guanghui Lan, Zhize Li, and Yi Zhou. A unified mmriace-reduced accelerated gradient method for convex optimization, 2019.
[30] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient- based leamning applicd to document recognition. Proceedings of the IEEE, 86(1)) (1:2)))22-22222 1998. doi: 10. 1109/57266911
[31] Kfir Y Levy, Alp Yurtsever, and Volkan Cevher. Online adaptive methods, universality and acceleration. In Neural and Information Processing Systems (NeurIPS), December 2018.
[32] Klir Yehuda Levy, Ali Kavis, and Volkan Cevher. STORM+: Fully adaptive SGD with recursive momentum for nonconvex optimization. In A. Beygelzimer, Y. Dauphin, Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL httt:p::///pperee// net/forum? id=ytke6qkpxtx.
[33] Bingcong Li, Lingda Wang, and Georgios B. Giannakis. Almost tune-free variance reduction. In Hal Daumé III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 1969-5978. PMLR, 13 18 Jul 2020. URL httpp::/pprete //proceee/c./c/p...... mlr. www.t.rrsssiivv wttps//vvv11111111111 html.
[34] Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In Kamalika Chaudhuri and Masashi Sugiyama, editors, The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16-18 April 2019, Nahu, Okinawa, Japan, volume 89 of Proceedings of Machine Learning Research, pages 983-992. PMLR, 2019.
[35] Zhize Li and Jian Li. A simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS 18, page 5569 5579, Red Hook, NY, USA, 2018. Curran Associates Inc
12

---

[36] Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtarik. Page: A simple and optimal probabilistic gradient estimator for nonconvex optimization. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pages 6286-6294 PMLR, 18-24 Jul 2021. URL https:/ htappp://prooe /ttp:////ooednngeeee mir. press/v139/ 1121a.html.
[37] Zhize Li, Slavomír Hanzely, and Peter Richtárik. Zerosarah: Efficient nonconvex simite-sum optimization with zero full gradient computation, 2021. URL atttps://araiii . org aba//////2... 01447.
[38] Zijian Liu, Ta Duy Nguyen, Alina Enc, and Huy L. Nguyen, Adaptive accelerated (extra- (arra-)gradientt methods with variance reduction. CoRR, abs/2201. 12302, 2022. URL poctps://arxo org/ /a/aab/s//// /2t./221.1.... 12302.
[39] H Brendan McMahan and Matthew Streeter. Adaptive bound optimization for online convex optimization. COLT 2010. page 244, 2010.
[40] H. Brendan McMahan and Matthew J. Streeter. Adaptive bound optimization for online convex optimization. In Adam Tauman Kalai and Mchryar Mohri, editors, COLT 2010 The 23rd Conference on Learning Theory, Haifa, Israel, June 27-29, 2010, pages 244-256. Omnipress, 2010. URL http://colt2010 httppppppsssOOOO/ httppp/rs//0t2211ooooooooiieeee
haifa. 11.11...bbb
#pf
[41] Yurii Nesterov. Introductory lectures on convex optimization. 2004, 2003.
[42]
Lam M. Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. 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 on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 2613-2222222 2621. PMLR, 06 11 Aug 2017.
[43] Francesco Orabona and Dávid Pál. Scale-free algorithms for online linear optimization. In International Conference on Algorithumic Learning Theory, pages 287-301. Springer, 2015.
[44] Nhan H. Pham, Lam M. Nguyen, Dzung Phan, and Quoc Tran- Tran-Dinh. Proxsarah: An efficient algorithmic framework for stochastic composite nonconvex optimization, 2019. URL huttps://arxiis wwg.titwwwwww...a.ooooo.oo.oortt org/abs 1902. 05679.
[45] Sashank J. Reddi, Ahmed Hefnny. Suvrit Sra, Barnabas Poczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. Proceedings The 33rd International Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pages 314-323, PMLR, 2016.
[46] Herbert Robbins and Sutton Monro. A Stochastic Approximation Method. The Annals of Mathematical Statistics, 22(3):400- 407, 1951. doi: 10.1214/0mm//1177775566 URL https:://dot org/10 1214/ aoms/117722958.
[47] Chaobing Song, Yong Jiang, and Yi Ma. Variance reduction via accelcrated dual averaging for finite-sum optimization. In Advances in Neural Information Processing Systems, volume 33, pages 833- 844, Curran Associates, Inc., 2020.
[48] Matthew Streeter and H. Brendan McMahan. Less regret via online conditioning. CoRR, abs/1002.4862. 2010.
[49] Conghui Tan, Shiqian Ma, Yu- Hu-Hong Dai, and Yuqiu Qian. karzilai-borweht step size for stochastic gradient descent. In Proceedings of the 30th International Conference on Neural Information Processing Systems, NIPS'16. 16. page 685 693, Red Hook, NY, USA, 2016. Curran Associates Inc. ISBN 0781510838819,
[50] Dong Quan Vu, Kimon Antonakopoulos, and Panayotis Mertikopoulos. Fast routing under uncertainty: Adaptive lcarning in congestion games via exponential weights. In Marc' Aurelio Ranzato, Alina Beygelz- imer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 1021, NeurIPS 2021, December 6-14, 2021, virtual, pages 14708-14720, 2021.
[51] Zhe Wang, Kaiyi Ji, Yi Zhou, Yingbin Liang, and Vahid Tarokh. Spiderboost and momentum: Faster variance reduction algorithms. In Hanna M. Wallach, Hugo I arochelle, Alina Beygelzimer, Florence d' Alché-BBue, Fmily B. Fox, and Roman Garnett, editors, Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 2403-2413, 2019.
[52] Rachel Ward, Xiaoxia Wu, and Léon Bottou, Adagrad stepsizes: sharp convergence over nonconvex land- scapes. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning. ICML 2019, 9-15 June 2019, Long Beach, California. USA, volume 97 of Proceedings of Machine Learning Research, pages 6677-6666 6686. PMLR, 2019.
[53] Blake E. Woodworth and Nati Srebro. Tight complexity bounds for optimizing composite objectives. In Daniel D. Lee, Masashi Sugiyama. Ulrike von Luxburg. Isabelle Guyon, and Roman Gamett, editors. Advances in Neural Information Processing Systems 29; Annual Conference on Neural Information Processing Systems 2016, December 5-10, 2016, Barcelona, Spain, pages 3639-3647, 2016.
[54] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07744 2017.
13

---

[55] Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for non- convex optimization. In S. Bengio, H. Wallach, H. Larochelle. K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL https:/ stsp:://pocceddnng. wew.eeddinnnnnnnnnssseeeee http://n....nrrppp..cppppppeeeee httpp/p....cppppe///////t/ (aor9513622ab22244eeeeee (111841183c299-PP0 Paper-.d..
[56] Zeyuan Allen Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In Maria-Flonin Balcan and Kilian Q. Weinberger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 699-707. JMLR.org. 2016.
[57] Zeyuan Allen Zhu and Yang Yuan. Improved SVRG for mon-strongly-oover or sum-of-non-convex objec- tives. In Maria-Florina Balcan and Kilian Q. Weinherger, editors, Proceedings of the 33nd International Conference on Machine Learning, ICMI, 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1080~1089. Jor,R. 2016.
[58] Zeyuan Allen Zhu and Yang Yuan. Improved SVRG for non strongly-conve or sum-of sum-of-non-eeee oo-oox-convex objectives. In Maria-Florina Balcan and Kilian Q. Weinherger, editors, Proceedings of the 33nd Inter- national Conference on Machine Learning. ICMI. 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 1080-1089. JML..org. 2016. URL http:// attp://proceedinng mlr. ptwss/v48/ allen- zhub16. html.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See, c.g, discussion below
Remark 3, contributions section of the Introduction
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section Theorem
(b) Did you include complete proofs of all theoretical results? [Yes] See the Appendix
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e-g., with respect to the random seed after running experi-
ments multiple times)? [Yes] We provide mean and standard deviation on the curves over multiple runs
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
14

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "wiXcbAwqsBr", "reviewer": "Reviewer_5sbc", "summary": "This paper presents a convergence analysis of an adaptive variance-reduction method (AdaSpider), which combines Spider method with the global(norm) version of AdaGrad stepsizes, for the minimization of smooth functions with a finite time structure. In particular, they show that AdaSpider can get an $\\epsilon$ stationary point with $\\tilde{O}\\left(n + \\sqrt{n}/\\epsilon^2 \\right)$ oracle complexity in expectation. Numerical results are also conducted. ", "questions": "I'm wondering if it is possible to extend the analysis to the convex setting. Will AdaSpider still yield an (almost) optimal oracle complexity? ", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper is well written and easy to follow. As far as I know, it is the first parameter-free nonconvex variance reduction method. In this way, I tend to support accepting this paper. Yet I have the following concerns.\n\nAdaSpider vs. Spider/Spiderboost: The advantage of AdaSpider is parameter-free, i.e. without prior knowledge of problem dependent parameter smoothness L/less tuning. However, theoretically, it has a worse dependency on the smoothness L as well as pays a logarithmic term compared to Spider. Also, though the method requires less tuning, it seems no better (sometimes worse) than the other variance reduction methods as shown in the experimental part. \n\nMinor:  Line 83, the dependency on the smoothness should be $L^4$?\n\n\n\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2vuGeWLHsUT", "reviewer": "Reviewer_kKhQ", "summary": "This paper considers the problem of finding a first-order stationary point of a non-convex function which decomposes into a finite sum of $L$-smooth functions. The main motivating prior work is the SPIDER algorithm, which is an stochastic variance-reduction algorithm with non-adaptive step-sizes which achieves an order-optimal convergence rate for this setting. However, this algorithm is only guaranteed this convergence rate when the step-sizes are carefully tuned to problem parameters (e.g., the accuracy $\\epsilon$ and smoothness constant $L$). Since these parameters may not be known a-priori, and the smoothness constant in particular may be difficult to compute, the authors aim to design an algorithm which does not need to be tuned w.r.t. these parameters. They propose a variant of the SPIDER algorithm which uses adaptively-chosen step sizes, and show that, up to logarithmic factors, their method obtains order-optimal convergence without tuning the step-size with $\\epsilon$ or $L$.", "questions": "I have outlined my main comments and questions in the **Limitations** section above. The main points that I would like to see addressed in the rebuttal are the following:\n\n- A more detailed discussion of prior work, and its relation to your work, and some techniques you use (e.g., to removing bounded gradient assumptions) should be added to the paper. I would like to see an outline of how you plan to incorporate this discussion in your paper.\n- I am particularly interested in hearing your responses to the points raised in _Technical novelty and limitations of results_, and would be interested to see if the results of your paper could be improved as suggested there, or if there are significant challenges in doing so.\n- I think it is important to fix the issues regarding _Dimensional analysis_ in your paper, as these discrepancies that are currently in your results make quickly sanity-checking the results very difficult for the quick/casual reader.\n- Regarding the missing lemmas/inequality explanations, I would like to see a discussion about this. Do you plan to incorporate these changes? Or have I missed something simple here?\n\n**Please note** that my current score for this paper reflects the fact that there are a number of changes that should be addressed by the authors before it is ready for publication. I will happily upgrade my score if the concerns I have raised are satisfactorily addressed.\n", "limitations": "N/A\n", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**:\nThis paper addresses an important problem of designing optimization algorithms which are guaranteed to converge even when the parameters of the objective function (namely, the smoothness constant) are not known, or are underestimated. The exposition of their algorithm, ideas, and analysis are well-written, and pretty concise and clear. Overall, I found this paper very accessible and easy to follow.\n\nMoreover, except for some minor typos, some (inconsequential) weirdness w.r.t. dimensional analysis, and some expressions which are not fully explained, the results of this paper appear correct to me, after a thorough reading of the proofs.\n\n**Weaknesses**:\nThere are a number of issues I came across in the paper (both technical, and in regards to prior work) that should be addressed. I will outline them below:\n\n> _Discussion of prior work_\n\nYour paper has missed a substantial amount of prior work which is very closely related to your paper. Indeed, the step-sizes that you consider are precisely the AdaGrad-Norm step sizes, introduced in “Less regret via online conditioning” (arXiv:1002.4862, 2010) in the online convex opt context, and analyzed further by “Scale-Free Algorithms for Online Linear\nOptimization” (ALT’15) (again in the context of online), and later by, e.g., “AdaGrad stepsizes: Sharp Convergence over Nonconvex Landscapes” (ICML’19), “The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance” (COLT’22), and minor variations of this step-size by “On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes” (AISTATS’19), “A High Probability Analysis of Adaptive SGD\nwith Momentum” (ICML’20 workshop). There are many other papers in this line of work, and this is only a small sample.\n\nParticularly related to your work is “The Power of Adaptivity in SGD: Self-Tuning Step Sizes with Unbounded Gradients and Affine Variance”, which deals with unbounded gradients, and guarantees their convergence rate without tuning the step size w.r.t. the smoothness constant $L$. In fact, Lemma 4 in your paper is essentially the same as Lemma 2 in that paper.\n\nI believe your paper should include a discussion on the line of work of AdaGrad-Norm, since it is the algorithm you consider in this paper. Further, it would be good to draw connections to the other recent works which avoid the need for assumptions of bounded gradients.\n\nAlso, when referencing the AdaGrad algorithm, I would suggest also citing “Adaptive Bound Optimization for Online Convex Optimization” (COLT’10), which proposed the AdaGrad algorithm concurrently (and in the same conference) to the Duchi, Hazan, and Singer paper.\n\n> _Technical novelty and limitations of results_:\n\nI have some observations about the results of your paper in relation to those of prior work.\n\n_The step-size choice_: While it is nice that your step-size choice does not need to be tuned w.r.t. the smoothness parameter $L$, this is not surprising to me, since AdaGrad-Norm is well-known to have this nice property (the earliest reference observing this property which I am aware of is “AdaGrad stepsizes: Sharp Convergence over Nonconvex Landscapes” (ICML’19), but I would not be surprised if it was observed in earlier work also).\n\nIn that prior work (as well as follow-up work to it), AdaGrad-Norm has an order-optimal convergence rate for _any_ choice of parameters. This seems to stand in contrast to your algorithm, where the step-size is tuned w.r.t. $n$ (which is, in a sense, a parameter which controls the variance, according to Lemma 5). It is not very intuitive to me why the step size in your setting should be tuned with this parameter (and, in particular, why the multiplicative factor of $1/n^{1/4}$ should be there). If $n = \\Theta(T)$ (which I would assume is typically the regime of interest?), then this step size is typically smaller than $1/\\sqrt{T}$, which I find somewhat surprising.\n\nIt would be very interesting, and perhaps a stronger result, if you could guarantee your convergence rate without tuning these parameters. Do you think this is possible? I noticed there seem to be a couple of places where there is some (small amount of) slack in your analysis (see my second comment in _Minor typos in some lemmas_). Do you think that by using this extra slack, your analysis could be improved to avoid this inverse multiplicative dependence on $n$ in the step-size? One possible place that I see where this (maybe?) could be improved is by more carefully upper-bounding in the second step of line 522, using the fact that for any $\\lambda > 0$,\n$$\n-\\gamma_t \\nabla_t^\\top (\\nabla f(x_t) - \\nabla_t)\n\\leq \\frac{\\lambda}{2} \\lVert \\nabla_t \\rVert^2 + \\frac{1}{2\\lambda} \\lVert \\nabla f(x_t) - \\nabla_t \\rVert^2,\n$$\nand optimizing the choice of $\\lambda$, perhaps as a function of $n$. In your analysis, you simply use $\\lambda = 1$, but perhaps there is a better choice here that would improve your result?\n\n_Convergence in “small-noise” regime_: Most results in stochastic first-order optimization (including all of the analyses of AdaGrad-Norm that I am aware of) obtain a faster convergence rate in the setting where the variance of the stochastic gradients is vanishingly small in $T$. In your setting, this perhaps could be viewed as many (or perhaps all) of the functions $f_i$ being the same (in this setting, your algorithm would obtain essentially a full estimate of the gradient for most time steps). I believe this should manifest itself as having a better dependence on $n$ in your convergence rate. Is there any way to quickly see this from Theorem 1? Or would a new, more refined analysis be needed to observe this phenomenon? \n\n_Technical novelty_: The results in this paper have a simple and concise proof, which is nice! However, it seems (at least to me – perhaps I am missing something!) that the results seem to follow from a straightforward combination of techniques from the SPIDER paper, together with prior techniques used to analyze AdaGrad-Norm in the stochastic setting. In this sense, the results of this paper are not too surprising to me – I would expect that the AdaGrad-Norm step size applied to SPIDER would have a similar convergence rate without having to tune w.r.t. $L$. Were there other (perhaps subtle?) challenges that you faced in obtaining these results? It would be nice to highlight these, if so.\n\n> _Proof of Theorem 1_\n\nI think that the first inequality in proof of Theorem 1 (line 545) needs a bit more explanation. First, there is a small typo, as there should be a sum over all times on the left-hand side. Second, you should explicitly say first that Lemmas 5-7 imply that\n$$\n\\frac{1}{n^{1/4} \\sqrt{T}} \\mathbb{E}[\\lVert \\nabla_t \\rVert] \\leq 2\\Delta_0 + 1 + \\frac{L \\log(...)}{\\sqrt{n}} + L^2 n \\mathbb{E}[\\gamma_t^3 \\lVert \\nabla_t\\rVert^2].\n$$\nThat inequality is easy to see by just combining those Lemmas. Then, you should show how to relate the LHS to the quantity you are interested in, using the observation that:\n$$\n\\frac{1}{T} \\sum_t \\mathbb{E}[\\lVert \\nabla f(x_t) \\rVert]\n=\n\\frac{1}{T} \\sum_t \\mathbb{E}[\\lVert \\nabla_t + \\nabla f(x_t) - \\nabla_t \\rVert]\n\\leq\n\\frac{1}{T} \\sum_t \\mathbb{E}[\\lVert \\nabla_t \\rVert + \\lVert \\nabla f(x_t) - \\nabla_t \\rVert],\n$$\ntogether with the fact that, by Lemma 5,\n$$\n\\frac{1}{T} \\sum_t \\mathbb{E}[\\lVert \\nabla f(x_t) - \\nabla_t \\rVert]\n\\leq\n\\frac{L n^{1/4} log(...)}{\\sqrt{T}}.\n$$\nI am not sure if the above is very standard in this line of work (I suspect that it probably is), but since it was not written anywhere in this paper, I originally thought there was a serious mistake in the proof of Theorem 1. I would strongly suggest that you elaborate on that inequality from line 545 so that others don’t have to think as much about this :)\n\n> _Dimensional analysis_:\n\nThere are many places in the paper where the dimensional analysis of your results does not quite check out. For instance, the quantity inside of the $\\log$ in Theorem 1 is not unitless, since $n L T \\lVert \\nabla f(x_0) \\rVert$ has units $f^2 / x^3$. For a detailed discussion on the problems with taking a logarithm of a quantity with units, you can see, e.g., the discussion in Appendix A of arxiv:2002.11259, “Dimensional Analysis in Statistical Modeling”. There are a number of other places in your paper where this problem also appears, e.g., Lemma 4, 5, 6, among other places.\n\nI would like to clarify, before continuing, that I don’t think this invalidates your results (though it should be either fixed or clarified in your paper). Indeed, it seems that the source of this “strangeness” comes from your choice of step-size. Indeed, in the denominator, you add a “unitless” quantity, $n$, with a quantity with units of ($f^2 / x^2$), $\\lVert \\nabla f(x_t) \\rVert^2$. Additionally, to make the units of the update check out (i.e., to make $\\gamma_t \\nabla_t$ have units $x$), the constant scaling the step-size ($1/n^{1/4}$ in your case) should have units of $x$. Thus, if one were to change the units of the domain $x$ or of the function $f$, then these terms in the step size would need to be scaled accordingly.\n\nIn order to track these units through your analysis (which, in my opinion, is one of the easiest ways to quickly sanity-check an optimization result), it would make things much easier if you included constants in your step size, scaling the multiplicative $1/n^{1/4}$ and additive $n^{1/2}$ terms. These constants would implicitly have the correct units, and would make verifying your result much easier on a quick read.\n\nTo conclude – I don’t think this issue creates any contradictory results for your guarantee. However, it makes reading some of the results a bit confusing, and throws some red flags (especially seeing a quantity with units inside a log). So I would suggest this issue be fixed throughout the paper.\n\n> _Minor typos in some lemmas_:\n\nI came across a number of minor errors/omissions (all inconsequential) in your technical results.\n\n_In the proof of Lemma 4_,  on line 507, it is not clear to me why $L$ and $\\lVert \\nabla f(x_0) \\rVert$ should be larger than $1$ w.l.o.g. When this is not true, then the last inequality in the following line is not true. Why not just replace the multiplication with an addition here?\n\n_Not an error, but_ it seems to me (unless I’m mistaken) that, on the second line of the inequality following line 525 (inside proof of Lemma 6), that $L$ can actually be $L/\\sqrt{n}$. Perhaps this makes some constants in your convergence rate slightly smaller? Not sure…\n\n_Also in the proof of Lemma 6_, in the third inequality on line 527, I believe you are using the fact that:\n$$\n\\sum_t \\frac{a_t}{\\sqrt{\\sum_{s\\leq t} a_s}} \\geq \\sqrt{\\sum_t a_t}.\n$$\nThis, of course, is a standard result which can be proven easily by induction. However, it is not written anywhere in your paper. Perhaps it should be included in the statement of Lemma 1? In fact, I didn’t find anywhere in your paper where Lemma 1 was used, and it seemed to me you only needed the lower bound. Perhaps you can just replace Lemma 1 with this bound?\n\n_One last thing in proof of Lemma 6_, it seems that the $L^2$ inside the $\\tilde{O}$ on line 528 should actually be replaced by $L/\\sqrt{n}$. This makes some constants in later results slightly better.\n\n_Small comment in proof of Lemma 7_, on lines 532-533, you say that “...which we have to do to circumvent non-measurability issues”. I was confused by this statement, as I don’t see why having a decreasing step size has anything to do with measurability… Perhaps this comment should be changed?\n\n_Another small typo in proof of Lemma 7_, the 3rd equality on line 536 should be an inequality I believe (it’s equality by adding $- \\gamma_{t-1}\\lVert \\nabla f(x_t) - \\nabla f(x_{t-1})\\rVert$). Not a big deal, just wanted to point this out.\n", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "2MT29Pb-49L", "reviewer": "Reviewer_rV1y", "summary": "The paper proposed a adaptive variant of Spider, called AdaSpider, for solving non-convex and smooth finite-sum optimization problem with the complexity of $\\tilde O(n + \\sqrt{n}/\\epsilon^2)$ of finding a first-order stationary point. In addition, the proposed AdaSpider is a parameter-free algorithm, which is pratical in real applications. Finally, the authors provided some experimental results on non-convex optimization and neural networks. ", "questions": "It seems the analysis heavily follows the Spider paper, which is very straightforward. I can not see the advantage of convergence analysis in this paper. Besider, the experimental results reveal that Spiderboost is better than AdaSpider. Can you explain?", "limitations": "No.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: The orginization of this paper is good and its presentation is clear to me. The proposed AdaSpide is parameter-free, which is a significant contribution to the non-convex optimization community. The experiments with neural networks are studied.  \n\nCons: The advantage of its convergence analysis over the standard one, i.e., Spider (Fang et. al), is not clear. Due to the additional $\\log$ term, the convergence result of the proposed AdaSpider is even worse than Spider and Spiderboost (Wang et. al). The experimental results show that the proposed AdaSpider is worse than Spiderboost.  ", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept