我们研究了学习被截断于未知半空间的高维高斯分布的基本问题。Lee、Mehrotra 和 Zampetakis（FOCS'24）最近提出了该问题的第一个多项式时间算法，但其样本和时间复杂度界限并不最优。
在非平凡截断下，对于任意目标精度 $\varepsilon > 0$ 和维度 $d$，我们提出了一种高效算法，使用 $n = \tilde{O}(d^2/\varepsilon^2)$ 个样本，并将高斯分布的误差控制在总变差距离 $\varepsilon$ 内。我们的算法运行速度快，其运行时间主要受计算经验协方差矩阵的成本影响。
我们的样本和时间复杂度在 $d$ 和 $\varepsilon$ 的情况下都是最优的，即使在没有截断的情况下：在这方面，我们可以在半空间截断下“免费”学习高斯分布。我们结果的关键在于对截断高斯的低阶矩进行新颖的重新解释，通过相对截断参数来实现。这个相对截断参数唯一确定了未截断高斯的参数，并使得直接参数恢复成为可能。
这种重新解释使我们能够绕过广泛用于截断学习的时间密集型投影随机梯度下降过程。
博主点评： 本文提出的算法在高维高斯学习领域具有重要意义，通过优化样本复杂度和运行时间，显著提升了学习效率。相对截断参数的引入为参数恢复提供了新的思路，展现了理论与实践的完美结合。值得关注的是，这一方法的普适性及其在其他领域的潜在应用。