# Multi-objective Evolutionary Search of Variable-length Composite Semantic
Perturbations

Jialiang Sun  Wen Yao<EMAIL_ADDRESS>Tingsong Jiang<EMAIL_ADDRESS>Xiaoqian Chen  Defense Innovation Institute, Chinese Academy of Military
Science, Beijing, 100071, China

###### Abstract

Deep neural networks have proven to be vulnerable to adversarial attacks in
the form of adding specific perturbations on images to make wrong outputs.
Designing stronger adversarial attack methods can help more reliably evaluate
the robustness of DNN models. To release the harbor burden and improve the
attack performance, auto machine learning (AutoML) has recently emerged as one
successful technique to help automatically find the near-optimal adversarial
attack strategy. However, existing works about AutoML for adversarial attacks
only focus on $L_{\infty}$-norm-based perturbations. In fact, semantic
perturbations attract increasing attention due to their naturalnesses and
physical realizability. To bridge the gap between AutoML and semantic
adversarial attacks, we propose a novel method called multi-objective
evolutionary search of variable-length composite semantic perturbations (MES-
VCSP). Specifically, we construct the mathematical model of variable-length
composite semantic perturbations, which provides five gradient-based semantic
attack methods. The same type of perturbation in an attack sequence is allowed
to be performed multiple times. Besides, we introduce the multi-objective
evolutionary search consisting of NSGA-II and neighborhood search to find
near-optimal variable-length attack sequences. Experimental results on CIFAR10
and ImageNet datasets show that compared with existing methods, MES-VCSP can
obtain adversarial examples with a higher attack success rate, more
naturalness, and less time cost.

###### keywords:

Composite semantic perturbations , Adversarial attack , Multi-objective
optimization , Robustness

††journal: Journal of Elsevier

##  1 Introduction

Deep Neural Network (DNN) models have achieved great success in the majority
of computer vision tasks [1, 2]. However, DNN proved to be vulnerable to
specific perturbations, which can make models output wrong results [3, 4]. The
images with the perturbations are called adversarial examples (AEs). The
phenomenon of AEs brings huge threats to real-world applications such as auto-
driving and face recognition systems.

Focusing on the study of AEs, many works have been developed in the
adversarial attack community. Developing stronger attack methods can approach
the lower bound of the accuracy of DNN models, which can more reliably
evaluate the model’s robustness [5]. The goal of adversarial attacks is to
generate specific perturbations to fool DNN models. According to the magnitude
of the perturbations, existing adversarial attacks can be divided into $L_{p}$
norm-based like projection gradient descent (PGD) [4, 6, 7] and unrestricted-
based [8, 9, 10, 11]. The former requires that the $L_{p}$ norm of
perturbations that are added on original images (also called clean images) can
not exceed a certain threshold. The latter does not limit the magnitude but
needs to ensure that the semantics of clean images can not be changed, which
is also called semantic perturbations. Due to the naturalness and physical
realizability, semantic perturbations have been an emerging area, such as
changing the geometry [12], color [13], and lightness [14] of clean images.

To enhance the robustness of deep neural network (DNN) models against
adversarial examples, significant efforts have been devoted to improving the
robustness of DNNs through various defense strategies. These strategies
include adversarial training [15], defensive distillation [16], dimensionality
reduction [17], input transformations [18], and activation transformations
[19]. The continuous development in the field of defense techniques has made
it challenging to accurately evaluate the robustness of DNN models due to the
limitations of existing adversarial attack algorithms. On the one hand,
evaluating the robustness of models using adversarial attacks often requires
high computational costs, making it computationally expensive to perform
extensive evaluations. On the other hand, existing adversarial attack methods
may not be able to fully explore the lower bound of the robust accuracy of
defended models, thus providing an incomplete assessment of the model’s
robustness. Therefore, the evaluation of DNN model robustness remains a
challenging task due to the trade-off between computational resources and the
inability to obtain a comprehensive measure of a model’s resilience against
adversarial attacks. Further research and development are needed to overcome
these challenges and establish more effective evaluation methodologies for
assessing the robustness of DNN models.

To achieve a more reliable and efficient robustness evaluation of defended
models, researchers have applied auto machine learning (AutoML) technique [20,
21] into adversarial attack area for automated adversarial attacks. For
instance, Francesco et al. [22] introduced auto attack (AA), an ensemble
attack that combines four types of attacks to obtain lower robust accuracy
against multiple defense methods. Tramer et al. [23] explored the impact of
loss functions on adversarial attacks and demonstrated that suitable loss
functions can further reduce the robust accuracy of defended models. Mao et
al. [24] proposed a composite adversarial attack (CAA), which utilized the
NSGA-II algorithm [25] to search for near-optimal adversarial attacks while
considering complexity and robust accuracy. Furthermore, Yao [26] proposed an
adaptive auto attack, which not only searched for adversarial attack
algorithms but also optimized hyperparameters, including randomization, using
a hyperparameter optimization search method. Liu et al. [27] introduced an
adaptive adversarial attack, which automatically selects the restart direction
and attack budget for each image. In summary, the development of automated
adversarial attack methods, such as auto attack, composite adversarial attack,
adaptive auto attack, and adaptive adversarial attack, has demonstrated that
conducting automated attacks for each defense model can yield lower robust
accuracy and provide a more reliable evaluation of model robustness. These
advancements contribute to a more comprehensive understanding of the
effectiveness and limitations of defense strategies against adversarial
attacks.

Though there exist some works about AutoML for $L_{\infty}$-norm-based
attacks, it still remains an open problem about AutoML for unrestricted-based
attacks. To improve the performance of semantic perturbations, Tsai et al.
[28, 29] proposed composite semantic perturbations (CSP), which combines the
advantages of different semantic perturbations and form stronger attack
algorithms. In their search space, five semantic perturbations are provided,
including Hue, Saturation, Rotation, Contrast, and Brightness. Given one
attack sequence, two modes can be selected, including the fixed and scheduled,
where the fixed one denotes the fixed attack sequence, while the scheduled one
would adjust the order of the attack sequence according to the batch data to
perform stronger perturbations.

Figure 1: The comparison of the robust accuracy of the model, attack success
rate, time cost, and $L_{2}$ distance between the generated AEs and clean
images by CSP and MES-VCSP (ours) under two modes, including the fixed and
scheduled. Figure 2: The illustration of the core idea and attack success rate
(ASR) of our proposed NS-VCSP.

Based on their work on CSP, we find that the adversarial performance of CSP
can be greatly improved by changing the length of attack sequences under the
same search space. This phenomenon motivates us to propose the mathematical of
variable-length composite semantic perturbations (VCSP), where the
perturbation interval of each type of attack needs to be adaptively changed
according to the number of the same attack in one attack sequence, making the
final perturbations meet the original maximum constraints. In addition, to
realize the automatical search, we introduce the multi-objective evolutionary
search algorithm to find the near-optimal composite semantic perturbation
sequence. Experimental results show that the attack performance can be
improved greatly. An example of the comparison of CSP and the proposed MES-
VCSP on the same adversarially trained model on the CIFAR10 dataset can be
seen in Figure. 1. Our proposed MES-VCSP can achieve the attack success rate
(ASR) of 49.1$\%$, while that of CSP is only 35.5$\%$. Besides, both the time
cost and the $L_{2}$ distance between generated AEs and clean images of MES-
VCSP are lower than CSP, showing the superiority of our proposed method. The
core idea of VCSP can be seen in Figure. 2. By just changing the length of CSP
from three to five, where both the rotation attack and saturation attack are
performed twice, we can improve the ASR from 23.8$\%$ to 35.5$\%$ on the
ImageNet dataset.

Our main contributions are concluded as follows:

  * 1.

We propose the mathematical model of variable-length composite semantic
perturbations, where the interval of each type of perturbation is adaptively
adjusted by the number in an attack sequence.

  * 2.

We introduce the multi-objective optimiztaion algorithm consisting of NSGA-II
and neighborhood search algorithm to solve the proposed optimization problem,
which can effectively find the near-optimal attack sequence.

  * 3.

Compared with existing methods, experimental results on CIFAR10 and ImageNet
datasets show that we can find the composite semantic perturbations with a
higher attack success rate, less time cost, and more naturalness.

The remainder of this paper is organized as follows. Section 2 introduces the
background of composite semantic perturbations. Section 3 elaborates our
proposed method. Section 4 elaborates the experimental settings and results.
Section 5 concludes this paper.

##  2 Background

In this section, the background of five types of semantic perturbations is
first introduced briefly. Then we describe the process of existing composite
semantic perturbation. Finally, we elaborate on the concept of neighborhood
search.

###  2.1 Semantic Perturbations

For most of the semantic perturbations, the parameters that need to be
optimized are continuous. Under the white-box attack setting, the parameters
of semantic attacks can be updated by the gradient descent algorithm.
Specifically, the paragraph outlines how the parameters can be updated for
five different types of semantic perturbations, namely hue, saturation,
brightness, contrast, and rotation. To optimize these perturbations, the
iterative gradient sign method [30] is extended for $T$ iterations , which is
defined as:

$\delta_{k}^{t+1}=\operatorname{clip}_{\epsilon_{k}}\left(\delta_{k}^{t}+\alpha\cdot\operatorname{sign}\left(\nabla_{\delta_{k}^{t}}J\left(\mathcal{F}\left(A_{k}\left(X;\delta_{k}^{t}\right)\right),y\right)\right)\right)$
(1)

where $t$ is the iteration number, $\mathcal{F}$ stands for the DNN model, $X$
denotes the input images, $y$ is the prediction label, $\epsilon_{k}$ is the
perturbation interval. Assume $\epsilon_{k}=[\alpha_{k},\beta_{k}]$, the
element-wise clipping operation $\operatorname{clip}_{\epsilon_{k}}$ is
expressed as:

$\operatorname{clip}_{\epsilon_{k}}(z)=\operatorname{clip}_{\left[\alpha_{k},\beta_{k}\right]}(z)=\left\\{\begin{aligned}
\alpha_{k}&\text{ if }z<\alpha_{k}\\\ z&\text{ if }\alpha_{k}\leq
z\leq\beta_{k}\\\ \beta_{k}&\text{ if }\beta_{k}<z\end{aligned}\right.$ (2)

The following description provides an explanation of each semantic attack.

Hue: The Hue attack can transfer clean images from RGB space to HSV space,
causing a dropping in accuracy. The Hue value ranges from 0 to 2$\pi$. Hence,
the maximum perturbation interval of Hue attack is [-2$\pi$,2$\pi$] [28].

$x_{H}^{t}=\operatorname{Hue}\left(x_{\mathrm{adv}}^{t}\right)=\operatorname{clip}_{[0,2\pi]}\left(x_{H}+\delta_{H}^{t}\right)$
(3)

Saturation: The Saturation attack can change the colorfulness of clean images
by modifying the Saturation value, which ranges from 0 to 1. If the saturation
value tends to be 1, the image becomes more colorful, while that is a gray-
scale image if the saturation value is 0 [28].

$x_{S}^{t}=\operatorname{Sat}\left(x_{\text{adv
}}^{t}\right)=\operatorname{clip}_{[0,1]}\left(x_{S}\cdot\delta_{S}^{t}\right)$
(4)

Brightness and Contrast: Brightness and contrast are different from hue and
saturation in that they are defined in the RGB color space (pixel space) and
determine the brightness and darkness differences of images. In our
implementation, we first convert the images from the [0, 255] scale to the [0,
1] scale. The perturbation interval for brightness is defined as
$\epsilon_{B}=[\alpha_{B},\beta_{B}]$, where
$-1\leq\alpha_{B}\leq\beta_{B}\leq 1$, while for contrast it is defined as
$\epsilon_{C}=[\alpha_{C},\beta_{C}]$, where
$-1\leq\alpha_{C}\leq\beta_{C}\leq 1$.

Similarly to the hue and saturation attacks, we choose initial perturbations
$\delta^{0}_{B}$ and $\delta^{0}_{C}$ uniformly from $\epsilon_{B}$ and
$\epsilon_{C}$, respectively, and update them using Eq. 1. The perturbed image
$x^{t}_{adv}$ under the brightness attack is then obtained by adding the
perturbation to the original image x, clamping the resulting values to be
between 0 and 1, and scaling the result back to the [0, 255] scale. The
Brightness and Contrast attacks determine the lightness, darkness, and
brightness difference of images in RGB color space [28], which can be obtained
by Eq. 5.

$x_{\mathrm{adv}}^{t}=\operatorname{clip}_{[0,1]}\left(x+\delta_{B}^{t}\right)\text{
and
}x_{\mathrm{adv}}^{t}=\operatorname{clip}_{[0,1]}\left(x\cdot\delta_{C}^{t}\right)$
(5)

Rotation: The purpose of this transformation is to discover an angle of
rotation that maximizes the loss of the rotated image. The rotation algorithm
was developed by [31]. Assuming we have a square image $x$, we can denote a
pixel’s position as $\left(i,j\right)$, and the center of $x$ as
$\left(c,c\right)$. To calculate the new position
$\left(i^{\prime},j^{\prime}\right)$ of a pixel rotated by an angle of
$\theta$ degrees, we can use the following formula:

$\left[\begin{array}[]{l}i^{\prime}\\\
j^{\prime}\end{array}\right]=\left[\begin{array}[]{c}\cos\theta\cdot
i+\sin\theta\cdot j+(1-\cos\theta)\cdot c-\sin\theta\cdot c\\\
-\sin\theta\cdot i+\cos\theta\cdot j+\sin\theta\cdot c+(1-\cos\theta)\cdot
c\end{array}\right]$ (6)

###  2.2 Composite Semantic Perturbations

As for the white-box model, each attack above-mentioned can obtain the optimal
perturbations by iteratively updating according to the gradient of model
predictions. CSP tries to ensemble different types of semantic attacks to
realize the more effective attacks. An illustration of the process of
composite semantic perturbations is presented in Figure. 3. The attack space
includes five types of semantic adversarial attacks, namely Hue, Saturation,
Rotation, Brightness, and Contrast. The configuration way of different types
of attacks can be represented using the attack sequence, which consists of the
types and order of multiple attacks. When an attack sequence is given, the
input image would be fed to different attacks subsequently. In the original
work, CSP constructed the mathematical model of combining multiple types of
attacks, which includes two modes, namely the fixed and scheduled.

Fixed: The fixed mode means that CSP utilizes the ensemble attack with the
fixed sequence, where the order of attacks does not change during the process
of attacking DNN models.

Scheduled: The scheduled mode means that the order of the attack sequence can
be adaptively adjusted with the batch data during the attacking process, which
can achieve a higher ASR. The detailed way of updating the order of CSP can be
seen in [28].

Figure 3: The illustration of composite semantic perturbation.

###  2.3 Neighborhood Search

To handle the discrete optimization problem, neighborhood search emerges as an
effective technique. Its core idea is to construct the appropriate
neighborhood for each candidate solution according to the characteristic of
the problem. The best solutions to optimization problems can be obtained by
iteratively exploring the neighborhood. Over the past years, many efforts have
been devoted to developing effective neighborhood search algorithms [32, 33,
34].

##  3 Method

In this section, we introduce our proposed MES-VCSP method in detail. In
section 3.1, we elaborate on the mathematical model of the proposed VCSP. In
section 3.2, we introduce the multi-objective search algorithm for VCSP,
including the search space, performance evaluation, and search strategy. The
overview of our proposed MES-VCSP is presented in Figure. 4. Among that, the
process of neighborhood search can be seen in Figure. 5.

Figure 4: The process of multi-objective evolutionary search of variable-
length composite semantic perturbations. Figure 5: The process of neighborhood
search.

###  3.1 The mathematical model of VCSP

In CSP, the length of attack sequence $k$ is fixed to the number of semantic
perturbations in the search space $l_{sp}$, and each type of semantic
perturbation is only allowed to be performed once. Then CSP tried to find the
near-optimal configuration of different semantic perturbations under the
scheduled mode. Different from CSP, we construct the mathematical model of
variable-length composite semantic perturbations, which is presented as
follows:

$\begin{array}[]{ll}\text{find}&\bm{x}\\\
\min&F=[f_{1}(\bm{x}),f_{2}(\bm{x})]\\\ \text{ s.t. }&1\leq\bm{x}(i))\leq
l_{sp},\forall i\in[0,k]\\\ &l_{sp}\leq k\leq l_{max}\\\ \end{array}$ (7)

where $\bm{x}$ is the attack sequence of VCSP that we aim to find, $k$ denotes
the length of VCSP, $l_{max}$ is the pre-settled maximum length of the attack
sequence, $i$ represents the dimension of $\bm{x}$. From Eq. 7, we can see
that our proposed VCSP can allow the same type of perturbation to be performed
multiple times. To ensure the naturalness, the interval of each perturbation
would be adaptively adjusted, where an example can be seen in 3.2.1. One
optimization objective is the robust accuracy (RA) of the DNN model under
adversarial attack $\bm{x}$, which is presented as follows.

$f_{1}=Robust\text{ }Accuracy\text{ =}\frac{{{n}_{adv}}}{{{n}_{total}}}$ (8)

where ${n}_{total}$ stands for the number of total test samples that are
generated by the adversarial attack. ${n}_{adv}$ denotes the number of
examples that are predicted rightly. Another optimization objective $f_{2}$ is
$L_{2}$ between the generated AEs and original images, which is calculated as
follows.

$\begin{array}[]{l}f_{2}=\mathcal{L}_{2}=\frac{\sum\limits_{i=1}{\text{MSE}(\mathbf{O}_{i},\mathbf{O}_{adv,i})}}{{n}_{total}}\end{array}$
(9)

where $\mathbf{O}_{i},\mathbf{O}_{adv,i}$ are $i_{th}$ original image and its
corresponding adversarial example.

###  3.2 Multi-objective search for VCSP

####  3.2.1 search space

To make a fair comparison, we still include five semantic perturbations
provided by CSP in our search space. Denote the Hue, Saturation, Rotation,
Brightness, and Contrast as 0, 1, 2, 3, 4, and we construct three search
spaces, which are [0,1,2], [0,1,2,3], [0,1,2,3,4]. It means that the $n_{sp}$
in Eq. 7 is 3, 4, and 5, respectively, in our defined search spaces. Under
three search spaces, we search for the near-optimal configuration of semantic
perturbations. The interval of each semantic perturbation is presented in
Table 1. In our variable-length CSP, the interval of each perturbation would
be adaptively adjusted. Taking the Rotation operation as an example, if the
attack sequence is [0,2,1,2], the interval of the Rotation operation at two
attacks is [-5∘,5∘], which ensures that the final perturbations meet the
original constraint [-10∘,10∘].

Table 1: Interval of each semantic perturbation. Peturbations | Hue | Saturation | Rotation | Brightness | Contrast
---|---|---|---|---|---
Interval |  [-$\pi$, $\pi$] | [0.7, 1.3] |  [-10∘, 10∘] | [-0.2, 0.2] | [0.7, 1.3]

Input:

The maximum number of iteration ${T}$, population size $n$, the training set
$D_{train}$, the crossover rate $r_{c}$, the mutation rate $r_{m}$, the
maximum length of the searched adversarial attack $l_{max}$;

Output:

The near-optimal adversarial attack.

1 Generate the initial population $\bm{P}$ with $n$ composite semantic
perturbations randomly. The length of each adversarial attack does not exceed
$l_{max}$;

2 Evaluate the RA and $L_{2}$ distance of each individual in $\bm{P}$;

3

4while  _$t\leftarrow 1:T$_ do

5 // Evolution by discrete NSGA-II

6 Generate $n$ offspring individuals using crossover and mutation operation;

7 Merge the offspring individuals with $\bm{P}$ and conduct the evaluation;

8 Select $n$ individuals to form the new $\bm{P}$ using non-dominated-sorting
and crowding distance;

9 // Neighborhood search

10 Obtain one individual in the first Pareto randomly $\bm{x}$;

11 Conduct neighborhood search based on $\bm{x}$ according to Algorithm 3;

12 Evaluate the individuals generated by local search and select the best one
to substitute $\bm{x}$;

13

14 end while

15

Return The near-optimal adversarial attack

Algorithm 1 Multi-objective Search of Variable-length Composite Semantic
Perturbations

Input: The attack sequence solution $\bm{x}$

Output: The neighbour candidate solutions $N(\bm{x},j)$

1 for  _$m\leftarrow 0:l_{sp}-1$_ do

2 $\bm{x}_{neighbor}$ $\leftarrow$ $\bm{x}$;

3 if  _$x_{j}\neq m$_ then

4 $x_{neighbor,j}$ $\leftarrow$ $m$;

5 Include the new $\bm{x}_{neighbor}$ in $N(\bm{x},j)$;

6

7 end if

8

9 end for

10

Return The neighbour candidate solutions $N(\bm{x},j)$

Algorithm 2 Generate the $j$th neighbour attack sequences solution
$\bm{x}$:$N(\bm{x},j)=neighborhood(\bm{x},j)$

Input: The search space of semantic perturbations, maximum iteration number of
outer loop $c$, an attack sequence $\bm{x}$, the maximum length of the
searched adversarial attack $l_{max}$

Output: The optimal attack sequence $\bm{x}_{g}$

1 $\bm{x}_{g}\leftarrow\bm{x}$;

2 $m\leftarrow$ Obtain current length of the attack sequence $\bm{x}_{g}$;

3 Calculate the RA and $L_{2}$ of $\bm{x}_{g}$;

4 Caulate the fitness of $\bm{x}_{g}$: $fitness_{g}$ = RA + $\lambda$$L_{2}$;

5 for  _$k\leftarrow m:min\left\\{m+c,l_{max}\right\\}$_ do

6

7 while  _$flag=1$_ do

8 $flag=0$;

9 for  _$j\leftarrow 1:k$_ do

10

11 Generate the neighbour solutions $N(\bm{x}_{g},j)$ according to Algorithm
2;

12 Calculate the perturbation interval of each atttack sequence in
$N(\bm{x}_{g},j)$;

13 $f_{1}(N(\bm{x}_{g},j)),f_{2}(N(\bm{x}_{g},j))\leftarrow$ Calculate the RA
and $L_{2}$ of $N(\bm{x}_{g},j)$ ;

14 $f(\bm{x})\leftarrow$ Calculate the fitness of $N(\bm{x}_{g},j)$;

15 if  _ $max_{\bm{x}\in N{(\bm{x}_{g},j)}}$$f(\bm{x})<fitness_{g}$_ then

16 $flag=1$;

17 $fitness_{g}$ $\leftarrow$ $min_{x\in N{(\bm{x}_{g},j)}}$;

18 $\bm{x}_{g}$ $\leftarrow$ $argmin_{x\in N{(\bm{x}_{g},j)}}$;

19

20 end if

21

22 end for

23

24 end while

25 Add the $\bm{x}_{g}$ to the set $\bm{S}$;

26 $\bm{x}_{g}\leftarrow$ concat($\bm{x}_{g}$, random.randint(0, 5))

27 end for

Return the best attack sequence $\bm{x}_{g}$ in set $\bm{S}$

Algorithm 3 The pseud-code of neighborhood search

####  3.2.2 performance evaluation

During the search, we take the robust accuracy and $L_{2}$ distance as two
metrics to evaluate the performance of each attack sequence. The robust
accuracy is the percentage of images that can be correctly recognized by DNN
models on total generated AEs. The $L_{2}$ distance denotes the $L_{2}$ norm
between generated AEs and original clean images. Lower RA means better attack
performance, while lower $L_{2}$ distance means better naturalness. In our
proposed method, we aim to search for the near-optimal attack sequence with
the lowest RA and smallest $L_{2}$ distance under the perturbation interval.
If multiple attack sequences with different lengths possess the same RA, the
short one would be selected as the final searched attack. It is because the
short one would bring less computational cost. Our proposed search strategy
includes NSGA-II and neighborhood search. The latter is a single-objective
optimization algorithm, where the objective is formulated as follows.

$\begin{array}[]{l}f=f_{1}+\lambda f_{2}=\text{RA}+\lambda L_{2}\end{array}$
(10)

####  3.2.3 search strategy

To find the near-optimal attack sequence, we introduce the multi-objective
search algorithm consisting of NSGA-II and neighborhood search. The whole
process of our method is presented in Algorithm 1. We start by generating the
initial population, including multiple random sequences, denoted as $\bm{P}$.
Among the population, the length of composite semantic perturbations can
differ. Thus a maximum length $n_{max}$ needs to be preset. After the
population is evaluated on the dataset, the crossover and mutation operations
are performed to generate the offspring. The crossover rate and mutation rate
are set to $r_{c}$ and $r_{m}$, respectively. The new population is selected
according to non-dominated-sorting. Then we will select the near-optimal
individual randomly from the first Pareto to conduct the neighborhood search.
Denote the selected individual as $\bm{x}$. The procedure of neighborhood
search can be seen in Algorithm 3. We first assign the value of $x$ to the
$\bm{x}_{g}$. Then the following procedure consists of two loops. In the inner
loop, we try to find the near-optimal sequence with the fixed length. We
obtain the neighborhood by changing one value at each time according to the
dimensionality, as presented in Algorithm 2. All the attack sequences in the
neighborhood would be evaluated and compared with $\bm{x}_{g}$. The best one
would be preserved as new $\bm{x}_{g}$. If all the dimensionalities are
changed and do not improve the attack performance, the algorithm will conduct
the outer loop. In the outer loop, we try to find the near-optimal length of
attack sequences from short to long. The initial length is the original length
of $x$, which is denoted as $m$. The maximum length is set to
$min\left\\{m+c,n_{max}\right\\}$, where $c$ is the maximum iteration number
of the outer loop and $l_{max}$ is the maximum length of the searched
adversarial attack. By $min\left\\{m+c,n_{max}\right\\}$, we can not only set
the maximum length of the attack sequence but also limit the computational
cost by setting $c$ flexibly. After each inner loop terminates, the best
attack sequence would be preserved to an archive $\bm{S}$ until the outer loop
ends. Then the best attack sequence in $\bm{S}$ would be the final searched
attack. By neighborhood search, the promising solution searched by NSGA-II can
efficiently find the better attack sequence. Thus, the whole algorithm can
achieve a better balance between the exploitation ability and exploration
ability.

##  4 Experimental Results

###  4.1 Experimental settings

In our experimental settings, we select the CIFAR10 and ImageNet datasets. The
number of test images is set to 10,000 and 500, respectively. The threat
models include standard training models and defensed models. The standard
training models are VGG19, ResNet18, GoogleNet, DenseNet121, and MobileNetV2.
On both datasets, the attack is searched on the former model (source model)
and transferred to the latter one (target model), which is to illustrate the
transferability of the searched attack and avoid the repeatedly search. In our
experiments, VGG19 is set as the source model. In addition, we also transfer
the searched attacks on CIFAR10 and ImageNet datasets to the defensed models
to evaluate the performance of the proposed method. For the defensed models,
we utilize generalized adversarial training (GAT), ensemble adversarial
training (EnsembleAT), label smoothing (LS), fast adversarial training
(FastAT), and robust transfer (RT). For the CIFAR10 dataset, we retrain the
VGG19, ResNet18, GoogleNet, DenseNet121, and MobileNetV2 models using the GAT
technique. For the ImageNet dataset, five model architectures, including
WideResnet50, WideResnet50, Resnet50, Inception$\\_$ResNet$\\_$V2, and
Inception$\\_$V3, adopt the corresponding above-mentioned defensed strategy.

Implementation details: To provide a comprehensive comparison, we include the
same search space, [0,1,2,3,4], as CSP. In the MES-VCSP, we just set the
iteration number of each attack component as 1. The maximum length of VCSP
$l_{max}$ is set to 8. To provide a fair comparison, in CSP, the corresponding
iteration number of each attack component is set to 2. During the search for
the near-optimal attack sequence, we take the robust accuracy and the $L_{2}$
distance between the generated AEs and clean images as the objectives. Both
the population size $n$ and maximum number of iteration $T$ are set to 20. The
crossover rate and mutation rate, namely $r_{c}$ and $r_{m}$, are set to 0.6
and 1, respectively. Duing the neighborhood search, the coefficient $\lambda$
in Eq. 10 is set to 1. The maximum iteration number of outer loop $c$ is set
to 1. The maximum length of the searched adversarial attack $l_{max}$ is set
to 8. The number of images in the training dataset to evaluate the performance
of attack sequences for CIFAR10 and ImageNet are set to 500 and 100,
respectively. When the searched attack is evaluated, we also include other
metrics, such as the attack success rate and time cost of the evaluation. All
the experiments are conducted using a single NVIDIA Titan P2 GPU.

Table 2: The comprehensive comparison of CSP and MES-VCSP on the CIFAR10
dataset.

Model | Clean | Method | Attack sequence | Mode | Robust Accuracy ($\downarrow$) |  ASR ($\uparrow$) |  Time cost ($\downarrow$) |  $L_{2}$ ($\downarrow$)
---|---|---|---|---|---|---|---|---
|  | CSP | [0,1,2,3,4] | fixed |  43.3$\%$ |  53.4$\%$ | 50.61s | 12.70
VGG19 | 92.34 | MES-VCSP | [2,1,0,1,4,2,3] | fixed | 30.1$\%$ | 67.7$\%$ |  45.64s | 12.61
|  | CSP | [0,1,2,3,4] | scheduled |  20.6$\%$ |  77.7$\%$ | 380.63s | 14.32
|  | MES-VCSP | [2,1,0,1,4,2,3] | scheduled | 13.7$\%$ | 85.2$\%$ |  315.29s | 13.38
|  | CSP | [0,1,2,3,4] | fixed |  51.6$\%$ |  45.6$\%$ | 60.73s | 13.13
ResNet18 | 94.87 | MES-VCSP | [2,1,0,1,4,2,3] | fixed | 33.6$\%$ | 64.6$\%$ |  49.61s | 13.12
|  | CSP | [0,1,2,3,4] | scheduled |  27.6$\%$ |  70.9$\%$ | 544.46s | 14.94
|  | MES-VCSP | [2,1,0,1,4,2,3] | scheduled | 15.7$\%$ | 83.5$\%$ |  438.91s | 13.95
|  | CSP | [0,1,2,3,4] | fixed |  53.0$\%$ |  44.5$\%$ | 183.93s | 13.38
GoogleNet | 95.26 | MES-VCSP | [2,1,0,1,4,2,3] | fixed | 32.3$\%$ | 66.3$\%$ |  142.76s | 13.00
|  | CSP | [0,1,2,3,4] | scheduled |  27.7$\%$ |  70.9$\%$ | 2043.92s | 15.18
|  | MES-VCSP | [2,1,0,1,4,2,3] | scheduled | 15.2$\%$ | 84.1$\%$ |  1568.07s | 14.04
|  | CSP | [0,1,2,3,4] | fixed |  49.1$\%$ |  48.0$\%$ | 202.31s | 13.45
DenseNet121 | 94.43 | MES-VCSP | [2,1,0,1,4,2,3] | fixed | 32.2$\%$ | 66.1$\%$ |  154.31s | 13.09
|  | CSP | [0,1,2,3,4] | scheduled |  25.0$\%$ |  73.5$\%$ | 2164.73s | 15.16
|  | MES-VCSP | [2,1,0,1,4,2,3] | scheduled | 15.4$\%$ | 83.7$\%$ |  1663.82s | 13.96
|  | CSP | [0,1,2,3,4] | fixed |  43.9$\%$ |  53.0$\%$ | 86.23s | 12.84
MobileNetV2 | 93.01 | MES-VCSP | [2,1,0,1,4,2,3] | fixed | 27.3$\%$ | 70.9$\%$ |  66.12s | 12.31
|  | CSP | [0,1,2,3,4] | scheduled |  19.2$\%$ |  79.4$\%$ | 815.75s | 14.33
|  | MES-VCSP | [2,1,0,1,4,2,3] | scheduled | 10.5$\%$ | 88.7$\%$ |  633.81s | 13.22

Table 3: The comprehensive comparison of CSP and MES-VCSP on the ImageNet
dataset.

Model | Clean | Method | Attack sequence | Mode | Robust Accuracy ($\downarrow$) |  ASR ($\uparrow$) |  Time cost ($\downarrow$) |  $L_{2}$ ($\downarrow$)
---|---|---|---|---|---|---|---|---
|  | CSP | [0,1,2,3,4] | fixed |  6.8$\%$ |  88.4$\%$ | 23.73s | 86.15
VGG19 |  58.4$\%$ | MES-VCSP | [3,4,2,0,1,3,2,1] | fixed | 1.6$\%$ | 97.2$\%$ |  20.51s | 55.56
|  | CSP | [0,1,2,3,4] | scheduled |  1.6$\%$ |  97.2$\%$ | 75.51s | 71.19
|  | MES-VCSP | [3,4,2,0,1,3,2,1] | scheduled | 1.3$\%$ | 97.8$\%$ |  49.84s | 62.58
|  | CSP | [0,1,2,3,4] | fixed |  3.9$\%$ |  93.5$\%$ | 9.44s | 84.00
ResNet18 |  59.4$\%$ | MES-VCSP | [3,4,2,0,1,3,2,1] | fixed | 1.9$\%$ | 96.7$\%$ |  9.12s | 61.32
|  | CSP | [0,1,2,3,4] | scheduled |  0.3$\%$ |  99.5$\%$ | 20.03s | 82.39
|  | MES-VCSP | [3,4,2,0,1,3,2,1] | scheduled | 0.0$\%$ | 100$\%$ |  14.85s | 65.01
|  | CSP | [0,1,2,3,4] | fixed |  21.6$\%$ |  70.9$\%$ | 16.53s | 94.97
GoogleNet |  74.2$\%$ | MES-VCSP | [3,4,2,0,1,3,2,1] | fixed | 9.0$\%$ | 87.8$\%$ |  14.56s | 77.37
|  | CSP | [0,1,2,3,4] | scheduled |  4.8$\%$ |  93.5$\%$ | 90.26s | 84.72
|  | MES-VCSP | [3,4,2,0,1,3,2,1] | scheduled | 1.6$\%$ | 97.8$\%$ |  50.75s | 73.59
|  | CSP | [0,1,2,3,4] | fixed |  12.3$\%$ |  84.1$\%$ | 31.05s | 90.47
DenseNet121 |  75.2$\%$ | MES-VCSP | [3,4,2,0,1,3,2,1] | fixed | 3.5$\%$ | 95.3$\%$ |  23.78s | 80.57
|  | CSP | [0,1,2,3,4] | scheduled |  2.9$\%$ |  96.1$\%$ | 127.06s | 85.85
|  | MES-VCSP | [3,4,2,0,1,3,2,1] | scheduled | 0.6$\%$ | 99.1$\%$ |  59.70s | 87.05
|  | CSP | [0,1,2,3,4] | fixed |  5.5$\%$ |  90.5$\%$ | 12.28s | 84.14
MobileNetV2 |  54.2$\%$ | MES-VCSP | [3,4,2,0,1,3,2,1] | fixed | 2.3$\%$ | 95.8$\%$ |  10.76s | 53.79
|  | CSP | [0,1,2,3,4] | scheduled | 0.6$\%$ | 98.8$\%$ | 23.59s | 69.14
|  | MES-VCSP | [3,4,2,0,1,3,2,1] | scheduled |  1.0$\%$ |  98.2$\%$ |  19.19s | 52.46

###  4.2 The performance MES-VCSP on standard training models

We compare the performance of CSP and MES-VCSP on two modes, including the
fixed and scheduled. The search Pareto front using VGG19 as the source model
is presented in Figure. 6. From Figure. 6, we can see that the proposed
optimization model is a typical multi-objective optimization problem. All the
individuals in the Pareto front are the optimal solutions. We compromise by
choosing a solution with relatively good robust accuracy and $L_{2}$ distance
as the searched attack to evaluate other models. The searched attacks on the
CIFAR10 dataset and ImageNet dataset are [2,1,0,1,4,2,3] and
[3,4,2,0,1,3,2,1], respectively. The evaluation results of five standard
training models under CSP and the searched attacks are shown in Table 2 and
Table 3, respectively. From Table 2 and Table 3, we can see that in almost all
cases, MES-VCSP can obtain a significantly higher ASR than CSP. In some cases,
like GoogleNet in CIFAR10 dataset, the improvement of ASR can even reach over
20$\%$. Besides, in all cases, the time cost of MES-VCSP is less than CSP,
which verifies the effectiveness of our proposed method. The $L_{2}$ distances
of generated AEs of MES-VCSP are also smaller than CSP in most cases. Some
examples of CSP and MES-VCSP are presented in Figure. 7. From Figure. 7, we
can see that the AEs generated by MES-VCSP can still possess good natural
appearances and original semantics. It shows that our improvement in ASR does
not sacrifice the semantic information of the original images. In addition,
experimental results also show that the searched attack possesses superior
transferability across different models. In all cases of target models, the
ASR of MES-VCSP is also higher than CSP. It illustrates that we do not need to
search for the near-optimal attack sequence repeatedly from scratch for each
model, further showing the effectiveness of our proposed method. In general,
our proposed method can obtain the AEs with higher ASR, less time cost, and
more naturalness.

Figure 6: The visualization of population after 20 iterations.

Figure 7: The visualization of generated AEs by CSP (first row) and MES-VCSP
(second row).

###  4.3 The performance of MES-VCSP on defensed models

Figure 8: The comparison of CSP and MES-VCSP on defensed model on the CIFAR10
dataset under the fixed mode. VGG, RN18, GN, DN121, and MNV2 denote VGG19,
ResNet18, GoogleNet, DenseNet121, and MobileNetV2. Figure 9: The comparison of
CSP and MES-VCSP on defensed model on the CIFAR10 dataset under the scheduled
mode. Figure 10: The comparison of CSP and MES-VCSP on defensed model on the
ImageNet dataset under the fixed mode. GAT, EAT, LS, FAT, and RT denote
generalized adversarial training, ensemble adversarial training, label
smoothing, fast adversarial training, and robust transfer. Figure 11: The
comparison of CSP and MES-VCSP on defensed model on the ImageNet dataset under
the scheduled mode.

During the process of evaluating the robustness of defensed models, we
directly transfer the searched attacks to standard training models to assess
them. The comprehensive evaluation results under different modes and datasets
are shown in Figure. 8, Figure. 9, Figure. 10 and Figure. 11, respectively.
From Fig 8 and Figure. 9, we can see that GAT can greatly improve the
robustness of DNN models against CSP and MES-VCSP, whose robust accuracy on
the CIFAR10 dataset can reach over 50$\%$. We also can find that under the
defensed strategies, our proposed MES-VCSP can still possess superior attack
performance than CSP. The improvement of ASR on five models on the CIFAR10
dataset can reach 5$\%$ to 10$\%$. In addition, MES-VCSP takes less time cost
and possesses more natural AEs. The results of Figure. 10 and Figure. 11 show
that GAT is the most effective defensed strategy. Under different defense
strategies, MES-VCSP can still possess higher ASR than CSP. Among them, the
improvement of MES-VCSP over CSP is the greatest on the GAT technique, which
is about 15$\%$ to 20$\%$. As for the FAT technique, MES-VCSP is slightly
better than CSP. These experimental results on different defensed strategies
show that our proposed MES-VCSP can possess better attack generality than CSP.

###  4.4 Analysis about the reason why VCSP is effective

The effectiveness of MES-VCSP motivates us to conduct experiments to explore
the reason for improving ASR greatly. We first select one defensed model on
the CIFAR10 dataset as the threat model to conduct the rotation attack. The
reason for selecting a rotation attack is that the search space, namely the
lower and upper bound of the original variable, does not change if multiple
attacks are performed using our proposed variable-length strategy. [2] stands
for the rotation attack, where the interval of the rotation angle is [-10∘,
10∘]. [2, 2] means that we perform rotation attack twice, where the interval
of the rotation angle is [-5∘, 5∘] at each time. The iteration number denotes
the iteration number of each rotation attack. Table 4 presents the performance
of different roration attacks. We can find that by increasing the length of
the attack sequence, the attack performance becomes better, whose results
correspond with the previous experimental results. The most important reason
is that when we perform each semantic attack, we first randomly sample a value
from the interval. Then based on the initial value, the gradient-based
optimization is conducted to find the near-optimal perturbation value.
Therefore, by the proposed variable-length strategy, we can sample multiple
times the initial values, which can prevent the gradient-based optimization
algorithm from being trapped in the local optimum. Another reason is that when
we perform one type of semantic into multiple attacks, the interval has
changed compared with the original one. Taking the Hue attack as an example,
the perturbation interval is [-$\pi$, $\pi$] if it is performed only once
time. However, if it is performed twice times, the second perturbation
interval [-$\pi$/2, $\pi$/2] is on the basis of the perturbed image other than
the original image. Hence, the total perturbation does not belong to
[-$\pi$/2, $\pi$/2] strictly. But in any case, the generated AEs are more
natural with smaller $L_{2}$ distance, which can illustrate the effectiveness
of the proposed VCSP model.

Table 4: The performance of different rotation attacks. Iteration number | Rotation | Robust Accuracy | ASR | Time cost | $L_{2}$
---|---|---|---|---|---
2 | [2] | 61.3 | 8.3 | 48.4 | 58.7
1 | [2] | 61.6 | 8.3 | 35.9 | 65.5
1 | [2,2] | 61.0 | 8.7 | 35.6 | 49.9
1 | [2,2,2] | 60.3 | 9.7 | 37.4 | 49.0

###  4.5 The performance of neighborhood search

To illustrate the effectiveness of neighborhood search in the proposed MES-
VCSP, we conduct the ablation study. We utilize random search to find the
optimal attack sequence in CSP and VCSP, which are denoted as RS-CSP and RS-
VCSP, respectively. Neighborhood search for CSP is denoted as NS-CSP. We
select the Fast-AT model on the ImageNet dataset as the threat model. The
robust accuracy and ASR of different methods are listed in Table 5. From Table
5, we can see that the proposed NS-VCSP can obtain the best performance.
Neighborhood search can obtain better solutions than random search in both CSP
and VCSP, showing the effectiveness of the optimization algorithm. By the same
optimization algorithm, VCSP achieves higher ASR than CSP, which illustrates
the effectiveness of our proposed variable-length composite semantic
perturbations.

Table 5: The performance of the ablation study. Method | Attack sequence |  Robust Accuracy ($\downarrow$) |  ASR ($\uparrow$) |
---|---|---|---|---
RS-CSP | [2,0,1,3,4] | 50.8 | 25.8 |
NS-CSP | [3,4,2,0,1] | 46.5 | 32.1 |
RS-VCSP | [3,4,2,0,1,3,2,1] | 38.6 | 43.6 |
NS-VCSP | [0,1,2,3,4,2,3,1] | 30.8 | 55.0 |

###  4.6 The performance of hyperparameters

During the optimization, the neighborhood search includes two hyperparameters,
namely $\lambda$ and $c$. Hence, in this section, we investigate the
performance of the whole algorithm under different hyperparameters. We set
$\lambda$ to four values, including 0.1, 0.5, 1, and 5, respectively. We also
set $c$ to 1, 3, 5, and 7. Other parameters, such as population size, are set
the same as in the above experiments. The searched Pareto fronts are presented
in Figure. 12. When $c=1$, we find the searched results of $\lambda=0.1$ and
$\lambda=0.5$ are the same. Smaller $\lambda$ makes the searched results
approach the robust accuracy, and the larger one would obtain the Pareto front
that approaches $L_{2}$ distance. A similar phenomenon can also be seen in the
experimental results under different $c$ values. When $\lambda=1$, we find the
searched results of $c=5$ and $c=7$ are the same. Larger $c$ can help to find
the attack sequence with lower robust accuracy and smaller $L_{2}$ distance,
which means neighborhood search takes more iterations. In general, to obtain
the satisfied results, both $\lambda$ and $c$ are set to 1 is a competitive
choice.

Figure 12: The searched results under different hyperparameters.

###  4.7 Discussions

Different from previous works that only focus on studying improving the
performance of semantic perturbations by manual design, our experimental
results have revealed that the proposed MES-VCSP can automatically find the
near-optimal variable-length composite semantic perturbations. In general, our
method has two strengths. On the one hand, MES-VCSP reduces the human burden
of designing the semantic adversarial attack method. On the other hand, the
proposed method can obtain the AEs with a higher ASR, less time cost, and more
naturalness. Experimental results have verified the effectiveness of the
proposed mathematical model of variable-length CSP and search strategy.
However, the proposed method still has some limitations. The defined search
space is relatively simple. We believe designing a more diverse and efficient
search space is one key component to influence the performance of
automatically searching for composite semantic perturbations.

##  5 Conclusion

This paper proposes a multi-objective evolutionary search of variable-length
composite semantic perturbations. Different from the existing composite
semantic perturbations method with the fixed length, MES-VCSP tries to search
for a near-optimal variable-length attack sequence. Specifically, variable-
length CSP constructs the mathematical model by adaptively adjusting the
interval with the changing of the attack sequence, where one type of attack is
performed multiple times. In addition, the multi-objective optimization
algorithm consisting of NSGA-II and neighborhood search algorithm is
introduced to find the optimal sequence. Experimental results on different
models, including standard training models and defensed models, show that the
searched attack by MES-VCSP can possess a higher attack success rate than CSP
with less time cost and more naturalness.

The experimental results show that our proposed variable-length composite
semantic perturbations and devised search strategy can obtain superior attack
performance on various models. But how to design a more efficient and diverse
search space towards further improving the attack performance against DNN
models with more defensed techniques can be further studied.

## Acknowledgments

This work was supported by the National Natural Science Foundation of China
(Nos.52005505).

## References

  * Szegedy et al. [2013] Szegedy, C., Toshev, A., Erhan, D..  Deep neural networks for object detection.  Advances in neural information processing systems 2013;26.
  * Zhao et al. [2019] Zhao, Z.Q., Zheng, P., Xu, S.t., Wu, X..  Object detection with deep learning: A review.  IEEE transactions on neural networks and learning systems 2019;30(11):3212–3232.
  * Goodfellow et al. [2014] Goodfellow, I.J., Shlens, J., Szegedy, C..  Explaining and harnessing adversarial examples.  arXiv preprint arXiv:14126572 2014;.
  * Madry et al. [2018] Madry, A., Makelov, A., Schmidt, L., Tsipras, D., Vladu, A..  Towards deep learning models resistant to adversarial attacks.  In: 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. OpenReview.net; 2018,.
  * Sun et al. [2023a] Sun, J., Yao, W., Jiang, T., Chen, X..  A multi-objective memetic algorithm for automatic adversarial attack optimization design.  Neurocomputing 2023a;547:126318.
  * Li et al. [2023] Li, C., Yao, W., Wang, H., Jiang, T., Zhang, X..  Bayesian evolutionary optimization for crafting high-quality adversarial examples with limited query budget.  Applied Soft Computing 2023;142:110370.
  * Li et al. [2022] Li, C., Wang, H., Zhang, J., Yao, W., Jiang, T..  An approximated gradient sign method using differential evolution for black-box adversarial attack.  IEEE Transactions on Evolutionary Computation 2022;26(5):976–990.
  * Hosseini and Poovendran [2018] Hosseini, H., Poovendran, R..  Semantic adversarial examples.  In: Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops. 2018, p. 1614–1619.
  * Bhattad et al. [2019] Bhattad, A., Chong, M.J., Liang, K., Li, B., Forsyth, D.A..  Unrestricted adversarial examples via semantic manipulation.  arXiv preprint arXiv:190406347 2019;.
  * Dreossi et al. [2018] Dreossi, T., Jha, S., Seshia, S.A..  Semantic adversarial deep learning.  In: International Conference on Computer Aided Verification. Springer; 2018, p. 3–26.
  * Sun et al. [2023b] Sun, J., Yao, W., Jiang, T., Wang, D., Chen, X..  Differential evolution based dual adversarial camouflage: Fooling human eyes and object detectors.  Neural Networks 2023b;163:256–271.
  * Xiao et al. [2018] Xiao, C., Zhu, J.Y., Li, B., He, W., Liu, M., Song, D..  Spatially transformed adversarial examples.  arXiv preprint arXiv:180102612 2018;.
  * Shamsabadi et al. [2020] Shamsabadi, A.S., Sanchez-Matilla, R., Cavallaro, A..  Colorfool: Semantic adversarial colorization.  In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2020, p. 1151–1160.
  * Sun et al. [2022] Sun, L., Juefei-Xu, F., Huang, Y., Guo, Q., Zhu, J., Feng, J., et al.  Ala: Adversarial lightness attack via naturalness-aware regularizations.  arXiv preprint arXiv:220106070 2022;.
  * Gowal et al. [2020] Gowal, S., Qin, C., Uesato, J., Mann, T., Kohli, P..  Uncovering the limits of adversarial training against norm-bounded adversarial examples.  arXiv preprint arXiv:201003593 2020;.
  * Papernot et al. [2016] Papernot, N., McDaniel, P., Wu, X., Jha, S., Swami, A..  Distillation as a defense to adversarial perturbations against deep neural networks.  In: 2016 IEEE symposium on security and privacy (SP). IEEE; 2016, p. 582–597.
  * Bhagoji et al. [2017] Bhagoji, A.N., Cullina, D., Mittal, P..  Dimensionality reduction as a defense against evasion attacks on machine learning classifiers.  arXiv preprint arXiv:170402654 2017;2(1).
  * Guo et al. [2017] Guo, C., Rana, M., Cisse, M., Van Der Maaten, L..  Countering adversarial images using input transformations.  arXiv preprint arXiv:171100117 2017;.
  * Dhillon et al. [2018] Dhillon, G.S., Azizzadenesheli, K., Lipton, Z.C., Bernstein, J., Kossaifi, J., Khanna, A., et al.  Stochastic activation pruning for robust adversarial defense.  arXiv preprint arXiv:180301442 2018;.
  * Karmaker et al. [2021] Karmaker, S.K., Hassan, M.M., Smith, M.J., Xu, L., Zhai, C., Veeramachaneni, K..  Automl to date and beyond: Challenges and opportunities.  ACM Computing Surveys (CSUR) 2021;54(8):1–36.
  * He et al. [2021] He, X., Zhao, K., Chu, X..  Automl: A survey of the state-of-the-art.  Knowledge-Based Systems 2021;212:106622.
  * Croce and Hein [2020] Croce, F., Hein, M..  Reliable evaluation of adversarial robustness with an ensemble of diverse parameter-free attacks.  In: Proceedings of the 37th International Conference on Machine Learning, ICML 2020, 13-18 July 2020, Virtual Event; vol. 119 of _Proceedings of Machine Learning Research_. PMLR; 2020, p. 2206–2216.  URL: http://proceedings.mlr.press/v119/croce20b.html.
  * Tramer et al. [2020] Tramer, F., Carlini, N., Brendel, W., Madry, A..  On adaptive attacks to adversarial example defenses.  Advances in Neural Information Processing Systems 2020;33:1633–1645.
  * Mao et al. [2021] Mao, X., Chen, Y., Wang, S., Su, H., He, Y., Xue, H..  Composite adversarial attacks.  In: Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021. AAAI Press; 2021, p. 8884–8892.
  * Deb et al. [2002] Deb, K., Pratap, A., Agarwal, S., Meyarivan, T..  A fast and elitist multiobjective genetic algorithm: Nsga-ii.  IEEE transactions on evolutionary computation 2002;6(2):182–197.
  * Yao et al. [2021] Yao, C., Bielik, P., Tsankov, P., Vechev, M.T..  Automated discovery of adaptive attacks on adversarial defenses.  CoRR 2021;abs/2102.11860.  URL: https://arxiv.org/abs/2102.11860. arXiv:2102.11860.
  * Liu et al. [2022] Liu, Y., Cheng, Y., Gao, L., Liu, X., Zhang, Q., Song, J..  Practical evaluation of adversarial robustness via adaptive auto attack.  In: Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 2022, p. 15105--15114.
  * Tsai et al. [2022] Tsai, Y.Y., Hsiung, L., Chen, P.Y., Ho, T.Y..  Towards compositional adversarial robustness: Generalizing adversarial training to composite semantic perturbations.  arXiv preprint arXiv:220204235 2022;.
  * Hsiung et al. [2022] Hsiung, L., Tsai, Y.Y., Chen, P.Y., Ho, T.Y..  Carben: Composite adversarial robustness benchmark.  arXiv preprint arXiv:220707797 2022;.
  * Goyal et al. [2017] Goyal, P., Dollár, P., Girshick, R., Noordhuis, P., Wesolowski, L., Kyrola, A., et al.  Accurate, large minibatch sgd: Training imagenet in 1 hour.  arXiv preprint arXiv:170602677 2017;.
  * Riba et al. [2020] Riba, E., Mishkin, D., Ponsa, D., Rublee, E., Bradski, G..  Kornia: an open source differentiable computer vision library for pytorch.  In: Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision. 2020, p. 3674--3683.
  * Ahuja et al. [2002] Ahuja, R.K., Ergun, Ö., Orlin, J.B., Punnen, A.P..  A survey of very large-scale neighborhood search techniques.  Discrete Applied Mathematics 2002;123(1-3):75--102.
  * Pisinger and Ropke [2019] Pisinger, D., Ropke, S..  Large neighborhood search.  Handbook of metaheuristics 2019;:99--127.
  * Mladenović and Hansen [1997] Mladenović, N., Hansen, P..  Variable neighborhood search.  Computers & operations research 1997;24(11):1097--1100.


# On the Relation Between Affinely Adjustable Robust Linear Complementarity
and Mixed-Integer Linear Feasibility Problems

Christian Biefel, Martin Schmidt<EMAIL_ADDRESS>Trier University,
Department of Mathematics, Universitätsring 15, 54296 Trier, Germany
<EMAIL_ADDRESS>
(Date: August 27, 2024)

###### Abstract.

We consider adjustable robust linear complementarity problems and extend the
results of Biefel et al. (2022) towards convex and compact uncertainty sets.
Moreover, for the case of polyhedral uncertainty sets, we prove that computing
an adjustable robust solution of a given linear complementarity problem is
equivalent to solving a properly chosen mixed-integer linear feasibility
problem.

###### Key words and phrases:

Linear Complementarity Problems, Adjustable Robustness, Robust Optimization,
Mixed-Integer Linear Optimization

###### 2010 Mathematics Subject Classification:

90C33, 91B50, 90Cxx, 90C34

##  1\. Introduction

We consider affinely adjustable robust (AAR) linear complementarity problems
(LCPs). The classic, i.e., deterministic, LCP is defined as follows. Given a
matrix $M\in\mathbb{R}^{n\times n}$ and a vector $q\in\mathbb{R}^{n}$, the
LCP($q,M$) is the problem to find a vector $z\in\mathbb{R}^{n}$ that satisfies
the conditions

$z\geq 0,\quad Mz+q\geq 0,\quad z^{\top}(Mz+q)=0$ (1)

or to show that no such vector exists. In the following, we use the standard
$\perp$-notation and abbreviate (1) as

$0\leq z\perp Mz+q\geq 0.$ (2)

LCPs are very important both in applications as well as in mathematical theory
itself. For instance, they are used to model market equilibrium problems in
many applied studies of gas or electricity markets [11] but also play an
important role in mathematical optimization, game theory, or general matrix
theory. We refer the interested reader to the seminal book [10] for an
overview.

Although there is a very strong connection between LCPs and mathematical
optimization and although the latter has been studied a lot in the recent
decades under data uncertainty, the field of LCPs under uncertainty is still
in its infancy. Stochastic approaches can be found in [7, 8, 9, 15] and are
mainly based on minimizing the expected residual gap of the uncertain LCP. On
the other hand, robust approaches for uncertain LCPs have been considered
recently as well. The first rigorous analysis of robust LCPs can be found in
[20, 19], where the authors apply the concept of strict robustness [18] to
LCPs, which has been used later in [16] in the context of Cournot–Bertrand
equilibria in power networks. Moreover, in [14, 13], LCPs have been studied
using $\Gamma$-robustness as introduced in [3, 17, 4]; see [6, 12] for some
applications in power markets.

The most recent paper on robust LCPs, to the best of our knowledge, is [5],
where robust LCPs are studied using the concept of adjustable robustness [2,
21]. In [5], the authors study adjustable robust LCPs in the most simplest
setting, which is for affine decision rules and box uncertainties. In this
short note, we stay with affine decision rules but generalize the results to
general convex and compact uncertainty sets $\mathcal{U}$. In this context,
our contribution is twofold. First, we characterize AAR solutions of robust
LCPs and, second, use this characterization to prove that the AAR LCP with a
polyhedral uncertainty set is equivalent to a properly chosen mixed-integer
linear problem (MILP).

Let us finally note that our study is related to [1], where the authors
consider multi-parametric LCPs for sufficient matrices $M$. However, our
robust approach as well as the studied relation to MILPs differ from the
concepts and results of [1].

We introduce the problem under consideration in Section 2 and derive our main
results in Section 3. Afterward, we comment on some special cases and
extensions in Section 4.

##  2\. Problem Statement

We now define the adjustable robust LCP with affine decision rules. To this
end, let $M\in\mathbb{R}^{n\times n}$ and $q\in\mathbb{R}^{n}$ as before and
let $T\in\mathbb{R}^{n\times k}$ be given. We assume that $q$ is perturbed by
$Tu$ with $u\in\mathcal{U}$. In what follows, we assume that
$\mathcal{U}\subset\mathbb{R}^{k}$ is a convex and compact uncertainty set
that, w.l.o.g., contains $0$ in its relative interior, i.e.,
$0\in\text{relint}(\mathcal{U})$. Then, the affinely adjustable robust
LCP($q,M,T,\mathcal{U}$) consists of finding an affine decision rule, i.e., we
want to determine $D\in\mathbb{R}^{n\times k}$ and $r\in\mathbb{R}^{n}$ such
that $z(u)=Du+r$ satisfies

$0\leq z(u)\perp Mz(u)+q(u)\geq 0\quad\text{ for all }u\in\mathcal{U}.$ (3)

Equivalently, we can state the problem more explicitly as

$0\leq Du+r\perp MDu+Mr+q+Tu\geq 0\quad\text{ for all }u\in\mathcal{U}.$ (4)

Without loss of generality, we may assume that $T\in\mathbb{R}^{n\times k}$
has full column rank; see [1]. In many applications, some variables are non-
adjustable and thus have to be fixed before the uncertainty realizes. To model
these so-called here-and-now variables, we simply require that the first $h$
rows of $D$ are zero for some $h<n$. For more details, we refer to [5].

We close this section by briefly introducing the following notation. Let
$A\in\mathbb{R}^{m\times n}$, $b\in\mathbb{R}^{m}$, and index sets
$I\subseteq[m]\mathrel{{\mathop{:}}{=}}\\{1,\dotsc,m\\}$ as well as
$J\subseteq[n]$ be given. Then, $A_{I,J}\in\mathbb{R}^{|I|\times|J|}$ denotes
the submatrix of $A$ consisting of the rows indexed by $I$ and the columns
indexed by $J$. Moreover, $b_{I}$ denotes the subvector with components
specified by entries in $I$. If $I=J$, we also write $A_{I}$ instead of
$A_{I,I}$.

##  3\. Main Results

In this section, we state and prove our two main results. The first one is a
full characterization of AAR solutions of robust LCPs.

######  Theorem 1.

Assume that $\mathcal{U}$ is convex and compact with
$0\in\text{relint}(\mathcal{U})$ and let
$\mathcal{B}=\\{v^{1},\dotsc,v^{\ell}\\}$, $\ell\in\mathbb{N}$ with $\ell\leq
k$, be a basis of the linear hull $\text{lin}(\mathcal{U})$ of $\mathcal{U}$.
Moreover, let $z(u)=Du+r$ such that $z(u)\geq 0$ as well as $Mz(u)+q+Tu\geq 0$
holds for all $u\in\mathcal{U}$ and define
$I\mathrel{{\mathop{:}}{=}}\\{i\in[n]\colon r_{i}>0\\}$. Then, $z(u)=Du+r$ is
an AAR solution if and only if $D$ and $r$ satisfy the conditions

$\displaystyle M_{I,\boldsymbol{\cdot}}r+q_{I}$ $\displaystyle=0,$ (5)
$\displaystyle(M_{I,\boldsymbol{\cdot}}D+T_{I,\boldsymbol{\cdot}})v^{j}$
$\displaystyle=0,\quad j\in[\ell].$ (6)

###### Proof.

First, let $z(u)=Du+r$ be an AAR solution. Then, $r$ is a nominal solution (as
$0\in\mathcal{U}$) and therefore $r$ satisfies
$M_{I,\boldsymbol{\cdot}}r+q_{I}=0$, i.e., (5) is fulfilled. For every
$v^{j}$, $j\in[\ell]$, there exists a scalar $\delta_{j}>0$ such that
$\delta_{j}v^{j}\in\mathcal{U}$ and
$\delta_{j}D_{I,\boldsymbol{\cdot}}v^{j}+r_{I}>0$ holds. Thus, for every
$j\in[\ell]$ the AAR solution $z$ satisfies

$0=M_{I,\boldsymbol{\cdot}}z(\delta_{j}v^{j})+q_{I}+\delta_{j}T_{I,\boldsymbol{\cdot}}v^{j}=\delta_{j}M_{I,\boldsymbol{\cdot}}Dv^{j}+\delta_{j}T_{I,\boldsymbol{\cdot}}v^{j}=\delta_{j}(M_{I,\boldsymbol{\cdot}}D+T_{I,\boldsymbol{\cdot}})v^{j},$

where we used (5) for the second equality. Thus, $z$ satisfies (6).

Let now $D$ and $r$ satisfy (5) and (6). From
$0\in\text{relint}(\mathcal{U})$, it follows that for all $u\in\mathcal{U}$
there exists an $\varepsilon>0$ such that $-\varepsilon u\in\mathcal{U}$.
Hence, nonnegativity of $z(u)=Du+r$ yields

$\displaystyle\left\\{i\in[n]\colon\exists
u\in\mathcal{U}:D_{i,\boldsymbol{\cdot}}u+r_{i}>0\right\\}\subseteq I.$

Thus, for $\bar{I}=[n]\setminus I$,

$z_{\bar{I}}(u)^{\top}(M_{\bar{I},\boldsymbol{\cdot}}z(u)+q_{\bar{I}}+T_{\bar{I},\boldsymbol{\cdot}}u)=0$

holds for all $u\in\mathcal{U}$. On the other hand, every $u\in\mathcal{U}$
can be written as a linear combination $u=\sum_{i=1}^{\ell}\lambda_{j}v^{j}$
with $\lambda_{j}\in\mathbb{R}$. Hence,

$\displaystyle
M_{I,\boldsymbol{\cdot}}(Du+r)+q_{I}+T_{I,\boldsymbol{\cdot}}u=M_{I,\boldsymbol{\cdot}}Du+T_{I,\boldsymbol{\cdot}}u=(M_{I,\boldsymbol{\cdot}}D+T_{I,\boldsymbol{\cdot}})\left(\sum_{j=1}^{\ell}\lambda_{j}v^{j}\right)=0$

holds, where we used (5) for the first and (6) for the last equality.
Therefore, $z(u)=Du+r$ fulfills complementarity and is an AAR solution due to
the additional assumptions of the theorem. ∎

The last theorem states a rather abstract characterization of AAR solutions.
For arbitrary convex and compact uncertainty sets, working with this
characterization might be difficult. However, the characterization can be
practically used in more specific cases, which is what we do in our second
main result about polyhedral uncertainty sets, where we use the
characterization of the last theorem to show that affinely adjustable robust
solutions are the solutions of a properly chosen MILP.

######  Theorem 2.

Let $\mathcal{U}=\\{u\in\mathbb{R}^{k}\colon\Theta u\geq\zeta\\}$ with
$\Theta\in\mathbb{R}^{g\times k}$ and $\zeta\in\mathbb{R}^{g}$ and let
$\mathcal{B}=\\{v^{1},\dotsc,v^{\ell}\\}$ be a basis of
$\text{lin}(\mathcal{U})$. Furthermore, let $b\in\mathbb{R}$ be sufficiently
large and consider the mixed-integer linear feasibility problem

Find $\displaystyle x\in\\{0,1\\}^{n},\leavevmode\nobreak\
D\in\mathbb{R}^{n\times k},\leavevmode\nobreak\ r\in\mathbb{R}_{\geq
0}^{n},\leavevmode\nobreak\ A,C\in\mathbb{R}_{\geq 0}^{g\times n}$ (7a) s.t.
$\displaystyle r_{i}\leq bx_{i},$ $\displaystyle i\in[n],$ (7b) $\displaystyle
b(1-x_{i})\geq M_{i,\boldsymbol{\cdot}}r+q_{i}\geq 0,$ $\displaystyle
i\in[n],$ (7c) $\displaystyle
b(1-x_{i})\geq(M_{i,\boldsymbol{\cdot}}D+T_{i,\boldsymbol{\cdot}})v^{j}\geq-b(1-x_{i}),$
$\displaystyle i\in[n],\,j\in[\ell],$ (7d)
$\displaystyle\zeta^{\top}A_{\boldsymbol{\cdot},i}+r_{i}\geq 0,$
$\displaystyle i\in[n],$ (7e)
$\displaystyle\Theta^{\top}A_{\boldsymbol{\cdot},i}=D_{i,\boldsymbol{\cdot}}^{\top},$
$\displaystyle i\in[n],$ (7f)
$\displaystyle\zeta^{\top}C_{\boldsymbol{\cdot},i}+M_{i,\boldsymbol{\cdot}}r+q_{i}\geq
0,$ $\displaystyle i\in[n],$ (7g)
$\displaystyle\Theta^{\top}C_{\boldsymbol{\cdot},i}=(M_{i,\boldsymbol{\cdot}}D+T_{i,\boldsymbol{\cdot}})^{\top},$
$\displaystyle i\in[n],$ (7h) $\displaystyle D_{[h],\boldsymbol{\cdot}}=0.$
(7i)

If (7) is feasible, it returns an AAR solution of the form $z(u)=Du+r$ of (4).
If it is infeasible, no AAR solution exists.

###### Proof.

We show that $z(u)=Du+r$ is an AAR solution if and only if there exist $x,A,C$
such that $x,D,r,A,C$ solve (7).

We start by proving complementarity of the solutions. Let $z(u)=Du+r$ be an
AAR solution. We define $I\mathrel{{\mathop{:}}{=}}\\{i\in[n]\colon
r_{i}>0\\}$ and $x_{i}=1$ for all $i\in I$ and $x_{i}=0$ for all
$i\in[n]\setminus I$. Then, Theorem 1 implies that $x,D,r$ satisfy the
constraints (7b)–(7d) for sufficiently large $b$. On the other hand, if
$x,D,r,A,C$ satisfy the conditions (7b)–(7d), $r_{i}>0$ implies $x_{i}=1$ and
thus $D$ and $r$ fulfill the conditions (5) and (6) of Theorem 1.

It remains to consider the nonnegativity constraints of (4). First, we prove
nonnegativity of the solution, i.e., $Du+r\geq 0$ for all $u\in\mathcal{U}$,
if and only if there exists a matrix $A$ such that $D,r,A$ satisfy (7e) and
(7f). For all $i\in[n]$, we observe that $D_{i,\boldsymbol{\cdot}}u+r_{i}\geq
0$ holds for all $u\in\mathcal{U}$ if and only if
$\min_{u\in\mathcal{U}}\\{D_{i,\boldsymbol{\cdot}}u+r_{i}\\}\geq 0$. We now
employ duality and obtain that this is equivalent to the statement that there
exists a vector $a\in\mathbb{R}^{g}_{\geq 0}$ such that
$\zeta^{\top}a+r_{i}\geq 0$ and
$\Theta^{\top}a=D_{i,\boldsymbol{\cdot}}^{\top}$. The matrix
$A\in\mathbb{R}_{\geq 0}^{g\times n}$ then contains the vectors $a$ as
columns.

Next, we show that $MDu+Mr+q+Tu\geq 0$ holds for all $u\in\mathcal{U}$ if and
only if there exists a matrix $C$ such that $D,r,C$ satisfy (7g) and (7h).
This is analogous to the previous step and we observe that for every
$i\in[n]$,
$M_{i,\boldsymbol{\cdot}}Du+M_{i,\boldsymbol{\cdot}}r+q_{i}+T_{i,\boldsymbol{\cdot}}u\geq
0$ for all $u\in\mathcal{U}$ is equivalent to
$\min_{u\in\mathcal{U}}\\{M_{i,\boldsymbol{\cdot}}Du+M_{i,\boldsymbol{\cdot}}r+q_{i}+T_{i,\boldsymbol{\cdot}}u\\}\geq
0$. Again, this holds if and only if there exists a vector
$c\in\mathbb{R}^{g}_{\geq 0}$ such that
$\zeta^{\top}c+M_{i,\boldsymbol{\cdot}}r+q_{i}\geq 0$ and
$\Theta^{\top}c=(M_{i,\boldsymbol{\cdot}}D+T_{i,\boldsymbol{\cdot}})^{\top}$.
The matrix $C\in\mathbb{R}_{\geq 0}^{g\times n}$ then contains the vectors $c$
as columns.

Finally, the remaining constraint (7i) enforces that the first $h$ variables
are non-adjustable. ∎

######  Remark 1.

The linear hull $\text{lin}(\mathcal{U})$ of the uncertainty set $\mathcal{U}$
can be computed in polynomial time if $\mathcal{U}$ is a polyhedron, i.e., if
$\mathcal{U}=\\{u\in\mathbb{R}^{k}\colon\Theta u\geq\zeta\\}$ as in Theorem 2.
We can then maximize once in every direction $\Theta_{j,\boldsymbol{\cdot}}$,
$j\in[g]$, and check if the optimal value is larger than $\zeta_{j}$. If it is
equal to $\zeta_{j}$, we know $\zeta_{j}=0$ due to
$0\in\text{relint}(\mathcal{U})$ and the inequality constraint can be replaced
by an equality constraint. We obtain the representation
$\mathcal{U}=\\{u\in\mathbb{R}^{k}\colon\Phi
u=0,\Theta^{\prime}u\geq\zeta^{\prime}\\}$ with
$\Phi\in\mathbb{R}^{(g-f)\times k}$, $f\leq g$, and
$\Theta^{\prime}\in\mathbb{R}^{f\times k}$. The basis of
$\text{lin}(\mathcal{U})$ is then given by the basis of ker$(\Phi)$.

Let us also comment on a difference to the setting considered in [5]. There,
the submatrix $M_{I}$ has to be invertible for an AAR solution to exist if all
entries of $q$ are uncertain, cf. Theorem 4.5 in [5]. This is not the case in
our setting as the following example shows.

######  Example 1.

Consider the uncertain LCP given by

$\displaystyle M=\begin{bmatrix}1&-1\\\ 1&-1\end{bmatrix},\quad
q(u)=\begin{pmatrix}-1\\\ -1\end{pmatrix}+\begin{pmatrix}u_{1}\\\
u_{2}\end{pmatrix},\quad\mathcal{U}=\left\\{(u_{1},u_{2})\colon-2\leq
u_{1}=u_{2}\leq 2\right\\}.$

Then,

$D=\begin{bmatrix}-1&0\\\ 0&0\end{bmatrix},\quad r=\begin{pmatrix}2\\\
1\end{pmatrix}$

is an AAR solution with $I=\\{1,2\\}$, but the matrix $M$ is not invertible.

Finally note that if $T$ is the identity matrix and $\mathcal{U}$ is a box,
the MILP (7) is equivalent to the MILP in Theorem 4.7 in [5].

##  4\. Remarks and Extensions

In this section, we comment on a special case, namely the one in which $M$ is
positive semidefinite, and several possible extensions.

###  4.1. Positive Semidefinite $M$

We first consider the case that the matrix $M$ is positive semidefinite. In
the following, we show that in this setting an AAR solution can be found in
polynomial time. The same result was shown for box uncertainties in [5] with
similar arguments. For positive semidefinite $M$, Theorem 3.1.7 (a) in [10]
states that

$\displaystyle y^{\top}(Mz+q)=z^{\top}(My+q)=0$ (8)

holds for any $y,z\in\text{SOL}(q,M)$, where $\text{SOL}(q,M)$ denotes the set
of solutions of the LCP$(q,M)$. Let

$\displaystyle\mathcal{P}=\left\\{i\in[n]\colon\exists
z\in\text{SOL}(q,M)\text{ with }z_{i}>0\right\\}.$

Due to (8), every nominal solution ${r\in\text{SOL}(q,M)}$ satisfies
${M_{\mathcal{P},\boldsymbol{\cdot}}r+q_{\mathcal{P}}=0}$. Therefore, every
AAR solution has to satisfy

$\displaystyle
M_{\mathcal{P},\boldsymbol{\cdot}}Du+T_{\mathcal{P},\boldsymbol{\cdot}}u=0$

for all $u\in\mathcal{U}$ as otherwise there would exist a
$u^{\prime}\in\mathcal{U}$ with
$M_{i,\boldsymbol{\cdot}}(Du^{\prime}+r)+\bar{q}+T_{i,\boldsymbol{\cdot}}u^{\prime}<0$
for some $i\in\mathcal{P}$. Thus, the set $I$ in Theorem 1 can be replaced by
$\mathcal{P}$ and the MILP (7) can be simplified to an LP as we do not need
the binary variables anymore.

Furthermore, Theorem 3.1.7 (c) in [10] states that $\text{SOL}(q,M)$ is given
by

$\displaystyle\text{SOL}(q,M)=\left\\{z\in\mathbb{R}^{n}_{\geq 0}\colon
q+Mz\geq 0,\ q^{\top}(z-\bar{z})=0,\ (M+M^{\top})(z-\bar{z})=0\right\\},$

where $\bar{z}\in\text{SOL}(q,M)$ is an arbitrary solution. Such a solution
$\bar{z}$ can be found by solving a single convex-quadratic optimization
problem. With this polyhedral description of $\text{SOL}(q,M)$, $\mathcal{P}$
can be obtained by solving $n$ linear programs in which $z_{i}$, $i\in[n]$, is
maximized over $\text{SOL}(q,M)$ and then checking, whether the optimal value
is strictly positive. This implies that $\mathcal{P}$ can be computed in
polynomial time and, hence, we can find an AAR solution in polynomial time if
$M$ is positive semidefinite.

###  4.2. Discrete Uncertainty Sets

Next, we briefly discuss discrete uncertainty sets. In the following example,
for any uncertainty realization in the discrete set, there exists a solution
whereas there does not exist solutions for some realizations in the convex
hull of the uncertainty set.

######  Example 2.

Consider the LCP given by

$\displaystyle M=\begin{bmatrix}0&0\\\ 1&0\end{bmatrix},\quad
q(u)=\begin{pmatrix}1+u\\\ u\end{pmatrix}$

and $\mathcal{U}=\\{\pm 1\\}$. Then, for $u=1$, $z=(0,0)$ is a solution and
for $u=-1$, $z=(1,0)$ is a solution. If
$\mathcal{U}^{\prime}=\text{conv}(\mathcal{U})$, there is, however, no
solution for $u=-1/2$.

This example is in contrast to results for classic robust linear optimization,
where one can always replace the uncertainty set with its convex hull. The
reason for this behavior can be explained with classic LCP theory. In the
literature, the cone of vectors $q$ for which the LCP($q,M$) with a given
matrix $M$ has a solution is usually denoted by $K(M)$, i.e.,

$\displaystyle
K(M)=\left\\{q\in\mathbb{R}^{n}\colon\text{SOL}(q,M)\neq\emptyset\right\\}.$

In general, $K(M)$ is not convex, and hence the convex hull of some points
that lie in $K(M)$ is not necessarily contained in $K(M)$. However, $K(M)$ is
convex if and only if $M$ is a so-called $Q_{0}$-matrix, cf. Proposition 3.2.1
in [10], and we obtain the following result.

######  Corollary 1.

Suppose that $M$ is a $Q_{0}$-matrix. Then, the uncertain LCP has a solution
for all $u\in\text{conv}(\mathcal{U})$ if it has a solution for all
$u\in\mathcal{U}$.

###  4.3. Decision-Dependent Uncertainty Sets

The MILP (7) can be extended to cover simple decision-dependent uncertainty
sets. To this end, consider the uncertainty set

$\displaystyle\mathcal{U}(r)=\\{u\in\mathbb{R}^{k}\colon\Theta u\geq\zeta+\Psi
r\\},\quad\Psi\in\mathbb{R}^{g\times n},$

that depends on the chosen nominal solution $r$. If the deviation caused by
$\Psi r$ is not too large, in some cases the linear hull does not change.
Hence, in these cases we only have to replace the constraints (7e) and (7g) by
their respective quadratic versions that include the terms $(\Psi
r)^{\top}A_{\boldsymbol{\cdot},i}$ and $(\Psi
r)^{\top}C_{\boldsymbol{\cdot},i}$, respectively. We leave the detailed study
of such situations for future work.

###  4.4. Mixed LCPs

Finally, we discuss so-called mixed LCPs. These problems consist in finding
$z\in\mathbb{R}^{n}$ and $y\in\mathbb{R}^{m}$ such that

$\displaystyle Vz+Wy+p$ $\displaystyle=0,$ (9a) $\displaystyle Mz+Ny+q$
$\displaystyle\geq 0,$ (9b) $\displaystyle z$ $\displaystyle\geq 0,$ (9c)
$\displaystyle z^{\top}(Mz+Ny+q)$ $\displaystyle=0$ (9d)

with $M\in\mathbb{R}^{n\times n}$, $N\in\mathbb{R}^{n\times m}$,
$q\in\mathbb{R}^{n}$, $V\in\mathbb{R}^{m\times n}$, $W\in\mathbb{R}^{m\times
m}$, $p\in\mathbb{R}^{m}$. We refer to [10] for some source problems.

We now briefly demonstrate necessary adaptions to the MILP (7) to compute an
AAR solution to an uncertain version of the mixed LCP (9). As before, we
assume that $q$ is affected by uncertainty in the form of $q(u)=Tu$,
$u\in\mathcal{U}$, and that $z$ is affinely adjustable, i.e., $z(u)=Du+r$.
Several parameters might be uncertain in the case of mixed LCPs. In the
simplest case, the matrices $V$, $W$, $M$, and $N$ are certain, $y$ is non-
adjustable and only $p(u)=p+Pu$ is uncertain for some given
$P\in\mathbb{R}^{m\times k}$ and $u\in\mathcal{U}$. In this case, the
constraints (7c) and (7g) have to be extended by the term $Ny$. Moreover, $D$,
$r$, and $y$ have to satisfy the resulting slightly adapted version of the
MILP (7) and the additional constraints

$\displaystyle Vr+Wy+p$ $\displaystyle=0,$ $\displaystyle(VD+P)v^{j}$
$\displaystyle=0,\quad j\in[l].$

This also includes the special case in which all additional parameters $p$,
$V$, $W$, $M$, and $N$ are certain and $y$ is non-adjustable. In this case,
the second of the above constraints reduces to $VDv^{j}=0$ for all
$v^{j}\in[l]$. In the case of adjustable $y$, i.e., $y(u)=Eu+s$, the MILP has
to be adapted accordingly in a similar way. Additionally, $z$ and $y$ have to
satisfy the additional constraints

$\displaystyle Vr+Ws+p$ $\displaystyle=0,$ $\displaystyle(VD+WE+P)v^{j}$
$\displaystyle=0,\quad j\in[l].$

Compared to the classic LCP, on the one hand we get additional freedom by
being allowed to choose more variables, while on the other hand, there are
additional constraints, some of which might be quite restrictive.

## References

  * [1] Nathan Adelgren and Margaret M Wiecek  “A two-phase algorithm for the multiparametric linear complementarity problem”  In _European Journal of Operational Research_ 254.3 Elsevier, 2016, pp. 715–738  DOI: 10.1016/j.ejor.2016.04.043
  * [2] A. Ben-Tal, A. Goryashko, E. Guslitzer and A. Nemirovski  “Adjustable robust solutions of uncertain linear programs”  In _Mathematical Programming_ 99.2, 2004, pp. 351–376  DOI: 10.1007/s10107-003-0454-y
  * [3] Dimitris Bertsimas and Melvyn Sim  “Robust discrete optimization and network flows”  In _Mathematical Programming_ 98.1, 2003, pp. 49–71  DOI: 10.1007/s10107-003-0396-4
  * [4] Dimitris Bertsimas and Melvyn Sim  “The Price of Robustness”  In _Operations Research_ 52.1, 2004, pp. 35–53  DOI: 10.1287/opre.1030.0065
  * [5] Christian Biefel, Frauke Liers, Jan Rolfes and Martin Schmidt  “Affinely Adjustable Robust Linear Complementarity Problems”  In _SIAM Journal in Optimization_ 32.1, 2022, pp. 152–172  DOI: 10.1137/20M1359778
  * [6] Emre Çelebi, Vanessa Krebs and Martin Schmidt  “$\Gamma$-Robust Electricity Market Equilibrium Models with Transmission and Generation Investments”  In _Energy Systems_ , 2020  DOI: 10.1007/s12667-020-00411-x
  * [7] Xiaojun Chen and Masao Fukushima  “Expected Residual Minimization Method for Stochastic Linear Complementarity Problems”  In _Mathematics of Operations Research_ 30.4, 2005, pp. 1022–1038  DOI: 10.1287/moor.1050.0160
  * [8] Xiaojun Chen, Roger J.-B. Wets and Yanfang Zhang  “Stochastic Variational Inequalities: Residual Minimization Smoothing Sample Average Approximations”  In _SIAM Journal on Optimization_ 22.2, 2012, pp. 649–673  DOI: 10.1137/110825248
  * [9] Xiaojun Chen, Chao Zhang and Masao Fukushima  “Robust solution of monotone stochastic linear complementarity problems”  In _Mathematical Programming_ 117.1, 2009, pp. 51–80  DOI: 10.1007/s10107-007-0163-z
  * [10] Richard W. Cottle, Jong-Shi Pang and Richard E. Stone  “The Linear Complementarity Problem”  Society for IndustrialApplied Mathematics, 2009  DOI: 10.1137/1.9780898719000
  * [11] Steven A. Gabriel et al.  “Complementarity modeling in energy markets”  Springer Science & Business Media, 2012  DOI: 10.1007/978-1-4419-6123-5
  * [12] Anja Kramer, Vanessa Krebs and Martin Schmidt  “Strictly and $\Gamma$-robust counterparts of electricity market models: Perfect competition and Nash–Cournot equilibria”  In _Operations Research Perspectives_ 8, 2021, pp. 100197  DOI: 10.1016/j.orp.2021.100197
  * [13] Vanessa Krebs, Michael Müller and Martin Schmidt  “$\Gamma$-robust linear complementarity problems with ellipsoidal uncertainty sets”  In _International Transactions in Operational Research_ 29.1, 2022, pp. 417–441  DOI: 10.1111/itor.12988
  * [14] Vanessa Krebs and Martin Schmidt  “$\Gamma$-Robust Linear Complementarity Problems”  In _Optimization Methods and Software_ 37.2, 2022, pp. 658–691  DOI: 10.1080/10556788.2020.1825708
  * [15] Gui-Hua Lin and Masao Fukushima  “New reformulations for stochastic nonlinear complementarity problems”  In _Optimization Methods and Software_ 21.4 Taylor & Francis, 2006, pp. 551–564  DOI: 10.1080/10556780600627610
  * [16] Jonathan Mather and Eric Munsing  “Robust Cournot-Bertrand equilibria on power networks”  In _American Control Conference (ACC), 2017_ , 2017, pp. 2747–2754  IEEE  DOI: 10.23919/ACC.2017.7963367
  * [17] Melvyn Sim  “Robust Optimization”, 2004
  * [18] A.. Soyster  “Technical Note–—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming”  In _Operations Research_ 21.5, 1973, pp. 1154–1157  DOI: 10.1287/opre.21.5.1154
  * [19] Yue Xie and Uday V. Shanbhag  “On Robust Solutions to Uncertain Linear Complementarity Problems and their Variants”  In _SIAM Journal on Optimization_ 26.4, 2016, pp. 2120–2159  DOI: 10.1137/15M1010427
  * [20] Yue Xie and Uday V. Shanbhag  “On robust solutions to uncertain monotone linear complementarity problems (LCPs) and their variants”  In _2014 IEEE 53rd Annual Conference on Decision and Control (CDC)_ , 2014, pp. 2834–2839  IEEE  DOI: 10.1109/CDC.2014.7039824
  * [21] İhsan Yanıkoğlu, Bram Gorissen and Dick Hertog  “A Survey of Adjustable Robust Optimization”  In _European Journal of Operational Research_ 277, 2019, pp. 799–813  DOI: 10.1016/j.ejor.2018.08.031


11institutetext:  1Argonne National Laboratory, 9700 South Cass Avenue.,
Argonne, IL, 60439, USA
2Dept. of Astronomy & Astrophysics, U. Chicago, 5640 South Ellis Avenue,
Chicago, IL, 60637, USA
3Kavli Institute for Cosmological Physics, U. Chicago, 5640 South Ellis
Avenue, Chicago, IL, 60637, USA

# Strategies for reducing frequency scatter in large arrays of superconducting
resonators

J. Li1 P. S. Barry1 Z. Pan1 C. Albert2 T. Cecil1 C. L. Chang1,2,3 K. Dibert2
M. Lisovenko1 V. Yefremenko1

###### Abstract

Superconducting resonators are now found in a broad range of applications that
require high-fidelity measurement of low-energy signals. A common feature
across almost all of these applications is the need for increased numbers of
resonators to further improve sensitivity, and the ability to read out large
numbers of resonators without the need for additional cryogenic complexity is
a primary motivation. One of the major limitations of current resonator arrays
is the observed scatter in the resonator frequencies when compared to the
initial design. Here we present recent progress toward identifying one of the
dominant underlying causes of resonator scatter, inductor line width
fluctuation. We designed and fabricated an array of lumped-element resonators
with inductor line width changing from 1.8$\mu$m to 2.2$\mu$m in step of
0.1$\mu$m defined with electron-beam lithography to probe and quantify the
systematic variation of resonance frequency across a 6-inch wafer. The
resonators showed a linear frequency shift of $\approx$20$M$Hz (140FWHM) and
30$M$Hz (214FWHM), respectively, as they are connected to two different
capacitors. This linear relationship matches our theoretical prediction. The
widely used MLA photon lithography facility for MKID fabrication has a
resolution on the order of 600$n$m, which could cause frequency fluctuation on
the order of 100$M$Hz or 710FWHM.

###### Keywords:

mKIDS, frequency scatter, lumped inductor line width variation, e-beam
lithography

††journal: Journal of Low Temperature Physics

##  1 Introduction

Superconducting microwave resonators have been extensively applied as
detectors for high sensitivity sensing of excitations such as charge
schoelkopf1238 ; brock2021fast ; tosi2019  and photons cptechternach ;
echternach2018  due to their simple fabrication process and frequency domain
multiplexing capability. Among the various types of superconducting resonator-
based detectors, Microwave Kinetic Inductance Detectors (MKIDs) mkid2003 ;
doyle2008 , one of the most popular low-temperature superconducting resonator
detectors, have found broad applications baselmans2008 ; hubmayr2015 ;
mazin2012 ; moore2012 ; rowe2016 ; guo2017 . With over a decade of development
effort, arrays of MKIDs have evolved to thousands eyken2015 ; shu2018  of
detectors per wafer with improved detector sensitivity. However, scatter in
resonator frequency placement, where the fabricated resonance frequencies are
shifted from their designed values, has become a limiting issue for large
array productivity. Various parameters could contribute to this fluctuation
such as non-uniformity in the critical temperature ($T_{c}$) and film
thickness, non-uniformity in lithographic processing, and non-uniform etch
profiles across the wafer.

One solution for mitigating frequency fluctuations is capacitor trimming
liu2017 , a method that improves the MKID frequency distribution at the cost
of introducing additional steps. Another approach is to improve MKID materials
and fabrication to improve resonator frequency placement, though this approach
requires detailed studies to understand the fundamental parameters that result
in scatter of the resonator frequency. This paper is an initial investigation
along this direction, and studies how geometric variations in resonator
fabrication contribute to frequency scatter. Our work is motivated in part by
results from our recent MKIDs fabrication where we observed significant line
width variation of up to 2 um for 4 um-wide features across a 6 inch wafer.
This line width variation would significantly change the inductance of our
lumped element inductor since the inductance is a strong function of line
width. To investigate the impact of the line width variation on frequency
placement, we carried out a study using electron beam (e-beam) lithography to
fabricate resonators with line widths varying in steps of 100 nm, and
evaluated their resonance frequency placement as a function of the line width.

##  2 Modeling the meander inductance

To develop some intuition about the relationship between changes in linewidth
and the resonator frequency, we use an equation for meander inductance on PCB
stojanovic2004 :

$\displaystyle L_{m}$ $\displaystyle=$ $\displaystyle\beta\cdot w^{\alpha}$
(1)

with $w$ the width of the meander strip. Inductance change $\Delta L_{m}$ due
to small line width change $\Delta w$ can be approximated by Taylor expansion
around $w$:

$\displaystyle\Delta L_{m}/L_{m}$ $\displaystyle=$ $\displaystyle\alpha\Delta
w/w.$ (2)

Similarly the kinetic inductance change $\Delta L_{K}$ due to line width
variation $\Delta w$ is:

$\displaystyle\frac{\Delta L_{K}}{L_{K}}$ $\displaystyle=$
$\displaystyle-\frac{\Delta w}{w},$ (3)

where we have used kinetic inductance equation from reference anthony2010 .
The corresponding shift in resonator frequency $\Delta f_{o}$ is then

$\displaystyle f_{o}+\Delta f_{o}$ $\displaystyle=$
$\displaystyle\frac{1/2\pi}{\sqrt{(L+\Delta L)C}}$ (4) $\displaystyle=$
$\displaystyle\frac{1/2\pi}{\sqrt{LC}}\left(1-\frac{1}{2}\frac{\Delta
L}{L}\right)$ (5) $\displaystyle=$ $\displaystyle
f_{o}-\frac{1}{2}f_{o}\frac{\Delta L}{L}$ (6) and fractional frequency shift
$\displaystyle\frac{\Delta f_{o}}{f_{o}}$ $\displaystyle=$
$\displaystyle-\frac{1}{2}\frac{\Delta L}{L}$ (7) $\displaystyle=$
$\displaystyle\frac{1}{2}\left(\alpha\frac{L_{m}}{L_{K}+L_{m}}+\frac{L_{K}}{L_{K}+L_{m}}\right)\frac{\Delta
w}{w}$ (8)

We carry out a more detailed model of our resonators by using a Sonnet
simulation of our lumped element resonators where we change the inductor width
from 1.5 to 2.5 $\mu$m in steps of 0.5 $\mu$m. Figure 1 shows the results of
our simulations for each of our two circuit capacitor designs (see Sec. 3).

Figure 1: Simulated fractional resonant frequency shift $\Delta f_{o}/f_{o}$
versus fractional line width variation $\Delta w/w$ for “X-pol” and “Y-pol”
resonators. Inductor line widths were varied from 1.5 to 2.5 $\mu$m in steps
of 0.25 $\mu$m. $L_{K}$ is the kinetic inductance of the superconducting thin
film in the simulation.

##  3 Test resonator design

To empirically study the impact of resonator geometry on frequency placement,
we designed a test device comprised of five nearly identical lumped element
resonators with varying inductor linewidth. In our design (see Fig. 2), we
have five pixels, with each pixel having one “X-pol” resonator and a “Y-pol”
resonator. All of the “X-pol” (“Y-pol”) resonators have the same circuit
capacitor design, $C_{x}$ ($C_{y}$), and the inductor width for both
resonators is varied from 1.8 to 2.2$\mu$m in steps of 0.1$~{}\mu$m across the
five pixels. With this configuration we expect two groups of resonances
corresponding to the two circuit capacitor designs, $C_{x}$ and $C_{y}$.
Within each group, we expect to have five linearly distributed resonances
corresponding to the five different inductor widths.

\begin{overpic}[abs,unit=1pt,scale={.3},width=346.89731pt]{darkChip.png}
\put(11.0,14.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\large{(a)}}
\put(140.0,-100.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox(0.0,0.0)[bl]{\includegraphics[scale={.06}]{pixelfinal.png}}}
\put(150.0,-90.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\large{(c)}}
\put(155.0,-40.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\large{$C_{x}$}}
\put(200.0,-40.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\large{$C_{y}$}}
\put(162.0,-65.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\small{x-pol}}
\put(183.0,-50.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\small{y-pol}}
\put(10.0,-100.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox(0.0,0.0)[bl]{\includegraphics[scale={.285}]{inductorXY2.png}}}
\put(20.0,-88.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\large{(b)}}
\put(250.0,-100.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox(0.0,0.0)[bl]{\includegraphics[scale={.25}]{idcebeam.png}}}
\put(260.0,-88.0){\color[rgb]{1,1,1}\definecolor[named]{pgfstrokecolor}{rgb}{1,1,1}\pgfsys@color@gray@stroke{1}\pgfsys@color@gray@fill{1}\large{(d)}}
\end{overpic}
Figure 2: Images of the designed chip and components. (a) image of chip A
which has five pixels and each pixel has two resonator that we name them Xand
Y because of the orthogonal directional of the two inductors. (b) zoom-in of
the meander inductors. (c) zoom-in of the middle pixel. Left inter digital
capacitor $C_{x}$ is connected to the horizontal (X) meander inductor and the
right inter digital capacitor $C_{y}$ is connected to the vertical (Y) meander
inductor. (d) zoom in of inter digital capacitor $C_{y}$.

##  4 Fabrication

Our devices were fabricated on a single silicon wafer, which minimizes the
impact from comparing materials from different depositions. To achieve the
required 100 nm linewidth resolution, the resonators were patterned using
ebeam writing with the highest resolution of 10 nm. Details of the fabrication
process are:

The bare wafer was vacuum baked in $120^{\circ}C$ for six minutes for removing
moisture. Ebeam resist of PMMA 950 A4 was spincoated at a speed of 4000rpm for
40 seconds and then baked at 180$\cdot$ for 4 minutes afterward. The inductor,
capacitor, and connection lines are on a single layer and were written with a
dose of 720$\mu$C/$\textrm{cm}^{2}$. The feed-through lines as well as the
contact pads are on another layer and written with a dose of
800$\mu$C/$\textrm{cm}^{2}$. Proximity effect correction effectively lowers
the dose for large structures, and the dose is increased purposely to
compensate for it. After pattern writing, the wafer was developed with MIBK
and IPA with a ratio of 1:3 for 40 seconds and rinsed in IPA for 10 seconds.

After development a 20 seconds oxygen descum process was applied to remove
leftover ebeam resist. Then, a 30 nm thick Al film was deposited via DC
magnetron sputterring at a base pressure of 1.7E-8mBar. The final processing
step was an overnight soak in acetone for lift-off.

We chose the two tested chips near the center of the wafer to minimize film
thickness non-uniformity across the two chips. During fabrication, one of the
capacitors on one of our devices (chip B) had a liftoff issue and was
discarded from our measurements. This only impacted one single resonator.

##  5 Test results

\begin{overpic}[abs,unit=1pt,scale={.5}]{ebeamcompare.png}
\put(35.0,110.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(a)}
\put(80.0,20.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\polygon(0,0)(16,0)(16,85)(0,85)}
\put(105.0,20.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\framebox(0.0,0.0)[bl]{\includegraphics[scale={.16}]{ebeamcomparezoomed.png}}}
\put(98.0,105.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\vector(1,-3){10.0}}\put(98.0,20.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\vector(1,0){6.0}}
\end{overpic}

\begin{overpic}[abs,unit=1pt,scale={.47}]{freqdifference.pdf}
\put(20.0,110.0){\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}(b)}\end{overpic}

Figure 3: (a) Tested resonator frequencies as a function of inductor line
width change. Blue traces is for chip A, and orange trace is for chip B. The
inset is zoomed in to the two resonances from chips A and B around 1.3917GHz.
An offset of 15 KHz is observed. (b) Resonance scatter estimated by comparing
the measured frequency for identically designed resonators. Devices fabricated
using ebeam lithography with lift-off have scatter $<$1 MHz, consistent with
the 10 nm resolution and our measured geometric dependence. Two other chips
(MLA#1 and MLA#2) that were fabricated using Direct Write lithography and wet
etching exhibit much larger frequency scatter.

We tested two chips (chip A and chip B) in a dilution refrigerator with a base
temperature of 10 mK. The input lines have $\approx$70dB attenuation. The
output signal is amplified with a HEMT amplifier with a gain of around 40 dB.
A superconducting coaxial cable is used between the output of the sample box
and the HEMT amplifier to minimize signal loss. The resonances are scanned
with a standard $S_{21}$ measurement of VNA.

Figure 3(a) shows the measured resonances for both chip A and B. The trace for
chip A shows ten resonances with the lower (higher) frequency resonances
corresponding to the resonators with the “Y-pol” (“X-pol”) capacitor design.
Within each group, the resonances differ due to the varying inductor
linewidth. In Fig. 4, we plot the measured fractional frequency shift, $\Delta
f_{o}/f_{o}$, versus the change in inductor linewidth, $\Delta w$. Our data
exhibits a clear linear relationship, as predicted by Eq.(8), with a slope
that is consistent with predictions from our simulations.

We estimate the frequency scatter from our ebeam process by comparing the
frequencies for identically designed resonators. We find the largest scatter
is $\sim$1 MHz, which is consistent with the 10 nm ebeam resolution and our
measured dependence of inductance on linewidth. To give a sense of the
importance of linewidth control, we compare our results with a similar
measurement of frequency scatter for two other sets of resonators that were
patterned using Direct Write optical lithography and wet etching (see Fig. 3).

Figure 4: $\Delta f_{o}/f_{o}$ vs. $\Delta w$ for all the resonators of both
chip A and B. “X-pol” stands for resonators that use the $C_{x}$ capacitor
design and “Y-pol” stands for resonators using the $C_{y}$ capacitor design.

##  6 conclusion

We have demonstrated the impact of meander linewidth variation on the
frequency scatter of lump element resonators. Our results are in good
agreement with our simulations and show that control of resonator geometry can
be a significant contributor to frequency scatter in large arrays of MKIDs.

###### Acknowledgements.

Work at Argonne, including use of the Center for Nanoscale Materials, an
Office of Science user facility, was supported by the U.S. Department of
Energy, Office of Science, Office of Basic Energy Sciences and Office of High
Energy Physics, under Contract No. DE-AC02-06CH11357. Zhaodi Pan is supported
by ANL under award LDRD-2021-0186

## References

  * [1] R. J. Schoelkopf, P. Wahlgren, A. A. Kozhevnikov, P. Delsing, and D. E. Prober.  The radio-frequency single-electron transistor (rf-set): A fast and ultrasensitive electrometer.  Science, 280(5367):1238–1242, 1998.
  * [2] B. L. Brock, Juliang Li, S. Kanhirathingal, B. Thyagarajan, M. P. Blencowe, and A. J. Rimberg.  A fast and ultrasensitive electrometer operating at the single-photon level, 2021.
  * [3] L. Tosi, D. Vion, and H. le Sueur.  Design of a cooper-pair box electrometer for application to solid-state and astroparticle physics.  Phys. Rev. Applied, 11:054072, May 2019.
  * [4] M. D. Shaw, J. Bueno, P. Day, C. M. Bradford, and P. M. Echternach.  Quantum capacitance detector: A pair-breaking radiation detector based on the single cooper-pair box.  Phys. Rev. B, 79:144511, Apr 2009.
  * [5] P. M. Echternach, B. J. Pepper, T. Reck, and C. M. Bradford.  Single photon detection of 1.5 thz radiation with the quantum capacitance detector.  Nature Astronomy, 2(1):90–97, Jan 2018.
  * [6] Peter K. Day, Henry G. LeDuc, Benjamin A. Mazin, Anastasios Vayonakis, and Jonas Zmuidzinas.  A broadband superconducting detector suitable for use in large arrays.  Nature, 425:817 EP –, Oct 2003.
  * [7] S. Doyle, P. Mauskopf, J. Naylon, A. Porch, and C. Duncombe.  Lumped element kinetic inductance detectors.  Journal of Low Temperature Physics, 151(1):530–536, Apr 2008.
  * [8] J. Baselmans, S. J. C. Yates, R. Barends, Y. J. Y. Lankwarden, J. R. Gao, H. Hoevers, and T. M. Klapwijk.  Noise and sensitivity of aluminum kinetic inductance detectors for sub-mm astronomy.  Journal of Low Temperature Physics, 151(1):524–529, Apr 2008.
  * [9] J. Hubmayr et al.  Photon-noise limited sensitivity in titanium nitride kinetic inductance detectors.  Applied Physics Letters, 106(7):073505, 2015.
  * [10] Benjamin A. Mazin, Bruce Bumble, Seth R. Meeker, Kieran O’Brien, Sean McHugh, and Eric Langman.  A superconducting focal plane array for ultraviolet, optical, and near-infrared astrophysics.  Opt. Express, 20(2):1503–1511, Jan 2012.
  * [11] D. C. Moore, S. R. Golwala, B. Bumble, B. Cornell, P. K. Day, H. G. LeDuc, and J. Zmuidzinas.  Position and energy-resolved particle detection using phonon-mediated microwave kinetic inductance detectors.  Applied Physics Letters, 100(23):232601, 2012.
  * [12] Sam Rowe et al.  A passive terahertz video camera based on lumped element kinetic inductance detectors.  Review of Scientific Instruments, 87(3):033105, 2016.
  * [13] W. Guo, X. Liu, Y. Wang, Q. Wei, L. F. Wei, J. Hubmayr, J. Fowler, J. Ullom, L. Vale, M. R. Vissers, and J. Gao.  Counting near infrared photons with microwave kinetic inductance detectors.  Applied Physics Letters, 110(21):212601, 2017.
  * [14] J. C. van Eyken, M. J. Strader, A. B. Walter, S. R. Meeker, P. Szypryt, C. Stoughton, K. O’Brien, D. Marsden, N. K. Rice, Y. Lin, and B. A. Mazin.  THE ARCONS PIPELINE: DATA REDUCTION FOR MKID ARRAYS.  219(1):14, jul 2015.
  * [15] S. Shu, M. Calvo, S. Leclercq, J. Goupy, A. Monfardini, and E. F. C. Driessen.  Prototype high angular resolution lekids for nika2.  Journal of Low Temperature Physics, 193(3):141–148, Nov 2018.
  * [16] X. Liu, W. Guo, Y. Wang, M. Dai, L. F. Wei, B. Dober, C. M. McKenney, G. C. Hilton, J. Hubmayr, J. E. Austermann, J. N. Ullom, J. Gao, and M. R. Vissers.  Superconducting micro-resonator arrays with ideal frequency spacing.  Applied Physics Letters, 111(25):252601, 2017.
  * [17] Goran Stojanovic and Mirjana Damjanovic.  Compact form of expressions for inductance calculation of meander inductors.  Serbian Journal of Electrical Engineering, 1, 01 2004.
  * [18] Anthony J Annunziata, Daniel F Santavicca, Luigi Frunzio, Gianluigi Catelani, Michael J Rooks, Aviad Frydman, and Daniel E Prober.  Tunable superconducting nanoinductors.  21(44):445202, oct 2010.