Hypothesis Selection via Weighted Medians

Given n distributions (hypotheses) H=H 1,,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(epsilon-2 (n/δ)) target samples, running in O(n epsilon-2 (n/δ)) time, with probability at least 1-δ, returns H i satisfying d TV(P,H i) at most 3 i in[n]d TV(P,H i)+ epsilon. 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 (n epsilon-2δ-1) of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question 2.