A PAC-Bayesian Tutorial with A Dropout Bound

By David A. McAllester. 2013

149 citations recorded by the source corpus.

This tutorial gives a concise overview of existing PAC-Bayesian theory focusing on three generalization bounds. The first is an Occam bound which handles rules with finite precision parameters and which states that generalization loss is near training loss when the number of bits needed to write the rule is small compared to the sample size. The second is a PAC-Bayesian bound providing a generalization guarantee for posterior distributions rather than for individual rules. The PAC-Bayesian bound naturally handles infinite precision rule parameters, $L_2$ regularization, {\em provides a bound for dropout training}, and defines a natural notion of a single distinguished PAC-Bayesian posterior distribution. The third bound is a training-variance bound --- a kind of bias-variance analysis but with bias replaced by expected training loss. The training-variance bound dominates the other bounds but is more difficult to interpret. It seems to suggest variance reduction methods such as bagging and may ultimately provide a more meaningful analysis of dropouts.

Subfields: Artificial Intelligence, Statistical Learning Theory, Signal Processing

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

In Statistical Learning Theory

In Signal Processing

Citations in the corpus

To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout (2015, background): “…neural networks, there have been a series of works providing strong theoretical understanding of the dropout heuristic Baldi and Sadowski [2014], Wager et al. [2013], Wang et al. [2013], van Erven et al. [2014], Helmbold and Long [2014], Wager et al. [2014], McAllester [2013], Maaten et al. [2013].”
Deep Learning: Methods and Applications (2014, methodology): “The first is a powerful regularization technique called “dropout”; see details in [166] and a series of further analysis and improvement in [10, 13, 240, 381, 385].”
Eternal Sunshine of the Spotless Net: Selective Forgetting in Deep Networks (2019, background): “While these bounds are often loose, we introduce a novel bound on the residual information about a set of samples to be forgotten, which exploits ideas from both the stability bounds and the PAC-Bayes bounds [22], which have been successful even for DNNs [9].”
Where is the Information in a Deep Neural Network? (2019, methodology): “We start by using the PAC-Bayes bound [14] to connect the information that the weights retain about the training set to performance on the test data.”
Formal Limitations on the Measurement of Mutual Information (2018, background): “An L2 PAC-Bayesian generalization bound (McAllester, 2013) gives that for any parameterized class of models and any bounded notion of loss, and any λ > 1/2 and σ > 0, with probability at least 1 − δ over the draw of S from pX we have the following simultaneously for all parameter vectors θ.”
Emergence of Invariance and Disentanglement in Deep Representations (2017, methodology): “By Theorem 2 of McAllester (2013), we have that for any ﬁxed λ > 1 / 2, prior p ( w ), and any weight distribution q ( w”
Calibrating Noise to Variance in Adaptive Data Analysis (2017, methodology): “Our use of mutual information to derive generalization bounds is closely related to PAC-Bayes bounds first introduced by McAllester (1999) and extended in a number of subsequent works (see (McAllester, 2013) for an overview).”
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Data-dependent PAC-Bayes priors via differential privacy (2017, methodology): “Theorem 3.2 (Linear PAC-Bayes Bound (McAllester, 2013; Catoni, 2007)) .”
Risk bounds for the majority vote: from a PAC-Bayesian analysis to a learning algorithm (2015, result): “We present here the same proof as in Seldin and Tishby (2010) and McAllester (2013).”
A New PAC-Bayesian Perspective on Domain Adaptation (2015, methodology): “As mentioned by McAllester & Keshet (2011), it is, however, the case provided we consider Gaussian processes as measure of distributions ⇡”
Non-vacuous Generalization Bounds at the ImageNet Scale: a PAC-Bayesian Compression Approach (2018, methodology): “In fact, the bound stated in this section may be obtained as a simple weighted union bound, and a variation is reported in McAllester (2013).”
Entropy-SGD optimizes the prior of a PAC-Bayes bound: Generalization properties of Entropy-SGD and data-dependent priors (2017, methodology): “ a (randomized) classiﬁer on a ﬁnite discrete set of labels K. We will use the following variation of a PAC-Bayes bound, where we consider bounded loss functions. Theorem 2.1 (Linear PAC-Bayes Bound; McAllester 2013; Catoni2007). Fix l > 1=2 and assume the loss takes values in an interval of leng”
Altitude Training: Strong Bounds for Single-Layer Dropout (2014, methodology): “Binomial dropout differs slightly from the usual definition of (blankout) dropout, which alters the feature vector x by setting random coordinates to 0 [6, 9, 11, 12].”
User-friendly introduction to PAC-Bayes bounds (2021, methodology): “So it came to me recently(4) that it might be useful to write a beginner-friendly tutorial, that I could send instead! Note that there are already short tutorials on PAC-Bayes bounds, by McAllester and van Erven: [137, 193], the introductory slides by Fleuret are also very nice [73].”