VC Classes are Adversarially Robustly Learnable, but Only Improperly

Introduction

Learning predictors that are robust to adversarial perturbations is an important challenge in contemporary machine learning. There has been a lot of interest lately in how predictors learned by deep learning are not robust to adversarial examples (Szegedy et al., 2013; Biggio et al., 2013; Goodfellow et al., 2014), and there is an ongoing effort to devise methods for learning predictors that are adversarially robust. In this paper, we consider the problem of learning, based on a (non-adversarial) i.i.d. sample, a predictor that is robust to adversarial examples at test time. We emphasize that this is distinct from the learning process itself being robust to an adversarial training set.

The common approach to adversarially robust learning is to pick a hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ (e.g. neural networks) and learn through robust empirical risk minimization:

$\hat{h}\in{\rm RERM}_{\mathcal{H}}(S):=\mathop{\rm argmin}\limits_{h\in\mathcal{H}}\hat{{\rm R}}_{\mathcal{U}}(h;S)$

How can we ensure that ${\rm R}_{\mathcal{U}}(h;\mathcal{D})$ is small? All prior approaches that we are aware of for ensuring adversarially robust generalization are based on uniform convergence, i.e. showing that w.h.p. for all predictors $h\in\mathcal{H}$, the estimation error $\lvert{\rm R}_{\mathcal{U}}(h;\mathcal{D})-\hat{{\rm R}}_{\mathcal{U}}(h;S)\rvert$ is small, perhaps for some surrogate loss (Bubeck et al., 2018; Cullina et al., 2018; Khim and Loh, 2018; Yin et al., 2018). Such approaches justify ${\rm RERM}$, and in particular yield M-estimation type proper learning rules: we are learning a hypothesis class by choosing a predictor in the class that minimizes some empirical functional. For standard supervised learning we know that proper learning, and specifically ${\rm ERM}$, is sufficient for learning, and so it is sensible to limit attention to such methods.

But it has also been observed in practice that the adversarial error does not generalize as well as the standard error, i.e. there can be a large gap between ${\rm R}_{\mathcal{U}}(h;\mathcal{D})$ and $\hat{{\rm R}}_{\mathcal{U}}(h;S)$ even when their non-robust versions are similar (Schmidt et al., 2018). This suggests that perhaps the robust risk does not concentrate as well as the standard risk, and so RERM in adversarially robust learning might not work as well as ERM in standard supervised learning. Does this mean that such problems are not adversarially robustly learnable? Or is it perhaps that proper learners might not be sufficient?

In this paper we aim to characterize which hypothesis classes are adversarially robustly learnable, and using what learning rules. That is, for a given hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ and adversary $\mathcal{U}$, we ask whether it is possible, based on an i.i.d. sample to learn a predictor $h$ that has population robust risk almost as good as any predictor in $\mathcal{H}$ (see Definition 2.1 in Section 2). We discover a stark contrast between proper learning rules which output predictors in $\mathcal{H}$, and improper learning rules which are not constrained to predictors in $\mathcal{H}$. Our main results are:

We show that there exists an adversary $\mathcal{U}$ and a hypothesis class $\mathcal{H}$ with finite VC dimension that cannot be robustly PAC learned with any proper learning rule (including ${\rm RERM}$).

We show that for any adversary $\mathcal{U}$ and any hypothesis class $\mathcal{H}$ with finite VC dimension, there exists an improper learning rule that can robustly PAC learn $\mathcal{H}$ (although with sample complexity that is sometimes exponential in the VC dimension).

Our results suggest that we should start considering improper learning rules to ensure adversarially robust generalization. They also demonstrate that previous approaches to adversarially robust generalization are not always sufficient, as all prior work we are aware of is based on uniform convergence of the robust risk, either directly for the loss of interest (Bubeck et al., 2018; Cullina et al., 2018) or some carefully constructed surrogate loss (Khim and Loh, 2018; Yin et al., 2018), which would still justify the use of M-estimation type proper learning. The approach of Attias et al. (2018) for the case where $|\mathcal{U}(x)|\leq k$ (i.e. finite number of perturbations) is most similar to ours, as it uses an improper learning rule, but their analysis is still based on uniform convergence and so would apply also to ${\rm RERM}$ (the improperness is introduced only for computational, not statistical, reasons). Also, in this specific case, our approach would give an improved sample complexity that scales only roughly logarithmically with $k$, as opposed to the roughly linear scaling in Attias et al. (2018)—see discussion at the end of Section 4 for details.

A related negative result was presented by Schmidt et al. (2018), where they showed that there exists a family of distributions (namely, mixtures of two $d$-dimensional spherical Gaussians) where the sample complexity for standard learning is $O(1)$, but the sample complexity for adversarially robust learning is at least $\Omega(\frac{\sqrt{d}}{\log d})$. This an interesting instance where there is a large separation in sample complexity between standard learning and robust learning. But distribution-specific learning is known to be less easily characterizable, with the uniform convergence not being necessary for learning, and ERM not always being optimal, even for standard (non-robust) supervised learning. In this paper we focus on “worst case” distribution-free robust learning, as in standard PAC learnability.

A different notion of robust learning was studied by Xu and Mannor (2012). They use empirical robustness as a design technique for learning rules, but their goal, and the guarantees they establish are on the standard non-robust population risk, and so do not inform us about robust learnability.

Problem Setup

${\rm R}_{\mathcal{U}}(\mathcal{A}(S);\mathcal{D})\leq\inf\limits_{h\in\mathcal{H}}{\rm R}_{\mathcal{U}}(h;\mathcal{D})+\varepsilon$.

If no such $m$ exists, define $\mathcal{M}_{{\rm AG}}(\varepsilon,\delta;\mathcal{H},\mathcal{U})=\infty$. We say that $\mathcal{H}$ is robustly PAC learnable in the agnostic setting with respect to adversary $\mathcal{U}$ if $\forall\varepsilon,\delta\in(0,1)$, $\mathcal{M}_{{\rm AG}}(\varepsilon,\delta;\mathcal{H},\mathcal{U})$ is finite.

${\rm R}_{\mathcal{U}}(\mathcal{A}(S);\mathcal{D})\leq\varepsilon$.

If no such $m$ exists, define $\mathcal{M}_{{\rm RE}}(\varepsilon,\delta;\mathcal{H},\mathcal{U}))=\infty$. We say that $\mathcal{H}$ is robustly PAC learnable in the realizable setting with respect to adversary $\mathcal{U}$ if $\forall\varepsilon,\delta\in(0,1)$, $\mathcal{M}_{{\rm RE}}(\varepsilon,\delta;\mathcal{H},\mathcal{U})$ is finite.

We say that $\mathcal{H}$ is properly robustly PAC learnable (in the agnostic or realizable setting) if it can be learned as in Definitions 2.1 or 2.2 using a learning rule $\mathcal{A}:(\mathcal{X}\times\mathcal{Y})^{*}\mapsto\mathcal{H}$ that always outputs a predictor in $\mathcal{H}$. We refer to learning using any learning rule $\mathcal{A}:(\mathcal{X}\times\mathcal{Y})^{*}\mapsto\mathcal{Y}^{\mathcal{X}}$, as in the definitions above, as improper learning.

We say that a sequence $\{x_{1},\dots,x_{k}\}\in\mathcal{X}$ is shattered by $\mathcal{H}$ if $\forall y_{1},\dots,y_{k}\in\mathcal{Y},\exists h\in\mathcal{H}$ such that $\forall i\in[k],h(x_{i})=y_{i}$. The VC dimension of $\mathcal{H}$ (denoted ${\rm vc}(\mathcal{H})$) is then defined as the largest integer $k$ for which there exists $\{x_{1},\dots,x_{k}\}\in\mathcal{X}$ that is shattered by $\mathcal{H}$. If no such $k$ exists, then ${\rm vc}(\mathcal{H})$ is said to be infinite.

In the standard PAC learning framework, we know that a hypothesis class $\mathcal{H}$ is PAC learnable if and only if the VC dimension of $\mathcal{H}$ is finite (Vapnik and Chervonenkis, 1971, 1974; Blumer et al., 1989; Ehrenfeucht et al., 1989). In particular, $\mathcal{H}$ is properly PAC learnable with ${\rm ERM}_{\mathcal{H}}$ and therefore proper learning is sufficient for supervised learning. A natural question to ask, based on the definition of robust PAC learning, is what is a necessary and sufficient condition on $\mathcal{H}$ that implies that it is robustly PAC learnable with respect to adversary $\mathcal{U}$. We can easily obtain a sufficient condition based on Vapink’s “General Learning” (Vapnik, 1982). Denote by $\mathcal{L}^{\mathcal{U}}_{\mathcal{H}}$ the robust loss class of $\mathcal{H}$,

If the robust loss class $\mathcal{L}_{\mathcal{H}}^{\mathcal{U}}$ has finite VC dimension (${\rm vc}(\mathcal{L}_{\mathcal{H}}^{\mathcal{U}})<\infty$), then $\mathcal{H}$ is robustly PAC learnable with ${\rm RERM}_{\mathcal{H}}$ and sample complexity that scales linearly with ${\rm vc}(\mathcal{L}_{\mathcal{H}}^{\mathcal{U}})$. One might then wish to relate the VC dimension of the hypothesis class (${\rm vc}(\mathcal{H})$) to the VC dimension of the robust loss class (${\rm vc}(\mathcal{L}_{\mathcal{H}}^{\mathcal{U}})$). But as we show in Sections 3 and 5, there can be arbitrarily large gaps between them.

As mentioned earlier, for supervised learning finite VC dimension of the loss class (which is equal to the VC dimension of the hypothesis class) is also necessary for learning. For general learning, unlike supervised learning, the loss class having finite VC dimension, and uniform convergence over this class, is not, in general, necessary, and rules other than ${\rm ERM}$ might be needed for learning (e.g. Vapnik, 1982; Shalev-Shwartz et al., 2009; Daniely et al., 2015). In the following Sections, we show that this is also the case for robust learning. We show that ${\rm vc}(\mathcal{L}_{\mathcal{H}}^{\mathcal{U}})$ can be arbitrarily larger, we might not have uniform convergence, ${\rm RERM}$ might not ensure learning, while the problem is still learnable with a different (improper, in our case) learning rule.

Sometimes There are no Proper Robust Learners

We start by showing that even for hypothesis classes with finite VC dimension, indeed even if ${\rm vc}(\mathcal{H})=1$, robust PAC learning might not be possible using any proper learning rule. In particular, even if there is a robust predictor in $\mathcal{H}$, and even with an unbounded number of samples, ${\rm RERM}$ (or any other M-estimator or other proper learning rules), will not ensure a low robust risk.

There exists a hypothesis class $\mathcal{H}\subseteq\mathcal{Y}^{\mathcal{X}}$ with ${\rm vc}(\mathcal{H})\leq 1$ and an adversary $\mathcal{U}$ such that $\mathcal{H}$ is not properly robustly PAC learnable with respect to $\mathcal{U}$ in the realizable setting.

Pick $m$ points $x_{1},\dots,x_{m}$ in $\mathcal{X}$ such that for all $i,j\in[m],\mathcal{U}(x_{i})\cap\mathcal{U}(x_{j})=\emptyset$. In other words, we want the perturbation sets $\mathcal{U}(x_{1}),\dots,\mathcal{U}(x_{m})$ to be mutually disjoint.

We will construct a hypothesis class $\mathcal{H}$ in the following iterative manner. Initialize set $\mathcal{Z}=\{x_{1},\dots,x_{m}\}$. For each bit string $b\in\{0,1\}^{m}$, initialize $Z_{b}=\emptyset$. For each $i\in[m]$, if $b_{i}=1$ then pick a point $z\in\mathcal{U}(x_{i})\setminus\mathcal{Z}$ and add it to $Z_{b}$, i.e. $Z_{b}=Z_{b}\cup\{z\}$. Once we finish picking points based on all bits that are set to $1$, we add $Z_{b}$ to $\mathcal{Z}$ (i.e. $\mathcal{Z}=\mathcal{Z}\cup Z_{b}$). We define $h_{b}:\mathcal{X}\rightarrow\mathcal{Y}$ as:

h_{b}(x)=\left\{\begin{array}[]{ll}+1&\text{if }x\notin Z_{b}\\ -1&\text{if }x\in Z_{b}\end{array}\right.

Then, let $\mathcal{H}=\{h_{b}:b\in\{0,1\}^{m}\}$. We can think of each mapping $h_{b}$ as being characterized by a unique signature $Z_{b}$ that indicates the points that it labels with $-1$. These points are carefully picked such that, first, they are inside the perturbation sets of $x_{1},\dots,x_{m}$; and second, no two mappings label the same point with $-1$, i.e. for any $b,b^{\prime}\in\{0,1\}^{m}$, where $b\neq b^{\prime}$, $Z_{b}\cap Z_{b}^{\prime}=\emptyset$. Also, we make sure that all mappings in $\mathcal{H}$ label the set $\{x_{1},\dots,x_{m}\}$ with $+1$.

Next, we proceed with proving two claims about $\mathcal{H}$. First, that ${\rm vc}(\mathcal{H})\leq 1$. Pick any two points $z_{1},z_{2}\in\mathcal{X}$. Consider the following cases. In case $z_{1}$ or $z_{2}$ is in $\mathcal{X}\setminus\mathcal{Z}$. Suppose W.L.O.G that $z_{2}\in\mathcal{X}\setminus\mathcal{Z}$. Then we know that all mappings label $z_{2}$ in the same way with label $+1$, because for all $b\in\{0,1\}^{m},z_{2}\notin Z_{b}$. Therefore, we cannot shatter $z_{1},z_{2}$ with $\mathcal{H}$. In case $z_{1}$ and $z_{2}$ are both in $\mathcal{Z}$. Since by our construction, $\mathcal{Z}=\cup_{b\in\{0,1\}^{m}}Z_{b}$ and $Z_{b}\cap Z_{b}^{\prime}=\emptyset$ for any $b\neq b^{\prime}$, we have two sub-cases. Either $z_{1},z_{2}\in Z_{b}$ for some $b\in\{0,1\}^{m}$, which means that the only labelings we can obtain are $(-1,-1)$ with $h_{b}$, and $(+1,+1)$ with $h_{b}^{\prime}$ for any $b^{\prime}\neq b$. Second case is that $z_{1}\in Z_{b}$ and $z_{2}\in Z_{b^{\prime}}$ for $b\neq b^{\prime},b,b^{\prime}\in\{0,1\}^{m}$. By our construction, we know that we cannot label both points $z_{1}$ and $z_{2}$ with $(-1,-1)$, because they don’t belong to the same set. Therefore, in both subcases, we cannot shatter $z_{1},z_{2}$ with $\mathcal{H}$. This concludes that ${\rm vc}{(\mathcal{H})}\leq 1$.

$\exists$ a distribution $\mathcal{D}$ over $\mathcal{X}\times\mathcal{Y}$ and a predictor $h^{*}\in\mathcal{H}$ where ${\rm R}_{\mathcal{U}}(h^{*};\mathcal{D})=0$.

With probability at least $1/7$ over $S\sim\mathcal{D}^{m}$, ${\rm R}_{\mathcal{U}}(\mathcal{A}(S);\mathcal{D})>1/8$.

We now proceed with the proof of Theorem 3.1.

h_{b}(x)=\left\{\begin{array}[]{ll}-1&\text{if }x\in Z_{b}\text{ or }x\in X_{m^{\prime}}\text{ for }m^{\prime}\neq m\\ +1&\text{otherwise }\end{array}\right.

Finite VC Dimension is Sufficient for (Improper) Robust Learnability

In the previous section we saw that finite VC dimension is not sufficient for proper robust learnability. We now show that it is sufficient for improper robust learnability, thus (1) establishing that if $\mathcal{H}$ is learnable, it is also robustly learnable, albeit possibly with a higher sample complexity; and (2) unlike the standard supervised learning setting, to achieve learnability we might need to escape properness, as improper learning is necessary for some hypothesis classes.

We begin, in Section 4.1 with the realizable case, i.e. where there exists $h^{*}\in\mathcal{H}$ with zero robust risk. Then in Section 4.2 we turn to the agnostic setting, and observe that a version of a recent reduction by David, Moran, and Yehudayoff (2016) from agnostic to realizable learning applies also for robust learning. We thus establish agnostic robust learnability of finite VC classes by using this reduction and relying on the realizable learning result of Section 4.1.

We will in fact establish a bound in terms of the dual VC dimension. Formally, for each $x\in\mathcal{X}$, define a function $g_{x}:\mathcal{H}\to\mathcal{Y}$ such that $g_{x}(h)=h(x)$ for each $h\in\mathcal{H}$. Then the dual VC dimension of $\mathcal{H}$, denoted ${\rm vc}^{*}(\mathcal{H})$, is defined as the VC dimension of the set ${\cal{G}}=\{g_{x}:x\in\mathcal{X}\}$. This quantity is known to satisfy ${\rm vc}^{*}(\mathcal{H})<2^{{\rm vc}(\mathcal{H})+1}$ (Assouad, 1983), though for many spaces it satisfies ${\rm vc}^{*}(\mathcal{H})=O({\rm poly}({\rm vc}(\mathcal{H})))$ or even, as is the case for linear separators, ${\rm vc}^{*}(\mathcal{H})=O({\rm vc}(\mathcal{H}))$.

For any $\mathcal{H}$ and $\mathcal{U}$, $\forall\varepsilon,\delta\in(0,1/2)$,

Since Assouad (1983) has shown ${\rm vc}^{*}(\mathcal{H})<2^{{\rm vc}(\mathcal{H})+1}$, this implies the following corollary.

For any $\mathcal{H}$ and $\mathcal{U}$, $\forall\varepsilon,\delta\in(0,1/2)$,

Our approach to this proof is via sample compression arguments. Specifically, we make use of a lemma (Lemma B.1 in Appendix 4.2), which extends to the robust loss the classic compression-based generalization guarantees from the -$1$ loss. We now proceed with the proof of Theorem 4.1.

The learning algorithm achieving this bound is a modification of a sample compression scheme recently proposed by Moran and Yehudayoff (2016), or more precisely, a variant of that method explored by Hanneke, Kontorovich, and Sadigurschi (2019). Our modification forces the compression scheme to also have zero empirical robust loss. Fix $\varepsilon,\delta\in(0,1)$ and a sample size $m>2{\rm vc}(\mathcal{H})$, and denote by $P$ any distribution with $\inf_{h\in\mathcal{H}}R_{\mathcal{U}}(h;P)=0$.

By classic PAC learning guarantees (Vapnik and Chervonenkis, 1974; Blumer et al., 1989), there is a positive integer $n=O({\rm vc}(\mathcal{H}))$ with the property that, for any distribution $D$ over $\mathcal{X}\times\mathcal{Y}$ with $\inf_{h\in\mathcal{H}}{\rm er}(h;D)=0$, for $n$ iid $D$-distributed samples $S^{\prime}=\{(x_{1}^{\prime},y_{1}^{\prime}),\ldots,(x_{n}^{\prime},y_{n}^{\prime})\}$, with nonzero probability, every $h\in\mathcal{H}$ satisfying $\hat{{\rm er}}(h;S^{\prime})=0$ also has ${\rm er}(h;D)<1/3$.

By our choice of $n$, we know that for any distribution $D$ over $\hat{S}_{\mathcal{U}}$, $n$ iid samples $S^{\prime}$ sampled from $D$ would have the property that, with nonzero probability, all $h\in\mathcal{H}$ with $\hat{{\rm er}}(h;S^{\prime})=0$ also have ${\rm er}(h;D)<1/3$. In particular, this implies at least that there exists a subset $S^{\prime}\subseteq\hat{S}_{\mathcal{U}}$ with $|S^{\prime}|\leq n$ such that every $h\in\mathcal{H}$ with $\hat{{\rm er}}(h;S^{\prime})=0$ has ${\rm er}(h;D)<1/3$. For such a set $S^{\prime}$, note that $\{(x_{I(x)},y):(x,y)\in S^{\prime}\}\subseteq S$, and therefore there exists a set $L$ with $|L|=n$ and $\{(x_{I(x)},y):(x,y)\in S^{\prime}\}\subseteq L\subseteq S$. Furthermore, since $x\in\mathcal{U}(x_{I(x)})$ for every $(x,y)\in S^{\prime}$, we know $\hat{{\rm er}}({\rm RERM}_{\mathcal{H}}(L);S^{\prime})=0$, and hence ${\rm er}({\rm RERM}_{\mathcal{H}}(L);D)<1/3$. Altogether, we have that, for any distribution $D$ over $\hat{S}_{\mathcal{U}}$, $\exists h_{D}\in\hat{\mathcal{H}}$ with ${\rm er}(h_{D};D)<1/3$.

We will use the above $h_{D}$ as a weak hypothesis in a boosting algorithm. Specifically, we run the $\alpha$-Boost algorithm (Schapire and Freund, 2012, Section 6.4.2) with $\hat{S}_{\mathcal{U}}$ as its data set, using the above mapping to produce the weak hypotheses for the distributions $D_{t}$ produced on each round of the algorithm. As proven in (Schapire and Freund, 2012), for an appropriate a-priori choice of $\alpha$ in the $\alpha$-Boost algorithm, running this algorithm for $T=O(\log(|\hat{S}_{\mathcal{U}}|))$ rounds suffices to produce a sequence of hypotheses $\hat{h}_{1},\ldots,\hat{h}_{T}\in\hat{\mathcal{H}}$ s.t.

From this observation, we already have a sample complexity bound, only slightly worse than the claimed result. Specifically, the above implies that $\hat{h}={\rm Majority}(\hat{h}_{1},\ldots,\hat{h}_{T})$ satisfies $\hat{R}_{\mathcal{U}}(\hat{h};S)=0$. Note that each of these classifiers $\hat{h}_{t}$ is equal ${\rm RERM}_{\mathcal{H}}(L_{t})$ for some $L_{t}\subseteq S$ with $|L_{t}|=n$. Thus, the classifier $\hat{h}$ is representable as the value of an (order-dependent) reconstruction function $\phi$ with a compression set size

Thus, invoking Lemma B.1, if $m>c{\rm vc}(\mathcal{H})^{2}{\rm vc}^{*}(\mathcal{H})\log({\rm vc}(\mathcal{H}){\rm vc}^{*}(\mathcal{H}))$ (for a sufficiently large numerical constant $c$), we have that with probability at least $1-\delta$,

$R_{\mathcal{U}}(\hat{h};P)\leq O\!\left({\rm vc}(\mathcal{H})^{2}{\rm vc}^{*}(\mathcal{H})\frac{1}{m}\log(m/{\rm vc}(\mathcal{H}))\log(m)+\frac{1}{m}\log(1/\delta)\right)$,

and setting this less than $\varepsilon$ and solving for a sufficient size of $m$ to achieve this yields a sample complexity bound, which is slightly larger than that claimed in Theorem 4.1. We next proceed to further refine this bound via a sparsification step. However, as an aside, we note that the above intermediate step will be useful in a discussion below, where the size of this compression scheme in the second expression in (1) offers an improvement over a result of Attias, Kontorovich, and Mansour (2018).

so that the majority vote predictor $\hat{h}^{\prime}(x)={\rm Majority}(\hat{h}_{i_{1}},\ldots,\hat{h}_{i_{N}})$ satisfies $\hat{{\rm er}}(\hat{h}^{\prime};\hat{S}_{\mathcal{U}})=0$, and hence $\hat{R}_{\mathcal{U}}(\hat{h}^{\prime};S)=0$. Since again, each $\hat{h}_{i_{j}}$ is the result of ${\rm RERM}_{\mathcal{H}}(L_{i_{j}})$ for some $L_{i_{j}}\subseteq S$ of size $n$, we have that $\hat{h}^{\prime}$ can be represented as the value of an (order-dependent) reconstruction function $\phi$ with a compression set size $nN=O({\rm vc}(\mathcal{H})){\rm vc}^{*}(\mathcal{H}))$. Thus, Lemma B.1 implies that, for $m\geq c{\rm vc}(\mathcal{H}){\rm vc}^{*}(\mathcal{H})$ (for an appropriately large numerical constant $c$), with probability at least $1-\delta$, $R_{\mathcal{U}}(\hat{h}^{\prime};P)\leq O\!\left({\rm vc}(\mathcal{H}){\rm vc}^{*}(\mathcal{H})\frac{1}{m}\log(m)+\frac{1}{m}\log(1/\delta)\right)$. Setting this less than $\varepsilon$ and solving for a sufficient size of $m$ to achieve this yields the stated bound.

2 Agnostic Robust Learnability

For the agnostic case, we can establish an upper bound via reduction to the realizable case, following an argument from David, Moran, and Yehudayoff (2016). Specifically, we have the following result.

For any $\mathcal{H}$ and $\mathcal{U}$, $\forall\varepsilon,\delta\in(0,1/2)$,

As above, since Assouad (1983) has shown ${\rm vc}^{*}(\mathcal{H})<2^{{\rm vc}(\mathcal{H})+1}$, this implies the following corollary.

For any $\mathcal{H}$ and $\mathcal{U}$, $\forall\varepsilon,\delta\in(0,1/2)$,

We establish the theorem via a reduction to the realizable case, following an approach used by David, Moran, and Yehudayoff (2016), except here applied to the robust loss. The reduction is summarized in the following Theorem, whose proof can be found in Appendix C:

Denote $\mathcal{M}_{{\rm RE}}=\mathcal{M}_{{\rm RE}}(1/3,1/3;\mathcal{H},\mathcal{U})$. Then

From this, Theorem 4.4 follows immediately by combining Theorem 4.6 with Theorem 4.1.

Their analysis proceeds by bounding the Rademacher complexity of the robust loss class of the convex hull of $\mathcal{H}$, which implies the sample complexity (2) can also be achieved by ${\rm RERM}_{\mathcal{H}}$ (they propose an alternative, improper, learning rule for computational reasons). But when $\max\left\lvert{\mathcal{U}(x)}\right\rvert\leq k$, the second expression in our (1) would be at most $O({\rm vc}(\mathcal{H})\log(mk))$. Thus, following the compression argument as in the proof of Theorem 4.1 would yield the following sample complexity for our improper rule:

In particular, our approach reduces the dependence on $k$ from $k\log(k)$ in (2) as obtained by Attias, Kontorovich, and Mansour (2018), to $\log(k)(\log\log(k))^{3}$. To do so, our approach does rely on improper learning, and our arguments are not valid for ${\rm RERM}_{\mathcal{H}}$. We do not know whether improperness is required to obtain this improvement, or whether in this case a ${\rm polylog}k$ dependence is possible even with ${\rm RERM}$ or some other proper learning rule. It follows from the construction of our negative result for proper learning in Theorem 3.1, that at least a $\log(k)$ factor is sometimes necessary for proper learning (regardless of the VC dimension), whereas our Corollary 4.5 implies that improper learning can achieve a sample complexity that is entirely independent of $k$ (albeit with a worse dependence on the VC dimension).

Necessary and Sufficient conditions for Robust Learnability

In the previous section, we saw that having finite VC dimension is sufficient for robust learnability. But a simple construction shows that it is not necessary: consider an infinite domain $\mathcal{X}$, the hypothesis class of all possible predictors $\mathcal{H}=\{-,+\}^{\mathcal{X}}$, and an all-powerful adversary specified by $\mathcal{U}(x)=\mathcal{X}$. In this case, the hypothesis minimizing the population robust risk ${\rm R}_{\mathcal{U}}(h;\mathcal{D})$ would always be the all-positive or the all-negative hypothesis, and so these are the only two hypothesis we should compete with. And so, even though ${\rm vc}(\mathcal{H})=\infty$, a single example suffices to inform the learner of whether to produce the all-positive or all-negative function.

Can we then have a tight characterization of robust learnability? Is there a weaker notion that is both necessary and sufficient for learning? A simple complexity measure one might consider is the maximum number of points $x_{1},\dots,x_{m}$ such that the entire perturbation sets $\mathcal{U}(x_{1}),\dots,\mathcal{U}(x_{m})$ are shattered by $\mathcal{H}$. That is, such that $\forall y_{1},\ldots,y_{m}\in\{+1,-1\},\exists h\in\mathcal{H},\forall i\forall x^{\prime}\in\mathcal{U}(x_{i}),\,h(x^{\prime})=y_{i}$. We denote this as ${\rm dim}_{\mathcal{U}\times}(\mathcal{H})$. When $\mathcal{U}(x)$ are balls around $x$, which is the typical case in metric-based robustness, this can be thought of shattering with a margin in input space. Indeed, for linear predictors and when $\mathcal{U}(x)=\{x^{\prime}|\lVert x-x^{\prime}\rVert_{2}\leq\gamma\}$ is a Euclidean ball around $x$, ${\rm dim}_{\mathcal{U}\times}(\mathcal{H})$ exactly agrees with the fat shattering dimension at scale $\gamma$ (or the $VC_{\gamma}$ dimension).

While it is fairly obvious that ${\rm dim}_{\mathcal{U}\times}(\mathcal{H})$ provides a lower bound on the sample complexity of robust learning, and thus its finiteness is necessary for learning, we construct an example in Appendix D showing that it is not sufficient. Specifically, there are classes where no points can be shattered in this way, and yet the classes are not robustly learnable. Formally,

There exist $\mathcal{X}$, $\mathcal{H}$, $\mathcal{U}$ such that ${\rm dim}_{\mathcal{U}\times}\!(\mathcal{H})=0$ but $\mathcal{M}_{{\rm RE}}(\varepsilon,\delta;\mathcal{H},\mathcal{U})=\infty$.

We now attempt to refine the above measure, and introduce a weaker notion of robust shattering that that can still be used to lower bound the sample complexity for robust learnability. Given an adversary $\mathcal{U}$ and a hypothesis class $\mathcal{H}$, consider the following notion of $\mathcal{U}$-robust shattering,

A sequence $x_{1},\ldots,x_{m}\!\in\mathcal{X}$ is said to be $\mathcal{U}$-robustly shattered by $\mathcal{H}$ if $\exists z_{1}^{+},z_{1}^{-},\ldots,z_{m}^{+},z_{m}^{-}\in\mathcal{X}$ with $x_{i}\in\mathcal{U}(z^{+}_{i})\cap\mathcal{U}(z^{-}_{i})$ $\forall i\in[m]$, and $\forall y_{1},\ldots,y_{m}\in\{-,+\}$, $\exists h\in\mathcal{H}$ with $h(z^{\prime})=y_{i}$, $\forall z^{\prime}\in\mathcal{U}(z_{i}^{y_{i}})$, $\forall i\in[m]$. The $\mathcal{U}$-robust shattering dimension ${\rm dim}_{\mathcal{U}}(\mathcal{H})$ is defined as the largest $m$ for which there exist $m$ points $\mathcal{U}$-robustly shattered by $\mathcal{H}$.

We have that ${\rm dim}_{\mathcal{U}\times}(\mathcal{H})\leq{\rm dim}_{\mathcal{U}}(\mathcal{H})\leq{\rm vc}(\mathcal{H})$, where the first inequality follows since disjoint robust shattering is a special case of robust shattering with $z_{i}^{y}=x_{i}$, and so ${\rm dim}_{\mathcal{U}}(\mathcal{H})$ is a plausible candidate for a necessary and sufficient dimension of robust learnability. The following theorem (proof provided in appendix D) establishes that the sample complexity of robust learnability is indeed lower bounded by the $\mathcal{U}$-robust shattering dimension ${\rm dim}_{\mathcal{U}}(\mathcal{H})$,

For any $\mathcal{X}$, $\mathcal{H}$, and $\mathcal{U}$, $\mathcal{M}_{{\rm RE}}(\varepsilon,\delta;\mathcal{H},\mathcal{U})=\Omega\!\left(\frac{{\rm dim}_{\mathcal{U}}(\mathcal{H})}{\varepsilon}+\frac{1}{\varepsilon}\log\!\left(\frac{1}{\delta}\right)\right)$ and $\mathcal{M}_{{\rm AG}}(\varepsilon,\delta;\mathcal{H},\mathcal{U})=\Omega\!\left(\frac{{\rm dim}_{\mathcal{U}}(\mathcal{H})}{\varepsilon^{2}}+\frac{1}{\varepsilon^{2}}\log\!\left(\frac{1}{\delta}\right)\right)$.

Based on Corollary 4.2 and Theorem 5.3, for any adversary $\mathcal{U}$ and any hypothesis class $\mathcal{H}$, we have

That is, the VC dimension is sufficient, and the robust shattering dimension is necessary for robust learnability. As discussed at the beginning of the Section, we know the VC dimension is not necessary and there can be an arbitrary large, even infinite, gap in the second inequality. We do not know whether the robust shattering dimension is also sufficient for learning, or whether there can also be a big gap in the first inequality. Establishing a complexity measure that characterizes robust learnability thus remains an open question.

Discussion and Future Directions

Perhaps one of the most interesting takeaways from this work is that we should start considering improper learning algorithms for adversarially robust learning. Even though our improper learning rule might not be practical, our results suggest to consider departing from robust empirical risk minimization and M-estimation (as in almost all published work), and considering improper learning rules such as bagging or other ensemble methods.

Although we settled the question of robust learnability of VC classes, there remains a large gap in the question of what is the optimal sample complexity for robust learning. Can the exponential dependence on ${\rm vc}(\mathcal{H})$ in Corollaries 4.2 and 4.5 be improved to a linear dependence? Perhaps this is possible with a new analysis of our learning rule or a different improper learning rule. Since our learning rule and analysis stem from recent progress on compression schemes for VC classes (Moran and Yehudayoff, 2016), it is certainly possible that further progress on the celebrated open problem regarding the existence of ${\rm vc}(\mathcal{H})$ compression schemes (Floyd and Warmuth, 1995; Warmuth, 2003) could also assist in progress on adversarially robust learning.

Our results demonstrate that there exist hypothesis classes with large gaps between what can be done with proper vs. improper robust learning. This means that when studying a particular class, such as classes corresponding to neural networks, one should consider the possibility that there might be such a gap and that improper learning might be necessary. It remains open to establish whether such gaps actually exist for specific interesting neural net classes (e.g., functions representable by a specific architecture, possibly with a bounded weight norm).

Throughout the paper we ignored computational considerations. Our learning rule can be viewed as an algorithm with black-box access to ${\rm RERM}_{\mathcal{H}}$, but making order $m^{{\rm vc}(\mathcal{H})}$ such calls, and additionally requiring order $m^{{\rm vc}(\mathcal{H}){\rm vc}^{*}(\mathcal{H})}$ time and space to represent and update the distributions used by the boosting algorithm. Without significantly increasing the sample complexity, is it possible to robustly learn with an algorithm making only a polynomial (in ${\rm vc}(\mathcal{H}),{\rm vc}^{*}(\mathcal{H}),m$) number of calls to ${\rm RERM}_{\mathcal{H}}$ or even ${\rm ERM}_{\mathcal{H}}$, plus polynomial additional time and space? What about ${\rm poly}({\rm vc}(\mathcal{H}),m)$? This question becomes even more interesting if there is such an algorithm that also only requires sample size $m={\rm poly}({\rm vc}(\mathcal{H}),1/\varepsilon,\log(1/\delta))$, rather than the $m={\rm poly}({\rm vc}(\mathcal{H}),{\rm vc}^{*}(\mathcal{H}),1/\varepsilon,\log(1/\delta))$ sufficient for our algorithm. Would another type of oracle be useful? For example, can one devise efficient methods that rely on black-box access to ${\rm ERM}$ on the dual of the hypothesis class (i.e. finding an example that is correct for the largest number of hypotheses in a given finite set of hypotheses)? More ambitiously, one may ask whether efficient PAC learnability implies efficient robust PAC learnability, roughly translating to asking whether access to any (non-robust) learning rule is sufficient for efficient robust learning.

As a final remark, we note that our results easily extend to the multiclass setting ($|\mathcal{Y}|>2$). In that case, by essentially the same algorithms and proofs, Theorems 4.1 and 4.4 (and Corollaries 4.2 and 4.5) will hold with ${\rm vc}(\mathcal{H})$ replaced by the graph dimension (Natarajan, 1989; Ben-David et al., 1995; Daniely et al., 2015). The lower bound in Theorem 5.3 also holds, by the same arguments, but with ${\rm dim}_{\mathcal{U}}(\mathcal{H})$ generalized analogous to the Natarajan dimension (Natarajan, 1989): that is, in the definition of robust shattering, after “and”, we now require $\forall i\exists y_{i,-},y_{i,+}\in\mathcal{Y}$ s.t. $\forall b_{1},\ldots,b_{m}\in\{-,+\}$, $\exists h\in\mathcal{H}$ with $h(z^{\prime})=y_{i,b_{i}}$, $\forall z^{\prime}\in\mathcal{U}(z_{i}^{b_{i}})$, $\forall i$. We leave as an open question whether one can also express an upper bound controlled by this quantity.

This work is partially funded by NSF-BSF award 1718970 and NSF award 1764032.

References

Appendix A Auxilliary Proofs Related to Proper Robust Learnability

Pick an arbitrary sequence $S\in C^{m}$. Consider a uniform weighting over the distributions $\mathcal{D}_{1},\dots,\mathcal{D}_{T}$. Denote by $E_{S}$ the event that $S\subset{\rm supp}(\mathcal{D}_{i})$ for a distribution $\mathcal{D}_{i}$ that is picked uniformly at random. We will lower bound the expected robust loss of the classifier that rule $\mathcal{A}$ outputs, namely $\mathcal{A}(S)\in\mathcal{H}$, given the event $E_{S}$,

We can lower bound the robust loss of the classifier $\mathcal{A}(S)$ by conditioning on the event that $(x,y)\notin S$ denoted $E_{(x,y)\notin S}$,

Since $\mathcal{A}(S)\in\mathcal{H}$, by construction of $\mathcal{H}$, we know that there are at least $m$ points in $C$ where $\mathcal{A}(S)$ is not robustly correct. We can unroll the expectation over $\mathcal{D}_{i}$ as follows

Appendix B Auxilliary Proofs Related to Realizable Robust Learnability

The following lemma extends the classic compression-based generalization guarantees from the -$1$ loss to also hold for the robust loss. It is used in the proof of Theorem 4.1. Generally, it is also possible to extend other generalization guarantees for compression schemes to the robust loss, such as improved bounds for permutation-invariant compression schemes, or convergence guarantees for the agnostic case (as discussed in Section 4.2).

For completeness, we include a brief proof, which merely notes that the classic argument of (Littlestone and Warmuth, 1986; Floyd and Warmuth, 1995) establishing generalization guarantees for sample compression schemes under the -$1$ loss remains valid under the robust loss.

For any indices $i_{1},\ldots,i_{k}\in\{1,\ldots,m\}$,

and a union bound over all $m^{k}$ possible choices of $i_{1},\ldots,i_{k}$ implies a probability at most $m^{k}(1-\varepsilon)^{m-k}\leq m^{k}e^{-\varepsilon(m-k)}$ that there exist $i_{1},\ldots,i_{k}$ with ${\rm R}_{\mathcal{U}}(\phi(\{(x_{i_{j}},y_{i_{j}})\}_{j=1}^{k});\mathcal{P}_{XY})>\varepsilon$ and yet $\hat{{\rm R}}_{\mathcal{U}}(\phi(\{(x_{i_{j}},y_{i_{j}})\}_{j=1}^{k});S)=0$. This is at most $\delta$ for a choice of $\varepsilon=\frac{1}{m-k}(k\ln(m)+\ln(1/\delta))$.

Appendix C Proof of Agnostic Robust Learnability

The argument follows closely a proof of an analogous result by David, Moran, and Yehudayoff (2016) for non-robust learning. Denote by the optimal realizable-case learner achieving sample complexity $\mathcal{M}_{{\rm RE}}(1/3,1/3;\mathcal{H},\mathcal{U})$, and denote $\mathcal{M}_{{\rm RE}}=\mathcal{M}_{{\rm RE}}(1/3,1/3;\mathcal{H},\mathcal{U})$, as above.

Then, in the agnostic case, given a data set $S\sim\mathcal{D}^{m}$, we first do robust-ERM to find a maximal-size subsequence $S^{\prime}$ of the data where the robust loss can be zero: that is, $\inf_{h\in\mathcal{H}}\hat{{\rm R}}_{\mathcal{U}}(h;S^{\prime})=0$. Then for any distribution $D$ over $S^{\prime}$, there exists a sequence $S_{D}\in(S^{\prime})^{\mathcal{M}_{{\rm RE}}}$ such that $h_{D}:=$ has ${\rm R}_{\mathcal{U}}(h_{D};D)\leq 1/3$; this follows since, by definition of $\mathcal{M}_{{\rm RE}}(1/3,1/3;\mathcal{H},\mathcal{U})$, there is a $1/3$ chance that $\hat{S}$ a random draw from $D^{\mathcal{M}_{{\rm RE}}}$ yields ${\rm R}_{\mathcal{U}}($, so at least one such $S_{D}$ exists. We use this to define a weak robust-learner for distributions $D$ over $S^{\prime}$: i.e., for any $D$, the weak learner chooses $h_{D}$ as its weak hypothesis.

Now we run the $\alpha$-Boost boosting algorithm (Schapire and Freund, 2012, Section 6.4.2) on data set $S^{\prime}$, but using the robust loss rather than -$1$ loss. That is, we start with $D_{1}$ uniform on $S^{\prime}$.We ignore the possibility of repeats; for our purposes we can just remove any repeats from $S^{\prime}$ before this boosting step. Then for each round $t$, we get $h_{D_{t}}$ as a weak robust classifier with respect to $D_{t}$, and for each $(x,y)\in S^{\prime}$ we define a distribution $\mathcal{D}_{t+1}$ over $S^{\prime}$ satisfying

where $\alpha$ is a parameter we can set. Following the argument from Schapire and Freund (2012, Section 6.4.2), after $T$ rounds we are guaranteed

so we will plan on running until round $T=1+48\ln(|S^{\prime}|)$ with value $\alpha=1/8$ to guarantee

Furthermore, note that, since each $h_{D_{t}}$ is given by , where $S_{D_{t}}$ is an $\mathcal{M}_{{\rm RE}}$-tuple of points in $S^{\prime}$, the classifier $\hat{h}$ is specified by an ordered sequence of $\mathcal{M}_{{\rm RE}}T$ points from $S$. Altogether, $\hat{h}$ is a function specified by an ordered sequence of $\mathcal{M}_{{\rm RE}}T$ points from $S$, and which has

Similarly to the realizable case (see the proof of Lemma B.1), uniform convergence guarantees for sample compression schemes (see Graepel, Herbrich, and Shawe-Taylor, 2005) remain valid for the robust loss, by essentially the same argument; the essential argument is the same as in the proof of Lemma B.1 except using Hoeffding’s inequality to get concentration of the empirical robust risks for each fixed index sequence, and then a union bound over the possible index sequnces as before. We omit the details for brevity. In particular, denoting $T_{m}=1+48\ln(m)$, for $m>\mathcal{M}_{{\rm RE}}T_{m}$, with probability at least $1-\delta/2$,

Let $h^{*}=\mathop{\rm argmin}_{h\in\mathcal{H}}{\rm R}_{\mathcal{U}}(h;\mathcal{D})$ (supposing the min is realized, for simplicity; else we could take an $h^{*}$ with very-nearly minimal risk). By Hoeffding’s inequality, with probability at least $1-\delta/2$,

By the union bound, if $m\geq 2\mathcal{M}_{{\rm RE}}T_{m}$, with probability at least $1-\delta$,

Since $T_{m}=O(\log(m))$, the above is at most $\varepsilon$ for an appropriate choice of sample size $m=O\!\left(\frac{\mathcal{M}_{{\rm RE}}}{\varepsilon^{2}}\log^{2}\!\left(\frac{\mathcal{M}_{{\rm RE}}}{\varepsilon}\right)+\frac{1}{\varepsilon^{2}}\log\!\left(\frac{1}{\delta}\right)\right)$.

Appendix D Auxilliary Proofs Related to Necessary Conditions for Robust Learnability

Note that by construction we have ${\rm R}_{\mathcal{U}}(h^{\mathbf{y}};\mathcal{D})=0$. Now, consider an arbitrary learning rule $\mathcal{A}:(\mathcal{X}\times\mathcal{Y})^{*}\mapsto\mathcal{Y}^{\mathcal{X}}$. We will assume that $\mathcal{A}$ always gets the prediction of $z_{1}^{y_{1}}$ correct. Let $I=\{2,\dots,d\}$ and let $\mathcal{S}$ be the set of all sequences of size $m$ containing at most $({\rm d}-1)/2$ elements from $I$. Fix an arbitrary sequence $S\in\mathcal{S}$. Denote by $S_{\mathbf{y}}=((z_{i}^{y_{i}},y_{i}):i\in\mathcal{S})$ the sequence of examples induced by the indices sequence $S$. Then,

Since the inequality above holds for any sequence $S\in\mathcal{S}$, it follows that

To finish the proof, we need to show that

For this just consider a distribution $P_{1}$ with mass $1-\varepsilon$ on $(z_{1}^{+},+1)$ and mass $\varepsilon$ on $(z_{2}^{+},+1)$, and another distribution $P_{2}$ with mass $1-\varepsilon$ on $(z_{1}^{+},+1)$ and mass $\varepsilon$ on $(z_{2}^{-},-1)$. If $m\leq(1/2\varepsilon)\ln(1/\delta)$, with probability at least $\delta$, we will only observe $m$ samples of $(z_{1}^{+},+1)$, and thus learning rule $\mathcal{A}$ will make a mistake on $x_{2}$ (which is in $\mathcal{U}(z_{2}^{+})\cap\mathcal{U}(z_{2}^{-})$) with probability at least $1/2$, therefore having error at least $\varepsilon/2$. By combining both parts, we arrive at the theorem statement.

For the agnostic case, we briefly describe the construction. The remainder of the proof more or less follows a standard argument, for instance see Anthony and Bartlett (1999, Chapter 5). Let ${\rm d}={\rm dim}_{\mathcal{U}}(\mathcal{H})$, and fix $x_{1},\ldots,x_{{\rm d}}$ a sequence $\mathcal{U}$-robustly shattered by $\mathcal{H}$, and let $z_{1}^{+},z_{1}^{-},\ldots,z_{{\rm d}}^{+},z_{{\rm d}}^{-}\in\mathcal{X}$ be as in definition 5.2; in particular, note that any $y,y^{\prime}$ and any $i\neq j$ necessarily have $z_{i}^{y}\neq z_{j}^{y^{\prime}}$. For $b\in\{0,1\}^{\rm d}$, define distribution $\mathcal{D}_{b}$ as follows, for $i\in[{\rm d}]$:

where $)<\alpha<1$ is appropriately chosen based on $\varepsilon$ and $\delta$.