On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implications
Authors: Ziqiao Wang
Yongyi Mao
Venue: ICLR 2022 Poster (2022)
Keywords: deep learning
generalization
information theory
learning bound
regularization

Abstract: This paper follows up on a recent work of Neu et al. (2021) and presents some new information-theoretic upper bounds for the generalization error of machine learning models, such as neural networks, trained with SGD. We apply these bounds to analyzing the generalization behaviour of linear and two-layer ReLU networks. Experimental study of these bounds provide some insights on the SGD training of neural networks. They also point to a new and simple regularization scheme which we show performs comparably to the current state of the art. 

Published as a conference paper at ICLR 2022
ON THE GENERALIZATION OF MODELS TRAINED WITH SGD: IITORMATION-THEORRTT BOUNDS AND
IMPLICATIONS
Ziqiao Wang
Yongyi Mao
University of Ottawa
University of Ottawa
zwang28 6 soottwaaa ca
ymao@uortawa.co ca
ABSTRACT
This paper follows up on a recent work Neu al. (2021) and presents some new informatiion-therretii upper bounds for the generalization enror of machine learn- ing models, such as neural networks, trained with SGD. We apply these bounds analyzing the generalization behaviour of linear and two-layer ReLU networks. Experimental study of these bounds provide some insights on the SGD training of neural networks. They also point to a new and simple regularization scheme which we show performs comparably to the current state of the art.
INTRODUCTION
The observation that high capacity deep neural networks trained with mini-batched stochastic gra- dient descent, referred to SGD in this paper, tend generalize well (Zhang al., 2017) contradicts the classical wisdom in statistical learning theory (e.g.. Vapnik] (1998) ) and has stimulated intense research interest in understanding the generalization behaviour of modern neural networks.
In this direction, generalization bounds for over-parameterrized neural networks are obtained (Allen-
Zhu al. 2019 Bartlett et al. 2017 Neyshabur al., 2015; 2018a by Arora et al. 2018 2019) and
a curious "double descent" phenomenon is observed and analyzed (Belkin et al. 2019 Nakkiran
al., 2019 Yang al., 2020). Built on a connection between stability and generalization (Bousquet
& Elisseeff 2002), a stability-based bound is first presented in Hardt et al. (2016). followed by
surge research effort exploiting similar approaches (London 2017 et al.) 2018 Feldman &
Vondrak 2019 Lei & Ying. 2020; [assily et al., 2020). In Informatiin-tteerrtiic bounding techniques
established recently (Russo Zou 2016 2019] 9 Xu Raginsky 2017 Asadi et al., 2018
8) Bu al,
2020 Steinke & Zakynthinou 2020: Dwork al. 2015 Bassily et al. 2018 Asadi & Abbe 2020
Hafez-Kolahi et al. aal.|2020) Zhou et al. (020) have also demonstrated great power in analyzing SGD- like algorithms. For example, Pensia al. (2018) is the first to utilize information-theerrtiee bound in analyzing the generalization ability of SGLD (Gelfand & Mitter 1991] Welling & Teh 2011).
The bound was subsquently improved by Negrea et al. (2019): Haghifan higm al. (2020); Rodriguez-
Gálvez et al. (2020); Wang et al. (2021b). Inspired by the work of Pensia et al. (2018), Neu et al.
(202l) presents an cormationntheoreee
analysis of the models trained with SGD. The analysis of Neu et al. (202T) constructs an auxiliary weight process parallel to SGD training and upper-bounde
the generalization error through this auxiliary process.
Another line of research connects the generalization of neural networks with the flatness of loss minima (Hochreiter & Schmidhuber 1997) found by SGD or variant (Keskar et al. 2017 Dinh et al., 2017. Dziugaite & Roy 2017 Neyshabur et al. 2017: Chaudhari et al. 2017 Jastrzebski cct al. 2017 Jiang et al.) 2019 Zheng et al., 2021: Foret et al. 2020). This understanding has led to the discovery of new SGD-based training algorithms for improved generalization. For example, in a concurrent development by Zheng et al. (2021) and Foret et al. (2000). a local "max-poolinne operation is applied to the loss landscape prior to the SGD updates. This approach, referred to as AMP (Zheng et al. 202T) or SAM (Foret et al.) 2020), is shown to make SGD favor flatter minima and achieve the state-of-the-ant performance among various competitive regularization schemes.

---

Published as a conference paper at ICLR 2022
In this paper, we focus investigating the generalization of machine learning models trained with SGD. Although we are primarily motivated by the curiosity to understanding neural networks, the results of this paper in fact apply broadly to any model trained with SGD.
This work follows the same construction of the auxiliary weight process in Neu et al. (002)) and develops upper bounds of generalization error that extend the work of Neu al. (2021) Like those
in Neu et al. (022)) the bounds we obtain can be decomposed into two terms, one measuring the impact of training trajectories ("the trajectory term") and the other measuring the impact of the
flatness of the found solution ("the flatness tern""). ). Having an identical flatness term as that in Neu al. (202T), empirical evidence hints that our bounds have a improved trajectory term. Figure shows an experimental comparison of the trajectory term in our bound (Theorem 2 with that in the bound in Neu et al. (202T) (re-stated as Lemma 2 in this paper) for two neural network models. The trajectory terms are compared in deterministic setting for two different values of a (the variance parameter of the noise in the auxiliary weight process, details given in appropriate context and in Appendix E.2).
The trajectory term in the bounds of Neu et al. (202 accumulates two terms over training steps: local gradient sensitivity, measuring the sensitivity of the SGD gradient signal to weight perturba- tions, and gradient dispersion f measuring the extent to which the gradient signal spreads around its mean. Usually gradient dispersion vanishes with training iterations but local gradient sensitivity does not. Our improvement over Neu et al.] (202T) is achieved by removing the local sensitivity term and involving the logarithmic of revised gradient dispersion. Although
new definition
of gradient dispersion is in general larger than that in Neu et al. (2021), as long as the number of
iterations is not too small, the fact that our gradient dispersion also vanishes with training allows our bounds to be tighter than Neu et al. (202T).
4000
(a) 10 (MNIST)
(b)
10 (MNIST) (c) 10 (CIFARIO) (d) 10 (CIFARIO)
Figure 1: Comparison of the trajectory term between our bound (Theorem 2 and the bound in Neu
al. 202T). (a)(b) MI. trained on MNIST. (c)(d) CNN trained on CIFAR-10
We also provide an application of our bounds in analyzing the generalization behaviour of linear and two-layer ReLU networks, where we show that the activation state in ReLU networks plays an important role in generalization.
It is remarkable that removing the local gradient sensitivity term makes our bound have a simple closed form (after optimizing the noise variances), much easier evaluate. We empirically validate the derived bounds, and provide various insights pertaining to the generalization behavior of models trained with SGD. For example, gradient dispersion is seen to reveal a double descent phenomenon with respect to training epochs, where the valley in the double descent curve appears to mark the great divide between the "generalization regime" and the "memorization regime" of training. Fur- thering from this observation, also show that it is possible to reduce the memorization effect by dynamically clipping the gradient and reducing its dispersion.
Our bounds also inspire natural and simple solution to alleviate generalization error. Specifically, we propose a new training scheme, referred to as Gaussian model perturbation (GMP), aiming at reducing the flatness term of the bounds. This scheme effectively applies local "average pooling" to the empirical risk surface prior to SGD, greatly resembling the "max-pooling" approach adopted in AMP (Zheng et al. 202T). We demonstrate experimentally that GMP achieves competitive performance with the current art of regularization schemes.
We note this term is correlated with flatness rather than precisely measures the flatness.
TThe quantity is often referred to as gradient variance in the literature, but we prefer "dispersion" to "vari- ance" so better comply with the mathematical conventions and avoid possible confusion.
2

---

Published as a conference paper at ICLR 2022
Proofs, additional discussions and experimental results are presented in Appendices.
Other Related I Literature Gradient dispersion is mostly studied from optimization perspectives (Bottou et al. 2018: |Roux etal. 2012 Johnsonnn & Zhang 2013 Wen et al., (2020) |aahri et al. 2020). Prior to this work, only a few works relate gradient dispersion with the generalization behaviour of the networks. In Neu et al. (202T) and Wang et al. (2021b), gradient dispersion also appears in the generalization bounds. and there are limited studies characterizing the generalization performance and the gradient variance. Particularly, in Jiang al. (2019), gradient dispersion argued to capture a notion of "flatness" of the local minima of the loss landscape, thereby correlating with general- ization. Injecting noise in the training process has been proposed various regularization schemes (Bishop] 1995; Camuto et al.) 2020 2021 Srivastava et al. [014] Wei et al.. (020). But unlike GMP derived in this paper, where noise is injected to the model parameters, noise in those schemes is injected either to the training data or to the network activation. In addition, noise also be im- plicitly injected during training, for example, by adjusting the momentum terms Xie et al. (021bb). The training objective in Xie al. (2021a) is similar to GMP but their NVRM-SGI minimizes a region directly while our GMP considers a trade-off between the empirical loss and the flatness term. Gradient clipping is common technique for preventing gradient exploding (see, e.g., S..,Myeity et al. (2018); Peters et al. (2018)). This technique is also used in ZZang et al.] (2019) to accelerate training. In this paper, gradient clipping is used to investigate and control the impact of gradient dispersion on generalization error.
2 PRELIMINARIES
Population Risk, Empirical Risk and Generalization Error Unless otherwise noted, a random variable will be denoted by capitalized letter (e.g., Z), and its realization denoted by the corre- sponding lower-case letter (e.g. 2). Let Z be the instance space of interest and be an unknown distribution 2, specifying random variable Z. Let W C Rd be the space of hypotheses. Suppose that a training sample S (Z1. Zz.... Zn) is drawn i.i.d. from μ and that stochastic learning algorithm A takes S its input and outputs a hypothesis W W according to some conditional distribution Pwis mapping Z" to W. Let é; W x Z - R be loss function, where E(w, 2) mea- sures the "unfitness" or "error" of any E 2 with respect to hypothesis w E W. The population risk, for any w E W, is defined as
(w) Ez [l( Z)]-
The goal of learning is find hypothesis w that minimizes the population risk. But since μ is only partially accessible via the sample S, in practice, we instead turn to the empirical risk, defined as
Ls(w)= Σ llw, Zt).
1=1
The expected generalization error of the learning algorithm AA is then defined as
gen, Pw s) A Ew.s(L,.(W) Ls(W)),
where the expectation is taken over the joint distribution of (S, W') (i.e., n²" & Pwis).
Throughout this paper, we take é as a continuous function (adopting the usual notion "surrogate loss" (Shalev-Shwartz & Ben-David] 2014)) Additionally, we assume that e is differentiable almost everywhere with respect to both w and z. Furthermore we assume that E(w, Z) is R-subgaussiar for any E W. Note that a bounded loss is guaranteed to be subgaussian. Let 7(X; Y') denote the mutual information (Cover & Thomas 2012) between any pair of random variables (X,Y) The following result is known.
Lemma (Xu & Raginsky 2017
Theorem 1.)). Assume the loss Elw, 2) is R-subgaussian for any E W. The generalization error of A is bounded by
2R
[gen(u, Pwis)) S
I(W;S),
n
'A random variable X is R-subgaussian if for any p. log Eexp (x (X-E)) s R²
3

---

Published as a conference paper at ICLR 2022
Stochastic Gradient Descent We now restrict the learning algorithm A to be the mini- SGD algorithm for empirical risk minimization. For each training epoch, the dataset S is randomly split into disjoint mini-batches, each having size b, namely, n mb. Based each batch, one parameter update is performed. Specifically, let B, denote the batch used for the 7th update. Define
g(u, B.)
=EB.
namely, g(w, B₂) is the average gradient computed for the batch B, with respect to parameter w. The rule for the bth parameter update is then
We & W,-1 - Aeg(W--,,B))
where ) is the learning rate at the step 6. The initial parameter setting Wo is assumed to be drawn from the zero-mean spherical Gaussian (0, oğTa) with variance of in each dimension. We will as- sume that the SGD algorithm stops after T updates and outputs WT as the learned model parameter.
Given the training sample S. let govern the randomness in the sequence (B1, B2...., BT) of batches. For the simplicity of notion, we will fix the configuration of द. That is, we will assume a fixed "batching trajectory", into m batches in each epoch. The presented generalization bounds of this paper can be extended to the case where the batching trajectory is uniformly random (as set up above). This merely involves averaging over all batching trajectories or taking expectation over Ç.
fixed way to shuffle the example indices {l,.... ..,...,. n2 and divide them
Auxiliary Weight Process We now associate with the SGD algorithm an auxiliary weight process (W)). Let o,, ..,,.,, By be a sequence of positive real numbers. Define
Wo Wo. and W. & W Wg B,) + No. for
where No o(0,ofLa is Gaussian noise. The relationship between this auxiliary weight process (We) and the weight process {W,} in SGD shown in the Bayesian network below.
N1
N2
Nr
Nr
1
1
W.
Wi
W2
Wr-1
Wr
W
Wi
W2
WT-1
Wr
Let A, E' N,. Noting that the weight updates in (W,) uses the same gradient signal as that used in (We) (which depends on Wi-1 not W,-1), it is immediate that W. W, + A.. Note that this auxiliary process follows the same construction as Neu et al. (202I), which we will use to study the generalization error of SGD. To that end, let's define gradient dispersion by
(e(w) A [1, (w, B.) E [ (W, 2
where the inside expectation is taken over (W, Z) μ 3 Pwiz- For a given sample s E 2", define
rw, 8) E (w Ar) T., (w)
where the expectation is taken over AT and Lg (w) is the empirical risk of at parameter
In the remainder of the paper, let S' denote another sample drawn from μ², independent of all other
random variables. The main generalization bound in Neu et al. (2021) is re-stated below.
Lemma 2 ((Neu et al. 2021 Theorem 1.)). The generalization error of SGD is upper bounded by
2R n
X2 (WW + + Eb - (Wr,
[gen(H, Pwr,1s) s
where V (w,-1) 3 E LE (V mu (w 2) - (. 51 ~1(, ~ oa and
V. (w)) A E []]g(w, B₂) E (w, -)]1[]
4

---

Published as a conference paper at ICLR 2022
The term (ww-1) in the bound is referred as "local gradient sensitivity" in Neu al. 2021
Note that the inside expectation of V (w) is taken over Z ~ yu instead of (W; μ Pwiz. 2. Thus, (w)) is in general not worse than our gradient dispersion (w) for fixed (see Figure (d) in Appendix(E.2] However, the difference between these two terms is very small when W close to local minima due to the tiny gradient norm. In addition, the definition of our gradient dispersion is
implicitly used in a bound in Section 5.2 of Neu et al. (202I), which can be regarded as a weaker version of Eq. 2 in our Theorem
3 NEW GENERALIZATION BOUNDS FOR SGD
Removal the local sensitivity term (w;-1) requires invoking a special instance of the HWI inequality (Raginsky & Sason 2018 Lemma 3.4.2), which we first state.
Lemma 3. Let and be two random vectors in Rd, and let
NN(O,I)) Ia) be independent of (X,Y) Y) Then, for t.y > 0, DKL(Px+van Mex.ViNNlPPytt PY+VEN) I 1 E ||| - Y + where DKL is the KL divergence.
+ (log + -1),
2
Note that Neu al. (2021) also makes uses of a similar lemma in their revision. However, the development in Neu et al. (021) requires constructing a ghost auxiliary weight process in which an independent noise perturbation A, is introduced. Due the mismatch between D, and A, the local gradient sensitivity term Vi (W,,1) appears in their bound. In this paper, we waive this A by using the following lemma.
Lemma 4. Let random variables X,Y and A be independent of N ~ I(),I)). Then for any O, any had-valued function f. and any random variable E Rd that is a function of Y, we have
d 2 log IE [[] + +, 2112
+1 +1) )
I(f(Y + A,X) oN;
2
Note that the outside expectation is taken over Y and the inside expectation is taken over (X, A). Then, exploiting Lemma 4 by letting X S. W and f2 E [g A, Z)] &
S.Y
[VE( - A, 2)] will enable us to have the bound below.
Theorem 1. The generalization error of SGD is upper bounded by
R T
+ +1)] +1 ( A (W,-1,B) B,) E [9 (.) 2)11 do?
E
log
This bound is strictly tighter than the bound in Lemma In fact, from Theorem one can recover Lemma 2 with smaller constant factor (see Appendix C.3 for more details).
To completely remove ((w,-)) and to obtain a closed form of the optimal bound, we will let Ω E (W, Z)}, then Lemma 4 gives independent of the distribution of A.
crisp way to have the following upper bound that is
(A do?
+ +1).
Lemma Let G2 -Agg(W (W Bi). Then, NG < d
In this lemma, the mutual information / IG,+NN, W.-1) roughly indicates the degree by which the SGD's updating signal G, (smoothed with noise) depends the training sample when B, is used for computing the gradient. When this dependency is strong (giving rise to high value of the mutual information), the model conceivably tends overfit the training sample. This lemma suggests that the strength of this dependency can be upper-bounded by the expected gradient dispersion at the current weight configuration. In our experiments, we will estimate the expected gradient dispersion and validate this intuition.
We are now in position to state our main theorem. Theorem 2. The generalization error of SGD is upper bounded by
R
X (W, 1)] +1) + 1BBhWWr -W (')] (2)
gen(u,, Pwr1s)l <
log
do?
5

---

Published as a conference paper at ICLR 2022
Further, assume L (ww) I Ea [,,( Ar)), l is twice differentiable, and of is independent of t. Denote by Hwr the Hessian of the loss with respect to Wr and let Tr(-) denote trace. Then
3
R
gen(p, Pwr(s) 2
Σ
B(V.(W-)))BB [Tr (Hw, (2))1
(3)
Remark 1. With a single draw of S and under the deterministic setting (i.e., with fixed weight initialization and batching trajectory), removing (Wi11) will make the bound much tighter as shown in Figure 1 This remarkable improvement should come at no surprise, since V (W,,1) monotonically increases with training epochs (noting that (W, has the cumulative variance E' La while (W(1) appears decreasing (see Figure Bap. Figure [ also indicates that if the noise variance oe is made small, one expects the gradient dispersion to dominate the trajectory term in Lemma 2 However, the factor 1/0, will become too large, make the bound loose. More discussions about the stochastic setting with multiple draws of S are deferred to Appendix E2.
Remark 2. The condition L (WT) S Esy [Ly(WT + AT]] indicates that the perturbation does not decrease the population risk. This is also assumed in Foret el al. (2020) in the derivation of JAC-Bayesian generulization bound.
In the bound of 2 the first term captures the impact of the training trajectory ("trajectory term"), and the second term captures the impact of the final solution, which in fact measures the flatness for the loss landscape at the found solution ("flatness term"). The learning rate in SGD has explicitly appeared in the trajectory term of 3 From the way it appears in the bound, one may be tempted to assert that small learning rate will improve generalization. This would then contradict some previous observations @Jsttzebski et al. 2017 Wu et al. 2018 He et al., 2019). in which large learning rate will benefit generalization. In addition, the bound also suggests that the batch size has some direct impact on the trajectory term through gradient dispersion. We investigate this by performing experiments with varying learning rates and batch sizes (see Figure in Appendix (.3). As seen in the experiments, increasing the learning rate impacts the trajectory term and the flatness term in opposite ways, i.e. making one increase and the other decrease. similar (but reverted) behaviour is also observed with batch sizes. This makes the generalization bound in Eq 3 have rather complex relationship with the settings of learning rate and batch size.
follows from Eq by minimizing the bound over a. The bound in Eq Iq is thus independent of a choice of o,'s 's and can be computed easily and efficiently.
To summarize, we remark that these bounds suggest that in order for the model to generalize well, both the trajectory term and the flatness term need to be small - the former involves the learning rate with the gradient dispersion along the training trajectory, whereas the latter depends on the flatness of the empirical risk surface at the found solution.
APPLICATION IN LINEAR NETWORKS AND TWO-LAYER RELU NETWORKS.
We now apply Theorem to two neural network models in a regression setting. Let Z = (X, with X e d and Y K. Assume ||||| 1. We use SGD train a model f(W.-) : RR IR and define the loss as E(W, 2) = 1/2(Y f(W. The bounds below are both in the form of the product of the flatness term and the trajectory term.
Theorem 3 (Linear Networks). Let the model be a linear network, i.e. f(W.X) = WT X, then
gen(u, Pwr]s)= S 3 (ET
A²A2T 4n
I [e(W>-1,))))
1==
Theorem 4 (Two-Layer ReLU Networks). Following Arora et al. (2019). consider
Von Em= A, ReL X) where m is the width of the neural network, A, unif( -13) and
ReLU(-) is the ReLU activation. We only train the first layer parameters W = [W1, Wz,.. Wm. e
Rd xm and fix the second layer parameters A [A,, A2....... Am) E Rmm during training. Then.
gen(u, Pwr|s) 5
E
L YT
Σ t=
T
Rd
XTT E
Σ
Unatt e(W ((W.1.22) 2)
4n

---

Published as a conference paper at ICLR 2022
where Ir,5, I(W 0} and I1 is the indicator function.
Compared with Theorem 3 we notice that in the two-layer ReLU network, the ReLU activation state along the training trajectory plays key role in the bound of Theorem 4 Specifically, the weights of the deactivated neurons do not contribute to the bound of Theorem 4 making the bound not explicitly depend on the model dimension d. This result also suggests that sparsely activated ReLU networks are expected to generalize better. Despite various empirical evidence pointing to this behaviour (see, c.g., Glorot al. (20TT). the best of our knowledge, this theorem provides the first theoretical justification in this regard.
The comparison between these bounds and the dynamics of generalization gap is deferred to Ap- pendix EE.4 In the remainder of this paper, we will study more complex network architectures beyond the linear and two-layer ReLU networks and implications of our bounds those settings.
EXPERIMENTAL STUDY
Bound Verification We first verify our bound of Eq [gBip Theorem by training MLP (with one hidden layer) and an AlexNet (Krizhevsky ct al. (012) on MNIST and CIFARIO (Krizhessky 2009). respectively. To simplify estimation, we fix the weight initialization and set o and X to be constants a and X, respectively. To compute Σ E [Vr(W,-))], we compute the gradient dispersion as its empirical estimate from batch, utilizing PyTorch (Paszke et al. 2019) library BackPack (Dageel et al. 2020). To compute Tr (E [Hw, (Z))), we use the PyHessian library (Yao al. 2020) to compute the Hessian.
We perform experiments with varying network width and varying levels of label noise. Specifically, noise level refers the setting where replace the labels of fraction of the training and testing instances with random labels. The estimated bound is compared against the true generalization gap, namely, the difference between the training loss and testing loss, and is shown in Figure 2
MLP on MNIST
(b) AlexNet CIFARIO
(c) MLP on MNIST
(d) AlexNet CIFARIO
Figure 2: Estimated bound and empirical generalization gap ("gap") as functions of network width
((a) and (b)) and label noise level ((c) and (d)). Note that Y-axis is in log scale.
In Figure 2 we see that in all cases the estimated bound follows closely the trend of the true gen- cralization gap. The fact that the bound curve consistently tracks the gap curve under various label noise levels indicates that our bound very well captures the changes of the data distribution. Note that in Figure 2 (a) and (b), our bound decays with the increase of the model size, showing a trend as opposite to the bounds obtained in classical learning theory. But such trend clearly better explains the generalization behaviour of modern neural networks.
Epoch-wise Double Descent of Gradient Dispersion We experimentally investigate the impact of gradient dispersion on the training of the neural networks by fixing the learning rate, batch size and weight initialization for the each model (MLP for MNIST, AlexNet for CIFARIO). For each model and various label noise levels, we plot in Figure 3 the evolution of the (empirical) gradient dispersion (e(w-11), training accuracy and testing accuracy across training epochs.
An intriguing epoch-wise "double descent" phenomenon is observed, particularly when the labels are noisy. According to the double descent curve, the training may be split into three phases (e.g.. Figure 3 (h)). In the first phase, the gradient dispersion rapidly descends and maintains a very low level. In this phase, both training and test accuracies increase while maintaining very small generalization gap. This suggests that the network in this phase is extracting useful patterns and generalizes well. In the second phase, the gradient dispersion starts increasing until it reaches
7

---

Published as a conference paper at ICLR 2022
peak value. In this phase, the training and testing accuracies gradually diverge, marking the model entering an overfitting or "memorization" regime- when the data contains the noisy labels, the network mostly tries to memorize the labels in the training set. In the third phase, the gradient dispersion descends again, reaching low value. In this phase, the model continuously overfits the training data, until the training and testing curves reach their respective maximum and minimum. It appears that the timing of the three phases depends on the dataset and the label noise level. For simpler data (e.g. MNIST) and cleaner datasets the first phase may shorter. This is arguably because in these datasets, extracting useful patterns is relatively easier. Nonetheless, the valley in the double-descent curve appears mark "great divide" between generalization and memorization.
8
Adc.
Dly
noise=0 (MNIST)
(b) noise=0.2 (MNIST)
(c) noose=00.4 (MNIST)
noise=0.6 (MNIST)
(e) noise=0 (CIFARIO)
(I) noise=0.2 (CIFARIO) (g) noise=0.4 (CIFARIO) (h) n.6 (CIFARIO)
Figure 3: Dynamics of gradient dispersion, in relation to training/testing accuracies.
Dynamic Gradient Clipping Inspired by our generalization bounds and above observations, one way reduce the generalization error is to control the trajectory of the bounds by reducing the gradient dispersion in each training step. Here we investigate simple scheme that dynamically clips the gradient norm so to reduce the gradient dispersion. Specifically, whenever the current gradient norm is larger than the gradient norm K steps earlier, or [l9(W,, B.) > 1lg(W,,K, B,_ K lll (i.e., the model is expected to have entered the "memorization" regime), reduce the norm of the current gradient g(W, B₂) to fraction of g B k 12,, for some prescribed value a < 1.
The effectiveness of this scheme best demon- strated when the labels contain noise. As shown Figure 4 (and Figure in in Appendix (E.5) dy- namic gradient clipping significantly closes the gap between the training accuracy and the testing accuracy. The models trained with this scheme maintain a near-optimal testing accuracy (e.g.. about 80% when the label noise level of MNIST 0.2), without suffering from the severe memo- rization effect seen in models trained without this scheme. Further understanding of the double- descent phenomenon of the gradient dispersion may enable more delicate design of such dynamic clipping scheme and potentially lead to novel and powerful regularization techniques.
Tols for. clgggeg
willgiing
(a) noise=0.2 (MNIST)
(b) noise=0.4 (MNIST)
Figure 4: Dynamic Gradient Clipping.
A PRACTICAL IMPLICATION: GAUSSIAN MODEL PERTURBATION
The appearance of the flatness term in generalization bounds suggests that for empirical risk minimizer w" to generalize well, it is necessary that the empirical risk surface at w" is flat, insensitive small perturbation of w². This naturally motivates a training scheme using the
8

---

Published as a conference paper at ICLR 2022
following regularized loss:
min (u)) +
E (~,
[L(w + A) Lo(w)},
where p is a hypper-arameter Replacing the expectation above with its stochastic approximation using k realizations of A gives rise to the following optimization problem.
min Σ ZEB
(1 (1--Ah (1-p)e(w, 2) + PPR Σ (e(w + 8,,
We refer to the SGD training scheme using this loss as Gaussian model perturbation or GMP. No- tably, GMP requires & forward passes for every parameter update. Empirical evidence shows that a small k, for example, 3, already gives competitive performance. Implementing the k + forward passes on parallel processors further reduces the computation load.
We compare GMP with several ma- jor regularization schemes in the cur- rent art, including Dropout (Srivas-) tava al. 2014), label smoothing (L.S.) (Szegedy et al. (0166. Flood-
Method
SVHN
CIFAR-10
CIFAR-100
ERM
96.66=0.000
93.68=0.193
72.16+0.297
Dropout
97.04=0.049
93.78=0.147
72.28=00337
L. S.
96.93110070
93.71=0.158
72.5110.179
ing (Ishida et al. (020). MixUp
Flooding
96.85-10.085
0..74
72.07+10.21
(Zanng et al.] 2018), adversarial
MixUp
96.91=0.057
94.52-0.112
73.19:0.254
training (Adv. Tr.) (Goodfellow
Adv. Tr.
97.06=10.09
93.31=0.130
70.88=0.145
et al. 2015). and AMP (Zheng et al.
AMP
97.27
9..35
74.40+0.168
202Ip. We will also include ERM as the baseline, where no regular- ization method applied. The com- pared schemes are evaluated three popular benchmark image classifica- tion datasets SVHN (Netzer al.) 2011). CIFAR-10 and CIFAR-100 Krizhevsky 2009). Two represen- tative deep architectures VGG16 (Si- monyan & Zisserman, (2035) and Pre-
GMP
97.18+0.057
94.33=0.094
74.45+0.256
GMP
97.09-10.068
94.45-10.18
75.09.10.285
Table 1: Top-1 classification accuracy acc.(%) of VGG16. We run experiments 10 times and report the mean and the standard deviation of the testing accuracy. Superscript de- notes the number of sampled Gaussian noises during train- ing.
ActResNet18 (He et al.] 2016) are taken as the underlying model. We train the models for 200 epochs by SGD. The learning rate is initialized as 0.1 and divided by 10 after 100 and 150 epochs. For all compared models, the batch size is set to 50 and weight decay set to 10-4. For GMP, we choose p 0.5 and set the standard deviation of the Gaussian noise A to 0.03. The value of k: chosen as 3 and 10 respectively (referred to as GMP and GMP
The performances of all compared schemes are given in Table (and the results of PreActResNet118 are shown in Appendix E.7 For the compared regularization schemes except GMP, we directly report their performances as given in Zheng al.) (202T). Table T demonstrates the effectiveness of GMP. Overall GMP performs comparably to the current art of regularization schemes, although appearing slighly inferior to the most recent record given by AMP on SVHN and MixUp on CIFAR- 10, respectively (Zheng et al., (021). Noting that the key ingredient of AMP, "max-pooling" in the parameter space, greatly resembles regularization term in GMP, which may be seen as "average- pooling" in the same space.
7 CONCLUSION AND OUTLOOK
This paper presents new information theoretic generalization bounds for models (e.g., linear net- works and two-layer ReLU neural networks) trained with SGD. Our bounds naturally point to new and effective regularization schemes. At the same time, our bounds and experimental study reveal interesting phenomena in the SGD training neural networks. There are yet promising directions for further improving these bounds, for example, via exploiting conditional mutual information bounds (Haghifam et al. (2020)), strong data processing inequalities (Wang et al. (2021a)), and the relationship between between the trajectory term and the flatness term.

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
This work supported partl by an NSERC Discovery Grant and Artificial Intelligence for Design Challenge program of National Research Council Canada. The authors would like to sincerely thank Gergely Neu and Borja Rodríguez- Gálvez for pointing out errors in the previous version of this paper. The authors would also like to thank Maia Fraser for stimulating discussions.
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. International Conference on Machine Learning, pp. 242-252. PMLR, 2019.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In International Conference on Machine Learning, pp- 254-263. PMLR, 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of op- timization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332. PMLR, 2019.
Amir R Asadi and Emmanuel Abbe. Chaining meets chain rule: Multilevel entropic regularization and training of neural networks. Journal of Machine Learning Research, 21(139):1-32, 2020.
Amir R Asadi, Emmanuel Abbe, and Sergio Verdú. Chaining mutual information and tightening generalization bounds. Proceedings of the 32nd International Conference on Neural Informa- fion Processing Systems, pp. 7245-7254 2018
Peter L Bartlett, Dylan Foster, and Matus Telgarsky. neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 6241 -6250, 2017.
normalized margin bounds for
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. Learners that use little information. In Algoritmmic Learning Theory. pp. 25-55. PMLR, 2018.
Raef Bassily, Vitaly Feldman, Cristóbal Guzmán, and Kunal Talwar. Stability of stochastic gradient descent nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical varianar trade-off. Proceedings of the National Academy of Sciences, 116(32):1549--1555 2019.
Chris M Bishop. Training with noise is equivalent to tikhonov regularization. Neural computation, 7(1):108-11 116, 1995.
Léon Bottou, Frank Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
Olivier Bousquet and André Elisseeff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499-526 526, 2002.
Yuheng Bu, Shaofeng Zou, and Venugopal V Veeravalli. Tightening mutual information-based bounds on generalization error. IEEE Journal on Selected Areas in Information Theory, 1(1): 121-130, 2020.
Alexander Camuto, Matthew Willetts, Umut Simsekli, Stephen Roberts, and Chris C. Holmes. Explicit regularisation in gaussian noise injections. In Advances in Neural Information Processing Systems, 2020.
Alexander Camuto, Xiaoyu Wang, Lingjiong Zhu, Chris Holmes, Mert Gürbüzbalaban, and Umut Şimşekli. Asymmetric heavy tails and implicit bias in gaussian noise injections. arXiv preprint arXiv:2102. 07006, 2021.
10

---

Published as a conference paper at ICLR 2022
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer T. Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gra- dient descent into wide valleys. In 5th International Conference Learning Representations. OpenReview.net, 2017.
Yuansi Chen, Chi Jin, and Bin Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint arXiv: 1804.0164 2018.
Thomas M Cover and Joy A Thomas. Elements of Information Theory. John Wiley & Sons, 2012.
Felix Dangel, Frederik Kunstner, and Philipp Hennig. Backpack: Packing more into backprop. In 8th International Conference Learning Representations. OpenReview.net, 2020.
Laurent Dinh, Razvan Pascanu, Samy Bengio, and Yoshua Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning, pp. 1019-1028. PMLR, 2017.
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth. Generalization in adaptive data analysis and holdout reuse. In Proceedings of the 28th Interna- tional Conference on Neural Information Processing Systems- Systems-Volume 2, pp. 2350-2355555 2015.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the 33rd Annual Conference on Uncertainty Artificial Intelligence (UAI), 2017.
Fartash Faghri, David Duvenaud, David Fleet, and Jimmy Ba. study gradient variance in deep learning. arXiv preprini 2rXiv:2007.04552, 2020.
Vitaly Feldman and Jan Vondrak. High probability generalization bounds for uniformly stable al- gorithms with nearly optimal rate. In Conference on Learning Theory, pp. 1270-1279. PMLR, 2019.
Pierre Foret, Ariel Kleiner, Hossein Mobahi, and Behnam Neyshabur, Sharpness-aware minimiza- tion for efficiently improving generalization. arXiv preprint arXiv:2010.01412, 2020.
Saul B Gelfand and Sanjoy K. Mitter. Recursive stochastic algorithms for global optimization in r'd. SIAM Journal on Control and Optimization, 29(5):999-1018 1991.
Xavier Glorot, Antoine Bordes, and Yoshua Bengio. Deep sparse rectifier neural networks. In 14th International Conference Artificial Intelligence and Statistics, volume 15, pp. 315-323, 2011.
Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversarial examples. In 3rd International Conference on Learning Representations, ICLR, 2015.
Dongning Guo, Shlomo Shamai, and Sergio Verdú. Mutual information and minimum mean-square error in gaussian channels. IEEE transactions on information theory, 5164):1211-128,, 2005.
Hassan Halcz-Kolahi, Zeinab Golgooni, Shohreh Kasaci, and Mahdich Soleymani. Conditioning and processing: Techniques improve information-theorettee generalization bounds. Advances in Neural Information Processing Systems, 33, 2020.
Mahdi Haghifam, Jeffrey Negrea, Ashish Khisti, Daniel M Roy, and Gintare Karolina Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. arXiv preprint Siti:20004129882 2020.
Moritz Hardt, Ben Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pp. 1225-1234, PMLR, 2016.
Fengxiang He, Tongliang Liu, and Dacheng Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems 32, pp. 1141-1150, 2019.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Identity mappings in deep residual networks. In European Conference Computer Vision, pp. 630-645, 2016.

---

Published as a conference paper at ICLR 2022
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural Computation, 9(1): 1997.
Takashi Ishida, Ikko Yamane, Tomoya Sakai, Gang Niu, and Masashi Sugiyama. Do we need zero training loss after achieving zero training error? In Proceedings of the 37th International Conference on Machine Learning, ICML, 2020.
Stanislaw Jastrzebski, Zachary Kenton, Devansh Arpit, Nicolas Ballas, Asja Fischer, Yoshua Bengio, and Amos Storkey. Three factors influencing minima in sgd. arXiv preprint arXiv:1711.04623, 2017.
Yiding Jiang. Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantas- tic generalization measures and where find them. In International Conference on Learning Representations, 2019.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-3233 2013.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- ter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In 5th International Conference on Learning Representations. OpenReview.net, 2017.
Alex Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep con- volutional neural networks. Advances in neural information processing systems, 25:1097-1105, 2012.
Yunwen Lei and Yiming Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. In International Conference on Machine Learning, pp. 5809-5819. PMLR, 2020.
Ben London. A pac-bayesian analysis of randomized learning with application stochastic gradient descent. In Proceedings of the I International Conference on Neural Information Processing Systems, pp. 2935-2944, 2017.
Stephen Merity, Nitish Shirish Keskar, and Richard Socher. Regularizing and optimizing Istm lan- guage models. In International Conference on Learning Representations. 2018.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. In International Conference on Learn- ing Representations, 2019.
Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, and Daniel M Roy. ceemmation-theorette generalization bounds for sgld via detendeennd estimates. In Advances in Neural Information Processing Systems, pp. 11013-11023, 2019.
Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Read- ing digits in natural images with unsupervised feature learning. In NeurlPS Workshop on Deep Learning and Unsupervised Feature Learning, 2011.
Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M Roy. Information-
theoretic generalization bounds for stochastic gradient descent. In COLT, 2021.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401. PMLR, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization deep learning. In Advances Neural Information Processing Systems, pp. 5947-5956, 2017.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A bac-bayesian approach to spectrally normalizd margin bounds for neural networks. In International Conference on Learn ing Representations, 2018a.
12

---

Published as a conference paper at ICLR 2022
Behnam Neyshabur, Zhiyuan Li, Srinadh Bhojanapalli, Yann LeCun, and Nathan Srebro. The role of over-paramettizzaioonn in generalization of neural networks. International Conference on Learning Representations, 2018b.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32: 8026-8037, 2019.
Ankit Pensia, Varun Jog, and Po-Ling Loh. Generalization error bounds for noisy, iterative algo- rithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pp. 546-550. IEEE, 2018.
Matthew Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. In Proceedings of the 2018 Con- ference of the North American Chapter the Association for Computational Linguisties: Human Language Technologies, Volume I (Long Papers), pp. 2227-2222222222 2237, 2018.
Yury Polyanskiy and Yihong Wu. Lecture notes on information theory. Lecture Notes for 6.441 (MIT), ECE 563 (UIUC), STAT 364 (Yale), 2019., 2019.
Maxim Raginsky and Igal Sason. Concentration of measure inequalities in information theory, com- munications and coding. Foundations and Trends in Communications and Information Theory; NOW Publishers: Boston, MA, USA, 2018.
Borja Rodríguez-Gálvex Germán Bassi, Ragnar Thobaben, and Mikael Skoglund. On random subset generalization error bounds and the stochastic gradient langevin dynamics algorithm. arXiv preprinl arXiv:2010. 10994, 2020.
Nicolas Le Roux, Mark Schmidt, and Francis Bach. A stochastic gradient method with an exponen- tial convergence rate for finite training sets. In Proceedings of the 25th International Conference on Neural Information Processing Systems- Volume 2, pp. 2663-2671, 1, 2012.
Daniel Russo and James Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pp. 1232-1240, 2016.
Daniel Russo and James Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions on Information Theory, 66(1):302-323, 2019.
Shai Shalev-Shward and Shai Ben-David. Understanding machine learning: From theory to algo- rithms. Cambridge university press, 2014.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. 3rd International Conference on Learning Representations, ICLR, 2015.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 15(1):1929 1958, 2014.
Thomas Steinke and Lydia Zakynthinou. Reasoning about generalization via conditional mutual information. In Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pp. 3457-3452. PMLR, 2020.
Christian Szegedy, Vincent Vanhoucke, Sergey loffe, Jon Shlens, and Zbigniew Wojna. Rethink- ing the inception architecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pp. 2818-2826, 2016.
Vladimir Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003-44
Hao Wang, Yizhe Huang, Rui Gao, and Flavio Calmon. Analyzing the generalization capability of sgld using properties of gaussian channels. Advances in Neural Information Processing Systems, 34, 2021a.
13

---

Published as a conference paper at ICLR 2022
Hao Wang, Yizhe Huang, Rui Gao, and Flavio P Calmon. Learning while dissipating information: Understanding the generalization capability of sgld. arXiv preprint arXiv:2102.02976 2021b.
Colin Wei, Sham Kakade, and Tengyu Ma. The implicit and explicit regularization effects of
dropout. In International Conference on Machine Learning, pp. 10181-10192. PMLR, 2020.
Max Welling and Yee W Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference machine learning (ICML-II), pp. 681-688. Citeseer, 2011.
Yeming Wen, Kevin Luk, Maxime Gazeau, Guodong Zhang, Harris Chan, and Jimmy Ba. An empirical study of stochastic gradient descent with structured covariance noise. In International Conference on Artificial Intelligence and Statistics, pp. 3621-3631. PMLR, 2020.
Lei Wu, Chao Ma, and E Weinan. How sgd selects the global minima in werr-parameterized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 2018: 8279-8288, 2018.
Zeke Xie, Fengxiang He, Shaopeng Fu, Issei Sato, Dacheng Tao, and Masashi Sugiyama. Arti- ficial neural variability for deep learning: on overfitting, noise memorization, and catastrophic forgetting. Neural computation, 3368):2163-2192, 202,a
Zeke Xie, Li Yuan, Zhanxing Zhu, and Masashi Sugiyama. Positive-negative momentum: Ma- nipulating stochastic gradient noise to improve generalization. In International Conference on Machine Learning, pp. 11448-11458. PMLR, 2021b.
Aolin Xu and Maxim Raginsky. Information thhorrttc analysis of generalization capability of learn ing algorithms. Advances in Neural Information Processing Systems, 2017:2525-255 2534, 2017.
Zitong Yang. Yaodong Yu, Chong You, Jacob Steinhardt, and Yi Ma. Rethinking bias-variance trade- off for generalization of neural networks. In International Conference on Machine Learning, pp. 10767-10777. PMLR, 2020.
Zhewei Yao, Amir Gholami, Kurt Keutzer, and Michael W Mahoney. Pyhessian: Neural networks through the lens of the hessian. In 2020 IEEE International Conference on Big Data (Big Data), pp. 581-590. IEEE, 2020.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations. OpenReview.net, 2017.
Hongyi Zhang, Moustapha Cisse, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond em- pirical risk minimization. In 6th International Conference Learning Representations, ICLR, 2018.
Jingzhao Zhang, Tianxing He, Suvrit Sra, and Ali Jadbabaic. Why gradient clipping accelcrates training: A theoretical justification for adaptivity. In International Conference on Learning Rep- resentations, 2019.
Yaowei Zheng, Richong Zhang, and Yongyi Mao. Regularizing neural networks via adversarial model perturbation. CVPR, 2021.
Ruida Zhou, Chao Tian, and Tie Liu. Individually conditional individual mutual information bound generalization error. arXiv preprint arXiv:2012.09922. 2020.
14

---

Published as a conference paper at ICLR 2022
Appendix
Table of Contents
HWT HWT Inequality: Proof of Lemma
15
B
Key Lemma: Lemma
Mutual Information Bounds for SGD: Proof of Theorem lladd Theorem 2
17
Lemma
17
Proof of Theorem]
18
C.3
Corollary
Recovering Lemma
19
C.4 Proof of Lemma
20
C,5
Proof of Theorem
20
C.6
Corollary2
21
D Application in Neural Networks: Proof of Theorems and
21
Lemmal7
21
D.2 Proof 3
22
D.3 Proof Theorem
22
E
Experiment Details
23
E.1
Architectures and Hyperparamettrs
23
F.2
More Experiments on the Comparison Between Theorem
and Lemma
23
E.3
Learning Rate and Batch Size.
24
E.4
Implementation of Theorem] and Theorem
25
Algorithm of Dynamic Gradient Clipping and Additional Results
25
Discussion on Gradient Dispersion Models Trained on Clean Datasels
25
Algorithm of Gaussian Model Perturbation and Additional Results
26
A HWI INEQUALITY: PROOF OF LEMMA 3
The proof given here is a simple extension of the proof of Raginsky & Sason 2018 Lemma 3.4.2), which is a special instance of the (weak) HWI inequality.
Proof.
DKL Dxu(PP-vexxIlB>xveN 5DKL PR.
(1)
E. Drr.P=taanaavlPPeeeeeN. N.Y DEIINNTX,,
X.Y
E.
(2)
1' + t (log
R 2 x.y
- V11 11X--11P
1),
(3)
t
where Eg [ is by the chain rule of the KL divergence, Eq 2 holds since N is independent of (X, Y) and Eq is by the equality
DKL (N(u,, Ei)l Ez))
log
Σg
d + Tr [ '1) + (p2 p1) (p2 -11)
Σ
15

---

Published as a conference paper at ICLR 2022
Eq holds for any joint distribution of (X,Y). If we let t' by the definition of Wasserstein distance, we have
DKL (RI (etx(PP+ViNIIPx+vaa -
wa W3 (Px. Py).
2t
This recovers the vector version of Raginsky & Sason (2018 Lemma 3.4.2).
B A KEY LEMMA: LEMMA 4
Proof. We give two proofs of this lemma, the first proof inspired by the techniques used in Wang
al. 2021a and Guo al. 22005), and the second proof is similar to Pensia al. (2018).
1. = A. By the properties of mutual information,
+ o X|Y y) T(f(Z.)) 22 + y).
Let xX & f(Z Ω. Let Pa. = LI)) for any o' > 0 and N' is indepen- dent of other random variables for fixed y. Then, for Y = y,
X))(Z.X) + NoN; y) = [KL P
- DRL (PAz. - DKL (RNZZ
(4)
I inf E [AL (AN. o'50
(5)
1
(log r²2
+ o²
inf
[1lloo I A =x = =y
E
+
022 - 1)
A o' 20 x
2
E
d log
X.
2
2
where Eq. iis the golden formula (see Theorem 3.3 Polyanskiy & Wu 2019 ), Eq.
is by the nog-tegativ of relative entropy, Eq. 6lis is due to Lemma and the last equality holds when the optimal
[llaly + A = v] X.
+ o²
d
is achieved.
Thus,
(f((,X) + N:X (AAN))=E(((( EI
+ N; =
E [ll
x) =
d
X.
E
log
+1
d
E [[]((z,x) - 11Il1 =y]
d
E
log
+1
2
which completes the proof.
16

---

Published as a conference paper at ICLR 2022
2. Alternativlly. let h(-) denote the differential entropy, then
(U((2,)++ol x|y y) [[((2,))++N; X| =)
[ - x) + =
( v) -((((, X, =
(7)
= = + +NNY= = =y) -((NN)
+))( + =y) d
log 2Teed
where Eq. 7 is due to the fact that conditioning reduces entropy.
Notice that
A. AX) = = E [lo = y] + do
Since the Gaussian distribution maximizes the entropy over all distributions with the same variance (Cover & Thomas 2012), we have
E (v +),X) y] + do
d
NoNZ y) log 2
d
Therefore,
E A,
[lls( + A, X)1 = =y] + do
+oN = =)
log 2Te
log 2
d
E
[lllt + A) = y]
A.X
log
+1
da²
The remaining part is straightforward and is the same with the previous proof.
C MUTUAL INFORMATION BOUNDS FOR SGD: PROOF OF THEOREM I AND THEOREM 2
In this section, we provide proof for Theorem and Theorem while elaborating on why the local gradient sensitivity term in Lemma _ can be removed. The key ingredient that makes this possible is a construction given in the proof of Lemma
C.1 LEMMA 6
We first give the following useful lemma.
Lemma 6. The mutual information SW S Σt= I (-N:g(Wi-1.B)) SW:
Proof. The mutual information between the final output of SGD and the training sample can be upper bounded by the mutual information between the full trajectories and the training sample,
17

---

Published as a conference paper at ICLR 2022
which is shown below.
I S)
Wr-1 -r Nr: S)
</ WT-1: (ir-i::ATy(WT-11) Br) + Nr: S)
(8)
( Br) + Nr; S S
=I(Wr-1;5) + (~Nrg(
(9)
<T(WT-2;5) + 2 Br-1) + 11 N:
+ (->rg(Wr-1. Br) + Nr; S
(10)
SI(Wo:8) +
(11)
t=1
T Σ T (-1ggg B.) No
(12)
where 8 is by [[f(X,);; S 1(X,Y; 2) (i.e Z - f(X, Y) forms a Markov chain and then use the data processing inequality), Eq by the chain rule of mutual information, To is by applying the similar procedure (namely, 8 to ((W--1;S), Eq. 11 is by doing these steps recursively and Eq 12 due to the fact that Wo is independent of S (i.e. I(Wo; S) 0).
C.2 PROOF OF THEOREM
Proof. We first follow the similar decomposition of the expected generalization error and apply Lemma T as in Neu al. 2021).
ggen Pwr1s)] = gen(u, 1sy)s) + E
[L,(WT)) - (wr) + Ar. (ss(Wr) - Ls())
Wr.Ar
2R I(WT; S)
-) S*)
(13)
Wr.3.s
The remaining task is to bound the mutual information 5):
Let X = Y Y = W.- and Ω
E
[g( A--1, 2)}, by applying Lemma 4 we have
A.112
Aeg B.) + No:SWW.-1)
x
|19(0r11- -
-,,,,
E
[g( - A.-1, 2)]l = Wr-1
d
Ac
< JE W.-1
log
+1
2
2
By Lemma and putting everything together, have
Ig, Pwz1s)l
X E S,
119(W.11, B,) E.
Lo(W-11. 2)
Rd
2.0.-
E
log
+1
+ E (>(W,, S) -WW,,
do?
W
This completes the proof.
18

---

Published as a conference paper at ICLR 2022
C.3 COROLLARY I RECOVERING LEMMA
We can recover the result of Lemma 2 in Neu et al. (2021) from Theorem 1 which is re-stated in the following corollary.
Corollary 1. The generalization error of SGD is upper bounded by
2R
Igen(1s Pwy|s)] &
E
3V( + (V.(( + (B(W2, S) -(2,,
W
Proof. From the first term in Theorem
we have
27
A
9(W(-1. Bi)
L9(W(-1, 2)]
R
T
S,Ar-1
2,B.-1
log
+1
do?
W
12
X
E
9(W, (-1 B₂)
E
g(W, 1-1 A..1. 27]
R2d
W.
1.A:
1.8
2.
log
+1
do?
(14)
R2
1(W--1, B,) E
E
(15)
A.-1.
2,
R
|o(W._,, Bi) - -16 BBB 23|
( [WW
g[ A A..221| 2]]1
E
E
Wi-1.8
2,
R
2 2llo(Wi-1.B)) - - 1iWi-122||1
+2 L ((WW-1.2)
[9(W1-1 A1.
|-,1 |
E
E
1:5
2,A,-1
1=1
(16)
12
T
| 2l Bi) - [[( ]]|
I
[W 2)]
[9( D.- 2)
E
+2 E. A.-.
-
S
2
1=1
(17)
R
T
| 2llo(W..1.B3) - (Gllww.nBB)--looov-------
2)] - [o 2) | || + +w
E
W 1.5
R
T
a|lo(W.-1. -1 271 +4 1 2)1 -
- [ 2)]11
+ +2
E
1=1
(18)
R22
T
4 || Be) - B Bb((W-,,2)||'+ (
W
2R
T
E
33((--1) + 2V.
Wi
19

---

Published as a conference paper at ICLR 2022
where Eq. 14 and 17 are by Jensen's inequality (i.e. the concavity of logarithm and the convexity of
squared norm), Eq. 15 is by log( + 1) $ 2, and Eq. 16 and 18 are by || + - 2||x|| 2||y/1
This completes the proof.
C.4 PROOF OF LEMMA 5
Proof. We first notice that
I(G, SW I(- I(-N1g((1-1, +
o -oNN:SSWW-
where ~ Ta)
Then let X = S, Y Wi1 and
E
Ve(W,-1, 2)}, by applying Lemma
we have
Wi 1.2
17 S,
[19(W.11.B)
E
2)]12
d
W W
I(-)o9(W111, B,) +oN:
S
E
log
W
do?
A² E
[v((W-1)]
d
log
W
+111
2
do?
where the second inequality is by Jensen's inequality.
This completes the proof.
C.5 PROOF OF THEOREM 2
Proof. Applying Lemma 6 and Lemma 5 and putting everything together, we have
R2d T
X2 E Wi-1
[V((W,)))
gen Pwr|s)| <
log
+1 +1 + (E((,,,,))
-WW,,
do
t=1
Next, to handle the mismatch between the outputs perturbed SGD and SGD, we apply Taylor expansion around Ar = Ö,
Ls(Wr + AT) - Ls WT,SAAT
[e(WT + Ar, 2,) ((TrZZ)
n
WT
AT
AT) (v A)) + " H (2)Ar) (Z)Ar
Wr.Z
AZHW, (2)
(19)
Wr.Z,Ar
1 ( E
[H,, (Z)}, E
A
2 2'wr2
Wr.2
Ar
1 E
[lw (2)), diag(
of))
(20)
2 W'rr2
Σ7 1= o²
Tr
E Wr.Z
Hw, (2))).
2
where 19 by the zero mean of the perturbation, Eq 20 is by the independence of the coordinates of Ar. (:..) denotes the inner product of two matrices, diag(A) A) is the diagonal matrix with element
A and Tr(:) is the trace of matrix.
20

---

Published as a conference paper at ICLR 2022
Under the condition
E (WW,, O, now bound gen(u, 1w))s) instead of its absolute Wr.S"
value, |gen(H,, Pw,, 1s)1s) With the inequality log( + 1) I 2, the following straightforward,
R
gen(u, Wrrss S
E
[V(W-11)]+
E Wr.5.5
-
π1
of
Wi-1
R
X
E [V(W-11)]+
+ E Wr.s
h(rr
71
of
Wi-1
R T E [VW--))]
E of Tr( IE Wr.2
[Hw, (Z)))
2
Since every choice of a gives valid generalization bound. The optimal bound can be found by simply utilizing the fact A/a+o²B 2 (AA22)2/3 B1/3 for any positive and B, where the equality achieved by the optimal a. Finally, rearranging the terms will complete the proof.
C.6 COROLLARY
Corollary 2. If the loss function differentiable and B-smooth with respect to w, then,
Red
T
X2 E W
[V((W,1))
T
Igen(u, Pwr|s)] S
log
+1
+ 3d
dof
t=1
Proof. Recall the smoothness implies f(v) < f(w) + ( for all v and w. By the triangle inequality, we have
8 E [|AT]]]]
T 3d Di=1 of BT
|E (WT) (WT AT)L
2), AT)||
Thus, we can see that E (L,(T) (Wr Ar)] + E [Ls WT + AT) Ls [W+) S
3d ET= of.
This completes the proof.
Remark 3. In Corollary 2 note that the dependence of d in the bound results from the spher-
ical Gaussian noise used in the construction of the weight process WT. It possible replace the spherical Gaussian with a Gaussian noise having non-diagonal covariance that reflects the geometry of the loss landscape. With this replacement, the dimension in the flatness term will be replaced by the trace of 11= Ks, where Ke is the covariance matrix of the noise added at step t. Please refer to Neu et al. (2027) for a similar development.
ST
D APPLICATION IN NEURAL NETWORKS: PROOF OF THEOREMS 3 AND
D.I LEMMA 7
Lemma 7. Under the same conditions of Theorem bounded by
the generalization error of SGD upper
3
R XT E [1g(Wo11, [ (Hw, (z)))
gen(H, Pw, S
n
21

---

Published as a conference paper at ICLR 2022
Proof. The proof of this lemma follows the same steps in the proof of Theorem except that require a different use of Lemma here.
Specially, let S 0 in Lemma and should be straightforward
The remaining steps the same in the proof of Theorem
Remark 4. The bound Lemmal 7 is weaker than Eq. 3in Theorem 2 as the centralized expected vector norm should be smaller thun the original expected vector norm.
D.2 PROOF OF THEOREM 3
Proof. By Cauchy-Schwarz inequality, we have
E 1 =
W Z,)
<
(21)
Z.EB,
Notice that V Vee(W, (WTX- X)X. Let & ((W,)) Then,
(( - > 21 -8- -r)= 20(WW-1, Z). (22)
For the Hessian matrix, it's easy to see that Tr (Z))
Plugging everything into Lemma 7 we have
R E ((W(-1:2))
gen Pwr1s) $3
4n
W.n1
This completes the proof.
D.3 PROOF OF THEOREM 4
Proof. Since V., (WW
- where Ir. = 1IG X; 2 0}, we have
V W e( 2)12
(23)
-.)
mm A.(J(W.11, 12)T,,113
((W, 2.).
(24)
In addition, we notice that Tr(Hw, (Z)) Em I.S. Plugging everything into Lemma have
Rº 4nm
Y2
1 m
))
gen(H, Pwr1s) 3
Zi)
E Wr.2e
W
m
This completes the proof.
22

---

Published as a conference paper at ICLR 2022
E EXPERIMENT DETAILS
E.1 ARCHITECTURES AND HYPERPARAMETERS
In Section 5 MLP has one hidden layer with 512 hidden units, and AlexNet has five convolution layers (conv. x 3 (64 filters) max-poot 3
conv. x 5 (192 filters) max-pool 3 conv. 3 x 3 (384 filters) - conv. x 3 (256 filters) - conv. 3 x 3 (256 filters) - max-pool 3 3) followed by two fully connected layers both with 4096 units and 10-way linear layer as the output layer. All of the convolution layers and the fully connected layers use standard rectified linear activation functions (ReLU).
The fixed learning rates used for MLP and AlexNet are 0.01 and 0.001, respectively. The batch size set to 60. For the corrupted label experiment, we train the models until the models achieve 100% training accuracy. For other cases, we train the neural networks until the training loss converges (e.g., < 0.0001). Other settings are either described Section orr apparent the figures. Standard techniques such as weight decay and batch normalization are not used.
To choose the variance proxy R. we first collected the per-instance losses 1(W,-1, 1,, 7,) that were observed during training, then we let R (naar,,((W,,.) 7.)) minq, eWW, 1-1, 7))) 2 in our experiments.
In Section 6 we compare GMP with other advanced regularization methods. The results of other methods are reported directly from Zheng et al.] (202T), and we now give their hyperparameter randomly selected to be deactivated
settings here for completeness. For Dropout, 10% of neurons in each layer. For label smoothing, the coefficient is 0.2. For flooding, the level is set to 0.02. For MixUp, lineally combine random pairs of training data where the coefficient is drawn from Beta(1, 1). For adversarial training, the perturbation size is for each pixel and we take one step to generate adversarial examples. For AMP, the number of inner iteration is and the L2 norm ball radius values are 0.5 for PreActResNet18 88 and 0.1 for VGG16, respectively.
The implementation in this paper is on PyTorch, and all the experiments are carried out NVIDIA Tesla V100 GPUs (32 GB).
E.2 MORE EXPERIMENTS THE COMPARISON BETWEEN THEOREM AND LEMMA
Thm 2
Lem 2
(a) le-2
(b) a le-
Tajestory
Traje Pejjectory
20
100
60
80
100
Sterations
itertions (d) V, and V.
(c) 1e
Grad, Dispersion
Trajectory
0
20
100
20
40
60
80
100
Hteations
ilerations
Figure 5: Comparison Between Theorem
2 and Lemma
2 in stochastic setting.
23

---

Published as a conference paper at ICLR 2022
A E E ((W V.Ww.)) and V B(v(Ww)) for two different values of a. Notice that indeed use weaker version of the trajectory term in Theorem 2 and the same constants like R. xe and of in the two bounds are ignored here. We choose the full dataset of MNIST and CIFARIO to train the models with the fixed initialization. We also fix the sampling of batches, making the training completely deterministic. To estimate the local gradient sensitivity term, we randomly sample 20 Gaussian noises from (00 Σー σr) to perturb the model parameters and compute the average perturbed gradient. With this single draw and deterministic setting, the estimated V. and V, are the same, so the bound of Eq. 2 in Theorem 2] should be smaller than the bound in Lemma 2 as shown in Figure
In Figure 1. we compare
We also provide the experiments under the stochastic setting. Specially, We randomly choose 1/10 of the MNIST data and train the MLP model with a fixed learning rate and batch size. To estimate T. [VE(W, Z)}, we conduct 20 runs with different random seeds and save W after every W
iteration. In Figure (d), we can see that at the beginning of training, our gradient dispersion Ve much larger than V. in Neu et al. (022)) ) but in the later training phase, the magnitude of gap between these two terms is very small. This is because the gradient norm will become tiny when
W is near local minima. In Figure 5 (a-c), we compare
T
X
(W-11) + (WW))
T and Ei=1 log ( (W +1) under three different settings of When is small (e.g., do?
1)- the local gradient sensitivity term will become small, but the factor 1//² will be very large, making the gap between log (ar + and x: be extremely large, as shown Figure (c). In this case, the improvement upon Neu et al. (2021) is significant. When is large (e.g.. 1e 3), at the beginning of training, the trajectory term in Lemma 2 will be smaller than the trajectory term in Theorem
2 since our V, is relatively large. However, since (W,,) has the cumulative variance, and V, and V, become closer soon or later, the bound Lemma 2 will be greater than the bound in Theorem 2 in the later training phase.
E.3 LEARNING RATE AND BATCH SIZE.
The learning rate and batch size have some impact on Eq. 3 in Theorem 2 We now investigate this by performing experiments with varying learning rates and batch sizes. In our experiments, the model is continuously updated until the average training loss drops below 0.0001. We separate trajectory and flatness terms of the bound and plot them in Figure
(Png ICC
(a) MLP on MNIST
(b) MLP on MNIST
(c) AlexNet CIFARIO (d) Alex CIFARIO
Figure 6: The impact of learning rate and batch size on the trajectory term and the flatness term in Eq.
A key observation in Figure i that the learning rate impacts the trajectory term and the flatness term in opposite ways, as seen, for example, in (a) and (b), where the two set of curves swap their orders in the two figures. On the other hand, the batch size also impacts the two terms in opposite ways, as seen in (a) and (b) where curves decrease in (a) but increase in (b). This makes the generalization bound, i.e., the sum of the two terms, have a rather complex relationship with the settings of learning rate and batch size. This relationship is further complicated by the fact that small learning rate requires a longer training time, or larger number T of training iterations, which increases the number that are summed over in the trajectory term. Nonetheless, we do observe that a smaller batch size gives a lower value of the flatness term ((b) and (d)), confirming the previous wisdom that small batch sizes enable the neural network to find flat minima (Keskar et al. 2017).
24

---

Published as a conference paper at ICLR 2022
31"
33.
1006
3300
2006
4300
2003
Figure 7: Generalization gap of a linear network v.s. Theorem Note y-axe is log-scale.
38-1
31
38-9
Seraice
Figure 8: Generalization gap of a two-layer ReLU network v.s. Theorem
E.4 IMPLEMENTATION OF THEOREM AND THEOREM
We let do 200 and use a two-layer ReLU network with hidden units 10000 to generate Y. More- over, we apply a lanh function to the output this network so that |Y| S The input data X 1) and we normalize X before training that ||X|| 1. For the training phase, choose m 100, let data size be 20, 000, batch size be 100 and learning rate be 0.5. Figure 7 and Figure
& compare the empirical generalization gap with the bound in Theorem 3 and that in Theorem respectively.
E.5 ALGORITHM OF DYNAMIC GRADIENT CLIPPING AND ADDITIONAL. RESULTS
The dynamic gradient clipping algorithm described in Algorithm I For both MLP and AlexNet, we let a = 0.1. The start step for clipping, T,, is also an important hyperparameter. However, it can be removed by detecting the evolution of the average gradient norm for each epoch. Specifically, whenever the average gradient norm of epoch j is larger than the average gradient norm of epoch j - 1, the clipping operation begins.
From Figure and Figure 9 we can see that dynamic gradient clipping effectively alleviates overfit- ting by conspicuously slowing down the transition of training to the memorization regime, without changing the convergence speed of testing accuracy. Unfortunately, the current design of the dy- namic gradient clipping algorithm does not provide significant improvement for models trained on clean dataset (without label noise). Designing better regularization algorithms may require under- standing the epoch-wise double descent curve of gradient dispersion where the model trained on clean dataset.
E.6 DISCUSSION GRADIENT DISPERSION OF MODELS TRAINED ON CLEAN DATASETS
In the case of no noise injected, Figure 3a shows that the model with good generalization property has exponentially-decae
gradient dispersion. This is consistent with our discussion of Lemma 5 in Section that is, small I(G, + N₁ W.-1) indicates good generalization. Notably, gradient dispersion of AlexNet trained the real CIFAR10 data still has epoch-wise double descent curve.
25

---

Published as a conference paper at ICLR 2022
Algorithm Dynamic Gradient Clipping
Require: Training set S, Batch size b, Loss function E, Initial model parameter wp, Learning rate X, Initial minimum gradient norm G. Number of iterations Clipping parameter a, Clipping
step Te
1: fort 4- 1 to T
2: Sample B = {z;)== from training set S
3:
Compute gradient:
<- Ei=1 V W zib/b
9B
4:
if T. then
5:
if @fl9s1l2 G then
6:
9ss & a
7:
else
8:
5 19
9:
end if
10:
end if
11: Update parameter: w, w,-1 X 95
12:
end for
Asc
clipping
Test wo clipping
Train clipping
Test Ace. wt clipping
80
100
20
40
60
100
epoch
opoch
0.2 (CIFARIO)
(b) noise=0.4 (CIFARIO)
Figure 9: Dynamic Gradient Clipping (AlexNet).
that the testing accuracy does not decrease in the second phase/memorization regime for AlexNet trained the true CIFARIO data. Loosely speaking, we conjugate that memorizing random labels will hurt the performance on unseen clean data but memorizing clean (or true) labels will not. This may explain why dynamic gradient clipping or preventing the training entering the memorization regime cannot improve the performance on clean dataset.
The difference between Figure 3e with Figure 3h 3h
E.7 ALGORITHM OF GAUSSIAN MODEL PERTURBATION AND ADDITIONAL RESULTS
Algorithm Gaussian Model Perturbation Training
Require: Training set S, Batch size b, Loss function f, Initial model parameter wp, Learning rate X, Number of noise k. Standard deviation of Gaussian distribution or, Lagrange multiplier p
while w, not converged do
2: Update iteration:
1++1
Sample B = {z from training set S
4: Sample A, (0, 2) for j E [k]
Compute gradient:
gB + Σb (we( 2,) + p Σi (wwl(w, 2,, - vol(w,, zk))k) /b
6: Update parameter: w++1 wi X 98
end while
26

---

Published as a conference paper at ICLR 2022
Method
SVHN
CIFAR-10
CIFAR-100
ERM
97.05=0.063
94.9810.212
75.6910.303
Dropout
97.20=00065
95.1440.144
75.52+00.351
L.S.
97.22=00087
95.15+0.115
77.93+0.256
Flooding
97.16=10.047
95.03+0.082
75.50-10.24
MixUp
97.26-10.044
95.91
78.22-+0.210
Adv. Tr.
97.23=0.080
95.01=0.085
74.77=00.229
AMP
9..70=0.025
96.03=0.091
7..49
GMP
97.43=0.037
95.6420.053
08.05=102208
GMP10
+7.54
95.71+0.073
78.07+0.170
Table 2: Top-1 classification accuracy acc.(%) of PreActResNet18. We run experiments 10 times and report the mean and the standard deviation of the testing accuracy. Superscript denotes the number of sampled Gaussian noises during training.
Method
SVHN
CIFAR-10
CIFAR-100
GMP abs
97.10=10.054
94.21=0.139
74.80=:0.113
Table 3: Top-1 classification accuracy (%) of VGG16.
The GMP algorithm is given in Algorithm 2 Table and Table 2 show that method is com- petitive to the state-of-the-arr regularization techniques. Specifically, our method achieves the best performance SVHN for both models and on CIFAR-100 where VGG16 is employed. Particu- larly, testing accuracy is improved by nealy 2% on the CIFAR-100 dataset with VGG16. For other tasks, GMP is always able achieve the top-3 performance. In addition, number of sampled noises does not guarantee the improvement of testing accuracy and may even degrade the performance on some datasets (e.g., SVHN). This hints that we can use small number of noises to reduce the running time without losing performance. Moreover, we observe that GMP with k 3 usually takes around 1.76x that of ERM training time, which affordable.
find that increasing the
For PreActtReNNe118, the performance of GMP appears slighly inferior to the most recent record given by AMP (Zheng et al. 202T). Noting that the key ingredient of AMP, "max-pooling" in the parameter space, greatly resembles regularization term in GMP, which may be seen as "average- pooling" in the same space.
One potential extension of GMP is to let the variance of the noise distribution be function of the iteration step f. In other words, using the time-dependent o; instead of constant a.
We also consider the following regularized scheme, which is a absolute value version.
min L. (w) 2L
E
L.(w + A) L.(ww
This scheme can still perform well as shown in Table 3 In fact, it outperforms GMP CIFAR- 100. This hints that it is possible to improve the performance by choosing other norm of Lg (w + A) L.(w..
27


Reviews:
[{"review_id": "sVNPhcB89Vz", "reviewer": "Reviewer_ULcg", "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": "This paper is solid and well-structured. It has a very clear introduction part, making readers easy to follow their idea. On the other hand, compared to Neu et. al., the bound derived in this paper is much tighter (see figure 1), and the technique to derive this is very interesting. However, there do exist some small issues, which is listed as below:\n1. The main concern comes from the novelty. The author also admitted that their bounds are not new compared with the previous result. On the other hand, their application for linear model, and two layer ReLU network is not convincing enough. For example, they author claims that the bound might be independent with the model complexity in the generalization bound due to the fact that the deactivated neurons do not contribute to the bound. However, it is not clear that how many neurons are activated from this bound, which means that this bound itself is not useful. On the other hand, the authors argue that their bound decays with the increase of the model size. This is not fair since they only run the simulation for different widths and filters (Figure 3a, b). It would be great if they can provide experiments for the depth.\n2. Some arguments are provided without any explanation. For example, in page 5, the last second paragraph of Theorem 2, the author mentioned that “This justifies the construction of the auxiliary weight process”. It is a little confused for me that based on the previous description, without the auxiliary weight process the bound will include an additional $log(n)$ factor, which is not a big problem to me. Another example, in the Experimental Study section, author said that “replace the labels of ε fraction of the training and testing instances with random labels”. Is the label in testing instances also replaced by the random labels?  Moreover, in the Dynamic Gradient Clipping section, author said that “i.e., the model is expected to have entered the “memorization” regime”. It is quite confusing for me that why the gradient norm is large than the gradient norm K steps earlier can lead to this argument.", "summary_of_the_paper": "This paper derives an improved stability-based generalization bound for SGD upon Neu et. al.’s work. In particular, they drop a term called local gradient sensitivity, leading to significantly tighter bound in practical models. Based on this generalization bound, they study both linear model and two layer ReLU neural networks. During their analysis, they obtain several interesting observations, which is consistent to the previous ones. Finally, based on their bound, they propose a new training scheme, named Gaussian model perturbation, having good performance on popular datasets.", "summary_of_the_review": "This paper is good and well-structured. However, its novelty is not very strong and there exists some confusing arguments.", "strength_and_weaknesses": "", "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": "nJYPiYZYVrw", "reviewer": "Reviewer_RzUv", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Two comments:\n1.\tThe introduction of Wasserstein distance in the main body of the paper seems to be redundant, as what is really used in the proof is the eq (3) in the appendix, which is only related to squared error between X and Y. A more concise way to present the result could be put eq (3) in the main body of the paper and discuss its connection to Wasserstein distance and HWI inequality in the appendix.\n2.\tIn evaluating the bounds in Figures 2 and 3, how to compute the sub-Gaussian parameter R? If I understand correctly, the loss function for MLP and AlexNet should be cross-entropy, which is not bounded. Moreover, can you prove that they are subgaussian?\n\nMinor comments:\n1.\tThe organization of section 3 can be improved. Currently, the statement of the main theorem, discussion, sketch of proof, and comparison are stuck together.\n2.\tPlots in Figure 3 have two different y-axes, which is hard for me to compare the true generalization gap and the bound. Can you somehow calibrate these plots?\n", "summary_of_the_paper": "This paper presents novel and tighter information-theoretic upper bounds for the generalization error of machine learning models, such as neural networks, trained with SGD. Following the same construction of the auxiliary weight process in Neu (2021), the upper bounds proposed in this paper improve upon Neu (2021) in two ways. One improvement is mainly due to removing an unnecessary term in the bound of Neu (2021), which the author refers to as “local gradient sensitivity”, by invoking the HWI inequality (Raginsky & Sason, 2018). Additionally, the improvement also benefits from replacing a sample-level mutual information term in Neu (2021) with an individual sample mutual information term, exploiting a recent result of Bu et al. (2020). The bounds obtained here decompose into two terms, one measuring the impact of training trajectories (“the trajectory term”) and the other measuring the impact of the flatness of the found solution (“the flatness term”).\n\nThe authors also apply these bounds to analyze the generalization behavior of linear and two-layer ReLU networks. Experimental studies based on these bounds provide some insights into the SGD training of neural networks. Some simple regularization schemes, including dynamical gradient clipping and Gaussian model perturbation, are proposed, which are shown to perform comparably to the current state of the art.\n", "summary_of_the_review": "This is a great paper that refines the information-theoretical analysis of the generalization behavior of SGD using the HWI inequality and the ISMI bound. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "VYYop5lt6YQ", "reviewer": "Reviewer_A9tc", "summary": "", "questions": "", "limitations": "", "rating": 10, "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": "The paper is exceptionally well written. The contribution is important not only from a theoretical, but also from a practical perspective, and the insights and hypotheses derived have the potential to bring the field a significant step forward. The authors also cover and connect with the related literature, at least as far as I can tell from my limited knowledge of this field. The explanations after Lemma 5 and Theorem 2 are particularly nice, and so is the discussion of Dynamic Gradient Clipping.\n\nI do have some questions that I would appreciate to have addressed during the discussion period, but these are mostly out of my own curiosity:\n\n- First, from Th. 3 and 4 it becomes clear that the generalization error increases with the number of epochs. This is also seen in Fig. 1. I assume that this is natural for the first few epochs, as initially the model performs equally badly on the training data and on the population. Is this the correct interpretation? However, what is the intuition behind a monotonic increase of the generalization error over epochs? Especially in the linear model, the term |W_t-1|^2 will eventually settle to a constant (if we can assume that training is successful). Does this mean that essentially the bound becomes more and more loose as T increases? Figure 8 suggests so.\n- In Figure 7, it seems that the trajectory term and flatness term have different orders of magnitude. This somehow works against your explanation that the two terms behave in opposite ways when it comes to batch size and learning rate. The picture is rather clear when you consider the orders of magnitude.\n- Does the second term in (1) really measure flatness? Suppose that w_1 is a very deep local minima, such that \\gamma evaluated at s is large for many samples s (e.g., if s is a large enough sample). In this case, we may assume that the flatness term is small, since both \\gamma values (at S and S') cancel, despite the fact that w_1 is not flat. What am I missing?\n- In Th. 3 and 4, is it still possible to dissect the bound into the product of a Hessian and a gradient dispersion term? If so, please mention that in the text.\n- In respect to Figure 4, why is gradient dispersion small at later epochs? I would assume that at a minimum of w, the gradient direction fluctuates more strongly with different samples than it does during initial training (where a strong gradient signal is available). Is this related to the flatness of the minimum, where the gradient magnitude is small for almost all Z? Does, in this sense, also the trajectory term contain some information about flatness?\n- In your regularization scheme, why do you not propose regularizing with the magnitude (or some other norm) of L_s(w+\\Delta)-L_s(w)?\n- How did you obtain the standard deviations (?) in Table 1? How many independent instances did you train?\nFurthermore, I have a few editorial comments:\n- In some instances, the text could do with a revision (e.g., p1: \"in fact broadly apply broadly\", p2: \"is presented, which the bound is revised\", p2: \"We also provide an application of our bounds is in analyzing\", etc.).\n- The distinction between sample-level and instance-level mutual information was not clear to me in the introduction, even though I am familiar with both types of bounds. Have these terms become common?\n- The usage of the batch gradient function g is not consistent; e.g., in the definition of \\psi, g is evaluated at a single sample Z (if I understood it correctly) and thus coincides with \\nabla_w l(w,Z); however, in the definition of V(w) the nabla version is used instead of g.\n- The HWI of the HWI inequality could be spelled out completely at least once. I am not familiar with this inequality, and I think it would be good to have a name to it.\n- Fig. 2 is too small to read.\n- In Fig. 3, I suggest to use the same axes for both the gap and the bound. Even though the results may not look as impressive, it would be good to show a fair comparison.\n\n\nI nevertheless have a few", "summary_of_the_paper": "The paper presents a new bound on the generalization error of models trained with stochastic gradient descent. The new bound builds on the work of Neu, but is tighter. Based on the insights obtained from the bounds, the authors propose two approaches to improve generalization. On the one hand, they show that gradient clipping helps preventing overfitting. On the other hand, the authors propose a regularization term that adds Gaussian noise to the network weights (Gaussian model perturbation) and show that this type of regularization performs on par with or even better than other contemporary regularization schemes. Aside from these technical contributions, the authors provide ample insight into the mathematical terms they derive and discuss several phenomena observed during learning. In the outlook, the authors discuss how their bound can be further improved by utilizing the strong data processing inequality.", "summary_of_the_review": "An excellent paper of high theoretical and practical relevance. Very well written, with many interesting insights.", "strength_and_weaknesses": "", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "OZxvitv61lI", "reviewer": "Reviewer_Xt5A", "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": "This paper is based on (Neu 2021). The authors clearly presented the technical increment, and the empirical improvements. A strength in this paper is that the proposed generalization bound yields a simple practical regularization technique, which can improve classification with VGG16. This is some novel bits as compared to (Neu 2021), which is mostly theoretical.\n\nDespite a few weakness (see below, for the authors to work on a revision), I tend to vote for acceptance, subject to the authors' rebuttal and the reviewers' discussion.\n\nFirst, this paper largely requires the settings of a very recent work. However, the significance of (Neu, 2021) is not clearly written. Why this\nrecently published results are such a foundational work to build upon? It is meaningful to compare against another, more well-known, bound. For example, in the figure 1, there can be a third bound, comparing with the sum of the trajectory term and the flatness term.\n\n\"let $\\xi$ govern the randomness in the sequence\": this paragraph explain a main assumption of the results, and is informal. There are two factors: the way that the samples are split, and the way the batches are ordered. It not clear on what is random and what is fixed.\n\nThe discussion after theorem 1. There is an inconsistency here. Do $\\Psi(W_t)$ in Lemma 3 and $\\Phi(W_t)$ here refer to the same thing?\nThe bounds in Lemma 3 and Theorem 1 should be explained in more detail. As the meaning of those two terms, and which one is the trajectory/flatness term.\n\nOverall, the writing can be better polished to explain the background and provide intuitions.\n\n**Minor comments:**\n\nIntroduction: \"Neu (2021) presents an information- theoretic analysis\" extra space before theoretic\n\nP2\n\"The bounds we obtain decompose into two terms\"\n-> \"The bounds we obtained can be decomposed into two terms\"\n\nTheorem 4: the equation is too wide\n\nTable 1: add some margin between the table and the surrounding text \n\nP3: is the KL divergence or cross entropy sub-Gaussian?\n\nLemma 3: add a remark to compare against lemma 1 and lemma 2\n\nStatements in conclusion. This is not so meaningful without sufficient motivation and discussion.\n\n", "summary_of_the_paper": "This paper proposed a new generalization bound which is based on the recent construction by Neu (2021). The authors made further assumptions on the randomness of the batch sequence, and improved the results by Neu by achieving tighter bounds by tuning the trajectory term. It is verified empirically, and the flatness term gives a regularization technique for better classification on VGG16 on MNIST.\n", "summary_of_the_review": "Pro:\n- Novel increments over a recent work on generalization bound\n- New regularization based on the flatness term\n\nCon:\n- A few glitches in writing", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made 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": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper offers a refinement of the information-theoretic characterization of the generalization of models obtained via SGD. This is assessed on some basic neural architectures and inspires the use of new regularizers. Overall, even though the perspective of this paper is not novel, the presented results appear to be clearer and tighter than prior instances of the same ideas. This was appreciated by most reviewers. The few clarity and organization concerns that were raised by the reviewers were adequately addressed by the authors. Overall, the paper deserves to be shared with the community.
Decision: Accept (Poster)