ZeroSARAH: Efficient Nonconvex Finite-Sum Optimization with Zero Full Gradient Computations
Authors: Zhize Li
Slavomir Hanzely
Peter Richtárik
Venue: ICLR 2022 Submitted (2022)
Keywords: nonconvex optimization
distributed optimization
finite-sum optimization
zero full gradient computation
variance reduction

Abstract: We propose ZeroSARAH -- a novel variant of the variance-reduced method SARAH (Nguyen et al., 2017) -- for minimizing the average of a large number of nonconvex functions $\frac{1}{n}\sum_{i=1}^{n}f_i(x)$. To the best of our knowledge, in this nonconvex finite-sum regime, all existing variance-reduced methods, including SARAH, SVRG, SAGA and their variants, need to compute the full gradient over all $n$ data samples at the initial point $x^0$, and then periodically compute the full gradient once every few iterations (for SVRG, SARAH and their variants). Note that SVRG, SAGA and their variants typically achieve weaker convergence results than variants of SARAH: $n^{2/3}/\epsilon^2$ vs. $n^{1/2}/\epsilon^2$. Thus we focus on the variant of SARAH. The proposed ZeroSARAH and its distributed variant D-ZeroSARAH are the \emph{first} variance-reduced algorithms which \emph{do not require any full gradient computations}, not even for the initial point. Moreover, for both standard and distributed settings, we show that ZeroSARAH and D-ZeroSARAH obtain new state-of-the-art convergence results, which can improve the previous best-known result (given by e.g., SPIDER, SARAH, and PAGE) in certain regimes. Avoiding any full gradient computations (which are time-consuming steps) is important in many applications as the number of data samples $n$ usually is very large. Especially in the distributed setting, periodic computation of full gradient over all data samples needs to periodically synchronize all clients/devices/machines, which may be impossible or unaffordable. Thus, we expect that ZeroSARAH/D-ZeroSARAH will have a practical impact in distributed and federated learning where full device participation is impractical.

Under review as a conference paper at ICLR 2022
ZeroSARAH: EFFICIENT NONCONVEX FINITE-SUM OPTIMIZATION WITH ZERO FULL GRADIENT COMPU- TATIONS
Anonymous authors Paper under double-blind review
ABSTRACT
novel variant of the variance-reduced method 2017) for minimizing the average of a large number SARAH (Nguyen et al. nonconvex functions --1 fz). To the best of our knowledge, in this noncon- vex finite-sum regime, all existing variance-reducee methods, including SARAH, SVRG, SAGA and their variants, need compute the full gradient over all data samples at the initial point x., and then periodically compute the full gradient once every few iterations (for SVRG, SARAH and their variants). Note that SVRG, SAGA and their variants typically achieve weaker convergence results than vari- ants SARAH: 2/3 /e2 vs. n2/2/e2 /e2. Thus we focus on the variant of SARAH. The proposed ZeroSARAH and its distributed variant D-ZeroSARAH variance-reduced algorithms which do not require any full gradient computations, not even for the initial point. Moreover, for both standard and distributed set- tings, we show that ZeroSARAH and D-ZeroSARAH obtain new state-of-the-art convergence results, which can improve the previous best-known result (given by e.g., SPIDER, SARAH, and PAGE) in certain regimes. Avoiding any full gradient computations (which are time-consuming steps) is important many applications as the number of data samples n usually is very large. Especially in the distributed setting, periodic computation of full gradient over all data samples needs to pe- riodically synchronize all dlientsddeiices/mahhines which may be impossible unaffordable. Thus, we expect that COOSARRAHD--erOSARAAA will have prac- tical impact in distributed and federated learning where full device participation is impractical.
We propose ZeroSARAH
the first
INTRODUCTION
Nonconvex optimization is ubiquitous across many domains of machine learning (Jain & Kar 2017). especially in training deep neural networks. In this paper, we consider the nonconvex finite-sum problems of the form
n f(x)= = 72 Σ f((x))
min zERd
f(x)
where f R2d - R is a differentiable and possibly nonconvex function. Problem ① captures the standard empirical risk minimization problems in machine learning (Shalev-Shwartz Ben-David] 2014). There are n data samples and fa denotes the loss associated with i-th data sample. We assume the functions fi : Rdd possibly nonconvex functions.
for all E [m] == (1.2....,n n) are also differentiable and
Beyond the standard/ceentralized problem (T). we further consider the distribuutedfedeertted noncon- vex problems:
1 EmO f((x) _ m Σ fes(z), min f(x) = n1
2E34

---

Under review as a conference paper at ICLR 2022
where n denotes the number of cliett/ddevies/mmchinees f. denotes the loss associated with m data samples stored on client i, and all functions are differentiable and can be nonconvex. Avoiding any full gradient computations is important especially in this distributed setting 2), periodic computation of full gradient over all data samples needs to periodically synchronize all clients, which may be impossible very hard to achieve.
There has been extensive research in designing first-order (gradient-typp methods for solving cen-
tralized/distributed nonconvex problems (1) and (2) such SGD, SVRG, SAGA, SCSG, SARAH
and their variants, e.g., (Ghadimi & Lan 2013 Ghadimi et al. 2016 Allen- Zhu & Hazan 2016
Reddi et al., 2016; Lei al. 2017 Li & Li 2018: Zhou et 2018 Fang et al. 2018: Wang al.
2018 Ge et al.) [219]] Pham et al. [019 Li 22019; Li & Richtárik 2020; Horväth et al. 2020; Li
ett al., ).21). Note that SVRG and SAGA variants typically achieve weaker convergence results than
SARAH variants, i.e., n2/3/e" /e² vs. vn/e². Thus the current best convergence results are achieved
by SARAH variants such as SPIDER (ang et al. 2018). SARAH (Pham et al., 2019) and PAGE (Li
et al.
2021
202T].
However, all of these variance-reduced algorithms (no matter based on SVRG, SAGA or SARAH) require full gradient computations (i.e.. compute fxr 1
n. Ei=1 faz)) without assuming ad- ditional assumptions except standard T-smoothness assumptions. We would like to point out that {f())
S o², Ve E R2), some of them (such as SCSG (Lei et al. (2017). SVRG+ (Li & Li 2018 PAGE al, may avoid full gradient computations by using a large minibatch of stochastic gradients instead (usually the minibatch size is D(a"/<²)) Clearly, there exist some drawbacks: i) o² usually is not known; ii) if the target error e is very small (defined as E[| V [ I e² in Definition 1) or a is very large, then the minibatch size O /e²) is still very large for replacing full gradient computations.
under an additional bounded variance assumption (e.g., E. (z)
In this paper, we only consider algorithms under the standard L-smoothness assumptions, with- out assuming any other additional assumptions (such bounded variance assumption mentioned above). Thus, all existing variance-reduced methods, including SARAH, SVRG, SAGA and their variants, need to compute the full gradient over all data samples at the initial point x and then periodically compute the full gradient once every few iterations (for SVRG, SARAH and their vari- ants). However, full gradient computations are consuminn steps in many applications as the number of data samples n usually is very large. Especially in the distributed setting, periodic com- putation of full gradient needs to periodically synchronize all clients/devices, which usually is im- practical. Motivated by this, we focus on designing new algorithms which do not require any full gradient computations for solving standard and distributed nonconvex problems
2 OUR CONTRIBUTIONS
In this paper, we propose the first variance-reduced algorithm ZeroSARAH (and also its dis- tributed variant D-ZeroSARAH) without computing any full gradients for solving both standard and distributed nonconvex finite-sum problems (2) Moreover, ZeroSARAH and Distributed D-ZeroSARAH can obtain new state-of-the-art convergence results which improve previous best- known results (given by e.g., SPIDER, SARAH and PAGE) in certain regimes (see Tables 2 for the comparison with previous algorithms). ZeroSARAH is formally described in Algorithm 2 which is variant of SARAH (Nguyen et al. 2017). See Section 4 for more details and comparisons between ZeroSARAH and SARAH. Then, D-ZeroSARAH is formally described in Algorithm of Section 5 which is distributed variant of our ZeroSARAH.
Now, we highlight the following results achieved by ZeroSARAH and D-ZeroSARAH:
ZeroSARAH and D-ZeroSARAH are the first variance-reduced algorithms which do not require any full gradient computations, not even for the initial point (see Algorithms 2 or Tables 2 Avoiding any full gradient computations is important in many applications as the number of data samples n usually is very large. Especially in the distributed setting, periodic computation of full gradient over all data samples stored in all clients/devices may be impossible or very hard to achieve. We expect that ZeroSARAHID-ZenSSAARI will have a practical impact in distributed and federated learning where full device participation is impractical.
Moreover, ZeroSARAH can recover the previous best-known convergence result O(n + YALA
(see Table I or Corollary 1. and also provide new state-of-the-art convergence results without any
2

---

Under review as a conference paper at ICLR 2022
Table 1:
Stochastic gradient complexity for finding e-approximate solution of nonconvex prob-
lems T
under Assumption !
Stochastic gradient
Algorithms
Full gradient computation
complexity
GD Nesterov
2004
0 mLLA
Computed for every iteration
SVRG (eeddi et al.
2016
Computed for the initial point and periodically computed for every / iterations
Allen-Zhu & Hazan
2016
O n + n /
SCSG (Li et al.
2017)
SVRG+ Li & Li
2018
Computed for the initial point and periodically computed for every / iterations
SNVRG Zhou et al. 2018
δ (n+ x
Geom-SARAH
(orvááth et al. 2020
SPIDER Fang al.
2018
SpiderBoost Wang 2018
Computed for the initial point and periodically computed for every / itcrations
0 on+ vaygo
SARAH Pham 2019
SSRGD
201
PAGE (Li
2021
ZeroSARAH
O ( + viido
Only computed once the initial point
(this paper, Corollary
ZeroSARAH
o vHlLdgg+Go
Never computed
(this paper, Corollary
In Corollary 1 ZeroSARAH only computes gradient vf(x²) 1 E Vii(a")
" once for the initial point æ., i.e., minibatch size bo n, and then v for all iterations
2 1 Algorithm 2
In Corollary 2 ZeroSARAH never computes full gradients, ie., minibatch size by = v for
all iterations K 0.
full gradient computations (see Table I or Corollary which can improve the previous best result in certain regimes.
Besides, for the distributed nonconvex setting 2). the distributed D-ZeroSARAH (Algorithm) 3 en- joys similar benefits as our ZeroSARAH, i.e., D-ZeroSARAH does not need to periodically synchro- nize all n clients to compute any full gradients, and also provides new state-of-the-ar convergence results. See Table[land Section for more details.
Finally, the experimental results in Section 6 show that ZeroSARAH is slightly better than the previous thate-of SARAH. However, we should point out that ZeroSARAH does not compute any full gradients while SARAH needs to periodically compute the full gradients for every iter- ations (here = vn). Thus the experiments validate our thcoretical results (can be slightly better than SARAH (see Table T and confirm the practical superiority of ZeroSARAH (avoid any full gra- dient computations). Similar experimental results of D-ZeroSARAH for the distributed setting are provided in Appendix A.2
PRELIMINARIES
Notation: Let [n] denote the set 21,2,... .n) and || denote the Euclidean norm for a vector
and the spectral norm for matrix. Let (u, denote the inner product of two vectors u and v. We use O()) and ((-) to hide the absolute constant, and Ö(-) to hide the logarithmic factor. We will
write Do = f(=") fr, f = min f(x), Go == 1 En [|V Ao = f(x") - f.
f = 1 Ei mingers fi(x) and Go == 1 n.
nm EijEn [ (x.)).
3

---

Under review as a conference paper at ICLR 2022
Table 2: Stochastic gradient complexity for finding an e-approximate solution of distributed non- convex problems 2 under Assumption 2
Stochastic gradient
Algorithms
Full gradient computation
complexity
DC-GD
0 m
Computed for every itcration
Khaled & Richtárik
2020
Li & Richtárik
2020
Computed for the initial point and periodically computed
D-SARAH
o yn + s/m log
Cen et al.
2020
across all clients
Computed for the initial point and periodically computed across all clients
D-GET
0 ( m vmyda
Sun al.
2020)
SCAFFOLD
Only computed once for
LAu
m 2/3
Karimireddy et al.
2020
the initial point Computed for the initial point and periodically computed
DC-LSVRG/DD-SAGG
2/3 LAu m +
Li & Richtárik
2020
173
across all n clients
Computed for the initial point and periodically computed across all n clients
FedPAGE 3
0 ( m + LAo
Zhao et al.
2021
Computed for the initial point and periodically computed across all clients
(Distributed) SARAIUSPIDER/SSRDD
O (m LAo
Nguyen et al.
2017
Fang et al.
2018 Li 2019
D-ZeroSARAH (this paper, Corollary
Only computed once for the initial point
O (m v पा. LAA) 2
D-ZeroSARAH
o (v mi L
Never computed
(this paper, Corollary
Distributed compressed methods. Here translate their results to this distributed setting 2
Decentralized methods. Here we translate their results this distributed setting 2
Federated local methods. Here we translate their results to this distributed setting 2
Distributed version of previous SARAH-type methods (see e.g., Algorithm Ii Appendix A.2b.
Definition 1 A point is called an e-approximate solution for noncorvex problems and if [[] | e
To show the convergence results, we assume the following standard smoothness assumption for nonconvex problems I
Assumption (L-smoothness) A function f. Rd + R is L-soooth if 0, such that [V - [y)ll) < L| vll. Vx,y Rd.
It is easy to see that (x) Σ fi(x) is also L-smooth under Assumption 1 We can also relax Assumption 1 by defining L.-smoothness for each St. Then we further denne the average L : 1 Σ" L? we know that f(z) A. Σ. fa(z) is also L-smooth. Here we use the same L just for simple representation.
For the distributed nonconvex problems ( use the following Assumption 2 instead of Assump- tion I Similarly, we can also relax it by defining smoothhsssss for different ft,y- Here we use the same L just for simple representation.
Assumption (L-smoothness) A function fi,j : ..d + R is L-smooth if > 0, such that fz)( - (f),( s L|| vll. Vz, y Rd.
(4)
4

---

Under review as a conference paper at ICLR 2022
Algorithm SARAH (gguyen et al. 2017 Pham et al. 2019)
Input: initial point xº, epoch length 1, stepsize 7), minibatch size
I: I x²
2: for
do
3: x
4:
6D vf(x0) Σ (a((2)
I/ compute the full gradient once for every iterations
5:
x² 500 goo
6:
for k= 1.2..... do
7:
Randomly sample minibatch data samples lo with [o6]
8:
8t Σ (Vf((**) vf((==11)) xk-
ieh
9: x
++ xx 70
end for
11: Ti randomly chosen from fa* Jeeu or T = al+1
end for
Algorithm SARAH without full gradient computations (ZeroSARAH)
Input: initial point σ0, stepsize } minibatch size {by]] J parameter {Aa
1: x =xx"
2: e-1 =-1=0,yp = 1/2
yo
no full gradient computation
3: for k= 0,0,1, =,.,,.2.... do
4: Randomly sample a minibatch data samples 1 with |4,51 = bk
5: uk bu iE
E (V(()")VV/(>>>))
- + d be iE
Σ (Vfi(**11) -v²-1 ッィー
no full gradient computations for e
6: x x+ = t ma2
(*** for i I
7:
for i 15
the update of {ut] directly follows from the stochastic gradients computed in Line
8: end for
ZeroSARAH ALGORITHM AND ITS CONVERGENCE RESULTS
In this section, consider the standard/centrrllized nonconvex problems 1 The distributed setting is considered in the following Section 5
4.1 ZeroSARAH ALGORITHM
We first describe the proposed ZeroSARAH in Algorithm 2 which is variant of SARAH (Nguyen ct al. (017). To better compare with SARAH and ZeroSARAH, we also recall the original SARAH Algorithm[] [
Now, we highlight some points for the difference between SARAH and our ZeroSARAH:
SARAH requires the full gradient computations for every epoch (see Line 4 of Algorithm However, ZeroSARAH combines the past gradient estimator = with another estimator to avoid
periodically computing the full gradient. See the difference between Line of Algorithm and Line 5 of Algorithm
2 (also highlighted with blue color).
The gradient estimator & in ZeroSARAH (Line Algorithm 2 does not require stochastic gradient computations compared with 2n in SARAH (Line of Algorithm 1 if the minibatch size by b.
The new gradient estimator * of ZeroSARAH also leads to simpler algorithmic structure, i.c., single-loop in ZeroSARAH double-loop in SARAH.
5

---

Under review as a conference paper at ICLR 2022
Moreover, the difference of gradient estimator 5t also leads to different results in expectation, i.e., 1) for SARAH: Ex(e* V fz(x") = y y vf(x"-1 (1ak-11) )) 2) for ZeroSARAH: Eg(e* Vf(==))
(1 ( -Vf Vf(x
4.2 CONVERGENCE RESULTS FOR ZeroSARAH
Now, present the main convergence theorem (Theorem of ZeroSARAH (Algorithm) 2 for solv- ing nonconvex finite-sum problems (I). Subsequently, we formulate two corollaries which present the detailed convergence results by specifying the choice of parameters. In particular, we list the results of these two Corollaries in Table for comparing with convergence results of previous works.
Theorem Suppose that Assumplion holds. Choose slepsize S
for any 2 O,
L L(I+/MMer
and Org 2 2m Then the sollowing equation holds for ZeroSARAH (Algorithm 2 for solving problem
where Me+1== == A
2
8
no Moreover, let An = 1, 7o 2
2X
1 for any iteration
K 0:
2Ap
(n 64 + 2ando
E V
(5)
K kk=
nbu Σk
K-1
k== 1/s
Note that we can upper bound both terms on the right-hand side of 5). It means that there no convergence neighborhood of ZeroSARAH and hence, ZeroSARAH can find c-approximate solution for any > 0.
Remark:
In the following. we provide two detailed convergence results in Corollaries 1 and 2 by specifying two kinds of parameter settings. Note that the algorithm computes full gradient in iteration & the minibatch by n. Our convergence results show that without computing any full gradients actually does not hurt the convergence performance of algorithms (see Table IT.
In partieular, note that the second term of will be deleted if we choose minibatch size bo for the initial point _. (see Corollary for more details). Here Corollary only needs to compute the full gradient once for the initialization, and does not compute any full gradients later (i.e., bş /n for all & > 0).
I
Also note that even if we choose n. we can also upper bound the second term of ( means that ZeroSARAH can find an e-approximate solution without computing any full gradients even for the initial point, i.e., minibatch size by < n for all iterations k For instance, we choose by /n for all & > 0 in Corollary 2 i... ZeroSARAH never computes any full gradients even for the initial point.
Corollary Suppose that Assumption holds. Choose stepsize тkk S (1+vS)L for any k 2 0,
by minibatch size by /ni and parameter d 2n for any k 2 L. Moreover, let bo and X 1. Then ZeroSARAH (Algorithm) 2) can canfind an e-approximate solution for problem ( such that
EIllff(*>\I"" =
and the number of stochastic gradient computations can be bounded by
K-1
by Inn 2(1 + v8) =((n+
VnLAu e²
#grad
Remark: In Corollary ZeroSARAH only computes the full gradient ) ff(2)) once for the initial point 20, i.e., minibatch size by = n, and then by = v for all iterations 2 in Algorithm
In the following Corollary 2 we show that ZeroSARAH without computing any full gradients even for the initial point does not hurt its convergence performance.

---

Under review as a conference paper at ICLR 2022
Corollary 2 Suppose that Assumption 1 holds. Choose stepsize 7k-
(14v8)L for any k 2 0,
minibatch size by /n for any k 2 and parameter de and Aς=
hu for any k 2 Then
ZeroSARAH (Algorithm 2 can find an e-approximate solution for problem
such that
f |l E
and the number of stochastic gradient computations can be bounded by
#grad =0 V + Go)
2
Note that Go can be bounded by Go S 2L via L-smootiness Assumption 1 then we also have #grad = O vM(LAD + LÔO)
2²
Remark: In Corollary 2 ZeroSARAH never computes any full gradients even for the initial point, i... minibatch size by /n for all iterations & 2 0 in Algorithm 2 If we consider L, Do. Go or An as constant values then the stochastic gradient complexity in Corollary is #grad 0 /m i.e. full gradient computations do not appear in ZeroSARAH (Algorithm 2 and the term 'n' also does not appear its convergence result. Also note that the parameter settings (i.e., { {6&} and } in Algorithm25 2) of Corollaries | and are exactly the same except for bo
(in Corollary I
and /u (in Corollary 2). Moreover, the parameter settings (i.e., {Tı,; ). {ba} } and {Ax}) only only
Corollaries and
require the values of L. and n, which is the same as all previous algorithms.
If one further allows other values, c.g., c, Go Åg. for setting the initial by. then the gradient complexity can further improved (see Appendix Defor more details).
D-ZeroSARAH ALGORITHM AND ITS CONVERGENCE RESULTS
Now, we consider the distributed nonconvex problems 2 i.e. min [=)x)== - f((z)) with f() = 1 Σx= (z), where n denotes the number of clients/device//machines,,, f; denotes m
the loss associated with m data samples stored on client i.
5.1 D-ZeroSARAH ALGORITIM
To solve distributed nonconvex problems we propose distributed variant of ZeroSARAH (called D-ZeroSARAH) and describe in Algorithm Same as our ZeroSARAH, D-ZeroSARAH also does not need to compute any full gradients at all. Avoiding any full gradient computations is important especially in this distributed setting, periodic computation full gradient across all n clients may be impossible unaffordable. Thus, expect the proposed D-ZeroSARAH (Algorithm (3 will have practical impact in distributed and federated learning where full device participation impractical.
5.2 CONVERGENCE RESULTS FOR D-ZeroSARAH
Similar ZeroSARAH in Section 4. we also first present the main convergence theorem (The-
orem 2 of D-ZeroSARAH (Algorithm quently, formulate two corollaries which present the detailed convergence results by specifying the choice of parameters. In particular, we list the results of these two Corollaries 3 3 in Table 2 for comparing with convergence results of previous works. Note that here we use smoothness Assumption instead of Assumption for this distributed setting (2)
3) for solving distributed nonconvex problems (2). Subse-
Theorem Suppose that Assumption
2 holds. Choose stepsize TH S
for any 2 O,
8 where Wh+1 == be41 < Pi
Moreover, let No = and Oo == Inm-11A
4Tumn da x7
Then the following equation holds for D-ZeroSARAH (Algorithm 3 for solving distributed problem 2p. for any iteration K 2 0:
24
+ (nm subo mobo)
B|IV/(?>>)P MP
(6)
Σ 77
K- R=0
nmsgbo Σk-1 17
7

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Distributed ZeroSARAH (D-ZeroSARAH)
Input: initial point 2., parameters (mH }. {8k), (bb), {7s}
I: =xr
2: e- -0.1- -0.01-10 1/2 -.. M/
// no full gradient computation
3: for k =0.1,2,... do
4: Randomly sample a subset of clients s from clients with size | Sk
5: for each client S* do
6: Sample the data minibatch Th (with size 1 = by)) from the m data samples in client
7:
Compute its local minibatch gradient information:
Σ Vee((=")) Di.cum bx jELS
P.mee bk
Σ V(es(ah-1),
Vi.prev by jE
Σ vi
JE
yh. = ((a((a
for j E by for j & lh.
ur
1
Σ
Vis
8:
end for t
9:
Σ (giear pre + (1 Ax)ua-1 + Ale sk iESt
Σ
ss.
ieSt
// no full gradient computations for uss
x k+1
11:
1 2
If here v. = for client S
1=1
end for
Corollary Suppose that Assumption 2 holds. Choose stepsize 1)
(1+v8JL for any 2 0,
clients subset size 8& = /n, minibatch size by = /m and parameter Ak Moreover, let so n, m, and do Then D-ZeroSARAH (Algorithm 3 can find an
scbs
for any k 2 1.
2nm
e-approximate solution for distributed problem (2) such that
and the number of stochastic gradient computations for each client can bounded by
#grad = =0( m LDo
2
Corollary Suppose that Assumption
2 holds. Choose stepsize Tlk (1+v8)L for any 2 0.
clients subset size Sy /n and minibatch size by mm for any k 0, and parameter Ào 1 and
gabs for any k > 1. Then D-ZeroSARAH (Algorithm 3) can find an e-approximate solution for A 2nm
distributed problem 2 such that
EIIVS("*>IE |
and the number of stochastic gradient computations for each client can be bounded by
#grad =0( m LAo G%
Remark: Similar discussions and remarks of Theorem D and Corollaries 2 for ZeroSARAH in Section 4.2 also hold for the results of D-ZeroSARAH (i.e., Theorem and Corollaries
EXPERIMENTS
Now, we present the numerical experiments for comparing the performance of our ZeroSARAH/D. ZeroSARAH with previous algorithms. In the experiments, consider the nonconvex robust linear regression and binary classification with two-layer neural networks, which are used in (Wang et al.
2018 Zhao al. 2010 Tran-Dinh et al. 2019). All datasets used in experiments down- loaded from LIBS VM (Chang & Lin 2011 1). The detailed description of these objective functions
and datasets provided in Appendix
A.1
8

---

Under review as a conference paper at ICLR 2022
Ditesie nx
ZeroScAM
EWiteC Swppie 1
Haares Incesice 3-3
ng Serpier (-0
22th Diteere Ca
55AAM
Zere5A
Zer 154AA
ZundatAe
gyacn
*ynds
#grssh
pyss
820828 Irapica y-
chat Irapiix 2-
ng Yigpiza y-
syd's uttaziza
SARAH ZereSh
SAR/
SARMI
2er:5AgA-1
Crette RAtM
ZenoSARAi
Figure I: Performance between SARAH and ZeroSARAH under different datasets (columns) with respect to different stepsizes (rows). In rows, we have stepsizes 0.01, 0.1, respectively. In columns, we have LIBSVM datasates 'abalone', 'triazines', 'mg', 'pyrim', respectively.
In Figure I the z-axis and y-axis represent the number of stochastic gradient computations and the norm of gradient, respectively. The numerical results presented in Figure | are conducted on different datasets with different stepsizes. Regrading the parameter settings, we directly use the theoretical values according to the theorems or corollaries of SARAH and ZeroSARAH, i.e., we do not tune the parameters. Concretely, for SARAH (Algorithm
1b. the epoch length / = vn and the minibatch size b /n (see Theorem 6 in Pham et al. (2019). ). For ZeroSARAH (Algorithm 2. by
the minibatch size by v for any k 2 0, Ao = and 0 2n 2/n for any k N
(see our Corollary 2. Note that there is no epoch length / for ZeroSARAH since it is a loopless (single-loop) algorithm while SARAH requires 1 for setting the length of its inner-loop (see Line 6 of Al Algorithm|] [). For the stepsize both SARAH and ZeroSARAH adopt the same constant stepsize " )( However the smooth parameter I, is not known in the experiments, thus here we use three stepsizes, i.e., 17 = 0.01, 0.
The experimental results validate theoretical convergence results (our ZeroSARAH can be slightly better than SARAH (see Table T and confirm the practical superiority of ZeroSARAH (avoid any full gradient computations). To demonstrate the full gradient computations in Figure I we point out that each circle marker in the curve of SARAH (blue curves) denotes a full gradient computation in SARAH. We emphasize that our ZeroSARAH never computes any full gradients. Note that in this section we only present the experiments for the standard/centtraized setting (1. Similar experiments in the distributed setting (2) are provided in Appendix A.2 c.g., Figure demonstrates similar performance between distributed SARAH and distributed ZeroSARAH.
Remark:
7 CONCLUSION
In this paper, we propose ZeroSARAH and its distributed variant D-ZeroSARAH algorithms for solv- ing both standard and distributed nonconvex finite-sum problems (I) and (2). In particular, they are the first variance-reduced algorithms which do not require any full gradient computations, not even for the initial point. Moreover, our new algorithms can achieve better theoretical results than previ- ous state-of-the-an the--ar results in certain regimes. While the numerical performance of our algorithms is also comparable/better than previous state-of-the-an algorithms, the main advantage of our algo- rithms is that they do not need to compute any full gradients. This characteristic can lead to practical significance of our algorithms since periodic computation of full gradient over all data samples from all clients usually is impractical and unaffordable.
9

---

Under review as a conference paper at ICLR 2022
REFERENCES
Zeyuan Allen-Zhu and Elad Hazan. Variance reduction for faster non-convex optimization. In International Conference on Machine Learning, pp. 699-707, 2016.
Shicong Cen, Huishuai Zhang, Yuejie Chi, Wei Chen, and Tie- Yan Liu. Convergence of distributed stochastic variance reduced methods without sampling extra data. IEEE Transactions on Signal Processing, (8:3976-3989) 2020.
Chih-Chung Chang and Chih-Jen Lin. LIBSVM: a library for support vector machines. transactions on intelligent systems and technology (TIST), 2(3): 2011.
ACM
Cong Fang, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. SPIDER: Near-optimal non-convex optimization via stochastic path-integrated differential estimator. In Advances in Neural Informa- tion Processing Systems, pp. 687-697, 2018
Rong Ge, Zhize Li, Weiyao Wang, and Xiang Wang. Stabilized SVRG: Simple variance reduction for nonconvex optimization. Conference on Learning Theory, pp. 1394-1448, 2019.
Saeed Ghadimi and Guanghui L Stochastic first-and zeroth-order methods for nonconvex stochas- tic programming. SIAM Journal on Optimization, 23(4):2341-2363 2013.
Saeed Ghadimi, Guanghui Lan, and Hongchao Zhang. Mini-batch stochastic approximation meth-
ods for nonconvex stochastic composite optimization. Mathematical Programming, 155(1-2): 267-305, 2016.
Samuel Horváth, Lihua Lei, Peter Richtárik, and Michael I Jordan. Adaptivity of stochastic gradient methods for nonconvex optimization. arXiv preprint arXiv:2002.0535) 2020.
Prateek Jain and Purushottam Kar. Non-convex optimization for machine learning. Foundations and Trends( in Machine Learning, 10(3-4):142-336, 2017.
Sai Praneeth Karimireddy, Satyen Kale. Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. SCAFFOLD: Stochastic controlled averaging for federated learning. In International Conference on Machine Learning, pp. 5132-5143, PMLR, 2020.
Ahmed Khaled and Peter Richtárik. Better theory for SGD in the nonconvex world. arXiv preprint arXiv:2002.03329, 2020.
Lihua Lei, Cheng Ju, Jianbo Chen, and Michael Jordan. Non-convex finite-sum optimization via SCSG methods. In Advances in Neural Information Processing Systems, pp. 2345-2355, 2017.
Thize Li. SSRGD: Simple stochastic recursive gradient descent for escaping saddle points. In Advances in Neural Information Processing Systems, pp. 1521-1531, 2019.
Zhize Li. A short note of PAGE: Optimal convergence rates for nonconvex optimization. arXiv preprint arXiv:2 106. 09660966, 2021.
Zhize Li and Jian Li. simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 5569-5579, 2018.
Zhize Li and Peter Richtárik. A unified analysis of stochastic gradient methods for nonconvex federated optimization. arXiv preprint arXiv:2006.0700 2020.
Zhize Li, Hongyan Bao, Xiangliang Zhang, and Peter Richtárik. PAGE: A simple and optimal prob- abilistic gradient estimator for nonconvex optimization. In International Conference on Machine Learning, pp. 6286-6295. PMLR, wwXiv:2008.1089: 2021.
Yurii Nesterov. Introductory Lectures on Convex Optimization: A Basic Course. Kluwer, 2004.
Lam M Nguyen, Jie Liu, Katya Scheinberg, and Martin Takáč. SARAH: A novel method for ma- chine learning problems using stochastic recursive gradient. International Conference on Ma- chine Learning, pp. 2613-2621, 2017.
10

---

Under review as a conference paper at ICLR 2022
Nhan H Pham, Lam M Nguyen, Dzung Phan, and Quoe Tran-Dinh. ProXSARAH: An effi- cient algorithmic framework for stochastic composite nonconvex optimization. arXiv preprint arXiv:1902.05679, 2019.
Sashank Reddi, Ahmed Hefny, Suvrit Sra, Barnabás Póczos, and Alex Smola. Stochastic variance reduction for nonconvex optimization. In International conference on machine learning, pp. 314 323, 2016.
Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: from theory to algo- rithms. Cambridge University Press, 2014.
Haoran Sun, Songtao Lu, and Mingyi Hong. Improving the sample and communication complexity for decentralized non-convex optimization: Joint gradient estimation and tracking. Interna- tional Conference on Machine Learning, pp. 9217-9223 PMLR, 2020.
Quoc Tran-Dinh, Nhan Pham, Dzung T Phan, and Lam M Nguyen. Hybrid stochastic gradi- ent descent algorithms for stochastic nonconvex optimization. arXiv preprint 2019.
Zhe Wang, Kaiyi Ji, Zhou, Yinghin Liang, and Vahid Tarokh. SpiderBoost and momentum:
Faster stochastic variance reduction algorithms. arXiv preprint arXiv:1810. 2018.
Haoyu Zhao, Zhize Li, and Peter Richtárik. FedPAGE: A fast local stochastic gradient method for communication-efficceen federated learning. arXiv preprint wrXiv:2108.04770 2021.
Lei Zhao, Musa Mammadov, and John Yearwood. From convex to nonconvex: a loss function anal- ysis for binary classification. 2010 IEEE International Conference on Data Mining Workshops, pp. 1281-1288. IEEE, 2010.
Dongruo Zhou, Pan Xu, and Quanquan Gu. Stochastic nested variance reduction for nonconvex optimization. In Advances in Neural Information Processing Systems, pp. 3925-3936, 2018
11

---

Under review as a conference paper at ICLR 2022
A EXTRA EXPERIMENTS
In this appendix, we first describe the details of the objective functions and datasets used in our experiments in Appendix A.I Then in Appendix A.2 we present the experimental results in the distributed setting (2)
A.1
OBJECTIVE FUNCTIONS AND DATASETS IN EXPERIMENTS
The nonconvex robust linear regression problem (used Wang et al. (018)) is:
min zER
f(z)
Σ
Elb:
x² ai) )
71
where the nonconvex loss function {(x) == log( 5" 2 + +).
The binary classification with two-layer neural networks (used in Zhao et al. 2010 Tran-Dine et al. 2019
min [(x) = 1 Σ e (o) + 1
(8)
where {ai} E Rd, E {-1,1), X 0 is an fg-regularization parameter, and the function is defined as
2
((x, u) =
1 + exp( -ay)
All datasets are downloaded from LIBSVM (Chang & Lin 2011). mation is provided in the following Table 3
The summary of datasets infor-
Table 3: Metadata of datasets
Dataset
n (# of datapoints)
(# of features)
a9a
32561
123
abalone
4177
mg
1385
mushrooms
8124
112
phishing
11055
68
pyrim
74
27
triazines
186
60
w8a
49749
300
A.2 EXPERIMENTS FOR THE DISTRIBUTED SETTING
Before presenting the experimental results in the distributed setting 2). we also need a distributed variant of SARAH-type methods in order to compare with our distributed variant of ZeroSARAH. Here describe one possible version in Algorithm Note that distributed SARAH also requires to periodically computes full gradients (see Line of Algorithm but not required by our D-ZeroSARAH (Algorithm 3.
order to mimic distributed setup, we represented clients as parallel processes. We implement the training process using Python 3.8.8, mpi4py library. We run it the workstation with 48 Cores, Intel(R) Xcon(R) Gold 6246 CPU @ 3.30GHz. We partition the dataset among 10 threads; having
M datapoints and clients, k-thread gets datapoints in range k| M +J+1,.... (I: 1) M In of a M
+ 1 < M. datapoints n 1.... .... M are ignored.
12

---

Under review as a conference paper at ICLR 2022
Algorithm 4 Distributed SARAH-type methods (one possible version)
Input: initial point x0, epoch length 1, stepsize 7), client minibatch size s, data minibatch size
I: -x"
2: for k= -, do
3: i mod / then
4: for each client i E [l...., n do
5:
Compute full gradient of each client: of m Σ (x)
vf((a*)
6:
end for
7:
0²
9
I/ full gradient computations
8:
else
9:
Randomly sample a subset of clients S from n clients with size | for each client E S* do Sample minibatch 7 of size ||,²| = b (from the m data samples in client i) Compute the local minibatch gradient information:
10:
12:
giecmr = Σ (aa jELt
and ff.prev = 8 Σ (aaa(at11)
jEl
end for
14:
th = Σ
(of.curr - skppoo)) + e
iESt
15: end if
16:
x k++1
= x ok
17: end for
nBa
plathing
mistrooms
21-1
Dew SARAR
26-1
Crlan
12-1
12-91
2103
1909
20
1996
1993
395
206
200
16-1
Performance between distributed SARAH and distributed ZeroSARAH under different datasets (columns). We show convergence using the theoretical stepsize in red lines; in blue lines, we scale it by factor x3; in green lines, we scale by factor x9.
Figure 2:
In Figure 2, we present numerical results for the distributed setting. The solid lines and dashed lines denote the distributed ZeroSARAH and distributed SARAH, respectively. Regrading the parameter settings, we also use the theoretical values according to the theorems or corollaries. In particular, from Tran-Dinh et al. (019)), we know that the smoothness constant L Rs 0.15405 max; ||a,]]
for objective function g). We choose the regularizer parameter to be = 0. 0.154405-00- max; ||a]1|2 In order obtain comparable plots similar to the standard/cennrralized setting (Figure []. also use multiple stepsizes. We choose the theoretical stepsize from Corollary (i.e., (1+V8)L) scaled by factors of 1 (red curves), x3 (blue curves), x9 (green curves), respectively.
Remark: Similar to Figure I the experimental results Figure also validate our theoretical
convergence results (distributed ZeroSARAH (D-ZeroSARAH) can be slightly better than distributed SARAH (see T) and confirm the practical superiority of D-ZeroSÁRAH (avoid any full gradi- ent computations) for the distributed setting (
13

---

Under review as a conference paper at ICLR 2022
B MISSING PROOFS FOR ZeroSARAH
In this appendix, we provide the missing proofs for the standard nonconvex setting ! provide the detailed proofs for Theorem D and Corollaries I of ZeroSARAH in Section 4
Concretely,
B.1 PROOF OF THEOREM
1
First, we need useful lemma in Li et al. (2021) which describes the relation between the function values after and before gradient descent step.
Lemma (Li et al. 2021)) Suppose that function f is L-smooth and let x = x² na Then for any 2h E Rddh and > O, we have
[(xht1) ((x
mk IV [V
1
1 1
1=112
7l 11
27p
Then, we provide the following Lemma to bound the last variance term of
(
Lemma Suppose that Assumption holds.
The gradient estimator v defined Line of
Algorithm 2
then we have
2L
ExIle* Vf(a*
5 1 b- V (f(x )|2
11 x 113
bi
21 by
V (x*
112
(10)
Proof of Lemma 2 First, according to the gradient estimator oe of ZeroSARAH (see Line of
Algorithm 2. we know that
n
2
(Vf((a*) - + (1 xa)x*-1 + >x by 1E
Σ
(Vii(a*=11)
- 11 1) + Σ yソ
bk
71 j=1
tE
(11)
Now bound the variance follows:
[ll *
)l
E
(Vf((*))
vf((zh-1)) + (11 - At)
by
SEI
(Vfi(a 11 + Σ
1ラ - vf v)(at)]
+ A
bk
j=1
1
Es
-
( - vf(()-11)) + v - + (1 - -w ()(a)111)
bs
A1
1 Σ (V/((>+11) 1 Σ
n
k-1 v
bE iET
j=1
Es
(Via(**) - vS(()=11)) + (
by EE
+ > by Σ (vf.(a+-1) - 1 + 1 k-1 (((aa11)
Σ
n 1=1
sEl7
(1 >1.)2111 (5(
14

---

Under review as a conference paper at ICLR 2022
S 2
Σ (Vii(=*)) V[i(a=-1)) + -
bk
iE
1 Σ
(Vii(x+-1) - 1イ + -
Σ yラ 3 V (((04-1)
+ 2
bE iE
==1
+ (1 \
212 bk
2
|
x= 11-1
+
Vfz(2 - زタ - 112 + (1 11 - -Vf(== ))?
bk
(12)
where (2) uses the L-smoothness Assumption 1 and the fact that [||| Er [|2] S |||| | for any random variable x.
To deal with the last term of TTO. use the following Lemma
Lemma 3 Suppose that Assumption I holds. The update of {ul is defined in Line of Algorithm then we have, for V3k > 0.
1 E&
- s (1 (1- bk ) Bka) n
1
[fz(*=11)
- 112
n
bk (1+
1.21
L
- 112
(13)
BK
Proof of Lemma 3
According to the update of {ut)} (see Line of Algorithm
2 we have
E
[V 1
bk
[+)() - 112
(14)
(1 bk 1
[ Vis(at + {f - 2/ 11
(1 bk (1 3K)
Σ [V
n
11- + (1 by (1 +
1
1,21,a )
- 2 (15)
where 14) uses the update of {y.] } (see Line 7 of Algorithm 2 and 15) uses Young's inequality
and T-smoothness Assumption
Now we combine Lemmas (i.e.,
and 13 to prove Theorem |
Proof of Theorem!
1 First, we take expectation obtain
((a - 1r + (1x
Th / 1l1 -\f(t))12 + 2m
1
2 1/) ||, - 1312 -2
+ ask
1
Σ
(1z(a*) - -,,,11
n ==1
E f f - Th
V )2 112 + 71 - Ax) 21)) V vf(ckt11)11
2
2
+ bn
1| - 111
[ - 23 1112
by ==1
+ 104(1
b
bk )1
1
2
1|
1 + au (1
by [1 + 3x)
1
V
f
k-
53 112
n
3a
n
7
15

---

Under review as a conference paper at ICLR 2022
R
[aah) - ---
77
||
+ 7x(11 - -VS
2
+
22
+ +ax(1
bk [1 + 3k
)L²) 1|= 11
bn
+
22
+ axk
be ) + Bx))
a Σ
1
n
[
- 1/ -13
(16)
by
n
n j=1
Now we choose appropriate parameters. Let 7/k = Uk-1 and 7h S 1 1, then 7/t (1 - Axx)² - 7 = Pu
2nE
2 Let 3x
2n' 0r = 2nAum and ag S -0k-1, we have 2 + a (1 - 4/2 (1 + 3x) S ak-1-
6%
by
We also have
27.4²
be + ax be
(1 + 3x
1 S 2 by further letting stepsize
n
1
Mパ-1 S
(17)
L(1 + MM²)
where M₁ := 2
+
8Aam" 2
beb
62
Summing up (66 from k= = 11o - 1, we get
K-1
0 < E [xx1) -
m
17 - 21)3
2
221
b )1 +
2m ) ||ا - 1212
+
+ ta1(1-
61
bi
dP
bj
b1
1 n
+
aa
)1 +
[ - -
(18)
61
n
2n
n
For = 0, we directly uses i.e.
B[f(=')- - 15 f(a") f
770
|| -
1
L
||
20112
+
nu
||000
vf(29))
2
2110
2
2
(19)
Now, we combine
18
and 19
to get
E
Σ
|
2
k=
< EE
f(x0)
fr + (11(1-111) -x1)2+ + 7o ))) 10000o-v// )2
-
2
a1 )1 + bi ) 1 Σ
(x)) - -111]]
(20)
bj
12
2n n ,=l
< E 5(2) f no(1 - -1a(1 - >11) -x1))
2nd no 1 Σ
1100 - vf((9))1
(f -|
2d1
b2
n
(21)
1 x2
< (E(1(2)) - -f 4*+0oll +7oll0" vf(29)]
+ aq
Σ
- 1
(22)
71
j=1
bo 1 a
- n
S SS(42) - 1 + 70 (n- - 1)bo n j=1
[ 2| + ao
Σ
|| (22)
(23)
n
5=1
= =1(2-) - 5r + (10 n hp
b
1
(n 11bb
+ aoo1
-
n
(24)
16

---

Under review as a conference paper at ICLR 2022
where (20 follows from the definition of nu in (7
21 uses
71
2
and
01
2n
bj
(2
holds by choosing 70 Z
Vin 2X1
2 dn
(n(1-A((1~An) and ao z
2n
no and 23 uses d = 1. By
2
bi
K-1 randomly choosing HKt from {x**)
k=o
with probability m//
11=
T) for
r
24
turns to
/|IVS/(** | 2(f(x)) )
2
(10
n n 60
+ ax
b0
(1}(2))
En= 1k
(n 1)b0
2( - (
(n bo + 2cxobo
1
[ff(2'))
(25)
Σ k= 4
nbn Σ K-1
k= I/K
n
B.2 PROOFS OF COROLLARIES 1 2
Now, we prove the detailed convergence results in Corollaries 2
with specific parameter settings.
Proof of Corollary L First we know that 25 with bg turns to
2(f(x)) --) f*)
(26)
Ek= 7l
Then if set A
by and by v for any k: 2 1, then we know that Me- Jebe 2n
8dnn
by
and thus the stepsize T)s S
1(1 (1+V8)L for any 2 O. By plugging v/ S (1+v8)L
into 26 we have
2(1+ + V8)L(f(x>) f*) =2
E ||
K
where the last equality holds by letting the number of iterations K 211+8))(1100-11 number of stochastic gradient computations is
Thus the
K-1
K
by = n+ (K- Sn+ 2( + (8)T -
#grad Σ
ba = bo
Σ
2
k=
k=1
Proof of Corollary]
First we recall 25
here:
2(f(#9) fr) fr)
(n (n- bo) + 220bb)
n
E[IVf(>>>1> |1 S
(27)
ΣK-1 17
nbo Ek=1 7
n
In this corollary, we do not compute any full gradients even for the initial point. set the minibatch
size by = /n for any k 2 0. So we need consider the second term of (27 since by vn is
not equal to n. Similar to Corollary
we set d 2n for any k 2 1, then we know that
Mr
SALn" and thus the stepsize 1/k S [1++
(1+ (1+V8)L for any k: 2 0. For
(1+v8)LVR It is easy to the second term, recall that " 2 Je va and an 2 2n 2λ, (1+v8)z
of
that Yo 2 agbo since by V I n. Now, we can change
2(1 + - 6(n Vn)
E
|
V11(20)12
K
nk
211 (1))(((()))) ) )r) 6Go
(28)
K
=2,
17

---

Under review as a conference paper at ICLR 2022
where (28) is due to the definition Go == 1 Σ |+*)) and the last equality holds by letting
the number of iterations K- 2[1+v8)[(f(u)) +66
Thus the number of stochastic gradient
computations is
K-1
2(1+ 2 - -r) - -Go = 00 v + Go) =
#grad
Σ by = Vnk= k=
=
c²
Note that Go can be bounded by Go S 2L(f(x²) - Po) via L-smoothness Assumption then wc have
#grad = 0 Vu(LAo + LĂO)
2²
Note that Do = f(xx) - fr, where f == ming f(x), and Do = f(x²) -r, where E min, f((x).
C MISSING PROOFS FOR D-ZeroSARAH
In this appendix, provide the missing proofs for the distributed nonconvex setting Concretely, we provide the detailed proofs for Theorem and Corollaries of D-ZeroSARAH Section
C.1 PROOF OF THEOREM
first recall the lemma Li al. 2021 which describes the change of function value after a gradient update step.
Similar to Appendix B.1
Lemma Li et al. for any t Rd and 1/2 > we huve
2021)) Suppose that function f is L-smooth and ler #+ == x² - -m Then
(
2 1
L.
11 +
2 llea V {( (29)
2
27k
Then, we provide the following Lemma to bound the last variance of (29).
Lemma
Suppose that Assumption holds. The gradient estimator a defined Line of then we have
Algorithm 3
2L2
ExIlb** V
(f(**-1)11
1| xk-111
s4bR
2X2
TLM
[Viis
Vi. 111
(30)
sg Tim
11=1,1
Proof of Lemma 4 First, according to the gradient estimator b of D-ZeroSARAH (see Line of Algorithm 3),
we know that
Σ (ot.amm (iprew)) + (1 A + Ak
1
(of V..pee) + A (31)
Sk
sk ve.s
$ES*
Now bound the variance follows:
[
31
(of.cum f..peee) + (1- -xa + Au
(of - -/..ree) ) + +3 + v v((xt)
1 Σ
Ex
(9f.cmm F.prew) v.f(at11)- (1- -
8k
SESA
18

---

Under review as a conference paper at ICLR 2022
Ak
1
(oipre Wi.prev) + + (
8k
iESt
1
Σ
(oficure skiprco) + V
8k iEsk
(1h.prev - VV..cco) ) + 1 V[(a 22
+ A
8k 1E9k
(1 )x)) P11 |1(
2Ek
Σ E
(a Vlag (/((x V V
iESt jE
+ 21 2
ΣΣ
(V (iss(* -(t + y (
skbb
iES* JEI
+ (1 Nx) 1112
\f(x
2L S4bb
2x
m,m
11.
k
112
[Vies(z - 111 1c)7111 (s(x
SybE
7m
11=11
(32)
where (32) uses the L-smoothness Assumption i.e. V V fi)(()) s L||x yll. and the
fact that E||l=- |x] < [|[]]]]]]] for any random variable
To deal with the last term in (3 we uses the following Lemma
Lemma 5 Suppose that Assumption 2 holds. The update of {utig} 3 is defined in Line of Algo-
rithm
3
then we have, for V3x+ > O,
subb
R,m
Eg
Σ
v/,
s 5(1-
(1 + 3k) nm
V
fr - Vi.j k- -12
nm
nm
1,=1,1
x.j 1.1
+ (1 saba
1
(1 +
2
- 111
(33)
B%
Proof of Lemma have
According the update of {utt}} } (see Line 7 and Line 11 of Algorithm 3),
Ex
[**))(***
112
TUTT
11==11
Sybkk
m.m
[&ts(a - "12
(34)
nm
nm
1,j=1.1
$ybb
(1
[V V.as( + ++VVee (z v.. 111
nm
1,11111
(1
sybb
(1 + 3x)
Σ
[ 1 + (1
suba )
(1
1
1.2
-
nm
nm
nm BL
(35)
where 34
uses the update of (v in Algorithm and 35 smoothness Assumption 2
uses Young's inequality and L-
Now combine Lemmas
and (i.e., 29
30 and 33 to prove Theorem
19

---

Under review as a conference paper at ICLR 2022
Proof of Theorem 2 First, we take expectation obtain
5 (1H - + (2 27k
1. )) |1 1t113
E
f f(at1))
[+a((**) - 112
+ ag nm 1,1=1,1
(aah) - - Tk (IV + 7x - 12))
<
22
2
n.m
11 11 +
Σ
| [iiss - 1 112
+ bg
8% bb
Tum
1,5=1,
scbk
1
+ +ax (g.(1
(1 +
L ||
112
11m
sEbK
+ +ax(1
+ Bax)
v 112
mmm
1,j=1,1
= E f(zt) ff - T2
[[Vf((")]1
+ +7x (1 - 2a)2 (f(c
2
+
(
+ + 122
(1 + 3/2
1 |1,2) )r,2)114 | - 11
skbb
nm
sabR
n.m
+
+
axe(1
(1 + Be))
Viss(0 - Vis 1//-112 (36)
sybb
mm
mm 1,1=1,1
Now we choose appropriate parameters. Let 7/k = 9h-1 and 7k S 7k then 7/ - (1 S 7k-1
2
mik-1 Let Se
sabr 2nm
2nmmAaT- and 0g S a we have
2 ax (1- sxbe ) (1 + Bax) S
sube
0--1- We also have
27 L²
+ oz SEDE ) (1 + 1 112 S 2mh
L by further letting stepsize
sabE
nm
nx
2
1
Tk-1 S L(1 + wWa)
(37)
where Wi = Ansebe
2
BAen" mm² 6262
Summing up 36 from k-
1 to K-
1, we get
K-1
1
0 < E f(x²) - 8"
Σ
7k
+ 21 1110 )1(2"))12
2
k=1
271 1
22
(1 + 211711
+ a (1
r.2) ||-t - 1012
sid1
nm!
+
27
+ +01(1-
rats
(1 + وودر
2nm
n.m Σ
VFas(()) - v25113
(38)
81b1
nm
mm 1,1=11
For h: = 0, we directly uses 29 i.e.
B[f(z') f4| s k f((") - fr
77u
[Vf(29)1
- 1
L ) ||
=0112+
+
nu
2/
||0 - {f(2))
2
2n10
2
(39)
Now, we combine
38
and 39
to get
K-1
E
2
2
O==
20

---

Under review as a conference paper at ICLR 2022
$ <E f(x") f + (m111 - + 2
)11e vf((2)11
2
+ 8161
2
+ ta1(1
51b1 (1 3
2nmm
Σ
(x) - -v2,11
(40)
mim
mm
1-ز=1,1
70(1 - -11(1 - A1l) 1100 - v5(20)11
s S S(x)
2
2nmd17m
8,3
[V
11
(41)
nm 8i
1,
$ 5((x)) 8 +
1/0
sobn Tim
7,m
2d1 (nm
s)sobu nm
11=11,1
2nmd1 nm
sodu 1
Σ [+
(42)
Tum
1,1=11
[xxx) / + (nm sobo)ao0
Go:
(43)
2nmss
where 44 follows from the definition of 170
uses 71
2
and a1
2nm
uses Xo = 1, and (43) uses the definitions Oo (nm 1)A1 +
Anm sody and G/
ff
=
nm f=1111 (x),(=
By randomly choosing x from J== with probability m// EK oe for w
443 turns
BiIVf(E*>1TL 2(f(x)) (nm lobo)moooGG
(44)
ΣkE nmnsobo Σk=0 Te
C.2 PROOFS OF COROLLARIES AND 4
Now, we prove the detailed convergence results in Corollaries 3
with specific parameter settings.
Proof of Corollary 3 First know that 44 with 8g and by turns
E
(45)
K-1 7
Then if we set Ag 8Ayn?m²
S4hy
= Vn, and by = m for any k 2 1, then we know that Wa. =
2nm
and thus the stepsize Vik S [11 ([1))
= (1+vB) for any k 2 0. By
Anseby by
plugging 7 S (1+V8)L into 45 we have
2(1 V8)L(((0)) -
|1
K
where the last equality holds by letting the number of iterations K = 211+vB number of stochastic gradient computations for each client is
Thus the
K-1
by m + (K-
1) S n
m 221 (8)L(f(=") f)) -*)
#grad
Σ k=
+
Vn
n
2
Proof of Corollary
First we recall 44 here:
2(f(x") - fr)
(nm Sob
|1
(46)
Σk-1 7l
nmsybo Ek-1
21

---

Under review as a conference paper at ICLR 2022
In this corollary, we do not compute any full gradients for the initial point. We set the client sample size Sy: yn and minibatch size by ym for any 2 0. So we need consider the
second term of (46) since spbp /nm is not equal to nm. Similar to Corollary if we set
sxbk for any 2 1, then we know that Wx == dK 2nm
An +
8A.n2m²
2 = 8 and thus the stepsize
p I z( ((11))
= (1+v3)L for any &o 2 O. Now, we can change 46 to
2(1 (8)((f(=)) --)
(nm sgba DO
E [
K
nmsoobo
2(1 + (8) fr) + 4G
(47)
K
=6,
where (47) holds by plugging the initial values of the parameters into the last term, and the last equality holds by letting the number of iterations K 2(++v))(((")--+++44 Thus the number of stochastic gradient computations for each client is
K-1 K Km
m 2(1 + (8)L(f(="))))))))))))))())()()))
4G = o(1 m LA Go
#grad
bk
vn
n
2²
22
k=
Note that Do = f(x0) f where f :- min f(x).
D FURTHER IMPROVEMENT FOR CONVERGENCE RESULTS
Note that all parameter settings, i.e., {mc). require the values of L and n, and {me), {sk {b J. {)a} } in D-ZeroSARAH for Corollanes only require the values of L, and m. both are the same as all previous algorithms. If one further
}. {ba} and {Ax in ZeroSARAH for Corollaries only
allows other values, e.g., Go Dg. for setting the initial bo. then the gradient complexity can be further improved. See Appendices D. a.2 better results of ZeroSARAH and D-ZeroSARAH, respectively.
D.1 BETTER RESULT FOR ZeroSARAH
Corollary' Suppose that Assumption holds. Choose stepsize 1jk S (1+v5)L for any k: 2 0, mini-
batch size bk / and parameter A by for any k 2 1. Moreover, let bo min {v nGo and An = 1. Then ZeroSARAH (Algorithm 2 can find an e-approximate solution for problem such that
ElIV E
and the number of stochastic gradient computations can be bounded by
#grad = =0( -
LAo min
Go (Va..v)))
Similarly, Go can be bounded by Go < 2LD, via Assumption we also have
Let bn = min {
nr.. p
n3. then
#grad = =0 =0(v
LAn 2
min { vnt))
Lbo
The result of Corollary 5 for ZeroSARAH is the best one compared with Corollaries 1 In particular, it recovers Corollary when by = n. In the case by < n (never computes any full gradients even for the initial point), then #grad o ( result 0 vm(LAn+Go) in Corollary Similar to the Remark after Corollary if we consider L,
Remark:
which is better than the
22

---

Under review as a conference paper at ICLR 2022
Au. Go Ån constant values then the stochastic gradient complexity in Corollary i #grad O( )"), ) i.e., full gradient computations do not appear in ZeroSARAH and the term 'n' also does not appear in its convergence result. If we further assume that loss functions fi's non-negative, i.e., Vx, (a:) 0 (usually the case in practice), we simply bound Do == f(x²) f S f(x and
then by can be set as min
aL.((a)) for Corollary
Proof of Corollary 5
First we recall 25 here:
(n- 64- + 200bo) 1
B(IVS )1
(+)())) j=1
(48)
Σk=o
nbo Ex= 7
Note that here we also need consider the second term of (48 since by may be less than n. Similar to Corollary 2 if we set A = by
and by = vn for any k 2 1, then we know that Ms ==
2n
SAg
and thus the stepsize 7ト S 1(1+V M411)
(1+V8)L for any k 2 0. For the
Anbb
second term, we recall that To 2
vn and oo 2 that 7o andu since bu I Now, (I+v8)T.
No
2n
easy to see
2X1
bi
(1+V8)
change 44 to 2(1 + (B)L(f(=))) f*) |
6(n bo) Σ [+
Vnbol
2(1+ ((fx( f*)
6(n - Go)
(49)
Vnbo
2
where 449 is due to the definition Go = E Li=1
|/('')1 and the last equality holds by letting (1++8)1(((a))
the number of iterations K gradient computations is
6(n-bo)Oo Thus the number of stochastic Vūbge"
K-1
K-1
#grad
by
bo +
bk
k=0
k=1
2(1 (8)/TL(((()) -
6(n Go)
= bo + (K 11)1 by
2
bnc
nCa _ n we have By choosing bo min(y
#grad < vn
2(1 + (8)
+ min {ov
Go
vnn
62
2
= -0(vin I.D min 1 {V (2ovvnt))
Similarly, Gp can be bounded by Go s 2l(f(x0) - fr) via Assumption and by
no minty 2 nn, then we have
#grad = 0 ( LAu
ما min {V e _,, vut))
Note that Ao = f(x0) fr, where f" == ming f(x), and Do = f(x²) - Jr. where f
D min, f((x).
D.2 BETTER RESULT FOR D-ZeroSARAH
Corollary 6 Suppose that Assumption holds. Choose stepsize ml < (1+v8)L for any k 2 0.
clients subset size 8k .n, minibatch size by vmn and parameter A
bubg 2nm
for any k 1.
23

---

Under review as a conference paper at ICLR 2022
Moreover, let 8o min {v and X = Then D D-ZeroSARAH (Algorithm 3 can find an e-approximate solution for distributed
nayy me²; nj and bo m (or bu min { mc ne² , and so n),
problem such that
E )1 2
and the number of stochastic gradient computations for each client can be bounded by
#grad =oadd=0(1
T.oo min (2.vm)))
n
Proof of Corollary 6 First recall (4
here: (nm sobo) Oo
2(f(x") -M)
|1
(50)
Σ 7/
rmmspbo > k== mB
Similar to Corollary here we also need consider the second term of (50) since sydo may be less saba, 2nm 8 = Vn, and by = vn for any 2 1, then we know that
than nm. Similarly, if we set 2
We
and thus the stepsize yi b(1+tWez.)
for any k: 2 0.
Ausabe
(1+V8)7
Then 500 changes
2(1 + (B)((((>)) - -M*)
E
K
nmsobuk
2(1 + v8) L((()) PT)
6(nm 80b0 0%
(51)
K
Vnmssbo
=
where (5T) by figuring out Og with the initial values of the parameters, and the last equality holds by letting the number of iterations K 20+ 20+v8)[((())/1 ((nm-eebu)GG, Thus the number of stochastic gradient computations for each client
Vamsobbrr"
K K-1
80 bo (K 1)/m
#grad
Σ k=0
by
+
n
Vn
2(1 + (8))(f(29)-)) -
soba + 6(am - sobo) Sobo-'
n
2
nsobne?
m
Go 2(1 + (8)L(((>)) - ( + min {TV
e vnmb)
(52)
(1
m
I.Do
Go
Vnm }))
+ min
{V
e²
holds by choosing sobp = min {v
nmCh
where 52
mmm {
It can be satisfied by letting 8p
min me? n and bn m (or 80 = n and by min
mGy
m)) The last equation uses the net
definition Do = fxx0) f where f" = min, ((x).
24


Reviews:
[{"review_id": "SvHaDYV65J7", "reviewer": "Reviewer_qPn9", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "1. The authors say in the abstract, intro and conclusion that \"their complexity improves existing ones in current regimes\", but I cannot see this written down explicitly. The closest I can find is the Remark after Corol. 2 that states \"if G_0, \\hat \\Delta_0\" are constants, which is obviously a too much of a simplification and also not true in most cases. For example, why is $\\hat \\Delta_0$ is even finite? Assuming the objective is lower bounded is a common assumption, but of course each component can be without a lower bound (take linear functions. Their sum can lower bounded whereas they individually are not). Then what will happen to $\\hat \\Delta_0$?\n\n2. Due to my previous point, it is not clear if it is possible to give a fair comparison between the current complexity and previous best complexity. The new complexities depend on $G_0, \\hat \\Delta_0$ and their relation to the other terms is quite unclear.\n\n3. In the experiments, only comparison is with SARAH which is insufficient. Since one of the main motivations of the paper is distributed optimization, I think the authors need to compare with the algorithms from Table 2, for example SCAFFOLD, or other SOTA algorithms in this setting to see if the new method is really useful in practice.\n\n4. Please define $\\hat x_K$ either in the algorithm or the theorem/corollaries. I had to check the proof to see how it is defined.\n\nI am of course open to increase my score if my concerns in 1,2,3 are addressed.", "summary_of_the_paper": "This paper introduce ZeroSARAH which is a variant of variance reduced SARAH algorithm, for solving $\\min_x 1/n \\sum_{i=1}^n f_i(x)$ with nonconvex and smooth $f_i$. ZeroSARAH and its distributed version are the first algorithms that do not require any full gradient computations. Most algorithms for this setting either required computing the full gradient once in the beginning or periodically. The paper also argues that in distributed optimization, computation of full gradients can be a bottleneck and therefore avoiding it is important.\n", "summary_of_the_review": "Overall, I agree that an algorithm with zero full gradient computation is definitely interesting, it is not clear if this brings any advantage in theory (due to different parameters in the bounds) and also in practice (experiments are only compared to SARAH and not with the SOTA solvers in distributed settings.)", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Np7V6s5mdQr", "reviewer": "Reviewer_xTXr", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "The paper first presents ZeroSARAH, which slightly modifies SARAH in the sense that ZeroSARAH replaces the past gradient estimator $v^{k-1}$ of SARAH with the weighted sum of $v^{k-1}$ and another estimator to avoid the periodic computation of the full gradient. The technique is definitely new, but still a bit incremental. \n\n\nIn the centralized setting (ZeroSARAH), the authors establish the ZeroSARAH's complexity of $O(n+\\frac{\\sqrt{n} L \\Delta_0}{\\epsilon^2})$ or $O(\\frac{\\sqrt{n} (L \\Delta_0+G_0)}{\\epsilon^2})$ versus $O(n+\\frac{\\sqrt{n} L \\Delta_0}{\\epsilon^2})$ of SARAH. The term $n$ in SARAH just means that you must run at least one iteration of the algorithm [1], which takes the full gradient snapshot, and is usually dominated by the other term due to the large condition numbers in practice. Therefore, the complexity achieved by ZeroSARAH is essentially comparable to SARAH's, where $O(\\frac{\\sqrt{n} (L \\Delta_0+G_0)}{\\epsilon^2})$ can be seen as the interpretation of the fact that no full gradient computation is needed. However, in this centralized setting, avoiding full gradient computation does not provide any real benefit. ZeroSARAH still serves as the basis for the development of D-ZeroSARAH for distributed setting where avoidance of full gradient computation can be beneficial.\n\n\nIn the distributed setting (D-ZeroSARAH), the complexities established for D-ZeroSARAH are comparable to distributed Sarah, which follows the same reasons as above. The main benefit of D-ZeroSARAH is the fact that it does not require full gradient computation, which can alleviate the burden of synchronizing all clients. This is an interesting perspective that has not been widely considered yet. Nevertheless, since both D-ZeroSARAH and distributed Sarah have the same gradient complexity $O(\\sqrt{\\frac{m}{n}} \\frac{1}{\\epsilon^2})$ and D-ZeroSARAH requires less gradient evaluations per iterations, the number of iterations, i.e. communication rounds, required by D-ZeroSARAH is more than by SARAH. The communication complexity (i.e. communication rounds) is one of the most common metrics considered by the distributed optimization literature, which also corresponds to the fact that setting up a synchronization round is expensive in practice. All in all, D-ZeroSARAH can be viewed as a variant of distributed SARAH with reasonable tradeoffs in number of gradient computations per iteration and communication complexity. Perhaps the authors can add some discussion on communication complexity. \n\nExtensive experiments for both of ZeroSARAH and D-ZeroSARAH were conducted to verify the theories and robustness of the proposed methods. \n\n\nTypos/Mismatch: In Corollary 3, the parameter is set such that $b_k= \\sqrt{m}$, but in its proof it seems that $b_k=\\sqrt{m/n}$. \n\n\n\n\n\n[1] Pham, Nhan H., Lam M. Nguyen, D. Phan and Quoc Tran-Dinh. “ProxSARAH: An Efficient Algorithmic Framework for Stochastic Composite Nonconvex Optimization.” ArXiv abs/1902.05679 (2020).", "summary_of_the_paper": "The paper proposes ZeroSARAH (and its distributed version D-ZeroSARAH), a variant of the well-known variance-reduced method SARAH, for non convex finite-sum optimization. The main benefit of ZeroSARAH and D-ZeroSARAH is that they do not require any full gradient computations, in contrast to other known variance reduction algorithms. In distributed setting, this can avoid the burden of synchronizing all clients. ", "summary_of_the_review": "Overall, the paper proposes ZeroSARAH and its distributed version D-ZeroSARAH, as variants of SARAH that avoid full gradient computation. Under the distributed setting (where such feature can be beneficial), requiring less number of gradient computations per iteration means that D-ZeroSARAH requires more iterations, i.e. communication rounds, than distributed SARAH to converge, since the  gradient complexity of these 2 algorithms are asymptotically the same. This provides some interesting tradeoffs, but in general, communication complexity is usually more prioritized in practice. D-ZeroSARAH can address certain situations where synchronizing all clients is impractical. This is a new perspective for this class of problems and can facilitate future work in this direction. The proposed methods are empirically validated. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Go488VdsqiA", "reviewer": "Reviewer_bVt3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "- The authors propose ZeroSARAH and its variant for distributed framework. They highlight that \"Avoiding any full gradient computations is important especially in this distributed setting, periodic computation of full gradient across all n clients may be impossible or unaffordable.\" Furthermore, \"the main advantage of (their) algorithms is that they do not need to compute any full gradients\".\n\n- However, ZeroSARAH needs a group of auxiliary variables $y_i^k$ for $i= 1,\\dots, n$ and $k = 0,1,2,\\dots$. I find it surprising when the authors did not discuss these variables in the description of Algorithm 2 (Section 4.1). The update in line 5 in fact requires us to compute the summation of $n$ such variables $\\sum_{j=1}^n y_j^{k-1}$, which is relatively similar to computing the full gradient. Again, I am surprised that the authors did not discuss the storage cost needed for ZeroSARAH. From my understanding, this algorithm needs to keep a table of past gradients in the auxiliary variables $y_i^k$, and at the moment I can not find a solution to get rid of this storage cost. For that reason, it is reasonable that your algorithm does not need many full gradient computations while still achieves the same state-of-the-art rate. I recommend that the authors discuss your method with SAG/SAGA where these methods also need to store a table of past gradients. \n\n- Similarly in the distributed setting, although we don't need a full gradient, we still need to compute a sum of $n$ variables (Line 11 of Algorithm 3). Hence this may slow down the training process no matter the fact that we don't collect every gradient. \n\n- For these reasons above, I do not see that ZeroSARAH has any major advantage over existing works. Please note that not every VR method needs to compute full gradients. For example, the reference [Inexact SARAH Algorithm for Stochastic Optimization] (Nguyen et al, 2020) only compute a mini-batch gradient in the training process. This should be added and discussed in this paper.\n\n- The authors might want to edit some statements that could be confusing/misleading. For example, the statement \"all existing variance-reduced methods, including SARAH, SVRG, SAGA and their variants, need to compute the full gradient\" while \"SCSG (Lei et al., 2017), SVRG+ (Li & Li, 2018), PAGE (Li et al., 2021)) may avoid full gradient computations by using a large minibatch of stochastic gradients instead\". Also the statement \"(our methods) improve the previous best-known result\" is also misleading.\n\n- A minor point: the authors might want to specify the output $\\hat{x}^K$ in the main paper.", "summary_of_the_paper": "The authors propose a variance-reduced algorithm ZeroSARAH for solving the nonconvex finite-sum problems. They also propose a distributed variant D-ZeroSARAH for the corresponding distributed framework. They provide the state-of-the-art convergence results for these methods using standard assumptions. The authors claim that both methods does not require computing full gradients, which gives a major advantage when the number of samples $n$ is large. They further validate ZeroSARAH using nonconvex linear regression and binary classification for neural networks.", "summary_of_the_review": "The authors present a new method named ZeroSARAH where the main advantage is that they do not need to compute any full gradients. However this algorithms may requires more storage/computational cost than the previous methods that use minibatch to update. Therefore I do not see any advantage and do not support publication at the moment when these issues are unresolved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "AuWAZuXr4qr", "reviewer": "Reviewer_YmLP", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "Overall it's a nice method and I don't see anything wrong with the proofs (though I really only skimmed). My main counterthought is that the paper didn't really address SAG and SAGA, which are other mainstream VR methods that also do not require full gradient calls, do not even require full minibatch computations, and also have competitive convergence rates. The downside of SAG and SAGA seem to be the same as this method, which is the high memory cost; the need to store the yi's seems to be similar to the issues of SAG and SAGA. As it stands, having such a high memory cost in general makes these methods prohibitive to most deep learning applications, and is on the same order of \"issues\" as SVRG.\n\nThe other (maybe not that minor) thing is that, the authors say that although minibatch versions of SVRG and such methods exist, their convergence depends on bounding the variance of the stochastic gradients, which it is true is hard in general. However, this is necessary for the proofs of ALL VR methods, not just the minibatched versions. It seems like the authors bypassed this issue via telescoping, so perhaps it just isn't an issue with SARAH. But I don't believe this is somehow a new issue with minibatching to estimate the stale full gradient, is my point. ", "summary_of_the_paper": "This paper introduces a form of SARAH (the variance reduction method)  that avoids taking full gradients, which is called ZeroSARAH, and also a distributed version (D-ZeroSARAH). They offer convergence results and shows that it is on the same order of gradient calls to $$\\epsilon$$-gradient norm as other state-of-the-art variance reduction methods, but claim it is without ever requiring full gradients.\n\n", "summary_of_the_review": "See above", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There are many discussions among the reviewers for this paper and eventually none of the reviewers (including the one who gave most positive score) would like to support the publication of this paper. 

Some concerns from the reviewers are as follows:
1. Missing the discussion on storage cost. 
2. The improvement is limited. $G_0$ must be small and independent of $n$, hence it is not clear if it is possible to give a fair comparison between the current complexity and previous best complexity. 
3. Missing the discussion on the case when $n \leq \mathcal{O}(\varepsilon^{-4})$ of the state-the-art results. 
4. For the complexity results in terms of $\varepsilon$, it requires $\varepsilon$ to be arbitrarily small. The authors should also discuss this point for comparing with their result. 
5. Some other statements in the papers are overclaimed. 

Please take the comments and suggestions from the reviewers carefully to revise the paper for the future venues since they raised valid points.
Decision: Reject