PaperlayerView exact revision on arXiv

Source-linked AI summary

Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data

Gintare Karolina Dziugaite, Daniel M. Roy

arXiv:1703.11008v2cs.LG

TL;DR

Many standard learning bounds are vacuous for SGD-trained networks whose parameter counts exceed their training data, leaving deep-learning generalization unexplained. The paper directly optimizes a PAC-Bayes bound and obtains nonvacuous bounds for deep stochastic networks with millions of parameters, including networks trained on 55,000 MNIST examples.

  • Problem

    Many learning bounds remain vacuous for SGD-trained neural networks when the number of parameters exceeds the number of training examples, so nonvacuous bounds are needed to explain generalization.

  • Method

    The paper optimizes an objective derived from a PAC-Bayes bound, incorporating data-dependent stochastic classifiers around solutions produced by SGD.

  • Results

    Nonvacuous generalization bounds were computed for deep stochastic neural networks with millions of parameters trained on 55,000 MNIST examples.

  • Takeaways & Limitations

    The results demonstrate nontrivial generalization in the modern deep-learning regime, although the bounds remain several times larger than the approximately 0.03 held-out test error.

  • Takeaways & Limitations

    Connecting SGD to flat minima and transferring results from stochastic networks back to deterministic ones may require additional structure.

Abstract

from arXiv · show

One of the defining properties of deep learning is that models are chosen to have many more parameters than available training data. In light of this capacity for overfitting, it is remarkable that simple algorithms like SGD reliably return solutions with low test error. One roadblock to explaining these phenomena in terms of implicit regularization, structural properties of the solution, and/or easiness of the data is that many learning bounds are quantitatively vacuous when applied to networks learned by SGD in this "deep learning" regime. Logically, in order to explain generalization, we need nonvacuous bounds. We return to an idea by Langford and Caruana (2001), who used PAC-Bayes bounds to compute nonvacuous numerical bounds on generalization error for stochastic two-layer two-hidden-unit neural networks via a sensitivity analysis. By optimizing the PAC-Bayes bound directly, we are able to extend their approach and obtain nonvacuous generalization bounds for deep stochastic neural network classifiers with millions of parameters trained on only tens of thousands of examples. We connect our findings to recent and old work on flat minima and MDL-based explanations of generalization.

1 INTRODUCTION

The paper addresses why deep networks generalize despite having far more parameters than training examples, where standard bounds are often vacuous. By directly optimizing PAC-Bayes bounds, it computes nonvacuous bounds for deep stochastic networks and studies solution structure related to flat minima.

  • Results: The resulting bounds are nonvacuous for deep networks with millions of parameters trained on datasets one or more orders of magnitude smaller than the parameter count.The paper presents this as the first explicit nonvacuous numerical bounds computed for trained neural networks in this modern deep-learning regime.
  • The limits of existing bounds: Standard capacity-based and state-of-the-art norm-based bounds can be vacuous for SGD-trained networks in the modern overparameterized regime.For MNIST, even a fully connected first layer with 72 hidden units yields vacuous PAC bounds.
  • Understanding SGD: Deep networks can fit randomized labels and still generalize on real labels, revealing substantial capacity to overfit without explaining SGD’s behavior.This creates a major open problem: identifying structure or implicit regularization that connects SGD solutions to generalization.
  • Results: On a binary MNIST variant, PAC-Bayes bounds across architectures fall in the range 16–22%, while held-out-data Chernoff bounds are consistently around 3%.The bounds demonstrate nontrivial generalization despite remaining substantially looser than held-out estimates.
  • Interpretation and open questions: The analysis connects large low-error regions around SGD solutions with flat-minima and MDL perspectives, while leaving the origin of this structure under SGD unresolved.The authors suggest that moving from stochastic-network guarantees to deterministic networks may require additional structure.

2 PRELIMINARIES

The preliminaries define randomized neural classifiers, their error measures, KL divergence, and the probabilistic bounds used to control generalization. The PAC-Bayes algorithm selects a distribution over hypotheses by minimizing an error bound.

  • A parametric classifier maps network parameters and inputs to binary predictions, while a randomized classifier is a distribution over parameters.
  • The paper distinguishes 0–1 error, logistic surrogate loss, empirical training error, and expected error under a randomized classifier.
  • KL divergence: KL divergence measures the discrepancy between posterior and prior distributions and has a closed-form specialization for multivariate normal distributions.
  • Bounds: The analysis uses union, sample-convergence, and PAC-Bayes bounds to control generalization error with high probability.
  • PAC-Bayes algorithm: The PAC-Bayes learning procedure fixes a prior and confidence level, collects i.i.d. data, minimizes the bound over Q, and returns the resulting randomized classifier.
  • PAC-Bayes algorithm: Optimal randomized prediction is generally intractable, so the paper treats approximation as necessary outside the simplest settings.

3 PAC-BAYES BOUND OPTIMIZATION

The method approximates PAC-Bayes optimization with a Gaussian posterior over network parameters, a Gaussian prior, surrogate loss, and numerical gradient optimization. Unbiased Monte Carlo estimates make the bound computationally usable.

  • The method restricts Q to diagonal-covariance Gaussian distributions and replaces the PAC-Bayes objective’s empirical loss with a convex surrogate.
  • A Gaussian prior centered at the random initialization uses a variance parameter λ selected from a discrete set through a union-bound argument.
  • The continuous optimization variables are transformed to unconstrained coordinates for weights, variances, and λ.
  • The exact randomized empirical error is intractable, so the algorithm optimizes an unbiased gradient estimate based on fresh Gaussian perturbations.
  • The reported bound combines PAC-Bayes, sample-convergence, and union-bound steps and holds with probability 1 −δ −δ′.

4 EXPERIMENTS

Experiments evaluate PAC-Bayes optimization on binary MNIST using SGD-trained multilayer perceptrons with varied depth and width, including a random-label control. The study reports empirical errors, SNN estimates, PAC-Bayes bounds, and VC-dimension comparisons.

  • The experiments begin with SGD-trained networks on binary MNIST and optimize stochastic perturbations of their weights across architectures varying in depth and width.
  • The binary MNIST setup uses 55,000 training images, 10,000 test images, and input dimension k = 784.
  • The networks use fully connected multilayer perceptrons with ReLU hidden activations and SGD with momentum trained in mini-batches.
  • PAC-Bayes setup: The stochastic network is Q = Nw,s, with mean equal to the SGD weights and diagonal variances initialized from the weight magnitudes.
  • PAC-Bayes optimization: PAC-Bayes optimization uses a prior variance initialized at e−6, a prior mean fixed at random initialization, and RMSprop-based gradient updates.
  • Reported quantities: Table 1 reports classification errors, VC-dimension upper bounds, SNN upper bounds, and PAC-Bayes test-error upper bounds with probability 0.965.
  • Reported quantities: The SNN error estimates use δ′ = 0.01 and n = 150000, producing estimates within 0.001–0.002.
  • Reported quantities: The VC-dimension bounds for ReLU networks scale as O(LW log W), with L layers and W tunable parameters.

5 RESULTS

The results show that SGD-trained networks generalize similarly across architectures, while PAC-Bayes bounds remain nonvacuous for true labels despite much larger parameter counts. Random labels yield poor test performance and a vacuous bound.

  • True-label SNN training error increases slightly as weight distributions broaden, whereas random-label SNN training error rises above 10%.
  • Empirical test error changes little across architectures, and SNN test error follows the same pattern with slightly higher error rates.
  • All true-label experiments have PAC-Bayes classification error bounded by 0.23 despite networks becoming several times larger.
  • The true-label PAC-Bayes bounds are several times larger than the approximately 0.03 held-out test error but still demonstrate nontrivial generalization.
  • Data-independent VC-dimension bounds are vacuous by several orders of magnitude because the parameter count exceeds the available training data.

6 RELATED WORK

The paper extends PAC-Bayes approaches to modern deep learning and relates its objective to work on flat minima, local entropy, and graduated optimization.

  • The approach scales earlier PAC-Bayes ideas to networks with millions of parameters trained on far fewer examples.
  • The optimized objective is an upper bound on PAC-Bayes, but it can be very loose when empirical classification error is approximately zero.
  • The work connects to research arguing that flat or nonisolated minima are associated with generalization and algorithmic properties.
  • Entropy-SGD seeks dense local minima by maximizing the depth and flatness of the energy landscape through a local-entropic objective.
  • Unlike local-entropic loss, the paper’s second objective term favors large regions near initialization, while its first term is stochastic-network empirical error.
  • The algorithm also resembles graduated optimization because its objective applies local smoothing to the error function.

7 CONCLUSION AND FUTURE WORK

The experiments obtain nonvacuous PAC-Bayes bounds for deep networks on MNIST, while the conclusion identifies dataset, architecture, posterior, and SGD-generalization questions for future work.

  • Nonvacuous bounds were obtained for deep neural networks with millions of parameters trained on 55000 MNIST examples.
  • The bounds were optimized from an SGD solution, which remained inside the 1% ellipsoidal quantile; randomized labels instead caused substantial movement.
  • The experiments used fully connected feed-forward networks on binary-class MNIST, leaving multiclass, other datasets, and convolutional architectures untested.
  • Tighter bounds may result from modeling dependencies among weights instead of enforcing an independent posterior covariance.
  • A loss-surface-tuned posterior, such as a local Gibbs distribution, is proposed as a possible route to quantitatively tighter bounds.
  • Understanding SGD generalization may require asking whether SGD finds flat minima and adding structure when transferring from stochastic to deterministic networks.

B.1 BOUNDS FROM MIXTURES

The section explains why PAC-Bayes analysis ideally uses distributions over functions, then uses symmetry mixtures as a tractable but limited approximation and instead centers the prior at random initialization.

  • Neural-network parameterizations form a quotient space because distinct weights can compute the same classifier.
  • PAC-Bayes ideally uses KL divergence between induced distributions over functions, but the quotient space is difficult to handle computationally.
  • Symmetry mixtures spread probability across equivalent parameterizations while preserving the induced function distribution and empirical error.
  • For a symmetry-invariant prior, symmetrization reduces KL divergence by KL(Q||Q_S), so it cannot worsen the bound.
  • For finitely many symmetries, the improvement is bounded by log |S|, and exploiting exponentially many symmetries appears intractable.
  • The paper instead places the prior at random initialization, relying on initialization to break symmetries reflected in learned parameters.

C COMPARING WEIGHTS BEFORE AND AFTER PAC-BAYES OPTIMIZATION

The comparison measures how far the original SGD weights lie under the optimized stochastic-network distribution, finding different behavior for true and randomized labels.

  • The PAC-Bayes optimization allows the posterior mean to deviate from the SGD solution because this produces tighter bounds.
  • The analysis evaluates the p-value of the SGD solution under the optimized stochastic neural network distribution.
  • For true-label experiments, the estimated p-value was 0, meaning the SGD solution was less extreme than a typical perturbation under the optimized distribution.
  • With randomized labels, the optimized mean and SGD solution differed significantly, consistent with optimization against random labels.

D EVALUATING RADEMACHER ERROR BOUNDS

This section evaluates Rademacher-complexity error bounds for ReLU networks using path-norm-based bounds and explains their relation to prior norm-based analyses.

  • The analysis computes Rademacher-complexity bounds for depth-d ReLU networks whose ℓ1 path norms are bounded by φ.The path norm can be computed in a forward pass using one matrix–vector product per layer.
  • Earlier Gaussian-complexity bounds based on γ1,∞ apply only to bounded activations, whereas the path-norm bound is tighter for ReLU networks.ReLU activations are unbounded, so the bounded-activation restriction excludes them from those earlier bounds.
  • Path-norm complexity is invariant to redistributing weights across adjacent layers while preserving the computed ReLU function.This invariance lets the path norm capture network complexity through the smallest equivalent layerwise norm.
  • The bounds combine a general error-bound theorem with a path-norm Rademacher bound for ReLU networks.The experiments use the bound obtained by combining Theorems D.1 and D.2.
  • The bound requires the constant L to be chosen independently of the data, but optimizing L using the data yields an optimistic bound.A union bound can formally permit data-dependent selection of L, although the effect is usually relatively small.

D.1 EXPERIMENT DETAILS

The experiments train a two-layer 600-hidden-unit ReLU network with SGD and compare unregularized training against explicit path-norm regularization.

  • SGD trains a two-layer 600-hidden-unit ReLU network on a binary-class MNIST task using global learning rate 0.005 and average logistic loss.The initialization variance is reduced because standard ReLU initializations produce vacuous initial path-norm bounds.

D.2 RESULTS

For this network, unregularized SGD rapidly makes the path-norm error bound vacuous, while explicit regularization avoids vacuity only at excessive strengths that leave training error high.

  • Within a fraction of a single epoch, the unregularized error bound becomes vacuous before training error falls appreciably below chance.The path norm diverges, while empirical margin growth is insufficient to offset it.
  • Under explicit path-norm regularization, the bounds remain vacuous unless regularization is excessive.At parameters 0.01 and 0.05, training error converges to approximately 20% and 30%, respectively.
  • Strong regularization can make the bound nonvacuous, but only at a trivial 50% guessing error rate with very large training and testing errors.The figure reports this behavior for the strongly regularized setting.
  • Without regularization, the path norm diverges quickly, and margin distributions do not grow rapidly enough to counteract that increase.The figure shows training error, testing error, bounds, path norm, and empirical margin distributions across epochs.
Loading 1703.11008v2…