ArXiv

Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity

2026-06-25 · 17:14 UTC ·Haitong Liu, Deepak Narayanan Sridharan, David Steurer... ·1 min read
Authors
Haitong Liu, Deepak Narayanan Sridharan, David Steurer...
Categories
cs.DS, cs.LG, math.ST, stat.ML
arXiv
https://arxiv.org/abs/2606.27298v1
PDF
https://arxiv.org/pdf/2606.27298v1

Brief

The paper addresses learning a high-dimensional Gaussian truncated to an unknown halfspace and introduces a reinterpretation of low-degree moments in terms of a relative truncation parameter that uniquely identifies the underlying Gaussian. Using this insight the authors give an algorithm with sample complexity n = Õ(d^2/ε^2) and runtime dominated by empirical covariance computation, matching optimal bounds and removing the need for projected SGD; accepted to COLT 2026.

Why it matters

For any ε>0 and dimension d the authors give an efficient algorithm that learns a Gaussian truncated by an unknown halfspace using n = Õ(d^2/ε^2) samples and with runtime dominated by computing the empirical covariance matrix (paper claims this is optimal in d and ε).

Key details

  • Key technical idea is a novel reinterpretation of low-degree moments via a relative truncation parameter that uniquely determines the untruncated Gaussian, enabling direct parameter recovery and avoiding the projected stochastic gradient descent used by Lee, Mehrotra & Zampetakis (FOCS'24). Paper (88 pages) accepted to COLT 2026; posted 2026-06-25.
Source evidence

Abstract

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.

Comment: 88 pages; accepted at the 39th Annual Conference on Learning Theory (COLT 2026)