DP-PCA: Statistically Optimal and Differentially Private PCA
Authors: Xiyang Liu
Weihao Kong
Prateek Jain
Sewoong Oh
Venue: NeurIPS 2022 Accept (2022)
Keywords: differential privacy
principal component analysis
private estimation

Abstract: We study the canonical statistical task of  computing the principal component from    i.i.d.~data under differential privacy. Although extensively studied in literature,  existing solutions fall short on two key aspects: ($i$) even for Gaussian data, existing private algorithms   require the number of samples  $n$ to scale super-linearly with $d$, i.e., $n=\Omega(d^{3/2})$, to obtain non-trivial results while non-private PCA  requires only $n=O(d)$, and ($ii$) existing techniques suffer from a large error even when the variance in each data point is small. We propose DP-PCA method that uses a single-pass minibatch gradient descent style algorithm to overcome the above  limitations. For sub-Gaussian data, we provide nearly optimal statistical error rates even for $n=O(d \log d)$. 

DP-PCA: Statistically Optimal and Differentially Private PCA
Xiyang Liu
Weihao Kong
Paul Allen School of Computer Science & Engineering
Google Research
University of Washington
veilaookong@google.coo
xiyangl@cs washington. edu
Prateek Jain
Sewoong Oh
Google Research
Paul Allen School Computer Science Engineering University of Washington, and Google Research sewoongocs washington. edu
prajain@google.com com
Abstract
We study the canonical statistical task computing the principal component from i.i.d. data in d dimensions under (s, (), -differrenta privacy. Although extensively studied literature, existing solutions fall short on two key aspects: (i) even for Gaussian data, existing private algorithms require the number of samples n scale super-linearly with d, i.e., n ((d3/2), to obtain non-trivial results while non-privat PCA requires only n = (d), and (ii) existing techniques suffer from non-vanishing error even when the randomness in each data point is arbitrarily small. We propose DP-PCA, which is single-pass algorithm that overcomes both limitations. It is based on private minibatch gradient ascent method that relies on private mean estimation to add minimal noise required to ensure privacy by adapting to the geometry of given minibatch of gradients. For uub-Gaussian data, provide nearly optimal statistical error rates even for Ö(d). Furthermore, we provide lower bound showing that sub-Gaussian style assumption is necessary in obtaining the optimal error rate.
Introduction
Principal Component Analysis (PCA) fundamental statistical tool with multiple applications including dimensionality reduction, data visualization, and noise reduction. Naturally, it is a key part of most standard data analysis and ML pipelines. However, when applied to data collected from numerous individuals, such the U.S. Census data, outcome of PCA might reveal highly sensitive personal information. We investigate the design of privacy preserving PCA algorithms and the involved privacy/utility tradeoffs, for computing the first principal component, that should serve as the building block more general rank-k PCA.
Differential privacy (DP) is widely accepted mathematical notion of privacy introduced in (1]] which is a standard in releasing the U.S. Census data (2) and also deployed in commercial systems 72 25 27]. A query database is said to be (s, -dfffferrent private if strong adversary who knows all other entries but one cannot infer that one entry from the query output, with high confidence. The parameters and restricts the confidence as measured by the Type-I and II emors [49] Smaller values E [0, oo) and E [0, imply stronger privacy and plausible deniability for the participants.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

For non con-private PCA with n i..d. samples in d dimensions, the popular Oja's algorithm (provided in Algorithm| 1) achieves the optimal error of sin(ū, v1) = é( /d/n), where the error is measured by the sine function of the angle between the estimate, é, and the principal component, V1. 45 For differentially private PCA, there is natural fundamental question: what is the extra cost we pay in the error rate for ensuring (e, 6)-DP?
We introduce novel approach we call DP-PCA (Algorithm and show that it achieves an error bounded by (ú, v) = Ō( ddyd/n+ d/ d/(en) for sub-Gaussian-lic data defined in Assumption which broad class of light-tailed distributions that includes Gaussian data as special case. The second term characterizes the cost of privacy and this is tight; we prove a nearly matching information theoretic lower bound showing that no (c. 8)-DP algorithm can achieve a smaller error. This significantly improves upon a long line of existing private algorithms for PCA, e.g., [14] g These existing algorithms are analyzed for fixed and non-stochastic data and achieve sub-optimal error rates of ((/d/n + d8/2 (en)) even the stochastic setting we consider.
38 36 23
A remaining question is whether the uub-Gaussian-- like assumption, namely Assumption A is necessary or if an artifact of our analysis and our algorithm. It turns out that such assumption on the lightness of the tail is critical; we prove an algorithmic independent and information theoretic lower bound (Theorem 5.4) to show that, without such an assumption, the cost of privacy is lower bounded by ((Vd/(En)) This proves separation of the error depending on the lightness of the tail.
We start with the formal description of the stochastic setting in Section 2 and present Oja's algorithm for non-private PCA. Our first attempt in making this algorithm private in Section Bl already achieves near-optimal error, if the data is strietly from a Gaussian distribution. However, there are two remaining challenges that we describe in detail in Section 4 (i) the excessive number of iterations of Private Oja's 's Algorithm (A (Algorithm 2) prevents using typical values of & used in practice, and (ii) for general -ab-Gaussian-like distributions, the error does not vanish even when the noise in the data (as measured by a certain fourth moment of a function of the data) vanishes. The first challenge is due to the analysis that requires amplification by shuffling [24] that is restrictive. The second due to its reliance on gradient norm clipping []] that does not adapt to the geometry of the current gradients. This drives the design of PP-PCA in Section that critically relies on two techniques overcome each challenge, respectively. First, minibatch SGD (instead of single sample SGD) significantly reduces the number iterations, thus obviating the need for amplification by shuffling. Next, private mean estimation (instead of gradient norm clipping and noise adding) adapts to the geometry of the problem and adds the minimal noise necessary to achieve privacy. The main idea this geometry adaptive stochastic gradient update is explained in detail in Section 6 along with a sketch of proof.
Notations. For vector E Rd we use ||ق||| to denote the Euclidean norm. For matrix X E Rddd we use |||| = |ax [|Xe|la to denote the spectral norm. We use Ia to denote d x d identity matrix. For n g+. let [n] := $2 = {x E Rdd ||^||| = =1.. Ō() hides logarithmic factors in n, d, and the failure probability Ç.
nn.. Let s denote the unit d-sphere of (2, i.e..
2 Problem formulation and background on DP
Typical PCA assumes i.i.d. data faz E Rd from a distribution and finds the first eigenvector of = B[ - (2; [[x.))]] E ddd Our approach allows for more general class of data {A gdxdy that recovers the standard case when A, (z, - E[x,)) (z+ E(x:))
Assumption 1 ((E, ".
a, 2,)3)) -model). Let A2....... An Raxd be sequence of (not necessarily symmetric) matrices sampled independently from the same distribution that satisfy the following with PSD) matrices Σ E dddd and Hr, E Rddx and positive scalar parameters M, V, K, K6, a, and +2
A.1. Let Σ E[A,), for symmetric positive semidefinite (PSD) matrix E E Bddd > denote the i-th largest eigenvalue E, and k == X1 >1/(>11 X2).
A.2. ||A,- - El1z < M almost surely.
A.3. max [||E [[A, (A, - E) ]],, E [[A, T)T(AA ))]] s XLV.
2

---

I [A, Ejol" 1/(2o) K² |
A.4. max|ju] 1./ E)uu (A, T. We denote 7/ max |u|l=1 |1/22
exp
I 2, where Ha = (1/A))
The first three assumptions are required for PCA even if privacy is not needed. The last assumption provides a Gaussian-like tail bound that determines how much noise we need to introduce in the algorithm for (s, 6)D. The following lemma is useful in the analyses.
Lemma 2.1. Under A.1 and A.4 4 in Assumption
7 for any unit vector v, with probability 1
M (A. E)ul z H2 log 20 (2/C).
(1)
2.1 Oja's algorithm
In non-private setting, the following streaming algorithm introduced in [69 achieves optimal sample complexity as analyzed in [5]. It is projected stochastic gradient ascent on the objective defined on the empirical covariance: max -1 (1/n) Ei= w" Aqu.
Algorithm 1: (Non-private) Oja's Algorithm
Choose wh uniformly at random from the unit sphere
2 for f = .,,...., I do wy & w + m-A,wi-1 wi + w///[w/l
Return WT
Central to our analysis is the following error bound on Oja's Algorithm from
Theorem 2.2 45
Theorem 4.1.). Under Assumptions A.7 A.3 suppose the step size 1)t
(A1 +1) for some > 1/2 and 5 := 20 max (RMa, R V + a) a1)22/logl /log(1 + (C/100)))
T then there exists constant C such that Algorithm 7 outputs wr achieving w.p. 1 S,
sin² (WT, v1) I C Clog(1/()
V²R²V (2a - 1)T
E T
+ d
2)
2
2.2 Background on Differential Privacy
Differential privacy (DP), introduced in [21] de facto mathematical measure for privacy leakage of a database accessed via queries. It ensures that even an adversary who knows all other entries cannot identify with a high confidence whether person of interest participated in a database or not.
multisets S and S', say the pair (S, S") is neighboring if JS \ S'I [ \ S1 S 1. We say a stochastic query q over datasel S satisfies (e, diffferrrttia privacy for some 0 and å (0,1) ifT(((()) A) (P((((())) A) for all neighboring (S,5") and all subset A of the range of q-
Definition 2.3 (Differential privacy (2I)). Given
Small values of and ensures that the adversary cannot identify any single data point with high confidence, thus providing plausible deniability. We provide useful DP lemmas in Appendix B Within our stochastic gradient descent approach PCA, we rely on the Gaussian mechanism to privatize
each update. The sensitivity of a query is defined as Ag nunihihhborigg (5,5*) (1q(S) - [[
Lemma 2.4 (Gaussian mechanism (22). For a query q with sensitivity Aq (0, 1), and E (0, 1), the Gaussian mechanism outputs (S) + NO (A,(V2log( (1..22281)2))
and achieves (c. DD-
This is special of family of output perturbation mechanisms which includes the Laplace mechanism (21) and stair-case mechanisms [34]. The latter is shown to be optimal one-dimension 35] and for hypothesis testing under local DP [48]. Another mechanism we frequently use is the private histogram learner of [56], whose analysis is provide in Appendix B along with various composition theorems to provide end-to-end guarantees.
2.3
Comparisons with existing results in private PCA
We briefly discuss the most closely related work and provide more previous work in Appendix A Most existing results assume fixed data under deterministic setting where each sample has bounded

---

Algorithm 2: Private Oja's Algorithm
Input: S = (A, E [Rdxd] privacy (e, 6), learning rates { h=
i== Randomly permute S' and choose wo uniformly random from the unit sphere
Set DP noise multiplier: <- C" (olog(n/0)/((
3 Set clipping threshold: 3 +
Ky log (nd/c) + 1)
for 1=1, 2, .... n do
5
Sample 24 ~ IO,
w + 1 To clip, (A( + 2mBaz, where clips(x) min(1,
3 T
We + / /w//l
Return W/
norm, ||=;||| Il S B, and the goal is to find the top eigenvector of E : (1/n) 1 (z;
(z;-
for the empirical mean ft. For the purpose of comparisons, consider Gaussian 2; ~ ~N, with | S 8 = ((v) V (on(/(i) for all E [nd] with probability 1 - Ç. The first line of approaches in 4 2 is Gaussian mechanism that outputs PCA(É Z), where Z is symmetric matrix with i..d. Gaussian entries with a variance ((B2) ((ff/n))/// log to ensure (s, ().d). The tightest
result in [23 Theorem 7] achieves
sin v1) = Ō (M((
d 8/2
1og(L/0))
(3)
en
with high probability, under strong assumption that the spectral gap is very large: A X2 w(d (/log(18)/((m)) In typical scenario with A O(1), this requires a large sample size of n = w(d /e). Since this Gaussian mechanism does not exploit the statistical properties of ii.d. samples, the second term in this upper bound is larger by a factor of d'/2 compared to the proposed DP-PCA (Corollary 5.2). The error rate of Eq. is also achieved in (38 336 by adding
Gaussian noise the standard power method for computing the principal components. When the
spectral gap, A Ag. is smaller, it is possible to trade-off off the dependence in and the sampling ratio d/n, which we do not address in this work but is surveyed in Appendix A
3 First attempt: making Oja's ss Algorithm private
Following the standard recipe in training with DP-SGD, e.g., M and a recent work (75), we introduce Private Oja's s Algorithm in Algorithm 2 At each gradient update, we first apply gradient norm clipping to limit the contribution of a single data point and next add an appropriately chosen Gaussian noise from Lemma 2.4 to achieve (s, DDDP, end-to-end. The choice of clipping threshold 3 ensures that, with high probability under our assumption, we do not clip any gradients. The choice of noise multiplier a ensures (c, 5D-..
One caveat in streaming algorithms that we access data n times, each with a private mechanism, but accessing only single data point at time. To prevent excessive privacy loss due to such large number of data accesses, we apply a random shufffing in line [ Algorithmm 2 in order to benefit from standard amplification by shuffling 24 29I. This gives amplified privacy guarantee that allows us to add a small noise proportional to a = (e)gn)))))())) Without the shuffle amplification, we will instead need larger noise scaling guarantee. However, this comes with a restriction that the amplification holds only for small values of e = O( / log(n//// (n))/n). Our first contribution in the proposed DP-PCA (Algorithm 3 is to expand this range to g O(1), which includes the practical regime of interest E E 5).
= (log(n/5)) /))E) resulting in suboptimal utility
Lemma 3.1 (Privacy). If a O (og(g////// and the noise multiplier is chosen to be Ω (lg((n/))((e//))) then Algorithm iis is (e, 8)-P.
Under Assumption D we select gradient norm clipping threshold 3 such that gradient exceeds B. Lemma 3.2 (Gradient clipping). Let 8 = C) (olKKyloo"(ndd)) + 1) some constant C > 0. Then with probability Ç. -| S |3 for any fixed w:-1 independent of As, for all t E [m].
We provide proofs of both lemmas and the next theorem in Appendix D When no clipping is applied, we can use the standard analysis of Oja's 's Algorithm from 45 to prove the following utility guarantee.

---

Theorem 3.3 (Utility). Given n ii.d. samples {A, E Raxd] satisfying Assumption with parameters (E, M, V, K, a, r.) if
V + dn + log(1/))) {
n = 0 +
+M 0
(4)
with a large enough constant, then there exists a positive universal constant e1 and choice of learning rate tt. that depends on (t, M, V, K, a, Y 11- 22, n, s, 8) such that Algorithm with choice of 0.01 outputs wn that achieves with probability 0.99,
sin" (wa, 01) = = V
(7+ 1) log (1/0) (110))
(5)
c2n?
where (.) hides polyylogarihmiicactin in n, d, 1/s, and log(1/6) and polynomial factors in K.
The first term in Eq. (5) matches the non- non-priven private error rate for Oja's algorithm in Eq. with a = O(logn) n) and T = n,, and the second term is the price we pay for ensuring (c, 6)-P..
Remark 3.4. For canonical setting of a Gaussian data with A; = T,T, and 2; ~ (N, E), we have, for example from {70) Lemma 1.12], J, that M Ooglog()) V = Odd), K = 4, a 1, and
y² = (1). Theorem 3.3 implies the following ervor rate:
sin (Wn, v1) = 0 ( d
d2 log (1/5)
E2n²
Comparing to lower bound in Theorem 5.3 this is already near optimal. However, for general distributions satisfying Assumption [ Algorithm 2 (in particular the second term in Eq. (5) can be significantly sub-optimal. We explain this second weakness of Private Oja's Algorithm in the following section (the first weakness is the restriction on O (lg)onn//)))/
4 Two remaining challenges
We explain the two remaining challenges in Private Oja's Algorithm and propose techniques to overcomes these challenges that lead to the design of DP-PCA (Algorithm 3).
First challenge: restricted range of & lll/oo///////// This is due to the large number, of iterations that necessitates the use number of iterations with minibatch SGD. For T O(log n) and 1,2, ..... we repeat
amplification by shuffling Theorem D.I We reduce the
Bt-1
WT/BBa
w/ +- W1-1 +
Σ
(A,
B 2t
and wt wt/ wl/llu//l
B
B(t+((t-1)
where 21 (00, and the minibatch size is B Ln/T]. Since the dataset is accessed only
T (log" n) times, the end-to-end privacy is analyzed with the serial composition (Lemma B.3 instead of the amplification by shuffling. This ensures (e, DDP for any = O(1), resolving the first challenge, and still achieves the utility guarantee of Eq. (5).
Second challenge: excessive noise for privacy. This is best explained with an example.
Example 4.1 (Signal and noise separation). Consider setting with A, I and x4 = 9, + na where 8; with probability half and 8; = -u otherwise for a unit norm vector and n, (0, o I). We want to find the principal component of Σ = E[E,,,
vu + I²I, which is This construction decomposes the signal and the noise. For A; = vo" + 8in? + n48 + +nan the signal component is determined by wo that is deterministic due to the sign cancelling. The noise Ratio
component is s;n. + nns8 n.m. which is random. We can control the Signal-to-Noke (SNR), 1/02, by changing a², and we are particularly interested in the regime where o² is small. As we are interested in a² 1, this satisfies Assumption 7 Tith = 1 g², X2 =² V O(da"),
K = 0(1), a 11, and 72 = o². Substituting this into Eq. (5). Private Oja's Algorithm achieves
sin sin?(wns v1) 0 7
d2 log(1/8)
(8)
22n²
where interested in o² 1.
5

---

400
44
Figure 1: 2-d PCA under the Gaussian data from Remark 3.4 (left) shows that the average gradient (red arrow) is smaller than the range of the minibatch of 400 gradients (blue dots). Under Example 4. (right), the range can be made arbitrarily smaller than the average gradient.
Algorithm 3: Differentially Private Principal Component Analysis (DP-PCA)
Input: S ={A,)== (s, 6), batch size B Σ4, learning rates ( Choose wh uniformly at random from the unit sphere
L//B probability Ç E (0,
for t 1....... T = /n/B] B do
Run Private Top Eigenvalue Estimation (Algorithm 4 with (e/2,8/2)-DP and failure
probability </(21") on [AB(L-1);;;; Hi B/2] Let the returned estimation be A, >
Run Private Mean Estimation (Algorithm with (s/2, (e/2,6/2)-0) -DP, failure probability C/(2T),
and the estimated eigenvalue 2Á, on { ( (BB (e//2)) Let the returned
mean gradient estimate be 9e E Bdd w w Ncht W/ f- w / ||,
Return WT
This is problematic since the second term, due to the DP noise, does not vanish as the randomness a2 in the data decreases. We do not observe this for Gaussian data where signal and noise scale proportionally as shown below. We reduce the noise we add for privacy, by switching from a simple norm clipping, that adds noise proportional to the norm of the gradients, private estimation, that only requires the noise to scale as the range of the gradients, i.c. the maximum distance between two gradients in the minibatch. The toy example above showcases that the range can be arbitrarily smaller than the maximum norm (Fig. D. We want to emphasize that although the idea of using private estimation within an optimization
been conceptually proposed in abstract settings, e.g., in [5]] DP-PCA is the first setting where (2) such separation between the norm and the range of the gradients holds under any statistical model, and hence (ii) the long line of recent advances private estimation provides significant gain over the simple DP-SGD I
Differentially Private Principal Component Analysis (DP-PCA)
Combining the two ideas of minibatch SGD and private mean estimation, propose DP-SGD. We use minibatch SGD of minibatch size B = O(n/ log" n) to allow for larger range of = 0(1. We use Private Mean Estimation to add an appropriate level of noise chosen adaptively according to Private Eigenvalue Estimation. We describe details of both sub-routines in Section
We show upper bound the error achieved by DP-PCA under appropriate choice of the learning rate. We provide a complete proof in Appendix E. that includes the explicit choice of the learning rate ne in Eq. (67). and proof sketch is provided in Section 6.
Theorem 5.1. For e E (0, 0.9), DP-PCA guarantees (s, 8)-DP for all S, B, S. and ô. Given n i.idd samples {A, E BRdddin satisfying Assumption
1
with parameters (E, M, V, K, K, 2)) if
n = =0 (/2((00(1/0))822 K. x dxy (log(1/5))112 d dlog(1/8)
(9)
E
E
E
with large enough constant and 8 < 1/nn then there exists positive universal constant e₁ and a choice of learning rate Ti that depends on (1, M, V, K, a, XG, A X2, n, e, 8) such that T [n/B] B] steps of DP-PCA in Algorithm 3 with choices of = 0.01 and B cin/ n)?

---

outputs wr such that with probability 0.99,
sin (wr, 01) = ② k
(0k(1)
(V(
V + Id
ed/logg1//0
(10)
where O.) hides poly-logarihhmicaactte in n, d, 1/e, and (o)( and polynomial factors factors in K.
We further interpret this analysis and show that (i) DP-PCA is nearly optimal when the data is from a Gaussian distribution by comparing against a lower bound (Theorem (.3): 3 and (ix) DP- PCA significantly improves upon the private Oja's algorithm under Example [. We discuss the
necessity of some of the assumptions at the end of this section, including how to agnostically find the
appropriate learning rate scheduling.
Near-optimality of DP-PCA under Gaussian distributions. Consider the case of i.i.d. samples {z;)ī=1 from Gaussian distribution from Remark 3.4
Corollary 5.2 (Upper bound; Gaussian distribution). Under the hypotheses of Theorem 3.1 and {A, = x. ) with Gaussian random vectors x4 xz's, after T = n/ steps, DP-PCA outputs wr that achieves, with probability 0.99.
Ö 0(m1 K
d
d (l1o((10)) EN
sin(wr, U1)
(11)
We prove a nearly matching lower bound, up to factors of / /1//2 and v (1/g( One caveat is that the lower bound assumes pure-DP with 5 O. We do not yet have lower bound technique for approximate DP that is tight, and all known approximate DP lower bounds have gaps to achievable upper bounds in its dependence in log(1/5), e.g., 62). We provide a proof in Appendix C.I
Theorem 5.3 (Lower bound; Gaussian distribution). Let Me be class of (E, D)P estimators that map i.idd samples to estimate i E Rd. A set of Gaussiun distributions with (A1, X2) the first and second eigenvalues of the covariance matrix is denoted by P P2)) For d>e where > some absolute constant, there exists a universal constant C > 0 such that
sup ES (0((((()))))) 2 C'min (N (<(V2
d
A2 Ai
inf B. PEP(A.))))
1
(12)
en
Comparisons with private Oja's algorithm. We demonstrate that DP-PCA can significantly improve upon Private Oja's Algorithm with Example where DP-PCA achieves error bound of sin(wr, v1) = (( + (og/oo( (em)) As the noise power x² decreases DP-PCA achieves a vanishing error, whereas Private Oja's Algorithm has a non-vanishing error in Eq. (8). This follows from the fact that the second term in the error bound in Eq. 10) scales % which can be made arbitrarily smaller than the second term in Eq. (5) that scales as (y + 1). Further, the error bound for DP-PCA holds for any (1), whereas Private Oja's 's Algorithm requires significantly smaller O(v log(n/0)/n).
Remarks on the assumptions of Theorem 5.1 We have an exponential dependence of the sample complexity in the spectral gap, 2 exp (x²) T his ensures we have a large enough T = |n/ B to
reduce the non-dominant second term in Fq. (2) in balancing the learning rate V). and 7 (which is explicitly shown in Eqs. 69 and (70p in the Appendix). It is possible get rid of this exponential dependence at the cost of an extra term of 2 log(1/6)/(en)
in the error rate in Eq. 10)) by selecting slightly larger T cs² log² n. A Gaussian-like tail bound in A Assumption A.4 is necessary get the desired upper bound scaling O(d /Log(1 (og(1/))/(e)) (en)( in Eq. 11 for example. The next lower bound shows that without such assumptions on the tail, the error due to privacy scales as 2( / /d (og)))))(en)) We believe that the dependence in 8 is loose, and it might be possible to get a tighter lower bound using (52). We provide proof and other lower bounds in Appendix C
Theorem 5.4 (Lower bound without Assumption A.4). Let Me be class of (e, 5)- estimators that map i.i.d. samples an estimate 0 Rd. A set of distributions satisfying Assumptions A.1 A.3
7

---

with M = Ō + / h). V = (dd) and = O(1) is denoted by P. For d 2 2, there exists
universal constant C such that
J (VaA log ((1 ((1- (
inf sup BS (sin( 2 Camin
(13)
Be PEP
EN
Currently, DP-PCA requires choices of the learning rates, Th, that depend on possibly unknown quantities. Since we can privately evaluate the quality of our solution, one instead run multiple
instances of DP-PCA with varying 7 01 (c/(22 + 1) and find the hest choice of e > 0 and c2 > 0. Let Wr(C,, 62) denote the resulting solution for instance of {? c1/(e2 + f)) }
- We first
set target error Ç. For each round i I,.... we will run algorithm for (cI, C2) = 2 2- x i+2 ..., 2..,2"=1 and (c1, 02) = 12- 2-112 ..... 2". 2- [2 [2--1 2 3. and compute each sin sin(wr (er 02), v1) privately, each with privacy budget e; (2--) d
[2- 2-
(2i-) We terminate the algorithm once there there is (r1 62) satisfies sin( (wr((rr, 62), v1) I Ç. is clear that this search meta-algorithm terminate in logarithmic round, and the total sample complexity only blows up by poly-log factor.
Private mean estimation for the minibatch stochastic gradients
DP-PCA critically relies on private mean estimation reduce variance of the noise required to
achieve (e, 6)-DP. We follow a common recipe from [56, 50 54 8 15
First, we privately find an
approximate range of the gradients in the minibatch (Alg- 4). Next, we apply the Gaussian mechanism
to the truncated gradients where the truncation is tailored to the estimated range (Alg. 5
estimating the range. We need to find an approximate range of the minibatch of gradients in order to adaptively truncate the gradients and bound the sensitivity. Inspired by a private precondition- ing mechanism designed for mean estimation with unknown covariance from [53] we propose to use privately estimated top eigenvalue of the covariance matrix of the gradients. For details on the version of the histogram learner we use in Alg. in Appendix E.2 we refer to 661 Lemma D.1J. Unlike the
Step I:
private preconditioning of (53 that estimates all eigenvalues and requires (d log(1 /e) samples, we only require the top eigenvalue and hence the next theorem shows that we only need
())))))))))
Theorem 6.1. Algorithm 4 is (e, 8)- Let 9i = for some fixed vector u, where A, satisfies A.1 such that the mean is E[gs]] Lu and the covariance is EE [u) = H,, With a large enough sample size scaling
and A.4 in Assumption 7
Σu)
K² d log(dlog(1/666)/(Ca)) log (Bd (B//()))g(1((60))
K d log(1/8)
B = 0
-
Algorithum outputs Å achieving Å e [(//V2)A]]HH]ll> | with probability 1 Ç. where the pair (K > 0, a >> 0) parametrizes the tail of the distribution in A.4 and Ô(-) hides logarithmic factors B, d, log(1/),, and
We provide a proof in Appendix E.2 approaches require known bounds such as oi I (Ha) I ouxx for all E [d] [56], and other agnostic approaches are more involved such as instance optimal universal estimators of [17]
There are other ways to privately estimate the range. Some
Gaussian mechanism for mean estimation. Once we have good estimate of the top eigenvalue from the previous section, we use to select the bin size of the private histogram and compute the truncated empirical mean. Since truncated empirical mean has bounded sensitivity, we can use Gaussian mechanism to achieve DP. The algorithm now standard in DP mean estimation, e.g., 50). However, the analysis is slightly different since our assumptions g, 's are different. For completeness, we provide the Algorithm SS Appendix E.3
Step 2:
The next lemma shows that the Private Mean Estimation is (c, 8)-DP, and with high probability clipping does not apply to any of the gradients. The returned private mean, therefore, distributed as spherical Gaussian centered at the empirical mean of the gradients. This result requires that we have
good estimate of the top eigenvalue from Alg. 4 such that Á ~ X2||,, |2- This analysis implics
8

---

that we get an unbiased estimate of the gradient mean (which is critical in the analysis) with noise scaling as /
(which is critical in getting where 7² = maX [Hu
the tight sample complexity in the second term of the final utility guarantee in Eq. (TO). We provide
a proof in Appendix E.3
Lemma 6.2. For 0.9) and any ā E (0. 1), Algorithm 5 is (e, 8)-DP. Let gi A,u for some
fixed vector u, where A; satisfies A. and A.4 in Assumption such that the mean is Elga] = Eu
and the covariance is E[[ - [x) Eu) I1 - A E Halllalle/ /2, <2 H 112]
5 S 1/B, and B ( (oo((//))))/)))))) (g(()((())) then, with probability S. 9i E
3K Vlog (Bd/C), 3K lo (Bd/C())))) for all i E [B].
6.1 Proof sketch of Theorem 5.1
We choose B - (n/ log" n²) such that we access the dataset only T = O(log" n) times. Hence we do not need to rely on amplification by shuffling. To add Gaussian noise that scales as the standard deviation of the gradients in each minibatch (as opposed to potentially excessively large mean of the gradients), DP-PCA adopts techniques from recent advances in private mean estimation. Namely, we first get private and accurate estimate of the range from Theorem 6.1 Using this estimate, A, Private Mean Estimation returns unbiased estimate of the empirical mean of the gradients, long as no truncation has been applied as ensured by Lemma 6.2
This gives
w/ f w1-1 + 17
AB(--1)+ Be2e
(14)
8K 22, log" (Bd/2) 2d (2566))))
for 2 (O I) and 3, Gaussian random vectors and the fact that
Using rotation invariance of spherical = 1, we can reformulate it as
1
W/-
B
w/ + W1-1 + 17t
A An(:- 1)++ B.G, W1-11
(15)
B
A with A, substituting Ag.
This process can be analyzed with Theorem 2.2
7 Discussion
Under the canonical task of computing the principal component from i.i.d. samples, we show the first result achieving an optimal error rate. This critically relies on two ideas: minibatch SGD and private mean estimation. In particular, private mean estimation plays a critical role in the case when the range of the gradients significantly smaller than the norm; we achieve an optimal error rate that cannot be achieved with the standard recipe of gradient clipping.
Assumption A.4 can be relaxed to heavy-tail bounds with bounded k-th moment on A,, which case we expect the second term in Eq. (10) to scale as O(d( /om drawing analogy from a similar trend in computationally inefficient DP-PCA without spectral gap 62] Corollary 6.10].
When fraction of data corrupted, recent advances in [84]]] 58, 46) provide optimal algorithms for PCA. However, existing approach of (62) for robust and private PCA is computationally intractable. Borrowing ideas from robust and private mean estimation in [1], one can design an efficient algorithm, but at the cost of sub-optimal sample complexity. It is an interesting direction to design an optimal and robust version of DP-PCA Our lower bounds are loose in its dependence in log(1/6). Recently, a promising lower bound technique has been introduced in [52] that might close this gap.
There are two ways to extend our framework to general rank-r PCA, whose analyses are promising research directions. First, applying Hotelling's 's deflation method [4], we can iteratively find the PCA components one by one, by alternating our DP-PCA and deflation. For example, in one step of the iteration, we only update the current iterate vector in the directions orthogonal to all the previously found PCA components. Repeating this steps gives the estimates of the top principal components. Secondly, we can directly apply Oja's algorithm. We keep track of a r-dimensional subspace in the Oja's update rule for PCA, and perform QR decomposition to keep the iterates on the Grassmannian manifold. It might be possible to extend the analysis of [2] to analyze the private version.

---

Acknowledgments and Disclosure of Funding
This work is supported in part by Google faculty research award and NSF grants CCF-1705007, CNS-2002664, 192995,,, DMS-2 21 134012, CCF-2019844 as part of NSF Institute for Foundations of Machine Learning (IFML), 124-2111271 as part of NSF Institute for Future Edge Networks and Distributed Intelligence (AI-EDGE).
References
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the ACM SIGSAC conference computer and communications security, pages 308-318, 2016.
[2] John M Abowd. The us census bureau adopts differential privacy. In Proceedings of the 24th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pages 2867-2867, 2018.
[3] Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. Differentially private assouad, fano, and le cam. In Algorithmic Learning Theory, pages 48-78. PMLR, 2021.
[4] Maria-Florine Balcan, Simon Shaolei Du Yining Wang, and Adams Wei Yu. An improved depeeeeenyyccy analysis of the noisy power method. In Conference on Learning Theory, pages PMLR, 2016.
[5] Rina Foygel Barber and John C Duchi. Privacy and statistical risk: Formalisms and minimax bounds. arXiv preprint arXiv: 14Xx::111.44551. 2014.
[6] Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Advances Neural Information Processing Systems, 32, 2019.
[7] Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Effi- cient algorithms and tight error bounds. In 2014 JEEE 55th Annual Symposium on Foundations of Computer Science, pages 464-473, IEEE, 2014.
[8] Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. arXiv preprint arXiv:2006.0660 2020.
[9] Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Proceedings of the twenty-forrth ACM CGGMOD-SIGACT-SIGEN symposium on Principles of database systems, pages 128-138, 2005.
[10] Gavin Brown, Marco Gaboardi, Adam Smith, Jonathan Ullman, and Lydia Zakynthinou. Covariance-aware private mean estimation without private covariance estimation. Advances in Neural Information Processing Systems, 34, 2021.
[11] Mark Bun, Kobbi Nissim, and Uri Stemmer. Simultancous private learning of multiple concepts.
J. Mach. Learn. Res., 20:94-1, 2019..
[12] Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. Advances Neural Information Processing Systems, 32, 2019.
[13] T Tony Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. arXiv preprint arXiv:1902.04495, 2019.
[14] Kamalika Chaudhuri, Anand D Sarwate, and Kaushik Sinha. A near-optimal algorithm for
sefferentiallly-rrvvte principal components. The Journal of Machine Learning Research, 14(1):2905-2943, 2013.
[15] Christian Covington, Xi He, James Honaker, and Gautam Kamath. Unbiased statistical estima- tion and valid confidence intervals under differential privacy. arXiv preprint arXiv:21 14465, 2021.
10

---

[16] Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, and Benjamin IP Rubinstein. Robust and private bayesian inference. In International Conference on Algorithmic Learning Theory, pages 291 195- Springer, 2014.
[17] Wei Dong and Ke Yi. Universal private estimators. arXiv preprint arXiv:2111.02550 2021.
[18] John Duchi and Ryan Rogers. Lower bounds for locally private estimation via communication complexity. In Conference on Learning Theory, pages 1161-1191. PMLR, 2019.
[19] John Duchi, Michael Jordan, and Martin Wainwright. Minimax optimal procedures for locally private estimation. Journal of the American Statistical Association, 113(521):182-200 2018.
[20] Cynthia Dwork and Jing Lei. Differential privacy and robust statistics. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 371-380, 2009.
[21] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference, pages 265-284. Springer, 2006.
[22] Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Founda- tions and Trends in Theoretical Computer Science, 933-4)211-440) 2014.
[23] Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for preaerviie principal component analysis. In Proceedings of the forty-sixth anmual ACM symposium on Theory of computing, pages 11 11-20, 2014.
[24] Úlfar Erlingsson, Vitaly Feldman, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and Abhradeep Thakurta. Amplification by shuffling: From local to central differential privacy via anonymity. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2468-2479, SIAM, 2019.
[25] Ülfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. Rappor: Randomized aggregatable privacy-preservie ordinal response. In Proceedings of the 2014 ACM SIGSAC conference on computer and communications security, pages 1054-1067, 2014.
[26] Hossein Esfandiari, Vahab Mirrokni, and Shyam Narayanan. Tight and robust private mean estimation with few users. arXiv preprint arXiv:2110.11876 2021.
[27] Giulia Fanti, Vasyl Pihur, and Ülfar Erlingsson. Building rappor with the unknown: Privacy- preserving learning of associations and data dictionaries. Proceedings on Privacy Enhancing Technologies, 2016(3):41-61, 2016.
[28] Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Proceedings of the 52nd Annual ACM SIGACT Symposium Theory of Computing, pages 439-449, 2020.
[29] Vitaly Feldman, Audra McMillan, and Kunal Talwar. Hiding among the clones: A simple and nearly optimal analysis of privacy amplification by shuffling. In 2021 IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS), pages 954-964. IEEE, 2022.
[30] Vitaly Feldman and Thomas Steinke. Calibrating noise to variance in adaptive data analysis. In Conference On Learning Theory, pages 535-544. PMLR, 2018.
[31] James Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of privevy-preserving bayesian data analysis. arXiv preprint
2016.
[32] Marco Gaboardi, Ryan Rogers, and Or Sheffet. Locally private mean estimation: z-test and tight confidence intervals. In The 22nd International Conference on Artificial Intelligence and Statistics, pages
PMLR, 2019.
[33] Arpita Gang, Bingqing Xiang, and Waheed U Bajwa, Distributed principal subspace analysis for partitioned big data: Algorithms, analysis, and implementation. IEEE Transactions on Signal and Information Processing over Networks, 7:699-715, 2021.
11

---

[34] Quan Geng, Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The staircase mechanism in differential privacy, IEEE Journal of Selected Topics in Signal Processing, 977:1177-1184, 2015.
[35] Quan Geng and Pramod Viswanath. The optimal mechanism in differential privacy. In 2014 IEEE international symposium on information theory, pages 2371-2375. IEEE, 2014.
[36] Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Advances in neural information processing systems, 27, 2014.
[37] Moritz Hardt and Aaron Roth. Beating randomized response on incoherent matrices. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 1255- 1268, 2012.
[38] Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computa- tion. In Proceedings of the forty forty-fithh annual ACM symposium on Theory of computing, pages 331-340, 2013.
[39] Samuel Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via sum-of-squares exponential mechanism. arXiv preprini arXiv:2111. 12981, 2021.
[40] Harold Hotelling. Analysis of complex of statistical variables into principal components. Journal of educational psychology. 24(6):417, 1933.
[41] Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data, arXiv preprint arXiv:2107.11136, 2021.
[42] De Huang, Jonathan Niles-Weed, and Rachel Ward. Streaming k-pca: Efficient guarantees for oja's algorithm, beyond rank-one updates. In Conference on Learning Theory, pages 2463-2498. PMLR, 2021.
[43] Hafiz Imtiaz and Anand D Sarwate. Differentially private distributed principal component analysis. In 2018 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages
IEEE, 2018
[44] Hafiz Imtiaz and Anand D Sarwate. Distributed differentially private algorithms for matrix and tensor factorization. IEEE journal of selected topics in signal processing, 1246:1144,,1464, 2018.
[45] Prateck Jain, Chi Jin, Sham M Kakade, Praneeth Netrapalli, and Aaron Sidford. Streaming pea: Matching matrix bernstein and near-optimal finite sample guarantees for oja's algorithm. In Conference on learning theory, pages 1147-1 164. PMLR, 2016.
[46] Arun Jambulapati, Jerry Li, and Kevin Tian. Robust sub- sub-gaussian principal component analysis and width-independent schatten packing. Advances in Neural Information Processing Systems, 33, 2020.
[47] Matthew Joseph, Janardhan Kulkarni, Jieming Mao, and Steven Z Wu. Locally private gaussian estimation. Advances in Neural Information Processing Systems, 32, 2019.
[48] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. Extremal mechanisms for local differential privacy. Advances in neural information processing systems, 27, 2014.
[49] Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning, pages 1376-1385 PMLR, 2015.
[50] Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high- dimensional distributions. In Conference on Learning Theory, pages 1853-1902. PMLR, 2019.
[51] Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. arXiv preprint arXiv:2106. 00.00003.3, 2021.
12

---

[52] Gautam Kamath, Argyris Mouzakis, and Vikrant Singhal. New lower bounds for private estimation and generalized fingerprinting lemma, arXiv preprint WwXiv:2205.0852, 2022.
[53] Gautam Kamath, Argyris Mouzakis, Vikrant Singhal, Thomas Steinke, and Jonathan Ullman. A private and computationally--efiiienn estimator for unbounded gaussians. arXiv preprini arXiv:2111.04609 2021.
[54] Gautam Kamath, Vikrant Singhal, and Jonathan Ullman. Private mean estimation of heavy-tailed distributions. arXiv preprini urXiv:2002.09464 2020.
[55] Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms, pages 1495-1414. SIAM, 2013.
[56] Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. arXiv preprint arXiv: 1711. 1.09908 2017.
[57] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
[58] Weihao Kong, Raghav Somani, Sham Kakade, and Sewoong Oh. Robust meta-learning for mixed linear regression with small batches. Advances in Neural Information Processing Systems, 33, 2020.
[59] Pravesh K Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. arXiv preprint urXiv:21 2021.
[60] Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu. Private non-smooth empirical risk minimiza- tion and stochastic convex optimization in subquadratic steps. arXiv preprint htt::2103.153555 2021.
[61] Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. Advances in Neural Information Processing Systems, 34, 2021.
[62] Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statistics in high dimensions. In Conference on Learning Theory, pages 1167-1246. PMLR, 2022.
[63] Pascal Massart. Concentration inequalities and model selection: Ecole d' Eté de Probabilités de Saint-Flour XXXIII-2003. Springer, 2007.
[64] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. In 48th Anmual IEEE Symposium on Foundations of Computer Science (F)CS'07), pages 94-103. IEEE, 2007.
[65] Frank D McSherry. Privacy integrated queries: an extensible platform for privacy-preserving data analysis. In Proceedings of the 2009 ACM SIGMOD International Conference on Manage- ment of data, pages 19-30, 2009.
[66] Jason Milionis, Alkis Kalavasis, Dimitris Fotakis, and Stratis loannidis. Differentially private regression with unbounded covariates. In International Conference on Artificial Intelligence and Statistics, pages 3242-3273. PMLR, 2022.
[67] Kentaro Minami, Hitomi Arai, Issei Sato, and Hiroshi Nakagawa. Differential privacy without sensitivity. Advances in Neural Information Processing Systems, pages 956 956-964, 2016.
[68] Darakhshan J Mir. Differential privacy: an exploration of the privacy-utility landscape. Rutgers The State University of New Jersey-New Brunswick, 2013.
[69] Erkki Oja. Simplified neuron model as a principal component analyzer. Journal of mathematical biology, 15(3):267-273, 1982.
[70] Phillippe Rigollet and Chrrihhittian Hütter. High dimensional statisties. Lecture notes for course 18S997, 8 813(814):44 2015.
13

---

[71] Or Sheffet. Old techniques in differentially private linear regression. In Algorithmic Learning Theory, pages 789-827. PMLR, 2019.
[72] Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. Pri- vacy loss in apple's implementation of differential privacy macos 10.12. arXiv preprint arXiv:1709.0275.. 2017.
[73] Joel Tropp.
User-friendly tail bounds for sums of random matrices. Foundations of computa- fional mathematics, 12(4):389 434, 2012.
[74] Christos Tzamos, Emmanouil- Eimaanoui-VVsiiliios Matakis-Gkaragkouue and Ilias Zadik. Optimal private median estimation under minimal distributional assumptions. Advances in Neural Information Processing Systems, 33:3301-3311, 2020.
[75] Prateek Varshney, Abhradeep Thakurta, and Prateek Jain. (nearly) optimal private linear regression via adaptive clipping. arXiv preprint arXiv:2207.04680 2022.
[76] Roman Vershynin. High--dimesiooal probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018.
[77] Duy Vu and Aleksandra Slavkovic. Differential privacy for clinical trial data: Preliminary evaluations. In 2009 IEEE International Conference on Data Mining Workshops, pages 138-143. IEEE, 2009.
[78] Vincent Vu and Jing Lei. Minimax rates of estimation for sparse pea in high dimensions. In Artificial intelligence and statistics, pages 1278-1286. PMLR, 2012.
[79] Martin J Wainwright. High-dimensional statistics: non-asymptotic viewpoint, volume 48.
Cambridge University Press, 2019.
[80] Di Wang, Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. International Conference on Machine Learning. pages
PMLR, 2020.
[81] Sen Wang and J Morris Chang. Differentially private principal component analysis horizontally partitioned data. In 2018 IEEE Conference on Dependable and Secure Computing (DSC), pages 1-8. IEEE, 2018
[82] Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. arXiv preprint arXiv:1833.0259 2018.
[83] Yu-Xiang Wang, Stephen Fienberg, and Alex Smola. Privacy for free: Posterior sampling and stochastic gradient monte carlo. In International Conference on Machine Learning, pages PMLR, 2015.
[84] Huan Xu, Constantine Caramanis, and Shie Mannor. Principal component analysis with contaminated data: The high dimensional case. arXiv preprint 1002.40002.400 2010.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes], see Section 7
(c) Did you discuss any potential negative societal impacts of your work? [N/A] Our work theoretical and does not have direct negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [N/A] We don't have experiments
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [N/A]
(c) Did you report error bars (e.g., with respect the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [N/A] We didn't use existing assets.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "_r08z6kju59", "reviewer": "Reviewer_2bGF", "summary": "The authors propose a Differentially Private PCA (DP-PCA) based on a minibatch GD method to overcome the limitations of existing approaches. Nearly optimal statistical error rates are provided. A lower bound shows that sub-Gaussian style assumption is necessary\nto obtain the optimal error rate.\n", "questions": "Can the authors locate their work in comparison of the works of . Imtiaz and. Sarwate published in 2018?", "limitations": "The authors have addressed adequately  the limitations of the proposed method.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1) The paper is well organized.\n2)  The proposed Private Oja’s Algorithm and DP-PCA are well explained and reproducible.\n\nWeaknesses:\n1) There are missing key references:\nH. Imtiaz, A. Sarwate, \"Differentially Private Distributed Principal Component Analysis\", IEEE International Conference on Acoustics, Speech and Signal Processing, ICASSP 2018, pages 2206-2210, 2018.\nH. Imtiaz, A. Sarwate, “Distributed Differentially-Private Algorithms for Matrix and Tensor Factorization” , IEEE Journal of Selected Topics in Signal Processing, December 2018.\nS. Wang, J. Chang, \"Differentially Private Principal Component Analysis Over Horizontally Partitioned Data\", IEEE Conference on Dependable and Secure Computing, DSC 2018, 2018.\nA. Gang, B. Xiang, W. Bajwa, “Distributed principal subspace analysis for partitioned big data: Algorithms, analysis, and implementation\", IEEE Transactions on Signal and Information Processing over Networks, Volume 7, pages 699–715, 2021.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VEqz6QKIykl", "reviewer": "Reviewer_YCMY", "summary": "Principal Component Analysis (PCA) is a fundamental statistical tool with multiple applications and differential privacy (DP) is a widely accepted mathematical notion of privacy. This paper presents a algorithm called DP-PCA and shows that it achieves an error bounded for sub-Gaussian-like data. ", "questions": "See below for the weakness", "limitations": "DP-PCA requires choices of the learning rates. I think authors should better explain their choice of learning rate.\n\nThere are no experiments to validate the effectiveness of the proposed methods in the current paper.\n", "rating": 7, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The authors make the Oja’s algorithm private and show that it achieves near-optimal error if the data is strictly from a Gaussian distribution. Then they overcame the two remaining challenges: (i) restricted range of \\epsilon=O(\\sqrt{log(n/\\delta)/n}); (ii) excessive noise for privacy. To overcome each challenge, it critically relies on two techniques: minibatch SGD and private mean estimation. The authors proposed DP-SGD based on the two ideas above. They use minibatch SGD of minibatch size B=O(n/log^{2}n) to allow for larger range of \\epsilon=O(1) and use Private Mean Estimation to add an appropriate level of noise chosen adaptively according to Private Eigenvalue Estimation.\nThis paper considers using private estimation within an optimization in DP-PCA setting while the idea has already been proposed in abstract settings. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RldcRcKcgyS", "reviewer": "Reviewer_24cL", "summary": "This paper studies principle component analysis (PCA) under differential privacy (DP) constraints. The authors improve the sample complexity from prior SOTA to a near-optimal rate by proposing a new single-pass algorithm. This algorithm is novel, and it is based on a minibatch SGD algorithm where each step contains a private top eigenvalue estimation and a private mean estimation. Although the authors have not shown any simulation or experiment for their algorithm, they provide both upper bounds and lower bounds under various assumptions with solid theoretical analysis.", "questions": "1. In Theorem 6.1, the rate on $B$ contains $d\\log(1/\\delta)$, but in Theorem 5.1, the rate on $n$, which I think should be almost the same as $B$ since $B=O(n/log^2 n)$ in Line 196, does not contain $d\\log(1/\\delta)$ as a whole term. Is there any typo?", "limitations": "The authors has discussed the limitation of their analysis and algorithm, e.g., Line 121-123, Line 235-244.", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Major strengths:\n\n1. The authors point out current issues for the existing results performing PCA with privacy constraint and use a totally different approach to tackle this problem. They identify the two challenges of the intuitive Private Oja’s Algorithm and solve them by two subalgorithms which perfectly match the need.\n2.  The authors provide both the upper bound and lower bound which vastly improves the understanding of the PCA problem under DP constraint. The analysis of the DP-PCA under Gaussian distributions shows that their algorithm is near-optimal.\n\nMinor strengths:\n\n1. This paper is well-written and greatly organized to help readers get familiar with the problem they are solving and the reason behind their solution. Section 6 is very helpful for understanding what is happening during the proof.\n2. The assumptions and the corresponding reasons are clearly provided.\n\nMajor weakness:\n\n1. I have checked most of the theorems with the proof in the appendix, and found all of them are solid and accurate, except for the lower bound, Theorem 5.3, which may invalidate the near-optimality: \n    1. In Section C.1, Line 635, the very last term in the equation is incorrect where from [3] Corollary 4, $\\frac{\\log(|V|)}{n\\phi\\varepsilon}$ should be $\\frac{|V|}{\\exp(10n\\phi\\varepsilon)}$; \n    2. In Line 640 Lemma C.3, the final part $c_1 d$ should contains $\\alpha$. \n    3. In Line 644, the usage of Lemma F.4 seems to have wrong constants. \n    4. In Line 647, the choice of $\\alpha$ depends on $d$ which is not permissible if we want to use Lemma C.3.  \n\nMinor weakness: \n\n1. This paper only considers PCA as computing the first principal component. The paper [23], which is the tightest result they have compared with in Line 115, can be used to compute the top $k$ principal components under DP constraint. Therefore, the description that the rate of DP-PCA is better than existing results is correct but may not be very fair. It would be better if the authors provide a discussion on how to use DP-PCA to find top $k$ principal components.\n2. Theorem 2.2 typo: $\\beta$ should be $\\xi$\n3. Line 178 typo, $x_i$ should be $s_i$", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HWBCtvlj7vo", "reviewer": "Reviewer_YYLJ", "summary": "This paper studies the PAC task under differential privacy guarantee and propose private algorithms which achieves the optimal sample complexity. ", "questions": "1. In Algorithm 3, why not apply subsampling in the input A_i but instead only implement on split data? Is is because it only concerns the asymptotic  properties and there does not matter if the mini-batch is n/log n for log n iterations? \n\n\n2. Can you further drop the Gaussian tail assumption (A4) but instead apply heavy-tailed mean estimation as Algorithm 5 to implement Algorithm 3? It seems that changes in A4 only produce a worse dependence on the variance of the data but some bound can still be derived though not necessarily optimal. \n\n3. Can the techniques to construct the lower bound be generalized to the case when only the second or fourth moment of  tail is assumed? I am curious for heavy-tailed data, can the author claim anything interesting on the utility bound? ", "limitations": "Please see above. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. This paper is well written and I enjoy the reading. The motivations for each proposed techniques and improvements, though simple, are clear.\n2. This paper shows DP PCA algorithm of an asymptotically optimal sample complexity. Concrete examples for the lower bound are presented, especially for the effect on concentration assumptions. \n\nWeakness:\nThere is some unclarity in the algorithm and proof. Please see below. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept