---
title: "半空间截断下高斯分布学习的最优样本复杂度快速算法"
source: "arXiv AI/CL/LG（论文）"
source_tier: "t2"
url: "https://arxiv.org/abs/2606.27298v1"
permalink: "https://feed.astralor.com/items/itm_68cda38510017892021a0015"
published: "2026-06-25T17:14:57.000Z"
score: 53
channel: "ai"
tags: ["半空间截断","样本复杂度","算法","高斯分布","高维"]
---

# 半空间截断下高斯分布学习的最优样本复杂度快速算法

## 速览

本文提出一种高效算法，用于学习未知半空间截断下的高维高斯分布。该算法仅需Õ(d²/ε²)个样本即可达到总变差距离误差ε，并且样本复杂度和时间复杂度在维度d和精度ε上均达到最优，即使在没有截断的情况下也是如此。关键创新在于重新解释截断高斯分布的低阶矩，引入相对截断参数，从而直接恢复未截断的高斯参数，避免了耗时的投影随机梯度下降过程。

## 关键点

- 样本复杂度Õ(d²/ε²)达到最优，与无截断情形下相同
- 算法时间复杂度主要由计算经验协方差矩阵决定，非常高效
- 提出相对截断参数的新解释，直接恢复未截断高斯参数
- 避免了投影随机梯度下降，显著提升效率

## 全文

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.

---

引用前请核对原文;本文由星际流动整理:https://feed.astralor.com/items/itm_68cda38510017892021a0015