Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: ## Edit after rebuttal

I have updated my evaluation (from 4 to 6) based on the changes made in the manuscript and the responses by the authors. See details in my response to the authors: https://openreview.net/forum?id=3q5IqUrkcF&noteId=qZzolK7E-wF

## Summary of the paper

This article analyses the discrepancy between the trajectory of the discrete numerical implementation of (full) batch gradient descent and the trajectory of the continuous gradient flow, for optimising over-parameterised models. The authors use backward error analysis to derive a modified loss whose gradient flow that better approximates the actual trajectory of gradient descent. The modified loss is the original loss plus a term that is proportional to the second moment of the loss gradients, the learning rate and the model size. The authors call this term "implicit gradient regulariser" and claim that it encourages flatter minima, higher test accuracy and more robust optima. 

## Summary of merits and concerns

### Merits

+ The paper presents a compelling mathematical analysis of the discrepancy between the actual trajectory of gradient descent and the gradient flow that determines it. The discrepancy is due to the discretisation of the gradient flow by a step size determined by the learning rate. This analysis sheds some light on why larger learning rate provides better results.
+ The mathematical derivations provided by the authors may be used by other researchers to better understand the dynamics of gradient descent.
+ The sections of the supplementary material concerned with mathematical proofs and derivations (I have more carefully read A.1 and A.2) are very clearly presented
+ The authors identify a good number of related articles.

### Concerns

- In my opinion, the authors overstate the role of the discrepancy between the gradient descent trajectory and the gradient flow in explaining the generalisation properties of over-parameterised models.
- The language used is confusing and contributes to the overstatement. For example, the authors state that "implicit gradient regularisation" "encourages", "guides", "has an impact on", etc., while it would probably be more accurate to say that it may help "explain" (some properties of gradient descent dynamics).
- Despite the rigour of the mathematical derivations, to the best of my understanding, the results do not fully support the claims that higher accuracy, flatter minima and better robustness are encouraged by implicit gradient regularisation, since other relevant aspects are not taken into account, such as parameter initialisation, model parameterisation, etc. In the same line, the experimental setup leaves important questions open and lacks transparency.
- There is substantial room for improvement regarding the readability of the paper. Examples are an overwhelming amount of cross-references back and forth between equations, figures, predictions, sections of the appendices, etc. that make it hard to navigate the paper; many of these cross-references are made before being introduced; repeated use of chains of multiple citations that certainly hinder the readability of some paragraphs.

## Evaluation and justification

While I acknowledge the merits and contributions of the paper---in particular the potential of the mathematical results for helping us understand the dynamics of gradient descent and, in a broader sense, the usefulness of the methods used here for studying machine learning problems---I contend that the theoretical and empirical results fall short at supporting the rather ambitious claims and that, at its current state, the impact of the paper is limited. These reasons, as well as my concerns about the clarity of the presentation and readability, led me to lean towards the recommendation of rejection. In the remaining part of my review I will discuss in more depth these concerns in order to better justify my recommendation and with the intention to provide constructive feedback for potential subsequent work on the paper.

### Overstated role of "implicit gradient regularisation"

The discrepancy in the trajectory of gradient descent with respect to the gradient flow is an intrinsic property of the method and a direct consequence of using finite step sizes, that is a positive learning rate. With an infinitesimal learning rate, the trajectory would perfectly approximate the gradient flow and, as a consequence, the optimisation could get stuck at the first critical point (for instance a suboptimal local minimum) after initialisation, in the case of non-convex loss landscapes. In other words, as it is well-known, a sufficiently large learning rate is required to escape local minima---the authors are of course aware of this simple and well-known notion and do mention it in the paper. Stating that implicit gradient regularisation "encourages" higher test accuracy and flatter optima, and "guides" gradient descent along shallower paths is an unnecessarily complicated way of putting the simple fact that gradient descent would not work if it followed the continuous gradient flow in infinitesimal steps. This said, I do acknowledge the rigour of the mathematical derivations and the fact that the results might be used to partly explain the dynamics of gradient descent.

In my opinion, one potential application of the backward error analysis of gradient descent presented in this paper is understanding the optimisation dynamics when the learning rate is larger. However, the analysis should be very careful and perhaps limited to the earlier stages of training, rather than focusing on the characteristics of the landscape at the end of the optimisation process, as it is analysed in the paper. A large learning rate actually prevents the algorithm from reaching better optima and in fact a common practice in neural network training is to decay the learning rate when the loss plateaus. Decaying the learning rate in turn anneals the "implicit gradient regulariser" $R_{IG}$ analysed in this paper, and brings the trajectory of gradient descent closer to the gradient flow. Implicit gradient regularisation would therefore fail to explain the characteristics of the loss landscape at the end of training if the learning rate is decayed, as is done in many successful models.

The optimisation trajectory that gradient descent follows with larger learning rate in over-parameterised models is an interesting subject of study and it may be analysed through backward error analysis as this paper proposes. However, in my opinion, this paper overstates the role of implicit gradient regularisation. I argue that the language used to state the claims exagerates the findings, since many other factors that play a role are not considered. Some examples are the following:

- "We find that IGR can account for the observation that learning rate size is correlated with test accuracy and model robustness" (Section 1)
- "EGR produces a boost of more than 12% in test accuracy" (Section 6)
- "networks with small learning rates or fewer parameters or both will have less IGR and worse test error" (Section 8)
- "solutions with high IGR are more robust to parameter perturbations" (Section 8)
- "IGR produces minima with low test error" (Section 8)

In sum, the main contribution of the paper seems to be Section 3, which shows "that gradient descent follows the gradient flow of the modified loss $\tilde{E}$ more closely than that of the original loss $E$". While this is a correct conclusion and the mathematical derivations are rigorous (though not very clearly presented), the relevant aspect is the implications of this on the dynamics and the relationship with the learning rate, which should be very carefully analysed as it is the cause of the discrepancy in the trajectories but it can lead to deficient optimisation. I believe that an interesting avenue is to analyse the role of larger learning rates on gradient descent dynamics, potentially through backward error analysis as in this paper, at early phases of training, following, for instance, on the work by Li, Wei and Ma (2019). This paper briefly outlines some ideas in this regard at the end of Section 3, but the focus diverges in the rest of the paper and the experimental results do not shed much light either (as discussed below). In my opinion, putting more focus on this aspect would make the paper stronger.

### Concerns about the experimental setup

In the experiments presented in the paper, the authors analyse $R_{IG}$ and the test accuracy "at the time of maximum test accuracy for each network that fits the training data exactly". However, we should note the following: First, the models trained on MNIST may achieve 100 % train accuracy, but as we can see in Figure A.2 of the appendix, the models do not achieve zero loss and there are differences depending on the learning rate. The authors also perform experiments on CIFAR-10, a more challenging task, but neither the training loss nor the training accuracy are reported in this case. It is claimed, in the case of CIFAR-10 in the appendix in Figure A.6, that "the test accuracy increases and the regularization value $R_{IG}$ decreases as the learning rate increases", but this could be simply explained because the models trained with smaller learning rate are simply not sufficiently optimised, with even lower training accuracy and loss. I would like to note that this denotes a relevant lack of transparency in the report of the results.

Similarly, from Figure 2a, the authors claim that $R_{IG}$ is smaller for larger learning rate x network size. While this generally holds across variation within each model, that is for increases in learning rate but not network size (the comparison highlighted in the figure), the conclusion is less clear for variation within each learning rate, that is for increases in network size but not learning rate. 

Another claim is that models trained with higher learning rate are more robust to parameter perturbation. This is an interesting observation, but the paper does not demonstrate that this is due to implicit gradient regularisation. The claim is derived in part from the claim that the end region in the loss landscape is flatter, whose connection with implicit gradient regularisation is problematic for the reasons stated above. Otherwise, the claim is derived from the experimental setup. However, only a few experiments are performed in this regard. For example, why is this only analysed on MNIST, but not on CIFAR-10 models? Furthermore, from the experiments on MNIST with various learning rates (Figures 3a and 3b), the authors conclude that "neural networks with larger learning rates, and hence, with stronger [implicit gradient regularisation] have smaller slopes at the time of maximum test accuracy" and "are more robust to parameter perturbations after training". However, how do the authors control that this is not due to the smaller training loss (Figure A.2) achieved with larger learning rate, as well as the longer effective (physical) training time (Figure A.4)?

### Clarity

Although there some parts of the paper that clearly presented, there are a few aspects that make some sections hard to read. I humbly believe that there is significant room for improving the clarity of the paper. I will use some specific examples to illustrate my concerns regarding clarity and readability:

- There are too many cross-references throughout the whole paper. The authors very often refer to equations, figures, predictions, theorems, etc. to illustrate their points. While this can be useful at times, if abused it runs the risk of making the paragraphs hard to understand and the paper difficult to navigate, at least in my case. This especially true if the references have not been introduced yet (often the case in sections 1 and 2), are several pages below (Figures 1 and 2 in pages 5 and 6 and referenced in page 2) and there are multiple pointers to the appendix. Take as an example the last paragraph in page 6: in one single paragraph there are 11 references to different parts of the paper. The paragraph, judging for the first sentence, should introduce the experiments on CIFAR-10. However, if one aims to understand and interpret the results on CIFAR-10, they would need a considerable effort and time to scrutinise the paper, especially several sections in the appendices, to finally conclude that the results are not reported with enough transparency. This lack of clarity not only makes the paper harder to read, but the confusion also hinders its transparency.
- In some paragraphs, there are so many citations that it is hard to read the sentences. Take, for instance, the first paragraph in Section 7. Probably more than half of the characters correspond to citations, with chains of up to 11 citations in one go and words ("stochasticity") hidden in between chains of citations. Is it really necessary to cite all these papers? If so, is this the best possible way in terms of clarity? Is the reader suppose to read all these papers? Some have referred to this as ["shotgun citations"](http://robertposhea.blogspot.com/2013/05/shotgun-citation.html). 
- Long mathematical derivations in-line within a paragraph are also hard to follow. The "clearest" example of this is the first paragraph in page 4. I would like to note that, in contrast, appendices A.1 and A.2 are very clear and well written, perhaps because the mathematical expressions are developed vertically with pertinent explanations.
- The legend of some figures is very small and therefore hard to read. See, for instance, Figure 1a.

## Questions and suggestions

Below I will list some questions or suggestions that occurred to me while reviewing the article. These have had a small impact in my assessment of the paper but the authors may find them useful for future work on this or subsequent papers. 

- As the authors acknowledge, one limitation of the present work is that it studies full batch gradient descent, while the optimisation workhorse in deep learning is stochastic gradient descent (SGD). I understand this limitation, but I think the paper would be stronger if it outlined some ideas for future work, perhaps related to previous work that has addressed SGD [1, 2].
- Another common practice in training deep neural networks is the decay of the learning rate. As discussed above, it is not obvious how implicit gradient regularisation would explain the benefits of learning rate decay and how these would be connected with the claims in the paper. DO the authors have any thoughts in these regards?
- "EGR produces a boost of more than 12% in test accuracy" (Section 6): While this seems impressive, a closer look reveals that the increase is from 62 to 74 % accuracy on CIFAR-10, that is well below the performance of typical architectures. By way of illustration, All-CNN (2014) achieves more than 90 % accuracy. This observation made me pay less attention to EGR and not really take it into account for my assessment, since the authors state that this is not the focus of the paper. However, since it is indeed included and discussed in the paper, I contend that the experiments should be more rigorous and the claims more careful.
- Inspired by EGR though, would it be an idea to consider an alternative loss of $E - R_{IG}$ (or along this line) so as to analyse a model that explains away the contribution of $R_{IG}$, for comparison theoretically or experimentally? I would need to think about this more carefully and see if it would make sense at all, since the discretisation would also affect this new loss.

## Minor comments and potential typos identified

The following list collects some minor comments or typos that I have identified. These are intended to improve the quality of the paper and did not have a substantial impact on my evaluation of the paper. The list is not organised into any particular order.

- The title may be too broad and slightly ambiguous.
- It seems that the authors used [hyphens](https://en.wikipedia.org/wiki/Hyphen) for parenthetical phrases, where an [em dash](https://en.wikipedia.org/wiki/Dash#Em_dash) would be probably more correct. Note that this occurs several times throughout the paper, but one example is in the first sentence of the introduction (Section 1).
- The meaning of variable $m$ is not explained in Equations 3 and 4.
- In Section 3, for better clarity, the authors may like to develop the acronym ODE (ordinary differential equation)
- In page 4, consider using "cancel out" instead of "kill"
- Typo: "we will _demonstration_ the effectiveness of EGR"
- Consider spelling "CIFAR-10" with upper case in page 4, as is commonly written, instead of "Cifar-10". Also for consistency throughout the paper.
- "are more robust to parameter perturbations after training (_Figure 3c_)" (page 6): I believe it should read "Figure 3b".
- In Section 7, considering mentioning data augmentation as an implicit source of implicit regularisation which is very commonly used in practice.
- Some relevant papers that the authors may consider discussing are [3, 4]
- It is not clear if the first paragraph in page 3 corresponds to Prediction 2.4, or it is a new paragraph.
- Theorem 3.1 refers back to Equation 2, while it would be clearer to explicitly express it there.
- Typo: "is a global _minima_" should probably read _minimum_
- The first paragraph of page 6 is really long and hard to read.


## References

[1] Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. arXiv:2003.07802, 2020.

[2] Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, volume 70, pp. 2101–2110, 2017.

[3] Gidel, Gauthier, Francis Bach, and Simon Lacoste-Julien. "Implicit regularization of discrete gradient dynamics in linear neural networks." Advances in Neural Information Processing Systems. 2019.

[4] Saxe, Andrew M., James L. McClelland, and Surya Ganguli. "Exact solutions to the nonlinear dynamics of learning in deep linear neural networks." arXiv preprint arXiv:1312.6120, 2013.
review_title: Nice mathematical analysis of gradient descent trajectory, but limited impact and improvable readability

final_score: rating: 6: Marginally above acceptance threshold
review_content: The authors show the discrete steps of gradient descent implicitly regularize models by penalizing trajectories that have large loss-gradients, which is called Implicit Gradient Regularization in the paper. The authors adopt a standard argument from the backward error analysis of Runge-Kutta methods to show this phenomenon. In the paper, the authors also provide some empirical results which indicate gradient descent leads to flat minima where test errors are small and solutions are robust to noisy parameter perturbations.

Overall, the paper is marginally above the acceptance threshold from my side. The paper proposes a natural form of implicit regularization when gradient descent is performed to train neural networks. I favor the explanation of the predictions made in the paper and the geometric interpretation of IGR. The experiment results seem to confirm the predictions made in the paper. The idea of backward error analysis is clear and comprehensible.

However, my major concerns are as follows and hopefully the authors can address my concerns in the rebuttal.

First, the paper is lack of existing literature reviews on related work on gradient norm regularization. This may impair the novelty of the paper. In particular, the paper considers explicit gradient regularization which has been discussed and studied for a long time. Moreover, the gradient regularization seems to be very natural in the gradient descent. Since the gradient descent converges by reducing the loss gradient, it seems not clear to me how much effect the additional gradient norm regularization R_{IG} plays in the process. As the authors stated in Prediction 2.2, it is possible that the loss surfaces have nearly equally flat minima. The impact of IGR seems to be unclear in reality. For now, the paper cannot fully convince me of the importance of such implicit regularization.

Second, the main proof techniques are not novel and have been widely used in the area of optimization and machine learning. The paper is sort of lack of technical novelty.

Third, given the sophisticated interactions between different sources of implicit regularization, the paper is lack of careful discussion on other related implicit regularization. The paper only lists some of the discovered implicit regularization in Section 7.


review_title: Recommendation to weak accept on "Implicit Gradient Regularization"

final_score: rating: 7: Good paper, accept
review_content: This paper provides a unique perspective on the implicit regularization effect of gradient descent that has been observed and studied previously. The authors point out that the discrete steps taken by the gradient descent updates means that the path followed through the optimization landscape is not that of steepest descent, but some alternate path. Thinking of GD as trying to solve the continuous time evolution equation implied by GD, they analyze the errors that the actual updates make in solving this equation. Given these errors, they construct an alternate ODE whose solution has a discretization that is precisely the GD updates (up to higher order corrections in the learning rate). Determining the loss implied by this alternative ODE gives an additional term, proportional to the norm squared of the gradient, the learning rate, and the number of parameters. This "Implicit Regularization'' leads to flatter optimization solutions, implying a positive effect on the generalization properties of models optimized under GD.

This work provides a very illuminating perspective on gradient descent through an extremely simple idea. The theoretical grounding for the idea is very sound (although I do have some questions about higher order corrections, see below). Relatedly, I think the "Explicit Regularization" presented (which is stated by the authors not to be the main focus of the paper) could be an influential idea and technique, but more experimentation would probably be necessary before that is likely to happen.

There's not too many weak points of the paper, but the following aspects did come to mind while reviewing. Focusing first on the theoretical parts of the paper, I wonder about the higher order corrections to the error analysis. It seems important to study them and e.g. see whether they have the signs and scaling expected for first correction to be valid widely. The authors do acknowledge that their regularization only holds for "moderate'' learning rates, but they don't attempt to determine what "moderate'' means. What scales do we compare the learning rate to in order to determine whether we're in this regime or not? The coefficient of the first term in the analysis scales with the learning rate and the number of parameters. How do higher order terms scale with the number of parameters? (This matters for understanding how implicit regularization works for larger models.) This sort of analysis seems rather essential and is unfortunately missing. Also, since the toy model is deterministic, there's no way to evaluate generalization error directly -- we only see that the regularization leads to a point on the minima curve with smaller gradient norm. It would be nice if there was a toy that also showed that this improves generalization explicitly, though this is obviously not essential for publishing the paper.

Synthesizing all the information above, I think this paper should be accepted. It is a really nice paper. I think the theoretical claims are broadly correct. I think the empirical methodology is sufficient, e.g. the concept is simple enough and the 2d linear model illustrative of the phenomenon. I think the paper is rather well written. The problem is clearly motivated, the authors explain the phenomenon they intend to study, the analysis of the phenomenon is clear, the toy model is nice and clear, and then confirming experiments follow.

One small criticism relates to the proof of Theorem 3.1, which is the central equation of the paper. The proof starts with a standard result in error analysis, the correction f_1, the derivation of which is in the supplementary material. Since this is so central to the paper, I think it would be nicer if the derivation was at least sketched in the main body of the paper. Perhaps the discussion could be trimmed to make room for such a derivation?


Finally, I have some additional questions and comments:

How does the implicit regularization phenomenon interplay with learning rate schedulers whose goal usually is to decrease the learning rate? Again, this makes me wonder what the intrinsic scale is that we should compare the learning rate to (probably related to the Hessian?) which dictates what the "moderate'' vs. "too small'' vs. "diverging'' regimes really are. 

Relatedly, I think it's a well-known fact that the large Hessian eigenvalues end up scaling like 1/(eta*t) over the course of training, with eta the learning rate and t the number of steps. Any comments on how this interplays with the implicit regularization as training progresses?

To my knowledge, usually "implicit regularization'' focuses on _stochastic_ gradient descent as having nice regularization properties. I understand that this paper focuses on only one aspect of the implicit regularization, but comparing to the continuous trajectory seems perhaps to be somewhat of a straw-man. It would be nice to understand how large an effect the regularization is due to discreteness is vs. the regularization due to stochasticity.

With that in mind, how far can the continuous trajectory and the regularized trajectory diverge after t steps? For the toy model, the paths really aren't all that different. If this is just an O(learning-rate) effect and the learning rate has to be small enough to be in the appropriate regime for the Taylor expansion to hold, then how significantly can this really matter in the training of real models? (This certainly motivates the introduction of explicit regularization, but as the authors point out, that's not the main focus of the paper.)

(As a side comment, it's not surprising that for the linear model in section 5 that the implicit gradient regularization is proportional to the L2 regularization of parameters given the relationship between the gradient and the parameter vector for linear models.)

Disclosure: I reviewed this paper for NeurIPS. I read the ICLR submission anew and updated my report accordingly.

review_title: A really nice paper about implicit regularization from the discreteness of gradient descent: the problem is clearly motivated, the authors explain the phenomenon they intend to study, the analysis of the phenomenon is clear, the toy model is nice and clear, and then confirming experiments follow.

Meta-review: The paper presents a mathematical analysis of the discrepancy between GD and GF trajectories. Following the discussion period, a knowledgeable R3 updated his/her initial rating from 4 to 6,  a knowledgeable R4 raised his/her score from 5 to 6. Finally, a very confident R1 considers this a good paper that should be accepted. He/she indicates that this paper provides a unique and very illuminating perspective on gradient descent through an extremely simple idea. The topic is very timely. I agree with R1 that the paper contributes a refreshing perspective with important elements which should be of interest to a good number of researchers. Taking into account the discussion, confidence levels and ratings of the reviewers, I am recommending the paper to be accepted. I would like to encourage the authors to take the reviewers' comments carefully into consideration when preparing the final version of the article. 
Decision: Accept (Poster)