Adversarial Robustness of Nonparametric Regression
This addresses a fundamental gap in machine learning for nonparametric regression, providing theoretical limits and a robust estimator, though it is incremental as it builds on existing parametric robustness studies.
The paper tackles the adversarial robustness of nonparametric regression by characterizing it under data corruption, establishing a minimax lower bound on estimation error and showing that a regularized smoothing spline estimator is robust, with error vanishing if o(n) samples are corrupted but no estimator can guarantee vanishing error if a constant fraction is corrupted.
In this paper, we investigate the adversarial robustness of nonparametric regression, a fundamental problem in machine learning, under the setting where an adversary can arbitrarily corrupt a subset of the input data. While the robustness of parametric regression has been extensively studied, its nonparametric counterpart remains largely unexplored. We characterize the adversarial robustness in nonparametric regression, assuming the regression function belongs to the second-order Sobolev space (i.e., it is square integrable up to its second derivative). The contribution of this paper is two-fold: (i) we establish a minimax lower bound on the estimation error, revealing a fundamental limit that no estimator can overcome, and (ii) we show that, perhaps surprisingly, the classical smoothing spline estimator, when properly regularized, exhibits robustness against adversarial corruption. These results imply that if $o(n)$ out of $n$ samples are corrupted, the estimation error of the smoothing spline vanishes as $n \to \infty$. On the other hand, when a constant fraction of the data is corrupted, no estimator can guarantee vanishing estimation error, implying the optimality of the smoothing spline in terms of maximum tolerable number of corrupted samples.