# Sample Complexity of Robust Linear Classification on Separated Data

Robi Bhattacharjee  Somesh Jha  Kamalika Chaudhuri

###### Abstract

We consider the sample complexity of learning with adversarial robustness.
Most prior theoretical results for this problem have considered a setting
where different classes in the data are close together or overlapping. We
consider, in contrast, the well-separated case where there exists a classifier
with perfect accuracy and robustness, and show that the sample complexity
narrates an entirely different story. Specifically, for linear classifiers, we
show a large class of well-separated distributions where the expected robust
loss of any algorithm is at least $\Omega(\frac{d}{n})$, whereas the max
margin algorithm has expected standard loss $O(\frac{1}{n})$. This shows a gap
in the standard and robust losses that cannot be obtained via prior
techniques. Additionally, we present an algorithm that, given an instance
where the robustness radius is much smaller than the gap between the classes,
gives a solution with expected robust loss is $O(\frac{1}{n})$. This shows
that for very well-separated data, convergence rates of $O(\frac{1}{n})$ are
achievable, which is not the case otherwise. Our results apply to robustness
measured in any $\ell_{p}$ norm with $p>1$ (including $p=\infty$).

Machine Learning, ICML

##  1 Introduction

Motivated by the use of machine learning in safety-critical settings,
adversarially robust classification has been of much recent interest.
Formally, the problem is as follows. A learner is given training data drawn
from an underlying distribution $D$, a hypothesis class $\mathcal{H}$, a
robustness metric $d$, and a radius $r$. The learner’s goal is to find a
classifier $h\in\mathcal{H}$ which has the lowest robust loss at radius $r$.
The robust loss of a classifier is the expected fraction of examples where
either $f(x)\neq y$ or where there exists an $x^{\prime}$ at distance
$d(x,x^{\prime})\leq r$ such that $f(x)\neq f(x^{\prime})$. Robust
classification thus aims to find a classifier that maximizes accuracy on
examples that are distance $r$ or more from the decision boundary, where
distances are measured according to the metric $d$.

In this work, we ask: how many samples are needed to learn a classifier with
low robust loss when $\mathcal{H}$ is the class of linear classifiers, and $d$
is an $\ell_{p}$-metric? Prior work has provided both upper (Yin et al., 2019;
Dan et al., 2020) as well as lower bounds (Schmidt et al., 2018; Dan et al.,
2020) on the sample complexity of the problem. However, almost all look at
settings where the data distribution itself is not separated – data from
different classes overlap or are close together in space. In this case, the
classifier that minimizes robust loss is quite different from the one that
minimizes error, which often leads to strong sample complexity gaps. Many real
tasks where robust solutions are desired however tend to involve well-
separated data (Yang et al., 2020), and hence it is instructive to look at
what happens in these cases.

With this motivation, we consider in this work robust classification of data
that is linearly $r$-separable. Specifically, there exists a linear classifier
which has zero robust loss at robustness radius $r$. This case is thus the
analog of the realizable case for robust classification, and we consider both
upper and lower bounds in this setting.

For lower bounds, prior work (Cullina et al., 2018) shows that both standard
and robust linear classification have VC-dimension $O(d)$, and consequently
have similar bounds on the expected loss in the worst case. However, these
results do not apply to this setting since we are specifically considering
well-separated data, which greatly restricts the set of possible worst-case
distributions. For our lower bound, we provide a family of distributions that
are linearly $r$-separable and where the maximum margin classifier, given $n$
independent samples, has error $O(1/n)$. In contrast, any algorithm for
finding the minimum robust loss classifier has robust loss at least
$\Omega(d/n)$, where $d$ is the data dimension. These bounds hold for all
$\ell_{p}$-norms provided $p>1$, including $p=2$ and $p=\infty$. Unlike prior
work, our bounds do not rely on the difference in loss between the solutions
with optimal robust loss and error, and hence cannot be obtained by prior
techniques. Instead, we introduce a new geometric construction that exploits
the fact that learning a classifier with low robust loss when data is linearly
$r$-separated requires seeing a certain number of samples close to the margin.

For upper bounds, prior work (Yin et al., 2019) provides a bound on the
Rademacher complexity of adversarially robust learning, and show that it can
be worse than the standard Rademacher complexity by a factor of $d^{1/q}$ for
$\ell_{p}$-norm robustness where $1/p+1/q=1$. Thus, an interesting question is
whether dimension-independent bounds, such as those for the accuracy under
large margin classification, can be obtained for robust classification as
well. Perhaps surprisingly, we show that when data is really well-separated,
the answer is yes. Specifically, if the data distribution is linearly
$r+\gamma$-separable, then there exists an algorithm that will find a
classifier with robust loss $O(\Delta^{2}/\gamma^{2}n)$ at radius $r$ where
$\Delta$ is the diameter of the instance space. Observe that much like the
usual sample complexity results on SVM and perceptron, this upper bound is
independent of the data dimension and depends only on the excess margin (over
$r$). This establishes that when data is really well-separated, finding robust
linear classifiers does not require a very large number of samples.

While the main focus of this work is on linear classifiers, we also show how
to generalize our upper bounds to Kernel Classification, where we find a
similar dynamic with the loss being governed by the excess margin in the
embedded kernel space. However, we defer a thorough investigation of robust
kernel classification as an avenue for future work.

Our results imply that while adversarially robust classification may be more
challenging than simply accurate classification when the classes overlap, the
story is different when data is well-separated. Specifically, when data is
linearly (exactly) $r$-separable, finding an $r$-separated solution to robust
loss $\epsilon$ may require $\Omega(d/\epsilon)$ samples for some distribution
families where finding an accurate solution is easier. Thus in this case,
there is a gap between the sample complexities of robust and simply accurate
solutions, and this is true regardless of the $\ell_{p}$ norm in which
robustness is measured. In contrast, if data is even more separated – linearly
$r+\gamma$-separable – then we can obtain a dimension-independent upper bound
on the sample complexity, much like the sample complexity of SVMs and
perceptron. Thus, how separable the data is matters for adversarially robust
classification, and future works in the area should consider separability
while discussing the sample complexity

###  1.1 Related Work

There is a large body of work (Carlini & Wagner, 2017; Liu et al., 2017;
Papernot et al., 2017, 2016a; Szegedy et al., 2014; Hein & Andriushchenko,
2017; Katz et al., 2017; Papernot et al., 2016b; Raghunathan et al., 2018;
Sinha et al., 2018) empirically studying adversarial examples primarily in the
context of neural networks. Several works (Schmidt et al., 2018; Raghunathan
et al., 2020; Tsipras et al., 2019) have empirically investigated trade-offs
between robust and standard classification.

On the theoretical side, this phenomenon has been studied in both the
parametric and non-parametric settings. On the parametric side, several works
(Khim & Loh, 2018; Attias et al., 2019; Montasser et al., 2019; Yin et al.,
2019; Ashtiani et al., 2020) have focused on finding distribution agnostic
bounds of the sample complexity for robust classification. In (Montasser et
al., 2019), Srebro et. al. showed through an example that the VC dimension of
robust learning may be much larger than standard or accurate learning
indicating that the sample complexity bounds may be higher. However, their
example did not apply to linear classifiers.

(Diakonikolas et al., 2020) considers learning linear classifiers robustly,
but is primarily focused on computational complexity as opposed to sample
complexity.

In (Yin et al., 2019), Bartlett et. al. investigated the Rademacher complexity
of robustly learning linear classifiers as well as neural networks. They
showed that in both cases, the robust Rademacher complexity can be bounded in
terms of the dimension of the input space – thus indicating a possible gap
between standard and robust learning. However, as with the works considering
VC dimension, this work is fundamentally focused on upper bounds – they do not
show true lower bounds on data requirements.

Because of it’s simplicity and elegance, the case where the data distribution
is a mixture of Gaussians has been particularly well-studied. The first such
work was (Schmidt et al., 2018), in which Schmidt et. al. showed an
$\Omega(\sqrt{d})$ gap between the standard and robust sample complexity for a
mixture of two Gaussians using the $\ell_{\infty}$ norm. This was subsequently
expanded upon in (Bhagoji et al., 2019), (Dobriban et al., 2020) and (Dan et
al., 2020). (Bhagoji et al., 2019) introduces a notion of “optimal transport,”
which they subsequently apply to the Gaussian case, deriving a closed form
expression for the optimally robust linear classifier. Their results apply to
any $\ell_{p}$ norm. (Dobriban et al., 2020) applies expands upon (Schmidt et
al., 2018) by consider mixtures of three Gaussians in both the $\ell_{2}$ and
$\ell_{\infty}$ norms. Finally, (Dan et al., 2020) fully generalizes the
results of (Schmidt et al., 2018) providing tight upper and lower bounds on
the standard and robust sample complexities of a mixture of two Gaussians, in
any norm (including $\ell_{p}$ for $p\in[1,\infty]$). (Schmidt et al., 2018)
and (Dan et al., 2020) bear the most relevance with our work, and we
consequently carefully compare our results in section 3.1.

Another approach for lower and upper bounds on sample complexities for linear
classifiers can be found in (Cullina et al., 2018), which examines the robust
VC dimension of learning linear classifiers. They show that the VC dimension
is $d+1$, just as it is in the standard case. This implies that the bounds in
the robust case match the bounds in the standard case and in particular shows
a lower bound of $\Omega(d/n)$ on the expected loss of learning a robust
linear classifier from $n$ samples.

While this result appears to match our lower bound, there is a crucial
distinction between the bounds. Our bound implies that there exists some
distribution with a large $\ell_{2}$ margin for which the expected robust loss
must be $\Omega(d/n)$. On the other hand, standard results about learning
linear classifiers on large margin data implies that the expected standard
loss will be $O(1/n)$ (when running the max-margin algorithm). For this
reason, our paper provides a case in the well-separated setting in which
learning linear classifiers is provably more difficult (in terms of sample
complexity) in the robust setting than in the standard setting. By contrast,
(Cullina et al., 2018) does not show this. Their paper only implies (through
standard VC constructions) the existence of some distribution that is
difficult to learn, and the standard PAC bounds cannot ensure that such a
distribution also has a large $\ell_{2}$ margin.

In the non-parametric setting, there are several works which contrast standard
learning with robust learning. (Wang et al., 2018) considers the nearest
neighbors algorithm, and shows how to adapt it for converging towards a robust
classifier. In (Yang et al., 2019), Yang et. al. propose the $r$-optimal
classifier, which is the robust analog of the Bayes optimal classifier.
Through several examples they show that it is often a fundamentally different
classifier - which can lead to different convergence behavior in the standard
and robust settings. (Bhattacharjee & Chaudhuri, 2020) unified these
approaches by specifying conditions under which non-parametric algorithms can
be adapted to converge towards the $r$-optimal classifier, thus introducing
$r$-consistency, the robust analog of consistency.

##  2 Preliminaries

We consider binary classification over $\mathbb{R}^{d}\times\\{\pm 1\\}$. Our
metric of choice is the $\ell_{p}$ norm, where $p>1$ (including $p=\infty$) is
arbitrary. For $x\in\mathbb{R}^{d}$, we will use $||x||_{p}$ to denote the
$\ell_{p}$ norm of $x$, and consequently will use $||x-y||_{p}$ to denote the
$\ell_{p}$ distance between $x$ and $y$. We will also let $\ell_{q}$ denote
the dual norm to $\ell_{p}$ \- that is, $\frac{1}{q}+\frac{1}{p}=1$.

We use $B_{p}(x,r)$ to denote the closed $\ell_{p}$ ball with center $x$ and
radius $r$. For any $S\subset\mathbb{R}^{d}$, we let $diam_{p}(S)$ denote its
diameter: that is, $diam_{p}(S)=\sup_{x,y\in S}||x-y||_{p}.$

###  2.1 Standard and Robust Loss

In classical statistical learning, the goal is to learn an accurate
classifier, which is defined as follows:

######  Definition 1.

Let ${\mathcal{D}}$ be a distribution over $\mathbb{R}^{d}\times\\{\pm 1\\}$,
and let $f\in\\{\pm 1\\}^{\mathbb{R}^{d}}$ be a classifier. Then the standard
loss of $f$ over ${\mathcal{D}}$, denoted $\mathcal{L}(f,{\mathcal{D}})$, is
the fraction of examples $(x,y)\sim{\mathcal{D}}$ for which $f$ is not
accurate. Thus

$\mathcal{L}(f,{\mathcal{D}})=P_{(x,y)\sim{\mathcal{D}}}[f(x)\neq y].$

Next, we define robustness, and the corresponding robust loss.

######  Definition 2.

A classifier $f\in\\{\pm 1\\}^{\mathbb{R}^{d}}$ is said to be robust at $x$
with radius $r$ if $f(x)=f(x^{\prime})$ for all $x^{\prime}\in B_{p}(x,r)$.

######  Definition 3.

The robust loss of $f$ over ${\mathcal{D}}$, denoted
$\mathcal{L}_{r}(f,{\mathcal{D}})$, is the fraction of examples
$(x,y)\sim{\mathcal{D}}$ for which $f$ is either inaccurate at $(x,y)$, or $f$
is not robust at $(x,y)$ with radius $r$. Observe that this occurs if and only
if there is some $x^{\prime}\in B_{p}(x,r)$ such that $f(x^{\prime})\neq y$.
Thus

$\mathcal{L}_{r}(f,{\mathcal{D}})=P_{(x,y)\sim{\mathcal{D}}}[\exists
x^{\prime}\in B_{p}(x,r)\text{ s.t. }f(x^{\prime})\neq y].$

###  2.2 Expected Loss and Sample Complexity

The most common way to characterize the performance of a learning algorithm is
through an $(\epsilon,\delta)$ guarantee, which computes
$\epsilon_{n},\delta_{n}$ such that an algorithm trained over $n$ samples has
loss at most $\epsilon_{n}$ with probability at least $1-\delta_{n}$.

In this work, we use the simpler notion of expected loss, which is defined as
follows:

######  Definition 4.

Let $A$ be a learning algorithm and let ${\mathcal{D}}$ be a distribution over
$\mathbb{R}^{d}\times\\{\pm 1\\}$. For any $S\sim{\mathcal{D}}^{n}$, we let
$A_{S}$ denote the classifier learned by $A$ from training data $S$. Then the
expected standard loss of $A$ with respect to ${\mathcal{D}}$, denoted
$EL^{n}(A,{\mathcal{D}})$ where $n$ is the number of training samples, is
defined as

$E\mathcal{L}^{n}(A,{\mathcal{D}})={\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}\mathcal{L}(A_{S},{\mathcal{D}}).$

Similarly, we define the expected robust loss of $A$ with respect to
${\mathcal{D}}$ as

$E\mathcal{L}_{r}^{n}(A,{\mathcal{D}})={\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}\mathcal{L}_{r}(A_{S},{\mathcal{D}}).$

Our main motivation for using this criteria is simplicity. Our primary goal is
to compare and contrast the performances of algorithms in the standard and
robust cases, and this contrast clearest when the performances are summarized
as a single number (namely the expected loss) rather than an
$(\epsilon,\delta)$ pair.

Next, we address the notion of sample complexity. As above, sample complexity
is typically defined as the minimum number of samples needed to guarantee
$(\epsilon,\delta)$ performance. In this work, we will instead define it
solely with respect to $\epsilon$, the expected loss.

######  Definition 5.

Let ${\mathcal{D}}$ be a distribution over $\mathbb{R}^{d}\times\\{\pm 1\\}$
and $A$ be a learning algorithm. Then the standard sample complexity of $A$
with respect to ${\mathcal{D}}$, denoted $m^{\epsilon}(A,{\mathcal{D}})$, is
the minimum number of training samples needed such that $A$ has expected
standard loss at most $\epsilon$. Formally,

$m^{\epsilon}(A,{\mathcal{D}})=\min(\\{n:E\mathcal{L}^{n}(A,D)\leq\epsilon\\}).$

Similarly, we can define the robust sample complexity as

$m_{r}^{\epsilon}(A,{\mathcal{D}})=\min(\\{n:E\mathcal{L}^{n}(A,D)\leq\epsilon\\}).$

###  2.3 Linear classifiers

In this work, we consider linear classifiers, formally defined as follows:

######  Definition 6.

Let $w\in\mathbb{R}^{d}$ be a vector. Then the linear classifier with
parameters $w\in\mathbb{R}^{d}$ and $b\in\mathbb{R}$ over
$\mathbb{R}^{d}\times{\pm 1}$, denoted $f_{w,b}$, is defined as ,

$f_{w,b}(x)=\begin{cases}+1&\langle w,x\rangle\geq b\\\ -1&\langle
w,x\rangle<b\end{cases}.$

Learning linear classifiers is well understood in the standard classification
setting. We now consider the linearly separable case, in which some linear
classifier has perfect accuracy. We will later define linear $r$-separability
as the robust analog of separability.

######  Definition 7.

A distribution ${\mathcal{D}}$ over $\mathbb{R}^{d}\times Y$ is linearly
separable if its support can be partitioned into sets $S^{+}$ and $S^{-}$ such
that:

1\. $S^{+}$ and $S^{-}$ correspond to the positively and negatively labeled
subsets of $\mathbb{R}^{d}$. In particular, $P_{(x,y)\sim{\mathcal{D}}}[x\in
S^{y}]=1.$

2\. There exists a linear classifier, $f_{w,b}$, that has perfect accuracy.
That is, $\mathcal{L}(f_{w,b},{\mathcal{D}})=0$.

The standard sample complexity for linearly separable distributions can be
characterized through their margin, which is defined as follows.

######  Definition 8.

Let ${\mathcal{D}}$ be a linearly separable distribution over
$\mathbb{R}^{d}\times\\{\pm 1\\}$. Let $S^{+}$ and $S^{-}$ be as above. Then
${\mathcal{D}}$ has margin $\gamma$ if $\gamma$ is the largest real number
such that there exists a linear classifier $f_{w,b}$ with the following
properties:

1\. $f_{w,b}$ has perfect accuracy. That is,
$\mathcal{L}(f_{w,b},{\mathcal{D}})=0$.

2\. Let $H_{w,b}=\\{x:\langle x,w\rangle=b\\}$ denote the decision boundary of
$f_{w,b}$. Then for all $x\in(S^{+}\cup S^{-})$, $x$ has $\ell_{2}$ distance
at least $\gamma$ from $H_{w,b}$. That is,

$\inf_{x\in S^{+}\cup S^{-},z\in H_{w,b}}||x-z||_{2}\geq\gamma.$

We let $\gamma({\mathcal{D}})$ denote the margin of ${\mathcal{D}}$.

Observe that although we use a general norm, $\ell_{p}$, to measure
robustness, the margin is always measured in $\ell_{2}$. This is because the
$\ell_{2}$ norm plays a fundamental role in bounding the number of samples
needed to learn a linear classifier.

The basic idea is that when the $\ell_{2}$ margin is large relative to the
$\ell_{2}$ diameter of the distribution, the max margin algorithm requires
fewer samples needed to learn a linear classifier. In particular, the ratio
between the $\ell_{2}$ margin and the $\ell_{2}$ diameter fully characterizes
the standard sample complexity of the max margin algorithm. To further
simplify our notation, we define this ratio as the aspect ratio.

######  Definition 9.

Let ${\mathcal{D}}$ be a linearly separable distribution over
$\mathbb{R}^{d}\times\\{\pm 1\\}$. Then the aspect ratio of ${\mathcal{D}}$,
$\rho({\mathcal{D}})$ is defined as,

$\rho({\mathcal{D}})=\frac{diam_{2}(S^{+}\cup S^{-})}{\gamma({\mathcal{D}})},$

where $\text{diam}_{2}(S^{+}\cup S^{-})$ denotes its diameter in the
$\ell_{2}$ norm.

We now have the following well-known result, which characterizes the expected
standard loss with the aspect ratio.

######  Theorem 10.

_(Chapter 10 in(Vapnik, 1998))_ Let $M$ denote the hard margin SVM algorithm.
If ${\mathcal{D}}$ is a distribution with aspect ratio
$\rho=\rho({\mathcal{D}})$, then for any $n>0$ we have
${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}\mathcal{L}(M_{S},{\mathcal{D}})\leq
O(\frac{\rho^{2}}{n}),$ where $M_{S}$ denotes the classifier learned by $M$
from training data $S$.

We can also express this result in terms of standard sample complexity.

######  Corollary 11.

Let $M$ denote the hard margin SVM algorithm. If ${\mathcal{D}}$ is a
distribution with aspect ratio $\rho=\rho({\mathcal{D}})$, then for any
$\epsilon>0$ we have $m^{\epsilon}(M_{S},{\mathcal{D}})\leq
O(\frac{\rho^{2}}{\epsilon}),$ where $M_{S}$ denotes the classifier learned by
$M$ from training data $S$.

Theorem 10 and Corollary 11 will serve as a benchmark for comparison with the
robust sample complexity.

###  2.4 Linear $r$-separability

Finally, we introduce linear $r$-separability, which is the key characteristic
of distributions considered in this paper. This can be thought of as the
robust analog of linear separability.

######  Definition 12.

For any $r>0$, a distribution ${\mathcal{D}}$ over $\mathbb{R}^{d}\times\\{\pm
1\\}$ is linearly $r$-separable if there exists a linear classifier $f_{w,b}$
such that $\mathcal{L}_{r}(f_{w,b},{\mathcal{D}})=0$.

This definition is the fundamental property considered in this paper. Our goal
is to understand the sample complexity required for learning robust linear
classifiers on linearly $r$-separable distributions, and compare it with the
standard sample complexity given in Theorem 10.

##  3 Lower Bounds

In this section, we consider $r$-separated distributions whose aspect ratio is
constant. By Theorem 10, the standard sample complexity for learning them is
independent of $d$. We will show that in contrast, the robust sample
complexity has a linear dependence on $d$, and consequently establish a
substantial gap between the standard and robust cases.

We begin by defining the family of such distributions.

######  Definition 13.

For any $\rho,r$, the set ${\mathcal{F}}_{r,\rho}$ is defined as the set of
all distributions ${\mathcal{D}}$ over $\mathbb{R}^{d}\times\\{\pm 1\\}$ such
that ${\mathcal{D}}$ is $r$-separated and has aspect ratio at most $\rho$.

We now state our main result.

######  Theorem 14.

Let $r>0$ and $\rho>20$. Then the following hold.

  1. 1.

For every learning algorithm $A$, and any $n>0$, there exists
${\mathcal{D}}\in{\mathcal{F}}_{r,\rho}$ such that the expected robust loss
when $A$ is trained on a sample of size $n$ from ${\mathcal{D}}$ is at least
$\Omega(\frac{d}{n})$. Formally, there exists a constant $c>0$ such that
${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]\geq\frac{cd}{n}.$

  2. 2.

In contrast, by Theorem 10, for any ${\mathcal{D}}\in{\mathcal{F}}_{r,D}$, the
max margin algorithm has expected standard loss $O(\frac{\rho^{2}}{n})$, when
trained on a sample of size $n$ from ${\mathcal{D}}$. Formally, there exists a
constant $c^{\prime}>0$ such that
${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}(A_{S},{\mathcal{D}})]\leq\frac{c^{\prime}\rho^{2}}{n}.$

The condition $\rho>20$ is required to rule out degenerate cases. This is
because for small values of $\rho$, the $\ell_{2}$ diameter of ${\mathcal{D}}$
is not much larger than the $\ell_{2}$ margin of ${\mathcal{D}}$. This forces
${\mathcal{D}}$ to be mostly clustered around a line which leads to more
complicated behavior.

Observe that when $\rho$ is a constant independent of $d$, the expected
standard loss is $O(\frac{1}{n})$ while the expected robust loss is
$\Omega(\frac{d}{n})$. Thus, the ratio between the expected robust loss and
the expected standard loss is $\Omega(d)$, leading to a dimensional dependent
gap between the robust and standard cases.

We also note that these bounds hold regardless of which $\ell_{p}$
($p\in(1,\infty])$ norm is being used. This is because our construction of
${\mathcal{D}}\in{\mathcal{F}}_{r,\rho}$ for which the lower bound holds is
given in terms of the norm $p$. More generally, the family
${\mathcal{F}}_{r,\rho}$ is implicitly defined with respect to $p$.

Furthermore, our lower bound differs from the lower bound of
$\Omega(\frac{d}{n})$ shown in prior work (Cullina et al., 2018) because it
specifically holds for ${\mathcal{F}}_{r,\rho}$, a linearly $r$-separated
family of distributions with constant aspect ratio. Thus, while (Cullina et
al., 2018) has shown the existence of distributions satisfying the first
condition of Theorem 14, our result is the first to exhibit a distribution
satisfying both conditions.

Finally, we note that Theorem 14 can also be expressed in terms of sample
complexities. We include this in the following corollary.

######  Corollary 15.

Let $r>0$ and $\rho>20$. Then the following hold.

1\. For every learning algorithm $A$, and any $\epsilon>0$, there exists
${\mathcal{D}}\in{\mathcal{F}}_{r,\rho}$ such that the robust sample
complexity of $A$ with respect to ${\mathcal{D}}$ is at least
$\Omega(\frac{d}{\epsilon})$. Formally, there exists a constant $c>0$ such
that $m_{r}^{\epsilon}(A,{\mathcal{D}})\geq\frac{cd}{\epsilon}.$

2\. In contrast, by Theorem 10, for any ${\mathcal{D}}\in{\mathcal{F}}_{r,D}$,
the max margin algorithm has standard sample complexity
$O(\frac{\rho^{2}}{\epsilon})$. Formally, there exists a constant
$c^{\prime}>0$ such that
$m^{\epsilon}(A,{\mathcal{D}})\leq\frac{c^{\prime}\rho^{2}}{\epsilon}.$

###  3.1 Comparison with (Dan et al., 2020) and (Schmidt et al., 2018)

The first work to provide a robust sample complexity lower bound that applied
to linear classifiers is (Schmidt et al., 2018); they showed a gap of
$\Omega(\sqrt{d})$ between the robust and accuracy loss for a specific mixture
of two Gaussians. This was later generalized to mixtures of any two Gaussians
by (Dan et al., 2020), who also established more general lower bounds for any
$\ell_{p}$ norm. Since (Dan et al., 2020) is a strict generalization of
(Schmidt et al., 2018), we next explain how our lower bounds differ from (Dan
et al., 2020), and why their techniques do not lead to our results. We begin
by summarizing their results.

##### Summary of (Dan et al., 2020)

(Dan et al., 2020) considers data distributions ${\mathcal{D}}$ that are
parametrized by $\mu\in\mathbb{R}^{d}$ and $\Sigma\in\mathbb{R}^{d\times d}$,
$\Sigma\succcurlyeq 0$. ${\mathcal{D}}_{\mu,\Sigma}$ is the mixture of two
Gaussians, ${\mathcal{N}}(\mu,\Sigma)$ and ${\mathcal{N}}(-\mu,\Sigma)$, with
equal mass, where instances drawn from ${\mathcal{N}}(\mu,\Sigma)$ are labeled
as $+$, and instances drawn from ${\mathcal{N}}(-\mu,\Sigma)$ are labeled as
$-$. They consider robustness measured in any normed metric in
$\mathbb{R}^{d}$, including the $\ell_{p}$ norm for $p\in(1,\infty]$. Although
their bounds apply to any classifier, this effectively deals with linear
classifiers since it can be shown that the optimally robust and accurate
classifiers are both linear.

For any distribution ${\mathcal{D}}_{\mu,\Sigma}$, let $L_{rob}$ denote the
optimal robust loss of any classifier on ${\mathcal{D}}_{\mu,\Sigma}$, and let
$L_{std}$ denote the optimal standard loss. Then the bounds shown in (Dan et
al., 2020) can restated as follows (a detailed derivation from (Dan et al.,
2020) appears in Appendix A).

######  Theorem 16.

(Dan et al., 2020)

  1. 1.

For any learning algorithm $A$ and any $n>0$, there exists some mixture of
Gaussians, ${\mathcal{D}}_{\mu,\Sigma}$ such that the expected excess robust
loss is at least $\Omega(L_{rob}\frac{d}{n}),$ when $A$ is trained on a sample
of size $n$ from ${\mathcal{D}}$.

  2. 2.

For any distribution ${\mathcal{D}}_{\mu,\Sigma}$, it is possible to learn a
classifier with expected excess standard loss at most $O(L_{std}\frac{d}{n})$.

  3. 3.

By (1.) and (2.), the ratio between the expected excess loss and expected
excess standard loss can be expressed as
$ratio\geq\Omega(\frac{L_{rob}}{L_{std}}).$

Observe that their bounds are given through excess losses, which is the amount
by which the loss exceeds to the optimal loss. This is necessary because in
their setting, the optimal classifiers do not have $0$ loss.

##### Comparison with our bounds

Recall that in our work, we are concerned with the linearly $r$-separated
case, which occurs precisely when the optimal robust and standard losses both
equal $0$. However, from Theorem 16, we see that although (Dan et al., 2020)
proves a gap between standard and robust sample complexity, this gap is
predicated on distributions for which the optimal robust loss, $L_{rob}$ and
optimal standard loss, $L_{std}$ differ. Furthermore, in the case where they
obtain a gap of $\Omega(d)$, we see that this requires
$\frac{L_{rob}}{L_{std}}=\Omega(d)$ which is a substantial difference. By
contrast, our results characterize a gap exclusively in the case that this
does not occur.

Finally, in the limiting case where the Gaussians they consider are
sufficiently far apart, their data will begin to appear linearly
$r$-separated, meaning both $L_{rob}$ and $L_{std}$ are close to $0$. However,
even in this case, it can be shown that the ratio $\frac{L_{rob}}{L_{std}}$
diverges towards infinity, meaning that their lower bound characterizes a very
different dynamic from ours. Precise details on this comparison can be found
in appendix A.

###  3.2 Intuition behind Theorem 14

The proof idea for Theorem 14 can be summarized with a simple example (Figure
1). In this example, we seek to learn a linear classifier for a linearly
$r$-separated distribution in $\mathbb{R}^{2}$. The key idea is to contrast
the necessary conditions for learning a robust classifier, and the necessary
conditions for learning an accurate classifier.

Observe that the distribution is precisely linearly $r$-separated, that is, it
is not possible to achieve robustness for radii larger than $r$. Because of
this, there is a unique linear classifier $f_{rob}$ that has perfect
robustness. In order to learn this classifier, we must see examples from
$S^{+}\cup S^{-}$ that are close to the “boundary” of $S^{+}\cup S^{-}$. In
our figure, this consists of points that are close to the dotted blue and red
lines. Moreover, it can be shown that the number of such examples we must see
is related to $d$, the dimension.

By contrast, any classifier that separates $S^{+}$ from $S^{-}$ has perfect
accuracy (take for example $f_{std}$ shown in the figure). It is possible to
exploit this by using margin based algorithms for learning linear classifiers.
In particular, we no longer need to see points that are extremely close to the
boundary of $S^{+}\cup S^{-}$.

Figure 1: An example of a linearly $r$-separated distribution, with positively
and negatively labeled examples in $S^{+}$ and $S^{-}$ respectively. The
optimally robust classifier, $f_{rob}$ is shown in purple, while the (not
necessarily unique) optimally accurate classifier, $f_{std}$, is shown in
green.

##### General Hypothesis Classes:

We now briefly consider how to extend our methods to other hypothesis classes.
For any hypothesis class $\mathcal{H}$ and distribution ${\mathcal{D}}$ let

$\mathcal{H}_{{\mathcal{D}},\alpha}=\\{h:h\in\mathcal{H},\mathcal{L}(h,{\mathcal{D}})\leq\alpha\\}$

and let

$\mathcal{H}_{{\mathcal{D}},\alpha}^{r}=\\{h:h\in\mathcal{H},\mathcal{L}_{r}(h,{\mathcal{D}})\leq\alpha\\}.$

$\mathcal{H}_{{\mathcal{D}},\alpha}$ can be thought of as the set of accurate
classifiers while $\mathcal{H}_{{\mathcal{D}},\alpha}^{r}$ can be thought of
as the set of astute classifiers. By their definitions, it is clear that
$\mathcal{H}_{{\mathcal{D}},\alpha}^{r}\subseteq\mathcal{H}_{{\mathcal{D}},\alpha}$.
However, in the case when $\mathcal{H}$ is the set of linear classifiers, we
see that for small $\alpha$, $\mathcal{H}_{{\mathcal{D}},\alpha}^{r}$ is a
much “smaller” set than $\mathcal{H}_{{\mathcal{D}},\alpha}$. By exploiting
the geometric structure inherent to $\mathcal{H}$, we can much more
efficiently search for some $h\in\mathcal{H}_{{\mathcal{D}},\alpha}$ than we
can in $\mathcal{H}_{{\mathcal{D}},\alpha}^{r}$. This dynamic is the crux of
our lower bound: as we essentially show that there are far more critical
points (i.e. points near the decision boundary) that we must see for learning
$\mathcal{H}_{{\mathcal{D}},\alpha}^{r}$ that aren’t required for
$\mathcal{H}_{{\mathcal{D}},\alpha}$.

Thus, for our methods to extend to an arbitrary hypothesis class, we would
require a similar dynamic. We need two properties to hold: (1)
$\mathcal{H}_{{\mathcal{D}},\alpha}^{r}$ must be a very strict subset of
$\mathcal{H}_{{\mathcal{D}},\alpha}$ for sufficiently small alpha. (2) We must
have some kind of exploitable geometric structure about $\mathcal{H}$ which
allows us to exploit this gap. For the case of linear classifiers, this was
the $\ell_{2}$ measured aspect ratio, $\gamma({\mathcal{D}})$.

##### Kernel Classifiers:

A natural choice of a more general hypothesis class would be Kernel
Classifiers, which are linear classifiers that operate in an embedded space,
$H$. The main difficulty in expanding our lower bound to this more general
setting comes from the behavior near the margin: the effects of the robustness
radius in the embedded space are considerably less behaved than they are in
the standard linear case. Nevertheless, we leave this as an important avenue
for future work.

##  4 Upper Bounds

Algorithm 1 Adversarial-Perceptron

1: Input: $S=\\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\\}\sim{\mathcal{D}}^{n},$

2: $w\leftarrow 0$

3: for $i=1\dots n$ do

4: $z=\operatorname*{arg\,min}_{||z-x_{i}||_{p}\leq r}y_{i}\langle w,z\rangle$
{finds adv. ex.}

5: if $\langle w,y_{i}z\rangle\leq 0$ {checks label} then

6: $w\leftarrow w+y_{i}z$ {perceptron update}

7: end if

8: end for

9: return $f_{w,0}$

Figure 2: An algorithm combining adversarial training with the perceptron
algorithm. For each $(x_{i},y_{i})$, we first attack it, to get $z$. If $z$ is
labeled incorrectly, we do a perceptron update using $z$.

In the previous section, we showed that for any algorithm, there is some
distribution ${\mathcal{D}}\in{\mathcal{F}}_{r,\rho}$ that is difficult (i.e.
requires high sample complexity) to learn robustly. A natural follow-up
question is: what about distributions for which the margin, $\gamma$ is very
large compared to $r$.

Observe that in Figure 1 the robustness radius $r$ is very close to the
margin. In particular, we can find adversarial examples from $S^{+}$ and
$S^{-}$ that are very close to the decision boundary $f_{rob}$. By contrast,
if $\gamma>>r$, then this no longer holds which suggests that better robust
sample complexities might be possible.

In this section, we will describe a subset of ${\mathcal{F}}_{r,\rho}$ that
can be learned with expected loss $O(\frac{1}{n})$, thus matching the standard
sample complexity up to a constant factor. To do so, we will introduce a novel
concept: the robust margin. The basic intuition is that distributions for
which the margin greatly exceeds the robustness radius are precisely
distributions with a large robust margin. We use the following notation.

Observe that if ${\mathcal{D}}$ is a linearly $r$-separated distribution, then
${\mathcal{D}}$ must also be linearly separable. As earlier, let
$S^{+},S^{-}\subset\mathbb{R}^{d}$ denote the positively and negatively
labeled examples from ${\mathcal{D}}$. We now define

$S_{r}^{+}=\cup_{s\in S^{+}}B_{p}(s,r)\text{ and }S_{r}^{-}=\cup_{s\in
S^{-}}B_{p}(s,r).$ (1)

It follows that the decision boundary of any linear classifier with perfect
robustness over ${\mathcal{D}}$ must separate $S_{r}^{+}$ and $S_{r}^{-}$. We
now define the robust margin as a measurement of this separation.

######  Definition 17.

Let ${\mathcal{D}}$ be a linearly $r$-separable distribution over
$\mathbb{R}^{d}\times\\{\pm 1\\}$. Let $S_{r}^{+}$ and $S_{r}^{-}$ be as
above. Then ${\mathcal{D}}$ has robust margin $\gamma_{r}$ if $\gamma_{r}$ is
the largest real number such that there exists a linear classifier $f_{w,b}$
with the following properties:

1\. $f_{w,b}$ has perfect astuteness. That is,
$\mathcal{L}_{r}(f_{w,b},{\mathcal{D}})=0$.

2\. Let $H_{w,b}=\\{x:\langle x,w\rangle=b\\}$ denote the decision boundary of
$f_{w,b}$. Then for all $x\in(S_{r}^{+}\cup S_{r}^{-})$, $x$ has $\ell_{2}$
distance at least $\gamma$ from $H_{w,b}$. That is,

$\inf_{x\in S_{r}^{+}\cup S_{r}^{-}}\inf_{z\in H_{w,b}}||x-z||_{2}\geq\gamma.$

We let $\gamma_{r}({\mathcal{D}})$ denote the margin of ${\mathcal{D}}$, and
say that such a distribution is $r,\gamma_{r}$-separated.

It is crucial to note that although adversarial perturbations are measured in
$\ell_{p}$, the robust margin is measured in $\ell_{2}$. This is because while
the metric $\ell_{p}$ plays a role in constructing $B(x,r)$, it can be
completely disregarded once the sets $S_{r}^{+}$ and $S_{r}^{-}$ are
considered, as any hyperplane separating $S_{r}^{+}$ and $S_{r}^{-}$ will have
perfect robustness.

We now define the robust aspect ratio, which is the robust analog of standard
aspect ratio.

######  Definition 18.

Let ${\mathcal{D}}$ be a distribution over $\mathbb{R}^{d}\times\\{\pm 1\\}$.
Then the robust aspect ratio of ${\mathcal{D}}$, $\rho_{r}({\mathcal{D}})$ is
defined as

$\rho_{r}({\mathcal{D}})=\frac{diam_{2}(S_{r}^{+}\cup
S_{r}^{-})}{\gamma_{r}({\mathcal{D}})},$

where as before, $diam_{2}(S_{r}^{+}\cup S_{r}^{-})$ denotes its diameter in
the $\ell_{2}$ norm.

We will now show that just as the aspect ratio, $\rho({\mathcal{D}})$,
characterized the sample complexity for standard classification, the robust
aspect ratio, $\rho_{r}({\mathcal{D}})$ will characterize the sample
complexity for robust learning. To do so, we present a perceptron-inspired
algorithm (Algorithm 1) for learning a robust classifier on $r$-separated data
with robust aspect ratio $\rho_{r}$.

The basic idea behind Algorithm 1 is to combine the standard perceptron
algorithm with adversarial training. In particular, we iterate through the
training set and do the following on each point (refer to Algorithm 1 for
precise details).

1\. Find an adversarial example $(z,y_{i})$ by attacking our classifier,
$f_{w,0}$, at $(x_{i},y_{i})$ (line 4). This is a straightforward convex
optimization problem for linear classifiers.

2\. If $f_{w,0}(z)\neq y_{i}$, we update our weight vector with $(z,y_{i})$ by
using the standard perceptron update (lines 5-6).

We have the following upper bound on the expected robust loss of our
algorithm.

######  Theorem 19.

Let ${\mathcal{D}}$ be a distribution with robust aspect ratio
$\rho_{r}({\mathcal{D}})$. Then for any $n>0$, we have

${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]\leq
O(\frac{\rho_{r}({\mathcal{D}})^{2}}{n}),$

where $A_{S}$ denotes the classifier learned by Algorithm 1 from training data
$S$.

Observe that this expected loss is still larger than the expected standard
loss in Theorem 10 as $\rho_{r}({\mathcal{D}})>\rho({\mathcal{D}})$ for any
${\mathcal{D}}$. We also note that this result is not contradictory with our
lower bound; there exist distributions
${\mathcal{D}}\in{\mathcal{F}}_{r,\rho}$ such that
$\gamma_{r}({\mathcal{D}})=0$, and these are precisely the distributions for
which our lower bounds hold.

###  4.1 Generalization to Kernel Classifiers

Algorithm 1 can be thought of as the robust analog to the perceptron
algorithm. We now generalize this algorithm to obtain a robust variant of the
kernel perceptron algorithm. We first briefly review kernel classifiers. A
detailed explanation of our generalized algorithm along with requisite
background material can be found in Appendix D

######  Definition 20.

Let $K:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ be a kernel similarity
function,
$T=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}\subset\mathbb{R}^{d}\times\\{\pm
1\\}$ be a set of labeled points, and $\alpha\in\mathbb{R}^{m}$ be a vector of
$m$ real numbers. Then the kernel classifier with similarity function $K$,
parameters $T,\alpha$, and denoted by $f_{T,K}^{\alpha}$ is defined as

$f_{T,\alpha}^{K}(x)=\begin{cases}+1&\sum_{1}^{m}\alpha_{i}y_{i}K(x_{i},x)\geq
0\\\ -1&\sum_{1}^{m}\alpha_{i}y_{i}K(x_{i},x)<0\end{cases}.$

Conceptually, kernel classifiers are linear classifiers operating in embedded
space. With each kernel similarity function $K$, there is a map
$\phi:\mathbb{R}^{d}\to H$ (where $H$ is some Hilbert space) such that
$K(x,x^{\prime})=\langle\phi(x),\phi(x^{\prime})\rangle$. Thus we can think of
kernel classifiers as having a linear decision boundary in $H$.

We now present an analog of Algorithm 1 that we call the Adversarial Kernel-
Perceptron. The essence of this algorithm has not changed. For each
$(x_{t},y_{t})$ in our training set, we do the following.

1\. Find an adversarial example $(z,y_{i})$ by attacking our classifier,
$f_{T,\alpha}^{K}$, at $(x_{i},y_{i})$ (line 4).

2\. If $f_{T,\alpha}^{K}(z)\neq y_{i}$, we update our weight vector with
$(z,y_{i})$ by appending $(z,y_{i})$ to $T$ (lines 5-6). This corresponds to a
kernel-perceptron update that uses $(z,y_{i})$ instead of $(x_{i},y_{i})$.

Algorithm 2 Adversarial-Kernel-Perceptron

1: Input: $S=\\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\\}\sim{\mathcal{D}}^{n},$
Similarity function, $K$

2: $T\leftarrow\emptyset$, $\alpha\leftarrow 0$

3: for $i=1\dots n$ do

4: $z=\operatorname*{arg\,min}_{||z-x||_{p}\leq r}y_{i}f_{T,\alpha}^{K}(z)$
{finds adv. ex.}

5: if $f_{T,\alpha}^{k}(z)\leq 0${checks label} then

6: $T=T\cup\\{(z,y_{i})\\}$ {kern. percep. update}

7: $\alpha=(1,\dots,1)_{|T|}$

8: end if

9: end for

10: return $f_{T,\alpha}^{K}$

Figure 3: A kernel version of Algorithm 1. We replace the perceptron update
step with a kernel-perceptron update step.

One challenging aspect of this algorithm is minimizing $f_{T,\alpha}^{k}(z)$.
For linear classifiers, this has a closed form solution that utilizes the dual
norm. For arbitrary Kernel classifiers, this is a somewhat more challenging
problem. However, we note that this can be solved using standard optimization
techniques, and in some cases (when $K$ is particularly simple), it can be
solved with basic gradient descent.

Finally, we show that this Algorithm has similar performance to the linear
case. Instead of using the robust aspect ratio, $\rho_{r}({\mathcal{D}})$, to
bound the performance, we will require the robust $K$-aspect ratio, which is
the kernel analog of this quantity. It can be thought of as the robust aspect
ratio in the embedded space $H$. Details about this quantity (along with the
proof of the theorem) can be found in Appendix D.

######  Theorem 21.

Let ${\mathcal{D}}$ be a distribution with robust $K$-aspect ratio
$\rho_{r}^{K}({\mathcal{D}})$. Then for any $n>0$, we have

${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]\leq
O(\frac{\rho_{r}^{K}({\mathcal{D}})^{2}}{n}),$

where $A_{S}$ denotes the classifier learned by Algorithm 2 from training data
$S$.

This result indicates that for small values of $\rho_{r}^{k}({\mathcal{D}})$,
we can achieve a very good robust sample complexity for kernel classifiers.
However, as the size of the perturbations approach this margin, this quantity
goes to infinity. This phenomenon mirrors the linearly separable case, and
suggests that a similar overall dynamic holds for kernel classification. We
leave finding a full generalization (including our lower bound) for a
direction in future work.

## References

  * Ashtiani et al. (2020) Ashtiani, H., Pathak, V., and Urner, R.  Black-box certification and learning under adversarial perturbations.  _CoRR_ , abs/2006.16520, 2020.  URL https://arxiv.org/abs/2006.16520.
  * Attias et al. (2019) Attias, I., Kontorovich, A., and Mansour, Y.  Improved generalization bounds for robust learning.  In Garivier, A. and Kale, S. (eds.), _Algorithmic Learning Theory, ALT 2019, 22-24 March 2019, Chicago, Illinois, USA_ , volume 98 of _Proceedings of Machine Learning Research_ , pp. 162–183. PMLR, 2019\.
  * Bhagoji et al. (2019) Bhagoji, A. N., Cullina, D., and Mittal, P.  Lower bounds on adversarial robustness from optimal transport.  In Wallach, H. M., Larochelle, H., Beygelzimer, A., d’Alché-Buc, F., Fox, E. B., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8-14 December 2019, Vancouver, BC, Canada_ , pp. 7496–7508, 2019.
  * Bhattacharjee & Chaudhuri (2020) Bhattacharjee, R. and Chaudhuri, K.  When are non-parametric methods robust?  _CoRR_ , abs/2003.06121, 2020.  URL https://arxiv.org/abs/2003.06121.
  * Carlini & Wagner (2017) Carlini, N. and Wagner, D. A.  Towards evaluating the robustness of neural networks.  In _2017 IEEE Symposium on Security and Privacy, SP 2017, San Jose, CA, USA, May 22-26, 2017_ , pp. 39–57, 2017.
  * Cullina et al. (2018) Cullina, D., Bhagoji, A. N., and Mittal, P.  Pac-learning in the presence of adversaries.  In Bengio, S., Wallach, H., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems_ , volume 31, pp. 230–241. Curran Associates, Inc., 2018.
  * Dan et al. (2020) Dan, C., Wei, Y., and Ravikumar, P.  Sharp statistical guarantees for adversarially robust gaussian classification.  _CoRR_ , abs/2006.16384, 2020.  URL https://arxiv.org/abs/2006.16384.
  * Diakonikolas et al. (2020) Diakonikolas, I., Kane, D. M., and Manurangsi, P.  The complexity of adversarially robust proper learning of halfspaces with agnostic noise.  _CoRR_ , abs/2007.15220, 2020.  URL https://arxiv.org/abs/2007.15220.
  * Dobriban et al. (2020) Dobriban, E., Hassani, H., Hong, D., and Robey, A.  Provable tradeoffs in adversarially robust classification.  _CoRR_ , abs/2006.05161, 2020.  URL https://arxiv.org/abs/2006.05161.
  * Freund & Schapire (1999) Freund, Y. and Schapire, R. E.  Large margin classification using the perceptron algorithm.  _Mach. Learn._ , 37(3):277–296, 1999.
  * Hein & Andriushchenko (2017) Hein, M. and Andriushchenko, M.  Formal guarantees on the robustness of a classifier against adversarial manipulation.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 30_ , pp. 2266–2276. Curran Associates, Inc., 2017.
  * Katz et al. (2017) Katz, G., Barrett, C. W., Dill, D. L., Julian, K., and Kochenderfer, M. J.  Towards proving the adversarial robustness of deep neural networks.  In _Proceedings First Workshop on Formal Verification of Autonomous Vehicles, FVAV@iFM 2017, Turin, Italy, 19th September 2017._ , pp. 19–26, 2017.
  * Khim & Loh (2018) Khim, J. and Loh, P.  Adversarial risk bounds for binary classification via function transformation.  _CoRR_ , abs/1810.09519, 2018.  URL http://arxiv.org/abs/1810.09519.
  * Liu et al. (2017) Liu, Y., Chen, X., Liu, C., and Song, D.  Delving into transferable adversarial examples and black-box attacks.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_ , 2017.
  * Montasser et al. (2019) Montasser, O., Hanneke, S., and Srebro, N.  VC classes are adversarially robustly learnable, but only improperly.  In Beygelzimer, A. and Hsu, D. (eds.), _Conference on Learning Theory, COLT 2019, 25-28 June 2019, Phoenix, AZ, USA_ , volume 99 of _Proceedings of Machine Learning Research_ , pp. 2512–2530. PMLR, 2019\.
  * Papernot et al. (2016a) Papernot, N., McDaniel, P. D., Jha, S., Fredrikson, M., Celik, Z. B., and Swami, A.  The limitations of deep learning in adversarial settings.  In _IEEE European Symposium on Security and Privacy, EuroS &P 2016, Saarbrücken, Germany, March 21-24, 2016_, pp. 372–387, 2016a.
  * Papernot et al. (2016b) Papernot, N., McDaniel, P. D., Wu, X., Jha, S., and Swami, A.  Distillation as a defense to adversarial perturbations against deep neural networks.  In _IEEE Symposium on Security and Privacy, SP 2016, San Jose, CA, USA, May 22-26, 2016_ , pp. 582–597, 2016b.
  * Papernot et al. (2017) Papernot, N., McDaniel, P. D., Goodfellow, I. J., Jha, S., Celik, Z. B., and Swami, A.  Practical black-box attacks against deep learning systems using adversarial examples.  _ASIACCS_ , 2017.
  * Raghunathan et al. (2018) Raghunathan, A., Steinhardt, J., and Liang, P.  Certified defenses against adversarial examples.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.
  * Raghunathan et al. (2020) Raghunathan, A., Xie, S. M., Yang, F., Duchi, J. C., and Liang, P.  Understanding and mitigating the tradeoff between robustness and accuracy.  _CoRR_ , abs/2002.10716, 2020.  URL https://arxiv.org/abs/2002.10716.
  * Schmidt et al. (2018) Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Madry, A.  Adversarially robust generalization requires more data.  In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurIPS 2018, 3-8 December 2018, Montréal, Canada_ , pp. 5019–5031, 2018.
  * Sinha et al. (2018) Sinha, A., Namkoong, H., and Duchi, J. C.  Certifying some distributional robustness with principled adversarial training.  In _6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings_ , 2018.
  * Szegedy et al. (2014) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I. J., and Fergus, R.  Intriguing properties of neural networks.  In _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , 2014.
  * Tsipras et al. (2019) Tsipras, D., Santurkar, S., Engstrom, L., Turner, A., and Madry, A.  Robustness may be at odds with accuracy.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019_. OpenReview.net, 2019.
  * Vapnik (1998) Vapnik, V. N.  _Statistical Learning Theory_.  Wiley-Interscience, 1998.
  * Wang et al. (2018) Wang, Y., Jha, S., and Chaudhuri, K.  Analyzing the robustness of nearest neighbors to adversarial examples.  In _Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsmässan, Stockholm, Sweden, July 10-15, 2018_ , pp. 5120–5129, 2018.
  * Yang et al. (2019) Yang, Y., Rashtchian, C., Wang, Y., and Chaudhuri, K.  Adversarial examples for non-parametric methods: Attacks, defenses and large sample limits.  _CoRR_ , abs/1906.03310, 2019.  URL http://arxiv.org/abs/1906.03310.
  * Yang et al. (2020) Yang, Y.-Y., Rashtchian, C., Zhang, H., Salakhutdinov, R., and Chaudhuri, K.  A closer look at accuracy vs. robustness, 2020.
  * Yin et al. (2019) Yin, D., Ramchandran, K., and Bartlett, P. L.  Rademacher complexity for adversarially robust generalization.  In Chaudhuri, K. and Salakhutdinov, R. (eds.), _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 7085–7094. PMLR, 2019.  URL http://proceedings.mlr.press/v97/yin19b.html.

##  Appendix A Expanded summary of (Dan et al., 2020)

In this section, we derive the formulation of Theorem 16 directly from their
results. In particular, their results are not stated in terms of $L_{rob}$ and
$L_{std}$, and are instead framed in terms of different parameters. To account
for this, we first review these alternative parameters, and then show how the
statements in Theorem 16 can be

Recall, that (Dan et al., 2020) consider the setting in which the data
distribution ${\mathcal{D}}_{\mu,\Sigma}$ can be characterized as a pair of
Gaussians in $\mathbb{R}^{d}$, ${\mathcal{N}}(\mu,\Sigma)$ and
${\mathcal{N}}(-\mu,\Sigma)$, that are symmetric about the origin with each of
them representing one label class. They consider robustness measured in any
normed metric in $\mathbb{R}^{d}$, including the $\ell_{p}$ norm for
$p\in[1,\infty]$.

For any such distribution (and robustness radius $r$), they introduce
parameters $s_{rob}(\mu,\Sigma)$ and $s_{std}(\mu,\Sigma)$, which they refer
to as the robust and standard signal-to-noise ratios respectively, that are
defined as follows:

$s_{std}(\mu,\Sigma)=2\sqrt{\mu^{t}\Sigma^{-1}\mu},$
$s_{rob}(\mu,\Sigma)=\min_{||z||_{p}\leq
r}2\sqrt{(\mu-z)^{t}\Sigma^{-1}(\mu-z)},$

where $r$ represents the robustness radius and $\ell_{p}$ is the distance norm
under which adversarial perturbations are measured.

They then show that these parameters fully characterize the sample complexity
for robust and standard learning respectively. They express this through the
following results:

  1. 1.

Let $\Phi$ denote the cumulative density function of the standard normal
distribution, and let $\overline{\Phi}(x)=1-\Phi(x)$. Then for any
${\mathcal{D}}_{\mu,\Sigma}$,

     * •

the optimally accurate classifier has standard loss
$\overline{\Phi}(\frac{1}{2}s_{std})$.

     * •

the optimally robust classifier has robust loss
$\overline{\Phi}(\frac{1}{2}s_{rob})$.

  2. 2.

For any learning algorithm, there exists some mixture of
${\mathcal{D}}_{\mu,\Sigma}$ such that the expected robust loss is at least
$\Omega(e^{(-\frac{1}{8}+o(1))s_{rob}^{2}}\frac{d}{n})$.

  3. 3.

By contrast, for any distribution ${\mathcal{D}}_{\mu,\Sigma}$, it is possible
to learn a classifier with expected standard loss at most
$O(s_{std}e^{-\frac{1}{8}s_{std}^{2}}\frac{d}{n})$.

  4. 4.

Thus, by (2.) and (3.), the gap between the robust sample complexity and the
standard complexity can be bounded as

$gap\geq\Omega\left(\frac{e^{(-\frac{1}{8}+o(1))s_{rob}^{2}}\frac{d}{n}}{s_{std}e^{-\frac{1}{8}s_{std}^{2}}\frac{d}{n}}\right)\simeq\Omega(e^{\frac{-1}{8}(s_{std}^{2}-s_{rob}^{2})}).$

They then qualitatively analyze this gap, and observe that for large values of
$\mu$ and large values of $r$, this gap can be arbitrarily large, even as a
function of $d$, the dimension.

We now show how to convert (2.), (3.), and (4.) into the statements appearing
in Theorem 16. As before, let us define $L_{std}$ and $L_{rob}$ as the best
possible standard and robust losses for ${\mathcal{D}}_{\mu,\Sigma}$
respectively. In particular, by (1.), we have

$L_{std}=\overline{\Phi}(\frac{1}{2}s_{std}^{2}),\text{ and
}L_{rob}=\overline{\Phi}(\frac{1}{2}s_{rob}^{2}).$

We now express the bounds in (2.) and (4.) in terms of $L_{std}$ and
$L_{rob}$. To do so, we use the well known inequality bounding
$\overline{\Phi}(x)$ as

$\Omega(\frac{x}{x^{2}+1}e^{-x^{2}/2})<\Phi(x)<O(\frac{e^{-x^{2}/2}}{x}).$

Substituting this into (2.) through (4.) imply the following, alternative
forms.

  1. 2.

For any learning algorithm, there exists some mixture of Gaussians,
${\mathcal{D}}_{\mu,\Sigma}$ such that the expected robust loss is at least
$\Omega(L_{rob}\frac{d}{n}).$

  2. 3.

For any distribution ${\mathcal{D}}_{\mu,\Sigma}$, it is possible to learn a
classifier with expected standard loss at most $O(L_{std}\frac{d}{n})$.

  3. 4.

By (2.) and (3.), the gap between robust sample complexity and standard sample
complexity can be expressed as

$gap\geq\Omega(\frac{L_{rob}}{L_{std}}).$

Together, these three statements comprise Theorem 16.

###  A.1 The limiting case

While a core difference between our works is that we consider separated
distributions whereas Gaussians are non-separated, we now consider the
limiting case in which a pair of Gaussians appear separated. To do this, we
will consider a case in which $L_{rob}$ is small, and $n\sim
O(\frac{1}{L_{rob}})$. In this case, with high probability, a sample of size
$n$ will appear linearly $r$-separated. Examining the bound in part 1 of
Theorem 16, we see that their lower bound on the expected robust loss reduces
to $O(\frac{1}{n}\frac{d}{n})=O(\frac{d}{n^{2}})$, which is significantly
weaker than ours (Theorem 14). Thus, considering Gaussians that appear
linearly $r$-separated does not generalize to the general, linearly
$r$-separated case.

##  Appendix B Proof of Theorem 14

We begin by broadly outlining our proof of Theorem 14. Let $\Pi$ be a
probability distribution over ${\mathcal{F}}_{r,\rho}$, and let $A$ be a
learning algorithm that returns a linear classifier.

  1. 1.

Sample ${\mathcal{D}}\sim\Pi$.

  2. 2.

Sample $S\sim{\mathcal{D}}^{n}$.

  3. 3.

Learn the classifier $A_{S}$ using algorithm $A$ and training sample $S$.

  4. 4.

Evaluate $A_{S}$ on ${\mathcal{D}}$. That is, compute
$\mathcal{L}_{r}(A_{S},{\mathcal{D}})$.

The basic idea of our proof is to show that for an appropriate choice of
$\Pi$, the overall expected loss of this procedure,
$\mathcal{L}_{r}(A_{S},{\mathcal{D}})$, satisfies

${\mathbb{E}}_{D\sim\Pi}[{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]]\geq\Omega(\frac{d}{n}).$

Our primary method for doing this is switching expectations. In particular,
observe that

${\mathbb{E}}_{D\sim\Pi}[{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]]={\mathbb{E}}_{S\sim\Sigma}[{\mathbb{E}}_{{\mathcal{D}}\sim\Pi|S}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]],$

where $\Sigma$ denotes the distribution over all $S$ obtained from first
sampling ${\mathcal{D}}\sim\Pi$ and then sampling $S\sim{\mathcal{D}}^{n}$,
and $\Pi|S$ denotes the posterior distribution of ${\mathcal{D}}$ after
observing $S$. It then suffices to bound the quantity
${\mathbb{E}}_{{\mathcal{D}}\sim\Pi|S}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]$,
which is a significantly more tractable problem since we no longer need to
deal with any specifics of the Algorithm $A$. In particular, $S$ is fixed in
this expectation and consequently $A_{S}$ is just a fixed linear classifier.
This bound subsequently follows from the distribution $\Pi|S$ having enough
“variation” for this expectation to be sufficient large.

Our proof will have the following main steps, each of which is given its own
subsection.

  1. 1.

In section B.1, we construct the distribution $\Pi$, and prove several
important properties about it.

  2. 2.

In section B.2, we show that the desired property of $\Pi$ holds, by bounding
${\mathbb{E}}_{{\mathcal{D}}\sim\Pi|S}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})].$

###  B.1 Constructing $\Pi$

We let $r$ be a fixed robustness radius, and $\ell_{p}$ be our norm with which
we measure robustness. Our construction of $\Pi$ is a somewhat technical and
lengthy process. We will organize this construction into 4 subsections,
outlined here:

  * •

In section B.1.1, we define the distribution ${\mathcal{D}}_{a}$,
characterized by parameter $a\in[0,1]^{d}$. This forms the basis for
constructing $\Pi$, which will comprise of distributions ${\mathcal{D}}_{a}$
for certain choices of $a$. We also show that ${\mathcal{D}}_{a}$ is linearly
$r$-separated.

  * •

In section B.1.2, we define the constant $\Delta$, which will be essential for
specifying which values of parameter $a$ are permissible.

  * •

In section B.1.3, we define functions
$g_{1},g_{2}:[0,\frac{\Delta}{3}]\to[0,\frac{\Delta}{3}]$ that will be used to
construct $\Pi$.

  * •

In section B.1.4, we finally put together the previous 3 sections and
construct $\Pi$. We also show that any ${\mathcal{D}}_{a}\sim\Pi$ satisfies
$\rho({\mathcal{D}}_{a})\leq C$.

####  B.1.1 Defining ${\mathcal{D}}_{a}$

Let $e_{1},e_{2},\dots,e_{d}$ denote the standard normal basis in
$\mathbb{R}^{d}$. Define $v_{i}=Re_{i}$ and
$u=\frac{R}{\sqrt{d}}\sum_{1}^{d}e_{i}$, where
$R=\frac{9rd^{1/q}}{2\sqrt{d}}$. It will also be convenient to define the
following function, which we will frequently use throughout the entirety of
the appendix.

######  Definition 22.

For $1\leq l\leq\infty$, let $f_{l}:[0,1]^{d}\to\mathbb{R}^{+}$ be the
function defined as

$f_{l}(a)=\sqrt[l]{\sum_{1}^{d}|\frac{1}{\sqrt{d}}+\overline{a}-a_{i}|^{l}},$

where $\overline{a}=\frac{1}{d}\sum_{1}^{d}a_{i}$. For $l=\infty$, we take the
convention that $\sqrt[\infty]{\sum_{1}^{d}|x_{i}|^{\infty}}=\max_{1\leq i\leq
d}|x_{i}|.$

To define ${\mathcal{D}}_{a}$, we first define the concept of a line segment
in $\mathbb{R}^{d}$.

######  Definition 23.

Let $x_{1},x_{2}\in\mathbb{R}^{d}$ be two points. A line segment joining
$x_{1},x_{2}$ is defined as one of the following four sets.

  * •

$(x_{1},x_{2})=\\{tx_{1}+(1-t)x_{t}:0<t<1\\}$.

  * •

$[x_{1},x_{2})=\\{tx_{1}+(1-t)x_{t}:0\leq t<1\\}$.

  * •

$(x_{1},x_{2}]=\\{tx_{1}+(1-t)x_{t}:0<t\leq 1\\}$.

  * •

$[x_{1},x_{2}]=\\{tx_{1}+(1-t)x_{t}:0\leq t\leq 1\\}$.

We will always distinguish which set we mean by using the notation above. In
all cases, $x_{1},x_{2}$ are said to be the endpoints of the line segment.

We now define ${\mathcal{D}}_{a}$.

######  Definition 24.

Let $a\in[0,1]^{d}$ be a vector, and let
$\overline{a}=\frac{1}{d}\sum_{1}^{d}a_{i}$. Set
$\lambda_{a}=\frac{r}{R}f_{q}(a)$, where $q$ is the dual norm of $p$. Assume
that for all $1\leq i\leq d$, $a_{i}>\lambda_{a}$ (i.e. we only
${\mathcal{D}}_{a}$ for $a$ for which this holds). Let $S^{-}$ and $S^{+}$ be
two sets of $d$ disjoint line segments (as defined in Definition 23) defined
as

$S^{-}=\\{[v_{i},v_{i}+(a_{i}-\lambda_{a})u):1\leq i\leq d\\},$
$S^{+}=\\{(v_{i}+(a_{i}+\lambda_{a})u,v_{i}+u]:1\leq i\leq d\\}.$

Then $D_{a}$ is defined as the probability distribution of random variables
$(X,Y)$ where

  * •

$X$ is chosen by the following random procedure. First, sample an arbitrary
segment from $S^{+}\cup S^{-}$ with each segment chosen with probability
proportional to its $\ell_{2}$ length. Next, $X$ is selected from the uniform
distribution over the chosen line segment. In particular, the probability that
$X$ lies on any interval on any line segment contained within $S^{+}\cup
S^{-}$ is directly proportional to the length of the interval.

  * •

$Y$ is $-1$ if $X\in\cup S^{-}$ and $+1$ if $X\in\cup S^{+}$.

Figure 4: An illustration of ${\mathcal{D}}_{a}$ in two dimensions. $S^{-}$ is
shown in red, and $S^{+}$ is shown in blue. The decision boundary, $H_{a}$, of
the optimal linear classifier, $f_{w^{a},1}$, is shown in purple.

We include an example of such a distribution in Figure 4. Next, we explicitly
compute a linear classifier that linearly $r$-separates ${\mathcal{D}}_{a}$.

######  Definition 25.

Let $a\in[0,1]^{d}$, and let $\overline{a}=\sum_{i=1}^{d}a_{i}.$ Then let
$w^{a}$ be defined as

$w_{i}^{a}=\frac{1}{R}-\frac{da_{i}}{R\sqrt{d}+dR\overline{a}}.$

######  Lemma 26.

$w^{a}$ satisfies $\langle w^{a},u\rangle=\frac{d}{\sqrt{d}+d\overline{a}}$
and $\langle w^{a},v_{i}+a_{i}u\rangle=1,$ for all $1\leq i\leq d.$

###### Proof.

By the definitions of $v_{i},u$, we have that

$\begin{split}\langle w^{a},u\rangle&=\langle
w^{a},\frac{1}{\sqrt{d}}\sum_{1}^{d}v_{i}\rangle\\\
&=\frac{1}{\sqrt{d}}\sum_{1}^{d}Rw_{i}^{a}\\\
&=\frac{1}{\sqrt{d}}\sum_{1}^{d}1-\frac{da_{i}}{\sqrt{d}+d\overline{a}}\\\
&=\frac{1}{\sqrt{d}}\sum_{1}^{d}\frac{\sqrt{d}+d\overline{a}-da_{i}}{\sqrt{d}+d\overline{a}}\\\
&=\frac{1}{\sqrt{d}}\frac{d\sqrt{d}}{\sqrt{d}+d\overline{a}}=\frac{d}{\sqrt{d}+d\overline{a}},\end{split}$

Which proves the first claim. Next, we also have that $\langle
w^{a},v_{i}\rangle=Rw_{i}^{a}$. Summing these, we get

$Rw_{i}^{a}+\frac{da_{i}}{\sqrt{d}+d\overline{a}}=1-\frac{da_{i}}{\sqrt{d}+d\overline{a}}+\frac{da_{i}}{\sqrt{d}+d\overline{a}}=1,$

as desired. ∎

We now prove that ${\mathcal{D}}_{a}$ is linearly $r$-separated.

######  Lemma 27.

${\mathcal{D}}_{a}$ is linearly $r$-separated by the classifier $f_{w_{a},1}$.

###### Proof.

Let $H_{a}$ denote the hyperplane passing through $\\{v_{i}+a_{i}u:1\leq i\leq
d\\}$. By Lemma 26, $H_{a}$ is the decision boundary of $f_{w_{a},1}$.
Referring to Figure 4, we see that $\cup S^{+}$ lies entirely above $H_{a}$
while the set $\cup S^{-}$ lies entirely below the hyperplane $H_{a}$, which
the classifier $f_{w^{a},1}$ has accuracy $1$ with respect to
${\mathcal{D}}_{a}$. It suffices to show that $f_{w^{a},1}$ is robust
everywhere. In order to do this, we must show that all points in the support
of ${\mathcal{D}}_{a}$ have $\ell_{p}$ distance at least $r$ from $H_{a}$.

Fix any $1\leq i\leq d$. Since the $\ell_{p}$ distance metric is invariant
under translation and scales linearly with dilations, it follows that the
point $x_{i}=v_{i}+(a_{i}-\lambda_{a})u$ is the closest point on the segment
$[v_{i},v_{i}+(a_{i}-\lambda_{a})u)$ to $H_{a}$. Suppose $x_{i}$ has distance
$D$ under the $\ell_{p}$ norm to $H_{a}$. Then the key observation is that the
$\ell_{p}$ ball, $B_{p}(x_{i},D)$, must be tangent to $H_{a}$. Expressing this
as an equation, we have $\max_{z\in B_{p}(x_{i},D)}\langle z,w^{a}\rangle=1,$
which can be re-written as

$\max_{||z-x_{i}||_{p}\leq D}\langle z-x_{i},w^{a}\rangle=1-\langle
x_{i},w^{a}\rangle.$

By Lemma 26 , $\langle w^{a},u\rangle=\frac{d}{\sqrt{d}+d\overline{a}}$ and
$\langle w^{a},v_{i}+a_{i}u\rangle=1$. Substituting this, we see that

$\begin{split}1-\langle x_{i},w^{a}\rangle&=1-\langle
v_{i}+a_{i}u-\lambda_{a}u,w^{a}\rangle\\\ &=1-\langle
v_{i}+a_{i}u,w^{a}\rangle+\langle\lambda_{a}u,w^{a}\rangle\\\
&=\langle\lambda_{a}u,w^{a}\rangle\\\
&=\frac{d\lambda_{a}}{\sqrt{d}+d\overline{a}}.\end{split}$

However, by using the dual norm, we see that $\max_{||z-x_{i}||_{p}\leq
D}\langle z-x_{i},w^{a}\rangle=D||w^{a}||_{q}$. Thus it follows that

$\begin{split}D&=\frac{d\lambda_{a}}{(\sqrt{d}+d\overline{a})||w^{a}||_{q}}\\\
&=\frac{d\frac{r}{R}f_{q}(a)}{(\sqrt{d}+d\overline{a})||w^{a}||_{q}}\\\
&=\frac{d\frac{r}{R}\sqrt[q]{\sum_{1}^{d}|\frac{1}{\sqrt{d}}+\overline{a}-a_{i}|^{q}}}{(\sqrt{d}+d\overline{a})||w^{a}||_{q}}\\\
&=\frac{r\sqrt[q]{\sum_{1}^{d}|\frac{1}{R}\frac{\sqrt{d}+d\overline{a}-da_{i}}{(\sqrt{d}+d\overline{a})}|^{q}}}{||w^{a}||_{q}}\\\
&=\frac{r||w^{a}||_{q}}{||w^{a}||_{q}}=r.\end{split}$

We can use an analogous argument holds for $v_{i}+(a_{i}+r_{a})u$, the closest
point to $H_{a}$ in $S^{+}$. Thus each point in the support of $D^{a}$ has
distance strictly larger than $r$ (as the endpoints were not included) to
$H_{a}$. Consequently $f_{w^{a},1}$ linearly $r$-separates $D^{a}$, as
desired. ∎

####  B.1.2 Defining $\Delta$

Now that we have defined ${\mathcal{D}}_{a}$, we turn our attention to
defining $\Pi$, which requires us to specify a distribution over valid choices
of $a$. In particular, although ${\mathcal{D}}_{a}$ is defined for
$a\in[0,1]^{d}$, we will require a more stringent condition on $a$ for our
construction to work. To this end, we begin by defining $\Delta$, a key
parameter that characterizes the domain of $a$. To define $\Delta$, we use the
following lemma.

######  Lemma 28.

There exists a real number $\Delta>0$ such that for all $l\in\\{2,q\\}$, and
for all $a\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$,

$||\nabla f_{l}(a)||_{2}\leq\frac{1}{d^{2}\sqrt{d}},$

where $f_{l}$ is as defined in Definition 22.

###### Proof.

Since $1\leq q<\infty$, we see that for both choices of $l$, the function
$h_{l}(x)=(\frac{1}{\sqrt{d}}-x)^{l}$ is a convex function for
$x\in[-\frac{1}{2\sqrt{d}},\frac{1}{2\sqrt{d}}]$. Thus, if
$\sum_{1}^{d}x_{i}=0$, then by Jensen’s inequality,
$\sum_{1}^{d}h_{l}(x_{i})\geq\sum_{1}^{d}h_{l}(0)$. Applying this, we see that
for all $l\in\\{2,q\\}$ and for all
$a\in[\frac{1}{2}-\frac{1}{4\sqrt{d}},\frac{1}{2}+\frac{1}{4\sqrt{d}}]^{d}$,

$\begin{split}f_{l}(a)&=\sqrt[l]{\sum_{1}^{d}|\frac{1}{\sqrt{d}}+\overline{a}-a_{i}|^{l}}\\\
&=\sqrt[l]{\sum_{1}^{d}\left(\frac{1}{\sqrt{d}}+\overline{a}-a_{i}\right)^{l}}\\\
&=\sqrt[l]{\sum_{1}^{d}h_{l}(a_{i}-\overline{a})}\\\
&\geq\sqrt[l]{\sum_{1}^{d}h_{l}(0)}\\\
&=f_{l}((\frac{1}{2},\frac{1}{2},\dots,\frac{1}{2})),\end{split}$

with the first equality holding since $\overline{a}-a_{i}<\frac{1}{\sqrt{d}}$
and the first inequality holding since $\sum_{1}^{d}a_{i}-\overline{a}=0$.
Thus $f_{l}(a)$ must be locally minimized when
$a=(\frac{1}{2},\frac{1}{2},\dots,\frac{1}{2})$, and it follows that

$||\nabla f_{l}(\frac{1}{2},\frac{1}{2},\dots,\frac{1}{2})||_{2}=0,\text{ for
}l=2,q.$

Now observe that the map $H(a)=\max_{l\in\\{2,q\\}}||\nabla f_{l}(a)||_{2}$ is
a continuous map as long as $|a_{i}-\overline{a}|<\frac{1}{\sqrt{d}}$ for all
$1\leq i\leq d$. Thus there exists an open neighborhood $U$ about
$(\frac{1}{2},\frac{1}{2},\dots,\frac{1}{2})$ such that
$H(a)\leq\frac{1}{d^{2}\sqrt{d}}$ for all $a\in U$. Taking $\Delta$ so that
$[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}\subseteq U$ suffices. ∎

######  Definition 29.

Let $\Delta$ be any constant for which Lemma 28 holds. In particular, $\Delta$
only depends on $\ell_{p}$, the robustness norm, and $d$, the dimension.

####  B.1.3 Defining $g_{1}$ and $g_{2}$

In this section, we define functions
$g_{1},g_{2}:[0,\frac{\Delta}{3}]\to[0,\frac{\Delta}{3}]$ which we will use to
specify $\Pi$. Before defining $g_{1}$ and $g_{2}$, we will first prove
several technical lemmas.

######  Lemma 30.

Let $I\subseteq\mathbb{R}$ be an interval, and $\Phi:I\to\mathbb{R}$ be a
strictly convex function. For any $s\in\mathbb{R}$ and $t\geq 0$, let
$\Phi_{s}(t)=\Phi(s-t)+\Phi(s+t)$. Then $\Phi_{s}$ is a strictly increasing
function.

###### Proof.

Fix $s$, and let $0\leq t_{1}<t_{2}$. Then we see that by Jensen’s inequality
(for strictly convex functions),

$\Phi(s+t_{1})<\frac{(t_{2}-t_{1})\Phi(s+t_{2})}{t_{1}+t_{2}}+\frac{2t_{1}\Phi(s-t_{1})}{t_{1}+t_{2}},$

and

$\Phi(s-t_{1})<\frac{(t_{2}-t_{1})\Phi(s-t_{2})}{t_{1}+t_{2}}+\frac{2t_{1}\Phi(s+t_{1})}{t_{1}+t_{2}}.$

Summing these inequalities, we see that

$\begin{split}\Phi_{s}(t_{1})&=\Phi(s-t_{1})+\Phi(s+t_{1})\\\
&<\frac{(t_{2}-t_{1})\Phi(s+t_{2})}{t_{1}+t_{2}}+\frac{2t_{1}\Phi(s-t_{1})}{t_{1}+t_{2}}+\frac{(t_{2}-t_{1})\Phi(s-t_{2})}{t_{1}+t_{2}}+\frac{2t_{1}\Phi(s+t_{1})}{t_{1}+t_{2}}\\\
&=\frac{t_{2}-t_{1}}{t_{1}+t_{2}}(\Phi(s+t_{2})+\Phi(s-t_{2}))+\frac{2t_{1}}{t_{1}+t_{2}}(\Phi(s-t_{1})+\Phi(s+t_{1}))\\\
&=\frac{t_{2}-t_{1}}{t_{1}+t_{2}}\Phi_{s}(t_{2})+\frac{2t_{1}}{t_{1}+t_{2}}\Phi_{s}(t_{1}).\end{split}$

Rearranging this yields $\Phi_{s}(t_{1})<\Phi_{s}(t_{2})$, as desired. ∎

######  Lemma 31.

Let $I\subseteq\mathbb{R}$ be an interval, $\Phi:I\to\mathbb{R}$ be a strictly
convex continuous function, and $x,y,z\in I$ be real numbers with $x<y<z$. Let
$\epsilon>0$ be such that $x-\epsilon\in I$ and $y+\epsilon\leq z-\epsilon$.
Then there exist unique $\delta,\gamma>0$ such that the following hold:

$\delta+\gamma=\epsilon,$
$\Phi(x-\delta)+\Phi(y+\epsilon)+\Phi(z-\gamma)=\Phi(x)+\Phi(y)+\Phi(z)$

###### Proof.

Fix any $\epsilon$ satisfying the desired conditions, and define
$\Theta:[0,\epsilon]\to\mathbb{R}$ as
$\Theta(t)=\Phi(x-t)+\Phi(y+\epsilon)+\Phi(z+t-\epsilon)$. Then, utilizing the
definition of $\Phi_{s}$ from Lemma 30, we see that

$\Theta(t)=\Phi_{\frac{x+z-\epsilon}{2}}(\frac{z-x-\epsilon}{2}+t)+\Phi(y+\epsilon).$

By Lemma 30, it follows that $\Theta$ is strictly increasing in $t$, and since
$\Phi$ is continuous, so is $\Theta$. Next, we bound $\Theta(0)$ and
$\Theta(\epsilon)$ to put us in the configuration to apply the intermediate
value theorem. To bound $\Theta(0)$, we have

$\begin{split}\Theta(0)&=\Phi(x)+\Phi(y+\epsilon)+\Phi(z-\epsilon)\\\
&=\Phi(x)+\Phi_{\frac{y+z}{2}}(\frac{z-y}{2}-\epsilon)\\\
&<\Phi(x)+\Phi_{\frac{y+z}{2}}(\frac{z-y}{2})\\\
&=\Phi(x)+\Phi(y)+\Phi(z),\end{split}$

and to bound $\Theta(\epsilon)$, we have

$\begin{split}\Theta(\epsilon)&=\Phi(x-\epsilon)+\Phi(y+\epsilon)+\Phi(z)\\\
&=\Phi_{\frac{x+y}{2}}(\frac{y-x}{2}+\epsilon)+\Phi(z)\\\
&>\Phi_{\frac{x+y}{2}}(\frac{y-x}{2})+\Phi(z)\\\
&=\Phi(x)+\Phi(y)+\Phi(z).\end{split}$

Together, these equations imply
$\Theta(0)<\Phi(x)+\Phi(y)+\Phi(z)<\Theta(\epsilon)$. Since $\Theta$ is
strictly increasing and continuous, there exists a unique
$\delta\in[0,\epsilon]$ such that $\Theta(\delta)=\Phi(x)+\Phi(y)+\Phi(z)$.
Setting $\gamma=\epsilon-\delta$, we see that

$\Theta(\delta)=\Phi(x-\delta)+\Phi(y+\epsilon)+\Phi(z-\gamma)=\Phi(x)+\Phi(y)+\Phi(z),$

as desired.

∎

Next, we define a function that will be useful for simplifying notation, both
in this section and subsequent ones.

######  Definition 32.

Let $\Delta$ be as in definition 29. For $x,y,z\in[0,\frac{\Delta}{3}]$, let

$F(x,y,z)=\sqrt[q]{\left(\frac{1}{\sqrt{d}}-x\right)^{q}+\left(\frac{1}{\sqrt{d}}-\frac{2\Delta}{3}+y\right)^{q}+\left(\frac{1}{\sqrt{d}}+\frac{2\Delta}{3}+z\right)^{q}}.$

We now define $g_{1},g_{2}$.

######  Corollary 33.

Let $\Delta$ be as in definition 29. There exist $1$-Lipshitz, monotonically
non-decreasing functions
$g_{1},g_{2}:[0,\frac{\Delta}{3}]\to[0,\frac{\Delta}{3}]$ such that for all
$t\in[0,\frac{\Delta}{3}]$, $g_{1}(t)+g_{2}(t)=t$ and
$F(t,g_{1}(t),g_{2}(t))=F(0,0,0)$.

###### Proof.

We have two cases.

##### Case 1: $1<q<\infty$:

Let $\Phi:[-\Delta,\Delta]\to\mathbb{R}$ be defined as
$\Phi(x)=(\frac{1}{\sqrt{d}}-x)^{q}$. Since $q>1$, and
$\Delta<\frac{1}{\sqrt{d}}$, $\Phi$ is strictly convex. Observe that

$F(x,y,z)^{q}=\Phi(x)+\Phi(2\frac{\Delta}{3}-y)+\Phi(-2\frac{\Delta}{3}-z).$

Next, fix any $t\in[0,\frac{\Delta}{3}]$. Then observe that
$-\frac{2\Delta}{3}\geq-\Delta$ and that $\frac{2\Delta}{3}-t\geq 0+t$. This
puts us in the configuration to apply Lemma 31. In particular, there exist
unique reals $\delta_{t},\gamma_{t}>0$ such that

$\delta_{t}+\gamma_{t}=t,$
$\Phi(-\frac{2\Delta}{3}-\delta_{t})+\Phi(t)+\Phi(\frac{2\Delta}{3}-\gamma_{t})=\Phi(-\frac{2\Delta}{3})+\Phi(0)+\Phi(\frac{2\Delta}{3}).$

We now define $g_{1},g_{2}:[0,\frac{\Delta}{3}]\to[0,\frac{\Delta}{3}]$ as

$g_{1}(t)=\gamma_{t}\text{ and }g_{2}(t)=\delta_{t}.$

Then it is clear that $F(0,0,0)=F(t,g_{1}(t),g_{2}(t))$ and
$g_{1}(t)+g_{2}(t)$ (by directly substituting into the equations above). All
that remains is to show that $g_{1}$ and $g_{2}$ are 1-Lipschitz.

Fix any $0\leq t_{1}<t_{2}\leq\frac{\Delta}{3}$, and let
$t_{2}-t_{1}=\epsilon$. The key idea is to apply Lemma 31 to
$-\frac{2\Delta}{3}-g_{2}(t_{1})<t_{1}<\frac{2\Delta}{3}-g_{1}(t_{1})$ and
$\epsilon$. To do so, we first check the conditions of the lemma.

We have that

$-\frac{2\Delta}{3}-g_{2}(t_{1})-\epsilon\geq-\frac{2\Delta}{3}-t_{1}-\epsilon=-\frac{2\Delta}{3}-t_{2}\geq-\Delta,$

and

$\begin{split}t_{1}+\epsilon&=t_{2}\\\ &\leq\frac{\Delta}{3}\\\
&\leq\frac{2\Delta}{3}-t_{2}\\\ &=\frac{2\Delta}{3}-t_{1}-\epsilon\\\
&\leq\frac{2\Delta}{3}-g_{1}(t_{1})-\epsilon.\end{split}$

Thus $\epsilon$ satisfies the necessary conditions for Lemma 31. Since $\Phi$
is strictly convex, by Lemma 31, there exist unique $\delta,\gamma>0$ with
$\delta+\gamma=\epsilon$ such that

$\Phi(-\frac{2\Delta}{3}-g_{2}(t_{1})-\delta)+\Phi(t_{1}+\epsilon)+\Phi(\frac{2\Delta}{3}-g_{1}(t_{1})-\gamma)=\Phi(-\frac{2\Delta}{3}-g_{2}(t_{1}))+\Phi(t_{1})+\Phi(\frac{2\Delta}{3}-g_{1}(t_{1})).$

However, by the definition of $g_{1},g_{2}$, we see that both of these
quantities are equal to $F(0,0,0)^{q}$. Moreover, again by the definition of
$g_{1},g_{2}$, we also have that $g_{1}(t_{2})$ and $g_{2}(t_{2})$ are the
unique real numbers in $[0,\frac{\Delta}{3}$ that satisfy

$\Phi(-\frac{2\Delta}{3}-g_{2}(t_{2}))+\Phi(t_{2})+\Phi(\frac{2\Delta}{3}+g_{1}(t_{2}))=F(0,0,0)^{q}.$

Thus, it follows that $g_{2}(t_{2})=g_{2}(t_{1})+\delta$ and
$g_{1}(t_{2})=g_{1}(t_{1})+\gamma$. However, $t_{2}-t_{1}=\epsilon$, and
$\delta,\gamma<\epsilon$ (since they sum to $\epsilon$). Thus, we see that
$|g_{1}(t_{2})-g_{1}(t_{1})|\leq|t_{2}-t_{1}|$ and
$|g_{2}(t_{2})-g_{2}(t_{1})|\leq|t_{2}-t_{1}|$. Since $t_{1}$ and $t_{2}$ were
arbitrary, it follows that $g_{1}$ and $g_{2}$ are both $1$-Lipschitz, as
desired.

Finally, since $\delta,\gamma>0$, it follows that $g_{2}(t_{2})>g_{2}(t_{1})$
and $g_{1}(t_{2})>g_{1}(t_{1})$. Since $t_{1},t_{2}$ were arbitrary, it
follows that $g_{1},g_{2}$ are monotonically non-decreasing.

##### Case 2: $q=1$

In this case, since $\Delta<\frac{1}{\sqrt{d}}$ (Lemma 28), we see that
$F(x,y,z)=\frac{3}{\sqrt{d}}+y+z-x$. Setting $g_{1}(t)=g_{2}(t)=\frac{t}{2}$
suffices, and clearly satisfies the desired properties. ∎

######  Definition 34.

Let $\Delta$ be as defined in Definition 29. We let
$g_{1},g_{2}:[0,\frac{\Delta}{3}]\to[0,\frac{\Delta}{3}]$ be defined as any
function satisfying the conditions of Corollary 33.

####  B.1.4 Putting it all together: defining $\Pi$

We are now ready to define $\Pi$. For convenience, we assume $d$ is a multiple
of $3$.

######  Definition 35.

Let $\Delta,g_{1}$, and $g_{2}$ be as defined in Definitions 29 and 34. Then
$\Pi$ is defined as the distribution of distributions ${\mathcal{D}}_{a}$
where $a$ is a random vector constructed as follows. Let $t_{1},t_{2},\dots
t_{d/3}$ be drawn i.i.d from the uniform distribution over
$[0,\frac{\Delta}{3}]$. Then for $1\leq i\leq d/3$, we let

  * •

$a_{i}=\frac{1}{2}+t_{i}$.

  * •

$a_{i+d/3}=\frac{1}{2}+2\frac{\Delta}{3}-g_{1}(t_{i})$.

  * •

$a_{i+2d/3}=\frac{1}{2}-2\frac{\Delta}{3}-g_{2}(t_{i}).$

Together the variables $a_{1},a_{2},\dots,a_{d}$ compose $a$. Thus a random
distribution ${\mathcal{D}}\sim\Pi$ can be constructed by sampling $a$ as
above and setting ${\mathcal{D}}={\mathcal{D}}_{a}$.

We now show that for all ${\mathcal{D}}_{a}\sim\Pi$, $\lambda_{a}$ (Definition
24) is constant.

######  Lemma 36.

There exists a constant $\Lambda$ such that for all
${\mathcal{D}}_{a}\sim\Pi$, $\lambda_{a}=\Lambda$.

###### Proof.

Let ${\mathcal{D}}_{a}\sim\Pi$ be arbitrary. By Lemma 33, for all $1\leq i\leq
d$, $g_{1}(t_{i})+g_{2}(t_{i})=t_{i}$. Substituting this, we see that

$\begin{split}\overline{a}&=\frac{1}{d}\sum_{1}^{d}a_{i}\\\
&=\frac{1}{d}\sum_{1}^{d/3}(\frac{1}{2}+t_{i})+(\frac{1}{2}+\frac{2\Delta}{3}-g_{1}(t_{i}))+(\frac{1}{2}-\frac{2\Delta}{3}-g_{2}(t_{i}))\\\
&=\frac{1}{d}\sum_{1}^{d/3}\frac{3}{2}\\\ &=\frac{1}{2}.\end{split}$

Recall that
$\lambda_{a}=\frac{r}{R}f_{q}(a)=\frac{r}{R}\sqrt[q]{\sum_{1}^{d}|\frac{1}{\sqrt{d}}+\overline{a}-a_{i}|^{q}}$.
By substituting that $\overline{a}=\frac{1}{2}$ and expressing each $a_{i}$ in
terms of $t_{i}$, we see that

$\begin{split}\lambda_{a}&=\frac{r}{R}\sqrt[q]{\sum_{1}^{d}|\frac{1}{\sqrt{d}}+\overline{a}-a_{i}|^{q}}\\\
&=\frac{r}{R}\sqrt[q]{\sum_{i=1}^{d/3}\left|\frac{1}{\sqrt{d}}+\frac{1}{2}-(\frac{1}{2}+t_{i})\right|^{q}+\left|\frac{1}{\sqrt{d}}+\frac{1}{2}-\left(\frac{1}{2}+\frac{2\Delta}{3}-g_{1}(t_{i})\right)\right|^{q}+\left|\frac{1}{\sqrt{d}}+\frac{1}{2}-\left(\frac{1}{2}-\frac{2\Delta}{3}-g_{2}(t_{i})\right)\right|^{q}}\\\
&=\frac{r}{R}\sqrt[q]{\sum_{1}^{d/3}\left|\frac{1}{\sqrt{d}}-t_{i}\right|^{q}+\left|\frac{1}{\sqrt{d}}+g_{1}(t_{i})-\frac{2\Delta}{3}\right|^{q}+\left|\frac{1}{\sqrt{d}}+g_{2}(t_{i})+\frac{2\Delta}{3}\right|^{q}}\\\
&=\frac{r}{R}\sqrt[q]{\sum_{1}^{d/3}F(t_{i},g_{1}(t_{i}),g_{2}(t_{i}))^{q}},\\\
\end{split}$

where $F$ is defined as in Definition 32. Next, by Corollary 33,
$F(t_{i},g_{1}(t_{i}),g_{2}(t_{i}))=F(0,0,0)$ for all $1\leq
i\leq\frac{d}{3}$. Thus, if we set
$\Lambda=\frac{r}{R}(\frac{d}{3})^{1/q}F(0,0,0)$, we have

$\begin{split}\lambda_{a}&=\frac{r}{R}\sqrt[q]{\sum_{1}^{d/3}F(t_{i},g_{1}(t_{i}),g_{2}(t_{i}))^{q}}\\\
&=\frac{r}{R}\sqrt[q]{\sum_{1}^{d/3}F(0,0,0)^{q}}\\\
&=\frac{r}{R}\sqrt[q]{\frac{d}{3}F(0,0,0)^{q}}\\\
&=\frac{r}{R}(\frac{d}{3})^{1/q}F(0,0,0)=\Lambda,\end{split}$

proving the claim. ∎

######  Definition 37.

We define $\Lambda=\frac{r}{R}(\frac{d}{3})^{1/q}F(0,0,0)$, where $F$ is
defined as in Definition 32.

Next, we compute upper and lower bounds on $\Lambda$, both of which will be
useful for subsequent lemmas.

######  Lemma 38.

$\frac{1}{9}<\Lambda<\frac{1}{3}$.

###### Proof.

By definition, $\Lambda=\frac{d}{3}^{1/q}F(0,0,0)$. Substituting the
definition of $f$, we see that
$F(0,0,0)=\sqrt[q]{|\frac{1}{\sqrt{d}}|^{q}+|\frac{1}{\sqrt{d}}-\frac{2\Delta}{3}|^{q}+|\frac{1}{\sqrt{d}}+\frac{2\Delta}{3}|^{q}},$
and consequently,

$3^{1/q}|\frac{1}{\sqrt{d}}-\frac{2\Delta}{3}|\leq F(0,0,0)\leq
3^{1/q}|\frac{1}{\sqrt{d}}+\frac{2\Delta}{3}|.$

By definition, $\frac{2\Delta}{3}<\frac{1}{2\sqrt{d}}$. It follows that

$\frac{r}{R}\frac{d^{1/q}}{2\sqrt{d}}<\Lambda<\frac{r}{R}\frac{3d^{1/q}}{2\sqrt{d}}.$

Finally, since $\frac{r}{R}=\frac{2\sqrt{d}}{9d^{1/q}}$, substituting this
yields $\frac{1}{9}<\Lambda<\frac{1}{3}$, as desired. ∎

Next, we show that for all ${\mathcal{D}}_{a}\in\Pi$, the aspect ratio
(Definition 9), $\rho({\mathcal{D}}_{a})$, is bounded by a constant.

######  Lemma 39.

For all ${\mathcal{D}}_{a}\in\Pi$, we have $\rho({\mathcal{D}}_{a})\leq
18\sqrt{3}$.

###### Proof.

We first bound the $\ell_{2}$ margin, $\gamma({\mathcal{D}}_{a})$ (Definition
8). Recall that the margin, $\gamma({\mathcal{D}}_{a})$ is described as the
largest possible $\ell_{2}$ distance from the support of ${\mathcal{D}}_{a}$
to the decision boundary of a linear classifier. Thus, we can lower bound
$\gamma({\mathcal{D}}_{a})$ by computing the distance from the support of
${\mathcal{D}}_{a}$ to $H_{a}$, the decision boundary of $f_{w^{a},1}$
(Definition 25).

By referring to Figure 4 (in Section B.1.1), it becomes clear that the closest
point (under the $\ell_{2}$ margin) from $S^{-}$ to $H_{a}$ is the point
$v_{i}+(a_{i}-\lambda_{a})u$, for some value of $i$. Thus it suffices to
compute the $\ell_{2}$ distance from this point to the plane $H_{a}$.

Recall that by Lemma 26, the point $v_{i}+a_{i}u$ satisfies $\langle
w^{a},v_{i}+a_{i}u\rangle=1$, and consequently must lie on the hyperplane
$H_{a}$. Let $D$ denote the $\ell_{2}$ distance from
$v_{i}+(a_{i}-\lambda_{a})u$ to $H_{a}$. Since $w^{a}$ is the normal vector to
$H_{a}$, it follows that

$\begin{split}D&=\langle
v_{i}+a_{i}u-(v_{i}+(a_{i}-\lambda_{a})u),\frac{w^{a}}{||w^{a}||_{2}}\rangle\\\
&=\frac{\langle\lambda_{a}u,w^{a}\rangle}{||w^{a}||_{2}}\\\
&\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mu1\mkern-1.5mu)}}{{=}}\frac{\langle\Lambda
u,w^{a}\rangle}{||w^{a}||_{2}}\\\
&\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mu2\mkern-1.5mu)}}{{=}}\frac{\Lambda\frac{d}{\sqrt{d}+d\overline{a}}}{||w^{a}||_{2}}\\\
&\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mu3\mkern-1.5mu)}}{{=}}\frac{\Lambda\frac{d}{\sqrt{d}+d\overline{a}}}{\sqrt{\sum_{1}^{d}\left(\frac{\sqrt{d}+d\overline{a}-da_{i}}{R(\sqrt{d}+d\overline{a}}\right)^{2}}}\\\
&=\frac{R\Lambda}{\sqrt{\sum_{1}^{d}(\frac{1}{\sqrt{d}}+\overline{a}-a_{i})^{2}}}\\\
&\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mu4\mkern-1.5mu)}}{{=}}\frac{R\Lambda}{f_{2}(a)}.\end{split}$

Here, (1) holds by Lemma 36, (2) holds by Lemma 26, (3) holds by Definition
25, and (4) holds by Definition 22.

Next, observe that since ${\mathcal{D}}_{a}\sim\Pi$, we must have
$a\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$. Thus it follows that
$||a-(\frac{1}{2},\frac{1}{2},\dots,\frac{1}{2})||_{2}\leq\Delta\sqrt{d}$.
However, by applying Lemma 28, we also see that $f_{2}$ is
$\frac{1}{d^{2}\sqrt{d}}$-Lipschitz over
$[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$. Thus, it follows that

$f_{2}(a)\leq
f_{2}(\frac{1}{2},\frac{1}{2},\dots,\frac{1}{2})+\Delta\sqrt{d}\frac{1}{d^{2}\sqrt{d}}\leq
2,$

with the latter inequality holding from the definition of $\Delta$.

Substituting this and applying Lemma 38, we see that

$\gamma({\mathcal{D}}_{a})\geq\frac{R\Lambda}{2}\geq\frac{R}{18}.$

Next, to bound the aspect ratio, $\rho({\mathcal{D}}_{a})$, we must also bound
the $\ell_{2}$ diameter of ${\mathcal{D}}_{a}$. However, the $\ell_{s}$
diameter of ${\mathcal{D}}_{a}$ is $R\sqrt{3}$, since it is the distance from
$v_{i}+u$ to $v_{j}$ for $i\neq j$. Thus, it follows that

$\rho({\mathcal{D}}_{a})=\frac{diam_{2}({\mathcal{D}}_{a})}{\gamma({\mathcal{D}}_{a})}\leq\frac{R\sqrt{3}}{R/18}=18\sqrt{3},$

as desired. ∎

Note that a tighter analysis (and selection of $\Delta$) can give a smaller
bound for $\rho({\mathcal{D}}_{a})$, but the most important fact is that
$\rho({\mathcal{D}}_{a})=O(1)$.

###  B.2 Bounding the expected robust loss

In this section, we finally prove our lower bound, Theorem 14. This will
require a few important steps, which we have separated into the following
subsections.

  * •

In section B.2.1, we give a useful lower bound for the loss
$\mathcal{L}_{r}(f,{\mathcal{D}}_{a})$ where $f$ is an arbitrary linear
classifier.

  * •

In section B.2.2, we give an explicit computation for the posterior
distribution $\Pi|S$ where $S\sim{\mathcal{D}}_{a}^{n}$ is the observed
training sample.

  * •

Finally, in section B.2.3, we present the proof of Theorem 14.

####  B.2.1 Bounding the loss $\mathcal{L}_{r}(f,{\mathcal{D}}_{a})$

In this section, we find a lower bound on the loss
$\mathcal{L}_{r}(f,{\mathcal{D}}_{a})$ where $f$ is a linear classifier. We
begin by first restricting $f$ to be in the set of classifiers

$f\in\\{f_{w^{b},1}:b\in[0,1]^{d}\\},$

where $w^{b}$ is as defined in Definition 25. These are precisely the
classifiers that have a decision boundary that passes through some point on
every line segment in $\\{[v_{i},v_{i}+u]:1\leq i\leq d\\}$. We are able to
only consider these classifiers since all other linear classifiers clearly
have a very high loss with respect to ${\mathcal{D}}_{a}$ as they necessarily
misclassify at least half the points on the line segment $[v_{i},v_{i}+u]$ for
some value of $i$.

We now find an initial lower bound on
$\mathcal{L}_{r}(f_{w^{b},1},{\mathcal{D}}_{a})$.

######  Lemma 40.

Fix any ${\mathcal{D}}_{a}\in\Pi$, and let $b\in[0,1]^{d}$ be arbitrary. Let
$w^{b}$ be the vector defined as in Definition 25, and
$\lambda_{b}=\frac{r}{R}f_{q}(b)$ where $f$ is as defined in Definition 22.
Then

$\mathcal{L}_{r}(f_{w^{b},1},{\mathcal{D}}_{a})\geq\frac{d(\lambda_{b}-\lambda_{a})+\sum_{1}^{d}|a_{i}-b_{i}|}{d-2d\Lambda}.$

###### Proof.

By Lemma 27, $f_{w^{b},1}$ precisely $r$-separates ${\mathcal{D}}_{b}$. This
implies that for all $1\leq i\leq d$,

$f_{w^{b},1}(x)=\begin{cases}1&x\in(v_{i}+(b_{i}+\lambda_{b})u,v_{i}+u]\\\
-1&x\in[v_{i},v_{i}+(b_{i}-\lambda_{b})u)\\\ \text{not
robust}&x\in[v_{i}+(b_{i}-\lambda_{b})u,v_{i}+(b_{i}+\lambda_{b})u]\end{cases}.$

Without loss of generality, suppose that $b_{i}\geq a_{i}$. The key
observation is that for all $1\leq i\leq d$, if
$x\in[v_{i}+(a_{i}+\lambda_{a})u,v_{i}+(b_{i}+\lambda_{b})u]$, then
$f_{w^{b},1}(x)=-1$ for $f_{w^{b},1}$ is not robust at $x$. In both cases, we
see that $f_{w^{b},1}$ is either inaccurate or not robust for all points in
$[v_{i}+(a_{i}+\lambda_{a})u,v_{i}+(b_{i}+\lambda_{b})u]$.

This interval has $\ell_{2}$ length at least
$(|a_{i}-b_{i}|+(\lambda_{b}-\lambda_{a}))||u||_{2}$. Note that in the case
that $a_{i}\leq b_{i}$ we can get an identical expression. Thus, combining
this for all $i$, we see that $f_{w^{b},1}$ is either inaccurate or not robust
for a total length of
$[d(\lambda_{b}-\lambda_{a})+\sum_{1}^{d}|a_{i}-b_{i}|]||u||_{2}$. Dividing by
the total length of the support of ${\mathcal{D}}_{a}$, we find that

$\begin{split}\mathcal{L}_{r}(f_{w^{b},1},{\mathcal{D}}_{a})&\geq\frac{[d(\lambda_{b}-\lambda_{a})+\sum_{1}^{d}|a_{i}-b_{i}|]||u||_{2}}{\sum_{1}^{d}||[v_{i},v_{i}+(a_{i}-\lambda_{a})u)+(v_{i}+(a_{i}+\lambda_{a})u,v_{i}+u]||_{2}}\\\
&=\frac{[d(\lambda_{b}-\lambda_{a})+\sum_{1}^{d}|a_{i}-b_{i}|]||u||_{2}}{\sum_{1}^{d}||u_{2}||(1-2\lambda_{a})}\\\
&=\frac{d(\lambda_{b}-\lambda_{a})+\sum_{1}^{d}|a_{i}-b_{i}|}{d(1-2\lambda_{a})}\\\
&=\frac{d(\lambda_{b}-\lambda_{a})+\sum_{1}^{d}|a_{i}-b_{i}|}{d-2d\Lambda},\end{split}$

with the last equality holding since by Lemma 36, $\lambda_{a}=\Lambda$. ∎

######  Lemma 41.

For all ${\mathcal{D}}_{a}\in\Pi$ and $b\in[0,1]^{d}$,
$d(\lambda_{a}-\lambda_{b})\leq\frac{1}{2}\sum_{1}^{d}|a_{i}-b_{i}|.$

###### Proof.

We have two cases.

##### Case 1:

$b\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$.

Observe that $\lambda_{b}=\frac{r}{R}f_{q}(b)$ and
$\lambda_{a}=\frac{r}{R}f_{q}(a)$. By Lemma 28, we see that $f_{q}$ is
$\frac{1}{d^{2}\sqrt{d}}$-Lipschitz over the domain
$[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$. It follows that

$\begin{split}\lambda_{a}-\lambda_{b}&=\frac{r}{R}(f_{q}(a)-f_{q}(b))\\\
&\leq\frac{r}{R}||a-b||_{2}\frac{1}{d^{2}\sqrt{d}}\\\
&=\frac{2\sqrt{d}}{9d^{1/q}}||a-b||_{2}\frac{1}{d^{2}\sqrt{d}}\\\
&<\frac{||a-b||_{1}}{2d},\end{split}$

with the last inequality following since the $\ell_{2}$ norm is smaller than
the $\ell_{1}$ norm. Rearranging this gives the statement of the Lemma as
desired.

##### Case 2:

$b\notin[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$.

The main idea in this case will be to find
$b^{\prime}\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$ such that
$\lambda_{b}\geq\lambda_{b^{\prime}}$ and such that
$||b^{\prime}-a||_{1}\leq||b-a||_{1}$. We will then apply Case 1 to get the
desired result.

Without loss of generality, assume that $b_{1}\geq b_{2}\geq\dots\geq b_{d}$,
and that $b_{1},b_{2},\dots b_{k}>\frac{1}{2}+\Delta$,
$b_{k+1},\dots,b_{l}\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]$, and
$b_{l+1},\dots b_{d}<\frac{1}{2}-\Delta$ for some values of $k$ and $l$.

We will construct $b^{\prime}$ in four steps. In each of these steps, we will
change the values of $b_{i}$ such that neither $||a-b||_{1}$ nor $\lambda_{b}$
are increased. At each step, we let $b_{i}$ refer to its value at the end of
the previous step.

Finally, for reference, recall that

$\lambda_{b}=\frac{r}{R}f_{q}(b)=\frac{r}{R}\sqrt[q]{\sum_{1}^{d}|\frac{1}{\sqrt{d}}+\overline{b}-b_{i}|^{q}}.$

##### Step 1:

We set

$b_{i}\leftarrow\begin{cases}\frac{1}{k}\sum_{j=1}^{k}b_{j}&1\leq i\leq k\\\
b_{i}&k+1\leq i\leq l\\\ \frac{1}{d-l}\sum_{j=l+1}^{d}b_{j}&l+1\leq i\leq
d\end{cases}.$

Since $a\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$, we see that these
operations do not change $||a-b||_{1}$, as
$\sum_{1}^{k}|b_{i}-a_{i}|=\sum_{1}^{k}b_{i}-a_{i}$ and
$\sum_{l+1}^{d}|b_{i}-a_{i}|=\sum_{1}^{k}a_{i}-b_{i}$. Also, observe that this
operation preserves $\overline{b}$, and consequently since the function
$f(x)=|\frac{1}{\sqrt{d}}+\overline{b}-x|^{q}$ is convex, we see that by
Jensen’s inequality that $\lambda_{b}$ is not increased by this operation.

##### Step 2:

Let
$\beta=\sum_{1}^{k}(b_{i}-\frac{1}{2}-\Delta)-\sum_{l+1}^{d}(\frac{1}{2}-\Delta-
b_{i})$. Then we set

$b_{i}\leftarrow\begin{cases}\begin{cases}\frac{1}{2}+\Delta+\frac{\beta}{k}&1\leq
i\leq k\\\ b_{i}&k+1\leq i\leq l\\\ \frac{1}{2}-\Delta&l+1\leq i\leq
d\end{cases}&\beta\geq 0\\\ \begin{cases}\frac{1}{2}+\Delta&1\leq i\leq k\\\
b_{i}&k+1\leq i\leq l\\\ \frac{1}{2}-\Delta+\frac{\beta}{d-l}&l+1\leq i\leq
d\end{cases}&\beta<0\end{cases}.$

Observe that this operation cannot increase $||a-b||_{1}$, since it doesn’t
increase $|a_{i}-b_{i}|$ for any value of $i$. Furthermore, this operation
also does not change $\overline{b}$, and a similar convexity argument on the
function $f(x)=|\frac{1}{\sqrt{d}}+\overline{b}-x|^{q}$ can show that this
does not increase $\lambda_{b}$.

Finally, if $\beta=0$, we set $b^{\prime}=b$, since we have reached a state
such that $b\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$.

##### Step 3a:

We run this step if $\beta>0$. Let
$\alpha=\frac{\sum_{k+1}^{d}(\frac{1}{2}+\Delta-b_{i})}{\beta}$. We then set

$b_{i}\leftarrow\begin{cases}\begin{cases}\frac{1}{2}+\Delta&1\leq i\leq k\\\
(\frac{1}{2}+\Delta)(\frac{\alpha-1}{\alpha})+\frac{b_{i}}{\alpha}&k+1\leq
i\leq d\end{cases}&\alpha\geq 1\\\
\begin{cases}\frac{1}{2}+\Delta+\frac{\beta}{k}(1-\alpha)&1\leq i\leq k\\\
\frac{1}{2}+\Delta&k+1\leq i\leq d\end{cases}&\alpha<1\end{cases}.$

In this step, we can similarly verify that $||a-b||_{1}$ does not increase (as
$|a_{i}-b_{i}|$ is strictly reduced for $1\leq i\leq k$ by an exact amount to
offset the possible increases in $|a_{i}-b_{i}|$ for $k+1\leq i\leq d$). We
also see by the same convexity argument as usual that this operation reduces
$\lambda_{b}$.

##### Step 3b:

We run this step if $\beta<0$. Let
$\alpha=\frac{\sum_{k+1}^{d}(b_{i}-\frac{1}{2}+\Delta)}{\beta}$. We then set

$b_{i}\leftarrow\begin{cases}\begin{cases}(\frac{1}{2}-\Delta)(\frac{\alpha-1}{\alpha})+\frac{b_{i}}{\alpha}&1\leq
i\leq l\\\ \frac{1}{2}-\Delta&k+1\leq i\leq d\end{cases}&\alpha\geq 1\\\
\begin{cases}\frac{1}{2}-\Delta&1\leq i\leq l\\\
\frac{1}{2}-\Delta+\frac{\beta}{d-l}(1-\alpha)&l+1\leq i\leq
d\end{cases}&\alpha<1\end{cases}.$

The justification for this step is analogous to 3a.

##### Step 4:

We only run this step if $\alpha<1$. Observe that if $\alpha\geq 1$, then both
Step 3a and Step 3b result with
$b\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$, which we set as
$b^{\prime}$. Observe that in this case, either $b_{i}\geq a_{i}$ for all $i$,
or $b_{i}\leq a_{i}$ for all $i$. Thus we simply set

$b_{i}\leftarrow\overline{b}.$

This operation does not change $||a-b||_{1}$, and it also reduces
$\lambda_{b}$ (by a convexity argument).

##### Step 5:

Finally, for all $1\leq i\leq d\Delta$, we set $b_{i}=\frac{1}{2}-\Delta$ if
$\overline{b}<\frac{1}{2}-\Delta$ and otherwise set $b_{i}=\frac{1}{2}-\Delta$
if $\overline{b}>\frac{1}{2}+\Delta$. In both cases, $\lambda_{b}$ is not
changed, and $||a-b||_{1}$ is strictly reduced. In this step, we finally set
$b^{\prime}=b$. Note that we do not always reach this step, as it was possible
in any of the previous steps to reach some
$b\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$, at which point we would
have simply terminated.

##### Conclusion:

Through steps $1$ through $5$, we have found
$b^{\prime}\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$ such that
$\lambda_{b^{\prime}}\leq\lambda_{b}$ and
$||a-b^{\prime}||_{1}\leq||a-b||_{1}$. By applying Case 1 to $b^{\prime}$, we
see that
$d(\lambda_{a}-\lambda_{b^{\prime}})\leq\frac{1}{2}||a-b^{\prime}||_{1}$.
Thus, we have that

$\frac{1}{2}||a-b||_{1}\geq\frac{1}{2}||a-b^{\prime}||_{1}\geq
d(\lambda_{a}-\lambda_{b^{\prime}})\geq d(\lambda_{a}-\lambda_{b}),$

which implies the result by the transitive property.

∎

From the previous two lemmas, we immediately have the following:

######  Corollary 42.

For all ${\mathcal{D}}_{a}\in\Pi$ and $b\in[0,1]^{d}$,

$\mathcal{L}_{r}(f_{w^{b},1},{\mathcal{D}}_{a})\geq\frac{1}{2d}\sum_{1}^{d}|a_{i}-b_{i}|.$

###### Proof.

We have that

$\begin{split}\mathcal{L}_{r}(f_{w^{b},1},{\mathcal{D}}_{a})&\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mua\mkern-1.5mu)}}{{\geq}}\frac{d(\lambda_{b}-\lambda_{a})+\sum_{1}^{d}|a_{i}-b_{i}|}{d-2d\Lambda}\\\
&\geq\frac{\sum_{1}^{d}|a_{i}-b_{i}|-d(\lambda_{a}-\lambda_{b})+}{d}\\\
&\stackrel{{\scriptstyle\scriptscriptstyle(\mkern-1.5mub\mkern-1.5mu)}}{{\geq}}\frac{\sum_{1}^{d}|a_{i}-b_{i}|-\frac{1}{2}\sum_{1}^{d}|a_{i}-b_{i}|}{d}\\\
&=\frac{1}{2d}\sum_{1}^{d}|a_{i}-b_{i}|,\end{split}$

where (a) holds by Lemma 40 and (b) holds by Lemma 41. ∎

####  B.2.2 Computing the posterior distribution, $\Pi|S$

Recall that our ultimate goal is to show that

${\mathbb{E}}_{{\mathcal{D}}\sim\Pi}[{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]]\geq\Omega(\frac{d}{n}),$

where $A$ denotes any learning algorithm returning a linear classifier. The
main idea for showing this is to “switch expectations” and realize that

${\mathbb{E}}_{{\mathcal{D}}\sim\Pi}[{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]]={\mathbb{E}}_{S\sim\Sigma}[{\mathbb{E}}_{{\mathcal{D}}\sim\Pi|S}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]],$

where $\Pi|S$ denotes the posterior distribution over $\Pi$ after observing
$S$. In this section, we fully characterize the distribution $\Pi|S$, and
prove several important properties about it.

Recall (Definition 35) that ${\mathcal{D}}_{a}\sim\Pi$ is generated by first
choosing $t_{1},t_{2},\dots,t_{d/3}\sim\mathbb{U}[0,\frac{\Delta}{3}]$ i.i.d,
and then letting $a=(a_{1},a_{2},\dots,a_{d})$ be a function of
$t=(t_{1},\dots,t_{d/3})$. Thus, to compute the posterior $\Pi|S$, it suffices
to focus on the posterior distribution of $t|S$ for any $1\leq
i\leq\frac{d}{3}$. We begin by first defining the likelihood of observing $S$
given that it is generated from parameter $t$.

######  Definition 43.

Let $S=\\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{n},y_{n})\\}$ be any set of
$n$ points in $\mathbb{R}^{d}\times\\{\pm 1\\}$, and let
$t\in[0,\frac{\Delta}{3}]^{d/3}$ be a vector. Let
$a\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$ be defined as in Definition
35. That is, let

  * •

$a_{i}=\frac{1}{2}+t_{i}$.

  * •

$a_{i+d/3}=\frac{1}{2}+\frac{2\Delta}{3}-g_{1}(t_{i})$.

  * •

$a_{i+2d/3}=\frac{1}{2}-\frac{2\Delta}{3}-g_{2}(t_{i})$.

Then we define $L(S|t)$ as the likelihood of observing the set $S$ from
${\mathcal{D}}_{a}^{n}$. In particular, for any measurable region of points
$R\subseteq(\mathbb{R}^{d}\times\\{\pm 1\\})^{n}$, we have that

$\mathbb{P}_{S\sim{\mathcal{D}}_{a}^{n}}[S\in R]=\int_{x\in R}L(x|t)dx.$

######  Lemma 44.

Let $S\subset\mathbb{R}^{d}\times\\{\pm 1\\}$ be a set with $n$ points. Then
for all $t\in[0,\frac{\Delta}{3}]^{d/3}$,

$L(S|t)\in\left\\{0,\left(\frac{1}{(d-2\Lambda)||u||_{2}}\right)^{n}\right\\},$

where $\Lambda$ is as defined in Definition 37 and $L(S|t)$ is as defined in
Definition 43.

###### Proof.

Let ${\mathcal{D}}_{a}$ be an arbitrary distribution in $\Pi$. Observe that
${\mathcal{D}}_{a}$ is uniform over the set of all points in its support. Thus
for every point in its support, we have that the likelihood $L(x|t)$ satisfies
$L(x|t)=\frac{1}{(d-2\Lambda)||u||_{2}}$.

Taking the product of this over all points in $S$, we get the desired result.
Note that if $S$ contains some point not in the support of
${\mathcal{D}}_{a}$, then the likelihood becomes $0$, since the likelihood of
observing some point not in the support of ${\mathcal{D}}_{a}$ is $0$. ∎

######  Definition 45.

For any dataset $S$, let $P_{S}$ denote the set of all “permissible” $t$, that
is $t\in[0,\frac{\Delta}{3}]^{d}$ such that $L(S|t)\neq 0$. Formally,

$P_{S}=\\{t:L(S|t)>0\\}.$

We now fully characterize $P_{S}$ when $S$ is drawn from some
${\mathcal{D}}\sim\Pi$.

######  Lemma 46.

Fix $n>0$. For all ${\mathcal{D}}\sim\Pi$ and $S\sim{\mathcal{D}}^{n}$, there
exist intervals (possibly open, closed, half open)
$I_{1}^{S},I_{2}^{S},\dots,I_{d/3}^{S}\subseteq[0,\frac{\Delta}{3}]$ such that
$P_{S}=\prod_{1}^{d/3}I_{i}^{S}$.

###### Proof.

Let $S=\\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{n},y_{n})\\}$. Since
$S\sim{\mathcal{D}}^{n}$, we see that for $1\leq j\leq n$, $x_{j}$ must
satisfy $x_{j}\in[v_{i},v_{i}+u]$ for some $1\leq j\leq d$. Using this, for
$1\leq i\leq d$ let

$s_{i}^{-}=\operatorname*{arg\,max}_{\\{x_{j}:x_{j}\in[v_{i},v_{i}+u],y_{j}=-1\\}}||x_{j}-v_{i}||_{2},$

and

$s_{i}^{+}=\operatorname*{arg\,max}_{\\{x_{j}:x_{j}\in[v_{i},v_{i}+u],y_{j}=+1\\}}||x_{j}-(v_{i}+u)||_{2}.$

$s_{i}^{-}$ and $s_{i}^{+}$ can be thought of as the points from $S$ on
segment $[v_{i},v_{i}+u]$ that are closest to each other and labeled as $-$
and $+$ respectively. As a default, if no such points exist, we set
$s_{i}^{-}=v_{i}$ and $s_{i}^{+}=v_{i}+u$.

Next, consider any $t\in[0,\frac{\Delta}{3}]^{d/3}$, let
$a\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$ be defined as in Definition
35. That is, let

  * •

$a_{i}=\frac{1}{2}+t_{i}$.

  * •

$a_{i+d/3}=\frac{1}{2}+\frac{2\Delta}{3}-g_{1}(t_{i})$.

  * •

$a_{i+2d/3}=\frac{1}{2}-\frac{2\Delta}{3}-g_{2}(t_{i})$.

The key idea of this lemma is that $t\in P_{S}$ (i.e. $L(S|t)>0$) if and only
if for all $1\leq i\leq d$,

$[v_{i}+(a_{i}-\Lambda)u,v_{i}+(a_{i}+\Lambda)u]\subseteq(s_{i}^{-},s_{i}^{+}).$

To see this, observe that if the claim above holds, then we must have that
$s_{i}^{-}\in[v_{i},v_{i}+(a_{i}-\Lambda)u)$ and
$s_{i}^{+}\in(v_{i}+(a_{i}+\Lambda)u,v_{i}+u]$, and it consequently follows
that all points in $S$ are elements of the support of ${\mathcal{D}}_{a}$
(Definition 24), as all other points in $S$ are “further” from the interval
$[v_{i}+(a_{i}-\Lambda)u,v_{i}+(a_{i}+\Lambda)u]$ than the points $s_{i}^{+}$
and $s_{i}^{-}$. Conversely, if $L(S|t)>0$, we must have that $S\subseteq
supp({\mathcal{D}}_{a})$, which immediately translates to the statement above.
Thus, it suffices to find all $t$ such that this condition holds.

To do this, observe that the interval
$[v_{i}+(a_{i}-\Lambda)u,v_{i}+(a_{i}+\Lambda)u]$ is a line segment of length
$2\Lambda||u||_{2}$ that is centered at the point $v_{i}+a_{i}u$. Thus, in
order for this to be a sub-segment of $(s_{i}^{-},s_{i}^{+})$, we only need
that $a_{i}$ satisfy $v_{i}+a_{i}u\in(s_{i}^{-}+\Lambda u,s_{i}^{-}-\Lambda
u)$. This condition is equivalent to the condition that $a_{i}\in J_{i}^{S}$
for some open interval $J_{i}^{S}\subseteq[0,1]$, where $J_{i}^{S}$ is only
dependent on $s_{i}^{-},s_{i}^{+}$ and $\Lambda$ (which is a constant). In
summary, there exist interval $J_{1}^{S},J_{2}^{S},\dots,J_{d}^{S}$ such that
$t\in P_{S}$ if and only if $a_{i}\in J_{i}^{S}$ for $1\leq i\leq d$.

Finally, note that for $1\leq i\leq d/3$, $a_{i},a_{i+d/3},a_{i+2d/3}$ are all
functions of $t_{i}$, and moreover these functions are $1$-lipschitz, and
monotonic. As a consequence, by taking the intersections of the pre-images of
these functions, we find that this condition holds if and only if $t_{i}\in
I_{i}^{S}$ where $I_{i}^{S}$ is some interval that is a subset of
$[0,\frac{\Delta}{3}]^{d/3}$. This proves the claim. ∎

######  Corollary 47.

For any $S\sim{\mathcal{D}}$ where ${\mathcal{D}}\sim\Pi$, let $I_{i}^{S}$ be
defined as in Lemma 46 for $1\leq i\leq d/3$. Then the posterior distribution
$t|S$ is equal to the uniform distribution over the set $\prod_{1\leq i\leq
d/3}I_{i}^{S}$, where $t_{i}$ is sampled from $I_{i}^{S}$.

###### Proof.

First, recall that our prior on $t$ is $\mathbb{U}([0,\frac{\Delta}{3}]^{d})$,
where $\mathbb{U}$ denotes the uniform distribution. By Lemma 44, we see that
for all $t\in P_{S}$,
$L(S|t)=\left(\frac{1}{(d-2\Lambda)||u||_{2}}\right)^{n}$, and for all other
$t$, $L(S|t)=0$. Furthermore, by Lemma 46, we see that $P_{S}=\prod_{1}^{1\leq
i\leq d/3}I_{i}^{S}$. Thus, applying Bayes rules gives the desired result. ∎

We conclude this section by lower bounding the expected length of the interval
$I_{i}^{S}$, denoted $\ell(I_{i}^{S})$.

######  Lemma 48.

For an interval $(c,d)\subset\mathbb{R}$, we let its length, denoted
$\ell((c,d))$ be defined as $\ell((c,d))=d-c$. Then for $1\leq k\leq d/3$, the
expected length (taken over ${\mathcal{D}}_{a}\sim\Pi$ and
$S\sim{\mathcal{D}}_{a}^{n}$) of the interval $I_{k}^{S}$ is at least
$\Omega(\frac{d}{n})$. That is,

${\mathbb{E}}_{{\mathcal{D}}_{a}\sim\Pi}{\mathbb{E}}_{S\sim{\mathcal{D}}_{a}^{n}}[\ell(I_{k}^{S})]]\geq\Omega(\frac{d}{n}).$

###### Proof.

Fix any ${\mathcal{D}}_{a^{*}}\sim\Pi$, and let $t^{*}$ denote the value of
$t$ used to generate $a$ (as in Definition 35). We will show that
${\mathbb{E}}_{S\sim{\mathcal{D}}_{a^{*}}^{n}}[\ell(I_{k}^{S})]]\geq\Omega(\frac{d}{n}),$
for all $1\leq k\leq d/3$. We begin by explicitly computing the interval
$I_{k}^{S}$.

Fix $1\leq k\leq d/3$. Then $t_{k}*\in[0,\frac{\Delta}{3}]$. Assume that
$t_{k}^{*}>0$; we will handle the case $t_{k}^{*}=0$ separately. Recall from
the proof of Lemma 46 that for $1\leq i\leq d$, we defined

$s_{i}^{-}=\operatorname*{arg\,max}_{\\{x_{j}:x_{j}\in[v_{i},v_{i}+u],y_{j}=-1\\}}||x_{j}-v_{i}||_{2},$

and

$s_{i}^{+}=\operatorname*{arg\,max}_{\\{x_{j}:x_{j}\in[v_{i},v_{i}+u],y_{j}=+1\\}}||x_{j}-(v_{i}+u)||_{2}.$

for $1\leq i\leq d$.

Next let $t\in[0,\frac{\Delta}{3}]^{d/3}$ be a vector, and let
$a\in[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]^{d}$ be defined as
$a_{k}=\frac{1}{2}+t_{k}$,
$a_{k+d/3}=\frac{1}{2}+\frac{2\Delta}{3}-g_{1}(t_{k})$ and
$a_{k+2d/3}=\frac{1}{2}-\frac{2\Delta}{3}-g_{2}(t_{k})$, for $1\leq k\leq
d/3$. Note that $g_{1},g_{2}$ are the functions defined in Definition 34.

As we argued in the proof of Lemma 46, it then follows that $t_{k}\in
I_{k}^{S}$ if and only if

$[v_{i}+(a_{i}-\Lambda)u,v_{i}+(a_{i}+\Lambda)u]\subseteq(s_{i}^{-},s_{i}^{+}),$

for $i=k,k+d/3,k+2d/3$. Finally, as we did in Lemma 46, for each $1\leq i\leq
d$, we define intervals
$J_{i}^{S}\subseteq[\frac{1}{2}-\Delta,\frac{1}{2}+\Delta]$ such that
$a_{i}\in J_{i}^{S}$ if and only if
$[v_{i}+(a_{i}-\Lambda)u,v_{i}+(a_{i}+\Lambda)u]\subseteq(s_{i}^{-},s_{i}^{+})$.

We now have the following three claims.

##### Claim 1:

Let
$\alpha=\min\left(\frac{||s_{k}^{-}-(v_{k}+(a_{k}^{*}-\Lambda)u)||_{2}}{||u||_{2}},t_{k}^{*}\right)$.
If $t_{k}\in(t_{k}^{*}-\alpha,t_{k}^{*}]$, then

$[v_{k}+(a_{k}-\Lambda)u,v_{k}+(a_{k}+\Lambda)u]\subseteq(s_{k}^{-},s_{k}^{+}).$

Proof:  First, observe that since $s_{k}^{+}$ and $s_{k}^{-}$ were sampled
from ${\mathcal{D}}_{a^{*}}$, it follows that

$[v_{k}+(a_{k}^{*}-\Lambda)u,v_{k}+(a_{k}^{*}+\Lambda)u]\subseteq(s_{i}^{-},s_{i}^{+}).$

Consider any $t_{k}\in[t_{k}^{*}-\alpha,t_{k}^{*}]$. Then substituting the
definitions of $a_{k},a_{k}^{*}$ imply that
$a_{k}\in[a_{k}^{*}-\alpha,a_{k}^{*}]$. Because of this, it follows that

$\begin{split}||(v_{k}+(a_{k}-\Lambda)u)-(v_{k}+(a_{k}^{*}-\Lambda)u)||_{2}&=||(a_{k}-a_{k}^{*})u||_{2}\\\
&<\alpha||u||_{2}\\\
&\leq||s_{k}^{-}-(v_{k}+(a_{k}^{*}-\Lambda)u)||_{2},\end{split}$

which implies that
$v_{k}+(a_{k}-\Lambda)u\in(s_{i}^{-},v_{k}+(a_{k}^{*}-\Lambda)u]$.
Furthermore, the fact that $a_{k}\leq a_{k}^{*}$ implies that
$v_{k}+(a_{k}+\Lambda)u\in(v_{k}+(a_{k}-\Lambda)u,v_{k}+(a_{k}^{*}+\Lambda)u]$.

Together, these observations imply the desired result, as it follows that

$[v_{k}+(a_{k}-\Lambda)u,v_{k}+(a_{k}+\Lambda)u]\subset(s_{k}^{-},v_{k}+(a_{k}^{*}+\Lambda)u]\subset(s_{k}^{-},s_{k}^{+}).$

$\blacksquare$

##### Claim 2:

Let
$\beta=\min\left(\frac{||s_{k+d/3}^{+}-(v_{k+d/3}+(a_{k+d/3}^{*}+\Lambda)u)||_{2}}{||u||_{2}},g_{1}(t_{k}^{*})\right)$.
If $t_{k}\in(g_{1}^{-1}(g_{1}(t_{k}^{*})-\beta),t_{k}^{*}]$, then

$[v_{k+d/3}+(a_{k+d/3}-\Lambda)u,v_{k}+(a_{k+d/3}+\Lambda)u]\subseteq(s_{k+d/3}^{-},s_{k+d/3}^{+}).$

Proof:  First, we observe that $\beta$ is well defined since $g_{1}$ is a
monotonic $1$-Lipschitz function, and consequently has an inverse. Next, we
also see that $0\leq g_{1}(t_{k}^{*})-g_{1}(t_{k})\leq\beta$. Substituting the
definitions of $a_{k}^{*},a_{k}$, it follows that $0\leq
a_{k}-a_{k}^{*}\leq\beta$ (notice the order switch). At this point, we can
apply the same argument as in Claim 1 to get the desired result.
$\blacksquare$.

##### Claim 3:

Let
$\tau=\min\left(\frac{||s_{k+2d/3}^{+}-(v_{k+2d/3}+(a_{k+2d/3}^{*}+\Lambda)u)||_{2}}{||u||_{2}},g_{2}(t_{k}^{*})\right)$.
If $t_{k}\in(g_{2}^{-1}(g_{2}(t_{k}^{*})-\tau),t_{k}^{*}]$, then

$[v_{k+2d/3}+(a_{k+2d/3}-\Lambda)u,v_{k+2d/3}+(a_{k+2d/3}+\Lambda)u]\subseteq(s_{k+2d/3}^{-},s_{k+2d/3}^{+}).$

Proof:  Completely analogous to Claim 2. $\blacksquare$.

Combining these claims, we see that if
$t_{k}\in(t_{k}^{*}-\alpha,t_{k}^{*}]\cap(g_{1}^{-1}(g_{1}(t_{k}^{*})-\beta),t_{k}^{*}]\cap(g_{2}^{-1}(g_{2}(t_{k}^{*})-\tau),t_{k}^{*}]$,
then $t_{k}\in I_{k}^{S}$. Since these three intervals all have an endpoint in
$t_{k}^{*}$, it follows that there is an interval with length $\eta$ that is a
subset of $I_{k}^{S}$, where

$\eta=\min(\ell((t_{k}^{*}-\alpha,t_{k}^{*}])),\ell((g_{1}^{-1}(g_{1}(t_{k}^{*})-\beta),t_{k}^{*}]),\ell((g_{2}^{-1}(g_{2}(t_{k}^{*})-\tau),t_{k}^{*}])).$

However, by substituting that $g_{1},g_{2}$ are $1$-Lipschitz, we see that
$\ell((g_{1}^{-1}(g_{1}(t_{k}^{*})-\beta),t_{k}^{*}])\geq\beta$ and
$\ell((g_{2}^{-1}(g_{2}(t_{k}^{*})-\tau),t_{k}^{*}]))\geq\tau$. Thus, it
follows that

$\ell(I_{k}^{S})\geq\eta\geq\min(\alpha,\beta,\tau).$

Thus it suffices to show that
${\mathbb{E}}_{S\sim{\mathcal{D}}_{a^{*}}}[\min(\alpha,\beta,\tau)]\geq\Omega(\frac{d}{n})$.

To do this, observe that

  * •

$\alpha||u||_{2}$ is the distance from the closest point labeled $-$ on the
segment $[v_{k},v_{k}+u]$ to the point $v_{k}+(a_{k}^{*}-\Lambda)u$

  * •

$\beta||u||_{2}$ is the distance from the closest point labeled $+$ on the
segment $[v_{k+d/3},v_{k+d/3}+u]$ to the point
$v_{k+d/3}+(\Lambda+a_{k+d/3}^{*})u$

  * •

$\tau||u||_{2}$is the distance from the closest point labeled $+$ on the
segment $[v_{k+2d/3},v_{k+2d/3}+u]$ to the point
$v_{k+2d/3}+(\Lambda+a_{k+2d/3}^{*})u$.

Finally, it is not difficult to see that for sufficiently large $n$, with high
probability each of these distances will be $\Omega(\frac{d}{n})$. This is
because with high probability there will be $\Theta(\frac{n}{d})$ points on
each of the respective line segments, and we are considering the closest point
among them to some reference point. Thus, it follows that with high
probability
${\mathbb{E}}_{S\sim{\mathcal{D}}_{a^{*}}}[\min(\alpha,\beta,tau)]\geq\Omega(\frac{d}{n}),$
as desired. ∎

####  B.2.3 Putting it all together, the proof

We prove the following key lemma, which directly implies Theorem 14.

######  Lemma 49.

Let $M$ be any learning algorithm that outputs a linear classifier. For any
training sample of points
$S=\\{(x_{1},y_{1}),(x_{2},y_{2}),\dots,(x_{n},y_{n})\\}$, we let $M_{S}$
denote the classifier learned by $M$ from $S\sim{\mathcal{D}}$. Then it
follows that

${\mathbb{E}}_{{\mathcal{D}}\sim\Pi}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(M_{S},{\mathcal{D}})]]\geq\Omega(\frac{d}{n}).$

###### Proof.

Let ${\mathcal{F}}_{n}$ denote the distribution over
$(\mathbb{R}^{d}\times\\{\pm 1\\})^{n}$ defined as the composition
${\mathcal{D}}\sim\Pi$ and $S\sim{\mathcal{D}}^{n}$. That is,
$S\sim{\mathcal{F}}_{n}$ follows the same distribution as
${\mathcal{D}}\sim\Pi,S\sim{\mathcal{D}}^{n}$. Then we can write the
expectation above as

$\begin{split}{\mathbb{E}}_{{\mathcal{D}}\sim\Pi}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]]={\mathbb{E}}_{S\sim{\mathcal{F}}_{n}}{\mathbb{E}}_{{\mathcal{D}}\sim(\Pi|S)}[\mathcal{L}_{r}(M_{S},{\mathcal{D}})]],\end{split}$

where $\Pi|S$ denotes the posterior distribution of ${\mathcal{D}}$
conditioned on observing $S$. First, fix any such $S$. We will bound
${\mathbb{E}}_{{\mathcal{D}}\sim(\Pi|S)}[\mathcal{L}_{r}(M_{S},{\mathcal{D}})].$
First, by reparametrizing in terms of $t\in[0,\frac{\Delta}{3}]^{d/3}$ and
applying Corollary 47, we have that

${\mathbb{E}}_{D\sim(\Pi|S)}[\mathcal{L}_{r}(M_{S},{\mathcal{D}})]={\mathbb{E}}_{t_{1}\sim\mathbb{U}(I_{1}^{S})}[\dots[{\mathbb{E}}_{t_{n}\sim\mathbb{U}(I_{d/3})}[\mathcal{L}_{r}(M_{S},{\mathcal{D}}_{a})]\dots],$

where $I_{1}^{S},I_{2}^{S},\dots,I_{d/3}^{S}\subset[0,\frac{\Delta}{3}]$ are
the intervals defined in Lemma 46, and $a$ is defined as in Definition 35.

Next, let $b\in[0,1]^{d}$ be such that $M_{S}=f_{w^{b},1}$, where $w^{b}$ is
defined as in Definition 25. Then it follows from Corollary 42 that

$\begin{split}\mathcal{L}_{r}(M_{S},{\mathcal{D}}_{a})]&\geq\frac{1}{20d}\sum_{1}^{d}|a_{i}-b_{i}|\\\
&\geq\frac{1}{20d}\sum_{1}^{d/3}|\frac{1}{2}+t_{i}-b_{i}|\end{split}$

with the last inequality coming from substituting the definition of $a_{i}$
and (and ignoring $a_{i}$ for $i>d/3$). We now take the expectation of this
inequality over $t_{1},t_{2},\dots,t_{d/3}$. To do so, observe that by simple
algebra,
${\mathbb{E}}_{t_{i}\sim\mathbb{U}(I_{i}^{S})}|\frac{1}{2}+t_{i}-b_{i}|\geq\frac{\ell(I_{i}^{S})}{4}$.
Substituting this, we see that

$E_{t_{1}\sim\mathbb{U}(I_{1}^{S})}[\dots[{\mathbb{E}}_{t_{n}\sim\mathbb{U}(I_{d/3}^{S})}[\mathcal{L}_{r}(M_{S},{\mathcal{D}}_{a})]\dots]\geq\frac{1}{80d}\sum_{i=1}^{d/3}\ell(I_{i}^{S}).$

Finally, by taking expectations over $S\sim{\mathcal{F}}_{n}$, we see that

$\begin{split}{\mathbb{E}}_{{\mathcal{D}}\sim\Pi}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(A_{S},{\mathcal{D}})]]&={\mathbb{E}}_{S\sim{\mathcal{F}}_{n}}{\mathbb{E}}_{{\mathcal{D}}\sim(\Pi|S)}[\mathcal{L}_{r}(M_{S},{\mathcal{D}})]]\\\
&\geq{\mathbb{E}}_{S\sim{\mathcal{F}}_{n}}\frac{1}{80d}\sum_{i=1}^{d/3}\ell(I_{i}^{S})\\\
&=\frac{1}{80d}\sum_{1}^{d/3}{\mathbb{E}}_{S\sim{\mathcal{F}}}[\ell(I_{i}^{S})]\\\
&=\frac{1}{80d}\sum_{1}^{d/3}{\mathbb{E}}_{{\mathcal{D}}\sim\Pi}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\ell(I_{i}^{S})]\\\
&\geq\frac{1}{80d}\sum_{1}^{d/3}\Omega(\frac{d}{n})=\Omega(\frac{d}{n}),\end{split}$

where the last step follows from Lemma 48. ∎

Finally, we can prove Theorem 14.

###### Proof.

(Theorem 14). First, by Lemmas 27 and 39, we see that
$\Pi\subseteq{\mathcal{F}}_{r,\rho}$ (provided $\rho>10$). Next, by Lemma 49,
for any $n$ there must exists some ${\mathcal{D}}\sim\Pi$ such that
${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[\mathcal{L}_{r}(M_{S},{\mathcal{D}})]\geq\Omega(\frac{d}{n})$.
Thus selecting this distribution suffices. This concludes the proof. ∎

##  Appendix C Proofs for Algorithm 1

This section is divided into 2 parts. In section C.1, we show that for the
case in which our data distribution ${\mathcal{D}}$ is linearly $r$-separated
by some hyperplane through the origin, the desired error bound holds. That is,
we prove Theorem 19 under this assumption.

Next, in section C.2, we show how to generalize Algorithm 1 to arbitrary
linearly $r$-separated distributions, and subsequently prove Theorem 19 in the
general case.

###  C.1 Origin Case

We begin by precisely stating the conditions required in the “origin” case. We
assume the following properties hold for our data distribution
${\mathcal{D}}$. We let $S_{r}^{+}$ and $S_{r}^{-}$ be defined as in section
4.

  1. 1.

There exists $R>0$ such that for all $x\in S_{r}^{+}\cup S_{r}^{-}$,
$||x||_{2}\leq R$.

  2. 2.

There exists a unit vector $u\in\mathbb{R}^{d}$ and $\gamma_{r}>0$ such that

     * •

$\mathcal{L}_{r}(f_{u,0},{\mathcal{D}})=0$, where $f_{u,0}$ denotes the linear
classifier with decision boundary $\langle u,x\rangle=0$.

     * •

$S_{r}^{+}\cup S_{r}^{-}$ has distance at least $\gamma_{r}$ from the decision
boundary of $f_{w}$. That is, $||S_{r}^{+}\cup
S_{r}^{-}-H_{u,0}||_{2}\geq\gamma_{r}$.

  3. 3.

By the previous conditions, it follows that $\langle
u,yx^{\prime}\rangle\geq\gamma_{r}$ for all $(x,y)\sim{\mathcal{D}}$, and
$x^{\prime}\in B_{p}(x,r)$. This is because $u$ is a unit vector.

Next, before analyzing Algorithm 1, we will first give a slight modification
of the algorithm that lends itself to better analysis. The only difference is
that in this new algorithm, we first randomly sample $k\sim\\{1,2,\dots,n\\}$,
and then only train on the first $r$ data-points of our training sample.

Algorithm 3 Modified-Adversarial-Perceptron

1: Input: $S=\\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\\}\sim{\mathcal{D}}^{n},$

2: $w\leftarrow 0$

3: $k\sim\mathbb{U}(\\{0,1,2,\dots,n\\})$

4: for $i=1\dots k$ do

5: $z=\operatorname*{arg\,min}_{||z-x_{i}||_{p}\leq r}y_{i}\langle w,z\rangle$

6: if $\langle w,y_{i}z\rangle\leq 0$ then

7: $w\leftarrow w+y_{i}z$

8: end if

9: end for

10: return $f_{w,0}$

We will show that Algorithm 3 satisfies the guarantees of Theorem 51. We begin
with the following, key lemma.

######  Lemma 50.

Under the assumptions above about ${\mathcal{D}}$, Algorithm 3 makes at most
$\frac{R^{2}}{\gamma_{r}^{2}}$ updates to $w$.

###### Proof.

Let $w_{t}$ denote our weight vector after we make $t$ updates. Observe that
$w_{t}=w_{t-1}+y_{t}x_{t}+z^{\prime}$ where $(x_{t},y_{t})$ denotes the point
we made a mistake on, and $z^{\prime}=\operatorname*{arg\,min}_{|z|_{p}\leq
r}\langle w,z\rangle$. Letting $x_{t}^{\prime}=x_{t}+y_{t}z^{\prime}$, we see
that $w_{t}=w_{t-1}+y_{t}x_{t}^{\prime}$. Now the key observation is that
$(x_{t}^{\prime},y_{t})\in S_{r}^{+}\cup S_{r}^{-}$, and as a result, it
follows that $\langle u,y_{t}x_{t}^{\prime}\rangle\geq\gamma_{r}$. Using this,
we see that

$\begin{split}\langle u,w_{t}\rangle&=\langle
u,w_{t-1}+y_{t}x_{t}^{\prime}\rangle\\\ &=\langle u,w_{t-1}\rangle+\langle
u,y_{t}x_{t}^{\prime}\rangle\\\ &\geq\langle
u,w_{t-1}\rangle+\gamma_{r}.\end{split}$

Thus, by a simple proof by induction, we see that $\langle w_{t},u\rangle\geq
t\gamma_{r}$.

Next, observe that we must have $\langle
w_{t-1},y_{t}x_{t}^{\prime}\rangle\leq 0$. This is because $w_{t-1}$ must
missclassify $(x_{t}^{\prime},y_{t})$ (thus failing to be astute at
$(x_{t},y_{t})$) in order for it to be updated. Substituting this, we see that

$\begin{split}||w_{t}||_{2}&=\sqrt{\langle w_{t},w_{t}\rangle}\\\
&=\sqrt{\langle
w_{t-1}+x_{t}^{\prime}y_{t},w_{t-1}+x_{t}^{\prime}y_{\rangle}}\\\
&=\sqrt{\langle w_{t-1},w_{t-1}\rangle+2\langle
w_{t-1},x_{t}^{\prime}y_{t}\rangle+\langle
x_{t}^{\prime},x_{t}^{\prime}\rangle}\\\
&\leq\sqrt{||w_{t-1}||_{2}^{2}+0+R^{2}},\end{split}$

with the last inequality holding since $|x_{t}^{\prime}|_{2}\leq R$. Thus, by
a simple proof by induction, we see that $||w_{t}||_{2}\leq R\sqrt{t}$.

Finally, since $u$ is a unit vector, it follows that $||w_{t}||_{2}\geq\langle
w_{t},u$. Substituting our inequalities, we find that
$R\sqrt{t}\geq\gamma_{r}t$ which implies that
$t\leq\frac{R^{2}}{\gamma_{r}^{2}}$. Since $t$ is the number of mistakes we
make, the result follows. ∎

######  Lemma 51.

Let ${\mathcal{D}}$ be a distribution with the assumptions above. For any
$S\sim{\mathcal{D}}^{n}$, let $f_{S}$ denote the classifier learned by
Algorithm 3. Then

${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}\mathcal{L}_{r}(f_{S},{\mathcal{D}})\leq\frac{R^{2}}{\gamma_{r}^{2}(n+1)}.$

This Theorem directly follows from the classic online to offline result
(Theorem 3 of (Freund & Schapire, 1999)). For completeness, we include a proof
in our context.

###### Proof.

Fix any $n$ and consider running Algorithm 3 on $S\sim{\mathcal{D}}^{n}$. Let
$L_{t}$ denote the expected robust loss of our classifier conditioning on
$k=t$, and let $L^{*}$ denote the expected overall loss of our classifier. It
follows that

${\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}L^{*}=\frac{1}{n+1}\sum_{t=0}^{n}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[L^{*}|k=t]=\frac{1}{n+1}\sum_{t=0}^{n}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[L_{t}].$

Next, let $T\sim{\mathcal{D}}^{n+1}$ be a separate i.i.d drawn sample, and
suppose we run the adversarial perceptron algorithm on the entirety of $T$
(i.e. rung Algorithm 3 on $T$ by setting $k=n+1$). For $1\leq t\leq n+1$, let
$X_{t}$ be the indicator variable for whether the $t$th point in $T$ requires
an update on $w$ (i.e. the classifier is not astute at $w$). There are two
important observations to make.

First, we have that
${\mathbb{E}}_{T\sim{\mathcal{D}}^{n+1}}[X_{t}]={\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[L_{t-1}]$.
This is because $X_{t}$ is an indicator variable for a classifier trained on
precisely $t-1$ i.i.d training examples lacking astuteness for a randomly
drawn point from ${\mathcal{D}}$. Second, we have that
$\sum_{t=1}^{n+1}X_{t}\leq\frac{R^{2}}{\gamma_{r}^{2}}$. This is because each
$\sum X_{t}$ is precisely the number of updates that perceptron makes on $T$,
which is bounded by Lemma 50. By combining these two observations, we see that

$\begin{split}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[L^{*}]&=\frac{1}{n+1}\sum_{t=0}^{n}{\mathbb{E}}_{S\sim{\mathcal{D}}^{n}}[L_{t}]\\\
&=\frac{1}{n+1}\sum_{t=0}^{n}{\mathbb{E}}_{T\sim{\mathcal{D}}^{n+1}}[X_{t+1}]\\\
&=\frac{1}{n+1}{\mathbb{E}}_{T\sim{\mathcal{D}}^{n+1}}[\sum_{t=1}^{n+1}X_{t}]\\\
&\leq\frac{R^{2}}{\gamma_{r}^{2}(n+1)},\end{split}$

as desired. ∎

###  C.2 General Case

In general case, we no longer assume that the optimal classifier $f_{u,b}$
passes through the origin. To account for this, we will need to first adapt
our algorithm. The basic idea is to simply append a $1$ to the vectors $x$ and
increase the dimension $d$ by $1$. We are then left with solving a $d+1$
dimensional problem in which the data is once-again separated by a hyperplane
passing through the origin.

We begin with two useful sets of notation.

######  Definition 52.

We use the following notation:

  * •

For any $x\in\mathbb{R}^{d}$ and $R\in\mathbb{R}$, we let
$x|R\in\mathbb{R}^{d+1}$ denote the $d+1$ dimensional vector obtained by
appending the value $R$ to $x$.

  * •

For $w\in\mathbb{R}^{d+1}$, let $||w||_{q}^{*}$ denote the $\ell_{q}$ norm of
the first $d$ coordinates of $w$.

  * •

For $x\in\mathbb{R}^{d+1}$, let $B_{p}^{*}(x,r)$ denote all
$z\in\mathbb{R}^{d+1}$ such that $||z-x||_{p}\leq r$ and such that $z$ and $x$
both share the same last coordinate.

  * •

For
$S=\\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\\}\subset\mathbb{R}^{d+1}\times\\{\pm
1\\}$, let $R_{S}$ denote $\max_{i\neq j}||x_{i}-x_{j}||_{2}$.

We now propose the following modified version of Algorithm 1, that is capable
of handling any dataset, including ones that aren’t separated by a hyperplane
through the origin.

Algorithm 4 General-Adversarial-Perceptron

1: Input: $S=\\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\\}\sim{\mathcal{D}}^{n},$

2: $x_{i}^{\prime}\leftarrow x_{i}-x_{1}$.

3: $R_{S}=diam_{2}(S)$

4: $w\leftarrow 0\in\mathbb{R}^{d+1}$

5: Randomly permute $S$

6: Randomly choose $k\in\\{1,2,3,\dots,n\\}$.

7: for $t=1\dots k$ do

8: if $\langle w,y_{t}(x_{t}|R_{S})\rangle\leq r||w||_{q}^{*}$ then

9: $z^{\prime}=\operatorname*{arg\,min}_{|z|_{p}\leq r}\langle w,z|0\rangle$

10: $w\leftarrow w+y_{t}(x_{t}|R_{S})+z^{\prime}|0$

11: end if

12: end for

13: $w^{*}\leftarrow$ first $d$ coordinates of $w$

14: $b\leftarrow$ the last element of $w$

15: Return $f_{w^{*},\langle w^{*},x_{1}\rangle-bR_{S}}$

The basic idea of the algorithm is to first translate $S$ so that one point is
the origin, and then append $R_{S}$ to every vector in $S$ so that each vector
is now $d+1$ dimensional. After doing this, we apply Algorithm 1 as before
with one important difference: for our adversarial attacks, we make sure to
not change the last coordinate.

We now show that this algorithm has a similar performance to our old
algorithm. We first prove a helpful lemma.

######  Lemma 53.

Let ${\mathcal{D}}$ be any linearly $r$-separated distribution, and let
$S\sim{\mathcal{D}}^{n}$ such that $S$ has positively and negatively labeled
examples. Let $x_{i}^{\prime}=x_{i}-x_{1}$ for $1\leq i\leq n$. Then the
following hold.

  * •

There exists a unit vector $u\in\mathbb{R}^{d+1}$ such that for all
$(x_{i},y_{i})\in S$, $\min_{z\in B_{p}^{*}(x_{i}^{\prime})}\langle
u,y_{i}(z|R_{S})\rangle\geq\frac{\gamma_{r}({\mathcal{D}})}{\sqrt{2}}.$

  * •

For all $(x_{i},y_{i})\in S$,
$||x_{i}^{\prime}|R_{S}||_{2}\leq\sqrt{2}diam_{2}({\mathcal{D}})$.

###### Proof.

Without loss of generality, we will assume $x_{1}=0$ so that we can safely
ignore the differences between $x_{i}^{\prime}$ and $x_{i}$. Since
${\mathcal{D}}$ is $r$-separated, there exist $w,b$ (with $w$ a unit vector)
such that

$\langle w,zy\rangle\geq by+\gamma_{r}({\mathcal{D}}),$

for all $(x,y)\sim{\mathcal{D}}$ and $z\in B_{p}(x,r)$. Furthermore, since
$x_{1}=0$, it follows that $||x||_{2}\leq\text{diam}_{2}({\mathcal{D}})$ for
all $(x,y)\sim{\mathcal{D}}$. This immediately implies that
$||x_{i}|R_{S}||_{2}\leq\sqrt{\text{diam}_{2}({\mathcal{D}})^{2}+R_{S}^{2}}\leq\sqrt{2}\text{diam}_{2}({\mathcal{D}})$,
yielding the second part of the lemma.

For the first part, observe that we can rearrange the equation above, we see
that

$\langle w|-\frac{b}{R_{S}},zy|R_{S}\rangle\geq\gamma_{r}({\mathcal{D}}).$

The key observation is that the first equation implies that $b\leq R_{S}$.
This is because $S$ contains positively and negatively labeled examples, and
consequently $\langle w,x_{i}\rangle\geq b+\gamma_{r}({\mathcal{D}})>b$ for
some $x_{i}$ such that $|x_{i}|=R_{S}$. Thus, it follows that the unit vector
$u=\frac{w|\frac{-b}{R_{S}}}{\sqrt{1+b^{2}/R_{S}^{2}}}$ has the desired
property, by observing that $\sqrt{1+b^{2}/R_{S}^{2}}\leq\sqrt{2}$. ∎

Lemma 53 allows us to analyze the performance of Algorithm 4. The basic idea
is that our performance on the transformed data in $\mathbb{R}^{d+1}$ is
isomorphic to its performance on the data in $\mathbb{R}^{d}$. As a
consequence, we can apply the same argument as in Theorem 51 to get a bound on
the error estimate. However, this bound must be given in terms of the diameter
and robust margin of the transformed data: quantities that have been bounded
in Lemma 53. Thus, putting this all together, Theorem 19 follows.

##  Appendix D Details for Kernel Algorithm

Next, we find analogs of linear $r$-separability and the robust margin when
considering kernels. First, we define an embedding function.

######  Definition 54.

Let $K:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{+}$ be a kernel
similarity function. Then there exists a Hilbert space $H$ and map
$\phi:\mathbb{R}^{d}\to H$ such that for all $x_{1},x_{2}\in\mathbb{R}^{d},$
we have

$K(x_{1},x_{2})=\langle\phi(x_{1}),\phi(x_{2})\rangle.$

We call $\phi$ the embedding function and $H$ the embedding space.

The key idea of this section is that Kenrel classifiers correspond to linear
classifiers in embedded space. This is the essence of the “kernel trick.”
Formally, we have the following, well-known theorem.

######  Theorem 55.

Let $K:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}^{+}$ be a kernel
similarity function. Let
$T=\\{(x_{1},y_{1}),\dots,(x_{m},y_{m})\\}\subset\mathbb{R}^{d}\times\\{\pm
1\\}$ be a set of labeled points, and $\alpha\in\mathbb{R}^{m}$ be a vector of
$m$ real numbers. Then for all $x\in\mathbb{R}^{d}$, we have that

$\sum_{i=1}^{m}\alpha_{i}y_{i}K(x_{i},x)=\big{\langle}\sum_{i=1}^{m}\alpha_{i}y_{i}\phi(x_{i}),\phi(x)\big{\rangle}.$

Because of this, if we let $w=\sum_{i=1}^{m}\alpha_{i}y_{i}\phi(x_{i})$, then
the kernel classifier $f_{T,\alpha}^{k}$ satisfies
$f_{T,\alpha}^{k}(x)=f_{w,0}(\phi(x))$, where the latter classifier is the
linear classifier in $H$ with weight vector $w$.

The main idea behind Algorithm 2, is that it corresponds to running Algorithm
1 inside the embedded space of the kernel $K$. In particular, the kernel-
perceptron update step precisely corresponds to the dual-form of the
perceptron-update step inside embedded space. It follows from Theorem 55 that
the following algorithm is identical to Algorithm 2.

Algorithm 5 Adversarial-Kernel-Perceptron

1: Input: $S=\\{(x_{1},y_{1}),\dots,(x_{n},y_{n})\\}\sim{\mathcal{D}}^{n},$
Similarity function, $K$,

2: $w\leftarrow 0$

3: for $i=1\dots n$ do

4: $z=\operatorname*{arg\,min}_{||z-x||_{p}\leq r}y_{i}\langle
w,\phi(z)\rangle$

5: if $\langle y_{i}w,\phi(z)\rangle\leq 0$ then

6: $w=w+y_{i}\phi(z)$

7: end if

8: end for

9: return $f_{w,0}\circ\phi$

In particular, by comparing Algorithms 2 and 5, we have by Theorem 55 that for
all time steps $t$,

$w=\sum_{(z,y)\in T}y\phi(z).$

Therefore, to analyze the performance of Algorithm 2, it suffices to analyze
Algorithm 5. However, we already have built to the tools for doing this: all
of the results from Section C.1 apply to Algorithm 5 since the only difference
is replacing $\mathbb{R}^{d}$ with $H$, the embedding space of $K$.

We now proceed by giving the corresponding assumptions on ${\mathcal{D}}$
needed for Theorem 21. We begin by first defining $(K,r)$-separability and
$K$-robust margin, $\gamma_{r,K}$, the Kernel analogs of linear
$r$-separability (Definition 12) and the robust margin (Definition 17).

######  Definition 56.

For any $r>0$, a distribution ${\mathcal{D}}$ over $\mathbb{R}^{d}\times\\{\pm
1\\}$ is $(K,r)$-separable if there exists a kernel classifier
$f_{S,\alpha}^{K}$ such that
$\mathcal{L}_{r}(f_{S,\alpha}^{K},{\mathcal{D}})=0$.

To define the $K$-robust margin, we will once again need the sets $S_{r}^{+}$
and $S_{r}^{-}$ defined in equation 1 (top right of page 7). Recall that these
sets denote the positively and negatively labeled elements from
$supp({\mathcal{D}})$ including all adversarial perturbations of those points.

######  Definition 57.

Let ${\mathcal{D}}$ be a $(K,r)$-separable distribution over
$\mathbb{R}^{d}\times\\{\pm 1\\}$. Then ${\mathcal{D}}$ has $K$-robust margin
$\gamma_{r}$ if $\gamma_{r}$ is the largest real number such that there exists
a kernel classifier $f_{T,\alpha}^{K}$, such that the following conditions
hold.