Questions: Generalization Bounds for Deep Networks

Question 1

A network with 10^7 parameters achieves 1% training error and 5% test error. The VC-dimension-based bound predicts the test error could be as high as 100% (the bound is vacuous). Why do VC-based bounds fail here?

• A. VC dimension does not apply to neural networks because they are non-linear
• B. The VC dimension is proportional to the number of parameters (~10^7), making the bound O(sqrt(10^7/n)) — which exceeds 1 for any reasonable training set size, rendering the bound vacuous (greater than the trivial 100% bound)
• C. VC-based bounds require convex hypothesis classes, and neural networks are non-convex
• D. The training error of 1% is too high for VC bounds to be informative

Answer: (B)

For neural networks, the VC dimension is at least proportional to the number of parameters (roughly O(W*L) for W weights and L layers). With 10^7 parameters and, say, 50,000 training examples, the VC-based generalization bound is O(sqrt(10^7/50000)) = O(sqrt(200)) ≈ 14 — the bound says test error could be 14 units above training error, which exceeds 100% and is completely uninformative. The bound fails because it treats every set of parameters as equally likely, ignoring that SGD finds solutions in a tiny corner of parameter space with special structure (small norms, low rank, etc.). Better bounds must measure this effective complexity rather than the raw parameter count.

Question 2

PAC-Bayes bounds depend on the KL divergence between the learned weight distribution and a prior distribution chosen before seeing data. Why is the choice of prior critical?

• A. A bad prior makes the bound infinite, while a good prior that places mass near the learned weights gives a tight bound
• B. The prior must be a Gaussian distribution — other distributions are not valid
• C. The prior controls the learning rate of the optimization algorithm
• D. The prior is irrelevant — PAC-Bayes bounds are prior-free in practice

Answer: (A)

The PAC-Bayes bound states that the generalization gap is O(sqrt(KL(posterior || prior) / n)). If the prior is far from the learned weights (high KL divergence), the bound is loose. If the prior is close (low KL), the bound is tight. The prior must be chosen BEFORE seeing the data — this is essential for the bound's validity. Data-dependent priors (chosen after seeing the training data) invalidate the guarantee. The art of PAC-Bayes for deep networks is choosing priors that are data-independent yet close to typical learned weights — for instance, priors centered at the initialization, since SGD tends to stay near initialization in over-parameterized networks.

Question 3

Spectrally-normalized margin bounds grow with the product of layer spectral norms, not the number of parameters. This means a 1000-layer network with small spectral norms per layer can generalize better than a 2-layer network with large spectral norms.

• T. True
• F. False

Answer: True

Spectral-norm bounds (Bartlett et al., 2017; Neyshabur et al., 2018) control the Rademacher complexity of a deep network by the product of layer-wise spectral norms (the largest singular value of each weight matrix) divided by the margin. A deep network with spectral norms near 1 per layer (e.g., through batch normalization or careful initialization) has a bounded spectral norm product regardless of depth. A shallow network with unconstrained large weight matrices can have a huge spectral norm product. The bound depends on this product, not the depth or parameter count — so yes, a deep, well-controlled network can have better generalization guarantees than a shallow, poorly controlled one.

Question 4

Explain why compression-based generalization bounds are conceptually natural for deep networks and how they avoid the parameter-counting problem.

Model answer: Compression-based bounds argue that if a trained network can be compressed to a description of length k bits without significantly changing its predictions, then its generalization error depends on k, not the original parameter count. Modern deep networks are highly compressible: weights can be quantized, pruned, or factored into low-rank matrices with minimal performance loss. If a 10-million-parameter network can be compressed to an effective description of 100,000 parameters, the generalization bound depends on 100,000 rather than 10,000,000. This is conceptually natural because compression measures the actual information content of the learned function, not the size of the container (parameter space) it was found in. A network that memorizes random labels cannot be compressed (every label is independent information), while a network that learns a genuine pattern has low-entropy weights that compress well — exactly matching the empirical observation that the former does not generalize while the latter does.

Compression bounds connect to the minimum description length (MDL) principle and Kolmogorov complexity. The practical challenge is that computing the best compression is hard, so compression-based bounds require specifying a particular compression scheme, and the bound quality depends on how well that scheme captures the network's actual structure.