Hypothesis Selection via Weighted Medians

Liang-Yu Zou

cs.DSOct 14, 2026

Hypothesis Selection via Weighted Medians

Authors: Liang-Yu Zou

Organizations: Aarhus University

Abstract

Given $n$ distributions (hypotheses) $\mathcal H=\{H_1,\ldots,H_n\}$ and samples from an unknown target distribution $P$ , proper hypothesis selection seeks a distribution whose total variation distance to $P$ is close to the best achievable within the known distributions. We give an algorithm that, using $O(\varepsilon^{-2}\log(n/δ))$ target samples, running in $O(n\varepsilon^{-2}\log(n/δ))$ time, with probability at least $1-δ$ , returns $H_{\hat i}$ satisfying $d_\mathrm{TV}(P,H_{\hat i})\leq 3\min_{i\in[n]}d_\mathrm{TV}(P,H_i)+\varepsilon.$ The algorithm achieves the optimal approximation factor and sample complexity. The running time improves the dependence on the failure probability from polynomial to logarithmic in the state-of-the-art bound $\tilde{O}(n\varepsilon^{-2}δ^{-1})$ of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.

Figures & tables

Algorithm	Running time	Failure probability	Comments
Minimum distance Yatracos (1985) ; Devroye and Lugosi (2001)	$O(n^{3}\varepsilon^{-2}\log n)$	$1/\mathrm{poly}(n)$
Modified minimum distance Mahalanabis and Stefankovic (2008)	$O(n^{2}\varepsilon^{-2}\log n)$	$1/\mathrm{poly}(n)$
Approx min distance Aliakbarpour et al. (2024)	$\tilde{O}(n/(\delta^{3}\varepsilon^{3}))$	$\delta$
Semi-distance threshold ( Aamand et al., 2026 , Theorem 1.3)	$\tilde{O}(n/(\delta\varepsilon^{2}))$	$\delta$	$\delta>1/n$
This paper, Theorem 1.1	$O(n\varepsilon^{-2}\log(n/\delta))$	$\delta$

Table 1: Proper hypothesis selection with approximation factor

3

. All rows use

O(\varepsilon^{-2}\log(n/\delta))

target samples; for polynomially small failure probability, this is

O(\varepsilon^{-2}\log n)

. More results are collected in ( Aamand et al., 2026 , Table 1) .

TV Distance Computation

See all 8 papers

Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance
Apr 15, 2025Peter Matthew Jacobs, Foad Namjoo, Jeff M. PhillipsTwo-Sample Testing Distribution Matching
University of Wisconsin–Madison, USA · University of Utah, USA
Asymmetric Likelihood-Free Hypothesis Testing
Oct 21, 2026Gunjan Kumar, Yash Pote, Jonathan ScarlettStatistical Hypothesis Testing Sample Complexity
IIT Kanpur · National University of Singapore
On the Sample Complexity of Robust Binary Hypothesis Testing
May 23, 2026Shankar Vallinayagam, Ankit Pensia, Varun JogSample Complexity Data Contamination
Department of Pure Mathematics and Mathematical Statistics, University of Cambridge · Department of Statistics, Carnegie Mellon University

Apr 15, 2025J/K move · Enter open · S save

Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance

Peter Matthew Jacobs, Foad Namjoo, Jeff M. Phillips

University of Wisconsin–Madison, USA · University of Utah, USA

Two-Sample Testing Distribution Matching Integral Probability Metrics

Open paper AskPDF arXiv

We revisit extending the Kolmogorov-Smirnov distance between probability distributions to the multi-dimensional setting, and make new arguments about the proper way to approach this generalization. Our proposed formulation maximizes the difference over orthogonal dominating rectangular ranges (d-sided rectangles in R^d), and is an integral probability metric. We also prove that the distance between a distribution and a sample from the distribution converges to 0 as the sample size grows, and bound this rate. Moreover, we show that one can, up to this same approximation error, compute the distance efficiently in 4 or fewer dimensions; specifically, the runtime is near-linear in the size of the sample needed for that error. With this, we derive a delta-precision two-sample hypothesis test using this distance. Finally, we show these metrics and approximation properties do not hold for other popular variants.

Abstract

TV Distance Computation

Explore similar work

Efficient and Stable Multi-Dimensional Kolmogorov-Smirnov Distance

Asymmetric Likelihood-Free Hypothesis Testing

On the Sample Complexity of Robust Binary Hypothesis Testing