# Theoretical Analysis of Adversarial Learning:
A Minimax Approach

Zhuozhuo Tu Jingwei Zhang11footnotemark: 1 Dacheng Tao11footnotemark: 1 UBTECH
Sydney AI Centre and the School of Computer Science in the Faculty of
Engineering and Information Technologies at The University of Sydney, NSW,
2006, Australia<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Here we propose a general theoretical method for analyzing the risk bound in
the presence of adversaries. Specifically, we try to fit the adversarial
learning problem into the minimax framework. We first show that the original
adversarial learning problem can be reduced to a minimax statistical learning
problem by introducing a transport map between distributions. Then, we prove a
new risk bound for this minimax problem in terms of covering numbers under a
weak version of Lipschitz condition. Our method can be applied to multi-class
classification problems and commonly used loss functions such as the hinge and
ramp losses. As some illustrative examples, we derive the adversarial risk
bounds for SVMs, deep neural networks, and PCA, and our bounds have two data-
dependent terms, which can be optimized for achieving adversarial robustness.

##  1 Introduction

Machine learning models, especially deep neural networks, have achieved
impressive performance across a variety of domains including image
classification, natural language processing, and speech recognition. However,
these techniques can easily be fooled by adversarial examples, i.e., carefully
perturbed input samples aimed to cause misclassification during the test
phase. This phenomenon was first studied in spam filtering [15, 32, 33] and
has attracted considerable attention since 2014, when Szegedy et al., [43]
noticed that small perturbations in images can cause misclassification in
neural network classifiers. Since then, there has been considerable focus on
developing adversarial attacks against machine learning algorithms [22, 9, 8,
4, 45], and, in response, many defense mechanisms have also been proposed to
counter these attacks [23, 21, 16, 42, 34]. These works focus on creating
optimization-based robust algorithms, but their generalization performance
under adversarial input perturbations is still not fully understood.

Schmidt et al., [39] recently discussed the generalization problem in the
adversarial setting and showed that the sample complexity of learning a
specific distribution in the presence of $l_{\infty}$-bounded adversaries
increases by an order of $\sqrt{d}$ for all classifiers. The same paper
recognized that deriving the agnostic-distribution generalization bound
remained an open problem [39]. In a subsequent study, Cullina et al., [14]
extended the standard PAC-learning framework to the adversarial setting by
defining a corrupted hypothesis class and showed that the VC dimension of this
corrupted hypothesis class for halfspace classifiers does not increase in the
presence of an adversary. While their work provided a theoretical
understanding of the problem of learning with adversaries, it had two
limitations. First, their results could only be applied to binary problems,
whereas in practice we usually need to handle multi-class problems. Second,
the 0-1 loss function used in their work is not convex and thus very hard to
optimize.

In this paper, we propose a general theoretical method for analyzing
generalization performance in the presence of adversaries. In particular, we
attempt to fit the adversarial learning problem into the minimax framework
[29]. In contrast to traditional statistical learning, where the underlying
data distribution $P$ is unknown but fixed, the minimax framework considers
the uncertainty about the distribution $P$ by introducing an ambiguity set and
then aims to minimize the risk with respect to the worst-case distribution in
this set. Motivated by Lee and Raginsky, [29], we first note that the
adversarial expected risk over a distribution $P$ is equivalent to the
standard expected risk under a new distribution $P^{\prime}$. Since this new
distribution is not fixed and depends on the hypothesis, we instead consider
the worst case. In this way, the original adversarial learning problem is
reduced to a minimax problem, and we use the minimax approach to derive the
risk bound for the adversarial expected risk. Our contributions can be
summarized as follows.

  * •

We propose a general method for analyzing the risk bound in the presence of
adversaries. Our method is general in several respects. First, the adversary
we consider is general and encompasses all $l_{p}$ bounded adversaries for
$p\geq 1$. Second, our method can be applied to multi-class problems and other
commonly used loss functions such as the hinge loss and ramp loss, whereas
Cullina et al., [14] only considered the binary classification problem and the
0-1 loss.

  * •

We prove a new bound for the local worst-case risk under a weak version of
Lipschitz condition. Our bound is always better than that of Lee and Raginsky,
[30], and can recover the standard non-adversarial risk bound by setting the
radius $\epsilon_{\mathcal{B}}$ of the adversary to 0, whereas Lee and
Raginsky, [30] give a $\epsilon_{\mathcal{B}}$-free bound.

  * •

We derive the adversarial risk bounds for SVM, deep neural networks, and PCA.
Our bounds have two data-dependent terms, suggesting that minimizing the sum
of the two terms can help achieve adversarial robustness.

The remainder of this paper is structured as follows. In Section 2, we discuss
related works. Section 3 formally defines the problem, and we present our
theoretical method in Section 4. The adversarial risk bounds for SVM, neural
networks, and PCA are described in Section 5, and we conclude and discuss
future directions in Section 6.

##  2 Related Work

Our work leverages some of the benefits of statistical machine learning,
summarized as follows.

###  2.1 Generalization in Supervised Learning

Generalization is a central problem in supervised learning, and the
generalization capability of learning algorithms has been extensively studied.
Here we review the salient aspects of generalization in supervised learning
relevant to this work.

Two main approaches are used to analyze the generalization bound of a learning
algorithm. The first is based on the complexity of the hypothesis class, such
as the VC dimension [46, 47] for binary classification, Rademacher and
Gaussian complexities [7, 5], and the covering number [55, 54, 6]. Note that
hypothesis complexity-based analyses of generalization error are algorithm
independent and consider the worst-case generalization over all functions in
the hypothesis class. In contrast, the second approach is based on the
properties of a learning algorithm and is therefore algorithm dependent. The
properties characterizing the generalization of a learning algorithm include,
for example, algorithmic stability [11, 40, 31], robustness [51], and
algorithmic luckiness [25]. Some other methods exist for analyzing the
generalization error in machine learning such as the PAC-Bayesian approach
[36, 2], compression-based bounds [28, 3], and information-theoretic
approaches [50, 1, 38, 53].

###  2.2 Minimax Statistical Learning

In contrast to standard empirical risk minimization in supervised learning,
where test data follow the same distribution as training data, minimax
statistical learning arises in problems of distributionally robust learning
[17, 19, 29, 30, 41] and minimizes the worst-case risk over a family of
probability distributions. Thus, it can be applied to the learning setting in
which the test data distribution differs from that of the training data, such
as in domain adaptation and transfer learning [12]. In particular, Gao and
Kleywegt, [19] proposed a dual representation of worst-case risk over the
ambiguity set of probability distributions, which was given by balls in
Wasserstein space. Then, Lee and Raginsky, [29] derived the risk bound for
minimax learning by exploiting the dual representation of worst-case risk
proposed by Gao and Kleywegt, [19]. However, the minimax risk bound proposed
in Lee and Raginsky, [29] would go to infinity and thus become vacuous as
$\epsilon_{\mathcal{B}}\rightarrow 0$. During the preparation of the initial
draft of this paper, Lee and Raginsky, [30] presented a new bound by imposing
a Lipschitz assumption to avoid this problem. However, their new bound was
$\epsilon_{\mathcal{B}}$-free and cannot recover the usual risk bound by
setting $\epsilon_{\mathcal{B}}=0$. Sinha et al., [41] also provided a similar
upper bound on the worst-case population loss over distributions defined by a
certain distributional Wasserstein distance, and their bound was efficiently
computable by a principled adversarial training procedure and hence certified
a level of robustness. However their training procedure required that the
penalty parameter should be large enough and thus can only achieve a small
amount of robustness. Here we improve on the results in Lee and Raginsky, [29,
30] and present a new risk bound for the minimax problem.

###  2.3 Learning with Adversaries

The existence of adversaries during the test phase of a learning algorithm
makes learning systems untrustworthy. There is extensive literature on
analysis of adversarial robustness [48, 18, 24, 20] and design of provable
defense against adversarial attacks[49, 37, 34, 41], in contrast to the
relatively limited literature on risk bound analysis of adversarial learning.
A comprehensive review of works on adversarial machine learning can be found
in Biggio and Roli, [10]. Concurrently to our work, Khim and Loh, 2018a [26]
and Yin et al., [52] provided different approaches for deriving adversarial
risk bounds. Khim and Loh, 2018a [26] derived adversarial risk bounds for
linear classifiers and neural networks using a method called function
transformation. However, their approach can only be applied to binary
classification. Yin et al., [52] gave similar adversarial risk bounds as Khim
and Loh, 2018a [26] through the lens of Rademacher complexity. Although they
provided risk bounds in multi-class setting, their work focused on
$l_{\infty}$ adversarial attacks and was limited to one-hidden layer ReLU
neural networks. After the initial preprint of this paper, Khim and Loh, 2018b
[27] extended their method to multi-class setting at the expense of incurring
an extra factor of the number of classes in their bound. In contrast, our
multi-class bound does not have explicit dependence on this number. We hope
that our method can provide new insight into analysis of the adversarial risk
bounds.

##  3 Problem Setup

We consider a standard statistical learning framework. Let
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$ be a measurable instance space
where $\mathcal{X}$ and $\mathcal{Y}$ represent feature and label spaces,
respectively. We assume that examples are independently and identically
distributed according to some fixed but unknown distribution $P$. The learning
problem is then formulated as follows. The learner considers a class
$\mathcal{H}$ of hypothesis $h:\mathcal{X}\rightarrow\mathcal{Y}$ and a loss
function $l:\mathcal{Y}\times\mathcal{Y}\rightarrow\mathbb{R}_{+}$. The
learner receives $n$ training examples denoted by
$S=((x_{1},y_{1}),(x_{2},y_{2}),\cdots,(x_{n},y_{n}))$ drawn i.i.d. from $P$
and tries to select a hypothesis $h\in\mathcal{H}$ that has a small expected
risk. However, in the presence of adversaries, there will be imperceptible
perturbations to the input of examples, which are called adversarial examples.
We assume that the adversarial examples are generated by adversarially
choosing an example from neighborhood $N(x)$. We require $N(x)$ to be nonempty
and that some choice of examples is always available. Throughout this paper,
we assume that $N(x)=\\{x^{\prime}:x^{\prime}-x\in\mathcal{B}\\}$, where
$\mathcal{B}$ is a nonempty, closed, convex, origin-symmetric set. Note that
the definition of $\mathcal{B}$ is very general and encompasses all $l_{p}$
-bounded adversaries when $p\geq 1$. We next give the formal definition of
adversarial expected and empirical risk to measure the learner’s performance
in the presence of adversaries.

######  Definition 1.

(Adversarial Expected Risk). The adversarial expected risk of a hypothesis
$h\in\mathcal{H}$ over the distribution $P$ in the presence of an adversary
constrained by $\mathcal{B}$ is

$R_{P}(h,\mathcal{B})=\mathbb{E}_{(x,y)\sim P}[\max_{x^{\prime}\in
N(x)}l(h(x^{\prime}),y)].$

If $\mathcal{B}$ is the zero-dimensional space $\\{\mathbb{0}\\}$, then the
adversarial expected risk will reduce to the standard expected risk without an
adversary. Since the true distribution is usually unknown, we instead use the
empirical distribution to approximate the true distribution, which is equal to
$(x_{i},y_{i})$ with probability $1/n$ for each $i\in\\{1,\cdots,n\\}$. That
gives us the following definition of adversarial empirical risk.

######  Definition 2.

(Adversarial Empirical Risk ). The adversarial empirical risk of $h$ in the
presence of an adversary constrained by $\mathcal{B}$ is

$R_{P_{n}}(h,\mathcal{B})=\mathbb{E}_{(x,y)\sim P_{n}}[\max_{x^{\prime}\in
N(x)}l(h(x^{\prime}),y)],$

where $P_{n}$ represents the empirical distribution.

In the next section, we derive the adversarial risk bounds.

##  4 Main Results

In this section, we present our main results. The trick is to pushforward the
original distribution $P$ into a new distribution $P^{\prime}$ using a
transport map $T_{h}:\mathcal{Z}\rightarrow\mathcal{Z}$ satisfying

$R_{P}(h,\mathcal{B})=R_{P^{\prime}}(h),$

where $R_{P^{\prime}}(h)=\mathbb{E}_{(x,y)\sim P^{\prime}}l(h(x),y)$ is the
standard expected risk without the adversary. Therefore, an upper bound on the
expected risk over the new distribution leads to an upper bound on the
adversarial expected risk.

Note that the new distribution $P^{\prime}$ is not fixed and depends on the
hypothesis $h$. As a result, traditional statistical learning cannot be
directly applied. However, note that these new distributions lie within a
Wasserstein ball centered on $P$. If we consider the worst case within this
Wasserstein ball, then the original adversarial learning problem can be
reduced to a minimax problem. We can therefore use the minimax approach to
derive the adversarial risk bound. We first introduce the Wasserstein distance
and minimax framework.

###  4.1 Wasserstein Distance and Local Worst-case Risk

Let $(\mathcal{Z},d_{\mathcal{Z}})$ be a metric space where
$\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$ and $d_{\mathcal{Z}}$ is defined as

$d_{\mathcal{Z}}^{p}(z,z^{\prime})=d_{\mathcal{Z}}^{p}((x,y),(x^{\prime},y^{\prime}))=(d_{\mathcal{X}}^{p}(x,x^{\prime})+d_{\mathcal{Y}}^{p}(y,y^{\prime}))$

with $d_{\mathcal{X}}$ and $d_{\mathcal{Y}}$ representing the metric in the
feature space and label space respectively. For example, if
$\mathcal{Y}=\\{1,-1\\}$, $d_{\mathcal{Y}}(y,y^{\prime})$ can be
$\mathbbm{1}_{(y\neq y^{\prime})}$, and if $\mathcal{Y}=[-B,B]$,
$d_{\mathcal{Y}}(y,y^{\prime})$ can be $(y-y^{\prime})^{2}$. In this paper, we
require that $d_{\mathcal{X}}$ is translation invariant, i.e.,
$d_{\mathcal{X}}(x,x^{\prime})=d_{\mathcal{X}}(x-x^{\prime},0)$. With this
metric, we denote with $\mathcal{P}(\mathcal{Z})$ the space of all Borel
probability measures on $\mathcal{Z}$, and with $\mathcal{P}_{p}(\mathcal{Z})$
the space of all $P\in\mathcal{P}(\mathcal{Z})$ with finite $p$th moments for
$p\geq 1$:

$\mathcal{P}_{p}(\mathcal{Z}):=\\{P\in\mathcal{P}(\mathcal{Z}):\mathbb{E}_{P}[d_{\mathcal{Z}}^{p}(z,z_{0})]<\infty\
for\ z_{0}\in\mathcal{Z}\\}.$

Then, the $p$th Wasserstein distance between two probability measures
$P,Q\in\mathcal{P}_{p}(\mathcal{Z})$ is defined as

$W_{p}(P,Q):=\inf_{M\in\Gamma(P,Q)}(\mathbb{E}_{M}[d_{\mathcal{Z}}^{p}(z,z^{\prime})])^{1/p},$

where $\Gamma(P,Q)$ denotes the collection of all measures on
$\mathcal{Z}\times\mathcal{Z}$ with marginals P and Q on the first and second
factors, respectively.

Now we define the local worst-case risk of $h$ at $P$,

$R_{\epsilon,p}(P,h):=\sup_{Q\in B_{\epsilon,p}^{W}(P)}R_{Q}(h),$

where
$B_{\epsilon,p}^{W}(P):=\\{Q\in\mathcal{P}_{p}(Z):W_{p}(P,Q))\leq\epsilon\\}$
is the $p$-Wasserstein ball of radius $\epsilon\geq 0$ centered at $P$.

With these definitions, we next show the adversarial expected risk can be
related to the local worst-case risk by a transport map $T_{h}$.

###  4.2 Transport Map

Define a mapping $T_{h}:\mathcal{Z}\rightarrow\mathcal{Z}$

$z=(x,y)\rightarrow(x^{*},y),$

where $x^{*}=\arg\max_{x^{\prime}\in N(x)}l(h(x^{\prime}),y)$. By the
definition of $d_{\mathcal{Z}}$, it is easy to obtain
$d_{\mathcal{Z}}((x,y),(x^{*},y))=d_{\mathcal{X}}(x,x^{*})$. We now prove that
the adversarial expected risk can be related to the standard expected risk via
the mapping $T_{h}$.

######  Lemma 1.

Let $P^{\prime}=T_{h}\\#P$, the pushforward of $P$ by $T_{h}$, then we have

$R_{P}(h,\mathcal{B})=R_{P^{\prime}}(h).$

###### Proof.

By the definition, we have

$\begin{array}[]{ll}R_{P}(h,\mathcal{B})=\mathbb{E}_{(x,y)\sim
P}[\max_{x^{\prime}\in N(x)}l(h(x^{\prime}),y)]\\\ =\mathbb{E}_{(x,y)\sim
P}[l(h(x^{*}),y)]=\mathbb{E}_{(x,y)\sim P^{\prime}}[l(h(x),y)]\\\ \end{array}$

So $R_{P}(h,\mathcal{B})=R_{P^{\prime}}(h)$. ∎

By this lemma, the adversarial expected risk over a distribution $P$ is
equivalent to the standard expected risk over a new distribution $P^{\prime}$.
However since the new distribution is not fixed and depends on the hypothesis
$h$, traditional statistical learning cannot be directly applied. Luckily, the
following lemma proves that all these new distributions locate within a
Wasserstein ball centered at $P$.

######  Lemma 2.

Define the radius of the adversary $\mathcal{B}$ as
$\epsilon_{\mathcal{B}}:=\sup_{x\in\mathcal{B}}d_{\mathcal{X}}(x,0)$. For any
hypothesis $h$ and the corresponding $P^{\prime}=T_{h}\\#P$, we have

$W_{p}(P,P^{\prime})\leq\epsilon_{\mathcal{B}}.$

###### Proof.

By the definition of Wasserstein distance,

$W_{p}^{p}(P,P^{\prime})\leq\mathbb{E}_{P}[d^{p}_{\mathcal{Z}}(Z,T_{h}(Z))]=\mathbb{E}_{P}[d^{p}_{\mathcal{\mathcal{X}}}(x,x^{*})]\leq\epsilon_{\mathcal{B}}^{p},$

where the last inequality uses the translation invariant property of
$d_{\mathcal{X}}$. Therefore, we have
$W_{p}(P,P^{\prime})\leq\epsilon_{\mathcal{B}}$. ∎

From this lemma, we can see that all possible new distributions lie within a
Wasserstein ball of radius $\epsilon_{\mathcal{B}}$ centered on $P$. So, by
upper bounding the worst-case risk in the ball, we can bound the adversarial
expected risk. The relationship between local worst-case risk and adversarial
expected risk is as follows. Note that this inequality holds for any $p\geq
1$. So, in the rest of the paper, we only discuss the case $p=1$; that is,

$R_{P}(h,\mathcal{B})\leq R_{\epsilon_{\mathcal{B}},1}(P,h),\quad\forall
h\in\mathcal{H}.$ (4.1)

###  4.3 Adversarial Risk Bounds

In this subsection, we first prove a bound for the local worst-case risk.
Then, the adversarial risk bounds can be derived directly by (4.1). For the
convenience of our discussion, we denote a function class $\mathcal{F}$ by
compositing the functions in $\mathcal{H}$ with the loss function
$l(\cdot,\cdot)$, i.e., $\mathcal{F}=\\{(x,y)\rightarrow
l(h(x),y):h\in\mathcal{H}\\}$. The key ingredient of a bound on the local
worst-case risk is the following strong duality result after Gao and Kleywegt,
[19]:

######  Proposition 1.

For any upper semicontinuous function $f:\mathcal{Z}\rightarrow\mathbb{R}$ and
for any $P\in\mathcal{P}_{p}(\mathcal{Z})$,

$R_{\epsilon_{\mathcal{B}},1}(P,f)=\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\mathbb{E}_{P}[\varphi_{\lambda,f}(z)]\\},$

where
$\varphi_{\lambda,f}(z):=\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda\cdot
d_{\mathcal{Z}}(z,z^{\prime})\\}$.

We begin with some assumptions.

######  Assumption 1.

The instance space $\mathcal{Z}$ is bounded:
$diam(\mathcal{Z}):=\sup_{z,z^{\prime}\in\mathcal{Z}}d_{\mathcal{Z}}(z,z^{\prime})<\infty$.

######  Assumption 2.

The functions in $\mathcal{F}$ are upper semicontinuous and uniformly bounded:
$0\leq f(z)\leq M<\infty$ for all $f\in\mathcal{F}$ and $z\in\mathcal{Z}$.

######  Assumption 3.

For any function $f\in\mathcal{F}$ and any $z\in\mathcal{Z}$, there exists a
constant $\lambda$ such that $f(z^{\prime})-f(z)\leq\lambda
d_{\mathcal{Z}}(z,z^{\prime})$ for any $z^{\prime}\in\mathcal{Z}$.

Note that Assumption 3 is a weak version of Lipschitz condition since the
constant $\lambda$ is not fixed and depends on $f$ and $z$. It is easy to see
that if the function $f\in\mathcal{F}$ is $L$-Lipschitz with respect to the
metric $d_{\mathcal{Z}}$, i.e., $|f(z)-f(z^{\prime})|\leq
Ld_{\mathcal{Z}}(z,z^{\prime})$, Assumption 3 automatically holds with
$\lambda$ always being $L$. Assumption 3 is very straightforward. But it is
not easy to use for our proof. For this sake, we give an equivalent expression
to Assumption 3 in the following lemma.

######  Lemma 3.

Assumption 3 holds if and only if for any function $f\in\mathcal{F}$ and any
empirical distribution $P_{n}$, the set
$\\{\lambda:\psi_{f,P_{n}}(\lambda)=0\\}$ is nonempty, where
$\psi_{f,P_{n}}(\lambda):=\mathbb{E}_{P_{n}}(\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda
d_{\mathcal{Z}}(z,z^{\prime})-f(z)\\})$.

The proof of this lemma is contained in Appendix A.

We denote the smallest value in the set as
$\lambda_{f,P_{n}}^{+}:=\inf\\{\lambda:\psi_{f,P_{n}}(\lambda)=0\\}$. In order
to prove the local worst-case risk bound, we need two technical lemmas.

######  Lemma 4.

Fix some $f\in\mathcal{F}$. Define $\bar{\lambda}$ via

$\bar{\lambda}:=\arg\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\lambda,f}(Z)]\\}.$

Then

$\bar{\lambda}\in\left\\{\begin{array}[]{ll}[0,\dfrac{M}{\epsilon_{\mathcal{B}}}]&if\
\epsilon_{\mathcal{B}}\geq\dfrac{M}{\lambda_{f,P_{n}}^{+}}\\\
[\lambda_{f,P_{n}}^{-},\lambda_{f,P_{n}}^{+}]&if\
\epsilon_{\mathcal{B}}<\dfrac{M}{\lambda_{f,P_{n}}^{+}}\\\
\end{array}\right.,$ (4.2)

where
$\lambda_{f,P_{n}}^{-}:=\sup\\{\lambda:\psi_{f,P_{n}}(\lambda)=\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}\\}$
if the set
$\\{\lambda:\psi_{f,P_{n}}(\lambda)=\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}\\}$
is nonempty, otherwise $\lambda_{f,P_{n}}^{-}:=0$.

###### Proof.

If $\epsilon_{\mathcal{B}}\geq\dfrac{M}{\lambda_{f,P_{n}}^{+}}$, by
Proposition 1,
$R_{\epsilon_{\mathcal{B}},1}(P_{n},f)=\bar{\lambda}\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\bar{\lambda},f}(Z)]$
, we have

$\bar{\lambda}\epsilon_{\mathcal{B}}\leq
R_{\epsilon_{\mathcal{B}},1}(P_{n},f).$

Since $f(z)\leq M$ for any $z$, we get
$R_{\epsilon_{\mathcal{B}},1}(P_{n},f)\leq M$. So
$\bar{\lambda}\leq\dfrac{M}{\epsilon_{\mathcal{B}}}.$

For the other side, we first show that $\psi_{f,P_{n}}(\lambda)$ is continuous
and monotonically non-increasing. The monotonicity is easy to verify from the
definition. For continuity, for any $\lambda_{2}>\lambda_{1}$, suppose that

$\begin{array}[]{l}\hat{z}=\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda_{1}d_{\mathcal{Z}}(z,z^{\prime})-f(z)\\}),\\\
z^{*}=\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda_{2}d_{\mathcal{Z}}(z,z^{\prime})-f(z)\\}).\end{array}$

Then we have

$\begin{array}[]{l}\psi_{f,P_{n}}(\lambda_{1})-\psi_{f,P_{n}}(\lambda_{2})\\\
=\mathbb{E}_{P_{n}}(\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda_{1}d_{\mathcal{Z}}(z,z^{\prime})-f(z)\\}-\\\
\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda_{2}d_{\mathcal{Z}}(z,z^{\prime})-f(z)\\})\\\
\leq\mathbb{E}_{p_{n}}\left((\lambda_{2}-\lambda_{1})d_{\mathcal{Z}}(z,\hat{z})\right)\leq(\lambda_{2}-\lambda_{1})diam(\mathcal{Z})\\\
\end{array}.$

So $\psi_{f,P_{n}}(\lambda)$ is $diam(\mathcal{Z})$-Lipschitz and thus
continuous.

Now we prove $\bar{\lambda}\in[\lambda_{f,P_{n}}^{-},\lambda_{f,P_{n}}^{+}]$.
If $\lambda>\lambda_{f,P_{n}}^{+}$, by the monotonicity and nonnegativity of
$\psi_{f,P_{n}}(\lambda)$, we have
$\psi_{f,P_{n}}(\lambda)=\psi_{f,P_{n}}(\lambda_{f,P_{n}}^{+})=0$, which
implies
$\lambda\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\lambda,f}(z)]\geq\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\lambda_{f,P_{n}}^{+},f}(z)]$.
Therefore the optimal $\bar{\lambda}\leq\lambda_{f,P_{n}}^{+}$. To show
$\bar{\lambda}\geq\lambda_{f,P_{n}}^{-}$, first notice that
$\psi_{f,P_{n}}(\lambda)$ belongs to $[0,M]$ for any $\lambda$. We define

$\lambda_{f,P_{n}}^{-}:=\sup\\{\lambda:\psi_{f,P_{n}}(\lambda)=\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}\\}.$

Note that this set
$\\{\lambda:\psi_{f,P_{n}}(\lambda)=\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}\\}$
might be empty if
$\psi_{f,P_{n}}(0)<\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}<M$. In
this case, we just let $\lambda_{f,P_{n}}^{-}=0$, and $\bar{\lambda}$ must
belong to $[0,\lambda_{f,P_{n}}^{+}]$. Otherwise, there must exist some
$\lambda\in[0,\lambda_{f,P_{n}}^{+}]$ which satisfies
$\psi_{f,P_{n}}(\lambda)=\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}$ by
the intermediate value theorem of a continuous function. We choose
$\lambda_{f,P_{n}}^{-}$ to be the maximal one in that set. Then, for any
$\lambda<\lambda_{f,P_{n}}^{-}$, since $\psi_{f,P_{n}}(\lambda)$ is
monotonically non-increasing, we have

$\mathbb{E}_{P_{n}}(\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda
d_{\mathcal{Z}}(z,z^{\prime})-f(z)\\})\geq\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}.$

By rearranging the items on both sides, we obtain

$\lambda\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\lambda,f}(z)]\geq\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}(f(z))$

for any $\lambda<\lambda_{f,P_{n}}^{-}$. Therefore,
$\bar{\lambda}\geq\lambda_{f,P_{n}}^{-}$, and we complete the proof. ∎

Remark 1. We can show $\lim_{\epsilon_{\mathcal{B}}\rightarrow
0}\lambda_{f,P_{n}}^{-}=\lambda_{f,P_{n}}^{+}$ by using $(\epsilon,\delta)$
language as follows. $\forall\epsilon$, define
$\delta=\frac{\psi_{f,P_{n}}(\lambda_{f,P_{n}}^{+}-\epsilon)}{\lambda_{f,P_{n}}^{+}}$.
Then, for any $\epsilon_{\mathcal{B}}<\delta$, we have
$\psi_{f,P_{n}}(\lambda_{f,P_{n}}^{+}-\epsilon)>\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}$.
By the definition of $\lambda_{f,P_{n}}^{-}$,
$\psi_{f,P_{n}}(\lambda_{f,P_{n}}^{-})=\lambda_{f,P_{n}}^{+}\cdot\epsilon_{\mathcal{B}}$.
Since $\psi_{f,P_{n}}(\lambda)$ is monotonically non-increasing, we have
$\lambda_{f,P_{n}}^{-}>\lambda_{f,P_{n}}^{+}-\epsilon$. Therefore,
$\lim_{\epsilon_{\mathcal{B}}\rightarrow
0}\lambda_{f,P_{n}}^{-}=\lambda_{f,P_{n}}^{+}$.

######  Lemma 5.

Define the function class
$\Phi:=\\{\varphi_{\lambda,f}:\lambda\in[a,b],f\in\mathcal{F}\\}$ where $b\geq
a\geq 0$. Then, the expected Rademacher complexity of the function class
$\Phi$ satisfies

$\begin{array}[]{lr}\mathfrak{R}_{n}(\Phi)\leq&\dfrac{12\mathfrak{C}(\mathcal{F})}{\sqrt{n}}+\dfrac{6\sqrt{\pi}}{\sqrt{n}}(b-a)\cdot
diam(Z),\end{array}$

where
$\mathfrak{C}(\mathcal{F}):=\int_{0}^{\infty}\sqrt{log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du$
and $\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)$ denotes the covering
number of $\mathcal{F}$.

The proof of this lemma is contained in Appendix B.

The following theorem gives the generalization bound for the local worst-case
risk. We first introduce the corresponding notation:
$\bar{\lambda}\in[\zeta^{-}_{f,P_{n}},\zeta^{+}_{f,P_{n}}]$ denotes expression
(4.2),
$[\zeta^{-},\zeta^{+}]:=\bigcup_{f,P_{n}}[\zeta^{-}_{f,P_{n}},\zeta^{+}_{f,P_{n}}]$
and $\Lambda_{\epsilon_{\mathcal{B}}}:=\zeta^{+}-\zeta^{-}$. It is
straightforward to check that
$[\zeta^{-},\zeta^{+}]\subset[0,M/\epsilon_{\mathcal{B}}]$ from expression
(4.2).

######  Theorem 1.

If the assumptions 1\- 3 hold, then for any $f\in\mathcal{F}$, we have

$\begin{array}[]{l}R_{\epsilon_{\mathcal{B}},1}(P,f)-R_{\epsilon_{\mathcal{B}},1}(P_{n},f)\leq\dfrac{24\mathfrak{C}(\mathcal{F})}{\sqrt{n}}+M\sqrt{\dfrac{log(\frac{1}{\delta})}{2n}}+\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \
\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot
diam(Z)\end{array}$

with probability at least $1-\delta$.

###### Proof.

For any $f\in\mathcal{F}$, define

$\bar{\lambda}:=\arg{\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\lambda,f}(Z)]\\}}.$

Then using Proposition 1, we can write

$\begin{array}[]{l}R_{\epsilon_{\mathcal{B}},1}(P,f)-R_{\epsilon_{\mathcal{B}},1}(P_{n},f)\\\
=\min_{\lambda\geq
0}\left\\{\lambda\epsilon_{\mathcal{B}}+\displaystyle\int_{\mathcal{Z}}\varphi_{\lambda,f}(z)P(dz)\right\\}-\bigg{(}\bar{\lambda}\epsilon_{\mathcal{B}}+\\\
\left.\displaystyle\int_{\mathcal{Z}}\varphi_{\bar{\lambda},f}(z)P_{n}(dz)\right)\leq\displaystyle\int_{\mathcal{Z}}\varphi_{\bar{\lambda},f}(z)(P-P_{n})(dz).\end{array}$

By lemma 4, we have
$\bar{\lambda}\in[\zeta^{-}_{f,P_{n}},\zeta^{+}_{f,P_{n}}]$. Define the
function class
$\Phi:=\\{\varphi_{\lambda,f}:\lambda\in[\zeta^{-},\zeta^{+}],f\in\mathcal{F}\\}$.
Then, we have

$R_{\epsilon_{\mathcal{B}},1}(P,f)-R_{\epsilon_{\mathcal{B}},1}(P_{n},f)\leq\sup_{\varphi\in\Phi}\left[\int_{\mathcal{Z}}\varphi(z)(P-P_{n})(dz)\right].$

Since all $f\in\mathcal{F}$ takes values in $[0,M]$, the same holds for all
$\varphi\in\Phi$. Therefore, by a standard symmetrization argument [35],

$R_{\epsilon_{\mathcal{B}},1}(P,f)-R_{\epsilon_{\mathcal{B}},1}(P_{n},f)\leq
2\mathfrak{R}_{n}(\Phi)+M\sqrt{\dfrac{log(1/\delta)}{2n}}$

with probability at least $1-\delta$, where
$\mathfrak{R}_{n}(\Phi):=\mathbb{E}[\sup_{\varphi\in\Phi}\dfrac{1}{n}\sum_{i=1}^{n}\sigma_{i}\varphi(z_{i})]$
is the expected Rademacher complexity of $\Phi$. Using the bound of lemma 4,
we get the following result

$\begin{array}[]{l}R_{\epsilon_{\mathcal{B}},1}(P,f)-R_{\epsilon_{\mathcal{B}},1}(P_{n},f)\leq\dfrac{24\mathfrak{C}(\mathcal{F})}{\sqrt{n}}+M\sqrt{\dfrac{log(\frac{1}{\delta})}{2n}}+\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \
\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot diam(Z)\\\
\end{array}.$

∎

Remark 2. Lee and Raginsky, [30] prove a bound with
$[\zeta^{-},\zeta^{+}]=[0,L]$ under the Lipschitz assumption with $L$
representing the Lipschitz constant. Our result improves a lot on theirs.
First, our Assumption 3 is weaker than the Lipschitz assumption in Lee and
Raginsky, [30]. Second, even under our weaker assumptions, our bound is still
better than that of Lee and Raginsky, [30] for the case
$\epsilon_{\mathcal{B}}\geq M/L$ since
$[\zeta^{-},\zeta^{+}]\subset[0,M/\epsilon_{\mathcal{B}}]\subset[0,L]$. Third,
if further assuming the same Lipschitz condition as Lee and Raginsky, [30], we
can get $[\zeta^{-},\zeta^{+}]\subset[0,L]$ by the definition of $\zeta^{-}$
and $\zeta^{+}$, which is always better than the ones in Lee and Raginsky,
[30]. Finally, the term
$\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot diam(Z)$
in our bound will vanish as $\epsilon_{\mathcal{B}}\rightarrow\infty$ or
$\epsilon_{\mathcal{B}}=0$ whereas Lee and Raginsky, [30] give a
$\epsilon_{\mathcal{B}}$-free bound with $\Lambda_{\epsilon_{\mathcal{B}}}$
always being a constant $L$.

This leads to the following upper bound on the adversarial expected risk.

######  Corollary 1.

With the conditions in Theorem 1, for any $f\in\mathcal{F}$, we have

$\begin{array}[]{l}R_{P}(f,\mathcal{B})\leq\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\displaystyle\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\psi_{f,P_{n}}(\lambda)\\}+\\\ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \
\dfrac{24\mathfrak{C}(\mathcal{F})}{\sqrt{n}}+\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}diam(Z)+M\sqrt{\dfrac{log(\frac{1}{\delta})}{2n}}\\\
\end{array}$ (4.3)

and

$\begin{array}[]{l}R_{P}(f,\mathcal{B})\leq\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\dfrac{24\mathfrak{C}(\mathcal{F})}{\sqrt{n}}+\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot
diam(Z)+M\sqrt{\dfrac{log(\frac{1}{\delta})}{2n}}\\\ \end{array}$ (4.4)

with probability at least $1-\delta$.

###### Proof.

By Proposition 1, $R_{\epsilon_{\mathcal{B}},1}(P_{n},f)$ can be written as

$\begin{array}[]{l}R_{\epsilon_{\mathcal{B}},1}(P_{n},f)\\\
=\displaystyle\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\lambda,f}(z)]\\}\\\
=\displaystyle\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\mathbb{E}_{P_{n}}[\varphi_{\lambda,f}(z)-f(z)]\\}+\mathbb{E}_{P_{n}}[f(z)]\\\
=\displaystyle\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\psi_{f,P_{n}}(\lambda)\\}+\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})\end{array},$

where the last equality uses the definition of $\psi_{f,P_{n}}(\lambda)$.
Substituting the above equation into Theorem 1, we get result (4.3). To obtain
(4.4), we can make use of the following inequality

$\begin{array}[]{rl}\displaystyle\min_{\lambda\geq
0}\\{\lambda\epsilon_{\mathcal{B}}+\psi_{f,P_{n}}(\lambda)\\}&\leq\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\psi_{f,P_{n}}(\lambda_{f,P_{n}}^{+})\\\
&=\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}\\\ \end{array},$

where the equality follows from the definition of $\lambda_{f,P_{n}}^{+}$. ∎

Remark 3. We are interested in how the adversarial risk bounds differ from the
case in which the adversary is absent. Plugging $\epsilon_{\mathcal{B}}=0$
into inequality (4.4) yields the usual generalization of the form

$\begin{array}[]{l}R_{P}(h)\leq\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\dfrac{24\mathfrak{C}(\mathcal{F})}{\sqrt{n}}+M\sqrt{\dfrac{log(1/\delta)}{2n}}.\end{array}$

So the effect of an adversary is to introduce an extra complexity term
$12\sqrt{\pi}\Lambda_{\epsilon_{\mathcal{B}}}\cdot diam(Z)/{\sqrt{n}}$ and an
additional linear term on $\epsilon_{\mathcal{B}}$ which contributes to the
empirical risk.

Remark 4. As mentioned in Remark 2, the extra complexity term will decrease as
$\epsilon_{\mathcal{B}}$ gets bigger if $\epsilon_{\mathcal{B}}\geq
M/\lambda_{f,P_{n}}^{+}$ , indicating that a stronger adversary might have a
negative impact on the hypothesis class complexity. This is intuitive, since
different hypotheses might have the same performance in the presence of a
strong adversary and, therefore, the hypothesis class complexity will
decrease. We emphasize that this phenomenon does not occur in our concurrent
work Khim and Loh, 2018a [26] and Yin et al., [52]. In both of their work,
this term will increase linearly as $\epsilon_{\mathcal{B}}$ grows.

Remark 5. We should point out that $\lambda_{f,P_{n}}^{+}$ is data-dependent
and might be difficult to compute exactly. Luckily we can upper bound it
easily. For example, if $f$ is $L$-Lipschitz, by the definition of
$\lambda_{f,P_{n}}^{+}$, we have $\lambda_{f,P_{n}}^{+}\leq L$. See Section 5
for more examples. In particular, if $\psi_{f,P_{n}}(\lambda)\equiv 0$ for any
$\lambda\geq 0$, we get $\lambda_{f,P_{n}}^{+}=0$, and the additional term
$\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}$ in (4.4) will disappear.

##  5 Example Bounds

In this section, we illustrate the application of Corollary 1 to several
commonly-used models: SVMs, neural networks, and PCA.

###  5.1 Support Vector Machines

We first start with SVMs. Let $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$,
where the feature space $\mathcal{X}=\\{x\in\mathbb{R}^{d}:||x||_{2}\leq r\\}$
and the label space $\mathcal{Y}=\\{-1,+1\\}$. Equip $\mathcal{Z}$ with the
Euclidean metric

$d_{\mathcal{Z}}(z,z^{\prime})=d_{\mathcal{Z}}((x,y),(x^{\prime},y^{\prime}))=||x-x^{\prime}||_{2}+\mathbbm{1}_{(y\neq
y^{\prime})}.$

Consider the hypothesis space
$\mathcal{F}=\\{(x,y)\rightarrow\max\\{0,1-yh(x)\\}:h\in H\\}$, where
$H=\\{x\rightarrow w\cdot x:||w||_{2}\leq\Lambda\\}$. We can now derive the
expected risk bound for SVMs in the presence of an adversary.

######  Corollary 2.

For the SVM setting considered above, for any $f\in\mathcal{F}$, with
probability at least $1-\delta$,

$\begin{array}[]{l}R_{P}(f,\mathcal{B})\leq\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\dfrac{144}{\sqrt{n}}\Lambda
r\sqrt{d}+\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot(2r+1)+(1+\Lambda
r)\sqrt{\dfrac{log(\frac{1}{\delta})}{2n}},\end{array}$

where $\lambda_{f,P_{n}}^{+}\leq\displaystyle\max_{i}\\{2y_{i}w\cdot
x_{i},||w||_{2}\\}$.

The proof of Corollary 2 can be found in Appendix C.

Our result can easily be extended to kernel SVM. Here, we take a Gaussian
kernel as an example. Let
$K:\mathcal{X}\times\mathcal{X}\rightarrow\mathbb{R}$ be a Gaussian kernel
with $K(x_{1},x_{2})=\exp(-||x_{1}-x_{2}||^{2}_{2}/\sigma^{2})$. Let
$\tau:\mathcal{X}\rightarrow\mathbb{H}$ be a feature mapping associated with
$K$ and $H=\\{x\rightarrow\langle
w,\tau(x)\rangle:||w||_{\mathbb{H}}\leq\Lambda\\}$, where
$\langle\cdot,\cdot\rangle$ is the inner product in the reproducing kernel
Hilbert space $\mathbb{H}$ and $||\cdot||_{H}$ is the induced norm. Suppose
$\mathcal{X}\subseteq\mathbb{R}^{d}$ is compact and the space $\mathcal{Z}$ is
equipped with the metric

$d_{\mathcal{Z}}(z,z^{\prime})=||\tau(x)-\tau(x^{\prime})||_{\mathbb{H}}+\mathbbm{1}_{(y\neq
y^{\prime})}$

for $z=(x,y)$ and $z^{\prime}=(x^{\prime},y^{\prime})$. It is easy to show
that $d_{\mathcal{X}}=||\tau(x)-\tau(x^{\prime})||_{\mathbb{H}}$ is
translation invariant from Gaussian kernel definition. To apply Corollary 1,
we must calculate the covering numbers
$\mathcal{N}(\mathcal{F},||\cdot||_{\infty},\cdot)$. To this end, we embed $H$
into the space $\mathcal{C}(\mathcal{X})$ of continuous real-valued functions
on $\mathcal{X}$ denoted by $I_{K}(H)$ equipped with the sup norm
$||h||_{\mathcal{X}}:=\sup_{x\in\mathcal{X}}|h(x)|$.

We can now derive the adversarial risk bounds for the Gaussian-kernel SVM.

######  Corollary 3.

For the Gaussian-kernel SVM described above, for any $f\in\mathcal{F}$, with
probability at least $1-\delta$,

$\begin{array}[]{rl}R_{P}(f,\mathcal{B})\leq&\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\dfrac{24}{\sqrt{n}}\Lambda\sqrt{d}C_{3}+\\\
&\dfrac{30\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}+\left(1+\Lambda\right)\sqrt{\dfrac{log(1/\delta)}{2n}},\end{array}$

where $\lambda_{f,P_{n}}^{+}\leq\displaystyle\max_{i}\\{2y_{i}\langle
w,\tau(x_{i})\rangle,||w||_{\mathbb{H}}\\}\leq 2||w||_{\mathbb{H}}$,
$C_{3}=(32+\dfrac{1280d}{\sigma^{2}})^{\frac{d+1}{2}}(2\Gamma(\frac{d+3}{2},\\\
\log 2)+(\log 2)^{\frac{d+1}{2}})$, and
$\Gamma(s,v):=\int_{v}^{\infty}u^{s-1}e^{-u}du$ is the incomplete gamma
function.

The proof of Corollary 3 can be found in Appendix C.

Remark 6. A margin bound for SVM in the multi-class setting can be derived in
similar way. So we omit the proof.

###  5.2 Neural Networks

We next consider feed-forward neural networks. To demonstrate the generality
of our method, we consider a multi-class prediction problem. We first define
some notations. Let $\mathcal{Z}=\mathcal{X}\times\mathcal{Y}$, where the
feature space $\mathcal{X}=\\{x\in\mathbb{R}^{d}:||x||_{2}\leq B\\}$ and the
label space $\mathcal{Y}=\\{1,2,\cdots,k\\}$; $k$ represents the number of
classes. The network uses $L$ fixed nonlinear activation functions
$(\sigma_{1},\sigma_{2},\cdots,\sigma_{L})$, where $\sigma_{i}$ is
$\rho_{i}$-Lipschitz and satisfies $\sigma_{i}(0)=0$. Given $L$ weight
matrices $\mathcal{A}=(A_{1},A_{2},\cdots,A_{L})$, the network computes the
following function

$\mathcal{H}_{\mathcal{A}}(x):=\sigma_{L}(A_{L}\sigma_{L-1}(A_{L-1}\sigma_{L-2}(\cdots\sigma_{2}(A_{2}\sigma_{1}(A_{1}x)\cdot)),$

where $A_{i}\in\mathbb{R}^{d_{i}\times d_{i-1}}$ and
$\mathcal{H}_{\mathcal{A}}:\mathbb{R}^{d}\rightarrow\mathbb{R}^{k}$ with
$d_{0}=d$ and $d_{L}=k$. Let $W=\max\\{d_{0},d_{1},\cdots,d_{L}\\}$. Define a
margin operator
$\mathcal{M}:\mathbb{R}^{k}\times\\{1,2,\cdots,k\\}\rightarrow\mathbb{R}$ as
$\mathcal{M}(v,y):=v_{y}-\max_{j\neq y}v_{j}$ and the ramp loss
$l_{\gamma}:\mathbb{R}\rightarrow\mathbb{R}^{+}$ as

$l_{\gamma}:=\left\\{\begin{array}[]{ll}0&r<-\gamma\\\
1+r/\gamma&r\in[-\gamma,0]\\\ 1&r>0\end{array}\right..$

Consider the hypothesis class $\mathcal{F}=\\{(x,y)\rightarrow
l_{\gamma}(-\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y)):\mathcal{A}=(A_{1},A_{2},\cdots,A_{L}),||A_{i}||_{\sigma}\leq
s_{i},||A_{i}||_{F}\leq b_{i}\\}$, where $||\cdot||_{\sigma}$ represents
spectral norm and $||\cdot||_{F}$ denotes the Frobenius norm. The metric in
space $\mathcal{Z}$ is defined as

$d_{\mathcal{Z}}(z,z^{\prime})=d_{\mathcal{Z}}((x,y),(x^{\prime},y^{\prime}))=||x-x^{\prime}||_{2}+\mathbbm{1}_{(y\neq
y^{\prime})}.$

Now we derive the adversarial expected risk for neural networks.

######  Corollary 4.

For the neural network setting defined above, for any $f\in\mathcal{F}$, with
probability of $1-\delta$, the following inequality holds

$\begin{array}[]{l}R_{P}(f,\mathcal{B})\leq\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\sqrt{\dfrac{log(1/\delta)}{2n}}+\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\dfrac{288}{\gamma\sqrt{n}}\prod_{i=1}^{L}\rho_{i}s_{i}BW\left(\sum_{i=1}^{L}\left(\dfrac{b_{i}}{s_{i}}\right)^{1/2}\right)^{2}+\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot(2B+1)\end{array},$

where
$\lambda_{f,P_{n}}^{+}\leq\displaystyle\max_{j}\bigg{\\{}\dfrac{2}{\gamma}\prod_{i=1}^{L}\rho_{i}||A_{i}||_{\sigma},\dfrac{1}{\gamma}\big{(}\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x_{j}),y_{j})+\max{\mathcal{H}_{\mathcal{A}}(x_{j})}-\min{\mathcal{H}_{\mathcal{A}}(x_{j})}\big{)}\bigg{\\}}$.

The proof of this Corollary is provided in Appendix D.

Remark 7. Setting $\epsilon_{\mathcal{B}}=0$, we can obtain a risk bound for
neural networks in terms of the spectral norm and the Frobenius norm of the
weight matrices; see (5.1). Although the result (5.1) is similar to the
results in Bartlett et al., [6] and Neyshabur et al., [36], the proof
technique is different. We hope that our approach provides a different
perspective on the generalization analysis of deep neural networks.

$\begin{array}[]{rl}R_{P}(f)\leq&\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\sqrt{\dfrac{log(1/\delta)}{2n}}+\\\
&\dfrac{288}{\gamma\sqrt{n}}\prod_{i=1}^{L}\rho_{i}s_{i}BW\left(\sum_{i=1}^{L}\left(\dfrac{b_{i}}{s_{i}}\right)^{1/2}\right)^{2}.\\\
\end{array}$ (5.1)

###  5.3 Principal Component Analysis

Until now we consider the adversarial learning problem in a supervised
learning setting. In this example, we show that our approach could be easily
extended to unsupervised learning setting, namely the principal component
analysis. We formalize PCA as follows. Fix $k\in[1,m]$ and let
$\mathcal{Z}\subset\mathbb{R}^{m}$ such that
$\max_{z\in\mathcal{Z}}||z||_{2}\leq B$. Define $\mathcal{T}^{k}$ as the set
of $m$-dimensional rank-$k$ orthogonal projection matrices. PCA consists of
projecting the $m$-dimensional input data onto a $k$-dimensional linear
subspace which minimizes reconstruction error, and the hypothesis space for
PCA is defined as
$\mathcal{F}=\\{z\rightarrow||Tz-z||_{2}^{2}:T\in\mathcal{T}^{k}\\}$. Note
that the definition for adversarial expected and empirical risk in supervised
learning setting given in Section 3 applies automatically to PCA, and the
adversarial expected risk bound for PCA is given as follows.

######  Corollary 5.

For PCA we define above, for any $f\in\mathcal{F}$, with probability of
$1-\delta$, the following inequality holds

$\begin{array}[]{rl}R_{P}(f,\mathcal{B})\leq&\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\dfrac{576B^{2}k\sqrt{m}}{\sqrt{n}}+\\\
&\dfrac{24B\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}+B^{2}\sqrt{\dfrac{log(1/\delta)}{2n}}\end{array},$

where
$\lambda_{f,P_{n}}^{+}\leq\displaystyle\max_{i}\\{B+||Tz_{i}-z_{i}||_{2}\\}$.

The proof of this Corollary can be founded in Appendix E.

Remark 8. For each example in this Section, we provide a data-dependent upper
bound for $\lambda_{f,P_{n}}^{+}$. This upper bound can be used for optimizing
the adversarial risk bounds, as discussed in Section 6.

##  6 Conclusions

In this paper, we propose a theoretical method for deriving adversarial risk
bounds. While our method is general and can easily be applied to multi-class
problems and most of the commonly used loss functions, the bound might be
loose in some cases. This is mainly because we always consider the worst case
so that we avoid the problem of solving the transport map. However, for some
simple problems, deriving the transport map directly might provide a better
bound. The other reason is that we use covering numbers instead of the
expected Rademacher complexity as our upper bounds, weakening our results. It
can be seen that we have an unavoidable dimension dependency. We speculate
that this dependency might be avoided by replacing the covering numbers in our
bounds with the Rademacher complexity of the hypothesis class, which we will
address in future studies.

In the future, one interesting problem is to develop adversarial robust
algorithms based on our results. For example, our bounds suggest that
minimizing the sum of empirical risk and the term
$\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}$ can help achieve adversarial
robustness. However, in practice, $\lambda_{f,P_{n}}^{+}$ is usually unknown,
and we only have an upper bound for $\lambda_{f,P_{n}}^{+}$. Thus, we can
perform a grid search of a regularization parameter $\eta$ on the interval
$[0,1]$ and replace $\lambda_{f,P_{n}}^{+}$ with its’s upper bound multiplied
by $\eta$ in the objective function. Then we minimize this new objective
function for each possible regularization parameter and at the end pick the
solution with the minimum value of the new objective function.

## References

  * Alabdulmohsin, [2015] Alabdulmohsin, I. M. (2015).  Algorithmic stability and uniform generalization.  In Advances in Neural Information Processing Systems, pages 19–27.
  * Ambroladze et al., [2007] Ambroladze, A., Parrado-Hernández, E., and Shawe-taylor, J. S. (2007).  Tighter pac-bayes bounds.  In Advances in neural information processing systems, pages 9–16.
  * Arora et al., [2018] Arora, S., Ge, R., Neyshabur, B., and Zhang, Y. (2018).  Stronger generalization bounds for deep nets via a compression approach.  arXiv preprint arXiv:1802.05296.
  * Athalye et al., [2018] Athalye, A., Carlini, N., and Wagner, D. (2018).  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  arXiv preprint arXiv:1802.00420.
  * Bartlett et al., [2005] Bartlett, P. L., Bousquet, O., Mendelson, S., et al. (2005).  Local rademacher complexities.  The Annals of Statistics, 33(4):1497–1537.
  * Bartlett et al., [2017] Bartlett, P. L., Foster, D. J., and Telgarsky, M. J. (2017).  Spectrally-normalized margin bounds for neural networks.  In Advances in Neural Information Processing Systems, pages 6240–6249.
  * Bartlett and Mendelson, [2002] Bartlett, P. L. and Mendelson, S. (2002).  Rademacher and gaussian complexities: Risk bounds and structural results.  Journal of Machine Learning Research, 3(Nov):463–482.
  * Biggio et al., [2013] Biggio, B., Corona, I., Maiorca, D., Nelson, B., Šrndić, N., Laskov, P., Giacinto, G., and Roli, F. (2013).  Evasion attacks against machine learning at test time.  In Joint European conference on machine learning and knowledge discovery in databases, pages 387–402. Springer.
  * Biggio et al., [2012] Biggio, B., Nelson, B., and Laskov, P. (2012).  Poisoning attacks against support vector machines.  arXiv preprint arXiv:1206.6389.
  * Biggio and Roli, [2018] Biggio, B. and Roli, F. (2018).  Wild patterns: Ten years after the rise of adversarial machine learning.  Pattern Recognition, 84:317–331.
  * Bousquet and Elisseeff, [2002] Bousquet, O. and Elisseeff, A. (2002).  Stability and generalization.  Journal of machine learning research, 2(Mar):499–526.
  * Courty et al., [2017] Courty, N., Flamary, R., Tuia, D., and Rakotomamonjy, A. (2017).  Optimal transport for domain adaptation.  IEEE transactions on pattern analysis and machine intelligence, 39(9):1853–1865.
  * Cucker and Zhou, [2007] Cucker, F. and Zhou, D. X. (2007).  Learning theory: an approximation theory viewpoint, volume 24.  Cambridge University Press.
  * Cullina et al., [2018] Cullina, D., Bhagoji, A. N., and Mittal, P. (2018).  Pac-learning in the presence of adversaries.  In Advances in Neural Information Processing Systems, pages 228–239.
  * Dalvi et al., [2004] Dalvi, N., Domingos, P., Sanghai, S., Verma, D., et al. (2004).  Adversarial classification.  In Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, pages 99–108. ACM.
  * Dekel et al., [2010] Dekel, O., Shamir, O., and Xiao, L. (2010).  Learning to classify with missing and corrupted features.  Machine learning, 81(2):149–178.
  * Farnia and Tse, [2016] Farnia, F. and Tse, D. (2016).  A minimax approach to supervised learning.  In Advances in Neural Information Processing Systems, pages 4240–4248.
  * Fawzi et al., [2016] Fawzi, A., Moosavi-Dezfooli, S.-M., and Frossard, P. (2016).  Robustness of classifiers: from adversarial to random noise.  In Advances in Neural Information Processing Systems, pages 1632–1640.
  * Gao and Kleywegt, [2016] Gao, R. and Kleywegt, A. J. (2016).  Distributionally robust stochastic optimization with wasserstein distance.  arXiv preprint arXiv:1604.02199.
  * Gilmer et al., [2018] Gilmer, J., Metz, L., Faghri, F., Schoenholz, S. S., Raghu, M., Wattenberg, M., and Goodfellow, I. (2018).  Adversarial spheres.  arXiv preprint arXiv:1801.02774.
  * Globerson and Roweis, [2006] Globerson, A. and Roweis, S. (2006).  Nightmare at test time: robust learning by feature deletion.  In Proceedings of the 23rd international conference on Machine learning, pages 353–360. ACM.
  * Goodfellow et al., [2014] Goodfellow, I. J., Shlens, J., and Szegedy, C. (2014).  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:1412.6572.
  * Gu and Rigazio, [2014] Gu, S. and Rigazio, L. (2014).  Towards deep neural network architectures robust to adversarial examples.  arXiv preprint arXiv:1412.5068.
  * Hein and Andriushchenko, [2017] Hein, M. and Andriushchenko, M. (2017).  Formal guarantees on the robustness of a classifier against adversarial manipulation.  In Advances in Neural Information Processing Systems, pages 2266–2276.
  * Herbrich and Williamson, [2002] Herbrich, R. and Williamson, R. C. (2002).  Algorithmic luckiness.  Journal of Machine Learning Research, 3(Sep):175–212.
  * [26] Khim, J. and Loh, P.-L. (2018a).  Adversarial risk bounds for binary classification via function transformation.  arXiv preprint arXiv:1810.09519.
  * [27] Khim, J. and Loh, P.-L. (2018b).  Adversarial risk bounds via function transformation.  arXiv preprint arXiv:1810.09519v2.
  * Langford, [2005] Langford, J. (2005).  Tutorial on practical prediction theory for classification.  Journal of machine learning research, 6(Mar):273–306.
  * Lee and Raginsky, [2017] Lee, J. and Raginsky, M. (2017).  Minimax statistical learning and domain adaptation with wasserstein distances.  arXiv preprint arXiv:1705.07815.
  * Lee and Raginsky, [2018] Lee, J. and Raginsky, M. (2018).  Minimax statistical learning with wasserstein distances.  In Advances in Neural Information Processing Systems, pages 2692–2701.
  * Liu et al., [2017] Liu, T., Lugosi, G., Neu, G., and Tao, D. (2017).  Algorithmic stability and hypothesis complexity.  arXiv preprint arXiv:1702.08712.
  * [32] Lowd, D. and Meek, C. (2005a).  Adversarial learning.  In Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, pages 641–647. ACM.
  * [33] Lowd, D. and Meek, C. (2005b).  Good word attacks on statistical spam filters.  In CEAS, volume 2005.
  * Madry et al., [2018] Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A. (2018).  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations.
  * Mohri et al., [2012] Mohri, M., Rostamizadeh, A., and Talwalkar, A. (2012).  Foundations of machine learning.  MIT press.
  * Neyshabur et al., [2017] Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N. (2017).  A pac-bayesian approach to spectrally-normalized margin bounds for neural networks.  arXiv preprint arXiv:1707.09564.
  * Raghunathan et al., [2018] Raghunathan, A., Steinhardt, J., and Liang, P. (2018).  Certified defenses against adversarial examples.  arXiv preprint arXiv:1801.09344.
  * Russo and Zou, [2016] Russo, D. and Zou, J. (2016).  Controlling bias in adaptive data analysis using information theory.  In Gretton, A. and Robert, C. C., editors, Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 1232–1240, Cadiz, Spain. PMLR.
  * Schmidt et al., [2018] Schmidt, L., Santurkar, S., Tsipras, D., Talwar, K., and Mądry, A. (2018).  Adversarially robust generalization requires more data.  arXiv preprint arXiv:1804.11285.
  * Shalev-Shwartz et al., [2010] Shalev-Shwartz, S., Shamir, O., Srebro, N., and Sridharan, K. (2010).  Learnability, stability and uniform convergence.  Journal of Machine Learning Research, 11(Oct):2635–2670.
  * Sinha et al., [2018] Sinha, A., Namkoong, H., and Duchi, J. (2018).  Certifiable distributional robustness with principled adversarial training.  In International Conference on Learning Representations.
  * Suggala et al., [2018] Suggala, A. S., Prasad, A., Nagarajan, V., and Ravikumar, P. (2018).  On adversarial risk and training.  arXiv preprint arXiv:1806.02924.
  * Szegedy et al., [2013] Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R. (2013).  Intriguing properties of neural networks.  arXiv preprint arXiv:1312.6199.
  * Talagrand, [2014] Talagrand, M. (2014).  Upper and lower bounds for stochastic processes: modern methods and classical problems, volume 60.  Springer Science & Business Media.
  * Uesato et al., [2018] Uesato, J., O’Donoghue, B., Oord, A. v. d., and Kohli, P. (2018).  Adversarial risk and the dangers of evaluating against weak attacks.  arXiv preprint arXiv:1802.05666.
  * Vapnik, [2013] Vapnik, V. (2013).  The nature of statistical learning theory.  Springer science & business media.
  * Vapnik, [1999] Vapnik, V. N. (1999).  An overview of statistical learning theory.  IEEE transactions on neural networks, 10(5):988–999.
  * Wang et al., [2017] Wang, Y., Jha, S., and Chaudhuri, K. (2017).  Analyzing the robustness of nearest neighbors to adversarial examples.  arXiv preprint arXiv:1706.03922.
  * Wong and Kolter, [2018] Wong, E. and Kolter, Z. (2018).  Provable defenses against adversarial examples via the convex outer adversarial polytope.  In International Conference on Machine Learning, pages 5283–5292.
  * Xu and Raginsky, [2017] Xu, A. and Raginsky, M. (2017).  Information-theoretic analysis of generalization capability of learning algorithms.  In Advances in Neural Information Processing Systems, pages 2524–2533.
  * Xu and Mannor, [2012] Xu, H. and Mannor, S. (2012).  Robustness and generalization.  Machine learning, 86(3):391–423.
  * Yin et al., [2018] Yin, D., Ramchandran, K., and Bartlett, P. (2018).  Rademacher complexity for adversarially robust generalization.  arXiv preprint arXiv:1810.11914.
  * Zhang et al., [2018] Zhang, J., Liu, T., and Tao, D. (2018).  An Information-Theoretic View for Deep Learning.  ArXiv e-prints.
  * Zhang, [2002] Zhang, T. (2002).  Covering number bounds of certain regularized linear function classes.  Journal of Machine Learning Research, 2(Mar):527–550.
  * Zhou, [2002] Zhou, D.-X. (2002).  The covering number in learning theory.  Journal of Complexity, 18(3):739–767.

##  Appendix A Proof of Lemma 3

Proof of Lemma 3. We first prove $\implies$. For any $f\in\mathcal{F}$ and any
empirical distribution $z_{i}\sim P_{n}$, by Assumption 3, there exists a
constant $\lambda_{f,z_{i}}$ such that
$f(z^{\prime})-f(z_{i})\leq\lambda_{f,z_{i}}d_{\mathcal{Z}}(z_{i},z^{\prime})$
for any $z^{\prime}\in\mathcal{Z}$, which leads to
$\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda_{f,z_{i}}d_{\mathcal{Z}}(z_{i},z^{\prime})-f(z_{i})\\})=0$.
Let $\lambda^{*}=\max_{i}\\{\lambda_{z_{i},f}\\}$. Then, for any $z_{i}\sim
P_{n}$, we have
$\sup_{z^{\prime}\in\mathcal{Z}}\\{f(z^{\prime})-\lambda^{*}d_{\mathcal{Z}}(z_{i},z^{\prime})-f(z_{i})\\})=0$.
Therefore, $\psi_{f,P_{n}}(\lambda^{*})=0$ and the set
$\\{\lambda:\psi_{f,P_{n}}(\lambda)=0\\}$ is nonempty. $\Longleftarrow$ can be
directly derived from the definition.

##  Appendix B Proof of Lemma 5

Proof of Lemma 5. Define the $\Phi$-indexed process
$X=(X_{\varphi})_{\varphi\in\Phi}$ by

$X_{\varphi}:=\dfrac{1}{\sqrt{n}}\sum_{i=1}^{n}\sigma_{i}\varphi(z_{i}).$

Note that $\mathbb{E}[X_{\varphi}]=0$ for all $\varphi\in\Phi$. First we show
that X is a subgaussian process with respect to the pseudometric
$d_{\Phi}(\varphi,\varphi^{\prime})$, defined as

$d_{\Phi}(\varphi,\varphi^{\prime}):=||f-f^{\prime}||_{\infty}+(diam(Z))|\lambda-\lambda^{\prime}|$

for $\varphi=\varphi_{\lambda,f}$ and
$\varphi^{\prime}=\varphi_{\lambda^{\prime},f^{\prime}}$. From the definition
of $\varphi_{\lambda,f}$, it is easy to show that
$||\varphi-\varphi^{\prime}||_{\infty}\leq
d_{\Phi}(\varphi,\varphi^{\prime})$. Then for any $t\in\mathbb{R}$, we can get

$\begin{array}[]{l}\mathbb{E}\left[\exp(t(X_{\varphi}-X_{\varphi}^{\prime}))\right]\\\
=\mathbb{E}\left[\exp(\dfrac{t}{\sqrt{n}}\sum_{i=1}^{n}\sigma_{i}(\varphi(z_{i})-\varphi^{\prime}(z_{i})))\right]\\\
=\left(\mathbb{E}\left[\exp(\dfrac{t}{\sqrt{n}}\sigma_{1}(\varphi(z_{1})-\varphi^{\prime}(z_{1}))\right]\right)^{n}\\\
\leq\exp\left(\dfrac{t^{2}d^{2}_{\Phi}(\varphi,\varphi^{\prime})}{2}\right)\end{array},$

where the second equality is by the fact that $(\sigma_{i},z_{i})$ are i.i.d.,
and the final inequality uses Hoeffding’s lemma. Therefore, X is subgaussian
with respect to $d_{\Phi}$. And the expected Rademacher complexity
$\mathfrak{R}_{n}(\Phi)$ can be bounded by the Dudley entropy integral [44]:

$\mathfrak{R}_{n}(\Phi)\leq\dfrac{12}{\sqrt{n}}\int_{0}^{\infty}\sqrt{log\mathcal{N}(\Phi,d_{\Phi},u)}du,$

where $\mathcal{N}(\Phi,d_{\Phi},\cdot)$ represents the covering numbers of
$(\Phi,d_{\Phi})$. By the definition of $d_{\Phi}$, it follows that

$\mathcal{N}(\Phi,d_{\Phi},u)\leq\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)\cdot\mathcal{N}([a,b],|\cdot|,\frac{u}{2diam(Z)})$

and therefore

$\begin{array}[]{rl}\mathfrak{R}_{n}(\Phi)\leq&\dfrac{12}{\sqrt{n}}\left(\displaystyle\int_{0}^{\infty}\sqrt{log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du+\right.\\\
&\left.\displaystyle\int_{0}^{\infty}\sqrt{log\mathcal{N}([a,b],|\cdot|,u/(2diam(Z)))}du\right)\end{array}.$

The second integral term could be easily obtained as follows

$\begin{array}[]{l}\displaystyle\int_{0}^{\infty}\sqrt{log\mathcal{N}([a,b],|\cdot|,u/(2diam(Z)))}du\\\
\leq(b-a)\cdot diam(z)\displaystyle\int_{0}^{1}\sqrt{log\dfrac{1}{u}}du\\\
=\dfrac{\sqrt{\pi}}{2}(b-a)\cdot diam(z)\end{array}.$

Consequently,

$\begin{array}[]{rl}\mathfrak{R}_{n}(\Phi)\leq&\dfrac{12}{\sqrt{n}}\displaystyle\int_{0}^{\infty}\sqrt{log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du+\\\
&\dfrac{6\sqrt{\pi}}{\sqrt{n}}(b-a)\cdot diam(Z)\end{array}.$

##  Appendix C Proofs of Corollary 2 and Corollary 3

Proof of Corollary 2. We first verify the assumption conditions in Theorem 1.
Assumption 1 is evidently satisfied since $diam(\mathcal{Z})\leq(2r+1)$. For
each $f\in\mathcal{F}$, assumption 2 holds with $M=1+\Lambda r$. To verify
assumption 3, we can write

$\begin{array}[]{rl}f(z^{\prime})-f(z)&\leq\max\\{0,yw\cdot x-y^{\prime}w\cdot
x^{\prime}\\}\\\ &\leq\max\\{0,2yw\cdot x\mathbbm{1}_{(y\neq
y^{\prime})}+||w||_{2}||x^{\prime}-x||_{2}\\}\\\ &\leq\max\\{2yw\cdot
x,||w||_{2}\\}d_{\mathcal{Z}}(z,z^{\prime})\end{array}.$

So $\lambda_{f,P_{n}}^{+}\leq\displaystyle\max_{i}\\{2y_{i}w\cdot
x_{i},||w||_{2}\\}$ and assumption 3 holds.

To evaluate the Dudley entropy integral, we need to estimate the covering
numbers $\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)$. First observe, for
any $f_{1},f_{2}\in\mathcal{F}$, we have

$\begin{array}[]{l}||f_{1}-f_{2}||_{\infty}=\sup_{x\in\mathcal{X},y\in\mathcal{Y}}|f_{1}(x,y)-f_{2}(x,y)|\\\
\leq\sup_{x\in\mathcal{X},y\in\mathcal{Y}}|yw_{1}\cdot x-yw_{2}\cdot
x|\leq||w_{1}-w_{2}||_{2}r.\end{array}$

Since $w_{1},w_{2}$ belong to a $\Lambda$-ball in $\mathcal{R}^{d}$,

$\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)\leq\left(\dfrac{6\Lambda
r}{u}\right)^{d}$

for $0<u<2\Lambda r$, and $\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)=1$
for $u\geq 2\Lambda r$, which gives

$\begin{array}[]{l}\displaystyle\int_{0}^{\infty}\sqrt{log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du\\\
\leq\displaystyle\int_{0}^{2\Lambda r}\sqrt{d\log(\dfrac{6\Lambda
r}{u})}du\leq 6\Lambda r\sqrt{d}\end{array}.$

Substituting this into expression (4.4), we get the desired result

$\begin{array}[]{l}R_{P}(f,\mathcal{B})\leq\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\dfrac{144}{\sqrt{n}}\Lambda
r\sqrt{d}+\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot(2r+1)+(1+\Lambda
r)\sqrt{\dfrac{log(\frac{1}{\delta})}{2n}}\end{array}.$

To prove Corollary 3, we need the following Proposition [13].

######  Proposition 2.

For compact $\mathcal{X}\subseteq\mathbb{R}^{d}$,

$\begin{array}[]{l}\log\mathcal{N}(I_{K}(H),||\cdot||_{\mathcal{X}},u)\leq
dC_{2}\left(\log\dfrac{\Lambda}{u}\right)^{d+1}\end{array}$

holds for all $0<u\leq\Lambda/2$ where
$C_{2}=(32+\dfrac{640d(diam(\mathcal{X}))^{2}}{\sigma^{2}})^{d+1}$.

Proof of Corollary 3. First note that
$||\tau(x^{\prime})-\tau(x)||_{\mathbb{H}}^{2}=2-2K(x,x^{\prime})\leq 2$. So
assumption 1 holds with $diam(\mathcal{Z})\leq\dfrac{5}{2}$. For any
$f\in\mathcal{F}$, assumption 2 holds with $M=1+\Lambda$. For assumption 3, we
have

$\begin{array}[]{l}f(z^{\prime})-f(z)\\\ \leq\max\\{0,y\langle
w,\tau(x)\rangle-y^{\prime}\langle w,\tau(x^{\prime})\rangle\\}\\\
\leq\max\\{0,2y\langle w,\tau(x)\rangle\mathbbm{1}_{(y\neq
y^{\prime})}+|\langle w,\tau(x)-\tau(x^{\prime})\rangle\\}\\\
\leq\max\\{2y\langle
w,\tau(x)\rangle,||w||_{\mathbb{H}}\\}d_{\mathcal{Z}}(z,z^{\prime})\end{array}.$

So $\lambda_{f,P_{n}}^{+}\leq\displaystyle\max_{i}\\{2y_{i}\langle
w,\tau(x_{i})\rangle,||w||_{\mathbb{H}}\\}$.

Now we calculate the covering numbers
$\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)$. Observe that

$\begin{array}[]{l}||f_{1}-f_{2}||_{\infty}=\sup_{x\in\mathcal{X},y\in\mathcal{Y}}|f_{1}(x,y)-f_{2}(x,y)|\\\
\leq\sup_{x\in\mathcal{X}}|\langle w_{1},x\rangle-\langle
w_{2},x\rangle|=||w_{1}-w_{2}||_{\mathcal{X}}\end{array}.$

So

$\begin{array}[]{l}\displaystyle\int_{0}^{\infty}\sqrt{log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du\\\
\leq\displaystyle\int_{0}^{\infty}\sqrt{\log(\mathcal{N}(I_{K}(H),||\cdot||_{\mathcal{X}},\dfrac{u}{2})}du\\\
=\displaystyle\int_{0}^{2\Lambda}\sqrt{\log(\mathcal{N}(I_{K}(H),||\cdot||_{\mathcal{X}},\dfrac{u}{2})}du\\\
\leq\displaystyle\int_{0}^{\Lambda}\sqrt{\log(\mathcal{N}(I_{K}(H),||\cdot||_{\mathcal{X}},\dfrac{u}{2})}du+\\\
\ \ \ \
\displaystyle\int_{\Lambda}^{2\Lambda}\sqrt{\log(\mathcal{N}(I_{K}(H),||\cdot||_{\mathcal{X}},\dfrac{\Lambda}{2})}du\\\
\end{array},$

where the equality uses $||w||_{\mathcal{X}}\leq\Lambda$ and the final
inequality uses the monotonicity of covering numbers. Using the bound from
Proposition 2,

$\begin{array}[]{l}\displaystyle\int_{0}^{\Lambda}\sqrt{\log(\mathcal{N}(I_{K}(H),||\cdot||_{\mathcal{X}},\dfrac{u}{2})}du\\\
\leq\sqrt{d}\left(32+\dfrac{640d(diam(\mathcal{X}))^{2}}{\sigma^{2}}\right)^{\frac{d+1}{2}}\displaystyle\int_{0}^{\Lambda}(\log\dfrac{2\Lambda}{u})^{\frac{d+1}{2}}du\\\
=2\Lambda\sqrt{d}\left(32+\dfrac{640d(diam(\mathcal{X}))^{2}}{\sigma^{2}}\right)^{\frac{d+1}{2}}\Gamma(\frac{d+3}{2},\log
2)\\\ \end{array}.$

And

$\begin{array}[]{l}\displaystyle\int_{\Lambda}^{2\Lambda}\sqrt{\log(\mathcal{N}(I_{K}(H),||\cdot||_{\mathcal{X}},\dfrac{\Lambda}{2})}du\\\
=\Lambda\sqrt{d}\left(32+\dfrac{640d(diam(\mathcal{X}))^{2}}{\sigma^{2}}\right)^{\frac{d+1}{2}}(\log
2)^{\frac{d+1}{2}}.\end{array}$

Therefore, applying Corollary 1, we get

$\begin{array}[]{ll}R_{P}(f,\mathcal{B})\leq&\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\dfrac{24}{\sqrt{n}}\Lambda\sqrt{d}C_{3}+\\\
&\dfrac{30\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}+(1+\Lambda)\sqrt{\dfrac{log(1/\delta)}{2n}}\end{array}.$

##  Appendix D Proof of Corollary 4

The goal of this section is to prove the adversarial expected risk for neural
networks. To this end, it is necessary to first establish some properties of
the margin operator $\mathcal{M}(v,y)=v_{y}-\max_{j\neq y}v_{j}$ and the ramp
loss $l_{\gamma}$.

######  Lemma 1.

For every $j$, $\mathcal{M}(\cdot,j)$ is 2-Lipschitz with respect to
$||\cdot||_{2}$.

proof. Let $u,v$ and $y$ be given. If $\mathcal{M}(u,y)\geq\mathcal{M}(v,y)$,
denote the index $j$ which satisfies that $\mathcal{M}(v,y)=v_{y}-v_{j}$.
Then,

$\begin{array}[]{l}\mathcal{M}(u,y)-\mathcal{M}(v,y)=u_{y}-\max_{i\neq
y}u_{i}-v_{y}+v_{j}\\\ \leq u_{y}-u_{j}-v_{y}+v_{j}\leq 2||u-v||_{\infty}\leq
2||u-v||_{2}.\end{array}$

Otherwise, let $j$ be the index satisfying $\mathcal{M}(u,y)=u_{y}-u_{j}$, and
we obtain

$-2||u-v||_{2}\leq\mathcal{M}(u,y)-\mathcal{M}(v,y).$

Therefore, $\mathcal{M}(\cdot,j)$ is $2$-Lipschitz with respect to
$||\cdot||_{2}$.

######  Lemma 2.

For any $f\in\mathcal{F}$, we have $\lambda_{f,P_{n}}^{+}\leq C_{4}$ where
$C_{4}:=\max_{j}\\{\dfrac{2}{\gamma}\prod_{i=1}^{L}\rho_{i}||A_{i}||_{\sigma},\dfrac{1}{\gamma}\big{(}\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x_{j}),y_{j})+\max{\mathcal{H}_{\mathcal{A}}(x_{j})}-\min{\mathcal{H}_{\mathcal{A}}(x_{j})}\big{)}\\}$.

###### Proof.

By the definition of $f$, for any $z$ and $z^{\prime}$, we have

$\begin{array}[]{l}f(z^{\prime})-f(z)\\\
=l_{\gamma}(-\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x^{\prime}),y^{\prime}))-l_{\gamma}(-\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y))\\\
\leq\max\\{0,\dfrac{1}{\gamma}(\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y)-\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x^{\prime}),y^{\prime}))\\}\\\
\leq\max\\{0,\dfrac{1}{\gamma}(\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y^{\prime})-\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x^{\prime}),y^{\prime}))+\\\
\ \ \ \
\dfrac{1}{\gamma}(\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y)-\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y^{\prime}))\\}\\\
\leq\max\\{0,\dfrac{2}{\gamma}|\mathcal{H}_{\mathcal{A}}(x)-\mathcal{H}_{\mathcal{A}}(x^{\prime})|+\dfrac{1}{\gamma}(\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y)-\\\
\ \ \ \ \mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y^{\prime}))\\}\\\
\leq\dfrac{2}{\gamma}\prod_{i=1}^{L}\rho_{i}||A_{i}||_{\sigma}||x-x^{\prime}||_{2}+\dfrac{1}{\gamma}\big{(}\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y)+\\\
\ \ \ \ \
\max{\mathcal{H}_{\mathcal{A}}(x)}-\min{\mathcal{H}_{\mathcal{A}}(x)}\big{)}\mathbbm{1}_{y\neq
y^{\prime}}\\\ \leq C_{4}d_{\mathcal{Z}}(z,z^{\prime})\\\ \end{array}.$

where the third inequality uses Lemma C.1. Therefore,
$\lambda_{f,P_{n}}^{+}\leq C_{4}$. ∎

######  Lemma 3.

For any two feedforward neural network $\mathcal{H}_{\mathcal{A}}$ and
$\mathcal{H}_{\mathcal{A^{\prime}}}$ where
$\mathcal{A}=(A_{1},A_{2},\cdots,A_{L})$ and
$\mathcal{A^{\prime}}=(A_{1}^{\prime},A_{2}^{\prime},\cdots,A_{L}^{\prime})$,
we have the following

$||\mathcal{H}_{\mathcal{A}}(x)-\mathcal{H}_{\mathcal{A^{\prime}}}(x)||_{2}\leq\prod_{i=1}^{L}\rho_{i}s_{i}B\left(\sum_{j=1}^{L}\dfrac{||A_{i}-A_{i}^{\prime}||_{\sigma}}{s_{i}}\right).$

###### Proof.

We proof this by induction. Let
$\Delta_{i}=||\mathcal{H}^{i}_{\mathcal{A}}(x)-\mathcal{H}^{i}_{\mathcal{A^{\prime}}}(x)||_{2}$.
First observe

$\begin{array}[]{l}\Delta_{1}=||\sigma_{1}(A_{1}x)-\sigma_{1}(A_{1}^{\prime}x)||_{2}\leq\rho_{1}||A_{1}x-A_{1}^{\prime}x||_{2}\\\
\leq\rho_{1}||A_{1}-A_{1}^{\prime}||_{\sigma}||x||_{2}\leq\rho_{1}B||A_{1}-A_{1}^{\prime}||_{\sigma}.\end{array}$

For any $i\geq 1$, we have the following

$\begin{array}[]{l}\Delta_{i+1}\\\
=||\sigma_{i+1}(A_{i+1}\sigma_{i}(A_{i}\cdots\sigma_{2}(A_{2}\sigma_{1}(A_{1}x))))-\\\
\ \ \ \ \ \
\sigma_{i+1}(A_{i+1}^{\prime}\sigma_{i}(A_{i}^{\prime}\cdots\sigma_{2}(A_{2}^{\prime}\sigma_{1}(A_{1}^{\prime}x))))||_{2}\\\
\leq||\sigma_{i+1}(A_{i+1}\sigma_{i}(A_{i}\cdots\sigma_{2}(A_{2}\sigma_{1}(A_{1}x))))-\\\
\ \ \ \ \ \
\sigma_{i+1}(A_{i+1}^{\prime}\sigma_{i}(A_{i}\cdots\sigma_{2}(A_{2}\sigma_{1}(A_{1}x))))||_{2}+\\\
\ \ \ \ \ \
||\sigma_{i+1}(A_{i+1}^{\prime}\sigma_{i}(A_{i}\cdots\sigma_{2}(A_{2}\sigma_{1}(A_{1}x)))-\\\
\ \ \ \ \ \
\sigma_{i+1}(A_{i+1}^{\prime}\sigma_{i}(A_{i}^{\prime}\cdots\sigma_{2}(A_{2}^{\prime}\sigma_{1}(A_{1}^{\prime}x))))||_{2}\\\
\leq\rho_{i+1}||A_{i+1}-A_{i+1}^{\prime}||_{\sigma}||\sigma_{i}(A_{i}\cdots\sigma_{2}(A_{2}\sigma_{1}(A_{1}x)))||_{2}+\\\
\ \ \ \ \ \ \rho_{i+1}s_{i+1}\Delta_{i}\\\
\leq\rho_{i+1}||A_{i+1}-A_{i+1}^{\prime}||_{\sigma}\prod_{j=1}^{i}\rho_{j}s_{j}B+\rho_{i+1}s_{i+1}\Delta_{i}\\\
\end{array}.$

Therefore, using the induction step, we get the following

$\begin{array}[]{l}\Delta_{i+1}\\\
\leq\rho_{i+1}||A_{i+1}-A_{i+1}^{\prime}||_{\sigma}\prod_{j=1}^{i}\rho_{j}s_{j}B+\rho_{i+1}s_{i+1}\Delta_{i}\\\
\leq\rho_{i+1}||A_{i+1}-A_{i+1}^{\prime}||_{\sigma}\prod_{j=1}^{i}\rho_{j}s_{j}B+\\\
\ \ \ \ \ \
\prod_{j=1}^{i+1}\rho_{j}s_{j}B\left(\sum_{k=1}^{i}\dfrac{||A_{k}-A_{k}^{\prime}||_{\sigma}}{s_{k}}\right)\\\
=\prod_{j=1}^{i+1}\rho_{j}s_{j}B\left(\sum_{k=1}^{i+1}\dfrac{||A_{k}-A_{k}^{\prime}||_{\sigma}}{s_{k}}\right)\end{array}.$

∎

We now return to the proof of Corollary 4.

Proof of Corollary 4. First we verify the three assumptions. Assumption 1
holds with $diam(\mathcal{Z})\leq 2r+1$. Assumption 2 is self-satisfied by the
definition of ramp loss with $0\leq f(z)\leq 1$. By Lemma C.2,
$\lambda_{f,P_{n}}^{+}\leq C_{4}$. Now we proceed to upper bound the covering
number for $\mathcal{F}$. For any $f$ and $f^{\prime}$,

$\begin{array}[]{l}||f-f^{\prime}||_{\infty}\\\
=\sup_{z}|f(z)-f^{\prime}(z)|\\\
=\sup_{z}|l_{\gamma}(-\mathcal{M}(\mathcal{H}_{\mathcal{A}}(x),y))-l_{\gamma}(-\mathcal{M}(\mathcal{H}_{\mathcal{A^{\prime}}}(x),y))|\\\
\leq\sup_{x}\dfrac{2}{\gamma}||\mathcal{H}_{\mathcal{A}}(x)-\mathcal{H}_{\mathcal{A^{\prime}}}(x)||_{2}\\\
\leq\dfrac{2}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}B\left(\sum_{j=1}^{L}\dfrac{||A_{j}-A_{j}^{\prime}||_{\sigma}}{s_{i}}\right)\end{array},$

where the last inequality applies lemma C.3. Since for any matrix $A$, we have
$||A||_{\sigma}\leq||A||_{F}$. The above inequality can be written as

$||f-f^{\prime}||_{\infty}\leq\dfrac{2}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}B\left(\sum_{j=1}^{L}\dfrac{||A_{j}-A_{j}^{\prime}||_{F}}{s_{i}}\right).$

Define $u_{j},a_{j}$ and $\bar{a}$ as

$u_{j}=\dfrac{s_{j}ua_{j}}{\frac{4}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}B},a_{j}=\dfrac{1}{\bar{a}}\left(\dfrac{b_{j}}{s_{j}}\right)^{1/2},\bar{a}=\sum_{j=1}^{L}\left(\dfrac{b_{j}}{s_{j}}\right)^{1/2}.$

So,

$\dfrac{2}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}B\left(\sum_{j=1}^{L}\dfrac{u_{j}}{s_{j}}\right)=\dfrac{u}{2}.$

Then, the covering number $\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)$
can be bounded by

$\begin{array}[]{l}\displaystyle\int_{0}^{\infty}\sqrt{\log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du\\\
\displaystyle\leq\int_{0}^{\infty}\sqrt{\sum_{i=1}^{L}\log\mathcal{N}(A_{i},||\cdot||_{F},u_{i})}du\\\
=\displaystyle\int_{0}^{\infty}\sqrt{\sum_{i=1}^{L}\log\mathcal{N}(\\{A_{i}:||A_{i}||_{\sigma}\leq
s_{i},||A_{i}||_{F}\leq b_{i}\\},||\cdot||_{F},u_{i})}du\\\
\leq\displaystyle\int_{0}^{\infty}\sqrt{\sum_{i=1}^{L}\log\mathcal{N}(\\{A_{i}:||A_{i}||_{F}\leq
b_{i}\\},||\cdot||_{F},u_{i})}du\\\
\leq\displaystyle\int_{0}^{\infty}\sum_{i=1}^{L}\sqrt{\log\mathcal{N}(\\{A_{i}:||A_{i}||_{F}\leq
b_{i}\\},||\cdot||_{F},u_{i})}du\end{array}.$

Since $A_{i}\in\mathbb{R}^{d_{i}\times d_{i-1}}$, we can regard $A_{i}$ as a
vector in $\mathbb{R}^{m}$ with $m=d_{i}\cdot d_{i-1}$ and $||\cdot||_{F}$ as
the standard Euclidean distance in $\mathbb{R}^{m}$. Then the set
$\\{A_{i}:||A_{i}||_{F}\leq b_{i}\\}$ forms a $b_{i}$-ball in
$\mathbb{R}^{m}$, and the covering number for this ball could be upper bounded
by

$\mathcal{N}(\\{A_{i}:||A_{i}||_{F}\leq
b_{i}\\},||\cdot||_{F},u_{i})\leq\left(\dfrac{3b_{i}}{u_{i}}\right)^{m}\leq\left(\dfrac{3b_{i}}{u_{i}}\right)^{W^{2}}$

for $0<u_{i}<b_{i}$, and $\mathcal{N}(\\{A_{i}:||A_{i}||_{F}\leq
b_{i}\\},||\cdot||_{F},u_{i})=1$ for $u_{i}\geq b_{i}$. So,

$\begin{array}[]{l}\displaystyle\int_{0}^{\infty}\sqrt{\log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du\\\
\leq\sum_{i=1}^{L}\bigg{(}\displaystyle\int_{0}^{\infty}\sqrt{\log\mathcal{N}(\\{A_{i}:||A_{i}||_{F}\leq
b_{i}\\},||\cdot||_{F},u_{i})}\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
du_{i}\cdot\dfrac{\dfrac{4}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}B}{s_{i}a_{i}}\bigg{)}\\\
\leq\sum_{i=1}^{L}\bigg{(}\displaystyle\int_{0}^{b_{i}}\sqrt{\log\mathcal{N}(\\{A_{i}:||A_{i}||_{F}\leq
b_{i}\\},||\cdot||_{F},u_{i})}\\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
du_{i}\cdot\dfrac{\dfrac{4}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}B}{s_{i}a_{i}}\bigg{)}\\\
\leq\sum_{i=1}^{L}\dfrac{\dfrac{4}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}BW}{s_{i}a_{i}}\displaystyle\int_{0}^{b_{i}}\sqrt{\log\dfrac{3b_{i}}{u_{i}}}du_{i}\\\
=\dfrac{12}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}BW\sum_{i=1}^{L}\dfrac{b_{i}}{s_{i}a_{i}}\displaystyle\int_{0}^{\frac{1}{3}}\sqrt{\log\dfrac{1}{u_{i}}}du_{i}\\\
\leq\dfrac{12}{\gamma}\prod_{i=1}^{L}\rho_{i}s_{i}BW\bar{a}^{2}\\\
\end{array},$

where the last inequality uses
$\displaystyle\int_{0}^{\frac{1}{3}}\sqrt{\log\dfrac{1}{u_{i}}}du_{i}=\dfrac{1}{6}(2\sqrt{\log
3}+3\sqrt{\pi}\textit{erfc}(\sqrt{\log 3}))<1$. Substituting it into Corollary
1, we obtain

$\begin{array}[]{l}R_{P}(f,\mathcal{B})\leq\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\sqrt{\dfrac{log(1/\delta)}{2n}}+\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\dfrac{288}{\gamma\sqrt{n}}\prod_{i=1}^{L}\rho_{i}s_{i}BW\left(\sum_{i=1}^{L}\left(\dfrac{b_{i}}{s_{i}}\right)^{1/2}\right)^{2}+\\\
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\dfrac{12\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}\cdot(2B+1)\end{array}.$

##  Appendix E Proof of Corollary 5

Proof of Corollary 5. In order to apply Corollary 1, we need to verify the
three assumptions first. Assumption 1 holds with $diam(Z)=2B$. Assumption 2
follows from the observation that $f(z)=||Tz-z||_{2}^{2}\leq B^{2}$. And for
Assumption 3, suppose $f(z)=||Tz-z||_{2}^{2}$. Then,

$\begin{array}[]{l}f(z^{\prime})-f(z)\\\
=||Tz^{\prime}-z^{\prime}||_{2}^{2}-||Tz-z||^{2}_{2}\\\
\leq(B+||Tz-z||_{2})(||Tz^{\prime}-z^{\prime}||_{2}-||Tz-z||_{2})\\\
\leq(B+||Tz-z||_{2})||T(z^{\prime}-z)-(z^{\prime}-z)||_{2}\\\
\leq(B+||Tz-z||_{2})||T-I||_{\sigma}||z^{\prime}-z||_{2}\\\
=(B+||Tz-z||_{2})||z^{\prime}-z||_{2}\end{array},$

where the first inequality uses $||Tz-z||_{2}\leq B$ for any
$z\in\mathcal{Z}$, the second inequality follows from the reverse triangle
inequality and the last equality holds because $||T-I||_{\sigma}=1$ for any
$T\in\mathcal{T}^{k}$. Thus Assumption 3 holds with
$\lambda_{f,P_{n}}^{+}\leq\displaystyle\max_{i}\\{B+||Tz_{i}-z_{i}||_{2}\\}$.
The covering numbers of $\mathcal{F}$ can be calculated as follows. Observe
that

$\begin{array}[]{l}||f_{1}-f_{2}||_{\infty}\\\ =\sup_{z}|f_{1}(z)-f_{2}(z)|\\\
=\sup_{z}\left|||T_{1}z-z||_{2}^{2}-||T_{2}z-z||_{2}^{2}\right|\\\ \leq
2B^{2}||T_{1}-T_{2}||_{\sigma}\\\ \leq 2B^{2}||T_{1}-T_{2}||_{F}\\\ \leq
2B^{2}||U_{1}U_{1}^{T}-U_{2}U_{2}^{T}||_{F}\\\ \leq
2B^{2}||U_{1}U_{1}^{T}-U_{1}U_{2}^{T}+U_{1}U_{2}^{T}-U_{2}U_{2}^{T}||_{F}\\\
\leq 4B^{2}||U_{1}-U_{2}||_{F}\end{array},$

where the second inequality uses $||\cdot||_{\sigma}\leq||\cdot||_{F}$ and the
last inequality follows from the fact that
$||U_{1}(U_{1}^{T}-U_{2}^{T})||_{F}=||(U_{1}-U_{2})U_{2}^{T})||_{F}=||U_{1}-U_{2}||_{F}$.
Then, the covering number $\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)$
can be bounded by

$\begin{array}[]{l}\displaystyle\int_{0}^{\infty}\sqrt{\log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du\\\
\displaystyle\leq\int_{0}^{\infty}\sqrt{\log\mathcal{N}\left(\mathcal{T}^{k},||\cdot||_{F},\frac{u}{4B^{2}}\right)}du\\\
\leq\displaystyle\int_{0}^{\infty}\sqrt{\log\mathcal{N}(\\{U\in\mathbb{R}^{m\times
k}:||U||_{F}\leq\sqrt{k}\\},||\cdot||_{F},\frac{u}{8B^{2}})}du\end{array},$

where the last inequality is due to the monotonicity of covering numbers. And
the covering number for $\\{U\in\mathbb{R}^{m\times
k}:||U||_{F}\leq\sqrt{k}\\}$ could be bounded in the following way:

$\mathcal{N}\bigg{(}\\{U\in\mathbb{R}^{m\times
k}:||U||_{F}\leq\sqrt{k}\\},||\cdot||_{F},\frac{u}{8B^{2}}\bigg{)}\leq\bigg{(}\dfrac{24B^{2}\sqrt{k}}{u}\bigg{)}^{mk}$

for $\dfrac{u}{8B^{2}}<\sqrt{k}$, and
$\mathcal{N}\big{(}\\{U\in\mathbb{R}^{m\times
k}:||U||_{F}\leq\sqrt{k}\\},||\cdot||_{F},\frac{u}{8B^{2}}\big{)}=1$ for
$\dfrac{u}{8B^{2}}\geq\sqrt{k}$. So,

$\begin{array}[]{l}\displaystyle\int_{0}^{\infty}\sqrt{\log\mathcal{N}(\mathcal{F},||\cdot||_{\infty},u/2)}du\\\
\displaystyle\leq\int_{0}^{8B^{2}\sqrt{k}}\sqrt{mk\log\dfrac{24B^{2}\sqrt{k}}{u}}du\\\
\leq 24B^{2}\sqrt{m}k\end{array},$

where the last inequality uses
$\displaystyle\int_{0}^{\frac{1}{3}}\sqrt{\log\dfrac{1}{u}}du<1$. Substituting
it into Corollary 1, we obtain the desired result

$\begin{array}[]{rl}R_{P}(f,\mathcal{B})\leq&\dfrac{1}{n}\sum_{i=1}^{n}f(z_{i})+\lambda_{f,P_{n}}^{+}\epsilon_{\mathcal{B}}+\dfrac{576B^{2}k\sqrt{m}}{\sqrt{n}}+\\\
&\dfrac{24B\sqrt{\pi}}{\sqrt{n}}\Lambda_{\epsilon_{\mathcal{B}}}+B^{2}\sqrt{\dfrac{log(1/\delta)}{2n}}\end{array}.$


# Subject Selection on a Riemannian Manifold for Unsupervised Cross-subject
Seizure Detection

Samaneh Nasiri Ghosheh Bolagh(∗) , Gari. D. Clifford(∗,†)
Department of Biomedical Informatics, Emory University School of Medicine (∗)
Department of Biomedical Engineering, Georgia Institute of Technology(†)
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

Inter-subject variability between individuals poses a challenge in inter-
subject brain signal analysis problems. A new algorithm for subject-selection
based on clustering covariance matrices on a Riemannian manifold is proposed.
After unsupervised selection of the subsets of relevant subjects, data in a
cluster is mapped to a tangent space at the mean point of covariance matrices
in that cluster and an SVM classifier on labeled data from relevant subjects
is trained. Experiment on an EEG seizure database shows that the proposed
method increases the accuracy over state-of-the-art from 86.83% to 89.84% and
specificity from 87.38% to 89.64% while reducing the false positive rate/hour
from 0.8/hour to 0.77/hour.

##  1 Introduction

Brain signal classification plays a crucial role in understanding underlying
mental processes [1]. Perhaps the simplest and most convenient modality for
analyzing the brain is through the electroencephalogram (EEG). Classification
of EEG features can be used for voluntary and involuntary tasks such as
controlling the neuroprosthesis and detection of epileptic seizures [1]. It is
well-known that brain signals are subject-specific, thus brain decoding models
are traditionally designed individually: training and test data belongs to the
same subject [2, 3]. However, it is often inconvenient, expensive and time-
consuming to obtain a large number of training samples to train an associated
classifier for every subject. To mitigate these issues, subsets of past
subjects can be used to initialize a classifier for training on a new subject
[3]. This form of learning is referred to as cross-subject learning [3].
However, this method is less effective, due to inter-subject variability and
possibly large differences between the current subject and past training data.
To address this problem, we use a clustering method on Riemannian manifold,
which groups subjects based on the similarity of the features used by the
classifier.

Barachant et al. [4] proposed a simple classifier based on the Riemannian
distance for brain-computer interface classification. Appropriate forms of
data covariance matrices were used as features and classification was
performed based on a simple distance metric [4]. This approach provided
superior cross-subject generalization capabilities compared to earlier works,
as well as robustness to EEG artifacts, outliers and mislabeling [2, 3].

In this article, we focus on the problem of cross-subject brain signal
classification without assuming knowledge of labels from the new (test)
subject. The key contribution of this work is to develop a subject selection
algorithm on a Riemannian manifold. Clearly, the inherent inter-subject
variability between individuals poses a challenge for the brain signal
classification, therefore it is important to identify subsets of subjects that
most closely map to the test case, and allow for a selection of a model
trained completely or weighted towards such a subset. In order to obtain
subsets of relevant subjects, we apply spectral clustering on a Riemannian
manifold. Subsequently, a support vector machine (SVM) classifier is used in
the tangent space to classify signals. Finally, the algorithm’s performance is
assessed on the open access CHB-MIT database [5].

##  2 Subject Selection on a Riemannian Manifold

In machine learning, it is often assumed that the training and test subjects
are drawn from the same distribution. Moreover, the patients on which we train
the data should exhibit enough variation to allow an accurate sampling of the
distribution. However, in the cross-subject classification problem, the
distribution of training subjects and test subject are different from each
other due to inherently high inter-subject variability and our inability to
accurately sample the feature space for the patient population. Consequently,
the training data comprises several sub-distributions. Therefore, identifying
(and using) the subset of training subjects that are most similar to our test
subject is likely to improve classification. To find the similar subjects,
spectral clustering is applied on the feature space.

To describe the extraction of a feature, we let $\mathbf{X}_{i}\in\Re^{C\times
T_{s}}$ denote a trial indexed by $i$, with $C$ the number of channels,
$T_{s}$ the number of time samples and $y_{i}$ the class label of the trial.
The feature covariance matrices are obtained simply by using a Sample
Covariance Matrix (SCM) estimator [6], such as

$\mathbf{\Sigma}_{i}=\frac{1}{T_{s}-1}{\mathbf{X}}_{i}{\mathbf{X}}_{i}^{T}.$
(1)

Such second-order information has been shown to be suitable for capturing the
relevant information about mental states [3]. The covariance matrices in (1)
belong to the space of Symmetric Positive Definite (SPD) matrice, which form a
Riemannian manifold [6]. Therefore, we can use tools from differential
geometry on Riemannian manifolds to manipulate the features.

Riemannian Distance: For any two covariance matrices $\mathbf{\Sigma}_{1}$ and
$\mathbf{\Sigma}_{2}$, the Riemannian distance is defined according to the
Riemannian metric as [4]

$\delta_{R}(\mathbf{\Sigma}_{1},\mathbf{\Sigma}_{2})=\|\mathrm{log}\left(\mathbf{\Sigma}_{1}^{-1/2}\mathbf{\Sigma}_{2}\mathbf{\Sigma}_{1}^{-1/2}\right)\|_{F}=\left[\sum_{c=1}^{C}\log^{2}\lambda_{c}\right]^{1/2}$
(2)

where $\lambda_{c},c=1\ldots C$ are the real eigenvalues of
$\mathbf{\Sigma}_{1}^{-1/2}\mathbf{\Sigma}_{2}\mathbf{\Sigma}_{1}^{-1/2}$ and
$C$ the number of channels. This distance is _Affine-invariant_ [4], i.e, it
is invariant with respect to similar and congruent transformations, and
inversion.

Riemannian Mean: The Riemannian geometric mean of $I$ covariance matrices,
also called the Fréchet or Karcher mean, is the point on the manifold
minimizing the dispersion given by [4]:

$\mathfrak{G}\left(\mathbf{\Sigma}_{1},\ldots,\mathbf{\Sigma}_{I}\right)=\operatorname*{argmin}_{\mathbf{\Sigma}}\sum_{i=1}^{I}\delta_{R}^{2}\left(\mathbf{\Sigma},\mathbf{\Sigma}_{i}\right).$
(3)

There is no closed form expression for the mean of $I>2$. However a gradient
descent procedure in the manifold can be used in order to find the solution
[6].

Zianai et al [3] have proposed to transform the covariance matrices of every
subject in order to center them with respect to a reference covarince matrix,
making the data from different subjects comparable. We use this transformation
in our work., which is given by

$\Sigma_{i}^{(j)}\Rightarrow(\bar{\Sigma}^{(j)})^{-\frac{1}{2}}\Sigma_{i}^{(j)}(\bar{\Sigma}^{(j)})^{-\frac{1}{2}}$
(4)

where $\bar{\Sigma}^{(j)}$ is the center of mass of covarinace matrices for
subject $j$. In order to find relevant subjects, spectral clustering is
applied on Riemannian manifold. At first, an affinity matrix is defined using
Gaussian function and the Riemannian distance. Following [7], the diagonal
elements of the affinity matrix are set to zero, giving

$A_{ij}=exp(-\frac{\delta_{R}^{2}(\bar{\mathbf{\Sigma}_{i}},\bar{\mathbf{\Sigma}_{j}})}{\sigma^{2}})$
(5)

The width of RBF kernel was chosen as $\sigma=0.5$, without attempting to
optimize, since the database is not large enough and we are likely to overfit.

Based on [8], the number of clusters can be estimated by the number of
eigenvalues of $\mathbf{A}^{\prime}$, the normalized affinity matrix, which
are approximately equal to unity. In this work, based on the computed affinity
matrix, the number of clusters was found to be five.

Algorithm 1 summarizes the proposed method for subject selection using
spectral clustering on a Riemannian manifold.

Algorithm 1 Subject Selection on Riemannian Manifold

0: $\mathbf{X}_{t}^{u}$ Unlabeled Signal from all subjects

0: ${\left\\{\mathbf{{X}_{s}^{l}}\right\\}}_{s=1}^{N_{R}}$ Relevant Subjects

1: Estimate Sample Covariance Matrix from feature matrix as Eq.(1)

2: Apply the transformation as
$\Sigma_{i}^{(j)}\Rightarrow(\bar{\Sigma}^{(j)})^{-\frac{1}{2}}\Sigma_{i}^{(j)}(\bar{\Sigma}^{(j)})^{-\frac{1}{2}}$

3: Calculate the mean for each subject as
$\bar{\Sigma}_{s}=\operatorname*{argmin}_{\mathbf{\Sigma}\in\mathcal{M}}\sum_{i=1}^{n_{s}}\delta_{R}^{2}\left(\mathbf{\Sigma},\mathbf{\Sigma}_{i}\right)$

4: Use Riemannian distance as similarity metric and define Affinity matrix
$A_{ij}=exp(-\frac{\delta_{R}^{2}(\bar{\mathbf{\Sigma}_{i}},\bar{\mathbf{\Sigma}_{j}})}{\sigma^{2}})$

5: Define $D=\text{diag}(d_{11},d_{22},\cdots,d_{NN})$, where
$d_{ii}=\sum_{j=1}^{N}A_{ij}$

6: Determine the number of cluster $K$ by counting the eigenvalues of
$\mathbf{A}^{\prime}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}$ which are most close
to 1.

7: Compute the $K$ eigenvectors $\\{\mathbf{u}_{j}\\}_{j=1}^{K}$ of
$A^{\prime}$ associated with its $K$ largest eigenvalues, and form the matrix
$\mathbf{U}=[\mathbf{u}_{1},\mathbf{u}_{2},\cdots,\mathbf{u}_{K}]$ by stacking
the eigenvectors in columns

8: Apply k-means to the rows of $\mathbf{U}$ to cluster the data into $K$
different groups.

9: Assign the original point $\Sigma_{i}$ on Riemannian manifold to cluster
$j$ if and only if row $i$ of the matrix $U$ was assigend to cluster $j$

##  3 Experiment

To demonstrate the merit of the proposed approach, we used a public EEG
database, the PhysioNet CHB-MIT database. This database contains EEG data with
23 channels from 23 patients divided among 24 cases (one patient has 2
recordings, 1.5 years apart) [9]
(www.physionet.org/physiobank/database/chbmit/). The goal in this database is
to detect whether a 10 second segment of signal contains a seizure or not with
high sensitivity and specificity and low false negative rate, as annotated in
the database.

At the first step of pre-processing, a 5th-order Butterworth 0.5-30 Hz band-
pass filter was applied. Each recording was divided into 10 sec epochs and
classified as either dominantly seizure or non-seizure (using expert labels).
Then, the FFT coefficients were extracted in three standard bands: theta (4-7
Hz), alpha (8-13 Hz) and beta (13-30 Hz). With a bin size of 0.1 Hz, this
resulted in 250 Fourier coefficients for each of the 23 channels. These
coefficients were then concatenated and covariance matrices extracted. Then to
increase the similarity of the data between subjects, each covariance matrix
was transformed per equation (4). The subsets of relevant subjects were then
determined per Algorithm 1. After subject selection, a SVM classifier was
trained on labeled data from the subjects that were located in the same
cluster and then tested on the withheld patient (i.e via a leave-one-subject-
out cross validation (LOSO-CV) procedure). In order to use many popular and
efficient classifiers, most of the literature focuses on mapping the
covariance matrices into a tangent space of Riemannian manifolds to extend
Euclidean-based algorithms to the Riemannian manifold of the SPD matrices [4,
3]. The SVM classifier can be applied on the tangent space located at the
geometric mean of the whole set of trials from relevant subjects to a given
test subject as follows:
$\mathbf{\Sigma}_{\mathfrak{G}}=\mathfrak{G}(\mathbf{\Sigma}_{i},i=1,\cdots,I)$.
Each SCM, $\mathbf{\Sigma}_{i}$, is then mapped into this tangent space, to
yield the set of $m=\frac{n(n+1)}{2}$ dimensional vectors [4]:

$s_{i}={\mathbf{\Sigma}_{\mathfrak{G}}}^{-\frac{1}{2}}log_{\mathbf{\Sigma}_{\mathfrak{G}}}(\mathbf{\Sigma}_{i}){\mathbf{\Sigma}_{\mathfrak{G}}}^{-\frac{1}{2}}$
(6)

In the experiments detailed here, the LIBSVM toolbox [10] was used.

Table 1 provides the per-patient (LOSO-CV) results and table 2 summarizes the
average results and compares them to the state-of-the-art. The methods
proposed previously by Chen et al. [11] and Thodoroff et al. [12] are based on
the wavelet transformation and deep learning, respectively. Table 2 shows an
increase over previous works in accuracy and specificity by 2-3%. (Subject-
specific works are not included in this comparison, since training and testing
on the same subject is less useful and inflates statistics.) We also note that
we improve the false positive rate from 1.7/hour to 0.77/hour over Shoeb’s
original work [9]. To the best of our knowledge, the method described in this
article is the first work to propose a subject selection on a Riemannian
manifold for unsupervised cross-subject seizure detection.

Table 1: Performance on CHB-MIT database Subject ID | Accuracy (%) | Sensitivity (%) | False Positive rate (seizures/h) | Latency (sec)
---|---|---|---|---
1 | 93.33 | 98.28 | 0.194 | 5.10
2 | 84.47 | 100.00 | 0.43 | 7.52
3 | 93.51 | 100.00 | 0.26 | 2.63
4 | 91.41 | 84.14 | 0.22 | 7.42
5 | 94.25 | 100.00 | 0.34 | 4.46
6 | 82.79 | 46.63 | 1.74 | 3.01
7 | 86.56 | 98.22 | 1.48 | 5.62
8 | 88.89 | 100.00 | 0.35 | 4.02
9 | 95.41 | 100.00 | 1.28 | 8.23
10 | 92.82 | 100.00 | 1.20 | 2.87
11 | 94.39 | 85.16 | 0.46 | 2.52
12 | 84.13 | 62.40 | 2.34 | 5.63
13 | 90.62 | 83.53 | 2.86 | 8.12
14 | 84.73 | 56.33 | 0.55 | 3.78
15 | 86.13 | 78.49 | 0.24 | 5.85
16 | 86.40 | 58.42 | 1.66 | 3.34
17 | 90.84 | 81.19 | 0.82 | 6.21
18 | 85.40 | 97.93 | 0.41 | 5.13
19 | 91.84 | 100.00 | 0.21 | 9.89
20 | 93.76 | 69.59 | 0.58 | 2.84
21 | 93.62 | 100.00 | 0.46 | 2.78
22 | 87.28 | 100.00 | 0.52 | 12.44
23 | 92.76 | 68.79 | 0.14 | 1.36
24 | 90.76 | 89.38 | 0.10 | 5.01
mean$\pm$(std) | 89.84 $\pm$ (3.90) | 85.77$\pm$(16.96) | 0.77$\pm$(0.75) | 5.24$\pm$(2.65)
Table 2: Performance comparison of works on CHB-MIT database Method | Accuracy (%) | Sensitivity (%) | Specificity (%)
---|---|---|---
Chen et al [11] | 86.83 % | 85.29 % | 87.38 %
Thodoroff et al [12] | 84.18% | 85.16 % | 83.21 %
Proposed Method |  89.84 % |  85.77 % |  89.64 %

##  4 Conclusion

It is well-known that EEG signals are very specific to each subject. As a
result, establishing a generic population model with high classification
performance is extremely challenging, due to the inherent inter-subject
variability. In this work, a novel subject selection approach for cross-
subject brain signal classification was proposed and tested. Spectral
clustering on a Riemannian manifold was applied in order to identify subsets
of relevant subjects to create sub-models. By evaluating the proposed
algorithm on the CHB-MIT scalp EEG database, we have shown that the our method
can outperform previous published works on the same data (not focused on
individually specific models). Future work will focus on evaluating the
proposed method on other databases and addressing how the mismatch between the
distributions of training and test subjects may be reduced.

### Acknowledgments

This research is supported in part by funding from the James S. McDonnell
Foundation, Grant $\\#220020484$ (http://www.jsmf.org), the Rett Syndrome
Research Trust and Emory University.

## References

  * [1] John-Dylan Haynes and Geraint Rees.  Decoding mental states from brain activity in humans.  Nature reviews. Neuroscience, 7(7):523, 2006.
  * [2] Samaneh Nasiri Ghosheh Bolagh, Mohammad Bagher Shamsollahi, Christian Jutten, and Marco Congedo.  Unsupervised cross-subject BCI learning and classification using riemannian geometry.  In 24th European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning (ESANN 2016), 2016.
  * [3] Paolo Zanini, Marco Congedo, Christian Jutten, Salem Said, and Yannick Berthoumieu.  Transfer learning: a riemannian geometry framework with applications to brain-computer interfaces.  IEEE Transactions on Biomedical Engineering, 2017.
  * [4] Alexandre Barachant, Stéphane Bonnet, Marco Congedo, and Christian Jutten.  Multiclass brain–computer interface classification by Riemannian geometry.  IEEE Transactions on Biomedical Engineering, 59(4):920–928, 2012\.
  * [5] A. L. Goldberger, L. A. N. Amaral, L. Glass, J. M. Hausdorff, P. Ch. Ivanov, R. G. Mark, J. E. Mietus, G. B. Moody, C.-K. Peng, and H. E. Stanley.  PhysioBank, PhysioToolkit, and PhysioNet: Components of a new research resource for complex physiologic signals.  Circulation, 2000 (June 13).
  * [6] Alexandre Barachant, Stéphane Bonnet, Marco Congedo, and Christian Jutten.  Classification of covariance matrices using a Riemannian-based kernel for BCI applications.  Neurocomputing, 112:172–178, 2013.
  * [7] Andrew Y Ng, Michael I Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In Advances in Neural Information Processing Systems, pages 849–856, 2002.
  * [8] Fei Wang and Changshui Zhang.  Spectral clustering for time series.  Pattern Recognition and Data Mining, pages 345–354, 2005.
  * [9] Ali Hossam Shoeb.  Application of machine learning to epileptic seizure onset detection and treatment.  PhD thesis, Massachusetts Institute of Technology, 2009.
  * [10] Chih-Chung Chang and Chih-Jen Lin.  LIBSVM: a library for support vector machines.  ACM transactions on intelligent systems and technology (TIST), 2(3):27, 2011.
  * [11] Duo Chen, Suiren Wan, Jing Xiang, and Forrest Sheng Bao.  A high-performance seizure detection algorithm based on discrete wavelet transform (DWT) and EEG.  PloS one, 12(3):e0173138, 2017.
  * [12] Pierre Thodoroff, Joelle Pineau, and Andrew Lim.  Learning robust features using deep learning for automatic seizure detection.  In Machine Learning for Healthcare Conference, pages 178–190, 2016\.