Research map / Learning theory and algorithms / Kernels and regression theory
Generalization Bounds via Conditional $f$-Information
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.
Introduces generalization bounds in the supersample setting based on conditional f-information, using a variational formula whose CGF term vanishes, and shows squared Hellinger-information bounds are tighter than CMI-type bounds empirically.
Problem
Existing information-theoretic generalization bounds are mostly based on conditional mutual information (CMI) and are loose or vacuous in some regimes; the question is whether the CMI framework generalizes to other f-divergence-based dependence measures and yields tighter bounds, including for unbou
Approach
Derive a variational lower bound on f-information by choosing the measurable function as the inverse convex conjugate applied to the centered loss difference, so the CGF term vanishes; lower-bound the inverse conjugate with quadratic inequalities (inspired by coin-betting) to get bounds for KL, chi-square, squared Hellinger, JS, and truncated-Holder variants for unbounded losses.
Key results
- Squared Hellinger-information bound (CSHI(Var)) is tighter than CMI(Oracle) and ld-CMI on the more complex tasks (MNIST, CIFAR10 with SGLD/ResNet), per the paper's figures.
- Oracle CMI bound yields fast-rate E_mu(A) <= (4/n) sum I(dL_i;U_i) in the realizable/interpolating setting, improving the constant of prior bounds to log(2)-based 1/(n log 2) form for zero-one loss.
- Sharpness bound is tightest for the two-class linear classifier, but applies only to zero-one loss.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use squared Hellinger-information instead of mutual information | Oracle conditional generalization bound · Linear classification, CNN on MNIST 4 vs 9, and ResNet-50 on CIFAR10 | generalization bound | Helped |
| Use CSHI(Var) instead of other f-information-based bounds | Conditional squared Hellinger-information bound · More complex prediction tasks | generalization bound | Helped |
| Replace the empirical loss-difference term with the constant 1 | CSHI(Worst) · More complex prediction tasks | generalization bound | Helped |
| Use the oracle CMI bound instead of the original ld-CMI bound | Conditional mutual-information generalization bound · CNN on MNIST 4 vs 9 and ResNet-50 on CIFAR10 | generalization bound | Helped |
| Use Jensen-Shannon-information instead of mutual information | Conditional generalization bound · Numerical prediction-task comparisons | generalization bound | Helped |
| Use the sharpness-based single-loss MI bound | Sharpness · Linear classifier on two-class synthetic Gaussian data | generalization bound | Helped |
Surprising findings
- Even the pessimistic CSHI(Worst) bound (with E[dL^2] replaced by 1) outperforms most other f-information bounds except Sharpness in several settings.
- The oracle CMI bound is looser than the ld-CMI bound's potential, showing significant room for improvement over the original ld-CMI bound.
Limitations
- Lacks high-probability generalization guarantees (only expected generalization error bounds).
- Some constants (e.g., JS-information bound) are pessimistic and not optimized.
- Unbounded-loss bound's relation between I(dL;U) and I_{phi_alpha} is unclear beyond alpha=1,2.
Experimental setup
Datasets: synthetic Gaussian dataset MNIST (4 vs 9) CIFAR10
Benchmarks: synthetic Gaussian dataset MNIST (4 vs 9) CIFAR10
Metrics: generalization error bound tightness zero-one prediction error
Baselines: ld-CMI Sharpness bound Binary kl CMI bound CMI(Oracle) bound
Builds on: conditional mutual information (CMI) framework ld-CMI bound f-divergence variational representation coin-betting concentration
Closest papers by meaning
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.89)
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.86)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.86)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · similarity 0.85)
- Assouad, Fano, and Le Cam with Interaction: A Unifying Lower Bound Framework and Characterization for Bandit Learnability (NeurIPS 2024 · similarity 0.85)
- Certification-Enhanced Generalization Bounds (NeurIPS 2026 · similarity 0.85)
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.