{'fraction_non_alphanumeric': 0.04684574861770212, 'fraction_numerical': 0.01599982585223562, 'mean_word_length': 4.164006294964029, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 11, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 29, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Explicit Regularization in Overparametrized Models via Noise Injection

Injecting noise within gradient descent has several desirable features. In this paper, we explore noise injection before computing a gradient step, which is known to have smoothing and regularizing properties. We show that small perturbations induce explicit regularization for simple finite-dimensional models based on the l1-norm, group l1-norms, or nuclear norms. When applied to overparametrized neural networks with large widths, we show that the same perturbations do not work due to variance explosion resulting from overparametrization. However, we also show that independent layer wise perturbations allow to avoid the exploding variance term, and explicit regularizers can then be obtained. We empirically show that the small perturbations lead to better generalization performance than vanilla (stochastic) gradient descent training, with minor adjustments to the training procedure.


Introduction
Injecting noise in gradient descent has several desirable properties. In previous works [24,48,55], noise injection after the gradient step has been used to escape saddle points efficiently in non-convex optimization. In several recent works [42,66], it was also shown that noise injection in gradient descent helps to escape local minima while optimizing non-convex functions. Adding noise within the gradient, either on labels or on the iterates before computing the (stochastic) gradient, has been classically used to smooth the objective function (often in the convex case) [12,13,14,39,40,46]. However, the effect of noise injection on generalization is not as well understood.
Recently, there has been some interests in understanding the geometry of the loss landscape enforced by the induced noise and its connection with generalization. A recent result [35] shows that perturbed gradient descent with sufficiently small noise converges to flat minima for non-convex matrix factorization tasks. Orvieto et al. [43] also provide some explanation and empirical evidence for better performance of noise induced gradient descent as the noise injection favors flat minima.
In this work, we explore several avenues along this line of work. Our aim is to tackle the following questions: • Do small perturbations in the model while training induce an explicit form of regularization for simple models common in machine learning?
• Do the same perturbations also induce an explicit regularization effect while training overparametrized models such as homogeneous neural networks with large (infinite) widths?
• Is the induced regularization useful in practice, i.e., does it lead to better generalization performance?
In response to the questions discussed above, we make the following contributions: • We show in Section 2 that small perturbations induce explicit regularization for simple models, and that this induced regularization is based on the 1 -norm, group 1 -norm, or nuclear norms. Such explicit formulations were available before for only special cases ( 1 -norm), or for special loss functions (logistic regression in the separable case).
• We show in Section 3 that the same perturbations do not work for overparametrized neural networks with large widths due to variance explosion resulting from the number of neurons tending to infinity. However, we also show that independent layer wise perturbations (where only one layer is perturbed at each gradient step) allow to avoid the exploding variance term, and explicit regularizers can be obtained, for a fully connected network with a single hidden layer. This is extended in Section 4 to deep feed-forward networks.
• We empirically show in Section 5 that the small perturbations lead to better generalization performance in practice over vanilla (stochastic) gradient descent training, for a variety of shallow and deep models, fully connected or convolutional, with minor adjustments to the training procedure.

Related work
Noise injection has been frequently used for various tasks in statistics, machine learning and signal processing. In this section, we discuss three major directions of research and existing literature associated with them which are closely connected to our work.
Perturbed gradient descent (PGD). PGD methods are versions of (stochastic) gradient descent (GD) where noise is injected in one of the following two ways: In the first option, perturbations are added after each GD step. Such versions of PGD have been shown to speed up the escape from spurious local minima and saddle points; see Zhou et al. [65] and Jin et al. [25], respectively. These methods correspond to discretizations of the continuous-time Langevin dynamics [34] where the perturbations add to the diffusion coefficient. In the second option, perturbations are added to the iterate before the gradient is evaluated. The so-perturbed gradient is then used to update the unperturbed iterate. In the convex case, this is typically used to smooth a non-smooth objective function [12,13,14,39,40,46]. In the non-convex case, such versions of PGD have been shown to exhibit an implicit bias toward flat minima (that generalize better) in the case of nonconvex matrix factorization [35], and more general models [43]. Flat minima are widely believed to have a better generalization property [7,23,26], and we follow this line of work, with several generalization guarantees that are based on PAC-Bayesian analysis and also apply to our framework [41,56]. The second option of PGD can be interpreted as an instance of the first option where the perturbations are anticorrelated. Such methods are therefore also referred to as Anti-PGD; see Section 2 from Orvieto et al. [43]. In our current paper, we determine the effective loss that is (on average) used in the second option.
Explicit and implicit regularization in learning. It is well understood that regularization plays a crucial role in the generalization performance of a learning model. The most common form of regularization is Tikhonov regularization [17,59], which is imposed explicitly in the optimization objective for linear and non-linear models. There are other ways to induce regularization explicitly while training machine learning models [20,47,54]. Apart from explicit regularization methods, optimization algorithms can also induce implicit bias on the optimal solution, which was observed by [19,30,53]. In a closely related line of work, Camuto et al. [6] study the regularization induced in neural networks by Gaussian noise injections to all network activations, and studies its regularization effect in the Fourier domain. However, while they obtain explicit regularizers similar to ours, we study the effect of noise injection to the model parameter instead of network activations, and hence our analysis is applicable to general machine learning models. Moreover, we deal with infinite widths through layer-wise perturbations.
Robustness. Apart from inducing regularization and finding flatter minima, noise injection is also helpful in getting robust models. Recent works [11,32,33,49] have shown that randomized smoothing is a scalable way of building provably robust neural network based classifiers. However, these approaches rely on input perturbation instead of model perturbation. Wu et al. [62] showed that adversarial weight perturbation helps in flattening the weight loss landscape, which improves the robust generalization gap. Zheng et al. [64] also employ adversarial model perturbation to to favor flat local minima of the empirical risk. However, a systematic study of the influence of noise injection in the model is lacking.

Finite-dimensional models
In this section, we consider a loss function L : R n → R, as well as a predictor Φ : R m → R n , and we aim to minimize with respect to w ∈ R m . In machine learning contexts, Φ(w) represents the n real-valued predictions over n inputs, and L is the associated loss function, typically, L(ϕ) = 1 2n n i=1 (y i − ϕ i ) 2 for leastsquares regression, or L(ϕ) = 1 n n i=1 log(1 + exp(−y i ϕ i )) for logistic regression, where y ∈ R n is the vector of output labels. The framework applies equally well to multi-dimensional outputs (such as for multi-category classification and the multinomial loss), where R n is replaced by R n×k (this is in fact considered in Sections 2.4, 3 and 4 for neural networks).
In this section, we only consider the asymptotics with respect to σ, assuming that the number of parameters m remains fixed (hence the denomination "finite-dimensional"). We analyze the effect of strong overparametrization with the number of parameters tending to infinity in Sections 3 and 4.

Gaussian perturbations and Taylor expansions
Following previous work on PGD (see Section 1.1), we consider perturbing the iterate by a standard Gaussian vector ε (with zero mean and identity covariance matrix), and consider the function We denote by DΦ(w) ∈ R n×m the Jacobian (matrix of first-order derivatives) of Φ, and D 2 Φ(w) ∈ R n×m×m the tensor of second-order derivatives.
Taylor expansions. Throughout this section, we assume for simplicity of exposition that L and Φ are three times differentiable functions with bounded third derivatives. In Appendix A, we discuss the case of functions where this is satisfied only piece-wise (to cover RelU activations). The Taylor expansion of Φ at w can be written: where We also need a Taylor expansion of L around Φ(w), which can be written as where, for ϕ ∈ R n , DL(ϕ) ∈ R 1×n is the row-vector of first-order partial derivatives, and D 2 L(ϕ) ∈ R n×n the matrix of second-order partial derivatives, with the notation To compute an expansion of R σ , as defined in Eq. (2), we compose the two expansions and get, . Taking expectations, using E[ε] = 0 and E[εε ] = I, we get: The careful reader will have noticed that we assumed that Φ is in C 3 ; in Appendix A we present an extension to the case where Φ is only piecewise in C 3 (e.g. RelU).) Note that the added terms on top of R(w) = L(Φ(w)) can be derived as well from the trace of the Hessian of R, as obtained by Orvieto et al. [43].
Minimizing R σ with stochastic gradient descent. As discussed by Orvieto et al. [43], in order to minimize R σ defined as an expectation in Eq. (2), we do not need to compute the expectation: we simply use a single perturbation (i.e., a single Gaussian vector ε), and compute the gradient with respect to parameters, which leads to an unbiased estimate that can be used within a stochastic gradient descent algorithm. Since the loss function L has a finite sum structure, we can also use stochastic gradient over observations, as traditionally done in machine learning.

Asymptotically equivalent objective functions
In several situations, we will show that we obtain the following "asymptotically equivalent" cost function R in the sense that finding a global minimizer of R σ (w) = E L(Φ(w + σε)) is essentially equivalent to finding a global minimizer of R (eff) σ (w) as σ → 0. In other words, the term σ 2 2 DL(Φ(w))D 2 Φ(w)[I] in Eq. (5) has no impact. This will be done by showing that the order of approximation between R and R σ is of order σ 2 , while the one between R σ and R (eff) σ is of order σ 3 , in two different cases.
Hessians with no cross-products. One simple sufficient condition for the term σ 2 2 DL(Φ(w))D 2 Φ(w)[I] to have no impact is that D 2 Φ(w)[I] = 0 for all w ∈ R m , which is satisfied for certain models such as neural networks, where the second-order derivatives have no cross-product terms (see Sections 2.4, 3, and 4). The following theorem makes it precise for sufficiently regular functions. See proof in Appendix A (already sketched above), as well as more general results.
Overparametrized models. A more general condition is related to overparametrization (when the model is sufficiently rich to lead to the minimizer of L), and we make a formal statement below with simplified assumptions. See Appendix A for the proof and more refined conditions. Theorem 2. Assume that (a) Φ is three-times continuously differentiable with uniformly bounded second and third derivatives, (b) L is strongly convex with uniformly bounded second and third derivatives, with unique global minimizer ϕ * , (c) there exists a (non-unique) w * ∈ R m such that Φ(w * ) = ϕ * , and that (d) there exist minimizers w σ * and w σ,(eff) * of R σ and R (eff) σ that lie in a compact set Ω ∈ R m . Then, if w σ * is a minimizer of R σ , and w σ,(eff) * is a minimizer of R . Note that (a) we characterize the prediction function Φ taken at the various minimizers to characterize asymptotic equivalence (but it is not possible to characterize a distance between parameters because in overparametrized models, Φ cannot be injective), and (b) when σ tends to zero the minimizer should converge to the interpolator Φ(w) = ϕ * with minimal D 2 L(Φ(w)) DΦ(w)DΦ(w) .
Below, we consider specific cases for the least square loss and the logistic loss in the separable case, before considering specific simple models for Φ.
Least-squares regression. We consider L(ϕ) = 1 2n y − ϕ 2 2 , which is a quadratic function with constant Hessian 1 n I. We therefore get an extra regularizer on top of R(w) equal to σ 2 n tr DL(Φ(w))DL(Φ(w)) . Note that our regularizer is then related to the neural tangent kernel [22], i.e., this is the trace of the corresponding kernel matrix. While this could lead to interesting further connections, we note that our work applies beyond the lazy training regime (that is, our parameters w can vary significantly) [10].
Separable logistic regression. If we consider the logistic loss with an overparametrized model, then the infimum of L is attained at infinity, and we should expect Φ(w) to diverge along a specific direction, like in other similar models [9,53].
For homogeneous models like considered by Lyu and Li [37], we can expect w to diverge in some direction, that is, w = λ∆ for λ → +∞. The term DΦ(w)D(Φ(w)) grows in λ, while D 2 L(Φ(w)) converges to zero exponentially fast. Overall, we conjecture (and empirically observe) that we get divergence, and that the direction ∆ ends up being proportional to the minimizer of DΦ(∆) 2 F such that y • Φ(∆) 1, where y ∈ {−1, 1} n is the vector of labels. See Appendix B for more details.

Lasso and 1 -norm
Following Pesme et al. [45], Vaskevicius et al. [57], Woodworth et al. [61], we consider "diagonal networks". All of the three mentioned works achieve implicit sparsity regularization under sufficiently small initialization of the model parameter. Here we show that noise injection in the model also induces an 1 -regularization in the problem. The main advantage we have over the discussed work is that our approach is applicable to more complex models as we show below.
We consider w = (w 1 , w 2 ) ∈ R 2d , and Φ(w) = X( When the model is overparametrized, that is X has rank n, we can apply Theorem 2, and we then get an equivalent risk: which is exactly the Lasso once considering where β = w 1 • w 1 − w 2 • w 2 (an explicit derivation of Eq. (7) is given in Appendix C). However, there exist many efficient algorithms dealing with 1 -regularization [see 4, and references therein], and one should probably not use our reduction to optimize the Lasso problem in Eq. (8).

Nuclear norm (linear networks)
Following Arora et al. [1], Baldi and Hornik [5], Gidel et al. [15], Saxe et al. [50], we consider w = (W 1 , W 2 ), with W 1 ∈ R d 1 ×d 0 and W 2 ∈ R d 2 ×d 1 , and Φ(w) = W 2 W 1 X with input data X ∈ R n×d 0 . We consider the square loss for simplicity, that is, We can then apply Theorem 2, where the Hessian has no diagonal term, and we get (see detailed computations in Appendix C): F · X 2 F with respect to compatible matrices W 1 and W 2 , leading to the penalty √ d 2 X F · M X * , where · * is the nuclear norm (sum of singular values), which favors low-rank matrices. Thus, minimizing R (eff) We obtain a nuclear norm penalty, thus providing an explicit regularizer in situations where the classical techniques for diagonal networks do not extend. See an empirical illustration in Section 5. We would also like to mention here a conjecture from Gunasekar et al. [18], which claims that with small enough step sizes and initialization close enough to the origin, gradient descent on a full dimensional factorization converges to the minimum nuclear norm solution, which we obtain explicitly using our noise injection approach without making those assumptions. Like for the Lasso, we are not advocating for gradient descent to be a particularly good algorithm for solving the problem above, although a detailed analysis is worthwhile performing as future work.

Extensions
Other models could be considered as well, with relationships to other explicit regularizers.
Group Lasso. It is traditional to recover the group Lasso as a special case of nuclear norm minimization [see, e.g., 2]. This is detailed in Appendix C, and can also be applied to the Lasso with a different formulation from Section 2.3 (and no need for overparametrization).
Optimizing over the PSD cone. By considering w ∈ R d×r , with r d and Φ(w) = ww ∈ R d×d , then for a cost function L over symmetric matrices, we would get a trace penalty over positive semi-definite matrices.
Beyond quadratic models. Thus far, we have considered only functions Φ that were quadratic. This can be extended to higher order polynomials, like done for linear networks below, but we could imagine applications to tensor decomposition beyond the matrix decomposition above [27,28,51].

One-hidden-layer neural networks with infinite widths
So far we have discussed the effect of noise injection on simple machine learning models. In this section, we will focus our attention on more complex models like neural networks with potentially large widths (where the limit of large widths is taken before the limit of small σ). In this section, we start with a single hidden layer, and extend to deeper networks in Section 4.
We first start with linear networks, before considering ReLU activation functions in Section 3.3. For simplicity, we only consider the (multivariate) square loss in our analysis.

Exploding variance for linear networks
As already shown in Section 2.4, we consider the matrix of labels (we allow here for multi-dimensional outputs).
We here consider the overparametrized limit We have, with Gaussian perturbations E 1 and E 2 , an explicit exact expansion for linear networks: Taking expectations and using that E 1 , E 2 have zero mean and are independent, and such that, and M any symmetric matrix of compatible size, we can get E Φ(w + σε) = Φ(w), and: We can now compute R σ as: We recover the expression from Section 2.4, but we have an extra term σ 4 2n d 2 d 1 X 2 F , which is of superior order in σ, but problematic when d 1 → +∞.
Note that due to our initialization, the term σ 2 2n tr(W 2 W 2 ) tr(X X) scales as σ 2 n X 2 F , while the term σ 2 n d 2 tr(W 1 X XW 1 ) scales as d 2 σ 2 n X 2 F , with thus no explosion in d 1 . However, the term σ 4 2n d 2 d 1 X 2 F explodes when d 1 goes to infinity. This is the exploding variance problem of perturbing all layers simultaneously -see discussion in the experiment section as well as Figures 1 and 3. We provide a fix by perturbing one layer at a time, which we now present.

Layer-wise perturbations for linear networks
We consider the selection of one layer j ∈ {1, 2} out of the two layers at random, and add √ 2E j to W j before computing the gradient. This corresponds to minimizing an objective functioñ R σ (W 1 , W 2 ), which is an expectation (both with respect to j and E j ) equal tõ that is, the exploding variance term is not there anymore, and we arrive at the same nuclear norm interpretation as in Section 2.4. This generalizes to non-linear activation functions as we show next.

One-hidden layer with non-linear activations
We now consider the same set-up as the previous section, but with ReLU activations, that is, We consider the square loss for simplicity, but this applies more generally.
We also consider weights W 1 and W 2 initialized with respective scales 1/ √ d 1 d 0 and 1/ √ d 2 d 1 , as in the previous section. This corresponds exactly (after re-scaling) to the mean-field limit that allows representation learning [8,38,52,60], and for which the scaling so that W 2 2 F and W 1 2 F do not explode is preserved throughout the optimization.
In this section, we consider asymptotics explicitly with respect d 1 (going to infinity), and then with respect to σ (going to zero). We show in Appendix D that the same variance explosion as in Section 3.1, when perturbing all layers simultaneously, still occurs in the limit of infinite widths and non-zero σ. We thus only focus here on the layer-wise perturbation.
Locally, we obtain Φ( We can therefore computeR σ as: Note that here our regularizer is 2-homogeneous, like considered by Chizat and Bach [9], but that the penalty is not any more separable in W 1 and W 2 . Like done by Chizat and Bach [9], we can take the number d 1 of hidden neurons to infinity and study the associated function space norm, which has similar adaptivity properties (see the Appendix D for details).

Deeper networks
In this section, we show that we sill get the explicit effect of perturbing each layer selected randomly with standard deviation σ √ M , where M is the number of layers, and the extra √ M term is added to take into account that the expectation with respect to the choice of the layer adds a multiplicative factor 1/M . In this section, we will mainly show that the expression of R (eff) σ found for finite-dimensional models in Section 2, is still valid, that is: Note that with full perturbations, and with a number of neurons going to infinity, we would get a variance explosion (see discussion in Appendix E). In this section, to simplify the exposition and avoid technicalities, we only consider linear networks (see Appendix E for non-linear ones).

Linear networks. Consider a linear neural network with
We now analyze the effect of independent layer-wise perturbations on this linear network.
We consider the selection of one layer j out of the M layers at random, and add a random Gaussian matrix √ M E j to W j . We then have an expectation (both with respect to j and E j ), equal toR We can then compute expectations and get which is exactly Eq. (11). We thus have a non-exploding explicit regularizer, based on the gradient of the prediction function with respect to the parameters. We show in Section 5 that this extra regularization does improve test accuracy, and leave for future work the detailed theoretical study of this new regularizer.

Experiments
The goal of this section is to provide experimental evidence to back-up the results of the last sections. In particular, we compare gradient descent (GD) with the perturbed variants studied in this paper: (1) noise injection at each weight in the model, for each iteration (named "GD+noise"), and (2) layer-wise perturbations (injection layer is sampled at random) at each iteration (named "GD+noise (layer)"). All perturbations are performed before the gradient computations. As seen in Section 3.2, if the variance of layer-specific weight perturbations is σ 2 M , where M is the number of layers, then the two noise injection methods minimize a similar regularized loss, in expectation. However, as the degree of overparametrization (e.g., number of parameters) increases, the theory suggests that layer-wise perturbations are preferable (see Sections 3.1 and 3.2). A compressed version of our code is available at https://github.com/aorvieto/noise_injection_overparam.
Minimization of the regularized loss. For a start, we consider a one hidden layer network with linear activations and either 50 or 300 hidden neurons on a randomly generated sparse 1 synthetic regression data set with inputs in R 10 and outputs in R. In Figure 1, we show the dynamics of the original and regularized loss derived in this paper. As the theory predicts, minimization of the regularized loss in the strongly overparametrized setting is only achievable with layer-wise perturbations (see Section 3.2). As discussed, to keep the noise injection scales comparable, the variance of the noise in the layer-wise approach is doubled compared to the vanilla approach. This depth scaling is adopted for all further experiments. As a final note, we clarify that the experiments in this section are performed under the standard Glorot/He initialization of the weights [16? ]: while the results in Section 3.1&3.2 are derived for a theoretically more convenient initialization, similar conclusions can be written down in this more practical settingas the results in Figure 1 clearly showcase. Effect of tuning. The findings of the last paragraph are reported for one specific value of σ. We test the influence of σ on a slightly more complex model: an MLP with 2 hidden layers (5000 neurons each) and ReLU activations on Fashion MNIST [63] (classification). Given that the data is relatively easy to fit, we train on a subset of 1024 data points -to induce heavy overparametrization. We run full-batch gradient descent with learning rate 0.005, and plot the test accuracy evolution (computed using 10K data points) for different values of σ. Figure 2 shows that, for this wide model, layer-wise perturbation acts as an effective regularizer that is able to increase the test accuracy. This is in contrast to standard noise injection (cf. Section 3.1).
Deep MLPs. Next, we test how the findings carry over to deeper networks. In the same data setting as the last paragraph, we consider now a ReLU MLP with 5 hidden layers and either 1000 (narrow) or 5000 (wide) hidden neurons. In Figure 3 we test our methods (σ = 0.05) against full-batch GD, with a step size of 0.005 in the narrow setting and 0.001 in the wide setting, to account for the more complex landscape. As can be seen, again layer-wise perturbations yield the best result. This is also reflected in the size of the regularizer (trace of Hessian), which is minimized by the best-performing method in terms of test error.
Convolutional networks. Finally, in Figure 4 we go a bit beyond our theoretical setting and test the application to convolutional networks on CIFAR10 [29], with full data and stochastic gradients (batch-size 1024). In this setting, we use a Toy CNN (2 convolutional layers with 5 channels + 3 fully-connected, details in the Appendix), and compare against a wider fullyconvolutional network with moderate width (4 convolutional layers with 128 channels + one linear layer). The same pattern we discussed can be observed also in this setting, albeit less pronounced due to the narrow nature of convolutional networks with reasonable number of channels. Note that in the fully convolutional wide network, the trace of the Hessian in the noise injection setting is damped but oscillates around zero. This is quite different from the MLP setting.

Conclusion
In this paper, we showed how explicit regularizers could be obtained from small random perturbations of parameters, both for simple machine learning models, and deep learning models with   On the left we show the performance using a toy PyTorch CNN+MLP (5 channels) while on the right we perform the same task on a fully convolutional network with 5 layers and 128 channels on 3 layers. All details are reported in the Appendix. We run SGD with batch size 1024 and learning rate 0.005 (0.001 for the PyTorch CNN+MLP) and cosine annealing [36]. We plot the performance for σ = 0.005 of the two noise injection methods. Plots of the loss dynamics are provided in the Appendix.
potentially a large number of neurons. This regularization is obtained by independent layer-wise perturbations, can be easily added to existing training codes, and lead to improved accuracies in our experiments. Several avenues for future research naturally open: (a) obtain non-asymptotic optimization convergence results for the models in Section 2, (b) a detailed theoretical study of the regularization properties of our new regularizer for deep networks, and (c) applications to other architectures, such as Resnets [21] or transformers [58].

A Proofs of equivalences
Note that in finite-dimensional models, all norms are equivalent, so we use any of them, unless otherwise stated.

A.1 Proof of Theorem 1
Theorem 1. Assume that (a) Φ and L are three-times continuously differentiable with uniformly bounded third derivatives, (b) D 2 Φ(w)[I] = 0 for all w ∈ R m . Then, there exist constants Proof. We first observe from Eq. (2) that By using the inequality (due to bounded second derivative of Φ) we obtain the first desired bound uniformly bounded by Ass.

DΦ(w)DΦ(w)
For the second desired bound, we observe from Eqs. (2) and (6) that which concludes the proof. (Note that in this proof the precise value of the constant C > 0 is changing form line to line. It is not necessarily the same as the C in the statement of the theorem.)

A.2 Proof of Theorem 2
Theorem 2. Assume that (a) Φ is three-times continuously differentiable with uniformly bounded second and third derivatives, (b) L is strongly convex with uniformly bounded second and third derivatives, with unique global minimizer ϕ * , (c) there exists a (non-unique) w * ∈ R m such that Φ(w * ) = ϕ * , and that (d) there exist minimizers w σ * and w σ,(eff) * of R σ and R (eff) σ that lie in a compact set Ω ∈ R m . Then, if w σ * is a minimizer of R σ , and w σ,(eff) * is a minimizer of R Proof. As proved in Eq. (13) under the same assumptions, we again have (Here, and in the rest of the proof, C > 0 is a constant independent of σ which may change from line to line.) Similarly, by both the boundedness of second derivatives of L and Φ, we have that Thus, by putting both bounds together, there exists a constant C > 0 such that for all w, Hence, if w σ * is a minimizer of R σ , we have the chain of inequalities by µ-strong-convexity of L. Thus, since w * and w σ * are in a predefined compact set Ω for σ small enough and since Φ(w) is bounded on Ω due to boundedness of its second derivative, we arrive at: . This shows the first statement. We also consider a minimizer w σ,(eff) * of R (eff) σ , which satisfies the same bound as above (exact same reasoning), that is, Since DL(Φ(w σ,(eff) * )) C due to w σ,(eff) * ∈ Ω (compact set) and

A.3 Extension of asymptotic theory from Sec. 2 to piecewise regularity of Φ
In this section, we show how the derivation of R σ (w), Eq. (5), and Theorem 1 can be extended to deal with a more general predictor Φ. More precisely, we extend it to the case where globally Φ is only assumed to be continuous and the additional regularity of Φ is only given piecewise, i.e., where there exists a finite number of open convex sets {Ω i , i = 1, . . . , M } with i∈I Ω i = R m such that Φ restricted to Ω i is in C 3 for all i. This is an important extension because it takes care of locally non-differentiable activation functions, such as ReLU.
Extension of Eq. (5) Let w ∈ Ω i for a fixed i = 1, . . . , M . Under the above piecewise assumption, the Taylor expansion of Φ at w can now be written: Thus, as in the main text, we have with the integrands from the above cases of L(Φ(w + σε)). Now,

Now, taking the expectation we get
analogously to the main text, and lim σ→0 J 1 (σ) = 0 because the probability mass of {ε : w + σε ∈ Ω i } under N (ε; 0, I) goes to zero exponentially fast, while L(Φ) can diverge at most polynomially. Thus, we arrive at Eq. (5) from the main text.
Extension of Theorems 1 and 2 Above, we saw how our Taylor expansions and averaging carry over to the case where Φ is only piece-wise in C 3 . Holding this in mind, we can now verify that the above proofs of Theorems 1 and 2 also carry through in this case: Since both Theorems are formulated only for sufficiently small σ > 0, this can be easily verified. For Theorem 1 this is trivial, one just has to emphasize that σ > 0 is small enough after each step. For Theorem 2, one additionally has to make sure that the minimizers w σ * and w σ,(eff) * of R(w) = L(Φ(w)) and R (eff) σ are also in Ω i . But this will hold true for all sufficiently small σ for the following reason: First, for w σ * this follows from the fact that J 2 (σ) goes to 0 exponentially fast, as σ → 0. Hence, only values of L(Φ(w)) for w ∈ Ω i matter to determine the minimizer w σ * , which will thus lie in Ω i . Second, under the assumptions of Theorem 2, the difference between R σ and R (eff) σ is in O(σ 3 ). Thus, for σ small enough, w σ,(eff) * will lie in the same open convex set as w σ * , i.e., in Ω i .

B Logistic regression
We consider a 2-homogeneous model such that Φ(λw) = λ 2 Φ(w) for any w and λ > 0. We aim to minimize 1 n where y ∈ {−1, 1} n . We assume that the model is overparameterized, so that there exists w such that y i Φ(w i ) > 0 for all i. Following Lyu and Li [37], we expect w to diverge in some direction, that is, w = λ∆ for λ → +∞ and ∆ 2 = 1. We assume that this is the case, and we derive here an informal argument highlighting what the limit direction ∆ should be.
In the function from Equation (6), the term DΦ(w)D(Φ(w)) grows in λ as λ 2 DΦ(∆)D(Φ(∆)) , while D 2 L(Φ(w)) is diagonal and proportional to exp(−λ 2 |Φ(∆) i |), with the same scaling as the loss function. We thus get an asymptotic approximate cost function equal to, since |Φ(∆) i | = y i Φ(∆) i (because we have perfect predictions): By taking the gradient with respect to w, we get that We conjecture that this is equivalent to the optimality conditions of the problem max ∆ 2 1 min i∈{1,...,n} where for σ = 0, this is the result of Lyu and Li [37]. We leave a formalization of such a result for future work.

C Direct derivations of formulas from Sections 2.3 and 2.4
This section contains some explicit derivation of formulas that were asserted in the main text.

C.2 Nuclear norm (linear networks)
For the main text, only the derivation of Eq. (9) is missing. To this end, we first observe that Moreover, Hence, with and Putting all equations to together concludes the derivation of Eq. (9).

C.3 Group Lasso
Extension to "group Lasso". It is traditional to recover the group Lasso as a special of nuclear norm minimization [see, e.g., 2]. We thus consider w = (v 1 , w 1 , . . . , v d , w d ) ∈ R d(k+1) , with v j ∈ R and w j ∈ R k , and Φ(w) = v 1 X 1 w 1 + · · · + v d X d w d , for X 1 , . . . , X d ∈ R n×k , and L(ϕ) = 1 2n y − ϕ 2 2 . This corresponds exactly to a linear network defined above, with X = (X 1 , . . . , X n ), W 1 defined by blocks and block-diagonal with blocks w j , and Regardless whether the model is overparametrized or not, we can apply Theorem 1, and we get: See the Appendix for a detailed derivation of Eq. (37). Optimizing over the "invariance of scale" (we can multiply v j by α j and divide w j by the same α j ), we get the equivalent problem of minimizing where β j = |v j |w j , which is a form of group Lasso. In particular if all β j 's have dimension one, we recover the Lasso with a different formulation from Section 2.3 (and no need for overparametrization). (37) First we note that D 2 L(Φ(w)) = 1 n I, i.e. the identity matrix, and that

Derivation of Equation
Under this notation, we get the Jacobian Now, which implies that By our above notation D 2 L(ϕ)[M ] = n a,b=1 D 2 L(ϕ) ab M ab ∈ R, we now get the desired formula: D Appendix for Section 3 (one-hidden layer)

D.1 Explosion of full perturbations
We have discussed the exploding variance phenomena in one hidden layer linear networks in Section 3.1. We here discuss the variance explosion in one hidden layer neural networsk with ReLU activations . Similarly, we here consider the overparametrized limit d 1 → +∞ with initialization which corresponds to having weights of order (W 1 ) ij ∼ 1 where the positive part is taken element-wise. We have, with Gaussian perturbations E 1 and E 2 , an explicit exact expansion for one hidden layer ReLU networks for small σ (so that Φ is locally quadratic): Taking expectations and using that E 1 , E 2 have zero mean and are independent, and such that, Consider a case when (W 1 X ) 0 + = 1 at all of its entries. In that case, We can now compute R σ as: The extra term σ 4 2n d 2 d 1 X 2 F is of superior order in σ, but problematic when d 1 → +∞ using same argument as that for linear net with one hidden layer.

D.2 Layer-wise perturbation
Now, we show that layer wise perturbation helps in variance control. Consider the following two cases : Similarly, Hence, Similarly, If we choose uniformly at random the layer to be perturbed, then one can then see that 2 Due to same argument as that for one hidden layer linear net, R σ (W 1 , W 2 ) is well behaved.

D.3 Function space
Here we change slightly the notations to be closer to notations from Chizat and Bach [9]. Given some data x 1 , . . . , x n , we consider the function ψ(a, b) = a(b x i ) + , with (a, b) ∈ R d+1 , and Φ(a 1 , b 1 , . . . , a m , b m ) = 1 m n i=1 ψ(a i , b i ), with all weights with unit scale. This corresponds exactly to the one-hidden layer neural network, where m = d 1 .
We consider L(ϕ) = 1 2n y − ϕ 2 2 , and the equivalent cost function that we obtained is exactly We can optimize over the scale λ j > 0 so that a j → a j λ and b j → b j /λ, leading to 1 2n that is, where E is the empirical expectation over the data and dµ(a, b) = 1 m m j=1 δ (a j ,b j ) . Denoting dν(b) = adµ(a, b), we get the following const function with respect to ν: We thus get a specific 1 -penalty, where the difference with the variation norm of Bach [3], Kurkova and Sanguineti [31] is the presence of the data-dependent multiplier E x 2 2 (b x) 0 + E(b x) 2 + , rather than simply having a constant. With sufficiently many data points, these expectations are bounded from below and above, so the regularization properties are the same, with the same adaptivity to linear substructures highlighted by Chizat and Bach [9].
Let us denote the noise with ε = (E 1 , E 2 , . . . , E M ). Let us now compute, where C i depends on W M , . . . , W 1 and E M , . . . , E 1 . It is easy to check that E[Φ(w + σε)] = Φ(w). To show that R σ explodes we will show that Φ(w + σε) 2 F explodes. Because of independence of E 1 , . . . E M , we have Consider the term In the above we used the fact that . . E 1 X 2 F diverges and hence R σ explodes as well. Using the same argument, we can show that all coefficients σ 2i for all i > 1 explode.

E.1.2 ReLU Network
Consider a deep neural network with w = (W 1 , , . . . , , where C i depends on W M , . . . , W 1 and E M , . . . , E 1 . Using similar argument as for linear network, Let us again consider a special case and assume that w = (W M , . . . , W 1 ) are such that W 1 X > 0 at all entries and W 2 , . . . , W M has all positive entries. In such scenario, for small enough σ F diverges and hence R σ explodes as well. We can use similar constructions to show that all coefficients σ 2i for i > 1 explode.

E.2 Layer-wise perturbation
In this section, we will show that how layer wise perturbations leads to the desired result. We then proceed to show that the term is not exploding.
The perturbation argument follows exactly the same line as Section D.2, using that neural networks with ReLU activations or without activations are positively homogeneous with respect to each layer.
We thus simply need to show that the extra term is not exploding. For linear networks, the regularization term is and with scaling described in the paper, we get that each element of W M · · · W j+1 is the product of d M −1 · · · d j+1 terms, each of scale 3 , thus we an overall scale of Then, the Frobenius norm of W M · · · W j+1 is of order The reasoning is the same for W j−1 · · · W 1 X 2 F and leads to no explosion. With ReLU activation functions, since the derivative of the ReLU activation is either 0 or 1, this does not change the scalings.

F Further experimental details
We provide a thorough overview of the experimental results presented in this work. Some of the plots of the main paper are also presented again here for ease of comparison.
Datasets and networks. We use the Fashion MNIST [63] and CIFAR10 [29] datasets and train on different neural network models (6 experiments in total).
Setup. We repeat all experiments 3 times (different network initializations and injected noise) and show mean and 1 standard deviation. All experiments are conducted in PyTorch [44] on up to 8 Tesla V100 GPUs with 32 GB memory.
Noise injection. We perform noise injection in two different ways, as described in the main paper. In GD (SGD) +noise at each iteration we perturbe all the network weights with Gaussian noise with standard deviation σ/ √ M ,where M is the number of layers. Instead, in GD (SGD) +noise (layer), at each iteration, a specific layer 4 is picked and all weights are perturbed with Gaussian noise with standard deviation σ. As explained in the main text (see Section 3.2&4), we expect the layer-wise perturbation to provide a more stable approach for the minimization of the regularized loss, as width increases. In the results below, we show that this is indeed the case and provide detailed comparisons.

F.1 Experiments on Fashion MNIST MLPs
Batch-size, learning rate and noise injection strength. For the simulations on Fashion MNIST, we use a random subsample of the dataset (1024 samples), to introduce a sizable train-test gap. This also allows us to train with full-batch gradient descent on this subset. Performance of stochastic gradient descent (i.e. mini-batch case) is evaluated for CNNs in the next subsection. We selected for all experiments a sizeable learning rate of 5e − 3, except for the Deep and Wide case (MLP 4), where a smaller learning rate is necessary to avoid instabilities. Since we have no access to the problem Lipschitz constant, to allow methods to converge to potentially sharp regions, we use cosine annealing [36] for the learning rate. Regarding σ, we select the value that showcases best the implications of our theory: picking a value around 0.05 works in all settings. A plot showing the effect of tuning σ on both noise injection schemes can be found in Section 5 in the main paper. Test performance is evaluated on the full 10K testing dataset.
The final output is then processed using a log-softmax and signal is backpropagated using a cross-entropy loss. We run full-batch gradient descent on the 1024 datapoints (subset of the data) and train with learning rate 5e − 3 and σ = 5e − 2. Figure 5 shows that, since the network is not too wide, both the noise injection schemes are able to decrease the Hessian trace and improve test accuracy. Yet, interestingly, layer-wise noise injection outperforms standard noise injection in test accuracy. Fashion MNIST MLP 2 (Shallow Wide). The 784-dimensional input is processed with the following 4 wide layers with ReLU activations (except last layer) to an output with dimension 10: The final output is then processed as before, and we select a stepsize 5e − 3 and σ = 1e − 1. Figure 6 shows that, since the network is wide, only layer-wise injection provides a successful regularization. These findings are complemented by Figure 2 in the main paper.
The final output is then processed as before, and we select a stepsize 5e − 3 and σ = 1e − 1. Figure 7 shows that the behavior is similar to the shallow case ( Figure 5).   Fashion MNIST MLP 4 (Deep Wide). 784-dimensional input is processed with the following 6 wide layers with ReLU activations (except last layer) to an output with dimension 10: 784 → 5000 → 5000 → 5000 → 5000 → 5000 → 10.
The final output is then processed as before, and we select a stepsize 1e − 3 and σ = 5e − 2. Figure 8 shows that the behavior is similar to the narrow case ( Figure 6): as the width increases, only layer-wise injection provides an improvement in test accuracy, while standard noise injection hurts convergence at the same value of σ (scaled properly).

F.2 Experiments on CIFAR10 CNNs
Batch-size and learning rate, noise injection strength. For the simulations on CIFAR10, we use the full training dataset (50K samples) and train with SGD with batch-size 1024 and cosine annealing on a tuned learning rate. σ is picked to be 0.05 in all settings and layer-wise noise injection is performed with √ M scaling compared to the standard case, where M is the number of parameter groups in the network. Test performance is evaluated on the full 10K testing dataset.
Backpropagated gradients are computed using a cross-entropy loss. For this network, we train with SGD with batch-size 1024, using a stepsize of 1e − 3 with cosine annealing. We select here σ = 5e − 2. In Figure 9 we see that, while the test performance of SGD with batch size 1024 degrades overtime (known effect of linear layers), the performance of all noise injection schemes leads to better and stable generalization. This is reflected in the regularized Hessian trace. We note that here the performances of the noise injection methods are comparable since the network is not very wide.
For this network, we train with SGD with batch-size 1024, using a stepsize of 5e − 3 with cosine annealing. We select here σ = 5e − 2. Figure 10 shows that, in contrast to the toy narrow CNN we inspected above, here layer-wise noise injection provides an improved performance in terms of test loss over standard noise injection. Yet, compared to the MLP case, here injecting noise to all weights does not lead to a quick performance degradation -to observe this, one has to design a network with unrealistically big number of channels. Regarding the Hessian trace, we observe that injecting noise dampens the oscillations in the dynamics of this quantity, which is in line with our result on minimization of a regularized loss (see Section 3.2), even though this was derived in the MLP case.