Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates

Jeffrey Negrea; Mahdi Haghifam; Gintare Karolina Dziugaite; Ashish Khisti; Daniel M. Roy

Source-linked AI summary

Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates

Jeffrey Negrea, Mahdi Haghifam, Gintare Karolina Dziugaite, Ashish Khisti, Daniel M. Roy

arXiv:1911.02151v3Nov 6, 2019stat.MLcs.ITcs.LG

TL;DR

Generalization analysis for noisy iterative learning is hindered by unknown mutual information and loose distribution-independent bounds. This work uses data-dependent priors to forecast mini-batch gradients, obtaining tighter mutual-information bounds for SGLD that depend on gradient incoherence rather than gradient norms or Lipschitz constants.

Problem
Unknown mutual information and distribution-independent Lipschitz-based analyses limit precise, non-vacuous generalization bounds for noisy iterative learning algorithms.
Method
The paper uses data-dependent priors that forecast each mini-batch gradient from a subset of training data, yielding bounds based on gradient incoherence and conditional information quantities.
Results
The resulting bounds are materially tighter and remain non-vacuous after many more epochs, while squared gradient incoherence is 100 to 10,000 times smaller than squared gradient norms in the reported examples.
Takeaways & Limitations
Data-dependent gradient prediction residuals provide a distribution-dependent alternative to gradient norms and Lipschitz constants for analyzing generalization in SGLD.
Takeaways & Limitations
The trajectory-based KL analysis may give a loose upper bound on terminal-parameter KL when the trajectory cannot be inferred from the terminus.

Abstract

from arXiv · show

In this work, we improve upon the stepwise analysis of noisy iterative learning algorithms initiated by Pensia, Jog, and Loh (2018) and recently extended by Bu, Zou, and Veeravalli (2019). Our main contributions are significantly improved mutual information bounds for Stochastic Gradient Langevin Dynamics via data-dependent estimates. Our approach is based on the variational characterization of mutual information and the use of data-dependent priors that forecast the mini-batch gradient based on a subset of the training samples. Our approach is broadly applicable within the information-theoretic framework of Russo and Zou (2015) and Xu and Raginsky (2017). Our bound can be tied to a measure of flatness of the empirical risk surface. As compared with other bounds that depend on the squared norms of gradients, empirical investigations show that the terms in our bounds are orders of magnitude smaller.

1 Introduction

The paper addresses loose or intractable information-theoretic generalization bounds for SGLD by introducing data-dependent estimates and priors. Its resulting bounds replace Lipschitz constants or squared gradient norms with gradient incoherence, which experiments find substantially smaller.

Motivation: Existing SGLD analyses use unknown mutual information, mixing assumptions, or Lipschitz constants that can make bounds vacuous for modern models.Deep-network empirical-risk Lipschitz constants may be prohibitively large or infinite.
Approach: Data-dependent mutual-information estimates use a subset of training data and the remaining data to produce distribution-dependent bounds.The approach introduces data-dependent priors that forecast iterative algorithm dynamics from a randomly chosen subset.
Approach: The analysis develops disintegrated information-theoretic bounds that extract expectations from concave functions as much as possible.This builds on prior improvements that effectively change the order of an expectation and square root.
Contribution: The framework includes information-theoretic bounds relating learned parameters to random training-data subsets and does not require smoothness or learning-rate restrictions.The stated SGLD bound is described as state of the art without those assumptions.
Contribution: The proposed SGLD and Langevin bounds depend on gradient incoherence rather than gradient norms or Lipschitz constants.Gradient incoherence measures disagreement between batch gradients and is never larger than the squared gradient norm.

2 Methods

The methods develop information-theoretic generalization bounds using random data subsets, data-dependent priors, and disintegrated mutual information. These tools decompose sequential algorithms stepwise while trading subset size against estimation variance and exploiting conditional structure for tighter control.

Information-theoretic bounds: The framework bounds expected generalization error through conditional mutual information, disintegrated mutual information, and relative entropy involving random data subsets.The random-subset formulation separates information dependence from risk estimation over the remaining data.
Data-dependent priors: A data-dependent prior uses a subset S_J to forecast the posterior while remaining independent of the complementary subset S^c_J.This construction enables bounds based on information learned beyond the data used to form the prior.
Conditional control: Conditioning on subset information permits tighter mutual-information control than unconditional Lipschitz-based analysis, while the disintegrated quantity is not generally bounded by full mutual information.The method therefore improves control through conditioning rather than by assuming a direct ordering between the two information quantities.
Subset-size tradeoff: The subset size m creates a tradeoff: larger m can reduce mutual information but leaves fewer points for empirical-risk estimation.The resulting bound is not uniformly ordered across subset sizes without additional context.
Sequential decomposition: For sequential algorithms, trajectory-level KL divergence is decomposed into a sum of conditional per-step divergences.This decomposition provides analytical tractability, although it can loosen the terminal-parameter bound when the trajectory is not recoverable from its endpoint.

3 Generalization Bounds for Specific Algorithms

The paper applies its information-theoretic machinery to SGLD and Langevin dynamics by constructing priors that forecast each noisy update. The resulting bounds depend on gradient-prediction residuals and support favorable asymptotic behavior under suitable subset and moment conditions.

SGLD construction: The SGLD analysis constructs a data-dependent prior that closely forecasts each minibatch update while sharing the algorithmic noise covariance.The minibatch sequence is treated as the auxiliary random element in the general bounds.
SGLD bounds: Theorem 3.1 provides expected generalization-error bounds for SGLD with constant batch size under a subgaussian loss assumption.The theorem is obtained by combining the general information bounds with the data-dependent prior.
Gradient incoherence: The SGLD bounds depend on gradient incoherence, represented by the residual between the actual minibatch gradient and its data-dependent prediction.The residual vanishes when the minibatch is contained in the forecasting subset, enabling sharper subset-dependent control.
Langevin dynamics: Langevin dynamics is recovered as the full-batch special case of SGLD, using the same data-dependent-prior strategy.The corresponding theorem assumes a subgaussian loss and applies when every batch contains the full dataset.
Asymptotic behavior: When the subset size is m = Ω(n), the expected generalization-error upper bound is O(β/n), yielding O(n^-1/2) when β = Ω(√n).The paper notes that smaller subsets can produce a lower order in n, including a distinct regime when m = O(√n).

4 Empirical Results

The empirical study compares gradient incoherence and gradient norms across datasets, architectures, schedules, and training epochs. It finds substantially smaller incoherence terms and materially tighter Monte Carlo estimates of the proposed bounds, while noting a training-error tradeoff and limited predictive-performance tuning.

Experimental design: Figure 1a shows that the bound becomes tighter for larger heldout subsets and compares incoherence with a gradient-norm upper bound.Figures 1b and 1c vary inverse-temperature and learning-rate schedules, while Figures 1d–1f compare summands across datasets.
Gradient-term comparison: The squared gradient incoherence is between 100 and 10,000 times smaller than the squared gradient norms across the reported dataset and architecture examples.The comparison uses per-epoch contributions to the proposed bound and the corresponding bound of Mou et al.
Bound comparison: Monte Carlo estimates show that the proposed generalization bounds are materially tighter than the compared bounds and remain non-vacuous after many more epochs.The proposed bound is tighter when the learning rate and inverse temperature are small, although those settings make very low training error difficult to achieve.
Scope of evaluation: The experiments were not designed to achieve state-of-the-art predictive performance, and further tuning could improve the prediction results.The reported focus is bound comparison rather than maximizing predictive accuracy.

B.2 Proofs of Main Results

The proofs use variational and disintegration arguments to control generalization through KL divergences between conditional and data-dependent distributions. They also distinguish subgaussian settings from the boundedness assumption required in one theorem.

Assumptions: The proof reduces the general argument to a subgaussian bound by establishing that the relevant function is σn−m-subgaussian for each parameter.The same reduction appears in the theorem-proof passages using cumulant-generating functions.
KL-based proof strategy: The variational proof uses conditional distributions, random subsets, and data-dependent measures to derive generalization bounds.The arguments invoke the Donsker–Varadhan variational formula and disintegration.
Assumptions: Theorem 2.5 requires boundedness because pointwise subgaussianity of the loss does not necessarily remain subgaussian under the relevant conditional distribution.The other cited proofs can exploit expectations over the complementary sample subset to use the loss's subgaussian property.
KL-based proof strategy: The terminal-parameter KL divergence is upper bounded by the KL divergence between full learning trajectories.This provides analytical tractability for stepwise analysis, although the trajectory bound can be loose.

C Mutual Information Bound for Subgaussian Losses

This section clarifies a flaw in extending pointwise subgaussianity to a learned parameter and supplies the conditional-variance reasoning needed for the mutual-information bound. The extension is valid only under a restrictive constancy condition.

Subgaussianity clarification: Pointwise subgaussianity of f(w,S) does not generally imply subgaussianity of f(W,S) when W is random and independent of S.A Cauchy-plus-normal counterexample shows that the learned-variable quantity may lack even a finite first absolute moment.
Subgaussianity clarification: The flawed argument omits the second term in the conditional variance decomposition, which vanishes only when EW f(W,S) is almost surely constant in W.The missing term captures variation in conditional means across parameter values.
Subgaussianity clarification: The claimed σ-subgaussian conclusion holds exactly when ES f(W,S) − Ef(W,S) is constant.The paper notes that this means all parameter vectors have the same expected generalization error.
Corrected argument: The section presents the corrected result as provable directly through the Donsker–Varadhan variational formula.The discussion distinguishes subgaussian parameters from true standard deviations.

D.2 Finite Population Statistics with Disjoint Samples

This section develops finite-population identities for statistics computed from two disjoint random samples. The resulting covariance calculations support later variance evaluations for the SGLD analysis.

Finite-population setup: Two disjoint subsets are sampled uniformly from a finite population, and their sample means are represented using indicator variables.The setup uses subset sizes n1 and n2 and a population variance matrix Σ.
Covariance calculation: The section computes cross-indicator relationships for distinct population elements to derive covariance formulas for the two sample means.These identities account for dependence created by sampling disjoint subsets.
Application: The derived identities are applied to the variance of a linear combination aȲ1 − bȲ2.The application is explicitly motivated by the SGLD setting developed elsewhere in the paper.

E Asymptotic Results

The asymptotic analysis gives expected-generalization-error bounds under several learning-rate and temperature schedules. For m = n−1, the bounds are ordered 2.3 ≥ 2.4 ≥ 2.5, with potentially material differences when the relevant KL divergence is highly variable.

Geometrically decaying learning rate: Under an L-Lipschitz loss, geometrically decaying learning rates and a temperature ramping polynomially in n yield an asymptotic bound.The schedule uses ηt = η0ρt with 0 < ρ < 1 and a temperature parameter βt that ramps with n.
Polynomially decaying learning rate: Under an L-Lipschitz loss, polynomially decaying learning rates and polynomial temperature in n yield a second asymptotic bound.The learning rate has the form ηt = η0t−α for α > 0, while the temperature is polynomial in n.
Comparison of bounds: For m = n−1, the bounds are ordered 2.3 ≥ 2.4 ≥ 2.5.The ordering follows from Jensen’s inequality applied to the conditional expectations.
Comparison of bounds: When KL(Q(S)∥P(SJ)) has large variance, the differences between the bounds can be materially large.This identifies variability in the KL term as a source of separation among the bounds.

G An analytically tractable example

The analytic mean-estimation example specializes SGLD to a quadratic loss and compares the resulting data-dependent bound with existing bounds. The comparison shows that the proposed bound can be substantially tighter, with the discrepancy depending on the distribution.

Setup: The example estimates the mean of a distribution on R using quadratic loss and a specialized SGLD update.The sample is S = {z1,...,zn} ∼ D^n, with loss ℓ(z,w) = (z − w)^2 and parameter space W = R.
Bound application: The data-dependent generalization bound is applied with m = n − 1 and a trivial random variable U.The held-out index set is chosen as J = {i⋆}.
Comparison: The resulting expected generalization error is bounded analytically and compared with bounds from prior work.The comparison includes bounds obtained using results from [24] [35].
Comparison: The proposed bound can be smaller than the comparison bound because E[|z_i|] ≤ ... follows from Jensen’s inequality.The discrepancy between the bounds can be made arbitrarily large through the choice of distribution D.

H Experiment Details

The experiments evaluate the bound on multilayer perceptrons and convolutional networks across MNIST, Fashion-MNIST, and CIFAR-10. For the MLP experiment, empirical behavior matches the analytical prediction that larger held-out subsets produce tighter bounds.

MLP on MNIST: The MLP experiment uses three hidden layers with 600 units per layer and ReLU activations on MNIST.The architecture is used to compare bounds for different amounts of held-out data.
MLP on MNIST: The empirical results confirm that the bound is tighter when m is larger.This agrees with the analytical dependence of the bound on the held-out-data choice.
CNNs: The CNN experiments on MNIST and Fashion-MNIST use two convolutional layers followed by pooling and two fully connected layers.The convolutional layers have 32 and 64 filters, while the fully connected layers have 1024 nodes each.
CNNs: The CIFAR-10 experiment uses two convolutional layers with 64 filters each and three fully connected layers.The fully connected layers contain 384, 192, and 10 neurons.

H.1 Evaluation of the generalization bound

The evaluation estimates the proposed and comparison bounds with nested Monte Carlo simulations under several training configurations. Reported training and generalization errors vary with inverse-temperature and learning-rate schedules while other parameters are held fixed.

Evaluation procedure: The proposed bound is estimated using nested Monte Carlo simulations of the inner gradient-norm expectation and the outer expectation.The procedure follows Theorem 3.1, specifically Eq. (6).
Evaluation procedure: Each hyperparameter combination uses 10 outer simulations with 10 inner simulations, while the comparison bound uses 100 simulations.The comparison is the bound from Mou et al. [22], evaluated using their Theorem 10.
Training schedules: The learning-rate schedules are η_t^(small) = 8×10^-4 × 0.96^(t/2000) and η_t^(large) = 2×10^-3 × 0.96^(t/2000).Here, t denotes the iteration number, and the remaining parameters are held fixed according to Table 2.
Training schedules: At epoch 6, the small-learning-rate setting has 7.62% training error and 1.1% test-set generalization error, versus 6.3% and 1.0% for the large-learning-rate setting.These values are reported for the two learning-rate scenarios with otherwise matched parameters.

I High Probability PAC-Bayes Bounds

The paper extends its data-dependent mutual-information and PAC-Bayes framework to high-probability generalization bounds. The construction permits priors depending on a subset of the data, but the authors present these bounds as illustrative rather than tight.

High-probability bounds: The methods used for expected generalization error can also derive high-probability generalization bounds.The authors note that the data-dependence level could be tuned to tighten the bound further.
Data-dependent priors: The PAC-Bayes proposition applies to a prior depending on m uniformly selected data points while the posterior depends on the full dataset.The result is applied conditionally on the subset determining the prior.
Tradeoff: In the Langevin setting, the construction yields a tradeoff between m and n − m under worst-case Lipschitz-constant bounds.Expectations over U and/or J can produce high-probability bounds for the full empirical loss.
Scope: The authors state that these high-probability bounds are not the tightest possible and reserve further investigation for future work.The section is presented as illustrating the possibility and nature of such bounds.