PaperlayerView exact revision on arXiv

Source-linked AI summary

Tightening Mutual Information Based Bounds on Generalization Error

Yuheng Bu, Shaofeng Zou, Venugopal V. Veeravalli

arXiv:1901.04609v2cs.LGstat.ML

TL;DR

The paper targets limitations of existing generalization bounds, including infinite mutual information for deterministic ERM, restrictive CGF assumptions, and difficult empirical evaluation. It derives an individual-sample mutual-information bound with broader applicability and tighter characterization, including for noisy and iterative algorithms. The resulting bound is also presented as readily estimable in practice.

  • Problem

    Existing generalization bounds can be infinite for deterministic ERM, require restrictive CGF conditions, and be difficult to evaluate empirically.

  • Method

    The paper combines point-wise stability with information theory to bound generalization error using I(W; Zi) for each individual training sample.

  • Results

    The ISMI bound is more broadly applicable and considerably tighter than existing bounds, including in the Gaussian-process comparison and SGLD analysis.

  • Takeaways & Limitations

    Because individual-sample mutual information has dimension independent of n, the ISMI bound can be estimated empirically in practice.

Abstract

from arXiv · show

An information-theoretic upper bound on the generalization error of supervised learning algorithms is derived. The bound is constructed in terms of the mutual information between each individual training sample and the output of the learning algorithm. The bound is derived under more general conditions on the loss function than in existing studies; nevertheless, it provides a tighter characterization of the generalization error. Examples of learning algorithms are provided to demonstrate the the tightness of the bound, and to show that it has a broad range of applicability. Application to noisy and iterative algorithms, e.g., stochastic gradient Langevin dynamics (SGLD), is also studied, where the constructed bound provides a tighter characterization of the generalization error than existing results. Finally, it is demonstrated that, unlike existing bounds, which are difficult to compute and evaluate empirically, the proposed bound can be estimated easily in practice.

I. INTRODUCTION

The paper addresses why deep learning can generalize well despite limitations of classical and existing information-theoretic bounds. It proposes a tighter bound based on the mutual information between each individual training sample and the algorithm’s output hypothesis.

  • Motivation: Deep learning often achieves low training error while performing well on unseen data, but the reasons for this generalization remain insufficiently understood.
  • Limitations of Existing Bounds: Classical complexity-based bounds can scale exponentially with network depth and often ignore implicit regularization from training algorithms.
  • Limitations of Existing Bounds: Existing algorithm-dependent bounds do not fully exploit dependence on the true data-generating distribution, which can strongly affect generalization error.
  • Information-Theoretic Framework: Mutual-information bounds incorporate the learning algorithm, hypothesis space, and data distribution, offering a broader information-theoretic framework for generalization analysis.
  • Limitations of Existing Bounds: Existing mutual-information bounds can become infinite for deterministic ERM and require bounded loss CGFs that may fail in some problems.
  • Main Contribution: The proposed ISMI bound combines point-wise stability with information theory, uses more general CGF conditions, applies more broadly, and can be tighter than prior bounds.

II. PRELIMINARIES

The preliminaries establish notation and CGF-based tools for deriving a general decoupling estimate. The analysis then replaces uniform CGF control over hypotheses with an expected CGF condition under an independent product distribution.

  • Notation: The paper uses uppercase letters for random variables, calligraphic uppercase letters for sets, product distributions such as µ⊗n, and nats for information units.
  • CGF and Legendre Dual: The cumulant generating function and Legendre dual provide convex-analytic tools for controlling centered random variables and inverting the resulting bounds.
  • General Decoupling Estimate: Theorem 1 bounds decoupling when the CGF of f(W~, Z~) is controlled under PW⊗PZ, rather than requiring pointwise CGF bounds for every hypothesis.

B. Individual Sample Mutual Information Bound

The paper constructs a generalization-error bound using mutual information between each individual training sample and the learned output. Under suitable loss-function conditions, the ISMI bound is no worse than existing mutual-information bounds and can be tighter in examples.

  • B. Individual Sample Mutual Information Bound: The proposed bound measures generalization through I(W; Zi), motivated by point-wise stability under replacement of an individual training sample.Point-wise stability concerns how much the expected loss changes when one training sample is replaced.
  • B. Individual Sample Mutual Information Bound: Theorem 2 derives the ISMI bound by comparing dependent W and Zi with independent W and eZ, then applying a cumulant-generating-function inequality.The dependent pair has joint distribution PW,Zi = µ ⊗ PW |Zi, while the independent pair has distribution PW ⊗ PZ.
  • B. Individual Sample Mutual Information Bound: Proposition 1 provides ISMI bounds under two alternative sub-Gaussian assumptions: uniform in w or under the independent product distribution.The second condition applies to ℓ(f W, eZ), whereas the first applies to ℓ(w, Z) for every w.
  • B. Individual Sample Mutual Information Bound: Under a concavity condition on ψ∗−1, the ISMI bound is no worse than the bound based on I(S; W).The sub-Gaussian specialization identifies ψ∗−1(y) with 2R2y and reaches the same comparison.
  • B. Individual Sample Mutual Information Bound: The ISMI bound is also no worse than the conditional-information bound based on I(W; Zi|S−i), and examples are reported to show a more accurate characterization than competing bounds.S−i denotes the training set with Zi removed.

IV. EXAMPLES WITH INFINITE I(W; S)

The examples study learning algorithms with infinite I(W; S), where the conventional bound becomes unusable. For Gaussian mean estimation, the ISMI approach avoids these issues while the conventional assumptions fail.

  • IV. EXAMPLES WITH INFINITE I(W; S): The examples consider learning algorithms with infinite I(W; S), for which the bound in Lemma 1 blows up while the ISMI bound remains an accurate approximation.The paper states that derivations of these bounds are provided in the appendices.
  • A. Estimating the Mean: For Gaussian mean estimation, the learner minimizes squared error and the ERM solution is the sample mean W = 1 n Σ Zi, deterministic given S.The samples follow Z ∼ N(µ, σ2Id).
  • A. Estimating the Mean: The exact generalization error can be computed for the sample-mean ERM solution, while Lemma 1 is inapplicable because I(S; W) = ∞.The failure follows from W being a deterministic function of S.
  • A. Estimating the Mean: Lemma 1 also fails its loss-function condition because squared Gaussian loss is not sub-Gaussian uniformly over w ∈ Rd.The loss variance diverges as ∥w∥2 → ∞, so no uniform CGF upper bound exists.
  • A. Estimating the Mean: Applying Theorem 2 avoids both issues by using individual-sample mutual information, which can be computed exactly for the Gaussian sample-mean output.The paper states that W is Gaussian and that I(W; Zi) is computable exactly.
  • A. Estimating the Mean: A competing bound is described as sub-optimal relative to the true generalization error, while VC-dimension and algorithmic-stability techniques also yield bounds of O.The supplied passage does not preserve the full asymptotic expression.

B. Gaussian Process

The Gaussian-process section evaluates ERM and noisy ERM using exact generalization errors and mutual-information bounds. The proposed ISMI bound is computed through the conditional output distribution and is closer to the true error than the CMI bound.

  • Gaussian-process setup: The ERM loss is a Gaussian process indexed by unit-norm hypotheses, with sub-Gaussian parameter R = 1.The loss may be negative, and the analysis explicitly does not require non-negativity.
  • Bound evaluation: The ISMI bound is applied to both the ERM solution and the noisy solution, with numerical comparisons presented in Figures 1 and 2.Figure 1 concerns ERM, while Figure 2 concerns noisy ERM with ϵ = 0.05.
  • ISMI computation: For ERM, the conditional distribution given one sample is characterized through the phase distribution of a Gaussian vector and depends on that sample's norm.Rotational symmetry permits representing the sample as (r, 0), reducing the conditional distribution to a function of r.
  • Experimental comparison: The experiment compares ERM and additive-noise ERM, including their ISMI and CMI bounds against true generalization errors as sample size varies.The noisy algorithm uses additive noise with ϵ = 0.05.
  • Results: The ISMI bound is closer to the true generalization error and significantly outperforms the CMI bound in both comparisons.The comparison uses generalization error as a function of the number of samples n.

V. NOISY, ITERATIVE ALGORITHMS

The paper applies its individual-sample mutual-information bound to noisy, iterative learning algorithms, specifically stochastic gradient Langevin dynamics.

  • Scope: The ISMI bound from Theorem 2 is applied to a class of noisy, iterative algorithms.The section specifically studies stochastic gradient Langevin dynamics (SGLD).
  • Algorithm: Stochastic gradient Langevin dynamics is the specific algorithm examined in this application.SGLD is identified as the representative noisy, iterative algorithm.
  • Analysis: The application uses Theorem 2's ISMI bound to analyze the generalization error of SGLD.The passage frames SGLD as an application domain for the proposed bound.

A. SGLD Algorithm

The paper applies the individual-sample mutual information (ISMI) bound to stochastic gradient Langevin dynamics (SGLD), deriving a bound under sub-Gaussian loss and bounded-gradient assumptions. With without-replacement sampling, the ISMI bound is tighter than the existing SGLD bound by a factor of √log n.

  • A. SGLD Algorithm: SGLD updates parameters using a selected training sample's gradient, a step size, and isotropic Gaussian noise.The noise variance is controlled by σ(t), and the algorithm outputs W(T) after T = nK iterations over K epochs.
  • A. SGLD Algorithm: The SGLD analysis assumes an R-sub-Gaussian loss and uniformly bounded gradients with bound L.These assumptions support the paper's ISMI generalization analysis for SGLD.
  • A. SGLD Algorithm: Proposition 3 characterizes an ISMI generalization bound for SGLD by conditioning on the random sample-selection path.The proof tracks each sample's selected iterations and uses conditional mutual information, with nonselected iterations contributing no dependence under the stated conditioning.
  • A. SGLD Algorithm: Under without-replacement sampling, every training sample is used exactly once per epoch, simplifying the ISMI calculation.The scheme applies across each block of n iterations corresponding to one training epoch.
  • A. SGLD Algorithm: The ISMI bound is tighter than the existing SGLD bound by a factor of √log n under without-replacement sampling.The comparison uses the specified step-size and noise schedules and removes a logarithmic term using log(1 + x) ≤ x.
  • A. SGLD Algorithm: For typical SGLD, choosing inverse temperature β = Θ(n) yields a generalization bound that does not decay in n.The paper uses β_t = 2 for comparison with prior work and notes that arbitrary β_t choices require separate analysis.

VI. EMPIRICAL EVALUATION OF ISMI BOUND FOR LOGISTIC REGRESSION

The paper empirically evaluates the ISMI bound for logistic regression because the numerical optimization procedure makes the learning algorithm difficult to characterize analytically. A K-nearest-neighbor mutual information estimator provides a practical evaluation whose convergence resembles the true generalization error as the sample size increases.

  • VI. EMPIRICAL EVALUATION OF ISMI BOUND FOR LOGISTIC REGRESSION: Logistic regression is evaluated because its numerical optimization makes the conditional output distribution difficult to characterize analytically.The paper therefore estimates both the ISMI bound and generalization error empirically.
  • VI. EMPIRICAL EVALUATION OF ISMI BOUND FOR LOGISTIC REGRESSION: The experiment uses binary classification with Gaussian-mixture features, balanced labels, and classification error as the evaluation loss.The logistic-regression objective is used because the classification error is not differentiable.
  • VI. EMPIRICAL EVALUATION OF ISMI BOUND FOR LOGISTIC REGRESSION: The ISMI bound is estimated with a K-nearest-neighbor mutual information estimator using N independent training runs.The estimator uses N i.i.d. samples of W and Z_i, and its mean squared estimation error is bounded by O(N^-2/(d_W+d_Z)).
  • VI. EMPIRICAL EVALUATION OF ISMI BOUND FOR LOGISTIC REGRESSION: Order-independent optimization with random shuffling allows estimating one individual mutual information quantity instead of estimating I(W; Z_i) for every i.This reduces the number of mutual information estimates needed for the empirical evaluation.
  • VI. EMPIRICAL EVALUATION OF ISMI BOUND FOR LOGISTIC REGRESSION: The ISMI bound avoids the high-dimensional estimation problem of I(W; S), whose dataset dimension scales linearly with n.The paper contrasts individual-sample mutual information with bounds involving the full training dataset and related Wasserstein estimates.
  • VI. EMPIRICAL EVALUATION OF ISMI BOUND FOR LOGISTIC REGRESSION: The ISMI bound has a similar convergence behavior to the true generalization error as the number of training samples n increases.Figure 3 uses d = 2, μ_1 = (1, 1), μ_-1 = (-1, -1), Σ = 4I, and N = 5000 i.i.d. samples.

VII. CONCLUSIONS

The paper concludes that individual-sample mutual information yields a tighter and more broadly applicable generalization bound. Because its estimated quantities do not grow in dimension with the sample size, the ISMI bound is comparatively easy to evaluate empirically.

  • VII. CONCLUSIONS: The proposed ISMI bound uses mutual information between each individual training sample Z_i and the output hypothesis W.The paper presents this as a tighter information-theoretic upper bound on generalization error.
  • VII. CONCLUSIONS: The ISMI bound is reported as more broadly applicable and considerably tighter than existing information-theoretic bounds.The conclusion also notes that the framework covers cases where full-dataset mutual information can be infinite.
  • VII. CONCLUSIONS: Individual-sample mutual information involves vector dimensions that do not scale with the sample size n, enabling practical empirical evaluation.The paper contrasts this with existing bounds whose estimation involves quantities with dimensions that grow with n.
  • VII. CONCLUSIONS: The framework may be further improved through chaining or data-dependent estimates and may guide model compression in deep learning.These are presented as possible extensions and applications of the proposed information-theoretic framework.

APPENDIX A SECTION IV-A DETAILS

The appendix derives the generalization error and ISMI quantities for a Gaussian example by exploiting independence and covariance structure. The resulting bound can be evaluated through the covariance matrix and numerical integration.

  • APPENDIX A SECTION IV-A DETAILS: For Gaussian W and training samples Z_i, individual mutual information is determined by their covariance matrix.The covariance expression applies for all i = 1, ..., n.
  • APPENDIX A SECTION IV-A DETAILS: The ISMI bound for the ERM algorithm can be evaluated numerically through the derived expression and numerical integration.The appendix thus provides a computable route from the Gaussian covariance characterization to the bound.
  • APPENDIX A SECTION IV-A DETAILS: The appendix derives an upper bound on the cumulant generating function of the loss evaluated at f_W and an independent sample.This provides the intermediate quantity used in the information-theoretic analysis.
  • APPENDIX A SECTION IV-A DETAILS: The appendix computes the expected population risk using the independence of W and an independent test sample Z.This independence simplifies the generalization-error calculation.

B. Individual Sample Mutual Information Bound

The section evaluates ISMI bounds by characterizing conditional phase distributions for ERM-related algorithms and computing the resulting expressions numerically. It compares these bounds with a normalized CMI bound plotted across sample sizes.

  • Conditional distribution characterization: The ISMI bound requires the conditional distribution P_W|Z_i=z_i, with the ERM solution conditioned on an individual training sample.The corresponding conditional distribution for W′ is characterized through a phase distribution.
  • Conditional distribution characterization: P_W|Z_i=z_i is equivalent to the phase distribution of a Gaussian random vector in polar coordinates.Because phase lies in [0, 2π), the conditional distribution can be analyzed through this polar-coordinate representation.
  • Conditional distribution characterization: The joint radius-phase distribution is obtained with the Jacobian method, after which the marginal phase distribution is computed by integrating out the radius.The Gaussian vector is rotated so z_i=(r,0), where r is the ℓ2 norm of z_i; Q(x) denotes the complementary CDF of the standard normal distribution.
  • Numerical evaluation: The ISMI bounds for ERM algorithms W and W′ are evaluated numerically using the resulting phase-distribution expressions.The section explicitly states that both bounds are computed via numerical integration.
  • Comparison bound: The comparison CMI bound is based on Table 1 in, whose reported value for the ERM solution W is 19.0352 at n=1.The n=1 value is identified as equivalent to the classical chaining bound.
  • Comparison bound: For Figures 1 and 2, the CMI bound is normalized by √n, producing the comparison curve 19.0352/√n.This normalization reflects the stated O(1/√n) convergence rate for generalization error.
Loading 1901.04609v2…