Nonconvex Variance Reduced Optimization with Arbitrary Sampling

We provide the first importance sampling variants of variance reduced algorithms for empirical risk minimization with non-convex loss functions. In particular, we analyze non-convex versions of SVRG, SAGA and SARAH. Our methods have the capacity to speed up the training process by an order of magnitude compared to the state of the art on real datasets. Moreover, we also improve upon current mini-batch analysis of these methods by proposing importance sampling for minibatches in this setting. Surprisingly, our approach can in some regimes lead to superlinear speedup with respect to the minibatch size, which is not usually present in stochastic optimization. All the above results follow from a general analysis of the methods which works with arbitrary sampling, i.e., fully general randomized strategy for the selection of subsets of examples to be sampled in each iteration. Finally, we also perform a novel importance sampling analysis of SARAH in the convex setting.


Introduction
Empirical risk minimization (ERM) is a key problem in machine learning as it plays a key role in training supervised learning models, including classification and regression problems, such as support vector machine, logistic regression and deep learning. A generic ERM problem has the finite-sum form where x corresponds to the parameters/features defining a model, f i (x) is the loss of the model associated with data point i, and f is the average (empirical) loss across the entire training dataset. In this paper we will focus on the case when the functions f i are L i -smooth but non-convex. We assume the problem has a solution x * . One of the most popular algorithms for solving (1) is stochastic gradient descent (SGD) [19,18]. In recent years, tremendous effort was exerted to improve its performance, leading to various enhancements which use acceleration [1], momentum [14], minibatching [35], distributed implementation [16,15], importance sampling [36,6,27,4], higher-order information [26,9], and a number of other techniques.
process in various clever ways so as to progressively reduce its variance as an estimator of the true gradient. We note that SAG and SARAH, the historically oldest and newest VR methods in the list, respectively, use a biased estimator of the gradient. In theory, all these methods enjoy linear convergence rates on smooth and strongly convex functions, which is in contrast with slow sublinear rate of SGD. VR methods are also easier to implement as they do not rely on a decreasing learning rate schedule. VR methods were recently extended to work with (non-strongly) convex losses [13], and more recently also to non-convex losses [29,28,2,23], in all cases leading to best current rates for (1) in a given function class.

Importance sampling, minibatching and non-convex models
In the context of problem (1), importance sampling refers to the technique of assigning carefully designed non-uniform probabilities {p i } to the n functions {f i }, and using these, as opposed to uniform probabilities, to sample the next data point (stochastic gradient) during the training process.
Despite the huge theoretical and practical success of VR methods, there are still considerable gaps in our understanding. For instance, an importance sampling variant of the popular SAGA method, with the "correct" convergence rate, was only designed very recently [10]; and the analysis applies to strongly convex f only. A coordinate descent variant of SVRG with importance sampling, also in the strongly convex case, was analyzed in [12]. However, the method does not seem to admit a fast implementation. For dual methods based on coordinate descent, importance sampling is relatively well understood [20,32,24,27,3].
The territory is completely unmapped in the non-convex case, however. To the best of our knowledge, no importance sampling VR methods have been designed nor analyzed in the popular case when the functions {f i } are non-convex. An exception to this is dfSDCA [5]; however, this method applies to an explicitly regularized version of (1), and while the individual functions are allowed to be non-convex, the average f is assumed to be convex. Given the dominance of stochastic gradient type methods in training large non-convex models such as deep neural networks, theoretical investigation of VR methods that can benefit from importance sampling is much needed.
The situation is worse still when one asks for importance sampling of minibatches. To the best of our knowledge, there are only a handful of papers on this topic [30,6], none of which apply to the non-convex setting considered here, nor to the methods we will analyze, and the problem is open. This is despite the fact that minibatch methods are de-facto the norm for training deep nets due to the volume of data that feeds into the training, and the necessity to fully utilize the parallel processing power of GPUs and other hardware accelerators for the task. In practice, typically relatively small (O(1) in comparison with n) minibatch sizes are used.

Contributions
The main contributions of this paper are: • Arbitrary sampling. We peform a general analysis of three popular VR methods-SVRG [11], SAGA [7] and SARAH [22]-in the arbitrary sampling paradigm [30,24,25,27,4]. That is, we prove general complexity results which hold for an arbitrary random set valued mapping (aka arbitrary sampling) generating the minibatches of examples used by the algorithms in each iteration.
• Rates. Our bounds improve the best current rates for these methods, for SVRG and SAGA even under the same L i 's. Our importance sampling can be up faster by factor of n comparing to the current state of the art (see Table 1 and Appendix C). Our methods can enjoy linear speedup or even for some specific samplings superlinear speedup in minibatch size. That is, the number of iterations needed to output a solution of a given accuracy drops by a factor equal or greater to the minibatch size used. This is of utmost relevance to the practice of training neural nets with minibatch stochastic methods as our results predict that this is to be expected. We design importance sampling and approximate importance sampling for minibatches which in our experiments vastly outperform the standard uniform minibatch strategies.
• Best rates for SARAH under convexity. Lastly, we also perform an analysis of importance sampling variant of SARAH in the convex and strongly convex case (Appendix I). These are the currently fastest rates for SARAH.

Importance Sampling for Minibatches
As mentioned in the introduction, we assume throughout that f i : R d → R are smooth, but not necessarily convex. In particular, we assume that f i is L i -smooth; that is, Without loss of generality assume that L 1 ≤ L 2 ≤ · · · ≤ L n .

Samplings
Let S be a random set-valued mapping ("sampling") with values in 2 [n] , where [n] def = {1, 2, . . . , n}. A sampling is uniquely defined by assigning probabilities to all 2 n subsets of [n]. With each sampling we associate a probability matrix P ∈ R n×n defined by The probability vector associated with S is the vector composed of the diagonal entries of P: From now on, we will refer to b as the minibatch size of sampling S. It is known that P − pp is a symmetric positive semidefinite matrix [31]. Let us without loss of generality assume that p 1 ≤ p 2 ≤ · · · ≤ p n and define constant k = |{i ∈ [n] : p i < 1}| = max{i : p i < 1} to be number of p i 's, which are not equal to one.
While our complexity results are general in the sense that they hold for any proper sampling, we shall now consider three special samplings; all with minibatch size b ∈ (0, n]: (i) Standard uniform minibatch sampling (S = S u ). 1 S is chosen uniformly at random from all subsets of [n] of cardinality b. Clearly, |S| = b with probability 1. The probability matrix is given by (ii) Independent sampling (S = S * ). Assume any proper p i 's . For each i ∈ [n] we independently flip a coin, and with probability p i include element i into S. Hence, by construction, p i = Prob(i ∈ S) and

E [|S|]
(2) (iii) Approximate independent sampling (S = S a ). Independent sampling has the disadvantage that k coin tosses 2 need to be performed in order to generate the random set. However, we would like to sample at the cost O(b + k − n) coin tosses instead. We now design a sampling which has this property and which in a certain precise sense, as we shall see later, approximates the independent sampling. In particular, given an independent sampling with parameters . We now sample a single set S of cardinality a using the standard uniform minibatch sampling (just for i ≤ k). Subsequently, we apply an independent sampling to select elements of S , with selection probabilities kpi a npj a = (a−1)k a(k−1) p i p j for i, j ≤ k, the probability matrix of S is given by Since (a−1)k a(k−1) ≈ 1, the probability matrix of the approximate independent sampling approximates that of the independent sampling. Note that S includes both the standard uniform minibatch sampling and the independent sampling as special cases. Indeed, the former is obtained by choosing p i = b/n for all i (whence a = b and p i = 1 for all i), and the latter is obtained by choosing a = n instead of a = k max i≤k p i .

Key lemma
The following lemma, which we use as upper bound for variance, plays a key role in our analysis. Lemma 1. Let ζ 1 , ζ 2 , . . . , ζ n be vectors in R d and letζ def = 1 n n i=1 ζ i be their average. Let S be a proper sampling (i.e., assume that p i = Prob(i ∈ S) > 0 for all i). Assume that there is v ∈ R n such that Then 1 In the literature, this is often refered to by the name b-nice sampling [31,25]. 2 Note that just k not n, because others are included with probability one.
where the expectation is taken over sampling S. Whenever (4) holds, it must be the case that Moreover, (4) is always satisfied for v i = n(1 − p i ) for i ≤ k and 0 otherwise. Further, if |S| ≤ d with probability 1 for some d, then (4) holds for v i = d. The standard uniform minibatch sampling admits v i = n−b n−1 , the independent sampling admits v i = 1 − p i , and the approximate independent sampling admits the choice The following quantities, which comes from Lemma 1 and smoothness assumption, play a key role in our general complexity results: We can see through theory that it is a good idea to design samplings for which the value α is the smallest possible, which would lead to optimal sampling. The following result sheds light on how S should be chosen, from samplings of a given minibatch size b, to minimize α.
Lemma 2. Fix a minibatch size b ∈ (0, n]. Then the quantity α, defined in (7), is minimized for the choice S = S * with the probabilities where k is the largest integer satisfying where s = 1 for S * and s = 1 − k−a a(k−1) for S a . Moreover, if we assume 3 bL n ≤ n i=1 L i , then k = n, thus From now let S * , S a denote Independent Sampling and Approximate Inpedendent Sampling, respectively, with probabilities defined in (8).
Remark 1. Lemma 2 guarantees that the sampling S * is optimal. Moreover, let b max def = max{b|bL n ≤ n i=1 L i } then in theory, we have super linear speed up for b up to b max for all three algorithms.

SVRG, SAGA and SARAH
In all of the results of this section we assume that S is an arbitrary proper sampling. Let b = E [|S|] be the (average) minibatch size. We assume that v satisfies (4) and that α (which depends on v) is defined as in (7). All complexity results will depend on α and b.
We propose three methods, Algorithm 1, 2 and 3, which are generalizations of original SVRG [28], SAGA and SARAH to the arbitrary sampling setting, respectively. The original non-minibatch methods arise as special  Algorithm 2 SAGA with arbitrary sampling x 0 , d, T, η, S cases for the sampling S = {i} with probability 1/n, and the original minibatch methods arise as a special case for the sampling S u (described in Section 2.1). Our general result for SVRG [11] follows.
Theorem 5 (Complexity of SARAH with arbitrary sampling). Consider one outer loop of Alg. 3 with Then the output x a satisfies: . Thus in terms of stochastic gradient evaluations to obtain -accurate solution, one needs following number of iterations If all L i 's are the same and we choose S to be S a , thus uniform with mini-batch size b, we can get back original result from [23]. Taking b = n, we can restore gradient descent with the correct step size.

Gradient dominated functions
Gradient dominance is weaker version of strong convexity due to the fact that if function is µ-strongly convex then it is τ -gradient dominated, where τ = 2/µ.
Any of the non-convex methods in this paper can be used as a subroutine of Algorithm 4, where T is the number of steps of the subroutine and A is the set of optimal parameters for the subroutine. We set T = αn 2/3 /(bν 2 ) for SVRG and T = αn 2/3 /(bν 3 ) for SAGA. In the case of SARAH, T is obtained by solving m + 1 = 2/η in m and setting T ← m. Using Theorems 3, 4, 5 and the above special choice of T , we get Combined with Definition 1, this guarantees linear convergence with the same constants α,L and b we had before in our analysis.

Importance sampling for SARAH under convexity
In addition to the results presented in previous sections, we also establish importance sampling results for SARAH in convex and strongly convex cases (Appendix I) with similar improvements as for the non-convex algorithm. Ours are the best current rates for SARAH in these settings.
Further, we also provide specialized non-minibatch versions of non-convex SAGA, SARAH and SVRG, which are either special cases of their minibatch versions presented in the main part, or slight modifications, with slightly improved guarantees.

Experiments
In this section, we perform experiments with regression for binary classification, where our loss function has form 1 is the sigmoid function, thus is smooth but non-convex. We use four LIBSVM datasets 4 : covtype, ijcnn1, splice, australian.
Parameters of each algorithm are chosen as suggested by theorems in section 3 and x 0 is set to be all zeros vector. The y axis shows the norm of the gradient, and the x axis shows how many times the algorithm evaluates the full gradient. Evaluation of the gradient of a single function from the empirical loss costs 1/n of the full gradient evaluation. For SARAH, we chose m = n/b .

Importance and uniform sampling comparison
Here we provide comparison of the methods with uniform S u and with importance S * sampling.

Linear or more than linear speedup
Theory suggests that linear or even more than linear speed up can be obtained using S * . Our experiment suggest that this is possible for all three algorithms.  2 confirms that linear, even superlinear, speedup (with increasing batch size, we need the same or less full gradient evaluations) can be obtained also in practice, not just in theory. However, it is limited, and for this dataset it is up to minibatch size of 250. Upper graphs at Figure 2 visualize convergence under assumption of multi-core settings, where we assume number of cores is the same as the minibatch size.

Independent Sampling vs. Approximate Independent Sampling
In the theory, Independent Sampling S * is slightly better than Approximate Independent Sampling S a . However, it is more expensive in terms of computations. The goal of the next experiment is to show that in practice S a yields comparable or faster convergence. Hence, it is more reasonable to use this sampling for datasets, where number of data points n is big (if we implement S a efficiently we can almost get rid of dependence on n). The intuition behind why S a could work better is that S a has smaller variance in batch size than S * . It can be seen from Figure 3 that S a can outperform S * , thus, however, S * is optimal in theory, one should use S a in practice.

Appendix
Let A = [a 1 , . . . , a n ] ∈ R d×n , where a i = ζi pi , and let e be the vector of all ones in R n . We now write the variance of X in a form which will be convenient to establish a bound: Since by assumption we have P − pp Diag (p • v), we can further bound To obtain (5), it remains to combine this with (12). Inequality (6) follows by comparing the diagonal elements of the two matrices in (4). Let us now verify the formulas for v.
• It was shown in [25] • Consider now the independent sampling. Clearly, where v i = 1 − p i .
• Consider the b-nice sampling (standard uniform minibatch sampling). Direct computation shows that the probability matrix is given by as claimed in (3). Therefore, the probability matrix of the approximate independent sampling satisfies

B Proof of Theorem 2
We first establish a lemma we will need in order to prove Theorem 2.

Let be the largest integer for which
Li L k (note that the inequality holds for k = n − b + 1). Then (13) has the following solution: Proof. The Lagrangian of the problem is L(p, y, λ 1 , .., λ n , u 1 , ..., Th constraints are linear and hence KKT conditions hold. The result can be deduced from the KKT conditions.
We can now proceed with the proof. Since n, b andL are constants, the problem is equivalent to In view of (6), where function Ω(p) was defined in Lemma 6. Since b = E [|S|] = i p i , and 0 ≤ p i ≤ 1 for all i, then in view of Lemma 6 we have where p * is defined by (8).
On the other hand, from Lemma 1 we know that the independent sampling S = S * with probability vector p * defined in (8) satisfies inequality (4) with v i = 1 − p i , and hence Hence, it is optimal.

C Improvements
Let us compute α for uniform sampling.
It is easy to see that L max ≥L. To prove that we have improved current best known rates, we need to show thatLα ≤ L max andL 2 α ≤ (n−b) , then L max ≈ nL and α S * ≤ 1 and α S u ≈ n, which essentially means, that we can have in theory speed up by factors of n.

D.1 SVRG
For SVRG, each outer loop costs n + mb evaluations of stochastic gradient. If we want to obtain -solution, following must hold (Theorem 3) Combining these two equations with definition from Theorem 3, we get total complexity in terms of stochastic gradients evaluation

D.2 SAGA
For SAGA, each loop costs d + b evaluations of stochastic gradient. If we want to obtain -solution, following must hold (Theorem 4) Combining these two equations with definition from Theorem 4, we get total complexity in terms of stochastic gradients evaluation because of evaluation of full gradient on the start.

D.3 SARAH
For SARAH with one outer loot, each inner loop costs 2b evaluations of stochastic gradient. If we want to obtain -solution, following must hold (Theorem 5) Solving this equation for m, we get Combining thise equation with complexity off each inner loop we obtain total complexity in terms of stochastic gradients evaluation E Proofs for SVRG Lemma 7. For c t , c t+1 , β > 0, suppose we have Let η, β and c t+1 be chosen such that Γ t > 0 (in Theorem (17)). The iterate x s+1 t in Algorithm 5 satisfy the bound: Proof. Since f i is L i -smooth we have Summing through all i and dividing by n we obtain Using the IS-SVRG update in Algorithm 5 and its unbiasedness ( ), the right hand side above is further upper bounded by Consider now the Lyapunov function For bounding it we will require the following: The second equality follows from the unbiasedness of the update of IS-SVRG. Plugging Equation (15) and Equation (16) into R s+1 t+1 , we obtain the following bound: To further bound this quantity, we use Lemma 10 to bound E v s+1 t 2 , so that upon substituting it in Equation (17), we see that The second inequality follows from the definition of c t and R s+1 t , thus concluding the proof.

Proof of Lemma 7 and Theorem 17
Proof. Since η = η for t ∈ {0, . . . , m − 1}, using Lemma 7 and telescoping the sum, we obtain This inequality in turn implies that where we used that R s+1 The above inequality used the fact thatx 0 = x 0 . Using the above inequality and the definition of x a in Algorithm 5, we obtain the desired result.

Proof of Theorem 3
The proofs essentially follow along the lines of Lemma 7, Theorem 17 and Theorem 18 with the added complexity of mini-batch. We first prove few intermediate results before proceeding to the proof of Theorem 3.

Lemma 8. Suppose we have
for 0 ≤ s ≤ S − 1 and 0 ≤ t ≤ m − 1 and the parameters η, β and c t+1 are chosen such that Then the iterates x s+1 t in the mini-batch version of Algorithm 5 i.e., Algorithm 1 with expected mini-batch size b satisfy the bound: Proof. Using essentially the same argument as the proof of Lemma 7 until Equation (17), we have We use Lemma 11 in order to bound E v s+1 t 2 in the above inequality. Substituting it in Equation (26), we see that The second inequality follows from the definition of c t and R s+1 t , thus concluding the proof.
The following theorem provides convergence rate of mini-batch IS-SVRG.
Theorem 9. Let γ n denote the following quantity: for t ∈ {0, . . . , m − 1} and γ n > 0. Then for the output x a of mini-batch version of Algorithm 5 with mini-batch size b, we have where x * is an optimal solution to (1).
Proof. Since η = η for t ∈ {0, . . . , m − 1}, using Lemma 8 and telescoping the sum, we obtain This inequality in turn implies that . Now sum over all epochs and using the fact thatx 0 = x 0 , we get the desired result.
We now present the proof of Theorem 3 using the above results.
Proof. The proof simply follows from the proof of Lemma 11 with S t = {i t }.
We now present a result to bound the variance of mini-batch IS-SVRG.
Lemma 11. Let v s+1 t be computed by the mini-batch version of Algorithm 5 i.e., Algorithm 1 with sampling S. Then, Proof. For the simplification, we use the following notation: We use the definition of v s+1 t to get The first inequality follows from fact that x + y 2 ≤ 2 x 2 + 2 y 2 and the fact that E ζ s+1 t = ∇f (x s+1 t ) − ∇f (x s ). From the above inequality, we get G Proofs for SAGA Lemma 12. For c t , c t+1 , β > 0, suppose we have Also let η, β and c t+1 be chosen such that Γ t > 0. Then, the iterates {x t } of Algorithm 6 satisfy the bound Proof. Since f isL-smooth we have We first note that the update in Algorithm 6 is unbiased i.e., E [v t ] = ∇f (x t ). By using this property of the update on the right hand side of the inequality above, we get the following: Here we used the fact that x t+1 − x t = −ηv t (see Algorithm 2). Consider now the Lyapunov function For bounding R t+1 we need the following: The above equality follows from the definition of α t+1 i and the definition of randomness of index j t in Algorithm 6 and Algorithm 2. The term T 1 in (32) can be bounded as follows The second equality again follows from the unbiasedness of the update of IS-SAGA. The last inequality follows from a simple application of Cauchy-Schwarz and Young's inequality. Plugging (31) and (33) into R t+1 , we obtain the following bound: where we use that To further bound the quantity in (34), we use Lemma 13 to bound E v t 2 , so that upon substituting it into (34), we obtain R t+1 The second inequality follows from the definition of c t i.e., c t = c t+1 1 − d n + ηβ and R t specified in the statement, thus concluding the proof.
The following lemma provides a bound on the variance of the update used in Mini-batch IS-SAGA algorithm. More specifically, it bounds the quantity E v t 2 .
Lemma 13. Let v t be computed by Algorithm 2. Then, Proof. For ease of exposition, we use the notation Using the convexity of · 2 and the definition of v t we get The first inequality follows from the fact that a + b 2 ≤ 2( a 2 + b 2 ) and that E [ The last inequality follows from L i -smoothness of f i and using properties of S sampling, thus concluding the proof.

Proof of Theorem 19
Proof. We apply telescoping sums to the result of Lemma 12 to obtain The first inequality follows from the definition of γ n . This inequality in turn implies the bound where we used that ). Using inequality (39), the optimality of x * , and the definition of x a in Algorithm 6, we obtain the desired result.
Using the above upper bound on c t we can conclude that upon using the following inequalities: (i) c t+1 η/β ≤ η/4, (ii) η 2 L ≤ η/3 and (iii) 2c t+1 η 2 ≤ η/6, which hold due to the upper bound on c t in (40) and if b ≤ K /L 2 n 2/3 . Substituting this bound on γ n in Theorem 19, we obtain the desired result.
Theorem 20 is special case with b = 1 and d = 1.

SARAH-non-convex
This lemmas are modification of lemmas appeared in [23] for importance sampling with mini-batch.
where x * is an optimal solution of (1).
Proof. ByL-smoothness of f and x t+1 = x t − ηv t , we have where the last equality follows from the fact r q = 1 2 r 2 + q 2 − r − q 2 , for any r, q ∈ R d . By summing over t = 0, . . . , m, we have which is equivalent to (η > 0): where the last inequality follows since x * is an optimal solution of (1). (Note that x 0 is given.)

Lemma 15.
Consider v t defined in SARAH, then for any t ≥ 1, Proof. Let F j = σ(x 0 , i 1 , i 2 , . . . , i j−1 ) be the σ-algebra generated by x 0 , i 1 , i 2 , . . . , i j−1 ; F 0 = F 1 = σ(x 0 ). Note that F j also contains all the information of x 0 , . . . , x j as well as v 0 , . . . , v j−1 . For j ≥ 1, we have where the last equality follows from By taking expectation for the above equation, we have Note that ∇f (x 0 ) − v 0 2 = 0. By summing over j = 1, . . . , t (t ≥ 1), we have With the above Lemmas, we can derive the following upper bound for E ∇f (x t ) − v t 2 .
Consider v t defined in SARAH. Then for any t ≥ 1, Proof. Let We have Hence, by taking expectation, we have By Lemma 15, for t ≥ 1, This completes the proof.

Proof of Theorem 5
Proof. By Lemma 16, we have We have is a root of equation Therefore, by Lemma 14, we have If x a is chosen uniformly at random from {x t } m t=0 , then This concludes the proof.
Comparing Theorem 17 to the previous result in [28], we can see improvement in constant, if we assume different L i -smooth constants for different functions. If the all L i 's are the same then our result is the same as previous result for uniform sampling, because then α = n−1 n−1 = 1.

H.2 SAGA
Here, we provide similar analysis as for SVRG with the same result. We provide more generalized improved form of theorems which appeared in [29]. Randomly uniformly pick it from [n] x t+1 = x t − ηv t 8: α t+1 j t = x t and α t+1 j = α t j for j = jt 9: g t+1 = g t − 1 n (∇fj t (α t j t ) − ∇fj t (α t+1 j t )) 10: end for 11: Output: Iterate xa chosen uniformly random from {x t } T t=0 .
We can see that exactly same conclusions apply here as for SVRG and results can be interpreted in the same way.

I.1 Main result
Consider Algorithm 7, which is an importance sampling variant of the SARAH method.
Note, that only 10-th and 11-th row are changed comparing to classic SARAH algorithm presented in [22]. We do not sample uniformly anymore and also in the 11-th row of Algorithm 7, where we use factor 1 npi in order to stay unbiased in outer cycle.
Then using similar analysis used in [22] and additional lemmas we can prove following theorems with p i in Algorithm 7 to be Li n j=1 Li Theorem 21. Suppose that f i (x) are L i -smooth and convex, f (x) is µ strongly convex. Consider v t defined in SARAH-ISc (Algorithm 7) with η < 2/L, whereL = 1 n n j=1 L i . Then, for any t ≥ 1, By choosing η = O(1/L), we obtain the linear convergence of v t 2 in expectation with the rate (1 − 1/κ 2 ), where κ =L µ is condition number, This is improvement over previous result in [22], because ofL µ ≤ Lmax µ . Below we show that a better convergence rate could be obtained under a stronger convexity assumption for each single f i (x). v t = 1 npi (∇f it (x t ) − ∇f it (x t−1 )) + v t−1 12: x t+1 = x t − ηv t

13:
end for 14: Setx s = x t with t chosen uniformly at random from {0, 1, . . . , m} 15: end for Theorem 22. Suppose that f i (x) are L i -smooth and µ strongly convex. Consider v t defined by in SARAH-ISc (Algorithm 7) with η ≤ 2/(µ +L). Then the following bound holds, ∀ t ≥ 1, By setting η = O(1/L), we derive the linear convergence with the rate of (1 − 1/κ), whereκ =L µ which is an improvement over the previous result of [22], because if we take the optimal stepsize ν = 2 µ+L than we can easily prove that 2µLη µ+L is greater than 2µLmaxη µ+Lmax , with optimal step size, where L max = max i {L i }.
Lemma 25. Suppose that f i (x)'s are L i -smooth and convex. Consider SARAH (Algorithm 7) with η < 2/L. Then we have that for any t ≥ 1,

Proof of Lemma 24
Proof. Let F j be σ algebra that contains all the information of x 0 , . . . , x j as well as v 0 , . . . , v j−1 . For j ≥ 1, we have where the last equality follows from By taking expectation for the above equation, we have Note that ∇f (x 0 ) − v 0 2 = 0. By summing over j = 1, . . . , t (t ≥ 1), we have

Proof of Lemma 25
Proof. For j ≥ 1, we have The consequent equality follows from definition of p i 's and the last equality follows from definition of SARAH-ISc . Taking expectation, we get when η < 2/L. By summing the above inequality over j = 1, . . . , t (t ≥ 1), we have By Lemma 24, we have

Proof of Theorem 21
Proof. For t ≥ 1, we have Using the proof of Lemma 25, for t ≥ 1, we have Note that 1 − 2 ηL < 0 since η < 2/L. The last inequality follows by the strong convexity of f , that is, µ x t − x t−1 ≤ ∇f (x t ) − ∇f (x t−1 ) and the fact that x t = x t−1 − ηv t−1 . By taking the expectation and applying recursively, we have Lemma 28 (Young's inequality). For a, b ∈ R and β > 0 we have Lemma 29 (Jensen's inequality). Let X be a random variable and g(x) be a convex function. Then