Generalization in Deep Learning

Kenji Kawaguchi; Leslie Pack Kaelbling; Yoshua Bengio

Source-linked AI summary

Generalization in Deep Learning

Kenji Kawaguchi, Leslie Pack Kaelbling, Yoshua Bengio

arXiv:1710.05468v9Oct 16, 2017stat.MLcs.AIcs.LGcs.NE

TL;DR

The paper addresses why deep learning can generalize despite highly capacious hypothesis spaces and reviews the limitations of existing theoretical explanations. It develops bounds based on validation and training datasets, deriving generalization insights and identifying scope limitations and open problems.

Problem
The central question is why deep models can generalize well despite sufficient capacity to memorize random labels and despite complexity, instability, nonrobustness, and sharp minima.
Method
The paper analyzes linear models, develops validation-dataset bounds, and studies training-dataset bounds for feed-forward ReLU networks with max-pooling.
Results
The analysis shows that overwhelming-capacity linear hypothesis spaces can have arbitrarily small test errors and expected risks, while the proposed bounds can be non-vacuous and quantitatively tight under stated settings.
Takeaways & Limitations
Generalization explanations should account for differences in underlying assumptions and distinguish theoretical analyses from practical model-selection procedures.
Takeaways & Limitations
Theorem 8 relies on pre-defined bounds in Assumption 1 for random datasets, whereas Theorem 7 is tighter for each given dataset.

Abstract

from arXiv · show

This paper provides theoretical insights into why and how deep learning can generalize well, despite its large capacity, complexity, possible algorithmic instability, nonrobustness, and sharp minima, responding to an open question in the literature. We also discuss approaches to provide non-vacuous generalization guarantees for deep learning. Based on theoretical observations, we propose new open problems and discuss the limitations of our results.

1. Introduction

The paper frames generalization as the unresolved question of why highly expressive deep models can predict future data without overfitting. It examines this tension theoretically and develops bounds intended to provide non-vacuous guarantees.

Expressive and trainable hypothesis spaces do not by themselves guarantee good prediction on future inputs because models may overfit training data.
Deep hypothesis spaces can represent some natural target functions efficiently when the target approximately satisfies assumptions such as deep composition of piecewise linear transformations.
Successful deep hypothesis spaces can memorize random labels, creating an apparent paradox for explanations based on low-capacity hypotheses.
Even linear models with overwhelming capacity can achieve arbitrarily small test errors and expected risks, motivating a broader open problem about deep-learning generalization.
The paper proposes validation-dataset bounds that can provide non-vacuous, numerically tight guarantees and training-dataset theory for ReLU networks with max-pooling.

2. Background

The background reviews generalization theory through expected and empirical risk, hypothesis-space complexity, stability, robustness, and flat-minima approaches. It emphasizes that existing approaches can face vacuous bounds, dimensionality costs, or sensitivity to dataset dependence.

Generalization theory studies when minimizing empirical risk is a sensible approach to minimizing the non-computable expected risk.
The generalization gap is difficult to analyze because the learned model depends on the same dataset used to compute empirical risk.
Hypothesis-space complexity bounds decouple the learned model from a particular dataset but require complexity measures such as Rademacher complexity or VC dimension.
Deep-learning complexity bounds can depend exponentially on depth or linearly on the number of trainable parameters, and existing solutions remain tied to hypothesis-space complexity.
Stability measures how changing one data point can change the learned model, whereas robustness measures loss variation across the input space.
Robustness bounds require an a priori fixed input-space partition and can still suffer from the curse of dimensionality.
Flat minima represent low variation in parameter space, but practical deep-learning flat minima can be transformed into sharp minima through re-parameterization.

3. Rethinking generalization

The paper argues that small generalization error can occur despite high capacity, instability, non-robustness, and sharp minima, and distinguishes theory’s broad problem-set scope from practice’s instance-specific focus. It formulates tighter instance-level open problems and identifies practical roles for generalization theory.

Over-parameterized linear models can memorize any training data while driving training and test errors arbitrarily close to zero, even with arbitrarily large parameter norms.This extends empirical observations about memorization and small test errors beyond deep networks.
Small generalization gaps do not require small capacity, low complexity, stability, robustness, or flat minima for a given problem instance.The paper states that these properties can be sufficient but are not necessary for generalization.
The paper’s central open problem is to characterize expected risk or generalization gap using only a hypothesis and the specific pair (P(X,Y ), S).A solution to this problem would imply solving the broader deep-learning problem that distinguishes natural from random-label instances.
3.1 Consistency of theory: Statistical learning theory commonly gives sufficient conditions or worst-case lower bounds over sets of problem configurations, so small gaps may still occur outside the characterized bad subset.Thus, large complexity or instability does not contradict a small observed generalization gap.
3.3 Practical role of generalization theory: The paper identifies guiding searches over model classes as one practical role for generalization theory because theory and practice can address different scopes.The authors explicitly note that theoretical bounds may be pessimistic for particular problem instances.

4. Generalization bounds via validation

The paper develops validation-set generalization bounds for model selection under a held-out validation set independent of training. These bounds can remain non-vacuous and practically meaningful even when many candidate models are searched.

A held-out validation set independent of training supports a generalization guarantee for every candidate in a validation-independent model set.The candidate set may depend on training data but not on the held-out validation set.
The validation-based bound remains non-vacuous with 10,000 validation examples, confidence parameter δ = 0.1, and up to 1,000,000,000 candidate models in a 0–1 loss classification task.The cited example states that the guarantee holds with probability at least 0.9.
In a non-worst-case scenario with C = 1 and γ2 = (0.05)2, the bound’s example value can decrease from 6.94% to 0.49%.The paper notes that larger validation sets or more optimistic parameters can yield better bounds.
Increasing the number of validation-searched candidates raises the bound only at a ln |Fval| rate under the stated proposition.The paper also describes an alternative that avoids direct dependence on the cardinality of Fval.
The effective candidate complexity can differ substantially from the parameterized hypothesis space because candidates may be filtered using training data and search procedures.If hyperparameter search uses the validation set, the bound must cover the possible search space rather than only visited models.

5. Direct analyses of neural networks

This section directly analyzes neural-network generalization for specified and random datasets, rather than deriving results from generic capacity-based theories. The resulting bounds provide tight, data-dependent insights for several practical deep-learning architectures and losses.

5. Direct analyses of neural networks: The section analyzes neural networks directly for both specified datasets and random datasets, rather than relying on generic capacity, stability, or robustness theories.The analysis covers practical networks represented as directed acyclic graphs with ReLU nonlinearities and/or max pooling, including convolutional, fully connected, and skip-connected architectures.
5.2 Theoretical insights via tight theory for every pair (P, S): Theorem 7 tightly analyzes the squared-loss generalization gap for any dataset using the learned model’s quality and the pair (P(X,Y), S).It does not assume that S was randomly generated from P(X,Y).
5.2 Theoretical insights via tight theory for every pair (P, S): Theorem 7 identifies weight norms, dataset concentration in the learned representation, and label concentration as factors governing the generalization gap.Deep-path feature learning can concentrate data in the learned representation space even when the original dataset is not concentrated there.
5.2 Theoretical insights via tight theory for every pair (P, S): Theorem 7 uses a tight equality rather than an inequality, yielding more precise theoretical insights when the resulting regularization guidance is the same.The equality preserves the exact ordering of problem instances without requiring bounds.
5.2 Theoretical insights via tight theory for every pair (P, S): Figure 2 reports competitive two-phase performance even when the smaller dataset used to learn wσ is only α = 0.05 of the data.At α = 0.05, αm equals 3000 for MNIST and 2500 for CIFAR-10.
5.3 Theoretical results: Theorem 8 gives a strongly data-dependent bound for the two-phase procedure on random datasets, while Theorem 7 is tighter for each instantiated dataset.Theorem 8 assumes an i.i.d. draw for the portion outside Sαm and independence from Sαm.
5.3 Theoretical results: Theorems 7–9 need not depend explicitly on the number of weights or exponentially on depth and effective input dimensionality.This applies to the squared-loss and multi-label 0–1-loss analyses described in the section.

6. Discussions and open problems

The discussion argues that useful generalization theory should characterize specific problem instances while preserving their performance ordering. It identifies open problems involving order-preserving analyses, human-guided architecture selection, and broader applicability of the presented results.

6. Discussions and open problems: Detailed characterization of a specific hypothesis requires information about the given problem instance, motivating analyses tailored to particular data and models.The paper contrasts this goal with traditional theory, which is limited by generic information about distributions, datasets, and hypothesis classes.
Open problems: The paper warns that theoretical insights can mislead when they fail to preserve the preference ordering of problem instances (P, S, f).It therefore proposes tightly characterizing expected risk or generalization gap while partially preserving this ordering.
Open problems: Theorem 7 partially addresses this ordering problem by preserving exact ordering through equality without bounds.The paper proposes studying weaker order-preservation notions to obtain more analyzable and useful insights.
Open problems: The paper identifies human intelligence in selecting architectures and hyperparameters as an open problem connected to engineering and scientific priors.Examples include hierarchical structure, convolution, motion architectures, and memory networks.
Limitations and future directions: Theorem 7 has limited applicability because it addresses only certain neural networks with squared loss.The paper suggests combining generic learning theory with concrete deep-learning analyses tailored to particular cases.
Technical discussion: Using many data-dependent hypothesis spaces or choices of wσ may require pre-decided families and union bounds, adding quantities to the resulting bounds.The construction must avoid choosing the family solely as a function of the full dataset.

A1 Simple regularization algorithm

This section motivates regularizing the learned hypothesis directly and proposes a family of mini-batch regularizers based on samples approximating the true input distribution. A simple implementation, DARC1, adds the regularization term to standard MNIST and CIFAR-10 training codes, with improvements observed in all evaluated cases.

Motivation: Theoretical bounds can be too loose for practice, motivating simpler regularization approaches based on hypothesis smoothness.The section contrasts statistical-learning-theory bounds with directly regularizing smoothness.
Method: The proposed family adds a new regularization term for each mini-batch to arbitrary architectures and training methods.The term uses a mini-batch size and a hyper-parameter, with independently sampled signs in the described formulation.
Method: The input distribution used for regularization need only be approximate and may come from a generative neural network or additional data augmentation.The approximation is not used as the training distribution itself.
Implementation: DARC1 was evaluated by adding the proposed regularization term to existing standard MNIST and CIFAR-10 code with almost negligible additional computational cost and programming effort.The experiments used a simple version of the broader proposed family.
Results: The DARC1 test errors were comparable with previous results, and improvements were observed for all evaluated cases.Base-model test errors were 0.53% for MNIST (ND), 0.28% for MNIST, and 7.11% for CIFAR-10.
Results: Data augmentation alone implicitly regularized the quantity explicitly regularized by the proposed method in the comparison between MNIST (ND) and MNIST.The learned models also differed significantly from base models in the value of the regularization term.

B. Appendix: Experimental details

The appendix specifies the fixed architectures, data augmentation procedures, optimization settings, and training durations used for the experiments.

Architecture: The fixed architecture includes two convolutional layers with 32 filters, max pooling and ReLU, followed by fully connected layers with 1024 and 10 units.The 1024-unit layer uses ReLU and dropout.
Architecture: Layer 4 outputs z[L], which is passed through softmax for training, while argmax(z[L](x)) gives the predicted label.This defines the model output and label prediction used in the appendix.
Data augmentation: Data augmentation used random horizontal flips with probability 0.5 and random crops of size 32 with padding 4.Another described augmentation setting used random crops, rotations up to ±15 degrees, and 15% scaling.
Optimization: For Table 1, training used ResNeXt-29(16 × 64d), SGD with Nesterov momentum, momentum 0.9, scheduled learning rates, and 300 epochs.The learning rate decreased from 0.05 to 0.005 at 150 epochs and 0.0005 at 250 epochs.
Optimization: For Tables 2 and 3, training used pre-activation ResNet-18, standard SGD, learning rate 0.001, momentum 0.9, and 1000 epochs.These settings apply to the smaller-model experiments.

C. Appendix: Proofs

The appendix invokes the Matrix Bernstein inequality as a proof tool, stating assumptions on independent self-adjoint random matrices and deriving a high-probability bound by solving for the deviation parameter.

Lemma 10: Lemma 10 applies the Matrix Bernstein inequality to a finite sequence of independent, random, self-adjoint matrices.The matrices have dimension d, zero expectation, and an almost-sure upper bound on their maximum eigenvalue.
Lemma 10: The lemma defines γ2 using the squared norm of the summed matrix variance terms and provides a probability statement for any δ > 0.The bound holds with probability at least 1 − δ.
Proof: The proof starts from Tropp’s theorem for all t ≥ 0, then solves the resulting inequality for t using the quadratic formula.The solution is bounded using subadditivity of the square root on non-negative terms.

C1 Proof of Theorem 1

The proof decomposes parameter space into components aligned with the matrix column space and null space, showing that parameters can vary without changing specified outputs while a norm-related quantity grows unboundedly.

Proof of Theorem 1: The proof uses column-space and null-space decompositions of parameter vectors to establish the theorem’s statements.It relies on rank conditions to show that the matrix columns span the relevant space and that a nontrivial null space exists.
Proof of Theorem 1: A parameter is constructed from column-space and null-space components, with independent scaling of the null-space component.The construction uses C1 in Col(M^T), C2 in Null(M), and α ≥ 0.
Proof of Theorem 1: The same parameter preserves the quantities A and B after suitable normalization while a related quantity grows unboundedly as α →∞.This proves statement (c) in the referenced theorem statement.
Generalization-gap analysis: For deep models with squared loss, the proof rewrites the pointwise loss and decomposes the generalization gap into three terms.The decomposition begins from Equation (1).
Generalization-gap analysis: The proof diagonalizes the real symmetric matrix G as G = UΛU⊤, with Λ containing eigenvalues λj and U containing orthogonal eigenvectors.The j-th column of U is denoted uj.

C4 Proof of Theorem 8

The proof decomposes the target bound into several terms and controls them with concentration inequalities under a frozen parameter setting. Combining these bounds yields a probability statement over the held-out sample, while the deterministic relation completes the theorem.

C4 Proof of Theorem 8: The concentration argument relies on independence across sample indices after fixing wσ, while allowing dependence across coordinates.The frozen parameter is independent of the remaining samples, making the relevant random variables independent over the sample index.
C4 Proof of Theorem 8: The proof bounds each term on the right-hand side using concentration inequalities.The decomposition is introduced before applying separate bounds to its terms.
C4 Proof of Theorem 8: Matrix Bernstein inequality controls the first term after verifying the centeredness and norm conditions of the constructed matrices.The proof states E[Mi] = 0 and bounds λmax(Mi) before applying the inequality.
C4 Proof of Theorem 8: Bernstein inequality with a union bound controls coordinate- or index-wise events for the second and third terms.The second term uses a union bound over dydz events, while the third term receives a separate Bernstein bound.
C4 Proof of Theorem 8: Combining the component bounds gives a bound with probability at least 1−δ over the samples outside Sαm for fixed wσ.The remaining theorem statement follows because Equation (C.1) holds deterministically.

C5 Proof of Theorem 9

The proof first establishes a uniform concentration statement over a validation hypothesis space, then specializes a Rademacher-based bound to parameterized spaces with frozen parameters. It concludes by combining these ingredients and selecting the valid Bernstein solution.

C5 Proof of Theorem 9: A recalled Koltchinskii–Panchenko result supplies a uniform Rademacher-variable bound over output coordinates and hypotheses.The supremum ranges over all k and all w allowed in F.
C5 Proof of Theorem 9: For frozen parameterized hypothesis spaces, Jensen’s inequality and linearity of expectation are used before assembling the final bound.Concavity of the square root justifies the Jensen step.
C5 Proof of Theorem 9: The validation proof applies Bernstein inequality to independent zero-mean variables for each fixed hypothesis.Independence follows because the validation hypothesis space is independent of the validation dataset.
C5 Proof of Theorem 9: A union bound extends the fixed-hypothesis Bernstein bound uniformly over all elements of Fval.The proof explicitly takes the union bound over Fval.
C5 Proof of Theorem 9: The Bernstein inversion uses the plus-sign solution because the minus-sign solution gives an invalid negative epsilon.The proof rejects the negative solution as incompatible with Bernstein’s inequality.
C5 Proof of Theorem 9: The resulting validation guarantee holds for all f ∈ Fval with probability at least 1−δ.This is obtained by negating the failure statement after the union-bound argument.