Distribution-Free Rates in Neyman-Pearson Classification
Mohammadreza M. Kalan Samory Kpotufe
We consider the problem of Neyman-Pearson classification which models
unbalanced classification settings where error w.r.t. a distribution $\mu_1$ is
to be minimized subject to low error w.r.t. a different distribution $\mu_0$.
Given a fixed VC class $\mathcal{H}$ of classifiers to be minimized over, we
provide a full characterization of possible distribution-free rates, i.e.,
minimax rates over the space of all pairs $(\mu_0, \mu_1)$. The rates involve a
dichotomy between hard and easy classes $\mathcal{H}$ as characterized by a
simple geometric condition, a three-points-separation condition, loosely
related to VC dimension.