标题： 统计上接近最优的假设选择 显示英文标题

标题： Statistically Near-Optimal Hypothesis Selection

摘要： 假设选择是一个基本的分布学习问题，其中给定一个比较类$Q=\{q_1,\ldots, q_n\}$的分布，以及对一个未知目标分布$p$的抽样访问，目标是输出一个分布$q$，使得$\mathsf{TV}(p,q)$与$opt$接近，其中$opt = \min_i\{\mathsf{TV}(p,q_i)\}$和$\mathsf{TV}(\cdot, \cdot)$表示总变分距离。 尽管这个问题自19世纪以来就已经被研究，但其在基本资源（如样本数量和近似保证）方面的复杂性仍未解决（例如，在Devroye和Lugosi `00的迷人著作中进行了讨论）。 这与其他（更年轻的）学习设置形成了鲜明对比，例如PAC学习，这些复杂性已经得到了很好的理解。 我们为假设选择问题推导出一个最优的$2$-近似学习策略，输出$q$使得$\mathsf{TV}(p,q) \leq2 \cdot opt + \eps$，具有几乎最优的样本复杂度~$\tilde O(\log n/\epsilon^2)$。 这是第一个同时达到最佳近似因子和样本复杂度的算法：之前，Bousquet、Kane 和 Moran（COLT `19）提出了一种学习者，实现了最优的$2$-近似，但样本复杂度为$\tilde O(\sqrt{n}/\epsilon^{2.5})$，这要差得多；而 Yatracos~(Annals of Statistics `85) 提出了一种具有最优样本复杂度$O(\log n /\epsilon^2)$的学习者，但近似因子为$3$，这不是最优的。 显示英文摘要

摘要： Hypothesis Selection is a fundamental distribution learning problem where given a comparator-class $Q=\{q_1,\ldots, q_n\}$ of distributions, and a sampling access to an unknown target distribution $p$, the goal is to output a distribution $q$ such that $\mathsf{TV}(p,q)$ is close to $opt$, where $opt = \min_i\{\mathsf{TV}(p,q_i)\}$ and $\mathsf{TV}(\cdot, \cdot)$ denotes the total-variation distance. Despite the fact that this problem has been studied since the 19th century, its complexity in terms of basic resources, such as number of samples and approximation guarantees, remains unsettled (this is discussed, e.g., in the charming book by Devroye and Lugosi `00). This is in stark contrast with other (younger) learning settings, such as PAC learning, for which these complexities are well understood. We derive an optimal $2$-approximation learning strategy for the Hypothesis Selection problem, outputting $q$ such that $\mathsf{TV}(p,q) \leq2 \cdot opt + \eps$, with a (nearly) optimal sample complexity of~$\tilde O(\log n/\epsilon^2)$. This is the first algorithm that simultaneously achieves the best approximation factor and sample complexity: previously, Bousquet, Kane, and Moran (COLT `19) gave a learner achieving the optimal $2$-approximation, but with an exponentially worse sample complexity of $\tilde O(\sqrt{n}/\epsilon^{2.5})$, and Yatracos~(Annals of Statistics `85) gave a learner with optimal sample complexity of $O(\log n /\epsilon^2)$ but with a sub-optimal approximation factor of $3$.