ExampleConstruction: AI-adaptedVerification: 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 finite class can make private ERM impractical

Example

Let $d \geq 1$ , let $X = {0, 1}^{d}$ with its power-set sigma-algebra, and let $C$ be the class of every map from $X$ to ${0, 1}$ . Then $∣ C ∣ = 2^{2^{d}}$ and $\ln ∣ C ∣ = 2^{d} \ln 2$ . For fixed $0 < α, β < 1$ and $ε > 0$ , the sample-size sufficient condition in the private finite-class ERM theorem becomes $n \geq 24 \max {\frac{2^{d} \ln 2 + \ln (1 / β)}{ε α}, \frac{2^{d} \ln 2 + \ln (1 / β)}{α^{2}}} .$ The selector's displayed normalizer sums one weight per classifier, so literal exhaustive evaluation of this class has $2^{2^{d}}$ hypotheses; evaluating each of them on all $m$ records by the direct method uses $m 2^{2^{d}}$ loss evaluations. This counts the direct exhaustive implementation only and is not a lower bound for every algorithm exploiting the structure of the class.

Example references

Finite-class empirical-risk selector

Finite-class private ERM sample-size bound

Dwork and Roth, The Algorithmic Foundations of Differential Privacy, Chapter 11 §11.1: full text.

Shalev-Shwartz and Ben-David, Understanding Machine Learning: From Theory to Algorithms, Chapter 4 §4.2: full text.

Facts & Assumptions

Given: An integer $d \geq 1$ , the discrete domain $X = {0, 1}^{d}$ , the class of all binary maps on $X$ , and fixed parameters $0 < α, β < 1$ , $ε > 0$ .

[F1]

The private ERM sample-size condition for a finite class of size at least two is $24$ times the maximum of the privacy and squared-accuracy terms involving $\ln ∣ C ∣ + \ln (1 / β)$ . Private finite-class ERM excess-risk bound

[F2]

The selector normalizer is a sum of one positive empirical-risk weight for every hypothesis in the finite class. Finite-class empirical-risk selection with exponential weights

Verification

Given: The finite domain, class and parameters in the Example and [F1]–[F2].

1.1givenalgebra

There are two independent choices for each of the $d$ coordinates of a point in ${0, 1}^{d}$ , so $∣ X ∣ = 2^{d}$ .

2.1givenstep 1.1algebra

A map $h : X \to {0, 1}$ is determined by one binary value at each of the $2^{d}$ domain points, and every such assignment defines a map. Hence there are $2^{2^{d}}$ maps, so $∣ C ∣ = 2^{2^{d}}$ and $\ln ∣ C ∣ = 2^{d} \ln 2$ .

3.1givenF1step 2.1algebra

Since $d \geq 1$ , $∣ C ∣ \geq 2$ . Substituting $\ln ∣ C ∣ = 2^{d} \ln 2$ into [F1] gives exactly the displayed sufficient sample-size condition.

4.1F2step 2.1algebra∎

By [F2], the normalizer contains $∣ C ∣ = 2^{2^{d}}$ terms. Directly computing one empirical risk by evaluating its loss on each of the $m$ records takes $m$ loss evaluations; doing this for every hypothesis uses $m ∣ C ∣ = m 2^{2^{d}}$ such evaluations. This is the cost of that exhaustive procedure; the count alone does not rule out an implementation that exploits structure or samples from the same distribution without explicitly listing every hypothesis.

Depends on

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

20 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

Cynthia Dwork and Aaron Roth, The Algorithmic Foundations of Differential Privacy, Chapter 11 §11.1 (standard reference, not scraped)
Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Chapter 4 §4.2 (standard reference, not scraped)