ExampleConstruction: AI-generatedVerification: AI-generatedPipeline-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.

Finite lookup tables have explicit PAC sample bounds

Example

Let $d \geq 1$ , let $X = {1, \dots, d}$ have the discrete sigma-algebra, and let $H$ be the class of all binary lookup tables on $X$ . Then $∣ H ∣ = 2^{d}$ . For any $0 < ϵ, δ < 1$ , the exact ERM is realizable $(ϵ, δ)$ -PAC at every realizable law when $m \geq \frac{d \log 2 + \log (1 / δ)}{ϵ},$ and is agnostic $(ϵ, δ)$ -PAC at every law when $m \geq \frac{2 (d \log 2 + \log (2 / δ))}{ϵ^{2}} .$ The agnostic condition uses the same class and binary zero-one loss; these are sufficient sample sizes.

Example references

Realizable and agnostic PAC learning: defines the realizable and agnostic PAC probability guarantees used here.

Finite-class realizable and agnostic sample complexity: gives the realizable and agnostic finite-class sample-size conditions.

Facts & Assumptions

Given: A finite discrete instance set of size $d \geq 1$ , all binary lookup tables on it, and $0 < ϵ, δ < 1$ .

[F1]

For a finite class of size $N$ , exact ERM has the stated realizable sample bound and the agnostic sample bound $m \geq 2 (\log N + \log (2 / δ)) / ϵ^{2}$ . Finite-class realizable and agnostic sample complexity

[F2]

IID means mutually independent sample observations with one common law. Identical distribution and IID families

Verification

Given: The finite lookup-table class and sample-size parameters in the Example.

1.1givenconstruct

A table assigns one of two labels independently at each of the $d$ inputs, so there are exactly $2^{d}$ tables. Every table is measurable on the finite discrete space, and the class is nonempty.

2.1F1F2step 1.1algebra∎

[F2] gives the IID sample convention required by [F1]. Substitute $N = 2^{d}$ into [F1] and use $\log (2^{d}) = d \log 2$ . The resulting sufficient sample-size conditions are exactly those in the Example.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

11 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.