A Non-asymptotic comparison of SVRG and SGD: tradeoffs between compute and speed
Authors: Qingru Zhang
Yuhuai Wu
Fartash Faghri
Tianzong Zhang
Jimmy Ba
Venue:  (2020)
Keywords: variance reduction
non-asymptotic analysis
trade-off
computational cost
convergence speed

Abstract: Stochastic gradient descent (SGD), which  trades off noisy gradient updates for computational efficiency, is the de-facto optimization algorithm to solve large-scale machine learning problems. SGD can make rapid learning progress by performing updates using subsampled training data, but the noisy updates also lead to slow asymptotic convergence.   Several variance reduction algorithms, such as SVRG, introduce control variates to obtain a lower variance gradient estimate and faster convergence.  Despite their appealing asymptotic guarantees, SVRG-like algorithms have not been widely adopted in deep learning. The traditional asymptotic analysis in stochastic optimization provides limited insight into training deep learning models under a fixed number of epochs. In this paper, we present a non-asymptotic analysis of SVRG under a noisy least squares regression problem. Our primary focus is to compare the exact loss of SVRG to that of SGD at each iteration t. We show that the learning dynamics of our regression model closely matches with that of neural networks on MNIST and CIFAR-10 for both the underparameterized and the overparameterized models. Our analysis and experimental results suggest there is a trade-off between the computational cost and the convergence speed in underparametrized neural networks. SVRG outperforms SGD after a few epochs in this regime. However, SGD is shown to always outperform SVRG in the overparameterized regime.

Under review as a conference paper at ICLR 2020
A NON-ASYMPTOTHE COMPARISON OF SVRG AND SGD: TRADEOFFS BETWEEN COMPUTE AND SPEED
Anonymous authors Paper under double-blind review
ABSTRACT
Stochastic gradient descent (SGD), which trades off noisy gradient updates for computational efficiency, is the de-facto optimization algorithm to solve large- scale machine learning problems. SGD can make rapid learning progress by per- forming updates using subsampled training data, but the noisy updates also lead to slow asymptotic convergence. Several variance reduction algorithms, such as SVRG, introduce control variates to obtain a lower variance gradient estimate and faster convergence. Despite their appealing asymptotic guarantees, SVRG-like algorithms have not been widely adopted in deep learning. The traditional asymp- totic analysis in stochastic optimization provides limited insight into training deep learning models under a fixed number of epochs. In this paper, we present a non-asymptotic analysis of SVRG under noisy least squares regression prob- lem. Our primary focus is to compare the exact loss of SVRG to that of SGD at each iteration f. We show that the learning dynamics of our regression model closely matches with that of neural networks on MNIST and CIFAR-10 for both the underparameterized and the overparameterized models. Our analysis and ex- perimental results suggest there is off between the computational cost and the convergence speed in underparametrized neural networks. SVRG outperforms SGD after the first few epochs in this regime. However, SGD is shown to always outperform SVRG in the overparameterized regime.
INTRODUCTION
Many large-scale machine learning problems, especially in deep learning, are formulated as mini-
mizing the sum of loss functions on millions of training examples (Krizhevsky et al., 2012 Devlin
al. 2018). Computing exact gradient over the entire training set is intractable for these problems.
Instead of using full batch gradients, the variants of stochastic gradient descent (SGD) (Robbins)
& Monro 1951: Zhang] 2004 Bottou| 2010 Suusskvvrr et al. 2013 Duchi al. 2011 Kingma &
Ba 20144) evaluate noisy gradient estimates from small mini batche of randomly sampled training points at each iteration. The mini-batch size is often independent of the training set size, which allows SGD to immediately adapt the model parameters before going through the entire training set. Despite its simplicity, SGD works very well, even in the non-convex non-smooth deep learn- ing problems (He et al.) 2016 Vaswani et al. 2017). However, the optimization performance of the stochastic algorithm near local optima is significantly limited by the mini-batch sampling noise, controlled by the learning rate and the mini-batch size. The sampling variance and the slow conver- gence of SGD have been studied extensively in the past (Chen et al.] 2016 Li et al. 2017] Toulis & Airoldi 2017). To ensure convergence, machine learning practitioners have to either increase the minc-batch size or decrease the learning rate toward the end of the training (Smith et al. 2017 Ge
et al. 2019)
Recently, several clever variance reduction methods (Roux al. 2012 Defazio et al. 2014 Wang et al. 20133 Johnson & Zhang 2013) were proposed to alleviate the noisy gradient problem by us- ing control- variates to achieve unbiased and lower- variance gradient estimators. In particular, the variants of Stochastic Variance Reduced Gradient (SVRG) (Johnson & Zhang 2013). 3,, k-SVRG (Raj & Stich 2018), L-SVRG (Kovalev et al. 2019) and Free-SVRG (Sebbouh et al. 2019) construct control-variates from previous staled snapshot model parameters. These methods enjoy a superior asymptotic performance in convex optimization compared to the standard SGD. The control-variate variate techniques are shown to improve the convergence rate of SGD from a sub-linear to a linear conver- gence rate. These variance reduction methods can also be combined with momentum (Allen-Zhu) 2017) and preconditioning methods (Moritz al.] 2016) to obtain faster convergence. Despite

---

Under review as a conference paper at ICLR 2020
Naisy Least-square
MNIST
10
Mnnmum Training Error (%)
SGD SVRG
128 sarch
Minium Loss
101
101
x
10-1
10
10-3
2 10P
0
10 20
30
10x100
5
10 opach
20
epoch
(a) Least-squares regression (predicted).
(b) Logistic regression.
Figure I: (a) The minimum loss achieved over a set of hyperparameters in a noisy least squares regression problem (simulated dynamics). (b) The minimum loss achieved in real dataset MNiST (a logistic regression model). Our theoretical prediction (a) matched with the training dynamics for real datasets, demonstrating tradcoffs between computational cost and convergence speed. The curves in red are SVRG and curves in bluc are SGD. Different markers refer to different per-iteration computational cost, i... the number of backpropaga- tion used per iteration on average.
their strong theoretical guarantees, SVRG-like algorithms have seen limited success in training deep learning models (Defazio & Bottou| 2018 Traditional results from stochastic optimization focus on the asymptotic analysis, but in practice, most of deep neural networks are only trained for hundreds of epochs due to the high computational cost. To address the gap between the asymptotic benefit of SVRG and the practical computational budget of training deep learning models, we provide a non-asymptotic study on the SVRG algorithms under a noisy least squares regression model. Al- though optimizing least squares regression is a basic problem. it has been shown to characterize the learning dynamics of many realistic deep learning models (Zhang al. 2019 Lee et al. 2019). Re- cent works suggest that neural network learning behaves very differently in the underparameterized regime vs the overparameterized regime (Ma et al., 2018: Vaswani et al. 2019), characterized by whether the learnt model can achieve zero expected loss. We account for both training regimes in the analysis by assuming a linear target function and noisy labels. In the presence of label noise, the loss lower bounded by the label variance. In the absence of the noise, the linear predictor can fit each training example perfectly. We summarize the main contributions as follows:
We show the exact expected loss of SVRG and SGD along an optimization trajectory as a function of iterations and computational cost.
Our non- asymptoti analysis provides an insightful comparison of SGD and SVRG by considering their computational cost and learning rate schedule. We discuss the trade-offs between the total computational cost, i.e. the total number of hack-propagations performed, and convergence performance.
We consider two different training regimes with and without label noise. Under noisy labels, the analysis suggests SGD only outperforms SVRG under a mild total computational cost. However, SGD always exhibits faster convergence compared to SVRG when there is no label noise.
Numerical experiments validate our theoretical predictions on both MNIST and CIFAR- 10 using various neural network architectures. In particular, we found the comparison of the convergence speed of SGD to that of SVRG in underparameterized neural networks closely matches with our noisy least squares model prediction. Whereas, the effect of overparameteriizaionn is captured by the regression model without label noise.
1.1 RELATED WORKS
Stochastic variance reduction methods consider minimizing a finite-sum of a collection of func- tions using SGD. case we use SGD to minimize these objective functions, the stochasticity comes from the randomness in sampling a function in each optimization step. Due to the induced noise, SGD can only converge using decaying step sizes with sub-linear convergence rate. Methods such as SAG (Roux et al. 2012). SVRG (Johnson & Zhang 2013), and SAGA (Defazio et al. 2014), are able to recover linear convergence rate of full- gradient descent with the asymptotic cost com- parable to SGD. SAG and SAGA achieve this improvement at the substantial cost of storing the most recent gradient of each individual function. In contrast, SVRG spends extra computation at snapshot intervals by evaluating the full-batch gradient. Theoretical results such as Gazagnadou et al. (2019) show that under certain smoothness conditions, we can use larger step sizes with stochastic variance reduction methods than is allowed for SGD and hence achieve even faster convergence. In situations where we know the smoothness constant of functions, there are results on the optimal mini-batch size and the optimal step size given the inner loop size (Sebbouh al. 2019). Applying variance
2

---

Under review as a conference paper at ICLR 2020
reduction methods in deep learning has been studied recently (Defazio & Bottou 2018 The authors conjectured the ineffectiveness is caused by various elements commonly used in deep learning such as data augmentation, batch normalization and dropout. Such elements can potentially decrease the smoothness and make the stored gradients become stale quickly. The proposed solution is to either remove these elements or update the gradients more frequently than is practical.
Dynamics of SGD and quadratic models Our main analysis tool is very closely related recent work studying the dynamics of gradient-based stochastic methods. [Wa et al. (2018) derived the dynamics of stochastic gradient descent with momentum 2013), showing the problem of short horizon bias. (Zhang et al.] (2019), the authors showed the same noisy quadratic model captures many of the essential characteristic of realistic neural networks training. Their noisy quadratic model successfully predicts the effectiveness of momentum, precon- ditioning and learning rate choices in training ResNets and Transformers, However, these previous quadratic models assume a constant variance in the gradient that independent of the current param- eters and the loss function, It makes them inadequate for analyzing the stochastic variance reduction methods, as SVRG can trivially achieve zero variance under the constant gradient noise. Instead, adopted a noisy least-squares regression formulation by considering both the mini-batch sampling noise and the label noise. There are also recent works that derived the risk of SGD, for least-squares regression models using the bias-variance decomposition of the risk (Belkin et al.] 2018: Hastie et al. 2019). We use similar decomposition in our analysis. In contrast to the asymptotic analysis in these works, we compare SGD to SVRG along the optimization trajectory for any finite-time horizon under limited computation cost, not just the convergence points of those algorithms.
noisy quadratic model (Schaul et al.
Many of the state-of-the-ar deep learning models are overparameterized deep neural networks with more parameters than the number of train- ing examples. Even though these models are able to overfit to the data, when trained using SGD, they generalize well (Zhang et al. 2017). As suggested in recent work, underparameterized and overpa- rameterized regimes have different behaviours (Ma et al., 2018 Vaswani et al. 2019: Schhidt & Roux 2013). Given the infinite width and a proper weight initialization, the learning dynamics of neural network can be aprroxaepo by a linear model via the neural tangent kernel (NTK) (Ja-) cot et al. 2018 Chizat & Bach 2018). In NTK regime, neural networks are known to achieve global convergence by memorizing every training example. On the other hand, previous convergence re- sults for SVRG have been obtained in stochastic convex optimization problems that are similar to that of an underparameterized model (Roux et al.. 2012, Johnssn & Zhang 2013). Our proposed noisy least-squares regression analysis captures both the underparameterization and overparameter- ization behavior by considering the presence or the absence of the label noise.
Underparameterizatinn vs overparameterization
PRELIMINARY
2.1 NOTATIONS
We will primarily focus on comparing the minibatch version of two methods, SGD and SVRG (John- son & Zhang 2013). Denote L; as the loss on tth data point. The SGD update is written as,
((++1) (00) - a (g)0)
(1)
Voie Li is the minibatch gradient, t is the training iteration, and (4) is the learning rate. The SVRG algorithm is an inner-outer loop algorithm proposed to reduce the variance of the gradient caused by the minibatch sampling. In the outer loop, for every T steps, we evaluate a large batch gradient g = N Σ, Too where N >> b, and m is the outer loop index, and we store the parameters (mT), In the inner loop, the update rule of the parameters is given by,
where (()) = Σト +
@lmT+++1) = g(miT++) (t)
(g( (g(T
(mT++)) +
(2)
where g (1)++) = V V L; is the current gradient of the mini-batch and g (mT++) D V Vatmz; L; is the old gradient. Note that in our analysis, the reference point is chosen to be the last iterate of previous outer loop ((mT), recommended as a practical implementation of the algorithm by the original SVRG paper Johnson & Zhang (013)).
3

---

Under review as a conference paper at ICLR 2020
2.2 THE NOISY LEAST SQUARES REGRESSION MODEL
We now define the noisy least squares regression model (Schaul et al. 2013] Wu et al. 2018). this setting, the input data is d-dimensional, and the output label is generated by linear teacher model with additive noise.
(a,, () ~ Ps x Pa: = xz 0 E
where E[æ,]] μa E Rd and Cov( = E, Ele.] O. Var(es) oz We assume WLOG 0" 0. We also assume the data covariance matrix E diagonal. This is assumption adopted in many previous analysis and it is also practical assumption as we often apply whitening to pre-process the training data. We would like to train student model f that minimizes the squared loss over the data distribution:
min L(O)= == 1 (a) yi)
At each iteration, the optimizer can query an arbitrary number of data points (æ,, yi3s sampled from data distribution. The SGD method uses b data points form minibatch gradient:
g(() 1 E a ( x,C,) = X,X 0
Xbeo.
(4)
vb
where X, vh 1 22: 26) E Rdxb, and the noise vector c (.:; :c]]] E R. SVRG on the other hand, queries for N data points every T steps to form large batch gradient g = xx
VN XNEN. where XN and eN are defined similarly. At each inner loop step, it further queries for another data points, to form the update in Eq 2
Lastly, note that the expected loss can be written as function of the second moment of the iterate,
L(O())
= 1 (
xx. ( -e:) ) - - (r((E1)000)0
T D) +o?)
Hence for the following analysis we mainly focus on deriving the dynamics of the second mo- ment ((((0)(()) 1. denoted as A(git).. When is diagonal, the loss can further be reduced to diag (E)T (iag(E(0(()))) 1) 20z We denote (iag(E(0(*) by m(0()).
2.3 THE DYNAMICS OF SGD
Definition (Formula for dynamics). We define the following functions and identities,
M(Ø) = E[00"], m(0) = diag [E I), C(M(0)) = Ex [xx [x(xx "M()) 1 ΣM(()
+ a² (I² + diag( E)diag [I) T)
n = diag E), R = [I-
b
2a²
P aE, F= a² + b) Nb
Q b
[ + (())g())))(()))
( ddig(E))diag) (E)) T)
b ++1 x²
1 + (diag(E)ddag(2))
G = a²(
The SGD update (Eq. I with the mini-batch gradient of of the noisy least squares model (Eq. is,
((+1) (I aXxx, 1000
vb
We substitute the update rule to derive the following dynamics for the second moment of the iterate:
M( (I ( a.) C(M(B()))
y
Σ
(5)
D: gradient descent shrinkage
D: input noise
label noise
This dynamics equation can be understood intuitively as follows. The term ① leads to an exponential shrinkage of the loss due to the gradient descent update. Since we are using noisy gradient, the second term 2 represents the variance of stochastic gradient caused by the random input X'. The
4

---

Under review as a conference paper at ICLR 2020
term 3 comes from the label noise. We show in the next theorem that when the second moment of the iterate approaches zero, ② will also approach zero. However due to the presence of the label noise, the expected loss is lower bounded by 3
When Σ diagonal, we further analyze and decompose C(M(O)) a function of m(0) so to derive the following dynamics and decay rate for SGD.
Theorem 2 (SGD Dynamies and Decay Rate), Given the noisy linear regression objective functiinn (Eq. 3) under the assumption that x ~ NN Σ) with E diagonal and 0 0, we can express C(0) as a junction of m@):
diag (c -M diag(E)) Dddiag E)
m(0)
(6)
Then we derive following dynamics of expected second moment of 0:
(() = R2' (m (I- - n2
(I- R)
(I (I-R) R) n
(7)
b
Under the update rule of SGD, R the decay rate of the second moment of parameters between two iterations. And based on Theorem 2 the expected loss can be calculated by diiggE)))) (((0())++)
A DILEMMA FOR SVRG
By querying a large batch of datapoints X every T steps, and small minibatch X₁ at every step, the SVRG method forms the following update rule:
0 (mT+++1) (1 aXxx,)) (lmT++) + a (XxXg XNXN) (
XNEN
(8)
VN
To derive the dynamics of the second moment of the parameters following the SVRG update, we look at the dynamics of one round of inner loop updates, i.e., from ((T)) to (((m=1)T):
Lemma 3. The dynamics of the second moment of the iterate following SVRG update rule is given by.
a (MM(O(mCHe))
0200
M(A ((())))++))) = (I - (D))(((mm+t)))
+
(9)
N
L gradient descent shrinkage
2 input noise
3 label noise
a N + (Arcoomart)
a² (M +c + (P'M(((m))) b
Nb
Dvariance due to g
(Im T4)
Variance reducctio from control variate
The dynamics equation above is very illuminating as it explicitly manifests the weakness of SVRG. First notice that terms D. 2, 3 reappear, contributed by the SGD update. The additional terms, ① and (5), are due to the control variate. Observe that the variance reduction term ( decays ex- ponentially throughout the inner loop, with decay rate I aΣ, i.c. P. We immediately notice that this is the same term that governs the decay rate of the term ①. and hence resulting in a conflict between the two. Specifically, if we want to reduce the term ! as fast as possible, we would prefer a small decay rate and large learning rate, i.e. a > (x)) But this will also make the boosts provided by the control variate diminish rapidly, leading to a poor variance reduction. The term 4 makes things even worse as it will maintain as constant throughout the inner loop, contributing to an extra variance on top of the variance from standard SGD. On the other hand, if one chooses a small learning rate for the variance reduction to take effect, this inevitably will make the decay rate for term ! smaller, resulting in a slower convergence. Nevertheless, good news for SVRG that the label noise (term 3) is scaled by N. which lets SVRG converge to lower loss value than SGD a strict advantage of SVRG compared to SGD.
To summarize, the variance reduction from SVRG comes at price of slower gradient descent shrinkage. In contrast, SVRG is able to converge to a lower loss value. This motivates the ques- tion, which algorithm to use given certain computational cost? We hence performed a thorough investigation through numerical simulation as well as experiments on real datasets in Sec.
Similarly done for SGD, we decompose ((0) as a function of m(0) and derive the following decay rate for SVRG.
5

---

Under review as a conference paper at ICLR 2020
Noisy squat-square
Noisy Least square
10
10"
10-
8 110-3
Minmum
10-21
20--
10-40
10-40
epoch
egoch
(a) With Label Noise
(b) Without Label Noise
Figure 2: The minimum loss achieved by following SGD (blue) and SVRG (red) over a set of hyperparameters a noisy least-squar dynamics simulation for cases with and without label noise. The plot suggests that in the presence of label noise, there is tradeoff between computational cost and convergence speed. In the absence of label noise, SGD strictly dominates SVRG in convergence speed for all computational cost.
Theorem (SVRG Dynamics and Decay rate). Given the noisy linear regression objective function functioo (Eq. 3). under the assumption that SVRG in mf) is given by:
(0, Σ) with E. diagonal and 0" 0, the dynamics for
m(f(im+1))) =\(a, D, ( (f(m))) + (I- R² R)
n
(10)
N
T-1
(,. =R²-
R pT-1 p (I- R )[I 1
(11)
3.1 THE DYNAMICS WITHOUT LABEL NOISE
In the absence of the label noise (i.e., J. 0), we observe that both SGD and SVRG enjoy linear convergence as corollary of Theorem an Theorem $
Corollary 5. Without the label noise, the dynamics of the second moment following SGD given by.
m(010) = Rt' (O()),
and the dynamics of SVRG is given by.
m(0((m+117) m(
where X is defined in (
Note that similar results have been shown in the past (Ma et al. 2018 Vaswani et al. 2019 Schmidt & Roux 2013), where general condition known "interpolation regime" is used to show linear convergence of SGD. Specifically they assume that VI, = 0 for all and our setting without label noise clearly also belongs to this regime. This setting also has practical implications, can treat training overparameterized neural networks as in interpolation regime. This motivates the investigation of the convergence rate of SGD and SVRG without label noise, and was also extensively studied in the experiments detailed follows.
one
EXPERIMENTS
In Sec. 3 we discussed critical dilemma for SVRG that is facing choice between effective vari- ance reduction and faster gradient descent shrinkage. At the same time, it enjoys a strict advantage over SGD as it converges to lower loss. We define the total computational cost as the total number of propagatattss performed. Similarly, per-iteration computational cost refers to the number of back-propagations performed per iteration. In this section, we study the question, which algo- rithm converges faster given certain total computational cost? We study this question for both the underparameterizzed and the overparameterized regimes.
Our investigation consists of two parts. First, numerical simulations of the theoretical convergence rates (Sec. 4.1.. Second, experiments on real datasets (Sec. 4.2). In both parts, we first fix the per-iteration computational cost. For SGD, the per-iteration computational budge is equal to the minibatch size. We picked three batch size (64, 128, 256). Denote the batchsize of SGD as b, the cquivalent batch size for SVRG is b' ] (1 N/ 66. We then perform training with an extensive set of hyperparameters for each method with each per-iteration computational cost. For SGD, the hyperparameter under consideration is the learning rate a. For SVRG, besides the learning rate,

---

Under review as a conference paper at ICLR 2020
MNIST
10
MNIST
CIFAR-10
8mmmmmm Ener
SGD SVRG
x 8 10
SGP
SVNG
Batch 128
Mmmimum Training
aochh 256
10"
xx100
6 10
Miniuum
5
4 4x10"
10
15
20
10 opoch
15
20
40
opoch
opcch
(a) Logistic Regression.
(b) underparameterizee MLP
(c) unnderparamcterized CNN
Figure 3: The minimum loss achieved by following SGD (blue) and SVRG (red) over a set of hyperparameters for training on MNIST and CIFAR-10 with underparameterized models. All the results in these plot suggested there is a tradcoff between computational cost and convergence speed when comparing SGD and SVRG.
we also ran over a set of snapshot intervals T. After running over all sets of hyperparameters, we gather all training curves of all hyperparameters. We then summarize the performance for each algorithm by plotting the lower bound of all training curves, i.e. each point (7, t) on the curve showed the minimum loss at time step over all hyperparameters. We compared the two methods under different computational cost.
Remarkably, we found in many cases phenomenon predicted by our theory matches with observa- tions in practice. Our experiments suggested there is a trade-off between the computational cost and the convergence speed for underparameterized neural networks. SVRG outperformed SGD after a few epochs in this regime. Interestingly, in the case of overparameterized model, a setting that matches modern day neural networks training, SGD strictly dominated SVRG by showing a faster convergence throughout the entire training.
4.1 SIMULATIONS ON NOISY LEAST SQUARES REGRESSION MODEL
We first performed numerical simulations of the dynamics derived in Theorem 2 for SGD and Theo- rem[ffor SVRG. We picked a data distribution, with data dimension d = 100, and the spectrum of Σ is given by an exponential decay schedule from 1 to 0.01. For both methods, we picked 50 learning rate from 1.5 to 0.01 using a exponential decay schedule. For SVRG, we further picked set of snapshot intervals for each learning rate: {256, 128, 64). We performed simulations in both under- parameterized and overparameterized setting (namely with and without label noise), and plotted the lower bound curves over all hyperparameters at Figure The z-axis represents the normalized total computational cost, denoting tbN-1, which is equivalent to the notion of an epoch in finite dataset setting. And the loss in Figure 2 does not contain bayes error (i.e. 2
We have the following observations from our simulations. In the case with label noise, the plot demonstrated an explicit trade-off between computational cost and convergence speed. We observed a crossing point of between SGD and SVRG appear, indicating SGD achieved a faster convergence speed in the first phase of the training, but converged to higher loss, for all per-iteration compute cost. Hence shows that one can trade more compute cost for convergence speed by choosing SGD than SVRG, and vice versa. Interestingly, we found that the the per-iteration computational cost does not seem to affect the time crossing point takes place. For all these three costs, the crossing points in the plot are at around the same time: 5.5 epochs. In the case of no label noise, we observed both methods achieved linear convergence, while SGD achieved much faster rate than SVRG, showing absolute dominance in this regime.
4.2 BENCHMARK DATASETS
In this section, we performed a similar investigation as in the last section, on two standard machine learning benchmark datasets: MNIST (LeCun et al. 1998) and CIFAR-10 (Krizhevsky 2209). We present the results from underparameterizee setting first, followed by the overparameterized set- ting. We performed experiments with three batchsizes for SGD: {64, 128, 256). and an equivalent batchsize for SVRG. For each batch size, we pick 8 learning rates varying from 0.3 to 0.001 fol- lowing an exponential schedule. Additionally. we chose three snapshot intervals for every computa- tional budget, searching over the best snapshot interval given the data. Hence for each per-iteration computational cost (64, 128, 256). there are 24 groups of experiments for SVRG and 8 groups of experiments for SGD.
7

---

Under review as a conference paper at ICLR 2020
101
MNIST
Mnnium Tra ninning Ereer (19)
110
CIFAR-1D
Plmimum Training tree
10a
SVIG
Batch 64
10-1
1.0
10-1
25
75
10"
50
2000
150 200
epoch
opech
(a) Over- ever-paremetrized MLP
(b) overparameterized CNN
Figure 4: The minimum loss achieved by following SGD (blue) and SVRG (red) over a set hyperparameters for training on MNIST and CIFAR-10 with overparameterized models. this setting we observed strict domi- nance of SGD over SVRG in convergence speed for all computational cost, matching our previous theoretical prediction.
4.2.1 UNDERPARAMETERIZZA SETTING
For MNIST, we trained Iwo underparameterrzzed model: 1. logistic regression 784 10 under- parameterized two layer MLP 784 - 10 10--10 10 where the hidden layer has 10 neurons. For CIFAR-10, chose underparameterriedd convolutional neural network model, which has only two 8-channel convolutional layers, and one 16-channel convolutional layer with one additional fully-connected layer. Filter size is 5. The lowest loss achieved over all hyperparameters for these models for each per-iteration computational cost are shown in Figure
From these experiments, we observe that on MNIST, the results with underparameterized model were consistent with the dynamics simulation of noisy least squares regression model with label noise. First of all, SGD converged faster in the early phase, resulting a crossing point between SGD and SVRG. It showed trade-off's between computational cost and convergence speed: before the erossing point, SGD converged faster than SVRG; after crossing point, SVRG attained lower loss. In addition, in Fig 3a all the crossing points of three costs matched at the same epoch (around 5), which was also consistent with the our findings with noisy least squares regression model. On CIFAR-10, 10, SGD achieved slightly faster convergence in the early phase, but was surpassed by SVRG around 17 25 epochs, again showing a trade-off between compute and speed.
4.2.2 THE OVERPARAMETERIZZE SETTING
Lastly, we compared SGD and SVRG on MNIST and CIFAR-10 using overparameterized models. For MNIST, we used MLP with two hidden layers, each layer having 1024 neurons. For CIFAR- 10, we chose a large convolutional network, which has one 64-channel convolutional layer, one 128-channel convolutional layer followed by one 3200 to 1000 fully connected layer and one 1000 to 10 fully connected layer.
The lowest loss achieved over all hyperparameters for these models for each per-iteration computa- tional cost are shown in Figure 4 For training on MNIST, both SGD and SVRG attained close to zero training loss. The results were again consistent with our dynamics analysis on the noisy linear regression model without label noise. SGD has strict advantage over SVRG. and achieved much faster convergence rate than SVRG throughout the entire training. As for CIFAR-IO, we stopped the training before either of the two got close to zero training loss due to lack of computing time. But we clearly see trend of approaching to zero loss. Similarly, we also had the same observa- tions as before, where SGD outperforms SVRG, confirms the limitation of variance reduction in the overparameterizedd regime.
5 DISCUSSION
In this paper, we studied the convergence properties of SGD and SVRG in the underparameterized and overparameterized settings. We provided non-asymptotic analysis of both algorithms. We then investigated the question about which algorithm to use under certain total computational cost. We performed numerical simulations of dynamics equations for both methods, well extensive experiments on the standard machine learning datasets, MNIST and CIFAR-10. Remarkably, we found in many cases phenomenon predicted by our theory matched with observations in practice. Our experiments suggested there a trade-off between the computational cost and the convergence speed for underparameterized neural networks. SVRG outperformed SGD after the first few epochs in this regime. In the case of overparameterized model. setting that matches with modern day neural networks training, SGD strictly dominated SVRG by showing a faster convergence for all computational cost.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhi Zhu. Katyusha: The first direct acceleration stochastic gradient methods. The Journal of Machine Learning Research, 18(1):819482244 2017.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. CoRR, abs/18 812.11118 2018.
Léon Bottou. Lcage-scale machine learning with stochastic gradient descent. In Proceedings of COMPSTAT pp. 177-186. Springer, 2010.
Xi Chen, Jason Lee, Xin T. Tong, and Yichen Zhang. Statistical inference for model parameters in stochastic gradient descent, 2016.
Lénaïc Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. CoRR, abs/1 81200755, 2018.
Aaron Defazio and Léon Bottou. On the ineffectiveness of variance reduced optimization for deep learning. CoRR, abs/181 1e2s1882.04499 2018.
Aaron Defazio, Francis R. Bach, and Simon Lacoste-Julien. SAGA: fast incremental gradient method with support for non-strongly convex composite objectives. In Neural Information Pro- cessing Systems (NeurIPS), pp. 1646-1654, 2014.
Jacob Devlin, Ming- Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: bidirectional transformers for language understanding. arXiv preprint arXiv: 04800, 2018.
Pre-training of deep
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(111:2121-2159, 2011.
Nidham Gazagnadou, Robert M. Gower, and Joseph Salmon. Optimal mini-batch and step sizes for SAGA. In International Conference Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 2142-2150. PMLR, 2019.
Rong Ge, Sham M Kakade, Rahul Kidambi, and Praneeth Netrapalli. The step decay schedule: A near optimal, geometrically decaying learning rate procedure. arXiv preprint arXiv:190. 12838, 2019.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. CoRR, abs/1903, 1903008560, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770-778, 2016.
Arthur Jacot, Clément Hongler, and Franck Gabriel. Neural tangent kernel: Convergence and gen- eralization in neural networks. In NeurIPS, pp. 8580-8589, 2018
Rie Johnson and Tong Zhang. Accelerating stochastie gradient descent using predictive variance reduction. In Neural Information Processing Systems (NeurIPS), pp. 315-323, 2013.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 141669,4, 2014.
Dmitry Kovalev, Samuel Horváth, and Peter Richtárik. Don't jump through hoops and remove those loops: Svrg and katyusha are better without the outer loop. arXiv preprint arXiv: 100100890,,0889, 2019.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in neural information processing systems, pp. 1097-1105. 2012.
Yann LeCun, Leon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedingy of the IEEE, 86(1 (1111)):278-22222 Nov 1998. ISSN 001 8-9219. doi: 10.1109/55 00917999..76691.

---

Under review as a conference paper at ICLR 2020
Jachoon Lee, Lechao Xiao, Samuel S Schoenholz, Yasaman Bahri, Jascha Sohl-Dickstein and Jef- frey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. arXiv preprint arXiv: 1x2iv 2019.
Tianyang Li, Liu Liu, Anastasios Kyrillidis, and Constantine Caramanis. Statistical inference using sgd, 2017.
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understanding the effectiveness of SGD in modern over-parann weerppaaaetrried learning. In ICML, volume 80 of Proceedings of Machine Learning Research, pp. 3331-333 3331-3340. PMLR, 2018.
Philipp Moritz, Robert Nishihara, and Michael Jordan. A linearly-convergent stochastic I-bfgs al- gorithm. In Artificial Intelligence and Statistics, pp. 249-258, 2016.
K. B. Petersen and M. S. Pedersen. The matrix cookbook, nov 2012. URL ARtt::/:/Locaaaoo pubcb/p. php?3274 Version 20121115.
Anant Raj and Sebastian U. Stich. k-svrg: Variance reduction for large scale optimization, 2018.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statisties, pp. 400 4070-407,1000 1951.
Nicolas Le Roux, Mark W. Schmidt, and Francis R. Bach, A stochastic gradient method with an exponential convergence rate for finite training sets. In Neural Information Processing Systems (NeurIPS), pp. 2672-2680, 2012.
Tom Schaul, Sixin Zhang, and Yann LeCun. No more pesky learning rates. In ICML (3), volume 28 of JMLR Workshop and Conference Proceedings, pp. 343-351. JMLR.org, 2013.
Mark Schmidt and Nicolas Le Roux. Fast convergence of stochastic gradient descent under a strong growth condition. arXiv preprint arXiv: 31..3086677, 2013.
Othmane Sebbouh, Nidham Gazagnadou, Samy Jelassi, Francis Bach, and Robert M Gower. To- wards closing the gap between the theory and practice of svrg. arXiv preprint arXiv: 1908.0225, 2019.
Samuel I. Smith, Pieter-Jan Kindermans, Chris Ying, and Quoe Le. Don't decay the learning rate, increase the batch size. arXiv preprint arXiv:1711.00482 2017.
Iya Sutskever, James Martens, George Dahl, and Geoffrey Hinton. On the importance of initial- ization and momentum in deep learning. In International conference on machine learning, pp- 1139-11477 2013.
Panos Toulis and Edoardo M. Airoldi. Asymptotic and finite finite-sample properties of estimators based on stochastic gradients. Ann. Statist, 45(4): 08 2017. doi: 10.1214/1-AASS1500 URL http:htts///ooo.oo .rrg 1214/111111111 A051506
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 5998-69900 6008, 2017.
Sharan Vaswani, Francis Bach, and Mark Schmidt. Fast and faster convergence of SGD for over- parameterized models and an accelerated perceptron. In AISTATS, volume 89 of Proceedings of Machine Learning Research, pp. 1195-1204. PMLR, 2019.
Chong Wang, Xi Chen, Alexander J Smola, and Eric P Xing. Variance reduction for stochastic gradient optimization. Advances in Neural Information Processing Systems, pp. 181-189, 2013.
Yuhuai Wu, Mengye Ren, Renjic Liao, and Roger B. Grosse. Understanding short-horizon bias in stochastic meta-optimization. In ICLR (Poster). OpenReview.net, 2018.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In ICLR. OpenReview.net, 2017.
10

---

Under review as a conference paper at ICLR 2020
Guodong Zhang, Lala Li, Zachary Nado, James Martens, Sushant Sachdeva, George E Dahl, Christopher Shallue, and Roger Grosse. Which algorithmic choices matter at which batch sizes? insights from noisy quadratic model. arXiv preprini arXiv: 190.044144 2019.
Tong Zhang. Solving large scale linear prediction problems using stochastic gradient descent algo- rithms. In Proceedings of the Twenty-first International Conference on Machine Learning. ICML '04, pp. 116-, New York, NY, USA, 2004, ACM. ISBN 1-581 doi: 10.1 145/1011133 1015332. URL http://doi acm. att..//.o......11111111333000000

---

Under review as a conference paper at ICLR 2020
A APPENDIX
B LEMMA ABOUT GRADIENT COVARIANCE
Lemma (Gradient Covariance). Given the noisy linear regression objective function (Eq. 3 the assumption that x ~ (0, 2) with E diagonal and 0 0, we have
under
(iag((Eaaa ( (()) wa "I) = -(2x² + diag (E)diag()) E(0(t)0
BX 0(0) x,X,1 - ΣE T E== 1 (B/2xx' ((0)@)) re _ EE((()) g T }
1
Proof. In the following proof, we define the entry-wise p power on vector æ as x.P Under our assumption μ 0, 0" 0 and E diagonal, for ~ (O,, x Rd, we have
E o(e ax ( g(0) wæ -2 E (+)
T 000 DE
(12)
Eq. 12 is a conclusion from The Matrix Cookbook (See section 8.2.3 in Petersen & Pedersen
2012
Then, for its main diagonal term, have:
diag(E, ,, fxx: T (())(()) xx "I) =2 E(0(1) diag (E)ddi(())( (E
(13)
= =222² diag(())daa(()) m m(((t)
(14)
Hence, for c (M((1))). we have:
diag (c(M((rO))) = (>²² + diag(2)) m m((0))
(15)
which is the first conclusion of Theorem
Notice, this conclusion can be generalized to any square matrix A not only for ((0(t)00)) any square matrix Raxd, with x NO, Σ) and Σ diagonal, since
i.c. for
Enp (ax Aaa -25 2 + Tr(AA)E
(16)
have
diag Em [xx Axx "I) -2 22Eddiag(AA) + diag (o)g((E)diin (E)diag( (E) diag(A)
(17)
25 + diag ( didiag (Σ) diag(A)
(18)
For batch gradient X,X,J ((1, we have
E. EXX,X, g())
X,XX
x )000
x
(19)
[E(N]
i |
bE x g(0 (()) xx T [+
(b2
b)
x
((0)
[x>>
62
b2
(20)
E fox T ((() T
ax "
ER
1E( J1x
(21)
b
where [V] is the index set of X
12

---

Under review as a conference paper at ICLR 2020
C
THE PROOF OF THEOREM 2
Theorem 2. Given the noisy linear regression objective function (Eg. 3 under the assumption that
(0, E) with E diagonal and 0 O, can express C(M(0)) function of m(0):
diag (M(())) -2 diag( E) diag 2) m())
Then we derive following dynamics of expected second moment of 0:
(1 R) R + (1 Rt) I
m(0()) R2' (m((l1))
b
Proof.
0(++)g((+11 =(I aX2X, )0 )()) (I [x-aX,Xy]] (1
+ ot (1-0XxX X
(22)
vb
a²
vb (1) (I- (xxx),))) + b X X
(23)
Since, E(es] = 0, and is independent with 0(1), Xo. we have:
E B(x
axxX, =0
(24)
E[(T aX )0 E x². =0
(25)
and,
a²
a²
Ex,, Xy
XneseT X
Ex
Xs [[(eNET]] Xn)
(26)
b
b
a²
Xx [xo (1)))) X
Ex
(27)
o²
(28)
Since X6 is independent with ((t), we have:
Bi(1 B[II-ox Xx,, )00000000000 g() (I- xxxxxX)1)) (I (I- -[[-OS)E((()) T
1(I (I-oE)
(29)
a T X6X1 - ((t) }H)
(0)
(30)
Thus,
] ( 1I-aE)- a²
B0 =(I
E x
g00 xx
(31)
a²0²
a
0(1) [2) + b
3
(32)
()) 1(1 - aΣ) + a
a²0z
C(M()(0))
+
(33)
b
For its diagonal term, we have:
m(0(+11)) =digg E (((+++)0+++)))
(34)
a² (I² diag (a))dia()(() ) m((()) + a²oz
-(1 az)²
diag +
(35)
b
=R -R-m(l()) + n
(36)
13

---

Under review as a conference paper at ICLR 2020
This formula can be written
m( b ( 1) R ( + + 1)
(37)
m( = (m(0)) + b- ' (R 1) 11) b -1)-
(38)
where
= -1 + + diag({)) )
n = =a aLo]diag(22) 22).
(39)
D THE PROOF OF LEMMA 3
Lemma 3. The dynamics of the second moment of the iterate following SVRG update rule is given by.
a (MM(B(TTH))
a
M( M(O (())))++++))))) = (m((0))T4))))) (0)
+
N
① gradient descent shrinkage
2 input noise
noise
a N + b C (MIiommmn) Nb
a² b
(c (C((Ommm)) pP)) + (P m1)))
Avariance due to (mmT+e)
Variance reduction from control variate
Proof. For SVRG update rule Eq. 8 we have:
glmT+++1) = ax,, ( + a (X,X,) XNXX) @(ITT)
XNEN
(40)
VN
Using the update rule of SVRG, we can get the outer product of parameters as:
( 0 (m
(41)
= -I- ((
g(m (I (I-
aX
(42)
+a( - a (( (T) (X,X, - XNXX))
(43)
+a(X,X, - X
0 +1)) (I (I-a )
(44)
+Xo(X NNNNN 0 1 g(aT)
(XxX, - x
(45)
a² XNENo(TT) (X6X, - -xxX))
VN XNENO(ITHO) (I-aXiX))
(46)
VN
a²
NX,N,
T ( NN
(XxX, XxXX EN
(47)
XNENEWXN
(48)
Likewise, since E[Ex] 0 and eN is independent with X, XNN and ((t), we have the expectation of equation 46 equation 47 equal O. And same SGD, also have
NEw.xx(XNeNe X
=Ix (eNe
(49)
E XN 0 XN
(50)
= =
(51)
Then, we give significant formula about the expectation of g(nT++)g(mT)) utilized to derive the expected term related to variance reduction amount.
g gmmT+++1) ++++) TT) =(I aX,X, 0 g(mT)
(52)
xXxxX - N X g(
(53)
VN
14

---

Under review as a conference paper at ICLR 2020
Since E B[X x ,[ = E, and ev is independent with Xy and ((mT), the expectation of Eq. 53 is equal to O. Therefore,
0 ( g(mT) | -(I (2) 1 a2i) S0ommgomm ] -pt+2M(((m21)
(54)
(55)
which suggests the covariance between g (() and ((T++ is exponentially decayed.
For every other term appearing in Eq. 41 have the following conclusions. First, similar with SGD, we have the formula about gradient descent shrinkage as:
(I - xxx F F X ( (((T+))))
(56)
= -I a 0 m (() 1(1 - aL)
(57)
+ + X O ( (mT++)) X6 1 EE E (1x)
(58)
= (I - ( g 1(I-a0 - -aE)
(59)
xxx" + +2bb En x M( xx | (M(
(60)
Using Eq. 54 we have following conclusion for variance reduction term from control variate. We
first take expectation over (1mm++1000 p(m))) T with Eq. 54 due to the independence among X XN and 0.
B[a(I - ax,,, (m( (X,X, - XxXX]]
(61)
Exa.XN aXoX P' (X662 - XNxXN
(62)
-a-b-- (Enlaaa P'M(O((MT)) Jaa - (-EP'M(O(M))
(63)
( E [[a XN ) gLMT+)) T (1- aXxx,
(64)
ExI.XN |a(XxX) - XNXX XxXX)M(((mMT) -1axx1)) = -aab-- Banlaa M(O(mI)) p' 1 EM(O(m))) pl..)
(65)
(66)
For the forth term, which represents the variance of g (mT++t) consider the independence between X6 and X and get
E
2 XN X
(X,X, XxXX)]
(67)
=a² 2 N + b
(E M T EM(O(mL))))
(68)
Nb
Thus,
M(olmt+e41) (u///i M(O(mT+0)) a22
(69)
+ +a²b-1 1 Eun wxx M( +1) xx 1 EM E ((((T()))) )
(70)
N + b
2
Em [wxr M((((T))
T| EM(O
(71)
Nb
2b
Eng [xx "M(((m)) (' p'ax EM(O(()) (..d
(72)
2b1
Em |vx T TourTp (O(()((T))
EP''(O('TTT)))
(73)
a² 2209
Σ
(74)
N
15

---

Under review as a conference paper at ICLR 2020
Under our definition, it can be expressed as:
M(e M(((noT-et))
a²
input noise (M((iintt))
a a²
(75)
i gradient descent shrinkage
label
a N + b c (M((ommm) Nb
(c (M((OL + c (P*M(((T)) )
b
variance due to 3(mTT T44)
Variance reduction from control variate
E THE PROOF OF THEOREM 4
Theorem 4. Given the noisy linear regression objective function (Eq. 3 under the assumption that
(0, E) with Σ diagonal and 0 0, the dynamics for SVRG in m()) )) given by:
m((((++1))) =M(a, b, T, N, E)m(( 0 (()m)) +1 ((( R² [[ R) N
T-1
Ma, ,T,, =R
R pt + (I- --RR") (T R) F
Proof. Form lemma 3 and lemma we can get:
m (0(mmm (m(mT+++l)) Rm @ (m)+ QP' p( Fm((((TT) + +N-1 n
(76)
where
R= (I aE)² + a² (I diag(E) diigg())
2a² (I diag E)diag E) T)
Q
(77)
F aN + b) (5.2 + (i)g(E)daa((E) T)
n = a² d'digg()>) (.)
(78)
Nb Recursively expending the above formula from m (0((m++))T) to m((mm))), we can get the follow- ing result:
m m m((((m+))T)))
(79)
R [R [Rm(0((T+T22)) - 2P (m((nT))) + Fm(o((T) + nn
(80)
Q (0(mm))) + Fm (m))) + N
(81)
= R2 mlm -
1t QP (T m m(((m))
(82)
k=
R*b
(Fm(O(mTT)) + NN
(83)
k=0
(84)
T-1
Rº m((mml))
-
Σ R pf-Im(((
(85)
T-1
Σ R²t)
(Fm(O(nT))+ + +N-
(86)
k=0
T-1
= R m(@(nnT)
Σ
Rtt R²QP-K) PT (o0-k>)TT-P11 (Q0(((mm)
(87)
k=0
+ +(I (1- R [[ - R)
(Fm(O(mTi) + -N'
(88)
16

---

Under review as a conference paper at ICLR 2020
In other word, Eq. 79 describe the dynamic of expected second moment of iterate between two nearby snapshots,
0 ( X(a, b, T,N, m m((m))) + (1 R R² R) R)-1 n
m
(89)
N
where
X,,,,,,,N,2) RD
Σ R QP- pT-1 (1- R1 RD-
(90)
Since I - R and I - Rd are commutable,
I-R = (I- R) (I - (I R RT) R) I-R
F THE PROOF OF COROLLARY 5
Corollary 5. Without the label noise, the dynamics of the second moment following SGD is given
by,
m(0 = (
and the dynamics of SVRG is given by,
m(0 1)T)) X(a, b, T, N,
where X is defined in Eq.( 17
Proof. If without label noise, i.e. of = 0, we can directly draw the corollary for the setting without
label noise, based on Theorem 2 and Theorem 4 Setting og = 0, we can draw:
m(0()) = Rt m ()))
and the dynamics of SVRG is given by,
m m(((m+1)))) M(a, b, b, (
where À is defined in Eq.
G THE SENSITIVITY OF N
In our theoretical analysis (Section 3 we evaluate large batch gradient g to control variance. That because any number data points can be directly sampled form the true distribution. But in order to compare the computational cost between SVRG and SGD, set the number of data points used to calculate g as N, which is slightly different with the original SVRG's setup of full-batch gradient. Therefore, we evaluate the sensitivity of N to illustrate when N is beyond threshold, it will cause little difference in convergence speed for SVRG.
10a.
10a
2-248
SVRG Loss
10.
Minimum Loss
100
SURG 5.128 N4456752
SVRO 9229 N2393220
10-1
10-2
10-3
10-5
10-4
2000
4000
2 Computational
1e6
Sensitivity of N Figure 5: Evaluate the sensitivity of N in Figure 5a with 0.5, T 256 and b 64 for SVRG under the noisy least square model. And compare large batch SGD to SVRG Figure 5b with T = 256 and fixing computational budget as 2048, varying b', N for SVRG.
(b) Large-batch SGD vs. SVRG
17

---

Under review as a conference paper at ICLR 2020
From figure Sa least square model, but it determines constant term of label noise in Eq. 9 @hich determines the level of final loss.
tell N has little effect the convergence speed of SVRG under the noisy
Besides, we also compare large batch SGD to SVRG in Figure 5b under the computation budget b = 2048 with fixed snapshot interval = 256 for SVRG, expentionally picking 50 learning rates from 1.5 to 0.01, varying 6', NN according to b' {1 76)6. )6.
18


Reviews:
[{"review_id": "SyxZrW16Yr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "\t\nThis paper aims to compare SGD and SVRG in deep learning, motivated by recent results that SGD performs better than SVRG, despite the latter's theoretical optimality.\nThe idea in the paper is to study this problem through linear regression by establishing \nsome asymptotic bounds for both SGD and SVRG. By looking into the terms of these bounds one can initiate a comparative study. A mixed picture is presented in the experiments which roughly agrees with some of the authors' claims.\n\nThere are, however, several important issues with the paper that require a major revision:\n\n1) The connection between neural networks is never really established. There is also an obscure relationship between 'overparameterized/underparaterized' neural networks and 'without/with label noise'. While this relationship is important to switch our attention to a much simpler problem, the specifics are not explicated.\n\n2) The theoretical content is not novel. All results on second moments (and more) are well known. \nFor example, [4] have both non asymptotic analysis, and a characterization of sampling variance for general SGD --- the assumptions of normal X with diagonal variance are very restricting (and unnecessary).\nAdditionally, the assumption of \\theta_\\star = 0 is not exactly WLOG.\n\n3) The related work is not well cited. Examples: \n\n 3a) \"Instead of using the full gradients, the variants of SGD...\"\n  The citations for SGD here are a bit confusing: Robbins and Monro never talked about SGD; Duchi et al is not about standard SGD, and so on. Better references are [1, 2].\n\n 3b) \"The sampling variance and the slow convergence of SGD have been studied extensively\nin the past (Robbins & Monro, 1951; Polyak & Juditsky, 1992; Bottou, 2010).\"\nNone of this paper studies sampling variance of SGD. RM (1951) only study convergence of stochastic approximation. PJ (1992) is about iterate averaging. Bottou (2010) is also not about sampling variance, and only covers convergence on a high-level. \nLook at [4] for the sampling variance of SGD procedures; also [5, 6].\n\n3c) \"Our main analysis tool is very closely related to recent\nwork studying the dynamics of gradient-based stochastic methods.\"\nMisses important prior work in stochastic approximation dynamics.\nLook at [7].\n\n\n[1] Zhang, \"Solving large scale linear prediction problems using gradient descent algorithms\" (2004)\n[2] Bottou, \"Large-Scale Machine Learning with Stochastic Gradient Descent\" (2010)\n[3] Amari, \"Natural gradient works efficiently in learning\" (1998)\n[4] Toulis and Airoldi, \"Asymptotic and finite-sample properties of estimators\nbased on stochastic gradients\" (2017)\n[5] Li et al, \"Statistical inference using SGD\" (2017)\n[6] Chen et al, \"Statistical Inference for Model Parameters in Stochastic Gradient Descent\" (2016)\n[7] Kushner and Yin, \" Stochastic approximation and recursive algorithms and applications\" (2003)", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1lyVZU_dB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper examines the tradeoffs between applying SVRG and SGD for training neural networks by providing an analysis of noisy least squares regression problems as well as experiments on simple MLPs and CNNs on MNIST and CIFAR-10. The theory analyzes a linear model where both the input $x$ and label noise $\\epsilon$ follow Gaussian distributions. Under these assumptions, the paper shows that SVRG is able to converge to a smaller neighborhood at a slower rate than SGD, which converges faster to a larger neighborhood. This analysis coincides with the experimental behavior applied to neural networks, where one observes when training underparameterized models that SGD significantly outperforms SVRG initially, but SVRG is able to attain a lower loss value asymptotically. In the overparameterized regime, SGD is demonstrated to always outperform SVRG experimentally, which is argued to coincide with the case where there is no label noise in the theory.\n\nStrengths:\n\nI liked how the authors distinguished between the underparameterized and overparameterized regimes in the analysis and experiments. This allowed them to observe different behavior between the two regimes when comparing SVRG and SGD. I also found the authors' setting of analyzing noisy least squares problems to be interesting because of its potential usefulness for both analytically and empirically understanding certain forms of DL phenomena. The introduction is also well-written.\n\nWeaknesses:\n\nOne aspect that I found unclear about the paper is its definition of the SVRG algorithm. In the analysis, the paper examines the expected risk least squares problem, and (if I understand correctly), considers the version of SVRG where the snapshot gradient is sampled i.i.d. over a large batch randomly from the true distribution. This is in contrast to the original SVRG method, which was designed for the empirical risk (or finite-sum) problem, where the set of datapoints is fixed. This coincides with the experiments, where the full training set is used to evaluate the snapshot gradient. Is this the correct interpretation of the theoretical and experimental results?\n\nIf so, how does this theoretical version of SVRG compare to a stochastic gradient method with large batch size? Does the theoretical behavior and insights exhibited by SVRG differ significantly from the theoretical behavior of SGD with larger batch size? \n\nIn addition, is the noisy least squares regression model with a diagonal data covariance equivalent to a separable quadratic problem? If so, it may not be surprising that the expected second moment of each parameter would evolve independently from each other, as noted at the end of Section 2.\n\nI also found some of the theorems and proofs difficult to follow. This is partly due to some inconsistent notation: what is $B$ (vs $b$) (pg. 4)? Is $A = M$ (pg. 4)? What does $\\circ$ denote in the exponents in the Appendix? What is the meaning of the constants defined in Definition 1? Some further explanation of the theoretical results (such as the meaning of those constants and more directly comparing the bounds for SVRG and SGD) would help with interpreting their results, particularly Theorem 4. \n\nAlong these lines, is it true that the rate of convergence for SGD is faster than the rate for SVRG? The constants made this difficult to tell, and no explanation was provided (although this was claimed in the Experiments section).\n\nMost steps in the proof were also left unexplained, which made it difficult to follow without knowledge of certain properties of multivariate Gaussians. Some necessary assumptions were also missing from the definition of the model; in particular, the paper did not specify the relationship between $\\epsilon_i$ and $x_i$ (which I assume are independent). \n\nThe experiments could also certainly be reinforced with some larger scale experiments on some larger datasets (such as ImageNet). One could see that the results became much more messy in the case of the underparameterized CNN on CIFAR-10 for example, and I wonder if this phenomena still holds with much larger datasets.\n\nSome additional typos:\n- Should use \\citep for the Johnson & Zhang reference at the end of page 3\n- SVRG Dynamics and Decay \"R\"ate in page 5\n\nOverall, although the paper provides an interesting observation and direction in contrasting the underparameterized and overparameterized regimes when comparing SVRG and SGD for training DNNs, in my opinion, the paper needs some additional refining, particularly in terms of clarity with respect to the theory and notation, and perhaps some more experiments. If I understand the theoretical and empirical SVRG algorithms correctly, I'm not currently convinced that the paper provides substantially more theoretical insight than before due to differences between the theoretical and empirical SVRG methods applied in this paper and the theoretical algorithm's similarity to large-batch SGD. The observation in the underparameterized regime, for example, has been highlighted in prior work even with logistic regression (particularly due to the cost of evaluating a full gradient), and a theoretical comparison of small-batch SGD and large-batch SGD neighborhood results for strongly convex problems (see Bottou, Curtis, and Nocedal (2018), for example) would lead to similar conclusions. Because of these reasons, I do not recommend this paper for publication at this time.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "B1ghYumwKH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper compares SGD and SVRG (as a representative variance reduced method) to explore tradeoffs. Although the computational complexity vs overall convergence performance tradeoff is well-known at this point, an interesting new perspective is the comparison in regions of interpolation (where SGD gradient variance will diminish on its own) and label noise (which propogates more seriously in SGD vs SVRG). The analysis is done on a simple linear  model with regression, with some experiments on simulations, MNIST, and CIFAR.\n\nOverall, I find the paper insightful and the nice and neat breakdowns of the sources of noise nicely interpretable. A weakness is that the regression model and linear separation is a bit oversimplified, and may not really capture the subtleties in deeper models. However, I didn't find the conclusions particularly controversial, so it's not obvious that the model is wrong--just very simple. \n\nHow are step sizes chosen in the experiments? In general, a huge benefit of variance reduction is the ability to use constant step sizes. Can the authors elaborate on a comparison between SGD with decaying step size vs SVRG with constant step size?\n\nOne suggestion I would push for is to extend the experiments in the plots. In a lot of cases it doesn't really seem like the experiment is done running, e.g. fig 2 (b), 4 (b), and it's hard to make sweeping statements about the final loss without running to that point. Since many of the experiments seem to be on relatively small datasets and easier models, this should not be too burdensome.\n\nWhile I like the breakdown of M vs m (for when the data is i.i.d.), I would say that the assumption that data is i.i.d. is not very realistic. That being said this is not a huge negative for this paper because both scenarios are considered. \n\nminor stuff:\ntypo in theorem 4 (decay rate)\n\nPost rebuttal: I read the comments and all the concerns are addressed. I don't really have any more major concerns about the paper.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Two reviewers as well as the AC are confused by the paper—perhaps because the readability of it should be improved?  It is clear that the page limitation of conferences are problematic, with 7 pages of appendix (not part of the review) the authors may consider another venue to publish.  In its current form, the usefulness for the ICLR community seems limited.
Decision: Reject