Stochastic gradient descent (SGD), which trades off noisy gradient updates for computational efficiency, is the de-facto optimization algorithm to solve largescale 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 the first few epochs in this regime. However, SGD is shown to always outperform SVRG in the overparameterized regime.
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.
Strengths:
I 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.
Weaknesses:
One 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?
If 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? 
In 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.
I 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. 
Along 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).
Most 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). 
The 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.
Some additional typos:
- Should use \citep for the Johnson & Zhang reference at the end of page 3
- SVRG Dynamics and Decay "R"ate in page 5
Overall, 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.