Robustness and Regularization of Support Vector Machines

Abstract

We consider regularized support vector machines (SVMs) and show that they are precisely equivalent to a new robust optimization formulation. We show that this equivalence of robust optimization and regularization has implications for both algorithms, and analysis. In terms of algorithms, the equivalence suggests more general SVM-like algorithms for classification that explicitly build in protection to noise, and at the same time control overfitting. On the analysis front, the equivalence of robustness and regularization, provides a robust optimization interpretation for the success of regularized SVMs. We use the this new robustness interpretation of SVMs to give a new proof of consistency of (kernelized) SVMs, thus establishing robustness as the reason regularized SVMs generalize well.

References in corpus (1)

• Consistency and robustness of kernel-based regression in convex risk minimization

Cited by in corpus (71)

• Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning
• A review of domain adaptation without target labels
• Understanding Adversarial Training: Increasing Local Stability of Neural Nets through Robust Optimization
• Learning with Pseudo-Ensembles
• Certifying Some Distributional Robustness with Principled Adversarial Training
• Robust Wasserstein Profile Inference and Applications to Machine Learning
• Distributionally Robust Optimization: A Review
• Support vector machines on the D-Wave quantum annealer
• On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems
• Distributionally Robust Logistic Regression
• A Survey on Aspect-Based Sentiment Classification
• Adversarial Training and Robustness for Multiple Perturbations
• Robustness of classifiers: from adversarial to random noise
• Rademacher Complexity for Adversarially Robust Generalization
• A Closer Look at Accuracy vs. Robustness
• Action Robust Reinforcement Learning and Applications in Continuous Control
• Robust counterparts of inequalities containing sums of maxima of linear functions
• Sparse Regression: Scalable algorithms and empirical performance
• Theory of Deep Learning III: explaining the non-overfitting puzzle
• Linear Maximum Margin Classifier for Learning from Uncertain Data
• Near-Optimal Algorithms for Minimax Optimization
• A Game-Theoretic Approach to Design Secure and Resilient Distributed Support Vector Machines
• Provably Robust Boosted Decision Stumps and Trees against Adversarial Attacks
• Regularization of Case-Specific Parameters for Robustness and Efficiency
• Template Matching via Densities on the Roto-Translation Group
• Adversarial Risk Bounds via Function Transformation
• Improving Robustness of ML Classifiers against Realizable Evasion Attacks Using Conserved Features
• Distributional Robustness and Regularization in Reinforcement Learning
• Distributionally Robust Optimization and Generalization in Kernel Methods
• Robustness Analysis of Visual QA Models by Basic Questions
• Adversarial Extreme Multi-label Classification
• Kernel Distributionally Robust Optimization
• Concise Explanations of Neural Networks using Adversarial Training
• Calibrated Surrogate Losses for Adversarially Robust Classification
• Convergence and Margin of Adversarial Training on Separable Data
• Understanding Generalization in Adversarial Training via the Bias-Variance Decomposition
• Inductive Bias of Gradient Descent based Adversarial Training on Separable Data
• An Integer Programming Approach to Deep Neural Networks with Binary Activation Functions
• Softmax-based Classification is k-means Clustering: Formal Proof, Consequences for Adversarial Attacks, and Improvement through Centroid Based Tailoring
• Doubly Robust Data-Driven Distributionally Robust Optimization
• The coupling effect of Lipschitz regularization in deep neural networks
• Twice regularized MDPs and the equivalence between robustness and regularization
• Sharp Statistical Guarantees for Adversarially Robust Gaussian Classification
• Consistency of semi-supervised learning algorithms on graphs: Probit and one-hot methods
• Marginalizing Corrupted Features
• Adversarially Robust Estimate and Risk Analysis in Linear Regression
• Less is More: Robust and Novel Features for Malicious Domain Detection
• A Precise Performance Analysis of Support Vector Regression
• Adversarial Risk Bounds for Neural Networks through Sparsity based Compression
• Active Robust Learning
• Online First-Order Framework for Robust Convex Optimization
• Smoothed Inference for Adversarially-Trained Models
• Distributional Robustness Regularized Scenario Optimization with Application to Model Predictive Control
• Augmenting Model Robustness with Transformation-Invariant Attacks
• On Regularized Square-root Regression Problems: Distributionally Robust Interpretation and Fast Computations
• Adversarially Robust Kernel Smoothing
• A Robust Learning Algorithm for Regression Models Using Distributionally Robust Optimization under the Wasserstein Metric
• Comment on "robustness and regularization of support vector machines" by H. Xu, et al., (Journal of Machine Learning Research, vol. 10, pp. 1485-1510, 2009, arXiv:0803.3490)
• Robust Neural Networks inspired by Strong Stability Preserving Runge-Kutta methods
• Recent Advances in Large Margin Learning
• Noisy Feature Mixup
• Higher-Order Expansion and Bartlett Correctability of Distributionally Robust Optimization
• Bridged Adversarial Training
• Efficient and Robust Mixed-Integer Optimization Methods for Training Binarized Deep Neural Networks
• Safe Screening Rules for ${\ell }_0$-Regression
• Multiple Kernel Learning and Automatic Subspace Relevance Determination for High-dimensional Neuroimaging Data
• Game-Theoretic Design of Secure and Resilient Distributed Support Vector Machines with Adversaries
• How to Allocate Resources For Features Acquisition?
• Regularized maximum correntropy machine
• Oracle-Based Robust Optimization via Online Learning
• Defending SVMs against Poisoning Attacks: the Hardness and DBSCAN Approach