ArXiv

When Are Trade-Off Functions Testable from Finite Samples?

2026-05-11 · 16:07 UTC ·Kaining Shi, Qiaosen Wang, Cong Ma ·1 min read

Authors: Kaining Shi, Qiaosen Wang, Cong Ma
Categories: math.ST, stat.ML
arXiv: https://arxiv.org/abs/2605.10774v1
PDF: https://arxiv.org/pdf/2605.10774v1

Brief

The paper studies finite-sample hypothesis testing for the type I/type II error trade-off function between two unknown distributions. Without structure testing is impossible; they identify exact attainability of Neyman–Pearson rejection regions by a class S and show finite VC-dimension of S is necessary and sufficient. They give a test with nonasymptotic type I control and uniform power under explicit separations, produce simultaneous confidence bands, analyze local rates (monotone likelihood-ratio) with near-matching lower bounds, and extend to approximate attainability (e.g., univariate log-concave).

Why it matters

Finite VC-dimension is necessary and sufficient: when Neyman–Pearson rejection regions for (P,Q) are attainable (up to null sets) by a prescribed class S, finite Vapnik–Chervonenkis dimension of S is both sufficient and necessary for nontrivial finite-sample testing of the trade-off curve.

Key details

They construct a test with nonasymptotic guarantees: type I error control holds without the attainability assumption, while uniform power holds over attainable alternatives satisfying an explicit separation condition; inverting the test yields simultaneous confidence bands for the entire trade-off function. Approximate attainability gives finite-sample guarantees for univariate log-concave distributions (via unions of intervals).
In the monotone likelihood-ratio model the authors derive local separation rates and prove matching lower bounds up to logarithmic factors. Paper: Kaining Shi, Qiaosen Wang, Cong Ma, arXiv:2605.10774v1, posted 2026-05-11.

Source evidence

Abstract

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.