# When Are Trade-Off Functions Testable from Finite Samples?

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 12 of its 23 references that are in the map.
- First posted on arXiv 11 May 2026.

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

- [Privacy Auditing with One (1) Training Run](https://mlsanity.com/paper/2305.08846/) (2023)
- [Detecting Violations of Differential Privacy](https://mlsanity.com/paper/1805.10277/) (2018)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Auditing f-Differential Privacy in One Run](https://mlsanity.com/paper/2410.22235/) (2024)
- [Property Testing for Differential Privacy](https://mlsanity.com/paper/1806.06427/) (2018)
- [Collision-based Testers are Optimal for Uniformity and Closeness](https://mlsanity.com/paper/1611.03579/) (2016)
- [The Price of Tolerance in Distribution Testing](https://mlsanity.com/paper/2106.13414/) (2021)
- [Optimal Algorithms and Lower Bounds for Testing Closeness of Structured Distributions](https://mlsanity.com/paper/1508.05538/) (2015)
- [A Randomized Approach for Tight Privacy Accounting](https://mlsanity.com/paper/2304.07927/) (2023)
- [General-Purpose f-DP Estimation and Auditing in a Black-Box Setting](https://mlsanity.com/paper/2502.07066/) (2025)
- [Exploring the Gap between Tolerant and Non-tolerant Distribution Testing](https://mlsanity.com/paper/2110.09972/) (2021)
- [Testing Imprecise Hypotheses](https://mlsanity.com/paper/2510.20717/) (2025)

## Abstract (arXiv)

We study finite-sample inference for the trade-off function of two unknown probability distributions, the function that traces the optimal type I/type II error frontier in binary testing. Given samples from distributions P and Q, we consider the problem of testing whether their trade-off function lies above a benchmark curve f0 or falls below a weaker benchmark f1. Without structural restrictions, this problem is impossible uniformly over nonparametric classes. We identify a sharp condition under which it becomes possible. The key structural assumption is that the Neyman--Pearson rejection regions for (P,Q) are attainable, up to null sets, by a prescribed class S of measurable sets. Within this exact attainability framework, finite Vapnik--Chervonenkis dimension of S is both sufficient and necessary for nontrivial finite-sample testing. We construct a test with nonasymptotic error guarantees: type I error control is valid without assuming attainability, while power holds uniformly over attainable alternatives satisfying an explicit separation condition. By inverting the test, we also obtain simultaneous confidence bands for the whole trade-off curve. Finally, we study the sharpness and robustness of the procedure. In the monotone likelihood-ratio model, we derive local separation rates and prove matching lower bounds up to logarithmic factors. We also allow approximate, rather than exact, attainability; this extension yields finite-sample guarantees for univariate log-concave distributions by approximating their rejection regions with unions of intervals.