TheoremStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedprecheck passjudge 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.

Empirical-risk oracle bound under uniform deviation

Statement

Let $X_{1}, \dots, X_{n}$ be iid with law $P$ , and let $L$ be a nonempty class of measurable integrable loss functions $ℓ$ such that $\inf_{ℓ \in L} P ℓ$ is finite. Define population risk $R (ℓ) = P ℓ$ and empirical risk $R_{n} (ℓ) = P_{n} ℓ$ . Suppose $\hat{ℓ} \in L$ satisfies the approximate-minimization inequality

$R_{n} (\hat{ℓ}) \leq \inf_{ℓ \in L} R_{n} (ℓ) + η$

for some $η \geq 0$ . On the event

$\sup_{ℓ \in L} ∣ R_{n} (ℓ) - R (ℓ) ∣ \leq ϵ,$

one has

$R (\hat{ℓ}) \leq \inf_{ℓ \in L} R (ℓ) + 2 ϵ + η .$

No existence of an exact empirical minimizer is required. The empirical averages use Empirical, centered, and Rademacher processes.

Facts & Assumptions

Given: The class $L$ with finite population risks and finite lower risk infimum, empirical and population risks, $ϵ, η \geq 0$ , the uniform-deviation event, and the stated approximate-minimization property.

[F1]

Empirical, centered, and Rademacher processes: for iid data, $P_{n} ℓ = n^{- 1} \sum_{i = 1}^{n} ℓ (X_{i})$ and $P ℓ = \int ℓ d P$ . Its current carrier and batch-15 manifest entry agree, and its current owner Step 1 record marks it construction-ready; that status is not independent mathematical approval.

Proof

Given: The iid experiment, the loss class and risks, the uniform-deviation event, and the approximate-minimization property.

1.1givenF1algebra

Fix any $ℓ \in L$ . On the stated event, $R (\hat{ℓ}) \leq R_{n} (\hat{ℓ}) + ϵ$ by applying the uniform deviation bound to $\hat{ℓ}$ .

2.1givenF1step 1.1algebra

The approximate-minimization property gives $R_{n} (\hat{ℓ}) \leq R_{n} (ℓ) + η$ , and the same event gives $R_{n} (ℓ) \leq R (ℓ) + ϵ$ . Combining these inequalities with step 1.1 yields $R (\hat{ℓ}) \leq R (ℓ) + 2 ϵ + η$ .

3.1step 2.1algebra∎

Since step 2.1 holds for every $ℓ \in L$ , take the infimum of its right-hand side over $L$ to obtain the claimed bound.

Depends on

Empirical, centered, and Rademacher processes

Used by

Nothing in the library uses this result yet.

Dependency tree · two levels

6 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

Jon A. Wellner, Empirical Processes: Theory and Applications, Chapter 1, §§5–6 (standard reference, not scraped)
David Pollard, Empirical Processes: Theory and Applications, Sections 8–10 (standard reference, not scraped)
Cornell CS 3780/5780, Lecture 16: Empirical Risk Minimization and Model Selection (standard reference, not scraped)