Differentially Private Dataset Condensation
Authors: Tianhang Zheng
Baochun Li
Venue: Submitted to ICLR 2023 (2023)

Abstract: Recent work in ICML'22 builds a theoretical connection between dataset condensation (DC) and differential privacy (DP) and claims that DC can provide privacy protection for free. However, the connection is problematic because of two controversial assumptions. In this paper, we revisit the ICML'22 work and elucidate the issues in the two controversial assumptions. To correctly connect DC and DP, we propose two differentially private dataset condensation (DPDC) algorithms---LDPDC and NDPDC. Through extensive evaluations on multiple datasets, we demonstrate that LDPDC has comparable performance to recent DP generative methods despite its simplicity. NDPDC provides acceptable DP guarantees with a mild utility loss, compared to the state-of-the-art DC method. Additionally, NDPDC allows a flexible trade-off between the synthetic data utility and DP budget.

Under review as a conference paper at ICLR 2023
DIFFERENTIALLY PRIVATE DATASET CONDENSATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Recent work in ICML'22 builds theoretical connection between dataset conden- sation (DC) and differential privacy (DP) and claims that DC can provide privacy protection for free. However, the connection is problematic because of two con- troversial assumptions. In this paper, revisit the ICML'22 work and elucidate the issues in the two controversial assumptions. To correctly connect DC and DP, we propose two differentially private dataset condensation (DPDC) algorithms-- LDPDC and NDPDC. Through extensive evaluations, we demonstrate that LD- PDC has comparable performance to recent DP generative methods despite its simplicity. NDPDC provides acceptable DP guarantees with a mild utility loss, compared to distribution matching (DM). Additionally, NDPDC allows flexible trade-off between the synthetic data utility and DP budget.
INTRODUCTION
Although deep learning has pushed forward the frontiers of many applications in the past decade, it still needs to overcome some challenges for broader academic and commercial use (Dilmegani 2022). One challenge is the costly process of algorithm design and practical implementation in deep learning, which typically requires inspection and evaluation by training many models ample data. The growing privacy concern is another challenge. Due to the privacy concern, an increasing number of customers are reluctant provide their data for the academia industry to train deep learning models, and some regulations are further created to restrict access to sensitive data.
Recently, dataset condensation (DC) has emerged as a potential technique address the two chal- lenges with one shot (Zhao et al., 2021 Zhao & Bilen] 2021b). The main objective of dataset condensation is to condense the original dataset into a small synthetic dataset while maintaining the synthetic data utility to the greatest extent for training deep learning models. For the first chal- lenge, both academia and industry can save computation and storage costs if using DC-generated small synthetic datasets to develop their algorithms and debug their implementations. In terms of the second challenge, since the DC-generated synthetic data may not exist the real world, sharing DC-generated data seems less risky than sharing the original data.
Nevertheless, DC-generated data may memorize a fair amount of sensitive information during the optimization process on the original data. In other words, sharing DC-generated data still exposes the data owners to privacy risk. Moreover, this privacy risk is unknown since the prior literature on DC has not proved any rigorous connection between DC and privacy. Although ICML'22 outstanding paper (Dong et al. 2022) proved a proposition to support the claim that DC can provide certain differential privacy (DP) guarantee for free, the proof is problematic because of two controversial assumptions, as discussed in Section 3.1
To correctly connect DC and DP for bounding the privacy risk of DC, propose two differentially private dataset condensation (DPDC) Algorithss-LDPD3 and NDPDC. LDPDC (Algorithm I adds random noise to the sum of randomly sampled original data and then divides the randomized sum by the fixed expected sample size to construct the synthetic data. Based on the framework of Rényi Differential Privacy (RDP) (Mironov) 20177] Mironov et al. 2211)). we prove Theorem 3. bound the privacy risk of LDPDC. NDPDC (Algorithm{2 optimizes randomly initialized synthetic data by matching the norm-clipped representations of the synthetic data and the randomized norm- clipped representations of the original data. For NDPDC, we prove Theorem 3.2 bound to its privacy
We note that, in this paper, performance specifically refers to the performance in producing high-utility synthetic data for data-efficient model training.

---

Under review as a conference paper at ICLR 2023
risk. The potential benefits brought by DPDC algorithms include (i) reducing the cost of data storage and model training: (ii) mitigating the privacy concerns from data owners; (iii) providing DP guar- antees for the hyperparameter fine-tuning process and the trained models on the OPDC-generated syntheric datasets, due to the post-processing property.
We conduct extensive experiments to evaluate DPDC algorithms multiple datasets, including MNIST, FMNIST, CIFARIO, 10, and CelebA. We mainly compare our DPDC algorithms with a non- private dataset condensation method, i.e. distribution matching (Zhao Bilen 2021a), and two recent differentially private generative methods, i.e., DP-MERF and DP-Sinkhorn (Cao et al. 202T Harder et al., 2021). We demonstrate that (i) LDPDC shows comparable performance DP-MERF and DP-Sinkhorn despite its simplicity; (ii) NDPDC can provide DP protection with a mild utility loss, compared distribution matching; (iii) NDPDC allows a flexible trade-off between privacy and utility and can use low DP budgets to achieve better performance than DP-MERF and DP-Sinkhom..
2
BACKGROUND AND RELATED WORK
2.1 DATASET CONDENSATION
We denote a data sample by æ and its label by y. In this paper, we mainly study classification problems, where (-(-) refers the model with parameters 0. {(fo(x), y) refers the cross-entropy between the model output (z) and the label y. Let T and S denote the original dataset and the synthetic dataset, respectively, then we can formulate the dataset condensation problem as
arg min (fo.s)-
where ((S) = arg min ((n.))- y), [S] < [T] (I)
An intuitive method to solve the above objective is meta-lcarning (Wang et al. 2018), with an inner optimization step update and a outer optimization step update S. However, this intuitive method needs lot of cost for implicitly using second-order terms in the outer optimization step. Nguyen et al., (2020) considered the classification task as a ridge regression problem and derived an algorithm called kernel inducing points (KIP) to simplify the meta-learning process. Gradient matching is an alternative method (Zhao et al., 202I) for dataset condensation, which minimizes a matching loss between the model gradients on the original and synthetic data, i.e.,
min Eg P 00
HM (V, VOL
1l refers to the matching loss in Zhao al. 2021 VoL (0.) and VoLT (0.) refer the model
gradients on the synthetic and original data, respectively; 0g is updated on the synthetic data to ob- tain 0.+1. To boost the performance, Zhao Bilen (202Tb) further applied differentiable Siamese augmentation A.n(-) with parameters to the original data samples and the synthetic data samples. Recently, Zhao & Bilen (201a)) proposed to match the feature distributions of the original and syn- thetic data for dataset condensation. Zhao & Bilen (202 used an empirical estimate of maximum mean discrepancy (MMD) as the matching loss, i.e.,
Eg- Poll |I T
Σ 2o (Aw - S
Σ 2 (A (xx))
where 22(()) is the feature extractor, and Pe is parameter distribution. With the help of differen- tiable data augmentation (Zhao & Bilen 2021b), the distribution matching method (DM) (Zhao & Bilen 2021a) achieves the state-of-the- art performance on dataset condensation.
2.2 DIFFERENTIAL PRIVACY
Differential Privacy (DP) (Dwork et al. 2006) is the most widely-used mathematical definition of privacy, so we first introduce the definitonn of DP in the following.
Definition 2.1 (Differential Privacy (DP)) For adjacent datasets D and D', and every possi- ble output set O, if a randomized mechanism M satisfies P(M(D) E O < e' e'P(M(()) E O + 8, then M obeys OD..
Based on the framework of DP, Abadi et al. (2016) developed DP-SGD with a moments accountant for learning differentially private models.
2

---

Under review as a conference paper at ICLR 2023
We also introduce the concept of Rényi Differential Privacy (RDP), RDP gives unified view of pure DP and (e, 6D- graceful composition bounds, and tighter bounds for the (sub)sampled Gaussian mechanism (Definition A.I1 (Wang al. [2019] Mironov al. 2019). Due to the benefits of RDP, Meta's Opacus library (Yousefpour et al., 2021) also relies on (Mironov et al. 2019) for DP analysis. We begin the brief introduction of RDP with two basic definitions:
Definition 2.2 (Rényi Divergence (Rényi et al. 1961) Let P and Q be two distributions on Z over the same probability space, the Rěnyi divergence between P and Q is
p(z) ((2)
(P(l))Q)
In
g(z)(
dz,
(4)
where p(z) and (()) are the respective probability density functions of P and Q. Without ambiguity, (P(P can also be written Da (p(2))lll(()))
Definition 2.3 (Rényi Differential Privacy (RDP) (Mironov 2017 For two adjacent datasets D and D', if randomized mechanism M satisfies (((MD))]MM(())) c 1), then M obeys (a, RDDPP, where Da refers to Rényi divergence.
We can easily connect RDP and DP by Lemma 2.1 and Corollary 2.1
Lemma 2.1 (RDP to DP Conversion (Balle et al. 2020) Ifa randomized mechanism M guaran-
tees (a, r)-DD, then it also obeys (e + log([a 1)/a)
(log 6 log a)/ 1),
In Appendix A (Page 15), we show that Lemma 2.1 is tighter than Mironov (017 conversion law.
Corollary 2.1 According to Lemma 2. if mechanism M obeys (a,, ) for a > 1, then
M obeys (mina>1(<(a)) + log((aa 1)/a) (log log
o)/ (olooo)////
One main advantage of RDP is that RDP allows graceful composition of the privacy budgets spent by multiple randomized mechanisms, as illustrated in Lemma 2.2
Lemma 2.2 (RDP Composition (Mironov. 2017)) If is (a, (2) M2 is (a, R2) then their composition obeys (a, 61 + RDP.
Furthermore, RDP allows a graceful parallel composition, as shown in Lemma 2.3
Lemma 2.3 (Parallel Composition (Chaudhuri et al. 2019) Iww datasets D and D2 are dis- joint (Di O D2 = (), and MM is (R,6))-RPP, M2 (ar, (2,622)DDP, then the combined release (M1(D1). Mz(2)) obeys (a, max((1, (2)) -RDP for D1 D2-
In Appendix we discuss more related work on differential privacy and generative methods.
DATASET CONDENSATION AND DIFFERENTIAL PRIVACY
3.1 REVISIT THE ICML'S 22 WORK (DNN ET AL.
2022
Dong et (2022) first established connection between DC and DP by Proposition 4.10 in their paper, which is unfortunately proved upon two controversial assumptions. One explicit controversial assumption is regarding the posterior model parameter distribution, as stated in Assumption 3.1
Assumption 3.1 (Assumption 4.8 in (Dong al., 2022)) function E, the distribution of the model parameters is
Given the training dataset S and loss
1 Zs
P(O
exp( Σ (fo(s:).)))
(5)
Although (Dong et al.) 2022) presents the assumption on T. actually uses the assumption on the synthetic dataset S in the proof of its Proposition 4.10. The original version of Assumption 3.1m (Sablayrolles al. 2019, quoted by Dong et al. (2022). ) is given below.

---

Under review as a conference paper at ICLR 2023
Assumption 3.2 (Original Assumption in (Sablayrolles et al., 2019)) Given the training dataset and loss function E, the distribution of the model parameters is
[s] Σ {(fo(s))
P(O]S) & exp( T
(6)
Comparing the above two assumptions, we observe that Assumption 3.1 has a controversial issue- Given the same loss function and model architecture, the posterior model parameter distribution assumed in Assumption 3.1 is fixed, regardless of the stochasticity and the learning method. Note that in an extreme case, if we gradient ascent with fixed seeds, the parameter distribution could collapse into a Dirac distribution. In contrast, Eq. 6 in Assumption 3.2 has a temperature hyperpa- rameter T depending on the stochasticity and the learning method, Le.. T 0 corresponds to MAP, and a small 7' corresponds to averaged SGD (Polyak & Juditsky| 1992. Sablayrolles et al.) 2019). From this viewpoint, although it intractable to verify the correctness of Assumption 3.2] intu- itive that Assumption 3.1 is controversial. Here natural question to ask is -Culd we instead use Assumption 3.2 in the proof of Proposition 4.10 in (Dong al.] 2022 The answer No because
when T is small, we could not approximate exp(7 3 (E(fo (s)), ya) - ((fo(s(), 9:))) 1 by E (8(fo(s;).u) v:) (()( 9:)). Thus, we could not have Eq. 39 the proof of Proposition 4.10 in (Dng et al. 2022) with Assumption 3.2
In the following, we introduce the other controversial assumption which is implicitly used in the proof of Proposition 4.10 in (Dong et al. 2022 (Eq. 35 in (Dong et al. 2022))
Assumption 3.3 (Implicit Assumption in (Dong et al. 2022 With random initialization &,
(0, Ia), the synthetic data 87 that minimizes the distribution matching loss (Eq. 3 is
ã (under E),
where the data is represented under an orthogonal basis E = {e, eg...... .... ea with ET
{E,, e2 ... edim(spen(T)) forming the orthogonal basis of span(T) Dong et al. 2022
Let Q be the transformation matrix from & to the standard basis. We then have
T
:f = ==, + T
Σ j=1
æÿ (under standard basis),
(8)
where of and æ; represent : and ã. under the standard basis. In Appendix C we detail how to compute the transformation matrix and the synthetic data given in Eq. & for each class. Actually, need to use 7.7 instead of T to compute the synthetic data for class c.
Assumption 3.3 is only proved on linear feature extractors, but it is directly used in the proof of
Proposition 4.10 in (Dong et al., (022) (Eq. 35 in (Dong et al. (022)), which attempts to prove a general privacy bound for dataset condensation. Unfortunately, Assumption 3.3 is not always true when we use nonlinear feature extractors to learn the synthetic data.
We conduct an experiment verify the above claim: We use the same data initialization to compute
a set of 500 synthetic data samples with Eq. g (See Appendix C) and learn a set of 500 synthetic data samples by DM with nonlinear extractors on CIFAR10. We then compute the DM loss on the synthetic data by Eq. 3 with nonlinear extractors. The DM loss on the synthetic data computed with Eq. is much higher than the DM loss on the DM-learned synthetic data, which conflicts with Assumption 3.3 We further train two ConvNet models on the two sets of synthetic data, respectively. The model trained on the synthetic data computed by Eq. 8 oonly has about 25% accuracy while the model trained on the DM-generated synthetic data achieves approximately 60% accuracy.
Moreover, we test whether the distributions of the synthetic data computed by Eq, Eq.3aan and the synthetic data generated by DM with nonlinear extractors may have the same population mean for each class
"Te is the subset of T that contains all the data with label Similar to the accuracy achieved by DM with linear extractors reported in (Dong et al. 2022'' appendix.
4

---

Under review as a conference paper at ICLR 2023
Specifically, we define the null hypothesis as
Ho He (synthetic data defined by Eq. [ = (syytthheticc data generated by nonlinear DM)
We use BS test (Bai & Saranadasa 1996 since the conventional Hotelling's T test (Hotelligg where dl is the data dimension, and Ni and N2 refer to the number of samples from the two populations. We compute the test statistic of BS test, denoted by ZBs for the 10 classes of CIFAR10. The smallest ZBS approximately -3.03 < -20.000 oor which gives us sufficient evidence to reject the null hypothesis. Thus, even with the same random initialization, the synthetic data defined by Eq. X and the synthetic data generated by DM with nonlinear feature extractors can have completely different distributions. Therefore, it is problematic to use Assumption 3.3 to prove general privacy bound for dataset condensation.
[992] is only applicable the case that < Ni + N2
3.2 DIFFERENTALLY PRIVATE DATASET CONDENSATION (DPDC)
We show that the privacy bound proved by Dong et al. (2022) is problematic due to two controversial assumptions. To correctly connect DC and DP, we propose two differentially private dataset con- densation (DPDC) algorithms- a linear algorithm (LDPDC) and nonlinear algorithm (NDPDC).
Linear DPDC (LDPDC) We illustrate LDPDC in Algorithm 1 For each class we construct M synthetic data samples {- For each synthetic sample 8j. we randomly sample subset
{ from To by Poisson Sampling with probability L/Ne. L is the group size (Abadi et al, 15
2016), and N. = |Tal L, follows a Poisson distribution with expectation L. Similar to the = L/ in (Abadi et al. (016) and the Opacus library, the sampling probability 9e- L/Ne is fixed for each class in the execution of the Aagorithms-For the adjacent datasets of Te. we still consider qe as the sampling probability, then we could exploit the prior theoretical results on subsampling for DP L5
analysis (similar to Opacus). With [= we compute 8f by 85 ( [ + #r))
where NO, Ia) refers to Gaussian random noise with standard deviation a. We do not use a formula similar to Eq. 8 to construct synthetic data because Q leaks private information.
Algorithm Linear Differentially Private Dataset Condensation (LDPDC)
Require: Original Dataset T = Ti U T2... U Te: the number of classes C; number of data samples per class Ne; number of synthetic samples per class M; group size L.
for each class e do for j = to MM do
Take randomly sampled subset D. = far c) L5 from To with sampling probability L/N.
(by Poisson Sampling, similar to (Abadi et al. 2016: Yousefpour et al. 2021
= + o2 + + xx)
end for end for Output the synthetic dataset S
Nonlinear DPDC (NDPDC) We illustrate NDPDC in Algorithm 2 which is designed upon the idea of matching the representations of original and synthetic data. We follow (Zhao & Bilen 202
to use differentiable augmentation function Aw. (.)3) to boost the performance ( (-) is sim- ilar to a composite function). In each iteration of Algorithm 2 we first sample random parameters 0 for the feature extractor 4 (not pretrained) and initialize the loss as O. After that, for each class e, we sample the augmentation parameters w. and randomly sample a subset from To by Poisson sampling with sampling probability L/N.. We then compute the representations of the original data and synthetic data and clip the representations with a pre-defined threshold G.
We remark that it is essential to clip both the representations of original and synthetic data: We clip the representations of the original data for the purpose of bounding the & sensitivity; We also clip the representations of the synthetic data in order to match the representations Since G is pre-defined as the constant (not computed from original data), the operation of clipping
similar scale.
"a..00 refers to critical value with 99% confidence level (two-tail).
We refer the interested readers to /Zhao Bilen 2021b) for more details Aw.()) (-)-
5

---

Under review as a conference paper at ICLR 2023
the synthetic data representations (i.e., F($)) min(1,
Tr(s5)l )m(s)) in Algorithm 2 does not leak
G
[r(s5)laa
private information regarding the original data. After clipping the representations, we add Gaussian noise the sum of the clipped original data representations.
We use the squared f2 distance between the randomized sum of the clipped original data represen- tations (i.e., (O o²1) I) + El F(x5)) and the sum of the clipped synthetic data representations multiplied by a factor L/M (i.e.. M Σド= F(s5)) as the loss. We use the factor L/M because E.21 F(x{) sums up Del (B([D.)) = L) representations, while Σ F(sf) sums up M repre- sentations. At the end of each iteration, we update the synthetic data with the gradient the loss é with respect to S, similar to Algorithm 1 in (Zhao & Bilen, 202 In practical implementation, following (Zhao et al. 2021 Zhao & Bilen 2021b a), we implement S as a tensor variable with size
[N, data_shape] (e.g., N. 3, 32, 32] on CIFARIO), where N is the size of the synthetic dataset.
Here a natural question to ask is Why not combine distribution matching and DP-SGD for dif- ferentially private data condensation? For many common deep learning tasks, could compute sample-wise loss so that DP-SGD can clip the sample-wise loss gradients to bound the sensitivity. However, distribution matching uses the squared & distance between the averaged original data representations and the averaged synthetic data representations as loss, so we could not directly compute sample-wise loss and apply DP-SGD to distribution matching.
Algorithm 2 Nonlinear Differentially Private Dataset Condensation (NDPDC)
Require: Original Dataset T Ti U 'T2... U Te: the number of classes C: the number of data samples per class Ne; the number of synthetic samples per class M; feature extractors 4 (not pretrained); parameter distribution Pe: group size L; number of iterations I. Initialize S = { { 1= 1C with random noise from A A( La)
for each iteration (total number of iterations is I) do Randomly sample 0 from Pe and initialize the loss as f = 0
for each class do
Sample the augmentation parameters We
Take a randomly sampled subset D. from To with sampling probability L.No (by Poisson Sampling, similar to (Abadi et al. 20166] Yousefpour et al. (021I).
La (at)) for the subset Dr (2f,c) !D.l
Compute Representations: r<x{))
r(sf) Do (Aw. (Awr. for S. = {
Norm Clipping: F($5) = min(1, TT(e5)] )r( (s())): F(x;)) = min(1, |ل( )r(a)))
Compute Loss: = f 1/ ΣØ- F(85) - (W(0,021) + + - end for
S = S se (sf = 89 v v/ l Vaf S).
end for
Output the synthetic dataset S = [(
Theorem 3.1 and Theorem 3.2 bound the privacy risk of Algorithm and Algorithm 2 respectively.
Theorem 3.1 Suppose the original data æ satisfies x E [-b, and let Sg (a) e Da((1 () (f) (1,6f))) of)) with 5 = (b///d) and q = maxx(L/N.)) then LDPDC obeys
(a, MΩ RR)) and (minas1 (MΩ (a)+log((( 1)/a) (log 5 log
Theorem 3.2 Let Pg,55 (a) A (1 g), o3) + gN(1, ( ( with ō2 = oGG and
q max.(L/N.. then NDPDC obeys (a, IT 2, RR)) and (minas> 1 (102, 1)/a) - -llg 8 + log a)/((a 1)), -DP where the number of iterations.
8, (a) + log((a-
The basic idea is prove the RDP bound on T. (a,, c) - where only need to consider æ; due to the same c, followed by generalizing the theoretical result to T using Lemma 2.3 In the experiments, we follow Opacus to exploit Mironov al. (2019)'s method for computing o2 (a). We note that Mironov et al. (2019) did not provide convergence analysis for their computation method when a is a fractional number. For completeness, we present our convergence analysis for the computation method in Appendix
We detail the proof of Theorem 3.1 and Theorem 3.2 in Appendix A

---

Under review as a conference paper at ICLR 2023
Dataset +
MNIST
FMNIST
Method 4
Test Ace
DP Budget
Test Ace
DP Budget
DM with Rand Init
98.38% 0.05%
No
86,90% = 0.44%
No
DP Sinkhorn
86.92% + 0.93%
(10, 10 9)-DP
65.60% + 1.06%
(10, 10 ")-DP
DP-MERF
84.81% + 2.04%
(1, 10 ")-D
63.05% + 2.05%
(1, (9,10-9))-00 9)DD
Linear DPDC (LDPPDC)
85.79% + 0.81%
(1.10, 1--P
63.95% + 0.42%
(1.06, 10-
Nonlinear DPDC (NDPDC)
97.35% + 0.13%
(6.12, 10 3-DP
82.72% + 0.35%
(5.45, 10 S-DP
Dataset +
CIFARIO
CelebA
Method 1
Test Acc
DP Budget
Test Ace
DP Budget
DM with Rand Init
59.69% + 0.44%
No
84.13% + 0.42%
No
DP Sinkhorn
15.09% + 0.33%
(10, 10 S--DP
71.72% + 1.13%
(10, 10 5)-PP
DP-MERF
17.10% 0.78%
(1,10-9)-DP
69.26% + 0.90%
(1, (1,10-5)-DB
Linear DPDC (LDPDC)
25.81% +: 0.52%
(1.14, 10 9-DP
68.72% + 2.26%
(0.61, 10-
Nonlincar DPDC (NDPDC))
52.68% + 0.40%
(6.72, 10
JJDPP
80.66% + 0.63%
(0.71, 10 9)-DP
Table 1: We use the default settings for all the methods. We employ 50 synthetic samples per class to train ConvNet models and report the testing accuracy here. We follow (Zhao & Bilen 202 to apply the augmentations in (Zhao & Bilen 2021b) when training ConvNet models. According to Table 8 in Appendix D even using low DP budgets (e < 1), NDPDC still outperforms LDPDC, DP-
MERF, and DP-Sinkhorn Similar to DP-Sinkhorn, we can also fix a target DP budget and compute the corresponding (or I) run LDPDC and NDPDC.
MNIST
FMNIST
CIFARIO
CelebA
Linear DPDC (LDPDC)
85.80% + 0.39%
63.64% t 0.76%
25.46% + 0.83%
69.64% + 1.01%
Nonlinear DPDC (NDPDC)
95.32% + 0.29%
78.79% t 0.37%
42.40% + 0.86%
81.47% + 0.80%
Sinkhorn
55.43% + 1.54%
43.22% + 1.40%
12.62% + 0.27%
64.02%
0.48%
DP-MERF
84.81% + 2.04%
63.05% + 2.05%
17.10% + 0.78%
69.26% + 0.90%
Table 2: We set e = and compare LDPDC, NDPDC, DP Sinkhorn, DP-MERF.
EXPERIMENTS
4.1 EXPERIMENTAL SETUP
We follow Zhao & Bilen 2021b Dong et al. 2022) to conduct experiments on four widely- used datasets: MNIST (Deng 2012). Fashion-MNIST (Xiao et al. 2017), CIFARIO (Krizhevsky et al. 2009), and CelebA (gender classification) (Liu et al. 2015). In the following, we introduce the baselines, DPDC settings, and the method for evaluating the synthetic data utility. We provide DPDC's code in the supplementary material, where the readers could find more technical details.
Baselines We compare DPDC with the state-of-the-art dataset condensation method, i.e., distri- bution matching (DM) (Zhao Bilen (222a). and two recent DP generative methods, i.e., DP- Sinkhorn (Cao et al.) 2021) and DP-MERF (Harder et al.) (021). For DP-Sinkhorn, we use Cao ct al. (2021)'s code to run the experiments. We set m to and the target to 10. For DP-MERI, we use Harder et al. (2021)'s 's code and follow (Harder et al. 2021 to set to 5.
DPDC Settings For LDPDC, we set = Vd, M 50, L 50 by default. Given that b 1, ã dbv/d) 1. For NDPDC, the default settings are σ 1, G 1, M 50, L 50, = 10000, and 7 = 1. We set G = 1, so ã2 o/G = 1. We follow (Zhao & Bilen 2021 to three-layer convolutional neural networks based feature extractors) for NDPDC. Batch normalization (BN) (Ioffe & Szegedy] 2015) is not DP friendly since sample's normalized value depends on other samples (Yousefpour et al. 202 Therefore, we do not use BN in the extractors. Since the data statistics like channel-wise means and channel-wise standard deviation may leak private information, we follow (Cao al. 2021) to use fixed value 0.5 for normalizing the images, which does not make obvious difference in the performance of DPDC and the baselines. After normalization, the pixel values range from -1 to 1.
the feature extractors (also called Conv Net-
Performance Evaluation We employ the evaluation method in (Zhao & Bilen 2021b Dong
et al. 2022) to compare the performance of DM, DP-Sinkhom, DP-MERF, and our DPDC algo-

---

Under review as a conference paper at ICLR 2023
LDPDC
MLP
LeNet
AlexNet
VGGII
ResNet18
MNIST
80.40% 1 0.33%
83.32% 3.03%
83.22%
0.67%
85.81% 1 7.4
88.14% 73%
FMNIST
68.84%
0.58%
68.49%
1.36%
66.45%
0.94%
67.31% + 1.01%
67.58%
0.92%
CIFARIO
30.60%
0.18%
29.82%
0.81%
29.65%
0.82%
24.86%
0.29%
23.79%
0.59%
CelebA
1.51% 69.48%
66.95% = 0.53%
67.61%
0.87%
2.23% 66.87%
1.42% 65.88%
NDPDC
MLP
LeNet
AlexNet
VGGIT
ResNet18
MNIST
93.15%
0.83%
96.82%
0.13%
97.00%
0.32%
97.37
0.13%
97.67%
0.14%
FMNIST
79.98% 0.33%
80.89%
0.40%
81.94%
0.54%
82.63%
0.54%
81.50%
0.33%
CIFARIO
36.99%
0.62%
36.94%
1.24%
42.60%
1.06%
48.80%
0.24%
44.79% 0.64%
CelebA
75.95% 1 1.30%
78.02% = 1.01%
79.69% 0.91%
81.25% 1.31%
82.32% 0.68%
Table 3: Performance varied model architectures with default settings: For NDPDC, the synthetic data is learned on ConvNet-based feature extractors and evaluated on those model architectures. The privacy budgets and the results on ConvNet are given in Table T
rithms. The evaluation method is to train deep learning models on the synthetic data from scratch and compare their accuracy on the real testing data. Higher testing accuracy indicates better syn- thetic data utility for training deep learning models (better performance). We also follow Zhao & Bilen| 2021b a to train a variety of model architectures, including MLP (Haykin) 1994). LeNet (LeCun et al. 1998), AlexNet (Krizhevsky et al. 2017). VGG1 (Simonyan & Zisserman 2014), and ResNet18 (He al. 2016), on DPDC-geenratee synthetic data to evaluate the data utility.
4.2 MAIN RESULTS
We report the main experimental results in Table 1 Our LDPDC algorithm achieves comparable performance to DP-MERF and DP-Sinkhorn with low DP budgets. Our NDPDC algorithm provides acceptable DP guarantees (c < 10) with a mild utility loss, compared to the random-initiale non-private DM method (Zhao & Bilen 2021a). Furthermore, NDPDC allows a flexible trade-off between synthetic data utility and DP budget-1f we are not satisfied with NDPDC's DP budgets in Table D we could increase o to reduce the budget. As shown in Table even with low DP budgets 1, NDPDC still outperforms LDPDC, OP-Sinkhorn, and DP-M DP-MERR. For DP-MERF, even we decrease a to 0.5 (e > 10), the accuracy increment is only about 7% on FMNIST and less than 5% the other datasets, shown in Table 9 in Appendix D We conjecture that small amount of NDPDC-condensed synthetic data is more useful than a small amount of De-generator generated synthetic data because DP generative methods optimize the generative model parameters, while NDPDC directly optimizes the small amount of synthetic data. It is worth noting that DPMix [Lee et al. 2019) recent linear DP data publishing method, which seems similar to LDPDC. However, LDPDC and DPMix still have some differences as discussed in Appendix F indicating that LDPDC may be better than DPMix. Compared to LDPDC and DPMix, NDPDC is more suitable for solving nonlinear problems such as image recognition. According to the results in (Lee et al.)
2019) NDPDC outperforms DPMix by 13%-24% in testing accuracy on MNIST and CIFARIO.
We further train variety of model architectures the synthetic data generated by LDPDC and NDPDC and report the testing accuracy in Table Since LDPDC does not rely on deep networks to learn the synthetic data, it is hard to predict which network architecture can make the best use of the LDPDC-generated synthetic data. According to the results in Table 3 on FMNIST, CIFARIO, 10, and CelebA, MLP makes the best use of the simple LDPDC-genenn -egeraete synthetic data, while on MNIST, ResNer18 makes the best use of the synthetic data. For NDPDC, since the synthetic data is learned on ConyNet-based extractors, ConvNet makes better use of the synthetic data than the other architectures. Besides, we visualize the synthetic images in Appendix D JDPDC-generatee images look more diverse and more useful than the synthetic images generated by DP-Sinkhorn, DP-MERF, and DPMix (Fig. 1 in (Lee et al. 2019) provides synthetic images generated by DPMix.).
4.3 ABLATION STUDY ON NDPDC
Although LDPDC is simple and comparable to recent DP generative methods here, we still rec- ommend the readers to use NDPDC in practice because of its outstanding performance. In this subsection, we conduct ablation study for NDPDC on MNIST, FMNIST, and CIFARIO with recom- mendations on how to select hyperparameters for executing NDPDC. When we study the effects of one hyperparameter, we fix the other hyperparameters as the default settings.
8

---

Under review as a conference paper at ICLR 2023
Effects of Noise Multiplier on Privacy and Utility We plot the DP budgets of NDPDC with different a in Fig. iin Appendix (mnd report the corresponding testing accuracy in Table Fig. [ in Appendix and T'able(4indicatt indicate that, creases, e will decrease, and the testing accuracy will also decrease. But the testing accuracy does not decrease much as increases. Thus, if we are unsatisfied with the DP budget, we could simply increase to obtain low DP budget with little loss of synthetic data utility. Additionally, we do not recommend to set a o/G G S 0.75, otherwise e will be larger than 10, then the DP guarantee is not very useful.
Noise
MNIST
FMNIST
CIFARIO
0.75
97.51%
83.28%
54.33%
a 1.25
97.06%
82.23%
51.36%
1.5
96.86%
81.66%
50.12%
in-
σ 2.0
96.46%
80.96%
47.93%
Table 4: The averaged testing accuracy of Con- vNets trained on the synthetic data generated by NDPDC with different noise multiplier
Effects of Group Size I on Privacy and Util- ity We plot the DP budgets with different L. Fig. Din in Appendix D and show the testing accu- racy in Table 5 If we increase L, it is expected that more original data will be sampled in each step for learning the synthetic data, and thus, both and the testing accuracy will increase. Accord- ing to Fig. iin Appendix Dnd 3 if we are unsatisfied with the DP budgets, we could also decrease L to 25 to obtain better DP budgets with a minor utility loss.
Group Size
MNIST
FMNIST
CIFARIO
96.41%
80.88%
48.07%
L = 75
97.61%
83.97%
54.81%
L = 100
97.90%
84.40%
56.42%
Table 5: The averaged testing accuracy of Con- vNett trained the synthetic data generated by NDPDC with different group size L..
Effects of Number of Iterations I on Privacy and Utility We plot the DP budgets in Fig. [ in Appendix D and show the testing accuracy in If we increase I, since NDPDC will learn on the original data for more iterations, both
Iterations
MNIST
FMNIST
CIFARIO
2000
96.32%
80.45%
47.42%
4000
96.84%
81.64%
50.07%
Table 6
I I= 6000
97.14%
82.18%
51.20%
== 8000
97.28%
82.50%
52.19%
the DP budget and testing accuracy will increase. Since the testing accuracy does not increase much when 7 large, reducing / another good choice beyond increasing and reducing L to save DP budget with acceptable utility loss.
Table 6: The averaged testing accuracy of Con- vNeets trained the synthetic data generated by NDPDC with different number of iterations /.
Effeets of Synthetic Data Size M on Privacy and Utility We show the testing accuracy with different M in Table 7 As M increases from 10 to 200, the testing accuracy also increases but will almost stop the uptrend around a certain M. This is probably because more synthetic data has the potential to capture more information, but the DP guarantee also limits the information leaked from the original data. Since the DP budget is unchanged, after the amount of synthetic data enough for capturing all the limited information, more synthetic data could not capture more useful information. Given the experimental results, M 50 is a good setting here. We do not recommend setting a larger M (M > 50), which will result in marginal performance gain but much more cost in the downstream applications.
Data Size
MNIST
FMNIST
CIFARIO
M = 10
96.47%
80.00%
45.88%
M 100
97.54%
82.88%
54.24%
M 200
97.50%
83.16%
54.26%
Table 7: The averaged testing accuracy of Con- vNeets achieved by NDPDC with different num- ber of synthetic samples per class M.
CONCLUSION
In this paper, we revisit a recent proposal in ICML'22 on pwwaay-preserving dataset condensation and reveal that its proposed privacy bound is problematic because of two controversial assumptions. To correctly connect data condensation and differential privacy, we propose two differentially private dataset condensation (DPDC) -DPPC and NDPDC. We demonstrate that LDPDC can use low DP budgets to achieve comparable performance to DP-Sinkhon and DP-MERF. Moreover, show that NDPDC can provide DP guarantees with mild utility loss compared to the distribution matching method. We hope our work can inspire further research in this potential direction to alleviate the cost burden and privacy concern in deep learning.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pp. 308-318, 2016.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214-223. PMLR, 2017.
Zhidong Bai and Hewa Saranadasa. Effect of high dimension: by an example of sample problem. Statistica Sinica, pp. 311-329, 1996.
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, pp.
PMLR, 2020.
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In 2014 IEEE 55th annual symposium foundations of computer science, pp. 464473. IEEE, 2014.
Amos Beimel, Kobbi Nissim, and Uri Stemmer. Characterizing the sample complexity of private learners. Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pp. 97-199 10, 2013.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. In International Conference Learming Representations, 2018.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of Cryptography Conference, pp. 635-658. Springer, 2016.
Mark Bun, Cynthia Dwork, Guy Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated cdp. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 74-86 86, 2018
Tianshi Cao, Alex Bie, Arash Vahdat, Sanja Fidler, and Karsten Kreis. Don't generate me: Training differentially private generative models with sinkhorn divergence. Advances in Neural Informa- tion Processing Systems, 14:12480-12492, 2021.
Kamalika Chaudhuri, Jacob Imola, and Ashwin Machanavajjhala. Capacity bounded differential
privacy. Advances in Neural Information Processing Systems, 32, 2019.
Dingfan Chen, Tribhuvanesh Orekondy, and Mario Fritz. Gs-wgan: A for learning differentially private generators. Advances in Neural Information Processing Systems, 33: 13:12673-1284. 2020.
approach
Li Deng. The mnist database of handwritten digit images for machine learning research. JEEE Signal Processing Magazine, 2916):141-142, 2012.
Cem Dilmegani. ways to overcome deep learning challenges in 2022, 2022. URL https: com/ deep- Lewrning whwilehgeallllle wtw.aniinnnnhllllggggss////////e
Tresearch.aimulee
Tian Dong, Bo Zhao, and Lingjuan Lyu. Privacy for free: How does dataset condensation help privacy? arXiv preprint arXiv:2206.00244 2022.
Cynthia Dwork and Guy N Rothblum. Concentrated differential privacy. arXiv preprint arXiv:1603.01887, 2016.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pp. 265-284. Springer, 2006.
James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of priiaccy-preeteee preserving bayesian data analysis. In Proceedings of the Thirty-Second Conference on Uncertainty in Artificial Intelligence, pp. 192-201, 2016.
10

---

Under review as a conference paper at ICLR 2023
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farke Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Infor- mation Processing Systems, volume 27, 2014.
Frederik Harder, Kamil Adamczewski, and Mijung Park. Dp-merf: Differentially private mean beddings with randomfeatures for practical privacy-preserving data generation. In International conference on artificial intelligence and statistics, pp. 1819-1827. PMLR, 2021.
Simon Haykin. Neural networks: a comprehensive foundation. Prentice Hall PTR, 1994.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Irina Higgins, Loic Matthey, Arka Pal, Christopher Burgess, Xavier Glorot, Matthew Botvinick, Shakir Mohamed, and Alexander Lerchner. beta-vae: Learning basic visual concepts with constrained variational framework. 2016.
Harold Hotelling. The generalization of student's ratio. In Breakthroughs in statisties, pp. 54-65. Springer, 1992.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pp. 448-456. PMLR, 2015.
James Jordon, Jinsung Yoon, and Mihaela Van Der Schaar. Pate-gan: Generating synthetic data with differential privacy guarantees. In International conference on learning representations, 2018.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal Computing. 40(3):793-822 2011.
Diederik P Kingma and Max Welling, Auto-encoding variational bayes.
arXiv preprint
1rXiv:13/2.111,220 2013.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. Communications of the ACM, 60(6):84-90, 2017.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(1 86(11):278--2324 1998.
Kangwook Lee, Hoon Kim, Kyungmin Lee, Changho Suh, and Kannan Ramchandran. Synthesizing differentially private datasets using random mixing. In 2019 IEEE International Symposium on Information Theory (ISIT). pp. $42-546. IEEE, 2019.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference on Computer Vision (ICCV), December 2015.
Yunhui Long, Boxin Wang, Zhuolin Yang, Bhavya Kailkhura, Aston Zhang, Carl Gunter, and Bo Li. G-pate: Scalable differentially private data generator via private aggregation of teacher discrimi- nators. Advances in Neural Information Processing Systems, 34:2965-2977 -9777, 2021.
Ilya Mironov. Rényi differential privacy. In 2017 IEEE 30th computer security foundations sympo- sium (CSF), pp. 263-275. IEEE, 2017.
Ilya Mironov, Kunal Talwar, and Li Zhang. Rényi differential privacy of the sampled gaussian mechanism. arXiv preprint arXiv: 10530, 2019.
Mchdi Mirza and Simon Osindero. Conditional generative adversarial nets. arXiv preprint arXiv: 14 17844, 2014.
Timothy Nguyen, Zhourong Chen, and Jachoon Lee. Dataset meta-learning from kernel ridge- regression. In International Conference Learning Representations, 2020.

---

Under review as a conference paper at ICLR 2023
Nicolas Papernot, Martin Abadi, Ülfar Erlingsson, lan Goodfellow, and Kunal Talwar. Semi- supervised knowledge transfer for deep learning from private training data. 2016.
Boris T Polyak and Anatoli B Juditsky. Acceleration of stochastic approximation by averaging. SIAM journal on control and optimization, (0(4):838-855) 1992.
Alfréd Rényi al. On measures of entropy and information. In Proceedings of the fourth Berke- ley symposium on mathematical statistics and probability, volume 1. Berkeley, California, USA, 1961.
Alexandre Sablayrolles, Matthijs Douze, Cordelia Schmid, Yann Ollivier, and Hervé Jégou. White- box vs black-box: Bayes optimal strategies for membership inference. In International Confer- ence on Machine Learning, pp. 3558-5567. PMLR, 2019.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv:1409.1555 2014.
Reihaneh Torkzadehmahani, Peter Kairouz, and Benedict Paten. Dp-cgan: Differentially private synthetic data and label generation. In Proceedings of the IEEF/CVF Conference on Computer Vision and Puttern Recognition Workshops, pp. 0-0, 2019.
Margarita Vinaroz, Mohammad-Amin Charusaie, Frederik Harder, Kamil Adamczewski, and Mi Jung Park. Hermite polynomial features for private data generation. In International Con- ference on Machine Learning, pp. 22300-22324. PMLR, 2022.
Tongzhou Wang, Yan Zhu, Antonio Torralba, and Alexei A Efros. Dataset distillation. arXiv preprint 1rXiv:1811.10999, 2018
Yu-Xiang Wang. Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 1226-1235. PMLR, 2019.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmark- ing machine learning algorithms. arXiv preprint 1708.07777 2017.
Liyang Xie, Kaixiang Lin. Shu Wang, Fei Wang, and Jiayu Zhou. Differentially private generative adversarial network. arXiv preprint arXiv:1802.067733 2018.
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 wtXiv:2109.1229: 2021.
Bo Zhao and Hakan Bilen. Dataset condensation with distribution matching. CoRR, abs/2110.04181,, 2021a.
Bo Zhao and Hakan Bilen. Dataset condensation with differentiable siamese augmentation. In International Conference on Machine Learning, pp. 12674 12685. PMLR, 2021b.
Bo Zhao, Konda Reddy Mopuri, and Hakan Bilen. Dataset condensation with gradient matching. ICLR, 1(2)33 2021.
12

---

Under review as a conference paper at ICLR 2023
A OMITTED PROOF
We first prove Lemma A.1 Based on Lemma A.1 we can easily prove Corollary A.1 used in the proof of Theorem & 3.2
which will be
Lemma A.1 Let u(z) and vzz) be two differentiable probability density finnetions domain Z (u, V: : 2 + R). ufz) + v(z) and u(z). vz)) > 0 on 2, then Da q)u(z)+ + (u())]((())) is an increasing function w.E.t q when 1 and E [0, 1].
Lemma A. is easy to understand: As increases, the weight of u(z) in the mixture (1 (()) + (u)=) decreases, thus the divergence between (1 - q))(z) + qu(2) and u(2) should increase. To our best knowledge, we are the first to present Lemma A.1 so we detail the proof in the following.
Proof [proof of Lemma A.1
The Rényi divergence Da - g)u(=) + qv()))
defined as
a In u(z)( g)u(z) + qU(2)) jd
a In / / u(2)(1 - a u(z))
1
(xz)
dz
(9)
u(z)
The derivative of Eq. w.r.t q
dz / alv(z) - u(z))( a q u(z)
0- dz,
(10)
(a- 1) (1
q m(z)
To prove Lemma A.1
we need to show Eq. 10 is positive when q [0, 1]. Since a: > and
u(=)(1 - 9 + 9 )
(If q * 0,
q
9 v(z)
(=(=))
--9 2 0). we only need to prove
[2(((z) - --)=)(((1)))1) - q + -())
a= O.
We divide 2 into 21 and Σg where 2 = fz 2|v(2) < m(2)) and 2, = fz E Zl((2) 2 n(2))-
Apparently, 3, and 3e are disjoint, and 2 = 3, U Zz. Thus, we can rewrite [v((( - u(z))(1
2 (()) ja-'dz vu(z)
q +
v(z)
/ (v(z) - (v(z)
11z) jo- jo-1dz dz (11)
(v(z) u(x))( +
dz +
u(z)) q [(())
u(z)
21
2
When 2 E Z1, we have (i) m(2) u(z)
(ii)
v(=)
1 < <(z) < u(2)); (1i)
u(z)
(1 1--4 q - q v(z)
a-1 (1 = - q > 1
q +
1 - 2 0). Therefore,
| (v(z) - (1=))(1=99))) g
f(2)
a- dz >
(v(z) u(z))dz
(12)
u(z)
jz1
When 2 E Zz, we have (i) v(z) - u(z) z 0: (ii)
v(=)
N 10 < u(z) s v(2)); (ii)) (1 +
a-1 1 2 1. Therefore,
/ 22
(u(z) u(2))(1 - + u(z) a- a-1dz
dz 2
(u(z) - u((2))dz
(13)
u(z))
As a result,
/ [v(z)-u(z)) - u(z))(( + v(z)
a aa-1dz dz
(u(z) u(())dxx + / (u(2) -(())dzz
u(z)
21
- -1((x)-u(22)) -u(=))dz / v(z)dz -f u(2)dz== =
Thus, the derivative of Eq. 9 w.r.t is positive. This concludes the proof of Lemma A.I
Corollary A.1 Let (a) A Da((1 - q.)W((,00) + (3)1,, o2)), where c =
1,2, C. We have max, Dg (a) S (m)
13

---

Under review as a conference paper at ICLR 2023
Proof [proof of Corollary A.1 Let u(2) _N o²) and v(2) _ ((1, (2 - R). then based on Lemma A.I, we know that 22 (a) is an increasing function w.r. 4. Thus, the maximum of ag (a) is achieved at max.(g.). This concludes the proof of Corollary A.1
In addition to Corollary A.1 2019) in the proof of Theorem 3.1
also need to use definition and lemma from (Mironov et al.
3.2
Definition A.1 ((Mironov al. 2019) Let be a function mapping subsets of a dataset D R". Mironov et al. (2019) define Sampled Gaussian Mechanism (SGM) as
(GM fa subset sampled from D with probability q) o0
(14)
Lemma A.2 (Mirronov et al., 2019)) Given the notations in Definition A.1 ffr any two adjacent
subsets Dj and D2 sampled from D. (l f(D2) S 1, then SGM or (D) obeys (a, RDDD
where c D.
Proof [proof of Lemma A.2 Given the proof of Theorem 4 in (Mironov et al. 2019 we know that g. (D) oheys (a,e)-RDP, where could be max(Pa (0, + (L o²) (N ( (), (2) o2)),
According to Theorem 5 in (Mironov et al. 2019) Da +od
(o o) + (N(1, o²). Thus, (a)(a), where (g) Da((1- - ()01))3)(( +
Eventually, we can present the proof of our theorems.
Proof [proof of Theorem 3.1 Define gDD) Σ Iy where D = (2;, g(0) = 0. For any
two adjacent datasets D, D' To (D' DU (æ')),
}). we have
(lg(D) g(D'') = || s
(15)
Thus, (D)
1 o 1.
In Algorithm I a synthetic data sample can be represented by
byd, L (D))( + o)) where ã = (b(Vdd
(16)
where De subset sampled from Te with by Poisson sampling with sampling probability le L/Ne. Apparently, SG (Te) (Da) + (N0,001) is sampled Gaussian mechanism
(SGM), and g gD')lla
Given Lemma A.2 SG (Ta) obeys (ax, Pg (R)) with ō = o and L/Ne- According to the post-processing property, 8, also guarantees (ax, 2q RDD.
Since I Dotpuut M synthetic samples for each class c, according to Lemma 2.2 Algo- rithm guarantees (a, (a,M2 (a)) for To. Since Ti, T2.... To are disjoint, according to (a,, max. (a:)))-RDP for T = Ti U T UTc.
Lemma 2.3 Catorithm@uuuraann
Corollary A. indicates that maX. (a:) MΩ mmxmxx.gg.).) (a). Therefore, Algorithm
obeys (a, MΩ (a))-RDP with max, (Lxx. and ã a/(bVd).
Proof [Proof of Theorem 3.2 For D {a, y1) 1. define (D) = E!' min(1, [[((=)) )r()),
where r(x;) ( (;) a.)). Also, define (0) 0. For any two adjacent subsets D, D' c To
and D' = -DU (x'), we have
(D) (D')ll | ||2 min(1, |[(a')]l2
)r(a')) S.. G.
(17)
14

---

Under review as a conference paper at ICLR 2023
Thus, (l) (D S
In each iteration of Algorithm
we rewrite (0 + EiDi F(æ{) as
1 G(N gg(D)), where 82 o/G
(18)
Apparently, SG (Te) (. 0) with 82 o/G and qe L/N, is also sampled
Gaussian mechanism (SGM). Since (D) (D) S gG (To) obeys (a, ag (a))- RDP, where 22 (a) _ (, - (0, o3) - (3) 02)).
Given the post-processing (iopetty,, de L/N, and ō2 o/G.
(Da) also guarantees (a, Pg (a)) RRD)-RDP with
According to Lemma 2.2 Algorithm guarantees (ex, 19 a. (a))--DD for Te. Since T1, T2, ... Te
are disjoint, based on Lemma 2.3 we know that Algorithm guarantees (a, max (a)))- RDP for T = =T: U2.. UTc.
Corollary A.1 indicates that max. (19 (a)) 1 (9 (a). Thus, Algorithm (a, T2 (1c) (a)) RRD) with max, (L/N. and o2 o//.
2 obeys
Here we also prove that Lemma 2.1 is tighter than Mironov 2017 conversion law.
Proof We first provide Mironov (017 's conversion law:
Lemma A.3 (RDP DP Conversion Mironov 2017)) If randomized mechanism M guaran- tees (a, t)-DPP, then it also obeys (e + log(1/0)/ (a
1),
Since ()/- < 1, log((a < 0. Since a > 1, log a > 0, and thus (loga))(((( 0. Combining log((a- 1)/a) and - (log a)/(a= 1) < 0, we have
log((a= 1) (x) - (log a)/(ae (a- 1) < 0 when a > 1.
(19)
We add + log(1/0)/(a 1) both sides of the above inequality and obtain
+ log((a - 1)/a) (log 5 + log.ll/////// aa - 1) < e log(L/0)/(a-11 - when a >
(20)
Therefore, Lemma 2.1 is tighter conversion law compared to Lemma A.3
B COMPUTATION METHOD FOR 2g (a:
In this section, we briefly introduce the computation method in MMironov al. 2019 which is used in Meta's 'ss Opacus library (Yousefpour et al., 202TT. Mironov et al. (2019) did not provide convergence analysis on the infinite series for computing the integral when a fractional number. So for completeness, we provide detailed convergence proof in this section.
Let u(z) _N(00
0²) and (Z2) AN(1, we can express Dg.o (a) as
u(2) pz (a) = a- In u(2)(1 + u(2)
1
1
u(2)
In E Bern(s))(1
)a
(((2)
(21)
If an integer, the integral can be expressed as the sum finite number of terms by applying binomial expansion, i.e.
x(z)
1(2)
(0)
9) a-ggt v(2)
(1 q +
Ea 9) 0)aa00- a-
(22)
u(=
k=
k=
15

---

Under review as a conference paper at ICLR 2023
Thus, (a) can be rewritten
Q (a)
1
In E B())(()
a
1: (1
-))==(/// *
2122)
u(2))
k=0
1 In
(2))
(1
(23)
u(z)
The remaining problem is to compute (z) w())
M..
Given that u(z)
exp(
and
0v25
20
v(2) ov22 exp(
(2-1)² ), it is not hard to derive that 20
((2
1.2
Bxou(=)
E
u(z) |d1 = exp(
(24)
20
Therefore, there is an analytical solution to 2g.o when a is an integer, L..,
k2 k
(a) In
b (1 9)" "00="0 exp(
(25)
202
kmm
If a is fractional number (a: E R), then we need to rely on the general binomial theorem to expand (1 q d(=))
Lemma B.1 (General Binomial Theorem) a, E R and |3| < 1, then (1 + 7)t can be ex-
pressed as convergent series, i.c., (1+7)²= E (i) where (+)
Based on Lemma B.1 we have the following corollary:
Corollary B.1 Ifa 3, y E R and hy| < [3), then (3 + 7) can also be expressed as convergent I (a-m)
series, i.e., 8o (1 3) g Σ (3)* = E (+) & ga-k, where (+)
R!
Given that 20 = 1 + In(g - 1) (2) in (Mironov et al. 2019 1
(()) m(()) when a < 20, and
v(z) when 2g. According to Corollary B.1 1 q 9 a()
we have the following convergent series:
((z) a (1- q + 9
k=U 2)
when 2 < 20
(26)
4)*
aakk when > 20
k=u
In the following, prove that the two series in Eq. 26 are also convergent 20-
Proof [Eq 26 is convergent at 2 = 20]
v(zo) If we substitute = in Eq. 26 with 20 (1 - - a Au(z))
), we can obtain
k (1 9)" a /hr p(22) x
(1 (0)(1
a
a)a p- v(20) ym aa =(1 9)"
00
u(20)
k:
u(20)
k
1m
(27)
We first show that lime->+00
(00 = 0 by representing [()] product of three partitions, i.e.,
[a] (a - m)
a
m m
(28)
k
[o]
When 2 [a] + 1, la
m
< Thus,
when m 2 [a] + 1. So we
have
k-1
a-m 1. Since
( is finite number and limg-+o0 0. we have a
m=
[ (1)
m
limg-xted
0.
16

---

Under review as a conference paper at ICLR 2023
In summary, the series (1 - -0 Σ k=0 satisfies the following conditions: (i) lim ((x)
(ii) When & 2 [a] (or k > a), (2) and (6+1) have different signs (iii) (++1))
< [(2) since
((++))//((==
1.
Given the above conditions, according to the alternating series test, we can conclude that Σ a convergent series with (%) 11 (o m)
Σ k= (
Therefore, we can rewrite Eq.
26 as (Eq. 12 in (Mironov et 2019
v22)
k=u (1) - ((2)
when 2 S z0
(1 q +
(29)
k=n (z) 9) q0=000
when 2 20
As result, we could rewrite (a)) as
a
M(2)
(a)
In
((2)
(1 ))
dz +
u(z)
400
(22)
u(z)
k
d22)
u(2)
k=
30 u(2)(
u(2)
In
(1
g)aak
y dz +
k
u(2)
k=0
80
u(z)( v(2) a dz)
(1 9) qp x
(30)
k
u(z)
k=0
According to MMronovv et al.
2019)
we could compute the integrals in the above series by
u(=)(
v(=)
d=
exp( 1.2
Jerfe( -
u(2)
2
20²
V20
dz exp( (a kk)² (a k))
1
20 (a k))
u(>)
jerfe(
(31)
22
The remaining problem is prove that Eq. 30 is convergent. Since Mironov al. (209)) did not provide convergence analysis, for completeness, we detail the convergence proof the following.
Proof [Eq. 30 is convergent] We first prove that the first half in In(.) in Eq. 30 Le., E (1)
q)a gh
20 u(2)( ((s) & dz is convergent series. We rewrite the series as
(1
DC
q
u(z)
1(2)
k dz
(32)
k
(1)))
k=0
Given that 2g 2 + 02In(q
1), we have
2kzo - k
1 1))
=1--9) qst
exp(
exp(k In(4
(33)
20
q
Thus,
9 kk 1 u(2)(
20
M(2)
x² 2k(z zo)
dz
exp(
Jdz.
(34)
u(z)
σ 2 -00
2T
202
Since - 20 S for z E (-x0, 20), expl
2(2
< and thus,
20
1
20
2²2 + 2(k + 1) 20)
1
-22 + 2k(2 20)
exp(
dd 5
exp(
Jdz. (35)
0V21 2T
2
o
2n
20
17

---

Under review as a conference paper at ICLR 2023
Therefore, (1=n)*
M())) dz dz is non-inereasing w.r.t k. Given that ((471) [(2))
have one condition for the alternating convergence test, i.e., 2 j I_x u(z)( creasing w.r.t.
v(=)
) dz is de-
u(=)
Since (1=1) S u(2)( ((())
. S - Jdz - S expl プラ Jdz S
1 and lim lim (() O, we have another condition for the alternating convergence test, i.e.,
((2) y
lim
kK) (6)
u(=)(
da 0.
(36)
h 400
u(z)
Given that (1 9)a I u(=)( ((s) jk positive, and when & 2 |a] + 1, (2) and (x41)
have different signs, we know that when 2 La] +1, (1gg)) J u()) (1 dz and (1 M+ I
((() )+ have different signs.
Therefore, according the alternating series test, we can conclude that the first half in In(-) in Eq. 30 ie., (1 - 8)a Ex=o (z) Soo u(z) u(=)
v(2)) )&, is a convergent series.
Next, we prove that the second half in In(-) in Eq. 30 i.e. ga= Ja u(=) mf= ja is convergent series. We rewrite the series as WEz
Ex (1)
a
u(z)( u(2) ja-
(a dz
(1
(37)
k: 1-
u(2)
h=
Given that 20 = 1/2 + 0² (nnnnq
1), we have
2(a k) - (a 1)), = exp((a - in)n(q - 1)) =
1 1- 1--9a-k
exp
(38)
20²
Thus,
② ja-k q
+oc
u(z)(
v1z)
a dz 1
exp
2² + 2( k)(2 20)
Jdz
(39)
u(z))
2T 50
202
50
Since 2 - 20 2 0 for 2 E [20, too exp(
2(2-20)
< 1. We then have
20
400
22 2(
(k
1))(2 20) ddz=
expl
0 20
202
2(2 20)
-22 + 2(a
k)(2 - 20)
exp(
expl
}dz S
2m
202
20
+00
2
2(a k))2 20) Jdz
exp
(40)
0V 2T
20²
Hence, ( f u(=)(
a- k dz is non-increasing w.r.t. k. Given that ((42)) (()) we
u[=]
have one condition for the alternating convergence test, i.e., (g) 1 is decreasing w.r.t. k.
(1 ja-k p+o u(2)(
mi=) aa dzl
When a, (a=z)a= ft (==)( dz = ov2n Stt expl +2la- Jdz S 2
2
f+ too exp( के dd < because 2(a - k² - 20) S O when k > a. As a result, we have another condition for the alternating convergence test, Lee,
lim t0+
a
g a-
u(=)((
((2) ja j- - =0 u(z)
(41)
1:
Since (122) - f to u(>)( ((2) )a dz positive, and when 2 |a| + 1, (2) and
(4+1) have different signs, we know that when & 2 [a] + 1, (2 f u(2)( ((()) o dz and
(12,) (k++)))))
(k+1) fto u(=)( (o- dz have different signs.
18

---

Under review as a conference paper at ICLR 2023
Therefore, according to the alternating series test, we conclude that the second half in In(-) in Eq 30 Le., Ek (x) (1 q0= 1 u(z)( ((2) ja )o-k)
u(z)
is convergent series.
All in all, Eq. 30 is convergent.
The practical computation of (g) when a fractional number proceeds by computing I "(=)( ((a) dz and _ u(=)( m(2) (()))) ) with Eq. 31 and then plugging in the results into
the series Eq. 30 until convergence (Mironov al. 2019
C SYNTHETIC DATA DEFINED BY EQ. 8
According to (Dong et al. 2022). the synthetic data defined by 7 represented under the orthog-
onal basis & fe,, e2.... ed). Thus, need to transform the synthetic data back to the standard basis with Eq, g Here we explain how to compute the synthetie dataset defined by Eq, For each class c, we flatten and concatenate the data from Te into data matrix X. with [Tel rows and d columns. Each row of X. is a data sample with dimension d. We then compute the transformation matrix by QR decomposition, Le., X = Q. After that, we randomly sample M Gaussian noise samples (5c, MM from (0,, Ia) and compute M synthetic samples for class c by Eq. 8 i.e., 82, = Q, + [T. 2==1 Lej. where To { e} and Le, is also flattened. Finally, we reshape s into the original data shape. The synthetic dataset 1
E.T
J. 11))
15
10.0
10
7.5
MNIST
FMNIST
FMNIST
FMNIST
2.5
CIFAR
CIFAR
CIFAR
0.75 1.00
1.25 1.50
2,00
25
50
75
100
2000
4000
5000
9000
10000
07 [G 1.0-1.
1,2 1..-550 -5,7- 10000)
1. (6 1,0 - 10000)
(G 1,0 0- 1, 50)
Figure 1: The privacy budgets of NDPDC with different a, L, and
Dataset
Noise
Test Acc
DP budget
0' 2
96. 46% + 0.20%
(2.16, 9DD
0 3
95.89% + 0.07%
(1.32, 10 -J-
MNIST
4
95.59% = 0.20%
(0.95.10-55 S)DPP
0 5
94.96% = 0.19%
0 = 2
80.96% = 0.39%
(1.93, 10 "J-DP
3
79.43% + 0.46%
(1.19, 10 $)-DP
FMNIST
= 4
78.42% + 0.41%
(0.85, 5)-
0 = 5
77.81% + 0.39%
(0.67,
10-
0 = 2
47.93% = 0.43%
(2.36, 10-5).D
3
45.03% + 0.62%
(1.44,10-9)-0)
CIFARIO 10
0 = 4
42.73%
= 0.54%
(1.04,10-9)-DP
0 = 5
41.20% + 0.51%
(0.81,10-9)-DP
0 2
78.49%
1 0.42%
(0.17, 1017,10-)--DP
3
77.38%
+ 1.05%
(0.09, 10 10-
CelebA
0 4
76.46%
+ 1.32%
(0.07, 10 SJ-DP
0 5
76.22% + 0.75%
(0.05, 10 -D
Table 8: The performance of NDPDC with variety of DP budgets.
19

---

Under review as a conference paper at ICLR 2023
Original images.
(b) DM generated synthetic images (with random initialization).
(c) DP-Shnnhorn generated synthetic images
(d) DP-MERF generated synthetic images.
(e) LDPDC generated synthetic images.
(1) NDPDC generated synthetic images.
Figure 2: Visualizing the synthetic CelebA images. Female synthetic images are listed in the first row, and male synthetic images listed in the second row.
20

---

Under review as a conference paper at ICLR 2023
(a) Original images.
(b) DM generated synthetic images.
(c) DP-Sinkhom generated synthetic images.
(d) DP-MERF generated synthetic images.
(c) LDPDC generated synthetic images.
(f) NDPDC generated synthetic images.
Figure 3: Visualizing the synthetic CIFARIO images.
21

---

Under review as a conference paper at ICLR 2023
D ADDITIONAL EXPERIMENTAL RESULTS
We visualize synthetic images generated by DM, DP-Sinkhorn, DP-MERF, LDPDC, and NDPDC in Fig. 2 and Fig. 3 Compared to DM-generated images, NDPDC-gemerated images more noisy due to the DP guarantees. A surprising result is that DDPDC-generatee images look like noise but the models still learn some information from LDPDC- images. We conjecture that this is because HBPDC-generated images still have certain patterns, but the patterns are hardly perceptible by human beings because of the high noise (a = vd).
We remark that, although the synthetic images generated by DP-Sinkhorn on CelebA look like faces, they are not very colorful and not diverse. Therefore, when being tested on the colorful and diverse original CelebA images, the model trained on NDPDC-generated images has better accuracy than the model trained on DP-Sine Sinkkinnhrr generated images.
Dataset
Test Acc
DP budget
MNIST
86.70% 2.07%
(11.60, 10-9)-DP
FMNIST
70.38% 0.79%
(11.60, 10-9)-DP
CIFARIO
20.61% 0.87%
(11.60, 10-9)-DP
CclebA
69.51% = 1.69%
(11.60, 10
The performance of DP-MERF with o = 0.5. We employ 50 synthetic samples per class Table 9:
train the ConvNet models for evaluation.
Beyond the visualization results, we report the results of NDPDC with high o and low DP budgets in Table 8
We set a set 0.5 and report the results of DP-MERF (Harder al. 202T) in Table 9 We also evaluate DP-HP using Vinaroz et al. (002)'ss 's publicly available code MNIST and FMNIST in Table 10
and report the results on
Datasct
Test Acc
DP budget
MNIST 74.20% + 1.66%
(1, 10 DD
FMNIST 28.05% + 1.12%
(1, D)-D-PP-PPPP
Table 10: The performance of DP-HP. We follow the instructions and run the code from https::///// github. com/ Pttp//aaaaaabbD----PPP -P to generate synthetic data. We employ 50 synthetic samples per class to train the ConvNet models for evaluation.
E EXTENDED RELATED WORK
Generative Methods The previous literature has proposed an array of generative methods for synthetic data generation (Kingma & Welling 2013 Goodfellow et al. 2014 Mirza & Osindero
2014 Higgins et al.) 2016; Arjovsky et al. 2017 7 Brock et al. 2018). Due to the growing privacy concern, recent research also focuses developing differentially private generative methods (Xie
ct al. 2018 Jordon et al. 2018 Torkzadehmahami et al. 2019 Long et al. 202T). Xic et al. a (2018)
first combined DP- SPD and GAN to generate private synthetic data. Torkzadehmahani et al. (2099)
combined conditional GAN and DP-SGD to generate class-conditional private data. pordon et al.
(2018) applied PATE (Papernot et al. 2016) to GAN and developed a differentially private GAN framework called PATE-GAN, PATE-GAN trains a student discriminator on the labels output by the PATE mechanism and trains the generator on the generative loss computed over the student discriminator. (Long et al. (021) proposed a framework called G-PATE with a private gradient ag- gregation mechanism to enable better combination of PATE and GAN. GS-WGAN (Chen et al., 2020) proposed to selectively apply the randomized mechanism in DP-SGD to maximally preserve the true gradient direction and use the Wasserstein objective to improve the amount of gradient in- formation flow during training the generative models. DP-MERF (Harder et al., 2021) proposed to train the generator by matching the mean embeddings of the real data and the generator-output
22

---

Under review as a conference paper at ICLR 2023
synthetic data. The main differences between DP-MERF and NDPDC include (i) NDPDC uses neu- ral network based feature extractors to compute the representations, while DP-MERF uses random Fourier features to compute the embeddings; (ii) NDPDC directly optimizes on the synthetic data, while DP-MERF optimizes the generative model parameters; (iii) NDPDC and DP-MERF apply the Gaussian mechanism in different way. OP-Shinkhorn (Cao al. (02T framed the generative learning problem as minimizing the optimal transport distance and trained the generative models using semi-debiased Sinkhorn loss. CCa al. (2021) demonstrated that, using (10, 10 --DP budget, DP-Shinkhorn can generate synthetic data with better utility and quality than G-PATE and
GS- GS-WGAN on MNIST and FNShi
Differential Privacy In addition to DP and RDP, the prior research has proposed some other dif- ferential privacy notations, such as Concentrated Differential Privacy (CDP) (Dwork & Rothblum 2016), zero CDP (Bun Steinke| 2016), and truncated CDP (Bun et al. 2018). CDP (Dwork & Rothblum 2016 is a relaxation of Dn-An algorithm obeys (1,, TP if privacy loss random variable has mean J4, and its deviation from lr is subgaussian with standard т. Zero CDP (Bun) & Steinke, 2016) is alternative formulation of CDP, and truncated CDP is relaxation of zero CDP. Beyond proposing new notations for enhancing privacy analysis, the prior literature also stud- ied privacy amplification by (sub)sampling, which was first proposed in (Kasiviswanathan et al., 2011 Beimel et al. 2013). The randomness introduced by sampling benefits the analysis in (Bassily al.
2014 Foulds et al., 2016). Recently, |Wang et al. (2019); Mironov et al. (2019) studied the (sub)sampled Gaussian mechanism-a combination of subsampling and the Gaussian mechanism and delivered privacy analysis under the framework of RDP. We follow Opacus (Yousefpour al.,
2021] to exploit (Mironov et al.
2019)'s 's results in our proof and experiments and provide detailed
convergence analysis for (Mironov al. 2019)ss 's computation method.
F ADDITIONAL DISCUSSION
Additional Discussion on LDPDC and DPMix Similar to LDPDC, DPMix (Lee et al. 2019) is a linear algorithm for differentially private data generation. However, there are some differences between LDPDC and DPMix:
1. LDPDC does not need to randomize the labels with the help of the parallel composition law, but DPMix needs to randomize the labels. We note that adding noise to the labels may hurt the model performance.
2. LDPDC adds noise to the sum of samples and divides it by the fixed group size L. while DPMix directly adds noise to the mean of the samples. For LDPDC, dividing the random- ized result by the group size L could help dilute the negative effects of random noise on model performance. Actually, we find that, for LDPDC, if we directly add noise to mean of samples like DPMix, the performance of LDPDC will become much worse.
3. DPMix uses sampling without replacement, while LDPDC uses Poisson sampling. Note that Poisson sampling is the standard sampling method used in the state-of-thh--a Pytorch library for differentially private deep learning YYousefpour et al., 202T).
We have reproduced DPMix and observe that LDPDC has better performance than DPMix with the settings for dataset condensation. Specifically, we set ox = σy = 1, L = 50, and M = 50, the result that we reproduce for DPMix only 10.22% + 1 1.23% on CIFARIO. We conjecture that this may be because (i) The operations of adding noise to the labels and the mean of the samples in DPMix cause more negative effects on model performance, compared to LDPDC. (ii) DPMix may be only able to use a large number of synthetic samples to achieve the results reported in (Lee et al.) 2019) (iii) There are some missing details in the published version of (Lee et al.) 2019) that may affect the effectiveness of DPMix. If we instead refer to the results reported in (Lee et al. 2019), also observe that LDPDC can use lower DP budgets to achieve comparable performance to DPMix.
General DP Data Generation vs. DP Dataset Condensation There is a major difference be- tween general DP data generation methods and DP dataset condensation methods: General DP data generation methods typically target at training generative models to generate new synthetic data samples, while DP dataset condensation methods aim condense the original dataset into small
23

---

Under review as a conference paper at ICLR 2023
synthetic dataset and maintain the data utility for training models. To achieve the respective goals, DP generative methods optimize the generative model parameters, while NDPDC directly optimizes the small synthetic dataset. Thus, DP data generation methods may be more useful for generating new data samples with the learned generators, but DP dataset condensation is more useful for data- efficient learning (Zhao & Bilen 2021a Zhao al. 202T Zhha & Bilen 202Tb). This is because DP dataset condensation significantly reduces the cost of data storage and model training, and the models trained on small amount of data produced by DP dataset condensation methods have better utility than the models trained on small amount of data generated by DP generative methods.
Practical Use of DP Dataset Condensation useful and practical application of DP dataset condensation methods is: Data owners with privacy concerns could condense their datasets into small synthetic datasets by DP dataset condensation methods. With DP protection, the data owners would feel more comfortable to share the synthetic datasets with other users devices. Even if some users or devices do not have much computational resource or storage, they could store the small synthetic datasets and train models with not bad utility. The data owners could also share their data with trusted entities such as governments, hospitals, or banks. To mitigate the data owners' concerns, the trusted entities execute DP dataset condensation methods the collected data and share the small synthetic datasets with other users or devices. In this application, DP dataset condensation is better choice than general DP data generation methods since the models trained on the small synthetic datasets produced by DP dataset condensation methods have better utility than the models trained on the data generated by DP generation methods.
24


Reviews:
[{"review_id": "plurI5MlMQS", "reviewer": "Reviewer_Spfc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper first discusses the issues in the controversial assumptions in a recent literature. Then it proposes two differentially private dataset condensation algorithms LDPDC and NDPDC. In the experiment, it makes the evaluations on multiple datasets and the results show that the proposed two methods achieves better privacy-utility trade-off than baselines.", "summary_of_the_review": "I appreciate this work studies the dataset condensation with differential privacy. However, because of the missing discussion and comparison with [1], the novelty and result significance are doubt. Therefore, I recommend reject.", "strength_and_weaknesses": "**Strengths**\n1. The experiment results of two proposed methods show the promising improvement from the baselines.\n\n**Weakness**\n1. My major concern is that this paper misses an important and relevant literature [1], which might influence the novelty and significance of the results. The algorithm in [1] is similar to Algorithm 1 in this paper. The slight difference is that in this paper, the data batch is sampled by Poisson sampling, while [1] samples the data without replacement. Moreover, it is questionable how much improvement LDPDC and NDPDC have by comparing them with this literature.\n2. The main experiment results could be more convincible if different algorithms can be compared with the (mostly) fixed DP-Budget. It is also worth showing at which $epsilon$ the performance of NDPDC would break down. They will help understand the comparison with the baselines. They are also convenient for later work to build the comparison with this work.\n3. The writing of this paper can be improved. Below some clarity questions or suggestions are listed:\n - The abbreviation \"DM\" is not introduced.\n - The definition of $T_c$ is introduced in page 5, but appears first in page 4.\n - The number of iteration $I$ is not mentioned in the Algorithm 2.\n - Missing the description of whether the feature extractor $\\phi$ is pretrained.\n - Missing the description of data augmentation in Algorithm 2.\n - What is the privacy budget setting for Table 2\n - Which column is the \"ConvNet\" mentioned in the second paragraph of section 4.2\n\n[1] Lee, Kangwook, et al. \"Synthesizing differentially private datasets using random mixing.\" 2019 IEEE International Symposium on Information Theory (ISIT). IEEE, 2019.\n\n\n--------After Discussion-------\nGiven that the difference between [1] and LDPDC is clarified, I raised my score to 6. I recommend authors to add the discussion and solve the clarification questions in the revision.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "R7YJxidgI6v", "reviewer": "Reviewer_kpgg", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Paper proposes differentially private dataset condensation, and improvement over the ICML'22 work [1], and shows that the proposed method provides good utility.\n\n[1] Dong, T., Zhao, B., & Lyu, L. (2022). Privacy for Free: How does Dataset Condensation Help Privacy?. arXiv preprint arXiv:2206.00240. ", "summary_of_the_review": "I like the proposed method, and assuming the proofs are solid, I have no problem accepting it to the conference.", "strength_and_weaknesses": "Paper proposes a differentially private version of dataset condensation and proposes two DP methods, linear and non-linear differentially private dataset condensation. Proposed methods claim to avoid the pitfall of [1], and provide formal privacy guarantees. \n\nEmpirical evaluation shows that the proposed DP methods perform better than DP-sinkhorn and DP-MERF, and provide tighter privacy guarantees. \n\nOverall, I like the paper. I have not checked the proofs in detail, assuming they go through, the proposed methods are potentially useful. I think a brief discussion on the utility and use of DP data condensation methods vs general DP data generation would be useful.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "AYyOBbN77Fg", "reviewer": "Reviewer_gV1f", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a data condensation algorithm that guarantees differential privacy, and demonstrated empirically that the proposed algorithm works better than existing data condensation algorithms.", "summary_of_the_review": "The general idea seems interesting, but I wasn't able to understand Algorithm 2 to judge the correctness of privacy.", "strength_and_weaknesses": "Strength: The idea seems interesting and the empirical results seem good.\n\nWeakness: I'm quite confused about how the algorithm works.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject