Stochastic Nested Variance Reduction for Nonconvex Optimization

Introduction

We study the following nonconvex finite-sum problem

In this work, we mainly focus on first-order algorithms, which only need the function value and gradient evaluations. We use gradient complexity, the number of stochastic gradient evaluations, to measure the convergence of different first-order algorithms.While we use gradient complexity as in to present our result, it is basically the same if we use incremental first-order oracle (IFO) complexity used by . In other words, these are directly comparable. For nonconvex optimization, it is well-known that Gradient Descent (GD) can converge to an $\epsilon$-approximate stationary point with $O(n\cdot\epsilon^{-2})$ number of stochastic gradient evaluations. It can be seen that GD needs to calculate the full gradient at each iteration, which is a heavy load when $n\gg 1$. Stochastic Gradient Descent (SGD) has $O(\epsilon^{-4})$ gradient complexity to an $\epsilon$-approximate stationary point under the assumption that the stochastic gradient has a bounded variance . While SGD only needs to calculate a mini-batch of stochastic gradients in each iteration, due to the noise brought by stochastic gradients, its gradient complexity has a worse dependency on $\epsilon$. In order to improve the dependence of the gradient complexity of SGD on $n$ and $\epsilon$ for nonconvex optimization, variance reduction technique was firstly proposed in for convex finite-sum optimization. Representative algorithms include Stochastic Average Gradient (SAG) , Stochastic Variance Reduced Gradient (SVRG) , SAGA , Stochastic Dual Coordinate Ascent (SDCA) , Finito , Batching SVRG and SARAH , to mention a few. The key idea behind variance reduction is that the gradient complexity can be saved if the algorithm use history information as reference. For instance, one representative variance reduction method is SVRG, which is based on a semi-stochastic gradient that is defined by two reference points. Since the the variance of this semi-stochastic gradient will diminish when the iterate gets closer to the minimizer, it therefore accelerates the convergence of stochastic gradient method. Later on, Harikandeh et al. proposed Batching SVRG which also enjoys fast convergence property of SVRG without computing the full gradient. The convergence of SVRG under nonconvex setting was first analyzed in , where $F$ is still convex but each component function $f_{i}$ can be nonconvex. The analysis for the general nonconvex function $F$ was done by , which shows that SVRG can converge to an $\epsilon$-approximate stationary point with $O(n^{2/3}\cdot\epsilon^{-2})$ number of stochastic gradient evaluations. This result is strictly better than that of GD. Recently, Lei et al. proposed a Stochastically Controlled Stochastic Gradient (SCSG) based on variance reduction, which further reduces the gradient complexity of SVRG to $O(n\land\epsilon^{-2}+\epsilon^{-10/3}\land(n^{2/3}\epsilon^{-2}))$. This result outperforms both GD and SGD strictly. To the best of our knowledge, this is the state-of-art gradient complexity under the smoothness (i.e., gradient lipschitz) and bounded stochastic gradient variance assumptions. A natural and long standing question is:

Is there still room for improvement in nonconvex finite-sum optimization without making additional assumptions beyond smoothness and bounded stochastic gradient variance?

In this paper, we provide an affirmative answer to the above question, by showing that the dependence on $n$ in the gradient complexity of SVRG and SCSG can be further reduced. We propose a novel algorithm namely Stochastic Nested Variance-Reduced Gradient descent (SNVRG). Similar to SVRG and SCSG, our proposed algorithm works in a multi-epoch way. Nevertheless, the technique we developed is highly nontrivial. At the core of our algorithm is the multiple reference points-based variance reduction technique in each iteration. In detail, inspired by SVRG and SCSG, which uses two reference points to construct a semi-stochastic gradient with diminishing variance, our algorithm uses $K+1$ reference points to construct a semi-stochastic gradient, whose variance decays faster than that of the semi-stochastic gradient used in SVRG and SCSG.

Our major contributions are summarized as follows:

We propose a stochastic nested variance reduction technique for stochastic gradient method, which reduces the dependence of the gradient complexity on $n$ compared with SVRG and SCSG.

We show that our proposed algorithm is able to achieve an $\epsilon$-approximate stationary point with $\widetilde{O}(n\land\epsilon^{-2}+\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$ stochastic gradient evaluations, which outperforms all existing first-order algorithms such as GD, SGD, SVRG and SCSG.

As a by-product, when $F$ is a $\tau$-gradient dominated function, a variant of our algorithm can achieve an $\epsilon$-approximate global minimizer (i.e., $F(\mathbf{x})-\min_{\mathbf{y}}F(\mathbf{y})\leq\epsilon$) within \widetilde{O}\big{(}n\wedge\tau\epsilon^{-1}+\tau(n\wedge\tau\epsilon^{-1})^{1/2}\big{)} stochastic gradient evaluations, which also outperforms the state-of-the-art.

2 Additional Related Work

Since it is hardly possible to review the huge body of literature on convex and nonconvex optimization due to space limit, here we review some additional most related work on accelerating nonconvex (finite-sum) optimization.

Acceleration by high-order smoothness assumption With only Lipschitz continuous gradient assumption, Carmon et al. showed that the lower bound for both deterministic and stochastic algorithms to achieve an $\epsilon$-approximate stationary point is $\Omega(\epsilon^{-2})$. With high-order smoothness assumptions, i.e., Hessian Lipschitzness, Hessian smoothness etc., a series of work have shown the existence of acceleration. For instance, Agarwal et al. gave an algorithm based on Fast-PCA which can achieve an $\epsilon$-approximate stationary point with gradient complexity $\widetilde{O}(n\epsilon^{-3/2}+n^{3/4}\epsilon^{-7/4})$ Carmon et al. showed two algorithms based on finding exact or inexact negative curvature which can achieve an $\epsilon$-approximate stationary point with gradient complexity $\widetilde{O}(n\epsilon^{-7/4})$. In this work, we only consider gradient Lipschitz without assuming Hessian Lipschitz or Hessian smooth. Therefore, our result is not directly comparable to the methods in this category.

Acceleration by momentum The fact that using momentum is able to accelerate algorithms has been shown both in theory and practice in convex optimization . However, there is no evidence that such acceleration exists in nonconvex optimization with only Lipschitz continuous gradient assumption . If $F$ satisfies $\lambda$-strongly nonconvex, i.e., $\nabla^{2}F\succeq-\lambda\mathbf{I}$, Allen-Zhu proved that Natasha $1$, an algorithm based on nonconvex momentum, is able to find an $\epsilon$-approximate stationary point in $\widetilde{O}(n^{2/3}L^{2/3}\lambda^{1/3}\epsilon^{-2})$. Later, Allen-Zhu further showed that Natasha 2, an online version of Natasha 1, is able to achieve an $\epsilon$-approximate stationary point within $\widetilde{O}(\epsilon^{-3.25})$ stochastic gradient evaluationsIn fact, Natasha 2 is guaranteed to converge to an $(\epsilon,\sqrt{\epsilon})$-approximate second-order stationary point with $\widetilde{O}(\epsilon^{-3.25})$ gradient complexity, which implies the convergence to an $\epsilon$-approximate stationary point..

After our paper was submitted to NIPS and released on arXiv, a paper was released on arXiv after our work, which independently proposes a different algorithm and achieves the same convergence rate for finding an $\epsilon$-approximate stationary point.

To give a thorough comparison of our proposed algorithm with existing first-order algorithms for nonconvex finite-sum optimization, we summarize the gradient complexity of the most relevant algorithms in Table 1. We also plot the gradient complexities of different algorithms in Figure 1 for nonconvex smooth functions. Note that GD and SGD are always worse than SVRG and SCSG according to Table 1. In addition, GNC-AGD and Natasha2 needs additional Hessian Lipschitz condition. Therefore, we only plot the gradient complexity of SVRG, SCSG and our proposed SNVRG in Figure 1.

Preliminaries

In this section, we present some definitions that will be used throughout our analysis.

$\sigma^{2}$ is called the upper bound on the variance of stochastic gradients .

We also consider a class of functions namely gradient dominated functions , which is formally defined as follows:

Note that gradient dominated condition is also known as the Polyak-Lojasiewicz (P-L) condition , and is not necessarily convex. It is weaker than strong convexity as well as other popular conditions that appear in the optimization literature .

The Proposed Algorithm

In this section, we present our nested stochastic variance reduction algorithm, namely, SNVRG.

One-epoch-SNVRG: We first present the key component of our main algorithm, One-epoch-SNVRG, which is displayed in Algorithm 1. The most innovative part of Algorithm 1 attributes to the $K+1$ reference points and $K+1$ reference gradients. Note that when $K=1$, Algorithm 1 reduces to one epoch of SVRG algorithm . To better understand our One-epoch SNVRG algorithm, it would be helpful to revisit the original SVRG which is a special case of our algorithm. For the finite-sum optimization problem in (1.1), the original SVRG takes the following updating formula

where $\eta>0$ is the step size, $i_{t}$ is a random index uniformly chosen from $[n]$ and $\widetilde{\mathbf{x}}$ is a snapshot for $\mathbf{x}_{t}$ after every $T_{1}$ iterations. There are two reference points in the update formula at $\mathbf{x}_{t}$: $\mathbf{x}_{t}^{(0)}=\widetilde{\mathbf{x}}$ and $\mathbf{x}_{t}^{(1)}=\mathbf{x}_{t}$. Note that $\widetilde{\mathbf{x}}$ is updated every $T_{1}$ iterations, namely, $\widetilde{\mathbf{x}}$ is set to be $\mathbf{x}_{t}$ only when $(t\mod T_{1})=0$. Moreover, in the semi-stochastic gradient $\mathbf{v}_{t}$, there are also two reference gradients and we denote them by $\mathbf{g}_{t}^{(0)}=\nabla F(\widetilde{\mathbf{x}})$ and $\mathbf{g}_{t}^{(1)}=\nabla f_{i_{t}}(\mathbf{x}_{t})-\nabla f_{i_{t}}(\widetilde{\mathbf{x}})=\nabla f_{i_{t}}(\mathbf{x}_{t}^{(1)})-\nabla f_{i_{t}}(\mathbf{x}_{t}^{(0)})$.

Back to our One-epoch-SNVRG, we can define similar reference points and reference gradients as that in the special case of SVRG. Specifically, for $t=0,\ldots,\prod_{l=1}^{K}T_{l}-1$, each point $\mathbf{x}_{t}$ has $K+1$ reference points $\{\mathbf{x}_{t}^{(l)}\},l=0,\ldots,K$, which is set to be $\mathbf{x}_{t}^{(l)}=\mathbf{x}_{t^{l}}$ with index $t^{l}$ defined as

Specially, note that we have $\mathbf{x}_{t}^{(0)}=\mathbf{x}_{0}$ and $\mathbf{x}_{t}^{(K)}=\mathbf{x}_{t}$ for all $t=0,\ldots,\prod_{l=1}^{K}T_{l}-1$. Similarly, $\mathbf{x}_{t}$ also has $K+1$ reference gradients $\{\mathbf{g}_{t}^{(l)}\}$, which can be defined based on the reference points $\{\mathbf{x}_{t}^{(l)}\}$:

where $I,I_{l}$ are random index sets with $|I|=B,|I_{l}|=B_{l}$ and are uniformly generated from $[n]$ without replacement. Based on the reference points and reference gradients, we then update $\mathbf{x}_{t+1}=\mathbf{x}_{t}-1/(10M)\cdot\mathbf{v}_{t}$, where $\mathbf{v}_{t}=\sum_{l=0}^{K}\mathbf{g}_{t}^{(l)}$ and $M$ is the step size parameter. The illustration of reference points and gradients of SNVRG is displayed in Figure 2.

We remark that it would be a huge waste for us to re-evaluate $\mathbf{g}_{t}^{(l)}$ at each iteration. Fortunately, due to the fact that each reference point is only updated after a long period, we can maintain $\mathbf{g}_{t}^{(l)}=\mathbf{g}_{t-1}^{(l)}$ and only need to update $\mathbf{g}_{t}^{(l)}$ when $\mathbf{x}_{t}^{(l)}$ has been updated as is suggested by Line 24 in Algorithm 1.

SNVRG: Using One-epoch-SNVRG (Algorithm 1) as a building block, we now present our main algorithm: Algorithm 2 for nonconvex finite-sum optimization to find an $\epsilon$-approximate stationary point. At each iteration of Algorithm 2, it executes One-epoch-SNVRG (Algorithm 1) which takes $\mathbf{z}_{s-1}$ as its input and outputs $[\mathbf{y}_{s},\mathbf{z}_{s}]$. We choose $\mathbf{y}_{\text{out}}$ as the output of Algorithm 2 uniformly from $\{\mathbf{y}_{s}\}$, for $s=1,\ldots,S$.

SNVRG-PL: In addition, when function $F$ in (1.1) is gradient dominated as defined in Definition 2.6 (P-L condition), it has been proved that the global minimum can be found by SGD , SVRG and SCSG very efficiently. Following a similar trick used in , we present Algorithm 3 on top of Algorithm 2, to find the global minimum in this setting. We call Algorithm 3 SNVRG-PL, because gradient dominated condition is also known as Polyak-Lojasiewicz (PL) condition .

Space complexity: We briefly compare the space complexity between our algorithms and other variance reduction based algorithms. SVRG and SCSG needs $O(d)$ space complexity to store one reference gradient, SAGA needs to store reference gradients for each component functions, and its space complexity is $O(nd)$ without using any trick. For our algorithm SNVRG, we need to store $K$ reference gradients, thus its space complexity is $O(Kd)$. In our theory, we will show that $K=O(\log\log n)$. Therefore, the space complexity of our algorithm is actually $\widetilde{O}(d)$, which is almost comparable to that of SVRG and SCSG.

Main Theory

In this section, we provide the convergence analysis of SNVRG.

We first analyze One-epoch-SNVRG (Algorithm 1) and provide a particular choice of parameters.

Suppose that $F$ has averaged $L$-Lipschitz gradient, in Algorithm 1, suppose $B\geq 2$ and let the number of nested loops be $K=\log\log B$. Choose the step size parameter as $M=6L$. For the loop and batch parameters, let $T_{1}=2,B_{1}=6^{K}\cdot B$ and

for all $2\leq l\leq K$. Then the output of Algorithm 1 $[\mathbf{x}_{\text{out}},\mathbf{x}_{T}]$ satisfies

within $1\lor(7B\log^{3}B)$ stochastic gradient computations, where $T=\prod_{l=1}^{K}T_{l}$, $C=600$ is a constant and $\operatorname{\mathds{1}}(\cdot)$ is the indicator function.

The following theorem shows the gradient complexity for Algorithm 2 to find an $\epsilon$-approximate stationary point with a constant base batch size $B$.

stochastic gradient computations, where $\Delta_{F}=F(\mathbf{z}_{0})-F^{*}$.

If we treat $\sigma^{2},L$ and $\Delta_{F}$ as constants, and assume $\epsilon\ll 1$, then (4.2) can be simplified to $\widetilde{O}(\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$. This gradient complexity is strictly better than $O(\epsilon^{-10/3}\land n^{2/3}\epsilon^{-2})$, which is achieved by SCSG . Specifically, when $n\lesssim 1/\epsilon^{2}$, our proposed SNVRG is faster than SCSG by a factor of $n^{1/6}$; when $n\gtrsim 1/\epsilon^{2}$, SNVRG is faster than SCSG by a factor of $\epsilon^{-1/3}$. Moreover, SNVRG also outperforms Natasha 2 which attains $\widetilde{O}(\epsilon^{-3.25})$ gradient complexity and needs the additional Hessian Lipschitz condition.

2 Convergence of SNVRG-PL

We now consider the case when $F$ is a $\tau$-gradient dominated function. In general, we are able to find an $\epsilon$-approximate global minimizer of $F$ instead of only an $\epsilon$-approximate stationary point. Algorithm 3 uses Algorithm 2 as a component.

stochastic gradient computations, where $\Delta_{F}=F(\mathbf{z}_{0})-F^{*}$

If we treat $\sigma^{2}$, $L$ and $\Delta_{F}$ as constants, then the gradient complexity in (4.3) turns into $\widetilde{O}(n\land\tau\epsilon^{-1}+\tau(n\land\tau\epsilon^{-1})^{1/2})$. Compared with nonconvex SVRG which achieves $\widetilde{O}(n+\tau n^{2/3})$ gradient complexity, our SNVRG-PL is strictly better than SVRG in terms of the first summand and is faster than SVRG at least by a factor of $n^{1/6}$ in terms of the second summand. Compared with a more general variant of SVRG, namely, the SCSG algorithm , which attains \widetilde{O}\big{(}n\wedge\tau\epsilon^{-1}+\tau(n\wedge\tau\epsilon^{-1})^{2/3}\big{)} gradient complexity, SNVRG-PL also outperforms it by a factor of $(n\land\tau\epsilon^{-1})^{1/6}$.

If we further assume that $F$ is $\lambda$-strongly convex, then it is easy to verify that $F$ is also $1/(2\lambda)$-gradient dominated. As a direct consequence, we have the following corollary:

Under the same conditions and parameter choices as Theorem 4.4. If we additionally assume that $F$ is $\lambda$-strongly convex, then Algorithm 3 will outputs an $\epsilon$-approximate global minimizer within

stochastic gradient computations, where $\kappa=L/\lambda$ is the condition number of $F$.

Corollary 4.6 suggests that when we regard $\lambda$ and $\sigma^{2}$ as constants and set $\epsilon\ll 1$, Algorithm 3 is able to find an $\epsilon$-approximate global minimizer within $\widetilde{O}(n+n^{1/2}\kappa)$ stochastic gradient computations, which matches SVRG-lep in Katyusha X . Using catalyst techniques or Katyusha momentum , it can be further accelerated to $\widetilde{O}(n+n^{3/4}\sqrt{\kappa})$, which matches the best-known convergence rate .

Experiments

In this section, we compare our algorithm SNVRG with other baseline algorithms on training a convolutional neural network for image classification. We compare the performance of the following algorithms: SGD; SGD with momentum (denoted by SGD-momentum); ADAM; SCSG . It is worth noting that SCSG is a special case of SNVRG when the number of nested loops $K=1$. Due to the memory cost, we did not compare GD and SVRG which need to calculate the full gradient. Although our theoretical analysis holds for general $K$ nested loops, it suffices to choose $K=2$ in SNVRG to illustrate the effectiveness of the nested structure for the simplification of implementation. In this case, we have $3$ reference points and gradients. All experiments are conducted on Amazon AWS p2.xlarge servers which comes with Intel Xeon E5 CPU and NVIDIA Tesla K80 GPU (12G GPU RAM). All algorithm are implemented in Pytorch platform version $0.4.0$ within Python $3.6.4$.

Datasets We use three image datasets: (1) The MNIST dataset consists of handwritten digits and has $50,000$ training examples and $10,000$ test examples. The digits have been size-normalized to fit the network, and each image is 28 pixels by 28 pixels. (2) CIFAR10 dataset consists of images in 10 classes and has $50,000$ training examples and $10,000$ test examples. The digits have been size-normalized to fit the network, and each image is 32 pixels by 32 pixels. (3) SVHN dataset consists of images of digits and has $531,131$ training examples and $26,032$ test examples. The digits have been size-normalized to fit the network, and each image is 32 pixels by 32 pixels.

CNN Architecture We use the standard LeNet , which has two convolutional layers with 6 and 16 filters of size 5 respectively, followed by three fully-connected layers with output size 120, 84 and 10. We apply max pooling after each convolutional layer.

Implementation Details & Parameter Tuning We did not use the random data augmentation which is set as default by Pytorch, because it will apply random transformation (e.g., clip and rotation) at the beginning of each epoch on the original image dataset, which will ruin the finite-sum structure of the loss function. We set our grid search rules for all three datasets as follows. For SGD, we search the batch size from $\{256,512,1024,2048\}$ and the initial step sizes from $\{1,0.1,0.01\}$. For SGD-momentum, we set the momentum parameter as $0.9$. We search its batch size from $\{256,512,1024,2048\}$ and the initial learning rate from $\{1,0.1,0.01\}$. For ADAM, we search the batch size from $\{256,512,1024,2048\}$ and the initial learning rate from $\{0.01,0.001,0.0001\}$. For SCSG and SNVRG, we choose loop parameters $\{T_{l}\}$ which satisfy $B_{l}\cdot\prod_{j=1}^{l}T_{j}=B$ automatically. In addition, for SCSG, we set the batch sizes $(B,B_{1})=(B,B/b)$, where $b$ is the batch size ratio parameter. We search $B$ from $\{256,512,1024,2048\}$ and we search $b$ from $\{2,4,8\}$. We search its initial learning rate from $\{1,0.1,0.01\}$. For our proposed SNVRG, we set the batch sizes $(B,B_{1},B_{2})=(B,B/b,B/b^{2})$, where $b$ is the batch size ratio parameter. We search $B$ from $\{256,512,1024,2048\}$ and $b$ from $\{2,4,8\}$. We search its initial learning rate from $\{1,0.1,0.01\}$. Following the convention of deep learning practice, we apply learning rate decay schedule to each algorithm with the learning rate decayed by $0.1$ every 20 epochs. We also conducted experiments based on plain implementation of different algorithms without learning rate decay, which is deferred to the appendix.

We plotted the training loss and test error for different algorithms on each dataset in Figure 3. The results on MNIST are presented in Figures 3(a) and 3(d); the results on CIFAR10 are in Figures 3(b) and 3(e); and the results on SVHN dataset are shown in Figures 3(c) and 3(f). It can be seen that with learning rate decay schedule, our algorithm SNVRG outperforms all baseline algorithms, which confirms that the use of nested reference points and gradients can accelerate the nonconvex finite-sum optimization.

We would like to emphasize that, while this experiment is on training convolutional neural networks, the major goal of this experiment is to illustrate the advantage of our algorithm and corroborate our theory, rather than claiming a state-of-the-art algorithm for training deep neural networks.

Conclusions and Future Work

In this paper, we proposed a stochastic nested variance reduced gradient method for finite-sum nonconvex optimization. It achieves substantially better gradient complexity than existing first-order algorithms. This partially resolves a long standing question that whether the dependence of gradient complexity on $n$ for nonconvex SVRG and SCSG can be further improved. There is still an open question: whether $\widetilde{O}(n\land\epsilon^{-2}+\epsilon^{-3}\land n^{1/2}\epsilon^{-2})$ is the optimal gradient complexity for finite-sum and stochastic nonconvex optimization problem? For finite-sum nonconvex optimization problem, the lower bound has been proved in Fang et al. , which suggests that our algorithm is near optimal up to a logarithmic factor. However, for general stochastic problem, the lower bound is still unknown. We plan to derive such lower bound in our future work. On the other hand, our algorithm can also be extended to deal with nonconvex nonsmooth finite-sum optimization using proximal gradient .

Acknowledgement

We would like to thank the anonymous reviewers for their helpful comments. This research was sponsored in part by the National Science Foundation IIS-1652539 and BIGDATA IIS-1855099. We also thank AWS for providing cloud computing credits associated with the NSF BIGDATA award. The views and conclusions contained in this paper are those of the authors and should not be interpreted as representing any funding agencies.

References

Appendix A Proof of the Main Theoretical Results

In this section, we provide the proofs of our main theories in Section 4.

We first prove our key lemma on One-epoch-SNVRG. In order to prove Lemma 4.1, we need the following supporting lemma:

Let $T=\prod_{l=1}^{K}T_{l}$. If the step size and batch size parameters in Algorithm 1 satisfy $M\geq 6L$ and $B_{l}\geq 6^{K-l+1}(\prod_{s=l}^{K}T_{s})^{2}$, then the output of Algorithm 1 satisfies

Note that $B=2^{2^{K}}$, we can easily check that the choice of $M,\{T_{l}\},\{B_{l}\}$ in Lemma 4.1 satisfies the assumption of Lemma A.1. Moreover, we have

We now submit (A.2) into (A.1), which immediately implies (4.1).

Next we compute how many stochastic gradient computations we need in total after we run One-epoch-SNVRG once. According to the update of reference gradients in Algorithm 1, we only update $\mathbf{g}_{t}^{(0)}$ once at the beginning of Algorithm 1 (Line 4), which needs $B$ stochastic gradient computations. For $\mathbf{g}_{t}^{(l)}$, we only need to update it when $0=(t\mod\prod_{j=l+1}^{K}T_{j})$, and thus we need to sample $\mathbf{g}_{t}^{(l)}$ for $T/\prod_{j=l+1}^{K}T_{j}=\prod_{j=1}^{l}T_{j}$ times. We need $2B_{l}$ stochastic gradient computations for each sampling procedure (Line 24 in Algorithm 1). We use ${\mathcal{T}}$ to represent the total number of stochastic gradient computations, then based on above arguments we have

Now we calculate ${\mathcal{T}}$ under the parameter choice of Lemma 4.1. Note that we can easily verify the following results:

Submit (A.4) into (A.3) yields the following results:

Therefore, the total gradient complexity ${\mathcal{T}}$ is bounded as follows.

A.2 Proof of Theorem 4.2

Now we prove our main theorem which spells out the gradient complexity of SNVRG.

where $C=600$. Taking summation for (A.7) over $s$ from $1$ to $S$, we have

Dividing both sides of (A.8) by $S$, we immediately obtain

where (A.9) holds because $F(\mathbf{z}_{S})\geq F^{*}$ and by the definition $\Delta_{F}=F(\mathbf{z}_{0})-F^{*}$. By the choice of parameters in Theorem 4.2, we have $B=n\land(2C\sigma^{2}/\epsilon^{2}),S=1\lor(2CL\Delta_{F}/(B^{1/2}\epsilon^{2}))$, which implies

A.3 Proof of Theorem 4.4

We then prove the main theorem on gradient complexity of SNVRG under gradient dominance condition (Algorithm 3).

Following the proof of Theorem 4.2, we obtain a similar inequality with (A.9):

where the second inequality holds due to the choice of parameters $B=n\land(4C_{1}\tau\sigma^{2}/\epsilon)$ and $S=1\lor(2C_{1}\tau L/B^{1/2})$ for Algorithm 3 in Theorem 4.4. By (A.14) we can derive

Appendix B Proof of Key Lemma A.1

In this section, we focus on proving Lemma A.1 which plays a pivotal role in proving our main theorems. Let $M,\{T_{i}\},\{B_{i}\},B$ be the parameters as defined in Algorithm 1. We denote $T=\prod_{l=1}^{K}T_{l}$. We define filtration $\mathcal{F}_{t}=\sigma(\mathbf{x}_{0},\dots,\mathbf{x}_{t})$. Let $\{\mathbf{x}_{t}^{(l)}\},\{\mathbf{g}_{t}^{(l)}\}$ be the reference points and reference gradients in Algorithm 1. We define $\mathbf{v}_{t}^{(l)}$ as

We first present the following definition and two technical lemmas for the purpose of our analysis.

We define constant series $\{c^{(s)}_{j}\}$ as the following. For each $s$, we define $c^{(s)}_{T_{s}}$ as

When $0\leq j<T_{s}$, we define $c^{(s)}_{j}$ by induction:

For any $p,s$, where $1\leq s\leq K$ and $0\leq p\prod_{j=s}^{K}T_{j}<(p+1)\prod_{j=s}^{K}T_{j}\leq\prod_{j=1}^{K}T_{j}$, we define

for simplification. Then we have the following results:

Let $\mathbf{a}_{i}$ be vectors satisfying $\sum_{i=1}^{N}\mathbf{a}_{i}=0$. Let $\mathcal{J}$ be a uniform random subset of $\{1,\dots,N\}$ with size $m$, then

where the second inequality comes from Lemma B.2 with we take $s=1,p=0$. Moreover we have

where (B.5) holds because of Lemma B.3. Plug (B.6) into (B.4) and note that we have $M=6L$, and then we obtain

where $C=100$. Divide both sides of (B.7) by $T$, then Lemma A.1 holds trivially. ∎

Appendix C Proof of Technical Lemmas

In this section, we provide the proofs of technical lemmas used in Appendix B.

Let $M,\{T_{l}\},\{B_{l}\},B$ be the parameters defined in Algorithm 1 and $\{\mathbf{x}_{t}^{(l)}\},\{\mathbf{g}_{t}^{(l)}\}$ be the reference points and reference gradients defined in Algorithm 1. Let $\mathbf{v}_{t}^{(l)},\mathcal{F}_{t}$ be the variables and filtration defined in Appendix B and let $c_{j}^{(s)}$ be the constant series defined in Definition B.1.

In order to prove Lemma B.2, we will need the following supporting propositions and lemmas. We first state the proposition about the relationship among $\mathbf{x}_{t}^{(s)},\mathbf{g}_{t}^{(s)}$ and $\mathbf{v}_{t}^{(s)}$:

Let $\mathbf{v}_{t}^{(l)}$ be defined as in (B.1). Let $p,s$ satisfy $0\leq p\cdot\prod_{j=s+1}^{K}T_{j}<(p+1)\cdot\prod_{j=s+1}^{K}T_{j}<T$. For any $t,t^{\prime}$ satisfying $p\cdot\prod_{j=s+1}^{K}T_{j}\leq t<t^{\prime}<(p+1)\cdot\prod_{j=s+1}^{K}T_{j}$, it holds that

The following lemma spells out the relationship between $c_{j}^{(s-1)}$ and $c^{(s)}_{T_{s}}$. In a word, $c_{j}^{(s-1)}$ is about $1+T_{s-1}$ times less than $c^{(s)}_{T_{s}}$:

If $B_{s}\geq 6^{K-s+1}(\prod_{l=s}^{K}T_{l})^{2},T_{l}\geq 1$ and $M\geq 6L$, then it holds that

Next lemma is a special case of Lemma B.2 with $s=K$:

Suppose $p$ satisfies $0\leq pT_{K}<(p+1)T_{K}\leq\prod_{i=1}^{K}T_{i}$. If $M>L$, then we have

Let $t^{l}$ be as defined in (3.1), then we have $\mathbf{x}_{t}^{(l)}=\mathbf{x}_{t^{l}}$, and

We use mathematical induction to prove that Lemma B.2 holds for any $1\leq s\leq K$. When $s=K$, the statement holds because of Lemma C.3. Suppose that for $s+1$, Lemma B.2 holds for any $p^{\prime}$ which satisfies $0\leq p^{\prime}\prod_{j=s+1}^{K}T_{j}<(p^{\prime}+1)\prod_{j=s+1}^{K}T_{j}\leq\prod_{j=1}^{K}T_{j}$. We need to prove Lemma B.2 still holds for $s$ and $p$, where $p$ satisfies $0\leq p\prod_{j=s}^{K}T_{j}<(p+1)\prod_{j=s}^{K}T_{j}\leq\prod_{j=1}^{K}T_{j}$. We first define $m=\prod_{j=s+1}^{K}T_{j}$ for simplification, then we choose $p^{\prime}=pT_{s}+u$, and we set indices $\text{start}_{u}$ and $\text{end}_{u}$ as

It can be easily verified that the following relationship also holds:

where the last inequality holds because of the induction hypothesis that Lemma B.2 holds for $s+1$ and $p^{\prime}$. Note that we have $\mathbf{x}_{\text{start}_{u}}=\mathbf{x}_{\text{start}+u\cdot m}=\mathbf{x}_{\text{start}_{u}}^{(s)}$ from Proposition C.1, which implies

Next we bound $\|\mathbf{x}_{\text{start}+(u+1)\cdot m}-\mathbf{x}_{\text{start}}\|_{2}^{2}$ as the following:

Adding up inequalities(C.15) and (C.12) together yields

We now telescope the above inequality for $u=0$ to $T_{s}-1$, then we have

Since $\text{start}_{u}=\text{end}_{u-1},\text{start}_{0}=\text{start}$, and $\text{end}_{T_{s}-1}=\text{end}$, we have

Therefore, we have proved that Lemma B.2 still holds for $s$ and $p$. Then by mathematical induction, we have for all $1\leq s\leq K$ and $p$ which satisfy $0\leq p\cdot\prod_{j=s}^{K}T_{j}<(p+1)\cdot\prod_{j=s}^{K}T_{j}\leq\prod_{j=1}^{K}T_{j}$, Lemma B.2 holds. ∎

C.2 Proof of Lemma B.3

The following proof is adapted from that of Lemma A.1 in Lei et al. . We provide the proof here for the self-containedness of our paper.

We only consider the case when $m<N$. Let $W_{j}=\operatorname{\mathds{1}}(j\in\mathcal{J})$, then we have

Appendix D Proofs of the Auxiliary Lemmas

In this section, we present the additional proofs of supporting lemmas used in Appendix C. Let $M,\{T_{l}\},\{B_{l}\}$ and $B$ be the parameters defined in Algorithm 1. Let $\{\mathbf{x}_{t}^{(l)}\},\{\mathbf{g}_{t}^{(l)}\}$ be the reference points and reference gradients used in Algorithm 1. Finally, $\mathbf{v}_{t}^{(l)},\mathcal{F}_{t}$ are the variables and filtration defined in Appendix B and $c_{j}^{(s)}$ are the constant series defined in Definition B.1.

By the definition of reference point $\mathbf{x}_{t}^{(s)}$ in (3.1), we can easily verify that (C.1) holds trivially.

Next we prove (C.2). Note that by (C.1) we have $\mathbf{x}_{t}^{(s)}=\mathbf{x}_{t^{\prime}}^{(s)}$. For any $0\leq s^{\prime}\leq s$, it is also true that $\mathbf{x}_{t}^{(s^{\prime})}=\mathbf{x}_{t^{\prime}}^{(s^{\prime})}$ by (3.1), which means $\mathbf{x}_{t}$ and $\mathbf{x}_{t^{\prime}}$ share the same first $s+1$ reference points. Then by the update rule of $\mathbf{g}_{t}^{(s^{\prime})}$ in Algorithm 1, we will maintain $\mathbf{g}_{t}^{(s^{\prime})}$ unchanged from time step $t$ to ${t^{\prime}}$. In other worlds, we have $\mathbf{g}_{t}^{(s^{\prime})}=\mathbf{g}_{t^{\prime}}^{(s^{\prime})}$ for all $0\leq s^{\prime}\leq s$.

We now prove the last claim (C.3). Based on (B.1) and (C.2), we have $\mathbf{v}_{t}^{(s)}=\sum_{s^{\prime}=0}^{s}\mathbf{g}_{t}^{(s^{\prime})}=\sum_{s^{\prime}=0}^{s}\mathbf{g}_{p\cdot\prod_{j=s+1}^{K}T_{j}}^{(s^{\prime})}=\mathbf{v}_{p\cdot\prod_{j=s+1}^{K}T_{j}}^{(s)}$. Since for any $s\leq s^{\prime\prime}\leq K$, we have the following equations by the update in Algorithm 1 (Line 18).

Then for any $s<s^{\prime\prime}\leq K$, we have

where the first equality holds because of the definition of $\mathbf{v}_{p\cdot\prod_{j=s+1}^{K}T_{j}}$ , the second equality holds due to (D.1) , the third equality holds due to (C.2) and the last equality holds due to (B.1). This completes the proof of (C.3). ∎

D.2 Proof of Lemma C.2

For any fixed $s$, it can be seen that from the definition in (B.3), $c_{j}^{(s)}$ is monotonically decreasing with $j$. In order to prove (C.4), we only need to compare $(1+T_{s-1})\cdot c_{0}^{(s-1)}$ and $c^{(s)}_{T_{s}}$. Furthermore, by the definition of series $\{c^{(s)}_{j}\}$ in (B.3), it can be inducted that when $0\leq j\leq T_{s-1}$,

where (D.4) holds because $(1+1/n)^{n}<2.8$ for any $n\geq 1$, (D.5) holds due to the definition of $c_{T_{s-1}}^{(s-1)}$ in (B.2) and $B_{s-1}\geq 6^{K-s+2}(\prod_{l=s-1}^{K}T_{l})^{2}$ and (D.6) holds because $M\geq 6L$. Recall that $c_{j}^{(s)}$ is monotonically decreasing with $j$ and the inequality in (D.6). Thus for all $2\leq s\leq K$ and $0\leq j\leq T_{s-1}$, we have

where the third inequality holds because $(1+T_{s-1})/T_{s-1}\leq 2$ when $T_{s-1}\geq 1$ and the last equation comes from the definition of $c_{T_{s}}^{s}$ in (B.2). This completes the proof of (C.4).

Using similar techniques, we can obtain the upper bound for $c_{0}^{K}$ which is similar to inequality (D.6) with $s-1$ replaced by $K$. Therefore, we have

D.3 Proof of Lemma C.3

Now we prove Lemma C.3, which is a special case of Lemma B.2 if we choose $s=K$.

where (D.9) is due to the $L$-smoothness of $F$, which can be verified as follows

(D.10) holds because $\langle\mathbf{v}_{p\cdot T_{K}+j},\mathbf{h}_{p\cdot T_{K}+j}\rangle+5M\|\mathbf{h}_{p\cdot T_{K}+j}\|_{2}^{2}=-5M\|\mathbf{h}_{p\cdot T_{K}+j}\|_{2}^{2}\leq 0$. Further by Young’s inequality, we obtain

where the second inequality holds because $M>L$. Now we bound the term $c^{(K)}_{j+1}\|\mathbf{x}_{p\cdot T_{K}+j+1}-\mathbf{x}_{p\cdot T_{K}}\|_{2}^{2}$. By (D.8) we have

Adding up inequalities (D.12) and (D.11), we get

where the last inequality holds due to the fact that $c^{(K)}_{j+1}(1+T_{K})<M$ by Lemma C.2. Next we bound $\|\nabla F(\mathbf{x}_{p\cdot T_{K}+j})\|_{2}^{2}$ with $\|\mathbf{h}_{p\cdot T_{K}+j}\|_{2}^{2}$. Note that by (D.8), we have

Next we bound $\|\nabla F(\mathbf{x}_{p\cdot T_{K}+j})-\mathbf{v}_{p\cdot T_{K}+j}\|_{2}^{2}$. First, by Lemma C.4 we have

Since $\mathbf{x}_{p\cdot T_{K}+j}^{(K)}=\mathbf{x}_{p\cdot T_{K}+j},\mathbf{v}_{p\cdot T_{K}+j}^{(K)}=\mathbf{v}_{p\cdot T_{K}+j}$, $\mathbf{x}_{p\cdot T_{K}+j}^{(K-1)}=\mathbf{x}_{p\cdot T_{K}}$ and $\mathbf{v}_{p\cdot T_{K}+j}^{(K-1)}=\mathbf{v}_{p\cdot T_{K}}$, we have

where (D.17) holds because we have $c^{(K)}_{j}=c^{(K)}_{j+1}(1+1/T_{K})+3L^{2}/(B_{K}M)$ by Definition B.1. Telescoping (D.17) for $j=0$ to $T_{K}-1$, we have

D.4 Proof of Lemma C.4

If $t^{l}=t^{l-1}$, we have $\mathbf{x}_{t}^{(l)}=\mathbf{x}_{t}^{(l-1)}$ and $\mathbf{v}_{t}^{(l)}=\mathbf{v}_{t}^{(l-1)}$. In this case the statement in Lemma C.4 holds trivially. Therefore, we assume $t^{l}\neq t^{l-1}$ in the following proof. Note that

Therefore, we can apply Lemma B.3 to (D.20) and obtain

Next we turn to bound term $J_{2}$. Note that

where the last equation is due to the definition of $\mathcal{F}_{t}$. Plugging $J_{1}$ and $J_{2}$ into (D.19) yields the following result:

Appendix E Additional Experimental Results

We also conducted experiments comparing different algorithms without the learning rate decay schedule. The parameters are tuned by the same grid search described in Section 5. In particular, we summarize the parameters of different algorithms used in our experiments with and without learning rate decay for MNIST in Table 2, CIFAR10 in Table 3, and SVHN in Table 4. We plotted the training loss and test error for each dataset without learning rate decay in Figure 4. The results on MNIST are presented in Figures 4(a) and 4(d); the results on CIFAR10 are in Figures 4(b) and 4(e); and the results on SVHN dataset are shown in Figures 4(c) and 4(f). It can be seen that without learning decay, our algorithm SNVRG still outperforms all the baseline algorithms except for the training loss on SVHN dataset. However, SNVRG still performs the best in terms of test error on SVHN dataset. These results again suggest that SNVRG can beat the state-of-the-art in practice, which backups our theory.

Appendix F An Equivalent Version of Algorithm 1

Recall the One-epoch-SNVRG algorithm in Algorithm 1. Here we present an equivalent version of Algorithm 1 using nested loops, which is displayed in Algorithm 4 and is more aligned with the illustration in Figure 2. Note that the notation used in Algorithm 4 is slightly different from that in Algorithm 1 to avoid confusion.