Introduction
Polynomial regression is a fundamental tool in statistics and machine learning for modeling complex relationships between variables. However, standard techniques like Ordinary Least Squares are highly susceptible to outliers—data points that deviate significantly from the underlying model due to noise or adversarial corruption. While robust univariate polynomial regression has seen recent breakthroughs, the multivariate case presents significant geometric challenges. This work introduces the first efficient algorithm for robust multivariate polynomial regression, capable of handling an outlier fraction of nearly 50%.
Problem Statement
The goal is to recover an unknown $n$-variate polynomial $p$ of degree $d$ in each variable from a set of samples. The data consists of:
- Inliers: Points where the observed value $y$ satisfies $|y - p(x)| \leq \sigma$.
- Outliers: Points that appear with probability $\rho < 1/2$ and can take arbitrary, even adversarial, values.
The objective is to output a polynomial $\hat{p}$ such that the maximum error $\|\hat{p} - p\|_\infty$ is bounded by $O(\sigma)$ over the entire domain $[-1, 1]^n$.
Methodology: Chebyshev Partitioning and Median Filtering
The core of the proposed approach is a generalization of the "Median-based recovery" framework to higher dimensions. The algorithm employs several key strategies:
Multivariate Chebyshev Partitioning
The $n$-dimensional cube $[-1, 1]^n$ is divided into a grid of cells. The boundaries of these cells are defined by the extrema of Chebyshev polynomials. This specific partitioning ensures that even with random samples, each cell contains enough "good" data points to represent the polynomial's local behavior.
Median-Based Filtering and Iterative Refinement
Within each cell, the algorithm calculates the median of the observed $y$-values. Because outliers constitute less than half of the data, the median remains a robust estimator of the true polynomial value. The algorithm then uses these medians to find a coarse approximation and iteratively refines it to "zoom in" on the true polynomial. To ensure computational efficiency regardless of initial coefficient size, an $\ell_1$ regression "warm start" is used to provide a reasonably close initial guess.
Theoretical Results and Sample Complexity
The authors provide rigorous proofs for the algorithm's performance under different sampling distributions. A key technical contribution is proving that any multivariate polynomial can be well-approximated by a piecewise constant function on a Chebyshev grid, justifying the use of cell medians.
As shown in the table above, the sample complexity is optimal relative to the degree $d$. For the $n$-dimensional Chebyshev distribution, the complexity is $O_n(d^n \log d)$, while for the Uniform distribution, it is $\tilde{O}_n(d^{2n})$. The algorithm also explicitly handles finite-precision arithmetic ($N$-bit precision), making it applicable to real-world computational constraints.
Key Insights
- Robustness of the Median: By partitioning the domain finely, the global outlier problem is reduced to local problems where the median consistently extracts the signal.
- Markov-type Inequality: The authors established a new inequality relating the $\ell_\infty$ (maximum) error to the $\ell_1$ (average) error for multivariate polynomials, showing that $\|\hat{p} - p\|_\infty \leq d^{2n} \|\hat{p} - p\|_1$. This is critical for the success of the $\ell_1$ warm-start phase.
Conclusion
This research provides a robust framework for multivariate polynomial regression that reaches the information-theoretic limit for outlier tolerance ($\rho < 1/2$). While the algorithm is efficient for constant dimensions, it faces the "curse of dimensionality" as complexity scales exponentially with $n$. Future work may explore structured polynomials (e.g., sparse models) to mitigate this scaling or investigate whether the approximation factor can be improved further toward the ideal limit.
Summary updated