Reasoning About Generalization via Conditional Mutual Information

1 Introduction

• Generalization asks whether a model reflects the underlying distribution rather than chance patterns in its training data, but existing guarantees are largely disconnected.Uniform convergence, differential privacy, compression schemes, and uniform stability provide established approaches, yet they are generally incompatible or incomparable.Source: §1 · p. 3, §1.1 · p. 4

1.1 Background: Generalization

• Classical uniform convergence controls the worst-case gap between empirical and population loss, whereas generalization can depend on the learning algorithm itself.VC dimension and fat-shattering dimension yield uniform-convergence bounds, while compression, stability, and differential privacy analyze particular algorithms.Source: §1.1 · pp. 3–4

1.1.1 (Unconditional) Mutual Information

• Unconditional mutual information implies generalization but can be unbounded for continuous data, even when strong generalization is available.The problem is that a single continuous-valued data point has infinite information content; conditioning instead normalizes each datum’s information to one bit.Source: §1.1.1 · pp. 4–5

1.2 Our contributions: Conditional Mutual Information (CMI)

• CMI measures how well a trained model reveals which points in a 2n-point supersample were selected as training data, and it is always finite with 0 ≤ CMID(A) ≤ CMI(A) ≤ n · log 2.The framework includes distribution-dependent and distribution-free versions, with the supersample revealed and the hidden information being its random partition.Source: §1.2 · p. 5

1.2.1 Generalization from CMI

• CMI bounds yield expected, squared, realizable-case, unbounded-loss, nonlinear-loss, and AUROC generalization guarantees, with meaningful bounds when CMI is o(n).The framework also supports non-adaptive composition and postprocessing, while probability bounds obtained through Markov’s inequality generally have polynomial rather than exponential failure decay.Source: §1.2 · p. 6, §1.2.1 · pp. 6–7

1.2.2 Obtaining CMI Bounds

• Known generalization methods imply CMI bounds: compression size k gives CMI(A) ≤ k log(2n), while a VC-dimension-d class admits an ERM with CMI(A) ≤ d log n + 2.These results demonstrate CMI’s unifying role across algorithm-dependent compression and output-space-based VC dimension.Source: §1.2.2 · p. 7, Compression Schemes · pp. 7–8
• Not every empirical risk minimizer over a bounded-VC class has bounded CMI, because pathological tie-breaking can encode superfluous input information.The resulting generalization bound is tight up to a log n term, and approximate empirical risk minimization is conjectured to remove it.Source: Compression Schemes · p. 8
• Compression schemes and VC dimension yield CMI bounds through restricted output spaces, typically incurring a multiplicative log n factor.Tighter bounds are possible: realizable threshold learning admits constant CMI, while uniform-distribution parity learning has CMI ≤ O(n · 2^d−n).Source: Compression Schemes · p. 8
• Distributional stability conditions imply CMI ≤ εn, including concentrated differential privacy and average leave-one-out KL stability.Approximate differential privacy implies total-variation stability and therefore CMI bounds, even though total-variation stability does not imply unconditional mutual-information bounds.Source: Compression Schemes · pp. 8–9

1.3 Related Work, Limitations, & Further Work

• CMI extends mutual-information approaches by incorporating VC dimension, and later work combines it with disintegrated and single-datum information for tighter generalization bounds [HNKRD20].Related approaches include information bottleneck, approximation-based mutual information, PAC-Bayes, and conditional single-datum analyses.Source: §1.3 · pp. 9–11
• CMI generally cannot provide strong high-probability guarantees because low-probability overfitting contributes only proportionally to expected information.The framework cannot guarantee failure probability below CMI/n; approximate max information or Rényi mutual information are proposed alternatives, while repetition can amplify success.Source: §1.3 · p. 10
• Unlike loss stability, CMI is loss-independent, robust to postprocessing, and naturally handles randomized algorithms, but it does not compose adaptively.Universal CMI is proposed as an adaptively composable variant, while evaluated CMI connects CMI with loss stability; further work also seeks additional CMI bounds.Source: §1.3 · pp. 10–11

2 Preliminaries

• The paper fixes notation for random variables, i.i.d. samples, uniform distributions, indexed sets, labeled examples, hypotheses, and empirical and population loss.Random variables use uppercase letters, realizations lowercase letters, and X ← P^n denotes n i.i.d. draws.Source: §2 · pp. 11–12

2.1 KL Divergence

• KL divergence is introduced with natural-log units measured in nats, alongside chain-rule, convexity, Gaussian, and KL-center properties.The KL center of a family of distributions is their mixture weighted by the indexing distribution.Source: §2.1 · p. 12

2.2 Mutual Information

• Mutual information is defined through the joint distribution and marginals, while CMI, chain rules, entropy bounds, symmetry, non-negativity, and data processing provide key identities.The data-processing inequality states that if X → Y → Z is a Markov chain, then I(X; Y) ≥ I(X; Z).Source: §2.2 · p. 13

2.3 Using Mutual Information

• A Donsker–Varadhan or Gibbs variational characterization is used to bound expectations through conditional mutual information and moment-generating functions.The paper also presents an alternative probability-based route for deriving CMI generalization bounds.Source: §2.3 · pp. 13–14

2.4 Concentration Bounds

• Hoeffding’s lemma and bounded-difference results provide the concentration tools, including McDiarmid’s inequality for independent variables and a related variance bound.These results assume coordinate-wise changes are bounded by constants ∆_i.Source: §2.4 · pp. 14–15

Non-adaptive composition

• Non-adaptive composition satisfies CMI(A) ≤ CMI(A1) + CMI(A2) when the algorithms use independent internal randomness.The same property holds for distribution-free CMI.Source: §3 · pp. 15–16
• The composition proof reduces to conditional independence of the two outputs given the random selector, yielding I(F1(S), F2(S); S) ≤ I(F1(S); S) + I(F2(S); S).Independent algorithmic randomness gives I(F1(S); F2(S)|S) = 0.Source: §3 · pp. 15–16

Postprocessing

• Postprocessing cannot increase CMI: applying an independently randomized transformation A2 to A1's output preserves or reduces the information revealed about the data.This follows from the Markov chain S → A1(˜zS) → A2(A1(˜zS)) and the data-processing inequality.Source: §3 · pp. 16–17

Adaptive composition

• The desired adaptive-composition bound CMI(A) ≤ CMI(A1) + sup_w∈W1 CMI(A2(·, w)) does not hold in general.The paper explores a CMI variant satisfying this stronger property in Section 6.1.Source: §3 · p. 17

4 Methods for Bounding CMI

• The section presents these theorems for distribution-free CMI, and they also apply to CMI because CMID(A) ≤ CMI(A) for any algorithm A and distribution D.Thus the listed bounding methods connect several existing generalization approaches to the paper’s CMI framework.Source: §4 · p. 17

4.1 Compression Schemes

• For a compression scheme of size k, the algorithm satisfies CMI(A) ≤ k · log(2n).The compression algorithm selects k sample elements whose retained values determine the output.Source: §4.1 · p. 17

4.2 Differential Privacy and Other Stability Notions

• The framework proves that KL, average-leave-one-out KL, mutual-information, total-variation stability, differential privacy, and d-bit learning imply bounded CMI.In particular, pure ε-differential privacy gives CMID(A) ≤ ε2n/2, d-bit learners give CMI(A) ≤ d, and δ-TV stability gives CMI(A) ≤ δn.Source: §4.2 · pp. 18–21

4.3 VC dimension

• Bounded VC dimension does not imply bounded CMI for every empirical risk minimizer.The result establishes existence of a suitable empirical risk minimizer, whereas threshold functions on an unbounded domain have VC dimension 1 but every proper empirical risk minimizer has unbounded unconditional mutual information [NSY18].Source: §4.3 · p. 21
• For every hypothesis class of VC dimension d, there exists an empirical risk minimizer with CMI(A) ≤ d log n + 2.The construction uses a deterministic empirical risk minimizer with global consistency, while Sauer-Shelah bounds the possible hypotheses on a fixed supersample.Source: §4.3 · pp. 21–23
• A consistently tie-broken empirical risk minimizer satisfies global consistency because reapplying it to an expanded dataset preserves the same hypothesis.The proof uses a fixed well-ordering to resolve multiple empirical minimizers and establishes equality between the original and re-applied outputs.Source: §4.3 · pp. 23–24
• VC dimension alone does not bound every ERM’s CMI: adversarial tie-breaking can encode the dataset in low-order output bits, despite VC dimension one.Global consistency is therefore needed to prevent such hidden-information pathologies; the section conjectures O(d) CMI bounds for approximate ERM variants.Source: §4.3 · pp. 24–25

4.4 Threshold functions

• For threshold functions on the real line, a simple ERM achieves CMI(A) ≤2 in the realizable setting, removing the general O(log n) factor.The algorithm outputs the threshold at the smallest positive example, or the constant-zero threshold when no positive example exists.Source: §4.4 · p. 25
• The threshold learner has constant CMI but infinite unconditional mutual information for continuous distributions, demonstrating a stark separation between CMI and MI.Its output distribution is analyzed through a truncated geometric distribution whose entropy is bounded by 2.Source: §4.4 · p. 26

4.5 Pseudodeterministic Learning

• If a learner outputs one hypothesis w* with probability 1−p, then CMID(A) ≤p · (log(1/p) + 1 + log |W|).This pseudodeterministic-learning bound tends toward zero as p decreases, formalizing how distributional assumptions can reduce CMI.Source: §4.5 · p. 26
• For noiseless parity learning under uniform examples, every consistent learner satisfies CMID(A) ≤ O(n · 2^d−n), improving the generic bound below d.The proof bounds disagreement probability by a union bound over alternative parities; the stated explicit bound is 2^d−n · (n log 2 + 1).Source: §4.5 · p. 27

• The section establishes that bounded CMI implies generalization through a variety of results demonstrating the framework’s versatility.Source: §5 · p. 28

5.1 Linear Loss Bounds for the Agnostic Setting

• Under |ℓ(w, z1) − ℓ(w, z2)| ≤ ∆(z1, z2), Theorem 5.1 bounds linear-loss generalization using 2 n · CMID(A) · E[(∆(Z1, Z2))2].For losses valued in [a, b], ∆ can be chosen as the constant b − a.Source: §5.1 · p. 28
• For ℓ: W × Z → [0, 1], Corollary 5.2 gives the corresponding bound in terms of 2 n · CMID(A).A triangle-inequality variant, Corollary 5.3, also applies to arbitrary real-valued losses using separate suprema over loss magnitudes.Source: §5.1 · p. 28

5.1.1 Expected Absolute Error

• Theorem 5.4 gives a bound involving 2 n · (CMID(A) + log 2) · E[(∆(Z1, Z2))2], under the stated randomized-algorithm setting.It assumes |ℓ(w, z1) − ℓ(w, z2)| ≤ ∆(z1, z2) for all z1, z2 ∈ Z and w ∈ W, while losing a small constant factor.Source: §5.1.1 · p. 29

5.1.2 Expected Squared Error

• Theorem 5.5 further bounds expected squared error for arbitrary measurable linear losses, again with only small constant-factor losses.For bounded losses ℓ: W × Z → [0, 1], Corollary 5.6 gives bounds involving CMID(A), n, u, ε2, and the constants log 3.Source: §5.1.2 · pp. 30–31

• The tighter analysis targets realizable and overfitted algorithms whose expected empirical loss is zero or close to zero, also called the interpolating setting [NDR19].Source: §5.2 · p. 32
• In the exactly zero empirical-error setting, the theorem’s constants are tight and yield non-vacuous bounds whenever CMID(A) < n · log 2.The section notes that CMID(A) ≤ n · log 2 always holds.Source: §5.2 · p. 33
• When empirical loss is not exactly zero, the more general theorem is most useful near zero but has slightly worse constants than the exact-zero statement.Source: §5.2 · p. 33
• For nearly zero empirical loss, the expected population loss is at most 2 times expected empirical loss plus 3·CMI(A).The bound applies to randomized algorithms and arbitrary losses ℓ: W × Z → [0, 1].Source: §5.2 · p. 34

• The nonlinear-loss bounds are the paper’s most general results and subsume the preceding linear-loss bounds up to constants.Source: §5.3 · p. 35

Probability bound

• Theorem 5.9 gives a high-probability generalization bound for arbitrary measurable losses using conditional mutual information and a high-probability bound on loss sensitivity.The sensitivity quantity Δ measures how much the loss changes when one paired sample is switched; a uniform sensitivity bound makes the theorem’s additional term vanish.Source: §5.3 · p. 35

Interpretation

• The bounds first control loss differences between sampled selections from paired data, while standard concentration can relate this quantity to loss against the distribution.The paper notes that independence of the trained model and the paired sample supports this final step, for example via McDiarmid’s inequality and the triangle inequality.Source: §5.3 · pp. 35–36

Expectation bound

• Theorem 5.11 provides a nearly identical expectation bound for arbitrary measurable nonlinear losses, combining CMI with expected sensitivity and a tail contribution.Source: §5.3 · p. 37

Application: Squared Error

• Squared loss is defined as ℓ(w, (x, y)) = (f_w(x) − y)^2 and includes linear regression with f_w(x) = ⟨w, x⟩.Source: §5.4 · p. 39
• Assuming f_w is c-Lipschitz and satisfies f_w(0) = 0, the loss obeys 0 ≤ ℓ(w, (x, y)) ≤ 2c^2∥x∥_p^2 + 2y^2.For linear predictors, these assumptions hold when W = {w ∈ R^d : ∥w∥_q ≤ c} under dual norms.Source: §5.4 · pp. 39–40
• A fourth-moment bound on the data distribution is sufficient to derive a generalization bound from CMI for squared loss.This conclusion follows by combining the squared-loss bound with Theorem 5.4.Source: §5.4 · p. 40

5.5 Application: Hinge Loss

• Hinge loss is defined as max{0, 1−y ·fw(x)} for y ∈{+1, −1}, with the objective Y · fw(X) > 0.Source: §5.5 · p. 40
• For linear predictors fw(x) = ⟨w, x⟩ with W = {w ∈Rd : ∥w∥q ≤c}, hinge loss becomes max{0, 1 −y ·⟨x, w⟩}.Source: §5.5 · p. 40
• Loss differences are bounded by ∥y1x1−y2x2∥p·∥w∥q using dual norms, where 1/p + 1/q = 1.Theorem 5.4 is applied with ∆((x1, y1), (x2, y2)) = c∥y1x1 −y2x2∥p; for p = q = 2, the analysis specializes further.Source: §5.5 · p. 40

Motivation

• The method relaxes bounded-parameter assumptions by incorporating parameter magnitude into generalization results, while remaining combinable with other generalization bounds.Scaling parameters can scale the loss, motivating a magnitude-dependent formulation.Source: §5.6 · p. 40

Lemma 5.12

• The bound controls the probability of a scaled generalization gap by 3 · CMI(A) + log 3, with scaling factor Ψ(A(Z)).Under the stated loss-difference condition, the event threshold is ε · Ψ(A(Z)).Source: §5.6 · p. 41

Proof

• The proof normalizes the loss to remove parameter-magnitude dependence, then applies existing generalization results because CMI is loss-independent.The normalized loss satisfies the required bounded-difference condition before Theorem 5.5 is applied.Source: §5.6 · p. 41

Examples

• Both squared error and hinge loss satisfy the assumptions of Lemma 5.12.The examples use dual norms for squared error and an analogous parameter-dependent factor for hinge loss.Source: §5.6 · p. 41

Definition

• AUROC is the probability that a random positive receives a higher score than a random negative, with ties broken at random.It is equivalently the Wilcoxon–Mann–Whitney statistic and summarizes the ROC tradeoff without selecting a threshold.Source: §5.7 · p. 42

Empirical estimation

• Except in the all-positive or all-negative degenerate case, the empirical AUROC is an unbiased estimator of the true AUROC.In the degenerate case, the empirical AUROC is arbitrarily defined as 1/2.Source: §5.7 · p. 42

Accuracy reduction

• AUROC can be lower-bounded from classification accuracy by 1 − ℓ(f, D) min{p, 1 −p}, via threshold-specific false-positive and false-negative probabilities.This connects the AUROC guarantee to existing classification accuracy bounds.Source: §5.7 · pp. 42–43

CMI corollary

• For zero empirical classification error, the expected AUROC is at least 1 − 1.5 · CMI(A) / n · min{p, 1 −p}.The guarantee assumes 0 < p < 1 and that the thresholded learned score correctly classifies every training example.Source: §5.7 · p. 43

General theorem

• Theorem 5.14 applies nonlinear-loss CMI generalization results to AUROC in all cases, while fixed-score sampling variance is approximately 1/[p(1 −p)n] in the worst case.The variance dependence is therefore roughly correct in the relevant parameters.Source: §5.7 · p. 43

6.1 Adaptive Composition and Universal CMI

• Universal CMI supports adaptive composition: composing algorithms with bounds b1 and b2 yields a bound b1 + b2.Ordinary CMI composes non-adaptively and is invariant under data-oblivious postprocessing, but does not generally support adaptive composition.Source: §6.1 · pp. 48–49
• For an ε-differentially private algorithm, universal CMI is bounded by εn, although differential privacy cannot generally yield strong universal-CMI bounds.A differentially private algorithm can identify large error-correcting-code inputs with high probability, producing high universal CMI.Source: §6.1 · p. 50

6.2.1 Uniform Stability

• Uniform stability controls changes in loss under one-sample replacement and implies generalization, with a nearly tight bound established for losses in [0, 1].Uniform stability is loss-dependent, whereas CMI is loss-agnostic; differential privacy instead controls changes in the output distribution.Source: §6.2.1 · p. 51

6.2.2 Evaluated CMI

• Evaluated CMI incorporates the loss function by measuring information in the loss values at sampled points, and it is no larger than ordinary CMI.Consequently, CMI upper bounds carry over, but the resulting generalization guarantees apply only to the loss function included in evaluated CMI.Source: §6.2.2 · pp. 51–52

6.2.3 Bounding Evaluated CMI from Uniform Stability

• Theorem 6.8’s eCMI reduction does not provide a tight analysis of uniform stability, contrasting with Theorem 6.5’s bound O(γ^2 + 1/n).Further work is needed to integrate uniform stability into the CMI framework.Source: §6.2.3 · p. 53