The application of stochastic variance reduction to optimization has shown remarkable recent theoretical and practical success. The applicability of these techniques to the hard non-convex optimization problems encountered during training of modern deep neural networks is an open problem. We show that naive application of the SVRG technique and related approaches fail, and explore why.
This paper is thorough and well-written. On first look, the paper seems to be addressing a topic that I believe is already well-known in the DL community that has typically been explained by memory constraints or light empirical evidence. However, a more in-depth reading of this paper shows that the authors provide a serious attempt at implementing SVRG methods. This is demonstrated by their detailed implementation that attempts to overcome the main practical algorithmic concerns for neural networks (which may be beneficial even in the implementation of other optimization algorithms for deep learning) and their in-depth experiments that give concrete evidence towards a reasonable explanation of why SVRG methods currently do not work for deep learning. In particular, they claim that because the SVRG estimator fails to significantly decrease the variance, the increased computation is not worthwhile in improving the efficiency of the algorithm. Because the empirical study is fairly in-depth and thorough and the paper itself is well-written (particularly for DL), I’m more inclined to accept the paper; however, I still do not believe that the explanation is significant and novel enough to be worthy of publication, as I will explain below.
1. Performance of SVRG methods in convex setting
It is fairly well-known that even in the convex optimization community (training logistic regression), SVRG methods fail to improve the performance of SG in the initial phase; see [1, 5]. Often, the improvements in the algorithm are seen in the later phases of the algorithm, once the iterates is sufficiently close to the solution and the linear convergence rate kicks in. 
The experiments for neural networks presented here seem to corroborate this; in particular, the variance reduction introduces an additional cost but without much benefit in the main initial phase (epochs up to 150). 
One also typically observes (in the convex setting) very little difference in test error between SG and SVRG methods since it is unnecessary to train logistic regression to a lower error for the test error to stabilize. Hence, the test error results in the neural network setting feels unsurprising.
2. Comments/questions on experiments
(i) Batch Normalization: When you were obtaining poor results and divergence with applying SVRG directly with training mode on, what batch size were you using for the batch normalization? In particular, did you use full batch when computing the batch norm statistics at the snapshot point? Did you try fixing the batch normalization “ghost batch size” [4]?
(ii) Measuring Variance Reduction: When training the models, what other hyperparameters were tried? Was SVRG sensitive to the choices in hyperparameters? What happened when momentum was not used? How did the training loss behave? It may also be good to mention which datasets were used since these networks have been applied to a wider set of datasets.
(iii) Streaming SVRG Variants: Have you considered SVRG with batching, as proposed in [3]? 
(iv) Convergence Rate Comparisons: Is it reasonable to use the same hyperparameter settings for all of the methods? One would expect that each method needs to be tuned independently; otherwise, this may indicate that SVRG/SCSG and the SG method are so similar that they can all be treated the same as the SG method. 
3. Generalization
For neural networks, the question of generalization is almost as important as finding a minimizer efficiently, which is not addressed in-depth in this paper. The SG method benefits from treating both the empirical risk and expected risk problems “equally”, whereas SVRG suffers from utilizing this finite-sum/full-batch structure, which may potentially lead to deficiencies in the testing error. In light of this, I would suggest the authors investigate more carefully the generalization properties of the solutions of SVRG methods for neural networks. This may be highly relevant to the work on large-batch training; see [6]. 
Summary:
Overall, the paper is quite thorough and well-written, particularly for deep learning. However, the paper still lacks enough content and novelty, in my opinion, to warrant acceptance. They appeal to a simple empirical investigation of the variance as supportive evidence for their claim; if the paper had some stronger mathematical justification specific for neural networks demonstrating why the theory does not hold in this case, the paper would be a clear accept. For these reasons, I have given a weak reject. A response addressing my concerns above and emphasizing the novelty of these results for neural networks may push me the other way.
References:
[1] Bollapragada, Raghu, et al. "A progressive batching L-BFGS method for machine learning." arXiv preprint arXiv:1802.05374(2018).
[2] Friedlander, Michael P., and Mark Schmidt. "Hybrid deterministic-stochastic methods for data fitting." SIAM Journal on Scientific Computing 34.3 (2012): A1380-A1405.
[3] Harikandeh, Reza, et al. "Stopwasting my gradients: Practical svrg." Advances in Neural Information Processing Systems. 2015.
[4] Hoffer, Elad, Itay Hubara, and Daniel Soudry. "Train longer, generalize better: closing the generalization gap in large batch training of neural networks." Advances in Neural Information Processing Systems. 2017.
[5] Johnson, Rie, and Tong Zhang. "Accelerating stochastic gradient descent using predictive variance reduction." Advances in neural information processing systems. 2013.
[6] Keskar, Nitish Shirish, et al. "On large-batch training for deep learning: Generalization gap and sharp minima." arXiv preprint arXiv:1609.04836 (2016). 
[7] Smith, Samuel L., Pieter-Jan Kindermans, and Quoc V. Le. "Don't Decay the Learning Rate, Increase the Batch Size." arXiv preprint arXiv:1711.00489 (2017).