Adversarial Robustness of Nonparametric Regression

Parsa Moradi, Hanzaleh Akbarinodehi, Mohammad Ali Maddah-Ali · 2025

Read Adversarial Robustness of Nonparametric Regression by Parsa Moradi, Hanzaleh Akbarinodehi, Mohammad Ali Maddah-Ali (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-17356.txt.

Introduction

Parsa Moradi, Hanzaleh Akbarinodehi, and Mohammad Ali Maddah-Ali study curve fitting when an attacker can corrupt some of the data, in a 2025 paper. Fitting a smooth curve to data is a basic machine learning task. Its robustness has been studied for models with set formulas, but not for flexible curve methods.

Two results are given. First, a lower bound shows a limit no method can beat when a fixed share of data is corrupt. Second, a classic smoothing spline method, when properly tuned, reaches that robustness. If the share of corrupt points shrinks as data grows, its error fades away. If a fixed share stays corrupt, no method can promise fading error. The classic method is thus optimal in how much corruption it can tolerate, a result the authors call surprising.

Catalog record

CREATORParsa Moradi, Hanzaleh Akbarinodehi, Mohammad Ali Maddah-Ali
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE66 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-17356

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Adversarial Robustness of Nonparametric Regression Parsa Moradi, Hanzaleh Akbarinodehi, Mohammad Ali Maddah-Ali Abstract In this paper, we investigate the adversarial robustness of 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 ) o(n) out of n n samples are corrupted, the estimation error of the smoothing spline vanishes as n → ∞ 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. 1 Introduction In recent years, machine learning (ML) models have increasingly relied on data from diverse sources and are often deployed in distributed or decentralized computing environments [ 1 , 2 , 3 , 4 , 5 , 6 , 7 ] . These settings introduce new attack surfaces and create incentives for adversaries to corrupt data or disrupt learning algorithms [ 8 , 9 , 10 , 11 ] . This has motivated a growing body of research initiatives aimed at understanding and mitigating the impact of adversarial behavior [ 12 , 13 , 14 , 15 , 16 , 17 , 18 , 19 , 20 , 21 ] . One of the fundamental problems in ML is regression, which aims to estimate an unknown function f based on observed noisy data [ 22 ] . This task is generally categorized into two approaches: parametric regression, which assumes f is a parametric function with known structure, and nonparametric regression, which makes minimal assumptions on f , allowing it to belong to a wide class of functions such as Sobolev or Hölder spaces [ 23 , 24 ] . Regression underpins many machine learning tasks, and understanding its robustness to adversarial corruption is a critical objective. Adversarial robustness in parametric regression has been extensively studied [ 25 , 26 , 27 , 28 , 29 , 30 , 31 ] . Many approaches leverage tools from classical robust statistics [ 32 , 33 ] , adapting techniques like trimmed means, median-of-means, and M -estimators to modern high-dimensional settings [ 34 , 35 , 36 ] . These methods benefit from the structural constraints of parametric models, which narrow the hypothesis space and simplify the alleviation of adversarial attacks. In contrast, robustness in nonparametric regression is considerably more challenging due to the absence of such structure, which makes the models more vulnerable to adversarial attacks [ 37 , 38 , 39 , 40 ] . In this work, we address the problem of nonparametric regression under adversarial corruption. We consider a setting in which one observes n pairs \{(x_{i},\widetilde{y}_{i})\}_{i=1}^{n} , where the responses \widetilde{y}_{i} may be partially corrupted by an adversary. Specifically, the adversary arbitrarily choose \widetilde{y}_{i} , for any i\in\mathcal{A} , where \mathcal{A} is an unknown subset of \{1,\ldots,n\} with cardinality at most q<n . On the other hand, for each i\not\in\mathcal{A} , the observed response is given by \widetilde{y}_{i}=f(x_{i})+\varepsilon_{i} , where f\colon\Omega\to\mathbb{R} is the unknown regression function, \{\varepsilon_{i}\}_{i\in[n]\backslash\mathcal{A}} are i.i.d. noise variables with zero mean and variance \sigma^{2} . In this paper, we assume that regression function f belongs to the second-order Sobolev space, consisting of functions that are square-integrable up to the second derivative over \Omega . The objective of non-parametric regression is to produce \hat{f} as an estimation of f based on \{(x_{i},\widetilde{y}_{i})\}_{i=1}^{n} . To evaluate the performance of \hat{f} in the presence of adversarial corruption, we use the following metrics [ 24 ] : \displaystyle R_{2}(f,\hat{f}):=\mathbb{E}_{\boldsymbol{\varepsilon}}[\sup_{\mathcal{S}}\|f-\hat{f}\|_{L_{2}(\Omega)}^{2}],\qquad R_{\infty}(f,\hat{f}):=\mathbb{E}_{\boldsymbol{\varepsilon}}[\sup_{\mathcal{S}}\|f-\hat{f}\|_{L_{\infty}(\Omega)}^{2}], where \mathcal{S} denotes the strategy, chosen by the adversary, to corrupt up to q samples. Our objective is then to characterize \inf_{\hat{f}}R_{2}(f,\hat{f}) and \inf_{\hat{f}}R_{\infty}(f,\hat{f}) over all possible estimators, and any f belongs to the second-order Sobolev space. The contributions of this paper are two-fold: • A Computationally-Efficient Estimator (Theorem 1 ): We prove that the classical smoothing spline estimator retains robustness against adversarial corruption. This estimator selects \hat{f} from the second-order Sobolev space, by minimizing the empirical error \frac{1}{n}\sum_{i=1}^{n}(g(x_{i})-\widetilde{y}_{i})^{2} , regularized by \lambda\int\hat{f}^{\prime\prime}(x)^{2}\,dx , where \lambda>0 controls the level of smoothness [ 41 ] . Smoothing splines are computationally efficient, with \mathcal{O}(n) complexity of fitting and evaluating, leveraging B-spline basis functions [ 42 , 43 ] , and have found wide applications in statistics and machine learning [ 44 , 45 , 46 , 47 ] . Note that classical nonparametric methods are not necessarily adversarially robust. For instance, the Nadaraya–Watson (NW) estimator [ 48 ] can be fragile even under a small number of adversarial corruptions [ 39 ] . It is therefore surprising that a computationally efficient nonparametric regression method, such as smoothing splines, also exhibits adversarial robustness. While smoothing splines have been extensively studied in non-adversarial settings [ 41 , 49 , 50 , 51 , 52 , 53 , 54 , 55 ] , their robustness properties against adversarial corruption were not previously understood. In this paper, we show that if q=o(n) , then for the smoothing spline estimator, both R_{2} and R_{\infty} converge to zero as n\to\infty . This result also implies an upper bound on \inf_{\hat{f}}R_{2}(f,\hat{f}) and \inf_{\hat{f}}R_{\infty}(f,\hat{f}) as functions of n and q . • Minimax Lower-Bound (Theorem 2 ): We derive minimax lower bounds on \inf_{\hat{f}}R_{2}(f,\hat{f}) and \inf_{\hat{f}}R_{\infty}(f,\hat{f}) , expressed as functions of n and q . These bounds characterize the fundamental limits of estimation accuracy: no estimator can achieve better rates over the second-order Sobolev space under adversarial corruption. A key implication of this result is that when q=\Theta(n) , no estimator can achieve vanishing error as n\to\infty . This highlights that smoothing splines are not only computationally efficient but also optimal in terms of the maximum number of tolerable adversarial corruptions (see Corollary 4 ). To better understand the results of this paper, we examine their implications in the regime of large n . In this regime, our results can be concisely summarized in Figure 1 . This figure illustrates the rate of convergence, defined as -\log_{n}R_{2}(f,\hat{f}) or respectively, -\log_{n}R_{\infty}(f,\hat{f}) , as a function of q , or equivalently, \frac{\log q}{\log n}=\log_{n}q , as n\to\infty . The red curves represent the impossibility result, indicating that no estimator can achieve a convergence rate beyond this bound for all functions in second-order Sobolev space (Theorem 2 ). The blue curve shows the convergence rate of the smoothing spline estimator in the presence of adversarial samples, as established in Theorem 1 . \frac{2}{5} \frac{11}{15} 1 \frac{4}{5} \log_{n}q -\log_{n}R_{2}(f,\hat{f}) (a) Rate region for R_{2}(f,\hat{f}) . \frac{1}{2} \frac{5}{8} 1 \frac{3}{5} \frac{3}{4} \log_{n}q -\log_{n}R_{\infty}(f,\hat{f}) (b) Rate region for R_{\infty}(f,\hat{f}) . Figure

Read the complete text