# On Neural Network approximation of ideal adversarial attack and convergence
of adversarial training

Rajdeep Haldar, Qifan Song
Department of Statistics
Purdue University
{rhaldar<EMAIL_ADDRESS>
###### Abstract

Adversarial attacks are usually expressed in terms of a gradient-based
operation on the input data and model, this results in heavy computations
every time an attack is generated. In this work, we solidify the idea of
representing adversarial attacks as a trainable function, without further
gradient computation. We first motivate that the theoretical best attacks,
under proper conditions, can be represented as smooth piece-wise functions
(piece-wise Hölder functions). Then we obtain an approximation result of such
functions by a neural network. Subsequently, we emulate the ideal attack
process by a neural network and reduce the adversarial training to a
mathematical game between an attack network and a training model (a defense
network). We also obtain convergence rates of adversarial loss in terms of the
sample size $n$ for adversarial training in such a setting.

##  1 Introduction

Neural networks are universal approximators [22, 8, 28, 34] and have enjoyed
immense popularity in the realm of machine learning problems and artificial
intelligence applications over the past two decades. Their ability to
approximate arbitrary functions with high accuracy has facilitated state-of-
the-art performance in nonparametric regression and classification problems.

Although, neural networks showcase high accuracy and fairly well
generalization on the training data and testing data; their testing
performance is vulnerable to minor perturbations to the original data [37].
[16] introduced a gradient-based method to generate bounded perturbations of
input data (adversarial examples/attack) which significantly hampers the
predictive performance of a given neural network. The adversarial robustness
of neural networks has been a topic of importance since then. One popular way
to make neural networks robust to such attacks is via training over generated
adversarial examples (adversarial training). The robustness of the network
will directly correspond to the quality or strength of the attack.

Over the years a slew of work has been done in generating strong adversarial
attacks [2], thereby increasing the robustness of the network models when
adversarially trained. Traditionally, the attack generation process has been
some sort of gradient-based operation such as the Fast-gradient [16, 9],
Iterative gradient [27], Projected gradient descent (PGD) [29], Carlini Wagner
Attack [7] etc, requiring direct access to the analytic form of the model.
Attacks that are generated having direct access to the underlying model are
known as white-box attacks. Alternatively, one can view these attacks as a
function of the input data which results in a perturbation in the original
space. If we think of attacks as a function, one can approximate it using a
neural network. So, the underlying classification/regression model is a neural
network that must learn how to defend itself (robustness) against the attacks
generated by an adversary neural network; adversarial training in this context
then becomes a game (in a game-theoretic sense) between two neural networks.
This perspective of using neural networks to generate attacks is fairly recent
and has been explored in [4, 40, 39, 23]. A benefit of using neural networks
to generate attacks is that we learn an attack function after training. Once
we obtain this attack function spanning over the input space, we can just use
it to generate new adversarial examples without having access to the
underlying predictive model. Using neural networks to generate attacks we can
exhibit so-called semi-white box or black-box attacks, which have limited
access or no access to the underlying model respectively. Another
consideration is the computation costs to generate these attacks; The
empirical successful white box attacks like PGD or similar iterated gradient
methods usually require recurrent gradient computations for each new sample of
data.

Even though a lot of progress has been made on the algorithmic front from both
attack [23, 14, 39, 9] and defense [13, 12, 35, 36] perspectives; there is a
lack of theoretical results to justify such methods. In this paper, we would
like to unify these ideas in a common mathematical framework and motivate
adversarial training in the context of an adversarial game (attack-defense)
between two neural networks.

In this work, we will prove results for RELU-based neural networks defined as:

######  Definition 1.1 (Deep Neural Networks).

Define the class of deep Relu networks
$f\in\mathcal{F}_{\sigma}(L,W,w,\kappa,B)$ as parametrized functions of the
form:

$f(x)=A^{(L)}\cdot\sigma\left(A^{(L-1)}\cdots\sigma\left(A^{(1)}x+b^{(1)}\right)\cdots+b^{(L-1)}\right)+b^{(L)},$

where the $A^{(l)}$’s are the weight matrices and $b^{(l)}$’s are the bias
vectors with real-valued elements, and the activation function
$\sigma:\mathbb{R}\mapsto\mathbb{R}$ is applied element-wise.
$\sigma(x)=\operatorname{ReLU}(x)=\max\\{0,x\\}$ (rectified linear unit). The
network is $L$-layer deep and its width is bounded by
$\sup_{l}\operatorname{dim}(b^{(l)})\leq w$. Further, we assume that

$\max_{i,j,l}\left|A^{(l)}_{ij}\right|\leq\kappa,\max_{i,l}|b^{(l)}_{i}|\leq\kappa,\sum_{l=1}^{L}\left\|A^{(l)}\right\|_{0}+\left\|b^{(l)}\right\|_{0}\leq
W,\text{ for }i=1,\ldots,L,$

i.e. all elements in the $A^{(l)}$’s and $b^{(l)}$’s are bounded in absolute
value by $\kappa$, and there are at most $W$ non-zero parameters in total.
Finally, we assume $\|f\|_{\infty}\leq B<\infty$ for all $f$. If the
particular value $B$ is an arbitrarily large constant, we may suppress the
notation and write
$\mathcal{F}_{\sigma}(L,W,w,\kappa,B)=\mathcal{F}_{\sigma}(L,W,w,\kappa)$.

###  1.1 Contribution

We first formalize the notion of an ideal or best possible attack
characterized by the underlying loss for the classification/regression
problem. Then we justify how gradient-based PGD and FGSM attacks are related
to the ideal attack. Furthermore, we show indeed the ideal attack can be
approximated by neural networks up to arbitrary accuracy; justifying the use
of neural networks to generate attacks. Subsequently, we derive convergence
bounds for adversarial training in the context of an adversarial game between
two neural networks as the sample-size $n$ increases. Finally, we showcase
some numerical experiments to verify the capabilities of neural networks to
learn the ideal attack function. Also, the robustness and attack strength of
adversarial trained networks in the context of an adversarial game has been
compared to the PGD robustly trained networks and PGD attacks respectively.

###  1.2 Problem definition / Notation

Let $(x,y)=\mathcal{Z}\in\mathcal{X}\times\mathcal{Y}=\mathcal{\tilde{Y}}$
represent an observation pair where $x\in\mathcal{X}$ is the predictor and
$y\in\mathcal{Y}$ is the response, where $\mathcal{Y}=\mathbbm{R}^{k}$ or
$\mathcal{Y}=\\{1,\dots,k\\}$ for regression and classification problems
respectively. Without loss of generality, we assign $\mathcal{X}=[0,1]^{D}$
after normalization.

Let $f:\mathcal{X}\to\mathbbm{R}^{k}\in\mathcal{C}$ be our model, where
$\mathcal{C}$ is some function class.
$\mathcal{L}:\mathbbm{R}^{k}\times\mathcal{Y}\to\mathbbm{R}$ denotes a loss
function which we wish to minimize, this could be the negative log-likelihood
or any reasonable discrepancy measure between $f(x)$ and $y$. An ideal model
minimizes the expected loss, i.e.,
$f^{*}=\arg\inf\limits_{f\in\mathcal{C}}\mathbbm{E}\mathcal{L}(f(x),y)$, where
$\mathbbm{E}=\mathbbm{E}_{(x,y)\sim\mathcal{P}}$ denotes the expectation over
the true distribution $\mathcal{P}$ of the data.

######  Definition 1.2 ($(p,\delta)$ Perturbation function class).

$\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ is a $(p,\delta)$ perturbation
function class restricted on function class $\tilde{\mathcal{C}}$

$\mathcal{F}^{p}_{\delta}=\\{g:\mathcal{\tilde{Y}}\to\mathcal{X}\in\tilde{\mathcal{C}}:\forall(x,y)\in\mathcal{\tilde{Y}},\,\norm{g(x,y)}_{p}\leq\delta\\},$
(1)

where $\tilde{\mathcal{C}}$ is some base function class, for instance, the
class of continuous functions, spline functions, Hölder functions, etc;

######  Definition 1.3 ($\ell_{p}(\delta)$ function attack).

$\lambda^{f}$ is the best $\ell_{p}(\delta)$ function attack (within the
family $\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$) on $f$ iff

$\lambda^{f}(x,y)=\arg\max\limits_{\lambda\in\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})}\mathbbm{E}\mathcal{L}(f(x+\lambda(x,y)),y).$
(2)

Our definition for $\ell_{p}(\delta)$ function attack serves as a surrogate of
the point wise $\ell_{p}$ attacks of strength $\delta$ in the literature,
defined as

$\lambda^{p.w}(x,y)=\arg\max_{\norm{\lambda}_{p}\leq\delta}\mathcal{L}(f(x+\lambda),y).$
(3)

Note that if $\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ has a nice
parameterized form, then the evaluation of $\lambda^{f}$, e.g., designing an
attack for new observations, would be more computationally efficient than
$\lambda^{p.w}(x,y)$, which generally needs to be evaluated point-wisely. Our
framework is similar to the one defined in [4].

#### Adversarial Training

The adversarial training aims to make the model robust against adversarial
attacks via minimizing the objective loss under the best possible attack
function on the model, i.e.,

######  Definition 1.4 (Robust $(p,\delta)$ model).

$f^{*}$ is a robust $(p,\delta)$ model if it minimises the following
objective:

$f^{*}=\arg\min\limits_{f\in\mathcal{C}}\max\limits_{\lambda\in\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})}\mathbbm{E}\mathcal{L}(f(x+\lambda(x,y)),y)$
(4)

where $\mathbbm{E}\mathcal{L}(f(x+\lambda(x,y)),y)$ is the adversarial loss.

When shifting from the point-wise paradigm to a functional form of an attack,
the natural question is which perturbation function class
$\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ (or more specifically the
choice of $\tilde{\mathcal{C}}$) is appropriate to induce adversarial
perturbations, that can approximate the strongest point-wise attack
$\lambda^{p.w}$, of any given input $(x,y)$ and model $f\in\mathcal{C}$?

The theoretical goal of this work is to determine a function class that
includes the optimal pointwise attack (i.e.,
$\lambda^{p.w}\in\tilde{\mathcal{C}}$), then we can try to approximate this
function class up to arbitrary accuracy using a parametric family, i.e.,
neural networks. Subsequently, we can then view our adversarial training
framework (4) as a mathematical game between two networks, and establish the
statistical properties for this game.

##  2 Best adversarial attack

In this section, we will first develop some heuristics and then rigorously
show that for smooth $f$’s, the point-wise attacks (3) can be represented by
functions of a certain form. We will first develop some intuition by analyzing
the simple case of $\ell_{\infty}(\delta)$ attacks on linear and logistic
regression models.

For the sake of brevity, from now onwards we will denote:

$\mathcal{L}(f(x+\lambda(x,y)),y)\coloneqq\mathcal{L}(f,\lambda,\mathcal{Z})\text{
and }\mathcal{L}(f(x),y)\coloneqq\mathcal{L}(f,\mathcal{Z})$ (5)

###  2.1 Attacks on linear models and FGSM

#### Linear regression

Let $y|x\sim N(\beta\cdot x,\sigma^{2})$ be the true relationship, and
$f(x)=\hat{\beta}\cdot x$ be the estimated model. The loss, in this case, is
the negative log-likelihood up to a constant:
$\mathcal{L}(f(x),y)=(y-\hat{\beta}\cdot x)^{2}$. For a given $\hat{\beta}$,
the ideal function attack $\lambda^{f}$ should satisfy the objective:
$\lambda^{f}=\arg\max_{\lambda\in\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})}\mathbbm{E}\mathcal{L}(f(x+\lambda),y)$.
With some straightforward one can see that the point wise attack (3) is as
follows:

$\displaystyle\lambda^{p.w}(x,y)$
$\displaystyle=\delta\cdot\text{sign}[(\hat{\beta}\cdot x-y)/\hat{\beta}].$

Note that one easily derives that this attack is equivalent to
$\lambda^{p.w}(x,y)=\delta\cdot\text{sign}(\nabla_{x}\mathcal{L}(f,\mathcal{Z}))$
as $\text{sign}(\frac{1}{\hat{\beta}})=\text{sign}(\hat{\beta})$. For the
multivariate case $Y|X\sim N(\beta^{T}X,\Sigma)$ where $\beta$ is a vector
now, one can get analogous results. The essential point is that for the linear
regression case, the best point-wise adversarial attacks are essentially
piece-wise constant functions which are related to the gradient of the
underlying loss $\mathcal{L}$ w.r.t. $x$. On the other hand, if our
perturbation function class $\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ is
flexible enough and can well approximate any piece-wise constant functions,
then trivially, $\lambda^{f}(x,y)\approx\lambda^{p.w}(x,y)$.

#### Logistic regression

For binary classification, $\mathcal{Z}=(y,x)\in\\{0,1\\}\times[0,1]$ follows
the conditional distribution:
$\mathbbm{P}(y=1|x)=p(\beta,x)=\frac{1}{1+e^{-\beta x}}$, i.e., $y|x\sim{\rm
Bernoulli}(p(\beta,x))$. Let the model $f$ be the logistic regression fit with
parameter estimator $\hat{\beta}$. The loss is the negative log-likelihood up
to a constant:
$\mathcal{L}(f(x),y)=-y\ln(p(\hat{\beta},x))-(1-y)\ln(1-p(\hat{\beta},x))$. As
in linear regression case, one can calculate $\lambda^{p.w}$; by simple
algebra, one can see the critical condition is
$\hat{\beta}(p(\hat{\beta},x+\lambda)-y)=0$ and $p(\hat{\beta},x+\lambda)$ is
monotonic in $\lambda$, which results in

$\lambda^{p.w}(x,y)=\delta\cdot\text{sign}(0.5-y)\text{sign}(\hat{\beta}).$
(6)

We can replicate the exact same arguments for the multivariate case, and get
the analogous result (with $\hat{\beta},x$ now being vectors). As in linear
regression case, one can express $\lambda^{p.w}$ (under the
$\ell_{\infty}(\delta)$ function attack) in terms of the gradient of
$\mathcal{L}(f,\mathcal{Z})$, and we get the exact same form:

$\lambda^{p.w}(x,y)=\delta\cdot\text{sign}(\nabla_{x}\mathcal{L}(f,\mathcal{Z})).$
(7)

Consequently, if the function class
$\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ can well approximate any
piece-wise constant functions, then
$\lambda^{f}(x,y)\approx\lambda^{p.w}(x,y)$.

######  Remark (FGSM as $\ell_{\infty}(\delta)$ function attack).

The attack of form
$\delta\cdot\text{sign}(\nabla_{x}\mathcal{L}(f,\mathcal{Z}))$ is known as the
fast-gradient signed max (FGSM) attack in the literature. [16] argues that
FGSM is the exact attack for logistic regression. We can reaffirm this even
from a function attack perspective, if the function class
$\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ is sufficiently broad. In
general, we can extend this idea and think of FGSM as a piece-wise constant
function which is the best $\ell_{\infty}(\delta)$ function attack for linear
models. The idea of a piece-wise smooth function for arbitrary loss is a much
more general concept and we will see how FGSM fits as a special case in our
framework.

###  2.2 Gradient flow-based attack

#### Basic concepts

In this section, we will construct a functional form for the best point-wise
$\ell_{p}(\delta)$ attack using the concept of gradient flows and continuous
dynamic systems (CDS). For the sake of completeness, preliminary knowledge of
CDS can be found in the appendix. Readers of interest in the detailed
background and theories of CDS may refer to Katok’s book on the Modern Theory
of dynamical systems or Brin’s book which provides a more condensed version of
the theory [6, 25]. Definition A.1 formally defines a CDS $T$, as a function
of time in an arbitrary metric space $\mathcal{X}$. $T$ can be thought of as a
law that dictates the movement of a particle in $\mathcal{X}$ as a function of
its initial position, i.e., $T(t)x_{0}$ is the location of a particle at time
$t$ initializing from $x_{0}$. Given a CDS $T$, an object of interest is the
set of points in space $\mathcal{X}$ where the particle is headed given any
initial position. These special points can be said to attract the particle
towards them (i.e. Definition A.2). We would also want the trajectory of the
particle given a particular initial point to be tractable, and the set of
initial points $\mathcal{A}(T)$ for which the trajectory is well defined is
called the attractor (Definition 25).

A point $x_{0}\in\mathcal{X}$ is a stationary point for a dynamical system $T$
if $T(t)x_{0}=x_{0}$ for all $t\in\mathbbm{R}^{+}$ (i.e., a stationary point
is a singleton invariant set A.4). Corresponding to a given CDS $T$, one can
define $T^{-1}$ which represents the inverse dynamics, i.e. for any $s\geq t$
and $s,t\in\mathbbm{R}^{-}$ we have $T(s-t)T^{-1}(t)=T^{-1}(s)$. If $T^{-1}$
is unique for a $T$, we say $T$ is one-one. $T^{-1}$ controls the flow of
particles going back in time, one can think of it as an inverse mapping. If
$T$ is one-one, we can have an abuse of notation and extend $T$ to the
negative time domain as $T(s)\coloneqq T^{-1}(s)\text{ if }s<0$.

We can also define the concept of stable ($W_{s}(x_{0})$) and unstable set
($W_{u}(x_{0})$) of a stationary point $x_{0}$ (Definition A.6) of an one-to-
one CDS. The stable set is essentially the set of points that eventually reach
$x_{0}$ under the dynamic system $T$; Similarly, the unstable set is the set
of points that eventually reach $x_{0}$ under the inverse dynamics $T^{-1}$.

####  2.2.1 Gradient Flow

We will consider a CDS $T^{gf}$, which follows a gradient dynamic, i.e.,
$T^{gf}$ is the solution to the ordinary differential equation
$\dot{x}=\nabla_{x}F(x)$ where $F(x)=\mathcal{L}(f(x),y)$. Note that for the
simplicity of the technical analysis, we assume that $F(x)$ is continuously
differentiable and all of its local optimums locate in the interior of
$\mathcal{X}$.

Assume that $\mathcal{X}$ is a compact space, if the gradient is bounded
everywhere in $\mathcal{X}$, then $\mathcal{A}(T^{gf})=\mathcal{X}$. Also, the
stationary points of $T^{gf}$ ($\\{x:T^{gf}(t)x=x;\,\forall
t\in\mathbbm{R}^{+}\\}$) are essentially the equillibria/critical points
($E=\\{x:\nabla{F(x)=0}\\}$) of $F$. A classic result in the literature is
that for $T^{gf}$ the set of equillibria attracts $\mathcal{A}(T^{gf})$
(Section 6, Theorem 6.12 [20]). This essentially means that if the particle
follows the gradient dynamic system, it is guaranteed to reach a critical
point.

The gradient flow satisfies a lot of nice properties including point-
dissipative (Definition A.3) set of equilibria, being one-one CDS,
$(T^{gf})^{-1}$ being just the negative gradient flow, i.e., solution of the
ODE $\dot{x}=-\nabla F(x)$, etc.

Also, for a maximization framework, the path followed by gradient flow is a
natural choice to study as it is locally maximal; following the gradient flow
path, the function value is non-decreasing as
$\dot{F}(x)=\norm{\nabla{F(x)}}_{2}^{2}\geq 0$ .

####  2.2.2 Decomposition of $\mathcal{X}$ into manifolds

For $T^{gf}$, the critical points (w.r.t. gradient) are essentially the
stationary points (w.r.t. dynamic system)and the stable set $W_{s}(x_{0})$ for
any $x_{0}\in E$ are essentially the set of initial positions which lead to
the local maxima/saddle $x_{0}$ when following the gradient path. Intuitively
any point in our metric space $\mathcal{X}=\mathcal{A}(T^{gf})$ should lead to
one of these critical points under $T^{gf}$. Remark 6.11 of [20] formalizes
this notion and we get $\mathcal{X}=\bigsqcup_{x_{0}\in E}W_{s}(x_{0})$.

Essentially we are able to partition the metric space based on the local
maxima/saddle points of the gradient flow dynamic system. This decomposition
will be useful when we argue the piece-wise nature of our function attack.
Additionally, if $T^{gf}(t)x$ is $C^{k}$ w.r.t. $t$ for any $x\in
W_{s}(x_{0})$ then $W_{s}(x_{0})$ is a $C^{k}$ manifold, and $\mathcal{X}$ is
just union of manifolds (see; Section 4 of [20]).

####  2.2.3 Projected gradient flow

Let’s denote $x_{adv}=\lambda^{p.w}(x_{s},y)+x_{s}$. By the definition of a
point-wise $\ell_{p}$ attack of strength $\delta$ (3), $x_{adv}$ must satisfy
the following constraint optimisation problem $\forall x_{s}\in\mathcal{X}$:

$\displaystyle\arg\max_{x\in\mathcal{X}}F(x),$ $\displaystyle\text{subject to
}g_{i}(x)\leq 0,\quad\forall i\in\\{1,\dots,Q\\}$ (8)

for some $g_{i}$’s, where $g_{i}(x)$ represents the inequality constraints and
$Q$ is the number of constraints. The $i^{th}$ constraint is said to be active
if and only if $g_{i}(x)=0$. To be more specific, for $1\leq p<\infty$, we
have $Q=1$ and $g_{1}(x)=\norm{x-x_{s}}_{p}^{p}-\delta^{p}$; for $p=\infty$,
we have $Q=D$ and $g_{i}(x)=\absolutevalue{(x-x_{s})_{i}}-\delta$ for all
$i\in\\{1,\dots,D\\}$. The constraints are active in this case when
$x\in\partial B_{\ell_{p}(x_{s},\delta)}$ (boundary of the $\ell_{p}$ ball of
radius $\delta$ around $x_{s}$).

Let $\boldsymbol{J}(x)=(\dots,\mathbbm{1}_{\\{g_{i}(x)=0\\}},\dots)^{T}$ be a
$Q\times 1$ vector whose $i^{th}$ component represents whether the $i^{th}$
inequality constraint is active or not (1 or 0). $\boldsymbol{J}(x)$ induces
an indexing set $I(x)\subset\\{1,\dots,Q\\}$ for the active constraints.
Define $\boldsymbol{C}(x)=[(g_{i}(x))_{i\in I(x)}]$ to be the active
constraint matrix and $D\boldsymbol{C}(x)=[(\nabla g_{i}(x))_{i\in I(x)}]$ be
its corresponding derivative/sub-derivative matrix. A projection operator
which takes any vector to the surface defined by the active constraints (i.e.,
$\\{x:g_{i}(x)=0,\,\forall i\in I(x)\\}$) can be canonically defined as

$\boldsymbol{P}(x)=\boldsymbol{I}-D\boldsymbol{C}(x)^{T}(D\boldsymbol{C}(x)D\boldsymbol{C}(x)^{T})^{-1}D\boldsymbol{C}(x).$

Note when all constraints are inactive, $\boldsymbol{C}(x)$ is a null vector
and the projection reduces to the identity $\boldsymbol{P}(x)=\boldsymbol{I}$.

Consider a CDS $T^{pgf}_{x_{s}}$ on $\mathcal{X}=B_{p}(x_{s},\delta)$
parameterized by $x_{s}$ as a solution to the ODE:

$\dot{x}=\boldsymbol{P}(x)\nabla_{x}F(x).$ (9)

This can be viewed as a special case of the constraint optimization problems
discussed by [11].

Note that for $1\leq p<\infty$ as we have a single norm constraint
$g_{1}(x)=\norm{x-x_{s}}_{p}^{p}-\delta^{p}$,
$\boldsymbol{J}(x)=\mathbbm{1}_{g_{1}(x)=0}$ and

$\boldsymbol{P}(x)=\boldsymbol{I}-\boldsymbol{J}(x)(\norm{\nabla
g_{1}(x)}^{2}_{2})^{-1}\nabla g_{1}(x)\nabla g_{1}(x)^{T}.$ (10)

When the particle is at the boundary of the $\ell_{p}$ ball
$B_{p}(x_{s},\delta)$, i.e., $\boldsymbol{J}(x)=1$, the projection matrix is
just orthogonal to the normal vector to the surface of the $\ell_{p}$ ball.
thus, when the particle is at the boundary it doesn’t go beyond and explores
the boundary surface based on the gradient direction over the surface. The
dynamic stops once the gradient becomes parallel to the normal vector of the
surface, in other words, there is no direction left to explore which increases
the function $F$ further (on the surface). When the particle is inside the
$\ell_{p}$ ball it just follows the standard gradient direction.

For $p=\infty$, the $\ell_{p}$ ball is just a hyper-cube and
$\boldsymbol{J}(x)\neq\boldsymbol{0}$ indicates which sides/diagonal of the
cube the particle resides in. The ODE in this case is just:

$\dot{x}=\nabla_{x}F(x)\odot(\boldsymbol{1}-\boldsymbol{J}(x)),$ (11)

where $\odot$ is the element-wise product. The ODE for $p=\infty$ just says
that once we reach the boundary of the cube, we move only along the sides by
ignoring gradient components where the particle has attained side length
$\delta$. The path traversed by $T^{pgf}_{x}$ is also non-decreasing as
$\dot{F}(x)=\nabla F^{T}(x)\boldsymbol{P}\nabla F(x)\geq 0$, as
$\boldsymbol{P}$ is positive semi-definite being a projection.

####  2.2.4 Deflecting saddle points

One issue with $T^{pgf}_{x_{s}}$ is that it can’t distinguish between saddle
points (where $\nabla^{2}_{x}F(x)$ hessian is indefinite) and local maxima;
the continuous dynamic stops as long as (i) $\nabla F(x)=0$ or (ii) $x$ on the
surface of the $\ell_{p}$ ball and $\nabla F(x)$ is parallel to the normal
vector of the $\ell_{p}$ ball. We can modify (9) to traverse a dynamics which
doesn’t get stuck at the saddle points. Let
$S=\\{\eta:\nabla^{2}_{x}F(x)|_{x=\eta}\text{ is indefinite}\\}\subseteq
E=\\{x:\nabla{F(x)=0}\\}$ be the set of saddle points. We can add a
deterministic perturbation towards the unit eigenvector $\nu^{\eta}_{max}$
corresponding to the maximum eigenvalue of $\nabla^{2}_{x}F(x)|_{x=\eta}$ to
exclude the saddle points from being a stationary point. Therefore, we define
a CDS $\bar{T}^{pgf}_{x_{s}}$ on $B(x_{s},\delta)$ parameterized by $x_{s}$ as
a solution to the ODE:

$\dot{x}=\boldsymbol{P}(x)[\nabla F(x)+\sum_{\eta\in
S}\psi_{\epsilon}^{\eta}(x)\nu^{\eta}_{max}],$ (12)

where $\epsilon>0$ and
$\psi_{\epsilon}^{\eta}(x)=\exp{-\frac{1}{\epsilon^{2}-\norm{x-\eta}_{2}^{2}}}$
if $x\in{B}_{2}(\eta,\epsilon)$ and $\psi_{\epsilon}^{\eta}(x)=0$ elsewhere.
Essentially we are adding a smooth perturbation to the originally defined
projected gradient flow dynamics as it gets closer (within $\epsilon$ radius)
to any saddle point (deflection).

######  Remark.

Our goal is that $\bar{T}^{pgf}_{x_{s}}$ can retain all the local smoothness,
local optimum, and non-decreasing properties of $T^{pgf}_{x_{s}}$ with a
proper choice of $\epsilon$. Under certain regularity of $F$ (see; Theorem
2.1), there should exist some sufficiently small $\epsilon$, such that
$\psi_{\epsilon}^{\eta}(x)$ is a small-bump function, which is smooth and non-
negative everywhere. Near any saddle point $\eta\in S$, we have
$\langle\nu^{\eta}_{max},\nabla{F}(x)\rangle\geq 0$, which preserves the non-
decreasing trajectory of the original ODE. At a local maximum, all the
eigenvalues of $\nabla^{2}_{x}F(x)$ are $<0$, resulting in the ODE around
local maxima having no deflection term. Equilibrium is attained as long as
$\nabla F(x)=0$, preserving the local maximas from the original ODE.

We can now define an attack function as:

$\lambda^{pgf}(x,y)=\lim_{t\to\infty}\bar{T}^{pgf}_{x}(t)x-x.$ (13)

Our next theorem demonstrates that (13) is the best point-wise attack. More
importantly, by the nature of CDS, $\lambda^{pgf}(x,y)$ has certain regularity
(e.g., local smoothness) properties, i.e., it belongs to some perturbation
function class $\mathcal{F}^{p}_{\delta}$ consisting of regulated functions,
therefore, $\lambda^{pgf}(x,y)$ is also the  best function attack over this
particular $\mathcal{F}^{p}_{\delta}$. Details of this
$\mathcal{F}^{p}_{\delta}$ will be addressed in section 2.4.

######  Theorem 2.1.

Given $F(x)=\mathcal{L}(f(x),y)$ be locally $C^{2}$ almost surely, and the set
of critical points $E=\\{x:\nabla{F(x)=0}\\}$ be finite, non-degenerate with
any $a,b\in E$ satisfying $dist(a,b)\geq\delta$; choosing any
$0<\epsilon<\delta$ in (12), then $\lambda^{pgf}(x,y)$ in (13) is the best
point-wise attack of strength $\delta$.

The proof relies on showing that $x_{adv}=\lambda^{pgf}(x,y)+x$ satisfies the
KKT (Karush–Kuhn–Tucker) conditions and the SOSC (second order sufficient
condition) for the constraint optimization (8).

###  2.3 Discretization of the best attack

Equation (13) is a construction of an ideal/best $\ell_{p}(\delta)$ point-wise
attack function for a given loss $F(x)=\mathcal{L}(f(x),y)$. The underlying
CDS $\bar{T}^{pgf}_{x}$ used in construction for this attack utilizes the
information related to the saddle points of $F(x)$ (12). In practice, we
usually have no access to the saddle points or the eigenvalues associated with
them; that itself is a challenging optimization problem especially when $f(x)$
is characterized by deep neural networks.

Note that the terms $\boldsymbol{P}(x)\sum_{\eta\in
S}[\psi_{\epsilon}^{\eta}(x)\nu^{\eta}_{max}]$ were added to the original
projected gradient flow dynamics $T^{pgf}_{x}$ (9) to account for deflection
around saddle points, so that the dynamic doesn’t get stuck in one of such
points. For our purpose, we were interested in showing the existence of an
ideal attack using such artificial construction. The key point was that such a
dynamic can locally solve the unconstrained optimization problem (8). In real
life, one can achieve an equivalent effect with very high probability by
introducing stochastic noise to the original projected gradient flow dynamics
(9). This leads to an ODE of the underlying dynamics being a stochastic
differential equation: $dx(t)=\boldsymbol{P}(x(t))[\nabla F(x(t))+2dB(t)]$
(where $B(t)$ is a Brownian motion). It is well known that introducing
stochasticity in the original dynamics, helps us solve the issue of getting
stuck in saddle points almost surely. This fact has been illustrated in [10,
32, 42, 24].

So the core component dictating the dynamic system is the term
$\dot{x}=\boldsymbol{P}(x)\nabla F(x)$ accompanied by a deflection term or
noise term to avoid saddle points. If we consider the discrete time step
version of the ODE based on the core component we get:

$x^{t+1}=\Pi(x^{t}+\gamma\nabla F(x^{t})),$ (14)

where $\gamma$ is the step-size and the operator $\Pi$ is (discrete) analogous
to $\boldsymbol{P}(x)$ which is a (continuous) projection to the $\ell_{p}$
ball of radius $\delta$ around $x^{0}$ (initial point). This is a projected
gradient-ascent algorithm derived from the underlying ODE (9). Note that to
eliminate the possibility that the process (14) is stuck at a saddle point,
one can always inject noise into it by replacing $\nabla F$ with its
stochastic version (e.g., stochastic gradient descent). In general, the
discretization can be characterized by any projected- steepest ascent
algorithm of the form:

$x^{t+1}=\Pi(x^{t}+\gamma\vec{d}),$ (15)

where $\vec{d}$ is the steepest ascent direction. The steepest ascent
direction $\vec{d}$ can be attributed as a unit vector with respect to
$\norm{}_{p}$ norm which is maximal along the gradient direction. [3] explores
and gives justification for these various steepest ascent directions. Steepest
ascent w.r.t. $\norm{\cdot}_{2}$ norm gives $\vec{d}\propto\nabla F$ which
reduces to (14). Steepest ascent w.r.t. $\norm{\cdot}_{1}$ gives us
$\vec{d}\propto\nabla F_{i_{max}}\cdot\boldsymbol{e}^{i_{max}}$ which is
essentially a coordinate ascent update step ($i_{max}=\arg\max_{i}(\nabla
F)_{i}$, $\boldsymbol{e}^{i}$ is the $i^{th}$ standard basis vector in
$\mathbbm{R}^{D}$). Steepest ascent w.r.t. $\norm{}_{\infty}$ implies
$\vec{d}\propto\text{sign}(\nabla F)$ which is a signed gradient update step.
In $\mathbbm{R}^{D}$, all the norms are equivalent and all of these steepest
ascent algorithms will generally enjoy the same convergence rate [3].

######  Remark (PGD and FGSM attack as discretization of the best attack).

If we consider the steepest ascent direction w.r.t. $\norm{\cdot}_{\infty}$,
$\vec{d}\propto\text{sign}(\nabla F)$, then the discrete time step updates for
our ODE (9) becomes:

$x^{t+1}=\Pi(x^{t}+\gamma\,\text{sign}\nabla F(x^{t})).$ (16)

This is essentially the projected gradient descent attack proposed in the
eminent paper [29]. As $\gamma\to 0$ the discrete dynamics converge to the
continuous dynamics. In real life, as the PGD updates are done on batches of
data, the discrete dynamics inherently include a noise term due to random
batch selection of data, which helps us deflect the saddle points.

Also, when the step size $\gamma=\delta$, then there is essentially only one
update step $t=0$ and we get $x=x^{0}+\delta\,\text{sign}\nabla F(x^{0})$.
This is equivalent to the FGSM attack proposed in [16]. We can now understand
why the FGSM turns out to be the best $\ell_{p}(\delta)$ function attack for
linear models 2.1; for linear models, the FGSM is exact and equivalent to (2)
as the gradient direction is constant.

###  2.4 Motivation for piece-wise Hölder spaces

Theorem 2.1 guarantees the existence of a $\ell_{p}(\delta)$ function attack,
now the natural next step is to define a perturbation function class to which
such a function attack belongs. Once we define such a function class, we aim
to show it can be approximated by neural networks with arbitrary accuracy and
as a consequence, we can emulate the best function attack (13) using neural
networks.

In section 2.2.2, it was discussed that $T^{gf}$ induces a partition of the
underlying metric space into stable sets $\mathcal{X}=\bigsqcup_{x_{0}\in
E}W_{s}(x_{0})$. If $T^{gf}$ is $C^{k}$ smooth in $W_{s}(x_{0})$ w.r.t. $x$,
then this will induce smoothness in $\bar{T}^{pgf}_{x}$ (12) and
$\lambda^{f}(x,y)$ defined in (2) up to certain singularities.
$\lambda^{pgf}(x,y)$ can be seen as local projection of $T^{gf}$ characterised
by $\boldsymbol{P}(x)$, which inherits smoothness properties of $T^{gf}$
almost everywhere.

######  Lemma 2.2.

Let $\nabla F$ be $C^{k}$ smooth w.r.t. $x\in\bigsqcup_{x_{0}\in
E}W^{\mathrm{o}}_{s}(x_{0})$ then, $\lambda^{pgf}(x,y)$ is $C^{k}$ smooth
w.r.t. $x\in\bigsqcup_{x_{0}\in E}W^{\mathrm{o}}_{s}(x_{0})$ for all $p$,
where $W^{\mathrm{o}}$ denotes the interior of the set $W$.

As we are dealing with compact spaces ($x\in[0,1]^{D}$), $C^{k}$ smoothness
will imply belonging to a Hölder space (Definition A.7) w.r.t. $x$. We can
consider the space of piece-wise Hölder function space to describe
$\lambda^{f}(x,y)$ where the pieces are characterized by the singularities
(Boundaries $\partial W_{s}(x_{0});x_{0}\in E$).

##  3 Piece-wise Hölder function and its approximation

######  Definition 3.1.

Let $\boldsymbol{A}=\\{A_{i}\\}$ be any disjoint partition of the domain space
$\cal{X}$. i.e, $\mathcal{X}=\bigsqcup_{i}A_{i}$. Then a function
$h:\mathbb{R}^{D}\to\mathbb{R}$ belongs to
$\bar{\mathcal{H}}(\omega,\mathcal{X})$, a piece-wise Hölder function class
iff for some $\boldsymbol{A}$, the restriction of the function $h$ to any
piece $A_{i}\in\boldsymbol{A}$, denoted by $h_{A_{i}}$, belongs to
$\mathcal{H}(\omega,A_{i})$ (Definition A.7).

Based on Section 2.4, we would like to consider the perturbation function
class (Definition 1) as
$\lambda^{f}(x,y)\in\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})=\mathcal{F}^{p}_{\delta}(\bigotimes_{i=1}^{D}\bar{\mathcal{H}}(\omega_{i},\mathcal{X}))$
(where $\bigotimes$ denotes the product space). For the sake of notational
convenience we will denote
$\bar{\mathcal{H}}(\omega^{*},D,\mathcal{X})\coloneqq\bigotimes_{i=1}^{D}\bar{\mathcal{H}}(\omega_{i},\mathcal{X})$
where $\omega^{*}=\min\\{\omega_{i}\\}$.

There has been a convincing argument to use
$\tilde{\mathcal{C}}=\bar{\mathcal{H}}(\omega^{*},D,\mathcal{X})$, but the way
we defined $\lambda^{f}(x,y)$(13) won’t have a closed-form expression. Hence,
we would like to use some closed-form parametric family of functions to
emulate the perturbation function class where the best attack function
resides.

We can use a family of Relu neural networks (Definition 1.1) to approximate
our perturbation function class with arbitrary accuracy up to a small
measurable set $\nu$. Theorem 3.1 shows that using a sufficiently wide network
one can achieve arbitrarily small approximation error.

######  Definition 3.2 (Asymptotic notation).

For any two real functions a,b:

  * •

$a\prec b$ or $a=\mathcal{O}(b)$ denotes there exists a positive constant
$0<C<\infty$ such that $\absolutevalue{a}\leq C\absolutevalue{b}$.

  * •

$a\succ b$ or $a=\Omega(b)$ denotes there exists a positive constant
$0<C<\infty$ such that $\absolutevalue{a}\geq C\absolutevalue{b}$

  * •

$a\asymp b$ or $a=\Theta(b)$ iff $a\prec b\prec a$.

  * •

Consider two real sequences $a_{n},b_{n}$ then $a_{n}=o_{\mathbb{P}}(b_{n})$
denotes that $\frac{a_{n}}{b_{n}}$ converges to 0 in probability.

######  Theorem 3.1.

Let $\mu$ be a probability measure on the space $\mathcal{X}$. For any
$h\in\bar{\mathcal{H}}(\omega^{*},D,\mathcal{X})$ and
$\mathcal{X}_{s}=Supp(\mu)\subset\mathcal{X}$ with
$\dim_{M}(\mathcal{X}_{s})=d$ (see; Definition A.9). Then given $W\geq
c_{1}\epsilon^{-\frac{d}{\omega^{*}}},w\geq
c_{2}\epsilon^{-\frac{d}{\omega^{*}}},\kappa\geq
c_{3}\epsilon^{-c_{4}},L=c_{5}$ and a measurable set $\nu$ with
$\mu(\nu)=\mathcal{O}(\epsilon^{\frac{1}{\omega^{*}}})$, there exists a neural
network $\hat{h}$ such that:

$\inf_{\hat{h}\in\mathcal{F}_{\sigma}(L,W,w,\kappa)}\sup_{x\in\mathcal{X}_{s}\setminus\nu}||\hat{h}(x)-h(x)||_{\infty}\leq\epsilon,$
(17)

where $c_{1},c_{2},c_{3},c_{4},c_{5}>0$ are some large enough constants
independent of $\epsilon$ .

######  Corollary 3.2.

For any $h\in\bar{\mathcal{H}}(\omega^{*},D,\mathcal{X})$ with
$\mathcal{X}_{s}=Supp(\mu)\subset\mathcal{X}\,,\dim_{M}(\mathcal{X}_{s})=d$,
there exists $\hat{h}\in\mathcal{F}_{\sigma}(L,W,w,\kappa)$ with sufficiently
large $\kappa$ and depth $L$ such that:

$\sup_{x\in\mathcal{X}\setminus\nu}\norm{\hat{h}(x)-h(x)}_{\infty}=\mathcal{O}\left(\min(W,w)^{-\omega^{*}/d}\right),$
(18)

where $\mu(\nu)=\mathcal{O}\left(\min(W,w)^{-1/d}\right)$. Furthermore, if
$h\in\bigotimes_{i}\mathcal{H}({\omega}_{i},\mathcal{X})$, then $\mu(\nu)=0$.

###### Proof.

Representing $\epsilon$ in terms of the width $w$ and number of non-zero
parameters $W$ we get the above result. Also, when
$h\in\prod_{i}\mathcal{H}({\omega}_{i},\mathcal{X})$ is just product space of
Hölder functions without any pieces, we don’t require the measurable set $\nu$
to bound the error. As in the proof of Theorem 3.1, $\nu$ arises as a
consequence of covering the boundary of pieces in a piece-wise Hölder
function. ∎

Theorem 3.1 and corollary 3.2 justifies the existence of a Relu neural net
which can approximate the best $\ell_{p}(\delta)$ function attack
$\lambda^{f}(x,y)$ as defined in (13). The approximation error $\epsilon$
decays based on the number of non-zero parametres, the width $W$, $w$ of the
network. The decay rate is controlled by $\omega^{*}/d$ which makes sense as
the smoothness $\omega^{*}$ increases the function is easier to approximate;
inversely it is harder to approximate as the intrinsic dimension $d$ of the
input space increases.
Similar observations can be made about the measure of $\nu$; whose decay rate
only depends on the dimension $d$, not the smoothness.

##  4 Convergence of Adversarial training

Let $f^{*}$ be the robust ($p$,$\delta$) model (4), this is the true robust
model in some arbitrary function space $\mathcal{C}$. We would like to study
how the empirical estimate of $\widehat{f}_{n}\in\mathcal{C}_{n}$ w.r.t sample
size $n$ converges to $f^{*}$. Corresponding to any $f\in\mathcal{C}$ we also
have the best $\ell_{p}(\delta)$ function attack
$\lambda^{f}(x,y)\in\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ which
maximises the adversarial loss (2). For notation convenience now on wards
denote $\lambda^{f}\coloneqq\lambda^{f}(x,y)$ for any model $f$; also
$\Lambda\coloneqq\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})$ original
function space of attacks. Adversarial training to find the robust
$(p,\delta)$ model $f^{*}$ is the sequential mini-max problem:

$\displaystyle\lambda^{f}$
$\displaystyle=\arg\max_{\lambda\in\Lambda}\mathbbm{E}\mathcal{L}(f,\lambda,\mathcal{Z}),\quad\forall
f\in\mathcal{C},$ $\displaystyle f^{*}$
$\displaystyle=\arg\min_{f\in\mathcal{C}}\mathbbm{E}\mathcal{L}(f,\lambda^{f},\mathcal{Z}).$

In order to find the empirical estimator $\widehat{f}_{n}$ of the above
sequential mini-max we can restrict the function spaces to
$\mathcal{C}_{n},\Lambda_{n}$ and optimize the empirical adversarial loss such
that:

$\displaystyle\widehat{\lambda}^{f}_{n}\in\Lambda_{n}:\mathbbm{E}_{n}\mathcal{L}(f,\widehat{\lambda}^{f}_{n},\mathcal{Z})$
$\displaystyle\geq\sup_{\lambda\in\Lambda_{n}}\mathbbm{E}_{n}\mathcal{L}(f,\lambda,\mathcal{Z})-\eta_{n},\quad\forall
f\in\mathcal{C}$ (19)
$\displaystyle\widehat{f}_{n}\in\mathcal{C}_{n}:\mathbbm{E}_{n}\mathcal{L}(\widehat{f}_{n},\widehat{\lambda}_{n}^{\widehat{f}_{n}},\mathcal{Z})$
$\displaystyle\leq\inf_{f\in\mathcal{C}_{n}}\mathbbm{E}_{n}\mathcal{L}(f,\widehat{\lambda}^{f}_{n},\mathcal{Z})+\bar{\eta}_{n}.$
(20)

$\mathbbm{E}_{n}$ is just the empirical expectation over the observed
$n$-sample data $\\{(x_{i},y_{i})\\}_{i=1}^{n}$,
$\widehat{\lambda}^{f}_{n},\widehat{f}_{n}$ are empirical etimators of
$\lambda^{f},f^{*}$ respectively. Notice that
$\widehat{\lambda}^{f}_{n},\widehat{f}_{n}$ might not reach the supremum and
infimum respectively w.r.t. the adversarial loss exactly but are very close to
it, up to some small error values $\eta_{n},\bar{\eta}_{n}$. This is done, as
$\mathcal{C}_{n},\Lambda_{n}$ (Sieve-spaces [19]) might not be closed in
general.

#### Zero-Sum game and Nash condition

In the real-life implementation, the above mini-max optimization faces
practical bottlenecks due to equation (19) as we need to find
$\widehat{\lambda}^{f}_{n}$ for all possible $f\in\mathcal{C}$ then proceed to
minimization problem (20). Fortunately, the adversarial training framework is
a special form of mini-max optimization.

Let $V=\mathbbm{E}\mathcal{L}(f,\lambda,\mathcal{Z})$, then a robust model is
trying to minimize $V$ and a $\ell_{p}(\delta)$ attack is trying to minimize
$-V$. This sort of mini-max optimization is known as a Zero-Sum game [1]. A
classical result in game theory is that Nash equilibrium is attained at the
solution of a zero-sum mini-max optimization. Hence, an equivalent
optimization scheme to (19),(20) based on empirical Nash condition will be as
follows:

$\displaystyle\widehat{\lambda}_{n}\in\Lambda_{n}:\mathbbm{E}_{n}\mathcal{L}(\widehat{f}_{n},\widehat{\lambda}_{n},\mathcal{Z})$
$\displaystyle\geq\sup_{\lambda\in\Lambda_{n}}\mathbbm{E}_{n}\mathcal{L}(\widehat{f}_{n},\lambda,\mathcal{Z})-\eta_{n}$
(21)
$\displaystyle\widehat{f}_{n}\in\mathcal{C}_{n}:\mathbbm{E}_{n}\mathcal{L}(\widehat{f}_{n},\widehat{\lambda}_{n},\mathcal{Z})$
$\displaystyle\leq\inf_{f\in\mathcal{C}_{n}}\mathbbm{E}_{n}\mathcal{L}(f,\widehat{\lambda}_{n},\mathcal{Z})+\widetilde{\eta}_{n}$
(22)

The above scheme is like a solution to a two-player game where the best robust
model is minimization of the loss w.r.t. the best attack and the best attack
itself is maximization of the loss w.r.t. the best robust model. The Nash
equilibrium formulation is useful when we do adversarial training in practice;
instead of exploring the whole parameter/function space we just iteratively
find the best attack given a model and then robustly train the model given the
best attack and continue the process until we reach equilibrium.

#### Convergence rate

We will state convergence results on the expected difference in loss based on
the empirical estimate $\widehat{f}_{n}$ and $f^{*}$; also
$\widehat{\lambda}^{f}$ and $\widehat{\lambda}_{n}^{f}$ for any $f$ with
respect to the sample size $n$. Also, we assume that the original parameter
space for the model is a product of Hölder space i.e.
$f\in\mathcal{C}=\prod_{i}^{K}\mathcal{H}(\bar{\omega}_{i},\mathcal{X})$ with
smoothness $\bar{\omega}^{*}=\min\\{\bar{\omega}_{i}\\}_{i=1}^{n}$.

######  Theorem 4.1 (Adversarial training rates).

Let $\mathcal{C}=\prod_{i}^{K}\mathcal{H}(\bar{\omega}_{i},\mathcal{X})$ and
$\Lambda=\mathcal{F}^{p}_{\delta}(\bar{\mathcal{H}}(\omega^{*},D,\mathcal{X}))$,
and we assume that $\Lambda,\mathcal{C}$ are compact under
$\|\cdot\|_{\infty}$. For all $\lambda,\lambda^{\prime}\in\Lambda,\
f,f^{\prime}\in\mathcal{C}$, assume the following conditions hold:

  * •

A0: Assume that $f^{*}\in\mathcal{C}$ with support
$\bar{\mathcal{X}}_{s}\subset[0,1]^{D}$ with
$\operatorname{dim}_{M}\bar{\mathcal{X}}_{s}=\bar{d}^{*}\leq D$ (see Def. A.9
and A.7), and that $\\{\lambda_{*}^{f}:f\in\mathcal{C}\\}\subset\Lambda$ on
support ${\mathcal{X}_{s}}\subset[0,1]^{D}$ with
$\operatorname{dim}_{M}{\mathcal{X}_{s}}=d^{*}\leq D$.

  * •

A1: The loss is Lipschitz continuous in $f$ and $\lambda$,

$\mathcal{L}(f,\lambda,\mathcal{Z})-\mathcal{L}(f^{\prime},\lambda^{\prime},\mathcal{Z})\prec\|f-f^{\prime}\|_{\bar{\mathcal{X}}}+\|\lambda-\lambda^{\prime}\|_{{\mathcal{X}}},$

where $\norm{}_{\mathcal{X}},\norm{}_{\tilde{\mathcal{X}}}$ are the supremum
norms over the supports $\mathcal{X},\mathcal{\tilde{\mathcal{X}}}$.

  * •

A2: The variance of the loss difference is bounded by its expectation,
specifically in terms of $f$ as follows:

$\mathbb{V}[\mathcal{L}(f,\lambda^{f},\mathcal{Z})-\mathcal{L}(f^{*},\lambda^{f^{*}},\mathcal{Z})]\prec\mathbb{E}[\mathcal{L}(f,\lambda^{f},\mathcal{Z})-\mathcal{L}(f^{*},\lambda^{f^{*}},\mathcal{Z})]\prec\|f-f^{*}\|^{2}_{\widetilde{{\mathcal{X}}}}$

for any $\widetilde{{\mathcal{X}}}\subset\bar{\mathcal{X}}_{s}$.

  * •

A3: The variance of the loss difference is bounded by its expectation,
specifically in terms of $\lambda$ as follows:

$\mathbb{V}[\mathcal{L}(f,\lambda^{f},\mathcal{Z})-\mathcal{L}(f,\lambda,\mathcal{Z})]\prec\mathbb{E}[\mathcal{L}(f,\lambda^{f},\mathcal{Z})-\mathcal{L}(f,\lambda,\mathcal{Z})]\prec\|\lambda^{f}-\lambda\|^{2}_{\widetilde{{\mathcal{X}}}}+\mathbb{P}^{2\omega^{*}}(x\not\in\widetilde{\mathcal{X}})$

for any $\widetilde{{\mathcal{X}}}\subset{\mathcal{X}}_{s}$.

Pick any two values
$\bar{r}>\underline{r}\geq\left(\frac{d^{*}}{\omega^{*}}\vee\frac{\bar{d}^{*}}{\bar{\omega}^{*}}\right)$.
Consider estimators $\widehat{f}_{n},\widehat{\lambda}_{n}^{f}$ in equations
(19),(20) with $\eta_{n},\bar{\eta}_{n}=o_{\mathbb{P}}(n^{-2/(2+\bar{r})})$
where $\Lambda_{n}=\mathcal{F}_{\sigma}(L,W_{n},w_{n},\kappa_{n})$ and
$\mathcal{C}_{n}=\mathcal{F}_{\sigma}(\bar{L},\bar{W}_{n},\bar{w}_{n},\bar{\kappa}_{n})$
implement neural networks (cf. Definition 1.1) satisfying
$W_{n},\bar{W}_{n},w_{n},\bar{w}_{n}\asymp
n^{\underline{r}/(\underline{r}+2)}$ and $\kappa_{n},\bar{\kappa}_{n}\asymp
n^{c}$ for any large enough choices of $L,\bar{L},c>0$. Then:

$\mathbb{E}[\mathcal{L}(\widehat{f}_{n},\lambda^{\widehat{f}_{n}},\mathcal{Z})-\mathcal{L}(f^{*},\lambda^{f^{*}},\tilde{\mathcal{Y})}]=o_{\mathbb{P}}(n^{-2/(2+\bar{r})}),$
$\sup_{f\in\mathcal{C}_{n}}\mathbb{E}[\mathcal{L}(f,\lambda^{f},\mathcal{Z})-\mathcal{L}(f,\widehat{\lambda}_{n}^{f},\mathcal{Z})]=o_{\mathbb{P}}(n^{-2/(2+\bar{r})}).$

Hence, $d(\widehat{f}_{n},f^{*})=o_{\mathbb{P}}(1)$ for any (pseudo-)norm
$d(\cdot,\cdot)$ under which
$\mathbb{E}[l(f,\lambda^{f},\tilde{\mathcal{Y})}]$ is compact and continuous.
Further, if
$d(f,f^{*})^{1/q}\prec\mathbb{E}[\mathcal{L}(f,\mathcal{Z})-\mathcal{L}(f^{*},\mathcal{Z})]$
for $q>0$, we get:

$d(\widehat{f}_{n},f^{*})=o_{\mathbb{P}}(n^{-2q/(2+\bar{r})}).$

We have the following remarks regarding the assumptions in the above theorem.

######  Remark.

$A_{0}$ is a trivial assumption ensuring that our robust model $f^{*}$ belongs
to a product space of Hölder continuous functions. This is a reasonable
assumption for regression/classification problems in the deep learning realm.
Also, the best attack $\lambda^{f}$ for any $f\in\mathcal{C}$ belongs to the
product space of piece-wise Hölder functions; this is supported by our
discussions in section 2.4. $A1$ enforces Lipschitz continuity for our
adversarial loss $\mathcal{L}(f,\lambda,\mathcal{Z})$ w.r.t. $\lambda$ and
$f$. $A2,A3$ suggests that the variance and mean of difference in adversarial
loss can be controlled by the difference of the underlying parameters. In
$A3$, we have the extra term
$\mathbb{P}^{2\omega^{*}}(x\not\in\widetilde{\mathcal{X}})$. This will be used
to account for the small measure set where our neural network can’t
approximate the attack well (Refer Theorem 3.1). That is, we will let
$\widetilde{\mathcal{X}}$ be the measurable set where approximation fails and
$\omega^{*}$ is the smoothness factor for piece-wise Hölder function space.

##  5 Numerical Experiments

As discussed earlier the sequential mini-max optimization of our adversarial
loss (19)(20) is a zero-sum game and must reach the Nash-equilibrium at the
optimum (21)(22). Empirically we can reach such an equilibrium by emulating
the adversarial Zero-sum game between the estimators of the robust model $f$
(4) and corresponding best attack $\lambda^{f}$ (2).

Motivated by this, given a sample of $N$ data points we train two neural
networks $f,\lambda^{f}$ with parameters $\theta_{f},\theta_{\lambda}$;
competing against each other until convergence or Nash-equilibrium is reached
(Algorithm: 1). $T$ is the number of training epochs; $P$ represents the
number of iterations the model $f$ is trained in each epoch; correspondingly
$H$ is the number of iterations $\lambda^{f}$ is trained in one epoch;
$\tilde{\gamma},\bar{\gamma}$ are the learning rates for $f,\lambda^{f}$. At
each training epoch, $f$ is optimized in order to minimize the adversarial
loss given the current state of $\lambda^{f}$; and $\lambda^{f}$ maximizes the
adversarial loss (minimizes negative adversarial loss) given the current state
of $f$. This is in a similar flavor to the training of general adversarial
networks (GANs) [15], where the discriminator plays an analogous role to our
robust model $f$ and the generator is analogous to the attack model
$\lambda^{f}$ in our scenario.

Algorithm 1 Adversarial Training

Initialize:

$t\leftarrow 0,h\leftarrow 0,p\leftarrow 0$. Each entry of
$\theta_{f},\theta_{\lambda}\sim^{iid}\mathcal{U}(-\sqrt{\frac{1}{\texttt{in\\_features}}},\sqrt{\frac{1}{\texttt{in\\_features}}})$,
where in_features means the width of the previous layer in the network.

while $t\leq T$ do

while $p\leq P$ do

$\theta_{f}\leftarrow\theta_{f}-\tilde{\gamma}\nabla_{\theta_{f}}\sum_{i=1}^{n}\mathcal{L}(f,\lambda^{f},(x_{i},y_{i}))$
$\triangleright$ Can be any gradient-based optimizer, e.g., SGD, ADAM, etc

$p\leftarrow p+1$

end while

while $h\leq H$ do

$\theta_{\lambda}\leftarrow\theta_{\lambda}+\bar{\gamma}\nabla_{\theta_{\lambda}}\sum_{i=1}^{n}\mathcal{L}(f,\lambda^{f},(x_{i},y_{i}))$

$h\leftarrow h+1$

end while

$p\leftarrow 0,h\leftarrow 0,t\leftarrow t+1$

end while

We apply the adversarial framework in both classification and regression
settings. For the classification setting, we use the two-dimensional geometric
datasets (see; Appendix D and Figure 6); we visually evaluate the consistency
of the learned attack network with respect to the theoretical best attack (13)
based on projected gradient flow. We also use the number of misclassifications
and adversarial loss to evaluate the robustness, and attack strength of
$f,\lambda^{f}$ respectively. For the regression setting, we use the (Boston)
[21], (Diabetes) [5] datasets; we evaluate adversarial loss on the test
dataset as a performance metric.

### Classification

We implement algorithm 1 with $T=100,H=1,P=1$ and
$\tilde{\gamma}=10^{-3},\bar{\gamma}=2\times 10^{-4}$ for all the
classification datasets. We use $\delta=0.2$ (attack strength) and
$\ell_{p}:p=2,\infty$ for our experiment. When $\delta$ is big, the so-called
robust overfitting might occurs, and optimization results may not be
satisfactory, and more discussion about it can be found in Section 6. For all
feasible values of $\delta$, the analysis remains the same. Furthermore, the
$\ell_{p}$ constraint on the attack network $\lambda^{f}$ is implemented in
the forward pass through learned scaling (between 0 and 1) and normalization.
Architecture and implementation details can be found in Appendix D. We use the
multinomial negative loglikelihood or the cross-entropy loss as our loss
function $\mathcal{L}(f(x),y)=\sum_{j=0}^{C-1}\mathbbm{1}_{y=j}\log{\rm
Softmax}(f(x))_{j}$; the corresponding adversarial loss is then
$\mathcal{L}(f,\lambda^{f},(x,y))=\mathcal{L}(f(x+\lambda^{f}(x,y)),y)=\sum_{j=0}^{C-1}\mathbbm{1}_{y=j}\log{\rm
Softmax}(f(x+\lambda^{f}(x,y)))_{j}$. Here, $C$ is the number of classes.

(a) Clean Training

(b) $\ell_{2}(0.2)$

(c) $\ell_{\infty}(0.2)$

Figure 1: (a) Clean trained model loss, the red arrows represent the gradient
direction of the loss at each point. (b) Adversarially trained model based on
algorithm 1 with $\norm{\lambda^{f}}_{2}\leq 0.2$. (c) Adversarially trained
model based on algorithm 1 with $\norm{\lambda^{f}}_{\infty}\leq 0.2$. For
figures (b) and (c); [Left]: Red arrows represent the gradient of the
adversarially trained model loss. [Right]: Purple arrows represent the attack
generated by $\lambda^{f}$. The contour colors represent the value of the
corresponding loss at each point.

#### Gradient flow and Neural Network attack direction

Figure 1(a), shows the loss surface and gradient direction
$\nabla_{x}\mathcal{L}(f_{clean}(x),y))/\|\nabla_{x}\mathcal{L}(f_{clean}(x),y))\|$
corresponding to $x$’s on a grid, where the response label $y$ is imputed by
model $f_{clean}$, which achieves almost 100% accuracy and is viewed as an
oracle. Here $f_{clean}$ is the clean model trained to minimize the standard
loss
($f_{clean}=\arg\min_{f\in\mathcal{C}_{n}}\mathbbm{E}_{n}\mathcal{L}(f(x),y)$)
without any adversarial perturbation. The higher loss regions correspond to
the estimated decision boundary (EDB) of the dataset; this is consistent as
the loss is locally maximized when any pair of classes have approximately
equal probability.

Figure 1(b) shows the loss surface, gradient direction, and learned attack
direction of $\lambda^{f}$ for the adversarially trained $\ell_{2}(0.2)$
robust model $f$ based on Algorithm 1. As discussed in Section 2.2.3, (13) is
the best theoretical attack. Ignoring the deflection term for saddle points,
the underlying ODE is dictated by a projected gradient flow (9, 10). For
$p=2$, the projected gradient flow projects the original gradient flow onto
local spheres. Due to the smoothness of spheres in every direction, we expect
a flow visually similar to the original gradient flow. This is what we see in
figure 1(b), where $\nabla_{x}\mathcal{L}(f(x),y)$ (left) and $\lambda^{f}$
(right) are essentially the same. This also corroborates the approximation
capability of neural network for piece-wise Hölder function space (Theorem
3.1) where the theoretical best attack resides.

Figure 1(c) is the $\ell_{\infty}(0.2)$ case of the prior discussion. Unlike
the $\ell_{2}$ case, for $\ell_{\infty}$, the projected gradient flow projects
the gradient trajectory onto local cubes, which are not smooth in all
directions. The gradient flow dynamic continues after reaching the boundary
and gets projected onto the sides/diagonals of a cube (11). This is consistent
with Figure 1(c) where $\nabla_{x}\mathcal{L}(f(x),y)$ (left) is more smooth,
but $\lambda^{f}$ (right) is restricted only to diagonal directions.

Subsequently, comparing the adversarially trained EDB with clean trained EDB
we see that the EDB is wider after adversarial training which essentially
induces the robustness in the model. Also, due to the prior projection
arguments $\ell_{2}$ adversarial training preserves the geometry of the EDB
while $\ell_{\infty}$ projects the original EDB onto local cubes, making it
more blocky; this phenomenon is most prominent for the circles dataset where
EDB transforms from a circle ($\ell_{2}$) to a square ($\ell_{\infty}$) as
expected.

Figure 2: (Classification setting) Test Loss vs training epochs for
adversarial training based on Algorithm 1. Where $f$ is our adversarially
trained classifier and $f_{PGD}$ PGD trained robust classifier. For the
attacks: $\lambda^{f}$ represents adversarially trained neural network attack
based on $f$ (semi-white box); $\lambda_{PGD}$ represents (white-box) PGD
attack; $\lambda_{FGSM}$ represents (white-box) FGSM attack.
In the legends the combination $(f,\lambda_{PGD})$ represents the empirical
loss $\sum_{i=1}^{n_{test}}\mathcal{L}(f,\lambda_{PGD},(x_{i},y_{i}))$ when
the PGD attack $\lambda_{PGD}$ is performed on the adversarially trained
defense $f$, similarly $(f_{PGD},\lambda_{PGD})$ represents the empirical loss
$\sum_{i=1}^{n_{test}}(f_{PGD},\lambda_{PGD},(x_{i},y_{i}))$ when
$\lambda_{PGD}$ attack is performed on $f_{PGD}$; and so on. Figure 3:
Percentage of mis-classified test labels vs training epochs for adversarial
training based on Algorithm 1. The notation and legend in the plots follow
Figure 2.

#### Comparison with PGD attacks and PGD trained robust classifer

In section 2.3 we discussed how PGD attack (16) [29] is just a discretization
of the theoretical best possible attack (13). With small enough step-size
$\gamma$ we can treat PGD attack as a baseline (i.e., discrete approximation
of best attack), for notational convenience we will denote $\lambda_{PGD}$ as
the PGD attack. Similarly, $\lambda_{FGSM}$ denotes the FGSM attack mentioned
in [16] which is just PGD attack with $\gamma=\delta$ and a single iteration
step. We train $f_{PGD}$ which aims to minimize the PGD-based adversarial loss
$\mathbbm{E}_{n}\mathcal{L}(f(x+\lambda_{PGD}),y)$, this is the traditional
way of adversarial training mentioned in [29]. In our framework, the attack
generation itself is approximated by a neural network $\lambda_{f}$ rather
than a gradient-based method, and the adversarial training becomes a
mathematical game between $f$ and $\lambda_{f}$. The significance of $f_{PGD}$
is that with small step-size $\gamma$ for PGD attack generation, it will act
as a baseline for our version of adversarial training.

Figures 2 and 3 show the evaluated adversarial loss and misclassification rate
for all attack-defense combinations on the test data as we progress through
adversarial training. For all the datasets we see that the adversarial loss
for our robust network $f$ with attacks
$\lambda^{f},\lambda_{PGD},\lambda_{FGSM}$ converge to their respective
$f_{PGD}$ counter-parts. The loss that our framework deals with is
corresponding to the $(f,\lambda^{f})$ pair (solid red line) and the baseline
would be $(f_{PGD},\lambda_{PGD})$ (dashed green line). For the streaks
dataset there seems to be a gap between PGD defense $f_{PGD}$ against FGSM
attack $\lambda_{FGSM}$ and PGD attack $\lambda_{PGD}$; we see that our
adversarially trained attack $\lambda^{f}$ tries to match $\lambda_{FGSM}$
attack on $f_{PGD}$. On the other hand our defense $f$ tries to match the loss
levels of $f_{PGD}$ defense against its own $\lambda_{PGD}$ attack. Comparing
the solid curves (defense model $f$) with non-solid curves (defense model
$f_{PGD}$), our defense model has a lower loss under the same attack,
indicating its higher adversarial robustness.

For the misclassification rate, we see that, for circles,streaks datasets, $f$
shows stronger defense for all types of attacks compared to $f_{PGD}$ but the
attack strength of $\lambda^{f}$ is weaker compared to $\lambda_{PGD}$. For
moon the opposite happens where the $\lambda^{f}$ shows misclassifications
comparable to $\lambda_{PGD}$ but the defense $f$ is a bit weaker than
$f_{PGD}$ but still competitive. For polynomials, our defense $f$ performs
better against $\lambda_{FGSM}$ compared to $f_{PGD}$, but $f_{PGD}$ is a bit
better to defend against $\lambda_{PGD}$. This is not that shocking as
$f_{PGD}$ should perform well against $\lambda_{PGD}$ as it is adversarially
trained over it. To comment on the differences between PGD and our method, we
note that our attack/defense model is trained solely based on loss values,
while the implemented PGD algorithm in our simulation combines the loss value
and misclassification. 111PGD, for classification, follows the standard PGD
iterations on each sample until it is misclassified. If a sample is
misclassified, we do not implement further PGD iterations. Early stopping
until misclassification maximizes the misclassification rate.
https://github.com/rhaldarpurdue/Adversarial-NN-simulations/blob/main/utils.py
Furthermore, the PGD attack is a white box attack, while our $\lambda_{f}$ is
a semi-white box attack.

#### White box vs Semi-white box attacks:

Note that technically the neural network-based attack $\lambda^{f}$ is at a
disadvantage compared to the gradient-based attacks
$\lambda_{PGD},\lambda_{FGSM}$. $\lambda^{f}$ learns the functional form of
the attack and doesn’t have access to the original model while generating new
attacks on the test dataset, this is known as a semi-white box setting, i.e.,
once the model has been trained no extra gradient computations are done.

In contrast, $\lambda_{PGD},\lambda_{FGSM}$ need to be computed from scratch
for each new sample in the test dataset and also need to have access to the
original classifier models $f,f_{PGD}$. These attacks hence fall into the
white-box setting.

The competitive performance based on test loss and misclassification rate
against various defense/attack combinations compared to the gradient-based
method is consistent with the theory. In real life, one saves computation
costs while using our framework, as $\lambda^{f}$ approximates (13) using
neural networks. Also, the defense $f$ learned as a consequence provides
competitive performance or sometimes better robustness based on these
experiments.

## Regression

For the Boston,Diabetes datasets, we implement Algorithm 1 with
$T=400,H=1,P=1,\tilde{\gamma}=10^{-3},\bar{\gamma}=2\times 10^{-4}$. We use
$\ell_{2}$ attacks to compare the adversarial loss between $f_{PGD}$ and $f$
under $\lambda_{FGSM},\lambda_{PGD},\lambda^{f}$ attacks on the test data. As
$\ell_{2}$ attacks preserve geometry, that perturbation strength in any
direction is the same; we deemed it to be an appropriate choice for the
regression setting. For the loss, we use the Gaussian negative log-likelihood
or the mean-square error loss, $\mathcal{L}(f(x),y)=\norm{f(x)-y}_{2}^{2}$.
The corresponding adversarial loss being
$\mathcal{L}(f,\lambda^{f},(x,y))=\mathcal{L}(f(x+\lambda^{f}(x,y)),y)=\norm{f(x+\lambda^{f}(x))-y}_{2}^{2}$

Figure 4 shows the convergence of the adversarial loss for our robust defense
$f$ based on algorithm 1, comparing against the baseline $f_{PGD}$. In
Appendix D, it can be seen that for higher $\delta$, $\lambda^{f}$ is stronger
than $\lambda_{PGD}$.

Figure 4: (Regression setting) Test Loss vs training epochs for adversarial
training based on Algorithm 1. Where $f$ is our adversarially trained
classifier and $f_{PGD}$ PGD trained robust classifier. For the attacks:
$\lambda^{f}$ represents adversarially trained neural network attack based on
$f$ (semi-white box); $\lambda_{PGD}$ represents (white-box) PGD attack;
$\lambda_{FGSM}$ represents (white-box) FGSM attack.
In the legends the combination $(f,\lambda_{PGD})$ represents the empirical
loss $\sum_{i=1}^{n_{test}}\mathcal{L}(f,\lambda_{PGD},(x_{i},y_{i}))$ when
the PGD attack $\lambda_{PGD}$ is performed on the adversarially trained
defense $f$, similarly $(f_{PGD},\lambda_{PGD})$ represents the empirical loss
$\sum_{i=1}^{n_{test}}(f_{PGD},\lambda_{PGD},(x_{i},y_{i}))$ when
$\lambda_{PGD}$ is performed on $f_{PGD}$; and so on.

##  6 Discussion and conclusion

#### Robust Overfitting

When $\delta$ is comparatively large, adversarial trained robust model
minimizing the objective (4) tends to prioritize minimizing the loss towards
generated adversarial examples and forget the original geometry of data. This
could lead to distortion of the loss surface compared to the clean model and
poor generalization performance of the robust model. This issue is known as
Robust Overfitting in the literature. [41] provides theoretical rates for
reduction of generalisation error w.r.t. $\delta$ attack strength. [43]
suggests a loss-constraining method to prevent data overfitting.

From our experiments, we see that robust overfitting arises as a distortion of
the loss surface. Figure 5 (left) shows the loss surface of adversarially
trained robust $\ell_{\infty}(0.2)$ robust model. The robust classifier tends
to defend against the perturbed data samples and as a result, forgets about
the original geometry of the data points which results in distortion of the
EDB. There is a trade-off between robustness and standard accuracy [38]. As
$\delta$ increases the distortion will get worse, as the perturbed data is
farther from the original data. We can resolve this issue by retaining some
original data information while conducting adversarial training; one can
modify the standard adversarial loss as follows:

$\mathcal{L}(f,\lambda^{f},\mathcal{Z})=\mathbbm{E}\mathcal{L}(f(x+\lambda^{f}(x,y)),y)\to\mathbbm{E}(1-\alpha)\mathcal{L}(f(x+\lambda^{f}(x,y)),y)+\alpha\mathcal{L}(f(x),y)$
(23)

The above equation doesn’t change any of our theory, all the convergence
results and arguments still hold as they are true for a general
$\mathcal{L}(f,\lambda^{f},\mathcal{Z})$. Also, the non-adversarial
counterpart of the loss function is still our original vanilla loss used for
clean training. This is a canonical modification that assigns $\alpha$
weightage to the original data. For the modified loss, the performance plots
analogous to Figures 3 and 2 are almost identical, and we omit them for
brevity. The advantage of this approach is that we eliminate the possible
distortions in the loss surface (Figure 5 Right). This gets rid of the robust
overfitting issue and even for high $\delta$ the robust model can’t stray away
completely from the original data (Figure 7).

[17] proposes a similar weighted loss but instead of using original data, they
use a generative model to produce synthetic data which are perturbed. The idea
being that synthetic data are purer in some sense and retain important
features even after perturbation.

Another popular method to deal with robust overfitting is trade adversarial
robustness off against accuracy (TRADES) proposed by [44]. TRADES splits the
adversarial loss in a similar fashion as (23); but uses the original
classifier scores instead of the true labels for the adversarial part. In our
framework this will correspond to the following adversarial loss:

$\mathcal{L}(f,\lambda^{f},\mathcal{Z})=\mathbbm{E}(1-\alpha)\mathcal{L}(f(x+\lambda^{f}(x,y)),f(x))+\alpha\mathcal{L}(f(x),y).$
(24)

One can extend these methods to our framework by changing the adversarial loss
$\mathcal{L}(f,\lambda^{f},\mathcal{Z})$ suitably.

Figure 5: $\ell_{\infty}(0.2)$, Loss contour plot with learnt attack direction
$\lambda^{f}$ compared for $\alpha=0$ (no-original data) vs $\alpha=0.3$
($30\%$ weightage to original data). Dataset: circles

#### AdvGAN

AdvGAN proposed by [40] uses general adversarial networks (GANs) to generate
adversarial examples. AdvGAN is the best performing black-box attack
generation method according to the Madry MNIST challenge. The theoretical
justifications for AdvGAN can be addressed by our framework.

For generating an attack, a GAN is trained with a generator $G$ and a
discriminator $D$ optimizing the objective
$\min_{G}\max_{D}\mathbbm{E}\mathcal{L}_{adv}+c_{1}\mathcal{L}_{GAN}+c_{2}\mathcal{L}_{hinge}$
for some chosen constants $c_{1},c_{2}$ determining weightage of the losses.
$\mathcal{L}_{GAN}=\log(1-D(G(x)))+\log(D(x))$ is the standard GAN loss
(Bernoulli likelihood) for distinguishing between real and adversarially
perturbed data; $\mathcal{L}_{adv}=-L(f(x+G(x)),y)$ is the adversarial loss
maximizing the model/classifier $f$’s original loss for some $L$, e.g., MSE,
cross-entropy, CW loss, etc;
$\mathcal{L}_{hinge}=\max(0,\norm{G(x)}_{2}-\delta)$ is the hinge loss which
softly bounds the $\ell_{2}$ norm of the generated attacks by $\delta$.

As $D$ appears only in $\mathcal{L}_{GAN}$, we can train $G$ via solving the
objective
$\max_{G}\mathbbm{E}-\mathcal{L}_{adv}-c_{1}\mathcal{L}_{GAN}(D^{*})-c_{2}\mathcal{L}_{hinge}$,
where $D_{G}^{*}=\arg\max_{D}\mathbbm{E}\mathcal{L}_{GAN}$.

To fit the advGAN approach into our framework, the generator $G$ corresponds
to the attack function $\lambda^{f}$ and we choose the loss function as
$\mathcal{L}(f(x),y)=L(f(x),y)-c_{1}\mathcal{L}_{GAN}(D_{G}^{*})$, then the
corresponding adversarial loss would be:

$\mathcal{L}(f,\lambda^{f},\mathcal{Z})=\mathcal{L}(f(x+\lambda^{f}(x,y)),y)=L(f(x+\lambda^{f}),y)-c_{1}\mathcal{L}_{GAN}(D_{G}^{*}).$

Consider the $\ell_{2}(\delta)$ best function attack (2) for the above loss:

$\lambda^{f}=\arg\max_{\norm{\lambda}_{2}\leq\delta}\mathcal{L}(f(x+\lambda(x,y)),y)$

If we consider the Lagrangian of the above objective with Lagrangian
multiplier $c^{\prime}_{2}$, we get:

$\lambda^{f}=\arg\max_{{\lambda}}\mathcal{L}(f(x+\lambda(x,y)),y)+c^{\prime}_{2}(\norm{\lambda}_{2}-\delta).$

When $\norm{\lambda_{2}}\leq\delta$, the optimal solution can be achieved for
$c^{\prime}_{2}=0$; when $\norm{\lambda_{2}}>\delta$, $c^{\prime}_{2}$ has to
be $-\infty$. So, in practice, the constrained optimization can be emulated
for $\lambda^{f}$ by solving:

$\lambda^{f}=\arg\max_{\lambda}\mathcal{L}(f(x+\lambda(x,y)),y)-c_{2}\max(0,\norm{\lambda}_{2}-\delta)=-\mathcal{L}_{adv}-c_{1}\mathcal{L}_{GAN}(D_{\lambda}^{*})-c_{2}\mathcal{L}_{hinge},$

where $c_{2}>0$ is a large coefficient. This is the same loss that the
generator in AdvGAN maximizes. Hence, AdvGAN can be thought of as a special
case of our framework which aims to generate the best $\ell_{2}(\delta)$
attack. Consequently, the dynamic distillation method proposed in [40] is
equivalent to the mathematical game between $G\equiv\lambda^{f}$ and $f$. We
can link the success of AdvGAN to the theoretical justifications provided in
this work.

#### Conclusion

Through this work, we were able to define a generalized framework for
adversarial training, in the sense that the best adversarial attacks/examples
(2) can take a functional form. We showed that this functional form is
essentially captured by a continuous dynamic system closely related to the
gradient flow of the adversarial loss (13). The traditional gradient-based
attacks in the literature can be thought of as a discrete approximation of the
same. Subsequently, the ideal attack resides in a piece-wise Hölder space and
we can render neural networks to approximate this function up to arbitrary
accuracy (Theorem 3.1). This is also empirically verified through our
experiments (Figure 1). Furthermore, using neural networks to generate attacks
and approximating the model with another neural network results in the
adversarial training process being a mathematical game between two neural
networks. We provided a convergence rate for such an adversarial game/training
based w.r.t. the sample size of the data (Theorem 4.1). We also compare the
performance between PGD and a function-based attack generator based on neural
networks; which further bolsters the argument of approximation capability of
neural nets for the ideal attack. As a consequence of training a functional
form, we are also able to generate attacks in a semi-white box setting, whose
performance is comparable to the PGD attack. Our work provides a theoretical
justification for a recent trend to use neural networks to generate attacks;
additionally, we can justify the use of such networks in the context of
adversarial training of a robust model.

## References

  * [1] Theory of Games and Economic Behavior (60th Anniversary Commemorative Edition) on JSTOR, https://www.jstor.org/stable/j.ctt1r2gkx.
  * [2] T. Bai, J. Luo, J. Zhao, B. Wen, and Q. Wang, Recent Advances in Adversarial Training for Adversarial Robustness, (2021), http://arxiv.org/abs/2102.01356.
  * [3] L. Balles, F. Pedregosa, and N. L. Roux, The Geometry of Sign Gradient Descent, (2020), http://arxiv.org/abs/2002.08056.
  * [4] A. J. Bose, G. Gidel, H. Berard, A. Cianflone, P. Vincent, S. Lacoste-Julien, and W. L. Hamilton, Adversarial Example Games, (2020), http://arxiv.org/abs/2007.00720.
  * [5] I. J. Bradley Efron, Trevor Hastie and R. Tibshirani, Least angle regression, 2004.  data retrieved from, https://www4.stat.ncsu.edu/~boos/var.select/diabetes.html.
  * [6] M. Brin and G. Stuck, Introduction to Dynamical Systems, Cambridge University Press, 10 2002, https://doi.org/10.1017/CBO9780511755316, https://www.cambridge.org/core/product/identifier/9780511755316/type/book.
  * [7] N. Carlini and D. Wagner, Towards Evaluating the Robustness of Neural Networks, http://nicholas.carlini.com/code/nn.
  * [8] G. Cybenkot, Mathematics of Control, Signals, and Systems Approximation by Superpositions of a Sigmoidal Function*, Math. Control Signals Systems, 2 (1989), pp. 303–314.
  * [9] Y. Dong, F. Liao, T. Pang, H. Su, J. Zhu, X. Hu, and J. Li, Boosting Adversarial Attacks with Momentum.
  * [10] S. S. Du, C. Jin, J. D. Lee, M. I. Jordan, B. Poczos, and A. Singh, Gradient Descent Can Take Exponential Time to Escape Saddle Points, (2017), http://arxiv.org/abs/1705.10412.
  * [11] F. Feppon, G. Allaire, and C. Dapogny, Null space gradient flows for constrained optimization with applications to shape optimization, ESAIM: Control, Optimisation and Calculus of Variations, 26 (2020), p. 90, https://doi.org/10.1051/COCV/2020015, https://www.esaim-cocv.org/articles/cocv/abs/2020/01/cocv190200/cocv190200.html.
  * [12] N. Frosst, S. Sabour, and G. Hinton, DARCCC: Detecting Adversaries by Reconstruction from Class Conditional Capsules, (2018), http://arxiv.org/abs/1811.06969.
  * [13] P. Ghosh, A. Losalka, and M. J. Black, Resisting Adversarial Attacks using Gaussian Mixture Variational Autoencoders, (2018), http://arxiv.org/abs/1806.00081.
  * [14] G. Gondim-Ribeiro, P. Tabacof, and E. Valle, Adversarial Attacks on Variational Autoencoders, (2018), http://arxiv.org/abs/1806.04646.
  * [15] I. J. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio, Generative Adversarial Networks, (2014), http://arxiv.org/abs/1406.2661.
  * [16] I. J. Goodfellow, J. Shlens, and C. Szegedy, Explaining and Harnessing Adversarial Examples, (2014), http://arxiv.org/abs/1412.6572.
  * [17] S. Gowal, S.-A. Rebuffi, O. Wiles, F. Stimberg, D. A. Calian, and T. Mann, Improving Robustness using Generated Data, (2021), http://arxiv.org/abs/2110.09468.
  * [18] J. R. Graef, J. Henderson, L. Kong, and X. S. Liu, Ordinary differential equations and boundary value problems, Ordinary Differential Equations And Boundary Value Problems, 1 (2018), pp. 1–166, https://doi.org/10.1142/10888.
  * [19] U. Grenander, Abstract inference, (1981), p. 526.
  * [20] J. K. Hale, Stability and Gradient Dynamical Systems, Rev. Mat. Complut, (2004), pp. 7–57.
  * [21] R. D. Harrison D, Hedonic prices and the demand for clean air, 1978\.  data retrieved from StatLib archive, http://lib.stat.cmu.edu/datasets/boston.
  * [22] K. Hornik, M. Stinchcombe, and H. White, Multilayer feedforward networks are universal approximators, Neural Networks, 2 (1989), pp. 359–366, https://doi.org/10.1016/0893-6080(89)90020-8.
  * [23] F. Jaeckle and M. P. Kumar, Generating Adversarial Examples with Graph Neural Networks, (2021), http://arxiv.org/abs/2105.14644.
  * [24] C. Jin, R. Ge, P. Netrapalli, S. M. Kakade, and M. I. Jordan, How to Escape Saddle Points Efficiently, (2017), http://arxiv.org/abs/1703.00887.
  * [25] A. Katok and B. Hasselblatt, Introduction to the Modern Theory of Dynamical Systems, Cambridge University Press, 4 1995, https://doi.org/10.1017/CBO9780511809187, https://www.cambridge.org/core/product/identifier/9780511809187/type/book.
  * [26] D. P. Kingma and J. Ba, Adam: A Method for Stochastic Optimization, (2014), http://arxiv.org/abs/1412.6980.
  * [27] A. Kurakin, G. Brain, I. J. G. Openai, and S. Bengio, ADVERSARIAL EXAMPLES IN THE PHYSICAL WORLD, (2017), http://www.
  * [28] M. Leshno, V. Y. Lin, A. Pinkus, and S. Schocken, Multilayer feedforward networks with a nonpolynomial activation function can approximate any function, Neural Networks, 6 (1993), pp. 861–867, https://doi.org/10.1016/S0893-6080(05)80131-5.
  * [29] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, Towards Deep Learning Models Resistant to Adversarial Attacks, (2017), http://arxiv.org/abs/1706.06083.
  * [30] J. Metzger, Adversarial Estimators, (2022), http://arxiv.org/abs/2204.10495.
  * [31] R. Nakada and M. Imaizumi, Adaptive Approximation and Generalization of Deep Neural Network with Intrinsic Dimensionality, (2019), http://arxiv.org/abs/1907.02177.
  * [32] A. Neelakantan, L. Vilnis, Q. V. Le, I. Sutskever, L. Kaiser, K. Kurach, and J. Martens, Adding Gradient Noise Improves Learning for Very Deep Networks, (2015), http://arxiv.org/abs/1511.06807.
  * [33] P. Petersen and F. Voigtlaender, Optimal approximation of piecewise smooth functions using deep ReLU neural networks, (2017), http://arxiv.org/abs/1709.05289.
  * [34] A. Pinkus, Approximation theory of the MLP model in neural networks, Acta Numerica, 8 (1999), pp. 143–195, https://doi.org/10.1017/S0962492900002919, https://www.cambridge.org/core/journals/acta-numerica/article/abs/approximation-theory-of-the-mlp-model-in-neural-networks/18072C558C8410C4F92A82BCC8FC8CF9.
  * [35] Y. Qin, N. Frosst, C. Raffel, G. Cottrell, and G. Hinton, Deflecting Adversarial Attacks, (2020), http://arxiv.org/abs/2002.07405.
  * [36] L. Schott, J. Rauber, M. Bethge, and W. Brendel, Towards the first adversarially robust neural network model on MNIST, (2018), http://arxiv.org/abs/1805.09190.
  * [37] C. Szegedy, W. Zaremba, I. Sutskever, J. Bruna, D. Erhan, I. Goodfellow, and R. Fergus, Intriguing properties of neural networks.
  * [38] D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry, Robustness May Be at Odds with Accuracy, 7th International Conference on Learning Representations, ICLR 2019, (2018), https://arxiv.org/abs/1805.12152v5.
  * [39] X. Wang, K. He, C. Song, L. Wang, and J. E. Hopcroft, AT-GAN: An Adversarial Generator Model for Non-constrained Adversarial Examples, (2019), http://arxiv.org/abs/1904.07793.
  * [40] C. Xiao, B. Li, J.-Y. Zhu, W. He, M. Liu, and D. Song, Generating Adversarial Examples with Adversarial Networks, (2018), http://arxiv.org/abs/1801.02610.
  * [41] J. Xiao, Y. Fan, R. Sun, J. Wang, and Z.-Q. Luo, Stability Analysis and Generalization Bounds of Adversarial Training, (2022), http://arxiv.org/abs/2210.00960.
  * [42] J. Yang, W. Hu, and C. J. Li, On the fast convergence of random perturbations of the gradient flow, (2017), http://arxiv.org/abs/1706.00837.
  * [43] C. Yu, B. Han, L. Shen, J. Yu, C. Gong, M. Gong, and T. Liu, Understanding Robust Overfitting of Adversarial Training and Beyond, (2022), http://arxiv.org/abs/2206.08675.
  * [44] H. Zhang, Y. Yu, J. Jiao, E. P. Xing, L. E. Ghaoui, and M. I. Jordan, Theoretically Principled Trade-off between Robustness and Accuracy, (2019), http://arxiv.org/abs/1901.08573.

##  Appendix A Additional definitions

###  A.1 CDS

######  Definition A.1 (Continuous dynamic system).

Let $\mathcal{X}$ be a metric space. A mapping
$T:\mathbbm{R}^{+}\times\mathcal{X}\to\mathcal{X}$, $(t;x)\to T(t)x$ is a
continuous ($C^{0}$) dynamical system if it satisfies the following:

  * •

$T(0)=I$,

  * •

$T(t+s)=T(t)T(s);t;s\in\mathbbm{R}^{+}$

  * •

$T(t)\in C^{0}(\mathcal{X};\mathcal{X})$ for $t\geq 0$

  * •

$T(t)x$ is continuous in $t;x$ for $(t;x)\in[0;\infty)\times\mathcal{X}$

######  Definition A.2 (Attraction).

A set $A\subset\mathcal{X}$ attracts a set $B\subset\mathcal{X}$ under the
dynamical system $T$ if

$\lim_{t\to\infty}dist(T(t)B,A)=0$

######  Definition A.3 (Point Dissipative).

A dynamical system $T$ is point dissipative if there is a bounded set
$B\subset\mathcal{X}$ which attracts each point of $\mathcal{X}$.

######  Definition A.4 (Invariant set).

A set $J\in\mathcal{X}$ is an invariant set of the dynamical system $T$ if
$T(t)J=J\,\forall t\in\mathbbm{R}^{+}$

######  Definition A.5.

For a dynamic system $T$:

$\mathcal{A}(T)=\\{x\in\mathcal{X}:T(t)x\text{ is defined and bounded }\forall
t\in\mathbbm{R}^{+}\\}$ (25)

The set $\mathcal{A}(T)$ is the compact global attractor of $T$ if it is
compact, invariant and attracts each bounded set of $\mathcal{X}$.

######  Definition A.6 (stable and unstable sets).

Given a stationary point $x_{0}\in\mathcal{X}$. The stable and unstable sets
of $x_{0}$ are defined respectively:

$\displaystyle W_{s}(x_{0})$
$\displaystyle=\\{x\in\mathcal{X}:\lim_{t\to\infty}dist(T(t)x,x_{0})=0\\}$
$\displaystyle W_{u}(x_{0})$
$\displaystyle=\\{x\in\mathcal{X}:\lim_{t\to-\infty}dist(T(t)x,x_{0})=0\\}$

###  A.2 Function classes

Some set of definitions borrowed from [30].

######  Definition A.7 (Hölder Space).

For a function $h:\mathbb{R}^{D}\rightarrow\mathbb{R},\partial_{d}h(x)$ is a
partial derivative with respect to a $d$-th component, and
$\partial^{\alpha}h:=\partial_{1}^{\alpha_{1}}\cdots\partial_{D}^{\alpha_{D}}h$
using multi-index $\alpha=\left(\alpha_{1},\ldots,\alpha_{D}\right).$ For
$z\in\mathbb{R}$. $\lfloor z\rfloor$ denotes the largest integer that is less
than $z$. Let $\omega>0$ be a degree of smoothness. For
$h:[0,1]^{D}\rightarrow\mathbb{R},$ the Hölder norm is defined as

$\|h\|_{\mathcal{H}\left(\omega,[0,1]^{D}\right)}:=\max_{\alpha:\|\alpha\|_{1}<\lfloor\omega\rfloor}\sup_{x\in[0,1]^{D}}\left|\partial^{\alpha}h(x)\right|+\max_{\alpha:\|\alpha\|_{1}=\lfloor\omega\rfloor
x,x^{\prime}\in[0,1]^{D},x\neq
x^{\prime}}\frac{\left|\partial^{\alpha}h(x)-\partial^{\alpha}h\left(x^{\prime}\right)\right|}{\left\|x-x^{\prime}\right\|_{\infty}^{\omega-\lfloor\omega\rfloor}}$

Then, the Hölder space on $[0,1]^{D}$ is defined as

$\mathcal{H}\left(p,[0,1]^{D}\right)=\left\\{h\in C^{\lfloor
p\rfloor}\left([0,1]^{D}\right)\mid\|h\|_{\mathcal{H}\left(p,[0,1]^{D}\right)}<\infty\right\\}$

Also,
$\mathcal{H}\left(\omega,[0,1]^{D},M\right)=\left\\{h\in\mathcal{H}\left(\omega,[0,1]^{D}\right)\mid\|h\|_{\mathcal{H}\left(\omega,[0,1]^{D}\right)}\leq
M\right\\}$ denotes the $M$-radius closed ball in
$\mathcal{H}\left(\omega,[0,1]^{D}\right)$.

######  Definition A.8 (Covering Number).

For some norm $\|\cdot\|$ over some metric space $\mathcal{X}$, the covering
number $\mathcal{N}(\delta,\mathcal{X},\|\cdot\|)$ is defined as the
cardinality of the smallest set $C\subset\Lambda$ such that
$\sup_{x\in\mathcal{X}}\inf_{c\in C}\|x-c\|\leq\delta$. The quantity
$\log\mathcal{N}(\delta,x,\|\cdot\|)$ is also called metric entropy.

######  Definition A.9 (Minkowski Dimension).

The (upper) Minkowski dimension of a set $S\subset[0,1]^{D}$ is defined as

$\operatorname{dim}_{M}{S}:=\inf\left\\{d^{*}\geq
0\mid\limsup_{\varepsilon\downarrow
0}\mathcal{N}(\varepsilon,{S},\|\cdot\|_{\infty})\varepsilon^{d^{*}}=0\right\\}$

where $\mathcal{N}(\varepsilon,{S},\|\cdot\|_{\infty})$ is given by Definition
A.8.

######  Definition A.10 (Minimum $\gamma$ covering).

Let $S\subset\mathcal{X}$ then the minimum $\gamma$ covering of $S$ is define
as the set of $\gamma$ radius balls $\mathcal{I}$ whose centres form the set
$C$ such that $\text{card}(C)=\mathcal{N}(\gamma,S,\|\cdot\|)($A.8). For
$\ell_{\infty}$ norm, $\cup_{i=1}^{|\mathcal{I}|}I_{i}=\mathcal{I}$ are the
set of hyper cubes of length $\gamma$ which cover $S$. If the norm is not
specified, assume it to be $\ell_{\infty}$.

##  Appendix B supporting results

######  Lemma B.1 (Lemma A.8 [33]).

Fix any $h\in\mathcal{H}(\omega,[0,1,]^{D},M)$ (A.7) and
$\bar{x}\in[0,1]^{D}$. Let $\bar{h}(x)$ be the Taylor polynomial of degree
$\lfloor{\omega}\rfloor$ of $h$ around $\bar{x}$, namely,

$\bar{h}(x):=\sum_{\absolutevalue{\alpha}\leq\lfloor{p}\rfloor}\frac{\partial^{\alpha}h(\bar{x})}{\alpha!}(x-\bar{x})^{\alpha}.$

Then, $\absolutevalue{h(x)-\bar{h}(x)}\leq
D^{\omega}M\norm{x-\bar{x}}^{\omega}$ holds for any $x\in[0,1]^{D}$. Note that
there exists some constant $\overline{C}=\overline{C}(\omega,D,M)$ such that
$\sup_{\absolutevalue{\alpha}\leq\lfloor{\omega}\rfloor}\absolutevalue{\partial^{\alpha}h(\bar{x})/\alpha!}\leq\overline{C}M$
for $f\in\mathcal{H}(\omega,[0,1]^{D},M)$.

######  Lemma B.2 (Lemma 20 [31]).

Let $\mathcal{I}$ be a minimum $\gamma$-covering of $\mathcal{X}$. Then, there
exists a disjoint partition $\quantity{\mathcal{I}_{i}}_{i=1}^{5^{D}}$ of
$\mathcal{I}$ such that $\mathcal{I}=\bigcup_{i=1}^{5^{D}}\mathcal{I}_{i}$ and
$d(I_{j},I_{k})\geq\gamma$ hold for any $I_{j}\neq I_{k}\in\mathcal{I}_{i}$ if
$\text{card}(\mathcal{I}_{i})\geq 2$.

######  Lemma B.3 (Volume of boundary cubes).

$\partial\boldsymbol{A}=\\{x:x\in\bar{A_{i}}\bigcap\bar{A_{i}^{c}}\text{ for
some }A_{i}\in\boldsymbol{A}\\}$ be the boundary set of the pieces of any
$f\in\bar{\mathcal{H}}(\omega,\mathcal{X})$. By definition the boundary set
can be at most $D-1$ dimensions.
Consider the set of minimum $\gamma$ covering interacting with the boundary of
the pieces, $\mathcal{I}_{\partial}=\\{I:I\in\mathcal{I}\
s.t.\,I\bigcap\partial\boldsymbol{A}\neq\phi\\}$.
Then
$\mathcal{N}(\gamma,\partial\boldsymbol{A},\norm{}_{\infty})\prec\text{card}(\mathcal{I}_{\partial})\prec\mathcal{N}(\frac{\gamma}{2},\partial\boldsymbol{A},\norm{}_{\infty})$
and $\mu(\mathcal{I}_{\partial})=\mathcal{O}(\gamma)$.

##  Appendix C Proofs

###### Proof of lemma B.3.

For any covering $\mathcal{I}_{0}$ define the coverage set as
$cv(\mathcal{I}_{0})=\\{\bigcup I_{i}:I_{i}\in\mathcal{I}_{0}\\}$ . We want to
show that the number of cubes $I\in\mathcal{I}$ intersecting with the boundary
is controlled by the covering number of the boundary.
We will prove the first inequality by contradiction; assume
$card(\mathcal{I}_{\partial})<\mathcal{N}(\partial\mathcal{A},\norm{}_{\infty},\gamma)$
instead. This isn’t possible as $\mathcal{I}_{\partial}$ is also a covering
for $\partial\mathcal{A}$ but that implies the existence of a covering smaller
than the minimum covering-number of $\partial\boldsymbol{A}$ which is a
contradiction. Hence,
$\mathcal{N}(\partial\mathcal{A},\norm{}_{\infty},\gamma)\leq
card(\mathcal{I}_{\partial})$.

For the second inequality, consider a naive $\gamma$-covering
$\mathcal{\hat{I}^{\gamma}}$ such that the centres of all the cubes involved
in the covering are at least $\gamma$ distance apart. Let $C=\\{C_{i}\\}$ be
the set of centers corresponding to the cubes of $\mathcal{\hat{I}}$, and they
satisfy that $\min_{i\neq j}\norm{C_{i}-C_{j}}_{\infty}=\gamma$. One can
visualise it as a space-filling covering by stacking cubes adjacent to each
other, such that all the cube edges pass through the centre of neighbouring
cubes. By construction $card(\mathcal{I})\leq
card(\mathcal{\hat{I}^{\gamma}})$, as $card(\mathcal{I})$ is the minimum
$\gamma$-covering.

Also, let
$\mathcal{\hat{I}^{\gamma}}_{\partial}=\\{I:I\in\mathcal{\hat{I}^{\gamma}}\
s.t.\,I\bigcap\partial\boldsymbol{A}\neq\phi\\}$. Notice, that
$cv(\mathcal{I}_{\partial})\subseteq\\{x:d(x,\partial\mathcal{A})\leq
2\gamma\\}$ and
$cv(\mathcal{\hat{I}^{\gamma}}_{\partial})\supseteq\\{x:d(x,\partial\mathcal{A})\leq\gamma\\}$.
This is enforced by the constraint that cubes intersecting with the boundary
can have points inside it at most $2\gamma$ distance away from the boundary.
Furthermore, as the radius of each cube is $\gamma$ it can at the least cover
$\gamma$ distance around the boundary. Similarly,
$cv(\mathcal{\hat{I}}^{2\gamma}_{\partial})\supseteq\\{x:d(x,\partial\mathcal{A})\leq
2\gamma\\}$.
Furthermore, noting that each cube of radius $2\gamma$ can be decomposed into
$2^{D}$ smaller cubes of radius $\gamma$, we can always define some
$\mathcal{I}^{\prime}$ which is a set of $\gamma$-radius cubes, such that
$cv(\mathcal{I}^{\prime})=cv(\mathcal{\hat{I}}^{2\gamma}_{\partial})$ and
$card(\mathcal{I}^{\prime})=2^{D}card(\mathcal{\hat{I}}^{2\gamma}_{\partial})$.
Therefore, $cv(\mathcal{I}_{\partial})\subseteq
cv(\mathcal{\hat{I}}^{2\gamma}_{\partial})=cv(\mathcal{I}^{\prime})$ and
$\mathcal{\hat{I}}$ is the minimal-$\gamma$ covering imply that
$card(\mathcal{I}_{\partial})<card(\mathcal{I}^{\prime})=2^{D}card(\mathcal{\hat{I}^{\gamma}}_{\partial})$.
(Otherwise
$\mathcal{\hat{I}}\backslash\mathcal{I}_{\partial}\cup\mathcal{I}^{\prime}$ is
a better $\gamma$-covering than $\mathcal{\hat{I}}$).

Let $V$ be the minimum $\gamma/2$-covering of $\partial{A}$. Notice that each
cube in the minimum $\gamma/2$ covering can intersect at most $4^{D}$ cubes in
$\mathcal{\hat{I}}^{\gamma}_{\partial}$. This is a consequence of the lattice
structure induced by $\mathcal{\hat{I}}^{\gamma}_{\partial}$. (Given a
$\gamma$ spacing lattice and any arbitrary point, there are at most $4^{D}$
lattice grid points that are within 3/2-$\gamma$ distance to the specific
point.) As, all cubes in $\mathcal{\hat{I}}^{\gamma}_{\partial}$ must
intersect with some $I\in V$ by definition. Subsequently, each $I\in V$ has at
most $4^{D}$ cubes in $\mathcal{\hat{I}}^{\gamma}_{\partial}$ that intersect
with it; hence a conservative estimate for the total number of cubes in
$\mathcal{\hat{I}}^{\gamma}_{\partial}$ can be bounded by
$4^{D}\text{card}(V)$. This implies that
$card(\mathcal{\hat{I}}^{\gamma}_{\partial})\leq
4^{D}\mathcal{N}(\partial\mathcal{A},\norm{}_{\infty},\gamma/2)$.

Combining all the previous arguments,

$\mathcal{N}(\partial\mathcal{A},\norm{}_{\infty},\gamma)\leq
card(\mathcal{I}_{\partial})\leq
2^{D}card(\mathcal{\hat{I}}^{\gamma}_{\partial})\leq 2^{D}\cdot
4^{D}\mathcal{N}(\partial\mathcal{A},\norm{}_{\infty},\gamma/2).$

Using the properties of covering numbers we have,
$\mathcal{N}(\partial\mathcal{A},\norm{}_{\infty},\gamma),\mathcal{N}(\partial\mathcal{A},\norm{}_{\infty},\gamma/2)\asymp\frac{1}{\gamma}^{D-1}$.
Consequently, $card(\mathcal{I}_{\partial})\asymp\frac{1}{\gamma}^{D-1}$.
Subsequently,
$\mu(\mathcal{I}_{\partial})=\mathcal{O}(\gamma^{D}\times\frac{1}{\gamma}^{D-1})=\mathcal{O}(\gamma)$.
∎

###### Proof of Theorem 2.1.

Considering (8), let the candidate solution be
$x^{*}=x_{adv}=\lambda^{f}(x_{s},y)+x_{s}$ where $\lambda^{f}$ is defined in
(13). Note that $x^{*}$ can’t be a saddle point of $F(x)$ ( As $\dot{x}>0$ at
saddle points (12)) and can only be a local maxima with $\nabla{F}(x^{*})=0$
or a point at the boundary of the $B_{p}(x_{s},\delta)$ ball which is
orthogonal to the surface of $B_{p}(x_{s},\delta)$.
$\ell_{\infty}$ constraint:

For each $i$ the gradient of the constrained function is $\nabla
g_{i}(x)=(0,\dots,s(x-x_{s})_{i},\dots,0)^{T}$, where $s(x)$ is the sub-
differential of the absolute function; $s(x)=1,-1$ for $x>0,<0$ resp. and
$s(x)=[-1,1]$ for $x=0$.

It easy to see that $\nabla g_{i}(x)$ is just a basis for the Euclidean space.
Hence, it is linearly independent and this non-linear optimisation problem
falls in the LICQ class of conditions (Linear independence constraint
qualification). The KKT conditions for LICQ class is necessary for a solution.

Stationarity: $\nabla F(x^{*})=\sum_{i}\mu_{i}^{*}\nabla
g_{i}(x^{*})=(\mu_{1}^{*}s(x^{*}-x_{s})_{1},\dots,\mu_{i}^{*}s(x^{*}-x_{s})_{i},\dots,\mu_{D}^{*}s(x^{*}-x_{s})_{D})^{T}$
where $\mu_{i}\geq 0$. When $x^{*}$ is in the interior of the
$B_{\infty}(x_{s},\delta)$ then it means the dynamics reaches equilibrium
$\dot{x^{*}}=\nabla F(x^{*})=0$, hence stationarity is satisfied for
$\mu_{i}=0$.

When $x^{*}\in\partial B_{\infty}(x_{s},\delta)$ then some of the inequality
constraints are active (represented by $\boldsymbol{J}(x^{*})$) and the
dynamic system reaches equllibrium if and only if
$\dot{x^{*}}=\nabla_{x}F(x^{*})\odot(\boldsymbol{1}-\boldsymbol{J}(x^{*}))=0$;
so the gradient will be along the diagonals or the sides of the cube
determined by the active constraint. Stationary condition is again satisfied,
with $\mu_{i}=0$ if $g_{i}(x^{*})<0$.

Complimentary Slackness: This also implies $\mu_{i}g_{i}(x)=0$ for all $i$
(for active constraint $g_{i}(x)=0$, for inactive constraints $\mu_{i}=0$).

Duality: Also note that by definition of $\bar{T}^{pgf}_{x_{s}}$ and
continuity of the gradient; the gradient sign is consistent to the
$\text{sign}(x^{*}-x_{s})$ enforcing duality $\mu_{i}\geq 0$ for all $i$.
Primal feasibility is trivially true as our CDS is within
$B_{\infty}(x_{s},\delta)$.

SOSC: Given the active constraints
$\boldsymbol{C}(x^{*})=[(g_{i}(x^{*}))_{i\in I}]$ at $x^{*}$; the set of
feasible directions is

$FD=\\{d\in\mathcal{X}:(D\boldsymbol{C}(x^{*})d)_{i}\leq 0\,\forall i\in I\\}$

The feasible directions in our case must be along $\boldsymbol{P}(x^{*})$.
When $x^{*}$ is at the boundary away from saddle points, it follows a non-
decreasing trajectory essentially along the feasible directions (9). Hence,
hessian along the feasible direction ($d^{T}\nabla_{xx}F(x)d<0$) must be
negative , as the gradient along the trajectory goes from positive to zero at
equilibrium ($\dot{F}(x(t))>0\to\dot{F}(x^{*})=0$). The second order
sufficient condition requires us to show $d^{T}\nabla_{xx}L(x,\mu)d>0$, where
$L(x,\mu)$ is the Lagrangian, but for $\ell_{\infty}$ constraints the second
derivatives corresponding to the constraints are zero hence
$-d^{T}\nabla_{xx}L(x,\mu)d=d^{T}\nabla_{xx}F(x)d<0$. For $x^{*}$ inside the
ball, all constraints are inactive and by our construction $x^{*}$ can’t be a
saddle point but it is equilibrium to an increasing trajectory hence
$\nabla_{xx}F(x)$ is just a negative definite matrix.

$\ell_{p};1\leq p<\infty$ constraint:

This is a much simpler case with only one inequality constraint
$g_{1}(x)=\norm{x-x_{s}}^{p}_{p}-\delta^{p}$. We can again verify the KKT and
SOSC to prove optimal solution.

Stationarity: In this case stationarity is achieved if the gradient $\nabla
F(x^{*})=\mu\nabla g_{1}(x^{*})$, essentially the gradient must be
proportional to the normal vector of the $\ell_{p}$ ball. This is naturally
satisfied as the ODE of our CDS attains equillibrium iff
$\dot{x^{*}}=\boldsymbol{P}\nabla F(x^{*})=0$; which implies that $\nabla
F(x^{*})$ must be orthogonal to the surface (as $\boldsymbol{P}$ is the
projection matrix to $\partial B_{p}(x_{s},\delta)$) or parallel to the normal
vector $\nabla{g_{1}}(x^{*})$.

If $x^{*}$ is in the interior of $B_{p}(x_{s},\delta)$, then the ODE at
equillibria $\dot{x^{*}}=\boldsymbol{P}\nabla F(x^{*})=\boldsymbol{I}\nabla
F(x^{*})=0$ implies the $\nabla{F}(x^{*})=0$; hence stationarity is satisfied
for $\mu=0$. Complimentary slackness, duality, primal feasibility can be
verified by the same arguments used for $\ell_{\infty}$ case.

SOSC: When $x^{*}$ is in the interior of the ball the argument is the same as
$\ell_{\infty}$ constraint case. At boundary again using similar arguments we
have $d^{T}\nabla_{xx}F(x)d<0;d\in FD$. Also, note that $\nabla_{xx}g_{1}(x)$
is positive definite (hessian of the norm) almost surely, so the Lagrangian
$L(x,\mu)=-F(x)+\mu g_{1}(x)$ is also enforced to have
$d^{T}\nabla_{xx}L(x,\mu)d>0;d\in FD$ hence the second order sufficient
condition is satisfied. With both KKT and SOSC conditions satisfied $x^{*}$ is
the optimal solution.

The optimality of $\lambda^{f}(x,y)$ as a $\ell_{p}(\delta)$ function attack
follows as

$\max\limits_{\lambda\in\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})}\mathbbm{E}\mathcal{L}(f(x+\lambda(x,y)),y)\leq\mathbbm{E}\max\limits_{\lambda\in\mathcal{F}^{p}_{\delta}(\tilde{\mathcal{C}})}\mathcal{L}(f(x+\lambda(x,y)),y).$

∎

###### Proof of Theorem 3.1.

We will first get an $\epsilon$ error bound for any
$f\in\bar{\mathcal{H}}(\omega,\mathcal{X})$. Then we can extend the result to
the product space for any
$\vec{f}=(f^{(1)},\dots,f^{(D)})\in\bar{\mathcal{H}}(\omega^{*},D,\mathcal{X})$.

$\epsilon$ bound for $f$: Consider the minimum-$\gamma$ covering $\mathcal{I}$
of $\mathcal{X}$. Using lemma B.2,
$\mathcal{I}=\cup_{i=1}^{5^{D}}\mathcal{I}_{i}$. Let $\Xi:\mathcal{I}\to
2^{card(\mathcal{I})}$, $\Xi(I)=\\{I^{\prime}\in\mathcal{I}:I\oplus
3\gamma/2\cap I^{\prime}\neq\phi\\}$ be a set function finding neighbouring
(radius $3\gamma/2$) cubes of $I$. Consider
$\tilde{\Xi}(I)=\Xi(I)\setminus\mathcal{I}_{\partial}$ defined for all
$I\in\mathcal{I}\setminus{I}_{\partial}$. (where $\mathcal{I}_{\partial}$ is
defined in lemma B.3)
Using Remark 19 of [31], one can construct a Neural network
$R(\phi^{simul}_{\epsilon/2}):\mathbbm{R}^{D}\to\mathbbm{R}^{\text{card}(\mathcal{I})}$,
and each of its output dimension represents a neural network approximation of
the Taylor-polynomial associated with $f>0$. Let $f_{I}$ be the Taylor-
polynomial approximation of $f$ centred at $\bar{x}_{I}$, where $\bar{x}_{I}$
is the center of the hypercube $I$. Denote a bijective mapping
$\psi:\mathcal{I}\to\\{1,2,\dots,\text{card}(\mathcal{I})\\}$ which maps any
hypercube $I\in\mathcal{I}$ to the associated output dimension of
$R(\phi^{simul}_{\epsilon/2})$. Then $R(\phi^{simul}_{\epsilon/2})_{\psi(I)}$
is an $\epsilon/2$ approximation of $f_{I}$.

For any general $f$, consider a shifted version of the function which is
always positive $f_{1}=f+M+1$ where $M$ is the upper bound of $|f|$ based on
Hölder norm (as $R(\phi^{simul}_{\epsilon/2})$ is valid for approximation of
non-negative functions). For a cube $I\in\mathcal{I}_{\partial}$, we define a
constant zero neural network $R_{0}(x)$ with all weights and bias being zeros.
For cubes $I\in\mathcal{I}\setminus\mathcal{I}_{\partial}$, we define the
neural network approximation to the Taylor polynomial around the center of the
cube as $R(\phi^{simul}_{\epsilon/2})_{\psi(I)}$. The piece-wise Hölder
function $f\in\bar{\mathcal{H}}(\omega,\mathcal{X})$ restricted to any of the
hypercubes $I\in\mathcal{I}\setminus\mathcal{I}_{\partial}$, will belong to
$\mathcal{H}(\omega,I)$ (A.7). In terms of architecture requirements from
Remark 19 of [31], we have
$W=C_{1}\epsilon^{-d/\omega},w=C_{2}\epsilon^{-d/\omega},\kappa=\mathcal{O}(\epsilon^{-s}),L=C_{3}$
for $R(\phi^{simul}_{\epsilon/2})$. Note that these neural networks
approximate the Taylor polynomial of $f_{1}$ at the center of the cube, for
all $x\in I$ with $\epsilon/2$ accuracy. And outside the cube it is strictly
less than the polynomial it is approximating and 0 after a lag of $\gamma/2$.

As the sum and max functions can be replicated by the Relu neural networks, we
can then mimic the proof of Theorem 5 for the piece-wise Hölder case [31], as
follows. Consider the neural network realisation of

$R(\phi_{\epsilon}^{f_{1}})=\max_{i\in
5^{D}}\\{\sum_{I\in\mathcal{I}_{i}\setminus\mathcal{I}_{\partial}}R(\phi^{simul}_{\epsilon/2})_{\psi(I)}+R_{0}(x)\\},$

hence for any $x\in I$ for some
$I\in\mathcal{I}\setminus\mathcal{I}_{\partial}$ we have

$\displaystyle\absolutevalue{R(\phi_{\epsilon}^{f_{1}})-f_{1}}$
$\displaystyle=\max\\{\max_{I^{\prime}\in\tilde{\Xi}(I)}R(\phi^{simul}_{\epsilon/2})_{\psi(I^{\prime})}-f_{1}(x),f_{1}-\max_{I^{\prime}\in\tilde{\Xi}(I)}R(\phi^{simul}_{\epsilon/2})_{\psi(I^{\prime})}\\}$
$\displaystyle\leq\max_{I^{\prime}\in\tilde{\Xi}{I}}\absolutevalue{R(\phi^{simul}_{\epsilon/2})_{\psi(I^{\prime})}-f_{1}(x)}$
$\displaystyle\leq\max_{I^{\prime}\in\tilde{\Xi}{I}}\absolutevalue{R(\phi^{simul}_{\epsilon/2})_{\psi(I^{\prime})}-f_{I^{\prime}}(x)}+\max_{I^{\prime}\in\tilde{\Xi}{I}}\absolutevalue{f_{I^{\prime}}(x)-f_{1}(x)}$
$\displaystyle\leq\epsilon/2+D^{\omega}M(\frac{3\gamma}{2})^{\omega},$

where the last inequality uses Remark 19 [31] and lemma B.1. For side-length
of the cube
$\gamma=D^{-1}(3M)^{\frac{-1}{\omega}}\epsilon^{\frac{1}{\omega}}$, we then
have $\absolutevalue{R(\phi_{\epsilon}^{f_{1}})-f_{1}}\leq\epsilon$
The above approximation works for all cubes upto the measure of the cubes in
$\mathcal{I}_{\partial}$. As we are working with probability measures the
$\mu(\mathcal{I}_{\partial})=\mathcal{O}(Vol(\mathcal{I}_{\partial}))=\mathcal{O}(\gamma)=\mathcal{O}(\epsilon^{\frac{1}{\omega}})$
is a consequence of lemma B.3.

Note that the composition of the sum and maximum function as neural network
only increases $L,W,w$ by some constant depending on
$\text{card}(\mathcal{I})$ and $5^{D}$. The number of layers $L$, number of
non-zero weights $W$ and in turn the width $w$ are additive w.r.t composition
of neural networks. Also, $\kappa$ is the maximum of the $\kappa^{\prime}s$ of
the constituent neural nets being composed. $\kappa$ for the sum and and max
neural network are just some constants dependent on $M$ and independent of
$\epsilon$. For small enough $\epsilon$ architecture requirement for
$R(\phi_{\epsilon}^{f_{1}})$ is same as $R(\phi^{simul}_{\epsilon/2})$ up to
constants independent of $\epsilon$;
$W=C_{1}^{\prime}\epsilon^{-d/\omega},w=C_{2}^{\prime}\epsilon^{-d/\omega},\kappa=\mathcal{O}(\epsilon^{-s_{1}}),L=C_{3}^{\prime}$.
Similarly, one can get a neural network realisation of $f$ by taking an affine
transformation $R(\phi_{\epsilon}^{f})=R(\phi_{\epsilon}^{f_{1}})-M-1$ which
adds constant additional layers and constant number of non-zero weights.

In conclusion, $\epsilon$ bound for $f_{1}$ above leads to $\epsilon$ bound
for $f$:

$\absolutevalue{R(\phi_{\epsilon}^{f})-f}=\absolutevalue{R(\phi_{\epsilon}^{f_{1}})-f_{1}}\leq\epsilon.$

$\epsilon$ bound for $\vec{f}$: Consider a concatenation of neural nets
$R(\phi_{\epsilon}^{\vec{f}})=[R(\phi_{\epsilon}^{f^{(1)}}),\dots,R(\phi_{\epsilon}^{f^{(D)}})]$;
where $R(\phi_{\epsilon}^{f^{(i)}})$ is an $\epsilon$\- neural network
approximation of $f^{(i)}\in\bar{\mathcal{H}}(\omega_{i},\mathcal{X})$ proved
previously.
It is easy to see that the architecture requirements for the
$R(\phi_{\epsilon}^{\vec{f}})$ are $W=\sum
C_{1}^{(i)}\epsilon^{-d/\omega_{i}}=\mathcal{O}(\epsilon^{-d/\omega^{*}});w=\sum
C_{2}^{(i)}\epsilon^{-d/\omega_{i}}=\mathcal{O}(\epsilon^{-d/\omega^{*}});\kappa=\mathcal{O}(\max(\epsilon^{-s_{1}},\dots,\epsilon^{-s_{d}}))=\mathcal{O}(\epsilon^{-s^{*}});L=\sum
C_{3}^{(i)}=C_{3}^{*}$. Where
$\omega^{*}=\min\\{\omega_{i}\\},s^{*}=\max\\{s_{i}\\}$.
Corresponding to each $R(\phi_{\epsilon}^{f^{(i)}})$ there is a measurable set
$\nu_{i}$ with $\mu(\nu_{i})=\mathcal{O}(\epsilon^{1/\omega_{i}})$ such that:

$\sup_{x\in\mathcal{X}_{s}\setminus\nu_{i}}\absolutevalue{R(\phi_{\epsilon}^{f^{(i)}})(x)-f^{(i)}(x)}\leq\epsilon.$

This implies for $\nu=\cup_{i}\nu_{i}$;
$\mu(\nu)=\mathcal{O}(\epsilon^{1/\omega^{*}})$ and the suitable architecture
requirements:

$\displaystyle\sup_{x\in\mathcal{X}_{s}\setminus\nu}||R(\phi_{\epsilon}^{\vec{f}})(x)-\vec{f}(x)||_{\infty}=\sup_{x\in\mathcal{X}_{s}\setminus\nu}\sup_{i\in\\{1,\dots,D\\}}\absolutevalue{R(\phi_{\epsilon}^{f^{(i)}})(x)-f^{(i)}(x)}\leq\epsilon.$

∎

###### Proof of lemma 2.2.

WLOG, $x\in W_{s}(x_{0})$ for some $x_{0}\in E$. Then by definition,
$\lambda^{pgf}(x,y)\in W_{s}(x_{0})$.

$\lambda^{pgf}(x,y)=\lim_{t\to\infty}\bar{T}^{pgf}_{x}(t)x-x=\int_{0}^{\infty}\underbrace{\boldsymbol{P}(X(t,x))}_{h_{1}(t,x)}[\underbrace{\nabla
F(X(t,x))+\sum_{\eta\in
S}\psi_{\epsilon}^{\eta}(X(t,x))\nu^{\eta}_{max}}_{h_{2}(t,x)}]\,dt-x$

Where, $X(t,x)=x+z(t,x)$ ; $\dot{z}(t,x)=h_{1}\cdot h_{2}(t,x)$ and $z(0)=0$.
Let, $t_{b}(x)=\inf\\{t:X(t,x)\in\partial B_{p}(x,\delta)\\}$.
Before time $t_{b}$ constraints are inactive and
$\boldsymbol{P}(X(t,x))=\boldsymbol{I}$.

$\displaystyle\lambda^{pgf}(x,y)$
$\displaystyle=\underbrace{\int_{0}^{t_{b}(x)}h_{2}(t,x)\,dt}_{I_{0}}+\underbrace{\int_{t_{b}(x)}^{\infty}h_{1}.h_{2}(t,x)\,dt}_{I_{1}}-x$
$\displaystyle=X(t_{b},x)+X(\infty,\underbrace{x_{1}}_{X(t_{b},x)})-x$

As, $\nabla F(X),\psi_{\epsilon}^{\eta}(X)$ are at least $C^{k}$ smooth in
$X$, using Theorem 3.1 (Differentiation w.r.t. initial condition) of [18]
inductively, we get $I_{0}=X(t_{b},x)$ is $C^{k}$ smooth w.r.t. $x$. For
$t>t_{b}$ and even $p<\infty$, note that $P(X)$ is $C^{\infty}$ smooth w.r.t.
$X$ because $\norm{X-x}_{p}^{p}-\delta^{p}$ is $C^{\infty}$ w.r.t $X$. Hence,
using Theorem 3.1[18] inductively we get $I_{1}$ is $C^{k}$ smooth w.r.t.
$x_{1}=X(t_{b},x)$. Using the chain rule, then we have $I_{1}$ is $C^{k}$
smooth w.r.t. $x$. For, even $p<\infty$, $\lambda^{pgf}(x,y)$ is then $C^{k}$
smooth w.r.t. $x$.
In the case $p=\infty$ or odd, for $t>t_{b}$, $\boldsymbol{P}(X)$ is only
smooth where $\text{sign}(X(t,x)-x)$ is consistent. Let,
$t_{1},t_{2},\dots,t_{m}$ be the times where the sign changes and
$t_{m+1}=\infty$. Then,

$\displaystyle\lambda^{pgf}(x,y)$
$\displaystyle=\underbrace{\int_{0}^{t_{b}}h_{2}(t,x)\,dt}_{I_{0}}+\underbrace{\int_{t_{b}}^{t_{1}}h_{1}.h_{2}(t,x)\,dt}_{I_{1}}+\sum_{l=2}^{m+1}\underbrace{\int_{t_{l-1}}^{t_{l}}h_{1}.h_{2}(t,x)\,dt}_{I_{l}}-x$
$\displaystyle=X(t_{b},x)+X(t_{1}-t_{b},\underbrace{x_{1}}_{X(t_{b},x)})+\sum_{l=2}^{m+1}X(t_{l}-t_{l-1},\underbrace{x_{l}}_{X(t_{l-1},x)})-x$

Using similar arguments as before we know that, each $I_{l}$ is $C^{k}$ smooth
w.r.t. $x_{l}$. Using induction:
Base step: $I_{0}=x_{1}$ is $C^{k}$ smooth w.r.t. $x$, $I_{1}$ is $C^{k}$
smooth w.r.t. $x_{1}$ hence using chain rule $I_{1}$ is $C^{k}$ smooth w.r.t.
$x$. In turn $X(t_{1},x)$ is $C^{k}$ smooth w.r.t. $x$
Induction Step: If $x_{l}=X(t_{l-1},x)$ is $C^{k}$ smooth then $X(t_{l},x)$ is
$C^{k}$ smooth.
$x_{l+1}=X(t_{l},x)=X(t_{l-1},x)+I_{l}$, but $I_{l}$ is $C^{k}$ smooth w.r.t.
$X(t_{l-1},x)$, hence using chain rule $I_{l}$ and consequently $x_{l+1}$ is
$C^{k}$ smooth w.r.t. $x$.

∎

###### Proof of Theorem 4.1.

The proof relies on the application of theorem 3.1 [30] and almost identical
to the proof of their theorem 3.2 with the major difference being the function
classes considered in our framework. This results in change of
$\epsilon_{n},\bar{\epsilon}_{n}$ terms which correspond to the expected
difference of the adversarial loss evaluated at the sieve projection and the
true parameters. In our case the sieve projection is just the neural network
approximation using $n$ samples. Using assumption $A3$ and corollary 3.2 we
get:

$\displaystyle\epsilon_{n}=\sup_{f\in\mathcal{C}_{n}}\mathbb{E}[\mathcal{L}(f,\lambda^{f},\mathcal{Z})-\mathcal{L}(f,\pi_{n}\lambda^{f},\mathcal{Z})]$
$\displaystyle\prec\sup_{f\in\mathcal{C}_{n}}\|\pi_{n}\lambda^{f}-\lambda^{f}\|_{\widetilde{{\mathcal{X}}}}^{2}+\mathbb{P}^{2\omega^{*}}(x\not\in\widetilde{{\mathcal{X}}})$
$\displaystyle\prec\min(W_{n},w_{n},D^{-1/p}\delta)^{2}+\min{(W_{n},w_{n})}^{-2\omega^{*}/d^{*}}$
$\displaystyle\prec
n^{-2\omega^{*}\underline{r}/d^{*}(\underline{r}+2)}=n^{-2/(\underline{r}+2)}$

where $\mathbb{P}(x\not\in\widetilde{{\mathcal{X}}})$ corresponds to the small
measurable set where the neural network can’t approximate (the volume which
covers the pieces of our piece-wise Hölder functions). Also, $D^{1/p}\delta$
is a hard bound for the function class $\mathcal{F}^{p}_{\delta}$, but when
considering very wide networks for approximation, that bound is never
exceeded.
Similarly we can bound $\bar{\epsilon_{n}}$ using $A2$ and Corollary 3.2:

$\displaystyle\bar{\epsilon}_{n}=\mathbb{E}[\mathcal{L}(\pi_{n}f^{*},\lambda^{f^{*}},\mathcal{Z})-\sup_{f\in\mathcal{C}_{n}}\mathcal{L}(f^{*},\lambda^{f^{*}},\mathcal{Z})]$
$\displaystyle\prec\|\pi_{n}f^{*}-f^{*}\|_{\widetilde{{\mathcal{X}}}}^{2}$
$\displaystyle\prec\min(W_{n},w_{n})^{2}\prec
n^{-2\omega^{*}\underline{r}/d^{*}(\underline{r}+2)}=n^{-2/(\underline{r}+2)}$

The rest of the proof follows using arguments of theorem 3.2 [30]. ∎

##  Appendix D Additional experiments and details

Figure 6: Simulated 2D datasets for classification setting.

Code for simulated dataset: https://github.com/rhaldarpurdue/Adversarial-NN-
simulations

###  D.1 Architecture details

We use Pytorch libraries for all of our implementations. For optimization, we
use the Adam method proposed by [26].

#### Classification:

$D=dim(x)$ and $C$ is the total number of classes; $c\in\\{1,\dots,C\\}$ is
the label index for each sample. The attack generator
$\lambda^{f}(x,y)\coloneqq S_{c}(x)\odot\mathcal{D}_{c}(\mathcal{E}(x))$ if
$y=c$.
$\mathcal{E},\mathcal{D}_{c},S_{c}$ are the encoder, decoder, scaler resp..
The scaler is responsible for the magnitude of the attack. (Table 1)

Table 1: Pytorch Architecture for classification setting $f$ | $\lambda^{f}$
---|---
$\mathcal{E}$ | $\mathcal{D}_{c}$ | $S_{c}$
| Linear(2, 50)
---
LeakyReLU(0.01),
Linear(50,100),
LeakyReLU(0.01),
Linear(100,15),
LeakyReLU(0.01),
Linear(15, $C$)
| Linear(2, 50),
---
LeakyReLU(0.01),
Linear(50,100)
| LeakyReLU(0.01),
---
Linear(100,50),
LeakyReLU(0.01),
Linear(50,15),
LeakyReLU(0.01),
Linear(15,2),
$\sqrt{D}\delta\cdot$L2Normalise(),
Clamp($-\delta,\delta$) For $\ell_{\infty}$
| Linear(2,20),
---
LeakyReLU(0.01),
Linear(20,1),
Sigmoid()

L2Normalise() is a user defined function which projects the input into a unit
circle.

#### Regression:

In similar spirit, we construct the attack network for regression setting as
$\lambda^{f}(x)\coloneqq S(x)\odot H(x)$. (Table 2)

Table 2: Pytorch Architecture for regression setting $f$ | $\lambda^{f}$
---|---
$H$ | $S$
| Linear($D$,50),
---
LeakyReLU(0.01),
Linear(50,20),
nn.LeakyReLU(0.01),
Linear(20,1)
| Linear($D$,50),
---
LeakyReLU(0.01),
Linear(50,50),
LeakyReLU(0.01),
Linear(50,$D$),
$\delta\cdot$L2Normalise()
| Linear(2,20),
---
LeakyReLU(0.01),
Linear(20,1),
Sigmoid()

#### Details for $f_{PGD},\lambda_{PGD}$

For both regression and classification settings $f_{PGD}$ uses the same
architecture as $f$ mentioned in Tables 1,2.
$\lambda_{PGD}$ is generated using (16), with $\gamma=0.01$ with $T=50$ the
total number of iterations/steps. Also, for each sample we try multiple
initialisation, then we choose the best performing attack for each sample
based on which one has the maximum loss. The number of such initialisation or
restarts is set to $10$ in our experiments.

###  D.2 Stabilising effect of $\alpha$

Figure 7: $\ell_{\infty}(\delta)$, Loss contour plot with learnt attack
direction $\lambda^{f}$ compared for $\alpha=0$ (no-original data) vs
$\alpha=0.3,0.6$ ($30\%,60\%$ weightage to original data). Dataset: circles.
Even for unfeasible $\delta\geq 0.25$ (attack strength so large that samples
cross the true decision boundary after perturbation), introducing $\alpha\neq
0$ helps stabilise the EDB