Research map / Learning theory and algorithms / Sample complexity
Towards a Unified Information-Theoretic Framework for Generalization
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use stability in a size-k sample compression scheme | Sample compression · Realizable distributions | CMI upper bound: k \log(2n) -> 2k \log 2 | Helped |
| Analyze SVM as a stable compression scheme of size d+1 | SVM · Realizable halfspaces in R^d | expected risk upper bound: 2(d+1)/n | Helped |
| Use evaluated CMI for a learner whose output lies in a VC class | Any learner outputting from a class of VC dimension d_n · VC classes | evaluated CMI upper bound: d_n \log 6n | Helped |
| Release the version space when the class has finite star number | Version space · Realizable distribution, n ≥ s | version-space CMI: 2 \mathfrak{s} \log 2 | Helped |
| Release the version space for a class with unbounded star number | Version space · Realizable distribution | version-space CMI: \Omega(\newmin\{\mathfrak{s},n\}) | Hurt |
| Choose the least consistent classifier from the version space | ERM for a VC class with finite star number · Realizable distributions, n ≥ s | CMI upper bound: O\big(d \log ( \mathfrak{s} /d )\big) | Helped |
| Use a leave-one-out error guarantee to bound evaluated CMI | Consistent learner · Realizable distribution | evaluated CMI upper bound: \theta \log( {(n+1)}/{\theta}) + 2\theta\log 2 | Helped |
| Apply the leave-one-out-to-eCMI reduction to the deterministic one-inclusion graph | One-inclusion graph · Realizable VC class of dimension d | evaluated CMI upper bound: d \log( {(n+1)}/{d}) + 2 d \log2 | Helped |
| Randomize the one-inclusion graph prediction rule | One-inclusion graph · Realizable point functions on R | evaluated CMI upper bound: O(1) | Helped |
| Require a proper learner with bounded CMI for every VC class | Proper learning of VC classes · Realizable VC classes | proper learner CMI | Hurt |
Closest papers by meaning
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.92)
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.89)
- Slicing Mutual Information Generalization Bounds for Neural Networks (ICML 2024 · similarity 0.88)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.87)
- Generalizability of Neural Networks Minimizing Empirical Risk Based on Expressive Power (ICLR 2025 · similarity 0.86)
- Which Algorithms Have Tight Generalization Bounds? (NeurIPS 2025 · similarity 0.86)
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.