Entropy-SGD optimizes the prior of a PAC-Bayes bound: Data-dependent PAC-Bayes priors via differential privacy

By Gintare Karolina Dziugaite, Daniel M. Roy. 2017

160 citations recorded by the source corpus.

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 show that an e-differentially private prior yields a valid PAC-Bayes bound, a straightforward consequence of results connecting generalization with differential privacy. Using stochastic gradient Langevin dynamics (SGLD) to approximate the well-known exponential release mechanism, we observe that generalization error on MNIST (measured on held out data) falls within the (empirically nonvacuous) bounds computed under the assumption that SGLD produces perfect samples. 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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Wireless Network Intelligence at the Edge (2018, methodology): “Utilizing this idea, it is possible to characterize the dependency between Dn and p via the differential privacy framework [140], yielding the following PACBayes bound”
User-friendly introduction to PAC-Bayes bounds (2021, methodology): “2 in [71]) Assume we have a function Π that maps any sample s = ((x1, y1), .”
Deep learning generalizes because the parameter-function map is biased towards simple functions (2018, background): “…by Zhang et al. (2016) also clearly demonstrated point 2), which spurred a wave of new work in learning theories tailored to deep learning (Kawaguchi et al. (2017); Arora et al. (2018); Morcos et al. (2018); Neyshabur et al. (2017b); Dziugaite & Roy (2017; 2018); Neyshabur et al. (2017a; 2018)).”
Deep neural networks are biased towards simple functions (2018, background): “…PAC-Bayesian generalization bounds, which apply to nondeterministic learning algorithms and depend on the probability distribution of the weights that the algorithm returns given the training set [McAllester, 1999,Catoni, 2007, Lever et al., 2013, Dziugaite and Roy, 2018, Neyshabur et al., 2017b].”
Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimates (2019, methodology): “The idea of using data-dependent priors to obtain tighter bounds is standard in the PAC-Bayes literature [2, 10, 22, 27], but its utility in the present work is brought through by our introduction of data-dependent estimates.”
Fast Convergence of Natural Gradient Descent for Overparameterized Neural Networks (2019, background): “Researchers have proposed norm-based generalization bounds [Neyshabur et al., 2015, 2017, Bartlett and Mendelson, 2002, Bartlett et al., 2017, Golowich et al., 2017], compression bounds [Arora et al., 2018] and PAC-Bayes bounds [Dziugaite and Roy, 2017, 2018, Zou et al., 2018].”
Bayesian Counterfactual Risk Minimization (2018, methodology): “This type of prior, known as distribution-dependent, was introduced by Catoni [4] and later developed by others [17, 23, 24, 9] to obtain tight PAC-Bayesian bounds.”