ExampleConstruction: Literature-sourcedVerification: AI-adaptedPipeline-generatedjudge pass (gpt-6-luna)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

A posterior concentrated on one hypothesis

Example

Let the hypothesis space be the two-point measurable space $Θ = {h_{0}, h_{1}}$ with its full sigma-algebra, and let the prior be uniform on the two hypotheses. Let $Z$ be any measurable observation space, let $D$ be a probability measure on $Z$ , and let $ℓ : Θ \times Z \to [0, C]$ be product-measurable for a finite $C \geq 0$ . Define $R (h) = \int_{Z} ℓ (h, z) D (d z)$ and ${\hat{R}}_{S} (h) = m^{- 1} \sum_{i = 1}^{m} ℓ (h, Z_{i})$ . For an IID sample $S = (Z_{1}, \dots, Z_{m})$ of size $m \geq 1$ with common law $D$ , take the posterior $ρ = δ_{h_{0}}$ . Then $K L (ρ ∥ π) = \log 2$ , and for every fixed $λ > 0$ and $δ \in (0, 1)$ , with probability at least $1 - δ$ , $R (h_{0}) \leq {\hat{R}}_{S} (h_{0}) + \frac{λ C^{2}}{8 m} + \frac{\log 2 + \log (1 / δ)}{λ}$

Example references

PAC-Bayes priors, posteriors, and relative entropy: defines the sample-independent prior, absolutely continuous posterior, and finite-partition relative entropy used here.

The PAC-Bayes KL generalization bound: gives the simultaneous posterior-average risk bound under the stated product-measurability and IID hypotheses.

The natural logarithm as the inverse of the exponential function: $\log$ is the inverse of the real exponential on positive reals.

Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, §2.1.1: discusses the PAC-Bayes bound with a posterior concentrated on an individual predictor.

Facts & Assumptions

Given: The finite measurable hypothesis space, its uniform prior, the bounded jointly measurable loss, an IID sample with common law $D$ , and the point-mass posterior $δ_{h_{0}}$ .

[F1]

A prior and posterior are probability measures, and relative entropy is the supremum of finite-partition divergences using the natural logarithm. PAC-Bayes priors, posteriors, and relative entropy, Probability measures and probability spaces, The natural logarithm as the inverse of the exponential function

[F2]

For the fixed prior and bounded product-measurable loss, with probability at least $1 - δ$ the PAC-Bayes inequality holds simultaneously for every posterior absolutely continuous with respect to the prior. The PAC-Bayes KL generalization bound

Verification

Given: The finite measurable hypothesis space, uniform sample-independent prior, bounded product-measurable loss, IID sample with common law $D$ , and posterior $δ_{h_{0}}$ in the Example.

1.1givenF1casesalgebra

The posterior $δ_{h_{0}}$ is absolutely continuous with respect to the uniform prior because every prior-null subset of $Θ$ is empty. For a finite measurable partition, if its cells keep $h_{0}, h_{1}$ together, its divergence is $0$ ; if it separates them, the cell containing $h_{0}$ contributes $1 \cdot \log (1 / (1 / 2)) = \log 2$ and the other cell contributes $0$ . Hence every partition divergence is at most $\log 2$ , and the partition into singletons attains it, so [F1] gives $K L (δ_{h_{0}} ∥ π) = \log 2$ .

2.1givenF2step 1.1algebra∎

Since $ρ$ is concentrated at $h_{0}$ , its population and empirical risk averages are respectively $R (h_{0})$ and ${\hat{R}}_{S} (h_{0})$ . Applying [F2] to this posterior gives the displayed inequality with probability at least $1 - δ$ .

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

28 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

Pierre Alquier, User-friendly Introduction to PAC-Bayes Bounds, Chapter 2, §2.1.1 (standard reference, not scraped)