---
title: "Optimal Sample Complexity Fast Algorithm for Learning Gaussian under Halfspace Truncation"
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: ["Halfspace Truncation","Sample Complexity","Algorithm","Gaussian Distribution","High Dimension"]
---

# Optimal Sample Complexity Fast Algorithm for Learning Gaussian under Halfspace Truncation

## At a glance

This paper proposes an efficient algorithm for learning a high-dimensional Gaussian truncated to an unknown halfspace. The algorithm requires only Õ(d²/ε²) samples to achieve error ε in total variation distance, and both sample and time complexity are optimal in terms of dimension d and accuracy ε, even when there is no truncation. The key innovation is a novel reinterpretation of low-degree moments of the truncated Gaussian in terms of a relative truncation parameter, which directly recovers the untruncated Gaussian parameters, bypassing the time-intensive projected stochastic gradient descent procedure.

## Key points

- Sample complexity Õ(d²/ε²) is optimal, matching the untruncated case
- Runtime is dominated by computing the empirical covariance matrix, making it fast
- Novel reinterpretation via a relative truncation parameter directly recovers parameters
- Bypasses projected stochastic gradient descent, greatly improving efficiency

## Full text

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.

---

Verify against the original before citing; curated by Astral Feed: https://feed.astralor.com/items/itm_68cda38510017892021a0015