Hypothesis Selection via Weighted Medians

Given $n$ distributions (hypotheses) $\mathcal{H}=\{H_1,\dots ,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}\log (n\mathrm{/}\delta ))$ target samples, running in $O(n{\epsilon }^{-2}\log (n\mathrm{/}\delta ))$ time, with probability at least $1-\delta$, returns $H_{\widehat{i}}$ satisfying $d_{\mathrm{T}\mathrm{V}}(P,H_{\widehat{i}})\le 3{\min }_{i\in [n]}{d}_{\mathrm{T}\mathrm{V}}(P,H_i)+\epsilon \mathrm{.}$ 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{\epsilon }^{-2}{\delta }^{-1})$ of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.