betaFeedback

WorksMathematics

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

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.

Introduction

As machine learning systems are used in increasingly consequential settings, the question is not only how to optimize a model, but also what kind of performance guarantee should generalize. Classical statistical learning theory is organized around a simple template: each example incurs a fixed pointwise loss, and performance is measured by averaging this loss over the data distribution. Algorithm-dependent information-theoretic (IT) generalization bounds provide a complementary view of this template: MI [41], CMI [34], eCMI [21, 39], and prediction-based fCMI [19] relate generalization to how much the learned hypothesis, prediction, or loss reveals about the selected training sample. Because these bounds depend on the learning algorithm rather than only on a uniform hypothesis-class complexity, they can capture stability and implicit regularization; recent supersample refinements further sharpen this picture [39].

Many modern evaluation criteria, however, are not averages of fixed per-example losses. In reliable prediction and uncertainty quantification, multicalibration asks whether predictive probabilities remain meaningful across many subpopulations and score regions, not only on average [20, 14, 3]. In risk-sensitive learning, optimized-certainty-equivalent risks and conditional value-at-risk (CVaR) emphasize tail behavior rather than mean loss alone [2, 32, 23]. In robust learning, distributionally robust optimization (DRO) reevaluates performance under adversarial reweightings of the empirical loss distribution [33, 1, 6]; related transport-based criteria depend on alignments of empirical distributions [4]. These criteria are central when average loss can look benign while subgroup, tail, or worst-case failures remain severe.

What makes these objectives hard for existing IT analysis is not merely that they are non-pointwise. Recent work has already extended IT generalization beyond pointwise averages to fixed higher-order losses, including pairwise and triplet objectives [5]; however, our setting is different. Here the empirical metric is set-input: it depends on the entire batch of predictions and labels. It is optimization-valued: after seeing the batch, the metric selects an auxiliary object by solving a downstream optimization problem, such as the most violated subgroup witness, a tail threshold, or an adversarial reweighting. Because this auxiliary choice is data-dependent, a one-point replacement can change not only one observation but also the optimizer that defines the metric. For multicalibration, the worst witness on the training batch need not coincide with the worst witness on the validation batch; for CVaR, the optimizing threshold can shift in the same way. This helps explain why existing analyses are family-specific, e.g., for ECE [11], OCE/CVaR [23], or robust optimization [1].

We develop a unified information-theoretic analysis of set-input optimization-valued objectives in the supersample setting (§ 3.1). From each pair, a selector independently chooses one observation for training with equal probability, while the other is held out for validation. The central object is the selector gap (Eq. (6)), defined as the optimized value on the validation sample minus that on the training sample. This gap directly compares the values obtained after re-optimizing the auxiliary variable separately on the two samples, without fixing a common optimizer. Complementing the selector vector exchanges the two samples and reverses the sign of the gap; thus, the selector gap is antisymmetric. This antisymmetry lets us control the expected optimized validation–training gap through two quantities (Theorem 1): the fCMI between the learned supersample prediction table and the selector vector, which measures algorithmic dependence on the selector vector, and an objective-dependent sub-Gaussian parameter for the selector gap under the uniform selector law, which reflects the stability or geometry of the optimized objective. To obtain a complete population–training bound, we combine this result with an objective-specific fixed-predictor bound on the population–validation gap. The validation–training bound accounts for auxiliary optimization without an explicit entropy, cardinality, Rademacher, or covering-number term for the auxiliary class.

We give two sufficient conditions for the selector gap to be sub-Gaussian under the uniform selector law. The first is a one-point stability certificate: if the objective changes little when one example is replaced, then the selector gap concentrates by bounded differences; this route also yields a single-index refinement that decomposes the validation–training gap into one-point replacement increments and one CMI term per index (§ 3.2; Theorem 2). The second is a convex L2L_2-Lipschitz certificate, which captures sharper geometry when the objective is a convex function of a coordinatewise score vector (§ 3.3). Together, these certificates give concrete bounds for multicalibration, CVaR, and Cressie–Read DRO, including the L2L_2-geometric improvement for DRO (Corollaries 1–6). We also give population–training decompositions using fixed-predictor MC, CVaR, and DRO comparisons (§ 3.4) and experiments illustrating computable local-information diagnostics (§ 5).

Preliminaries

We fix notation used throughout. We use uppercase letters for random variables (RVs) and lowercase letters for their realizations. For a∈Na \in\mathbb{N}, write [a]:={1,…,a}[a] := \{1,\ldots,a\}. Let X\mathcal{X} be the input space, Y\mathcal{Y} the label space, and Z=X×Y\mathcal{Z} = \mathcal{X} \times\mathcal{Y}. Let V\mathcal{V} be the prediction space, and let D\mathcal{D} be an unknown distribution on Z\mathcal{Z}. We denote mutual information (MI) and CMI by I(⋅;⋅)I(\cdot;\cdot) and I(⋅;⋅∣⋅)I(\cdot;\cdot\mid\cdot), respectively. All expectations are over the random variables under discussion.

IT generalization bound based on eCMI

For ordinary pointwise losses, we use the standard supersample construction [34, 21]. Let Z~∈Zn×2\widetilde{Z} \in\mathcal{Z}^{n \times2} be an array of 2n2n i.i.d. draws from D\mathcal{D}, with entries Z~i,j=(X~i,j,Y~i,j)\widetilde{Z}_{i,j} = (\widetilde{X}_{i,j}, \widetilde{Y}_{i,j}) (i∈[n]i \in[n], j∈{0,1}j \in\{0,1\}). We denote the ii-th row by Z~i=(Z~i,0,Z~i,1)\widetilde{Z}_i = (\widetilde{Z}_{i,0}, \widetilde{Z}_{i,1}). Let the selector vector U=(U1,…,Un)∼Unif⁡({0,1}n)U = (U_1,\ldots,U_n) \sim\operatorname{Unif}(\{0,1\}^n) be independent of Z~\widetilde{Z}. Each component UiU_i is called a selector; write U‾i=1−Ui\overline{U}_i = 1 - U_i. For a deterministic selector vector u∈{0,1}nu \in\{0,1\}^n, we similarly write u‾i=1−ui\overline{u}_i = 1 - u_i. The selected sample Z~U:=(Z~i,Ui)i=1n\widetilde{Z}_U := (\widetilde{Z}_{i,U_i})_{i=1}^n is used as the training sample, while the complementary sample Z~U‾:=(Z~i,U‾i)i=1n\widetilde{Z}_{\overline{U}} := (\widetilde{Z}_{i,\overline{U}_i})_{i=1}^n is used as the held-out validation (or test) sample. Write S:=Z~US := \widetilde{Z}_U, S′:=Z~U‾S' := \widetilde{Z}_{\overline{U}}. We use nn-subscripts for batch size. A learning algorithm receives SS and independent randomness R∈RR \in\mathcal{R}, outputs W=A(S,R)W = A(S,R), and returns a predictor fW∈F:X→Vf_W \in\mathcal{F}:\mathcal{X}\to\mathcal{V}. We evaluate fWf_W on all 2n2n supersample inputs and write fW(X~):=(fW(X~i,j))i∈[n], j∈{0,1}∈Vn×2f_W(\widetilde{X}):=(f_W(\widetilde{X}_{i,j}))_{i\in[n],\,j\in\{0,1\}}\in\mathcal{V}^{n\times2}.

For comparison with the standard setting, let ℓ:V×Y→[0,1]\ell:\mathcal{V}\times\mathcal{Y}\to[0,1] be a bounded pointwise loss function. For a predictor ff and a sample s=((xi,yi))i=1ns=((x_i,y_i))_{i=1}^n, define the population risk L(f):=EZ∼Dℓ(f(X),Y)L(f):=\mathbb{E}_{Z\sim D}\ell(f(X),Y) and the empirical risk L^(f;s):=n−1∑i=1nℓ(f(xi),yi)\widehat{L}(f;s):=n^{-1}\sum_{i=1}^n\ell(f(x_i),y_i). When no confusion is possible, write the loss value ℓ(f,z)\ell(f,z) as shorthand for ℓ(f(x),y)\ell(f(x),y) with z=(x,y)z=(x,y), and write the ii-th supersample loss row as ℓ(fW,Z~i):=(ℓ(fW,Z~i,0),ℓ(fW,Z~i,1))\ell(f_W,\widetilde{Z}_i):=(\ell(f_W,\widetilde{Z}_{i,0}),\ell(f_W,\widetilde{Z}_{i,1})). The standard evaluated CMI (eCMI) and functional CMI (fCMI) generalization bound [19, 21] gives

∣E[L^(fW;S′)−L^(fW;S)]∣≤1n∑i=1n2I(ℓ(fW,Z~i);Ui∣Z~)≤2nI(fW(X~);U∣Z~).(1)\left|\mathbb{E}\left[\widehat{L}(f_W;S')-\widehat{L}(f_W;S)\right]\right| \leq\frac{1}{n}\sum_{i=1}^{n}\sqrt{2I(\ell(f_W,\widetilde{Z}_i);U_i\mid\widetilde{Z})} \leq\sqrt{\frac{2}{n}I(f_W(\widetilde{X});U\mid\widetilde{Z})}. \tag*{(1)}

After fixing fWf_W, flipping one selector swaps only the corresponding training and validation loss values. The next subsection considers batch-level objectives without this row-wise structure.

Motivating examples beyond ordinary losses

Beyond the pointwise empirical risks of § 2.1, we consider three criteria. They become important precisely when mean performance is not sufficiently expressive: multicalibration [20, 14, 3] captures subgroup and score-conditional reliability, CVaR [32, 23] captures tail-sensitive risk, and distributionally robust optimization (DRO) [30, 33] captures worst-case performance under adversarial reweighting. Throughout, S=((Xi,Yi))i=1n∈ZnS=((X_i,Y_i))_{i=1}^n\in\mathcal{Z}^n and Z=(X,Y)∼DZ=(X,Y)\sim D.

References

  1. [1]Yang An and Rui Gao. Generalization bounds for (wasserstein) robust optimization. Advances in Neural Information Processing Systems, 34:10382–10392, 2021.
  2. [2]Aharon Ben-Tal and Marc Teboulle. An old-new concept of convex risk measures: The optimized certainty equivalent. Mathematical Finance, 17(3):449–476, 2007.DOI
  3. [3]J. Błasiok, P. Gopalan, L. Hu, and P. Nakkiran. A unifying theory of distance from calibration. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, page 1727–1740, 2023.arxiv.org/abs/2211.16886
  4. [4]Marco Cuturi. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, 26, 2013.arxiv.org/abs/1306.0895
  5. [5]Yuxin Dong, Tieliang Gong, Hong Chen, Zhongjiang He, Mengxiang Li, Shuangyong Song, and Chen Li. Towards generalization beyond pointwise learning: A unified information-theoretic perspective. In Ruslan Salakhutdinov, Zico Kolter, Katherine Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors, Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 11311–11345. PMLR, 21–27 Jul 2024.
  6. [6]John C. Duchi and Hongseok Namkoong. Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3):1378 – 1406, 2021. doi: 10.1214/20-AOS2004.DOI
  7. [7]Adam N Elmach et al. and Paul Grigas. Smart “predict, then optimize”. Management Science, 68(1):9–26, 2022.arxiv.org/abs/1710.08005
  8. [8]Dean P Foster and Sergiu Hart. Smooth calibration, leaky forecasts, finite recall, and nash dynamics. Games and Economic Behavior, 109:271–293, 2018.DOI
  9. [9]Dean P Foster and Rakesh V Vohra. Asymptotic calibration. Biometrika, 85(2):379–390, 1998.DOI
  10. [10]Futoshi Futami and Masahiro Fujisawa. Time-Independent Information-Theoretic Generalization Bounds for SGLD. In Advances in Neural Information Processing Systems, volume 36, pages 8173–8185. Curran Associates, Inc., 2023.arxiv.org/abs/2311.01046
  11. [11]Futoshi Futami and Masahiro Fujisawa. Information-theoretic generalization analysis for expected calibration error. In Advances in Neural Information Processing Systems, volume 37, pages 84246–84297. Curran Associates, Inc., 2024.arxiv.org/abs/2405.15709
  12. [12]Futoshi Futami and Atsushi Nitanda. Smooth calibration error: Uniform convergence and functional gradient analysis. In The Fourteenth International Conference on Learning Representations, 2026.
  13. [13]Ira Globus-Harris, Declan Harrison, Michael Kearns, Aaron Roth, and Jessica Sorrell. Multicalibration as boosting for regression. In Andreas Krause, Emma Brunskill, K Yunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11459–11492. PMLR, 23–29 Jul 2023.arxiv.org/abs/2301.13767
  14. [14]Parikshit Gopalan, Michael P Kim, Mihir A Singhal, and Shengjia Zhao. Low-degree multicalibration. In Po-Ling Loh and Maxim Raginsky, editors, Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pages 3193–3234. PMLR, 02–05 Jul 2022.arxiv.org/abs/2203.01255
  15. [15]Peter Grunwald, Thomas Steinke, and Lydia Zakynthinou. Pac-bayes, mac-bayes and conditional mutual information: Fast rate bounds that handle general vc classes. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 2217–2247. PMLR, 15–19 Aug 2021.arxiv.org/abs/2106.09683
  16. [16]Nika Haghtalab, Michael Jordan, and Eric Zhao. A unifying perspective on multi-calibration: Game dynamics for multi-objective learning. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural Information Processing Systems, volume 36, pages 72464–72506. Curran Associates, Inc., 2023.arxiv.org/abs/2302.10863
  17. [17]Dutch Hansen, Siddartha Devic, Preetum Nakkiran, and Vatsal Sharan. When is multicalibration post-processing necessary? Advances in Neural Information Processing Systems, 37:38383–38455, 2024.arxiv.org/abs/2406.06487
  18. [18]Jason Hartline, Yifan Wu, and Yunran Yang. Smooth Calibration and Decision Making. In Mark Bun, editor, 6th Symposium on Foundations of Responsible Computing (FORC 2025), volume 329 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1–16:26, Dagstuhl, Germany, 2025. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-367-6. doi: 10.4230/LIPIcs.FORC.2025.16.DOI
  19. [19]H. Harutyunyan, M. Raginsky, G. Ver Steeg, and A. Galstyan. Information-theoretic generalization bounds for black-box learning algorithms. In Advances in Neural Information Processing Systems, pages 24670–24682, 2021.arxiv.org/abs/2110.01584
  20. [20]Ursula Hebert-Johnson, Michael Kim, Omer Reingold, and Guy Rothblum. Multicalibration: Calibration for the (Computationally-identifiable) masses. In Jennifer Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 1939–1948. PMLR, 10–15 Jul 2018.
  21. [21]F. Hellström and G. Durisi. A new family of generalization bounds using samplewise evaluated CMI. In Advances in Neural Information Processing Systems, pages 20648–20660, 2022.arxiv.org/abs/2210.06422
  22. [22]Tomoharu Iwata and Futoshi Futami. Data-driven projection generation for efficiently solving heterogeneous quadratic programming problems. arXiv preprint arXiv:2510.26061, 2025.arxiv.org/abs/2510.26061
  23. [23]Jaeho Lee, Sejun Park, and Jinwoo Shin. Learning bounds for risk-sensitive learning. Advances in Neural Information Processing Systems, 33:13867–13879, 2020.arxiv.org/abs/2006.08138
  24. [24]Jayanta Mandi, Víctor Bucarey, Maxime Mulamba Ke Tchomba, and Tias Guns. Decision-focused learning: Through the lens of learning to rank. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvari, Gang Niu, and Sivan Sabato, editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 14935–14947. PMLR, 17–23 Jul 2022.arxiv.org/abs/2112.03609
  25. [25]P. Massart. The Tight Constant in the Dvoretzky-Kiefer-Wolfowitz Inequality. The Annals of Probability, 18(3):1269 – 1283, 1990. doi: 10.1214/aop/1176990746.DOI
  26. [26]Zakaria Mhammedi, Benjamin Guedj, and Robert C Williamson. Pac-bayesian bound for the conditional value at risk. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 17919–17930. Curran Associates, Inc., 2020.arxiv.org/abs/2006.14763
  27. [27]Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2nd edition, 2018. ISBN 0262039400.
  28. [28]Gergely Neu, Gintare Karolina Dziugaite, Mahdi Haghifam, and Daniel M. Roy. Information-theoretic generalization bounds for stochastic gradient descent. In Mikhail Belkin and Samory Kpotufe, editors, Proceedings of Thirty Fourth Conference on Learning Theory, volume 134 of Proceedings of Machine Learning Research, pages 3526–3545. PMLR, 15–19 Aug 2021.arxiv.org/abs/2102.00931
  29. [29]Georgy Noarov and Aaron Roth. The statistical scope of multicalibration. In Andreas Krause, Emma Brunskill, Kyungyhun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 26283–26310. PMLR, 23–29 Jul 2023.
  30. [30]Hamed Rahimian and Sanjay Mehrotra. Distributionally robust optimization: A review. arXiv preprint arXiv:1908.05659, 2019.DOI
  31. [31]R Tyrrell Rockafellar and Stanislav Uryasev. Conditional value-at-risk for general loss distributions. Journal of banking & finance, 26(7):1443–1471, 2002.
  32. [32]R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk. Journal of risk, 2:21–42, 2000.
  33. [33]Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:1911.08731, 2019.arxiv.org/abs/1911.08731
  34. [34]T. Steinke and L. Zakynthinou. Reasoning about generalization via conditional mutual information. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Thirty Third Conference on Learning Theory, volume 125 of Proceedings of Machine Learning Research, pages 3437–3452. PMLR, 09–12 Jul 2020.arxiv.org/abs/2001.09122
  35. [35]Michael Sucker, Jalal Fadili, and Peter Ochs. Learning-to-optimize with pac-bayesian guarantees: Theoretical considerations and practical implementation. Journal of Machine Learning Research, 26(211):1–53, 2025.arxiv.org/abs/2404.03290
  36. [36]Vega. flights-200k.json. https://vega.github.io/vega-datasets/datasets/flights_200k_json/. vega-datasets, version 3.2.1. Data source: U.S. Bureau of Transportation Statistics.
  37. [37]M. J. Wainwright. High-Dimensional Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
  38. [38]Kaiwen Wang, Dawen Liang, Nathan Kallus, and Wen Sun. A reductions approach to risk-sensitive reinforcement learning with optimized certainty equivalents. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste-Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research, pages 63636–63661. PMLR, 13–19 Jul 2025.arxiv.org/abs/2403.06323
  39. [39]Z. Wang and Y. Mao. Tighter information-theoretic generalization bounds from supersamples. In Proceedings of the 40th International Conference on Machine Learning, volume 202, pages 36111–36137, 2023.arxiv.org/abs/2302.02432
  40. [40]Bryan Wilder, Bistra Dilkina, and Milind Tambe. Melding the data-decisions pipeline: decision-focused learning for combinatorial optimization. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’19/IAAI’19/EAAI’19. AAAI Press, 2019. ISBN 978-1-57735-809-1. doi: 10.1609/aaai.v33i01.33011658.DOI
  41. [41]A. Xu and M. Raginsky. Information-theoretic analysis of generalization capability of learning algorithms. In Advances in Neural Information Processing Systems, volume 30, pages 2524–2533, 2017.arxiv.org/abs/1705.07809

Paper details

vlnc:W_4v2ngjwc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 5

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents