Source-linked AI summary
Stronger generalization bounds for deep nets via a compression approach
Sanjeev Arora, Rong Ge, Behnam Neyshabur, Yi Zhang
TL;DR
Deep networks can generalize despite having more parameters than training samples, while prior analyses had not yielded bounds better than naive parameter counting. The paper introduces explicit compression based on layerwise noise stability, obtaining improved bounds and extending the analysis to convolutional networks.
Problem
Deep networks generalize despite overparameterization, but prior PAC-Bayes and margin analyses had not produced sample-complexity bounds better than naive parameter counting.
Method
The paper uses an explicit compression framework and layerwise noise-stability properties to construct smaller, provably related representations of trained networks.
Results
The resulting bounds are better than naive parameter counting in practice and extend to convolutional networks.
Takeaways & Limitations
The framework provides theoretical support for compressing trained deep networks and connects measurable stability properties with generalization.
Takeaways & Limitations
The framework generally proves generalization for the compressed network, and its current proof requires 1/ρδ to be of order 1/d.
Abstract
from arXiv · showhide
Deep nets generalize well despite having more parameters than the number of training samples. Recent works try to give an explanation using PAC-Bayes and Margin-based analyses, but do not as yet result in sample complexity bounds better than naive parameter counting. The current paper shows generalization bounds that're orders of magnitude better in practice. These rely upon new succinct reparametrizations of the trained net --- a compression that is explicit and efficient. These yield generalization bounds via a simple compression-based framework introduced here. Our results also provide some theoretical justification for widespread empirical success in compressing deep nets. Analysis of correctness of our compression relies upon some newly identified \textquotedblleft noise stability\textquotedblright properties of trained deep nets, which are also experimentally verified. The study of these properties and resulting generalization bounds are also extended to convolutional nets, which had eluded earlier attempts on proving generalization.
1 Introduction
The paper addresses why deep networks generalize despite overparameterization and introduces compression and layerwise noise stability as measurable explanations.
- Deep networks can fit randomly labeled data despite SGD and regularization, challenging the idea that regularization alone explains generalization.
- Existing analyses had difficulty producing quantitative sample-size bounds for deep networks comparable to classical results.
- The paper introduces a simple compression framework that provides an explicit and intuitive route to generalization bounds.
- It identifies layerwise noise stability, where perturbations injected at lower layers are attenuated by higher layers, as a new property linked to compressibility.
- The resulting algorithms reduce effective parameter counts, improve on naive parameter counting, extend to convolutional networks, and empirically correlate with generalization.
2 Compression and Generalization
This section formalizes generalization through compression: a low-parameter classifier matching a trained network on the training set can receive a concentration-based bound.
- Compression and Generalization: If a low-parameter classifier matches a complex classifier’s training loss closely, compression-based concentration can yield low population classification error.
- Compression and Generalization: The framework permits a fixed helper string, such as random initialization, while counting only the discrete trainable parameters in the compressed representation.
- Compression and Generalization: Theorem 2.1 bounds generalization using the number of discrete compressed parameters, their possible values, the training-set size, and margin-compressibility.
- Remarks: The framework bounds the compressed network rather than the original network unless comparable loss is established throughout the domain, not only on training data.
- Example: Linear classifiers with margin: A margin-γ linear classifier can be sparsified to O(1/γ^2) nonzero entries and generalized after discretization with O(log d/γ^2) samples.
- Deep-network compression: The deep-network construction compresses each matrix layer by truncated singular-value decompositions, replacing rank-based parameter counts for full matrices.
3 Noise stability properties of deep nets
The paper develops noise-stability quantities that explain why compression errors can be attenuated across layers rather than amplified solely by worst-case Lipschitz bounds.
- Noise sensitivity: Noise sensitivity measures the maximum relative effect of a noise distribution on a mapping over a specified input set.
- Noise sensitivity: For matrices under Gaussian noise, low sensitivity corresponds to dominant singular directions that carry signal while uniformly distributed noise is attenuated.
- Noise stability: The compression strategy injects approximately Gaussian layer errors and exploits low sensitivity in subsequent layers to permit more aggressive compression.
- Cushion: Layer cushion relates layer output magnitude to Frobenius-norm and activation magnitude, with its inverse squared linked to Gaussian noise sensitivity.
- Interlayer cushion: Interlayer cushion captures local linear behavior of the network segment between two layers under perturbations.
- Interlayer smoothness: Interlayer smoothness accounts for nonlinear activation changes; empirically, the paper reports that 1/ρδ is a small constant.
- Proof condition: The current proof requires 1/ρδ to be of order 1/d, unless a stronger lower-order perturbation assumption is made.
4 Fully Connected Networks
The paper compresses fully connected networks with randomized, explicit reparametrizations and uses noise-stability properties to bound the resulting output error and generalization.
- The compression proof applies to fully connected multilayer networks and bounds the compressed network’s output error using properties defined in Section 3.1.
- Randomized compression fixes a helper string of random matrices and represents each weight matrix using only k inner products.The resulting output error is designed to behave like a Gaussian, following the intuition of Johnson–Lindenstrauss dimension reduction.
- The matrix-compression lemma guarantees, simultaneously over matrix/vector pairs, an error bounded by ε∥A∥F∥U∥F∥x∥ with probability at least 1 − δ.
- Algorithm 1 generates a network with a bounded total parameter count while preserving outputs on the training set with probability 1 − δ/2.The bound assumes interlayer smoothness ρδ ≥ 3d and uses layer cushion, interlayer cushion, activation contraction, and interlayer smoothness.
- The framework can improve its bounds by encoding changes relative to random initialization and by excluding a ζ fraction of outliers, at the cost of an additive ζ generalization term.
5 Convolutional Neural Networks
For convolutional networks, the paper develops a p-wise independent filter-compression strategy because naive independent or fully shared compression fails under convolutional weight sharing.
- 5 Convolutional Neural Networks: Theorem 5.1 gives a generalization bound for compressed convolutional networks under interlayer smoothness, margin, and well-distributed-Jacobian conditions.The bound also depends on layer cushions, interlayer cushions, activation contraction, stride, and filter width.
- 5 Convolutional Neural Networks: Naively extending fully connected compression to convolutional filters either causes a parameter blowup or introduces correlations that invalidate the interlayer analysis.Independent compression across filter copies makes parameters proportional to the number of spatial locations, while one shared compression does not produce suitably spherical noise.
- 5 Convolutional Neural Networks: The convolutional construction uses p-wise independent compressed filters, positioned between fully independent and fully dependent compression.
- 5 Convolutional Neural Networks: The convolutional analysis defines interlayer cushions using Jacobians and adds a well-distributed-Jacobian condition to formalize uniform incorporation of image-field information.
- 5 Convolutional Neural Networks: The convolutional proof relies on assumptions about Gaussian perturbations and the distribution of information across pixels.
6 Empirical Evaluation
The empirical evaluation studies noise-stability properties and compression-based bounds on trained VGG-19 and AlexNet models, finding especially strong improvements in higher-layer layer cushion.
- Experiments train VGG-19 and AlexNet for multiclass classification on CIFAR-10 using SGD with specified regularization and learning-rate schedules.
- Training drastically improves layer cushion, especially in layers 8 and higher where most parameters reside.
- Interlayer cushion, activation contraction, and interlayer smoothness remain well behaved after training, while the paper identifies layer cushion as the likely driver of the observed generalization phenomenon.
- The paper verifies its Section 3 assumptions on VGG-19 by histogramming stability properties and Jacobian well-distributedness across training-set examples.
- Figure 2 compares trained and randomly initialized VGG-19 networks through distributions of layer cushion, minimal interlayer cushion, activation contraction, and interlayer smoothness.The distributions are measured across training-set data points for the 13th layer.
appendix D.1.
The appendix reports empirical behavior of the proposed bound and its relationship to generalization, compression, and layer properties. It also records proof ingredients for the compression-based guarantees.
- Correlation to generalization error: After 120 epochs, training error is almost zero while test error continues improving, and the bound improves but does not capture all generalization.The bound is rescaled to the range of empirical generalization error for comparison.
- Correlation to generalization error: 77.22% validation accuracy is achieved by the AlexNet trained on normal CIFAR-10 data, whose larger layer cushion and lower activation contraction match the bound’s prediction.The comparison uses a corrupted-data AlexNet trained with randomly shuffled labels.
- Comparison to other generalization bounds: All previous neural-net bounds are orders of magnitude worse than the proposed bound on VGG-19; the closest is about 10^15.The cited closest baseline is spectral norms times average ℓ1,2 of the layers.
- Comparison to other generalization bounds: Compression rates can be as low as 1% in later layers 9–19, while earlier layers are less compressible.The table is qualitative because depth, logarithmic factors, and constants are ignored.
- Proofs: The framework proves generalization by compressing a low-loss classifier into a much smaller discrete-parameter classifier and applying concentration and union bounds.The appendix includes a theorem guaranteeing generalization for the compressed function.
A.2 Example 1: Compress a Vector
This section develops vector-compression procedures that approximate inner products while using few discrete parameters, including a helper-string variant with stronger guarantees.
- Vector compression: Vector-Compress approximates c⊤u within γ for any fixed independent u with probability at least 1−η, using O((log h)/ηγ^2) nonzero entries with high probability.The proof uses unbiased randomized coordinates, variance control, Chebyshev concentration, and a Chernoff bound on sparsity.
- Vector compression: The discretized construction combines truncation, randomized compression, and rounding while preserving the approximation guarantee with probability at least 1−η.The three approximation errors are combined through the triangle inequality.
- Limitations: The basic compression rate is not optimal because it depends on m^1/3 instead of √m.The limitation arises because the underlying vector-compression lemma lacks a high-probability guarantee over all test vectors.
- Helper-string compression: Vector-Project uses random Gaussian vectors and produces a compressed vector whose inner product with any fixed u differs from c⊤u by at most γ with probability at least 1−η.The argument invokes the Johnson–Lindenstrauss lemma and concentration, with sampled vectors stored in a helper string.
A.3 Proof for Generalization Bound in Neyshabur et al. [2017a]
This section states the layerwise assumptions used to analyze compression and explains how compressed-layer errors are controlled across a deep network.
- Proof strategy: The baseline analysis rounds weights and uses an induction showing how perturbations from different layers accumulate through the network.The resulting compressed network can then be analyzed with the generalization theorem.
- Definitions: Layer cushion measures the largest layerwise signal-to-perturbation margin maintained for every training example.It is defined separately for each layer on the training set.
- Definitions: Interlayer cushion measures the corresponding stability between pairs of layers, with minimal interlayer cushion taking the minimum over downstream layers.The definitions are evaluated over all training examples.
- Definitions: Activation contraction is defined as the smallest factor controlling contraction of activations across layers on the training set.It is one of the network properties used in the compression analysis.
- Definitions: Interlayer smoothness controls the effect of injected noise between layer pairs with probability 1−δ.Together, these conditions formalize the network properties required for the improved analysis.
B.2 Proofs
The proofs establish that layerwise compression preserves network behavior under noise-stability conditions, then extend the construction and proof strategy to convolutional networks.
- Fully connected networks: The layerwise induction decomposes compression error into propagation through fixed activations and error caused by changed activations.Interlayer smoothness bounds both terms and completes the induction.
- Fully connected networks: For fully connected networks with ρδ≥3d, the compressed network preserves training margin loss while using a bounded number of parameters determined by cushion, contraction, and smoothness properties.The guarantee is stated for any probability 0<δ≤1 and margin γ>0.
- Fully connected networks: The covering-number proof bounds compressed weights, discretizes their parameters, and applies a Rademacher-complexity argument to obtain generalization.Positive homogeneity permits assuming balanced layer norms during approximation.
- Convolutional neural networks: The convolutional extension defines tensor products and location-dependent compressed weights, whose outputs are generated by a p-wise independent procedure.The analysis makes the compressed output behave similarly to Gaussian noise before reusing the feed-forward strategy.
- Convolutional neural networks: The convolutional proof follows the same error-control strategy as the fully connected case and derives the generalization bound from the resulting total error.The convolutional layers use filter sizes κi and strides si.
C.1 p-wise Independent Compression
The section develops a convolutional compression procedure that uses low-dimensional random subspaces and p-wise independent filters, then establishes parameter efficiency and perturbation guarantees for compressed networks.
- Compression algorithm: Algorithm 4 generates compressed convolutional filters designed to use few parameters while approximating independent compression at each spatial location.The procedure addresses weight sharing, which creates correlations across locations.
- Compression algorithm: The compressed filters can be computed from the projection of the original tensor onto a kp-dimensional subspace, reducing the stored representation to kp parameters.A helper string containing the random matrices is used to reconstruct the filters.
- Independence properties: The generated filters are p-wise independent, with i.i.d. Gaussian marginal distributions for the random matrices used in their construction.For p = log 1/η, the filters can be shown to behave similarly to fully independent random filters.
- Noise control: Under β-well-distributedness, the convolutional compression noise is bounded simultaneously over a finite collection of matrix/vector pairs with probability at least 1 − δ.The proof combines concentration for the generated noise with a union bound.
- Network-level guarantee: The convolutional network guarantee applies when the network’s noise-stability conditions hold, including layer and interlayer cushions, activation contraction, interlayer smoothness, and Jacobian well-distributedness.These quantities are defined as the network properties controlling the perturbation analysis.
D Extended experiment
The extended experiment verifies several noise-stability conditions on a VGG-19 network, including layer cushion, interlayer cushion, activation contraction, interlayer smoothness, and Jacobian well-distributedness.
- Verification of conditions: The VGG-19 verification figures cover layer cushion, interlayer cushion, activation contraction, and interlayer smoothness conditions.These are four of the network properties identified as contributing to noise stability.
- Verification of conditions: The VGG-19 verification also examines the well-distributedness of Jacobians on convolutional layers.The figure uses Jacobian distributions to assess this condition.
D.2 Effect of training on corrupted dataset
The extended experiment compares distributions of layer cushion and activation contraction for AlexNets trained on normal and corrupted CIFAR-10.
- Effect of training on corrupted dataset: The experiment compares layer-cushion distributions for AlexNets trained on normal CIFAR-10 and corrupted CIFAR-10.The comparison is presented in Figure A.6.
- Effect of training on corrupted dataset: The experiment compares activation-contraction distributions for AlexNets trained on normal CIFAR-10 and corrupted CIFAR-10.The comparison is presented in Figure A.7.