Outlier Robust Multivariate Polynomial Regression

We study the problem of robust multivariate polynomial regression: let pⁿ be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (xᵢ, yᵢ) -1, 1ⁿ R that are noisy versions of (xᵢ, p (xᵢ) ). More precisely, each xᵢ is sampled independently from some distribution on -1, 1ⁿ, and for each i independently, yᵢ is arbitrary (i. e. , an outlier) with probability at most < 1/2, and otherwise satisfies |yᵢ-p (xᵢ) |. The goal is to output a polynomial p, of degree at most d in each variable, within an _-distance of at most O () from p. Kane, Karmalkar, and Price FOCS'17 solved this problem for n=1. We generalize their results to the n-variate setting, showing an algorithm that achieves a sample complexity of Oₙ (dⁿ d), where the hidden constant depends on n, if is the n-dimensional Chebyshev distribution. The sample complexity is Oₙ (d^2n d), if the samples are drawn from the uniform distribution instead. The approximation error is guaranteed to be at most O (), and the run-time depends on (1/). In the setting where each xᵢ and yᵢ are known up to N bits of precision, the run-time's dependence on N is linear. We also show that our sample complexities are optimal in terms of dⁿ. Furthermore, we show that it is possible to have the run-time be independent of 1/, at the cost of a higher sample complexity.