PaperlayerView exact revision on arXiv

Source-linked AI summary

Non-Vacuous Generalization Bounds at the ImageNet Scale: A PAC-Bayesian Compression Approach

Wenda Zhou, Victor Veitch, Morgane Austern, Ryan P. Adams, Peter Orbanz

arXiv:1804.05862v3stat.MLcs.LG

TL;DR

The paper asks why overparameterized neural networks can generalize despite their ability to overfit, and connects this question to their observed compressibility. It develops a PAC-Bayesian bound based on effective compressed size and combines it with standard compression schemes. The resulting guarantees are non-vacuous at practical scale, while theory and experiments link greater overfitting to poorer compressibility.

  • Problem

    Overparameterized networks can fit training data or random labels while often generalizing well, motivating bounds that identify which learned models are plausible.

  • Method

    The paper develops a PAC-Bayesian generalization bound based on effective compressed size, including corrections for robustness to weight perturbations.

  • Results

    Off-the-shelf compression yields the first non-vacuous generalization guarantees for modern convolutional networks, while overfitting is linked theoretically and empirically to reduced compressibility.

  • Takeaways & Limitations

    Compression provides a quantitative connection between model description length and generalization in practical deep-learning settings.

  • Takeaways & Limitations

    The bounds are far from tight; substantially better compression would be needed for them to have practical value.

Abstract

from arXiv · show

Modern neural networks are highly overparameterized, with capacity to substantially overfit to training data. Nevertheless, these networks often generalize well in practice. It has also been observed that trained networks can often be "compressed" to much smaller representations. The purpose of this paper is to connect these two empirical observations. Our main technical result is a generalization bound for compressed networks based on the compressed size. Combined with off-the-shelf compression algorithms, the bound leads to state of the art generalization guarantees; in particular, we provide the first non-vacuous generalization guarantees for realistic architectures applied to the ImageNet classification problem. As additional evidence connecting compression and generalization, we show that compressibility of models that tend to overfit is limited: We establish an absolute limit on expected compressibility as a function of expected generalization error, where the expectations are over the random choice of training examples. The bounds are complemented by empirical results that show an increase in overfitting implies an increase in the number of bits required to describe a trained network.

1 INTRODUCTION

The paper connects neural-network compression with generalization through a PAC-Bayesian bound based on effective compressed size. Off-the-shelf compression yields non-vacuous guarantees, while overfitting is associated with limited compressibility.

  • Contribution: The paper establishes a generalization bound based on the effective compressed size of a trained neural network.The effective complexity subtracts remaining superfluous structure, including information made irrelevant by weight robustness.
  • Contribution: The bound can be evaluated by compressing a trained network, measuring effective compressed size, and substituting it into the bound.This makes the guarantee compatible with existing compression procedures.
  • Results: Off-the-shelf compression schemes yield state-of-the-art guarantees, including the first non-vacuous bounds for modern convolutional neural networks.The result targets practical deep-learning settings rather than modified training procedures.
  • Results: Models that tend to overfit have an absolute limit on expected compressibility, and empirical tests find that more overfitting requires more description bits.The theoretical result lower-bounds the entropy of the random classifier by expected overfitting.
  • Relation to prior ideas: The approach extends classical Occam-style reasoning into the deep-learning regime, where compression and generalization had largely been studied separately.The paper presents compression as a model-plausibility prior within PAC-Bayes.
  • Motivation: Overparameterized networks can fit random labels perfectly yet generalize poorly, so useful bounds must distinguish plausible training outputs.The paper frames this as a central challenge for generalization theory.

2 GENERALIZATION AND THE PAC-BAYESIAN PRINCIPLE

This section defines risk, empirical risk, and overfitting, then introduces PAC-Bayes as a framework for bounding the generalization error of stochastic classifiers. The bound depends critically on choosing a prior close to the learning procedure's output.

  • Learning setup: Examples are drawn independently from a data-generating distribution, and learning chooses a hypothesis that predicts labels from features.The learner observes a finite training sample because the distribution is generally unknown.
  • Learning setup: Risk is expected loss under the data distribution, while empirical risk estimates it using the training sample.The paper uses these quantities to distinguish population performance from training performance.
  • Learning setup: Overfitting occurs when a selected hypothesis has much lower empirical risk than true risk, with their difference defining generalization error.The dependency between hypothesis selection and quality estimation creates this possibility.
  • PAC-Bayes: PAC-Bayes bounds control stochastic-classifier generalization error through the discrepancy between a prior classifier and the classifier of interest.The prior encodes plausible learned models, while the posterior represents the classifier being analyzed.
  • PAC-Bayes: The paper recalls a PAC-Bayes theorem for {0, 1}-valued losses that holds with probability at least 1 − ϵ over the sample.Its formulation is noted to be significantly tighter when KL/n is large.
  • PAC-Bayes: The quality of a PAC-Bayes bound depends on keeping KL(ρ, π) small and computable by choosing an appropriate prior π.Finding such a prior is identified as the main challenge.

3 RELATIONSHIP TO PREVIOUS WORK

The paper builds on classical compression and generalization ideas while distinguishing its use of existing compression algorithms from prior noise-stability-based approaches. It positions the resulting bounds as quantitative and non-vacuous.

  • Generalization: Prior work has often formalized network properties such as VC-dimension or margins to prove bounds, but these bounds are generally loose relative to observed error.Some alternatives modify training procedures substantially and have not improved practical performance empirically.
  • Compression and generalization: Compression-based generalization has roots in Occam’s razor and minimum description length, including earlier work emphasizing weight quantization and stochasticity.The paper treats its contribution as a deep-learning extension of this longstanding idea.
  • Comparison with prior work: Arora et al. derive simpler networks from noise stability and then bound their error by code length, whereas this paper leverages existing neural-network compression algorithms.The two approaches are described as complementary.
  • Robustness: The paper uses insensitivity to mild weight perturbations to strengthen a naïve compression bound and account for structure in the hypothesis space.This robustness-based strategy is connected to earlier work on perturbation tolerance and generalization.

4 MAIN RESULT

The paper develops PAC-Bayesian generalization bounds based on compressed representations, refining compressed size by accounting for residual structure such as robustness to weight perturbations.

  • Compression-based bound: The Occam-style bound assigns higher PAC-Bayes prior mass to models with shorter code lengths, translating compression quality into a generalization bound.The PAC-Bayes posterior is a point mass at the compressed model, reducing the relevant KL calculation to the coding-based complexity.
  • Compression-based bound: Theorem 4.1 bounds a compressed hypothesis using its coded bit length under a pre-specified coding scheme and a distribution over possible lengths.The result is agnostic to whether compression is lossy, provided the coding represents the decoded model.
  • Robustness adjustment: Effective complexity is defined as compressed size minus remaining structure, correcting for irrelevant information in the representation.Weight perturbation robustness is an example of structure that can substantially reduce effective complexity.
  • Robustness adjustment: Practical compression outputs a triplet of nonzero-weight locations, a codebook, and quantized values, matching many state-of-the-art schemes.The quantized values require k⌈log r⌉ bits, while the locations and codebook contribute their respective coding lengths.
  • Robustness adjustment: The stronger PAC-Bayes construction adds independent Gaussian noise to nonzero weights and bounds generalization through the resulting stochastic estimator.Its KL term is controlled by the effective compressed size, with the coding contribution adjusted by the length distribution.

5 GENERALIZATION BOUNDS IN PRACTICE

The bounds become non-vacuous when combined with modern compression schemes, including for realistic convolutional networks and ImageNet models.

  • Overview: Combining the theory with state-of-the-art compression schemes yields non-vacuous bounds on realistic deep-learning problems.The authors describe these results as state-of-the-art and emphasize the explanatory connection between compressibility and generalization.
  • Overview: 95% confidence bounds are obtained by combining the PAC-Bayes theorem with the effective compressed-size bound.A layerwise grid search selects the prior variance and adds a negligible contribution to effective size.
  • MNIST: On MNIST, LeNet-5 is compressed by pruning, 4-bit quantization, and compressed storage of nonzero-coordinate locations.The original network has 431k parameters, and pruning retains 1.5% of its weights.
  • MNIST: 6.23 KiB is the measured effective compressed size for the stochastic MNIST model, which has a 46% training-error bound at 95% confidence.Gaussian noise is added to each nonzero coordinate before each forward pass, with negligible classification-performance loss.
  • ImageNet: On ImageNet, the approach combines compression with parsimonious architectures because current compression techniques do not suffice for AlexNet- or VGG-16-scale models.The paper applies its stronger bound to MobileNet 0.5 after pruning and quantization.

6 LIMITS ON COMPRESSIBILITY

The paper argues theoretically and empirically that overfitting limits how much a learned estimator can be compressed. More severe overfitting is associated with greater description length after compression.

  • Theory: Overfitting imposes an absolute limit on a model’s expected compressibility.The theoretical result lower-bounds the entropy of estimators by a function of expected overfitting.
  • Theory: The estimator’s entropy is lower-bounded because distinguishing training from fresh examples requires retaining information about the training set.The paper links stronger overfitting to better discrimination between training and testing samples, implying a larger information memory.
  • Theory: Theorem 6.1 formalizes the relationship between expected training–test error differences and estimator entropy for discrete sample and hypothesis spaces.The theorem assumes discrete X × Y and hypothesis set H, with the bound expressed using a non-negative function g.
  • Experiments: In the empirical study, fixed architectures are trained on datasets with varying fractions of randomly relabeled examples.The randomization test varies label corruption while holding the architecture fixed.
  • Experiments: 50% sparsity preserves essentially all training accuracy even with completely random labels, but further pruning causes faster accuracy decay for more randomized labels.This pattern is consistent with network size controlling generalization error and with worse-generalizing models requiring more bits.

7 DISCUSSION

The paper reports that standard training followed by compression can yield non-vacuous generalization guarantees at practical scale without modifying the usual pipeline. It also emphasizes that current bounds remain loose because substantially better compression would be needed for sharp practical guarantees.

  • Discussion: A standard engineering pipeline of training and compressing neural networks produces demonstrable, non-vacuous generalization guarantees at practical scale.The authors describe these as the first such results for networks and problems at practical scale.
  • Discussion: The result aligns with practitioners’ observation that good generalization often occurs without heavy regularization or optimizer modifications.The discussion connects the guarantee to empirical practice rather than claiming that such modifications are never useful.
  • Discussion: Current bounds are far from tight, and sharper practical guarantees would require substantially better compression rates.The paper gives a hypothetical ImageNet compression target of 30 KiB as an example of a rate that could yield a sharp bound.

A PROOF OF THEOREM 4.3

The proof constructs a prior as a code-length-weighted mixture over representable compression outputs, then exploits coordinate independence to make the KL calculation tractable. The resulting bookkeeping accounts for compressed structure and quantized parameters.

  • KL calculation: The proof’s main complexity term combines coded subset size, coded component size, and quantized-coordinate count.The displayed expression contains |Ŝ|c, |Ĉ|c, and k̂⌈log r̂⌉.
  • Prior construction: The prior is defined as a weighted mixture over triplets representing compressed network components and their code lengths.The mixture ranges over representable subsets, quantized values, and coordinate choices.
  • Prior construction: The representable values use a finite set F and quantization level r, with F including numbers such as IEEE-754 single-precision values.The construction takes S over subsets of parameter indices and C over F^r.
  • KL calculation: Although the mixture has r^k terms and is computationally intractable directly, coordinate-wise independence factorizes it into tractable univariate components.The factorization uses the independent-coordinate structure of the mixture and the normal density φτ.
  • KL calculation: Substituting the coordinate-wise KL computation into the preceding expression completes the desired bound.The proof concludes by plugging the mixture calculation into equation (13).

A.1 DETAILS IN PRACTICAL USES OF THE BOUND

Applying the bound in practice requires bookkeeping for selected parameters, including quantization resolutions and prior variances. The implementation controls these choices through a union-bound variant and finite-precision discretization.

  • Practical parameter selection: Practical use extends the theorem to unrestricted and potentially data-dependent parameter selection, usually with negligible effect on computed bounds.The paper highlights prior variances as an example of parameters requiring this adjustment.
  • Practical parameter selection: A union-bound variant controls empirically chosen discrete parameters such as per-layer quantization resolutions.The same device is also applied to continuous quantities after discretization.
  • Practical parameter selection: Continuous quantities such as prior variances are discretized as IEEE-754 single-precision, 32-bit floating-point numbers.This converts continuous choices into a finite representable set for the bound.
  • Implementation: The LeNet-5 baseline is trained with momentum SGD for 20,000 steps, using batch size 1024, an initial learning rate of 0.01, inverse-time decay, and an ℓ2 penalty of 0.005.No data augmentation is used.
  • Implementation: Pruning uses Dynamic Network Surgery with layerwise thresholds, a pruning probability decaying from 1.0 to 10^-3, and 30,000 ADAM steps.The threshold schedule is based on layer coefficient means and standard deviations.
  • Implementation: Weights are quantized with a 4-bit per-layer k-means codebook, including a zero cluster for pruned weights.The remaining cluster centers are learned with ADAM for 1,000 steps.

B.2 MOBILENET

The paper uses a pre-trained Google MobileNet as a baseline, then compresses it by pruning and quantizing selected layers while testing noise robustness.

  • MobileNet uses depthwise separable convolutions, with each layer combining depthwise and pointwise convolutions.
  • The compression procedure prunes pointwise and fully connected layers using Dynamic Network Surgery with layer-dependent sparsity targets.Targets are scaled linearly between 65% and 75% according to layer size, while smaller lower layers receive adjusted targets because they are more sensitive.
  • Weights are quantized with layer-specific codebooks using 6 bits generally and 5 bits for the final fully connected layer.Pointwise and fully connected codebooks reserve an exact-zero encoding, while non-pruned depthwise codebooks are fully learned.
  • Noise robustness is evaluated by adding Gaussian noise only to pointwise and fully connected layers.The fully connected layer receives noise with standard deviation equal to 2% of its coordinate range, while pointwise-layer noise is scaled by relative layer size.

C PROOF THAT OVERFITTING IMPLIES HIGH CLASSIFIER ENTROPY

The proof connects overfitting with the ability of a learned estimator to distinguish training examples from fresh samples. It formalizes this connection by lower-bounding the estimator’s entropy using the discriminator’s performance.

  • Setup: Overfitting is characterized by substantially lower training loss than testing loss, with randomness entering through the sampled dataset and resulting estimator.
  • Discriminator construction: An overfitting estimator can be converted into a discriminator for whether an example came from the training set or the data-generating distribution.The example is drawn from an independent mixture of the uniform training-set distribution and the distribution D.
  • Entropy connection: The discriminator’s quality is summarized by quantities interpreted as average false-positive and true-negative proportions.If these quantities differ substantially from those of a random classifier, the estimator must have high entropy.
  • Theorem: Theorem C.1 states the result for a selection procedure that depends only on the unordered i.i.d. sample, assuming discrete sample and hypothesis spaces.
  • Proof construction: The proof constructs the sample by selecting from paired examples with independent Bernoulli variables, preserving an i.i.d. sample from D.Independence gives the selector entropy H(B | E) = H(B) = n log 2.
  • Entropy bound: Entropy chain-rule bounds relate the estimator’s conditional entropy to the Bernoulli selector entropy and the discriminator’s conditional uncertainty.The resulting inequality lower-bounds entropy by a term involving binary entropy expressions in p_n and q_n.
Loading 1804.05862v3…