Hypothesis Selection via Weighted Medians

Given n distributions (hypotheses) mathcal H=H1,ldots,Hn 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-2log(n/δ)) target samples, running in O(nvarepsilon-2log(n/δ)) time, with probability at least 1-δ, returns Hhat i satisfying dTV(P,Hhat i)≤ 3mini∈[n]dTV(P,Hi)+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 tildeO(nvarepsilon-2δ-1) of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.