PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization
Authors: Sanae Lotfi
Marc Anton Finzi
Sanyam Kapoor
Andres Potapczynski
Micah Goldblum
Andrew Gordon Wilson
Venue: NeurIPS 2022 Accept (2022)
Keywords: PAC-Bayes
Generalization
Compression
Generalization Bounds
PAC-Bayes Bounds
Occam's Razor
Transfer Learning
Data-Dependent Priors

Abstract: While there has been progress in developing non-vacuous generalization bounds for deep neural networks, these bounds tend to be uninformative about why deep learning works. In this paper, we develop a compression approach based on quantizing neural network parameters in a linear subspace, profoundly improving on previous results to provide state-of-the-art generalization bounds on a variety of tasks, including transfer learning. We use these tight bounds to better understand the role of model size, equivariance, and the implicit biases of optimization, for generalization in deep learning. Notably, we find large models can be compressed to a much greater extent than previously known, encapsulating Occam’s razor.

PAC-Bayes Compression Bounds So Tight That They Can Explain Generalization
Sanae Lotfi'
Marc Finzi*
Sanyam Kapoor
Andres Potapezynski"
Micah Goldblum
Andrew Gordon Wilson
New York University
Abstract
While there has been progress in developing non-vacuous generalization bounds for deep neural networks, these bounds tend to be uninformative about why deep learning works. In this paper, we develop compression approach based on quan- tizing neural network parameters in linear subspace, profoundly improving on previous results to provide state-of-the-art generalization bounds on variety tasks, including transfer learning. We use these tight bounds to better understand the role of model size, equivariance, and the implicit biases of optimization, for generalization in deep learning. Notably, we find large models can be compressed to a much greater extent than previously known, encapsulating Occam's 's razor. We also argue for data-independent bounds in explaining generalization.
Introduction
Despite many parameters than the number of training datapoints, deep learning models gen- eralize extremely well and can even fit random labels [72]. These observations are not explained through classical statistical learning theory such VC-dimension Rademacher complexity which focus on uniform convergence over the hypothesis class [53]. The PAC-Bayes framework, by con- trast, provides a convenient way of constructing generalization bounds where the generalization gap depends on the deep learning model found by training rather than the hypothesis set as whole. Us- ing this framework, many different potential explanations have been proposed drawing on properties of a deep learning model that are induced by the training dataset, such as low spectral norm [57], noise stability [2], flat minima [30]. derandomization [55], robustness, and compression [2, 73).
In this work, we show that neural networks, when paired with structured training datasets, are sub- stantially more compressible than previously known. Constructing tighter generalization bounds than have been previously achieved, we show that this compression alone is sufficient to explain many generalization properties of neural networks. In particular:
1. We develop a approach for training compressed neural networks that adapt the com- pressed size to the difficulty of the problem. We train a random linear subspace of the parameters [45] and perform learned quantization. Consequently, achieve extremely low compressed sizes for neural networks at a given accuracy level, which essential for our tight bounds. (See Section 4).
2. Using prior encoding Occam's razor and our compression scheme, we construct the best generalization bounds to date on image datasets, both with data-dependent and data-
'Equal contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

independent priors. We also show how transfer learning improves compression and thus our generalization bounds, explaining the practical performance benefits of pre-training. (See Section 5).
3. PAC-Bayes bounds only constrain the adaptation of the prior the posterior. For bounds constructed with data-dependent priors, we show that the prior alone achieves performance comparable to the generalization bound. Therefore argue that bounds constructed from data-independent priors are more informative for understanding generalization. (See Sec- tion 5.2).
4. Through the lens of compressibility, we are able to help explain why deep learning models generalize on structured datasets like CIFAR-10, but not when structure is broken such as by shuffling the pixels or shuffling the labels. Similarly, we describe the benefits of equivariant models, e.g. why CNNs outperform MLPs. Finally, we investigate double descent and whether the implicit regularization of SGD is necessary for generalization. (See Section 6).
We emphasize that while we achieve state-of-the-an results in both data-dependent bounds and data- independent bounds through our newly developed compression approach, our goal is to leverage these tighter bounds to understand generalization in neural networks. Among others, Figure 1 high- lights some of our observations regarding (a) data-dependent bounds, (b) how our method trades-off between data fit and model compression in relation to generalization, and (c) the explanation of several deep learning phenomena through model compressibility using our bounds.
All code to reproduce results available here.
Dalugaate [19]
Compressed Size (KB)
with
without
Hookkiing Sound Onta Dependeen: Titrr
Error Bound
600
Eiror Bounde
PMC Sayee Bource
60
Classification
25
Drlugatte et [19)
Train Error
Pemzz-Crtize et at (57)
40
KL
20
Bound
16
Ou a..77
20
0.2
0.4
0,6
0.8
10a
10
Transfer Learning
Shuffle
Rotation
Fraction of
Subspace Dimension (d)
Pooels
Equivariance
(a) Pitfalls of data-dependent bounds
(b) Adaptive compression
(c) Deep learning phenomena
Figure 1: The power of data-independent subspace compression bounds for explaining deep learning phenomena. Bounds for 10 except (c)-rotation, which is roLMNIST. (a) We show that the simple Hoeffding bound computed only on the data-dependent prior and evaluated on the remainder of the training data (essentially measuring validation loss) achieves error bounds that are competitive or even better than data-dependent bounds obtained by previous works, showing that data-dependent PAC-Bayes bounds do not explain generalization any further than the prior alone. Instead, data-independent bounds are more informative for understanding generalization (see Section 5.2). (b) Training eπrоr, the KL term (compressed model size measured in KB), and our PAC-Bayes bound as the subspace dimension is varied. For fixed network, our method provides an adaptive compression scheme that trades off compressed size with training error, finding the optimal bound for a given model and dataset. (c) We compute our data-indeeendent bounds for model trained with and without: transfer learning, shuffling the pixels, and the rotation-equivariane property- Our bounds identify the positive impact transfer learning, how breaking structure in the data by shuffling pixels hurts the model, and that rotationally equivariant models improve generalization rotated data. Each of these interventions impact the compressibility of the models. See Section 6 for more details.
Related Work
Optimizing the PAC-Bayes Bound. Dziugaite and Roy [18] obtained the first non-vacuous gen- eralization bounds for deep stochastic neural networks on binary MNIST. The authors constructed a relaxation of the Langford and Seeger [41] bound and optimized it to find a posterior distribution that covers a large volume of low-loss solutions around a local minimum obtained using SGD. Ri-

---

Table 1: Non-vacuous PAC-Bayes bounds obtained on popular image classification datasets in deep learning. * indicates bounds obtained using data-dependent priors (Section 5.2). X indicates that either the method does not support multi-class problems or that completely reliant on data-dependent priors and therefore cannot result in data-independent bounds. Additionally, we add Binary MNIST for reference a benchmark used in earlier works.
Non-vacuous PAC-Bayes hounds (%) MNIST FMNIST
Reference
Binary MNIST
CIFAR-10
CIFAR-I00
ImageNet
Dziugaite and Roy [18]
16.1
X
X
X
X
X
Rivasplata et al. [60]
2.2
X
X
X
X
X
Zhou et al. [73]
46
91.6
100
100
96.5
Dziugaite ct al. [19]
11*
38'
23"
x
X
Pérez-Ortiz et al. [59]
21.7/1.5'
49.1
90.0/16.7*
100
X
Our bounds
11.6/1.4"
32.8/10.1"
58.2/16.6"
94.6/44.4"
93.5/40.8
vasplata et al. [60] further extended the idea by developing novel relaxations of PAC-Bayes bounds based on Blundell et al. [6].
Model Compression and PAC-Bayes Bounds. Noting the robustness of neural networks to small perturbations [29, 30, 40, 39, 37, 57, 8), Arora et al. [2] developed compression-based approach that uses noise stability. Additionally, they used the ability to reconstruct weight matrices with random projections to study generalization of neural networks. Subsequently, Zhou et al. [73] developed a PAC-Bayes bound that uses the representation of a compressed model in bits, and added noise stability through the use of Gaussian posteriors and Gaussian mixture priors. Furthermore, they achieved even smaller model representations through pruning and quantization [27, 10). Our compression framing is similar Zhou et al. [73] but with key improvements. First, we train in a lower dimensional subspace using intrinsic dimensionality [45] and FiLM subspaces [58] which proves be more effective and adaptable than pruning. Second, develop more aggressive quantization scheme with variable length code and quantization aware training. Finally, we exploit the increased compression provided by transfer learning and data-dependent priors.
Dziugaite et al. [19] demonstrated that for linear PAC-Bayes bounds such Thiemann et al. [64], tighter bound can be achieved by choosing the prior distribution to be data-dependent, i.c., the prior is trained to concentrate around low loss regions on held-out data. More precisely, the authors show that the optimal data-dependent prior is the conditional expectation of the posterior given a subset of the training data. They approximate this data-dependent prior by solving variational problem over Gaussian distributions. They evaluate the bounds for SGD- trained networks on data-dependent priors obtaining tight bounds on MNIST, Fashion MNIST, and CIFAR-10. In a similar vein. Pérez-Ortiz al. [59] combine data-dependent priors [19] with the PAC-Bayes with Backprop (PBB) [60] to obtain state-of-the-ar! PAC-Bayes non-vacuous bounds for MNIST and CIFAR-10 using data-dependent priors.
Data-Dependent Priors.
Downstream Transferability. Ding et al. [16] investigate different correlates of generalization derived from PAC-Bayes bounds predict the transferability of various upstream models; however, because of this different aim they do not actually compute the full bounds.
Our focus is to achieve better bounds in order to better understand generalization in deep neural networks. For example, we investigate the effects of transfer learning, equivariance, and stochastic training on the bounds, and argue for the importance of data-independent bounds in explaining generalization. We summarize improvements of our bounds relative to prior results Table
3 A Primer on PAC-Bayes Bounds
PAC-Bayes bounds are fundamentally an expression of Occam's razor: simpler descriptions of the data generalize better. As an illustration, consider the classical generalization bound on a finite
hypothesis class. Let R(h) = +. Σm= (h (2;) ) be the empirical risk of a hypothesis with [H| 0o. Let e be the 0-1 loss, and let R(h) [[[(()) denote the population risk. With
H,
3

---

probability at least 1 - 6, the population risk of hypothesis h using n data samples satisfies
log [H1] + log(1/6)
R(h) S R(h) +
V
2n
In other words, the population risk is bounded by the empirical risk and complexity term log [H] which counts the number of bits needed to specify any hypothesis h E H.
But what if we don't it believe that each hypothesis is equally likely? If we consider a prior distribution over the hypothesis class that concentrates around likely hypotheses, then we can construct variable length code that uses fewer bits to specify those hypotheses. Note that if P is a prior distribution over H. then any given hypothesis h will take log2 P(A bits to represent when using an optimal compression code for P. This prior may result in smaller complexity term as long as the hypotheses that are consistent with the data are also likely under the prior, regardless of the size of the hypothesis class.
1 to KL(()) || P) by considering Moreover, the number of bits required can be reduced from log2 P[A] distribution of "good" solutions Q. If we don't care which element of Q we arrive at, we can gain some bits back from this insensitivity (which could be used to code a separate message). The average number of bits to code sample from Q using the prior P is the cross entropy H(Q, P) and we get (Q) bits back from being agnostic about which sample h ~ Q to use, yielding the KL-divergence between Q and P: (Q, P) (QQ) (L P).
With these improvements on the finite hypothesis bound - replacing log [H] with KTL(Q P), and sampling hypothesis h E H we arrive (with minor bookkeeping) at the PAC-Bayes bound introduced in McAllester [51]. This last bound states that with probability at least 1 8,
|| P) + log (n/0) 2
E [R (1)] S E (R)]+ h~2
h~Q
2n
Many refinements of Eq. (2) have been developed [41, 50, 7, 64] but retain the same character. That is, the lower the ratio of the KL-divergence to the number of data points n. the lower the gap between empirical and expected risk. In this work, we use the tighter Catoni [7] variant of the PAC-Bayes bound (see Appendix J for details).
Leveraging Occam's razor, can define prior that explicitly penalizes the minimum compressed length of the hypothesis, also known as the universal prior [62]: P(h) = 2 x-Kh)/Z /Z, where K is the prefix Kolmogorov complexity [33] of h (the length of the shortest program that produces h and also delimits itself), and Z S 1.2 Using point mass posterior on single hypothesis h² we get the following upper-bound
Universal Prior.
1 KLL (1(k=A-] || P(h)) = log P(h)) I (hh))log2 < ((h*) log + 2 llgg((h").
where 1(h) is the length of given program that reproduces h not including the delimiter. For convenience, we can condition on using the same method for compression and decompression for all elements of the prior. Lastly, we can improve the tightness of the previous PAC-Bayes bound by reducing the compressed length I(h") ) of the hypothesis h² that we found during training.
Model Compression. Model compression aims to find nearly equivalent models that can be ex- pressed in fewer bits either for deploying them in mobile devices or for improving their inference time on specialized hardware [9, 10]. For computing PAC-Bayes generalization bounds, however, we only care about the model size. Therefore, we can employ compression methods which may otherwise be unfavorable in practice due to worse computational requirements. Pruning and quan- tization are among the most widely used methods for model compression. In this work, we rely on quantization (Section 4.2) to achieving tighter generalization bounds.
4 Tighter Generalization Bounds via Adaptive Subspace Compression
Training a neural network involves taking many gradient steps in a high-dimensional space R Although D may be large, the loss landscape has been found to be simpler than typically believed
'The universal prior similar to the discrete hypothesis prior from Zhou et al. [73] but setting m(h) 2 logg ((h) rather than the flat mahh- 72

---

1,0
Runtime (GPU Hours)
Sparse
Denia
Train Accuracy
0.8
60
FLLM
Train Accuracy
Krenecker Sum
Kronacker Product
FILM
Sparse
40
Kronedker Product
0.4
FILM
20
Kranecker Sum
Kronerkerr Product
8.0
0.3
X10
110
x101
Figure 2: Effective and scalable projection operators. (Left) Different projection operators (Section 4.1) used for transfer learning from Imagenet to CIFAR-10 ResNet-34 across different subspace dimensions d. Kronecker product, Sparse, and Dense perform almost identically (Cen- ter) Kronecker product runs with substantially reduced the runtime cost compared to the Sparse or Fastfood matrices used by Li et al. [45]. (Right) Training from scratch on CIFAR-10. The FiLM projector alone is unable fit the data when training from scratch, and instead a sum of FiLM and Kronecker Product projectors perform the best.
[14, 26, 23]. Analogous to the notion of intrinsic dimensionality more generally, Li et al. [45] searched for the lowest dimensional subspace in which the network can be trained and still fit the training data. The weights of a neural network E RR parametrized in terms of an initialization 8g and a projection w E Rd to a lower dimensional subspace through a fixed matrix P E Rxd
0 = 0o + Pw.
To facilitate favorable conditioning during optimization. P is chosen to be approximately or- thonormal PT P z Laxd- For scalability, Li et al. [45] use random normal matrices of the form P~N(0, 1) /VD, and their sparse approximations [46, 43].
In its original form, intrinsic dimensionality (ID) only used as scientific tool to measure the complexity of the learning task. Unlike methods like pruning, intrinsic dimension [45] scales with complexity of the task more complex tasks require a larger intrinsic dimension. Subsequently, we find that ID) combined with quantization can serve as effective model compression method. We note that ideas similar to the intrinsic dimensionality of a model have been explored in the context of model compression for estimating bounds [2]. For our work, the ability to find the intrinsic dimension < has profound implications for the compressibility of the models, and therefore our ability to construct generalization bounds. As demonstrated by Zhou et al. [73], the compressibility of a neural network has a direct connection to generalization and allows us to compute non- vucuuusuuus PAC-Bayes bounds for transfer learning.
Resting upon ID, our key building blocks to achieve tight generalization bounds are composed of (i) new scalable method to train an intrinsic dimensionality neural network parameterized by Eq. (3)
(Section 1),, and (ii) a new approach to simultaneously train both the quantized neural network weights and the quantization levels for maximum compression (Section 4.2). Our complete method summarized in Algorithm 1.
4.1 Finding Better Random Subspaces
To further improve upon the scalability and effectiveness of the projections P used by Li et al. [45), we introduce three novel projector constructions.
Using the Kronecker product 8 we construct the matrix Pe = (1 @ R + R2 & 1)/V2D where R,, R2 1), and is the vector of all ones in RVD Noting that R2 IL R2 and that the entries are standard normal, P_ Ps Laxd + OLLvVD).
Kronecker Sum Projector.
Kronecker Product Projector. Alternatively, we form the matrix Pe = Q @ Q2/ with the smaller Q1 Q2 ~ NoO, 1) Dxva and again this matrix is approximately orthogonal: P P @ O(D-1/4) laxd + 1(44)
(QT Q1/VD) (TQ2//VD)
As neither nor d is typically perfect square, we concatenate a dense random matrix to pad out the difference between D. d, and perfect square. As (VD + 1)a D 2vD + 1. we have that the size of
5

---

The matrix vector multiply w + Pw for both of the above projectors can be performed in time O(dvD) and O(vdD) respectively, rather than the OddD) that is required by the dense random matrix. Figure 2 demonstrates the runtime speedup and training performance improvement in com- parison to the methods using by Li et al. [45]. Notably, the Kronecker-stren structure projections retain the fidelity of the dense random matrix while being orders of magnitude faster than the alternative operators when scaling to larger values of d. In other words, the Kronecken-structuredd projectors are as good as the dense projectors for generating random linear subspaces of a given size, but are much scalable.
FiLM projector. BatchNorm parameters have an disproportionate effect on the downstream task performance relative to their size. This observation has been used in Featurewise indepen- dent Linear Modulation (FiLM) [58, 17] for efficient control of neural networks in many different settings. Several authors have explored performing fine-tuning for transfer learning solely on these parameters and the final linear layer [36]. Drawing on these observations, we construct a pro- jection matrix PFiLM where only columns corresponding with BatchNorm or head parameters are non-zero and sampled from (0, /)d/VD, which we also show in Figure 2. While the FiLM pro- jector is highly effective for transfer learning (shown in Figure left), the performance saturates quickly when training from scratch. For this reason, when training from scratch employ the sum PFiLM* (PRIM + Pw))/22 which outperforms the two projectors individually as shown in Figure right.
4.2 Quantization Scheme and Training
Through quantization, the average number of bits used per parameter can be substantially reduced. When optimizing purely for model size rather than efficiency on specialized hardware, we can choose non-linearly spaced quantization levels which are learned, and use variable length coding schemes as shown in Han et al. [27]. Additionally, the straight through estimator has been central to learning weights in binary neural networks [31]. We combine these ideas to simultaneously optimize the quantized weights and the quantization levels for maximum compression.
Given the full precision weights w = [wi,.... wa] E Id'' and a vector c [c..... cn] E R of quantization levels, we construct the quantized vector u [.......; :Wa] such that ú; Cg(s) where
((1) = arg ming /w; cxl. The quantization levels are learned alongside w, where the gradients are defined using the straight through estimator [3, 70]:
Ow: Owg
0u;; 0cg
d.j and
= [0(0=)]
(4)
We initialize e with uniform spacing between the minimum and maximum values in parameter vector w or k-means [11]. To further compress the network, we use variable length code the form of arithmetic coding [49], which takes advantage of the fact that certain quantization levels are more likely than others. Given probabilities pı (empirical fractions) for cluster arithmetic coding of w takes at most [d x HH[p)] + bits, where (H)p) the entropy Hi(p) -xx Pk log Pk. For a small number of quantization levels, arithmetic coding yields better compression than Huffman coding.
In summary, use [d x H(p) + 2 bits for coding the quantized weights tē 16L bits for the codebook с (represented in half precision), and additional x [log, d] bits for representing the probabilities p&. arriving at ((w) [d x [H((p)+++x (16+ df) +2) As we show in Appendix B, we optimize over the subspace dimension d and the number of quantization levels I. and any other hyperparameters, by including them in the compressed description of our model, contributing only a few extra bits.
4.3 Transfer Learning
For transfer learning, we replace Oo with a learned initialization Op that is found using the pretraining task and data D. With the ID compression, the universal prior P(h fp) x 2 <(((pp) will place higher likelihood on solutions that are close to the pre-training solution 0p.
this padding is at most vDx Vd, so it does not increase the asymptotic cost of performing the matrix vector multiplies.

---

Algorithm Compute PAC-Bayes Bound.
1: Inputs: Neural network fe. Training dataset {24,, VoN== Clusters L, Intrinsic dimension d,
Confidence - 6, and Prior distribution P.
2: function COMPUTE, COCNUTEEBBUUDD/FC fo, L, d. (Ii, (i). 5, P)
3: w f- TRAIN ID(fa, d, (I,, 34) 14)
> (Section 4.1)
4: # TRAIN QUANTIZE(u:, I, (Ii, ((),))))=)))
5: Compute quantized train error R (w)).
6: KKL (Q, P) <- GET ( P)
(Section 3)
7: return GET
R (i), KIL (Q, 6))
(Section 3)
8: end function
9: function TRAIN QUA.NIZEUUNT L, (Zi, 3/ )=1)
> (Section 4.2)
10: Initialize + GET REETCCLSSERSSCC L)
11: for = to quant_epocia do pV cf (w, c) and w pv ww (w,)
12:
13: end for
14: return vü:
15: end function
16: function GET BET_KL(((;: P))
17:
count GET CRRETENNIQE_IUI WEETTQQUEVVLLLLCOO VALS_COUNTS(N)
18:
message_size <- DO ARIARTTTMT EIN.HEEEEICCEEENOIIGG.CCCC c, count)
19:
message.size <- message _size + hyperparam.searde
> (Appendix B)
20:
return message_ssszzz + 2 x log (message.size)
21:
end function
Empirical Non- Vacuous Bounds
Combining the training in structured random subspaces with our choice of learned quantization, we produce extremely compressed but high performing models. Using the universal prior, bound the generalization error of these models and optimize over the degree of compression via the subspace dimension and other hyperparameters summarized in Algorithm 1. We additionally describe hyperparameters, architecture specifications for each experiment, and other experimental details in Appendix E. In the following subsections, apply method to generate strong generalization bounds in the data-independent, data-dependent, and transfer learning settings.
5.1 Vacuous PAC-Bayes Bounds
We present our bounds for the data-indenn inteeiindeendentt prior in Table 2. We derive the first non-vacuous bounds on FashionMNIST, CIFAR-10, 10, and CIFAR- without data-dependent priors. These results have particular significance, as argue in Section 5.2 that using data-dependent priors are not explanatory about the learning process. particular, we improve over the compression bound results obtained by Zhou al. [73] on MNIST from 46% to 11.55% and ImageNet from 96.5% to 94.1%. In terms of compression. we dramatically improve the rates as we reduce the compressed size for the best MNIST bound by 94% bringing it down from 6.23 KB to 0.38KB with LeNet5 and, ImageNet, by 87% bringing it down from 358 KB to 46.3 KB with Mobile Since we perform transfer learning with an ImageNett-traned checkpoint, ImageNet (downstream) dataset. The tightness of our SOTA subspace compression bounds allows us improve the understanding of several deep learning phenomena discussed in Section 6. See Appendix E. for model architectures and Appendix A for additional results.
omit transfer learning experiments the
5.2 Data-Dependent PAC-Bayes Bounds
So far, we demonstrated the strength of our bounds on data-independent priors, where we con- siderably improve on the state-of-the-ant However, number of recent papers have considered data-dependent priors
way of achieving tighter bounds [59, 19]. In this setup, the training data D {(x; ys) } I is partitioned into two parts, D, and D,, with length n m and m. The first dataset is used to construct data-dependent prior P(h DD.). and then the bound is formed over
7

---

Table Our PAC-Bayesian subspace compression bounds compared state-of-the-art (SOTA)
bounds. All results are with 95% confidence, i.e. 8 = .05. The sign i refers to data iattaindeeendent SOTA numbers that we computed using [59], which we run on the additional datasets.
Dataset
Data-independent priors
Data detandependent priors
Err. Bound (%)
SOTA (%)
Err. Bound (%) SOTA (%)
MNIST
11.6
21.7 [59]
1.4
1.5 [59]
+ SVHN Transfer
9.0
16.1
FashionMNIST
32.8
46.51
10.1
38 [19]
+ CIFAR-10 Transfer
28.2
30.1
CIFAR-10
58.2
89.9
16.6
16.7 [59]
+ ImageNett Transfer
35.1
54.2
CIFAR-100
94.6
100
44.4
ImageNet Transfer
81.3
98.1
ImageNet
93.5
96.5 [73]
40.9
the remaining part of the process: the adaptation of the prior P(h Da) the posterior (hh) using the data Dz. The empirical risk is computed over Di only. Intuitively, using dataset D, it is possible construct much tighter prior over the possible neural network solutions. In our setting, simi- lar to transfer learning, we use the prior (0) 2 ((9Pp.)) / where for compression we use 0 = 0D. + Pw, and 0D,, is the solution found by training the model (without random projections) on the data D, rather than initializing randomly. With these data-dependent priors, we achieve the best bounds in Table 2.
However, our adaptive approach exposes significant downside of data-dependent priors. To the extent that PAC-Bayes bounds can be used for explanation, data-dependent bounds only provide insights into the procedure used adapt the prior Po. (0) to the posterior Q using D3: any learning that is done in finding PD. (0) is not constrained or explained by the bound. Given the ability to
adapt the size of the KL to the difficulty of the problem, it is possible squeeze all of the learning into PD. (0) and none in this adaption to Q. This phenomenon happens as the KIL - O, which we m
find happens empirically (or very nearly so) across splits of the data, and especially when is large. Setting Q0)) 10= the KL has only the contribution from the optimization over d: (p.)) S log D. We find that the bound is nothing more than a variant of the simple log Dm/8)++
Hoeffding bound where D2 is the validation set R (0D.) S RD, (0D.) +
2mm1
We can see this phenomenon in Figure ((a) where we compare existing data-dependent bounds to the simple Hoeffding bound applied directly to the data-dependent prior which was trained on only small fraction of the data. We can consider the Hoeffding bound as the simplest data-dependent bound without any fine-tuning so that the prior, a single pre-trained checkpoint, is directly eval- uated on held-out validation data with KL-divergence term. If another data-dependent bound cannot achieve significantly stronger guarantees than the prior Hoeffding bound, then only ex- plains that neural networks generalize because the priors already have low validation error which is no explanation for generalization at all. Indeed, we see in Figure that the strength of existing data- dependent bounds relies almost entirely on the a priori properties of the data-dependent prior rather than constraining the actual learning process through compressibility. Similarly, from a minimum description length (MDL) perspective, data-independent bounds can be used to provide a lossless compression of the training data, whereas data-dependent bounds cannot (see Appendix H).
We also note that with data-dependent priors, optimization over the subspace dimension selects very low dimensionality, even if the data does not have low intrinsic dimension. Because most of the data fitting is moved into fitting the prior, the bound selects low complexity solution with respect the prior without hurting data fit by choosing a low subspace dimensionality (Appendix D).
By contrast, data-independent bounds explain generalization for the entirety of the learning process. Similarly, our transfer learning bounds meaningfully constrain what happens in the fine-tuning on the downstream task, but they do not constrain the prior determined from the upstream task.
8

---

5.3 Non-Vacuone Vacuous PAC-Bayes Bounds for Transfer Learning
By directly interpreting PAC-Bayer bounds through the lens of compression. we immediately see the benefits of using an upstream dataset for transfer learning. Transfer learning allows us con- strain the prior P(0) (p.) around parameters consistent with the upstream dataset Pa, reducing the Kl-divergence between the prior and the posterior and leading to even tighter bounds as we show in Table 2. Our tighter data- independent transfer learning bounds provide a theoretical certification that transfer learning can improve generalization. Our PAC-Bayes transfer learning approach also indi- cates that transfer learning can boost generalization whenever codings optimized on pre-training task are more efficient for encoding a downstream posterior than an a priori guess made before see- ing data. By contrast, downstream tasks which greatly differ from the upstream task may only be consistent with models that are not compressible under the learned prior, a scenario that describes negative transfer. See Appendix C for more details.
6 Understanding Generalization through PAC-Bayes Bounds
The classical viewpoint of uniform convergence focuses on properties of the hypothesis class as a whole, such its size. In contrast, PAC-Bayes shows that the ability generalize is not merely a result of the hypothesis class but also a result of the particular dataset and the characteristics of the individual functions in the hypothesis class. After all, many elements of our hypothesis class are not compressible, yet in order to guarantee generalization, we choose the ones that are. Real datasets actually contain tremendous amount of structure, or else we could not learn from them as famously argued by Hume [32] and No Free Lunch theorems [67, 25]. This high degree of structure in real-world datasets reflected in the compressibility of the functions (i.e. neural networks) we find in our hypothesis class which fit them.
In this section, examine exactly how dataset structure manifests in compressible models by ap- plying our generalization bounds, and we see what happens when this structure is broken, for exam- ple by shuffling pixels or fitting random labels. Corrupting the dataset degrades both compressibility and generalization.
Standard
Shuffled Pixels
Shuffled Labels
100
Err. Bound (%)
90
70
CNN
MLP
60
x10
x104
x10*
Subspace Dimension
Figure 3: Breaking structure in the data and the model. Our PAC-Bayes bound computed using various subspace dimensions for a fixed size CNN and MLP, both with 500k parameters. We train on (left) CIFAR-10, 10, (center) CIFAR- 10 with shuffled pixels, (right) CIFAR-14 10 with shuffled labels. Structure the dataset induces structure in the model. As structure is removed from the dataset, models which fit the data become much less compressible, hence generalize worse.
MLPs vs CNNs. It is well known that convolutional neural networks (CNNs) generalize much better than standard multilayer perceptrons (MLPs) with alternating fully-connected layers and ac- tivation functions on image classification problems, even when controlling for the number of pa- rameters. In our generalization bounds, this is reflected in the improved compressibility of CNNs when compared to MLPs. In Figure 3 (left), we see how on CIFAR-I0 a we are able to find lower description length for a CNN than an MLP with the same number of parameters. See Appendix E,4 for experimental details.
Shuffled Pixels. However, when the image structure broken by shuffling the pixels, we find that CNNs are no better at generalizing than MLPs. For this dataset, CNNs become substantially less compressible and hence our bounds show them generalizing worse than MIPs, see Figure? (center). MI.s do not suffer when this structure is broken since they never used it in the first place.

---

Shuffled Labels. When the structure of the dataset is entirely broken by shuffling the labels, the compressibility of the models (both for CNNs and MLPs) which fit the random labels is lost. Regardless of the subspace dimension used, our generalization bounds are all at 100% error as shown in Figure (right). It not possible to fit the training data using low subspace dimensions, and when using a large enough dimension to fit the data, the compressed size of the model is larger than the training data and hence the generalization bounds are vacuous.
Equivariance. Designing models which are equivariant to certain symmetry transformations has been a guiding principle for the development of data-efficient neural networks in many domains [12, 13, 65, 66, 22, 35]. While intuitively it is clear that respecting dataset symmetries severely improves generalization. relatively little has been proven for neural networks [48, 21, 74, 4, 20J. We compress and evaluate rotationally equivariant (C₂) and non-equivariant Wide ResNets [66, 71] trained on MNIST and rotated version of MNIST. As shown in Figure 5, the rotationally equivariant models are more compressible and provably generalize better than their non-equivariant counterparts when paired with dataset that also has the rotational symmetry. See Appendix F for further details.
Is Stochasticity Necessary for Generalization? It is widely hypothesized that the implicit biases of SGD help to find solutions which generalize better. For example, Arora et al. [1] argue that there is no regularizer that replicates the benefits of gradient noise. Wu et al. [68], Smith et al. [61], and Li et al. [47] advocate that gradient noise is necessary achieve state-of-the-an performance. In comparison, recent work by Geiping et al. [24] shows that full-batch gradient descent can match tfateoof-the-as performance, and Izmailov al. [34] shows that full-batch Hamiltonian Monte Carlo sampling generalizes significantly better than mini-batch MCMC and stochastic optimization.
We train ResNet-18 18 and LeNet5 models on CIFAR-10 and MNIST, respectively, using full-batch and SGD with different intrinsic dimensionalitiess We provide the training details in Appendix G. For MNIST with LeNet5, the best generalization bounds that we obtain are 11.55% and 11.20% using stochastic gradient descent (SGD) and full-batch training respectively. The best generalization bounds that obtain for CIFAR-10 10 with ResNet-18 are 74.68% and 75.3% using SGD and full- batch training respectively. We also extend this analysis to SVHN to MNIST transfer learning with LeNet5 and obtain PAC-Bayes bounds of 9.0% and 8.7% using SGD and full-batch training respectively. These close theoretical guarantees on the generalization error for both SGD and full- batch training suggest that while the implicit biases of SGD may be helpful, they are not at all necessary for understanding why neural networks generalize well (see Appendix G).
Double Descent. Our bounds are also tight enough to predict the double descent phenomenon noted in Nakkiran et al. [54]. See Appendix for a depiction of these experiments and discussion of their significance.
7 Discussion
In this work, we constructed a new method for compressing deep learning models that is highly adaptive to the model and the training dataset. Following Occam's prior, which considers shorter compressed length models to be more likely, we construct state-of-the-art generalization bounds across a variety of settings. Through our compression bounds, we show how generalization relates to the structure in the dataset and in the model, and we are able to explain aspects of neural network generalization for natural image datasets, shuffled pixels, shuffled labels, equivariant models, and stochastic training.
Limitations. Despite the power of our compression scheme and the ability of our bounds to faithfully describe the generalization properties of many modeling decisions and phenomena, we are scratching the surface of explaining generalization. Our compression bounds prefer models with a smaller number of parameters as shown in Appendix H, instead of larger models which actually tend to generalize better. While we achieved better model compression than previous works, is unlikely that we are close to theoretical limits. Maybe through nonlinear parameter compression schemes we might find that larger deep learning models are more compressible than smaller models. Moreover, it is unclear how to relate the bounds of the compressed models to their uncompressed counterparts, perhaps leveraging ideas from Nagarajan and Kolter [52] and others investigating this question. Additionally, while our bounds show that the compressibility of our models implies generalization, we make no claims about the reverse direction. However, we believe that model compression and Occam's 's razor have yet untapped explanatory power in deep learning.
10

---

Acknowledgements
We thank Pavel Izmailov and Nate Gruver for helpful discussions. This research is supported by NSF CAREER IIS- 25-441449 NSF I-DISRE 193471, NIH R01DA048764 NSF 11S-1910266, NSF 1922658 NRT-HDR, Meta Core Data Science, Google AI Research, BigHat Biosciences, Capital One, and an Amazon Research Award. This work is also supported in part through the NYU IT High Performance Computing resourees, services, and staff expertise.
References
[1] Sanjeev Arora, Nadav Cohen, and Elad Hazan. On the optimization of deep networks: Implicit acceleration by overparameterization. In Proceedings the the 35th International Conference on Machine Learning, ICMI. 2018, Stockholmsmässsan Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 244-253. PMLR, 2018. 10
[2] Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via compression approach. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 254-263. PMLR, 2018. 1, 1,
5
[3] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or Propagating Gradients through Stochastic Neurons for Conditional Computation. Preprint arXiv: 1313..88.332. 2013.
[4] Alberto Bietti, Luca Venturi, and Joan Bruna. On the sample complexity of learning under geometric stability. Advances in Neural Information Processing Systems, 34, 2021. 10
[5] Lukas Biewald. Experiment tracking with weights and biases, 2020. Software available from wandb.com. 20
[6] Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncer- tainty in neural network. In Proceedings of the 32nd International Conference Machine Learning, ICML 2015, Lille, France, 6-11 July 2015, volume 37 of JMLR Workshop and Con- ference Proceedings, pages 1612-1622. JMLR.org. 2015. 3
[7] Olivier Catoni. PAC-Bayesian Supervised Classification: the Thermodynamics of Statistical Learning. Institute of Mathematical Statistics Lecture Notes, 2007. 4, 24
[8] Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Chris- tian Borgs, Jennifer T. Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. In 5th International Conference on Learning Representa- tions, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. Open- Review.net, 2017.
[9] Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. A survey of model compression and accel- eration for deep neural networks. arXiv preprint arXiv: 2017.
[10] Yu Cheng, Duo Wang, Pan Zhou, and Tao Zhang. Model compression and acceleration for deep neural networks: The principles, progress, and challenges. IEEE Signal Processing Magazine, 35(1):126-136, 2018. 3,
[11] Yoojin Choi, Mostafa El- El-Khhmy, and Jungwon Lee. Towards the limit of network quantization. In Sth International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. 6
[12] Taco Cohen and Max Welling. Group equivariant convolutional networks. In Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York City, NY, USA, June 19-24, 2016, volume 48 of JMLR Workshop and Conference Proceedings, pages 2990-2999 JMLR. org, 2016.
[13] Taco S. Cohen, Mario Geiger, Jonas Köhler, and Max Welling. Spherical cnns. In 6th Inter- national Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. 10
[14] Yann N. Dauphin, Razvan Pascanu, Çaglar Gülçehre, KyungHyun Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in hime-dimen non- convex optimization. In Advances in Neural Information Processing Systems 27: Annual
11

---

Conference on Neural Information Processing Systems 2014, December 8-13 2014, Montreal, Quebec. Canada, pages -933-2941, 2014. 5
[15] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Fei-Fei Li. Imagenet: A large- scale hierarchical image database. In 2009 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR 2009), 20-25 June 2009, Miami, Florida, USA, pages 248-255. IEFE Computer Society, 2009. 19, 24
[16) Nan Ding, Xi Chen, Tomer Levinboim, Beer Changpinyo, and Radu Soricut. Pactran: Pac- bayesian metrics for estimating the transferability of pretrained models to classification tasks.
arXiv preprint arXiv:2203.05/22 2022. 3
[17] Vincent Dumoulin, Ethan Perez, Nathan Schucher, Florian Strub, Harm de Vries, Aaron Courville, and Yoshua Bengio. Feature- wise transformations. Distill, 3:e11, 2018.
[18] Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Pro- ceedings of the Thirty- Third Conference on Uncertainty in Artificial Intelligence, UAI 2017,
Sydney, Australia, August 1 1--5, 2017, AUAI Press, 2017. 2,3
[19] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, Gabriel Aprino, and Daniel M. Roy. On the Role of Data Pac-Bar Pac-Bayes Bounds. The 24th International Conference on Artificial Intelligence and Statistics (AISTATS), 2021. 3, 7, 8, 17
[20] Bryn Elesedy. Group symmetry in pac learning. In ICLR 2022 Workshop on Geometrical and Topological Representation Learning, 2022. 10
[21] Bryn Elesedy and Sheheryar Zaidi. Provably strict generalisation benefit for equivariant mod- els. In International Conference on Machine Learning, pages 2959-2969. PMLR, 2021. 10
[22] Mare Finzi, Samuel Stanton, Pavel Izmailov, and Andrew Gordon Wilson. Generalizing con- volutional neural networks for equivariance to lie groups on arbitrary continuous data. In Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 3165 3176. PMLR, 2020. 10
[23] Timur Garipov, Pavel Izmailov, Dmitrii Podoprikhin, Dmitry P. Vetrov, and Andrew Gordon Wilson. Loss surfaces, mode connectivity, and fast ensembling of dnns. In Advances Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, December 3-8, 2018, Montréal, Canada, pages 8803-8812, 2018. 5
[24] Jonas Geiping, Micah Goldblum, Phillip E. Pope, Michael Moeller, and Tom Goldstein. Stochastic Training Is Not Necessary For Generalization. The 10th International Conference on Learning Representations (ICLR), 2022. 10, 19
[25] Christophe Stiradd-Carrie and Foster Provost. Toward a justification of meta-leariing Is the no free lunch theorem show-stopper. In Proceedings of the ICMI.-2005 Workshop on Meta- learning, pages 12-19, 2005. 9
[26] lan J. Goodfellow and Oriol Vinyals. Qualitatively characterizing neural network optimization problems. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings, 2015. 5
[27] Song Han, Huizi Mao, and William J. Dally. Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding. The 4th International
Conference Learning Representations (ICLR), 2016. 3, 6, 16
[28] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In 2016 IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2016, Las Vegas, NV, USA, June 27-30, 2016, pages 770-778. IEEE Computer Society, 2016. 19
[29] Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimiz- ing the description length of the weights. In Proceedings of the sixth annual conference on Computational learning theory, pages 5-13, 1993.
[30] Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1):1-42, 1997.
3,3
12

---

[31] Itay Hubara, Matthieu Courbariaux, Daniel Soudry, Ran El- Lanii,, and Yoshua Bengio. Bina- rized neural networks. Advances neural information processing systems, 29, 2016. 6
[32] David Hume. Treatise of Human Nature. Oxford University Press, 1978. revised P.H. Nidditch. 9
[33]
Marcus Hutter et al. Algorithmic complexity, 2008. 4
[34] Pavel Izmailov, Sharad Vikram, Matthew D Hoffman, and Andrew Gordon Gordon Wilson. What are bayesian neural network posteriors really like? In International conference ma- chine learning, 2021. 10
[35] John Jumper, Richard Evans, Alexander Pritzel, Tim Green, Michael Figurnov, Olaf Ron-
neherger, Kathryn Tunyasuvunakool, Russ Bates, Augustin Zidek, Anna Potapenko, et al. Highly accurate protein structure prediction with alphafold. Nature, 596(7873):583-558 2021.
10
[36] Fahdi Kanavati and Masayuki Tsuneki. Partial transfusion: on the expressive influence of trainable batch norm parameters for transfer learning. In Medical Imaging with Deep Learning,
pages 338-353. PMLR, 2021. 6
[37]
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On large-batch training for deep learning: Generalization gap and sharp minima. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[38] Alex Krizhevsky. Learning multiple layers of features from tiny images, 2009. 19, 24
[39] John Langford. Quantitatively tight sample complexity bounds. PhD thesis, Camegie Mellon University, 2002.
[40] John Langford and Rich Caruana. (not) bounding the true error. In Advances in Neural In- formation Processing Systems 14 [Neural Information Processing Systems: Natural and Syn- thetic, NIPS 2001, December 3-8, 2001, Vancouver, British Columbia, CanadaJ, pages 809- 816. MIT Press, 2001. 3
[41] John Langford and Matthias Seeger. Bounds for Averaging Classifiers. Tech. rep CMU-CS- 01-102, Carnegie Mellon University, 2001. 2, 4
[42] Hugo Larochelle, Dumitru Erhan, Aaron C. Courville, James Bergstra, and Yoshua Bengio. An empirical evaluation of deep architectures on problems with many factors of variation. In Machine Learning, Proceedings of the Twenty-Fourth International Conference (ICML 2007), Corvallis, Oregon, USA. June 20-24. 2007, volume 227 of ACM International Conference
Proceeding Series, pages 473-480, ACM, 2007. 21
[43] Quoc V. Le, Tamás Sarlós, and Alex Smola. Fastfood: Approximate kernel expansions in loglinear time. ArXiv, abs/1408.3060, 2013. 5
[44] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient- learning applied to document recognition. Proc. IEEE, 86:2278-2333 1998. 19,24
[45] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In 6th International Conference on Learning Representa- tions, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceed- ings. OpenReview.net, 2018 3, 5,6 6
[46] Ping Li, Trevor J. Hastie, and Kenneth Ward Church. Very sparse random projections. In KDDD '06, 2006.
[47] Zhiyuan Li. Sadhika Malladi, and Sanjeev Arora. On the Validity of Modeling SGD with
Stochastic Differential Equations (SDEs). Preprint arXiv:2 /2470 2021. 10
[48] Clare Lyle, Mark van der Wilk, Marta Kwiatkowska, Yarin Gal, and Benjamin On the benefits of invariance in neural networks. arXiv preprint arXiv:2005.00 10178, 2020. 10
[49] David JC MacKay, David JC Mac Kay, et al. Information theory, inference and learning algorithmss. Cambridge university press, 2003.
[50] Andreas Maurer. A Note on the PAC Bayesian Theorem. Preprint arXiv 041999v1, 2004. 4
[51] David McAllester. PAC-Bayesian Model Averaging. Proceedings of the 12th Annual Con- ference on Learning Theory (COLT), pages 164-170, 1999. 4
13

---

[52] Vaishnavh Nagarajan and Zico Kolter. Deterministic pac- pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv:1905.1334. 2019. 10
[53] Vaishnavh Nagarajan and J Zico Kolter. Uniform convergence may be unable to explain gen- eralization in deep learning. Advances in Neural Information Processing Systems, 32, 2019.
[54] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and lya Sutskever. Deep double descent: Where bigger models and more data hurt. In 8th International Con- ference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. 10
[55] Jeffrey Negrea, Gintare Karolina Dziugaite, and Daniel Roy. In defense of uniform conver- gence: Generalization via derandomization with an application to interpolating predictors. In International Conference on Machine Learning, pages 7263-7272, PMLR, 2020. 1
[56] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011. 19, 24
[57] Behnam Neyshabur, Srinadh Bhojanapallii, and Nathan Srebro. A pac-bayesian approach to spectrally nperrrally-oommalized margin bounds for neural networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3. 2018, Conference Track Proceedings. OpenReview.net 2018. 1,3
[58] Ethan Perez, Florian Strub, Harm de Vries, Vincent Dumoulin, and Aaron C. Courville. Film: Visual reasoning with a general conditioning layer. Proceedings of the Phirty-Secons AAAI Conference Artificial Intelligence, (AAA1-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18) 18), and the 8th AAAI Symposium on Educational Advances Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, February 2-7, 2018, pages 3942-3951.
AAAI Press, 2018. 3, 6
[59] María Pérez-Ortiz, Omar Rivasplata, John Shawe-Taylor and Csaba Szepersvári. Tighter Risk Certificates for Neural Networks. Journal of Machine Learning Research 22 (2021) 1-40,
2021. 3, 7, 8, 17
[60] Omar Rivasplata, Vikram M Tankasali, and Csaba Szepesvári. Pac-bayes with backprop. arXiv preprint arXiv: 1e...19000.880 2019. 3
[61] Samuel L. Smith, Erich Elsen, and Soham De. On the generalization benefit of noise in stochastic gradient descent. Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Research, pages 0058-9067.. PMLR, 2020. 10
[62] Ray J Solomonoff. formal theory of inductive inference, part Information and control, (1):1-22, 1964. 4
[63] Mingxing Tan and Quoe V. Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In Proceedings of the 36th International Conference on Machine Learning, ICML, 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Research, pages 6105-6114. 14. PMLR, 2019. 19
[64] Niklas Thiemann, Christian Igel, Oliver Wintenberger, and Yevgeny Seldin. A Strongly Qua- siconvex PAC-Bayesian Bound. 28th Annual Conference on Learning Theory (COLT), 2017.
3,
[65] Nathaniel Thomas, Tess Smidt, Steven Kearnes, Lusann Yang, Li Li, Kai Kohlhoff, and Patrick Riley. Tensor field networks: Rotation-and translation-equivariann neural networks for 3d point clouds. arXiv preprint 10Xi::88022.82/99 19, 2018. 10
[66] Maurice Weiler and Gabriele Cesa. General e(2)-equivariant steerable cnns. In Advances in Neural Information Processing Systems 32: Annual Conference Neural Information Pro- cessing Systems 2019, NeurlPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pages 44334-143455 2019. 10,21 21
[67] David H Wolpert and William G Macready. No free lunch theorems for optimization. IEEE transactions on evolutionary computation, (11):67-82, 1997. 9
[68] Jingfeng Wu, Wenqing Hu, Haoyi Xiong, Jun Huan, Vladimir Braverman, and Zhanxing 7hu. On the noisy gradient descent that generalizes as SGD. In Proceedings of the 37th International
14

---

Conference on Machine Learning. ICML 2020, 13-18 July 2020, Virtual Event, volume 1 119 of Proceedings of Machine Learning Research, pages 10367-10376. PMLR, 2020. 10
[69] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for bench- marking machine learning algorithms, 2017. 19, 24
[70] Penghang Yin, Jiancheng Lyu, Shuai Zhang, Stanley J. Osher, Yingyong Qi, and Jack Xin. Understanding straight-through estimator in training activation quantized neural nets. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. 6
[71] Sergey 7agoruyko and Nikos Komodakis. Wide residual networks. In Proceedings of the British Machine Vision Conference 2016, BMVC 2016, York, UK, September 19-22, 2016. BMVA Press, 2016. 10
[72] Chiyuan Zhang. Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understand- ing deep learning (still) requires rethinking generalization. Communications of the ACM, 64
(3):107-115, 2021.
[73] Wenda Zhou, Victor Veitch, Morgane Austem, Ryan P. Adams, and Peter Orbanz. Non- vacuous generalization bounds the imagenet scale: a pac-bayesian compression approach. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019. 4, 2,
[74] Sicheng Zhu, Bang An, and Furong Huang. Understanding the generalization benefit of model invariance from data perspective. Advances in Neural Information Processing Systems, 34, 2021. 10
15


Reviews:
[{"review_id": "pbPO2EXDTi", "reviewer": "Reviewer_GrpD", "summary": "The paper proposes to apply model compression into an existing PAC-Bayes bound to obtain non-vacuous to obtain \"better\" prior from data (a portion of or the whole training dataset) to make the bound non-vacuous. The proposed method is based on the random subspace compression [38] that projects the high-dimensional parameter vector onto a lower-dimensional subspace with a fixed but random matrix projection, corresponding to the intrinsic dimension of the learning task. Such projected model parameter is then quantized to compress the model further.", "questions": "The contribution of the paper is not very clear to me. I wonder if it could be clarified further, especially differentiating the conventional random subspace projection and quantization with what are proposed in the current work.\n\nAnother suggestion is about the evaluation of other baselines in the literature. And since the current work includes two things: lower-dimensional projection and quantization, could the authors provide an ablation study to see the effect of using only the projection without the quantization. In such case, we could understand further how influence each of the proposed factors leads to the final result.", "limitations": "The authors explicitly stated the limitation where the current work only helps to unveil a part of the performance observed in deep learning models. There are certain aspects regarding to the generalization of deep learning models remained unexplained.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe main difference of the current work from the literature, to me, is the integration of model compression into existing PAC-Bayes bound to make the bound non-vacuous.\n\nAnother contribution of the current work is to present some ad-hoc methods based on either Kronecker product or the observation about Batch Normalization layers to improve the random subspace projection to find a better intrinsic dimension of the task of interest. It is then followed by a quantization technique to compress the model further to regularize the model of interest further according to the Occam's razor.\n\n**Weaknesses**\n\nThe proposed random subspace projection in Section 4.1, despite improving the running time significantly, seems as an engineering technique to optimize [38].\n\nAnother suggestion is that the evaludation is quite simple with a limited number of baselines (both Tables 1 and 2). It seems that previous methods on non-vacuous PAC-Bayes bounds do not include results on several datasets, but it would make the paper more convincing if those methods could be reproduced and evaluated on the datasets of interest.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ZLYPH_SULv2", "reviewer": "Reviewer_9nYn", "summary": "The paper demonstrates a novel combination of compression schemes that lead to significantly better generalization bounds derived from PAC-Bayes bounds. This approach is based on known bounds that were previously used by other works, but is combined with a more powerful compression scheme. The compression scheme is based on limiting the parameter space of model to a d-dimensional random subset represented by the addition of a random starting point in the parameter space plus the random project of a d-dimensional vector of learnable parameters. Such a representation was used in prior works to estimate the \"inherent dimension\" of a dataset / task. The d-dimensional vector is then optimized with quantization-aware training techniques, followed by quantization at the end of training. Finally, arithmetic coding is employed to retrieve the end compressed code of the classifier, which also includes additional hyperparameters on which the compression scheme is dependent (e.g., the seed). The estimated code-length is then plugged into the known bounds to result in the estimated generalization bounds.\n\nThe paper demonstrate how this method can obtain data-independent bounds that are sufficiently small to explain (to some extent) performance on MNIST, FMNIST, and CIFAR10, as well as additional phenomena, e.g., generalization of transfer learning, the importance of structure in the dataset for generalization of fully-connected vs. convolutional networks, and double descent. The paper also highlights some of the limitations of the current approach, for example, the estimated bounds do not correlate with the empirical observation that larger models generalize better.", "questions": "Think of the things where a response from the author can change your opinion, clarify a confusion or address a limitation. This can be very important for a productive rebuttal and discussion phase with the authors. ====\n\nAre there any benefits to the Kroncker Projector beyond the runtime? Does it not harm model compression (in the \"from scratch\" scenario)? It would appear that Figure 1 (right) should also include a plot for the training accuracy when using the dense projector. While faster runtime is nice in practice, for theoretical exploration it seems secondary. If it leads to worse generalization bounds, then it will be detrimental to the main goal of the paper.\n\nAlso, some references are not properly cited, e.g., [2] above is cites by its arxiv number, not as an ICLR paper. I would advised making sure the citations are all updated and correct.", "limitations": "The authors gave a sufficient description of the limitations of their work.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper gives strong evidence to support a long standanding conjecture that NN can be sufficiently compressed to a degree where compression-based bounds are close to their empirically observed accuracy. While not the first to follow this path or reach non-vacuous bounds, it obtains bounds that are far closer to real-world observations, and does so without relying on data-dependent bounds. The paper shows the limitations of data-dependent bounds that many prior works have focused on, that they are not as explanatory and are closer to bounds obtained by considering the estimation of the validation accuracy. The results on more complex tasks (CIFAR-10, CIFAR-100) are still far from what is desired, but the paper also shows the potential of this approach (its applicability for explaining a wide variety of phenomena) and indicates the area where researchers should focus. In addition, the paper is exceptionally well-written, clearly explaining PAC-Bayes bounds and their proposed compression scheme.\n\nThe main weakness of the paper is that many of its components are either wholly-based or lightly-derived from prior works, including the compression-based bounds and the individual components of the compression scheme. From that perspective, it is not as novel of an approach. It is also worth noting that the authors slightly misrepresent the degree to which using the \"inherent dimension\" factorization is novel in the context of model compression for estimating compression-based bounds. One could interpret Algorithm 1 in [1] as following such a factorization which appeared even prior to [2] that coined the term \"inherent dimension\". Of course the analyses and methods in that paper are far different from this submission. Regardless of the above, the specific combination of approaches (and their slight improvements) is novel, and it leads to the strong results mentioned above.\n\n[1] - Arora et al., Stronger generalization bounds for deep nets via a compression approach, ICML 2018.\n\n[2] - Li et al., Measuring The Intrinsic Dimension Of Objective Landscapes, ICLR 2018.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "S29rLdZJv9Q", "reviewer": "Reviewer_tugh", "summary": "The authors propose a new method for compressing deep learning models which is adaptive to the level of structure in the model and the training dataset. In their research, the authors follow the Occam razor paradigm with which they are able to explain why deep learning models generalize on structured data sets such as CIFAR-10.", "questions": "1. Can you type values for the missing values in the tables or explain why you can't do this?\n2. Can an experiment be conducted to confirm the statistical effectiveness of the proposed approach?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- the proposed method is based on theoretical foundations,\n- the subject of the research is interesting.\n\nWeaknesses:\n- poor comparison with other methods, many results of competing methods are not entered in the tables,\n- there are no results confirming the statistical advantage of the proposed approach (it is worth running the method several times and presenting the mean and statistical deviations, it may perform a statistical test confirming the effectiveness of the method),\n- the authors focused on the compression methods of the subspace dimension and the Occam razor paradigm, but there are many methods in the literature that reduce the number of model parameters in other ways. Couldn't you comment on them?  Here are some of them:\n   * https://arxiv.org/pdf/1812.08928.pdf\n   * https://openaccess.thecvf.com/content/CVPR2021/papers/Li_Dynamic_Slimmable_Network_CVPR_2021_paper.pdf\n   * https://papers.nips.cc/paper/2017/file/a51fb975227d6640e4fe47854476d133-Paper.pdf\n   * https://proceedings.neurips.cc/paper/2019/file/68b1fbe7f16e4ae3024973f12f3cb313-Paper.pdf\n   * https://arxiv.org/pdf/1810.05331.pdf\n- the presented charts are not sufficiently clearly described.", "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": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "OXHm3YNqCeB", "reviewer": "Reviewer_1YMo", "summary": "Following a Pac-Bayes compression-based approach to generalization bounds developed in prior work, the paper leverages improved compression procedures to derive tight bounds for the compressed models, both in supervised and transfer learning settings. It also provides empirical evaluations of the bound upon variations of several factors known to impact generalization.", "questions": "Answering the above concerns (which justifies my low rating for now) would be a good starting point for a discussion. \n\nMiscellaneous (minor points):\n\n* Line 99: \"relative entropy\" and \"entropy\" could be named explicitly  \n\n* In the $KL$ bound below line 113: I believe $h$ should be $h^\\ast$ in the right hand side expressions. \n\n*  Fig 2 has no (a) or (b) as named on lines 290 and 296. \n\n*  Role of implicit regularization: to dig deeper into the role of the optimizer, it would be interesting to see how the bound evolve during training compared to the actual test error.   ", "limitations": "The conclusion does include a discussion on the limitations of the results. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper digs deeper into a nice approach that leverages a quantitative connection between compressibilty and generalization. Although the paper largely relies on the approach developed in prior work by Zhou et al (ref [59] in the paper), the practical improvements look substantial. I also find the discussion and empricial analysis in Section 6 particularly nice and promising. \n\nMy main reservation concerns a lack of clarity of the approach, which I feel can potentially lead to misinterpretations and misunderstandings. In fact I think these clarifications are important also for the reviewers so as to avoid misjudgements of the significance of the results. \n\nFrom my understanding  from Section 3 and Algorithm 1 (please correct me if I'm wrong), the main idea (following Zhou et al) is to combine (i) a Pac-Bayes generalization bound applied to a pointwise posterior at the learned hypothesis and the the universal prior which penalizes predictors' minimum length; and (ii) improved compression schemes applied to the learned network weights.  This provides strong generalization guarantees for the compressed models. I believe the question of the relationship with the generalization gap for the uncompressed classifer is non trivial -- and left open here; I feel this is an important issue (which is addressed e.g in Nagarajan & Kolter (2019a)) which should be explicitly mentioned in the paper to avoid ambiguity. (I see that this limitation is explicitly mentioned and discussed in Arora et al 2018 for example, which also provides bounds for compressed models). \n\nNote that this distinction is important conceptually: for example, recent analysis (e.g., Nagarajan & , Kolter (2019b),  Negrea et al (2019)) suggest that using suitable surrogates -- randomized or compressed -- versions of the learned predictors can circumvent the limitations of uniform convergence. From this point of view, it seems that the crux of the generalization problem is to explain generalization of the original predictor (e.g. by a suitable coupling that ties its  performance to that of the surrogate).  \n\nRegardless of clarify, a potentially more serious consequence of the above point is the soundness of the comparison with existing bounds. I believe it would not be methodologically fair to compare bounds on compressed models with bounds on uncompressed ones (just like it would not be fair to compare bounds on stochastic predictors  with bounds on deterministic ones). In fact, I would also be curious to see explicit comparisons with other standard existing (e.g., norm based) bounds applied to the compressed network. Could the authors comment on this point?\n\nOn the other hand, I do think that obtaining strong guarantees for well performing compressed models is very interesting. Now, if the goal is to obtain competitive compression models with guarantees,  I think the various tradeoffs that usually comes along with compression need to be more thoroughly investigated: in particular, how does the actual generalization performance  compare with the uncompressed network ? What are the computational costs (I would not agree that this issue is unimportant here as suggested on line 122-123) ? etc. \n\nI think that the paper can potentially yield a  very nice contribution, provided the above ambiguity is correctly clarified and settled. For example, even without theoretical guarantees that tie the performances of the compressed and uncompressed model,  the bound for  the compressed model can still yield a powerful heuristic generalization measure for the uncompressed one. The results in Section 6 suggest that this is the case, but if this point of view is favoured, they would probably deserve a deeper and more thourough investigation, so as to compare well with prior work in the subject (in fact recent large scale correlation analysis revealed key challenges  in identifying actual causal factors for generalization (e.g. Jiang et al, 2019, Dziugaite et al 2020)). \n\nReferences: \n\nNagarajan & Kolter (2019a). Deterministic PAC-Bayesian generalization bounds for deep networks via generalizing noise-resilience. ICLR 2019. https://arxiv.org/abs/1905.13344.\n\nNagarajan & Kolter (2019b). Uniform convergence may be unable to explain generalization in deep learning. NeuriPS 2019. https://arxiv.org/abs/1902.04742\n\nNegrea, Dziugaite, Roy (2019). In Defense of Uniform Convergence: Generalization via derandomization with an application to interpolating predictors.  ICML 2010. https://arxiv.org/abs/1912.04265\n\nJiang et al (2019). Fantastic Generalization Measures and Where to Find Them. ICLR 2010. https://arxiv.org/abs/1912.02178\n\nDzuigaite et al (2020) In search of robust measures of generalization. NeurIPS 2020. https://arxiv.org/abs/2010.11924", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept