TheoremStatement: AI-adaptedProof: 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 finite-class ERM excess-risk bound

Statement

Let $(X, Σ_{X})$ be a nonempty measurable space, let $C$ be a finite nonempty class of measurable classifiers $h : X \to {0, 1}$ , let $n \geq 1$ be an integer, and let $ε > 0$ . On the domain of finite labeled databases of size at least $n$ , use add/remove adjacency, with both neighboring databases required to remain in the domain. For a database $D$ of size $m \geq n$ , write ${\hat{L}}_{D} (h) = \frac{1}{m} \sum_{(x, y) \in D} 1 {h (x) \neq y},$ where records are counted with multiplicity. The finite-class exponential selector that outputs $h \in C$ with probability proportional to $\exp (- ε n {\hat{L}}_{D} (h) / 2)$ is pure $ε$ -differentially private on this domain.

For the statistical guarantee, let $P$ be any probability law on $X \times {0, 1}$ , let $Z_{1}, \dots, Z_{n}$ be IID with law $P$ , and apply the same selector to their labeled sample. Define the population risk $L_{P} (h) = P {h (X) \neq Y}$ . For every $0 < β < 1$ , with probability at least $1 - β$ over both the sample and the selector's random draw, its output $H$ satisfies $L_{P} (H) - \inf_{h \in C} L_{P} (h) \leq 2 \sqrt{\frac{\ln ∣ C ∣ + \ln (4 / β)}{2 n}} + \frac{2}{ε n} (\ln ∣ C ∣ + \ln (2 / β)) .$ If $∣ C ∣ \geq 2$ and $0 < α, β < 1$ , then $n \geq 24 \max {\frac{\ln ∣ C ∣ + \ln (1 / β)}{ε α}, \frac{\ln ∣ C ∣ + \ln (1 / β)}{α^{2}}}$ suffices to make this excess risk at most $α$ with probability at least $1 - β$ . If $∣ C ∣ = 1$ , the excess risk is identically zero.

Statement references

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

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

Differential privacy, databases, and add/remove adjacency: finite-support databases, add/remove adjacency, and the ordered event inequality.

Finite-class empirical-risk selection with exponential weights: the measurable finite-class selector and its exponential weights.

Finite-class agnostic ERM bound: the choice-free two-sided finite-class deviation event used in the statistical argument.

Facts & Assumptions

Given: A nonempty measurable instance space, a finite nonempty measurable binary class $C$ , an integer $n \geq 1$ , $ε > 0$ , add/remove neighboring finite labeled databases restricted to sizes at least $n$ , and an IID sample of size $n$ from an arbitrary law $P$ on $X \times {0, 1}$ . For the statistical bound also assume $0 < β < 1$ ; for the sample-size conclusion assume $0 < α < 1$ .

[F1]

A database is a finite-support record-count function, add/remove neighbors differ by one record, and $(ε, 0)$ -DP means that for every ordered neighboring pair and every output event $A$ , $K (D, A) \leq e^{ε} K (D^{'}, A)$ . The neighboring relation is symmetric, so both orders are required. Differential privacy, databases, and add/remove adjacency

[F2]

On a sample or multiset $D$ of size $m \geq n$ , the algorithm uses empirical zero-one risk ${\hat{L}}_{D} (h) = m^{- 1} \sum_{(x, y) \in D} 1 {h (x) \neq y}$ and output probabilities proportional to $\exp (- ε n {\hat{L}}_{D} (h) / 2)$ ; the formula is invariant under sample permutations. Finite-class empirical-risk selection with exponential weights

[F3]

For a finite nonempty measurable class $C$ and $n$ IID examples, population and empirical zero-one risks are expectations and sample averages of measurable $[0, 1]$ -valued losses; with probability at least $1 - γ$ , simultaneously for every $h \in C$ , $∣ L_{P} (h) - {\hat{L}}_{S} (h) ∣ \leq a_{γ} : = \sqrt{\frac{\ln ∣ C ∣ + \ln (2 / γ)}{2 n}} .$ This two-sided deviation conclusion is choice-free. Finite-class agnostic ERM bound

[F4]

For events $A_{1}, A_{2}$ , the probability of their union is at most the sum of their probabilities. Basic identities for a probability measure

[F5]

The exponential is strictly positive, strictly increasing, and satisfies $\exp (u) / \exp (v) = \exp (u - v)$ ; the natural logarithm is its inverse on positive reals, is increasing, and obeys the product and reciprocal laws. The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$ , The exponential function is strictly increasing, The exponential addition formula $\exp (x + y) = \exp (x) \exp (y)$ , The natural logarithm as the inverse of the exponential function, Order, continuity, range, and the product, quotient, and reciprocal laws for the natural logarithm

Proof

Given: The hypotheses in the Statement and [F1]–[F5].

1.1givenF2algebra

Let $D, D^{'}$ be neighboring databases in the restricted domain and orient them so $D^{'}$ is obtained from $D$ by adding one record $z = (x, y)$ . Since both databases are in the domain, $m : = ∣ D ∣ \geq n$ . For $q_{h} = 1 {h (x) \neq y} \in {0, 1}$ , ${\hat{L}}_{D^{'}} (h) - {\hat{L}}_{D} (h) = (m {\hat{L}}_{D} (h) + q_{h}) / (m + 1) - {\hat{L}}_{D} (h) = (q_{h} - {\hat{L}}_{D} (h)) / (m + 1)$ . As $q_{h}, {\hat{L}}_{D} (h) \in [0, 1]$ , this difference has absolute value at most $1 / (m + 1) \leq 1 / n$ ; reversing the pair gives the same bound.

1.2givenF2F5algebra

For a fixed sample $S$ , let ${\hat{L}}_{*} = \min_{h \in C} {\hat{L}}_{S} (h)$ , which exists because the class is finite and nonempty. For any $t > 0$ , the selector's probability that ${\hat{L}}_{S} (H) > {\hat{L}}_{*} + t$ is at most $∣ C ∣ \exp (- ε n ({\hat{L}}_{*} + t) / 2) / \exp (- ε n {\hat{L}}_{*} / 2) = ∣ C ∣ e^{- ε n t / 2}$ : each event weight is bounded by the numerator term and the normalizer includes a minimizer's weight. With $t = \frac{2}{ε n} (\ln ∣ C ∣ + \ln (2 / β)) > 0$ , this probability is at most $β / 2$ .

1.3givenF3algebra

Apply [F3] with $γ = β / 2$ . With probability at least $1 - β / 2$ , all $h \in C$ satisfy $∣ L_{P} (h) - {\hat{L}}_{S} (h) ∣ \leq a$ , where $a = \sqrt{(\ln ∣ C ∣ + \ln (4 / β)) / (2 n)}$ .

2.1givenF1F2F5step 1.1

Write $w_{D} (h) = \exp (- ε n {\hat{L}}_{D} (h) / 2)$ and $Z_{D} = \sum_{g \in C} w_{D} (g)$ . By [F5] and step 1.1, $e^{- ε / 2} \leq w_{D} (h) / w_{D^{'}} (h) \leq e^{ε / 2}$ for each $h$ . Summing gives the same two-sided bounds for $Z_{D} / Z_{D^{'}}$ . Each weight and normalizer is positive and finite because the class is finite nonempty and [F5] makes every exponential weight positive. The normalized finite weights therefore form a probability measure on the output class; because the restricted database domain has the power-set sigma-algebra, every event-evaluation function is measurable, so this is a probability kernel. Therefore $(w_{D} (h) / Z_{D}) / (w_{D^{'}} (h) / Z_{D^{'}}) \leq e^{ε}$ . Summing over any event $A \subseteq C$ proves $K (D, A) \leq e^{ε} K (D^{'}, A);$ interchanging $D, D^{'}$ proves the reverse ordered inequality. By [F1] this is pure $ε$ -DP.

2.2givenF3F4step 1.2step 1.3algebra

For every fixed sample, step 1.2 bounds the conditional selector failure probability by $β / 2$ , so averaging over the sample gives the same joint failure bound. Intersect that utility event with the deviation event from step 1.3; [F4] gives probability at least $1 - β$ . On the intersection, ${\hat{L}}_{S} (H) \leq \min_{g} {\hat{L}}_{S} (g) + t$ , $L_{P} (H) \leq {\hat{L}}_{S} (H) + a$ , and for every $h \in C$ , $\min_{g} {\hat{L}}_{S} (g) \leq {\hat{L}}_{S} (h) \leq L_{P} (h) + a$ . Taking the infimum over $h$ in the last inequality and combining yields $L_{P} (H) - \inf_{h} L_{P} (h) \leq 2 a + t$ , which is the displayed excess-risk bound.

3.1givenstep 2.2algebra∎

Suppose $∣ C ∣ \geq 2$ and write $Q = \ln ∣ C ∣ + \ln (1 / β) \geq \ln 2$ . Then $\ln ∣ C ∣ + \ln (4 / β) = Q + \ln 4 \leq 3 Q$ and $\ln ∣ C ∣ + \ln (2 / β) = Q + \ln 2 \leq 2 Q$ . The sample-size condition gives $2 \sqrt{3 Q / (2 n)} \leq α / 2$ and $4 Q / (ε n) \leq α / 6$ , so the bound in step 2.2 is at most $2 α / 3 \leq α$ . If $∣ C ∣ = 1$ , its only classifier is always selected and minimizes population risk over that class, so its excess is zero.

Source notes

The sensitivity scale $1 / n$ is a valid upper bound on the restricted size-at-least- $n$ add/remove domain; no exact maximum-sensitivity claim is used. The agnostic ERM supplier body gives the deviation event and its proof is choice-free, but its current Step-1 readiness hash is stale. This consumer therefore remains escalated until the owner reconciles that supplier record.

Depends on

Used by

A finite class can make private ERM impractical Example
Private ERM on a four-threshold class Example

Dependency tree · two levels

48 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 3 §3.4 and 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)