Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper analyzes the implicit regularization in SGD with finite learning rates via backward error analysis. The modified flow introduced in this paper better approximates the practical behavior of SGD as it does not require vanishing learning rates and it allows to use random shuffling in stead of i.i.d sampling. The numerical experiments validates the existence of the implicit regularization and how it affects the generalization of the model trained by SGD. The difference from SDE analysis is also discussed.

Reason for score:
1. The paper is well organized. Specially, I enjoy reading section II. The tool of backward error analysis and the derivation of the implicit regularization in SGD flow are introduced clearly and concisely. The analysis is based on random shuffling instead of i.i.d sampling matches the practical use of SGD.
2. The numerical experiments are very convincing. The consistency of SGD with larger lr and SGD with smaller lr plus explicit regularization validates the results of theoretical analysis. The numerical experiments also provide some insights into tuning hyper parameters such as learning rate and batch size.
review_title: Review of On the Origin of Implicit Regularization in Stochastic Gradient Descent 

final_score: rating: 7: Good paper, accept
review_content: This paper studies an implicit regularization mechanism of finite learning rate SGD by introducing explicitely a regularization term, using the framework of backward analysis.

They theoretically motivate their analysis, then empirically demonstrate it on CIFAR-10 using a Wide ResNet architecture.

This extends a previous (Barrett and Dherin, preprint) analysis of GD using the same framework, but limited to full batch GD. Noticeably, this new analysis using minibatch GD highlights an additional regularization of the trace of the covariance of per-example gradients.

In sec 2, however, I think it should be made clear that the setup is slightly different from minibatch GD, even when trained for a single epoch, in that there is an expectation accross permutations of sequences of minibatches. Can you discuss this assumption a bit more?

In terms of experiments, it would be useful to include other architecture/tasks, even toyish, in order to appreciate the generality of the empirical evaluation.

Overall, I think this contributes new interesting insights which are very relevant for studying minibatch GD in deep learning.
review_title: Good paper, can be improved by varying experiments

final_score: rating: 7: Good paper, accept
review_content: Summary: To analyze why the generalization error of SGD with larger learning rates achieves better test error, this paper analyzes the implicit regularization of SGD (with a finite step size) via a first order backward error analysis. Under this analysis the paper shows that the mean position of SGD with $m$ minibatches effectively follows the flow according to Eq (20) for a small but finite step size, while GD effectively follows the last inline equation in section 2.1. The paper shows empirically on an image classification task that by explicitly including the (implicit SGD) regularizer, SGD on the modified loss behaves similarly to using a larger learning rate when evaluating on the test set. The paper then extends this results to consider varying the batch size in section 3, showing that for small batchsizes the implicit regularization scales with the ratio of learning rate and batchsize $\epsilon/B$. Finally in section 4, the paper analyzes SGD when for each sampled minibatch in an epoch, we apply $n$ gradient steps with a stepsize $\epsilon/n$ and show that performance degrades as $n$ increases, suggesting that the benefit of SGD with larger learning rates is due to the implicit regularizer and not the temperature of an associated SDE. 

This paper is clearly written and well edited. I find the main result and the analysis technique interesting and novel. Although the experiments are well explained and help support the theory developed, there is only one experiment setting making it difficult to believe strong general claims such as those in section 4. I do have concerns about equating the "mean" behavior of SGD with the actual behavior of SGD and. 
 
Recommendation:
I recommend accepting this paper. As it currently stands, this paper is borderlin on the acceptance threshold for me. I like the novel use of the backward error analysis to gain insight into the behavior of SGD and I believe it would be of interest to ICLR readers. My main concerns are the papers' narrow focus on the mean behavior of SGD and the single experiment setting used to validate results. I would much more strongly support this paper if the theoretical analysis was stronger (e.g. analyzing the variance of individual SGD flows/regularizers to the mean SGD flow/regularizer) or if more experiments (in different settings) supported the results.  

Questions: 
If we don't take the expectation over $\xi(m)$ in Section 2.2, the theory suggests that there exist a (random) modified flow for each (random) ordering of minibatches $\hat{C}_0, \ldots, \hat{C}_m$ by equating equations (14) and (19). The main result Eq (20) would correspond to the expected value over the (random) modified flow. I believe this paper would be much stronger if there was some discussion of how the variance / deviations of these random flows from the mean flow (i.e the variance of $\xi(m)$) affects the implicit regularization and how this scales with batch size and properties of the loss. Would the implicit regularization break down for some experiments? 

Is the assumption that $m \epsilon$ is small reasonable (so that we can ignore the higher order $O(m^3 \epsilon^3)$ terms in the analysis)? Isn't $m = N/B$ the number of updates per epochs very large in practice since $N >> B$?

review_title: Borderline Accept Paper

final_score: rating: 7: Good paper, accept
review_content: ## Summary

Using backward error analysis, the paper argues that SGD with small but finite step sizes stays on the path of a gradient flow ODE of a modified loss, which penalizes the squared norms of the mini-batch gradients. This offers a possible explanation of the empirically observed positive effect of (relatively) large step sizes on generalization performance. The paper further contests previous findings based on a vanishing step size assumption.


## Rating

Similar to several recent works, this paper tries to explain certain aspects of stochastic gradient descent using a continuous time approximation. In contrast to existing works, it explicitly accounts for the effect of finite step sizes, which I think is a very interesting direction and surfaces several interesting aspects. I also welcome and endorse the critical discussion of prior work based on infinitesimal step size assumptions. Overall, the paper was interesting and pleasant to read. To the very best of my knowledge, all mathematical derivations are technically correct.

However—as the authors themselves note in their critique of SDE approximations to SGD—the devil is in the details with continuous time approximations. In my opinion, that makes is absolutely crucial to discuss the scope of the results carefully and transparently, including a critical discussion on assumptions made and simplifications that go into the continuous-time model. In my opinion, this paper fails to deliver that, which is why I recommend rejection. Below, I am asking for clarification on various points and would encourage the authors to respond to the major points in the rebuttal phase.


## Major Comments


1) The main result says that the *expected* SGD iterate after a *single* epoch lands close to the path of a gradient flow ODE on a modified loss. Unless I am missing something, this fundamentally fails to capture the behavior over multiple epochs. The analysis only guarantees that, from any given starting point $\omega_0$, the expected iterate after one epoch of SGD ends up close to the ODE path starting from $\omega_0$. Unless I am missing something, this does *not* imply that two epochs of SGD starting from $\omega_0$ end up on that path. We can not simply chain two epochs together: The first epoch only stays on the path in expectation, but any realization of that random variable will deviate from the path, which affects the initial condition of the next epoch. Intuitively, one needs to get a handle on the variance of the iterate as well in order to give guarantees for multiple epochs. Is this understanding correct? If so, to what extent can insights about a single epoch of SGD be transferred to practical settings?

2) Comment (1) hints at a larger (but vague) point that the paper is trying to characterize a *stochastic* optimization procedure with a solution of a *deterministic* gradient flow ODE. It does so by focusing on the *expectation* of the iterate, which might be an approach to highlight certain aspects, but it will never give a full picture. Why wouldn’t we also be interested in the covariance of the iterates? The limitations of this characterization should be discussed thoroughly in the paper.

3) In Section 2, the composition of the minibatches is assumed to be fixed and the randomness only comes from their ordering. The paper says: "It is standard practice to shuffle the dataset once per epoch, but this step does not affect our analysis and we omit it for brevity.“ I don’t think that statement is justified with respect to the result in Eq. (1), given that the modified loss depends on the minibatch composition. Therefore, would we reshuffle the dataset after each epoch, the modified loss would change from one epoch to the next. Later, in Section 3, the expectation is additionally taken over the composition of the batches. Why is the result presented in these two distinct steps? None of the key findings of the paper seems to rely on the intermediate fixed-composition result. It also doesn’t reflect the common practice of reshuffling the entire dataset and then traversing it, which simultaneously randomizes the composition and ordering of batches. So why not give the result of Eq. (22) directly? It is also the more intuitive result, invoking the trace of the gradient covariance matrix, which also appears in prior work on continuous time approximations of SGD.

4) While the analysis tries to account for finite step sizes, it still seems to assume step sizes that are orders of magnitude smaller than those used in practice. In particular, when going from Eq. (12) to Eq. (13), each minibatch cost function is equated with its second-order Taylor approximation around the starting point $\omega_0$. This is a *drastic* approximation and I don’t see any justification for why this should be anywhere near accurate for practical settings. For large datasets and moderate batch sizes, the number of updates in one epoch will be in the thousands. For realistic step size choices, a second-order Taylor expansion around the starting point will probably be rather poor after a handful of SGD updates, no?

5) The paper strongly emphasizes the assumption of sampling data points without replacement. While sampling without replacement is indeed the usual setting in practice, most of the stochastic optimisation literature builds on the assumption of sampling with replacement. And to my knowledge, no major differences (in terms of generalization performance) have been reported in the literature between the two approaches.
    a) Can the analysis presented in the paper be extended to setting of sampling with replacement? It seems to me that this should be straight-forward. Equations (12) and (13) should hold also when each minibatch is obtained from sampling with replacement. In that case, the expectation of the second-order correction term should directly give a result akin to Eq. (22). If that is in fact possible, it should definitely be added to the paper.
    b) If that is not possible, what prevents the application and is this a technicality or would you actually expect substantially different behavior in terms of generalization?
    c) It would also have been nice to see the experiments repeated with sampling with replacement to check empirically whether the findings hold in that case?

6) Something that bugs me from an optimization perspective is that the smoothness properties of the problem do not enter this analysis at all. For example, you write (near the bottom of page 4) that “our analysis assumes $m\epsilon = N\epsilon / B$ is small.” However, any given loss function $C(w)$ can be rescaled by a constant $M\gg 1$ while scaling the step size with $1/M$. This leaves the behavior of SGD unaffected while making the step size arbitrarily small. Why does that not enter into the analysis? It probably relates to my comment (4), seeing that the step sizes are assumed to be so small that they are not restricted by the smoothness of the function.


## Minor Comments

7) The paper derives the implicit regularizer and provides empirical evidence that it can partially explain the benefits of large step sizes for generalization. However, very little attention is given to the regularization term itself and to the question *why* this regularizer might be beneficial. The only comment speaking to that is that the regularizer penalizes “sharp” regions. I would like to see this discussion expanded and connected to the recent literature.

8) At the end of page 6, you write about the large batch size regime and say that the “we expect the optimal learning rate to be independent of the batch size in this limit.” It would have been great to substantiate that conjecture with an experiment and/or to refer to specific experiments done in prior work.

9) You repeatedly use the phrase “small but finite learning rates”. If my understanding is correct, that has phrase has a very precise meaning in the context of this work, namely that terms of order $O(\epsilon^3)$ are vanishingly small while terms that a quadratic or linear in $\epsilon$ can not be ignored. (This is in contrast to prior work that also ignores quadratic terms.) Maybe this could be stated clearly the first time you use this phrase.


## Typos / Style

- I think you should capitalize references to sections, equations, figures, et cetera.
- The bib file could really need some love. You are citing the arXiv versions for several papers that have been published in peer-reviewed venues. Capitalization in paper titles is messed up (e.g., “sgd”).

## Edit after Rebuttal

I thank the authors for their engagement with my review. Many of my comments and questions have been resolved and, consequently, I have increase my score and **recommend accepting this paper.**
review_title: Missing a discussion of the scope of the results and the assumptions that go into it

Meta-review: Dear authors,

all reviewers found many interesting contributions in your paper and also pointed out some minor/major issues. In your rebuttal discussions, you addressed most of them to their satisfaction and I hope you will incorporate them carefully also in your final submission.

I hence recommend accepting this paper


Decision: Accept (Poster)