# Hypothesis Selection via Weighted Medians

arXiv: https://arxiv.org/abs/2610.20375 · HTML: https://mlsanity.com/paper/2610.20375/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 3 of its 11 references that are in the map.
- First posted on arXiv 14 Oct 2026.

## Builds on (most cited first, 3 of 3)

- [The Optimal Approximation Factor in Density Estimation](https://mlsanity.com/paper/1902.05876/) (2019)
- [Statistically Near-Optimal Hypothesis Selection](https://mlsanity.com/paper/2108.07880/) (2021)
- [How fast can you find a good hypothesis?](https://mlsanity.com/paper/2509.03734/) (2025)

## Abstract (arXiv)

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.