arXiv preprint ·
Hypothesis Selection via Weighted Medians
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
Abstract
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Data Structures & Algorithms
Learning-Augmented Streaming Algorithms for Approximating Boolean Max-CSPs
Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
Approximation Algorithms for Emergency Vertex Cover with Few Stations and Fault-Tolerant Coverage
A 0.4584-approximation for DR-submodular maximization over down-closed convex sets
Revisiting Non-Adaptive Set Membership Schemes: Removing the Logarithmic Factor
Get the few papers worth your time in Data Structures & Algorithms every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.