On Neural Network approximation of ideal adversarial attack and
  convergence of adversarial training
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\"older 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.
Rajdeep Haldar, Qifan Song
# On Neural Network approximation of ideal adversarial attack and convergence of adversarial training

###### 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 Holder 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)=\mathrm{ReLU}(x)=\max\{0,x\}\) (rectified linear unit). The network is \(L\)-layer deep and its width is bounded by \(\sup_{l}\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)\).

### 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.

### Problem definition / Notation

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

Let \(f:\mathcal{X}\rightarrow\mathbb{R}^{k}\in\mathcal{C}\) be our model, where \(\mathcal{C}\) is some function class. \(\mathcal{L}:\mathbb{R}^{k}\times\mathcal{Y}\rightarrow\mathbb{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}}\mathbb{E}\mathcal{L}(f(x),y)\), where \(\mathbb{E}=\mathbb{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:\tilde{\mathcal{Y}}\rightarrow\mathcal{X}\in \tilde{\mathcal{C}}:\forall(x,y)\in\tilde{\mathcal{Y}},\,\left\|g(x,y)\right\| _{p}\leq\delta\}, \tag{1}\]

where \(\tilde{\mathcal{C}}\) is some base function class, for instance, the class of continuous functions, spline functions, Holder 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_{\lambda\in\mathcal{F}^{p}_{\delta}(\mathcal{C})} \mathbb{E}\mathcal{L}(f(x+\lambda(x,y)),y). \tag{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_{\|\lambda\|_{p}\leq\delta}\mathcal{L}(f(x+ \lambda),y). \tag{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_{f\in\mathcal{C}}\max_{\lambda\in\mathcal{F}^{p}_{\delta}( \tilde{\mathcal{C}})}\mathbb{E}\mathcal{L}(f(x+\lambda(x,y)),y) \tag{4}\]

where \(\mathbb{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}) \tag{5}\]

### 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}(\mathcal{C})} \mathbb{E}\mathcal{L}(f(x+\lambda),y)\). With some straightforward one can see that the _point wise_ attack (3) is as follows:

\[\lambda^{p.w}(x,y)=\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: \(\mathbb{P}(y=1|x)=p(\beta,x)=\frac{1}{1+e^{-\beta x}}\), i.e., \(y|x\sim\mathrm{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\!\left(p(\hat{\beta},x)\right)-(1-y)\ln\!\left(1-p( \hat{\beta},x)\right)\). 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}). \tag{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})). \tag{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.

### 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 A.5).

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\mathbb{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\mathbb{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)\) 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\mathbb{R}^{+}\}\)) are essentially the equilibria/critical points (\(E=\{x:\nabla F(x)=0\}\)) of \(F\). A classic result in the literature is that for \(T^{gf}\) the set of equilibria _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)=\|\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}\):

\[\arg\max_{x\in\mathcal{X}}F(x),\] \[\text{subject to }g_{i}(x)\leq 0,\quad\forall i\in\{1,\dots,Q\} \tag{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)=\|x-x_{s}\|_{p}^{p}-\delta^{p}\); for \(p=\infty\), we have \(Q=D\) and \(g_{i}(x)=|(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,\delta)}\) (boundary of the \(\ell_{p}\) ball of radius \(\delta\) around \(x_{s}\)).

Let \(\mathbf{J}(x)=(\dots,\mathbb{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). \(\mathbf{J}(x)\) induces an indexing set \(I(x)\subset\{1,\dots,Q\}\) for the active constraints. Define \(\mathbf{C}(x)=[(g_{i}(x))_{i\in I(x)}]\) to be the active constraint matrix and \(D\mathbf{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

\[\mathbf{P}(x)=\mathbf{I}-D\mathbf{C}(x)^{T}(D\mathbf{C}(x)D\mathbf{C}(x)^{T})^{-1}D\mathbf{C}(x).\]

Note when all constraints are inactive, \(\mathbf{C}(x)\) is a null vector and the projection reduces to the identity \(\mathbf{P}(x)=\mathbf{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}=\mathbf{P}(x)\nabla_{x}F(x). \tag{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)=\|x-x_{s}\|_{p}^{p}-\delta^{p}\), \(\mathbf{J}(x)=\mathbb{1}_{g_{1}(x)=0}\) and

\[\mathbf{P}(x)=\mathbf{I}-\mathbf{J}(x)(\|\nabla g_{1}(x)\|_{2}^{2})^{-1}\nabla g_{1}(x) \nabla g_{1}(x)^{T}. \tag{10}\]
When the particle is at the boundary of the \(\ell_{p}\) ball \(B_{p}(x_{s},\delta)\), i.e., \(\mathbf{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 \(\mathbf{J}(x)\neq\mathbf{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(\mathbf{1}-\mathbf{J}(x)), \tag{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_{x}^{pgf}\) is also non-decreasing as \(\dot{F}(x)=\nabla F^{T}(x)\mathbf{P}\nabla F(x)\geq 0\), as \(\mathbf{P}\) is positive semi-definite being a projection.

#### 2.2.4 Deflecting saddle points

One issue with \(T_{x_{s}}^{pgf}\) is that it can't distinguish between saddle points (where \(\nabla_{x}^{2}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_{x}^{2}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_{max}^{\eta}\) corresponding to the maximum eigenvalue of \(\nabla_{x}^{2}F(x)|_{x=\eta}\) to exclude the saddle points from being a stationary point. Therefore, we define a CDS \(\bar{T}_{x_{s}}^{pgf}\) on \(B(x_{s},\delta)\) parameterized by \(x_{s}\) as a solution to the ODE:

\[\dot{x}=\mathbf{P}(x)[\nabla F(x)+\sum_{\eta\in S}\psi_{\epsilon}^{\eta}(x)\nu_{ max}^{\eta}], \tag{12}\]

where \(\epsilon>0\) and \(\psi_{\epsilon}^{\eta}(x)=\exp\Bigl{\{}-\frac{1}{\epsilon^{2}-\|x-\eta\|_{s} ^{2}}\Bigr{\}}\) 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}_{x_{s}}^{pgf}\) can retain all the local smoothness, local optimum, and non-decreasing properties of \(T_{x_{s}}^{pgf}\) 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_{max}^{\eta},\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_{x}^{2}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}_{x}^{pgf}(t)x-x. \tag{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}_{\delta}^{p}\) consisting of regulated functions, therefore, \(\lambda^{pgf}(x,y)\) is also the _best function attack_ over this particular \(\mathcal{F}_{\delta}^{p}\). Details of this \(\mathcal{F}_{\delta}^{p}\) 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).

### 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}_{x}^{pgf}\) 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 \(\mathbf{P}(x)\sum_{\eta\in S}[\psi_{\epsilon}^{\eta}(x)\nu_{max}^{\eta}]\) were added to the original projected gradient flow dynamics \(T_{x}^{pgf}\) (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)=\mathbf{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}=\mathbf{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})), \tag{14}\]

where \(\gamma\) is the step-size and the operator \(\Pi\) is (discrete) analogous to \(\mathbf{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 the form:

\[x^{t+1}=\Pi(x^{t}+\gamma\vec{d}), \tag{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 \(\left|\left|\right|\right|_{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. \(\left|\cdot\right|\right|_{2}\) norm gives \(\vec{d}\propto\nabla F\) which reduces to (14). Steepest ascent w.r.t. \(\left|\cdot\right|_{1}\) gives us \(\vec{d}\propto\nabla F_{i_{max}}\cdot\mathbf{e}^{i_{max}}\) which is essentially a coordinate ascent update step (\(i_{max}=\arg\max_{i}(\nabla F)_{i}\), \(\mathbf{e}^{i}\) is the \(i^{th}\) standard basis vector in \(\mathbb{R}^{D}\)). Steepest ascent w.r.t. \(\left|\left|\right|\right|_{\infty}\) implies \(\vec{d}\propto\text{sign}(\nabla F)\) which is a signed gradient update step. In \(\mathbb{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. \(\left|\cdot\right|\right|_{\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})). \tag{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.

### Motivation for piece-wise Holder 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}_{x}^{pgf}\) (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 \(\mathbf{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_{s}^{o}(x_{0})\) then, \(\lambda^{pgf}(x,y)\) is \(C^{k}\) smooth w.r.t. \(x\in\bigsqcup_{x_{0}\in E}W_{s}^{o}(x_{0})\) for all \(p\), where \(W^{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 Holder space (Definition A.7) w.r.t. \(x\). We can consider the space of piece-wise Holder 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 Holder function and its approximation

**Definition 3.1**.: Let \(\mathbf{A}=\{A_{i}\}\) be any disjoint partition of the domain space \(\mathcal{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 Holder function class iff for some \(\mathbf{A}\), the restriction of the function \(h\) to any piece \(A_{i}\in\mathbf{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.2) 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 \(|a|\leq C|b|\).
* \(a\succ b\) or \(a=\Omega(b)\) denotes there exists a positive constant \(0<C<\infty\) such that \(|a|\geq C|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{\nu}{\nu}},w\geq c_{2}\epsilon^{-\frac{\nu}{\nu}}, \kappa\geq c_{3}\epsilon^{-c_{4}},L=c_{5}\) and a measurable set \(\nu\) with \(\mu(\nu)=\mathcal{O}(\epsilon^{\frac{1}{\nu}})\), 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, \tag{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}\left\|\hat{h}(x)-h(x)\right\|_{\infty}= \mathcal{O}\left(\min(W,w)^{-\omega^{*}/d}\right), \tag{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 Holder 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 Holder 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}_{\delta}^{p}(\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=\mathcal{F}_{\delta}^{p}(\tilde{\mathcal{C}})\) original function space of attacks. Adversarial training to find the robust \((p,\delta)\) model \(f^{*}\) is the sequential mini-max problem:

\[\lambda^{f} =\arg\max_{\lambda\in\Lambda}\mathbb{E}\mathcal{L}(f,\lambda, \mathcal{Z}),\quad\forall f\in\mathcal{C},\] \[f^{*} =\arg\min_{f\in\mathcal{C}}\mathbb{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:

\[\widehat{\lambda}_{n}^{f}\in\Lambda_{n}:\mathbb{E}_{n}\mathcal{L}(f,\widehat{ \lambda}_{n}^{f},\mathcal{Z})\geq\sup_{\lambda\in\Lambda_{n}}\mathbb{E}_{n} \mathcal{L}(f,\lambda,\mathcal{Z})-\eta_{n},\quad\forall f\in\mathcal{C} \tag{19}\]

\[\widehat{f}_{n}\in\mathcal{C}_{n}:\mathbb{E}_{n}\mathcal{L}(\widehat{f}_{n}, \widehat{\lambda}_{n}^{f},\mathcal{Z})\leq\inf_{f\in\mathcal{C}_{n}}\mathbb{ E}_{n}\mathcal{L}(f,\widehat{\lambda}_{n}^{f},\mathcal{Z})+\bar{\eta}_{n}. \tag{20}\]

\(\mathbb{E}_{n}\) is just the empirical expectation over the observed \(n\)-sample data \(\{(x_{i},y_{i})\}_{i=1}^{n},\widehat{\lambda}_{n}^{f},\widehat{f}_{n}\) are empirical epimators of \(\lambda^{f},f^{*}\) respectively. Notice that \(\widehat{\lambda}_{n}^{f},\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}_{n}^{f}\) 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=\mathbb{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:

\[\widehat{\lambda}_{n}\in\Lambda_{n}:\mathbb{E}_{n}\mathcal{L}( \widehat{f}_{n},\widehat{\lambda}_{n},\mathcal{Z}) \geq\sup_{\lambda\in\Lambda_{n}}\mathbb{E}_{n}\mathcal{L}(\widehat{ f}_{n},\lambda,\mathcal{Z})-\eta_{n} \tag{21}\] \[\widehat{f}_{n}\in\mathcal{C}_{n}:\mathbb{E}_{n}\mathcal{L}( \widehat{f}_{n},\widehat{\lambda}_{n},\mathcal{Z}) \leq\inf_{f\in\mathcal{C}_{n}}\mathbb{E}_{n}\mathcal{L}(f,\widehat{ \lambda}_{n},\mathcal{Z})+\widetilde{\eta}_{n} \tag{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}^{f}_{n}\) 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 Holder 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}_{\delta}^{p}(\tilde{\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_ \(\dim_{M}\bar{\mathcal{X}}_{s}=\bar{d}^{*}\leq D\) _(see Def._ A.9 _and_ A.7_), and that_ \(\{\lambda^{f}_{n}:f\in\mathcal{C}\}\subset\Lambda\) _on support_ \(\mathcal{X}_{s}\subset[0,1]^{D}\) _with_ \(\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^{*},\lambda^{\prime},\mathcal{ Z})\prec\|f-f^{\prime}\|_{\widetilde{\mathcal{X}}}+\|\lambda-\lambda^{\prime}\|_{ \mathcal{X}},\] _where_ \(\|\|_{\mathcal{X}}\)_,_ \(\|\|_{\widetilde{\mathcal{X}}}\) _are the supremum norms over the supports_ \(\mathcal{X},\widetilde{\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^{*}\|_{\widetilde{ \mathcal{X}}}^{2}\] _for any_ \(\widetilde{\mathcal{X}}\subset\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\|_{\widetilde{\mathcal{X}}}^{2}+ \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{r}^{*}} {\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},\bar{w}_{n})\) and \(\mathcal{C}_{n}=\mathcal{F}_{\sigma}(\underline{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 Holder 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 Holder 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 Holder 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.

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.
```
Initialize: \(t\gets 0,h\gets 0,p\gets 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\gets p+1\) endwhile while\(h\leq H\)do \(\theta_{\lambda}\leftarrow\theta_{\lambda}+\tilde{\gamma}\nabla_{\theta_{\lambda}} \sum_{i=1}^{n}\mathcal{L}(f,\lambda^{f},(x_{i},y_{i}))\) \(h\gets h+1\) endwhile \(p\gets 0,h\gets 0,t\gets t+1\) endwhile
```

**Algorithm 1** Adversarial Training

## 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}\mathbb{1}_{y=j}\log\mathrm{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}\mathbb{1}_{y=j}\log\mathrm{Softmax}(f(x+\lambda^{f}(x,y)))_{j}\). Here, \(C\) is the number of classes.

### Gradient flow and Neural Network attack direction

Figure 0(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}}\mathbb{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 0(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 0(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 Holder function space (Theorem 3.1) where the theoretical best attack resides.

Figure 0(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 0(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 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.

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.
### 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 \(\mathbb{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. 1 Furthermore, the PGD attack is a white box attack, while our \(\lambda_{f}\) is a _semi-white box_ attack.

Footnote 1: PGD, 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/fhladrpartos/Adversarial-MF-simification/Yiob/main/vtili.py](https://github.com/fhladrpartos/Adversarial-MF-simification/Yiob/main/vtili.py)

### 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},\tilde{\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)=\left\|f(x)-y\right\|_{2}^{2}\). The corresponding adversarial loss being \(\mathcal{L}(f,\lambda^{f},(x,y))=\mathcal{L}(f(x+\lambda^{f}(x,y)),y)=\left\| f(x+\lambda^{f}(x))-y\right\|_{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}\).

## 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})=\mathbb{E}\mathcal{L}(f(x+\lambda^{f} (x,y)),y)\rightarrow\mathbb{E}(1-\alpha)\mathcal{L}(f(x+\lambda^{f}(x,y)),y) +\alpha\mathcal{L}(f(x),y) \tag{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.

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.**
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})=\mathbb{E}(1-\alpha)\mathcal{L}(f(x+ \lambda^{f}(x,y)),f(x))+\alpha\mathcal{L}(f(x),y). \tag{24}\]

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

#### 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}\mathbb{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,\left\|G(x)\right\|_{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}\mathbb{E}-\mathcal{L}_{adv}-c_{1}\mathcal{L}_{GAN}(D^{*})-c_{2} \mathcal{L}_{hinge}\), where \(D^{*}_{G}=\arg\max_{D}\mathbb{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_{\left\|\lambda\right\|_{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} (\left\|\lambda\right\|_{2}-\delta).\]

When \(\left\|\lambda_{2}\right\|\leq\delta\), the optimal solution can be achieved for \(c^{\prime}_{2}=0\); when \(\left\|\lambda_{2}\right\|>\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, \left\|\lambda\right\|_{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.

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
## 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 Holder 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.
