We study the fundamental problem of learning a high-dimensional Gaussian truncated to an unknown halfspace. Lee, Mehrotra, and Zampetakis (FOCS'24) recently presented 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 provide an efficient algorithm that uses $n = \tilde{O}(d^2/\varepsilon^2)$ samples and learns the underlying Gaussian to an error of $\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.
Blogger's Review: The proposed algorithm holds significant importance in the domain of high-dimensional Gaussian learning, enhancing learning efficiency through optimized sample complexity and runtime. The introduction of the relative truncation parameter offers a novel approach to parameter recovery, demonstrating a perfect blend of theory and practice. The universality of this method and its potential applications in other fields warrant attention.