Generalization and Learning Theory

Learning targets and capacity

• PAC and agnostic learning — 2014. 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.
• VC dimension and uniform convergence — 2014. 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.
• Rademacher complexity — 2002. 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.
• Local Rademacher complexity — 2005. 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.
• Spectral margin bounds — 2017. 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.

Algorithm-dependent bounds

• Algorithmic stability — 2002. 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.
• SGD stability — 2015. 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.
• Information-theoretic bounds — 2017. 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.
• Compression bounds — 2018. 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.

PAC-Bayes and stochastic predictors

• PAC-Bayes — 2021. 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.
• Nonvacuous neural bounds — 2017. 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.

Optimization bias and interpolation

• Random-label fitting — 2016. 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.
• Implicit max-margin bias — 2018. 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.
• Double descent — 2018. 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.
• Deep double descent — 2019. 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.
• Benign overfitting — 2019. 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.
• Neural tangent kernel — 2018. 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.
• Grokking — 2022. 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.

Sharpness and parameterization

• Sharp minima can generalize — 2017. 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.
• Sharpness-aware minimization (SAM) — 2020. 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.

Group robustness and invariant predictors

• Group DRO — 2019. 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.
• Invariant risk minimization (IRM) — 2019. 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.
• IRM failure cases — 2020. 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.
• Risk extrapolation (REx) — 2021. 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.

Limits of predictive coverage

• Conditional coverage limits — 2019/2021. 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.

Testing explanations and distribution shifts

• Limits of uniform-convergence explanations — 2019. 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.
• Comparing generalization measures — 2019. 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.
• Underspecification — 2022. 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.
• DomainBed — 2020. 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.
• WILDS — 2020. 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.
• Evaluate a generalization claim. Separate a theorem’s assumptions, an empirical correlation and a deployment stress test. Specify train/test distributions and compare predictors under the same selection procedure; these provide different evidence.

Related topics

Evaluation · Neural networks · Optimization · Transfer learning · Meta-learning · Bayesian inference.

Star Issue