Outlier Robust Multivariate Polynomial Regression

We study the problem of robust multivariate polynomial regression: let pcolonℝn→ℝ be an unknown n-variate polynomial of degree at most d in each variable. We are given as input a set of random samples (xi,yi) ∈ [-1,1]n × ℝ that are noisy versions of (xi,p(xi)). More precisely, each xi is sampled independently from some distribution chi on [-1,1]n, and for each i independently, yi is arbitrary (i.e., an outlier) with probability at most ρ < 1/2, and otherwise satisfies |yi-p(xi)|≤σ. The goal is to output a polynomial hatp, 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 On(dnlog d), where the hidden constant depends on n, if chi is the n-dimensional Chebyshev distribution. The sample complexity is On(d2nlog 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 log(1/σ). In the setting where each xi and yi 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 dn. Furthermore, we show that it is possible to have the run-time be independent of 1/σ, at the cost of a higher sample complexity.