stat.MLNov 7, 2026

Information-Theoretic Generalization for Set-Input Optimization-Valued Objectives

Authors: Futoshi Futami, Masahiro Fujisawa

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

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Information-Theoretic Generalization Bounds for Sequential Decision Making

    May 12, 2026Futoshi Futami, Masahiro FujisawaInformation-Theoretic Generalization BoundsGeneralization Bounds

  2. Generalization Bounds via Vector-Valued LpL_p Correlation VαV_α

    Oct 21, 2026Mohammad Hossein Momeni Hamaneh, Mohammad Mahdi Mojahedian, Mohammad Hossein YassaeeGeneralization BoundsInformation-Theoretic Generalization Bounds