On the Generalization of Neural Networks Trained with SGD: Information-Theoretical Bounds and Implications
Authors: Ziqiao Wang
Yongyi Mao
Venue: NeurIPS 2021 Submitted (2021)
Keywords: deep learning
generalization
information theory
learning bound
regularization

Abstract: Understanding the generalization behaviour of deep neural networks is an important theme of modern research in machine learning. In this paper, we follow up on a recent work of (Neu, 2021) and  present new information-theoretic upper bounds for the generalization error of neural networks trained with SGD.   Our bounds and experimental study provide new 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. 

On the Generalization of Neural Networks Trained with SGD: Information-Theoretiaa Bounds and Implications
Anonymous Author(s)
Affiliation Address email
Abstract
Understanding the generalization behaviour of deep neural networks is an important theme of modern research in machine learning. In this paper, follow up cormmation-theoreee upper bounds
a recent work Neu [49] and present new for the generalization error of neural networks trained with SGD. Our bounds and experimental study provide new insights on the SGD training of neural networks. They also point to and simple regularization scheme which show performs comparably to the current state of the art.
Introduction
The outstanding performance of deep learning has brought to the surface some intriguing properties of deep neural networks, one which is the observation that despite their high capacity, deep neural networks tend to generalize well [80]. This contradicts classical wisdom in statistical learning theory 12 (e.g., [71]) ) and has stimulated intense research interest in understanding the generalization behaviour of modern neural networks.
10
14 One theme of research focuses on the study of over-parameterized neural networks, where generaliza-
15 tion bounds are obtained [22, 1, 6, 50, 52, 53, 2, 3] and curious "double descent" phenomenon is observed and analyzed [9, 46, 78). New bounding techniques for analyzing generalization have also been developed, utilizing information theoretic quantities [64, 65, 77, 5, 13, 69, 23, 7, 4, 30, 84]. The bounds provided by these techniques have the advantages accounting for both the data structure and the learning algorithm.
16
18
20 The generalization ability of neural networks trained with mini-batched stochastic gradient descent [61], simply referred to SGD in this paper, has also been widely studied. Specifically, built on connection between stability and generalization [12]. a stability- based bound is first presented in [32]. followed by surge of research effort exploiting similar approaches [44, 17, 26, 43, 8). Information- theoretic bounding techniques have also demonstrated great power in analyzing SGD-like algorithms. bound in analyzing the generalization
21
22
23
24
25
For example, [55] is the first to utilize information-theons
26
ability of SGLD [28, 74]. The bound was subsquently improved by [47, 31, 62, 72]. Inspired by the
work of [55], [49] presents information- theoretic analysis of the models trained with SGD, The
28
analysis of [49] constructs an auxiliary weight process parallel to SGD training and upper-bounds generalization error through this auxiliary process.
30
Another line research connects the generalization of neural networks with the flatness of loss minima [35] found by SGD or its variant [40, 20, 24, 51, 16, 37, 38, 83, 27]. This understanding 32 has led to the discovery of new SGD-based training algorithms for improved generalization. For example, in concurrent development by [83] and [27], local "max-pooling" operation is applied to
31
33
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

34 the loss landscape prior to the SGD updates. This approach, referred to as AMP[83] or SAM[27], is shown make SGD favor flatter minima and achieve the state-of-the-art performance among various competitive regularization schemes [83].
35
36
37 In this paper, we focus investigating the generalization of neural networks trained with SGD. We build upon the work of [49]. Following the same construction of the auxiliary weight process in [49], we present upper bounds of generalization error that improve upon [49] in two ways. The first improvement is via removing an unnecessary term in the bounds of [49] by invoking the HWI inequality [60]. The second improvement is via replacing a sample-leve mutual information term in [49] with an instance-lewe mutual information term, exploiting a recent result of [13]. The bounds we obtain 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") ")
38
39
40
41
42
43
44
We empirically validate the derived bounds. Various insights are also obtained experimentally concerning the generalization of neural networks under SGD training. For example, the batch size of SGD appears to impact the trajectory term and the flatness term in opposite ways, which complicates the overall dependency of generalization error on batch sizes. A particular interesting observation from our experiments is that a key quantity arising in the trajectory term of the bounds, which we refer to as gradient dispersion', ; reveals double descent phenomenon with respect to training epochs. Most intriguingly, the valley in the double descent curve appears to mark the great divide between the "generalization regime" and the "memorization regime" of training. Furthering from this observation, 53 we also show that it possible to reduce the memorization effect by dynamically clipping the gradient and reducing its dispersion.
46
47
48
49
50
51
52
54
Our bounds also inspire a natural and simple solution to alleviate generalization error. Specifically, 56 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[83]. We demonstrate experimentally that GMP achieves a competitive performance with the current art of regularization schemes.
57
58
59
60
61
Length constraints precludes elaboration at places. The reader is referred to supplementary materials for proofs and additional information.
62
Other Related Literature Gradient dispersion is mostly studied from optimization perspectives[11 I, 63, 39, 75, 25]. Prior to this work, only a few works relate gradient dispersion with the generalization behaviour of the networks. In [49, 721, gradient dispersion also appears in the generalization bounds. In [38], gradient dispersion is argued to capture a notion of "flatness" of the local minima of the loss landscape, thereby correlating with generalization.
64
66
67
66 Injecting noise in the training process has been proposed in various regularization schemes, for example, [10, 14, 15, 68, 73]. But unlike the Gaussian model perturbation scheme 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.
69
70
71
72 Gradient clipping is a common technique for preventing gradient exploding (see, e.g., [45, 56]). This technique is also used in [82] to accelerate training. In this paper, gradient clipping is used to investigate and control the impact of gradient dispersion on generalization error.
73
74
75
2
Preliminaries
76 Population Risk, Empirical Risk and Generalization Error Unless otherwise noted, a random
77 variable will be denoted by a capitalized letter (c.g., 2), and its realization denoted by the correspond-
78 ing lower-case letter (c.g. 2). Let Z be the instance space of interest and be unknown distribution
79 on Z, specifying random variable Z. Let W C IRd be the space of hypotheses. Suppose that a training sample S = (Z,, Zz... .2.... ... Z,,) is drawn i..d. from μ and that a stochastic learning algorithm 81 A takes S as its input and outputs a hypothesis W E W according to some conditional distribution Mapp
Pwis mapping 2" to W. Let é W x Z R+ be loss function, where f(w, 2) measures the "unfitness" or "error" of any 2 E Z with respect to a hypothesis w E W. The population risk, for any
83
'The quantity is often referred to as gradient variance in the literature [49, 72). but we prefer "dispersion" to "variance" to better comply with the mathematical conventions and avoid possible confusion.

---

84 E W, is defined as
(u)() _ Ez~ule(w: Z)}.
85 The goal of learning is to find a hypothesis w that minimizes the population risk. But since μ is only
86 partially accessible via the sample S, in practice, we instead turn to the empirical risk, defined
(s(w) A n
Awu, Zí)-
87
The expected generalization error of the learning algorithm is then defined
gen(u, Pw s) Ew.s(L,. Ls)))
86
where the expectation is taken over the joint distribution of (S, W) (i.e., μ² Pwis).
89
Throughout this paper, we take as a continuous function (adopting the usual notion "surrogate loss" [66].). Additionally, assume that & is differentiable almost everywhere with respect to both and
81 2. Furthermore we assume that f(w, 2) is R-suhgaussian" for any to E W. Note that a bounded loss guaranteed be subgaussian for all şe and all w e W. Let (X; Y) denote the mutual information
92
93
[18] between any pair of random variables (X, Y). The following results are known.
94
Lemma ((77, Theorem I.]). The expected generalization error of algorithm A is bounded by
ggen(u, $ <V 2R
n I(W:S).
35
Lemma 2 ([13, Proposition 1.D. gen(u,, gwnss, S
The expected generalization error of algorithm A is bounded by
2R:
1=1
97
Stochastic Gradient Descent We now restrict the learning algorithm A to be the mini-batched 89 stochastic gradient descent (SGD) algorithm for empirical risk minimization. For each training epoch, the dataset randomly split into m disjoint mini-batches, each having size b, namely, Based on each batch, one parameter update is performed. Specifically, let B, denote the batch used for the 1th update. Define
100
mbb
101
102
g(w, B,) A
Σ
V 2):
ZEB,
103
namely, g(w, B,) is the average gradient computed for the batch B, with respect to parameter w. The rule for the ęth parameter update is then
104
W, W Xeg((W-1,,
where d is the learning rate at the step t. The initial parameter setting Wo is assumed to be drawn from the zero-mean spherical Gaussian (0, LfL with variance of in each dimension. We will assume that the SGD algorithm stops after T' updates and outputs WT the learned model parameter.
106
107
108
Given the training sample S, let govern the randomness the sequence ( (B1, B2.... Br) of batches. For the simplicity of notion, we will fix the configuration of Ç. That is, we will assume fixed "batching trajectory", or a fixed way to shuffle the example indices {l,.... n3 and divide them into batches in each epoch. The presented generalization bounds of this paper be extended
110
112
to the case where the batching trajectory is uniformly random (as we set up above). This merely involves averaging over all batching trajectories or taking expectation over &
now associate with the SGD algorithm an auxiliary weight process 115 (.). Let o² be given, and let 01, o or be sequence of positive real numbers. Define
114
Auxiliary Weight Process
Wo A Wo. and W. A W A B.) + No. for > 0, 118 where N ~ (00 La) is a Gaussian noise. The relationship between this auxiliary weight process {W.) and the weight process (W,} in SGD is shown in the Bayesian network below.
Recall that random variable X is susbaauussa [60] if for any p. log E exp (p (X EEX)) - H²² /2/2.
3

---

N1
N₂
Nr-1
NT
118
Wo
WI
+
W2
WT-1
WT
7
W
W
W2
WT-1
WT
Let A = Ei=1 N,. Noting that the weight updates in { uses the same gradient signal as that 119
used in { (which depends W not W.-)), is immediate that Wt W; + A.. Note that this auxiliary process follows the same construction as [49], which we will use to study the generalization error of SGD.
121
125 To that end, define gradient dispersion at parameter w by V(w) - E VII 2) E [V .n lw,, 2)
124
where the expectation is taken over Z ~ μ..
125
For given sample E 2", define
r(w, s) A [L + Ar) L.(w),.
128
where the expectation is taken over ÅT and (x(w) is the empirical risk of at parameter w.
127 In the remainder of the paper, let S' denote another sample drawn from μ², independent of all other random variables. The main generalization bound in [49] is re-stated below.
129
Lemma 3 ([49, Theorem I.).. The gemeralization error of SGD is upper bounded by
2R n
T
V(W. + v(W-11)
Igen(u, Pwy S \
+ -) 7
130
where T (wa-1) A E
V w
((w Z)
Vwl(w:-1 + 5. 2) and ~N,0 oTT,)
The term V (w,-1) in the bound is referred to as "local gradient sensitivity" in [49].
3
New Generalization Bounds for SGD
132
139
We first prove that the generalization bound in Lemma 3 can be tightened by removing the local gradient sensitivity term (w)--)) The key observation is that independence condition used for establishing Lemma 3 in [49] is unnecessary (see Lemma 4 in [49]). This requires invoking a vector version of the HWI inequality [60, Lemma 3.4.2], which we prove in this paper.
135
136
Lemma 4. Let X and Y be two random vectors in Rd, and let N (O, La) be independent of X, Y). Then, for every t >> 0, DKL DKL Py S 2t [|XX - YI
138
139
Here DKL is the KL divergence. Note that the bound in Lemma 3 relies on similar result which however requires the independence of X and Y. Using Lemma 4, we obtain the following theorem.
140
141
Theorem 1. The generalization error of SGD is upper bounded by
2R nb
(p, Pwr|s)] <
E
BV(.W.1)) + | Eb(W,, - -
f=1
142
143
The proof of this theorem, as the bounds in [49], relies on Lemma and the sample-level mutual information bound therein. This theorem instance-level mutual information bound in Lemma is in fact tighter than the sample-level mutual information bound in Lemma 1, as shown in [13]. The main ingredient to proceed in this direction is the following lemma.
be further tightened by exploiting the fact that the
145
147
Lemma 5. Let G, = (W.1, B.). 1f E Bv, then I(G NG; N W-1) S AI BV(--11))
148

---

In this lemma, the mutual information I[G; + Ny; Z, Wi-1) roughly indicates the degree by which the SGD's updating signal G. (smoothed with noise) depends on an individual training instance 71, when Z; is used for computing the gradient. When this dependency is strong (giving rise to high value of the mutual information). the model conceivably tends to overfit the individual training instances. 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.
150
151
152
153
154
155
157
is remarkable that the noise {Nr} plays an important role for the bound to hold. To see this, consider b = 1 and Z is countable and large. Then I(G;; 1-( is merely the conditional entropy (Z. (-1)) which would grow with sample size least as log n. Spper-bbunding it with
158
159
160
quantity independent of n would be impossible This justifies the construction of the auxiliary
161
weight process.
162
We now state our main theorem. Unlike Theorem 1, which considers a random batching trajectory, this theorem considers a fixed batching trajectory keep the expression less cluttered. For that batching trajectory, we will use Ti to denote the set of indices of batches B, containing instance Z,
163
184
Theorem 2. The expected generalization error of SGD is bounded by
R
n
2X
ggen(p, Pwr1s)]] S nbb
E
o
IT
166
167
With an additional assumption, the second term in the bound can be re-expressed, shown in the following corollary.
168
Corollary 1. Assume (wr) S EA [Ly(wr + Ar)), then the following holds,
169
gen Pwrls) S
R
Σ
n
Σ TET,
2x
BV((--))]++
Σi=1 ot Tr (E Hw, (Z))),
nbb
of
2
170
where Hw, is the Hessian matrix of the loss with respect to WT and Tr(-) denotes trace.
171
Corollary follows directly from the second order Taylor expansion of the second term in the bound of Theorem 2. The condition L,, (wr) I EA (wy Ar)) indicates that the perturbation does
173
not decrease the population risk. This is also assumed in [27] in the derivation of a PAC- AAC-Bayesian generalization bound.
175 Notably, in the bound of Theorem 2, the first term captures the impact of the training trajectory ("trajectory term"), and the second term captures the impact of the final solution. As seen in Corollary
176
177
1, this term in fact measures the flatness for the loss landscape at the found solution ("flatness term")..
The previous bound of [49] (Lemma 3) and its tightened version in Theorem I also similarly contain trajectory term and a flatness term. Despite that the flatness term there are identical to that in Theorem
179
2, we now show the trajectory term in Theorem 2 does improve on its counter-pan part in Theorem 1.
181
Lemma 6. Assume the instances are sampled without replacement in every epoch. Then the trajectory term in Theorem 2 is spper-bounded by
182
R
T
2x²
2R nb
min
E (VW...)). of
E
[V(W-
t=1
188
184
The condition in Lemma 6 is usually satisfied in practice. This lemma then immediately implies that the trajectory term in Theorem 2 is no worse than that in Theorem 1. Incorporating this result, if we restrict the smoothness of the loss function L, we may obtain another version of the generalization bound (although the flatness term therein is expected to be looser than that in Corollary 1).
185
186
187
Corollary 2. If the loss function is differentiable and 3-smooth with respect to w, then under the condition of Lemma 6,
189
[gen(H,, Pwz]s)] < min
R
T
2x2 of
E (WWW
T 2R
Σ
(V
+ 3d Σ
T
2
nb t=1
o
t=1
t=1
5

---

191
To conclude, we remark that these bounds suggest that in order for the model to generalize well, both the trajectory term and the flatness term need be small the former involves the interaction of the learning rate and batch size with the gradient dispersion along the training trajectory, whereas the latter depends on the flatness of the empirical risk surface the found solution.
192
193
194
195
4
Experimental Study
196
Bound Verification We first verify our bound in Corollary by training an MLP (with one hidden layer) and an AlexNet [42] on MNIST and CI [41], respectively. To simplify estimation, we fix the weight initialization and set oN and A to be constants a and X, respectively. To compute
198
En VEET, [VW--)))], we compute the gradient dispersion its empirical estimate from a
199
batch, utilizing PyTorch [54] library BackPack [19]. To compute Tr (E (Hw, (Z))), randomly sample 10% of the training data and use the PyHessian library [79] to compute the Hessian. Since
201
202
every choice of a gives valid generalization bound in Corollary 1, we need to find the optimal
0, which gives the tightest bound. This can be done by simply utilizing the fact A/o + o²B Z
203
3(AA2)22/ / for any positive A and B, where the equality is achieved by the optimal o. We set the sub- gaussian parameter R. = 0.1. The implementation in this paper is on PyTorch, and all the experiments are carried out on NVIDIA Tesla V100 GPUs (32 GB).
204
205
208
We perform experiments with varying network width and varying levels of label noise. Specifically, label noise level c refers to the setting where we 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 1.
208
210
1.0
18
MCc MEni pn1
(a) MLP on MNIST
(b) AlexNet on CIFARIO
(c) MLP on MNIST
(d) AlexNet on CIFARIO
Figure I: Estimated bound and empirical generalization gap ("gap") as functions of network width
((a) and (b)) and label noise level ((c) and (d)). Left Y-axis: gap value; right Y-axis: bound value.
In Figure 1, we see that in all cases the estimated bound follows closely the trend of the true generalization 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.
212
214
Note that in Figure I (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.
216
hull E05
Bull
(a) MLP on MNIST
(b) MLP on MNIST
(c) AlexNet on CIFARIO (d) AlexNet on CIFARIO
Figure 2: The impact of learning rate and batch size on the trajectory term and the flatness term.
217 Learning Rate and Batch Size. The learning rate and batch size in SGD have explicitly appeared
in the trajectory term of the bound in Theorem 2. From the way they appear in the bound, one may be tempted to assert that a small learning rate or large batch size will improve generalization. This would then contradict some previous observations [37, 76, 33], in which increasing the ratio of learning rate
219

---

221 to batch size will benefit generalization. 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 2.
222
224
225
A key observation in Figure 2 is that the learning rate impacts the trajectory term and the flatness term in opposite ways, as seen, for example, (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, ie., 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 a small learning rate requires
228
227
228
229
230
231
a longer training time, or larger number I of training iterations, which increases the number that
232
are summed over the trajectory term. Nonetheless, we do observe that smaller batch size gives a
233
lower value of the flatness term ((b) and (d)), confirming the previous wisdom that small batch sizes
234
enable the neural network to find flat minima [40].
8 m00
Tist Acc God. Dap
noise=0 (MNIST)
noisc=0.2 (MNIST)
(c) noisc=0.4 (MNIST)
(d) no6sc=0.6 (MNIST)
Tome Adc.
Dagg
60
10 na
(c) noise=0 (CIFAR10)
(f) noise=0.2 (CIFAR10)
(g) noise=0.4 (CIFARIO) (h) noisc=0.6 (CIFARIO)
Figure 3: Epoch-wise double descent of gradient dispersion, in relation to training/testing accuracies.
235
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 (MIP for MNIST, AlexNet for CIFAR10). For each model and various label noise levels, we plot in Figure 3 the evolution of the (empirical) gradient dispersion (w)), training accuracy and testing accuracy across training epochs.
236
237
238
240
An intriguing epoch-wise "double descent" phenomenon is observed, particularly when the labels noisy. According to the double descent curve, the training may be split into three phases (c.g.. Figure (h)). In the first phase, the gradient dispersion rapidly descends and maintains very low level. In this phase, both training and test accuracies increase while maintaining a 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 a 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 a low value. In this phase, the model continuously overfits the training data, until the training and testing curves reach their respective maximum and minimum. 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 (e.g. CIFARIO with low label noise), the first phase may be shorter. This is arguably because in these datasets, extracting useful patterns is relatively easier. Nonetheless, the valley in the double-descent curve appears to mark a "great divide" between generalization and memorization.
241
242
243
244
245
246
247
248
250
252
254
Dynamic Gradient Clipping Inspired by our generalization bounds and above observations, one way to reduce the generalization error is to control the trajectory term of the bounds by reducing the gradient dispersion in each training step. Here we investigate simple scheme that dynamically clips
256
7

---

Trins for shudlpiin Tea slgeng
(a) noise=0.2 (MNIST) (h) noise=0.4 (MNIST) (c) noise=0.2 (CIFARIO) (d) noise=0.4 (CIFARIO)
Figure 4: Dynamic Gradient Clipping.
258
the gradient norm so as to reduce the gradient dispersion. Specifically, whenever the current gradient norm is larger than the gradient norm K steps carlier, or (l9 B,)ll2 > Il9(W,-k: Bt-K K l (i... the model is expected to have entered the "memorization" regime), we reduce the norm of the current gradient (W,, B,) to a fraction of [la(W..K Br- x) x)1 for some prescribed value < 1. The effectiveness of this scheme is best demonstrated when the labels contain noise. As shown in Figure 4, dynamic 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 is 0.2), without suffering from the severe memorization effect as seen in models trained without this scheme. Further understanding 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.
259
260
262
263
264
266
288
A Practical Implication: Gaussian Model Perturbation
269
The appearance of the flatness term in our generalization bounds suggests that for empirical risk minimizer w" to generalize well, necessary that the empirical risk surface at w" flat, insensitive to small perturbation of w*. This naturally motivates training scheme using the following regularized loss:
271
273
min (w) +
E ol
[L(w + A) Lo(w),
where p is hyper-ppanee parameter. Replacing the expectation above with its stochastic approximation using I realizations of A gives rise to the following optimization problem.
275
min- Σ (1
1 (((0()) (1- + PT. Σ (E(w 8,, +.,
276
We refer to the SGD training scheme using this loss as Gaussian model perturbation or GMP. Notably, GMP requires k ++1 forward passes for every parameter update. Empirical evidence shows that small k. for example, k = 3, already gives competitive performance. Implementing the k + forward passes on parallel processors further reduces the computation load.
278
279
280
We experimentally compare GMP with several major regularization schemes in the current art, includ- ing Dropout [68], label smoothing [70], Flooding [36], Mix [81], adversarial training [29], and AMP [83]. The compared schemes are evaluated on three popular benchmark image classification datasets SVHN [48], CIFAR-10 and CIFAR- 100 [41]. Two representative deep architectures PreAc- 1Res [34] and VGG16 [67] 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 is set to 10-4 For GMP, we choose p 0.5 and set the standard deviation of the Gaussian noise to 0.03. The value of is chosen as and 10 respectively (referred to as GMP3 and GMP
282
284
286
287
288
The performances of all compared schemes given in Table 1. For the compared regularization schemes except GMP, we directly report their performances as given in [83]. Performances of vanilla ERM without regularization also included reference.
290
292
Table 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 [83]. Noting that the key ingredient of AMP, maxx-oooling" the parameter space, greatly resembles regularization term in GMP, which may be seen as "average-pooling" in the same space.
294
8

---

PreActResNec18
Top-I Acc. (%)
PreActResNer188
Top-1 Ace. (%)
PreActResNer18
Top-1 Acc. (%)
ERM
97.05.10.063
ERM
94,9810.212
ERM
75.69110.33
Dropout
97.20+-0.065
Dropout
15.14400.14
Dropout
75.52+00.35
Label Smoothing
97.22=00.87
Label Smoothing
95.15=0.115
Label Smoothing
77.93=#0.256
Flooding
97.16.10.047
Flooding
95.03:10,082
Flooding
75.50.10.234
MixUp
97.26++0.044
MixUp
95.91=0.117
MixUp
78.22++0,210
Adv. Training
97.23:10.080
Adv. Training
95.01=10.085
Adv. Training
74.77=:0.29
AMP
97.70:10.025
AMP
9.003:0.091
AMP
78.49::0.300
GMPa
97.43.10.037
GMP3
95.64.10.053
GMP
78.05110.208
GMP1o
97.34.10.058
GMP
95.71110.03
GMP
78.07:10.170
VGGI6
Top-I Acc. (%)
VGGI6
Top-1 Acc. (%)
V6G
Top-1 Ace. (%)
ERM
0.006
ERM
93.68.10.193
ERM
72.16.10.297
Dropout
97.04++0.049
Dropout
93.78+0.147
Dropout
72.28++0.337
Label Smoothing
96.93=10.070
Label Smoothing
93.7110.158
Label Smoothing
72.51=0.1179
Flooding
96.85++0.0885
Flooding
93.74:10.145
Flooding
72.07=+0.27
MixUp
96.91=0.007
MixUp
94.52=0.112
MixUp
73.19=+0.254
Adv. Training
97.06.10.091
Adv. Training
93.51:10.130
Adv. Training
70.88 1.55
AMP
97.27+ 0.015
AMP
94.35+0.147
AMP
74,40++0.1M 168
GMP3
97.18 0.057
9.057
GMPa
94.33:10.094
GMP
74.45 : 0.256
GMP10
97.09110.06
GMP10
94.45:10.158
GMP10
75.09.10.20
(a) SVHN
(b) CIFAR-10
(c) CIFAR- 100
Table 1: Top-1 classification accuracy on (a) SVHN (b) CIFAR-IO and (c) CIFAR-100. We run experiments 10 times and report the mean and the standard deviation of the testing accuracy.
6
Conclusion and Outlook
297
This paper presents new generalization bounds for neural networks trained with SGD, improving upon the results of [49]. Our bounds naturally point to new and effective regularization schemes. At the same time, they reveal interesting phenomena in the SGD training of neural networks. While these phenomena deserve further investigation in their own right, we here suggest another direction for improving the bounds, namely, via the use of strong data-processing inequalities (DPI) [57-59] (noting that the standard DPI is in fact needed for establishing Theorem 2).
299
301
303
For any Markov chain U + + Y, we will denote by U, X' and y the spaces in which U, X, Y take values, respectively. For any distribution P on X, we will use Pv|x P to denote the
304
305
distribution on y induced by the push-forward of the distribution P by Pylx, namely, for any y V,
Pryx P) (y) & f Pr|x (2)x) (f)x=)((2)da Let S(U) be the support of Py and H(U Px be the convex hull (Pxiu=u= : ( Define
306
307
DKL(Prix PlIPrxXQ)
miU -U-X-Y)
sup P.QEH(U,PxIO)
(pl()))))
Lemma 7. For any Markov chain U
I(U:Y) & nuU + +
309
Here v7 + + Y) serves as the "contraction coefficient" for the stochastic kernel Pr|x, characterizing the greatest extent by which the kernel may bring closer any two distributions on S(U) in its output space. It is easy to see that n + X Y)= < giving rise to stronger DPI.
310
W, form Markov chain. Denote Thi A (2 + Vi W.), and r {t+ 1, + 2, ..... T} T. Theorem can be improved to:
Denote V, A W. G.. It can be verified that Z; V,
313
Theorem 3. The expected generalization error of SGD is bounded by
[gen(u, Pwr1s)) <
2R
Σ TET.
E (V((,
II nhr + [E - rEr!
nb
315
It remains characterize the contraction coefficient 7h.- in computable form. Simply bounding it 317 via the Dobrushin's 's coefficient [21], J, as suggested in [72] for analyzing SGLD, unlikely to make the bound in this theorem significantly tighter than that in Theorem 2.

---

References
319
320
[1] Z. Allen-Zhu, Y. Li. and Z. Song. A convergence theory for deep learning via over-
parameterization. In International Conference on Machine Learning, pages 242-252. PMLR. 2019.
322
323
[2] S. Arora, R. Ge, B. Neyshabur, and Y. Zhang. Stronger generalization bounds for deep nets via compression approach. In International Conference on Machine Learning, pages 254-263. PMLR, 2018.
325
326 [3] S. Arora, S. Du, W. Hu, Z. Li, and R. Wang- Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. In International Conference on Machine Learming, pages 322-332. PMLR, 2019.
327
328
329
[4] A. R. Asadi and E. Abbe. Chaining meets chain rule: Multilevel entropic regularization and training of neural networks. Journal of Machine Learning Research, 21(139):1-33 2020.
330
331
[5] A. R. Asadi, E. Abbe, and S. Verdú. Chaining mutual information and tightening generalization bounds. In Proceedings of the 32nd International Conference on Neural Information P Processing Systems, pages 7245-7254, 2018.
332
335
334 [6] L. Bartlett, D. J. Foster, and M. Telgarsky. Spectrally-normalizee margin bounds for neural networks. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 6241-6250, 2017.
336
337 [7] R. Bassily, S. Moran, I. Nachum, J. Shafer, and A. Ychudayoff. Learners that use little information. In Algorithmic Learning Theory, pages 25-55, PMLR, 2018.
[8] R. Bassily, V. Feldman, C. Guzmán, and K. Talwar. Stability of stochastic gradient descent on nonsmooth convex losses. Advances in Neural Information Processing Systems, 33, 2020.
340
341 [9] M. Belkin, D. Hsu, S. Ma, and S. Mandal. Reconciling modern machine-learning practice and the classical birinvar trade-off. Proceedings of the National Academy of Sciences, 116
342
343
(32): 15849-1554, 2019.
344
[10] C. M. Bishop. Training with noise is equivalent to tikhonov regularization. Neural computation, 7(1):108-115 1995.
345
346
[11] L.. Bottou, F. E. Curtis, and J. Nocedal. Optimization methods for large-scale machine learning. Siam Review, 60(2):223-311, 2018.
347
[12] O. Bousquet and A. Elisseeff. Stability and generalization. The Journal of Machine Learning Research, 2:499-526, 2002.
349
350
[13] Y. Bu, S. Zou, and V. V. Veeravalli. Tightening mutual information- bounds on generaliza- tion error. IEEE Journal on Selected Areas in Information Theory, 1(1):121-130, 2020.
[14] A. Camuto, M. Willetts, U. Simsekli, S. J. Roberts, and C. C. Holmes. Explicit regularisation in gaussian noise injections. In Advances in Neural Information Processing Systems, 2020.
353
354
[15] A. Camuto, X. Wang, I.. Zhu, C. Holmes, M. Gürbüzbalaban, and U. Şimşekli. Asymmetric heavy tails and implicit bias in gaussian noise injections. arXiv preprint arXiv: 102.07006, 2021.
355
356
357
[16] P. Chaudhari, A. Choromanska, S. Soatto, Y. LeCun, C. Baldassi, C. Borgs, J. T. Chayes, L. Sagun, and R. Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. In 5th International Conference on Learning Representations. OpenReview.net, 2017.
358
359
360
[17] Y. Chen, C. Jin, and B. Yu. Stability and convergence trade-off of iterative optimization algorithms. arXiv preprint
361
2018
362
[18] M. Cover and J. A. Thomas. Elements of Information Theory. John Wiley & Sons, 2012.
363
[19] Dangel, F. Kunstner, and Hennig. Backpack: Packing more into backprop. 8th International Conference on Learning Representations. OpenReview.net, 2020.
10

---

385
[20] L. Dinh, R. Pascanu, S. Bengio, and Y. Bengio. Sharp minima can generalize for deep nets. In International Conference on Machine Learning. pages 1019-1028. PMLR, 2017.
386
367
[21] R. L. Dobrushin. Central limit theorem for nonstationary markov chains. Theory of Probability & Its Applications, 1(1):65-800 80, 1956.
389
[22] S. Du, X. Zhai, B. Poczos, and A. Singh. Gradient descent provably optimizes over- parameterized neural networks. In International Conference on Learning Representations, 2018.
370
371
372
[23] C. Dwork, V. Feldman, M. Hardt, T. Pitassi, O. Reingold, and Roth, Generalization in adaptive data analysis and holdout reuse. In Proceedings of the 28th International Conference on Neural Information Processing Systems-Volun Volume 2, pages 2350-2358, 2015.
374
375
(24) G. K. Dziugaite and D. 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 in Artificial Intelligence (UAI), 2017.
377
378
[25] F. Faghri, D. Duvenaud, D. J. Fleet, and J. Ba. A study of gradient variance in deep learning. arXiv preprint 20Xx:22007.04532,, 2020.
379
380
[26] V. Feldman and J. Vondrak. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. In Conference on Learning Theory, pages 1270-1279. PMLR, 2019.
382
383
[27] P. Foret, A. Kleiner, H. Mobahi, and B. Neyshabur. Sharpness-awee aware minimization for efficiently improving generalization. arXiv preprint arXiv:2010.01412. 2020.
384
385
[28] B. Gelfand and K. Mitter. Recursive stochastic algorithms for global optimization in r'd. SIAM Journal on Control and Optimization, 29(5):99-11088 1991.
[29] I. J. Goodfellow, J. Shlens, and C. Szegedy. Explaining and hamnsssin adversarial examples. In 3rd International Conference on Learning Representations, ICLR, 2015.
388
389
[30] H. Hafez-Kolahi, Z. Golgooni. S. Kasaci, and M. Soleymani. Conditioning and processing: Techniques to improve coammation-theorerte generalization bounds. Advances in Neural Information Processing Systems, 33, 2020.
390
[31] M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite. Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms. arXiv preprint arXiv:2004. /2983, 2020.
393
395
[32] M. Hardt, B. Recht, and Y. Singer. Train faster, generalize better: Stability of stochastic gradient descent. In International Conference on Machine Learning, pages 1225-1234. PMLR, 2016.
396
[33] F. He, T. Liu, and D. Tao. Control batch size and learning rate to generalize well: Theoretical and empirical evidence. In Advances in Neural Information Processing Systems 32, pages 1141-1150, 2019.
396
400
[34] K. He, X. Zhang, S. Ren, and J. Sun. Identity mappings in deep residual networks. In European Conference on Computer Vision, pages 630-645, 2016.
401
402
[35] S. Hochreiter and J. Schmidhuber, Flat minima. Neural Computation, 9(1): 1-), 1997.
[36] T. Ishida, I. Yamane, T. Sakai, G. Niu, and M. Sugiyama. Do need zero training loss after achieving zero training error? In Proceedings of the 37th International Conference on Machine Learning, ICML, 2020.
404
406
[37] S. Jastrzębski, Z. Kenton, D. Arpit, N. Ballas, A. Fischer, Y. Bengio, and A. Storkey, Three factors influencing minima in sgd, arXiv preprint arXiv:1711.04622 2017.
407
[38] Y. Jiang, B. Neyshabur, H. Mobahi, D. Krishnan, and S. Bengio. Fantastic generalization measures and where to find them. In International Conference on Learning Representations, 2019.
409
11

---

[39] R. Johnson and T. Zhang. Accelerating stochastic gradient descent using predictive variance reduction. Advances in neural information processing systems, 26:315-323, 2013.
412
413
[40] N. S. Keskar, D. Mudigere, J. Nocedal, M. Smelyanskiy, and P. T. P. Tang. On large-batch train- ing for deep learning: Generalization gap and sharp minima. In 5th International Conference on Learning Representations. OpenReview.net. 2017.
415
416
[41] A. Krizhevsky. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.
417
418
[42] A. Krizhevsky, I. Sutskever, and G. E. Hinton. Imagenet classification with deep convolutional neural networks. Advances in neural information processing systems, 15:1097-1105, 2012.
419
[43] Y. Lei and Y. Ying. Fine-grained analysis of stability and generalization for stochastic gradient descent. International Conference on Machine Learning, pages 5809-5819. PMIR, 2020.
421
422
[44] B. London. A pac-bayesian analysis of randomized learning with application to stochastic gradient descent. In Proceedings of the 31st International Conference Neural Information Processing Systems, pages 2944,, 2017.
424
425
[45] S. Merity, N. S. Keskar, and R. Socher. Regularizing and optimizing Istm language models. In International Conference on Learning Reprexentations, 2018.
426
427
[46] Nakkiran, G. Kaplun, Bansal, T. Yang, B. Barak, and I. Sutskever. Deep double de- scent: Where bigger models and more data hurt. In International Conference on Learning Representations, 2019.
428
429
430
[47] J. Negrea, M. Haghifam, G. K. Dziugaite, A. Khisti, and D. M. Roy. Information -ifomattionthhcorticc generalization bounds for sgld via data-dependent estimates. In Advances in Neural Information Processing Systems, pages 11013-11220 2019.
432
439
[48] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng. Reading digits in natural images with unsupervised feature learning. In NeurlPS Workshop Deep Learning and Unsupervised Feature Learning, 2011.
435
438
[49] G. Neu. Information-theorrtic generalization bounds for stochastic gradient descent. arXiv preprint arXiv:2 2021.
437
438
[50] B. Neyshabur, R. Tomioka, and N. Srebro. Norm-based capacity control in neural networks. In Conference Learning Theory, pages 1376-1401. PMLR, 2015.
[51] B. Neyshabur, S. Bhojanapalli, D. McAllester, and N. Srebro. Exploring generalization in deep learning. In Advances in Neural Information Processing Systems, pages 5947-5956, 2017.
441
442
[52] B. Neyshabur, S. Bhojanapalli, and N. Srebro. A pac-bayesian approach to ppectrally-normalie margin bounds for neural networks. In International Conference on Learning Representations, 2018.
443
444
445
(53]
B. Neyshabur, Z. Li, S. Bhojanapalli, Y. LeCun, and N. Srebro. The role of wverpaaramttiization in generalization of neural networks. International Conference on Learning Representations, 2018.
446
[54] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L.. Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in Neural Information Processing Systems, 32:8026-80333 8037, 2019.
449
450
[55] A. Pensia, V. Jog, and P.-L. Loh. Generalization error bounds for noisy, iterative algorithms. In 2018 IEEE International Symposium on Information Theory (ISIT), pages 546-550. IEEE, 2018.
452
453
454
[56) M. Peters, M. Neumann, M. Tyyer, M. Gardner, C. Clark, K. Lee, and L. Zettlemoyer. Deep contextualized word representations. In Proceedings of the 2018 Conference of the North Amer- ican Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long Papers), pages 2227-2233 2237, 2237,2211 2018.
456
12

---

458
[57] Y. Polyanskiy and Y. Wu. Dissipation of information in channels with input constraints. IEEE Transactions on Information Theory. 62(1):35-55, 2015.
459
480
[58] Y. Polyanskiy and Y. Wu. Strong data-processing inequalities for channels and bayesian networks. In Convexity and Concentration, pages 21 211- Springer, 2017.
462
[59] M. Raginsky. Strong data processing inequalities and é-sobolev inequalities for discrete channels. IEEE Transactions Information Theory, 62(6))3355- 2016.
464
[60] M. Raginsky and I. Sason. Concentration of measure inequalities information theory, communications and coding. Foundations and Trends in Communications and Information Theory; NOW Publishers: Boston, MA, USA, 2018.
486
467
[61] H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical stutistics, pages 400-407, 1951.
468
489
[62] B. Godve, G. Bassi, R. Thobaben, and M. Skoglund. On random subset general- ization error bounds and the stochastic gradient langevin dynamics algorithm. arXiv preprint arXiv:2010.1 10994, 2020.
470
472
[63] N. L. Roux, M. Schmidt, and Bach. A stochastic gradient method with an exponential convergence rate for finite training sets. In Proceedings of the 25th International Conference on Neural Information Processing Systems-Volume 2, pages 2663-2671, 2012.
473
474
475
[64] D. Russo and J. Zou. Controlling bias in adaptive data analysis using information theory. In Artificial Intelligence and Statistics, pages
2016.
477
[65] D. Russo and Zou. How much does your data exploration overfit? controlling bias via information usage. IEEE Transactions Information Theory, 66(1):302-323, 2019.
479
[66] S. Shalev-Shwartz and Ben-David. Understanding machine learning: From theory to
480
algorithms. Cambridge university press, 2014.
481
[67] K. Simonyan and Zisserman. Very deep convolutional networks for large-scale image recognition. In 3rd International Conference on Learning Representations, ICLR, 2015.
482
668]
N. Srivastava, G. Hinton, A. Krizhevsky, I. Sutskever, and R. Salakhutdinov. Dropout: A simple way to prevent neural networks from overfitting. The Journal of Machine Learning Research, 151):1992-1958, 2014.
484
485
486
[69] T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual infor- mation. In Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3437-3452. PMLR, 2020.
488
[70] C. Szegedy, V. Vanhoucke, S. loffe, J. Shlens, and Z. Wojna. Rethinking the inception archi- tecture for computer vision. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, CVPR, pages 281 8-2826, 2016.
490
492
[71] V. Vapnik. Statistical learning theory. Wiley, 1998. ISBN 978-0-471-03003--4
493
[72] H. Wang, Y. Huang, R. Gao, and F. P. Calmon. Learning while dissipating information:
494
Understanding the generalization capability of sgld. arXiv preprint arXiv:2102.02977 2021.
485
[73] C. Wei, S. Kakade, and T. Ma. The implicit and explicit regularization effects of dropout. In International Conference Machine Learning, pages 10181-10192. PMLR, 2020.
497
[74] M. Welling and Y. W. Teh. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th international conference machine learning (ICML-11), pages 681-688, Citescer, 2011.
499
[75] Y. Wen, K. Luk, M. Gazeau, G. Zhang, H. Chan, Jnd Ba. An empirical study of stochastic gradient descent with structured covariance noise. In International Conference on Artificial Intelligence and Statistics, pages 3621-3631. PMLR, 2020.
501
13

---

503
[76] L. Wu, C. Ma, and E. Weinan. How sgd selects the global minima in over wer-parmmeterized learning: A dynamical stability perspective. Advances in Neural Information Processing Systems, 1188828--8888 2018.
504
[77] A. Xu and M. Raginsky. cotommation-thooretie analysis of generalization capability of learning algorithms. Advances in Neural Information Processing Systems,
507
2017.
508
[78] Z. Yang. Y. Yu, C. You, Steinhardt, and Y. Ma. Rethinking bias-variance trade-off for
generalization of neural networks. In International Conference Machine Learning, pages 10767-10777. PMLR, 2020.
510
[79] Z. Yao, A. Gholami, K. Keutzer, and M. W. Mahoney. Pyhessian: Neural networks through the lens the hessian. In 2020 IEEE International Conference on Big Data (Big Data), pages
512
513
581-590. IEEE, 2020.
514
[80] C. Zhang. S. Bengio, M. Hardt, B. Recht, and O. Vinyals. Understanding deep learning requires rethinking generalization. In 5th International Conference on Learning Representations. OpenReview.net, 2017.
515
[81] H. Zhang, M. Cisse, N. Dauphin, and D. Lopez-Paz. mixup: Beyond empirical risk mini- mization. In 6th International Conference on Learning Representations, ICLR, 2018.
518
519
[82] J. Zhang, T. He, S. Sra, and A. Jadbabaie. Why gradient clipping accelerates training: A theoretical justification for adaptivity. In International Conference on Learning Representations, 2019.
521
522
[83] Y. Zheng, R. Zhang. and Y. Mao. Regularizing neural networks via adversarial model perturba- tion. In CVPR, 2021.
523
524
[84] R. Zhou, C. Tian, and T. Liu, Individually conditional individual mutual information bound on generalization error. arXiv preprint arXiv:2012.09992, 2020.
14

---

Checklist
528
527
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
529
contributions and scope? [Yes]
530
(b) Did you describe the limitations of your work? [Yes] See Section 4, Section 5 and supplementary materials.
531
532
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See supplementary materials.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
535
536
2. If you are including theoretical results...
537
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section and Section 3.
538
(b) Did you include complete proofs of all theoretical results? [Yes] See supplementary materials.
540
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] See supplemen-
543
tary materials.
545
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 5 and supplementary materials.
546
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See Section 4 and Section 5.
548
549
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 4.
550
4. If you using existing assets (e.g., code, data, models) or curating/releasing new assets...
552
(a) If your work uses existing assets, did you cite the creators? [Yes] See Section 4 and Section 5.
553
554
(b) Did you mention the license of the assets? [Yes] See supplementary materials.
555
(c) Did you include any new assets either in the supplemental material or as URL? [No]
556
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [No]
557
558
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [No]
560
5. If you used crowdsourcing or conducted research with human subjects...
581
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
582
563
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
564
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
586
15


Reviews:
[{"review_id": "uvGXgPZRSdA", "reviewer": "Reviewer_dXbz", "summary": "\nThis paper considers the important problem of understanding the generalization of the SGD algorithm. This paper is a follow up on this paper:\n\n G. Neu. “Information-theoretic generalization bounds for stochastic gradient descent”.\n\nTo analyze the generalization, the authors use the mutual information framework of Russo-Zou and Xu-Raginsky where the expected generalization error is upper bounded using mutual information (MI) between output and training set. The main issue with analyzing SGD with MI is that it leads to vacuous bounds due to the fact that there is only degenerate noise in SGD. To circumvent this issue,  the authors use the idea of analyzing a “surrogate algorithm” from Neu’ 21 paper. The surrogate algorithm is a noisy version of the SGD, and instead of analyzing the SGD we can analyze the generalization of the surrogate algorithm. At the end we need to add “pay” for the difference between the output of the surrogate algorithm and SGD.   \n", "questions": "", "limitations": "", "rating": 4, "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": "Contribution and Positive points:\n\nThe main contributions of the authors on the top of Neu’ 21 paper are obtaining a tighter bound using the mutual information bound of Bu et al. in Theorem 2. Note that the construction of the surrogate algorithm is exactly the same as the paper by Neu'21.\nAn interesting point about the main results is that the generalization bound both depends on the trajectory of SGD and the final solution. In particular, the variance of the gradients along the pass captures how trajectory affects the generalization. Then, in Corollary 2 they have a nice result which shows the sharpness of the final solution impacts the generalization. Finally, they have an extensive empirical study of their bound on different benchmarks. \n\nHowever, I have some major comments and some of them are concerned with the validity of their proof.\n\nWeakness and Questions:\n\n-I think the introduction needs to be revised. It is not clear how this work relates to other work in the literature of understanding generalization of SGD. Note the problem of understanding the generalization of SGD has been approached using lots of different tools and techniques. \n\n-General comment about the paper: In the abstract and in the introduction, it has been emphasized that this paper aims to derive generalization bounds for neural networks trained with SGD. However, it is not clear how the quantities appearing in the main theorem in the paper (Theorem 2) depend on the neural networks parameters. Specifically, I could not find anything specific about neural networks in the main results. In fact the results hold for any learning objective which is optimized with SGD. This is in contrast with some of the known results on the generalization of neural networks which connect the generalization to the specific parameters of the neural networks.\n\n-Corollary 2: One important issue with this result is the dependence on the dimension. This is in contrast with the classical analysis of SGD using the stability framework which is dimension-free. How do you compare the stability method and your method? \n\n-Corollary 1: Assume we want to study the generalization error of a NN trained with SGD with respect to 0-1 loss. 0-1 loss is subG with parameter ¼. However, it is not continuous. Therefore, the bound in corollary 2 can’t be used for 0-1 loss function since it does not have second-derivative. Because the Gamma term is defined with respect to the loss function. How does this affect the conclusion of the paper on the impact of the flatness of the final solution on the generalization? \n\n-Diagonal covariance: Adding gaussian noise seems to be reasonable. However, why do not you consider the non-diagonal covariance? \n\n-Stochastic Convex optimization: Assume that the loss function is convex, lipschitz, and smooth. How can you use this information to design the noise variances? It seems to me that this framework in this regime is much looser than Hardt et al results specifically because of the dependence on the dimension. \n\n-Line 205: In your numerical results what do you mean by setting the sub-gaussian parameter to 0.1? If you use 0-1 loss then the subgaissian parameter is ¼. \n\n-It seems you use corollary 1 for empirical studies. As pointed out, this is not valid, it is not valid for 0-1 loss function.\n\nComments of the proof:\n\n\n-The conditional expectation notation in the paper should be revised. For instance in Eq (9) the notation is not correct and it makes it very difficult for readers to understand it. The outer expectation is over S,S’ but inside there is a conditioning on the specific realizations. The same error appears in the rest of the proof.\n\n-I have difficulty understanding  Eq(6) - Eq(10). Specifically, what do you mean by “we do not use an independent copy of \\tilde{W}”?  I believe the derivation in Neu’ 21 is correct (beginning of Page 8 in the V1 arxiv version of Neu’ 21). My understanding is as follows: P(W|S) is a kernel which shows the learning algorithm: specifically given a training set, it outputs a distribution on W. Therefore, when you have two independent training sets S and S’, they will generate two independent copies of W and W’ whose law are given by P(W|S) and P(W’|S’). Specifically Eq(8) in your paper is not correct. This is an extremely serious issue and I would like to hear your detailed response on this.\n\n-Could you please elaborate on Eq (11)? Eq(10) follows from the monotonicity of the KL divergence or Data Processing. In Eq (11) you wanted to use the chain rule for KL. But the caveat here is that the surrogate algorithm \\tilde{W} is NOT Markovian as shown in the figure on Page 4 of your paper.  As a result,  Eq (11) in its current form is NOT CORRECT. I would appreciate it if you could comment on it since it is an important step in the proof and it might affect the validity of the proof.\n\n-I think in Eq. 11 you wanted to use the tower rule but you forgot to write the outer expectation. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I think the limitations of this work is not discussed thoroughly in the paper. The authors can refer to my questions above to find suggestions for improvement. ", "review_text": "", "extra_scores": {"ethical_concerns": "There is no specific ethical concerns with this paper.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "VLIh3oTFpUi", "reviewer": "Reviewer_Bv3T", "summary": "This paper studies the generalization of neural networks trained using stochastic gradient descent (SGD) using information-theoretic bounds. It builds upon existing work that bounds the generalization error using the average square root of the mutual information of the weights with each training datum and related work by Neu 2021 [49] that refines this bound using quantities that correspond to the local gradient sensitivity, the variance/dispersion of the mini-batch gradients, and a stability term that captures the loss at the terminal weights on independent test data. The main contributions of this manuscript are as follows.\n\n1. The paper introduces a coupled auxiliary weight process which refers to the weights updated using additive noise in the gradient descent direction calculated by SGD using the original weights. This allows the authors to study the mutual information of the descent direction with a particular datum in Lemma 5.\n2. Theorem 1 establishes that the gradient sensitivity term can be eliminated using an application of Otto and Villani’s HWI inequality that relates the entropy of the weight posterior with the Wassserstein distance and the Fisher information. Theorem 2 and Corollary 1 expand on this result. The main conclusion is that the generalization error can be broken down into two terms, one that depends upon the ratio of the learning rate and batch-size and another that depends upon the stability term referred to above (bounded in Corollary 1 using the trace of the Hessian).\n3. The bound in Theorem 2 is verified using a fully-connected network on MNIST and a convolutional network on CIFAR-10. \n4. The paper also develops a loss function that training neural networks that averages the loss of the network across different perturbations of the weights by Gaussian noise. This new loss function is evaluated on MNIST, CIFAR-10 and CIFAR-100.", "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": "Main comments\n\n1. This paper is very closely related to [49]. It is understood that this reference is, as yet, unpublished. The authors should however discuss the novelty compared to respect to this existing work.\n2. Line 214: Arguably, the red line in Fig. 1 a,b does not decrease but rather settles down to a steady value as the model size increases. Is this an experimental artifact?\n3. How do you explain the fact that the upper bound in Theorem 2/Lemma 6 increases with T, i.e., is larger for longer trajectories? In practice, the generation gap clearly remains bounded as the number of training epochs increases. The authors come close to discussing this around Line 230 but it is necessary to expand upon this for bounds such as those in this paper.\n4. It is possible that the complex relationship between the learning rate, number of training steps T and the upper bound stems from the fact that the gradient dispersion term is not “normalized“. This term (Line 123) does not distinguish between the gradient dispersion being small somewhere at the beginning of training (say all per-sample gradients have similar magnitudes and point in similar directions) versus the term being small at the end (which would indicate training finding a critical point that is close to the critical points of the per-sample loss functions). It may be possible to separate out these two phenomena.\n5. The above point also calls into question the importance of the “double descent of gradient dispersion” phenomenon explored in Figure 3. Indeed, for noisy samples, it has been seen that there is a long phase in training where the per-sample gradients show a strong mismatch and the training/test loss plateaus (https://arxiv.org/abs/2101.06509). It is unclear what the implication of this double descent observation is and how it is related to the rest of the paper.\n6. I have concerns about the experiments in Table 1. First, such loss functions have been used numerous times in prior work (the authors do cite papers on flat minima so they are aware of algorithms like https://arxiv.org/abs/1611.01838, https://arxiv.org/abs/1609.04836 etc.); so this loss is not really novel. Second, networks trained with this new loss generalize about as well as algorithms like AMP, so this experiment is more of a sanity check than a new contribution. It would be good for the manuscript to demarcate the new contributions explicitly in the introduction.\n\nIn conclusion, there are interesting theoretical parts in this manuscript but (i) it is difficult to ascertain whether the theory is novel enough to merit publication, and (ii) the experiments seem to be essentially disjoint of the theory. Perhaps, the results in Theorem 3 could be fleshed out and added to the main text.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Adequate.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "GYQwW3WdOuk", "reviewer": "Reviewer_ytrb", "summary": "Improves existing information-theoretic generalization bounds for neural networks trained with SGD, and explores a new double descent phenomenon. Application consisting of GMP interesting but not competitive to best baselines.", "questions": "", "limitations": "", "rating": 7, "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": "This paper improves a bound in [49], removing a term therein by using a variant of the HWI. This bound is further improved from n^-1/2 to 1/n rate. These improvements, while not requiring a wholly new analysis, do seem to be significant improvements, and the authors discuss the interpretation and implications of the new bound thoroughly. I therefore recommend acceptance.\n\nLine 61-62 can be removed, it is sufficient to mention additional material in the supplement in line.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "no social impact", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "NA"}, "extra_text": {}}, {"review_id": "7AEfOfq-xdR", "reviewer": "Reviewer_w2wb", "summary": "This paper proves a new information-theoretic upper bound for the generalization of neural networks trained with SGD. The authors claim that the developed new bound provides new insights on the SGD and propose a new regularization scheme which can match the state-of-the-art result.\n", "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": "After reading this paper it seems that the main contribution is the improvement of the generalization bound compared to [49, Theorem 1.1]. In particular, the authors prove that the “local gradient sensitivity” term in [49] is unnecessary. However, it is not clear whether this improvement is significant. the authors may need to discuss which term in Lemma 3 could be the dominating one (i.e., comparing the magnitude of $\\Psi(W)$ and $V(W)$). Besides, the authors should also include the bound in Lemma 3 in the experiment (e.g., Figure 1) to better interpret the improvements.\n\nFrom Theorem 2 it can be seen that the generalization error becomes smaller when increasing the mini-batch size. Consider an extreme case where $b=n$, then the algorithm reduces to full-batch gradient descent. The authors did discuss a bit in Section 4, but a theoretical explanation could be better. Besides, why not directly compare the proved generalization bound or test accuracy for different batch sizes as that could be more related to the theory of this paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This paper has no negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4 hrs"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proves an information-theoretic generalization error bound of neural networks trained by SGD. The main concern of the reviewers is about the novelty and significance of the results derived in this paper because this paper is heavily built upon recent work in COLT 2021. Even after the author response, this paper does not receive sufficient support from the reviewers. Therefore, I recommend rejection.
Decision: Reject