Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: The paper shows that the variance of the gradient has an inverse dependence on the batch size in linear networks, subject to the knowledge of the initial weights. The main novelty of the paper is the computation of an exact dependence between batch size and variance of the gradient in the linear regression setting. In addition to that, the authors conduct a lot of experiments involving non-linear networks and real-world datasets, that show the inverse dependence of the variance of gradient and batch size throughout the training.


My major concern is that the authors don't provide an application of their theorems, i.e. a setting where the exact knowledge of the variance of the gradient is useful. It will be useful to know if their theorems help tighten the convergence rates of mini-batch SGD in convex regression or improve generalization bounds for mini-batch SGD. Or can the authors say that their theorems help to tune the learning rate when going from large batch SGD to small-batch SGD? Without any such application, I believe the theorems are incomplete.

My other concerns are the following:
1. The authors prove that the variance is inversely dependent on the batch size. However, their theorems also imply the variance of the gradient keeps on increasing with time. Hence, a convergence theorem with an appropriate learning rate decay will be helpful. I see in the experiments the authors have used the learning rate as $1/t$. A justification will be really helpful.
2. Most of the experiments in the paper have been conducted on non-linear networks and non-gaussian data (like MNIST and YELP). Hence, a rough idea about how the theorems can be extended to ReLU networks, even in the over parametrized case, will be highly appreciated. 
3. The experiments show that small-batch SGD can reach lower training loss. Can the authors show why the training loss decreases with increasing variance in gradient, at least in the linear regression case?

My scores are on the lower side mainly because I believe the authors need to show some application of their theorems. I am happy to discuss this with the authors and other reviewers during the discussion period.

Minor concern:
The abstract and introduction have writing issues. However, I haven't taken them into account in my score. I would request the authors to improve those sections soon.
review_title: Official Blind Review #1

final_score: rating: 6: Marginally above acceptance threshold
review_content: ## Summary and contributions

This paper tackles the problem of the impact of mini-batch size on the variance of the gradients of SGD. Unlike most work on the topic, it does not study the variance of the gradient conditionned over the last iteration, but rather the absolute variance of the gradient conditioned only on the initial point.

The paper restricts itself to linear models, either with least mean square regression or deep linear model with 2 layers (which would be non convex but still linear).
The paper shows two results. For linear models, the variance of the gradients conditionned on the initial point is decreasing with the batch size b.
For a deep linear model, the result shows that the variance of gradient is a polynomial in 1/b with no constant term. Therefore, for b >= b0 for some b0, the variance is decreasing with b.

## Review

This paper tackles the problem of the variance in SGD from a novel angle, namely the total variance conditioning only on the initial weights, and not on the previous iteration as usually done.

The result on linear regression seems very natural, and the proof is done elegantly (I checked up to the proof of Theorem 1).

I haven't checked the proof for the deep linear network. The result is more interesting than in the linear regression case because the 2 layers linear network is non convex, and therefore, one can imagine having multiple local minima and 2 different trajectory starting from the same point to diverge at some point, which could lead to drastically different gradients. This is not really possible for least mean square with a full rank hessian, as there is a single optimum, and in any case all trajectories will end up at the same place.

Having a small total variance conditioned only on the initial point means that somehow the trajectories for different samplings cannot diverge too much. Of course, if the batch size goes to infinity, one is doing gradient descent, and all the trajectories are exactly the same which is compatible with theorem 4. I think the proof technique is interesting to be able to bound or study deviations between trajectories. However, in its current form it is non practical as the bound is very complex and in particular can increase as the iteration increases. In essence, the results says that for any iteration, as B increases, trajectories get closers, but it does not say that they will stay close for any iteration number.

I must say that while the theoretical part is doing a good job, the experiment part in Section 4 is quite poor.
The author tries to open up to the problem of generalization. 
Speaking of figure 1 b), the authors say that the validation loss improves with the batch size, i.e. the generalization ability is better with large batch sizes. This however contradicts previous work that have been mentioned by the authors in their very introduction. The authors do not comment on this contradiction. My own conclusion is that deriving general results on generalization from MNIST is a perilous exercice, if not plain wrong.


## Conclusion

Overall, I would say that this paper is just above the acceptance bar, because the theory holds up well and could be of interest for finer analysis of the dynamics of SGD, and in particular of different trajectory starting from the same point (how quickly will they diverge?), although doing so would require significant extension to the present work.
The authors try to open up to the problem of generalisation but fail to a proper theoretical link with their own work, while their experimental results are obtained only on MNIST and therefor subject to caution (and in fact contradict previous work).


## Notes and remarks

- In the abstract, the authors write "for deep neural network with L2 loss, we show...". This is not true, the result is only for two layers deep linear network.
- Definition 1: the definition of the degree is a bit hand wavy, there should be some minimum over all possible decomposition of M. This is especially needed if for some X, both X and X^{-1} belong to \mathcal{X}.
- page 18, at the top: "We denote A = \sum ...", A has already been introduced before end of page 17, but with x_i x_i^T instead of C_i (both are equal of course).
- Section 4, comments on the loss of Figure 1: phrasing "loss is decreasing with b" is ambigous or wrong. For the training, the loss increases with the batch size. I guess the authors meant that the loss worsen with b (as low is good), but worsen != decreasing.
review_title: Review of the impact of mini-batch sgd size on...

final_score: rating: 4: Ok but not good enough - rejection
review_content: This paper studied mini-batch stochastic gradient descent (SGD) for linear regression and linear neural networks. The analysis show that the variance of the stochastic gradient estimator is a decreasing function of b (mini-batch size). The authors also empirically validate their observations on MNIST and YELP review datasets.

I think the main result of this paper is not interesting. There are some comments.

1. The connection between mini-batch size and the variance of gradient estimator almost will be considered in any paper about SGD and I do not think this paper provide any novel perspective.
2. The analysis in section 3.2 discuss the extension on linear network, however, we are more interested in nonlinear case. The current analysis looks cannot be extended to nonlinear model directly.
3. The experimental section also should be improved. The structure of the network should be introduced in details. It is prefer to validate the proposed theory on more difficult task. MNIST and YELP cannot reflect the power of deep learning model.
review_title: reject

final_score: rating: 3: Clear rejection
review_content: This paper studies the variance of stochastic gradient in SGD conditioned on the initialization point. It shows that the variance of stochastic gradient is a decreasing function of minibatch size for linear regression and deep linear network. Compared with previous works that show similar the results for one step in SGD, the results in this work only rely on initialization point. 
Although the technique in this paper is different from previous works,  the setting in this paper can only handle linear model which is simple and limited. Besides, only showing that the tendency of gradient variance as minibatch size changes is not enough,  and it is better to give the decreasing rate. So the impact of the refinement on the estimation of gradient variance is not clearly stated. If the authors can provide some examples to show that the analyses in previous works are too coarse to give the wrong direction, the impact of this paper can be enhanced. In current version of the paper, I can not get any new insights from the theoretical and experimental results because there have been many existing works that can tell the relation (or tendency) between gradient variance and minibatch.  

Detailed comments: 
1. The notation "var()" is not rigorous because the gradient is high-dimensional. It should be replaced by the covariance matrix of a random vector.  Given that the gradient is a high-dimensional vector and the "variance" is a matrix, it is not clear that what the meaning of "the variance is a decreasing function of minibatch size" is. Does it mean that all the diagonal elements in the covariance matrix is a decreasing function?
2. It must be clarified that which distribution the expectation and variance are taken over. For example, var(\nabla L(w_t)) should be written as var_{w_t}(\nabla L(w_t)).
3. In the setting of deep linear network, the distribution of data is assumed to be normal distribution, which is strong. Is this condition necessary in the proof? 
4. The experiments are not sufficient to support the claim. Can you provide results for more selections of minibatch sizes, more datasets and more NN architectures?
5. In future works, the authors point out many interesting research problems, but it is not clear that why the techniques and results in this work can help to solve those problems. Can you provide connections between the main results and the future work? For example, which technique can help design better variance reduction method? Clarifying this will be helpful to evaluate the impact of this paper.
 
review_title: Minor refinement of the estimation of stochastic gradient

Meta-review: This work analyses the impact of mini-batch size on the variance of the gradients during SGD, in the context of linear models. It shows an inverse relationship between the variance of the gradient and the batch size for such models, under certain assumptions. Reviewers generally agree that the work is theoretically sound. However, all reviewers believe that the contributions of this work are limited. This concern was not adequately addressed during the discussion phase and led to the ultimate decison to reject.
Decision: Reject