Robust Polynomial Regression up to the Information Theoretic Limit

We consider the problem of robust polynomial regression, where one receives samples that are usually within a small additive error of a target polynomial, but have a chance of being arbitrary adversarial outliers. Previously, it was known how to efficiently estimate the target polynomial only when the outlier probability was subconstant in the degree of the target polynomial. We give an algorithm that works for the entire feasible range of outlier probabilities, 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.

Authors

• Daniel M. Kane
• Sushrut Karmalkar
• Eric Price 0001

Keywords

• Chebyshev approximation
• Robustness
• Approximation algorithms
• Decoding
• Complexity theory
• Computer science
• Additives
• Polynomial Regression
• Robust Regression
• Polynomial Of Degree
• Problem Parameters
• Lower Bound
• Estimation Algorithm
• Linear Programming
• Constant Factor
• Uniform Density
• Probability Of Failure
• Triangle Inequality
• Chebyshev Polynomials
• Robust recovery
• Learning
• Approximation