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ⁿlog d), where the hidden constant depends on n, if χ is the n-dimensional Chebyshev distribution. The sample complexity is Oₙ(d²ⁿlog 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 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.