arXiv：cs.LG· Liang-Yu Zou·· 6 小时前
加权中位数实现最优假设选择，运行时间对失败概率依赖降至对数级
Hypothesis Selection via Weighted Medians
AI 导读
针对假设选择问题，新算法仅需 O(ε^-2 log(n/δ)) 个目标分布样本、O(nε^-2 log(n/δ)) 运行时间，以至少 1-δ 概率返回满足 d_TV(P,H_î) ≤ 3min_i d_TV(P,H_i)+ε 的假设，达到最优近似因子与样本复杂度。
正文
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/\delta))$ target samples, running in $O(n\varepsilon^{-2}\log(n/\delta))$ time, with probability at least $1-\delta$, 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}\delta^{-1})$ of Aamand, Aliakbarpour, Chen, and Silwal (COLT 2026), thereby answering their Question~2.
| Subjects: | Data Structures and Algorithms (cs.DS); Machine Learning (cs.LG) |
| Cite as: | arXiv:2610.20375 [cs.DS] |
| (or arXiv:2610.20375v1 [cs.DS] for this version) | |
| https://doi.org/10.48550/arXiv.2610.20375 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Liang-Yu Zou [view email]
[v1]
Wed, 14 Oct 2026 15:45:01 UTC (16 KB)
来源：arXiv：cs.LG · arxiv.org