Research map / Learning theory and algorithms / Kernels and regression theory
Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence
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.
Derives information-theoretic generalization bounds linking expected empirical and population risk via a binary Jensen-Shannon divergence, with a binarized-loss mutual information that yields exactly tight bounds for bounded losses.
Problem
Information-theoretic generalization bounds converge slowly (O(1/sqrt n)) and overestimate generalization error, and some existing evaluated-loss bounds fail to vanish for certain stochastic convex optimization problems.
Approach
A lemma bounding the binary JS divergence between conditional expectations of a function of X given a fair binary variable by I(X;Y); applied with supersample indicators it gives a single-sample conditional MI hypothesis bound, a single-loss MI prediction bound, and a binarization of losses (Bernoulli rounding) that makes the bound exactly tight for bounded losses.
Key results
- Binary JS bound recovers the true generalization error exactly for binary 0-1 loss (Theorem 3.9), and Corollary 3.10 extends this to any bounded loss via binarization.
- Binary JS bound stays non-vacuous for any population risk in [Ln, 1] in the Figure 1 comparison (Ln=0.2), whereas square-root, fast-rate, and binary KL bounds become vacuous around Lµ ≳ 0.8.
- On the Example 3.11 stochastic convex optimization instance, the bound based on single-loss MI does not vanish, while the binarized-loss bound remains valid and tight.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use binary JS divergence instead of the square-root, fast-rate, or binary KL bounds | Expected population-risk estimation in the supersample setting · Figure 1 comparison | population-risk bound tightness | Helped |
| Condition on one sample rather than the sample pair | SICIMI hypothesis-based bound · Generalization bounds | upper-bound tightness | Helped |
| Use binarized loss mutual information instead of single-loss mutual information | Binary JS bound · Bounded loss functions | generalization-bound tightness | Helped |
| Use the exactly tight Binary JS bound | General randomized learning algorithms · Figure 3 learning scenarios | generalization-error tracking | Helped |
| Use the Binary JS bound rather than the Fast-Rate bound | Generalization analysis with continuous loss functions · Figure 3 continuous-loss experiments | generalization-bound tightness | Helped |
Surprising findings
- The single-loss binary JS bound (Theorem 3.6) does not vanish for the stochastic convex optimization example of Haghifam et al. (2023), since I(L0_i;U_i) is Omega(1) there.
- Single-sample conditioning I(W;U_i|Z0_i) is strictly tighter than the previous pair-conditioned variant, yet for Example 3.5 the proposed hypothesis bound is still not exact.
Limitations
- Truncation-based extension to unbounded losses requires the stringent condition delta_j Ln <= delta_j Lµ for all j, which may fail in practice.
- Bounds are for expected generalization, not high-probability guarantees.
- Binary JS approach is limited to the supersample setting, as the comparator argument does not carry over to standard I(W;Z) measures.
Experimental setup
Datasets: synthetic Gaussian binary MNIST (4 vs 9) CIFAR10
Benchmarks: synthetic Gaussian linear classification binary MNIST (4 vs 9) CIFAR10 fine-tuning
Metrics: generalization error bound tightness population risk bound value
Baselines: Fast-Rate bound Binary KL bound CMI oracle CSHI oracle CJSI oracle square-root bound
Builds on: Hellström & Durisi binary KL bound Wang & Mao single-loss mutual information supersample CMI (Steinke & Zakynthinou) Harutyunyan et al. f-CMI
Closest papers by meaning
- Information Theoretic Lower Bounds for Information Theoretic Upper Bounds (NeurIPS 2023 · similarity 0.93)
- A unified framework for information-theoretic generalization bounds (NeurIPS 2023 · similarity 0.92)
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.90)
- Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective (ICML 2024 · similarity 0.90)
- Fantastic Generalization Measures are Nowhere to be Found (ICLR 2024 · similarity 0.89)
- Algorithmic Stability Unleashed: Generalization Bounds with Unbounded Losses (ICML 2024 · 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.