Robust polynomial regression up to the information theoretic limit
This solves a fundamental robustness problem in polynomial regression for machine learning practitioners, providing the first efficient algorithm that works up to the information-theoretic limit.
The paper tackles robust polynomial regression with adversarial outliers, developing an algorithm that works for the entire feasible range of outlier probability ρ < 1/2, improving from previous methods limited to ρ < 1/log d. The algorithm achieves a factor 2 approximation, complemented by impossibility results showing even a 1.09 approximation is infeasible.
We consider the problem of robust polynomial regression, where one receives samples $(x_i, y_i)$ that are usually within $σ$ of a polynomial $y = p(x)$, but have a $ρ$ chance of being arbitrary adversarial outliers. Previously, it was known how to efficiently estimate $p$ only when $ρ< \frac{1}{\log d}$. We give an algorithm that works for the entire feasible range of $ρ< 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.