ZeroSARAH: EFFICIENT NONCONVEX FINITE-SUM OPTIMIZATION WITH ZERO FULL GRADIENT COMPU-
Year: 2021

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 1 n ∑n i=1 fi(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, 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 vs. n/ . Thus we focus on the variant of SARAH. The proposed ZeroSARAH and its distributed variant D-ZeroSARAH are the first variance-reduced algorithms which 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.

text: ∑n i=1 fi(x). To the best of our knowledge, in this noncon-
vex 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 x0, 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: n2/3/ 2 vs. n1/2/ 2. Thus we focus on the variant of SARAH. The proposed ZeroSARAH and its distributed variant D-ZeroSARAH are the first variance-reduced algorithms which 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.

heading: 1 INTRODUCTION
text: 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
min x∈Rd
{ f(x) := 1
n n∑ i=1 fi(x)
} , (1)
where f : Rd → R is a differentiable and possibly nonconvex function. Problem (1) captures the standard empirical risk minimization problems in machine learning (Shalev-Shwartz & Ben-David, 2014). There are n data samples and fi denotes the loss associated with i-th data sample. We assume the functions fi : Rd → R for all i ∈ [n] := {1, 2, . . . , n} are also differentiable and possibly nonconvex functions.
Beyond the standard/centralized problem (1), we further consider the distributed/federated nonconvex problems:
min x∈Rd
{ f(x) := 1
n n∑ i=1 fi(x)
} , fi(x) := 1
m m∑ j=1 fi,j(x), (2)
where n denotes the number of clients/devices/machines, fi 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 or very hard to achieve.
There has been extensive research in designing first-order (gradient-type) methods for solving centralized/distributed nonconvex problems (1) and (2) such as 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 et al., 2017; Li & Li, 2018; Zhou et al., 2018; Fang et al., 2018; Wang et al., 2018; Ge et al., 2019; Pham et al., 2019; Li, 2019; Li & Richtárik, 2020; Horváth et al., 2020; Li et al., 2021). Note that SVRG and SAGA variants typically achieve weaker convergence results than SARAH variants, i.e., n2/3/ 2 vs. √ n/ 2. Thus the current best convergence results are achieved by SARAH variants such as SPIDER (Fang et al., 2018), SARAH (Pham et al., 2019) and PAGE (Li et al., 2021; Li, 2021).
However, all of these variance-reduced algorithms (no matter based on SVRG, SAGA or SARAH) require full gradient computations (i.e., compute ∇f(x) = 1n ∑n i=1∇fi(x)) without assuming additional assumptions except standard L-smoothness assumptions. We would like to point out that under an additional bounded variance assumption (e.g., Ei[‖∇fi(x) −∇f(x)‖2] ≤ σ2, ∀x ∈ Rd), some of them (such as 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 (usually the minibatch size is O(σ2/ 2)). Clearly, there exist some drawbacks: i) σ2 usually is not known; ii) if the target error is very small (defined as E[‖∇f(x̂)‖2] ≤ 2 in Definition 1) or σ is very large, then the minibatch size O(σ2/ 2) is still very large for replacing full gradient computations.
In this paper, we only consider algorithms under the standard L-smoothness assumptions, without assuming any other additional assumptions (such as 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 n data samples at the initial point x0, and then periodically compute the full gradient once every few iterations (for SVRG, SARAH and their variants). However, full gradient computations are time-consuming steps in many applications as the number of data samples n usually is very large. Especially in the distributed setting, periodic computation of full gradient needs to periodically synchronize all clients/devices, which usually is impractical. Motivated by this, we focus on designing new algorithms which do not require any full gradient computations for solving standard and distributed nonconvex problems (1)–(2).

heading: 2 OUR CONTRIBUTIONS
text: In this paper, we propose the first variance-reduced algorithm ZeroSARAH (and also its distributed variant D-ZeroSARAH) without computing any full gradients for solving both standard and distributed nonconvex finite-sum problems (1)–(2). Moreover, ZeroSARAH and Distributed D-ZeroSARAH can obtain new state-of-the-art convergence results which improve previous bestknown results (given by e.g., SPIDER, SARAH and PAGE) in certain regimes (see Tables 1–2 for the comparison with previous algorithms). ZeroSARAH is formally described in Algorithm 2, which is a 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 3 of Section 5, which is a 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–3 or Tables 1–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 ZeroSARAH/D-ZeroSARAH 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 + √ nL∆0 2 ) (see Table 1 or Corollary 1), and also provide new state-of-the-art convergence results without any
full gradient computations (see Table 1 or Corollary 2) which can improve the previous best result in certain regimes.
• Besides, for the distributed nonconvex setting (2), the distributed D-ZeroSARAH (Algorithm 3) enjoys similar benefits as our ZeroSARAH, i.e., D-ZeroSARAH does not need to periodically synchronize all n clients to compute any full gradients, and also provides new state-of-the-art convergence results. See Table 2 and Section 5 for more details.
• Finally, the experimental results in Section 6 show that ZeroSARAH is slightly better than the previous state-of-the-art 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 l iterations (here l = √ n). Thus the experiments validate our theoretical results (can be slightly better than SARAH (see Table 1)) and confirm the practical superiority of ZeroSARAH (avoid any full gradient computations). Similar experimental results of D-ZeroSARAH for the distributed setting are provided in Appendix A.2.

heading: 3 PRELIMINARIES
text: Notation: Let [n] denote the set {1, 2, · · · , n} and ‖ · ‖ denote the Euclidean norm for a vector and the spectral norm for a matrix. Let 〈u, v〉 denote the inner product of two vectors u and v. We use O(·) and Ω(·) to hide the absolute constant, and Õ(·) to hide the logarithmic factor. We will write ∆0 := f(x0) − f∗, f∗ := minx∈Rd f(x), G0 := 1n ∑n i=1 ‖∇fi(x0)‖2, ∆̂0 := f(x0) − f̂∗,
f̂∗ := 1n ∑n i=1 minx∈Rd fi(x) and G ′ 0 := 1 nm ∑n,m i,j=1,1 ‖∇fi,j(x0)‖2.
Definition 1 A point x̂ is called an -approximate solution for nonconvex problems (1) and (2) if E[‖∇f(x̂)‖2] ≤ 2.
To show the convergence results, we assume the following standard smoothness assumption for nonconvex problems (1).
Assumption 1 (L-smoothness) A function fi : Rd → R is L-smooth if ∃L > 0, such that ‖∇fi(x)−∇fi(y)‖ ≤ L‖x− y‖, ∀x, y ∈ Rd. (3)
It is easy to see that f(x) = 1n ∑n i=1 fi(x) is also L-smooth under Assumption 1. We can also relax Assumption 1 by defining Li-smoothness for each fi. Then if we further define the average L2 := 1n ∑n i=1 L 2 i , we know that f(x) = 1 n ∑n i=1 fi(x) is also L-smooth. Here we use the same L just for simple representation.
For the distributed nonconvex problems (2), we use the following Assumption 2 instead of Assumption 1. Similarly, we can also relax it by defining Li,j-smoothness for different fi,j . Here we use the same L just for simple representation.
Assumption 2 (L-smoothness) A function fi,j : Rd → R is L-smooth if ∃L > 0, such that ‖∇fi,j(x)−∇fi,j(y)‖ ≤ L‖x− y‖, ∀x, y ∈ Rd. (4)
Algorithm 1 SARAH (Nguyen et al., 2017; Pham et al., 2019) Input: initial point x0, epoch length l, stepsize η, minibatch size b 1: x̃ = x0
2: for s = 0, 1, 2, . . . do 3: x0 = x̃
4: v0 = ∇f(x0) = 1n n∑ i=1 ∇fi(x0) // compute the full gradient once for every l iterations 5: x1 = x0 − ηv0 6: for k = 1, 2, . . . , l do 7: Randomly sample a minibatch data samples Ib with |Ib| = b 8: vk = 1b ∑ i∈Ib ( ∇fi(xk)−∇fi(xk−1) ) + vk−1
9: xk+1 = xk − ηvk 10: end for 11: x̃ randomly chosen from {xk}k∈[l] or x̃ = xl+1 12: end for
Algorithm 2 SARAH without full gradient computations (ZeroSARAH) Input: initial point x0, stepsize {ηk}, minibatch size {bk}, parameter {λk} 1: x−1 = x0
2: v−1 = 0, y−11 = y −1 2 = · · · = y−1n = 0 // no full gradient computation 3: for k = 0, 1, 2, . . . do 4: Randomly sample a minibatch data samples Ikb with |Ikb | = bk 5: vk = 1bk
∑ i∈Ikb ( ∇fi(xk)−∇fi(xk−1) ) +(1− λk)vk−1 + λk ( 1 bk ∑ i∈Ikb ( ∇fi(xk−1)− yk−1i ) + 1n n∑ j=1 yk−1j ) // no full gradient computations for vks
6: xk+1 = xk − ηkvk
7: yki = { ∇fi(xk) for i ∈ Ikb yk−1i for i /∈ Ikb // the update of {yki } directly follows from the stochastic gradients computed in Line 5 8: end for
4 ZeroSARAH ALGORITHM AND ITS CONVERGENCE RESULTS
In this section, we consider the standard/centralized nonconvex problems (1). The distributed setting (2) is considered in the following Section 5.
4.1 ZeroSARAH ALGORITHM
We first describe the proposed ZeroSARAH in Algorithm 2, which is a variant of SARAH (Nguyen et al., 2017). To better compare with SARAH and ZeroSARAH, we also recall the original SARAH in Algorithm 1.
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 1). However, ZeroSARAH combines the past gradient estimator vk−1 with another estimator to avoid periodically computing the full gradient. See the difference between Line 8 of Algorithm 1 and Line 5 of Algorithm 2 (also highlighted with blue color).
• The gradient estimator vk in ZeroSARAH (Line 5 of Algorithm 2) does not require more stochastic gradient computations compared with vk in SARAH (Line 8 of Algorithm 1) if the minibatch size bk = b.
• The new gradient estimator vk of ZeroSARAH also leads to simpler algorithmic structure, i.e., single-loop in ZeroSARAH vs. double-loop in SARAH.
•Moreover, the difference of gradient estimator vk also leads to different results in expectation, i.e., 1) for SARAH: Ek[vk −∇f(xk)] = vk−1 −∇f(xk−1); 2) for ZeroSARAH: Ek[vk −∇f(xk)] = (1− λk)(vk−1 −∇f(xk−1)).
4.2 CONVERGENCE RESULTS FOR ZeroSARAH
Now, we present the main convergence theorem (Theorem 1) of ZeroSARAH (Algorithm 2) for solving nonconvex finite-sum problems (1). 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 1–2 in Table 1 for comparing with convergence results of previous works. Theorem 1 Suppose that Assumption 1 holds. Choose stepsize ηk ≤ 1 L ( 1+ √ Mk+1
) for any k ≥ 0, where Mk+1 := 2λk+1bk+1 + 8λk+1n 2 b3k+1 . Moreover, let λ0 = 1, γ0 ≥ η02λ1 and α0 ≥ 2nλ1η0 b21
. Then the following equation holds for ZeroSARAH (Algorithm 2) for solving problem (1), for any iteration K ≥ 0:
E[‖∇f(x̂K)‖2] ≤ 2∆0∑K−1 k=0 ηk + (n− b0)(4γ0 + 2α0b0)G0 nb0 ∑K−1 k=0 ηk . (5)
Remark: Note that we can upper bound both terms on the right-hand side of (5). It means that there is no convergence neighborhood of ZeroSARAH and hence, ZeroSARAH can find an -approximate solution for any > 0.
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 k if the minibatch bk = n. Our convergence results show that without computing any full gradients actually does not hurt the convergence performance of algorithms (see Table 1).
In particular, we note that the second term of (5) will be deleted if we choose minibatch size b0 = n for the initial point x0 (see Corollary 1 for more details). Here Corollary 1 only needs to compute the full gradient once for the initialization, and does not compute any full gradients later (i.e., bk ≡ √ n for all k > 0).
Also note that even if we choose b0 < n, we can also upper bound the second term of (5). It means that ZeroSARAH can find an -approximate solution without computing any full gradients even for the initial point, i.e., minibatch size bk < n for all iterations k ≥ 0. For instance, we choose bk ≡ √ n for all k ≥ 0 in Corollary 2 , i.e., ZeroSARAH never computes any full gradients even for the initial point.
Corollary 1 Suppose that Assumption 1 holds. Choose stepsize ηk ≤ 1(1+√8)L for any k ≥ 0, minibatch size bk ≡ √ n and parameter λk = bk2n for any k ≥ 1. Moreover, let b0 = n and λ0 = 1. Then ZeroSARAH (Algorithm 2) can find an -approximate solution for problem (1) such that
E[‖∇f(x̂K)‖2] ≤ 2
and the number of stochastic gradient computations can be bounded by
#grad := K−1∑ k=0 bk ≤ n+ 2(1 + √ 8) √ nL∆0 2 = O ( n+ √ nL∆0 2 ) .
Remark: In Corollary 1, ZeroSARAH only computes the full gradient ∇f(x0) = 1n ∑n i=1∇fi(x0)
once for the initial point x0, i.e., minibatch size b0 = n, and then bk ≡ √ n for all iterations k ≥ 1 in Algorithm 2.
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.
Corollary 2 Suppose that Assumption 1 holds. Choose stepsize ηk ≤ 1(1+√8)L for any k ≥ 0, minibatch size bk ≡ √ n for any k ≥ 0, and parameter λ0 = 1 and λk = bk2n for any k ≥ 1. Then ZeroSARAH (Algorithm 2) can find an -approximate solution for problem (1) such that
E[‖∇f(x̂K)‖2] ≤ 2
and the number of stochastic gradient computations can be bounded by
#grad = O
(√ n(L∆0 +G0)
2
) .
Note that G0 can be bounded by G0 ≤ 2L∆̂0 via L-smoothness Assumption 1, then we also have
#grad = O
(√ n(L∆0 + L∆̂0)
2
) .
Remark: In Corollary 2, ZeroSARAH never computes any full gradients even for the initial point, i.e., minibatch size bk ≡ √ n for all iterations k ≥ 0 in Algorithm 2. If we consider L, ∆0, G0 or ∆̂0 as constant values then the stochastic gradient complexity in Corollary 2 is #grad = O( √ n 2 ), i.e., full gradient computations do not appear in ZeroSARAH (Algorithm 2) and the term ‘n’ also does not appear in its convergence result. Also note that the parameter settings (i.e., {ηk}, {bk} and {λk} in Algorithm 2) of Corollaries 1 and 2 are exactly the same except for b0 = n (in Corollary 1) and b0 = √ n (in Corollary 2). Moreover, the parameter settings (i.e., {ηk}, {bk} and {λk}) for Corollaries 1 and 2 only require the values of L and n, which is the same as all previous algorithms. If one further allows other values, e.g., , G0 or ∆̂0, for setting the initial b0, then the gradient complexity can be further improved (see Appendix D for more details).
5 D-ZeroSARAH ALGORITHM AND ITS CONVERGENCE RESULTS Now, we consider the distributed nonconvex problems (2), i.e., minx∈Rd { f(x) := 1n ∑n i=1 fi(x) } with fi(x) := 1m ∑m j=1 fi,j(x),where n denotes the number of clients/devices/machines, fi denotes the loss associated with m data samples stored on client i.
5.1 D-ZeroSARAH ALGORITHM
To solve distributed nonconvex problems (2), we propose a distributed variant of ZeroSARAH (called D-ZeroSARAH) and describe it in Algorithm 3. 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 of full gradient across all n clients may be impossible or unaffordable. Thus, we expect the proposed D-ZeroSARAH (Algorithm 3) will have a practical impact in distributed and federated learning where full device participation is impractical.
5.2 CONVERGENCE RESULTS FOR D-ZeroSARAH
Similar to ZeroSARAH in Section 4.2, we also first present the main convergence theorem (Theorem 2) of D-ZeroSARAH (Algorithm 3) for solving distributed nonconvex problems (2). 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 3–4 in Table 2 for comparing with convergence results of previous works. Note that here we use the smoothness Assumption 2 instead of Assumption 1 for this distributed setting (2). Theorem 2 Suppose that Assumption 2 holds. Choose stepsize ηk ≤ 1 L ( 1+ √ Wk+1
) for any k ≥ 0, whereWk+1 := 2λk+1sk+1bk+1 + 8λk+1n 2m2
s3k+1b 3 k+1
. Moreover, let λ0 = 1 and θ0 := nm(nm−1)λ1 + 4nmλ1s0b0
s21b 2 1 . Then the following equation holds for D-ZeroSARAH (Algorithm 3) for solving distributed problem (2), for any iteration K ≥ 0:
E[‖∇f(x̂K)‖2] ≤ 2∆0∑K−1 k=0 ηk + (nm− s0b0)η0θ0G′0 nms0b0 ∑K−1 k=0 ηk . (6)
Algorithm 3 Distributed ZeroSARAH (D-ZeroSARAH) Input: initial point x0, parameters {ηk}, {sk}, {bk}, {λk} 1: x−1 = x0
2: v−1 = 0, y−11 = y −1 2 = · · · = y−1n = 0 // no full gradient computation 3: for k = 0, 1, 2, . . . do 4: Randomly sample a subset of clients Sk from n clients with size |Sk| = sk 5: for each client i ∈ Sk do 6: Sample the data minibatch Ikbi (with size |I k bi | = bk) from the m data samples in client i 7: Compute its local minibatch gradient information: gki,curr = 1 bk
∑ j∈Ikbi ∇fi,j(xk), gki,prev = 1bk ∑ j∈Ikbi ∇fi,j(xk−1), yki,prev = 1bk ∑ j∈Ikbi yk−1i,j
yki,j = { ∇fi,j(xk) for j ∈ Ikbi yk−1i,j for j /∈ Ikbi , yki = 1 m m∑ j=1 yki,j
8: end for 9: vk = 1sk ∑ i∈Sk ( gki,curr − gki,prev ) + (1− λk)vk−1 + λk 1sk ∑ i∈Sk ( gki,prev − yki,prev ) + λky k−1
// no full gradient computations for vks 10: xk+1 = xk − ηkvk
11: yk = 1n n∑ i=1 yki // here y k i = y k−1 i for client i /∈ S k 12: end for
Corollary 3 Suppose that Assumption 2 holds. Choose stepsize ηk ≤ 1(1+√8)L for any k ≥ 0, clients subset size sk ≡ √ n, minibatch size bk ≡ √ m and parameter λk = skbk2nm for any k ≥ 1. Moreover, let s0 = n, b0 = m, and λ0 = 1. Then D-ZeroSARAH (Algorithm 3) can find an -approximate solution for distributed problem (2) such that
E[‖∇f(x̂K)‖2] ≤ 2
and the number of stochastic gradient computations for each client can be bounded by
#grad = O ( m+ √ m
n
L∆0 2
) .
Corollary 4 Suppose that Assumption 2 holds. Choose stepsize ηk ≤ 1(1+√8)L for any k ≥ 0, clients subset size sk ≡ √ n and minibatch size bk ≡ √ m for any k ≥ 0, and parameter λ0 = 1 and λk = skbk 2nm for any k ≥ 1. Then D-ZeroSARAH (Algorithm 3) can find an -approximate solution for distributed problem (2) such that E[‖∇f(x̂K)‖2] ≤ 2
and the number of stochastic gradient computations for each client can be bounded by
#grad = O
(√ m
n
L∆0 +G ′ 0
2
) .
Remark: Similar discussions and remarks of Theorem 1 and Corollaries 1–2 for ZeroSARAH in Section 4.2 also hold for the results of D-ZeroSARAH (i.e., Theorem 2 and Corollaries 3–4).

heading: 6 EXPERIMENTS
text: Now, we present the numerical experiments for comparing the performance of our ZeroSARAH/DZeroSARAH with previous algorithms. In the experiments, we consider the nonconvex robust linear regression and binary classification with two-layer neural networks, which are used in (Wang et al., 2018; Zhao et al., 2010; Tran-Dinh et al., 2019). All datasets used in our experiments are downloaded from LIBSVM (Chang & Lin, 2011). The detailed description of these objective functions and datasets are provided in Appendix A.1.
In Figure 1, the x-axis and y-axis represent the number of stochastic gradient computations and the norm of gradient, respectively. The numerical results presented in Figure 1 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 1), the epoch length l = √ n and the minibatch size b = √ n (see Theorem 6 in Pham et al. (2019)). For ZeroSARAH (Algorithm 2), the minibatch size bk ≡ √ n for any k ≥ 0, λ0 = 1 and λk = bk2n ≡ 1 2 √ n
for any k ≥ 1 (see our Corollary 2). Note that there is no epoch length l for ZeroSARAH since it is a loopless (single-loop) algorithm while SARAH requires l for setting the length of its inner-loop (see Line 6 of Algorithm 1). For the stepsize η, both SARAH and ZeroSARAH adopt the same constant stepsize η = O( 1L ). However the smooth parameter L is not known in the experiments, thus here we use three stepsizes, i.e., η = 0.01, 0.1, 1.
Remark: The experimental results validate our theoretical convergence results (our ZeroSARAH can be slightly better than SARAH (see Table 1)) and confirm the practical superiority of ZeroSARAH (avoid any full gradient computations). To demonstrate the full gradient computations in Figure 1, 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/centralized setting (1). Similar experiments in the distributed setting (2) are provided in Appendix A.2, e.g., Figure 2 demonstrates similar performance between distributed SARAH and distributed ZeroSARAH.

heading: 7 CONCLUSION
text: In this paper, we propose ZeroSARAH and its distributed variant D-ZeroSARAH algorithms for solving both standard and distributed nonconvex finite-sum problems (1) 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 previous state-of-the-art results in certain regimes. While the numerical performance of our algorithms is also comparable/better than previous state-of-the-art algorithms, the main advantage of our algorithms 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.

heading: A EXTRA EXPERIMENTS
text: In this appendix, we first describe the details of the objective functions and datasets used in our experiments in Appendix A.1. Then in Appendix A.2, we present the experimental results in the distributed setting (2).

heading: A.1 OBJECTIVE FUNCTIONS AND DATASETS IN EXPERIMENTS
text: The nonconvex robust linear regression problem (used in Wang et al. (2018)) is:
min x∈Rd
{ f(x) := 1
n n∑ i=1 `(bi − xTai)
} , (7)
where the nonconvex loss function `(x) := log(x 2
2 + 1).
The binary classification with two-layer neural networks (used in Zhao et al. (2010); Tran-Dinh et al. (2019)) is:
min x∈Rd
{ f(x) := 1
n n∑ i=1 ` ( aTi x, bi ) + λ 2 ‖x‖2
} (8)
where {ai} ∈ Rd, bi ∈ {−1, 1}, λ ≥ 0 is an `2-regularization parameter, and the function ` is defined as
`(x, y) := ( 1− 1
1 + exp(−xy)
)2 .
All datasets are downloaded from LIBSVM (Chang & Lin, 2011). The summary of datasets information is provided in the following Table 3.

heading: A.2 EXPERIMENTS FOR THE DISTRIBUTED SETTING
text: 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 we describe one possible version in Algorithm 4. Note that distributed SARAH also requires to periodically computes full gradients (see Line 7 of Algorithm 4), but it is not required by our D-ZeroSARAH (Algorithm 3).
In 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 on the workstation with 48 Cores, Intel(R) Xeon(R) Gold 6246 CPU @ 3.30GHz. We partition the dataset among 10 threads; having M datapoints and n clients, k-thread gets datapoints in range kbMn c+ 1, . . . , (k + 1)b M n c. In case of nbMn c+ 1 ≤M , datapoints nb M n c+ 1, . . .M are ignored.
Algorithm 4 Distributed SARAH-type methods (one possible version) Input: initial point x0, epoch length l, stepsize η, client minibatch size s, data minibatch size b 1: x−1 = x0
2: for k = 0, 1, 2, . . . do 3: if k mod l = 0 then 4: for each client i ∈ {1, . . . , n} do 5: Compute full gradient of each client: gki = 1 m m∑ j=1 ∇fi,j(xk) // = ∇fi(xk) 6: end for 7: vk = 1n n∑ i=1 gki // full gradient computations 8: else 9: Randomly sample a subset of clients Sk from n clients with size |Sk| = s
10: for each client i ∈ Sk do 11: Sample minibatch Iki of size |Iki | = b (from the m data samples in client i) 12: Compute the local minibatch gradient information:
gki,curr = 1 b ∑ j∈Iki ∇fi,j(xk) and gki,prev = 1b ∑ j∈Iki ∇fi,j(xk−1)
13: end for 14: vk = 1s ∑ i∈Sk ( gki,curr − gki,prev ) + vk−1 15: end if 16: xk+1 = xk − ηkvk 17: end for
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. (2019), we know that the smoothness constant L ≈ 0.15405 maxi ‖ai‖2 + λ for objective function (8). We choose the regularizer parameter to be λ = 0.15405·10−6 maxi ‖ai‖2. In order to obtain comparable plots similar to the standard/centralized setting (Figure 1), we also use multiple stepsizes. We choose the theoretical stepsize from Corollary 4 (i.e., 1
(1+ √ 8)L ) scaled
by factors of ×1 (red curves), ×3 (blue curves), ×9 (green curves), respectively.
Remark: Similar to Figure 1, the experimental results in Figure 2 also validate our theoretical convergence results (distributed ZeroSARAH (D-ZeroSARAH) can be slightly better than distributed SARAH (see Table 2)) and confirm the practical superiority of D-ZeroSARAH (avoid any full gradient computations) for the distributed setting (2).
B MISSING PROOFS FOR ZeroSARAH
In this appendix, we provide the missing proofs for the standard nonconvex setting (1). Concretely, we provide the detailed proofs for Theorem 1 and Corollaries 1–2 of ZeroSARAH in Section 4.

heading: B.1 PROOF OF THEOREM 1
text: First, we need a useful lemma in Li et al. (2021) which describes the relation between the function values after and before a gradient descent step.
Lemma 1 (Li et al. (2021)) Suppose that function f is L-smooth and let xk+1 := xk − ηkvk. Then for any vk ∈ Rd and ηk > 0, we have
f(xk+1) ≤ f(xk)− ηk 2 ‖∇f(xk)‖2 − ( 1 2ηk − L 2 ) ‖xk+1 − xk‖2 + ηk 2 ‖vk −∇f(xk)‖2. (9)
Then, we provide the following Lemma 2 to bound the last variance term of (9).
Lemma 2 Suppose that Assumption 1 holds. The gradient estimator vk is defined in Line 5 of Algorithm 2, then we have
Ek[‖vk −∇f(xk)‖2] ≤ (1− λk)2‖vk−1 −∇f(xk−1)‖2 + 2L2
bk ‖xk − xk−1‖2
+ 2λ2k bk 1 n n∑ j=1 ‖∇fj(xk−1)− yk−1j ‖ 2. (10)
Proof of Lemma 2. First, according to the gradient estimator vk of ZeroSARAH (see Line 5 of Algorithm 2), we know that
vk = 1
bk ∑ i∈Ikb ( ∇fi(xk)−∇fi(xk−1) ) + (1− λk)vk−1 + λk ( 1 bk ∑ i∈Ikb ( ∇fi(xk−1)− yk−1i ) + 1 n n∑ j=1 yk−1j ) (11)
Now we bound the variance as follows:
Ek[‖vk −∇f(xk)‖2]
(11) = Ek [∥∥∥∥ 1bk ∑ i∈Ikb ( ∇fi(xk)−∇fi(xk−1) ) + (1− λk)vk−1
+ λk ( 1 bk ∑ i∈Ikb ( ∇fi(xk−1)− yk−1i ) + 1 n n∑ j=1 yk−1j ) −∇f(xk) ∥∥∥∥2 ]
= Ek [∥∥∥∥ 1bk ∑ i∈Ikb ( ∇fi(xk)−∇fi(xk−1) ) +∇f(xk−1)−∇f(xk) + (1− λk)(vk−1 −∇f(xk−1))
+ λk ( 1 bk ∑ i∈Ikb ( ∇fi(xk−1)− yk−1i ) + 1 n n∑ j=1 yk−1j −∇f(x k−1) )∥∥∥∥2 ]
= Ek [∥∥∥∥ 1bk ∑ i∈Ikb ( ∇fi(xk)−∇fi(xk−1) ) +∇f(xk−1)−∇f(xk)
+ λk ( 1 bk ∑ i∈Ikb ( ∇fi(xk−1)− yk−1i ) + 1 n n∑ j=1 yk−1j −∇f(x k−1) )∥∥∥∥2 ]
+ (1− λk)2‖vk−1 −∇f(xk−1)‖2
≤ 2Ek [∥∥∥∥ 1bk ∑ i∈Ikb ( ∇fi(xk)−∇fi(xk−1) ) +∇f(xk−1)−∇f(xk) ∥∥∥∥2 ]
+ 2Ek [ λ2k ∥∥∥∥ 1bk ∑ i∈Ikb ( ∇fi(xk−1)− yk−1i ) + 1 n n∑ j=1 yk−1j −∇f(x k−1) ∥∥∥∥2 ] + (1− λk)2‖vk−1 −∇f(xk−1)‖2
≤ 2L 2 bk ‖xk − xk−1‖2 + 2λ 2 k bk 1 n n∑ j=1 ‖∇fj(xk−1)− yk−1j ‖ 2 + (1− λk)2‖vk−1 −∇f(xk−1)‖2,
(12)
where (12) uses the L-smoothness Assumption 1 and the fact that E[‖x−Ex‖2] ≤ E[‖x‖2], for any random variable x.
To deal with the last term of (10), we use the following Lemma 3.
Lemma 3 Suppose that Assumption 1 holds. The update of {yki } is defined in Line 7 of Algorithm 2, then we have, for ∀βk > 0,
Ek
[ 1
n n∑ j=1 ‖∇fj(xk)− ykj ‖2 ] ≤ ( 1− bk n ) (1 + βk) 1 n n∑ j=1 ‖∇fj(xk−1)− yk−1j ‖ 2
+ ( 1− bk
n
)( 1 + 1
βk
) L2‖xk − xk−1‖2. (13)
Proof of Lemma 3. According to the update of {yki } (see Line 7 of Algorithm 2), we have
Ek
[ 1
n n∑ j=1 ‖∇fj(xk)− ykj ‖2 ]
= ( 1− bk
n ) 1 n n∑ j=1 ‖∇fj(xk)− yk−1j ‖ 2 (14)
= ( 1− bk
n ) 1 n n∑ j=1 ‖∇fj(xk)−∇fj(xk−1) +∇fj(xk−1)− yk−1j ‖ 2
≤ ( 1− bk
n
) (1 + βk) 1
n n∑ j=1 ‖∇fj(xk−1)− yk−1j ‖ 2 + ( 1− bk n )( 1 + 1 βk ) L2‖xk − xk−1‖2, (15)
where (14) uses the update of {ykj } (see Line 7 of Algorithm 2), and (15) uses Young’s inequality and L-smoothness Assumption 1.
Now we combine Lemmas 1–3 (i.e., (9), (10) and (13)) to prove Theorem 1.
Proof of Theorem 1. First, we take expectation to obtain
E [ f(xk+1)− f∗ + ( γk −
ηk 2
) ‖vk −∇f(xk)‖2 + ( 1 2ηk − L 2 ) ‖xk+1 − xk‖2 + αk 1 n n∑ j=1 ‖∇fj(xk)− ykj ‖2 ]
≤ E [ f(xk)− f∗ − ηk
2 ‖∇f(xk)‖2 + γk(1− λk)2‖vk−1 −∇f(xk−1)‖2
+ 2γkL
2
bk ‖xk − xk−1‖2 + 2γkλ
2 k
bk
1
n n∑ j=1 ‖∇fj(xk−1)− yk−1j ‖ 2
+ αk(1− bk n )(1 + 1 βk )L2‖xk − xk−1‖2 + αk(1− bk n )(1 + βk) 1 n n∑ j=1 ‖∇f(xk−1)− yk−1j ‖ 2
]
= E [ f(xk)− f∗ − ηk
2 ‖∇f(xk)‖2 + γk(1− λk)2‖vk−1 −∇f(xk−1)‖2
+ (2γkL2
bk + αk(1− bk n )(1 + 1 βk )L2 ) ‖xk − xk−1‖2
+ (2γkλ2k
bk + αk(1− bk n )(1 + βk) ) 1 n n∑ j=1 ‖∇fj(xk−1)− yk−1j ‖ 2 ] . (16)
Now we choose appropriate parameters. Let γk = ηk−1 2λk and γk ≤ γk−1, then γk(1−λk)2 ≤ γk−1− ηk−1
2 . Let βk = bk 2n , αk = 2nλkηk−1 b2k and αk ≤ αk−1, we have 2γkλ 2 k bk +αk(1− bkn )(1+βk) ≤ αk−1.
We also have 2γkL 2
bk + αk(1− bkn )(1 + 1 βk )L2 ≤ 12ηk−1 − L 2 by further letting stepsize
ηk−1 ≤ 1 L ( 1 + √ Mk ) , (17)
where Mk := 2λkbk + 8λkn
2
b3k .
Summing up (16) from k = 1 to K − 1, we get
0 ≤ E [ f(x1)− f∗ −
K−1∑ k=1 ηk 2 ‖∇f(xk)‖2 + γ1(1− λ1)2‖v0 −∇f(x0)‖2
+ (2γ1L2
b1 + α1(1− b1 n )(1 + 2n b1 )L2 ) ‖x1 − x0‖2
+ (2γ1λ21
b1 + α1(1− b1 n )(1 + b1 2n ) ) 1 n n∑ j=1 ‖∇fj(x0)− y0j ‖2 ] . (18)
For k = 0, we directly uses (9), i.e., E[f(x1)− f∗] ≤ E [ f(x0)− f∗ − η0
2 ‖∇f(x0)‖2 − ( 1 2η0 − L 2 ) ‖x1 − x0‖2 + η0 2 ‖v0 −∇f(x0)‖2 ] .
(19)
Now, we combine (18) and (19) to get
E [ K−1∑ k=0 ηk 2 ‖∇f(xk)‖2 ] ≤ E [ f(x0)− f∗ + ( γ1(1− λ1)2 +
η0 2
) ‖v0 −∇f(x0)‖2
+ (2γ1λ21
b1 + α1(1− b1 n )(1 + b1 2n ) ) 1 n n∑ j=1 ‖∇fj(x0)− y0j ‖2 ]
(20)
≤ E [ f(x0)− f∗ + η0(1− λ1(1− λ1))
2λ1 ‖v0 −∇f(x0)‖2 + 2nλ1η0 b21 1 n n∑ j=1 ‖∇fj(x0)− y0j ‖2 ]
(21) ≤ E [ f(x0)− f∗ + γ0‖v0 −∇f(x0)‖2 + α0 1
n n∑ j=1 ‖∇fj(x0)− y0j ‖2 ]
(22)
≤ f(x0)− f∗ + γ0 n− b0 (n− 1)b0 1 n n∑ j=1 ‖∇fj(x0)‖2 + α0(1− b0 n ) 1 n n∑ j=1 ‖∇fj(x0)‖2 (23)
= f(x0)− f∗ + ( γ0
n− b0 (n− 1)b0 + α0(1− b0 n ) ) 1 n n∑ j=1 ‖∇fj(x0)‖2, (24)
where (20) follows from the definition of η0 in (17), (21) uses γ1 = η02λ1 and α1 = 2nλ1η0 b21 , (22) holds by choosing γ0 ≥ η02λ1 ≥ η0(1−λ1(1−λ1)) 2λ1 and α0 ≥ 2nλ1η0b21 , and (23) uses λ0 = 1. By
randomly choosing x̂K from {xk}K−1k=0 with probability ηk/ ∑K−1 t=0 ηt for x k, (24) turns to
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk + 2∑K−1 k=0 ηk
( γ0
n− b0 (n− 1)b0 + α0(1− b0 n ) ) 1 n n∑ j=1 ‖∇fj(x0)‖2
≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk + (n− b0)(4γ0 + 2α0b0) nb0 ∑K−1 k=0 ηk 1 n n∑ j=1 ‖∇fj(x0)‖2. (25)

heading: B.2 PROOFS OF COROLLARIES 1 AND 2
text: Now, we prove the detailed convergence results in Corollaries 1–2 with specific parameter settings.
Proof of Corollary 1. First we know that (25) with b0 = n turns to
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk . (26)
Then if we set λk = bk2n and bk ≡ √ n for any k ≥ 1, then we know that Mk := 2λkbk + 8λkn 2 b3k ≡ 8
and thus the stepsize ηk ≤ 1 L ( 1+ √ Mk+1 ) ≡ 1 (1+ √ 8)L for any k ≥ 0. By plugging ηk ≤ 1(1+√8)L into (26), we have
E[‖∇f(x̂K)‖2] ≤ 2(1 + √
8)L(f(x0)− f∗) K = 2,
where the last equality holds by letting the number of iterations K = 2(1+ √ 8)L(f(x0)−f∗) 2 . Thus the number of stochastic gradient computations is
#grad = K−1∑ k=0 bk = b0 + K−1∑ k=1 bk = n+ (K − 1) √ n ≤ n+ 2(1 + √ 8) √ nL(f(x0)− f∗) 2 .
Proof of Corollary 2. First we recall (25) here:
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk + (n− b0)(4γ0 + 2α0b0) nb0 ∑K−1 k=0 ηk 1 n n∑ j=1 ‖∇fj(x0)‖2. (27)
In this corollary, we do not compute any full gradients even for the initial point. We set the minibatch size bk ≡ √ n for any k ≥ 0. So we need consider the second term of (27) since b0 = √ n is not equal to n. Similar to Corollary 1, if we set λk = bk2n for any k ≥ 1, then we know that Mk :=
2 λkbk
+ 8λkn 2
b3k ≡ 8 and thus the stepsize ηk ≤ 1 L ( 1+ √ Mk+1 ) ≡ 1 (1+ √ 8)L for any k ≥ 0. For
the second term, we recall that γ0 ≥ η02λ1 = √ n (1+ √ 8)L and α0 ≥ 2nλ1η0b21 = 1 (1+ √ 8)L √ n . It is easy to
see that γ0 ≥ α0b0 since b0 = √ n ≤ n. Now, we can change (27) to
E[‖∇f(x̂K)‖2] ≤ 2(1 + √
8)L(f(x0)− f∗) K + 6(n−
√ n)
nK
1
n n∑ j=1 ‖∇fj(x0)‖2
≤ 2(1 + √
8)L(f(x0)− f∗) + 6G0 K
(28)
= 2,
where (28) is due to the definition G0 := 1n ∑n i=1 ‖∇fi(x0)‖2, and the last equality holds by letting the number of iterations K = 2(1+ √ 8)L(f(x0)−f∗)+6G0 2 . Thus the number of stochastic gradient computations is
#grad = K−1∑ k=0 bk = √ nK = √ n 2(1 + √ 8)L(f(x0)− f∗) + 6G0 2 = O (√ n(L∆0 +G0) 2 ) .
Note that G0 can be bounded by G0 ≤ 2L(f(x0) − f̂∗) via L-smoothness Assumption 1, then we have
#grad = O
(√ n(L∆0 + L∆̂0)
2
) .
Note that ∆0 := f(x0) − f∗, where f∗ := minx f(x), and ∆̂0 := f(x0) − f̂∗, where f̂∗ := 1 n ∑n i=1 minx fi(x).
C MISSING PROOFS FOR D-ZeroSARAH
In this appendix, we provide the missing proofs for the distributed nonconvex setting (2). Concretely, we provide the detailed proofs for Theorem 2 and Corollaries 3–4 of D-ZeroSARAH in Section 5.

heading: C.1 PROOF OF THEOREM 2
text: Similar to Appendix B.1, we first recall the lemma in Li et al. (2021) which describes the change of function value after a gradient update step.
Lemma 1 (Li et al. (2021)) Suppose that function f is L-smooth and let xk+1 := xk − ηkvk. Then for any vk ∈ Rd and ηk > 0, we have
f(xk+1) ≤ f(xk)− ηk 2 ‖∇f(xk)‖2 − ( 1 2ηk − L 2 ) ‖xk+1 − xk‖2 + ηk 2 ‖vk −∇f(xk)‖2. (29)
Then, we provide the following Lemma 4 to bound the last variance term of (29).
Lemma 4 Suppose that Assumption 2 holds. The gradient estimator vk is defined in Line 9 of Algorithm 3, then we have
Ek[‖vk −∇f(xk)‖2] ≤ (1− λk)2‖vk−1 −∇f(xk−1)‖2 + 2L2
skbk ‖xk − xk−1‖2
+ 2λ2k skbk 1 nm n,m∑ i,j=1,1 ‖∇fi,j(xk−1)− yk−1i,j ‖ 2. (30)
Proof of Lemma 4. First, according to the gradient estimator vk of D-ZeroSARAH (see Line 9 of Algorithm 3), we know that
vk = 1
sk ∑ i∈Sk ( gki,curr − gki,prev ) + (1− λk)vk−1 + λk 1 sk ∑ i∈Sk ( gki,prev − yki,prev ) + λky k−1 (31)
Now we bound the variance as follows:
Ek[‖vk −∇f(xk)‖2]
(31) = Ek [∥∥∥∥ 1sk ∑ i∈Sk ( gki,curr − gki,prev ) + (1− λk)vk−1 + λk ( 1 sk ∑ i∈Sk ( gki,prev − yki,prev ) + yk−1 ) −∇f(xk) ∥∥∥∥2 ]
= Ek [∥∥∥∥ 1sk ∑ i∈Sk ( gki,curr − gki,prev ) +∇f(xk−1)−∇f(xk) + (1− λk)(vk−1 −∇f(xk−1))
+ λk ( 1 sk ∑ i∈Sk ( gki,prev − yki,prev ) + yk−1 −∇f(xk−1) )∥∥∥∥2 ]
= Ek [∥∥∥∥ 1sk ∑ i∈Sk ( gki,curr − gki,prev ) +∇f(xk−1)−∇f(xk)
+ λk ( 1 sk ∑ i∈Sk ( gki,prev − yki,prev ) + yk−1 −∇f(xk−1) )∥∥∥∥2 ]
+ (1− λk)2‖vk−1 −∇f(xk−1)‖2
≤ 2Ek [∥∥∥∥ 1skbk ∑ i∈Sk ∑ j∈Ikbi ( ∇fi,j(xk)−∇fi,j(xk−1) ) +∇f(xk−1)−∇f(xk) ∥∥∥∥2 ]
+ 2Ek [ λ2k ∥∥∥∥ 1skbk ∑ i∈Sk ∑ j∈Ikbi ( ∇fi,j(xk−1)− yk−1i,j ) + yk−1 −∇f(xk−1) ∥∥∥∥2 ] + (1− λk)2‖vk−1 −∇f(xk−1)‖2
≤ 2L 2 skbk ‖xk − xk−1‖2 + 2λ 2 k skbk 1 nm n,m∑ i,j=1,1 ‖∇fi,j(xk−1)− yk−1i,j ‖ 2 + (1− λk)2‖vk−1 −∇f(xk−1)‖2,
(32)
where (32) uses the L-smoothness Assumption 2, i.e., ‖∇fi,j(x)−∇fi,j(y)‖ ≤ L‖x− y‖, and the fact that E[‖x− Ex‖2] ≤ E[‖x‖2] for any random variable x. To deal with the last term in (30), we uses the following Lemma 5.
Lemma 5 Suppose that Assumption 2 holds. The update of {yki,j} is defined in Line 7 of Algorithm 3, then we have, for ∀βk > 0,
Ek
[ 1
nm n,m∑ i,j=1,1 ‖∇fi,j(xk)− yki,j‖2 ] ≤ ( 1− skbk nm ) (1 + βk) 1 nm n,m∑ i,j=1,1 ‖∇fi,j(xk−1)− yk−1i,j ‖ 2
+ ( 1− skbk
nm
)( 1 + 1
βk
) L2‖xk − xk−1‖2. (33)
Proof of Lemma 5. According to the update of {yki,j} (see Line 7 and Line 11 of Algorithm 3), we have
Ek
[ 1
nm n,m∑ i,j=1,1 ‖∇fi,j(xk)− yki,j‖2 ]
= ( 1− skbk
nm ) 1 nm n,m∑ i,j=1,1 ‖∇fi,j(xk)− yk−1i,j ‖ 2 (34)
= ( 1− skbk
nm ) 1 nm n,m∑ i,j=1,1 ‖∇fi,j(xk)−∇fi,j(xk−1) +∇fi,j(xk−1)− yk−1i,j ‖ 2
≤ ( 1− skbk
nm
) (1 + βk) 1
nm n,m∑ i,j=1,1 ‖∇fi,j(xk−1)− yk−1i,j ‖ 2 + ( 1− skbk nm )( 1 + 1 βk ) L2‖xk − xk−1‖2,
(35)
where (34) uses the update of {yki,j} in Algorithm 3, and (35) uses Young’s inequality and Lsmoothness Assumption 2.
Now we combine Lemmas 1, 4 and 5 (i.e., (29), (30) and (33)) to prove Theorem 2.
Proof of Theorem 2. First, we take expectation to obtain
E [ f(xk+1)− f∗ + ( γk −
ηk 2
) ‖vk −∇f(xk)‖2 + ( 1 2ηk − L 2 ) ‖xk+1 − xk‖2
+ αk 1
nm n,m∑ i,j=1,1 ‖∇fi,j(xk)− yki,j‖2 ]
≤ E [ f(xk)− f∗ − ηk
2 ‖∇f(xk)‖2 + γk(1− λk)2‖vk−1 −∇f(xk−1)‖2
+ 2γkL
2
skbk ‖xk − xk−1‖2 + 2γkλ
2 k
skbk
1
nm n,m∑ i,j=1,1 ‖∇fi,j(xk−1)− yk−1i,j ‖ 2
+ αk ( 1− skbk
nm
)( 1 + 1
βk
) L2‖xk − xk−1‖2
+ αk ( 1− skbk
nm
) (1 + βk) 1
nm n,m∑ i,j=1,1 ‖∇fi,j(xk−1)− yk−1i,j ‖ 2
]
= E [ f(xk)− f∗ − ηk
2 ‖∇f(xk)‖2 + γk(1− λk)2‖vk−1 −∇f(xk−1)‖2
+ (2γkL2 skbk + αk ( 1− skbk nm )( 1 + 1 βk ) L2 ) ‖xk − xk−1‖2
+ (2γkλ2k skbk + αk ( 1− skbk nm ) (1 + βk) ) 1 nm n,m∑ i,j=1,1 ‖∇fi,j(xk−1)− yk−1i,j ‖ 2 ] . (36)
Now we choose appropriate parameters. Let γk = ηk−1 2λk and γk ≤ γk−1, then γk(1−λk)2 ≤ γk−1− ηk−1
2 . Let βk = skbk 2nm , αk = 2nmλkηk−1 s2kb 2 k and αk ≤ αk−1, we have 2γkλ 2 k skbk +αk ( 1− skbknm ) (1 +βk) ≤
αk−1. We also have 2γkL 2
skbk + αk ( 1− skbknm )( 1 + 1βk ) L2 ≤ 12ηk−1 − L 2 by further letting stepsize
ηk−1 ≤ 1 L ( 1 + √ Wk ) , (37)
where Wk := 2λkskbk + 8λkn
2m2
s3kb 3 k
.
Summing up (36) from k = 1 to K − 1, we get
0 ≤ E [ f(x1)− f∗ −
K−1∑ k=1 ηk 2 ‖∇f(xk)‖2 + γ1(1− λ1)2‖v0 −∇f(x0)‖2
+ (2γ1L2 s1b1 + α1 ( 1− s1b1 nm )( 1 + 2nm s1b1 ) L2 ) ‖x1 − x0‖2
+ (2γ1λ21 s1b1 + α1 ( 1− s1b1 nm )( 1 + s1b1 2nm )) 1 nm n,m∑ i,j=1,1 ‖∇fi,j(x0)− y0i,j‖2 ] . (38)
For k = 0, we directly uses (29), i.e., E[f(x1)− f∗] ≤ E [ f(x0)− f∗ − η0
2 ‖∇f(x0)‖2 − ( 1 2η0 − L 2 ) ‖x1 − x0‖2 + η0 2 ‖v0 −∇f(x0)‖2 ] .
(39)
Now, we combine (38) and (39) to get
E [ K−1∑ k=0 ηk 2 ‖∇f(xk)‖2 ]
≤ E [ f(x0)− f∗ + ( γ1(1− λ1)2 +
η0 2
) ‖v0 −∇f(x0)‖2
+ (2γ1λ21 s1b1 + α1 ( 1− s1b1 nm )( 1 + s1b1 2nm )) 1 nm n,m∑ i,j=1,1 ‖∇fi,j(x0)− y0i,j‖2 ]
(40)
≤ E [ f(x0)− f∗ + η0(1− λ1(1− λ1))
2λ1 ‖v0 −∇f(x0)‖2
+ 2nmλ1η0 s21b 2 1 1 nm n,m∑ i,j=1,1 ‖∇fi,j(x0)− y0i,j‖2 ]
(41)
≤ f(x0)− f∗ + η0 2λ1 nm− s0b0 (nm− 1)s0b0 1 nm n,m∑ i,j=1,1 ‖∇fi,j(x0)‖2
+ 2nmλ1η0 s21b 2 1 nm− s0b0 nm 1 nm n,m∑ i,j=1,1 ‖∇fi,j(x0)‖2 (42)
= f(x0)− f∗ + (nm− s0b0)η0θ0 2nms0b0 G′0, (43)
where (40) follows from the definition of η0 in (37), (41) uses γ1 = η02λ1 and α1 = 2nmλ1η0 s21b 2 1 , (42) uses λ0 = 1, and (43) uses the definitions θ0 := nm(nm−1)λ1 + 4nmλ1s0b0
s21b 2 1 and G′0 := 1 nm ∑n,m i,j=1,1 ‖∇fi,j(x0)‖2.
By randomly choosing x̂K from {xk}K−1k=0 with probability ηk/ ∑K−1 t=0 ηt for x k, (43) turns to
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk + (nm− s0b0)η0θ0G′0 nms0b0 ∑K−1 k=0 ηk
(44)

heading: C.2 PROOFS OF COROLLARIES 3 AND 4
text: Now, we prove the detailed convergence results in Corollaries 3–4 with specific parameter settings.
Proof of Corollary 3. First we know that (44) with s0 = n and b0 = m turns to
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk . (45)
Then if we set λk = skbk2nm , sk ≡ √ n, and bk ≡ √ m for any k ≥ 1, then we know that Wk :=
2 λkskbk
+ 8λkn 2m2
b3ks 3 k ≡ 8 and thus the stepsize ηk ≤ 1 L ( 1+ √ Wk+1 ) ≡ 1 (1+ √ 8)L for any k ≥ 0. By
plugging ηk ≤ 1(1+√8)L into (45), we have
E[‖∇f(x̂K)‖2] ≤ 2(1 + √
8)L(f(x0)− f∗) K = 2,
where the last equality holds by letting the number of iterations K = 2(1+ √ 8)L(f(x0)−f∗) 2 . Thus the number of stochastic gradient computations for each client is
#grad = K−1∑ k=0 bk = m+ (K − 1) √ m√ n ≤ n+ √ m n 2(1 + √ 8)L(f(x0)− f∗) 2 .
Proof of Corollary 4. First we recall (44) here:
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk + (nm− s0b0)η0θ0G′0 nms0b0 ∑K−1 k=0 ηk . (46)
In this corollary, we do not compute any full gradients even for the initial point. We set the client sample size sk ≡ √ n and minibatch size bk ≡ √ m for any k ≥ 0. So we need consider the
second term of (46) since s0b0 = √ nm is not equal to nm. Similar to Corollary 3, if we set λk = skbk 2nm for any k ≥ 1, then we know that Wk := 2 λkskbk + 8λkn 2m2 b3ks 3 k ≡ 8 and thus the stepsize
ηk ≤ 1 L ( 1+ √ Wk+1 ) ≡ 1 (1+ √ 8)L for any k ≥ 0. Now, we can change (46) to
E[‖∇f(x̂K)‖2] ≤ 2(1 + √
8)L(f(x0)− f∗) K + (nm− s0b0)θ0G′0
nms0b0K
≤ 2(1 + √
8)L(f(x0)− f∗) + 4G′0 K
(47)
= 2,
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(1+ √ 8)L(f(x0)−f∗)+4G′0
2 . Thus the number of stochastic gradient computations for each client is
#grad = K−1∑ k=0 bk = K √ m√ n = √ m n 2(1 + √ 8)L(f(x0)− f∗) + 4G′0 2 = O (√ m n L∆0 +G ′ 0 2 ) .
Note that ∆0 := f(x0)− f∗ where f∗ := minx f(x).

heading: D FURTHER IMPROVEMENT FOR CONVERGENCE RESULTS
text: Note that all parameter settings, i.e., {ηk}, {bk} and {λk} in ZeroSARAH for Corollaries 1–2, only require the values of L and n, and {ηk}, {sk}, {bk}, {λk} in D-ZeroSARAH for Corollaries 3–4 only require the values of L, n and m, both are the same as all previous algorithms. If one further allows other values, e.g., , G0 or ∆̂0, for setting the initial b0, then the gradient complexity can be further improved. See Appendices D.1 and D.2 for better results of ZeroSARAH and D-ZeroSARAH, respectively.
D.1 BETTER RESULT FOR ZeroSARAH
Corollary 5 Suppose that Assumption 1 holds. Choose stepsize ηk ≤ 1(1+√8)L for any k ≥ 0, minibatch size bk ≡ √ n and parameter λk = bk2n for any k ≥ 1. Moreover, let b0 = min {√ nG0 2 , n } and λ0 = 1. Then ZeroSARAH (Algorithm 2) can find an -approximate solution for problem (1) such that
E[‖∇f(x̂K)‖2] ≤ 2
and the number of stochastic gradient computations can be bounded by
#grad = O (√ n (L∆0 2 + min {√G0 2 , √ n })) .
Similarly, G0 can be bounded by G0 ≤ 2L∆̂0 via Assumption 1. Let b0 = min {√ nL∆̂0 2 , n } , then
we also have
#grad = O (√ n (L∆0 2 + min {√L∆̂0 2 , √ n })) .
Remark: The result of Corollary 5 for ZeroSARAH is the best one compared with Corollaries 1–2. In particular, it recovers Corollary 1 when b0 = n. In the case b0 < n (never computes any full gradients even for the initial point), then #grad = O (√ n ( L∆0 2 + √ G0 2 )) which is better than the
result O (√ n(L∆0+G0) 2 ) in Corollary 2. Similar to the Remark after Corollary 2, if we consider L,
∆0, G0 or ∆̂0 as constant values then the stochastic gradient complexity in Corollary 5 is #grad = O( √ n 2 ), 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 are non-negative, i.e., ∀x, fi(x) ≥ 0 (usually the case in practice), we can simply bound ∆̂0 := f(x0)− f̂∗ ≤ f(x0) and then b0 can be set as min {√ nLf(x0) 2 , n } for Corollary 5.
Proof of Corollary 5. First we recall (25) here:
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk + (n− b0)(4γ0 + 2α0b0) nb0 ∑K−1 k=0 ηk 1 n n∑ j=1 ‖∇fj(x0)‖2. (48)
Note that here we also need consider the second term of (48) since b0 may be less than n. Similar to Corollary 2, if we set λk = bk2n and bk ≡ √ n for any k ≥ 1, then we know that Mk :=
2 λkbk
+ 8λkn 2
b3k ≡ 8 and thus the stepsize ηk ≤ 1 L ( 1+ √ Mk+1 ) ≡ 1 (1+ √ 8)L for any k ≥ 0. For the
second term, we recall that γ0 ≥ η02λ1 = √ n (1+ √ 8)L and α0 ≥ 2nλ1η0b21 = 1 (1+ √ 8)L √ n
. It is easy to see that γ0 ≥ α0b0 since b0 ≤ n. Now, we can change (48) to
E[‖∇f(x̂K)‖2] ≤ 2(1 + √
8)L(f(x0)− f∗) K + 6(n− b0)√ nb0K 1 n n∑ j=1 ‖∇fj(x0)‖2
= 2(1 +
√ 8)L(f(x0)− f∗)
K + 6(n− b0)G0√ nb0K
(49)
= 2, where (49) is due to the definition G0 := 1n ∑n i=1 ‖∇fi(x0)‖2, and the last equality holds by letting the number of iterations K = 2(1+ √ 8)L(f(x0)−f∗) 2 +
6(n−b0)G0√ nb0 2
. Thus the number of stochastic gradient computations is
#grad = K−1∑ k=0 bk = b0 + K−1∑ k=1 bk
= b0 + (K − 1) √ n ≤ b0 +
2(1 + √ 8) √ nL(f(x0)− f∗) 2 + 6(n− b0)G0
b0 2 . By choosing b0 = min{ √ nG0 2 , n}, we have
#grad ≤ √ n
( 2(1 + √ 8)L(f(x0)− f∗)
2 + min
{ 7 √ G0 2 , √ n })
= O (√ n (L∆0 2 + min {√G0 2 , √ n })) .
Similarly, G0 can be bounded by G0 ≤ 2L(f(x0) − f̂∗) via Assumption 1 and let b0 = min{ √ nL∆̂0 2 , n}, then we have
#grad = O (√ n (L∆0 2 + min {√L∆̂0 2 , √ n })) .
Note that ∆0 := f(x0) − f∗, where f∗ := minx f(x), and ∆̂0 := f(x0) − f̂∗, where f̂∗ := 1 n ∑n i=1 minx fi(x).
D.2 BETTER RESULT FOR D-ZeroSARAH
Corollary 6 Suppose that Assumption 2 holds. Choose stepsize ηk ≤ 1(1+√8)L for any k ≥ 0, clients subset size sk ≡ √ n, minibatch size bk ≡ √ m and parameter λk = skbk2nm for any k ≥ 1.
Moreover, let s0 = min {√ nG′0 m 2 , n } and b0 = m (or b0 = min {√ mG′0 n 2 ,m } and s0 = n), and λ0 = 1. Then D-ZeroSARAH (Algorithm 3) can find an -approximate solution for distributed problem (2) such that
E[‖∇f(x̂K)‖2] ≤ 2
and the number of stochastic gradient computations for each client can be bounded by
#grad = O
(√ m
n
(L∆0 2 + min {√G′0 2 , √ nm })) .
Proof of Corollary 6. First we recall (44) here:
E[‖∇f(x̂K)‖2] ≤ 2(f(x 0)− f∗)∑K−1 k=0 ηk + (nm− s0b0)η0θ0G′0 nms0b0 ∑K−1 k=0 ηk . (50)
Similar to Corollary 4, here we also need consider the second term of (50) since s0b0 may be less than nm. Similarly, if we set λk = skbk2nm , sk ≡ √ n, and bk ≡ √ n for any k ≥ 1, then we know that Wk := 2
λkskbk + 8λkn
2m2
b3ks 3 k ≡ 8 and thus the stepsize ηk ≤ 1 L ( 1+ √ Wk+1 ) ≡ 1 (1+ √ 8)L for any k ≥ 0.
Then (50) changes to
E[‖∇f(x̂K)‖2] ≤ 2(1 + √
8)L(f(x0)− f∗) K + (nm− s0b0)θ0G′0
nms0b0K
= 2(1 +
√ 8)L(f(x0)− f∗)
K + 6(nm− s0b0)G′0√ nms0b0K
(51)
= 2,
where (51) by figuring out θ0 with the initial values of the parameters, and the last equality holds by letting the number of iterations K = 2(1+ √ 8)L(f(x0)−f∗) 2 + 6(nm−s0b0)G′0√
nms0b0 2 . Thus the number of
stochastic gradient computations for each client is
#grad = K−1∑ k=0 bk = s0 n b0 + (K − 1) √ m√ n
≤ √ m
n
2(1 + √
8)L(f(x0)− f∗) 2 + s0b0 n + 6(nm− s0b0)G′0 ns0b0 2
≤ √ m
n
( 2(1 + √ 8)L(f(x0)− f∗)
2 + min
{ 7 √ G′0 2 , √ nm })
(52)
= O
(√ m
n
( L∆0 2 + min {√ G′0 2 , √ nm })) ,
where (52) holds by choosing s0b0 = min {√ nmG′0 2 , nm } . It can be satisfied by letting s0 =
min {√
nG′0 m 2 , n } and b0 = m (or s0 = n and b0 = min {√ mG′0 n 2 ,m } ). The last equation uses the
definition ∆0 := f(x0)− f∗ where f∗ := minx f(x).

Review summaries:
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. 

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.

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.