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 đŸ”’.
  • 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 đŸ”’.
  • 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.
    • 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.
  • 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.

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.
    • 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.
  • 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.
  • 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.

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.
  • 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.

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.
  • 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.
  • 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.
  • 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.
    • 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.
  • 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.
  • 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.
    • 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.

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.
  • 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.

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.
    • 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.
  • 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.
  • 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.
  • 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.

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.

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.
  • 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.
  • 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.
  • 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.
  • 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.