Generalization bounds via distillation
Authors: Daniel Hsu
Ziwei Ji
Matus Telgarsky
Lan Wang
Venue: ICLR 2021 Spotlight (2021)
Keywords: Generalization
statistical learning theory
theory
distillation

Abstract: This paper theoretically investigates the following empirical phenomenon: given a high-complexity network with poor generalization bounds, one can distill it into a network with nearly identical predictions but low complexity and vastly smaller generalization bounds.  The main contribution is an analysis showing that the original network inherits this good generalization bound from its distillation, assuming the use of well-behaved data augmentation.  This bound is presented both in an abstract and in a concrete form, the latter complemented by a reduction technique to handle modern computation graphs featuring convolutional layers, fully-connected layers, and skip connections, to name a few.  To round out the story, a (looser) classical uniform convergence analysis of compression is also presented, as well as a variety of experiments on cifar and mnist demonstrating similar generalization performance between the original network and its distillation.  


Published as a conference paper at ICLR 2021
GENERALIZATION BOUNDS VIA DISTILLATION
Daniel Hsu
Ziwei Ji, Matus Telgarsky, Lan Wang University of Illinois, Kirana-Chaapatt (ziweiji2 mjt [ (rraang@@iiiieee sillincis.edu
Columbia University, New York City djhsuêcs. col umbia.edu
ABSTRACT
This paper theoretically investigates the following empirical phenomenon: given a high-complexity network with poor generalization bounds, one can distill it into a network with nearly identical predictions but low complexity and vastly smaller generalization bounds. The main contribution is analysis showing that the orig- inal network inherits this good generalization bound from its distillation, assum- ing the use of well-behaved data augmentation. This bound is presented both in an abstract and in a concrete form, the latter complemented by reduction tech- nique to handle modern computation graphs featuring convolutional layers, fully- connected layers, and skip connections, to name few. To round out the story, a (looser) classical uniform convergence analysis of compression also presented. as well as a variety of experiments on ei farrll 0 and mnist demonstrating sim- ilar generalization performance between the original network and its distillation.
OVERVIEW AND MAIN RESULTS
Generalization bounds are statistical tools which take as input various measurements of predic- tor on training data, and output a performance estimate for unseen data that is, they estimate how well the predictor generalizes to unseen data. Despite extensive development spanning many decades (Anthony & Bartleti 1999), there is growing concern that these bounds are not only dis- astrously loose (Dziugaite & Roy 2017). but worse that they do not correlate with the underlying phenomena (Jiang et al. 2019b). and even that the basic method of proof is doomed (Zhang et al. 2016 Nagarajan & Kolter 2019). ). As an explicit demonstration of the looseness of these bounds, Figure calculates bounds for standard ResNet architecture achieving test errors of respectively 0.008 and 0.067 on mni st and ci farl0; O; the observed generalization gap is 10-1, while standard generalization techniques upper bound it with 10
Contrary to this dilemma, there evidence that these networks can often be compressed or distilled into simpler networks, while still preserving their output values and low test error. Meanwhile, these simpler networks exhibit vastly better generalization bounds: again referring to Figure [ those same networks from before can be distilled with hardly any change their outputs, while their bounds reduce by factor of roughly 1 Distillation is widely studied (Buciluu et al. (2006, Hinton et al., 2013), but usually the original network is discarded and only the final distilled network is preserved.
The purpose of this work is to carry the good generalization bounds of the distilled network back to the original network; in a sense, the explicit simplicity of the distilled network is used as a witness to implicit simplicity of the original network. The main contributions are as follows.
The main theoretical contribution is generalization bound for the original, undistilled network which scales primarily with the generalization properties of its distillation, assuming that well- behaved data augmentation is used to measure the distillation distance. An abstract version of this bound is stated in Lemma [.] along with a sufficient data augmentation technique in Lemma 1.2 A concrete version of the bound, suitable to handle the ResNet architecture in Fig- ure is described in Theorem
Handling sophisticated architectures with only minor proof alterations is another contribution of this work, and is described alongside Theorem 1.3 This abstract and concrete analysis is sketched in Section 3 with full proofs deferred to appendices.
Rather than using assumption the distillation process (e.g., the aforementioned "well- behaved data augmentation") "), this work also gives a direct uniform convergence analysis, cul- minating in Theorem 1.4 This is presented partially open problem or cautionary tale, as

---

Published as a conference paper at ICLR 2021
10
10ia
1016
Gen bound:
10
Lemma
Gen measure:
10
==1 [[[
10P
10
10c
Distilation
108
distancce ento
10a
10a
Training
10P
10
Testing
10a
10
10
10a
10a
distillation distance p,ss
distillation distance $ 2
(a) ResNet8 trained on eifar10.
(b) ResNet8 trained mnist.
Figure 1: Generalization bounds throughout distillation. These two subfigures track a sequence of increasingly distilled/comppessedd ResNet8 networks along their horizontal axes, respectively for cifar10 and mnist data. This horizontal axis measures distillation distance 4y.m, defined below in eq. [.Tp. The bottom curves measure various training and testing errors, whereas the top two curves measure respectively generalization bound presented here (cf. Theorem Lemma 3.1). and a generalization measure. Notably, the top two curves drop throughout a long interval during which test error remains small. For further experimental details, Section
1x3 and
its proof vastly more sophisticated than that of Theorem 1.3 but ultimately results in a much looser analysis. This analysis sketched in Section 3 with full proofs deferred to appendices.
While this work is primarily theoretical, it is motivated by Figure and related experiments: Figures to demonstrate that not only does distillation improve generalization upper bounds, but moreover it makes them sufficiently tight to capture intrinsic properties of the predictors, for example removing the usual bad dependence on width these bounds (cf. Figure33 These experiments detailed in Section
1.1 AN ABSTRACT BOUND VIA DATA AUGMENTATION
This subsection describes the basic distillation setup and the core abstract bound based on data augmentation, culminating in Lemmas I.] and 1.2. concrete bound follows in Section 1.2
Given a multi-class predictor f RRd TR. distillation finds another predictor g RRd -> T which is simpler, but close in distillation distance py,m. meaning the sofimax outputs o, are close on average over a set points (2
mm (f.g) = 1 Σ - where (,(s(z)) exp (f(2)/7). (1.I)
The quantity 0 is sometimes called a temperature (Hinton et al. 2015). Decreasing y increases sensitivity near the decision boundary; in this way, is naturally related the concept of margins in generalization theory, as detailed in Appendix B due to these connections, the use of softmax is beneficial in this work, though not completely standard the literature (Buciluù et al.) 2006).
We can now outline Figure and the associated empirical phenomenon which motivates this work. (Please see Section for further details on these experiments.) Consider a predictor f which has good test error but bad generalization bounds; by treating the distillation distance (, (f.,) as an objective function and increasingly regularizing 9. we obtain a sequence predictors (go...., ...o......))))...... It), where gu f. which trade off between distillation distance and predictor complexity. The curves in Figure are produced in exactly this way, and demonstrate that there are predictors nearly identical to the original which have vastly smaller generalization bounds.
Our goal here to show that this enough to imply that f in turn must also have good generalization bounds, despite its apparent complexity. To sketch the idea, by bit of algebra (cf. Lemma A.2 can upper bound error probabilities with expected distillation distances and errors:
Pra.y (arg max fz) # vl s 2f (1((())) 2E v (1 (g(())))
2

---

Published as a conference paper at ICLR 2021
The next step is to convert these expected errors into quantities over the training set. The last term already in a form we want: depends only on g. so we can apply uniform convergence with the low complexity of g. (Measured over the training set, this term is the distillation error in Figure
The expected distillation distance term is problematic, however. Here are two approaches.
1. We can directly apply uniform convergence; for instance, this approach was followed by Suzuki et al. (2019). and a more direct approach is followed here to prove Theorem 1.4 Unfortunately, it is unclear how this technique can avoid paying significantly for the high complexity of f.
2. The idea in this subsection to somehow trade off computation for the high statistical cost of the complexity of f. Specifically, notice that L..m (f.g) only relies upon the marginal distribution of the inputs x, and not their labels. This subsection will pay computation to estimate & 7. with extra samples via data augmentation, offsetting the high complexity of f.
We can now set up and state our main distillation bound. Suppose we have a training set ((ri, )== drawn from some measure μ., with marginal distribution fax on the inputs Suppose we also have (z4) drawn from a data angmentation distribution Vn, the subscript referring to the fact that it depends on (z;) Our analysis works when ||dox/ar.lloo. the ratio between the two densities, is finite. If it is large, then one can tighten the bound by sampling more from Vn, which is computa- tional burden; explicit bounds on this term will be given shortly in Lemma 1.2]
Lemma 1.1. Let temperature parameter 7 > be given, along with sets of multiclass predictors FF and G. Then with probability at least - 28 over an iid draw of data ((I,, V:)) Vim from and 1 Pas every f E and g E 9 satisfy
Pr(arg max f(z)y # v) s 2
dux dv
p y. (f.9)
2 1
=E (1-0,,0(2x)))
1/32
dux
(Radi (F) + Radm (9) (9) + Vi
Rad (9)
7
dvn
1000
6V
(1/0/))
[+
dux
n1
2n
dun
where Rademacher complexities Rad,, and Rad,,. are defined in Section 1.4
key point that the Rademacher complexity Rad,, (F) of the complicated functions F. has subscript "m"" which explicitly introduces a factor 2/m in the complexity definition (cf. Section 1.4). As such, sampling more from the data augmentation measure can mitigate this term, and leave the complexity of the distillation class as the dominant term.
Of course, this also requires ||dxx/dr=||>> to be reasonable. As follows one data augmentation scheme (and assumption marginal distribution μx) which ensures this.
Lemma 1.2. Let (Ira)== be data sample drawn iid from px, and suppose the corresponding - density is supported on j0. 11d and is Hölder continuous, meaning (oe))p(z'){ < for some Ca 2 0. E [0, 1]. Define data augmentation measure Vn, via the following sampling procedure.
With probability 1/2, sample z uniformly within [0, 1],
Otherwise, select data index i E [m] uniformly, and sample z from a Gaussian centered at a; and having covariance I²1 where == 11/2a++
Then with probability at least 1 - 1/n over the draw of (xx (
dux
Vnnn (2a+2d
=4+0
dun 100
Though the idea is not pursued here, there are other ways to control ||dux/dr,llo> for instance via an independent sample of unlabeled data; Lemmal 1.1 is agnostic to these choices.
3

---

Published as a conference paper at ICLR 2021
1.2 A CONCRETE BOUND FOR COMPUTATION GRAPHS
This subsection gives an explicit complexity bound which starts from Lemma 1.1 but bounds ||dux/dr_ll>> via Lemma 1.2 and also includes an upper bound on Rademacher complexity which can handle the ResNet, as in Figure [ A side contribution of this work is the formalism to easily handle these architectures, detailed as follows.
Canonical computation graphs are a way to write down feedforward networks which include dense linear layers, convolutional layers, skip connections, and multivariate gates, to name a few, all while allowing the analysis to look roughly like a regular dense network. The construction applies directly to batches: given an input batch X E Re the output X, of layer is defined inductively as
x-= ; o1 (W..LLLW.. - ([" 1):
P.XT_
where: o, is multivariate- tontittt-tt--eeee to-multivariate P; P:-Lipschitz function (measured over minibatches on ei- ther side with Frobenius norm); F; a fixed matrix, for instance an identity mapping as in a residual network's skip connection; D, is a fixed diagonal matrix selecting certain coordinates, for instance the non-skip part in residual network; 11, is Frobenius norm projection of full minibatch; W; is a weight matrix, the trainable parameters; [W denotes row-wise concatenation of W,ILD,; and F,.
As simple example of this architecture, a multi-layer skip connection can be modeled by including identity mappings in all relevant fixed matrices F,, and also including identity mappings in the corresponding coordinates of the multivariate gates o, As second example, note how to model convolution layers: each layer outputs a matrix whose rows correspond to examples, but nothing prevents the batch size from changes between layers; in particular, the multivariate activation before a convolution layer can reshape its output to have each row correspond to a patch of an input image, whereby the convolution filter is now a regular dense weight matrix.
fixed computation graph architecture (( 6, F) has associated hyperparameters (7., b, r, 8), de- scribed as follows. is the set of Lipschitz constants for each (multivariate) gate, as described before. T; is norm bound || S r2 (sum of the |l2-norms of the rows), / (where n is the input batch size) is the radius of the Frobenius norm ball which I1, is projecting onto, and s; is the operator norm of X + DX,"),""" While the definition is intricate, it cannot only model basic residual networks, but it is sensitive enough to be able have s; = 1 and r; = 0 when residual blocks are fully zeroed out, an effect which indeed occurs during distillation.
Let temperature parameter y > O be given, along with multiclass predictors F, and computation graph architecture G. Then with probability least - 25 over an iid draw of data ((x,, f and (z:)= from Vns every I E F satisfies
Theorem 1.3.
dux
2 Σ
Prfargmax max f(x) # vl //
inf (6.F5)21
2
Py (f.)(
(o(x))))
dun
10
+ ④
A/3/2
duxxx
Radm (F)
+ 66/
In(1/6)
1+
dux
71
du
2n
du
+ δ
Vk
1
+
k
dup
12
Σ
r:bip:
r.
S1PE
2/3
3/2
dun
1=++1
Under the conditions of Lemma 1.2
ignoring an additional failure probability 1/a, then ll duxx 11
4 -
Vinn (2
A proof sketch of this bound appears in Section B with full details deferred to appendices. The proof is a simplification of the covering number argument from (Bartlett et al.) 2017a); for another computation graph formalism designed to work with the covering number arguments from (Bartlett et al. 2017a), see the generalization bounds due to Wei & 2019).
4

---

Published as a conference paper at ICLR 2021
Lemina 3.1
2000
width 64
10a
Theorem 1.4
1750
wicth 256
bound
width 1024
1500
Training error
Testing error
1250
10a
1000
750
10a
500
250
10
10aa
10a
0.000
0.002
0.004
0.006
0.008 0.010
0.012
distillation distance & x.mm
(a) Comparison of bounds on ci sifarl..
(b) Width dependence with Theorem 1.4
Figure 2: Performance of stable rank bound (ef. Theorem 1.4). Figure 2a compares Theorem L.4
to Lemma 3.1 and the VC bound (Bartlett et al.) 2017b). and Figure 2b normalizes the margin histogram by Theorem [..4 showing an unfortunate failure of width independence (cf. Figure 3 For details and a discussion of margin histograms, see Section
1.3 UNIFORM-COO CEFFORM-CONVERGENCE APPROACH TO DISTILLATION
In this section, we derive Rademacher complexity bound on F whose proof internally uses com- pression; specifically, it first replaces f with a narrower network g. and then uses a covering number bound sensitive network size to control g. The proof analytically chooses g's width based on the structure of f and also the provided data, and this data dependence incurs factor which causes the familiar 1/v5 rate worsen 1/11/4 (which appears I| This proof much more intricate than the proofs coming before, and cannot handle general computation graphs, and also ignores the beneficial structure of the softmax.
Theorem 1.4. Let data matrix X E Raxd be given, and let F denote networks of the form I + (WL -.. (Wiz)) with spectral norm [|Wll2 S s4, and 1-Lipschitz and 1-homogeneous activations oi and || [|F= I R2 and width most m. Then
Rad FF 5
||
II 83
Σ
(R//s))
5/4
Σ In R.
1/4
3/4
The term R./s, is the square root of the stable rank of weight matrix W, and is desirable quantity in generalization bound: it scales more mildly with width than terms like WW]l2, and || / width which often appear (the former appears in Theorem] 1.3 and Lemma B.I.. I.. Another stable rank bound was developed by Suzuki et al. 2019), but has extra mild dependence width.
As depicted in Figure however, this bound is not fully indth-independent. Moreover, we can compare it to Lemma 3.1 throughout distillation, and not only does this bound not capture the power of distillation, but also, eventually its bad dependence on n causes it to lose out to Lemma 3.1
1.4 ADDITIONAL NOTATION
Given data (2,) the Rademacher complexity of univariate functions H. is
Rad(H) == T2
Σ <dh((z))
where 6, iid.
Uniform((11,+1).
bEH
Rademacher complexity is the most common tool in generalization theory (Shalev-Shwartz & Ben- David 2014), and is incorporated in Lemma [.] due to its convenience and wide use. To handle multivariate (multiclass) outputs, the definition is overloaded via the worst case labels as Rad,, (F) supşeld- Rad( { (z, y) + f(z), f E F)). This definition is for mathematical convenience, but overall not ideal; Rademacher complexity seems to have difficulty dealing with such geometries.
Regarding norms, || I|e will denote the Frobenius norm, and ||2 will denote spectral norm.

---

Published as a conference paper at ICLR 2021
2000
width
width 64, 42 0.035
1750
width 258
2500
width 256, 0.026
wilth 1024
width 1024, O 0.026
1500
2000
1250
1500
1000
750
500
500
250
0.00
0.01
0.02
0.03
0.04
-0.2
-0.1
0.0
0.1
0.2
0.3
(a) Margins before distillation.
(b) Margins after distillation.
Figure 3: Width independence. Fully-connected 6-layer networks of widths {64, 256, 1024) were trained on mnimmtt.ttt........... until training error zero; the margin histograms, normalized by the generalization bound in Lemma 3.1 all differ, and are close to zero. After distillation, the margin distributions are far from zero and nearly the same. In the distillation legend, the second term p,,m denotes the distillation distance, as defined Equation (I.I). Experiment details and an explanation of margin histograms appear in Section 2.
ILLUSTRATIVE EMPIRICAL RESULTS
This section describes the experimental setup, and the main experiments: Figure showing progres- sive distillation, Figure compprrig Theorem T.4] Le I. VC dimension, Figure showwig width independence after distillation, and Figure showing the effect of random labels.
Experimental setup. As sketched before, networks were trained in standard way on either cifar10 or mnist, and then distilled by trading off between complexity and distillation distance T 7. Details are as follows.
1. Training initial network f. In Figures and 2a the architecture was ResNet8 based on one used in (Coleman al., (017), and achieved test errors 0.067 and 0.008 on cifarl0 and mnisst respectively, with changes to the setup and a modest amount of training; the training algorithm was Adam; this and most other choices followed the scheme eifarl0. In Figures 2b 3 and
(Coleman)
ct al. 2017) to achieve competitively low test 6-layer fully connected network was used (width 8192 in Figure 2bb widths {64, 256 1024 in Figure width 256 in Figure D. and vanilla SGD was used to optimize.
2. Training distillation network Given f and a regularization strength メj. each distillation øj was found via approximate minimization of the objective
y (f. A,Cooplexity(g)
(2.1)
In more detail, first 9o was initialized to f (g and f always used the same architecture) and optimized via eq. (2.1 with Ån set roughly tik(///comlletty(/) and thereafter 9,-1 ini- tialized to 9j and found by optimizing eq. (2.I) with Aj+1 : 2A.. The optimization method the same the used to find f- The term Complexity was some computationally reasonable approximation
Lemma 3.1 for Figures 2b and it was just >; ||T 2|,, but for Figures [ and 2a| it also included a tractable surrogate for the product of the spectral norms, which greatly helped distillation performance with these deeper architectures.
In Figures 2b 3 and 4 full regularization sequence was not shown, only single 0j. This was chosen with a simple heuristic: amongst all (9)))21- pick the one whose 10% margin quantile is largest (see the definition and discussion of margins below).
Margin histograms. Figures 26 and all depict margin histograms, flexible tool to study the individual predictions of a network on all examples in a training set (see for instance (Schapire & Freund 2012) for their use studying boosting, and (Bartlett et al, 2017al Jiang al. 2019a) for

---

Published as a conference paper at ICLR 2021
103%: rand, 6 0.0.222
100% rand. + 0.012
rand. 0u000
3000
rand, 00000
rand, 0.036
50% rand, 0.005
25% rand, 9 0u0004
2546 rand, 9 -00,004
rand,
2000
1500
1500
1000
1000
500
500
0.00
(a) Permuting diffcrent fractions of labels.
(b) Zoomed in.
Figure 4: Label randomization. Here (0%, 25%, 50%, 75%, 100%) of the labels were permuted across the respective experiments. In all cases, the margin distribution is collapsed to zero. For details, including an explanation of margin histograms, see Section 2
their in studying deep networks). Concretely, given predictor g G, the prediction every example is replaced with a real scalar called the normalized margin via
(Ii, vi) + g g(Zi)y. # g(xz),
Rad,, (9)
where Rad, (G) is the Rademacher complexity (cf. Section 1.4). and then the histogram of these n scalars is plotted, with the horizontal axis values thus corresponding to normalized margins. By using Rademacher complexity as normalization, these margin distributions can be compared across predictors and even data sets, and give a more fine- mee-grained analysis of the quality of the generaliza- tion bound. This normalization choice was first studied in (Bartlett et al.) (2017)), where it was also mentioned that this normalization allows one to read off generalization bounds from the plot. Here, it also suggests reasonable values for the softmax temperature 7.
Figure [ effect of distillation on generalization bounds. This figure was deseribed before; briefly, a highlight is that in the initial phase, training and testing errors hardly change while bounds drop by factor of nearly 1010 Regarding "generalization measure", this term appears in studies of quantities which correlate with generalization, but are not necessarily rigorous generalization bounds (Jiang et al.) 2019b; Dziugaite al.] (0200); in this specific case, the product of Frobenius norms requires a dense ReLU network (Golowich et al. 2018), and is invalid for the ResNet (e.g., complicated ResNet with single identity residual block yields value by this measure).
Figure 2a comparison of Theorem 1.4 Lemma 3.1 and VC bounds. Theorem 1.4 was intended to internalize distillation, but as in Figure 2a clearly a subsequent distillation still greatly reduces the bound. While initially the bound is better than Lemma 3.1 (which does not internalize distillation), eventually the n 1/ factor causes it to lose out. Also note that eventually the bounds beat the VC bound, which has been identified as a surprisingly challenging baseline (Arora et al. 2018).
Figure 3 width independence. Prior work has identified that generalization bounds are quite bad at handling changes in width, even if predictions and test error don't change much (Nagarajan & Kolter 2019 Diang et al. 2019b; Dziugaite et al.) 2020). This is captured in Figure 3a where the margin distributions (see above) with different widths are all very different, despite similar test errors. However, following distillation, the margin histograms Figure (3b are nearly identical! That is say: distillation not only decreases loose upper bounds before, it tightens them to the point where they capture intrinsic properties of the predictors.
Figure 2b: failure of width independence with Theorem 1.4 designed to internalize compression, and there was some hope of this due the stable rank term.
The bound Theorem L.4 was

---

Published as a conference paper at ICLR 2021
Unfortunately, Figure 2b shows that it doesn't t quite succeed: while the margin histograms are less separated than for the undistilled networks Figure Ba they are still visibly separated unlike the post-distillation histograms in Figure 3b
Figure 4 random labels. A standard sanity check for generalization bounds is whether they can reflect the difficulty of fitting random labels (Zhang al.) 2016). While it has been empirically shown that Rademacher bounds do sharply reflect the presence of random labels (Bartlett et al, 2017a Figures & 3), the effect is amplified with distillation: randomizing just 25% shrinks the margin distribution significantly.
ANALYSIS OVERVIEW AND SKETCH OF PROOFS
This section sketches all proofs, and provides further context and connections to the literature. Full proof details appear in the appendices.
3.1 ABSTRACT DATA AUGMENTATION BOUNDS IN SECTION
As mentioned in Section 1.1 the first step of the proof is to apply Lemma A.2 to obtain
Pra.y (arg max f()) + vl S 2E l
(g(2)) 2E.. (g(2))))
yf
this step is similar to how the ramp loss is used with margin- based generalization bounds, connec- tion which is discussed in Appendix
Section also mentioned that the last term is easy: d, is (1/s)-iiscchizz, and we peel it off and only pay the Rademacher complexity associated with g E G.
With data augmentation, the first term is also easy:
(())((())) ( (g(2))) dux()))=)))))=))))))))) ((00))))((1(,(())))))))))))))))) ())
dux dun (z)
IE ymm (f.g)
du,
dux
/ - dzn(z),
(x((())
du,
and now we may apply uniform convergence to V4 rather than px. the appendix, this proof is handled with bit more generality, allowing arbitrary norms, which may help in certain settings. All together, this leads to proof of Lemma
For the explicit data augmentation estimate in Lemma 1.2 the proof breaks into roughly two cases: low density regions where the uniform sampling gives the bound, and high density regions where the Gaussian sampling gives the bound. In the latter case, the Gaussian sampling in expectation behaves as a kernel density estimate, and the proof invokes a standard bound (Jiang 2017).
3.2 CONCRETE DATA AUGMENTATION BOUNDS IN SECTION
The main work in this proof is the following generalization bound for computation graphs, which follows the proof scheme from (Bartlett et al., 2017a),, though simplified in various ways, owing mainly to the omission of general matrix norm penalties weight matrices, and the omission of the reference matrices. The reference matrices were a technique to center the weight norm balls away from the origin; logical place center them setting, it is in fact most natural to center everything at the origin, and apply regularization and shrink to a well-behaved function (rather than shrinking back to the random initialization, which after all defines complicated function). The proof also features a simplified (2, -nom matrix covering proof (cf. Lemma C.3).
initialization. However, in this distillation
Lemma 3.1. Let data E Roxd be given. Let computation graph G be given, where II, projects Frobenius-nome balls of radius b bi and 1 I тı and III,,I, Fillz S Si, and Lip(a,) & ps. and all layers have width at most m. Then for every e > there exists a covering set M satisfying
2/3- 3
2433 In(2m²)
L
geg XEM 19(X) - X x||se Se and In In|M
sup min
Σ
TsbaP: II
stPt
1=i+1
8

---

Published as a conference paper at ICLR 2021
Consequently,
2/3-
3/2
4 n
In (2m²)
Rad(g)
1
rabepi II StP1
1=++1
From there, the proof of Theorem
1.3 follows via Lemmas
and
1.2 and many union bounds.
3.3 DIRECT UNIFORM CONVERGENCE APPROACH IN THEOREM
As mentioned before, the first step of the proof is to sparsify the network, specifically each matrix product. Concretely, given weights W; of layer i, letting XT_ denote the input to this layer, then
m W Σ (Wxe))(X
Written this way, it seems natural that the matrix product should "concentrate", and that considering all m outer products should not be necessary. Indeed, exactly such an approach has been followed before to analyze randomized matrix multiplication schemes (Sarlos (006). As there is no goal of high probability here, the analysis is simpler, and follows from the Maurey lemma (cf. Lemma C.1
is used in the (2, 1) nnom matrix covering bound in Lemma C.3
Lemma 3.2. Let network be given with 1-Lipschitz homogeneous activations o, and weight ma- trices (W..... W)) of maximum width m, along with data matrix X Rn and desired widths (K1,...,k)) k1) be given. Then there exists sparsified network output, recursively defined via
M; = Σ e
xJ= = and XI = (W....)).)). where
|ee
jES;
where S₃ is a multiset of K; |S.] indices, I1, denotes projection onto the Frobenius-nome ball of radius || 11ll1sss [|W and the scaling term Z, satisfies Zj S [| w mm/k/, and
L
W h; W
|o (W, -x S |||
W.ll2 112
Σ
The statement of this lemma is lengthy and detailed because the exact guts of the construction needed in the subsequent generalization proof. Specifically, now that there are few nodes, gener- alization bound sensitive narrow networks can be applied. On the surface, it seems reasonable to apply VC bound, but this approach did not yield rate better than 1/6 and also had explicit dependence on the depth the network, times other terms visible in Theorem [.4]
Instead, the approach here, aiming for better dependence network depth, was to produce an oc-norm covering number bound (see (Long & Sedghi 2019) for related approach), with was applied to obtain a Frobenius-norm bound, as in Lemma (.I). Unfortunately, the magnitudes of weight matrix entries must be controlled for this work (unlike the VC approach), and this necessitated the detailed form of Lemma 3.2 above.
and also explicit dependence
minor adjustments (indeed, the co-norm parameter covering approach
To close with a few pointers the literature, as Lemma 3.2 essentially a pruning bound, it is potentially of independent interest; see for instance the literature on lottery tickets and pruning (Frankle & Carbin, 2019; Frankle et al. 2020 Su et al. 2020). Secondly, there is already one generalization bound in the literature which exhibits spectral norms, due to (Suzuki et al. 2019); unfortunately, it also has an explicit dependence on network width.
ACKNOWLEDGMENTS
MT thanks Vaishnavh Nagarajan for helpful discussions and suggestions. ZJ and MT are grateful for support from the NSF under grant I15-1750051, and from NVIDIA under GPU grant.

---

Published as a conference paper at ICLR 2021
REFERENCES
Martin Anthony and Peter L. Bartlett. Neural Network Learning: Theoretical Foundations. Cam- bridge University Press, 1999.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. 2018. arxiv:1802, 05296 [cs. L.].
Peter L Bartlett, Dylan J Foster, and Matus J Telgarsky. Spectrally margin bounds for neural networks. NIPS, pp. 6240-6249, 2017a.
Peter I..
Bartlett, Nick Harvey, Chris Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. 2017b. arXiv: 1703. 02930 [cs. LG].
Cristian Buciluū, Rich Caruana, and Alexandru Niculescu-Mizil, Model compression. In KDD, pp- 535-541, 2006.
Cody A. Coleman, Deepak Narayanan, Daniel Kang, Tian Zhao, Jian Zhang, Luigi Nardi, Peter Bailis, Kunle Olukotun, Chris Ré, and Matei Zaharia. Dawnbench: An end-to-end deep learning benchmark and competition. In NIPS ML Systems Workshop, 2017.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. 2017.
arXiv:1703. 11008 [CS.LG].
Gintare Karolina Dziugaite, Alexandre Drouin, Brady Neal, Nitarshan Rajkumar, Ethan Caballero, Linbo Wang, Ioannis Mitliagkas, and Daniel M. Roy. search of robust measures of generaliza- tion. In NeurIPS, 2020.
Dylan J. Foster and Alexander Rakhlin. fo vector contraction for rademacher complexity. 2019. arXiv:1911. 06468 [CS.
Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. 2019. arXiv:1803 03635 (Cs..G].
Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M. Roy, and Michael Carbin. Pruning neu- ral networks at initialization: Why are missing the mark? 2020. arXiv:2009. 08576
[cs. LG].
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. COLT, 2018.
Geoffrey Hinton, Oriol Vinyals, and Jeff Dean. Distilling the knowledge in neural network. 2015. arXiv:1503 02531 [stat.Mi ML]
Heinrich Jiang. Uniform convergence rates for kernel density estimation. In ICMI, 2017.
Yiding Jiang. Dilip Krishnan, Hossein Mobahi, and Samy Bengio. Predicting the generaliza- tion gap in deep networks with margin distributions. In ICLR, 2019a. arXiv: 1tti::11100000 [stat.M..] ML.].
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. 2019b. arXiv:1912 02178 [cs CGs.LG..
Philip M. Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. 2019. MeXiv:1905 12600 [cs LG].
Vaishnavh Nagarajan and Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. 2019. arXiv: 902. 04742 [cs. L.G.
Gilles Pisier. Remarques sur un résultat non publié de b. maurey. Séminaire Analyse fonctionnelle (dit), pp. 1-12, 1980.
10

---

Published as a conference paper at ICLR 2021
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In FOCS, pp. 143-152, 11 2006.
Robert E. Schapire and Yoav Freund. Boosting: Foundations and Algorithms. MIT Press, 2012.
Shai Shalev-Shwartz and Shai Ben-David. Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press, 2014.
Jingtong Su, Yihang Chen, Tianle Cai, Tianhao Wu, Ruiqi Gao, Liwei Wang, and Jason Lee. Sanity-checking pruning methods: Random tickets can win the jackpot. 2020. [cs.LG].
arXiv:2009. 11094
Taiji Suzuki, Hiroshi Abe, and Tomoaki Nishimura. Compression based bound for non-compressed network: unified generalization error analysis of large compressible deep neural network. 2019.
arXiv:1909. 11274 [cs LG].
Colin Wei and Tengyu Ma. Data-dependens sample complexity of deep neural networks via lipschitz augmentation. 2019. arXiv: 1905. 03684 [cs LG].
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. 2016. arXiv:1611. 03530 (Cs.LG].

---

Published as a conference paper at ICLR 2021
A PROOFS FOR SECTION 1.
The first step is an abstract version of Lemma 1.1 which does not explicitly involve the softmax, just bounded functions.
Lemma A.1. Let classes of bounded functions F and G be given with F F f - [0, 17th and
G 3 g X + [0, 11 Let conjugate exponents 1/p + +1/g 1 be given. Then with probability at least 1 25 over the draw of ((1i, B;); from μ and (=)) Un. for every J E F and g E G.
In(1/5)
Ef(x)y I
(ai)y + 2Rad,.
(((2.)) - g(x) :ggg))ggg)))) + +3V
2m
dux
1 Σ
- ( + +3/ In(1/0)
+
dun Lg(um)
2m
((z)mminf min (1, - (=))1]] (EE 1/2
+ 2Radm
where
(12+ - - -(())()))) ff fe
Radm
k
S
p
Radm (f2 + f(z) : ff E F}) + Rad (1 g())y 9))]
y==1
Proof of Lemma A.I To start, for any f E F and E 9, write
Bf(x), = [(f(x) g(x))y + Eg(a),
The last term is easiest, and let's handle it first: by standard Rademacher complexity arguments (Shalev-Shward & Ben-D 2014), with probability at least 1 8, every g E 9 satisfies
Σ g(:s)). + 2Rad, (((x, y) + g(x) : g egg)) + 3/ /l((1/)) Eg(x), I n 1=1
2n
For the first term, since f X + [0, 1 and g : X [0, 11th by Hölder's inequality
B(f(x) - g(x)), /
(1, g(x)),,) du(z. y)
<
ml,((1,11f()) ((=)11p) du(x, v)
min(1, llf(2) ((x))1p} dux (x) dz)(z)
dun
dux
min [1, ff |alee (..
du (v.)
Once again invoking standard Rademacher complexity arguments (Shalev- Shwartz & Ben-Dave David 2014 with probability at least - 8, every mapping- z + min(1, [f(=) ((>)[g) where E F and g E G satisfies
1 Σ = + 3/ / (in(1))) - =(=)]l)) (z), S
In(1/8)
2m
+ 2Radm
(1
min [1f(2) - s())) (
Combining these bounds and unioning the two failure events gives the first bound.
12

---

Published as a conference paper at ICLR 2021
For the final Rademacher complexity estimate, first note + min(1,r} is 1-Lipschitz and can be peeled off, thus
(1 min (If(z))))))))))))))))))))))))))) - fe
mRadm
((2+ [If(x) - =(>) [(t)))
I mRaam
m
EE, sup SEF DEG
Σ
allf(z)) - 0(
i=1
k
m
Ee sup FEF gEG
<lf(zi) -((z))
y'=1
k
(f==+1(6s- 15== -((=)) : fERBEE))
= Σ
mRadm
Since and have range [0, 11 then (f - g) has range [-1, for every y'. and since r + |r| is p-Lipschitz over [- (for any p E [1, co), combining this with the Lipschitz composition rule for Rademacher complexity and also the fact that a Rademacher random vector c E {+1}m is distributionally equivalent to its coordinate-win
negation -c, then, for every y' [A]]
Radm (1= [=) s(=) EEF 9})
S pRad
((2 ((=
(f(z) g(x)) :f F
= LE, sup sup m JEF DEG 1=1
E (f(x)) - -((z))
LE sup JEF i=1
<i(())) + - E. sup gEn ==1
- <gg()
= =pRad (f2 + f(z)y' : F}) + pRad (fz g(2)y : 9)).
To prove Lemma 1.1 it still remains collect few convenient properties of the softmax.
Lemma A.2. For any E &&& and E {l,...,k:},
2(1 - ((1-,( (v)) 1 + arg max uz].
Moreover, for any functions FF with J f X + R
(
VT:
Rad,, (((x,)) (1 : /EF))= =
Proof. For the first property, let u E IR* be given, and consider two cases. If y = arg max, Us then (v) E [0, 1]th implies
2 (1 - (v)), ž 0 = 1 * arg max
On the other hand, y * arg max; 0i then (,(2, S 1/2, and
2 (v)), > 1 1 [y + arg maxe;]
The second part follows from multivariate Lipschitz composition lemma for Rademacher com- plexity due to (Foster & Rakhlin 2019, Theorem 1); all that remains to prove is that e + (v), is (1/r)-Lipschitz with respect to the foo norm for any u E g² and E [kt]. To this end, note that
d (v) duy
exp(v/7), Ejer exp(0/7),
d duipo
(,(,), exp(v/7), exp(v/>); ,LE, exp(pp/p))
mLE, exp(e/7);)²
13

---

Published as a conference paper at ICLR 2021
and therefore
V (v),ll 2 2exp(u/7)y Ener exp(v/7);
'(, exp(w/7)5)
7
and thus, by the mean value theorem, for any u E I2 and v E IR,, there exists E (u, such that
(w) (u)al = (Von - u) s || u|| (o) s 211100 ulloa
and in particular + (u//v is (1/7)-Lipschil with respect to the &xc norm. Applying the aforementioned Lipschitz composition rule (Foster & Rakhlin 2019 Theorem 1),
( Rada Radn(())
v
Rad,, (1(x,)) (,(()) :fa =6
Lemma 1.1 now follows by combining Lemmas A. and A.2
Proof of Lemma 7.7 Define & 1 Φy. The bound follows by instantiating Lemma A.1 with = and the two function classes
:= = {(x, v) + ()(()))) EFF and 2g ((x, v) ~ : 9),
combining its simplified Rademacher upper bounds with the estimates for Radm ( (Qf) and Rad,, (2x) and Rad, from Lemma A.2 and by using Lemma A.2 to lower bound the left hand side with
Ba((())), B(1 - (f(:))) 2 2
1
arg max f(x) # w].
1
and lastly noting that
IV(((z))) - +(((2))) = 1 Σ || (,(())))) 1 ( = Dy.m(sgg)-
To complete the proofs for Section 1.1 it remains to handle the data augmentation error, namely the term [ddux/dv.ll so. This proof uses the following result about Gaussian kernel density estimation.
Lemma A.3 (See (Jiang 2017 Theorem and Remark 8)). Suppose density is a-Hööler contin- uous, meaning (p(x) p( ] I Callæ lzz - x'11 for some Ca and a E [0, 1]. There there exists a constant C 2 O, depending on a, C., max p(z), and the dimension, but independent of the sample size, so that with probability at least 1 1/n, the Gaussian kernel density estimate with bandwidth o² where
+2) satisfies
In(n) (2ax/)))
sup 1p(x) -Px(x)) S CV FER
The proof of Lemma 1.2 follows.
Proof of Lemma 7.2 The proposed data augmentation measure Vn has density Pn,3 over [0, 1]d, and it has the form
Pn,s(x) = + (1- (2),......
where B 1/2, and p. the kernel density estimator as described in Lemma A.3 whereby
Inn (2a+F]
Pn - p(x)) S en :
The proof proceeds bound ||dux/du..llo> /1// by considering three cases.
14

---

Published as a conference paper at ICLR 2021
If x & [0, 174 then p(z) = 0 by the assumption the support of jax, whereas pn, 2
Pa(a)/2 > 0, thus p(z) p())
I E [0, 1]d and p(x) 2 nn,. then (n))(()) 2 (1 -1- 3)p(z) (1-9)p(z) - -en) 2 fn/2, and
p(z)
+ p(x) (m)
Pn.0 (x)
(o)
$ 8p(r)
(1 - (11)))p(a) Pr (1)
pn,3(22)
pn,
Bp(xz)
(1 - Bn
$ 1
(1 (1- (p(x) - Cn)
en/2
3
1 (1-B)(1 <En/p(x) +1
44
I E [0, 1jd and p(x) < no, since pn, (x) 2 B 1/2, then
p(r)
2En
den. B
(x)
Combining these cases, |ddxx/aum 1oc 11p/2a.0
m 1en S 4 den.
B REPLACING SOFTMAX WITH STANDARD MARGIN (RAMP) LOSS
The proof of Lemma I.I was mostly a reduction to Lemma A. which mainly needs bounded functions; for the Rademacher complexity estimates, the Lipschitz property of dh, was used. As such, the softmax can be replaced with the (1/7)-Lipschin ramp loss as is standard from margin-based generalization theory (c.g.. in multiclass version as appears in (Bartlett al. 2017a)). Specifically, define My : & + [0, 1] for any coordinate j as
2 x 0,
(n(r); =000==00000 (u5 arg max Byy) v'
where (2)z) ==
E (0,
2 %
We now have 1 [arg max, f()) S (f without a factor of 2 as in Lemma plug it into the general lemma in Lemma A.I to obtain the following corollary.
A.2 and can
Corollary B.1. Let temperature (margin!) parameter > O be given, along with sets of multiclass predictors F and G. Then with probability least 1- 28 over an iid draw of data ((z), I- from and (2, R from Vn every f E F and g E G satisfy
Pr[arg max f(x) + vl <
dux
m
(M,()) - -M, + M,(g(x))),
Σ
R
du
m
t=1
k//
dpxx
Vi
(Rad,n (F) (eadm(9)) + (g)
Y
dvn
y
In(1/5)
dux
+ 3
1
dun
m
Proof. Overload function composition notation to sets of functions, meaning
M, == + MM,())),,,,,,,,, FF
First note that M, is (2/7)-Lipschir with respect to the fxc norm, and thus, applying the multivari- ate Lipschitz composition lemma for Rademacher complexity (Foster Rakhlin 2019 Theorem 1)
just as in the proof for the softmax in Lemma A.2
Rad, (M, o F) = δ (add((F))
2
15

---

Published as a conference paper at ICLR 2021
with similar bounds for Radm (M,, g) and (M,, g). The desired statement now follows by combining these Rademacher complexity bounds with Lemma I.I applied to My o F and My o g. and additionally using 11 aar maxy f y) (f(xx))
C SAMPLING TOOLS
The proofs of Lemma 3.1 and Lemma 3.2 both make heavy use of sampling.
Lemma C.1 (Maurey (Pisier 1980)). Suppose random variable V is almost surely supported on a subset S of some Hilbert space, and let (Vi,..., Vk) be lo iid copies of V. Then there exist
(V1,..., Vx)= E Sth with
2
EV Σ
V.
S
E Vi.
EV
Σ V2
1 k
V
EVIE
1 - EIII
-
sup | VES
Vi
The first inequality is via the probabilistic method. For the remaining inequal- ities, by expanding the square multiple times,
Proof of Lemma C.7
E
EV-
1 k
Σ
V
E
1
Σ BV - Vi +
Σ
EV
EV Vs)
V1 V/2
Vi
12
Ev 11 - -EVIE=
1
EIIVI - IEV 18
S -
S k ves
sup V
A first key application of Lemma C.1 is to sparsify products, as used in Lemma 3.2
Lemma C.2. Let matrices A Rdxm and B Ruxm be given, along with sampling budget k. Then there exists a selection (ii,..., in) of indices and a corresponding diagonal sampling matrix M with at most k nonzero entries satisfyyng
|A
e e7 1
and ||AB AMBTI S 1 1111911B11
M
Aee,
Proof of Lemma C.2 For convenience, define columns a; == Ae; and b, = Be, for E (1..... m). Define importance weighting B; = (Il=:1//1.A Al))) whereby E, Br 1, and let V
be a random variable with
Pr V = + = 3,,
whereby
m 3 a,,3 = Σ (Be)) = Σ e
m
m
EV
B = A A = =B,,
1 Σ 8 |1:8
3 |as IIbe 1 Σ || |1 = || -1B
By Lemma C.I there exist indices (i.,... is) and matrices V/J = 3.. ai, bi, with
ABT ΣΣ V
<
EV
k ΣV
1/
[1410 | - ||BBi]] = 1A1B
To finish, by the definition of M,
Σ V, $/4
Σ
3
Σ
e, c/
3 B".
4
k
k
i
16

---

Published as a conference paper at ICLR 2021
A second is to cover the set of matrices W satisfying norm bound ||* 22.1 S The proof here
is more succinct and explicit than the one in (Bartlett et al. 2017a, Lemma 3.2).
Lemma C.3 (See also (Bartlett al. 2017a| Lemma 3.2)). Let norm bound integer k be given. Define a family of matrices
X Rexd and
x|
lE
k
M =
81 E (+1) (I,...,,,,,i E ( (1....,d)) dd (.......)}
Xe
Then
min |WX' - W S 1l W St WEM
[M] S (2nd)*
sup
Proof. Let W E mmd be given with || 22,11 S
Define Sij := Way/ W v and note
W WX1ll1Xeel12 r|| 1 e (Xe,)
W Σ -
Σ [Xe;(
Σ
x||
|ee
2.
Note by Cauchy-Schwarz that
| 12
rIX Σ
Σ
W7 1
x||
potentially with strict inequality, thus is not probability vector. To remedy this, construct proba- bility vector p from q by adding in, with equal weight, some Ug and its negation, so that the above summation form of W goes through equally with and with
Now define iid random variables (V1,..., Vi),, where
Pr[Vi = Uny] = Pij:
EV
Σ
PiJUss
Σ is
Un W
(Xe,)
||Us||| =
.r|x = -sisll ||c:|12
-r||X||, = r||
||Xe
|Xe,lla
B||Vi||
Pis 1 S Σ 2 || = 1
By Lemma C.1 there exist (Vi,.... Vi)) E 5 with
W
Σ Vi
<
EV
Σ Vi
k
Furthermore, the matrices Vi have the form
1 Σ V
s (Xe,)
ste ej Xe |I
- =W=,
T
Xe
where We M. Lastly, note |M| has cardinality at most (2nd)*
D PROOFS FOR SECTION
The bulk of this proof is devoted to establishing the Rademacher bound for computation graphs in Lemma 3.1 thereafter, as mentioned in Section 3 suffices to plug this bound and the data augmentation bound in Lemma 1.2 into Lemma [.I and apply pile of union bounds.
As mentioned in Section this proof follows the scheme laid out (Bartlett et al., 2017a), with simplifications due to the removal of "reference matrices" and some norm generality.
17

---

Published as a conference paper at ICLR 2021
Let cover scale and per-layer scales (fi....,EE) ,L) be given; the proof will develop a covering number parameterized by these per-layer scales, and then optimize them to derive the final covering number in terms of c. From there, Dudley integral will give the Rademacher bound.
Proof of Lemma 3.7
Define b, == bivn for convenience. As in the statement, recursively define
x== X == oi (IW.I.D))))).)))
The proof will recursively construct an analogous cover via
X7 =
X- : (WAIDE))X-)
where the choice of W; depends X,-1, and thus the total cover cardinality will product (and not simply sum) across layers. Specifically, the cover N₁ for W, is given by Lemma C.3 by plugging in [IT D. 1l: S b,, and thus it suffices choose
rf e?
cover cardinality A =
whereby
min [W W.D.X W.EM
By this choice (and the cardinality estimate in Lemma
the full cover N satisfies
r
In | = Σ In WA
In(2m²))
To optimize the parameters (cI,..., CL). the first step is show via induction that
|x - X711e
II
SIP--
1=j+1
The base case is simply [|x] - X = |
X = 0. thus consider layer i > 0. Using the
inductive formula for X; and the cover guarantee W,,
x7
x:|
0. (W. WWW.T/AAAALLL--OVWWWWWWAA -.VV(..
(WIL
W.II -W, | +.
S P:
$ I.
XL_ Xi_ - -F
I sipi Σ
GP3 II
SIPI + P: (W; -,),.
151-1
1=++1
Σ GPj
II
Σ SPs II
Spp
P.G: S
S1P-- i=+1
1
|=t
15i
To balance (e,,..., (z), it suffices minimize a Lagrangian corresponding the cover size subject to an error constraint, meaning
L
I Σ GB
L
((,,))
=
a
where o; := : In(2m?),
::
II
Sipl:
1=1
1=++1
whose unique critical point for >> 0 implies the choice
20s
1/3
where Z = Σ 32)/33
= Z
8
18

---

Published as a conference paper at ICLR 2021
whereby -X
X7 ll & automatically, and
62 l2mm²²
In | z²
(2cxs/ /3)22/3
2
2/382/33 32/3 In(2m2)1/8
Σ
//
///88//8
1n(2m2)1/388)
2////3
i
i
24/3 In (2mm²
L
2/3-
72
Σ
r.bips
StPt
2²
1mi+1
as desired, with J introduced for convenience in what is come.
For the Rademacher complexity estimate, by standard Dudley entropy integral (Shalev-Shward & Ben-David 2014), setting == max(T, 1/3} for convenience,
(g) < inl 4CV v VFe
= inf VC vn -inf- 4n
d
which is minimized at = 3f/ Vn. whereby
nRad(G) < 12f + 67 Inn 12f (nfFn////// 12 - In(3f)) S 12F 127 + 4.
This now gives the proof of Theorem 13
Proof of Theorem L.3
With Lemma
Lemma 1.2] and Lemma 3.1 out of the way, the main work
of this proof is to have an infimum over distillation network hyperparameters (6, 8) on the right hand side, which is accomplished by dividing these hyperparameters into countably many shells, and unioning over them.
In more detail, divide (6, 5) into shells as follows. Divide each b, and r; into shells of radius increasing by one, meaning meaning for example the first shell for by has by 1, and the jth shell has b E (j - 1. and similarly for rę; moreover, associate the jth shell with prior weight (b:) == (j(j + 1)) - whereby Σ5²1 (b,) = Meanwhile, for s; use a finer grid where the first shell has 8; S I/L, and the jth shell has s; E (G - 1)/L. L.), and again the prior weight is (s()) = (i(i + 1) Lastly, given a full set of grid parameters (b, F, 8), associate prior weight q(5, F, 8) equal to the product of the individual prior weight, whereby the sum of the prior weights over the entire product grid is 1. Enumerate this grid in any way, and define failure probability 8(5, F, 5) == 8- q(b, F, F).
Next consider some fixed grid shell with parameters (8, s") and let H denote the set of networks for which these parameters form the tightest shell, meaning that for any E H with parameters (6, then (8,,".3 < (b+ 1, + 1, + 1) component-wise. As such, by Lemma 1.1 with probability least 1 8(b), F) each g H. satisfies
dux de
2 n
Prjargmi max f(x) + y] <
m (f.g)
Σ
(1 (1-(((9()))))
y
A-3/2
ddpx
[Radm(F) + Rad, (?)) + Vl
+ 5
Rad, (P1)
γ
dum
In(g(E', 77, ()) + In(1/0) (
dux
+ 6
2n
dv
m
19

---

Published as a conference paper at ICLR 2021
To simplify this expression, first note by Lemma 3.1 and the construction of the shells (relying in particular on the finer grid for 8, to avoid a multiplicative factor L) that
2/3
3/2
1 vn
Rad (H) (H)
Mips
II sip 1=++1
L II 1=1-1
2/3
3/2
Σ
(r: + 1)(b, + 1)p;
(st + 1/L)
vn
2/3
3/2
=
Σ r.bipp
II
SIPt
1=++1
and similarly for Rad, (H) (the only difference being /m replaces Vn). Secondly, absorb the term In(g((', F0 F))5) noting that In(a) z In(>>) + (a - /2)/(>²), and also using pj 2 1, then
2/3 2/3 2/3 In(g(F (,,)))))= 0 In II (ra + 1) + 1)²((== 1)r)}² =0 L. L. In
8
= Ō
L +
In 2/3 2/3 2/3 In II
Pi
s;
2/3
0
T. + 1n
E
2/3 8//
2/3
7/2
1>1
2/3
=
++
Σ
rab II
722
1=i+1
L.
2/3
1
Ō
1++
Σ
rybipe
S1P1
72
i=++1
Together,
djpx
a $ Pym (f.g) ().m(f + Σ
Pr(arg max f(x) #yl s 2
(1 Φy (g((())))
//
du
m
1=1
1/2/2
dpx
ln(1/5)
dux
+
Radm (F) + 6v
1
dv
2n
dv
+ δ
V
1 +
dux de
n2
Σ
ribips
II 1mi+1
L
8iPi
2/3.
3/2
Since h was arbitrary, the bound may be wrapped in infgER- Similarly, unioning bound- ing away the failure probability for all shells, since this particular shell was arbitrary, an infinum over shells can be added, which gives the final infimum over (6, F, 8). The last touch is to apply Lemma 1.2 to bound /dux/av_lloo
E PROOF OF STABLE RANK BOUND, THEOREM T.4
The first step is to establish the sparsification lemma in Lemma 3.2 which in turn sparsifies each ma- trix product, cannot simply invoke Lemma C,2 prepprocessing necessary control the element- wise magnitudes of the resulting matrix. Throughout this section, define the stable rank matrix W as sr(W)= := ||W]]|/ /|[l]l [ (or 0 when W = 0).
20

---

Published as a conference paper at ICLR 2021
Lemma E.1. Let matrices A E R and B R be given, along with sampling budget k. Then there exists a selection (f1...., ix) of indices and a corresponding diagonal sampling matrix M with most k nonzero entries satisfying
Zi ei, b |as,1
4 k and |A AMB & 1A111BB.
M
where Zi S |1
Proof. Let 0 be parameter be optimized later, and define subset of indices 5 == {i mL. ||Ael] 2 7) with S == (l,...,,, m} S. Let A, denote the matrix obtained by
zeroing out columns not in S, meaning
A, = Σ (Ae))e)
iES
whereby
|AB A,B ||, S 1| A+l |B] S ||B||
Σ
|| < STVM
iESt
Applying Lemma
C.2 A, B" gives
M ||A+|| k
C A e
Σ j=1
Zz 0 |A,e;
such that
|A,B A,MB S k
I BI1
1
where Zi is specified by these equalities. To simplify, note ||A S ||||| and A,M AM. Combining the two inequalities,
|| AMB S |AB A, + ||, A,MB"I S TTmmBB| + Vk ||
To finish, setting T ||||/ mmk gives the bound, and ensures that the scaling term Zi, satisfies, for any iz E S,
1
|A
2, 11
||A||
A
kT
k
With this tool in hand, the proof of Lemma 3.2 follows.
Proof of Lemma 3.2 Let Xj denote the network output after layer j. meaning
x-= = =W,,,(WxX,_))
whereby
|X - 1o,, a < IW,
< |[, |2l ll. < |X] II Will.
The proof will inductively choose sampling matrices (M My) as in the statement and con- struct
x=== (W,
where II denotes projection onto the Frobenius-norm ball of radius I ||al]2 (whereby I1,X, X2), satisfying
X, - s
||
W ll2 p=1
I
sr(We) h;
which gives the desired bound after plugging in j T.
21

---

Published as a conference paper at ICLR 2021
Proceeding with the inductive construction, the base case is direct since Xu X Xo and Xo - O, thus consider some > 0. Applying Lemma E. to the matrix multiplication W, with k; samples, there exists multiset of S coordinates and corresponding sampling matrix Mj, as specified in the statement, satisfying
- - Vky
W3M,
I WW S
1 Vky
||
X [W
K
Using the choice X3
== (W,,
[x - X, 1
O,(W5X]-11 -15o ( (WG,
W,X W,M,,y-1
W W - -1|
W - W, ||, + |, - WW,,,
11
<
W, 112 Xy-1 X x
+ kky
||
11Wil2
sr(Wa)
sr(W,,
WV l
||
II
Will2
Σ
+
|
[Wll
ki
i5J
sr(W:)
sr
$ |X
Wall
as desired.
To prove Theorem T.4 via Lemma 3.2 the first step a quick tool to cover matrices element-wise.
Lemma E.2. Let A denote matrices with at most k2 nonzero rows and kn nonzero columns, entries bounded in absolute value by b, and total number of rows and columns each at most Then there exists a cover set M C A satisfying
2bykik2
MM| S tkz
and
sup min ||A Alb.c.. Sc AEA
Proof. Consider some fixed set of k2 nonzero rows and 1 nonzero columns, and let Mo denote the whereby
covering set obtained by gridding the kn hi entries at scale va
ky
26y k
Moo <
For any A E A with these specific nonzero rows and columns, the Á E Mo obtained by rounding each nonzero entry of to the nearest grid element gives
| - Āll = IAy
<
Σ Vkik2
Σ
=
kink2
i,j
The final cover M is now obtained by unioning copies of MM for all submatrices of size kg x k1-
(MT) (1t) S k possible
The proof of Theorem 1.4 now carefully combines the preceding pieces.
22

---

Published as a conference paper at ICLR 2021
Proof of Theorem 1.4 The proof proceeds in three steps, as follows.
1. A covering number is estimate for sparsified networks, as output by Lemma 3.2
2. A covering number for general networks is computed by balancing the error terms from Lemma 3.2 and its cover computed here.
3. This covering number is plugged into Dudley integral to obtain the desired Rademacher bound.
Proceeding with this plan, let ........ Xx) be the layer outputs (and network input) exactly as provided by Lemma 3.2, Additionally, define diagonal matrices Dj == Σiesşto ejta (with Dr =
I, where the "!" denotes unique inclusion; these matrices capture the effect of the subsequent sparsification, and can be safely inserted after each W without affecting Xj. meaning
x IW,, -
Let per-layer cover precisions (.),)..,er. be given, which will be optimized away later. This proof will inductively construct
= x- [W,
where Wj is a cover element for D, and inductively satisfying
||]]
X1ı| s || 1/2
To construct the per-layer elements Wj, first note by the form of Mj (and the scaling Z, provided by Lemma 3.2 that
W [Wee:l
m
= max (D, (D,,,Mj)a max [W,l < 2,
I 11
kz-i
Consequently, by Lemma
there exists a cover C₁ of matrices of the form D,W,M, satisfying
k
8yks-1
2b /Dykyy
2/|W5 lly kyym
[c,l S m 4
S -
Ej
6j
and the closest cover element W,C, to Dj satisfies [1,, WD,W,M, - W3ll+ S Sej
Proceeding with the induction, the base case has || j O. The first step is to estimate the spectral norm D, W,W. which can be coarsely upper bounded via
-XTI| ||XT X 0, thus consider
1,, & IID,W,M,IB <
m Σ WW = Σ |
K < 1W
By the form of Xj and X,,
| - X|11 = -,
< -,,,
< IDDNANAAAL-DDMMWAXX.ALII...
< 1I -,, W5
< s/mllW,l 1 0- 1)/2
W + II WW
< X 1
6
23

---

Published as a conference paper at ICLR 2021
which establishes the desired bound on the error.
The next step is to optimize ky. E be arbitrary, and set e = - m I W[alle whereby
Cc,l t ALLVk,IIII II. Walee K
- S 2
The overall network cover N is the product of the covers for all layers, and thus has cardinality satisfying
AmLL ky
X II.
IW
In M
S Σ In C2 2 Σ ky Inm +
Σ 1kkj-1l1
C
4mLy kg |Ix
2 Σ k3 mmm+ 22g In 1
2
+
2N
2
Σ In Wylle
Ej
To choose (ki,..., :.), letting X1 denote the output of the original unsparsified network, note firstly that the full error bound satisfies
|x7 - x |X
X7 1x7 XLI
where a; := ||
Will2
sr.)..
2
To choose k, the approach here is to minimize a Lagrangian corresponding the cover cardinality, subject to the total cover error being e. Simplifying the previous expressions and noting 2ki S k3 + 1 whereby the dominant term in [W] is E3 kz. consider Lagrangian
L(ki ... R1, A)
Σ k +
Σ
v K4
2 2)¹
which has critical points when each k; satisfies
k 5/2
Oy 4'
thus k; := o / with Z == 2/ 4/5/2.
As sanity check (since was baked into the Lagrangian), plugging this into the cover error indeed gives
oj
| - X < Σ a;
Z
4/5
c
a
e. 2
To upper bound the cover cardinality, first note that
Σ k 2
Σ
4/5
4 e
Σ
4/5
5
a
a;
whereby
In =
Σ k?
Σ In [Wille]
8
where B
-1
=
Σ
In Iw..ll)).
The final step is to apply a Dudley entropy integral gives
& Ben- 2014), which
/B
nRad(F) inf 45VTm 12
de
inf
12
VB
{
2
5
24

---

Published as a conference paper at ICLR 2021
Dropping the negative term gives expression of the form aç b/Ş, which is convex in Ç > 0 and has critical point at Ç² b/a, which after plugging back in gives upper bound 2vab, meaning
1/2 8V3n
(Rad(F) (Av 12 3
Dividing by and expanding the definition of 3 gives the final Rademacher complexity bound.
25


Reviews:
[{"review_id": "y7t6GQpr25i", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper provides generalization bounds for seemingly complex neural networks\non the basis of much simpler ones. That is a good idea and something that is currently very relevant I think and the approach seems to be the natural one to take. \n\nEssentially the bounds proved, bound the out of sample error\nwith a form of in sample error, average difference in predictions between complex and simple network, and complexity term for the simple network in terms of Rademacher complexity. \n\nThe authors provide a general framework which can be applied and show a particular way of using it and use recent results (Bartlett et al) to provide interesting application of the framework.\n\n\nIn terms of the actual bound achieved there are a few things I feel should be discussed more.\n\nIn Lemma 1.1.\nThe in-sample error. First it is not the in-sample classification error but the sort of a margin error that essentially is never zero for any prediction. Usually margin errors have a\nlinear penalty on the wrong side of the margin and zero on the correct side of the margin.\nSecond, there is a factor 2 in front of it. Normally, and in uniform convergence bounds, there are no constants in front of the in-sample error. (The other constants are of no concern).\n\nThe authors state that their work can be applied to  generalization bound of Arora et a. 18 that only worked for a compressed network but not the original one. Given the above comments about the actual bound achievable it is not clear to me what exactly one would get out of \"distilling\" the construction in Arora et al, but it seems it does not become the same bound as for the compressed network as shown by Arora et al. Comments on that would be appreciated.\n\nAnother small question: What does the early distillation phase on page 4 means (below lemma 1.3)?\n\n\nI like the experimental setup, particularly using gradient descent to try and find a network to distill to.\n\nOverall, I think the paper is well written including the proof sketches that make me believe the statements are actually provable (I did not rigorously check)\n\nOverall, I think this is an interesting paper and should be accepted. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "mUH2Hl3lCDG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper overall is of good quality. The story of the work is well-written which makes the contributions easier to digest. One suggestion would be to comment a bit more on the relevance of the margin distribution for readers that are unfamiliar with it, for instance, in Figure 1, the term margin distribution is thrown without explaining why one should look into it. \n\nThe topic of this work is of great significance given that understanding the generalization error of neural nets is relevant to the community.\n\nIn terms of theoretical contributions, the results seem sound although I did not check the proofs in much detail. Most of the proofs are based on known techniques to find upper bounds. Authors also show some experiments on the behavior of their bounds, and in particular, on margin distributions.\n\nOverall, I like the idea of bounding complex models by distilled models (simpler ones), and as authors point out, to make this approach work one needs to have a solid way to find such distilled models. If my understanding is correct, the \"weak\" part of the work is that authors do rely on sparsification to find distilled models. While valid, my intuition is that such distillation process could still lead to large bounds. Which seem to be the case of Figure 3(b)? \nTo give an example, consider a task where an overparametrized complex network generalizes well in practice, it seems unlikely to me that a (very) sparse or pruned network would \"perform similarly\". That is, the \"sparsified\" model to be \"close in performance\" to the complex model would not be simple enough to give a non-vacuous upper bound. I would appreciate if authors can comment on this concern.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "iOI6zFoC-DL", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper provides an upper boundary of the generalization error of networks: the sum of its training error, the distillation error, and the complexity of the distilled network. Then, it also provides an instantiation of the lemma applicable to residual networks, an explicit compression analysis via pruning with a corresponding generalization bound, and empirical supports.\n\n**Pros**\n\n* The idea of applying distillation to tackle the generalization dilemma seems interesting, and the proof seems rigorous.\n* Experiments in section 2 on the width independence, depth, and random label are reasonable for me.\n\n**Cons**\n\n* A comparison (e.g. on the tightness of the bound, or the correlation with generalization) between the proposed distillation-based generalization bound and existing generalization bounds in literature may help demonstrating the effectiveness of the proposed bound.", "extra_scores": {}, "extra_text": {}}, {"review_id": "QEZB78snd7v", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The generalization performance of learning algorithms characterizes their ability to generalize their empirical behavior on training examples to unseen test data, which provides an intuitive understanding of how different parameters affect the learning performance and some guides to design learning machines. Different from the traditional error analysis, this paper focuses on bounding the divergence bettween the test error and the training error by the the corresponding distillation error and distillation complexity, e.g., test error  is bounded by training error + distillation error + distillation complexity. The current learning theory analysis may be important to understand the theoretical foundations of distillation strategy in deep networks. However, some theoretical issues should be illustrated to improve its readability, e.g,. \n1)What is the relation between the original network complexity and the corresponding distillation error +distillation complexity? \n2)Is the derived upper bound (e.g., Theorem 1.2) tighter than the traditional one? Please present a table to compare it with  the related error bounds.\n3)What are necessary/sufficient theoretical conditions for the effectiveness of distillation strategy (from the generalization error bounds)?\n4)It may be better to state some discussions for the lower bound on the generalization error. Does it also relate with distillation complexity?  \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a novel generalization bound for neural networks using knowledge distillation. In particular, they argue that

"test error <= training error + distillation error + distillation complexity" where the distillation complexity is typically much smaller than the original complexity of the neural network. This is motivated by the empirical findings that neural networks can typically be significantly compressed in practice using KD without losing too much accuracy. 


I found this result novel and the direction is very promising. This is a clear accept for ICLR. 
Decision: Accept (Spotlight)