Deepak Narayanan Sridharan

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…Read more