Consistency

Definition

An algorithm producing $f_n$ from $n$ i.i.d. points is consistent for $P$ if the risk converges to the Bayes risk in probability; strongly consistent with almost sure convergence; universally consistent if it is consistent for every $P$ on $\mathcal{X}\times \mathcal{Y}$.

Formula

$$\forall \epsilon >0:\underset{n\to \infty }{\lim }P(R(f_n)-R^{\ast }>\epsilon )=0$$

• It concerns the risk, not the function: $f_n$ need not converge to $f^{\ast }$.
• It is asymptotic and gives no rate; for every fixed $n$ some distribution is still hard.
• First universally consistent algorithm: kNN with $k\to \infty$, $k/n\to 0$ (Stone 1977). Later: SVMs, boosting, random forests. 1-NN and ERM over a fixed class are not universally consistent.

Appears in

• Lecture 1.2, definitions and Stone’s theorem
• Lecture 1.2, the plug-in classifier
• Lecture 1.2, ERM is not always consistent
• Lecture 1.2, why NFL does not contradict universal consistency
• Lecture 3, consistency w.r.t. F and Bayes consistency
• Lecture 3, Theorem 7: consistency of ERM iff uniform convergence
• Lecture 3, Theorem 14: iff finite VC dimension

Related concepts

• Bayes Classifier
• Empirical Risk Minimization
• No Free Lunch Theorem