Adversarially Robust Learning with Tolerance

Several empirical studies (Szegedy et al., 2014; Goodfellow et al., 2018) have demonstrated that models trained to have a low accuracy on a data set often have the undesirable property that a small perturbation to an input instance can change the label outputted by the model. For most domains this does not align with human perception and thus indicates that the learned models are not representing the ground truth despite obtaining good accuracy on test sets.

The theory of PAC-learning characterizes the conditions under which learning is possible. For binary classification, the following conditions are sufficient: a) unseen data should arrive from the same distribution as training data, and b) the class of models should have a low capacity (as measured, for example, by its VC-dimension). If these conditions are met, an Empirical Risk Minimizer (ERM) that simply optimizes model parameters to maximize accuracy on the training set learns successfully.

Recent work has studied test-time adversarial perturbations under the PAC-learning framework. If an adversary is allowed to perturb data during test time then the conditions above do not hold, and we cannot hope for the model to learn to be robust just by running ERM. Thus, the goal here is to bias the learning process towards finding models where label-changing perturbations are rare. This is achieved by defining a loss function that combines both classification error and the probability of seeing label-changing perturbations, and learning models that minimize this loss on unseen data. It has been shown that even though (robust) ERM can fail in this setting, PAC-learning is still possible as long as we know during training the kinds of perturbations we want to guard against at test time (Montasser et al., 2019). This result holds for all perturbation sets. However, the learning algorithm is significantly more complex than robust ERM and requires a large number of samples (with the best known sample complexity bounds potentially being exponential in the VC-dimension).

We study a tolerant version of the adversarially robust learning framework and restrict the perturbations to balls in a general metric space with finite doubling dimension. We show this slight shift in the learning objective yields significantly improved sample complexity bounds through a simpler learning paradigm than what was previously known. In fact, we show that a version of the common “perturb-and-smooth” paradigm successfully PAC-learns any class of bounded VC-dimension in this setting.

Learning in general metric spaces. What kinds of perturbations should a learning algorithm guard against? Any transformation of the input that we believe should not change its label could be a viable perturbation for the adversary to use. The early works in this area considered perturbations contained within a small $\ell_{p}$-ball of the input. More recent work has considered other transformations such as a small rotation, or translation of an input image (Engstrom et al., 2019; Fawzi and Frossard, 2015; Kanbak et al., 2018; Xiao et al., 2018), or even adding small amounts of fog or snow (Kang et al., 2019). It has also been argued that small perturbations in some feature space should be allowed as opposed to the input space (Inkawhich et al., 2019; Sabour et al., 2016; Xu et al., 2020; Song et al., 2018; Hosseini and Poovendran, 2018). This motivates the study of more general perturbations.

We consider a setting where the input comes from a domain that is equipped with a distance metric and allows perturbations to be within a small metric ball around the input. Earlier work on general perturbation sets (for example, (Montasser et al., 2019)) considered arbitrary perturbations. In this setting one does not quantify the magnitude of a perturbation and thus cannot talk about small versus large perturbations. Modeling perturbations using a metric space enables us to do that while also keeping the setup general enough to be able to encode a large variety of perturbation sets by choosing appropriate distance functions.

Learning with tolerance. In practice, we often believe that small perturbations of the input should not change its label but we do not know precisely what small means. However, in the PAC-learning framework for adversarially robust classification, we are required to define a precise perturbation set and learn a model that has error arbitrarily close to the smallest error that can be achieved with respect to that perturbation set. In other words, we aim to be arbitrarily close to a target that was picked somewhat arbitrarily to begin with. Due to the uncertainty about the correct perturbation size, it is more meaningful to allow for a wider range of error values. To achieve this, we introduce the concept of tolerance. In the tolerant setting, in addition to specifying a perturbation size $r$, we introduce a tolerance parameter $\gamma$ that encodes our uncertainty about the size of allowed perturbations. Then, for any given $\varepsilon>0$, we aim to learn a model whose error with respect to perturbations of size $r$ is at most $\varepsilon$ more than the smallest error achievable with respect to perturbations of size $r(1+\gamma)$.

In this paper we formalize and initiate the study of the problem of adversarially robust learning in the tolerant setting for general metric spaces and provide two algorithms for the task. Both of our algorithms rely on: 1) modifying the training data by randomly sampling points from the perturbation sets around each data point, and 2) smoothing the output of the model by taking a majority over the labels returned by the model for nearby points.

Our first algorithm starts by modifying the training set by randomly perturbing each training point using a certain distribution (see Section 5 for details). It then trains a (non-robust) PAC-learner (such as ERM) on the perturbed training set to find a hypothesis $h$. Finally, it outputs a smooth version of $h$. The smoothing step replaces $h(x)$ at each point $x$ with the a majority label outputted by $h$ on the points around $x$. We show that for metric spaces of a fixed doubling dimension, this algorithm successfully learns in the tolerant setting assuming tolerant realizability.

An interesting feature of the above result is the linear dependence of the sample complexity with respect to $\mathrm{VC}(\mathcal{H})$. This is in contrast to the best known upper bound for non-tolerant adversarial setting  (Montasser et al., 2019) which depends on the dual VC-dimension of the hypothesis class and in general is exponential in $\mathrm{VC}(\mathcal{H})$. Moreover, this is the first PAC-type guarantee for the general perturb-and-smooth paradigm, indicating that the tolerant adversarial learning is the “right” learning model for studying these approaches. While the above method enjoys simplicity and can be computationally efficient, one downside is that its sample complexity grows exponentially with the doubling dimension. For instance, such algorithm cannot be used on high-dimensional data in the Euclidean space. Another limitation is that the guarantee holds only in the (robustly) realizable setting.

In the second main part of our submission (Section 6) we show that, surprisingly, these limitations can be overcome by incorporating ideas from the tolerant framework and perturb-and-smooth algorithms into a novel compression scheme for robust learning. The resulting algorithm improves the dependence on the doubling dimension, and works in the general agnostic setting.

This algorithm exploits the connection between sample compression and adversarially robust learning Montasser et al. (2019). However, unlike Montasser et al. (2019), our new compression scheme sidesteps the dependence on the dual VC-dimension (refer to the discussion at the end of Section 6 for more details). As a result, we get an exponential improvement over the best known (nontolerant) sample complexity in terms of dependence on VC-dimension.

PAC-learning for adversarially robust classification has been studied extensively in recent years (Cullina et al., 2018; Awasthi et al., 2019; Montasser et al., 2019; Feige et al., 2015; Attias et al., 2019; Montasser et al., 2020a; Ashtiani et al., 2020). These works provide learning algorithms that guarantee low generalization error in the presence of adversarial perturbations in various settings. The most general result is due to Montasser et al. (2019), and is proved for general hypothesis classes and perturbation sets. All of the above results assume that the learner knows the kinds of perturbations allowed for the adversary. Some more recent papers have considered scenarios where the learner does not even need to know that. Goldwasser et al. (2020) allow the adversary to perturb test data in unrestricted ways and are still able to provide learning guarantees. The catch is that it only works in the transductive setting and only if the learner is allowed to abstain from making a prediction on some test points. Montasser et al. (2021a) consider the case where the learner needs to infer the set of allowed perturbations by observing the actions of the adversary.

Tolerance was introduced by Ashtiani et al. (2020) in the context of certification. They provide examples where certification is not possible unless we allow some tolerance. Montasser et al. (2021b) study transductive adversarial learning and provide a “tolerant” guarantee. Note that unlike our work, the main focus of that paper is on the transductive setting. Moreover, they do not specifically study tolerance with respect to metric perturbation sets. Without a metric, it is not meaningful to expand perturbation sets by a factor $(1+\gamma)$ (as we do in the our definition of tolerance). Instead, they expand their perturbation sets by applying two perturbations in succession, which is akin to setting $\gamma=1$. In contrast, our results hold in the more common inductive setting, and capture a more realistic setting where $\gamma$ can be any (small) real number larger than zero.

Subsequent to our work, Bhattacharjee et al. (2022) study adversarially robust learning with tolerance for “regular” VC-classes and show that a simple modification of robust ERM achieves a sample complexity polynomial in both VC-dimension and doubling dimension. In a similar vein, Raman et al. (2022) identify a more general property of hypothesis classes for which robust ERM is sufficient for adversarially robust learning with tolerance.

Like many recent adversarially robust learning algorithms (Feige et al., 2015; Attias et al., 2019), our first algorithm relies on calls to a non-robust PAC-learner. Montasser et al. (2020b) formalize the question of reducing adversarially robust learning to non-robust learning and study finite perturbation sets of size $k$. They show a reduction that makes $O(\log^{2}{k})$ calls to the non-robust learner and also prove a lower bound of $\Omega(\log{k})$. It will be interesting to see if our algorithms can be used to obtain better bounds for the tolerant setting. Our first algorithm makes one call to the non-robust PAC-learner at training time, but needs to perform potentially expensive smoothing for making actual predictions (see Theorem 5.2).

A related line of work studies smallest achievable robust loss for various distributions and hypothesis classes. For example,  Bubeck and Sellke (2021) show that hypothesis classes with low robust loss must be overparametrized. Yang et al. (2020b) explore real-world datasets and provide evidence that they are separable and therefore there must exist locally Lipschitz hypotheses with low robust loss. Note that the existence of such hypotheses does not immediately imply that PAC-learning is possible.

The techniques of randomly perturbing the training data and smoothing the output classifier has been extensively used in practice and has shown good empirical success. Augmenting the training data with some randomly perturbed samples was used for handwriting recognition as early as by  Yaeger et al. (1996). More recently, “stability training” was introduced by Zheng et al. (2016) for state of the art image classifiers where training data is augmented with Gaussian perturbations. Empirical evidence was provided that the technique improved the accuracy against naturally occurring perturbations. Augmentations with non-Gaussian perturbations of a large variety were considered by Hendrycks et al. (2019).

Smoothing the output classifier using random samples around the test point is a popular technique for producing certifiably robust classifiers. A certification, in this context, is a guarantee that given a test point $x$, all points within a certain radius of $x$ receive the same label as $x$. Several papers have provided theoretical analyses to show that smoothing produces certifiably robust classifiers (Cao and Gong, 2017; Cohen et al., 2019; Lecuyer et al., 2019; Li et al., 2019; Liu et al., 2018; Salman et al., 2019; Levine and Feizi, 2020), whereas others have identified cases where smoothing does not work Yang et al. (2020a); Blum et al. (2020).

However, to the best of our knowledge, a PAC-type guarantee has not been shown for any algorithm that employs training data perturbations or output classifier smoothing, and our paper provides the first such analysis.

We denote by $X$ the input domain and by $Y=\{0,1\}$ the binary label space. We assume that $X$ is equipped with a metric $\mathrm{dist}$. A hypothesis $h:X\to Y$ is a function that assigns a label to each point in the domain. A hypothesis class ${\mathcal{H}}$ is a set of such hypotheses. For a sample $S=((x_{1},y_{1}),\ldots,(x_{n},y_{n}))\in(X\times Y)^{n}$, we use the notation $S^{X}=\{x_{1},x_{2},\ldots,x_{n}\}$ to denote the collection of domain points $x_{i}$ occurring in $S$. The binary (also called 0-1) loss of $h$ on data point $(x,y)\in X\times Y$ is defined by

where $\mathds{1}\left[{.}\right]$ is the indicator function. Let $P$ by a probability distribution over $X\times Y$. Then the expected binary loss of $h$ with respect to $P$ is defined by

Similarly, the empirical binary loss of $h$ on sample $S=((x_{1},y_{1}),\ldots,(x_{n},y_{n}))\in(X\times Y)^{n}$ is defined as ${\mathcal{L}^{0/1}_{S}}(h)=\frac{1}{n}\sum_{i=1}^{n}\ell^{0/1}(h,x_{i},y_{i})$. We also define the approximation error of $\mathcal{H}$ with respect to $P$ as ${\mathcal{L}^{0/1}_{P}}(\mathcal{H})=\inf_{h\in\mathcal{H}}{\mathcal{L}^{0/1}_{P}}(h)$.

A learner ${\mathcal{A}}$ is a function that takes in a finite sequence of labeled instances $S=((x_{1},y_{1}),\ldots,(x_{n},y_{n}))$ and outputs a hypothesis $h={\mathcal{A}}(S)$. The following definition abstracts the notion of PAC-learning Vapnik and Chervonenkis (1971); Valiant (1984).

The smallest function $m:(0,1)^{2}\to\mathbb{N}$ for which there exists a learner ${\mathcal{A}}$ that satisfies the above definition with $m_{{\mathcal{A}}}=m$ is referred to as the (realizable or agnostic) sample complexity of learning $\mathcal{H}$.

The existence of sample-efficient PAC-learners for VC classes is a standard result Vapnik and Chervonenkis (1971). We state the results formally in Appendix A.

In this section we focus on tolerant adversarial PAC-learning in metric spaces (Definition 4.3), and show that VC classes are tolerantly PAC-learnable in the tolerantly realizable setting. Interestingly, we prove this result using an approach that resembles the “perturb-and-smooth” paradigm which is used in practice (for example by Cohen et al. (2019)). The overall idea is to “perturb” each training point $x$, train a classifier on the “perturbed” points, and “smooth out” the final hypothesis using a certain majority rule.

We employ three perturbation types: $\mathcal{U}$ and $\mathcal{V}$ play the role of the actual and the reference perturbation type respectively. Additionally, we consider a perturbation type $\mathcal{W}:X\to 2^{X}$, which is used for smoothing. We assume $\mathcal{U}\prec\mathcal{V}$ and $\mathcal{W}\prec\mathcal{V}$. For this section, we will use metric balls for the three types. Specifically, if $\mathcal{U}$ consists of balls of radius $r$ for some $r>0$, then $\mathcal{W}$ will consists of balls of radius $\gamma r$ and $\mathcal{V}$ will consist of balls of radius $(1+\gamma)r$.

The perturb-and-smooth approach discussed in the previous section offers a general method for tolerant robust learning. However, one shortcoming of this approach is the exponential dependence of its sample complexity with respect to the doubling dimension of the metric space. Furthermore, the tolerant robust guarantee relied on the data generating distribution being tolerantly realizable. In this section, we propose another approach that addresses both of these issues. The idea is to adopt the perturb-and-smooth approach within a sample compression argument. We introduce the notion of a $(\mathcal{U},\mathcal{V})$-tolerant sample compression scheme and present a learning bound based on such a compression scheme, starting with the realizable case. We then show that this implies learnability in the agnostic case as well. Remarkably, this tolerant compression based analysis will yield bounds on the sample complexity that avoid the exponential dependence on the doubling dimension.

For a compact representation, we will use the general notation $\mathcal{U},\mathcal{V},$ and $\mathcal{W}$ for the three perturbation types (actual, reference and smoothing type) in this section and will assume that they satisfy the Property 1 below for some parameter $\beta>0$. Lemma 5.3 implies that, in the metric setting, for any radius $r$ and tolerance parameter $\gamma$ the perturbation types $\mathcal{U}={\mathcal{B}}_{r}$, $\mathcal{V}={\mathcal{B}}_{(1+\gamma)r}$, and $\mathcal{W}={\mathcal{B}}_{\gamma r}$ have this property for $\beta=\frac{1}{3}\left(\frac{1+\gamma}{\gamma}\right)^{-\zeta d}$.

A compression scheme of size $k$ is a pair of functions $(\kappa,\rho)$, where the compression function $\kappa:\bigcup_{i=1}^{\infty}(X\times Y)^{i}\to\bigcup_{i=1}^{k}(X\times Y)^{i}$ maps samples $S=((x_{1},y_{1}),(x_{2},y_{2}),\ldots,(x_{m},y_{m}))$ of arbitrary size to sub-samples of $S$ of size at most $k$, and $\rho:\bigcup_{i=1}^{k}(X\times Y)^{i}\to Y^{X}$ is a decompression function that maps samples to classifiers. The pair $(\kappa,\rho)$ is a sample compression scheme for loss $\ell$ and class ${\mathcal{H}}$, if for any samples $S$ realizable by ${\mathcal{H}}$, we recover the correct labels for all $(x,y)\in S$, that is, ${\mathcal{L}_{S}}(H)=0$ implies that ${\mathcal{L}_{S}}(\kappa\circ\rho(S))=0$.

For tolerant learning, we introduce the following generalization of compression schemes:

The next lemma establishes that the existence of a sufficiently small tolerant compression scheme for the class ${\mathcal{H}}$ yields bounds on the sample complexity of tolerantly learning ${\mathcal{H}}$. The proof of the lemma is based on a modification of a standard compression based generalization bound. Appendix Section D provides more details.

We next establish a bound on the tolerant compression size for general VC-classes, which will then immediately yield the improved sample complexity bounds for tolerant learning in the realizable case. The proof is sketched here; its full version has been moved to the Appendix.

This yields the following result

In particular, for the doubling measure scenario (as considered in the previous section), we obtain