---
kind: concept
slug: pac-bayes-bound
title: PAC-Bayes bound
summary: >-
  A PAC-Bayes bound gives a high-probability limit on a posterior's true error, set by a prior, a posterior and the training-set size. The only card here uses a Gaussian-process prior over functions to bound realizable networks on binarized MNIST, fashion-MNIST and CIFAR10. The bounds track author-reported test error, but the key assumption about SGD is unverified.
tags: [generalization, pac-bayes, bounds]
papers: ["1805.08522"]
related: [gaussian-process, bayesian-neural-network, inductive-bias, implicit-bias-of-gradient-descent]
status: draft
updated_at: 2026-11-03
---

## 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 [arxiv:1805.08522 §5] [arxiv:1805.08522 eq. 2].
The theorem and its realizable corollary come from earlier work by Langford and
Seeger and by McAllester [arxiv: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 [arxiv:1805.08522 §5].
The bound then depends on P(U), the prior probability that the training labels
occur [arxiv:1805.08522 §5]. The authors estimate P(U) with a Gaussian-process
approximation [arxiv: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 [arxiv:1805.08522 §5]. The paper's experiments use the realizable
corollary below, not this form [arxiv:1805.08522 §6]. Card:
[Valle-Pérez et al. (2018)](/papers/1805.08522).

### 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)
[arxiv:1805.08522 §5]. The corollary bounds −ln(1 − ε(Q*)) by
(ln(1/P(U)) + ln(2m/δ))/(m−1) [arxiv:1805.08522 §5, cor. 1].

The kernel comes from the infinite-width limit of the network, which is a
Gaussian process [arxiv: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. [arxiv:1805.08522 §5.1].
The labels are modelled with a Bernoulli likelihood and a probit link, and the
evidence is computed with expectation propagation [arxiv:1805.08522 §5.1]
[arxiv:1805.08522 app. A].

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

| Network | MNIST error | MNIST bound | fashion-MNIST error | fashion-MNIST bound | CIFAR10 error | CIFAR10 bound |
|---|---|---|---|---|---|---|
| CNN (4 layers) | 0.023 | 0.134 | 0.071 | 0.175 | 0.320 | 0.485 |
| FC | 0.031 | 0.169 | 0.070 | 0.188 | 0.341 | 0.518 |

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
[arxiv:1805.08522 §6] [arxiv:1805.08522 fig. 3]. Card:
[Valle-Pérez et al. (2018)](/papers/1805.08522).

## When to use which

| Situation | Use | Why |
|---|---|---|
| Labels can be fit exactly (zero training error reachable) | Realizable corollary | The corollary assumes this; the paper trains to 100% training accuracy [arxiv:1805.08522 §5] [arxiv:1805.08522 app. A] |
| Noisy labels, or training cannot reach zero error | General KL form, if you can compute KL(Q‖P) | The corollary's assumption fails. The paper gives no numbers for this form [arxiv:1805.08522 §5] |
| Fully connected ReLU network | Arc-cosine kernel in closed form | Kernel is available without extra code [arxiv:1805.08522 §5.1] |
| Convolutional network | Needs a CNN GP kernel implementation | The paper relies on external kernel code [arxiv:1805.08522 §5.1]; the authors' repository does not include the GP code (see [Valle-Pérez et al. (2018)](/papers/1805.08522)) |
| Need a number you can report | Set δ yourself and state it | The paper does not state δ [arxiv:1805.08522 tab. 1] |
| Evaluating the bound on a large training set | Budget for an m×m kernel and EP | Computation cost is not stated [arxiv:1805.08522 §5.1] |

Caveats that change the bound:

- **Variances dominate.** σ_w and σ_b change the bound a lot [arxiv:1805.08522 app. C]. The paper used σ_w = σ_b = 1 for the CNN and 10 for the FC net [arxiv:1805.08522 fig. 3], chosen "above the phase transition"; the exact rule is not stated [arxiv:1805.08522 app. C].
- **Approximation bias.** EP "appears to overestimate probabilities" [arxiv: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 [arxiv:1805.08522 §5].
- **Unverified assumption.** The bound needs SGD to sample the zero-error region close to uniformly [arxiv: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 [arxiv:1805.08522 §7] [arxiv: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 [arxiv:1805.08522 §5].

```pseudocode
# 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
[arxiv:1805.08522 §5.1] [arxiv: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" [arxiv:1805.08522 §4]. The authors' code uses variance σ_w²/n, which is the GP convention [arxiv: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) [arxiv:1805.08522 §3]. The appendix uses 2^(−(aK̃ + b)) [arxiv:1805.08522 app. F]. The two forms are not equivalent.
- **Depth of the FC net.** Figure 3 says one hidden layer [arxiv:1805.08522 fig. 3]. Table 1 says "1 layer FC" [arxiv:1805.08522 tab. 1]. The appendix caption says a two-layer FC net [arxiv:1805.08522 app. C].
- **Training-set size for the SGD-vs-ABI check.** The text gives 118 [arxiv:1805.08522 app. D]; the code uses 64 (see the card).

## Papers

- [Valle-Pérez et al. (2018)](/papers/1805.08522): 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.