DefinitionDefinition: Literature-sourcedProof: Not applicablePipeline-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.

Population and empirical risk

Definition

For a supervised prediction problem with joint law $P$ , the population risk of any measurable predictor $f : X \to A$ (in particular, every $f \in F$ ) is the extended nonnegative integral $R_{P} (f) : = \int_{X \times Y} ℓ (f (x), y) P (d (x, y)) \in [0, + \infty] .$ For an ordered sample $S = ((x_{1}, y_{1}), \dots, (x_{m}, y_{m}))$ of length $m \geq 1$ , the empirical risk or training risk of any such $f$ is ${\hat{R}}_{S} (f) : = \frac{1}{m} \sum_{i = 1}^{m} ℓ (f (x_{i}), y_{i}) \in [0, + \infty] .$ Neither definition assumes finite risk. The sum uses extended nonnegative arithmetic; since $m \geq 1$ , any summand equal to $+ \infty$ makes the empirical risk $+ \infty$ .

Definition references

Supervised prediction problems: fixes the measurable spaces, joint law, predictor class and loss.

Expectation of a nonnegative or integrable random variable: the expectation of a nonnegative measurable function is its extended integral.

Depends on

Used by

Approximate empirical risk minimization with a supplied selector Algorithm
Finite-list empirical risk minimization Algorithm
Stochastic gradient descent Algorithm
ERM excess risk from Rademacher uniform deviation Corollary
A data-dependent prior can invalidate the PAC-Bayes bound Counterexample
Bayes predictors and excess risk Definition
Binary learning minimax excess risk Definition
Binary surrogate classification risk Definition
Empirical risk minimizers Definition
Latent-class contrastive representation learning Definition
Margin-preserving compression of score classifiers Definition
Measurable PAC learning criteria for a possibly infinite VC class Definition
Multiclass margins, ramp loss, and empirical margin loss Definition
One-hidden-layer particle-measure model Definition
Realizable and agnostic PAC learning Definition
Source and target joint laws, risks, and covariate shift Definition
A finite-support sample-compressed classifier Example
A nearest-neighbor rule can have unit deletion instability and zero training loss Example
A nonattained risk infimum Example
Absolute loss and conditional medians Example
Absolute-loss RKHS regularization has an explicit stability envelope Example
Binary zero-one loss and risk Example
Squared loss and a conditional mean Example
Training accuracy, algorithmic stability, and class-wide Rademacher bounds Example
Two indistinguishable laws leave error on an unseen atom Example
Uniform empirical-risk sampling gives an unbiased bounded-variance gradient Example
Binary zero-one excess risk with a zero-score error convention Lemma
Population and empirical risks are measurable Lemma
Exact labels, slow version-space shrinkage, and abstention limits Remark
A conditional Bayes rule minimizes population risk Theorem
Agnostic sample complexity for finite-VC ERM Theorem
Expected generalization from uniform stability Theorem
Expected generalization of convex stochastic gradient training Theorem
Expected generalization of nonconvex stochastic gradient training Theorem
Finite-class agnostic ERM bound Theorem
Finite-class realizable PAC bound Theorem
High-probability generalization from uniform stability 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

…and 6 more results.

Dependency tree · two levels

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