Hypothesis Selection via Weighted Medians
In the authors' words
Given distributions (hypotheses) and samples from an unknown target distribution , proper hypothesis selection seeks a distribution whose total variation distance to is close to the best achievable within the known distributions. We give an algorithm that, using target samples, running in time, with probability at least , returns satisfying 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 of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.
Main resultThe abstract does not state a limitation.
Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.