# A dynamical argument for a Ramsey property

Enhui Shi  Soochow University, Suzhou, Jiangsu 215006, China
<EMAIL_ADDRESS>and  Hui Xu  Soochow University, Suzhou, Jiangsu 215006,
China<EMAIL_ADDRESS>
###### Abstract.

We show by a dynamical argument that there is a positive integer valued
function $q$ defined on positive integer set $\mathbb{N}$ such that $q([\log
n]+1)$ is a super-polynomial with respect to positive $n$ and

$\limsup_{n\rightarrow\infty}r\left((2n+1)^{2},q(n)\right)<\infty,$

where $r(\ ,\ )$ is the opposite-Ramsey number function.

##  1\. Introduction and preliminaries

For positive integers $p$ and $q$, we define the opposite-Ramsey number
$r(p,q)$ to be the maximal number $k$ for which every edge-coloring of the
complete graph $K_{q}$ with $p$ colors yields a monochromatic complete
subgraph of order $k$ (the order of a graph means the number of its vertices).

The following is implied by the well-known Ramsey’s theorem.

######  Theorem 1.1.

Let $p$ be a fixed positive integer. Then

$\liminf_{q\rightarrow\infty}r\left(p,q\right)=\infty.$

One may expect that if $p=p(n)$ and $q=q(n)$ are positive integer valued
functions defined on $\mathbb{N}$ and the speed of $q(n)$ tending to infinity
is much faster than that of $p(n)$ as $n$ tends to infinity, then we still
have

$\liminf_{n\rightarrow\infty}r\left(p(n),q(n)\right)=\infty.$

The purpose of the paper is to show by a dynamical argument that this is not
true in general even if $p(n)$ is a polynomial and $q([\log n]+1)$ is a super-
polynomial. By a super-polynomial, we mean a function
$f:\mathbb{N}\rightarrow\mathbb{R}$ such that for any polynomial $g(n)$,

$\liminf_{n\rightarrow\infty}\frac{|f(n)|}{|g(n)|}=\infty.$

Let $(X,d)$ be a compact metric space. For any $\varepsilon>0$, let
$N(\varepsilon)$ denote the minimal number of subsets of diameter at most
$\varepsilon$ needed to cover $X$. The lower box dimension of $X$ is defined
to be

(1.1) $\underline{\dim}_{B}(X,d)=\liminf_{\varepsilon\rightarrow 0}\frac{\log
N(\varepsilon)}{\log 1/\varepsilon}.$

For a subset $E$ of $X$ and $\varepsilon>0$, we say $E$ is
$\varepsilon$-separated if for any distinct $x,y\in X$,
$d(x,y)\geq\varepsilon$. Let $S(\varepsilon)$ denote the cardinality of a
maximal $\varepsilon$-separated subset of $X$. It is easy to verify
$N(\varepsilon)\leq S(\varepsilon)\leq N(\varepsilon/2)$. Thus

(1.2) $\underline{\dim}_{B}(X,d)=\liminf_{\varepsilon\rightarrow 0}\frac{\log
S(\varepsilon)}{\log 1/\varepsilon}.$

Furthermore, it is easy to see that

(1.3) $\underline{\dim}_{B}(X,d)=\liminf_{n\rightarrow\infty}\frac{\log
S(1/n)}{\log n}.$

We use $\dim(X)$ to denote the topological dimension of $X$. It is well known
that the topological dimension of $X$ is always no greater than its lower box
dimension with respect to any compatible metric.

A continuous action $G\curvearrowright X$ of group $G$ on $X$ is said to be
expansive if there exists $c>0$ such that for any two distinct points $x,y\in
X$, $\sup_{g\in G}d(gx,gy)>c$. For $v=(v_{1},\cdots,v_{k})\in\mathbb{Z}^{k}$,
let $|v|$ denote $\max\\{|v_{1}|,\cdots,|v_{k}|\\}$.

The following lemma is due to T. Meyerovitch and M. Tsukamoto.

######  Lemma 1.2.

[4, Lemma 4.4] Let $k$ be a positive integer and $T:\mathbb{Z}^{k}\times
X\rightarrow X$ be a continuous action of $\mathbb{Z}^{k}$ on a compact metric
space $(X,d)$. If the action is expansive, then there exist $\alpha>1$ and a
compatible metric $D$ on $X$ such that for any positive integer $n$ and any
two distinct points $x,y\in X$ satisfying $D(x,y)\geq\alpha^{-n}$, we have

$\max_{v\in\mathbb{Z}^{k},|v|\leq n}D(T^{v}x,T^{v}y)\geq\frac{1}{4\alpha}.$

######  Lemma 1.3.

If $(X,d)$ is a compact metric space of infinite dimension, then $S(1/n)$ is a
super-polynomial with respect to variable $n$.

###### Proof.

Since $\dim(X)\leq\underline{\dim}_{B}(X,d)$, we have

(1.4) $\underline{\dim}_{B}(X,d)=\liminf_{n\rightarrow\infty}\frac{\log
S(1/n)}{\log n}=\infty.$

Thus, for any positive integer $k$,
$\liminf_{n\rightarrow\infty}\frac{S(1/n)}{n^{k}}=\infty$. ∎

##  2\. Main results

For a positive real number $x$, we use $[x]$ to denote its integer part.

######  Theorem 2.1.

There is a function $q:\mathbb{N}\rightarrow\mathbb{R}$ such that $q([\log
n]+1)$ is a super-polynomial and

$\limsup_{n\rightarrow\infty}r\left((2n+1)^{2},q(n)\right)<\infty.$

###### Proof.

Let $T:\mathbb{Z}^{2}\times X\rightarrow X$ be an expansive continuous action
on a compact metric space $(X,d)$ of infinite dimension (see [5] where an
expansive $\mathbb{Z}^{2}$-action on $\mathbb{T}^{\infty}$ was constructed).
By Lemma 1.2, there exist $\alpha>1$ and a compatible metric $D$ on $X$ such
that for any positive integer $n$ and any two distinct points $x,y\in X$ with
$D(x,y)\geq\alpha^{-n}$,

$\max_{v\in\mathbb{Z}^{2},|v|\leq n}D(T^{v}x,T^{v}y)\geq\frac{1}{4\alpha}.$

For each $n\in\mathbb{N}$, let $V_{n}$ be a maximal $\alpha^{-n}$-separated
set of $(X,D)$. Hence $|V_{n}|=S(\alpha^{-n})$. Let $G_{n}$ be the complete
graph $K_{S(\alpha^{-n})}$ whose vertex set is $V_{n}$. Now we use the color
set $C_{n}=\\{v\in\mathbb{Z}^{2}:|v|\leq n\\}$ to color the edges of $G_{n}$.
Since $V_{n}$ is $\alpha^{-n}$-separated, for any two distinct points $x,y\in
V_{n}$, $D(x,y)\geq\alpha^{-n}$. By Lemma 1.2, there exists $v\in C_{n}$ such
that $D(T^{v}x,T^{v}y)\geq\frac{1}{4\alpha}$. Then we color the edge
$\\{x,y\\}$ by $v$. By the definition of opposite-Ramsey number, there is a
monochromatic complete subgraph $H_{n}$ of order
$r\left((2n+1)^{2},S(\alpha^{-n})\right)$.

By Lemma 1.3, $S(1/n)$ is a super-polynomial. Let $q(n)=S(\alpha^{-n})$. Thus
$q([\log n]+1)$ is a super-polynomial with respect to positive $n$. Assuming
that the conclusion of the Theorem is false, we have

$\limsup_{n\rightarrow\infty}r\left((2n+1)^{2},q(n)\right)=\infty.$

Therefore, there is an increasing subsequence $(n_{i})$ of positive integers
such the the sequence of orders of $H_{n_{i}}$ is unbounded. Since $H_{n_{i}}$
is monochromatic, there exists $v_{n_{i}}\in C_{n_{i}}$ such that the image of
vertex set of $H_{n_{i}}$ under $T^{v_{n_{i}}}$ is
$\frac{1}{4\alpha}$-separated. These imply that there are arbitrarily large
$\frac{1}{4\alpha}$-separated subsets of $X$, which contradicts the
compactness of $X$. Thus we complete the proof. ∎

##  3\. Comparison with Classical Ramsey number

For any positive integers $k$ and $g$, the Ramsey number $R_{g}(k)$ is defined
to be the minimal number $n$ for which every edge-coloring of the complete
graph $K_{n}$ with $g$ colors yields a monochromatic complete subgraph of
order $k$.

By Corollary 3 of Greenwood and Gleason in [1], $R_{g}(k)$ has an upper bound
$g^{gk}$. In [2] Lefmann and Rödl obtained a lower bound $2^{\Omega(gk)}$ for
$R_{g}(k)$. Thus

(3.1) $2^{\Omega((2n+1)^{2}k)}\leq
R_{(2n+1)^{2}}(k)\leq\left((2n+1)^{2}\right)^{(2n+1)^{2}k}.$

Suppose $r\left((2n+1)^{2},q(n)\right)=r<\infty$. Then it implies that

  * (1)

every edge-coloring of complete graph $K_{q(n)}$ with $(2n+1)^{2}$ colors
yields a monochromatic complete subgraph of order $r$, hence

(3.2) $q(n)\geq R_{(2n+1)^{2}}(r);$

  * (2)

there exists an edge-coloring of $K_{q(n)}$ with $(2n+1)^{2}$ colors such that
there is no monochromatic complete subgraph of order $r+1$, hence

(3.3) $q(n)\leq R_{(2n+1)^{2}}(r+1).$

Thus $q(n)$ gives a lower bound of $R_{(2n+1)^{2}}(r+1)$ and an upper bound of
$R_{(2n+1)^{2}}(r)$. By Theorem 2.1, every expansive $\mathbb{Z}^{2}$-action
on a compact metric space of infinite dimension gives rise to such a $q(n)$.
In addition, there is a positive integer $r$ and an increasing subsequence
$(n_{i})$ of positive integers such that for any $i\in\mathbb{N}$,
$r\left((2n_{i}+1)^{2},q(n_{i})\right)=r$. Therefore, we obtain a lower bound
of $R_{(2n_{i}+1)^{2}}(r+1)$ and an upper bound of $R_{(2n_{i}+1)^{2}}(r)$ for
each $i\in\mathbb{N}$.

If $q(\log n)$ is a super-polynomial, then we claim that for any $A\geq 0$,

(3.4) $\liminf_{n\rightarrow\infty}\frac{q(n)}{A^{n}}=\infty.$

In fact, take a positive integer $m$ such that $e^{m}\geq A$. Then

$\displaystyle\liminf_{n\rightarrow\infty}\frac{q(n)}{A^{n}}\geq\liminf_{n\rightarrow\infty}\frac{q(n)}{e^{mn}}=\liminf_{n\rightarrow\infty}\frac{q(\log(e^{n}))}{(e^{n})^{m}}=\infty.$

The lower bound of $R_{(2n+1)^{2}}(r+1)$ obtained by (3.1) is
$2^{\Omega\left((2n+1)^{2}(r+1)\right)}$ which is also faster than any
exponential growth. If there is an expansive $\mathbb{Z}$-action on a compact
metric space of infinite dimension, then we can get a lower bound for
$R_{2n+1}(r+1)$ which is faster than the classical bound
$2^{\Omega\left((2n+1)(r+1)\right)}$. Unfortunately, in [3] Mañé showed that
such action does not exist. If we can construct an expansive
$\mathbb{Z}^{2}$-action on a compact metric space of infinite dimension such
that the condition $D(x,y)\geq\alpha^{-n}$ in Lemma 1.2 can be replaced by
$D(x,y)\geq\alpha^{-n^{2}}$, then we can show that $q(n)$ obtained in Theorem
2.1 satisfies that $q([\sqrt{\log n}]+1)$ is a super-polynomial. Then it
satisfies $\liminf_{n\rightarrow\infty}\frac{q(n)}{A^{n^{2}}}=\infty$. Hence
$q(n)$ is faster than the classical lower bound
$2^{\Omega\left((2n+1)^{2}(r+1)\right)}$. Therefore, we leave the following
question.

######  Question 3.1.

Is there an expansive $\mathbb{Z}^{2}$-action on a compact metric space
$(X,d)$ of infinite dimension and $\alpha>1$ such that for any positive
integer $n$ and any two distinct points $x,y\in X$ satisfying
$d(x,y)\geq\alpha^{-n^{2}}$, we have

$\max_{v\in\mathbb{Z}^{2},|v|\leq n}d(T^{v}x,T^{v}y)\geq\frac{1}{4\alpha}.$

A positive answer to Question 3.1 can give a better estimate of the lower
bound of $R_{(2n_{i}+1)^{2}}(r+1)$, where $(n_{i})$ and $r$ come from the
system. By (3.2), a negative answer also gives a better estimate of the upper
bound of $R_{(2n_{i}+1)^{2}}(r)$.

Finally, we remark that the above comparison between $q(n)$ and the bound of
Ramsey is only for a subsequence of positive integers. However, dealing with a
concrete system we may obtain more information and can get a special edge-
coloring of $K_{q(n)}$ as the proof of Theorem 2.1. Our method may give a new
direction to estimate the bounds of Ramsey numbers and construct edge-
colorings of big graphs.

### Acknowledgements

We would like to thank Professor Bingbing Liang and Professor Xin Wang for
their helpful comments.

## References

  * [1] R. E. Greenwood and A. M. Gleason, Combinatiorial Relations and Chromatic Graphs. Canadian Journal of Mathematics 7(1955):1-7.
  * [2] H. Lefmann and V. Rödl, On canonical Ramsey numbers for complete graphs versus paths. J. Combin. Theory Ser. B 58 (1993), no. 1, 1-13.
  * [3] R. Mañé, Expansive homeomorphisms and topological dimension, Trans. Amer. Math. Soc. 252(1979), 313-319.
  * [4] T. Meyerovitch and M. Tsukamoto, Expansive multiparameter actions and mean dimension. Trans. Amer. Math. Soc. 371 (2019), no. 10, 7275-7299.
  * [5] E. Shi and L. Zhou, The nonexistence of expansive $\mathbb{Z}^{d}$ actions on graphs. Acta Math. Sin. (Engl. Ser.) (2005) 1509-1514.


# Entangled Pair Resource Allocation under Uncertain Fidelity Requirements

Rakpong Kaewpuang1, Minrui Xu1, Stephen John Turner2, Dusit Niyato1, Han Yu1,
and Dong In Kim3
1School of Computer Science and Engineering, Nanyang Technological University,
Singapore
2School of Information Science and Technology, Vidyasirimedhi Institute of
Science and Technology, Thailand
3School of Information and Communication Engineering, Sungkyunkwan University,
South Korea

###### Abstract

In quantum networks, effective entanglement routing facilitates remote
entanglement communication between quantum source and quantum destination
nodes. Unlike routing in classical networks, entanglement routing in quantum
networks must consider the quality of entanglement qubits (i.e., entanglement
fidelity), presenting a challenge in ensuring entanglement fidelity over
extended distances. To address this issue, we propose a resource allocation
model for entangled pairs and an entanglement routing model with a fidelity
guarantee. This approach jointly optimizes entangled resources (i.e.,
entangled pairs) and entanglement routing to support applications in quantum
networks. Our proposed model is formulated using two-stage stochastic
programming, taking into account the uncertainty of quantum application
requirements. Aiming to minimize the total cost, our model ensures efficient
utilization of entangled pairs and energy conservation for quantum repeaters
under uncertain fidelity requirements. Experimental results demonstrate that
our proposed model can reduce the total cost by at least 20% compared to the
baseline model.

###### Index Terms:

Quantum networks, entanglement routing, end-to-end fidelity, entanglement
purification, entangled pair resource allocation, stochastic programming.

##  I Introduction

In recent decades, quantum networks have emerged as a groundbreaking
advancement, enabling the support of innovative applications that surpass the
capabilities of classical networks. These applications include quantum key
distribution (QKD), distributed quantum computing, and quantum encryption
protocols [1]. Quantum networks rely on entangled qubit pairs, which serve as
a fundamental component for end-to-end quantum communication between two
quantum nodes. This unique feature allows for secure communication, robust
computational power, and novel cryptographic schemes that are resistant to
current and future threats. Furthermore, quantum networks pave the way for the
development of new technologies and applications that leverage quantum
phenomena such as superposition and entanglement, providing substantial
advantages over their classical counterparts in terms of speed, security, and
efficiency. Consequently, the exploration of quantum networks and their
potential continues to gain momentum, driving research into their optimization
and integration within existing communication infrastructures.

In quantum networks, quantum nodes are interconnected by optical fiber links
[2]. Quantum nodes possess the capability to generate quantum information and
store it within their quantum memories. Furthermore, they can transmit and
receive quantum information between nodes [3, 4]. Prior to exchanging
information, the quantum network must establish an entanglement connection
between the nodes and enable the transmission of quantum information encoded
as a quantum bit (qubit) over this connection. Consequently, the quantum
source node can utilize entangled pairs in the entanglement connection to
transmit information to the quantum destination node. When a quantum source
node is distant from the quantum destination node, entanglement connections
are generated based on routing, and quantum repeaters (i.e., intermediate
quantum nodes in the routing) connect the quantum source node to the quantum
destination node using entanglement swapping, or joint Bell state measurements
at quantum repeaters, for a remote entanglement connection [1]. For large-
scale quantum networks, efficiently utilizing entangled pairs and identifying
optimal routing for entanglement connections are vital challenges. By
optimizing the use of entangled pairs and routing, the energy consumption of
quantum repeaters can be minimized in quantum networks.

Entanglement fidelity is a crucial factor in guaranteeing the quality of
remote entanglement connections, as quantum repeaters may not generate
entangled pairs with the desired fidelity due to system noise [3]. Low-
fidelity entangled pairs can impact the quality of services provided by
quantum applications [5]. For instance, the security of key distribution in
quantum cryptography protocols, such as the BB84 protocol, can be compromised
if entanglement fidelity is lower than the quantum bit error rate requirements
[6]. Nevertheless, entanglement purification techniques can increase the
fidelity value of entangled pairs [7]. These techniques use additional
entangled pairs to achieve higher fidelity values, but determining the optimal
number of additional entangled pairs to satisfy uncertain fidelity
requirements for quantum applications remains a challenge and is often
overlooked in existing works.

To address these challenges, in this paper, we propose a stochastic resource
management framework for achieving optimal entangled resources in quantum
networks and introduce a dynamic entanglement purification algorithm to
adaptively increase fidelity values. We consider entangled pair resource
allocation and fidelity-guaranteed entanglement routing within quantum
networks. Specifically, we solve the optimization problem to obtain the
optimal number of entangled pairs and fidelity values, satisfying all requests
(i.e., multiple quantum source nodes and quantum destination nodes), while
considering the uncertainty of fidelity requirements during resource
allocation and routing.

The major contributions of this paper can be summarized as follows:

  * •

We propose a novel entangled pair resource allocation and fidelity-guaranteed
entanglement routing model under uncertainty of fidelity requirements in
quantum networks. Additionally, we introduce a dynamic entanglement
purification algorithm to elastically improve fidelity values.

  * •

We formulate and solve a two-stage stochastic programming (SP) model to obtain
not only the optimal decisions on entangled pair resource allocation but also
fidelity-guaranteed entanglement routing with the minimum number of quantum
repeaters in quantum networks. In the proposed model, the entangled pair
resource allocation and fidelity-guaranteed entanglement routing are jointly
calculated, with statistical information in the first stage and realization in
the second stage.

  * •

We evaluate the performance of the proposed model through comprehensive
experiments under real-world network topologies. Moreover, we compare the
solution of the proposed model with those of baseline models to demonstrate
the superior performance of our approach.

##  II Related Work

In this section we provide a brief overview of relevant works in the field,
highlighting their contributions and limitations. The authors of [3] presented
a fidelity-guaranteed entanglement routing scheme to ensure fidelity for
source-destination pairs in quantum networks. In [3], they initially proposed
an iterative routing algorithm (Q-PATH) for optimal entanglement routing with
minimum entangled pair cost for single source-destination pairs. For multiple
source-destination pairs, they introduced a greedy-based algorithm to minimize
the entanglement routing path and entangled pair count. Similarly,[1] authors
proposed an efficient routing scheme for multiple entanglement generation
requests in quantum lattice networks with limited quantum resources. Their
objective was to allocate quantum resources effectively, meeting entanglement
generation requests and fidelity thresholds. In[8], the authors suggested a
linear programming model to maximize the achievable expected entanglement
generation rate between multiple source-destination pairs in a quantum
network, satisfying the end-to-end fidelity demand. This problem resembled
that in [3]. Nonetheless,[8] did not consider the purification process.
Therefore, in[9], the authors introduced redundant entanglement provisioning
and selection (REPS) for throughput maximization in multi-hop quantum networks
with multiple source-destination pairs. The authors of [10] proposed an
adaptive routing scheme addressing quantum memory failures in quantum nodes
within quantum networks, finding the shortest entanglement paths between
source and destination quantum nodes. The author of [11] suggested an optimal
routing protocol for quantum networks, identifying the path with the highest
end-to-end entanglement rate between source-destination pairs in quantum
networks. In [12], the authors employed graph-theoretic tools (i.e., graph
states) to reduce the number of necessary measurements and proposed a routing
method for quantum communication between source and destination nodes.

However, none of these existing works address the problem of jointly managing
entangled pair resources and optimizing fidelity-guaranteed entanglement
routing under fidelity requirement uncertainty.

##  III System Model

Figure 1:  Short-distance and long-distance quantum teleportation for qubit
transmission in a quantum network.

We propose entangled pair resource allocation and fidelity-guaranteed
entanglement routing in a quantum network for quantum applications. In the
quantum network, quantum nodes connected via optical fiber links can generate,
store, exchange, and process quantum information [3, 4], as shown in Figs. 1.

In Fig. 1, the quantum network establishes an entanglement connection between
the source and destination nodes to enable the transmission of quantum
information in the form of qubits. To create this connection over long
distances, entangled pairs are generated between intermediate quantum nodes
located between the source and destination nodes. As illustrated in Fig. 1(b),
the quantum repeater (an intermediate node) establishes communication with
other quantum nodes through entanglement swapping, creating a long-distance
entanglement connection. When quantum source node 2 attempts to transmit
information to quantum destination node 2, it first becomes entangled with the
quantum repeater, which in turn entangles with quantum destination node 2.
Subsequently, the repeater performs entanglement swapping, generating a long-
distance connection between quantum source node 2 and quantum destination node
2 for the transmission of qubits.

The quantum network is represented by a network graph
$G(\mathcal{M},\mathcal{E})$ where $\mathcal{M}$ and $\mathcal{E}$ are a set
of quantum nodes and a set of edges between two quantum nodes, respectively.
Each quantum node has finite quantum memories that are used to store qubits.
The maximum capacity defined as the maximum number of entangled pairs of an
edge between quantum nodes $i$ and $j$ is denoted as $C^{\mathrm{etp}}_{i,j}$
where $i$ and $j$ $\in\mathcal{M}$. The entanglement purification is performed
on each edge to satisfy the fidelity threshold that is denoted as
$F^{\mathrm{ths}}_{i,n}$ where $i$ and $n$ $\in\mathcal{M}$. In each round of
the entanglement purification operation, entangled pairs are utilized. The
fidelity value of multiple entangled pairs on the same edge is identical while
the fidelity value on different edges can vary [1].

Figure 2: An example of three purification rounds in the entanglement
purification process.

###  III-A Network Model

The quantum node, quantum repeater, quantum source, quantum destination, and
quantum channel are described as follows:

####  III-A1 Quantum Node, Quantum Repeater, Quantum Source, and Quantum
Destination

A quantum node can create, exchange, and process quantum information in
quantum networks [4]. The quantum node contains the quantum repeater’s
function, i.e., entanglement generation, purification, and swapping. Quantum
processors and quantum applications can be installed in quantum nodes to
establish a quantum network and support the quantum applications. In the
quantum repeater, the number of quantum memories is limited, and the
entanglement generation, purification, and swapping are applied [3]. In
quantum networks, all quantum nodes have limited computing and storage
capacities, and are connected via classical networks [3]. A quantum network is
typically managed by a centralized controller through classical networks. This
controller is responsible for overseeing all the quantum nodes and storing
essential information about the network, including its topology and resources.
The quantum nodes can report any updates to this information to ensure it
remains accurate and up to date. To support the quantum application, a quantum
source node can establish an entanglement connection with the quantum
destination node according to the requirement of the quantum application.

####  III-A2 Quantum Channel

Each quantum channel established between intermediate quantum nodes is used to
share entangled pairs of qubits between the nodes. These entangled pairs are
shared via both optical fibers [3, 4] and free space[13]. Qubits are encoded
and then transmitted using quantum teleportation between the entangled pairs
of qubits. Therefore, a capacity (i.e., the number of entangled pairs) of a
quantum channel between intermediate quantum nodes is generated in advance by
the entanglement generation process, e.g., nitrogen-vacancy centers [15],
before qubit transmission. The entanglement generation process, particularly
when using the nitrogen-vacancy center, can be seen as a deterministic black
box [3]. In addition, the fidelity of the entangled pair on each quantum
channel is approximately computed beforehand by the deterministic equations
without noise [14] [15], e.g., the deterministic state-delivery protocol [15].

The three steps for an entanglement routing process are described as follows:
First, the quantum source node, the quantum destination node, and intermediate
quantum nodes generate the entangled pairs in the quantum channel. After that,
the network controller calculates the routing and allocates entangled pair
resources in the network. Finally, the network controller instructs the
corresponding quantum nodes to perform entanglement purification to increase
the fidelity of entangled pairs to satisfy the requirement of the quantum
application. For the multi-hop entanglement connection, entanglement swapping
is introduced to build the long-distance entanglement.

Entanglement generation, purification, and swapping to establish entanglement
connections in the quantum networks can be described as follows:

####  III-A3  Entanglement Generation

To establish physical entanglement between two manageable quantum nodes, they
are linked to an intermediate station, referred to as the heralding station,
through optical fibers. A range of hardware platforms can be employed for this
objective, such as nitrogen-vacancy centers in diamond [16]. Upon successful
generation at the heralding station, the entangled pair is retained in the
memory of both quantum nodes. Serving as a valuable resource, the entangled
pair facilitates entanglement communication and qubit transmission between the
nodes.

####  III-A4 Entanglement Purification

Entanglement purification is applied to increase the fidelity of a Bell pair
by combining two low-fidelity Bell pairs into a single high-fidelity Bell
pair, which is implemented by controlled-NOT (C-NOT) gates or a polarizing
beam splitter [17]. The entanglement purification function [3] is expressed as
follows:

$\displaystyle
f^{\mathrm{pur}}(q_{1},q_{2})=\frac{q_{1}q_{2}}{q_{1}q_{2}+(1-q_{1})(1-q_{2})}.$
(1)

$q_{1}$ and $q_{2}$ are the fidelity of two Bell pairs in purification
operation. The dynamic entanglement purification algorithm is introduced to
perform the purification operation in Eq. (1) to satisfy the requirement of
quantum applications. In the entanglement purification algorithm, each round
of purification operation in Eq. (1) utilizes an additional entangled pair.
For example, Fig. 2 shows three rounds of entanglement purification operations
to increase the fidelity value from 0.75 to 0.987 by utilizing entangled
pairs. The entanglement purification algorithm can be expressed in Algorithm
1. The entanglement purification algorithm is applied to the SP model in the
constraints of Eqs. (14) and (14).

####  III-A5 Entanglement Swapping

When the quantum source node is far away from the quantum destination node,
entanglement swapping is introduced to establish distant entanglement
connections along the routing. By using entanglement swapping, the multi-hop
entanglement connection can be established along the routing of quantum
repeaters containing entangled pairs.

Algorithm 1 Dynamic Entanglement Purification, i.e.,
$\mathbf{F}^{\mathrm{epg}}(\cdot)$

1: Input: The number of entangled pairs between quantum nodes $i$ and $j$

2: Output: The resulting fidelity value ($f_{v}$) between quantum nodes $i$
and $j$

3: $N$ is the total number of entangled pairs - 1.

4: $f_{v}$ is the fidelity value.

5: for $p\\_round$ = $1$ to $N$ do

6: if $p\\_round$ == 1 then

7: $q_{1}$ = the fidelity of the first pair

8: $q_{2}$ = the fidelity of the second pair

9: $f_{v}=f^{\mathrm{pur}}(q_{1},q_{2})$

10: else

11: $f_{v}$ = $f_{v}$ of $p\\_round-1$

12: $q_{2}$ = the fidelity of the next pair

13: $f_{v}=f^{\mathrm{pur}}(f_{v},q_{2})$

14: end if

15: $p\\_round=p\\_round+1$

16: end for

##  IV Problem Formulation

###  IV-A Model Description

We define sets and decision variables in the proposed formulation as follows:

  * •

${\mathcal{M}}$ represents a set of all quantum nodes that are present within
the network.

  * •

${\mathcal{Q}}_{n}$ represents a set of all outbound links from node
$n\in{\mathcal{M}}$.

  * •

${\mathcal{J}}_{n}$ represents a set of all inbound links to node
$n\in{\mathcal{M}}$.

  * •

${\mathcal{R}}$ represents a set of requests, i.e., quantum source and
destination nodes, in the network.

  * •

$x_{i,j,r}$ represents a binary decision variable indicating whether request
$r\in\mathcal{R}$ will take a route with the link from nodes $i$ to $j$ or
not, i.e., $x_{i,j,r}\in\\{0,1\\}$, $i,j\in\mathcal{M}$.

  * •

$y^{\mathrm{r}}_{i,j,r}$ represents a decision variable indicating the number
of entangled pairs between nodes $i$ and $j$ in the reservation phase, i.e.,
$y^{\mathrm{r}}_{i,j,r}\in\\{0,1,2,\dots\\}$.

  * •

$y^{\mathrm{e}}_{i,j,r,\omega}$ represents a decision variable indicating the
number of entangled pairs between nodes $i$ and $j$ under scenario $\omega$ in
the utilization phase, i.e.,
$y^{\mathrm{e}}_{i,j,r,\omega}\in\\{0,1,2,\dots\\}$.

  * •

$y^{\mathrm{o}}_{i,j,r,\omega}$ represents a decision variable indicating the
number of entangled pairs between nodes $i$ and $j$ under scenario $\omega$ in
the on-demand phase, i.e.,
$y^{\mathrm{o}}_{i,j,r,\omega}\in\\{0,1,2,\dots\\}$.

We consider the uncertainty of fidelity requirements for request $r$ in the SP
model. As such, fidelity requirements are treated as uncertain parameters. Let
$\tilde{\omega}$ and $\omega$ represent the random variables of fidelity
requirements and a scenario of request $r$, respectively. A scenario
represents a realization of the random variable $\tilde{\omega}$, and its
value can be taken from the set of scenarios. We denote the set of all
scenarios for each fidelity requirement (i.e., a scenario space), as
$\Upsilon$. We denote the set of all scenarios for request $r$ as
$\Omega_{r}$. The set of all scenarios for each fidelity requirement is
described as follows:

$\displaystyle\Upsilon$ $\displaystyle=$
$\displaystyle{\displaystyle\prod_{r\in\mathcal{R}}}\Omega_{r}=\Omega_{1}\times\Omega_{2}\times\dots\times\Omega_{|\mathcal{R}|}$
(2) Where $\displaystyle\Omega_{r}=\\{0.0,\dots,1.0\\}.$ (3)

Therefore, $\omega$, $\times$, and $|\mathcal{R}|$ are the scenario space of
request $r$ (i.e., $\omega\in\Omega_{r}$), the Cartesian product, and the
cardinality of the set $\mathcal{R}$, respectively. The probability that the
fidelity requirement of request $r$ is realized can be denoted as
$\mathbb{P}_{r}(\omega)$.

###  IV-B Stochastic Programming Formulation

We propose the two-stage SP model [18] to provision entangled pair resources
and fidelity-guaranteed entanglement routing in quantum networks for quantum
applications. In the first stage, decisions on provisioning the number of
entangled pairs and finding the routing according to the fidelity requirements
are performed. In the second stage, when the numbers of entangled pairs in the
first stage are inadequate, the number of entangled pairs in the on-demand
phase is provisioned to satisfy the rest of the fidelity requirements.

The objective function is designed to achieve the minimum total cost of
entangled pair utilization of all quantum nodes to satisfy all the requests,
which is expressed as follows:

$\displaystyle\min_{x_{i,n,r},y^{\mathrm{r}}_{i,n,r}}$
$\displaystyle\sum_{r\in{\mathcal{R}}}\sum_{n\in{\mathcal{M}}}\sum_{i\in{\mathcal{J}}_{n}}\big{(}(E^{\mathrm{eng}}_{n,r}+S^{\mathrm{stp}}_{n,r})x_{i,n,r}$
(4)
$\displaystyle+R^{\mathrm{r}}_{n,r}y^{\mathrm{r}}_{i,n,r}\big{)}+{\mathbf{E}}\left[{\mathscr{L}}(y^{\mathrm{r}}_{i,n,r},\tilde{\omega})\right].$

Theoretically, we can convert the SP model with the random variable
$\tilde{\omega}$ into a deterministic equivalent formulation [18], expressed
in Eqs. (5) - (14). The objective function in Eq. (5) corresponds to and
shares the same meaning as Eq. (4). Eq. (14) enforces that the number of
outbound routes exceeds the number of inbound routes if the node is the source
node $S_{r}$ of request $r$. Eq. (14) dictates that the number of inbound
routes surpasses the number of outbound routes if the node is the destination
node $D_{r}$ of request $r$. Eq. (14) requires that the number of outbound
routes equals the number of inbound routes if the node serves as an
intermediate node for request $r$. Eq. (14) ensures no loop for any request,
implying that each node has only one outbound route for the request. Eq. (14)
establishes that the number of reserved entangled pairs between node $i$ and
node $n$ in the reservation phase does not exceed the maximum capacity of
entangled pairs between node $i$ and node $j$ ($C^{\mathrm{etp}}_{i,j}$). Eq.
(14) asserts that the number of utilized entangled pairs between node $i$ and
node $n$ in the utilization phase is not greater than the number of reserved
entangled pairs between node $i$ and node $n$ in the reservation phase. Eq.
(14) states that the numbers of entangled pairs in utilization and on-demand
phases must meet the entanglement fidelity requirement.
$\mathbf{F}^{\mathrm{epg}}(\cdot)$ in Eq. (14) refers to the entanglement
purification algorithm applied to calculate entanglement fidelity based on the
numbers of entangled pairs in utilization and on-demand phases. Eq. (14)
stipulates that the numbers of entangled pairs in utilization and on-demand
phases must satisfy the entanglement fidelity threshold. Finally, Eq. (14)
ensures that the number of entangled pairs used in the on-demand phase does
not surpass the maximum capacity of entangled pairs between node $i$ and node
$j$ ($O^{\mathrm{etp}}_{i,j}$).

$\displaystyle\min_{x_{i,n,r},y^{\mathrm{r}}_{i,n,r},y^{\mathrm{e}}_{i,n,r,\omega},y^{\mathrm{o}}_{i,n,r,\omega}}\sum_{r\in{\mathcal{R}}}\sum_{n\in{\mathcal{M}}}\sum_{i\in{\mathcal{J}}_{n}}$
(5)
$\displaystyle\big{(}(E^{\mathrm{eng}}_{n}+S^{\mathrm{stp}}_{n})x_{i,n,r}y^{\mathrm{r}}_{i,n,r}+R^{\mathrm{r}}_{n,r}y^{\mathrm{r}}_{i,n,r}\big{)}+\sum_{r\in{\mathcal{R}}}$
$\displaystyle\Big{(}\mathbb{P}_{r}(\omega)\sum_{n\in{\mathcal{M}}}\sum_{i\in{\mathcal{J}}_{n}}\big{(}U^{\mathrm{e}}_{n,r}y^{\mathrm{e}}_{i,n,r,\omega}+O^{\mathrm{o}}_{n,r}y^{\mathrm{o}}_{i,n,r,\omega}\big{)}\Big{)}$
s.t.
$\displaystyle\sum_{j^{\prime}\in{\mathcal{Q}}_{S_{r}}}x_{S_{r},j^{\prime},r}-\sum_{i^{\prime}\in{\mathcal{J}}_{S_{r}}}x_{i^{\prime},S_{r},r}=1,r\in{\mathcal{R}},$
(14)
$\displaystyle\sum_{i^{\prime}\in{\mathcal{J}}_{D_{r}}}x_{i^{\prime},D_{r},r}-\sum_{j^{\prime}\in{\mathcal{Q}}_{D_{r}}}x_{D_{r},j^{\prime},r}=1,r\in{\mathcal{R}},$
$\displaystyle\sum_{j^{\prime}\in{\mathcal{Q}}_{n}}x_{n,j^{\prime},r}-\sum_{i^{\prime}\in{\mathcal{J}}_{n}}x_{i^{\prime},n,r}=0,r\in{\mathcal{R}},$
$\displaystyle n\in{\mathcal{M}}\setminus\\{S_{r},D_{r}\\},$
$\displaystyle\sum_{j^{\prime}\in{\mathcal{Q}}_{n}}x_{n,j^{\prime},r}\leq
1,n\in{\mathcal{M}},r\in{\mathcal{R}},$
$\displaystyle\sum_{r\in{\mathcal{R}}}y^{\mathrm{r}}_{i,n,r}x_{i,n,r}\leq
C^{\mathrm{etp}}_{i,j},i,j,n\in{\mathcal{M}},$ $\displaystyle
y^{\mathrm{e}}_{i,n,r,\omega}x_{i,n,r}\leq y^{\mathrm{r}}_{i,n,r}x_{i,n,r},$
$\displaystyle
i,j,n\in{\mathcal{M}},r\in{\mathcal{R}},\forall\omega\in\Omega_{r},$
$\displaystyle\mathbf{F}^{\mathrm{epg}}\big{(}(y^{\mathrm{e}}_{i,n,r,\omega}x_{i,j,r})+y^{\mathrm{o}}_{i,n,r,\omega}\big{)}\geq\omega,$
$\displaystyle i,n\in{\mathcal{M}},r\in{\mathcal{R}},\omega\in\Omega_{r},$
$\displaystyle\mathbf{F}^{\mathrm{epg}}\big{(}(y^{\mathrm{e}}_{i,n,r,\omega}x_{i,j,r})+y^{\mathrm{o}}_{i,n,r,\omega}\big{)}\geq
F^{\mathrm{ths}}_{i,n},$ $\displaystyle
i,n\in{\mathcal{M}},r\in{\mathcal{R}},\omega\in\Omega_{r},$
$\displaystyle\sum_{r\in{\mathcal{R}}}\big{(}y^{\mathrm{o}}_{i,j,r,\omega}x_{i,j,r}\big{)}\leq
O^{\mathrm{etp}}_{i,j},i,j\in{\mathcal{M}},\forall\omega\in\Omega_{r}.$

##  V Performance Evaluation

###  V-A Parameter Setting

We examine the network topology of NSFNET, which is connected using optical
fibers [2] and perform experiments on this topology. For each quantum node in
the topology, we set the fidelity values between nodes $i$ and $j$ as shown in
Fig. 3(a). The fidelity threshold is initially 0.8 [3]. The maximum numbers of
entangled pairs between nodes $i$ and $j$ in the reservation phase
($C^{\mathrm{etp}}_{i,j}$) and the on-demand phase ($O^{\mathrm{etp}}_{i,j}$ )
are initially 10 and 60, respectively. For the SP model, we consider a random
number of requests with fidelity requirements that are uniformly distributed.
We assume the costs of reservation, utilization, and on-demand phases are 10$,
1$, and 200$, respectively. The cost of energy consumption of transferring
traffic of request $r$ through node $n$ ($E^{\mathrm{eng}}_{n}$) is 5$. The
cost of energy consumption to establish repeater $n$ ($S^{\mathrm{stp}}_{n}$)
is 150$. We implement and solve the entangled pair resource allocation and
fidelity-guaranteed entanglement routing via the GAMS/CPLEX solver [19].

###  V-B Numerical Results

(a) Three requests.

(b) The entangled pair utilization.

(c) The optimal solution.

(d) The cost comparison.

Figure 3: (a) Three requests in NSFNET topology, (b) The entangled pair
utilization under different fidelity requirements, (c) The optimal solution
under different numbers of reserved entangled pairs, and (d) The cost
comparison of three models.

####  V-B1 Routing and Entangled Pair Utilization

Figure 3(a) shows the solutions of the SP model that satisfies the fidelity
requirements of three requests (i.e., $f_{1}$, $f_{2}$, and $f_{3}$)
represented by different colors. In the solutions, the SP model not only
allocates the entangled pairs to satisfy fidelity requirements but also
minimizes the number of repeaters (i.e., intermediate quantum nodes) for the
requests in the network. In Fig. 3(a), to obtain the optimal cost, the
entangled pairs are forced to share the same edges and the number of repeaters
is forcibly minimized while supporting all requests. For example, each request
utilizes one entangled pair (i.e., $[1,1,1]$) on the edge between quantum
nodes 4 and 11, which is a direct result of minimizing the number of
repeaters.

Figure 3(b) shows the number of entangled pairs in the reservation,
utilization, and on-demand phases under different fidelity requirements. In
Fig. 3(b), in the reservation and utilization phases, the number of entangled
pairs reserved and then utilized increases steadily until the fidelity
requirement is 0.87. At this point, the numbers of reserved and utilized
entangled pairs reach the maximum capacity of the entangled pairs. As a
result, the numbers of reserved and utilized entangled pairs are stable at 9
entangled pairs, and it cannot support the higher fidelity requirements.
Therefore, to meet the high fidelity requirements, the entangled pairs in the
on-demand phase are utilized. In the on-demand phase, the number of entangled
pairs starts utilizing at 0.88 of the fidelity requirement due to the limited
capacity of the entangled pairs in the reservation phase.

####  V-B2 Cost Structure Analysis

In Fig. 3(c), we assess the SP model’s effectiveness in attaining an optimal
solution. Initially, we modify the number of reserved entangled pairs and
subsequently present the optimal solution derived from the SP model, as well
as the impact of reserved entangled pairs on this solution. In Fig. 3(c), the
first-stage cost notably escalates as the quantity of reserved entangled pairs
expands. In contrast, the second-stage cost markedly diminishes when fidelity
requirements are satisfied. This is a consequence of the reservation phase
(i.e., the first stage) necessitating the maximum number of entangled pairs
due to lower costs, while the on-demand phase (i.e., the second stage) demands
the minimum number of entangled pairs. As a result, with 24 reserved entangled
pairs, the optimal solution is attained at 11,952$, and the second-stage cost
remains at 0. This occurs because the reserved entangled pairs fulfill
fidelity requirements, negating the need for on-demand entangled pairs in the
second stage. Beyond 24 reserved entangled pairs, the total cost and first-
stage cost experience a slight increase due to a penalty cost for surplus
reserved entangled pairs. In Fig. 3(c), we observe that over- and under-
provision of entangled pairs contribute to the overall high total cost.

####  V-B3 Performance Evaluation

We compare the SP model’s performance with two alternative models: the
entangled pair resource allocation (EPRA) over the expected value and the
deterministic equivalent formulation. In the EPRA over the expected value, the
fidelity requirements in the first stage are treated as expected demands. In
the deterministic equivalent formulation, fidelity requirements are considered
as exact demands. In Fig. 3(d), the SP model evidently attains the optimal
solution in comparison to the EPRA over the expected value as the number of
requests increases. For instance, when the request count is 2, the SP model
can reduce the total cost by 53.21% compared to the EPRA over the expected
value. However, the SP model’s solution is inferior to that of the
deterministic equivalent formulation. This difference arises because the
deterministic equivalent formulation employs exact fidelity requirements to
reach the solution, while the SP model relies on statistical information of
fidelity requirements. Nevertheless, the SP model is more pragmatic than the
deterministic equivalent formulation, as determining exact entangled pair
fidelity requirements for input in the deterministic equivalent formulation is
challenging in real-world scenarios.

##  VI Conclusion

In this paper, we have proposed the entangled pair resource allocation and
fidelity-guaranteed entanglement routing model for quantum networks. Using the
two-stage SP framework, we have formulated the model to determine the optimal
cost under fidelity requirement uncertainty. The experimental results have
demonstrated that our proposed model not only achieves optimal total cost and
entanglement routing but also minimizes the number of repeaters (i.e.,
intermediate quantum nodes). Moreover, the model’s performance has surpassed
that of the EPRA over the expected value by a minimum of 20%. In future
research, we plan to investigate and incorporate the energy consumption model
of quantum nodes within quantum networks into the SP model. Additionally, we
aim to develop an entangled pair resource allocation and fidelity-guaranteed
entanglement routing model for space-air-ground integrated networks (SAGIN).

## References

  * [1] C. Li et al., “Effective routing design for remote entanglement generation on quantum networks,” NPJ Quantum Inf., vol. 7, no. 1, pp. 1-12, 2021.
  * [2] Y. Cao et al., “Hybrid Trusted/Untrusted Relay-Based Quantum Key Distribution Over Optical Backbone Networks,” IEEE JSAC, vol. 39, no. 9, pp. 2701-2718, 2021.
  * [3] J. Li et al., “Fidelity-Guaranteed Entanglement Routing in Quantum Networks,” in IEEE Transactions on Communications, vol. 70, no. 10, pp. 6748-6763, 2022.
  * [4] S. Shi and C. Qian, “Concurrent entanglement routing for quantum networks: Model and designs,” in Proc. ACM SIGCOMM Conf., pp. 62–75, 2020.
  * [5] A. S. Cacciapuoti et al., “Quantum Internet: Networking Challenges in Distributed Quantum Computing,” in IEEE Network, vol. 34, no. 1, pp. 137-143, 2020.
  * [6] Q. Jia et al., “An improved QKD protocol without public announcement basis using periodically derived basis,” Quantum Inf. Process, vol. 20, 69 (2021).
  * [7] A. S. Cacciapuoti et al., “When Entanglement Meets Classical Communications: Quantum Teleportation for the Quantum Internet,” in IEEE Transactions on Communications, vol. 68, no. 6, pp. 3808-3833, 2020.
  * [8] K. Chakraborty et al., “Entanglement Distribution in a Quantum Network: A Multicommodity Flow-Based Approach,” in IEEE TQE, vol. 1, pp. 1-21, 2020.
  * [9] Y. Zhao and C. Qiao, “Redundant Entanglement Provisioning and Selection for Throughput Maximization in Quantum Networks,” IEEE INFOCOM 2021, pp. 1-10, 2021.
  * [10] L. Gyongyosi and S. Imre, “Adaptive routing for quantum memory failures in the quantum internet,” Quantum Inf. Process, vol. 18, no. 2, pp. 1–21, 2019.
  * [11] M. Caleffi, “Optimal Routing for Quantum Networks,” IEEE Access, vol. 5, pp. 22299-22312, 2017.
  * [12] F. Hahn, A. Pappa, and J. Eisert, “Quantum network routing and local complementation,” NPJ Quantum Inf., vol. 5, no. 1, pp. 1–7, 2019.
  * [13] J.-G. Ren et al., “Ground-to-satellite quantum teleportation,” Nature, vol. 549, no. 7670, pp. 70–73, 2017.
  * [14] M. Caleffi and A. S. Cacciapuoti, “Quantum Switch for the Quantum Internet: Noiseless Communications Through Noisy Channels,” in IEEE JSAC, vol. 38, no. 3, pp. 575-588, 2020.
  * [15] P. C. Humphreys et al.. ”Deterministic delivery of remote entanglement on a quantum network.” Nature, vol. 558, no. 7709, pp. 268-286, 2018.
  * [16] A. Dahlberg et al., “A link layer protocol for quantum networks,” in Proc. ACM SIGCOMM Conf., pp. 159–173, 2019.
  * [17] X.-M. Hu et al., “Long-distance entanglement purification for quantum communication,” Phys. Rev. Lett., vol. 126, no. 1, 2021.
  * [18] J. R. Birge, and F. Louveaux, “Introduction to Stochastic Programming,” 2nd ed. Springer, 2011.
  * [19] General Algebraic Modeling System (GAMS), https://www.gams.com/, 2022.


# Boundary Adversarial Examples
Against Adversarial Overfitting

Muhammad Zaid Hameed
IBM Research Europe
Dublin, Ireland
<EMAIL_ADDRESS>
&Beat Buesser
IBM Research Europe
Dublin, Ireland
<EMAIL_ADDRESS>

###### Abstract

Standard adversarial training approaches suffer from robust overfitting where
the robust accuracy decreases when models are adversarially trained for too
long. The origin of this problem is still unclear and conflicting explanations
have been reported, i.e., memorization effects induced by large loss data or
because of small loss data and growing differences in loss distribution of
training samples as the adversarial training progresses. Consequently, several
mitigation approaches including early stopping, temporal ensembling and weight
perturbations on small loss data have been proposed to mitigate the effect of
robust overfitting. However, a side effect of these strategies is a larger
reduction in clean accuracy compared to standard adversarial training. In this
paper, we investigate if these mitigation approaches are complimentary to each
other in improving adversarial training performance. We further propose the
use of helper adversarial examples that can be obtained with minimal cost in
the adversarial example generation, and show how they increase the clean
accuracy in the existing approaches without compromising the robust accuracy.

##  1 Introduction

Adversarial examples have gained great attention in ML research [1, 2, 3] and
building models with increased robustness against such examples is still an
open challenge [4, 5, 6, 7, 8, 9, 10, 11]. Adversarial training (AT) [4] is
the most successful approach against adversarial examples where approximate
worst-case adversarial examples are used to train the model.
The success of AT is impeded by high computational costs compared to standard
training and gaps between robust and clean accuracy [4, 5, 12, 13]. It has
been shown that AT reduces the clean accuracy [5] and mitigation techniques
based on label smoothing and stochastic weight averaging [11] or use of
additional unlabeled data [14] have been proposed, which solve the problem
only partially.
Recently, another phenomenon associated with adversarial training has been
discovered and coined robust overfitting [15, 11, 16, 17], which occurs when
models are adversarially trained for too long. Especially after the first
learning rate decay, the robust accuracy tends to decrease with additional
training. Even though overfitting to training data results in increased clean
accuracy, the robust accuracy is negatively impacted by this additional
training. The exact causes of robust overfitting are still unclear and most
explanations are conflicting. For example, memorization effects induced by
large loss data, which give rise to high confidence predictions, have been
shown to be a driving force behind robust overfitting [16]. On the other hand,
small loss data and large differences in loss distribution across training
samples, tend to amplify as AT progresses, and have been shown to enhance
robust overfitting [17]. Reported mitigation approaches like temporal
ensembling (TE) [16] and model weight perturbation (WP) [17] alleviate robust
overfitting, but tend to trade off more clean accuracy when compared to
standard adversarial training (AT) [4]. This shows that increased
regularization induced by these schemes negatively impact the generalization
performance on clean data.
Here, we analyze how these two seemingly conflicting approaches, TE and WP,
which attribute robust overfitting to training with samples with large and
small loss data, respectively, mitigate robust overfitting and if they can be
combined to create a compounding mitigation effect. First, we investigate how
TE and WP behave during AT and find that they induce different types of
regularization on adversarial examples during overfitting. Second, we evaluate
a combination of TE and WP and find that there is no compounding improvement
in robust accuracy. Third, we minimize loss on clean input data along-with
these robust overfitting mitigation approaches which results in increased
clean accuracy at the expense of robust accuracy. Thus, we find that the
negative impacts on clean accuracy induced by TE and WP can be prevented
without affecting the robust accuracy with appropriate regularization.
We propose to employ TE/WP based robust overfitting mitigation with the
additional use of helper adversarial examples along-with a TE-based
regularization term and demonstrate improvement in clean accuracy over the
existing AT approaches. The helper examples can be created during the
adversarial example generation in AT with a minimal computational overhead of
just one extra forward pass. Our idea is to use perturbed samples close to
decision boundaries as helper examples with their property of increasing clean
accuracy with only a small degradation in robust accuracy compared to using
clean data only.

##  2 Preliminaries

Adversarial training (AT) has empirically proved to be the most effective
defense strategy against adversarial evasion attacks [4, 5, 6, 10, 11]. In the
following we will briefly describe the mechanics of AT [4] and two robust
mitigation schemes [16, 17].

###  2.1 Adversarial Training (AT) [4]

We consider a classification problem where an input sample
$\mathbf{x}\in\mathbb{R}^{n}$ belongs to a true class $y$ among a set of
classes $\mathcal{Y}=\\{1,2,\ldots,Y\\}$. A DNN-based classifier
$F_{\boldsymbol{\theta}}:\mathbb{R}^{n}\times\mathcal{Y}\to\mathbb{R}$,
assigns a label
$\hat{y}\in\operatorname*{arg\,max}_{y\in\mathcal{Y}}F_{\boldsymbol{\theta}}(\mathbf{x},y)$
to $\mathbf{x}$, where ${\boldsymbol{\theta}}\in\Theta$ denotes the parameters
of DNN. With a slight abuse of notation, we also use $F$ to denote the
classifier, $F(\mathbf{x})$ to denote the class label assigned to
$\mathbf{x}$, and $F(\mathbf{x},y)$ to denote the score of class $y$ for input
$\mathbf{x}$ and $p(\mathbf{x})$ denotes the DNN prediction probability
vector. For a correctly classified input $\mathbf{x}$ i.e., $y=F(\mathbf{x})$
is the true label, an adversarial attack aims to find a sample
$\tilde{\mathbf{x}}$ in the $\epsilon$-neighborhood of $\mathbf{x}$ in norm
$p$ denoted by
$\mathcal{B}_{\epsilon}(\mathbf{x})=\left\\{\tilde{\mathbf{x}}:\|\tilde{\mathbf{x}}-\mathbf{x}\|_{p}\leq\epsilon\right\\}$,
such that $F(\tilde{\mathbf{x}})\neq F(\mathbf{x})$. In practice, these
adversarial examples are generated by modifying the input $\mathbf{x}$ through
optimizing a loss function $\mathcal{L}$ on the classifier [3, 18, 19, 20, 4].
Finally, AT can be considered as a robust optimization problem:

$\min_{\boldsymbol{\theta}}\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\mathcal{L}(F(\tilde{\mathbf{x}},y),y),$
(1)

where $\tilde{\mathbf{x}}$ is the adversarial example. Hence, during training,
adversarial attacks first generate adversarial examples in the neighborhood
$\mathcal{B}_{\epsilon}(\mathbf{x})$ of input $\mathbf{x}$ to approximately
maximize the loss $\mathcal{L}$ (e.g., cross-entropy loss), followed by
training on the examples to update the network parameters and achieving
robustness against adversarial examples.

###  2.2 Adversarial Training with Temporal Ensembling (AT-TE) [16]

Robust overfitting is attributed to neural networks training on high loss
input data and over-confident predictions (memorization) by the model during
AT [11, 16]. To prevent this, a regularization based on temporal ensembling
(TE) has been proposed in [16] which penalizes over-confident predictions. Let
$z(\mathbf{x})$ denote the ensemble prediction by a model on input
$\mathbf{x}$ which is updated as $z(\mathbf{x})=\eta\cdot
z(\mathbf{x})+(1-\eta)\cdot p(\mathbf{x})$ in each epoch and the AT objective
becomes

$\min_{\boldsymbol{\theta}}\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\\{\mathcal{L}(F(\tilde{\mathbf{x}},y),y)+w\cdot\|p(\tilde{\mathbf{x}})-\hat{z}(\mathbf{x})\|_{2}^{2}\\},$
(2)

where $\hat{z}(\mathbf{x})$ is obtained by normalizing $z(\mathbf{x})$ and $w$
is regularization weight. In this AT,

the regularization term is activated close to the first learning rate decay,
and prevents the network from assigning high confidence to samples with large
loss.

###  2.3 Minimum Loss Constrained Adversarial Training (MLCAT-WP) [17]

Training samples with small loss and large differences in loss distribution
among samples are shown to cause robust overfitting in [17] and adversarial
weight perturbation [9] is employed to increase the loss on such samples,
which helps to mitigate robust overfitting. The training objective becomes

$\min_{\boldsymbol{\theta}}\max_{\mathbf{v}\in\mathcal{V}}\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\mathcal{L}(F_{\theta+v}(\tilde{\mathbf{x}},y),y),$
(3)

where $v\in\mathcal{V}$ is an adversarial weight perturbation and is generated
by $\max_{\mathbf{v}\in\mathcal{V}}\sum_{i}\mathbbm{1}_{\\{\mathcal{L}_{i}\leq
L_{min}\\}}\cdot\mathcal{L}_{i},$ where
$\mathcal{L}_{i}=\mathcal{L}(F_{\theta+v}(\tilde{\mathbf{x}_{i}},y_{i}),y_{i})$,
$L_{min}$ is threshold for minimum adversarial loss and $\mathbbm{1}_{c}$ is
an indicator function which is 1 only when condition $c$ is true.

##  3 Comparison of AT, AT-TE and MLCAT-WP

In order to investigate how standard AT and robust overfitting mitigation
approaches AT-TE and MLCAT-WP behave as training progresses, we consider image
classification on CIFAR-10 [21] with a ResNet-18 model [22]. For all
approaches, we use a Projected Gradient Descent ($\mathrm{PGD}$) attack [4]
for 10 steps denoted by $\mathrm{{PGD}_{10}}$ in training and
$\mathrm{{PGD}_{20}}$ for evaluation; see Appendix A for full details. We
observe from Figure 1(b)-(d) that as the training progresses, an AT model
starts to classify training data with high true class probability (TCP)
(Average TCP $\geq 0.5$) after the first learning rate decay at epoch 100 and
proportion of training samples with very small loss value (in range [0, 0.5))
and high TCP also grows ($\geq 40\%$ of all training samples). On the other
hand, an MLCAT-WP trained model’s average TCP on training data increases
gradually and stays small ($\approx 0.4$) at epoch 200 and the proportion of
samples in the loss range [0, 0.5) amounts to only 20% of all training data
which shows weight perturbation prevents the model from assigning very high
TCP to training data and fitting samples with small loss. In case of AT-TE the
average TCP for samples with loss in range [0, 0.5) starts to decrease when
temporal ensembling is activated (epoch $\geq 90$) and even though the
proportion of samples increase, it lies between AT and MLCAT-WP. Finally, we
can also make this observation from Figure 1(a) that combining weight
perturbation and temporal ensembling (MLCAT-WP+TE) does not result in any
improvement in robust accuracy and its behavior closely resembles MLCAT-WP.
Moreover, modifying AT-TE and MLCAT-WP to AT-TE+XEC and MLCAT-WP+XEC by
including cross entropy loss on clean data results in higher clean accuracy at
the cost of reduced robust accuracy and results in increase in TCP and
proportions of samples with small loss.

(a)

(b)

(c)

(d)

Figure 1: CIFAR-10 training for ResNet-18. (a) Test accuracy against clean
data (dark solid lines) and $\mathrm{{PGD}_{20}}$ attack (dim solid lines) are
plotted.

##  4 Boundary Adversarial Examples for Improving Adversarial Training

To counter the negative effect of regularization in AT-TE and MLCAT-WP on
clean accuracy and negative effect of using clean sample on robust accuracy,
we propose to extract additional useful information from the adversarial
examples generation process in adversarial training. More specifically, we
extract intermediate adversarial examples that are close to a decision
boundary as soon as the perturbed sample is misclassified. Our underlying idea
is that using boundary (intermediate and weak) adversarial examples in place
of clean samples will guide the network to attain better clean accuracy
without affecting robust accuracy too much. Thus, using this intermediate
perturbed sample $\mathbf{x}^{\prime}\in\mathcal{B}_{\epsilon}(\mathbf{x})$
and a regularization based on its prediction $p(\mathbf{x}^{\prime})$ and
ensemble prediction $z(\mathbf{x}^{\prime})$, the AT-TE objective becomes

$\min_{\boldsymbol{\theta}}\\{\mathcal{L}(F(\mathbf{x}^{\prime},y),y)+w\cdot\|p(\mathbf{x}^{\prime})-\hat{z}(\mathbf{x}^{\prime})\|_{2}^{2}\
+\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\\{\mathcal{L}(F(\tilde{\mathbf{x}},y),y)+w\cdot\|p(\tilde{\mathbf{x}})-\hat{z}(\mathbf{x})\|_{2}^{2}\\}\\},$
(4)

where $\hat{z}(\mathbf{x}^{\prime})$ is normalized $z(\mathbf{x}^{\prime})$,
and $z(\mathbf{x}^{\prime})$ is updated as $z(\mathbf{x}^{\prime})=\eta\cdot
z(\mathbf{x}^{\prime})+(1-\eta)\cdot p(\mathbf{x}^{\prime})$ in each epoch. We
denote this modified AT-TE as AT-TEBS. Similarly, MLCAT-WP objective becomes
MLCAT-WP+TEBS by including TE and boundary sample as

$\min_{\boldsymbol{\theta}}\\{\mathcal{L}(F_{\theta+v}(\mathbf{x}^{\prime},y),y)+w\cdot\|p(\mathbf{x}^{\prime})-\hat{z}(\mathbf{x}^{\prime})\|_{2}^{2}\
+\
\max_{\mathbf{v}\in\mathcal{V}}\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\\{\mathcal{L}(F_{\theta+v}(\tilde{\mathbf{x}},y),y)+w\cdot\|p(\tilde{\mathbf{x}})-\hat{z}(\mathbf{x})\|_{2}^{2}\\}\\}$
(5)

##  5 Experimental Evaluation

We train a ResNet-18 model using AT, AT-TE, MLCAT-WP, MLCAT-WP+TE, AT-TEBS and
MLCAT-WP+TEBS for CIFAR-10 [21], CIFAR-100 [21] and SVHN [23]; see Appendix A
for details. We use $\mathrm{{PGD}_{10}}$ attack ($\epsilon=8/255$,
$L_{\infty}$ norm) during training and $\mathrm{{PGD}_{20}}$ at inference. In
addition, we also run AutoAttack (AA) [24] which is an ensemble of different
attacks for a more reliable evaluation. Table 1 shows that both AT-TEBS and
MLCAT-WP+TEBS attain significant increase in clean accuracy over their
counterparts AT-TE and MLCAT-WP/MLCAT-WP+TE ($\approx$2%-3% in CIFAR-10, 2%-5%
in CIFAR-100, and 1%-2% in SVHN). AT-TE and AT-TEBS do not prevent overfitting
in the SVHN dataset because the training data fits very early in training with
high confidence, whereas temporal ensembling activates closer to first
learning rate decay and thus, regularization based on ensemble prediction is
ineffective. On the other hand, weight perturbation based approaches MLCAT-WP
and MLCAT-WP+TEBS result in superior performance across all datasets compared
to AT-TE and AT-TEBS in terms of clean and robust accuracy; and use of
adversarial boundary examples significantly boosts the clean accuracy
especially for CIFAR-100 and SVHN datasets in MLCAT-WP+TEBS. From Figure 2, we
observe that for all three datasets, AT-TEBS and MLCAT-WP+TEBSapproximately
retain the robust accuracy of AT-TE and MLCAT-WP, but increase the clean
accuracy to match and even surpass AT in case of the CIFAR-100 and SVHN
datasets.

(a)

(b)

(c)

Figure 2: Accuracy results for AT using ResNet-18. Clean test accuracy (dark
solid lines) and $\mathrm{{PGD}_{20}}$ attack test accuracy (dim solid lines)
are plotted. Table 1: Test accuracy (mean and standard deviation of 5 runs).
“Last" and “Best" refer to test accuracy at the end of training, and end of
epoch that gives the highest accuracy w.r.t. test data respectively.

Dataset | Name | Clean(Best) | Clean(Last) | Robust(Best) | Robust(Last) | AA(Best) | AA(Last)
---|---|---|---|---|---|---|---
CIFAR-10 | AT | 82.03$\pm 0.42$ | 84.37$\pm$0.30 | 52.64$\pm$0.13 | 45.06$\pm$0.70 | 48.04$\pm$0.15 | 42.64$\pm$0.62
AT-TE | 82.11$\pm$0.14 | 82.73$\pm$0.22 | 55.69$\pm$0.11 | 54.15$\pm$0.42 | 49.99$\pm$0.16 | 48.95$\pm$0.37
MLCAT-WP | 82.05$\pm$0.31 | 81.78 $\pm$0.26 | 58.16$\pm$0.13 | 57.46$\pm$0.45 | 50.43$\pm$0.07 | 49.96$\pm$0.31
MLCAT-WP+TE | 81.06$\pm$0.49 | 80.74$\pm$0.24 | 58.48$\pm$0.08 | 57.71$\pm$0.22 | 50.67$\pm$0.10 | 50.46$\pm$0.20
AT-TEBS | 83.99$\pm$0.14 | 84.46$\pm$0.36 | 55.26$\pm$0.07 | 53.58$\pm$0.74 | 50.17$\pm$0.09 | 48.80$\pm$0.70
MLCAT-WP+TEBS | 83.712$\pm$0.51 | 83.75$\pm$0.41 | 59.20$\pm$0.21 | 58.53$\pm$0.52 | 50.38$\pm$0.07 | 50.30$\pm$0.26
CIFAR-100 | AT | 55.49$\pm$0.60 | 56.93$\pm$0.15 | 29.50$\pm$0.22 | 22.11$\pm$0.25 | 25.05$\pm$0.44 | 19.97$\pm$0.19
AT-TE | 56.43$\pm$0.25 | 56.94$\pm$0.44 | 32.07$\pm$0.06 | 30.67$\pm$0.18 | 26.19$\pm$0.18 | 25.1$\pm$0.09
MLCAT-WP | 57.65$\pm$0.41 | 57.96$\pm$0.30 | 32.73$\pm$0.11 | 31.68$\pm$0.61 | 27.14$\pm$0.14 | 26.48$\pm$0.41
MLCAT-WP+TE | 56.60$\pm$0.56 | 57.44$\pm$0.33 | 33.02$\pm$0.16 | 32.02$\pm$0.56 | 27.08$\pm$0.16 | 26.58$\pm$0.54
AT-TEBS | 58.78$\pm$0.23 | 58.82$\pm$0.29 | 31.59$\pm$0.09 | 30.40$\pm$0.16 | 25.99$\pm$0.18 | 24.98$\pm$0.23
MLCAT-WP+TEBS | 62.50$\pm$0.28 | 62.45$\pm$0.42 | 31.95$\pm$0.06 | 30.72$\pm$0.65 | 26.57$\pm$0.14 | 25.74$\pm$0.48
SVHN | AT | 89.08$\pm$0.47 | 89.91$\pm$0.30 | 53.21$\pm$0.32 | 44.70$\pm$0.60 | 45.59$\pm$0.61 | 39.97$\pm$0.63
AT-TE | 89.17$\pm$0.58 | 89.83$\pm$0.34 | 53.21$\pm$0.18 | 44.24$\pm$0.71 | 45.81$\pm$0.43 | 39.65$\pm$0.81
MLCAT-WP | 91.45$\pm$0.26 | 91.91$\pm$0.21 | 60.25$\pm$0.28 | 56.98$\pm$0.62 | 51.60$\pm$0.37 | 49.20$\pm$0.30
MLCAT-WP+TE | 91.53$\pm$0.46 | 91.67$\pm$0.30 | 60.33$\pm$0.30 | 57.71$\pm$ 0.84 | 51.57$\pm$0.31 | 49.89$\pm$0.54
AT-TEBS | 91.58$\pm$0.32 | 90.43$\pm$0.46 | 50.94$\pm$0.16 | 44.43$\pm$0.66 | 45.37$\pm$0.29 | 39.43$\pm$0.70
MLCAT-WP+TEBS | 92.43$\pm$0.46 | 92.53$\pm$0.35 | 60.07$\pm$0.31 | 57.61$\pm$ 0.94 | 51.27$\pm$0.49 | 49.42$\pm$0.54

##  6 Conclusion

We investigate temporal ensembling and weight perturbation for mitigating
robust overfitting and discover that temporal ensembling mainly influences
high confidence predictions whereas weight perturbation affects both
confidence in predictions and small loss data samples. Overall, adversarial
weight perturbation, which directly prevents the model from fitting low loss
data samples, achieves better clean and robust accuracy compared to temporal
ensembling. Furthermore, we propose to use samples close to decision boundary
for improving clean accuracy. These can be directly obtained from the
adversarial examples generation process during adversarial training with
minimal additional cost. Together with ensemble prediction regularization,
this helps in retaining the robust accuracy of both robust overfitting
mitigation approaches but significantly increases the clean accuracy.

## References

  * [1] J. Bruna, C. Szegedy, I. Sutskever, I. Goodfellow, W. Zaremba, R. Fergus, and D. Erhan, “Intriguing properties of neural networks,” in International Conference on Learning Representations, 2014.
  * [2] I. J. Goodfellow, J. Shlens, and C. Szegedy, “Explaining and harnessing adversarial examples,” in International Conference on Learning Representations, 2015.
  * [3] N. Carlini and D. Wagner, “Towards evaluating the robustness of neural networks,” in 2017 IEEE Symposium on Security and Privacy (SP), pp. 39–57, IEEE, 2017.
  * [4] A. Madry, A. Makelov, L. Schmidt, D. Tsipras, and A. Vladu, “Towards deep learning models resistant to adversarial attacks,” in International Conference on Learning Representations, 2018.
  * [5] H. Zhang, Y. Yu, J. Jiao, E. Xing, L. El Ghaoui, and M. Jordan, “Theoretically principled trade-off between robustness and accuracy,” in International Conference on Machine Learning, pp. 7472–7482, 2019.
  * [6] A. Shafahi, M. Najibi, M. A. Ghiasi, Z. Xu, J. Dickerson, C. Studer, L. S. Davis, G. Taylor, and T. Goldstein, “Adversarial training for free!,” in Advances in Neural Information Processing Systems, pp. 3353–3364, 2019\.
  * [7] C. Qin, J. Martens, S. Gowal, D. Krishnan, K. Dvijotham, A. Fawzi, S. De, R. Stanforth, and P. Kohli, “Adversarial robustness through local linearization,” in Advances in Neural Information Processing Systems (H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, eds.), vol. 32, Curran Associates, Inc., 2019.
  * [8] V. Sehwag, S. Wang, P. Mittal, and S. Jana, “Hydra: Pruning adversarially robust neural networks,” in Advances in Neural Information Processing Systems (H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, eds.), vol. 33, pp. 19655–19666, Curran Associates, Inc., 2020.
  * [9] D. Wu, S.-T. Xia, and Y. Wang, “Adversarial weight perturbation helps robust generalization,” Advances in Neural Information Processing Systems, vol. 33, 2020.
  * [10] S. Gowal, C. Qin, J. Uesato, T. Mann, and P. Kohli, “Uncovering the limits of adversarial training against norm-bounded adversarial examples,” arXiv preprint arXiv:2010.03593, 2020.
  * [11] T. Chen, Z. Zhang, S. Liu, S. Chang, and Z. Wang, “Robust overfitting may be mitigated by properly learned smoothening,” in International Conference on Learning Representations, vol. 1, 2021.
  * [12] D. Tsipras, S. Santurkar, L. Engstrom, A. Turner, and A. Madry, “Robustness may be at odds with accuracy,” in International Conference on Learning Representations, 2019.
  * [13] Y.-Y. Yang, C. Rashtchian, H. Zhang, R. Salakhutdinov, and K. Chaudhuri, “A closer look at accuracy vs. robustness,” Advances in Neural Information Processing Systems, vol. 33, 2020.
  * [14] Y. Carmon, A. Raghunathan, L. Schmidt, J. C. Duchi, and P. S. Liang, “Unlabeled data improves adversarial robustness,” in Advances in Neural Information Processing Systems, pp. 11190–11201, 2019.
  * [15] L. Rice, E. Wong, and Z. Kolter, “Overfitting in adversarially robust deep learning,” in International Conference on Machine Learning, pp. 8093–8104, PMLR, 2020.
  * [16] Y. Dong, K. Xu, X. Yang, T. Pang, Z. Deng, H. Su, and J. Zhu, “Exploring memorization in adversarial training,” in International Conference on Learning Representations, 2022.
  * [17] C. Yu, B. Han, L. Shen, J. Yu, C. Gong, M. Gong, and T. Liu, “Understanding robust overfitting of adversarial training and beyond,” in International Conference on Machine Learning, pp. 25595–25610, PMLR, 2022.
  * [18] S.-M. Moosavi-Dezfooli, A. Fawzi, and P. Frossard, “Deepfool: a simple and accurate method to fool deep neural networks,” in Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 2574–2582, 2016\.
  * [19] P.-Y. Chen, Y. Sharma, H. Zhang, J. Yi, and C.-J. Hsieh, “Ead: elastic-net attacks to deep neural networks via adversarial examples,” in Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
  * [20] C. Laidlaw and S. Feizi, “Functional adversarial attacks,” in NeurIPS, 2019\.
  * [21] A. Krizhevsky, “Learning multiple layers of features from tiny images,” tech. rep., University of Toronto, 2009.
  * [22] K. He, X. Zhang, S. Ren, and J. Sun, “Deep residual learning for image recognition,” in Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 770–778, 2016.
  * [23] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and A. Y. Ng, “Reading digits in natural images with unsupervised feature learning,” 2011.
  * [24] F. Croce and M. Hein, “Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks,” in International conference on machine learning, pp. 2206–2216, PMLR, 2020.

##  Appendix A Experimental Setup

For all experiments, we use ResNet-18 models [22] which are trained using SGD
with momentum value of 0.9 and weight decay of 5 × $10^{-4}$. Initial learning
rate is set to 0.1 for CIFAR-10 and CIFAR-100 datasets and 0.01 for SVHN
dataset, which is divided by 10 at the $100^{th}$ and $150^{th}$ epochs with a
total training of 200 epochs. Data augmentation consisting of horizontal flip
and random crop is used for CIFAR-10 and CIFAR-100 datasets, while no data
augmentation is used for SVHN datatset.

For $\mathrm{PGD}$ attack parameters for training, we set the
$\epsilon=\frac{8}{255}$ in $L_{\infty}$ norm (maximum perturbation) and 10
attack steps for all datasets where step size of $\frac{2}{255}$ is used for
CIFAR-10 and CIFAR-100 datatsets and step size of $\frac{1}{255}$ for SVHN.
For evaluation we consider $\mathrm{PGD}$ attack with 20 steps with
$\epsilon=\frac{8}{255}$ in $L_{\infty}$ norm and step size of $\frac{2}{255}$
for all datasets.

For temporal ensembling based approaches, the value of temporal ensembling
weight parameter $w$ is adjusted experimentally and is set to 300 in AT-TE,
AT-TEBS and AT-TECS for CIFAR-10 and SVHN datasets and 3000 for CIFAR-100
datatset along a Gaussian ramp-up curve [16]. Similarly, for MLCAT-WP+TE,
MLCAT-WP+TEBS and MLCAT-WP+TECS $w=30$ is used in training with CIFAR-10 and
SVHN datasets and $w=300$ is used for CIFAR-100 dataset along a Gaussian ramp-
up curve. The momentum term $\eta$ in ensemble prediction update is set to 0.9
and temporal ensembling activates at $90^{th}$ epoch [16] for all experiments
involving temporal ensembling. For all experiments with MLCAT-WP, MLCAT-WP+TE,
MLCAT-WP+TEBS and MLCAT-WP+TECS, $L_{min}=1.5$ for CIFAR-10 and SVHN datasets
and $L_{min}=4.0$ for CIFAR-100 dataset and other parameters are set as per
the original work [17].

Furthermore all experiments are run on a single NVIDIA A100 Tensor Core GPU
using PyTorch version 1.11.0 on Red Hat Enterprise Linux release 8.5 operating
system.

##  Appendix B Additional Results for CIFAR-10, CIFAR-100 and SVHN Datasets

This section contains additional results for CIFAR-10, CIFAR-100 and SVHN
datasets. We consider the case when instead of boundary sample
$\mathbf{x}^{\prime}$ we use clean input sample $\mathbf{x}$ and a
regularization on network’s current prediction on this clean sample
$p(\mathbf{x})$ and ensemble prediction $z(\mathbf{x})$. Thus AT-TEBS modifies
to

$\min_{\boldsymbol{\theta}}\\{\mathcal{L}(F(\mathbf{x},y),y)+w\cdot\|p(\mathbf{x})-\hat{z}(\mathbf{x})\|_{2}^{2}\
+\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\\{\mathcal{L}(F(\tilde{\mathbf{x}},y),y)+w\cdot\|p(\tilde{\mathbf{x}})-\hat{z}(\mathbf{x})\|_{2}^{2}\\}\\}$
(6)

which we denote as AT-TECS. Similarly, MLCAT-WP+TEBS objective becomes MLCAT-
WP+TECS by including TE and clean input sample as

$\min_{\boldsymbol{\theta}}\\{\mathcal{L}(F_{\theta+v}(\mathbf{x},y),y)+w\cdot\|p(\mathbf{x})-\hat{z}(\mathbf{x})\|_{2}^{2}\
+\
\max_{\mathbf{v}\in\mathcal{V}}\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\\{\mathcal{L}(F_{\theta+v}(\tilde{\mathbf{x}},y),y)+w\cdot\|p(\tilde{\mathbf{x}})-\hat{z}(\mathbf{x})\|_{2}^{2}\\}\\}$
(7)

We also consider the case when MLCAT-WP objective is modified to include cross
entropy loss on boundary sample $\mathbf{x}^{\prime}$ but no temporal
ensembling is employed. We denote this scheme as MLCAT-WP+XEBS which is given
by

$\min_{\boldsymbol{\theta}}\\{\mathcal{L}(F_{\theta+v}(\mathbf{x}^{\prime},y),y)\
+\
\max_{\mathbf{v}\in\mathcal{V}}\max_{\tilde{\mathbf{x}}\in\mathcal{B}_{\epsilon}(\mathbf{x})}\\{\mathcal{L}(F_{\theta+v}(\tilde{\mathbf{x}},y),y)\\}\\}$
(8)

Table 2 shows the inherent trade off between robust accuracy and clean
accuracy when clean input sample is used in place of boundary sample.
Adversarial weight perturbation based approaches MLCAT-WP+TEBS and MLCAT-
WP+TECS seem to be more sensitive to the choice of sample as boundary sample
clearly leads to significantly higher robust accuracy whereas clean input
sample leads to significantly higher clean accuracy. In addition, robust
overfitting occurs more severely for MLCAT-WP+TECS compared to MLCAT-WP+TEBS.
MLCAT-WP+XEBS that does not employ temporal ensembling attains clean and
robust accuracy that lie in between MLCAT-WP+TEBS and MLCAT-WP+TECS. On the
other hand, AT-TECS with clean input sample has increased clean accuracy and
comparable robust accuracy to AT-TEBS for CIFAR-10 and CIFAR-100 datasets.
Both AT-TEBS and AT-TECS suffer from robust overfitting for SVHN dataset
training and the reason is that the networks learn data in few epochs and
start to assign high confidence predictions to input samples as shown in
Figure 5(b). Since regularization based on network current prediction and
ensemble prediction activates at a later stage close to first learning rate
decay at epoch 100, it becomes ineffective as the ensemble prediction is also
very high similar to current prediction. Figure 3-Figure 5 show how accuracy,
average TCP and proportion of small loss samples evolve with time for
CIFAR-10, CIFAR-100 and SVHN datasets, respectively.

Table 2: Test accuracy (mean and standard deviation of 5 runs). “Last" and
“Best" refer to test accuracy at the end of training, and end of epoch that
gives the highest accuracy w.r.t. test data respectively.

Dataset | Name | Clean(Best) | Clean(Last) | Robust(Best) | Robust(Last) | AA(Best) | AA(Last)
---|---|---|---|---|---|---|---
CIFAR-10 | AT-TEBS | 83.99$\pm$0.14 | 84.46$\pm$0.36 | 55.26$\pm$0.07 | 53.58$\pm$0.74 | 50.17$\pm$0.09 | 48.80$\pm$0.70
AT-TECS | 85.62$\pm$0.23 | 85.76$\pm$0.18 | 54.83$\pm$0.23 | 53.21$\pm$0.91 | 50.09$\pm$0.21 | 48.81$\pm$0.61
MLCAT-WP+TEBS | 83.712$\pm$0.51 | 83.75$\pm$0.41 | 59.20$\pm$0.21 | 58.53$\pm$0.52 | 50.38$\pm$0.07 | 50.30$\pm$0.26
MLCAT-WP+TECS | 86.17$\pm$0.37 | 88.47$\pm$0.67 | 55.37$\pm$0.28 | 51.68$\pm$1.18 | 48.13$\pm$0.40 | 46.84$\pm$0.23
MLCAT-WP+XEBS | 84.81$\pm$0.3 | 84.91$\pm$0.33 | 58.76$\pm$0.16 | 57.8$\pm$0.61 | 50.09$\pm$0.09 | 49.75$\pm$0.32
CIFAR-100 | AT-TEBS | 58.78$\pm$0.23 | 58.82$\pm$0.29 | 31.59$\pm$0.09 | 30.40$\pm$0.16 | 25.99$\pm$0.18 | 24.98$\pm$0.23
AT-TECS | 60.71$\pm$0.37 | 60.52$\pm$0.41 | 31.08$\pm$0.22 | 29.72$\pm$0.19 | 25.72$\pm$0.23 | 24.77$\pm$0.15
MLCAT-WP+TEBS | 62.50$\pm$0.28 | 62.45$\pm$0.42 | 31.95$\pm$0.06 | 30.72$\pm$0.65 | 26.57$\pm$0.14 | 25.74$\pm$0.48
MLCAT-WP+TECS | 66.38$\pm$0.82 | 67.25$\pm$0.38 | 28.87$\pm$0.25 | 26.96$\pm$0.53 | 24.00$\pm$0.26 | 22.59$\pm$0.62
MLCAT-WP+XEBS | 62.67$\pm$0.3 | 63.1$\pm$0.37 | 31.19$\pm$0.15 | 29.95$\pm$0.51 | 26.29$\pm$0.14 | 25.46$\pm$0.49
SVHN | AT-TEBS | 91.58$\pm$0.32 | 90.43$\pm$0.46 | 50.94$\pm$0.16 | 44.43$\pm$0.66 | 45.37$\pm$0.29 | 39.43$\pm$0.70
AT-TECS | 91.75$\pm$0.69 | 90.24$\pm$0.43 | 48.72$\pm$0.45 | 43.02$\pm$0.79 | 42.42$\pm$0.27 | 38.22$\pm$0.68
MLCAT-WP+TEBS | 92.43$\pm$0.46 | 92.53$\pm$0.35 | 60.07$\pm$0.31 | 57.61$\pm$ 0.94 | 51.27$\pm$0.49 | 49.42$\pm$0.54
MLCAT-WP+TECS | 93.18$\pm$0.69 | 93.57$\pm$0.41 | 56.22$\pm$1.17 | 52.05$\pm$ 1.78 | 48.71$\pm$1.02 | 45.19$\pm$1.01
MLCAT-WP+XEBS | 92.47$\pm$0.44 | 93.4$\pm$0.82 | 59.78$\pm$0.04 | 55.21$\pm$ 1.2 | 51.29$\pm$0.24 | 46.73$\pm$1.81

(a)

(b)

(c)

(d)

Figure 3: CIFAR-10 training for ResNet-18. (a) Test accuracy against clean
data (dark solid lines) and $\mathrm{{PGD}_{20}}$ attack (dim solid lines) are
plotted.

(a)

(b)

(c)

(d)

Figure 4: CIFAR-100 training for ResNet-18. (a) Test accuracy against clean
data (dark solid lines) and $\mathrm{{PGD}_{20}}$ attack (dim solid lines) are
plotted.

(a)

(b)

(c)

(d)

Figure 5: SVHN training for ResNet-18. (a) Test accuracy against clean data
(dark solid lines) and $\mathrm{{PGD}_{20}}$ attack (dim solid lines) are
plotted.