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.

Private ERM on a four-threshold class

Example

Let $X = {0, 1, 2}$ with its power-set sigma-algebra and let $h_{r} (x) = 1 {x \geq r}$ for $r \in {0, 1, 2, 3}$ . On the labeled database $D = {(0, 0), (1, 1), (2, 0)}$ , use the private finite-class selector with $n = 3$ and $ε > 0$ . In the order $r = 0, 1, 2, 3$ , the empirical risks are $2 / 3, 1 / 3, 2 / 3, 1 / 3$ and the selector weights are $e^{- ε}, e^{- ε / 2}, e^{- ε}, e^{- ε / 2}$ . Its normalizer is $2 e^{- ε} + 2 e^{- ε / 2}$ , so each of the two risk- $2 / 3$ thresholds is selected with probability $1 / [2 (1 + e^{ε / 2})]$ and each of the two risk- $1 / 3$ thresholds with probability $e^{ε / 2} / [2 (1 + e^{ε / 2})]$ .

Example references

Finite-class empirical-risk selector

Privacy and excess-risk guarantee

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: The discrete instance space ${0, 1, 2}$ , thresholds $h_{r}$ for $r \in {0, 1, 2, 3}$ , the stated database $D$ , $n = 3$ , and $ε > 0$ .

[F1]

The selector uses empirical zero-one risk on the multiset and assigns each hypothesis weight $\exp (- ε n {\hat{L}}_{D} (h) / 2)$ before normalizing over the finite class. Finite-class empirical-risk selection with exponential weights

[F2]

The class consists of the four maps $h_{r} (x) = 1 {x \geq r}$ on the stated domain, and the output probabilities are the normalized finite weights of [F1]. Finite-class empirical-risk selection with exponential weights

Verification

Given: The data, thresholds and selector in the Example and [F1]–[F2].

1.1givenF2algebra

For $r = 0$ , the predictions on $0, 1, 2$ are $(1, 1, 1)$ , which disagree with labels $(0, 1, 0)$ twice. For $r = 1$ , predictions are $(0, 1, 1)$ and disagree once; for $r = 2$ , predictions are $(0, 0, 1)$ and disagree twice; for $r = 3$ , predictions are $(0, 0, 0)$ and disagree once. Dividing by the three records gives risks $(2 / 3, 1 / 3, 2 / 3, 1 / 3)$ .

2.1F1step 1.1algebra

By [F1] with $n = 3$ , a risk $2 / 3$ gives weight $\exp (- 3 ε (2 / 3) / 2) = e^{- ε}$ and a risk $1 / 3$ gives weight $\exp (- 3 ε (1 / 3) / 2) = e^{- ε / 2}$ . Therefore the normalizer is $Z = 2 e^{- ε} + 2 e^{- ε / 2}$ .

3.1F1step 2.1algebra∎

Dividing the weights by $Z = 2 e^{- ε / 2} (1 + e^{- ε / 2})$ gives probability $1 / [2 (1 + e^{ε / 2})]$ for each risk- $2 / 3$ threshold and probability $e^{ε / 2} / [2 (1 + e^{ε / 2})]$ for each risk- $1 / 3$ threshold. The four probabilities sum to one, since the two groups have total masses $1 / (1 + e^{ε / 2})$ and $e^{ε / 2} / (1 + e^{ε / 2})$ .

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)