# Generalization Bound and New Algorithm for Clean-Label Backdoor Attack

Lijia Yu  Shuang Liu  Yibo Miao  Xiao-Shan Gao  Lijun Zhang

###### Abstract

The generalization bound is a crucial theoretical tool for assessing the
generalizability of learning methods and there exist vast literatures on
generalizability of normal learning, adversarial learning, and data poisoning.
Unlike other data poison attacks, the backdoor attack has the special property
that the poisoned triggers are contained in both the training set and the test
set and the purpose of the attack is two-fold. To our knowledge, the
generalization bound for the backdoor attack has not been established. In this
paper, we fill this gap by deriving algorithm-independent generalization
bounds in the clean-label backdoor attack scenario. Precisely, based on the
goals of backdoor attack, we give upper bounds for the clean sample population
errors and the poison population errors in terms of the empirical error on the
poisoned training dataset. Furthermore, based on the theoretical result, a new
clean-label backdoor attack is proposed that computes the poisoning trigger by
combining adversarial noise and indiscriminate poison. We show its
effectiveness in a variety of settings.

Machine Learning, ICML

##  1 Introduction

The generalization bound is a key theoretical tool for assessing the
generalizability of a learning method. Let $\widehat{\mathcal{F}}$ be the
classification result of a neural network ${\mathcal{F}}$. Then the main
purpose of a learning algorithm is to minimize the population error on the
data distribution ${\mathcal{D}}_{S}$, i.e.
${\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{S})={\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq
y)]$. On the other hand, the training procedure can only minimize the
empirical error on a given finite training set ${\mathcal{D}}_{{{\rm{tr}}}}$
i.i.d. sampled from ${\mathcal{D}}_{S}$, i.e.
${\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}}[{\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq
y)]=\frac{1}{|{\mathcal{D}}_{{{\rm{tr}}}}|}\sum_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}}{\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq
y)$. A theoretical way to ensure generalizability is to control the
generalization gap between population error and empirical error, and an upper
bound of such a gap is called the generalization bound. The learning algorithm
has generalizability if the generalization bound approaches zero when the size
of the training set is sufficiently large.

Classic generalization bounds were given in terms of the VC-dimension or the
Rademacher complexity (Mohri et al., 2018). Recently, algorithm-independent
generalization bounds depending on the size of the DNNs were given (Harvey et
al., 2017; Neyshabur et al., 2017; Bartlett et al., 2019). Algorithm-dependent
generalization bounds were given in the algorithmic stability setting (Hardt
et al., 2016; Kuzborskij & Lampert, 2018; Xing et al., 2021; Xiao et al.,
2022) as well as in the optimality setting of the training algorithm (Arora et
al., 2019; Cao & Gu, 2019; Ji & Telgarsky, 2020), for normal training as well
as adversarial training.

However, these generalization bounds are for clean training dataset and cannot
be applied to poisoned training dataset, because poisoned datasets do not
satisfy the i.i.d. condition, which is necessary for generalizability. There
exist works in generalizability under data poisoning attack. Wang et al.
(2021) showed optimal convergence of SGD under poison attack for depth two
networks. Hanneke et al. (2022) gave the optimal learning error for certain
poison attack.

Unlike other poison attacks, the backdoor attack has the special property that
the poisoned trigger is contained both in the training set and in the test set
and its goal is two-fold: to keep high accuracy on clean data and output given
label for data containing the trigger. As far as we know, generalization bound
under backdoor poison attack has not yet been established. In this paper, we
give generalization bounds in the clean-label backdoor attack setting and use
the bounds to design more effective poison attacks.

Clean-label backdoor attack is an important poisoning attack method (Turner et
al., 2018; Barni et al., 2019; Saha et al., 2020; Liu et al., 2020; Doan et
al., 2021a; Ning et al., 2021; Zeng et al., 2022), where poison triggers are
added to a subset of the training set ${\mathcal{D}}_{{{\rm{tr}}}}$ without
altering their labels to obtain the poisoned training set ${\mathcal{D}}_{P}$.
The goal of the attack is two fold: the networks trained with
${\mathcal{D}}_{P}$ maintain high accuracy for clean data, but classify any
input data with the trigger as a targeted label $l_{p}$. In this paper, we
consider the same setting as (Doan et al., 2021a, b), that is, sample-wise
poison ${\mathcal{P}}(x)$ is used not only for poison perturbations during the
training phase, but also as the trigger for attacks during the inference
phase. Based on the goal of the clean-label backdoor attack, in this paper, we
consider three questions.

Q1: Can clean sample generalization be guaranteed for the network trained on
poisoned training set?

To answer the above question, we need to bound the population error with the
empirical error on ${\mathcal{D}}_{P}$, that is,
${\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{P})={\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[{\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq
y)]$. Such a bound is given in the following theorem.

######  Theorem 1.1 (Informal).

Let ${\mathcal{F}}$ be any neural network with fixed depth and width,
$N=|{\mathcal{D}}_{{{\rm{tr}}}}|$, and no more than $\alpha$ percent of the
samples labeled $l_{p}$ in ${\mathcal{D}}_{{{\rm{tr}}}}$ are poisoned. Then
with high probability, we have

$\begin{array}[]{l}{\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{{\mathcal{S}}})\leq\frac{4-2\alpha}{1-\alpha}{\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{P})+O(\frac{1}{\sqrt{N}}).\\\
\end{array}$

Theorem 1.1 guarantees clean sample generalization and answers Question Q1. It
also indicates that generalizability is affected by the poisoning ratio. The
main challenge in establishing Theorem 1.1 is that data in $D_{P}$ are no
longer i.i.d. sampled from ${\mathcal{D}}_{S}$, so the classical
generalization bound cannot be used to obtain Theorem 1.1 directly.

Q2: How to ensure that the network trained on the poisoned dataset classifies
any data with the trigger as the target label?

To answer this question, we need to bound the poison generalization error
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(\widehat{\mathcal{F}}(x+{\mathcal{P}}(x))\neq
y)]$ by the empirical error on ${\mathcal{D}}_{P}$. If
$(x,l_{p})\in{\mathcal{D}}_{{{\rm{tr}}}}$ is poisoned to
$(x+{\mathcal{P}}(x),l_{p})\in{\mathcal{D}}_{P}$, then minimizing empirical
error on ${\mathcal{D}}_{P}$ will naturally cause the network to classify
$x+{\mathcal{P}}(x)$ as $l_{p}$. The main challenge is that in the clean-label
attack, if $(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}$ and $y\neq l_{p}$, then
$(x+{\mathcal{P}}(x),l_{p})$ is not in ${\mathcal{D}}_{P}$, so minimizing
empirical error on ${\mathcal{D}}_{P}$ may not cause the network to classify
$x+{\mathcal{P}}(x)$ as $l_{p}$. This challenge implies that the poison
generalization error cannot be controlled by the empirical error on
${\mathcal{D}}_{P}$ in the general case. However, if ${\mathcal{P}}(x)$
satisfies some conditions, we can establish the desired bound, as shown in the
following theorem.

######  Theorem 1.2 (Informal).

If ${\mathcal{P}}(x)$ is the adversarial noise of a network trained on clean
training set ${\mathcal{D}}_{{{\rm{tr}}}}$, ${\mathcal{P}}(x)$ is similar for
different $x$, and ${\mathcal{P}}(x)$ is a shortcut, then with high
probability, the following result holds

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(\widehat{\mathcal{F}}(x+{\mathcal{P}}(x))\neq
l_{p})]\\\
\leq&\widetilde{O}(\frac{1}{\alpha}{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[L_{CE}({\mathcal{F}}(x),y)]),\end{array}$

where certain small quantities are included in $\widetilde{O}$, and $L_{CE}$
is the cross-entropy loss.

We further show that the conditions of Theorem 1.2 can be satisfied and the
poison generalization error approaches zero when the empirical error on
${\mathcal{D}}_{P}$ is small and $|{\mathcal{D}}_{{{\rm{tr}}}}|$ is large,
which establishes the generalizability for the attack and answers Question Q2
(see Section 4.3).

Q3: The backdoor attack algorithm guided by the generalization bound.

Theorem 1.1 shows how the poisoning ratio affects the accuracy of clean
samples, and we do not have special requirements for the trigger itself.
Theorem 1.2 indicates that if the trigger satisfies certain conditions, the
poison generalization error can be controlled. Motivated by the conditions in
Theorem 1.2, we propose a new clean-label backdoor attack which has certain
theoretical guarantee. By (Yu et al., 2022), the indiscriminate poison can be
considered as shortcuts, so according to the conditions in Theorem 1.2, we use
a certain combination of adversarial noise and indiscriminate poison as a
trigger, and then we experimentally demonstrate that our backdoor attack is
effective in a variety of settings.

##  2 Related Work

Generalization bound. Generalization bound is the central issue of learning
theory and has been studied extensively (Valle-Pérez & A. Louis, 2022).

The algorithm-independent generalization bounds usually depend on the VC-
dimension or the Rademacher complexity (Mohri et al., 2018). In (Harvey et
al., 2017; Bartlett et al., 2019), generalization bounds for DNNs were given
in terms of width, depth, and number of parameters. In (Neyshabur et al.,
2017; Barron & Klusowski, 2018; Dziugaite & Roy, 2017; Bartlett et al., 2017;
Valle-Pérez & A. Louis, 2022), upper bounds of the generalization error under
various cases were given. In (Wei & Ma, 2019; Arora et al., 2018), some
tighter generalization bound of networks was given based on Radermacher
complexity. Long & Sedghi (2019) gave the generalization bound of CNN, Vardi
et al. (2022) gives the sample complexity of small networks, Brutzkus &
Globerson (2021) studied the generalization bound of maxpooling networks.

Algorithm-dependent generalization bounds were established in the algorithmic
stability setting in (Wang & Ma, 2022; Kuzborskij & Lampert, 2018; Farnia &
Ozdaglar, 2021; Xing et al., 2021; Xiao et al., 2022; Wang et al., 2024) both
for the normal training and for the adversarial training. (Farnia & Ozdaglar,
2021; Xing et al., 2021; Xiao et al., 2022). Li et al. (2023) studied the
generalization bound of transformer. In (Arora et al., 2019; Cao & Gu, 2019;
Ji & Telgarsky, 2020), the training and generalization of DNNs in the over-
parameterized regime were studied.

For generalization under data poisoning, Wang et al. (2021) analyzed the
convergence of SGD under poison attacks for two-layer neural networks, and
Hanneke et al. (2022) gave the optimal learning error under poison attack when
there is only one target sample. In (Bennouna & Van Parys, 2022; Bennouna et
al., 2023), generalization bounds were used to design new robust algorithms
under the data poisoning.

Our result is different from these works and cannot be derived from them.
First, our bounds are for general networks and algorithm-independent. Second,
the backdoor attack has the special property that the trigger occurs in both
the training phase and the inference phase. Third, the purpose of the attack
is two-fold, whereas other poisoning attacks have a single goal.

Backdoor attacks and defenses. In general, backdoor attacks alter the training
data to introduce a trigger that induces model vulnerability (Chen et al.,
2017; Zhong et al., 2020; Li et al., 2020, 2021; Doan et al., 2021a), where
the labels can changed. Highly relevant to our work is a subset of backdoor
attacks called clean-label backdoor attacks (Turner et al., 2018; Barni et
al., 2019; Liu et al., 2020; Saha et al., 2020; Ning et al., 2021; Zeng et
al., 2022; Souri et al., 2022), where modifications to training data cannot
alter the label. The real-world attack was considered (Chen et al., 2017;
Bagdasaryan & Shmatikov, 2021). Backdoor detection methods (Huang et al.,
2019; Kolouri et al., 2020; Hayase et al., 2021; Zeng et al., 2021b) and
backdoor mitigation methods were proposed to defend against backdoor attacks
in (Liu et al., 2018; Wang et al., 2019; Zeng et al., 2021a). Most existing
backdoor attacks are mainly based on empirical heuristics, while our attack is
based on generalization bounds and has certain theoretical guarantees.

##  3 Notation

###  3.1 Basic Notation

Let the data satisfy a distribution ${\mathcal{D}}_{{\mathcal{S}}}$ over
${\mathcal{S}}\times[m]$, where ${\mathcal{S}}\subset[0,1]^{n}$ is a set of
image data and $[m]=\\{1,\ldots,m\\}$ is the label set. Let
${\mathcal{D}}_{{{\rm{tr}}}}=\\{(x_{i},y_{i})\\}_{i=1}^{N}$ be the training
set with $N$ samples that are i.i.d. sampled from
${\mathcal{D}}_{{\mathcal{S}}}$. Let
${\mathcal{F}}:{\mathcal{S}}\to{\mathbb{R}}^{m}$ be a neural network with Relu
as the activation function and Softmax added to the output layer. So, we have
${\mathcal{F}}:{\mathcal{S}}\to[0,1]^{m}$. For any network ${\mathcal{F}}$,
let
$\widehat{{\mathcal{F}}}(x)={\hbox{\rm{argmax}}}_{l=1}^{m}{\mathcal{F}}_{l}(x)$
be the classification result of ${\mathcal{F}}$, where ${\mathcal{F}}_{l}(x)$
is the $l$-th component of ${\mathcal{F}}(x)$. Let ${\mathcal{H}}_{W,D}$ be
the set of neural networks with width $W$ and depth $D$. For a given network
${\mathcal{F}}$, define
$h_{\mathcal{F}}(x,y)={\mathcal{F}}_{y}(x)\in{\mathcal{S}}\times[m]\to[0,1]$.
Let
${\mathcal{H}}_{W,D,1}=\\{h_{\mathcal{F}}(x,y)\,\|\,{\mathcal{F}}\in{\mathcal{H}}_{W,D}\\}$.

Let ${\hbox{\rm{Rad}}}^{{\mathcal{D}}}_{k}({\mathcal{H}})$ be the Rademacher
complexity of hypothesis space ${\mathcal{H}}$ under distribution
${\mathcal{D}}$ with $k$ samples, that is:

${\hbox{\rm{Rad}}}^{\mathcal{D}}_{k}({\mathcal{H}})={\mathbb{E}}_{x_{i}\sim{\mathcal{D}},i\in[k]}[{\mathbb{E}}_{\sigma}[\sup_{h\in{\mathcal{H}}}\frac{\sum_{i=1}^{k}\sigma_{i}h(x_{i})}{k}]],$

where $\sigma=(\sigma_{i})_{i=1}^{k}$ is a set of random variables such that
${\mathbb{P}}(\sigma_{i}=1)={\mathbb{P}}(\sigma_{i}=-1)=0.5$.

###  3.2 Backdoor Attack

In a clean-label backdoor attack, let
${\mathcal{P}}(x):{\mathbb{R}}^{n}\to{\mathbb{R}}^{n}$ be the trigger of the
sample $x$, $l_{p}$ be the target label, $\alpha$ be the poisoning rate of the
target label. The exact procedure for poisoning is as follows.

Create a clean label poisoned training set ${\mathcal{D}}_{P}$. Firstly,
randomly select $\alpha$ percent of the samples labeled $l_{p}$ in
${\mathcal{D}}_{{{\rm{tr}}}}$ to form a dataset ${\mathcal{D}}_{sub}$; then
let
${\mathcal{D}}_{poi}=\\{(x+{\mathcal{P}}(x),l_{p})\,\|\,(x,l_{p})\in{\mathcal{D}}_{sub}\\}$
be the set of poisoned samples and
${\mathcal{D}}_{clean}={\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{sub}$
be the set of clean samples; finally, let
${\mathcal{D}}_{P}={\mathcal{D}}_{clean}\cup{\mathcal{D}}_{poi}$ be the
poisoned training set.

Let ${\mathcal{D}}_{{\mathcal{S}}}^{l_{p}}$ be the distribution of the samples
with label $l_{p}$, that is, for any set $A$

${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}^{l_{p}}}((x,y)\in
A)={\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}}((x,y)\in A|y=l_{p}).$

The goal of clean-label backdoor attack. Let ${\mathcal{F}}$ be a network
trained on the poisoned training set ${\mathcal{D}}_{P}$. The goal of clean-
label backdoor attack is two fold:

(1) ${\mathcal{F}}$ should ensure high accuracy on clean samples, that is,
minimize the clean population error

${\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{{\mathcal{S}}})={\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(\widehat{{\mathcal{F}}}(x)\neq
y)].$

(2) For any clean sample $x$, ${\mathcal{F}}$ should classify
$x+{\mathcal{P}}(x)$ into label $l_{p}$, that is, minimize the poison
population error

${\mathcal{E}}_{P}({\mathcal{F}},{\mathcal{D}}_{{\mathcal{S}}})={\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(\widehat{{\mathcal{F}}}(x+{\mathcal{P}}(x)))\neq
l_{p})].$

To achieve the goals of the clean-label backdoor attack, we need to give upper
bounds for the clean population error and the poison population error in terms
of the empirical risk or the empirical error over the poisoned training set:

$\begin{array}[]{l}{\mathcal{R}}({\mathcal{F}},{\mathcal{D}}_{P})={\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[L_{CE}({{\mathcal{F}}}(x),y)]\\\
{\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{P})={\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[{\mathbf{1}}(\widehat{{\mathcal{F}}}(x)\neq
y)].\\\ \end{array}$

##  4 Generalization Bounds under Poison

In this section, we derive generalization bounds under clean-label backdoor
attack.

###  4.1 Clean Generalization Error Bound

In this subsection, we give an upper bound of the clean population error based
on the empirical error on ${\mathcal{D}}_{P}$, which implies Theorem 1.1.

######  Theorem 4.1.

Let $N=|{\mathcal{D}}_{{{\rm{tr}}}}|$. Then for any $\delta>0$, with
probability at least $1-\delta-O(\frac{1}{N})$, the following inequality holds
for any ${\mathcal{F}}(x)\in{\mathcal{H}}_{W,D}$

$\begin{array}[]{cl}{\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{S})\leq&\frac{4-2\alpha}{1-\alpha}{\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{P})\\\
&+{O}(\sqrt{\frac{mW^{2}D^{2}}{N(1-\alpha)^{2}}}+\sqrt{\frac{\ln(2/\delta)}{N(1-\alpha)}}).\end{array}$
(1)

Proof idea. In the backdoor attack, only a portion of the data is poisoned, so
we can select a subset from the training set ${\mathcal{D}}_{P}$, whose
elements are i.i.d. sampled from distribution ${\mathcal{D}}_{{\mathcal{S}}}$.
Then use the classical generalization bound in Theorem A.1 to estimate the
generalization bound under this subset. The proof and a generalized form of
Theorem 4.1 is given in the Appendix A.

The generalization bound (1) implies that for fixed $\alpha,W,D,$ when $N$ is
large enough, the attack has generalizability in the sense that a small
empirical error on ${\mathcal{D}}_{p}$ leads to a small population error. From
(1), we also see that the poison ratio $\alpha$ affects the population error:
a smaller $\alpha$ leads to a lower population error, as expected.

######  Remark 4.2.

Generalization bounds are usually given as upper bounds for the generalization
gap:
${\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{S})-{\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{{{\rm{tr}}}})$.
The generalization bound (1) cannot be written in this form, but it can be
used to establish generalizability as just explained above.

######  Remark 4.3.

The population error in (1) also depends on ${\mathcal{P}}(x)$ implicitly,
because the empirical error is affected by ${\mathcal{P}}(x)$. We will show
that certain ${\mathcal{P}}(x)$ can result in a large poison empirical error
in Appendix B.

######  Remark 4.4.

In Appendix C, we show that $O(\frac{1}{\sqrt{N}})$ is the optimal bound for
the generalization gap between the population error and the empirical error if
there is no special restriction on the distribution and hypothesis space.

###  4.2 Poison Generalization Error Bound

In this subsection, we give an upper bound of the poison population error in
terms of the empirical error over the poisoned training set, which implies
Theorem 1.2.

######  Theorem 4.5.

Let $N=|{\mathcal{D}}_{{{\rm{tr}}}}|$. For any
${\mathcal{F}}(x),{\mathcal{G}}(x)\in{\mathcal{H}}_{W,D}$, if trigger
${\mathcal{P}}(x)$ meets the following three conditions for some
$\epsilon>0,\tau>0,\lambda\geq 1$:
(c1):
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}[{\mathcal{G}}_{y}(x+{\mathcal{P}}(x))]\leq\epsilon$,
(c2):
${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{{\mathcal{S}}}}({\mathcal{P}}(x)\in
A|y\neq l_{p})\leq\lambda$
${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{{\mathcal{S}}}}$ $({\mathcal{P}}(x)\in
A|y=l_{p})$ for any set $A$,
(c3):
${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|({\mathcal{F}}-{\mathcal{G}})_{l_{P}}({\mathcal{P}}(x))-({\mathcal{F}}-{\mathcal{G}})_{l_{p}}(x+{\mathcal{P}}(x))|]\leq\tau$,
where
$({\mathcal{F}}-{\mathcal{G}})_{l_{P}}(x)={\mathcal{F}}_{l_{P}}(x)-{\mathcal{G}}_{l_{p}}(x)$,
then with probability at least $1-\delta-O(1/N)$, the following inequality
holds for ${\mathcal{F}}$:

$\begin{array}[]{l}{\mathcal{E}}_{P}({\mathcal{F}},{\mathcal{D}}_{{\mathcal{S}}})\leq\lambda
O(\frac{1}{\alpha}({\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[L_{CE}({\mathcal{F}}(x),y)]\\\
+{\hbox{\rm{Rad}}}_{N}^{{\mathcal{D}}_{S}^{l_{p}}}({\mathcal{H}}_{W,D,1}))+\sqrt{\frac{\ln(1/\delta)}{N\alpha}}+\epsilon+\tau+\frac{\lambda-1}{\lambda}).\end{array}$
(2)

Proof idea. First, estimate
${\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{y}(x+{\mathcal{P}}(x))]$
by the empirical error, which is similar to Theorem 4.1. Second, estimate
${\mathbb{E}}_{{\mathcal{D}}_{S}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]$ by
${\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{y}(x+{\mathcal{P}}(x))]$
and use the following method:
${\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{y}(x+{\mathcal{P}}(x))]\xrightarrow{{\rm{use}}\
(c1),(c3)}{\mathbb{E}}_{{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]\xrightarrow{{\rm{use}}\
(c2)}{\mathbb{E}}_{{\mathcal{D}}_{S}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]$.
Finally, use (c3) to estimate
${\mathcal{E}}_{P}({\mathcal{F}},{\mathcal{D}}_{{\mathcal{S}}})$ by
${\mathbb{E}}_{{\mathcal{D}}_{S}}[{\mathcal{F}}_{l_{p}}({\mathcal{P}}(x))]$.
An intuitive explanation of the proof is given in Appendix A.1. The proof and
a generalized form of Theorem 4.5 are given in Appendix D.

######  Remark 4.6.

It is clear that making the poison generalization error small by just adding
the trigger to a small percentage of training data can only be valid under
certain conditions. A key contribution of this paper is to find conditions
(c1), (c2), (c3) in Theorem 4.5. In the next subsection, we will explain these
conditions and show that it is possible to establish generalizability of the
poisoning attack with Theorem 4.5.

######  Remark 4.7.

${\hbox{\rm{Rad}}}_{N}^{{\mathcal{D}}_{S}^{l_{p}}}({\mathcal{H}}_{W,D,1})$ in
inequality (2) is not easy to calculate in terms of $W,D,N$, but we can
demonstrate that if $N$ is sufficiently large, this value will approach to $0$
in most cases, as shown in Appendix D.3.

######  Remark 4.8.

Please note that the right-hand side of inequality (2) is the empirical risk
${\mathcal{R}}({\mathcal{F}},{\mathcal{D}}_{P})$ but not the empirical error
${\mathcal{E}}({\mathcal{F}},{\mathcal{D}}_{P})$. This is due to some scaling
techniques used in the proof, which is reasonable. In order to achieve “victim
network classifies $x+{\mathcal{P}}(x)$ as class $l_{p}$”, the victim network
must learn the poisoned data ${\mathcal{D}}_{P}$ very well, just classifying
the poison data correct is not enough.

###  4.3 Explaining the Conditions in Theorem 4.5

In order to make the bound 2 small, the value of $\epsilon$ and $\tau$ need to
be small and $\lambda$ need to close to 1. In this section, we show that how
these values in the conditions (c1) to (c3) could be small.

How $\epsilon$ could be small? By condition (c1), since ${\mathcal{G}}_{y}(x)$
represents the probability that the network ${\mathcal{G}}$ classifies $x$ as
$y$, to make $\epsilon$ small, we only need to take the trigger
${\mathcal{P}}(x)$ as adversarial noise of the network ${\mathcal{G}}$ trained
on the clean dataset. In other words, if ${\mathcal{P}}(x)$ is adversary of
$x$ of a network trained on clean data, then $\epsilon$ is small.

How $\lambda$ could close to 1? By condition (c2), the upper bound is
proportional to $\lambda$, so we hope to have a small $\lambda$. When
${\mathcal{P}}(x)$ is the same for all $x$, we have $\lambda=1$. So, to make
$\lambda$ close to 1, ${\mathcal{P}}(x)$ need to be similar to $x$ with
different labels.

How $\tau$ could be small? Condition (c3) is not intuitive. In the rest of
this section, we give a condition for $\tau$ to be small. We give a simplified
version of the proposition and definition for easier reading. For a formal
description, please refer to the Appendix E.1.

Intuitive speaking, if ${\mathcal{F}}$ is a network trained on
${\mathcal{D}}_{P}$, then the meaning of (c3) is that the backdoor part (i.e.
${\mathcal{F}}-{\mathcal{G}}$) gives the similar outputs for
${\mathcal{P}}(x)$ and $x+{\mathcal{P}}(x)$. This is similar to some
conclusions in the indiscriminate poison(Zhu et al., 2023b; Huang et al.,
2021), and by(Yu et al., 2022), indiscriminate poison can be considered as
shortcut. These encourage the trigger to be shortcut. We will show that, under
some assumptions, making ${\mathcal{P}}(x)$ to be shortcut can ensure
condition (c3). First, we define the shortcut.

######  Definition 4.9 (Binary shortcut, Informal).

${\mathcal{P}}(x)$ is called a shortcut of the binary linear inseparable
classification dataset
${\mathcal{D}}=\\{(x_{i},1)\\}_{i=1}^{N_{1}}\cup\\{(\widehat{x}_{i},0)\\}_{i=1}^{N_{0}}$,
if
${\mathcal{D}}_{P}=\\{(x_{i},1)\\}_{i=1}^{N_{1}}\cup\\{(\widehat{x}_{i}+{\mathcal{P}}(\widehat{x}_{i}),0)\\}_{i=1}^{N_{0}}$
is linear separable.

Definition 4.9 means that shortcut is a poison which makes the poisoned
dataset to be linear separable. Finally, we will show that, when
${\mathcal{P}}(x)$ is a suitable shortcut, there exists an upper bound for
${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|({\mathcal{F}}-{\mathcal{G}})_{l_{p}}({\mathcal{P}}(x))-({\mathcal{F}}-{\mathcal{G}})_{l_{p}}(x+{\mathcal{P}}(x))|]$,
which implies that (c3) in Theorem 4.5 can be satisfied with a small $\tau$.

######  Proposition 4.10 (Informal. The exact form and proof are given in
Appendix E).

Following Theorem 4.5 and let
$D^{\prime}_{P}=\\{(x,0)|(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}\setminus{\mathcal{D}}_{clean}\\}\cup\\{(x,1)|(x,y)\in{\mathcal{D}}_{clean}\\}$.
Under certain mild conditions, if ${\mathcal{P}}(x)$ is the shortcut of the
dataset ${\mathcal{D}}^{\prime}_{P}$ and $N$ is big enough, then with high
probability, for some ${\mathcal{F}}\in{\mathcal{H}}_{W,D}$ satisfying
${\mathcal{F}}_{y}(x)>1-\epsilon$ for $\forall(x,y)\in{\mathcal{D}}_{P}$ and
${\mathcal{G}}\in{\mathcal{H}}_{W,D}$ satisfying
${\mathcal{G}}_{y}(x)>1-\epsilon$ for
$\forall(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}$, we have
${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|({\mathcal{F}}-{\mathcal{G}})_{l_{p}}({\mathcal{P}}(x))-({\mathcal{F}}-{\mathcal{G}})_{l_{p}}(x+{\mathcal{P}}(x))|]\leq\widetilde{O}(\epsilon)$.

So, let ${\mathcal{P}}(x)$ be shortcut of $D_{p}^{\prime}$, then, by
Proposition 4.10, if ${\mathcal{F}}\in{\mathcal{H}}_{W,D}$ fits
${\mathcal{D}}_{P}$ well and ${\mathcal{G}}\in{\mathcal{H}}_{W,D}$ fits
${\mathcal{D}}_{{{\rm{tr}}}}$ well, or empirically,
${\mathcal{F}}$(${\mathcal{G}}$) is well trained on dataset
${\mathcal{D}}_{P}$(${\mathcal{D}}_{{{\rm{tr}}}}$), then condition (c3) holds
for a small $\tau$.

######  Remark 4.11.

For condition (c3) in Theorem 4.5, we need to clarify that although
${\mathcal{F}}\approx{\mathcal{G}}$ implies (c3) for a small $\tau$, but
$\tau$ is small does not equivalent to ${\mathcal{F}}\approx{\mathcal{G}}$.
Moreover, using ${\mathcal{F}}\approx{\mathcal{G}}$ instead of (c3) can also
make Theorem 4.5 valid because it can derive (c3). But this is not a good
idea, because ${\mathcal{F}}\approx{\mathcal{G}}$ makes ${\mathcal{F}}$
satisfying (c1), and then ${\mathcal{F}}(x+p(x))$ always does not output label
$l_{p}$ when $x\sim D_{S}^{l_{p}}$. So for the poisoned data in the poisoning
dataset, ${\mathcal{F}}$ cannot output the correct labels, leading to a larger
empirical error on the right-hand side of equation (2), and consequently leads
to a big poison generalization error upper bound. Obviously, what we need is a
small poison generalization error upper bound but not a big one, so we cannot
only consider ${\mathcal{F}}\approx{\mathcal{G}}$.

##  5 Method

In this section, we will propose a new clean-label poison attack based on
Theorems 4.1 and 4.5. There exists no requirement for the trigger
${\mathcal{P}}(x)$ in Theorem 4.1, so we only need to make the trigger
approximately satisfy the conditions of Theorem 4.5. Our method thus has
certain theoretical guarantee.

From Section 4.3, in order to satisfy the three conditions in Theorem 4.5,
${\mathcal{P}}(x)$ need to be (1) adversarial noises for the clean-trained
network, (2) shortcut for a specifically designed binary dataset, (3) similar
for different samples.

######  Remark 5.1.

The effectiveness of adversarial and shortcut in creating backdoor has already
been demonstrated empirically in previous work. On the other hand, our theory
provides a more informed approach to using these methods.

Based on the above three requirements just mentioned, we design the trigger as
follows:

(M1): Obtain adversarial disturbance: For any given clean sample $x$, use PGD
on the network trained on ${\mathcal{D}}_{{{\rm{tr}}}}$ to find adversarial
noise $x_{adv}$ of $x$.

(M2): Obtain shortcut disturbance: For any given clean sample $x$, use min-min
method (Huang et al., 2021) under the clean training set to find the shortcut
$x_{scut}$ of $x$. In (Zhu et al., 2023b) it has been shown that the shortcuts
created by the min-min method are indeed similar for different $x$, thus
satisfying condition (c2) automatically.

(M3): The trigger of $x$ is designed to be
${\mathcal{P}}(x)=Ux_{adv}+(1-U)x_{scut}$, where $U\in\\{0,1\\}^{n}$ is a
mask. We combine such two disturbances in this way because: (1) make the
trigger both adversarial and shortcut; (2) make the triggers have a certain
degree of similarity for different $x$, using the fact that the part of
$(1-U)x_{scut}$ in trigger is similar for different $x$. It is worth
mentioning that making $x_{adv}$ similar for different $x$ is difficult, so
creating a trigger by $\lambda x_{adv}+(1-\lambda)x_{scut}$ will not be
effective to ensuring similarity.

The mask $U$ in (M3) is constructed as follows. The upper left corner is 0 and
the other part is 1. On the basis of experience, it is necessary to disturb
the key parts of the image to create adversarial samples, so we use a large
portion to create adversaries. But the cost of the shortcut is relatively low,
so we just use a small place to create the shortcut.

Algorithm 1 provides detailed steps for creating the trigger, where $\cdot$ is
element-wise product.

Algorithm 1 Method of Creating the Trigger:

0: An initialized network
${\mathcal{F}}_{1}:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$;An initialized network
${\mathcal{F}}_{2}:{\mathbb{R}}^{n}\to{\mathbb{R}}^{2}$;A clean dataset
$T=\\{(x_{i},y_{i})\\}_{i=1}^{N}\subset[0,1]^{n}\times[m]$;A mask vector
$U\in\\{0,1\\}^{n}$;The poison budget $\eta$;Victim dataset
$\\{(x^{v}_{i},y^{v}_{i})\\}_{i=1}^{V}$.

0: Trigger $\\{{\mathcal{P}}(x^{v}_{i})\\}_{i=1}^{V}$ for all victim data
$\\{(x^{v}_{i},y^{v}_{i})\\}$.S1 Use $T$ to train the network
${\mathcal{F}}_{1}$.S2 Let $T_{1}=\\{\\}$, for each $(x,y)\in T$: let
$x_{adv}=x+U\cdot{\hbox{\rm{argmax}}}_{||{\mathbf{\varepsilon}}||\leq\eta}L(F_{1}(x+{\mathbf{\varepsilon}}),y)$
add $(x_{adv},0)$ and $(x,1)$ to $T_{1}$.S3 Use $T_{1}$ to train the network
${\mathcal{F}}_{2}$ as follows:  $\min_{{\mathcal{F}}_{2}}\sum_{(x,y)\in
T_{1}}L({\mathcal{F}}_{2}(x+{\mathbf{\varepsilon}}(x,y)),y)$ where
${\mathbf{\varepsilon}}(x,y)={\mathbf{1}}(y=0)\cdot(1-U)\cdot\mathop{{\hbox{\rm{argmin}}}}\limits_{||{\mathbf{\varepsilon}}||\leq\eta}L({\mathcal{F}}_{2}(x+(1-U)\cdot{\mathbf{\varepsilon}}),y)$.S4
For any victim data $(x_{i}^{v},y_{i}^{v})$, we calculate
${\mathcal{P}}(x_{i}^{v})$ as following:
$x^{v}_{a}=x_{i}^{v}+U\cdot{\hbox{\rm{argmax}}}_{||{\mathbf{\varepsilon}}||\leq\eta}L({\mathcal{F}}_{1}(x_{i}^{v}+{\mathbf{\varepsilon}}),y_{i}^{v})$;
${\mathcal{P}}(x_{i}^{v})=(x^{v}_{a}-x_{i}^{v})+$
$(1-U)\cdot\mathop{{\hbox{\rm{argmin}}}}\limits_{||{\mathbf{\varepsilon}}||\leq\eta}L({\mathcal{F}}_{2}(x^{v}_{a}+{\mathbf{\varepsilon}}\cdot(1-U)),0)$.Output:
Trigger $\\{{\mathcal{P}}(x^{v}_{i})\\}_{i=1}^{V}$.

In Algorithm 1, ${\mathcal{F}}_{1}$ is used to create adversarial disturbance
and ${\mathcal{F}}_{2}$ is used to create shortcuts. When we complete step
$S3$ in the algorithm, we will save ${\mathcal{F}}_{1}$ and
${\mathcal{F}}_{2}$, and for any sample $(x,y)$, we directly generate
${\mathcal{P}}(x)$ using S4. Some poisons obtained using Algorithm 1 are shown
in Figure 1.

Figure 1: From top row to bottom row are respectively the clean images,
normalized triggers (original trigger has $L_{\infty}$ norm bound $16/255$),
poison images. Due to the selection of $U$, the upper left corners of the
poison images are similar, while the other parts are used to generate
adversaries.

##  6 Experiments

In this section, we empirically validate the proposed backdoor attack on
benchmark datasets CIFAR10, CIFAR100 (Krizhevsky et al., 2009), SVHN and
TinyImageNet(Le & Yang, 2015), and against popular defenses. We also conduct
ablation experiments to verify our main Theorems 4.1 and 4.5. All experiments
are repeated for $3$ times and report the average values. Furthermore, we make
our attacks invisible by limiting the $L_{\infty}$ norm of trigger. Details
about the experiment setting can be found in Appendix F.1. Code is in
https://github.com/hong-xian/backdoor-attack.git.

###  6.1 Baseline Evaluation

In this subsection, we study the effectiveness of our backdoor attack. For
backdoor attacks, the goal is to misclassify the samples with trigger into a
specified target class $l_{p}$. Unless said otherwise, we set the target label
$l_{p}$ as $0$ in this paper. In addition to evaluating the test accuracy and
attack success rate (ASR), we also measure the accuracy of the target class
$l_{p}$ to analyze the impact of the attack on the target label.

Table 1 shows the result on CIFAR-10 when perturbing $1\%$ of training images,
with each perturbation restricted to a radius $l_{\infty}$-norm $16/255$. We
observe that the ASR exceeds $90\%$, while the poison has negligible impact on
both the test accuracy and the target class accuracy. In Table 2, we observe
that the proposed attack remains remarkably effective even when the poison
budget is very small. More experiments on different poison budgets and norm
bounds can be found in Table 8. About transferability of attack and whether
the victim network has learned the feature of trigger, please refer to the
Appendix F.5.

Table 1: Baseline evaluations on CIFAR-10. Perturbations have $l_{\infty}$-norm bounded above by $16/255$, and poison budget is $1\%$ of training images. Res means ResNet18, VGG means VGG16, WR means WRN34-10. Model | Res | VGG | WR
---|---|---|---
Clean model acc ($\%$) | 93 | 92 | 94
Poisoned model acc($\%$) | 91 | 91 | 92
Clean model $l_{p}$ acc($\%$) | 94 | 92 | 95
Poisoned model $l_{p}$ acc($\%$) | 93 | 91 | 93
Attack Success Rate($\%$) | 93 | 91 | 90
Table 2: The effect of poison budget on CIFAR-10 with ResNet18. Perturbations have $l_{\infty}$-norm bounded above by $16/255$. Poison Budget | $0.6\%$ | $1\%$ | $2\%$
---|---|---|---
Clean model acc ($\%$) | 93 | 93 | 93
Poisoned model acc($\%$) | 93 | 91 | 93
Clean model $l_{p}$ acc($\%$) | 94 | 94 | 94
Poisoned model $l_{p}$ acc($\%$) | 93 | 93 | 92
Attack Success Rate($\%$) | 86 | 93 | 94

Attack performance during the training process: To further validate the
efficacy of our attack, we monitor the evolution of the overall clean model
accuracy, the poisoned model accuracy, and the attack success rate throughout
the training process, as shown in Figure 2. In Figure 2, we observe that the
overall clean model accuracy and poisoned model accuracy remain very close.
The attack success rate reaches a relatively high level from the very
beginning and gradually converges to remain stable over time. This shows that
our attack method is effective under the premise of maintaining the accuracy
of the model.

Any target label: Note that the success of backdoor attacks also depends on
the choice of target classes, to demonstrate the general efficacy of our
attack for any target label $l_{p}$, we change $l_{p}$ from $0$ to $9$, the
result is shown in Figure 3. The results are quite uniform.

Figure 2: Attack performance during the training process on CIFAR10 with
ResNet18 and VGG16. This figure shows the trend of the poison model accuracy
($A$), attack success rate (ASR) and clean model accuracy ($A_{c}$).  Figure
3: Performance of different target label $l_{p}$. We show the poison model
accuracy ($A$), accuracy of target label ($A_{t}$), attack success rate
($A_{p}$) on CIFAR-10, using VGG16 and ResNet18.

###  6.2 Evaluation on More Datasets

We perform experiments on SVHN, CIFAR-100 and TinyImageNet. Table 3 summarizes
the performance of our attack on different datasets, where the attacks are
tested on ResNet18 for SVHN and CIFAR-100, and WRN34-10 for TinyImageNet. Each
attacker can only perturb $0.8\%$ of the training images for TinyImageNet and
CIFAR-100 and $2\%$ of the training images for SVHN, all perturbations are
restricted to an $l_{\infty}$ norm $16/255$, and the target label is
$l_{p}=0$. Additional experiments on different poison budgets and
$l_{\infty}$-norm bounds are presented in Table 9 in the appendix.

Table 3: Evaluations on more datasets. Perturbations have $l_{\infty}$-norm bounded by $16/255$, and poison budget is $0.8\%$ for TinyImageNet and CIFAR-100 and $2\%$ for SVHN.  Datasets | Clean acc | Poison acc | ASR
---|---|---|---
SVHN ($\%$) | 93 | 92 | 79
CIFAR-100 ($\%$) | 76 | 72 | 92
TinyImageNet($\%$) | 62 | 60 | 82

###  6.3 Compare with Other Attacks

There are several existing clean-label hidden-trigger backdoor attacks that
claim success in some settings. We consider the following seven attack
methods.

Clean Label: Turner et al. (2018) pioneered clean label attacks. They first
utilized adversarial perturbations or generative models to initially alter
target class images and then performed standard invisible attacks.

Reflection: Liu et al. (2020) proposed adopting reflection as the trigger for
stealthiness.

Hidden Trigger: Saha et al. (2020) proposed to inject the information of a
poisoned sample generated by a previous visible attack into an image of the
target class by minimizing its distance in the feature space.

Invisible Poison Ning et al. (2021) converted a regular trigger to a noised
trigger to achieve stealthiness, but remains effective in the feature space
for poison training data.

Image-specific: Luo et al. (2022) used an autoencoder to generate image-
specific triggers that can promote the implantation and activation phases of
the backdoor.

Narcissus: Zeng et al. (2022) solved the following optimization to obtain the
trigger ${\mathcal{P}}$: ${\hbox{\rm{argmin}}}_{{\mathcal{P}}}\sum
L(f_{sur}(x+{\mathcal{P}},l_{p})$, where $f_{sur}$ is the surrogate network.

Sleeper Agent: Souri et al. (2022) proposed a backdoor attack by approximately
solving the bilevel formulation with the Gradient Matching method (Geiping et
al., 2020).

To further validate the efficacy of our attack, we compare our method with
other clean label attack methods under the same settings. Specifically, we
limit the $L_{\infty}$ norm trigger no more than $16/255$ on both the training
set and the test set. It should be noted that, in some attack methods, the
trigger budget in their original settings may exceed $16/255$, so we also
compare under each respective settings. The results are given in Table 4. More
results and some details are provided in Appendix F.3.

Table 4: Attack success rate on CIFAR-10 with ResNet18. Comparison of our method to popular clean-label attacks, poison budget is $1\%$. The first column is the attack under $L_{\infty}$ limitation $16/255$, the second column is under each respective settings. Attacks | 16/255 | Each setting |
---|---|---|---
Clean-Label | $23\%$ | $96\%$ |
Hidden-Trigger | $75\%$ | $95\%$ |
Reflection | $54\%$ | $90\%$ |
Invisible Poison | $73\%$ | $98\%$ |
Image-specific | $70\%$ | 70$\%$ |
Narcissus | $50\%$ | $92\%$ |
Sleeper-Agent | 61$\%$ | 71$\%$ |
Ours | 93$\%$ | 93$\%$ |

From Table 4, we find that our attack significantly outperforms all other
methods under the $16/255$ limitation. Moreover, our method has two key
advantages: (1) Our method does not require additional steps. Sleeper Agent
and Hidden-Trigger need a pre-existing patch and Reflection requires a fitting
image; Narcissus needs to magnify the trigger in the reference phase. (2) Our
method does not require large networks during poison generation, whereas
Invisible Poison and Image-specific utilize large generative models to achieve
optimal performance, and Narcissus requires a network trained on a different
dataset. See Tables 10 and 11 in the appendix for more results.

Under each respective setting, all results were good, but many of them no
longer meet the $16/255$ limitation. Furthermore, some of them need a patch in
the trigger like Clean-label and Sleeper-Agent, and some of them need a larger
disturbance like Reflection and Narcissus.

###  6.4 Defenses

Many backdoor defenses have been proposed to mitigate the effects of backdoor
attacks. We test our attack and the attack methods mentioned in section 6.3
against some major popular defenses. We evaluate six types of defenses:

(1) AT: adversarial training with radius $8/255$ (Madry et al., 2017);

(2): Data Augmentation: (Borgnia et al., 2021);

(3) Scale-up: contrastive learning (Guo et al., 2023);

(4) DPSGD: differentially private SGD (Hong et al., 2020);

(5) Frequency Filter: remove high-frequency parts of images (Zeng et al.,
2021b);

(6): Fine-Tuning: (Zhu et al., 2023a).

Table 5: Defenses: The attack success rate($\%$) and poison model accuracy($\%$, in bracket) on CIFAR-10 with ResNet18 of our attack and other attacks against various defense methods. Poison ratio is $1\%$ and perturbation have $l_{\infty}$-norm bound $16/255$, target label $l_{p}=0$. | AT | Data Augmentaion | Scale-Up | DPSGD | Frequency Filter | Fine-Tuning
---|---|---|---|---|---|---
Clean Label(%) | 13(83) | 17(89) | 9(77) | 12(78) | 12(86) | 11(89)
Invisible Poison(%) | 11(84) | 30(91) | 18(80) | 18(76) | 20(88) | 12(90)
Hidden Trigger(%) | 14(83) | 25(90) | 31(81) | 14(75) | 20(87) | 10(88)
Narcissu(%) | 13(83) | 23(90) | 11(83) | 15(76) | 16(86) | 10(89)
Image-specific(%) | 10(84) | 28(89) | 22(79) | 14(77) | 22(87) | 12(87)
Reflection(%) | 13(85) | 20(89) | 16(82) | 13(76) | 37(85) | 13(85)
Sleeper-Agent | 14(83) | 27(87) | 27(79) | 15(75) | 27(84) | 11(89)
Ours(%) | 15(83) | 40(91) | 32(80) | 12(77) | 28(88) | 13(89)
Ours-stronger(%) |  34(84) |  66(90) | – |  52(80) |  62(88) | –

The defense results are given in Table 5. We can see that ASR has basically
decreased to around 10$\%$, which is the lowest level because 10$\%$ of the
samples themselves have the label 0. This is because we have imposed many
restrictions on backdoor attacks, as said in Section F.1; and also because our
theory and construction of trigger are mainly based on clean training, so our
method appears somewhat fragile under defense; in fact, all attack methods
mentioned in Section 6.3 appear fragile under defense methods, as shown in
Table 5.

On the other hand, we find that there exists a robustness-accuracy trade-off
across many of these defenses. Although these defense methods do degrade the
attack success rate, they also cause the accuracy of the model test to
decrease. For defense methods Scale-Up, this method is not stable and
sometimes detects clean samples as poison samples; for fine-tuning, because a
clean training set was used, this defense method has a very outstanding
effect.

Furthermore, we point out that if we incorporate these defense methods into
our attack generation to produce corresponding enhanced attacks, we can
effectively withstand these defenses. For defense methods (1), (2), (4) and
(5), we enhance our attack, details are shown in Appendix F.4, and get the
better result.

###  6.5 Verify Theorem 4.5

In this section, we verify Theorem 4.5. In Appendix F.7, we verify Theorem
4.1.

We verify Theorem 4.5 by showing that any trigger ${\mathcal{P}}(x)$ that
makes the $\epsilon,\tau,\lambda$ in conditions (c1), (c2), (c3) of Theorem
4.5 small can achieve a high attack success rate.

To validate our conclusions, we evaluate the following poisoning function
${\mathcal{P}}(x)$, refer to Appendix F.6 for more details:

RN: Random noises with $L_{\infty}$ bound and $L_{0}$ norm bound;

UA: Universal adversarial perturbations (Moosavi-Dezfooli et al., 2017);

Adv: Adversarial perturbations (Szegedy et al., 2013);

SCut: shortcut noise(Huang et al., 2021);

Ours: Perturbations generated by Algorithm 1.

We consider two indicators to evaluate the performance of poison on conditions
(c1) and (c3) in Theorem 4.5:

  * •

Use the validation loss on poisoned data to measure condition (c1):
$V_{adv}={\mathbb{E}}_{(x,y)\sim{\mathcal{D}}}L({\mathcal{F}}(x+{\mathcal{P}}(x)),y)$,
where ${\mathcal{F}}$ is ResNet18 trained on the clean dataset.

  * •

Use the binary classification loss to measure condition (c3) by Proposition
4.10:
$V_{sc}=\min_{{\mathcal{F}}}{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}}[L({\mathcal{F}}(x+{\mathcal{P}}(x),0))+L({\mathcal{F}}(x),1)]$,
where ${\mathcal{F}}$ is a two-layer network.

About condition (c2) in Theorem 4.5: for RN and UA, the poison perturbation is
the same for every sample; for SCut and Ours, the perturbations for different
samples are similar (or at least parts of the perturbation are similar).

Table 6 shows the results. We can see that RN, UA, SCut with a large budget
can achieve good attack performance because they satisfy conditions (c1),
(c2), (c3) in Theorem 4.5 to certain degree, which validates the effectiveness
of conditions in Theorem 4.5. Moreover, each of $V_{adv}$ and $V_{sc}$ is not
satisfied, because adversaries alone yield excessively large $V_{sc}$ since
adversarial perturbations do not form shortcuts. Shortcuts alone produce an
undesirably small $V_{adv}$ since the shortcuts do not become adversaries.
However, by combining Adv and SCut via our algorithm, we achieve a
significantly improved outcome.

On the other hand, please note Adv attack under the $32/255$ budget. Although
the Adv attack’s similarity between different samples is poor, but its
$V_{adv}$ and $V_{sc}$ is not bad, and its ASR is about $80\%$, this
indicating that even if the similarity is not good enough, but the other two
indicators are good, the attack can still be achieved. Therefore, in order to
prevent the trigger from being detected due to being too similar, we can
achieve attack effectiveness by reducing similarity and improving other two
metrics.

Table 6:  Values of $V_{adv}$ and $V_{sc}$; poison model accuracy (Acc); attack success rate (ASR) on CIFAR-10 test set with ResNet18. Poison budget is $1\%$. If not specified, the norm is $L_{\infty}$. Poison Type | $V_{adv}(\uparrow)$ | $V_{sc}(\downarrow)$ | ASR$(\uparrow)$ | Acc
---|---|---|---|---
RN ($16/255$) | 2.40 | 0.014 | 12$\%$ | 91$\%$
RN ($L_{0}$, $200$) | 3.87 | 0.004 | 59$\%$ | 92$\%$
UA ($16/255$) | 2.92 | 0.002 | 51$\%$ | 91$\%$
Adv ($16/255$) | 8.92 | 1.27 | 22$\%$ | 92$\%$
SCut ($16/255$) | 1.19 | ${\bf 10^{-4}}$ | 30$\%$ | 91$\%$
Ours ($16/255$) | 6.53 | 0.001 | 93$\%$ | 91$\%$
RN ($32/255$) | 6.28 | $10^{-4}$ | 99$\%$ | 91$\%$
RN ($L_{0}$, $300$) | 6.33 | 0.003 | 94$\%$ | 91$\%$
UA ($32/255$) | 15.45 | $10^{-4}$ | 92$\%$ | 92$\%$
Adv ($32/255$) | 16.38 | 0.35 | 80$\%$ | 92$\%$
SCut ($32/255$) | 4.22 | ${\bf 10^{-5}}$ | 93$\%$ | 90$\%$
Ours ($32/255$) | 14.65 | $10^{-4}$ | 99$\%$ | 92$\%$

##  7 Conclusion

In this paper, we give generalization bounds for the clean-label backdoor
attack. Precisely, we provide upper bounds for the clean and poison population
error based on empirical error on the poisoned training set and some other
quantities. These bounds give the theoretical foundation for the clean-label
backdoor attack in that the goal of the attack can be achieved under certain
reasonable conditions. The main technical difficulties in establishing these
bounds include how to treat the non-i.i.d. poisoned dataset and the fact that
the triggers are both in the training and testing phases.

Based on these theoretical results, we propose a novel attack method that uses
a combination of adversarial noise and indiscriminate poison as the trigger.
Moreover, extensive experiments show that our attack can guarantee that the
accuracy of the poisoned model on clean data and the attack success rate are
high.

Limitations and Future Work. The conditions of Theorem 4.5 are quite
complicated, and it is desirable to give simpler conditions for the poisoned
population error bound in Theorem 4.5. The current generalization bounds do
not involve the training process, and algorithmic-dependent generalization
bounds, such as stability analysis (Hardt et al., 2016), should be further
analyzed for backdoor attacks.

## Impact Statement

A theoretical basis for backdoor attacks is given. One potential negative
social impact of this work is that malicious opponents may use these methods
to generate new types of backdoor poisons. Therefore, it is necessary to
develop more powerful models to resist backdoor attacks, which is left for
future work.

## Acknowledgments

This work is supported by CAS Project for Young Scientists in Basic Research,
Grant No.YSBR-040, ISCAS New Cultivation Project ISCAS-PYFX-202201, and ISCAS
Basic Research ISCAS-JCZD-202302. This work is supported by NSFC grant
No.12288201 and NKRDP grant No.2018YFA0306702. The authors thank anonymous
referees for their valuable comments.

## References

  * Arora et al. (2018) Arora, S., Ge, R., Neyshabur, B., and Zhang, Y.  Stronger generalization bounds for deep nets via a compression approach.  In _International Conference on Machine Learning_ , pp. 254–263. PMLR, 2018.
  * Arora et al. (2019) Arora, S., Du, S., Hu, W., Li, Z., and Wang, R.  Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks.  In _International Conference on Machine Learning_ , pp. 322–332. PMLR, 2019.
  * Bagdasaryan & Shmatikov (2021) Bagdasaryan, E. and Shmatikov, V.  Blind backdoors in deep learning models.  In _30th USENIX Security Symposium (USENIX Security 21)_ , pp. 1505–1521, 2021.
  * Barni et al. (2019) Barni, M., Kallas, K., and Tondi, B.  A new backdoor attack in cnns by training set corruption without label poisoning.  In _2019 IEEE International Conference on Image Processing (ICIP)_ , pp. 101–105. IEEE, 2019.
  * Barron & Klusowski (2018) Barron, A. R. and Klusowski, J. M.  Approximation and estimation for high-dimensional deep learning networks.  _arXiv preprint arXiv:1809.03090_ , 2018.
  * Bartlett et al. (2017) Bartlett, P. L., Foster, D. J., and Telgarsky, M. J.  Spectrally-normalized margin bounds for neural networks.  _Advances in neural information processing systems_ , 30, 2017.
  * Bartlett et al. (2019) Bartlett, P. L., Harvey, N., Liaw, C., and Mehrabian, A.  Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks.  _The Journal of Machine Learning Research_ , 20(1):2285–2301, 2019.
  * Bartlett et al. (2021) Bartlett, P. L., Montanari, A., and Rakhlin, A.  Deep learning: a statistical viewpoint.  _Acta numerica_ , 30:87–201, 2021.
  * Bennouna & Van Parys (2022) Bennouna, A. and Van Parys, B.  Holistic robust data-driven decisions.  _arXiv preprint arXiv:2207.09560_ , 2022.
  * Bennouna et al. (2023) Bennouna, A., Lucas, R., and Van Parys, B.  Certified robust neural networks: Generalization and corruption resistance.  In _International Conference on Machine Learning_ , pp. 2092–2112. PMLR, 2023.
  * Bertsekas & Tsitsiklis (2008) Bertsekas, D. and Tsitsiklis, J. N.  _Introduction to probability_ , volume 1.  Athena Scientific, 2008.
  * Borgnia et al. (2021) Borgnia, E., Cherepanova, V., Fowl, L., Ghiasi, A., Geiping, J., Goldblum, M., Goldstein, T., and Gupta, A.  Strong data augmentation sanitizes poisoning and backdoor attacks without an accuracy tradeoff.  In _IEEE International Conference on Acoustics, Speech and Signal Processing_ , pp. 3855–3859. IEEE, 2021.
  * Brutzkus & Globerson (2021) Brutzkus, A. and Globerson, A.  An optimization and generalization analysis for max-pooling networks.  In _Uncertainty in Artificial Intelligence_ , pp. 1650–1660. PMLR, 2021.
  * Cao & Gu (2019) Cao, Y. and Gu, Q.  Generalization bounds of stochastic gradient descent for wide and deep neural networks.  _Advances in neural information processing systems_ , 32, 2019.
  * Chen et al. (2017) Chen, X., Liu, C., Li, B., Lu, K., and Song, D.  Targeted backdoor attacks on deep learning systems using data poisoning.  _arXiv preprint arXiv:1712.05526_ , 2017.
  * Dabouei et al. (2020) Dabouei, A., Soleymani, S., Taherkhani, F., Dawson, J., and Nasrabadi, N.  Smoothfool: An efficient framework for computing smooth adversarial perturbations.  In _Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision_ , pp. 2665–2674, 2020.
  * Doan et al. (2021a) Doan, K., Lao, Y., and Li, P.  Backdoor attack with imperceptible input and latent modification.  _Advances in Neural Information Processing Systems_ , 34:18944–18957, 2021a.
  * Doan et al. (2021b) Doan, K., Lao, Y., Zhao, W., and Li, P.  Lira: Learnable, imperceptible and robust backdoor attacks.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pp. 11966–11976, 2021b.
  * Dziugaite & Roy (2017) Dziugaite, G. K. and Roy, D. M.  Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data.  _arXiv preprint arXiv:1703.11008_ , 2017.
  * Farnia & Ozdaglar (2021) Farnia, F. and Ozdaglar, A.  Train simultaneously, generalize better: Stability of gradient-based minimax learners.  In _International Conference on Machine Learning_ , pp. 3174–3185. PMLR, 2021.
  * Fu et al. (2020) Fu, S., He, F., Liu, Y., Shen, L., and Tao, D.  Robust unlearnable examples: Protecting data against adversarial learning.  _arXiv preprint arXiv:2012.04115_ , 2020.
  * Gao et al. (2023) Gao, Y., Li, Y., Zhu, L., Wu, D., Jiang, Y., and Xia, S.-T.  Not all samples are born equal: Towards effective clean-label backdoor attacks.  _Pattern Recognition_ , 139:109512, 2023.
  * Geiping et al. (2020) Geiping, J., Fowl, L., Huang, W. R., Czaja, W., Taylor, G., Moeller, M., and Goldstein, T.  Witches’ brew: Industrial scale data poisoning via gradient matching.  _arXiv preprint arXiv:2009.02276_ , 2020.
  * Gu et al. (2017) Gu, T., Dolan-Gavitt, B., and Garg, S.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  _arXiv preprint arXiv:1708.06733_ , 2017.
  * Guo et al. (2023) Guo, J., Li, Y., Chen, X., Guo, H., Sun, L., and Liu, C.  Scale-up: An efficient black-box input-level backdoor detection via analyzing scaled prediction consistency.  _arXiv preprint arXiv:2302.03251_ , 2023.
  * Hanneke et al. (2022) Hanneke, S., Karbasi, A., Mahmoody, M., Mehalel, I., and Moran, S.  On optimal learning under targeted data poisoning.  _Advances in Neural Information Processing Systems_ , 35:30770–30782, 2022.
  * Hardt et al. (2016) Hardt, M., Recht, B., and Singer, Y.  Train faster, generalize better: Stability of stochastic gradient descent.  In _International conference on machine learning_ , pp. 1225–1234. PMLR, 2016.
  * Harvey et al. (2017) Harvey, N., Liaw, C., and Mehrabian, A.  Nearly-tight vc-dimension bounds for piecewise linear neural networks.  In _Conference on learning theory_ , pp. 1064–1068. PMLR, 2017.
  * Hayase et al. (2021) Hayase, J., Kong, W., Somani, R., and Oh, S.  Spectre: Defending against backdoor attacks using robust statistics.  In _International Conference on Machine Learning_ , pp. 4129–4139. PMLR, 2021.
  * He et al. (2016) He, K., Zhang, X., Ren, S., and Sun, J.  Deep residual learning for image recognition.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 770–778, 2016.
  * Hong et al. (2020) Hong, S., Chandrasekaran, V., Kaya, Y., Dumitraş, T., and Papernot, N.  On the effectiveness of mitigating data poisoning attacks with gradient shaping.  _arXiv preprint arXiv:2002.11497_ , 2020.
  * Huang et al. (2021) Huang, H., Ma, X., Erfani, S. M., Bailey, J., and Wang, Y.  Unlearnable examples: Making personal data unexploitable.  _arXiv preprint arXiv:2101.04898_ , 2021.
  * Huang et al. (2019) Huang, X., Alzantot, M., and Srivastava, M.  Neuroninspect: Detecting backdoors in neural networks via output explanations.  _arXiv preprint arXiv:1911.07399_ , 2019.
  * Ji & Telgarsky (2020) Ji, Z. and Telgarsky, M.  Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow relu networks.  In _ICLR 2020_ , 2020.
  * Kolouri et al. (2020) Kolouri, S., Saha, A., Pirsiavash, H., and Hoffmann, H.  Universal litmus patterns: Revealing backdoor attacks in cnns.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pp. 301–310, 2020.
  * Krizhevsky et al. (2009) Krizhevsky, A., Hinton, G., et al.  Learning multiple layers of features from tiny images.  _Technical Report TR-2009_ , 2009.
  * Kuzborskij & Lampert (2018) Kuzborskij, I. and Lampert, C.  Data-dependent stability of stochastic gradient descent.  In _International Conference on Machine Learning_ , pp. 2815–2824. PMLR, 2018.
  * Le & Yang (2015) Le, Y. and Yang, X.  Tiny imagenet visual recognition challenge.  _CS 231N_ , 7(7):3, 2015.
  * Li et al. (2020) Li, S., Xue, M., Zhao, B. Z. H., Zhu, H., and Zhang, X.  Invisible backdoor attacks on deep neural networks via steganography and regularization.  _IEEE Transactions on Dependable and Secure Computing_ , 18(5):2088–2105, 2020.
  * Li et al. (2021) Li, Y., Li, Y., Wu, B., Li, L., He, R., and Lyu, S.  Invisible backdoor attack with sample-specific triggers.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pp. 16463–16472, 2021.
  * Li et al. (2023) Li, Y., Ildiz, M. E., Papailiopoulos, D., and Oymak, S.  Transformers as algorithms: Generalization and stability in in-context learning.  In _International Conference on Machine Learning_ , pp. 19565–19594. PMLR, 2023.
  * Liu et al. (2018) Liu, K., Dolan-Gavitt, B., and Garg, S.  Fine-pruning: Defending against backdooring attacks on deep neural networks.  In _International symposium on research in attacks, intrusions, and defenses_ , pp. 273–294. Springer, 2018.
  * Liu et al. (2020) Liu, Y., Ma, X., Bailey, J., and Lu, F.  Reflection backdoor: A natural backdoor attack on deep neural networks.  In _Computer Vision–ECCV 2020: 16th European Conference, Glasgow, UK, August 23–28, 2020, Proceedings, Part X 16_ , pp. 182–199. Springer, 2020.
  * Long & Sedghi (2019) Long, P. M. and Sedghi, H.  Generalization bounds for deep convolutional neural networks.  _arXiv preprint arXiv:1905.12600_ , 2019.
  * Luo et al. (2022) Luo, N., Li, Y., Wang, Y., Wu, S., Tan, Y.-a., and Zhang, Q.  Enhancing clean label backdoor attack with two-phase specific triggers.  _arXiv preprint arXiv:2206.04881_ , 2022.
  * Madry et al. (2017) Madry, A., Makelov, A., Schmidt, L., Tsipras, D., and Vladu, A.  Towards deep learning models resistant to adversarial attacks.  In _International Conference on Learning Representations_ , 2017.
  * Massart (2000) Massart, P.  Some applications of concentration inequalities to statistics.  In _Annales de la Faculté des sciences de Toulouse: Mathématiques_ , volume 9, pp. 245–303, 2000.
  * Mohri et al. (2018) Mohri, M., Rostamizadeh, A., and Talwalkar, A.  _Foundations of machine learning_.  MIT press, 2018.
  * Moosavi-Dezfooli et al. (2017) Moosavi-Dezfooli, S.-M., Fawzi, A., Fawzi, O., and Frossard, P.  Universal adversarial perturbations.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 1765–1773, 2017.
  * Neyshabur et al. (2017) Neyshabur, B., Bhojanapalli, S., McAllester, D., and Srebro, N.  Exploring generalization in deep learning.  _Advances in neural information processing systems_ , 30, 2017.
  * Ning et al. (2021) Ning, R., Li, J., Xin, C., and Wu, H.  Invisible poison: A blackbox clean label backdoor attack to deep neural networks.  In _IEEE Conference on Computer Communications_ , pp. 1–10. IEEE, 2021.
  * Saha et al. (2020) Saha, A., Subramanya, A., and Pirsiavash, H.  Hidden trigger backdoor attacks.  In _Proceedings of the AAAI conference on artificial intelligence_ , volume 34, pp. 11957–11965, 2020.
  * Sauer (1972) Sauer, N.  On the density of families of sets.  _Journal of Combinatorial Theory, Series A_ , 13(1):145–147, 1972.
  * Simonyan & Zisserman (2014) Simonyan, K. and Zisserman, A.  Very deep convolutional networks for large-scale image recognition.  _arXiv preprint arXiv:1409.1556_ , 2014.
  * Souri et al. (2022) Souri, H., Fowl, L., Chellappa, R., Goldblum, M., and Goldstein, T.  Sleeper agent: Scalable hidden trigger backdoors for neural networks trained from scratch.  _Advances in Neural Information Processing Systems_ , 35:19165–19178, 2022.
  * Szegedy et al. (2013) Szegedy, C., Zaremba, W., Sutskever, I., Bruna, J., Erhan, D., Goodfellow, I., and Fergus, R.  Intriguing properties of neural networks.  _arXiv preprint arXiv:1312.6199_ , 2013.
  * Tsai et al. (2021) Tsai, Y.-L., Hsu, C.-Y., Yu, C.-M., and Chen, P.-Y.  Formalizing generalization and robustness of neural networks to weight perturbations.  _arXiv preprint arXiv:2103.02200_ , 2021.
  * Turner et al. (2018) Turner, A., Tsipras, D., and Madry, A.  Clean-label backdoor attacks.  In _https://people.csail.mit.edu/madry/ lab/cleanlabel.pdf_ , 2018.
  * Valle-Pérez & A. Louis (2022) Valle-Pérez, G. and A. Louis, A.  Generalization bounds for deep learning.  _arXiv preprint arXiv:2203.14533_ , 2022.
  * Vapnik & Chervonenkis (2015) Vapnik, V. N. and Chervonenkis, A. Y.  On the uniform convergence of relative frequencies of events to their probabilities.  In _Measures of complexity: festschrift for alexey chervonenkis_ , pp. 11–30. Springer, 2015.
  * Vardi et al. (2022) Vardi, G., Shamir, O., and Srebro, N.  The sample complexity of one-hidden-layer neural networks.  _Advances in Neural Information Processing Systems_ , 35:9139–9150, 2022.
  * Wainwright (2019) Wainwright, M. J.  _High-dimensional statistics: A non-asymptotic viewpoint_ , volume 48.  Cambridge university press, 2019.
  * Wang et al. (2019) Wang, B., Yao, Y., Shan, S., Li, H., Viswanath, B., Zheng, H., and Zhao, B. Y.  Neural cleanse: Identifying and mitigating backdoor attacks in neural networks.  In _2019 IEEE Symposium on Security and Privacy (SP)_ , pp. 707–723. IEEE, 2019.
  * Wang & Ma (2022) Wang, M. and Ma, C.  Generalization error bounds for deep neural networks trained by sgd.  _arXiv preprint arXiv:2206.03299_ , 2022.
  * Wang et al. (2021) Wang, Y., Mianjy, P., and Arora, R.  Robust learning for data poisoning attacks.  In _International Conference on Machine Learning_ , 2021.
  * Wang et al. (2024) Wang, Y., Liu, S., and Gao, X.-S.  Data-dependent stability analysis of adversarial training.  _arXiv preprint arXiv:2401.03156_ , 2024.
  * Wei & Ma (2019) Wei, C. and Ma, T.  Data-dependent sample complexity of deep neural networks via lipschitz augmentation.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Xiao et al. (2022) Xiao, J., Fan, Y., Sun, R., Wang, J., and Luo, Z.-Q.  Stability analysis and generalization bounds of adversarial training.  _Advances in Neural Information Processing Systems_ , 35:15446–15459, 2022.
  * Xing et al. (2021) Xing, Y., Song, Q., and Cheng, G.  On the algorithmic stability of adversarial training.  _Advances in neural information processing systems_ , 34:26523–26535, 2021.
  * Yu et al. (2022) Yu, D., Zhang, H., Chen, W., Yin, J., and Liu, T.-Y.  Indiscriminate poisoning attacks are shortcuts.  _arXiv preprint arXiv:2111.00898_ , 2022.
  * Zeng et al. (2021a) Zeng, Y., Chen, S., Park, W., Mao, Z. M., Jin, M., and Jia, R.  Adversarial unlearning of backdoors via implicit hypergradient.  _arXiv preprint arXiv:2110.03735_ , 2021a.
  * Zeng et al. (2021b) Zeng, Y., Park, W., Mao, Z. M., and Jia, R.  Rethinking the backdoor attacks’ triggers: A frequency perspective.  In _Proceedings of the IEEE/CVF international conference on computer vision_ , pp. 16473–16481, 2021b.
  * Zeng et al. (2022) Zeng, Y., Pan, M., Just, H. A., Lyu, L., Qiu, M., and Jia, R.  Narcissus: A practical clean-label backdoor attack with limited information.  _arXiv preprint arXiv:2204.05255_ , 2022.
  * Zhong et al. (2020) Zhong, H., Liao, C., Squicciarini, A. C., Zhu, S., and Miller, D.  Backdoor embedding in convolutional neural network models via invisible perturbation.  In _Proceedings of the Tenth ACM Conference on Data and Application Security and Privacy_ , pp. 97–108, 2020.
  * Zhu et al. (2023a) Zhu, M., Wei, S., Shen, L., Fan, Y., and Wu, B.  Enhancing fine-tuning based backdoor defense with sharpness-aware minimization.  In _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , pp. 4466–4477, 2023a.
  * Zhu et al. (2023b) Zhu, Y., Yu, L., and Gao, X.-S.  Detection and defense of unlearnable examples.  _arXiv preprint arXiv:2312.08898_ , 2023b.

##  Appendix A Proof of Theorem 4.1

###  A.1 Prelinimaries

We first give some notation that will be used in all the proofs.

Subdistribution ${\mathcal{D}}_{S}^{\neq l_{p}}$. Let ${\mathcal{D}}_{S}^{\neq
l_{p}}$ be the distribution of samples whose label is not $l_{p}$, that is,

${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq l_{p}}}((x,y)\in
A)={\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}}((x,y)\in A|y\neq l_{p})$

for any set $A$.

Probability of samples to have label $y_{p}$. For a fixed $p$, let

${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}}(y=l_{p})=\eta\hbox{ and }0<\eta<1.$
(3)

General Hypothesis Space. In some theorems, we will consider the more general
hypothesis space

$H=\\{h(x,y):{\mathcal{S}}\times[m]\to[0,1]\\}.$

$H$ contains the commonly used hypothesis space
$\\{L({\mathcal{F}}(x),y):{\mathcal{S}}\times[m]\to[0,1]\\}$, where
${\mathcal{F}}$ is the network and $L$ is the loss function.

We give a classic generalization bound below, which will be used in the proof.

######  Theorem A.1 (P.217 of (Mohri et al., 2018), Informal).

Let the training set ${\mathcal{D}}_{{{\rm{tr}}}}$ be i.i.d. sampled from the
data distribution ${\mathcal{D}}_{S}$ and $N=|{\mathcal{D}}_{{{\rm{tr}}}}|.$
For the hypothesis space
${\mathcal{H}}=\\{L({\mathcal{F}}(x),y):{\mathbb{R}}^{n}\times[m]\to[0,1]\\}$
and $\delta\in{\mathbb{R}}_{+}$, with probability at least $1-\delta$, for any
$L({\mathcal{F}}(x),y)\in{\mathcal{H}}$, we have

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[L({\mathcal{F}}(x),y)]\leq{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}}[L({\mathcal{F}}(x),y)]+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}}_{N}({\mathcal{H}})+\sqrt{\frac{\ln(1/\delta)}{2N}}\\\
\end{array}$ (4)

We prove Theorem 4.1 in three steps given in Sections A.2, A.3, and A.4,
respectively.

###  A.2 Proof of Theorem A.2

We first prove the following theorem, which gives a generalization bound for a
more general hypothesis space.

######  Theorem A.2.

Let ${\mathcal{D}}_{S}$, ${\mathcal{D}}_{P}$, ${\mathcal{D}}_{S}^{l_{p}}$,
$\alpha$ be defined in Section 3 and ${\mathcal{D}}_{S}^{\neq l_{p}}$ be
defined in Section A.1. Then for any hypothesis space
$H=\\{h(x,y):{\mathcal{S}}\times[m]\to[0,1]\\}$, with probability at least
$1-\delta-\frac{4\eta}{4\eta+(1-\eta)N}-\frac{4(1-\eta)}{\eta N+4(1-\eta)}$,
for any $h\in H$, it holds

$\begin{array}[]{cc}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x,y)]\leq\frac{4-2\alpha}{1-\alpha}{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[h(x,y)]+4{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq
l_{p}}}_{N}(H)+\frac{4}{1-\alpha}{{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N}(H)}+2\sqrt{\frac{\ln(2/\delta)}{N(1-\alpha)}}.\end{array}$
(5)

As mentioned previously, the samples in ${\mathcal{D}}_{P}$ do not satisfy
“i.i.d. sampled from ${\mathcal{D}}_{{\mathcal{S}}}$”, and we will find a
subset of ${\mathcal{D}}_{{\mathcal{S}}}$, whose samples are i.i.d. sampled
from ${\mathcal{D}}_{{\mathcal{S}}}$. The core of the proof of theorem A.2 is
the following two lemmas, which show how to select such a subset.

######  Lemma A.3.

Use notations in Theorem A.2. Let $X$ be the random variable of the number of
samples with label $\neq l_{p}$ in ${\mathcal{D}}_{P}$. Let $k$ be a given
number in $\\{1,2,\dots,N\eta\\}$. If $X\geq k$, we randomly select $k$
samples without label $l_{p}$ in ${\mathcal{D}}_{P}$ and let $D_{l}$ be the
set of these samples; otherwise, let $D_{l}$ be the set of all samples without
label $l_{p}$ in ${\mathcal{D}}_{P}$. Let $D_{l}$ satisfy the distribution
${\mathcal{D}}_{S_{0}}$. Then we have
${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in A|X\geq
k)={\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in A)$ for any set $A$,
where $X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}$ means i.i.d. sampling $k$ data
from distribution ${\mathcal{D}}_{S}^{\neq l_{p}}$.

###### Proof.

By the Bayesian formula, we have

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X\geq k)\\\ =&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A,X\geq k)/{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(X\geq k)\\\
=&\sum_{i=k}^{N}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A,X=i)/{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(X\geq k)\\\
=&\sum_{i=k}^{N}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X=i){\mathbb{P}}(X=i)/{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(X\geq
k)\\\
=&\sum_{i=k}^{N}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X=i){\mathbb{P}}(X=i|X\geq k).\\\ \end{array}$ (6)

We will show that ${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X=i)={\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in A)$ for any
$i\geq k$, and hence the lemma.

Since the poison does not change labels, $X$ is also the number of samples
without label $l_{p}$ in ${\mathcal{D}}_{{{\rm{tr}}}}$. Then for any $i\geq
k$, when $X=i$, we will traverse all possible selection methods for $D_{l}$ to
calculate ${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in A|X=i)$.

Note that the $N$ samples in ${\mathcal{D}}_{{{\rm{tr}}}}$ are i.i.d samples
from ${\mathcal{D}}_{S}$. We will consider the order of these samples. Let
$(x_{j},y_{j})\in{\mathcal{D}}_{{{\rm{tr}}}}$ be the $j$-th element selected
from the distribution ${\mathcal{D}}_{\mathcal{S}}$. If we add poison to
$(x_{j},y_{j})$, then it becomes
$(x_{j}+{\mathcal{P}}(x_{j}),y_{j})\in{\mathcal{D}}_{P}$; if we do not add
poison to $(x_{j},y_{j})$, then $(x_{j},y_{j})\in{\mathcal{D}}_{P}$.

Let $D_{y\neq l_{p}}\subset[N]$ be the set of $k$ such
$(x_{k},y_{k})\in{\mathcal{D}}_{P}$ satisfying $y_{k}\neq l_{p}$. By
considering all the possible situations of $D_{y\neq l_{p}}$, we have

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X=i)\\\ =&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A,X=i)/{\mathbb{P}}(X=i)\\\ =&\sum_{{\mathcal{D}}_{y\neq
l_{p}},|{\mathcal{D}}_{y\neq
l_{p}}|=i}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A,{\mathcal{D}}_{y\neq l_{p}})/{\mathbb{P}}(X=i)\\\
=&\sum_{{\mathcal{D}}_{y\neq l_{p}},|{\mathcal{D}}_{y\neq
l_{p}}|=i}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|D_{y\neq l_{p}})\frac{{\mathbb{P}}({\mathcal{D}}_{y\neq
l_{p}})}{{\mathbb{P}}(X=i)}\\\ =&{\sum_{{\mathcal{D}}_{y\neq
l_{p}},|{\mathcal{D}}_{y\neq
l_{p}}|=i}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|D_{y\neq l_{p}})}/{C_{N}^{i}}.\\\ \end{array}$

Thus, for all ${\mathcal{D}}_{y\neq l_{p}}$ satisfying $|{\mathcal{D}}_{y\neq
l_{p}}|=i$, we traverse all the possibilities of the sample index
$\\{i_{1},i_{2},\dots,i_{k}\\}$ selected by ${\mathcal{D}}_{l}$ and then have

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|D_{y\neq l_{p}})\\\ =&\frac{\sum_{i_{1},i_{2},\dots,i_{k}\in D_{y\neq
l_{p}}}{\mathbb{P}}((x_{i_{1}},x_{i_{2}},\dots,x_{i_{k}})\in A)}{C_{i}^{k}}\\\
=&\frac{1}{C_{i}^{k}}\sum_{i_{1},i_{2},\dots,i_{k}\subset D_{y\neq
l_{p}}}{\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in A)\\\
=&{\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in A)\end{array}$

where $x_{i}$ are i.i.d. and $C_{a}^{b}$ is the combination number of
selecting $b$ samples from $a$ samples. We thus have:

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X=i)\\\ =&\frac{\sum_{{\mathcal{D}}_{y\neq l_{p},|{\mathcal{D}}_{y\neq
l_{p}}|=i}}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|D_{y\neq l_{p}})}{C_{N}^{i}}\\\ =&\frac{\sum_{{\mathcal{D}}_{y\neq
l_{p}},|{\mathcal{D}}_{y\neq
l_{p}}|=i}{\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in
A)}{C_{N}^{i}}\\\ =&{\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in
A).\end{array}$

Finally, we have

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X\geq k)\\\
=&\sum_{i=k}^{N}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in
A|X=i){\mathbb{P}}(X=i|X\geq k)\\\
=&\sum_{i=k}^{N}{\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in
A){\mathbb{P}}(X=i|X\geq k)\\\ =&{\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq
l_{p}}}\in A)\sum_{i=k}^{N}{\mathbb{P}}(X=i|X\geq k)\\\
=&{\mathbb{P}}(X_{k}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in A).\end{array}$

This proves the lemma. ∎

For samples with label $l_{p}$, we have the similar conclusion.

######  Lemma A.4.

Let $X$ be the random variable of the number of samples with label $l_{p}$ in
the set ${\mathcal{D}}_{P}$. Let $k$ to be a given number in
$\\{1,2,\dots,[N\eta]\\}$. If $X\geq k$, we randomly select $(1-\alpha)k$
samples without trigger but with label $l_{p}$ in ${\mathcal{D}}_{P}$, and let
these samples form the set $D_{l_{p}}$; otherwise, we select all samples
without trigger but with label $l_{p}$ in ${\mathcal{D}}_{P}$, and make these
samples the set $D_{l_{p}}$. Let $D_{l_{p}}$ obey the distribution
${\mathcal{D}}_{{\mathcal{S}}_{1}}$. Then we have
${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in A|X\geq
k)={\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in A)$
for any set $A$, where
$X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}$ means i.i.d. sample
$(1-\alpha)k$ samples from distribution
${\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}$.

###### Proof.

By the Bayesian formula, we have

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X\geq
k)=\sum_{i=k}^{N}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X=i){\mathbb{P}}(X=i|X\geq k).\\\ \end{array}$

The intermediate steps are similar to equation (6) in the proof of Lemma A.3,
so we omit them.

Now we prove ${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X=i)={\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A)$ for any $i\geq k$. Note that the $N$ samples in
${\mathcal{D}}_{{{\rm{tr}}}}$ are i.i.d selected from ${\mathcal{D}}_{S}$. Now
we will consider the order of these samples. Let
$(x_{j},y_{j})\in{\mathcal{D}}_{{{\rm{tr}}}}$ be the $j$-th element selected
from the distribution ${\mathcal{D}}_{\mathcal{S}}$. If we add poison to
$(x_{j},y_{j})$, then it becomes
$(x_{j}+{\mathcal{P}}(x_{j}),y_{j})\in{\mathcal{D}}_{P}$; if we do not add
poison to $(x_{j},y_{j})$, then $(x_{j},y_{j})\in{\mathcal{D}}_{P}$.

For any $i\geq k$, when $X=i$, there must be
$|{\mathcal{D}}_{l_{p}}|=(1-\alpha)k$. Let $D_{y=l_{p}}\subset[N]$ be the set
of $j$ such that $(x_{j},y_{j})\in{\mathcal{D}}_{P}$ satisfied $y_{j}=l_{p}$.
Now we consider all the possible situation of $D_{y=l_{p}}$:

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X=i)\\\ =&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A,X=i)/{\mathbb{P}}(X=i)\\\
=&\sum_{D_{y=l_{p}},|D_{y=l_{p}}|=i}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A,D_{y=l_{p}})/{\mathbb{P}}(X=i)\\\
=&\sum_{D_{y=l_{p}},|D_{y=l_{p}}|=i}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|D_{y=l_{p}}){\mathbb{P}}(D_{y=l_{p}})/{\mathbb{P}}(X=i)\\\
=&\sum_{D_{y=l_{p}},|D_{y=l_{p}}|=i}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|D_{y=l_{p}})/C_{N}^{i}.\\\ \end{array}$ (7)

Let $D^{poi}_{y=l_{p}}\subset[N]$ be the set of $j$ satisfying that $x_{j}$ is
a poisoned sample, and $D^{no\ poi}_{y=l_{p}}\subset[N]$ be the set of $j$
satisfying $(x_{j},y_{j})\in{\mathcal{D}}_{l_{p}}$. It is easy to see that
$D^{no\ poi}_{y=l_{p}},D^{poi}_{y=l_{p}}\subset D_{y=l_{p}}$. Then, for any
given $D_{y=l_{p}}$ such that $|D_{y=l_{p}}|=i$, we traverse all possibilities
of $D^{poi}_{y=l_{p}}$ and $D^{no\ poi}_{y=l_{p}}$ to calculate
${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in A|D_{y=l_{p}})$:

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|D_{y=l_{p}})\\\
=&\sum_{\\{i_{k}\\}_{k=1}^{i\alpha},\\{i_{j}\\}_{j=1}^{[N\eta](1-\alpha)}}{\mathbb{P}}(\\{i_{j}\\}_{j=1}^{[N\eta](1-\alpha)}\in
A){\mathbb{P}}(D^{poi}_{y=l_{p}}=\\{i_{k}\\}_{k=1}^{i\alpha},D^{no\
poi}_{y=l_{p}}=\\{i_{j}\\}_{j=1}^{[N\eta](1-\alpha)}|D_{y={l_{p}}})\\\
=&\sum_{\\{i_{k}\\}_{k=1}^{i\alpha},\\{i_{j}\\}_{j=1}^{[N\eta](1-\alpha)}}{\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A){\mathbb{P}}(D^{poi}_{y=l_{p}}=\\{i_{k}\\}_{k=1}^{i\alpha},D^{no\
poi}_{y=l_{p}}=\\{i_{j}\\}_{j=1}^{[N\eta](1-\alpha)}|D_{y={l_{p}}})\\\
=&{\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A)\sum_{\\{i_{k}\\}_{k=1}^{i\alpha},\\{i_{j}\\}_{j=1}^{[N\eta](1-\alpha)}}{\mathbb{P}}(D^{poi}_{y=l_{p}}=\\{i_{k}\\}_{k=1}^{i\alpha},D^{no\
poi}_{y=l_{p}}=\\{i_{j}\\}_{j=1}^{[N\eta](1-\alpha)}|D_{y={l_{p}}})\\\
=&{\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A).\\\ \end{array}$

The $x_{i}$ are i.i.d. and $C_{a}^{b}$ is the number of combinations to select
$b$ samples from $a$ samples. Substituting it into inequality (7), we have

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X=i)\\\
=&\sum_{D_{y=l_{p}},|D_{y=l_{p}}|=i}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|D_{y=l_{p}})/C_{N}^{i}\\\
=&\sum_{D_{y=l_{p}},|D_{y=l_{p}}|=i}{\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A)/C_{N}^{i}\\\
=&{\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A).\\\ \end{array}$

This is what we want. Finally, we have

$\begin{array}[]{ll}&{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X\geq k)\\\
=&\sum_{i=k}^{N}{\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X=i){\mathbb{P}}(X=i|X\geq k)\\\
=&\sum_{i=k}^{N}{\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A){\mathbb{P}}(X=i|X\geq k)\\\
=&{\mathbb{P}}(X_{(1-\alpha)k}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A).\end{array}$

The lemma is proved. ∎

Now, we prove Theorem A.2.

###### Proof.

By the Bayesian formula, we have

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x,y)]\\\
=&{\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}}(y=l_{p}){\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x,y)]+{\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}}(y\neq
l_{p}){\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq l_{p}}}[h(x,y)]\\\
=&\eta{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)]+(1-\eta){\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)].\end{array}$ (8)

Now we will separately estimate
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq l_{p}}}[h(x,y)]$ and
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x,y)]$.

Upper bound of ${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)]$. We give such a bound in the following Results (c1), (c2),
and (c3).

Result (c1): Let random variable $X$ be the number of samples with labels not
equal to $l_{p}$ in ${\mathcal{D}}_{{{\rm{tr}}}}$. Then with probability at
least $1-\frac{4\eta}{4\eta+N-N\eta}$, we have $X\geq N(1-\eta)/2$.

Let ${\mathcal{D}}_{{{\rm{tr}}}}=\\{(x_{i},y_{i})\\}_{i=1}^{N}$. Then
$X=\sum_{i=1}^{N}{\mathbf{1}}(y_{i}\neq l_{p})$, so
${\mathbb{E}}[X]={\mathbb{E}}[\sum_{i=1}^{N}{\mathbf{1}}(y_{i}\neq
l_{p})]=\sum_{i=1}^{N}{\mathbb{E}}[{\mathbf{1}}(y_{i}\neq l_{p})]=N(1-\eta)$,
and the variance
${\mathbb{V}}[X]={\mathbb{V}}[\sum_{i=1}^{N}{\mathbf{1}}(y_{i}\neq
l_{p})]=\sum_{i=1}^{N}{\mathbb{V}}[{\mathbf{1}}(y_{i}\neq
l_{p})]=N(1-\eta)\eta$, because ${\mathbf{1}}(y_{i}\neq l_{p})$ are
independent events. By the Cantelli inequality, we have ${\mathbb{P}}(X\leq
N(1-\eta)/2)\leq\frac{{\mathbb{V}}[X]}{{\mathbb{V}}[X]+({\mathbb{E}}[X]-(N(1-\eta)/2))^{2}}=\frac{4\eta}{4\eta+N-N\eta}$,
and Result (c1) is proved.

Result (c2): We randomly select $N(1-\eta)/2$ samples without label $l_{p}$ in
${\mathcal{D}}_{\mathcal{P}}$ and let $D_{l}$ be the set of these samples. If
the number of samples without label $l_{p}$ in ${\mathcal{D}}_{\mathcal{P}}$
is less than $N(1-\eta)/2$, then we select all samples without label $l_{p}$,
and let $D_{l}$ be the set of these samples.

Assuming that the set ${\mathcal{D}}_{l}$ obeys the distribution
${\mathcal{D}}_{{\mathcal{S}}_{0}}$, we have
${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{0}}}(x\in A|X\geq
N(1-\eta)/2)={\mathbb{P}}(X_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in
A)$ for any set $A$, where $X_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq l_{p}}}$
is the set of $N(1-\eta)/2$ data i.i.d. sampled from distribution
${\mathcal{D}}_{S}^{\neq l_{p}}$.

Following Lemma A.3, Result (c2) shows that when $X\geq N(1-\eta)/2$,
${\mathcal{D}}_{l}$ can be seen as i.i.d. sampled from
${\mathcal{D}}_{S}^{\neq l_{p}}$.

Result (c3): With probability $1-\frac{4\eta}{4\eta+N-N\eta}-\delta/2$, we
have

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)]\leq\frac{\sum_{(x,y)\in{\mathcal{D}}_{P}}h(x,y)}{N(1-\eta)/2}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq
l_{p}}}_{N(1-\eta)/2}(H)+\sqrt{\frac{\ln(2/\delta).}{N(1-\eta)}}.\end{array}$

$D\in({\mathbb{R}}^{n}\times[m])^{N(1-\eta)/2}$ is called a bad set, if
$|D|=N(1-\eta)/2$, and

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)]>\frac{\sum_{(x,y)\in
D}h(x,y)}{N(1-\eta)/2}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq
l_{p}}}_{N(1-\eta)/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N(1-\eta)}}\end{array}$
(9)

for some $f\in H$. Let $S_{b}=\\{D\|D\ \hbox{ is a bad set}\\}$.

By Theorem A.1, if the samples in ${\mathcal{D}}$ are i.i.d. sampled form
${\mathcal{D}}_{S}^{\neq l_{p}}$ and $|D|=N(1-\eta)/2$, then with probability
$1-\delta/2$, we have ${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)]\leq\frac{\sum_{(x,y)\in
D}h(x,y)}{N(1-\eta)/2}+2{\hbox{\rm{Rad}}}_{N(1-\eta)/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N(1-\eta)}}$
for any $f\in H$.

So by the definition of bad set, we have
${\mathbb{P}}(X_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq l_{p}}}\in
S_{b})\leq\delta/2$, where $X_{N(1-\eta)/2}^{{\mathcal{D}}_{S}^{\neq l_{p}}}$
is mentioned in result (c2). And by Result (c2), we have that: when $X\geq
N(1-\eta)/2$, we have ${\mathbb{P}}(D_{l}\in S_{b})\leq\delta/2$. Then, by
Result (c1), we have

$\begin{array}[]{ll}&{\mathbb{P}}(D_{l}\notin S_{b},X\geq N(1-\eta)/2)\\\
=&{\mathbb{P}}(D_{l}\notin S_{b}|X\geq N(1-\eta)/2){\mathbb{P}}(X\geq
N(1-\eta)/2)\\\ \geq&(1-\delta/2)(1-\frac{4\eta}{4\eta+N-N\eta})(by\ (c1))\\\
\geq&1-\delta/2-\frac{4\eta}{4\eta+N-N\eta}.\\\ \end{array}$

So, with probability at least $1-\delta/2-\frac{4\eta}{4\eta+N-N\eta}$,
$D_{l}$ is not in $S_{b}$ and $X\geq N(1-\eta)/2$. Hence,

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)]\\\ \leq&\frac{\sum_{(x,y)\in
D_{l}}h(x,y)}{N(1-\eta)/2}+2{\hbox{\rm{Rad}}}_{N(1-\eta)/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N(1-\eta)}}\\\
\leq&\frac{\sum_{(x,y)\in{\mathcal{D}}_{P}}h(x,y)}{N(1-\eta)/2}+2{\hbox{\rm{Rad}}}_{N(1-\eta)/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N(1-\eta)}}.\end{array}$

This is what we want.

The upper bound of
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x,y)]$.

We will give such a bound in Results (d1), (d2), and (d3) below, which are
similar to results (c1), (c2), (c3).

Result (d1): Let the random variable $X$ be the number of samples with label
$l_{p}$ in ${\mathcal{D}}_{{{\rm{tr}}}}$. Then with probability at least
$1-\frac{4(1-\eta)}{4(1-\eta)+N\eta}$, we have $X\geq N\eta/2$. The proof is
similar to that of Result (c1).

Result (d2): Now we evenly select $[N\eta(1-\alpha)/2]$ samples with label
$l_{p}$ in ${\mathcal{D}}_{\mathcal{P}}/{\mathcal{D}}_{poi}$ and make these
samples to form the set $D_{l_{p}}$. If the number of samples with label
$l_{p}$ in ${\mathcal{D}}_{\mathcal{P}}/\/D_{poi}$ is smaller than
$[N\eta(1-\alpha)/2]$, then we select all of these samples and add these
samples to $D_{l_{p}}$.

Assume that the set ${\mathcal{D}}_{l_{p}}$ obeys the distribution
${\mathcal{D}}_{{\mathcal{S}}_{1}}$. Then we have
${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}_{1}}}(x\in
A|X\geq[N\eta/2])={\mathbb{P}}(X_{[N\eta(1-\alpha)/2]}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A)$ for any set $A$, where
$X_{[N\eta(1-\alpha)/2]}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}$ is the set
that i.i.d. selecting $[N\eta(1-\alpha)/2]$ samples from distribution
${\mathcal{D}}_{S}^{\neq l_{p}}$.

Following Lemma A.4, Result (d2) shows that when $X\geq[N\eta/2]$, $D_{l_{p}}$
can be seen as i.i.d. samples from $D^{l_{p}}_{\mathcal{S}}$.

Result (d3): With probability $1-\frac{4-4\eta}{4(1-\eta)+N\eta}-\delta/2$, we
have

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x,y)]\leq\frac{\sum_{(x,y)\in{\mathcal{D}}_{P}}h(x,y)}{N(1-\alpha)\eta/2}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N(1-\alpha)\eta/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N(1-\alpha)\eta}}.\end{array}$

This is similar to Result (c3), but using (d1) and (d2) instead.

To obtain a bound of $E_{(x,y)\sim{\mathcal{D}}_{S}}[h(x,y)]$.

Using the fact
${\hbox{\rm{Rad}}}^{D}_{M}(H)\leq\frac{N}{M}{\hbox{\rm{Rad}}}^{D}_{N}(H)$ for
any $M\leq N$, distribution ${\mathcal{D}}$, hypothesis space $H$, and
applying (c3), (d3) to equation (8), we finally have

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x,y)]\\\
=&\eta{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x,y)]+(1-\eta){\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x,y)]\\\
\leq&\frac{4-2\alpha}{1-\alpha}\frac{\sum_{(x,y)\in{\mathcal{D}}_{P}}h(x,y)}{N}+4{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq
l_{p}}}_{N}(H)+4\frac{{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N}(H)}{1-\alpha}+\sqrt{\frac{\ln(2/\delta)(1-\eta)}{N}}+\sqrt{\frac{\ln(2/\delta)\eta}{N(1-\alpha)}}.\end{array}$
(10)

Then using $\eta<1$, we prove the theorem. ∎

###  A.3 Estimate Rademacher Complexity

In this section, we will estimate the Rademacher Complexities in Theorem A.2
when $H=\\{{\mathbf{1}}({\mathcal{F}}(x)\neq y)\\}$, where ${\mathcal{F}}$ is
a network with width $W$ and depth $D$. We first need a definition:

######  Definition A.5.

Let $H$ be a hypothesis space. Then the growth function $\Pi_{H}(N)$ of $H$ is
defined as:

$\Pi_{H}(N)=\max_{\\{x_{i}\\}_{i=1}^{N}}|\\{(h(x_{i}))_{i=1}^{N}\|h\in H\\}|.$

For a hypothesis space $H=\\{h:{\mathbb{R}}^{n}\to\\{-1,1\\}\\}$, we can
estimate its VCdim (Vapnik & Chervonenkis, 2015), and the relationship between
VCdim and growth function.

######  Lemma A.6 ((Bartlett et al., 2021, 2019)).

Let $H$ be the hypothesis space that satisfies: ${\mathcal{F}}\in H$ if and
only if ${\mathcal{F}}$ is a network with width not more than $W$ and depth
not more than $D$, and the activation function of each hidden layer of
${\mathcal{F}}$ is Relu, the output layer uses sign as activation function.
Then the VCdim of $H$ is $O(D^{2}W^{2})$.

######  Lemma A.7 ((Sauer, 1972)).

Let $H$ be the hypothesis space with VCdim $V$. Then for any $N\geq 1$, the
growth function satisfies $\Pi_{H}(N)\leq(eN)^{V}$.

######  Lemma A.8 ((Massart, 2000; Mohri et al., 2018)).

Let $H$ be the hypothesis space with growth function $\Pi_{H}$, and any
$h(x)\in H$ satisfy $|h(x)|\leq 1$ for any $x$. Then for any distribution
${\mathcal{D}}$, we have
${\hbox{\rm{Rad}}}^{\mathcal{D}}_{N}(H)=O(\sqrt{\frac{\ln(\Pi_{H})}{N}})$.

######  Lemma A.9 ((Mohri et al., 2018)).

Let $H$ be the hypothesis space, $q\in{\mathbb{R}}^{m}\to\\{0,1\\}$, and
$H_{q}=\\{q(h_{1}(x),h_{2}(x),\dots,h_{m}(x))\|h_{i}\in H\\}$. Then
$\Pi_{H_{q}}(N)\leq(\Pi_{H}(N))^{m}$.

Now, we calculate the Rademacher complexity of
$H=\\{{\mathbf{1}}(\widehat{{\mathcal{F}}}(x)\neq
y)\|{\mathcal{F}}\in{\mathcal{H}}_{W,D}\\}$:

######  Lemma A.10.

Let $H=\\{{\mathbf{1}}(\widehat{{\mathcal{F}}}(x)\neq
y):[0,1]^{n}\times[m]\to\\{0,1\\}\|{\mathcal{F}}\in{\mathcal{H}}_{W,D}\\}$.
Then, for any distribution ${\mathcal{D}}$, we have
${\hbox{\rm{Rad}}}^{\mathcal{D}}_{N}(H)=O(\sqrt{\frac{mW^{2}D^{2}}{N}})$.

###### Proof.

Let $H^{0}_{W,D}$ be defined as: ${\mathcal{F}}\in H^{0}_{W,D}$ if and only if
${\mathcal{F}}$ is a network with width $W$ and depth $D$, and the activation
function of each hidden layer of ${\mathcal{F}}$ is Relu, the output layer
does not use the activation function. And let
$H^{0}=\\{{\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq y)\|{\mathcal{F}}\in
H^{0}_{W,D}\\}$.

Let $H^{1}_{W,D}$ be defined as: ${\mathcal{F}}\in H^{1}_{W,D}$ if and only if
${\mathcal{F}}$ is a network with width $W$ and depth $D$, and the activation
function of each hidden layer of ${\mathcal{F}}$ is Relu, the output layer
uses the activation function sign.

Then we have that $H^{0}=\\{{\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq
y)\|{\mathcal{F}}\in
H^{0}_{W,D}\\}=\\{{\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq
y)\|{\mathcal{F}}\in{\mathcal{H}}_{W,D}\\}=H$ and
$\Pi_{H^{1}_{W,D}}(N)\leq(eN)^{O(D^{2}W^{2})}$ by Lemmas A.7 and A.6.

For any ${\mathcal{F}}\in H^{0}_{W,D}$, let
${\mathcal{F}}_{i,j}={\hbox{\rm{sign}}}({\mathcal{F}}_{i}-{\mathcal{F}}_{j})$,
where ${\mathcal{F}}_{i}$ is the $i$-th weight of ${\mathcal{F}}$. Then it is
easy to see that, ${\mathcal{F}}_{i,j}\in H^{1}_{W,D}$. Since
${\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq y)={\mathbf{1}}(-\sum_{j\neq
y}{\mathcal{F}}_{y,j}+(m-1)-0.1)$. By Lemma A.9, the growth function of
$H^{0}$ is $(eN)^{mO(D^{2}W^{2})}$; so by Lemma A.8 and $H^{0}=H$, the
Rademacher complexity ${\hbox{\rm{Rad}}}^{\mathcal{D}}_{N}(H)$ of $H$ is
$O(\sqrt{\frac{mD^{2}W^{2}}{N}})$ (ignore minor items). This proves the lemma.
∎

###  A.4 Proof for Theorem 4.1

Now we prove Theorem 4.1 by using Sections A.2 and A.3:

###### Proof.

Taking $H=\\{{\mathbf{1}}({\mathcal{F}}(x)\neq
y)\|{\mathcal{F}}\in{\mathcal{H}}_{W,D}\\}$ and substituting the Rademacher
complexity in Section A.3 into Theorem A.2, we prove Theorem 4.1. ∎

##  Appendix B Poison Impact Empirical Errors

In this appendix, we prove a proposition to support Remark 4.3. In Proposition
B.2 below, we show that if the poison ${\mathcal{P}}(x)$ is not satisfactory,
then it can result in a big empirical error.

######  Remark B.1.

Please note that the conclusion “poison implies big empirical error” only
holds in some situations. In fact, when ${\mathcal{P}}(x)$ is bounded, or the
network in the hypothesis space has a strong expressive ability, then the
conditions for the proposition in this section will not hold, so the poison
will not lead to big empirical error. In our experimental result in Section 6,
there is no need to consider the occurrence of large empirical error, because
we bound the trigger ${\mathcal{P}}(x)$ and use a large network.

Let ${\mathcal{D}}^{poi}$ be the distribution of poisoned data with label
$l_{p}$, that is,

${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}^{l_{p}}}(x+{\mathcal{P}}(x)\in
A)={\mathbb{P}}_{x\sim{\mathcal{D}}^{poi}}(x\in A)$

for any set $A$.

######  Proposition B.2.

Use the notation introduced in Theorem A.2 and let $\eta\leq 0.5$ be defined
in (3). We further assume that $h(x,y_{1})+h(x,y_{2})\geq 1$ for any $h\in H$,
$x\in{\mathbb{R}}^{n}$, $y_{1}\neq y_{2}$, and for some
$\tau,V\in{\mathbb{R}}_{+}$, it holds:
(1) ${\mathbb{P}}_{x\sim{\mathcal{D}}^{poi}}(x\in
A)\geq\tau{\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq l_{p}}}(x\in A)$ for
any set $A$;
(2) ${\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq l_{p}}}_{N}(H)\leq V$.
Let $Q=\eta^{N}\tau^{N\alpha}$, if $\alpha-\delta/Q>0$ and
$0.5-2\delta\alpha/Q-V\alpha>0$. Then with probability $\delta$, for any $h\in
H$ we have

${\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[h(x,y)]>\frac{0.5-2\delta\alpha/Q-V\alpha}{\alpha-\delta/Q}.$

First, we have the following lemma (Bertsekas & Tsitsiklis, 2008).

######  Lemma B.3.

If distributions $D_{1}$, $D_{2}$ and function $h$ satisfy
${\mathbb{P}}_{x\sim D_{1}}(h(x)\in A)\leq\lambda{\mathbb{P}}_{x\sim
D_{2}}(h(x)\in A)$ for any set $A$, then ${\mathbb{E}}_{x\sim
D_{1}}[f(h(x))]\leq\lambda{\mathbb{E}}_{x\sim D_{2}}[f(h(x))]$ for any bounded
and positive measurable function $f(x)$.

Then we prove the following lemma, which directly lead to Proposition B.2.

######  Lemma B.4.

Use the notations in Proposition B.2. We further assume that
$h(x,y_{1})+h(x,y_{2})\geq 1$ for any $h\in H$, $x\in{\mathbb{R}}^{n}$ and
$y_{1}\neq y_{2}$, and for some $\tau,V\in{\mathbb{R}}_{+}$, it holds:
(1): ${\mathbb{P}}_{x\sim{\mathcal{D}}^{poi}}(x\in
A)\geq\tau{\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq l_{p}}}(x\in A)$ for
all sets $A$, where $\tau\in{\mathbb{R}}_{+}$;
(2): with probability $1-\delta$, there exists an $h\in H$ such that
${\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[h(x,y)]\leq{\mathbf{\varepsilon}}$.
Then for any $K\leq N\alpha$, we have

$\begin{array}[]{l}{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq
l_{p}}}_{K}(H)\geq
0.5-N{\mathbf{\varepsilon}}/K-\frac{(2-N{\mathbf{\varepsilon}}/K)\delta\alpha}{\eta^{N}\tau^{K}}.\\\
{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq l_{p}}}_{N}(H)\geq
K(0.5-N{\mathbf{\varepsilon}}/K-\frac{(2-N{\mathbf{\varepsilon}}/K)\delta\alpha}{\eta^{N}\tau^{K}})/N.\\\
\end{array}$

###### Proof.

In order to calculate the probability easily in the proof, we treat
${\mathcal{D}}_{{{\rm{tr}}}}$ and ${\mathcal{D}}_{P}$ as ordered sets. Let
$(x_{i},y_{i})$ be the $i$-th element of ${\mathcal{D}}_{{{\rm{tr}}}}$.
${\mathcal{D}}_{P}$ is obtained from ${\mathcal{D}}_{{{\rm{tr}}}}$ as follows:
Let ${\mathcal{D}}_{P}={\mathcal{D}}_{{{\rm{tr}}}}$ first and if poison
${\mathcal{P}}(x_{i})$ is added to $(x_{i},y_{i})$ for some $i$, then replace
the $i$-th element of ${\mathcal{D}}_{{{\rm{tr}}}}$ by
$(x_{i}+{\mathcal{P}}(x_{i}),y_{i})$.

First, we give three notations:

(1): For the poisoned training set ${\mathcal{D}}_{P}$ and $q\in{\mathbb{N}}$,
we take the first $q$ clean samples without $l_{p}$ in ${\mathcal{D}}_{P}$ to
form a subset $F_{clean}(q,{\mathcal{D}}_{p})$, that is, if we write
${\mathcal{D}}_{{{\rm{tr}}}}=\\{(x_{i},y_{i})\\}_{i=1}^{N}$, then
$F_{clean}(q,{\mathcal{D}}_{P})=\\{(x_{i_{k}},y_{i_{k}})\\}_{k=1}^{q}$, where
$\\{i_{k}\\}_{i=1}^{q}$ is the smallest $q$ numbers in $[N]$ that satisfy
$y_{i_{k}}\neq l_{p}$, $(x_{i_{k}},y_{i_{k}})\in{\mathcal{D}}_{clean}$, and
$i_{a}<i_{b}$ if $a<b$.

(2): For the poisoned training set ${\mathcal{D}}_{P}$ and $q\in{\mathbb{N}}$,
we take the first $q$ poisoned samples in ${\mathcal{D}}_{P}$ to form the
subset $F_{poison}(q,{\mathcal{D}}_{p})$, that is, if we write
${\mathcal{D}}_{{{\rm{tr}}}}=\\{(x_{i},y_{i})\\}_{i=1}^{N}$, then
$F_{poison}(q,{\mathcal{D}}_{P})=\\{(x_{i_{k}}+{\mathcal{P}}(x_{i_{k}}),y_{i_{k}})\\}_{k=1}^{q}$,
$\\{i_{k}\\}_{i=1}^{q}$ is the smallest $q$ numbers in $[N]$ that satisfy
$y_{i_{k}}=l_{p}$,
$(x_{i_{k}}+{\mathcal{P}}(x_{i_{k}}),y_{i_{k}})\in{\mathcal{D}}_{poi}$, and
$i_{a}<i_{b}$ if $a<b$.

(3): For any given $K$ samples $\\{(x_{i},y_{i})\\}_{i=1}^{K}$ where
$y_{i}\neq l_{p}$ and a given set $S\subset[K]$, let $S_{i}$ be the $i$-th
minimum number in $S$, in particular, ${\mathcal{S}}_{1}$ is the minimum
number in $S$ and $S_{|S|}$ is the maximum number in $S$.

Second, we define a property of ${\mathcal{D}}_{P}$:

The poisoned training set ${\mathcal{D}}_{P}$ obtained by poisoning
${\mathcal{D}}_{{{\rm{tr}}}}$ is said to be nice-inclusion of a new dataset
${\mathcal{D}}_{G}$ if ${\mathcal{D}}_{G}={\mathcal{D}}_{T_{p}}\cup D_{T}$
such that $D_{T}\subset{\mathcal{D}}_{{{\rm{tr}}}}$,
$D_{T_{p}}\subset{\mathcal{D}}^{poi}$, and $\min_{h\in
H}\frac{1}{|{\mathcal{D}}_{P}|}\sum_{(x,y)\in{\mathcal{D}}_{P}}h(x,y)\leq{\mathbf{\varepsilon}}$.
For convenience, we write these conditions more explicitly as follows.

The poisoned training set ${\mathcal{D}}_{P}$ obtained by poisoning
${\mathcal{D}}_{{{\rm{tr}}}}=\\{(x^{\prime}_{i},y^{\prime}_{i})\\}_{i=1}^{N}$
is said to be nice-inclusion of the ordered dataset
${\mathcal{D}}_{G}=\\{(z_{i},l_{i})\\}_{i=1}^{K}$ and $S\subset[K]$ satsfying
$|[K]\setminus S|=|{\mathcal{D}}_{poi}|$, if
(e1): Let
$F_{clean}(|S|,{\mathcal{D}}_{P})=\\{(x^{\prime}_{i_{k}},y^{\prime}_{i_{k}})\\}_{k=1}^{|S|}$
such that $x^{\prime}_{i_{k}}=z_{S_{k}}$ and $y^{\prime}_{i_{k}}=l_{S_{k}}$
for any $k\in[S]$;
(e2): Let $F_{poison}(|[K]\setminus
S|,{\mathcal{D}}_{P})=\\{(x^{\prime}_{i_{k}}+{\mathcal{P}}(x^{\prime}_{i_{k}}),y^{\prime}_{i_{k}})\\}_{k=1}^{K-|S|}$.
There must be
$x^{\prime}_{i_{k}}+{\mathcal{P}}(x^{\prime}_{i_{k}})=z_{([K]\setminus
S)_{k}}$ for any $k\in[K-|S|]$.
(e3): $\min_{f\in
H}\sum_{(x,y)\in{\mathcal{D}}_{P}}\frac{h(x,y)}{|{\mathcal{D}}_{P}|}\leq{\mathbf{\varepsilon}}$.

We say that the poisoned training set ${\mathcal{D}}_{P}$ obtained by
poisoning
${\mathcal{D}}_{{{\rm{tr}}}}=\\{(x^{\prime}_{i},y^{\prime}_{i})\\}_{i=1}^{N}$
is said to be common-nice-inclusion of the ordered dataset
${\mathcal{D}}_{G}=\\{(z_{i},l_{i})\\}_{i=1}^{K}$ and $S\subset[K]$ satisfying
$|[K]\setminus S|=|{\mathcal{D}}_{poi}|$, if (e1) and (e2) hold.

Now, we define some functions:

Let $v_{i}\in\\{-1,1\\}$ for $i\in[K]$ and
$S((v_{i})_{i=1}^{K})=\\{i\|i\in[K],v_{i}<0\\}$. Given $K$ samples
$\\{(x_{i},y_{i})\\}_{i=1}^{K}$ where $y_{i}\neq l_{p}$, we define that
$S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((v_{i})_{i=1}^{K}))=1$, if there is a
nice-inclusion poison set ${\mathcal{D}}_{P}$ of
$\\{(x_{i},y_{i})\\}_{i=1}^{K}$ and $S((v_{i})_{i=1}^{K})$; otherwise
$S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((v_{i})_{i=1}^{K}))=0$. Then we have
the following results.

Result one: If $S_{i}({(x_{i},y_{i})}_{i=1}^{K},S((v_{i})_{i=1}^{K}))=1$ and
$y_{i}\neq l_{p}$, then $\sup_{f\in
H}\sum_{i\in[K]}v_{i}h(x_{i},y_{i})\geq\sum_{i=1}^{K}{\mathbf{1}}(v_{i}>0)-N{\mathbf{\varepsilon}}$.

Let ${\mathcal{D}}_{P}$ be a nice-inclusion of
${(x_{i},y_{i})}_{i=1}^{K},S((v_{i})_{i=1}^{K})$. Then

$\begin{array}[]{ll}&{\mathbf{\varepsilon}}\\\ \geq&\min_{f\in
H}\sum_{(x,y)\in{\mathcal{D}}_{P}}\frac{h(x,y)}{|{\mathcal{D}}_{P}|}(by\
(e3))\\\ \geq&\min_{f\in H}(\sum_{i\in
S((v_{i})_{i=1}^{K})}h(x_{i},y_{i}))/|{\mathcal{D}}_{P}|+(\sum_{i\in[K]/S((v_{i})_{i=1}^{K})}h(x_{i},l_{p}))/|{\mathcal{D}}_{P}|(by\
(e1,e2))\\\ \geq&\min_{f\in H}(\sum_{i\in
S((v_{i})_{i=1}^{K})}h(x_{i},y_{i}))/|{\mathcal{D}}_{P}|+(\sum_{i\in[K]/S((v_{i})_{i=1}^{K})}1-h(x_{i},y_{i}))/|{\mathcal{D}}_{P}|(by\
y_{i}\neq l_{p})\\\ =&\min_{f\in
H}(|[K]/S((v_{i})_{i=1}^{K})|-\sum_{i\in[K]}v_{i}h(x_{i},y_{i}))/|{\mathcal{D}}_{P}|\\\
=&(\sum_{i=1}^{K}{\mathbf{1}}(v_{i}>0)-\sup_{f\in
H}\sum_{i\in[K]}v_{i}h(x_{i},y_{i}))/|{\mathcal{D}}_{P}|\\\
=&(\sum_{i=1}^{K}{\mathbf{1}}(v_{i}>0)-\sup_{f\in
H}\sum_{i\in[K]}v_{i}h(x_{i},y_{i}))/N.\\\ \end{array}$

The result is proved.

Result Two: In order to give the lower bound of the Rademacher complexity
${\hbox{\rm{Rad}}}^{{\mathcal{D}}^{l}}_{K}(H)$, we just need to consider the
upper bound of ${\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))\neq
1)]$ for each $(\sigma_{i})_{i=1}^{K}\subset\\{-1,1\\}^{K}$.

Let $\sigma_{i}$ be Rademacher random variables, that is
$P(\sigma_{i}=1)=P(\sigma_{i}=-1)=0.5$. Then, by the definition of Rademacher
complexity, we have

$\begin{array}[]{ll}&{\hbox{\rm{Rad}}}^{{\mathcal{D}}^{l}}_{K}(H)\\\
=&{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbb{E}}_{\sigma_{i}}[\sup_{f\in
H}\frac{\sum_{i=1}^{K}\sigma_{i}h(x_{i},y_{i})}{K}]]\\\
=&{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[\sum_{\sigma_{i}}\sup_{f\in
H}\frac{\sum_{i=1}^{K}\sigma_{i}h(x_{i},y_{i})}{2^{K}K}]\\\
\geq&{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[\sum_{\sigma_{i}}{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))=1)\frac{\sum_{i=1}^{K}{\mathbf{1}}(\sigma_{i}>0)-N{\mathbf{\varepsilon}}}{2^{K}K}\\\
&-{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))\neq
1)\frac{1}{2^{K}}]\\\
\geq&{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[\sum_{\sigma_{i}}\frac{\sum_{i=1}^{K}{\mathbf{1}}(\sigma_{i}>0)-N{\mathbf{\varepsilon}}}{2^{K}K}-{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))\neq
1)\frac{2K-N{\mathbf{\varepsilon}}}{2^{K}K}]\\\
=&0.5-N{\mathbf{\varepsilon}}/K-{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[\sum_{\sigma_{i}}{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))\neq
1)\frac{2K-N{\mathbf{\varepsilon}}}{2^{K}K}].\end{array}$

The first inequality uses Result one. So, if we want to give a lower bound of
${\hbox{\rm{Rad}}}^{{\mathcal{D}}^{l}}_{K}(H)$, we just need to give an upper
bound of ${\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[\sum_{\sigma_{i}}{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))\neq
1)]$. Furthermore, we just need to consider
${\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))\neq
1)]$ for each $(\sigma_{i})_{i=1}^{K}$. Result two is proved.

Result Three: Now, we prove
${\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((v_{i})_{i=1}^{K}))\neq
1)]<\frac{\delta}{\eta^{N}\tau^{K}}$ for any
$(v_{i})_{i=1}^{K}\in\\{-1,1\\}^{K}$.

For a given $(v_{i})_{i=1}^{K}\in\\{-1,1\\}^{K}$, let set
$C_{(v_{i})_{i=1}^{K}}=\\{\\{(x_{i},y_{i})\\}_{i=1}^{K}|S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((v_{i})_{i=1}^{K}))\neq
1,y_{i}\neq l_{p}\\}$, then
${\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}(S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((v_{i})_{i=1}^{K}))\neq
1)]={\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}(\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}})]$.

For $(v_{i})_{i=1}^{K}\in\\{-1,1\\}^{K}$ and $\\{(x_{i},y_{i})\\}_{i=1}^{K}$,
let ${\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}$ be the
set of ${\mathcal{D}}_{P}$, which is a common-nice-inclusion for
$\\{(x_{i},y_{i})\\}_{i=1}^{K}$ and $S((v_{i})_{i=1}^{K})$. It is easy to see
that:
(r1):
${\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{((x_{i},y_{i}))_{i=1}^{K}}\cap{\mathbb{E}}_{(v^{\prime}_{i})_{i=1}^{K}}^{((x^{\prime}_{i},y^{\prime}_{i}))_{i=1}^{K}}=\phi$
when $v_{i}\neq v^{\prime}_{i}$ for some $i\in[K]$ or $x_{i}\neq
x^{\prime}_{i}$ for some $i\in[K]$.
(r2): If
${\mathcal{D}}_{P}\in{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}$
satisfies (e3), then
$S_{i}(\\{(x_{i},y_{i})\\}_{i=1}^{K},S((v_{i})_{i=1}^{K}))=1$.

So by (r2), if $\\{(x_{i},y_{i})\\}_{i=1}^{K}\in C_{(v_{i})_{i=1}^{K}}$, then
for any
${\mathcal{D}}_{P}\in{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}$,
(e3) cannot stand. Let the set $B$ contain all the ${\mathcal{D}}_{P}$ that do
not satisfy (e3). Then, if $\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}}$, there must be
${\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{{(x_{i},y_{i})}_{i=1}^{K}}\subset B$.

Now we prove the following two results:

Result S1:
$\int_{{\mathcal{D}}_{P}}{\mathbf{1}}(D\in\bigcup_{\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}}}{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}){\hbox{\rm{d}}}D<\delta$.

By (r1) and
${\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{{(x_{i},y_{i})}_{i=1}^{K}}\subset B$ for
all $\\{(x_{i},y_{i})\\}_{i=1}^{K}\in C_{(v_{i})_{i=1}^{K}}$, we have that:

${\mathbf{1}}(D\in
B)\geq{\mathbf{1}}({\mathcal{D}}\in\bigcup_{\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}}}{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}})$

So
$\int_{{\mathcal{D}}_{P}}{\mathbf{1}}({\mathcal{D}}\in\bigcup_{\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}}}{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}){\hbox{\rm{d}}}D\leq\int_{{\mathcal{D}}_{P}}{\mathbf{1}}({\mathcal{D}}\in
B){\hbox{\rm{d}}}D\leq\delta$, using condition (2) of the theorem here.

Result S2:
$\int_{{\mathcal{D}}_{P}}{\mathbf{1}}(D\in\bigcup_{\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}}}{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}){\hbox{\rm{d}}}D\geq{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}((x_{i},y_{i})\in
C_{(v_{i})_{i=1}^{K}})]\eta^{N}\tau^{K}/\alpha$.

Consider the definition of $F_{clean}$ and ${\mathcal{F}}_{poison}$ in (e1)
and (e2). When
$D_{p}\in{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}$,
the first $\sum_{i=1}^{K}{\mathbf{1}}(v_{i}<0)$ samples without label $l_{p}$
in ${\mathcal{D}}_{{{\rm{tr}}}}$ must be $\\{(x_{i_{k}},y_{i_{k}})\\}$, where
$i_{k}$ satisfies $v_{i_{k}}=-1$; and
${\mathcal{D}}_{poi}=\\{(x_{i_{k}},y_{i_{k}})\\}$, where $i_{k}$ satisfies
$v_{i_{k}}=1$. Let $N_{0}=\sum_{i=1}^{K}{\mathbf{1}}(v_{i}<0)$, then

$\begin{array}[]{ll}&\int_{{\mathcal{D}}_{P}}{\mathbf{1}}(D\in\bigcup_{\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}}}{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}){\hbox{\rm{d}}}D\\\
=&\int_{({\mathcal{D}}_{S}^{\neq
l_{p}})^{N_{0}}({\mathcal{D}}_{poi})^{K-N_{0}}}{\mathbf{1}}(\\{(x_{i},y_{i})\\}\in
C_{(v_{i})_{i=1}^{K}})(\sum_{q=0}^{N}{\mathbf{1}}([q\alpha]=K-N_{0})C_{N}^{q}\eta^{q}(1-\eta)^{N-q}){\hbox{\rm{d}}}(x_{i},y_{i})\\\
\geq&\int_{({\mathcal{D}}_{S}^{\neq
l_{p}})^{N_{0}}({\mathcal{D}}_{poi})^{K-N_{0}}}{\mathbf{1}}(\\{(x_{i},y_{i})\\}\in
C_{(v_{i})_{i=1}^{K}})(\sum_{q=0}^{N}{\mathbf{1}}([q\alpha]=K-N_{0})\eta^{N}){\hbox{\rm{d}}}(x_{i},y_{i})\\\
\geq&\int_{({\mathcal{D}}_{S}^{\neq
l_{p}})^{N_{0}}({\mathcal{D}}_{poi})^{K-N_{0}}}{\mathbf{1}}(\\{(x_{i},y_{i})\\}\in
C_{(v_{i})_{i=1}^{K}})(\eta^{N}/\alpha){\hbox{\rm{d}}}(x_{i},y_{i})\\\
\geq&\int_{({\mathcal{D}}_{S}^{\neq l_{p}})^{K}}{\mathbf{1}}((x_{i},y_{i})\in
C_{(v_{i})_{i=1}^{K}})\eta^{N}\tau^{K}/\alpha{\hbox{\rm{d}}}(x_{i},y_{i})\\\
=&{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}((x_{i},y_{i})\in
C_{(v_{i})_{i=1}^{K}})]\eta^{N}\tau^{K}/\alpha.\end{array}$

The first inequality uses $\eta\leq 0.5$ and $C_{N}^{i}\geq 1$. The second
inequality uses at least $1/\alpha$ numbers of $q\in[N]$ such that
$[q\alpha]=K-N_{0}$. The last inequality uses Lemma B.3 and condition (1) in
theorem. This proves Result S2.

Finally, by Result S1 and Result S2, we have
$(\eta^{N}\tau^{K}/\alpha){\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}(\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}})]\leq\int_{{\mathcal{D}}_{P}}{\mathbf{1}}(D\in\bigcup_{\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}}}{\mathbb{E}}_{(v_{i})_{i=1}^{K}}^{\\{(x_{i},y_{i})\\}_{i=1}^{K}}){\hbox{\rm{d}}}D\leq\delta$,
that is, ${\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[{\mathbf{1}}(\\{(x_{i},y_{i})\\}_{i=1}^{K}\in
C_{(v_{i})_{i=1}^{K}})]\leq\alpha\delta/(\eta^{N}\tau^{K})$.

Prove the lemma. Use Results three and two, we have

$\begin{array}[]{ll}&{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{\neq
l_{p}}}_{K}(H)\\\
\geq&0.5-N{\mathbf{\varepsilon}}/K-{\mathbb{E}}_{(x_{i},y_{i})\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[\sum_{\sigma_{i}}{\mathbf{1}}(S_{i}(((x_{i},y_{i}))_{i=1}^{K},S((\sigma_{i})_{i=1}^{K}))\neq
1)\frac{2K-N{\mathbf{\varepsilon}}}{2^{K}K}]\\\
\geq&0.5-N{\mathbf{\varepsilon}}/K-\frac{(2-N{\mathbf{\varepsilon}}/K)\delta\alpha}{\eta^{N}\tau^{K}}.\end{array}$

Since
${\hbox{\rm{Rad}}}^{D}_{M}(H)\leq\frac{N}{M}{\hbox{\rm{Rad}}}^{D}_{N}(H)$ for
any $M\leq N$ and distribution $D$, the lemma is proved. ∎

Now we use Lemma B.4 to prove Proposition B.2:

###### Proof.

Use reduction to absurdity. Assume that with probability at least $1-\delta$,
there is
${\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[h(x,y)]\leq\frac{0.5-2\delta\alpha/Q-V\alpha}{\alpha-\delta/Q}$,
and take the right-hand size value as $\epsilon$.

By Lemma B.4, take $K=N\alpha$. Then
${\hbox{\rm{Rad}}}_{N}^{{\mathcal{D}}_{\mathcal{S}}^{\neq
l_{p}}}\geq(0.5-N\epsilon/K-\frac{(2-N\epsilon/K)\delta\alpha}{\eta^{N}\tau^{K}})/\alpha$.
We substitute $\epsilon$ in it. Then

$\begin{array}[]{ll}&{\hbox{\rm{Rad}}}_{N}^{{\mathcal{D}}_{\mathcal{S}}^{\neq
l_{p}}}\\\
\geq&(0.5-N\epsilon/K-\frac{(2-N\epsilon/K)\delta\alpha}{\eta^{N}\tau^{K}})/\alpha\\\
=&1/\alpha(0.5-\frac{2\delta\alpha}{Q}-\epsilon(\alpha-\delta/Q))\\\
=&1/\alpha(0.5-\frac{2\delta\alpha}{Q}-\frac{0.5-2\delta\alpha/Q-V\alpha}{\alpha-\delta/Q}(\alpha-\delta/Q))\\\
=&1/\alpha(0.5-\frac{2\delta\alpha}{Q}-(0.5-2\delta\alpha/Q-V\alpha))\\\
=&1/\alpha(V\alpha)\\\ =&V.\end{array}$

So ${\hbox{\rm{Rad}}}_{N}^{{\mathcal{D}}_{\mathcal{S}}^{\neq l_{p}}}\geq V$,
which is contradictory to (2) in Proposition B.2, and the proposition is
proved. ∎

##  Appendix C Optimality of the Generalization Bound

In this section, we show that for the general hypothesis space and data
distribution, the generalization gap between the empirical error and the
population error cannot be smaller than $O(\frac{1}{\sqrt{N}})$, mentioned in
Remark 4.4.

######  Proposition C.1.

Let $m=2$ and the data distribution ${\mathcal{D}}_{{\mathcal{S}}}$ satisfy
$P_{(x,y)\sim{\mathcal{D}}_{S}}(y=1)=P_{(x,y)\sim{\mathcal{D}}_{S}}(y=0)=0.5$.
Let ${\mathcal{H}}=\\{L({\mathcal{F}}(x),y)\\}$ be the hypothesis space,
$L({\mathcal{F}}(x),y)={\mathbf{1}}(\widehat{\mathcal{F}}(x)\neq y)$ the loss
function, and ${\mathcal{F}}_{0}$ a neural network classifying
$\widehat{{\mathcal{F}}}_{0}(x)=0$ for
$(x,y)\sim{\mathcal{D}}_{{\mathcal{S}}}$. Then for any $c>0$, $k>0.5$, and
${\mathcal{D}}_{{{\rm{tr}}}}$ i.i.d. sampled from
${\mathcal{D}}_{{\mathcal{S}}}$ with $|{\mathcal{D}}_{{{\rm{tr}}}}|=N$, we
have

${\mathbb{P}}(|{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[L({\mathcal{F}}_{0}(x),y)]-{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}}[L({\mathcal{F}}_{0}(x),y)]|<\frac{c}{N^{k}})=O({c}{N^{0.5-k}}).$

###### Proof.

First, we have
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[L({\mathcal{F}}_{0}(x),y)]={\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[{\mathbf{1}}(y=1)]=0.5$.
Then we have
${\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}}[L({\mathcal{F}}_{0}(x),y)]={\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}}[{\mathbf{1}}(y=1)]=N_{1}/N$,
where $N_{1}$ is the number of $x$ with label 1 in
${\mathcal{D}}_{{{\rm{tr}}}}$. So,
${\mathbb{P}}(|{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[L({\mathcal{F}}_{0}(x),y)]-{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{{{\rm{tr}}}}}[L({\mathcal{F}}_{0}(x),y)]|<\frac{c}{N^{k}})={\mathbb{P}}(|0.5-N_{1}/N|<\frac{c}{N^{k}})$.

To estimate ${\mathbb{P}}(|0.5-N_{1}/N|<\frac{c}{N^{k}})$, we only need to
calculate the probability of $N_{1}\in(0.5N-cN^{1-k},0.5N+cN^{1-k})$. Since
${\mathcal{D}}_{{{\rm{tr}}}}$ is i.i.d. sampled from
${\mathcal{D}}_{{\mathcal{S}}}$, a sample labeled 1 is selected with
probability 0.5. Thus,

$\begin{array}[]{ll}&{\mathbb{P}}(N_{1}\in(0.5N-cN^{1-k},0.5N+cN^{1-k}))\\\
\leq&\sum_{i=0.5N-cN^{1-k}}^{0.5N+cN^{1-k}}C_{N}^{i}0.5^{N}\\\
\leq&2cN^{1-k}C_{N}^{N/2}0.5^{N}.\\\ \end{array}$

When $N\to\infty$, using Stirling’s approximation to calculate the
$C_{N}^{N/2}$, we have

$\begin{array}[]{ll}&{\mathbb{P}}(N_{1}\in(0.5N-cN^{1-k},0.5N+cN^{1-k}))\\\
\leq&2cN^{1-k}C_{N}^{N/2}0.5^{N}\\\ =&2cN^{1-k}0.5^{N}O(\frac{\sqrt{2\pi
N}(N/e)^{N}}{\pi N(N/(2e))^{N}})\\\ =&O(cN^{0.5-k}).\end{array}$

The proposition is proved. ∎

It is easy to see that $O({c}{{N^{0.5-k}}})\to 0$ when $N\to\infty$, so by
Proposition C.1, the generalization gap cannot be smaller than
$O(\frac{1}{\sqrt{N}})$. Together with Theorem A.1, we show the optimality of
$O(\frac{1}{\sqrt{N}})$ of the generalization gap for a clean dataset.

This is also for the generalization bound under poison attacks, because the
proof of Theorem 4.1 need the generalization bound Theorem A.1 for the
dataset.

##  Appendix D Proof of Theorem 4.5

We provide a more intuitive explanation on how to estimate the poison
generalization bound in Theorem 4.5, which is the core of our theorem.

Based on research on indiscriminate poisoning, neural networks always
prioritize learning simple features, i.e., shortcut. So we try to make the
trigger to be a shortcut (as said in condition (c3) in Theorem 4.5 and
Proposition 4.10).

However, only a few samples were poisoned in the backdoor attack, which is
different from the setting of indiscriminate poisoning, so only using shortcut
cannot establish the bound. Therefore, we aim to disrupt the original features
of the poisoned images, such that the classification of the poisoned images
and the classification of clean images become two independent tasks for the
network (as said in condition (c1) in Theorem 4.5). By doing so, when the
network completes the task of classifying poison data, the clean part of the
data set is useless, and the network will learn the feature in the poison part
of data, so that the shortcut can be learned.

Finally, if the shortcuts are similar for different images, the shortcuts
learned on a small portion of the data can be generalized to all the data (as
said in condition (c2) in Theorem 4.5).

By the above idea, we will prove a more general form of Theorem 4.5, as shown
below, and Theorem 4.5 is an easy corollary of this theorem.

######  Theorem D.1.

Use the notation in Section 3. Let $N=|{\mathcal{D}}_{{{\rm{tr}}}}|$. For any
two hypothesis spaces ${\mathcal{H}}\subset{\mathcal{H}}_{W,D}$ and
$F\subset{\mathcal{H}}_{W,D}$, if ${\mathcal{P}}(x)$ satisfies the following
conditions for some $\epsilon>0,\tau>0,\lambda\geq 1$:
(c1):
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}[f_{y}(x+{\mathcal{P}}(x))]\leq\epsilon$
for all $f\in F$,
(c2):
${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{{\mathcal{S}}}}({\mathcal{P}}(x)\in
A|y\neq l_{p})\leq\lambda$
${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{{\mathcal{S}}}}$ $({\mathcal{P}}(x)\in
A|y=l_{p})$ for any set $A$,
(c3): some $h\in H$ satisfies that: $\exists f\in F$ such that
${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(h-f)_{l_{P}}({\mathcal{P}}(x))-(h-f)_{l_{p}}(x+{\mathcal{P}}(x))|]\leq\tau$,
where $(h-f)_{l_{P}}(x)=h_{l_{P}}(x)-f_{l_{p}}(x)$,
then with probability at least $1-\delta-O(1/N)$, the following inequality
holds for all $h\in H$ satisfying (c3):

$\begin{array}[]{ll}&{\mathcal{E}}_{P}(h,{\mathcal{D}}_{{\mathcal{S}}})\leq\lambda
O(\frac{1}{\alpha}({\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[L_{CE}(h(x),y)]+{\hbox{\rm{Rad}}}_{N}^{{\mathcal{D}}_{S}^{l_{p}}}({\mathcal{H}}_{W,D,1}))+\sqrt{\frac{\ln(1/\delta)}{N\alpha}}+\epsilon+\tau+\frac{\lambda-1}{\lambda}).\end{array}$
(11)

It is easy to see that we just need to take the hypothesis spaces $H,F$ in
Theorem D.1 to be $H=\\{{\mathcal{F}}(x)\\}$ and $F=\\{{\mathcal{G}}(x)\\}$
(i.e. hypothesis space just contains only one network). Then Theorem D.1
naturally equivalent to Theorem 4.5.

###  D.1 Proof of Theorem D.2

We give the following theorem, which is a generalization bound theory under
more general hypothesis space.

######  Theorem D.2.

For any two hypothesis spaces
$H=\\{h(x,y)\in{\mathcal{S}}\times[m]\to[0,1]\\},F=\\{f(x,y)\in{\mathcal{S}}\times[m]\to[0,1]\\}$,
if ${\mathcal{P}}(x)$ satisfies the following conditions for some
$\epsilon>0,\tau>0,\lambda\geq 1$:
(1)
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}[f(x+{\mathcal{P}}(x),y)]\geq
1-\epsilon$ for any $f\in F$,
(2) ${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}({\mathcal{P}}(x)\in
A)\leq\lambda{\mathbb{P}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}({\mathcal{P}}(x)\in
A)$ for any set $A$,
(3) Some $h\in H$ satisfies that there exists an $f\in F$ such that
${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(h-f)({\mathcal{P}}(x),l_{p})-(h-f)(x+{\mathcal{P}}(x),l_{p})|]\leq\tau$,
where $(h-f)(x)=h(x)-f(x)$,
then with probability at least $1-\delta-\frac{4-4\eta}{4-4\eta+\eta N}$, for
any $h\in H$ satisfying (3), we have:

$\begin{array}[]{l}{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]\leq\lambda(2{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}h(x,y)/(\alpha\eta)+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}+\tau/\eta+\epsilon)+\tau+(\lambda-1)\eta.\end{array}$
(12)

We will use Theorem D.2 to prove Theorem D.1 in Section D.2. Now, we prove
Theorem D.2 and give a detailed explanation of the “proof idea” of Theorem
4.5. Please note that, in the proof of Theorem D.2, the poison generalization
error is
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]$.

###### Proof.

The proof is divided into two parts.

Part one, we estimate the upper bound of
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x+{\mathcal{P}}(x),l_{p})]$.
This part corresponds to the “firstly” part in the proof idea shown under
Theorem 4.5.

We first give three bounds in the following Results (e1), (e2), and (e3).
Since (e1), (e2), (e3) are similar to (d1), (d2), (d3) in the proof of Theorem
A.2, we omitted the proof.

Result (e1): Let the random variable $X$ be the number of samples with label
$l_{p}$ in ${\mathcal{D}}_{\mathcal{P}}$. Then with probability at least
$1-\frac{4(1-\eta)}{4-4\eta+N\eta}$, it holds $X\geq N\eta/2$.

Result (e2): Now we even randomly select $N\eta\alpha/2$ poisoned samples in
${\mathcal{D}}_{P}$. If the number of poisoned samples in ${\mathcal{D}}_{P}$
is smaller than $N\eta\alpha/2$, then we let $D_{l_{p}}$ be the set of all
such samples.

Let ${\mathcal{D}}_{l_{p}}$ obey the distribution
${\mathcal{D}}_{{\mathcal{S}}2}$. Then we have
${\mathbb{P}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}2}}(x\in
A|X\geq[N\eta/2])=P(X_{N\eta\alpha/2}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}\in
A)$ for any set $A$, where
$X_{N\eta\alpha/2}^{{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}$ is the set that
i.i.d. sampled $N\eta\alpha/2$ data from distribution
${\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}$, and add ${\mathcal{P}}(x)$ to each
data.

Result (e3): With probability $1-\frac{4-4\eta}{4-4\eta+N\eta}-\delta/2$, for
any $h\in H$, we have

${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x+{\mathcal{P}}(x),l_{p})]\leq\frac{\sum_{(x,y)\in{\mathcal{D}}_{poi}}h(x,y)}{N\alpha\eta/2}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}.$

We use
${\mathcal{D}}_{poi}=\\{(x+{\mathcal{P}}(x),l_{p})\|(x,l_{p})\in{\mathcal{D}}_{sub}\\}$,
Result (e1), and Result (e2) to prove Result (e3). The concrete steps are
similar to that of Result (c3). ${\mathcal{D}}_{poi}$ and
${\mathcal{D}}_{sub}$ are defined in Section 3.2.

Part two, estimate the upper bound of
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]$.

Please note that when $y\neq l_{p}$, $h(x+{\mathcal{P}}(x),l_{p})$ will not
appear in the empirical error
${\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[h(x+{\mathcal{P}}(x),y)]$, so we
need to use some other methods to estimate
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]$.

For any $h\in H$ and $f\in F$, let $c_{h,f}(x)=h(x,l_{p})-f(x,l_{p})$. Let $Q$
be the upper bound mentioned in Result (e3) in Part one.

The upper bound of ${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[h(x+{\mathcal{P}}(x),l_{p})]$ will be given by the following Results
(f1), (f2), (f3), and (f4). Note that (f1) and (f2) correspond to the
“Secondly” step in the proof idea shown under the Theorem 4.5; (f3) and (f4)
correspond to the “Finally” step in the proof idea shown under the Theorem
4.5.

Result (f1): If $f\in F$ and $h\in H$ satisfy (3), then we have
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}({\mathcal{P}}(x))]\leq
Q+\tau/\eta-(1-{\mathbf{\varepsilon}})$.

By condition (3), we have:

$\begin{array}[]{ll}&\tau\\\
\geq&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[|c_{h,f}({\mathcal{P}}(x))-c_{h,f}(x+{\mathcal{P}}(x))|](use\
(3))\\\
\geq&\eta({\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[|c_{h,f}({\mathcal{P}}(x))-c_{h,f}(x+{\mathcal{P}}(x))|])\\\
\geq&\eta({\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}({\mathcal{P}}(x))-c_{h,f}(x+{\mathcal{P}}(x))]).\\\
\end{array}$ (13)

Now by condition (1) and Result (e3), with probability $1-\delta$, we have

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}(x+{\mathcal{P}}(x))]\\\
=&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[h(x+{\mathcal{P}}(x),l_{p})]-{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[f(x+{\mathcal{P}}(x),l_{p})]\\\
\leq&Q-(1-\epsilon).\end{array}$ (14)

Combine inequalities (13) and (14), we have:

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}({\mathcal{P}}(x))]\\\
\leq&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}(x+{\mathcal{P}}(x))]+\tau/\eta\\\
\leq&Q-(1-\epsilon)+\tau/\eta.\end{array}$ (15)

Result (f1) is proved.

Result (f2): ${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[c_{h,f}({\mathcal{P}}(x))+1]\leq\lambda{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}({\mathcal{P}}(x))+1]$.

Result (f2) can be proved by using Lemma B.3 and condition (2).

Result (f3): When $h\in H$ and $f\in F$ satisfy condition (3), we have
${\mathbb{E}}_{{\mathcal{D}}_{S}}[c_{h,f}(x+{\mathcal{P}}(x))]\leq(\eta+(1-\eta)\lambda)(Q+\epsilon+\tau/\eta-1)+\lambda-1+\tau$.

By condition (3), we have

$\begin{array}[]{ll}&\tau\\\
\geq&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[|c_{h,f}({\mathcal{P}}(x))-c_{h,f}(x+{\mathcal{P}}(x))|]\\\
\geq&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[-c_{h,f}({\mathcal{P}}(x))+c_{h,f}(x+{\mathcal{P}}(x))]\\\
\end{array}.$

Then, we have
${\mathbb{E}}_{{\mathcal{D}}_{S}}[c_{h,f}(x+{\mathcal{P}}(x))]\leq{\mathbb{E}}_{{\mathcal{D}}_{S}}[c_{h,f}({\mathcal{P}}(x))]+\tau$.
Now, substitute Results (f1) and (f2) in it to estimate
${\mathbb{E}}_{{\mathcal{D}}_{S}}[c_{h,f}({\mathcal{P}}(x))]$, and we can get

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[c_{h,f}({\mathcal{P}}(x))]\\\
=&\eta{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}({\mathcal{P}}(x))]+(1-\eta){\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}[c_{h,f}({\mathcal{P}}(x))]\\\
\leq&(\eta+(1-\eta)\lambda){\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{\mathcal{S}}}[c_{h,f}({\mathcal{P}}(x))]+\lambda-1\\\
\leq&(\eta+(1-\eta)\lambda)(Q+\epsilon+\tau/\eta-1)+\lambda-1.\end{array}$

So, we prove Result (f3):
${\mathbb{E}}_{{\mathcal{D}}_{S}}[c_{h,f}(x+{\mathcal{P}}(x))]\leq(\eta+(1-\eta)\lambda)(Q+\epsilon+\tau/\eta-1)+\lambda-1+\tau$.

Result (f4):
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]\leq\lambda(Q+\tau/\eta+\epsilon)+\tau+(\lambda-1)\eta$.

Since
$c_{h,f}(x+{\mathcal{P}}(x))=h(x+{\mathcal{P}}(x),l_{p})-f(x+{\mathcal{P}}(x),l_{p})$
and $f(x+{\mathcal{P}}(x),l_{p})\leq 1$, using Result (f3), we have

$\begin{array}[]{ll}&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]\\\
\leq&{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[c_{h,f}(x+{\mathcal{P}}(x),l_{p})]+1\\\
\leq&(\eta+(1-\eta)\lambda)(Q+\epsilon+\tau/\eta-1)+\lambda+\tau\\\
\leq&\lambda(Q+\tau/\eta+\epsilon)+\tau+(\lambda-1)\eta.\end{array}$

This proves Result (f4).

When $h$ satisfies condition (3), using the value of $Q$ into the Result (f4),
we see that with probability $1-\delta-\frac{4-4\eta}{4-4\eta+\eta N}$, we
have:

${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]\leq\lambda(\frac{\sum_{(x,y)\in{\mathcal{D}}_{poi}}h(x,y)}{N\alpha\eta/2}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}+\tau/\eta+\epsilon)+\tau+(\lambda-1)\eta.$

Finally, using the facts ${\mathcal{D}}_{poi}\subset{\mathcal{D}}_{P}$ and
Result (e3) is valid for $X=|{\mathcal{D}}_{poi}|\geq[N\eta/2]$, we have

${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[h(x+{\mathcal{P}}(x),l_{p})]\leq\lambda(\frac{2{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[h(x,y)]}{\alpha\eta}+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H)+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}+\tau/\eta+\epsilon)+\tau+(\lambda-1)\eta.$

The theorem is proved. ∎

###  D.2 Proof of Theorem D.1

Now, we use Theorem D.2 to prove Theorem D.1.

First, for any $h:{\mathbb{R}}^{n}\to{\mathbb{R}}^{m}$, we define
$h_{-1}(x,y)=1-h_{y}(x):{\mathbb{R}}^{n}\times[m]\to{\mathbb{R}}$, and for any
$H\subset{\mathcal{H}}_{W,D}$, we define the hypothesis space:
$H_{-1}=\\{h(x,y)=1-h_{y}(x)\|h(x)\in H\\}$. Using Theorem D.2, we have the
following lemma.

######  Lemma D.3.

For any two hypothesis spaces $H,F\subset{\mathcal{H}}_{W,D}$, if
${\mathcal{P}}(x)$ satisfies the following conditions for some
$\epsilon>0,\tau>0,\lambda\geq 1$:
(1)
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}[f_{y}(x+{\mathcal{P}}(x))]\leq\epsilon$
for any $f\in F$;
(2) ${\mathbb{P}}_{(x,y)\sim{\mathcal{D}}_{S}^{\neq
l_{p}}}({\mathcal{P}}(x)\in
A)\leq\lambda{\mathbb{P}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}({\mathcal{P}}(x)\in
A)$ for any set $A$, where $\lambda\geq 1$;
(3) Some $h\in H$ satisfies that there exists an $f\in F$ such that
${\mathbb{E}}_{x\sim{\mathcal{D}}_{{\mathcal{S}}}}[|(h_{l_{p}}-f_{l_{p}})({\mathcal{P}}(x))-(h_{l_{p}}-f_{l_{p}})(x+{\mathcal{P}}(x))|]\leq\tau$,
where $(h_{l_{p}}-f_{l_{p}})(x)=h_{l_{p}}(x)-f_{l_{p}}(x)$,
then with probability at least $1-\delta-\frac{4-4\eta}{4-4\eta+\eta N}$, for
any $h\in H$ satisfied (3), we have:

$\begin{array}[]{l}{\mathbb{E}}_{(x,y)\sim{\mathcal{D}}_{S}}[1-h_{l_{p}}(x+{\mathcal{P}}(x))]\leq\lambda(2{\mathbb{E}}_{(x,y)\in{\mathcal{D}}_{P}}[1-h_{y}(x)]/(\alpha\eta)+2{\hbox{\rm{Rad}}}^{{\mathcal{D}}_{S}^{l_{p}}}_{N\alpha\eta/2}(H_{-1})+\sqrt{\frac{\ln(2/\delta)}{N\alpha\eta}}+\tau/\eta+\epsilon)\\\
+\tau+(\lambda-1)\eta.\end{array}$ (16)

###### Proof.

We can use Theorem D.2 to $H_{-1}$ and $F_{-1}$ to prove the lemma. We just
need to verify that the three conditions in Theorem D.2 for $H_{-1}$ and
$F_{-1}$.

Verify condition (1) in Theorem D.2.

We just need to show that
${\mathbb{E}}_{(x,y)\sim{\mathcal{D}}^{l_{p}}_{{\mathcal{S}}}}[f_{-1}(x+{\mathcal{P}}(x),y)]\geq
1-\epsilon$ for any $f_{-1}\in F_{-1}$.

By condition (1) in Lemma D.3, and considering that $f_{-1}(x,y)=1-f_{y}(x)$
for the corresponding $f\in F$, we get the result.

Verify condition (2) in Theorem D.2.

This is obvious because condition (2) in Theorem D.2 and Lemma D.3 are the
same.

Verify condition (3) in Theorem D.2.

We just need to show that: Some $h_{-1}\in H_{-1}$ satisfies the requirement
that there exists an $f_{-1}\in F_{-1}$ such that