Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization
Authors: Antonio H. Ribeiro
David Vävinggren
Dave Zachariah
Thomas B. Schön
Francis Bach
Venue: NeurIPS 2025 poster ()
Keywords: Kernel learning; adversarial training; generalization bounds
Primary area: theory
TL;DR: We introduce a computationally efficient kernel learning method that employs adversarial feature perturbations instead of input perturbations, achieving better optimization, adaptive regularization, and strong theoretical and empirical results.

Abstract: Adversarial training has emerged as a key technique to enhance model robustness against adversarial input perturbations. Many of the existing methods rely on computationally expensive min-max problems that limit their application in practice. We propose a novel formulation of adversarial training in reproducing kernel Hilbert spaces, shifting from input to feature-space perturbations.  This reformulation enables the exact solution of inner maximization and efficient optimization. It also provides a regularized estimator that naturally adapts to the noise level and the smoothness of the underlying function. We establish conditions under which the feature-perturbed formulation is a relaxation of the original problem and propose an efficient optimization algorithm based on iterative kernel ridge regression. We provide generalization bounds that help to understand the properties of the method. We also extend the formulation to multiple kernel learning. Empirical evaluation shows good performance in both clean and adversarial settings.

Kernel Learning with Adversarial Features: Numerical Efficiency and Adaptive Regularization
Antônio H. Ribeiro Uppsala University
David Vävinggren Uppsala University
Dave Zachariah
Uppsala University
intonio.hort..rieiine @t.uu.se
vavid.vavinggren @ it.uu.s
dave.zachariah @ it..uu.e
Thomas B. Schön
Francis Bach
Uppsala University
PSL Research University / INRIA francis. @aschiing @nnria.fr
thomas.schon @ @uu.se
Abstract
Adversarial training has emerged as a key technique to enhance model robust- ness against adversarial input perturbations. Many of the existing methods rely on computationally expensive min-max problems that limit their application in prac- tice. We propose novel formulation of adversarial training in reproducing kernel Hilbert spaces, shifting from input to feature-space perturbations. This reformu- lation enables the exact solution of inner maximization and efficient optimization. It also provides a regularized estimator that naturally adapts to the noise level and the smoothness of the underlying function. We establish conditions under which the perture-petturbed formulation is a relaxation pose an efficient optimization algorithm based on iterative kernel ridge regression. We provide generalization bounds that help to understand the properties of the method. We also extend the formulation to multiple kernel learning. Empirical evaluation shows good performance in both clean and adversarial settings.
the original problem and pro-
Introduction
Adversarial training can be used learn models that are robust against input perturbations (Madry et al., 2018). It considers training samples that have been modified by adversary, with the goal of obtaining a model that will be more robust when faced with newly perturbed samples. Consider training dataset {(x,, y/ }> consisting of samples of dimension X x R. The training procedure formulated as the following min-max optimization problem:
n
min FEH
max E(y:. f(x + Ar.)),
n
An,RRx
finding the best function f H. subject to the worst disturbances in predefined set of admissible input perturbations 2x. for instance, 2x = (Aæ ||Aæ|] < 8). For nonlinear functions, solving this problem directly is often challenging; simple optimization typically requires two stages. First we differentiate through the inner maximization, which is often approximated via projected gra- dient descent (Madry et al., 2018), and then we differentiate again through the solver steps in the computation of gradients through the outer minimization.
We consider H to be a reproducing kernel Hilbert space (RKHS) and represent the function f as a linear model applied to (potentially difnite-dimensional feature transformation of the input. Let Φ(x) x)) denote the corresponding feature map, so that any f E evaluated at & can be expressed as f(x) = (f, (xx))) where (,,)) denotes the inner product in H. see Schölkopf and Smola (2002). In this paper, we introduce perturbations directly the feature space rather than in the input space.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

Data Ridge CV True
Data Adv Ridge CV True
10 10-1
Test MSE
f(x)
f(x)
10
Smooth-Adw Kern
Smonth-Ridge CV-
10
Non- seeesmooth-AAd Kern
Non- smooth Ridge CV
0.0
0.5
1.0
0.0
0.5
1.0
10
10a Training size
Figure I: We compare adversarial kernel training with cross- coos-valldated kernel ridge regression (Ridge CV). All experiments make use of the Matern-5/2 5/ kernel. Left: we show how it fits smooth target function. Middle: a non-smooth target function. Right: we show the test mean square error (MSE) vs the size of the training dataset n, and illustrate how adversarial kernel training adapts to the target function similarly to kernel ridge regression with cross validation, without the need of tuning on hyperparameters.
This leads the following formulation:
E max Elys, (f, ((x,) d)). dEdx
min JEH T2
(2)
Note that the disturbance is applied in (potentially infnite-dimmesional) feature space H. rather than the input space X. As we will show, this formulation of adversarial training is particularly amenable to both analysis and efficient optimization. Working in the feature space allows for the exact solution of inner maximization problem, allowing for more efficient optimization. We further develop dedicated solver tailored to this formulation. Beyond its computational advantages, we establish theoretical guarantees showing that the feature-perturbed objective Eq. (2) upper bounds its input-perturbed counterpart in Eq. (I), ensuring that optimizing the former provides robustness guarantees for the latter. Empirically, we also demonstrate that this formulation achieves strong robustness to adversarial input perturbations.
We study the properties of our method not only in adversarial, but also in clean data, analysing the regularization properties of our estimator. We are interested in this estimator promoting model simplicity and enhancing generalization to unseen, non-adversarial data. In the linear (finite- dimensional) case, adversarial training has been shown to behave similarly to parameter-shrinkin approaches such as lasso and ridge regression (Ribeiro et al., 2023). In this setting, unlike when we are trying to defend against a threat model with fixed adversarial radius d, we can allow the training adversarial radius to decay as we get more data. Particularly, if we allow d x 1/ I/, our estimator is consistent and also have near-oracle performance (Ribeiro al., 2023; Xie & Huo, 2024). Previous work argue that key advantage of adversarial training as an alternative to parameter shrinking meth- ods is that it achieves the same sample-efficiency rates as the latter without requiring 5 to depend on the noise level (Ribeiro et al., 2023; Xie & Huo, 2024), paralleling the square-root Lasso (Belloni et al., 2011). In this paper, we prove that similar properties hold for mulation in (2), with default set without requiring knowledge of the signal-to- noise ratio yielding similar rates to kernel regression when this quantity is known. In practice, shown in Figure 1, the method has an adaptive regularization property with the default choice often performing compara- bly with kernel ridge regression with parameter chosen using cross-validane validaaali. The rightmost plot further highlights the method's adaptivity to the underlying function class.
for-
Our contributions are to propose and analyze feature- peuturree adversarial kernel training. We:
We identify condi- tions under which the perttrrb- formulation (2) upper-bounds the input-perturbed objec- tive (1), ensuring that solving the former yields guarantees for the latter.
Establish equivalences between input and peeturreeerturbed formulation:
Propose efficient solver: We show that the Saature-perturbel problem (2) allows for the inner maximization to be solved exactly and derive a tailored solver for its optimization.
Provide generalization guarantees: We derive upper bounds for the generalization error that highlight how the hyperparameter can be set without access to noise levels, leading to practical performance without hyperparameter tuning, with natural adaptivity to noise levels.
Extend the framework to multiple kernel learning: We generalize our formulation support combinations of kernels, enhancing expressivity.
These results demonstrate the practical and theoretical appeal of feature- perturbed adversarial learn- ing. We validate the method on real and simulated data. We make our implementation available at gi thub. com/ www.aanntnnngoo 9 anvversarial. serraiiingkkeneee

---

Table 1: Kernel functions and choices of 22x for which Ωx S {Az D=( + Ax) < 8). Equivalences proved in Appendix A. For the polynomial kernel, the constant depends on ||>||| and || + Ax| and is specified in the appendix.
Kernel
k(x,2")
2x
Linear
x: x!'
|| 12 S
Polynomial
(1 + x x
|4æ||2 1 //
Exponential
exp(-7llaz x' (1)
| || _ log 2
Gaussian
exp(->|læ x (
|Aa||2 S 1 log I-
2
Laplacian
exp(->/1æ> (11)
|Ax |1 1 log 2
7
2 Background
Different estimators will be relevant to our developments and will be compared in this pa- per. Let H. be Reproducing Kernel Hilbert Space (RKHS) associated with the kernel k(x, (0(x), ((xx)) and the induced norm || 1l See Bach (2024) and Schölkopf and Smola (2002). Here, we will focus on the squared loss for simplicity, but some of the developments can apply more generally.
Adversarial kernel training is our main object of study. We will call the following estimator feature-perurbed adversarial kernel training:
min JEH
max (y: (ʃ, (x;;)) + d))²
denx
where Dex = {d: | S 83. This estimator stands in contrast the input-perturbed adversarial kernel training defined in Equation (1), where the perturbation is applied to the input rather than the features. For simplicity, and unless otherwise specified, to refer to the ceature-perturbed variant, which is the main focus of this work. The ceature-perturbon will be explained in Section 3.
use the term adversarial kernel training
formulation relaxation of the input-perturbed counterpart, We will also show that is closely related to kernel ridge regression.
Kernel ridge regression (Bach, 2024; Schölkopf & Smola, 2002) estimates f E H. by solving,
Σ(: f(xx)) A JEH
min
where H. is reproducing kernel Hilbert space. Here, even though we might be optimizing over an space, the kernel trick can be used to transform the problem into regularized least squares problem using a kernel matrix.
Multiple kernel learning (Lanckriet et al., 2004: Rakotomamonjy et al., 2008) consists of finding of functions {f, Hy,j 1, 1,... .P} by solving
M ( (t,()))) + j=1....
min f,H,,
If If,l1HH,,
J=1
The framework combines multiple kernel functions-eed each representing different notion of simi- larity between data points-into single model, allowing the algorithm to simultaneously learn the model parameters and the best combination of kernels. This is particularly useful when data may have multiple modalities, or when is not possible for single kernel to capture all relevant patterns in the data. In Section 6 we propose an adversarial multiple kernel learning method.
Problem formulation
Here, we will establish properties of adversarial kernel training. Particularly, analyse the feature- perturbed adversarial error. We first prove that it upper bounds the input-perturbed adversarial error and later show that has casy-to-analyze closed-form solution.

---

Relation between feature and input perturbations: In the case of RKHS, we can always find Ox for which reature-perturbed adversarial kernel training adversarial kernel training, with Eq. (2) being an upper bound to Eq. (1). Particularly, the result holds for inputs within ball in the kernel distance (=( x') = (|<b(rr) (a: (b(r') Il| stated in the next proposition (proved in the appendix). Table also provides concrete examples of a few kernels and the sets 2g for which the above proposition holds. The proof is provided in Appendix A.I.
relaxation of the input-perturbed
Proposition 1. Let Uz = {d: |||| S 6} and 9xx = {Ax= (H( + Ax) S 8} then:
max (y (f, (xx) d)) 2 de
max (y - f(x Ar))? for all f E H. AvERt
The dual formulation of feature-perturbed adversarial error: Feature perturbed adversarial training is closely related to kernel ridge regression. The following proposition extends earlier
work (Ribeiro et al., 2023) and provides a characterization that makes this connection explicit.
Proposition 2 (closed formula for inner-maximization If Uu x, y, f. then we have:
{d
||d|| I 63 for every
max (y (f. + + = (1y f f()) + f11 defxx
This result shows that adversarial training loss under RKHS- norm bounded perturbations admits closed-fon form expression. As a consequence, our original optimization problem Eq. (2) can be equivalently rewritten as:
- > - f(x))) + {f
min JEN
which by inspection is very similar to ridge regression (for which the norm outside the paren- theses), and suggests similar properties. Still, as we will see in Section 5, the two problems have important differences that might make it advantageous use the latter formulation rather than kernel ridge regression.
This reformulation highlights an appealing property of feature- perturbed adversarial training. While both the input-perturbed and feature- perturre formulations can be expressed as pointwise max- ima of convex functions (and are therefore convex), the inner maximization in the input-perturbed case is non-concave and generally intractable. In contrast, the feature-perturbed formulation admits the closed-form solution derived above, yielding a convex and computationally favorable objective that preserves a clear interpretation in terms of robustness to bouddddddded perturbations. In the following, we propose an iterative algorithm to efficiently solve this problem.
4 Optimization
In this section, we propose iterative kernel ridge regression algorithm (Algorithm 1) for solv- ing (2) efficiently. The algorithm proposed here is influenced by Ribeiro et al. (2025), but adapted to non-parametric regression from the linear regression setting. Below, we describe the key parts of the algorithm, while additional details are available the appendix.
4.1 Proposed algorithm
Algorithm follows from the idea of using the following variational reformulation of the loss:
Iy f(x)
8
(Iv f(=) + 2 inf
(6)
nnn"
n70
17¹
s.t. r7 + 1n¹ 1,
0, 0.
The above reformulation is often referred as trick (Bach, 2011, 2019). And, for - f(x)] and || >> 0, allows the closed formula solution:
f(x) + 811f 1z
f(x) + 61
17 n
1y - f [x)
o|[ xx
We can use this trick to rewrite the original loss as the squared sum as a sum of squares. We apply the equivalence in (6) individually to each sample, yielding:

---

Algorithm Iterative Kernel Ridge Regression
Initialize: weights 1, I,..., n2; and, <- 5
Repeat:
Solve reweighted kernel ridge regression:
7 c arg min
E ws(n ((x))) + Allsf1l
2. Update weights (using Eq. (9)) w, UpdatoWeights Quit if StopCriteria.
Vi f(x))1 Pa
82
min inf
n
7
(
s.t. Th + m r 0. m
Vi.
We solve it as a block-wise coordinate problem, alternating between 1) solving for n7, .7' and com- puting the weights
82 for all
and 2) solving the kernel ridge regression problem that arises to find an approximated f.
4.2 Additional analysis and comments
Practical implementation. To make the algorithm numerically stable, we use variation of the n-trick with an added e that guarantees convergence the solution of (8) as e - 0. See Bach (2019) and Ribeiro et al. (2025). Using e > 0 is important to avoid numerical problems and to guarantee convergence. Otherwise, when either large values for 1 1/1 and an ill-conditioned problem.
f(x) || are too small, could obtain extremely
Convergence. The convergence of the above algorithm (for 0) follows from results about the convergence of block coordinate descent for problems that are jointly convex and differentiable with unique solutions along each direction (Luenberger & Ye, 2008, Section 8.6).
Computational complexity. Solving kernel ridge regression typically incurs computational cost of O(r²)) due to the need to factor the kernel matrix. This term usually dominates the cost of Algo- rithm 1, that usually converges within few iterations (Bach, 2019; Ribeiro al., 2025). To further reduce complexity, Ribeiro al. (2025) proposes using the conjugate gradient (CG) method to ap- proximately solve the reweighted ridge regression problem with only quadratic complexity. Similar considerations apply our setting. Moreover, since our formulation relies on kernel evaluations, it is naturally compatible with Nyström approximations (Williams & Seeger, 2001), offering addi- tional scalability for large datasets. While these extensions are promising, they fall outside scope and are not explored in the current study.
5 Generalization bounds
We establish worst-case error bounds for adversarial kernel training. Particularly, we assume that data generated as
= f*x)) + ow.
where f the function that we want to recover and ur is unitary vector representing the noise. We use to quantify the magnitude of the noise, and R to denote the function magnitude R = || We provide upper bounds on the in-sample excess risk:"
E(f ff)
n (f(..))
This setting is also called fixed-design setting (Bach, 2024). We choose to study it because it pro- vides maximum intuition without some of the additional technical challenges of the random-design
'This quantity is called excess risk because it is equal to the difference between the expected risk EulL _ Di,,(( 3x)²] and the Bayes optimal risk E. [1 En (f' (xx))) w) (Bach, 2024, Prop. 3.3).
5

---

case, where we would bound (xlf(=) fx)). As discussed Section 5.3, bounds in the fixed- design setting can also inform results in the random-design setting (Wainwright. 2019, Chap. 14). As we will see, adversarial training has the desirable property that the parameter 8 can be set without knowledge of the noise magnitude a. The same is not true for kernel ridge regression.
Our analysis is as follows: we first consider deterministic values of w and the function f within the model class, that is, f E H. We define ry and [ E IR as follows:
n
7
sup Ilal| n
Σ ( 12
B sup ( n
wig(z;),
(10)
$1
where we take supremum over all g E H. and we obtain bounds in terms of this quantities. This analysis is described in Section 5.1.
Next, we obtain high probability bounds for the case where the noise is Gaussian. Particularly under Gaussian noise we have, with high probability, that = O(n 1/2)
(1/2) ) for linear or any translational invariant kernel. On the other hand, with high probability, 3 Opp/n) (1) for linear kernel or for
the matérn kernel / = O(n O ). We will discuss these results in detail in Section 5.2. Finally, Section 5.3 mentions generalization to the case where the model is mispecified to the random design setting. This progression allows us to progressively analyse more advanced cases, with each section building on the previous one.
5.1 Deterministic bounds and well-specified models
Let consider deterministic values of w. chosen such that - 1= u = 1. The next theorem bounds the excess risk in terms of y and (3. We are using proof techniques similar to those in Wainwright (2019, Chapters 7 and 13), and also related to those developed in the context of adversarial train- ing (Ribeiro et al., 2023; Xie & Huo, 2024).
Theorem 1 (Excess risk for adversarial kernel training). Let quantify the magnitude of the noise, and Rt = | 1lx denote the function magnitude, and 6 be the adversarial training radius. We have the following upper bound on the excess risk:
EfP f") S min(B B3ad)).
where Badd = 1(222 2(20R & + 1²) and Bydd = 4ooR+ 108 12 + 1602
Considering B3ddv and 13gd allows us to describe two different regimes. The optimal choice for Baddy is to set 8 x y. In this case, ignoring constants and higher order terms: Budv = O(aRR)) The bound based on Badd is bound that does not really improve as we increase 6, and the optimal choice here would be = Overall, for any 8 < 3. we obtain Badv = O 32). Next, we present the equivalent result for kernel ridge regression for comparison.
Theorem 2 (Excess risk for kernel ridge regression). Let quantify the magnitude of the noise, R | ||x, and let À be the regularization parameter in kernel ridge regression Equation (3). We have the following upper-bound on the excess risk E( - --) S min(B,r Blr). Where Bkrr 2 (R)+)>)² and BKr 2
Similar considerations apply here and each bound allows us to describe different regime. The optimal choice for optimizing Bkr is to set x 77 In this case, B = ( Rty. The bound based on B is a bound that does not really improve as we increase X, and the optimal choice here would be À = 0. Overall, for any X < d² 32, we obtain Bkr 2
Signal-to-noise ratio. Notice that for kernel ridge regression if we set without knowledge of the signal-to-noise ratio a o/R, for instance if À x 7, the resulting excess risk is: BtT = O( +R R²))). Indeed, kernel ridge regression exhibits a quadratic dependency on the noise level unless is tuned with prior knowledge of the signal-to-non the noise level automatically, achieving near-optimal performance without requiring knowledge of a/ R. This adaptivity is a key ad advantage of the latter approach.
ratio. In contrast, adversarial kernel training adapts to

---

5.2 High-probabilie bounds under Gaussian noise
In this subsection, we assume the noise variables are Gaussian and iid. w (0, 4n). We define y and follows:
E (00
sup Ialls
w. (o((m)))))
sup ((a)
(((()))))
(11)
These are usually called Gaussian complexity and local Gaussian complexity. Where we consider any value 3 satisfying the inequality. The following results allow us use Ý and B in our analysis, showing that they upper bound y and /3 with high probability.
Proposition 3. Let μ4 122 > matrix with entries ki = ka,, x.). w ~ N(0, In) and é > O, then:
Mn be the eigenvalues of the kernel matrix K, i.e., the
We have S 7 + with probability higher than 1 *5;
And, 3 v 3 + with probability 1 cxp( n( ). as long as E 2
We can obtain closed-form expressions for y and 3 which enable a more explicit analysis of the upper bounds derived in the previous section. We do it for adversarial training, but similar argument holds for kernel ridge regression.
On the dimension-free bounds depending on 7. We have 7 V Vu(K) where tr(.) denotes the matrix trace. For any normalized kernel, i.e., one satisfying f(z,2)) = follows that tr (K) = n and thus y 1/ nr. Examples include Gaussian and Matérn kernels. A similar rate holds for the linear kernel: if M max; |ar: then 7 M/vn. Combining this with the results from the previous section, we obtain the following dimension bound for adversarial training:
(RR Vn
Budd 0
for
5
(Linear or translation-invarian kernel)
Vn
We refer to this as a dimension-free bound since it does not depend explicitly on the input dimension P. although p may still influence the a, R. M.
On the faster (but dimension-dependenn) rates in 32, We can also derive closed-form expressions for 3. The derivations are very similar that of (Wainwright, 2019, Chapter 13) and provide aditional details in Appendix C. In particular, we have 3 Opp/n) for the linear kernel and 32 = (n -2/(2+p/v) for the Matérn kernel. This leads the following bounds:
O²p n for
Badv -
8
P R
(Linear kernel)
and
Badv = = 2/122 2/12-p/o))
for
8 < 0 n
2/(2+p/u)
(æ-Matérn kernel)
R
Here, 8 is not required to scale with n in a specific way it only needs to be sufficiently small. The linear recovers the classical p/n rate of standard linear regression, which converges faster but explicitly depends on the number features p.
5.3 Additional analysis and comments
Bounds for the mispecified case. For adversarial kernel regression, i.e., when f & H we can use the following equations
E(J (") 2 f") + min BBdy).
Note that the results involve the terms (Bady B3 that appear in the well-specified case. Similar expressions also apply to kernel ridge regression. The first term in the equation is the ap- proximation error of trying approximate [f S R and the second term the estimation error. For translational invariant kernels, we can leverage results from Bach (2024, Section 7.5.2) to anal- yse the left-hand side above.
Bounds for the random design case. We are often interested the random design case, i.c., bounding Ex (f() f fx(x). We suggest that the difference between this quantity and the excess
7

---

risk fff-"" can be bounded by the Radamacher complexity (Wainwright, 2019, Chapter 14) or lo- calized Radamacher complexity (Wainwright. 2019, Chapter 14). For instance, see Corollary 14.15, where the authors establish such results for Kernel Ridge Regression. We believe this deserves more careful investigation, but due the relation between Gaussian and Radamacher complexity in many cases, the rate for the random design case should be the same as the ones we observe here.
6 Adversarial multiple kernel learning
Let us denote the space H. = -i Hi = [Σ}=1 ff (a) where f, E Hj for = 1,, 1.... ,D. Here, we propose an adversarial multiple-kernel learning method, where we solve:
min EER
max (y (f. ((x) + d))? deap
(12)
We consider S2 to be the intersection of balls in different kernel spaces as attack region:
Og Pp = - { E H₁ I|d s _ō} - E M2
||dll S o).
max j=1,".,
The framework combines multiple kernel functions- representing a different notion of sim- ilarity between data points-into single model, allowing the algorithm learn both the model parameters and the best combination of kemels simultaneously. This is particularly useful when data may have multiple views modalities, when single kernel captures all relevant patterns in the data. Notably, many of the techniques observed in the context of reature-perturbed adversarial kernel training have clear parallels in Equation (12). We highlight some of these connections below.
Relation with attacks applied the input domain. Our optimization problem (12) a relaxation
of
min FER 7 1=1 Ax,
max (y - f(x Am:)))
(13)
for 2x = -2{Ax:: Dx, (x, x Ar) S 83 10 (Ax: : max; Dz, (2, x + Da) S 6).
Reformulation and optimization. Proposition 9 in the Appendix, allow for the reformulation of (12) the following minimization problem
D +
D
2
min f.H
M
+0 j=1
11
j=1
which by inspection very similar to the multiple kernel learning problem. similar algorithm to Algorithm also applies here and is described in Appendix D.
7 Related work
Adversarial attacks (Bruna et al., 2014; Goodfellow et al., 2015) can significantly degrade the per- formance of ttate-of-the-art models and adversarial training has emerged as one of the most effective strategies to prevent vulnerabilities.
Adversarial training in neural networks. Adversarial training is often studied in the context of neural networks and deep learning. Traditional methods for solving adversarial training require solving min-max problem: minimizing parameter vector while maximizing the error with lim- ited attack size. Examples of traditional methods to solve the inner maximization include the Fast Gradient Size Method (Goodfellow et al., 2015), and PGD-type of attacks (Madry et al., 2018). The problem can be solved by backpropagating through the inner loop (Madry al., 2018). Re- cent efforts also aim to make adversarial training more efficient by approximate but faster update strategies. Indeed, recent works have sought to simplify adversarial training by relying on single- step (Wong et al., 2020) or latent-space perturbations (Park & Lee, 2021), rather than more costly multi-step procedures. Methods such TRADES (Zhang et al., 2019) explore variants of robust optimization that trade off accuracy and robustness using tractable approximations. A recent (and more theoretically focused) study by Hosseiii al. (2025) proposes method for learning multi-index models in an adversarially robust manner using two-layer neural networks-wher the first layer can be trained in standard way, and the second layer minimizes the adversarial loss.
8

---

We develop framework not intended for neural networks, but one that we hope can inspire new methods in that domain. Our approach builds on theoretical insights from linear models, extending them to nonparametric settings.
Adversarial training in linear models. Adversarial training in linear models has been extensively studied over the past five years. The linear setting serves as tractable framework for analyzing the behavior of deep neural networks. For instance, it has been used to study the robustness- -buusress-accuuracy trade-off (Ilyas et al., 2019; Tsipras et al., 2019) and the impact of overparameterization on adver- sarial robustness (Ribeiro & Schön, 2023). Asymptotic analyses have further examined adversarial training in binary classification and regression (Javanmard & Soltanolkotabi, 2022; Javanmard al., 2020; Taheri et al., 2022), and also for random feature models (Hassani & Javanmard, 2024). Re- lated work has also investigated Gaussian classification (Dan et al., 2020; Dobriban et al., 2023), the effect of dataset size on adversarial vulnerability (Min et al., 2021), and the behavior of & -attacks on linear classifiers (Yin et al., 2019). In this work, we explore how these insights can be extended to function spaces and non-aaramttric models. This allow for leveragin results from linear models, In particular, connections between ---nrrm adversarial training and ridge regresion, have been well established (Ribeiro et al., 2023). The optimization approach presented in Section extends the method of Ribeiro et al. (2025) to nonparametric settings, while the generalization bounds derived in Section 5 adapt proof techniques from Ribeiro et al. (2023) and Xie and Huo (2024) to the context of nonparametric regression.
Robust kernel regression. There is substantial body of work on robust kernel ridge regression, primarily aimed at improving robustness to outliers. These methods often rely on M-estimators (De- bruyne et al., 2010; Hwang et al., 2015; Wibowo, 2009) or quantile regression (Li et al., 2007), and are typically optimized using iterative reweighted ridge regression schemes. While our method shares some algorithmic similarities, its purpose and formulation differ fundamentally. Our objec- tive is not robustness to outliers, but robustness to adversarial perturbations. Moreover, our formu- lation is not based on an M-estimator: the adversarial relaxation leads to an objective where both the loss and the regularization are jointly shaped by the perturbation set, as shown in Equation (2). Another related line of work replaces the ridge penalty in kernel ridge regression with an É penalty to promote spansity in the observations (Allerbo, 2025; Feng et al., 2016; Roth, 2004). Alternatively, some approaches use max-norm (i.e., foc regularization to train kernelized support vector machines that are robust to label attacks (Russu et al., 2016). Our setting differs from both: we do not aim for sparsity, nor do we focus on robustness to label noise. Instead, we are concerned with robustness to structured perturbations in the input space.
Numerical experiments
0.8
Adv Kora
Kemel Ridge
0.6
The numerical experiments aim to evaluate the performance both in clean and adversarially perturbed data. We emphasize the optimal con- figuration for clean data does not necessarily co- incide with that for adversarial robustness. For the clean data evaluation, following the intuition from our generalization analysis, we suggest de- crease the perturbation radius as the sample size increases, 1/ /n. In contrast, for robust eval- uation, it is often beneficial to keep the adversarial radius fixed ó x 8test.
0.4
R2
0.0
Polution
Diabctes
crime
Wine
Abalone
Figure 2: Kernel ridge vs adversarial kernel training. Compared using R22 (higher is better).
Evaluation on clean data: adaptativity to smoothness and noise levels. We evaluate the proposed methods on both smooth and non-smooth target functions (same setting as in Figure 1). In particular, we investigate whether adversarial kernel training can adapt to the target's ' smoothness. Kernel ridge regression with cross-validation can automatically achieve such adaptation (Bach, 2021). Here, we perform a similar experiment, applying adversarial training with the default parameter choice (6 x n -1/2), and observe comparable behavior. The results in Figure 3 show that adversarial kernel training naturally adjusts to the regularity of the target function across different kernels. In these plots, the dashed line represents the linear approximation, whose slope indicates the observed efficiency rate (reported in Table S.1). Finally, Figure S.2 examines robustness to varying noise levels, comparing sine, square, and linear targets.
Evaluation on clean data: performance on bechmarks. In Figure 2, we compare the per- formance of adversarial kernel training with kernel ridge regression across several regression

---

10
Test MSR
10-1 1
Test MSE
10-1
Test MSE
10"1
Smooth
10
Smooth
10-2
Kern
10--
Sucoill-Ragge CVV
Susoeth-Rallee CV
Saundi-Rille CV
Nun-emnoth--ee Adl Kem
smooth Ridge
10
Not-smmoth Adl Keen
smooth Ridge
1003
San--amootl--A Adl
smooth Ridge
10
10
10*
10
10
10 Training size
10
10
10
10
Training size
Training size
(a) Matérn 1/2
(b) Matérn 3/2
(c) Gaussian
Figure 3: We compare adversarial kernel training with eross- cols-validated kemee ridge regression (Ridge
CV). We show the test mean square error (MSE) vs training size n. for different kernels.
Table 2:
Comparing methods under adversarial attacks (Abalone). Reported values are test set R² scores (higher is better), with bootstrapped interquartile ranges (Q1-Q3) shown in parentheses. The best result for each setting is highlighted in boldface.
test: Linetime atlack 62
lest- atlack for
training method
attack
[|Arl]| S 0.013
(|]Aalla $ 0.13
[[]Am] S 0.013
{ ~ S 0.1)
Adv Kern (6 x n n
0.57 (0.56-0.55) 58)
0.55 (0.54-0.57)
0.39 (0.37-0.40)
0.54 (0.52-0.55) 0.52 (0.5--05))
0.13:0.11-0.16
Ridge Kemel (A crass-validate))
0.57(0.56-0.59)
0.55 (0.53-0.56)
0.26 (0.24-0.28)
-0.16 (-0.20001111
Ady Kern
x x 0.01]
0.56 (0.55 0.58)
0.55 (0.53 0.56)
0.40 (0.39 0.42)
0.53 (0.52 0.55)
(0.16 0.20)
Adv Kern
d|I 0.1}
0.38 (0.37-0.39)
0.38 (0.37-0.39)
0.35 (0.34-0.36)
0.37 (0.36-0.38)
0.30 (0.29-0.31)
Adv Input
Aar S 0.1)
0.57 (0.56 0.59)
0.55 (0.53 0.56)
0.27 (0.25 0.29)
0.52 (0.51 0.54)
0..14 (c0.17 0.11)
Adv Input
Ar o0 E 0.1)
0.57 (0.55-00.58)
0.54 (0.53-0.50) 0.56)
0.27 (0.25
0.52 (0.51-0.53)
.0.11 (.0.4-0.08)
datasets. For kernel ridge regression, hyperparameters are selected via cross-validation over Y E (10,1,0.1, 10 2, 10 3} and X {1,0.1,10 10. For adversarial kernel training, use a default adversarial radius and select y from the same range using cross- cross-validttion. Thanks to its reduced hyperparameter space, adversarial kernel training consistently performs on par with or better than kernel ridge regression across the evaluated benchmarks.
Robustness to adversarial attacks. In Table 2, we focus on one of the benchmark datasets. In addition to the clean-data evaluation, we include four new training variants based on feature-space adversarial kernel training with fixed values of 5-which a natural choice when the objective is adversarial robustness. For comparison, we also include input-space ad adversarial training base- line with gtrain 0.05, following Equation (I), trained for 300 epochs using Adam. All methods are evaluated both on clean data and under test-time adversarial attacks in the &2 and foo norms. Results on additional datasets are provided in the Appendix.
Notably, although our proposed method is trained with perturbations in feature space, it remains highly robust to input-space attacks, outperforming approaches explicitly trained for input robust- ness. We hypothesize that this arises from the feature-perturben formulation offering more favor- able optimization properties. Furthermore, comparing models feture- perttereetrrddddeee adversarially trained models with |]d]| R S 0.01 and ||d||H S 0.1 illustrates the trade-off hetween clean and adversarial accuracy: as the feature-space adversarial radius 5 increases, the model becomes more robust to input-space attacks particularly when the attacker has large budget, e.g.. ||Ax ( < albeit at the cost of a drop in clean performance. Interestingly, our method still surpasses direct input-space adversarial training even under the same test-time threat model.
Conclusion and future work
We covered several aspects of the proposed method. Our goal was to present a unified perspective that makes the method broadly applicable, by including optimization, generalization and robustness properties. Different aspects however deserve deeper investigation. Further directions include im- proving the optimization focusing large-scale systems. The proposed generalization bounds also deserve more detailed analysis and future work, we aim to fully explore the results in the mis- specified and the random design setting. Another promising direction is generalizing to classification and further study the multiple kernel learning scenario. The ideas here also naturally extend to infinitely wide neural networks, which can often be analyzed using RKHS tools. A key example is the neural tangent kernel (NTK) framework (Jacot et al., 2018). Moreover, it would be interest- ing to explore adversarial training for infinitely wide networks as a tool to guide architecture and hyperparameter selection, following similar ideas to Yang et al. (2021).
10

---

Acknowledgments and Disclosure of Funding
This work was partially developed during AHR visit to the SIERRA team at INRIA. We would like to thank Dominik Baumann, Oskar Allerbo and Elis Stefansson for giving feedback on the early ver- sions of this manuscript. We would also like to thank Bruno Loureiro for the interesting discussions around the theme. TBS and DZ are financially supported by the Swedish Research Council, with the projects Deep probabílistic regression-new models and learning algorithms (project number 2021- (4301) and Robust learning methods for citto--distribution tasks (project number 2021-05022); and, by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by Knut and Alice Wallenberg Foundation. TBS, AHR and DZ are partially funded by the Kjell och Märta Beijer Foundation. FB by the National Research Agency, under the France 2030 program with the reference "PR[AIJRIE-PSAT (ANR-23-JACL-0008))
References
Allerbo, O. (2025). Fast Robust Kernel Regression through Sign Gradient Descent with Early Stopping, Elec- tronic Journal of Statistics, 19(1).
Bach, F. (2011). 1). Optimization with Sparsity-Inducing Penalties. Foundations and Trends in Machine Learning,
4(1). 1 1-106.
Bach, F. (2019). The "eta-trick" or the effectiveness of reweighted least-squares- - Machine Learning Research Blog.
Bach, F. (2021). The quest for adaptivity Machine Learning Research Blog.
Bach, F. (2024). Learning Theory from First Principles. MIT Press.
Bach, F. (2025). Unraveling spectral properties of kernel matrices - II Machine Learning Research Blog.
Belloni, A., Chernozhukov, V., & Wang, L. (201 1). Square-Roof Root Lasso: Pivotal Recovery of Sparse Signals via
Conic Programming. Biometrika, 98(4), 791-806.
Bruna, J., Szegedy, C., Sutskever, L., Goodfellow. L., Zaremba, W., Fergus, R., & Erhan, D. (2014). Intriguing properties of neural networks. International Conference on Learning Representations (ICLR).
Cortez, P., Cerdeira, A., Almeida, F., Matos. T., & Reis. (2009). Modeling wine preferences by data mining from physicnchemical properties. Decision Support Systems, 47(4), 547-553.
Dan, C., Wei, Y., & Ravikumar, P. (2020). Sharp statistical guaratees for adversarially robust Gaussian classifi-
cation. In International Conference on Machine Learning (ICML) (pp. 2345-2355).
Debruyne, M., Christmann, A., Hubert, M., & Suykens, J. A. K. (2010). Robustness of reweighted Least
Squares Kernel Based Regression. Journal Multivariate Analysis, 10)(2), 447-463.
Dobriban, E., Hassani, H.,, Hong, D., & Robey, A. (2023). Provable tradcoff's adversarially robust classifica- tion. IEEE Transaction on Information Theory, 69(12), 7793-7822.
Efron, B., Hastie, T.. Johnstone, I., & Tibshirani, R. (2004). Least angle regression. The Annals of Statistics, 32(2), 407-499.. Feng, Y., Lvv, S.-G., Hang, H., & Suykens, J. A. K. (2016). Kernelized Elastic Net Regularization: Generaliza-
tion Bounds, and Sparse Recovery. Neural Computation, 28(3). 525-562.
Goodfellow, I. J., Shlens, J., & Szegedy, C. (2015). Explaining and Hamessing Adversarial Examples. Inter- national Conference on Learning Representations (ICLR).
Hassani, H., & Javanmard, A. (2024). The curse of overparamctrization in adversarial training: Precise analysis of robust generalization for random features regression. The Annals of Statistics, 52(2), 441-465. Hwang, S., Kim. D., Jeong. M. K., & Yum, B. (2015). Robust kernel- regression with bounded influence for outliers. Journal of the Operational Research Society, 66(8), 1385-1398.
Ilyas, A., Santurkar, S., Tsipras. D., Engstrom. L.. Tran, B., & Madry. A. (2019). Adversarial Examples Are Not Bugs. They Are Features. Advances Neural Information Processing Systems, 32.
Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks. Advances in Neural Information Processing Systems 31.
Javanmard, A., & Soltanolkotabi, M. (2022). Precise statistical analysis of classification accuracics for adver- sarial training. The Annals of Statisticy. 50(4). 2127-2156.
Javanmard, A., Soltanolkotabi, M., & Hassani, H. (2020). Precise tradeoft's in adversarial training for linear regression. Proceedings of the Conference on Learning Theory, /25, 2034-2078.
Lanckriet, G. R. G., De Bie, T., Cristianini, N., Jordan. M. 1., & Noble. W. S. (2004). A statistical framework for genomic data fusion. Bioinformatics (Oxford, England), 20(g6),,,,2(16)), 2626-2635.
Li, Y., Liu, Y., & 7hu, J. (2007). Quantile Regression in Reproducing Kernel Hilbert Spaces. Journal of the American Statistical Association. 102(477), 255-268.
Luenberger, G.G & Ye, Y. (2008). Linear and nonlinear progranmingg (3rd ed). Springer. Madry, A., Makelov, A., Schmidt, L.,, Tsipras, D., & Vladu, A. (2018). Towards Deep Learning Models Resis- tant to Adversarial Attacks. International Conference for Learning Representations (ICLR). McDonald, G. C., & Schwing, R. C. (1973). Instabilities Regression Estimates Relating Air Pollution to Mortality. Technometrics, 15(3), 481.

---

Min. Y., Chen, L.. & Karbasi, A. (2021). The Curious Case of Adversarially Robust Models: More Data Can Hclp, Double Descend, or Hurt Generalization. Conference on Uncertainty in Artificial Intelligence, 161, 129-139.
Mousavi-Hosseeing A., Javanmard, A., Erdogdu, M. A. (2025). Robust feature learning for multi-index mod- els in high dimensions. International conference on representation learning, 2025, 18774-1888 18812. Park, G. Y. & Lee, S. W. (2021). Reliably fast adversarial training via latent adversarial perturbation.
Rakotomamonjy. A., Bach, F. R.. Canu, S., & Grandvalet, Y. (2008). SimpleMKL. Journal of Machine Learning Research, 9(83), 2491-2521.
Redmond, M.. & Baveja, A. (2002). data-driven software tool for enabling cooperative information sharing among police departments. European Journal of Operational Research, (4)(3), 660-678.
Ribeiro, A. H.. Schön, T. B. (2023). Overparameterized Linear Regression under Adversarial Attacks, IEEE Transactions on Signal Processing.
Ribeiro, A. H., Schön, T. B., Zahariah, D., & Bach, F. (2025). Efficient Optimization Algorithms for Linear Adversarial Training. International Conference on Artificial Intelligence and Statistics (AISTATS). Ribeiro, A. H.. Zachariah, D... Bach, F., & Schön, T. B. (2023). Regularization properties of adversarially trained lincar regression. Advances in Neural Information Processing Systems.
Roth, V. (2004). The generalized LASSO. IEEE Transactions on Neural Networks, 15(1), 16-28.
Russu, P., Demontis, A., Biggio, B., Fumera, G., & Roli, F. (2016). Secure Kernel Machines against Evasion
Attacks. ACM Workshop on Artificial Intelligence and Security, 59-69.
Schölkopf, B., & Smola, A. J. (2002). Learning with Kernels: Support Vector Machines, Regularization, Opti- mization, and Beyond. MIT Press,
Taheri, H., Pedarrsaii R., & Thrampoulidis, C. (2022). Asymptotic Behavior of Adversarial Training in Binary Classification. JEEE International Symposium on Information Theory (ISIT), 127-132. Tsipras, D., Santurkar, S., Engstrom, L.., Turner, A., Ma, A. (2019). Robustness May Be Odds with Accuracy. International Conference for Learning Representations.
Wainwright, M. J. (2019). High-Simensional Statistics: A non-Asymptotic Viewpoint. Cambridge University
Press.
Wibowo, A. (2009), Robust kernel ridge regression based M-estimation. Computational Mathematics and Modeling, 20(4), 438-446. Williams, C. K. I., & Seeger, M. (2001). Using the nyström method to speed up kernel machines. In Advances in neural information processing systems 13 (NIPS 2000) (pp. 682-6662666 228).88). MIT Press. Wong, E., Rice, L.,, & Kolter, J. Z.. (2020). Fast is better than free: Revisiting adversarial training.
Xie, Y., & Huo, X. (2024). hiig--dimensionll (Group) Adversarial Training in Linear Regression. Advances in Neural Information Processing Systems.
Yang, G., Hu. E.. -Babuschkin,, I., Sidor, S.. Liu, X.. Farhi, D., Ryder, N., Pachocki, J., Chen, W., & Gao, J. (2021). Tuning Large Neural Networks via Zero-Shot Hyperparameter Transfer. Advances Neural Information Processing Systems, 34, 17084-17097.
Yin, D., Kannan, R., & Bartlett P. (2019). Rademacher Complexity for Adversarially Robust Generalization. International Conference on Machine Learning, 7085-7094.
Zhang, H., Yu, Jiao, J., Xing. E. P., Ghaoui, L.. E., & Jordan, M. I. (2019). Theoretically Principled Trade-off between Robustness and Accuracy.
12

---

Table of Contents
A Problem formulation
Proof Proposition
A.2 Proof of regions in Tahle
B Convergence rates
B.I Proof of Theorem 2
Proof Theorem
B.3 Proof of Proposition 3
C Gaussian and local Gaussian complexities across different RKHS
viii
C.I Computing the Gaussian complexity 7.
C.2 Computing the local Gaussian complexity 3?.
D Adversarial multiple kernel learning
X
E Numerical experiments
X
E.1 Datasets
X
Additional results
NeurIPs Paper Checklist
xiv

---

A Problem formulation
A.1 Proof of Proposition
Let Av E Ωx then by definition
[1 - Φ( + Az) Du(x, +a) I
hence (Φ(x)) d(x Ax)) S2x and follows that:
max (y:: f + Ax))² Awellx
max (yi (f, (f. Art))) Awellx
(y, (f. ((x) d))²
d= -ax) - ((x)).
Aweflx
max (yi (f. (f=) + d))²
deft
A.2
Proof of regions in Table
Linear kernel.
For the linear kernel:
ar'r,ar) x
we have the evaluation functional (xx) x, and the induced RKHS space H. = R², Hence:
(x( + Ar) |
and 2x = [Ax: ||A2||2 S 8}.
Translation invariant kernels. Now, let have any kernel
k( x²) [[11 x'll)
for which an strictly decreasing function with f(0) we use that:
(x x') k(æ, x) 2k(x, x²) + k( xx) 2 2/([1 (o'lm=x1l)) x'Il)
where the second inequality we plugged the definition of kernel. Now, since / monotonic, Du(æx x + Ax) S implies that
| - x'1l S s 6
Now we can apply this result to kernels of interest, particularly, Gaussian, Laplace and Matérn kernels.
Gaussian kernel.
The gaussian kernel
k( x') = exp(->/l x'
x'112).
falls into the above scenario and, hence, the above derivation implies that
exp(->|1x- x'13)
1 7
|| - 2'112 < log
and the result follows. Very similar derivations hold for the Laplacian and exponential kerness.

---

Polynomial.
If Az = x' - 2 E Ω2 then
8² z Dx( x')
k(x, x:) k(a=', x.) 2k(x,xx')
Now, rearranging and exponentiation by 1/d.
211 x')
z (k( x) + kkak x0) - 02)1/0
M M (k( m) + k(a' x )) 82/d
22/((k(a x)k((' 1/(d)) 82/4
Where, (a) follows from applying Proposition 4 with ) )/ 1/d. And, (b) follows from using Proposition with Ç (= 1. Therefore:
8²
22/d2 1/d 2 -k x¹) 2//2//
3/d= + (k(æ, 2))( , 2())2
1/ k(a' w') x' 1/d (kxxx k(0', x 3/20/2 2 x)
Where the last equality follows from summing and subtracting kk( x) + ka('', x') and regrouping. Now, will rewrite A and B, using the definition of polinomial kemnel, ic. k< x') = =1 x T=. On one hand,
2A k(xx x 1/d + k(a', x') 2k(x x' 2'/ ||
and, on the other hand,
2B (V 1
x 2
/1 + ||>11 ||a=|||? 2|
(||05)
(v +
/
Xx 1|2)2
||
[1|==]]
+ 1x )
ax 1232
[[[[==]] + oo !I)?
(v
1 +
|
1oo" )12)2
A
1
[[|[=]]| + || 1=
2
| + x
Am
[2 + ||21
2 ||=||
|
Hence,
1/d2-11/ > A B
8/dd 1/d > Ax 1|
2 + |0
|
82/d2-1/d +
|
| (12)
A
81/22-1/22) /2 ||0||
x
Putting everything together, we obtain
l/l/d
Ax
for C= 2-1(2(2) / + x Next, we prove the proposition that was used.

---

Proposition 4. For any 0 < 2 < 1 and d any positive integer, we have that
- 2) < --
Proof. We can prove it recursively. The result trivial for d now if assume that:
(1 2)d-1 I 2d-1
since (1 z) > we have
(1 -1-2) 2) (1- 5(1 2) S ---1 +2 1 $1+ + 2d
The result follows.
B Convergence rates
B.1 Proof of Theorem 2
In our developments, we will also use the following proposition.
Proposition 5. For any Ç > O,
1 ab
_a² a² + 5
2C
For kernel ridge regression we minimizing the cost function:
L(F) - Σ v f(x)))) Alls
using that yı = (x;) + ow; we obtain for estimated function that:
L 1 Σ (f + tow; +
(3) = E( fr)
2x
n Σ wi (f(x)) (x;)) + to² + -113112
where in (a), we used that " wp and E( - -' E - fxx))) By
-f(
definition I(F) < I(f*) and by similar procedure we can obtain that I(f*) o² + > Hence, simple algebraic manipulation shows that:
2x
E(e fd)
+ (115 -1
(S.1)
Bounds as a function of 7. By the definition of y in the theorem assumption:
w: (f(.)))) f((),) s xlf f"1
Hence:
0 f²) S 20 - ff A(1 - |1 lise)
(S.2a)
240
< | HM
1x*11= - f'H + A(11f*11 - (1
ll + [l3l)x)
(S.2b)
[1220000 +x) || -11
< (1]S | + (1311z)
(S.2c)
And therefore:
|lll s 1+ 20 ||
yo

---

Replacing this in Equation (S.2c)
E(F c(f-f") f
2 1| I1
llf
[(1
2
2 Il
11
N1331111
1f
270
2 + >ll 1|
|lf lu
+ +2 l1f
[1 ll
22 (l1f" +
A
And the result follows.
Bounds as a function of 3. By the definition of in the theorem assumption:
wy f² -
Hence:
8fF f*) s 20 E(F f²) )++++ + A(IIf 1331) 0 E(f fr) + A
where (a) follows from Proposition 5 with ( 1. Hence, using R = || || we obtain:
Ef - f*) < 20 + 2AR
B.2
Proof of Theorem
For adversarial kernel regression are minimizing the cost function:
L(F) (1y- f(x.)) 811f11x))
25
Σ [v f(x:))² + -1 1I Σ lys f(x;)) + 1f
Similarly to the proof of Theorem 2 using that y: f((x,) + aw, we obtain for an estimated function f that:
20 n L -
26 n
wi (.(((x))-
|| N Σ
1s (w:))
n
similarly,
L(f") 0² f*
1
Σ
|ws|
+ 1 122
11
By definition L < L(f"). Hence, simple algebraic manipulation shows that:
E - 1r) < 20
20 -
Wi ( (x:: - (xx()) +
||
Σ (lowsl (((" + +ow - -ow--- -x(x))
1=1
1 Σ |ooil + (11-1 -13312)))
+ -00 || - 1xx)
Now using the relation between norms ||æ||| < dim xx) 2|/1/2 we have that:
(low;) - 1f (mx) ow f(x)))
1
>E (f))) F(xx) V f*)
n
n
1
wil
<
x = 1,
nn i=1
iv

---

and it follows that:
E(f-8) w. (()))))))
20
V EΦ 21000(1 +0
[1
- 11311%))
(S.3)
Bounds as a function of y. Now, by the definition of y in the theorem assumption:
n ar (f.)) (x,)) s ~ f'1
n
Hence:
E(f-f') 5 - 1
1x +8 (11F 1+11%)
Now usign Proposition with ( and rearranging, we can obtain bound on &:
E(J - f*) z 40 3 11x 46 46 l2x + 48o 11 (1 28 (1 11 113111))
s 4 - f 1 + 400 11 |1 1z) + 28 (11 11 + 117111)
I f0 -f 1 + 480 15 Fll + 25² (11f* [1F111))
s 40 + 6) -7 + 28² (ILS*) + 117)
Now, result that prove later in Proposition 6, Eq. (S.5), particularly, we have that Il s (1 + ff [ 1| In this case,
E - 5 s 800(1 + + + (1+
Using that || = R we obtain
Ef fff- 48R(20 + 88)(1 + 2
Bounds as a function of 3. Alternatively, by the definition of 3 in the theorem assumption:
n
1i - f( -f))) ( f))
n
Hence, from (S.3) we obtain
8 - l*) < 20 203 EΦ fr) + 26 E( 1r)
- [1]lx)) + + -
s 2 Eiî - fr) + 28 11 E(J f*) + 26 ff + ff
<40B EΦ f*) + 26 I| E f*) + 25 1 1| + 5² 1
Where in the last equation used Proposition 6, Eq. (S.6): 8 81 1| S f1|f* ||
Ba. Now,
applying Proposition 5 with ( = 2 for each of the first two terms:
Eff - f*) S 80
cΦ fr) 48
E(F fr) + 250 8
And therefore:
Ef - f") < 2602 + 400R + 1082
(S.4)
Next, we prove the relation between the norms
|| # and ||f" | that were used the proof above.

---

Proposition 6. If the conditions of Theorem are satisfied. On the one hand:
8| fl (6 >) 1
(S.5)
on the other hand:
8 ollll I 811 11 +0
(S.6)
Proof. For the adversarial kernel regression loss:
L(f) = Σ
(lys -
im1
1
28
Σ (wi ((.)((=))))++++
||
Σ Mys -
+
the estimator f minimizes L(f), and satisfies the subderivative optimality condition AL( 0.
We have
H 811
n (xxx))+ +8
1 72
0=
+ w,
where &, E Tk ((:))) vil and to E ollll H Taking the dot product with f - and manipu- lating we obtain:
Efp f³) =
wi (fx)) - fxx)), + + 1 (f - f(x
+
Σ 1ui ( ((x))) + 811
(w, f" F).
Next, we bound each of the terms highlighted above by one. First:
(w, f) @b f*) fll 1f
[f
Where (a) uses that w J 17 which follows by the definition of subderivative. And (b) follows Cauchy-Schwarz inequality (w, f*) < [ < [| Moreover,
n1 Σ ys O, (.+())))))))
1 Σ (x:) ((x)) Σ lusl S SVE0-5 to n
Similarly, we have that:
1 -E(())) S Iif(a) - 7(xi) VE f
n
Now, we have two options on how to bound the first term in red:
Bounds as a function of y. By the definition of y in the theorem assumption:
w. - (*:)) soilss - Fllx
Hence,
8f- < - 10 (VeG- 8r) to + +8113lxx (1f* - (l(l
vi

---

rearranging:
1 a(rilf" fll + o11. 11 - fl + ff | E - f + f1 11 - 611f(1H)
< -Jll
1ills---lip + 6|1 - (1 + 55( 1*)
1 5 | 11 + flllll f* 62 11
2
2
<a(y)lf- -Fllx 811.f* fl)ll) SE(F f*)
+ 8 1
(l + C(K= - 1)11f11xx (15 S(x 1)113112))
2
where x² =1+ -/5/ Now, let Ç we have a: v2 and
0 S <(>lf
- -Fllx + 8f1ff 1|x - -811f l1+)
6²
[1 2l + 2(v2 1)I (1f 2(v2+ 2(v2++))|
+ 4
If I| 2 (1 + f)1 the left hand side above is negative and we have contradiction. There- fore, the result holds.
Bounds as a function of 3. Alternatively, by the definition of B::
- ((x)) So
completely equivalent derivation should yield that:
Ef - fz) 5 E 5*) +
51(3ll)) +
2 55(F f*)
+ 2 (1f + -(x- 1)1lfl1x) (1 + 1)11F11x))
1(1-111311)))
If we set ( 1 obtain x v3 and therefore:
- 8 (3) E0F / - fr) + 0011ff - =11331++)
2
82 2
1 + (V3 - 1)1l31lx) (11 - (V3 +11131111
Applying Proposition 5 to the first term
0 S 32
(6] 11 flll)) 82 (1f*llx (V3 1)1 (1f (V3 1)11
If 611 H 2 8|l + 0. the left-hand side above is negative and have contradiction. Therefore,
8| 81 1l I 811 ll + a f11ffl1 +
Where use in (a) that B < 1, since:
1
1 Σ g(x;)2 n)/E(g) n
w (x.) < ||m||
n
B.3 Proof of Proposition
The following theorem useful for obtaining probabilistic bounds is proved in (Wainwright, 2019. Theorem 2.26).
vii

---

Theorem 3 (Lipschitz functions of Gaussian Variables (Wainwright, 2019)), Let X.) be vector i.i.d. standard Gaussian variables, and let h IR + be I--Lipschitz with re- spect to the Euclidean norm. Then the variable h( X) [b (X) is sub-Gaussian with parameter at most and hence
( - (x)]I 2 8 2e z
for all t 2 O.
Now, lets start with the first statement. Lets write:
r(w) = sup
(x
(S.7)
11
notice that:
Vdmax
(g(x)))
wi (g. (xx))) S =1191111 Σ u, S
1 | |20 2
7
n
Where we used that:
Σ (; = Σ wr Σ [w
Σ Σ
w,wy(((x;)) (00)()()) = =w '' S A Amax/1e018
i=1 ]
hence (w)) is Lipschitz with constant Vmmae
virk
Then by Theorem 3:
Ply > 27] 2
The secons statement we follows from the follows directly from the following result
Proposition 7. If w NN, In) and have:
0. Then, for every g E H where VE(g) 2 3 +
1
Σ
n
with probability 1- ( (((+e))
2
The proof is given in (Wainwright, 2019, Lemma 13.12).
C
Gaussian and local Gaussian complexities across different RKHS
C.1 Computing the Gaussian complexity 7.
Let
(w
sup wi g(a;)) 11 1=1
where H. is a reproducing kernel Hilbert space (RKHS) with kernel k(.,.) and corresponding Gram matrix K E RaxE defined by Kij k( mz)) By the reproducing property, g(x.) (g, k(,, HH so that
((x;)
9,
k(;;
1=1
Applying the Cauchy-Schward Schwarz inequality, the supremum over ||g|| | S gives
1
sup llg
g(x.)
Σ
wi ki,, x.i)
$1
==1
1=1
Thus,
n
1
7 n
(10,Ta)
Σ
wi k(, xz)
Ew-NNio..) Vw w.
n
H
viii

---

Using Jensen's s inequality and E/w" K w) = K. we obtain the bound
(t((K)
7 u T K w)
72
Translational invariant kernel.
For translational invariant kernels vtr(K) = and 9 Vn.
Linear kernel.
The linear kernel is defined here as:
kax, y)
y
We have:
X
7
(max (0:112)
(S.8)
72
Th
vn
C.2 Computing the local Gaussian complexity B2.
Linear kernels. For linear kernels, we have 3 ((V )) Wainwright, 2019.
the details are given in Example 13.8,
Matérn kernels. Here, follow argument similar Wainwright, 2019, Example 13.20. We consider the following result, proved in Wainwright, 2019, Lemma 13.22, which provides a bound for slightly different definition of 3. For simplicity, adopt it informally tte main goal is to convey the dimensional dependence, and the necessary modifications to adapt it to our setting should follow naturally.
Proposition Consider an RKHS with kernel function For a given set of design points C,, And let μl 2 2 Pn 2 be he eigenvalues of where K is the kernel matrix with entries Ki = k( 2,). Then for all B2 we have
2
E
sup lle (
(wg(((;))
S
Σ
min (32 pi)
where w/ ~ (0, 1) are i.i.d Gaussian variables.
Let be the smalest positive integer such that for which
ck 22/2 < 32
(S.9)
we have that μ4 S ci -u/p for some constant e, see Bach, 2025.
2
n
2
m
2
min (32, S
min (32cci-2//2) S
321 +
Σ i-20/p
n
k=
We upper bound the sum by an integral,
22/2 < 10 (2//p S ck -22/2//tt S Bk
1=k+1
k+1
and hence:
min (32, s 2
=B
therefore, the critical inequality is satisfied for B 2 2 k now since e' 2/3-p/2v S V by (S.9), the
inequality is satisfied for any 3 2 -1n=t/((+//v) Therefore 3 On -122/112//)))
ix

---

D Adversarial multiple kernel learning
The next proposition is the equivalent proposition 2
Proposition Let f - Ei=1 S. where f; E Hi, then
(y - (()) d))) = (ly Et((0) Ilffslmn,)
max dE(",
A similar algorithm to that proposed in Algorithm also apply for the of adversarial multiple kernel learning. The algorithm also follows from the 1--trick that yields the following variational reformulation of the loss:
y - Σj (0)
111,, rp
(vv - E,,(() +8
|s |1,l1,,)²
min 7n
170
s.t. Σ n = 1, > 0.
We apply the above reformulation each sample, obtaining and solve it as block-wise coordinate problem, alternating between 1) solving over 7) to compute the weights wy 1/T and 2) solving the reweighted ridge regression problems that arises.
Σ,
E
Numerical experiments
E.1
Datasets
We used 5 different data sets our experiments.
(Efron et al., 2004) The dataset has p-10 baseline variables (age, sex, body mass index, average blood pressure, and six blood serum measurements), which were obtained for n=442 diabetes patients. The model output is a quantitative measure of the disease progression. Abalone: (OpenML ID=30, UCI ID=1) Predicting the age of abalone from p-8 physical mea- surements. The age of abalone is determined by cutting the shell through the cone, staining it, and counting the number of rings through a microscope a boring and time-consuming task. Other measurements, which are easier obtain, are used to predict the age of the abalone. considers n=4417 examples.
Diabetes:
Wine quality: (Cortez al., 2009, UCI ID=186) A large dataset (n=4898) with white and red vinho verde" samples (from Portugal) used to predict human wine taste preferences. It considers p=11 features that describe physicochemical properties of the wine.
Polution: (McDonald & Schwing, 1973, OpenML. ID=542) Estimates relating air pollution to mortality. It considers p=15 features including precipitation, temperature the year, percent- age of the population over 65, besides socio-ccomomic variables, and concentrations of different compounds in the air. In total it considers It tries predict age-adjusted mortality rate in n= different locations.
US crime: (Redmond & Baveja, 2002, OpenML ID=42730, UCI ID=182) This dataset combines p=127 features that come from socio-economic data from the US Census, law enforcement data from the LEMAS survey, and crime data from the FBI for n= 1999 comunities. The task is to predict violent crimes per capita in the US as target.
X

---

E.2
Additional results
Radge
Ridge
Ridgo
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
(a) Matérn 1/2
(b) Matérn 3/2
(c) Gaussian
Data Adl Kera Rädge CV Thue
Data July Kem Ridge CV True
Dota Adl Kem Ridge CV
Trme
0.0
0.5
1.0
0.0
0.5
1.0
0.0
0.5
1.0
(d) Matérn 1/2
(c) Matérn 3/2
(f) Gaussian
Figure S.I: We compare adversarial kernel training with cross-validated kernel ridge regression (Ridge CV), For (a)-(c), show how it fits smooth target function. For (d)-(f), we show how it a non-smooth target function.
Adv Kem
Adv Kem Ridge CV
Text MSB
10
Ridge
Test MSE
10
3 1X1
Rilge
10-7
10-4
Ady Kem Ridge CV Ridge
2 10-1
10-1
10
10
10
10a
10
10
10
10
10
10
10-2
10a
Noise standard deviation
Noise standard deviation
Noise standard deviation
(a) Linear
(b) Sine
(c) Square
Figure S.2: We compare Adversarial Kernel Training (Adv Ker) against two baseline methods:
Kernel Ridge Regression with cross-validation (Ridge CV) and Kernel Ridge Regression without cross-validation (Ridge). Our evaluation includes the sine and square wave examples shown in Fig- S.I, using Gaussian kernel, well synthetic linear dataset using linear kernel. To assess robustness to noise, we vary the standard deviation of Gaussian noise added to data from 10-7 to 10
Table S.1: Empirically observed rate of convergence r, such that, Test MSE n². Computed as the slope of the dashed line the linear approximation in Figure (rright) and Figure 3.
Non-smooth
Smooth
Ady Kern Ridge CV
Adv Kem
Ridge CV
Matérn 1/2
-0,67
-0.73
-0.92
-1.02
Matérn 3/2
-0.45
-0.73
-1.06
-1.07
Matérn 5/2
-0.37
-0.63
-1.08
-1.08
Gaussian
-0.13
-0.24
-1.04
-1.14
xi

---

100
100
Ridge CV
Ridge CV
Test MSE
Adv Kern
Test MSE
Ridge
10-2
10-2
10 4
10 2
100
10Th
10
100
A
Figure S.3: We compare Adversarial Kernel Training (Adv Kern) and Kernel Ridge Regression without cross-validation (Ridge) against Kernel Ridge Regression with cross-validation (Ridge CV). We train and evaluate on the sine wave example shown in Figure S.1, using a Gaussian kernel, and plot the test MSE as function of 5 and À respectively.
xii

---

test atlack E2
test-time atlack to
training method
attack
[1 0.013
{| S 0.1)
[| S 0.013
{1) S 0.1)
Ady Kern (6 oc n 1/2)
0,70 (0.50 (0.58-0.77)
0.69 (0.59-0.76)
0.66 (0.56-0.75)
0.69 (0.57-0.76)
0.58 (0:44-0.66)
Ridge Kemee (A cross validated)
0.68 (0.57 0.73)
(0.56 0.73)
(0.47 0.68)
(0.54 0.71)
0.49 (0.33 0.56)
Adv Kern d и g (0.01)
0.72 (0.59-0.84)
0.72 (0.60-0.84)
0.67 (0.51-0.78)
0.71 (0.55-0.85)
0.51 (0.29-0.63)
Adv Kern
{ [| 3 0.1}
0.67 (0.57-0.72)
0.67 (0.58-0.72)
0.65 (0.54-0.70)
0.67 (0.57-0.72)
0,58 (0.49-0.64)
Ady Iuput { A
S 0.13
0.67 (0.54-0.73)
0.66 (0.55-0.72)
0.61 (0.46-0.69)
0.65 (0.51-0.72)
0.47 (0.26-0.53)
Adv laput
{ || < S 0.13
0.68 (0.57 0.75)
0.67 (0.56 0.74)
0.63 (0.51 0.69)
0.66 (0.53 0.74)
0.49 (0.30 0.56)
(a) Pollution
test-lime atlack &g
test-time atlnck Eo
Iraining method
attack
0.013
[|] S 0.1)
(|A S 0.01)
[|| 0.1)
Adv Kern ix n 1/2)
0.38 (0.29--0.44 0.44)
0.37 (0.26-0.43)
0.31 (0.21-0.38)
0.36 (0.27-0.33
0.20 (0.09-0.22)
Ridge Kemel (A cross-validate)
0.38 (0.27-0.44)
0.37 (0.26-0.43)
0.29 (0.18-0.38)
0.35 (0.25-0043)
0.15 (0.02-0.24)
Ady [|d]
и 0.01)
0.38 (0.27-0.44)
(0.28-0.44)
0.31 (0.19-0.37)
0.37 (0.26-0.43)
0.19 (0.09-0.27)
Ady Kern
d
5 0.1}
0.32 (0.22 0.38)
0.32 (0.23 0.38)
0.27 (0.18 0,34)
0.31 (0.22 0.37)
0.17 (0.06 0.23)
Input
Am
S )
0.37 (0.27 00455
(.425)))44)
0.29 (0.18-0.36)
(0:24 0.48)
0.15 (0.02-0.24)
Adv Input
Am
S 0.1}
0.37 (0.26 0.45)
0.37 (0.25 0.44)
0.29 (0.19 0.38)
0.35 (0.24 0.42)
0.16 (0.04 0.22)
(b) Diabetes
test-time attack Exe
training method
atlack
(IlAm|ls
S 0.01]
{|] S 0.1)
[|| S 0.01)
[||Am| S 0.1)
x 1/2)
0.65 (0.63 0.67)
0.67)
0.63 (0.61 0.65)
0.65)
0.44 (0.41
Ridge Kemel (A cross-validate))
0.65 (0.63-0.67)
0.65 (0.62-0.67)
0.61 (0.59-0.63)
0.62 (0.59-0.64)
0.21 (0. 16-064))))
Adv Kern
||d и I 0.01)
0.65 (0.63 0.67)
0.65 (0.63 0.67)
0.63 (0.61 0.65)
0.63 (0.61 0.66)
0.43 (0.40 0.46)
Adv Kern
d x I 0.13
0.45 (0.44-0.46)
0.45 (0.43-0.46)
0.44 (0.42-0.45)
0.44 (0.43-0.45)
0.36 (0.35 0.37)
Ady Toput
Am S 0.1)
0.65 (0.63 0.67)
0.65 (0.62. 0.67)
0.61 (0.59 0.63)
0.62 (0.60 0.64)
0.21 (0.17 0.24)
Adv Input
{ || S 0.13
0.65 (0.63-0.67)
0.65 (0.63-0.67)
0.61 (0.59-0.63)
0.62 (0.59-0.64)
0.21 (0. 17-0022)
(c) US Crime
test time attack
test time attack f.v.
training method
no attack
(I|Aæ||2 S 0.013
{|| S 0.1)
(||a/|s sc & 0.013
[1 S 0.13
Adv Kern 1/2)
0.39 (0.37-0.40)
0.38 (0.36-0.39)
0.28 (0.26-0.29)
0.36 (0.35-0.37)
0.06 (0.04-0.07)
Ridge Kemnll (A cross validated))
0,38 (0.36-0.39)
0.36 (0.34-0.37)
0.20 (0.18-0.21)
0.33 (0.32-0.35)
-0.17 (-0.20
Ady Kern [|d]] x < 0.01)
0.40 (0.39 0.41)
0.38 (0.37 0.40)
0.25 (0.23 0.26)
0.36 (0.34 0.37)
0.07 (.0.09 0.06)
[]d] n 5 0.1)
0.16 (16600016-0..
15)0.16)
(0.14-0.5))
(0.6
0.11 (0. 10-0.1)
Adv Input {
| S 0.13
0.38 (0.36-0.33 39)
0.36 (0.35-0.38)
0.20 (0.19-0.22)
0.33 (0.32-0.33)
Toput |m x S 1.1)
0.38 (0.
(0.35-0.37)
(0.19-0.211)
(0.32-0.35)
-0.15 (40.18 0.13)
(d) Wine
test-time attack Eg
tost-time attack &oo
training method
(||Aml|a S 0.01)
(|| 0.1)
(||
S 0.013
(1] $ 0.1)
Adv Kern (6 oc 1/2)
0.57 (0.56-0.55) 58)
0.55 (0:54-0.57)
0.39 (0.37-0044)
0.54 (0.52-0.55)
0.13 (0.110010))
Ridge Kemel (A cross- cross-validated
0.57(0.36-0.59)
0.55 (0.53-0.56)
0.26 (0.24-0.28)
0.52 (0.51-0.54)
-0.16 -.16
Adv Kern d и 5 0.01)
0.56 (0.55-0 58)
0.55 (0.53-0.56)
0.40 (0.39-0.42)
0.53 (0.52-0.55)
0.18 (0) 16-0.00)
Adv Kern
x S 0.1)
0.38 (0.37 0.399
0.38 (0.37-0.39)
0.35 (0.34 0,36)
0.37 (0.36 0.38)
0.30 (0.29
Ady Input { || 2 S 0.13
0.57 (0.56-0 59)
0.55 (0.53-0.56)
0.27 (0.25-0.22)
0.52 (0.51-0.54)
0.14(4.177-011)
Input || <z S 0.1}
0.57 (0.55-0.58)
(0.53-0.56)
0.27 (0.25-0.29)
0.52 (0.51-0.533
-0.11 (-0.1400.88
(e) Abalone
Table S.2: R² scores (higher is better) across datasets for varying adversarial training perturbation norms p and adversarial radius 5. We show the interquartile range obtained through bootstrap.
xiii

---

NeurlPs 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: Yes, the claims reflect the contributions and scope of the paper. The main contribu- tions-problen problem equivalences, convexity, generalization bounds, and a practical algorithm- are clearly stated and developed, with experiments supporting the claims.
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 contribu- tions made in 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.
is fine to include aspirational goals motivation long as is clear that these goals are not attained by the paper.
Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: The limitations are discussed throughout the paper, especially in Section 9, where also point further directions for improvement.
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 viola- tions of these assumptions (c.g.. independence assumptions, noiseless settings, model well- specification, asym 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 a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is 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 of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address prob- lems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by review- ers as grounds for rejection, a 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 transparency play an important 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 proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof? Answer: [Yes]
Justification: All theoretical results have clearly stated assumptions and are accompanied by proofs in the lext or suplementary material.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross-re roosserefeeeccdd..
All assumptions should be clearly stated referenced in the statement of any thcorems.
xiv

---

The proofs can either appear in the main paper or the supplemental material, but if they appear the supplemental material, the authors are encouraged to provide a short proof sketch to 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 be properly referenced.
Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main exper- imental results the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The main contributions of the paper is a new formulation for adversarial training and its analysis. The optimization algorithm for described clearly and with pseudo-cod provided. The numerical experiments provide details and the code is also provided.
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a 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 provided not.
dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
the contribution
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, if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to hosted model (e.g., in the case of a large language model), releasing of model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be a way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, may be that access to the model limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes]
Justification:
Yes, we provide access to the code to reproduce the numerical experiments training kernel).
(gt thub.
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurIPS code and data submission guidelines (tttss//hips.cc/pubhic/ggddd CodeSubmissionPolle
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to repro- duce the results. See the NeurIPS code and data submission guidelines https://nips.cc/pubii SaaddessCodeSummisiioooeooe for more details.
XV

---

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. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyperparame- ters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The paper specifies the most relevant training and test details in Section Ad- ditional implementation details explicitly mentioned are provided in Appendix and can be verified in the accompanying code.
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 level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material. 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: We use bootstrap sampling compute the error bars, which represent the in- terquartile range.
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, confidence
intervals, or statistical significance tests, at 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 run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to 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 the standard enror of the mean.
It is OK to report I-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error 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 out of range (e.g. negative error rates). If error bars are reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the exper- iments?
Answer: [No]
Justification: This not a very computationally intensive paper. All the experiments can run on personal computer, hence we don't 't put lot of emphasis in this aspect.
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, or cloud
provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experi- mental runs as well as estimate the total compute.
xvi

---

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 't make
into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https//heurips.ccppbbiieeee cc/public/Etticccciiiiiiness Answer: [Yes]
Justification: We comply with NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
a The authors should make sure to preserve anonymity (e.g., if there special consideration
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: This is methods paper there is no immediate societal impact that deserves discus- sion.
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 or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploy- ment 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 par- ticular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, is not needed to point out that a 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 as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
legitimate to point out that
If there negative societal impacts, the authors could also discuss possible mitigation strate- gies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Justification:
The paper poses no such risks. We propose new methods that are mostly bench-
marked in simple examples.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse 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 re- quire this, but we encourage authors to take this into account and make a best faith effort.
12. Licenses for existing assets
xvii

---

Question: 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?
Answer: [Yes]
Justification: We use open datasets in our experiments. All datasets include corresponding cita- tions and descriptions in the Appendix.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if 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 the package should be provided. For popular datasets, paperswithcode.c cottdaasst has curated licenses for some datasets. Their licensing guide can help determine the license a dataset. For existing datasets that re-par packaged, both the original license and the license of the de- rived asset (if it has changed) should be provided.
If this information is not available online, the authors encouraged reach out to the asset'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: We do not release new assets, but we release the code for reproducing the results in the paper and for using the proposed method (see the answer question "Open access data and code").
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmodel as part of their submis-
sions 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an 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, applicable, as well as detils about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
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 contribution of the paper involves human subjects, then much detail possible should be included in the main paper.
According to the NeurIPS Code of Ethics, 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 equivalent for research with human subjects Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human
subjects.
Xviii

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. 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 lo- cations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if appli- cable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if is an important, original, or non- standard component of the core methods in this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM is used only for small improvements in writing and formalting purposes. does not impact the core methodology of the research.
Guidelines:
The answer NA means that the core method development in this research does not involve
LLMs any important, original, or non-standard components. Please refer to our L.M policy http:://eaiii..ccommneeeeees///s for what should or should not be described.
xix


Reviews:
[{"review_id": "zGras3QwZE", "reviewer": "Reviewer_pZHY", "summary": "This paper establishes the theoretical framework for kernel learning in the context of adversarial training and RKHS.\nThe proposed framework handles feature-space perturbation.\nThe efficient algorithm for solving the kernel adversarial training has been proposed, and generalization properties for the proposed framework are also provided.", "questions": "1. If \\delta follows different orders of the sample size, then what is the order of the generalization bound?\n2. How do the authors compare their results for kernel ridge regression in Theorem 2 with the rates developed in traditional statistics?", "limitations": "Yes", "rating": 5, "confidence": 3, "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 solid.\n3. This paper provides a new theoretical perspective of adversarial training from function spaces and non-parametric models.\n4. The authors have considered different aspects of the proposed kernel adversarial training (formulation, numerical optimization, generalization bounds, multiple kernel learning, etc.)\n\n\nWeakness\n1. It will be better if the authors can explain how the generalization bound of the kernel adversarial training relies on the sample size n under different settings of the upper bound of adversarial error and compare this with kernel ridge regression and original adversarial training.\n2. Some of the theorems/propositions in this paper are not self-contained. For example, what are R,\\lambda, \\sigma in Theorem 1 and Theorem 2? I would appreciate it if the authors could adjust them.\n3. UpdateWeights in Algorithm 1 is confusing. Could the author write the details of this step?", "was_revised": true, "final_justification": "I believe this paper has made solid contributions in establishing a framework for kernel learning in the context of adversarial training and RKHS. Also, the authors have given the dependence of generalization bounds on the sample size and provided some comparisons with kernel ridge regression. I am satisfied by the authors' response.", "rebuttal": "We greatly appreciate the reviewer’s time and attention in evaluating our research. We are happy to receive an overall positive feedback and also comments that can help us to improve clarity. We respond to the Questions **(Q)** and address the Weaknesses **(W)** below:\n\n* **(Q1 & W1) Dependence of generalization bounds on the sample size.** Thank you for the comment. We agree that the presentation of our analysis in Section 5 is somewhat scattered. To improve clarity, we will add a brief summary of the key results at the beginning of the section. We obtain two rates depending on how you set $\\\\delta$:  \n  * If $\\\\delta\\\\propto \\\\gamma$  we obtain the rate $O(R\\\\sigma/\\\\sqrt{n})$ for linear, Gaussian and Mattern kernel;  \n  * If $\\\\delta\\<\\\\frac{\\\\sigma}{R} \\\\beta^2$ we obtain $O(\\\\sigma^2 p/n)$ for linear kernel, $O(\\\\sigma^2(log n)^c/\\\\sqrt{n})$  for the Gaussian kernel, and $O(\\\\sigma^2/n^{1/(2 \\+ p/\\\\nu)})$ for the Matern-$\\\\nu$ kernel.   \n* **(Q2) Comparison with kernel ridge regression.** We can set the regularization parameter to obtain the same rates for ridge regression. In the first case, however, this requires choosing $\\\\lambda \\\\propto \\\\sigma / (R \\\\gamma)$, which depends not only on the problem dimensions but also on the signal-to-noise ratio (which is typically unknown). We highlight this as a strength of Kernel Adversarial Training, which simplifies hyperparameter selection.  \n* **(W2)** **Clarifying notation.** Thank you for pointing this out. The variable were defined in the first paragraph of Section 5, but we agree that the theorems should be fully self-contained.  Just for the reference $R \\= \\\\|f^\\*\\\\|\\_{\\\\mathcal{H}}$ denotes the radius of the hypothesis space in the RKHS norm, $ \\\\lambda$ is the regularization parameter in ridge regression, and $\\\\sigma$ is the noise magnitude.  In the revised version, we will clearly define all quantities in the theorem statements.   \n* **(W3) Clarifying step in the algorithm.**   Thank you for pointing this out\\! We agree. The weight calculation is specified on the previous page (end of *4.1 Proposed Algorithm*) as  \n  * $w\\_i \\= \\\\frac{1}{\\\\eta^{0}\\_i}$, and  \n  * $\\\\lambda \\= \\\\frac{1}{n}\\\\sum\\_{i} \\\\frac{\\\\delta^2}{\\\\eta^{1}\\_i}$. \n\n  We will add this to Algorithm 1 to make it easier to read."}, {"review_id": "MdaIKutBny", "reviewer": "Reviewer_zxfo", "summary": "This paper proposes an adversarial training framework used to kernel-based linear regression models, aiming to enhance model robustness. Traditional adversarial training methods typically formulate robustness as a min-max optimization problem in the input space and solve it using computationally intensive projected gradient descent (PGD). In contrast, this study introduces perturbations directly in the reproducing kernel Hilbert space (RKHS) feature space rather than the input space, enabling a convex reformulation of the problem that admits a closed-form solution. An optimization algorithm based on iterative kernel ridge regression is proposed. The paper establishes the convexity of the proposed formulation and analyzes its theoretical properties, deriving generalization bounds that guarantee its performance. Furthermore, the methodology is extended to multiple kernel learning, thereby increasing model expressiveness. Experimental evaluations on synthetic and real-world datasets demonstrate the superior performance of the proposed method compared to traditional kernel ridge regression approaches.", "questions": "● Can the proposed adversarial training framework be effectively scaled to handle larger datasets?\n● Is it possible to extend or adapt this method for classification tasks, and what modifications would be necessary?\n● How does the computational complexity of the proposed method compare with existing large-scale kernel methods?\n● Could alternative kernel approximation methods or matrix decomposition techniques address the computational complexity issue effectively?\n● Are there practical scenarios or applications where the feature-space perturbation provides significantly better robustness compared to input-space perturbations?\n● Are you perhaps confusing excess risk(used in line 150) with the L2 error? Excess risk refers to the difference between the risk of the empirical risk minimizer (ERM) and the risk of the Bayes estimator, and it is conceptually distinct from the L2 error.\n● In Table 3, what does the parameter p represent? In Appendix Table S.2, p appears to refer to the p-norm, whereas in Appendix E.1 and Table 2, p is used to denote the number of features in the data. This inconsistent notation is quite confusing. Moreover, the role of the p-norm is not clearly explained in the paper.\n● Traditional kernel regression already achieves robustness through the use of a ridge penalty, so it is unclear what additional benefits your method provides. Are there specific scenarios where standard kernel ridge regression is not robust, but your approach demonstrates robustness?", "limitations": "● The proposed framework does not address the high computational complexity of kernel regression, which involves O(n³) operations for kernel matrix inversion.\n● The methodology and experiments are restricted to regression problems, without considering or testing its generalization to classification tasks.\n● The experimental validations provided are limited to relatively small datasets, raising questions about the scalability and numerical efficiency of the approach.", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n● Introduces perturbations in the RKHS feature space rather than the input space during adversarial training, presenting a closed-form solution for the inner-maximization problem, thus eliminating the need for PGD.\n● Provides theoretical insights by deriving upper bounds on the empirical L2 prediction error associated with the solutions obtained by the proposed algorithm, offering theoretical guarantees for performance.\n\n\nWeaknesses:\n\n● Kernel regression inherently involves computing the inverse of the kernel matrix, resulting in a high computational complexity of O(n³). Although acknowledged by the authors, this limitation is not addressed within the scope of the paper.\n● The proposed framework is limited to regression problems, lacking discussion or experimental validation for classification scenarios.\n● Due to methodological constraints, the diversity of experiments is limited. The datasets employed in experiments have relatively small numbers of features and data points, raising concerns about the scalability and numerical efficiency of the proposed method.\n● Additionally, the paper does not include a proof for Proposition 1, which is central to the theoretical foundation of the proposed method.", "was_revised": true, "final_justification": "The authors propose a method that applies adversarial learning in the feature space as a way to fit robust models. However, it remains unclear how much advantage this approach provides over standard kernel ridge regression. To properly assess the merit of the proposed method, experiments on larger-scale tasks. Such as high-dimensional image classification or applications involving large language models (LLMs) would be necessary, in addition to the small to medium scale regression problems currently presented in the paper.", "rebuttal": "Thank you very much for reading our paper and providing feedback. These are very useful comments. We answer to the  questions and concerns below:\n\n* **Scalability and numerical efficiency.** In this paper, we focus on medium-scale problems, which allows us to include generalization analysis and multiple kernel learning within the scope of the study. Nonetheless, the method is well-suited for scaling to larger settings. The main computational bottleneck—solving a reweighted ridge regression—can be solved approximately, for instance by using a small number of iterations of a first-order method, thus avoiding the $\\\\mathcal{O}(n^3)$ complexity of exact solvers. Ribeiro et al. \\[1\\] show that a conjugate gradient (CG)–based approach can replace costly matrix decompositions such as Cholesky or SVD. This significantly reduces the per-iteration cost and makes the adversarial training framework computationally feasible for large-scale applications. \n\n * **Usage of large-scale kernel methods and approximations.** We also highlight that our method solves a sequence of reweighted kernel ridge regression problems, hence it can naturally benefit from the same computational accelerations developed for large-scale kernel methods. Hence that any scalable solver for kernel ridge regression—such as those based on random feature approximations, Nyström methods, or iterative solvers—can be directly integrated as a subroutine in our algorithm. We will clarify this point in the revised manuscript. \n    \n* **Classification.** Thank you for the question. This is a valid and important point, and indeed one we discussed internally. We chose to focus on regression in this paper to keep the presentation clear and focused. Regression offers a rich and well-understood setting that allows us to highlight the core ideas and trade-offs of adversarial kernel learning. That said, many of our results can be extended to classification. The main idea—adversarial training in feature space—is applicable to both regression and classification tasks. Proposition 1, which connects input- and feature-space perturbations, holds for classification. Proposition 2 also has a natural analogue under similar regularity conditions. The optimization algorithm we propose is tailored to the square loss, but related approaches for classification exist. Indeed, Ribeiro et al. \\[1\\] provide an algorithm in the linear setting that could be adapted to the nonparametric case considered here. Sections 5 and 6, which deal with generalization and empirical performance, could in principle be adapted for classification, but doing so would require additional theoretical and experimental work. We will revise the text to clarify these points and highlight potential directions for extension.  \n    \n\n    \n* **Scenarios where the feature-space perturbation provides better robustness than input-space perturbations.** Thank you for the question. Interestingly, in several scenarios, we observe that adversarial training in feature space leads to improved robustness compared to direct input-space perturbations. This is illustrated in Table 3, and we will expand the paper to include additional examples for a more direct comparison.  \nBelow, we present a representative example using the pollution dataset.  We report results under a standard threat model with $\\\\ell\\_\\\\infty$-bounded input perturbations of radius $\\\\delta\\_{\\\\text{inp}} \\= 0.1$ . We include the results for the two values of $\\\\delta$, illustrating the trade-off between clean and robust accuracy: increasing the feature-space radius $\\\\delta$ enhances robustness, but comes at the cost of slightly reduced clean performance. Notably, in both cases, our method outperforms input-space adversarial training—even when the latter uses the same threat model as the one applied during evaluation. We believe this is due to the fact that our method enables exact optimization of the worst-case feature-space loss, whereas input-space adversarial training typically relies on approximate solvers such as PGD.  We will add this comparison and discussion to the paper to highlight scenarios where our method achieves better robustness than traditional input-space adversarial training. *We show the $R^2$ score (higher is better).*\n| $R^2$ score  | Clean data  |  Adversarial attack  |\n | :---- | ----: | ----: | \n| **Adv Kern** (ours, $\\\\delta\\=0.01$) | **0.72** | 0.51 | \n| **Adv Kern** (ours, $\\\\delta\\=0.1$) | 0.67 | **0.58** | \n| **Adv Inp** (same threat model as evaluation) |  0.68 | 0.50 |\n\n\n\n* **Excess risk**. Thank you for bringing this up.  We agree that this could cause confusion; we will revise the text to better clarify why we refer to this quantity as the *excess risk*. We highlight, though, that our definition does follow from what you said. Particularly,  $$\\\\frac{1}{n}\\\\sum\\_{i=1}^n (f(x\\_i) \\- f^\\*(x\\_i))^2  \\= \\\\text{Expected risk} \\- \\\\text{Bayes risk} $$  Where$$\\\\begin{aligned}  \\\\text{Bayes risk}& \\= \\\\mathbb{E}\\_{w}\\[\\\\frac{1}{n}\\\\sum\\_{i=1}^n (y \\- f^\\*(x))^2\\]  \\= \\\\mathbb{E}\\_{w}\\[\\\\frac{1}{n}\\\\sum\\_{i=1}^n (\\\\sigma w\\_i)^2 \\]  \\= \\\\sigma^2\\\\\\\\  \n  \\\\text{Expected risk}&=  \\\\mathbb{E}\\_{w}\\[\\\\frac{1}{n}\\\\sum\\_{i=1}^n (y \\- f(x))^2\\]  \\= \\\\mathbb{E}\\_{w}\\[\\\\frac{1}{n}\\\\sum\\_{i=1}^n (\\\\sigma w\\_i \\+ f(x\\_i) \\- f^\\*(x\\_i))^2 \\] \\= \\\\sigma^2 \\+ \\\\frac{1}{n}\\\\sum\\_{i=1}^n (f(x\\_i) \\- f^\\*(x\\_i))^2.  \n  \\\\end{aligned}$$ We will ensure this reasoning is made explicit and clearly presented in the revised manuscript.  \n* **Parameter $p$ and inconsistencies in the notation.** Thank you a lot for catching this up. Indeed, we use the parameter $p$ to refer to the $p$-norm in Table 2 and to the number of parameters in Table 2\\. We agree that this could cause confusion to the reader and we will fix it in the revision.  \n* **Improved robustness when compared to kernel ridge regression.**  While kernel ridge regression already offers some robustness via the ridge penalty, our method explicitly minimizes the worst-case loss over a feature-space perturbation set (Eq. 2), directly targeting adversarial robustness. This results in *better defense against adversarial disturbances in all the cases we evaluated*, with our method outperforming kernel ridge regression under input-space attacks (see Table 3 and Figure 3). This demonstrates the practical robustness benefits of our formulation beyond those offered by standard ridge penalties.  \n* **Proof of proposition 1\\.** Thank you for the comment.  Proof of proposition 1 is given in the Appendix (A.1). We will add a pointer to it in the main text.\n\n**References**\n\n- \\[1\\] \"Efficient Optimization Algorithms for Linear Adversarial Training\" A. H. Ribeiro, T. B. Schön, D. Zachariah, and F. Bach. AISTATS, 2025\\."}, {"review_id": "gAQ5f0JHXC", "reviewer": "Reviewer_vuz8", "summary": "This paper studies adversarial kernel regression, where we aim at choosing the best function in an RKHS that is robust to worst-case perturbations in the input. The authors provide a relaxation of this problem by considering worst-case perturbations over the feature space, which allows the inner maximization to be solved in closed-form and leading to a convex minimization problem that can be solved with block-coordinate descent type algorithms. The authors also prove generalization bounds and demonstrate that unlike ridge regression, the optimal value of perturbation strength does not depend on noise level.", "questions": "1. As the original adversarial training loss (with perturbations in the input space) is a maximization over convex functions, it is itself a convex minimization problem. How would solving the original problem compare to solving the relaxed version in the feature space?\n\n2. A relevant reference may be [1], where the authors study how to learn multi-index models in an adversarially robust manner with two-layer neural nets. The authors show that the first layer can be trained in a standard way, which leads to a data-adapted RKHS. In the second stage, they need to minimize the adversarial loss over this RKHS. The approach used in this paper can be used there to provide end-to-end guarantees for robustly learning multi-index models.\n\n3. What is the main technical difficulty in establishing random design generalization bounds? The Rademacher complexity for the adversarial loss has been studied extensively in prior works, so this seems within reach, and with this bound we can make a more confident comparison between adversarial learning and ridge regression.\n\n4. I couldn’t find the definition of the constant $R$ in the main text.\n\n5. How does it make sense to talk about $\\Vert d \\Vert_{\\mathcal{H}_j}$? Does this mean $d = \\sum_j d_j$, and the norm is $\\Vert d _j \\Vert _{\\mathcal{H}_j}$?\n\n---\n[1] A. Mousavi-Hosseini, A. Javanmard, M. A. Erdogdu. \"Robust Feature Learning for Multi-Index Models in High Dimensions.\" ICLR 2025.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "* Strengths:\nThe paper provides a novel and interesting trick to efficiently solve convex adversarial learning problems, and I believe there is some potential to use this insight in certain non-convex settings discussed below. The fact that the perturbation strength does not need to be adapted to the noise level makes this an appealing approach in settings where standard performance matters.\n\n* Weaknesses:\n    * In most use cases of adversarial training, one is interested in conditions of the type $\\Vert x \\Vert \\leq \\delta$ with a fixed $\\delta$ to ensure worst-case input perturbations can not degrade the model performance significantly. Since the relaxation provided in this paper may not be sharp, ensuring this constraint may require a very large perturbation budget in the feature space, which would eventually hurt standard performance.\n    * Some technical aspects of the paper can be improved. For example it is relatively standard to also study Rademacher-based generalization bounds in this setting, but the authors only consider a fixed-design excess risk which provides weaker guarantees and cannot rule out overfitting.\n    * While the authors measure the excess risk with respect to $f^\\*$, it might make more sense to compare the learned model's performance to the best model in the RKHS measured by population adversarial loss. $f^\\*$ may not be a good benchmark for adversarial robustness if it changes quickly with $x$.", "was_revised": true, "final_justification": "I didn't have any major concerns, and the other reviews are generally positive. I think the paper's approach towards relaxing the problem of robustness w.r.t. to input perturbations to robustness w.r.t. feature perturbations is interesting, which is why I recommend acceptance.", "rebuttal": "Thank you very much for reading our paper and providing feedback. These are useful comments. We answer the questions **(Q)** and weaknesses **(W)** below.\n\n* **(W1) On the size of  $\\\\delta$ to guarantee input robustness.** Thank you for the comment. Robustness to fixed input-space perturbations is a standard goal in adversarial training. Table 1 in our paper outlines conditions under which input-space perturbations are upper-bounded by constraints in feature space. For some kernels, achieving equivalent robustness may require a relatively large feature-space radius to satisfy these conditions. We will make sure to clearly highlight this limitation in the paper. That said, the radii required to guarantee equivalence may be somewhat conservative, and our numerical experiments (Table 3) show that the method still improves robustness even when using smaller, more practical values.\n* **(W3) On optimal $f^\\*$ for robustness.** In our work, we emphasize two distinct perspectives on adversarial training: generalization and robustness. While our analysis of the optimal function $f^\\*$ primarily focuses on generalization, we agree that robustness is also a crucial aspect. Importantly, the two are closely connected. In particular, the expected adversarial error can be approximated as (see, e.g., \\[1\\]): $$\\\\text{Expected Adversarial Error}(f, \\\\delta_{\\\\text{test}}) \\\\propto \\\\text{Expected Error}(f) \\+ \\\\delta\\_{\\\\text{test}}^2 \\\\|f\\\\|\\_{\\\\mathcal{H}}^2,$$ where $\\\\|f\\\\|\\_{\\\\mathcal{H}}^2$ denotes the RKHS norm of the predictor. This expression shows that the regularization effect studied in our analysis also contributes to adversarial robustness at test time, with the additional term capturing the model’s sensitivity to perturbations.  \n  Thank you again for the comment. We will revise the text to clarify that generalization is the primary focus of our analysis there, but also to better explain how it also provides insight into robustness.  \n* **(Q1) About the comparison with input-perturbations.** Thank you for the comment. We highlight that the original problem with the perturbation in the input space is not convex. Particularly, we are considering classes of nonlinear functions where $f(x+\\\\Delta x)$ is often non-convex in $\\\\Delta x$, hence the advantage of our formulation in the feature space that yields a convex problem. While input-space adversarial training can still be approximately solved—for example, using projected gradient descent (PGD), which is common in neural network settings—we compare both approaches in our numerical experiments (see Table 3).  \n\n* **(Q2) Adding relevant reference.**  Thank you. This is indeed a very relevant and interesting reference. It points to potential directions where our framework could be applied and offers valuable inspiration for future work. We will include it in the related work section and briefly discuss possible connections.  \n* **(Q3 & W2) About using Rademacher complexity.** Thank you for the opportunity to clarify. In this work, we rely on Gaussian complexity ($\\\\gamma$) and localized Gaussian complexity ($\\\\beta$). Nonetheless, we agree that Rademacher complexity is a powerful tool for analyzing generalization in adversarial settings \\[2\\], and it could indeed be used to extend our analysis to the random design case. Below, we explain our choice of Gaussian complexity and outline how Rademacher-based extensions could be pursued.  \n  1. **Gaussian vs Rademacher complexity.** Both Gaussian and Rademacher complexities are useful for studying generalization, but Gaussian complexity offers a particular advantage in regression settings: it allows the role of the noise level $\\\\sigma$ to appear more transparently in the analysis. In contrast, this dependence is harder to extract when using Rademacher complexity. For example, \\[2, Section 7\\] presents a rigorous analysis of kernel regression using Rademacher complexity, but the role of $\\\\sigma$ is not explicit. In our view, this transparency is one motivation for our choice. That said, Rademacher complexity could still be applied on top of our results to derive random design generalization bounds, while retaining the insights related to $\\\\sigma$. We consider this a natural and technically straightforward extension, and we will clarify this in Section 5.3.  \n  2. **Localized Gaussian complexity.** It is also important to note that neither Gaussian nor Rademacher complexity in their standard forms yield faster rates than $1/\\\\sqrt{n}$. However, some of our generalization rates—such as $B^{\\\\text{adv}}$ and $B^{\\\\text{kr}}$—scale with $\\\\beta^2$ and can be faster, due to the use of *localized* Gaussian complexity (see, e.g., \\[4\\], Chapter 13). As we mention in the paper, obtaining analogous rates in the random design case would require the use of localized Rademacher complexity \\[6\\], which involves additional assumptions and technical challenges (see \\[5\\] and \\[4\\], Chapter 14). We believe this is a promising direction, better suited for future work.\n\n  Overall, we appreciate the suggestion. We agree that, particularly for the first case, extending our results using Rademacher complexity is both natural and feasible. We will revise Section 5.3 to include a more detailed discussion of these points and the possible extensions.\n\n* **(Q4) Definition of R.** Thank you for pointing this out. This was mentioned in the first paragraph of Section 5, $R \\= \\\\|f^\\*\\\\|\\_{\\\\mathcal{H}}$ denotes the radius of the hypothesis space in the RKHS.  But we agree this can be easily missed by the reader. To improve clarity, we will add this definition directly to the relevant theorem statements to ensure they are fully self-contained.  \n* **(Q5) On the definition of $d$.** Thank you very much for bringing this up. You are absolutely right that the definition given after Equation (11) is unclear and does not specify the space to which $d$ belongs.  It should be $d \\= \\\\max\\_j(d\\_j)$ where $d\\_j\\\\in  \\\\mathcal{H}\\_j , \\\\|d\\_j\\\\|\\_{\\\\mathcal{H}\\_j} \\\\le \\\\delta.$ We sincerely appreciate you spotting this issue. We emphasize that all subsequent results remain valid. We will revise the text to correct and clarify this definition.\n\n**References:**\n\n* \\[1\\] \"Overparameterized Linear Regression Under Adversarial Attacks\" A. H. Ribeiro and T. B. Schön. *IEEE Transactions on Signal Processing*, vol. 71, pp. 601–614, 2023\\.  \n* \\[2\\] \"Rademacher Complexity for Adversarially Robust Generalization\" D. Yin, K. Ramchandran, and P. Bartlett. *ICML*, 2019\\.  \n*  \\[3\\] \"Learning Theory from First Principles\" F. Bach. *The MIT Press*, 2024\\.  \n*  \\[4\\] \"High-Dimensional Statistics: A Non-Asymptotic Viewpoint\" M. J. Wainwright. *Cambridge University Press*, 2019\\.  \n*  \\[5\\] \"Gaussian and Rademacher Complexities: Risk Bounds and Structural Results\" P. L. Bartlett and S. Mendelson. *Journal of Machine Learning Research*, vol. 3, pp. 463–482, 2002\\.  \n*  \\[6\\] \"Local Rademacher Complexities\" P. L. Bartlett, O. Bousquet, and S. Mendelson. *Annals of Statistics*, vol. 33, no. 4, pp. 1497–1537, 2005\\."}, {"review_id": "LpDWhVz8zg", "reviewer": "Reviewer_PoeL", "summary": "This paper looks at adversarial optimization in the context of adversarial robustness. Instead of framing the problem as a min-max optimization with respect to perturbation in input space, they consider perturbations in feature space, which allow to translate the min-max problem in a convex optimization algorithm with convergence guarantees. The authors later provide theoretical generalization bounds on this method, and provide numerical evidence that this method has advantages with respect to kernel ridge regression and standard robust training.", "questions": "Line 73-74: the Authors claim they consider square loss for simplicity and they point out that some developements can be applied more generally. Can they elaborate on this? Do not find an argument about this statement in the paper.\n\nLine 155: if the Authors refer to the fact that in ridge regression the optimal regularization $\\lambda$ depends on the noise, maybe adding one line of explanation, reference can improve the readability.", "limitations": "It seems to me this paper does not have any theoretical insight for the high dimensional. If this is true, it is fair to discuss this.\n\nThe paper does not carry a clear connection between the meaning of $\\delta$ in input space and on a generic feature space. In words, a fixed value of $\\delta$ for a specific feature map, would provide robustness guarantees as if the optimization was like the one in Eq. (1) for which radius of $\\Omega_X$?", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strenghts**\n\nThe paper discusses what i think to be a rather original approach to robust optimization. Furthermore, the paper is well written and presented with rigor.\n\n---\n\n**Weaknesses**\n\nThe Authors minimally elaborate on what is the exact set $\\Omega_{X}$ for different feature maps. They provide examples in Table 1, but I would in general stress that this connection is important to track the relevance of the the value $\\delta$ to express robustness (which generally considers perturbations in input space, not feature space)\n\nTo my understanding, these results are meaningful in the small dimensional setting, i.e. the scalings are for sufficiently large number of samples $n$, and the number of input dimensions $p$ is much smaller (see for example Table 2). This should also be a necessary assumption to have a direct connection between the fixed and random design (see line 153), as overfitting here becomes negligible. Can the authors remark on this point? In case I am correct, given the high popularity of high dimensional learning in the recent literature I would strongly suggest to remark this limitation in the revision.\n\nAt line 178 I found myself confused: the Authors mention \"optimal choices for $\\delta$\". To my understanding, $\\delta$ is a parameter that guarantees more robustness as it grows larger, and performances are in general monotonically decreasing as $\\delta$ increases (tradeoff between robustness and generalization). The narrative here seems to have a different angle, as $\\delta$ is framed more as a hyper-parameter that enables regularization. Can the authors explain this difference in perspective? This is maybe my main concern regarding the significance of this work. This is also not clear with respect to the results shown in Table 3, where $\\delta$ is directly associated with the resistance to some attack...\n\nIt is not totally clear to me how to parse the numerical experiments in the last section: in general, I would compare the test error of two algorithms for a fixed level of safety (which I identify as the resistance to adversarial perturbations). Here, a fixed value of $\\delta$ gives different robustness guarantees depending on the specific kernel (as shown for few examples in Table 1). It is possible that the proposed method has better generalization simply because it is guaranteeing \"less robustness\" for input perturbations (I am referring to Figure 3 in this case). Considering my previous comment, it is possible I did not fully understood what is the role of $\\delta$ the Authors want to stress here...", "was_revised": true, "final_justification": "The final justification is in my discussion comment for AC and Reviewers.", "rebuttal": "Thank you very much for your comments—they were extremely helpful. You raised several important points that we aim to clarify in the revised version of the paper. Below, we respond to your specific questions, as well as the limitations (L) and weaknesses (W) you identified. For reference, we use labels such as L1 for the first point raised in the first paragraph of “Limitations,” W2 for the second point raised in the “Weaknesses” section, and so on.\n\n* **(L1/W2)   Importance of our analysis in the high-dimensional regime.** We want to highlight that the results from Section 5 of our paper are relevant in the high-dimensional regime. Particularly, they have strong parallels to that of Chapter 13 in the book “High-Dimensional Statistics,” \\[3\\] where similar bounds are used to analyse Kernel Ridge Regression in the high-dimensional regime.   \n  * **About Table 2\\.** We included the bounded $p$ assumption for the Gaussian kernel in Table 2 mainly for clarity, as it allowed us to provide a simple closed-form expression for $\\\\beta$. However, we agree this could be confusing, since all other results hold for arbitrary $p$. We will revise the text to make this distinction clearer and avoid potential misunderstanding.  \n  * **Two different regimes.** We obtain two different regimes in Theorem 1\\. One regime depends on $\\\\gamma$ and is independent of the input dimension. This bound remains relevant even in very high-dimensional settings. The second regime depends on $\\\\beta$, and for the linear and Matérn kernels, the dependency on the input dimension $p$ is made explicit in the expressions for $\\\\beta$, allowing direct analysis in high-dimensional scenarios. This bound can sometimes outperform the dimension-free one when $p$ is small, but it is typically looser in the high-dimensional regime.  \n  * **Analysing overfitting.** Our analysis also sheds light on the bias–variance trade-off. The upper bounds we derive reveal an explicit dependence on the noise level $\\\\sigma$ and admit a natural interpretation: terms involving $R$ capture the bias component, while terms involving $\\\\sigma$ reflect variance. For example, when $\\\\delta \\= 0$, the term $B^{\\\\text{adv}}$ recovers the classical bound for linear regression, $\\\\sigma^2 d / n$, illustrating how overfitting arises when the number of parameters is too large. In contrast, the bound $A^{\\\\text{adv}}$ remains independent of the number of parameters, emphasizing the regularizing effect of adversarial training.  \n* **(L2/W1) Highlighting the exact meaning of set $\\\\Omega\\_X$.**  Thank you a lot for the question about  $\\\\Omega\\_X$. We will try to make things more explicit in the main text, but we highlight that Table 1 gives one to one equivalences between radius on the feature space  $\\\\delta\\_{features}$ and the input space $\\\\delta\\_{inp}$.  Under these choices, our method gives robustness equivalences that also hold in the input space. For instance for $\\\\delta\\_{inp} \\\\Leftrightarrow  \\\\delta\\_{features}$ for linear kernels;  $\\\\delta\\_{inp} \\\\Leftrightarrow C\\\\delta\\_{features}^{1/d}$ for polynomial and so on.  We will better highlight this connection, bringing some insight into the main text. We will also make clear the limitations of such analysis, particularly for the kernels where the $\\\\delta\\_{inp}$  in the input space increases very slowly with  $\\\\delta\\_{features}$ in the feature space.   \n* **(W3)  Robustness vs regularization.** Thank you for raising this important point. We agree that the dual role of adversarial training is central to the paper, and we appreciate the opportunity to clarify this. In our work, we emphasize two distinct perspectives on adversarial training:  \n   1. **Robustness perspective:** Adversarial training is used to defend against perturbations in the input space—larger values of $\\\\delta$ offer stronger protection but may degrade generalization.  \n   2. **Regularization perspective:** Following Ribeiro et al.  \\[4\\], we view adversarial training as a form of regularization, where $\\\\delta$ acts as a tuning parameter akin to the regularization strength in ridge regression. A key benefit is that it can be chosen independently of the noise level, e.g., set as $\\\\delta \\\\propto 1/\\\\sqrt{n}$.  We will revise the text to clearly distinguish these two perspectives early in the paper and avoid confusion.  \n* **(W3) Optimal choice of $\\\\delta$.** Indeed, there is a conflicting goal here on how to set $\\\\delta$ and a tradeoff between robustness and generalization. For robustness, $\\\\delta$ should remain fixed to guarantee resistance to a specific threat model. In contrast, from the generalization/regularization viewpoint, we allow $\\\\delta$ to decrease with sample size, enabling the estimator to approach the true function—much like a shrinking regularization path. When we refer to the \"optimal choice\" of $\\\\delta$, we are referring specifically to the second perspective (generalization). We will make this more explicit in the revision.  \n* **(W4) Experiments with $\\\\delta$ constant.**  We will include experiments with a fixed $\\\\delta$. Below, we present a representative example using the *pollution* dataset. Robustness is evaluated against input-space attacks with $p=\\\\infty$ and $\\\\delta\\_{\\\\text{inp}} \\= 0.1$—a higher value than in the main tables, chosen to emphasize the effects.  Notably, our method outperforms direct input-space adversarial training under the same threat model ($p=\\\\infty$, $\\\\delta\\_{\\\\text{inp}} \\= 0.1$), especially in terms of robustness. Moreover, these results illustrate the trade-off between clean and adversarial accuracy: as the feature-space adversarial radius $\\\\delta$ increases, the model becomes more robust, albeit with a slight drop in performance on clean data. *We show the $R^2$ score (higher is better).*\n| $R^2$ score  | Clean data  |  Adversarial attack  |\n| :---- | ----: | ----: |\n| **Adv Kern** (ours, $\\\\delta\\=0.01$) | **0.72** | 0.51 |\n| **Adv Kern** (ours, $\\\\delta\\=0.1$) | 0.67 | **0.58** |\n| **Adv Inp** (same threat model as evaluation)  |  0.68 | 0.50 | \n\n\n* **(W4) Interpreting Figure 3\\.** We agree that robustness to input perturbations depends on the kernel, since the same value of $\\\\delta$ in feature space implies different levels of robustness in input space, as shown in Table 1\\. However, we stress that our primary goal in Figure 3 is to evaluate generalization performance, not robustness. To avoid confusion, we will revise the text to clarify the intended interpretation of each experiment and the role $\\\\delta$ plays in each setting.  \n* **(Question about Line 73-74)** Thank you for the comment. We agree that this point deserves a clearer explanation in the text. Several of our developments can indeed be extended to classification settings. In particular, the core idea of adversarial training in feature space applies broadly, whether the task is regression or classification.  \n Proposition 1, which provides bounds on the input-feature perturbation relation, holds for classification as well. Proposition 2 also admits a natural analogue in the classification setting, under similar regularity assumptions. While the specific optimization algorithm we propose relies on the structure of the square loss, related approaches for classification have been developed—e.g., Ribeiro et al. \\[1\\] propose an algorithm in the linear setting that could be extended to the nonparametric case considered here.  \n  Finally, Sections 5 and 6, which study generalization and empirical performance, could in principle be adapted to classification tasks. However, doing so would require further theoretical and experimental work, and we believe it is best left for future work. We will revise the text to clarify these points.  \n* **(Question about Line 155\\)** Thank you for the comment. You are absolutely right. We will add comments and a reference to improve readability.  More specifically, one place where this is shown is in Proposition 3.8 of  \\[2\\]\n\n**References:**\n\n* \\[1\\] \"Efficient Optimization Algorithms for Linear Adversarial Training\" A. H. Ribeiro, T. B. Schön, D. Zachariah, and F. Bach. *AISTATS*, 2025\\.  \n* \\[2\\] \"Learning Theory from First Principles\" F. Bach. *The MIT Press*, 2024\\.  \n* \\[3\\] \"High-Dimensional Statistics: A Non-Asymptotic Viewpoint\" M. J. Wainwright. *Cambridge University Press*, 2019\\.  \n* \\[4\\] “Regularization properties of adversarially trained linear regression,” A. H. Ribeiro,, D. Zachariah,  F. Bach, and T. B. Schön. *NeurIPS*, 2023"}, {"review_id": "kZxpTwAfmR", "reviewer": "Reviewer_KwLt", "summary": "This paper presents a new method for adversarial training in the regenerated kernel Hilbert space. By transferring perturbations from the input space to the feature space, convex optimization and adaptive regularization are achieved. Theoretical analysis and experiments verified the validity of the method.", "questions": "1.The comparison of related jobs (such as TRADES, etc.) is not comprehensive enough, and the Adversarial training methods in recent years have not been fully discussed in Adversarial training in deep learning, which weakening the positioning of the methods in the field of deep learning\n\n2.In the introduction, a comparison of non-RKHS methods (such as adversarial training in deep learning) is added to highlight the theoretical uniqueness of the method proposed in this paper.\n\n3. The inheritance and development relationship with the work of Ribeiro et al. (2023) can be clearly stated to avoid repetition.\n\n4. If only PGD attacks are tested, why not verify the robustness against other attacks (such as FGSM, C&W)?\n\n5. How sensitive δ and λ are to the results, and the hyperparameter selection criteria (such as the specific implementation effect of cross-validation) are not specified. The influence of the ε value in η-trick on the convergence rate and stability has not been fully discussed.\n\n6. The alternating use of \"adversarial perturbation\" and \"feature perturbation\" can easily lead to misunderstandings. It is recommended to review the entire text and improve the manuscript.\n\n7. “As shown in Figure 1...” However, the content of Figure 1 was not explicitly mentioned in the paper.", "limitations": "The paper is valuable in terms of methodological innovation and theoretical analysis, but it does not fully discuss the technical limitations and neglects the analysis of social impact, which may reduce its credibility in practical applications.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The overall framework is theoretically innovative, but the experimental design and writing expression need to be further improved.\n\n1.The upper bound relationship of the characteristic perturbation objective function with respect to the input perturbation target was derived, and the generalization error limit was derived.\n\n2.Adversarial training migrates from the input space to the feature space, solving the computational bottleneck of the traditional min-max problem.\n\n3.Extend the framework to multiple kernel learning, and the mathematical proof is rather rigorous.", "was_revised": true, "final_justification": "Thank you for the authors' efforts during the rebuttal period, my main concern are resolved. I will maintain my score.", "rebuttal": "Thank you very much for your constructive feedback. We answer your Questions **(Q)** below and will update the paper accordingly.\n\n* **(Q1 & Q2) On related literature on adversarial training for deep learning.** Thank you for this important observation. We agree that our current discussion of adversarial training methods in deep learning could be strengthened. Our framework aligns with recent efforts that aim to make adversarial training more efficient through simpler, theoretically grounded regularization techniques. Indeed, recent works have sought to simplify adversarial training by relying on single-step perturbations \\[2\\] or latent-space perturbations \\[3\\], rather than more costly multi-step procedures. As you mention, methods such as TRADES \\[1\\] explore variants of robust optimization that trade off accuracy and robustness using tractable approximations. Overall, we believe there is also a tendency to try to use fast and simpler methods that align with our work. We will revise the introduction and related work section to include a more comprehensive comparison with adversarial training in the deep learning setting and highlight our contribution relative to these recent advances.  \n* **(Q3)** **On more explicit mention of Ribeiro et al. (2023).** We agree and will make this connection more explicit to avoid unnecessary repetition, highlighting early on the links to Ribeiro et al. (2023) and how our work extends it to the nonparametric setting.  \n* **(Q4) On the use of PGD.** Thank you for the comment. We will add a sentence to justify our choice. We use PGD because it is a strong multi-step adversary that generalizes many other methods. PGD was introduced by Madry et al. \\[4\\] as a unifying framework for first-order adversarial attacks (see Section 3, “Towards Universally Robust Networks”), offering a principled formulation for adversaries. Many popular attacks, such as FGSM and C\\&W, can be interpreted as special cases of PGD with fewer steps or different constraints. This unified perspective facilitates a more general and consistent analysis, which may be obscured when relying on weaker, single-step methods.  \n* **(Q5) On the influence of hyperparameters.** Thank you for the suggestion—this is indeed an important point. The performance variation with respect to $\\\\delta$ is highly relevant, and we will include additional analysis in the paper. The table below shows how the test MSE of Adversarial Kernel Regression changes as a function of $\\\\delta$. In this experiment, we used an RBF kernel and 100 training points sampled from a sine curve with additive Gaussian noise (standard deviation 0.1). For reference, standard kernel ridge regression with cross-validation achieves a test MSE of 0.001. We will include this and other sensitivity analyses in the revised version of the paper.\n| $\\\\delta$ | Test MSE |\n| :-----| ---- |\n| $1 \\\\times 10^{-5}$ | 0.002 |\n| $7 \\\\times 10^{-4}$ | 0.001 |\n| 0.026 | 0.002 |\n| 0.048 | 0.003 |\n| 0.086 | 0.009 |\n| 0.16 | 0.033 |\n| 0.30 | 0.329 |\n| 0.55 | 0.499 |\n| 1 | 0.499 |\n\n  About setting $\\\\epsilon$, we follow the recommendation of \\[5\\] and set $\\\\epsilon \\= 1e-20$. Overall, our experience is that this is quite easy to set. Using a small value close to numerical precision yields good results, and the exact value is not important.\n\n* **(Q6)** **Using more consistent nomenclature.** Thank you for the suggestion. We agree and will revise the manuscript to use terminology more consistently, referring to our approach as \"feature-space adversarial perturbation\" throughout, to avoid confusion.  \n* **(Q7) Mention all the figures in the main text.**  We agree. In the revised version, we will explicitly describe Figure 1 in the paragraph following it. So that the main text contains a description of each panel and the main takeaway that our method adapts to the function’s smoothness without requiring explicit tuning.  \n* **(Limitations)** Thank you for the helpful and constructive feedback. We will incorporate the reviewer’s suggestions by clearly stating the main technical limitations in the revised version. While the paper is primarily theoretical, we agree it is important to reflect on societal impact and will add a brief discussion—particularly noting that safer, adversarially trained models often come with increased computational cost, which we hope can be mitigated through improved formulations such as the one we propose.\n\n**References:**\n\n* \\[1\\] \"Theoretically Principled Trade-off between Robustness and Accuracy\" H. Zhang, Y. Yu, J. Jiao, E. Xing, L. El Ghaoui, and M. Jordan. *ICML*, 2019  \n* \\[2\\] \"Fast is Better than Free: Revisiting Adversarial Training\" E. Wong, L. Rice, and J. Z. Kolter. *ICLR*, 2020\\.  \n*  \\[3\\] \"Reliably Fast Adversarial Training via Latent Adversarial Perturbation\" G. Y. Park and S. W. Lee. *ICCV,* 2021\\.  \n*  \\[4\\] \"Towards Deep Learning Models Resistant to Adversarial Attacks\" A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu. ICLR, 2018\\.  \n*  \\[5\\] \"Efficient Optimization Algorithms for Linear Adversarial Training\" A. H. Ribeiro, T. B. Schön, D. Zachariah, and F. Bach. *AISTATS*, 2025\\."}]

Author rebuttal:

Meta-review: This paper proposes a new adversarial training framework based on kernel space. The core idea is to transfer adversarial perturbations from the input space to a high-dimensional feature space defined by a kernel function. This conversion brings several key advantages
1. Convert the "min-max" problem that is originally difficult to optimize into a convex optimization problem, so that it can be solved efficiently.
2. The paper proves that this new objective function has a closed-form solution, which avoids iterative optimization in the inner loop.
3. This method provides an adaptive regularization effect and can achieve near-optimal performance without knowing the data noise level. This is a significant advantage compared to standard kernel ridge regression.

Overall, the reviewers think this paper is solid.
Decision: Accept (poster)