LemmaStatement: AI-adaptedProof: AI-generatedPipeline-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.

The finite-list ERM selector is measurable

Statement

For a sample of positive length, a finite ordered nonempty list of measurable predictors, and finite tolerance $η \geq 0$ , let $J (S)$ be the index returned by the finite-list empirical-risk algorithm. Then $J$ is measurable into the finite index set with its discrete sigma-algebra, the evaluation map $(S, x) \mapsto f_{J (S)} (x)$ is jointly measurable, and the returned predictor is an $η$ -approximate empirical risk minimizer as defined in the algorithm's input conditions. When $η = 0$ , it is an exact minimizer.

Facts & Assumptions

Given: A supervised prediction problem, sample size $m \geq 1$ , an ordered list $(f_{1}, \dots, f_{n})$ of measurable predictors with $n \geq 1$ , and finite tolerance $η \geq 0$ .

[F1]

The algorithm returns index $1$ when every list risk is infinite; otherwise it returns the first finite-risk index within $η$ of the finite list minimum. Finite-list empirical risk minimization

[F2]

For each fixed predictor, the empirical-risk map on the sample space is extended-real measurable. Population and empirical risks are measurable

[F3]

A finite-list exact or approximate ERM is defined by its empirical risk relative to the list infimum, with a separate all-infinite case. Empirical risk minimizers

[F4]

Finite sums of measurable extended-real functions are measurable when pointwise defined; real scalar multiples of real-valued measurable functions, functions $f 1_{E}$ for nonnegative measurable extended-real $f$ and measurable $E$ , countable infima, and increasing pointwise limits of measurable extended-real functions are measurable. Closure properties of measurable functions used by the integral

[F5]

The finite sample-and-instance product sigma-algebra contains measurable rectangles and is closed under finite unions and differences. The product sigma-algebra and its finite iterates

[F6]

An extended-real function is measurable when preimages of Borel sets, including the finite-value ray, are measurable. Extended-real-valued measurable functions

[F7]

A map between measurable spaces is measurable exactly when preimages of measurable sets are measurable. A measurable function between measurable spaces

Proof

1.1F2F4F6

For $j = 1, \dots, n$ , put $r_{j} (S) = {\hat{R}}_{S} (f_{j})$ and $r_{*} (S) = \min_{j} r_{j} (S)$ . By [F2] each $r_{j}$ is measurable. The finite minimum is the infimum of the measurable sequence $r_{1}, \dots, r_{n}, r_{n}, r_{n}, \dots$ , so [F4] makes $r_{*}$ measurable. Thus $E : = {S : r_{*} (S) < + \infty}$ is measurable by [F6].

2.1F1F4F6step 1.1

Define finite nonnegative measurable functions $u_{j} : = r_{j} 1_{{r_{j} < + \infty}}$ and $u_{*} : = r_{*} 1_{E}$ . Their measurability follows from [F4], including the convention $0 \cdot (+ \infty) = 0$ . The sets ${r_{j} < + \infty}$ and $E$ are measurable by [F6]. On $E$ , $u_{*} = r_{*}$ and each finite $r_{j}$ equals $u_{j}$ , so $C_{j} : = E \cap {r_{j} < + \infty} \cap {u_{j} - u_{*} \leq η}$ is measurable by [F4, F6]. At every $S \in E$ a finite minimizing index lies in some $C_{j}$ .

3.1F1F5F7step 2.1

The algorithm's selected-index events are ${J = 1} = E^{c} \cup C_{1}$ and, for $j > 1$ , ${J = j} = C_{j} ∖ ⋃_{k < j} C_{k}$ . They are measurable by step 2.1, so $J$ is measurable into the finite discrete index set by [F7]. For each measurable $B \subseteq A$ , the evaluation preimage is $⋃_{j = 1}^{n} ({J = j} \times f_{j}^{- 1} (B))$ , a finite union of measurable rectangles by [F5]; hence $(S, x) \mapsto f_{J (S)} (x)$ is jointly measurable by [F7].

4.1F1F3givenstep 1.1step 2.1∎

On $E^{c}$ all list risks are $+ \infty$ , so the returned first predictor is an exact minimizer by [F3]. On $E$ , at least one finite minimizer exists in the finite list, belongs to some $C_{j}$ , and the first selected $C_{j}$ has finite risk at most $r_{*} + η$ by its definition. If $η = 0$ , this inequality forces the selected risk to equal $r_{*}$ . Thus the output has the asserted ERM property in both branches.

Depends on

Used by

Finite-class agnostic ERM bound Theorem
Finite-class realizable PAC bound Theorem

Cited to discharge well-definedness by Finite-list empirical risk minimization.

Dependency tree · two levels

19 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

Shai Shalev-Shwartz and Shai Ben-David, Understanding Machine Learning: From Theory to Algorithms, Chapter 3 Remark 3.1 (standard reference, not scraped)