3 papers
cs.DS2026
Fast algorithms for learning a Gaussian under halfspace truncation with optimal sample complexity
Haitong Liu, Deepak Narayanan Sridharan, David Steurer +1
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 polyn…
cs.DS2026
On efficient robust regression with subquadratic samples
Deeksha Adil, JarosÅaw BÅasiok, Hongjie Chen +1
We revisit the problem of robust linear regression under Gaussian covariates with an unknown covariance matrix of condition number . For this fundamental problem, significant g…
cs.DS2024
Outlier-robust Mean Estimation near the Breakdown Point via Sum-of-Squares
Hongjie Chen, Deepak Narayanan Sridharan, David Steurer
We revisit the problem of estimating the mean of a high-dimensional distribution in the presence of an -fraction of adversarial outliers. When is at most…