When Are Trade-Off Functions Testable from Finite Samples?
Kaining Shi ∗, Qiaosen Wang ∗, Cong Ma · 2026
Read When Are Trade-Off Functions Testable from Finite Samples? by Kaining Shi ∗, Qiaosen Wang ∗, Cong Ma (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-10774.txt.
Introduction
Kaining Shi, Qiaosen Wang, and Cong Ma ask when a trade-off function between two distributions can be tested from finite samples. The trade-off function traces the best frontier between false alarms and missed detections in binary testing, and without structure, testing it from samples is impossible in general.
The authors find a sharp condition: when Neyman-Pearson rejection regions can be matched by a prescribed set class, finite Vapnik-Chervonenkis dimension of that class is both necessary and sufficient for meaningful testing. They build a test with finite-sample error control and invert it into simultaneous confidence bands for the whole curve. Statisticians get a clean boundary between testable and hopeless cases.
Catalog record
| CREATOR | Kaining Shi ∗, Qiaosen Wang ∗, Cong Ma |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 126949 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.10774
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
When Are Trade-Off Functions Testable from Finite Samples? Kaining Shi ∗, Qiaosen Wang ∗, Cong Ma 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 P and Q Q , we consider the problem of testing whether their trade-off function lies above a benchmark curve f 0 f_{0} or falls below a weaker benchmark f 1 f_{1} . 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 ) (P,Q) are attainable, up to null sets, by a prescribed class 𝒮 \mathcal{S} of measurable sets. Within this exact attainability framework, finite Vapnik–Chervonenkis dimension of 𝒮 \mathcal{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. * * footnotetext: These two authors contributed equally. 1 Introduction How well can two probability distributions be distinguished from finite samples? This question arises across several areas of modern statistics and machine learning. In privacy auditing 12 ; 23 , one asks whether the output distributions of a randomized mechanism on neighboring datasets are sufficiently similar to satisfy a target privacy guarantee. In tolerant distribution testing 4 , one asks whether two unknown distributions are close enough under one threshold or far enough apart under another. Although these problems are often studied separately, they share a common statistical object: the trade-off function . For two distributions P and Q on a common measurable space, the trade-off function T(P,Q) , introduced by 13 , maps each type I error level to the minimum achievable type II error when testing P against Q . It therefore gives the full Neyman–Pearson error frontier. Lower bounds on this function encode indistinguishability guarantees. For example, f -differential privacy 13 can be expressed as a uniform lower bound on the trade-off functions of neighboring output distributions, while total variation distance corresponds to a particular piecewise-linear benchmark curve. This makes the trade-off function a natural common language for a broad class of inference problems. In this paper, we study the following composite hypothesis testing problem H_{0}:\;T(P,Q)\succeq f_{0},\qquad\text{versus}\qquad H_{1}:\;T(P,Q)\not\succeq f_{1}, based on independent samples X_{1:n}\sim P and Y_{1:n}\sim Q , where f_{0}\succeq f_{1} are benchmark trade-off functions and f\succeq g means f(\alpha)\geqslant g(\alpha) for every \alpha\in[0,1] . Under the null, P and Q are at least as hard to distinguish as prescribed by f_{0} ; under the alternative, the trade-off curve falls below the weaker benchmark f_{1} somewhere. This formulation includes, as special cases, testing privacy guarantees against a benchmark profile and tolerant testing under total variation. The basic question is whether such hypotheses can be tested from finite samples. In full generality, the answer is negative. The trade-off function is an infinite-dimensional object, and without structural assumptions on the pair (P,Q) , no finite-sample procedure can estimate it accurately enough to support nontrivial uniform testing. At the other extreme, if (P,Q) belongs to a known parametric family, then the problem reduces to classical finite-dimensional inference. The interesting regime lies between these extremes: one seeks structural assumptions that are weak enough to cover broad nonparametric families, but strong enough to make the trade-off curve statistically identifiable. Our starting point is the Neyman–Pearson lemma. Writing \mu=(P+Q)/2 , p=dP/d\mu , and q=dQ/d\mu , the trade-off function is generated by the likelihood-ratio level sets \{x:q(x)>\lambda p(x)\},\qquad\lambda\in[0,\infty]. These are the rejection regions that trace out the optimal type I/type II frontier. Thus, finite-sample inference for the trade-off curve is governed by the geometry of these witness sets. If they belong to a structured family whose probabilities can be estimated uniformly, then the trade-off curve itself becomes testable. To formalize this idea, we introduce \mathcal{S} -attainability as a modeling language for classes of distribution pairs. Given a set family \mathcal{S} , a pair (P,Q) is \mathcal{S} -attainable if every Neyman–Pearson likelihood-ratio level set can be represented, up to null sets, by a member of \mathcal{S} . The class \mathcal{S} describes the geometry of the most informative tests between P and Q . For example, in a monotone likelihood-ratio model on the real line, the relevant level sets are half-lines. This formulation separates the statistical problem into two components. The first is a structural component: violations of the benchmark must be witnessed by sets in \mathcal{S} . The second is a complexity component: probabilities of sets in \mathcal{S} must be estimable uniformly from samples. Our main result shows that, within the exact \mathcal{S} -attainability framework, finite Vapnik–Chervonenkis (VC) dimension is the threshold for finite-sample testability. If \mathrm{VC}(\mathcal{S})<\infty , we construct a nonasymptotic test with uniform guarantees. If \mathrm{VC}(\mathcal{S})=\infty , no nontrivial finite-sample test exists, even when the hypotheses are separated by fixed benchmark curves. The proposed test scans over candidate rejection regions S\in\mathcal{S} and compares the empirical pair (P_{n}(S),Q_{n}(S^{c})) with the benchmark curve after applying simultaneous confidence corrections. Its validity has an important asymmetry. Type I error control is assumption-free: it holds for arbitrary distribution pairs (P,Q) , even if the pair is not \mathcal{S} -attainable. The attainability assumption is needed only for power, because it ensures that any population-level violation of the benchmark has a witness inside the search class. This feature is useful in applications such as privacy auditing, where false discoveries may be more costly than loss of power under model misspecification. 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. We derive local separation rates showing how the detectable gap between f_{0} and f_{1} depends on the local geometry of the benchmark curve. In the monotone likelihood-ratio model, we prove matching lower bounds up to logarithmic factors, showing that these local rates are essentially sharp. We also relax exact attainability to an approximate version. This gives a bias–variance trade-off: enlarging \mathcal{S} improves approximation of the optimal rejection regions but increases the uniform estimation error. As an application, we show that univariate log-concave pairs can be handled by approximating their likelihood-ratio level sets with unions of intervals. Paper organization. The rest of the paper develops this program in stages. Section 2 sets up the formal framework and establishes the impossibility of testing without structural assumptions. Section 3 develops the monotone likelihood ratio case as a warm-up. Section 4 introduces \mathcal{S} -attainability, proves the necessity of finite VC dimension, presents the general test, and inverts it into simultaneous confidence bands. Section 5 extracts local detection boundaries and establishes matching lower bounds in