Distribution-Free Rates in Neyman-Pearson Classification

Abstract

We consider the problem of Neyman-Pearson classification which models unbalanced classification settings where error w.r.t. a distribution _1 is to be minimized subject to low error w.r.t. a different distribution _0. 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 (_0, _1). 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.

Tasks

Reproductions