Robustness and Regularization of Support Vector Machines

By Huan Xu, Constantine Caramanis, Shie Mannor. 2008

502 citations recorded by the source corpus.

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 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.

Subfields: Control and Systems Engineering, Optimization & Training, Statistical Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Control and Systems Engineering

In Optimization & Training

In Statistical Learning Theory

Citations in the corpus

Wild Patterns: Ten Years After the Rise of Adversarial Machine Learning (2017, background): “More recently, we have also exploited the theoretical ﬁndings in [78], which connect regularization and robustness in kernel-based classiﬁers, to provide a theoretically-sound countermeasure for linear classiﬁers against evasion attacks [46, 71].”
Adversarial Training and Robustness for Multiple Perturbations (2019, neutral): “[43], Demontis et al.”
Using Machine Teaching to Identify Optimal Training-Set Attacks on Machine Learners (2015, background): “Promising as the name suggests, we point out that robust learning is not an appropriate defense against training-set attacks.”
Provable defenses against adversarial examples via the convex outer adversarial polytope (2017, methodology): “Indeed, robust optimization techniques have been used in the context of linear machine learning models (Xu et al., 2009) to create classifiers that are robust to perturbations of the input.”
Certifying Some Distributional Robustness with Principled Adversarial Training (2017, background): “Unfortunately, this approach is intractable except for specially structured losses, such as the composition of a linear and simple convex function (Ben-Tal et al., 2009; Xu et al., 2009; 2012).”
Analysis of classifiers’ robustness to adversarial perturbations (2015, background): “These works specifically study attacks that manipulate the learning system (e.g., change the decision function by injecting malicious training points), as well as defense strategies to counter these attacks.”
Adversarial Vulnerability of Neural Networks Increases With Input Dimension (2018, background): “…the gradient regularized objective (4) is essentially the ﬁrst-order approximation of the robust training objective max (cid:107) δ (cid:107)≤ L ( x + δ , c ) which has a long history in math (Wald, 1945), machine learning (Xu et al., 2009) and now adversarial vulnerability (Sinha et al., 2018).”
Is Deep Learning Safe for Robot Vision? Adversarial Examples Against the iCub Humanoid (2017, background): “In this respect, it would be interesting to investigate more in detail the intimate connections between robustness to adversarial input noise and regularization, as highlighted in [29, 22].”
Yes, Machine Learning Can Be More Secure! A Case Study on Android Malware Detection (2017, background): “[46] have shown that the regularization term depends on the kind of hypothesized noise over the input data.”
On Security and Sparsity of Linear Classifiers for Adversarial Settings (2016, background): “In particular, Xu et al. [13] have considered the following robust optimization problem: where ( z ) , and the so-called uncertainty set U is deﬁned as Typical examples of uncertainty sets according to the above deﬁnition include (cid:96) 1 and (cid:96) 2 balls [13,14].”
Learning kernel logistic regression in the presence of class label noise (2014, background): “by finding a way to express the label-robust objective in terms of some regularised objective as it has been done for SVM under feature noise [43].”
Adversarially Robust Generalization Requires More Data (2018, background): “[58] establishes a connection between robust optimization and regularization for linear classification.”
Robustness of classifiers: from adversarial to random noise (2016, methodology): “The robustness properties of SVM classifiers have been studied in [19] for example, and robust optimization approaches for constructing robust classifiers have been proposed to minimize the worst possible empirical error under noise disturbance [1, 10].”
Robustness and generalization (2010, methodology): “Indeed, Xu et al. (2009a, 2010b) showed that this reformulation implies that the loss of a sample “close” to zi is small, which further implies statistical consistency of these two algorithms.”
Analysis of universal adversarial perturbations (2017, background): “, [3]) and new approaches for constructing robust classifiers (based on robust optimization) have been proposed [4], [5].”
Pattern Recognition Systems under Attack: Design Issues and Research Challenges (2014, background): “This suggest to investigate the connections between secure learning techniques and classifier regularization, by formally characterizing adversarial noise, following the intuition in [72] related to SVMs and noise-based classifier regularization (see also [56] for an example).”
Robust Classification (2019, methodology): “…more recently, it has been shown that a robust optimization formulation of the maximum margin classifier is equivalent to the classical SVM; thus, methods derived as robust variations to classical SVM are “doublecounting” the effect of robustness (Xu et al. 2009, Bertsimas and Copenhaver 2017).”
Age and Gender Estimation of Unfiltered Faces (2014, background): “Others propose the use of more robust optimization procedures [70].”
Theory and Applications of Robust Optimization (2010, methodology): “Using this equivalence, they re-prove that Lasso is sparse using a new robust optimization-based explanation of this sparsity phenomenon, thus showing that sparsity is a consequence of robustness. In [131], the authors consider robust Support Vector Machines (SVM) and show that like Lasso and Tikhon”
Rademacher Complexity for Adversarially Robust Generalization (2018, methodology): “In earlier work, robust optimization has been studied in Lasso [56] and SVM [57] problems.”