Fast and Scalable Adversarial Training of Kernel SVM via Doubly Stochastic Gradients

Huimin Wu, Zhengmian Hu, Bin Gu

TL;DR

This paper introduces adv-SVM, the first method for fast and scalable adversarial training of kernel Support Vector Machines (SVMs). By cleverly reformulating the adversarial training objective and leveraging Doubly Stochastic Gradients (DSG) with random feature approximation, adv-SVM achieves robust kernel SVMs against adversarial attacks with significantly reduced computational cost.

What Problem Does This Paper Address?

Adversarial attacks, which subtly alter input data to fool machine learning models, pose a significant threat to the reliability of AI systems. While much research has focused on defending deep neural networks (DNNs) against these attacks, kernel SVMs, a fundamental and powerful machine learning algorithm, have been largely overlooked in the context of adversarial training. Existing adversarial training methods for SVMs are limited to linear SVMs and struggle with the computational complexity of kernel methods, especially on large datasets. This paper aims to bridge this gap by developing an efficient and scalable adversarial training method for kernel SVMs.

Methods

The core of this work lies in two main innovations:

  • Kernel Space Perturbation Equivalence: The authors establish a crucial connection between perturbations in the original input space and the corresponding feature space induced by the kernel. This allows them to reformulate the adversarial training objective for kernel SVMs into a more tractable form.
  • Doubly Stochastic Gradients (DSG) with Random Features: To overcome the computational bottleneck of kernel computations (which typically scale quadratically with the number of data points), the paper employs a DSG approach. This involves approximating kernel computations using random features, significantly reducing complexity. DSG updates are then applied to the reformulated objective function, enabling efficient and scalable training. The authors also provide theoretical guarantees for the convergence of their DSG-based algorithm.

Datasets

The authors evaluate their proposed adv-SVM on several standard datasets:

  • MNIST: Used in binary classification tasks (e.g., 1 vs. 7, 8 vs. 9, 8M 0 vs. 4, 8M 6 vs. 8).
  • CIFAR10: Used in binary classification tasks (e.g., automobile vs. truck, dog vs. horse).

These datasets are standard benchmarks for image classification and are adapted for binary classification to fit the SVM framework.

Key Insights and Ideas

  • Kernel Space Perturbations are Manageable: A key insight is that adversarial perturbations in the kernel space, while seemingly complex, can be effectively related to perturbations in the original space. This connection is fundamental to reformulating the problem.
  • DSG is a Game-Changer for Kernel SVMs: The application of DSG, combined with random feature approximation, is critical for making adversarial training of kernel SVMs computationally feasible. Without it, the quadratic complexity of kernel methods would render the approach impractical for large datasets.
  • Trade-off between Constant and Diminishing Stepsizes: The theoretical analysis highlights a trade-off: diminishing stepsize leads to smoother convergence, while constant stepsize offers a faster transient phase but may exhibit oscillations. Both are shown to achieve O(1/t) convergence.

Key Results

  • Robustness: adv-SVM demonstrates significant robustness against various white-box (FGSM, PGD, C&W) and black-box (ZOO) adversarial attacks across multiple datasets.
  • Efficiency: The proposed method achieves training times orders of magnitude faster than traditional linear SVM adversarial training (adv-linear-SVM), often completing in minutes rather than hours.
  • Scalability: The use of DSG and random features allows adv-SVM to scale to larger datasets, as evidenced by experiments on MNIST8M.
  • Competitive Performance: adv-SVM achieves competitive accuracy under attack compared to other methods, while significantly outperforming them in training speed. For instance, on CIFAR10 automobile vs. truck against C&W attack, adv-SVM(C) achieves 51.76% accuracy with a training time of 19.28 minutes, compared to adv-linear-SVM's 48.82% accuracy in 594.90 minutes.

Limitations and Future Work

  • Approximation-Based: The method relies on random feature approximation, which introduces an approximation error. However, the theoretical analysis shows that this error does not prevent convergence to the optimal solution.
  • Hyperparameter Tuning: Like most machine learning methods, adv-SVM requires careful tuning of hyperparameters (e.g., regularization parameter C, step size γ).
  • Future Work: The paper implicitly suggests future work could explore other kernel types, more advanced adversarial attack strategies, and potentially extend the framework to multi-class kernel SVMs. The authors also provide code for reproducibility.

Summary updated

Abstract

Adversarial attacks by generating examples which are almost indistinguishable from natural examples, pose a serious threat to learning models. Defending against adversarial attacks is a critical element for a reliable learning system. Support vector machine (SVM) is a classical yet still important learning algorithm even in the current deep learning era. Although a wide range of researches have been done in recent years to improve the adversarial robustness of learning models, but most of them are limited to deep neural networks (DNNs) and the work for kernel SVM is still vacant. In this paper, we aim at kernel SVM and propose adv-SVM to improve its adversarial robustness via adversarial training, which has been demonstrated to be the most promising defense techniques. To the best of our knowledge, this is the first work that devotes to the fast and scalable adversarial training of kernel SVM. Specifically, we first build connection of perturbations of samples between original and kernel spaces, and then give a reduced and equivalent formulation of adversarial training of kernel SVM based on the connection. Next, doubly stochastic gradients (DSG) based on two unbiased stochastic approximations (i.e., one is on training points and another is on random features) are applied to update the solution of our objective function. Finally, we prove that our algorithm optimized by DSG converges to the optimal solution at the rate of O(1/$t$) under the constant and diminishing stepsizes. Comprehensive experimental results show that our adversarial training algorithm enjoys robustness against various attacks and meanwhile has the similar efficiency and scalability with classical DSG algorithm.
BibTeX
@inproceedings{wu2021fast,
  author = {Huimin Wu and Zhengmian Hu and Bin Gu},
  title = {{Fast and Scalable Adversarial Training of Kernel SVM via Doubly Stochastic Gradients}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i12.17237},
}
Figure