SOURCE-LINKED INTELLIGENCE

Extreme classification: beating chance with one training example from each class

arXiv · AI, language, vision and robotics · article · Sep 17, 2026 · UTC

We study a minimal classification problem: Given independent labeled observations $X\sim P$ and $Z\sim Q$ from two unknown distributions $P,Q$, and given an independent target $Y$ drawn with equal probability from $P$ or $Q$, can one classify $Y$ strictly better than chance whenever $P\neq Q$? The one-nearest-neighbor rule succeeds for every pair of multivariate Gaussian distributions with distinct means and a common positive-definite covariance matrix but can perform strictly worse than chance even for smooth densities on the real line. We construct a fixed randomized kernel rule whose expect

Read original source ↗ Open in workspace

recordType

paper

region

Global