Research map / Learning theory and algorithms / Kernels and regression theory
Fantastic Generalization Measures are Nowhere to be Found
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proves that generalization bounds depending only on training set, hypothesis, and class cannot be uniformly tight in the overparameterized setting, and shows a learnability-estimability trade-off for algorithm-dependent bounds.
Problem
Whether generalization bounds of the form L_D(A(S)) < L_S(A(S)) + C can be uniformly tight (over all algorithms and distributions) in the overparameterized setting, as empirically many published neural network bounds are not tight.
Approach
Formalizes estimability of population loss by an estimator and shows that VC-type hypothesis classes are not estimable over many (algorithm, distribution) pairs; for algorithm-dependent bounds, shows a trade-off where an algorithm that learns a subclass well cannot be estimable (uniformly tight).
Key results
- Any estimator of VC class H fails over many (algorithm, distribution) pairs: for n <= d/2, not estimable with accuracy about 1/8 for roughly half of combinations.
- For linear functions over F_11 with ERM-with-linear-bias algorithms, not estimable with epsilon 0.45 (failure probability about 0.4).
- For parity functions (q=2), algorithms in the class are not (0.25, 0.14, n)-estimable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Require a generalization bound to depend only on the training set, learned hypothesis, and hypothesis class | Generalization bounds in overparameterized settings · Overparameterized settings | uniform tightness | Hurt |
| Use an algorithm-dependent bound while the algorithm learns a suitable subclass well | Algorithm-dependent generalization bounds · Overparameterized settings | estimability | Hurt |
| Apply any estimator to a VC-dimension d class with sample size n≤d/2 | Generalization-bound estimators · VC classes, realizable distributions | estimability accuracy: at least 49% | Hurt |
| Use a training set of size at most d/2 for a hypothesis class with VC dimension d | Any estimator · Overparameterized setting | estimation error ε: ε ≥ 1/8-o(1) | Hurt |
| Use an algorithm with linear bias for linear functions over a finite field | ERM algorithms with linear bias · Linear functions over F_q, n≤d-1 | estimability: 1/2 - 1/2q | Hurt |
| Use an algorithm with linear bias for parity functions | ERM algorithms with linear bias · Parity functions, n≤d-1 | estimability: (0.25, 0.14, n) | Hurt |
Surprising findings
- Algorithm-independent bounds are not uniformly tight even for simple settings such as a uniform distribution over a small set of natural images, implying distribution-independent bounds can be loose in simple settings.
Limitations
- Results are theoretical and their applicability to specific neural network bounds is debated by the authors themselves.
- Definition of overparameterization is an alternative formal definition rather than the standard one in practice.
- Lower bounds on estimability are asymptotic in d and some constants are only moderately strong for small q.
Experimental setup
Builds on: Jiang et al. 2020 Fantastic Generalization Measures PAC-Bayes bounds VC theory
Closest papers by meaning
- Which Algorithms Have Tight Generalization Bounds? (NeurIPS 2025 · similarity 0.93)
- Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.92)
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.89)
- Certification-Enhanced Generalization Bounds (NeurIPS 2026 · similarity 0.89)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.89)
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.