PaperlayerView exact revision on arXiv

Source-linked AI summary

Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors

Gintare Karolina Dziugaite, Daniel M. Roy

arXiv:1712.09376v3stat.MLcs.LG

TL;DR

The paper asks how Entropy-SGD can provide generalization guarantees when its optimized prior depends on the data. It interprets Entropy-SGD as optimizing a PAC-Bayes bound, replaces the relevant update with SGLD to obtain private data-dependent priors, and finds tight but potentially optimistic bounds alongside test errors below state-of-the-art performance.

  • Problem

    Entropy-SGD optimizes a PAC-Bayes prior using the data, violating the theorem’s data-independence requirement and leaving its generalization behavior unresolved.

  • Method

    The paper connects local-entropy maximization to PAC-Bayes and uses SGLD-based, differentially private data-dependent priors to seek valid bounds.

  • Results

    Entropy-SGD and its Gibbs posterior can rapidly overfit, while Entropy-SGLD produces relatively tight but conservative bounds and 3–8% MNIST test error under a privacy contribution of approximately 0.2%.

  • Takeaways & Limitations

    Private data-dependent priors can preserve PAC-Bayes validity while improving prior matching, but the reported Entropy-SGLD settings do not achieve state-of-the-art performance.

  • Takeaways & Limitations

    The bounds rely on assuming SGLD reaches stationarity, although convergence is difficult to measure and the authors interpret them as optimistic.

Abstract

from arXiv · show

We show that Entropy-SGD (Chaudhari et al., 2017), when viewed as a learning algorithm, optimizes a PAC-Bayes bound on the risk of a Gibbs (posterior) classifier, i.e., a randomized classifier obtained by a risk-sensitive perturbation of the weights of a learned classifier. Entropy-SGD works by optimizing the bound's prior, violating the hypothesis of the PAC-Bayes theorem that the prior is chosen independently of the data. Indeed, available implementations of Entropy-SGD rapidly obtain zero training error on random labels and the same holds of the Gibbs posterior. In order to obtain a valid generalization bound, we rely on a result showing that data-dependent priors obtained by stochastic gradient Langevin dynamics (SGLD) yield valid PAC-Bayes bounds provided the target distribution of SGLD is ε-differentially private. We observe that test error on MNIST and CIFAR10 falls within the (empirically nonvacuous) risk bounds computed under the assumption that SGLD reaches stationarity. In particular, Entropy-SGLD can be configured to yield relatively tight generalization bounds and still fit real labels, although these same settings do not obtain state-of-the-art performance.

1. Introduction

The paper connects Entropy-SGD to PAC-Bayes theory, then shows that its data-dependent prior can invalidate the bound and permit overfitting. It studies private SGLD-based priors as a route to valid bounds, while reporting tight but conservative empirical results.

  • Contribution: Entropy-SGD’s local-entropy maximization corresponds to minimizing a PAC-Bayes bound on a Gibbs posterior.The perturbation distribution defines the PAC-Bayesian prior, so optimizing local entropy also optimizes the bound’s prior.
  • Results: Entropy-SGD and its Gibbs posterior can rapidly overfit, despite claims that Entropy-SGD may be more stable than SGD.The paper identifies two theoretically motivated changes intended to prevent overfitting.
  • Problem: Optimizing the prior mean with training data violates the PAC-Bayes requirement that the prior be data-independent.The paper reports that the resulting bound does not hold empirically.
  • Method: Differentially private data-dependent priors can yield valid, though looser, PAC-Bayes bounds; SGLD provides a route because it converges weakly to its target distribution under regularity conditions.The paper replaces the local-entropy SGD step with SGLD in Entropy-SGLD.
  • Limitation: The approach faces a convergence limitation because the distance of SGLD from convergence cannot easily be measured.The experiments therefore run SGLD beyond apparent convergence and interpret bounds under an assumed convergence condition as optimistic.
  • Results: 3–8% test-set error on MNIST was obtained when the privacy contribution was limited to approximately 0.2%, roughly 5–10 times the 0.2-1% state-of-the-art range.The resulting PAC-Bayes bounds were described as quite tight but still conservative.

2. Preliminaries: Supervised learning, Entropy-SGD, and PAC-Bayes

This section introduces supervised learning with randomized Gibbs classifiers, Entropy-SGD's local-entropy optimization, and the PAC-Bayes framework used to analyze generalization. It also highlights that Entropy-SGD's noise modification can undermine smoothness and stability claims.

  • Supervised learning and Gibbs classifiers: Gibbs classifiers are probability distributions over weight vectors, evaluated through expected risk under a bounded loss.The setup includes neural-network 0–1 loss and a bounded modification of cross-entropy loss.
  • Entropy-SGD: Entropy-SGD maximizes the local-entropy objective Fγ,τ(w;S), the log partition function of an associated Gibbs distribution.The algorithm approximates stochastic gradient ascent using inner-loop SGLD updates.
  • Entropy-SGD: The local-entropy objective is differentiable under an exchange-of-derivatives assumption, even when empirical risk is not.Its derivative and the objective are described as Lipschitz in the original analysis.
  • PAC-Bayes setup: The standard PAC-Bayes prior must be independent of the sample, although it may depend on the data-generating distribution.This requirement motivates later treatment of data-dependent priors.

3. Maximizing local entropy minimizes a PAC-Bayes bound

The paper proves that maximizing local entropy is equivalent to minimizing a PAC-Bayes bound for a Gibbs posterior with a Gaussian prior centered at the learned weights. This connection requires bounded loss.

  • Gibbs distributions: For a measure P and function g, the Gibbs distribution Pexp(−τg) reweights P by the exponential of negative scaled loss.When g is empirical risk and P is a probability measure, this is the Gibbs posterior.
  • PAC-Bayes connection: Maximizing Fγ,τ(w;S) selects exactly the weights minimizing the PAC-Bayes bound for Q = Gw,Sγ,τ.The corresponding prior is multivariate normal with mean w and covariance matrix (τγ)^−1I_p.
  • Assumptions: The connection applies under a bounded-loss assumption because the PAC-Bayes bound used in the theorem is stated for bounded losses.Alternative bounds for unbounded losses require additional assumptions about empirical-risk distributions.

4. Data-dependent PAC-Bayes priors

The paper addresses data-dependent PAC-Bayes priors by using differential privacy and SGLD, yielding valid bounds under convergence assumptions. Because convergence is difficult to assess, the reported bounds are interpreted as optimistic, while longer runs tighten the theoretical guarantee.

  • Data-dependent priors: Optimizing Entropy-SGD's prior makes it sample-dependent, so the ordinary PAC-Bayes theorem no longer applies directly.Differential privacy can restore validity for a data-dependent prior, at the cost of a looser bound.
  • Private sampling: The exponential mechanism gives an idealized private sampler, but exact sampling is generally intractable, motivating approximate SGLD sampling.The local-entropy distribution is the target distribution for this private sampling view.
  • Private SGLD: SGLD can provide a valid data-dependent prior when its limiting distribution is ε-differentially private.The relevant guarantee concerns convergence in distribution to a private vector, with an additional convergence-dependent term.
  • Entropy-SGLD: Entropy-SGLD adds noise to the outer optimization loop while retaining biased inner-loop gradient estimates from SGLD.Ignoring inner-loop bias, the resulting prior supports a valid PAC-Bayes bound.
  • Convergence limitation: Longer SGLD runs yield tighter bounds, but unknown convergence rates require interpreting experimentally computed bounds as optimistic.The experiments therefore run SGLD far beyond apparent convergence and retain this qualification.

5. Numerical evaluations on MNIST

The experiments evaluate SGD, SGLD, Entropy-SGD, and Entropy-SGLD on two-class MNIST using true and random labels, comparing errors and generalization bounds. Properly tuned Entropy-SGLD achieves low test and generalization error without overfitting random labels, while the bounds remain optimistic and loose.

  • Experimental setup: The study compares several algorithms, architectures, labels, errors, and generalization bounds on MNIST.Experiments include true and random labels, fully connected and convolutional networks, and both deterministic and Gibbs classifiers.
  • Experimental setup: The CONV architecture produces the lowest training and test errors and the tightest generalization bounds.Results for FC600 and FC1200 are nearly identical despite FC1200 having three times as many parameters.
  • SGLD: At 0.05 thermal noise, SGLD achieves almost zero generalization error on true and random labels, but with relatively large risk.Higher thermal noise improves SGLD generalization while worsening risk performance.
  • Entropy-SGD: At 0.01 thermal noise, Entropy-SGD achieves good risk and low generalization error on true and random labels, though its test performance remains worse than SGD.Entropy-SGD improves the risk and generalization error of SGD at matched thermal-noise settings, while the source notes that the test-error difference is unresolved.
  • Entropy-SGLD: Entropy-SGLD yields approximately 2% test error and essentially zero generalization error on true labels, with bounds of roughly 3%.The same tuning does not overfit random labels even after thousands of epochs, but the plotted bounds assume SGLD has converged and are therefore optimistic.
  • Bounds: The PAC-Bayes bounds are generally tighter than the H- and C-bounds, nonvacuous but still loose, and exclude the term measuring distance from SGLD’s weak limit.The authors report almost no empirical violations despite this optimistic treatment.

6. Discussion

The paper interprets Entropy-SGD as optimizing a PAC-Bayes bound through its prior, but data dependence makes that bound invalid. Entropy-SGLD restores validity through private data-dependent priors, although the resulting bounds remain optimistic and performance involves substantial trade-offs.

  • Discussion: Entropy-SGD optimizes a PAC-Bayes bound through the bound’s prior, but its data-dependent prior violates the theorem’s independence requirement.The corresponding Gibbs posterior also exhibits overfitting under the paper’s experiments.
  • Discussion: Entropy-SGLD uses approximately private data-dependent priors to obtain a statistically valid PAC-Bayes bound, trading a looser privacy term for a better-matched prior.The improved prior reduces the KL term, which can offset the privacy cost.
  • Discussion: The bounds are optimistic because they omit the ε′ term under the assumption that SGLD has essentially converged.The authors interpret them as bounds that might become rigorous after advances in private optimization.
  • Discussion: Entropy-SGLD’s test error remains 5–10 times worse than SGD despite its stronger generalization guarantees.The authors also report that differential privacy may be too conservative, leading to underfitting.
  • Discussion: The paper identifies a possible tradeoff among learning speed, excess risk, and producing a rigorous generalization certificate.Entropy-SGLD learns more slowly than Entropy-SGD, while its bounds remain loose despite being tighter than existing bounds.

C.1. Architecture

The experiments use convolutional and fully connected networks trained with bounded cross-entropy and SGLD-based procedures. Privacy parameters determine the differential-privacy contribution to the PAC-Bayes bound, which is numerically 0.002 under the reported settings.

  • Architecture: The study uses CONV, FC600, and FC1200 architectures with 126,711, 834,601, and 2,385,185 parameters, respectively.CONV has two convolutional layers and a fully connected ReLU layer; FC600 and FC1200 are fully connected three-layer networks.
  • Architecture: Without batch normalization, learning rates require tuning, and the interaction between SGLD and batch normalization remains an open problem.The reported bounds with and without batch normalization are very similar.
  • Loss and training: Training minimizes a bounded cross-entropy loss, with Lmax = 4 obtained by restricting extreme probability values.The bounded transformation maps probabilities into [e^-Lmax, 1 − e^-Lmax].
  • Loss and training: Each Entropy-SG(L)D outer step contains 20 inner SGLD steps, while plot epochs are scaled to align wall-clock time with SGD.The inner and outer loops use minibatches of size K = 128.
  • Bound estimation: The PAC-Bayes bound is estimated with an additional 1000-epoch SGLD run and weighted averaging to reduce sampling variance.The inner-loop estimate uses α = 0.75, whereas bound estimation uses α = 0.005.
  • Privacy and bounds: With τ = √m, the differential-privacy contribution decays as 1/m and equals 0.002 for Lmax = 4 and β = 1.The parameters τ, Lmax, and β determine the privacy of sampling from the local-entropy distribution.

D. Multiclass MNIST experiments

The multiclass MNIST experiments reuse the general bound-evaluation setup with a fully connected network and a bounded softmax cross-entropy loss. The supplied passages primarily specify the experimental configuration rather than reporting outcomes.

  • Experimental setup: The standard MNIST experiments evaluate the same generalization bounds as the binary-labeling experiments.The results are presented in Fig. 4.
  • Architecture: The network is FC1024, a fully connected architecture with 1024 hidden units per layer.The architecture and parameters otherwise follow the MNIST setup described in Appendix C.2.
  • Loss: For multiclass classification, the network outputs a softmax probability vector and training uses bounded cross-entropy −logψ(p_y).The bounded loss replaces the ordinary −log p_y objective during private training.
  • CIFAR10 comparison: The CIFAR10 experiments train a convolutional network on both true and random labels without dropout or weight decay.The architecture matches the one used by Chaudhari et al. (2017).
  • CIFAR10 comparison: CIFAR10 results are recorded after 100 outer-loop calls, or 2000 epochs, to allow SGLD to approach its target distribution.Training error typically converges within the first part of this extended run.

E.1. Privacy parameter experiments

The privacy-parameter experiments vary τ and γ to examine generalization and bound behavior on true and random labels. Larger τ produces a phase transition and can make the privacy penalty dominate, while increasing γ shifts the transition earlier.

  • γ = 0.03: For γ = 0.03, random-label overfitting changes sharply when τ lies between 10^4 and 10^5.For smaller τ, little overfitting occurs on both true and random labels; for large τ, random labels can reach nearly zero classification error.
  • γ = 0.03: For true-label data, the generalization error remains at or below 0.2 in the reported γ = 0.03 experiments.For random labels with large Bayes error, the classifier can achieve almost zero classification error and maximal generalization error.
  • Bound behavior: At high τ, the differentially private PAC-Bayes bound is dominated by its privacy penalty and becomes effectively data independent.Consequently, it cannot capture the difference in generalization error between true and random labels.
  • γ = 3: With γ = 3, the same qualitative patterns appear, but the phase transition occurs substantially earlier.This shift causes the DP-PAC-Bayes bound to approach the C-gen bound.

E.2. Prior variance experiments

The experiments fix privacy at τβ = 2000 and vary γ, showing that γ affects optimization performance even though sampling privacy does not directly depend on it. Lower prior variance and adjusted β can improve classifiers and bounds under the same privacy level.

  • Privacy-controlled experiments: Fixing τβ = 2000 isolates γ's effect on optimization performance while holding the privacy level constant.The differential privacy of sampling from the local entropy distribution does not directly depend on γ.
  • β = 1: For β = 1, τ ∈[1,3] gives the smallest risk bound and best test-error performance across tested γ values.A value of τ < 0.01 produces excessive smoothing and poor classifiers.
  • Adjusted β: Reducing β to 0.004 permits larger τ at the same privacy level, enabling relatively good classifiers even when γ < 0.001.The change increases outer-loop noise and decreases inner-loop noise; the prior variance is (γτ)−1.

F. Related work

The paper places Entropy-SGD in work on flatness, nonvacuous bounds, differential privacy, and randomized learning algorithms. Its experiments connect these ideas to architecture comparisons and show that Entropy-SGLD can avoid overfitting in some settings while bounds remain dependent on convergence assumptions.

  • Flatness and perturbation methods: Entropy-SGD builds on regularization methods that seek weights insensitive to Gaussian perturbations or located in broad, connected low-risk regions.These earlier approaches motivate connections between noise sensitivity, description length, and flat minima.
  • Nonvacuous bounds: Entropy-SGLD yields bounds that are tighter than those of Dziugaite and Roy under the optimistic assumption that SGLD has converged.The bound value depends on the degree to which SGLD is allowed to converge.
  • Differential privacy: Differential privacy connects data-dependent priors to valid PAC-Bayes bounds, while SGLD convergence in distribution can replace computationally difficult strong privacy requirements.This line of work provides the theoretical basis for analyzing Entropy-SGLD.
  • MNIST experiments: On binarized MNIST, FC600 and FC1200 show similar training and generalization errors, with near-zero gaps and loose but nonvacuous test-error bounds.The comparison uses differentially private Entropy-SGLD on true labels.
  • Random-label behavior: On MNIST, SGLD avoids overfitting on random labels, but its C-bound is around 8%, versus roughly 4% for the mean classifier.This compares the Gibbs-related network with the mean classifier.
  • MNIST experiments: On MNIST random labels, Entropy-SGLD shows less than 1% overfitting for CONV, while FC1024 shows approximately 2% after 1000 epochs.For true labels, the generalization gap is close to zero and bounds exceed test error by slightly more than 3%.
  • CIFAR10 experiments: On CIFAR10, good classifiers can occur only where bounds are vacuous for one configuration, while larger τ increases generalization gaps and overfitting.The onset of overfitting depends on γ, occurring above τ > 2∗102 in one setting and τ > 5∗104 in another.
Loading 1712.09376v3…