Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Authors: Clément Pierquin
Aurélien Bellet
Marc Tommasi
Matthieu Boussard
Venue: ICML 2025 poster (2025)
Keywords: Differential Privacy
Synthetic Data
Primary area: social_aspects->privacy
TL;DR: Releasing synthetic data and keeping its generation model hidden could lead to better privacy guarantees, as demonstrated in our study on linear regression.

Abstract: Synthetic data inherits the differential privacy guarantees of the model used to generate it. Additionally, synthetic data may benefit from privacy amplification when the generative model is kept hidden. While empirical studies suggest this phenomenon, a rigorous theoretical understanding is still lacking. In this paper, we investigate this question through the well-understood framework of linear regression. First, we establish negative results showing that if an adversary controls the seed of the generative model, a single synthetic data point can leak as much information as releasing the model itself. Conversely, we show that when synthetic data is generated from random inputs, releasing a limited number of synthetic data points amplifies privacy beyond the model's inherent guarantees. We believe our findings in linear regression can serve as a foundation for deriving more general bounds in the future.

Privacy Amplification Through Synthetic Data:
Insights from Linear Regression
Clément Pierquin 12
Aurélien Bellet
Mare Tommasi? Matthieu Boussard'
Abstract
ularly relevant for differentially private generative models (Zhang et al., 2017a; Xie et al., 2018; McKenna et al., 2019; Jordon et al., 2019; McKenna et al., 2021; Lee et al., 2022; Dockhorn et al., 2023; Bie et al., 2023), where the synthetic data they produce inherits the same privacy guarantees as the model itself.
Synthetic data inherits the differential privacy guarantees of the model used to generate it. Addi- tionally, synthetic data may benefit from privacy amplification when the generative model is kept hidden. While empirical studies suggest this phe- nomenon, a rigorous theoretical understanding is still lacking. In this paper, we investigate this question through the well-understood framework of linear regression. First, we establish negative results showing that if an adversary controls the seed of the generative model, single synthetic data point can leak as much information as releas- ing the model itself. Conversely, we show that when synthetic data is generated from random in- puts, releasing a limited number of synthetic data points amplifies privacy beyond the model's inher- ent guarantees. We believe our findings in linear regression can serve as a foundation for deriving more general bounds in the future.
Empirical studies, however, suggest that synthetic data may offer even stronger privacy protection than the theoretical guarantees provided by the model (Annamalai et al., 2024), This suggests that certain structural properties of the data or the generative process itself could contribute to an implicit privacy amplification effect. One possible intuition is that the privacy leakage might be reduced when the number of released synthetic data points is "small" relative to the complexity of the generative model. However, to the best of our knowledge, existing work has formally established the existence of such a privacy amplification effect, and a rigorous quantification of differential privacy in synthetic data release remains an open question.
To address this gap, this paper takes an initial step towards developing theoretical framework for quantifying privacy in synthetic data release. We focus on the well-studied set- ting of (igh-dimensional) linear regression trained via least-squares objective as simple case study. This model has the advantage of being analytically tractable but suffi- ciently expressive to capture phenomena observed in more complex models- as double descent in overparam- eterized regimes (Hastie et al., 2022) and, more recently, model collapse in generative AI (Dohmatob et al., 2024; Gerstgrasser et al., 2024).
1. Introduction
Differential privacy (DP) (Dwork and Roth, 2014) has be- come the gold standard for peeecy-preserving data analysis. Training machine learning models with DP guarantees can be achieved through various techniques: output perturbation (Chaudhuri et al., 2011; Zhang et al., 201 Lowy and Raza- viyayn, 2024), which adds noise to the non- non-private model; objective perturbation (Chaudhuri et al., 201 I; Kifer et al., 2012; Redberg et al., 2023), which introduces noise into the objective function; and gradient perturbation, which injects noise into the optimization process, as in DP-SGD (Song al., 2013; Bassily et al., 2014; Abadi et al., 2016; Feldman et al., 2018). Once trained, the model can be safely released, with its privacy guarantees extending to all subsequent uses thanks to the post-processing property of DP. This is partic-
We rely on the f-Differential Privacy (f-DP) framework (Dong et al., 2022), which provides a flexible and robust approach to privacy analysis, allowing precise characteri- zations of privacy guarantees through trade-off functions. When these trade-offs functions are difficult interpret, also express privacy guarantees in the Rényi differential privacy (RDP) framework (Mironov, 2017).
'Craft AI. Paris, France Université de Lille, Inria, CNRS, Centrale Lille, UMR 9189 CRISIAL, F-59000 Lille, France Inria, Université de Montpellier, INSERM. Correspondence to: Clément Pierquin <clement, celement.picrquine @ ai.
Our results are two-fold. First, in Section 3, we present negative results in scenarios where an adversary controls the seed of the synthetic data generation process. Specifi- cally, we show that the adversary can leverage this control to achieve privacy leakage equivalent to the bound imposed by post proceesnnns the model using only single synthetic
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
sample. Second, in Section 4, we analyze the privacy guar- antees when synthetic data is generated from random inputs to private regression model obtained via output perturba- tion. We demonstrate that privacy amplification is possible in this setting, depending on the model size and the number of released synthetic samples. All proofs can be found in the supplementary material.
more favorable when only a few samples are released.
Our results relate to the concept of privacy amplifica- tion (Balle et al., 2018; Feldman et al., 2018; Erlingsson et al., 2019; Cyffers and Bellet, 2022), which leverages the non-disclosure of certain intermediate computations to strengthen the privacy guarantees of existing mechanisms. We note that the form of amplification we study in the con- text of synthetic data release differs from privacy amplifi- cation by iteration (Feldman et al., 2018). In that setting, the final model is released after private training. In contrast, our approach withholds the model entirely and releases only synthetic data generated from random inputs to the model, introducing an additional layer of privacy protection.
Our findings highlight the critical role of the randomness given as input to the model, which must remain concealed from the adversary in order to enable privacy amplification. While the practical impact of our results is limited, we believe they offer valuable insights and lay the groundwork for a deeper understanding of synthetic data privacy in more complex machine learning models.
We conclude our discussion of related work by mentioning recent study that shows synthetic data can satisfy differ- ential privacy guarantees without formal guarantees for the generative model itself (Neunhoeffer et al., 2024). However, this work is limited to simple model where the private training data is one-dimensional, and the synthetic data is generated from a Gaussian distribution with mean and vari- ance estimated from the private data. In contrast, our paper addresses a different, more complex problem: we investi- gate the privacy guarantees associated with releasing the output of a differentially private model, specifically linear regression. In our case, we directly model the distribution of the output of linear regression for a random seed, which corresponds to a product of Gaussian matrices.
Related work. To the best of our knowledge, existing meth- ods for differentially private synthetic data generation rely on learning differentially private generative model (Hu et al., 2024).. Early approaches focused on marginal- techniques for tabular data, where a graphical model such as a Bayesian network- privately estimated from data and then used to generate new samples (Zhang et al., 2017a; McKenna et al., 2019; 2021). More recent methods ex- tend to other data modalities, leveraging expressive neural network-based generative models like GANs and diffusion models trained with differentially privacy (Xie et al., 2018; Jordon et al., 2019; Lee et al., 2022; Dockhorn et al., 2023; Bic et al., 2023). A key advantage of neural networks is the availability of general differentially private training algo- rithms, such as DP-SGD (Abadi et al., 2016) and PATE (Pa- pernot et al., 2017), which can be applied across various generative models. Crucially, all these methods rely on the post- post-processing theorem to ensure the privacy guarantees of the generated synthetic data-but it remains unclear whether this guarantee is tight or potentially overly conservative.
2. Background & Preliminaries
2.1. Differential Privacy
In this section, we give brief background about the tech- nical tools we use from the differential privacy literature. Here and throughout, M denotes randomized mechanism, and we say that two datasets 'D and D'' of fixed size m are adjacent they differ in a single data point.
In principle, one could deviate from this dominant approach by adding noise directly to the data generated by a (non- private) generative model. In such cases, the overall privacy loss would scale with the number of released data points due to the composition property of differential privacy. However, this approach would require strong and often unrealistic as- sumptions about the data. Most critically, it would lead to significant utility loss- partreruulllllly for high-dimensional perceptual data such as images, where even small perturba- tions can severely degrade semantic content and downstream performance. To our knowledge, no successful applications of this approach have been demonstrated in practice.
Rényi Differential Privacy (RDP) is a variant of DP which quantities the privacy guarantees in terms of Rényi divergence between M(D) and MM(D') (Mironov, 2017). Formally, for a > 1, let (P, =
T log Ee-.P (P()) be the Rényi divergence of order a between distributions P and Q. By abuse of notation, if V. ~ P, W Q, we will write D, (V, W) D., Q). For > 0, mechanism M is said to satisfy (a, sa.s)-RDP if, for any two adjacent datasets D and D', we have:
Interestingly, our results in Section suggest that differ- entially private generative models may offer the best of both worlds: the post-processing guarantee, which strictly bounds the privacy leakage when releasing large number of samples, and simaltaneously privacy guarantee that scales with the number of released data points, which is
Da(M(D)) S.c.
Trade-off functions and f-DP. Trade-off functions (Dong et al., 2022) capture the inherent trade-off between type I and type II errors of hypothesis tests that distinguish between outputs generated from two adjacent datasets. Let P and Q
2

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
be two distributions and consider the following hypothesis testing problem:
established by post-processing. even with just a single data point. In other words, no privacy amplification occurs der this scenario. These negative results underscore the vulnerability of synthetic data generation mechanisms to adversarial manipulation.
H1 the distribution is P vs Hg : the distribution is Q.
For a given rejection rule & E [o. 1]. the type error is [p[ø] and the type II error is [o] Then, the trade-off function T(P, Q) is defined as:
3.1. Output Perturbation
We begin with models trained with output perturbation. We make the assumption that each element (I,, (1) of the dataset satisfies the following property: ||æ S M2 and |Bll I My. where || denotes the Frobenius norm. These hypotheses are standard in private linear regres- sion (Wang, 2018). Denoting the fz-regularized least- square objective as F' (w;; D) = = E 2km || 2ill + À |o/l we know from (Chaudhuri et al., 2011) that D ト arg min Fx(w; D) has bounded sensitivity A 2L/m>, where L = M2 + M2 + XMs and Mg is the upper bound of the Frobenius norm of the min- imizer of Fxx, always bounded for ridge regression. We denote the output perturbation mechanism by M(D) arg mil Fx(w; D) + ag,, where Nij sid ~ NV 1). For two adjacent datasets D and D', let arg minneeeeee Fx(w; D) and w² arg min Fx With some abuse of notation, we denote M(v*) M(D) and M(w") = MDD).
T(P, ())) in Eglø! Eplo] S a).
Again, by abuse of notation, V ~ P. W Q, we will write T(V, W)= = T(P. (.P.Q) Q).
Let f : [0.1] + [o. 1] be a decreasing convex function. mechanism .M said to satisfy f-Differential Privacy
(f-DP) if for any adjacent D, D', we have:
T(M(D),M(D)) 2
Gaussian Differential Privacy (GDP) (Dong et al., 2022) a special case of f-DP defined with Gaussian trade-off functions. For j 2 0, we define:
G = T(V(O, ((,,,
e²
Then, MM is said y- if it is Gr.-DP.
2.2. Linear Regression Setting
The exact trade-off function of output perturbation with the Gausian mechanism is well known (Dong et al., 2022):
Throughout the paper, we consider a multi-output lin- ear regression setting, where a dataset D = (X,Y) = ((11: ..),..., (Xm, Um)) consists of m labeled data points, with X E x the data matrix and E m=xm the label (output) matrix. Here, d denotes the number of features of the imput (private) data points, and n denotes the dimen- sion of outputs (i.e., the number of features of synthetic data points). A linear model is represented by parameters w E xxd and predicts y = wX.
inf M(w) = inf Gllnll/a = Gaaaau E ||--W||S
MERMXd, INISA
The RDP guarantees are also known (Mironov, 2017):
aA2
sup (a(M()). e
20
|e- SA
Due to translation invariance of trade-off function for Gaus- sian matrices and noting μ = -=' v², comparing M(V") and ((w)) is equivalent to comparing V = M(nxxa) and W = V + μ where μ is called the shift between V and W.
3. Releasing Synthetic Data from Fixed Inputs
In this section, we investigate the privacy guarantees of releasing synthetic data when the input to the generation process is fixed and chosen by an adversary. This represents a strong yet practically relevant threat model, encompassing situations such as when an adversary has access to an API that allows them to query the generative model.
We are interested in quantifying the privacy leakage of re- leasing the output of the model queried with a seed input. Formally, a seed is a vector 2 E IRd and we define the corre- sponding query to model v* (respectively w²) as v== E R. (respectively w²) Note that M(U*), )2 is a Gaussian vec- tor. Based on the derivation above and due to translation invariance of trade-off functions for Gaussian vectors, quan- tifying the privacy leakage then amounts to characterizing the trade-off function T(V z, Wz).
Focusing on linear regression, we consider two standard ways to train the model with differential privacy guaran- tees: output perturbation (Chaudhuri et al., 2011) and Noisy Gradient Descent (Song et al., 2013; Bassily et al., 2014; Abadi et al., 2016). In both cases, we show that when the adversary controls the seed of the generation process, they can induce privacy leakage that reaches the upper bound
It is clear that an adversary can recover the model param- eters x" from d queries (v" 21,..., u==,, 2a) by choosing, for
3

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
i E [1, [1, = (8tg) jj]. effectively probing each co- ordinate individually. This leads the maximum possible information leakage allowed by the post-processing upper bound. Strikingly, we now show that for some datasets, the adversary can in fact induce this maximal privacy leakage with just one query.
only differ in the labels (Ghazi et al., 2021). Formally, ad- jacent datasets under label DP can be written D ==X,Y) D' = Y"), where Y E R=xm and Y' E IR= differ in exactly one column (we say Y,Y are adjacent). Since any two datasets that are adjacent under Label DP remain adjacent under standard DP (where both features and labels can differ), the maximum privacy leakage under standard DP is at least as large. Our negative results for Label DP thus extend to standard DP.
By definition, W V2+ pa and therefore Wa is the result of shifting the distribution V2 by pzz, The norm of the shift between W² and V2 is thus ||ع||, while the norm of the shift between V and W is ||a|| We can compare, for a given shift μ and a given seed z, the trade-off functions of (V, W) and (Vz, z). We have T(V2, 2, W2) = G Gluee// /|| For a given shift between V and W, which is known by the adversary in the threat model of DP, the adversary can max- imize ||==||/||a|| by taking z to be the right singular vector corresponding the largest singular value o mma (11) of p.. We directly obtain that
Let V. = Wo E Raxd standard Gaussian initialization, F(w, N00,X,Y7 X) 1 E Lazz- yx + X A|[=| the objec- tive function, 17 > 0, a > 0 and (Ne)e a sequence of i.d standard Gaussian matrices of Raxd, On two adjacent datasets D = (X. Y), D' (X, Y"), NGD corresponds to the following updates:
V = V - v/V nn F(V. X,)) + / 2n
W4+1 = V. Y') + 22no
T(V2WWz) = Glomsse (1a)
Hence, for a hypothesis test between a particular instantia- tion of shift μ E Raadd the sensitivity of the exact trade-off function between V2 and Wa improved from ||/l to |mmax [mmax(p))//ra (p))/ However, these considerations do not imply better privacy guarantees than releasing the model parameters, as shown by the following result.
Note that V2 can be decomposed into independent Gaussian rows, and likewise for W,-
In the following, we focus on the case where the model trained until convergence (i.c., + oo) before querying it to release synthetic data finite-time analysis can also be done, see Appendix A.2). Our objective is thus to com- pare the trade-offs functions T(V>,, Wxo)-oor releasing the model directly-and T( z, Wso f releasing the output of the model on a query 2 E Rd.
Proposition 3.1. For any fixed z E Rd, there exist adjacent datasets D and D' such that:
T(V2, Wz) = TVV.
As a discretized Langevin dynamical system with a strongly convex, smooth objective, it is known that V converges in distribution to a limit distribution (Durmus et al., 2019), which is the Gibbs stationary distribution when r 0. We can leverage this consideration to characterize T(V W and TV W.... w.
In other words, for any possible query E Rdd there ex- ists two (pathological) adjacent datasets D, D' such that performing the query (D)) implies the same privacy leakage as directly releasing M(D).
Note however that our results show that, for a specific shift E Raxdd the sensitivity of the exact trade-off function between Vz and Wz is (1)) /og. which can be strictly smaller than the norm-based bound ||л||| /aa- This indicates that, from an empirical standpoint, the actual privacy leak- age may be lower than the worst-case upper bound implied by the post-processing theorem for realistic datasets.
- XI, M = I- 21/ Proposition 3.2. Let - E=
and denote by A the square root of M and B the square root of Σ - M1 Assume that Y and Y" are adjacent and that ( M2/ n) < 1. Then:
T(Vxo; Wxx) = G (IXAT
We provide the detailed proof and discussion about the choice of 2 in Appendix A.
T(Vo2, = Ti=Tg-iXTor YSI nol|sel
3.2. Noisy Gradient Descent
As in the output perturbation setting, the adversary aims to maximize the privacy leakage from a single data point. Thus, her objective is, for fixed pair of adjacent datasets D, D' to find supzer= T(V W 2) The following proposition quantifies the associated privacy leakage.
We now extend the previous results the case where the private generative model is trained with Noisy Gradient Descent (NGD) (Song et al., 2013; Bassily et al., 2014; Abadi et al., 2016; Feldman et al., 2018; Altschuler and Talwar, 2022).
Proposition 3.3. For any pair of adjacent datasets (in the label DP sense), the adversary can choose 2 E Rd such that:
Specifically, we present negative results in the context of La- bel Differential Privacy (Label DP), where adjacent datasets
T(Vso2, Wox)) = T(Vo,, Wxx).
4

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
This statement gives negative result similar to the one obtained for output perturbation (Proposition 3.1): releasing Voo does not offer any privacy amplification compared to releasing the model Vo in the worst case.
that ||v - w|l A. We note V = MM()) c + ag and W M( w + ag..
VZ and WZ are two distributions of a family that can be parametrized by the mean of the left Gaussian matrix in the product (u and w). We denote as P. the distribution of V Z and Pw the distribution of W Z. The trade-off function between V and W equal to:
We provide the detailed proofs of the above results and a discussion about the choice of z in Appendix A.3.
4. Privacy Amplification for Releasing Synthetie Data from Random Inputs
T(V =
1 (1- ( - 1| wll /0a),
where & is the c.d.f of a standard Gaussian variable.
Motivated by the negative results of the previous section, we now consider the case where synthetic data points are gener- ated by feeding random inputs into linear regression model privatized via output perturbation. This relaxed threat model reflects the common scenario where trusted party trains the generative model, generates 1 synthetic data points, and releases only these points points-without without revealing the generative model or the random inputs used in the generation process.
We can derive closed-form expressions for Po, as shown in the following lemma.
Lemma 4.1. (Distribution of V and WZ). The distribu- tion Py has the following characteristic function:
(t) exp ( tr(t"
uttF"oo" ov oo +14
det (4 + 2
Remarkably, we demonstrate that releasing synthetic data points provides stronger privacy guarantees than directly releasing the model when / < d, highlighting the key role of randomization in the privacy of synthetic data generation.
The proof can be found in Appendix B. For v = 0 and = 1, the distribution P. corresponds to a generalized Laplace distribution, which has the following density (Mattei, 2017);
4.1. Setting
As before, we consider the linear regression setting intro- duced in Section 2.2. We privatize the model via output perturbation, as in Section 3.1, which we recall is given by (D) = arg min (x; D) + N,N, where Nij std ((00 1). The difference is that the seeds Z E Rdxl used to generate synthetic data points are now Gaussian. More precisely, we consider the following mechanism.
2
|8||| =
||||| (2
Po(s)
ad T(d/2) Kay
where π is a constant, I is the Gamma distribution and a is the modified Bessel function of the second kind of order ايه However, to our knowledge, when v * O, the distribution P. does not correspond to any standard or well-studied distribution, and its density lacks a simple closed-form expression (Li and Woodruff, 2021).
Definition 4.1 (Synthetic data generation from random in- puts). Let D be dataset and M denote the output pertur- bation mechanism. Our objective is to analyze the privacy guarantees of the mechanism Mz(v)= = M( where ~ (0,00)).
4.2. Releasing a Single Point
Z E Rdx with Zij sid
The above observations suggest that the exact computation of T(V Z, W WZ) or D. Da W WZ) is likely intractable, if not impossible in general. In this section, we focus on the simplest case, where words, the input dimension is large, and we release single one-dimensional synthetic data point. In this special case, we can derive simple, non-asymptotic privacy bounds by leveraging a univariate variation of the Central Limit The- orem (CLT). Indeed, VZ E R. so we avoid complications related to dimensionality that arise in the multivariate CLT. As result, we obtain tighter bounds with better scaling in d than would be possible in the higher-dimensional case (n, l > 1). In contrast, multivariate non asn-asymio CLTs break down when the dimension of the random vector be- comes large- we discuss the applicability of our results in higher dimensions in Section 4.3.
For two adjacent datasets DD and D', we de- fine 2 = arg winne Fx (w;; D) and w* arg min wi Fw: D").
[ = 1, and d >>>>> 1. In other
The post-processing theorem (Dong al., 2022) ensures that we have:
M(M2()"),M(uu") T(M()"),
However, the post-processing theorem may not be tight for this mechanism, i.e., equality may not hold in the inequality above. In order to assess the potential privacy amplification phenomenon associated with this mechanism, we aim to compute, or at least estimate, T(M2 (t"M,("",,M)) M2(m)
Throughout the rest of the section, we let v, w E Boxd such
5

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Specifically, we observe that VZ can be decomposed into
Proposition 4.1. (Trade-off function between Gaussians with different variance). Let Ø1, 02 > 0. Then,
a sum of independent terms: VZ= = Ei VaZg, with Z (00 d2Ja). From there, we apply a central limit result to approximate VZ and W Z by Gaussian variables for which the trade-off function is known. The following lemma is essential to our reasoning.
Ti (a) if S 02 (2( else,
T(N(0.0)).
Lemma 4.2. (Approximate trade-off function). Let P.Q, P, Q four distributions of Rd. Let Y = max TV (P, P), TV(Q,Q) where TV denotes the total variation between distributions. Let (7, 1 7). Then, S T(P, ()
where Ti(a) = 24
01 +
1 - (11/22) - 11,
02
T2(a) = 2 24
- - + 11/2)
02
We denote this trade-off function by (())))))
We refer to Appendix B.2 for the proof. This lemma ensures that the non-asymptotic bounds of the CLT translate into bounds for the trade-off function. Moreover, we use the following theorem derived from (Bally and Caramellino, 2016) to establish convergence to the Gaussian distribution. Theorem 4.2 (Multivariate CLT asymptotic development in total variation distance (informal, adapted from Theorem 2.6. of Bally and Caramellino, 2016)). Let F = (Fi & be sequence of ii.d random variables in IR~ absolutely contin- uous with respect to the Lebesgue measure, with null mean and invertible covariance matrix C(F). Let G ~ NO, T.). 1/2 and S = va Ex_ A(F) Let r 2 2. 1i < +oo and all moments up to order r of F; agree with the moments of standard Gaussian F.v. in R.,, then:
We refer to Appendix B.4 for the proof. With these results, we can approximate the trade-off function of interest (corre- sponding to linear regression in the univariate output setting) by that of Gaussians, as stated in the following theorem.
Theorem 4.3. Let d > O. Then, there exists universal constant C >> O such that for all a E (C/d,1 1 C/d):
0
C
a
S T(VZ, (Z),),
0
d
Gx(oo//11)))) a -
C
+ d 2 T(VZ,W2)(0)
Let A(F) = C(F)-1/2
This theorem states that the trade-off function between V and W Z converges in (1/d) to a tradc-off function be- tween two Gaussian variables with different variances. Com- bining our bounds with the post-processing theorem, we have shown that:
(V. G) S C((+ [[L+EE[AA+* (IIAAt*))mmaN///... 1)/2
where C depends on r, N and C(F).
T(V2,W2) 2 max T(V,W), &A (.+ 9) c.
In the univariate case, this theorem takes a particularly sim- ple form given below.
Below, we will denote this lower bound by h. Figure 1 represents numerical computation of the upper bound.
Lemma 4.3. Let G ~ ~N(, 1). Then, there exists Allll > such that:
TV (ValooN+ +U),N+ u)z, /003 + ||wlpp
Appll d
Interpretation with Rényi divergences. Translating the convergence of the trade-off function into a formal privacy amplification bound is nontrivial. We can first examine the Rényi divergence between the limiting Gaussian distribu- tions. We denote vg (O, of divergence is maximized for e v, W, U, + A for some value e, which depends on d, A and oy (more details in Appendix B.7). Then, it can be shown that:
<
We have established that VZ and Z can be approximated by Gaussian variables, both with zero mean but different variance. In the univariate case and for large d, our syn- thetic data release thus transforms a mean shift between V and W as described by the relationship W = V + w v into a variance shift. The variance shift is captured by the approximation:
v²)). The Rényi
a
Da v2.)
o(d
4do
do || d + |laa1
WZ
VZ for d >>> 1.
This result yields two key insights. First, d co, nd is indistinguishable from vd supporting the idea that V becomes indistinguishable from WZ. Second, we have:
For conciseness, for x, y > O. we denote by A(ag, d, x, y) the pair +
Now, we need to com- pute the trade-off function of these Gaussian variables.
Dalvi,,ve F Da (V.
2d
6

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
10
For multiple values of d and A, we first determine e and C2. Then, we estimate la (h) using a Monte Carlo approxi- mation:
T.F:W:
Gupo fou + Cjj0- - C/d Lower bound on TVV W2)
la(h) R L(a - 1)
log ((x)) k=1
0.-
Type
where (Xx)a21 sid Unif((O, 1J) and I. 10 is the number of samples. We run the procedure M = 50 times, and the estimates are averaged. Figure 2 reports the logarithm of the estimated divergence as a function of log(d) for mul- tiple values of A. Standard deviations are not shown as they are negligible compared to the estimated values. The results suggest a convergence rate la (h) = O(1/d) in the high privacy regime A < 1. The initial plateau observed for small d arises from limitations in our analysis. Specif- ically, it reflects conservative constants in Lemma 4.3 and the worst case- apsssopppooiitiionn of trade-off functions of The- orem 4.3, rather than an intrinsic property of the divergence itself. More details about the experiments can be found in Appendix B.7.
0.
0.2
02
0.4
1.0
Type error
Figure 1. Comparison of the lower bound on 7(VZ, 2) to T(V, W) and C. {a + + - for C 1, 1,0
1, = 12.
This comparison with the post-processing upper bound (V,V, W) suggests a privacy amplification of order ((1/d) in the asymptotic regime. However, this observation alone does not suffice to conclude that Da Z, W Z) = (11/d). The difficulty arises from the fact that the ((1/d) conver- gence rate of the lower bound h on the trade-off function does not directly imply a corresponding convergence rate for the Rényi divergence between the original Gau--aass)n distributions.
0.3
Log of estimated Rewi diverggoooo
0.6
-2
-3-
-4-
We thus numerically approximate D., (V 2)) using i to gain more intuition. This is done via the following conver- sion result from Dong et al. (2022).
-6
Proposition 4.2 (Conversion from f-DP to RDP (Dong et al., 2022)). If a mechanism f-DP, then it is (f)) RDP for all a with:
- log [f(( ifz =
log(d)
(f())
+00 else,
Figure 2. Privacy amplification in Rényi DP when releasing sin- gle point: estimation of D. (VZ, WZ) as a function of log(d) for different values of A.
0) with 2y = inf(t E (0, f(t = 0) 1.
While is difficult to theoretically compute h, for d large enough, there exist c1 C2 < such that:
4.3. Releasing Multiple Points
(() if (0,c) ( h(a)= ((a)ifae (2),
We now consider the more general case where 2 syn- thetic data points in dimension n 2 1 are released. In this case, the adversary can leverage correlations between the different outputs to better reconstruct V or W and thus yield higher privacy leakage. In fact, the elements of V are not independent. This means that we cannot directly leverage the results of the previous section and apply composition theorems to obtain an approximation of the trade-off func- tion T(V Z, W W).. However, VZ can be vectorized and
where ā(a) GAira.d,a) (a + 9) C. This matches the numerical representation in Figure 1. Working with h rather than ğ alone is essential, because 2 < 1 implies (ō) = +oc yielding no meaningful RDP guarantee. In contrast, la remains finite, allowing us to derive valid bounds.
7

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
decomposed into sum of independent vectorized matrices: 2)) = E vee(V., Ex), where V. is the k-th col- umn of V. Then, we can apply Theorem 4.2 for random vectors and expect the distribution of vec(VZ) E TR to converge Gaussian. However, the constants in Theo- rem 4.2 depend on the dimension of vee V 2), here N = nl. To our knowledge, no multivariate central limit theorem cur- rently provides total variation distance bounds with explicit constants yet. Raič (2019) studied Berry-Esseen bounds for the central limit theorem and obtained universal constants equal 42N1/4 + 16, which become uninformative when N is larger than some power of d.
By Theorem 4.4, we can approximate -_ as Gaus- sian matrix vd sG. Using the triangle inequality for the TV distance:
TV (N HN
< TV H,
(I)
+ TV Vdd H, H, SG +E
(2)
Using independence in the decomposition and the post- processing theorem, we have:
A recent work solved this issue in the special case of the product of i.i.d Gaussian matrices.
nl
(1) TV
= <OV d-s
Theorem 4.4 (Convergence of product of Gaussian matrices (adapted from Theorem of (Li and Woodruff, 2021)), Sup- pose that d 2 (nxx,n.)) 1} and N E Rnxd Z E Rdxi G E Raxt are standard Gaussian matrices. Then, there exists
Also, (2) can be seen as the total variation distance between the convolution of two distributions by third one. We use Pinsker inequality to relate this TV distance to KL divergence. Then, we define a random variable W and write: G = G + W + H W. Using the post-processing inequality, the chain rule and convexity for KL divergences, we obtain:
C > 0 such that:
nd
TV(NZ, VdG) S VV
DKL(Vd- 8G EZ vd Vd- H)
This theorem must be adapted to our case, where N is shifted by some matrix v. The following theorem estab- lishes convergence even the presence of a shift u that induces dependence between N and vZZ. complicating the analy- sis. We provide a non asymptotic upper bound on the TV distance between (a + Z and a Gaussian matrix. Strik- ingly, our bound does not depend on the norm of the shift
<DKL(EZ' + W)
+Bw- #Bw-WIDKL(VC (DRLIDdVVV SG W, Vd vd- sG]].
Setting W Ei N. we D2I(2Z + +W, H) 0 and:
nls
DRL(Vd- sG + EZ' Vd H) 2 2(d - s)
Theorem 4.5. (Convergence of product of Gaussian matri- ces, shifted version). Let N E Baxd ZZ E Rdx G e Raxl be independent standard Gaussian matrices. Let rank(o). Assume that d 2 max(n,I}. Then, there exists C' > 0 such that:
This concludes the proof.
This theorem allows to recover privacy amplification re- sults in the multiple outputs scenario. By abuse of notation, for G E Raxi Gaussian matrix independent of Z, we de- note G (Good-n..,.)) = T(oavd - nG + vZ, aa d - nG + w Z).
nds TV ( (looN+u) sG +z) S CC' d-s'
Sketch of proof (details in Appendix B.6): For simplicity, we set σg = 1. The idea of the proof is to use the SVD of u FEST and use the invertibility of F and S and the invariance of Gaussian matrices by orthogonal trans- formation to write TVN + v)2, v -G= sG + vZ') = TV((N + Σ) Vd - SG + ΣZ") and observe that for d> max (n, 13. Σ- = (Ai,..., Xx, O, .,......
Theorem 4.6. Let d > 0. Then, there exists a universal
constant C" 0, Cni,d C'n d-n L such that for all a (C 1- Cn,Ld):
G(rooddn,,,,)) (a + Cu.Ld) Cn,.dd S T(VZ, (a) G(ondd-n), (a Cn,,d) + Cn. 2 (VZ, W (a).
nー e times
Combining our bounds with the post-processing theorem and denoting ğ(a) G(aa.d-n.. (a + Cn,1.)) Cn.,,d. we have shown that:
Then, we decompose (N + 2 into part that depends on the shift e and vanishes as > to0 and another part that we can approximate with a Gaussian matrix: H = Ein (N., + 2, and N N_ = Eh-s+1 1 N. Zu. and NZ = N_ + H. Note that N_ and H are independent.
T(V2,WZ) 2 max Max(T(V,
We note h this upper bound, with a slight abuse of notation.
8

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Interpretation with Rényi divergences. Leveraging Rényi divergences allows us interpret result both form of privacy amplification via synthetic data release and composition theorem for the "release one point" mechanism of Section 4.2, which valid when only a small number of synthetic points are released, i.c., max 1) I d.
that of directly releasing the model parameters. The result- ing guarantees are comparable in order those obtained by training the model non-privately and releasing nl noisy pre- dictions- individually satisfying differential privacy. However, as discussed in Section 1, directly adding noise to model outputs is undesirable, as requires difficult and often loose sensitivity analyses and often degrade utility. In contrast, although we privatize the model itself, we obtain bounds that resemble the composition of the "release one point" mechanism. It is important to note, however, that this convergence analysis holds only when d 2 max (n.1).
Similar to the case n 1, we can derive Rényi divergence privacy bounds for the limiting distributions in order to get some intuition about the relationship be- tween the parameters and the privacy loss. Denoting G, de ee - nG G da davdd nG+wZZ Da (Gu, Gw) can be upper bounded as follows (see Appendix B.7):
We believe that this behavior may hold in more general settings, but our proof techniques heavily rely on the con- vergence theorem of products of Gaussians. Unfortunately, there no hope to apply this technique in the "small d" regime, proven by Li and Woodruff (2021).
am/s?
Da (Gu, Gw) & 4(d - n
+ t(
Analogous to Section 4.2, G2 and G converge in distri- bution when d + +00. However, this time, there is a dependence in nl which behaves as a composition result of the "release one point" mechanism. Comparing to the post-processing upper bound (V W), we now have:
Theorem 4.7 (Non convergence of Gaussian product for small d. adapted from Theorem in Li and Woodruff, 2021). Let G1 E TRnxd G2 E [Rdxl G E RRxx be Gaussian matri- ces. Suppose that
d C" C"C"mmma mmx((n 12 min(n,1333
nl Da(Gu, S 2n 2(d-n)Da(Vi)) WV.
with C" an universal constant. Then:
TV(G, VaG) 2 2/3.
Following the same procedure described in Section 4.2, we numerically estimate the Rényi divergence between VZ and WZZ Z for various values of d. Figure suggests an approximate convergence rate of (dd-1/2) when I and n are fixed. More details about the experiments can be found in Appendix B.7.
5. Conclusion & Perspectives
We have shown that there exists privacy amplification phe- nomenon for synthetic data in the context of linear regres- sion. However, there is no amplification when the adversary has control over the seed of the synthesizer.
Value
This negative result could inform the development of tighter privacy auditing strategies for synthetic data release (An- namalai et al., 2024). By quantifying the degradation in privacy guarantees, our findings offer insights that can help design more robust auditing methods in adversarial settings.
0.3
Log of estimated Reayi divergrace
0.6
Several important directions remain for future work, includ- ing deriving general privacy amplification bounds that hold when n, 1 are large or d is small. A complete investigation of privacy bounds for more advanced privacy preserving algorithms such as Projected Noisy Gradient Descent or DP- SGD, for fixed and random output settings, is also essential. Finally, extending our analysis to more complex models such as neural networks a crucial step toward making these theoretical results applicable to real-world scenarios.
logid)
Figure 3. Privacy amplification in Rényi DP when releasing mul- tiple points (I = 10, n 1): estimation of D., (V WZ as function of (d) for different values of A.
Impact Statement
This paper presents work whose goal is to advance privacy in machine learning, offering tools to make it more secure. Private synthetic data generation is recognized as promis- ing approach for enabling flexible yet privacy-preserving
Discussion. When d is sufficiently large, the privacy loss incurred by releasing nł synthetic data points lower than

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
analyses. Studying privacy amplification phenomena in this context is valuable because it allows for tighter quantifica- tion of privacy guarantees, thereby strengthening protection. Moreover, it assists data curators in designing more effective privacy-preserving algorithms.
Dong, J., Roth, A., and Su, W. J. (2022). Gaussian differ- ential privacy. Jourmal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3377.
Durmus, A., Majewski, S., and Miasojedow, B. (2019).
Analysis of langevin monte carlo via convex optimization. Journal of Machine Learning Research, 20(73):1-46
References
Dwork, C. and Roth, A. (2014). The algorithmic founda- tions of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3 4):211-407.
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., and Zhang, L. (2016). Deep learning with differential privacy. In CCS.
Erlingsson, U., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., and Thakurta, A. (2019). Amplification by shuffling: From local to central differential privacy via anonymity. In SODA.
Altschuler, J. M. and Talwar, K. (2022). Privacy of noisy stochastic gradient descent: More iterations without more privacy loss. In NeurlPS.
Annamalai, M. S., Ganev, G., and Cristofaro, E. D. (2024). "what do you want from theory alone?" experi- menting with tight auditing of differentially private syn- thetic data generation. In USENIX Security 24, pages
Feldman, V., Mironov, I., Talwar, K.. and Thakurta, A. (2018). Privacy amplification by iteration. 2018 IEEE
59th Anmual Symposium on Foundations of Computer Science (FOCS), pages 521-532.
Gerstgrasser, M., Schaeffer, R., Dey, A., Rafailov, R., Sleight, H., Hughes, J., Korbak, T., Agrawal, R., Pai, D., Gromov, A., Roberts, D. A., Yang, D., Donoho, D. L., and Koyejo, S. (2024). breaking the curse of recursion by accumulating real and synthetic data. CoRR, abs/2404.01413.
Balle, B., Barthe, G., and Gaboardi, M. (2018). Privacy am- plification by subsampling: Tight analyses via couplings and divergences. In Bengio. S., Wallach, H., Larochelle, H., Grauman, K., Ceea-BBianch N., and Garnett, R., edi- tors, tors, Advances in Neural Information Processing Systems, volume 31, Curran Associates, Inc.
model collapse inevitable?
Ghazi, B., Golowich, N., Kumar, R., Manurangsi, P., and Zhang, C. (2021). Deep learning with label differential privacy. NeurlPS.
Bally, V. and Caramellino, L. (2016). Asymptotic develop- ment for the CLT in total variation distance. Bernoulli, 22(4):2442
Hastie, T., Montanari, A., Rosset, S., and Tibshirani, R. J. (2022). Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2)9949 986.
Bassily, R., Smith, A. D., and Thakurta. A. (2014). Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds. In FOCS.
Hu, Y., Wu, F., Li, Q., Long, Y., Garrido, G. M., Ge, C., Ding, B., Forsyth, D., Li, B., and Song, D. (2024). SoK: Privacy- Preucc-Preserving Data Synthesis In 2024 IEEE Sym- posium on Security and Privacy (SP), pages 4696 4713, Los Alamitos, CA, USA. IEEE Computer Society.
Bie, A., Kamath, G., and Zhang, G. (2023). Private GANs, revisited. Transactions on Machine Learning Research. Survey Certification.
Chaudhuri, K., Monteleoni, C., and Sarwate, A. D. (2011). Differentially private empirical risk minimization. Jour- nal of Machine Learning Research, 12:1069-1109
Jordon, J., Yoon, J., and van der Schaar, M. (2019). Pate- gan: Generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations (ICLR).
Cyffers, E. and Bellet, A. (2022). Privacy amplification by decentralization. In AISTATS.
Kifer, D., Smith, A. D., and Thakurta, A. (2012). Private convex optimization for empirical risk minimization with applications to nigh-dimensional regression. COLT, volume 23, pages
Dockhorn, T., Cao, T., Vahdat, A., and Kreis, K. (2023). Differentially Private Diffusion Models. Transactions Machine Learning Research.
Dohmatob, E., Feng, Y., and Kempe, J. (2024). Model collapse demystified: The case of regression. In Advances in Neural Information Processing Systems, volume 37, pages 47979-47013 Curran Associates, Inc.
Lee, J., Kim, M., Jcong, Y., and Ro. Y. (2022). Differen- tially private normalizing flows for synthetic tabular data generation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7345-7353.
10

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Lehmann, E. and Romano, (2006). Testing Statistical Hypotheses. Springer Texts in Statistics. Springer New York.
in unbounded domain. In Conference on Uncertainty in Artificial Intelligence.
Xie, L., Lin, K., Wang, S., Wang, F., and Zhou, (2018). Differentially private generative adversarial network. arXiv: 182.:1802.00739.
Li, Y. and Woodruff, D. (2021). The Product Gaus- sian Matrices Is Close Gaussian. In Approximation, Randomization, and Combinatorial Optimization. Algo- rithms and Techniques (APPROX/RANDOM 2021), vol- ume 207 of Leibniz International Proceedings in Infor- matics (LIPlcs), pages 35:1-35:22.
Zhang. J., Cormode, G., Procopiuc, C. M., Srivastava, D., and Xiao, X. (2017a), Privbayes: Private data release via bayesian networks. ACM Trans. Database Syst., 42(4).
Zhang. J., Zheng, K., Mou, W., and Wang, L. (2017b). Efficient private ERM for smooth objectives. In IJCAI.
Lowy, A. and Razaviyayn, M. (2024). Output perturbation for differentially private convex optimization: Faster and more general. arXiv:2102.04704.
Mattei, P.-. (2017). Multiplying a gaussian matrix by gaussian vector. Statistics & Probability Letters, 128(C):67-70.
McKenna, R., Miklau, G., and Sheldon, D. (2021). Win- ning the nist contest: A scalable and general approach to differentially private synthetic data. Journal of Privacy and Confidentiality, 11(3).
McKenna, R., Sheldon, D., and Miklau, G. (2019). Gradhical-model based estimation and inference for dif- ferential privacy. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 4435- 4444.
Mironov, (2017). Rényi differential privacy. In 2017 IEEE 30th Computer Security Foundations Symposium (CSF), pages 263-275.
Neunhoeffer, M., Latner, J., and Drechsler, J. (2024). On the formal privacy guarantees of synthetic data. In Data Privacy Protection and the Conduct of Applied Research: Methods, Approaches and their Consequences. National Bureau of Economic Research.
Papernot, N., Abadi, M., Erlingsson, U., Goodfellow. J., and Talwar, (2017). Semi- comi-supervised knowledge trans- fer for deep learning from private training data. In ICLR.
Raič, M. (2019). A multivariate berry-esseen theorem with explicit constants. Bernoulli, 25(4A).
Redberg, R., Koskela, A., and Wang, Y. (2023). Improving the privacy and practicality of objective perturbation for differentially private linear learners. In NeurIPS.
Song, S., Chaudhuri, K., and Sarwate, A. D. (2013). Stochas- tic gradient descent with differentially private updates. In 2013 IEEE Global Conference Signal and Information Processing.
Wang, Y.-.. (2018). Revisiting differentially private linear regression: optimal and adaptive prediction & estimation

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
This appendix presents detailed proofs and additional discussion.
A. Proofs of Section 3
A.1. Proof of Proposition 3.1
Proposition 3.1. For any fixed 2 E IRd, there exist adjacent datasets 'D and DD' such that:
T(Vz, W2) W),
Proof. We simply write W V= + μuz. Then, T(V,, z, Wz) = / Then, ||=|1/||=|| is maximized by taking the right singular vector corresponding to the largest singular value of μr.
Now, we prove that for all & E Rd, there exists D, D' such that T(V2, Wz) = T(V, W). J. In order to do this, we prove that there exists two adjacent datasets = (X,Y). D' = (X,Y (X)Y)) such that the shift f between V and W, the weights matrices of linear regression on D and D' convergence, has rank 1.
Let RM u= 2/||=|| R R" Let X au" Rmxdd Y av E Rm be two rank matrices. Therefore, XTY (a ad)uu is rank one. We know that regularized linear regression converges Y XxXXXXX X + A By Sherman-Morrison formula,
uu T x A + 1
x = (llallun² + -1)= = x1
Then,
x |al2 vu |//|| ||
vuut
À A ||w||2"
Finally, choosing Y' proportional to Y, the shift has rank and || = |a (1)) = ||==||/|=|||
A.2. Discussion finite training time and convergence of NGD
We prove that full batch NGD converges normal distribution if 1)(A + M2/n) <1
Proposition A.1. Let t N Then, Vr is composed of independent Gaussian columns (Vi), sdd N Ex) with:
BBM*
Bi(T - (1
t-1
Σ = 2
no
Σ
M2x = M2m + 110 - -Ma).
k=0
Proof. The gradient is equal to
1 m
V Vu + 2XV 2 (VeXT -YT)X + 2AVE-
(V,
n
Then, noting B = 27 ",y"X,E= - + V and M = =1-21E, we get:
2 -y V.M +B+ 22
Vi+1 = V4- VV X,Y) + VrN++1 Va(II - 2n X/n + X1))
n
Then, can write:
V4 = VoM + (B
B + v 2no 111
Om0
12

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
which is composed of independent lines with mean and covariance:
14 B = ( M¹),
L-1
Σ = 2 2r + 2n10"
Σ M = -M + 2170" 2 2
1mm0
Note that we used symmetry M.
Assume that n + M2/n) < 1. Then M + 0 and
-M) --1))----- - -,,X X
14 B:(1 (5(I-M)
11
X -
Σ + 2no (1 (1
- 1-- 21111121)--13
By Levy's continuity theorem, 1t2 + V0 - N 22M 02M-11-11 can be decomposed in independent rows which have the same covariance and different mean. Note that when 17 - 0, we recover the Gibbs distribution.
A.3. Proofs of Proposition 3.2, Proposition 3.3
In this section, we compute the trade-off functions T(, W and T( Woo.). The following lemma characterizes the trade-off function between two Gaussian vectors with identical covariance and different mean. This function is expressed in terms |/x: (Mahalanobis) norms, which we define below:
Definition A.1 (Il ||s: norm.). Let ju E Idd, Rdd be an symmetric definite positive matrix. Then, the Mahalanobis norm is defined as:
|| VITE-
Lemma A.1 (trade-off function between Gaussian vectors with different means.). Let n² E Rd, E E Rdxdd be an symmetric definite positive matrix. Then,
T(V, W) = G 1p-H'lls
Let p. E Rd, Ee E gdxd be a positive definite symmetric matrix. Let V ~ (R, 2),, and W ~ N(d, 2)
Proof. Let Ho : (p, M), H1 :N''', 2). We note the log likelihood ratio:
uk(xr) = (z - " E - 14) - (x (x-))=
(p' - (N) - (1+ +²)) +C
= 2(p -
x (4' - " (M+
Following the Neyman-Pearson Lemma B.2, the most powerful test at level has the form T(x) = (4l - E 'x > ta.
Let N ~ NO, Ia)-
Under Ho:
(n' V -1) 1,, "n, (p' - n)) 1| - (n' -1)-E-11
Then, the type I error is:
N ta - (p' - -
P((p' - 1) VV ta) = =1 P
11 pl12 |
to (n' 11) ' 4 + 1| 111x0111111 (1 aa).
13

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Under H1:
(μ' - -E)= ~ -1) 11' (p' (u - Allx + +(4 -n)"E~~
Then, the type II error is given by:
8(a) P((p' - -1) sta P N ta (p' - -1)--)²-- -))
11 11 1>
N S ( 11) - 11 + 11 11 11115:0 $ 11-11 (1 - a) - (1' 1 11)
=
|1 - plll
= Φ a 111(1 - a) + (n' - - (14 - pl!)
1| 111l
= + + (1 a) -11y' 111'-~1113 -u(ls)
Then, T(V W) G1jp'=allas
Now can prove Propositions 3.2, 3.3. We give slightly more general result allowing Y and Y' to differ in multiple entries.
Proposition A.2. Let E = 1x"x+ + AI, M = -- - 2 and denote by A the square root of E M. Assume that Y and
Y" differ and that 7 + M < 1. Then:
T(V Woo GI
Moreover, for two given datasets, the adversary can choose E Rdd such that:
T(V Wxoz) = (X
In particular, when Y' and Y are adjacent (label DP), the adversary can choose Rd such that:
T(V 2oo TV Woo).
The first statement shows that the trade-off function can be improved from sensivity || - -Y')' /no to mm (AX*(Y - Y'))//no when Y and Y' differ on multiple rows, but when they are adjacent (as y is of rank 1).
We provide unified proof below.
Proof. We note B = E-IM-1 By Proposition A.1, Vx2 and Woc have independent rows and the i-th row of V. follows the distribution (Voo)i NYY?"> / //,n/nnn - The square roots are defined because I and M commute. Using Lemma A.1, the trade-off function between Vo and Wo is T(Vo,, Wx) = Gy ill--millan -illl-u------- 1g-1 with μ = xy-'XTY', -y Then,
a14 - M4 1 = (V, -Y) MXT (Y' = 1011/12002
Furthermore, for 2 E Rd, Voo ~ N(EE) XTY; 2)1 02 12,) Then, T(Vxz2, Wx = G -
By noting the change of variable u = B2 and using the invertibility of B, we get:
TTT--1 XT Y'Il = sup |Bz||
I!"" - = Fmax Tmax (AXT (Y - YY)),
sup z
|u]|
u
which corresponds to the 2-norm of AXT - YY' and is obtained by setting u" the right singular vector corresponding
to the largest singular value of AXT(Y - Y'). In the setting of Label DP, Y - has rank 1, so T(V 2, Wxo) = T(Voe; Woo).
14

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
B. Proofs of Section 4
B.1. Proof Lemma 4.1
We provide the characteristic functions of VZ and WZ.
Lemma 4.1. (Distribution of VZ and W Z). The distribution P. has the following characteristic function:
Φr, (t) = exp tr(t" vv 84 + o3
det (1 + 120
Proof. Let 1. E Rixx Assume that 02 00 = 1. We have:
Φr. (t) Elexp(i tr(t" (t""NNNN + o) E|E/exp((irr(f (N+))))]
Conditioned on Z, (N Z follows matrix normal distribution + u) (NN, Then,
Φp. (t) exp (tr(teNN) (t(NNT)E))
Notice that 1 + ttt is symmetric positive definite. We note As the square root of 1t + t and B, = ii, Then, leveraging the commutativity of trace operation and symmetry of A₁:
pp, (t) = (2xx d1/2 / exp
i ttr ez) 2 tr(x" at"t)) exp (- = dr
= (2xz) d1/2 / exp
1
2 (itr(x" (l + i itr(t" (x) - tr(x" tr(x">a?)) dr
= (2x)-a/22 -d12 / exp
2 (itr(v" tx + +it((at(e) - tr(z dr
(2x) d12 exp
lr(B,B()) / exp
(Ir((EA, - B.)(EAr (lonk-Be))))) Bi)²)) ) de
(2x)
d12 exp
1 (B,B exp
(tr((x BBA,1)AA(E B,A,))7)) dr
2
exp { ir( lr()
del (A (A/
exp ( tr T t(1 + + -t v))
det (h d/)0/2
Now, assume that o., og # 1. Then,
exp 2 tr(t" ov ooTt(I 020
dr. = =esxp(ttt((( z/)1
del (I + 1203(T1) 4/2
B.2. Proof of Lemma 4.2
We rewrite the Lemma 4.2 of approximation of trade-off functions and prove it.
Lemma 4.2. (Approximate trade-off function). Let P,Q, P. Q four distributions of IR.. Let γ
max (V, P), TV(Q, Q)) where TV denotes the total variation between distributions. Let (7, 7). Then,
T(P.Q)(a+ + T(P:)) < T(P, (
15

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Proof. Let E (0. - 7). We define 0 v S as the most powerful test between P and Q level a. We have (o)) = [
Then, using the definition of TV distance and the fact that 0 S v S 1,
[B[ B S (P..P)) 1 V - - - QV)
Then, using is a test between P and Q. v is at level 00 a + TV(P, P) and is not necessarily optimal. This means that T(P,Q) I -R [.) B As (PP, @) is non-increasing.
T(P, + P)) S T(P, - - v
< 1
QVQQ
As trade-off functions are non-increasing:
+ - P
For the other side of the inequality, take a' = a (1,1). We get:
T(P, ((P) - +)
and leverage the symmetry of the setting, giving the result.
B.3. Proof of Lemma 4.3
Before proving Lemma 4.3, we prove the following useful lemma:
Lemma B.1. Les > O. Let N Raxd Z R be two independent standard Gaussian matrix. Let B be deterministic matrix. Then, the distribution of (aN + Z is absolutely continuous with respect to the Lebesgue measure if and only if d 2 min(n,1) [n,I] l}.
Proof. First, let assume that d < min(n,2). We know that rank((oN + +) S minn + +o), rank( and because N and Z are Gaussian matrices, rank(N +v) = min [,, d} and rank(2) = min(d, 1]. Then, rank((oN +e) s min(n, d, () < d, and (N + = lies in the manifold Md,,(R of matrices of size nıl with rank d which has dimension d(n+l-d) d). Then, there exists Borel set A C M such that P( E A) 0. However, as (I- d) > 0, ni > d(n+ d) and Leb., (A) O. Thus, (a + Z is not absolutely continuous with respect to the Lebesgue measure.
Now, assume that d 2 n. Let A be Borel set of =R such that (A) = 0. Then, we write P((oN + + E A) [ (oN+ E A)dr. For all x E Rnd such that rank(x) = n, xZ is a Gaussian matrix and admits a density [REF), which means that Pr+Z E A) = O. Then, P(ooN + v)2 E A) = Srankla) (aN+ E A)dr. Also, for all Raxd P(=Z E A) < Then, P((aN + r)Z A) Srank(aa) PoN+o(x)dz Prrank(oN + v) n) because N + e is Gaussian matrix and absolutely continuous with respect to the Lehesgue measure. Then, (N + v) absoolutely continuous with respect to the Lebesgue measure. In the case n 2 I, we apply the same reasoning to the decomposition P((oN + v)Z E A) = Pz P( + v)y E A)dy.
Lemma 4.3. Let ~ NO0 1). Then, there exists Allll > 0 such that:
TV (ValooN + v)2, oz / do3 + +|u11/2
Appll
Proof. We note E Rd the orthogonal matrix such that T = ū = J/ (1o|l [mll)). Then, using invariance of Gaussian matrices by orthogonal transformation, VZ = (N + oUT)z = (NU + T)UTZ (N + o)Z. We write
VZ = Di ViZe d Ed (oaNk + l11l1 which is sum iid components. By Lemma B.I, (a + + [|
16

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
absolutely continuous with respect to the Lebesgue measure. We compute:
E
+
|ell)
E
(ogN1
+
|ell
[Z1] 0,
Vd
Vd
E
(o
+
|1ol)) 23
(ouNi
1
| = (a
211011
Vd
vd
E
(o
+
2}
=0
Vd
1
4
No
Val
z
33 + 60²1| + /|/ll//d))
Then, +.ve3+2llu1 (ooNi + Jal Z match the 3 first moments of Gaussian variable. Then, leveraging Theorem 4.2,
(aoNi + Jtal [1lll) $ zi
TV ( V2, og H|opPP <C
E
Alpll
1+
2 d
of (Vog + _110113)
with Allil C(9
[1 d1+do 1
This means that for any E Rd. Alpll S 9C.
Note that does not depend on og, and d. fact, noting Y,
(o + +/ I1ll))))
we have Cov(Yi)
0. 1 [ill
J = 1, and we apply Theorem 4.2 on the random variable 1 obtained by invariance of TV distance by invertible transformation.
Ei= Yt. removing the dependence. The final bound is
v7
B.4. Proof of Proposition 4.1
Before proving the result, we recall the
lemma.
Lemma B.2 (Neyman- Peaarsnn lemma (Lehmann and Romano, 2006)). Let P and Q be probability distributions on Q admitting densities p and q, respectively with respect some measure v. For the hypothesis testing problem Ho P vs H1 Q test ò Ω [0, 1] is the most powerful test at level if and only if there exists a constant h >> 0 such that ó has the form:
lffg(w)= > kp(w) Off < hp(w).
<(w)=
and [r[[o]
Proposition 4.1. (Trade-off function between Gaussians with different variance). Let 01, 0. Then,
(i(() ifa S o2 T2((x) else,
TWNO..)).NN(.033)
01 Φ -1 (1 - a/2) 1,
where Ti(a) = 2Φ
[ x 10-1((a + 11/2)
Tb(a) = 2 - 24
We denote this trade-off function by G(oroz)
17

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Proof. Assume that S 01 S 02- We note Ho X O( P. H1 X (V), Q. We write the log-likelihood ratio between P and Q:
z² 1 o
[k(x))
2
2
Noting that (1 02 o3 2 0 and using the Neyman Pearson Lemma B.2, the most powerful test at level a has the form
T(x) = x² 2 ta. Let N ~ NO0 1). The type I eπror is:
a = P > ta) = 2(1
2(1 - @(ta//1)).
Then, ta -1 a/2). Also, the type II error writes:
B(a) N sta) = (4((t//2)) - -2)(t//2))-11231)
11
(1- a/2)
02
Also, if 01 > 02 the log-likelihood ratio l1k(x)) S 0. Then, the most powerful test at level a has the form T(x) x²² S ta.
The type I error is:
a N2
N2 2 (a) = 2P(0 s N ta/o1) = (2a(ta/1) -.
Then, ta =0 (1ta)
Also, the type II error writes:
1 +
((a) P(azN2 > ta) 2(1 - (ta//o2)) =
Φ-1
02
Combining both tests gives the trade-off function.
We also give the trade-off function between Gaussian with different variances. This trade-off function depends on the cdf and the inverse edf of weighted chi squared variable, which are not trivial to compute in practice.
Lemma B.3 (Trade-off function between Gaussians matrices with different variances). Let v, w E RRadd Let E.g L² + vo E Ruxn En I²In www" Ruxn, P = (00 En Ii) and - NO, En I).. We note X1,..., An the eigenvalues 1/2 1T Ln 1/2 We note Fxmmndd x) the distribution of the weighted sum of n independent x² variables
with weights Ai,.... An at x. Then,
T(P,Q)(o) F(AE-LAE(L,)) (FFG-//Makepn.n (1)-)))
Proof. We start with the case 1. vo is positive semi-definite, so E, positive definite and E-1 exists. The log likelihood ratio between P and is: Uk(x) (E,1 1 )
+ -
Using the Neyman Pearson Lemma B.2, the most powerful test at level a has the form T(x) = x² (5,1 En- n² ".' 1/2
2 fa- We investigate the law of I under P and Q We note M Σ, 112 En D- 11112 M is symmetric and positive definite. Then, we note M UT DU, with D diag(>i..... An)-
Let N Ia)
Under P: X =-//"M N and 1,112x N:
T(X) NI, M NT - D-1)N = Σ (1 11-
Under Q: X 1//2N N and US 1/2 ~ N D). Then, writing T(X) = XT 1/2 (Tn D-' 1/2 x:
T(X) = -. No
(D-) 2(s 1)N2
18

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Then, the type error is:
P
Σ L1
111-//) =a to = (L- (1, 1111-a) a).
Finally, the type II error is given by:
n
B(a) = Σ (A - 1 Sta = = (Fasssaeep..)()1-o)))
In the case 1 > 1, the eigenvalues of M, (E, (11 M&L are
I times
limes
The log likelihood ratio between and Q is:
Uk(x)) = x² ((E, @ - (E & 11) 11) )2 + == =======<<=" 1
As in the case = 1, we can write the distribution of the test T x. (1E, Ew²) & 11) under P and Q and compute the type and II errors, giving the desired result. Let ~ N/0, I, @ li).
In the case
An >> 1. the type error is:
P L > to )0)=
> = P(L P((1-1/A)) tt) =a = ta -1- x
a),
k=1k=1
where 2a the edf of chi-squared variable with nıl degrees of freedom. The type II error is given by:
B(a) = P
AA 1)N2 S S/a) P ((A-(11)))) (.) = x2
(1 (1))))
X
w=1k k=1
B.5. Proof of Theorem 4.3
Theorem 4.3. Let d >> O. Then, there exists universal constant C > 0 such that for all a E (C/d,1 - C/d):
C
GM ((Bol))
+
T(VZ,
d
d
C
+ d
2 T(VZ,W2)o))
d
Proof. Let d > 0. Based on Lemma 4.3, there exists C such that:
9C
TV
V VZ,0zy of + |01|22
9
(1 + do 2|
TV 0Z o3 ++1gg11 1100332
C
6
96
9
+ do ////1/1133
d
Then, leveraging Lemma 4.2, for (C/d,1 -C/d):
B'lmil |
C) 90
((VZ,W2)(a) T 0= of d ||o||2G oz
/ oo
a
d
d
a c + d
9C
T(VZ,WZ)(a) T
Tz oo + [oloo oz o3 E'|i
giving the desired result.
19

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
B.6. Proof of Theorem 4.5
Theorem 4.5. (Convergence of product of Gaussian matrices, shifted version). Let N gu Z E [R G R
be independent standard Gaussian matrices. Let rank(v)). Assume that d 2 max(n,1) Then, there exists C' > 0 such that:
nls TV (loaN u)), sG + 0z SC d-s
Proof. We assume that 2 max(n, Let Raxd Z' Raxi, G R be independent standard Gaussian matrices. We note the singular value decomposition of FEST. Then, (aaN + v) (a,N FESS" NS+
d F + Z, by invariance of Gaussian matrices through orthogonal transformations. Because F is invertible, we can write: TV( + o)Z, sG + vZ') TV(F + E)Z, sG + vZ') (V + E) ga aavd - sG + Σ2").
We observe that N Z is decomposed into sum of independent bits: NZ = Ei N. Then,
TV( + E)Z, oaV. +G +G)
TV
Σ N +
+u6'
kms+1
k=1
SV
Σ Zk +
(N., + 22 E (N. + Ex,)Zz (1)
k=st1
+ +V
Govd - 5G + Σ + 2o EZZ
(2)
k=1
Using the data-processing inequality for TV distance for the map (I, v) + x +
((0
oood 5G, Σ No + )1)ZZK)) )
TV
Σ
MR.
+ & +Z,
Σ
k=st1
ml SCV
TV Σ
Mo
sG
d-s'
k=st1
by independence of the components in the pair and using Theorem 4.5 for product or size d - Also, using Pinsker inequality:
(2) < DEL oa aava - SG E2' -odd sG + Σ (ooN. N + E.
Because of independence of components in the sum, this divergence corresponds to the KL divergence between the convolution of two distributions by a third distribution. We find an upper bound to this divergence using the chain rule for KL divergence and a technique proof similar to the shift-reduction lemma (Feldman et al., 2018). Shift reduction lemma allows to upper bound the divergence between convolution of two distributions by the same distribution by coupling technique and the use of chain rule.
Lemma B.4 reductoreduction for KI divergences). Let X,Y and N be three independent random vectors. Then, for any random variable W that depend on X,
(X + N,Y +N+ S DRL(X + W,Y) F. DRL(N w., N)).
20

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Proof. Let X, Y and N be three independent random vectors. Let W be random variable. Then, observe that X+N = X W W N. We apply the post-procsssing inequality for KL. divergence under the map f (x, v) x t
DRE(X + N,Y + N) - (xx W.-W NY)))
Using the independence between N and the other variables, we obtain:
DKL + N,Y + N) = (xL + W.Y) + E [KL(NN w + W = y.
Then, using convexity of KL divergences and writing PN (x- P ( we obtain
D
+ +Ww,Y++Eyyae Ey BI DKL w. N)) = Bw (D
Then, for a 1, setting a shift W Tg Ei=1 Z we have in distribution, EZ' + + E3 C E.. means that:
DKL
No & E,,) 0. ΣZ' W.
Also, DKL(oevd-sCL sG w, w. sG) 20
w
Using the shift-reduction lemma, we get:
DKL Ez' + too loovd= Σ + + +oo < Bm-- W DDillovdd
+
08 aavd d
|
< Bwn
20 d s)
nls
2(d =s)
where expectation is obtained using independence between N and Z,
27 No.
W || = og ΣΣE
E
nill
1E N.
= oānls.
i=1 5=1
k=
Finally, we find:
nls
nds
TV 22) +Z) & C d d-s
CC'
$ C²
V d-s
4(d - s)
We obtain the result of the lemma by applying invariance of TV distance under rescaling.
B.7. Experiments and Interpretation with Rényi divergences
In this section, explain the setup of our experiments, and compute upper bounds for Rényi divergences between Gaussian matrices with different covariance structures.
Rényi divergence between Gaussian variables.
Let > The Rényi divergence between. (N + 0²) and A((, s + w²) maximized by setting v = T.,A w = U for some value 0 < A <
21

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Lemma B.5 (maximum of Rényi divergence between Gaussian variables with same mean and different variance).
2a- (a log(rs,a) log(ar,, + +1)) if 2 a(a 1)42
Da(NV(,s++'") +.) + + 1--
sup
+o0 else,
2s + A Av A + 4s
where As
28
Proof. For r > O, we note f(r) = a log(r) log(ar + 1 -.), and we note r(v, w) =
st62
stw2.
The Rényi divergence of order a > 1 between (WVO0, +-2) NO,, is given by Da (0,)), NO,, (((,,+++)))
Me-11 (r(v, w)). We note Tmax su ((u, w), mmin = T w). We study the function f:
('(r) = a or
((()) & 00ir 1 1) and else f'(r) 2 O. This means that sup w- Sa f(r(v, w)) = mf (Tmin))
Now, we compute Ymax and Tmin. We first observe that Fmax = 1/Tmin Writing e w + x, and |x| S A, we have (+++22) Also, T Tmax is obtained for w + A, and positive. In fact, if w O, for R such that which has two
r(w + I, w) st
|x| S A, r( w) r(-w 2, w) S r(-w A w) We derivate: -r(w w) 2A s- (stw2)=
roots. We note Wmaxx
2 (VV A 45 A), which verifies Wmax A s/Wmax- Then,
+ (Wmax
+ +
+ (s/Wmaxx) )2
2s
mmax
+ w waax
$ 5 Wiax
w max
2s + A2 A A + 4s
Then, investigate
for (1,a/(a-1))
Let, for x E (1,a/(0 - 1)), g(x) = -1-20
a+(1-a)a artl-a
Then,
g'xx) (1-221)) 2xxxx= 22 (1 a))a (11ax+1-a0 +1
a(a + (1 -1- (1-a)x) =(1- -2a) x x=_
(a+ + (1 (1-a)=)2 )
(1-
Given that a 1, x + x convex on (1, 1)), xa 2 + oz > oæ + 1 a, and, by monotonicity, x 20 S (a+(1-o)z)²- Then, g/ (x) 2 O.
Also, ,(0) = 0. Therefore, for æ E
2 0. By monotonicity of the logarithm,
a (1 - a))x) )+) - f(1/z) 2 f(x).
(1 - log(z) 2 log
1 a
Then, the supremum of the Rényi divergence attained for r = Tmin and is given by:
sup Da(N(0, s ( = 2a By (a log(rmin) - log(ar min + 1 a1) if 2 - 1)A2,
1e-wa AA
00 else,
2s + 2 A 2 4s
where Tmin
2s
Performing an asymptotic expansion, we recover convergence rates for the Rényi divergence: Proposition B.1 (Rényi divergence rate of convergence univariate case).
aA
sup we- Da(A o 7o, ozd w²))
+ o(d-1).
4do7
22

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Proof. Note o²d. We first compute an asymptotical expansion of ra.A-
2s
A
A + 48
A
A
A
A
11
+1=11
+o(1).
2s
2s
V$
4s
2s
V3
Also, we have a log(1 + r) Combining both expansions.
log(1 + +ar) = a(r - 12 2 + o(r?)) (ar - (ar) /2 o(r?)) = a(a-1) ,2 o(r2).
2
0A2
2(a - 1) -
log((r,,,, + a))
old
4d
Rényi divergence between Gaussian matrices.
Now, we compute an upper bound of W| DalV&G+ /sG++ + wZ).
Lemma B.6 (Upper bound of Rényi divergence between Gaussian variables with same mean and different variance). Let G' e paxi G E Rdxi be Gaussian matrices, and v, E Indd Then,
+ Da(VoG+ + vZ, voG + w2) S 2 (alog(rr,s)) - ifs a(a 1afa--10 1)42
sup |M-=||AA
else,
28 + 1= AV 48
where Ts.A
28
Proof. Because uZ is composed of independent columns, can write Da(ViG vZ, /5G + wZ) IDa + 1Z1 V3, + w21). Noting Σ, =/n + vu'" Ew sI, + www" we reduce to the problem:
Da(sG + uZ, sG = -.) (0,
Σ, is positive definite and admit a square root. We note Mr,ur Σ, ",, and note A..... An its eigenvalues. Then, by invariance of Rényi divergence my invertible matrix multiplication, the Rényi divergence can be written:
Do (N((,, WO, )m = Da (0, (O,, (N,, Mo.w)) = 2(a 1)
(a loggodet(MM,an - log(aM + +1- - ax)
1
2(a log((>) log(adk + 11
Da ((..
Now, we prove that for all & E [1, m], A E (f/.A. We note S= W. Any eigenvalue À of My can be written (with a change variable x + 1E11/2)):
x²' Fmn
A
x E.,
where v is an cigenvector associated to A. We have: Dn shn + www sl, +lut +US +S +SST
Then.
A A 1 xT(E, + S + S + SSST)
2(ST x, vTz) + S 2|
x² Enxx
$||x||2 10 x
The condition ||S] < A gives ||Sar|12 < σ max (5)2111112 A |0|1 Cauchy-Schwarz inequality yields (S x, of x)
||uT x||]
< A| To[T=lllaa =|||||||| and
+ A
- 2
24
|||||||||| + 1
s
|||||
+ (w + 4)2
A < 1+
< sup
< 1/r,,a,
s||=||2 + ||
[
wE
$ s x2
|
23

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
using the analysis from Lemma B.5.
Then, leveraging Lemma B.5, find:
DalV&G + vZ, V&G - wZ) S + -V,,A + A)3)),
sup || will SA
with V4
(V
+
A), concluding the proof.
Note that there is reason for this bound to be optimal. In fact, we leverage upper bound of the eigenvalues of M individually instead of directly analyzing:
Po(N(..1).N
sup
1=1
Performing the same asymptotical analysis as Proposition B.1, we recover the following upper bound for the Rényi divergence: Proposition B.2 (Rényi divergence rate of convergence multivariate case).
omlA2
sup
Da(aovd- nG + uZ, u2,,oodd- nG + wZ) < 4(d n)o
+ o(d
Methodology of experiments - releasing one output.
Let v, u E Flxd We give a result more precise than Theorem 4.3. By Theorem 4.3, there exists Cl 0 such that for all (CitellIw))) (tvll.be////d
G (o
(a+ Gieillllull )
I <T)V),
Here, the constant [[ is not universal but depends on and w. C[brl||/ell = max [ u|| A is given by Proposi-
tion 4.3. Aljal and Allll both depend on a universal constant, derived from Theorem 4.2, that we set to 1 for our experiments. We note A joll
6
(1+do3/1lo1??>
Based on Lemma B.5, the Rényi divergence (NV agd + N agd + [|]l))) is maximized by setting 42 := ||a||
A); Wd,s = ||w|| = {VA= 2 + 40gd + A). Then, the ratio of the variances r satisfies aod+n < 1. Leveraging Proposition 4.1, for (0, 1). consider the trade-off function:
(VA² + 40gd
aadtu1
and + v2 Φ (1 a/2) 1. agd + vg
(x 24
Our objective is to estimate the Rényi divergence derived from the following trade-off function:
T(V, (a),
(a)= = max
(1- a/2 2 Cea...aa - -1- Cog.a.ng
2Φ
codtoy
where we set, by abuse of notation:
& aad + U² x (1 a/2 Cuaswa..//d -1+ Con,sMas = 0if (0, C.s Cal 1).
aod + UZA
The constant Coy. is equal to OayA = maxf Avas Awaa = =(9- (1+ do
24

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
Now, we can numerically estimate la (h)..
As discussed in Section 4.3, for d large enough, there exist C1 C2 < such that:
T(V, (a) if E (0,c)) (c,,1),
h(a))
aodtt x- (1 (1- a/2 C /2d) 1 CoLAsis if E (21,
2Φ
oodtti
numerically compute ej and C2 with the scipy. optimize brentq method, with the smallest possible tolerance :ol 4+np finfo (float) eps 10-15, which is negligible compared the other quantities of the experiment. @ and --1 respectively computed with the methods sci scipy. py stats norm. cd f and sci py stats norm ppf.
We compute the derivative:
6(b '(1-a) A/oo) if E (0,c))
(1-a))
(a)))
111-a/2 (aa-a/2-Cuaaae Coali--Caaaaaaaa a if E (21,
ood+r
oydtri
6 (1--((1-)) aa2 2- Cva, wa (2d)
Then, we estimate la (h) using Monte Carlo algorithm. We de 1. We set the number samples L 5 10 We sid Unif([O, 1)). Then, we the procedure and the estimates are averaged:
draw M 50 times (Xk,)) (Xerr)sssassSS
(h) = M(a Σ log Σ
['((x,x))==
M=1
We repeat the process for different values of and A. For each configuration, we compute the empirical standard variation of the averaged estimates:
M Σ
I
(1)
log
1
W(Xxx)))
TT,
VM-
L
k=1
#==1
Standard variations are not shown in Figure 2 as they are too small to be distinguishable (they are about 50 times lower than the corresponding averages).
Methodology of experiments - releasing multiple outputs.
Let U, w Raxd By Theorem 4.6, There exists a universal constant C such that for all a
(Om L 1 Cn -
T Loovdd - nG vZ, o2 + wZ) (a le+Cry 4(d 4(d-n)
1 CTy d S (TVZ,
take C for our experiments. The left trade-off function is not simple to compute for general values of v and w (see Lemma B.3). However, by independence rows in oovdd nG vZ.
nG T +7 + wZ) T TT nGn aZ n01 wZi &V
By Lemma B.6 the associated Rényi divergence can be upper bounded by a choice of u, = Ud-n, with Ud-n,A (v22 + 40 - n) - A), w, (Ua-n.A + I) Note that || - w| = nA, so the upper bound may not be tight. We denote x22, as the trade-off function of a chi-squared random variable with nl degrees of freedom. Then, we consider
25

---

Privacy Amplification Through Synthetic Data: Insights from Linear Regression
the following trade-off function:
T aov - -ovd-nGi-o + v. 2,, nG1 + w.
=T 0oV d nG1 + 2/d an - nG1 + (Ud-n, A)In
60ml
[oovd nG1,1 + U 0oVd nG1,1 + (Ua-n,A + A)
oz - n2)
b 22
$7 Xnt
a))
oz(d n) (Vd-n,A A)2
which is obtained from Lemma B.3. Let the trade-off function:
TTV,
h(a)= = max
cg(d-n)+o2 T- Xai
11-a a d-)) Cnvy d-n
Φ And (vlddn))(ra-m,att))
For large enough, there exist
a < <
such that:
add--))-ri T(V, ((V ifa ((22) 1),
h(a)=
Φx2 o3(d-n)+(m AA 27 (1 a1-a Cn/ - if (c1,
With the same method as the one output case, we numerically compute с and c2. Then, we compute the derivative:
Φ (11 (11-a) if E (0, (o,,) 6( (1-a)
((a))
ob(d-n)+e3_n. (d- (Mu
2 ogd nit (
ozll-nitt ns
(I-a-Cay Nal
if E (2),
AA
(1-a-Cm/2- 2-n
where 222 is the density of a chi-squared random variable with nl degrees of freedom. The functions Tb xa. and 0x2, are respectively computed with the methods scipy ky- stats..tt......... chii 2, edf, sci py . stats. ch .c.....ppp... and acipy. stats. chi2 cdf. Using the same Monte Carlo procedure as above, empirical estimates with M = 50 repetitions and L = 5 x 10 samples. We set / = 10 and n 1, and we report in Figure 3 the estimated Rényi divergence for multiple values of d and A. As in the one-dimensional output case, standard variations are not shown in Figure as they are too small to be distinguishable (they are about 20 times lower than the corresponding averages).
Φ-
x
now compute the averaged
26


Reviews:
[{"review_id": "5UwlhIy3L0", "reviewer": "Reviewer_RSvt", "summary": "This paper investigates the privacy amplification effect that could be gained when hiding the model that has been used to generate differentially-private synthetic data. The objective is to be able to quantify the privacy gain obtained by releasing only a limited number of synthetic data and not the model itself. More precisely, the authors show that releasing a number of synthetic profiles smaller than the input dimension provides strong privacy guarantees.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "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": "We thank Reviewer RSvt for their feedback. Below, we address each concern separately.\n\n## Weaknesses\n\n> The term \"privacy amplification\" used in the title is exaggerated\n\nIn our paper, the phrase \"privacy amplification from synthetic data release\" refers to potential privacy gains achieved by releasing only synthetic data while keeping the generative model hidden. We demonstrate that this privacy amplification does not occur when the adversary controls the seed. However, existing empirical studies suggest the existence of this effect when the seed is randomized (e.g., [1]). This empirical observation motivates our research question: *Can privacy amplification occur from synthetic data release, or are existing membership inference attacks simply insufficiently powerful to achieve the maximal privacy leakage?*\n\nTo address this, we conduct a rigorous theoretical analysis in a simplified linear regression setting. Our results are the first to show that under certain conditions, privacy amplification can indeed occur—even achieving perfect privacy as $d$ increases. While our analysis applies to a specific setting, it does not rule out amplification in more general cases. Instead, our work highlights scenarios where amplification is provable, laying the groundwork for deeper theoretical exploration in broader, more realistic contexts. This motivation is reflected in our title: \"Insights from linear regression\".\n\n[1] Annamalai, M. S. M. S., Ganev, G., and Cristofaro, E. D. \"What do you want from theory alone?\" Experimenting with tight auditing of differentially private synthetic data generation. USENIX Security 2024\n\n> There is also a lack of experiments to validate practically the theoretical claims\n\nThis is a theoretical paper, and experiments are not necessary to support rigorously proven claims. However, we agree that empirically estimating the privacy guarantees, for example to assess the tightness of our theoretical results, is an interesting idea and we thank the reviewer for this suggestion.\n\n## Questions\n\n> It would be great if the authors could comment on the potential of the approach to generalize to other types of models.\n\nWe agree that the generalization of our results to deeper models present significant challenges. However, we believe our findings have the potential to be leveraged in broader settings. For instance, the post-processing theorem ensures that the results also apply to regression problems with activation functions---such as logistic or ReLU regression---provided that Lipschitzness and convexity are preserved.\n\nA promising direction for broader applicability is private fine-tuning of the last layer in deeper neural networks, which maintains the linear regression framework. However, modeling the distribution of the noise in this setting becomes more challenging, as the transformation of the Gaussian input through the layers alters its statistical properties. We leave this for future work.\n\n\n\n> About $f$-DP and Rényi DP: \"Ideally, it would have been great if the authors could have elaborated on why such notions are necessary compared to the classical DP definition.\"\n\nWe chose to consider $f$-DP because it is a tight way to track the privacy guarantees at all $(\\epsilon,\\delta(\\epsilon))$ budgets as trade-off functions. In fact, $f$-DP is the most informative DP notion for the Blackwell order [2]. While alternatives such as privacy profiles could also be considered, our analysis fundamentally relies on the approximation of trade-off functions. For other privacy definitions, this would require other tools and may lead to looser results. In addition to $f$-DP, we considered Rényi DP for its more interpretable privacy bounds, which are easier to grasp than trade-off functions.\n\n[2] Jinshuo Dong, Aaron Roth, and Weijie J Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series B: Statistical Methodology, 84(1):3–37, 2022.", "claims_and_evidence": "Currently, the paper does not contain any experiments for validating the theoretical claims made. If possible, it would have been great to conduct some auditing experiments on controlled datasets to be able to verify these claims.", "methods_and_evaluation_criteria": "The paper takes a novel approach of trying to model the worst-case approach for the generative process by giving the control of the seed to the adversary. While this approach is promising, there is however no experimental methodology proposed for validating the performance of such adversarial approach in practice.", "theoretical_claims": "The theoretical claims are made with respect to two different variants of differential privacy, namely f-DP and Rényi DP. Ideally, it would have been great if the authors could have elaborated on why such notions are necessary compared to the classical DP definition.\n\nNonetheless, the authors have been able to show that in the specific case of differentially-private linear regression, there exists situation in which if the adversary is able to manipulate the randomness used by the generative process, he can achieve the theoretical upper bound in terms of privacy leakage. \n\nTo be frank, the proofs are highly technical and specialized and I do not have the expertise to validate them thoroughly.", "experimental_designs_or_analyses": "The theoretical analysis seem sound although as mentioned earlier I do not have the technical expertise to validate them fully. However, there is no experiments set up for validating them.", "relation_to_broader_scientific_literature": "The main results of the paper contributes to better understand the privacy guarantees that are possible in a context in which only synthetic data is released and not the model itself. However, the impact is limited in the sense that the results only holds if the number of released synthetic samples is very small compared to the input dimension, which is very limited in terms of practical interests.", "essential_references_not_discussed": "I do not see any missing important references, rather the authors have done a good job at reviewing the corresponding state-of-the-art.", "other_strengths_and_weaknesses": "The paper is well-written and the authors have done a good job at explaining the current state-of-the-art on the evaluation of DP guarantees of synthetic data. The theoretical analysis conducted is interesting but only holds for a very small release of synthetic data and thus I consider that the term \"privacy amplification\" used in the title is exaggerated. There is also a lack of experiments to validate practically the theoretical claims.", "other_comments_or_suggestions": "A small typo : « Without loss of generarilt » -> « Without loss of generality »", "questions_for_authors": "It would be great if the authors could comment on the potential of the approach to generalize to other types of models.", "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": "", "extra_scores": {}}, {"review_id": "WJVR6ohbrZ", "reviewer": "Reviewer_c2xJ", "summary": "This paper explored the privacy amplification properties of hiding the generative model in private synthetic data generative contexts. Differentially private generative models produce synthetic data that formally inherits the same privacy guarantees. In practice, it has been observed that when the synthetic data generated is small enough, it meets stronger guarantees than the generating model, through an amplification effect. This paper formally shows that this amplification effect exists in cases where synthetic data is generated from random inputs to private linear regression models as case study. In particular, releasing synthetic data leads to stronger privacy guarantees than releasing the generative models when the number of released samples is small enough. The paper also demonstrates that in the case where the adversary has access to the seed of the generative algorithm, there is no such amplification of privacy.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "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": "We thank Reviewer c2xJ for their interesting and positive feedback. Below, we address each concern separately.\n\n## Limitations\n\n> Restricting the focus to linear regression provides a clean case study but limits the generalizability of the findings: it’s unclear how well these results could extend to more complex models.\n\nWe agree that the generalization of our results to deeper models present significant challenges. However, we believe our findings have the potential to be leveraged in broader settings. For instance, the post-processing theorem ensures that the results also apply to regression problems with activation functions---such as logistic or ReLU regression---provided that Lipschitzness and convexity are preserved.\n\nA promising direction for broader applicability is private fine-tuning of the last layer in deeper neural networks, which maintains the linear regression framework. However, modeling the distribution of the noise in this setting becomes more challenging, as the transformation of the Gaussian input through the layers alters its statistical properties. We leave this for future work.", "claims_and_evidence": "The claims in the paper are well supported by theorems, propositions and lemmas. I reviewed the theoretical results in the main paper, which appear well structured and correct. I did not review proofs and other results in the Appendix.", "methods_and_evaluation_criteria": "The goal of the paper is to provide an initial theoretical framework to study the phenomenon of privacy amplification through synthetic data. This is achieved mainly via theoretical analysis that is appropriate with respect to the overall goal.", "theoretical_claims": "I checked all proofs and results in the main text, and to the best of my knowledge they seem correct. I did not however have the time to review results in Appendix.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The main contribution of the paper is to set up the theoretical framework to study privacy amplification via synthetic data, a phenomenon that was empirically highlighted in work by Annamalai et al. (2024), and in part explored by Neunhoeffer (2024) in a more limited context where training data is one-dimensional and the generative model is a Gaussian with mean and variance estimated privately from the data. This paper uses linear regression to study the phenomenon in a more extended way. The contribution is two-fold: i) the author(s) first prove a negative result: for both output perturbation and noisy gradient descent as methods to privately train the generative model, releasing synthetic data from fixed inputs does not lead to privacy amplification (Theorem 3.1 and 3.4 respectively); ii) then, the paper proves privacy amplification for the single release case (Theorem 4.8) and the more general case of multiple releases (Theorem 4.11). To the best of my knowledge, these contributions are novel, and pave the way for new valuable results in this line of research.", "essential_references_not_discussed": "I don't think any essential related work was left out of the discussion.", "other_strengths_and_weaknesses": "Strengths:\n- The paper addresses an important open question by developing a theoretical framework for quantifying privacy guarantees in synthetic data release, specifically in the context of linear regression. This rigorous approach helps fill a gap in understanding privacy amplification in generative models.\n- The paper presents both positive and negative results. It demonstrates that privacy amplification is possible under certain conditions (with random inputs) while also highlighting scenarios where the privacy benefits don't hold, such as when an adversary controls the synthetic data generation seed. \n\nLimitations:\n- Restricting the focus to linear regression provides a clean case study but limits the generalizability of the findings: it’s unclear how well these results could extend to more complex models. \n- As stated by the author(s), while these findings lay the ground for better insights into private synthetic data, their practical impact is limited.", "other_comments_or_suggestions": "No additional comments or suggestions at the moment.", "questions_for_authors": "No specific questions at the moment.", "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": "", "extra_scores": {}}, {"review_id": "gsztQcTUHB", "reviewer": "Reviewer_ukYX", "summary": "This paper investigates privacy amplification from synthetic data release within the specific setting of linear regression.\n\nThe authors first establish negative results, showing that an adversary controlling the seed of the generative model can induce the maximum possible privacy leakage from a single query.    \n\nConversely, they demonstrate that generating synthetic data from random inputs amplifies privacy beyond the model's inherent guarantees when releasing a limited number of synthetic data points. The amplification holds in the regime when few synthetic samples are released and the ambient dimension d is large.\n\nThis highlights the crucial role of randomization in the privacy of synthetic data generation.\n\n---\n## update after rebuttal\n\nThe paper presents an interesting theoretical observation, which I appreciate, albeit with limited potential applications. The rebuttal reinforces my stance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We thank Reviewer ukYX for their feedback. Below, we address each concern separately.\n\n## Weaknesses \n\n> The amplification only holds when the number of generated points is less than the dimension\n\nThis is correct. However, our results do not imply that privacy amplification does not happen when the number of generated points is larger. Our work focuses on the theoretical existence of privacy amplification by synthetic data release. Making it more generally applicable is an interesting open problem.\n\n> \"... limitations of the model as well as techniques, which are unlikely to extend beyond linear regression\"\n\nWe agree that the generalization of our results to deeper models present significant challenges. However, we believe our findings have the potential to be leveraged in broader settings. For instance, the post-processing theorem ensures that the results also apply to regression problems with activation functions---such as logistic or ReLU regression---provided that Lipschitzness and convexity are preserved.\n\nA promising direction for broader applicability is private fine-tuning of the last layer in deeper neural networks, which maintains the linear regression framework. However, modeling the distribution of the noise in this setting becomes more challenging, as the transformation of the Gaussian input through the layers alters its statistical properties. We leave this exploration for future work.\n\n## Questions\n\n> \"Are there any downstream applications the authors envision for releasing $\\leq d$ private synthetic data points from a linear model?\"\n\n\nAs you pointed out in your comment, revealing less than $d$ synthetic data points has limited utility. However, our work is the first to highlight scenarios where amplification is provable, laying the groundwork for deeper theoretical exploration in broader, more realistic contexts. We are confident that our privacy bounds can be extended in practical settings. This is an objective for future work.", "claims_and_evidence": "The theoretical claims are supported by proofs.", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "I briefly checked the proofs but not in thorough detail.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The key contribution is the formal proof that releasing synthetic data can in fact reduce privacy loss compared to releasing a privatized model. This is in contrast to most prior works where the privacy loss is bounded using post-processing once there is a privately learned generative model. While privacy amplification from synthetic data is not completely new, past works only study the simpler case of univariate Gaussian data (Neunhoeffer et al., 2024).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths: \n- This work provides a decently thorough examination of privacy amplification from synthetic data release in the setting of linear regression, including an impossibility result when the internal randomness of the generator is controlled by an adversary, and a positive result when the internal randomness is actually random.\n\nWeaknesses: \n- The amplification only holds when the number of generated points is less than the dimension. However, we need $O(d)$ samples to learn the parameters of a linear model, so it doesn't seem possible to learn the linear model using synthetic data while satisfying privacy amplification.\n- Another potential weakness is the limitations of the model as well as techniques, which are unlikely to extend beyond linear regression to, e.g. neural networks, where synthetic data is much more useful.\n\nThat being said, I believe the theoretical results are interesting within their scope and can be a plausible addition to ICML.", "other_comments_or_suggestions": "It might be helpful to contextualize the amplification results in terms of (eps, delta)-DP, perhaps even in restricted choices of the parameters, to better interpret the quantitative improvement over simple post-processing.", "questions_for_authors": "1. Are there any downstream applications the authors envision for releasing $< d$ private synthetic data points from a linear model?", "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": "", "extra_scores": {}}, {"review_id": "aWQJX1PgcT", "reviewer": "Reviewer_pnmm", "summary": "The paper offers a theoretical analysis of the privacy loss of releasing synthetic samples in linear regression. It demonstrates that, under a strong threat model where an adversary controls the seed of the generative model, releasing even a single synthetic sample can result in privacy leakage equivalent to that of releasing the full generative model in the worst case. Conversely, when the seed is random, the authors prove a form of privacy amplification.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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": "We sincerely thank Reviewer pnmm for providing valuable feedback and pointing out several valid issues. Below, we address and discuss each point.\n\n## Claims And Evidence\n\n> Privacy leakage is not about recovering model parameters\n    \nWe agree that our sentence might be confusing. What we mean here is that if the adversary is able to recover the model parameters, then no privacy amplification is possible compared to the privacy guarantee given by post-processing the model (this is what we call \"maximum privacy leakage\" in this context). We show that a single query is sufficient for an adversary to achieve this maximum privacy leakage (Proposition 3.1).\n                                                            \n> How… Label DP translate into a construction for standard DP\n    \nDP upper bounds the privacy leakage across all possible pairs of adjacent datasets. In Label DP, adjacent datasets differ only in their labels. Since any two datasets that are adjacent under Label DP remain adjacent under standard DP (where both features and labels can differ), a lower bound on the privacy leakage in the Label DP setting also applies to standard DP.\n \n> Mathematically, it seems to be the case that $|A\\Sigma X^T(y_i'- y_i)| \\leq |A X^T(y_i'- y_i)|$ does not necessarily hold\n    \nYou are right, thanks for catching this. There is a minor error in the upper bound. We address this in the \"Theoretical claims\" section below, where you also raised a related question about the convergence of NGD.\n\n## Theoretical claims\n\n> Output perturbation is not possible without Lipschitz condition on the objective function\n    \nYou are right and we thank you for pointing out this oversight. To ensure the loss is Lipschitz, we can assume that $\\|x\\| \\leq M_x, \\|y\\| \\leq M_y$ and limit the parameter space to the centered ball of radius $M_\\theta$ (the latter condition is always verified for ridge regression). Such conditions are common in private linear regression analysis, see for e.g. [1]. The objective is then $L$-Lipschitz with $L = M_x^2 M_\\theta + M_x M_y + \\lambda M_\\theta$, allowing us to use the output perturbation mechanism and to keep our results unchanged.\n\n\n[1] Y. X. Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. AISTATS 2018.\n\n> Discrete convex Langevin dynamical systems do not necessarily converge\n\nAgain, you are right. The ergodicity of the process is required for convergence, and is ensured when the objective function is strongly convex and smooth (see for e.g., [2]), which is the case in our setting. Furthermore, for NGD with full batch training, it can be shown that if the learning rate $\\eta$ is sufficiently small, then $V_t$ converges to a normal distribution, which is the Gibbs distribution when $\\eta \\to 0$. The correct result writes as follows.\n\n>Let $\\Sigma = \\frac{1}{n}X^T X + \\lambda I$, $M = I - 2\\eta\\Sigma$ and denote by $A$ the square root of $\\Sigma^{-1} M$. Without loss of generality, assume that $y$ and $y'$ differ. Assume that $\\eta(\\lambda + M_x^2/n) <1$. Then:\n$$T(V_\\infty,W_\\infty) = G_{\\sqrt{2}\\|A X^T (y-y')\\|/n\\sigma}.$$\nMoreover, for two given datasets, the adversary can choose $z \\in \\mathbb{R}^d$ such that:\n    $$T(V_\\infty z,W_\\infty z) = G_{\\sqrt{2}|\\sigma_{\\max}(A X^T (y-y'))|/n\\sigma}.$$\nIn particular, if $y'$ and $y$ are adjacent (label DP), the adversary can choose $z \\in \\mathbb{R}^d$ such that:\n    $$T(V_\\infty z,W_\\infty z) = T(V_\\infty,W_\\infty).$$\n\nThis result corrects both the confusion about convergence of $V_t$ and Propositions 3.2 to 3.4.\nDue to space limitations, we are not able to give the sketch of proof here, but we are happy to provide it as a follow-up comment to the reviewer.\n\n[2] A. Durmus, S. Majewski, and B. Miasojedow. Analysis of Langevin Monte Carlo via convex optimization. J. Mach. Learn. Res. 20:73,  2019\n\n## References not discussed\n\nThank you for highlighting these references. We will add a citation to this recent survey and discuss how our work relates to other privacy amplification results. As you noted, synthetic data release is a distinct phenomenon that extends beyond privacy amplification by iteration. In the latter, the final model is released at the end of private training, while our approach further conceals the model itself and discloses only synthetic data generated from random inputs to the model.", "claims_and_evidence": "There are a couple of points that I find problematic or unclear:\n- \"It is clear that the adversary can recover the model parameters $v^*$ from $d$ queries...Strikingly, we now show that the\nadversary can in fact recover the model parameter with just one query.\" --> The discussion here is very confusing. Privacy leakage is not about recovering model parameters (as a matter of fact, they are already known after training), but rather about inferring information about the training samples. Additionally, what you really show here is that with one query it is possible to achieve the maximum privacy leakage (as specified by the privacy budget of training the generative model) for some worst-case datasets. \n- \"Since Label DP is a weaker notion than standard DP, these results also imply negative results for standard DP\" --> I don't follow this claim. How does a construction where releasing a single synthetic sample achieves maximum privacy leakage under Label DP translate into a construction for standard DP?\n- \"However, these results do not imply that for every possible seed $z$, the privacy loss $T(V_\\infty z, W_\\infty z)$ is strictly smaller than $T(V_\\infty, W_\\infty)$\" --> I'm confused about this argument. Mathematically, it seems to be the case that $\\|A\\Sigma X^\\top (y_i-y_i')\\| \\le \\|A X^\\top (y_i-y_i')\\|$ does not necessarily hold. On the other hand, the post-processing property of DP guarantees that the privacy loss of releasing a single data point is upper bounded by the privacy loss of training the generative model. How can these two observations be reconciled?", "methods_and_evaluation_criteria": "N/A", "theoretical_claims": "- For output perturbation, Chaudhuri et al., 2011 assumes certain properties of the loss function, specifically bounded gradient (or equivalently, Lipschitz), to upper bound the L2 sensitivity of the minimizer of the regularized least-square objective. To satisfy this property, they primarily focus on classification losses such as cross-entropy and hinge loss and assume that the samples have bounded norm. In contrast, the current paper directly borrows the results from Chaudhuri et al., 2011 but applies them to linear regression. The assumptions from Chaudhuri et al., 2011 are not formally stated, and the gap between the two settings is not addressed, which is problematic. In fact, the gradient of the square loss is not necessarily bounded without additional assumptions.\n- The authors claim that \"As a discretized Langevin dynamical system with a convex objective, it is known that $V_t$ converges in distribution to its stationary Gibbs distribution\". This claim is made without any references or citations. My understanding is that while Langevin dynamics with a convex objective do converge to the stationary Gibbs distribution in continuous time, this convergence is not guaranteed for discretized processes without further assumptions on the step size. This lack of rigor is concerning.", "experimental_designs_or_analyses": "N/A", "relation_to_broader_scientific_literature": "The paper contributes to the literature on DP data synthesis by providing a formal analysis of the privacy loss of synthetic samples. It also extends the literature on privacy amplification by identifying an alternative mechanism---privacy amplification through synthetic data---beyond traditional approaches such as subsampling and iteration, once again showcasing the power of randomness in privacy protection.", "essential_references_not_discussed": "For DP synthetic data generation, the authors should discuss [1]. In particular, Figure 1 offers a useful overview of the current state of the field.\n\nAt a high level, the phenomenon uncovered in this work resembles privacy amplification by iteration: releasing only the final model checkpoint, rather than all the intermediate ones, leads to better privacy. In addition to Feldman et al., 2018, the authors should consider discussing [2,3,4], which provide last-iterate privacy analysis under the assumptions that the loss function is convex and/or smooth, showing that the privacy loss is bounded as $T$ goes to infinity. Moreover, it would be beneficial to review several works on privacy amplification by subsampling [5,6]. Collectively, these studies highlight the power of randomness in privacy protection.\n\n[1] Hu, Yuzheng, et al. \"Sok: Privacy-preserving data synthesis.\" 2024 IEEE Symposium on Security and Privacy (SP). IEEE, 2024.\n\n[2] Altschuler, Jason, and Kunal Talwar. \"Privacy of noisy stochastic gradient descent: More iterations without more privacy loss.\" Advances in Neural Information Processing Systems 35 (2022): 3788-3800.\n\n[3] Ye, Jiayuan, and Reza Shokri. \"Differentially private learning needs hidden state (or much faster convergence).\" Advances in Neural Information Processing Systems 35 (2022): 703-715.\n\n[4] Chien, Eli, and Pan Li. \"Convergent privacy loss of noisy-sgd without convexity and smoothness.\" arXiv preprint arXiv:2410.01068 (2024).\n\n[5] Balle, Borja, Gilles Barthe, and Marco Gaboardi. \"Privacy amplification by subsampling: Tight analyses via couplings and divergences.\" Advances in neural information processing systems 31 (2018).\n\n[6] Steinke, Thomas. \"Composition of differential privacy & privacy amplification by subsampling.\" arXiv preprint arXiv:2210.00597 (2022).", "other_strengths_and_weaknesses": "Strengths: The paper provides, to the best of my knowledge, the first theoretical analysis of the privacy loss of the synthetic samples generated by DP-trained generative models. Although the setting appears somewhat toyish, the techniques employed, particularly for releasing multiple points, are non-trivial. Overall, this work could serve as a promising first step toward an important research direction.\n\nWeaknesses: The main factor lowering my overall rating is related to the theoretical claims; I feel that the rigor in this work does not meet the bar for ICML. Additionally, the paper could be strengthened by:\n- Including a notation section. For instance, $||\\cdot||$ is typically interpreted as the 2-norm, but here it is mostly used as the Frobenius norm. Moreover, $\\delta_{ij}$, which appears in both Sec 3.1 and Prop 4.2, is never formally defined. \n- Providing an overview of the proof techniques. It would be helpful to discuss the technical challenges and how the paper addresses them.\n- Discussing the implications of the main results. For example, how does Theorem 4.8 relate to privacy amplification? What is the relationship between $\\tilde{G}_{\\Lambda(\\sigma_w, d, \\Delta)}$ and $T(V,W)$?", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper studies the problem of private synthetic data generation in linear regression.

The reviewers agree that the paper presents interesting theoretical results and novel analytic tools. The authors also try their best to address the reviewers' concerns, especially the one regarding the technical flaws. Since most of the reviewers support the paper, I recommend weak accept.
Decision: Accept (poster)