提出高效算法，用最少样本学习被截断的高维正态分布。
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
- 通过重定义截断参数，直接恢复原始正态分布参数。
- 仅需 $\tilde{O}(d^2/\varepsilon^2)$ 样本即可在总变差距离下达到 $\varepsilon$ 精度。
- 相比已有方法显著提速，适合高维数据中带截断的分布学习场景。
我们研究高维正态分布被未知半空间截断下的学习问题。Lee、Mehrotra 和 Zampetakis（FOCS'24）首次提出多项式时间算法，但其样本与时间复杂度非最优。针对非平凡截断情形，对任意精度 $\varepsilon > 0$ 和维度 $d$，本文给出一种高效算法，仅需 $n = \tilde{O}(d^2/\varepsilon^2)$ 样本，即可将底层正态分布学习至总变差距离 $\varepsilon$ 的误差。该算法运行时间主要由经验协方差矩阵计算决定，且样本与时间复杂度在无截断时已为最优，意味着在截断下学习正态分布无需额外代价。核心思想是将截断正态分布的低阶矩重新解释为相对截断参数的函数，该参数唯一确定未截断分布的参数，从而实现直接参数恢复，避免了传统中耗时的投影随机梯度下降过程。
原文摘要 · Abstract (English)
We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra and Zampetakis (FOCS'24) recently obtained the first polynomial time algorithm for this problem, but their resulting sample and time complexity bounds are not optimal. Under non-trivial truncation, for any target accuracy $\varepsilon > 0$ and dimension $d$ we give an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to error $\varepsilon$ in total variation distance. Our algorithm is also fast: its runtime is dominated by the cost of computing the empirical covariance matrix. Both our sample and time complexity are optimal in terms of $d$ and $\varepsilon$ even without truncation: in this regard, we can learn a Gaussian under halfspace truncation for free. The key ingredient behind our result is a novel reinterpretation of the low-degree moments of the truncated Gaussian in terms of a relative truncation parameter. This relative truncation parameter uniquely determines the parameters of the untruncated Gaussian and enables direct parameter recovery. This reinterpretation allows us to circumvent the time intensive projected stochastic gradient descent procedure that is widely used in learning under truncation.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。