Information-Theoretic Generalization for Set-Input Optimization-Valued Objectives
Organizations: The University of Osaka · The University of Tokyo · RIKEN AIP · Toyota Motor Corporation
Abstract
Modern machine learning is increasingly evaluated using criteria such as multicalibration, CVaR, and Cressie-Read DRO, which target subgroup reliability, tail risk, and distributional robustness rather than averages of fixed per-example losses. Existing information-theoretic generalization bounds for pointwise losses do not directly apply, because these empirical criteria depend on the entire batch and involve a post-hoc auxiliary optimization over witnesses, thresholds, or reweightings. We formalize this structure as set-input optimization-valued objectives. In the balanced supersample setting, we bound the expected optimized validation-training gap in terms of an objective-dependent sub-Gaussian parameter and the square root of the prediction-based conditional mutual information (fCMI) between the learned supersample prediction table and the selector vector. Combining this with fixed-predictor population-validation comparisons yields unified algorithm-dependent generalization bounds. We verify sub-Gaussianity of the selector gap using stability and convex L2-Lipschitz certificates, obtaining concrete bounds for multicalibration, CVaR, and Cressie-Read DRO, with a stability-based single-index refinement.
Figures & tables
| Objective | Uniform stability (Assumption 2 ) | Convex -Lipschitz (Assumption 3 ) | Preferred |
|---|---|---|---|
| MC | Stability | ||
| CVaR | Best of two | ||
| CR DRO | Convex |
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| Objective | Existing | Ours |
|---|---|---|
| Binning ECE | [ 11 ] | |
| CVaR | [ 23 ] | |
| CR DRO | [ 6 ] |
Generalization Bounds
Generalization bounds quantify how training performance can differ from population or test performance as sample size and model complexity change.
See all 169 papers