在假设选择问题中，我们通过样本和查询访问有限的候选分布集（假设）$\mathcal{H} = \{H_1, \ldots, H_n\}$，以及来自未知分布 $P$ 的样本，目标是输出一个分布 $Q$，其与 $P$ 的距离与 $\mathcal{H}$ 中最近的假设相当。
具体来说，如果最小距离为 $\mathsf{OPT}$，我们希望以至少 $1-\delta$ 的概率输出 $Q$，使其与 $P$ 的总变差距离至多为 $C \cdot \mathsf{OPT} + \varepsilon$。
对于适当算法（即 $Q \in \mathcal{H}$），最佳近似为 $C=3$，需要从 $P$ 获得 $\Theta(\log(n/\delta)/\varepsilon^2)$ 个样本；而对于不适当算法（即 $Q$ 不一定在 $\mathcal{H}$ 中），$C=2$，需要 $\tilde{\Theta}(\log(n/\delta)/\varepsilon^2)$ 个样本。
在不适当的设置中，达到 $C=2$ 的算法 [Bousquet, Braverman, Kol, Efremenko, Moran, FOCS 2021] 的运行时间随着 $|\mathcal{X}|$ 多项式增长，对于实值分布无法在有限时间内运行。
一个有前景的改进运行时间的方向是考虑输出假设混合的非适当算法，因为这样的分布可以用 $n$ 个字的内存表示。
我们展示了 (1) 一个下界，即没有输出混合的算法能够在样本数量是 $|\mathcal{X}|$ 的多项式情况下实现更好的近似 $C = 3-2/n$，以及 (2) 一个运行时间为 $\text{poly}(n)$ 的算法，且实现相同的近似保证。
在适当设置中，[Aliakbarpour, Bun, Smith, NeurIPS 2024] 提供的算法以 $C=3$ 运行时间为 $\tilde{O}(n/(\delta^3\varepsilon^3))$。我们将此时间复杂度改进为 $\tilde{O}(n/(\delta \varepsilon^2))$，显著减少了对置信度和误差参数的依赖。
博主点评： 本文探讨了假设选择的复杂性，为算法优化提供了新思路。尤其是在不适当假设的情况下，提出的混合输出方法为实际应用中的效率提升提供了可能性，值得深入研究。整体而言，作者在时间复杂度上的改进具有重要的理论与实践意义。