Module 12. Information-theoretic generalization bounds: PAC-Bayes and mutual information

Exercise 1. Proving PAC-Bayes-kl

Reconstruct the proof from Section 12.4.

Start from
$\mathbb E_S e^{n\operatorname{kl}(\widehat L_S(w)\|L(w))} \le2\sqrt n$
for fixed $w$ .
Integrate over $P$ and apply Markov's inequality.
Use the change-of-measure inequality
$\mathbb E_QF \le D_{\mathrm{KL}}(Q\|P) + \ln\mathbb E_Pe^F.$
Apply joint convexity of binary KL.
Identify exactly where independence of $P$ from $S$ is required.

Show answer and solution

Let

F_S(w) = n\operatorname{kl} \bigl( \widehat L_S(w)\|L(w) \bigr).

For each fixed $w$ , Maurer's exponential-moment inequality gives

\mathbb E_S e^{F_S(w)} \le 2\sqrt n.

Because the prior $P$ is independent of $S$ , expectations can be exchanged:

\mathbb E_S \mathbb E_{W\sim P} e^{F_S(W)} = \mathbb E_{W\sim P} \mathbb E_S e^{F_S(W)} \le 2\sqrt n.

Markov's inequality implies that, with probability at least $1-\delta$ ,

\mathbb E_{W\sim P} e^{F_S(W)} \le \frac{2\sqrt n}{\delta}.

Fix a sample for which this event holds. For every posterior $Q$ , the change-of-measure inequality gives

\mathbb E_QF_S(W) \le D_{\mathrm{KL}}(Q\|P) + \ln\mathbb E_Pe^{F_S(W)}.

Therefore,

\mathbb E_QF_S(W) \le D_{\mathrm{KL}}(Q\|P) + \ln\frac{2\sqrt n}{\delta}.

Binary KL is jointly convex, so

\begin{aligned} &n\operatorname{kl} \bigl( \widehat L_S(Q)\|L(Q) \bigr)\\ &=n\operatorname{kl} \left( \mathbb E_Q\widehat L_S(W) \middle\| \mathbb E_QL(W) \right)\\ &\le n\mathbb E_Q \operatorname{kl} \bigl( \widehat L_S(W)\|L(W) \bigr)\\ &= \mathbb E_QF_S(W). \end{aligned}

Combining the inequalities and dividing by $n$ gives

\operatorname{kl} \bigl( \widehat L_S(Q)\|L(Q) \bigr) \le \frac{ D_{\mathrm{KL}}(Q\|P) + \ln\dfrac{2\sqrt n}{\delta} }{n}.

Where independence of the prior is used

The critical equality is

\mathbb E_S\mathbb E_{W\sim P}e^{F_S(W)} = \mathbb E_{W\sim P}\mathbb E_Se^{F_S(W)}.

If $P=P_S$ is chosen from the same sample, then inside the first expectation the law of $W$ changes together with $S$ . The fixed-hypothesis exponential-moment inequality can no longer be applied without an additional charge for the data dependence of the prior.

Exercise 2. Zero empirical error

Suppose

\operatorname{kl}(0\|L(Q))\le c.

Show that
$L(Q)\le1-e^{-c}.$
Compare it with
$L(Q)\le\sqrt{c/2}.$
Evaluate both bounds at $c=0.01$ .
Explain why exact inversion matters when training risk is nearly zero.

Show answer and solution

For $a=0$ , binary KL equals

\operatorname{kl}(0\|b) = -\ln(1-b).

Hence

-\ln(1-L(Q))\le c

implies

\ln(1-L(Q))\ge-c,

1-L(Q)\ge e^{-c},

and finally

\boxed{ L(Q)\le1-e^{-c} }.

For small $c$ ,

1-e^{-c} =c-\frac{c^2}{2}+O(c^3) \approx c.

Pinsker gives only

L(Q) \le \sqrt{c/2}.

At $c=0.01$ , for example,

1-e^{-0.01} \approx0.00995,

whereas

\sqrt{0.01/2} \approx0.0707.

The difference is almost sevenfold. For models with zero or near-zero training error, the binary-KL bound should therefore not be replaced by its square-root corollary without a reason.

Exercise 3. A Gaussian posterior and $L_2$

For

P=\mathcal N(0,\sigma_P^2I), \qquad Q=\mathcal N(\mu,\sigma_Q^2I),

derive $D_{\mathrm{KL}}(Q\|P)$ .

Isolate the term proportional to $\|\mu\|^2$ .
Explain the role of the variance terms.
Explain why this establishes a connection to $L_2$ regularization but not full equivalence with ordinary deterministic weight decay.

Show answer and solution

For

P=\mathcal N(0,\sigma_P^2I_d), \qquad Q=\mathcal N(\mu,\sigma_Q^2I_d)

the Gaussian KL formula gives

\begin{aligned} D_{\mathrm{KL}}(Q\|P) &= \frac12 \left[ \operatorname{tr} (\sigma_P^{-2}I_d\,\sigma_Q^2I_d) + \mu^T(\sigma_P^{-2}I_d)\mu -d + \ln\frac{\det(\sigma_P^2I_d)}{\det(\sigma_Q^2I_d)} \right]\\ &= \frac12 \left[ d\frac{\sigma_Q^2}{\sigma_P^2} + \frac{\|\mu\|^2}{\sigma_P^2} -d + d\ln\frac{\sigma_P^2}{\sigma_Q^2} \right]. \end{aligned}

That is,

\boxed{ D_{\mathrm{KL}}(Q\|P) = \frac{\|\mu\|^2}{2\sigma_P^2} + \frac d2 \left( \frac{\sigma_Q^2}{\sigma_P^2} -1 + \ln\frac{\sigma_P^2}{\sigma_Q^2} \right) }.

The first term does have the form of an $L_2$ penalty. But the complete PAC-Bayes objective also contains:

a variance term;
the empirical Gibbs risk, rather than the loss of a network with mean weights;
the scale $1/(\lambda n)$ ;
a confidence term inside the certificate itself;
a validity requirement on the prior.

Ordinary deterministic weight decay is therefore related to the Gaussian PAC-Bayes penalty, but not identical to the whole procedure.

Exercise 4. Adaptive selection and MI

There are $M$ hypotheses with identical Bernoulli population loss $p$ . On a sample of size $n$ , the algorithm selects the hypothesis with the smallest empirical loss.

Why is the winner's expected empirical loss at most $p$ ? Give an example of equality and a sufficient condition for a strict decrease.
If selection is deterministic, why is
$I(W;S)=H(W)\le\ln M?$
For losses in $[0,1]$ , derive
$|\mathbb E\operatorname{gen}| \le \sqrt{\frac{\ln M}{2n}}.$
What changes under tempered Gibbs selection?

Show answer and solution

Every hypothesis has the same population risk $p$ , while its empirical risk is random. Taking the minimum cannot increase the expected estimate:

\mathbb E \left[ \min_j\widehat L_j \right] \le \min_j \mathbb E[\widehat L_j] =p.

Equality is possible even when $0<p<1$ . Suppose all hypotheses incur the same loss on each observation, with independent Bernoulli $(p)$ losses across observations. Then all $\widehat L_j$ coincide, and their minimum has expectation $p$ . With a fixed tie-breaking rule, such as choosing the smallest index, $W$ is constant and $I(W;S)=0$ .

A sufficient condition for a strict decrease is $M>1$ , $n\ge1$ , $0<p<1$ , and independent Bernoulli losses across candidates and observations. The event that the first candidate has loss 1 on every observation while the second has loss 0 on every observation then has positive probability. On that event, $\min_j\widehat L_j<\widehat L_1$ ; on every other outcome, the minimum is at most $\widehat L_1$ . Its expectation is therefore strictly below $p$ .

If the selection $W=A(S)$ is deterministic, then

H(W\mid S)=0.

Consequently,

I(W;S) =H(W)-H(W\mid S) =H(W).

Since $W$ takes at most $M$ values,

H(W) \le \ln M.

For a loss in $[0,1]$ the MI bound may use $\sigma^2=1/4$ :

|\mathbb E\operatorname{gen}| \le \sqrt{ \frac{2(1/4)I(W;S)}{n} } \le \sqrt{ \frac{\ln M}{2n} }.

Temperature-controlled Gibbs selection defines the distribution

Q_S(j) \propto \exp \left( -\frac{\widehat L_j(S)}{\tau} \right).

As $\tau\to0$ it approaches argmin, and as $\tau\to\infty$ it approaches an almost uniform choice. Raising the temperature increases

H(W\mid S),

which lowers

I(W;S)=H(W)-H(W\mid S).

The price is a less aggressive use of the empirical fit.

Exercise 5. The exact average-KL decomposition

Prove

\mathbb E_S D_{\mathrm{KL}}(Q_S\|P) = I(W;S) + D_{\mathrm{KL}}(P_W\|P).

Then answer the following.

Which $P$ minimizes the left side on average?
Why is it called an oracle prior?
Under what knowledge would it be theoretically admissible in the standard theorem?
Why can it not be estimated from the same sample without a correction?

Show answer and solution

Let

Q_S=P_{W\mid S},

and let $P_W$ be the marginal law of $W$ . Then

\begin{aligned} \mathbb E_S D_{\mathrm{KL}}(Q_S\|P) &= \mathbb E_{S,W} \ln\frac{dQ_S}{dP}(W)\\ &= \mathbb E_{S,W} \left[ \ln\frac{dQ_S}{dP_W}(W) + \ln\frac{dP_W}{dP}(W) \right]\\ &= I(W;S) + D_{\mathrm{KL}}(P_W\|P). \end{aligned}

The second term is nonnegative, so the minimum over $P$ is attained at

\boxed{P=P_W}.

Then

\mathbb E_S D_{\mathrm{KL}}(Q_S\|P_W) = I(W;S).

This distribution is called an oracle prior, because building it generally requires the law of the algorithm output over all datasets drawn from the unknown data distribution $\mathcal D$ .

Unavailability should not be confused with invalidity. If $\mathcal D$ and the conditional law $P_{W\mid S}$ of the algorithm were known, then the marginal

P_W(dw) = \int P_{W\mid S=s}(dw)\,P_S(ds)

would be defined before the realized certification sample is observed. In that idealized setting, $P_W$ is a fixed and theoretically admissible prior for the standard PAC-Bayes theorem.

In practice $\mathcal D$ is unknown, which invites estimating $P_W$ from the current sample and substituting that estimate into the certificate. This is a different object: the prior then depends on the certification data. It requires a separate argument—sample splitting, a hierarchical construction, a differential-privacy correction, or a theorem designed for data-dependent priors.

Exercise 6. Python: selection bias and a PAC-Bayes certificate

Run

text

M12_generalization_experiments.py

The script performs two experiments.

Adaptive selection among 32 equally good hypotheses:
- compare selection bias with the MI bound;
- track the effect of temperature;
- verify the exact average-KL decomposition.
A stochastic linear classifier:
- compare empirical Gibbs risk, diagnostic test risk, and the PAC-Bayes-kl certificate;
- find the posterior variance that minimizes the certificate;
- compare exact binary-KL inversion with the square-root corollary.

Explain why test risk is not part of the certificate.

Show answer and solution

The script reproduces two experiments.

Part 1. Adaptive selection

For argmin:

I(W;S) \approx3.2351\text{ nats},

\mathbb E\operatorname{gen} \approx0.0874,

and the MI bound is about

0.1422.

At temperature $\tau=0.05$ :

I(W;S) \approx0.3382,

\mathbb E\operatorname{gen} \approx0.0351,

\text{MI bound} \approx0.0460.

At $\tau=0.5$ both the mutual information and the gap become almost zero, because the algorithm has nearly stopped choosing the winner from the data.

For $\tau=0.05$ the script also checks

\mathbb E_S KL(Q_S\|P) = I(W;S)+KL(P_W\|P)

to within Monte Carlo noise.

Part 2. A stochastic linear classifier

The best posterior standard deviation among those tested is

\sigma_Q=0.1.

For it:

\widehat L_S(Q) \approx0.2273,

L_{\mathrm{test}}(Q) \approx0.2254,

D_{\mathrm{KL}}(Q\|P) \approx12.6653\text{ nats},

\text{PAC-Bayes-kl certificate} \approx0.2715.

The square-root Pinsker corollary gives about

0.2780,

that is, a slightly weaker result.

Test risk does not enter the certificate. It is used only to check how conservative the certificate is in a synthetic world where a large independent test set can be generated.

Code solution · the same source file for RU/EN

PythonM12_generalization_experiments.pyDownload .py

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305

from __future__ import annotations

from pathlib import Path
import json
import math

import matplotlib
matplotlib.use("Agg")
import matplotlib.pyplot as plt
import numpy as np
from scipy.special import expit, ndtr

ROOT = Path(__file__).resolve().parent
OUT = ROOT / "generated_experiment"
OUT.mkdir(exist_ok=True)
SEED = 202612


def binary_kl(q: float, p: float) -> float:
    """Bernoulli KL kl(q || p), in nats."""
    eps = 1e-15
    q = float(np.clip(q, eps, 1 - eps))
    p = float(np.clip(p, eps, 1 - eps))
    return q * math.log(q / p) + (1 - q) * math.log((1 - q) / (1 - p))


def kl_upper_inverse(q: float, c: float) -> float:
    """Largest p in [q,1] such that kl(q || p) <= c."""
    if c <= 0:
        return float(q)
    lo = float(q)
    hi = 1.0 - 1e-12
    if binary_kl(q, hi) <= c:
        return 1.0
    for _ in range(100):
        mid = 0.5 * (lo + hi)
        if binary_kl(q, mid) <= c:
            lo = mid
        else:
            hi = mid
    return lo


def softmax_rows(logits: np.ndarray) -> np.ndarray:
    shifted = logits - np.max(logits, axis=1, keepdims=True)
    weights = np.exp(shifted)
    return weights / np.sum(weights, axis=1, keepdims=True)


def experiment_adaptive_selection() -> dict:
    """Adaptive selection among equally good hypotheses.

    Each data point is a vector of M Bernoulli losses. All hypotheses have the
    same population risk p. The algorithm chooses a hypothesis using a Gibbs
    distribution over empirical losses. This makes the selection bias and the
    MI bound directly visible.
    """
    rng = np.random.default_rng(SEED)
    m = 32
    n = 80
    true_risk = 0.20
    trials = 120_000
    empirical = rng.binomial(n, true_risk, size=(trials, m)) / n
    temperatures = [0.0, 0.01, 0.02, 0.05, 0.10, 0.20, 0.50]
    rows: list[dict] = []

    # A deliberately mismatched fixed prior for the KL decomposition demo.
    skew_prior = np.full(m, 0.5 / (m - 1))
    skew_prior[0] = 0.5

    for tau in temperatures:
        if tau == 0.0:
            minima = np.min(empirical, axis=1, keepdims=True)
            ties = empirical == minima
            q_cond = ties / np.sum(ties, axis=1, keepdims=True)
        else:
            q_cond = softmax_rows(-empirical / tau)

        marginal = np.mean(q_cond, axis=0)
        eps = 1e-300
        h_marginal = -float(np.sum(marginal * np.log(np.clip(marginal, eps, None))))
        h_conditional = -float(
            np.mean(np.sum(q_cond * np.log(np.clip(q_cond, eps, None)), axis=1))
        )
        mutual_information = h_marginal - h_conditional
        selected_empirical = float(np.mean(np.sum(q_cond * empirical, axis=1)))
        expected_gap = true_risk - selected_empirical

        # A [0,1]-valued loss is 1/2-sub-Gaussian by Hoeffding's lemma,
        # hence sigma^2 = 1/4 and the Xu-Raginsky bound is sqrt(I/(2n)).
        mi_bound = math.sqrt(mutual_information / (2 * n))

        avg_kl_uniform = float(
            np.mean(np.sum(q_cond * (np.log(np.clip(q_cond, eps, None)) + math.log(m)), axis=1))
        )
        avg_kl_skew = float(
            np.mean(
                np.sum(
                    q_cond
                    * (
                        np.log(np.clip(q_cond, eps, None))
                        - np.log(skew_prior)[None, :]
                    ),
                    axis=1,
                )
            )
        )
        marginal_kl_skew = float(
            np.sum(marginal * (np.log(np.clip(marginal, eps, None)) - np.log(skew_prior)))
        )

        rows.append(
            {
                "temperature": tau,
                "mutual_information_nats": mutual_information,
                "expected_empirical_risk": selected_empirical,
                "population_risk": true_risk,
                "expected_generalization_gap": expected_gap,
                "mi_bound": mi_bound,
                "marginal_entropy_nats": h_marginal,
                "conditional_entropy_nats": h_conditional,
                "avg_kl_to_uniform_prior": avg_kl_uniform,
                "avg_kl_to_skew_prior": avg_kl_skew,
                "marginal_kl_to_skew_prior": marginal_kl_skew,
            }
        )

    fig, ax = plt.subplots(figsize=(9.6, 5.6))
    x = np.array([r["mutual_information_nats"] for r in rows])
    gap = np.array([r["expected_generalization_gap"] for r in rows])
    bound = np.array([r["mi_bound"] for r in rows])
    ax.plot(x, gap, marker="o", label="estimated expected gap")
    ax.plot(x, bound, marker="s", linestyle="--", label="MI upper bound")
    for r in rows:
        label = "argmin" if r["temperature"] == 0 else f"τ={r['temperature']:g}"
        ax.annotate(label, (r["mutual_information_nats"], r["expected_generalization_gap"]),
                    xytext=(4, 5), textcoords="offset points", fontsize=8)
    ax.set_xlabel("I(W; S), nats")
    ax.set_ylabel("expected generalization gap")
    ax.set_title("Adaptive selection: less information about the sample, less selection bias")
    ax.legend()
    ax.grid(alpha=0.25)
    fig.tight_layout()
    fig.savefig(OUT / "M12_experiment_adaptive_selection.png", dpi=180)
    plt.close(fig)

    # Decomposition for tau=0.05.
    chosen = next(r for r in rows if abs(r["temperature"] - 0.05) < 1e-12)
    terms = [
        chosen["mutual_information_nats"],
        chosen["marginal_kl_to_skew_prior"],
        chosen["avg_kl_to_skew_prior"],
    ]
    fig, ax = plt.subplots(figsize=(8.8, 5.2))
    ax.bar(["I(W;S)", "KL(P_W || P)", "E KL(Q_S || P)"], terms)
    ax.set_ylabel("nats")
    ax.set_title("Exact decomposition of average posterior-to-prior KL")
    ax.text(2, terms[2] + 0.02, "sum of the first two terms", ha="center", fontsize=9)
    ax.grid(axis="y", alpha=0.25)
    fig.tight_layout()
    fig.savefig(OUT / "M12_experiment_kl_decomposition.png", dpi=180)
    plt.close(fig)

    return {
        "M": m,
        "n": n,
        "true_risk": true_risk,
        "trials": trials,
        "rows": rows,
    }


def fit_logistic_regression(x: np.ndarray, y: np.ndarray) -> np.ndarray:
    """Simple deterministic full-batch logistic regression."""
    n, d = x.shape
    w = np.zeros(d)
    learning_rate = 0.10
    l2 = 1e-3
    for _ in range(1800):
        margins = y * (x @ w)
        grad = -(x.T @ (y * expit(-margins))) / n + l2 * w
        w -= learning_rate * grad
    return w


def gaussian_kl_isotropic(mean: np.ndarray, sigma_q: float, sigma_p: float) -> float:
    k = mean.size
    return 0.5 * float(
        np.sum((sigma_q**2 + mean**2) / sigma_p**2 - 1 + math.log(sigma_p**2 / sigma_q**2))
    )


def gibbs_linear_risk(x: np.ndarray, y: np.ndarray, mean: np.ndarray, sigma_q: float) -> float:
    """Exact Gibbs 0-1 risk for W~N(mean, sigma_q^2 I) and sign(W^T x)."""
    signed_mean = y * (x @ mean)
    std = sigma_q * np.linalg.norm(x, axis=1)
    z = -signed_mean / np.maximum(std, 1e-15)
    return float(np.mean(ndtr(z)))


def experiment_pac_bayes_classifier() -> dict:
    rng = np.random.default_rng(SEED + 1)
    n_train = 4000
    n_test = 80_000
    d = 5
    delta = 0.05
    sigma_prior = 1.0

    true_w = rng.normal(size=d)
    true_w /= np.linalg.norm(true_w)

    def sample_data(n: int) -> tuple[np.ndarray, np.ndarray]:
        x = rng.normal(size=(n, d))
        prob = expit(2.0 * (x @ true_w))
        y = np.where(rng.random(n) < prob, 1.0, -1.0)
        x_aug = np.column_stack([x, np.ones(n)])
        return x_aug, y

    x_train, y_train = sample_data(n_train)
    x_test, y_test = sample_data(n_test)
    mean = fit_logistic_regression(x_train, y_train)
    deterministic_train = float(np.mean(y_train * (x_train @ mean) <= 0))
    deterministic_test = float(np.mean(y_test * (x_test @ mean) <= 0))

    sigmas = [0.03, 0.05, 0.10, 0.20, 0.30, 0.50, 0.80, 1.00]
    rows: list[dict] = []
    confidence_term = math.log(2 * math.sqrt(n_train) / delta)

    for sigma_q in sigmas:
        empirical_gibbs = gibbs_linear_risk(x_train, y_train, mean, sigma_q)
        test_gibbs = gibbs_linear_risk(x_test, y_test, mean, sigma_q)
        kl = gaussian_kl_isotropic(mean, sigma_q, sigma_prior)
        complexity = (kl + confidence_term) / n_train
        kl_bound = kl_upper_inverse(empirical_gibbs, complexity)
        pinsker_bound = min(1.0, empirical_gibbs + math.sqrt(complexity / 2))
        rows.append(
            {
                "sigma_posterior": sigma_q,
                "empirical_gibbs_risk": empirical_gibbs,
                "test_gibbs_risk": test_gibbs,
                "kl_q_p_nats": kl,
                "pac_bayes_kl_bound": kl_bound,
                "pinsker_square_root_bound": pinsker_bound,
            }
        )

    best = min(rows, key=lambda r: r["pac_bayes_kl_bound"])

    fig, ax = plt.subplots(figsize=(9.6, 5.6))
    xs = np.array(sigmas)
    ax.plot(xs, [r["empirical_gibbs_risk"] for r in rows], marker="o", label="empirical Gibbs risk")
    ax.plot(xs, [r["test_gibbs_risk"] for r in rows], marker="o", label="test Gibbs risk")
    ax.plot(xs, [r["pac_bayes_kl_bound"] for r in rows], marker="s", label="PAC-Bayes-kl certificate")
    ax.plot(xs, [r["pinsker_square_root_bound"] for r in rows], linestyle="--", label="square-root corollary")
    ax.axhline(deterministic_test, linestyle=":", label="deterministic mean test error")
    ax.set_xscale("log")
    ax.set_xlabel("posterior standard deviation σ_Q")
    ax.set_ylabel("0-1 risk")
    ax.set_title("Stochastic linear classifier: empirical fit, KL complexity, and certificate")
    ax.legend()
    ax.grid(alpha=0.25)
    fig.tight_layout()
    fig.savefig(OUT / "M12_experiment_pac_bayes_classifier.png", dpi=180)
    plt.close(fig)

    return {
        "n_train": n_train,
        "n_test": n_test,
        "dimension_with_bias": d + 1,
        "delta": delta,
        "sigma_prior": sigma_prior,
        "mean_norm": float(np.linalg.norm(mean)),
        "deterministic_train_error": deterministic_train,
        "deterministic_test_error": deterministic_test,
        "rows": rows,
        "best_by_pac_bayes_kl": best,
    }


def main() -> None:
    results = {
        "adaptive_selection": experiment_adaptive_selection(),
        "pac_bayes_classifier": experiment_pac_bayes_classifier(),
    }
    (OUT / "M12_experiment_results.json").write_text(
        json.dumps(results, indent=2, ensure_ascii=False), encoding="utf-8"
    )

    best = results["pac_bayes_classifier"]["best_by_pac_bayes_kl"]
    print("Adaptive selection (argmin):")
    row0 = results["adaptive_selection"]["rows"][0]
    print(f"  I(W;S): {row0['mutual_information_nats']:.6f} nats")
    print(f"  expected gap: {row0['expected_generalization_gap']:.6f}")
    print(f"  MI bound: {row0['mi_bound']:.6f}")
    print("Best stochastic classifier certificate:")
    print(f"  sigma_Q: {best['sigma_posterior']:.3f}")
    print(f"  empirical Gibbs risk: {best['empirical_gibbs_risk']:.6f}")
    print(f"  test Gibbs risk: {best['test_gibbs_risk']:.6f}")
    print(f"  KL(Q||P): {best['kl_q_p_nats']:.6f} nats")
    print(f"  PAC-Bayes-kl bound: {best['pac_bayes_kl_bound']:.6f}")


if __name__ == "__main__":
    main()

Bonus. A valid prior learned from part of the data

Split the sample into $S_0$ and $S_1$ .

Build $P_{S_0}$ from $S_0$ .
Train $Q_{S_0,S_1}$ .
Conditional on $S_0$ , state a PAC-Bayes bound on the independent subset $S_1$ .
Explain the trade-off between prior quality and certification-sample size.

Show answer and solution

Split the sample:

S=(S_0,S_1),

where $S_0$ and $S_1$ are disjoint i.i.d. parts and therefore independent conditional on $\mathcal D$ .

From $S_0$ build the prior

P_{S_0}.

Now condition on a particular value of $S_0$ . After that conditioning, $P_{S_0}$ is fixed and independent of the random certification sample $S_1$ , so the standard PAC-Bayes theorem applies:

\operatorname{kl} \bigl( \widehat L_{S_1}(Q)\|L(Q) \bigr) \le \frac{ KL(Q\|P_{S_0}) + \ln\dfrac{2\sqrt{|S_1|}}{\delta} }{|S_1|}.

The posterior $Q$ may depend on both $S_0$ and $S_1$ , because once the prior is fixed the bound holds simultaneously for all $Q$ .

The trade-off:

a larger $S_0$ allows a more informative prior and a smaller KL;
a smaller $S_1$ weakens the concentration term and shrinks the effective certification sample.

Exercise 1. Proving PAC-Bayes-kl

Where independence of the prior is used

Exercise 2. Zero empirical error

Exercise 3. A Gaussian posterior and L2L_2L2​

Exercise 4. Adaptive selection and MI

Exercise 5. The exact average-KL decomposition

Exercise 6. Python: selection bias and a PAC-Bayes certificate

Part 1. Adaptive selection

Part 2. A stochastic linear classifier

Bonus. A valid prior learned from part of the data

Exercise 3. A Gaussian posterior and $L_2$