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

Kevin Bleakley, Aaditya Ramdas

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$…