The Gaussian Mixing Mechanism: Renyi Differential Privacy via Gaussian Sketches
Authors: Omri Lev
Vishwak Srinivasan
Moshe Shenfeld
Katrina Ligett
Ayush Sekhari
Ashia C. Wilson
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy; Renyi Divergence; Sketching; Private Linear Regression;
Primary area: other

Abstract: Gaussian sketching, which consists of pre-multiplying the data with a random Gaussian matrix, is a widely used technique in data science and machine learning. Beyond computational benefits, this operation also provides differential privacy guarantees due to its inherent randomness. In this work, we revisit this operation through the lens of \Renyi Differential Privacy (RDP), providing a refined privacy analysis that yields significantly tighter bounds than prior results. We then demonstrate how this improved analysis leads to performance improvement in different linear regression settings, establishing theoretical utility guarantees. Empirically, our methods improve performance across multiple datasets and, in several cases, reduce runtime.

The Gaussian Mixing Mechanism: Rényi Differential Privacy via Gaussian Sketches
Omri Lev!
Vishwak Srinivasan l.f
Moshe Shenfeld
Katrina Ligett²
Ayush Sckhari
Ashia C. Wilson
Massaacusetts Institute of Technology
The Hebrew University of Jerusalem
Boston University
Abstract
Gaussian sketching, which consists of pre-multiplying the data with random Gaussian matrix, is a widely used technique in data science and machine learning. Beyond computational benefits, this operation also provides differential privacy guarantees due to its inherent randomness. In this work, we revisit this operation through the lens of Rényi Differential Privacy (RDP), providing a refined privacy analysis that yields significantly tighter bounds than prior results. We then demonstrate how this improved analysis leads to performance improvement in different. linear regression settings, establishing theoretical utility guarantees. Empirically, our methods improve performance across multiple datasets and, in several cases, reduce runtime.
Introduction
Advances in data collection and storage have enabled the creation of massive datasets, which have necessitated the design of scalable algorithms for efficient processing, analysis, and inference. With the formation of such large datasets, there has also been an increased focus on privacy-preservngg analyses in a bid to protect private attributes [Apple Research, 2017, Facebook Research, 2020, Snap Security, 2022, Ponomareva et al., 2023]. For instance, census data consists of a variety of private information about individuals recorded, and the United States Census Bureau has been taking various measures ensure confidentiality in the data, and has adopted more modern methods since the late 1900s [Bureau, 2019].
A popular mathematical notion of privacy is given by Differential Privacy (DP) [Dwork, 2006, McSherry and Talwar, 2007, Dwork et al., 2014], which is currently the de facto standard for privacy-rreeervigg mechanisms. A private mechanism is a (randomized) function M which takes as input a dataset X, and the key challenge in designing a "good" private mechanism balancing the tradeoff between the loss in utility with the increase in privacy- preseri- nature of the algorithm; it is possible to obtain complete privacy by simply returning noise regardless of the input. but this clearly does not have good utility.
With regard to designing scalable algorithms to handle massive datasets, sketching as a technique [Sarlos, 2006] has led to more computationally scalable algorithms relative to naïvely working with the full dataset; see Woodruff [2014] for a review. Given a data matrix X ngd sketch constructs a compressed representation SX e gxd with < n, where S E x is random matrix. For the case where S is comprised of i.i.d. Gaussian elements,
*Corresoondnce:: omrilevenit.edu Code: https://gitte com/ommrleet//asseeeeeeeooaeeeee
Equal contribution.
39th Conference on Neural Information Processing Systems (NeurIPS 2025).

---

for sufficiently large l it holds that 1 = In with high probability. This property is particularly valuable in machine learning applications that rely on inner-products of the form A B for matrices A and B, as one could now apply Gaussian sketching matrix S to both A and B and largely preserve this Hilbert-Schmict inner product (up to scaling constants). In this work, we study a mechanism based on a "noisy" sketching operation, which we call the Gaussian Miring Mechanism (abbrev. GaussMix) and is defined by
M(X) :- SX of with S ~ Lx,,) {~ (0, Ixxa). S
(GaussMix)
The additive Gaussian noise (hence the "noisy" sketching operation) essentially contributes a constant bias to the inner product between the outputs of GaussMix applied to A and B, as for sufficiently large k and appealing standard concentration inequalities, we have
(SA + oE) T (SB of) = B :
(1)
Thus, this noisy sketch is potentially well-suited for applications involving inner products. The intriguing aspect of GaussMix is that the Gaussian sketching operation contributes to stronger privacy guarantees when compared to the standard Gaussian mechanism.
The first evidence of sketching yielding a differentially privale mechanism was given by Blocki et al. [2012], and later works [Sheffet, 2017, 2019] focused on establishing that GaussMix also provides DP. While it might seem surprising that GaussMix is differentially privale mechanism, the operation can be viewed as instantiating the classical Gaussian mechanism for DP [wwork et al., 2014, Appendix A] for the Gaussian sketched data matrix SX.
Intuition for GaussMix. Interestingly. certain key operations in augmenting mechanisms for improved differential privacy can be expressed as left mutttippppiiinion operations. Two such instances are (1) permuting the rows of the data matrix X randomly [Erlingsson et al., 2019], which can be expressed as left- sef--multiplication of X by a permutation matrix, and (2) subsampling the data matrix at random, which can be expressed as left-multiplication of X by a random matrix whose entries are either or [Kasiviswanathan et al., 2011, Balle et al., 2018]. A rough intuition for why sketching is a reasonable operation for preserving privacy is that SX generates random lincar combinations of rows, which can potentially hide the contribution of any one row. Differential privacy more rigorous notion seeks to ensure that the presence of any one particular row in the data can not be guessed well, even by adversary that has knowledge of the other rows. Note that sketching by itself is not impervious to such a setting: consider a data matrix X where all but one row contain Os, and in this case, it is possible to make educated guesses for what the non-zero row might be from the sketched data matrix SX. This motivates the inclusion of the noise addition in GaussMix, which also covers this adversarial situation. Informally speaking, through our analysis, we observe that the "richness" of the data matrix (quantified by the minimum singular value) contributes to the success of the sketching mechanism as differentially private mechanism.
Contributions. Expanding on the above, our primary contributions, which are both theoretical and empirical, are summarized below.
Tighter Privacy Analysis via Rényi Differential Privacy (RDP). We present new RDP analysis of GaussMix, which to the best of our knowledge, has not been previously explored. Our bounds are simpler to derive than existing analyses and in several cases, are tight with respect to RDP. Notably, our results show that GaussMix achieves stronger privacy guaranteos than those established by Sheffet [2019] for the same mochanism paramcters. Our imprvement extend to scttings that rely on GaussMix, such as Prakash et al. [2020], Anand et al. [2021], Sun et al. [2022], Bartan and Pilanci [2023].
Algorithm for Private Ordinary Least Squares. We use GaussMix to develop diffcrentially private algorithm for lincar regression under bounded data, extending the framework of Sheffet [2017]. Leveraging our new RDP analysis, we derive bounds on the excess empirical risk that, in some cases, match those of the AdaSSP algorithm by Wang [2018], a standard benchmark under domain-bound assumptions. We validate these theoretical results through empirical evaluations, where our method consistently outperforms the baselines of Sheffet [2017] and Wang [2018] across several benchmark
2

---

datasets. Furthermore, we show that retrofitting the improved RDP analysis into the algorithm of Sheffet [2017] yields improved results, further demonstrating the broad applicability of our improved analysis.
Algorithm for Private Logistic Regression. We adapt the algorithm for private linear regression to perform diffcrentially private logistic regression. This specifically works by using a second-order approximation of the loss function [Huggins et al., 2017, Ferrando and Sheldon, 2025] that reduces the problem to a differentially privale quadratic minimization, which makes it amenable to apply GaussMix. We derive theoretical guaranlees for our proposed method and give numerical simulations over certain datasets that demonstrate improvements in both accuracy and computation time over the commonly used objective perturbation [Chaudhuri et al., 2011] and DP-SGD [Abadi al., 2016] baselines.
Organization of the paper. In Section 2, we discuss related work. Section 3 introduces necessary preliminaries. We present the Gaussian Mixing Mechanism and our privacy analysis in Section 4, including comparisons with prior bounds. Applications of our mechanism to DP OLS (Section 5.1) and DP logistic regression (Section 5.2) are given in Section 5, supported by theoretical and empirical evaluations.
2 Related Work
A substantial body of research has investigated the use of random matrix projections for pri- vacy, particularly through the Maanson-Lindenttranss (JL) transform and its variants [Blocki et al., 2012, Kenthapadi et al., 2013, Sheffet, 2017, Showkatbakhsh et al., 2018, Sheffet, 2019]. Sheffet [2015, 2017, 2019] and Showkatbakhsh et al. [2018] are the most relevant our work, as they propose using Gaussian sketches for privale linear regression. Sheffet [2015, 2017, 2019] analyze the crivacy-preserving characteristics of GaussMix for this problem, and show that it achieves (e, -)diifferenntal privacy for certain settings of a, k. Showkatbakhsh et al. [2018] study the same mechanism but under a modified notion of differential privacy known as MI-DP (defined by Cuff and Yu [2016]).
The mathematical intuition for why sketching useful in privacy-sensitive optimization was studied by Pilanci and Wainwright [2015]. They observe that the mutual information between X and its sketched version S. can not be too large, thus providing a form of privacy. However, their analysis is centered around information-theored such as the mutual information, and does not actually provide guarantees of differential privacy. More recently, Bartan and Pilanci [2023] provides another application of Gaussian sketching in the specific context of DP distributed linear regression, based on the results obtained by Sheffet [2015].
principles and quantities
In contrast to these prior approaches, our work uses the stronger RDP framework of Mironov [2017] in its privacy analysis. We derive a simple, closed-form expression for the RDP curve E(a) corresponding to GaussMix, which tight and improves upon the bounds obtained in earlier works. These improvements yield practical gains in the performance of our algorithm for DP linear regression relative to both Sheffet [2019] and other common alternatives such as Wang [2018], and can be further used in other settings that currently use (GaussMix), such as Prakash al. [2020], Anand et al. [2021], Sun et al. [2022], Bartan and Pilanci [2023]. Moreover, we further derive computationally efficient algorithm for private logistic regression. Our numerical experiments demonstrate that these enhancements translate into improved accuracy over standard baselines.
3 Preliminaries
Basic Notation. We denote random variables in sans-serif (e.g., X,y), and their realizations in serif (c.g., X,y resp.). The set (1....,n} n.. is denoted by In]. For vector A E Id its Euclidean norm is denoted by ||] The all-zeros column vecior of length d is denoted by 0,a- The à x identity matrix is Tl and (0, Uk xx2) denotes a h x h2 matrix of i.i.d. standard Gaussian entries. We give more elaborate discussion of notation in Appendix A.
3

---

Differential Privacy. Differential privacy relies on the notion of a "neighboring" dataset, which we introduce first. Two datasets X, X'' are called neighbors if X' is formed by removing an element from X or vice-versa, and we use X = X' to denote this relation. In this work, a dataset regarded as a collection of n real-valued rows, each of length d for n, 2 1. For dataset given to us, we assume knowledge of an upper bound Cx (called the row bound) where ||ai||| S Cx for all i E [n].
Intuitively, differential privacy, formalized in the next definition, requires that a randomized algorithm induce nearly identical output distributions given neighboring input datasets. Definition 1 ((e, -i-Differential Privacy [Dwork et al., 2006]). A randomized mechanism M is said to satisfy (e, -ddifffrenttial privacy if for all X, X' such that X' = X and measurable subsets S C Rango(M).
(X) ES) Se e Pr(M(X)) ES)+
secondary, somewhat stronger notion of differential privacy that we adopt throughout this work is given by Rényi-DP, first introduced by Mironov [2017].
Definition 2 ((a,)(())-RDP [Mironov, 2017]). A randomized mechanism M is said to satisfy (a, ((D)))DPP for some a > 1 if for all X' such that X = X',,
Da (M(X) (X())) <(a))
P(x) Q(अ) )
where QP( - log
E x~Q
denotes the a-Rényi divergence [Rényi, 1961].
The notion of (e, DD- can be viewed as ensuring that the likelihood ratio of events induced by neighboring datasets are uniformly bounded, and 5 in 5EP provides some additive slack on this condition. On the other hand, for any a > 1, (a. (a, as another control that bounds the moments of this likelihood ratio. The latter can be translated into the former; this conversion is explicilly stated in the proposition below.
can be seen
Proposition 1 (Canonne et al. [2020, Proposition
12)). If M satisfies (a, ((a))-DPP then log(ad)
also satisfies (EDP, 8)-DP for any 0 < 6 < 1, where EDP =(a) log (1 2) (a-1)
Both (a, ((a)))DDPP and (s, dD- satisfy key properties such graceful degradation under composition and post-processing. In particular, the post-processing property ensures that mochanism f satisfies either privacy definition, then so does g o f for any (possibly randomized) function [Dwork et al., 2014, Mironov, 2017].
We highlight special family of mechanisms that satisfy (a, ((a))-DRRD for a range of values of a wherein E(a)) grows at most. linearly in a within this range. Such mechanisms are said to satisfy truncated concentrated DP (ICDP) which is defined formally below.
Definition 3 (tCDP [un et al., 2018)). Let p > 0 and w > 1. A mechanism M satisfies (p, w)-DDD if D. (M(X))))(X') S p-a for all neighboring X' and for all a E (1, w).
The (p, wD property lends to tighter translation to (EDP, 6)-DP in comparison to simply picking a E (1,w) w) and instantiating Proposition 1. This fact leads to tighter privacy guarantees for GaussMix as present in the latter parts of this paper.
Proposition 2 (Bun et al. [2018, Lemma 6)). If M satisfies (p, WCCDP, then its also satisfies (EDr, 6D- for all 8 >> O where
p 2/pp log(1/8) if log (1/8) S (w 1)2 p-w w-w log(1/) if log (1/8) > (w 1)2 1p..p.
ÊDP-
Gaussian mechanism. The Gaussion mechanism is a standard baseline for achieving (E by simply adding Gaussian noise to (some function of) the data before releasing it. In our notation it amounts to Mc(X)= = X + of with ~ Ix,, The Gaussian C3
mechanism is 20 xc) -tCD (also known as zCDP Bun and Steinke, 2016]), and (c, (eP
where e = /2 25/5) for any 8 E (0, 1) [work et al., 2014, Appendix A].
'For simplicity, we identify removal of a row with its replacement by da, so the dimension remains constant. This notion is sometimes referred zero-out neighboring.

---

4 The Gaussian Mixing Mechanism
We start by providing new privacy analysis of GaussMix, under the assumption that have a lower bound Xii for the minimum eigenvalue of x (called the scale bound).
For any data matrir X Raa that satisfies row bound Cx and scale bound Xmin. GaussMix with parameters Is and a such that y Cx .0o (12++ > 1 satisfies (a, ppa: k 7))- RDP for any a E (1,7), where yp (a; (a) 2[-11
Lemma 1.
* ka log (1- I[a-1 log (1-
To help understand the role of y, this can be viewed as a lower bound on the minimal eigenvalue of the matrix X X where X == Cx' [XT]] E R( Using this perspective, the noise addition can be seen way to artificially raise the minimum singular value of the matrix X to a predetermined threshold 7, after which a standard Gaussian sketching step is applied. This reinforces the prior intuition that privacy arises from applying Gaussian sketching to a matrix with a sufficiently large minimum singular value.
Proof sketch of Lemma 1. For fixed X, we first deduce that every row of (X) is distributed according to multivariate Gaussian distribution with zero mean and covariance Σ = X X + T Using the closed form expression of the Rényi divergence between multivariate Gaussian distributions, the quantity Da (X())))) of x -ー where æ is the row in X that is zeroed out in X'. This quantity can be bounded and Amin 2 Xmin + o² by the scale bound. We defer the details of this proof to Appendix C.1.
is monotonic function
as xx --='' (Amin (E)) (E))= -0>)= ||=||/
Two key observations from the analysis is that (1) the function &o is non-negative for every a E (1,7) 7) and further bounds the RDP curve of MMX) from above, and (2) for sufficiently large 7; the function & in Lemma 1 grows at most linearly in a in certain range. The latter property is precisely the definition of tCDP (Definition 3).
Corollary 1. Consider the selup of Lemma 1. 7 5/2, then GaussMix satisfies (k/2),,27)) 27/2),,
Tightness of Bound. In our computations, the only incquality that occurs is the one stated in the proof sketch. This inequality is tight when the row in which X differs from X' happens to be the eigenvector corresponding to the minimal eigenvalue of XT This implies that the lemma is light for specific inputs, ensuring the bound is optimal under certain imput assumptions. More precisely, for the set of matrices X E Bxxd such that n 2 with norm bounds Cx and such that Amin(X X) 2 Cx, our bound is achieved with equality for any X such that x x = Cx La; corresponding to the case where X a semi-orthogonal matrix.
Comparison to Existing Literature. Below we summarise the comparison between our guarantees for the (E of GaussMix and prior result by Sheffet [2019].
Our result
Sheffet [2019]
(Corollary Proposition 2)
(Thenrem 2)
h v llllg((
2 1olg///)) llog(4/8)
2,2
7
For a fixed k; the dependence on y in our guarantee is strictly better than the result of Sheffet [2019]: specifically the bound from Sheffet [2019] suffers from the additional 2log(4/4) term. Nunerical analysis based on the exact RDP guarantee (derived by using the conversion from RDP to DP of Proposition 1) provides a larger improvement of Lemma 1 over the bound of Sheffet [2019]; see Figure for plots to showcasing this comparison.
Moreover, we note that with GaussMix the entire dataset contributes to the privacy protection of a single element via mixing. Since Xmin is at most nC
d (sce discussion in [Wang, 2018]), this resembles privacy amplification by shuffling or subsampling, whereby the added noise to other elements contributes lo the privacy protect ion of any element. The dependence of & on the parameters is not trivially comparable since & affects only GaussMix, and the utility of the two outputs might be ar arbitrarily different.
5

---

6p
10000,
d 100.
Our
n 10000,
d 100.
10a
8
10
6-
10
10
4-
10
3-
10
2-
10"6
1
10
10t
102 102 10 10c 105
10c 107
10a
10a
10-
10a
10a
10"
10"
10/
Ami o²
Amn o²
Sheffet '19, Theerem 2
Mixing: (ours), converted via propesition
(a) Required EDP.
(b) Ratio between the hounds.
Figure 1: Amin + o² required for attaining &DP, using Lemma converted to (éDP, 6)-DP via Proposition 1, and compared the bound from Sheffet [2019, Theorem 2]. We plot (a) EDP function of Amin o² and (b) the ratio between the SDP bounds. Our improved RDP analysis reduces the final EDP, illustrating the benefit of our new approach.
Algorithm 1 ModifiedGaussMix
Require: Dataset X Rnxd row bound Cx, parameters k. 6,7,77 T,
1: if T then:
2:
Output: SX + 7Cxx with S ~ (O and & 0,, 4xxa).
3: clsc:
4: Set Ā = max { (Nuin (X C (r - 02) whore 2 2~ ~~,
5: Set 7= V maxxx X,0].
6: Output: SX + #xxEi with ~ N N00 Lxxn) and & ~ (O, Lxxa).
Usage Without Amin- Since the bounded scale assumption cannot. be enforced in the general case, one way to utilize Lemma 1 is by simply using the fact that Amin 2 0 and relying solely on the added noise. In this case, the GaussMix mechanism can be thought of as a complicated counterpart
the Gaussian mechanism. Comparing their privacy guarantees reveals a clear similarity, with vk/y taking the role of 1/a in the Gaussian mechanism. In this case 7 = o² which amounts to quadratic dependence of e on in the leading term (rather than the linear one in the Gaussian mechanism), balanced by Vk, which implies improved privacy results when > Vk. Since the output of these two mechanisms follows different distributions, the privacy-utility tradeoff depends on the use case.
Instance Specific Bound. While setting Amin 0 provides privacy guarantee for any matrix, one might wish to reduce the added noise in data-dependent manner based on XX X). Since this quantity is data-dependent, it must be used in a privacy-preserving manner, which is achieved using Algorithm 1. A similar algorithm was proposed by Sheffet [2017, hm 1], with sampled from a Laplace distribution, and n set either to 0 or to V based on X, rather than interpolating between the two as do.
Theorem 1. Let 8 E (0,1), output of Algorithm 1 is (é(n, 7, k, DD for
1, 11 > and 8/2, and set (lo/(3)/) Then, the
E(n. 7, k, = / /2log(33.7//)
p((aski)) log(%/6) + (a - log(1 1/a) log(a)) (a)
min Teaey
(2)
where p(ack,)) 7) was previously defined in Lemma 1.

---

Proof sketch. The case of y < is the previously discussed Amia = 0 setting. For the other case, note that w.p. 2 1-6/3 we have À 2 Amin X), the conditions of Lemma are met. Since Amin has sensitivity Cx, the privacy properties of the Gaussian mechanism apply to the release of X. Using simple composition, we combine it with the privacy of GaussMix, which completes the proof. We give full details in Appendix C.3.
The quantity E(n. Y, k 6) 2 0 and further can be made arbitrarily small by increasing 7 and Yi we show this formally in Appendix B. As mentioned previously, the parameter y should be thought of as the target minimal eigenvalue, serves the accuracy bound on the estimation of Amin, and 7) controls the privacy loss of its private estimation. Setting 2/vk, Vk, and combining Corollary 1 with the DP implication of tCDP, we get that Algorithm 1 is (c, 6)-DP
2v log(4/6) which matches the privacy bound GaussMix up constant.
where
24
5
Applications
We now demonstrate applications GaussMix for two private learning tasks that can be formalized as linear regression. In each case, we instantiate the mechanism concatenated dataset (X1,Xy) X2)) where X1 E "xx and X2 E Rmdd The application of GaussMix to the concatenation X2) is given by
M(X,, X2) (X1, + (51,52) (SX1 σLi, SX2 + +f2)
where S ~ (NO Ixxn,, & ~ (O,,, laxd;), ), and &2 ~ (N, lxxxd2). If M(X1,X2) satisfies RDP w.r.b. (X1, X2), then by post-processing the inner-product I. defined as
X(M(X1, = (SX1 + o (SX2 + +
(3)
also satisfies RDP. The inner-product IC will form the core component our algorithms.
5.1 Differentially Private Ordinary Least Squares
We begin with the problem of DP linear regression. Let the dataset (X, Y) such that the design matrix X E Raxd and the response vector Y E IR.. Throughout, we make the following assumptions:
(A1) Bounded domain: || < Cx and lys| s Cy for all i E [n] (A2) Overspecified system: n 2 d.
Our goal is to estimate a linear predictor under (e, DP,,, while preserving the privacy of each individual data pair (x. y:). Our non-private baseline is the standard Ridge regression estimator [Tikhonov, 1963, Hoerl and Kennard, 1970]:
0*(v) argmin {ILY -x01 + x110113) X
6
where v 2 0 is a regularization parameter. The unregularized least-squares solution is denoted 0* = (0), and we define the empirical loss as (x. = Y - Our algorithm, summarized in Algorithm 2, uses Algorithm 1 for obtaining privatized version of the pair (X, Y) (interpreted as halves of one joint matrix) by sctting a large enough ? and then solving the resulting least-squares problem. The existence of that satisfies the conditions in Line in Algorithm 2 ensured by the analysis presented in Appendix B. While the structure of our algorithm resembles earlier proposal by Sheffet [2017], our refined privacy analysis under Rényi-DP improves the overall crivacy-utilite trade-off. Moreover, our algorithm exploits Amin in modified way, ensuring that the variance of the additive noise component is always reduced by utilizing the private estimation of Amin (X (X).
Corollary 2. For any 2 the oulput Or.in of Algorithm (DP
These domain bounds appear in many standard DP linear regression settings, such as [Sheffet, 2017, Wang, 2018).

---

Algorithm 2 LinearMixing
Require: Dataset (X, Y) satisfying (A1, A2), privacy parameters (E, 8), parameter k.
1: Find smallest y > 6/2 such that E(n; 7, k; 8) S E, while sctting 1f = 7/VI.
2: Calculate X |]
ModifiedGaussMin (X,Y), + + k, 7, /2 (3/8).
Output: OLin = X X -1 XTY.
3:
Proof. We first note that for any k 2 1, we are guaranteed to find a y in Line such that the target ě(n, y, k, 6) S where 7) = 7/V6 (see Appendix B3. Since we apply ModifiedGaussMix (Line 2) with the appropriate domain bounds, the differential privacy guarantee follows from Theorem 1. Finally, since oLn is a function of Y), which is (s,5)-DP, we have by post-processing that OLin also satisfies (s, (D...
Theorem 2. There crist universal constants cu, c1, 22 such that for any X (0.1) 1] satisfying kx² 2 end, the following holds with probabilily at least 1 -q . exp x {c22kx]]
Lx,y (0Lin) (1 + x)2 (x,y s O (1+ x)2 ( (1+ 110011))
The proof is deferred to Appendix C.4. Notably, in the regime where Cr x Cx 10 and d >>> 1, for a target failure probability 2, setting x /k= max {cod, (Yea) log(s)/)) and k = (1 + 3) max (cod, 1/ez (0gg((/)))) for some finite 3 yields excess empirical risk of O (e--V/max (d, log()))) Cog( (1 (1+ 1100))])) xxxx)(0))) In particular, we note that the first term avoids the multiplicative log(d%/) factor that exists in the guarantees from Wang [2018]. Thus, whenever it holds that Amin (XTT X) < 1 and furthermore Lx,y (6*) < e-1 V max {d, log(}/)) log( Cx (1+1001)) we expect
method to outperform the AdaSSP baseline. Conversely, in high-residual regimes- -whnness-whrre our bound incurs the term x (xx,y when { (X) X) is large-ss that AdaSSP's guarantee enjoy from this minimal eigenvalue in the denominator of its guarantees, AdaSSP is likely to perform better.
To demonstrate the usefulness of Algorithm 2, we have simulated its performance on four different datasets: the Communities Crime dataset [Redmond and Baveja, 2002], the Tecator dataset [Thodberg, 2015], synthetic dataset comprised of Gaussian features trans- formed via an MLP and another dataset comprised of Gaussian features. Full experimental details are provided in Appendix F. We use algorithm. 1 from [Sheffet, 2017] as well as the AdaSSP algorithm of [Wang, 2018] as our private baselines. We further simulated a variant of algorithm. 1 from [Sheffet, 2017] that uses the analysis established in Lemma 1. The AdaSSP algorithm is considered the leading baseline for DP linear regression under bounded domain assumptions [Liu et al., 2022, Brown et al., 2024]. While some recent works, such as [Ferrando and Sheldon, 2025], have proposed practical enhancements over AdaSSP, this method involves significantly higher computational cost and lacks theoretical utility guarantees, as opposed to our method which runs essentially within the same time constants. As Figure 2 shows, our method outperforms the AdaSSP method and the method of [Sheffet, 2017]. achieving lower or equal test MSE across all privacy levels on every dataset. Furthermore, incorporating the analysis of Lemma into the algorithm of [Sheffet, 2017] improves its performance, hinting on the further usefulness of our new analysis technique.
5.2 Differentially Private Logistic Regression
Our second application considers the problem of DP logistic regression, with the goal of developing DP solutions to the ERM problom:
0 = argmin 1 - log (1 + exp { (- zz1)) = argmin
Σ Lo(s;, V:)
0
8

---

Communities & crime dataset
Tecator dataset
Ogo - min[10 2
Opr m min 1
0.200
0.14
0.175
0.32
Text MSF
0.150
0.10
0.125
0.00
0.300
0.075
0.04
0.02
Sop Baseline
for Basellnee
[Alg. Sheffet '17]: 5 2.500
[Alg. Sheffet 117: }= 2.500
ADASSP [Wang '18]
ADASSP [Wang '18]
[Alg. 1, Sheffet '17] Our Analysis: 2.500
Alg. Sheffet '17] Our Analysis: 2.500
Linear mixing (ours): 5 2.500
Linear mixing (ours): } - 2.500
(a) Crime dataset
(b) Tecator dataset
Synthetic dataset
Gaussian dataset
5g = min(10- m))
0.030
[du min )
0.20
0.15
Test MSE
0.006
Teat
0.10
0.025
0.05
0.024
10
19
Zpp Baseline
ESP
Baseline
[Alg. 1, Sheffet 117;: 2 2.500
[Alg. 1, Sheffet 117]: 3 2.500
ADASSP [Wang '18]
ADASSP (Wang '18]
[Alg. Sheffet '17] Our Analysis: } 2.500
Alg. Sheffet '17] Our Analysis: 5 2.500
Linear mixing (ours): 5 = 2.500
Linear mixing (ours): Š = 2.500
(c) Synthetic dataset
(d) Gaussian dataset
Figure 2: Lincar mixing performance on four linear regression tasks. The paramcter k was chosen to ensure negligible approximation error in the sketched solution.
and where y: E {-1,, +1} for all i [m]. Following [Huggins et al., 2017] (see also [Ferrando and Sheldon, 2025)), this problem can be solved by approximating fo(8, y) with a second- order polynomial g(s)= = bn + b1s + b28² i.e. - log (1 + exp(-s}) R u(s), for s E J, where I satisfies yd I E I for all datapoints (z, ensuring the surrogate is valid over the dataset. Substituting = y: TT I, and discarding the constant bo, minimising the surrogate objective reduces to ordinary least squares with a response vector Y = by Y, with 26g
Y = (Vi,..., vnd T. Therefore, we can invoke Algorithm 2, originally designed for linear regression, to obtain a (e, DPP estimate for logistic regression. The utility of this solution
follows via similar arguments those of Theorem 2, with the replacement of C2 with 26p and with an extra factor due to the loss approximation and is presented in Appendix D. However, in this case, the complexity of sketching the data and then solving the linear system (for example, using QR decomposition) will be O(nkd + kd²). In many cases, this one-shot approach is more computationally efficient than classical approaches that use iterative optimization techniques.
To demonstrate this point, we have tested our approach in similar setting to that presented by Guo et al. [2020], where we (i) trained CNN with DP stochastic gradient descent (DP-SGD) implemented using Opacus [Yousefpour et al., 2021] and (ii) used the pre-trained private embeddings for DP fine-tuning of logistic head. The CNN architecture and training hyperparameters mirror those in [Guo et al., 2020] (see Appendix train the head using one of three methods: DP-SGD [Abadi et al., 2016, Youselpour el al., 2021], objective perturbation as [Guo et al., 2020), or with our approach (Linear Mixing as depicted in Algorithm 2). As shown in Figure 3, our approach delivers lower runtime than
for full details). We
9

---

FMNIST Classification
CIFAR100 Classification
0.15
Stp - min SP-)
Ubj. Pert.: 1.18x Faster
0.100
DP-SED: 4.65x Faster
0.49
Errtrrror Rate
0.125
0.100
0.35
dor = min 20112000--000 aal)
0.075
0bj.
Peri 10x Faster
0.000
025
50D: 3.63x Faster
0.000
1074
Epr
Ep Baseline (Non-private) mixing tours) f 4.500
-.* Baseline (Non-private)
Gaussian mixing (eurs) 5: 4.500
Objective Perturbation on (Guo al., 2020)
Objective Perturbation (Gue 2020)
DR.GG
DP logistic regression using features from privately trained CNN on binary subsets of Mishion-MNIST and CIFAR100. We fixed & on l = 4.5d.
Figure 3:
both baselines and achieves consistent accuracy gains over objective perturbation. It further exceeds DP-SGD accuracy for larger values of the privacy parameter e. Full experimental details are provided in Appendix F.2.
6 Discussion and Conclusion
In this work, we revisited the Gaussian mixing mechanism originally introduced by Blocki et al. [2012] and later studied by Sheffet [2017, 2019]. We derived its RDP curve, which yields tighter bounds on the relationship between the noise parameter a and (s, 6), thereby strengthening the privacy analysis of this mechanism. We further demonstrated the practical usefulness this improved analysis by applying (GaussMix) to two distinct machine learning tasks and providing: (i) an improved algorithm for DP linear regression, (ti) an algorithm for DP logistic regression. The analysis used in the proof of Lemma 1 is tighter than that presented in [Sheffet, 2019]. Thus, it also offers performance improvement in other settings currently invoking the results of [Sheffet, 2019], such as [Bartan and Pilanci, 2023].
A key technical property that underpins the usefulness of (GaussMix) is its compatibility with formulations in which terms involving the random projection matrix S cancel in expectation, described intuitively in (1). Identifying additional machine learning problems and formulations that naturally admit this structure and which facilitate an implementation using the Gaussian mixing mechanism is interesting direction for future work, open the possibility for applying (GaussMix) beyond the currently studied linear regression settings. Moreover, this work focuses the case where S is Gaussian. Extending the framework to other classes of irojections, such as those studied by Woodruff [2014], Pilanci and Wainwright (2015, 2016], could enable computationally efficient. implementation of (3).
Broader Impact The paper develops the DP guarantees for the Gaussian mixing mechanism. However, when used in practice, needs to verify all the prior mathematical assumptions we made throughout in order to guarantee data privacy in practice.
Acknowledgements
The authors thank the reviewers at NeurIPS 2025 for their valuable feedback on a preliminary version of this work. AS thanks Gautam Kamath for helpful discussions. The work of MS and KL was supported in part by ERC grant 101125913, Simons Foundation Collaboration 733792, Isracl Science Foundation (ISF) grant 2861/20, Apple, and grant from the Isracli Council of Higher Education. AW was supported in part by Simons Foundation Collaboration on A Algorithmic Fairness. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
10

---

References
Martin Abadi, Andy Chu, lan Goodfellow, Н Brendan McMahan, llya Mironov, Kunal Talwar, and Li Zhang, Deep learning with differential privacy. In Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, 2016., pages 308-318, 2016.
Arjun Anand, Sagar Dhakal, Mustafa Akdeniz, Brandon Edwards, and Nageen Himayat. Differentially private coded federated linear regression. In JEEE Data Science and Learning Workshop, pages 6. IEEE, 2021.
Apple Research. Learning with Privacy at Scale. Apple Machine Learning Research, 2017. URL https://docs-astt assets developer.appee apple. hopple..commml-eeerrchh papers/learning with-privacy-att scale. pdf.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems, 31, 2018.
Burak Bartan and Mert Pilanci. Distributed sketching for randomized optimization: Exact characterization, concentration, and lower bounds. IEEE Transactions Information Theory, 69(6))3880 3879, 2023.
bike. Bike sharing dataset. https://archive.ctt ics. uci dataset, 2019.
Jeremiah Blocki, Avrim Blum, Anupam Datta, and Or Sheffet. The Johnson-Linndenstrauss transform itself preserves differential privacy. In IEEE Symposium on Foundations of Computer Science, pages 410 419, IEEE, 2012.
Gavin R Brown, Krishnamurthy Dj Dvijotham, Georgina Evans, Daogao Liu, Adam Smith, and Abhradeep Guha Thakurta. Private gradient descent for linear regression: Tighter error bounds and instance-specific uncortainty estimation. In Proceedings of the International Conference on Machine Learning, pages 4561-4584. PMLR, 2024.
Mark Bun and Thomas Steinke. Concentrated differential privacy: simplifications, extensions, and lower bounds. In Theory of cryptogruphy conference, pages 635 658. Springer, 2016.
Mark Bun, Cynthia Dwork, Guy N Rothblum, and Thomas Steinke. Composable and versatile privacy via truncated CDP. In Proceedings of the 50th ACM SIGACT Symposium on Theory of Computing, pages 74-86, 2018.
United States Census Bureau. A History of Census Privacy Protections. https://www. census... sow/ibbrrrr//uusaaaaaatoooooooo http:///////111//////////e//e/// comm//omm///////
html, 2019.
Clément Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. Advances in Neural Information Processing Systems, 33:15676-15688, 2020.
Kamalika. Chaudhuri, Claire Monteleoni, and Anand D Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(3), 2011.
Paul Cuff and Lanqing Yu. Differential privacy as a mutual information constraint. Tn Proceedings of the ACM SIGSAC Conference on Computer and Communications Security, pages 43 54, 2016.
Cyuthia Dwork. Differential privacy. In International Colloquium on Automato, Languages, and Programming, pages 1-12. Springer, 2006.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptogrphhy Conference, pages 265 284. Springer, 2006.
11

---

Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends0 Theoretical Computer Science, 9(3-4):211-400 2014.
Ülfar Erlingsson, Vitaly Feldman, Nya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468 2479. SIAM, 2019.
Facebook Research. Protecting privacy in facebook mobility data during the covid- 19 response, June 2020. URL https://reseearch.. facebook. / wwtp://wwaaa....aaooooooooooiiia
Cecilia Ferrando and Daniel Sheldon. Private regression via data-dependent sufficient statistic perturbation. Transactions on Machine Learning Research, 2025.
Manuel Gil, Fady Alajaji, and Tamas Linder. Rényi divergence measures for commonly used univariate continuous distributions. Information Sciences, 249:124-131, 2013.
Chuan Guo, Tom Goldstein, Awni Hanmun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In Proceedings of the International Conference on Machine Learning, pages 2842-3842. PMLR, 2020.
David Harrison Jr and Daniel L Rubinfeld. Hodonic housing prices and the demand for clean air. Journal of Environmental Economics and Management, 5(1):81-102, 1978.
Arthur E Hoerl and Robert W Kennard. Ridge regression: Biased estimation for nonorthog
onal problems. Technomelrics, 12(1):55 67, 1970.
Jonathan Huggins, Ryan Adams, and Tamara Broderick. PASS-GLM: polynomial ap- proximate sufficient statistics for scalable Bayesian GLM inference. Advances in Neural Information Processing Systems, 30, 2017.
Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. What can we learn privately? SIAM Journal on Compuling, 40(3):793 826, 2011.
Krishnaram Kenthapadi, Aleksandra Korolova, lyya Mironov, and Nina Mishra. Privacy via the Lindensraas transform. Journal of Privacy and Confidentiality, 5(1), July 2013.
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk mini- mization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. PMLR, 2012.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Torontro, ON, Canada, 2009. URL https: wtw..cs.toroooo.oooo.o/
//www. cs. toronto.... www.tto..oooooooooo edn/-kriz/ fawaaninn-ettuurs--0000
pdf.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010. URL http: //yann. lecun. wwwc hwdp//nist//../////////////..m//
Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statisties in high dimensions. Tn Conference on Learning Theory, pages 1167-1246. PML.R, 2022.
Frank McSherry and Kunal Talwar. Mechanism design differential privacy. Tn JEEE Symposium on Foundations of Computer Science, pages 94-103. IEFE, 2007.
Tlya Mironov. Rényi differential privacy. Tn IEFF 30th Computer Security Foundations Symposium, pages 263-275. TEFF, 2017.
Mert Pilanci and Martin J Wainwright. Randomized sketches convex programs with sharp guarantees. IEEE Transactions Information Theory, 61(())5096-5))) 5116-15511,, 2015.
12

---

Mert Pilanci and Martin J Wainwright, Iterative Hessian sketch: Fast and accurate solution approximation for constrained least-squares. Journal of Machine Learning Research, 17 (53):1-38, 2016.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to dp-fy ml: practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77:1113-120 2023.
Saurav Prakash, Sagar Dhakal, Mustafa Riza Akdeniz, Yair Yona, Shilpa Talwar, Salman Avestimehr, and Nageen Himayat. Coded computing for low-latenc) federated learning over wireless edge networks. IEEE Journal on Selecled Areas in Communications, 39(1): 233-250, 2020.
Michael Redmond and Alok Baveja. A data-driven software tool for enabling cooperative information sharing among police departments. European Journal of Operalional Research, 141(3):660 678, 2002.
Alfréd Rényi. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium mathematical statistics and probability, volume 1: contributions to the theory of statistics, volume 4, pages 547-562. University of California Press, 1961.
Tamas Sarlos. Improved approximation algorithms for large matrices via random projections. In 2006 47th annual IEEE symposium on foundations of computer science, pages 143 152. IEEE, 2006.
Or Sheffet.
Private approximations of the 2nd-moment matrix using existing techniques in linear regression. arXiv preprint arXiv:1507.0000 507000066, 2015.
Or Sheffet. Differentially private ordinary least squares. In Proceedings of the International Conference on Machine Learning, pages 3105-3114. PMLR, 2017.
Or Sheffet. Old techniques in differentially private linear regression. In Algorillmiic Learning Theory, pages 789 827. PMLR, 2019.
Mehrdad Showkatbakhsh, Can Karakus, and Suhas Diggavi. Privacy-utility trade-off of linear regression under random projections and additive noise. In Proceedings of the IEEE International Symposium on Information Theory, pages 186-190. IEEE, 2018.
Snap Security. Differential privacy at snapchat, December 2022. URL https: //eng. snap. http//ffferentilll-rivvv-------e
Yuchang Sun, Jiawei Shao, Songze Li, Yuyi Mao, and Jun Zhang. Stochastic coded federated learning with convergence and privacy guarantees. In Proceedings of the IEEE International Symposium on Information Theory, pages 2033-003.. IEEE, 2022.
H.H. Thodberg. Tecator meat sample dataset. StatLib Datasets Archive, Carnegie Mellon University, 2015.
Andrei N Tikhonov. Solution of incorrectly formulated problems and the regularization method. Soe Dok, 4:1035-1033 1963.
Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction & estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence, pages 93 93-103. AUAI Press, 2018.
wine. Wine quality data set. https://archive ics www. http://aaaatstt///////e/uuualla 2009.
David P. Woodruff. Sketching as tool for numerical linear algebra. Foundations and Trends in Theoretical Computer Science 10(1-2))1-157, 2014.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-MNIST: a novel image dataset for benchmarking machine learning algorithms. ar preprint orxiv: 708. 077.07747, 2017.
13

---

Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj, Jessica Zhao, al. Opacus: User-friendly differential privacy library in PyTTrch. arXiv preprint arXin: 210. 12298, 2021.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The paper deals with differential privacy via mechanism we dubbed as Gaussian mixing. This is reflected the paper title.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match thcoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as it clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The paper describes the application of the mixing mechanism to linear regression. Furthermore, we demonstrate results on a finite number of datasets which we describe in the paper body.
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model sell-speeifiiation asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, a facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or a speech-to-texx system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algo- rithms and how they scale with dataset size.
If applicable, the huth should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
15

---

3. Theory assumptions and proofs
Question: For each thcoretical result, does the paper provide the full set of assump- tions and a complete (and correct) proof?
Answer: [Yes]
Justification:
The assumptions made in each theorem are described in the theorem
body.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the thcorems, formulas, and proofs in the paper should be numbered and cross-referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The methods and the datasets used are detailed in the paper, along with experimental details section in the paper appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in varions ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary either make possible for others to replicate the model with the same datasct, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference docs require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should doscribe the architecture clcarly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
16

---

(d)
We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e-g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Docs the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [No]
Justification:
Code will be released upon publication.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurIPS code and data submission guidelines (https://nips.
cc/public/ wtwpgeeeeeeeeeaauasssssiiiiiii
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submis- sion guidelines (https://nipp) cc/pcclccc/cc/cccccccccccccccclt http:////aaaa.cpppp///////////// httpg///eeec.eettiissiiioooooooo for more details.
The authors should provide instructions on data access and preparation, in- cluding how to access the data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and basclines. only a subset of experiments are reproducible, they should state which ones are omitted from the script and why. At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/dee /details
Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [Yes]
Justification: The paper contain an experimental section with details of all of the experiments.
Guidelincs:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question:
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
17

---

Justification: All the plots in the paper contain corresponding confidence intervals, claiming the statistical significance of the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/ter teet/ split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (c.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mcan.
It is OK to report 1-sigma error bars, but should state it The authors should preferably report a 2-sigma error bar than state that they have a 96% C1, if the hypothesis of Normality of errors is verified.
For asymmetric distributions, the authors should be careful not show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculatod and reference the corresponding figures or tables in the text.
8. Experiments compute resources
Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: The computer resources of all the experiments are detailed in the paper body.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics https://neures httpp/////cpppcccctccccccieeeeed
Answer: [Yes]
Justification: We have verified that the research performed in this paper conformed with the NeurIPS code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
18

---

The authors should make sure to preserve anonymity (e.g., if there is a special consideration due laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negalive societal impacts of the work performed?
Answer: [Yes]
Justification:
We have included broader impact subsection in our paper.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g,, disinformation, generating fake profiles, surveillance) fairness consid- crations (o.g., deployment of technologics that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from foodback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses no such risks.
Relcased models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implemeenting safely filters.
Datascts that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
19

---

Answer:
[Yes]
Justification: All the datasets are publicly available and their sources are cited in the paper main body.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g,, CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datascts that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced the paper well documented and the documentation provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details of the aataast/code//eee mooel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL include an anonymized xip file.
14. Crowdsourcing and rescarch with human subjects
Question:
For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelincs:
The answer NA means that the paper does not involve crowdsourcing nor rescarch with human subjects.
Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
20

---

Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (TRB) approvals (or an equivalent approval/revie based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects rescarch. If you obtained IRB approval, you should clearly state this the paper.
We recognize that the procedures for this may vary significantly between insti- tutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our L.M policy (https http///eerps..eeeee cc/Conferences for what should or should not be described.
21

---

Appendix to the paper The Gaussian Mixing Mechanism: Rényi Differential Privacy via Gaussian Sketches
Organization In Section A, we elaborate on notation used throughout this work. In Section B, discuss salient property of ğ that appears in Algorithm 2. In Section C, we give proofs for the main theoretical results presented in the main text. Section contains the utility guarantees for our differentially private logistic regression method in Section 5.2. We then discuss details of the various DP algorithms considered as baselines in Section E. Finally, give details of the experiments in Section F, and additional mumerical experiments in Section G.
A Notation
Given a matrix A E mR"x" we denote its elements by Aij and its Sohumn-stack representation
by
vec ()) = (A11, A21...., Ami; A12, Amo
Random variables are denoted using sans-serif fonts (e.g. X,y), while their realizations are represented by regular italics (c.g., X, v)- The L2 norm of a vector A = (a1....,
(a....,02) O.) is given
by (Ei=1 af) and is denoted by ||A||- We denote the minimal and the maximal eigenvalues of a matrix A by Amia (A) and Amax(A). We denote a PSD matrix A by A 1 and PD matrix by A > 0. We usually denote our dataset ( where each x; E Rd in the matrix form X IT)) Then, we denote the j'th entry of x; by x; 2z()). The determinant of a matrix A is denoted by det (A). The set of integer numbers from 1 to is denoted by [n]. The all zeros column vector of size d is denoted by 0₂ = O) We denote by (0, xk2) bj 22 matrix comprised of i..d. Gaussian elements with zero mean and unit variance. We denote by Naym (0, Ia) a d d symmetric matrix whose elements on the upper triangular matrix are i.i.d. and distributed accoring to No, 1). The Kronocker product between matrices A and B is defined via
AuB
Aim
A B =
Am B
Anm B
The l x le identity matrix is denoted by Tk.
B A central property of E(1, 7, k,
Proposition 3. The function E in (2) is non-negative. For fixed values of k, 8, E(1, k, 8) is a decreasing function in n, and satisfies E(n, k, k, E h()) for a morotonically decreasing function h where h(7) + as 7 0o.
Proof. We now show that ε(n, 7, k, 5) 2 0 and further that one can make 6(1, 7, k, 5) as small as any desirable & by increasing 17 and 7. We first note that (p k, 7) is an upper bound on (M(MM))) Canonne et al. [2020], the second term in Ē(n, 7, k, 6) provides an upper bound on the privacy parameter c, and thus is non-negative. Since the first term in Ë(n, 7, k, 5) is non-negative we get that the entire expression is non-ncgative.
Thus, following the validity of the conversion from RDP to DP of
To prove that E(n, 7, k 8) can be made arbitrarily small, we use the result of Corollary which tells us that ip(a; k 7) I ka for 1 < a S Ey and provided that y > 2. However, we 24
note that the minimum in E(n, k. 8) is upper bounded by
ka +
log (3/6)
k
log (3/6)
min 1<a<27/5
<
+
22
a-1
1
57
2
5
22

---

which is derived by substituting a = 27/5. Thus, this minimum is monotonically decreasing in y and can be made arbitrarily small by increasing y. The result then follows since the first term in (2) is monotonically decreasing in 7, and holds further in the case where Vk by picking sufficiently large 7.
C Proofs
C.1 Proof of Lemma 1
The proof relies the next lemma, which establishes the a- a-Rényi divergence between two multivariate Gaussian distributions.
Lemma (Gil al. [2013]). Let X1 (H1, Eni and X2 N (N2, Ez). Then,
(x(xil(x2) (mi p22 (21 + a(2² 21)) (M1 u22
(4)
det (E) + ax 2 E1)) (det (E,)) (det (E2))*
log
2(a - 1)
for all such that a'ii+ + (1 - a)ح - 0.
Proof of Lemma 1. Instead of analyzing GaussMix, we will analyze the transformed mecha- nism
M(X)= = (M(x)) S + +
which, in terms of privacy, is equivalent to M(X). We note that M(X) a matrix of Gaussian random variables, where its columns are i.d. and each column has covariance of
E [ s; + +X)))(( s; + +Gt) = x
Σ x0 + 02Ia
where have denoted S = (si,..,,, and E
Ex). Thus, first note that voc(M(X)) ~ NO, @ (X + o²I2)).
Let X' be our neighbor dataset that is different from X in single Throughout assume that X' is equivalent to X except for one row which is zeroed out (see Section 3). We then show that the proof also covers the inverse case where one row of is zeroed out.
Without loss generality, assume that the differing row the first row of X. Thus, we first note that
I 2 (X X + d2 - L @ (X x' + = II @ (I12T).
Let Σ II (XT X + ll)) and Eg =
=1 I+ 2 (X"T X' + IIIa). Now,
E, a Σ1) I @ x x o
and since E vec(M = E [ee((M(X))
0 by using the algebraic identity
det (Tg 8 A) = (det (A and by using (4) we get
k
det (-azjeT x d21d)
(M((I))I)(E')) = 2(a-1) 1) log (det (XT + (1)) - (XTX I 1
5
For invertible matrix A, the matrix determinant lemma states that det (A + T) = det (A) (1 + A
23

---

Since the matrix X X + o is invertible whenever o² > 0, this further tells us that the denominator of (5) can be simplified to
(det (x x + )la)) 1-a (det (x" X - x) (det (X X + o daI))) 1-a (dot (x X o )Qll ((()))((()) (1 21 (x x+ +o )1)
= det (xTx + Ta) (1 - 2 (X X + 12))
Thus, we further have
det (-a0ia) + X X + 0²La)
(det (XT X + o' a (X T X 02Id - 21 )
det (-axrel T + + X + o )'ll))) ) -11- x -21) det (X + oPIa)
Similarly, we can apply the same determinant identity to det (-ar1s + +x X + )² and
get det (-ax10] + x =1 -ox ox X o²Ta)- x- det (X x o
Next, we note that this yields the next simplified form for D Da(M(X)IM(X'); D=(M(x))((('))
log ((1 ozr (X X T2 12)) 10000=]((20 (x X + -)
2(a - 1)
h log
(1 - x (X X T -1=1)
(6)
2(a - 1)
1 o (X X + T2Ta)-1m
We nate that the function (1-1)* is monotonically non-decreasing function of in the range
0 st
1 for a > 1. To see this, note that
1 1 ol
11 [1-)) 1)a
a + 1 al (1 1) at) {a log(1 (1 - t) - loog11 - at) = 1-6
a a(a - 1)t
01
log
=
which is positive in the range 0 5 < 1 (recall that > 1). Thus, to further simplify (6),
will try to find upper bound z (XTX + - To that end, note that for general symmetric positive-definite matrix we have
|
x AA-1
1 x
Amin (A)
where equality is achieved whenever x is the eigenvector of A that correspond to Amin(A)
Then, using this relation with regard to XTX X T and using the identity
Auin (X X + I Amin (X
X) +
yields
||,,1' 2 X) + 0
x. T oTT) Xmiul X
for all i = 1,...,
Since we know that max
iE[n] ||ا;|| s C2 we further have
C2 Amin (X X) + 0
a. <x X +
2. -a
24

---

This further leads to the next final upper bound on the Rényi divergence:
De(M(X))I(()))
(1 x (X X X L2 2x1)
2(a 1) log
ox (XT X + o2Ta) 1m
1|r 112
k log
Amiia (X X)+t0²
(7a)
2(a 1)
al|x,11= Amina (X X)+02
ka
k 2(a 1la-11 1) log 1 1 Amin (TT) + 0²
|,11l12
a |||1a112 Amin (XT x) + 0²
2(a 1)) log
where (7a) requires that a < Amin xX)+0
Then, since a similar analysis holds when we replace 21 with a general point 24, the worst case divergence between X and an X that is changed by zeroing out one entry x; is
||=
sup Da(M(X)IIM (x())
kE(x)
ko 2(aa- - 1)
log (1-
Amin (1-Aatn |x:;1 (X) + +0²
k
a ||=x,1?
I sup (E(m]
log 1
2(a -
Amin (X X) + +
ka
C² Amin (X (X)
k
aC²
1 2(a - 1)
log
1
log 1
+ +
2(a 1)
Amiu (X X) + +
ka
O
aC
5 2( -11 1) log
1
2(a 1) log 1
(8a)
Aminn + 0²)
Amiu + 0²
where (8a) is again by the monotonicity of (1-1)- TToot and since Amiu (XTX) X) 2 Xmin, where
a S min "mminta? |=,]I" Amintaa and the bound holds whenever Amin + 0² > C2. Finally,
note that since a-1> 0 for all > and since a log (1 (1-x == for all a > (this follows since the function is for a = and since its derivative is positive) this upper bound is non-negative and valid upper bound on this divergence.
Ct ) log (1- ac3
For the case where one row of zeroed out, we note that we have X' + 02lla X X + lblla I,a. Then, (6) is replaced with
k log
(1 (1+ +
Da(M(X))M((')) = 2(a - 1) 1 + oar] (XTX + o²T
Now, we define the function f(t; a) log
(1-1)a T-oat
-log
[1+r)= Ttat
Then, note that f(0; a))
and further since and at < 1 then
[t: a) = 2a 1- (at)²
f2 20
0t
1
and thus f((;a) 2 0 for all L < , and get that the maximum between the two divergences row. Thus, by finding the o² that
is always given by the case where X' contains makes (8a) equal to e we guarantee that our mechanism is (a, Réééyi--DD
holds. However, since throughout we have Σ₂ = En x with Σ₁ = XT X + - by using the formulas for the inverse of rank-1 update we get
remains to validate that the condition a + (1 - a)
Σ 112 T 21
1/2
a +(1 1l-)E E--//
La (Ia+(1-0))) (l-a).
Σ
1/2
x 5-1 5z
25

---

We note that since Σ1 > 0, for this term to be positive definite it suffices for the middle matrix to be positive definite. However, since this matrix is rank-1 update of Ha its eigenvalues are I's and an additional eigenvalue that is given by
1/2 24 21
1 E 23
1+ 1+ a1
a)
1
Σ
I2.
1 x Ej 24
We note that this term is positive whenever a S
However, since x
Dj
xs
S
12:11
x. _ a
Xmn ta
this inequality is satisfied by the restrictions we have on the domain of a.
C.2 Proof of Corollary
Proof. We start by defining the difference function
Akk a) = ka
272 2(a (1--1) 1) log (1 ) + 2(a - 1) log 1 91-
ka
Our goal is to find when A(k, a; 7) 2 for < a < 7. We note multiplying by the positive
factor 2a² 1) and cancelling the term h. > 0 gives the equivalent condition
G(a) == a(a 1) ary log ( (1-1) 1) + 7a log [1- (1- a 2 0, <<a<w,
where w will be specified shortly. On a = we further get G(1) = 0. Moreover,
Ga = 2a 1 - 7² log (1- 7) a-a'
72
and multiplying by ( - a) (recall that a < 7) shows (a(a) has the same sign as the quadratic
H(a) == (7)
=(20 - 1)(7 - -a) - -ooo-- (1-
7 - -q2
=22a² 1 2 + log (1- - a - ( (1 22 (1- )1
We define the discriminant to be
AF = 1 + 27 72 log 1 ))
2
87 (100+ 1008(1111 (1-2)
which is non-negative. Thus, H has two real roots
722 log (1 1/1) + 27 + 1 VAH
Omax / min
4
and H(a) 2 O for E [Omin; mmax) since the coefficient of the quadratic term H(a) is
negative. However, note that Omin < 1/2 for all y > 1 and moreover Omax for y 5/2 and Omax < for all > 5/2. Thus, since the derivative is positive and since G(1) = 0.
setting w == amax yield Ga(a) 2 0 for every 1 < a < w and thus the inequality G(a) holds throughout that interval, whenever 7 > 5/2. The proof completed since Ommax
for all 7 1.
C.3 Proof of Theorem 1
We recall that the sensitivity of the minimum eigenvalue Xxin X) is C (sce, for example Sheffet [2017], Wang [2018]). Then, by using the standard formula of the Gaussian mechanism [woork et al,, 2014, Appendix A] we get that À is (22log(3.75/))) 8/3) release
26

---

of X X). Using Lemma 1 and Proposition 1, we note that whenever Amin (XT x y the release of the output in both cases satisfies (E, (E,63))-D where
{
log (3/6) (ax 1) log (1 1/4) - log(a)
8=
min K<aRy
(f(askk)))
The first case (when y S T) trivially satisfies this. However, for the second case (whenever r), this is satisfied only if 772 + Amiul (XT X) y, which by using the incquality
172 + Amin( (X X) 7 Amiu (X T X) + C nxx22 Amin (X X) + n 1
corresponds to having 2 T (we note that the case Ā = 0 immedialely satisfies Amin (X (XTX) + of2 2 y since then we have 17" = =)) Thus,
72
(a P ( + Amin (X (xTx) = exp
Then, using simple composition [Dwork al., 2014, Chapter. 3] and substituting N /2 log(3/) yiclds the desired result.
C.4 Proof of Theorem 2
Proof. We first establish the performance of a method that adds noise with a general level o, namely,
Orin = ((SX o
( (SX + = (SX + + (SY + ot2).
Then, we can rewrite OLin in the next form
Y 0g
X
Onin = argmin
(5)
oLd
0
9
Now, since rank((XT, olla, 0z) T) d and since o² 2 O, by Pilanci and Wainwright [2015,
Corollary. 2), whenever h: cad
x w.p. at least 1 0 exp [c we have
(fLm() + o || ? s (1 + x)² (|Y- x0" (0²)]1 0² 110 (03)11 (22))²+02))
We note that this further implies that
(OLm( S (1 + x)2 XI ( + 18113)
Thus, we can write
Lxy((Oran) - (1 Lxx S (1+ x)2 (18- xx0 a| x 11 + 0²(1 + [101113)
=o(a+x)200 (1+10019))
where the last inequality is by Wang [2018, App. B.2,. Now, we note that in both of the cases of the algorithm the magnitude of the added noise is at most 7C* + C.), where ? is determined by the calculation done in step 1. Thus, since the bound is monotonically increasing in d² we can further use the upper bound
(fra)) - (1 + x) x) (x,x O (11 (11 (1+x) + ct) (1+ (1+107?)).
(9)
We further note that
((0,y,k.6)= /2 /2g log (377/8)
((a;k,,)++ (ag() -o/(a)))og(())
min Kaay
a-1
2k (3766)))/))
{ ka
+ log(3/6)
min
cxo<2//6
27
-
2/ 13/2klog(33711 (3.768))))
γ
27

---

Thus, equating this upper bound suggests further that y = (Vklog((/8) and using this bound in (9) leads to
(1+ -L+xxaaa-0-xxxxxx0000000-00-)-00 = (klog(/0)(C3 + +x)] (1+ (1+1001)))
The proof finished since this holds for any X under the constraints the theorem.
D Utility Guarantees for Logistic Regression
We now demonstrate utility guarantees on our method for DP logistic regression, presented in Section 5.2. Those derived similarly to Theorem 2, by considering both sources of errors: the error of approximating the objective with a polynomial and the empirical error of the linear regression solution. Throughout the proof, we denote by 9 the private solution obtained by scaling the putput of Algorithum 2 by b.. We also let 0* denote the minimizer of the
2bg
approximated loss, given explicitly by bi (X X We further denote the empirical logistic loss via
2b
(x) = Σ log (1 + exp (-y,0,0)
and the approximated empirical logistic loss via
(-
(xXTV)
(_xTx) 0
Lx,y(0) (0) = dn + 0io
+ 12oT
b7
b2
bj
bo
||
+
X8
4nb2
2b
bi
b2
b
bo 4nb2
||
+
F
X,
Y. 0
262
We note that Corollary guarantees that our logistic regression solution obtained by minimizing this surrogate is private. We now present the utility guarantees this solution.
Corollary 3. Assume that ||, 12 s Cx, lual < C2 and y Ø- S Q and y. Ø s Q for all i [n]] and for some finite Q > 0. Let (bo, 62) chosen such that
max eE[-Q.Q1
- log((1 + t - (bo + bis + bys?) S
(10)
Then, there erist universal constants Cos C1, C2 such that for any x satisfying 1x? > and the following holds with probability at least 1 - C1 exp [-cokx?):
- - (0) - (1+ (1+ (1 (1 (13)
bu
4b2
=0 ( (1+ x)+x)22 lozel 1188)
(1 [0. (10111))
28

---

Proof. We first note that
(xyr - (1+ x) 0 S (xy (1 xX (
(11a)
(xx (0+) + (x, - (1 + x 0
+(1+x) 0 (1+x
Lxy +1+
- +1+ 2xx 0
(11b)
(1 (1 x1+ 14 (1- x) bn
bi
||8)13
(11c)
Anb2
b2 F
X,
11 v (1 x1+x)²F
X,
bi
r,
262
2b
where (11a) is by the optimality of 0" (11b) is by (10) and (11c) is by the definition of (x,((0) and by the assumptions Ma.. 0" S Q and yar 0 & Q. Then, the final result
follows by using Theorem and since this case lys| = 1, thus || = n and Cy 1.
When we take X < 1, the bound acquires an extra 2q term in the excess risk, introduced by the polynomial approximation.
E
Algorithms for DP regression
E.1
Linear regression
E.1.1
AdaSSP
Algorithm 3 AdaSSP [Wang, 2018]
Require: Datasct (X,Y); Privacy paramcters 8; Bounds: max
||a:|| < 2
max iE/n|
1y:1
<
vE[n]
C².
1: Calculate the minimum eigenvalue Amin (XT (X)...
2: Privately release Amin max
Amin + Moo(99/5033 4/3
lo/(4/a) 4/3
C2. 0
where I~ 1).
3: Set A = max (0. v Valog(%/s) 1og(23
Xmin
4/3
4: Privately release X X + Oo
En for & ~ Noym La)
4/3
5: Privately release XT = XT y + Vlog(//)Cxxxx Eo for & ~ (o,
4/3
6: return 7- (XTX+MI +Ta)
XT
29

---

E.1.2
Algorithm 1 from Sheffet [2017] and our proposed modification
Algorithm 4 Sheffet's Algorithm (Original)
Require: Datasct (X,Y); Privacy parameters E, 6, Bounds: max
||>;||
I C
X
max ié|n
Bil
Cy: Hyperparameter k.
1: Compute Amin == Amin (X))),
2: Set y f- 4[C3+03)) (12h log (3) + 2og (1)).
3: Sample S~ 50,
4: if Amin > > 4(C3 +C3 (og(11) for Lap [(3++
then
e
5: return 0 + ((SX) (SX) (SX)
6: else
7: Sample noises (0, Txdd), & (N(
8: return H - ((SX + + (SX + +(1) TSX (SX + (EY +
Algorithm 5 Sheffet's Algorithu with Our Analysis
Require: Dataset (X,Y); Privacy parameters e, 0, Bounds: max
||=;;|*
<
C
X
max iE(n)
1
(E[n]
Cý: Hyperparameter k.
1: Compute Amin = Amin (XX, min 2: Set y Icaey
{ro(a5 ( log (1 2)
log(18) 5e/2.
a-1
3: Sample S ~ NN, Ixx))-
> + 4(0 + (3g for ~ Lap
(4C
4: if Amin
then
e
5: return 0 ((SX) (SX)((S)
6: clse
7: Sample noises E (0, & -N(0, Iz).
8: return 0 - ((S.X + (SX +*+)) (SX TSY +762)
E.2 Logistic Regression
E.2.1 Objective Pertubation
Algorithm 6 Objective Perturbation [Kifer et al., 2012]
Require: Dataset (X, Y); privacy parameters and 8; Bound ||>ı||| < Cx for all i [m];
1: Set a (1s+810g(3/6) Cx and A
c
2: Sample b ~ (0 (l)
2
3: return 8 +- argmin
E log (1 + exp (-y.0 0}) +
|01
2n
F
Experimental Details
All the linear regression experiments were run 12th Gen Intel(R) Core(TM) i7- 12552U and all the logistic experiments were run on an NVIDIA A100 GPU.
F.1 Linear Regression
For the linear regression experiments, we used four datasets. The first two are real-world datasets: the Tecator dataset [Thodberg, 2015] and the Communities and Crime dataset [Red-
30

---

mond and Baveja, 2002]. We have used a random train-test split of 80%/20% for generating train and a test set.
The other two are synthetic datasets where the responses were generated via the linear model yi x. Oo of, with 8g sampled unit vector uniformly from the (d 1)ddimension sphere, & Unif(-1,1), and o= = 0.1.
In the first syuthetic dataset (termed Gaussian dataset), the parameters were 8192, d 512, and the covariates were sampled as ~ (D, (Q,QQ)) )) where Q E Rx is random orthogonal matrix with q = 4, ensuring the data lies on a 4-dimensional subspace. The matrix Q was generated via QR decomposition of random malrix with i.ddd standard Gaussian entries.
The second synthetic dataset (termed the synthetic dataset) was constructed as follows. First, we sampled latent covariates T; ~ (N(0, I12). Then, we generated final covariates using a two-layer neural network:
6W2 + b1) + b2).
where d(.) is the element-wise sigmoid function, W1 b1 ~ N (0, 10- Iιo0), and b2 ~ (0, Ia). In our experiments, we have fixed d = 29.
W2 ~ NO Ila 100),
For both synthetic datasets, the train and test sets were generated independently, using the same fixed & but with independent covariates and additive noise.
In all cases, we normalized the training data so that the maximum 4--norm of any training sample was 1. The test data was scaled using the same normalization factor the training data.
The baseline (non-private) estimator computed as θ = (XT X y for X = 10 ensuring invertibility in all cases. We report the mean squared error (MSE) for both the train and the test set, computed as the squared error in predicting ys via x, 0. All results are averaged over 250 independent trials, and we report both the empirical means and confidence intervals.
F.1.1 Algorithms
Our algorithm was implemented as described in Algorithm 2. The AdaSSP algorithm was implemented based on [Wang, 2018, Alg. 2], following the procodure detailed in Ap- pendix E.1.1. Our second baseline, from [Sheffet, 2017, Alg. 1), was implemented according to the description in Appendix E.1. This implementation matches that of [Sheffet, 2017, Alg. 1), except. for an adjustment to account for a factor of 2 in the parameter w, which arises due to using the zero-out neighboring definition rather than the replacement definition. In the variant of this baseline that incorporates our improved privacy analysis, we replaced the original noise calibration with bounds derived from Lemma 1, translated to (c, 0)-D using the conversion provided in Proposition (see also Appendix E.1.2).
F.2 Logistic Regression
In this set of experiments, we trained a logistic regression classifier for a binary classifica- lion task without applying any regularization. Our non-private baseline is the standard crrrisstieegessiiio solver from the sklearn. linear linear_modell library. The private baselines are the objective perturbation method (described in Appendix E.2), where the minimization is carried out using torch. oithio.pimmmm. LBFGS with a maximum of 500 iterations and a tolerance optim.LBFGS
of 10-6, following the setup of [Guo et al, 2020], and DP-SGD [Abadi et al., 2016] as implemented in Opacus Yousefpour et al. [2021] with a batch size 1024, 10 epochs, and a learning rate of 0.5. While DP-SGD may benefit from hyperparameter tuning, our method requires only one; to avoid spending additional privacy budget on tuning, we use a fixed, reasonable configuration. We also fixed the parameter on 4.5d.
We conducted experiments on the Fashion- [Xiao et al., 2017] and the CI- FAR100 [Krizhevsky and Hinton, 2009] dalasets, using the implementations provided in torchvision datasets. www.siaaees.dssss...o.. From each dataset, we selected only the samples corresponding to classes 3 and 8, and relabeled them as -1, to fit the binary classification setting. We used
31

---

the standard PyTorch train/test splits and normalized the training data by the maximum L2 norm across all training samples, ensuring that each training sample has norm of at most 1. The same normalization factor was then applied to the test set. The train and test loaders were generated using torch. utils data. DataLoader with shuffling enabled. In Appendix G.2 we present additional simulations with the CIFAR10 [Krizhevsky and Hinton, 2009] and the MNIST [LeCun and Cortes, 2010] datasets.
The network architecture used is a compact convolutional neural network for RGB image classification. It consists two convolutional layers with ReLU activations and max pooling, reducing the input to a 64-channel feature map of size 8x8. The flattened features are passed through fully connected layer with 128 hidden units and ReLU, followed by final linear layer that outputs class logits. In both of the experiments, we have first trained this network end-to-end using the DP-SGD primitive implemented Opacus [Yousefpour et al., 2021], where we have set the clipping parameter to 4.0, learning rate to 0.001, the number of epochs to 20, and the batch size to 500.
Performance metrics are averaged over 50 independent runs, and as before, we report test accuracy along with confidence intervals. Runtime comparisons show the ratio of execution times for the largest simulated 6.
G Additional Experiments
G.1 Linear Regression
We have simulated additional four datasets: the Boston housing dataset [Harrison Jr and Rubinfeld, 1978] that contains 506 measurements of 13-dimensional features with the goal of predicting house prices in the Boston arca, the Wine quality dataset [wine, 2009] which contains 1359 measurements of 11-dimensional features, with the goal of predicting wine quality, the Bike sharing dataset [bike, 2019] with the goal of predicting the count of rental bikes, and another artificial dataset that follows the same description that of the Gaussian dataset but now with i.i.d. features where the distribution of each entry is (ni ([-1, 1)). The additional results are presented in Figure 4.
G.2 Logistic Regression
We have simulated two additional datasets: the CIFARIO (Krizhevsky and Hinton, 2009] and the MNIST [LeCun and Cortes, 2010) datasets, using the same logistic regression setting, The additional results are presented in Figure 5. Both settings demonstrale the computational improvement of our method, well utility improvement for range of the simulated values of E.
32

---

Wine dataset
Uniform dataset
Pap min(10
0.0225
Bee = min(10-3 [P)
0.4
Test MSE
0.0175
0.3
0.0150
0.0125
0.2
0.0100-
0.0075
0.0050-
0.0
0.0025
10
12
10.
10
13P
Edi
Baseline
Baseline
[Alg. Sheffet '17]: ; 2.500
[Alg. 1, Sheffet 117: ; 2.500
ADASSP [Wang '18]
ADASSP [Wang '18]
[Alg. 1, Sheffet '17] Analysis: ; 2.500
[Alg. 1, Sheffet '17] Ana Ana mallysss: 5 2.500
Linear mixing (ours): 1 2.500
Linear mixing (ours): 2.500
(a) Wine dataset
(b) Uniform dataset
Boston Housing dataset
Bike sharing dataset
Pap min(10 -
0.11
Bee = min(10 1P)
0.10
0.09
0.08
0.08
Text
Test
0.07
0.00
0.06
0.05
0.04
0.04
10
18F
107
19
10
10
Eot
Bascline
Bascline
[Alg. Sheffet '17]: 5.500
[Alg. 1, Sheffet 117: = 5.500
ADASSP [Wang '18]
ADASSP [Wang '18]
[Agg. 1, Sheffet '17) Our Analysis: ; 5.500
[Alg. 1. Sheffet '17) Our Analy lsiis 5 5.500
Linear mixing (ours): ~ 5.500
Linear mixing (ours): 5.500
(c) Boston housing datasel
(d) Bike sharing datasel
Figure 4: Linear mixing performance on the additional four linear regression tasks.
CIFAR10 Classification
MNIST Classification
dop = min(10 0bj Pert.: 1.22x Faster
One = min[10 (.))) Qbj. Part.: 1. 1.x Faster
0.35
Test Error Rate
0.30
DP-50D: 4.88x Faster
Test Error Rate
SP-:0D: 4.91x Faster
0.25
0.20
0.20
0.15
0.10
10
107
12
10
Egp
Eoe
Baseline (Nom private)
Baseline (Nov-private)
Gaussi an mixing (ours) E; 4.500
Gaussian miking (ours) 5 4.500
Objective Perturbation (Guo al., 2020)
Objective Perturbation (Guo et al., 2020)
DP-SGD
DP-SGD
(a) CIFARIO
(b) MNIST
Figure 5: DP logistic regression using a privately trained CNN feature extractor on binary subsets of CIFAR10 and MNIST.
33


Reviews:
[{"review_id": "HxkIOJtpd5", "reviewer": "Reviewer_yhdg", "summary": "This paper provides a tigher (Renyi DP) analysis for well-known Guassian mixing mechanism (GaussMix), which pre-multiplies the data matrix with a random Gaussian matrix (traditionally used for row mixing and reduction) before adding DP Gaussian noise. \n\nParticularly, applications such as linear models which depend on cross-correlations of two matrices (e.g. features and labels) benefit from Gaussmix. GaussMix can be applied independently to each matrix, and the random matrix cancels out in expectation whp.\n\nTheir contribution is based on the observation that sketching itself can contribute to the privacy of outliers (in addition to dp noise) when the data matrix has large enough smallest Eigen value.\n \nTheir bound (Lemma 1, and Theorem 1) improves over Sheffet[2019]’s bound (which includes an additional term ($2 \\log(4/\\delta)/\\gamma$)) and outperforms well-known AdaSSP baseline for linear regression. Additionally, it also boosts Sheffet[2017]’s algorithm.   \n\nGaussMix can also be used for logistic regression using a 2nd-order approximation of the loss function provided by [Huggings et al. 2017]. GaussMix with this new analysis provides improvements in the test errors over the objective perturbation baseline, in addition to significant computational saving (due to sketching).", "questions": "Comments/Clarifications: \n\n1)\tDid you observe any improvements in the experiments when data dependent noise is added with $\\lambda_{min}$ >0?\n\n2)\tHow does the performance of logistic regression with our bound compare to that of a single layer trained using DP-SGD?\n\n3)\tFor logistic regression, any specific rational for privately obtaining (with DP-SGD) the embeddings needed for private finetuning? You could have privately finetune on the embeddings obtained non-privately?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength \n1)\tThere is no prior work on the RDP analysis of GaussMix. The improvement in $\\epsilon$ is tangible (Figure 1), and translates into improved accuracy in the regression experiments.\n2)    The problem is a high impact. The GaussMix mechanism provides computational benefits in addition to privacy.  \n3)  The bound can be used independently  to also improve a prior algorithm ([Sheffet 2017]).\n4)  It seems there are no numeric restrictions on the bound from Theorem 1. $\\epsilon$'s can be made arbitrarily small, making the bound practical.   \n5)  Authors provide utility statement for linear regression which asymptotically match a baseline's utility statement. \n5)\tGenerally well written. Authors make an effort to explain the  intuition --- DP noise boosts the minimum Eigen value of the sketched matrix to improve the privacy guarantee.  \n\n Weakness: \n1)\tIt's unclear how this method will stand against the gold standard baseline of DP-SGD when training a single layer logistic regression. The experiments do not include DP-SGD.  I think comparison with DP-SGD will only  strengthen the work, even if the method performs slightly inferior to DP-SGD in the worst case, if the computational benefits due to sketching are significant.", "was_revised": true, "final_justification": "My doubts have been resolved, authors should include experiments on DP-SGD with the next version. \nOverall, a good contribution, and justifies acceptance.", "rebuttal": "We appreciate the reviewer’s positive feedback and acknowledgment of our work’s strengths. Please find below our detailed responses to the points you raised.\n\nWe agree that DP-SGD is an important and widely used baseline in the literature, particularly due to its strong theoretical guarantees.\nTo address your suggestion, we have extended our experiments to include DP-SGD as an additional baseline on two representative datasets. We selected a reasonable fixed set of DP-SGD hyperparameters to ensure a fair comparison without incurring additional privacy cost from hyperparameter tuning (which we view as a potential drawback of DP-SGD, especially compared to our proposed mechanism, which requires tuning only a single hyperparameter). As shown in the attached table, our method outperforms DP-SGD in terms of runtime, and in these specific settings, it also achieves higher test accuracy for some settings of $\\epsilon$. We believe these results highlight the practical value of our method, particularly in scenarios where computational efficiency and simplicity are important considerations. We will add these additional simulations to the final version of our manuscript. \n\nRegarding the other points raised by the reviewer:\n    \n1. Usage with $\\lambda_{\\min} > 0$: Our method can be applied in cases where $\\lambda_{\\min} > 0$, and does not necessarily require that this eigenvalue is zero. However, note that our approach relies on $\\lambda_{\\min}((X,Y)^{\\top}(X,Y))$ rather than $\\lambda_{\\min}(X^{\\top}X)$. The former tends to be small in settings where $\\underset{\\theta}{\\min} ||Y - X\\theta||^2$ is small. This distinction implies that our method is expected to outperform AdaSSP when $\\lambda_{\\min}(X^\\top X)$ is small, whereas in regimes where this eigenvalue is large, the guarantees in [2] suggest that AdaSSP benefits more due to its inverse dependence on $\\lambda_{\\min}(X^\\top X)$. To clarify this point and the setting simulated in our work, we have added a table below reporting the observed minimum eigenvalues across all simulation settings.\n    \n2. Tuning Private Embeddings: We appreciate your observation that our method can also be applied to fine-tune embeddings obtained non-privately. In this work, we followed the setup proposed in [1], which motivated the need for privately fine-tuning a logistic head. Our goal was to demonstrate the effectiveness of our approach in this setting, demonstrating its effectiveness in a commonly used setup.\n\n\n| Method               | ε = 0.1 | ε = 0.42 | ε = 1.78 | ε = 7.50 | ε = 31.62 | Slower by |\n|----------------------|---------|----------|----------|----------|------------|------------|\n| FMNIST (DP-SGD)      | 0.155   | 0.040    | 0.030    | 0.025    | 0.020      | 0.833      |\n| FMNIST (Obj. Pert.)  | 0.200   | 0.065    | 0.025    | 0.020    | 0.015      | 0.384      |\n| MNIST (Obj. Pert.)   | 0.350   | 0.155    | 0.070    | 0.040    | 0.025      | 0.666      |\n| MNIST (DP-SGD)       | 0.180   | 0.110    | 0.100    | 0.045    | 0.027      | 0.188      |\n| **FMNIST (Ours)**    | **0.125** | **0.030** | **0.025** | **0.014** | **0.0125** | --         |\n| **MNIST (Ours)**     | **0.315** | **0.130** | **0.080** | **0.045** | **0.028**  | --         |\n\n\n| Dataset                           | Crime         | Tecator        | Synthetic      | Gaussian       | Wine           | Uniform        | Housing        | Bike           |\n|----------------------------------|---------------|----------------|----------------|----------------|----------------|----------------|----------------|----------------|\n| $$\\lambda_{\\min}(X^{\\top}X)$$      | $4.3 \\cdot 10^{-4}$  | $7.3 \\cdot 10^{-16}$  | $1.5 \\cdot 10^{-14}$  | $6.5 \\cdot 10^{-16}$  | $7.6 \\cdot 10^{-6}$  | $1.1 \\cdot 10^{-13}$  | $2.4 \\cdot 10^{-6}$  | $7 \\cdot 10^{-17}$  |\n| $\\lambda_{\\min}((X,Y)^{\\top}(X,Y))$ | $4.3 \\cdot 10^{-4}$  | $6 \\cdot 10^{-16}$    | $1.27 \\cdot 10^{-14}$ | $2.4 \\cdot 10^{-16}$  | $7.4 \\cdot 10^{-6}$  | $9.6 \\cdot 10^{-14}$  | $2.4 \\cdot 10^{-6}$  | $3.5 \\cdot 10^{-17}$ |\n\n\n\n\n[1] Chuan Guo, Tom Goldstein, Awni Hannun, and Laurens Van Der Maaten. Certified data removal from machine learning models. In Proceedings of the International Conference on Machine Learning (ICML). JMLR.org, 2020.362\n\n[2] Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction \\& estimation in unbounded domain. In Proc. 34th Conf. Uncertainty in Artif. Intell. (UAI), pages 93–404103. AUAI Press, 2018."}, {"review_id": "e4sK0YbPkb", "reviewer": "Reviewer_HkTC", "summary": "This paper proves privacy properties of what is called the Gaussian mixing mechanism -- \"randomly\" mixing the data values through multiplying by a Gaussian matrix followed by addition by another Gaussian matrix. By going to f-DP, tight privacy guarantees are provided. Then, it shows that this can lead to better algorithms for differentially private linear regression, and theoretical performance guarantees as well as empirical results are provided.", "questions": "none", "limitations": "none", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\n\n+ The tight privacy analysis of the mixed Gaussian mechanism is well-done\n\nWeaknesses:\n\n- While the theoretical contributions are good, it was not completely clear to me what was mathematically novel -- the theory seemed to be quite standard applications of existing f-DP proof techniques.\n- The empirical improvements are also somewhat marginal and quite small especially for small privacy budgets. \n\nOverall I think the contributions are fairly marginal -- the theory is not terribly novel, and the empirical gains are very small.", "was_revised": true, "final_justification": "I will retain my score \"borderline reject\". The paper has some interesting theory, but the empirical results are quite weak; consequently the contributions are perhaps not significant enough for NeuRIPS", "rebuttal": "We thank the reviewer for their thoughtful comments and for recognizing the strength of our privacy analysis of the Gaussian mixing mechanism.\n\nThroughout the paper, we have aimed to highlight the main contributions, namely our refined RDP-based analysis of the Gaussian mixing mechanism and its implications for improving the performance of sketching-based algorithms for private linear regression. To that end, our primary objective was not to conduct an exhaustive empirical comparison against all existing methods, but rather to provide consistent evidence that our approach yields improvements over standard baselines in regimes where earlier analyses (e.g., [1, 2]) could not. While we acknowledge that the empirical gains may appear modest in some cases, we believe that consistently outperforming AdaSSP—particularly in settings where prior methods fail to do so—is a meaningful empirical contribution of our work. Moreover, as noted in our paper, the method proposed in [1, 2] remains effective in certain scenarios. Therefore, we believe that the fact that our approach achieves consistent and substantial performance improvements over this baseline across all datasets is another empirical contribution.\n\n\n**Comments Related to Theoretical Analysis:**\n\nWe agree that our mathematical analysis by itself is not novel. However, we believe that our key conceptual and technical insight is that the privacy properties of this mechanism can be better understood, and its guarantees improved when viewed through the lens of RDP. This perspective enables us to derive tighter bounds than those previously known, and, furthermore, leads to two additional theoretical contributions:\n\n\n   1. Our bounds yield a closed-form characterization of the privacy parameters for certain inputs. To see this, as a direct consequence of our analysis, for input matrices $X$ such that $\\underset{i\\in [n]}{\\text{sup}} ||x_i||^2 \\leq C_X^2$ and $\\lambda\\_{\\min}(X^{\\top}X) \\geq C_X^2$, our bound is achieved with equality when $\\frac{1}{C_X}X$ is semi-orthogonal. In particular, in this case, it holds that $\\underset{i\\in [n]}{\\text{sup}} \\ x_i^\\top (X^\\top X + \\sigma^2 \\mathbf{I}_d)^{-1} x_i = \\frac{C_X^2}{\\sigma^2 + C_X^2}$ and all the inequalities in our analysis are achieved with equality, leading to tight privacy guarantees. \n\n   2. Our analysis establishes that the Gaussian mixing mechanism is tCDP. Importantly, we show that using the conversion between tCDP to $(\\varepsilon, \\delta)$-DP yields tighter privacy bounds than a direct $(\\varepsilon, \\delta)$-DP analysis—an outcome that is not immediate or obvious. In contrast, prior works such as [1, 2] rely on direct $(\\varepsilon, \\delta)$-DP arguments and derive weaker privacy guarantees. Furthermore, the fact that the Gaussian mixing mechanism satisfies tCDP enables one to leverage a broad body of existing theoretical results developed for this class of mechanisms. As a further insight, our work provides an example of a mechanism with a data-dependent covariance that satisfies tCDP. This stands in contrast to previously studied examples, which involve only data-dependent variances (see [4, 6]). We believe this observation is both nontrivial and potentially impactful, as it opens the door to further extend the previous developments from [4, 6] towards using richer data-dependent structures.\n\nIn addition to the contributions previously discussed, we believe our results offer meaningful value to the differential privacy community—particularly given the widespread use of randomized sketches in the optimization literature. Our findings demonstrate that, in certain settings, sketching-based mechanisms can yield substantial improvements in both privacy-utility trade-offs and computational efficiency, outperforming several state-of-the-art baselines. \n\n**Comments Related to Significance of Empirical Results:**\n\nOur experimental results are designed to demonstrate the practical relevance of our improved privacy analysis, showing consistent utility gains across multiple linear regression tasks within the standard privacy regime of $\\varepsilon \\in [0.1, 10]$, a range widely accepted for $(\\varepsilon, \\delta)$-differential privacy. While we agree that the empirical gains might be small for certain cases, our focus was not the empirical study by itself but rather demonstrating that our method offers a mathematically rigorous refinement over the popular baselines introduced in [1, 2], and that it capable of achieving a non-trivial improvements over the widely used AdaSSP algorithm [5] in various settings. The ability of the Gaussian mixing mechanism to consistently outperform this strong baseline is, in our view, a meaningful contribution. Notably, this improvement holds uniformly across all datasets considered.\n\n\nWe will ensure that these contributions are more clearly emphasized in the revised manuscript and thank the reviewer again for raising these points. \n\n\n[1] Sheffet, Or. ``Differentially private ordinary least squares.\" International Conference on Machine Learning (ICML) PMLR, 2017.\n\n[2] Sheffet, Or. ``Old techniques in differentially private linear regression.\" Algorithmic Learning Theory (ALT) PMLR, 2019.\n\n[3] Bun, Mark, et al. \"Composable and versatile privacy via truncated CDP.\" Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (SOTC). 2018.\n\n[4] Hendrikx, Hadrien, Paul Mangold, and Aurélien Bellet. \"The relative Gaussian mechanism and its application to private gradient descent.\" International Conference on Artificial Intelligence and Statistics (AISTATS). PMLR, 2024.\n\n[5]  Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction \\& estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 93–103. AUAI Press, 2018."}, {"review_id": "97fDy01OdQ", "reviewer": "Reviewer_UXxy", "summary": "This paper studies the differential privacy mechanism of gaussian mixing mechanism, and improve the privacy guarantee by using techniques from renyi differential privacy. On a high level, the paper proposes a spectrum interpretation of the usefulness of the gaussian mixing mechanism, and provides a bound based on eigenvalues. As applications, the new analysis is applied on DP linear regression and DP logistic regression, and outperforms existing methods.", "questions": "- In figure 2, the pink line and red line are very close. Does this mean the improvement on the algorithm side is limited? I.e. algorithm in [1] is already good enough?\n- It seems that the metric in differential private linear regression is the test MSE. In this case, have you considered to directly perturb the estimator? That is, you solve the OLS with the original data and perturb the final estimator. What is the advantage of gaussian mixing compared to this straight forward baseline?\n\n\n\n[1] Sheffet, Or. \"Differentially private ordinary least squares.\" International Conference on Machine Learning. PMLR, 2017.", "limitations": "Yes.", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Pros:\n- The study of Gaussian mixing mechanism is important. The high level idea of eigenvalues providing privacy is valuable. The theoretical part is well inspired and solid. The proof of spectrum argument seems promising to be applied in other stats/machine learning problems.\n- The code is provided and the experiment results are great, outperforming the current SOTA results.\n\nCons:\n- Theorems are not self-contained. For instance, in theorem 2, most of the contexts are missing and it is hard to parse. Also, algorithm 2 mentions assumption 1,2, but I could not find them in the paper.", "was_revised": true, "final_justification": "I think this work provided good insights on using sketching techniques with differential privacy. The theoretical analysis is solid. I am leaning towards acceptance of this work.", "rebuttal": "We thank the reviewer for highlighting the significance of our new analysis and for acknowledging the strength of our theoretical contributions.\n\nWe also appreciate the comment regarding clarity and agree that some statements in the current version may be difficult to follow. In the revised version, we will revise the text to improve clarity and readability, as suggested.\n\nRegarding the questions raised:\n\n1. As noted in the text, both the pink and red curves represent our newly developed analysis. The only substantive difference between the algorithm proposed in our work and the baseline in [1, 2] lies in how the smallest eigenvalue, $\\lambda_{\\min}((X, Y)^{\\top}(X, Y))$, is estimated and used. In particular, when $\\lambda_{\\min}((X, Y)^{\\top}(X, Y))$ is close to zero, the two versions behave similarly. Thus, the pink and red curves often overlap, with slight differences attributed to the different privacy parameter allocation throughout the algorithm. We emphasize that both variants stem from contributions introduced in our work, not from the results of [1].\n\n2. The method referred to by the reviewer, known as output perturbation, can provide reasonably good private solutions under certain technical conditions (see, for example, [2, 4]). However, for private linear regression, the AdaSSP algorithm from [3] achieves the strongest guarantees on both empirical and test risk under minimal assumptions and is widely regarded as the leading baseline in this setting. For this reason, we selected AdaSSP as our baseline for the linear regression experiments. \n    \n    For the logistic regression simulations, however, the output perturbation technique is generally considered less effective than the widely adopted objective perturbation approach (see, e.g., the discussions in [2] and [4]). For this reason, we selected objective perturbation as the primary baseline in our logistic regression experiments. To further strengthen our empirical comparison, we have included an additional DP-SGD baseline in this rebuttal (see the table below), which we also plan to incorporate into the final version of the manuscript.\n\n\n| Method               | ε = 0.1 | ε = 0.42 | ε = 1.78 | ε = 7.50 | ε = 31.62 | Slower by |\n|----------------------|---------|----------|----------|----------|------------|------------|\n| FMNIST (DP-SGD)      | 0.155   | 0.040    | 0.030    | 0.025    | 0.020      | 0.833      |\n| FMNIST (Obj. Pert.)  | 0.200   | 0.065    | 0.025    | 0.020    | 0.015      | 0.384      |\n| MNIST (Obj. Pert.)   | 0.350   | 0.155    | 0.070    | 0.040    | 0.025      | 0.666      |\n| MNIST (DP-SGD)       | 0.180   | 0.110    | 0.100    | 0.045    | 0.027      | 0.188      |\n| **FMNIST (Ours)**    | **0.125** | **0.030** | **0.025** | **0.014** | **0.0125** | --         |\n| **MNIST (Ours)**     | **0.315** | **0.130** | **0.080** | **0.045** | **0.028**  | --         |\n\n\n[1] Sheffet, Or. ``Differentially private ordinary least squares.\" International Conference on Machine Learning. PMLR, 2017.\n\n[2] Kifer, Daniel, Adam Smith, and Abhradeep Thakurta. ``Private convex empirical risk minimization and high-dimensional regression.\" Conference on Learning Theory. JMLR Workshop and Conference Proceedings, 2012.\n\n[3]  Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction \\& estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 93–103. AUAI Press, 2018.\n\n[4] Chaudhuri, Kamalika, Claire Monteleoni, and Anand D. Sarwate. \"Differentially private empirical risk minimization.\" Journal of Machine Learning Research 12.3 (2011)."}, {"review_id": "6FaXDjve3n", "reviewer": "Reviewer_FmFk", "summary": "This paper provides an improved privacy analysis for a mechanism that first applies a standard Gaussian random projection to the data matrix and then adds Gaussian noise. Using this sharper analysis, the authors obtain tighter utility bounds for differentially private linear and logistic regression, building on existing techniques. They also show that their method performs better in practice, demonstrating improved accuracy on standard linear regression datasets.", "questions": "The tightening of the RDP analysis still recovers the existing error bounds in the worst case. Other than a novel analysis, what is the main theoretical significance of the work that the authors would like to highlight?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n1. The core technique and accompanying theoretical analysis are both novel and thoughtfully developed. The novelty in the techniques pertaining to the analysis of a tighter RDP-DP conversion mechanism and deriving a tighter $\\epsilon, \\delta$-DP bound has been well established in this paper. These techniques would be interesting from the point of view of a nice conversion technique from RDP to DP bounds for non-gaussian like mechanisms. Such mechanisms are useful not only in linear regression but other random projection based mechanisms for which this paper provides a clear analysis.\n\n2. The paper is well-organized and clearly communicates its main contributions. The exposition and proofs are accessible and precise. The proof-sketches within the paper is helpful along with a small ablation of different use-cases after each theorem.\n\n3. Empirical results show the method performs favorably compared to existing approaches, suggesting practical promise. It can be seen that in practical datasets like Communities and Crime and the Teactor Dataset, the linear mixing performs better than all of the baselines the latest being . Moreover, in the synthetic and gaussian dataset versions, it is shown that the algorithm due to Sheffet 2017 [2] performs better but corresponding to the parameter calculations by the technique proposed by this paper, further underscoring the effectiveness of conversion technique in practice.\n\n**Weaknesses:**\n\n1. The paper could do a better job of explaining the theoretical significance of the method and how it compares to existing approaches. A clearer discussion of what sets it apart would be helpful. Most of the work seems to be derived from the analysis of Sheffet 2019 [1] paper and it is not clear how exactly are the authors differentiating in terms of their contribution. Other than proposing a more nuanced analysis of the random projection mechanism and further developments in further bounds, it is not clear what the overall contribution is as the utility bounds are mostly matching the previously derived bounds.\n\n2. This connects to the previous point. It would also be useful to include some intuition or explanation for why the method performs better empirically—this could make the results more insightful and grounded. For instance, their improvements in parameters regimes does underscore well empirically, the authors should explicitly mention that in the experiments section and give further insights on how one can go about theoretically characterizing this improvement.\n\n**Overall Assessment:**\n\nThis is a good paper with theoretical and empirical strengths. A deeper discussion of the method’s advantages and practical performance would make it even stronger and how it distinguishes itself from previous work.\n\n[1] Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory (ALT), pages 789–827. PMLR, 2019.\n[2] Or Sheffet. Differentially private ordinary least squares. In Proceedings of the International Conference on Machine Learning (ICML), pages 3105–3114. PMLR, 2017.", "was_revised": true, "final_justification": "The paper presents an interesting contribution by offering a novel privacy analysis tool. While this analytical approach is valuable, the paper itself does not introduce significantly new results in terms of utility; rather, it provides a refined method for analyzing privacy. Notably, similar techniques have appeared in implicit form in prior work, such as Blocki et al. (2012). The authors extend this line of work by proposing a more distribution-aware analysis that aligns with recent developments in moment-based relaxations of pure differential privacy, such as tCDP. Although this is a compelling and useful tool, it does not, in our view, merit a substantial increase in score, as it lacks major new contributions to utility bounds in the general case.\n\nBlocki, J., Blum, A., Datta, A., & Sheffet, O. (2012, October). The johnson-lindenstrauss transform itself preserves differential privacy.", "rebuttal": "We thank the reviewer for their detailed and thoughtful feedback. We aim to address the points raised below. \n\n**Differentiation from [1, 2]:**  \n\n- **Privacy Analysis via RDP:**\n    \nWhile [1,2] analyze a variant of the Gaussian mixing mechanism using classical $(\\varepsilon,\\delta)$-DP techniques, our analysis leverages the RDP framework and leads to the following theoretical insights:\n\n1. The RDP-based approach yields tighter bounds on the privacy parameters of the Gaussian mixing mechanism. These tighter guarantees directly translate into improved utility when applied to private linear regression.   \n        \n2. We prove that the Gaussian mixing mechanism satisfies tCDP, a fact that was not known prior to our work. Moreover, and perhaps more surprisingly, this finding provides a novel example of a mechanism with a data-dependent covariance matrix that satisfies tCDP. Notably, such behavior is not exhibited by previously known mechanisms with data-dependent parameters that satisfy tCDP, such as the Gaussian smooth sensitivity. \n    \n3. For certain datasets $X$, our bounds are achieved with equality, giving a tight characterization of the privacy guarantees of the Gaussian mixing mechanism. As a direct consequence of our analysis, for input matrices $X$ such that $\\underset{i\\in [n]}{\\sup} ||x_i||^2 \\leq C_X^2$ and $\\lambda\\_{\\min}(X^{\\top}X) \\geq C_X^2$, our bound is achieved with equality when $\\frac{1}{C_X}X$ is semi-orthogonal. In particular, in this case, it holds that $\\underset{i \\in [n]}{\\sup} \\ x_i^\\top (X^\\top X + \\sigma^2 \\mathbf{I}_d)^{-1} x_i = \\frac{C_X^2}{\\sigma^2 + C_X^2}$ and all inequalities in our analysis are achieved with equality, resulting in tight privacy guarantees.\n\n- **Utility Guarantees for Gaussian Mixing in Private Linear Regression:**\n  \nAs a second theoretical contribution, we establish a formal utility guarantee for an algorithm that employs Gaussian mixing to perform private linear regression. This provides a meaningful extension beyond prior analyses in [1,2], which also connects to the utility theorem presented in [3].\n\n\nThe current version of our work deliberately places greater emphasis on the refined privacy analysis, which is the central focus of this paper. An ongoing extension of this work aims to build upon our current utility analysis (Theorem 3) by providing a more detailed and rigorous utility comparison to complement our existing privacy results.\n\n **Intuition for Empirical Improvements:**\n\nAn intuition for these results can be formalized as follows:\n\n1. Compared to the algorithms in [1, 2], our method provides tighter privacy guarantees and is therefore expected to yield strictly better performance in private linear regression tasks. To see this, note that for a fixed value of $\\gamma$ (corresponding to a fixed noise level), the privacy parameter $\\varepsilon$ achieved by our method is smaller whenever the condition$\\frac{\\sqrt{k}}{\\gamma} < 2\\sqrt{2\\log(1/\\delta)} + \\frac{4\\log(4/\\delta)}{\\sqrt{k}}$ is satisfied. As discussed in Section 4, the effective noise level in our scheme is given by $\\frac{\\gamma}{\\sqrt{k}}$, which is typically much greater than one. This makes the above condition likely to hold in most practical settings. Consequently, for any fixed set of mechanism parameters, our method achieves a smaller $\\varepsilon$—or equivalently, requires less noise to attain a given target $\\varepsilon$—and is therefore expected to outperform the algorithm from [1, 2], as supported by our simulations.\n\n2. Compared to the AdaSSP algorithm from [3], our current guarantees (presented in Theorem 3) align closely with those of AdaSSP in the regime where $\\lambda_{\\min}(X^{\\top}X) \\approx 0$. In this setting, both methods yield similar utility bounds. Notably, our method avoids the additional $\\log(d^2/\\varrho)$ dependence that appears in the AdaSSP analysis, and as such can provide improved guarantees—particularly when the parameter $\\chi$ is small and $\\varepsilon$ lies in a low to moderate privacy regime. This behavior is consistent with our empirical findings.\nIn contrast, when $\\lambda\\_{\\min}(X^{\\top}X) \\gg 0$, the analysis in [3] shows that AdaSSP enjoys a favorable inverse dependence on this eigenvalue, potentially leading to tighter bounds. Our method, on the other hand, relies on the minimum eigenvalue of the extended matrix $(X, Y)^{\\top}(X, Y)$, which is always upper-bounded by $\\lambda\\_{\\min}(X^{\\top}X)$. Therefore, in the regime where $\\lambda\\_{\\min}(X^{\\top}X)$ is large while $\\lambda\\_{\\min}((X, Y)^{\\top}(X, Y))$ remains small, AdaSSP is expected to outperform our method.\nLastly, there is a third regime, where both $\\lambda\\_{\\min}(X^{\\top}X) \\gg 0$ and $\\lambda\\_{\\min}((X,Y)^{\\top}(X,Y)) \\gg 0$. This situation arises when $Y$ is nearly orthogonal to the column space of $X$, such that the augmented matrix $(X, Y)$ is nearly full-rank. In this regime, the signal in $Y$ is poorly explained by $X$, and the underlying linear regression task becomes less meaningful and both methods perform poorly.\n\n**Main Theoretical Significance:**\n\nAs highlighted earlier in our response, the core theoretical contribution of this work lies in the improved privacy analysis based on RDP and the conclusions it enables. This analysis yields not only tighter bounds on the privacy parameters of the Gaussian mixing mechanism but also a more nuanced characterization of its privacy behavior—both aspects that were not captured in prior work. Moreover, as our simulations show, this refined analysis is essential for allowing the sketching-based algorithm to compete effectively with AdaSSP.\n\n\n[1] Sheffet, Or. ``Differentially private ordinary least squares.\" International Conference on Machine Learning (ICML) PMLR, 2017.\n\n[2] Sheffet, Or. ``Old techniques in differentially private linear regression.\" Algorithmic Learning Theory (ALT) PMLR, 2019.\n\n[3]  Yu-Xiang Wang. Revisiting differentially private linear regression: Optimal and adaptive prediction \\& estimation in unbounded domain. In Conference on Uncertainty in Artificial Intelligence (UAI), pages 93–103. AUAI Press, 2018."}]

Author rebuttal:

Meta-review: This paper studies the privacy properties of the Gaussian mixing mechanism, which multiplies the data with a random Gaussian matrix and then adds Gaussian noise. The authors user RDP analysis to provide tighter bounds for the privacy parameters of this mechanism, and show that it can be tight in certain settings. The paper also includes some experimental results showing some computational benefits while obtaining similar utility. 

The reviewers are encouraged from the results in this paper, especially the tighter analysis. The authors should address the concerns of the reviewers' in their final version, for example, comparing to the standard DP-SGD baseline, and also highlighting the computational benefits, especially since the accuracy improvements are not big.

Given the above, I recommend acceptance.
Decision: Accept (poster)