Adversarial Robustness of Nonparametric Regression

We thank the reviewer for the helpful feedback. Below we address the questions and will update the manuscript accordingly.

1. Some of the assumptions ... Hölder space instead?

The second-order Sobolev space is a widely studied and important functional class in nonparametric regression [2].
Regarding the Hölder space, as mentioned in the paper, there are existing works that have considered this functional setting. Specifically, Zhao et al. analyzed the robustness of an M-estimator based on the Nadaraya–Watson method under a poisoning attack model, assuming the regression function belongs to a Hölder class. Their approach improves robustness, but at the cost of increased computational complexity, specifically $\mathcal{O}(n \log(1/\epsilon))$. This implies that achieving higher accuracy comes with a corresponding increase in computational cost. Another paper studied a different adversarial model, namely, feature corruption, also within the Hölder space framework [1]. In this paper, we chose to evaluate robustness within the Sobolev setting to complement the existing literature on Hölder spaces. Moreover, the smoothing spline estimator we study admits a closed-form solution and achieves $\mathcal{O}(n)$ computational complexity. It does not involve a trade-off between accuracy and runtime.

2. The results apply...input perturbations.

Regarding the asymptotic setting, we note that the adversary enjoys substantial flexibility, which makes the theoretical analysis of the problem highly complex. Establishing asymptotic upper and lower bounds is therefore an important step toward understanding the more demanding non-asymptotic scenarios. Even in this asymptotic regime, the nonparametric nature of the problem poses significant analytical challenges.

In many problems, non-asymptotic bounds remain elusive due to technical obstacles, making it common practice to first develop a solid asymptotic analysis as a foundation.

Regarding the focus on response (label) corruption, we note that adversarial learning typically considers two main attack types:

• Label corruption (poisoning): where the adversary perturbs the labels $\{y_i\}$ while keeping inputs $\{x_i\}$ fixed.
• Input corruption: where the adversary perturbs the inputs $\{x_i\}$.

Both settings are important in practice and need to be addressed. In this work, we focus on the label corruption model, where up to $q$ labels may be arbitrarily corrupted. This already captures substantial complexity, particularly in the nonparametric setting where there are no structural constraints on the regression function.

3. One high-level ... adversarial attacks.

As discussed in the paper, regression methods generally fall into two broad categories: parametric and nonparametric. Both have wide-ranging applications across statistics and machine learning.

Parametric models assume a fixed functional form and have been extensively studied in the context of adversarial robustness. Several such works are cited in our paper. Their structured nature often makes them more amenable to theoretical and algorithmic analysis.

In contrast, nonparametric regression does not assume any specific functional form, offering greater flexibility but also introducing significant analytical challenges, particularly under adversarial corruption. Because of these difficulties, far fewer works have studied adversarial robustness in the nonparametric setting.

4. While the authors... would be beneficial.

Our setup considers a much stronger and more general adversarial model. Specifically, we allow the adversary to arbitrarily modify up to $q$ labels $\{y_i\}$, provided the corrupted values lie within a bounded range $[-M, M]$. This setup does not restrict the adversary to additive noise, it may employ arbitrary, input-dependent, and even coordinated corruption strategies, potentially tailored to the structure of the estimator.

Regarding the breakdown point, our analysis provides a precise characterization for the smoothing spline estimator. We prove that as long as the number of corrupted points satisfies $q = o(n)$, the smoothing spline estimator achieves vanishing error for any function in the second-order Sobolev space. Conversely, when $q/n$ is bounded away from zero, no estimator can guarantee vanishing error uniformly over this function class.

Finally, while the median estimator is known to have a 50% breakdown point in classical settings, this guarantee applies to point estimation of fixed parameters (e.g., estimating the mean under i.i.d. noise). Our problem, in contrast, involves nonparametric function estimation under adversarial sample corruption, a fundamentally more challenging setting, where the 50% breakdown point does not hold.

5. I do not understand ...fitted values.

While it is true that the regularization in the smoothing spline objective promotes smoothness and may intuitively mitigate the influence of outliers, the robustness of smoothing splines is not guaranteed a priori. In fact, other classical and computationally efficient nonparametric estimators, such as the NW estimator (that implicitly induces some level of smoothness through its kernel and bandwidth) , are not robust under adversarial contamination [1]. This highlights that robustness is not an automatic consequence of imposing smoothness.

What makes the smoothing spline particularly surprising and noteworthy is that it is not only robust, but also optimal., as mentioed in the above question.

6. What does $q = \theta(n^\beta)$ mean?

It means there exist constants $c_1, c_2 > 0$ such that for large $n$, $c_1 n^\beta \leq q \leq c_2 n^\beta$.

7. The authors discuss... such cases?

Please see the response to question 2.

8. In Figure 3 ...results are.

We would like to emphesize that the "best possible estimator" in this settings is not known. In fact, one of the main contributions of our work is to investigate both the achievability and the fundamental limits of estimation under adversarial corruption.

If, however, the reviewer was referring to including the theoretical upper bound from Theorem 1 in all experimental plots to better visualize the gap between empirical and theoretical performance, we agree this would be helpful. We will incorporate this in the final version to clarify how closely the smoothing spline tracks the theoretical limits.

9. The paper ... applicability.

First, we have extended our experiments as suggested. The detailed results can be found in our response to the following question.

Second, we encourage the reviewer to view this work as addressing a fundamental and core problem in robust nonparametric estimation—one that lays the groundwork for robustness in more practical and complex settings.

In particular, smoothing splines under fixed design have recently gained attention in modern machine learning architectures, including Kolmogorov–Arnold Networks (KANs) [3], SplineCNN [4], and related models [5]. These architectures are being actively used in various ML applications. Our theoretical framework and analysis offer a foundation for establishing robustness guarantees in such models, and can potentially guide the design of robust estimators in these and other neural network-based systems.

10. In the experiments ... truly are.

We have extended our experiments along several settings to address this concern.

Effect of Large $M$

Let $f(x) = x \sin(x)$ over $x \in [-1, 1]$, $M = 10$ and $q = n^{0.6}$. $\mathcal{R}_2(f,\hat{f})$

$\mathcal{R}_\infty(f,\hat{f})$

Adaptive Greedy Corruption

In this process, the attacker:

1. Fits the baseline estimator on clean data.
2. Computes $\ell_i = (\hat{f}(x_i) - y_i)^2$ for each sample: .
3. Identifies $i^\star = \arg\min_i \ell_i$.
4. Update $y_{i^\star} \leftarrow y_{i^\star} + M \cdot \operatorname{sign}(\hat{f}(x_{i^\star}) - y_{i^\star})$.
5. Repeats the process until $q$ points are corrupted.

Below are the results for $f(x) = x \sin(x)$ with $M = 100$ and input domain $[-10, 10]$: $\mathcal{R}_2(f,\hat{f})$ (log-log slope):

$\mathcal{R}_\infty(f,\hat{f})$ (log-log slope):

3. Evaluation on Neural Network Functions

We further tested our approach on a fixed 3-layer MLP neural network and $M = 500$, $\sigma^2 = 1$, and $x \in [-1, 1]$. $\mathcal{R}_2(f,\hat{f})$

$\mathcal{R}_\infty(f,\hat{f})$:

[1] Jingfu et al. Adversarial learning for nonparametric regression: Minimax rate and adaptive estimation, 2025 [2] Tsybakov et al., Introduction to Nonparametric Estimation, 2008 [3] Liu et al., Kan: Kolmogorov-arnold networks. ICLR 2025 [4] Fey et al., Splinecnn: Fast geometric deep learning with continuous b-spline kernels. CVPR 2018. [5] Doległo et al., Deep neural networks for smooth approximation of physics with higher order and continuity B-spline base functions. (2022).

We thank the reviewer for the helpful feedback. Below we address the questions and will update the manuscript accordingly.

The input is one-dimensional, which is uncommon in practical applications.

Answer:
We thank the reviewer for this comment. Indeed, our analysis focuses on the one-dimensional input setting as an initial step toward understanding adversarial robustness in nonparametric regression.

This setting is already quite challenging: unlike in parametric models, we make no structural assumptions about the underlying function class, and the adversary is allowed to follow an arbitrary contamination strategy. Moreover, as discussed in the paper, not all classical nonparametric estimators are robust in this setting, for instance, the Nadaraya–Watson estimator can be easily misled by adversarial perturbations.

We view our work as a foundational step, and we hope it lays the groundwork for extending these robustness guarantees to higher-dimensional and more complex settings in future work.

The analysis is limited to regression and label corruption.

Answer:
We thank the reviewer for this observation. In adversarial learning, two widely studied forms of attack are:

• Label corruption (poisoning): the adversary modifies the labels $\{y_i\}_{i=1}^n$ while keeping the inputs $\{x_i\}_{i=1}^n$ fixed.
• Input corruption: the adversary perturbs the input features $\{x_i\}_{i=1}^n$, possibly relocating them to adversarial positions.

Both types of corruption are important and relevant in practice. In this work, we focus on the label corruption setting—formally, we assume the adversary can arbitrarily change the values of $y_i$ for up to $q$ indices.

This setting already captures significant challenges, especially in the nonparametric regime where the function class is highly flexible and no structural assumptions are made. As shown in [Reference], even well-known classical estimators like the Nadaraya–Watson method fail to be robust under this model.

We hope this work lays the foundation for analyzing other adversarial models, including those involving corrupted inputs, in future research.

Can the theorem be extended to the case of multiple regression?

Answer:
We thank the reviewer for this question. While we are not entirely certain what is meant by "multiple regression" in this context, we assume it refers to the setting where the response variable $y$ is a vector-valued output of dimension $k$.

The answer is yes. Our analysis can be extended to this setting. In both the achievable direction, this is equivalent to applying $k$ independent smoothing splines (one for each output dimension), all using the same regularization parameter $\lambda$. The convergence rates remain the same as in the scalar case, up to a constant factor that depends on $k$. The same thing happens in lower bound derivation as the problem can be decomposed to $k$ independant problems.

Can the analysis be extended to classification and feature corruption?

Answer:
We thank the reviewer for this thoughtful question. Regarding feature corruption, we note (as discussed in earlier responses) that adversarial attacks generally fall into two broad categories:

• Label corruption (output attack): where the adversary modifies the labels $\{y_i\}$ while keeping inputs $\{x_i\}$ fixed.
• Feature corruption (input attack): where the adversary perturbs the features $\{x_i\}$.

In this paper, we focus specifically on label corruption, which is already quite challenging in the nonparametric setting due to the lack of structure in the function class and the flexibility of the adversary's strategy. Extending our analysis to include feature corruption is a natural and important next step and will likely require additional technical tools, particularly to handle the geometric aspects of input perturbation.

As for classification, this belongs to a distinct family of problems with its own objectives and complexity measures. While we do reference several robust nonparametric classification works in the related literature section, our focus in this paper is strictly on nonparametric regression under adversarial label contamination.

We view this paper as a foundational step toward broader analysis across different settings, including classification and more general corruption models.

We thank the reviewer for the helpful feedback. Below we address the questions and will update the manuscript accordingly.

1. Is kind of ... assumptions.

Our goal was to adopt a standard formulation grounded in nonparametric regression. Since classical nonparametric regression does not account for adversarial contamination, we introduced minimal extensions to accommodate such behavior within this framework. We have deliberately chosen assumptions that are both general and conventional. Specifically, we assume the regression function lies in a second-order Sobolev space, which is a standard modeling choice in nonparametric regression[1].

2. No general ... learners. No crucial insight ... splines.

We agree that identifying general theoretical principles for designing robust learners is an important long-term objective. However, due to the scarcity of existing results in this area and the flexibility of the problem formulation in nonparametric regression, we are not yet in a position to propose such general rules. At this stage, it seems we have no choice but to analyze each estimator individually, taking into account its specific assumptions, structure, and computational complexity. Notably, even well-established classical methods such as the NW estimator are not inherently robust to adversarial contamination [2].

3. Experiments ... weakness Experiments: ... why f = x sin(x)?

We have extended our experiments along several settings to address this concern.

Effect of Large $M$

Let $f(x) = x \sin(x)$ over $x \in [-1, 1]$, $M = 10$ and $q = n^{0.6}$. $\mathcal{R}_2(f,\hat{f})$

$\mathcal{R}_\infty(f,\hat{f})$

Adaptive Greedy Corruption

In this process, the attacker:

1. Fits the baseline estimator on clean data.
2. Computes $\ell_i = (\hat{f}(x_i) - y_i)^2$ for each sample: .
3. Identifies $i^\star = \arg\min_i \ell_i$.
4. Update $y_{i^\star} \leftarrow y_{i^\star} + M \cdot \operatorname{sign}(\hat{f}(x_{i^\star}) - y_{i^\star})$.
5. Repeats the process until $q$ points are corrupted.

Below are the results for $f(x) = x \sin(x)$ with $M = 100$ and input domain $[-10, 10]$: $\mathcal{R}_2(f,\hat{f})$:

$\mathcal{R}_\infty(f,\hat{f})$:

Evaluation on Neural Network Functions

Let $f(x)$ is a 3-layer MLP neural network with $M = 500$, $\sigma^2 = 1$, and $x \in [-1, 1]$. $\mathcal{R}_2(f,\hat{f})$

$\mathcal{R}_\infty(f,\hat{f})$:

4. The writing ... highlighted

Please see the response to question 1 and 7.

5. Abstract: It ... this part.

As we formally show in the paper, smoothing spline is optimal in terms of the maximum number of adversarial corruptions it can tolerate. Specifically, as long as $q/n \to 0$ as $n \to \infty$, the estimator achieves vanishing error. On the other hand, when $q/n$ is bounded away from zero, we prove that no estimator can guarantee vanishing error for all functions in the second-order Sobolev space. Therefore, in this sense, the smoothing spline achieves the best possible robustness guarantee.

While we characterize both the achievable convergence rate of the smoothing spline and the minimax lower bound, we don't claim that the smoothing spline is optimal in terms of convergence rate.

6. Typo @ line 38

We will correct them in the final version.

7. The lines from 45-48 ... unambiguous.

Our intention was to define the problem formulation by building on standard definitions from classical nonparametric regression, with appropriate references to existing baselines. However, since classical regression frameworks do not include any notion of adversarial corruption, we extended the setting to include an adversary capable of modifying up to $q$ labels. In doing so, we aimed to adopt widely accepted assumptions and evaluation metrics such as $R_2$ and $R_\infty$, which are standard in the literature [1]. While the formulation builds naturally from these foundations, we understand that some notations and definitions may initially appear dense. We try to make it more accessible to readers.

8. Typo @ Line 47

We will correct them in the fincal version.

9. Lines 124-129

It is not the case. We note that in our work, we adopt the fixed design assumption [1], where the points $\{x_i\}_{i=1}^n$ are deterministic. Still, we assume that these points satisfy a uniform convergence to a limiting distribution $p(x)$, as $n \to \infty$. This is a standard assumption in the asymptotic analysis of smoothing spline [3].

10. Line 130:

Our formulation involves two boundedness assumptions: first, we assume that the regression function is bounded by some constant $m_1$; and second, that the values chosen by the adversary are also bounded, say by $m_2$. The bound on the adversary's input is implied by the first bound, considering the variance of the additive noise in the honest samples. In our analysis, we simply define $M = \max(m_1, m_2)$.

11. Lower-bound: ... sharply near r_q?

Upper vs. Lower Bound

In the upper bound, we assume the target function $f \in \mathcal{W}^2(\Omega)$, and we introduce a specific estimator which is smoothing spline. On the other hand, the lower bound is a minimax impossibility result, where we assume $f \in \mathcal{W}^2(\Omega)$, and we derive a lower-bound for any estimator. Thus it is a valid lower-bound for the proposed solution.

Hypothesis Testing

The lower bound is derived via a reduction to a binary hypothesis testing problem, following the Proposition 5.1 of Ref. [57] in the paper. In particular, we construct two functions, $f_1$ and $f_2$, with a non-zero distance in both the $L_2$ and $L_\infty$ norms, yet are rendered statistically indistinguishable by the adversary’s attack. Specifically, the adversary modifies at most $q$ labels such that the distribution of the observed data under $f_1$ becomes indistinguishable from that under $f_2$. This implies that any estimator must incur a non-vanishing error for these two functions.

Sampling Lemma

We appreciate the reviewer for suggesting an alternative. We carefully explored this suggestion and made a sincere effort to make it work. However, our attempts fell short when dealing with the technical details.

Function Shape

In choosing $f_1$ and $f_2$, we are subject to the constraint that both functions must lie in the Sobolev space $\mathcal{W}^2(\Omega)$. We carefully design $f_2$ using a piecewise construction that satisfies the Sobolev conditions. While alternative constructions are certainly possible, the choice presented here is sufficient to establish the desired lower bound.

12. Both Upper ... novel

Upper Bound

As noted, one of our main contributions is to analyze the adversarial robustness of the smoothing spline. The error of the estimator has two sources: niose added to the honest inputs, and worst-case adversrial samples. To bound the error of smoothing spline estimator, one of our conribution is to isolate these two errros by introducing an auxiliary "all-honest" scenario. We then decompose the overall estimation error (Eq.(7) and Eq. (8)) into two terms:

• The first term measures the error of the smoothing spline estimator in the all-honest setting. This is precisely where we leverage existing results from the literature (Eq.(9) and Eq.(10)).

• The second term captures the deviation between the estimator computed on adversarial data versus the one computed on clean data. To bound this second term, we face two key challenges. First, the presence of adversarial nodes means the problem no longer fits within the classical smoothing spline framework, so existing theoretical results are not directly applicable. Second, the adversary's strategy space is infinite-dimensional, which significantly complicates the worst-case analysis. To overcome these challenges, we rely on a less commonly used kernel-based representation of the smoothing spline estimator, rather than the standard matrix-based formulation typically adopted in the literature. This choice enables us to decompose and bound the deviation term effectively. By leveraging this representation, along with tools such as equivalent kernels, norm inequalities, and Sobolev interpolation, we derive new upper bounds on the impact of adversarial contamination. Identifying and working with this alternative formulation is an important part of our technical development.

Lower Bound

To prove the lower-bound, we construct two functions $f_1$ and $f_2$ such that the following conditions are satisfied:

• Their distance in $L_2$ and $L_\infty$ norms is nonzero.
• An adversary corrupts $q$ labels, such that the corrupted data distributions under $f_1$ and $f_2$ become indistinguishable.

As a result, no estimator can determine whether the data were generated from $f_1$ or $f_2$. Designing the pair $(f_1, f_2)$ to simultaneously satisfy the smoothness and norm gap conditions, along with the explicit construction of an adversarial strategy, constitutes the core technical contribution of our lower bound analysis.

13. General Suggestion ... practice

We answered this comment in the second question.

[1] Tsybakov et al., Introduction to Nonparametric Estimation, 2008 [2] Zhao et al. Robust nonparametric regression under poisoning attack. AAAI 2024 [3] Silverman et al. Spline smoothing: the equivalent variable kernel method." The annals of Statistics, 1984

We sincerely thank the reviewer for their thoughtful and encouraging feedback. Here, we provide responses to the questions raised. We will update the final version of the manuscript accordingly.

1. Related works ... the paper.

Our Contribution

Unlike parametric regression, where robustness has been extensively studied, the nonparametric setting remains more challenging and less explored due to the lack of structural assumptions. To the best of our knowledge, our work is among the few that address adversarial robustness in nonparametric regression. A key contribution of our paper is threefold: (1) we demonstrate that the classical smoothing spline estimator, known for its high efficiency and growing popularity [1], is robust to adversarial contamination, and we characterize its convergence rate; (2) we derive minimax lower bounds for this general setting; and (3) by comparing the two, we show that the smoothing spline estimator is optimal in terms of the maximum number of tolerable outliers, provided the regularization parameter is appropriately chosen. As noted in the paper and discussed below, this robustness is not necessarily shared by other classical nonparametric methods.

Comparison to The class of NW estimators:

It has been shown that the NW estimator lacks robustness, even in the presence of a single corrupted sample [2, 3]. As discussed in the paper, concatenating the NW estimator with the Median-of-Means (MoM) procedure does not resolve this issue [4]. Concatenation of the NW estimator with the Trimmed Mean Estimator is also not robust against adversarial attacks [3]. In this method, given data $\{(x_i, y_i)\}_{i=1}^n$, the $y_i$ values are sorted, and an $\alpha$ fraction from both ends is removed to eliminate potential outliers. The NW estimator is then applied only to the remaining samples. This method is effective under scattered or uniformly distributed outliers, assuming that adversarial samples appear among both high and low extremes. For this reason, it trims data symmetrically from both ends. However, it fails under concentrated attacks. If the adversary targets a small region of the input space, many honest points may be removed during trimming, while corrupted points remain. This allows the adversary to inject a non-vanishing error into the estimator. Compared to the above methods, a key advantage of our approach is that we explicitly analyze the worst-case adversary, without assuming uniform contamination. In contrast, prior methods often rely on (implicit) assumptions of near-uniform corruption strategies.

Comparison with Kernel-Based M-Estimators:

Zhao et al. [2] propose an M-estimator based on the NW method, assuming the regression function lies in a Hölder class. Their approach improves robustness, but at the cost of increased computational complexity, specifically $\mathcal{O}(n \log(1/\epsilon))$. This implies that achieving higher accuracy comes with a corresponding increase in computational cost. In contrast, our method operates over the second-order Sobolev space, which is a different functional class. Moreover, the smoothing spline estimator we study admits a closed-form solution and achieves $\mathcal{O}(n)$ computational complexity. It does not involve a trade-off between accuracy and runtime.

Other works have studied adversarial robustness in nonparametric settings such as classification and density estimation, as covered in the paper.

2. In line 284 ... splines approach?

No, this issue does not occur in the spline approach. The smoothing spline fits a global function with regularization. This smoothness constraint limits the influence of individual outliers. As proven in the paper, the smoothing spline can tolerate up to $o(n)$ adversarial samples. In addition, we have proved that if $q/n$ stays bounded away from zero, then no estimator can achieve vanishing error for all functions in the Sobolev space.

3. In line 130 ... function?

We were unable to fully understand the second part of the question, as it appears that some words were accidentally dropped. Still, we would like to emphasize that the assumption of a bounded function over the domain is a standard practice in robustness analysis for nonparametric regression [2, 3]. The metrics we use, $R_2$ and $R_\infty$, are also well-established in the literature [5]. Our formulation involves two boundedness assumptions: first, we assume that the regression function is bounded by some constant $m_1$; and second, that the values chosen by the adversary are also bounded, say by $m_2$. The bound on the adversary's input is implied by the first bound—namely, that the adversary cannot inject arbitrarily large inputs. In our analysis, we simply define $M = \max(m_1, m_2)$. Importantly, $M$ is not a parameter used by the algorithm itself. It does not influence the computation or tuning of the estimator. Any sufficiently loose upper bound suffices, as long as it is finite. Varying $M$ affects only the constants in the theoretical bounds and not the asymptotic convergence rates.

4. There is a clear ... in Eq 12.

Note that in the original setting, a subset of nodes is honest, while the rest are adversarial. To isolate and evaluate the estimator's deviation caused by adversarial contamination, from the deviation caused by the added noise, we define a hypothetical scenario in which all nodes, including those previously adversarial, are assumed to be honest and follow the same noise model. We refer to this as the all-honest scenario. In particular, the labels in the hypothetical all-honest scenario, denoted by $y_i$, match the labels in the adversarial setting, $\tilde{y}_i$, for all $i \in [n] \setminus \mathcal{A}$. For the remaining points where $i \in \mathcal{A}$, we define $y_i = f(x_i) + \epsilon_i$, where $\epsilon_i$ follows the standard noise distribution. The key difference is that in this auxiliary setting, the honest nodes remain unchanged, while the adversarial nodes are hypothetically replaced with honest ones that generate data according to the assumed statistical model. To reflect this, we introduce a new set of noise variables for these now-honest nodes, denoted by $\hat{\epsilon}$ in line 145. We will revise the relevant section of the manuscript to clarify this modeling step and explain the motivation and notation, so the distinction is clear to the reader.

5. So the bounds in Eq 9 ... this work.

As noted, one of our main contributions is to analyze the adversarial robustness of the smoothing spline. The error of the estimator has two sources: niose added to the honest inputs, and worst-case adversrial samples. One of our conribution is to isolate these two errros by introducing an auxiliary "all-honest" scenario. We then decompose the overall estimation error (as shown in Eq. (7) and Eq. (8)) into two terms:

• The first term measures the error of the smoothing spline estimator in the all-honest setting. This is where we leverage existing results from the literature (Eq.(9) and Eq.(10)).
• The second term captures the deviation between the estimator computed on adversarial data versus the one computed on clean data. This part lies outside the scope of existing analyses of smoothing splines.

To bound the second term, we face two key challenges. First, the presence of adversarial nodes means the problem no longer fits within the classical smoothing spline framework, so existing theoretical results are not directly applicable. Second, the adversary's strategy space is infinite-dimensional, which significantly complicates the worst-case analysis. To overcome these challenges, we rely on a less commonly used kernel-based representation of the smoothing spline estimator, rather than the standard matrix-based formulation typically adopted in the literature. This choice enables us to decompose and bound the deviation term effectively. By leveraging this representation, along with tools such as equivalent kernels, norm inequalities, and Sobolev interpolation, we derive new upper bounds on the impact of adversarial contamination. Identifying and working with this alternative formulation is an important part of our technical development.

6. The experiments seem to ... value of M in practice.

For the choice of $M$, please see the answer to the question 3. In addition, we have done another experiment for a large $M$ compared to the input domain, as follows (plots are not available due to NeurIPS policy): | $M = 10,\ x \in [-1,1]$, $q = n^{0.6}$ |

7. In lie 131 ... as a constant.

Plese see the response to the question 3.

8. Isn’t the truncation ... line 248?

In trimming-based estimators, the core idea is to eliminate outliers. Consequently these methods are not robust against adversarial attacks, where the labels are strategically shifted within the acceptable range to induce an uncompensated error. As a result, this approach is NOT robust against worst-case adverserial attack (see answer to question 1). In contrast, the core idea of smoothing splines is to enforce smoothness by adding a regularization term, scaled by an appropriate factor. This imposed smoothness counterbalances adversarial shifts, even when those shifts lie within the acceptable range. This effect is implied by Theorem 1.

[1] Wahba et al., Smoothing noisy data with spline functions. 1975. [2] Zhao et al., Robust nonparametric regression under poisoning attack, AAAI 2024. [3] Dhar et al. The trimmed mean in non-parametric regression function estimation, 2022. [4] Ben-Hamou, Anna, and Arnaud Guyader. "Robust non-parametric regression via median-of-means." 2023. [5] Tsybakov et al., Introduction to Nonparametric Estimation, 2008