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.

Supervised prediction problems

Definition

A supervised prediction problem consists of nonempty measurable spaces $(X, Σ_{X})$ of instances, $(Y, Σ_{Y})$ of labels, and $(A, Σ_{A})$ of prediction actions; the product measurable space $(X \times Y, Σ_{X} \otimes Σ_{Y})$ ; a probability measure $P$ on that product; a nonempty class $F$ of measurable predictors $f : X \to A$ ; and a loss $ℓ : A \times Y \to [0, + \infty]$ that is measurable with respect to $Σ_{A} \otimes Σ_{Y}$ . The law $P$ need not be supported on a deterministic labeling function, and this definition imposes no assumption that sample observations be independent or share a common law.

Definition references

Measurable spaces and measurable sets: a measurable space is a set with a specified sigma-algebra.

A measurable function between measurable spaces: a function is measurable when preimages of measurable sets are measurable.

The product sigma-algebra and its finite iterates: the product sigma-algebra is generated by measurable rectangles.

Probability measures and probability spaces: a probability measure has total mass one.

Loss functions and risk: a loss is nonnegative and measurable in the action variable; risk is an extended nonnegative integral.

Remarks

The joint law $P$ can be used at a fixed member of a statistical experiment. If it is selected from a parametric family, this prediction definition makes no parameter-recovery claim, and the family of laws need not distinguish parameter labels.

Remarks references

Statistical experiments: an experiment is a measurable sample space with a parameter-indexed family of probability measures.

Parametric statistical models: the parameter-to-law map need not be injective.

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
Bayes predictors and excess risk Definition
Binary learning minimax excess risk Definition
Binary surrogate classification risk Definition
Deterministic sample-compression schemes Definition
Empirical risk minimizers Definition
Finite pool-based realizable active-learning instance Definition
Latent-class contrastive representation learning Definition
Margin-preserving compression of score classifiers Definition
Multiclass margins, ramp loss, and empirical margin loss Definition
Population and empirical risk Definition
Probability calibration and calibration error Definition
Realizable and agnostic PAC learning Definition
Source and target joint laws, risks, and covariate shift Definition
Uniform stability for randomized learning rules Definition
A nearest-neighbor rule can have unit deletion instability and zero training loss Example
A nonattained risk infimum Example
A smooth quadratic loss without global Lipschitzness has unbounded stability 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
Uniform empirical-risk sampling gives an unbiased bounded-variance gradient Example
A finite label has a conditional probability function 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
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
Target risk bound by source risk, H-delta-H divergence, and joint error Theorem
The unlabeled marginal alone does not identify labels Theorem

…and 1 more result.

Dependency tree · two levels

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