Understanding Gradient Regularization in Deep Learning: Efficient Finite-Difference Computation and Implicit Bias
Authors: Ryo Karakida
Tomoumi Takase
Tomohiro Hayase
Kazuki Osawa
Venue: Submitted to ICLR 2023 (2023)
Keywords: Gradient regularization
Implicit bias
Gradient ascent and descent
Diagonal Linear Network

Abstract: Gradient regularization (GR) is a method that penalizes the gradient norm of the training loss during training. Although some studies have reported that GR improves generalization performance in deep learning, little attention has been paid to it from the algorithmic perspective, that is, the algorithms of GR that efficiently improve performance. In this study, we first reveal that a specific finite-difference computation, composed of both gradient ascent and descent steps, reduces the computational cost for GR. In addition, this computation empirically achieves better generalization performance. Next, we theoretically analyze a solvable model, a diagonal linear network, and clarify that GR has a desirable implicit bias. Learning with GR chooses better minima in a certain problem, and the finite-difference GR chooses even better ones as the ascent step size becomes larger. Finally, we demonstrate that finite-difference GR is closely related to some other algorithms based on iterative ascent and descent steps for exploring flat minima: sharpness-aware minimization and the flooding method. In particular, we reveal that flooding performs finite-difference GR in an implicit way. Thus, this work broadens our understanding of GR in both practice and theory.

Under review as a conference paper at ICLR 2023
UNDERSTANDING GRADIENT REGULARIZATION IN DEEP LEARNING: EFFICIENT FINITE-DIFFERENE COMPUTATION AND IMPLICIT BIAS
Anonymous authors Paper under double-blind review
ABSTRACT
Gradient regularization (GR) is method that penalizes the gradient norm of the training loss during training. Although some studies have reported that GR improves generalization performance in deep learning, little attention has been paid to it from the algorithmic perspective, that is, the algorithms of GR that efficiently improve performance. In this study, first reveal that a specific finite- differenee computation, composed of both gradient ascent and descent steps, reduces the computational cost for GR. In addition, this computation empirically achieves better generalization performance. Next, we theoretically analyze a solvable model, diagonal linear network, and clarify that GR has a desirable implicit bias in a certain problem. In particular, learning with the finitediifference GR chooses better minima as the ascent step size becomes larger. Finally, we demonstrate that finite-different difference GR is closely related to some other algorithms based on iterative ascent and descent steps for exploring flat minima: sharpness-aware minimization and the flooding method. We reveal that flooding performs finiteddifference GR in an implicit way. Thus, this work broadens our understanding of GR in both practice and theory.
INTRODUCTION
Explicit or implicit regularization key component for achieving better performance in deep learning. For instance, adding some regularization on the local sharpness of the loss surface is one common approach to enable the trained model to achieve better performance (Hochreiter Schmidhuber, 1997; Foret et al., 2021; Jastrzebski et al., 2021). In the related literature, some recent studies have empirically reported that gradient regularization (GR), i.e., adding penalty of the gradient norm to the original loss, makes the training dynamics reach flat minima and leads to better generalization performance (Barrett Dherin, 2021; Smith et al., 2021; Zhao et al., 2022). Using only the information of the first-order gradient seems simple and computationally friendly idea. Because the first-order gradient is used to optimize the original loss, using its norm is seemingly easier to than other sharpness penalties based second-order information such as the Hessian and Fisher information (Hochreiter & Schmidhuber, 1997; Jastrzebski et al., 2021).
Despite its simplicity, First, we need to consider the fact that GR must compute the gradient of the gradient with respect to the parameter. This type of computation has been investigated in slightly different context: input-Jacobian regularization, that is, penalizing the gradient with respect to the input dimension to increase robustness against input noise (Drucker & Le Cun, 1992; Hoffman et al., 2019). Some studies proposed the use of double backpropagation (DB) as an efficient algorithm for computing the gradient of the gradient for input-Jacobian regularization, whereas others proposed the use of finite-diffe inite-difference computation (Peebles et al., 2020; Finlay & Oberman, 2021). Second, theoretical understanding of GR has been limited. Although empirical studies have confirmed that the GR causes the gradient dynamics to eventually converge to better minima with higher performance, the previous work provides no concrete theoretical evaluation for this result. Third, it remains unclear whether the GR has any potential connection to other regularization methods. Because the finite difference is composed both gradient ascent and descent steps by definition, we are reminded of some learning algorithms for exploring flat minima such sharpness-aware minimization (SAM) (Foret al.,
understanding of GR has been limited so far in the following ways.

---

Under review as a conference paper at ICLR 2023
2021) and the flooding method (Ishida et al., 2020), which are also composed of ascent and descent steps. Clarifying these points would help to deepen our understanding on efficient regularization methods for deep learning.
In this work, we reveal that GR works efficiently with a finite-difference computation. This approach has lower computational cost, and surprisingly achieves better generalization performance than the other computation methods. We present three main contributions to deepen our understanding of GR:
We demonstrate some advantages to using the finite-difference computation. We give a brief estimation of the computational costs of finite difference and DB in deep neural network and show that the finite difference is more efficient than DB (Section 3.2). We find that a so-called forward finite difference leads to better generalization than a backward one and DB (Section 3.3). Learning with forward finite-difference GR requires two gradients of the loss function, gradient ascent and descent. A relatively large ascent step improves the generalization.
We give a theoretical analysis of the performance improvement obtained by GR. we amalyze the selection of global minima in a diagonal linear network (DLN), which is a theoretically sol solvable model. We prove that GR has an implicit bias for selecting desirable solutions in the so-called rich regime (Woodworth al., 2020) which would potentially lead to better generalization (Section 4.2). This implicit bias is strengthened when we use forward finite- difference GR with an increasing ascent step size. In contrast, weaken for a backward finite difference, i.c., negative ascent step.
mrnite-difference GR is also closely related to other learning methods composed of both gradient ascent and descent, that is, SAM and the flooding method. In particular, we reveal that the flooding method performs difiteedifference GR in implicit way (Section 5.2).
Thus, this work gives a comprehensive perspective on GR for both practical and theoretical under- standing.
2 RELATED WORK
Barrett & Dherin (2021) and Smith et al. (2021) investigated explicit and implicit GR in deep learning. They found that the discrete-time update of the usual gradient descent implicitly regularizes the gradient norm when its dynamics are mapped to the continual-tine counterpart. This is referred to as implicit GR. They also investigated explicit GR, i.e., adding GR term explicitly to the original loss, and reported that it improved generalization performance even further. Jia & Su (2020) also empirically confirmed that the explicit GR gave the improvement of generalization. Barrett & Dherin (2021) characterized GR as the slope of the loss surface and showed that a low GR (gentle slope) prefers flat regions of the surface. Recently, Zhao et al. (2022) independently proposed a similar but different gradient norm regularization, that is, explicitly adding a non non--quared L2 norm of the gradient to the original loss. They used a forward finite-difference computation, but its superiority to other computation methods remains unconfirmed.
The implementation of GR has not been discussed in much detail in the literature. In general, to compute the gradient of the gradient, there are two well-known computational methods: DB and finite difference. Some previous studies applied DB to the regularization of an information matrix (Jastrzebski et al., 2021) and input-Jacobian regularization, i.e., adding the L2 norm of the derivative with respect to the input dimension (Drucker & Le Cun, 1992: Hoffman et al., 2019). Others have used computation for Hessian regularization (Peebles al., 2020) and input-Jacobian
the Emite-differene regularization (Finlay & Oberman, 2021). Here, we apply the finite-difference computation to GR and present some evidence that the fiiie-differrece computation outperforms DB computation with respect to computational costs and generalization performance.
In Section 4, we give a theoretical amalysis of learning with GR in diagonal linear networks (DLNs) (Woodworth al., 2020). The characteristic property of this solvable model is that we can evaluate the implicit bias of learning algorithms (Nacson et al., 2022; Pesme et al., 2021). Our analysis includes the analysis of SAM in DLN special case (Andriushchenko & Flammarion, 2022). In contrast to previous work, we evaluate another lower-order term, and this enables us to show that forward fnite-difference GR selects global minima in the so-called rich regime.
2

---

Under review as a conference paper at ICLR 2023
3 GRADIENT REGULARIZATION
We consider GR (Barrett & Dherin, 2021; Smith et al., 2021), wherein the squared L.2 norm of the gradient is explicitly added the original loss C(0) follows:
[()) (()) + 2
R(O), R(O) = IV
(1)
where ||
denotes the Euclidean norm and > a constant regularization coefficient. We abbreviate the derivative with respect to the parameters Vo by V. Its gradient descent is given by
0.+1 02 v).)
for time step 0, ..... and learning rate 7 While previous studies have reported that explicitly adding GR term empirically improves generalization performance, its algorithms and implementations have not been discussed in much detail.
3.1 ALGORITHMS
To optimize the loss function with GR (1) using a gradient method, we need compute the gradient of the gradient, i.e., R(0).. As is well studied input-Jacobian regularization (Drucker Le Cun, 1992; Hoffman et al., 2019; Finlay & Oberman, 2021), there two main approaches to computing the gradient of the gradient.
Finite difference: The liffe-difference method approximates derivative by finite step. In the case of GR, we have V R((0)/2 = (VL(0') (E())) + O(s) with 0' = 0g + eV for a constant O. The final term expressed in Landau notation and is neglected in the computation. We update the GR term by
-V2(.)))
ARr(s)
(F-GR).
We refer to this gradient as Forward finite-difference GR (F-GR). Because the gradient VL(00)
computed for the original loss, the finite difference (3) requires only one additional gradient computation VL(0") The order of the computation time is only double that of the usual gradient descent. The finiteddifference method also has backward computation:
ARB(E) (C(),) V (0, - cV)))) (B-GR).
(4)
If we allow a negative step size, A RB corresponds to A R through AR = ARr(-e). For sufficiently small e, both finite-difference GRs yield the same original gradient R if we can neglect any numerical instability caused by the limit. The finiteddifference method has been used in the literature for the optimization of neural networks, especially for Hessian- bastd techniques (Bishop, 2006; Peebles et al., 2020). When we need more precise VR, we can use higher-order approximation, e.g., the centered finite difference, but this requires additional gradient computations, and hence we focus on the first-order finite difference.
Double Backpropagation: The other approach is to apply the automatic differentiation directly to the GR term, i.e., V R. For example, its PyTorc implementation is quite straightforward, as shown in Section C.I of the Appendices. This approach is referred to as DB, which was originally developed for input-Jacobian regularization (Drucker Le Cun. 1992). We explain more details on the DB computation and its computational graph in Section 3.2. DB, in effect, corresponds to computing the following Hessian-vector vector product:
ARDB = ((,))
(5)
where H())- VVL(O). The following equation may give us an intuition about the difference between the finite difference and DB alternatives. From the mean value theorem, F-GR is equivalent
J ds dsH(O, (((0+&VVL()))V)) (VL(O.)
ARr (8)
We can interpret the finite difference as taking an average of the curvature (Hessian) along the line of gradient update. For
0, this reduces A ARpB-
3

---

Under review as a conference paper at ICLR 2023
(a)
MLP
ReaNet
(b)
200
bB F-GR
60
Wall (slepoch)
We time (sHopoch)
190
0.8
Text Acc.
0.6
20
DB
-RR
0
100
200
300
400
500
100
120
140
3 Wall time [s]
8 xx10'
Dopth
ResNot L
Figure 1: Finite-difference computation more efficient than DB computation in wall time. (a) Wall time required for learning with GR in one epoch. For the ResNet, we used ResNet- {18, 34, 50, 101, 152]. (b)Training dynamics in ResNet-18 on CIFAR-10. Learning with F-GR is much faster in wall time.
Note that the difference among these algorithms appears in non-linear models. For naive linear model X0, the squared error loss has a constant Hessian XX".. Therefore, all A have the same update. We analyze simple network model with non-linearity on the parameters in Section 4 and reveal the difference of implicit biases.
3.2 COMPUTATIONAL COST
We clarify the computational efficiencies of each algorithm of GR deep networks. First, we give rough estimation of the computational cost by counting the number of matrix multiplication required to compute V V.. Consider an L-layer fully connected neural network with a linear output layer: A (U;),, , Ui WiAr11 for = .... L. Note that A, denotes a batch of activation and WiA(11 requires matrix multiplication. We denote the element-wise activation function as 6(-) and weight matrix as W₁. For simplicity, we neglect the bias terms. The number of matrix multiplications required to compute V is given by
Nmu! ~ 6L (for F-GR), 9L (for DB),
where ~ hides an uninteresting constant shift independent of the depth. One can evaluate Nmut straightforwardly from the computational graph (Figure 2), originally developed for the DB computa- tion of input-Jacobian regularization (Drucker & Le Cun, 1992). In brief, the original gradient C, that is, the backpropagation
the forward pass { {A A plications: T. for the forward pass, I. for backward pass B₁ = o' ( (+1 Bi+1), and T. for gradient G 0C/0W, BrAT_, Because F-GR is composed of both gradient ascent and descent steps, we eventually need 6L. In contrast, for learning using the DB of GR, we need 3L for VL and additional 6L for the GR term. The GR term requires forward pass of composed of A,, B,, and G; obtained in the gradient computation of V.. Note that the upper part {Ao + A + ... + BL - ... - B1} is well known the DB of input-Jacobian regularization. As pointed out in Drucker & Le Cun (1992), the computation of V Bj is equivalent to treating the upper part of the graph as the forward pass and applying backpropagation. It requires 2L multiplications. In our GR case, we have additional L multiplications due to G₁. Because the backward pass doubles the number of required multiplications, we eventually need (2L + L) 6L multiplication. Further details are given in Section C.I.
requires 37. matrix multi-
The results of numerical experiments shown in Figure 1 confirm the superiority of finite-difference GR in typical experimental settings. We trained deep neural networks using NVIDIA A A100 GPU for this experiment. All experiments were implemented by PyTorch. We summarize the pseudo code and implementation of GR and present the detailed settings of all experiments in Section C. Figure ((a) shows the wall time required for one epoch of training with stochastic gradient descent (SGD) and the objective function (1). We trained various multi-layer perceptrons (MLPs) and residual neural networks (ResNets) with different depths. The wall time increased almost linearly the depth increased. The slope of the line is different for F-GR and DB, and F-GR was faster. This observation is consistent with the number of multiplications (7). In particular, in ResNet, GR was more than twice as fast as learning with
of the most typical
deep neural networks, learning with DB. Figure (bb) confirms that F-GR has fast convergence in ResNet- 18 on CIFAR-10 10. In Figure S.1
4

---

Under review as a conference paper at ICLR 2023
Forward Pass for (())
Backward Pass
Ap + A1 + + 111 As
[(0)
B₁ -
B ... - B1
for
Gr. GC-1
G
Figure 2: Computational graph of DB. Each node with an incoming solid arrow requires one matrix multiplication for the forward pass.
we also show the convergence measured by the training loss and time steps. All of them showed better convergence for the finite difference.
Note that the finite difference is also better to use from the perspective of memory efficiency. This because DB requires all of the {A, Br: Gi} be retained for the forward pass, which occupies more memory. It is also noteworthy that in general, it is difficult for theory completely predict the realistic computational time required because could heavily depend on the hardware and the implementation framework and does not necessarily correlate well with the number of floating-pone ppintt operations (FLOPs) (Dehghani et al., 2021). Our result suggests that at least the number of matrix multiplication explains well the superiority of the finite-difference approach in typical settings.
3.3 GENERALIZATION PERFORMANCE
Here, show that the superiority of finite-difference computation over DB also appears in the eventual performance trained models. Figures and S.2 show the test accuracy of 4-layer MLP and ResNet-18 trained by using SGD with GR CIFAR-10 We trained the models in exhaustive manner with various values for y and & for each algorithm of the GR. For learning with F-GR, the model achieved the highest accuracy In contrast, learning with B-GR showed a rapid decrease of the performance as the step size increased. The highest average test accuracy of F-GR better than those of B-GR and DB although our purpose is to confirm the difference among the algorithms and not to achieve higher accuracy by tuning both y and E. It was (F-GR, B-GR, DB) (58.6, 58.3, 57.6) + (0.2, 0.2, 0.2) for MLP and (87.0, 86.2, 86.3) + (0.2, 0.3, 0.3) for ResNet-18 18. We also confirmed that the same tendencies appeared in the grid search of ResNet-34 on CIFAR- 100 (Figure S.3 Moreover, we confirmed that F-GR performed better than B-GR and DB in a more realistic training of wide residual network (WRN-28-10) on CIFAR-10 and CIFAR-10K with/without data augmentation (Table S.1)
relatively large ascent steps (s 0.1).
It is noteworthy that the best accuracy of F-GR was obtained close the line of closely related to SAM algorithm. We explain more details Section 5. We also observed that when the ascent step too small (c.g.. < 10-4), numerical instability sometime appeared in the calculation the finite difference AR. Overall, the experiments suggest that F-GR with large ascent step is better for achieving higher generalization performance.
This line is
(a) MLP
(b) ResNet-18
F-GR
B-GR
DB
F-GR
B-GR
857
0.0
107
10
653
19
16
10
16
19"1
161
10"
19"
10?
Figure 3: Grid search on learning with different GR algorithms shows the superiority of F-GR and that relatively large achieves high test accuracy. The color bar shows the average test accuracy over 5 trials, Gray dashed lines indicate e.
5

---

Under review as a conference paper at ICLR 2023
4 THEORETICAL ANALYSIS OF IMPLICIT BIAS
Although previous work and our experiments Section 3.3 indicate improvements of prediction performance caused by GR, theoretical understanding of this phenomenon remains limited. Because the gradient norm itself eventually becomes zero after the model achieves a zero training loss, seems challenging to distinguish the generalization capacity by simply observing the value of the gradient norm after training. In addition, our experiments clarified that the performance also depends on the choice of the algorithm and revealed that the situation is complicated. To attack this problem. we consider a solvable model and reveal that GR methods actually contribute to the selection of global minima and the eventual performance.
4.1 DIAGONAL LINEAR NETWORK
A DLN is a solvable model proposed by Woodworth et al. (2020). is a linear transformation of input J E Rdd defined as (,. æ) where 3 parameterized by 3 w w with w = (w4, w-) E 2d2d
Here, the square of the vector is an clement-wii wise square operation. Suppose we have n training samples (z,,3) yc) (i = I,.... 12). The training loss is given by
1 4n Σ (( w², vi) Wi)
((w)
(8)
Consider continual-time training dynamics dw - V L. We set an initialization w+ = 00) wt-tt = 0) which is d-dimensional vector and whose entries are non-zero. We define data matrix X whose i-th row is given by zz. Woodworth al. (2020) found that interpolation solutions of usual gradient descent are given by
Boc (a)=
arg min (B)
BERO X8=
with a = ag. The potential function da is given by (B = Σi a.9 (B:/a,) with ((2)
2 / 4 22 + z arcsinh((:/2), For larger scale of initialization a, this potential function becomes closer to L2 regularization as (3; //./aa ))))= ~ 12, which corresponds to the L2 min-norm solution of the lazy regime (Chizat al., 2019). In contrast, for a smaller scale of initialization a, becomes closer to L1 regularization as a (3.(3/)3) ~ |3,]. In this way, we can observe one-parameter interpolation between Ll and 1.2 implicit biases. Deep neural networks in practice acquire rich features depending on data structure and are believed to be beyond the lazy regime. Thus, obtaining an LI solution by setting small a is referred to as the rich regime and desirable. Previous work has revealed that effective values of a decreases by larger learning rate in the discrete update (Nacson et al., 2022), SGD (Pesme et al., 2021), and SAM update (Andriushchenko & Flammarion, 2022). These learning methods have an implicit bias that chooses the L1 sparse solution in the rich regime.
4.2 IMPLICIT BIAS OF GR
Now, consider gradient descent with F-GR dw/dt = VVC(w) ()) We find that the GR has implicit bias for the rich regime, and moreover, the strength the bias depends on the ascent step size.
Theorem 4.1. Assume that (i) the gradient dynamics converges to the interpolation solution satisfying X3 y. (ii) L2 norm of the parameter [[w(t)]] has a constant upper bound independent of 7 and for sufficiently small y and the integral of the training loss, i.e., J L(w(t)) dt, has a constant upper (lower, respectively) bound R (R) independent of y and Then, for sufficiently small y and interpolation solutions are given by Boc (ap-an) with
OF S On o exp(pxpst +0(2)++
(10)
The exponent E RRd is non-negative constant vector given by
2n (x (x
y))²
(11)
Note that the inequality is element-wise. The proof given in Section A.I. Technically speaking, learning with F-GR requires to evaluate novel e* term, which has not appeared in the analyses of

---

Under review as a conference paper at ICLR 2023
(a)
35
(b) 10
10
Text Lows
100
10
10"
0.01
0,02
0.03
0.04
0.06
0.01
0.02
0.03
0.04
0.05
Figure 4: Results of training of DLNs using gradient descent with F-GR ( = 0.02). (a) norm of the solutions, (b) test loss, and (c) the largest eigenvalue of the Hessian of the training loss.
previous studies. Lemma A. clarifies that we can prove the positivity of the seemingly complicated term of c* through an integral of the learning dynamics. The assumptions seem rational in the following sense. First, assumption (i) is common in the previous studies DLNs. Second, Nacson et al. (2022) recently reported that we can obtain interpolation solutions with a smaller parameter norm [t) using the discrete update with a larger learning rate. Because the interpolation solutions of gradient descent are also those of our learning with GR, assumption (ii) seems rational. The upper bound of assumption (iii) means that the convergence speed of [(w(t)) does not get too small for sufficiently small y and e. As side note, we can replace assumption (iii) with the positive definiteness of certain matrix (assumption A.2). This is seemingly rather technical, but related to a sufficient condition that the dynamics converge to the global minima. See Section A.2 for details.
This theorem reveals that GR has an implicit bias to select the LI solution, that is, the rich regime because is always smaller than As the ascent step increases, we have an exponentially smaller upper bound and the implicit bias L1 solution will become stronger. We confirm this dependence of solutions on the ascent step in numerical experiments (Figure 4). As in previous work, we trained DLNs on the synthetic data of sparse regression problem, where Is N(ul, o²1) and y/ ~ N ((3", .x;) 0..01,, and where 3 is k -s-arss with non-zero entries equal to 1/Vk* (d = 100 and n 50). Following Nacson al. (2022), we chose μ x² 5, where the parameter norm a(t) is suppressed and assumption (ii) ix expected to hold. As the ascent step increases, models trained by F-GR obtain sparser solutions (Figure 4(a)) and better generalization performance (Figure 4(b)). The dashed lines show the results of gradient descent without GR. This result is consistent with our experiments of in more realistic settings (Figure 3) where relatively large achieves the best performance. In Figure 4(c), we also present the largest eigenvalue of the Hessian (S.50) ), computed after training. As the ascent step size inereases, F-GR chooses flatter minima. This is also consistent with empirical observations in previous studies on GR. Note that B-GR can potentially make the bound looser as the step size increases since B-GR equivalent to F-GR with -E. Actually, we can immediately find a lower bound QBBRR 2 C' exp(7ec") for positive constant vector C, as remarked in Section 1. The results of numerical experiments on DLNs shown Figure S.3 confirm that learning with F-GR achieved better generalization performance than B-GR.
While Theorem 4.1 gives us insight into the finite- diffeeeifference GR, the upper bound converges to ao for the DB limit (s + 0+) and becomes meaningless. Fortunately, we can construct an upper bound applicable to the DB limit.
Proposition 4.2. Under the same assumptions as in Theorem 4.1, for sufficiently small e and
OF--G S ag o exp((-cc+ +
(12)
where the exponent c Rd is a non-negative variable given by c c= =--=== n 22 (x (XT (X3(s) - 2s.
Its derivation is given in Section A.3. One can regard this proposition as a minor extension of Theorem in Andriushchenko & Flammarion (2022), which has investigated 7 = E. This setting has a special meaning as we mention in Section 5. From the proposition, one can see that the DB limit still has the implicit bias to select the rich regime. This consistent with the numerical experiments in Figure 4 where the limit of small achieves slightly better and sparser solutions than GD without GR. Although the bound (12) is informative, it difficult evaluate concrete value of As a side note, we can make a bound of the average over entries, that is, Σ c/d 2 (4n/d) /min (XX RR See Section A.3 for details.
7

---

Under review as a conference paper at ICLR 2023
5 GR IN GRADIENT-ASCENT-ND-DEEES LEARNING
We have revealed that learning with finiteddifference GR, F-GR in particular, improves performance. We recall that the GR is composed of both gradient ascent and descent steps. This computation makes the GR essentially related to two other learning methods similarly composed of both gradient ascent and descent steps: the SAM algorithm and the flooding method.
5.1 CONNECTION WITH SAM
The SAM algorithm was derived from the minimization of a surrogate loss mäX]|e||s C(O + s) for a fixed > O, and has achieved the highest performance in various models (Foret et al., 202 1). After some heuristic approximations, its update rule reduces to iterative gradient ascent and descent steps: p = 8, - r) (66') with 0' = 8, + E, (((b) and E, = p/ (())] Under a specific condition, the SAM update can be seen as gradient descent with F-GR. Let consider time-dependent regularization coefficient Yt and ascent step εt. Then, for T = ét, the gradient descent with F-GR becomes equivalent to the SAM update:
VL(0) + -VC())-V((0) = V
(13)
similar equivalence has been pointed out in Zhao al. (2022) which supposes non-squared gradient norm and é, p/ naturally appears. Let us focus on the SAM update without the gradient normalization for simplicity, that is, E, = p. This simplified SAM update was analyzed on DLNs in Andriushchenko & Flammarion (2022). We can recover the SAM case by setting sufficiently small 7 = e Proposition 4.2. Although will be curious to identify any optimal setting of (7: e), our analysis is limited to the range of the first-order Taylor expansion and characterizing any optimal setting seems beyond the scope of our analysis. In Figure 3, we empirically observed the optimal setting for generalization was very close to just on the line 7 E. In contrast, our Figures 4, S.3 and the previous study Zhao et al. (2022) demonstrated that the optimal setting was not necessarily on E, and thus combining the ascent and descent steps would be still promising.
5.2 FLOODING PERFORMS GR IN AN IMPLICIT WAY
The flooding method (Ishida et al., 2020) is another learning algorithm composed of both gradient ascent and descent steps. Its update rule is given by
O++1 0.
(14)
for a constant > 0, referred to as the flood level. When the training loss becomes lower than the flood level, the sign of the gradient is flipped and the parameter is updated by gradient ascent. Therefore, the flooding causes the training dynamics to continue to wander around L()) ~ b, and its gradient continues to take a non-zero value. This would seem a kind of early stopping, but previous work empirically demonstrates that flooding performs better than naive early stopping and finds flat minima. For simplicity, let us focus on the gradient descent for a full batch. The following theorem clarifies a hidden mechanism of flooding.
Theorem 5.1. Consider the time step satisfying L(0+) < b and [(0++1) > b. Then, the flooding update from Og O,42 is equivalent the gradient of the F-GR with = 7 nf
Oc42 = 0, n?² V + vV VC(0,)
(15)
1)
Similarly, for L(0:) > b and L(0++1) < b, the flooding update is equivalent to the gradient of the B-GR.
Although its derivation is quite straightforward (see Section B), this essential connection between finite-difference GR and flooding has been missed in the literature. Ishida et al. (2020) conjectured that flooding causes a random walk the loss surface and this would contribute to the search for flat minima in some ways. Our result implies that the dynamics of flooding are not necessarily random and it can actively search the loss surface in dircction that decreases the GR. This is consistent with the observations that the usual gradient descent with GR finds flat minima (Barrett & Dherin, 2021; Zhao et al., 2022). Note that the ascent step is given by the learning rate 1), and 17 is usually decayed
8

---

Under review as a conference paper at ICLR 2023
(a)
Troking 4x100
(b)
0.9
Teat Acc.
Goal Narn Rio)
Trinin Lore
Grad Norm
0.85
0.-
Text
0.3
0.75
10
10
10
Epoch
Learning
Figure 5:
Flooding decreases the gradient norm, as expected by theory. (a) Training dynamies of flooding with b = 0.05. (b) Test accuracy and gradient norm after the training.
in the training. This implies that because the ascent step size is relatively small, the implicit B-GR in the flooding update would not make the generalization performance much worse.
Figure 5 empirically confirms that the flooding method decreases the gradient norm R(0). We trained ResNet-18 on CIFAR-IO by using flooding. Figure 5(a) shows that at the beginning of the training. the training loss decreases in the usual way because the loss is far above flood level b. Around the 10th epoch, the loss value becomes sufficiently close to the flood level for the decrease in the loss to slow (Figure S.5 Then, the flooding update becomes dominant in the dynamics the gradient norm begins to decrease. Figure 5(b) demonstrates that the gradient norm of the trained model decreases as the initial learning rate increases. This is consistent with Theorem 5.1 because the theorem claims that the larger learning rate induces the larger regularization coefficient of the GR = vj. In contrast, naive SGD training without flooding always reaches an almost zero gradient norm regardless of the learning rate. Thus, the change in the gradient norm depending on the learning rate is specific to flooding and implies that it implicitly performs GR.
DISCUSSION
This work presented novel practical and theoretical insights into GR. The finite-difference computation is effective in the sense of both reducing computational cost and improving performance. Theoretical analysis supports the empirical observation that the forward difference computation has an implicit bias that chooses potentially better minima depending on the size of the ascent step. Because deep learning requires large-scale models, it would be reasonable to use learning methods only composed of first-order descent or ascent gradients. The current work suggests that the F-GR is promising direction for further investigation and could be extended for our understanding and practical usage of gradient-based regularization.
We suggest several potentially interesting research directions. From a broader perspective, we may regard diffeerddffeeee GR, SAM, and flooding single learning framework composed of iterative gradient ascent and descent steps. would be interesting to investigate if there is optimal combination of these steps for further improving performance. As our experiments suggest, only using the gradient descent or ascent does not necessarily achieve the best performance, and a combination of them seems be the best approach. Similar results were empirically observed in other gradient-based regularization techniques (Zhao et al., 2022; Zhuang et al., 2022). Related to the combination between the gradient descent and ascent, although we fixed the ascent step size as a constant, a step size decay or any scheduling could enhance the performance further. For instance, Zhuang et al. (2022) used a time-step dependent ascent step to achieve high prediction performance for SAM.
It will also be interesting to explore any theoretical clarification beyond the scope of DLNs. Although a series of analyses in DINS enable us to explore the implicit bias for selecting global minima, assumes global convergence and avoids an explicit evaluation of convergence dynamics. Thus, it would be informative to explore the convergence rate or escape from local minima in other solvable models or more general formulation if possible. Constructing generalization bounds would also be an interesting direction. Some theoretical work has proved that regularizing first-order derivatives of the network output control the generalization capacity (Ma & Ying, 2021). and such derivatives are included in the gradient norm as a part. We expect that the current work will serve as a foundation for further developing and understanding regularization methods in deep learning.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Maksym Andriushchenko and Nicolas Flammarion. Towards understanding sharpness- aware min- imization. International Conference on Machine Learning (ICML), pp. 639 668. PMLR, 2022.
David GT Barrett and Benoit Dherin. Implicit gradient regularization. International Conference Learning Representations (ICLR), 2021.
Christopher M Bishop. Puttern recognition and machine learning. Springer, 2006.
Lenaic Chizat, Edouard Oyallon, and Francis Bach. On lazy training in differentiable programming. Advances in Neural Information Processing Systems (NeurIPS), 32, 2019.
Mostafa Dehghani, Yi Tay, Anurag Amab, Lucas Beyer, and Ashish Vaswani. The efficiency misnomer. In International Conference on Learning Representations (ICLR), 2021.
Harris Drucker and Yann Le Cun. Improving generalization performance using double backpropaga- tion. IEEE Transactions Neural Networks, 3(6)9991-977, 1992.
Chris Finlay and Adam M. Oberman. Scaleable input gradient regularization for adversarial robust- ness. Machine Learning with Applications, 3:100017, 2021.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnamy Neyshabur. Sharpness-aware minimization for efficiently improving generalization. In International Conference on Learning Representations (ICLR), 2021.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1): 42, 1997.
Judy Hoffman, Daniel A Roberts, and Sho Yaida. Robust learning with Jacobian regularization. arXiv: 1008:190.000 02729, 2019.
Takashi Ishida, Ikko Yamane, Tomoya Sakai, Gang Niu, and Masashi Sugiyama. Do need zero training loss after achieving zero training error? In International Conference on Machine Learning (ICML), pp. 4604-4611 PMLR, 2020.
Stanislaw Jastrzebski, Devansh Arpit, Oliver Astrand, Giancarlo B Kerg, Huan Wang, Caiming Xiong, Richard Socher, Kyunghyun Cho, and Krzysztof J Geras. Catastrophic Fisher explosion: Early phase Fisher matrix impacts generalization. In International Conference on Machine Learning (ICML), pp. 4772-4784. PMLR, 2021.
Zhiwei Jia and Hao Su. Information theoretic local minima characterization and regularization. In International Conference on Machine Learning (ICML), pp. 4773-4783. PMLR, 2020.
Chao Ma and Lexing Ying. On linear stability of SGD and input-smoothness of neural networks. Advances in Neural Information Processing Systems (NeurIPS), 34, 2021.
Mor Shpigel Nacson, Kavya Ravichandran, Nathan Srebro, and Daniel Soudry. Implicit bias of the step size in linear diagonal neural networks. In International Conference on Machine Learning (ICML), pp. 16270-16295. PMLR, 2022.
William Peebles, John Peebles, Jun-Yar Zhu, Alexei Efros, and Antonio Torralba. The Hessian penalty: weak prior for unsupervised disentanglement. In European Conference on Computer Vision (ECCV), pp. 581-597. Springer, 2020.
Scott Pesme, Loucas Pillaud- Pillaud-Vivien. and Nicolas Flammarion. Implicit bias of SGD for diagonal linear networks: provable benefit of stochasticity. Advances in Neural Information Processing Systems (NeurIPS), 34:29218- 292200, 2021.
Samuel Smith, Benoit Dherin, David GT Barrett, and Soham De. On the origin of implicit regular- ization in stochastic gradient descent. In International Conference on Learning Representations (ICLR), 2021.
10

---

Under review as a conference paper at ICLR 2023
Blake Woodworth, Suriya Gunasekar, Jason D Lee, Edward Moroshko, Pedro Savarese, Itay Golan, Daniel Soudry, and Nathan Srebro. Kernel and rich regimes in overparametrized models. In Conference Learning Theory (COLT), pp- 3635-3673, PMLR, 2020.
Yang Zhao, Hao Zhang, and Xiuyuan Hu. Penalizing gradient norm for efficiently improving generalization in deep learning. In International Conference on Machine Learning (ICML), volume 162, pp. 26982-26992 PMLR, 2022.
Juntang Zhuang, Boqing Gong, Liangzhe Yuan, Yin Cui, Hartwig Adam, Nicha C Dvorne, sekhar tatikonda, James Duncan, and Ting Liu. Surrogate gap minimization improves sharpness-aware training. In International Conference on Learning Representations (ICLR), 2022.

---

Under review as a conference paper at ICLR 2023
Appendices
A ANALYSIS BY DIAGONAL LINEAR NETWORKS
A.1 PROOF OF THEOREM 4.1
A.1.1 INTERPOLATION SOLUTIONS BETWEEN LI AND L2 REGULARIZATION
We consider the training dynamics with F-GR
vi = - VV((w)) - VL(W; VVL(w,)) - V((w:)
(S.1)
= 91 VL(w)) 02 VL + +V)((w)),
(S.2)
where Qı (1 r/E), 92 7/E. The training loss L(w) is defined in (8). The dynamics
rewritten as
dw((l) ạ (XT r(t)) (()) (X (t)) o (t):
(S.3)
dt
n
where denotes the element-wise product between vectors. We defined r(t) Xw(()²= - y. (t) Xw (t) y, w (t) = VV[[+++ and put X = [ X -X E
Rx We recall that the square of the vector is an element-wise square operation. The general solution of (S.3 is written
ao [a
XT S' ( + (2r"))))r)s)))) (s))ds)
w(t) =
o
exp
o exp
92E n²
(X (X r (s)) o (X ((())dss))
(S.4)
This recovers the GD solution obtained by Woodworth et al. (2020) for (91, (2) = (1, 0). and SAM solution by Andriushchenko & Flammarion (2022) for (41, 92) (0. 1). To evaluate the effect of both and on the implicit bias, we need a lower-order evaluation compared to previous work.
Suppose interpolation solution 3xo satisfying X XB y. We represent it by
Bs = w+ (+0)) - w- (oc)2
(S.5)
= 20 sinh (X v).
(S.6)
where - f0 (gir(s) + "22" (s))ds and
OF-GR ag exp (-
[0 (x (x)) (xT (()ss)s ds.
V
V
(S.7)
n2
Put Brx = Bog.OR (XTv) v) with
20 oR o sinh(=). Because the form of the function
8 Ba (XTv) v) is the same in the analysis of usual gradient descent (Woodworth et al., 2020), we can use their transformation Bo as is. We have KKT condition (da XT v and the function da satisfies
Voa(3) = (T) aresinh
2a o 03)
(S.8)
We have
(x) = arg min (3)
(S.9)
BER st. X8=
with
(3) Σ of4 (3./o?)
(S.10)
and
((z) = - / 4+ x2 + arcsinh(z/22.
(S.11)
In our GR case, is just replaced by OF.GR-
12

---

Under review as a conference paper at ICLR 2023
A.1.2 EVALUATION ON OF-GR
From the definitions of rt) and (t), have
28 ((XT((()) o w(())) + 8² xxx (((((T((1)) w(t)))
(t) - r(t)=
(S.12)
n?
n
Then.
1/ =
00
(X (XTr(s))
r(s)))
E / 2(x X((x r())) o w()))) (X r()))
=:2(s)
82
n2 Jo
(X xTX(((X x()))((s)) w()) o (X (x)s ds.)
(S.13)
Let us put
E²
v vo + V
22
(S.14)
n²
1 2ss)ds, Vo = f (xTrss))
2/2 = 1.
2h (s)
(S.15)
Note that the first term Vy essentially corresponds the implicit bias of the SAM update investigated in the previous study (Andriushchenko & Flammarion, 2022). Because the SAM update corresponds y = E, the dominant term of V Vo and they neglect the other terms. In our GR case, Y and have different scales in general and we need to evaluate the coefficient of the ascent step, that is, 1
Lemma A.1. Under assumptions (i)-(iti), for sufficiently small y, 1 > nb(0) O()). If further assume b, (0) * for all 1 > nb(0)²/ /4.
Proof of Lemma I. I. The dynamics (S.3 are rewritten
dw n dt
= -bo w 7 (2 w²)) o ow + 82 w]
78 n² 1(2(6) w²)) + +2 o w o
1(2(6) w²)) o o (S.16)
n
where we put i = RT, r and 7 = XT X. This gives us
d3
7 12 a)) oa b² o
boo
2 dt
n
.Q(())
78 (7(12 o 3)) oa + 2(2 o a)) o BB
752 [7(22 o B)) o 0 Bob,
(S.17)
n
n
QQ(11)
=:Qs(0)
where put w + 22, b T and 7 XTX. Note that db/dl X (dr/dl)
X (d3/dtt) By multiplying X T X (S.17) and taking the Hadamard product with we have
n db²
8 Q2(() 47 bo bo x(Q
di = 4b (X (
n mh Qa(tM)
(S.18)
=:Q(t)
The point is that we have 2bo (XT (bboa)) z(t). This relation makes us to evaluate the seemingly complicated term v by the change of b(t)2. which corresponds to training loss. By taking the integral over time, the above dynamics become
V = / 2(s)ds
" (0))) -2 l Q(s)ds. 2
(S.19)
n
We used assumption (i) that have global minimum and b(20) 0. If y is sufficiently small and Jo Q(s)ds is finite, will have non-negative V,.
13

---

Under review as a conference paper at ICLR 2023
Here, we use assumption (ii) that the parameter norm has finite constant upper bound independent
of y and e. Because ||a(t)] = I| + (t) I ||l? we have an upper bound of |a (t) as well:
||a(t)]| S a.
(S.20)
Define K1 == arg max; |xx]]l K2 == arg max, |0 || and K3 == ||XXX T 122 Then, we find
(Q), - 20. |||||| all b2 |.1
(S.21)
S 2m / (()]] (1)
(S.22)
where we used |b o all - |||||||||| - / K3d |||
and ||||| - ||||| S a. Similarly, we have
[Q2,((1) _ d² / + 2a /
(S.23)
where we used |bº]] (X,r))) S (X,r) |6| We also have
(t) & K2
(S.24)
Note that under assumption (ii), the training loss is upper- bounded as well because
[+]( = || + |vll S Aza + Illll =: C.
(S.25)
Therefore, we have
(t)l S ||
(S.26)
After all, the inequalities (S.22 ,S.23 .S.26) lead to
J ds))(s)) S C J ds||r||?
(S.27)
where C denotes an uninteresting positive constant. By using assumption (iii) that fo ds|[r||2 has an constant upper bound 4n independent of y and e, we have
nb(0)² S.CR.
11 2
(S.28)
2
Therefore, for sufficiently small y, the dominant term is non-negative. Moreover, if we have b,(0) for i,
* 0
V1 nb((0)² O for 7 < min (b)²
(S.29)
R
As side note, the inequality (S.29) ) of gives us some insight into non-asymptotic evaluation on how large y we can take. First, the constant includes and it implies that we need smaller ? for larger parameter norm a. Second, note that R controls the integral of the training loss over the whole training dynamics. We need smaller y as well for a larger It which implies the convergence of dynamics is slower.
Next, we evaluate 2- Since
(x) (Z(b² 8)) bb,
(S.30)
have
1sh.ll S MIRakgaD
(S.31)
Therefore,
1/ zn. S C.
(S.32)
exThus, 1 is finite and becomes negligible in for sufficiently small E.
Finally, we have
b(0)2
887 2
2²
7V 2
CR
C'R,
(S.33)
2
n
14

---

Under review as a conference paper at ICLR 2023
where used Lemma A.1. Substituting the above inequality and b(0) x=r(0) into (S.7) obtain Theorem 4.1.
Remark higher-order terms in Theorem 4.1: First, let us remark ( term. Lemma A.1 tells us that if we have (0) # for all i, we have a slightly stronger result than Theorem 4.1:
QF-GR S Cgg exp(->Ec" 2 O(="))
(S.34)
where the O(>2) term disappears. The condition of (0) * 0 seems to hold in usual cases because the network parameters and training samples are randomly assigned at initialization. Second, regarding O(s²) term, we have Vr 2 0 for
n1 C'R
b,(0)
8Y
S
mim
CR
(S.35)
2
min (0)2
(S.36)
R
where the first line comes from (S.33) and the second one from a small y satisfying (S.33) This implies that we need smaller E for larger à and R in similar way to
Remark on B-GR: We have obtained the upper bound of OF-GR, that is, the lower bound of for F-GR. Since we can see B-GR as the F-GR with negative E, the sign of L is flipped in B-GR. Then, we can easily obtain the upper bound of V as follows.
First, we have
Lo S 2Aman (XXT) Lod [|r(s)]|
(S.37)
S 8namaz (XX )
(S.38)
where Xmaz (XXT) denotes the largest eigenvalue of X.X.. We have
V Vo V + +162
(S.39)
n
b(0)2
$ 8nAmaz (XX (XXT) R 2
(S.40)
where we used Lemma A.1. Substituting the above inequality into (S.7 ), we obtain ar-GR 2 C' exp(1ee")) for positive constant C. Thus, the lower bound increases for larger step size in B-GR and the implicit bias is strengthen in the direction to L2 solutions.
A.2 ALTERNATIVE TO ASSUMPTION (II)
Instead of assumption (iii), we may use
Assumption A.2. For sufficiently small E and 7, the smallest eigenvalue of S(t Xt) is positive.
Since we suppose the overparameterized case (d >> n), the matrix X is wide matrix and S has no trivial zero eigenvalue. The positive definiteness of S sufficient condition of global convergence as follows. From Eq. (S.17). ), we have
d 1
-2((() 1 -5.00)))++((0))) n2
n d3 2
- T
Qa(1))
(S.41)
4 di
dt
Using the inequalities (S.22 SS.23 .S.26) ), we have
dl|r|1? - -
(S.42)
dt
where we take the lower bound of the smallest eigenvalue as X mint, Amin (S((). . By taking a sufficiently small such that < 3 (4CC), we obtain
[|r(1)] < []]] exp(- \/nn
(S.43)
15

---

Under review as a conference paper at ICLR 2023
from Grönwall's inequality. Since [(w(t)) ||r(t)))/((nn), we obtain global convergence. In addition, we have
ds|]r(s)]| & [|(())]] / ds t/n) = 12 /0]]
(S.44)
This gives the upper bound R. Similarly, we obtain R by taking the lower bound of (S.41 ) and using Grönwall's 's inequality. Thus, instead of assumption (iii), we apply Assumption A.2 in the transformation from (S.27) to (S.29).
Note that (t) is known as the neural tangent kernel in the lazy regime and its positive definiteness is straightforward (Woodworth et al., 2020). Although there is no proof of the positive definiteness in the rich regime, observed it in numerical experiments and the assumption A.2 seems rational.
A.3 DERIVATION OF PROPOSITION 4.2
We obtained the upper bound of AF-GR (in other words, the lower bound of v) from the term of 1 In some cases, Vo gives complementary insight.
Proposition A.3. Under the same assumptions as in Theorem 4.1, for sufficiently small and %
OFF-GR S on exp(-7c+ 0 O(e²)) )),
(S.45)
where the exponent e is a non-negative variable given by n f (XB((((s) d))
Proof. Vo is non non-negative by definition and written as
Vo 1. (X (X 2s.
(S.46)
In addition, we have v 2 (()) from Lemma A.1. Therefore, we have V 2 Vo + 0()) + (s
Substituting this into (S.7 ), we obtain the result.
Remark on average of c: Note that may depend of training dynamics. It seems hard to obtain a concrete value of this integral. Instead of evaluating each entries of c, let us analyze the average value of c, that is, ||c|l//d = Ei c./d. This approach gives some insight into typical value the exponent c:
and because it is given by the integral
||c]| /d = ā 1. r(8) TXX (XXT))(())) (s()ds
(S.47)
4n
d Amin (XXT)R.
(S.48)
A similar evaluation has been used in the analysis of SAM (Andriushchenko & Flammarion, 2022).
A.4 HESSIAN
The MSE loss of the diagonal linear network has the following Hessian:
diag X T r) + 2diag(w)) X x Ediag(w))
(S.49)
At the interpolation solution,
2 H diag(w) (w) X diag(w)).
(S.50)
n
B DERIVATION OF THEOREM 5.1
is straightforward to derive this theorem. Consider the time step satisfying L(O,) < b and (0.+1) > b. The update rule is given by
0+1 = 8, + VoL(
(S.51)
0,42 61t1 (oL((())))
(S.52)
16

---

Under review as a conference paper at ICLR 2023
Taking the summation, get
0tt2 = 0: 7 (VII(0 Vol(O.))
(S.53)
= =i=- 11 (O. + +V/L((0)) - VL (0.)
(S.54)
"
Similarly, for I((,) > and I(0x+1) < b, we have
0+11 = 8 (V)))()))
(S.55)
0142 1t+1 (o
(S.56)
and get
U1+2 = 0 + n (VLL(0(+1) VoL(O.)
(S.57)
VC VL VL TT (0.)
= 0: - 1?
(S.58)
11
C EXPERIMENTS
C.1 COMPUTATION OF LEARNING WITH GR
C.I.1 PSEUDO-CODE AND IMPLEMENTATION
In the experiments on benchmark datasets, we computed the GR term in each mini-batch of SGI> update. The pscudo-code for F-GR given Algorithm The double backward computation is implemented shown in Listing 1.
Algorithm 1 Learning with F-GR
Input: mini-batches [1, ..., Br}
I: while SGD update do
2: if i-th mini-batch then
3:
AC < (L(; B,)
4:
+- +&A
5:
AL' VL(O'; Bi)
6:
AR < (AC' AC)/E
7:
0 O 0 M(A + ARR
8:
end if
9:
end while
#backpropagation of original loss loss_pP (gamma/2) suu [torch. sum (p. grad for p in model, pawell..aammttrro
loss
1) #computing GR term
Bass_DB.backwarr #backpropagation of GR term optimizer.r (tep
Listing Implementation of DB in PyTorch.
C.1.2 EVALUATION ON THE NUMBER OF MATRIX MULTIPLICATION
We represent an L-layer fully connected neural network with a linear output layer by Ar = ((Ui). U1 = W for / 1,.... L. We define the element-wise activation function by o(-) and weight matrix by W,. For simplicity, we neglect bias terms. Note that we have multiple samples Ag (within each minibatch) requires L matrix multiplication. Next, let us overview usual backpropagation on the forward pass Ar.). We can express the backward pass B, p'(U)) (W,T, Bt+1), where the backward signal B, corresponds to OL/OU (1 1, ..... L 1). Then, the backward pass requires
input and WLA, requires
-atrix product. Therefore, the forward pass
{Ao A
17

---

Under review as a conference paper at ICLR 2023
L-1 matrix- matrix multiplication between weights W and backward signals B. In addition, need to compute the gradient /C/aw/ = B, for V C and this is also a matrix-matie multiplication. Alter all, need 3L matrix multiplicatiin for V..
Finite difference computation: VZ((0) requires the same number of matrix multiplication as the normal backpropagation. Therefore, V requires 69 - 2. For a sufficiently deep network, this is ~ 6L.
Double Backward computation: Let us denote a by Gt- Figure 2 represents the forward pass for computing the gradient of GR. Note that the upper part of this graph, i.e., {Ao A + + B5, + + Bi J. is well-known in double backpropagation of VB, for the input-Jacobian regularization. As explained in Drucker & Le Cun (1992), the computation of V VB, is equivalent to apply backpropagation to this upper part of the graph. GR requires additional L nodes for G2. Note that when we have a forward pass with matrix multiplication, its backward computation requires two matrix multiplications. That is, when node of the forward pass S is function of the matrix X given by X UV, we need to compute aS/0u = (aS/aX)) ax)v and 0S/0V /V (aSS00X) in the backpropagation. In addition, we do not need compute the derivative of Ag. After all, need 2 x (3L- - 1) - 2 = 6L - for the VR. Since we also compute the gradient of the original loss VL, need 9L 5. For sufficiently deep network, this is 9T.
C.2 DETAILS EXPERIMENTAL. SETTINGS
Figure 1: We trained MLP (width 512) and ResNet on CIFAR- 10 by using SGD with GR. We set batch size 256, momentum 0.9, initial learning rate 0.01 and used step decay of the learning rate (scaled by 5 at epochs 60. 120, 160), = = 0.05 for GR. We showed the average and standard deviation over trials of different random initialization.
Figure 3: (a) We trained the 4-layer MLP and ResNet- 18 on CIFAR-10 by using SGD with GR. We trained the models with various typer-parameters
= (10-5,5 5 x 10-5 ;.... 0.5, 1} and r = 10-1, 101033 ..... 1, 2, 5]. The other settings are the same as in Figure 1. We set
(10-1,2 2 x 10-1, batch size 128, weight decay 0.0001, and used no other regularization technique or data augmentation.
Figure 4: We generated synthetic data by x; (Vuu,, and y/ N ((8", 0.01). 8* is k s*-sparse with non-zero entries equal to 1/Vk*. We set d 100, 50, μ = x² = 5, 0.02 and initialization 00.; ~ (0, 0.01). We trained the models by the discrete time update with a small learning rate 7 0.001. We showed the average of 25 trials with different seeds. We trained the models until the training loss L became lower than 10
Figure 5: We trained ResNet-18 on CIFAR-IO by SGD with flooding (b 0.05). The setting the same as in Figure 1. We computed the gradient norm R by the average of mini-batches in each epoch. We showed the average and standard deviation over 10 trials of different random initialization.
18

---

Under review as a conference paper at ICLR 2023
2.5
F-GR
2
Training Loss
1.5
Training
0.5
0.5
0
20
60
100
0
2000
4000
6000
Epech
Wall Time
Training dynamics in ResNet-18 18 on CIFAR-10. Learning with F-GR is much faster in wall time.
Figure S.1
C.3 ADDITIONAL EXPERIMENTS
C.3.1 TRAINING DYNAMICS
This figure shows the trajectories of the original training loss L. during the training. Its setting the same as in Figure We observed that learning with F-GR could make the loss decrease faster than DB in the sense of convergence rate (i.e., the number of epochs). This means that the loss converges even faster in wall time.
Figure S.1:
C.3.2 GENERALIZATION PERFORMANCE
Figure S.2: To see the difference among algorithms in more detail, show test accuracy along axis with a fixed y of the grid search shown in Figure 3. Each line represents the average and standard deviation over 5 trials of different random initialization. We fixed 7 0.5 for MLP and 0.05 for ResNet-18. This means that the objective function is the same among different algorithms. Nevertheless, the eventual performance different. For large e, F-GR achieves the higher test accuracy than DB beyond one standard deviation. For such a large s, F-GR also performs better than B-GR.
MLP
ResNet-18
0.87
0.57
Test Ace.
0.86
Test
0.56
0.55
DB
0.54
F-GR
0.84
8-0R
0.53
0.83
1
10
10"1
10
10
10
10a
Figure S.2 : 'est accuracy shown in Figure 3 along e axis with a fixed y. We fixed y = 0.5 for ML. and 7 0.05 for R8sNet-18.
Figure S.3: This figure shows an additional experiment of the grid search shown in Section 3.3. We did experiments on a different architecture and dataset, that is, ResNet-34 on CIFAR-10. The result consistent with those in Figure 3. Learning with F-GR achieves the highest accuracy for large ascent steps. B-GR performs much worse for them. In addition, the highest accuracy of F-GR is better than that of DB. The best test accuracy was (F-GR, B-GR, DB) (59.9, 58.6, 59.5) + (0.5, 0.4, 0.5). From this experiment, we can see that the result the finite difference computation with small æ does not necessarily coincide with that of DB. We observed that the training dynamics showed instability for too small e. This would be attributed to numerical instability. The important point is that F-GR shows better accuracy than DB for large ascent steps.
19

---

Under review as a conference paper at ICLR 2023
F-GR
B-GR
DB
0.6
10
0.58
0.58
1
0.54
10"3
10
10
10"
10
10
10
10
Figure S.3 : Grid search on learning with different GR algorithms in ResNet-34 on CIFAR-100, The color bar shows the average test accuracy over trials. Gray dashed lines indicate 7
Table S.1: We trained WideResNet-28-I1 (WRN-28-10) with 7 = {0, 10-1, 10-3, 10-2, 10-1). For F-GR and B-GR. we set {0.001, 0.01, 0.1}. We computed the average and standard deviation over trials of different random initialization, and reported the best average accuracy achieved over all the above combinations of prpeer-arameter. F-GR performs better than DB and B-GR beyond one standard deviation in most cases. We used crop and horizontal flip as data augmentation, cosine scheduling with an initial learning rate 0.1, and set momentum 0.9, batch size 128, and weight decay 0.0001.
Table S.I : Test accuracy of WRN-28-10 10 shows that F-GR performs better. We trained the models with/without data augmentation (DA).
WRN-28-10
CIFAR-I0
CIFAR-100
w/o DA
w/ DA
w/o DA
w/ DA
F-GR
92.1 0.2
96.1=
71.3 0.3
80.7 0.2
B-GR
91.9+
95.9=
71.1
80.2#
DB
91.7+002
95.9 0.1
70.3 0.2
80.3 0.4
C.3.3 DIAGONAL LINEAR NETWORK
Figure S.4: We trained DLNs with various and in the same setting in Figure 4. The black
circles in the figure show the cases of the lowest test error. The best test error was (F-GR, (10- 1.37 10 -1.16 and F-GR performed better.
F-GR
B-GR
10
-044
08
-05
>
10
10
10
10
10
10
10
Figure S.4 Learning of diagonal linear networks with GR. The color bar shows the average test loss over 10 trials. Training dynamics exploded in the gray area.
20

---

Under review as a conference paper at ICLR 2023
C.3.4 FLOODING METHOD
This figure confirms at which epoch the training loss started get close the flood level. The experimental setting is the same as in Figure 5. The blue line shows a flip rate, that is, the ratio of how many times the training loss gets smaller than the flood level during each epoch. Around the 10-th epoch, the training loss started to reach the flooding level and the gradient norm also started decrease.
Figure S.5:
1.2
0.24
Training Loss Flip Rate
0.9
0.18
Training Loss
Flip Rate
0.12
10
10
10²
Epoch
Figure S.5 Flip rate of flooding with = 0.05.
21


Reviews:
[{"review_id": "jO3WtsTiig", "reviewer": "Reviewer_MSVy", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This paper studies the algorithmic behavior of gradient regularization in deep learning. In particular, this paper considers three versions of practical implementations of the gradient calculation of the gradient regularization term: forward finite-difference, backward finite-difference, and double backpropagation. The authors theoretically investigate the algorithmic bias of these three implementations on a diagonal linear network and prove that gradient regularization has an implicit bias to find the solution with potentially better generalization. Finally, the authors illustrate the close connection between finite-difference GR and other training methods such as SAM and the flooding method. ", "summary_of_the_review": "Overall this is a good paper. However, both the theoretical and experimental parts need to be improved according to my comments in the weakness section.", "strength_and_weaknesses": "Strength:\n1. This paper demonstrates certain advantages of using finite-difference computation over double backpropagation on the gradient regularization term.\n2. This paper provides a theoretical analysis to study the implicit bias of gradient regularization on a diagonal linear network and shows that GR can potentially lead to better solutions.\n3. This paper further builds a connection between GR and other learning methods.\n\nweakness:\n1. The theoretical analysis is not clear to me. In particular, Theorem 4.1 and  Proposition 4.2 only give bounds on the final solutions found by the algorithms, while their sharpness is not fully justified. So I am still not clear what’s the exact quantity of the solution. \n2. Following the previous comment, why the final solutions found by F-GR will be smaller than $\\alpha_0$? Does it require $\\alpha_0$ to be positive?\n3. I also cannot understand why Theorem 4.1 suggests that GR tends to select the L1 solution and why the L1 solution has a better generalization performance. It may need a rigorous theory to connect the implicit bias of GR and the generalization performance.\n4. When performing experiments on CIFAR, do you add standard weight decay regularization? More details of the experiment setup should be added.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "I_Tisoh9-aN", "reviewer": "Reviewer_V6uG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "Update: I raised my score to 5 after reading the authors' rebuttal.  \n\n--------  \nThe paper studies gradient regularization, a technique that is often associated with improved generalization in deep learning. The authors consider a finite-difference approximation of gradient regularization that not only decreases the computational cost but also is shown to improve generalization empirically. This effect is proven to hold for diagonal linear networks, which can be seen as a very simple example of neural networks. The authors also validate their claims using numerical experiments on neural networks.", "summary_of_the_review": "All in all, this paper presents a number of small results about finite-difference schemes for gradient regularization. Each result on its own seems to be quite small. The results do not become much stronger together either, since they are on orthogonal topics: numerical efficiency, implicit bias on diagonal linear networks, and the relation to other deep learning techniques. The work seems to lack depth in its theoretical investigation, which makes me suggest a rejection.", "strength_and_weaknesses": "## Strengths  \n1. Gradient regularization has been popular recently and the paper might be of interest to the conference attendees.\n2. The finite-difference approximation is indeed cheaper to calculate than the full gradient with backpropagation.\n3. Some of the theoretical claims are checked numerically.\n\n## Weaknesses  \n1. The overall intuition behind the efficiency of finite-difference approximation is not clear. In general, finite differences yield very noisy estimates of gradients that poorly scale with dimension, and it is not explained why in this case this approximation happens to be better. As far as I can see, this issue, which is normally the main counter-argument against finite-differences, is not addressed in the paper.\n2. The reduction of double backpropagation to forward passes is not a critical improvement. It is of course nice to reduce the training time, but the impact of this change is limited and is only worth it if all other factors (such as variance) remain the same.\n3. The diagonal linear network is mostly a toy example that no one uses in practice. On top of that, the derivation for this problem is mostly the same as done in prior works. A more general theory, for instance, for locally smooth objectives, could be of more interest.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "6luclcjsuM", "reviewer": "Reviewer_jCXs", "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": "GR is a method that penalizes the gradient norm of the training loss during training. However, computing the gradient of GR objectives leads to Hessian evaluation, which is computationally expensive. The paper attempts to accelerate the gradient regularized (GR) training by finite-difference approximations. In particular, forward and backward finite-difference methods are discussed. Theoretically, the implicit bias of GR in diagonal linear model is explicitly characterized. The paper also connects GR to other algorithms based on iterative ascent and descent steps for exploring flat minima.", "summary_of_the_review": "I am leaning towards a positive rating, due to the clarity and the broad scope of the paper.\n\nA major criticism might be Section 4 is a bit disconnected, as the implicit bias does not provide deeper understanding of the finite-difference implementation of GR. This is partly due to the limited analytical tools. Therefore, I would recognize Section 4 as some understanding of GR. In this sense, the concept in the paper is broad, while the inner coherence can still be improved.\n\n==================== Post author response ====================\n\nThank you for addressing my concerns and I am willing to keep the initial rating. A minor point is that I am still not very clear what are the technical contributions in theory. The analysis handles the new term $\\Psi_1$, but what are the new proof details or tools leveraged (developed) in paper? Providing these details would be even more helpful.", "strength_and_weaknesses": "==================== Strength ====================\n\nThe paper targets at an important problem of circumventing expensive Hessian computations in regularized training. Regularized training is essential to the success of modern learning models and gradient regularization has close ties to the flatness of minima and generalization properties. The finite-difference method resolves the computational issue and also achieves good -- even better -- performance. This should be of high interest to practitioners.\n\nThe paper is well motivated and clearly written. The theoretical results seem to be correct.\n\nThe scope of the paper is actually broad; it aims to provide a comprehensive understanding of GR, touching its implementation, implicit bias, and connection to other popular methods.\n\n==================== Weakness ====================\n\nSection 4 is rather toy and seems to lack technical contributions (compared to Woodworth et al. (2020)).", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0yIRCwrrHmz", "reviewer": "Reviewer_hFFP", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "The work considers a gradient norm regularizer and the implicit bias afforded by the numerical methods for computing the regularization terms, namely, (1) forward finite difference, (2) backward finite difference, or (3) double back propagation. It was suggested that forward finite difference with a relatively large time step gives the best generalization among the three methods. Additionally, the paper discussed some theory for this phenomenon using a diagonal linear networks. Finally, some connections to two existing algorithms, sharpness-aware-minimization and flooding method, are discussed. ", "summary_of_the_review": "Please see above. Due to the mentioned issues I would like to keep my scoring conservative for now. I will consider increasing my score if my questions receive proper replies. I am being conservative because some of the results are quite surprising to me.", "strength_and_weaknesses": "# Strength \n1. Overall I find the writing is good and most of the presentation is clear. \n2. It is very novel to my knowledge the observation/conjecture that a finite difference scheme with a positive and large time step might bring additional implicit bias. \n3. I like the discussion about the connection of the authors' finding and the existing SAM, flooding methods. I think it brings some interesting insights that could potentially unify several existing methods that were developed from different areas. \n\n# Weakness\n\nThe Strength#2 is too surprising to me such that I have to ask a lot of questions to be fully convinced. \n1. Section 3.3. Could you report the stand deviation/error bar for the data obtained for MLP and ResNet-18? \n\n2. I checked Table S.1 that presents test accuracy for WRN, where some error bar is provided. However, the difference between the three schemes is too small to be interesting to be honest (most of the cases the differences is O(0.1%) in terms of accuracy).\n\n3. Figure 3 is interesting, but is hard to interpret as the exact numbers are hard to read. \n\n4. Note that compared to DB, finite difference introduces an additional hyper parameter $\\\\epsilon$. Would you say that the small advantage of finite difference is actually due to the additional flexibility for tuning the new hyperparameter? I would love to hear some discussion on this issue, because the improvement does not seem to be significant so I think it is very likely caused by tuning the hyperparameter. \n\nThe following questions are about the theory, which I find not been presented as clear as the other part of the paper. \n\n5. Theorem 4.1. Assumption (iiI) could use more discussions. First of all, $L(\\\\cdot)$ is a function of a $2d$-dimensional vector, why it can be integral over a real line? Secondly, it requires the upper and lower bound for the integral to be independent of small $\\\\gamma$ and $\\\\epsilon$. Why this is related to the convergence speed of the dynamics with/without GR?\n\n6. Can you briefly discuss how large the quanatity $\\\\epsilon$ and $\\\\gamma$ could be in Theorem 4.1? Because in the follow-up discussion you have mentioned that a larger $\\\\epsilon$ leads to a stronger regularization. I am just wondering how much changing on the bound is allowed to happen. \n\n7. Since Theorem 4.1 only provides upper bound on $\\\\alpha$, this does not necessarily support the follow-up discussion that a larger $\\\\epsilon$ leads to a stronger regularization. Note that a larger $\\\\epsilon$ only leads to a smaller upper bound on $\\alpha$, which does not necessarily mean that $\\alpha$ itself is decreased. Indeed, Eq(12) provides another upper bound on $\\\\alpha$ that does not decrease when $\\epsilon$ increases. So at least one can take the minimum of the bounds in Eqs(11) and (12), which is still a valid upper bound on $\\alpha$. Would you say that this improved upper bound is still decreasing when $\\\\epsilon$ increases? \n\n8. It seems that $c$ in Eq(12) is a vector? But $c\\^\\*$ in Eq(11) is a constant? I am just confused by the notations, and I find the follow-up discussion after Proposition 4.2 is hard to interpret because it mentioned \"the average over entries\" of $c$.\n \n\n# Typos\n- A lot of figures are not correctly numbered. Please double check. \n- Theorem 4.1, assumption (ii), upper -> upper bound.\n- The comments on Figure 5 might have some typos. It seems to me that the loss gets close to the flood level at about the $100$ epoch instead of the $10$-th epoch. \n\n\n\n\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject