Hypothesis Selection via Weighted Medians

arXiv:2610.20375v1 Announce Type: cross 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(arepsilon^{-2}log(n/elta)) target samples, running in O(narepsilon^{-2}log(n/elta)) time, with probability at least 1-elta, returns H_{hat i} satisfying d_TV(P,H_{hat i})leq 3min_{iin[n]}d_TV(P,H_i)+arepsilon. 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 ilde{O}(narepsilon^{-2}elta^{-1}) of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.

Source: arXiv cs.LG | 2026-10-15