Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: 	
This 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.
The idea in the paper is to study this problem through linear regression by establishing 
some 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.

There are, however, several important issues with the paper that require a major revision:

1) 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.

2) The theoretical content is not novel. All results on second moments (and more) are well known. 
For 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).
Additionally, the assumption of \theta_\star = 0 is not exactly WLOG.

3) The related work is not well cited. Examples: 

 3a) "Instead of using the full gradients, the variants of SGD..."
  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].

 3b) "The sampling variance and the slow convergence of SGD have been studied extensively
in the past (Robbins & Monro, 1951; Polyak & Juditsky, 1992; Bottou, 2010)."
None 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. 
Look at [4] for the sampling variance of SGD procedures; also [5, 6].

3c) "Our main analysis tool is very closely related to recent
work studying the dynamics of gradient-based stochastic methods."
Misses important prior work in stochastic approximation dynamics.
Look at [7].


[1] Zhang, "Solving large scale linear prediction problems using gradient descent algorithms" (2004)
[2] Bottou, "Large-Scale Machine Learning with Stochastic Gradient Descent" (2010)
[3] Amari, "Natural gradient works efficiently in learning" (1998)
[4] Toulis and Airoldi, "Asymptotic and finite-sample properties of estimators
based on stochastic gradients" (2017)
[5] Li et al, "Statistical inference using SGD" (2017)
[6] Chen et al, "Statistical Inference for Model Parameters in Stochastic Gradient Descent" (2016)
[7] Kushner and Yin, " Stochastic approximation and recursive algorithms and applications" (2003)
review_title: Official Blind Review #3

final_score: rating: 6: Weak Accept
review_content: 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.

Overall, 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. 

How 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?

One 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.

While 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. 

minor stuff:
typo in theorem 4 (decay rate)

Post rebuttal: I read the comments and all the concerns are addressed. I don't really have any more major concerns about the paper.
review_title: Official Blind Review #2

final_score: rating: 3: Weak Reject
review_content: 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.
review_title: Official Blind Review #1

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