# Sleep syndromes onset detection based on automatic sleep staging algorithm

Tim Cvetko, Tinkara Robek

(May 2021)

##  1 Abstract

Sleep specialists often conduct manual sleep stage scoring by visually
inspecting the patient’s neurophysiological signals collected at sleep labs.
This is, generally, a difﬁcult, tedious and time-consuming task. The
limitations of manual sleep stage scoring have escalated the demand for
developing Automatic Sleep Stage Classiﬁcation (ASSC) systems. Sleep stage
classiﬁcation refers to identifying the various stages of sleep and is a
critical step in an effort to assist physicians in the diagnosis and treatment
of related sleep disorders. In this paper, we propose a novel method and a
practical approach to predicting early onsets of sleep syndroms, including
restless leg syndrome, insomnia, based on an algorithm which is comprised of
two modules. A Fast Fourier Transform is applied to 30 seconds long epochs of
EEG recordings to provide localized time-frequency information, and a deep
convolutional LSTM neural network is trained for sleep stage classification.
Automating sleep stages detection from EEG data offers a great potential to
tackling sleep irregularities on a daily basis. Thereby, a novel approach for
sleep stage classification is proposed which combines the best of signal
processing and statistics. In this study, we used the PhysioNet Sleep European
Data Format (EDF) Database. The code evaluation showed impressive results,
reaching accuracy of 90.43, precision of 77.76, recall of 93,32, F1-score of
89.12 with the final mean false error loss 0.09. All the source code is
availlable at https://github.com/timothy102/eeg.

###  1.1 Index Terms:

Sleep stage classification, algorithm design, onset detection, convolutional
neural networks, signal processing, recurrent neural networks, fourier
transform, CEEMDAN, preprocessing

##  2 Introduction

Sleep stage classification is crucial for our day-to-day functioning and
disease prevention, such as obesity, type 2 diabetes, and different
psychiatric disorders that may develop in association with the shortage of
sleep.Maintaining a healthy sleep schedule is significant for obtaining our
natural circadian rhythm and the normal course of sleep. This must include REM
(rapid-eye movement) and non-REM phases. NREM is specified by slow-wave
activity (delta power). REM phase is characterized by the eye movements which
we track with EOG (electrooculogram), low muscle tone which we track with
EMG(electromyogram), low amplitude waves, and generally mixed frequency EEG
(electroencephalogram). It is also a stage where dreams occur. The brain is as
active during REM as during wakefulness, only in different parts
(correspondingly, the prefrontal cortex, responsible for judgment and decision
making is deactivated during both phases). The REM state is initialized by the
neurons located in the brainstem. The process of recording sleep in the
laboratories for the purposes of examining its structure (mainly in terms of
slow-wave activity) is known as polysomnography. Polysomnograms can show the
diagnostics of various disorders during sleep. They are commonly used for
identifying disorders such as obstructive sleep apnea, excessive daytime
sleepiness, and insomnia. Polysomnograms record numerous types of information:
EEG (electroencephalogram; for recording brain waves), EOG (electrooculogram;
for recording eye movements), EMG (electromyogram; recording of the electrical
activity of muscle surfaces), EKG (electrocardiogram). Combining the gathered
data allows us to identify the individual’s stage of sleep. For the purposes
of recognizing sleep apnea, it is also required to record snoring, nasal and
oral airflow, movement of the abdomen and chest, and pulse oximetry. There are
multiple types of waves measured in EEG which tell whether the person is
asleepor awake and what stage they are in. Alpha activity (frequency: 8-13Hz)
is present in the occipital cortex when a person is resting with their eyes
closed and goes away when they wake up or fall asleep. Theta activity (4-7Hz)
is the most common frequency during sleep. Delta activity is known as slow-
wave activity (0,5-2/4Hz) with higher amplitudes and is mostly present in the
frontal areas of the cortex. Sleep spindles (11-16Hz) normally indicate stage
2 of NREM sleep, with a duration of 2-3 seconds. K complexes are also most
common in stage 2 of NREM, while they might appear in other phases as well.
Their amplitude is not specified, while the time span must be at least 0.5
seconds.Sleep stages are regulated by individual neurotransmitters.
Wakefulness is a heterogeneous state, maintained by neurotransmitters
acetylcholine, serotonin, norepinephrine, histamine, dopamine, hypocretin, and
glutamate. NREM is initialized by GABA and adenosine, while acetylcholine also
sends signals for REMonset. Interactions between neurotransmitters determine
behavioral states at any given time. During sleep, they define muscle tone,
eye movements and EEG activity. The same neurotransmitter can have opposite
effects during wakefulness and sleep and in different brain regions. The
preoptic area of the brain (anterior hypothalamus) is known to act as a sleep
center, while the posterior hypothalamus acts as a wakefulness center.
Electrical stimulation of the preoptic area, therefore, has the ability to
initiate sleep. Apart from the objective reasons for not sleeping long enough
(the recommended 8 hours, for obtaining full sleep cycles), there are also
multiple sleeping disorders present in today’s society. Sleeping disorder is
usually a composition of multiple neurological modifications that may be
caused by external or internal factors. These factors include our lifestyle,
genetics, associated diseases, psychiatric disorders, and so on. Disordered
sleeping is alarmingly common in modern society. . In the field of various
disorders, the most common persist to stay the following: insomnia, sleep-
disordered breathing (obstructive sleep apnea, hyperventilation), central
disorders of hypersomnolence (narcolepsy, idiopathic hypersomnia, Kleine-Levin
Syndrome), circadian rhythm disorders, parasomnias (sleepwalking, terrors,
sleep eating disorders, sleep enuresis) and sleep-related movement disorders
(restless leg syndrome, periodic limb movement disorder). Insomnia and other
disorders that result in trouble sleeping are often associated with multiple
chronic health conditions. They have an impact on blood pressure and blood
sugar levels, therefore they put us at risk of coronary diseases and metabolic
imbalances. Middle-aged/older parts of the population and obese individuals
are at grater risk of developing these issues. In addition, sex also plays a
role in developing some sleeping disorders - males are more likely to develop
obstructive sleep apnea, while women are predisposed to insomnia. The first
step for identifying problems with sleep is by clinical approach with ESS
(EpworthSleepiness Scale)[0]. Insomnia can arise as chronic insomnia or in a
short-term form. Its typical symptoms are problems initiating or maintaining
sleep, non-restorative sleep, and waking too early which result in daily
distress. These issues occur due to the brain’s arousal systems which are not
turning off. It is diagnosed in a laboratory with polysomnography. It can be a
cause for endothelial dysfunction, oxidative stress, inflammation,
hypertension, and even stroke in severe cases. Ordinarily, it is treated with
CPAP (continuous positive airway pressure).

##  3 Methodology

###  3.1 Event detection during sleep

Although detecting periods of raised or lowered activity during sleep is an
appealing task, it is rather interesting to detect transient, short signals.
Furthermore, during sleep we can for example detect events like QRS complexes
in the ECG or EEG events like slow waves (single waves of about 0.5 to 2 Hz
which have a high amplitude of about 75 uV), sleep spindles (transient waxing
and waning events of about 0.5 to 2 seconds duration and 15 to 50 uV maximal
amplitude). For the sake of this research and simplicity we do not make any
distinction between slow-waves, K-complexes or slow oscillations but lump them
all together.

###  3.2 Detailed description of the methodology

For the preprocessing part, we took advantage of the complete ensemble
empirical mode decomposition with adaptive noise (CEEMDAN) as a noise assisted
EMD technique. Several signal processing methods have been developed in recent
years. The traditional signal processing method is based on the Fast Fourier
Transform. However, this method alone cannot obtain the time-domain and
frequency-domain analyzed results simultaneously. Many time-frequency analysis
methods have been applied to diagnoses for vibration signals, such as the
Wigner-Ville distribution (WWD) as proposed in [2]. This algorithm
successively computes the analytic signal corresponding to the input signal,
forms a weighted kernel function, and analyzes the kernel via a discrete
Fourier transform (DFT). To evaluate the analytic signal required by the
algorithm, it is shown that the time domain definition implemented as a finite
impulse response (FIR) filter is practical and more efficient than the
frequency domain definition of the analytic signal, according to [3]. The
wavelet transform ([4], [5]) utilizes the Fast Fourier Transform to extract
frequency based wavelets. Empirical mode composition is one of the most
powerful signal processing techniques used for fault diagnosis. Deriving from
local characteristic timescales of a signal and can decompose the signal into
a set of complete and almost orthogonal components known as intrinsic mode
function (IMF). The IMFs indicate the natural oscillatory mode imbedded in the
signal and serve as the basis functions, which are determined by the signal
itself, rather than by predetermined kernels. Therefore, it is a self-adaptive
signal processing technique that is suitable for nonlinear and nonstationary
processes and is suitable for fault feature extraction of spiral-bevel gears.
According to [5], CEEMDAN has been proven to be an effective method for
analyzing nonstationary signal followed by strong noise. First, the raw
vibration signal is decomposed by the CEEMDAN method to obtain a series of
intrinsic modal functions (IMFs). The IMFs which included greater amounts
fault information are selected as the optimal IMFs based on the correlation
coefficient. Next, the permutation entropy values of the optimal IMFs are
calculated. In order to obtain accurate permutation entropy values, the two
key parameters, namely, embedding dimension and delay time, are optimized by
using the overlapping parameter method. In order to assess the sensibility of
the permutation entropy features, the support vector machine (SVM) is used as
the classifier for fault mode identification, and the diagnostic accuracy can
verify its sensibility.

###  3.3  Model architecture

The standard practice for image recognition, computer vision and more are deep
convolutional neural networks. Models like, LeNet[7], AlexNet[8], ImageNet[9]
and more work exclusively on 2D data. They are also referred to as 2D CNNs.
With the same idea in mind, 1D CNN have been developed. Despite the obvious
fact, that the 1D CNNs apply a 1D kernel to data, some of the advantages are:
1D CNNs don’t require heavy matrix operations ( nor at the forward pass or the
backpropagation). Potentially, what this means is that they are, compared to
their 2D counterparts, computionally less complex and can run on CPU hardware.

In this study, we have come up with a twin fully connected convolutional
network. Each convolutional block consists of a convolutional 1D layer, which
is passed through a Leaky Rectified Linear Unit as a nonlinearity. The input
signal then passes a max-pooling layer with the stride of 2, following that is
batch normalization layer and finally the Bidirectional layer. Each twin
structure contains three such blocks. The outputs of the convolutional-LSTM
blocks are then concatenated across axis 1 in order to be finally passed
through a fully connected 64 unit dense layer. We use the softmax activation
to recieve the final scores for each sleep stage. The CNN consists of three
different-sized filters with the idea in mind being that small filters extract
temporal information and large filters to extract frequency information. The
idea behind these variable sizes of filters comes from the signal processing
community to have a trade-off between extracting time domain and frequency
domain features [6]. This helps get benefit from both time and frequency
domain features in the classification task. The feature map generated from the
1D concatenated output from the twin convolutional blocks are intertwined with
long short-term memory (LSTM) units to capture the complex context
dependencies between the inputs and the targets.

###  3.4 Utilizing the Conv-1D and the Bidirectional LSTM

The Conv-LSTM network combines the best of both worlds, one-dimensional
convolutional layers handles spatial data using a kernel to train a set of
filters that best represent the hyperplane and the LSTM which encodes temporal
inputs using cell state memory. To put it differently, Conv-LSTM predicts the
future state of a cell given vectors on a spatial grid and past states of
neighbours.

Convolutional-LSTM layer works by passing the 1D kernel over a set of training
points and its result a.k.a feature map is passed onto the LSTM cell. In this
project, we have utilized the bidirectional recurrent neural network instead
of the standard LSTM cell. Put simply, this was enabled due to the limitations
of LSTM having the limitation of being restricted from processing previous
input state. Given the inputs x = x0, xN , which are single dimensional data
of a 30-second clip, which should assure stability and little overlap, these
inputs are passed into the twin architecture.

Figure 1: A schema of the twin convolutional Bidirectional LSTM network

###  3.5 Loss calculation

Quite obviously, sleep stage classification encounters the class imbalance
issue. To alleviate this issue, we have taken both the extended mean false
error(MFE) and the mean squared false error(MSFE) for multiclass
classification.

$MFE_{L}=\sqrt{\frac{1}{N}\sum\\_{i=1}^{C}(x_{i}-\hat{x})^{2}}$

###  3.6 Unsupervised method for detecting onsets of sleep syndromes

Syndromes in question are restless leg syndrome(RLS), rapid Eye Movement (REM)
sleep behaviour disorder, insomnia, sleep apnea and narcolepsy. In attempt to
detect these complex syndromes through EEG data, we have come up with the
following:

####  3.6.1 Restless leg syndrome

A dopaminergic drug - lisuride exhibited increase in alpha, decrease in beta
and slow activities on brain function measured by computerized EEG. It was
postulated that reverse EEG changes might play role in the pathogenesis of
RLS. During transition from wakefulness to sleep stage 1 changes in alpha
activity initiate long-lasting alpha arousal responses and they continue
increasingly at sleep stage 2. This dysfunction is probably due to a genetic
vulnerability of EEG alpha rhythm and disinhibits the diencephalospinal
dopamine system, mostly during sleep but also during wakefulness. The
disinhibition produces background for activation of PLMs, disturbing
sensations in brainstem and urge to move, motor restlessness at cerebral
cortex, generally for legs. All lead to severe insomnia. In RLS patients,
forced deviations from alpha to theta or beta activity are unsuitable and
resting EEGs reflect a dopamine receptor-specific ’individual sensitivity.’
This vulnerability is alleviated after lisuride with suitable CEEG changes.

We have designed an unsupervised statistical inference model for approximating
the restless leg syndrome in EEG. First the Savitzky–Golay filter was applied
to each 30-second window for the purpose of smoothing the data, that is, to
increase the precision of the data without distorting the signal tendency.
This is achieved, in a process known as convolution, by fitting successive
sub-sets of adjacent data points with a low-degree polynomial by the method of
linear least squares. Next, an orthnogonal discret Fourier Transform was
applied to the data to decompose functions depending on space or time into
functions depending on spatial or temporal frequency. At last, the final RLS
score is computed by applying the sigmoid activation function to the fourier-
transformed data.

####  3.6.2 Sleep apnea

When a person is sleeping, due to pause in breathing, carbon dioxide may build
up in the bloodstream. When this reaches a critical level, it is detected by
chemoreceptors. These receptors signal an alarm to the brain to wake the
sleeping person and breathe in air. As a result, a transition in sleep stages
occurs, which in turn, causes fluctuation in activity level of various
frequency bands of the EEG signal. Hence, more distinct features can be
preserved in frequency band-limited signals for apnea detection compared with
that in full-band EEG signal. As a result, for apnea event detection,
characteristics of band-limited signals are used instead of analysing full-
band EEG signal. EEG signal is partitioned into five frequency bands [10]
including delta (0.25–4 Hz), theta (4–8 Hz), alpha (8–12 Hz), sigma (12–16 Hz)
and beta (16–40 Hz). Spectral filtering is done in fast Fourier transform
domain to achieve this division.

In order to attain a relative score for approximating sleep apnea possibility,
we have adopted the method proposed in [7] .For classification of apnea and
non-apnea events, a subject-specific classification scheme based on feature is
introduced in this proposed method. Inter-band energy ratio of band-limited
EEG signal, expected to possess differentiating characteristic for apnea and
non-apnea events, is proposed as the feature. During sleep apnea, the energy
contents in various frequency bands change significantly with respect to non-
apnea events.

####  3.6.3 REM behaviour sleep disorder

Despite what was presented in [9], we have come about a rather simple, but
clever way of detecting the REM instability score. A relative score was
calculated by using a greedy algorithm for longest continuing sequence [10] to
obtain a value that should correspond to the disturbance of REM sleep in an
individual.

####  3.6.4 Narcolepsy

According to [11] patients with narcolepsy showed lower alpha power, higher
delta and theta power during wakefulness, and higher alpha and beta power
during rapid eye movement (REM) sleep. The former two groups also showed lower
sleep efficiency and a higher rate of positivity of REM-related symptoms than
the other two groups. With this idea in mind, we have combined the REM
instability score and the obtained frequency range with wavelet transform on
the first and last 10 percent of sleep, indicating worse sleep-to-wake
transitions or vice versa.

####  3.6.5 Insomnia

Insomnia or sleeplessness is a sleep disorder in which there is an inability
to fall asleep or to stay asleep as long as desired. Following the previous
work done by Mohd Maroof Siddiqui, Geetika Srivastava, and Syed Hasan Saeed in
[11]. Now each clipped signal is preprocessed and then passed through the
Hanning window low pass filter for removing the high frequency components that
eventually indicate noise because major proportion of EEG signals are limited
within the range of 25 Hz. Hence, the filter based in FIR filter design of
order 200 with cut off frequency of 25 Hz with shape of hanning window. At
this stage, we adopt a method for extracting frequency length windows via the
Welch Power Spectrum [12]. This score, obtained with softmax and the REM
instability score combine for the insomnia score.

####  3.6.6 Sleep depth

Given a great sleep stage classifier, we concluded to not only move in the
direction of detecting abnormalities, but to also quantify sleep depth. First,
the raw records are pushed through a Savgol filter to noise filtering.
Furthermore, a Fast Fourier Transform has given us a distribution of
frequencies. At this stage, we evaluted the FFT distribution to obtain the
sleep depth score along with the REM instability score.

Figure 2: Polysomnography plot for a single patient. Picture was generated
with the MNE Python library

Syndromes | RLS | REM disorder | Apnea | Narcolepsy | Insomnia | Sleep depth
---|---|---|---|---|---|---
In total | 177983 | 6674 | 8899 | 4449 | 48945 | 164738
Percentage | 7.80 | 0.29 | 0.41 | 3,0 | 22 | 74.0
Percentage given NCHS | 7-10 | 0.5-1 | 0.5 | 3-7 | 10-30 | 66

##  4 Experimental results

###  4.1 Data

For the purposes of this research, we used the Physionet Sleep-EDF dataset.
The sleep-edf database contains 197 whole-night PolySomnoGraphic sleep
recordings, containing EEG, EOG, chin EMG, and event markers. Some records
also contain respiration and body temperature.The Sleep-EDF dataset contains
two different studies including study of age effects on sleep in healthy
individuals (SC = Sleep Cassette) and study of temazepam effects on sleep (ST
= Sleep Telemetry). The dataset includes whole-night polysomnograms (PSGs)
sleep recordings at the sampling rate of 100 Hz. Each record contains EEG
(from Fpz-Cz and Pz-Oz electrode locations), EOG, chin electromyography (EMG),
and event markers. Few records often also contain oro-nasal respiration and
rectal body temperature. The hypnograms (sleep stages; 30-s epochs) were
manually labeled by well-trained technicians according to the Rechtschaffen
and Kales standard. Each stage was considered to belong to a different class
(stage). The classes include W, REM, N1, N2, N3, N4, M. Data syndrome
comparison was done according to [13]

Dataset | W | N1 | N2 | N3-N4 | REM | Total
---|---|---|---|---|---|---
Sleep-EDF-13 | 8285 | 2804 | 17799 | 5703 | 7717 | 42308
Sleep-EDF-18 | 65951 | 21522 | 96132 | 13039 | 25835 | 222479

It is worth noting that the sleep stages in the Physionet’s Sleep-EDF database
are not normally distributed. There is a significantly higher number of W and
N2 stages than others which is causing class imbalance. We have discussed this
at Loss calculation.

The model was trained for 20 epochs. We used the Adam optimizer to minimize
the MFE loss with a batch size of 16 and a learning rate alpha = 0.001. We
also added the L2 regularization penalty with beta being = 0.001 to mitigate
the overfitting. For this goal, we used Python as the programming language and
TensorFlow as the framework.

By employing the Conv-1D and the Bidirectional LSTM twin network, we have
succesfully taken advantage of the temporal and spatial component of the
signal processing nature. To reduce the class imbalances problem, we adopted
the weighted MFE loss.

Accuracy | Precision | Recall | F1-score | Final MFE
---|---|---|---|---
90.43 | 77.76 | 93.32 | 89.12 | 0.09

.

##  5 Conclusion and Future Work

In this paper, we have successfully proposed a new deep learning approach to
the challenging problem of sleep stage classification that is essential for
further analysis of the human brain activity. We utilized a two-part
convolutional-LSTM block along with a multi-layer perceptron to classify sleep
stages from EEG data with the accuracy of . By incoorporating a vastly
important CEEMDAN preprocessing method, we build a more stable and noise-free
variant of our data, which enabled building an end-to-end trainable model for
not only classifying sleep stages, but also detect early onsets of frequently
occuring sleep syndroms. Our algorithm takes advantage of both the spatial and
temporal dimension of signal processing, as well as statistical analysis to
come up with a score that represents the sleep stage the most. As a
limitation, we would like to add that no data is known to bare diluted
patients. For future work, given proper data, we would like to do a follow-up.
In the future, we intend to extent this using multimodal polysomnography to
enhance the model’s performance and usability. Following our work, we will
investigate how these syndrome predictions/scores align with actual scores and
will hopefully serve as a professional service for automatic sleep stage and
syndrome onset detection.

##  6  References

[1] https://epworthsleepinessscale.com/about-the-ess/

[2] Shie Qian and Dapang Chen, ”Decomposition of the Wigner-Ville distribution
and time-frequency distribution series,” in IEEE Transactions on Signal
Processing, vol. 42, no. 10, pp. 2836-2842, Oct. 1994, doi: 10.1109/78.324750.

[3] B. Boashash and P. Black, ”An efficient real-time implementation of the
Wigner-Ville distribution,” in IEEE Transactions on Acoustics, Speech, and
Signal Processing, vol. 35, no. 11, pp. 1611-1618, November 1987, doi:
10.1109/TASSP.1987.1165070.

[4] Katsuhiro Inoue, Akihiko Takajo, Makoto Maeda and Shigeaki Matsuoka,
”Tuning method of modified wavelet transform in human sleep EEG analysis,”
2007 International Conference on Control, Automation and Systems, 2007, pp.
2784-2789, doi: 10.1109/ICCAS.2007.4406842.

[5] Xujing Yao, Ji Han, COVID-19 Detection via Wavelet Entropy and
Biogeography-Based Optimization, COVID-19: Prediction, Decision-Making, and
its Impacts, 10.1007/978-981-15-9682-7-8, (69-76), (2021).

[6] https://www.hindawi.com/journals/sv/2019/7806015/. [7] Deep Convolutional
Neural Networks for Image Classification: A Comprehensive Review - Scientific
Figure on ResearchGate.

Available from: https://www.researchgate.net/figure/Architecture-of-
LeNet-5-LeCun-et-al-1998-fig2-317496930 [accessed 3 May, 2021]

[8] M. X. Cohen, Analyzing neural time series data: theory and practice. MIT
press, 2014.

[9] Krizhevsky, A., Sutskever, I. and Hinton, G. E. (2012). ImageNet
Classification with Deep Convolutional Neural Networks. In F. Pereira, C. J.
C. Burges, L. Bottou and K. Q. Weinberger (ed.), Advances in Neural
Information Processing Systems 25 (pp. 1097–1105) . Curran Associates, Inc.

[10] Saha S, Bhattacharjee A, Fattah SA. Automatic detection of sleep apnea
events based on inter-band energy ratio obtained from multi-band EEG signal.
Healthc Technol Lett. 2019;6(3):82-86. Published 2019 Jun 3.
doi:10.1049/htl.2018.5101.

[11] J. Deng, W. Dong, R. Socher, L. Li, Kai Li and Li Fei-Fei, ”ImageNet: A
large-scale hierarchical image database,” 2009 IEEE Conference on Computer
Vision and Pattern Recognition, 2009, pp. 248-255, doi:
10.1109/CVPR.2009.5206848.

[12] Ferri R, Rundo F, Silvani A, Zucconi M, Bruni O, Ferini-Strambi L, Plazzi
G, Manconi M. REM Sleep EEG Instability in REM Sleep Behavior Disorder and
Clonazepam Effects. Sleep. 2017 Aug 1;40(8). doi: 10.1093/sleep/zsx080. PMID:
28482056.

[13] Schensted, C. (1961). Longest Increasing and Decreasing Subsequences.
Canadian Journal of Mathematics, 13, 179-191. doi:10.4153/CJM-1961-015-3.

[14] Sasai-Sakuma T, Inoue Y. Differences in electroencephalographic findings
among categories of narcolepsy-spectrum disorders. Sleep Med. 2015
Aug;16(8):999-1005. doi: 10.1016/j.sleep.2015.01.022. Epub 2015 Apr 1. PMID:
26026626.

[15] Siddiqui MM, Srivastava G, Saeed SH. Diagnosis of insomnia sleep disorder
using short time frequency analysis of PSD approach applied on EEG signal
using channel ROC-LOC. Sleep Sci. 2016;9(3):186-191.
doi:10.1016/j.slsci.2016.07.002 [16] Zhao, Li and He, Yang. (2013). Power
Spectrum Estimation of the Welch Method Based on Imagery EEG. Applied
Mechanics and Materials. 278-280. 1260-1264.
10.4028/www.scientific.net/AMM.278-280.1260.

[17] https://www.cdc.gov/nchs/nvss/index.html[Accessed 4.5.2021]


1]Meta AI 2]Mila - Québec AI Institute, Montreal, Quebec, Canada 3]Department
of Computer Science, McGill University, Montreal, Quebec, Canada 4]Canada
CIFAR AI Chair Jonathan Lebensold at , Chuan Guo at

# DP-RDM: Adapting Diffusion Models to Private Domains Without Fine-Tuning

Jonathan Lebensold  Maziar Sanjabi  Pietro Astolfi  Adriana Romero-Soriano
Kamalika Chaudhuri  Mike Rabbat  Chuan Guo  [  [  [  [<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Text-to-image diffusion models have been shown to suffer from sample-level
memorization, possibly reproducing near-perfect replica of images that they
are trained on, which may be undesirable. To remedy this issue, we develop the
first differentially private (DP) retrieval-augmented generation algorithm
that is capable of generating high-quality image samples while providing
provable privacy guarantees. Specifically, we assume access to a text-to-image
diffusion model trained on a small amount of public data, and design a DP
retrieval mechanism to augment the text prompt with samples retrieved from a
private retrieval dataset. Our _differentially private retrieval-augmented
diffusion model_ (DP-RDM) requires no fine-tuning on the retrieval dataset to
adapt to another domain, and can use state-of-the-art generative models to
generate high-quality image samples while satisfying rigorous DP guarantees.
For instance, when evaluated on MS-COCO, our DP-RDM can generate samples with
a privacy budget of $\epsilon=10$, while providing a $3.5$ point improvement
in FID compared to public-only retrieval for up to $10,000$ queries.

Figure 1: Samples generated by our _differentially private retrieval-augmented
diffusion model_ (DP-RDM), which was trained on face-blurred ImageNet, using
different private retrieval datasets at inference time: Shutterstock, MS-COCO
with face-blurring (FB), ImageNet FB, and CIFAR-10. We calibrated the noise
added in each row for a privacy budget of $\epsilon=10$ after answering
$1,000$ queries. Each query uses $k=18$ neighbors for retrieval augmentation
and a 0.1%-0.3% random subset of the retrieval dataset. The differences
between the generated images show how swapping the private retrieval dataset
changes the distribution of the generated images to adapt to a given data
domain, _e.g._ , the differences in laptop and smart watch, or missing
concepts such as goose, llama, smart watch and laptop in CIFAR-10.

##  1 Introduction

Text-to-image diffusion models (Ho et al., 2020; Song et al., 2020) enable
highly customizable image generation, producing photo-realistic image samples
that can be instructed through text prompting. However, recent studies also
showed that it is possible to prompt text-to-image diffusion models to produce
near-perfect replica of some of their training samples (Somepalli et al.,
2023; Carlini et al., 2023).

One promising strategy for mitigating this risk is through _differential
privacy_ (DP; Dwork et al. (2006)). In essence, if a generative model
satisfies DP, then its generated samples cannot critically depend on any
individual training sample, therefore preventing the model from replicating
any training image in a provable manner. Currently, the state-of-the-art in DP
image generation focuses on adaptation through fine-tuning (Ghalebikesabi et
al., 2023; Lyu et al., 2023), where a diffusion model is first trained on
public data (e.g., a licensed dataset) and then fine-tuned on a private
dataset using DP-SGD (Abadi et al., 2016). This approach, although effective
at a small scale, suffers immensely when scaling up the model and the private
dataset due to the computational cost of DP fine-tuning (Sander et al., 2023;
Mehta et al., 2022). To date, most studies on DP image generation are limited
to simple image datasets such as MNIST and CIFAR-10 (Dockhorn et al., 2022).

To address this limitation, we adopt a different approach for private image
generation through _differentially private retrieval augmentation_. Retrieval-
augmented generation (RAG; Lewis et al. (2020)) is an emerging paradigm in
generative modeling that performs generation in a semi-parametric manner. To
generate a sample, the model utilizes both its learned parameters as well as a
_retrieval dataset_ that consists of an arbitrary set of images. In effect,
the model can adapt to different domains at generation time by changing the
retrieval dataset without fine-tuning. The modularity of RAG makes it ideal
for privacy-sensitive applications, where the sensitive data can be stored in
the retrieval dataset for more fine-grained control of information leakage.

We utilize this desirable property of RAG and define a _differentially private
retrieval-augmented diffusion model_ (DP-RDM) that is capable of generating
high-quality images based on text prompts while satisfying rigorous DP
guarantees. To this end, we first demonstrate that without any privacy
protection, retrieval-augmented diffusion models are prone to copying
artifacts from samples in the retrieval dataset. Then, we propose a private
retrieval mechanism that adds calibrated noise to the retrieved samples, along
with modifications to an existing retrieval-augmented diffusion model
architecture (Blattmann et al., 2022) to accommodate this mechanism. As a
result, our DP-RDM is capable of generating high-quality samples from complex
image distributions at a moderate privacy cost of $\epsilon=10$; see Figure 1
for example. Notably, DP-RDM can potentially work with any state-of-the-art
retrieval-augmented image generation model, regardless of the number of
parameters and output resolution. To the best of our knowledge, this is the
first work to show privacy risks of using private data in the retrieval
dataset for RAG and propose a DP solution for adapting text-to-image diffusion
models to sensitive target domains. Our approach holds the potential of
democratizing the adoption of such models in privacy-sensitive applications
since it does not require any costly fine-tuning, nor does it require sharing
sensitive data with a fine-tuning party.

##### Contributions.

Our main contributions are the following.

  1. 1.

We demonstrate how retrieval-augmented diffusion models without any privacy
protection can leak sample-level information from their retrieval dataset in
the worst case.

  2. 2.

We propose a _differentially private retrieval-augmented diffusion model_ (DP-
RDM) that provably mitigates this information leakage. DP-RDM utilizes a DP
retrieval mechanism based on private $k$-NN (Zhu et al., 2020) and adapts the
existing retrieval-augmented diffusion model architecture (Blattmann et al.,
2022) to this mechanism.

  3. 3.

We evaluate our DP-RDM on three datasets—CIFAR-10, MS-COCO and Shutterstock, a
privately licensed dataset of 239M image-captions pairs—and show that it can
effectively adapt to these datasets privately with minor loss in generation
quality. On MS-COCO, our model is able to generate up to $10,000$ images at a
privacy cost of $\epsilon=10$ while achieving an FID of $10.9$ (lower is
better). In comparison, using only the public retrieval dataset yields an FID
of $14.4$ with the same model.

##  2 Background

We first present the necessary background on diffusion models, retrieval-
augmented generation and differential privacy.

###  2.1 Diffusion Models and Retrieval Augmented Generation

Diffusion models (Ho et al., 2020; Song et al., 2020) represent a leap of
research progress in generative modeling yielding photorealistic generated
images. During training, an image is corrupted with noise (_i.e._ , forward
process), and fed to a model (neural network), whose learning objective is to
predict the noise in order to perform denoising (_i.e._ , reverse process). At
generation time, the model produces an image sample from noise through
iterative denoising. Although this denoising process can be carried out in the
raw pixel space, a more effective approach is to perform it in the latent
space of a pre-trained autoencoder, giving rise to the so-called latent
diffusion models (LDMs; Rombach et al. (2022)). Another popular extension to
diffusion models is text-to-image diffusion models (Rombach et al., 2022;
Saharia et al., 2022), where the denoising process is conditioned on text
captions from paired image-text datasets. In effect, the model learns to
produce images that are relevant to a given text prompt.

Retrieval augmented generation (RAG). While text-to-image generative models
have achieved remarkable results, one major drawback is their limited
generation controllability. _Retrieval augmentation_ (Sheynin et al., 2022;
Chen et al., 2022; Blattmann et al., 2022; Yasunaga et al., 2022) is an
emerging paradigm that provides more fine-grained control through the use of a
retrieval dataset. In _retrieval augmented generation_ (RAG), the model is
trained to condition on both the text prompt and samples retrieved from the
retrieval dataset, making it possible to steer generation by modifying the
retrieved samples. Aside from controllable generation, RAG has additional
benefits: 1. By scaling up the retrieval dataset, one can surpass the typical
learning capacity limits of parametric models and obtain higher-quality
samples without increase the model size (Blattmann et al., 2022). 2. By using
retrieval datasets from different image domains, the model can adapt to a new
target domain without fine-tuning (Sheynin et al., 2022; Casanova et al.,
2021). 3. It is easy to satisfy security and privacy requirements such as
information flow control (Tiwari et al., 2023; Wutschitz et al., 2023) and
right-to-be-forgotten (Ginart et al., 2019; Guo et al., 2019; Bourtoule et
al., 2021) for samples in the retrieval dataset.

###  2.2 Differential Privacy

Throughout we will consider randomized mechanisms operating on a dataset $D$
in some data space $\mathcal{X}$. Two datasets $D$ and $D^{\prime}$ are said
to be neighboring, denoted $D\simeq D^{\prime}$, if they differ in a single
data point either in addition, removal or replacement of some $x\in D$.

######  Definition 2.1 (DP; Dwork et al. (2006)).

Let $\epsilon\geq 0$ and $\delta\geq 0$. A randomized mechanism
$M:\mathcal{X}\rightarrow\mathcal{O}$, is $(\epsilon,\delta)$-DP if for every
pair of neighboring datasets $D\simeq D^{\prime}$ and every subset
$S\subseteq\mathcal{O}$, we have:

$\displaystyle\Pr[M(D)\in S]\leq e^{\epsilon}\Pr[M(D^{\prime})\in
S]+\delta\enspace.$

The privacy guarantee we offer relies on Rényi DP, a generalization of DP
measured in terms of the Rényi divergence.

######  Definition 2.2 (Rényi divergence; Rényi (1961)).

Let $\alpha>1$. The Rényi divergence of order $\alpha$ between two probability
distributions $P$ and $Q$ on $\mathcal{X}$ is defined by:

$\mathbb{D}_{\alpha}(P||Q)\triangleq\frac{1}{\alpha-1}\log\mathbb{E}_{o\sim
Q}\left[\frac{P(o)}{Q(o)}\right]^{\alpha}.$

######  Definition 2.3 (Rényi DP; Mironov (2017)).

Let $\alpha>1$ and $\epsilon\geq 0$. A randomized mechanism $M$ is
$(\alpha,\epsilon)$-RDP if for all $D\simeq D^{\prime}$, we have
$\mathbb{D}_{\alpha}(M(D)\|M(D^{\prime}))\leq\epsilon$.

A Rényi DP guarantee can be translated to an $(\epsilon,\delta)$-DP guarantee
through conversion (Balle et al., 2020). Rényi DP also benefits from
simplified privacy composition, whereby the privacy budget for multiple
invocations can be added together. Finally, Rényi DP inherits the post-
processing property of DP, meaning that future computation over a private
result cannot be made less private (Mironov, 2017).

##### DP mechanisms.

In this work, we mainly consider the Sampled Gaussian Mechanism (SGM) which is
an extension of the Gaussian Mechanism.

######  Definition 2.4 (Gaussian Mechanism).

Let $f:\mathcal{X}\to\mathbb{R}^{d}$ be a query with global sensitivity
$\Delta=\sup_{D\simeq D^{\prime}}\|f(D)-f(D^{\prime})\|_{2}$ and
$Z\sim\mathcal{N}(0,\sigma^{2}I)$. The Gaussian Mechanism, defined as
$M(D)=f(D)+Z$, satisfies $(\alpha,\epsilon)$-RDP with
$\epsilon=\frac{\alpha\Delta^{2}}{2\sigma^{2}}$ for every $\alpha>1$ (Mironov,
2017).

Given a large dataset, it is also possible to amplify the privacy guarantee by
outputting a noisy answer on a subset of the dataset using SGM.

######  Definition 2.5 (SGM; Mironov et al. (2019)).

Let $f:\mathcal{X}\to\mathbb{R}^{d}$ be a function operating on subsets of
$D$. The Sampled Gaussian Mechanism (SGM), with sampling rate $q\in(0,1]$ and
noise $\sigma>0$ is defined by:

$\text{SG}_{q,\sigma}(D)\triangleq f(\\{\mathbf{x}:\mathbf{x}\in D\text{,
sampled w.p. }q\\})+Z\enspace,$

where each $\mathbf{x}$ is sampled independently with probability $q$ without
replacement and $Z\sim\mathcal{N}(0,\sigma^{2}I)$.

######  Theorem 2.6 (SGM satisfies RDP; Mironov et al. (2019)).

Let $\text{SG}_{q,\sigma}(D)$ be defined as Definition 2.5 for function $f$.
Then $\text{SG}_{q,\sigma}(D)$ satisfies $(\alpha,\epsilon)$-RDP with

$\epsilon\leq\mathbb{D}_{\alpha}((1-q)\mathcal{N}(0,\sigma^{2})+q\mathcal{N}(1,\sigma^{2})\|\mathcal{N}(0,\sigma^{2})),\enspace$

if $\|f(D)-f(D^{\prime})\|_{2}\leq 1$ for adjacent $D,D^{\prime}\in\cal{S}$.

##### DP training/fine-tuning.

To apply differential privacy to machine learning, the quintessential
algorithm is DP-SGD (Abadi et al., 2016)—a differentially private version of
the SGD algorithm. At each iteration, instead of computing the average
gradient on a batch of training samples, DP-SGD applies SGM to the sum of
norm-clipped per-sample gradients. The resulting noisy gradient can be used
directly in optimization, and the total privacy cost can be derived through
composition and post-processing. Although DP-SGD appears straightforward at
first, successful application of DP-SGD usually requires excessively large
batch sizes to reduce the effect of noisy gradients (Li et al., 2021; De et
al., 2022; Sander et al., 2023; Yu et al., 2023). This requirement drastically
increases the computational cost of training, limiting the application of DP-
SGD mostly to simple datasets and small models, or for fine-tuning a model
pre-trained on public data (Cattan et al., 2022; Yu et al., 2021). In the
context of DP generative modeling, DP-SGD has only been successfully applied
to DP fine-tuning on simple datasets such as MNIST, CIFAR-10 and CelebA
(Ghalebikesabi et al., 2023; Lyu et al., 2023). By contrast, our method
achieves differential privacy on retrieval-augmented diffusion without DP
fine-tuning.

##  3 Differentially Private RDM

(a) RDM architecture.

(b) Samples generated by RDM using an adversarial retrieval dataset.

Figure 2: (a) RDM architecture from Blattmann et al. (2022). (b) Samples
generated with a non-private RDM. The retrieval dataset consists of blank
images and one illustration of the Eiffel Tower with a Shutterstock watermark.
Each row shows samples for a different number of retrieved neighbors $k$. The
watermark is clearly visible even though it came only from conditioning on the
retrieval dataset.

This section exemplifies the privacy risks in RDM, presents our
_differentially private retrieval-augmented diffusion model_ (DP-RDM)
framework, details its technical implementation and introduces privacy
guarantees.

###  3.1 Motivation: Privacy Risks in Retrieval Augmented Generation

To motivate our DP-RDM framework, we first show that RDM (Blattmann et al.,
2022), like standard text-to-image diffusion models, are also vulnerable to
sample memorization. The RDM architecture is illustrated in Figure 2(a). To
generate an image sample, RDM encodes a text prompt using the CLIP text
encoder (Radford et al., 2021) and retrieves $k$ nearest neighbors from the
retrieval dataset, which contains CLIP-embedded images. The retrieved
neighbors are then used as conditioning vectors in lieu of the text prompt for
the diffusion model.

We consider information stored in the retrieval dataset to be private. To
illustrate the memorization risk in RDMs, we craft an adversarial retrieval
dataset that consists of an image of the Eiffel Tower with a Shutterstock
watermark (see Figure 2(b)) and a number of blank images. We vary the number
of retrieved neighbors $k$ and show image samples generated by the RDM in
Figure 2(b). Note that the watermark is visible in the generated images even
when $k=6$, which is a clear indication of sample-level information leakage.
While this experiment was constructed with worst-case assumptions, we argue
that such assumptions are reasonable when the data coverage of the retrieval
dataset is sparse, and the queries can be chosen adversarially.

###  3.2 DP-RDM Architecture

Although RDM fails to provide privacy protection in the worst case, its
architecture is already amenable to fine-grained control of information
leakage. Samples in the retrieval dataset leak information only through the
retrieval mechanism, and influence on the generated sample can be attributed
precisely to the retrieved conditioning vectors. Thus by building a “privacy
boundary” around the retrieval mechanism and bounding the influence of each
sample on the conditioning vector, we can ensure rigorous and quantifiable
privacy protection through DP (see Section 3.4).

Figure 3: Text-to-image generation with DP-RDM using a private retrieval
dataset. Yellow blocks refer to models trained on public datasets. The private
$k$-NN block, denoted in pink, illustrates the privacy boundary between public
and private data.

input :

LDM $\phi$, public retrieval dataset $U$; private retrieval dataset $D$; text
prompt $\mathbf{y}\in\mathbb{R}^{d}$; prior $\xi\sim\mathcal{N}(0,I)$

input :

Noise parameter $\sigma>0$, num. of neighbors $k\in\mathbb{N}$, query
interpolation $\lambda\in[0,1]$, subsample rate $q\in[0,1]$.

$k$-NN retrieval:

$D^{\prime}=\mathsf{RandomSubset}(D,q)$

$N_{k}=\mathsf{NearestNeighbors}(D^{\prime},\mathbf{y},k)$

$O_{k}=\mathsf{NearestNeighbors}(U,\mathbf{y},k)$

Noisy aggregation:

$\mathbf{z}=\frac{1}{k}\left(\sum_{j=1}^{k}N_{k}^{(j)}\right)+\mathcal{N}(0,\sigma^{2}I)$

Query interpolation:

$\mathbf{e}=(1-\lambda)\cdot O_{k}+\lambda\cdot[\mathbf{z}|\cdots|\mathbf{z}]$

return _$\phi(\mathbf{e},\xi)$_

Algorithm 1 Generating Samples with DP-RDM. Figure 4: Pseudo-code description
of the private image generation procedure.

Figure 4 depicts the DP-RDM workflow, whose steps are summarized in Algorithm
1. The framework is based on RDM, which retrieves image embeddings from a
database given an input text-query, and uses the retrieved embeddings to
condition the image generation process. We endow the retrieval augmentation
system with a _private $k$-NN retrieval module_, which produces a privatized
image embedding. This privatized image embedding may be interpolated with
embeddings of public images retrieved using the text-query. The resulting
interpolated embedding is used to condition the reverse diffusion process. We
detail the components of the _private $k$-NN retrieval module_ in the
following.

##### Retrieval dataset construction.

Let $D$ be a retrieval dataset constructed by encoding a private image dataset
using a pre-trained CLIP image encoder (Radford et al., 2021) trained on a
public dataset $U$. Each encoded image is a unit $d$-dimensional vector. Since
the CLIP encoder was trained on a public retrieval dataset, we assume that it
is available both at training and sampling time.

##### k-NN retrieval with random subset selection.

Given a text prompt, we first encode it into a unit $d$-dimensional vector
$\mathbf{y}$ using the CLIP text encoder. Instead of querying $D$ directly, we
obtain a subset $D^{\prime}$ by subsampling each encoded image in $D$
independently with probability $q\in[0,1]$. This is done to utilize privacy
amplification via subsampling (Mironov et al., 2019). We then query
$D^{\prime}$ using $\mathbf{y}$ via max inner product search to obtain its $k$
nearest neighbor set $N_{k}\subseteq D^{\prime}$.

##### Noisy aggregation.

The retrieved set $N_{k}$ must be privatized before use. Rather than
conditioning on these retrieved vectors individually, we aggregate them by
computing the mean as $\frac{1}{k}\sum_{j}{N_{k}^{(j)}}$. We then apply
calibrated Gaussian noise with standard deviation $\sigma>0$ to obtain the
privatized embedding vector $\mathbf{z}$.

##### Query interpolation.

Since the training dataset $U$ for the RDM is public, we can use it in
conjunction with the privatized embedding vector $\mathbf{z}$ for retrieval
augmentation. That is, we retrieve the $k$ nearest neighbors $O_{k}$ from $U$
and combine them with $\mathbf{z}$ by repeating the vector $\mathbf{z}$ $k$
times, resulting in $\mathbf{e}=(1-\lambda)\cdot
O_{k}+\lambda\cdot[\mathbf{z}|\cdots|\mathbf{z}]$.

Note that the contribution from $D$ through $\mathbf{z}$ decreases as
$\lambda$ decreases, which can help improve image quality when $\sigma$, from
the noisy aggregation step, is large. In the extreme cases when $\lambda=0$ or
$\sigma=\infty$, no private information is leaked from $D$ and we rely
entirely on $U$.

###  3.3 Model Training

Although the RDM in Blattmann et al. (2022) can be readily used with the DP-
RDM generation algorithm, we can drastically improve generation quality by
making a minor change in the training algorithm of the RDM. Rather than
conditioning on a set of retrieved embeddings from the public dataset, we can
utilize the _noisy aggregation_ module presented in Section 3.2 during
training. Hence for each training step $t$, isotropic Gaussian noise is scaled
uniform random ($\sigma_{t}\sim\mathcal{U}(0,\sigma)$) and added to the
aggregate embedding. This change helps the model to learn to extract weak
signal from the noisy conditioning vector $\mathbf{e}$ at sample generation
time, thereby improving the sample quality substantially. We also substitute
the CLIP encoder with the open-source MetaCLIP encoder (Xu et al., 2023). See
Section 6 for further details.

###  3.4 Privacy Guarantee

In the theorem below, we show that running Algorithm 1 on a single query
satisfies Rényi DP. As a result, one can leverage the composition theorem of
Rényi DP (Mironov, 2017) and conversion theorem (Balle et al., 2020) to prove
that handling $T$ queries using Algorithm 1 satisfies $(\epsilon,\delta)$-DP.

######  Theorem 3.1.

Alg. 1 satisfies $(\alpha,\epsilon)$-RDP with

$\epsilon=\mathbb{D}_{\alpha}(q\mathcal{N}(2/k,\sigma^{2})+(1-q)\mathcal{N}(0,\sigma^{2})\leavevmode\nobreak\
||\leavevmode\nobreak\ \mathcal{N}(0,\sigma^{2})).$ (1)

###### Proof.

We first prove the DP guarantee for replacement adjacency; the proof for
leave-one-out adjacency is almost identical. Let $D_{1}$ and $D_{2}$ be
neighboring datasets with $D_{1}\setminus D_{2}=\mathbf{x}_{1},D_{2}\setminus
D_{1}=\mathbf{x}_{2}$ for some $\mathbf{x}_{1},\mathbf{x}_{2}$. For any query
$\mathbf{y}$, let $D_{1}^{\prime}$ (resp. $D_{2}^{\prime}$) be the Poisson
subsampled subset of $D$ and $N_{1,k}$ (resp. $N_{2,k})$ be the k-NN set from
Algorithm 1.

Assume that the sampling of $D_{1}^{\prime}$ and $D_{2}^{\prime}$ share the
same randomness. Then, with probability $1-q$ we have that
$\mathbf{x}_{1}\notin D_{1}^{\prime}$ and $\mathbf{x}_{2}\notin
D_{2}^{\prime}$, hence $N_{1,k}=N_{2,k}$ and the distribution of $\mathbf{z}$
is identical under both $D_{1}$ and $D_{2}$. With probability $q$ we have
$\mathbf{x}_{1}\in D_{1}^{\prime}$ and $\mathbf{x}_{2}\in D_{2}^{\prime}$. In
this case, if $\mathbf{x}_{1}\notin N_{1,k}$ and $\mathbf{x}_{2}\notin
N_{2,k}$ then $N_{1,k}=N_{2,k}$ and again the distribution of $\mathbf{z}$ is
identical under both $D_{1}$ and $D_{2}$. Otherwise, without loss of
generality assume that $\mathbf{x}_{1}\in D_{1}^{\prime}$. Since
$\|\mathbf{x}\|_{2}=1$ for all $\mathbf{x}\in D_{1},D_{2}$, we have that:

$\left\|\frac{1}{k}\left(\sum_{j=1}^{k}N_{1,k}^{(j)}\right)-\frac{1}{k}\left(\sum_{j=1}^{k}N_{2,k}^{(j)}\right)\right\|_{2}=\frac{1}{k}\|\mathbf{x}_{1}-\mathbf{x}\|_{2}\leq\frac{2}{k}\enspace,$

for some $\mathbf{x}\in D_{2}$. Thus Alg. 1 is a subsampled Gaussian mechanism
with $L_{2}$ sensitivity of $2/k$. Eq. 1 holds by Theorems 4 and 5 of Mironov
et al. (2019). ∎

The statement of Theorem 3.1 gives the RDP parameter $\epsilon$ in terms of
the Rényi divergence between a Gaussian and a mixture of Gaussians. In
practice, this divergence can be computed numerically using popular packages
such as Opacus Yousefpour et al. (2021) and TensorFlow Privacy.

##### Privacy-utility analysis.

The privacy-utility trade-off of Alg. 1 depends on three factors: 1. the
number of neighbors $k$, 2. the Gaussian noise magnitude $\sigma$, 3. and the
quality of retrieved embeddings $N_{k}$. Ideally, $k$ is large and all $k$
retrieved embeddings are relevant to the text query $\mathbf{y}$. This ensures
that the privacy loss is low according to Theorem 3.1 and the generated image
is faithful to the text query.

Figure 5:  Privacy loss $\epsilon$ for generating $1,000$ images of certain
concepts with concept density $r$ in log-log scale. For concepts with high
concept density, it is possible to generate a large number of high-quality
images under low privacy cost.

To analyze this trade-off more concretely, for a given text query
$\mathbf{y}$, we introduce the quantity $r\in[0,1]$ that represents the
density of the concept encoded by $\mathbf{y}$ in the private retrieval
dataset $D$. For example, the query “an image of the Eiffel Tower” likely has
higher density than the query “an image of the Eiffel Tower from 1929”.
Suppose $n\triangleq|D|$ and there are at least $rn$ samples in $D$ that are
relevant to the query. Under a subsampling rate of $q$, for all $k$ neighbors
to be relevant, we must have $k\leq rqn$. For a fixed $\sigma$ and number of
queries $T$, we can then minimize Eq. 1 over $k,q$ subject to this constraint
to determine the minimum $\epsilon$ for answering $T$ queries faithfully.
Intuitively, when $n$ increases, the space of $k,q$ becomes larger and it
becomes possible to attain a lower $\epsilon$.

We simulate this trade-off curve for a retrieval dataset of size $n=$ 1M, 10M,
100M under a fixed $\sigma=0.1$. Figure 5 shows the privacy loss $\epsilon$
for generating $1,000$ images of a certain concept with density $r$. As
density increases, $\epsilon$ drastically decreases as expected. At the same
time, increasing the retrieval dataset size from 1M to 100M can reduce the
privacy loss by as much as three orders of magnitude for rare concepts.
Notably, for a common concept with density $r=10^{-3}$, $\epsilon$ can be as
low as $0.21$ when $n=$ 100M. This analysis shows that the privacy-utility
trade-off when generating images of common concepts using DP-RDM can be
desirable, especially when scaling up the retrieval dataset.

##  4 Results

To demonstrate the efficacy of our DP-RDM algorithm, we evaluate its text-to-
image generation performance on several large-scale image datasets.

###  4.1 Experiment Design

####  4.1.1 Datasets

##### Evaluation datasets.

We evaluate on three image datasets: CIFAR-10 (Krizhevsky and Hinton, 2009),
MS-COCO 2014 (Lin et al., 2014) with face-blurring (Yang et al., 2022), and
Shutterstock, a privately licensed dataset of 239M image-caption pairs. Both
MS-COCO and Shutterstock contain pairs of images and corresponding text
descriptions, and we evaluate by sampling validation image-text pairs and
using the text description to perform text-to-image generation. For CIFAR-10,
we perform class-conditional image generation using the text prompt [label],
high quality photograph where [label] is replaced by one of the CIFAR-10
classes.

##### Retrieval dataset.

We consider ImageNet (with face-blurring), MS-COCO (with face-blurring), and
Shutterstock as retrieval datasets. We treat ImageNet as a public dataset both
for training the RDM as well as for retrieval at generation time, while MS-
COCO and Shutterstock serve as private retrieval datasets. Going forward, all
references to MS-COCO refer to the 2014 version with face blurring.
Consequently, when the query interpolation parameter $\lambda=0$, we leverage
only public retrieval from ImageNet.

####  4.1.2 Models and Baselines

We follow the training algorithm detailed in Blattmann et al. (2022) (with
minor changes) to obtain two 400M parameter RDMs: RDM-fb and RDM-adapt. For
RDM-fb, we use the face-blurred ImageNet dataset and MetaCLIP instead of CLIP.
Note that MetaCLIP is also trained with face-blurring (Xu et al., 2023). For
RDM-adapt, we further introduce noise in the retrieval mechanism during
training as described in Section 3.3, which improves the retrieval mechanism’s
robustness to added DP noise at generation time.

The model checkpoints above can be used in two different manners: with public
retrieval (PR; _c.f._ Figure 2(a)) or DP retrieval with private $k$-NN (DPR;
_c.f._ Figure 4). Applying the two retrieval methods to different retrieval
datasets yields several methods/baselines:

  1. 1.

Public-only = (RDM-fb PR or RDM-adapt PR) + public retrieval dataset. This is
a baseline that only utilizes the public retrieval dataset (_i.e._ ImageNet),
which our DP-RDM method should consistently outperform.

  2. 2.

Non-private = (RDM-fb PR or RDM-adapt PR) + private retrieval dataset. This
baseline uses public retrieval on a private dataset and is thus non-private.
The performance of this baseline serves as a reference point that upper bounds
the performance of DP retrieval methods.

  3. 3.

DP-RDM = (RDM-fb DPR or RDM-adapt DPR) + private retrieval dataset. This is
our method applied to the two RDM models.

When using a private retrieval dataset at sample generation time, the models
are evaluated using the method described in Algorithm 1. For our experiments,
we fix $\epsilon$, the query budget, $T$, and evaluate a range of neighbors
$k$, subsample rate $q$ and private noise $\sigma$. For experiments with RDM-
adapt DPR, we fix $\sigma$ and do binary search to find $k$ (for fixed $q$) or
$q$ (for fixed $k$). For each method, we generate 15k samples, one for each
prompt from a hold-out set.

####  4.1.3 Evaluation Metrics

We measure quality, diversity and prompt-generation consistency for generated
images using the Fréchet inception distance (FID) score (Heusel et al., 2017),
CLIPScore (Hessel et al., 2021), density and coverage (Naeem et al., 2020).
The FID score measures the Fréchet distance between two image distributions by
passing each image through an Inception V3 network (Szegedy et al., 2015). A
lower FID score is better. The CLIPScore quantifies how close the generated
samples are to the query prompt where higher is better. Density and coverage
are proxies for image quality and diversity (Naeem et al., 2020). Both of
these metrics require fixing a neighborhood of $K$ samples and measuring the
nearest-neighbor distance between samples, where $\text{NND}_{K}$ computes the
distance between sample $R_{i}$ and the $K^{\text{th}}$ nearest neighbor. Let
$B(w,u)$ be the ball in $\mathbb{R}^{d}$ around point $w$ with radius $u$.
Given real samples $R$ and fake samples $F$, then density for fixed $K$, is
defined as,

$\text{density}\triangleq\frac{1}{KF}\sum_{j=1}^{F}\sum_{i=1}^{R}\mathbf{1}_{F_{j}\in
B(R_{i},\text{NND}_{K}(R_{i}))}\enspace.$

Note that it is possible for $\text{density}>1$. Coverage measures the
existence of a generated sample near a real sample and is bounded between 0
and 1. Coverage is defined as,

$\text{coverage}\triangleq\frac{1}{R}\sum_{i=1}^{R}\mathbf{1}_{\exists\
j\text{ s.t. }F_{j}\in B(R_{i},\text{NND}_{K}(R_{i}))}\enspace.$

We fix $K=5$ when computing coverage and density in our experiments.

###  4.2 Quantitative Results

Figure 6: FID score for images generated by DP-RDM under a privacy budget of
$\epsilon=10$. With both MS-COCO and Shutterstock retrieval datasets we
observe a privacy gain for a wide range of number of private queries.

##### FID score.

We first demonstrate the performance of DP-RDM quantitatively in terms of the
Fréchet inception distance (FID) score. Figure 6 shows the FID score for DP-
RDM on MS-COCO and Shutterstock when answering $T$ queries privately for $T$
ranging from 1 to 10k. The evaluation dataset and the private retrieval
dataset are the same, _i.e._ for Figure 6(a) we treat the MS-COCO validation
set as the evaluation dataset and MS-COCO training set as the private
retrieval dataset. We highlight two notable observations.

  * •

_DP-RDM achieves a desirable trade-off between model utility and privacy._ The
public-only (red line) and non-private (dotted blue line) baselines define the
region of interest for the FID score of DP-RDM. Any region below the non-
private line is unattainable, and any region above the public-only line
provides no privacy-utility benefit compared to using only the public data.
For most settings of the interpolation parameter $\lambda$ and number of
queries $T$, the FID score of DP-RDM sits comfortably within this region and
is closer to the non-private baseline. At a high level, Figure 6 suggests that
at $\epsilon=10$, DP-RDM can obtain a desirable privacy-utility trade-off even
for as many as 10k queries.

  * •

_Query interpolation helps improve model utility when answering a large number
of queries._ Query interpolation with $\lambda=1$ uses only the retrieved
aggregated embedding from the private retrieval dataset, which is injected
with Gaussian noise to ensure differential privacy. As a result, FID suffers
when answering a large number of queries. In comparison, by interpolating with
the public retrieval dataset (_i.e._ , $\lambda=0.5,0.8$), we see that DP-RDM
retains a low FID even when answering as many as 10k queries.

  * •

_Increasing the size of the retrieval dataset greatly improves model utility._
The analysis in Figure 5 suggests that scaling up the retrieval dataset is
crucial for maintaining a good privacy-utility trade-off. Our result validates
this hypothesis concretely: FID score for Shutterstock stays flat when ranging
$T$ from 1 to 10k, whereas FID score for MS-COCO increases sharply when $T=$
10k for $\lambda=0.8,1$. Our DP-RDM architecture is amenable to the use of a
large private retrieval dataset such as Shutterstock, whereas using such
internet-scale high-fidelity datasets for DP training/finetuning of state-of-
the-art generative models is out of reach at the moment.

See Section 7.2 for similar results with CIFAR-10, and Section 10 for detailed
results with $\epsilon=\\{5,10,20\\}$.

(a) CLIPScore

(b) Density

(c) Coverage

Figure 7: Quantitative evaluation of DP-RDM on MS-COCO using other metrics.
CLIPScore measures the degree of semantic alignment between the text prompt
and the generated images, whereas density and coverage reflect the
distribution-level similarity between images generated from validation prompts
and ground-truth validation images. $\epsilon=\infty$ denotes the non-private
baseline.

##### Other metrics.

In Figure 7 we plot the other quantitative metrics, namely CLIPScore, density
and coverage, as a function of the number of queries for different values of
$\epsilon$ on MS-COCO. See Figure 14 in Section 7.1 for corresponding plots
for Shutterstock. CLIPScore reflects the degree of semantic alignment between
the text prompt and the generated image, whereas density and coverage reflect
the distribution-level similarity between images generated from validation
prompts and ground-truth validation images. As expected, all three metrics
decrease as the number of queries increases. For the coverage metric, the gap
between DP-RDM and the non-private baseline is particularly large, which
suggests that DP-RDM may be suffering from mode-dropping.

###  4.3 Qualitative Results

In this section, we showcase prompts and privately generated image samples
using _RDM-adapt_ with DP retrieval. We sample 15k validation prompts from
Shutterstock and MS-COCO and use RDM-adapt DPR with $\epsilon=10,T=100$ to
generate corresponding images, and then select the top 12 for each dataset
according to CLIPScore. Figure 8 shows the selected prompts and Figure 9 shows
the generated images. Intriguing, DP-RDM is able to generate images of
concepts that are unknown to _RDM-adapt_ at training time by utilizing the
private retrieval dataset. For example, the prompt “abstract light background”
(prompt 9 for Shutterstock) generates a surprisingly coherent image that is
unlikely to appear in the ImageNet dataset. These results suggest that DP-RDM
can successfully adapt to a new private image dataset under a strong DP
guarantee. In Section 8.2 we also show prompts and generated images that
scored the lowest in CLIPScore as failure cases.

Ref |  Validation Prompt
---|---
1 |  image of blue sky with white cloud for background usage.
2 |  wood texture paint yellow
3 |  School of Jackfish in Sipadan Malaysia
4 |  A bunch of garlic isolated on white background
5 |  Halloween pumpkins on wooden table on dark color background
6 |  cauliflower
7 |  Closeup of golden art sculpture pagoda and golden tiered umbrella in temple against with blue sky in north of Thailand. Faith and religion concept.
8 |  White stork hunting in a meadow
9 |  abstract light background
10 |  White grunge wood close-up background. Painted old wooden wall.
11 |  Multicolored abstract background holidays lights in motion blur image. illustration digital.
12 |  Torn blue jean fabric texture.
(a) Shutterstock.

Ref |  Validation Prompt
---|---
1 |  A dog watching a television that is displaying a picture of a dog.
2 |  The Asian girls are sharing conversation under a parasol.
3 |  An aerial view of several jumbled cars on a narrow road.
4 |  a short passenger train on a track by a grassy hill
5 |  A kitchen scene with focus on the microwave and oven.
6 |  An empty wooden bench near a large body of water.
7 |  A brown bear on two legs is near the water.
8 |  An adult and a baby elephant crossing a road.
9 |  A man rides a motorcycle on a track.
10 |  A bear that is in the grass in the wild.
11 |  A black-and-white photo of a large bench on the sidewalk.
12 |  A view of a sink and toilet in a bathroom in the dark.
(b) MS-COCO.

Figure 8: Text prompts for generated samples with high CLIPScore for RDM-adapt
DPR.

(a) Shutterstock, ($k=17,\lambda=0.8,q=0.001$).

(b) MS-COCO, ($k=19,\lambda=0.8,q=0.01$).

Figure 9: Images generated using RDM-adapt DPR with privacy budget
$\epsilon=10$ under 100 queries.

###  4.4 Ablations

##### Effect of adapted RDM training.

In Section 3.3 we detailed changes we made to the RDM training pipeline to
better adapt it to our DP-RDM algorithm. The most critical change is the
addition of Gaussian noise in the aggregated embeddings during training, which
helps the RDM to learn to extract weak signals from noisy embeddings. Figure
10(a) shows the FID score on MS-COCO when using the non-adapted RDM-fb model
in DP-RDM. It is evident that without adaptation, the model is unable to
generate coherent images when the number of queries $T$ increases.

##### Effect of the parameter $k$.

The number of retrieved neighbors $k$ plays a critical role in controlling the
privacy-utility trade-off for DP-RDM. When $k$ is large, the privacy cost
$\epsilon$ decreases at the expense of aggregating embeddings retrieved from
irrelevant neighbors. In Figure 10(b) and Figure 10(c), we plot the histogram
of computed $L_{2}$ norms on a fixed sample of MS-COCO validation prompts.
Intuitively, a high $L_{2}$ norm indicates strong semantic coherence between
the retrieved neighbors, hence the generated image is more likely to be
faithful to the text prompt. Compared to MS-COCO retrieval in Figure 10(b),
Shutterstock is less susceptible to the negative effect of aggregating across
a large number of neighbors, despite the validation prompts coming from MS-
COCO validation. We suspect that this is primarily due to the size of
Shutterstock being $\approx 2,900$ times larger than the MS-COCO retrieval
dataset, and partially explains the strong performance of Shutterstock in
Figure 6.

(a) MS-COCO (RDM-fb DPR)

(b) MS-COCO $L_{2}$ norm

(c) Shutterstock $L_{2}$ norm

Figure 10:  Ablation studies. (a) FID score vs. number of queries when using
DP-RDM with the RDM-fb model. Without adapting the RDM to noise in the
retrieved embeddings at training time, the model is uncompetitive compared to
the public-only baseline. (b,c) Histogram of the $L_{2}$ norm of aggregated
embeddings across different validation prompts. As $k$ increases, more
irrelevant neighbors are included in the aggregated embedding, which reduces
the retrieved embedding’s $L_{2}$ norm.

##  5 Conclusion

We showcased DP-RDM, the first differentially private retrieval-augmented
architecture for text-to-image generation. DP-RDM enables adaptation of a
diffusion model trained on public data to a private domain without costly
fine-tuning. By scaling up the retrieval dataset, DP-RDM can generate a large
number of high-quality images (as many as 10k) under a fixed privacy budget,
thereby advancing the state-of-the-art in DP image generation.

##### Limitations.

While our method achieves competitive results for DP image generation, there
are some clear limitations and opportunities for future work.

  1. 1.

The current privacy analysis is based on worst-case assumptions on the query
and retrieval dataset. Variants of DP such as individual-level DP (Feldman and
Zrnic, 2021) offer more flexible privacy accounting on a sample-level basis,
which is beneficial to DP-RDM as it can assign a different privacy budget for
each sample and expend it based on the query (Zhu et al., 2023).

  2. 2.

RAG can easily satisfy requirements such as the right-to-be-forgotten for
samples in its retrieval dataset. DP-RDM can leverage this property to
guarantee both privacy and right-to-be-forgotten at the same time, although
further care is needed to ensure that it interfaces well with formal data
deletion definitions such as $(\epsilon,\delta)$-unlearning (Ginart et al.,
2019; Guo et al., 2019).

  3. 3.

Our paper focuses on private RAG for images. Can a similar technique be
successfully applied to retrieval-augmented language models (Lewis et al.,
2020)?

## References

  * Abadi et al. (2016) 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.
  * Balle et al. (2020) Borja Balle, Gilles Barthe, Marco Gaboardi, Justin Hsu, and Tetsuya Sato.  Hypothesis testing interpretations and renyi differential privacy.  In _International Conference on Artificial Intelligence and Statistics_ , pages 2496–2506. PMLR, 2020.
  * Blattmann et al. (2022) Andreas Blattmann, Robin Rombach, Kaan Oktay, Jonas Müller, and Björn Ommer.  Retrieval-augmented diffusion models.  _Advances in Neural Information Processing Systems_ , 35:15309–15324, 2022.
  * Bourtoule et al. (2021) 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.
  * Carlini et al. (2023) Nicolas Carlini, Jamie Hayes, Milad Nasr, Matthew Jagielski, Vikash Sehwag, Florian Tramer, Borja Balle, Daphne Ippolito, and Eric Wallace.  Extracting training data from diffusion models.  In _32nd USENIX Security Symposium (USENIX Security 23)_ , pages 5253–5270, 2023.
  * Casanova et al. (2021) Arantxa Casanova, Marlene Careil, Jakob Verbeek, Michal Drozdzal, and Adriana Romero.  Instance-conditioned GAN.  In A. Beygelzimer, Y. Dauphin, P. Liang, and J. Wortman Vaughan, editors, _Advances in Neural Information Processing Systems_ , 2021.
  * Cattan et al. (2022) Yannis Cattan, Christopher A Choquette-Choo, Nicolas Papernot, and Abhradeep Thakurta.  Fine-tuning with differential privacy necessitates an additional hyperparameter search.  _arXiv preprint arXiv:2210.02156_ , 2022.
  * Chen et al. (2022) Wenhu Chen, Hexiang Hu, Chitwan Saharia, and William W Cohen.  Re-imagen: Retrieval-augmented text-to-image generator.  _arXiv preprint arXiv:2209.14491_ , 2022.
  * Chrabaszcz et al. (2017) Patryk Chrabaszcz, Ilya Loshchilov, and Frank Hutter.  A downsampled variant of imagenet as an alternative to the cifar datasets.  _arXiv preprint arXiv:1707.08819_ , 2017.
  * De et al. (2022) Soham De, Leonard Berrada, Jamie Hayes, Samuel L Smith, and Borja Balle.  Unlocking high-accuracy differentially private image classification through scale.  _arXiv preprint arXiv:2204.13650_ , 2022.
  * Dockhorn et al. (2022) Tim Dockhorn, Tianshi Cao, Arash Vahdat, and Karsten Kreis.  Differentially private diffusion models.  _arXiv preprint arXiv:2210.09929_ , 2022.
  * Dwork et al. (2006) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith.  Calibrating noise to sensitivity in private data analysis.  In _Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY, USA, March 4-7, 2006. Proceedings 3_ , pages 265–284. Springer, 2006.
  * Feldman and Zrnic (2021) Vitaly Feldman and Tijana Zrnic.  Individual privacy accounting via a renyi filter.  _Advances in Neural Information Processing Systems_ , 34:28080–28091, 2021.
  * Ghalebikesabi et al. (2023) Sahra Ghalebikesabi, Leonard Berrada, Sven Gowal, Ira Ktena, Robert Stanforth, Jamie Hayes, Soham De, Samuel L Smith, Olivia Wiles, and Borja Balle.  Differentially private diffusion models generate useful synthetic images.  _arXiv preprint arXiv:2302.13861_ , 2023.
  * Ginart et al. (2019) 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.
  * Guo et al. (2019) Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten.  Certified data removal from machine learning models.  _arXiv preprint arXiv:1911.03030_ , 2019.
  * Harder et al. (2023) Frederik Harder, Milad Jalali, Danica J Sutherland, and Mijung Park.  Pre-trained perceptual features improve differentially private image generation.  _Transactions on Machine Learning Research_ , 2023.
  * Hessel et al. (2021) Jack Hessel, Ari Holtzman, Maxwell Forbes, Ronan Le Bras, and Yejin Choi.  Clipscore: A reference-free evaluation metric for image captioning.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 7514–7528, 2021.
  * Heusel et al. (2017) Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  _Advances in neural information processing systems_ , 30, 2017.
  * Ho et al. (2020) Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Advances in neural information processing systems_ , 33:6840–6851, 2020.
  * Jegou et al. (2010) Herve Jegou, Matthijs Douze, and Cordelia Schmid.  Product quantization for nearest neighbor search.  _IEEE transactions on pattern analysis and machine intelligence_ , 33(1):117–128, 2010.
  * Johnson et al. (2019) Jeff Johnson, Matthijs Douze, and Hervé Jégou.  Billion-scale similarity search with GPUs.  _IEEE Transactions on Big Data_ , 7(3):535–547, 2019.
  * Krizhevsky and Hinton (2009) Alex Krizhevsky and Geoffrey Hinton.  Learning multiple layers of features from tiny images.  Technical report, University of Toronto, Toronto, Ontario, 2009.
  * Krizhevsky et al. (2012) Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton.  Imagenet classification with deep convolutional neural networks.  _Advances in neural information processing systems_ , 25, 2012.
  * Lewis et al. (2020) Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, et al.  Retrieval-augmented generation for knowledge-intensive nlp tasks.  _Advances in Neural Information Processing Systems_ , 33:9459–9474, 2020.
  * Li et al. (2021) Xuechen Li, Florian Tramer, Percy Liang, and Tatsunori Hashimoto.  Large language models can be strong differentially private learners.  _arXiv preprint arXiv:2110.05679_ , 2021.
  * Lin et al. (2014) Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence Zitnick.  Microsoft coco: Common objects in context.  In _Computer Vision–ECCV 2014: 13th European Conference, Zurich, Switzerland, September 6-12, 2014, Proceedings, Part V 13_ , pages 740–755. Springer, 2014.
  * Lyu et al. (2023) Saiyue Lyu, Margarita Vinaroz, Michael F Liu, and Mijung Park.  Differentially private latent diffusion models.  _arXiv preprint arXiv:2305.15759_ , 2023.
  * Mehta et al. (2022) Harsh Mehta, Abhradeep Thakurta, Alexey Kurakin, and Ashok Cutkosky.  Large scale transfer learning for differentially private image classification.  _arXiv preprint arXiv:2205.02973_ , 2022.
  * Mironov (2017) Ilya Mironov.  Rényi differential privacy.  In _2017 IEEE 30th computer security foundations symposium (CSF)_ , pages 263–275. IEEE, 2017.
  * Mironov et al. (2019) Ilya Mironov, Kunal Talwar, and Li Zhang.  Rényi differential privacy of the sampled gaussian mechanism.  _arXiv preprint arXiv:1908.10530_ , 2019.
  * Naeem et al. (2020) Muhammad Ferjad Naeem, Seong Joon Oh, Youngjung Uh, Yunjey Choi, and Jaejun Yoo.  Reliable fidelity and diversity metrics for generative models.  In _International Conference on Machine Learning_ , pages 7176–7185. PMLR, 2020.
  * Parmar et al. (2022) Gaurav Parmar, Richard Zhang, and Jun-Yan Zhu.  On aliased resizing and surprising subtleties in gan evaluation.  In _CVPR_ , 2022.
  * Radford et al. (2021) 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.
  * Rényi (1961) Alfréd Rényi.  On measures of entropy and information.  In _Proceedings of the Fourth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Contributions to the Theory of Statistics_ , volume 4, pages 547–562. University of California Press, 1961.
  * Rombach et al. (2022) Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _Proceedings of the IEEE/CVF conference on computer vision and pattern recognition_ , pages 10684–10695, 2022.
  * Saharia et al. (2022) Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily L Denton, Kamyar Ghasemipour, Raphael Gontijo Lopes, Burcu Karagol Ayan, Tim Salimans, et al.  Photorealistic text-to-image diffusion models with deep language understanding.  _Advances in Neural Information Processing Systems_ , 35:36479–36494, 2022.
  * Sander et al. (2023) Tom Sander, Pierre Stock, and Alexandre Sablayrolles.  Tan without a burn: Scaling laws of dp-sgd.  In _International Conference on Machine Learning_ , pages 29937–29949. PMLR, 2023.
  * Sheynin et al. (2022) Shelly Sheynin, Oron Ashual, Adam Polyak, Uriel Singer, Oran Gafni, Eliya Nachmani, and Yaniv Taigman.  Knn-diffusion: Image generation via large-scale retrieval.  _arXiv preprint arXiv:2204.02849_ , 2022.
  * Somepalli et al. (2023) Gowthami Somepalli, Vasu Singla, Micah Goldblum, Jonas Geiping, and Tom Goldstein.  Diffusion art or digital forgery? investigating data replication in diffusion models.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 6048–6058, 2023.
  * Song et al. (2020) Jiaming Song, Chenlin Meng, and Stefano Ermon.  Denoising diffusion implicit models.  _arXiv preprint arXiv:2010.02502_ , 2020.
  * Szegedy et al. (2015) Christian Szegedy, Wei Liu, Yangqing Jia, Pierre Sermanet, Scott Reed, Dragomir Anguelov, Dumitru Erhan, Vincent Vanhoucke, and Andrew Rabinovich.  Going deeper with convolutions.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 1–9, 2015.
  * Tiwari et al. (2023) Trishita Tiwari, Suchin Gururangan, Chuan Guo, Weizhe Hua, Sanjay Kariyappa, Udit Gupta, Wenjie Xiong, Kiwan Maeng, Hsien-Hsin S Lee, and G Edward Suh.  Information flow control in machine learning through modular model architecture.  _arXiv preprint arXiv:2306.03235_ , 2023.
  * Wutschitz et al. (2023) Lukas Wutschitz, Boris Köpf, Andrew Paverd, Saravan Rajmohan, Ahmed Salem, Shruti Tople, Santiago Zanella-Béguelin, Menglin Xia, and Victor Rühle.  Rethinking privacy in machine learning pipelines from an information flow control perspective.  _arXiv preprint arXiv:2311.15792_ , 2023.
  * Xu et al. (2023) Hu Xu, Saining Xie, Xiaoqing Ellen Tan, Po-Yao Huang, Russell Howes, Vasu Sharma, Shang-Wen Li, Gargi Ghosh, Luke Zettlemoyer, and Christoph Feichtenhofer.  Demystifying clip data.  _arXiv preprint arXiv:2309.16671_ , 2023.
  * Yang et al. (2022) Kaiyu Yang, Jacqueline Yau, Li Fei-Fei, Jia Deng, and Olga Russakovsky.  A study of face obfuscation in imagenet.  In _International Conference on Machine Learning (ICML)_ , 2022.
  * Yasunaga et al. (2022) Michihiro Yasunaga, Armen Aghajanyan, Weijia Shi, Rich James, Jure Leskovec, Percy Liang, Mike Lewis, Luke Zettlemoyer, and Wen-tau Yih.  Retrieval-augmented multimodal language modeling.  _arXiv preprint arXiv:2211.12561_ , 2022.
  * Yousefpour et al. (2021) 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.
  * Yu et al. (2021) Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al.  Differentially private fine-tuning of language models.  In _International Conference on Learning Representations_ , 2021.
  * Yu et al. (2023) Yaodong Yu, Maziar Sanjabi, Yi Ma, Kamalika Chaudhuri, and Chuan Guo.  Vip: A differentially private foundation model for computer vision.  _arXiv preprint arXiv:2306.08842_ , 2023.
  * Zhu et al. (2020) Yuqing Zhu, Xiang Yu, Manmohan Chandraker, and Yu-Xiang Wang.  Private-knn: Practical differential privacy for computer vision.  In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , pages 11854–11862, 2020.
  * Zhu et al. (2023) Yuqing Zhu, Xuandong Zhao, Chuan Guo, and Yu-Xiang Wang.  " private prediction strikes back!”private kernelized nearest neighbors with individual renyi filter.  _arXiv preprint arXiv:2306.07381_ , 2023.

##  6 Appendix: Training Details

In Figure 11 we detail the training procedure.

We train on a face-blurred version of ImageNet (Krizhevsky et al., 2012; Yang
et al., 2022) to enhance privacy of the pre-training dataset. While this
method is not exhaustive, and in some cases will blur non-human subjects, this
method effectively mitigates facial memorization by the trained model. Both
models (RDM-fb PR and RDM-adapt PR ) were trained using single patches,
center-cropped on ImageNet FB.

Figure 11: DP-RDM follows a typical training process for text-to-image
generative models. The training process can be done entirely with public data.

DP-RDM supports two aggregation methods. RDM-fb PR instantiates the
Concatenation module, which is the standard approach for training RDM (see
Blattmann et al. (2022) for details). Alternatively, DP-RDM can be trained
using the same Noisy Aggregation approach done during private sample
generation. Due to the bound on global sensitivity at sample generation time,
we ensure embeddings are normalized during training to match the normalization
procedure when samples are generated.

|  RDM (Blattmann et al., 2022) | RDM-fb PR | RDM-adapt PR
---|---|---|---
Steps | 120k | 110k | 140k
Batch | 1280 | 3840 | 3840
Encoder | CLIP ViT-B/32 | MetaCLIP ViT-B16 (400M)
Train Dataset | ImageNet | ImageNet Face-Blurred
Added Noise ($\sigma$) | 0 | 0.05
Aggregation | No | Yes
Figure 12: Training Setup. Experimental results were performed on models
trained with face-blurring (FB) in the CLIP encoder, the conditioning and the
training dataset.

##### Picking a Noise Magnitude for Training.

Remark that all embeddings are normalized, and therefore the aggregated
embedding will be no greater than 1. We therefore consider the highest amount
of training noise such that $\sigma\cdot\sqrt{d}\approx 1$. When training RDM-
adapt PR, $d=512$ and $\sigma=0.05$.

##### Efficient subsampling and nearest neighbor search.

For large-scale retrieval datasets with millions of samples, it is necessary
to adopt fast nearest neighbor search for computational efficiency. To this
end, we use the Faiss library (Johnson et al., 2019), which is known to
support fast inner product search for billion-scale vector databases. To
support subsampling, we use the selector array functionality
(IDSelectorBatch), which allows one to specify a binary index vector that
limits the inner product search to a subset of the full retrieval dataset. We
apply product quantization (Jegou et al., 2010) to the vector database in the
case of Shutterstock. Note that product quantization requires training as
well, which can also leak private information if done on the retrieval dataset
itself. For retrieval from CIFAR-10, ImageNet FB, MS-COCO FB and the
adversarial dataset, we use a flat index without index training. The
Shutterstock index is built using an inverted file index and product
quantization (IVFPQ) using an L2 quantizer, $8,192$ centroids, and a code size
of $256$.

##### Privacy Analysis.

In Figure 13 we show how DP-RDM is calibrated across a range of neighbors and
noise magnitudes. This mechanism can be tuned using in terms of the
subsampling rate $q$, number of neighbors $k$ and additive noise $\sigma$.

Figure 13:  DP-RDM privacy analysis for a 100M dataset, over 10k fixed queries
using privacy amplification by subsampling.

##  7 Further Experiment Details

All experiments were performed with $100$ DDIM steps. ImageNet FB,
Shutterstock and MS-COCO samples were generatured using a classifier-free
guidance scale of $2.0$. CIFAR-10 experiments were done with the guidance
scale set to $1.25$. We resize and center crop each image before encoding the
image and storing the normalized embedding. To evaluate FID, we use work by
Parmar et al. (2022).

###  7.1 Shutterstock Metrics

(a) CLIPScore

(b) Density

(c) Coverage

Figure 14: Shutterstock Density and Coverage plots over a range of privacy
parameters. The dashed line ($\epsilon=\infty$) corresponds with the non-
private baseline.

###  7.2 CIFAR-10

CIFAR-10 images are $32\times 32$ pixels. We therefore up-sample them to match
our models. We found that random subsampling of the retrieval dataset (with
$q=1/100$) significantly improved quality and diversity of the images
generated. We generate 30k samples and report their similarity against pre-
computed statistics. At privacy loss $\epsilon=10$, or no privacy
($\epsilon=\infty$), we report the best quality score for $k$ on CIFAR-10 over
30,000 generated samples. With private diffusion models, there are two notable
fine tuning results. Harder et al. (2023) reduce the dependency on private
data by using public feature extractor to train a private generator on
CIFAR-10, and report FID of $26.8$. Another fine-tuning result comes from
Ghalebikesabi et al. (2023), where they report FID of $9.8$ on CIFAR-10.
However, both of these methods train on a downsampled version of ImageNet
(Chrabaszcz et al., 2017), which limits their capacity to generate high-
quality samples.

|  |  | FID | $\sigma$ | $k$ | $\lambda$ | $q$
---|---|---|---|---|---|---|---
Model (CIFAR-10) | $T$ | $\epsilon$ |  |  |  |  |
RDM-adapt PR | 0 | $\infty$ | 15.26 | 0.05 | 4 | 1.0 | 0.01
RDM-adapt DPR | 1 | 10 | 13.91 | 0.05 | 13 | 1.0 | 0.01
10 | 10 | 14.26 | 0.05 | 16 | 1.0 | 0.01
100 | 10 | 14.34 | 0.05 | 19 | 1.0 | 0.01
1,000 | 10 | 14.52 | 0.05 | 23 | 1.0 | 0.01
10,000 | 10 | 15.19 | 0.05 | 33 | 1.0 | 0.01
Figure 15: CIFAR-10: Tabular Results Figure 16: For $\epsilon=10$, we compare
the privacy trade-off for RDM-adapt DPR and CIFAR-10 retrieval.

##  8 Appendix: More Generated Samples

Figure 17:  RDM-adapt DPR samples generated for $\epsilon=10,\delta=1/n$,
where $n=50,000$ denotes the size of the retrieval datasets (CIFAR-10 train).
Here no. neighbors, $k=23$, and the Sub-sampled Gaussian Mechanism is
calibrated for 1,000 private queries over random subsets $q=0.01$.

###  8.1 ImageNet (Face Blurred) Results

When $\lambda=0$, then privacy loss $\epsilon=0$ and the model relies only on
the public retrieval dataset.

(a) Shutterstock Validation

(b) MS-COCO Validation

Ref |  Validation Prompt
---|---
1 |  Female Ptarmigan Stood.
2 |  Yorkshire terrier with a red bow
3 |  Bowl of coffee beans , isolated on white background.
4 |  Cute Siberian Husky puppy with pink flowers
5 |  Stork stands guarding the nestlings in his nest. Beautiful Moon in the background - Banya, Bulgaria
6 |  Ancient Bon stupa in Saldang village, Nepal. Saldang lies in Nankhang Valley, the most populous of the sparsely populated valleys making up the culturally Tibetan region of Dolpo.
7 |  Turkish coffee pots made in a traditional style
8 |  Human hand holding a big snail shell
9 |  Rugby American football ball isolated on white background. This has clipping path.
10 |  abstract orange. Summer background with a magnificent sun burst with lens flare. space for your message
11 |  colored disposable knives lie on a pink and blue background
12 |  Closeup of golden art sculpture pagoda and golden tiered umbrella in temple against with blue sky in north of Thailand. Faith and religion concept.
(a) RDM-adapt DPR with Shutterstock.

Ref |  Validation Prompt
---|---
1 |  A white toilet sitting next to a toilet paper roller.
2 |  A street sign reads both in English and Asian script.
3 |  A dog inspects an open dishwasher in a kitchen.
4 |  A bathroom sink has a running facet and bamboo plant.
5 |  A bathroom with blue walls and white tiles.
6 |  A teddy bear sitting on a chair inside a room.
7 |  A computer desk with an open umbrella hooked up to wires.
8 |  A young baby girl standing in a driveway holding an open umbrella.
9 |  A bus that is sitting in the grass near a street.
10 |  A stuffed animal pushed into a toilet.
11 |  A metal bench sits on a path in the forest.
12 |  Black and white photograph of a bowl of apples.
(b) RDM-adapt DPR with MS-COCO.

###  8.2 Failure Cases

In the following figures and tables we show examples of generated samples with
the lowest CLIPScore when compared to their validation prompt.

Figure 20: Shutterstock Figure 21: MS-COCO

Ref |  Validation Prompt
---|---
1 |  Beautiful Seamless Pattern of Watercolor Summer Garden Blooming Flowers on purple background
2 |  Hello august calligraphy and set of cute and necessary things for relaxing on the beach, isolated on white background.
3 |  strawberry milk splash isolated on white background
4 |  Merry Christmas line flat design card with holidays symbols - Santa Claus, Christmas tree, house, mistletoe
5 |  Illustration of card with bowknot with round frame for text isolated on white background. Black friday sale banner template. Design for Christmas sale, shopping, retail, discount poster
6 |  Men’s classic shoes isolated on white background
(a) Failure cases with Shutterstock.

Ref |  Validation Prompt
---|---
1 |  An old plane flying through the cloudy sky.
2 |  A person sitting by the water with a bike.
3 |  A man in a neon green vest is holding a stop sign on the newly paved road.
4 |  Tire marks carve paths down a snow covered street.
5 |  An elderly man wearing a white button down shirt and a black bow tie smiling.
6 |  A number of red and green traffic lights on a wide highway.
(b) Failure cases with MS-COCO.

##  9 Appendix: RDM and DP-RDM Compared

Here we show how RDM-adapt DPR mitigates individual samples from appearing in
an adversarially chosen dataset via noisy aggregation.

(a) Adversarial $D$ with RDM

(b) Adversarial $D$ with RDM-adapt DPR

##  10 Appendix: Quantitative Results

|  | FID | CLIPScore | Coverage | Density
---|---|---|---|---|---
Model | Validation |  |  |  |
RDM-adapt PR | CIFAR-10 | 40.87 | - | - | -
MS-COCO FB | 14.40 | 0.294 | 0.85 | 1.15
Shutterstock | 24.32 | 0.269 | 0.79 | 0.95
Figure 24: Imagenet Face Blurred: Tabular Results |  |  | FID | CLIPScore | Coverage | Density | $\sigma$ | $k$ | $\lambda$ | $q$
---|---|---|---|---|---|---|---|---|---|---
MS-COCO FB | $T$ | $\epsilon$ |  |  |  |  |  |  |  |
RDM-adapt PR | 0 | $\infty$ | 10.08 | 0.267 | 0.88 | 1.4 | 0.0 | 4 | 1.0 | 1.0
RDM-adapt DPR | 1 | 5 | 11.14 | 0.26 | 0.86 | 1.13 | 0.05 | 23 | 1.0 | 0.05
10 | 11.35 | 0.273 | 0.88 | 1.25 | 0.04 | 21 | 1.0 | 0.1277
20 | 10.68 | 0.265 | 0.88 | 1.14 | 0.05 | 10 | 1.0 | 0.05
10 | 5 | 11.32 | 0.259 | 0.86 | 1.13 | 0.05 | 28 | 1.0 | 0.05
10 | 11.36 | 0.251 | 0.85 | 0.97 | 0.065 | 16 | 1.0 | 0.05
20 | 10.96 | 0.263 | 0.88 | 1.13 | 0.05 | 15 | 1.0 | 0.05
100 | 5 | 11.57 | 0.257 | 0.85 | 1.1 | 0.05 | 37 | 1.0 | 0.05
10 | 11.75 | 0.249 | 0.83 | 0.99 | 0.065 | 21 | 1.0 | 0.05
20 | 11.1 | 0.261 | 0.86 | 1.12 | 0.05 | 21 | 1.0 | 0.05
1,000 | 5 | 15.5 | 0.24 | 0.75 | 0.88 | 0.05 | 29 | 1.0 | 0.01
10 | 12.14 | 0.246 | 0.82 | 0.94 | 0.065 | 34 | 1.0 | 0.05
20 | 11.26 | 0.258 | 0.85 | 1.11 | 0.05 | 32 | 1.0 | 0.05
10,000 | 5 | 20.01 | 0.218 | 0.66 | 0.66 | 0.08 | 30 | 1.0 | 0.01
10 | 16.68 | 0.237 | 0.73 | 0.83 | 0.05 | 34 | 1.0 | 0.01
20 | 14.61 | 0.242 | 0.77 | 0.91 | 0.05 | 26 | 1.0 | 0.01
RDM-fb | 1 | 10 | 17.9 | 0.232 | 0.94 | 0.78 | 0.03 | 22 | 1.0 | 0.01
10 | 10 | 20.86 | 0.227 | 0.88 | 0.62 | 0.035 | 22 | 1.0 | 0.01
100 | 10 | 21.42 | 0.227 | 0.6 | 0.61 | 0.033 | 28 | 1.0 | 0.01
1,000 | 10 | 27.07 | 0.22 | 0.49 | 0.4 | 0.041 | 28 | 1.0 | 0.01
10,000 | 10 | 42.01 | 0.207 | 0.3 | 0.18 | 0.059 | 28 | 1.0 | 0.01
100,000 | 10 | 155.67 | 0.192 | 0.06 | 0.02 | 0.164 | 22 | 1.0 | 0.01
Figure 25: MS-COCO Face Blurred: Tabular Results |  |  | FID | CLIPScore | Coverage | Density | $\sigma$ | $k$ | $\lambda$ | $q$
---|---|---|---|---|---|---|---|---|---|---
Shutterstock | $T$ | $\epsilon$ |  |  |  |  |  |  |  |
RDM-adapt PR | 0 | $\infty$ | 20.09 | 0.245 | 0.77 | 0.71 | 0.05 | 4 | 1.0 | 1.0
RDM-adapt DPR | 1 | 5 | 20.77 | 0.256 | 0.8 | 0.84 | 0.08 | 16 | 0.5 | 0.01
10 | 20.73 | 0.244 | 0.77 | 0.73 | 0.065 | 14 | 0.8 | 0.01
20 | 20.95 | 0.262 | 0.8 | 0.87 | 0.06 | 10 | 0.5 | 0.01
10 | 5 | 21.19 | 0.255 | 0.8 | 0.83 | 0.08 | 17 | 0.5 | 0.01
10 | 20.93 | 0.26 | 0.8 | 0.85 | 0.065 | 16 | 0.5 | 0.01
20 | 21.05 | 0.262 | 0.8 | 0.88 | 0.06 | 12 | 0.5 | 0.01
100 | 5 | 21.28 | 0.247 | 0.78 | 0.79 | 0.06 | 24 | 0.8 | 0.01
10 | 20.99 | 0.256 | 0.8 | 0.84 | 0.08 | 14 | 0.5 | 0.01
20 | 20.86 | 0.244 | 0.78 | 0.74 | 0.065 | 13 | 0.8 | 0.01
1,000 | 5 | 21.02 | 0.247 | 0.78 | 0.75 | 0.06 | 28 | 0.8 | 0.01
10 | 20.96 | 0.26 | 0.81 | 0.88 | 0.065 | 21 | 0.5 | 0.01
20 | 21.09 | 0.244 | 0.77 | 0.74 | 0.065 | 16 | 0.8 | 0.01
10,000 | 5 | 22.06 | 0.234 | 0.76 | 0.73 | 0.08 | 36 | 0.8 | 0.01
10 | 21.27 | 0.263 | 0.81 | 0.88 | 0.05 | 38 | 0.5 | 0.01
20 | 21.44 | 0.263 | 0.81 | 0.88 | 0.05 | 29 | 0.5 | 0.01
Figure 26: Shutterstock: Tabular Results