Adversarial Robustness of Nonparametric Regression
Authors: Parsa Moradi
Hanzaleh Akbari Nodehi
Mohammad Ali Maddah-Ali
Venue: NeurIPS 2025 poster ()
Keywords: Nonparametric regression
Adversarial Robustness
Smoothing Spline
Primary area: theory

Abstract: 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.

Adversarial Robustness of Nonparametric Regression
Parsa Moradi University of Minnesota moradi Gumn, edu
Hanzaleh Akbarinodehi" University Minnesota akbar066@umn. edu
Mohammad Ali Maddah-Ali University Minnesota
maddah@umn.
Abstract
In this paper, we investigate the adversarial robustness nonparametric regression, 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., is square integrable up to its second derivative).
The contribution of this paper is two-fold: (i) we establish minimax lower bound the estimation error, revealing fundamental limit that estimator 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 of the smoothing spline vanishes
oc. 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.
Introduction
In recent years, machine learning (ML) models have increasingly relied data from diverse sources and are often deployed distributed or decentralized computing environments [177]. These settings introduce new attack surfaces and create incentives for adversaries to corrupt data or disrupt learning
algorithms [8 This has motivated a growing body of research initiatives aimed at understanding
and mitigating the impact of adversarial behavior 11-21.
One of the fundamental problems 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 ff is a parametric function with known structure, and nonparametric regression, which makes minimal assumptions
f. allowing it to belong 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 critical objective.
Many ap- adapting techniques like trimmed M-estimators to modern high-dimensional settings [4]66] 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
Adversarial robustness parametric regression has been extensively studied 21.
proaches leverage tools from classical robust statistics 32 33
means, median-of-means.
In this work, we address the problem of nonparametric regression under adversarial corruption. We consider a setting which one observes n pairs {(x, V.) where the responses V may be
Equual contribution.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

partially corrupted by an adversary. Specifically, the adversary arbitrarily choose Dr. for all i E A. where is an unknown subset of {1..... n with cardinality at most q < n. For each & A, the observed response is V/i [mxa + Ei. where f: Ω + R is the unknown regression function with domain Q TR, and (Ei)ve())aa are i.i.d. noise variables with zero mean and variance at most o².
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 Q2 The objectíve of non non-param non-parametric regression is to produce f as an estimation of f based on {( 3s) }+));=1 To evaluate the performance of f in the presence of adversarial corruption, we use the following metrics (2
R2(J, = Ee sup || - 11
(J, = Ee sup f1l.....) (0))
where E =
and S denotes the adversarial strategy that can corrupt up to q samples. Our goal is to characterize inf, R2 f) and inf, Ro over all estimators, assuming f belongs to the second-order Sobolev space, under the setting where the adversary may corrupt up q samples.
The contributions of this paper are two-fold:
A Computationally-EFni Effiicien Estimator (Theorem 1: We prove that the classical smoothing spline estimator retains robustness against adversarial corruption. This esti- mator selects f from the second-order Sobolev space, by minimizing the empirical error E
), regularized by A f (=)) dr, where À 0 controls the level of smoothness [4]] Smoothing splines are computationally efficient, with (nz) complexity of fitting and evaluating, leveraging B-spline basis functions [42] 43], and have found wide applications in statistics and machine learning [44. Note that classical nonparametric methods are not necessarily adversarially robust. For instance, the Andaraya-Watson (NW) estimator [48] can be fragile even under small number of adversarial corruptions (39). It is therefore surprising that a computationally efficient nonparametrie regression method, such smoothing splines, also exhibits adversarial robustness.
While smoothing splines have been extensively studied in aon-adversarial settings [41 49 55), their robustness properties against adversarial corruption were not previously under- stood. In this paper, we show that if the adversary corrupts most q o(n) samples and the regression function f belongs to a second-order Sobolev space, then the smoothing spline estimator achieves R2 -> and Rx -
- co. This result further provides an upper bound on inf R2 f) and inf Roc (f. f) as functions of and q.
Minimax Lower-Bound (Theorem 2 : We derive minimax lower bounds on inf R2 f) and inf Rao f), expressed functions of 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 (nn). no estimator can achieve vanishing error as + oo. This highlights that smoothing splines are not only computationally effi- cient 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 [ This figure illustrates the rate of convergence, defined
log, R2(ʃ, f') respectively, log, R (f, as a function of g, or equivalently, log n log, q. as n + oc. The red curves represent the impossibility result, indicating that no estimator can achieve a convergence rate beyond this bound for all functions in second- -odeer Sobolev space (Theorem 2). The blue curve shows the convergence rate of the smoothing spline estimator the presence of adversarial samples, as established Theorem [
log
It is worth noting that, as shown in Figure la when log,, q < g. the smoothing spline achieves the Linimax-optimal convergence rate for metric R2 For 2 < log,, (g) < 1, in metric R2 (Figure Iap. and for < log, (q) < in metric Rxo (Figure [b), while the smoothing splines offers vanishing estimation enror for large the rate of convergence may not be optimum (there is a gap between the rate of convergence smoothing splines and the minimax outer-bound). This theoretical results are supported with the simulation experiments results (see Section 4).

---

logn f))
logn Rox (f,
logn !
logn !
11 15
1
(a) Rate region for R).
(b) Rate region for R ff.
Figure 1: Rates of convergence for estimation error R2(f, f) and R& (f. f). as n - 00, and for any f belongs second-order Sobolev space (for non-asymptotic analysis, see Theorems and 2 The blue curves represent the minimum rate achieved by the smoothing spline estimator. The red curves denote minimax outer bounds that are impossible beat. Specifically, for g = o(n). for the smoothing spline estimator, both R2 and R& converge to zero show that no estimator can achieve vanishing error, establishing a fundamental limit on robustness. This result highlights that smoothing splines are optimal in terms of the maximum tolerable number of adversarial corruptions (see Corollary
- oc. When q ((n), we
This paper is organized as follows. Section 2 presents the problem formulation. Section 3 presents main results by providing an upper and lower bounds under adversarial corruption. Section provides simulation results, and Section reviews related works.
Throughout the paper, we use [m]] := (1,2.....,n) and denote the cardinality of a set A by [A]. Derivatives of scalar functions written as f", f", and, more generally, f(a) for the k-th derivative. The quantities ( and || denote the L2-norm and the supremum norm of a function g()) over f2. The space (² refers to the second-order Sobolev space, consisting of square-integrable functions on Ω whose first and second derivatives are also equare-integrable We write a S to indicate that there exists a constant C >> O such that a S Cb, and similarly a 2 to mean Cb for some constant C 0.
Notation.
Ω.
2 Problem Formulation
Let f [a, b) + be in (T( b)). The objective is to estimate S. from observations at fixed design points I; E (a, for [m). Instead of observing noisy version of responses (as in standard regression problem (2 ), we are given (possibly) adversarially corrupted outputs {ū/ )= defined as:
V: = [(ax)) Eis if A, A
where (Es)ie(n) A are i.i.d. noise variables with zero mean and variance at most 0², and A C [n] is an unknown subset of indices corresponding to adversarially corrupted observations. Here, denotes an arbitrary value chosen strategically by the adversary to mislead the estimator. We assume [A] S for some known q E N.
Let Ω == [a denote the domain of the design points, and e = (cs) denote the noise vector.
Following [24] we evaluate the performance of any estimator f using metries, R2 f) and
Ros (f), where
Ba(J.) = Eg
sup S
s (20)
R Ro. = Er
sup
f - Loo (9)
(2)
S
3

---

where S denotes the strategy, chosen by the adversary, in choosing the subset A and the value of jıs- for i A, as long as A q. The supremum over S considers the worst-case adversarial attack, aiming to maximize estimation error for f-
In this paper, the objective to find f, that minimizes f2(J.f) or (oo f), over all possible estimator functions f. where ff is an arbitrary function (2())).
3 Main Results
In this section, present main results on the adversarial robustness of nonparametric regression. Without loss of generality, we assume that Ω [0, 1 Let {zi) C S2 denote the set of design points, and W (12) be the regression function.
First, we evaluate the robustness of the classical cubic smoothing spline estimator under adversarial corruption. In Theorem I
show that this estimator, computationally efficient [42 43 and
widely pepular estimator [4), exhibits robustness to adversarial corruption.
The cubic smoothing spline estimator is defined as the solution to the following optimization problem:
n
fss arg min s0W
Σ (g(x))
(o(x:) - Di)² A (o)( de
n
Here, À 0 is smoothing parameter that balances the fitness to the sample data, measured by + (g(a) 72,², and smoothness of the estimator, quantified by Ja ge (r.
We define the empirical distribution function Fn associated with the design points {a,)
" (x = m Σ
1x S x))
where (rx; S x)) is the indicator function. We assume that Fn, converges uniformly to continuously differentiable cumulative distribution function (CDF) F; that is,
sup (F) F(x)) + 0 zEit
This is a standard assumption in the related literature 24 For the limiting CDF, i.e., F(x), we assume that the density function p(x) == F'(x) exists. In addition, similar to (39 49 we assume that p(x) is bounded away from zero, i.e., there exists a constant Pmin > 0 such that inf p(z) 2 Pmino and that p(x) is three times continuously differentiable on Ω.
We assume that the function f is bounded; that is, for all E Ω2 [f(x) S my for some constant mi E R. Moreover, we assume that the adversary's 's corrupted values are also bounded, i.e., the adversary cannot inject arbitrarily large perturbations, satisfying [ S my for my R and i E A.
Finally, let Amax := supxen minje(m] Jr æ;l, Amin min |x; xzyl denote the maximum gap from any point in to the nearest design point, and the minimum separation between any two design points, respectively. Likewise to [50], assume that their ratio is bounded by constant, i.e., A A < k, for some >> O, ensuring that the design points are neither arbitrarily sparse nor overly clustered.
Theorem 1 (Upper Bound). Let f W²()), and let fgs denote the smoothing spline estimator defined in (3. Let M = max[mm; m2). Assume that X + 0 as n xo and X n Then, for sufficiently large n, we have
R2(5, S / (x)) dr o²
(M + +
(5)
nd1/4
1/22/2
and also
(o. S 1/4 (a (o)) de nAT/4
(M2 + 02)
6
1²11/2
Noote that any function f: |a, b) R can be transformed with scaling and shifting into function f: [0, 1] R without affecting its Sobolev regularity or the scaling of the associated metrics.

---

For the proof details, see Appendix A Here, we present proof sketch: We first decompose each metric into two components using the triangle inequality. Specifically, we have
2
R2(f, fis) - 2 E
sup s
fss
+ 2 2
sup 5
sss
fss
(7)
[2(()]
[22
(s, (5,))) S 2 2
sup ||
Sss
2
+ 2 2
sup
Jss fs' (8)
(8)
La
(0))
where iss denotes the smoothing spline estimator fitted on clean (uncorrupted) data. More precisely, we have
1 Σ (u g(x;))) + / (x)( dx j
fss == arg
min
g (EW)(
with y; = yi, for i E [,, and otherwise, for E A. y; = f(x;) + c₁ for some i.dd e,. addition, have (G))
The first term in each decompositions 7 and (8) quantifies the estimator's error the absence of adversarial contamination, reflecting the classical estimation error. The second term, referred to as adversarial deviation, captures how much the adversarial estimator fgs deviates from its uncorrupted counterpart fas-
To bound the first term in decomposition 77. spline estimation [50 51). which guarantee that, for sufficiently large ni we have
we rely on an established upper bounds for smoothing
Ea -
153 f()
$ 1(2-1)/2 J (F)( de nx2H+1)44
(9)
Applying (9) with yields the desired bound for the first term decomposition 7 For decomposition (8). the first term is bounded by combining (9) with j = and j 1, applying norm inequalities for Sobolev spaces [56), and using the Cauchy- Schwarz inequality, leading to
Ee ||
iss
F. (8))
I X-11
(2// (T))))) dr nxIAT
o²
(10)
To bound the second term in decompositions (7) and (8), we leverage the fact that the smoothing spline estimator is linear smoother [4]] Specifically, the solution can be expressed in a kernel form as
n Σ (x,
Fo (z)
(11)
where Wr, W....)) denotes the smoothing spline kernel (or weight funetion), which depends the design points (2i (Zi))e(m) sample size n, and the smoothing parameter X. Using this representation, we have
[fs((x) (x)
n Σ W (2, (u
x))
(o)
Σ
Wn(z, (v1 [i)
(12)
iEA
where (a) follows from the fact that ys = ü. for E [n].AA Using the Hölder inequality, and taking expectation, we show that
(M² 1 02)
Ee sup Jis
Ass
Ee
sup S.EE0.JEIn)
(W,(2, xT)
(13)
(2(0)
n²
Unfortunately, W does not admit an analytically tractable form its supremum 13). However, a substantial body of research (3 has focused on approximating (..:.)) with analytically tractable functions, known as equivalent kernels, denoted by W.,,,,), s). We leverage such approximations in our analysis derive an upper bound for [3). leading to
52
53
for directly bounding
q2(M2 +
Ex sup
La
fss
x
(14)
L2(03)
n²A1/2
5

---

We also take similar steps to derive
( + 0²)
Eg
sup
Sss
fss
(15)
1221//2
Combining 9 (10) 14 and 15) completes the proof of Theorem
Corollary 1 (Convergence Rate of R2(f. f)). Assume the conditions of Theorem 1 hold. and q= ( for some 3 E [0. 1]. Then, by choosing À ( 3 S 0.4 and X O(n 4/3(1-8))
for 3 > 0.4, we have
for < 0.4, O (n 4/-4
inf R2(S.)) S R2(s,
(16)
O (n 4/34(11111)
for 0.4,
as depicted by the blue curve in Figure la
Corollary (Convergence Rate of (f. f)). Under the same assumptions as in Corollary | by choosing À (n 4 for S 0.5 and On (/5(1-8))_0
- for B > 0.5, we have
0 (n 3/3) for B < 0.5, 0 0/5(1-8)) for B > 0.5,
inf (S, S Roo (J, fss)
(17)
as depicted by the blue curve in Figure Tb
Based on Corollaries 1 and 2 the thresholds B = 0.4 for R2(s, [Ss) and 0.5 for (S iss indicate a phase transition: Below these points, the estimation error dominated by noise, and adversarial corruption has impact on the convergence rate. Beyond these thresholds, the adversary dictates the rate of convergence. In this scenario, we must choose a larger smoothing parameter À to smooth out the adversarial contribution in the data points.
Furthermore, for all / E [0, 1). the convergence rate of (s. fss) is slower than that of R2(f, fss). as established by Theorem This reflects the greater sensitivity of Ro estimation error to adversarial attacks: while metric R2 averages the estimation error across the entire domain, metric Rox. is driven by the worst-case pointwise error, making it inherently more vulnerable to adversarial perturbations.
In the following theorem we provide a minimax lower bound for both metrics.
Theorem Let Pe denote the probability density function of the noise vector e, with i.id zero-mean x² variance entries, J E W2 (2) be the regression function. Then
inf sup R2(f, f) 2 4
(18)
4//
f J.S.P.
n
inf sup Rec (f. f) 2 2 +
log 3//
(19)
f S.S.P
n
n
The full proof of Theorem is provided in Appendix B Here, we present proof sketch. To establish
Theorem 2] we reduce the minimax risk (18) and (99 to hypothesis testing problem [57]. Specifically, we construct two functions Si and f2 in (T with La and Lox distance, bounded away from zero (see Figure 2). However, given n samples from either function, an adversary can corrupt up to g of them, making it impossible for any estimator to reliably distinguish between Si and fz. Consequently, no estimation approach can identify which function generated the data, and the average hypothesis testing error remains 1/2. Applying (57 Proposition 5.1] yields the following lower bounds:
inf sup Bz(f.f) 2 (r
(20)
f S.S.Pe
inf sup R.o (S, î) 2
(21)
f J.S.P.
Furthermore, when q 0, the adversarial model reduces the classical non-adversarial setting, for which the minimax lower bounds have been established as inf sup,,,r R2(f.f) 2 -4/5 and
inl i sup Roso (S.f) Z (logn/n)3/4 24
Combining these with 20 and (1 completes the
proof of Theorem 2

---

(1 =0 f2(Ø)
Fq
6q
T
Eg
1
Figure 2: Construction functions Ji (blue) and f2 (red) used Theorem Both functions belong to ( IJ), where fi (a:) 0 for all æ. and (2(): differs from fi only on the interval [0, rg), with ro q/n. The function f2 is linear on [0, Egg. where Eg = r... and transitions smoothly to zero on [ra - Eg. [g] via degree-5 polynomial, ensuring /2 E ([o, 1J). This construction induces a non-zero gap in both Lg and Loc norms, while enabling the adversary to obscure the difference by corrupiing only samples, and making f1, f2 statistically indistinguishabl.. The details of this construction is provided Appendix B
Corollary 3. Assuming q O(r²) for some B [0, 1). we conclude from Theorem that
0 (n 4/5)
for B < 11
inf sup R2(f, 2
(22)
f S.S.P.
10 (n 10--11110
for B > T5
11
0 (n -3/4)
for $ <
inf sup (o.
Ô (n 221-9)))) for Se
(23)
f S.S.P.
as depicted by red curves in Figure Corollary 4 (On optimality of Smoothing Spline). Assume the conditions of Theorem 7 hold and that = o(n). Then, by selecting the smoothing parameter X = = when 2 n and
-0.8 when q n-, R2(f. vanishes as n. + co. Similarly, for R (f: fss). setting = (2)8/5 when q 2 0.5 and X = n 00.8 when q < n. 0.5 ensures that Ri (f f8s) also converges zero. Consequently, as long as q o(n), then Ra( fis) and (J fās) ( go zero,
co. Conversely, if O(n), according to Corollary 3 there exists a function f E W2 such that, for any estimator f. none of R2(f. f) and Ro (f, f) converges to zero as - cc. This implies that the classical cubic smoothing spline estimator is optimal with respect to maximum tolerable number of adversarial corruptions.
4 Experimental Results
In this section, we present numerical experiments to validate the theoretical results. All experiments conducted single CPU-only machine. The smoothing spline estimator is implemented using the SciPy package [58]. We consider two regression functions: (i) f(x) x sin(r) over the domain Q - 10, 10] with M 100, and (ii) three-layer MLP network with weights initialized [-1, 1] and MM = 500. The noise vector is drawn independently from Gaussian distribution with zero
mean and variance x²
To evaluate the adversarial robustness of the cubic smoothing spline estimator, we consider three distinct attack strategies:
Random Corruption Attack: The adversary randomly selects g out of the n samples and replaces their response values with M.
Greedy Corruption Attack: In this process, the attacker:
1. Fits the baseline estimator on clean data.
2. Computes E, = (f(x)) ) for each sample.
3. Identifies i* = arg min; &
7

---

0 22
7 n
log Ho J D
log (f f)
Random Actack, Slope na -1 1.20
Random Attock, Slope -1.41
Consantaated Attack, Slap
Cumantza Atlack, Skyp
Groedy Attack Slope 1.58
Gready Attock, Slopa
151
log(n)
log(n)
06
9 of
log R
Tog Rix
Random Attock, Slape
Random Atrack, Slope ro
Concentrated Attack, Slope -0.63
Concentrated Attack. Slaze -0.18
Gready Attack, Slope
Greeely Attack, Slops
log(n)
log(n)
Figure 3: Log-log plots of error convergence rates for the cubic smoothing spline estimator f= fāg for (xx) = x sin(x:) in the uniform design setting, where the input points converge a uniform distri- bution. The top row shows R2(f, f) and (f. errors for n.3 along with the corresponding theoretical upper bounds of O(n -0.8) and On -0.),, respectively. The bottom row presents (2 and R. (f. errors for q n.6, with theoretical upper bounds of (n-55.5) and O(n -0.15) respectively.
4. Updates + + M sign (z..) ye-)
5. Repeats the process until g points corrupted.
Concentrated Corruption Attack: The adversary targets q consecutive samples centered around the median of the design points and modifies their corresponding labels to M.
For each attack strategy, we evaluate both (2( fia) and Roo (f, f&s) across range of sample sizes n. and examine how these metrics scale with n under varying levels adversarial corruption. Additionally, for each experiment, Gaussian. In the uniform and Gaussian settings, the design points { converge to a uniform and truncated Gaussian distribution over Ω respectively,
consider two settings for the design points: uniform and
For the function f(x) x sin(r), Figures and illustrate the behavior of R2(J, and Ro (S, f under uniform and Gaussian designs, respectively, for corruption levels, q n 0.3 and = 0.6 Similarly, for the MLP network, Figures 6 present the corresponding results.
As shown in these figures, the empirical convergence rates align well with the theoretical upper bounds established in Theorem Specifically, Theorem establishes that R2 fo (nn-0.8) and
Rox (J. fg S On for q = n 0.3, and R2(ʃ. S S (0.5333) and Roo (S, f S O(n -0.18) for q 0.6 These thcoretical predictions align with the empirical convergence trends observed in

---

n
0 = 11
log H n
log Ro )
Random Slope 1.37
Random Actack, Slope ry 1.37
Comcentrated Astack, Slops -11
Concentrated Attack. Slage -0.3
Grondy Attack Slope -.54
Greedy Attack, Slope -1.44
log(n)
log
n6
n
log C,
Randem Attack, Blope -0.8
Random Artack, Slope -055
Concentrated Attack, Slope i -0.55
Concentrated Attack. Slooe -1,18
Greedy Attack, Slope -1.88
Greedy Attack, Slope -1.38
(ng(n)
log(
Figure 4: Log-log plots showing the convergence behavior of the cubic smoothing spline estimator
= fō when the ground-truth function is the MLP network, under the uniform design setting. The top row corresponds to the case n.333 with theoretical convergence rates of ((n-0.8) for R2 (f. and On for (f, f). The bottom row shows results for higher corruption level, q 6.6, with respective theoretical upper bounds of Onn -0.53) and O(n -0.48).
the figures. Moreover, these figures show that the concentrated attack results in noticeably higher estimation error compared to the other two attack strategies.
is important note that these empirical rates are not expected match the lower bounds from Theorem 2] since those bounds are minimax in nature. That is, they guarantee the existence of worst-case function f* (*( for which no estimator can achieve faster convergence. Therefore, the lower bounds apply to such worst-case functions and not necessarily to all functions in (?))).
including the functions in our experiments.
Related Work
Unlike parametric regression, which benefits from structural assumptions on the model class, nonpara- metric regression imposes minimal assumptions the underlying function. This flexibility, makes substantially more challenging to evaluate and guarantee adversarial robustness. Consequently, the literature adversarial robustness in nonparametric settings remains relatively sparse. Nonetheless, several notable efforts have begun to address this gap.
As discussed earlier, the Nadaraya-Wann Watson (NW) estimator is not robust to adversarial corruption and can fail even the presence of a single corrupted sample (3 Classical robust estimation techniques, such the Median-of-Meann extended to nonparametric settings 37 61 to improve the robustness of the NW estimator. In
(MoM) estimator [59 and trimmed means 60) have been
the MoM approach, the data partitioned into several groups, NW estimator is fitted to each

---

group, and the median of the resulting estimates is taken. While this method enhances robustness to outliers, its performance degrades sharply when even a single corrupted sample appears in each group. Trimmed-men
methods, on the other hand, discard fixed fraction of samples with extreme response values and fit the NW estimator on the remaining data. However, their effectiveness is limited when adversarial corruption is not uniformly distributed across the input space.
Zhao et al. 39 study adversarial robustness kernel-based nonparametric regression by analyzing an M-estimator variant of the Nadaraya-Watte Watson (NW) estimator 48 62], deriving upper and minimax lower bounds for metrics based on L2- -o-norm and Lee -norm. In comparison to our setting, which assumes the regression function lies in second Sobolev space, their work considers first-order Hölder class. Their proposed estimator requires gradient descent with On (o(()) complexity to produce an estimation with precision on new data point. In contrast, the cubic smoothing spline accurately evaluates new data point in (n) time, offering greater computational efficiency.
Several works also have studied the robustness of nonparametric classification. In [40] the authors analyze the robustness of nonparametric linear classifiers under arbitrary norms and mild regularity assumptions. The robustness of nearest neighbor classifiers against adversarial perturbations has been studied in [63] and general attack framework applicable wide class of nonparametric classifiers is introduced in [64] and data-pruning defense strategy to mitigate such attacks is proposed.
Conclusion
In this paper, we study the adversarial robustness of nonparametric regression when the underlying regression function belongs to ( We prove that the cubic smoothing spline achieves vanishing R2 and Roo errors as long as the number of corrupted samples satisfies q = o(n). We also establish lower bounds using minimax argument. Notably, we show that cubic smoothing splines are optimal with respect to the maximum number of tolerable adversarial corruptions.
Acknowledgment
This material is based upon work supported by the National Science Foundation under Grant CIF- 2348638.
References
[1] Jeffrey Dean, Greg Corrado, Rajat Monga, Kai Chen, Matthieu Devin, Mark Mao, Marc' aurelio Ranzato, Andrew Senior, Paul Tucker, Ke Yang, et al. Large scale distributed deep networks. Advances neural information processing systems, 25, 2012.
[2] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas communication-effccienn learning of deep networks from decentralized data. In Artificial intelligence and statistics, pages 1273-1282. PMLR, 2017.
[3] Yang You, Zhao Zhang, Cho-Jui Hsieh, James Demmel, and Kurt Keutzer. Imagenet training in minutes. In Proceedings of the 47th international conference on parallel processing, pages 1-10, 2018.
[4] Jakub Konečný, Brendan McMahan, and Daniel Ramage. Federated optimization: Distributed optimization beyond the datacenter. arXiv preprint arXiv: 1. 2015.
[5] Mohammad Shoeybi, Mostofa Patwary, Raul Puri, Patrick LeGresley, Jared Casper, and Bryan Catanzaro. Megatron-Im: Training multi-billion parameter language models using model parallelism. arXiv preprint arXiv: 100.0000,00 2019.
[6] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175-1191,201 2017.
10

---

[7] Hanzaleh Akbari Nodehi, Viveck R Cadambe, and Mohammad Ali Maddah-Ali. Game of coding: Sybil resistant decentralized machine learning with minimal trust assumption. arXiv preprint arXiv:2410.055500, 2024.
[8] Peiyu Xiong, Michael Tegegn, Jaskeerat Singh Sarin, Shubhraneel Pal, and Julia Rubin. It is all about data: A survey on the effects of data on adversarial robustness. ACM Computing Surveys, 56(7):1-41, 2024.
[9] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprint arXiv: 131.,199, 2013.
[10] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6572. 2014.
[11] Zhiyi Tian, Lei Cui, Jie Liang, and Shui Yu. A comprehensive survey poisoning attacks and countermeasures in machine learning. ACM Computing Surveys, 15(8):1-35, 2022.
[12] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pages 39-57. leee, 2017.
[13] Lianghe Shi and Weiwei Liu. Adversarial self-training improves robustness and generalization for gradual domain adaptation. Advances in Neural Information Processing Systems, 36: 37321-37333, 2023.
[14] Tao Bai, Jinqi Luo. Jun Zhao, Bihan Wen, and Qian Wang. Recent advances in adversarial training for adversarial robustness. arXiv preprint arXiv:2102.01356, 2021.
[15] Brendan Van Rooyen and Robert C Williamson. A theory learning with corrupted labels. Journal of Machine Learning Research, 18(228):1500, 2018.
[16] Sainbayar Sukhbaatar and Rob Fergus. Learning from noisy labels with deep neural networks. arXiv preprint arXiv: 1406.2000 2(3):4, 2014.
[17] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu, Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.0640 2017.
[18] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer. Machine learn- ing with adversarics: Byzantine tolerant gradient descent. Advances in neural information processing systems, 30, 2017.
[19] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine- distributed learning: Towards optimal statistical rates. In International conference on machine learning. pages 5650-5659. Pmlr, 2018.
[20] Parsa Moradi, Hanzaleh Akbarinodehi, and Mohammad Ali Maddah-Ali. General coded computing: Adversarial settings. arXiv preprint arXiv:2502.08058, 2025.
[21] Hanzaleh Akbari Nodehi, Viveck R Cadambe, and Mohammad Ali Maddah-Ali. Game of coding:
Beyond trusted majorities. In 2024 IEEE International Symposium on Information Theory (ISIT), pages 2850-2855. IEEE, 2024.
[22] Wolfgang Härdle and Enno Mammen. Comparing nonparametric versus parametric regression fits. The Annals of Statistics, pages 1926-1947, 1993.
[23] Wolfgang Härdle. Applied nonparametric regression. Cambridge university press, 1990.
[24] Alexandre Tsybakov. Introduction to Nonparametric Estimation. Springer Series in Statistics. Springer, New York, 2009.
[25] Chen Dan, Yuting Wei, and Pradeep Ravikumar. Sharp statistical guaratees for adversarially robust gaussian classification. In International Conference on Machine Learning, pages 2345- 2355. PMLR, 2020.
11

---

[26] Yue Xing, Ruizhi Zhang, and Guang Cheng. Adversarially robust estimate and risk analysis in linear regression. International Conference on Artificial Intelligence and Statistics, pages 514-522. 2021.
[27] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing. In international conference on machine learning, pages 5510-1320 PMLR, 2019.
[28] Aref Rekavandi, Farhad Farokhi, Olga Ohrimenko, and Benjamin Rubinstein. Certified ad- versarial robustness via randomized a-smoothing for regression models, Advances in Neural Information Processing Systems, 37:134127-1341500 2024.
[29] Yiling Xie and Xiaoming Huo. High-dimensional (group) adversarial training in linear regres- sion. arXiv preprint arXiv:2405. 13940, 2024.
[30] Antonio Ribeiro, Dave Zachariah, Francis Bach, and Thomas Schön. Regularization properties of adversarially-train traineed linear regression. Advances in Neural Information Processing Systems, 36:23658-23670, 2023.
[31] Edgar Dobriban, Hamed Hassani, David Hong, and Alexander Robey. Provable tradeoffs in adversarially robust classification. IEEE Transactions on Information Theory, 69(1))777 7822, 2023.
[32] Peter Huber and Elvezio M Ronchetti. Robust statistics. John Wiley & Sons, 2011.
[33] Ricardo A Maronna, R Douglas Martin, Victor J Yohai, and Matías Salibián-Barrent Robust statistics: theory and methods (with R). John Wiley & Sons, 2019.
[34] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Robust estimators high-dimensions without the computational intractability. SIAM Journal on Computing, 48(2):742-866 2019.
[35] Ilias Diakonikolas, Gautam Kamath, Daniel M Kane, Jerry Li, Ankur Moitra, and Alistair Stewart. Being robust (in high dimensions) can be practical. In International Conference on Machine Learning, pages 999-1008. PMLR, 2017.
[36] Yu Cheng, Ilias Diakonikolas, Rong Ge, and David P Woodruff. Faster algorithms for high- dimensional robust covariance estimation. In Conference on Learning Theory, pages 727-757. PMLR, 2019.
[37] Anna Ben- and Arnaud Guyader. Robust non parameerei regression via median-of of-nne.s.. http://hal..cccaeeeaaaaa--////// httpa//all1100/////////eeeeeeee 2023. HAL preprint, hal-03957385.
[38] Subhra Dhar, Prashant Jha, and Prabrisha Rakshit. The trimmed mean in non-parametric regression function estimation. Theory of Probability and Mathematical Statistics, 107:133- 158, 2022.
[39] Puning Zhao and Zhiguo Wan. Robust nonparametric regression under poisoning attack. In Proceedings of the AAAI Conference Artificial Intelligence, volume 38, pages 17007-17015, 2024.
[40] Elvis Dohmatob. Consistent adversarially robust linear classification: non-parametric setting.
In Forty-first International Conference Machine Learning, 2024.
[41] Grace Wahba. Smoothing noisy data with spline functions. Numerische mathematik, 24(5): 383-393, 1975.
[42] Grace Wahba. Spline models for observational data. SIAM, 1990.
[43] Paul HC Eilers and Brian D Marx. Flexible smoothing with b-splines and penalties. Statistical science, 11(2):89-121 1221, 1996.
[44] Ziming Liu, Yixuan Wang, Sachin Vaidya, Fabian Ruehle, James Halverson, Marin Soljačić, Thomas Hou, and Max Tegmark. Kan: Kolmogorov-arnold networks. arXiv preprint arXiv:2404.1977 19756, 2024.
12

---

[45] Jian Zhao and Hui Zhang. Thin-plate spline motion model for image animation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 3657-3666, 2022.
[46] Chuanbo Hua, Federico Berto, Michael Poli, Stefano Massaroli, and Jinkyoo Park. Learning efficient surrogate dynamic models with graph spline networks. Advances in Neural Information Processing Systems, 16:555233555444 2023.
[47] Junhui He, Ying Yang, and Jian Kang. Adaptive bayesian multivariate spline knot inference with prior specifications on model complexity. arXiv preprint arXiv:2405. 143.5 13353, 2024.
[48] Elizbar A Nadaraya. On estimating regression. Theory of Probability & Its Applications, 9(1): 141-142, 1964.
[49] Felix Abramovich and Vadim Grinshtein. Derivation of equivalent kernel for general spline smoothing: systematic approach. Bernoulli, 5(1):109-123, 1999.
[50] Florencio I Utreras. Convergence rates for multivariate smoothing spline functions. Journal of approximation theory, 52(1):1-27, 1988.
[51] David L Ragozin. Error bounds for derivative estimates based on spline smoothing of exact or noisy data. Journal of approximation theory, 37(4):335-355, 1983.
[52] Bernard W Silverman. Spline smoothing: the equivalent variable kernel method. The annals of Statistics, pages 898-916, 1984.
[53] K Messer. A comparison of a spline estimate to its equivalent kernel estimate. The Annals of Statistics, pages 817-829, 1991.
[54] Karen Messer and Larry Goldstein. A new class of kernels for nonparametric curve estimation. The Annals of Statistics, pages 179-195, 1993.
[55] Douglas Nychka. Splines as local smoothers. The Annals of Statistics, pages 1175-1197, 1995.
[56] Giovanni Leoni. A first course in Sobolev spaces, volume 181. American Mathematical Society, 2024.
[57] Martin J Wainwright. High-dimensional statistics: non-asymplotic viewpoint, volume 48. Cambridge university press, 2019.
[58] Pauli Virtanen, Ralf Gommers, Travis E Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, et al. Scipy 1.0: fundamental algorithms for scientific computing in python. Nature methods, 17(3):261-72,, 2020.
[59] Arkadij Semenovich Nemirovskij and David Borisovich Yudin. Problem Complexity and Method Efficiency in Optimization. Wileey-nterscience, 1983.
[60] AH Welsh. The trimmed mean the linear model. The Annals of Statistics, 15(1):20-36, 1987.
[61] Pierre Humbert, Batiste Le Bars, and Ludovic Minvielle. Robust kernel density estimation with median-of-means principle. In International Conference on Machine Learning, pages 9444-9465. PMLR, 2022.
[62] Geoffrey S Watson. Smooth regression analysis. Sankhyā; The Indian Journal of Statistics, Series A, pages 359-372, 1964.
[63] Yizhen Wang, Somesh Jha, and Kamalika Chaudhuri. Analyzing the robustness of nearest neighbors adversarial examples. In International Conference on Machine Learning, pages 5133-5142. PMLR, 2018
[64] Yao-Yuan Yang, Cyrus Rashtchian, Yizhen Wang, and Kamalika Chaudhuri. Robustness for non naraparae classification: generic attack and defense. In International Conference on Artificial Intelligence and Statistics, pages 941-951. PMLR, 2020.
13

---

[65] Robert J Serfling. Approximation theorems of mathematical statistics. John Wiley & Sons, 2009.
[66] Parsa Moradi, Behrooz Tahmasebi, and Mohammad Maddah-Ali. Coded computing for resilient distributed computing: A learning-theorede framework. Advances in Neural Information Processing Systems, 111111923-11196 2024.
[67] Lucien LeCam. Convergence of estimates under dimensionality restrictions. The Annals of Statistics, pages 38 53, 1973.
[68] Bin Yu. Assouad, fano, and le cam. In Festschrift for Lucien Le Cam: research papers in probability and statistics, pages 423-435. Springer, 1997.
14

---

A Proof of Theorem 1
In this section, we prove Theorem 1 Without loss of generality, we assume that Ω [0. 1 Recall that the solution of is unique and the explicit formula for fss is given by
iss (x)
(24)
where W,, (ar, nny) denotes the smoothing spline weight function depending on {x:) the sample size and the smoothing parameter X.
To facilitate the analysis, we define second scenario in which the adversarial strategy to be honest, that is, for any E A, the adversary does not deviate from the clean data generation process and behaves if it were non-adversarial. This allows to construct one-to-one correspondence between the realizations of the adversarial and honest scenarios such that for each i & .A. the observed responses y/ are identical across both settings, while for E A. the responses may differ: in Scenario I (adversarial), the adversary may introduce arbitrary deviations, whereas in Scenario 2 (honest), the responses follow the true underlying model.
In this second setting, we apply the same smoothing spline estimator to the uncorrupted data. The resulting estimator, which we denote by fss. is given by
iss (2)
(,,,,,;)1. n Σ
(25)
where yi denotes the uncorrupted response corresponding to input F3, i.e., y/ = Ds. for E [n]].4. and otherwise, for i A. ys f(x;)= + ç₁ for some i.i.d 6;- We define è = (G))e(m)-
now proceed to prove the bounds stated in Theorem | We first establish the upper bound for R2 (f, fgs) in and subsequently turn to the bound for Rox (f. f(s)
in (6)
By the definition of Re(f, fss), we have
Ra (2. ((s) = Ee sup f
fsz
(26)
L2(
where = (Ei)iE(M][A- First, observe that
||
Eg sup
fss
Eg
sup
fss
(2())
(22
which follows from the fact that ||5 f- fais) is independent of the noise terms (Ei)EEA To proceed,
we add and subtract fss (z) inside the squared term:
(s(x) f((())) (s(x) fss(()) - fss(x) f fo))
(27)
Using AM-GM inequality, we obtain
2 (1()) S2 ((st))(s(())) +2 -
(28)
Substituting this bound into the definition of R2(f. fa we get
Ra fis
E2 sup
fss
+2
sup
fss
fa L2(
(29)
L2(
To prove the upper bound in ( it suffices to find appropriate bounds for the two terms appearing in (2 We begin by analyzing the first term involving the honest estimator fss:
Ea
sup S
fss
(9)
2 Note that any function f: Ja, b)
R can be transformed with scaling and shifting into function
f: [0, 1] R without affecting its Sobolev regularity or the scaling of the associated metrics.
15

---

To do so, we use the following theorem, which is a direct consequence of [50] Therorem 1.1], specialized to the second-order Sobolev space setting:
Lemma 1. Lei - (a, b] be a bounded interval, and let the design points {x:]==1 I satisfy
the quasi-uniformity condition
A max
S
(30)
Amin
for some constant k > 0, where
max == sup min
I Dils
Amin == min [ zz}. 1fj
(31)
Then, for any j 0, 1, there exist constants do
Po > and Qo such that for all
S x S λo, we have
12 E2 -1100-193 1SS
S Po ((("())) de 20 n 31+1
(32)
(2(
Here, fss is the smoothing spline estimator applied to uncorrupted data, and f() denotes the j-th derivative of f. To bound the first term in (29). we invoke Lemma with j = 0, corresponding to the (22)) error between the regression function / and the honest smoothing spline estimator sss. This yields:
||+ fss
S Po (z)) de Q0
Ee
(33)
L2(0)
n A1/4
where À is the regularization parameter, and Po, Qo
0 constants from Lemma
To complete the proof of (5), we now seek find an upper bound for the second term 22 which captures the deviation between the adversarial and honest estimators:
Eg
sup
fss
fss
(2)
Note that from the kernel representations (24 and 25
we have
iss(0) - -
(z, (yi - T.).
(34)
n
Thus, for each Ω
[ -
1
W. 2x) (vi 33
(35)
Note that for each
If i é A, there no corruption, and yı D/--
If É A, the adversary may modify ye. and since f(x:), T1 E [-M, M). we have
1y: V.l = (f(x) T. + + 1f(x))) -
Til + leal < 2M + [eel.
Thus, the sum above reduces
1
Wn 2x) (yr Tt).
7
1EA
and we can bound
[ss(()) - f=)(()
< n
Σ
W,, (2M + + < 1
sup
[W,(x, Σ
(2M + +.).
n zen.jEIn
jEA
JEA
(36)
16

---

This implies that
W (2, 2
fss - f83
SUPzEnJeen|
Σ
(2M + +(ell)
L2(1)
ieA
IA
[SPP=ER.E[N]
(Z, n
Σ1) 12)
Σ
(2M + +cc1)2
ien
iEA
W (2, suPaen.,ejml
8MM + +2|(s)²)
q
n
iEA
W (I, x3)] suPoenJeeM
8M2 + 2 Σ
(37)
n
iEA
where (a) and (b) follow from the Sauchy-Schwaaze and AM-GM inequalities, respectively. Taking expectations and supremum over yields
q2(8M2 + 2
E sup
fss
fss L2(
S
sup (2, 22,)) sEn.JE(m]
(38)
n²
Now, to complete the proof of (5) it remains to find an upper bound for the kernel supremum term
sup 2.jE
Unfortunately, (-.)) does not admit analytically tractable form 55 53 for directly bounding its supremum in (T).. However, a substantial body of research 55 has focused on approximating
Wn(::-) with analytically tractable functions, known as equivalent kemells, denoted by W,,,,, s). We leverage such approximations in our analysis to derive an upper bound.
Recall that we define the empirical distribution function Fr as
(x)) = Σ
1(x S xr.
(39)
We assume that the empirical distribution function F,, converges cumulative distribution function
F, i..., a(n) == sup (x) F(x) satisfies a(n) -> O as n - co. Moreover, we assume that F(x) is differentiable Ω with density p(x) F' F'(x), and that there exists constant Pmin 0 such that
inf p(x) 2 Pmin- ZEB
(40)
To proceed, according to 49 we define the equivalent kernel Wn, (I, as
1/4
Wa(c, 8) (p())p(x)) 3/8 e- po(z)) sin 1114 1114 8) 7)
(41)
where the phase function (a, s) is given by
max((r,)
s) 2 1/2
p(1)2/4 dt.
(42)
min(z.s)
Based on 49 Theorem 1], for sufficiently large n, we have
Wn,z, s) Wn (n, s)} c (X-V)/a(m))))) +1),
(43)
where > a constant independent n, and the bound holds uniformly over all [0, and E [T1, T2), where 0 < < < 1.
17

---

Now note that
sup zER,eE(a
sup =En,jE(m)
W (2, + (W)(z,z)) - 2z)
(44)
sup =en.jelu]
W (n(z, (1(2)
sup rER.jE(n]
(z) Wn(,
(45)
Using the uniform approximation property established in 443) can bound the second term:
sup sEn.jE(M)
Wn(z, - (1 sc (xx +1).
(x-1//2((()++1
(46)
Thus,
sup =EQ.JE[n]
[W (x,
sup #Eft.jEin]
W (1, +C (x (1)))a(()))
(a) --1/4 1/4
(Pmin) 3/4 + 11-1/2 (()) +1)
(47)
where (a) follows from the definition of (z. kÿ) in 411. and the fact that inf p(x) 2 Pmin-
Combining the decomposition in (29) the bound on the honest estimator error from (33 and the
adversarial deviation bounds from 388 and 447.. we obtain the final upper bound for Re fs)) stated in Theorem
Ro fix) < 2P. / (f)( dx +
2Q0o²
nAl/4
29 (8M2+ 20
X-4
(>~1/22a00) 0004+C((1000 + :))²
+ n²
(Pmin) 3/4 + C.
(48)
2
Therefore, in the regime where A - 0 F1, Fgg Fg such that for sufficiently large n,
and
X n- n- there exist constants
R2(S.fg) S FAd / (x)) dr
E20² nxi/4
(M²+ n²
(1+1-1/40(1) x2/4)?
(49)
Since 1/44 + O as n > co. the additive term X 1/4 becomes negligible compared to for sufficiently large n. Dropping this term and absorbing constants, we obtain
S S (+)) dr mAI/4 Relf (Ss)
o²
(MM (1+1-
(50)
n2/1/2
For continuous cumulative distribution function F, Serfling almost surely. Since À > - it follows that X-1/4a(n) large n, we have + X 11/4 < 2. As result, obtain
66| shows that (n) 1/2 log log
co. Therefore, for sufficiently
R2 f() S / (x)) da + nAI/4
(M²
(51)
n²\2/2
This concludes proof the upper bound on R2(S, I5h) Theorem
To complete the proof of Theorem | it remains to prove (6) To do so, we adopt a similar strategy as
in the La case, but adapted the squared supremum norm. By the inequality (a 6)2 < 2a² 262. we have
||- fog
52115
fas (2)
+2 +2 sss
fg (0)
(52)
(1)
18

---

Taking expectation and supremum over S, we substitute into the definition of Ro and obtain
Rf, fss)
Ee f
sup
fa fss
s
Loe (9t)
1E, - 2
sup ||
fss
|
+ 2 E2
sup
Jss f3' (m)
-
(53)
L (92)
From the pointwise bound established in (36), we have
[Ss((e) (a) MM + max, (ea))
sup SEN.jE|M)
(54)
Applying the kernel estimate from
47 we conclude that
[ss fsi
MM max, le:l)
(A-14 (Pmin) -3/4
3/4 + C (1-19a(m)++1)
(55)
Loc (Q)
n
2
Squaring both sides and taking expectation and supremum over S, we obtain
(M² + o²) (1+A-1/Aa(m) + +1/1)²
Ex
sup
fss
fss
(56)
22/1/2
To complete the proof of (6). remains to find an upper bound for the first term in 55) namely
sup || fss (9)
E₂
To do so, Since f fss E (12), we can leverage Sobolev norms inequalities 56 and use the same arguments as in [66 Lemma 5] and obtain:
iss
$2
fss
1115--
f's
(57)
L (R)
(2(1)
L2(
Taking expectations on both sides of (77 and applying the Cauchy Schwarz inequality, we obtain:
E2
|| iss
< 2E
||| fss
-|r--f's
I's
(0)
L2(
L2(())
< 2 Ex |||s
iss
12
1)
1/2
E2
S
Pss
1)
1/2
(58)
(
Applying Lemma
with and j
= 1, we can bound the right-hand side using:
||5
/ (f)(z)) dr + nAI/4
Qoo²
Ea
fss
S Pod
(59)
La (9))
a
/ (c)) dr Q00²
Ea ||'
Pss
< PoX
(60)
T (9)
3A3/4'
Substituting the bounds from
59 and
660
into 57
we obtain
|||
2 Pod ( (z)( de + Q00²
1/2
R2
fss
nAI/4
Lox (0))
[Pall12 [ (x)) dx +
Q0o²
1/2
(61)
nx3/4
Combining the decomposition in upper bound in the regime where
53 with the bounds from 61 and 56
we obtain the following
- Do and À > n
T² 1/2
x (X1/2 I (f) de +
o²
1/2
Roo (f. (f. S 2 (x)(
22 dx 1AI/4
nA3/4
(2M
+0²)
11 - 1144 ((())) + x111)²2
(62)
1/21/2
19

---

We now multiply and divide the first term by 11/4, yielding:
Roo (f. S X 1//4/// (A dæ + nAIA4 + q2M22 (1 -1+11111--000 (1+A-1/4(m) a(n) + 2
n²A1/2
By arguments similar to those used in the bound for Ra(f.fss)
neglect both A// and
X (-1) compared for sufficiently large n. Thus, obtain
R (J, fis) S SA-1/4 (2/o (x)) de + nx1/4
o²
9d (M ( o²)
(63)
22/1/22
This completes the proof of the upper bound on Roo (f, {$s) in (6). and thereby concludes the proof of Theorem
1
B Proof of Theorem 2
To prove Theorem we first state and prove Lemma
Lemma Let P1 and P2 denote two probability density functions of two distributions with common variance a² >> 0. Then, there exists or E (0, 11. and two probability density functions Q1 and Q2 such that
a) aQi = (1 (1- a)P2 a1-a) a022.
(64)
where Q1 and Q2 are explicitly constructed P1 and Pz.
Proof. Define as:
[PPPS1)2PP(0 (Pa()) - (u)) du
a 1+ I+ ((AN(((222A)))) (Pz(u) Pi(u)) du I 1.
(65)
Next, define Q1 and Q2 as:
Q1(u)= 1-a (P2(u) ((t)) R())) a Q2(u) 1 1-a (P) - (()()) > P((4))
(66)
(67)
where 1(.} denotes the indicator function.
By construction, both (u( and Q2(u) are non-negative since the indicator functions restrict the support to regions where the corresponding differences are non-negative. We now show that Q1 and Q2 are valid probability density functions. Consider:
@ii( du = 1-
/ (Pa(w) - P(()) (1))) du
1-a I ((MP2(02A(())) (P2(u) P(()) du
(68)
By symmetry, the same argument shows that f Q2(u) du as well.
Hence, both Qı and Q2 are valid densities. With this choice of a, the following identity holds:
a aQ = (1 a) +aQ2.
(69)
This completes the proof.
We now prove Theorem building on Lemma We begin by establishing the lower bound for the
metric Rg, stated in 18 ; the proof for Roc. given in (99, follows by similar argument. To do so, we reduce the minimax risk (18) and 19 to hypothesis testing problem [57]. Specifically,
we construct two functions /i and fa in W (22 with L2 and L-x distance, bounded away from zero
(
(see Figure However, given n samples from either function, an adversary can corrupt up to g of them, making impossible for any estimator to reliably distinguish between fi and f2. Consequently,
20

---

no estimation approach can identify which function generated the data, and the average hypothesis testing eπrоr remains 1/2. Applying [57 Proposition 5.1] yields the lower bounds in Theorem 2 The details of the proof is as follows.
Throughout the proof, we assume fixed design given by æ; i/n and 6; (0, o²) are i.i.d noise samples drawn from a normal distribution with zero mean and variance a², for i E [m].
Let Tq I and define Eg r We construct two functions, fi and f2, as follows, Set
(1 = 0 for all x E [0, 1].
To define f2, we construct a degree-S polynomial g(x) on the interval [ra - ryl that satisfies the following conditions:
g(rg cg) gg
(70)
g (Tg Eq)
(71)
g (rg Eq) 0,
(72)
g(r,) = 0,
(73)
g ((rr) = 0,
(74)
g"(rg) O.
(75)
These six conditions uniquely determine a polynomial of degree 5, since there are six coefficients to solve for. Hence, such polynomial g exists and can be explicitly constructed. Now, define f2 on the interval [0, 1] by
rg
i E [0,r, - if x E [rg Eq. if rq.
f2(x)
g(x),
It is straightforward to verify that f2 E ([ 1)), since both fe and its first and second derivatives have bounded norms over (See Figure 2).
Note that fi and f2 are close but not identical; their differences are concentrated on the interval [0, rgl. and will used to construct the lower bound.
For each sample vi, the adversary proceeds as follows:
If x; 2 rg. then (1;) f2(1;), so no corruption is needed: both models produce identical distributions for Vi-
If xz < Tq. then fi (x,) * f2(x:), and the adversary applies Lemma to the pair of normal distributions
P(0) == (z)))))),
P = =f([f(x;),,
obtaining scalar a; [0, and auxiliary distributions Q and Q such that
(1 az) + Q (1 - a + +a
For each such the adversary acts:
With probability a; leave y uncorrupted (i.e., drawn from p(() if = fi, or from
p(0 if f= f2).
With probability a; the adversary replaces yı by draw from Q the true function is f1, and from 2 if the true function is fz-
For the above adversarial strategy, we have |A| S rg = q. addition, note that under model fis conditionally 24, the corrupted response Ys is distributed according to (1 Pp) a3)(1) and under model f2. is distributed according to (1 - p..) + Q Q in Lemma these mixtures are identical for each i.
( By construction of Q and
Therefore, after adversarial corruption, the distribution of all observed data (T) ) is identical under fi and fz. More precisely:
21

---

For all i with > Tg. we have (xx,) f2(2)), and hence p(O)
p(()
no corruption is
needed, and the distribution of y the same under both models.
For all with 2; Ty. the adversary modifies the responses exactly so that the overall conditional distribution of yi is matched across the two models.
Note that the constructed functions fi and f2 are not identical: by definition, their difference measured by the metrics introduced T and (2) is nonzero. However, the adversarial corruption strategy described above renders the corrupted data distribution identical under both fi and fz. Consequently. no estimator can achieve better performance than random guessing between the two hypotheses. As result, the minimax error under adversarial corruption remains bounded away from zero, establishing a nontrivial lower bound.
To prove 18). by starting from the definition of f2, we have
R2(J, = sup L (s(x) - f(x)) dr
(76)
where the expectation is over the noise E, and the supremum is taken over all admissible adversarial strategies S. Since Theorem 2 considers the worst-case function f. obtain
S (f()) f(x)) dx
inf
Ra(f. f) 2 inf sup f S...
sup
Ee f fe(
(77)
As established earlier, the adversary makes the corrupted data distribution identical under both fi and f2. Formally, let f. and p((A) denote the distributions over the corrupted datasets when the ground truth is fi or f2, respectively. Thus, we have:
p(A) = P((4)
That is, the total variation distance satisfies:
TV(E f1 p(4A) -
(78)
This guarantees that no estimator can distinguish between them better than random guessing. To formalize this, we use Le Cam's 's two-point method [67] 68] (the hypothesis testing between two points), which states that for any estimator f and any pair f1, f2.
Iff f2 f2
inf sup Es [1l f112((0)
f SEL/i/at
Using 78 we obtain the following lower bound:
inf sup E [[lf f11:2(0) re(fifa)
2 - -fal-ooll
Consequently, following
777 we have
Re(f. 1 1//²
1 l' (fi(x) f2(xx)) dr.
inf sup (Q).s.)
(79)
4
Recall that f1 = 0, and
Fg F, g(r),
00, rg Egl: x E [rg - Eq. rgl.
f2(z) =
0,
Tg:
where g(x) is degree-5 polynomial satisfying the smoothness and boundary conditions described earlier. Therefore,
S/ (f(()) f2(x))² dx = 1-r f2(x))dx=
(
(ro =) + f glx)2dx dx
(r, =).
(80)
22

---

Note that since Eg = rg. we have
l (rg - x))
u uddu
19
Eg
rg
9
3
(81)
3
7
Therefore, we have
(2) 3
inf
Re(f. f) 2 , f (EW.
sup
(82)
Moreover, even the absence adversarial corruption (i.e., y = 0), it is well known from classical minimax theory in nonparametric regression [24] that
|| f La(l)
inf sup fEWA(
2 n 4/3
(83)
Combining the two regimes, we obtain the following lower bound on the adversarial error:
inf
sup (E)
R2 2
n + 4/5
(84)
This completes the proof of (18). To complete the proof of Theorem we now establish lower bound for Ro Recall that
Roo (f, = Eg sup f
(85)
Lo (9))
where the expectation is taken over the noise e, and the supremum is all adversarial corruption strategies S. The norm ||- I..l denotes the supremum norm over the interval [0. 1].
As in the case of R2, the adversary can construct corrupted data distributions under fi and fa that are indistinguishable. Consequently, no estimator can distinguish between the two hypotheses better than random guessing. Applying Le Cam't 's two-point method 66 68 to the L loss, we obtain:
1f1 f2)),.0())
inf sup Es [1I f1) 2 fe(i.f))
(1-TV (
4
Therefore, we have:
inf sup Rxo (J: 11 f2ll2 Se
(86)
Since fi(z) = 0, we have fl - fell have fz(0) N'g. Therefore,
(x) fellel = |I 2 f2(0)) From the definition of fz, we
inf sup f (eW
R (f. f) 22
9
(87)
Moreover, in the absence of adversarial corruption (i.e., estimation under the supremum norm is known to satisfy (see 24
0), the standard minimax rate for
3/4
||
log n
inf sup E Se)
(88)
(20)
Combining both contributions, we conclude that
log n
3/4
inf f ())
sup
Roo(f
(89)
This completes the proof of 19 and thereby the proof of Theorem
23

---

C
Gaussian Setting Experiments
4 n
q
log (RgU (
log Rox ff)
Random Actack, Slape rs -1277
Random Attack, Slope -141
Concentroted Astack, Slope 1.12
Concentrored Attock, Slope 3.35
Grondy Slop -1.62
Gouuly Atteck, Skpp
log(n)
log(n)
06
9 of
log R&
Tog Rex
Random Attock, Slape
Random Atrack, Slope
Concentrated Attack, Slope -0.68
Concentrated Attack. Slaze -0.19
Greedy Attack, Slope 2200
Greedly Attack, Slops
log(n)
log(n)
Figure Log-log plots showing the convergence rate of the cubic smoothing spline estimator f= for f(x) sin under Gaussian design. The top row plots are results for q = n.3 with theoretical rates of (n--8.8 for R2(J, J) and ((n-0.6) for (x, The bottom row corresponds to higher corruption level, q n n.6 with respective theoretical upper bounds of O( and -0.15)))
24

---

n
log HH (
log R
Random Slope 1.38
Random Actack, Slope 1.36
Comventrated Astack, Slops 11
Concentrated Attack. Slage -0.51
Grondy Attack Slope -.62
Greedl Attack, Slope -1.46
log(n)
log
n6
n
Rf D)
Randem Attack, Blope -0.79
Random Artack, Slope -0.2
Concentrated Attack, Slope a -0,68
Concentrated Attack. Slooe -0.19
Greedy Attack, Slope -200
Greedy Attack, Slope -1.99
(ng(n)
log(n))
Figure 6: Log-log plots showing the convergence behavior of the cubic smoothing spline estimator
f fss when the ground-truth function is an MLP, under the Gaussian design. The top row corresponds to the case q = 0.3, with theoretical convergence rates of O(n for R2(f, f) and respective theoretical upper bounds of (n-00.33) and O(n Onn-0.B).
Onn 0.6) for (J, The bottom row shows results for higher corruption level, 0.6 with
25

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We detailed our contributions clearly in the abstract and the introduction sections of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We provided all the details regarding the assumptions, conditions, and limita- tions the main problem (Section 2), theorems (Section 3), the experiments (Section 4 as well the conclusion (Section the paper.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
26

---

Answer: [Yes]
Justification: Our paper includes theoretical results in Section 3 In our theorems, we clearly mentioned all the required assumptions, and complete (and correct) proof of them is available in appendices. Please see Section 2 for a full definition of the problem and the notations used in the paper are described in introduction T
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We have provided details regarding our empirical evaluations in Section 4 in the paper.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
27

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification: We provided references to all packages that used in the paper. Regarding the code, we are happy to share it later required.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.cr
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
Codeeoomi ssioiiiiicyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification:
We provided full experimental details in the paper (see Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer:
[Yes]
Justification: The details are provided in Scction 4
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
28

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provided all the details regarding our experiments Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We followed the NeurIPS code ethics in our paper.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper is focused on developing a theoretical foundation for adversarial robustness of non-paraan parametric regression. We believe this work has no direct societal impact that should be explained in the paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
29

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This is not applicable to our work and this paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: This paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
30

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
This paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve these.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve these.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
31

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: We just use LLM for writing and editing purposes.
Guidelines: The core method development in this research does not involve LLMs as any important, original, or non-standard components.
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy battps://neurs / for what should or should be described.
32


Reviews:
[{"review_id": "952hE61Err", "reviewer": "Reviewer_Yr9M", "summary": "The paper analyzes the robustness of nonparametric regression models using splines method. They make the second order Sobolev space assumption on the regression function. They also assume only the labels are arbitrarily corrupted for few samples but not the features. Further the authors prove the minimax optimal lower bound. The authors also claim to have zero  estimation error asymptotically if the number of outliers are limited to o(n).", "questions": "1) In lie 131, the authors use the threshold M? How is it chosen in practice? It seems M is treated as a constant in Theorem 1 and its proof or the later discussion. It feels like M can be a large and should not be treated as a constant. \n2) Isn’t the truncation to [-M,M] in line 131 used by authors similar to trimming methods critiqued in line 248?", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 1, "originality": 2, "strengths_and_weaknesses": "## Strengths\n1) The minimax optimal lower bound seems novel. \n2) The derived theoretical results makes sense. For example, achieving zero error for o(n) outliers and impossibility result for constant outlier proportion. \n3) The authors have done empirical studies to validate the theoretical claims. \n\n## Weakness\n\n1) Related works should be discussed more. It will help the reader to identify the exact contributions made in the paper \n2) In line 284, the authors discard median of means approach saying that it can fail arbitrarily if a single corrupted sample falls in each group. Can the same thing happen in the splines approach? \n3) In line 130, the authors the function is bounded in the domain. Does that assumption for simple least squares objective function? \n4) There is a clear model mismatch in line 40 and line 144 or 161. It makes it tough to follow the proof in Eq 12\n5) So the bounds in Eq 9 and 10 are directly taken from the existing literature? And the bounds for 2nd term in Eq 7 and 8 are not seen in the literature? I am interested in identifying the exact theoretical contributions of this work. \n6) The experiments seem to be misleading. In line 215, the authors consider the domain [-10,10] and function f(x) = x sin(x). Hence, the max value of the function can take is 10. The authors take M = 10 in the experiments which basically implies that all outliers greater than 10 were deleted due to truncation or trimming. Ideally, one would not know the exact value of M in practice.", "was_revised": true, "final_justification": "I justify my score because I am still not convinced about how the authors are choosing M, which is critical practically and in theoretical bounds also. \n\nTheoretically, the max of $n$ samples will grow as $O(\\log(n))$ even for sub-Gaussian random variables. This may be worse for heavy-tailed data. Hence, the value of M will be at least  $O(\\log(n))$. The authors seem to be treating it as a constant. \n\nI don't understand the reasoning behind this comment from authors: \"What we meant was that $M$ is chosen to be significantly larger than the range of $f$ over the input domain.\" If I understand correctly, the range of f is not assumed to be known a priori (otherwise it makes the problem trivial). Hence, I am not sure how they choose the value of M in experiments either. And how do they quantify \"significantly larger\" practically? I believe these are critical questions in robust statistics.", "rebuttal": "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.\n1. > Related works ... the paper.\n### Our Contribution\nUnlike 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. \nA 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.\n### Comparison to The class of NW estimators:\nIt 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]. \nConcatenation 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.\nThis 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. \nHowever, 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.\nCompared 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.\n### Comparison with Kernel-Based M-Estimators:\nZhao 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.\nIn 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.\n\nOther works have studied adversarial robustness in nonparametric settings such as classification and density estimation, as covered in the paper.\n\n2. > In line 284 ... splines approach?\n\nNo, 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. \n\n3. >In line 130 ... function?\n\nWe 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].\nOur 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)$.\nImportantly, $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. \n\n4. > There is a clear ... in Eq 12.\n\nNote 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.\nIn 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.\nThe 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.\nWe 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.\n\n5. >So the bounds in Eq 9 ... this work.\n\nAs 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:\n- 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)).\n- 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.\n\nTo 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.\nTo 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. \n\n6. >The experiments seem to ... value of M in practice.\n\nFor 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):\n| $M = 10,\\ x \\in [-1,1]$, $q = n^{0.6}$ |\n\n|$\\mathcal{R}_2(f,\\hat{f})$|log-log Slope|\n|-|-|\n|Random Corruption|-0.85|\n|Concentrated Corruption|-0.67|\n\n|$\\mathcal{R}_\\infty(f,\\hat{f})$|log-log Slope|\n|-|-|\n|Random Corruption|-0.59|\n|Concentrated Corruption|-0.48|\n\n7. >In lie 131 ... as a constant.\n\nPlese see the response to the question 3.\n\n8. >Isn’t the truncation ... line 248?\n\nIn 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).\nIn 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.\n\n[1] Wahba *et al.*, *Smoothing noisy data with spline functions.* 1975.\n[2] Zhao *et al.*, *Robust nonparametric regression under poisoning attack*, AAAI 2024.\n[3] Dhar *et al.* *The trimmed mean in non-parametric regression function estimation*, 2022.\n[4] Ben-Hamou, Anna, and Arnaud Guyader. \"Robust non-parametric regression via median-of-means.\" 2023.\n[5] Tsybakov *et al.*, *Introduction to Nonparametric Estimation*, 2008"}, {"review_id": "u1ZlZXeCwr", "reviewer": "Reviewer_MnJT", "summary": "This paper studies the classic problem of non-parametric regression: however, it is studied under an adversarial setting. \nTo understand the set-up imagine n samples (x_i, y_i) generated from some ground truth f:X  \\to Y with y_i = f(x_i) + \\eps_i where \\eps_i's are mean zero constant variance iid variables (we can even think of X = [0,1]). We wish to learn a function \\hat{f} (non-parametric) which fits the data. However, there is an adversary who can choose any q points of their liking and corrupt the y-values there arbitrarily. This makes it unclear if the current toolkit for non-parametric regression is sufficient. \n\nThere is prior work in the parametric setting of the above adversarial set-up. However, the setting of non-parametric regression makes the problem challenging due to a lack of \"structure\" on the hypothesis space.\n\nThe main results in the paper are (with error rates being define as squared L_2 norm or squared L_\\infty norm between f and \\hat{f}): \n1> Under some assumptions it is proved that the computationally efficient classic smoothing spline estimator retains robustness against adversarial corruption\n2> Further, a lower bound on the error rates of the best data dependent estimator is shown, and under some regime of parameters it matches the error rate achieved by the smoothing spline estimator.\n\nThe paper also demonstrates experimental performance of the smoothing spline in presence of random corruptions and concentrated corruptions to corroborate the theory.", "questions": "1> Abstract: It will be good to give some notion of what the estimation error is here to help the reader. Also, the last statement about the optimality of the smoothing spline is a bit misleading as that is only true in a certain range of parameters: perhaps you want to reword this part.\n \n2> Typo @ line 38: choose -> chooses, for any -> for all\n\n3> The lines from 45-48, and in fact 63-67, 77-79, whole of section 2 could be made more precise. Chiefly, the game that is being played needs to be specified clearly, i.e., devise a data dependent learner \\hat{f} that when given any ground truth f and any collection of data points, and any adversarial corruption of q points, does well on expectation over the randomness of the \\epsilon's. Please make sure that this is amply clear as the whole set-up is only made clear when one looks at corollary 3, which is deep insider the paper. The descriptions currently are not making the set-up unambiguous.\n\n4> Typo @ Line 47: any f that belongs...but please reword in light of above\n\n5> Lines 124-129: Can we not just say that we are sampling n points from p: seems that we are morally thinking about it that way\n\n6> Line 130: Do you mean |f(x)| < M/2 or something because if f(x) is M then there is a good chance the answer might go above M for y when the noise is added: so, then the adversary can in fact choose a value outside M.\n\n7> Lower-bound: <a> does this lower-bound match all the assumptions of the upper-bounds...please include a short description of this as we are comparing the two bounds and hence it is good to clarify that even under the assumptions of the upper bound the lower bound works. <b> Can you provide a clean hypothesis testing problem here since there might then be scope to improver the lower-bounds\n<c> I was looking at Appendin B...can you explain why you need to have the sampling lemma...can't the adversary just set the sample to (0 + \\eps) everytime x< r_q. and trivailly match the sample dist of f_1....I guess it is okay to have a randomized adversary.....also why do you need the linear decay in f_2, can we not have it decay sharply near r_q?.....\n\n8> Experiments: More experiments with other functions and other kind of adversaries (perhaps using some kind of learning algorithms to corrupt the data points)....also why f = x sin(x)?\n\n9> Both Upper and Lower Bounds:  good to emphasize a bit more as to what steps in the proof are novel ..\n\n9> General Suggestion:  It'll be great if we obtain from this work a general understanding of what makes regression robust so as to capture more techniques and not just the smoothing spline operator; even better if this can inform practice", "limitations": "Yes (I have included some suggestions in the questions section already)", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n1> Studies an interesting topic: non-parametric regression in the presence of an adversary. This should be of sufficient interest to communities thinking about adversarial robustness.\n2> Shows that an existing classic technique, i.e., smoothing spline operator, can tolerate a certain number of adversarial corruptions. This is proved by decomposing the error term and analyzing them by nicely collating previous results. It displays originality in the way the results are combined: the skeleton of the proofs can be argued are perhaps natural.\n3> Establishes lower-bound on the optimal rate for any data dependent estimator via a reduction to hypothesis testing. Uses a cool sampling lemma. Though it is not fully explained why such a lemma is needed.\n\nWeakness:\n\n1> Is kind of a stylized setting in the sense of assumptions.\n2> No general insight for a theoretical point of view to design robust learners.\n3> No crucial insight for practice in terms of dealing with adversarial corruptions beyond using smoothing splines.\n4> Experiments are somewhat limited, but that said this is a theory focused paper: so, this is not a big weakness\n5> The writing in some areas can be made clearer and steps which are new can be highlighted", "was_revised": true, "final_justification": "The proof follows a natural skeleton, there are possibly non-trivial steps in the details, but they are buried deep within. I have tried to elicit these from the authors in the review. Overall, while the authors study a natural and important problem, there is a lack of general insight (which would have scored the paper higher) so I have retained my score.", "rebuttal": "We thank the reviewer for the helpful feedback. Below we address the questions and will update the manuscript accordingly.\n1. >Is kind of ... assumptions.\n\nOur 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].\n\n2. > No general ... learners.\n    >No crucial insight ... splines.\n\nWe 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]. \n\n3. > Experiments  ... weakness \n    > Experiments: ... why f = x sin(x)?\n\nWe have extended our experiments along several settings to address this concern. \n\n### Effect of Large $M$\n\nLet $f(x) = x \\sin(x)$ over $x \\in [-1, 1]$, $M = 10$ and $q = n^{0.6}$.\n$\\mathcal{R}_2(f,\\hat{f})$\n\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.85|\n|Concentrated Corruption|-0.67|\n\n$\\mathcal{R}_\\infty(f,\\hat{f})$\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.59|\n|Concentrated Corruption|-0.48|\n\n### Adaptive Greedy Corruption\nIn this process, the attacker:\n1. Fits the baseline estimator on clean data.\n2. Computes $\\ell_i = (\\hat{f}(x_i) - y_i)^2$ for each sample: .\n3. Identifies $i^\\star = \\arg\\min_i \\ell_i$.\n4. Update $y_{i^\\star} \\leftarrow y_{i^\\star} + M \\cdot \\operatorname{sign}(\\hat{f}(x_{i^\\star}) - y_{i^\\star})$.\n5. Repeats the process until $q$ points are corrupted.\n\nBelow are the results for $f(x) = x \\sin(x)$ with $M = 100$ and input domain $[-10, 10]$:\n$\\mathcal{R}_2(f,\\hat{f})$:\n|$q$|log-log Slope|\n|-|-|\n|$q = n^{0.6}$|-1.12|\n|$q = n^{0.8}$|-0.91|\n\n$\\mathcal{R}_\\infty(f,\\hat{f})$:\n|$q$|log-log Slope|\n|-|-|\n|$q = n^{0.6}$|-1.21|\n|$q = n^{0.8}$|-0.97|\n\n### Evaluation on Neural Network Functions\n\nLet $f(x)$ is a 3-layer MLP neural network with $M = 500$, $\\sigma^2 = 1$, and $x \\in [-1, 1]$. \n$\\mathcal{R}_2(f,\\hat{f})$\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.80|\n|Concentrated Corruption|-0.65|\n|Adaptive Greedy Corruption|-1.29|\n\n$\\mathcal{R}_\\infty(f,\\hat{f})$:\n\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.86|\n|Concentrated Corruption|-0.48|\n|Adaptive Greedy Corruption|-1.31|\n\n4. > The writing ... highlighted\n\nPlease see the response to question 1 and 7.\n\n5. > Abstract: It ... this part.\n\nAs 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.\n\nWhile 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. \n\n6. > Typo @ line 38\n\nWe will correct them in the final version.\n\n7. > The lines from 45-48 ... unambiguous.\n\nOur 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.\nIn 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.\n\n8. > Typo @ Line 47\n\nWe will correct them in the fincal version.\n\n9. > Lines 124-129\n\nIt 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].\n\n10. > Line 130: \n\nOur 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)$.\n\n11. > Lower-bound: ... sharply near r_q?\n\n###  Upper vs. Lower Bound\nIn 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. \n\n### Hypothesis Testing\nThe 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.\n### Sampling Lemma \nWe 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. \n### Function Shape\nIn 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.\n\n12. > Both Upper ... novel\n\n### Upper Bound\n\nAs 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:\n\n- 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)).\n\n- The second term captures the deviation between the estimator computed on adversarial data versus the one computed on clean data. \nTo 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.\nTo 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. \n### Lower Bound\nTo prove the lower-bound, we construct two functions $f_1$ and $f_2$ such that the following conditions are satisfied:\n\n- Their distance in $L_2$ and $L_\\infty$ norms is nonzero.\n- An adversary corrupts $q$ labels, such that the corrupted data distributions under $f_1$ and $f_2$ become indistinguishable. \n\nAs 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. \n\n13. > General Suggestion ... practice\n\nWe answered this comment in the second question.\n\n[1] Tsybakov *et al.*, *Introduction to Nonparametric Estimation*, 2008 \n[2] Zhao *et al.* *Robust nonparametric regression under poisoning attack.* AAAI 2024\n[3] Silverman *et al.* *Spline smoothing: the equivalent variable kernel method.\" The annals of Statistics*, 1984"}, {"review_id": "3VNG70VMUz", "reviewer": "Reviewer_Az91", "summary": "This work investigates the adversarial robustness of nonparametric regression, focusing on scenarios where a subset of the training labels may be corrupted by adversarial label noise—i.e., an attacker can arbitrarily alter the labels of some training examples. The authors show that, for bounded and one-dimensional input and output spaces, the smoothing spline estimator exhibits robustness to such attacks. Furthermore, they derive a minimax lower bound, establishing that the smoothing spline estimator is statistically optimal under these conditions.", "questions": "1. Can the theorem be extended to the case of multiple regression?\n2. Can the analysis be extended to classification and feature corruption?", "limitations": "Yes.", "rating": 5, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. This paper is well-written and easy to follow. \n2. The authors propose a minimax lower-bound, which shows the fundamental limits of estimation accuracy.\n3. The authors analyze the classical smoothing spline estimator and show the optimal of it. \n\nWeaknesses\n1. The input is one-dimensional, which is uncommon in practical applications.\n2. The analysis is limited to regression and label corruption.", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the helpful feedback. Below we address the questions and will update the manuscript accordingly.\n\n> The input is one-dimensional, which is uncommon in practical applications.\n\n**Answer:**  \nWe 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.\n\nThis 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.\n\nWe 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.\n\n\n> The analysis is limited to regression and label corruption.\n\n**Answer:**  \nWe thank the reviewer for this observation. In adversarial learning, two widely studied forms of attack are:\n\n- **Label corruption (poisoning):** the adversary modifies the labels $\\{y_i\\}_{i=1}^n$ while keeping the inputs $\\{x_i\\}_{i=1}^n$ fixed.\n- **Input corruption:** the adversary perturbs the input features $\\{x_i\\}_{i=1}^n$, possibly relocating them to adversarial positions.\n\nBoth 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.\n\nThis 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.\n\nWe hope this work lays the foundation for analyzing other adversarial models, including those involving corrupted inputs, in future research.\n\n\n> Can the theorem be extended to the case of multiple regression?\n\n**Answer:**  \nWe 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$.\n\nThe 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.\n\n> Can the analysis be extended to classification and feature corruption?\n\n**Answer:**  \nWe 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:\n\n- **Label corruption (output attack):** where the adversary modifies the labels $\\{y_i\\}$ while keeping inputs $\\{x_i\\}$ fixed.\n- **Feature corruption (input attack):** where the adversary perturbs the features $\\{x_i\\}$.\n\nIn 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.\n\nAs 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. \n\nWe view this paper as a foundational step toward broader analysis across different settings, including classification and more general corruption models."}, {"review_id": "oG0ur0rPnG", "reviewer": "Reviewer_pg9c", "summary": "This paper positions itself as one of the first to analyze the robustness properties of nonparametric regression models when the underlying function belongs to a second-order Sobolev space. It begins by deriving an upper bound on the risk of the smoothing spline estimator in the asymptotic setting. The authors then characterize the minimax optimal risk and discuss where and how the two bounds coincide.", "questions": "1. One high-level question that a reader may ask is why we should choose a nonparametric regression function over a parametric one (including large-scale deep networks) to be concerned about their vulnerability to adversarial attacks.\n\n2. While the authors refer to the problem as the adversarial robustness of regression models, I do not see a significant difference between their setup and the standard robust regression framework with outliers—that is, $y=f(x)+e$ where $e$ follows a contamination model of the form $(1-\\epsilon) N(0,\\sigma^2)+\\epsilon h$ where $h$ is an unown distribution. Given that, I analyze the problem from the perspective of robust estimation. What is the breakdown point of this estimator? For example, we know that the breakdown point of the median estimator is 50\\%, meaning it can handle up to 50\\% of the data being arbitrary without the estimator diverging. While I understand that the authors’ assumption about  range of $y \\in [-M,M]$ prevents divergence, a more balanced basis for comparison would be beneficial.\n\n3. I do not understand why the authors find it surprising that a computationally efficient nonparametric regression method, such as smoothing splines, demonstrates adversarial robustness. Given the objective function for spline fitting, which includes a penalty term that regularizes the function by penalizing roughness through the integrated squared second derivative, it is natural that smoother functions are less vulnerable to adversarial perturbations. Hence, adding a deviated sample is unlikely to cause a significant change in the fitted values.\n\n4. What does q = $\\boldsymbol{\\Theta}(n^\\beta)$ mean?\n\n5. The authors discuss the asymptotic behavior of the estimator as $n \\rightarrow \\infty$, but they do not address the small-sample regime, which is often more relevant in practical regression settings. Do you have any intuition on how the guarantees might change in such cases?\n\n6. In Figure 3, please include the curve for the best possible estimator in the same plot to clearly illustrate the gaps and assess how tight the results are.\n\n7. In the experiments, the attack types are rather simple. Please consider using a greedy search to optimize the attack strategy, which will help evaluate how robust and tight the bounds truly are.", "limitations": "The results apply only to the asymptotic setting.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\nIn terms of writing and clarity, this is the most well-written manuscript in my batch. The paper is well-organized, with a smooth flow that clearly articulates both the motivation and the contributions of the work. The problem of adversarial robustness in regression models—both parametric and nonparametric—remains underexplored in the machine learning community, as most existing studies focus on classification. From this perspective, I find the core idea of the paper both timely and compelling.\n\nWeaknesses:\n\nSome of the assumptions in the paper are not well-justified—for instance, the choice of modeling the function as belonging to a second-order Sobolev space. It is unclear whether this choice is made for analytical convenience or if there is a more principled reason behind it. Why not consider a Hölder space instead?\n\nThe paper includes only limited simulation results to demonstrate the advantages of the proposed approach, and no experiments have been conducted on real-world datasets. It remains unclear in which practical scenarios this method would be preferable to parametric alternatives. Including empirical insights or intuition based on real data would significantly strengthen the case for its applicability.\n\nThe results apply only to the asymptotic setting and consider contamination in the response variable y, but not in the input data x. This is notable since often adversarial certification methods in the literature primarily focus on input perturbations.", "was_revised": true, "final_justification": "I had a detailed discussion with the authors and found substantial value in this paper. The problem it tackles and the research direction it explores are both exciting and timely.\n\nIn my view, the main limitations are that the results are confined to the asymptotic regime and there is no evaluation on real data. However, these factors are not significant enough to ignore the merit of the work. Asymptotic results often provide key insights into the finite-sample regime, and given that the paper positions itself as a theoretical study, the absence of real data experiments is understandable.\n\nOverall, as I mentioned before, I am satisfied with the results presented in the paper and have decided to increase my score to 5. The authors should revise their paper according to our discussion to better reflect its value.", "rebuttal": "We thank the reviewer for the helpful feedback. Below we address the questions and will update the manuscript accordingly.\n\n1. >Some of the assumptions ... Hölder space instead?\n\nThe **second-order Sobolev space** is a widely studied and important functional class in nonparametric regression [2].  \nRegarding 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]. \nIn 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.\n\n2. >The results apply...input perturbations.\n\nRegarding 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. \n\nIn 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.\n\nRegarding the focus on **response (label) corruption**, we note that adversarial learning typically considers two main attack types:\n\n- **Label corruption (poisoning):** where the adversary perturbs the labels $\\{y_i\\}$ while keeping inputs $\\{x_i\\}$ fixed.\n- **Input corruption:** where the adversary perturbs the inputs $\\{x_i\\}$.\n\nBoth 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.\n\n3. >One high-level ... adversarial attacks.\n\nAs 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.\n\nParametric 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.\n\nIn 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.\n\n4. >While the authors... would be beneficial.\n\nOur 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.\n\nRegarding 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. \n\n\nFinally, 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.\n\n5. > I do not understand ...fitted values.\n\nWhile 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.\n\nWhat makes the smoothing spline particularly surprising and noteworthy is that it is not only **robust**, but also **optimal**., as mentioed in the above question.\n\n6. >What does $q = \\theta(n^\\beta)$ mean?\n\nIt 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$.  \n\n7. >The authors discuss... such cases?\n\nPlease see the response to question 2.\n\n8. >In Figure 3 ...results are.\n\nWe 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.\n\nIf, 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.\n\n9. >The paper ... applicability.\n\nFirst, we have extended our experiments as suggested. The detailed results can be found in our response to the following question.\n\nSecond, 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.\n\nIn 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.\n\n10. >In the experiments ... truly are.\n\nWe have extended our experiments along several settings to address this concern. \n\n### Effect of Large $M$\n\nLet $f(x) = x \\sin(x)$ over $x \\in [-1, 1]$, $M = 10$ and $q = n^{0.6}$.\n$\\mathcal{R}_2(f,\\hat{f})$\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.85|\n|Concentrated Corruption|-0.67|\n\n$\\mathcal{R}_\\infty(f,\\hat{f})$\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.59|\n|Concentrated Corruption|-0.48|\n\n### Adaptive Greedy Corruption\nIn this process, the attacker:\n1. Fits the baseline estimator on clean data.\n2. Computes $\\ell_i = (\\hat{f}(x_i) - y_i)^2$ for each sample: .\n3. Identifies $i^\\star = \\arg\\min_i \\ell_i$.\n4. Update $y_{i^\\star} \\leftarrow y_{i^\\star} + M \\cdot \\operatorname{sign}(\\hat{f}(x_{i^\\star}) - y_{i^\\star})$.\n5. Repeats the process until $q$ points are corrupted.\n\nBelow are the results for $f(x) = x \\sin(x)$ with $M = 100$ and input domain $[-10, 10]$:\n**$\\mathcal{R}_2(f,\\hat{f})$ (log-log slope):**\n|$q$|Slope|\n|-|-|\n|$q = n^{0.6}$|-1.12|\n|$q = n^{0.8}$|-0.91|\n\n**$\\mathcal{R}_\\infty(f,\\hat{f})$ (log-log slope):**\n|$q$|Slope|\n|-|-|\n|$q = n^{0.6}$|-1.21|\n|$q = n^{0.8}$|-0.97|\n\n### **3. Evaluation on Neural Network Functions**\n\nWe further tested our approach on a fixed 3-layer MLP neural network and $M = 500$, $\\sigma^2 = 1$, and $x \\in [-1, 1]$. \n$\\mathcal{R}_2(f,\\hat{f})$\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.80|\n|Concentrated Corruption|-0.65|\n|Adaptive Greedy Corruption|-1.29|\n\n$\\mathcal{R}_\\infty(f,\\hat{f})$:\n\n|Corruption Type|log-log Slope|\n|-|-|\n|Random Corruption|-0.86|\n|Concentrated Corruption|-0.48|\n|Adaptive Greedy Corruption|-1.31|\n\n[1] Jingfu *et al.* *Adversarial learning for nonparametric regression: Minimax rate and adaptive estimation*, 2025\n[2] Tsybakov *et al.*, *Introduction to Nonparametric Estimation*, 2008 \n[3] Liu *et al.*, *Kan: Kolmogorov-arnold networks.* ICLR 2025\n[4] Fey *et al.*, *Splinecnn: Fast geometric deep learning with continuous b-spline kernels.* CVPR 2018.\n[5] Doległo *et al.*, *Deep neural networks for smooth approximation of physics with higher order and continuity B-spline base functions.* (2022)."}]

Author rebuttal:

Meta-review: This paper studies the adversarial robustness of nonparametric regression under contamination, providing novel upper and lower bounds on estimation rates in second-order Sobolev spaces, and demonstrating how smoothing spline estimators achieve minimax-optimal robustness. The work fills a gap in the literature, as most prior robustness analyses have focused on parametric models.

The reviewers found the problem important and the contributions significant, though raised concerns about clarity of assumptions (e.g., $M$ that grows logarithmically with $n$), technical correctness in parts of the proofs, and the positioning of the results relative to prior work. Reviewer comments highlighted presentation issues and asked for clarification of key modeling choices.

The authors provided a detailed and thoughtful rebuttal that addressed these concerns point by point, clarifying assumptions, correcting inconsistencies, and expanding discussion of related literature and implications. While some reservations about exposition remain, the responses and additional experiments strengthened confidence in the correctness and relevance of the results.

Overall, weighing the novelty, technical depth, and potential impact against presentation concerns, I find the paper makes an important and timely contribution to the theory of robust learning. I therefore recommend acceptance.
Decision: Accept (poster)