Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing
Abstract
When testing a composite null π« against a composite alternative π¬, it has been known since Huber and Strassen (1973) that if a least favorable distribution (LFD) pair exists, then a version of its likelihood ratio yields a minimax optimal test, and Huber (1965) derived a similar result in the sequential setting for a specific robust testing problem that is the focus of the current paper; the same likelihood ratio is log-optimal in the worst case; its expected logarithm under the alternative equals infP β π«,S β π¬ KL(S|P), whose inverse also determines the stopping time of the test under the alternative. These results focus on optimizing worst-case performance, but the resulting methods have lower power if the data come from simpler alternatives. This paper studies an arguably more practical goal of achieving asymptotic \emph{instance optimality} for ``power-one'' sequential tests, which remarkably may even be possible when π¬ = π«c. This means that when the data are drawn from any S β π«c, the test has power one, and its stopping time is determined by the larger information number infP β π« KL(S|P), which governs the performance of an oracle that knows S. To demonstrate this point, our paper focuses on the case of testing a TV ball around a discrete distribution with d components, and designs a computationally and memory efficient algorithm that is also asymptotically instance-optimal. Specifically, we consider two different asymptotic settings: one is the "Wald setting", where the type-1 error level Ξ± approaches zero for a fixed alternative S and the second is the "Farrell setting", where Ξ± is fixed and infP β π« KL(S|P) approaches $0$. Our sequential test is simultaneously optimal in both regimes.
Related
- Halve-Then-Greedy: Adaptive Sampling for Posterior Success with Near-Optimal Instance Dependence
- Instance-Optimal Adaptive Location Estimation via Multiscale Mid-Summaries
- Instance Optimal Sparse Recovery from Nonlinear Observations: A Unified Framework
- Relatively Smart II: Tractable or Semi-Supervised Instance-Optimal Learning
- The Certification Exponent: Instance-Optimal Sequential Certification of Policy Improvement from History Dependent Logs
BibTeX
@misc{saha2026beyond,
title = {{Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing}},
author = {Aytijhya Saha and Aaditya Ramdas},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.02130},
eprint = {2611.02130},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.02130},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing
AU - Aytijhya Saha
AU - Aaditya Ramdas
PY - 2026
DA - 2026/11/01
PB - arXiv
DO - 10.48550/arxiv.2611.02130
UR - https://arxiv.org/abs/2611.02130
AB - When testing a composite null π« against a composite alternative π¬, it has been known since Huber and Strassen (1973) that if a least favorable distribution (LFD) pair exists, then a version of its likelihood ratio yields a minimax optimal test, and Huber (1965) derived a similar result in the sequential setting for a specific robust testing problem that is the focus of the current paper; the same likelihood ratio is log-optimal in the worst case; its expected logarithm under the alternative equals inf_P β π«,S β π¬ KL(S|P), whose inverse also determines the stopping time of the test under the alternative. These results focus on optimizing worst-case performance, but the resulting methods have lower power if the data come from simpler alternatives. This paper studies an arguably more practical goal of achieving asymptotic \emph{instance optimality} for ``power-one'' sequential tests, which remarkably may even be possible when π¬ = π«^c. This means that when the data are drawn from any S β π«^c, the test has power one, and its stopping time is determined by the larger information number inf_P β π« KL(S|P), which governs the performance of an oracle that knows S. To demonstrate this point, our paper focuses on the case of testing a TV ball around a discrete distribution with d components, and designs a computationally and memory efficient algorithm that is also asymptotically instance-optimal. Specifically, we consider two different asymptotic settings: one is the "Wald setting", where the type-1 error level Ξ± approaches zero for a fixed alternative S and the second is the "Farrell setting", where Ξ± is fixed and inf_P β π« KL(S|P) approaches $0$. Our sequential test is simultaneously optimal in both regimes.
ER -