Distribution-Free Rates in Neyman-Pearson Classification

We consider the problem of Neyman-Pearson classification which models unbalanced classification settings where error w.r.t. a distribution μ₁ is to be minimized subject to low error w.r.t. a different distribution μ₀. Given a fixed VC class 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 (μ₀, μ₁). The rates involve a dichotomy between hard and easy classes H as characterized by a simple geometric condition, a three-points-separation condition, loosely related to VC dimension.