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

May 12, 2026

Information-Theoretic Generalization Bounds for Sequential Decision Making

Information-theoretic generalization bounds based on the supersample construction are a central tool for algorithm-dependent generalization analysis in the batch i.i.d. setting. However, existing supersample conditional mutual information (CMI) bounds do not directly apply to sequential decision-making problems such as online learning, streaming active learning, and bandits, where data are revealed adaptively and the learner evolves along a causal trajectory. To address this limitation, we develop a sequential supersample framework that separates the learner filtration from a proof-side enlargement used for ghost-coordinate comparisons. Under a row-wise exchangeability assumption, the sequential generalization gap is controlled by sequential CMI, a sum of roundwise selector--loss information terms. We also establish a Bernstein-type refinement that yields faster rates under suitable variance conditions. The resulting bounds specialize to online learning, streaming active learning with importance weighting, and stochastic multi-armed bandits.
Oct 21, 2026

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

Understanding generalization of randomized learning algorithms remains a central challenge. Mutual-information and total-variation bounds provide complementary ways to quantify data--hypothesis dependence, but they can behave quite differently in high-dimensional regimes. We study a one-parameter family of dependence measures, the vector-valued LpL_p-norm correlation VαV_α, and derive generalization bounds whose dependence terms interpolate between total variation (TV) at α=1α=1 and variance and χ2χ^2 related behavior at α=2α=2. For α>2α>2, the Hölder-conjugate loss moment is below two, yielding heavy-tailed specializations that can remain finite even when the loss variance is infinite. A particularly interpretable specialization occurs at α=2α=2, where the bound can be expressed in terms of the variability of the algorithm's output density across datasets, ∫VarS[p(w∣S)] dw\int \sqrt{\mathrm{Var}_S[p(w\mid S)]}~ dw. We show that the entire VαV_α family is invariant under smooth bijective reparameterizations of the hypothesis space. We also introduce an adaptive density stability (ADS) condition that implies explicit control of V2V_2, and we verify it for Gibbs-type posteriors under bounded losses (yielding rates that depend on the inverse temperature and sample size). To address scaling, we extend the framework to a conditional formulation using supersamples, analogous in spirit to conditional mutual information (CMI), and discuss evaluations in the output space as a practical surrogate for estimating dependence. Simulations on Bayesian linear regression illustrate how tuning αα can change the tightness of the resulting bounds across regimes. Additional supersample experiments on noisy MNIST and on a pretrained ResNet-50 for CIFAR-10 show similar behavior of the projected loss-space bounds beyond the original clean-MNIST setting.
Oct 6, 2026

An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information

Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power r≥2r\ge2, on product distributions over a scaled sign cube in dimension at least linear in nn, every proper learner with expected excess risk at most ε\varepsilon on these distributions at the optimal sample size n≍ε−2+2/rn\asymp\varepsilon^{-2+2/r} has worst-case ld-CMI of order nn bits, and Θ(n/(1+(τ/ε)2))Θ(n/(1+(τ/\varepsilon)^2)) bits under Gaussian noise of standard deviation ττ on the loss differences. The same holds without a regularizer, at n≍ε−2n\asymp\varepsilon^{-2}. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is O(n−1/2)O(n^{-1/2}). We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.