Robust polynomial regression up to the information theoretic limit

Abstract

We consider the problem of robust polynomial regression, where one receives samples $(x_i,y_i)$ that are usually within $\ddot{I}ƒ$ of a polynomial $y=p(x)$, but have a $\ddot{I}$ chance of being arbitrary adversarial outliers. Previously, it was known how to efficiently estimate $p$ only when $\ddot{I}<\frac{1}{\log d}$. We give an algorithm that works for the entire feasible range of $\ddot{I}<1/2$, while simultaneously improving other parameters of the problem. We complement our algorithm, which gives a factor 2 approximation, with impossibility results that show, for example, that a $1.09$ approximation is impossible even with infinitely many samples.

19 Pages. To appear in FOCS 2017