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

Futoshi Futami, Masahiro FujisawaarXiv 2026 · arXiv

TL;DR

This paper introduces a unified information-theoretic framework to bound the generalization gap for complex, batch-level metrics like multicalibration, CVaR, and distributionally robust optimization (DRO). By factorizing generalization into algorithmic dependence (via conditional mutual information) and objective geometry (via sub-Gaussianity), the authors provide the first algorithm-dependent bounds for objectives that involve internal, post-hoc optimization.

What Problem Does This Paper Address?

Most classical learning theory is built on a simple "pointwise" assumption: your performance is just the average of individual losses across examples. However, modern machine learning often cares about more sophisticated criteria. For instance:

  • Multicalibration (MC): Does the model remain reliable across many overlapping subgroups?
  • Conditional Value-at-Risk (CVaR): How does the model perform on the "worst" 5% of cases?
  • Distributionally Robust Optimization (DRO): How does the model handle adversarial reweighting of the data?

These metrics are set-input (they depend on the entire batch at once) and optimization-valued (calculating them requires solving an internal sub-problem, like finding the most-violated subgroup). Standard information-theoretic (IT) tools break here because changing a single data point doesn't just change one loss value; it can shift the entire internal optimizer, making traditional row-wise analysis impossible.

Methods

The authors tackle this by formalizing these metrics as "set-input optimization-valued objectives" and analyzing them in a balanced supersample setting.

  1. The Selector Gap: They imagine a supersample of $2n$ points where a random "selector" vector $U$ determines which $n$ points go to training and which go to validation. They define a "selector gap"—the difference between the optimized metric on validation vs. training. Because this gap is antisymmetric (flipping $U$ just flips the sign), its expectation under a uniform selector is zero.
  2. Factorized Bounds: Using the Donsker-Varadhan variational inequality, they bound the expected gap using two components:
  3. fCMI (functional Conditional Mutual Information): Measures how much the model's predictions "leak" information about which points were chosen for training.
  4. $L_{\Gamma,n}$ (Sub-Gaussian Parameter): Captures the "stability" or "geometry" of the optimized objective.
  5. Certificates for Sub-Gaussianity: To make the bounds concrete, they provide two "certificates" to calculate $L_{\Gamma,n}$:
  6. One-point stability: Based on how much the objective changes when one example is replaced.
  7. Convex $L_2$-Lipschitzness: A sharper geometric approach for objectives that are convex functions of the score vector (like DRO).

Datasets

The authors evaluate their bounds using:

  • Flights200K: Used for experiments with linear logistic regression to show the bounds are computable and track the actual generalization gap.
  • CelebA: Used for large-scale image classification with a Vision Transformer (ViT) to test the framework on complex, high-dimensional models.

Key Insights and Ideas

  • Separation of Concerns: Generalization is shown to be a product of the learning algorithm's sensitivity (fCMI) and the objective's inherent geometry ($L_{\Gamma,n}$). This allows researchers to plug in different stability results for different metrics while using the same information-theoretic "engine."
  • No Explicit Complexity Penalty: Remarkably, the validation-training bound does not require an explicit entropy or Rademacher complexity term for the auxiliary optimization class (e.g., the set of all possible subgroups). The symmetry of the supersample construction effectively "cancels out" this complexity.
  • Geometry Beats Stability for DRO: For Distributionally Robust Optimization, the authors show that an $L_2$-geometric analysis provides much sharper rates than a simple $L_\infty$ stability analysis, recovering optimal plug-in rates while remaining algorithm-dependent.
Table 1: Upper bounds on LΓ,n under stability and convex L2-Lipschitz certificates.

Key Results

  • Unified Bounds: The paper provides concrete, unified bounds for MC, CVaR, and Cressie–Read DRO.
  • Optimal Rates: For DRO, the convex $L_2$ certificate recovers the known optimal rate of $n^{-1/(c^* \vee 2)}$, but adds the benefit of being algorithm-dependent (capturing things like implicit regularization).
  • Empirical Validation: In the Flights200K experiments, the bounds were conservative but tracked the generalization gap linearly on a log-log scale. For the ViT/CelebA experiments, the authors successfully used a "local-information proxy" based on nearest-neighbor MI estimation to diagnose generalization.

Limitations and Future Work

  • Optimization Error: The theory focuses on statistical generalization but does not analyze the optimization error of the "outer" learning problem (how well we actually minimize the training objective).
  • Estimation Challenges: For large models like ViT, estimating mutual information accurately is computationally expensive and prone to bias. The authors had to rely on "proxies" rather than strict bounds for these cases.
  • Future Directions: The authors suggest extending the work to include "fast-rate" refinements (similar to Bernstein-type bounds) and applying the framework to other batch-level criteria like optimal transport-based metrics.

Summary updated

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.
BibTeX
@misc{futami2026information,
  author = {Futoshi Futami and Masahiro Fujisawa},
  title = {{Information-Theoretic Generalization for Set-Input Optimization-Valued Objectives}},
  year = {2026},
  eprint = {2611.10362},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10362},
}
Figure