Pre-trained Encoders in Self-Supervised Learning Improve Secure and Privacy-
preserving Supervised Learning

Hongbin Liu∗ |  |  | Wenjie Qu∗
---|---|---|---
Duke University |  |  | Huazhong University of Science
<EMAIL_ADDRESS>|  |  | and Technology
|  |  |<EMAIL_ADDRESS>
Jinyuan Jia |  |  | Neil Zhenqiang Gong
University of Illinois Urbana-Champaign |  |  | Duke University
<EMAIL_ADDRESS>|  |  |<EMAIL_ADDRESS>

**footnotetext: Equal contribution. Wenjie Qu performed this research when he
was a remote intern in Gong’s group.

###### Abstract

Classifiers in supervised learning have various security and privacy issues,
e.g., 1) _data poisoning attacks_ , _backdoor attacks_ , and _adversarial
examples_ on the security side as well as 2) _inference attacks_ and _the
right to be forgotten_ for the training data on the privacy side. Various
secure and privacy-preserving supervised learning algorithms with formal
guarantees have been proposed to address these issues. However, they suffer
from various limitations such as accuracy loss, small certified security
guarantees, and/or inefficiency. Self-supervised learning is an emerging
technique to pre-train encoders using unlabeled data. Given a pre-trained
encoder as a feature extractor, supervised learning can train a simple yet
accurate classifier using a small amount of labeled training data. In this
work, we perform the first systematic, principled measurement study to
understand whether and when a pre-trained encoder can address the limitations
of secure or privacy-preserving supervised learning algorithms. Our key
findings are that a pre-trained encoder substantially improves 1) both
accuracy under no attacks and certified security guarantees against data
poisoning and backdoor attacks of state-of-the-art secure learning algorithms
(i.e., bagging and KNN), 2) certified security guarantees of randomized
smoothing against adversarial examples without sacrificing its accuracy under
no attacks, 3) accuracy of differentially private classifiers, and 4) accuracy
and/or efficiency of exact machine unlearning.

##  1 Introduction

Supervised learning is widely used in many security-critical and privacy-
sensitive applications such as autonomous driving, cybersecurity, and
healthcare. In a nutshell, supervised learning trains a classifier on labeled
training data, which is then used to classify testing inputs. However, many
studies showed that supervised learning has various security and privacy
issues. For security, an attacker can leverage _data poisoning attacks_ [61,
10], _backdoor attacks_ [38, 24, 58], or _adversarial examples_ [76, 19] to
make a classifier predict incorrect labels as an attacker desires. For
privacy, an attacker can leverage various inference attacks such as _model
inversion attacks_ [33], _membership inference attacks_ [73], and _property
inference attacks_ [6, 34] to infer sensitive information about a classifier’s
training data. Moreover, various regulations and laws such as the European
Union’s General Data Protection Regulation (GDPR) [79] confer _the right to be
forgotten_ to users, where a user’s data should be deleted from the training
data and its effect on a classifier should be removed upon the request from
the user.

To address those security and privacy issues, various defenses have been
proposed. Roughly speaking, those defenses can be divided into _empirical
defenses_ and _certified defenses_. Empirical defenses cannot provide formal
security or privacy guarantees, and thus they are often broken by advanced,
adaptive attacks. Therefore, we focus on certified defenses in this work,
which provide formal security or privacy guarantees in adversarial settings.

Secure supervised learning algorithms and their limitations: A certified
defense against data poisoning and backdoor attacks is essentially a secure
supervised learning algorithm, which can build a classifier on a training
dataset whose predicted label for a testing input is provably unaffected by
attacks, once the number of added, deleted, and/or modified training examples
is no larger than a threshold (called _certified poisoning size_). In this
work, we focus on _bagging_ [44] and _K-nearest neighbors (KNN)_ [46], which
are two state-of-the-art secure supervised learning algorithms. A certified
defense against adversarial examples can build a classifier that provably
predicts the same label for a testing input, once the magnitude (e.g.,
measured by $\ell_{2}$-norm) of the adversarial perturbation is smaller than a
threshold (called _certified radius_). We focus on _randomized smoothing_
[27], a state-of-the-art certified defense against adversarial examples that
is applicable to arbitrary classifiers including large neural networks.

Existing secure supervised learning algorithms suffer from two limitations: 1)
they sacrifice the testing accuracy under no attacks, i.e., the learnt secure
classifiers are (much) less accurate than their non-secure counterparts when
there are no attacks, and 2) their certified security guarantees are weak,
i.e., they can only achieve small certified poisoning sizes or certified
radii. These limitations are the major obstacles for deploying them in
practice.

Privacy-preserving supervised (un)learning algorithms and their limitations:
To defend against inference attacks that compromise the training data privacy
of a classifier, many studies [4, 74, 9, 20, 50, 56] developed differentially
private supervised learning algorithms to train the classifier with formal
privacy guarantees. For instance, DP-SGD [4] is a state-of-the-art
differentially private learning algorithm, which is applicable to deep neural
networks. Exact machine unlearning aims to completely remove the effect of a
user’s data on a classifier, which certifiably achieves the right to be
forgotten. _Retraining from scratch_ is the only exact machine unlearning
method that is applicable to any learning algorithms. Roughly speaking,
retraining from scratch first deletes a user’s data from the training dataset
and then trains a classifier from scratch on the remaining training data.

The major limitation of existing differentially private learning algorithms is
that a differentially private classifier has a (much) lower testing accuracy
than the non-private counterpart. Retraining from scratch is either
inefficient or the unlearnt classifier is inaccurate.

Self-supervised learning: Self-supervised learning [40, 41, 22, 67] is an
emerging machine learning paradigm, which pre-trains an encoder using
unlabeled data. The pre-trained encoder can be used as a feature extractor for
supervised learning tasks. In particular, with high-quality feature vectors
produced by the encoder, we can use supervised learning to train a simple yet
accurate classifier with a small amount of labeled training data.

Our work: We perform the first systematic and principled measurement study to
understand whether and when a pre-trained encoder in self-supervised learning
can improve secure and privacy-preserving supervised (un)learning algorithms.
We consider the pre-trained encoder can produce high-quality feature vectors.
Moreover, the encoder is pre-trained on public data and thus does not incur
privacy concerns for users. Our results show that the pre-trained encoder can
address the limitations of a secure or privacy-preserving supervised
(un)learning algorithm.

Measurement setup. We adopt a state-of-the-art encoder pre-trained by OpenAI
[67] on 400 million (image, text) pairs collected from the public Internet.
Moreover, we consider three benchmark datasets, i.e., STL10, CIFAR10, and
Tiny-ImageNet, for supervised learning. To understand the benefits of a pre-
trained encoder, we compare three cases, namely Case I, Case II, and Case III,
on each dataset. In particular, we respectively train a linear classifier and
a deep neural network from scratch in Case I and Case II without using a pre-
trained encoder. Case III considers a pre-trained encoder is available, and a
common way to build a classifier is to concatenate the encoder and a fully
connected layer with softmax activation function [11]. Then, we train the
classifier by either just training the last fully connected layer (denoted as
_linear probing_) or training both the encoder and the last fully connected
layer (denoted as _fine-tuning_). Note that it is commonly believed that fine-
tuning often achieves higher testing accuracy than linear probing in non-
adversarial settings, which were confirmed by both prior work [54] and our
work. As hyperparameters significantly influence the performance of a
classifier [80], we use grid search to find the best combination of the key
hyperparameters of a secure or privacy-preserving algorithm in each case on
each dataset.

A pre-trained encoder improves secure supervised learning algorithms. Via a
systematic measurement study, we find that a pre-trained encoder substantially
mitigates the limitations of secure supervised learning algorithms.
Specifically, we find that a pre-trained encoder substantially improves both
1) the testing accuracy under no attacks of bagging and KNN and 2) their
certified security guarantees against data poisoning and backdoor attacks. For
instance, on STL10 dataset, the testing accuracies of bagging for Case I, Case
II, and Case III with linear probing are respectively 0.352, 0.559, 0.979,
while the average certified poisoning sizes of the correctly classified
testing examples are respectively 1.3, 2.8, and 68.8 in three cases. We also
find that linear probing and fine-tuning in Case III achieve comparable
testing accuracy and certified security guarantees for bagging, but linear
probing is orders of magnitude more space and time efficient.

Moreover, we find that a pre-trained encoder improves the certified security
guarantees of randomized smoothing against adversarial examples without
sacrificing its testing accuracy under no attacks. For example, on STL10, the
average certified radii of the correctly classified testing examples are
respectively 0.295, 0.625, and 1.482 in Case I, Case II, and Case III with
fine-tuning, while the testing accuracies under no attacks are respectively
0.272, 0.610, and 0.612 in the three cases. Unlike bagging, we find that fine-
tuning achieves much larger testing accuracy and certified security guarantees
than linear probing for randomized smoothing when a pre-trained encoder is
available.

We note that state-of-the-art certified defense methods (i.e., bagging, KNN,
and randomized smoothing) are based on ensemble. Their key limitation is that
their base classifiers used to build ensemble classifiers are less accurate
when trained on a small amount of subsampled training data or noisy training
data. Our intuition is that pre-trained encoder can extract high-quality
feature vectors and thus make their base classifiers more accurate. Note that
more accurate base classifiers can lead to better security-utility tradeoff
for those methods.

A pre-trained encoder improves privacy-preserving supervised (un)learning
algorithms. We find that a pre-trained encoder also substantially mitigates
the limitations of privacy-preserving supervised (un)learning algorithms.
Specifically, we find that a pre-trained encoder substantially improves the
testing accuracy of a differentially private classifier. For instance, a
differentially private classifier in Case III with linear probing achieves a
testing accuracy of 0.956 on STL10 under $(1.0,10^{-5})$-differential privacy.
Under the same privacy budget, the testing accuracies of the differentially
private classifiers in Case I and Case II are respectively 0.237 and 0.142. We
also find that linear probing achieves much higher testing accuracy than fine-
tuning to train a differentially private classifier when a pre-trained encoder
is available. Our intuition is that with an encoder pre-trained on public,
non-private data, we can train an accurate, yet privacy-preserving downstream
linear classifier.

For exact machine unlearning, we find that retraining from scratch in Case III
with linear probing is much more accurate and slightly more efficient than
that in Case I, and is more accurate and orders of magnitude more efficient
than that in Case II. We also observe that linear probing is orders of
magnitude more efficient than fine-tuning for retraining from scratch when a
pre-trained encoder is available.

Our contributions can be summarized as follows:

  * •

We perform the first systematic and principled measurement study to understand
whether and when a pre-trained encoder in self-supervised learning improves
secure or privacy-preserving supervised (un)learning algorithms.

  * •

We find that a pre-trained encoder substantially improves the testing accuracy
under no attack and the certified security guarantees of state-of-the-art
provably secure supervised learning algorithms, i.e., bagging, KNN, and
randomized smoothing.

  * •

We find that a pre-trained encoder substantially improves the testing accuracy
of a differentially private classifier, and the efficiency or the testing
accuracy of exact machine unlearning.

##  2 Background

###  2.1 Self-Supervised Learning

Given a _pre-training dataset_ , e.g., a set of unlabeled images or (image,
text) pairs, self-supervised learning [40, 41, 22, 67] aims to pre-train an
image encoder and (optionally) a text encoder, which can be used as general-
purpose feature extractors for various AI tasks. Many self-supervised learning
algorithms have been developed in the past several years. Among them, CLIP
[67] is the state-of-the-art one. Specifically, CLIP jointly pre-trains an
image encoder and a text encoder using a set of (image, text) pairs. The image
encoder and text encoder respectively output a feature vector for an image and
a text. Given a mini-batch of $B$ (image, text) pairs, we use the image
encoder to produce a feature vector for each of the $B$ images and the text
encoder to produce a feature vector for each of the $B$ texts. CLIP aims to
jointly optimize the image encoder and text encoder such that an image and a
text in the same (image, text) pair have similar feature vectors, while an
image and a text from different (image, text) pairs have dissimilar feature
vectors. OpenAI uses CLIP to pre-train an image encoder and a text encoder on
400 million (image, text) pairs collected from the public Internet [67].

###  2.2 Supervised Learning

Suppose we have a labeled training dataset
$\mathcal{D}=\\{(\mathbf{x}_{1},y_{1}),(\mathbf{x}_{2},y_{2}),\cdots,(\mathbf{x}_{n},y_{n})\\}$,
where $\mathbf{x}_{i}\in\mathbb{R}^{d}$ is the $i$-th training input, $y_{i}$
is the corresponding label, and $d$ is the input dimension. Supervised
learning aims to train a classifier $f$ on the training dataset. In
particular, the classifier $f$ is a function that maps an input
$\mathbf{x}\in\mathbb{R}^{d}$ to a label among a set of $c$ labels
$\\{1,2,\cdots,c\\}$. We consider two scenarios depending on whether a pre-
trained encoder is used or not.

Without a pre-trained encoder: Given the training dataset $\mathcal{D}$,
supervised learning defines a loss function $\mathcal{L}$ for a classifier
$f$: $\mathcal{L}=\frac{1}{n}\sum_{i=1}^{n}l(f(\mathbf{x}_{i}),y_{i})$, where
${l}$ is the loss function, e.g., cross-entropy loss, for a single training
example. Supervised learning trains the classifier $f$ via minimizing the loss
function $\mathcal{L}$, e.g., using stochastic gradient descent (SGD).

With a pre-trained encoder: When a pre-trained encoder is available, we can
use it as a feature extractor when training a classifier. In general, given a
pre-trained encoder, there are two popular ways [22, 23, 41, 67], i.e.,
_linear probing (LP)_ and _fine-tuning (FT)_ , to train a classifier depending
on whether the parameters of the pre-trained encoder are updated or not during
training. In particular, LP freezes the parameters of the pre-trained encoder
during training, while FT updates the parameters of the pre-trained encoder
during training. Next, we discuss them in more details.

  * •

Linear probing (LP): LP appends a fully connected layer with the sofmax
activation function to the pre-trained encoder, where the number of output
neurons is the number of classes for the classification task. The composition
of the pre-trained encoder and the fully connected layer is viewed as a
classifier $f$, which maps an input to a label. When training the classifier
using supervised learning, LP freezes the parameters of the pre-trained
encoder and only updates the parameters of the fully connected layer.

  * •

Fine-tuning (FT): Like LP, FT also appends a fully connected layer with the
sofmax activation function to the pre-trained encoder. However, unlike LP, FT
updates the parameters of both the pre-trained encoder and the fully connected
layer when training the classifier using supervised learning.

##  3 Threat Model

Classifiers in supervised learning: We consider that a classifier in
supervised learning is vulnerable to various security and privacy attacks. In
particular, for security, a classifier is vulnerable to _data poisoning
attacks_ [61, 10], _backdoor attacks_ [38, 24, 58], or _adversarial examples_
[76, 19]. A data poisoning attack assumes that an attacker can tamper with the
labeled training dataset such that the learnt classifier makes incorrect
predictions for indiscriminate clean testing inputs or attacker-chosen ones.
In a backdoor attack, an attacker may also tamper with the training dataset
but the backdoored classifier predicts an attacker-chosen label for any input
embedded with a backdoor trigger. In an adversarial example, an attacker adds
a carefully crafted, human-imperceptible perturbation to a testing input such
that it is misclassified as the attacker desires. Various defenses have been
proposed to defend against these attacks. We consider _certified defenses_ in
this work, because they have formal security guarantees against these attacks.

For privacy, given a black-box or white-box access to a classifier, an
attacker can use various inference attacks such as _model inversion attacks_
[33], _membership inference attacks_ [73], and _property inference attacks_
[6, 34], to infer sensitive information about the training data of the
classifier. Differential privacy is the de-facto standard for privacy
protection, which has formal privacy guarantees. Therefore, we consider
training a classifier with differential privacy to protect the training data
privacy. Moreover, a user may request deleting his/her data from the training
dataset due to privacy concerns after a classifier has been trained. Upon such
request, the classifier has to be unlearnt to remove the effect of the user’s
data, which is known as the right to be forgotten. We consider _exact machine
unlearning_ , which has formal privacy guarantees at achieving the right to be
forgotten.

Pre-trained encoders: We consider an encoder is pre-trained on public, non-
sensitive data in non-adversarial settings. In other words, we assume 1) the
pre-trained encoder produces high-quality feature vectors for inputs, and 2)
the pre-training dataset does not have privacy concerns for users. For
instance, the publicly available image encoder pre-trained by OpenAI on public
(image, text) pairs collected from the Internet [67] is an example of such
encoder. We note that pre-trained encoders could also be vulnerable to data
poisoning and backdoor attacks [47, 17], which may reduce the quality of the
produced feature vectors. However, security/privacy of pre-trained encoders is
beyond the scope of our work. In this work, we aim to understand whether and
when a clean, high-quality pre-trained encoder can improve a secure or
privacy-preserving supervised learning algorithm.

##  4 Measurement Setup

###  4.1 Experimental Setup

Pre-trained encoder (i.e., CLIP [67]): We use the state-of-the-art image
encoder (called CLIP) pre-trained by OpenAI [67] in our evaluation.
Specifically, this image encoder is pre-trained by OpenAI on 400 million
public (image, text) pairs collected from the Internet. The neural network
architecture of the image encoder is a vision transformer [30] and the encoder
outputs a 1024-dimension feature vector for an input. We downloaded the
encoder from GitHub [3].

Datasets for training and testing classifiers: We use three benchmark
datasets, i.e., STL10 [26], CIFAR10 [53], and Tiny-ImageNet [1], to train and
test classifiers. Each dataset contains a pre-defined training dataset and
testing dataset. Moreover, Tiny-ImageNet also contains a pre-defined
validation dataset. For STL10 or CIFAR10, we evenly split its pre-defined
testing dataset into two halves, which we respectively treat as validation
examples and testing examples. Table 1 shows the statistics of the three
datasets. For each dataset, we use its training examples to train a
classifier, use its validation examples to search hyperparameters (e.g.,
learning rate, number of training epochs) used to train the classifier, and
use its testing examples to evaluate the classifier. Unless otherwise
mentioned, we show experimental results on STL10.

Table 1: Statistics of datasets. | STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
#Classes | 10 | 10 | 200
#Training examples | 5,000 | 50,000 | 100,000
#Validation examples | 4,000 | 5,000 | 10,000
#Testing examples | 4,000 | 5,000 | 10,000

Three cases to train classifiers: Our goal is to measure whether a pre-trained
encoder improves a secure or privacy-preserving supervised learning algorithm.
Therefore, we consider the following three cases to train classifiers, where a
pre-trained encoder is not used in the first two cases while is used in the
third case.

  * •

Case I: The first case is to train a simple linear classifier using the
training examples. In particular, we train a multinomial logistic regression
classifier, which can be viewed as a simple neural network with a fully
connected layer with softmax activation function. We note that we represent
each input image as a vector. For instance, in CIFAR10, an image has size
$32\times 32\times 3$, which can be represented as a vector with $3,072$
dimensions.

  * •

Case II: The second case is to train a deep neural network classifier from
scratch. We adopt ResNet-18 [42] as the architecture of the deep neural
network classifier because it achieves state-of-the-art accuracy on the three
datasets.

  * •

Case III (Case III-LP and Case III-FT): The third case is to train a
classifier using linear probing or fine-tuning when a pre-trained encoder is
available (please see Section 2.2 for details). In particular, we append a
fully connected layer with softmax activation function (i.e., a multinomial
logistic regression classifier) to the encoder. The composition of the encoder
and the fully connected layer is a classifier. Then, in LP, we only train the
fully connected layer using supervised learning, while we train both the
encoder and the fully connected layer in FT. We denote these two scenarios as
_Case III-LP_ and _Case III-FT_ , respectively.

Case I and Case II represent two extreme cases of classifiers (i.e., simple
linear classifier and complex deep neural network classifier) when a pre-
trained encoder is not available. Training a linear classifier is more
efficient but less accurate than training a deep neural network. Comparing
Case III with the first two cases enables us to comprehensively measure the
benefits of a pre-trained encoder when training a classifier.

Hyperparameter search: The performance of a classifier highly depends on the
hyperparameters used to train the classifier. The best hyperparameters of a
classifier may be different for different datasets. Moreover, the best
hyperparameters for the same dataset may be different for the three cases.
Since our goal is to compare the classifiers in the three cases, we aim to
search for the best hyperparameters for each case. Specifically, based on the
performance of a secure or privacy-preserving classifier on the validation
examples, we perform grid search to find the best combination of the number of
training epochs, learning rate, and security/privacy-dependent hyperparameters
for each case on each dataset.

Specifically, the metric to evaluate the performance of a classifier and the
security/privacy-dependent hyperparameters (e.g., the number of nearest
neighbors $K$ in $K$-nearest neighbor algorithm) are different for different
secure and privacy-preserving algorithms, whose details we will discuss when
introducing our measurement results for each secure or privacy-preserving
algorithm in Section 5 to Section 8. We consider every 5 training epochs up to
500 ones and learning rates $10^{-5},10^{-4},10^{-3},10^{-2}$, and $10^{-1}$
in our grid search. We note that mini-batch size is also a hyperparameter for
training a classifier. However, we found that mini-batch size has a small
impact once it is large enough. Therefore, we set mini-batch size to be 128
and do not perform grid search for it to reduce the computation cost of
hyperparameter search.

###  4.2 Accuracy in Non-adversarial Setting

Table 2: The testing accuracy of the three cases in non-adversarial setting. | STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 0.353 | 0.438 | 0.069
Case II | 0.755 | 0.953 | 0.516
Case III-LP | 0.985 | 0.954 | 0.751
Case III-FT | 0.970 | 0.973 | 0.785

Table 2 shows the testing accuracy of the classifiers in the three cases under
non-adversarial settings. First, we observe that Case III achieves larger
testing accuracy than Case I and Case II. The reason is that the pre-trained
encoder extracts high-quality feature representations, which help improve the
testing accuracy. Our observation is consistent with prior studies on self-
supervised learning [67, 22]. Moreover, Case II achieves larger testing
accuracy than Case I. This is because a deep neural network in Case II is more
expressive than a linear classifier in Case I. Second, Case III-FT outperforms
Case III-LP in general. Specifically, the average testing accuracy of Case
III-FT and Case III-LP across the three datasets in our experiments is 0.909
and 0.897, respectively. Our observation is also consistent with prior works
[54, 52, 86] on comparing Case III-FT and Case III-LP in non-adversarial
settings, which also found that Case III-FT outperforms Case III-LP with
respect to average testing accuracy across datasets. Case III-FT achieves a
smaller testing accuracy than Case III-LP on STL10. We suspect the reason is
that STL10 only contains 5,000 training examples and Case III-FT is more
likely to overfit the classifier to the training examples.

##  5 Security against Data Poisoning and Backdoor Attacks

###  5.1 Related Work

Data poisoning and backdoor attacks: Classifiers are vulnerable to data
poisoning attacks [61, 10, 35, 60, 71] and backdoor attacks [38, 24, 58]. In
data poisoning attacks, an attacker poisons the training data (e.g., adds,
deletes, and/or modifies training examples) such that a classifier trained on
the poisoned training data has attacker-desired behaviors. Specifically, the
poisoned classifier either achieves a low testing accuracy for indiscriminate
clean testing inputs [10, 60, 72, 32] or predicts attacker-chosen labels for
attacker-chosen clean testing inputs [71, 16, 17]. Like data poisoning
attacks, some backdoor attacks also poison the training data. However, unlike
data poisoning attacks, a backdoored classifier predicts an attacker-chosen
label for any testing input embedded with a backdoor trigger and its
predictions for clean testing inputs without the backdoor trigger are
unaffected. For instance, BadNet [38] embeds a backdoor trigger (e.g., a pixel
pattern) to some training inputs and changes their labels to the attacker-
chosen label. The classifier trained on the poisoned training data predicts
the attacker-chosen label for any testing input embedded with the same
backdoor trigger.

Certified defenses against data poisoning and backdoor attacks: Based on
whether a defense has formal security guarantee against data poisoning and
backdoor attacks, we can categorize existing defenses into _empirical
defenses_ [28, 69, 8, 64, 63, 75, 57, 65, 21, 78] and _certified defenses_
[44, 46, 68, 48, 81, 55]. In particular, empirical defenses do not have formal
security guarantees and thus they are often broken by more advanced, adaptive
attacks [51]. Therefore, we focus on certified defenses in this work.

A certified defense is a secure learning algorithm $\mathcal{A}$ whose
predicted label for a testing input is provably not affected by poisoning
training examples once the number of them is no larger than a threshold, which
is called _certified poisoning size_. Specifically, we denote
$\mathcal{A}(\mathcal{D},\mathbf{x})$ as the label predicted for a testing
input $\mathbf{x}$ by a classifier learnt by $\mathcal{A}$ on the training
dataset $\mathcal{D}$. In data poisoning and backdoor attacks, an attacker can
arbitrarily add, delete, and/or modify some training examples in
$\mathcal{D}$. For simplicity, we use $\mathcal{D}^{\prime}$ to denote the
poisoned training dataset. We denote by $P(\mathcal{D},\mathcal{D}^{\prime})$
the number of poisoning training examples in $\mathcal{D}^{\prime}$, compared
to $\mathcal{D}$. A certified defense guarantees the following:

$\displaystyle\mathcal{A}(\mathcal{D},\mathbf{x})=\mathcal{A}(\mathcal{D}^{\prime},\mathbf{x}),\forall\mathcal{D}^{\prime}\text{
s.t. }P(\mathcal{D},\mathcal{D}^{\prime})\leq r_{\mathbf{x}},$ (1)

where $r_{\mathbf{x}}$ is the certified poisoning size for $\mathbf{x}$. In
data poisoning attacks, $\mathbf{x}$ is a clean testing input. In backdoor
attacks, $\mathbf{x}$ is a testing input with a backdoor trigger. The above
guarantee means once a classifier trained on the clean training dataset
correctly classifies the testing input with trigger (i.e.,
$\mathcal{A}(\mathcal{D},\mathbf{x})$ is the true label of $\mathbf{x}$), the
backdoored classifier trained on the poisoned training dataset still correctly
classifies the testing input with trigger (i.e.,
$\mathcal{A}(\mathcal{D}^{\prime},\mathbf{x})$ is still correct) when the
number of poisoning training examples is at most $r_{\mathbf{x}}$.

Next, we discuss two state-of-the-art certified defenses, namely _bagging_
[44] and _K-nearest neighbors_ [46]. We respectively discuss how they build a
secure classifier and how they compute the certified poisoning size for a
testing input.

_1) Bagging[13, 44]._ Bagging [13] is a popular ensemble learning algorithm.
Suppose we create a random _subsample_ with $k$ training examples via sampling
them from a training dataset $\mathcal{D}$ uniformly at random with
replacement. We use an arbitrary learning algorithm (either deterministic or
probabilistic) to train a classifier (called _base classifier_) on it. Due to
randomness in the subsample and (the learning algorithm), the label predicted
by the base classifier for a testing input $\mathbf{x}$ is also random. We
define _label probability_ $p_{i}$ ($i=1,2,\cdots c$) as the probability that
the base classifier predicts label $i$ for $\mathbf{x}$. Given the label
probability $p_{i}$’s, bagging builds an _ensemble classifier_ $F$ which
predicts the label (denoted as $F(\mathcal{D},\mathbf{x})$) with the largest
label probability for the testing input $\mathbf{x}$. Formally, we have:
$F(\mathcal{D},\mathbf{x})=\operatorname*{arg\,max}_{i=1,2,\cdots,c}p_{i}.$

Jia et al. [44] showed that bagging has certified security guarantees and
leveraged Monte-Carlo sampling to compute $F(\mathcal{D},\mathbf{x})$ and
$r_{\mathbf{x}}$. In particular, they first create $N$ subsamples, each of
which includes $k$ training examples sampled from $\mathcal{D}$ uniformly at
random with replacement, then train a base classifier on each subsample, and
finally count the number of base classifiers that predict label $i$ for
$\mathbf{x}$, where $i=1,2,\cdots,c$. The label with the largest count is
treated as $F(\mathcal{D},\mathbf{x})$, i.e., the predicted label for
$\mathbf{x}$. Jia et al. showed that the certified poisoning size
$r_{\mathbf{x}}$ is the solution to an optimization problem, which relies on a
lower bound of the largest label probability and an upper bound of the second
largest label probability for $\mathbf{x}$. Given the count of each label, Jia
et al. [44] used a Monte-Carlo method to estimate them, which are then used to
solve the optimization problem to obtain the certified poisoning size
$r_{\mathbf{x}}$. Due to the randomness in estimating the label-probability
bounds, the obtained $r_{\mathbf{x}}$ may be incorrect with a probability
$\alpha$, where $\alpha$ is called _confidence level_ that can be set to be
arbitrarily small. Note that $\alpha$ influences the estimated certified
poisoning size $r_{\mathbf{x}}$ but not the predicted label
$F(\mathcal{D},\mathbf{x})$.

_2) $K$-nearest neighbors (KNN) [5, 46]._ K-nearest neighbors (KNN) is a
classical non-parametric algorithm for classification. Jia et al. [46] showed
that KNN is intrinsically secure against data poisoning and backdoor attacks.
Given a training dataset $\mathcal{D}$, a distance metric $d$ (e.g.,
$\ell_{1}$ distance in our experiments), and a testing input $\mathbf{x}$, KNN
first calculates the distance between each training input and $\mathbf{x}$
with respect to the distance metric $d$, and then finds the $K$ training
examples that have the smallest distances to $\mathbf{x}$. Given the $K$
nearest neighbors, KNN takes a majority vote among their labels as the
predicted label for $\mathbf{x}$.

Jia et al. derived the certified security guarantee of KNN. Suppose $a$ (or
$b$) is the most (or second most) frequent label among the $K$ nearest
neighbors of $\mathbf{x}$. Moreover, we use $K^{a}_{\mathbf{x}}$ (or
$K^{b}_{\mathbf{x}}$) to denote the number of nearest neighbors that have
label $a$ (or $b$). Jia et al. showed that $r_{\mathbf{x}}$ can be computed as
follows:

$\displaystyle
r_{\mathbf{x}}=\left\lceil\frac{K^{a}_{\mathbf{x}}-K^{b}_{\mathbf{x}}+\mathbb{I}(a>b)}{2}\right\rceil-1,$
(2)

where $\mathbb{I}$ is an indicator function whose value is $1$ if the
condition $a>b$ is true and is $0$ otherwise.

Limitations of bagging and KNN: Bagging and KNN have two limitations: 1) they
sacrifice testing accuracy under no attacks, i.e., the (ensemble) classifiers
built by bagging or KNN are (much) less accurate than non-secure classifiers
(e.g., deep neural network) when there are no attacks, and 2) their certified
poisoning sizes are small, i.e., they can only tolerate a small number of
poisoning training examples. These two limitations substantially hinder their
deployment in practice. We aim to understand whether and when a pre-trained
encoder can mitigate these limitations.

###  5.2 Experimental Setup

Building classifiers using bagging or KNN: Suppose we have a training dataset
$\mathcal{D}$. For bagging, we can respectively use Case I, Case II, and Case
III to train $N$ base classifiers on $N$ subsamples created from
$\mathcal{D}$. Given those base classifiers, we build an ensemble classifier
for each case.

For KNN, Case I, Case II, and Case III have different meanings as KNN does not
have training process. In particular, in Case I, we directly apply KNN to the
raw training/testing images, i.e., the distance between a testing image and a
training image is calculated based on their pixel values. To further improve
KNN, Jia et al. [46] proposed to first extract histogram-of-oriented-gradients
(HOG) [29] features for each training/testing image and then calculate
distance between two images based on those features in KNN, which we use in
our Case II. In Case III, we use a pre-trained encoder to compute a feature
vector for each training/testing image and then calculate distance between two
images based on the feature vectors in KNN.

Evaluation metrics: We use _testing accuracy under no attacks (testing
accuracy)_ and _average certified poisoning size (ACPS)_ as the evaluation
metrics. Testing accuracy is the fraction of clean testing inputs whose labels
are correctly predicted by a classifier when there are no attacks. ACPS is the
average certified poisoning size of the testing inputs that are correctly
classified. Formally, given a testing dataset $\mathcal{D}_{te}$, we compute
ACPS as follows:

$\displaystyle ACPS$
$\displaystyle=\frac{\sum_{(\mathbf{x}_{i},y_{i})\in\mathcal{D}_{te}}\mathbb{I}(c_{\mathbf{x}_{i}}=y_{i})\cdot
r_{\mathbf{x}_{i}}}{\sum_{(\mathbf{x}_{i},y_{i})\in\mathcal{D}_{te}}\mathbb{I}(c_{\mathbf{x}_{i}}=y_{i})},$
(3)

where $c_{\mathbf{x}_{i}}$ and $r_{\mathbf{x}_{i}}$ respectively represent the
predicted label and the certified poisoning size of the testing input
$\mathbf{x}_{i}$, and $\mathbb{I}$ is an indicator function. For data
poisoning attacks, the testing dataset $\mathcal{D}_{te}$ contains clean
testing examples. For backdoor attacks, the testing dataset $\mathcal{D}_{te}$
contains backdoored testing examples obtained via embedding a backdoor trigger
to each testing input. Note that the ACPS does not account for the clean data
samples used to pre-train the pre-train the CLIP encoder in our Case III,
since we consider the security of supervised learning, i.e., classifiers.

Hyperparameter search and parameter setting: We search the best hyperparameter
setting for each of the three cases to achieve the largest ACPS. In bagging,
$k$ is the number of training examples used to train each base classifier. As
we will show in our experimental results, ACPS first increases and then
decreases as $k$ increases. Moreover, the $k$ that achieves the largest ACPS
could also be different for the three cases. To fairly compare the three
cases, we search for a wide range of $k$ when training base classifiers for
each case. In particular, we consider the following values of $k$: 10, 30, 50,
100, 300, 500, and 1,000. We use grid search to find the combination of $k$,
number of training epochs, and learning rate that achieves the largest ACPS
following the search process described in Section 4.1. We note that there are
two other hyperparameters in testing phase of bagging, i.e., $N$ and $\alpha$,
which respectively control the number of base classifiers and confidence level
of the outputted certified poisoning size. We use the same $N$ and $\alpha$
for all three cases to fairly compare them. Following Jia et al. [44], we set
$N=10^{3}$ and $\alpha=10^{-3}$ by default.

$K$ is a hyperparameter in KNN. We search for the $K$ that achieves the
largest ACPS from the following values: 100, 300, 500, 1,000, 3,000, and
5,000. Following Jia et al. [46], we use $\ell_{1}$ distance in KNN. For
backdoor attacks, we use a $2\times 2$ white patch as the backdoor trigger.
Moreover, following previous work [38, 82], we embed the backdoor trigger at
the bottom right corner of an image.

###  5.3 Experimental Results

Table 3: Comparing Case III-LP and Case III-FT for bagging.

| Case III-LP | Case III-FT
---|---|---
Testing accuracy | 0.979 | 0.982
(a) Testing accuracy under no attacks

| Case III-LP | Case III-FT
---|---|---
Data poisoning attacks | 70.3 | 71.0
Backdoor attacks | 69.9 | 70.5
(b) ACPS against attacks

| Case III-LP | Case III-FT
---|---|---
Training time (seconds) | $1.41\times 10^{2}$ | $1.86\times 10^{3}$
Testing time (seconds) | $2.26\times 10^{2}$ | $2.97\times 10^{3}$
Storage (MB) | $2.15\times 10^{1}$ | $3.38\times 10^{5}$
(c) Computation and storage cost

Comparing Case III-LP with Case III-FT for bagging: Table 3 shows the results
of bagging in Case III-LP and Case III-FT on STL10. First, Case III-LP and
Case III-FT achieve similar testing accuracy and ACPS. In particular, their
testing accuracy difference is within 0.003 and their ACPS differences are
within 0.6. Second, the computation and storage cost of Case III-LP are
respectively an order and four orders of magnitude smaller than those of Case
III-FT. Case III-LP takes a smaller training time because it only trains the
last fully connected layer for each base classifier; Case III-LP takes a
smaller testing time because different base classifiers share the same encoder
and thus we only need to use it to compute a feature vector for each testing
input once; and Case III-LP incurs a smaller storage cost because we only need
to save the parameters of the last fully connected layer for each base
classifier. As Case III-LP and Case III-FT achieve similar testing accuracy
and ACPS but Case III-LP incurs smaller computation and storage cost, we use
Case III-LP in Case III in the following experiments.

Table 4: Comparing the three cases for bagging.

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 0.352 | 0.358 | 0.071
Case II | 0.559 | 0.566 | 0.072
Case III-LP | 0.979 | 0.907 | 0.629
(a) Testing accuracy under no attacks

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 3.7 | 21.2 | 0.001
Case II | 5.0 | 20.7 | 0.06
Case III-LP | 70.3 | 359.0 | 19.5
(b) ACPS against data poisoning attacks

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 3.7 | 20.9 | 0.001
Case II | 5.0 | 20.3 | 0.06
Case III-LP | 69.9 | 357.5 | 19.4
(c) ACPS against backdoor attacks

Table 5: Comparing the three cases for KNN.

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 0.194 | 0.229 | 0.029
Case II | 0.230 | 0.327 | 0.038
Case III | 0.963 | 0.865 | 0.583
(a) Testing accuracy under no attacks

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 36.6 | 187.8 | 10.3
Case II | 14.3 | 164.2 | 13.2
Case III | 138.7 | 929.4 | 51.6
(b) ACPS against data poisoning attacks

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 36.1 | 187.3 | 10.3
Case II | 14.3 | 163.3 | 13.2
Case III | 138.5 | 962.2 | 51.3
(c) ACPS against backdoor attacks

Comparing the three cases for bagging: Table 4 compares the testing accuracy
and ACPS of the three cases under the framework of bagging. We have the
following observations. First, Case III achieves significantly higher testing
accuracy and ACPS than Case I and Case II among all datasets. This is because
base classifiers trained by Case III are much more accurate than those trained
by Case I and Case II, especially when the number of training examples $k$
used to train each base classifier is small. Second, bagging achieves
significantly higher ACPS on CIFAR10 than on the other two datasets. The
reason is that CIFAR10 has $9\times$ more training examples than STL10, and
thus each subsample created from CIFAR10 is less likely to contain poisoning
training examples than STL10 for a given subsample size $k$ and number of
poisoning training examples. The reason why CIFAR10 has higher ACPS than Tiny-
ImageNet is that the base classifiers on CIFAR10 are more accurate than those
on Tiny-ImageNet since Tiny-ImageNet is a more challenging classification
task. Third, we find that bagging achieves similar ACPS against data poisoning
attacks and backdoor attacks. This is because a base classifier is very likely
to predict the same label for testing inputs with and without the backdoor
trigger when its size is small ($2\times 2$ in our experiments).

Comparing the three cases for KNN: Table 5 shows the testing accuracy and ACPS
of the three cases for KNN. Similar to bagging, we have three observations: 1)
Case III achieves higher testing accuracy and ACPS than Case I and Case II, 2)
CIFAR10 has higher ACPS than the other two datasets, and 3) ACPS of each case
is similar for data poisoning attacks and backdoor attacks.

Comparing bagging with KNN in Case III: By comparing the results in Table 4
and 5, we find that bagging achieves higher testing accuracy but lower ACPS
than KNN on each dataset. Bagging achieves higher testing accuracy because
each base classifier is trained to better fit with the data distribution,
while KNN does not have trainable parameters. Bagging achieves lower ACPS than
KNN because one poisoning training example impacts multiple base classifiers
in bagging, but only impacts at most two nearest neighbors of a testing input
in KNN. Thus, KNN can tolerate more poisoning training examples than bagging.
We also note that, compared with KNN, bagging is a more general framework as
we can use an arbitrary learning algorithm to train each base classifier.

(a) Testing accuracy (b) ACPS

Figure 1: Impact of $k$ on the testing accuracy of bagging under no attacks
and ACPS of bagging against data poisoning and backdoor attacks.

Impact of $k$, $N$, and $\alpha$ on bagging in Case III: Figure 1 shows the
impact of $k$ on testing accuracy and ACPS of bagging in Case III on STL10
dataset. We find that testing accuracy increases as $k$ increases. This is
because the base classifiers are more accurate when $k$ is larger as more
training examples are used to train each base classifier. Moreover, we find
that ACPS first increases and then decreases as $k$ increases. The reason is
that base classifiers are less accurate when $k$ is small and are more likely
to be trained on poisoning training examples when $k$ is large. Figure 6 in
Appendix shows the impact of $N$ on the testing accuracy and ACPS of bagging.
We find that $N$ has a negligible impact on testing accuracy. The reason is
that a small $N$ can already well estimate the predicted label of bagging for
a testing input. Moreover, ACPS increases as $N$ increases. The reason is that
a larger $N$ results in tighter estimation of the lower and upper bounds of
label probabilities, which leads to a larger certified poisoning size. Figure
7 in Appendix shows the impact of $\alpha$ on ACPS of bagging in Case III.
Note that testing accuracy of bagging under no attacks does not depend on
$\alpha$. We observe that ACPS increases as $\alpha$ increases. This is
because a larger $\alpha$ results in tighter estimation of label-probability
bounds.

(a) Testing accuracy

(b) ACPS

Figure 2: Impact of $K$ on the (a) testing accuracy of KNN under no attacks,
and (b) ACPS of KNN against data poisoning and backdoor attacks.

Impact of $K$ on KNN in Case III: Figure 2 shows the impact of $K$ on the
testing accuracy under no attacks and ACPS of KNN against data poisoning and
backdoor attacks. First, we find that testing accuracy decreases as $K$
increases. This is because the decision boundary of KNN classifier is smoother
when $K$ is larger. Second, we observe that ACPS of KNN first increases and
then decreases as $K$ increases. The reasons are as follows. When $K$ is too
small, the gap between $K^{a}_{\mathbf{x}}$ and $K^{b}_{\mathbf{x}}$ is small
and thus the certified poisoning size is small based on Equation 2. When $K$
is too large, KNN is less accurate compared with a smaller $K$ as shown in
Figure 2a.

Summary: We observe that a pre-trained encoder makes bagging and KNN more
accurate under no attacks and more secure against data poisoning and backdoor
attacks. Compared with bagging, KNN is less accurate under no attacks but
achieves a stronger certified security guarantee. Bagging with linear probing
and bagging with fine-tuning achieve similar testing accuracy under no attacks
and certified security guarantees against attacks, but bagging with linear
probing is orders of magnitude more space and time efficient.

##  6 Security against Adversarial Examples

###  6.1 Related Work

Adversarial examples: An attacker can add carefully crafted noise to a testing
input such that a classifier predicts an arbitrary or attacker-chosen
incorrect label for it [76, 19]. Such testing input with carefully crafted
noise is called _adversarial example_. Adversarial examples pose severe
security threats to classifiers, especially for security-critical applications
such as autonomous driving.

Certified defenses against adversarial examples: To defend against adversarial
examples, both empirical defenses [62, 84, 37, 59, 14] and certified defenses
[27, 43, 66, 70, 45] were proposed. Empirical defenses do not have formal
security guarantees against adversarial examples, and thus they are often
broken by adaptive, advanced attacks [18, 7]. Therefore, we focus on certified
defenses in this work. A certified defense can prove a classifier’s predicted
label for a testing input does not change when the magnitude (e.g., measured
by $\ell_{2}$-norm) of the noise added to the testing input is smaller than a
threshold (called _certified radius_). Formally, given a testing input
$\mathbf{x}$ and a classifier $g$, a certified defense can provide the
following guarantee:

$\displaystyle g(\mathbf{x})=g(\mathbf{x}+\delta),\forall\delta\text{ s.t.
}\|\delta\|_{2}<R_{\mathbf{x}},$ (4)

where $R_{\mathbf{x}}$ is the certified radius for the testing input
$\mathbf{x}$. Among existing certified defenses, randomized smoothing [27] is
state-of-the-art since it is applicable to arbitrary classifiers and scalable
to large neural networks. Next, we discuss it in more details.

Randomized smoothing [27]: Given a testing input $\mathbf{x}$, randomized
smoothing first creates a randomized input via adding isotropic Gaussian noise
to it. Then, randomized smoothing uses an arbitrary classifier $f$ (called
_base classifier_) to predict a label for the randomized input. Due to
randomness in the randomized input, the predicted label is also random. To
capture such randomness, we define label probability $p_{i}$ as the
probability that the base classifier $f$ predicts label $i$ for the randomized
input, where $i=1,2,\cdots,c$. Formally, we define
$p_{i}=\Pr(f(\mathbf{x}+\mathcal{N}(0,\sigma^{2}I))=i)$, where
$\mathcal{N}(0,\sigma^{2}I)$ is isotropic Gaussian noise with standard
deviation $\sigma$. Given the label probabilities, randomized smoothing builds
a _smoothed classifier_ $g$ which predicts the label with the largest label
probability for $\mathbf{x}$. Formally, we have:
$g(\mathbf{x})=\operatorname*{arg\,max}_{i=1,2,\cdots,c}p_{i}$.

Cohen et al. [27] proposed a Monte-Carlo method to compute $g(\mathbf{x})$ and
the certified radius $R_{\mathbf{x}}$. Roughly speaking, they first generate
$M$ noise from $\mathcal{N}\left(0,\sigma^{2}I\right)$, then add each of them
to $\mathbf{x}$ to create $M$ noisy inputs, and finally use the base
classifier $f$ to predict a label for each noisy input. Given the predicted
labels, they count the number of noisy inputs that are predicted as label $i$
($i=1,2,\cdots,c$). The label with the largest count (denoted as $a$) is
predicted as $g(\mathbf{x})$. Given the count of the label $a$, Cohen et al.
proposed to use one-sided Clopper-Pearson method [25] to estimate a lower
bound of the label probability $p_{a}$, which we denote as
$\underline{p_{a}}$. Cohen et al. showed that the certified radius
$R_{\mathbf{x}}$ can be computed as follows:

$\displaystyle
R_{\mathbf{x}}=\frac{\sigma}{2}(\Phi^{-1}(\underline{p_{a}})-\Phi^{-1}(1-\underline{p_{a}})),$
(5)

where $\Phi^{-1}$ is the inverse of the standard Gaussian cumulative
distribution function. Due to probabilistic errors in estimating the label-
probability lower bound $\underline{p_{a}}$, the outputted certified radius
$R_{\mathbf{x}}$ may be incorrect with a probability $\alpha$ (called
_confidence level_), which can be set to be arbitrarily small.

Limitations of randomized smoothing: The key limitations of randomized
smoothing are that: 1) it sacrifices testing accuracy under no attacks, and 2)
its certified radius is small. We aim to study whether and when a pre-trained
encoder can mitigate these limitations of randomized smoothing.

###  6.2 Experimental Setup

Training base classifiers: Given a training dataset, we train a base
classifier in Case I, Case II, Case III-LP, or Case III-FT. Cohen et al. [27]
showed that the smoothed classifier achieves better accuracy under no attacks
and certified radius if the isotropic Gaussian noise is added to the training
inputs when training the base classifier. Therefore, we add random isotropic
Gaussian noise to the training inputs in each epoch when training a base
classifier in each case.

Evaluation metrics: We use _testing accuracy under no attacks (testing
accuracy)_ and _average certified radius (ACR)_ as the evaluation metrics. In
particular, testing accuracy measures the fraction of testing examples that
are correctly classified by a smoothed classifier. ACR measures the average
certified radius of the testing examples that are correctly classified by a
smoothed classifier. Formally, given a testing dataset $\mathcal{D}_{te}$, ACR
can be computed as follows:

$\displaystyle
ACR=\frac{\sum_{(\mathbf{x}_{i},y_{i})\in\mathcal{D}_{te}}\mathbb{I}(a_{\mathbf{x}_{i}}=y_{i})\cdot
R_{\mathbf{x}_{i}}}{\sum_{(\mathbf{x}_{i},y_{i})\in\mathcal{D}_{te}}\mathbb{I}(a_{\mathbf{x}_{i}}=y_{i})},$
(6)

where $a_{\mathbf{x}_{i}}$ and $R_{\mathbf{x}_{i}}$ are respectively the
predicted label, certified radius for the testing input $\mathbf{x}_{i}$, and
$\mathbb{I}$ is an indicator function.

Hyperparameter search and parameter setting: $\sigma$ achieves a tradeoff
between testing accuracy and ACR of a smoothed classifier as shown in Figure
3. In particular, testing accuracy decreases and ACR increases as $\sigma$
increases. As a result, $\sigma$ would be $\infty$ (or $0$) if we search for
it to achieve the largest ACR (or testing accuracy) in each case, which leads
to $\infty$ (or $0$) ACR based on Equation 5 and makes comparison of ACR
across the three cases meaningless. In response, we compare the three cases by
following previous work on how to compare different smoothed classifiers [27,
45]. In particular, we set $\sigma$ to be a small value (i.e., $0.25$) for
Case I and Case II and then search for $\sigma$ in Case III such that the
testing accuracy of the smoothed classifier in Case III is similar to or
higher than those in Case I and Case II. In particular, we search among the
following $\sigma$ in Case III: 0.25, 0.50, 0.75, and 1.00. Note that for each
case, we still search for the combination of number of training epochs and
learning rate that achieves the largest ACR when training a base classifier,
following the description in Section 4.1. In the testing phase, $M$ and
$\alpha$ are two parameters used to estimate the predicted label and label-
probability bound for a testing input. We set them to be the same in the three
cases for fair comparison. Following Cohen et al. [27], we set $M=10^{4}$ and
$\alpha=10^{-3}$ by default.

Table 6: Comparing Case III-LP and Case III-FT in randomized smoothing. | Case III-LP | Case III-FT
---|---|---
Testing accuracy | 0.390 | 0.612
ACR | 0.815 | 1.482
Table 7: Comparing three cases for randomized smoothing.

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 0.272 | 0.312 | 0.036
Case II | 0.610 | 0.754 | 0.390
Case III-FT | 0.612 | 0.806 | 0.418
(a) Testing accuracy under no adversarial examples

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 0.295 | 0.411 | 0.315
Case II | 0.625 | 0.518 | 0.482
Case III-FT | 1.482 | 0.593 | 0.767
(b) ACR against adversarial examples

###  6.3 Experimental Results

Comparing Case III-LP with Case III-FT: Table 6 compares testing accuracy and
ACR of Case III-LP and Case III-FT on STL10 dataset. Our results show that
Case III-FT achieves better testing accuracy and ACR than Case III-LP. The
reason is that Case III-FT updates both the encoder and the last fully
connected layer using training inputs added with Gaussian noise when training
the base classifier. Thus, the base classifier trained by Case III-FT is more
likely to correctly classify the testing inputs added with Gaussian noise.
Therefore, unless otherwise mentioned, we use Case III-FT in Case III in the
following experiments.

Comparing the three cases: Table 7 compares the testing accuracy and ACR of
the three cases. We have the following observations. First, Case III-FT
achieves the highest ACR while its testing accuracy is similar to or higher
than those of Case I and Case II. In other words, Case III-FT can offer a
stronger certified security guarantee against adversarial examples than Case I
and Case II without sacrificing testing accuracy under no attacks. The reason
is that a pre-trained encoder can produce high-quality features and thus the
base classifier in Case III-FT is more likely to correctly classify the
testing inputs with Gaussian noise. Second, we find that Case III-FT achieves
significantly higher ACR on STL10 than the other two datasets. We suspect the
reason is that the number of training examples in STL10 is much smaller than
the other two datasets and thus the performance improvement brought by high-
quality features produced by the pre-trained encoder is more significant.
Another observation is that Case II achieves higher testing accuracy and ACR
than Case I. The reason is that deep neural network is more powerful in
generalization than a linear classifier.

Impact of $\sigma$, $M$, and $\alpha$ in Case III-FT: Figure 3 shows the
impact of $\sigma$ on testing accuracy and ACR of the smoothed classifier in
Case III-FT on STL10. First, we find that testing accuracy decreases as
$\sigma$ increases, which is because adding a larger noise to testing inputs
makes it harder to correctly classify them. Second, we find that ACR increases
as $\sigma$ increases. The reason is that adding a larger noise to a testing
input requires a larger adversarial perturbation to manipulate its predicted
label. Figure 8 in Appendix shows the impact of $M$ on testing accuracy and
ACR of the smoothed classifier. We find that $M$ has a negligible impact on
testing accuracy. This is because a small $M$ can already provide good
estimations of the labels predicted by the smoothed classifier for the testing
inputs. We also observe that ACR increases as $M$ increases. The reason is
that a larger $M$ produces a tighter label-probability lower bound
$\underline{p_{a}}$ and thus a larger certified radius. Figure 9 in Appendix
shows the impact of $\alpha$ on ACR of the smoothed classifier. We find that
ACR increases as $\sigma$ increases. The reason is that a larger $\alpha$
leads to a tighter $\underline{p_{a}}$. We note that $\alpha$ does not impact
testing accuracy.

(a) Testing accuracy

(b) ACR

Figure 3: Impact of $\sigma$ on the testing accuracy and ACR of randomized
smoothing.

Training with vs. without Gaussian noise: Table 8 compares the testing
accuracy and ACR of Case III-FT when training the base classifiers with or
without adding Gaussian noise to the training inputs. We find training with
noise achieves significantly higher testing accuracy and ACR than training
without noise. The reason is that, in training with Gaussian noise, both
training and testing data of the base classifier have the same distribution
and thus the base classifier is more accurate at classifying testing inputs
with Gaussian noise.

Table 8: Training with vs. without Gaussian noise. | Training w/o noise | Training with noise
---|---|---
Testing accuracy | 0.358 | 0.612
ACR | 0.729 | 1.482

Summary: We observe that a pre-trained encoder can improve both the testing
accuracy under no attacks and certified security guarantees against
adversarial examples of randomized smoothing. The smoothed classifier can
achieve better testing accuracy and certified security guarantees when
training a base classifier via fine-tuning and adding Gaussian noise to the
training inputs.

##  7 Training with Differential Privacy

###  7.1 Related Work

Inference attacks to classifiers: Classifiers are vulnerable to various
inference attacks such as model inversion attacks [33], membership inference
attacks [73], and property inference attacks [6, 34]. In particular, given
either a black-box or white-box access to a classifier, an attacker can infer
various information about its training data. These attacks cause severe
privacy concerns when the training data is privacy-sensitive, e.g., medical
images.

Differentially private classifiers: To defend against inference attacks, many
studies [4, 74, 9, 20, 50, 56] extend differential privacy [31], a rigorous
privacy notation, to classifier training. Roughly speaking, a learning
algorithm is differentially private if the distribution of the model
parameters of its learnt classifier does not change much when one training
example is added or deleted in the training dataset. Suppose we have a
randomized learning algorithm $\mathcal{A}$ whose input is a training dataset
$\mathcal{D}$ and whose output is a classifier $f\in\mathcal{F}$, where
$\mathcal{F}$ is the space of classifier. We denote by
$\mathcal{A}(\mathcal{D})$ the classifier learnt by $\mathcal{A}$ on
$\mathcal{D}$. Two training datasets $\mathcal{D}$ and $\mathcal{D}^{\prime}$
are said to be adjacent if and only if $\mathcal{D}$ and
$\mathcal{D}^{\prime}$ differ by exactly one training example. Formally, we
have the following definition for $(\epsilon,\delta)$-differential privacy:

######  Definition 7.1 ($(\epsilon,\delta)$-differential privacy [31]).

A randomized learning algorithm $\mathcal{A}$ is
$(\epsilon,\delta)$-differentially private if for any
$\mathcal{R}\subseteq\mathcal{F}$ and for any two adjacent training datasets
$\mathcal{D}$ and $\mathcal{D}^{\prime}$, $\mathcal{A}$ satisfies the
following: $\Pr[\mathcal{A}(\mathcal{D})\in\mathcal{R}]\leq
e^{\epsilon}\Pr[\mathcal{A}(\mathcal{D}^{\prime})\in\mathcal{R}]+\delta$.

A smaller $\epsilon$ indicates a stronger privacy guarantee. $\epsilon=\infty$
means no privacy guarantee, which is equivalent to training a non-private
classifier. Many differentially private learning algorithms [4, 74, 9, 20, 50,
56] have been proposed. Their key idea is to introduce randomness to the
training process. For instance, they may add random noise to the training
examples [49], gradients [4, 74, 9] used to update the parameters of a
classifier, and/or loss functions [20, 50]. Among them, DP-SGD [4] is state-
of-the-art and is applicable to deep neural networks. Roughly speaking, DP-SGD
clips the gradients and adds Gaussian noise to them before using them to
update the parameters of a classifier during training.

Limitations of differentially private classifiers: A key limitation of
differentially private learning algorithms is that they substantially
sacrifice the testing accuracy of the classifiers. In particular, a
differentially private classifier is (much) less accurate than its non-private
counterpart. Such limitation is a key obstacle for deploying differentially
private classifiers in the real world. We aim to measure whether a pre-trained
encoder can mitigate such limitation.

###  7.2 Experimental Setup

Training differentially private classifiers: We use DP-SGD [4] to train
classifiers that achieve $(\epsilon,\delta)$-differential privacy. We adopt
the public implementation [85] of DP-SGD in our experiments. For Case I and
Case II, we train classifiers with DP-SGD from scratch. For Case III-LP, we
use DP-SGD to train the parameters of the last fully connected layer of the
classifier, while for Case III-FT, we use DP-SGD to update the pre-trained
encoder and the last fully connected layer.

Evaluation metric: We use testing accuracy to evaluate the performance of a
differentially private classifier. In particular, given a testing dataset and
a classifier, testing accuracy is the fraction of the testing examples that
are correctly classified.

Hyperparameter search and parameter setting: Following previous works [31, 4],
we set $\delta=10^{-5}$. Moreover, unless otherwise mentioned, we set
$\epsilon=1.0$ to achieve a strong privacy guarantee. Given $\epsilon$ and
$\delta$, we use grid search to find the best combination of the number of
training epochs and learning rate for DP-SGD in each case, following the
hyperparameter search process in Section 4.1. Specifically, we find the best
hyperparameter setting of DP-SGD that achieves the largest accuracy on the
validation examples.

###  7.3 Experimental Results

(a)

(b)

Figure 4: (a) Comparing testing accuracy of Case III-LP and Case III-FT as
$\epsilon$ varies. (b) Comparing testing accuracy of the three cases as
$\epsilon$ varies.

Comparing Case III-LP with Case III-FT: Figure 4a compares the testing
accuracy of Case III-LP and Case III-FT on STL10 dataset when $\epsilon$
decreases from $\infty$ (no privacy guarantee) to 0.2 (strong privacy
guarantee). In these experiments, we use the image encoder [22] pre-trained by
Google on the ImageNet dataset, which is publicly available on GitHub [2]. We
did not use the OpenAI’s CLIP encoder because its neural network architecture
is a vision transformer, whose attention pooling layer is not supported by the
public implementation of DP-SGD. In particular, Case III-FT uses DP-SGD to
update both the pre-trained encoder and the last fully connected layer. Since
the public implementation of DP-SGD does not support vision transformer, we
were not able to perform experiments on DP-SGD for Case III-FT using the CLIP
encoder. We note that we use the Google’s pre-trained encoder only in the
experiments in Figure 4a, and we perform all other experiments in Case III
using CLIP.

We observe that the testing accuracy of Case III-FT drops sharply while the
testing accuracy of Case III-LP drops slowly as $\epsilon$ decreases. In other
words, Case III-LP achieves much higher testing accuracy than Case III-FT
under differential privacy. This is because Case III-FT adds larger noise to
the gradients as it updates both the pre-trained encoder and the last fully
connected layer during training. Our results indicate that Case III-LP should
be used to train a differentially private classifier when a pre-trained
encoder is available. Therefore, in the following, we focus on LP in Case III.

Comparing the three cases: Table 9 shows the testing accuracy of the
classifiers in the three cases under strong privacy guarantee on STL10
dataset. We have two observations from the results. First, we observe that
Case III achieves significantly higher testing accuracy than the other two
cases. For instance, the testing accuracies are respectively 0.237, 0.142, and
0.956 for Case I, Case II, and Case III on STL10 dataset. The reason is that
the pre-trained encoder in Case III can extract high-quality features,
enabling DP-SGD to train more accurate, diffrentially private classifiers. We
note that our observation is consistent with prior work [77], which also found
that a pre-trained encoder can improve the accuracy of a differentially
private classifier. But our evaluation is more comprehensive since we compare
training differentially private classifiers using linear probing and fine-
tuning when having a pre-trained encoder. Second, Case II achieves much higher
testing accuracy than Case I under no privacy guarantee (please see Table 2),
but we find that the testing accuracy of Case I is similar to or even higher
than that of Case II under strong privacy guarantee. The reason is that a deep
neural network classifier in Case II has much more parameters and thus DP-SGD
introduces larger noise during training, which overwhelms the expressiveness
advantages of a deep neural network. Our observation indicates that, without a
pre-trained encoder, we can train a simple linear classifier instead of a
complex deep neural network to (possibly) achieve better accuracy under strong
privacy guarantee.

Table 9: Comparing the testing accuracy of the three cases under $(1.0,10^{-5})$-differential privacy. | STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 0.237 | 0.344 | 0.020
Case II | 0.142 | 0.338 | 0.021
Case III-LP | 0.956 | 0.918 | 0.613

Impact of $\epsilon$: Figure 4b shows the impact of $\epsilon$ on the testing
accuracy for the three cases on STL10 dataset. First, we observe that the
testing accuracy of each case decreases as $\epsilon$ decreases (i.e., privacy
guarantee becomes stronger). The reason is that a smaller $\epsilon$ requires
adding larger noise during training, leading to less accurate classifiers.
Second, the testing accuracy of Case III-LP decreases slowly when
$\epsilon>1$, after which it decreases quickly. For instance, compared to Case
III-LP with $\epsilon=\infty$ (i.e., no privacy guarantee), the testing
accuracy of Case III-LP with $\epsilon=1$ (strong privacy guarantee) decreases
only by 0.029. However, the testing accuracy of Case II decreases sharply
(i.e., by 0.703) when $\epsilon$ decreases from $\infty$ to 5. Third, Case I
achieves larger testing accuracy than Case II when $\epsilon$ is small (e.g.,
$\epsilon\leq 5$), indicating that a simple linear classifier is preferred
over a complex deep neural network when a pre-trained encoder is not available
but strong privacy guarantee is desired.

Summary: We observe that a pre-trained encoder substantially improves the
accuracy of a differentially private classifier. When a pre-trained encoder is
not available, a differentially private linear classifier can be more accurate
than a differentially private deep neural network when strong privacy
guarantee is desired.

##  8 Exact Machine Unlearning

###  8.1 Related Work

The right to be forgotten: The right to be forgotten refers to the right to
have a user’s private data removed from a service. Various regulations and
laws, e.g., the European Union’s General Data Protection Regulation (GDPR)
[79], have established such right for users. In the context of machine
learning, a user may request deleting his/her data from the training dataset
and removing its effect on a classifier after the classifier has been trained.

Exact unlearning: _Machine unlearning_ [15] aims to achieve the right to be
forgotten in the context of machine learning. Specifically, given a set of
training examples to be forgotten/unlearnt (denoted as
$\mathcal{D}_{unlearn}$), machine unlearning aims to remove the effect of
these training examples on a classifier. Based on the completeness of
unlearning, machine unlearning can be categorized into _exact unlearning_ [15,
36, 12] and _approximate unlearning_ [83, 39]. Roughly speaking, exact
unlearning completely removes the effect of the training examples to be
unlearnt on the classifier, while approximate unlearning does not. Therefore,
we focus on exact unlearning in this work because it provides strong privacy
guarantees for the right to be forgotten. Following Cao & Yang [15], we
formally define exact unlearning as follows:

######  Definition 8.1 (Exact Unlearning).

Suppose we have a training dataset $\mathcal{D}$, a set of training examples
$\mathcal{D}_{unlearn}$ to be unlearnt, a randomized learning algorithm
$\mathcal{A}$, which takes a training dataset as input and outputs a
classifier. We denote an unlearning algorithm as $\mathcal{U}$, which takes
$\mathcal{A}$, $\mathcal{D}$, $\mathcal{A}(\mathcal{D})$, and
$\mathcal{D}_{unlearn}$ as input and outputs a classifier.
$\mathcal{A}(\mathcal{D}-\mathcal{D}_{unlearn})$ is the classifier learnt by
$\mathcal{A}$ on the remaining training examples
$\mathcal{D}-\mathcal{D}_{unlearn}$. Since $\mathcal{A}$ is randomized, the
learnt classifier is also randomized in the space of classifiers. We denote by
$\mathbb{F}$ the probability distribution of the classifier
$\mathcal{A}(\mathcal{D}-\mathcal{D}_{unlearn})$ in the classifier space.
Moreover, we denote by $\mathbb{F}^{\prime}$ the probability distribution of
the classifier outputted by the unlearning algorithm $\mathcal{U}$. We call
$\mathcal{U}$ exact unlearning for $\mathcal{A}$ if and only if
$\mathbb{F}=\mathbb{F}^{\prime}$ holds for arbitrary $\mathcal{D}$ and
$\mathcal{D}_{unlearn}$.

The most popular exact unlearning method is to retrain a classifier from
scratch on the remaining training examples, i.e.,
$\mathcal{U}(\mathcal{A},\mathcal{D},$
$\mathcal{A}(\mathcal{D}),\mathcal{D}_{unlearn})$ =
$\mathcal{A}(\mathcal{D}-\mathcal{D}_{unlearn})$. We call this method _retrain
from scratch_. Retrain from scratch is the only known exact unlearning method
that is applicable to any learning algorithm.

Limitations of retraining from scratch: A key limitation of retrain from
scratch is that it incurs significant computation cost for unlearning complex
classifiers such as deep neural networks. We aim to understand whether a pre-
trained encoder can enable efficient retraining from scratch while the
unlearnt classifier still achieves high accuracy.

We note that Cao and Yang [15] proposed exact unlearning methods for several
simple learning algorithms such as support vector machines, naive Bayes, and
decision trees, which are more efficient than retrain from scratch. Their
methods are applicable to a learning algorithm that 1) relies on a summation
form and 2) defines a unique globally optimal classifier for a given training
dataset. However, these exact unlearning methods are not applicable to our
three cases because the learning algorithms in our three cases do not satisfy
the above two conditions. Bourtoule et al. [12] showed that ensemble learning
can be efficiently unlearnt. However, this method is also not applicable to
our three cases since they are not ensemble learning. Therefore, we adopt
retrain from scratch as the exact unlearning method in our experiments.

###  8.2 Experimental Setup

Exact unlearning via retraining from scratch: Given a set of unlearning
training examples $\mathcal{D}_{unlearn}$, we retrain a classifier from
scratch on the remaining training examples $\mathcal{D}-\mathcal{D}_{unlearn}$
in each case. Specifically, for Case I and Case II, we train classifiers on
the remaining training examples from scratch. For Case III-LP, we train the
last fully connected layer on the remaining training examples from scratch.
For Case III-FT, we reset the encoder as its pre-trained parameters, re-
initialize the last fully connected layer, and then train them on the
remaining training examples.

Evaluation metrics: We use _testing accuracy_ and _retraining time_ as
evaluation metrics. Testing accuracy is the fraction of testing examples that
are correctly classified by the unlearnt classifier. Retraining time is the
time for training from scratch.

Hyperparameter search and parameter setting: Unless otherwise mentioned, we
set the number of training examples to be unlearnt as 50. Note that we set the
number of training examples to be unlearnt as 50 without the loss of
generality as long as this number is small compared to the training data’s
size. Moreover, we sample $\mathcal{D}_{unlearn}$ uniformly at random from a
training dataset. Given $\mathcal{D}_{unlearn}$, we use grid search to find
the best combination of the number of training epochs and learning rate for
retraining from scratch in each case, following the hyperparameter search
process described in Section 2. In particular, the best hyperparameter setting
of retraining from scratch achieves the highest accuracy on the validation
examples. Since our $\mathcal{D}_{unlearn}$ are randomly sampled, we repeat
each experiment five times and report the average results for each experiment.

###  8.3 Experimental Results

Comparing Case III-LP with Case III-FT: Table 10 shows the testing accuracy
and retraining time of unlearning for Case III-LP and Case III-FT on STL10
dataset. Case III-LP achieves a higher testing accuracy than Case III-FT on
STL10 dataset but lower testing accuracy than Case III-FT on CIFAR10 and Tiny-
ImageNet datasets (results are omitted for simplicity), which is consistent
with our results in Table 2. We observe that Case III-LP is orders of
magnitude more efficient than Case III-FT. This is because Case III-LP freezes
the pre-trained encoder when training classifier, while Case III-FT updates
both the pre-trained encoder and the last fully connected layer. Therefore, we
focus on Case III-LP in the following experiments due to its computation
efficiency.

Table 10: Testing accuracy and retraining time for Case III-LP and Case III-FT when unlearning 50 training examples. | Testing Accuracy | Retraining Time (seconds)
---|---|---
Case III-LP | 0.984 | $5.92\times 10^{1}$
Case III-FT | 0.962 | $9.38\times 10^{3}$

Comparing the three cases: Table 11b shows the testing accuracy and retraining
time of exact unlearning for the three cases when unlearning 50 training
examples on STL10, while Figure 5 shows the results when unlearning different
amounts of training examples. We observe that Case III-LP achieves the highest
testing accuracy among the three cases. This is because a pre-trained encoder
extracts generalizable feature representations, which help improve testing
accuracy. Moreover, we observe that Case I and Case III-LP are orders of
magnitude more efficient than Case II. This is because retraining the one
fully connected layer in Case I and Case III-LP is much more efficient than
retraining the deep neural network in Case II from scratch. We also note that
Case III-LP is more efficient than Case I on unlearning. The reason is that
the fully connected layer in Case III-LP has fewer parameters than the fully
connected layer in Case I. For example, on STL10, the fully connected layer in
Case III-LP has $1,024\times 10=10,240$ parameters, where 1,024 is the
dimension of the feature vector outputted by the encoder. However, the fully
connected layer in Case I has $96\times 96\times 3\times 10=276,480$
parameters, where $96\times 96\times 3$ is the dimension of training/testing
inputs. Therefore, we conclude that unlearning in Case III-LP is both much
more accurate and efficient than Case II, and is much more accurate and
slightly more efficient than Case I.

Table 11: Comparing the testing accuracy and retraining time of exact
unlearning for the three cases when unlearning 50 training examples.

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | 0.358 | 0.247 | 0.072
Case II | 0.754 | 0.946 | 0.506
Case III-LP | 0.984 | 0.954 | 0.751
(a) Testing accuracy

| STL10 | CIFAR10 | Tiny-ImageNet
---|---|---|---
Case I | $9.72\times 10^{1}$ | $7.41\times 10^{2}$ | $1.51\times 10^{3}$
Case II | $1.21\times 10^{3}$ | $8.63\times 10^{3}$ | $1.82\times 10^{4}$
Case III-LP | $5.92\times 10^{1}$ | $4.79\times 10^{2}$ | $9.41\times 10^{2}$
(b) Retraining time (seconds)

(a) Testing accuracy

(b) Retraining time

Figure 5: Testing accuracy and retraining time for the three cases when
unlearning different amount of training examples.

Comparing LP with KNN in Case III: KNN classifies a testing input based on the
labels of the $K$ nearest training inputs. Unlearning a KNN classifier is
straightforward, i.e., we directly delete the training examples to be unlearnt
from the training dataset. Therefore, we compare LP with KNN in Case III when
a pre-trained encoder is available. Specifically, in KNN, we use the pre-
trained encoder to compute a feature vector for each training/testing input;
and when finding the $K$ nearest neighbors of a testing input, we calculate
the $\ell_{1}$ distance between a training input and the testing input based
on their feature vectors.

Table 12 shows testing accuracy and retraining time of unlearning LP and KNN
in Case III in our default setting, as well as their inference time per
testing input and storage after unlearning. The storage for LP is used to
store the fully connected layer, while the storage for KNN is used to store
the feature vectors and labels of the training inputs. We observe that KNN
achieves comparable testing accuracy with LP and does not require any
retraining time. However, KNN requires orders of magnitude more storage space
and is orders of magnitude less efficient at inferring the label of a testing
input. This is because KNN directly stores the training data and requires
calculating distance between a testing input and every training input to
predict its label. On the contrary, LP’s storage and inference time for a
testing input do not depend on the training dataset size. Therefore, as the
training dataset size becomes larger, LP’s advantages with respect to storage
and inference time become more significant.

Table 12: Comparing LP with KNN when unlearning 50 training examples. |  Testing accuracy |  Retraining time (seconds) |  Inference time (seconds) |  Storage (MB)
---|---|---|---|---
LP | 0.984 | $5.92\times 10^{1}$ | $1.38\times 10^{-5}$ | $2.20\times 10^{-2}$
KNN | 0.978 | 0.00 | $3.1\times 10^{-3}$ | $2.56\times 10^{1}$

Summary: We observe that a pre-trained encoder improves the accuracy and/or
efficiency of exact unlearning via retraining from scratch. Specifically,
exact unlearning via retraining from scratch for a simple linear classifier in
Case I is efficient but not accurate. Retraining from scratch for a complex
deep neural network in Case II is more accurate than Case I but is not
efficient. Retraining from scratch for Case III-LP is both accurate and
efficient.

##  9 Conclusion, Limitations, and Future Work

In this work, via a systematic and principled measurement study, we find that
a high-quality encoder pre-trained on non-private data can improve the testing
accuracy under no attacks, certified security guarantees, and/or efficiency of
secure or privacy-preserving supervised (un)learning algorithms. We
acknowledge that our findings are limited to high-quality encoders pre-trained
on non-private data, but state-of-the-art pre-trained encoders such as CLIP
satisfy such conditions. One interesting future work is to understand whether
and when our findings still hold for an encoder pre-trained on private data in
adversarial settings.

## References

  * [1] MicroImageNet classification challenge.  https://www.kaggle.com/c/tiny-imagenet/overview, 2021.
  * [2] Public pre-trained image encoder by Google.  https://storage.cloud.google.com/simclr-gcs/checkpoints/ResNet50_1x.zip, 2021\.
  * [3] Public pre-trained image encoder of CLIP by OpenAI.  https://openaipublic.azureedge.net/clip/models/40d3657 15913c9da9857 9312b702a82c18be219cc2a73407c4526 f58eba950af/ViT-B-32.pt, 2021.
  * [4] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang.  Deep learning with differential privacy.  In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308–318, 2016.
  * [5] Naomi S Altman.  An introduction to kernel and nearest-neighbor nonparametric regression.  The American Statistician, 46(3):175–185, 1992.
  * [6] Giuseppe Ateniese, Luigi V Mancini, Angelo Spognardi, Antonio Villani, Domenico Vitali, and Giovanni Felici.  Hacking smart machines with smarter ones: How to extract meaningful data from machine learning classifiers.  International Journal of Security and Networks, 10(3):137–150, 2015\.
  * [7] Anish Athalye, Nicholas Carlini, and David Wagner.  Obfuscated gradients give a false sense of security: Circumventing defenses to adversarial examples.  In International conference on machine learning, pages 274–283. PMLR, 2018.
  * [8] Marco Barreno, Blaine Nelson, Anthony D Joseph, and J Doug Tygar.  The security of machine learning.  Machine Learning, 81(2):121–148, 2010.
  * [9] Raef Bassily, Adam Smith, and Abhradeep Thakurta.  Private empirical risk minimization: Efficient algorithms and tight error bounds.  In 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pages 464–473. IEEE, 2014.
  * [10] Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning attacks against support vector machines.  In Proceedings of the 29th International Coference on International Conference on Machine Learning, pages 1467–1474, 2012.
  * [11] Christopher M Bishop and Nasser M Nasrabadi.  Pattern recognition and machine learning, volume 4.  Springer, 2006.
  * [12] Lucas Bourtoule, Varun Chandrasekaran, Christopher A Choquette-Choo, Hengrui Jia, Adelin Travers, Baiwu Zhang, David Lie, and Nicolas Papernot.  Machine unlearning.  In 2021 IEEE Symposium on Security and Privacy (SP), pages 141–159. IEEE, 2021.
  * [13] Leo Breiman.  Bagging predictors.  Machine learning, 24(2):123–140, 1996.
  * [14] Xiaoyu Cao and Neil Zhenqiang Gong.  Mitigating evasion attacks to deep neural networks via region-based classification.  In Proceedings of the 33rd Annual Computer Security Applications Conference, pages 278–287, 2017.
  * [15] Yinzhi Cao and Junfeng Yang.  Towards making systems forget with machine unlearning.  In 2015 IEEE Symposium on Security and Privacy, pages 463–480. IEEE, 2015.
  * [16] Nicholas Carlini.  Poisoning the unlabeled dataset of semi-supervised learning.  In USENIX Security Symposium, 2021.
  * [17] Nicholas Carlini and Andreas Terzis.  Poisoning and backdooring contrastive learning.  arXiv preprint arXiv:2106.09667, 2021.
  * [18] Nicholas Carlini and David Wagner.  Adversarial examples are not easily detected: Bypassing ten detection methods.  In Proceedings of the 10th ACM workshop on artificial intelligence and security, pages 3–14, 2017.
  * [19] Nicholas Carlini and David Wagner.  Towards evaluating the robustness of neural networks.  In 2017 ieee symposium on security and privacy (sp), pages 39–57. IEEE, 2017.
  * [20] Kamalika Chaudhuri, Claire Monteleoni, and Anand D Sarwate.  Differentially private empirical risk minimization.  Journal of Machine Learning Research, 12(3), 2011.
  * [21] Jian Chen, Xuxin Zhang, Rui Zhang, Chen Wang, and Ling Liu.  De-pois: An attack-agnostic defense against data poisoning attacks.  IEEE Transactions on Information Forensics and Security, 16:3412–3425, 2021.
  * [22] Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey Hinton.  A simple framework for contrastive learning of visual representations.  In International conference on machine learning, pages 1597–1607. PMLR, 2020.
  * [23] Ting Chen, Simon Kornblith, Kevin Swersky, Mohammad Norouzi, and Geoffrey E Hinton.  Big self-supervised models are strong semi-supervised learners.  Advances in neural information processing systems, 33:22243–22255, 2020.
  * [24] Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song.  Targeted backdoor attacks on deep learning systems using data poisoning.  arXiv preprint arXiv:1712.05526, 2017.
  * [25] Charles J Clopper and Egon S Pearson.  The use of confidence or fiducial limits illustrated in the case of the binomial.  Biometrika, 26(4):404–413, 1934.
  * [26] Adam Coates, Andrew Ng, and Honglak Lee.  An analysis of single-layer networks in unsupervised feature learning.  In Proceedings of the fourteenth international conference on artificial intelligence and statistics, pages 215–223. JMLR Workshop and Conference Proceedings, 2011.
  * [27] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter.  Certified adversarial robustness via randomized smoothing.  In International Conference on Machine Learning, pages 1310–1320. PMLR, 2019.
  * [28] Gabriela F Cretu, Angelos Stavrou, Michael E Locasto, Salvatore J Stolfo, and Angelos D Keromytis.  Casting out demons: Sanitizing training data for anomaly sensors.  In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages 81–95. IEEE, 2008.
  * [29] Navneet Dalal and Bill Triggs.  Histograms of oriented gradients for human detection.  In 2005 IEEE computer society conference on computer vision and pattern recognition (CVPR’05), volume 1, pages 886–893. Ieee, 2005.
  * [30] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al.  An image is worth 16x16 words: Transformers for image recognition at scale.  In International Conference on Learning Representations, 2020.
  * [31] Cynthia Dwork, Aaron Roth, et al.  The algorithmic foundations of differential privacy.  Found. Trends Theor. Comput. Sci., 9(3-4):211–407, 2014.
  * [32] Liam H Fowl, Micah Goldblum, Ping-yeh Chiang, Jonas Geiping, Wojciech Czaja, and Tom Goldstein.  Adversarial examples make strong poisons.  In Advances in Neural Information Processing Systems, 2021.
  * [33] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart.  Model inversion attacks that exploit confidence information and basic countermeasures.  In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security, pages 1322–1333, 2015.
  * [34] Karan Ganju, Qi Wang, Wei Yang, Carl A Gunter, and Nikita Borisov.  Property inference attacks on fully connected neural networks using permutation invariant representations.  In Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, pages 619–633, 2018.
  * [35] Jonas Geiping, Liam H Fowl, W Ronny Huang, Wojciech Czaja, Gavin Taylor, Michael Moeller, and Tom Goldstein.  Witches’ brew: Industrial scale data poisoning via gradient matching.  In International Conference on Learning Representations, 2020.
  * [36] Antonio Ginart, Melody Guan, Gregory Valiant, and James Y Zou.  Making ai forget you: Data deletion in machine learning.  Advances in Neural Information Processing Systems, 32, 2019.
  * [37] Ian J Goodfellow, Jonathon Shlens, and Christian Szegedy.  Explaining and harnessing adversarial examples.  ICLR, 2015.
  * [38] Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.  Badnets: Identifying vulnerabilities in the machine learning model supply chain.  arXiv preprint arXiv:1708.06733, 2017.
  * [39] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten.  Certified data removal from machine learning models.  arXiv preprint arXiv:1911.03030, 2019.
  * [40] Raia Hadsell, Sumit Chopra, and Yann LeCun.  Dimensionality reduction by learning an invariant mapping.  In IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2006.
  * [41] Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick.  Momentum contrast for unsupervised visual representation learning.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 9729–9738, 2020.
  * [42] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep residual learning for image recognition.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770–778, 2016.
  * [43] Xiaowei Huang, Marta Kwiatkowska, Sen Wang, and Min Wu.  Safety verification of deep neural networks.  In International conference on computer aided verification, pages 3–29. Springer, 2017.
  * [44] Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong.  Intrinsic certified robustness of bagging against data poisoning attacks.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7961–7969, 2021.
  * [45] Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong.  Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing.  arXiv preprint arXiv:1912.09899, 2019.
  * [46] Jinyuan Jia, Yupei Liu, Xiaoyu Cao, and Neil Zhenqiang Gong.  Certified robustness of nearest neighbors against data poisoning and backdoor attacks.  In Proceedings of the AAAI Conference on Artificial Intelligence, 2022.
  * [47] Jinyuan Jia, Yupei Liu, and Neil Zhenqiang Gong.  Badencoder: Backdoor attacks to pre-trained encoders in self-supervised learning.  arXiv preprint arXiv:2108.00352, 2021.
  * [48] Jinyuan Jia, Binghui Wang, Xiaoyu Cao, and Neil Zhenqiang Gong.  Certified robustness of community detection against adversarial structural perturbation via randomized smoothing.  In Proceedings of The Web Conference 2020, pages 2718–2724, 2020\.
  * [49] James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar.  Pate-gan: Generating synthetic data with differential privacy guarantees.  In International conference on learning representations, 2018.
  * [50] Daniel Kifer, Adam Smith, and Abhradeep Thakurta.  Private convex empirical risk minimization and high-dimensional regression.  In Conference on Learning Theory, pages 25–1. JMLR Workshop and Conference Proceedings, 2012.
  * [51] Pang Wei Koh, Jacob Steinhardt, and Percy Liang.  Stronger data poisoning attacks break data sanitization defenses.  Machine Learning, 111(1):1–47, 2022.
  * [52] Simon Kornblith, Jonathon Shlens, and Quoc V Le.  Do better imagenet models transfer better?  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 2661–2671, 2019.
  * [53] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [54] Ananya Kumar, Aditi Raghunathan, Robbie Matthew Jones, Tengyu Ma, and Percy Liang.  Fine-tuning can distort pretrained features and underperform out-of-distribution.  In International Conference on Learning Representations, 2021.
  * [55] Alexander Levine and Soheil Feizi.  Deep partition aggregation: Provable defenses against general poisoning attacks.  In International Conference on Learning Representations, 2020.
  * [56] Hongbin Liu, Jinyuan Jia, and Neil Zhenqiang Gong.  On the intrinsic differential privacy of bagging.  arXiv preprint arXiv:2008.09845, 2020.
  * [57] Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg.  Fine-pruning: Defending against backdooring attacks on deep neural networks.  In International Symposium on Research in Attacks, Intrusions, and Defenses, pages 273–294. Springer, 2018.
  * [58] Yingqi Liu, Shiqing Ma, Yousra Aafer, Wen-Chuan Lee, Juan Zhai, Weihang Wang, and Xiangyu Zhang.  Trojaning attack on neural networks.  NDSS, 2017.
  * [59] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu.  Towards deep learning models resistant to adversarial attacks.  In International Conference on Learning Representations, 2018.
  * [60] Luis Muñoz-González, Battista Biggio, Ambra Demontis, Andrea Paudice, Vasin Wongrassamee, Emil C Lupu, and Fabio Roli.  Towards poisoning of deep learning algorithms with back-gradient optimization.  In Proceedings of the 10th ACM Workshop on Artificial Intelligence and Security, pages 27–38, 2017.
  * [61] Blaine Nelson, Marco Barreno, Fuching Jack Chi, Anthony D Joseph, Benjamin IP Rubinstein, Udam Saini, Charles Sutton, J Doug Tygar, and Kai Xia.  Exploiting machine learning to subvert your spam filter.  LEET, 8(1-9):16–17, 2008.
  * [62] Nicolas Papernot, Patrick McDaniel, Xi Wu, Somesh Jha, and Ananthram Swami.  Distillation as a defense to adversarial perturbations against deep neural networks.  In 2016 IEEE symposium on security and privacy (SP), pages 582–597. IEEE, 2016.
  * [63] Andrea Paudice, Luis Muñoz-González, Andras Gyorgy, and Emil C Lupu.  Detection of adversarial training examples in poisoning attacks through anomaly detection.  arXiv preprint arXiv:1802.03041, 2018.
  * [64] Andrea Paudice, Luis Muñoz-González, and Emil C Lupu.  Label sanitization against label flipping poisoning attacks.  In Joint European conference on machine learning and knowledge discovery in databases, pages 5–15. Springer, 2018.
  * [65] Neehar Peri, Neal Gupta, W Ronny Huang, Liam Fowl, Chen Zhu, Soheil Feizi, Tom Goldstein, and John P Dickerson.  Deep k-nn defense against clean-label data poisoning attacks.  In European Conference on Computer Vision, pages 55–70. Springer, 2020.
  * [66] Rafael Pinot, Laurent Meunier, Alexandre Araujo, Hisashi Kashima, Florian Yger, Cédric Gouy-Pailler, and Jamal Atif.  Theoretical evidence for adversarial robustness through randomization.  Advances in Neural Information Processing Systems, 32, 2019.
  * [67] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al.  Learning transferable visual models from natural language supervision.  In International Conference on Machine Learning, pages 8748–8763. PMLR, 2021.
  * [68] Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and Zico Kolter.  Certified robustness to label-flipping attacks via randomized smoothing.  In International Conference on Machine Learning, pages 8230–8241. PMLR, 2020.
  * [69] Benjamin IP Rubinstein, Blaine Nelson, Ling Huang, Anthony D Joseph, Shing-hon Lau, Satish Rao, Nina Taft, and J Doug Tygar.  Antidote: understanding and defending against poisoning of anomaly detectors.  In Proceedings of the 9th ACM SIGCOMM Conference on Internet Measurement, pages 1–14, 2009.
  * [70] Hadi Salman, Jerry Li, Ilya Razenshteyn, Pengchuan Zhang, Huan Zhang, Sebastien Bubeck, and Greg Yang.  Provably robust deep learning via adversarially trained smoothed classifiers.  Advances in Neural Information Processing Systems, 32, 2019.
  * [71] Ali Shafahi, W Ronny Huang, Mahyar Najibi, Octavian Suciu, Christoph Studer, Tudor Dumitras, and Tom Goldstein.  Poison frogs! targeted clean-label poisoning attacks on neural networks.  Advances in neural information processing systems, 31, 2018.
  * [72] Shawn Shan, Emily Wenger, Jiayun Zhang, Huiying Li, Haitao Zheng, and Ben Y Zhao.  Fawkes: Protecting privacy against unauthorized deep learning models.  In 29th USENIX Security Symposium (USENIX Security 20), pages 1589–1604, 2020.
  * [73] Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov.  Membership inference attacks against machine learning models.  In 2017 IEEE symposium on security and privacy (SP), pages 3–18. IEEE, 2017.
  * [74] Shuang Song, Kamalika Chaudhuri, and Anand D Sarwate.  Stochastic gradient descent with differentially private updates.  In 2013 IEEE Global Conference on Signal and Information Processing, pages 245–248. IEEE, 2013.
  * [75] Octavian Suciu, Radu Marginean, Yigitcan Kaya, Hal Daume III, and Tudor Dumitras.  When does machine learning $\\{$FAIL$\\}$? generalized transferability for evasion and poisoning attacks.  In 27th $\\{$USENIX$\\}$ Security Symposium ($\\{$USENIX$\\}$ Security 18), pages 1299–1316, 2018.
  * [76] Christian Szegedy, Wojciech Zaremba, Ilya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfellow, and Rob Fergus.  Intriguing properties of neural networks.  ICLR, 2014.
  * [77] Florian Tramer and Dan Boneh.  Differentially private learning needs better features (or much more data).  In International Conference on Learning Representations, 2021.
  * [78] Brandon Tran, Jerry Li, and Aleksander Madry.  Spectral signatures in backdoor attacks.  Advances in neural information processing systems, 31, 2018.
  * [79] Paul Voigt and Axel Von dem Bussche.  The eu general data protection regulation (gdpr).  A Practical Guide, 1st Ed., Cham: Springer International Publishing, 10(3152676):10–5555, 2017.
  * [80] Binghui Wang and Neil Zhenqiang Gong.  Stealing hyperparameters in machine learning.  In 2018 IEEE Symposium on Security and Privacy (SP), pages 36–52. IEEE, 2018.
  * [81] Binghui Wang, Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong.  Certified robustness of graph neural networks against adversarial structural perturbation.  In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining, pages 1645–1653, 2021.
  * [82] Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao Zheng, and Ben Y Zhao.  Neural cleanse: Identifying and mitigating backdoor attacks in neural networks.  In IEEE Symposium on Security and Privacy, 2019.
  * [83] Yinjun Wu, Edgar Dobriban, and Susan Davidson.  Deltagrad: Rapid retraining of machine learning models.  In International Conference on Machine Learning, pages 10355–10366. PMLR, 2020.
  * [84] Weilin Xu, David Evans, and Yanjun Qi.  Feature Squeezing: Detecting Adversarial Examples in Deep Neural Networks.  In Proceedings of the 2018 Network and Distributed Systems Security Symposium (NDSS), 2018.
  * [85] Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, et al.  Opacus: User-friendly differential privacy library in pytorch.  arXiv preprint arXiv:2109.12298, 2021.
  * [86] Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, Andre Susano Pinto, Maxim Neumann, Alexey Dosovitskiy, et al.  A large-scale study of representation learning with the visual task adaptation benchmark.  arXiv preprint arXiv:1910.04867, 2019.

(a) Testing accuracy (b) ACPS

Figure 6: Impact of $N$ on the testing accuracy of bagging under no attacks
and ACPS of bagging against data poisoning and backdoor attacks. Figure 7:
Impact of $\alpha$ on the ACPS of bagging against data poisoning and backdoor
attacks.

(a) Testing accuracy

(b) ACR

Figure 8: Impact of $M$ on the testing accuracy and ACR of randomized
smoothing. Figure 9: Impact of $\alpha$ on the ACR of randomized smoothing.