Extreme classification: beating chance with one training example from each class
Abstract
We study a minimal classification problem: Given independent labeled observations X∼ P and Z∼ 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≠ 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 expected accuracy is exactly 1/2+MMDk2(P,Q)/4, and obtain characteristic kernels on countably generated measurable spaces from countable families of measurable binary questions. We also prove that a deterministic order rule on ℝ beats chance for every pair of distinct Borel probability measures. A measurable encoding then gives a deterministic distribution-free rule which beats chance on every countably generated measurable space, in particular every separable metric space. Finally, we show that no rule works for every distinct pair of distributions and every unknown unbalanced class prior; under adaptive target-class selection, every rule other than a fair coin is strictly worse than chance for some finitely supported pair.
Related
- Below what training size do deep tabular generators stop beating trivial baselines? A preregistered benchmark on a size ladder of clinical and standard datasets
- Extreme Binary Classification: Extreme Value Theory for Extreme Constraint on False Negative
- ChorusTIC: Training-Free Multivariate Time Series Classification via Chorus In-Context Learning
- Training More Robust Classification Model via Discriminative Loss and Gaussian Noise Injection
- Eventual convexity for separable chance constraints with skewed generalized hyperbolic random variables
BibTeX
@misc{bleakley2026extreme,
title = {{Extreme classification: beating chance with one training example from each class}},
author = {Kevin Bleakley and Aaditya Ramdas},
howpublished = {HAL},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20897},
eprint = {2609.20897},
archivePrefix = {arXiv},
url = {https://inria.hal.science/hal-05748276v1},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Extreme classification: beating chance with one training example from each class
AU - Kevin Bleakley
AU - Aaditya Ramdas
PY - 2026
DA - 2026/09/13
PB - HAL
DO - 10.48550/arxiv.2609.20897
UR - https://inria.hal.science/hal-05748276v1
AB - We study a minimal classification problem: Given independent labeled observations X∼ P and Z∼ 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≠ 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 expected accuracy is exactly 1/2+MMD_k^2(P,Q)/4, and obtain characteristic kernels on countably generated measurable spaces from countable families of measurable binary questions. We also prove that a deterministic order rule on ℝ beats chance for every pair of distinct Borel probability measures. A measurable encoding then gives a deterministic distribution-free rule which beats chance on every countably generated measurable space, in particular every separable metric space. Finally, we show that no rule works for every distinct pair of distributions and every unknown unbalanced class prior; under adaptive target-class selection, every rule other than a fair coin is strictly worse than chance for some finitely supported pair.
ER -