# How fast can you find a good hypothesis?

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Sep 2025.

## Built on by (most cited first, 1 of 1)

- [Hypothesis Selection via Weighted Medians](https://mlsanity.com/paper/2610.20375/) (2026)

## Abstract (arXiv)

In the hypothesis selection problem, we are given sample and query access to finite set of candidate distributions (hypotheses), H = H1, ldots, Hn, and samples from an unknown distribution P, both over a domain X. The goal is to output a distribution Q whose distance to P is comparable to that of the nearest hypothesis in H. Specifically, if the minimum distance is mathsfOPT, we aim to output Q such that, with probability at least 1-δ, its total variation distance to P is at most C · mathsfOPT + varepsilon. The optimal approximation for proper algorithms (where Q ∈ H) is C=3 using Theta(log(n/δ)/varepsilon2) samples from P and for improper algorithms (where Q is not necessarily in H) is C=2 using tildeTheta(log(n/δ)/varepsilon2) samples from P. In the improper setting, the algorithm achieving C=2 [Bousquet, Braverman, Kol, Efremenko, Moran, FOCS 2021] runs in time which grows polynomially with |X| -- it does not run in finite time for real-valued distributions. A promising path towards improved runtime is to consider improper algorithms which output a mixture Q of the hypotheses as such a distribution can be represented in n words of memory. We show (1) a lower bound that no algorithm which outputs a mixture can achieve approximation better than C = 3-2/n unless the number of samples is polynomial in |X|, as well as (2) an algorithm which runs in time poly(n) and achieves the same approximation guarantee. In the proper setting, [Aliakbarpour, Bun, Smith, NeurIPS 2024] provided an algorithm with C=3 running in tildeO(n/(δ3varepsilon3)) time. We improve this time complexity to tildeO(n/(δ varepsilon2)), significantly reducing the dependence on the confidence and error parameters.