Sharpened Generalization Bounds based on Conditional Mutual Information and an Application to Noisy, Iterative Algorithms

1 Introduction

• The paper frames generalization bounds through dependence between training data and learned parameters, building on mutual-information bounds and refinements using individual samples or data-dependent estimates.The cited prior work includes Russo and Zou, Xu and Raginsky, Bu et al., and Negrea et al..Source: §1 · pp. 1–2
• The super-sample setup hides the training sample within an IID array, with random indices identifying its locations; conditional mutual information measures dependence between learned parameters and those indices given the array.The paper connects this measure to recognizing which samples from the super-sample were used for training.Source: §1 · p. 2

1.1 Contributions

• For Langevin dynamics, the paper constructs a generalized prior that uses the optimization trajectory to learn about dataset indices, so it need not pay again for information from previous iterations.The authors describe this as the first generalized prior that learns about the dataset from the algorithm’s iterates.Source: §1 · p. 2, §1.1 · p. 2
• Experiments show the Langevin dynamics bound is tighter than, especially late in training, and remains non-vacuous for more epochs without exceeding 1 during severe overfitting.A hypothesis-test component discounts the contributions of new gradients in late training.Source: §1 · p. 2, §1.1 · p. 3
• The paper shows conditional mutual information is less than input–output mutual information for any algorithm, data distribution, and k, and converges to it as k grows for finite parameter spaces.It also introduces two super-sample-based generalization bounds that are tighter than bounds based on conditional mutual information.Source: §1.1 · p. 2, §1 · p. 2

1.2 Definitions from Probability and Information Theory

• A probability kernel is defined as a measurable map from an input space to probability measures on an output space; the paper also defines conditional mutual information as expected disintegrated mutual information.The notation section introduces these probability and information-theoretic conventions.Source: §1.2 · p. 3

• The section aims to unify the two main information-theoretic approaches to studying generalization error.Source: §2 · p. 3
• For finite parameter spaces, bounds based on CMI_k^D(A) can recover bounds based on IOMI_D(A).Source: §2 · p. 3
• CMI_k^D(A) is never larger than IOMI_D(A).Source: §2 · p. 3
• For finite parameter spaces, CMI_k^D(A) agrees with IOMI_D(A) as k tends to infinity.Source: §2 · p. 3

3 Sharpened Bounds based on Individual Samples

• Theorem 3.1 bounds expected generalization error using mutual information between the output and a random subset of indices, and is tighter than Theorem 1.3 for k = 2.Source: §3 · p. 4
• The bound increases with subset size m, and its tightest value is achieved when m = 1.Source: §3 · p. 4
• Theorem 3.4 sets J ∼ Unif([n]) (m = 1 above) independent from W, ˜Z(2), and U, and is stated to be tighter than Theorem 1.3.Source: §3 · p. 4

3.1 Controlling CMI bounds using KL Divergence

• KL control uses a prior informed by the super-sample; knowing the other training samples reduces the possible training sets and lets priors better exploit dependence on the index set.Source: §3.1 · p. 5

3.2 Tighter Generalization bound for the case m = 1

• For m = 1, Theorem 3.7 gives a tighter direct KL bound by moving expectations over U_Jc and J outside the concave square root.Source: §3.2 · p. 5

4.1 Bounding Generalization Error via Hypothesis Testing

• An online test uses the trajectory to infer the hidden index; once inferred, later penalty contributions stop accumulating, even when subsequent gradients are large.The prior can use the history of weights to reduce its conditional KL penalty.Source: §4.1 · p. 6

4.2 Example: Langevin Dynamics Algorithm for Non-Convex Learning

• For Langevin dynamics, a non-Markovian prior tests which candidate sample contributed to the gradient, using past iterates to discount later information costs.The prior’s decision function weights candidate gradients according to evidence from the trajectory.Source: §4 · p. 5, §4.2 · p. 6
• Under an L-Lipschitz surrogate loss, the bound improves by a constant factor over the naïve θ(x)=1/2 choice and has an order-wise improvement in n over bounds by Bu et al. and Pensia et al..For more sophisticated θ, analytical comparison is difficult because the impact of discounting is hard to quantify.Source: §4.2 · p. 7
• Unlike Markovian-prior analyses that accumulate per-step penalties and may become vacuous, trajectory-based testing filters those penalties when the hidden index can be inferred.The proposed penalty uses squared two-sample incoherence; existing approaches use squared gradient norms, squared gradient norms, or minibatch gradient-covariance trace.Source: §4.2 · pp. 7–8

4.2.1 Empirical Results

• The proposed bound is tighter and remains non-vacuous for more iterations; its hypothesis-test error can decay over training, producing a plateau in CIFAR10 and Fashion-MNIST experiments.For CIFAR10, the test error is vanishingly small after iteration 600.Source: §4.2.1 · p. 8, Figure 1 · p. 9

Funding

• The Vector Institute supported MH and JN, and also provided research resources.JN additionally received an NSERC Vanier Canada Graduate Scholarship and an NSERC Michael Smith Foreign Study Supplement.Source: Funding · p. 10
• DMR received support from an NSERC Discovery Grant and an Ontario Early Researcher Award.Source: Funding · p. 10
• The research was partly carried out during visits to the Institute for Advanced Study by MH, JN, GKD, and DMR.JN’s visit was funded by an NSERC Michael Smith Foreign Study Supplement.Source: Funding · p. 10

A CMI, Membership Attack, and Fano’s Inequality

• Fano’s inequality applies because the index vector is uniform over a set of size k^n.Source: A CMI, Membership Attack, and Fano’s… · p. 12
• Conditional mutual information lower-bounds the hardness of recovering the training-sample indices from the learned output and super-sample.The argument invokes Fano’s inequality for the uniformly distributed index vector.Source: A CMI, Membership Attack, and Fano’s… · p. 12
• The result formally connects generalization to a membership attack in which an adversary uses the model and super-sample to identify the training set.The passage states that conditional mutual information upper-bounds every adversary’s success probability.Source: A CMI, Membership Attack, and Fano’s… · p. 12

B Matching the leading coefficient of Theorem 1.1 with CMIk

• The comparison considers a learning algorithm with finite output as k tends to infinity.The plotted constants are those of Theorems 1.1, 1.3, and B.1.Source: B Matching the leading coefficient of… · p. 12, Figure 2 · p. 13
• Theorem B.1 is rewritten for the k → ∞ comparison before its constant is plotted against the other two theorems.The supplied passage introduces the reformulation but does not provide a readable formula.Source: B Matching the leading coefficient of… · p. 12, Figure 2 · p. 13
• Theorem B.1 gives a much tighter constant than Theorem 1.3 and matches Theorem 1.1 when IOMID(A) = 1.The comparison concerns the constants as k tends to infinity.Source: B Matching the leading coefficient of… · p. 12, Figure 2 · p. 13

C Proofs of Section 2

• The expected-generalization-error bound is derived using the chain rule for mutual information and the Donsker–Varadhan variational formula.The proof also invokes Bennett’s inequality and independence of the auxiliary variables in its bound derivation.Source: C Proofs of Section 2 · pp. 13–16
• I(W;U(k), Ẑ(k)) equals I(W;S) because W is independent of (Ẑ(k), U(k)) given S.The proof uses that S is measurable with respect to (Ẑ(k), U(k)).Source: C Proofs of Section 2 · p. 13
• When I(W;S) is finite, the proof reduces the limiting conditional-mutual-information claim to showing I(W;Ẑ(k)) → 0.For finite output, the proof establishes convergence of the probabilities associated with each output value, then concludes that this mutual information vanishes as k grows.Source: C Proofs of Section 2 · pp. 13–14

D Proofs of Section 3

• In the proof of Theorem 3.1, the term I_{Ẑ(2)}(J;U_J) vanishes because J is independent of U_J given Ẑ(2).The proof substitutes this into the preceding equation to obtain the desired result.Source: D Proofs of Section 3 · p. 17
• Theorem 3.2’s proof uses conditional independence relations and a modified Han inequality to obtain the bound.The proof also uses that U is independent of Ẑ(2) and that its elements are IID.Source: D Proofs of Section 3 · p. 18
• The proof of Theorem 3.4 applies the Donsker–Varadhan variational formula and disintegration, then averages over indices and takes expectations.Source: D Proofs of Section 3 · p. 18
• Theorem 3.7’s proof uses Hoeffding’s lemma for a bounded function and concludes the desired result.The proof defines independent auxiliary variables in its variational-formula argument.Source: D Proofs of Section 3 · p. 19

E Proofs of Section 4

• The proof derives Eq. (14) using the update rule’s Markov property and a belief vector built from the trajectory’s log-likelihood ratio.It specifies a uniform prior over the two hypotheses.Source: E Proofs of Section 4 · pp. 19–21
• The proof uses information in the trajectory up to time t to construct a prior for a binary test between hypotheses about which candidate sample is in the training set.The two hypotheses are that Z1,J or Z2,J, respectively, belongs to the training set.Source: E Proofs of Section 4 · p. 20

F Conditional Han’s Inequality

• The conditional Han inequality lemma states that its quantity is decreasing in k.The proof averages over permutations of the indices to obtain the result.Source: F Conditional Han’s Inequality · p. 21

• The section covers experiment details and minimizing the generalization bound in Theorem 4.2.Source: G Details of Experiments · p. 21

G.1 Network architectures and learning curve

• Tables 2–5 summarize experiment hyperparameters for MNIST with MLP, MNIST with CNN, Fashion-MNIST with CNN, and CIFAR10 with CNN.Source: §G.1 · p. 21, Table 2 · p. 23, Table 3 · p. 23
• Figure 3 plots training error, test error, and cross-entropy training loss, with log-scale y-axes for the error plots.The learning curves are for the experiments reported in Section 4.2.1.Source: §G.1 · p. 21, Figure 3 · p. 22

G.2 Optimizing the bound over the choice of θ function

• Theorem 4.2’s bound is minimized over θ using half the trajectory samples, then evaluated on the other half for an unbiased estimate.The training split selects θ_a⋆ to minimize expected generalization; the test split evaluates that choice.Source: §G.2 · p. 23