Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a novel algorithm for proper hypothesis selection from $n$ candidate distributions, aiming to find a hypothesis whose total variation distance to an unknown target distribution $P$ is near-optimal. The algorithm achieves an approximation factor of $3+\varepsilon$ and optimal sample complexity of $O(\varepsilon^{-2}\log(n/\delta))$ using $O(n\varepsilon^{-2}\log(n/\delta))$ time. This result significantly improves upon prior work by reducing the dependence on the failure probability $\delta$ from polynomial to logarithmic.
A hypothesis selection algorithm achieves optimal sample complexity and a near-optimal approximation factor while improving the state-of-the-art runtime by reducing the dependency on failure probability from polynomial to logarithmic.
Given $n$ distributions (hypotheses) $\mathcal H=\{H_1,\ldots,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(\varepsilon^{-2}\log(n/δ))$ target samples, running in $O(n\varepsilon^{-2}\log(n/δ))$ time, with probability at least $1-δ$, returns $H_{\hat i}$ satisfying $d_\mathrm{TV}(P,H_{\hat i})\leq 3\min_{i\in[n]}d_\mathrm{TV}(P,H_i)+\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 $\tilde{O}(n\varepsilon^{-2}δ^{-1})$ of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.