Universal Consistency of Learning Rules

Most machine learning guarantees you'll encounter — VC bounds, PAC bounds — are stated for a fixed data distribution, or at best a class of distributions with some assumed structure. A stronger and more demanding question is: does an algorithm eventually find the best possible predictor no matter what the true data-generating distribution turns out to be, with no assumptions on it at all? A learning rule with that property is called universally consistent.

Formally, a rule is universally consistent if, as the number of training samples $n \to \infty$, its expected error converges to the Bayes-optimal error (the best any predictor could possibly achieve, given the true but unknown relationship between features and label) — and this convergence holds for every distribution over the feature-label pairs, not just well-behaved ones. The $k$-nearest-neighbor classifier, with $k$ growing slowly with $n$ (like $k \approx \sqrt{n}$), is a classic example proven universally consistent; so are certain histogram-partition rules and, under suitable conditions, single hidden-layer neural networks with growing width.

The catch is that universal consistency is a statement purely about the limit as data goes to infinity — it says nothing about how fast that convergence happens for any real, finite sample size. Two universally consistent rules can differ enormously in how many samples they need to get close to Bayes-optimal on a given real dataset, so the property is reassuring in principle (the algorithm isn't fundamentally broken for some class of problems) but gives no guidance at all on which algorithm to actually pick for a finite quant dataset of, say, ten years of daily data.