AlgorithmAlgorithm: Literature-sourcedProof: 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.

Finite-class empirical-risk selection with exponential weights

Definition

Let $(X, Σ_{X})$ be a nonempty measurable space, let the binary label set ${0, 1}$ carry its power-set sigma-algebra, and let $C$ be a finite nonempty class of measurable maps $h : X \to {0, 1}$ . Fix an integer $n \geq 1$ and a parameter $ε > 0$ . On an ordered labeled sample $S = ((x_{1}, y_{1}), \dots, (x_{m}, y_{m}))$ with $m \geq n$ , or on its underlying finite multiset, define ${\hat{L}}_{S} (h) = \frac{1}{m} \sum_{i = 1}^{m} 1 {h (x_{i}) \neq y_{i}}, w_{S} (h) = \exp ⁣ (- \frac{ε n}{2} {\hat{L}}_{S} (h)) .$ Output $h \in C$ with probability $w_{S} (h) / \sum_{g \in C} w_{S} (g)$ . This formula is invariant under permutations of the sample. For the statistical input, the ordered sample space has its finite product sigma-algebra. For the private-database input, the same formula is defined on finite-support record-count functions of size at least $n$ , with the power-set sigma-algebra; privacy is proved separately.

Definition references

Finite product sigma-algebras for samples

The real exponential function

Probability kernels for randomized selection

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

Salil Vadhan, The Complexity of Differential Privacy, Proposition 4.2: full text.

Facts & Assumptions

Given: The measurable binary class, $n \geq 1$ , $ε > 0$ , and a finite sample or multiset with at least $n$ records.

[F1]

A measurable space is a set with a sigma-algebra; measurable rectangles generate the finite product sigma-algebra. Measurable spaces and measurable sets, Measurable rectangles in a product of measurable spaces, The product sigma-algebra and its finite iterates

[F2]

The real exponential is finite and strictly positive on every real input. The real exponential function and the number $e$ by a power series, The exponential is positive and satisfies $\exp (- x) = 1 / \exp (x)$

[F3]

The exponential is continuous, continuous real maps have Borel preimages, and composition with a Borel measurable outer map preserves measurability. The exponential function is strictly increasing, A continuous map has Borel preimages of Borel sets, Composition with a Borel measurable outer map preserves measurability

[F4]

Finite sums, scalar multiples, and products of measurable real functions are measurable. Arithmetic and lattice operations preserve measurability whenever they are defined

[F5]

A real function is measurable exactly when its strict threshold sets are measurable. Threshold characterisations of real-valued and extended-real-valued measurability

[F6]

A probability measure has total mass one; a probability kernel has probability-measure sections and measurable event evaluations. Probability measures and probability spaces, Measure kernel and probability kernel

Verification

Given: The hypotheses and procedure in the Definition.

1.1givenF1F2F3F4construct

For each $h \in C$ , its mismatch set is $(h^{- 1} {0} \times {1}) \cup (h^{- 1} {1} \times {0})$ , a finite union of measurable rectangles by [F1]. Thus each sample loss indicator and the finite average ${\hat{L}}_{S} (h)$ are measurable in the ordered sample. By [F2]–[F4], the weight $w_{S} (h)$ is finite, positive, and measurable in $S$ .

2.1F2F4F5F6step 1.1algebra∎

Since $C$ is finite and nonempty, $Z_{S} : = \sum_{g \in C} w_{S} (g)$ is finite, measurable, and strictly positive. For $a \leq 0$ , ${S : 1 / Z_{S} > a}$ is the whole sample space; for $a > 0$ , it is ${S : Z_{S} < 1 / a}$ , which is measurable by [F5]. Hence $1 / Z_{S}$ , and then each $p_{S} (h) : = w_{S} (h) / Z_{S}$ , is measurable by [F4]. These probabilities sum to one. Define $K (S, A) = \sum_{h \in A} p_{S} (h)$ for $A \subseteq C$ ; it is countably additive because a disjoint family of subsets of finite $C$ has only finitely many nonempty members, and $K (S, C) = 1$ . For each $A$ , $S \mapsto K (S, A)$ is measurable as a finite sum of measurable functions; on the power-set private-database domain every event evaluation is also measurable. Thus [F6] gives the probability-kernel conditions.

Source notes

The scale $1 / n$ is used as a sensitivity upper bound. The private theorem proves its add/remove validity on the restricted size-at-least- $n$ domain and derives privacy and utility directly; no exact attained-maximum convention is assumed here.

Depends on

Used by

A finite class can make private ERM impractical Example
Private ERM on a four-threshold class Example
Private finite-class ERM excess-risk bound Theorem

Dependency tree · two levels

42 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)
Salil Vadhan, The Complexity of Differential Privacy, 2017 manuscript, §4.2 (standard reference, not scraped)