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

Learning a Gaussian distribution from truncated data—where observations are only available if they fall within a specific subset of the space—is a classic statistical challenge. While recent work has provided polynomial-time algorithms for this problem, existing methods often suffer from sub-optimal sample complexity or high computational costs, such as those arising from the use of the ellipsoid method or projected stochastic gradient descent. This paper asks: can we design an algorithm for halfspace truncation that matches the optimal sample and time complexity of the untruncated setting?

The authors introduce a method of moments approach that avoids the computationally intensive iterative procedures used in previous literature. By reinterpreting the low-degree moments of the truncated Gaussian, they define a relative truncation parameter that uniquely characterizes the impact of the truncation on the distribution. This allows for direct recovery of the underlying mean and covariance parameters. The algorithm first estimates a vector related to the truncation direction using the third central moment, then uses the first three moments to solve for the relative truncation parameter and the Gaussian parameters simultaneously.

The proposed algorithm achieves a sample complexity of O(d^2/ε^2) and a runtime dominated by the cost of computing the empirical covariance matrix, which is O(T(N, d)). This matches the optimal complexity of the untruncated setting, effectively allowing one to learn a Gaussian under halfspace truncation for free. The authors also extend their framework to provide a robust version of the estimator capable of handling adversarial corruption, and they demonstrate that their techniques generalize to the intersection of two orthogonal halfspaces.