Robustness and generalization

By Huan Xu, Shie Mannor. 2010

504 citations recorded by the source corpus.

We derive generalization bounds for learning algorithms based on their robustness: the property that if a testing sample is “similar” to a training sample, then the testing error is close to the training error. This provides a novel approach, different from complexity or stability arguments, to study generalization of learning algorithms. One advantage of the robustness approach, compared to previous methods, is the geometric intuition it conveys. Consequently, robustness-based analysis is easy to extend to learning in non-standard setups such as Markovian samples or quantile loss. We further show that a weak notion of robustness is both sufficient and necessary for generalizability, which implies that robustness is a fundamental property that is required for learning algorithms to work.

Subfields: Control and Systems Engineering, Statistics and Probability, Safety, Robustness & Interpretability, 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 Statistics and Probability

In Safety, Robustness & Interpretability

In Statistical Learning Theory

Citations in the corpus

Parseval Networks: Improving Robustness to Adversarial Examples (2017, methodology): “In the robustness framework of (Xu & Mannor, 2012), the Lipschitz constant also controls the difference between the average loss on the training set and the generalization performance.”
Robust Large Margin Deep Neural Networks (2016, methodology): “In order to provide bounds to the GE for DNN classifiers we leverage the robustness framework [32], which is described next.”
On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning (2022, background): “Starting from the first studies focusing on this simple dichotomy, the Lipschitz constant L of a DNN has been established as a commonplace measure of both smoothness and generalization [82, 72, 39] and still constitutes a key ingredient for current evaluations of model capacity [8, 30].”
Measuring Neural Net Robustness with Constraints (2016, background): “o been work using smoothness regularization related to [5] to train neural nets, focusing on improving accuracy rather than robustness [14]. Robustness has also been studied in more general contexts; [23] studies the connection between robustness and generalization, [2] establishes theoretical lower”
Robustness May Be at Odds with Accuracy (2018, background): “Xu & Mannor (2012) explore the connection between robustness and generalization, showing that, in a certain sense, robustness can imply generalization.”
Adversarially Robust Generalization Requires More Data (2018, background): “• The work of Xu, Caramanis, and Mannor [56] establishes a connection between robust optimization and regularization for linear classification.”
Exploring Generalization in Deep Learning (2017, methodology): “Another related approach is through algorithmic robustness as suggested by Xu and Mannor [28].”
Generalization in Deep Learning (2017, background): “For example, if algorithm A is (Ω, (∙))-robust and the codomain of ` is upper-bounded by M , given a dataset Sm, we have (Xu and Mannor, 2012) that for any δ > 0, with probability at least 1 − δ,”
SMART: Robust and Efficient Fine-Tuning for Pre-trained Natural Language Models through Principled Regularized Optimization (2019, background): “Existing literature has shown that the adversarial training has a regularization effect, which can improve generalization in supervise learning tasks (Xu and Mannor, 2012).”
FreeLB: Enhanced Adversarial Training for Natural Language Understanding (2019, positive): “In theory, such improved robustness can lead to better generalization (Xu & Mannor, 2012), which is consistent with our experiments.”
A Survey on Metric Learning for Feature Vectors and Structured Data (2013, background): “Bellet and Habrard (2012) demonstrate how to adapt the more flexible notion of algorithmic robustness (Xu and Mannor, 2012) to the metric learning setting to derive (loose) generalization bounds for any matrix norm (including sparsity-inducing ones) as regularizer.”
SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Data (2017, methodology): “More recent works, study alternative notions of complexity, such as Rademacher compexity (Bartlett & Mendelson, 2002; Neyshabur et al., 2015; Bartlett et al., 2017; Kawaguchi et al., 2017), Robustness (Xu & Mannor, 2012) and PAC-Bayes (Neyshabur et al., 2017b).”
Frequency Principle: Fourier Analysis Sheds Light on Deep Neural Networks (2019, background): “L G ] 28 M a r 2019 Mannor, 2012; Hardt et al., 2015), and implicit bias of the training process (Neyshabur et al., 2014; Poggio et al., 2018; Soudry et al., 2018; Arpit et al., 2017; Xu et al., 2018).”
L2-Nonexpansive Neural Networks (2018, background): “These issues bring up both theoretical questions of how neural networks generalize (Kawaguchi et al., 2017; Xu & Mannor, 2012) and practical concerns of security in applications (Akhtar & Mian, 2018).”
Robust twin support vector machine for pattern classification (2013, background): “Simultaneously we does not need to solve the extra inverse of matrices, which is totally different with existing TWSVMs.”
Learning under p-Tampering Attacks (2018, background): “The robustness of a learner [21, 43, 45] refers to its behavior when the test test are close, but not necessarily drawn from the same distribution.”
Action Robust Reinforcement Learning and Applications in Continuous Control (2019, background): “Additionally, a connection between robustness and generalization has been suggested (Xu et al., 2009; Xu & Mannor, 2012), while it is not clear how this holds in RL, we believe that there lies a similar yet complex connection between the two concepts.”
Deformed Graph Laplacian for Semisupervised Learning (2015, background): “Suppose all the examples are i.i.d, and are generated from an unknown distribution P , then the above two errors are deﬁned by Theorem 4 (Generalization Bound [17]): If the training set consists of n i.i.d. samples, and the algorithm A is (θ, ε((cid:2))) -robust, then for any δ > 0, with probability”
Trustworthy AI: From Principles to Practices (2021, unknown): “As demonstrated in Reference [362], an algorithm that is robust against small perturbations has better generalization.”