PRIMO: Private Regression in Multiple Outcomes
Authors: Seth Neel
Venue: Accepted by TMLR ()

Abstract: We introduce a new private regression setting we call \textit{Private Regression in Multiple Outcomes} (PRIMO), inspired by the common situation where a data analyst wants to perform a set of $l$ regressions while preserving privacy, where the features $X$ are shared across all $l$ regressions, and each regression $i \in [l]$ has a different vector of outcomes $y_i$. Naively applying existing private linear regression techniques $l$ times leads to a $\sqrt{l}$ multiplicative increase in error over the standard linear regression setting. We apply a variety of techniques including sufficient statistics perturbation (SSP) and geometric projection-based methods to develop scalable algorithms that outperform this baseline across a range of parameter regimes. In particular, we obtain \textit{no dependence on l} in the asympotic error when $l$ is sufficiently large. We apply our algorithms to the task of private genomic risk prediction for multiple phenotypes. Empirically, we find that even for values of $l$ far smaller than the theory would predict, our projection-based method improves the accuracy relative to the variant that doesn't use the projection.

Published in Transactions on Machine Learning Research (01/2025)
PRIMO: Private Regression in Multiple Outcomes
Scth Necl
sneel@hbs.c edu
Horvard Business School
Reviewed on OpenReview: https: // openrevie. net/ form?? id= 34vtRA3Nou
Abstract
We introduce new private regression setting we call Private Regression in Multiple Outcomes (PRIMO), inspired by the common situation where data analyst wants to perform set of I regressions while preserving privacy, where the features X are shared across all regressions, and each regression i E [4] has a different vector of outcomes yt- Naively applying existing private lincar regression tochniques/ times leads to a vî multiplicative increase in crror over the standard linear regression setting. We apply a variely of techniques including sufficient statistics perturbation (SSP) and geometric projection- algorithms that outperform this bascline across range of parameter regimes. In particular, we obtain dependence on l in the asymplolic error when l is sufficiently large. Empirically, on the task of genomic risk prediction with multiple phenotypes we find that even for values of l far smaller than the theory would predict, our projection-based method improves the accuracy relative to the variant that docsn't use the projection.
methods to develop scalable
1 Introduction
Linear regression is one of the most fundamental statistical tools used across the applied sciences, for both inference and prediction. In genetics, polygenic risk scores Krapohl et al. (2018); Pattte & Pan (2020) are computed by regressing different phenotypes (observed outcomes of interest like the presence of a trait or disease) onto individual genomic data (SNPs) in order to identify genetic risk factors. In the social sciences, observed societal outcomess like income or marital status might be regressed on a fixed set of demographic features Agresti & Barbara (209)). In many of these cases where the data records correspond to individuals, there are two aspects of the problem sctting that co-occur:
Aspect 1. The individuals may have a legal or moral right to privacy that has the potential to be compromised by their participation in a study.
Aspect 2. with different outcomes, either within the same study or across many diffcrent studics.
Multiple regressions will be ran using the same set of individual characteristics across each regression
Aspect 1 has been established as a legitimate concern through both theoretical and applied work. The seminal paper Homer et al. (2008) showed that the presence of an individual in a genomic dataset could be identified given simple summary statistics about. the dataset, leading to widespread concern over the sharing of the results of genomic analyses. In the machine lcarning setting, where what is being relcasod a model w trained on the underlying data, there is long line of research into "Membership Inference Attacks' Huu et al. (2021); Shokri et al. (2016), which given access to are able to identify which points are in the training set. Over the last decade, differential privacy Dwork & Roth (2044) has emerged as rigorous solution to the privacy risk posed by Aspect 1. In the particular case of linear regression the problem of how to privately compute the optimal regressor has been studied in great detail, which we summarise in Subsection 2.1
Aspect has been studied extensively from the orthogonal perspective of multiple hypothesis testing, but until now has not been considered in the context of privacy. The problem of overfitting or "p-hacking" in the social and natural sciences has been referred to the "statistical crisis in science' Gelman & Loken

---

Published in Transactions on Machine Learning Research (01/2025)
Label DP
14
X
W
J8
78
14
Figure 1: PRIMO imagines the scenario where the weights W computed function of sensitive features X and multiple outcomes Y are published or leaked. Our algorithms prevent adversary with access to W from exposing the underlying sensitive data F2 Tz, y².
(2014), and developing methods that quantify and mitigate the effects of overfitting has been the subject of much attention in the statistics and computer seience communitics Dwork et al. (2015a): Bassily et al. (2021); Korthauer et al. (2019). Given the ubiquity of Aspects 1 and 2, this raises an important question that we explore in this work:
When computing i I.../ distinct regressions with a common set of X's and distinct y:'s, what is the optimal accuracy-privacy tradeoff?
2
Preliminaries
We start by defining the standard linear regression problem. Let E X C TRaxd consist of d-dimensional samples from n individuals, y/s E 3 be a vector n outcomes for regression indexed by i, and parameter space WC C Rd denote the subset of linear regression coefficients we will optimize over.
For E W let f(w) = 1E (w Fe yak ) be the linear regression objective, and denote by wis arg wR" f(w) XX"X)XX -XTX)) yr where is the Mooro-Penrose inversc. For À > 0 let fx(w) En (w - +|| the ridge regression objective, and let w arg min (>(W) X
yr- The definition of data privacy we use throughout is the popular (s, difffferrntt privacy introduced in Dwork ct al. (006)) We refer the reader the to Dwork & Roth (2014) for an overview the basic propertics of (e, 8) DP including closure under post-processing and advanced composition. order to define a differentially private mechanism, we first define what it means for two datasets to be adjacent.
Definition 1. Two datasets (X, y), (X', v/) E X" y" are adjacent if they differ in a single element, e.g. there erists j. [n], such that X U {xz) \ {-,) = X', ( {urt = =y/ We say that (X, (X,y), (X',) are feature-adjacent they share labels y = V/, and 3j E [n] such that X U {2/}} [= X'. Similorly, they are label-adjacent if X X', and 3j [n] such that y (vf) (v,) = =
We denote adjacency of (X,,), (X', 1/' by (X,9) (X',y"). Definition 2. Let M: (X 3)n + O randomized algorithum taking as impul a datasel of n records. M is (E if V pairs of adjacent datasets (X,Y) (X',Y') YY). O:
Pr[M(X, E o PI[M(XX, x')
(1)
When Definition 1 holds for adjacency defined over (It; yi) pairs, this is the standard set lentin of differential privacy, which we call "Full DP order to differentiate from its relaxations. In the less restrictive case where Equation | holds only over pairs of label-adjacent datascts, we are in the well-studiod sctting of label differential privacy Ghazi al. (2021): Esfandiari et al. (2021); Paapennot al. (2016). When Equation holds only over pairs of feature-adjacen jacent datasets, say that have feature differential privacy. We develop
2

---

Published in Transactions on Machine Learning Research (01/2025)
specific PRIMO algorithms for these relaxations of DP in Section 5 We now formalize the Private Regression In Multiple Oulcomes (PRIMO) problem.
Let X the matrir with 8th row Tt, and let Yuxt the matrir with jth column yj = (.jj)...,r)))) The optimal solution W to the PRIMO problem is
Definition 3. PRIMO. Let E X C TR" Mig y for i = 1....
n,j= 1...I. .....,j-==
W arg |XW - -
WEWECROXt
Given a randomized algorithm M: (X x y²1" + W we say that M an (a, 3,,,6) solution to the PRIMO problem (i) M is (e,))-DP, and (ii) with probability
over W M:
1 [ - rI nl
1 | - -YI <a ml
We will use yj to denote the vector of outcomes for the jth outcome, and 3² ydd for the vector of I outcomes corresponding to individual i E [n]. We note that in PRIMO under full DP, the adjacency condition holds over pains (Ia; y²). The (e, 6)-P algorithm we will use most throughout is the Gaussian Mechanism. We state version of the Gaussian mechanism with constant 5) that is valid for all 0, which follows from analyzing the mechanism using Renyi DP Mironov (2017) and converting back to (c.
Lemma 1 (Dwork & Roth (2014)). Let f : N - Rd arbitrary d-dimensional function, and define it's sensitivity A2( = supx~>' [|((X) ((,))l,, where X ~ X' are datasets that differ in exactly one element. Then the Goussian mechanism GaussMech(e, 6, A) releases f(X)+ +N(00 )² and is (e, difffrrrreyt private for a 2 d)((),, where d) = V 2 + log A)
Lastly, we define some notation. Given a vector v and matrix A, ||0||2- ||A||2 denote the la and the spectral norm respectively, ||A]|e is the Frobenius norm, | = supzex ||x|||< | = ||vlloo and || v II where W* is the optimal PRIMO solution in Definition 3 Following convention in prior work, will let
|| ||]||, [|||2 denote supaex tell2,suppee ||vll2, sup..ew ||l||2 respectively.
2.1 Private Linear Regression
Private linear regression is well-studied under variety of different assumptions on the data generating process and parameter regimes. Typically analysis of private linear regression is done either under the fully agnostic setting where only parameter bounds || |M/|2 are assumed, or under the assumption of a fixed design matrix and generated by a linear Gaussian model (the so-called realizable case), or under the assumption of random design matrix from a known distribution Milionis et al. (2022). In this paper we focus on the first fully agnostic setting, because in our intended applications within the social and biomedical sciences in general we neither have realizability (when y is actually linear function of æ) or Gaussian features. In the fully agnostic setting Wang (2018) provides a comprehensive survey of existing private regression approaches and bounds, including a discussion of the impact of different parameter norms.
Broadly speaking, techniques for private linear regression fall into 4 classes: sufficient statistics perturbation (SSP) Vu & Slavkovic (2009); Foulds et al. (2016), Objective Perturbation (ObjPert) Kifer et al. 2012)). Posterior sampling Dimitrakakis et al. (2016), and privatized (stochastic) gradient descent (NoisySGD) Chaudhuri et al. (2011). The methods in this paper are a sub-class of SSP-based methods, which correspond to Algorithm where [ = 1. Methods based on SSP rely on perturbing x = E and X = Exy separately
with matrices of Gaussian noise (denoted by E1, Egs respectively). and then using these noisy estimates to compute the (regularizod) least squares estimator:
Wi. [ + + - X
(x" yi + E2s)
(2)
noisy covariance term &
noisy association term Exy
In their Theorem 5.3 Bassily et al. (2044) give a lower bound on the mean squared error of any (c. 8)D algorithm for optimizing Lipschitz objective function. In the case of linear regression (which corresponds to
3

---

Published in Transactions on Machine Learning Research (01/2025)
PRIMO with 1 = 1), if privote denotes the output of any (c, (c,5)-DP algorithm, then with probability at least
3:
a = f(uprivate) - f(w 2 min [ vd +
|| ||
(3)
n1
Cai et al. 2220 prove a lower bound that is tailored for realizable low-dimensional (n 2 d) linear regression, where ~ 2'3 + o2), with ||ل|| s 1 and || = O(1/d), showing that a = 02( + )). Neither of these bounds are exactly applicable to our setting; the bound of [Bassily et al. (2014) is not neccessarily tight for lincar rogression, and the bound of Cai ct al. (2200) makes realizability assumptions that clearly fail to hold for the lype of genomic applications that moviva our work. We also note that all existing lower bounds for private linear regression are under full DP, and so do not immediately apply to the algorithms in Section which operate in the weaker feature-DP or label-DP settings. In general, the focus of this work is upper bounds, and so we highlight this curious lack of relevant lower bounds in the literature potential future direction, given the long line of work on upper bounds for private linear regression. Acknowledging the above issues with existing bounds, throughout the paper we'll use the lower bound of Bassily et al. (2014) as a benchmark for the cost to accuracy of taking I 1, and in settings in which the bounds for PRIMO match this lower bound we will say we have "PRIMO for Free."
d n=
Given any (e, 6)-DP algorithm for computing wy privately, we can use it as a sub-routine to solve PRIMO by simply running it / times to compute each column of W. Hence by running any of the optimal algorithms (for example SSP Vu & Slavkovic (2009)) 1 times with parameters E' Rs e/VI, 8' se 6/t, by advanced composition for differential privacy Dwork & Roth (2014) we can achieve MSE, subject to (P.B)-DP:
a == Ō v TT(( X1 WI + || 11
(4)
ne
where the Ô hides factors of l) So for a fixed privacy budget e, this naive baseline is factor of vi worse than in the standard private regression setting where 1 = 1.
Further background on private query release for linear and low-sensitivity queries (relevant to our techniques in Section 5) under Loo and la error, and on sub-sampled linear regression (Subsection 7.7 is included in the Appendix.
3 Results
The primary contribution of this work is to introduce the novel Private Regression in Multiple Outcomes (PRIMO) problem, and to provide a class of algorithms that trade off accuracy, privacy, and computation. In addition to introducing the PRIMO problem, to our knowledge we are the first to apply private query release methods to linear regression (Section 5 We also provide compelling practical application of our algorithms to the problem of genomic risk prediction with multiple phenotypes using data from The 1000 Genomes
Project Fairley et al. (2019) and The Database of Genotypes and Phenotypes Mailman et al. 2007
Algorithm is our meta-algorithm for the PRIMO problem, and has two variants, ReuseCovGause which corresponds to M = GaussMech, and ReuseCovProj, which corresponds to M = Algorithm 2 Algorithm 2 itself has two variants, which correspond to the label private setting (GaussProj xx), and to the feature private setting (GaussProjy) respectively. For any given setting of the problem parameters (n, 1, d, || ||W (D')) one of those variants achieves superior performance, in terms of the upper bound we can prove on the error a. Which variant achieves the lowest a depends on the value of relative to the other parameters, and the lype of DP (Full, Feature, or Label) required. In Table I we summarize the theoretical upper bound by the best PRIMO variant in each setting. In Sections
achieved we prove these upper bounds for each variant.
In Sect ion we adapt the previously proposed sufficient statistics perturbation (SSP) algorithm of Vu & Slavkovic 2009);; Foulds et al.] (2016) into the ReuseCovGauss Algorithm. Via a novel accuracy analysis of SSP for the case when the privacy levels for E,, Ez, differ Equation 2 (Thcorem [] we show that since the noisy covariance matrix is reused across the regressions (as it only depends on X), by allocating the majority of our privacy budget to computing this term, we are able to obtain PRIMO for Free when l is sufficiently
4

---

Published in Transactions on Machine Learning Research (01/2025)
Guarantees ReuseCov
#1 of regressions
a = MSE
cost
M
Privacy
1 < min(
m
Gauss
Full
31
DP
E
| LIWIE
Ô [ MallavTaDilIR
v7
Gauss
Full
1
Vd
DP
1
Va"
T2
vd
X
3 LI
Projy
Feature
DP
1>
vd
| |0il|ad Villalla V'
Vn d'/a
Projy
Feature
va
y1-
DP
1> n
X (Yllava [|00ll
1/4 V/
Projx
Label
vnl
DP
Table 1: In the table above clst(l) is the ratio of the PRIMO MSE to the lower bound in Equation 3 and M denoles the mechanism used to compute the association term X in Algorithu
small. This happens because the error term is dominated by the error in computing the noisy covariance matrix, which does not depend on 1, rather than the error from computing the noisy association term (row the asymptotic error of ReuseCovGauss dominated by the error computing the noisy association term, which has a vi dependence in the error on I (row 2 of Table Given this, it natural ask if, under parameter regimes where the error from the association term dominates, can we obtain improved dependence of on over the vi given by ReuseCovGauss?
|
of Table 11. When 1>
DI
We answer this question in the affirmative in Section 5 with the introduction of the ReuseCovProj algorithms. The key idea is that instead of privately computing X via the Gaussian Mechanism (Lemma 1. which necessarily has error that scales like vi, in the setting where either or Y are not considered private, projecting the noisy value 1 +N(0, o²) returned by the Gaussian Mechanism onto the space of feasible values that the non-private quantity _ could take (Line 5 of Algorithm 2), can reduce the error for sufficiently large I. This set of "feasíble" values is the image of the domain of Y under X when X is considered public, and it is the image of the domain of X under YT when Y is considered public. The assumption that either X or Y are public are critical to these algorithms, as computing the projection depends on the space we are projecting into in a way that would not be easily privatized. The setting where X is public and Y is private corresponds to feature DP, and the setting where is public and Y is public is label differential privacy. In rows 3 - in Table | we summarise the guarantces of Theorems 3 that characterize the accuracy in these settings. In both the Feature DP and Label DP settings, the projection improves the dependence in the error on 1, d, at the cost of a factor of /n in the denominator. As a result, until 7, d are sufficiently large relative to n we'de expect the projection to actually increase error. We discuss these bounds further in Section
In Section 6 we implement our ReuseCovGauss and ReuseCovProj algorithms using SNP data from two of the most common genomic databases Mailman al. (2007); Fairley al. (2019). We compare our algorithms to each other, and to the non-private baseline. In both settings we reach the surprising conclusion that even for relatively small values of ( 11, 100, much smaller than the theory would predict, ReuseCovProj outperforms ReuseCovGauss. Moreover, ReuseCovProj is able to achieve non-trivial MSE (as mcasured by I²)) for very large values of 1, as predicted by Theorem 3 We also compare both algorithms to the baseline of rumning a single private regression / times (via DP-SGD Bassily et al. (2019)) and composing the privacy loss. DP-SGD performs significantly worse than any PRIMO algorithm unless we are in the setting of Row 2 in Table I where we expect no benefit from ReuseCovGauss or ReuseCovProj over SSP, consistent with the theory.
5

---

Published in Transactions on Machine Learning Research (01/2025)
4 Full DP: The ReuseCovGauss Algorithm
We start by presenting our first algorithm for PRIMO, ReuseCovGauss, which corresponds to Algorithm with M = GaussMech. To understand the intuition behind ReuseCovGauss, we start from the analysis of the ridge regression variant of SSP in Wang (2018). Equation 13 in Wang (2018) shows that üH is the noisy ridge regressor output by SSP, and wis the (non-private) OLS estimator, then w.p.
d | 2
f(w))) -(w))=
A2 +
IIMI
(5)
due ridge penalty
Assocciation error term
covariance error
Inspecting these terms, see that when || || the error is dominated by the covariance error term, which is the error due to random noise injected when privately computing x"x, rather than the association error term, which is error due to random noise injected when privately computing X y:- We now turn back to our PRIMO sctting, and imagine independently applying SSP to solve cach of our == 1... regression problems. By the lower bounds in Bassily el. al. (2014), given a fixed privacy budget this incurs at least vi multiplicative blow up in error. However, we notice that when our private linear regression subroutine is an SSP variant, this naive scheme of rumning / independent copics of SSP is grossly wasteful. Since the X matrix is shared across all the regressions, once, and then reuse it across all the regressions. Combining these two observations, we present Algorithm M can be any (e/2, algorithm for estimating X² but when M GaussMech we call Algorithm ReuseCovGauss.
simply compute noisy estimate of X
Algorithm Input: n, A, E X" C Rdxn Y = [UI... w) yxx", privacy params: 6,
ReuseCov
1: Draw E ~ Na of), where or =
Compute i = ( E1 XI)
Draw 3 = 101,...9t 90] ~ M(e/2,6/2,x,y)
M GaussMech Algorithm 2
4: for 1=
5: Set. vē; = î-19: fj
b In practice computed via f QR (Algorithm
6: end for
Return W- [u01... ... u6
|1)1)1)))))) Algorithm 1 is an (a, solution to Theorem With M CaussMech(e/2.0/22 - the PRIMO problem with
a á -=0(1bālee
x
d
1d
(6)
n²
n12
where ||001 I| and Ô omits terms polynomial in 2 log((1 log((//)))
Proof. The privacy proof follows from a straightforward application of the Gaussian mechanism. We note that releasing each 9, privately, is equivalent to computing X + Ez, where Eg ~ (0, Now it is easy to compute Asensitivity A(S) of f(x) = XTy. Fix an individual i, and an adjacent dataset. X' = X/(x,, vi v/). Then f(X) f(X') Av M = yuz, - 2/a Then:
[I((X) - S(X) / VlAr
Σ 11 14 S VI 1144411110 1 2|/|**||2||11
Hence setting 02 = 2)2, 12/c by the Gaussian mechanism Dwork & Roth 2014 publishing 9 satisfies (c/2,8/2) DP. Similarly if g x A(g) $ ||xI|| and so setting 01 c(c. c. | 12/e,, means publishing is (e/2, D/D)-D.. By basic composition for DP, the entire mechanism is (t, DDP

---

Published in Transactions on Machine Learning Research (01/2025)
To prove the accuracy bound we follow the general proof technique developed in Wang 2018) analysing the accuracy guarantees of the ridge regression variant of SSP in the case Amin XX = 0, adding some mathematical detail to their exposition, and doing the appropriate book-keeping to handle our setting where the privacy level (as function of the noise level) guaranteed by E₁ and Eg differ. The reader less interested in these details can skip to Equation 11 below for the punchline.
Fix a specific index 11, and let y yi- We will analyze the prediction error of w; e.g. f(ū)) f(wt).
Then the following result is stated in Wang 2018 for which provide short proof:
Lemma 2
(Wang 2018
f(m:;) f(w:.) = (lly Xw;ll 11y Xwiillll II) = || - wia 1
Proof. We note that all derivatives of orders higher than of (ww) lyy Xwll zero, and that V fun.- 0 by the optimality of W... We also note that the Hessian 72 =I XTT X at all points Then by the Taylor expansion of (ww around wi.:
f(w))) = (w)) + (i, - w Vfu. + 1 - - wiw, xxxx - wix)
Which using fww. = 0 and rearranging terms gives the result.
Now Corollary 7 in the Appendix of Wang 20018) states (without proof) the below identity, which we provide a proof of for completeness in Lemma in the Appendix:
ú; Win = (-x XI F1) Ei x(x"x + -w;
Wi. +
+x + A Fi) F2
(7)
Hence, still following
Wang 2018 for any psd matrix A, ||0; - wi. 11 v
xX + AI + E E w. lia I12 + AI + E,) -u; 11 + 3133 X + AI A +
(8)
Lemma 3 (Wang (0118)
With probability 1 - p, || 1a < 10min(X' + A)/2, and hence
x + XI E 5(X AT)
We also remark that |Byy| (By)² ABy I for any vector y, and matrices A, B.
Hence, Inequality with A = x X can be further simplified to:
3|1(X"x x
AI E1) E, 11a + 3x 3 AI + E1) - + 3||
AI -1)
O | ll l(
X2 1111 xl
E2 | S
(Lemma 3 O [
11 12
E2 [221
(9)
By basic properties of the trace we have: x < ddmaz (1l + X XX
[Am and ||1x,.11 (xxxxxxX=x-++ S Iuw. Continuing from Wang (2018) by their Lemma 6, we can bound
each || 1(x and 2 |
Lemma 4 Wang 2018 ) Let w E IRd and let E symmetric Gaussian matriz where the upper triangular region sampled from N(0, and let be any psd matrix. Then with probability 1 p:
Ew 13 s o² (²tr(A))((11) log(2d?)) (2d2/)))
Then recalling that:

---

Published in Transactions on Machine Learning Research (01/2025)
of = ((1x1)/))
o3 = 01
Plugging into Lemma and bringing it all together we get:
n n. m.((())) - f(w+)] )1 $ ||w5 - TillxTx=
E1 1oxx:llxxxxx>> + + >21/100 mlx.allxxxxxxyy + +11|2l1xxxxxx133
d
| |1 12/))) log(2d//0) + A111cia11
d +
1122 11221211111 (lggg/ /p) (10)
Amin +
Amin +
Upper bounding Equation 10 by taking Amin = 0, minimize over À setling
A - 0 (
|1 +
|
(s [wr+)] = d log 22)2
||
wl. + +1D/9//ws.. (11)
me
Now if we are the 7- smmlll regime, we have |/]| S 1/ 7/|1X1|2||1us [l,, and so
1/ s 11/ | 1
which reduces Equation to:
[s(w;) - S(w;)) = ( me
as desired.
| ), Algorithm with M the Gaussian
Inspecting Theorem we see that when < min( n Va D mechanism achieves error ò valla B1101 Since this matches the lower bound in Equation for a single
private regression in this say that have achieved "PRIMO for Free!"
5 Improved Algorithms for Large
The improvement of ReuseCovGauss over the naive PRIMO baseline in the previous section only applies in the parameter regime where the asymptotic error in Equation 5 is dominated by the covariance error term. In the regime where the association error term dominates, ReuseCovGauss still incurs v/ multiplicativo factor in the error term, which does not improve over the baseline. In this section we show that if we are willing to relax from full DP to either feature DP or label DP, we can improve the dependence on Specifically, via a reduction from privately computing the association term to computing the image of private vector under a public matrix, under feature DP we can obtain improved bounds for PRIMO when I n and under label differential pricacy we obtain improved bounds when > 2/3 (Subscction 5.2). In these cases, obtain the surprising result. that the MSF has explicit asymptotic dependence on l.
va (Subscction 5.
8

---

Published in Transactions on Machine Learning Research (01/2025)
A Algorithm Input: Xe x c (Rd)", Y= M,,...-9 3d ylx,, privacy params: e,
GaussProjy
Let r c(c, 0) sup; ||0'|2/11111
Sample N(, 1)
3: Let Ò - - where 1 Y
> Up to this point this is just GaussMech
4: Formulate C = ((Y) E xyy vec(X).
C is only used in the projection step
5: Let 9 = argmingexlla - Ell. where K = C(
5.1 PRIMO Under Feature Differential Privacy
Let us reconsider the problem of privately computing the association term 1 Y where Y yuxi, X X C. Raxd and
considered public, M is only constrained to be feature DP. Let vec(X) (R11,...,TIn) T21,... F.l.... Idn) E Rnd Then since ! is linear in every entry of X, there exists matrix C(Y) E yodttdn such that A _ C X). We explicitly derive expression for C' in Subsection 7.4 of the Appendix. Note that ||vec[X)]] - al 212, hence _ E C( where B1 = {x E nm ||ل|| S 1).
Algorithm is our projection-bel based subroutine for privately computing _ Y which we call GaussProjy We first state the squared error of GaussProjy in Theorem and then translate this error into the PRIMO error of ReuseCovProjj (Algorithm [ with M Algorithm in Theorem 3 The crux of the proof is Lemma 6 from Nikolov et al. [2013). which uses geometric argument to bound the error after the projection.
Theorem 2. Let 9.9 as in Line 4 of Algorithm g Then with probability 1
1g - 012 (
Proof. M is (e, differentially private by the Gaussian Mechanism and post-processing Dwork & Roth
(2014). So we locus on the high probability accuracy bound. By Lemma 4 from Nikolov et al. (2013) have,
letting K, r, as defined in Algorithm 2 that:
l|
g1l < 4||rw|||
sup 2 zeK
(12)
Using the fact that the le norm is self-dual, we have:
ll - g12 < wr|lw]lx> s 4rll/llavv sup (Cz) w 4-|1"||2v<7|((* w|l2
(13)
sEB,
So in order to bound || - E|ل with high probability it suffices to bound ||CT wll2 with high probability. This is the content of the Hanson- Hanson-Wright Inequality for anisotropic random variables Vershynin (0019)
Lemma 5 Vershynin 2019)). Let CT matrir, and X ~ N() E RR. Then for fixed constant
0:
ct2
P[ - >> 4 2erp(
with probability 1 1- p. Given Økj E X, let m = (k I)n +j be the corresponding column of C, and let ct denote this column. Then ||c = Al(( l1)ll2 =
Lemma 5 shows that [ICTw|la = 0[||C|| /lo((//p)
/ /d>x ; 1lv 3
! Elll'l vi Hence ||C]|

---

Published in Transactions on Machine Learning Research (01/2025)
Plugging in the value of gives, with probability p:
ف [-l1 - o -/2 ( /z VdEi- 1e llo((2/p)
c(c, 6)1,x)
sup: 11v2|l2
(14)
((c,,))/oo((21)) (//)
Ei 1 sup; |1'1
(15)
nlvd
Since both lerms involving Y in the numerator are < vID2 the bound follows. We note that since Y is public, in practice we can compute these terms rather than using [V), the worst case bound.
Notice that the mean squared error of the Gaussian mechanism without the projection is 0(r2)= - "1 -l which for lvd >> is strictly larger than the error of the projection mechanism. We also note that the bound in Theorem 2 is strictly better than the error given by applying the Median Mechanism algorithm of Blum let al.
n²
2011 for low-sensitivity queries, which is tailored for Loo error, and which also requires discrete X. = vd, and so Theorem gives a bound of (( whereas the Median Mechanism gives Ō da/3 1og(d))) for the mean squared error. We now state the accuracy guarantees of ReuseCovProjy- The proof follows the proof of Theorem [ substituting the bound
For example, when y = (0,1). = (0,1}% then [J]] = 1, =
n273
from Theorem [ into the || term in Equation 7 We defer the full proof the Appendix.
Theorem 3. Let A denote the variant of Algorithm with M GaussProjy (X, Y, e/2, 8/2). Then A is
(,, solution to the feature DP PRIMO problem with
d (1000 (11+111111 (1161bbb)
vdDrI
a á=Ō
n²
where Ô omits terms polynomial in log(1 log(1/p).
Inspecting Theorem in the Mechanism, when Va is not too large, the dominant term in the error is Ô V
regime where the projection improves the error over the Gaussian
which matches the lower bound 3 and so we achieve PRIMO for Free! When n is sufficiently large the dominant term is Ô
[ 2d
which is factor of n worse than the lower bound.
Vn.
5.2 PRIMO Under Label Differential Privacy
The setting where X is public and Y is considered private is strictly easier to satisfy than setting in which they are both considered private, and in particular in order for Algorithm [ to satisfy label DP, we only need to add noise to terms that involve Y. Thus we can compute in Line 2 of Algorithm [ exactly without adding any noise E1. We still need to compute the association term TY privately in Y, where now the privacy guarantee holds over rows Y rather than rows of X. Computing X privately is equivalent to computing 1 Xyix,-Xxxa where we've added subscripts indicating the dimensions of the matrices. Then by n
direct analogy to the previous section, we can compute " 1 via Algorithm 2, where Theorem holds by switching X and Y, and d. We call this variant of Algorithm GaussProjx- Thus invoking Theorem the error in computing the association term is with probability 1
p:
[gg -112- ( (le,)))oo((2// log(2/222 X
(16)
n
The crror in Equation 16 improves over the error given by M GaussMech when O(dv') < O > n3, which we summarise row 5 of Figure [ Interestingly, in contrast to the public label setting, this condition has no dependence on the dimension Substituting Equation 16 into Equation 7 with E, since we are the private setting and don't 't have add noise to the covariance matrix, we can optimize over À to get:
di
10

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 4. Let A denote the label-private variant of Algorithm
with Ej O,M
CaussProjx (x, Y, 12/228822) Then A is an P,e, 6, solution to the label DP PRIMO problem with
|X Illl
= δ |1002
nd114
We remark that while the form of Theorem 4 which is counterintuitive, I actually appears in the numerator through || O(D)lv), giving MSE with (mild) dependence ((11/4) on I.
appears suggest that the MSE decreases with increasing
5.3 Computational Efficiency
In this section we discuss the computational complexity of Algorithm | which can be broken down into 3 components:
Step 1: Forming X x
Step 2: In the case where M the projection algorithm, Line 5 in Algorithm 2
9 = lg...... 9i]
Step 3: the cost of computing i- (x" + A + + e
Step 1 forming the covariance matrix X is matrix multiplication of two d matrices, which can be done via the naive matrix multiplication in time O(nd²), and via long-line of "fast" matrix multiplication algorithms in time O(d++a());; For example if n < d it can be done in lime that is essentially ((d²) Gall
(2012). Step 2 corresponds to minimizing a quadratic over sphere. Setting A = CT C e Rduxdn b 20 " ge R then ğ = Cr, where x E Rnd is the minimizer of:
min x' Ax - b'x ZEB:
(17)
s.t. 1 S vT
(18)
Now, given the spectral decomposition of A UAUT, and the coordinates of in the eigenbasis U Lemma 2.2 in Hager (2001) gives a simple closed form for that computes each coordinate in constant time. Since there are nd coordinates of x, this incurs additional additive factor of O(nd) in the complexity, which is dominated by the cost of diagonalizing A. So the complexily of this step is the complexily of diagonalizing A = CT C, or equivalently finding the right singular vectors of C, plus the complexity of computing U.b.. This is soomingly bad news, as C' E dR dl is a very high-dimensional matrix, and the complexity for computing the SVD of C' without any assumptions about its structure is O(d In mi)) Golub Van Loan (1996). However, is evident from the construction of in Subsection that Kronecker product. In Appendix we show that using properties the Kronecker product, we can compute the SVD(C) in the same time as computing SVD(Y), or O(nl min(n, (n,())) I)). UTb can be computed in time O(nld) using similar tricks based on the Kronecker decomposition of C.
Ia 2 _YT, where X is the
Finally, Step 3 can be completed by solving the equation Iw; = Ôi, i = 1.../ via the conjugate gradient method, which takes time log(//)) to compute an e-approximate solution Mahoney 20111 where (f) is the condition number. We note that this has to be done separately for each i= I... giving total time O(l (f)) log(1/()). Alternatively, an exact solution f-lg; can be computed directly using the QR decomposition of the matrix î. The decomposition f= QR can be computed in time ((d)) Mahoney 2001 and does not depend the Ô., after which using Rú; Q Q"'g. tù backward substitution. This gives total time complexity of O + Id2). So if and I are sufficiently
be computed in time O(d)) via
7(1
small relative to c.g. if (fd)()(f))), it will be faster to use the QR decomposition based method.
Putting this all together we have:
11

---

Published in Transactions on Machine Learning Research (01/2025)
Theorem 5. The complexity of Algorithm 8 is O(max(min(nIP) n²t), nld, ndl, ,ld?, dd)).
We summarize these algorithmic changes to ReuseCovProj in Algorithm 3 Theorem shows that when > d > I, the complexity of Algorithm 3 is O(nd²) the cost of forming the covariance matrix. This motivates the results in Subsection 7.7 of the Appendix where we show how sub-sampling 8 < n points and using matrix Chernoff' bounds can improve this to (sd)).
6 Experiments
Datasets. We evaluate the accuracy of our algorithms ReuseCovGauss and ReuseCovProjx on the task of genomic risk prediction using real X data from two of the largest publicly available databases, and simulated outcomes Y so that we can easily vary the number of outcomes l. In addition, in Appendix [7.8] we include experiments on two additional datasets over smaller values of I, one constructed by sub-sampling MNIST Deng 2012 and generating synthetic outcomes from noisy linear model, and the other from entirely synthetic Gaussian data with outcomes generated either from 2-layer MT.P or noisy linear model.
The genomic datasets are from two sources: the 1000 Genomes project (IKG) Fairley et al. (001 and the Database of Genomes and Phenotypes Mailman et al. (2007) (accession phs000688.vI.pl. The datasets contain n 5008, 6042 haplotypes at == 78961, 16721 SNPs, respectively. Whenever experiments are run with & fixed value of d < 78961, 16721, we have randomly sub-sampled d SNPs without replacement. In order to vary the number of phenolypes I we generate synthetic phenotype data using our haplolype dalaset. After centering our haplotype matrix X by subtracting off the row means generate synthetic phenotypes yı for i == 1... by gencrating random 0 ~ N(O,, d "2) Uij ~ 0: I. + (O, 1). In order to evaluate our algorithms at larger values of than exist. in our genomic datasets, we train GAN on the dbGaP dataset follow- ing Olagoke et al. 2023 and use it to generate synthetic samples to simulate having up to a million data points.
Experimental Details. For a given dataset and setting of (n,d,1) we run ReuseCovProjx and ReuseCovGauss 10 different times, and calculate the resulting average MSE. We study two different regimes, one where n is of moderate size correspouding to real genomic datasets, 1e5 (Figure 2). The other regime models the scenario where in the near future genomic databases will have millions of individuals (e.g. UK Biobank already has 400000 samples Prive (2022)), generating n le6 samples from the GAN trained on dbGaP and again varying / from 1 to le5 (Figure Note that we do not have experiments with larger values of d for computational reasons; as discussed in Section 7.6 the runtime of both algorithms is quadratic in d.
small, and is varied from to
Rather than plotting the MSE a directly, in Figure 2 we plot the coefficient of determination R2, which is equivalent that R = SSS... We use R² because is easier to interpret given that achieving
error better than the constant predictor implies R² E (0. 1]. Tn Figures 3d 4 using a different metric, the log of the ratio of the MSE of the private predictor to the MSE of the optimal non-private predictor, where larger ratio indicates greater multiplicative error.
we also visualize the results
Realistic n, varying I. We find that for values of 1 starting as small as 11 for IKG and 101 for dbGaP, ReuseCovProjx achieves higher R² than ReuseCovGauss, and is able to achieve non-trival R²2 for large I which is consistent with our Theorem 3 For I < 11 on 1KG and < 101 on dbGaP, ReuseCovCauss achieves higher R². In addition to being consistent with the theory, this intuitive; when l small the bias induced by the projection outweighs the reduction in the overall noise. Figures 2a 2b show that for I > 101,801 801 on IKG and dbGaP respectively ReuseCovGausa has negative 12 by contrast, zooming in on the R2 curve for ReuseCovProj in Figures 2c 2d are able to achieve non-trivial R² at all values of I, and see minimal increase in error as 1 increases.
Large n, varying 1. Our upper bounds suggest that for large values of n, ReuseCovGauss will outperform ReuseCovProj x and that the MSE should increase polynomially with increasing 4, or equivalently linearly in log/ when we take the log ratio. Both of these trends can be seen in Figure aa). Given that the relative performance of ReuseCovProj x is improving as | increases, we expect that for larger values of I that were computationally prohibitive to run at such large n, ReuseCovProj would again be the superior algorithm.
12

---

Published in Transactions on Machine Learning Research (01/2025)
R² Comparison 1K Genomes d=
R² Comparison dbGaP d=25
1.00
0.75
0.50
0.25
R2
0.00
0.25
-20
0.50
ReuseCovGauss
ReureCovGauss Rousecavenn
ReuseCovPraj
-0.75
-25
OLS
200
400
600
800
1000
800
(a)
(b)
R² Comparison
1K Genomes d==2
R² Comparison dbGaP d=25
1.-
0.8
0.50
0.6
R2
0.75
0.4
0.00
-0.75
0.2
0.0
RouseCouPra)
ReuseCovProj
ous
OLS
200
400
000
800
1000
(c)
(d)
R² Comparison 1K Genorres d==5
Comparison | dbGaP
d=25
1.0
1.00
0.75
0.50
0.53
ReuseCooPPoj
ReuseCovProj
-0.75
oLS
20000
40000
60000
80000
100000
20000
40000
60000
80000
100000
(e)
(f)
Figure 2: Each R² value is averaged over 10 iterations. The shaded area around the lines indicates the error bars for the R² value at given value of (I, d). In Figures (a)-(d) we plot the average R² for d d 25, = 11, 101, 201,401, 601, 801, 1001), fixing (e, 6) = (5, + with n = 5008, 6042. In Figures (e)-(1) we show / up to 1e5.
13

---

Published in Transactions on Machine Learning Research (01/2025)
Log Relative Error 1000 Genome d=25
Log Relative Error dbGaP d=25
ReuseCovGauss
NeuseCovCiauss
ReuseCov/roo
10
loglapn/doo (doss)
10
log(atn pauus dous)
20000
40000
60000
80000
100000
20000
40000
60000
80000
100000
(a.
(b)
Log Relative Error 1000 Genome d=25
Log Relative Error | dbGaP d=25
ReuseCovGauss
ReuseCovProj
7
loglapp//oou)
loglaun//auus (lus)
ReuseCovProj
600
800
1000
1000
(c)
(d)
Figure 3: Comparing the log of the ratio of the squared loss of the private estimator to the square loss of the OLS estimator. Each value averaged over 10 iterations. The shaded area around the lines indicates the error bars at the given value of L. (a) and (b) range I up 100, (c) and (d) show [= (1, 11, 101, 201,401, 601, 801, 1001) while fixed d 25 and () (5, + with 5008, 6042 for 1000 Genomes and dbGaP respectively
Additional Ablations. In the setting where << Ja (Row 2 of Table D, theory suggests our algorithms should not outperform naive composition of private regressions. Since privale regression methods like DP-SGD Bassily et al. (2019) are known to equal or outperform SSP, our ReuseCov algorithms which are variants of SSP might actually perform worse than composing DP-SGD across regressions. We construct such a dataset. and show this is in fact the case in Figure in the Appendix.
The experiments above on genomic data generate outcomes Y from noisy linear model; in Figure 5 in the Appendix we show that generating outcomes from a 2-layer MLP with noise doesn't change the relative ordering of the algorithms by performance.
6.1 Limitations
There are 3 main criticisms that can be levied the results in this paper. The first that the reductions in error in the feature DP and label DP settings due to projection in Lines 3 - of Figure rely sufficiently large (: l 1 >> 2/3 respectively. As result, there are practical settings where n is particularly large
14

---

Published in Transactions on Machine Learning Research (01/2025)
Log Relative Error | synthetic dbGaP d=
R² Comparison synthetic dbGaP dd=25
0.8
poylappy/doo (dou))
R2
0.2
NeuseCovGauss
RovsaCos ReuseCovProj
ReuseCovProj
0LS
200
400
800
1000
400 800
1000
(a)
(b)
Figure 4: (a) shows the log of the ratio of the squared loss of the private estimator to the square loss of the OLS estimator and (b) shows the R2 values. For both of these, the value was averaged over iterations. The shaded area around the lines indicates the error bars a given value of (. We plot this for 1= (1, 10, 25, 100, 500, 1000,0000000 5000) with = 25, (e, (5, # and = 5 le5 on a synthetic dbGaP dataset.
or I is small where the theory does not suggest ReuseCovProj will outperform ReuseCovGauss. The second critique is that this improvement requires us relaxing our notion of DP to label or fcature DP. In settings where both X and Y are highly sensitive, if we want to guarantee full DP ReuseCovGauss would be is our only option. Finally, all of our algorithms are variants of SSP Vu & Slavkovic (2009), which has complexity that scales super-lincarly d due to forming the covariance matrix X For high-dimensional regression settings algorithms like private SGD are preferred due to their scalability CCauddhuri et al. (2011). With
respect to the first critique, note that in common settings, like in genomics, d can be very large relative to n, and so Va be quite small in practice. For example, in the popular Fairley et al. (2019) dataset used in the experiments, n 5008, and 78961, and so n 17. Similiarly, if n is modest size, is va plausible that 1 >> n2/3, We also note that our experimental results show that the projection improves error values of I much smaller than the theory would suggest, making this algorithm the practical choice for values of ( as small 11! Finally, the ReuseCovGuass Algorithm is itself also a contribution of this work. On the issue of scalability, in Subsection 5.3 we discuss how when n >> d > I, the computational complexity of the ReuseCovGauss algorithm is the cost of computing the covariance matrix x"x, which is ((dd²), which we improve to ((sd)) if we use s points to sketch the covariance matrix (Appendix 7.7). Dospite these improvements, the computational complexity of our methods is still super-linear d.
Obtaining versions of PRIMO that scale for large values of d, and that do not require relaxing full DP in order to improve the dependence on I as do in Section 5 exciting directions for future work.
15

---

Published in Transactions on Machine Learning Research (01/2025)
References
Alan Agresti and Finlay Barbara. Statistical methods for the social sciences. Pearson Prentice Hall, 2009.
Sergüll Aydöre, William Brown, Michael Kearns, Krishnaram Kenthapadi, Luca Melis, Aaron Roth, and Amaresh Ankit Siva. Differentially private query release through adaptive projection. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Evenl, volume 139 of Procerdings of Machine Learning Research, pp. 457-467. PMLR, 2021. URL http::/proceedingg mlr, ptress/v139/yddore2211
Raef Bassily, Adam D. Smith, and Abhradeep Thakurta. Private empirical risk minimization, revisited. CoRR, abs/1405.7088 2014. URL http://arxi...org//////0005. 7085
Rael Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. Private stochastic convex optimization with optimal rates. CoRR,
2019. URL
Raef Bassily, Kobbi Nissim, Adam D. Smith, Thomas Steinke, Uri Stemmer, and Jonathan R. Ullman. Algorithmic stability for adaptive data analysis. SIAM J. Comput., 50(3), 2021. doi: 10.113/166M113366 URL http:://doi. org/10. 10t...1111/11106060
Brett Beaulieu-Jones, Zhiwei Wu, Chris Williams, Ran Lee, Sanjeev Bhavnani, James Byrd, and Casey Greene. Privacy-preserving generative deep neural networks support clinical data sharing. Circulation: Cardiovasculor Quality and Oulcomes, 12, 07 2019. doi: 10.1161 (0.166//CCCCOUTCOMESSSI 118.00112.
Avrim Blum, Katrina Ligelt, and Aaron Roth. A learning theory approach to non-interactive dalabase privacy. CoRR, abs/ 122.2999,, 2011. URL
2229
Mark Bun, Jonathan R. Ullman, and Salil P. Vadhan. Fingerprinting codee codes and the price of approximate differential privacy. CoRR, abs/131 2as/1311.3158 2013. URL http://arxiv..rrg/bs///////a//// 3158
T. Tony Cai, Yiehen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy, 2020.
Kamalika Chaudhuri, Claire Monteleoni, and Anand D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research, 12(29):1099-1109, 2011. URL URT. http:://jmmrr.rr///
2opers//122/haudhuu 11a. htmml
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, (6):1111144,, 2012.
Michal Derezinski and Manfred K. Warmuth. Unbiasod estimates for linear regression via volume sampling. CoRR, abs/1705.06908, 2017. URL htttp://axxiv.orgg/.// wwwgg//bb//70...o
Michal Derezinski, Manfred K. Warmuth, and Daniel Hsu. Tail bounds for volume sampled linear regression. CoRR, abs/1802.06649, 2018. URL
Christos Dimitrakakis, Blaine Nelson, Zuhe Zhang, Aikaterini Mitrokotsa, and Benjamin Rubinstein. Bayesian differential privacy through posterior sampling, 2016. URL /tttp::////a www.o/ggg///.....///////// 1066
Petros Drincas, Michael W. Mahoncy, and S. Muthukrishnan. Sampling algorithms for 12 regression and applications. In SODA '06, 2006.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 9(3-4):211-407, 2014. URL httt:://bblp uni cuiittrier... jouioonall//////
Ettcs/fttcs9, http://tttcs...tttaxoorkkkt. htmmHDD4
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Iya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Serge Vaudenay (ed.), Advances in Cryptology - EUROCRYPT 2006, 25th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28- June 1, 2006, Proceedings, volume 4004 of Lecture Notes in Computer Science, pp. Springer, 2006. doi: 10. 10.1007/117000 00.107/11766169, 29. URL
16

---

Published in Transactions on Machine Learning Research (01/2025)
Cynthia Dwork, Vitaly Feldman, Moritz Hardt, Toniann Pitassi, Omer Reingold, and Aaron Roth.
Generalization in adaptive data analysis and holdout reuse. CoRR, abs/1150.002299, 2015a. URL
http://arxiv.org// http://wwrg/ab//15...00 02629
Cynthia Dwork, Aleksandar Nikolov, and Kunal Talwar. Efficient algorithms for privately releasing marginals via convex relaxations. Discrel. Compul. Geom., 53(3):650 673, 2015b. doi: 10.1007/3004544015-9777 URL 00010//0000000000000000000000000
Alexander Edmonds, Aleksandar Nikolov, and Jonathan R. Ullman. The power of factorization mechanisms in local and central differential privacy. CoRR, abs/1991.08839, 2019. URL http://arxxw..rr//bbb.
08689
Hossein Esfandiari, Vahab S. Mirrokni, Umar Syed, and Sergei Vassilvitskii. Label differential privacy via clustering. CoRR, abs/2110.001159, 2021. URI. httppp////xxvvoor//aaaaaa
02159
Susan Fairley, Ernesto Lowy-Gallego, Emily Perry, and Paul Flicek. The International Genome Sample Resource (IGSR) collection of open human genomic variation resources. Nucleic Acids Research, 48(D1): D941 D947, 10 2019. ISSN 0305-1048. doi: 10.1093 na000///a/////8666 URL
gkz836
James R. Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of privacy-preservie bayesian data analysis. CoRR, I603.07294
2016. URL http://arxiv.oo http:///aarii..o/abbb///
François Le Gall. Faster algorithms for rectangular matrix multiplication. CoRR, abs/ 1104.11111 2012. URL
http://arxiv org/ aaaaabaa1200 1104/ 1.204.111 1111
Andrew Gelman and Eric R. Loken. The statistical crisis in science. American Scientist, 102:460, 2014. URL
http://cccccc.....oooooooooooiia htt//CorpusDD::48855555 146855235
Badih Ghazi, Noah Golowich, Ravi Kumar, Pasin Manurangsi, and Chiyuan Zhang. On deep learning with label differential privacy. CoRR, abs/ abs/2212.00062, 2021. URL https://arxiv.. http:://arai.oogg/bbb///// wwtp://wwwaabb.....ooaooooo 06062
Gene H. Golub and Charles F. Van Loan. Matriz Computations. The Johns Hopkins University Press, third edition, 1996.
Anupam Gupta, Aaron Roth, and Jonathan Ullman. Iterative constructions and private data release, 2011.
William W. Hager. Minimizing a quadratic over a sphere. SIAM J. Optim., 12:188 208, 2001.
Moritz Hardt and Guy N. Rothblum. A multiplicative weights mechanism for privacy-preservie data analysis. In 2010 IEEE 51st Annual Symposium on Foundations of Compuler Science, pp. 61-70, 2010. doi: W0..9//FOS.00/U/
Nils Homer, Szaboles Szelinger, Margot Redman, David Duggan, Waibhav Tembe, Jill Muehling, John V. Pearson, Dietrich A. Stephan, Stanley F. Nelson, and David W. Craig. Resolving individuals contributing trace amounts of dna to highly complex mixtures using high-density snp genotyping microarrays. PLOS Genetics, 4(8):1-9, 08 2008. doi: 10. (3.1331/jom (journjju 1000667 URL hhtphs:t http://dio..oo/g//// ott..o.org/....1////rrraaaaa pgen. 1000167
Hongsheng Hu, Zoran Salcie, Lichao Sun, Gillian Dobbie, Philip S Yu, and Xuyun Zhang. Membership inference allacks machine learning: A survey. ACM Compuling Surveys (CSUR), 2021.
Shiva Prasad Kasiviswanathann, Mark Rudelson, Adam D. Smith, and Jonathan R. Ullman. The price privately releasing contingency tables and the spectra of random matrices with correlated rows. In Leonard Schulman (ed.), Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010, pp. 775-784. ACM, 2010. doi: 10.1145/1806689.1806779 URL http::://.oi.orrgtteeoo wttp:///.....1111...11 1806795
17

---

Published in Transactions on Machine Learning Research (01/2025)
Michael J. Kearns. Efficient noise-tolerant learning from statistical queries. In S. Rao Kosaraju, David S. Johnson, and Alok Aggarwal (eds.); Proceedings of the Twenly- Fifth Annual ACM Symposium on Theory of Computing, May 16-18, 1993, San Diego, CA, USA, pp. 392 401. ACM, 1993. doi: 10.1145/167088.16777 URL httpp:://oi.orrg org/ 10. 1ee...111511111 1145/167088. 167200
Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Shie Mannor, Nathan Srebro, and Robert C. Williamson (eds.). Proceedings of the 25th Annual Conference on Learning Theory, volume 23 of Proceedings of Machine Learning Research, pp. 25.1 20,40, Edinburgh, Scotland, 25 27 Jun 2012. PMLR. URL https: httpps://proceeddnng: mlr. press/ v23/kifer12 2tmll
Keegan Korthauer, Patrick K. Kimes, Claire Duvallet, Alejandro Reyes, Ayshwarya Subramanian, Mingxiang Teng, Chinmay Shukla, Eric J. Alm, and Stephanie C. Hicks. practical guide to methods controlling false discoveries in computational biology. Genome Biology, 20(1):1188 2019. doi: (0L1180/113099-01-1777
URL https://doi. org/ 110.1111///3305-011-117177
E. Krapohl, H. Patel, S. Newhouse, C J Curtis, S. von Stumm, PS S Dale, D. Zabaneh, G. Breen, P O'Reilly, and R. Plomin. Multi-polyyenic score approach to trait prodiction. Molecular Psychiatry, 23(5):1368- 1374, 2018. doi: 10.1038 10.1088/m..22 20..001.11.. URL http:://dooo.orrg////oo 1.38/mp.200 20177.63)
Yin Tat Lee and He Sun. Constructing linear-sized spectral sparsification in almost-linear time. CoRR, abs/1508.0322 03261, 2015. URL
03261
Michael W. Mahoney. Randomized algorithms for matrices and data. CoRR, abs/ 1ls/11045555,, 2011. URL
http:///rxii org/ arg/abs/1104.5m
Matthew D Mailman, Michael Feolo, Yan Jin, Michi Kimura, Kimberly Tryka, Rinal Bagoutdinov, Li Hao, Alex Kiang, Justin Paschall, Lon Phan, Natalia Popova, Sherri Pretel, Luda Ziyabari, Ming Lee, Yongzhao Shao, Zhining Y Wang, Karl Sirotkin, Michael Ward, Maxim Kholodov, Karen Zbicz, Judith Beck, Michael Kimelman, Sergey Shevelev, Don Preuss, Elena Yaschenko, Alexander Graeff, James Ostell, and Stephen T Sherry. The ncbi dbgap database of genotypes and phenotypes. Nature genetics, 39(10): 2007.
Ryan McKenna, Gerome Miklau, Michael Hay, and Ashwin Machanavaijhala. Optimizing error of high- dimensional statistical queries under differential privacy. CoRR, abs/1808.03537, 2018. URL http:
003000000// 03537
Ryan McKenna, Daniel Sheldon, and Gerome Miklau. Graphicel-modell based estimation and inference for differential privacy. CoRR,, abs//990.00913 2019. URL http:///aaxii.oorraab//////a//// 09136
Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis loannidis. Differentially private regression with unbounded covariates. In Gustau Camps- Valps-Valls, Francisco J. R. Ruiz, and Isabel Valera (eds.), Proceedings of The 25th International Conference Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 3242-3273. PMLR, 28-30 Mar 2022. URL https html
\/proceedings.o
mlr. weaeeediins..ll...
Iya Mironov. Renyi differential privacy. CoRR, abs/1702.074703 2017. URL http:://arst..or//abbb// 07476
S. Muthukrishnan and Aleksandar Nikolov. Optimal private halfspace counting via discrepancy. In Howard J. Karloff and Toniann Pitassi (eds.), Proceedings of the 44th Symposium Theory of Compuling Conference, STOC 2012, New York, NY, USA, May 19- 22, 2012, pp. 1285 1255-129..44 ACM, 2012. doi: 10.1145/2213977 2214090. URL htttps://ooii org/10. 1145/2213977 2214099.
Seth V. Neel, Aaron L. Roth, and Zhiwei Steven Wu. How use heuristics for differential privacy. In 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS), pp. 72-93, 2019. doi: 10. 10.1109/FOCS.2011 201..000...000......
Alcksandar Nikolov, Kunal Talwar, and Li Zhang. The geometry of differential privacy: the sparse and approximate cases. In STOC '13, 2013.
18

---

Published in Transactions on Machine Learning Research (01/2025)
Lukman Olagoke, Salil Vadhan, and Seth Neel. Black-box training data identification in gans via detector networks, 2023.
Nicolas Papernot, Martín Abadi, Úlfar Erlingsson, lan Goodfellow, and Kunal Talwar. Semi-superrised knowledge transfer for deep learning from private training data, 2016. URL htttp:://axxvv.rrg//
1610.05755
Jack Pattee and Wei Pan. Penalized regression and model selection methods for polygenic scores on summary statistics. PLOS Computational Biology, 16(10):1-22 27, 10 2020. doi: ptt.://oooaaaa.....oo.o.ooo... URL
https://doi.... hww//li..oggggg/ 10.
http://b...rr.......1//////aaaaa 177.1/////oorrl.ppoo. pcbi 1008271
Florian Privé. Using the UK biobank as global reference of worldwide populations: application to
measuring ancestry diversity from GWAS summary statistics. Bioinform. 3813):347333 2022. doi:
10.1093/bioinfrmmai bbtac448.. CRL https://doi. www.oo././/........ http:///.00////ooooootiiiieaaaaa
Garvesh Raskutti, Martin J. Wainwright, and Bin Yu. Minimax rates of estimation for high-dimensional linear regression over by-balls, 2009. URL
2042
Reza Shokri, Marco Stronati, and Vitaly Shmatikov. Membership inference attacks against machine learning models. CoRR, abs/ 1610.05820, 2016. URL htttp:://aarx....rt///////5....0
Justin Thaler, Jonathan R. Ullman, and Salil P. Vadhan. Faster algorithms for privately relcasing marginals. In Artur Caumaj, Kurt Mehlhorn, Andrew M. Pitts, and Roger Wattenhofer (eds.), Aulomala, Languages, and Programmingg 39th International Colloquium, ICALP 2012, Warwick, UK, July 9-13, 2012, Proceedings, Part 1, volume 7391 of Lecture Notes in Computer Science, pp. 810 821. Springer, 2012. doi: 10.1007/ 978-3- 1---3--42--111 1112--1594-7 68. URL lattps://dat http:://doooogo1.../ 111.110977-7---42--11-----
Reihanch Torkzadchmahani, Peter Kairouz, and Benedict Paten. DP-CGAN: diffcrentially private synthetic data and label generation. CoRR, 0bss/2001.09700 2020. URL https://arxiv http:aaawwi..rgaaa//aaaaaaa wwwpg/abs///0...// 09700
Joel A. Tropp. Improved analysis of the subsampled randomized hadamard transform. CoRR, abs/1011.1595, 2010. URL http://arxivi wwwpexivvi..r.veeooo abs//01.. 1595
Jonathan R. Ullman and Salil P. Vadhan. Peps and the hardness of generating private synthetic data. In Yuval Ishai (ed.), Theory of Cryptography - 8th Theory of Cryptography Conference, TCC 2011, Providence, RI, USA, March 28-30, 2011. Proceedings, volume 6597 of Lecture Notes in Computer Science, pp. 400 416. Springer, 2011. doi: 10.1007/978-3 19571-111116611 24. URL https://doi. https://ab1.oog/11.1000 org//0.100/// 000--64211997--- 24
Salil P. Vadhan. The complexity of differential privacy. In Tulorials on the Foundations of Cryplography, 2017.
Roman Vershynin. High- Higgh-Dimensional Probability. Cambridge University Press, 2019. URL https: // //ww math. uci. httpa///wwwoaaaaa////pppppp/p/pp
pdf
Duy Vu and Aleksandra Slavkovic. Differential privacy for clinical trial data: Preliminary evaluations. In 2009 IEEE International Conference on Data Mining Workshops, pp. 133-143, 2009. doi: 10.1109/ICDMIV 2009.52.
Yu-Xiang Wang. Revisiting differentially private lincar regression: optimal and adaptive prediction and estimation in unbounded domain, 2018. URL htttps:/arxxvv.rr//bbbba httg//bs/18800 1ttp//103.000 02596
Yu-Xiang Wang, Borja Balle, and Shiva. Prasad Kasiviswanathan. Subsampled rényi differential privacy and analylical moments accountant. CoRR, abs/ abs/1808.00087, 2018. URL http:://arsiv..rgaabb////// 00000/000000/0880000000077 00087
Jinsung Yoon, James Jordon, and Mihaela van der Schaar. PATE-GAN: Generating synthetic data with differential privacy guarantees. In International Conference on Learning Representations, 2019. URL
https://openreviior wwt.:/oorur/i---111as.....
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in Poror... Xi preprint arxiv:2109. 1 12298, 2021.
19

---

Published in Transactions on Machine Learning Research (01/2025)
7 Appendix
7.1
Additional Related Work
Query Release. In Subsection we show that privately computing the association term n y is equivalent to the problem of differentially privately releasing a set of l d low-sensitivity queries [asssiy et al.] (202T). While less known about the optimal 12 error for arbitrary low-sensitivity queries, it is clear that geometric techniques based on factorization and projection do not (at least obviously) apply, since there is corresponding notion of the query matrix Ae Edmonds et al. (2019). In the case where X, Y are both private, this corresponds to releasing a subset. of (. d 2-way marginal queries over d 4+ I dimensions, which is well-studied Dwork et al. (015bb;; Thaler et al. (2012); )5 Ullman & Vadhan (2011). In the related work section of the Appendix we discuss why applying existing algorithms for private release of marginals seems unlikely be able to both improve over the Gaussian Mechanism and achieve non-trivial error. However, in the less restrictive but still practically relevant setting where the labels Y are public, computing the association term y is equivalent to the problem of differentially privately releasing a special class of dl "Jow-sensitivity" queries we term "inner product queries" (Definition 6). For this special class of queries we can adapt the projected Gaussian Mechanism of Aydöre et al. (2021) that is optimal for linear queries under l2 error in the sparse regime. We are ablc to obtain greatly improved results over the naive Gaussian Mechanism in the regime where 1 >> n vd as summarised in Figure and presented in Subsection 5 This is a key regime of interest, particularly for genomic data, where d the number of SNPs could be in the hundreds of millions, n the population size in the hundreds of thousands (~ 400K for UK Biobank Privé (2022) one of the most popular databases), and [ the number of recorded phenotypes could be in the thousands.
Projection mechanisms and Algorithm 2 Since we make heavy use of projection mechanisms in Subsection in the public label setting, we elaborate on the difference between the existing methods and our Algorithm The most technically related work to our Algorithm 2 is Aydöre et al. (2021), which is itself variant of the projection mechanism of Nikolov et al. (2013). There are several key differences in our analysis and application.The projection in Nikolov et al. (2013) is designed for linear queries over discrete domain, and runs in time polynomial in the domain size. Algorithm 2 allows continuous N, and runs in time polynomial in n, I. Like the relaxed projection mechanism Aydöre et al. (2021), when our data is discrete we relax our data domain to be continuous in order to compute the projection more efficiently. Unlike in their setting which attempts to handle general linear queries, due to the linear structure of inner product queries our projection can be computed in polynomial time via linear regression over the l2 ball, as opposed to solving a possibly non-convex optimization problem. Moreover, due to this special structure we can use the same geometric techniques as in Nikolov et al. (2013) to obtain theoretical accuracy guarantees (Theorem
Private relcase of 2-way marginals Consider the problem of privately releasing all 2-way marginals over n points in 104t, Theorem 5.7 in Dwork et al. (015b) gives a polynomial time algorithm based on relaxed projections that achieves mcan squared error O(v/d+ 7), which matches the best known information theoretic upper bound Dwork et al. (2015b), although there is small gap to the existing lower bound min(n, (d + 1)).. This relaxed projection algorithm outperforms the Gaussian Mechanism when nvd+l= di
Id - n
dvd+1 +1> n. Since the mean squared error of Algorithm ] that used this projection
Vd+i
as a subroutine at least dvēF1 this means that in the regime where the projection outperforms the Gaussian Mechanism, we do not achieve mean squared error 1 in our regression.
This suggests that, at least using the existing error analysis of SSP from Wang 2018 it seems unlikely that by applying specialized algorithms for private release of 2-way marginals to compute the 1 Y term subject to differential privacy in (X, Y), e.g. the label private setting, we can both improve over the Gaussian Mechanism and achieve non-trivial error.
Linear Queries under -loss. Beyond 2-way marginals, the problem of privately releasing large numbers of linear queries (Definition 4 has been studied extensively. It is known that the worst case error is bounded
by min( (1) [X]] */ / /l The first term, which dominates in the so-called low-accuracy "sparse" Nikolov et al. 2013 regime, is achieved by the PréonteMulllplicnttiee Weights algorithm of Hardt.
20

---

Published in Transactions on Machine Learning Research (01/2025)
& Rothblum (0110) which is optimal over worst case workloads Bun et al. 20133) However, this algorithm
has running time exponential in the data dimension, which is unavoidable Vadhan [0117] 7) over worst case Q.
The second term, which dominates for n >> log [ log La the "high accuracy" regime, achieved by the
[
simple and efficient Gaussian Mechanism Dwork & Roth 2014), which is also optimal over worst-case sets of queries Q Bun et al. (2013)
Linear Queries under l2-loss. For the l2 error, in the high accuracy n >>>>> ② regime the factorization mechanism achieves error that is exactly tight for any workload of linear queries Q up a factor of log(1/6), although it is not efficient (Theorem [Edmnnds et. al. (2019)). In the low-accuracy regime, the algorithm of Nikolov et al. (2013) that couples careful addition of correlated Gaussian noise (akin to the factorization mechanism) with an l-ball projection step achieves error within log factors of what is (a slight variant) of a quantity known as the hereditary discrepancy o (Theorem Nikolov et al. (2013) ). This quantity is a known lower bound on the error of any (c, mechanism for answering linear queries Muthukrishnan & Nikolov 20122) and so the upper bound tight up to log factors in [Q], [2)] Theorem 21 in Nikolov
et al. (2013) analyzes the simple projection mechanism that adds independent Gaussian noise and projects rather than first performing the decomposition step that utilizes correlated Gaussian noise, achieving error ((ndlog(1/))) log X(/c), which matches the best known (worst case over Q) upper bound for the sparse < dl case Gupla et al. (2011). In our Theorem 2 we give such universal upper bound, rather than one that depends on the hereditary discrepancy of the matrix Y. While the bound can of course be improved for a specific set of outcomes Y by the addition of the decomposition step to the projection algorithm, we omit this step in favor of a simpler algorithm with more directly comparable bounds to cxisting private regression algorithms.
While the information-theoreli (o or la error achievable for linear queries is well-understood Edmonds et al. (2019 Nikolov et al. (2013): Bun al. (2013), , synthetic data algorithms like PréuateMultippicctte Weights and
or the factorization or projection mechanisms are in general inefficient, there are many open problems pertaining to developing efficient algorithms for specific query classes, or heuristic approaches that work better in practice. Examples of these approaches along the lincs of the factorization mechanism McKenna et al. 20018 2019), efficient approximations of the projection mechanism Aydöre et al. (2021): Dwork et al. (2015b). and using hcuristic techniques from distribution learning the framework of iterative synthetic data algorithms Yoon et al. (2019): Torkzadehmahani al. 22020;; [eaulieu-Jones et al.
2019 Neel et al.
2019
Sub-sampled Linear Regression. In Subsection 7.7 we analyze SSP where we first sub-sample random set of s points without replacement, and use this sub-sample to compute the noisy covariance matrix. Sub-sampled linear regression has been studied extensively absent privacy, where it is known that uniform sub-sampling is sub-optimal in that it produces biased estimates the OLS estimator, and performs poorly in the presence of high-leverage points Derezinski al. (2018). To address these shortcomings, techniques based on leverage score sampling Drineas et al.] (2006), volume-based sampling Derezinski & Warmuth 2201 Derezinsk et al. (2018), and spectral sparsification Lee & Sun (205 have been developed. Crucially, in these methods the probability of a point being sub-sampled is dala-dependent, and so they are (not obviously) compatible with differential privacy.
7.2 Definitions
Throughout the paper we make heavy use of common matrix and vector norms. For a vector u E Rdd and matrix A gdxd sdxx,,|julB == v' Av, || >max (AT A), 1ell = Σdn oz ||A|| = Ei.jeg ozz.
Definition 4. Statistical Query Kearns 1993 Let D E x dataset. A linear query is a function g: q:X- + [0,1], 1], where q(D) == 1 Σ Ex,d (zx))
Definition 5. Kasivisunnalhan el al. (010)) Let X = (0. 1m and Q
where (g(x)) ==
IIt,, 24, Then the class Qx are called k- way marginals.
Lastly, we define a new class of "low-sensitivity" queries Bassily et al. (0021 we call "inner product" queries that we will make heavy of in Subsection 5
21

---

Published in Transactions on Machine Learning Research (01/2025)
Definition 6. Inner Product Query. Let X C Rd and X E X C B a dataset with column corresponding to Jj X. Let y E IR"", and i [d]. Then the pair (i. y) defines an inner product query 9(3.y) X -+ R,
1 ((.,0) (X)
1 -e, Xy.
Xisyi
71
n
where et is the 5th basis vector in Rdd
Changing one row of X, changes most one summand 1 Xiyy, of q()) and hence the ly sensitivity (2(((1)) s [لااار I |>]|ii fact we will use throughout.
x
7.3 Lemmas
Lemma 6 [Raskttti et al. ()09 Let K Rdd be symmetric conver body, let g K and ğ 9 for E R.. Then if 9 argming' k || g'l 0'12, then
1 g1l min 4||w||k=
Lemma 7.
Tropp 2010) Let Zi E ST and sample Zı.... Zo without replacement from (Zi... Zn Suppose
[ = La, and maxie[n] Amax (Z,) S B. Then for v 2B log(2d/o) with probability 1 p:
2x) < 1 8, Amin Amax Σ i=1
Zz) > 1-5
Lemma (folklore c-g- Wang et al. (2018)). Given a dataset X of points and an (c,8)-DP mechanism M. Let the procedure subsample lake random subset of points from X without replacement. Then if y s/n, the procedure M subsample is 78) for sufficiently small e.
The following lemma is used repeatedly in analyzing the accuracy of all SSP variants.
Lemma 9. Let A, B invertible matrices in Raxn, and u, vectors R
Then
-A BA (A+B)- B (o
Proof. Expanding we get that:
A - (A+ (A- (A++ B) (A+ Be-
it suffices to show that:
(44 -BA
Now the Woodbury formula tells that (A+ -)+ (A+ AB- - AA hence
(A-- AB- (A(1 + 1-1 A)) -'y
Then since:
(A (A (B (B- A)) 111 = (B + -BA-1
done.
22

---

Published in Transactions on Machine Learning Research (01/2025)
7.4 Proofs from Subsection 5
Computing the association term. Consider entry (k, of L for k E [d],j E [1, akj ( 4.
e* = B (().),(()), ((k.y,) is the inner product query of Definition 6 Thus privately computing 1 x XYY, Y. is equivalent to privately releasing answers to dl inner product queries (9())s)) (E(())EE)
It will be convenient for us to write (()x))))) as a single inner product. Let vec( vec(X), let mat(y) = X. Denote by E Rnd the vector that has all zeros except in positions (A: - 11)nnn+,, l... kn it contains 1 n Æys..... 1 Uny- Then it clear that Q(k.M,) (X) = c veo(X) so if we let E ( be the matrix with row kj E [di] equal to Ckjs then 1 Y = C vec(
(Eib..,,Iinn I.l.... Idn) E Rnd, and given
n
Proof of Theorem
Proof. We start with our usual expansion of f(ū,) f(w+.), up until Equation 10 we have with probability - p for every i E [1]:
n n. (.;()) - [(w+.) Ō
Wir
Al|wtol13
|1E2:11
(19)
Amin +
Amin
Aggregating over i and rearranging gives:
(
d Aimin + A
Σ [(0))) f(wr))
|10 log(2d)) 1//22/11 /p) A111112 Amin X
E2i 12
(20)
where ||01| 1 1|
Then by Theorem have with E i= ||
O (((e:)//log(//))//aa0 f(w())
with probability 1 1-p. So with probability 1-2p, we have Σ/ f(
δ 0 Amii +
d
1 /p) 21 Amin
c(c, ecc.0//ncce/////appp1111 (21)
Finally optimizing over À gives the desired result:
a (iailay dl |0 (11
(og(ge/)) c(e, 6) /lgg////ol//////////// (bgg(2/))
n²
7.5 Proofs from Subsection 7.7
Proof of Theorem G
Proof. Our analysis will hinge the case where / = 1 e.g. that of standard private linear regression, which we will extend to the PRIMO case by our choice of E as in the proof of Theorem [ The fact that the Algorithm is 5) private follows immediately from the Gaussian mechanism, and the secrecy of the sub-sample lemma (Lemina 8 which is why we can set el = #e/2 in Line 2. We proceed with the accuracy analysis.
Define:
Wis = -XXY:: the least squares estimator as before
we = AT) AT)- - 1ixTy: the ridge regression estimator
23

---

Published in Transactions on Machine Learning Research (01/2025)
w. (1x5Xs
the sub-sampled least squares estimator
w. (xX5Xs + E + X1) -1) xT E2): differentially private estimate of ws
We note that 0 3 f(w - f(ws)) E (1 11 s A/DIi Then by the Lemma and Cauchy- Schwartz with respect to the norm
xxx:
-Wee xxx S [f(w)) - [(wx)]] ||0
8/1wix - w 11.11221 xxx + 3 31 - w.,l + +3|1wg - W. xTx
- S
3iMMi/I + 3||ws w XTx + 3 -
-
w.ll x (22)
Lemmas
14 13
bound these terms with high probability.
Lemma 10. Under the assumption || O(nA), then w.p. 1 - p/2:
| woll xxx = =0 ||x||||)0| [1 (ogg(d//))
As
Lemma 11. Under the assumption || (n1)), then w.p. p/22:
d log(2d/
11211111111 d d p)
Iww - w XTXX
0(
(23)
n?E2
n²c²
8
Then by Equation 35 and Lemmas
14
13
get that w.p. 1 p:
f(w,) - -[(w)))
0 A//wwx 11 ||2112/21 log(2d/p) +
| n
log (g((2d/))
212111
d
log log(2d/p)
|
(1 +
A
n
(24)
Summing over and minimizing over À we set
||11122)11 (2g(()d/)))))))))))))))) (ogg(2///)) )+ + 24,2
|IWI12 {1 + log(2a/p))
+ n²,2 (1 log(2d/p)
Vill|W/FF
which completes the result.
Proof of Lemma 14
Proof. Now:
|/wa. w nl/wa, ws w/ll2 1 S 22| nlllwa w. wallāxTx+Nr
We will focus on Imli wall3 10l12x wall2xtxx2r Lot E 1 + AI, Σ, = E F + AI, and u 1XTY.
Expanding ||w wallx=
1 - IEE
= b. - - Σ - Σー W E-1) oT Au
(25)
Now since A Hermitian, we know ||a|A < |||||||||| Since ||||| < | suffices bound ||A||2 with high probability. Noting that A (Σ, ンー'E -ー 3-1125,5-112/1//55-- have by the sub-multiplicativity of the operator
24

---

Published in Transactions on Machine Learning Research (01/2025)
||||2 v (1>g)>1/913) (11-5~12,,81111 2
Amax (2)
(11-E-1/22,, ---,11111--))111) (26)
X2
Now consider E-1 E-1/21 E ( + AfJE-1/2 E_ + A/) 1-1/22551122 = and that Amaz (2,) S || 112l=
3 5je Zi. Then note that B|Z]]
+ +All2 & 1 nx
||
Now we can bound ||4 -iE Zille by Theorem 2.2 in Tropp (0110):
Lemma 12. Tropp 2010) Let Zz.... Ze sumpled without replucement from Zn}. Then if Z, E $ [[Z]] la, and max Amax (xi) S B w.p. 1 - P, for v 2B log(2d/p)
5
Amax Σ 21) < 1 Amin (
2i) -22)== 1-8
3
So by Lemma 12
we know that with probability 1-p: (1
xmx (E-1
8, and similarly Xmaax (I E 1, 6, thus -|-- --- S 6. Substituting this all into
Equation 26 and noting Amax (E) S ||||| we get with probability 1-p:
|/m. wxll Wxll I |000- w s || m|| A|12 - || Amax (Σ)
8²
(27)
X2
||
+ X)2 log (2g(2d/))
2 2
(28)
A
which under the assumption || O(n)) gives 0 || D log(2d/e) ). as desired.
Ae
Proof of Lemma 13
Proof. By Lemma with 1 X XI, B F, == E2, v E,,, - x + E,) 5 E2, and so
1 LT, we get n. - U = X + A
||w,- G. 1 s 211( x5 x + + - En xTx + + 1 - + 1
Under the assumption || EEil2 s a/2, this becomes
|[w -0,11xxx =0
(1
(29)
Now to apply Lemma
we need to bound
Tr(( x + AT) -X" N)X-XXX + AT) AT) S ddmax (E))ss
ddmax ( 1/-1/2(11//2/1 1//12/355 1//3333-111
d 1
d)maxe
1 ) (30)
Amia (Σ' 1E-1/ 1/2)
where the last inequality follows from Lemma
12 Applying Lemma g we get that with probability - 2p:
wallxTX/a =0
d 1
j ||m (2d /p) oz. d 1 )2 log (2d lp) (31)
X 1
1
25

---

Published in Transactions on Machine Learning Research (01/2025)
2(+ us log(2d/p) which under the assumption || - O (n1) gives (T-8)
From Lemma 12 8
O +
log(2d/ 0) 2
Substituting in the value of 01, gives:
X st22
I x (1+ log(2d/p)
ME n²c2
log(2d/p)
+
desired.
7.6
Computational Complexity
We continue the discussion of how to efficiently compute the projection step in Algorithm 2 by exploiting properties of the Kronecker product. Recall that C' = La YY where & denotes the Kronecker product. Then if LAVT denotes the SVD of y standard properties of the Kronecker product imply that the spectral decomposition of C C is:
= L. (1.LLLLLLAA))rr) - n1
(32)
C² (La (0
(33)
Hence we can compute SPEC(C) the time takes to compute SVD(Y), or O(nl min(n, ()). Similarly, efficiently compute the b term required for Lemma 2.2 Hager 2001 we can again take advantage of properties of the Kronecker product, U=b=
(Ia 2 g VT) 1 -Y)=
1 VT.
VV ")ğ = vool -vo(= 2 V ymat (g)),
2(Ta Ø n
n
where mat(ğ) is the I x d matrix with row given by elements (I(i 1) + 1(...,,(i-- + of g, and the last equality follows properties of the Kronecker product. Now VTy AUT which be computed in (II)) since A is diagonal. Multiplying by mat(ğ) can be done in another O(nld), for total complexity of Onl max(min(n,, d))
A Algorithm Input: X, X' E Xn Rdxn Y (y1,... v1] plxn, privacy params: e, 6. We denote by B the Algorithm in Lemma 2.2 Hager (2001)
ReuseCov
Draw E1 N2jd+1)/2(0,00)) (0, where 01 2 20gg
2: Compute î = x
AI)
Compute the QR decomposition 1 -=QR
4: Draw 0 = 0g] ~ GaussMech( (attssMMeccc/2,5//00 522 A \(1(2(1111)))
5: Compute SVD(Y?) = UAV"
6: Compute 9 = 0 ((),A,
for 1=
Solve Rú;; Q" 9. by back substitution. end for
10: Return W- [u0 وij
7.7 Sketching ReuseCov
Theorem 5 shows that when n > d > I, the complexity Algorithm 3 is O(nd?) or the cost of forming the covariance matrix. In this section we show how sub-sampling < n points can improve this O(sd²) by giving an analysis sub-sampled SSP. The key ingredient marrying the convergence of the sub-sampled covariance matrix to X X with the accuracy analysis of SSP in Section
26

---

Published in Transactions on Machine Learning Research (01/2025)
Our algorithm is based the observation that if we sub-sample S C [n], points without replacement them:
The cost of computing the covariance matrix Eg Ekes Fta O(sd)
By the "secrecy of the sub-sample' principle Dwork & Roth (014)) our privacy cost for estimating Es is scaled down by a factor of s/n
With high probability for sufficiently large 8, Es E by matrix-Chernoff bound for sampling without replacement Tropp 2010
Algorithm Input: 8, X, d' E Xm C Ruxn Y (9,,... vi| E ylxn, privacy params: c, 8
A SubSampReuseCov
1: Sub-sample s points without replacement from X, we denote the sub-sampled design matrix by Xg.
Let (61, 61) = (#r/2, (0, oi), where oF = =22221og(25/00)1x11 Compute f, = ( X + E + AT)
Draw Ej ~ (/((a1)12((0000))
5: Draw è = [ 0r] ~ GaussMech(e/22
A - (121)
6: for = 1...
7: Set rù; = I, 0,
end for
Return W- [wi ... (1
Theorem 6. With M (enass/Meccee2,6/22 to the PRIMO problem with a²
111x1112)') Algorithm 4
an (a, Oc),, 6) solution
log(2d/p)
log(2d/p)
O 4
2
(34)
X n1
|
2422
n²
Proof Sketch. Our analysis will hinge on the case where e.g. that of standard private linear regression, which will extend to the PRIMO case by choice of as in the proof of Theorem 1 Now let:
wi -x (x the least squares estimator as before
wAA xxX"X + - the ridge regression estimator
w, Xxx5xs + ( (T) the sub-sampled least squares estimator
w. -Gx5 + F + XT) XTy + F2)) our differentially private estimate of wi
We note that 0 S (w - f(ws.) < X (1 11 1w s >IDII Then by the Lemma and Cauchy- Schwartz with respect to the norm x
(f(w)) - f(w.)) ||w. - -wia x x
311w0,
xxx w// 112 + 3/ w w.ll22z x + +31lw, w. 11 11 5
3 + 3||w, - w 1| x
3 3/00,
w.
2
X
(35)
Matrix Chernoff
SSP analysis Matrix Cheruoff
27

---

Published in Transactions on Machine Learning Research (01/2025)
So it suffices to bound each term with high probability. The second term, || w. x xxxxx+XX be bounded using the same arguments in Theorem 1 with small differences due to scaling. Crucially though, as we need to bound this in the norm induced by x rather than X X5 we will need to utilize the convergence of X + X via Matrix-Chernol bounds.
Lemma 13. Under the assumplion || O(nA), then w.p. 1 - p/22:
X 2
d dloo(2d/p))
11 d log(2d/p)
Iw T.sl yTx 0
WI
(36)
n²22
Bounding the first term can be reduced to bounding || ( follows more directly via the Matrix- Chernoff bound for sub-sampling without replacement: Lemma 14. Under the assumplion ||*1||2 O(nA), then w.p. p/2:
which
Matrix-Chernoff
|| log 2d/p
|/w wT XXX
As
Substituting into Equation 36 and minimizing over À gives the desired result.
7.8 Additional Experimental Results
Realizability of outcomes has a minimal effect.
Log Selativ Smor Outtoracc Gereoned Model
Bnd free
NeatCorte.athi
38
(a)
(b)
Figure 5: Both (a) and (b) show the log the ratio of the squared loss the private estimator to the square loss of the OLS estimator, but (a) the outcomes are synthetically generated from a linear model, whereas (b) the outcomes are generated from 2-layer neural network, test how the algorithms perform when the outcomes are not generated by linear model. All values averaged
iterations, over / = (1, 11, 101) with (e, 6) (5, ) and 5000, 25 synthetic dataset with Gaussian features.
DP-SGD outperforms ReuseCov for / vi We construct our dataset by sub-sampling n 5000 images of dimension d = 784 from MNIST Deng (2012), and generating / = 11, 101 outcomes from a noisy linear model with unit norm. We implement. DP-SGD using the Opacus Yousefpour et al. (2021) library from Meta, and do privacy accounting across regressions by composing in zCDP and then converting back to (c. DP DP. Figure shows that DP-SGD outperforms our ReuseCov algorithms when e (1, 11, 101), although, in agreement with the theory, this gap shrinks increases.
28

---

Published in Transactions on Machine Learning Research (01/2025)
Reraeirirnn Nelative srror Outcomes Generated from Hodel UNNAA
Figure 6: We construct our MNIST dataset by sampling 5000 random training images (d= 784), and then generating synthetic labels from a random linear model. All values are averaged over 5 iterations, over = (1, 11, 101) with (c (5, 1
n² ).
29


Reviews:
[{"review_id": "WIhJTmJh5H", "reviewer": "Reviewer_qHFs", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. The paper provides a strong theoretical analysis of DP multiple Linear Regressing (PRIMO) under different settings, including full DP, feature DP, and label DP with different ranges of data set sizes, feature dimensions, and label numbers.\n2. The dependency on label size $l$ is interesting.\n\nWeakness:\n1. The paper is poorly organized and badly written. For example, Section 3 mixes the summary of the results with the description of the algorithms and intuitions; the authors cite equations from another paper without clear explanations (eq.3, 5). Lemmas and Theorems, and their proofs are directly listed in the paper without clean organization. Lemmas from other papers are not clearly cited, e.g., Lemma 2.\n2. Most results directly apply existing methods and analyses, e.g., Lemma 2, 3, 4, 5, 6, and 7 are either citing results from other paper or well-known inequalities. The novelty of the paper is not significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies differentially private linear regression problems, which aim to protect the data privacy of the linear regression problem (with vector labels) when releasing the final model. The paper proposes a series of privacy-preserving algorithms by applying the Gaussian mechanism to different parts of the regression problems. The authors further provide the theoretical error bounds, i.e., the privacy-utility trade-off of these algorithms under different settings.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "Unifies the notations: \n1. The optimal/private solutions $W$ or $w$ have multiple definitions, which might be confusing. \n2. The notation on the top two lines on Page 4 is confusing; please provide more explanation.\n\nFigure 2 is a table.\n\nPlease improve the English usage and check the grammar. I suggest a complete rewrite of the paper.\n\nTypos:\n1. Improper citation format, e.g., missing parenthesis on page 1 citing Dwork & Roth (2014).\n2. eq(3), missing \")\", $w_{private}, w_{opt}$ not defined.\n3. Input of algorithm 1 $\\mathcal{X}$ should be $X$.\n4. What is normregw in eq (22)?", "broader_impact_concerns": "I didn't see Broader Impact Concerns in this paper.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "UOCp4p7wm2", "reviewer": "Reviewer_Jq7n", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\nSections 1 and 3 are easy to read. I particularly liked the clarity of the paragraph beginning \"We answer this question...\"\n\nThe techniques are straightforward but yield clear improvements over the naive baseline.\n\nI anticipate there are at least a few applications where PRIMO applies and label DP or feature DP is acceptible.\n\n*Weaknesses*\nThe submission is missing comparison with the naive baseline of using the optimal single-outcome mechanism $\\ell$ times. In particular, I would like to see how it fares in each of the $\\ell$ regimes that Table 1 decomposes, both asymptotically and experimentally. I also think this is a more reasonable benchmark for comparison than the lower bound by Bassily et al. (2014), since that result is limited to full DP and is \"not necessarily tight for linear regression\" as the authors admit.\n\nIn the genomics use-case that the submission focuses on, it is unclear what label and feature DP guarantee to an individual. Is it realistic to assume that the thousands of SNPs belonging to an individual are fair game to be processed without protections? On the face of it, it seems dangerous. The authors do acknowledge this in the Limitations section, but the experimental section still heavily focuses on algorithms for genomics that do not satisfy full DP; this raises the question of why they did not consider other datasets for evaluation.\n\nA limitation not discussed in the submission is the fact that the labels in the experiments were generated according to a random linear model. While this is a reasonable \"sanity-check\"---if there were no regime where an algorithm performed well on such data, it would clearly not be a good linear regression algorithm---I would caution that the experimental results are not as strong as if they were obtained by operating on real labels. This is more motivation to move to other datasets where labels are easier to come by than the genomics case.\n\n*Questions*\nIn the experiments, was ReuseCovProjX used or ReuseCovProjY? The \"Datasets\" paragraph of Experiments indicates the latter but the \"Experimental Details\" indicate the former. And why not test both?\n\nWhat happens when we restrict the privacy definition? Specifically, if we are limited to Renyi, concentrated, or pure DP?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This submission considers differentially private (DP) linear regression where each individual contributes a tuple of $d$ attributes and $\\ell > 1$ outcomes. The naive baseline would be to run a DP optimizer $\\ell$ times, but this incurs an overhead of $\\sqrt{\\ell}$ in the error as measured in squared-Froebenius norm. The authors begin with the observation that the $\\ell$ executions can re-use a noisy covariance estimate, reducing error in a ``small $\\ell$'' regime. For other values of $\\ell$, the authors show reductions in error are possible when it is permitted to remove protections from either features or labels. Experiments indicate that these relaxations bring the error close to that of the non-DP OLS estimator.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "As per the *Weaknesses*, extend Table 1 to include comparison with the naive baseline. Also, if time permits, experiments with other datasets where label or feature DP is more applicable than the genomics case.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "9zYEGPeCph", "reviewer": "Reviewer_gBuC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The primary focus of the paper is on objective perturbation, with the authors proving utility bounds in three settings: full-DP, feature-DP, and label-DP. For the full-DP setting, the authors propose the ReuseCovGauss method, which reuses the noisy covariance matrix $X^{T}X$ for all targets, where $X\\in \\mathcal{R}^{n\\times d}$ is the feature matrix. This approach yields improved bounds compared to the naive baseline that applies objective perturbation separately for each target. In the feature-DP setting, the authors provide a bound that is independent of the number of targets$l$. The authors conduct experiments on a genome dataset to support their theoretical results.\n\nOverall, the paper addresses a relevant and interesting problem in differentially private optimization. I have the following suggestions for improvement:\n\n1. The authors use privatized gradient descent as a baseline for their theoretical comparisons. It would be good to also include this method as a baseline in the experimental results.\n\n2. A table summarizing the conditions under which the bounds derived in this paper outperform or compare to the baseline methods would help clarify the paper's contributions.\n\n3. There is a missing bracket in Eq. (16).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates differentially private linear regression in multi-target settings, where the label $Y\\in\\mathcal{R}^{l}$ is a vector rather than a scalar. All targets share the same weight matrix.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please see weaknesses.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviewer comments have been sufficiently addressed during revision period.
Decision: Accept (poster)