arxivcs.DScs.LGmath.STstat.ML2026-06-25
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
Haitong Liu, Deepak Narayanan Sridharan, David Steurer, Manuel Wiedmer
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…