A Comprehensive Analysis of the Adversarial Robustness of Kernel Methods
Adversarial Robustness of Kernel Machines: A Comprehensive Analysis
The authors systematically compare the adversarial robustness of kernel machines and neural networks on 8 datasets, state that kernel machines are inherently more robust, and provide an approximate adversarial training algorithm for kernel machines.
- Most adversarial example research centers on neural networks, and the adversarial robustness of kernel machines (KM) and their variants RFC and RFM lacks systematic comparison. The authors ask: is there a hierarchy of adversarial robustness among different function classes.
- On 5 image and 3 tabular datasets, white-box (PGD, AutoAttack) and black-box (SPSA) attacks are used to compare the robust accuracy of KRR, KLR, KSVM, RFC, RFM with FCNN, LeNet, WRN, and an approximate adversarial training algorithm for kernel machines, MARK, is derived.
- The authors state that the robustness of KM decreases more slowly than that of NN as the attack budget increases, with gaps of up to 40 (multiclass) to 70 (binary) percentage points on some tasks; Gaussian KLR exceeds adversarially trained NN on three datasets; Laplacian RFC exhibits gradient masking.
- Limitations listed by the authors include: attacks are tuned for NN, only ℓp threats are considered, only relatively simple datasets are used, there are no theoretical guarantees, and the gradient masking of Laplacian RFC is not fully explained; future directions include theoretical analysis and comparison with tree models.
- Threat model
- Test-time evasion attacks: the attacker perturbs the input within an ℓ∞ or ℓ2 norm budget ε to make the classifier misclassify; for images, white-box attacks (PGD, AutoAttack's apgd-ce) and black-box attacks (SPSA) are used, and for tabular data, CaFA; the victim systems are kernel machines and neural network classifiers.
- Evaluated models
- KRRKLRKSVMRFCRFMAdv-KLRFCNNFCNN-AdvLeNet-5LeNet-AdvWideResNet-28-10 (WRN-28-10)
- Benchmarks
- FashionMNISTKMNISTQMNISTSVHNCIFAR-10AdultBankMarketingPhishing
- Metrics
- robust accuracybenign accuracyone-v-one robust accuracypointwise boundary distance εb
The researchers comprehensively evaluate the adversarial robustness of kernel methods through white-box and black-box evasion attacks; the experiments strongly indicate that they are naturally more resistant to adversarial perturbations than neural networks, with a gentler performance decline. The evaluation covers kernel methods, random feature classifiers, and the more recent Recursive Feature Machines, spanning binary and multiclass tasks on image and tabular datasets. The paper also proposes an approximate adversarial training algorithm for kernel methods.
Paper analysis
What problem does this paper attempt to solve?
The adversarial robustness of kernel machines and their variants relative to neural networks lacks systematic empirical comparison, and the paper fills this gap.
Core question: are models such as kernel machines (KM) inherently harder to attack with adversarial examples than neural networks, i.e., is there a hierarchy of adversarial robustness between function classes (possibly dataset-dependent).
- Problem setting: The authors note that adversarial examples are also prevalent in limited-information settings, and that apart from robust training there are few effective defenses; robust training solves a min-max problem, is computationally expensive, and has unfavorable trade-offs. This motivates the authors to re-examine whether there exists a class of models that is inherently more robust than NN.
- Gaps in existing research: The authors state that KM have regained attention due to results such as NTK, but their adversarial robustness has "received little attention"; a comprehensive comparison of the three variants KM, RFC, RFM had not been done before (§1.2).
- What the paper proposes: An empirical comparison covering 8 datasets and multiple attacks, with analysis at three levels: overall robust accuracy, fine-grained robust accuracy on C choose 2 one-vs-one tasks, and per-point distance from individual samples to the decision boundary; additionally an approximate adversarial training algorithm for KM (a convex approximation for binary classification, and a non-convex approximation plus iterative algorithm for multiclass).
- Threat model:
- Goal: test-time evasion, i.e., perturbing the input within a norm budget so that the classification result changes (§2.1).
- Knowledge: white-box (AutoPGD/PGD, with access to the model implementation) and black-box (SPSA, input-output access only); CaFA is used for tabular data.
- Capability: ℓ∞ and ℓ2 perturbation budgets ε on images; ℓ∞ budget on tabular data subject to feature constraints.
- Victim systems: KRR, KLR, KSVM, RFC, RFM and FCNN, LeNet, WRN-28-10 classifiers.
What related research exists?
Related work falls into three groups: robustness of KM against poisoning, studies of test-time perturbations against KM, and theoretical analysis of RFC overparameterization.
Robustness of KM to data poisoning
- KM with outlier-resistant loss functions such as Cauchy loss, Huber loss, and ℓ1 loss (the paper cites [43][41][39][13])—enhancing KM with poisoning-resistant losses.
- Li et al. [26]—prove that KM trained with the NTK and early stopping is robust to label noise.
Test-time perturbations against KM
- Xu et al. [47]—use a hinge loss upper bound and a regularized variant to show that KSVM is robust to pointwise uncertainty; the paper notes that they provide no empirical evidence and perturb only in feature space.
- Wang [40] (which the paper calls the closest to this work)—analyzes the empirical robustness of linear and Gaussian kernel SVMs and finds them not robust; the paper instead claims that KLR, KRR, and KSVM with the Laplacian kernel and a properly tuned Gaussian kernel are robust.
- Han and Rubinstein [16]—study gradient-descent evasion attacks on Gaussian SVM and find that reducing kernel smoothness improves robustness.
Theoretical analysis of RFC and adversarial training of KM
- Hassani and Javanmard [17]—theoretically analyze how overparameterized random features harm robust generalization under the proportional asymptotics d,p,n→∞; the paper states that its experimental results raise questions about the practical validity of their conclusions, and the authors suggest this may be because their feature isotropy assumption leads to pessimistic results.
- Wu et al. [44]—perform adversarial training of KM in feature space via dual stochastic gradients; the paper points out that [40][44] both perform adversarial training in feature space rather than input space, and both use the upper bound of [47], which is often overly conservative.
Comparison setting: The comparison models are FCNN, LeNet-5, WideResNet-28-10 and their adversarially trained variants; the benchmarks are FashionMNIST, KMNIST, QMNIST, SVHN, CIFAR-10 and Adult, BankMarketing, Phishing (Table 1).
The authors position this paper as: providing the previously missing comprehensive robustness comparison of three kernel model variants, and giving an approximate adversarial training method for KM in input space.
How does the paper address this problem?
Systematically compare three types of kernel models with neural networks using a hierarchical robust accuracy metric, and derive an approximate adversarial training algorithm for KM, MARK.
Overall approach: measure the robust accuracy of kernel machines (KRR/KLR/KSVM), RFC, RFM, and NNs under a unified attack protocol, comparing at three levels: overall, one-vs-one, and pointwise; the theoretical part makes a first-order approximation to the robust training objective, yielding a solvable approximate adversarial training problem.
Problem setting and metrics
- Adversarial example definition: at x, a perturbation δ satisfies ∥δ∥p ≤ ε and changes the arg max prediction (§2.1); attacks approximately solve the norm-constrained loss maximization problem via local search, using cross-entropy as the loss.
- Robust accuracy: raε(f) := 1 − P[∃ δ: |δ|p ≤ ε, argmaxi fi(x+δ) ≠ y], i.e., the proportion of samples for which no successful perturbation within the budget exists, estimated via plug-in.
- Three-level analysis: overall multiclass robust accuracy; fine-grained decomposition of C choose 2 one-vs-one tasks; pointwise robustness εb(f,(x,y)), estimated by binary search combined with AutoAttack for the distance of a single sample to the boundary.
Model families compared
- KM: f(x) = ∑i=1n αi K(x, xi), using Matérn family kernels (Laplacian ν=1/2, Gaussian ν→∞), with square loss (KRR), hinge loss (KSVM), and logistic loss (KLR) respectively.
- RFM: the kernel is parameterized by a positive semidefinite matrix M, which is recursively updated using the average gradient outer product (AGOP), for at most 5 iterations, trained with square loss.
- RFC: random feature approximation, with 5000 and 20000 features for binary classification, an ablation over 10k–60k features for multiclass classification, and both square and cross-entropy losses.
Approximate adversarial training (§4)
- Starting point: the robust training min-max problem on the RKHS no longer has a representer theorem guaranteeing a finite representation; linearizing for small ε gives the objective minf ∑i ℓi(f(xi)) + ε|ℓi′(f(xi))⊤ ∇ f(xi)|q + λ/2|f|H2.
- Binary classification: taking a convex upper bound for Lipschitz losses (∥ℓ′∥≤L) gives a convex problem; under ℓ∞, a saddle-point form and stochastic primal-dual updates are derived (Eq. 10), with a matrix-free implementation, O(n(d+1)) memory, decaying step sizes, and convergence guaranteed only for λ>0.
- Multiclass classification: Proposition 2 gives a solution form with 2nc+nd coefficients (far fewer than the general case's nc(d+1)); for cross-entropy, using ∥ℓ′∥1≤2 gives an upper bound, the objective is convex but the constraint set is nonconvex, and MARK is proposed (Algorithm 1): an approximate rank-1 projection every T epochs (Algorithm 2, the delayed projection idea).
Attacks and evaluation protocol
- White-box: fixed-iteration PGD (100 steps, step size ε/10) and AutoAttack's apgd-ce, reporting the lower robust accuracy of the two.
- Black-box: SPSA is used to check for gradient masking; tabular data uses CaFA (mining constraints, TabPGD perturbation, SAT projection), with ε ∈ {0.01, 0.03, 0.075}.
- Model selection: the hyperparameter combination with the highest clean accuracy on the validation set is the attack target; the hyperparameter search ranges are in §B (e.g., the λ, σ grid for KRR).
What experiments did the paper conduct?
Robust accuracy of 13 models is compared on 8 datasets; KM degrades more slowly as ε increases, and Gaussian KLR surpasses adversarially trained NNs.
Experimental setup
- Models evaluated: KRR, KLR, KSVM, RFC, RFM, adversarially trained KLR (MARK), compared against FCNN, LeNet, WRN-28-10 and adversarially trained FCNN-Adv, LeNet-Adv; Figure 2 has 13 models in total (3 adversarially trained, 10 benign).
- Datasets: images FashionMNIST, KMNIST, QMNIST, SVHN, CIFAR-10; tabular Adult, BankMarketing, Phishing (Table 1); the paper does not give the sample size of each dataset in the main text.
- Attacks: white-box PGD and AutoAttack (apgd-ce), taking the lower value; black-box SPSA; CaFA for tabular data. ℓ∞ multiclass budget ε0/255, ε0 ∈ {0,.1,1,2,4,6,8,12,20,32,40,55}; ℓ2 multiclass ε ∈ {0,.5,1,2,4,6} (§B.3).
- Metrics: robust accuracy (%), clean accuracy, one-vs-one difference heatmaps, CDF of per-point εb ratios.
- Repeats and seeds: RFC results are averaged over 10 seeds (100–550); FCNN shows consistent trends across seeds, seed 42 is reported; ℓ2 attacks have error bars but they are too small, ℓ∞ plots only seed 42 (§C.1).
- Adversarial training budgets: NN multiclass ℓ∞ training budgets FMNIST 8/255, KMNIST 16/255, QMNIST 24/255, ℓ2 is ε=1 (§B.4).
Main results
The table below shows the robust accuracy (%) of some models in Figure 2 (FMNIST multiclass, lower of PGD/AutoAttack, ℓ∞):
Swipe horizontally to read the table
Model ε=0 8/255 20/255 40/255 Adv. Gaussian KLR 85.1 82.3 78.6 72.2 Gaussian KLR 87.0 72.3 50.9 40.5 Laplacian KLR 88.2 73.0 48.2 30.6 Adv. FCNN 88.0 81.2 62.4 18.1 Adv. LeNet 88.8 82.1 53.0 2.6 Gaussian KRR 90.5 57.4 38.3 12.4 Laplacian KRR 90.0 69.1 34.8 4.5 Benign FCNN 89.6 50.7 8.3 0.0 Benign LeNet 90.5 26.9 0.2 0.0 (Omitted: Laplacian/Gaussian SVM, Laplacian/Gaussian RFM, all in Figure 2; among them Benign LeNet has the worst results at ε≥20/255.)
- The authors state that the robustness of KM decreases more slowly than that of NN as ε increases, with gaps of up to 40 percentage points on some multiclass tasks and 70 percentage points on binary tasks (§1.1); in Figure 2, at ε≥32/255 the best models are all KM with logistic loss.
- On KMNIST at ε=40/255, Gaussian KLR is 73.4%, while Adv. LeNet is 28.0%, Adv. FCNN 20.1%, Gaussian KRR 12.5%, Gaussian SVM 16.2% (§3.2, corresponding to the same values in Figure 4A).
- Exceptions: KLR lags in clean accuracy, and on FMNIST Adv. Gaussian KLR has the lowest clean accuracy (85.1%, Figure 2); on CIFAR-10 LeNet is comparable to KM under ℓ2 and better under ℓ∞ (§5.1).
Per-point robustness (§5.2)
- What was measured: For all random samples correctly classified by the models (FMNIST 388, KMNIST 423, QMNIST 479), the minimum successful perturbation εb is estimated by bisection + AutoAttack, and the CDF of the ratio εb(KLR)/εb(other models) is plotted (Figures 1, 6A, 7A).
- Results: The authors state that on the median sample KLR is more robust than Adv-FCNN and Adv-LeNet (nearly 2× on KMNIST); adversarially trained KM is the most robust among all models; on FMNIST the KRR and RFM curves overlap.
RFC and gradient masking (§3.4, §D.1)
- Gaussian RFC: Robustness rises steadily as the number of features increases, and robust accuracy is consistently higher under SPSA, from which the authors conclude there is no gradient masking; with enough features it exceeds FCNN and LeNet in many cases.
- Laplacian RFC: Robust accuracy under SPSA attack is lower than under white-box attack, and the authors state that gradient masking exists and that the white-box numbers overestimate its true robustness; under square loss, robustness varies irregularly with the number of features. The authors attribute this to the heavy-tailed (Cauchy) spectral distribution of Laplace random features.
Other ablations and analyses
- RFM iterations: More feature-learning iterations reduce the robustness of Laplacian RFM (Fig. 78A); on KMNIST/QMNIST KRR is more robust than RFM, and on FMNIST RFM is comparable (§3.3).
- Kernel parameters: Increasing the Matérn smoothness ν reduces robustness (Fig. 77A); a smaller length scale σ improves robustness (Figs. 79A, 80A); λ improves robustness only when very large, at the cost of clean accuracy (Fig. 81A).
- SVHN/CIFAR-10: Gaussian RFM exceeds all models on SVHN, improving on the base kernel accuracy by 20 percentage points (Table 4A); on CIFAR-10, in 4 of 5 random 1v1 tasks KM exceeds FCNN by up to 4% (Figs. 63A–66A).
- WRN-28-10: Clean accuracy is higher but robust accuracy drops faster than LeNet as the budget increases (Table 5A), from which the authors conclude that the advantage of KM does not stem from the size of the comparison models.
- MARK: Adversarial training improves KM robustness (Figs. 1, 2, 4A–7A); multiclass training takes about 24 hours/10 epochs (Table 3A).
What are some points that can be further explored?
The authors list 5 limitations and give follow-up directions such as theory, comparison with tree models on tabular data, and loss landscape analysis.
Limitations noted by the authors and follow-up directions
- Attack suitability (§5.3): The main attacks are tuned for NNs and may overestimate the robustness of KM; the authors consider this unlikely because the loss surface of KM should be relatively smooth for the attacker, so first-order attacks should be effective.
- Scope of threat model (§5.3): Only ℓp adversaries on visual data are considered; the authors consider it worthwhile to examine other attacks such as StAdv and ReColor.
- Dataset complexity (§5.3): Only relatively simple datasets on which KM and NN are competitive are used; the authors state this is beyond the scope of this paper and consider these tasks to be exactly the scenarios where lightweight KM applies.
- Lack of theoretical guarantees (§5.3): No theoretical result proving that KM is more robust than NN is given.
- Unexplained phenomena (§5.3): The gradient masking of Laplacian RFC, and the effects of training loss and number of features on robustness in RFC, are not fully characterized.
- Follow-up directions (§5.4): A representer theorem for exact robust training, robustness bounds specific to KM; comparison with tree models such as gradient boosted trees on tabular data; analysis of the attacker's loss landscape and the confidence of KM on adversarial and out-of-distribution samples.
Scope of experimental coverage
- 13 models tested in total: 5 types of kernel models (KRR/KLR/KSVM/RFC/RFM), MARK, FCNN, LeNet, WRN-28-10, and two adversarially trained NNs (Table 1, Figure 2).
- 8 datasets: 5 image + 3 tabular (Table 1); tabular experiments use CaFA with ε ∈ {0.01, 0.03, 0.075} (§A.2).
- Attacks cover white-box (PGD, apgd-ce), black-box (SPSA), and tabular constrained attacks (CaFA); both ℓ∞ and ℓ2 norms (§B.3).
- Pointwise analysis sample sizes are 388/423/479 (FMNIST/KMNIST/QMNIST, Figures 1, 6A, 7A); RFC uses 10 seeds, FCNN reports seed 42 (§B.1, §B.2).
- The paper does not report the number of repetitions or confidence intervals for each cell of the main results (ℓ∞ plots only seed 42, §C.1); SVHN and CIFAR-10 only had a "limited number of experiments" (§5.1).
Summarize the main content of the paper
Empirical comparisons show that kernel machines have better native adversarial robustness than neural networks, and the paper also provides an approximate adversarial training algorithm for kernel machines.
An empirical study on the adversarial robustness of kernel machines, addressing the question "is there an adversarial robustness hierarchy among function classes?"
- Problem: Adversarial example research concentrates on NNs, and the robustness of KM and its variants RFC and RFM lacks systematic comparison; robust training is expensive, so the authors seek model classes that are naturally more robust.
- Method: On 8 datasets (5 image + 3 tabular), robust accuracy of 13 models is measured using PGD, AutoAttack (white-box), SPSA (black-box), and CaFA (tabular), analyzed at three levels: overall, one-vs-one, and pointwise; theoretically, a first-order approximation is made to the robust training objective, yielding a convex problem for binary classification, and for multiclass classification an iterative algorithm MARK with delayed rank-1 projection is proposed.
- Main results:
- The authors state that KM degrades more slowly as ε increases, leading NNs by up to 40 (multiclass)/70 (binary) percentage points on some tasks (§1.1).
- On FMNIST at ε=40/255, Adv. Gaussian KLR 72.2%, Adv. FCNN 18.1%, Adv. LeNet 2.6% (Figure 2).
- On KMNIST at ε=40/255, Gaussian KLR 73.4%, higher than Adv. LeNet 28.0% and Adv. FCNN 20.1% (§3.2).
- On the median sample, the pointwise robustness of KLR exceeds that of adversarially trained FCNN/LeNet, nearly 2× on KMNIST (Figures 1, 6A).
- Laplacian RFC has lower robust accuracy under SPSA, which the authors attribute to gradient masking; Gaussian RFC does not show this phenomenon and becomes more robust as the number of features increases.
- Authors' conclusion: The authors argue that KM (especially KLR with logistic loss) is natively more robust than NNs on these datasets and can be further enhanced via MARK; interpolation behavior may not contradict test robustness. The authors also acknowledge limitations such as attacks being tuned for NNs, relatively simple datasets, and no theoretical guarantees, and list theoretical explanation and broader threat models as future work.
Related papers
- No Free Efficiency: Revisiting the Trade-off Between Training Efficiency and Model VulnerabilityAnalysis / interpretabilityarXiv