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.

Population and empirical risks are measurable

Statement

In a supervised prediction problem, for every measurable predictor $f$ , the function $(x, y) \mapsto ℓ (f (x), y)$ is measurable, so its population risk is a defined extended nonnegative integral. For every sample size $m \geq 1$ , the empirical risk $S \mapsto {\hat{R}}_{S} (f)$ is an extended nonnegative measurable function on the finite product sample space.

Facts & Assumptions

Given: A supervised prediction problem, a measurable predictor $f \in F$ , and a positive integer $m$ . The sample domain is $(X \times Y)^{m}$ with its recursively formed product sigma-algebra.

[F1]

Predictors are measurable, and the loss is measurable on the action-label product. Supervised prediction problems

[F2]

The product sigma-algebra is generated by measurable rectangles and finite products are formed recursively. The product sigma-algebra and its finite iterates

[F3]

Population risk is the nonnegative integral of $(x, y) \mapsto ℓ (f (x), y)$ , and empirical risk is its finite sample average. Population and empirical risk

[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]

A map is measurable when preimages of measurable sets are measurable; preimages under a composition are taken successively. A measurable function between measurable spaces

[F6]

An extended-real-valued function is measurable when all of its strict-superlevel preimages are measurable. Extended-real-valued measurable functions

Proof

Given: A supervised prediction problem, a measurable predictor $f$ , and a sample size $m \geq 1$ .

1.1F1F2F3F5

Define $Φ_{f} (x, y) = (f (x), y)$ . For each measurable rectangle $U \times V$ in $A \times Y$ , its preimage is $f^{- 1} (U) \times V$ , which belongs to $Σ_{X} \otimes Σ_{Y}$ by measurability of $f$ . Since the rectangles generate the target product sigma-algebra by [F2], $Φ_{f}$ is measurable by [F5]. Therefore $ℓ_{f} : = ℓ \circ Φ_{f}$ is measurable by successive preimages in [F5] and nonnegative; [F3] defines $R_{P} (f) = \int ℓ_{f} d P$ .

2.1givenF2F3F4F5F6step 1.1∎

For each coordinate $i \in {1, \dots, m}$ , the sample projection $π_{i} : (X \times Y)^{m} \to X \times Y$ is measurable by the finite product construction in [F2]. Hence $S \mapsto ℓ_{f} (π_{i} (S))$ is measurable by [F5]. The finite sum $s (S) : = \sum_{i = 1}^{m} ℓ_{f} (π_{i} (S))$ is a defined nonnegative extended-real function and is measurable by [F4]. Since $m > 0$ , for every real $a$ we have ${S : s (S) / m > a} = {S : s (S) > m a}$ , including when $s (S) = + \infty$ . Thus $s / m$ is measurable by the strict-superlevel criterion [F6], and [F3] gives measurability of $S \mapsto {\hat{R}}_{S} (f)$ .

Depends on

Used by

Approximate empirical risk minimization with a supplied selector Algorithm
Finite-list empirical risk minimization Algorithm
ERM excess risk from Rademacher uniform deviation Corollary
A data-dependent prior can invalidate the PAC-Bayes bound Counterexample
Binary learning minimax excess risk Definition
Latent-class contrastive representation learning Definition
A finite-support sample-compressed classifier Example
The finite-list ERM selector is measurable Lemma
Exact labels, slow version-space shrinkage, and abstention limits Remark
Agnostic sample complexity for finite-VC ERM Theorem
Importance weighting under covariate shift Theorem
Masked-diffusion KL reduces to weighted cross-entropy Theorem
One-sided VC uniform convergence and the finite-class branch Theorem
Realizable sample complexity for finite-VC classes Theorem
The PAC-Bayes KL generalization bound Theorem
The sample-compression generalization bound Theorem
VC entropy uniform deviation without a logarithmic sample-size factor Theorem

Cited to discharge well-definedness by Population and empirical risk.

Dependency tree · two levels

21 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)
Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar, Foundations of Machine Learning, 2nd ed., Chapter 2 §2.1 (standard reference, not scraped)