Information-theoretically Safe Bias Classifier Against Adversarial Attacks

## Abstract

Abstract In this paper, the bias classifier is introduced, that is, the bias part
of a DNN with Relu as the activation function is used as a classifier.
The work is motivated by the fact that
the bias part is a piecewise constant function with zero gradient and hence cannot be
directly attacked by gradient-based methods to generate adversaries, such as FGSM.
The existence of the bias classifier is proved and an effective training method
for the bias classifier is given.
It is proved that by adding a proper random first-degree part to the bias classifier, an information-theoretically safe classifier against the original-model gradient attack is obtained
in the sense that the attack will generate a totally random attacking direction.
This seems to be the first time that the concept of information-theoretically safe classifier is proposed.
Several attack methods for the bias classifier are proposed
and numerical experiments are used to show that
the bias classifier is more robust than DNNs with similar size against these attacks in most cases. Keywords. Robust DNN,
adversarial samples,
bias classifier,
information-theoretically safe,
gradient-based attack.

## 1 Introduction

The deep neural network (DNN) [] has become the most powerful machine learning method, which has been successfully applied in computer vision, natural language processing,
game playing,
protein structure prediction,
and many other fields.

A major weakness of DNNs is the existence of adversarial samples [], that is, it is possible to intentionally make small modifications to an input such that human can still recognize the input clearly, but the DNN outputs a wrong label or even any label given by the adversary.
Existence of adversary samples makes the DNN vulnerable in safety-critical applications.
Although many effective methods to defend adversaries were proposed [, , , ], it was shown that adversaries are still inevitable for current DNNs [, ].
In  [], it was proved that adversarial attacks
always exist for any successful DNNs under certain conditions.
In this paper, we present a new approach by using the bias part of the DNN as the classifier
and show that the bias classifier is safe against gradient-based attacks.

### 1.1 Contributions

Let ${\mathbb{I}}=[0,1]\subset{\mathbb{R}}$ and
${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ a classification DNN for $m$ objects, using Relu as the activation function.
For any $x\in{\mathbb{I}}^{n}$, there exist $W_{x}\in{\mathbb{R}}^{m\times n}$ and $B_{x}\in{\mathbb{R}}^{m}$ such that

$$ ${\mathcal{F}}(x)=W_{x}x+B_{x}$ $$

where $W_{x}x$ is called the first-degree part and $B_{x}$ the bias part of ${\mathcal{F}}$.
From the definition of Relu,
the bias part

$$ $B_{\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ $$

defined as $B_{\mathcal{F}}(x)=B_{x}$ is
a piecewise constant function with a finite number of values.

The most popular and effective methods to generate adversaries,
such as FGSM [] or PGD [], use $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ to make the loss function bigger.
An attack on DNNs only using the values of ${\mathcal{F}}(x)$ and $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ is called a gradient-based attack.
Since $n$ is generally quite large, using $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ to find
adversaries in the high-dimensional space ${\mathbb{R}}^{n}$ seems inevitable.

Motivated by the above observation,
the bias classifier is introduced in this paper,
that is, the bias part
$B_{\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ of ${\mathcal{F}}$ is used to classify the $m$ objects.
Since $B_{\mathcal{F}}$ is a piecewise constant function, it has zero gradients
and is safe against direct gradient-based attacks.
The contributions of this paper are summarized below.

First, the existence of the bias classifier is proved.
Precisely, it is shown that for any classification problem,
there exists a DNN ${\mathcal{F}}$ such that its bias part $B_{\mathcal{F}}$ gives the correct
label with arbitrarily high probability.

Second, an effective training method for the bias classifier is proposed.
It is observed that the adversarial training method introduced in []
significantly increases the classification power of the bias part.
Furthermore, using the adversarial training to the loss function
$L_{{\hbox{\scriptsize\rm{CE}}}}(B_{{\mathcal{F}}}(x),y)+\gamma L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x),y)$
increases the classification power of the bias part
and decreases the classification power of first-degree part of ${\mathcal{F}}$,
and hence is used to train the bias classifier.

Third, an information-theoretically safe bias classifier against gradient-based attacks is given.
A network ${\mathcal{F}}$ is called information-theoretically safe against an attack ${\mathcal{A}}$,
if when generate an adversary for a sample $x$ with ${\mathcal{A}}$,
a random attack direction is given.
In other words, the rate to generate adversaries with ${\mathcal{A}}$ equals
the rate of random samples to be adversaries.
Let $W\in{\mathbb{R}}^{m\times n}$ be a matrix with certain random entries,
${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ a trained bias classifier,
and $\widetilde{{\mathcal{F}}}(x)={\mathcal{F}}(x)+Wx$.
Then, it is shown that $B_{\widetilde{{\mathcal{F}}}}$ is information-theoretically safe against the gradient-based attack of $\widetilde{{\mathcal{F}}}$, if the structure and parameters of ${\mathcal{F}}$ are kept secret.
The notion of information-theoretically safe
is borrowed from cryptography [], which means
that the ciphertext yields no information regarding the plaintext
for cyphers which are perfectly random.

Fourth, several methods to attack the bias classifier are proposed.
Experiments with MNIST and CIFAR-10 show that
the bias classifier has comparable accuracies with DNNs on the test sets
and
is more robust than DNNs of similar sizes against these adversarial attacks in most cases.

### 1.2 Related work

There exist two main approaches to obtain more robust DNNs:
using a better training method
or a better structured DNN.
Of course, the two approaches can be combined.

Many effective methods were proposed to train more robust DNNs to defend adversaries [, , , ].
The adversarial training method proposed by Madry et al []
can reduce adversaries significantly,
where the value of the loss function of the worst adversary in a small neighborhood of
the training sample is minimized.
A similar approach is to generate adversaries and
add them to the training set [].
A fast adversarial training algorithm was proposed,
which improves the training efficiency by reusing the backward pass calculations [].
A less direct approach to resist adversaries is to make the DNN more stable
by introducing the Lipschitz constant or $L_{p,\infty}$ regulations of each
layer [, , , ].
Adding noises to the training data is an effective way to increase
the robustness [].
Knowledge distilling is also used to enhance robustness and defend adversaries [].

In this paper, the adversarial training [] is
used to a new loss function to train the bias classifier.

Many effective new structures for DNNs were proposed to defend adversaries.
The ensembler adversarial training [] was introduced
for CNN models, which can apply to large datasets such as ImageNet.
In [], a denoising layer is added to each hidden layer to defend adversarial attack.
In [], difference-privacy noise layers are added to defend adversaries.
In [], a low-rank DNN is shown to be more robust.
In [], a classification-autoencoder was proposed, which is robust against
outliers and adversaries.
In [], it was observed that by taking average values of points
in a small neighbourhood of an input can give a larger robust region for the input.
In [, ], strategies to defend adversarial attacks by modifying the input were given.

In this paper, a new idea to obtain robust DNNs is given, that is, the
bias part is used as the classifier to avoid gradient-based attacks.
Another advantage of using the bias part as the classifier is that,
an information-theoretically safe classifier can be constructed.
Our network does not deliberately hide the gradient like the method in [].
Our network does not have gradient, so the white box attack method for the gradient hiding method in [] does not work for our model.

The rest of this paper is organized as follows.
In section [2](#S2), the existence of the bias classifier is proved
and the training method is given.
In section [3](#S3), several attack methods for the bias classifier
are given.
In section [4](#S4), the bias classifier is shown to be
information-theoretically safe against the original-model gradient-based attack.
In section [5](#S5), numerical experimental results are given
to show that the bias classifier indeed improves robustness to resist adversaries.
In section [6](#S6), conclusions are given.

## 2 Bias Classifier

In this section, we prove the existence of a DNN ${\mathcal{F}}$ such that
the bias part of ${\mathcal{F}}$ can be used as a classifier.
We also give a training algorithm for the new classifier.

### 2.1 The standard DNN

Let ${\mathbb{I}}=[0,1]\subset{\mathbb{R}}$ and $[n]=\{1,\ldots,n\}$ for $n\in{\mathbb{N}}_{>0}$.
Let ${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ be a
classification DNN with $L$ hidden layers
and the label set ${\mathbb{L}}=[m]$.
Each hidden-layer of ${\mathcal{F}}$ uses Relu as activity functions
and the output layer does not have activity functions. We write ${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ as

$$ $\begin{array}[]{ll}x_{0}\in{\mathbb{I}}^{n},n_{0}=n,n_{L+1}=m,\\ x_{l}={\hbox{\rm{Relu}}}(W_{l}x_{l-1}+b_{l})\in{\mathbb{R}}^{n_{l}},l\in[L],\\ {\mathcal{F}}(x_{0})=x_{L+1}=W_{L+1}x_{L}+b_{L+1},\\ \end{array}$ (1) $$

where $W_{l}\in{\mathbb{R}}^{n_{l}\times n_{l-1}},b_{l}\in{\mathbb{R}}^{n_{l}}$.
Denote $\Theta_{\mathcal{F}}=\{W_{l},b_{l}\}_{l=1}^{L+1}$ to be the parameter set of ${\mathcal{F}}$.
Given a training set ${\mathcal{S}}$, the network ${\mathcal{F}}$ can be trained by solving the following optimization problem with BP

$$ $\min_{\Theta}\sum_{(x,y)\in{\mathcal{S}}}L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x),y).$ (2) $$

For any $x\in{\mathbb{I}}^{n}$, there exist $W_{x}\in{\mathbb{R}}^{m\times n}$ and $B_{x}\in{\mathbb{R}}^{m}$, such that ${\mathcal{F}}(x)=W_{x}x+B_{x}$.
We define the first-degree part of ${\mathcal{F}}$ to be $W_{{\mathcal{F}}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$, that is $W_{{\mathcal{F}}}(x)=W_{x}x$; and the bias part of ${\mathcal{F}}$ to be $B_{{\mathcal{F}}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$, that is $B_{{\mathcal{F}}}(x)=B_{x}$.
It is easy to see that

$$ ${\mathcal{F}}(x)=W_{{\mathcal{F}}}(x)+B_{{\mathcal{F}}}(x)=W_{x}x+B_{x}.$ (3) $$

For a label $i\in[m]$ and $x\in{\mathbb{I}}^{n}$, denote ${\mathcal{F}}_{i}(x)$ to be the $i$-th coordinate of
${\mathcal{F}}(x)$.

A linear region of ${\mathcal{F}}$ is a maximal connected open subset of the input space ${\mathbb{I}}^{n}$, on which ${\mathcal{F}}$ is linear [].
On each linear region $A$ of ${\mathcal{F}}$, there exist $W_{A}\in{\mathbb{R}}^{m\times n}$ and $B_{A}\in{\mathbb{R}}^{m}$, such that ${\mathcal{F}}(x)=W_{A}x+B_{A}$ for $x\in A$.
Due to the property of Relu function, it is clear that ${\mathcal{F}}$ has a finite number of disjoint linear regions
and ${\mathbb{I}}^{n}$ is the union of the closures of these linear regions.

### 2.2 Existence of bias classifier

In this section, we will prove the existence of the bias classifier.
Let ${\mathbb{O}}\subset{\mathbb{I}}^{n}$ be the objects to be classified.
For $x\in{\mathbb{O}}$ and $r\in{\mathbb{R}}_{>0}$, when $r$ is small enough, all images in

$$ ${\mathbb{B}}(x,r)=\{x+\eta\,|\,\eta\in{\mathbb{R}}^{n},||\eta||<r\}$ $$

can be considered to have the same label with $x$.
Therefore, the object ${\mathbb{O}}$ to be classified may be considered
as bounded open sets in ${\mathbb{I}}^{n}$.
This observation motivates the following existence theorem, whose proof is given in Appendix A.

###### Theorem 2.1 .

Let ${\mathbb{O}}=\bigcup_{i=1}^{m}O_{i}\subset{\mathbb{I}}^{n}$ be the elements to be classified
and ${\mathbb{L}}=\{l\}_{l=1}^{m}$ the label set,
where $O_{i}\subset{\mathbb{I}}^{n}$ is an open set,
$O_{i}\bigcap O_{j}=\phi$ if $i\neq j$,
and $x$ has label $l$ for $x\in O_{l}$.
Then for any $\epsilon>0$, there exist a DNN ${\mathcal{F}}$ and an open set $D\subset{\mathbb{I}}^{n}$ with volume $V(D)<\epsilon$,
such that $B_{{\mathcal{F}}}(x)$ gives the correct label for $x\in{\mathbb{O}}\setminus D$,
that is, the $l$-th coordinate of ${\mathcal{F}}(x)$ has the biggest value for $x\in O_{l}$.

A network ${\mathcal{F}}$ satisfying the conditions of Theorem [2.1](#S2.Thmtheorem1) gives
a bias classifier $B_{\mathcal{F}}$, which can be computed from ${\mathcal{F}}$ as follows:

$$ $B_{{\mathcal{F}}}(x)={\mathcal{F}}(x)-W_{{\mathcal{F}}}(x)={\mathcal{F}}(x)-\frac{\nabla{\mathcal{F}}(x)}{\nabla x}\cdot x.$ (4) $$

###### Theorem 2.1 .

### 2.3 Training the bias classifier

In order to increase the robustness of the network, we will use
the adversarial training introduced in [], which is one of the
best practical training method to defend adversaries.
Let $(x,y)$ be a data in the training set ${\mathcal{S}}$.
Then the adversarial training is to solve

$$ $\min_{\Theta}\max_{||\zeta||<\varepsilon}\sum_{(x,y)\in{\mathcal{S}}}L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x+\zeta),y)$ (5) $$

where $\varepsilon\in{\mathbb{R}}_{>0}$ is a given small real number.
In order to increase the power of the bias part $B_{\mathcal{F}}$, we use the following training method

$$ $\min_{\Theta}\max_{||\zeta||<\varepsilon}\sum_{(x,y)\in{\mathcal{S}}}[L_{{\hbox{\scriptsize\rm{CE}}}}(B_{{\mathcal{F}}}(x+\zeta),y)+\gamma L_{{\hbox{\scriptsize\rm{CE}}}}({\mathcal{F}}(x+\zeta),y)]$ (6) $$

where $\gamma$ is a super parameter.
The training procedure is given in Algorithm [1](#alg1).

We first use a simple example to show that the adversarial training can increase
the classification power of $B_{\mathcal{F}}$.
The accuracies of ${\mathcal{F}}$, $W_{{\mathcal{F}}}$, $B_{{\mathcal{F}}}$ on the test set for
three kinds of training methods are given in Table [1](#S2.T1), respectively.
More comprehensive numerical experiments are given in section [5](#S5).

**Table 1: Accuracies of network Lenet-5 for MNIST**
|  | $W_{{\mathcal{F}}}$ | $B_{{\mathcal{F}}}$ | ${\mathcal{F}}$ |
| --- | --- | --- | --- |
| Normal training ([2](#S2.E2)) | 98.80$\%$ | $15.62\%$ | 99.09$\%$ |
| Adversarial training ([5](#S2.E5)) | 90.61$\%$ | $98.77\%$ | 99.19$\%$ |
| Adversarial training ([6](#S2.E6)) | 0.28$\%$ | 99.09 $\%$ | 99.43$\%$ |

Figure: Algorithm 1 BCTrain

## 3 Attack methods for the bias classifier

In this section, several possible methods to attack the bias classifier are given.

### 3.1 Safety against gradient-based attack

The most popular methods to generate adversaries, such as FGSM [] or PGD [], use $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ to make the loss function bigger.
More precisely, adversaries are generated as follows

$$ $x\to x+\varepsilon{\hbox{\rm{sign}}}(\frac{\nabla L_{CE}({\mathcal{F}}(x),y)}{\nabla x})$ (7) $$

for a small parameter $\varepsilon\in{\mathbb{R}}_{>0}$.
It is easy to see that, $\frac{\nabla L_{CE}({\mathcal{F}}(x),y)}{\nabla x}$
can be obtained from $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$.
So, in the above attack, only the values of ${\mathcal{F}}(x)$ and
$\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ are needed
and the detailed structure of ${\mathcal{F}}$ is not needed.
Motivated by this fact, we introduce the concept of gradient-based attack.
A DNN model is called a gradient-based model,
if for $x\in{\mathbb{I}}^{n}$, the values of ${\mathcal{F}}(x)$ and $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$
are known, but the detailed structure of ${\mathcal{F}}$ is not known.
Correspondingly, an attack only uses the values of ${\mathcal{F}}(x)$ and $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ is called gradient-based attack.

Since the derivative of $B_{\mathcal{F}}$ is always zero,
a gradient-based attack against $B_{\mathcal{F}}$ becomes a black-box attack,
and in this sense we say that the bias classifier is safe against the gradient-based attack.

In the gradient-based model, we do not know the structure of ${\mathcal{F}}$, but we can calculate $B_{{\mathcal{F}}}(x)$ from $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ using ([4](#S2.E4)),
and the bias classifier still works.

### 3.2 Original-model attack

An obvious attack for the bias classifier is to create
adversaries of $B_{\mathcal{F}}$ using the gradients of ${\mathcal{F}}$, which is called original-model attack. The attack is given in Algorithm 2, where $\widehat{B}_{{\mathcal{F}}}(x)$ is the label of $B_{{\mathcal{F}}}(x)$.

Figure: Algorithm 2 OAttack

### 3.3 Correlation attack on the bias classifier

From numerical experiments, we have the following observations.
For a network ${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ trained with ([6](#S2.E6)) and a small vector $\epsilon\in{\mathbb{R}}^{n}$,
the following fact happens with high probability:
$W_{{\mathcal{F}}}(x)[l]\geq W_{{\mathcal{F}}}(x^{\prime})[l]$ is valid
if and only if $B_{{\mathcal{F}}}(x)[l]\leq B_{{\mathcal{F}}}(x^{\prime})[l]$ is valid,
where $l\in{\mathbb{L}}$ and $x^{\prime}=x+\epsilon$.
In other words, $W_{{\mathcal{F}}}$ and $B_{{\mathcal{F}}}$ are co-related
and we thus can decrease $B_{\mathcal{F}}[l]$ by increasing $W_{{\mathcal{F}}}[l]$,
which is called the correlation attack.

In the correlation attack, we create adversaries by making
$W_{{\mathcal{F}}}(x)[y]-W_{\mathcal{F}}(x)[i]$ bigger, where $y$ is the label of $x$, $i\in[m]$ and $i\neq y$.
The attack is given in Algorithm 3.

Figure: Algorithm 3 CAttack

## 4 Information-theoretically safety against original-model gradient-based attack

By the original-model gradient-based attack, we mean using the gradient of ${\mathcal{F}}$
to generate adversaries for $B_{\mathcal{F}}$.
In this section, we show that it is possible to make
the bias classifier safe against this kind of attack.
The idea is to make $\frac{\nabla{\mathcal{F}}(x)}{\nabla x}$ random and
$B_{\mathcal{F}}$ still gives the correct classification.

### 4.1 Information-theoretically safety

In this section, we will define the concept of
information-theoretically safety of a DNN against an attack.

Let ${\mathcal{F}}$ be a DNN defined in ([1](#S2.E1)).
Motivated by the FGSM attack ([7](#S3.E7)), we assume that
the attack ${\mathcal{A}}(x,{\mathcal{F}},\rho):{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ generates an adversary of $x$ as below:

$$ ${\mathcal{A}}(x,{{\mathcal{F}}},\rho)=x+\rho\,V$ (8) $$

where $\rho\in{\mathbb{R}}_{>0}$ and $V\in\{-1,1\}^{n}$ is the sign vector of certain quantity related with the gradient of ${\mathcal{F}}(x)$.

The attack ${\mathcal{A}}(x,{{\mathcal{F}}},\rho)$ is called
information-theoretically safe, if
$V=({\mathcal{A}}(x,{{\mathcal{F}}},\rho)-x)/\rho$ is a random vector in $\{-1,1\}^{n}$
for any input $x$.

We now show how to build an information-theoretically safe bias classifier.
First train a DNN ${\mathcal{F}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ with the method in Section [2.3](#S2.SS3).
Let $W_{R}\in{\mathbb{R}}^{m\times n}$ satisfy
a given distribution ${\mathcal{M}}$ of random matrices in ${\mathbb{R}}^{m,n}$ and

$$ $\begin{array}[]{l}\widetilde{{\mathcal{F}}}(x)={\mathcal{F}}(x)+W_{R}x=(W_{x}+W_{R})x+B_{x}\\ B_{\widetilde{{\mathcal{F}}}}(x)=\widetilde{{\mathcal{F}}}(x)-\frac{\nabla{\widetilde{{\mathcal{F}}}(x)}}{\nabla x}\cdot x.\end{array}$ (9) $$

It is easy to see that $B_{\widetilde{{\mathcal{F}}}}=B_{{\mathcal{F}}}$,
that is, the bias classifiers for ${\mathcal{F}}$ and $\widetilde{{\mathcal{F}}}$ are the same.
On the other hand, $\frac{\nabla{\widetilde{{\mathcal{F}}}}(x)}{\nabla x}=\frac{\nabla{\mathcal{F}}(x)}{\nabla x}+W_{R}$ is random in certain sense.

The safety of $B_{\widetilde{{\mathcal{F}}}}$ against the attack
${\mathcal{A}}(x,{\widetilde{{\mathcal{F}}}},\rho)$
can be measured by the following adversary creation rate

$$ $\begin{array}[]{l}{\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}},{\mathcal{M}})={\mathbb{E}}_{W_{R}\sim{\mathcal{M}}}[{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}[{\mathbf{I}}(\widehat{B}_{{{\mathcal{F}}}}({\mathcal{A}}(x,\widetilde{{\mathcal{F}}},\rho))\neq\widehat{B}_{{{\mathcal{F}}}}(x))]]\end{array}$ (10) $$

where $\widehat{B}_{{\mathcal{F}}}$ is the label of the classification
and ${\mathcal{D}}_{{\mathbb{O}}}$ is the distribution of the objects to be classified.

If $B_{\widetilde{{\mathcal{F}}}}$ is
information-theoretically safe against the attack ${\mathcal{A}}(x,{\widetilde{{\mathcal{F}}}},\rho)$,
then it is easy to show that ${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}},{\mathcal{M}})$ equals

$$ $\begin{array}[]{l}{\mathcal{C}}({\mathcal{F}},\rho)=\frac{1}{2^{n}}{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}\sum_{V\in\{-1,1\}^{n}}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho\,V)\neq\widehat{B}_{{\mathcal{F}}}(x))]\end{array}$ (11) $$

which depends only on ${\mathcal{F}}$ and $\rho$ and will be used as a measure of the robustness of the bias classifier.

Note that ${\mathcal{C}}({\mathcal{F}},\rho)$ is the rate of adversaries in certain random samples.
In other words, if $B_{\widetilde{{\mathcal{F}}}}$ is information-theoretically safe under attack ${\mathcal{A}}$,
then the adversary creation rate of $B_{\widetilde{{\mathcal{F}}}}$ under attack ${\mathcal{A}}$
is equal to the rate of random samples to be adversaries,
which is very small as shown in section [5.3.1](#S5.SS3.SSS1).

If $B_{\widetilde{{\mathcal{F}}}}$ is not information-theoretically safe, we can use the value
${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}},{\mathcal{M}})/{\mathcal{C}}({\mathcal{F}},\rho)$ to measure
the safety of $B_{\widetilde{{\mathcal{F}}}}$ relative to the information-theoretically safety.

### 4.2 Safety against direct attack

In this section, we show that $B_{\widetilde{{\mathcal{F}}}}$ defined
in ([9](#S4.E9)) is safe
against the direct attack [] of $\widetilde{{\mathcal{F}}}$.

Let ${\mathcal{U}}(a,b)$ be the uniform distribution in $[a,b]\subset{\mathbb{R}}$.
For $\lambda\in{\mathbb{R}}_{>0}$, denote ${\mathcal{M}}_{m,n}(\lambda)$ to be the random matrices
such that the elements of their $i$-row are in
$({\mathcal{U}}(-2i\lambda,-(2i-1)\lambda)\cup{\mathcal{U}}((2i-1)\lambda,2i\lambda))^{m\times n}.$

Let $||x||_{-\infty}=\min_{i\in[n]}\{|x_{i}|\}$ for $x\in{\mathbb{R}}^{n}$.
It is easy to see that for $W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$,
we have $||W_{R,i}-W_{R,j}||_{-\infty}>\lambda$ for $i\neq j$,
where $W_{R,i}$ is the $i$-th row of $W_{R}$.

For $\rho\in{\mathbb{R}}_{>0}$,
consider the following gradient-based direct attack [] for
the network ${{\mathcal{F}}}$:

$$ $\begin{array}[]{ll}{\mathcal{A}}_{1}(x,{{\mathcal{F}}},\rho)=x+\rho\,{\hbox{\rm{sign}}}(\frac{\nabla{{\mathcal{F}}}_{n_{x}}(x)}{\nabla x}-\frac{\nabla{{\mathcal{F}}}_{y}(x)}{\nabla x})\\ \end{array}$ (12) $$

where $y$ is the label of $x$
and $n_{x}=\arg\max_{i\neq y}\{{{\mathcal{F}}}_{i}(x)\}$.

###### Theorem 4.1 .

Let $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\lambda/2$
and $W_{R}\in{\mathcal{M}}_{m,n}(\lambda)$.
If the structure and parameters of ${\mathcal{F}}$ are kept secret, then
$B_{\widetilde{{\mathcal{F}}}}$ is information-theoretically safe against the attack
${\mathcal{A}}_{1}(x,\widetilde{{\mathcal{F}}},\rho)$.

###### Proof.

From ([3](#S2.E3)) and ([9](#S4.E9)),
$\frac{\nabla\widetilde{{\mathcal{F}}}(x)}{\nabla x}=W_{x}+W_{R}$.
Let $W_{R,i}$ and $W_{x,i}$ be the $i$-rows of $W_{R}$ and $W_{x}$, respectively.
If $W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$, then $||W_{R,i}-W_{R,j}||_{-\infty}>\lambda$ for $i\neq j$.
Since $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}=|W_{x}|_{\infty}<\lambda/2$, we have
$||W_{x,i}-W_{x,j}||_{\infty}<\lambda$ for $i\neq j$.
Then,

$$ $\begin{array}[]{ll}&{\mathcal{A}}_{1}(x,\widetilde{{\mathcal{F}}},\rho)\\ &=x+\rho\,{\hbox{\rm{sign}}}(\frac{\nabla\widetilde{{\mathcal{F}}}_{n_{x}}(x)}{\nabla x}-\frac{\nabla\widetilde{{\mathcal{F}}}_{y}(x)}{\nabla x})\\ &=x+\rho\,{\hbox{\rm{sign}}}(W_{x,n_{x}}-W_{x,y}+W_{R,n_{x}}-W_{R,y})\\ &=x+\rho\,{\hbox{\rm{sign}}}(W_{R,n_{x}}-W_{R,y}).\\ \end{array}$ (13) $$

Since $W_{R}\in{\mathcal{M}}_{m,n}(\lambda)$, $\widehat{W}=W_{R,n_{x}}-W_{R,y}$ is a random vector whose entries
having values in two intervals of the form $[-b_{2},-b_{1}]\cup[b_{1},b_{2}]$,
${\hbox{\rm{sign}}}(\widehat{W})$ is a random vector in $\{-1,1\}^{n}$
and the theorem is proved.
∎

###### Theorem 4.1 .

###### Proof.

### 4.3 Safety against FGSM attack

In this section, we show that the result in section [4.2](#S4.SS2) holds for the FGSM attack if $m=2$.
Here is the FGSM attack:

$$ ${\mathcal{A}}_{2}(x,{\mathcal{F}},\rho)=x+\rho\,{\hbox{\rm{sign}}}(\frac{\nabla L({{\mathcal{F}}}(x),y)}{\nabla x}).$ (14) $$

###### Theorem 4.2 .

If $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\lambda/2$, $W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$,
and $m=2$, then
$B_{\widetilde{{\mathcal{F}}}}$ is information-theoretically safe against the attack
${\mathcal{A}}_{2}(x,\widetilde{{\mathcal{F}}},\rho)$.

###### Proof.

Let $y\in\{0,1\}$ be the label of $x$.
Use the notations introduced in the proof of Theorem [4.1](#S4.Thmtheorem1).
Since the loss function is $L_{CE}$ and $m=2$, we have

$$ $\begin{array}[]{ll}&\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}\\ =&\frac{\sum_{i=1}^{m}{e^{\widetilde{{\mathcal{F}}}_{i}}}(W_{x,i}-W_{x,y}+W_{R,i}-W_{R,y})}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}\\ =&\frac{e^{\widetilde{{\mathcal{F}}}_{1-y}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}(W_{x,1-y}-W_{x,y}+W_{R,1-y}-W_{R,y}).\\ \end{array}$ (15) $$

The last equality comes from $m=2$.
Since $||W_{x,i}-W_{x,j}||_{\infty}<\lambda$ and $||W_{R,i}-W_{R,j}||_{-\infty}>\lambda$
for $i\neq j$,
we have
${\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x})={\hbox{\rm{sign}}}(W_{R,1-y}-W_{R,y})$ which is a random vector in $\{-1,1\}^{n}$,
similar to the proof of Theorem [4.1](#S4.Thmtheorem1).
The theorem is proved.
∎

When $m>2$, we have the following result, whose proof is given in Appendix B.

###### Theorem 4.3 .

Assume $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\mu/2$,
$|B_{{\mathcal{F}}}(x)|_{\infty}<\beta$,
and $\lambda\in{\mathbb{R}}_{>0}$ satisfying $(\lambda-\mu)e^{-2\beta-n\mu+\sqrt{\lambda}}>(2m\lambda+\mu)m$.
Furthermore, assume the samples are normalized, that is, $|x|_{\infty}=1$.
If $W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$, then
${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{2},{\mathcal{M}}_{m,n}(\lambda))\leq(m-1){\mathcal{C}}({\mathcal{F}},\rho)+\frac{(m-2)^{2}}{\sqrt{\lambda}}$.

We can choose a large $\lambda$ to make the term $\frac{(m-2)^{2}}{2\sqrt{\lambda}\eta}$ small. So from Theorem [4.3](#S4.Thmtheorem3), $B_{\widetilde{{\mathcal{F}}}}$ is approximately safe if $m$ is small.

###### Theorem 4.2 .

###### Proof.

###### Theorem 4.3 .

### 4.4 Safety against direct attack under simpler distribution

Let ${\mathcal{U}}_{m,n}(\lambda)$ be the random matrices whose entries are in ${\mathcal{U}}(-\lambda,\lambda)$.
In this section, we show that the result in section [4.2](#S4.SS2)
is approximately valid for the simpler distribution ${\mathcal{U}}_{m,n}(\lambda)$.
We consider the $k$-step direct attack:

$$ $\begin{array}[]{l}x^{(0)}=x\\ x^{(i)}=x^{(i-1)}+\frac{\rho}{k}\,{\hbox{\rm{sign}}}(\frac{\nabla{\mathcal{F}}_{n_{x}}(x^{(i-1)})}{\nabla x^{(i-1)}}-\frac{\nabla{\mathcal{F}}_{y}(x^{(i-1)})}{\nabla x^{(i-1)}}),i\in[k]\\ {\mathcal{A}}_{3}(x,{\mathcal{F}},\rho)=x^{(k)}\\ \end{array}$ (16) $$

where $y$ is the label of $x$ and $n_{x}=\arg\max_{i\neq y}\{{\mathcal{F}}_{i}(x)\}$.

###### Theorem 4.4 .

If $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\mu/2$
and $W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)$, then
${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\leq{\mathcal{C}}({\mathcal{F}},\rho)+\mu n/\lambda$.
Furthermore, if $\lambda>n\mu/\epsilon$, then ${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\leq{\mathcal{C}}({\mathcal{F}},\rho)+\epsilon$
for any $\epsilon\in{\mathbb{R}}_{>0}$,
and in particular, if $\lambda>na/(\epsilon{\mathcal{C}}({\mathcal{F}},\rho))$, then ${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\leq(1+\epsilon){\mathcal{C}}({\mathcal{F}},\rho)$.

Proof of Theorem [4.4](#S4.Thmtheorem4) is given in Appendix C.
Theorem [4.4](#S4.Thmtheorem4) implies that $B_{\widetilde{{\mathcal{F}}}}$ can be made close to information-theoretically safe under attack ${\mathcal{A}}_{3}(x,\widetilde{{\mathcal{F}}},\rho)$.

###### Theorem 4.4 .

### 4.5 Safety against FGSM under simpler distribution

In this section, we show that the result in section [4.3](#S4.SS3)
is approximately valid for the simpler distribution ${\mathcal{U}}_{m,n}(\lambda)$.
Let ${\mathcal{A}}_{2}$ be the attack in ([14](#S4.E14)). Then we have

###### Theorem 4.5 .

If $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\mu/2$,
$W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)$, and $m=2$, then
${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))\leq e^{n\mu/\lambda}{\mathcal{C}}({\mathcal{F}},\rho)$.
Furthermore, if $\lambda>n\mu/\ln(1+\epsilon)$,
then ${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))\leq(1+\epsilon){\mathcal{C}}({\mathcal{F}},\rho)$.

For the general $m$, we have

###### Theorem 4.6 .

Assume $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\mu/4$, $|B_{{\mathcal{F}}}(x)|_{\infty}<\beta$, and $\lambda\in{\mathbb{R}}_{>0}$ satisfying $\mu e^{-2\beta-n\mu/2+\sqrt{\lambda}}>2(2\lambda+\mu)m$.
Furthermore, assume the samples are normalized, that is, $|x|_{\infty}=1$.
If $W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)$, then
${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))\leq(m-1){\mathcal{C}}({\mathcal{F}},\rho)+\frac{(m-1)n\mu}{\lambda}+\frac{(m-2)^{2}}{\sqrt{\lambda}}$.

Proofs of Theorems [4.5](#S4.Thmtheorem5) and [4.6](#S4.Thmtheorem6) are given in
Appendixes D and E, respectively.
Theorem [4.5](#S4.Thmtheorem5) shows that, for binary classifications, $B_{\widetilde{{\mathcal{F}}}}$ is close to information-theoretically safe against FGSM under distribution ${\mathcal{U}}_{m,n}(\lambda)$.
Theorem [4.6](#S4.Thmtheorem6) shows that the result is approximately valid in the general case
under certain conditions.

###### Theorem 4.5 .

###### Theorem 4.6 .

## 5 Experiments

### 5.1 Accuracy of the bias classifier

In this section, we give the accuracy of the bias classifier using the MNIST and CIFAR-10 data sets.
We compare two DNN models:

$$ $\begin{array}[]{l}{\mathcal{F}}^{(1)}:\hbox{ trained with adversarial trianing \eqref{eq-AT}}\\ {\mathcal{F}}^{(2)}:\hbox{ trained with Algorithm \ref{alg-ht1}}\end{array}$ (17) $$

whose detailed structure can be found in Appendix F.

We give the accuracy on the test set (TS) and the strong adversaries (SA, see [])
and the results are given in Table [2](#S5.T2).

From the table, we can see that the bias classifier has comparable
accuracies with ${\mathcal{F}}^{(1)}$ on the test set,
but achieves significant higher accuracies than ${\mathcal{F}}^{(1)}$ for the strong adversaries,
which implies that the bias classifier is more robust against adversaries
than DNNs of similar size and trained with adversarial training.

**Table 2: Accuracies for MNIST and CIFAR-10**
| DNN | TS/MNIST | SA/MNIST | TS/CIFAT-10 | SA/CIFAT-10 |
| --- | --- | --- | --- | --- |
| ${\mathcal{F}}^{(1)}$ | 99.19$\%$ | 51.5$\%$ | 81.23$\%$ | 19$\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ | 99.12$\%$ | 87.5$\%$ | 82.84$\%$ | 42$\%$ |

Moreover, for CIFAR-10, we compare the accuracy of our network and
two other networks ResNet18 and VGG19, all using adversarial training.
From the results in Table [3](#S5.T3),
our network ${\mathcal{F}}^{(1)}$ performs better than ResNet18 and VGG 19.

**Table 3: Accuracies for three networks on CIFAR-10.**
| DNN | Test Set | Strong Adversaries |
| --- | --- | --- |
| ${\mathcal{F}}^{(1)}$ | 81.23$\%$ | 19$\%$ |
| ResNet18 | 80.64$\%$ | 9$\%$ |
| VGG19 | 78.92$\%$ | 12$\%$ |

As pointed out in [], networks trained
with adversarial training usually have lower accuracies,
and the accuracies given in Tables [2](#S5.T2) and [3](#S5.T3) are about the
best ones for DNNs of similar sizes, which implies that the models
${\mathcal{F}}^{(1)}$ and ${\mathcal{F}}^{(2)}$ are appropriate for MNIST and CIFAR-10.

### 5.2 Robustness of the bias classifier against original-model attack

In this section, we check the robustness of the bias classifier against the original-model attack given in Algorithm [2](#alg2).

#### 5.2.1 Experimental results

We use two more networks:
${\mathcal{F}}^{(3)}$ has the same structure with ${\mathcal{F}}^{(1)}$ given in ([17](#S5.E17)),
but trained with the first-order regulation method [],
and ${\mathcal{F}}^{(4)}$ has the same structure with ${\mathcal{F}}^{(1)}$,
but trained with TRADES [].
Six kinds of adversaries are used:

$l_{\infty}$ adversaries: $1$-$i$ $(i=1,2,3)$. Each pixel of the sample changes at most $0.i$. PGD [] is used to attack: each step changes 0.01 and moves $10i$ steps.

$l_{0}$ adversaries: $2$-$i$ $(i=40,60,80)$. Change at most $i$ pixels of the sample. JSMA [] is used to attack: change $i$ pixels and each pixel can change up to $1$.

The adversary creation rates are given in Tables [4](#S5.T4) and [5](#S5.T5).
The results in the last two rows are obtained with the original-model attack.

**Table 4: Creation rates of adversaries for MNIST**
| DNN | 1-1 | 1-2 | 1-3 | 2-40 | 2-60 | 2-80 |
| --- | --- | --- | --- | --- | --- | --- |
| ${\mathcal{F}}^{(1)}$ | $3\%$ | 17$\%$ | 55$\%$ | $55\%$ | $79\%$ | $87\%$ |
| ${\mathcal{F}}^{(2)}$ | $4\%$ | $22\%$ | $77\%$ | $62\%$ | 82$\%$ | 90$\%$ |
| ${\mathcal{F}}^{(3)}$ | $22\%$ | $78\%$ | $99\%$ | $75\%$ | 98$\%$ | 99$\%$ |
| ${\mathcal{F}}^{(4)}$ | 4$\%$ | 15$\%$ | 53$\%$ | 62$\%$ | 77$\%$ | 88$\%$ |
| $B_{{\mathcal{F}}^{(1)}}$ | 3$\%$ | 14$\%$ | 49$\%$ | $48\%$ | $67\%$ | $92\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ | $2\%$ | $6\%$ | $22\%$ | 41$\%$ | 56$\%$ | $79\%$ |

**Table 5: Creation rates of adversaries for CIFAR-10**
| DNN | 1-1 | 1-2 | 1-3 | 2-40 | 2-60 | 2-80 |
| --- | --- | --- | --- | --- | --- | --- |
| ${\mathcal{F}}^{(1)}$ | $54\%$ | $77\%$ | $90\%$ | $72\%$ | $85\%$ | 96$\%$ |
| ${\mathcal{F}}^{(2)}$ | $54\%$ | $72\%$ | $85\%$ | $69\%$ | $88\%$ | 97$\%$ |
| ${\mathcal{F}}^{(3)}$ | $88\%$ | $92\%$ | $99\%$ | $89\%$ | $99\%$ | 99$\%$ |
| ${\mathcal{F}}^{(4)}$ | $49\%$ | $73\%$ | $85\%$ | $70\%$ | 89$\%$ | 97$\%$ |
| $B_{{\mathcal{F}}^{(1)}}$ | $67\%$ | $70\%$ | $86\%$ | $70\%$ | $84\%$ | $91\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ | $41\%$ | $58\%$ | $77\%$ | $49\%$ | $73\%$ | 84$\%$ |

From the tables, we can see that the bias classifiers $B_{{\mathcal{F}}^{(2)}}$
has significant lower adversary creation rates than all other networks.
For $l_{\infty}$ adversaries of MNIST, $B_{{\mathcal{F}}^{(2)}}$ achieves near optimal results and the adversaries almost disappear.
For CIFAR-10, the adversary creation rates are still quite high comparing to that of MNIST. We will explain the reason in Section [5.2.2](#S5.SS2.SSS2).

Also, $B_{{\mathcal{F}}^{(2)}}$ achieves much better results than $B_{{\mathcal{F}}^{(1)}}$,
which implies that our training method ([6](#S2.E6))
is better than the usual adversarial training ([5](#S2.E5)).

#### 5.2.2 Influence of adversarial training on the bias classifier

In this section, we give an intuitive explanation for the results in
Tables [4](#S5.T4) and [5](#S5.T5).
Let $x$ be a sample and $y$ its label.
We use PGD [] to create adversaries and show how $B_{{\mathcal{F}}_{y}}(x)$ and ${\mathcal{F}}_{y}(x)$
change along with the steps of the adversarial training to explain the results in
Tables [4](#S5.T4) and [5](#S5.T5).

In Figure [1](#S5.F1), we give the data of using the network
Lenet-5 [] for a sample $x$ with label $y$ in MNIST.
The blue, orange, green lines in the first picture
are Softmax${\mathcal{F}}_{y}(x)$, Softmax$B_{{\mathcal{F}}_{y}}(x)$, Softmax$W_{{\mathcal{F}}_{y}}(x)$, respectively.
The blue, orange, green lines in the second picture
are ${\mathcal{F}}_{y}(x)$, $B_{{\mathcal{F}}_{y}}(x)$, $W_{{\mathcal{F}}_{y}}(x)$, respectively.

When the blue line decreases, we obtain an adversary for ${\mathcal{F}}$,
which is not an adversary of $B_{{\mathcal{F}}}$, because the orange line does not reduce significantly.
For most samples from MNIST, the pictures are almost like this one,
and this explains why the values in lines 5-6 of Table [4](#S5.T4) are low.

Figure: Figure 1: Values of ${\mathcal{F}}_{y}(x)$, $B_{{\mathcal{F}}_{y}}(x)$ and $W_{{\mathcal{F}}_{y}}(x)$ along with the adversarial training steps
Refer to caption: /html/2111.04404/assets/h-9.png

Similar results are given in in Figures [2](#S5.F2) for CIFAR-10 and network VGG-19 [].
In this case,
the orange and the blue lines both decrease, and
the adversary of ${\mathcal{F}}$ is also an adversary of $B_{{\mathcal{F}}}$.
This explains why the values in lines 5-6 of Table [5](#S5.T5) are higher than that of Table [4](#S5.T4).

Figure: Figure 2: Values of ${\mathcal{F}}_{y}(x)$, $B_{{\mathcal{F}}_{y}}(x)$ and $W_{{\mathcal{F}}_{y}}(x)$ along with the adversarial training steps
Refer to caption: /html/2111.04404/assets/h-5.png

### 5.3 Safety against original-model gradient-based attack

In this section, we use experimental results to validate
the results in Section [4](#S4).

#### 5.3.1 Rates of adversaries in random samples

In this section, we give the rates of a random
point near a sample to be an adversary.
Two ways to select random points near a sample $x$ are used:

R1: Randomly change 60 pixels of $x$ from $b$ to $1-b$.

R2: Add a random number in $[-0.2,0.2]$ to each pixel of $x$.

Two networks are used:

${\mathcal{N}}_{1}$: Lenet-5 for MNIST and VGG-19 for CIFAR-10, with normal training ([2](#S2.E2)).

${\mathcal{N}}_{2}$: Lenet-5 for MNIST and VGG-19 for CIFAR-10, with adversarial training ([5](#S2.E5)).

In Table [6](#S5.T6), we give the average rates of adversaries.
From the table, we can see that the rates for random samples to be adversaries are
quite low for networks ${\mathcal{N}}_{2}$ and $B_{{\mathcal{F}}^{(2)}}$ trained with the adversarial training.

**Table 6: Rates for random samples to be adversaries**
| DNN | R1/MNIST | R2/MNIST | R1/CIFAR-10 | R2/CIFAR-10 |
| --- | --- | --- | --- | --- |
| ${\mathcal{N}}_{1}$ | 0.77$\%$ | 1.47$\%$ | 13.31$\%$ | 11.81$\%$ |
| ${\mathcal{N}}_{2}$ | 1.00$\%$ | 1.02$\%$ | 4.69$\%$ | 2.49$\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ | 0.85$\%$ | 1.64$\%$ | 4.28$\%$ | 1.67$\%$ |

In Table [7](#S5.T7), we give the values of ${\mathcal{C}}({\mathcal{F}},\rho)$ defined in ([11](#S4.E11))
for two values of $\rho$. We can see that ${\mathcal{C}}({\mathcal{F}},\rho)$ is a little bit smaller than
the values in Table [6](#S5.T6), as expected.

**Table 7: ${\mathcal{C}}({\mathcal{F}},\rho)$. M means MNIST, C means CIFAR-10.**
| DNN | $\rho=0.1$/M | $\rho=0.2$/M | $\rho=0.1$/C | $\rho=0.2$/C |
| --- | --- | --- | --- | --- |
| ${\mathcal{N}}_{1}$ | 1.00$\%$ | 1.77$\%$ | 5.26$\%$ | 9.92$\%$ |
| ${\mathcal{N}}_{2}$ | 0.88$\%$ | 1.01$\%$ | 1.84$\%$ | $2.04\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ | 0.72$\%$ | 0.97$\%$ | 1.59$\%$ | 1.71$\%$ |

#### 5.3.2 Safety of the bias classifier

For MNIST, let ${\mathcal{F}}^{(5)}={\mathcal{F}}^{(2)}+W_{5}x$, where ${\mathcal{F}}^{(2)}$ is given in ([17](#S5.E17)) and $W_{5}\in{\mathbb{R}}^{10\times 784}$ is from ${\mathcal{U}}_{10,784}(\lambda)$ for $\lambda=100$.

For CIFAR-10, let ${\mathcal{F}}^{(6)}={\mathcal{F}}^{(2)}+W_{6}x$, where ${\mathcal{F}}^{(2)}$ is in ([17](#S5.E17)) and $W_{5}\in{\mathbb{R}}^{10\times 3072}$ is from ${\mathcal{U}}_{10,3072}(\lambda)$ for $\lambda=100$.

The adversary creation rates are given in Table [8](#S5.T8), where the adversaries are introduced in Section [5.2](#S5.SS2).

**Table 8: Original-model gradient-based attack**
| DNN | 1-1 | 1-2 | 1-3 | 2-40 | 2-60 | 2-80 |
| --- | --- | --- | --- | --- | --- | --- |
| $B_{{\mathcal{F}}^{(5)}}$ for MNIST | $1\%$ | $2\%$ | $2\%$ | $2\%$ | $3\%$ | $4\%$ |
| $B_{{\mathcal{F}}^{(6)}}$ for CIFAR-10 | $19\%$ | $20\%$ | $22\%$ | $21\%$ | $22\%$ | $24\%$ |

From Table [8](#S5.T8),
the bias classifier is safe against the original-model gradient-based attack for MNIST,
and the adversarial creation rates in Table [8](#S5.T8)
are close to those in Table [6](#S5.T6).

From Table [8](#S5.T8), the results are also near optimal for CIFAR-10.
First, comparing to the results in Table [5](#S5.T5),
the adversary creation rates are decreased by half and are about $20\%$.
Second, from Table [3](#S5.T3), the accuracy of the bias classifier is about $82\%$.
Comparing these data, the real adversary creation rates are about $1\%-6\%$
which are just above the rates of random samples to be adversaries in Table
[6](#S5.T6).

### 5.4 Black-box attack on the bias classifier

In this section, we use the transfer-based black-box attack []
to compare four networks: ${\mathcal{F}}^{(1)}$, ${\mathcal{F}}^{(3)}$, ${\mathcal{F}}^{(4)}$, $B_{{\mathcal{F}}^{(2)}}$ defined in Sections [5.1](#S5.SS1) and [5.2](#S5.SS2).

The black-box attack for ${\mathcal{F}}$ works as follows.
A new network $\overline{{\mathcal{F}}}$ is trained with the training set
$\{(x,{\mathcal{F}}(x))\}$ for certain samples $x$.
Then, we use PGD and JSMA to create adversaries for $\overline{{\mathcal{F}}}$
and check wether they are adversaries of ${\mathcal{F}}$.
The adversary creation rates are given in Table [9](#S5.T9).
We can see that, the bias classifier performs better for most
adversaries and in particular for $l_{\infty}$ adversaries.
Also, the adversary creation rates are about half of that of the original-model attack
in Tables [4](#S5.T4) and [5](#S5.T5).
So the bias classifier has better robustness for the black-box attack in most cases.

**Table 9: Black-box attack of MNIST**
| DNN | 1-1 | 1-2 | 1-3 | 2-40 | 2-60 | 2-80 |
| --- | --- | --- | --- | --- | --- | --- |
| ${\mathcal{F}}^{(1)}$ | 1$\%$ | 2$\%$ | 18$\%$ | 28$\%$ | 35$\%$ | 40$\%$ |
| ${\mathcal{F}}^{(3)}$ | 6$\%$ | 12$\%$ | 28$\%$ | 38$\%$ | 45$\%$ | 50$\%$ |
| ${\mathcal{F}}^{(4)}$ | 1$\%$ | 3$\%$ | 21$\%$ | 24$\%$ | 39$\%$ | 46$\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ | 3$\%$ | 5$\%$ | 13$\%$ | 24$\%$ | 30$\%$ | 37$\%$ |

**Table 10: Black-box attack of CIFAR-10**
| DNN | 1-0.1 | 1-0.2 | 1-0.3 | 2-40 | 2-60 | 2-80 |
| --- | --- | --- | --- | --- | --- | --- |
| ${\mathcal{F}}^{(1)}$ | 22$\%$ | 23$\%$ | 28$\%$ | 35$\%$ | 36$\%$ | 41$\%$ |
| ${\mathcal{F}}^{(3)}$ | 27$\%$ | 29$\%$ | 36$\%$ | 40$\%$ | 43$\%$ | 50$\%$ |
| ${\mathcal{F}}^{(4)}$ | 21$\%$ | 24$\%$ | 28$\%$ | 33$\%$ | 39$\%$ | 44$\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ | 21$\%$ | 23$\%$ | 24$\%$ | 33$\%$ | 36$\%$ | 41$\%$ |

### 5.5 Correlation attack

In this section, it is shown that the bias classifier is safe against the
correlation attack proposed in Section [3.3](#S3.SS3).
The network used here is ${\mathcal{F}}^{(2)}$ given in ([17](#S5.E17))
and the data set is CIFAR-10.
In Table [11](#S5.T11), we give the adversary creation rates
for samples which are given the correct label by $B_{{\mathcal{F}}^{(2)}}$.
Comparing to results in Tables [5](#S5.T5) and [10](#S5.T10),
we can see that the bias classifier is quite safe against the correlation arrack.

**Table 11: Adversary creation rates for the correlation attack**
| Network | 1-0.1 | 1-0.2 | 1-0.3 | 2-40 | 2-60 | 2-80 |
| --- | --- | --- | --- | --- | --- | --- |
| $B_{{\mathcal{F}}^{(2)}}$ | $4\%$ | $11\%$ | $12\%$ | $8\%$ | $17\%$ | $21\%$ |

In Figure [3](#S5.F3), we give the attack procedure.
It can be seen that when $(W_{x,y}-W_{x,i})x$ increases $B_{x,y}-B_{x,i}$ indeed decreases,
but $B_{x,y}-B_{x,i}$ does not decrease enough to change the label,
where $y$ is the label of $x$ and $i\neq y$.

Figure: Figure 3: The input is an image for $9$ from MNIST. The $x$-axis is the number of steps of the attack. The blue line is $(W_{x,9}-W_{x,0})x$ and the orange line $B_{x,9}-B_{x,0}$.
Refer to caption: /html/2111.04404/assets/h-10.png

### 5.6 Comparison with other methods

In this section, we compare our model with several existing models to defend adversaries. We use PGD-20 with $l_{\infty}$ bound $\epsilon=8/255$ to create adversaries on the test set of CIFAR-10.

In Table [12](#S5.T12), we give the adversary creation rates for various attacks.
Our models are ${\mathcal{F}}^{(2)}$ in ([17](#S5.E17)) and ${\mathcal{F}}^{(6)}$ in Section [5.3.2](#S5.SS3.SSS2).
ResNet-10 [] is used in other cases.
The results for other networks are from the cited papers.
Gradient-based attacks cannot be used for the bias classifier,
so we use the original-model attack given in Section [3.2](#S3.SS2).

**Table 12: Adversary creation rates for CIFAR-10**
| Attack Method | Adv. creation rates |
| --- | --- |
| ADV [] | 57.1$\%$ |
| TRADE [] | 54.7$\%$ |
| MMA [] | 62.7$\%$ |
| FOAR [] | 67.7$\%$ |
| SOAR [] | 44.0$\%$ |
| $B_{{\mathcal{F}}^{(2)}}$ in Sec. [5.1](#S5.SS1) | 41.1$\%$ |
| $B_{{\mathcal{F}}^{(6)}}$ in Sec. [5.3.2](#S5.SS3.SSS2) | $20\%$ |

Although the DNN models and the attacks are not the same,
this comparison gives a rough idea of the performance that can be achieved for various
methods of defending adversaries.

From Table [12](#S5.T12), we see that
the attack method SOAR [] and the bias classifier $B_{{\mathcal{F}}_{B}^{(2)}}$ achieve the best
results for creating lower rates of adversaries, besides $B_{{\mathcal{F}}_{B}^{(6)}}$.
As explained in Section [5.3.2](#S5.SS3.SSS2),
the optimal adversary creation rate is about $20\%$
and is achieved by $B_{{\mathcal{F}}_{B}^{(6)}}$.

### 5.7 Summary of the experiments

We give a summary of the experiments in this section.

From Tables [2](#S5.T2) and [3](#S5.T3), we can see that
the bias classifier achieves comparable accuracies
with DNNs of similar sizes.

From Table [6](#S5.T6), we can see that
the bias classifier with a random first-degree part is safe against
gradient-based attacks, as proved in Section [4](#S4).

From Tables [2](#S5.T2), [4](#S5.T4), [5](#S5.T5), [9](#S5.T9), [10](#S5.T10), and [12](#S5.T12),
we can see that the bias classifier is more robust than DNNs with similar sizes against adversarial attacks .

From Tables [5](#S5.T5), [10](#S5.T10), [11](#S5.T11),
the original-model attack, the black-box attack, and the correlation attack
become weaker for creating adversaries, and the original model attack is the best available attack for
the bias classifier.

## 6 Concluding remarks

In this paper, we show that the bias part of a DNN can be effectively trained as
a classifier.
The motivation to use the bias part as the classifier is that
gradients of the DNN seems to be inevitable to generate adversaries efficiently and
the bias part of a DNN with Relu as activation functions
is a piecewise constant function with zero gradient
and is safe against direct gradient-based attacks such as FGSM.

The bias classifier can be effectively trained with
the adversarial training method [],
which increases the classification power of the bias part
and decreases the classification power of first-degree part.
Experimental results are used to show the robustness of the bias classifier
over the standard DNNs

Further, by adding a random first-degree part to the bias classifier,
an information-theoretically safe classifier against gradient-based attacks is obtained,
that is, the adversary creation rate
is almost the same as the rate of certain random samples to be adversaries.

For further research, the estimations in Theorems [4.3](#S4.Thmtheorem3), [4.5](#S4.Thmtheorem5), [4.6](#S4.Thmtheorem6)
are not optimal, and better estimations are desirable.

## Appendix

### Appendix A. Proof of Theorem 2.1

See [2.1](#S2.Thmtheorem1)
We first prove several lemmas. In this section,
the notations ${\mathbb{O}},O_{l},{\mathbb{L}}$ introduced in Theorem [2.1](#S2.Thmtheorem1) will be used.

Let $\Gamma:{\mathbb{R}}\rightarrow{\mathbb{R}}$ be another activation function:

$$ $\Gamma(x)=\left\{\begin{array}[]{lll}0&\hbox{ if }&x\leq 0\\ 1&\hbox{ if }&x>0\\ \end{array}\right..$ $$

###### Lemma 2.1 (Theorem 5 in [ 8 ] ) .

Let $l\in{\mathbb{L}}$ and $F_{l}:{\mathbb{R}}\to{\mathbb{R}}$ be a function such that $F_{l}(x)=1$ if $x\in O_{l}$
and $F_{l}(x)=-1$ otherwise.
Then for any $\epsilon>0$, there exist $N\in{\mathbb{N}}_{>0}$, $W\in{\mathbb{R}}^{N\times n}$, $b\in{\mathbb{R}}^{N}$, $U\in{\mathbb{R}}^{1\times N}$, and an open set $D\subset{\mathbb{I}}^{n}$ with $V(D)<\epsilon$,
such that

$$ $G(x)=U\cdot\Gamma(Wx+b):{\mathbb{I}}^{n}\to{\mathbb{R}}$ $$

and $|G(x)-F_{l}(x)|<\epsilon$ for $x\in{\mathbb{O}}\setminus D$.

The following lemma shows that there exists a DNN with one hidden layer
and using $\Gamma$ as the activation function, which can be used as a classifier
for ${\mathbb{O}}$.

###### Lemma 2.2 .

For any $\epsilon>0$, there exist $N\in{\mathbb{N}}_{>0}$, $W\in{\mathbb{R}}^{N\times n}$, $b\in{\mathbb{R}}^{N}$, $U\in{\mathbb{R}}^{m\times N}$, and an open set $D\subset{\mathbb{I}}^{n}$ with $V(D)<\epsilon$,
such that

$$ ${\mathcal{G}}(x)=U\cdot\Gamma(Wx+b):{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ $$

gives the correct label for $x\in{\mathbb{O}}\setminus D$.

###### Proof.

By Lemma [2.1](#S2.Thmlemma1), for $l\in{\mathbb{L}}=[m]$, there exist
$N_{a}\in{\mathbb{N}}_{>0}$,
$W_{l}\in{\mathbb{R}}^{N_{a}\times n}$,
$b_{l}\in{\mathbb{R}}^{N_{a}}$,
$U_{l}\in{\mathbb{R}}^{1\times N_{a}}$,
and $D_{l}\subset{\mathbb{I}}^{n}$ with $V(D_{l})<\epsilon/m$
such that

$$ $G_{l}(x)=U_{l}\cdot\Gamma(W_{l}x+b_{l})\hbox{ and }|G_{l}(x)-F_{l}(x)|<\epsilon$ $$

for $x\in{\mathbb{O}}\setminus D_{l}$, where $F_{l}$ is defined in Lemma [2.1](#S2.Thmlemma1).

Let $N=N_{a}m$, $W\in{\mathbb{R}}^{N\times n}$, $b\in{\mathbb{R}}^{N}$,
where the $l$-th row of $W$ is the $l_{2}$-th row of $W_{l_{1}}$ and
the $l$-th row of $b$ is the $l_{2}$-th row of $b_{l_{1}}$,
where $l=l_{1}N_{a}+l_{2}$, $0\leq l_{2}<N_{a}$, and $0\leq l_{1}<m$.

Let $U\in{\mathbb{R}}^{m\times N}$ be formed as follows:
for $j\in[m]$, the $j$-th row of $U$ are zeros except the
$(j-1)N_{a}$-th to the $((j-1)N_{a}+N_{a}-1)$-th rows,
and the values of the $((j-1)N_{a}+k)$-th place of the $j$-th row of
$U$ equal to the values of the $k$-th place of $U_{l}$, where $k=0,1,\ldots,N_{a}-1$.

Now we have $N=N_{a}m\in{\mathbb{N}}_{>0}$, $W\in{\mathbb{R}}^{N\times n}$, $b\in{\mathbb{R}}^{N}$, $U\in{\mathbb{R}}^{m\times N}$, and

$$ ${\mathcal{G}}(x)=U\cdot\Gamma(Wx+b)$ $$

satisfies ${\mathcal{G}}(x)_{l}$=$G_{l}(x)$, where ${\mathcal{G}}(x)_{l}$ is the $l$-th coordinate of ${\mathcal{G}}(x)$.
Let $D=\bigcup_{i=1}^{m}D_{l}\subset{\mathbb{I}}^{n}$ with $V(D)<\epsilon$.
Then ${\mathcal{G}}(x)_{y}>1-\epsilon$ and ${\mathcal{G}}(x)_{l}<-1+\epsilon$ for $x\in O_{y}$ and $l\neq y$.
Since $\epsilon$ can be as small as possible,
we have ${\mathcal{G}}(x)_{y}>{\mathcal{G}}(x)_{l}$ for $l\neq y$,
and ${\mathcal{G}}(x)$ give label $y$ for $x\in O_{y}\setminus D$.
Hence, ${\mathcal{G}}(x)$ gives the correct label for $x\in{\mathbb{O}}\setminus D$.
∎

###### Lemma 2.3 .

Let $W\in{\mathbb{R}}^{1\times n}$ have nonzero entries and $b\in{\mathbb{R}}$.
For any $a>0$, let $Z_{a}=\{x\in{\mathbb{I}}^{n}\,|\,|Wx+b|<a\}$.
Then $V(Z_{a})\leq 2a\sqrt{n}^{n-1}/||W||_{2}$.

###### Proof.

Let $U=\{U_{1},\ldots,U_{n}\}$ be a unit orthogonal basis of ${\mathbb{R}}^{n}$ and $U_{1}=\frac{W}{||W||_{2}}$.
If $T_{i}=\max_{x,y\in Z_{a}}\{\langle x-y,U_{i}\rangle\}$, then we have $V(Z_{a})\leq\Pi_{i=1}^{n}T_{i}$.

For $i>1$, we have $T_{i}\leq\max_{x,y\in Z_{a}}||x-y||_{2}\leq\sqrt{n}$.
Moreover, for any $x,y\in Z_{a}$, we have

$$ $\begin{array}[]{ll}&\langle x-y,U_{1}\rangle\\ =&\langle x-y,W\rangle/||W||_{2}\\ =&(Wx+b-Wy-b)/||W||_{2}\\ \leq&2a/||W||_{2}\\ \end{array}$ $$

which means $T_{1}\leq 2a/||W||_{2}$. Then we have

$$ $V(Z_{a})\leq\Pi_{i=1}^{n}T_{i}\leq 2a\sqrt{n}^{n-1}/||W||_{2}.$ $$

The lemma is proved.
∎

###### Lemma 2.4 .

The bias vector $b$ in Lemma [2.2](#S2.Thmlemma2) can be chosen to consist of nonzero values.

###### Proof.

By Lemma [2.2](#S2.Thmlemma2), there exist
$N\in{\mathbb{N}}_{>0}$, $W\in{\mathbb{R}}^{N\times n}$, $b\in{\mathbb{R}}^{N}$, $U\in{\mathbb{R}}^{m\times N}$,
and $D_{1}\subset{\mathbb{I}}^{n}$ with $V(D_{1})<\epsilon/2$, such that

$$ ${\mathcal{G}}(x)=U\cdot\Gamma(Wx+b)$ $$

gives the correct label for $x\in{\mathbb{O}}\setminus D_{1}$.

Let $\gamma=\frac{\epsilon W_{m}}{4N\sqrt{n}^{n-1}}$, where $W_{m}=||W||_{2,\infty}$.
Assume $\widetilde{b}=b-I_{0}(|b|)\gamma$, where $I_{0}(x)=1-{\hbox{\rm{sign}}}(x)$ and
when $I_{0}$ is treated as a map of a vector,
it acts on each entry of the vector, respectively.
From the construction, $\widetilde{b}$ does not have zero entries, because $\widetilde{b}_{i}=b_{i}$ if $b_{i}\neq 0$, and $\widetilde{b}_{i}=\gamma$ if $b_{i}=0$,
where $b_{i}$ and $\widetilde{b}_{i}$ are respectively the $i$-th rows of $b$ and $\widetilde{b}$.

Let $W_{i}$ be the $i$-th row of $W$ and $Z_{i}=\{z\in{\mathbb{R}}^{n}\,|\,|W_{i}z+b_{i}|<\gamma\}$.
By Lemma [2.3](#S2.Thmlemma3), we have $V(Z_{i}\bigcap{\mathbb{I}}^{n})<2\gamma\sqrt{n}^{n-1}/W_{m}$. We write $C_{n}=\sqrt{n}^{n-1}/W_{m}$.

Let $Z=\{x\in{\mathbb{R}}^{n}\,|\,\Gamma(Wx+b)\neq\Gamma(Wx+\widetilde{b})\}$.
We will show that $Z=\cup_{i=1}^{N}Z_{i}$.
If $\Gamma(Wx+b)\neq\Gamma(Wx+\widetilde{b})$,
then there exists an $i\in[N]$ such that
$W_{i}x+b_{i}>0$ and $W_{i}x+\widetilde{b}_{i}<0$,
or $W_{i}x+b_{i}<0$ and $W_{i}x+\widetilde{b}_{i}>0$.
If $W_{i}x+b_{i}>0$ and $W_{i}x+\widetilde{b}_{i}<0$,
then
$W_{i}x+\widetilde{b}_{i}=W_{i}x+b_{i}-I_{0}(|b|)\gamma<0$
and hence $|W_{i}x+b_{i}|\leq\gamma$.
Similarly, if $W_{i}x+b_{i}<0$ and $W_{i}x+\widetilde{b}_{i}>0$,
we also have $|W_{i}x+b_{i}|\leq\gamma$,
which implies $x\in Z_{i}$.
As a consequence $Z=\cup_{i=1}^{N}Z_{i}$.

From $Z=\cup_{i=1}^{N}Z_{i}$, we have $V(Z\bigcap{\mathbb{I}}^{n})<2\gamma NC_{n}<\epsilon/2$,
since $\gamma=\frac{\epsilon}{4NC_{n}}$.
Let $D=D_{1}\bigcup(Z\bigcap{\mathbb{I}}^{n})\subset{\mathbb{I}}^{n}$.
Then $V(D)<V(D_{1})+V(Z\bigcap{\mathbb{I}}^{n})<\epsilon$.

Finally, let

$$ $\widetilde{{\mathcal{G}}}(x)=U\cdot\Gamma(Wx+\widetilde{b}).$ $$

Then, for $x\in{\mathbb{O}}\setminus D$, we have $\Gamma(Wx+b)=\Gamma(Wx+\widetilde{b})$
and hence $\widetilde{{\mathcal{G}}}(x)={{\mathcal{G}}}(x)$.
That is, $\widetilde{{\mathcal{G}}}$ satisfies the conditions of the lemma.
∎

###### Lemma 2.5 .

Let ${\mathcal{G}}:{\mathbb{I}}^{n}\to{\mathbb{R}}^{m}$ be a one-hidden-layer DNN with activation function $\Gamma(x)$,
and any coordinate of its bias vector is nonzero.
Then there exists a DNN ${\mathcal{F}}$, which has the same structure as ${\mathcal{G}}$,
except that the activation function of ${\mathcal{F}}$ is Relu, such that
$B_{{\mathcal{F}}}(x)={\mathcal{G}}(x)$
for all $x\in{\mathbb{I}}^{n}$.

###### Proof.

Assume ${\mathcal{G}}(x)=U\cdot\Gamma(Wx+b)+c$.
Let ${\mathcal{F}}(x)=U^{{\mathcal{F}}}{\hbox{\rm{Relu}}}(Wx+b)+c$, where
$U^{{\mathcal{F}}}=U{\hbox{\rm{diag}}}(\frac{1}{b_{i}})$ and $b_{i}$ is the $i$-th entry of $b$.
We will show that ${\mathcal{F}}$ satisfies the condition of the lemma.
By the definition of $\Gamma$, the constant part of
${\hbox{\rm{Relu}}}(Wx+b)$ is $b\circ\Gamma(Wx+b)$, where $\circ$ is the point-wise product.
So, $B_{{\mathcal{F}}}(x)=U^{{\mathcal{F}}}(b\circ\Gamma(Wx+b))+c=U{\hbox{\rm{diag}}}(\frac{1}{b_{i}})(b\circ\Gamma(Wx+b))+c=U\Gamma(WX+b)+c$.
$B_{{\mathcal{F}}}(x)={\mathcal{G}}(x)$ and the lemma is proved.
∎

Proof of Theorem [2.1](#S2.Thmtheorem1).
By Lemma [2.2](#S2.Thmlemma2),
there exist a $D\subset{\mathbb{I}}^{n}$ with $V(D)<\epsilon$
and a network ${\mathcal{G}}$ with one-hidden-layer and with activation function $\Gamma(x)$,
such that ${\mathcal{G}}(x)$ gives the correct label for $x\in{\mathbb{O}}\setminus D$.
By Lemma [2.4](#S2.Thmlemma4), all the parameters of ${\mathcal{G}}$ are nonzero.
Then by Lemma [2.5](#S2.Thmlemma5), we can obtain a network ${\mathcal{F}}$ with Relu as the activation function
such that $B_{{\mathcal{F}}}={\mathcal{G}}(x)$,
and the theorem is proved.∎

###### Lemma 2.1 (Theorem 5 in [ 8 ] ) .

###### Lemma 2.2 .

###### Proof.

###### Lemma 2.3 .

###### Proof.

###### Lemma 2.4 .

###### Proof.

###### Lemma 2.5 .

###### Proof.

### Appendix B. Proof of Theorem 4.3

We first prove two lemmas.

###### Lemma 4.1 .

Let $\{u_{i}\}_{i=1}^{n}$ be a set of iid random variables with values in $[-\lambda,\lambda]$ and $u=\sum_{i=1}^{n}x_{i}u_{i}$, where $x_{i}\in{\mathbb{R}}$ such that $|x_{i}|>a>0$ for some $i$.
Let the density function of $u$ be $f(x)$.
Then $f(x)<\frac{1}{2\lambda a}$ for all $x$.

###### Proof.

Assume $|x_{n}|>a$ and $f_{n}(x)$ is the distribution function of $x_{n}u_{n}$. We have

$$ $\begin{array}[]{ll}&P(u<m)\\ =&\displaystyle\int_{\{-\lambda|x_{i}|\}_{i=1}^{n-1}}^{\{\lambda|x_{i}|\}_{i=1}^{n-1}}(\Pi_{i=1}^{n-1}\frac{1}{2\lambda|x_{i}|})f_{n}(m-\sum_{i=1}^{n-1}t_{i}){\hbox{\rm{d}}}t_{1}t_{2}\dots t_{n-1}.\end{array}$ $$

Since $0<f^{\prime}_{n}(x)\leq\frac{1}{2\lambda|x_{n}|}$ and $f(x)=\frac{\nabla P(u<x)}{\nabla x}$, we have

$$ $\begin{array}[]{ll}&f(x)\\ =&\frac{\nabla P(u<x)}{\nabla x}\\ =&\frac{\nabla{\displaystyle\int}_{\{-\lambda|x_{i}|\}_{i=1}^{n-1}}^{\{\lambda|x_{i}|\}_{i=1}^{n-1}}(\Pi_{i=1}^{n-1}\frac{1}{2\lambda|x_{i}|})f_{n}(x-\sum_{i=1}^{n-1}t_{i}){\hbox{\rm{d}}}t_{1}t_{2}\dots t_{n-1}}{\nabla x}\\ =&{\displaystyle\int}_{\{-\lambda|x_{i}|\}_{i=1}^{n-1}}^{\{\lambda|x_{i}|\}_{i=1}^{n-1}}(\Pi_{i=1}^{n-1}\frac{1}{2\lambda|x_{i}|})\frac{\nabla f_{n}(x-\sum_{i=1}^{n-1}t_{i})}{\nabla x}{\hbox{\rm{d}}}t_{1}t_{2}\dots t_{n-1}\\ \leq&{\displaystyle\int}_{\{-\lambda|x_{i}|\}_{i=1}^{n-1}}^{\{\lambda|x_{i}|\}_{i=1}^{n-1}}(\Pi_{i=1}^{n-1}\frac{1}{2\lambda|x_{i}|})\frac{1}{2\lambda|x_{n}|}{\hbox{\rm{d}}}t_{1}t_{2}\dots t_{n-1}\\ \leq&\frac{1}{2\lambda|x_{n}|}\\ \leq&\frac{1}{2\lambda a}.\end{array}$ $$

The lemma is proved.
∎

###### Lemma 4.2 .

Let $\{u_{i}\}_{i=1}^{n}$ be a set of iid variables, $f_{i}$ the density function of $u_{i}$, and $f_{i}(x)<a$ for all $x\in{\mathbb{R}}$.
Then we have

$$ $P(|u_{i}-u_{j}|>\psi\ \hbox{for}\ \forall i\neq j)>\Pi_{i=0}^{n-1}(1-2i\psi a).$ $$

###### Proof.

Let $D_{k}$ be the event $|u_{i}-u_{j}|>\psi$ for $\forall i,j\leq k$, and $F_{k}:{\mathbb{R}}^{k}\to{\mathbb{R}}$ the joint probability density function of $\{u_{i}\}_{i=1}^{k}$ under condition $D_{k}$.
Then we have

$$ $\begin{array}[]{ll}&P(D_{k})\\ =&P(D_{k},D_{k-1})\\ =&P(D_{k}\|D_{k-1})P(D_{k-1})\\ =&P(|u_{k}-u_{i}|>\psi\ for\ \forall i<k\|D_{k-1})P(D_{k-1})\\ =&P(D_{k-1})\int_{-\infty^{k-1}}^{\infty^{k-1}}\int_{-\infty}^{\infty}F_{k-1}(t_{1},\dots,t_{k-1})\\ &f_{k}(t_{k})I(|t_{k}-t_{i}|>\psi\ \forall i<k){\hbox{\rm{d}}}t_{k}{\hbox{\rm{d}}}t_{1}\dots t_{k-1}\\ >&P(D_{k-1})\int_{-\infty^{k-1}}^{\infty^{k-1}}\int_{-\infty}^{\infty}F_{k-1}(t_{1},\dots,t_{k-1})\\ &(f_{k}(t_{k})-aI(|t_{k}-t_{i}|<\psi\ \exists i<k)){\hbox{\rm{d}}}t_{k}{\hbox{\rm{d}}}t_{1}\dots t_{k-1}\\ =&P(D_{k-1})(1-\int_{-\infty^{k-1}}^{\infty^{k-1}}\int_{-\infty}^{\infty}aF_{k-1}(t_{1},\dots,t_{k-1})\\ &I(|t_{k}-t_{i}|<\psi\ \exists i<k){\hbox{\rm{d}}}t_{k}{\hbox{\rm{d}}}t_{1}\dots t_{k-1})\\ >&P(D_{k-1})(1-\\ &\int_{-\infty^{k-1}}^{\infty^{k-1}}2a(k-1)\psi F_{k-1}(t_{1},\dots,t_{k-1}){\hbox{\rm{d}}}t_{1}\dots t_{k-1})\\ =&P(D_{k-1})(1-2a(k-1)\psi).\end{array}$ $$

Since $P(D_{0})=1$, we have

$$ $\begin{array}[]{ll}&P(|u_{i}-u_{j}|>\psi\ for\ \forall i\neq j)\\ =&P(D_{n})\\ >&P(D_{n-1})(1-2(n-1)\psi a)\\ >&P(D_{n-2})(1-2(n-1)\psi a)(1-2(n-2)\psi a)\\ >&\dots\\ >&\Pi_{i=0}^{n-1}(1-2i\psi a).\end{array}$ $$

The lemma is proved.
∎

See [4.3](#S4.Thmtheorem3)

###### Proof.

From ([3](#S2.E3)) and ([9](#S4.E9)), we have
${\mathcal{F}}(x)=W_{x}x+B_{x}$ and $\widetilde{{\mathcal{F}}}(x)=(W_{x}+W_{R})x+B_{x}$.
Let $x$ be a sample with label $y$.
From equation ([15](#S4.E15)), we have

$$ $\begin{array}[]{ll}&\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}=\frac{\sum_{i=1}^{m}(W_{R,i}-W_{R,y}+W_{x,i}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}.\end{array}$ $$

Let $m_{x}=\arg\max_{i\neq y}\{\langle W_{R,i},x\rangle\}$ and consider the condition:

Condition $C_{1}$: $\langle W_{R,m_{x}},x\rangle\ >\ \langle W_{R,j},x\rangle+\sqrt{\lambda}$ for all $j\in[m]\setminus\{y,m_{x}\}$.

We first give the probability for condition $C_{1}$ to be valid.
By Lemmas [4.1](#S4.Thmlemma1) and [4.2](#S4.Thmlemma2) and due to $|x|_{\infty}=1$, we have

$$ $\begin{array}[]{ll}&P_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}(C_{1})\\ \geq&P_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}(|\langle W_{R,j},x\rangle-\langle W_{R,i},x\rangle|>\sqrt{\lambda},\\ &\forall i,j\in[m]/\{y\},\ i\neq j)\\ \geq&\Pi_{i=1}^{m-2}(1-\frac{2i\sqrt{\lambda}}{2\lambda|x|_{\infty}})\\ \geq&(1-\frac{m-2}{\sqrt{\lambda}})^{m-2}\\ \geq&1-\frac{(m-2)^{2}}{\sqrt{\lambda}}.\end{array}$ (18) $$

Let $||x||_{-\infty}=\min_{i\in[n]}\{|x|_{i}\}$ for $x\in{\mathbb{R}}^{n}$.
Since $|\frac{\nabla{\mathcal{F}}(x)}{\nabla x}|_{\infty}<\mu/2$ and $W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)$, we have
$||W_{R,i}+W_{R,j}||_{-\infty}>\lambda$, $||W_{R,i}+W_{R,j}||_{\infty}<2m\lambda$
and $||W_{x,i}+W_{x,j}||_{\infty}<\mu$ for any $i\neq j$.
If condition $C_{1}$ is satisfied,
then for any $j\in[m]\setminus\{y,m_{x}\}$, we have

$$ $\begin{array}[]{ll}&\widetilde{{\mathcal{F}}}_{m_{x}}(x)-\widetilde{{\mathcal{F}}}_{j}(x)\\ =&(W_{R,m_{x}}+W_{x,m_{x}}-W_{R,j}-W_{x,j})x+B_{x,m_{x}}-B_{x,j}\\ =&(W_{R,m_{x}}-W_{R,j})x+(W_{x,m_{x}}-W_{x,j})x+B_{x,m_{x}}-B_{x,j}\\ >&\sqrt{\lambda}-n\mu-2\beta.\end{array}$ $$

Further considering the hypothesis $(\lambda-\mu)e^{-2\beta-n\mu+\sqrt{\lambda}}>(2m\lambda+\mu)m$,
we have

$$ $\begin{array}[]{ll}&||W_{R,m_{x}}-W_{R,y}+W_{x,m_{x}}-W_{x,y}||_{-\infty}e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)}\\ >&(\lambda-\mu)e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)}\\ >&(\lambda-\mu)e^{{\widetilde{{\mathcal{F}}}_{j}(x)}+\sqrt{\lambda}-2\beta-n\mu}\\ =&(\lambda-\mu)e^{-2\beta-n\mu}e^{\sqrt{\lambda}}e^{{\widetilde{{\mathcal{F}}}_{j}(x)}}\\ >&(2m\lambda+\mu)me^{{\widetilde{{\mathcal{F}}}_{j}(x)}}\\ >&m||(W_{R,j}-W_{R,y}+W_{x,j}-W_{x,y})||_{\infty}e^{\widetilde{{\mathcal{F}}}_{j}(x)}\end{array}$ $$

which means

$$ $\begin{array}[]{ll}{\hbox{\rm{sign}}}(\sum_{i=1}^{m}(W_{R,i}-W_{R,y}+W_{x,i}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)})=\\ {\hbox{\rm{sign}}}((W_{R,m_{x}}-W_{R,y}+W_{x,m_{x}}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)}).\end{array}$ $$

Because of this, we have:

$$ $\begin{array}[]{ll}&{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x})\\ =&{\hbox{\rm{sign}}}(\frac{\sum_{i=1}^{m}(W_{R,i}-W_{R,y}+W_{x,i}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}})\\ =&{\hbox{\rm{sign}}}(\sum_{i=1}^{m}(W_{R,i}-W_{R,y}+W_{x,i}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)})\\ =&{\hbox{\rm{sign}}}((W_{R,m_{x}}-W_{R,y}+W_{x,m_{x}}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)})\\ =&{\hbox{\rm{sign}}}((W_{R,m_{x}}-W_{R,y}+W_{x,m_{x}}-W_{x,y})\\ =&{\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y}).\end{array}$ $$

Let $V$ be a random vector in $\{0,1\}^{n}$.
Then the probability for the sign of $W_{R,m_{x}}-W_{R,y}$
to be $V$ is

$$ $\begin{array}[]{ll}&P({\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y})=V,C_{1})\\ \leq&P({\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y})=V)\\ =&\sum_{i<y}P(m_{x}=i,{\hbox{\rm{sign}}}(W_{R,y})=V)+\\ &\sum_{i>y}P(m_{x}=i,{\hbox{\rm{sign}}}(W_{R,i})=V)\\ \leq&\sum_{i<y}P({\hbox{\rm{sign}}}(W_{R,y})=V)\\ &\sum_{i>y}P({\hbox{\rm{sign}}}(W_{R,i})=V)\\ =&\frac{m-1}{2^{n}}.\end{array}$ $$

So we have

$$ $\begin{array}[]{ll}&{\mathbb{E}}_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}\\ &[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}))\neq\widehat{B}_{{\mathcal{F}}}(x)){\mathbf{I}}(C_{1})]\\ =&{\mathbb{E}}_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}\\ &[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y}))\neq\widehat{B}_{{\mathcal{F}}}(x)){\mathbf{I}}(C_{1})]\\ =&\sum_{V\in\{-1,1\}^{n}}P({\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y})=V,\ C_{1})\\ &{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho V)\neq\widehat{B}_{{\mathcal{F}}}(x))\\ \leq&\sum_{V\in\{-1,1\}^{n}}(m-1)/(2^{n}){\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho V)\neq\widehat{B}_{{\mathcal{F}}}(x))\\ =&(m-1){\mathcal{C}}({\mathcal{F}},\rho).\end{array}$ $$

Finally, from ([18](#S4.E18)) we have

$$ $\begin{array}[]{ll}&{\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}}{\mathcal{A}}_{2},{\mathcal{M}}_{m,n}(\lambda))\\ =&{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}\\ &[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\ \leq&{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}\\ &[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}))\neq\widehat{B}_{{\mathcal{F}}}(x)){\mathbf{I}}(C_{1})\\ &+(1-{\mathbf{I}}(C_{1}))]\\ \leq&(m-1){\mathcal{C}}({\mathcal{F}},\rho)+{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}[(1-{\mathbf{I}}(C_{1}))]\\ \leq&(m-1){\mathcal{C}}({\mathcal{F}},\rho)+{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}[1-P_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}(C_{1})]\\ \leq&(m-1){\mathcal{C}}({\mathcal{F}},\rho)+\frac{(m-2)^{2}}{\sqrt{\lambda}}.\\ \end{array}$ $$

The theorem is proved.
∎

###### Lemma 4.1 .

###### Proof.

###### Lemma 4.2 .

###### Proof.

###### Proof.

### Appendix C. Proof of Theorem 4.4

We first prove a lemma.

###### Lemma 4.3 .

Let $x_{1},x_{2}\sim{\mathcal{U}}(-\lambda,\lambda)$ and $z=x_{1}-x_{2}$.
Then for $a\in[0,2\lambda]$, we have $P(z<a)=P(z>-a)=1-\frac{(2\lambda-a)^{2}}{8\lambda^{2}}$,
which is denoted as $T(\lambda,a)=1-\frac{(2\lambda-a)^{2}}{8\lambda^{2}}$.

###### Proof.

Let $f(z)$ be the density function of $z$.
Then $f(z)=0$, if $z\geq 2\lambda$ or $z\leq-2\lambda$;
$f(z)=\frac{2\lambda+z}{4\lambda^{2}}$, if $0\geq z\geq-2\lambda$;
$f(z)=\frac{2\lambda-z}{4\lambda^{2}}$, if $0\leq z\leq 2\lambda$.
Hence, $P(z<a)=P(z>-a)=1-\frac{(2\lambda-a)^{2}}{8\lambda^{2}}$.
∎

Note that $T(\lambda,a)$ increases with $a$ and $T(\lambda,a)\in[0.5,1]$.

See [4.4](#S4.Thmtheorem4)

###### Proof.

Similar to ([13](#S4.E13)),
if $||W_{R,n_{x}}-W_{R,y}||_{-\infty}>\mu$, then we have

$$ $\begin{array}[]{ll}&{\mathcal{A}}_{3}(x,\widetilde{{\mathcal{F}}},\rho)\\ =&x+\frac{\rho}{k}\sum_{i=1}^{k}{\hbox{\rm{sign}}}(W_{x^{i-1},n_{x}}-W_{x^{i-1},y}+W_{R,n_{x}}-W_{R,y})\\ =&x+\rho{\hbox{\rm{sign}}}(W_{R,n_{x}}-W_{R,y}).\\ \end{array}$ $$

Since $V=W_{R,n_{x}}-W_{R,y}$ is a random variable in $[-2\lambda,2\lambda]$,
${\hbox{\rm{sign}}}(V)$ is a random variable in $\{-1,1\}^{n}$.
By Lemma [4.3](#S4.Thmlemma3),

$$ $\begin{array}[]{ll}&{\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\\ =&{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}({\mathcal{A}}_{3}(x,\widetilde{{\mathcal{F}}}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\ \leq&{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(||W_{R,n_{x}}-W_{R,y}||_{-\infty}\leq\mu)+\\ &{\mathbf{I}}(||W_{R,n_{x}}-W_{R,y}||_{-\infty}>\mu)[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}({\mathcal{A}}_{3}(x,\widetilde{{\mathcal{F}}}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\ \leq&(1-2^{n}(1-T(\lambda,\mu))^{n})+\\ &{\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathbb{O}}}}\sum_{V\in\{-1,1\}^{n}}{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho V)\neq\widehat{B}_{{\mathcal{F}}}(x))]\\ \leq&(1-2^{n}(1-T(\lambda,\mu))^{n})+{\mathcal{C}}({\mathcal{F}},\rho)\\ \end{array}$ $$

where $T(\lambda,\mu)=1-\frac{(2\lambda-\mu)^{2}}{8\lambda^{2}}$. We have
$2^{n}(1-T(\lambda,\mu))^{n}=(2-2+\frac{4\lambda^{2}+\mu^{2}-4\lambda\mu}{4\lambda^{2}})^{n}=(1-\frac{4\lambda\mu-\mu^{2}}{4\lambda^{2}})^{n}\geq 1-n\frac{4\lambda\mu-\mu^{2}}{4\lambda^{2}}\geq 1-n\mu/\lambda.$
So,

$$ $\begin{array}[]{ll}&{\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{3},{\mathcal{U}}_{m,n}(\lambda))\\ \leq&1-2^{n}(1-T(\lambda,\mu))^{n}+{\mathcal{C}}({\mathcal{F}},\rho)\\ \leq&{\mathcal{C}}({\mathcal{F}},\rho)+n\mu/\lambda.\\ \end{array}$ $$

The theorem is proved.
∎

###### Lemma 4.3 .

###### Proof.

###### Proof.

### Appendix D. Proof of Theorem 4.5

See [4.5](#S4.Thmtheorem5)

###### Proof.

Let $y\in\{0,1\}$ be the label of $x$.
Denote
$U=W_{x,1-y}-W_{x,y}\in{\mathbb{R}}^{1\times n}$
and $Z=W_{R,1-y}-W_{R,y}\in{\mathbb{R}}^{1\times n}$.
We have

$$ $\begin{array}[]{ll}&{\hbox{\rm{sign}}}(\frac{\nabla L({\mathcal{F}}(x),y)}{\nabla x})\\ =&{\hbox{\rm{sign}}}(\frac{e^{{\mathcal{F}}_{1-y}(x)}(\frac{\nabla({\mathcal{F}}_{1-y}(x))}{\nabla x}-\frac{\nabla({\mathcal{F}}_{y}(x))}{\nabla x})}{e^{{\mathcal{F}}_{y}(x)}+e^{{\mathcal{F}}_{1-y}(x)}})\\ =&{\hbox{\rm{sign}}}(\frac{\nabla({\mathcal{F}}_{1-y}(x))}{\nabla x}-\frac{\nabla({\mathcal{F}}_{y}(x))}{\nabla x})\\ =&{\hbox{\rm{sign}}}(W_{x,1-y}-W_{x,y})\\ =&{\hbox{\rm{sign}}}(U).\\ \end{array}$ $$

From equation ([15](#S4.E15)), we have

$$ $\begin{array}[]{ll}&{\hbox{\rm{sign}}}(\frac{\nabla L({\widetilde{{\mathcal{F}}}}(x),y)}{\nabla x})\\ =&{\hbox{\rm{sign}}}(\frac{e^{\widetilde{{\mathcal{F}}}_{1-y}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}(W_{x,1-y}-W_{x,y}+W_{R,1-y}-W_{R,y})).\\ =&{\hbox{\rm{sign}}}(U+Z).\\ \end{array}$ $$

For $i\in[n]$, ${\hbox{\rm{sign}}}(U_{i})={\hbox{\rm{sign}}}(U_{i}+Z_{i})$ if and only if
$(Z_{i}\leq-U_{i}$ when $U_{i}\leq 0$) or
$(Z_{i}\geq-U_{i}$ when $U_{i}\geq 0$),
where $Z_{i},U_{i}$ are respectively the $i$-th coordinates of $Z,U$.
Since $W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)$, $Z=W_{R,1-y}-W_{R,y}$ is the difference of
two uniform distributions in $[-\lambda,\lambda]$.
By Lemma [4.3](#S4.Thmlemma3),
$U_{i}>0$ implies $P(Z_{i}\geq-U_{i})=T(\lambda,|U_{i}|)<T(\lambda,\mu)$,
and $U_{i}<0$ implies $P(Z_{i}\leq-U_{i})=T(\lambda,|U_{i}|)<T(\lambda,\mu)$.
Hence, no matter what is the value of $U$,
we always have $P({\hbox{\rm{sign}}}(U)={\hbox{\rm{sign}}}(U+Z))<T(\lambda,\mu)^{n}$,
where $T(\lambda,\mu)=1-\frac{(2\lambda-\mu)^{2}}{8\lambda^{2}}$.

Moreover, for $i\in[n]$, if ${\hbox{\rm{sign}}}(U_{i})\neq{\hbox{\rm{sign}}}(U_{i}+Z_{i})$,
we have ($Z_{i}>0$ when $U_{i}<0$) or ($Z_{i}<0$ when $U_{i}>0$).
So,
$P({\hbox{\rm{sign}}}(U_{i})\neq{\hbox{\rm{sign}}}(U_{i}+Z_{i}))<1/2<T(\lambda,\mu)$,
since $T(\lambda,\mu)$ is always $\geq 1/2$.

Since $\{Z_{i}\}_{i\in[n]}$ is iid,
by Lemma [4.3](#S4.Thmlemma3), for a random vector $V\in\{-1,1\}^{n}$ we have

$$ $\begin{array}[]{ll}&P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x})=V)\\ =&P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(U+Z)=V)\\ =&\prod_{i=1}^{n}P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(U_{i}+Z_{i})=V_{i})\\ =&\prod_{i=1}^{n}({\mathbf{I}}({\hbox{\rm{sign}}}(U_{i})=V_{i})P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(U_{i})={\hbox{\rm{sign}}}(U_{i}+Z_{i}))\\ &+{\mathbf{I}}({\hbox{\rm{sign}}}(U_{i})\neq V_{i})P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(U_{i})\neq{\hbox{\rm{sign}}}(U_{i}+Z_{i})))\\ \leq&\prod_{i=1}^{n}({\mathbf{I}}({\hbox{\rm{sign}}}(U_{i})=V_{i})T(\lambda,\mu)+{\mathbf{I}}({\hbox{\rm{sign}}}(U_{i})\neq V_{i})T(\lambda,\mu))\\ =&T(\lambda,\mu)^{n}.\\ \end{array}$ $$

For $V\in\{-1,1\}^{n}$, denote
$Q(x,V,\rho)={\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho V)\neq\widehat{B}_{{\mathcal{F}}}(x))$.
We have

$$ $\begin{array}[]{ll}&{\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))\\ =&{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}))\neq\widehat{B}_{{\mathcal{F}}}(x))]]\\ =&{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}[\sum_{V\in\{-1,1\}^{n}}\\ &P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}({\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x})=V)Q(x,V,\rho)]\\ \leq&(T(\lambda,\mu))^{n}{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}[(\sum_{V\in\{-1,1\}^{n}}Q(x,V,\rho))]\\ \leq&(2T(\lambda,\mu))^{n}{\mathcal{C}}({\mathcal{F}},\rho)\end{array}$ $$

where $T(\lambda,\mu)=1-\frac{(2\lambda-\mu)^{2}}{8\lambda^{2}}$.
We have
$(2T(\lambda,\mu))^{n}=(2-\frac{4\lambda^{2}+\mu^{2}-4\lambda\mu}{4\lambda^{2}})^{n}=(1+\frac{4\lambda\mu-\mu^{2}}{4\lambda^{2}})^{n}\leq(1+\frac{\mu}{\lambda})^{n}\leq e^{n\mu/\lambda}$.
Hence, ${\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}},{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))<e^{n\mu/\lambda}{\mathcal{C}}({\mathcal{F}},\rho)$.
The theorem is proved.
∎

###### Proof.

### Appendix E. Proof of Theorem 4.6

See [4.6](#S4.Thmtheorem6)

###### Proof.

The proof is similar to that of Theorem [4.3](#S4.Thmtheorem3).
So certain details of the proof are omitted.
From equation ([15](#S4.E15)), we have

$$ $\begin{array}[]{l}\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}=\frac{\sum_{i=1}^{m}(W_{R,i}+W_{x,i}-W_{R,y}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}}.\end{array}$ $$

Let $m_{x}=\arg\max_{i\neq y}\{\langle W_{R,i},x\rangle\}$ and consider two
conditions $C_{1}$ and $C_{2}$:

Conditions $C_{1}$: $\langle W_{R,m_{x}},x\rangle\ >\ \langle W_{R,j},x\rangle+\sqrt{\lambda}$ for all $j\in[m]\setminus\{y,m_{x}\}$.

Conditions $C_{2}$: $||W_{R,m_{x}}-W_{R,y}||_{-\infty}>\mu$.

Note that condition $C_{2}$ implies
${\hbox{\rm{sign}}}((W_{R,i}-W_{R,y}+W_{x,i}-W_{x,y})={\hbox{\rm{sign}}}(W_{R,i}-W_{R,y})$.

We give the probabilities for conditions $C_{1}$ and $C_{2}$ to be valid.
From the proof of Theorem [4.3](#S4.Thmtheorem3),

$$ $\begin{array}[]{ll}&P_{W_{R}\sim{\mathcal{M}}_{m,n}(\lambda)}(C_{1})\geq 1-\frac{(m-2)^{2}}{\sqrt{\lambda}}.\end{array}$ $$

Let $f(x)$ be the density function of $W_{R,m_{x}}$. Then

$$ $\begin{array}[]{ll}&P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}(C_{2})\\ &\geq P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}(||W_{R,i}-W_{R,y}||_{-\infty}>\mu,\forall i\neq y)\\ &\geq(1-\frac{(m-1)\mu}{\lambda})^{n}\\ &\geq 1-\frac{(m-1)n\mu}{\lambda}.\end{array}$ $$

For $V\in\{-1,1\}^{n}$, it is also easy to see

$$ $\begin{array}[]{ll}&P({\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y})=V,\ C_{1},\ C_{2})\\ \leq&P({\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y})=V)\\ =&\sum_{i<y}P(m_{x}=i,{\hbox{\rm{sign}}}(W_{R,y})=V)+\\ &\sum_{i>y}P(m_{x}=i,{\hbox{\rm{sign}}}(W_{R,i})=V)\\ \leq&\sum_{i<y}P({\hbox{\rm{sign}}}(W_{R,y})=V)+\\ &\sum_{i>y}P({\hbox{\rm{sign}}}(W_{R,i})=V)\\ =&\frac{m-1}{2^{n}}.\end{array}$ $$

If conditions $C_{1}$ and $C_{2}$ are satisfied, then for any $y\in[m]\setminus\{y,m_{x}\}$, we have

$$ $\begin{array}[]{ll}&||W_{R,m_{x}}+W_{x,m_{x}}-W_{R,y}-W_{x,y}||_{-\infty}e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)}\\ >&\mu/2e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)}\\ >&\mu/2e^{{\widetilde{{\mathcal{F}}}_{j}(x)}+\sqrt{\lambda}-2\beta-n\mu/2}\\ =&\mu/2e^{-2b-n\mu/2}e^{\sqrt{\lambda}}e^{{\widetilde{{\mathcal{F}}}_{j}(x)}}\\ >&(2\lambda+\mu)me^{{\widetilde{{\mathcal{F}}}_{j}(x)}}\\ >&m||W_{R,j}+W_{x,j}-W_{R,y}-W_{x,y}||_{\infty}e^{\widetilde{{\mathcal{F}}}_{j}(x)}\end{array}$ $$

which means

$$ $\begin{array}[]{ll}&{\hbox{\rm{sign}}}(\sum_{i=1}^{m}(W_{R,i}+W_{x,i}-W_{R,y}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)})\\ =&{\hbox{\rm{sign}}}((W_{R,m_{x}}+W_{x,m_{x}}-W_{R,y}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)}),\end{array}$ $$

and hence

$$ $\begin{array}[]{ll}&{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x})\\ =&{\hbox{\rm{sign}}}(\frac{\sum_{i=1}^{m}(W_{R,i}+W_{x,i}-W_{R,y}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)}}{\sum_{i=1}^{m}e^{\widetilde{{\mathcal{F}}}_{i}(x)}})\\ =&{\hbox{\rm{sign}}}(\sum_{i=1}^{m}(W_{R,i}+W_{x,i}-W_{R,y}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{i}(x)})\\ =&{\hbox{\rm{sign}}}((W_{R,m_{x}}+W_{x,m_{x}}-W_{R,y}-W_{x,y})e^{\widetilde{{\mathcal{F}}}_{m_{x}}(x)})\\ =&{\hbox{\rm{sign}}}(W_{R,m_{x}}+W_{x,m_{x}}-W_{R,y}-W_{x,y})\\ =&{\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y}).\end{array}$ $$

Hence

$$ $\begin{array}[]{ll}&{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}\\ &[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}))\neq\widehat{B}_{{\mathcal{F}}}(x)){\mathbf{I}}(C_{1},\ C_{2})]\\ =&{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y}))\neq\widehat{B}_{{\mathcal{F}}}(x))\\ &{\mathbf{I}}(C_{1},\ C_{2})]\\ =&\sum_{V\in\{-1,1\}^{n}}P({\hbox{\rm{sign}}}(W_{R,m_{x}}-W_{R,y})=V,\ C_{1},\ C_{2})\\ &{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho V)\neq\widehat{B}_{{\mathcal{F}}}(x))\\ &\leq\frac{m-1}{2^{n}}\sum_{V\in\{-1,1\}^{n}}{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho V)\neq\widehat{B}_{{\mathcal{F}}}(x))\\ =&(m-1){\mathcal{C}}({\mathcal{F}},\rho).\end{array}$ $$

Finally, we have

$$ $\begin{array}[]{ll}&{\mathcal{C}}(B_{\widetilde{{\mathcal{F}}}}{\mathcal{A}}_{2},{\mathcal{U}}_{m,n}(\lambda))\\ =&{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}))\neq\widehat{B}_{{\mathcal{F}}}(x))]\\ \leq&{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[{\mathbf{I}}(\widehat{B}_{{\mathcal{F}}}(x+\rho{\hbox{\rm{sign}}}(\frac{\nabla L(\widetilde{{\mathcal{F}}}(x),y)}{\nabla x}))\neq\widehat{B}_{{\mathcal{F}}}(x))\\ &{\mathbf{I}}(C_{1},\ C_{2})+(1-{\mathbf{I}}(C_{1}))+(1-{\mathbf{I}}(C_{2}))]\\ \leq&(m-1){\mathcal{C}}({\mathcal{F}},\rho)+{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}{\mathbb{E}}_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}[(1-{\mathbf{I}}(C_{1}))+(1-{\mathbf{I}}(C_{2}))]\\ \leq&(m-1){\mathcal{C}}({\mathcal{F}},\rho)+{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}[1-P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}(C_{1})]+\\ &{\mathbb{E}}_{x\sim D_{{\mathbb{O}}}}[1-P_{W_{R}\sim{\mathcal{U}}_{m,n}(\lambda)}(C_{2})]\\ \leq&(m-1){\mathcal{C}}({\mathcal{F}},\rho)+\frac{(m-1)n\mu}{\lambda}+\frac{(m-2)^{2}}{\sqrt{\lambda}}.\\ \end{array}$ $$

The theorem is proved.
∎

###### Proof.

### Appendix F. Structures of DNN models used in the experiments

The networks in section [5.1](#S5.SS1):

Networks ${\mathcal{F}}^{(1)}$ and ${\mathcal{F}}^{(2)}$ for MNIST have the same structure:

Input layer: $N\times 1\times 28\times 28$, where $N$ is steps of training.

Hidden layer 1: a convolution layer with kernel $1\times 32\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max pooling with step=2.

Hidden layer 2: a convolution layer with kernel $32\times 64\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max pooling with step=2.

Hidden layer 3: a convolution layer with kernel $64\times 128\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max pooling with step=2.

Hidden layer 4: draw the output as $N\times 128\times 3\times 3$ $\to$ use a full connection with output size $N\times 128\times 2$ $\to$ do Relu.

Hidden layer 4: use a full connection with output size $N\times 100$ $\to$ do Relu.

Output layer: a full connection layer with output size $N\times 10$.

Networks ${\mathcal{F}}^{(1)}$ and ${\mathcal{F}}^{(2)}$ for CIFAR-10 have the same structure:

Input layer: $N\times 3\times 32\times 32$, where $N$ is steps of training.

Hidden layer 1: a convolution layer with kernel $3\times 64\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 2: a convolution layer with kernel $64\times 64\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 3: a convolution layer with kernel $64\times 128\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 4: a convolution layer with kernel $128\times 128\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max pooling with step=2.

Hidden layer 5: a convolution layer with kernel $128\times 256\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 6: a convolution layer with kernel $256\times 256\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 7: a convolution layer with kernel $256\times 256\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max pooling with step=2.

Hidden layer 8: a convolution layer with kernel $256\times 512\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 9: a convolution layer with kernel $512\times 512\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 10: a convolution layer with kernel $512\times 512\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max pooling with step=2.

Hidden layer 11: a convolution layer with kernel $512\times 512\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 12: a convolution layer with kernel $512\times 512\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu.

Hidden layer 13: a convolution layer with kernel $512\times 512\times 3\times 3$ with padding$=1$ $\to$ do a batch normalization $\to$ do Relu $\to$ use max pooling with step=2.

Hidden layer 14: draw the output as $N\times 2048$ $\to$ a full connection layer with output size $N\times 1024$ $\to$ do Relu.

Hidden layer 15: a full connection layer with output size $N\times 512$ $\to$ do Relu.

Hidden layer 16: a full connection layer with output size $N\times 128$ $\to$ do Relu.

Output layer: a full connection layer with output size $N\times 10$.

## Peer Reviews

confidence: 5
contribution: 1
initial_rating: 1
presentation: 1
questions: None.
soundness: 1
strengths: None.
summary: This paper designs a "provable" adversarial robustness enhancing method named "bias classifier" that is supposed to help ML models achieve high adversarial accuracy. A new information-theoretically inspired notation is proposed to measure the provable robustness of the bias classifier method. Experiments are conducted on two simple datasets, i.e., MNIST and CIFAR-10, and the results show that the adversarial robustness of models obtained from the bias classifier method is extremely weak (compared with existing adversarial robustness approaches).
weaknesses: This is a wrong paper and should be rejected immediately. Detailed comments are as follows:

1. The authors claim that their proposed bias classifier method has provable high adversarial robustness. However, according to the experiment results in Section 5, the robustness of the proposed method is actually extremely WEAK compared with existing adversarial robustness approaches. Specifically:

    - In Table 2, the proposed method can only achieve an adversarial accuracy (adversarial radius $\rho = 8/255$) of $31.25%%$ on the CIFAR-10 dataset under the AutoAttack [r1]. However, according to the original AutoAttack paper [r1], under the same setting, the best adversarial accuracy is $59.53%%$ in 2020 (see Table 2 in [r1]), which is almost two times larger than the performance of the proposed bias classifier method.

    - In Table 5, although the adversarial accuracies seems to be high, they are actually calculated based on adversarial examples crafted with **random noise** (see Line#394-400). Such an attack is even much weaker than the simplest FGSM attack. Thus, Table 5 is meaningless and does not show any advantages of the proposed bias classifier method.

2. The authors claim that existing defenses cannot give provable adversarial robustness (see Line#050). Unfortunately, this is a **wrong claim** since the well-known "certified robustness" method [r2] can indeed give the model provable and high adversarial robustness. For example, [r3] shows that with the help of diffusion models, when the adversarial perturbation is not stronger than $127/255$ under $l\_2$-norm, one can provablely ensure an adversarial accuracy of $65.5\\%$ on the CIFAR-10 dataset. [r4] further improves such an provable adversarial accuracy to $70.7\\%$. Given the profound success of existing certified robustness methods, I am wondering what is the advantage of the proposed bias classifier method compared with existing approaches.

3. The overall goal of the bias classifier method is to ensure ML models satisfy Eq.(11). Unfortunately, satisfying Eq.(11) does not mean that the model indeed enjoys a **provablely high** robustness. This is because Eq.(11) only ensures that small perturbations would not change model predictions, but the model clean accuracy could be very low in order to fulfill the requirement of Eq.(11). Actually, experiments in Section 5 indeed show that models obtained from bias classifier method and satisfying Eq.(11) indeed enjoys a very weak clean accuracy (since low robust accuracy implicitly imply low clean accuracy according to this paper). I suggest the authors read more papers about certified robustness, which can achieve "**provablely high** adversarial robustness".

**References:**

[r1] Croce F. and Hein M. "Reliable Evaluation of Adversarial Robustness with an Ensemble of Diverse Parameter-free Attacks." ICML 2020.

[r2] Cohen J. et al. "Certified Adversarial Robustness via Randomized Smoothing." ICML 2019.

[r3] Carlini N. et al. "(Certified!!) Adversarial Robustness for Free!" arXiv 2206.10550 / ICLR 2023.

[r4] Chen H. et al. "Diffusion Models are Certifiably Robust Classifiers." arXiv 2402.02316 / NeurIPS 2024.

---

confidence: 4
contribution: 2
initial_rating: 1
presentation: 2
questions: See weaknesses.
soundness: 1
strengths: - Originality:

The paper is somewhat original in considering test time training of a classifier.

- Quality:

The paper is well-written for the most part.

- Clarity:

The paper uses easy to follow instructions.

- Significance:

The paper considers a significant problem.
summary: The paper proposes Bias Classifiers which results from subtracting the linear approximation of a ReLU activated neural network on some test sample from the network. The paper is mostly focused on proving that if we assume that the norm of the Jacobian is less than some upper bound, then we can infer that the bias classifier is robust.
weaknesses: The paper is not ready for publication for various reasons. Here are some key observations:

1) The paper does not make use of standard notation, e.g. $\frac{\nabla F(x)}{\nabla x}$ is not meaningful as it seems to be a division of two vectors. Maybe the authors meant to write $\frac{\nabla F(x)}{|\nabla F(x)|}$?

2) The paper is testing a self-fulfilling prediction where an accurate classifier over benign test samples is forced to be constant on a neighborhood of the benign test sample and then finding out that it is both robust and accurate. A real test of robustness of this method should involve linearization on an adversarial test sample for which the reference network is *not* accurate.

3) The idea of information theoretic safety is very similar the idea of probabilistic robustness which is already discussed in the literature. Moreover, the description is vague, e.g. "Let $\mathcal{F}_R$ be a neural network that involves a random variable $R$ satisfying the distribution $\mathcal{R}$". What does it mean for a neural network to involve a random variable?

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: Please refer to Weakness.
soundness: 2
strengths: 1.	It is interesting to study the potential of utilizing the bias term of a neural network towards improved adversarial robustness. It seems that the authors theoretically show the bias classifier can defend against certain kinds of adversarial attacks.
2.	The empirical results seem to support the claim.
summary: This paper proposes to adversarially train the model and the bias and then take the bias as the classifier (dubbed as bias classifier), which improves the adversarial robustness. The authors theoretically show that the bias classifier can be information-theoretically safe against certain kinds of adversarial attacks, i.e., FGSM and CW attacks. Experimental results using the ResNet and VGG validate the effectiveness of the bias classifier.
weaknesses: 1.	The scope of the theory is limited. The authors only show the potential theoretically-information safety of the bias classifier against two certain adversarial attacks, i.e., FGSM and CW attacks, instead of the generalized adversarial attacks.
2.	The experiments are conducted on simple networks and small datasets, which cannot well support the effectiveness of the bias classifier. 
3.	The presentation is somewhat unclear. For example, what does ‘the original model gradient-base attacks’ refer to in Table 5? Besides, in Table 5, which results refers to the baseline?

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: Please refer to the weakness.
soundness: 2
strengths: The paper proposes and introduces a new adversarial-related definition called "information-theoretically safe" along with a new model termed "bias classifier," which may be valuable to the literature.
summary: The paper proposes a bias classifier and proofs that it serves as a universal classifier. Additionally, it introduces a new concept called "information-theoretically safe." Finally, based on experimental results, the authors claim that the adversarially trained bias classifier is information-theoretically safe against various white-box and black-box attack methods.
weaknesses: I strongly recommend that the author include a notation section in the revised version.

Here, I have listed several questions that arose while reviewing the paper.

Line 060-061, What is meant by a "random direction attack"? Does this refer to adding random noise to the DNN input? The motivation behind this new definition is unclear. The upper bound of adversarial accuracy for a classifier can be defined as its classification accuracy on clean examples. What advantage does the paper's definition offer over this approach? Additionally, if a DNN is highly sensitive to noise, achieving zero accuracy on any noisy input, it would trivially meet the "information-theoretically safe" criterion, despite having no robustness at all.


Line 063, "By the bias classifier, we mean to use $\mathcal{F}$’s bias part ${\mathcal{B_F}}(x)$  = $\mathcal{B}x$ : $\mathbb{I}^n \rightarrow R$ m as a classifier." A classifier is a function that maps the input $x$ to a output prediction. Could the authors clarify how the bias term of a classifier can itself function as a classifier? $\mathbb{I} = [0, 1]$. What is $\mathbb{I} $? Does [0, 1] means $\mathbb{I}$ is bounded between 0 and 1?

Line 099-100, [1] is a review paper that does not focus on DNN structure, so why is it cited here?

The related work section is somewhat disorganized. The authors just list different approches without detailed explaination. Further, Madry's adversarial training is well-known in the literature, it is not considered one of the most effective practical defense methods from nearly all perspectives. 

Line 119, Where is the new loss function?

Line 175-177, "The following existence theorem shows that the bias classifier has the power to interpolate any classification functions with arbvitray high probability". Minor: arbitrary is misspelled. 

Section 3.3 What's the motivation of using adversarial training to train the bias classifier? 

Line 229-230. 
Gradient-based adversarial attacks are well-established in the literature and have been studied for years; thus, the concept is not original to the author.

Line 249. 
What does the author mean by stating that a neural network involves a random variable? It is more common to say that a random variable follows a specific distribution.


Line 259, Could the authors further clarification on the formula of $\mathcal{C}(\mathcal{F}_R)$?

Equation (14) seems wrong.

Line 379-380, What is the "original based AutoAttack"?

Line 480-481, "bias classifier is essentially different from gradient obfuscated defences." I don't believe it is appropriate to make such a strong statement based on experiments involving only one method published in 2018. Could the author provide more context or additional evidence?

The experimental results are insufficient. The authors did not benchmark and compare against the state-of-the-art methods and only test their method on small datasets like MNIST and CIFAR-10.

[1] Han Xu, Yao Ma, Hao-Chen Liu, Debayan Deb, Hui Liu, Ji-Liang Tang, and Anil K Jain. Adversarial attacks and defenses in images, graphs and text: A review. International journal of automation and computing, 17:151–178, 2020.