# Generalization and Learning Theory 🔒 Full text at this link requires payment or institutional access. Unmarked links may be unchecked. ## Learning targets and capacity - **PAC and agnostic learning** - PAC learning bounds the samples needed for low population error with high probability; agnostic learning compares with the best predictor in a chosen class. The data distribution, loss and hypothesis class define the claim. [Shalev-Shwartz and Ben-David 2014 🔒]( "Understanding Machine Learning: From Theory to Algorithms; book"). - **VC dimension and uniform convergence** - For binary classification, finite VC dimension characterizes distribution-free PAC learnability under the standard assumptions. Uniform convergence controls empirical-population error across a hypothesis class. [Shalev-Shwartz and Ben-David 2014 🔒]( "Understanding Machine Learning: From Theory to Algorithms; book"). - **Rademacher complexity** - Measures how well a function class fits random signs on sampled inputs. Bartlett and Mendelson derive data-dependent risk bounds and composition rules; the class and loss still determine the guarantee. [Bartlett and Mendelson 2002]( "Rademacher and Gaussian Complexities: Risk Bounds and Structural Results; JMLR"). - **Local Rademacher complexity** - Measures complexity near low-error predictors rather than over the whole hypothesis class. Bartlett et al. obtain sharper risk bounds using localization; fast rates rely on additional loss and variance conditions. [Bartlett et al. 2005]( "Local Rademacher complexities; Ann. Statist."). - **Spectral margin bounds** - Bartlett et al. bound multiclass error using margins and spectral complexity of network weights. This connects prediction margins to weight norms; counting parameters alone misses the bound's dependence on the fitted predictor. [Bartlett et al. 2017]( "Spectrally-normalized margin bounds for neural networks; NeurIPS"). ## Algorithm-dependent bounds - **Algorithmic stability** - Bousquet and Elisseeff relate sensitivity to training-sample changes to generalization bounds. Stability analyzes the learning procedure, allowing regularized algorithms to be studied beyond hypothesis-class size. [Bousquet and Elisseeff 2002]( "Stability and Generalization; JMLR"). - **SGD stability** - Hardt et al. bound generalization through the stability of stochastic gradient updates under Lipschitz and smoothness assumptions. Convex and nonconvex analyses differ; iteration count and step sizes enter the bounds. [Hardt et al. 2016]( "Train faster, generalize better: Stability of stochastic gradient descent; ICML"). - **Information-theoretic bounds** - Xu and Raginsky bound generalization using information shared by the training sample and algorithm output. Their results connect data dependence to error; they are not a claim that every useful representation must discard information. [Xu and Raginsky 2017]( "Information-theoretic analysis of generalization capability of learning algorithms; NeurIPS"). - **Compression bounds** - Arora et al. derive generalization bounds from compressed networks that preserve predictions under noise-stability conditions. Parameter count and effective description length need not coincide. [Arora et al. 2018]( "Stronger generalization bounds for deep nets via a compression approach; ICML"). ## PAC-Bayes and stochastic predictors - **PAC-Bayes** - Bounds risk of a distribution over predictors using empirical risk and divergence from a reference prior. Prior choice and its dependence on data require care; a PAC-Bayes posterior need not be a Bayesian posterior. [Alquier 2024]( "User-friendly introduction to PAC-Bayes bounds; Found. Trends ML"). - **Nonvacuous neural bounds** - Dziugaite and Roy optimize PAC-Bayes bounds for stochastic neural classifiers with more parameters than examples. The reported guarantees concern the resulting randomized predictors, not automatically the original deterministic network. [Dziugaite and Roy 2017]( "Computing Nonvacuous Generalization Bounds for Deep (Stochastic) Neural Networks with Many More Parameters than Training Data; arXiv"). ## Optimization bias and interpolation - **Random-label fitting** - Zhang et al. show convolutional networks can fit random labels and noise inputs. Capacity to memorize does not explain why the same training procedure generalizes on structured data. [Zhang et al. 2017]( "Understanding deep learning requires rethinking generalization; ICLR"). - **Implicit max-margin bias** - Gradient descent on unregularized logistic regression converges in direction to a max-margin solution for separable homogeneous linear predictors. Soudry et al. distinguish this directional limit from convergence of coefficient norms. [Soudry et al. 2018]( "The Implicit Bias of Gradient Descent on Separable Data; JMLR"). - **Neural tangent kernel** - Jacot et al. show an infinite-width limit where the training kernel stays constant, enabling function-space analysis. This limiting description does not by itself explain feature learning in finite networks. [Jacot et al. 2018]( "Neural Tangent Kernel: Convergence and Generalization in Neural Networks; NeurIPS"). - **Double descent** - Belkin et al. connect classical error curves with a second descent beyond interpolation in studied models. Increasing capacity can cross qualitatively different regimes; the curve is not a universal monotonicity law. [Belkin et al. 2019]( "Reconciling modern machine learning practice and the bias-variance trade-off; PNAS"). - **Deep double descent** - Nakkiran et al. observe nonmonotonic test error with model size and training duration; in some studied regimes, adding training data also hurts. The results qualify simple capacity or data-size heuristics. [Nakkiran et al. 2020]( "Deep Double Descent: Where Bigger Models and More Data Hurt; ICLR"). - **Benign overfitting** - Bartlett et al. characterize when minimum-norm linear interpolation predicts well despite fitting noise. Effective ranks of the input covariance matter; the theorem is not a guarantee for arbitrary overparameterized networks. [Bartlett et al. 2020]( "Benign Overfitting in Linear Regression; PNAS"). - **Grokking** - Power et al. observe delayed generalization after memorization on small algorithmic datasets. Training loss can plateau long before test accuracy improves; the evidence concerns these controlled tasks. See [softmax collapse]() for numerical effects. [Power et al. 2022]( "Grokking: Generalization Beyond Overfitting on Small Algorithmic Datasets; arXiv"). - **Representation-readout dynamics** - Frozen-feature probes separate encoder learning from classifier fitting. In one MNIST grokking recipe, representation quality degrades while the readout overfits; delayed test gains need not imply that useful representations appear suddenly. [Chou et al. 2026]( "Two Speeds of Learning: A Representation-Readout Decomposition of Grokking and Double Descent; NeurIPS"). ## Sharpness and parameterization - **Sharp minima can generalize** - Dinh et al. construct equivalent ReLU networks with arbitrarily different sharpness. Parameter symmetries can change loss geometry while preserving predictions, so flatness comparisons need a specified parameterization. [Dinh et al. 2017]( "Sharp Minima Can Generalize For Deep Nets; ICML"). - **Sharpness-aware minimization (SAM)** - Minimizes worst-case loss near the current weights. Foret et al. report gains on image benchmarks and noisy labels; these experiments support an optimization method, not a parameterization-independent explanation of generalization. [Foret et al. 2021]( "Sharpness-Aware Minimization for Efficiently Improving Generalization; ICLR"). ## Group robustness and invariant predictors - **Invariant risk minimization (IRM)** - Learns a representation admitting the same optimal classifier across training environments. The objective seeks shared predictive structure; the observed environments determine which invariances can be identified. [Arjovsky et al. 2019]( "Invariant Risk Minimization; arXiv"). - **IRM failure cases** - Rosenfeld et al. construct linear and nonlinear settings where IRM fails to recover an invariant predictor or generalize to shifted data. Success across observed environments does not ensure success under arbitrary new shifts. [Rosenfeld et al. 2021]( "The Risks of Invariant Risk Minimization; ICLR"). - **Group DRO** - Optimizes the worst loss over predefined groups. Sagawa et al. find that strong regularization or early stopping is needed to improve worst-group test accuracy in their overparameterized image and language models. [Sagawa et al. 2020]( "Distributionally Robust Neural Networks for Group Shifts: On the Importance of Regularization for Worst-Case Generalization; ICLR"). - **Performative prediction** - Deployment changes the data distribution. Retraining can converge to a stable point distinct from the performative optimum; sufficient conditions include smoothness, strong convexity and weak distribution sensitivity. [Perdomo et al. 2020]( "Performative Prediction; ICML"). - **Risk extrapolation (REx)** - Models shifts beyond mixtures of training domains. V-REx penalizes variance of domain risks; IRM instead constrains the optimal classifier. REx assumes observed domain variation is informative about future shifts. [Krueger et al. 2021]( "Out-of-Distribution Generalization via Risk Extrapolation (REx); ICML"). ## Limits of predictive coverage - **Conditional coverage limits** - Barber et al. distinguish coverage averaged over test inputs from coverage at each input. Nontrivial exact conditional guarantees are generally impossible without distributional restrictions; the paper studies feasible relaxations. [Barber et al. 2020]( "The limits of distribution-free conditional predictive inference; Information and Inference: A Journal of the IMA"). ## Testing explanations and distribution shifts - **Limits of uniform-convergence explanations** - Nagarajan and Kolter construct settings where two-sided uniform-convergence bounds remain vacuous despite low test error. Their counterexamples limit this proof strategy, not learning theory as a whole. [Nagarajan and Kolter 2019]( "Uniform convergence may be unable to explain generalization in deep learning; NeurIPS"). - **Comparing generalization measures** - Jiang et al. test over 40 measures on over 10,000 CNNs. Sharpness-related measures show promising correlations, while several norm-based measures fail comparisons; results depend on the examined interventions. [Jiang et al. 2020]( "Fantastic Generalization Measures and Where to Find Them; ICLR"). - **DomainBed** - Gulrajani and Lopez-Paz find tuned empirical risk minimization competitive with tested domain-generalization methods. Model selection materially affects comparisons; unseen-domain claims must specify selection data. [Gulrajani and Lopez-Paz 2021]( "In Search of Lost Domain Generalization; ICLR"). - **WILDS** - Ten datasets test natural shifts across hospitals, camera locations, time and other domains. Standard training and the tested shift-robust methods retain substantial out-of-distribution gaps; synthetic shifts alone miss these deployment conditions. [Koh et al. 2021]( "WILDS: A Benchmark of in-the-Wild Distribution Shifts; ICML"). - **Underspecification** - D'Amour et al. find similarly accurate in-distribution predictors can behave differently under deployment stress tests. Matching one held-out score does not establish equivalent behavior across environments. [D'Amour et al. 2022]( "Underspecification Presents Challenges for Credibility in Modern Machine Learning; JMLR"). ## Related topics - [Evaluation](https://mlpapers.org/evaluation/) - [Neural networks](https://mlpapers.org/neural-nets/) - [Optimization](https://mlpapers.org/optimization/) - [Transfer learning](https://mlpapers.org/transfer-learning/) - [Meta-learning](https://mlpapers.org/meta-learning/) - [Bayesian inference](https://mlpapers.org/bayesian-inference/)