arXiv preprint ·
Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testing
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
When testing a composite null $\mathcal{P}$ against a composite alternative $\mathcal{Q}$, 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 \in \mathcal{P},S \in \mathcal{Q}} 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 $\mathcal{Q} = \mathcal{P}^c$. This means that when the data are drawn from any $S \in \mathcal{P}^c$, the test has power one, and its stopping time is determined by the larger information number $\inf_{P \in \mathcal{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 \in \mathcal{P}} KL(S\|P)$ approaches $0$. Our sequential test is simultaneously optimal in both regimes.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Statistics Theory
Transport for Conditional Sampling: Foundations and Applications
Sketching in Regression: Sketchy in Practice?
Instance-Specific Sharp Convergence Rate of the Add-$λ$ Estimator via Feature Space Decomposition
Calibrated Multiaccuracy: Deterministic and Randomized Sample Complexity
Federated Estimation of Loading Spaces in Tensor Factor Models under Differential Privacy
Get the few papers worth your time in Statistics Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.