Finite-Sum Smooth Optimization with SARAH

Introduction

We are interested in solving the finite-sum smooth minimization problem

where each $f_{i}$, $i\in[n]\stackrel{{\scriptstyle\text{def}}}{{=}}\{1,\dots,n\}$, has a Lipschitz continuous gradient. Throughout the paper, we consider the case where $F$ has a finite lower bound $F^{*}$.

Problems of form (1) cover a wide range of convex and nonconvex problems in machine learning applications including but not limited to logistic regression, neural networks, multi-kernel learning, etc. In many of these applications, the number of component functions $n$ is very large, which makes the classical Gradient Descent (GD) method less efficient since it requires to compute a full gradient many times. Instead, a traditional alternative is to employ stochastic gradient descent (SGD) . In recent years, a large number of improved variants of stochastic gradient algorithms called variance reduction methods have emerged, in particular, SAG/SAGA , SDCA , MISO , SVRG/S2GD , SARAH , etc. These methods were first analyzed for strongly convex problems of form (1). Due to recent interest in deep neural networks, nonconvex problems of form (1) have been studied and analyzed by considering a number of different approaches including many variants of variance reduction techniques (see e.g. , etc.)

We study the SARAH algorithm depicted in Algorithm 1, slightly modified. We use upper index $s$ to indicate the $s$-th outer loop and lower index $t$ to indicate the $t$-th iteration in the inner loop. The key update rule is

The computed $v_{t}^{(s)}$ is used to update

We will analyze SARAH for smooth nonconvex optimization, i.e., we study (1) with the following assumption

We notice that, the above assumption is weaker than the assumption on $L$-smoothness of each $f_{i}$, $i=1,\dots,n$. Throughout this paper for non-convex results, we only consider Assumption 1 and no other assumptions. We stress that our convergence analysis only relies on the above average smooth assumption without bounded variance assumption (as required in ).

We measure the convergence rate in terms of total complexity $\mathcal{T}$, i.e., the total number of gradient computations. For SARAH we have

We notice that SARAH, using the notation and definition of , is a random algorithm ${\cal A}$ that maps functions $f$ to a sequence of iterates

In this paper, we show that in SARAH we can choose parameters $S$ and $m$ such that, for $n\leq\operatorname{\mathcal{O}}(\epsilon^{-2})$, the total complexity is

Related Work: The paper that introduces SARAH is only able to analyze convergence of a single outer loop giving a total complexity of $\operatorname{\mathcal{O}}(n+\frac{L^{2}}{\epsilon^{2}})$.

Besides the lower bound, introduces SPIDER, as a variant of SARAH, which achieves the best known convergence result in the nonconvex case. SPIDER uses the SARAH update rule (2) as was originally proposed in and the mini-batch version of SARAH in . SPIDER and SARAH are different in terms of iteration (3), which are $w_{t+1}=w_{t}-\eta(v_{t}/\|v_{t}\|)$ and $w_{t+1}=w_{t}-\eta v_{t}$, respectively. Also, SPIDER does not divide into outer loop and inner loop as SARAH does although SPIDER does also perform a full gradient update after a certain fixed number of iterations. A recent technical report provides an improved version of SPIDER called SpiderBoost which allows a larger learning rate. Both SPIDER and SpiderBoost are able to show for smooth nonconvex optimization a total complexity of $\operatorname{\mathcal{O}}\left(n+L\sqrt{n}/\epsilon\right)$.

According to the results in Table 1, we can observe that SARAH enjoys the same fast convergence rate as those of SPIDER and SpiderBoost in the nonconvex case for finding a first-order stationary point based on only the average smooth assumption. Its complexity matches the lower-bound worst case complexity in up to a constant factor when $n\leq\operatorname{\mathcal{O}}(\epsilon^{-2})$.

Contributions: We summarize our key contributions as follows.

Smooth Non-Convex. We provide a convergence analysis for the full SARAH algorithm with multiple outer iterations for nonconvex problems (unlike in which only analyses a single outer iteration). Its complexity matches the lower-bound worst case complexity in up to a constant factor when $n\leq\operatorname{\mathcal{O}}(\epsilon^{-2})$. The convergence analysis only supposes the average smooth assumption (which is weaker than Lipschitz continuous assumption on each component gradient) in the non-convex case (Theorem 1). We extend this result to the mini-batch case (Theorem 2).

Smooth Convex. In order to complete the picture, we study SARAH+ which was designed as a variant of SARAH for convex optimization. We propose a novel variant of SARAH+ called SARAH++. Here, we study the iteration complexity measured by the total number of iterations (which counts one full gradient computation as adding one iteration to the complexity) – and leave an analysis of the total complexity as an open problem. For SARAH++ we show a sublinear convergence rate in the general convex case (Theorem 3) and a linear convergence rate in the strongly convex case (Theorem 4). SARAH itself may already lead to good convergence and there may no need to introduce SARAH++; in numerical experiments we show the advantage of SARAH++ over SARAH. We further propose a practical version called SARAH Adaptive which improves the performance of SARAH and SARAH++ for convex problems – numerical experiments on various data sets show good overall performance.

For the convergence analysis of SARAH for the non-convex case and SARAH++ for the convex case we show that the analysis generalizes the total complexity of Gradient Descent (GD) (Remarks 1 and 2), i.e., the analysis reproduces known total complexity results of GD. Up to the best of our knowledge, this is the first variance reduction method having this property.

Non-Convex Case: Convergence Analysis of SARAH

SARAH is very different from other algorithms since it has a biased estimator of the gradient. Therefore, in order to analyze SARAH’s convergence rate, it is non-trivial to use existing proof techniques from unbiased estimator algorithms such as SGD, SAGA, and SVRG.

We start analyzing SARAH (Algorithm 1) for the case where we choose a single sample $i_{t}$ uniformly at random from $[n]$ in the inner loop.

Suppose that Assumption 1 holds. Consider a single outer loop iteration in SARAH (Algorithm 1) with $\eta\leq\frac{2}{L(\sqrt{1+4m}+1)}$. Then, for any $s\geq 1$, we have

where $F^{*}$ is any lower bound of $F$, and $w_{t}^{(s)}$ is the result of the $t$-th iteration in the $s$-th outer loop.

is simply the average of the expectation of the squared norms of the gradients of all the iteration results generated by SARAH. For nonconvex problems, our goal is to achieve

Suppose that Assumption 1 holds. Consider SARAH (Algorithm 1) with $\eta=\operatorname{\mathcal{O}}(\frac{1}{L\sqrt{m+1}})$ where $m$ is the inner loop size. Then, in order to achieve an $\epsilon$-accurate solution, the total complexity is

The total complexity can be minimized over the inner loop size $m$. By choosing $m=n$, we achieve the minimal total complexity:

Suppose that Assumption 1 holds. Consider SARAH (Algorithm 1) with $\eta=\operatorname{\mathcal{O}}(\frac{1}{L\sqrt{m+1}})$ where $m$ is the inner loop size and chosen equal to $m=n$. Then, in order to achieve an $\epsilon$-accurate solution, the total complexity is

The total complexity in Corollary 1 covers all choices for the inner loop size $m$. For example, in the case of $m=0$, SARAH recovers the Gradient Descent (GD) algorithm which has total complexity $\operatorname{\mathcal{O}}\left(\frac{n}{\epsilon}\right)$. Theorem 1 for $m=0$ also recovers the requirement on the learning rate for GD, which is $\eta\leq\frac{1}{L}$.

The above results explain the relationship between SARAH and GD and explains the advantages of the inner loop and outer loop of SARAH. SARAH becomes more beneficial in ML applications where $n$ is large.

2 Mini-batch case

The above results can be extended to the mini-batch case where instead of choosing a single sample $i_{t}$, we choose $b$ samples uniformly at random from $[n]$ for updating $v_{t}$ in the inner loop. We then replace $v_{t}$ in Algorithm 1 by

where we choose a mini-batch $I_{t}\subseteq[n]$ of size $b$ uniformly at random at each iteration of the inner loop. The result of Theorem 1 generalizes as follows.

Suppose that Assumption 1 holds. Consider SARAH (Algorithm 1) by replacing $v_{t}$ in the inner loop size by (8) with

where $F^{*}$ is any lower bound of $F$, and $w_{t}^{(s)}$ is the $t$-th iteration in the $s$-th outer loop.

We can again derive similar corollaries as was done for Theorem 1.

For the conditions in Theorem 2, in order to achieve an $\epsilon$-accurate solution, the total complexity is

For the conditions in Theorem 2 and Corollary 3 with $b=n^{\alpha}$ and $m=n^{\beta}$ where $\alpha+\beta=1$ with $\beta\geq 1/2$ and $0\leq\alpha\leq 1/2$, in order to achieve an $\epsilon$-accurate solution, the total complexity is

Convex Case: SARAH++: A New Variant of SARAH+

In this section, we propose a new variant of SARAH+ (Algorithm 2) , called SARAH++ (Algorithm 3), for convex problems of form (1).

Different from SARAH, SARAH+ provides a stopping criteria for the inner loop; as soon as

Here, we modify SARAH+ (Algorithm 2) into SARAH++ (Algorithm 3) by choosing the stopping criteria for the inner loop as

and by introducing a stopping criteria for the outer loop.

Before analyzing and explaining SARAH++ in detail, we introduce the following assumptions used in this section.

Under Assumption 3, let us define the (unique) optimal solution of (1) as $w_{*}$. Then strong convexity of $F$ implies that

We note here, for future use, that for strongly convex functions of the form (1), arising in machine learning applications, the condition number is defined as $\kappa\stackrel{{\scriptstyle\text{def}}}{{=}}L/\mu$. Assumption 3 covers a wide range of problems, e.g. $l_{2}$-regularized empirical risk minimization problems with convex losses.

We separately assume the special case of strong convexity of all $f_{i}$’s with $\mu=0$, called the general convexity assumption, which we will use for convergence analysis.

SARAH++ is motivated by the following lemma.

Suppose that Assumptions 2 and 4 hold. Consider a single outer loop iteration in SARAH (Algorithm 1) with $\eta\leq\frac{1}{L}$. Then, for $t\geq 0$ and any $s\geq 1$, we have

where $w_{*}$ is any optimal solution of $F$.

where $\eta\leq\frac{\gamma}{L}$, inequality (11) implies

For this reason, we choose the stopping criteria for the inner loop in SARAH++ as $\|v_{t}^{(s)}\|^{2}<\gamma\|v_{0}^{(s)}\|^{2}$ with $\gamma\geq L\eta$. Unlike SARAH+, for analyzing the convergence rate $\gamma$ can be as small as $L\eta$.

The above discussion leads to SARAH++ (Algorithm 3). In order to analyze its convergence for convex problems, we define random variable $T_{s}$ as the stopping time of the inner loop in the $s$-th outer iteration:

Note that $T_{s}$ is at least 1 since at $t=0$, the condition $\|v_{0}^{(s)}\|^{2}\geq\gamma\|v_{0}^{(s)}\|^{2}$ always holds (and $m\geq 0$).

Let random variable $S$ be the stopping time of the outer iterations as a function of an algorithm parameter $T>0$:

Notice that SARAH++ maintains a running sum $G=\sum_{j=1}^{s}T_{i}$ against which parameter $T$ is compared in the stopping criteria of the outer loop.

For the general convex case which supposes Assumption 4 in addition to smoothness we have the next theorem.

Suppose that Assumptions 2 and 4 hold. Consider SARAH++ (Algorithm 3) with $\eta\leq\frac{\gamma}{L}$, $0<\gamma\leq 1$. Then,

the expectation of the average of the squared norm of the gradients of all iterations generated by SARAH++, is bounded by

The theorem leads to the next corollary about iteration complexity, i.e., we bound $T$ which is the total number of iterations performed by the inner loop across all outer loop iterations. This is different from the total complexity since $T$ does not separately count the $n$ gradient evaluations when the full gradient is computed in the outer loop.

For the conditions in Theorem 3 with $\eta=\operatorname{\mathcal{O}}(\frac{1}{L})$, we achieve an $\epsilon$-accurate solution after $\operatorname{\mathcal{O}}(\frac{1}{\epsilon})$ inner loop iterations.

By supposing Assumption 3 in addition to the smoothness and general convexity assumptions, we can prove a linear convergence rate. For strongly convex objective functions we have the following result.

Suppose that Assumptions 2, 3 and 4 hold. Consider SARAH++ (Algorithm 3) with $\eta\leq\frac{\gamma}{L}$, $0<\gamma\leq 1$. Then, for the final output $\hat{w}$ of SARAH++, we have

This leads to the following iteration complexity.

The proofs of the above results hold for any $m\leq T$. If we choose $m=0$, then SARAH++ reduces to the Gradient Descent algorithm since the inner “while” loop stops right after updating $w_{1}^{(s)}=w_{0}^{(s)}-\eta v_{0}^{(s)}$. In this case, Corollaries 5 and 6 recover the rate of convergence and complexity of GD.

In this section, we showed that SARAH++ has a guarantee of theoretical convergence (see Theorems 3 and 4) while SARAH+ does not have such a guarantee.

An interesting open question we would like to discuss here is the total complexity of SARAH++. Although we have shown the convergence results of SARAH++ in terms of the iteration complexity, the total complexity which is computed as the total number of evaluations of the component gradient functions still remains an open question. It is clear that the total complexity must depend on the learning rate $\eta$ (or $\gamma$) – the factor that decides when to stop the inner iterations.

We note that $T$ can be “closely” understood as the total number of updates $w^{(s)}_{t+1}$ of the algorithm. The total complexity is equal to $\sum_{i=1}^{S}(n+2(T_{i}-1))$. For the special case $T_{i}=1$, $i=1,\dots,S$, the algorithm recovers the GD algorithm with $T=\sum_{i=1}^{S}T_{s}=S$. Since each full gradient takes $n$ gradient evaluations, the total complexity for this case is equal to $nS=\operatorname{\mathcal{O}}(\frac{n}{\epsilon})$ (in the general convex case) and $nS=\operatorname{\mathcal{O}}(n\kappa\log(\frac{1}{\epsilon}))$ (in the strongly convex case).

However, it is non-trivial to derive the total complexity of SARAH++ since it should depend on the learning rate $\eta$. We leave this question as an open direction for future research.

2 Numerical Experiments

Paper provides experiments showing good overall performance of SARAH over other algorithms such as SGD , SAG , SVRG , etc. For this reason, we provide experiments comparing SARAH++ directly with SARAH. We notice that SARAH (with multiple outer loops) like SARAH++ has theoretical guarantees with sublinear convergence for general convex and linear convergence for strongly convex problems as proved in . Because of these theoretical guarantees (which SARAH+ does not have), SARAH itself may already perform well for convex problems and the question is whether SARAH++ offers an advantage.

where $\{x_{i},y_{i}\}_{i=1}^{n}$ is the training data and the regularization parameter $\lambda$ is set to $1/n$, a widely-used value in literature . The condition number is equal to $\kappa=L/\mu=n$. We conducted experiments to demonstrate the advantage in performance of SARAH++ over SARAH for convex problems on popular data sets including covtype ($n=406,708$ training data; estimated $L\simeq 1.90$) and ijcnn1 ($n=91,701$ training data; estimated $L\simeq 1.77$) from LIBSVM .

Figure 1 shows comparisons between SARAH++ and SARAH for different values of learning rate $\eta$. We depicted the value of $\log[F(w)-F(w_{*})]$ (i.e. $F(w)-F(w_{*})$ in log scale) for the $y$-axis and “number of effective passes” (or number of epochs, where an epoch is the equivalent of $n$ component gradient evaluations or one full gradient computation) for the $x$-axis. For SARAH, we choose the outer loop size $S=10$ and tune the inner loop size $m=\{0.5n,n,2n,3n,4n\}$ to achieve the best performance. The optimal solution $w_{*}$ of the strongly convex problem in (13) is found by using Gradient Descent with stopping criterion $\|\nabla F(w)\|^{2}\leq 10^{-15}$. We observe that, SARAH++ achieves improved overall performance compared to regular SARAH as shown in Figure 1. From the experiments we see that the stopping criteria $\|v_{t}^{(s)}\|^{2}<\gamma\|v_{0}^{(s)}\|^{2}$ ($\gamma=L\eta$) of SARAH++ is indeed important. The stopping criteria helps the inner loop to prevent updating tiny redundant steps.

3 SARAH Adaptive: A New Practical Variant

We now propose a practical adaptive method which aims to improve performance. Although we do not have any theoretical result for this adaptive method, numerical experiments are very promising and they heuristically show the improved performance on different data sets.

We have conducted numerical experiments on the same datasets and problems as introduced in the previous subsection. Figures 2 and 3 show the comparison between SARAH Adaptive and SARAH and SARAH++ for different values of $\eta$. We observe that SARAH Adaptive has an improved performance over SARAH and SARAH++ (without tuning learning rate). We also present the numerical performance of SARAH Adaptive for different values of $\gamma$ in Appendix. We also present the numerical performance of SARAH Adaptive for different values of $\gamma$ in Appendix.

We note that additional experiments in this section on more data sets are performed in Appendix.

References

Appendix

Useful Existing Results

Consider $v_{t}^{(s)}$ defined by (2) (or (8)) in SARAH (Algorithm 1) for any $s\geq 1$. Then for any $t\geq 1$,

Suppose that Assumptions 2 and 4 hold. Consider $v_{t}^{(s)}$ defined as (2) in SARAH (Algorithm 1) with $\eta<2/L$ for any $s\geq 1$. Then we have that for any $t\geq 0$,

Nonconvex SARAH

Lemma 1. Suppose that Assumption 1 holds. Consider SARAH (Algorithm 1) within a single outer loop with $\eta\leq\frac{2}{L(\sqrt{1+4m}+1)}$. Then, for any $s\geq 1$, we have

We use some parts of the proof in . By Assumption 1 and $w_{t+1}^{(s)}=w_{t}^{(s)}-\eta v_{t}^{(s)}$, for any $s\geq 1$, we have

Now, we would like to determine $\eta$ such that the expression in (17)

Let $\mathcal{F}_{j}=\sigma(w_{0},w_{1},\dots,w_{j})$ be the $\sigma$-algebra generated by $w_{0},w_{1},\dots,w_{j}$. Note that $\mathcal{F}_{j}$ also contains all information of $v_{0},\dots,v_{j-1}$. We have

Taking the expectations to both sides yields

Note that $\|\nabla F(w_{0}^{(s)})-v_{0}^{(s)}\|^{2}=0$. Hence, by summing over $t=0,\dots,m$ ($m\geq 1$), we have

By choosing $\eta\leq\frac{2}{L\left(\sqrt{1+4m}+1\right)}$, we have

since $\eta=\frac{2}{L\left(\sqrt{1+4m}+1\right)}$ is a root of equation $L^{2}\eta^{2}m-(1-L\eta)=0$. Therefore, with $\eta\leq\frac{2}{L(\sqrt{1+4m}+1)}$, we have

Proof of Corollary 1

Corollary 1. Suppose that Assumption 1 holds. Consider SARAH (Algorithm 1) with $\eta=\operatorname{\mathcal{O}}(\frac{1}{L\sqrt{m+1}})$ where $m$ is the inner loop size. Then, in order to achieve $\epsilon$-accurate solution, the total complexity is $\operatorname{\mathcal{O}}\left(\left[\left(\frac{n+2m}{\sqrt{m+1}}\right)\frac{1}{\epsilon}\right]\vee\left[n+2m\right]\right)$.

since $S\geq 1$. Therefore, the total complexity to achieve $\epsilon$-accurate solution is

Proof of Theorem 2

Theorem 2 (Smooth nonconvex with mini-batch). Suppose that Assumption 1 holds. Consider SARAH (Algorithm 1) by replacing $v_{t}$ in the inner loop size by (8) with

where $F^{*}$ is any lower bound of $F$, and $w_{t}^{(s)}$ is the $t$-th iteration in the $s$-th outer loop.

Following the proof of Lemma 1, we would like to determine $\eta$ such that the expression in (17)

Let $\mathcal{F}_{j}=\sigma(w_{0}^{(s)},I_{1},I_{2},\dots,I_{j-1})$ be the $\sigma$-algebra generated by $w_{0}^{(s)},I_{1},I_{2},\dots,I_{j-1}$; $\mathcal{F}_{0}=\mathcal{F}_{1}=\sigma(w_{0}^{(s)})$. Note that $\mathcal{F}_{j}$ also contains all the information of $w_{0}^{(s)},\dots,w_{j}^{(s)}$ as well as $v_{0}^{(s)},\dots,v_{j-1}^{(s)}$. We have

Note that $\|\nabla F(w_{0}^{(s)})-v_{0}^{(s)}\|^{2}=0$. Hence, by summing over $t=0,\dots,m$ ($m\geq 1$), we have

By choosing $\eta\leq\frac{2}{L\left(\sqrt{1+\frac{4m}{b}\left(\frac{n-b}{n-1}\right)}+1\right)}$, we have

since $\eta=\frac{2}{L\left(\sqrt{1+\frac{4m}{b}\left(\frac{n-b}{n-1}\right)}+1\right)}$ is a root of equation $\frac{1}{b}\left(\frac{n-b}{n-1}\right)L^{2}\eta^{2}m-(1-L\eta)=0$.

Therefore, with $\eta\leq\frac{2}{L\left(\sqrt{1+\frac{4m}{b}\left(\frac{n-b}{n-1}\right)}+1\right)}$, we have

where $F^{*}$ is any lower bound of $F$, and $w_{t}^{(s)}$ is the $t$-th iteration in the $s$-th outer loop. ∎

Proof of Corollary 3

Corollary 3. For the conditions in Theorem 2, in order to achieve an $\epsilon$-accurate solution, the total complexity is

In order to achieve the $\epsilon$-accurate solution, we need

since $S\geq 1$. Therefore, the total complexity is

Proof of Corollary 4

Corollary 4. For the conditions in Theorem 2 and Corollary 3 with $b=n^{\alpha}$ and $m=n^{\beta}$ where $\alpha+\beta=1$ with $\beta\geq 1/2$ and $0\leq\alpha\leq 1/2$, in order to achieve an $\epsilon$-accurate solution, the total complexity is

Let $b=n^{\alpha}$, $\alpha<1$, and $m=n^{\beta}$, we have

In order to minimize the order of $n$, we need to choose $1-\alpha/2-\beta/2=\alpha/2+\beta/2$, which is equivalent to $\alpha+\beta=1$ with $\beta\geq\alpha$. The best option is to choose $\alpha+\beta=1$ with $\beta\geq 1/2$ and $0\leq\alpha\leq 1/2$ in order to achieve $\operatorname{\mathcal{O}}(n^{1/2})$.

In order to minimize the order of $n$, we need to choose $1-\beta=\alpha$, which is equivalent to $\alpha+\beta=1$ with $\beta\leq\alpha$. The best option is to choose $\beta=1/2$ and $\alpha=1/2$ in order to achieve $\operatorname{\mathcal{O}}(n^{1/2})$.

Therefore, with $b=n^{\alpha}$ and $m=n^{\beta}$ where $\alpha+\beta=1$ with $\beta\geq 1/2$ and $0\leq\alpha\leq 1/2$, we have

By Corollary 3 with $bm=n^{\alpha+\beta}=n$, it implies the total complexity

Convex SARAH++

Lemma 2. Suppose that Assumptions 2 and 4 holds. Consider SARAH (Algorithm 1) within a single outer loop with $\eta\leq\frac{1}{L}$. Then, for $t\geq 0$ and any $s\geq 1$, we have

where $w_{*}$ is any optimal solution of $F$.

By using (16) and adding $-F(w_{*})$ for both sides, where $w_{*}=\arg\min_{w}F(w)$, we have

Proof of Theorem 3

Theorem 3 (Smooth general convex). Suppose that Assumptions 2 and 4 holds. Consider SARAH++ (Algorithm 3) with $\eta\leq\frac{\gamma}{L}$, $0<\gamma\leq 1$. Then, the expectation of the average of squared norm of gradient of all iterations generated by SARAH++

We recall the following definitions. $T_{s}$ is the stopping time (a random variable) of the $s$-th outer iteration such that

and $S$ is the stopping time of the outer iterations (a random variable) and such that for some $T>0$

Note that $T_{s}\geq 1$ is the first time such that $\|v_{T_{s}}^{(s)}\|^{2}<\gamma\|v_{0}^{(s)}\|^{2}$. Hence, for a given $T_{s}$, we have $\|v_{t}^{(s)}\|^{2}\geq\gamma\|v_{0}^{(s)}\|^{2}$, for $0\leq t\leq T_{s}-1$, and

where the last inequality follows since $\sum_{s=1}^{S}T_{s}\geq T$. Hence, by taking the expectation to both sides, we could have

Therefore, we achieve the desired result since the LHS is the expectation of the average of squared norm of gradient of all iterations generated by SARAH++ (Algorithm 3). ∎

Proof of Corollary 5

Corollary 5 (Smooth general convex). Consider the conditions in Theorem 3 with $\eta=\operatorname{\mathcal{O}}(\frac{1}{L})$. Then we could achieve the $\epsilon$-accurate solution after $\operatorname{\mathcal{O}}(\frac{1}{\epsilon})$ total iterations.

Proof of Theorem 4

Theorem 4 (Smooth strongly convex). Suppose that Assumptions 2, 3 and 4 holds. Consider SARAH++ (Algorithm 3) with $\eta\leq\frac{\gamma}{L}$, $0<\gamma\leq 1$. Then, for the final output $\hat{w}$ of SARAH++, we have

Following the beginning part of the proof of Theorem 3, we have, for a given $T_{s}$,

where the last inequality follows since $\sum_{s=1}^{S}T_{s}\geq T$. Hence, by taking the expectation to both sides, we could have

Proof of Corollary 6

Note that: $-\frac{1}{x}-1\leq-\frac{1}{\log(1+x)}\leq-\frac{1}{x}$, $-1<x<0$. We can have

By choosing $\eta=\operatorname{\mathcal{O}}(\frac{1}{L})$, we have $T=\operatorname{\mathcal{O}}(\kappa\log(\frac{1}{\epsilon}))$. ∎

Additional Experiments

We provide more experiments in this section on popular data sets with diverse size $n$ including covtype ($n=406,708$ training data; estimated $L\simeq 1.90$), ijcnn1 ($n=91,701$ training data; estimated $L\simeq 1.77$), w8a ($n=49,749$ training data, estimated $L\simeq 7.05$) and phishing ($n=7,738$ training data, estimated $L\simeq 7.49$) from LIBSVM.

Additional experiments in Section 3.3

Sensitivity of γ𝛾\gamma for SARAH Adaptive

In Figure 7 we present the numerical performance of SARAH Adaptive for different values of $\gamma=\left\{\frac{1}{2},\frac{1}{3},\frac{1}{4},\frac{1}{6},\frac{1}{8},\frac{1}{10},\frac{1}{12},\frac{1}{16}\right\}$ on covtype, ijcnn1, w8a, and phishing data sets.