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-SVMdemonstrates 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-SVMto scale to larger datasets, as evidenced by experiments on MNIST8M. - Competitive Performance:
adv-SVMachieves 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 toadv-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-SVMrequires 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