PaperlayerView exact revision on arXiv

Source-linked AI summary

A PAC-Bayesian Tutorial with A Dropout Bound

David McAllester

arXiv:1307.2118v1cs.LG

TL;DR

The tutorial addresses how PAC-Bayesian theory can provide interpretable generalization guarantees across finite-precision rules, posterior distributions, and learning-algorithm variance. It surveys three bounds and their extensions, finding that the training-variance bound dominates the others but is harder to interpret and lacks a known optimal algorithm.

  • Problem

    PAC-Bayesian theory requires a unified understanding of generalization guarantees for individual rules, posterior distributions, and learning-algorithm variance, including settings with infinite precision and dropout.

  • Method

    The tutorial develops a concise overview of Occam, PAC-Bayesian, and training-variance bounds, plus applications to sparse coding, regularization, dropout, and bound refinements.

  • Results

    The training-variance bound dominates the Occam and PAC-Bayesian bounds, while PAC-Bayesian analysis handles infinite-precision parameters, L2 regularization, and dropout.

  • Takeaways & Limitations

    The training-variance bound may motivate variance-reduction methods such as bagging, but its consequences remain insufficiently understood.

  • Takeaways & Limitations

    No optimal algorithm is known for the training-variance bound, and applying it to the PAC-Bayesian posterior suffers from looseness.

Abstract

from arXiv · show

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.

1 Introduction

The tutorial surveys three PAC-Bayesian generalization bounds: Occam, PAC-Bayesian, and training-variance bounds. It also discusses clarifications and improvements, while noting that tighter Occam analyses have fundamentally limited gains and training-variance bounds remain difficult to interpret.

  • 1 Introduction: PAC-Bayesian theory separates the learner’s prior weighting over rules from nature’s distribution over situations.Its guarantees concern performance when rules are stochastically selected from a posterior distribution.
  • 1 Introduction: The tutorial focuses on three bounds: Occam for individual rules, PAC-Bayesian for posterior distributions, and training-variance for expected generalization loss.The training-variance bound replaces bias with expected training loss and incorporates output variance.
  • 1 Introduction: PAC-Bayesian bounds handle infinite-precision parameters, L2 regularization, and a form of dropout learning.They govern loss when rules are stochastically selected from a PAC-Bayesian posterior.
  • 1 Introduction: The training-variance bound dominates the PAC-Bayesian and Occam bounds but is more difficult to interpret.It appears to suggest variance-reduction methods such as bagging.
  • 1 Introduction: The tutorial applies training-variance analysis to the PAC-Bayesian posterior and tightens the Occam bound using loss variance.The training-variance application suffers from looseness, while gains from the Occam improvement are fundamentally limited.

2 An Occam Bound

The Occam bound gives simultaneous generalization guarantees for individual rules in a discrete rule set. Its complexity term can reflect the bits needed to encode finite-precision parameters, including sparse representations, although PAC-Bayesian bounds better handle infinite precision.

  • 2 An Occam Bound: The Occam bound simultaneously controls generalization loss for all individual rules in a countable rule set.The guarantee holds with probability at least 1−δ over an IID sample and depends on the prior probability assigned to each rule.
  • 2 An Occam Bound: The Occam bound’s tuning parameter need not be large: restricting λ below 10 increases the bound by at most a factor of 20/19.For practical purposes, λ can therefore be assumed no larger than 10.
  • 2.1 Finite Precision Bounds: For finite-precision parameter vectors in d dimensions with b-bit components, a uniform prior can cover 2^bd possible rules.This converts parameter precision into a rule-complexity term in the Occam guarantee.
  • 2.1 Finite Precision Bounds: Sparse finite-precision parameter vectors can be encoded by specifying sparsity and listing nonzero component indices and values.The construction assigns probability 2^−|h| based on the number of bits needed to name a rule.
  • 2.1 Finite Precision Bounds: The tutorial presents the Occam bound mainly for conceptual simplicity because PAC-Bayesian bounds handle infinite-precision parameters and are generally preferable.More sophisticated classifier codings, including variable-precision codes, are also possible.

3 A PAC-Bayesian Bound

The PAC-Bayesian bound controls expected loss for posterior distributions, using empirical posterior loss and KL divergence from a prior. The tutorial applies it to infinite-precision, scale-invariant classifiers and derives bounds for L2-style objectives and dropout training.

  • 3 A PAC-Bayesian Bound: The bound uniformly controls posterior generalization loss using empirical posterior loss and KL divergence from the prior.Q represents a stochastic process that samples rules, while D(Q, P) is the KL divergence from posterior Q to prior P.
  • 3.1 An Infinite Precision L2 Bound: For scale-invariant rules, an isotropic Gaussian prior represents uniform directions, while Q_Θ is a Gaussian centered on Θ.The rule depends only on the direction of its parameter vector, so the Gaussian distributions are interpreted over directions.
  • 3.2 Binary and Multi-Class classification: The resulting objective is similar to a support vector machine objective, replacing hinge loss with a non-convex sigmoidal loss.At test time, the deterministic rule h_Θ uses Θ, the mean of Q_Θ.
  • 3.3 Dropouts: The tutorial derives a dropout PAC-Bayesian bound by using Q_α,0 as the prior and Q_α,Θ as the posterior.Dropout samples coordinates as zero with probability α and otherwise uses Θ_i plus Gaussian noise.
  • 3.3 Dropouts: A dropout rate α reduces the complexity cost by a factor of 1 − α, although small α is expected to produce large posterior training loss.The bound can be optimized by stochastic gradient descent.
  • 3 A PAC-Bayesian Bound: For finite rule spaces, the bound has a closed-form minimizing posterior, yielding a distinguished PAC-Bayesian posterior for a fixed regularization parameter.The posterior depends strongly on the choice of Lmax.

4 A Training-Variance Bound

The training-variance bound controls expected generalization loss using expected training loss and variation in a learning algorithm’s output. It dominates the PAC-Bayesian alternative when the divergence from the average posterior is large, but its optimal algorithm is unknown.

  • The training-variance bound upper-bounds expected generalization loss using expected training loss and variation in the algorithm’s output over samples.It applies to any fixed learning algorithm that maps a sample to a rule distribution.
  • Unlike the PAC-Bayesian bound, the training-variance bound has no known solution for its optimal learning algorithm.
  • The analysis motivates variance-reduction methods such as bagging, although the bound remains difficult to interpret.
  • The bound dominates the PAC-Bayesian bound and is especially stronger when the divergence between the average posterior and prior is large.

5 Applying the Training-Variance Bound to the PAC-Bayesian Posterior

Applying the training-variance analysis to the PAC-Bayesian posterior yields bounds, but the analysis is acknowledged to be loose. The PAC-Bayesian posterior optimizes its own bound, not necessarily the training-variance bound.

  • The PAC-Bayesian posterior Qλ(S) is used as the learning algorithm for applying the training-variance bound.
  • The resulting analysis is somewhat loose, and Qλ(S) is unlikely to optimize the training-variance bound.
  • The derivation combines PAC-Bayesian inequalities and parameter choices to obtain bounds on the expected loss of Qλ(S).
  • Although replacing the prior with the average posterior should significantly improve the bound, a further replacement makes it vacuous after inserting the preceding inequality.

6 Incorporating Empirical Loss Variance

Empirical loss variance can tighten generalization bounds, but even the zero-variance case has a fundamental limitation. The resulting bound is not substantially better than the general Occam bound.

  • The section motivates variance-sensitive bounds by asking whether empirical loss variance can yield tighter guarantees.
  • A union bound over the prior yields a guarantee that holds simultaneously for all rules.
  • Even when empirical loss variance is zero, unseen outliers prevent a union-bound analysis from ruling out losses as large as Lmax.
  • The variance-sensitive bound is not significantly tighter than the general Occam bound, differing by at most a factor of two in the stated comparison.

7 Conclusion

The tutorial presents the Occam and PAC-Bayesian bounds mainly as foundations for the stronger training-variance bound. That bound suggests variance reduction but remains theoretically underexplained.

  • The training-variance bound dominates the Occam and PAC-Bayesian bounds, which primarily provide its conceptual proof foundation.
  • The bound suggests variance-reduction methods such as boosting, but no analogous optimal algorithm is known and its consequences remain insufficiently understood.

A Proof of Theorem 2

The proof of Theorem 2 combines a Bernoulli-divergence formulation with exponential-moment bounds, convexity, a shift-of-measure lemma, and Markov’s inequality to obtain a simultaneous high-probability statement for all distributions Q.

  • A Proof of Theorem 2: The appendix proofs are adapted from Catoni except for the proof of Theorem 6.Theorem 6 is described as straightforward.
  • A Proof of Theorem 2: Theorem 2 holds simultaneously for all distributions Q on H with probability at least 1 − δ when λ > 1/2 is fixed before sampling.The theorem’s probability is over the draw of the sample.
  • A Proof of Theorem 2: The proof restricts the loss to Lmax = 1 and defines D(q, p) as the divergence between Bernoulli variables with biases q and p.The general bounded-loss case follows by rescaling the loss function.
  • A Proof of Theorem 2: For bounded random variables, convexity of the exponential yields an exponential-moment bound for the empirical mean of N independent draws.The argument uses e^(γx) ≤ 1 − x + xe^γ for x in [0,1].
  • A Proof of Theorem 2: The proof converts the moment inequality into a divergence inequality and applies Markov’s inequality to obtain a probability statement over the sample.The derivation also uses a shift-of-measure lemma and convexity of Dγ.
  • A Proof of Theorem 2: Joint convexity of Dγ and an intermediate lemma complete the implication to Theorem 2.The supplied proof text includes an additional algebraic condition involving λ and c.

B Proof of Theorem 4

The proof of Theorem 4 modifies the proof of Theorem 2 by applying the shift-of-measure lemma, then uses expectations and convexity/concavity properties to derive the result.

  • B Proof of Theorem 4: The theorem’s setup concerns a distribution P on rules, an algorithm A, and λ > 1.
  • B Proof of Theorem 4: The proof is a slight modification of Theorem 2’s proof and begins by applying the shift-of-measure lemma for any fixed sample S.
  • B Proof of Theorem 4: Taking expectations over S and using convexity of Dγ together with concavity of the logarithm produces the required intermediate inequality.
  • B Proof of Theorem 4: Theorem 4 follows from the earlier inequality (17) and Lemma 2.

C Proof of (10) and (13)

The proof derives the relevant bound from the log-partition function’s convexity and then applies Hoeffding’s inequality because λ is selected before the sample is drawn.

  • C Proof of (10) and (13): The proof begins by introducing equation (10) as the next expression in the derivation.
  • C Proof of (10) and (13): Convexity of the log-partition function supplies the key inequality used in the proof.
  • C Proof of (10) and (13): Because λ is chosen before sampling, Hoeffding’s bound controls L(Qλ) − Lhat(Qλ) with probability at least 1 − δ.

D Proof of Theorem 6

The proof of Theorem 6 treats zero empirical variance by identifying outliers relative to a target loss and bounding their rate through a realizable-analysis argument and a union bound.

  • D Proof of Theorem 6: Theorem 6 provides a high-probability statement for all rules h with empirical variance sigma-hat^2(h) = 0.The supplied theorem statement specifies probability at least 1 − δ over the sample.
  • D Proof of Theorem 6: For each rule, the first sample defines a target loss, and later samples are outliers when their losses differ from that target.
  • D Proof of Theorem 6: The proof bounds the outlier probability using a realizable-analysis argument on the remaining sample.The outlier probability is denoted µ(h).
  • D Proof of Theorem 6: A union bound over rules weighted by P(h) shows that, with high probability, the claimed condition holds simultaneously for all zero-variance rules.
  • D Proof of Theorem 6: For a fixed rule, observing zero empirical variance over N − 1 samples has probability at most e^(-(N−1)µ(h)).
Loading 1307.2118v1…