Research map / Learning theory and algorithms / Kernels and regression theory
Towards Generalization beyond Pointwise Learning: A Unified Information-theoretic Perspective
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.
Extends information-theoretic generalization bounds (input-output MI, CMI, e-CMI, fast-rate) beyond pointwise learning to pairwise, triplet, quadruplet and higher-order losses, with 2-dimensional prediction-based MI terms and gradient-covariance bounds for SGLD.
Problem
Information-theoretic generalization analysis has been confined to pointwise learning; extending it to non-pointwise losses (e.g., contrastive, triplet, N-pair) is hard due to non-i.i.d. loss terms and exponential dimensionality of prediction-based MI quantities.
Approach
A unified framework over m-sample losses via group-wise reduction of hypothesis-based MI bounds, and a decomposition of supersample variables into independent lower-dimensional pieces so prediction-based bounds use only 2-dimensional loss-difference MI terms regardless of m.
Key results
- Fast-rate bound (Theorem 4.6) gives the tightest estimates across synthetic and real-world settings for cross-entropy, contrastive, triplet and N-pair losses.
- Prediction-based bounds use only 2-dimensional MI quantities regardless of m, strictly tighter than the e-CMI bound (Theorem 4.1).
- In the CLIP fine-tuning experiment, the generalization gap increases with n, attributed to false negatives in self-supervised labels; the bounds still track this trend.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the fast-rate bound (Theorem 4.6) instead of the square-root or binary KL bounds | generalization-bound estimation · Synthetic Gaussian datasets: cross-entropy, contrastive, triplet, and N-pair learning | bound tightness | Helped |
| use the fast-rate bound (Theorem 4.6) instead of the square-root or binary KL bounds | generalization-bound estimation · MNIST, CIFAR-10, and Flickr30k | bound tightness | Helped |
| increase the sample size | generalization bounds · Synthetic Gaussian datasets | bound value | Helped |
| increase the sample size | CLIP (ViT-B/32) fine-tuned on Flickr30k · Flickr30k | generalization gap | Hurt |
Surprising findings
- The generalization gap for CLIP fine-tuning on Flickr30k increases with sample size n, attributed to false negatives in self-supervised ground-truth labels.
Limitations
- Bounds for interpolating/fast-rate regimes require near-zero training risk and binary or bounded losses.
- Algorithm-based bounds are developed mainly for SGLD; SGD and adaptive methods are only sketched as extensions.
Experimental setup
Datasets: synthetic Gaussian (5-class) binarized MNIST (4 vs 9) CIFAR-10 Flickr30k
Benchmarks: synthetic Gaussian binarized MNIST CIFAR-10 Flickr30k
Metrics: generalization gap vs bound value
Baselines: square-root bound binary KL bound e-CMI bound
Builds on: Xu & Raginsky input-output MI bound Steinke & Zakynthinou supersample CMI Hellström & Durisi e-CMI Wang & Mao loss-difference bounds Dong et al. 2023 SGLD gradient covariance bound
Closest papers by meaning
- Information-theoretic generalization bounds for black-box learning algorithms (NeurIPS 2021 · similarity 0.91)
- Information-theoretic analysis of generalization capability of learning algorithms (NeurIPS 2017 · similarity 0.91)
- Exactly Tight Information-theoretic Generalization Bounds via Binary Jensen-Shannon Divergence (ICML 2025 · similarity 0.90)
- Certification-Enhanced Generalization Bounds (NeurIPS 2026 · similarity 0.89)
- Slicing Mutual Information Generalization Bounds for Neural Networks (ICML 2024 · similarity 0.88)
- Tighter CMI-Based Generalization Bounds via Stochastic Projection and Quantization (NeurIPS 2025 · similarity 0.88)
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.