Implicit Gradient Regularization
Authors: David Barrett
Benoit Dherin
Venue: ICLR 2021 Poster (2021)
Keywords: implicit regularization
deep learning
deep learning theory
theoretical issues in deep learning
theory
regularization

Abstract: Gradient descent can be surprisingly good at optimizing deep neural networks without overfitting and without explicit regularization. We find that the discrete steps of gradient descent implicitly regularize models by penalizing gradient descent trajectories that have large loss gradients. We call this Implicit Gradient Regularization (IGR) and we use backward error analysis to calculate the size of this regularization. We confirm empirically that implicit gradient regularization biases gradient descent toward flat minima, where test errors are small and solutions are robust to noisy parameter perturbations. Furthermore, we demonstrate that the implicit gradient regularization term can be used as an explicit regularizer, allowing us to control this gradient regularization directly. More broadly, our work indicates that backward error analysis is a useful theoretical approach to the perennial question of how learning rate, model size, and parameter regularization interact to determine the properties of overparameterized models optimized with gradient descent.

Published as a conference paper at ICLR 2021
IMPLICIT GRADIENT REGULARIZATION
David G.T. Barrett
Benoit Dherin'
DeepMind
Google
London
Dublin
bazetttdiid@ggoogeeeeco
dherinégoogle.com com
ABSTRACT
Gradient descent can be surprisingly good at optimizing deep neural networks with- out overfitting and without explicit regularization. We find that the discrete steps of gradient descent implicitly regularize models by penalizing gradient descent trajec- tories that have large loss gradients. We call this Implicit Gradient Regularization (IGR) and we use backward error analysis to calculate the size of this regularization. We confirm empirically that implicit gradient regularization biases gradient descent toward flat minima, where test errors are small and solutions are robust to noisy parameter perturbations. Furthermore, we demonstrate that the implicit gradient regularization term can be used as an explicit regularizer, allowing us to control this gradient regularization directly. More broadly, our work indicates that backward error analysis is a useful theoretical approach to the perennial question of how learning rate, model size, and parameter regularization interact to determine the properties of overparameterized models optimized with gradient descent.
INTRODUCTION
The loss surface of deep neural network is mountainous terrain highly non-convex with multitude of peaks, plateaus and valleys et 2018 Liu et al. 2020). Gradient descent provides path through this landscape, taking discrete steps in the direction of steepest descent toward sub-manifold of minima. However, this simple strategy can be just as hazardous as it sounds. For small learning rates, our model is likely get stuck at the local minima closest to the starting point, which is unlikely to be the most desirable destination. For large learning rates, we run the risk of ricocheting between peaks and diverging. However, for moderate learning rates, gradient descent seems to move away from the closest local minima and move toward flatter regions where test data errors are often smaller (Keskar et al., 2017 Lewkowyez et al. 2020 Li al.. 2019). This phenomenon becomes stronger for larger networks, which also tend to have smaller ler test error (Arora ctt al., 2019a| Belkin et al.) 2019; Geiger et al., 2020 Liang & Rakhlin 2018 Soudry ct al., (018). In addition, models with low test errors are more robust parameter perturbations (Morcos et al.) 2018). Overall, these observations contribute to an emerging view that there is some form of implicit regularization in gradient descent and several sources of implicit regularization have been identified.
We have found a surprising form of implicit regularization hidden within the discrete numerical flow of gradient descent. Gradient descent iterates in discrete steps along the gradient of the loss, after each step it actually steps off the exact continuous path that minimizes the loss at each point. Instead of following a trajectory down the steepest local gradient, gradient descent follows shallower path. We show that this trajectory is closer to an exact path along a modified loss surface, which can be calculated using backward error analysis from numerical integration theory (Hairer et al. (006)). Our core idea is that the discrepancy between the original loss surface and this modified loss surface is a form of implicit regularization (Theorem 3.1 Section 3
We begin by calculating the discrepancy between the modified loss and the original loss using backward error analysis and find that is proportional to the second moment of the loss gradients, which we call Implicil Gradient Regularization (IGR). Using differential geometry, we show that IGR also proportional to the square of the loss surface slope, indicating that encourages optimization paths with shallower slopes and optima discovery in flatter regions of the loss surface. Next, we
cqual contribution

---

Published as a conference paper at ICLR 2021
explore the properties of this regularization in deep neural networks such MLP's trained to classify MNIST digits and ResNets trained to classify CIFAR- 10 images and in a tractable two-parameter model. In these cases, verify that IGR effectively encourages models toward minima in the vicinity of small gradient values, in flatter regions with shallower slopes, and that these minima have low test error, consistent with previous observations. We find that IGR can account for the observation that learning rate size is correlated with test accuracy and model robustness. Finally, we demonstrate that IGR can be used an explicit regularizer, allowing us to directly strengthen this regularization beyond the maximum possible implicit gradient regularization strength.
THE MODIFIED LOSS LANDSCAPE INDUCED BY GRADIENT DESCENT
The general goal of gradient descent to find a weight vector Ô in parameter space R" that minimizes a loss E(O). Gradient descent proceeds by iteratively updating the model weights with learning rate in the direction of the steepest loss gradient:
0n+1 = 8, (()))
(1)
Now, even though gradient descent takes steps in the direction of the steepest loss gradient, it does not stay on the exact continuous path of the steepest loss gradient, because each iteration steps off the exact continuous path. Instead, show that gradient descent follows path that is closer the
exact continuous path given by i - E()). along a modified loss E(O), which can be calculated analytically using backward error analysis (see Theorem 3.1 and Section yielding:
Σ(0) (()) + (R),
where
A hm
(3)
and
1 Σ (V,)
RiG(0)=
(4)
Immediately, we see that this modified loss composed of the original training loss E()) and an additional term, which we interpret as regularizer (0) with regularization rate X. We call (o)( the implicit gradient regularizer because it penalizes regions of the loss landscape that have large gradient values, and because it is implicit in gradient descent, rather than being explicitly added to our loss.
Definition. Implicit gradient regularization is the implicit regularisation behaviour originating from the use of discrete update steps in gradient descent, as characterized by Equation 2
We now make several predictions about IGR which we will explore in experiments: Prediction 2.1. IGR encourages smaller values of RIG (0) relative to the loss F((A).
Given Equation 2 and Theorem 3.1 we expect gradient descent to follow trajectories that have relatively small values of RI It is already well known that gradient descent converges by reducing the loss gradient so it is important to note that this prediction describes the relative size of (0) along the trajectory of gradient descent. To expose this phenomena in experiments, great care must be taken when comparing different gradient descent trajectories. For instance, in deep learning experiments, we compare models at the iteration time of maximum test accuracy (and we consider other controls in the appendix), which is important time point for practical applications and is not trivially determined by the speed of learning (Figures 2 Also, related to this, since the regularization rate À is proportional to the learning rate h and network size (Equation 3), expect that larger models and larger learning rates will encourage smaller values of Ria (Figure
Prediction 2.2. IGR encourages the discovery of flatter optima.
In section we will show that RIa(0) is proportional to the square of the loss surface slope. Given this and Prediction 2.1 we expect that IGR will guide gradient descent along paths with shallower loss surface slopes, thereby encouraging the discovery of flatter, broader optima. Of course, it is possible construct loss surfaces at odds with this (such Mexican-hat loss surface, where all minima are equally flat). However, we will provide experimental support for this using loss surfaces that are of widespread interest in deep learning, such ML.Ps trained MNIST (Figure T
2

---

Published as a conference paper at ICLR 2021
Prediction 2.3. IGR encourages higher test accuracy.
Given Prediction 2.2, we predict that IGR encourages higher test accuracy since flatter minima are known empirically coincide with higher test accuracy (Figure -
Prediction 2.4. JGR encourages the discovery of optima that are more robust to parameter perturba- tions.
There several important observations make about the properties of IGR: 1) It does not originate in any specific model architecture or initialization, although our analysis does provide a formula to explain the influence of these model properties through IGR; 2) Other sources of implicit reg- ularization also have an impact on learning, alongside IGR, and the relative importance of these contributions will likely depend on model architecture and initialization: 3) In defining À and Rie we chose to set À proportional to the number of parameters m. To support this choice, we demonstrate in experiments that the test accuracy is controlled by the IGR rate X. 4) The modified loss and the original loss share the same global minima, so IGR vanishes when the gradient vanishes. Despite this, the presence of IGR has an impact on learning since it changes the trajectory of gradient descent, and in ver-paraaeterized models this can cause the final parameters to reach different solutions. 5) Our theoretical results are derived for full-batch gradient descent, which allows us to isolate the source of implicit regularisation from the stochasticity of stochastic gradient descent (SGD). Extending our theoretical results to SGD is considerably more complicated, and as such, is beyond the scope of this paper. However, in some of our experiments, we will demonstrate that IGR persists in SGD, which is especially important for deep learning. Next, we will provide a proof for Theorem 3.1 and we will provide experimental support for our predictions.
BACKWARD ERROR ANALYSIS OF GRADIENT DESCENT
In this section, show that gradient descent follows the gradient flow of the modified loss E (Equation [ more closely than that of the original loss E. The argument is a standard argument from the backward error analysis of Runge-Kutta methods (Hairer al. 2006). We begin by observing that gradient descent (Equation D can be interpreted as a Runge-Kutee Kutta method numerically integrating the following ODE:
i = VoE())
(5)
In the language of numerical analysis, gradient descent is the explicit Euler method numerically integrating the vector field {0) = (0). The explicit Euler method is of order 1, which means the deviation from the gradient flow
that after one gradient descent step 0, fn E ||0 - {h)]l is of order (h²). where (h) is the solution of Equation 5 starting at 6 and evaluated time h. Backward error analysis was developed deal with this discrepancy between the discrete steps of a Runge-Kutta method and the continuous exact solutions (or flow) of a differential equation.
The main idea is to modify the ODE vector field Ó = f(O) with corrections in powers of the step size
f(0) = f(0) + (0) + f2() +
(6)
so that the numerical steps 6, approximating the original Equation now lie exactly on the solutions of the modified equation 0 = f(0). In other words, backward error analysis finds the corrections fi in Equation 6 such that 0₂ = (nh) for all n, where O(t) is the solution of the modified equation starting at 0g In theory,
now precisely study the flow of the modified equation to infer properties of the numerical method because its steps follow the modified differential equation solutions perfectly in formal sense. The following result is direct application of backward error analysis to gradient descent:
Theorem 3.1. Let E be a sufficiently differentiable function on a parameter space 0 E R... The modified equation for gradient flow (Equation 5) is of the form
0 - + O(h))
where F. == F the modified loss introduced in Equation 2 Consider gradient flow with the modified loss Ô = v E(0) and its solution ((t) starting at On-1- Now the local ervor 1|0,- - -(h)]l between (h) and one step of gradient descent 6,p = 0,,
1 - hV ((,.-)) is of order Ohh2), while it is of order O(h2) for gradient flow with the original loss.
3

---

Published as a conference paper at ICLR 2021
Proof. We begin by computing fi for which the first two orders in h of the Taylor's Series of the modified equation solution ((t) at t h coincide with one gradient descent step. Since ('() = f(0). we see that 0" (t) (0) and we find that
0 + hf(00 - + hf(0) + + (2) -
yielding (1( = - (0() Now, when ʃ is a gradient vector field with f = VE, we find:
f1( = 1 (DBE)V V
where D is the Hessian of E(0). Putting this together, we obtain the first order modified equation:
i f= + hf + Oh?) = - V - ((0) + " 1I + -0(?)
which is gradient system with modified loss
E(0)- = E |EE
As for the local error, if (h) is a solution of gradient flow starting at 9n we have in general that ((h) 6n + Oh2)). The correction fi is constructed that it cancels out the (12) term in the expansion of its solution, yielding 0(h) = O.. Ohh)).
Remark 3.2. A direct application of a standard result in backward error analysis (Hairer & Lubich (1997). Thm. 1) indicates that the learning rate range where the gradient flow of the modified loss provides a good approximation of gradient descent lies below ho CR/M, where V is analytic and bounded by M in a ball of radius around the initialization point and where C depends on the Runge-Kutta method only, which can be estimated for gradient descent. We call this the moderate learning rate regime. For each learning rate below hg, we can provably find an optimal truncation of the modified equation whose gradient flow is exponentially close to the steps of gradient descent, so the higher term corrections are likely to contribute to the dynamics. Given this, we see that the exact value of the upper bound for the moderate regime will correspond to a setting where the optimal truncation is the first order correction only. Calculating this in general is difficult and beyond the scope of this paper. Nonetheless, our experiments strongly suggest that this moderate learning rate regime overlaps substantially with the learning rate range typically used in deep learning.
Next, we give purely geometric interpretation of IGR, supporting Prediction 2.2
Consider the loss
surface S associated with a loss function E defined over the parameter space 8 E TRm This loss surface is defined as the graph of the loss: S {(0, E(0)) : 0 E Rm) C R= We define (0) to be the angle between the tangent space S to S at 0 and the parameter plane, i.e., the linear subspace {(0, 0) E RT) in m= We can compute this angle using the inner product between the normal vector (0) to S at @ and the normal vector 2 to the parameter plane: a(9) arecos (N))). 2). Now we can define the loss surface slope at 0 as being the tangent of this angle: slope(0) == tan (0). This is a natural extension of the 1 1-dimensional notion of slope. With this definition, we can now reformulate the modified loss function in a purely geometric fashion:
Proposition 3.3. The modified loss E. in Equation 2 can be expressed in terms of the loss surface slope E(()= E()) 3 slope?(()
This proposition is an immediate consequence of Theorem 3.1 and Corollary A. in Appendix A.2 It tells us that gradient descent with higher amounts of implicit regularization (higher learning rate) will implicitly minimize the loss surface slope locally along with the original training loss. Prediction 2.2 claims that this local effect of implicit slope regularization accumulates into the global effect of directing gradient descent trajectories toward global minima in regions surrounded by shallower slopes- toward flatter (or broader) minima.
Remark 3.4. It is important to note that IGR does not help gradient descent to escape from local minima. In the learning rate regime where the truncated modified equation gives good approxi- mation for gradient descent, the steps of gradient descent follow the gradient flow of the modified loss closely, As Proposition shoos, shows, the local minima of the original loss are still local minima of the modified loss so gradient descent within this learning rate regime remains trapped within the basin of attraction of these minima. IGR does not lead to escape from local minima, but instead, encourages a shallower path toward flatter solutions close to the submanifold of global interpolating minima, which the modified loss shares with the original loss (Proposition) A.10
4

---

Published as a conference paper at ICLR 2021
4 EXPLICIT GRADIENT REGULARIZATION
For overparameterized models, we predict that the strength of IGR relative to the original loss can be controlled by increasing the learning rate h (Prediction 2.1). However, gradient descent becomes unstable when the learning rate becomes too large. For applications where we wish to increase the strength of IGR beyond this point, we can take inspiration from implicit gradient regularization to motivate Explicit Gradient Regularization (EGR), which we define as:
(0) E()) + A V EO)I
where, μ is the explicit regularization rate. which is a hyper-parameter that we are free to choose, unlike the implicit regularization rate À (Fquation 3 which can only by controlled indirectly. Now, we can do gradient descent on Ep with small learning rates and large J..
Although EGR is not the primary focus of our work, we will demonstrate the effectiveness of EGR for simple two parameter model in the next section (Section 5 and for a ResNet trained on Cifar- 10 (Figure Our EGR experiments act as control study in this work, to demonstrate that the Rig term arising implicitly in gradient descent can indeed improve test accuracy independent of confounding effects that may arise when we control IGR implicitly through the learning rate. Namely, if we had not observed significant boost in model test accuracy by adding the RIG term explicitly, our prediction that implicit regularization helps to boost test accuracy would have been in doubt.
Related work: Explicit regularization using gradient penalties has long history. In early work, Drucker & Le Cun (1992) used gradient penalty (using input gradients instead of parameter gradients). Hochreiter & Schmidhuber (197)) introduced a regularization penalty to guide gradient descent toward flat minima. EGR is also reminiscent of other regularizers such as dropout, which similarly encourages robust parameterizations (Morcos et al. 2018 Srivastava et al. [0144] Tartaglione ct al.] 2018). More recently, loss gradient penalties have been used to stabilize GAN training (Nagraajn & Kolter 2017] Balduzzi et al.) 2018) Mescheder et al., 2017; Qin et al. 2020). The
success of these explicit regularizers demonstrates the importance of this type of regularization in
deep learning.
5 IGR AND EGR IN A 2-D LINEAR MODEL
In our first experiment we explore implicit and explicit gradient regularization in simple two- parameter model with loss given by E(a, = (y f(:; a, b))² /2, where fæ; a, b) abæ is model, a, b E E are the model parameters and x, E IR is the training data. We have chosen this model because we can fully visualize the gradient descent trajectories in 2-d space. For a single data point, this model is overparameterized with global minima located along a curve attractor defined by the hyperbola ab y/z. For small learning rates, gradient descent follows the gradient flow of the loss from an initial point (4g, by) toward the line attractor. For larger learning rates, gradient descent follows longer path toward a different destination on the line attractor (Figure[p)
We can understand these observations using Theorem 3.1 which predicts that gradient descent is closer to the modified flow given by à - E(a,, b) and b Ea,E(a, b) where E(a,b) Fl(a,) b) + XRIG (a, b) is the modified loss from Equation 2 (a, is the implicit regularization term from Equation and X h/2 is the implicit regularization rate from Equation B with learning rate h. Although the modified loss and the original loss have the same global minima, they generate different flows. Solving the modified flow equations numerically starting from the same initial point (ag, by) as before, we find that the gradient descent trajectory is closer to the modified flow than the exact flow, consistent with Theorem 3.1 (Figure [p).
(la)2 + [b(2) x² F(aa b)
Next, we investigate Prediction 2.1 that the strength of the implicit gradient regularization RIo(a, b) relative to the original loss E(a, b) can be controlled by increasing the regularization rate X. In this case, this means that larger learning rates should produce gradient descent trajectories that lead to minima with smaller value of (ra(a, b)/E(a, b) x² (la|² + 16(²). It is interesting to note that this is proportional to the parameter norm, and also, to the square of the loss surface slope. In our numerical experiments,
find that larger learning rates lead to minima with smaller L2 norm (Figure [p)), closer to the flatter region in the parameter plane, consistent with Prediction 2. and 2.2 The extent which we can strengthen IGR in this way is restricted by the learning rate. For excessively
5

---

Published as a conference paper at ICLR 2021
(a)
(b) 4.60
ceal earving FOER madiee
4.55
rop globe
4.50
4.45
4.40
4.35
4.30
4.25
4.20
0.000 0.002 0.004 0.006 0.008 0.010 0.012 learning rate network size
Figure I: Implicit gradient regularization and explicit gradient regularization for simple 2-d model. (a) In this phase space plot, the loss surface of a simple overparameterized model is represented with arrows denoting the direction of gradient flow from each point, with global minima represented by a line attractor (black dashed line). Gradient descent trajectories originating from two different starting points are illustrated (from do 2.8, bu 3.5, and from ag 75, bo 74.925, off plot). The global minima in the flattest region of the loss surface and with lowest 1.2 norm indicated with black cross. For small learning rate, hs, gradient descent trajectories follow the exact gradient flow closely (green lines). For a moderate learning rate h gradient descent follows longer trajectory (red lines). This is closer the corresponding exact flow following the modified loss gradient, with = h2/ /2, consistent with backward error analysis. We also calculate the gradient descent trajectory with explicit regularization (dashed blue lines) using large regularization rates (p >> hM)) (b) The ratio RIG/ E at the end of training is smaller for larger learning rates (See Appendix A.4 for details).
large learning rates, gradient descent ricochets from peak to peak, until either diverges or lands in the direct vicinity of a minimum, which is sensitively dependent on initialization (Figure|A. A.I).
To go beyond the limits of implicit gradient regularization, we can explicitly regularize this model using Equation to obtain regularized loss E,, (a, 6) = E(a, b) + p (|a|2 1b|²) E(a,,))))))) b). Now, F (a, b) starting from the same initial
F,, (a, b) and point (4g, by), using very large explicit regularization rate (and using gradient descent with very small learning rate h for numerical integration, see Appendix (A.4) we find that this flow leads to global minima with small L2 norm (Figure [ in the flattest region of the loss surface. This is not possible with IGR, since would require learning rates so large that gradient descent would diverge.
if we numerically integrate
6 IGR AND EGR IN DEEP NEURAL NETWORKS
Next, we empirically investigate implicit gradient regularization and explicit gradicnt regularization in deep neural networks. We consider selection of MLPs trained classify MNIST digits and also investigate R8 8 trained to classify CIFAR-10 images. All our models are implemented using Haiku (Hennigan al. 2020).
To begin, we measure the size of implicit regularization in MLPs trained to classify MNIST digits with variety of different learning rates and network sizes (Figure 2 Specifically, we train 5-layer MLPs with ny units per layer, where n4 E {50, 100, 200, 400, 1600). h E (0.5, 0.05, 0.01, 0.005, 0.001, 0.0005), using ReLu activation functions and cross entropy loss (see Appendix A.5 for further details and see Figures AA.3 A.4 and A.5 for training and test data curves). We report Rie and test accuracy at the time of maximum test accuracy for each network that fits the training data exactly. We choose this time point for comparison because it is important for practical applications. We find that RJG is smaller for larger learning rates and larger networks (Figure 2), consistent with Theorem 3.1 and Prediction 2.1 Next, we measure the loss surface slope in 5-layer MLPs, with 400 units per layer, trained to classify MNIST digits with a range of different learning rates. We find that neural networks with larger learning rates, and hence, with stronger IGR have smaller slopes at the time of maximum test accuracy (Figure B4). We also measure the loss surface slope in the vicinity of these optima. To do this, we add multiplicative Gaussian

---

Published as a conference paper at ICLR 2021
(a)
(b)
* paramaters
119930
10
319816
Regularisation Ri
559610
3199210
11518410
Test Accuracy
10"7
98.0
paramaters
97.8
49350
119910
11538610
102
107
10 16
104
10F
10'
10
307
10"
learning rate x network size
À leamiing rate network size /
Figure 2: Implicit regularization and test accuracy: (a) Here, each dot represents a different MLP, with different learning rates and network sizes. Implicit gradient regularization RIG is reported for each model, at the time of maximum MNIST test accuracy and 100% train accuracy. We see that models with larger implicit regularization rate have smaller values RIG. (b) Networks with higher values of À also have higher maximum test accuracy values.
noise every parameter according to 0(1 + 11), where 0 are the parameters of fully trained model and 8, are the parameters after the addition of noise, where ~ (N,,0) o). We find that neural networks trained with larger learning rates have flatter slopes and these slopes remain small following larger perturbations (Figure 3a). These numerical results are consistent with our prediction that IGR encourages the discovery of flatter optima (Prediction 2.2
Next, we observe that improvements in test set accuracy are correlated with increases in regularization rate (Figure [p), and also with increases in learning rate and network size (Figure A.6). This is consistent with Prediction 2.3 Furthermore, the correlation between test set accuracy and network size m supports our use of network size scaling Equation
andd
Next, we explore the robustness of deep neural networks in response to parameter perturbations. In previous work, has been reported that deep neural networks are robust to a substantial amount of parameter noise, and that this robustness is stronger in networks with higher test accuracy (Morcos) al. 2018). We measure the degradation classification accuracy as we increase the amount of multiplicative Gaussian noise and find that neural networks with larger learning rates, and hence, with stronger IGR, are more robust to parameter perturbations after training (Figure 3b), consistent with Prediction 2.4 This may explain the origin, in part, of deep neural network robustness.
We also explore IGR in several other settings. For ResNet-18 models trained on CIFAR-10, we find that RIG is smaller and test accuracy is higher for larger learning rates (at the time of maximum test accuracy) (Figure A.7 A.8). consistent again with Theorem 3.1 and Predictions 2.1 and 2.3 We also explore IGR using different stopping time criteria (other than the time of maximum test accuracy), such as fixed iteration time (Figures A A..4), and fixed physical time (Figure A.5) (where iteration time is rescaled by the learning rate, see Appendix AA.5 for further information). We explore IGR for full batch gradient descent and for stochastic gradient descent (SGD) with variety of different batch sizes (Figure A.6) and in all these cases, our numerical experiments are consistent with Theorem 3.]] These supplementary experiments are designed to control for the presence, and absence, of other sources of implicit regularisation such as model architecture choice. SGD stochasticity and the choice of stopping time criteria.
Finally, we provide an initial demonstration explicit gradient regularization (EGR). Specifically, we train ResNet-18 18 using our explicit gradient regularizer (Equation 8 and we observe that EGR produces boost of more than 12% test accuracy (see Figure (3. This initial experiment indicates that EGR may be useful tool for training of neural networks, in some situations, especially where IGR cannot be increased with larger learning rates, which happens, for instance, when learning rates large that gradient descent diverges. However, EGR is not the primary focus of our work here, but for IGR, which our primary focus, this experiment provides further evidence that IGR may play important role as a regularizer in deep learning.
7

---

Published as a conference paper at ICLR 2021
(a) 4
(b) 100
Learning rate
(c)
74
0.25
Test Accuracy (%) CIFAR 10
72
Loss surface siope
0.06
60'
Test Accuracy
0.01
0.005
Leamiing
25
66
30*
05
01
065
20
000
50 parameter perturbation (%)
200
260 parameter perturbation (86)
80
0.00 14 Explicit Gradient Regularization
Figure 3: (a) We measure the loss surface slope the time of maximum test accuracy for models trained on MNIST, and we observe that the loss surface slope is smaller for larger learning rates, and the loss surface slopes remain small for larger parameter perturbations compared to models trained with small learning rates. We perturb our networks by adding multiplicative Gaussian noise to each parameter (up 300% of the original parameter size). (b) We measure the test accuracy robustness of models trained to classify MNIST digits and see that the robustness increases as the learning rate increases. (Here, solid lines show averages across perturbations and dashed lines demarcate one standard deviation across 100 realizations.) (c) Explicit gradient regularization (EGR) for ResNet- 18 trained on CIFAR-10.
7 RELATED WORK
Implicit regularization: Many different sources of implicit regularization have been identified,
including early-stopping (Hardt et al. 2016), model initialization (Glorot & Bengio 2010 Li &
Liang 2018
Nagarajan & Kolter 2018 Gunasckar et al. [0018) /Zhang et al. 2019 Zou et al. 2019)
model
architecture (Li et al. |0.1 8: Lin & Tegmark| [2016]
[|0mark|[006:]]]0 2.016:MMs Ma et al. 2020). stochasticity (Keskar
eet al.
2017;
Soudry al.. 2018 Roberts| (008ss]018|]] et al. 2020 Chaudhari & Soatto 2018 De &
Smith
[2000] Mandt et al. 2017 Park et al. [219)] Sagun et al.
[
2017||Smith & Le| 2018]]Wilso Wilson
al.
2017 /sstzzebski et al. (021). implicit L2 regularity (Soudry et al.] |008]] Neyshabur et al.
2015
Ali et al. 2019 Ji & Telgarsky 2019; Nacson et al.] |oggoo et 20119
Suggala et al.
2018).
9 low rank biases (Arora al. [019a Gunasekar al. Razin & Cohen (2020) among
other possibilities. A number of studies have investigated implicit regularization in the discrete steps of gradient descent for specific datasets, losses, or architectures (Soudry et al., 2018 Neyshabur ett all.,20015, Gidel et al.] IGR might also be useful for understanding implicit regularization in deep matrix factorization with gradient descent (Arora et al., [209a]] Gunasekar et al. 2017]] Razin & Cohen 2020), where gradient descent seems to have low-rank bias. Our work may also provide a useful perspective on the break-even point deep learning (Jastrzebski et al., 202T). At break-even point our backward analysis suggests that gradient descent with large learning rates will move toward flatter regions, consistent with this work. Stochastic effects are also likely to contribute to the trajectory at break-even points.
Learning rate schedules and regimes: Implicit gradient regularization can be used to understand the role of learning schedules, since learning rate controls the relative strength of implicit regu- larization and loss optimization. For example, for a cyclical learning rate schedule (Smith) 2017). cyclically varying learning rates between large and small learning rates can be interpreted cyclical variation between large and small amounts of IGR (i.e., alternate phases of optimization and regularization). A number of studies have identified various learning rates regimes characterized by different convergence and generalization properties. For instance Li et al. (2019) identifies a small learning rate regime where network tends to memorize and a large learning rate regime characterized by increased generalization power. This is consistent with IGR which we believe is most useful at the start of training, orienting the search toward flatter regions, and less important in later stages of the training, when a flatter region has been reached, and where convergence to any of the flatter minima more important. This is also consistent with Jastrzebski et al. (2021) who showed the importance of large learning rates at the beginning of training in encouraging more favourable optimization trajectories. Also Lewkowyez et al. (2020) identifies lazy phase, a catapult phase, and
divergent phase, which may be related to the range of backward error analysis applicability.
8

---

Published as a conference paper at ICLR 2021
Neural Tangent Kernel: The Neural Tangent Kernel (NTK) is especially interesting (Arora et al. 2019b|e Chizat & Bach, 2019 Jacot et al. 2018 Lee et al. 2019; Oymak & Soltanolkotabi 2019 Woodworth et a 2020; Cao & Gu|2019/ since, in the case of the least square loss, the IGR term R can be related to the NTK (see Appendix A.3). This is particularly interesting because it suggests that the NTK may play role heyond the kernel regime, into the rich regime. In this context, IGR is also related to the trace of the Fisher Information Matrix (Karakida et al. 2019).
To the best of our knowledge, backward analysis has not been used pre- viously to investigate implicit regularization in gradient based optimizers. However, Runge- Rutge-Kutta methods have been used to understand old (and devise new) gradient- based optimization methods (Betancourt et al., 2018: Scieur et al., 2017; Zhang et al.] 2018: FFança et al. 2020). A stochastic version of the modified equation was used (Li et al., 2017 | Feng et al.) (020) to study stochastic
Runge-Kutta, methods:
gradient descent in the context of stochastic differential equations and diffusion equations with
focus on convergence and adaptive learning, and very recently França al. (2020) used backward
analysis to devise new optimizers to control convergence and stability.
8 DISCUSSION
Following our backward error analysis, we now understand gradient descent algorithm that effectively optimizes modified loss with an implicit regularization term arising through the discrete nature of gradient descent. This leads to several predictions that confirm experimentally: (i) IGR penalizes the second moment of the loss gradients (Prediction 2.I). and consequently, (ii) it penalizes minima in the vicinity of large gradients and encourages flat broad minima in the vicinity of small gradients (Prediction 2.2]; (iii) these broad minima are known to have low test errors, and consistent with this, we find that IGR produces minima with low test error (Prediction 2.3); (iv) the strength of
regularization is proportional to the learning rate and network size (Equation 3 (v) consequently, networks with small learning rates or fewer parameters or both will have less IGR and worse test error, and (vi) solutions with high IGR are more robust to parameter perturbations (Prediction 2.4)
can be difficult to study implicit regularization experimentally because is not always possible to control the impact of various alternative sources of implicit regularization. Our analytic approach to the study of implicit regularization in gradient descent allows us to identify the properties of implicit gradient regularization independent of other sources of implicit regularization. In our experimental work, we take great care to choose models and datasets that were sufficiently simple to allow us to clearly expose implicit gradient regularization, yet, sufficiently expressive to provide insight into larger, less tractable settings. For many state-of-ther art deep neural networks trained on large real-world datasets, IGR is likely to be just one component of a more complex recipe of implicit and explicit regularization. However, given that many of the favourable properties of deep neural networks such low test error capabilities and parameter robustness are consistent with IGR, it is possible that IGR is an important piece of the regularization recipe.
There are many worthwhile directions for further work. In particular, it would be interesting to use backward error analysis to calculate the modified loss and implicit regularization for other widely used optimizers such as momentum, Adam and RMSprop. It would also be interesting to explore the properties of higher order modified loss corrections. Although this is outside the scope of our work here, we have provided formulae for several higher order terms in the appendix. More generally, we hope that our work demonstrates the utility of combining ideas and methods from backward analysis, geometric numerical integration theory and machine learning and we hope that our contribution supports future work in this direction.
ACKNOWLEDGMENTS
We would like to thank Samuel Smith, Soham De, Mihaela Rosca, Yan Wu, Chongli Qin, Mélanie Rey, Yee whye Teh, Sébastien Racaniere, Razvan Pascanu, Daan Wierstra, Ethan Dyer, Aitor Lewkowyez. Guy Gur-Ari, Michael Munn, David Cohen, Alejandro Cabrera and Shakir Mohamed for helpful discussion and feedback. We would like to thank Alex Goldin, Guy Scully, Elspeth White and Patrick Cole for their support. We would also like to thank our families, especially Wendy; Susie, Colm and Fiona for their support, especially during these coronavirus times.

---

Published as a conference paper at ICLR 2021
REFERENCES
Alnur Ali, J. Zico Kolter, and Ryan J. Tibshirani. A continuous-time view of early stopping for least squares regression. In International Conference on Artificial Intelligence and Statistics, volume 89, 2019.
Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. In International Conference on Machine Learning, volume 119, 2020.
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. In Advances in Neural Information Processing Systems, volume 32. 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. International Conference Machine Learning, volume 97, 2019b.
Sanjeev Arora, Simon $ Du, Wei Hu, Zhiyuan Li, Russ Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. In Advances in Neural Information Processing Systems, volume 32. 2019c.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Gracpel. The mechanics of n-player differentiable games. In International Conference on Machine Learning. volume 80, 2018.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bari-variance trade-off. In Proceedings of the National Academy of Sciences, volume 116, 2019.
Michael Betancourt, Michael I. Jordan, and Ashia C. Wilson. On symplectic optimization. arXiv: 03653, 2018.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclau- rin, and Skye Wanderman-Milne, JAX: composable transformations of Python+NumPy programs, 2018. URL httt::ttttttt/aia com/ wwt.o///gooo//aaaooooo
Yuan Cao and Quanquan Gu. Generalization bounds of stochastic gradient descent for wide and deep neural networks. Advances in Neural Information Processing Systems, volume 32. 2019.
Pratik Chaudhari and Stefano Soatto. Stochastic gradient descent performs variational inference, converges to limit cycles for deep networks. In International Conference on Machine Learning. volume 80, 2018.
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. In Advances in Neural Information Processing Systems, volume 33. 2019.
Soham De and Samuel Smith. Batch normalization biases residual blocks towards the identity function in deep networks. In Advances in Neural Information Processing Systems, volume 33. 2020.
Harris Drucker and Yann Cun. Double backpropagation increasing generalization performance. In International Joint Conference on Neural Networks, 1992.
Yuanyuan Feng, Tingran Gao, Lei Li, Jian-guo Liu, and Yulong Lu. Uniform-in-time weak error analysis for stochastic gradient descent algorithms via diffusion approximation. Communications in Mathematical Sciences, 18, 2020.
Guilherme França, Michael Jordan, and René Vidal. On dissipative symplectic integration with applications gradient-based optimization. arXiv:2004.06840) 2020.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane d' l'Ascoli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number parameters in deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2, 2020.
10

---

Published as a conference paper at ICLR 2021
Gauthier Gidel, Francis Bach, and Simon Lacoste- Implicit regularization of discrete gradient dynamics linear neural networks. In Advances in Neural Information Processing Systems, volume 32. 2019.
Xavier Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. Journal of Machine Learning Research, 9, 2010.
Suriya Gunasekar, Blake E Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization matrix factorization. In Advances in Neural Information Processing Systems, volume 30. 2017.
Suriya Gunasekar, Jason Lee, Daniel Soudry, and Nathan Srebro. Characterizing implicit bias in terms of optimization geometry. In International Conference on Machine Learning, volume 80, 2018.
Ernst Hairer and Christian Lubich. The life-span of backward error analysis for numerical integrators. Numerische Mathematik, 76, 1997.
Emst Hairer, Christian Lubich, and Gerhard Wanner. Geometric numerical integration, volume 31. Springer-Veriiee Verlag, Berlin, second edition, 2006. ISBN 3-540-30663-3, 978-3-540-30666-4
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, volume 48, 2016.
Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. Haiku: Sonnet for JAX. http://gihubb.cmm/deemmm////
2020.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1), 1997.
Arthur Jacot, Franck Gabriel, and Clement Hongler. Neural tangent kernel: Convergence and gener- alization in neural networks. In Advances in Neural Information Processing Systems, volume 31. 2018.
Stanislaw Jastrzebski, Maciej Szymczak, Stanislav Fort, Devansh Arpit, Jacek Tabor, Kyunghyun Cho, and Krzysztof Geras. The break-even point optimization trajectories of deep neural networks. In International Conference on Learning Representations, 2021.
Ziwei Ji and Matus Telgarsky. The implicit bias of gradient descent on nonseparable data. In Proceedings of the Thirly-Second Conference Learning Theory, volume 99, 2019.
Ryo Karakida, Shotaro Akaho, and Shun-ichi Amari. Universal statistics of fisher information in deep neural networks: Mean field approach. In Proceedings of Machine Learning Research, volume 89, 2019.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In International Conference on Learning Representations, 2017.
Jaehoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. In Advances in Neural Information Processing Systems, volume 32. 2019.
Aitor Lewkowycz, Yasaman Bahri, Ethan Dyer, Jascha Sohl-Dickstein, and Guy Gur-Ari. The large learning rate phase of deep learning: the catapult mechanism. arXiv:2003.022/8 2020.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. Advances in Neural Information Processing Systems, volume 31. 2018
Qianxiao Li, Cheng Tai, and Weinan E. Stochastic modified equations and adaptive stochastic gradient algorithms. In International Conference on Machine Learning, volume 70, 2017.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. Advances in Neural Information Processing Systems, volume 31. 2018.
11

---

Published as a conference paper at ICLR 2021
Yuanzhi Li, Colin Wei, and Tengyu Ma. Towards explaining the regularization effect of initial large learning rate in training neural networks. In Advances in Neural Information Processing Systems, volume 32. 2019.
Tengyuan Liang and Alexander Rakhlin, Just interpolate: Kernel "ridgeless" regression can generalize. The Annals of Statistics, 48(3), 2018.
Henry Lin and Max Tegmark. Why does deep and cheap learning work so well? Journal of Statistical Physics, 168, 2016.
Chaoyue Liu, Libin Zhu, and Mikhail Belkin. Toward theory of optimization for over wer-parameterizer systems of non- non-linear equations: the lessons of deep learning. arXivv2003.00307, 2020.
Chao Ma, Lei Wu, and Weinan E. The quenching--activatio behavior of the gradient descent dynamics for two-layer neural network models. arXiv:2006. 1 14450, 2020.
Stephan Mandt, Matthew D. Hoffman, and David M. Blei. Stochastic gradient descent approximate bayesian inference. Journal of Machine Learning Research, 18(134), 2017.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, volume 30. 2017.
Ari S. Morcos, David G.T. Barrett, Neil C. Rabinowitz, and Matthew Botvinick. On the importance of single directions for generalization. In International Conference on Learning Representations, 2018.
Mor Shpigel Nacson, Nathan Srebro, and Daniel Soudry. Stochastic gradient descent on separable data: Exact convergence with fixed learning rate. In International Conference on Artificial Intelligence and Statistics, volume 89, 2019.
Vaishnavh Nagarajan and J Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in neural information processing systems, volume 30. 2017.
Vaishnavh Nagarajan and J. Zico Kolter. Generalization in deep networks: The role of distance from initialization. In Advances in Neural Information Processing Systems, volume 31. 2018.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. In Conference on Learning Representations, 2015.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterizee nonlinear learning: Gradient descent takes the shortest path? In International Conference on Machine Learning, volume 97, 2019.
Daniel S. Park, Jascha Sohl-dickstein, Quoc V. Le, and Sam Smith. The effect network width on stochastic gradient descent and generalization: empirical study. In International Conference Machine Learning, 2019.
Tomaso A. Poggio, Andrzej Banburski, and Qianli Liao. Theoretical issues in deep networks: 2019.
Approximation, optimization and generalization. CoRR, abs/1
Chongli Qin, Yan Wu, Jost Tobias Springenberg, Andrew Brock, Jeff Donahue, Timothy P. Lillierap. and Pushmeet Kohli. Training generative adversarial networks by solving ordinary differential equations. In Advances in Neural Information Processing Systems, volume 33. 2020.
Noam Razin and Nadav Cohen. Implicit regularization in deep learning may not be explainable by norms, In Advances in Neural Information Processing Systems, volume 33. 2020.
Daniel A. Roberts. Sgd implicitly regularizes generalization error. In NIPS 2018 Workshop. 2018.
Levent Sagun, Utku Evci, V. Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the hessian of over-parametrized neural networks. 150i:1700004454, 2017.
Damien Scieur, Vincent Roulet, Francis Bach, and Alexandre d' d'Asremmont. Integration methods and optimization algorithms. In Advances in Neural Information Processing Systems, volume 30. 2017.
12

---

Published as a conference paper at ICLR 2021
Leslie N. Smith. Cyclical learning rates for training neural networks. In Winter Conference Applications of Computer Vision, 2017.
Sam Smith and Quoc V. Le. A bayesian perspective on generalization and stochastic gradient descent. In International Conference on Learning Representations, 2018.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent on separable data. Journal of Machine Learning Research, 19(70), 2018.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. Journal of Machine Learning Research, 15(56), 2014.
Arun Suggala, Adarsh Prasad, and Pradeep K Ravikumar. Connecting optimization and regularization paths. In Advances in Neural Information Processing Systems, volume 31. 2018.
Enzo Tartaglione, Skjalg Lepsøy, Attilio Fiandrotti, and Gianluca Francini. Learning sparse neural networks via sensitivity-driven regularization. International Conference on Neural Information Processing Systems, volume 31. 2018.
James H. Wilkinson. Error analysis of floating-poiis point computation. Numerische Mathematik, 2, 1960.
Ashia C Wilson, Rebecca Roelofs, Mitchell Ster,, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, volume 30. 2017.
Blake Woodworth, Suriya Gunasekar, Jason Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Proceedings of Thirty Third Conference on Learning Theory, 2020.
Jingzhao Zhang, Aryan Mokhtari, Suvrit Sra, and Ali Jadbabaic. Direct runge-kutta discretization achieves acceleration. In Advances in Neural Information Processing Systems, volume 31. 2018.
Yaoyu Zhang, Zhiqin Xu, Tao Luo, and Zheng Ma. type of generalization error induced by initialization in deep neural networks. Proceedings of Machine Learning Research, 107, 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Gradient descent optimizes over-
parameterized deep relu networks. Machine Learning, 109, 2019.
13

---

Published as a conference paper at ICLR 2021
A APPENDIX
A.1 BACKWARD ERROR ANALYSIS OF THE EXPLICIT EULER METHOD
In this section, we provide formulae for higher order backward analysis correction terms for the explicit Euler method, including the first order correction which is required to complete the proof of Theorem 3.1
We start by restating the general problem addressed by backward error analysis. To begin, consider a first order differential equation
i = f(0),
(A.1)
with vector field f IR + R The explicit Euler method
,, 8n (f.)
(A.2)
with step size h produces sequence of discrete steps Go. oI..... .n..... approximating the solution (t) of Equation A..1 with initial condition 0g. (In other word, O, approximates ((nh) for n 2 0.) However, at each discrete step the Euler method steps off the continuous solution 0(t) with one-step error (or local error) ||0= - {h)]l of order (h²)). Backward error analysis was introduced in numeric integration to study the long term error (or global error) ||0,, {(nh)]l of the numerical method. More generally, backward error analysis is useful for studying the long term behavior of a discrete numeric method using continuous flows, such its numerical phase portrait near equilibrium points, its asymptotic stable orbits, and conserved quantities among other properties (see Hairer & Lubich (1997): Hairer et al. (2066) for a detailed exposition). It stems from the work of Wilkinson (9600) in numerical linear algebra where the general idea in the study of numeric solution via backward error analysis to understand as an exact solution for the original problem but with modified data. When applied to numerical integration of ODEs this idea translates into finding a modified vector field f with corrections fi's to the original vector field f in powers of the step-size
i(0) - ((0 + (0) + 1² f2(0) +
(A.3)
so that the numeric method steps now exactly follow the (formal) solution of the modified equation: ه f
(A.4)
In other words, if (t) is the solution of the modified equation A.4 and 6, is the th discrete step of the numerical method, now one has:
On (nh)
(A.5)
In general, the sum of the corrections fi's in A.3) diverges, and the modified vector field / is only formal power series. For practical purposes, one needs to truncate the modified vector field. If we truncate the modified vector field up to order n (i.c., we discard the higher corrections fı for I 12 1), the one-step error between the numeric method and the solution of the truncated modified equation is now of order O(h*+1). ). It is also possible to bound the long term error, but in this section we will only formally derive the higher corrections f. for the explicit Euler method. (We refer the reader to Hairer & Lubich (1997), for instance, for precise bounds on the error for the truncated modified equation.)
To derive the corrections fi's for the explicit Euler method, it is enough to consider single step of gradient descent 0 + (0) and identify the corresponding powers of h in
0 h0) Toylor (h))
by expanding the solution ((h) of the modified equation (A.4) starting at @ into its Taylor series at zero:
hm o (1) (0).
0(h) 0
(A.6)
n
For a gradient flow f(0) = - E(())) its Jacobian f(( is symmetric. In this case, it is natural to look for modified vector field whose Jacobian is still symmetric (i.e., the higher order corrections can be expressed as gradients). If we assume this, we have the following expression for the higher derivatives of the modified flow solution:
14

---

Published as a conference paper at ICLR 2021
Lemma A.1. In the notation above and with f whose Jacobian is symmetric, we have
0(0) = [(0)
(A.7)
d |F(O))1?
@(0) = d0 2
(A.8)
dn-2 11 n22
(0))()
(A.9)
dtn
d- d. where d 05 ((0) is shorthand to denote the operator
t=o d0 o
( and 0(t) is the
solution of the modified equation A.4 We will will use this shorthand notation throughout this section.
Proof. By definition (() is the solution of (A.4) with initial condition 0(0) 0, hence 0(0) - f(0).
Differentiating both sides (A.4) with respect to t, we obtain
((t) = ((-))(())))) (((G))())=(P00000000
d
d0 0=0(s)
The last equation is obtained because we assumed (0) is symmetric. Now the higher derivatives are obtained by differentiating both sides of the last equation times with respect to and setting t= 0.
The previous lemma gives formula for the derivatives ((x) (0). However in order compare the powers of h we need to expand these derivatives into power of h. which is what the next lemma does:
Lemma A.2. In the notation above, we have
g(m)
1 (0) n n22
(A.10)
k20
where we define
d=-2 d
Σ (f((),,,(00)
L,,((0) dtn dA
(A.11)
2
i+j=k
with So( being the original vector field [(0), and (,) denoting the inner product of two vectors.
Proof. This follows immediately from
A.9 and by expanding [[((0)] in powers h:
1(
1
(fo(()) hf) + fo(0) + (0) +....
2
2
(,(10),,,00)
Σ h Σ
2
k20 ドナプ=
Putting everything together, we now obtain Taylor series for the solution of the modified equation as formal power series in h:
Lemma A.3. In the notation above, we have
0 (h) = - Σ 11 (f((0) + ft(.........,..--)))
(A.12)
120
where is the original vector field f. Ho and we define recursively
Hi.Jo, (i) = Σ
((-
L.. (0)
(A.13)
n!
n+t-=+1
n22,120 120
15

---

Published as a conference paper at ICLR 2021
Proof. Replacing ((*) by their expression in (A.10
in the Taylor series (A.6).
obtain
ha+k
0(h) = 0 + +10000) + Σ
(m,)(0)
n!!
n2 220
= 0 Σ
1 (fi(() +
Σ
n! (m))
120
n++=++1
122
which finishes the proof.
Now comparing the Taylor series for the modified equation solution in its last form in A.12 with step of the Euler method
+ -
Σ h x + H2(
121
for each order of h, we obtain the following proposition:
Proposition A.4. The corrections ft s for the Euler method modified equation in A.3 are given by the general recursive formula:
f((0)
Σ
Ln (0),
(A.14)
n+ 122,120
where the Lo,k are defined by Equation A.71
Let (A.14) compute the first order correction in the modified equation for the Euler explicit method:
Example A.S. Suppose f = E, then the first order correction is
1
1 d
f1(0) = -20
VE(O))
4 do
which is the only correction use in Theorem 3.1 The remarkable thing is that now the first two terms of (A.3) can be understood as the gradient of a modified function, yielding the following form for the modified equation M.4
-- +0
with E = E+ VE which the main result of Theorem 3.1
A.2 GEOMETRY OF IMPLICIT GRADIENT REGULARIZATION
In this section, we provide all the details for a proof of Proposition 3.3 and for our claim concerning the relationship between the loss surface slope and the implicit gradient regularizer, which we package in Corollary A.6.1 The geometry underlying implicit gradient regularization makes it apparent that gradient descent has a bias toward flat minima (Keskar et al.) 2017 Hochreiter & Schmidhuberi 1997).
To begin with, consider loss over the parameter space E R The loss surface is defined as the graph of the loss:
S (e,, E(O)) 0 R" R
a submanifold m+++ of co-dimension 1, which means that the space of directions orthogonal to S at a given point (0, E())) is spanned by single unit vector, the normal vector N()) to S at (0, (()). There natural parameterization for surfaces given by the graphs of functions, the Monge parameterizztion, where the local chart is the parameter plane: 0 - (0, E())). Using this parameterization it is easy to see that the tangent space to at (0, E()) is spanned by the tangent vectors:
U; (0) (0. 1.
O, Vo, F()))
16

---

Published as a conference paper at ICLR 2021
for i 1...., m and where the is at the tth position. Now that have the tangent vectors, can verify that the following vector is the normal vector, since its inner product with all the tangent vectors is zero and its norm is one:
(O)
Vo, E,,) Vo., 1)
We can compute the cosine of the angle between the normal vector N (0) at (0, [O)) and the vector (0,.... 0, 1) that is perpendicular to the parameter plane by taking the inner product between these two vectors, immediately yielding the following Proposition:
Proposition A.6. Consider a loss E and its loss surface as above, The cosine of the angle between the normal vector (6) to the loss surface at (0, E(0)) and the vector 2 = (O..... .., 1) perpendicular to the parameter plane can be expressed in terms of the implicit gradient regularizer as follows:
(N) VI+ mRRa
(A.15)
Now observe that if (N))), 2) is zero this means that the tangent plane to S at (9, E(O)) is orthogonal to the parameter space, in which case the loss surface slope is maximal and infinite at this point! On the contrary, when (N) 2) is equal to 1, the tangent plane at (0, E()) is parallel to the parameter plane, making S look like plateau in neighborhood of this point.
Let us make precise what we mean by loss surface slope. First notice that the angle between & (which the unit vector normal the parameter plane) and N (0) (which is the vector normal the tangent plane to S) coincides with the angle between this two planes. We denote by ax(O) this angle:
(x = arrccos((())...
(A.16)
Now, we define the loss surface slope at (0, (()) by the usual formula
slope(0) = tan (())
(A.17)
As we expect, when the loss surface slope is zero this means that the tangent plane to the loss surface is parallel to the parameter plane (i.e., a()) 0), while when the slope goes to infinity it means the tangent plane orthogonal the parameter plane (i.e., (0))= = 2/2).
The following corollary makes it clear that implicit gradient regularization in gradient descent orients the parameter search for minima toward flatter regions of the parameter space, or flat minima, which have been found to be more robust and to possess more generalization power (see Keskar et al. (2017) Hochreiter & Schmidhuber (1997)):
Corollary A.6.1. The slope of the loss surface at (0, E(0)) can be expressed in terms of the implicit gradient regularizer as follows:
slope(() / (O)
(A.18)
Proof. From (A.15) and the fact that cos (0) = (O), E), we have that
cos2 (0)) = -1 mR)G
Now basic trigonometry tells us that in general //os2 a = + tan? a, which implies here that tan (x( mR)GG()). (f). Taking the square root of this last expression finishes the proof.
Li
Remark A.7. Corollary A.6.I gives very clear understanding of implicit gradient regularization. Namely, the quantity that is regularized is nothing other than the square of the slope RIo(O) =
(lope2(0) and the modified loss becomes É(O) E(0) + a slope? (0). For explicit gradient regularization, we can now also understand the explicitly regularized loss terms of the slope:
E,(0) E(0) - pollope (0),
This makes it clear that this explicit regularization drives the model toward flat minima (with zero slope).
17

---

Published as a conference paper at ICLR 2021
Remark A.8. There is another connection between IGR and the underlying geometry of the loss surface through the metric tensor. It a well-known fact from Riemannian geometry that the metric tensor 9 for surfaces in the Monge parameterization O + (0, E()) has the following form:
9u = dig + Vo, ,
where 6ij is the Kronecker delta. Now the determinant [g). which defines the local infinitesimal volume element on the loss surface, can also be expressed in terms of the implicit gradient regularizer:
Namely, 1000]==1= || [[ 1+ mlRra(0) Solving this equation above for RIG. oblain a geometric definition for the implicit gradient regularizer:
( = 1 - -1),
(A.19)
which incidentally is zero when the surface looks like an Euclidean space.
We conclude this section by showing that the increase in parameter norm can be bounded by the loss surface slope at each gradient descent step.
Proposition A.9. Let On be the parameter vector after gradient descent updates. Then the increase in parameter norm is controlled by the loss surface slope as follows:
|
|00.1|| < (ssoop((,,)
(A.20)
Proof. The triangle inequality applied to one step of gradient descent ||0.+ 110,, - (O,)) yields ([10==11- Il) S F(0,)l which concludes the proof, since the gradient norm coincides with the loss surface slope.
We now prove proposition that relates the geometry of the minima of F. and i.
Proposition A.10. Let E be a non-negative loss. Then local minima of E are local minima of the modified loss E. Moreover, the two losses have the same interpolating solutions (i.e., locus of zeros).
Proof. Since VE = VE EVE, where D2 is the Hessian of F,, it is clear that critical point of is a critical point of F. Suppose now that 0* is a local minimum of E. This means that there is neighbourhood of lr where E(0) > E(0*). We can add [())2 on the left of this inequality, since it is positive quantity, and we can also add ([ on the right of the inequality, since it is zero. This shows that in neighborhood of 8", also have that E(O) > E(0*). This means that is also a local minimum of E. Finally, let us see that E and E share the same locus of zeros. Let 0 be zero of F. Since F is non-negative and E(() 0 then 0 is global minima, which implies that v E()) 0 also, and hence E(0) 0. Now for positive E, E(0) trivially implies E(0)= = O.
A.3 THE NTK CONNECTION
In the case of the least square loss, the modified equation as well the implicit gradient regularizer take very particular form, involving the Neural Tangent Kernel (NTK) introduced in Jacot et al. (2018).
Proposition A.11. Consider model fo Rd R with parameters 0 mm and with least square loss E(0) = En= [lfo(z.) vill?. The modified loss can then be expressed as
E(θ) E(0) + h Σ {(0))o(rr.))))
(A.21)
where Kg is the Neural Tangent Kernel defined by
(o( == (e,
(A.22)
where cx(0)= fo(x)) yh E Rd is the error vector on data point Iy- In the particular case when the model output is dimenninss,,,,l, we can write the modified loss compactly as follows:
ē((0) =0)² (1 Ko)c((),
(A.23)
18

---

Published as a conference paper at ICLR 2021
Proof. Let begin by computing the gradient
VE(0) Σ Vi]fo(r)) yll
= Σ Vofo(z)) v))
(E)
since (0) = Vafo(a;) is matrix. Using that result, we can compute the implicit gradient regularizer in this case:
RIG(!) (E(00,VEE0
(C((0)((0))
4
c()) ((0))
(0) Ko (o(
which concludes the first part of the proof. Now when the model output is one-dimensional, then the (0) are longer vectors but scalars. We then collect them into single vector c()) (ei (f). cn (0)). Similarly, the terms (T 2y) are no longer matrices but scalars, allowing us to collect them into single matrix Ks. this notation we now see that the original loss can be written E =e" yielding E ex (1 Kø)e for the modified loss, concluding the proof.
For the least square loss, we see that the IGR expressed in terms the NTK. Therefore the NTK entries will tend to be minimized during gradient descent. In particular, the cross terms Ko(r;, 2z) will be pushed to zero. This means that gradient descent will push the maximum error direction (ex( at different data points to be orthogonal to each other (i.c.. (e) Ve(() ~ 0). This is good, since a gradient update is nothing other than a weighted sum of these error directions. If they orthogonal, this means that the gradient update contribution at point Ia will not affect the gradient update contribution at point z₁, so the individual data point corrections are less likely to nullifying each other as gradient descent progresses.
A.4 EXPERIMENT DETAILS FOR THE 2-D LINEAR MODEL
In this section, we provide supplementary results (Figure A.Tp, hyper-parameter values (Table A. and modified loss derivations for the two parameter model described in Section 5 This model has loss given by:
E = (y abx)² /2
(A.24)
where b R are the model parameters and x, R is the training data.
The implicit regularization term for this model can be calculated using Equation yielding:
RIG (V + (V+E)² (a² 12)
(A.25)
2
The implicit regularization rate be calculated using Equation 3 yielding:
X mh/4 /4 h/2.
(A.26)
19

---

Published as a conference paper at ICLR 2021
small kamiing rate
large learning
3
2
-1
Figure A.1: Gradient descent with large learning rates: In this phase space plot, the same loss surface as in Figure i represented, but showing larger area the phase space. We plot two gradient descent trajectories, originating from the learning rate hg = 10 and the other has a much larger learning rate Jい = 1.8 x 10-1 The gradient descent trajectory with larger learning rate ricochets across the loss surface, stepping line attractors until it happens to land in a low gradient region of the loss surface where it converges toward global minima.
initial point (on 2.8, by 3.5). One has small
The modified loss be calculated using Equation 2 yielding:
== E + XRIG = E (1 (a² + x²)
(A.27)
Here, we can see that the global minima for E(a, b) (i.e. the zeros) are the same the global minima for E(a, b) since + À (a² + b2) x² is positive. However, as we will see, the corresponding gradient flows are different.
The exact modified gradient flow for the modificd loss is given by:
à
= V (1 (a +b² x²) X (2ax²) b = -v, = V.E (1+ (a² + b²) x²) A (2bx²) E.
(A.28)
The exact gradient flow for the original loss is given by
à V.F. F
i V,E,
(A.29)
The exact numerical flow of gradient descent is given by
an+1 an hV
b b, hVbE,
(A.30)
Table A.I: Experiment hyper-parameters for the two-parameter model
Initial point I
Initial point II
(ap, bu)
3.5)
74.925)
(x, v)
(1,0.6)
(1,0.6)
hs
10-3
10-6
h.
2.5 10-2
0.5 10-4 n/a
hr.
1.8 x 10-1
p
0.5
4.1 x 10-2
hguter
10
10
20

---

Published as a conference paper at ICLR 2021
0.00180
0.00178
0.00176
Test loss
0.00174
0.00172
0.00170
0.00168
0.00166
0.00164
0,005
0,020
Figure A.2: Test error for 2-d linear model: We evaluate test emror using a test data point given by
(x = 0.5. y = 3/5) for a model trained on a training data point given by (æ = y 3/5). We see that models with larger amounts of EGR have smaller test errors, consistent with Prediction 2.3 This happens because gradient regularisation leads to flatter solutions, where the difference between train and test data incurs smaller cost.
where (an, b,.) are the parameters at iteration step n. For this model, we have V. -brly - abx)) and V -ar(y abx).
Remark A.12. vector notation, we see that the modified gradient flow equation
Ô= - Ar 1 (2x E)0,
with 0 == (a, b). The last term - (2Xx² E)0 is central vector field re-orienting the original vector field VE away from the steepest slopes and toward the origin which coincides in this example with flateer regions where the minimal norm global minima are located. This phenomenon becomes stronger for parameters further away from from the origin, where, coincidentally the slopes are the steepest. Specifically, slope(0) = [/0]..////F.
In Figure D. we plot the trajectories of four different flows starting from the same initial point (ap, bu). to illustrate the impact of IGR. We look at initial points, chosen to illustrate the behaviour of gradient descent in different settings. The full set of syper-parameters used for this experiment is given in Table A. First, calculate the numerical flow of gradient descent with small learning rate kg using Equation A.30 Next, we plot the numerical flow of gradient descent with a moderate learning rate has using Equation A.30 We then calculate the modified gradient flow by solving Equation A.28 numerically using the Euler method, starting from initial point (ao, bo) and using hM 2. For this numerical calculation, we use very small Euler method step size Egteer so that the Éuler method follows the gradient flow of the modified loss accurately. We observe that this modified flow is close to the numerical flow of gradient descent, consistent with Theorem 3.1
We also plot the trajectory of gradient descent for large learning rate h where backward analysis no longer applicable (Fig. A. and observe that gradient descent ricochets across the loss surface, stepping over line attractors until it lands in a low gradient region of the loss surface where it converges toward global minima. This large learning rate regime can be unstable. For larger learning rates, or for different initial positions, observe that gradient descent can diverge in this regime.
In Figure D. we explore the asymptotic behaviour of gradient descent by measuring R/ E after convergence for range of models, all initialized at ag 2.8 and by = 3.5, with range of learning rates.
We also explore the impact of explicit gradient regularization, using Equation 8 to define the explicitly regularized modified loss for our two-parameter model:
Fry F (1
(a² 12) n²²)
(A.31)
21

---

Published as a conference paper at ICLR 2021
(c)
10-1
Leining rate h
Training Loss
10-1
0.1
0.05
10
10-3
0.01
0.005
10
10-4
10
(b)
200000
400000
600000
800000
1000000
(d)
200000
400000
600000
800000
1000000
Regularisation Rig
10-3
2200
2000
10-1
10-
1800
10-11
1600
200000
600000 Training iteration
200000
600000
800000
Training iteration
Figure A.3: Implicit gradient regularization in deep neural network: For an MLP trained to classify MNIST digits, we see that (a) the training loss E' and (b) the regularization value Rie both decrease during training, consistent with backward error analysis (Equation 2) (c) The ratio of AR / E is smaller for networks that have larger learning rates, consistent with the prediction that the learning rate controls the regularization rate (Equation 3 (d) The parameter magnitudes grow during training, and this growth decreases as RiG decreases and finally plateaus before the training loss does, consistent with Proposition A.9
We use this modified loss for gradient descent:
Op++1 an Futer V Ey
bp+1 = b,, - h Futer V E,,
(A.32)
Here, we have used a very small learning rate, hEater (Table A. and a very large value of (Table A.I]. This allows us to achieve stronger regularization, since μ can be increased large value where gradient descent with h = 2μ would diverge. We observe that EGR can decrease the size of RIG after training (Figure Th) and can increase test accuracy (Figure A.2)
A.5 DEEP NEURAL NETWORK EXPERIMENT DETAILS
In this section, we provide further details for the calculation of (0) in a deep neural network (Figure 23 A.3 A.4
A.5 A.6 A.7 A.8). For all these experiments, we use JAX (Bradbury et al., 2018) and Haiku Hennigan et al. 2020) automatically differentiate and train deep neural networks for classification. Conveniently, the loss gradients that compute with automatic differentiation the same loss gradients that we need for the calculation of (0) We calculate the size of implicit gradient regularization RIG(O), during model training, using Equation 4 We observe that (0), the loss E(O) and the ratio RIG/ E(f) all decrease as training progresses, for all learning rates considered (Figure 3.3) We also observe that the parameter magnitudes grow during training, and this growth slows as Ria(()) becomes small, in agreement with Proposition A.9 After a sufficiently large fixed number of training steps, see that models with larger learning rates have much smaller values of (0) relative to E(O), which appears to be consistent with Prediction 2.1 However, the speed of learning clearly depends on the learning rate so it may not be reasonable to compare models after fixed number of training iterations. Instead of stopping after a fixed number of iterations, we could stop training after n. = -T/h iterations, where is the fixed physical time that naturally occurs in our backward analysis (Equation A.5). Again, we find that models with larger learning rates have lower values of Ri) and (())) after a sufficiently large amount of physical training time T (Figure A.5). However, even for fixed physical time comparisons, we still need to choose an arbitrary physical time point T for making comparisons between models. The choice of stopping time is effectively an unavoidable form of implicit regularization. Instead of fixed iteration time or fixed physical time, we use the time of maximum test accuracy as the stopping time for model comparison in Figure and A.6. We choose this option because it is the most
22

---

Published as a conference paper at ICLR 2021
(c)
Learning
10-5
10"
Test Loss
10
0.01
0.005
Test
10-1
10:
50000
100000
150000
200000
250000
(d)
50000
100000
150000
200000
250000
100
Test Accuracy (96)
10'
Rio
10-7
94
Mwy.
50000
100000
150000
290000
250000
0
50000
100000
150000
200000 250000
Training iteration
Training iteration
Figure A.4: Implicit gradient regularization with test data: (a) The test loss and (b) the test regularisation value RiG both decrease initially before increasing again. (c) The ratio of RIG/ E is smaller for networks that have larger learning rates, consistent with Equation 2 (d) The test accuracy increases during training, until it reaches maximum value before starting decrease again slightly. The models used in this figure are the same as those reported in Figure 2, but using test data instead of training data.
10a
Learning
Training LossE
0.1
10-5-
10-2
Mmyl
10
0.025
10-3
10
10
0.005
10:4
10-2
10-4
(b)
5000
10000
15000
20000
(d)
5000
10000
15000
20000
Regularisation Rio
10-#1
2200
10-4
2000
10:40
10:12
1800
10:14
1600
5000
10000
15000
20000
5000
10000
15000
20000
Training time (ixh)
Training time (ixh)
Figure A.5: Implicit gradient regularization for networks trained for equal amounts of physical training time T x h, where is the number of training iterations. Since physical training time depends on learning rate h. models with large learning rates are trained for far fewer iterations, and are exposed far fewer epochs of training data than models with small learning rates. Nonetheless, following sufficiently long period of physical training time, the ratio (f) E(0) is smaller for models with larger learning rates, consistent with Theorem 3.1
23

---

Published as a conference paper at ICLR 2021
0182s
33
0.65
98.6
req requiarizaioo Rd
reqularisation Ro
98.4
98.2
peraraaa
15823
98.0
100220
33
1538813
33
10
10
learning rate
networkk Size
regularisation Ri
50.0
06.0
96.0
333553
58.5
3.00
8.00
18.4
3335820
Tect accuracy
Test 30 waccurrryyy
3.5
18.2
98.0
$6.0
kerring rale
01.
0,05
61A
611
22"
28
10 IP
15
learning rabe
network size
regularisation Ra:
Figure A.6: The relationship between learning rate, network size, RiG and test accuracy, using the same data as in Figure 2 We see that RiG typically decreases as the learning rate increases, or, as the network size increases. We also see that test accuracy typically increases the learning rate increases, or, as the network size increases. Finally, we observe that test error is strongly correlated with the size of RIG after training.
useful time point for most real-world applications. For each model, we calculate E(O), (i) and the test accuracy at the time of maximum test accuracy (which will be a different iteration time for each model) (Figure A.4). The observation that (i) fixed iteration stopping time, (ii) fixed physical stopping time, and (iin) maximum test accuracy stopping time all have smaller values of RıG (0) (0) for larger values of X, consistent with Prediction 2.1 indicates that the relationships between these quantities cannot be trivially explained be consequence of particular choice stopping time regularization. In these examples, we use ny 400 (corresponding to ~ 9.6 10 parameters) with batch size 32.
In Figure 2 and Figure A.6 we report (0) and test accuracy at the time of maximum test accuracy for a selection networks of different size, trained with different learning rates. For models with sufficient capacity to solve the training task and simultancously minimize (r)( we expect (1)( E and test error to decrease as increases (Prediction 2.1 and 2.3j. To expose this behaviour, exclude models that fail to reach 100% MNIST training accuracy, such as models that diverge (in the large learning rate regime), and models with excessively small learning rates, which fail to solve the task, even after long training periods. We observe that test error is strongly correlated with the size of RIG after training (Figure A.6). We also confirm this for a range of batch sizes, including full batch gradient descent (Figure A.6 top right) with n4 400, and for SGD with batch size 32 across a range of learning rates and network sizes (Figure A.6 bottom right).
Finally, explore IGR and EGR for larger model we trained a ResNet-18 classify CIFAR-10 images using Haiku (Hennigan et al.) 2020). We used stochastic gradient descent for the training with batch size of 512 for a range of learning rates E (0.005, 0.01, 0.05, 0.1, 0.2). We observe the same behaviour as in the MNIST experiments: as the learning rate increases, the values of RiG decrease (Prediction 2. the test accuracy increases (Prediction 2.3} and the optimization paths follow shallower slopes leading to broader minima (Prediction 2.2 The experimental results are summarized by the training curves displayed in Figure A.7 and in Figure A.8 where we plot the relation between learning rate, Rig, and test accuracy taken at the time of maximum test accuracy for each training curve.
24

---

Published as a conference paper at ICLR 2021
(a)
(c)
90
Test Accuracy
10
surface
40
0.1
20
(b)
10000
20000
30000
40000
50000
(d)
10000
20000
30000
40000
50000
Regularisation Ris
20"
Learning
10:4
9000
0.1
0.05
10-6
8800
0.01
0.005
(e)
10000
20000
30000
40000
50000
10000
20000
30000
40000
50000
100
Train Accuracy
98-
Train Loss
96
8
94-
90
30000
Training iteration
Training Iteration
Figure A.7: Implicit gradient regularization for Resnet-18 trained on CIFAR-10: (a) The test accuracy increases and (b) the regularization value RiG decreases as the learning rate increases. (c) The optimization paths follow shallower loss surface slopes as the learning rate increases. (d) We also report the L2 norm of the model parameters. (e) and (f) The interpolation regime is reached after few thousand iterations.
(a)
(b) 10:4
10-
75.0
Text Accurasy (98)
70.0
regulerization rizatioonn Rd
67.5
regularization
20-12
10
10-13
10-12
62.5
regular
30-14
10-94
57.
10-14
10"54
55 0
75
Learning
Learning
accuracy
Figure A.8: The relationship between learning rate, RiG. and test accuracy, using the same data as in Figure A.7 for various Resnet-18 models trained CIFAR-IO. We that learning RiG typically decreases and the test accuracy increases as the learning rate increases. Finally, we also observe that accuracy strongly correlated with the size of RIG. All the values are taken the time of maximum test accuracy.
25


Reviews:
[{"review_id": "q7DNuPzWDcG", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Edit after rebuttal\n\nI 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\n\n## Summary of the paper\n\nThis 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. \n\n## Summary of merits and concerns\n\n### Merits\n\n+ 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.\n+ The mathematical derivations provided by the authors may be used by other researchers to better understand the dynamics of gradient descent.\n+ 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\n+ The authors identify a good number of related articles.\n\n### Concerns\n\n- 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.\n- 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).\n- 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.\n- 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.\n\n## Evaluation and justification\n\nWhile 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.\n\n### Overstated role of \"implicit gradient regularisation\"\n\nThe 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.\n\nIn 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.\n\nThe 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:\n\n- \"We find that IGR can account for the observation that learning rate size is correlated with test accuracy and model robustness\" (Section 1)\n- \"EGR produces a boost of more than 12% in test accuracy\" (Section 6)\n- \"networks with small learning rates or fewer parameters or both will have less IGR and worse test error\" (Section 8)\n- \"solutions with high IGR are more robust to parameter perturbations\" (Section 8)\n- \"IGR produces minima with low test error\" (Section 8)\n\nIn 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.\n\n### Concerns about the experimental setup\n\nIn 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.\n\nSimilarly, 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. \n\nAnother 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)?\n\n### Clarity\n\nAlthough 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:\n\n- 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.\n- 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). \n- 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.\n- The legend of some figures is very small and therefore hard to read. See, for instance, Figure 1a.\n\n## Questions and suggestions\n\nBelow 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. \n\n- 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].\n- 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?\n- \"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.\n- 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.\n\n## Minor comments and potential typos identified\n\nThe 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.\n\n- The title may be too broad and slightly ambiguous.\n- 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).\n- The meaning of variable $m$ is not explained in Equations 3 and 4.\n- In Section 3, for better clarity, the authors may like to develop the acronym ODE (ordinary differential equation)\n- In page 4, consider using \"cancel out\" instead of \"kill\"\n- Typo: \"we will _demonstration_ the effectiveness of EGR\"\n- Consider spelling \"CIFAR-10\" with upper case in page 4, as is commonly written, instead of \"Cifar-10\". Also for consistency throughout the paper.\n- \"are more robust to parameter perturbations after training (_Figure 3c_)\" (page 6): I believe it should read \"Figure 3b\".\n- In Section 7, considering mentioning data augmentation as an implicit source of implicit regularisation which is very commonly used in practice.\n- Some relevant papers that the authors may consider discussing are [3, 4]\n- It is not clear if the first paragraph in page 3 corresponds to Prediction 2.4, or it is a new paragraph.\n- Theorem 3.1 refers back to Equation 2, while it would be clearer to explicitly express it there.\n- Typo: \"is a global _minima_\" should probably read _minimum_\n- The first paragraph of page 6 is really long and hard to read.\n\n\n## References\n\n[1] Alnur Ali, Edgar Dobriban, and Ryan Tibshirani. The implicit regularization of stochastic gradient flow for least squares. arXiv:2003.07802, 2020.\n\n[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.\n\n[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.\n\n[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.", "extra_scores": {}, "extra_text": {}}, {"review_id": "pFBw5ieeVmt", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nOverall, 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.\n\nHowever, my major concerns are as follows and hopefully the authors can address my concerns in the rebuttal.\n\nFirst, 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.\n\nSecond, 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.\n\nThird, 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.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "SXQr77z1J7F", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThis 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.\n\nThere'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.\n\nSynthesizing 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.\n\nOne 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?\n\n\nFinally, I have some additional questions and comments:\n\nHow 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. \n\nRelatedly, 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?\n\nTo 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.\n\nWith 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.)\n\n(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.)\n\nDisclosure: I reviewed this paper for NeurIPS. I read the ICLR submission anew and updated my report accordingly.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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)