PAC-Bayes bound

Overview

A PAC-Bayes bound limits the true error of a posterior distribution Q over hypotheses. The limit is set by a prior P, the training-set size m and a confidence level δ. With probability at least 1 − δ, a KL-type inequality between the empirical error and the true error of Q holds, with KL(Q‖P) and ln(2m/δ) on the right-hand side 1805.08522 §5 1805.08522 eq. 2. The theorem and its realizable corollary come from earlier work by Langford and Seeger and by McAllester 1805.08522 §5.

The one card here uses a different prior. It is placed on functions, not on parameters: sample random parameters, map each sample to the function it computes, and use the distribution over functions as P 1805.08522 §5. The bound then depends on P(U), the prior probability that the training labels occur 1805.08522 §5. The authors estimate P(U) with a Gaussian-process approximation 1805.08522 §5.1.

Variants

General KL form over a posterior

The inequality for any posterior Q, written as a binary-KL between empirical error and true error, bounded by (KL(Q‖P) + ln(2m/δ))/(m−1) [arxiv:1805.08522 eq. 2]. The paper uses it as the starting point, and the card notes that its right-hand side can be inverted to bound the true error, without giving a procedure 1805.08522 §5. The paper's experiments use the realizable corollary below, not this form 1805.08522 §6. Card: Valle-Pérez et al. (2018).

Realizable corollary with a Gaussian-process prior over functions

Assumes zero training error is achievable. The posterior is the prior restricted to labellings that agree with the training set, normalised by P(U) 1805.08522 §5. The corollary bounds −ln(1 − ε(Q*)) by (ln(1/P(U)) + ln(2m/δ))/(m−1) 1805.08522 §5, cor. 1.

The kernel comes from the infinite-width limit of the network, which is a Gaussian process 1805.08522 §5.1. For fully connected ReLU networks the kernel has a closed form (arc-cosine kernel). For convolutional networks the authors use kernel code from Garriga-Alonso et al. 1805.08522 §5.1. The labels are modelled with a Bernoulli likelihood and a probit link, and the evidence is computed with expectation propagation 1805.08522 §5.1 1805.08522 app. A.

The paper reports the following author-reported bounds with 10000 training examples and training error 0 1805.08522 tab. 1:

The label-corruption sweep shows bounds that follow the trend of the measured error, and P(U) falls by many orders of magnitude as corruption grows 1805.08522 §6 1805.08522 fig. 3. Card: Valle-Pérez et al. (2018).

When to use which

Caveats that change the bound:

• Variances dominate. σ_w and σ_b change the bound a lot 1805.08522 app. C. The paper used σ_w = σ_b = 1 for the CNN and 10 for the FC net 1805.08522 fig. 3, chosen "above the phase transition"; the exact rule is not stated 1805.08522 app. C.
• Approximation bias. EP "appears to overestimate probabilities" 1805.08522 app. D. Since a larger P(U) lowers the right-hand side of cor. 1, an overestimate makes the bound look tighter than it is 1805.08522 §5.
• Unverified assumption. The bound needs SGD to sample the zero-error region close to uniformly 1805.08522 §5. The evidence is on a 7-input Boolean network, and the correlation depends on σ: ρ = 0.99 at σ = 10, but ρ = 0.72 (advSGD) and 0.66 (Adam) at σ = 1 1805.08522 §7 1805.08522 app. D.

Implementation sketch

The steps follow the paper's realizable bound. The inversion in the last step is ours: the paper states that the bound can be inverted but gives no procedure 1805.08522 §5.

# Realizable PAC-Bayes bound with a GP prior over functions  [arxiv:1805.08522 §5.1]
# inputs: m training inputs labelled with zero training error; sigma_w, sigma_b; delta

def pac_bayes_realizable_bound(inputs, labels, sigma_w, sigma_b, delta):
    m = len(inputs)
    # Evidence P(U): marginal likelihood of the labels under the GP prior  [§5.1]
    log_p_u = gp_log_marginal(inputs, labels, sigma_w, sigma_b)
    # Right-hand side of the corollary  [arxiv:1805.08522 §5, cor. 1]
    r = (-log_p_u + log(2 * m / delta)) / (m - 1)
    # Invert -ln(1 - eps) <= r; this step is not in the paper  [§5]
    return 1 - exp(-r)

gp_log_marginal computes the kernel over the training inputs, then the expectation-propagation log evidence with a Bernoulli probit likelihood 1805.08522 §5.1 1805.08522 app. A.

Contradictions

None known across papers: only one card cites this slug. Inside the source, the paper disagrees with itself or with its code on several points:

• Weight variance. The text says "variance 1/√n" 1805.08522 §4. The authors' code uses variance σ_w²/n, which is the GP convention 1805.08522 §5.1. The card's Paper vs code section lists the details.
• Sign of b. Eq. 1 in the main text uses 2^(−aK̃ + b) 1805.08522 §3. The appendix uses 2^(−(aK̃ + b)) 1805.08522 app. F. The two forms are not equivalent.
• Depth of the FC net. Figure 3 says one hidden layer 1805.08522 fig. 3. Table 1 says "1 layer FC" 1805.08522 tab. 1. The appendix caption says a two-layer FC net 1805.08522 app. C.
• Training-set size for the SGD-vs-ABI check. The text gives 118 1805.08522 app. D; the code uses 64 (see the card).

Papers

• Valle-Pérez et al. (2018): applies a PAC-Bayes realizable bound with a Gaussian-process prior over functions to binarized image datasets, and reports bounds that move with author-reported test error.