# Distribution-Free Rates in Neyman-Pearson Classification

arXiv: https://arxiv.org/abs/2402.09560 · HTML: https://mlsanity.com/paper/2402.09560/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 29 references that are in the map.
- First posted on arXiv 14 Feb 2024.

## Builds on (most cited first, 10 of 10)

- [The Optimal Sample Complexity of PAC Learning](https://mlsanity.com/paper/1507.00473/) (2015)
- [Quadratically Regularized Subgradient Methods for Weakly Convex Optimization with Weakly Convex Constraints](https://mlsanity.com/paper/1908.01871/) (2019)
- [Bayes-Optimal Classifiers under Group Fairness](https://mlsanity.com/paper/2202.09724/) (2022)
- [Neyman-Pearson (NP) classification algorithms and NP receiver operating characteristics (NP-ROC)](https://mlsanity.com/paper/1608.03109/) (2016)
- [A Generalized Neyman-Pearson Criterion for Optimal Domain Adaptation](https://mlsanity.com/paper/1810.01545/) (2018)
- [Neyman-Pearson classification: parametrics and sample size requirement](https://mlsanity.com/paper/1802.02557/) (2018)
- [EDIMA: Early Detection of IoT Malware Network Activity Using Machine Learning Techniques](https://mlsanity.com/paper/1906.09715/) (2019)
- [Neyman-Pearson Classification under High-Dimensional Settings](https://mlsanity.com/paper/1508.03106/) (2015)
- [GBM-based Bregman Proximal Algorithms for Constrained Learning](https://mlsanity.com/paper/2308.10767/) (2023)
- [Neyman-Pearson and equal opportunity: when efficiency meets fairness in classification](https://mlsanity.com/paper/2310.01009/) (2023)

## Built on by (most cited first, 3 of 3)

- [Concentration and excess risk bounds for imbalanced classification with synthetic oversampling](https://mlsanity.com/paper/2510.20472/) (2025)
- [Neyman-Pearson Classification under Both Null and Alternative Distributions Shift](https://mlsanity.com/paper/2511.06641/) (2025)
- [Classification with Abstention Under Class-Conditional Error Constraints](https://mlsanity.com/paper/2609.22632/) (2026)

## Abstract (arXiv)

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.