Pith. sign in

REVIEW 2 major objections 5 minor 90 references

Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities

T0 review · 2 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper establishes that a unified data-processing-inequality argument generates change-of-measure bounds — including P(E) ≤ γQ(E) + Eγ(P∥Q), which strictly improves the strong-converse lemma — and that these bounds yield tighter high-pr

desk verdict DPI framework is sound and the new bounds are real, but Eq. (4) defines Eγ inconsistently and must be corrected before acceptance. read the letter →

arxiv 2602.07999 v4 pith:5RZVF2NG submitted 2026-02-08 cs.IT cs.LGmath.IT

Yanxiao Liu , Yijun Fan , Deniz Gündüz This is my paper · ORCID
classification cs.ITcs.LGmath.IT MSC 94A1760E1568T05
keywords changeofmeasureinequalitiesf-divergencesdataprocessinginequalitygeneralizationboundsPAC-BayesdifferentialprivacyEγ-divergencemaximalleakage
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper is trying to establish a single, simple mechanism — applying the data-processing inequality for f-divergences to the indicator channel of an event — that produces a whole family of 'change of measure' inequalities, which convert divergences between two probability measures into upper bounds on event probabilities. The headline inequality, P(E) ≤ γQ(E) + Eγ(P∥Q), improves on the classical strong-converse lemma because the Eγ-divergence captures not only that the density ratio exceeds γ but by how much. If correct, this means that numerous previously scattered generalization bounds — in terms of KL, χ², Hellinger, power-β, Rényi divergences, α-mutual information, and maximal leakage — can be derived from one elementary source and are usually tighter than the best-known results. A sympathetic reader would care because the bounds are directly actionable: they tighten high-probability guarantees on the gap between training and test loss for stochastic learning algorithms, sharpen PAC-Bayesian certificates, and give sample-size-explicit generalization guarantees for approximate differential privacy.

What carries the argument

The workhorse is the f-divergence data-processing inequality (DPI) applied to the indicator test channel T=1_E: D_f(P∥Q) ≥ D_f(Ber(P(E))∥Ber(Q(E))). This reduces the search for change-of-measure inequalities to computing and inverting a two-point f-divergence. The second key object is the Eγ-divergence, Eγ(P∥Q)=sup_E |P(E)−γQ(E)|, which is the unique information measure among those considered that has an explicit, finite upper bound under approximate differential privacy, and whose variational form drives the improvement over the strong converse lemma. A third tool, a generalized Hölder inequality in Orlicz spaces (Theorem 3), extends the bounds to settings where only moments of the density

What would settle it

Pick two distributions P and Q on a finite alphabet, compute both sides of Proposition 1 for every subset E and a range of γ; if any E,γ satisfy P(E) > γQ(E)+Eγ(P∥Q), the central inequality is false. For the tightness claims, evaluate the power-β bound (20) and the comparison bound from the earlier literature at small Q(E) (e.g., q=10^{-6}) for several β; if (20) ever exceeds the comparison bound in that regime, the claimed improvement is refuted.

Watch

Extended reading notes

Core claim

The central discovery is that for any event E and any f-divergence, the data-processing inequality applied to the deterministic indicator channel 1_E gives the scalar lower bound D_f(P∥Q) ≥ q f(p/q)+(1−q)f((1−p)/(1−q)), with p=P(E), q=Q(E); inverting this bound yields explicit inequalities of the form P(E) ≤ ξ(Q(E), D_f(P∥Q)). For the f-divergence f(t)=[t−γ]₊ (the Eγ-divergence), this yields P(E) ≤ γQ(E)+Eγ(P∥Q), which strictly improves the strong converse lemma P(E) ≤ γQ(E)+P(dP/dQ>γ), since Eγ(P∥Q) is always no larger than the tail probability. The same pipeline produces inequalities in terms of χ²-divergence, KL divergence, squared Hellinger distance, power-β divergence, reverse divergenc

Load-bearing premise

Every generalization bound in the paper (Theorems 4–5, Corollaries 6–7) assumes P_SW ≪ P_S P_W, so the density ratio dP_SW/d(P_S P_W) must exist; for deterministic algorithms or when the hypothesis space has lower dimension than the data, this absolute continuity fails and the bounds become vacuous or undefined.

Editorial extensions

If this is right

  • For stochastic algorithms with σ-sub-Gaussian losses, the new change-of-measure inequalities yield high-probability generalization bounds (Theorem 5) that are tighter than existing bounds in terms of the same divergence, except in one specified regime.
  • The Eγ-based inequality recovers the maximal leakage generalization bound exactly with a much shorter proof, and Theorem 4 recovers the α-mutual-information bound, unifying these results under one framework.
  • In the PAC-Bayesian setting, the power-β inequality gives bounds of order σ√((1/n)log(1/δ)·log(Hβ^{1/β})), improving the previous order-of-growth results.
  • For the conditional-mutual-information (CMI) framework, the Orlicz-space inequality yields new bounds on the ghost-sample generalization gap.
  • For (ε,δ)-differentially private algorithms, the paper derives a generalization bound of the form 2exp(c₂(ε²n+n√(δ/ε)) − nη²/(2σ²)) + e^{−ε²n}+c₁n√(δ/ε), giving explicit sample-size dependence.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The indicator channel T=1_E is only one choice; the same DPI machinery with other test channels may recover chaining or rate-distortion based bounds, and the paper's own conjectures point in that direction.
  • The Eγ-divergence's unique role under approximate DP suggests a testable strengthening: if the same bounds are plugged into the standard max-information transfer theorem, the resulting generalization guarantee for (ε,δ)-DP may be improvable to match known optimal private-learning sample complexities.
  • The absolute-continuity assumption is the real bottleneck for applications: extending the arguments to singular pairs (e.g., via conditional distributions or limiting density ratios) would make the bounds applicable to deterministic algorithms and under-parameterized hypotheses.
  • The improvement of Eγ over the strong-converse lemma — counting 'how far above γ' rather than just 'whether above γ' — may sharpen other large-deviation and hypothesis-testing arguments that use the strong converse as a black box.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper proposes a unified method for deriving change-of-measure inequalities of the form P(E) ≤ ξ(Q(E), dP/dQ) by applying the data-processing inequality (DPI) to the indicator kernel T = 1_E. The main theoretical contributions are Proposition 1 (an Eγ-based inequality claimed to improve the strong converse lemma), Theorem 2 (inequalities in terms of χ², KL, power-β, Hellinger divergences and their relaxations), and Theorems 3–4 (Orlicz-norm generalizations). These are applied to high-probability generalization bounds, PAC-Bayes bounds, CMI bounds, and approximate differential privacy, while also recovering several known results such as maximal-leakage bounds with simplified proofs. The appendices contain detailed derivations and comparisons with prior work.

Significance. If corrected, the DPI framework is genuinely useful: it gives a single elementary source for several known and new bounds, and the recovery of maximal-leakage and α-mutual-information bounds from Proposition 1 is elegant. The proofs in the appendices are mostly self-contained, and the comparisons with [15] and [3] are concrete. The novelty and breadth of applications are valuable. However, the current definitional error in Eq. (4) makes the flagship Proposition 1 internally inconsistent as printed, and the missing proof of Proposition 12 leaves the DP application unverified. With a local fix to the Eγ definition and a supplied proof of Proposition 12, the paper would make a solid contribution.

major comments (2)
  1. [Eq. (4) / Proposition 1] The definition Eγ(P∥Q) := sup_E |P(E)−γQ(E)| is not equal to ∫[dP/dQ−γ]_+ dQ for γ>1. Example: X={0,1}, P=δ0, Q=(δ0+δ1)/2, γ=2. The integral is 0, while sup_E |P(E)−2Q(E)| = 1 (attained at E={1}). The printed Eγ is therefore not the f-divergence with generator [t−γ]_+, so the DPI step in the proof of Proposition 1 is invalid as written. Under the literal definition, the claimed strict improvement over the strong converse lemma (13) fails: for E={0}, Prop. 1 yields 2 while (13) yields 1. This error propagates to Corollary 6, Lemma 11, and the DP application in Section V-E. Please redefine Eγ as sup_E(P(E)−γQ(E)) = ∫(dP/dQ−γ)_+ dQ and update Eq. (4); with that correction the results hold.
  2. [Section V-E, Proposition 12] Proposition 12 is stated without proof or derivation; the text only says it follows by combining Lemma 11 and [12, Theorem III.1]. Since the constants c1,c2 and the exact form of τ and k are not specified, the subsequent DP generalization bound rests on an unverified assertion. Please provide a self-contained proof or state and prove the exact corollary of [12] being used.
minor comments (5)
  1. [Appendix L, Corollary 19] The displayed bound is (2σ²/n)(2√I + 2/e + √π), but the proof concludes 2σ/√n (2√(I+2/e) + √π). The stated dependence on n is incorrect and inconsistent with the proof; please fix the statement.
  2. [Section V-E] The assumption P_SW ≪ P_SP_W is used throughout the generalization bounds but is not discussed. It fails for deterministic algorithms or when the hypothesis space has lower dimension than the data; a sentence on this limitation would help set expectations.
  3. [Theorem 2, Eq. (19)] The parameter M is defined after its use, and the sentence 'where M≤1/P(E)−1 in (19)' is confusing. Please clarify that M is a constant such that 1−P(E) ≥ M P(E), with the explicit choice given in Appendix C-F.
  4. [Theorem 5, Eq. (25)] The minimization in (25) is over several bounds, but γ is fixed in the theorem statement. If γ is meant to be a free parameter of the first term, say so explicitly and include it in the optimization.
  5. [General] Typos: 'Apendix K', 'for every very measurable set', 'Eγ-divergence underlies otherf-divergences'.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: DPI-based derivation is self-contained; only self-citation is non-load-bearing related work.

full rationale

The derivation chain is self-contained. Section IV's change-of-measure inequalities all start from the DPI identity (8) for f-divergences and then instantiate f (or use Young-Fenchel/Orlicz relaxations); the target event probability P(E) is not used as an input to define any of the information measures, and no parameter is fitted to data. Proposition 1 follows from the DPI lower bound Eγ(P∥Q) ≥ p−γq (with Eγ intended as the hockey-stick divergence); the strong converse lemma (13) is compared to, not assumed by, the result. Theorem 2 inequalities are explicit inversions of the same Bernoulli DPI expression, and the "recovery" statements (e.g., Corollary 6 recovering [3, Cor. 3]) use only known maximal-leakage identities, so they are sanity checks rather than premises. The sole author-overlapping citation ([50], used in the related-work survey of typicality-based DP bounds) is not load-bearing. The manuscript's Eq. (4) contains an apparent inconsistency (absolute-value definition vs. the hockey-stick integral used in proofs), but this is a mathematical correctness issue, not a circular reduction; with the intended hockey-stick definition the inequality is a direct consequence of the definition, and the paper does not secretly fit or assume its conclusions.

Assumptions & free parameters 5 free parameters · 8 assumptions · 0 invented entities

The central results rely on standard information-theoretic axioms and domain assumptions. The free parameters are optimization knobs, not fitted constants. No new physical or mathematical entities are introduced.

free parameters (5)
  • γ (threshold in E-gamma) = user-selected; e.g., γ = M(w) in Cor. 6
    Free parameter in Proposition 1 and Theorem 5, optimized or chosen to simplify bounds.
  • c (KL bound parameter) = optimized, e.g., c = log(1/Q(E)) in Eq. (37)
    Introduced in Eq. (15) via Fenchel relaxation; the bound holds for all c > 0.
  • β (power divergence order) = user-selected > 1
    Order of the power divergence in Eq. (17); affects the strength of the bound.
  • u0 (auxiliary in Eq. 20) = min(1, (1+(β−1)Hβ)^(1/β) q^(β−1)/β)
    Defined in terms of β and Hβ to relax (17) in the small-Q(E) regime.
  • M (auxiliary in Eq. 19) = Qmax^{(1-β)/β} ((β−1)Hβ + 1)^{−1/β} − 1
    Chosen to make the bound valid when P(E) is assumed small; paper notes (20) is usually better.
assumptions (8)
  • standard math Data processing inequality for f-divergences
    Central tool, stated in Section IV, Eq. (8).
  • standard math Radon-Nikodym theorem / absolute continuity P≪Q
    Required to define dP/dQ and all f-divergences; stated in Notation and used throughout.
  • standard math Young-Fenchel inequality
    Used in Eq. (9)-(11) to derive the general inequality (10).
  • standard math Hölder's inequality / Orlicz norm duality
    Used in Theorem 3 and Appendix E, citing [88].
  • domain assumption Loss is σ-sub-Gaussian
    Enables Hoeffding's bound Q(E) ≤ 2 exp(−nη²/(2σ²)) in Section V-A and Theorem 5.
  • domain assumption P_SW ≪ P_S P_W
    Stated in Theorem 4 and Corollaries 6-7; needed to define the change-of-measure ratios in generalization applications.
  • domain assumption Loss bounded on [a,b] for CMI bounds
    Section V-D assumes bounded loss to get sub-Gaussianity of dgen via Hoeffding's lemma.
  • domain assumption Dataset drawn i.i.d. from product distribution for DP result
    Section V-E adopts the assumption of [12, Thm III.1] to connect Eγ with approximate max-information.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities." pith.science (2026). https://pith.science/paper/5RZVF2NG

@misc{pith2026260207999,
  author       = {Pith},
  title        = {Pith review of: Tighter Information-Theoretic Generalization Bounds via a Novel Class of Change of Measure Inequalities},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/5RZVF2NG}},
  note         = {Machine review of arXiv:2602.07999}
}
abstract

Change of measure inequalities translate divergences between probability measures into explicit bounds on event probabilities, and play an important role in deriving probabilistic guarantees in learning theory, information theory, and statistics. We propose novel change of measure inequalities via a unified framework based on the data processing inequality, which is surprisingly elementary yet powerful enough to yield novel, tighter inequalities. We provide change of measure inequalities in terms of a broad family of information measures, including $f$-divergences (with Kullback-Leibler divergence and $\chi^2$-divergence as special cases), R\'enyi divergence, and $\alpha$-mutual information (with maximal leakage as a special case). We apply these results to generalization error analysis, PAC-Bayesian theory, differential privacy, and data memorization, obtaining stronger guarantees while recovering best-known results through simplified analyses.

Figures

Figures reproduced from arXiv: 2602.07999 by the authors.

Figure 1
Figure 1. Comparison between Corollary 19 and [21, Corollary 1]. [PITH_FULL_IMAGE:figures/full_fig_p039_1.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

90 extracted references · 7 linked inside Pith

  1. [15]

    On change of measure inequalities forf-divergences,

    A. Picard-Weibel and B. Guedj, “On change of measure inequalities forf-divergences,”arXiv preprint arXiv:2202.05568, 2022

    arXiv 2022

  2. [3]

    Generalization error bounds via Rényi-,f-divergences and maximal leakage,

    A. R. Esposito, M. Gastpar, and I. Issa, “Generalization error bounds via Rényi-,f-divergences and maximal leakage,”IEEE Transactions on Information Theory, vol. 67, no. 8, pp. 4986–5004, 2021

    2021

  3. [31]

    A DPI-PAC-Bayesian framework for generalization bounds,

    M. Guan, F. Farokhi, and J. Zhu, “A DPI-PAC-Bayesian framework for generalization bounds,” inIEEE Information Theory Workshop (ITW) 2025, Australia, 2025, pp. 1–6

    2025

  4. [12]

    Max-information, differential privacy, and post-selection hypothesis testing,

    R. Rogers, A. Roth, A. Smith, and O. Thakkar, “Max-information, differential privacy, and post-selection hypothesis testing,” in2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 2016, pp. 487–494

    2016

  5. [1]

    Controlling bias in adaptive data analysis using information theory,

    D. Russo and J. Zou, “Controlling bias in adaptive data analysis using information theory,” inArtificial Intelligence and Statistics. PMLR, 2016, pp. 1232–1240

    2016

  6. [2]

    Information-theoretic analysis of generalization capability of learning algorithms,

    A. Xu and M. Raginsky, “Information-theoretic analysis of generalization capability of learning algorithms,”Advances in Neural Information Processing Systems, vol. 30, 2017

    2017

  7. [4]

    Generalization bounds via information density and conditional information density,

    F. Hellström and G. Durisi, “Generalization bounds via information density and conditional information density,”IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 3, pp. 824–839, 2020

    2020

  8. [5]

    An operational measure of information leakage,

    I. Issa, S. Kamath, and A. B. Wagner, “An operational measure of information leakage,” inConference on Information Science and Systems (CISS). IEEE, 2016, pp. 234–239

    2016

Show all 90 references
  1. [6]

    f-divergence inequalities,

    I. Sason and S. Verdú, “f-divergence inequalities,”IEEE Transactions on Information Theory, vol. 62, no. 11, pp. 5973–6006, 2016

    2016

  2. [7]

    Information radius,

    R. Sibson, “Information radius,”Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, vol. 14, no. 2, pp. 149–160, 1969

    1969

  3. [8]

    α-mutual information,

    S. Verdú, “α-mutual information,” inInformation Theory and Applications Workshop (ITA). IEEE, 2015, pp. 1–6

    2015

  4. [9]

    A primer on PAC-Bayesian learning,

    B. Guedj, “A primer on PAC-Bayesian learning,”arXiv preprint arXiv:1901.05353, 2019

    1901 arXiv

  5. [10]

    Reasoning about generalization via conditional mutual information,

    T. Steinke and L. Zakynthinou, “Reasoning about generalization via conditional mutual information,” inConference on Learning Theory (COLT). PMLR, 2020, pp. 3437–3452

    2020

  6. [11]

    Calibrating noise to sensitivity in private data analysis,

    C. Dwork, F. McSherry, K. Nissim, and A. Smith, “Calibrating noise to sensitivity in private data analysis,” inThird Theory of Cryptography Conference, TCC 2006, New York, NY, March, 2006, pp. 265–284

    2006

  7. [13]

    I-divergence geometry of probability distributions and minimization problems,

    I. Csiszár, “I-divergence geometry of probability distributions and minimization problems,”The Annals of Probability, pp. 146–158, 1975

    1975

  8. [14]

    Large deviations for markov processes and the asymptotic evaluation of certain markov process expectations for large times,

    M. Donsker and S. Varadhan, “Large deviations for markov processes and the asymptotic evaluation of certain markov process expectations for large times,” inProbabilistic Methods in Differential Equations: Proceedings of the Conference Held at the University of Victoria, August...

    1974

  9. [16]

    Novel change of measure inequalities with applications to PAC-Bayesian bounds and monte carlo estimation,

    Y . Ohnishi and J. Honorio, “Novel change of measure inequalities with applications to PAC-Bayesian bounds and monte carlo estimation,” inInternational conference on artificial intelligence and statistics. PMLR, 2021, pp. 1711–1719

    2021

  10. [17]

    Polyanskiy and Y

    Y . Polyanskiy and Y . Wu,Information theory: From coding to learning. Cambridge University Press, 2025

    2025

  11. [18]

    Learners that use little information,

    R. Bassily, S. Moran, I. Nachum, J. Shafer, and A. Yehudayoff, “Learners that use little information,” inAlgorithmic Learning Theory. PMLR, 2018, pp. 25–55

    2018

  12. [19]

    Chaining mutual information and tightening generalization bounds,

    A. Asadi, E. Abbe, and S. Verdú, “Chaining mutual information and tightening generalization bounds,”Advances in Neural Information Processing Systems, vol. 31, 2018

    2018

  13. [20]

    f-divergences and their applications in lossy compression and bounding generalization error,

    S. Masiha, A. Gohari, and M. H. Yassaee, “f-divergences and their applications in lossy compression and bounding generalization error,” IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 7538–7564, 2023

    2023

  14. [21]

    A unified framework for information-theoretic generalization bounds,

    Y . Chu and M. Raginsky, “A unified framework for information-theoretic generalization bounds,”Advances in Neural Information Processing Systems, vol. 36, pp. 79 260–79 278, 2023

    2023

  15. [22]

    Rate-distortion theoretic generalization bounds for stochastic learning algorithms,

    M. Sefidgaran, A. Gohari, G. Richard, and U. Simsekli, “Rate-distortion theoretic generalization bounds for stochastic learning algorithms,” inConference on Learning Theory (COLT). PMLR, 2022, pp. 4416–4463

    2022

  16. [23]

    On measures of entropy and information,

    A. Rényi, “On measures of entropy and information,” inProceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics. The Regents of the University of California, 1961

    1961

  17. [24]

    Generalization in adaptive data analysis and holdout reuse,

    C. Dwork, V . Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. Roth, “Generalization in adaptive data analysis and holdout reuse,” Advances in neural information processing systems, vol. 28, 2015

    2015

  18. [25]

    Preserving statistical validity in adaptive data analysis,

    C. Dwork, V . Feldman, M. Hardt, T. Pitassi, O. Reingold, and A. L. Roth, “Preserving statistical validity in adaptive data analysis,” in ACM Symposium on Theory of Computing, 2015, pp. 117–126

    2015

  19. [26]

    On information-type measure of difference of probability distributions and indirect observations,

    I. Csiszár, “On information-type measure of difference of probability distributions and indirect observations,”Studia Sci. Math. Hungar., vol. 2, pp. 299–318, 1967. February 11, 2026 DRAFT 16

    1967

  20. [27]

    Eine informationstheoretische ungleichung und ihre anwendung auf den beweis der ergodizität von markoffschen ketten,

    ——, “Eine informationstheoretische ungleichung und ihre anwendung auf den beweis der ergodizität von markoffschen ketten,”A Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei, vol. 8, no. 1-2, pp. 85–108, 1963

    1963

  21. [28]

    A general class of coefficients of divergence of one distribution from another,

    S. M. Ali and S. D. Silvey, “A general class of coefficients of divergence of one distribution from another,”Journal of the Royal Statistical Society: Series B (Methodological), vol. 28, no. 1, pp. 131–142, 1966

    1966

  22. [29]

    On the concept and measure of information contained in an observation,

    I. Vincze, “On the concept and measure of information contained in an observation,” inContributions to probability. Elsevier, 1981, pp. 207–214

    1981

  23. [30]

    Le Cam,Asymptotic methods in statistical decision theory

    L. Le Cam,Asymptotic methods in statistical decision theory. Springer Science & Business Media, 2012

    2012

  24. [32]

    Computable bounds on the exploration bias,

    I. Issa and M. Gastpar, “Computable bounds on the exploration bias,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2018, pp. 576–580

    2018

  25. [33]

    Hypothesis testing under maximal leakage privacy constraints,

    J. Liao, L. Sankar, F. P. Calmon, and V . Y . Tan, “Hypothesis testing under maximal leakage privacy constraints,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 779–783

    2017

  26. [34]

    A tunable measure for information leakage,

    J. Liao, O. Kosut, L. Sankar, and F. P. Calmon, “A tunable measure for information leakage,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2018, pp. 701–705

    2018

  27. [35]

    Pointwise maximal leakage,

    S. Saeidian, G. Cervia, T. J. Oechtering, and M. Skoglund, “Pointwise maximal leakage,”IEEE Transactions on Information Theory, vol. 69, no. 12, pp. 8054–8080, 2023

    2023

  28. [36]

    Generalization error bounds for noisy, iterative algorithms via maximal leakage,

    I. Issa, A. R. Esposito, and M. Gastpar, “Generalization error bounds for noisy, iterative algorithms via maximal leakage,” inConference on Learning Theory (COLT). PMLR, 2023, pp. 4952–4976

    2023

  29. [37]

    Sibsonα-mutual information and its variational representations,

    A. R. Esposito, M. Gastpar, and I. Issa, “Sibsonα-mutual information and its variational representations,”IEEE Transactions on Information Theory, vol. 72, no. 7, pp. 1–36, 2025

    2025

  30. [38]

    Tighter risk certificates for neural networks,

    M. Pérez-Ortiz, O. Rivasplata, J. Shawe-Taylor, and C. Szepesvári, “Tighter risk certificates for neural networks,”Journal of Machine Learning Research, vol. 22, no. 227, pp. 1–40, 2021

    2021

  31. [39]

    Still no free lunches: the price to pay for tighter PAC-bayes bounds,

    B. Guedj and L. Pujol, “Still no free lunches: the price to pay for tighter PAC-bayes bounds,”Entropy, vol. 23, no. 11, p. 1529, 2021

    2021

  32. [40]

    Non-vacuous generalisation bounds for shallow neural networks,

    F. Biggs and B. Guedj, “Non-vacuous generalisation bounds for shallow neural networks,” inInternational conference on machine learning. PMLR, 2022, pp. 1963–1981

    2022

  33. [41]

    Some PAC-Bayesian theorems,

    D. A. McAllester, “Some PAC-Bayesian theorems,” inConference on Computational Learning Theory, 1998, pp. 230–234

    1998

  34. [42]

    Pac-bayesian model averaging,

    ——, “Pac-bayesian model averaging,” inProceedings of the twelfth annual conference on Computational learning theory, 1999, pp. 164–170

    1999

  35. [43]

    Catoni,Statistical learning theory and stochastic optimization: Ecole d’Eté de Probabilités de Saint-Flour XXXI-2001

    O. Catoni,Statistical learning theory and stochastic optimization: Ecole d’Eté de Probabilités de Saint-Flour XXXI-2001. Springer, 2004

    2001

  36. [44]

    PAC-Bayesian supervised classification: the thermodynamics of statistical learning,

    ——, “PAC-Bayesian supervised classification: the thermodynamics of statistical learning,”arXiv preprint arXiv:0712.0248, 2007

    2007 arXiv

  37. [45]

    User-friendly introduction to pac-bayes bounds,

    P. Alquier, “User-friendly introduction to pac-bayes bounds,”arXiv preprint arXiv:2110.11216, 2021

    2021 arXiv

  38. [46]

    Generalization bounds via conditionalf-information,

    Z. Wang and Y . Mao, “Generalization bounds via conditionalf-information,”Advances in Neural Information Processing Systems, vol. 37, pp. 52 159–52 188, 2024

    2024

  39. [47]

    Tighter CMI-based generalization bounds via stochastic projection and quantization,

    M. Sefidgaran, K. Nadjahi, and A. Zaidi, “Tighter CMI-based generalization bounds via stochastic projection and quantization,”Advances in Neural Information Processing Systems, vol. 38, 2025

    2025

  40. [48]

    The algorithmic foundations of differential privacy,

    C. Dwork, A. Rothet al., “The algorithmic foundations of differential privacy,”Foundations and Trends® in Theoretical Computer Science, vol. 9, no. 3–4, pp. 211–407, 2014

    2014

  41. [49]

    Upper bounds on the generalization error of private algorithms for discrete data,

    B. Rodríguez-Gálvez, G. Bassi, and M. Skoglund, “Upper bounds on the generalization error of private algorithms for discrete data,”IEEE Transactions on Information Theory, vol. 67, no. 11, pp. 7362–7379, 2021

    2021

  42. [50]

    On the generalization error of differentially private algorithms via typicality,

    Y . Liu, C. H. M. Shiu, L. Wang, and D. Gündüz, “On the generalization error of differentially private algorithms via typicality,”arXiv preprint arXiv:2601.08386, 2026

    2026 arXiv

  43. [51]

    Algorithmic stability for adaptive data analysis,

    R. Bassily, K. Nissim, A. Smith, T. Steinke, U. Stemmer, and J. Ullman, “Algorithmic stability for adaptive data analysis,” inProceedings of the forty-eighth annual ACM symposium on Theory of Computing, 2016, pp. 1046–1059

    2016

  44. [52]

    Information-theoretic generalization bounds for deep neural networks,

    H. He and Z. Goldfeld, “Information-theoretic generalization bounds for deep neural networks,”IEEE Transactions on Information Theory, vol. 71, no. 8, pp. 6227–6247, 2025

    2025

  45. [53]

    Trade-offs in data memorization via strong data processing inequalities,

    V . Feldman, G. Kornowski, and X. Lyu, “Trade-offs in data memorization via strong data processing inequalities,”arXiv preprint arXiv:2506.01855, 2025

    2025

  46. [54]

    A martingale approach to continuous-time marginal structural models,

    K. Røysland, “A martingale approach to continuous-time marginal structural models,”Bernoulli, vol. 17, no. 3, pp. 895–915, Aug. 2011. February 11, 2026 DRAFT 17

    2011

  47. [55]

    Scalable information inequalities for uncertainty quantification,

    M. A. Katsoulakis, L. Rey-Bellet, and J. Wang, “Scalable information inequalities for uncertainty quantification,”Journal of Computational Physics, vol. 336, pp. 513–545, 2017

    2017

  48. [56]

    Relating data compression and learnability,

    N. Littlestone and M. Warmuth, “Relating data compression and learnability,” 1986

    1986

  49. [57]

    Statistical learning theory,

    V . N. Vapnik, V . Vapniket al., “Statistical learning theory,” 1998

    1998

  50. [58]

    Theory of classification: A survey of some recent advances,

    S. Boucheron, O. Bousquet, and G. Lugosi, “Theory of classification: A survey of some recent advances,”ESAIM: Probability and Statistics, vol. 9, pp. 323–375, 2005

    2005

  51. [59]

    Shalev-Shwartz and S

    S. Shalev-Shwartz and S. Ben-David,Understanding machine learning: From theory to algorithms. Cambridge University Press, 2014

    2014

  52. [60]

    Understanding deep learning requires rethinking generalization,

    C. Zhang, S. Bengio, M. Hardt, B. Recht, and O. Vinyals, “Understanding deep learning requires rethinking generalization,” inInternational Conference on Learning Representations (ICLR), 2017

    2017

  53. [61]

    Stability and generalization,

    O. Bousquet and A. Elisseeff, “Stability and generalization,”The Journal of Machine Learning Research, vol. 2, pp. 499–526, 2002

    2002

  54. [62]

    On the uniform convergence of relative frequencies of events to their probabilities,

    V . N. Vapnik and A. Y . Chervonenkis, “On the uniform convergence of relative frequencies of events to their probabilities,” inMeasures of Complexity: Festschrift for Alexey Chervonenkis. Springer, 2015, pp. 11–30

    2015

  55. [63]

    Occam’s razor,

    A. Blumer, A. Ehrenfeucht, D. Haussler, and M. K. Warmuth, “Occam’s razor,”Information processing letters, vol. 24, no. 6, pp. 377–380, 1987

    1987

  56. [64]

    Information complexity and generalization bounds,

    P. K. Banerjee and G. Montúfar, “Information complexity and generalization bounds,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2021, pp. 676–681

    2021

  57. [65]

    Information-theoretic generalization bounds for black-box learning algorithms,

    H. Harutyunyan, M. Raginsky, G. Ver Steeg, and A. Galstyan, “Information-theoretic generalization bounds for black-box learning algorithms,”Advances in Neural Information Processing Systems, vol. 34, pp. 24 670–24 682, 2021

    2021

  58. [66]

    Tightening mutual information-based bounds on generalization error,

    Y . Bu, S. Zou, and V . V . Veeravalli, “Tightening mutual information-based bounds on generalization error,”IEEE Journal on Selected Areas in Information Theory, vol. 1, no. 1, pp. 121–130, 2020

    2020

  59. [67]

    Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms,

    M. Haghifam, J. Negrea, A. Khisti, D. M. Roy, and G. K. Dziugaite, “Sharpened generalization bounds based on conditional mutual information and an application to noisy, iterative algorithms,”Advances in Neural Information Processing Systems, vol. 33, pp. 9925– 9935, 2020

    2020

  60. [68]

    Towards a unified information-theoretic framework for generalization,

    M. Haghifam, G. K. Dziugaite, S. Moran, and D. Roy, “Towards a unified information-theoretic framework for generalization,”Advances in Neural Information Processing Systems, vol. 34, pp. 26 370–26 381, 2021

    2021

  61. [69]

    Data-dependent generalization bounds via variable-size compressibility,

    M. Sefidgaran and A. Zaidi, “Data-dependent generalization bounds via variable-size compressibility,”IEEE Transactions on Information Theory, 2024

    2024

  62. [70]

    Tighter expected generalization error bounds via convexity of information measures,

    G. Aminian, Y . Bu, G. W. Wornell, and M. R. Rodrigues, “Tighter expected generalization error bounds via convexity of information measures,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2022, pp. 2481–2486

    2022

  63. [71]

    A generalization of the rate-distortion theory and applications,

    M. Zakai and J. Ziv, “A generalization of the rate-distortion theory and applications,” inInformation Theory New Trends and Open Problems. Springer, 1975, pp. 87–123

    1975

  64. [72]

    Interpretations of rényi entropies and divergences,

    P. Harremoës, “Interpretations of rényi entropies and divergences,”Physica A: Statistical Mechanics and its Applications, vol. 365, no. 1, pp. 57–62, 2006

    2006

  65. [73]

    P. D. Grünwald,The minimum description length principle. MIT press, 2007

    2007

  66. [74]

    Generalized cutoff rates and Rényi’s information measures,

    I. Csiszár, “Generalized cutoff rates and Rényi’s information measures,”IEEE Transactions on Information Theory, vol. 41, no. 1, pp. 26–34, 2002

    2002

  67. [75]

    Rényi divergence and kullback-leibler divergence,

    T. Van Erven and P. Harremos, “Rényi divergence and kullback-leibler divergence,”IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 3797–3820, 2014

    2014

  68. [76]

    Generalization error bounds for noisy, iterative algorithms,

    A. Pensia, V . Jog, and P. Loh, “Generalization error bounds for noisy, iterative algorithms,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2018, pp. 546–550

    2018

  69. [77]

    Gaussian differential privacy,

    J. Dong, A. Roth, and W. J. Su, “Gaussian differential privacy,”Journal of the Royal Statistical Society Series B: Statistical Methodology, vol. 84, no. 1, pp. 3–37, 2022

    2022

  70. [78]

    Fundamental bound on the reliability of quantum information transmission,

    N. Sharma and N. A. Warsi, “Fundamental bound on the reliability of quantum information transmission,”Physical Review Letters, vol. 110, no. 8, p. 080501, 2013

    2013

  71. [79]

    On the strong converses for the quantum channel capacity theorems,

    ——, “On the strong converses for the quantum channel capacity theorems,”arXiv preprint arXiv:1205.1712, 2012

    2012 arXiv

  72. [80]

    Channel coding rate in the finite blocklength regime,

    Y . Polyanskiy, H. V . Poor, and S. Verdú, “Channel coding rate in the finite blocklength regime,”IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2307–2359, 2010

    2010

  73. [81]

    Arimoto channel coding converse and rényi divergence,

    Y . Polyanskiy and S. Verdú, “Arimoto channel coding converse and rényi divergence,” in2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton). IEEE, 2010, pp. 1327–1333. February 11, 2026 DRAFT 18

    2010

  74. [82]

    E γ-resolvability,

    J. Liu, P. Cuff, and S. Verdú, “E γ-resolvability,”IEEE Transactions on Information Theory, vol. 63, no. 5, pp. 2629–2658, 2016

    2016

  75. [83]

    Resolvability inE γ with applications to lossy compression and wiretap channels,

    ——, “Resolvability inE γ with applications to lossy compression and wiretap channels,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2015, pp. 755–759

    2015

  76. [84]

    Strong functional representation lemma and applications to coding theorems,

    C. T. Li and A. El Gamal, “Strong functional representation lemma and applications to coding theorems,”IEEE Transactions on Information Theory, vol. 64, no. 11, pp. 6967–6978, 2018

    2018

  77. [85]

    Universal exact compression of differentially private mechanisms,

    Y . Liu, W.-N. Chen, A. Özgür, and C. T. Li, “Universal exact compression of differentially private mechanisms,”Advances in Neural Information Processing Systems, 2024

    2024

  78. [86]

    Contraction ofE γ-divergence and its applications to privacy,

    S. Asoodeh, M. Diaz, and F. P. Calmon, “Contraction ofE γ-divergence and its applications to privacy,”arXiv preprint arXiv:2012.11035, 2020

    2012 arXiv

  79. [87]

    Local differential privacy is equivalent to contraction of anf-divergence,

    S. Asoodeh, M. Aliakbarpour, and F. P. Calmon, “Local differential privacy is equivalent to contraction of anf-divergence,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2021, pp. 545–550

    2021

  80. [88]

    Amemiya norm equals orlicz norm in general,

    H. Hudzik and L. Maligranda, “Amemiya norm equals orlicz norm in general,”Indagationes Mathematicae, vol. 11, no. 4, pp. 573–585, 2000

    2000

  81. [89]

    Dependence measures bounding the exploration bias for general measurements,

    J. Jiao, Y . Han, and T. Weissman, “Dependence measures bounding the exploration bias for general measurements,” inIEEE International Symposium on Information Theory (ISIT). IEEE, 2017, pp. 1475–1479. February 11, 2026 DRAFT 19 APPENDIXA MORE ONRELATEDWORK We have presented a ...

    2017

  82. [90]

    high-information

    has been one of the most popular privacy measures in the past decade. Typicality, as a celebrated tool in information theory, has been used to derive generalization bounds for differentially private (and its variants [77]) algorithms that are easy to compute [49], [50]. Intere...

    2026

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.