Optimal Robust Linear Regression in Nearly Linear Time

Yeshwanth Cherapanamjeri, Efe Aras, Nilesh Tripuraneni +3

We study the problem of high-dimensional robust linear regression where a learner is given access to $n$ samples from the generative model $Y=⟨X,w^{\ast }⟩+\epsilon$ (with $X…