An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise
Authors: Johanna Düngler
Amartya Sanyal
Venue: NeurIPS 2025 poster ()
Keywords: Differential Privacy
Stochastic PCA
Adaptive Noise
Primary area: social_and_economic_aspects_of_machine_learning

Abstract: Given $n$ i.i.d.random matrices $A_i \in \mathbb{R}^{d \times d}$ that share common expectation $\Sigma$, the objective of Differentially Private Stochastic PCA is to identify a subspace of dimension $k$ that captures the largest variance directions of $\Sigma$, while preserving differential privacy (DP) of each individual $A_i$. Existing methods either (i) require the sample size $n$ to scale super-linearly with dimension $d$, even under Gaussian assumptions on the $A_i$, or (ii) introduce excessive noise for DP even when the intrinsic randomness within $A_i$ is small.~\citet{liu2022dp} addressed these issues for sub-Gaussian data but only for estimating the top eigenvector ($k=1$) using their algorithm DP-PCA. We propose the first algorithm capable of estimating the top $k$ eigenvectors for arbitrary $k \leq d$, whilst overcoming both limitations above. For $k=1$, our algorithm matches the utility guarantees of DP-PCA, achieving near-optimal statistical error even when $n = \tilde{O}(d)$. We further provide a lower bound for general $k > 1$, matching our upper bound up to a factor of $k$, and experimentally demonstrate the advantages of our algorithm over comparable baselines.

An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise
Johanna Düngler Department of Computer Science University of Copenhagen joduddi ku. dk
Amartya Sanyal Department of Computer Science University of Copenhagen amsa@di ku. dk
Abstract
Given n i.i.drrndom matrices A, Raxd that share common expectation Σ, the objective of Differentially Private Stochastic PCA is to identify subspace of dimension that captures the largest variance directions Σ, while preserving differential privacy (DP) of each individual AN. Existing methods either (i) require the sample size n to scale super-linearly with dimension d, even under Gaussian assumptions the A,, (ii) introduce excessive noise for DP even when the intrinsic randomness within A; is small. Liu et al.) 2022a addressed these issues for sub-Gaussian data but only for estimating the top eigenvector (k = using their algorithm DP-PCA. We propose the first algorithm capable of estimating the top k eigenvectors for arbitrary k S d, whilst overcoming both limitations above. For k = 1, our algorithm matches the utility guarantees of DP-PCA, achieving near-optimal statistical error even when n = (d). We further provide lower bound for general & >> matching our upper bound up to factor of k; and experimentally demonstrate the advantages of our algorithm over comparable baselines.
Introduction
Principal Component Analysis (PCA) is foundational statistical method widely utilized for dimen- sionality reduction, data visualisation, and noise filtering. Given n data points { classical PCA computes the top eigenvectors the empirical covariance matrix X == = - T E ddxd This problem of extracting the top k cigenvectors is commonly known as k-PCA. In this work. we consider the problem of Stochastic k-PCA, which differs from the standard setting as follows: instead of inputting single matrix, independently from distributions that share the same expectation Σ. Given this input, the goal of a Stochastic k-PCA algorithm is to approximate the dominant eigenvectors of Σ.
input stream of matrices Aj...., A, that sampled
Differential privacy (DP) Dwork et al. 2006) provides rigorous, quantifiable guarantees of individual data privacy and has been widely adopted in sensitive data contexts, such as census reporting Abowd et al. 2020) and large-scale commercial analytics (Apple 2017). Despite extensive study of differentially private PCA Blum et al.) 2005 Chaudhuri al., 2013] Hardt and Roth 2013 Dwork ct al. 2014b), existing methods in the stochastic setting suffer from sample complexity super-lines in inject noise at scale that ignores the underlying stochasticity in the data. When applied the stochastic setting, these works generally yield suboptimal error rates of O O(ydk//r //kk// (8/2k/(En)
where E is the DP parameter.
Example 1 (Spiked Covariance). In the spiked covariance model, observe i.i.d. matrices A, E R that contain both a deterministic (low-rank) signal and random noise, causing the A; to be full-rank. As a concrete illustration, consider data points I; 8; ni composed a signal 8t (in,((v with a unit vector and n4 ~ (0, Aa). Therefore A; == TıKt consists of
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

deterministic part ve" and noise terms that scale with o². One would hope that the privacy noise that needed, shrinks as the noise variance o² decreases. Instead, most differentially private PCA methods employ non-adaptive clipping thresholds, so their added privacy noise scales only with that threshold, resulting unnecessarily large privacy noise for many distributions.
Recent advances Li et al. [022a address these limitations for sub- Gaussian distributions, but only for the top cigenvector case (k 1). Cai et al. (2024) achieve optimal performance specifically for the k-dimensional spiked covariance model, yet their privacy guarantees only apply under distributional
assumptions the data.
Our Contributions. In this work, we propose k-DPP-PA, the first DP algorithm for stochastic PCA that simultaneously (1) achieves sample complexity as Liu et al.) al.) (2027y. (2) adapts is privacy noise to the data's 's inherent randomness, (3) generalizes seamlessly to any target dimension l S d, and (4) is simple to implement.
O(d) under similar assumptions
For k = 1, k-DP-PCA matches the risk Liu et al. [002aa] under sub-Gaussian assumptions. For
general k, we prove a nearly matching lower bound up linear factor in k. precisely characterising the cost of privacy in this general setting. Technically, we employ the deflation framework: iteratively
estimate the top eigenvector, project it out, and repeat. We extend the recent deflation analysis of
Jambulapati et al. (2024) to the stochastic setting via novel stochastic e-PCA oracle (Definition) 3
which may be of independent interest. We then adapt DP subroutines from Liu al. [2022a]
based on Oja's ss algorithm and finally, through a novel utility analysis of non-private Oja ' algorithm, demonstrate that the adapted subroutines satisfy the oracle's requirements, yielding a simple to implement, memory-efficient method.
The remainder of this paper is structured follows. We formally define setting in Section 2 state main results in Section 3 present technical analyses in Section 4 and empirical evaluations demonstrating the effectiveness of our approach in Section 5 Finally, we end with a discussion and open questions in Section and conclusion in Section
Problem formulation
Let AI...., An E Rddd be independent random matrices with common expectation > E3 [A.]. We assume > is symmetric positive semi-definite (PSD) with eigenvalues ' 2 X2 2 ... 2 d 2 0. For given & < d, assume the eigengap A > Au+1 > 0. The goal of Stochastic PCA is to produce a U E Rddk whose orthonormal columns approximate the top-k eigenspace of Σ. We measure the utility of U by comparing it to Vk, the matrix containing the true top k eigenvectors of Σ as columns. Throughout, I|-1/, denotes the operator norm, (..)) the Frobenius inner product: (A, B) = Tr (AT B), and 2 and O(-) hide polylogarithmic factors. Definition 1 (a-approximate Utility). We say U E Raxk is Ç-approximate if U has orthonormal columns and
( N 21 (3VV
E) E.).
Although several utility measures exist for PCA, our choice is motivated by the error measure used Jambuullaaa
in Jambulapati et al. (2024). This is natural measure of usefulness, much of the original "energy" of Σ is retained when projecting onto the lower-dimensional subspace Eckart-Young Young Theorem we know V2 is the optimal rank-k approximation
(UUT, Σ) quantifies how
spanned by U, and by the Eckart- of Σ.
Further, we use the add/remove model of differential privacy, namely
Definition (Differential Privacy (Dwork al. 2006 )). Given two multi-sets S and S', we say the pair (S, S') is neighboring if | \ SST+ 15" S < I. We say stochastic query g over dataset S satisfies (e, ddffferrretl privacy for some E and E (0, 1)
P(g(S) E A) < e P(g(S") A) +
for all neighboring (S, and all subsets A of the range of g.
Before discussing the main results of our work, we first formalize the assumptions on the data in Assumption A Note that Assumption A only required for our utility guarantee and is not necessary for the privacy guarantee.

---

Assumption A (CE, (.. M, K,,, ) Let E Rddd be sampled inde-
pendently from distributions satisfying:
A.1 B[A]] = Σ, where Σ is PSD with eigenvalues A1 2 ... Ao 2 0, corresponding eigenvectors 01.-..; 0 < A min As and n'
A A
A.2 ||A; 5:|| A M almost surely.
A.3 max {
E (A, -)
[ - APV.
A.4 For all unit vectors u, v and projection matrices P.
1 P(A; P[A:-2)PPff 1/20
E
exp
K22772
11.
Define H.,
1 X1
[( Eyuu" (A; E) and 722 = max =1 H 1|2.
Assumptions A. to A.3 are standard for matrix concentration (e.g., under the matrix Bernstein inequality (Tropp 2012 and thus also required for the utility guarantees of Oja's algorithm even in the non-private setting. Assumption A.4 guarantees that for any unit vectors u, v, and projection P
1u P(A, - Pu < k2
log? (1/0)
with probability 1 - 0, for some sufficiently large constant K. This bound, which controls the size of the bilinear form, can be seen as a Gaussian- tail bound, which tells us that the magnitude of the projection of the A, along any direction is bounded with high probability. It is an extension of the assumptions in [Liu et al. 2022a] to the higher dimensional case. Distributions that fulfill this assumption include bounded matrices and (abb-)gaussian outer product matrices:
Example (Gaussian Data, Remark 3.4 in Liu et al. (022a ) Let A, T with ~ NO, Σ). then comparing to Assumption we have that M Old (og()))) V Od)) 4, a 1, and
72 0(1)
Distributions that violate assumption include heavy-tailed outer products, for example r (a)eto ru, A, va. mixtures with rare but huge spikes:
Example 3. Let A, = Nt with be sampled follows:
N(0.Ia)
w.p.
Ji x Unif(a
w.p. a
where is unit vector and 0 < 1. Then the mean of this distribution is 0 and its covariance is = (1-00 LI + Varv" Sor
and P = Ta, if 11/4
(A. Eluu = v (I, - E) = (o (Txx) x2,)² T T.
Ev
=a v Eu a 1/2 (1 a) + Va 2
for a + this term blows up, so for any fixed K, A1 7y the overall expectation will exceed 1, and hence violate Assumption A.4
3
Main Results
In this section, we first discuss our main proposed algorithm in Section 3.1 In Section 3.2 we then discuss main upper bounds and complement that with lower bounds in Section 3.3
3.1 Our Algorithm
Our first proposed algorithm k-DP-PCA, defined in Algorithm I follows a classical deflation (Jam bulapati et al. 2024] approach. The algorithm proceeds rounds and in each of & rounds invokes the sub-routine MODIFIEDDP-PCE the algorithm removes contribution by projecting out the direction of the eigenvector from the remaining data (Line 4h, on which it carries out the next round.
(Line 3. to identify the current top eigenvector. Then,

---

Algorithm k-DP-PCA
Input: (A1,.... Anj. J. [d], privacy parameters (e, B Z4,, learning rates [/ and 7 TE (0, 1)
1: m t n/k, Po + Ia
2: for i E do
3:
+ NODDFEDD--PPAA((M-----
P.- (e,
4: P: P:-1 i
5: end for
6: return U t {us) [E((
The MODIFIEDDP-PCA subroutine (Algorithm 2 itself is based on Oja's streaming Algorithm Jain et al., 2016], but importantly replaces the vanilla gradient update in Oja's algorithm wt Wt-1 + - with a two-stage algorithm: first, Line 3 privately estimates the range of batch of (A,w-i), then Line 4 leverages that range calibrate the added noise privately compute the batch's mean. By tailoring the noise scale to the empirical spread of the data, we inject significantly less (privacy) noise whenever the batch concentrates tightly around its mean. Thanks to those additional steps the algorithm enjoys certain statistical benefits as discussed in the paragraph below Corollary 2
Nevertheless, is possible to replace the MODIFIEDDP-PP PCA subroutine with other simpler subrou- tines that can privately estimate the top eigenvector. We present such algorithm in Algorithm we present simulations with both of these algorithms highlighting their respective
In Section []] advantages.
Algorithm 2 ModificdDP-PCA
Input: {A,...., Am projection P, privacy parameters (e, 8), learning rates (n Z and r E 1)
1: Choose w/ uniformly at random from the unit sphere, wa +- Pu6//||uth
2: for ......., T [m/ B] do
Á + PRIVRANGE ((PA - || [B/2] (6/2,.622) (Algorithm) 6
3:
4:
0r + PRIVMEAN
AB( B/2 A ( (Algorithm
5:
w/ + Wi-1 + Pr.
6:
Wi Pw///l Pwill
7: end for
8: return wr
3.2 Upper Bound
We now the main privacy and utility guarantees of k-DP-PCA (Algorithm I Theorem 1 (Main Theorem). Let e, E (0,0.9) and 1 s k < d. Then k-DP-PCA satisfies the following:
Privacy: For any input sequence (A₃ E BRddd), ,, the algorithm is (c, -)dffferrenl private.
Utility: Suppose AI...., An are iid. satisfying Assumption (E, M, V, K, R', a, 72). If
A
with parameters
ex dk' (mm(1/8)
+R' R2 Va (1n(188))2/
n 2 C max
12
(1)
x2 k2 d (1(1/8)
for a sufficiently large constant C, then with probability at least 0.99, the output Raxk Sapprrxximate with

---

n' <<V (VV Vk
ydk log(1/00 Malkyloo1//00
en
where Õ()) hides factors polylogarithmic in n, d, 1/e, (n(1/)) and polynomial in K.
Remark. The proof of our main Theorem can be found in Appendix For k 1, Theorem Srceoremrecoveee recovers the bound of Liu et al. [2022a] for DP-PCA. Moreover, the linear dependence d in matches the lower bound in Liu et al. [2022a]. On the other hand, the additional linear factor in & may be an artifact of our analysis: if one could reuse samples across deflation steps, this factor could potentially be improved. Further, in Ç. the first term /Vk/n is the non non-private statistical error of PCA, while the second term Sydkky/n((1// (//))/))///// /(n) the cost of privacy. Lastly, the sample-size condition [T arises because (i) each batch must be large enough to accurately estimate the range in PRIVRANGE
Algorithm 2 and (ii) errors accumulate across the deflation steps (Line 4
As direct consequence of applying Theorem Examples T and Corollaries:
obtain the following
Corollary 1 (Upper bound, Gaussian distribution). Under the same setling as Theorem 7 let A; = s.a with 22 ~ (0, Σ). Then with high probability the output is Ç-approximate with
ç <=ō(m'
(
((V dk
dl (og(10))
where Ô.) hides hoga--looritmmiic in n, d, 1/e, and log(1
Corollary 2 (Upper bound, Spiked Covariance). If A; follows the spiked covariance model from Ex- ample 7 then V (()²d), 72 = o², and K = 1. Hence, with high probability the output is (-approximate with
(V dk 72
dk log(1/8)
Ō= a..
EN
Adaptive noise: Our algorithm's advantage is most pronounced when y and V grow with the data randomness, as in Corollary Since for = o (v ddk/n (dk (atl//(()))/(emm)) the approximation error decreases as the noise standard deviation a shrinks. Moreover, by comparison with Corollary this bound is tight up to factor of k.
3.3 Lower Bounds
In this section, we derive an information coimmattioonthortttie lower bound for differentially private PCA under our setting. Formal proofs can be found in Appendix [.I]] Recall that our utility metric Ç defined in Definition measures measures the relative loss in captured variance compared the optimal top-k subspace of Σ. By contrast, most classical lower bounds for PCA (e.g., Cai et al. 2024), Liu et al. (2022a))
quantify error in terms of the squared Frobenius norm | V&V V I These two measures fundamentally different: the ratio of captured variance directly reflects variance explained in Σ, whereas the Frobenius-norm loss measures subspace distance without respecting the eigenvalue gaps in Σ. To connect them, first establish:
Lemma 1 (Reduction to Frobenius norm). Let Σ be a PSD d x matrix with top-k eigenvectors
VR E Rdxk and eigenvalues \₁ ... 2 Xa Any U Rdxk that satisfies IUU V& 2 7
musl incur
7
22>
2 R DEE A
where Ae = Ao= A
Note that if all eigenvalues of Σ are equal, every subspace captures the same variance so ( = 0 for any estimate, yet two such subspaces can be far apart Frobenius norm. This gap sensitivity to eigengaps is precisely why our reduction from Frobenius error to Ç incurs a factor of Ag. With this reduction hand, we prove the spiked-covariance lower bound by invoking standard Frohenius-norm minimax rates CCa et al. 2024 for differentially private PCA in the spiked covariance model.
5

---

Corollary 3 (Lower bound, Spiked Covariance). Let the d x n data matrix X have i..d. columns sam- ples from distribution P (0, U AUT +2I,)== E o(). where P(), o²)
(O,
UAUT + oaI cλ Σ Åạ 2 ... < A I CAJ. Suppose I ćg expleE co(Ev nokk + dk)} for some small constants co. Co O. Then, there exists absolute constant > 0 such that
ovA + + (2, + +02) ) I
(V dk
dk
A1)
inf sup UEu, & 2)
E[[] 2 c1
Comparing to our upper bound (Corollary 2 we see matching dependence on d, n, and E, up to multiplicative factor of k V\ + o²_ and logg(/5)). The gap in le arises from our sequential deflation approach, which currently requires independent batches at each step. Reusing samples across rounds could remove this up to a V factor
Special case l: = 1. When k = 1, k-DP-PCA reduces exactly to MODIFIEDDP-PCA. Theorem guarantees that the sine of the angle between the privately estimated eigenvector of MODIFIEDDP- PCA and the true top eigenvector is small, which is equivalent to being close in the Frobenius norm. This matches the upper bound of Liu al. [2022a] and thus also the lower bound up to factor of (og(1/8) (restated in Theorem 11 in the Appendix).
Technical Results
We now sketch the proof of Theorem by first proving a more general "meta-theorem" that applies to any stochastic ePCA oracle (defined below in Definition 5). At high level, k-DP-PCA uses the classical deflation strategy: Extract the top eigenvector of the current residual using a 1-PCA subroutine. 2. Project this vector out of the data. 3. Repeat until k components are obtained. In Theorem [ we implement the 1-PCA step with MODIFIEDDP-PA. but the same proof carries through for any algorithm satisfying the following guarantee.
Definition 3 (stochastic ePCA oracle). An algorithm OePCA is a (-approximate 1-ePCA oracle the following holds. On independent inputs , An E Raxd with [[A.] = Σ E saxd for all i and any orthogonal projector P Rdxd, OePCA returns unit vector u E Im(P) such that, with high probability,
(wn PEP) 2 (v0 PEP)
where v the top eigenvector of the projected matrix PEP.
This notion was inspired by Jambulapati et al. [024], who analyzed deflation in the non-stochastic setting. Their results do not extend the stochastic setting that we explore here.
Theorem 2 (Meta Theorem). Let E E S and , An be n i.i.d. samples with E[A,] Σ.
Suppose we replace each 1-PCA step in BineBlo Algorithm By C-approximate stochastic ePCA oracle OIPCA. Then the deflation algorithm outputs U E Raxi satisfying
(UUT, Σ) (1-
Further, for any E > 0, E (0, if Oorca is e, 5-DP then the entire algorithm remains 5E,5)-DP Remark. This Theorem a consequence of the stochastic deflation method we prove in Appendix C and Parallel Composition (Lemma 15p.
One important thing would like to highlight in this section is that this proof strategy is not unique to MODIFIEDDP PCA. In fact, our novel analysis of non- non-private Oja's algorithm (Theorem 7 shows that Algorithm iis also stochastic ePCA oracle. We highlight the two results below.
Theorem 3. Given A An are i.i.d. and satisfy Assumption MODIFIEDDP-POL and DP- DP-Ojas
as defined Algorithms/ 2 and are stochastic ePCA oracles with ( = Ô K
V
yd log(1/11
and ( Ō (m0(m (VV
1iddll/llo (1/(1/))
respectively.
Reusing will allow us to all samples every round (instead of n n//k), however we will incur an additional Vee factor due to privacy composition, which is why it will only lead to total improvement of vi and not k.

---

Algorithm 3 DP-Ojas
Input: {A1..... Am). , projection P, privacy parameters (e, 0), learning rates (m))
Set DP noise multiplier: a C"
2: Set clipping threshold: / +- Cλ1 V log (nd/() +1)
3: Choose w/ uniformly random from the unit sphere, wo Put//IPwh
4: for == 1,2,.... m do
5: Sample
(O. Ia)
6: w/ W1-1 + n.P (Pipp(PA,PPr....... 28azz)
7: Wt Pw// Pwill
8: end for
9: return WT
where ct) min T=
Remark. In Appendix we establish that both MODIFIEDIP-PCAA and k-DP-Ojas are valid ePCA oracles, with each result stated and proved as a separate theorem.
Note that we cannot plug in the DP-PCA algorithm of Liu et al. 2022a in Theorem 2 since it only guarantees relative on E E|P]EE[P]:
(uu) T, E[P]EE[P]) 2 ()v (EPP)EE [[PE))())
rather than on PEP, and [[P] need not be projection matrix.
The proof of Theorem follows directly from the utility proof of MODIFIEDDP-PP PPC (Theorem 9)
and of DP-Ojas (Theorem I0.. Combining this with Theorem immediately gives us Theorem and the following Corollary
To proof the utility of MODIREDDP-PCA we proceed three steps: 1. Prove non-private Oja's algorithm is stochastic ePCA oracle via Novel analysis in Appendix 2 Show that with high probability, the update step (Line (5) in Algorithm can be reduced to an update step non-private Oja's algorithm with matrices PC,P, where C, B Exe( A; B,G, and G, is scaled Gaussian matrix. 3. Bound the accumulated projection error across deflation steps (Lemma 23). Importantly, similar argument also shows that DP-Ojas Algorithm satisfies the same property with a slightly differently Ç.
Corollary (K-DP-Ojas). Under Assumption A if n. is sufficiently large then using Algorithm each 1-PCA step returns U E Baak that is Ç approximate with
A A
Vk +
(7+ + 1)ck log(1 (1/))
Ç Ō=
En
hiding poly-logarithmic factors in n, d, In(18)) and polynomial factors in K.
Remark. This Corollary follows directly from Theorem 2 together with Theorem
When comparing the utility bounds of MODIFIDDDP-ED PCC and k-DP-Ojas the difference partic- ularly apparent when considering Example I as for k-DP-Ojas when a - 0 the bound becomes Ô dk (1g()/)) as due to the second term the utility bound containing the multiplicative factor of (++1) 1) (as opposed 7 as MODIFIEDD
does not vanish. Therefore in the low-noise cases will outperform k-DP-Ojas. However, for other cases such as (sub-)Gaussian data we expect them to perform similarly. In those cases can be preferential use k-DP-Ojas as due to its simplicity it requires less hyperparamters to be set and is more stable to changes in learning rates.
MODIFIEDDP-PCE
Experiments
In our experiments, we compare k-DP-PCA and k-DP-Ojas against two modified versions of the DP- Gauss algorithms Dwork et al. (2014b) and a modified version the noisy power method (Hardt and Price 2014). All of these works operate in deterministic setting, and require some form of norm
7

---

Algorithm
K-DP-PCA
DP-Gauss-2
DP-Gauss-1
DP-Power-Method
1.0
1.0
1.0
<aapprox
0.5
0.5
0.5
0.0
0.0
0.0
x 10
10*
x 104
3 x 10 10a 3
10
100
200 dimension
sample size n
sample size
(a) σ = 0.025
(b) σ 0.001
(c) growing dimension
Figure 1: Comparison of K-DP-PCA vs DP-Gauss-1 (input perturbation), DP-Gauss-2 (output perturbation). and Pir-Power-Methhn on the spiked covariance model. We plot the mean over 50 trials, with shaded regions
representing 95% confidence intervals. We set h = 2, d = 200, A = 10, E 1, and 5 = 0.01.
bound on the matrices to ensure differential privacy. Dwork et al. [2014b] requires each row of the data matrix X Rn to be bounded in 42-norm by and they then estimate the top eigenvectors of XTX. The original noisy power method given matrix A E Rdxd allowed only single entry changes
by at most 11, however more recent analysis [Nicolas et al. 2024 Florina Balcan et al. 2016) showed
that it protects the privacy for changes of the form A' A + C, with VE II S 1. By contrast, our setting is stochastic: we draw independent matrices A4, without any norm constraint, and we estimate the top eigenvectors of TE [A] = Σ. Thus, we first adapt these algorithms to also guarantee privacy in setting. Note that if we draw observations n; from a distribution with mean serves as an unbiased estimate of nε. A naive way
zero and covariance Σ, then X x -"= z.r, to enforce the bounded norm requirement of Dwork al. (011b),, is to define .. zz/ max { [|a. However, this non-private pre-processing step will violate privacy (Hu et al. 2024]: modifying a single x; can potentially change the maximum norm and thus affect all of the Iy. A natural next attempt is to scale each vector exactly to unit norm, i.e., म. = >./1|==/12. However, this will result in a biased estimator as E [xx" //|l==11 |2] * Σ and thus does not enjoy meaningful utility guarantees. Instead, we clip each 2; at 3 so that with probability at least 1 - 0,s ||>i||2 S B. Then scaling the Gaussian noise in the DP-Gauss mechanisms by 3 maintains (s, -DP guarantee. For the spiked covariance model this would mean Algorithm 1 and in Dwork et al. (b114) and refer to them as DP-Gauss-1 and DP-Gauss-2 respectively. DP-Gauss-1 first clips each x4, adds appropriately scaled Gaussian noise to the sum E, प. and then performs standard (non-private) PCA. DP-Gauss-2, on the other hand, begins by privately estimating the eigengap of the clipped covariance matrix, runs non-private PCA on the clipped data, and finally perturbs the resulting top-k eigenvectors with noise that scales with that that privately computed eigengap. Similarly to what we do for the DP-Gauss algorithms, to enforce the condition V | 17 < 1 by Nicolas et al. [2024] we define A' A aa" meaning C' aa" T, then the ith row of equal to |a; ||a||| 11, which results in the requirement ||a|||||||| - 1. So we clip the matrices to ||a||] < and ||a|| S 3 (same /3 as for DP-Gauss) and scale the privacy noise accordingly. For the spiked covariance model we choose a = od + vdid /d log(n/U)) to achieve | I a with probability 1 - 9. This makes their algorithm comparable to DP-Gauss in terms of utility guarantees with respect to k and d. However, we will see, it is still outperformed by the DP-Gauss algorithms. In the rest of this section, Figure [ compares k-DP-PCA with DP DP-Gauss-L DP- Pa-sssss 22 and DP-Power -eeerr-ettie Mho across various noise levels and dimensions d. Figure alsoo incorporates the much simpler-to to- --implemennt k-DP-Ojas algorithm and shows that a simpler, more scalable algorithm can match even outperform k-DP-PCA in practice, despite its slightly weaker theoretical guarantee.
CV²i + / /dggon////// 8). Using this strategy we modify
Experimental Results using Spiked Covariance Data We evaluate all methods on the spiked- I [b] utility as a function of sample size for large and small noise levels, respectively. Our results show that across both regimes, K-DP-PCA consistently outperforms the baselines, with the gap widening when the noise level is significantly smaller than the signal strength (o < A1). Figure Ic examines the effect of increasing ambient dimension d at fixed n. As d grows, the DP- methods and SreverrMehho'ss utility degrades faster than k-DP-PCA 's, reflecting the fact that their theoretical utility scales like (d3/2 /n), whereas guarantee only incurs linear dependence on d.
covariance model(see Example []. Figures La and
8

---

Algorithm
K-DP-PCA
DP-Gauss-2
DP-Gauss-1
DP-Power-Method
K-DP-Ojas
1.0
1.0
<aapprox
0.5
0.5
0.5
0.0
0.0
0.0
0
50
100
10
10
10
x 10
104
3 10
Ak
Ax
sample size n
(a) Increasing eigengap
(b) Varying noise level
(c) 0.025
Figure 2: Comparison of K-DP-PCA and k-DP-Ojas in a higher noise regime (also including OP-Gauss-1 (input perturbation), DP-Gauss 2 (object perturbation), and DP- P--er--eetheeee plot the mean over 50 trials, with shaded regions representing 95% confidence intervals. We 2, d 200, A1 = 10, = 1, and 0.01.
the spiked covariance model. We
we plot the utility against the eigengap (Aş )k+1) for different algo- rithms. Ga-ssuss22, 2, which is designed with large eigen-gape in mind steadily improves in utility as the gap grows and nearly matches the utility of k-DP-PCA for very large eigengap. By contrast, DP-Gauss-1 1 which offers better scalability with dimension d but is insensitive to the eigen-gap, main- tains a nearly flat utility as the eigen-gap grows. Throughout, k-DP-PCA consistently outperforms both DP-Gauss algorithms.
In Figure
Za
Next, in Figure 2 we compare k-DP-PCA against the much simpler k-DP-Ojas algorithm. As predicted by Corollaries and k-DP-PCA clearly outperforms k-DP-Ojas in the low-noise regime (a & A1). Conversely, at larger noise levels k-DP-Ojas often matches or even exceeds k-DP-PCA in practice, owing to its fewer hyperparameters and greater robustness to learning- rrat choices (see Figure 26n appendix G). Although both algorithms require knowledge of the eigenvalues of Σ to set optimal step sizes, these can be obtained privately via the Gaussian mechanism. Nevertheless, is interesting to note that k-DP-Ojas remains effective even when its step size chosen without any explicit eigenvalue estimates (see Appendix G). Lastly, we want to note that in Appendix G we present more comprehensive results, using different d and k. The results this section are kept simple for illustrative purposes.
6 Related Work and Open problems
Related Work Differentially private PCA has been studied extensively [Blum al. 2005 Chaudhuri et al. 2013 Hardt and Roth, 2013 Dwork et al. [2014b. However, when applied to the stochastic setting, these methods typically ly suffer from sample complexity that scales super-linearly in inject noise at a scale that ignores the underlying stochasticity in the data, resulting in suboptimal error rates of O dk/nn  + (8/2k/(sn)) The first to address these limitations were [Liu et al. 2022b Cai al. 2024]: however the results by [Liu et al.) [022bb only apply for
and Cai al. 2024
provide an algorithm whose privacy guarantee is conditional on distributional assumptions on the data. In contrast, our algorithm applies all < d. is private for all inputs, provides an error rate that scales linearly with d, and the injected noise scales with the inherent stochasticity in the data.
A complimentary line of work, (Singhal and Steinke 2021 Tsfadia 2024 obtains sample com- plexity that scales independently of the dimension d but requires a strong multiplicative eigengap (Ae/ (Ae/A++1) (V7),, which a strictly stronger assumption than ours.
Open Problems Despite being a mild concentration requirement also seen in prior work [Liu et al. 2022a], Assumption A.4 is perhaps the most non-standard assumption in Assumption A As observed by Liu et al. 2022a this can be relaxed to a bounded k-th moment condition, at which point the second term in (2.3) grows to (d 1/0)/en) 1-1/k). Further, empirical improvements may also be possible from applying private robust mean estimation [Liu et al., 2021 Hopkins et al., 20022, as opposed to clipping around the mean of the gradients. Lastly, the current PRIVR ANGE is optimal for spiked covariance data, however for other data distributions we expect different range estimators to
work better. We leave this to future work.

---

The sample size condition in Equation ( includes an exponential dependence on the spectral gap: 2 exp(k'). While this is relatively harmless as there is no such exponential dependence in the utility guarantee Equation ( we show in Appendix F.2 how to get rid of this exponential dependence
by incurring an additional O(yd (og(1/6)/(en))) term in the utility guarantee.
As already mentioned in Section 3.3, our upper bounds are loose in their dependence in At and 6. We incur this additional k factor, because each deflation step must use a fresh batch of samples, so that the projection matrices P remain independent of the data matrices in Line 4 of Algorithm [ If one could safely reuse the same A, across rounds, this could be improved to O(Vk) via adaptive composition. We think it interesting future work to see whether we can obtain a vk factor using the techniques from the robust PCA results in Jambulapati et al. [2024) or using our analysis but with "slightly" correlated data. However, even if one theses approaches turn out to be viable, a gap still remains between the resulting upper bound and our lower bound and it is an interesting question to resolve this. Finally, although inspired by the streaming analysis of Oja's method [Jain al.. 2016 Huang et al. [202]], our subroutines (MODIFIEDDP PCA, PRIVR RANGE, PRIV FRIV) are not directly streaming- compatible. Adapting them to the streaming setting is an interesting avenue for future work.
7 Conclusion
We have presented the first algorithm for stochastic k-PCA that is both differentially private and computationally efficient, supports any k S d, and achieves near-optimal error. Our analysis critically relies on our adaptation of the DP-PCA algorithm [Liu et al. 2022a]. a stochastic deflation framework inspired by (Jambulapati et al., 2024), and our novel analysis of non-private Oja's 's algorithm (Jinn et al. 2016). Along with our novel results in the Stochastic k-PCA problem, we believe the above mentioned theoretical results are of independent interest, and may inspire the developement of new algorithms for this and related problems.
Acknowledgement
JD acknowledges support from the Danish Data Science Academy, which is funded by the Novo Nordisk Foundation (NNF2ISA0069429) and VILLUM FONDEN (40516). AS acknowledges the Novo Nordisk Foundation for support via the Startup grant (NNF240C00878220 and VILLUM FONDEN via the Young Investigator program (72069). The authors would also like to thank Rasmus Pagh for very insightful discussions.
References
John M Abowd, Gary L Benedetto, Simson L Garfinkel, Scot A Dahl, Aref N Dajani, Matthew Graham, Michael B Hawes, Vishesh Karwa, Daniel Kifer, Hang Kim, et al. The modernization of statistical disclosure limitation at the us census bureau. URL: bit. lyDPccnsus20, 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Lazysvd: Even faster svd decomposition yet without agonizing pain. Neural Information Processing Systems (NeurIPS), 2016.
Differential Privacy Team Apple. Learning with privacy at scale, 2017. machinelearning, apple. wwt.eeecoooeeeeeeeeee wwweeeeaarchleearnnngg wwth- at- scale
https://
Raef Bassily, Adam Smith, and Abhradeep Thakurta. Private empirical risk minimization: Efficient algorithms and tight error bounds. In Foundations of Computational Science (FOCS), 2014.
Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Guha Thakurta. Private stochastic convex optimization with optimal rates. Neural Information Processing Systems (NeurIPS), 2019.
Sourav Biswas, Yihe Dong, Gautam Kamath, and Jonathan Ullman. Coinpress: Practical private mean and covariance estimation. Neural Information Processing Systems (NeurIPS), 2020.
Avrim Blum, Cynthia Dwork, Frank McSherry, and Kobbi Nissim. Practical privacy: the sulq framework. In Principles of Database Systems (PODS), 2005.
10

---

Mark Bun and Thomas Steinke. Average-case averages: Private algorithms for smooth sensitivity and mean estimation. Neural Information Processing Systems (NeurIPS), 2019.
Tony Cai, Dong Xia, and Mengyue Zha, Optimal differentially private pea and estimation for spiked covariance matrices. wrXiv:2401.03820 2024.
Kamalika Chaudhuri, Anand D Sarwate, and Kaushik Sinha. A near-optimal algorithm for differentially-privalll principal components. Journal of Machine Learning Research, 2013.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography (TCC), 2006.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014a.
Cynthia Dwork, Kunal Talwar, Abhradeep Thakurta, and Li Zhang. Analyze gauss: optimal bounds for 2014b.
principal component analysis. In Symposium on Theory of Computing (STOC),
Vitaly Feldman and Thomas Steinke. Calibrating noise to variance in adaptive data analysis. In Conference on Algorithmic Learning Theory (ALT), 2018.
Vitaly Feldman, Tomer Koren, and Kunal Talwar. Private stochastic convex optimization: optimal rates in linear time. In Symposium Theory of Computing (STOC), 2020.
Maria Florina Balcan, Simon S Du, Yining Wang, and Adams Wei Yu. An improved gap-dependency analysis of the noisy power method. In Conference on Algorithmic Learning Theory (ALT), 2016.
Moritz Hardt and Eric Price. The noisy power method: A meta algorithm with applications. Neural Information Processing Systems (NeurIPS). 2014.
Moritz Hardt and Aaron Roth. Beyond worst-case analysis in private singular vector computation. In Symposium on Theory of Computing (STOC), 2013.
Samuel B Hopkins, Gautam Kamath, and Mahbod Majid. Efficient mean estimation with pure differential privacy via a sum-of-squares exponential mechanism. In Symposium on Theory of Computing (STOC), 2022.
Roger A. Horn and Charles R. Johnson. Matrix Analysis. Cambridge University Press, 2012.
Lijie Hu, Shuo Ni, Hanshen Xiao, and Di Wang. High dimensional differentially private stochastic optimization with heavy-tailed data. In Principles of Database Systems (PODS), 2022.
Yaxi Hu, Amartya Sanyal, and Bernhard Schölkopf. Provable privacy with non-private pre-processing.
In International Conference on Learning Representations (ICLR), 2024.
De Huang, Jonathan Wiles-Weed: and Rachel Ward. Streaming k-pea: Efficient guarantees for oja's algorithm, beyond rank-one updates. In Conference on Algorithmic Learning Theory (ALT), 2021.
Prateek 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 Algorithmic Learning Theory (ALT), 2016.
Arun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia, and Kevin Tian. Black-box k-to-1-pea reductions: Theory and applications. arXiv:2403.03900, 2024.
Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International Conference on Learning Representations (ICLR), 2015.
Gautam Kamath, Jerry Li, Vikrant Singhal, and Jonathan Ullman. Privately learning high-dimensional distributions. In Conference on Algorithmic Learning Theory (ALT), 2019.
Gautam Kamath, Xingtu Liu, and Huanyu Zhang. Improved rates for differentially private stochastic convex optimization with heavy-tailed data. In International Conference on Learning Representa- tions (ICLR), 2022.

---

Michael Kapralov and Kunal Talwar. On differentially private low rank approximation. In Symposium on Discrete Algorithms, 2013.
Vishesh Karwa and Salil Vadhan. Finite sample differentially private confidence intervals. In Innovations in Theoretical Computer Science Conference, 2017.
Pravesh Kothari, Pasin Manurangsi, and Ameya Velingker. Private robust estimation by stabilizing convex relaxations. In Conference on Algorithmic Learning Theory (ALT), 2022.
Janardhan Kulkarni, Yin Tat Lee, and Daogao Liu, Private non-smooth empirical risk minimization and stochastic convex optimization in subquadratic steps. In Neural Information Processing Systems (NeurIPS), 2021.
Xiyang Liu, Weihao Kong, Sham Kakade, and Sewoong Oh. Robust and differentially private mean estimation. Neural Information Processing Systems (NeurIPS), 2021.
Xiyang Liu, Weihao Kong, Prateek Jain, and Sewoong Oh. Dp-pea: Statistically optimal and differentially private pea. In Neural Information Processing Systems (NeurIPS), 2022a.
Xiyang Liu, Weihao Kong, and Sewoong Oh. Differential privacy and robust statisties in high dimensions. In Conference on Algorithmic Learning Theory (ALT), 2022b.
Lester Mackey. Deflation methods for sparse pea. Neural Information Processing Systems (NeurIPS), 2008.
Julien Nicolas, César Sabater, Mohamed Maouche, Sonia Ben Mokhtar, and Mark Coates. Differen- tially private and decentralized randomized power method. (xXi:2441.01931/ 2024.
Erkki Oja. Simplified neuron model as principal component analyzer. Journal of Mathematical Biology, 1982.
Vikrant Singhal and Thomas Steinke. Privately learning subspaces. Neural Information Processing Systems (NeurIPS), 2021.
Joel Tropp. User-friendly tail bounds for sums of random matrices. Foundations of Computational Mathematics (FoCM), 2012.
Eliad Tsfadia. On differentially private subspace estimation in a distribution setting. In Neural Information Processing Systems (NeurIPS), 2024.
Christos Tzamos, Emmanouil- Vasileios Vlatakis Saaaaki-Garrakouniii. and Ilias Zadik. Optimal private
median estimation under minimal distributional assumptions. Neural Information Processing Systems (NeurIPS), 2020.
Di Wang, Hanshen Xiao, Srinivas Devadas, and Jinhui Xu. On differentially private stochastic convex optimization with heavy-tailed data. In International Conference Learning Represenia- tions (ICLR), 2020.
12

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Yes. Our main contributions are also detailed in Section contains the relevant mathematical proofs.
3 and Appendix
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
Justification:
Yes, see Section 6 for limitations. We also comment on the limitations of the
different algorithms Section
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g.. independence assumptions, noiseless settings, model sellsspeciiiationn asymptotic approximations only holding locally). ). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g. if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-tex, system might not be used reliably to provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
13

---

Answer: [Yes]
Justification: Yes, please see Appendix for a detailed proof of the Main Theorem, and Appendix [ Appendix [ for the more general novel results we developed in order proof the Main Theorem. Lastly in Appendix we proof the lower bound.
Guidelines:
The answer NA means that the paper does not include theoretical results,
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We describe our algorithm in Detail in Section 3 and state all the hyperparame- ters used for the plots in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
14

---

reproducible, they 5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [N]
Justification:
We will release the code publically after we have cleaned it.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.co co/
public/guides
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7/nips cc/ wtc/publiic/ subbbic/guides gwt.///ieeee/eee// Codeeoobiiieeeee dusee/uuuude/oo SanSSuubissss iolbbmmsssioo ssionnoiccyy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: detailed discussion can be found in Appendix G Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We ran a minimum of 50 trials for each experiment and included the variance of results in the plots.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
15

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma enror bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
All experiments were run locally on a MacBook M3 Pro.
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We followed the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work mainly a theory result. The numerical experiments were run on synthetic data and are therefore not related to any private or personal data, and there's no explicit negative social impacts.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
16

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
We do not foresee any high risk for misuse of this work.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
17

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification:
We have not released any new assets as part of this work.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
18

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: The core method development in this research does not involve LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.LM policy for what should or should not be described.
19

---

Appendix
The appendix is structured as follows. In Appendix A we provide a more detailed overview of related work to complement the discussion in the main text. Appendix [B introduces mathematical and privacy- related preliminaries that lay the groundwork for our analysis. In Appendices C and D we present novel technical contributions: in C we extend the recent deflation analysis of Jambulapati
Can
[2024]
to the stochastic setting and also prove Theorem 2 in the main text, and in D we provide new utility
analysis of the non-private Oja's 's algorithm. These results are then used to prove our main theorem
and establish the utility and privacy guarantees for our second proposed algorithm (Corollary 4..
k-DP-Ojee Ojas, in Appendix[E [E] In Appendix[[] we prove our lower bound result from Section 3.3 We then provide additional experimental details in Appendix G and conclude by restating the subroutines from Liu et al. 2022b), which are used in MODIFTEDDP-PCA Appendix H
A Related Work
The problem of private k-PCA has been the subject of extensive research, with many works exploring it under various constraints. Several works address k-PCA in the standard setting, while assuming
an additive eigengap [Blum et al.
2005 Chaudhuri et al., 2013 Hardt and Roth 2013 Dwork
These works operate in a deterministic setting where each sample is assumed to be bounded (I|=;|l < B). When applied to the stochastic setting, these
2014b, Nicolas et al. [0044]
works generally yield suboptimal error rates. This is partially due to the fact that all of these works assume a data independent bound (3 = 1), which we cannot easily enforce in the stochastic setting (as discussed in Section 5). Considering Gaussian data with x, (O, Σ), we know
||=||| < 3 = ((vAid log(n/() for all i with probability 1 - [Blum et al. 2005 Dwork et al. 2014b Nicolas et al. 2024] use the Gaussian mechanism, when scaling the privacy noise with
factor 3 we ensure (E, dD-DP in the stochastic setting. The tightest of the previous discussed result then achieves
o (Vak/a + @/2k/(en))-
More recent work has considered the multiplicative eigengap setting [sfadia 2024 Singhal and Steinke| 202T]. though this is a strictly stronger assumption. Finally, there is a set of results without spectral gap assumptions [Chaudhuri However, these works either do not allow a tractable implementation or give utility bounds that are super-linear in their dependence on d.
al. 2013 Kapralov and Talwar 2013 Liu et al. [0022b).
widely used strategy in the non-private PCA literature to mitigate the complexity of designing algo- rithms for &-PCA is to reduce the k-dimensional problem to series of 1 1-dimensional problems using a technique known as the deflation method [Mackey] 2008 Allen- Zhu and Li 2016). Jambulapati et al. [2024] proved significantly sharper bounds the degradation of the approximation parameter of deflation methods for k-PCA. While their analysis only catered to the standard non-stochastic setting and assumed access to the true covariance matrix Σ, their results serve conceptual foundation for this work. We extend similar arguments to the stochastic setting, where only access to sample matrices A; with shared expectation E [A,] = Σ is available.
Our 1-PCA method builds upon Oja's algorithm [Oja] 1982], (see Algorithm 5 one of the oldest and most popular algorithms for streaming PCA. The first formal utility guarantees for Oja's algorithm in the in Appendix Subsequent extensions to the k >> 1 case were provided by Huang et al. 202
case were established by Jain et al.] (0166), whose analysis inspired our proofs
Lastly, our ePCA oracle MODIFIEDDP-PEO PCA is largely inspired by the DP-PCA algorithm of Liu et al.
[2022b]. Their result builds upon a series of advances in private SGD [Kamath et al. 2022 Bassily
et 20144 2019 Feldman al., 2020 Kulkarni et al.] [202]] Wang et al. [020 Hu et al. [022]]
and private mean estimation |Bun and Steinke| 2019 Karwa and Vadhan |017] Kamath et al. 2019
Biswas et al. 2020 Feldman and Steinke, 2018 Tzamos et al. [2020]. J. In this work, we use some
of the techniques proposed by Liu et al. [022b specifically their PRIVMEAN and PRIVRANGE
algorithms. Replacing them with robust and private mean estimation [Liu et al. 2021 Kothari et al.
2022 could relax Assumption A.4 but at the cost of sub-optimal sample complexity.
20

---

B Preliminaries
In this section we list some mathematical and privacy preliminaries. A familiar reader is welcome to skip this section.
B.1
Mathematics Preliminaries
Lemma 2. Let C,DC E Rdxd be symmetric matrices and let A E R.mdd be any conformable matrix. Then C D ACA ADA
Proof. Since C < D, we have C- 3 0. For any x E R set = A x. Then
(C x AAC A) y Dly S..
which shows ACA ADA
Theorem (Woodbury matrix identity). Let A E Rax and C E bx be invertible matrices, and let U E Bank V RRxx Then
(A+UCV)) = -A- - A A- + UV-
Theorem 5 (Pinsker's Inequality). For P and Q two probability distributions measurable space then
TV(P.Q) S V -K((PII)
Lemma (Lemma F.2 in [Liu et al. 2022al). Ler G Ruix be a random matrix whose entries Gs3 are ii.d. (N,, 1). Then there exists universal constant C > 0 such that for all t > 0,
Pr
GGl|2 & C(Va+ 2 21-28 2e
Lemma 4 (Lemma F.5 in least -
Liu et al. 2022a ). Under Assumptions
A.1 1o
A.3
with probability at
1 B
1 - =
Σ SE[B]
V log (2/+)
M log (d/r)
B
Lemma (Adapted Version of Lemma F.3 [Liu et al. 2022al).
Rdxd be a random matrix
where each entry Gig is i..dd sampled from standard Gaussian N(0, 1). Then we have
E[[|GT [|a] S Cd
(4)
Proof.
E|||G [1a] s B|
P(I u)du / P([|G]|2 > vuddu
G[|2 > r)2rdr
where we do the change of variable with == Vu, y2 du 2rdr. Next we split the integral into two parts using the "concentration radius" ro = C1 Civd. as by Lemma the exists a universal constant C1 > 0 such that
P[|| 2 CilVa
+((V++))) 8)) S >
this gives us
/ 00
B BI|
[2] =
P([ > r)2rdr +
P[[|G]]2 > 2)dr
Pro
< Jo
2rdr +
P(I >r)>>)2000 2r
Ccd+
P([|G]]2 > r)2rdr
21

---

for the second integral we use again Lemma 3 or rather its equivalent form
P[||)) r) S -V=
which gives us
P( r))rdr
- -Va) 2rdr
Ci(Vd+ s)e 3)e-dd ds
cRva
/ c ds + 09 / se
ds
SC2VD+
where we used r C1(v s) and dr Cids in the second step, which finishes our proof.
Lemma (Weyl's inequality (Horn and Johnson, 2012 ) Let G1 and G2 be symmetric matrices with eigenvalues μl 2 2 pa and 1/1 2 ... 2 Va respectively, then
1/ - 14 Σ |G1 G2ll2
Lemma (Conditional Markov Inequality). Let F be a sigma-algebre let X a non negative random variable, and let > O. Then
F
P(X 2 aF) <
Proof. Define the indicator
1, X
[[x2a] (0, o.w..
Then X, [x 2 (x22))
Taking conditional expectation given F on both sides yields
E
F 2 E [a
[ a Pr (X 2 F).
X
F
Hence, Pr(X 2 F
Lemma 8 (Conditional Chebyshev's Inequality). Let F be conditioning event (or sigma-algebra). then for a > 0
Var[X[F
P - E 2 &
a²
where Var[X|F]= [B[ -
Proof.
P(IX E| 2 aFF) P(( - P(X7)) > a²IF)
(X- RK-BU E( is non negative random variable, so use conditional Markov (Lemma) 7b. which gives us
E - E
- P((X-E[X
2
d²
22

---

Lemma 9 (Distributional Equivalence). Let 2 ~ (0, be a d-dimensional Gaussian with covariance > O. Let P E Raxd be an orthogonal projection matrix, and fix any unit vector Im (P). Then there exists random matrix G = Y, where each entry in Y Rd is sampled i...d. from N (0, 1), such that
Pz PGPw.
Proof. Since ~ N(0, Σ) and P is a projection matrix, we have Cov (P2) PEP = PEP. On the other hand, let G = Σ y2y. Then for any fixed E Im (P) with ||||| = 1,
Cov (Gw) = Cov (Yw) =
because Yw N (0, Ta) by rotational invariance of spherical gaussian (and |||||| 1). Hence Cov (PGPw) PEP = Cov (Pz). Since both Pz and PGPw are mean-zero Gaussians with the same covariance, we have
Pz _ PGPw.
Lemma 10. For any matrix A Bddd and any projection matrix P.
|PAPll 2 S ||
Proof. For any unit vector || = |IP S ||Px|| < Px < ||A
where the last inequality follows as projection matrices have eigenvalues in {0, 13. Taking ths supremum over all x completes the proof.
Lemma 11. Let A E I be random matrix and P a random projection mutrix, independent of A. Then
[PAPAA < |BJA
Proof. We first show that for any orthogonal projection P. we have PAPA PAAT P. Since and p2 P. Consider the difference:
P is an orthogonal projection,
PAA PAPA P PA(T)A P
Using the identity I = + (I P), the expression becomes
PA(P + - P)ATP- PAPA PA(I- PAT
where the last step follows as I - P is also an orthogonal projection. This implies
PAPA P.A
Taking expectation (over both P and A) then yields
E [[PAPATP] E [PAA P].
(5)
As P independent of A, one has
EP.A [PAA] P] Ep [EA [PAA
Pi] Ep [PEA [AA P] Ep [PMP]
where M : EA [AAT] Combining with previous step, get
EpA [PAPA EEp (PMP]
(6)
Finally, we show
| [PMP]]2 ||M
Indeed, for any fixed projection P, the largest eigenvalue of PMP P can be written
Amax (PMP) = max T (PMP)*= max (Px)" M (Px).
=||==
23

---

Since || < whenever | = 1, it follows
(Px) M ((x))
max y T My ||M I
Taking the maximum over all | = shows IPMPI: 3 || Hence Ep [IIPM < ||
Because the operator norm || convex,
[Bp [PMP]]2 Ep PI || 1l2
which is Equation
Now combine Equations 66 and have
|| [PAPAA p]ll2 s [Ep & [| - || [AA [Al
This completes the proof.
Lemma 12. Let A and be independent random matrices in Rdxd Then
[ABA']] = |E [BI12 E [AAT]
Proof. Since A and B are independent, we have E [ABAA]] = E [[AE[B]AT] Then, using E B = | [B]] Ia and Lemma we obtain the wished inequality.
Lemma 13. Fix any projection matrix Raldd Define, for each unit vector R
--= = (PEP) E. [P(A, Σ) Puu T [| 7
max H 2
||||=1
where a1 and y are defined in Assumption and Xद (PEP) refers the top eigenvalue of PEP. Then
(PEP) < x11²
Proof.
| (TAA,-))Puii' T P(A,- E] || = ||Ep [PE[(A; - Pu) P(A: - [) I
< Ep |||||| - Pum T P(A, - 2) P|I
Ep
[|E[(A, Pu P 2) PI|]
and further
max [IE[(A) Puu P(A: - -EJPP11 < max [B[(A,- LlAA-Maau E'uu [(4 (A: - 21| = X²? |||||=
|+||=1
Puu T 3 u... So, all together this proves the Lemma.
Definition 4. Define Og, denote the
& matrices satisfying U I
Remark. The Frobenius norm is equal to the Schatten-2 norm.
Lemma 14 (Lemma Jambulapati et al. 2024 E E gdxd k E [d]. If E Rdxd
rank-(d k) orthogonal projection matrix, then PEP12 2 1x)
B.2 Differential Privacy Preliminaries
Lemma 15 (Parallel composition, (Dwork et al. 2014a]). Suppose have K interactive queries ......, чK, each acting on a disjoint subset Sy of the database, and each query qk individually satisfies ()D on its subset Sy. Then the joint mechanism (q1 (S1),, (e()))..... (Sx(Sk) is also (c, DD...
Lemma 16 (Advanced Composition, Kairouzz et 2015)). Let S 0.9 and 0 8 < Suppose database is accessed k times, each time using e/(2 24 log log 5/(k)) -DP mechanism.
Then the overall procedure satisfies (s, DD-.
24

---

Algorithm 4 BlackBoxPCA(((1)) k, OIPCa) (Jambulapati et al. 2024
Input: n. i..d. matrices AI...., An E IRdxd with B[A.] = E 0, target rank k E {l,.... d], and OIPCA stochastic 1-ePCA oracle which, inputs a batch of samples Anr...., Ag and an orthogonal projector P, and returns a unit vector u E [m(P).
1: Po < Ia
2: - n/k
3: for i = 1,2, ..... do
4:
Draw the next batch ((1-))B+1,.... A:B).
5: Uj < OIPCA 1)++1. ABB: P;-1)
6:
P. 4,u4
7:
end for
8:
return U (us
C Meta Algorithm for stochastic k-PCA
In this section we prove that any stochastic 1-ePCA oracle, when passed into Algorithm 4 yields valid k-PCA algorithm. This is the basis for Theorem our argument applies to any randomized stochastic 1-ePCA oracle (not necessarily private). particular, it generalizes the utility analysis Jamuulaaaat et al. [0024] to the stochastic setting where each call to the oracle sees only fresh batch of i.i.d. matrices A,, and must approximate the top eigenvector [[[A]] = Σ.
Definition 5 (stochastic ePCA oracle). An algorithm OePCA a (-approximate 1-ePCA oracle the following holds. On independent inputs ..,....44 E Raxd with E[A,] Σ E sixd for all and any orthogonal projector P E Rdxd, O&PCA returns a unit vector u. E Im(P) such that, with high probability,
(wu' PEP) 2 (1 -
where u the top eigenvector of the projected matrix PEP.
Remark. The DP-PCA algorithm in Liu al. (022al) ) does directly qualify as stochastic 2 (1 (²) (ve' E[P]EE[P]). rather than
1-ePCA oracle, since it guarantees (uu" comparing to PEP itself. It is not obvious in general how large E[P]EE[P] PEP can be.
We will now show that for this type of approximation algorithm we can obtain a utility guarantee and recall the energy formulation of
that it would be optimal for the spiked covariance setting. We approximate k-PCA from Jambulapati et al. [2024), which is the utility metric we will use here.
Definition 6 (energy k-PCA, (Jambulapati et al. 2024)). ). Let M sdxd. A matrix U E Bgdk with
orthonormal columns is (-approximate energy k- PCA of M if
(UUT, M) 2 (1 (1-<3) (2) ||
where
|| (xy =
max VER A
Tr (VVVTTM)
V=I
The following lemma relates the angle between two unit vectors to the corresponding energy in Σ.
Lemma 17. Let u, w E Idd be unit vectors, let 0 be the angle between them, and let Σ 2 0 be any PSD matrix with top-eigenvector Then
(ww)) T Σ) 2 (1- sin)(0)) (ve Σ)
Proof. Observe
(ww T. ,E) = = -vv ww , =(1- (voT wro _) (v) Σ)
(v)TE)
(8)
25

---

Note that since is the top eigenvector of Σ, we have
(uv - Tr (vv T - Ev A1
where A1 2 ... 2 Xd denote the cigenvalues of Σ and v, U......, the corresponding eigenvectors. Then, we can rewrite
(1 1 (ve) ww T, 22
= - (1- w Ew
w DU T w
d X T
u503 w
=
(av) Σ)
A1
A1
A1
2
d
Xj fw. u32
1 -
(w, b)²
Σ
X
j=2
2 1
(w, u) = (1 - sin (0))
Substituting this back Equation gives us
ww ) 2 - (i)) (ve 2))
and completes the proof.
We now prove that, if each OIPCA call in Algorithm 4 approximates the top cigenvector of P. P:-1L:;:1. then the final U is a (-approximate energy of
Theorem 6 (Reduction from k-PCA to 1-ePCA). Let A,,...,A, be i.i.d. samples Raxd with E[A,] = Σ = O. Fix Ç E (0, 1)- Suppose OPPAA is a (-approximate stochastic 1-ePCA oracle as defined in Definition []] we run Algorithm with OIPCA, then (with high probability) output
= = satisfies
(UUT T د. 2 (1 (2)-
Proof. Define U, == [i....,, Us
E Rdxi We claim by induction on that
Tr (U, =
Σ u Eu 2 (1- --) (1 j=1
Base case (i = 1) Since Po = Ia, by definition of the oracle, the first call returns U, satisfying
Tr (U, uu Eui (nrny 2n) 2 (1 (2) Amax (2) (1- (201())))
Inductive step. Suppose after i steps, Tr EU;) 2 (1 (²) | [=))
(1)- Let P. = Ia - U, U.T Then, by definition of the oracle, the (i + 1)-th call returns u;-1 E Im (P:) such that
IN++IUTT P.EP.) (² |P.EEPI12
Since (u:41uTH1 Σ) 2 (u.41u,,1 P.EPP), it follows
u 4 Eu441 (M14iu P.E.)) 21 2 ||EEP111
By Lemma in Jambulapati et al. Hence,
2024 (restated Lemma 14p. we know |.P.E.P112 2 A441
Tr (U, EU+1
Tr (U, + 4 Eu+t1
2 (1 (?) |5 + (1 (?) |PPEEPIl2
2 (1 (2) 13 (1 (2) A (2)
(1 (²) [|](())))
completing the induction.
Therefore, after l steps, (UUT, .) Tr(U Tr(UTEU) > (1- - (2) [5l
26

---

Algorithm 5 Oja's Algorithm
Input: { [=rr learning rates (m)
Choose wy uniformly random from the unit sphere.
2: for I,..., do
3: w/ + W1-1 +/
T/. W
4: 1 w//ll///l
5: end for
6: return
Theorem 2 (Meta Theorem). Let E E Sgod and A1,..., A, be n ii.d samples with [[A,] E. Suppose we replace each 1-PCA step in Bi Algorithm by a (-approximate stochastic ePCA oracle OIPCA- Then the deflation algorithm oulputs U E Raxe satisfying
(UU Σ) (1-
Further, for any > 0,8 (0.1), if OLPCA is E, E-P then the entire algorithm remains (E,8)-DP.
Proof. Apply Theorem obtain the utility guarantee, and invoke Lemma 15 to conclude privacy under parallel composition.
D Novel Analysis of non private Oja's Algorithm
Throughout this appendix, condition a fixed projection matrix P. All probability statements refer to randomness over the i..d. samples {A:]. with P held fixed. Whenever we write "with probability at least - 8", it means Pr(- PP)
6. At the end, we apply a union bound to obtain
an unconditional failure probability S 6.
Let Aj...., A, be i.i.d. in Rddd with E[A,] = E. Denote the eigenvalues of E with A 2 A2 2
... 2 Aa and corresponding eigenvectors v1, Ga. Let be a projection independent of (A.)==1 Our goal is to approximate the top eigenvector of PEP.
When P is deterministic, Jain al. [016] shows that Oja's algorithm outputs vector close the top cigenvector of PEP. However, in our setting P itself is random. where P is defined as Σ; Uy u,!" where each u, is computed using a prior independent sample of {At]. We cannot directly apply their result, since it would only guarantee closeness to the top eigenvector of E[P]EE[P], and [P] is generally not projection matrix and may not preserve the spectral structure of interest.
P = -
To address this, analyze Oja's algorithm inputs (PA,P) and our main theorem shows that, under suitable conditions. the output is still an accurate approximation to the top eigenvector of PEP, even though P is random and data-dependent. From here on, we write d₁ 2 X2 2 ... 2 da to denote the cigenvalues of PEP, and denote top eigenvector.
Assume scalars M, satisfy
|| Ell < M
(9)
(A. - (A: (A Σ) " | [A., T (Ai Σ) s
max
(10)
Remark. We intentionally different notations M, V here instead of M, V than in Assumption to simplify the expressions. Here M = M and V XPV under Assumption A
A
Next, define
B, (I+ Th ThP P) n -
(I+PPAP)
(11)
BR
Wn = |B
(12)
(13)
where d/ refers the learning rate of Oja's Algorithm at step i, which in turn means w,, is the output of Oja's Algorithm after steps given (PA, P) as input. We defined the variables like this order to apply the following Lemma from Jain al. 2016) to prove convergence of
27

---

Lemma 18 (One Step Power Method Jain et al. 2016)). Let B E B let v E B be a unit vector, and let V1 be matrix whose columns form an orthonormal basis of the subspace orthogonal to v. is sampled uniformly on the unit sphere then, with probability at least 5,
Bw
)
log (1/0) TI (V VL
sin?
=1
(w)) <C
(14)
BB
where C is an absolute constant.
Now we are ready to state the main theorem of this section.
Theorem (Main theorem of this section). Fix any and set 1)t (>1->a)(3+4)) for a > 1/2. and define
3 =0 max
MMa Ma (hi->a)' (21-
Va
( log
1+
100
Suppose the number of iterations n of Algorithm 5 given inputs {PA,P) satisfies
3. Then, with probability least 1 the output wh
C'log(1/8)
2a
a²
(w
82
(2a 1)(21 x2)
Here C is an absolute numerical constant. Remark. Based on Lemma 18 to show Oja's algorithm (Algorithm 5) succeeds for our inputs we simply need that with high probability Tr V B,B V1) is relatively large and J_ B, 7 is relatively small, so that their ratio is large. Where i refers to the top eigenvector of PEP and V, is matrix whose columns form an orthonormal basis of the subspace orthogonal to As long as we pick y Algorithm sufficiently small, i.e. Th = O(1/ max M, Åτ) then I 77. PAP, is invertible, so turn B, B which guarantees TT B, B, 0 > O, so the RHS of the inequality will always be finite. In order to explicitly bound the RHS we will utilize conditional Chebychev's 's and Markov's, where the conditioning will serve fix P.
Proof of Theorem 7 The proof is analogous to Theorem 4.1 in Jain et al. 2016). except we replace their Theorem 3.1 by our Theorem stated and proved below.
Theorem 8. Given AI....,A, An that fulfill Assumptiios A. with parameters E.M. V, projection matrix P independent of the Ag, i the top eigenvector of PEP. P, and B, as in Equation (T]. the output wn resulting from non- non-private Oja's 's Algorithm (Algorithmm) 5 inputs P PAPP.... P.A satisfies
sin i,
Br |Butinllg
1
exp
Σ
5n3 v j=1
dexp -2((xr -51)))))
Σ m
s
where Q Clo((1/8)
(1-
1
vall V exp
EE 181 11)
By Lemma 18 applied after replacing B with Ba, with ē, and Vi spanning T-t, we have with probability at least 6
Proof of Theorem 8
Brw
C Jog (1/8) TI (V. B1
sin²
(15)
5T B,
It now remains upper bound the numerator Tr (VI B, B, V1) and lower bound the denomina-
tor 0 B, B, e separately.
(i) Lower Bound the denominator Using Conditional Chebychev's inequality (Lemma
we have
P
6
B B,
B, P]
Var BB,
0 P] < 5.
(16)
28

---

Expand the variance expression as
E
(iB,, 8) 2
VVa Var i P = E BBB PIVA-1
where A
E
Br δ P]
Then, rewrite Equation 16 to
1 (1-
(I-VV--1))
P
1
P]
<6
(17)
V8
Now, we need to bound the conditional expectation term and A. Using Lemma 20 conditional expectation by
we bound the
B
B
P 2 exp
Σ 2m 11/ 21283)
(18)
Then, using both Lemmas 20 and 21 we bound
A
E
BB
P
n1
A
S exp Σ th
(100+ (10V+833)
S exp
Σ
18n8(
(19)
E
B₁
B
Plugging Equations
18
and 19
into Equation
bounds the denominator
ū 2 exp Σ 2m an2xt)
P
B,B,
<.
(20)
where
8
C log (1/8)
vō
exp
18nf
-1
(ii) Upper Bound the numerator Using Conditional Markov's inequality (Lemmal 7
we have
V Br
BT
Pr Tr [.
P
(21)
8
Using Lemma 22 we can bound the conditional expectation as
Tr
B B V1
p]
s exp
Σ
2n d2
d V
Σ
th exp
Σ jE[A
2n
(Nr
-1-)))
jEl()
dexp
Σ JELL
21l 2n
n
(iii) Applying Union Bound Using the above bounds, by applying union bound over both the numerator and the denominator we have with probability - 28, conditioned on P
Tr VI B, B.
<
Qdexp
Σ JEJN
2nd (īe X1) + (V + 4x7)
T. B,
Substituting this into Equation
15 completes the proof.

---

D.1
Supporting Lemmas
We now state and prove several lemmas that together with Lemma will allow us to prove Theorem which in turn yields Theorem 7
The terms M. V. V, BB, wn are defined in Equations 9 to 13 Further d1 2 2 2 ... 2..2 Xa denote the eigenvalues of PEP, and ö to denotes its top eigenvector.
Lemma 19. E [ l|l|2 - exp(ZiE(1) 2n + n (A1 + V))
Proof. We
denote at
| [B Pi]l2
where
B.
IPP.P (I+ T (I+ P...).
E B T P| = E (I B. (1+ P
1 2 E (I+ TH (I P]]
(by Lemma T2
0t-1 E P P PAPAPA PI
= -
(I+ 2m
2mp PEP + /p PPAPAA
We bound PEP 3 AI Further,
E PPA.PA P Pl PEPEP + E. P Σ) P(A - -E) P P]
PEPEP + PE (A, - -5) (A. -E) Pl
3 x [A, - (A. -2)) -E) Pl
X [A. Σ) (A. - 1
= X + + I,
where the third step follows as assumption on the A,. Hence,
||||| I 1, the 4th as P is independent of A, and the last step by
at S at-1 (1+ 2m + ne (22 (2++)))
With og = 1 and + S e²
Σ
2nrdr + (5i + v))
at S exp
iE(1]
Lemma 20. E BBB
P 2 exp
[Eeetg] (2n:d= - 4nイx²)
Proof. Let 8, = E [ B,B,T. 0 P]. where é is the top eigenvector of PEP with eigenvalue X Since B, = (I + PPPPP) B. and A, is independent of B given P,
Be E [B. BT P] E (I [I+ (.+m)AP 00 T (I (1 PPPP)) |P|)
For the right hand side,
E [I mh M.P.PP Tū (I (PP.P) |P]
To + +TPPPPs T0 n:bē PEP
+ E गह PA P]
2 5τ T + 21 Tū_
because PEP 8 A10. Hence B 2 (1 2np28a) Be-1. With So= 11013 and 1 2
exp (x 1-2 2²) for x 2
3, 2 exp Σ
22::21 -41
30

---

Lemma 21.
( B, P] - exp E Am +10m
Proof. We define is- == B((ū We, W P) where W = (I + m.P.P)) ... (I
7t-++1 AA-A++1 P). So by this definition we see Wt, = B₁ and "/t = E((ō) B,B, 8) As exploit the eyclie permutation properties of the trace: 7t- TT 2, 00 We, W Wt,)P))
the trace of scalar is the scalar itself,
= -T + A GI 4
1 8i o "1,, Wi,-1- We first bound for arbitrary Gt-1 G. and then take the where Gt-1 == -
expectation over only A₁ and finally over Gt-1-
P[E[(I+7]] |AA0::CH-APAAAAaH-H-/PPPPPAPPP10
-Tr(G") 3XCC)--HH|II11222100m////pAAAAA2
+ +=/10C/AAA/22AAA//33///AuAAAAAa PG)P)
+ W PGPA)PIPI) PGPAP)))))
Tn) PGPA PGPA
// THEEA PGPA PGPAPA PGPAPPI))
Let's begin with the first order term:
Tr(PEPG*) < ||EPP| = TT
then let's consider:
TIEE PIPIG* & ( P(A Pill + ||PSPEP)))T()*>> (V+ X2))T(G?) (V+X)))))))
where the last inequality follows by Lemma Next we have 4 remaining second order terms:
I[EEPA -Tr PGPA] PGPPT
=I(E[GPA//GPPPP))) ([EGGPA
BBIIPAT PG] + +|PPAP
S S *
Third order terms can bound as follows:
P[E[PA]]GP.A PGPA PGPPAPA < |PA] P|IKEBPA
s (M+ (M+ +
Finally the fourth order term
Tr[E[PA] PGP P PGPA.PPPP)))))) < PITATAAATPPTTTTTTTTCTTPAAAAAAAAT
XI
all of this together gives
Tr(E((I PTTE[II PAAAAAAA-PPPPPPPPPPPPPEP PA +
<Tr(G9) +
4AAM {.)(TH(G)) + +M (
4 A PD
<(1 41 10n
E + 10n
where we used < M and exp(x). All of this give
t < exp(4m + 10n VE exp(4m) + 10n
then using 70 = 1 gives the wished result.
31

---

Lemma 22.
E
Tr(V] B, exp Σ
20, 20 22 + nイ²
d+ Σ
v exp
Σ 2013 EE(1
(21
x22
iE
Proof. Let or = IP Th VI B, V1) pl
By cyclicity of trace and V1 being fixed under
E
PI.
EB [B. [P] VIVI)
-B [B[B.-BBB]] Pl. E (I m PA (A,P) |p])
For the right-hand matrix,
V. VI + +PPP VI + nh V Vi PEP + 7H PA.P PAPIP
1 (1 + 2m + n VIV. + n T00
using V1 orthogonal to the top eigenvector ē of PEP, and V1 VI 3 I. Therefore,
ao 5 [1+ 22 + v/ a=1 + niv E B B, P] 607)
Using 1 ++x S exp (x) and (X, T0 S |||||
at exp 22 + m//)) 1:1 + n | [B-1B B P]ll2
1-1
S exp 2222a + n a--1 + n exp
Σ
(2n:dr + n2:D)
by Lemma 19 Unrolling the recursion,
ag cxp
Σ (2nrde + n1/D)
ao Σ
nF exp
Σ 2n d1 + 015)) exp Σ
(2ngde + t3/b)
Σ 2n (51 -Xo) )
exp
(2 + n1?1)
a +
V exp
Since 0g =Tr Tr (VTVI) = 1d11 d, the claim follows.
E
Proof of Main Theorem
Theorem 1 (Main Theorem). Let e (0,0.9) and s k d. Then k-DP-PCA satisfies the following:
Privacy: For any input sequence {Ai E Raddd, the algorithm is (c, ddifferrrrel private.
Utility: Suppose AI....,A An are iidd satisfying Assumption (,, M. V, K, K', a, 72). If
with parameters
dx' 7 1n(1/8)
+ + RPV Va (In(1/8))33
E X 2 V,
n 2 C max
(1)
1222 222 d (1(8)
32

---

for sufficiently large constant C, then with probability at least 0.99, the output U E Raxk is S-approximate with
Ç= n' (VVVV
Vk
ydk log(1/6)
En
where O() hides factors polylogarithmic in n, d, 1//ein(11/11111 and polynomial in K.
Proof of Theorem 7 The privacy proof of Algorithm| [ follows straight away from using Advanced Composition (Lemma 16 together with the privacy of MODIFEEDD-PPCA, which in turn follows we know that when passing
by [Liu et al. 2022a] For the utility proof we note that by Theorem 9 n/ matrices A; at every step of our deflation method obtain vector u, fulfilling
(PEPP
Vk y /log/1)((1/))) (V
sin 0;) 5
A1(PP)) (PEP)
EN
where vs the top eigenvector of P.-1E.:-I. Which by Lemma 17 give us
(u,u, P 2 (7) (1au Pa- PP-1EP,-1) 7dk (og(1/1)) ))
with C Ō
(PEP)
Vk VVy
By our choice of n we know by
on
Lemma 23 that
À
Vk
yek log(1/0)
A
n
en
where we used that (A 8)6 is maximized by 8 = A/2. So finally Theorem 6 gives that
(UUT, 2 2 (1 (V&V 2)
(22)
where Vi is the matrix obtained by non private k-PCA.
For the above utility proof could not apply DP-PCA straight away, this would only give guarantee that the vector e we obtain is good approximation of the top eigenvector of E| P This is not sufficient for the deflation method, We show that for MODIFIEDDP-PCA this is indeed the case Theorem 9.. We proof Theorem 9 by first showing that with high likelihood can reduce the update step Oja's Algorithm with matrices PC,P. We then apply a novel result we establish in Appendix D which shows that the non-private Oja's algorithm, when produces a good approximation of the top eigenvector of PE[CC, P. under certain assumptions on the sequence {Ct). Lastly, we need control the eгrоr we accumulate through approximate projections
require 7 to be good approximation of PEP.
update step of non private
the projected matrices (PC, P Jt.
P. 1-=1->; u,u,. which we do in Lemma
Theorem (MODIFIEDDP-POG PCA). L (0, 0.9). then
For any input sequence (A, E [Rdxd] and projection matrix P independent of the {Ai} the algorithm is (e, diifferrretti private.
Privacy:
Utility: Suppose Au.....A An are i...d satisfying Assumption Assumption A.4 with parameters (E, M, V, K, K. K',a,"'" 72,)),
du (r'r(log11/6))1 + +WM 2V +
112 (log(1/6)))7)
n C
E
for a large enough constant C, where K²' ((PPE))-x(PPSPP) 8 < 1/n and
(x)
0 < (PEP) - Xp(EP)
33

---

then there exists learning rate that depends on (t. M. K, (1 (PEP)
22(PEP): de, such that T n/ BJ steps of ModifiedDP- with choices of 0.01 and B = cin/(lgnn) n) output wr that with probability 0.99 fulfills
(VV
nd loglog((1/))
sin(wr, 8) S 10
(23)
en
where ō is the top eigenvector of PEP and Ô(-) hides poly-logarithmic factors in n, d, 1/e, and (16(1/6) and polynomial factors in K.
Remark. For readability we omitted the advanced composition details. If we choose T = Ollognn)
log (m))og(2/66)), (/(())6/222 (ogg in every step and then by advanced composition we get. And in our utility guarantee we would only oceur additional log" (n) factors which we omit. We also want to comment on why the utility bound only depends on P in the parameter x': We can see the the utility bound of MODIFIEDDP-PG depends on several constants originating from constraints on the data:
we can simply set (s',8) (2/ 2
K Ā1-A2
2. M so that |IA,, E112 - M almost surely
3. V so that max || [| (A; 23) Il1.lll,111 |EE( (A )}][ S vlV
4. ? = max Huule
[AT )1/22)) } X
5. so that max
exp
now if we replace (A.). the input to MODIFIEDDP-PG PCA, with (PA,P} (which is exactly what happens at iteration of Algorithm I where P is projection matrix, the constants M, V. Xpy and K will still remain upper bounds (see Lemma 10
Lemma Lemma 13
Proof. We choose the batch size B = (n/ (onnlog²// n) such that we access the dataset only T Ollgg n)) times. Hence we do not need to rely on amplification by shuffling. To add Gaussian noise that scales the standard deviation of the gradients in each minibatch (as opposed potentially excessively large mean of the gradients). DP-PCA first gets a private and accurate estimate of the range. Using this estimate PRIV MEAN returns an unbiased estimate the empirical mean of the gradients, as long as no truncation has been applied. As we choose the truncation threshold so that with high probability there will be no truncation the update step will look as follows:
w w/ + The P(
Σ
PA, + Be2+)
B
1E[
where ~ (0, I) and B: 8K 2A, log" (Bd/r) 2211o
The privacy follows by the privacy of the subroutines private eigenvalue and private mean estimation [Liu al. 2022a]. So all that is left to do is show the utility guarantee. We will do that by showing we can reduce it the accuracy of the non private case. First note that p22 so we get
EB
w = w + mee
Σ +
sin[23]
Using rotation invariance of the spherical Gaussian random vectors and the fact that ||w,-1|| and wi-1 E Im(P) (for details see Lemma 9
we can reformulate it as
w/ -- Wi-1 +
Σ
PA.P+3.PCE Wi-1
B
*E[M]
we can further pull out the projection matrices to obtain
w/ t Wi-1 + mpP
Σ
A + B,G,
Pwi-1
B
[E[
34

---

Where G' is matrix whose entries are i..d. (N0, 1) distributed. So we have matrix
1 Σ C. = B *E[
A + B.G
and we will now proof that C₁ fulfills all requirements for Theorem 7 (our version of the non private Oja's Algorithm utility guarantee), which will directly give us the wished utility guarantee. It is easy to see that E[C,] = Σ as 2 is a zero mean random variable and hence so is G.. Next we show the
upper bound of max { (C, [), - Σ) = E [C,
(C, - Σ)
E [G-
- [) (G--))
E
Σ
A + B.Gr E x
A, B.G. E
-E)
B
B
iE[B]
(
1
E
1
Σ
A
- E 2
+ |
B
B
iE[B]
VX
+ o | [G,
V\ B + C2d= V
where the first inequality holds due to Ge being independent to A, and [[ = 0. The second inequality follows due to having B elements of 1 E (A, - Σ) (A, Σ) 2
and Assumption 3.
And the last inequality holds with high probability due to G, having i.i.d. Gaussian entries (Lemma and by choosing
B 16Kr>1 log (Bd//)) / 2d log (2.5/6)
eB
we have 3 2 Be for all i as by Theorem 6.1 in [Lu et al. 2022a and Assumption 4
À S 22
Hull2 S V2Air
Lastly let us consider |C₁ - El[2. By Lemma all / E [T]
3 and Lemma 4 we know with proabability - T for
||C El12
Σ
A; B.G - E
B
(E[
MX log (TTT+)
VX log (1T/T)
3 (Vd+ vlog (7/r))
A
B
B
so by Theorem with stepsize Mi
(Ar (21-12)(+0) after T steps with
(i (v+ X7) a²
Ma
T > 20 max
=
(24)
(Å1-
(7n X2) log (1+ 150
with probability 1-
Colog(188) 8²
$ d
2a
a²v
sinn(wr; 0) s
+
T
(2a
1)(11 X222TT
so if we fill in M, V. and 3 into & and use
BT get
Ay M (dT/// (A1 A2)n
VloggaT/T
Nia
Ky log (nd/I'r T / log (2.5/6) /lols//////////////// /Tg(TT/dda
E = 20 max
(A -xa
en( (1(A
T
Vxia²
3² log (dd (2556)
m(A - )2)a log(1 1
cAn - d2)
Aogg( log(1+ (1+)))))
-A1 lo 1
35

---

in order for Theorem to hold we need to force E/T S 1. Noting 7 0(1), K = O(1) and selecting a clog n. T c' (I) we get that
log( log(()))()))))))))))))g)))))))
(dg((n)
A
2A log/ log())) (10)11/5) log(log(n) log(n)d
$ T
20C max
(A: (A)=
a(A1
V VAl(logn)
m(A: - + 2 log" ( log(n)) (1 cAn An)²
Af n)²
(A) -aa-27
< 1 will be trivially fulfilled if each of the summand is smaller than 1/3. For the last term
need
Af(log n)²
1 1/3
(25)
(A1 22)
as T = c'(log(n)) this means
A1
log 12 2 3
(y1 X2)
for the remaining terms need
7>1 v log(1/00))))) 1/8)d
log" (n/ log n) log(n)
s(11 -22)
V1
nh
3
(log(n))2
(Λ1 - 22)²
v3 Vlog(d)
log(log(n))
3 \ log(d)
log(n) log(log(n))
(λ1 x2)
We note that to obtain n/log(n) 2 a, aog((a) + a log (a). So
M\1
V\
y7 v log(1/0)
C exp(Af/(Ar - (2)3) (A1
+
Ax)
(A: x2)x
(λ1 -x2)E
with large enough constant suffices (where 2 is hiding log terms) obtain E/T S and d(E/T)22 < 1/n2. And we get
V
VVP +
R2d log((/0)
I C"
(λ: X2)
En
(where S is hiding log terms), so plugging this in our bound for sin(wr, 8) we get
sin (WT, 8) S Ô n' (V yd rdg/lo((1/))
which finishes the proof.
Lemma 23, If we are given matrices {Ai E [dxd]nn
li=1 1 fulfiling Assumption with parameters
(E, M, V, K, k a, 72), fixed k I d, 0 < A minje([]] d A1+1 where X, refers the ith eigenvalue of E, 5 so that 0 < 5 < A, and sufficiently large constant C > so that
(A 6)8
Bujk <
Ck
then
\ & S
Balk
where
7d log(11) 1/5)
B, =
and & refers to the utility of the vector u, returned iteration i [k] of Algorithm) 1
36

---

Proof. We will denote
(P(--11)P))) Ki = (PP--1EPP-1) - PPP--1
Then by Theorem 9 we obtain
& S Ki Bn
Lemma 25 will give utility bound independent of P for k = 2, as it bounds Kg. However, want to obtain a utility guarantee for arbitrary & < d, so the goal is to upper bound K2 for general If we iteratively apply Lemma
25 we get
x + E A
K4 S
{(E)) - Aet1 (E) 2 2 Aj
where A, EX (Ao 0 for completeness). Now the problem is that A still
depends on previous projections and it's not even clear in general if & > Ey+1 or the other way around. Ultimately we want to have upper bound for all E,, to get utility bound for U {wz). A natural approach is to try and choose big enough so that
( & A (PEP)) 2
(26)
(27)
for some > O. If we achieve this we are done, as this will guarantee that
E Bn
We will proof that at every step Equation (6) and Equation 27 are fulfilled by induction. For k = 1 we have Po which straightaway gives us equation 26 And ō is smaller then the minium
eigengap equation 27 directly follows as well. For k + we start with showing equation 26 By
Lemma 24
(P.EP)) S (Z) +
first let's upper bound Σ/= Ay. By definition have
A, c. \1(P)-1
for some constant c. By induction assumption this gives us:
EPP;;-EPP3-.)
Σ j=1
A
B.
X1 X1 - (e(P)-12PP)11)
k
x;
S cB
Σ
8
j=1
so equation 26 will be implied by
5
B S (A1 )4+1)
ck.23
which is surely fulfilled as by assumption
8A-
Bn 5
cki2
To show equation 27 we see that
(P.EP)) - -(PEE)) 2 \x+1(E) - (6+2(E)
- -2
-2I4) A
1=1
& A A
Σ
A
j=1
37

---

where the first inequality follows by Lemma 25 and the second by definition of A == minse[A] A
A Using the upper bound on Σ5 1-1 A we established before we obtain
(P.EEP)) (e(PEP)))) 2 A 2c KB
6
so if we choose
- 8)6
Bn S
ck
this shows equation 27 will be fulfilled.
We need Lemma 23 as the utility result for MODIFIEDDP-PON -P-C depends on the eigenvalues of the input. After the first step of k-DP-PCA our input is of the form PA,, P..... P.,,P, so utility )2(PEP) can be arbitrarily sufficient utility bound as to
bound depends on the eigenvalues of PEP. In general λ (PEP) much smaller than the actual eigengap of Σ, and therefore it proof Theorem However, as we iteratively apply projection matrices of the form
P I wu
where u is unit vector, and further is c-close to the top eigenvector of the matrix we apply it to, we can actually relate the eigengap of PEP to the one of Σ using Weyl's Theorem.
Lemma 24. Given (0) < &, where 0 refers to the angle between U1 the top eigenvector of Σ (psd), and the unit vector u, then we have
A 2 A4+1 - A
A S A111 +
where X; is the ith eigenvector of PEP, with P - X the ith eigenvector of E, and = SAIVE(1 + VE)
Proof. We will use Weyl's Theorem (Lemma 6 proof this, by defining
G (I Vnn )E viu])
G2 (I uu ) uu")
then for br the eigenvalues of G1, and y4 the eigenvalues of G2 we know d2 =11, A3 = P2,... and d = )2 = ...... etc. Now we can use this as follows:
λ = A + (λ. A;-1)
$ - 14 -
< 5 || -Gll
where the last inequality follows by Weyl's Theorem. Next we will bound ||G1 G2
|G G2ll [|(,,0] uu Σ) + (Σere] EuuJ) + (uu Exu U1 v. Σ2 2i )ll
S 1 uu |2|
where the last step follows as (wm T Eun lala Eoro ia and aaaall lll ||uu" T 1/2 1. Further it turns out that we can bound [| uu ll using sin (vi, u) S &: First we that as u and are unit vectors can write
(wu un YSun" T + ma E(uu
Ou1 sin
so this means
cosu cos aaip cos2 wu
+ otoo) + sin? out
and also gives us
|| Iuu""
u 2 = (coos 0 - Iaaael + cosossi
+ vi vi + sin? Oug oi Tll
|| sin" Our "I. + cos0 T + ou oiT) + sin" 0wl u 1l2
sin 0 || || + cos sin " of of ll sin" 011 of T
< 2 sin? 0 + 2| sin 0| s 2 2 + +-8
38

---

We can now use Lemma 24 lowerbound the eigengap of PEP.
Lemma 25, For E Rdxd a matrix with eigenvalues \ X2 2 2 Ad, = uu T with
E Em) and X 2 d 2 ...... 2 the eigenvalues of PEP
X X2 z d2 X3 22
where A SAIVE(1+ VE) and { sin with the angle between u and U1 the top eigenvector 2.
E.1 Proof of Utility of DP-Ojas
Theorem Given A An are i.i.d. and satisfy Assumption MODIFIEDDP-PA. and DP- O-jass
as defined Algorithms 2 and 3 are stochastic ePCA oracles with Ç O n' /lgloo(1/5)
and Ç 5=0
In 1 111l//log1//))
respectively.
Proof. The proof follows by the utility proofs of MODIFIEDDP-PCA and DP-Ojas (Theorem and Theorem I0) and Lemma 17
Theorem 10 (DP-Ojas). Privacy: If O(Vlo((n88)mm) then Algorithm iss (c, 6)-DP.
Utility: Given i.dd samples (A, E Raxdia Jim1 satisfying Assumption A with parameters (E, V,K,K, n', a,y3) 72),
dx'(7 + log
n ZZC. C. 6R=+
with a large enough constant C, then there exists a choice of learning rate th such that Algorithm with choice of $ 0.01 outputs wn that with probability 0.99 fulfills
sin(w,, v1) S 00
V (v=
(
lld 1/8) ))
en
where K'
((PPP))Axp(PSS) (P(P and Ö(-) hides voly-logarithmic factors in n, d, 1/e, and log log(1/8)
A
and polynomial factors K.
Proof.
Privacy:
The privacy proof follows by Lemma 3.1 Liu et al. 2022b
Utility: By Assumption A.4 it follows analogously Lemma 3.2 in Liu al. 2022b that with probability 1 - O()) Algorithm does not have any clipping. Under this event, the update rulc
becomes
w/ + wi-1 + - Wt + Pu//1|Pu/ll
where B = C' CCt./((Knn log" (nd/{) + 1) and ~ (O011). Just like in the proof of Theorem we use that p2 and Lemma rewrite this as
w/ + wi-1 + P/P (A, + 28aG,, Pw,
where G is matrix whose entries are i.i.d. .N distributed. So if we define
A. A. + 28aGr
this becomes
w/ 4- W + P A.P
so if show the A,'s fulfill all requirements for Theorem utility guarantee. Equivalently to the proof of Theorem 9 we can show
will directly obtain the wished
[B[(A, Σ)(Á, Σ) T1l2 s VA 4o 2
|4, - Σ||2 MX + 2C3aB(Vā Vog(n/()= =:
39

---

Under the event that ||A,, - E112 I M for all & E [n], we apply Theorem with a learning rate -a)(()))+ where
Mh
(V 11)
= 20 max
(A1 1hi->2) X2)" (A1 >2) log + 100)
which tells us that with probability 1 - f.r n2 =
sin (wn, vi) Colog(1/()
(d($)
2h
h2v
72
(2h - (2 - 22)
for some positive constant C. we plug in a C' lok(n/8) evn
(as defined in Algorithm 30, set ( 0(1),
K O(), select h e (n)(n)) and assume
MA1 log(n)
(log((())) (Ky log (nd/() (ndd(())) + 1) log(n/0) (og(n)))oo(())))) log(n)d (A1 - X2)=
lo (n)
2 C
A1 X2
(A1 - 22)
(A1 22)
we are guaranteed n 2 E and d(g/n) - 1/n2, so we will obtain the wished bound.
Remark. An analogue to Lemma 23 holds as well for k-DP-Ojas, by simply setting
B, = 0
(V
V
(r+ + 10d
en
E.2 Sample Size requirements
The sample size condition in Theorem
ex22 d 7 1n(1/8)
Vd Vd((n(1/8)322
+ R + ReV
E > 12 1- V,
n 2 C' max
x²2 y k2 d /m(1/1))
includes an exponential dependence on the spectral gap: 2 exp(x'). While this is relatively harmless as there is no such exponential dependence in the utility guarantee of the Theorem, we exchange for an additional term the utility
are able to get rid of this exponential dependency guarantee. When looking at the utility proof of MODIFIEDDP-PCA arises as we choose T and so that (É/T)= 1, as this is one of the requirements of Theorem 7 The specific inequality that arose from bounding (E/T) and that lead to this exponential dependency is
(Theorem 9 we see this term
Afgg
1/3
(28)
(A1 X²)
(see Equation (5 ). As we selected T = c' c'(log n33,, we required log(n) > A1/(Ai A2). By selecting slightly larger T = ek log we would get rid of this exponential dependence, however at the cost of getting an extra term of 2dd log(1/8)/(en)) in the utility guarantee.
F Proof of Lower Bound
Corollary 3 (Lower bound, Spiked Covariance). Let the d n data matrix X have i.i.d. columns sam- ples from distribution P = =N,00, U AUT +o21,) E P(), o²) where P(), 0²) = (0, Σ), Σ A1 < CA). Suppose X I d explee cole ndkk + dk)) for
U + L cA < > < some small constants co. cp > 0. Then, there exists an absolute constant e₁ > 0 such that
ov + +
(V
dk
dk
A1)
inf sup
E[[l 2 c1
tru a PEP(A.
(2: +02) ()
nE
40

---

Proof. Combining Lemma 26 with Theorem 13 we obtain the lower bound in Corollary 3
Lemma 26 (Reduction to Frobenius norm), Let E be a PSD d x d matrix with top-k eigenvectors VE E Bdxk and eigenvalues d 2 ... 2 Ad. Any U Bddk that satisfies |UU V 2 7 must incur
2² 2 7
>i=1 A:
where De = d Akt1.
Proof. As
(UUT, xx LUUT,X ,X) (VVV,, X)
(ViV ,x) Tr(UUTX) (ViVi, .))
Tr(VV x)
this implies that
TUUUU X) Tr(VA V X)
21-
(29)
Tr(U T X) V X)
So any upper bound on
will give lower bound on C². By Lemma 27 we know
IUU -VI
STIVV - X)
which gives us that
Tr(UU X)
| VIV 2Tr(Va X)
Tr(V2 X)
By equation 29 this gives us
LUT VAVRI32 <
2 2Σ A
Lemma 27. For an orthonormal matrix U E Bdxk and a psd matrix E Rddd with eigengap
A 2 X441 and top k eigenvectors V Baxk we have
|IUT VVI < TMVV (eIVVx)-Tie XUUTUUUXX)
Proof. We will proof this by proving the following two (in)cqualities:
A sin θUU, V) Tr(VV X) Tr(UUTx) X)
(30)
| VV || v sin ( V)ll=
(31)
Equation 30
We first that
Tr(VV x) TrUUUTT xx) Tr(VVV UU (X Aat1)
Tr((VV - D441) = AR+1 (Tr(VVT) - IN(UUT)= =0
where the last equality follows as Tr(UUT) = k Tr(VVT). Now Now
M((VVT-UT)(X A4t1) TT((VVT + (Ts VV -UUIVUTTUUTTE - A4t1)la)
= =T<(VVT(VVT (X- +T((II -VT))VT-- -
2 TT(VV T(TT -UTU-UTC (x0-)xx)
> A,TI((VAVT -UUT)+)
41

---

where (A)+ is obtained by replacing each eigenvalue of the matrix A with max(u;, 0z. Now we note that
Tr((V -
sin @ V -UU -
Hence, since the sin 0, nonnegative (as the principal angles 0; lie in [0, 7/2) we have Vr((VV )UT)+) Ei= sin 8, Further, by definition we have
|| sin O(U
sin 0,
==
So by noticing that for any angle 0 E 7/, sin 0 2 sin" 0 we have proved the first inequality. Equation
|LUT - VV T || Tr((UUT - T2)) By expanding (UUT - VVT)2 we see 31
UU (UU - = - -U vV -VV +V
which gives us
Tr((UU - - = vT
2h: -T(V
2k: V
Lastly, utilizing
k
110 T VI = 2 Σ
cos 0, = Σ (1 - sin 02)
==1
1=1
the proof follows.
F1 Existing Lower Bounds
Theorem 11 (Lower bound, Gaussian distribution, Theorem 5.3 in Liu et al. [2022a]). Let Me be class of (s, O)-DP estimators that map n i.i.d. samples to an estimate i Rd. set of Gaussian distributions with (A1, X2) as the first and second eigenvalues of the covariance matrix is denoted by P()))))) There exists a universal constant C such that
d
A2 A
inf sup BEMM, (EP(A)))))
Es- (sin(((s)((s))))) e1) 2 C'min K
en
Theorem 12 (Lower bound without Assumption 4, Theorem 5.4 Liu et al.
(022aa) ). Let Ms be class of (s, DDP estimators that map i.i.d. samples to an estimate ē E R. set of distributions
satisfying 1.-3. of Assumption A with M = Ö(d + /ne/d), V= ((d) and 7 = O(1) is denoted by
P. For d 2 2, there exists universal constant C > 0 such that
(Van
d |dAlog(( log((1 )//))
inf sup Es-pr (aaiinn((Ss)). e1)] Min PEP
Cwmin
En
Theorem 13 (Theorem 4.2 in Cai al. 2024 Let the d data matrix X have i.i.d. columns samples from distribution P (0, U AU + I E P(), Suppose X S cb exples
(okv + d for some small constants co. cb > 0. Then, there exists an absolute constant ei > such that
EHÜÜT - -UUTIE 2a
((oVAto*)
(VL++ dvk
A1
inf sup
Beula PEP().
Vi
where the infimum is taken over all the possible (s, algorithms, denoted by Us and the expectation is taken with respect to both Ú and P and
p(),03) : ( UAU L
Oax, c.) Ao), Se S CoA}
42

---

Algorithm Performance Sample Size for All (d, k) Combinations
24
22:00
+000
18:00
2008
semple
0-406, 6.6.
180
4-100, eHO 1-15
00
85
55
24
20004
20000
3000
+0000
13000
2008
20000
1003
3M0X
3000
4000
300
C1-t88 0.000 boa
130
150
di-AAl aHAun h-13
04
Capp M0/
22
.0004
20000
30008
10000
2000 33000
1003
2000
4.000
Figure 3: Comparison of K-DP-PCA and k-DP-Ojas for varying i and d (also including DP-Gauss- 1 (input perturbation), DP-Gauss-2 (object perturbation), and De-Power-Methol on the spiked covariance model. We plot the mean over 50 trials, with the bars representing the standard deviation.
G Experiments
In Section we compare the performance of k-DP-PCA and k-DP-Ojas to two modified versions of the DP- Gauss algorithms of Dwork et al. [2014b]. we refer to as DP- Pap-aauss- 1 and 2 respectively, and modified version of the noisy power method [Hardt and Price 2014).
Given a stream of matrices {A.} and a clipping threshold / (that is chosen based on the distri- bution of the input data), DP-Gauss-1 first clips each matrix to have trace at most 62: A, A; min (1, 32 (T(()))) In a second step it computes the sum of the A; X = x; A; and then per- forms the gaussian mechanism: X' = X+ F,, where F: is a symmetric matrix with their upper triangle values (including its diagonal) i.i.d. sampled from (O, AiLa) and A 8 3² log(1.25/0)f4 Lastly, it performs an eigenvalue decomposition on X', and releases the top k eigenvectors.
uP-Gauss-2 2 just like DP-Gauss-1 clips the matrices and sums them up to obtain X. Next it extracts V&x the top & eigenvectors of X via an eigenvalue decomposition and privatizes its eigengap: Lap (2/E). It then applies the Gaussian mechanism to V V/ = V2 + E, where E' is a symmetric matrix with their upper triangle values (including its diagonal) i.idd. sampled from from.N(O. (0, AbLa) and
gi A AR+1 + 2, where
B² + 22oggo/////////
A
19k 2(1 + log(1 (/8)/s)
Finally, an additional eigenvalue decomposition is performed on V/, as the introduction of noise may result in matrix whose columns are no longer orthogonal. The top & cigenvectors obtained from
43

---

this decomposition are then released. It is important to note that if 9k: is not positive, the procedure is no longer differentially private, despite adherence to the algorithm described in the original paper (see Algorithm 2 in [Dwork et al. 2014bl). A fully compliant implementation- -aso discussed in the paper-would employ the PTR mechanism, albeit at the expense of increased privacy loss. For simplicity and to allow greater flexibility, we instead opt to resample fresh noise whenever Ik S 0.
DP- Pe-PPoer--Mtthooe clips the matrices with respect to the square root of the trace and the trace of the square root of the diagonal. For A = aa' with a E Rd the first corresponds to clipping with respect to ||a S B, whereas the second to clipping with respect to ||a||2 S a, where the clipping threshold 3 is the same as we choose for the DP-Gauss algorithms. In a second step it then also computes the sum of the clipped matrices and then performs the noisy power method (find algorithm in [Nicolas et al. 2024)) where the gaussian noise that is being added at every iteration of the power method is scaled with an additional |3 a factor.
G.1 Synthetic Data
We sample data from the spiked covariance model, meaning each matrix A, E Rdxdd consists of deterministic rank-k component, plus random noise that ensures A; is full-rank. For the case k = 1, we generate samples via Ty = 8 + n4, where ~ Unif ((Auu, U, -}po3), with e E Ie a unit vector and \ E R a scalar. The noise term is sampled as n, ~ NO oa).). We then define A; = .. - Here, a1 and are inputs to the sampling function, while is obtained by sampling standard Gaussian vector of dimension d and normalizing it to unit length. For & > 1, we proceed differently: first sample a random matrix V R with i.i.d standard normal entries, then apply the Gram-Schmidt process to obtain V&= E Rdxk a matrix with & orthonormal columns. We construct A; V + 2,2, where 2; (N00, and A R is diagonal matrix whose entries are user-specified eigenvalues. We note that this construction for k > is not a direct extension of the k 1 case. In particular, independently sampling i vectors as in the their outer products would result in mixture of Gaussians rather than single spiked covariance structure. To avoid this and retain a well-defined rank-k component, we instead fix the subspace and apply deterministic structure through V.AV,
case and summing
We set 3 = CVA1 + /dloog(n/() for 1P-Gauss-1 and DP- OP-Gauss-2. where n is the number of samples, ( is the probability of not clipping. We set Ç = 0.01 uniformly across all methods, including our algorithms (MODIFTEDD--PC.. and k-DP-Ojas) as well as both Gauss baselines. For both k-DP-PCA and k-DP-Ojas, the parameters K and (as defined in Assumption A) must be provided as inputs. In the case of data generated as described above, we have a = 1 and K O(1) and thus we set a = and K = 1 for our experiments. Additionally, k-DP-PCA requires specifying a batch size B, which is used in the PRIVMEAN algorithm. While the theoretical analysis suggests that the optimal choice is B nz/ log) where is the sample size, we found empirically that setting B- v yielded improved performance practice. Lastly, we need to set a learning rate for k-DP-PCA and k-DP-Ojas. For k-DP-PCA we set the learning rates to be
m = 1/ + (A, - A411) t/ log(n))
where / refers to the 7th update step inside of MODIFEDDP-PCA (t E [T] where T = Ln/B)) and to the ith iteration of K-DP-PCA. For k-DP-Ojas we empirically found that simply choosing a decreasing learning rate (independent of eigenvalues) resulted in good performance, so we set the learning rate to be
π 1/(1+
for j E [n]] for all & iterations of k-DP-Ojas.
G.2
Gaussian Data
For more general data distributions-thee is, those not exhibiting clean signal-plus-noise decompo- Cooonn-Coolllaaaa Eovollary[indae indicates that k-DP-PCA can still outperform existing state-of wate-of-the--e art methods, primarily due to its favorable scaling with the ambient dimension d. However, our second algorithm, k-DP-Ojas, offers comparable utility guarantees in such settings (see Corollary 4).
While k-DP-PCA has strong theoretical properties, it requires careful tuning of the learning rate, which can be challenging practice. Specifically, depends on a step size parameter that must be adapted to the signal-to-noise ratio and spectrum of the data. In regimes where the noise level is
44

---

Algorithm
k-DP-Ojas
DP-Gauss-2
DP-Gauss-1
1.00
<approx
0.75
Gapporox
0.75
<.pprrx
0.75
0.50
0.50
0.50
0.25
0.25
0.25
10"
10
25
75
100
20
40
60
sample size
Ap Ag+1
dimension d
(a) utility vs sample size
(b) utility vs cigengap
(c) utility vs dimension
Figure 4: Comparison of k-DP-PCA DP-Gauss-I (input perturbation) and 2P-Gauss-2 (outpur perturbation) on gaussian data. We plot the mean over 50 trials, with shaded regions representing 95% confidence intervals. We set & 2. d 200. A 10, e 1. and d = 0.01.
moderate high, the theoretical gains of k-DP-PCA do not clearly outweigh the practical overhead of hyperparameter tuning and range estimation.
In contrast, k-DP-Ojas is simpler to deploy: it requires hyperparameter tuning and exhibits robust performance across a range of learning rates. As shown Figure k-DP-Ojas consistently outperforms other state-of-the-art methods on data of the form A, raæ; with æ; N/ E). For these reasons, we recommend k-DP-Ojas as the preferred method in practical settings involving general data distributions.
G.3 Further comments
Lastly, we comment on potential modification our algorithm. The subroutine PRIVRANGE is used to privately estimate a suitable truncation threshold around the mean for PRIVMEAN, In certain scenarios, however, may be preferable to fix this threshold in advance determine through an alternative (non-pri) mron-private) mechanism. Doing so would eliminate the need to estimate the threshold from the data under differential privacy, thereby avoiding the substantial sample complexity that this estimation typically requires.
This consideration directly explains the lower bound sample size in k-DP-PCA: sufficient number of samples is necessary to ensure that the truncation threshold can be estimated both meaningfully and privacy-preserving manner. Interestingly, this also sheds light on why the algorithm may perform better in practice than its theoretical utility bounds suggest. In particular, even when using fewer samples than required for formal utility guarantees-i.e. below the threshold for reliable private estimation of the truncation point-k-DP-PCC can still exhibit strong empirical performance. In such cases, the algorithm retains its privacy guarantees, but the formal utility guarantees no longer apply.
More broadly, while our algorithm is provably asymptotically optimal, the choice of range finder estimation method can significantly impact empirical performance depending the data distribution. One of the key advantages of our iterative framework is its modularity. As demonstrated by k-DP-Ojas in Section 4 the algorithm estimation subroutine can be replaced with alternative methods tailored to specific data characteristics. Crucially, Theorem ensures
be viewed
alug-and-pla, template: the private mean
ensures that any such substitution carries over corresponding utility guarantee. enabling both flexibility and theoretical rigor.
H Algorithms used in Modified DP-PCA
Below we describe the two subroutines that estimate the range and mean the gradients in MODIFEEDD-PCAA.
45

---

Algorithm 6 Top-Eigenvalue- Estimaatinn Algorithm in [Liu et al. 2022a]
Input:
| privacy parameters (c, 6). failure probability т E (0,1)
1: 9i < 92i 92i-1 for E 1,2, [B/2]
2: $ {
3: Partition 5 into Ci (lg((/(67)) subsets and denote each dataset as Gj E Rdxb (where
b = [B/2k] is the size of the dataset)
4: 2 +- top eigenvalue of (1/b),,G} for j [k]
5: partition oo) into S 5 f.... 2/4 2 2: 1/4 (1,2!/4)....
6: run (e. 8.-DP histogram learner on {^] (
Jj=1 over ?
7: if all bins are empty then
8: return
9: else
for r] the bin with the maximum number of points the DP histogram
11: return Å =
12: end if
Algorithm 7
-ettcannstiiation. Algorithm 5 in [Liu et al. [002aa]
Input: { privacy parameters (E, target error a, failure probability r E (0, 1),
approximate top eigenvalue A
1: let = 2 K / log²(25) (25)
2: for j = 1, d do
3: Run 4/ (//
DDD histogram learner of Lemma {gi)e([ Ω
(..., (-2-, v). (-v, 0), (0, v). (v, (v,2v].... 2v]....)
4:
Let h) be the bucket that contains maximum number of points in the private histogram
5:
Øj
+
6:
Truncate the j-th coordinate of gradient (0ilie(B) by [ō 3K V (BD/T),
3K V Â (Dg"(
Let 9, be the truncated version of gi
8: end for
9: Compute empirical mean of truncated gradients jı = (1/B) Ti and add Gaussian noise:
12K PekvAloge (Bdl
2
u = a +
0,
L
eB
return
46


Reviews:
[{"review_id": "iRCkv0hXyr", "reviewer": "Reviewer_cqe7", "summary": "The paper considers the problem of DP $k$-PCA. The goal is to privately approximate the sub-space corresponding to the $k$ largest eigenvalues of a matrix that is the expected value of a distribution over random matrices. The problem has been addressed in the past in the work of Liu et al. (2022) for the case where $k = 1$, i.e., the case where we want to perform top eigenvector estimation.\nThe present paper gives the first algorithm for private $k$-PCA under approx-DP for which it suffices for the number of samples to scale roughly linearly with $d$ (the dimension of the data) to obtain low statistical error. A core element of the approach involves the use of the deflation framework of Jambulapati et al. (2024). That work demonstrates how, given black-box access to an oracle for top eigenvector estimation, it becomes possible to estimate the top-$k$ subspace by using the oracle iteratively. The present work combines a stochastic version of that reduction with variants of the subroutines given in Liu et al. (2022), which leads to their algorithm for $k$-PCA. This necessitates using the notion of a stochastic e-PCA oracle, and showing that the well-known Oja's algorithm satisfies the requirements of the oracle's definition. Upper bounds are given when the input is constructed from Gaussian random vectors, as well as when it comes from the spiked covariance model. Additionally, a lower bound is given for the spiked covariance model, which exhibits a gap with the upper bound in the dependence on $k$. Finally, an empirical evaluation of the method is conducted.\n\nArun Jambulapati, Syamantak Kumar, Jerry Li, Shourya Pandey, Ankit Pensia, and Kevin Tian. Black-box k-to-1-pca reductions: Theory and applications. arXiv:2403.03905, 2024.\n\nXiyang Liu, Weihao Kong, Prateek Jain, and Sewoong Oh. Dp-pca: Statistically optimal and differentially private pca. In Neural Information Processing Systems (NeurIPS), 2022.", "questions": "Can the authors provide a more detailed discussion and comparison with the results of Liu et al. (2022) and Jambulapati et al. (2024)?", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "I think that this is a good paper, but there's a number of weaknesses too in my opinion. I am going to discuss both positive and negative aspects in detail below.\n\nStrengths:\n1) This is the first work that gives a computationally efficient private algorithm for top-$k$ PCA with roughly linear sample complexity and low error. I feel this alone gives the work significant merit.\n2) The use of the deflation method from the work of Jambulapati et al. (2024) in the context of privacy was something that I found nice at a conceptual level.\n\nWeaknesses:\n1) One issue has to do with the gap in the $k$-dependence between the upper and the lower bounds. This is a weakness, but I don't think it significantly affects the value of the paper, since this is the first algorithm for DP $k$-PCA, and I think it's not damning if it is not statistically optimal.\n2) By reading the main body, it was not entirely clear to me what the technical challenges were for modifying the subroutines of Liu et al. (2022), and to show that the requirements of a stochastic e-PCA oracle are satisfied. I have not read Liu et al. (2022) and Jambulapati et al. (2024), so I was hoping for a more detailed discussion, which would make the evaluation of the merits of the present work easier.\n\nOverall, I think this is a decent paper, but I want to wait for the discussion period before expressing strong opinions about whether it should be accepted or not. I am voting borderline accept for the time being.", "was_revised": true, "final_justification": "I have read the authors' response carefully. It clarifies my questions about the technical challenges of the work, so I have decided to increase my score accordingly.", "rebuttal": "We thank the reviewer for their comments. We address their perceived weaknesses below.\n\n>  Gap in the k-dependence:\n\nWe acknowledge the gap and note that we incur a factor of $k$ because our analysis requires that the projections $P_{i-1}$ at step $i$ of the deflation method are independent of the matrices $A_1, …, A_n$ we pass at step $i$. Therefore we split the data into $k$ equal subsets so that each deflation step obtains a fresh independent batch of data. This ensures that at iteration $i$ of the deflation method: $P_{i-1} = I - \\sum_{j < i} u_j u_j^{\\top}$, is independent of the data matrices. However, this requirement might be an artifact of our proof, and if we were able to do the analysis over correlated batches, we could reuse all data samples at every deflation step and only incur a factor of $\\sqrt{k}$ (due to adaptive composition). Reducing this gap in $k$ or understanding  if the $\\sqrt{k}$ factor is inherently necessary for deflation methods with DP, could be an exciting direction for future work.\n\n\n> Technical contributions and challenges: \n\nOur algorithm indeed combines the DP-PCA method by Liu et al. with the deflation strategy from Jambulapati et al. Algorithmically, our techniques are reminiscient of these methods. However, the main contribution of our work lies in the theoretical arguments showing that this combination indeed leads to a working DP algorithm with a utility guarantee in the stochastic setting.\n\nBelow we outline why this is not a straightforward result and what technical challenges we encountered. \n1. Standard 1-PCA oracles (e.g. Liu et. al. 2021) guarantee that their (randomised) output eigenvector $u$ is close to the top eigenvector of the population covariance $\\mathbb{E}[xx^\\top] = \\Sigma$. In deflation, one sets $P=I-u_1u_1^\\top$ and runs the oracle on the residual data $Px$, hoping to approximate the top eigenvector of the residual covariance $P\\Sigma P^{\\top}$. However, because P itself is not only random but also correlated with the data (due to both the adaptive privacy noise and the randomness in the data used to construct $u_1$), the stochastic 1-PCA oracle only guarantees that $u_2$ is close to the top eigenvector of $\\mathbb{E}[Pxx^tP]$, which is too weak for deflation (deflation needs closeness to the top eigenvector of $P\\,\\mathrm{E}[xx^t]\\,P^\\top$).\nTo avoid this and apply DP to the deflation approach, we introduce the **stochastic ePCA oracle** (Definition 3), which by design (1) inputs a random projector $P$ and (2) outputs a vector $u$ guaranteeing that with high probability $u$ is close to the top-eigenvector of $P\\mathbb{E}[xx^{\\top}]P$.\n    * To the best of our knowledge,this is the first work to apply deflation in a DP context. We do this by introducing the stronger but sufficient concept of stochastic ePCA oracle. \n    * We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)\n    \n2. Having identified what is sufficient for the problem, we next construct a DP algorithm that implements this stronger oracle. Starting from Liu et. al.’s DP-PCA (which is itself a modification of the classical Oja’s method), we introduce the following important modifications\n    * Naively feeding $Pxx^{\\top}P^{\\top}$ into DP-PCA fails because the gaussian noise added in PRIVMEAN (for DP) pushes the iterate outside of $\\mathrm{Im}(P)$. Consequently successive outputs would not be orthogonal and deflation breaks. To fix this, we explicitly re-project back onto $\\mathrm{Im}(P)$ (Step 5 of ModifiedDP‑PCA). This ensures every eigenvector remains in the correct subspace, preserving orthogonality.\n    * Even with the projection, as mentioned above, existing analyses only shows closeness to the top eigenvector of $\\mathrm{E}[Pxx^{\\top}P^{\\top}]$, not to $P\\mathrm{E}[xx^{\\top}]P^{\\top}$. To solve this, \n\n        1. we first reduce the private updates of modified DP-PCA to a non-private (projected and noisy) Oja’s algorithm on $P\\tilde{A}P^{\\top}$ where $\\tilde{A}$ is a \"noisy\" version of $xx^{\\top}$  (Theorem 9) and \n        2. prove a new utility bound for this projected and noisy version of Oja’s algorithm showing that its output indeed aligns with the top eigenvector of $P\\mathrm{E}[xx^{\\top}]P^{\\top}$ (Theorem 8)\n    * Further we had to control the error terms resulting from a single call of ModifiedDP-PCA. To the best of our knowledge Jambulapati et al considered 1-PCA oracles whose utility guarantees do not contain constants affected by the projection matrix P. The utility guarantee of ModifiedDP-PCA (Theorem 9) however, depends on several constants originating from constraints on the data (see Assumption A). If we replace $\\{ x_i x_i^{\\top}\\}$ the input to ModifiedDP-PCA with $\\{ Px_i x_i^{\\top}P\\}$, we need to control how these constants change. We show that most of the constants will not incur a cumulative error (see Lemma 10, 11 and 13), except for $\\kappa = \\frac{\\lambda_1}{\\lambda_1 - \\lambda_2}$ (= eigengap). The eigengap will indeed incur a cumulative error due to deflation (as at every step i we need to account for how far the top eigenvector of $P\\Sigma P$ is removed from the true ith eigenvector of $\\Sigma$). In Lemma 23, we characterize how to control this error. This might be of independent interest when using 1-PCA algorithms whose utility depends on the eigengap ($\\kappa$) with the deflation method, as it was shown that the eigengap can play an important role in the performance of PCA algorithms.\n3. Lastly we derive an **information-theoretic lower bound for differentially private PCA under our setting**. \n\nTaken together, these yield the first deflation-based DP-PCA algorithm for $k>1$ with near-optimal utility. Some of the new tools that we introduce e.g. stochastic-ePCA oracles, deflation with stochastic methods, as well as the new Oja’s analyses, may well be of independent interest outside DP.\n\nApart from this we note that our proof strategy immediately gives us two additional insights:\n1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.\n2. Our proof strategy generalizes beyond ModifiedDP-PCA to any stochastic ePCA oracle, leading to our second algorithm, k-DP-Oja (via the Meta Theorem) but can also be used for non-DP randomised PCA algorithms.\n\nWe hope our answer clarifies the technical challenges in obtaining our results. We are happy to include these details in the updated draft as well as answer any questions you may have during the rebuttal period."}, {"review_id": "lLV5dhleWM", "reviewer": "Reviewer_KnV6", "summary": "The paper studies the problem of k-PCA in the differential privacy settings. Prior work Liu et al.[2022a] address the problem only when k=1. Recently Jambulapati et al. [2024] provides a k-to-1-PCA reduction. This paper extended the deflation analysis of Jambulapati et al 2024 to the stochastic setting. The proposed algorithm repeatedly applies the DP-PCA subroutine in Liu et al. 2022a to recover the top eigenvector and filter out the component in the recovered space. A complementing lowerbound showed that the algorithm achieves near matching statistical error upto a factor of k.", "questions": "1. How is ModifiedDP-PCA different from DP-PCA in Liu et al. [2022a]? If we simply project each matrix with PAP^T and apply DP-PCA, do we have the same result and guarantee?\n2. Following the first question. Line 210 on page 7 says “Note that we cannot plug in the DP-PCA algorithm...since it only guarantees relative error on E[P] \\Sigma E[P]”. What does this mean? Isn’t P an input to the algorithm which is deterministic?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths: The paper addresses an important problem in the DP data analysis. The algorithm is simple to implement and achieves a near optimal error upto a factor of k.\nWeakness: It is not clear there is significant technical novelty or contribution, at least not that I am aware of upon reading the paper. It seems to be a straightforward combination of Liu et al. [20222a] and Jambulapati et al. [2024]. The guarantee of the algorithm is off by a k factor, which might be improved to sqrt(k) if data is reused.", "was_revised": true, "final_justification": "I will maintain my recommendation of Borderline Accept due to limited technical innovation of the paper.", "rebuttal": "We thank the reviewer for their comments. We hope our responses below answers the reviewer's concerns. \n\n> How is ModifiedDP-PCA different from DP-PCA? ... If we simply project each matrix with PAP^T and apply DP-PCA, do we have the same result and guarantee?\n\nWhile, we agree with the reviewer that Modified DP-PCA and DP-PCA (by Liu et al.) are algorithmically similar, they differ in step 5 of the algorithm. We highlight that by simply inputting the matrices $PAP^{\\top}$ into DP-PCA, we would not obtain the same results. The additional projection ($P$) we add in step 5 of ModifiedDP-PCA is crucial, as the noise the PRIVMEAN algorithm (subroutine of DP-PCA) adds to achieve DP would lead the updates to no longer lie in Im($P$), which in turn will cause the deflation to not converge.\n\nHowever, even if one were to include this additional projection in Step 5, the utility guarantee in Liu et al  still does not apply. Their guarantee shows that the approximate eigenvector u is close to the top eigenvector of $\\mathbb{E}[P A P]$. While this would suffice if $P$ were deterministic, in our setting $P$ is random, as it is dependent n the eigenvectors $u_j$ obtained in earlier steps of the deflation method. Due to the inherent randomness of our algorithm (due to DP) and the data-dependent nature of this randomness, the projection matrix $P =  I - \\sum_{j < i} u_j u_j^{\\top}$ may introduce bias. This bias can hinder convergence, which is why we require a new analysis accounting for this. Consequently, this also explains why it is not sufficient to apply an arbitrary DP algorithm within the deflation framework and we need it to satisfy a property like the stochastic ePCA oracle.\n\n> “It is not clear there is significant technical novelty or contribution”\n\nWe agree with the reviewer that our algorithm indeed combines the PCA method by Liu et al. with the deflation strategy from Jambulapati et al. Algorithmically, our algorithm is similar to these two techniques. However, the main contribution of our work lies in the theoretical arguments showing that this combination leads to a working DP algorithm with a utility guarantee in the stochastic setting.\n\nBelow we outline why this is not a straightforward result and what technical challenges we encountered. \n1. Standard 1-PCA oracles (e.g. Liu et. al. 2021) guarantee that their (randomised) output eigenvector $u$ is close to the top eigenvector of the population covariance $\\mathbb{E}[xx^\\top] = \\Sigma$. In deflation, one sets $P=I-u_1u_1^\\top$ and runs the oracle on the residual data $Px$, hoping to approximate the top eigenvector of the residual covariance $P\\Sigma P^{\\top}$. However, because P itself is not only random but also correlated to the data (due to both the adaptive privacy noise and the randomness in the data used to construct $u_1$), the stochastic 1-PCA oracle only guarantees that $u_2$ is close to the top eigenvector of $\\mathbb{E}[Pxx^tP]$, which is too weak for deflation (deflation needs closeness to the top eigenvector of $P\\,\\mathrm{E}[xx^t]\\,P^\\top$).\nTo avoid this and apply DP to the deflation approach, we introduce the **stochastic ePCA oracle** (Definition 3), which by design (1) inputs a random projector $P$ and (2) outputs a vector $u$ guaranteeing that with high probability $u$ is close to the top-eigenvector of $P\\mathbb{E}[xx^{\\top}]P$.\n    * To the best of our knowledge, **this is the first work to apply deflation in a DP context**. We do this by introducing the stronger but sufficient concept of stochastic ePCA oracle. \n    * We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)\n    \n2. Having identified what is sufficient for the problem, we next construct a DP algorithm that implements this stronger oracle. Starting from Liu et. al.’s DP-PCA (which is itself a modification of the classical Oja’s method), we introduce the following important modifications\n    * Naively feeding $Pxx^{\\top}P^{\\top}$ into DP-PCA fails because the gaussian noise added in PRIVMEAN (for DP) pushes the iterate outside of $\\mathrm{Im}(P)$. Consequently successive outputs would not be orthogonal and deflation breaks. To fix this, we explicitly re-project back onto $\\mathrm{Im}(P)$ (Step 5 of ModifiedDP‑PCA). This ensures every eigenvector remains in the correct subspace, preserving orthogonality.\n    * Even with the projection, as mentioned above, existing analyses only shows closeness to the top eigenvector of $\\mathrm{E}[Pxx^{\\top}P^{\\top}]$, not to $P\\mathrm{E}[xx^{\\top}]P^{\\top}$. To solve this, \n        1. we first reduce the private updates of modified DP-PCA to a non-private (projected and noisy) Oja’s algorithm on $P\\tilde{A}P^{\\top}$ where $\\tilde{A}$ is a \"noisy\" version of $xx^{\\top}$  (Theorem 9) and\n        2. prove a new utility bound for this projected and noisy version of Oja’s algorithm showing that its output indeed aligns with the top eigenvector of $P\\mathrm{E}[xx^{\\top}]P^{\\top}$ (Theorem 8).\n    * Further we had to control the error terms resulting from a single call to ModifiedDP-PCA. To the best of our knowledge Jambulapati et al considered 1-PCA oracles whose utility guarantees do not contain constants affected by the projection matrix P. The utility guarantee of ModifiedDP-PCA (Theorem 9) however, depends on several constants originating from constraints on the data (see Assumption A). If we replace $\\{ x_i x_i^{\\top}\\}$ the input to ModifiedDP-PCA with $\\{ Px_i x_i^{\\top}P\\}$, we need to control how these constants change. We show that most of the constants will not incur a cumulative error (see Lemma 10, 11 and 13), except for $\\kappa = \\frac{\\lambda_1}{\\lambda_1 - \\lambda_2}$ (= eigengap). The eigengap will indeed incur a cumulative error due to deflation (as at every step i we need to account for how far the top eigenvector of $P\\Sigma P$ is removed from the true ith eigenvector of $\\Sigma$). In Lemma 23, we characterize how to control this error. This might be of independent interest when using 1-PCA algorithms whose utility depends on the eigengap ($\\kappa$) with the deflation method, as it was shown that the eigengap can play an important role in the performance of PCA algorithms.\n3. Lastly we derive an **information-theoretic lower bound for differentially private PCA under our setting**.\n\nTaken together, these yield the first deflation-based DP-PCA algorithm for $k>1$ with near-optimal utility. Some of the new tools that we introduce e.g. stochastic-ePCA oracles, deflation with stochastic methods, as well as the new Oja’s analyses, may well be of independent interest outside DP.\n\nApart from this we note that our proof strategy immediately gives us two additional insights:\n1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.\n2. Our proof strategy generalizes beyond ModifiedDP-PCA to any stochastic ePCA oracle, leading to our second algorithm, k-DP-Oja (via the Meta Theorem) but can also be used for non-DP randomised PCA algorithms."}, {"review_id": "Jk1iyrcD8N", "reviewer": "Reviewer_e7Rs", "summary": "The proposed stochastic k-PCA algorithm not only has differential privacy and computational efficiency, but also overcomes the following two limitations: (i) require the sample size n to scale super-linearly with dimension d, even under Gaussian assumptions on the Ai, or (ii) introduce excessive noise for DP even when the intrinsic randomness within Ai is small.", "questions": "1. In the experimental part, only k=2 was set to compare with other algorithms, and the advantages of the algorithm can not be demonstrated.\n2. Line 230, “However, for other cases such as sub-Gaussian data we expect them to perform similarly.” This conclusion has not been verified.", "limitations": "This paper extends the algorithm DP-PCA of Liu et al. [2022a] and is capable of estimating the top k eigenvectors of any k≤d. However, no new solutions were proposed to overcome the two limitations (i) and (ii).", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 1, "strengths_and_weaknesses": "This paper proposes the first algorithm for stochastic k-PCA that is both differentially private and computationally efficient, supports any k≤d, and achieves near-optimal error.\nWeaknesses: \nLiu et al. [2022a] addressed these issues for sub-Gaussian data but only for estimating the top eigenvector (k = 1) using their algorithm DP-PCA. This paper proposes a kind that can estimate the top k eigenvectors of any k≤d. For k = 1, the algorithm in this paper matches the utility guarantee of DP-PCA and improves the computational efficiency. It also provides a lower bound for the general k > 1. The essence of the paper can be regarded as an expansion of Liu et al. [2022a].", "was_revised": true, "final_justification": "The authors have addressed some of the concerns.", "rebuttal": "We thank the reviewer for their comments. We address each of them below:\n> In the experimental part, only k=2 was set to compare with other algorithms, and the advantages of the algorithm can not be demonstrated.\n\nThe primary goal of the paper is to provide a computationally efficient Differentially Private algorithm with theoretical utility guarantees for the problem of k>1 DP-PCA in the stochastic setting.  Despite the theoretical focus, we do appreciate the reviewers' concerns that larger results with larger d and k will boost the  contribution of our paper. Thus, during the rebuttal we repeated our experiments with larger d and k and observed the same trend as the experiments in the paper (see results below):\n```\n             Mean Distance vs. Sample Size (k=10, d=450)\n    ┌────────────────────────────────────────────┐\n0.98┤ •• DP-Gauss-1   ♰           ♰              │\n0.82┤ ♰♰ DP-Gauss-2                              │\n    │ pp k-DP-Ojas                               │\n0.66┤ cc k-DP-PCA           p                    │\n0.50┤                                            │\n    │                                            │\n0.34┤             •                        p     │\n0.18┤                                            │\n    │ c       c                •                 │\n0.03┤                     c              c    •  │\n    └┬──────────┬──────────┬─────────┬──────────┬┘\n  1995.0     12746.2    23497.5   34248.8 45000.0 \ndistance             sample size n                \n```\n|  Algorithm  |  $n$  |  $d$  |  $k$  |  distance  |\n|-------------|-------|-------|-------|------------|\n| DP-Gauss-1  | 20000 |  200  |   5   |   0.043    |\n| DP-Gauss-2  | 20000 |  200  |   5   |   0.138    |\n|  k-DP-Ojas  | 20000 |  200  |   5   |    0.1     |\n|  **k-DP-PCA**   | **20000** |  **200**  |   **5**   |   **0.002**    |\n|-------------|-------|-------|-------|------------|\n| DP-Gauss-1  | 40000 |  450  |  15   |   0.072    |\n| DP-Gauss-2  | 40000 |  450  |  15   |   0.933    |\n|  k-DP-Ojas  | 40000 |  450  |  15   |    0.57    |\n|  **k-DP-PCA**   | **40000** |  **450**  |  **15**   |    **0.02**    |\n\n> \"However, for other cases such as sub-Gaussian data we expect them to perform similarly.” This conclusion has not been verified\n\nWe also ran our experiments on gaussian-data and observed the same trends.\n``` \n             Mean Distance vs. Sample Size (k=10, d=200)       \n    ┌────────────────────────────────────────────┐\n1.00┤ •• DP-Gauss-1                              │\n0.86┤ ♰♰ DP-Gauss-2   •  ♰          •   ♰        │\n    │ pp k-DP-Ojas                p             p│\n0.73┤ cc k-DP-PCA                                │\n0.60┤                                            │\n    │                                            │\n0.46┤                                            │\n0.33┤      c                                     │\n    │             c                              │\n0.19┤                           c             c  │\n    └┬──────────┬──────────┬─────────┬──────────┬┘\n    100       11325      22550     33775    45000 \ndistance             sample size n                                        \n```\n|  Algorithm  |  $n$  |  $d$  |  $k$  |  distance  |\n|-------------|-------|-------|-------|------------|\n| DP-Gauss-1  | 45000 |  100  |   2   |   0.514    |\n| DP-Gauss-2  | 45000 |  100  |   2   |   0.808    |\n|  k-DP-Ojas  | 45000 |  100  |   2   |   0.477    |\n|  **k-DP-PCA**   | **45000** |  **100**  |   **2**   |   **0.057**    |\n|-------------|-------|-------|-------|------------|\n| DP-Gauss-1  | 45000 |  200  |  15   |    0.85    |\n| DP-Gauss-2  | 45000 |  200  |  15   |   0.912    |\n|  k-DP-Ojas  | 45000 |  200  |  15   |   0.878    |\n|  **k-DP-PCA**   | **45000** |  **200**  |  **15**  |    **0.29**    |\n\nWe hope the above experiments resolves the reviewer’s concern regarding the performance of the algorithm on larger k and gaussian data and that the reviewer will consider increasing their score.\n\n> The essence of the paper can be regarded as an expansion of Liu et al. [2022a].\n\nWhile our work uses a modification of the DP-PCA method by Liu et al., we combine it with the deflation strategy (non-private version in Jambulapati et al).  Algorithmically, our techniques are reminiscient of these methods. However, the main contribution of our work lies in the theoretical arguments showing that this combination indeed leads to a working DP algorithm with a utility guarantee in the stochastic setting.\n\nBelow we outline why this is not a straightforward result and what technical challenges we encountered. \n1. Standard 1-PCA oracles (e.g. Liu et. al. 2021) guarantee that their (randomised) output eigenvector $u$ is close to the top eigenvector of the population covariance $\\mathbb{E}[xx^\\top] = \\Sigma$. In deflation, one sets $P=I-u_1u_1^\\top$ and runs the oracle on the residual data $Px$, hoping to approximate the top eigenvector of the residual covariance $P\\Sigma P^{\\top}$. However, because P itself is not only random but also correlated to the data (due to both the adaptive privacy noise and the randomness in the data used to construct $u_1$), the stochastic 1-PCA oracle only guarantees that $u_2$ is close to the top eigenvector of $\\mathbb{E}[Pxx^tP]$, which is too weak for deflation (deflation needs closeness to the top eigenvector of $P\\,\\mathrm{E}[xx^t]\\,P^\\top$).\nTo avoid this and apply DP to the deflation approach, we introduce the **stochastic ePCA oracle** (Definition 3), which by design (1) inputs a random projector $P$ and (2) outputs a vector $u$ guaranteeing that with high probability $u$ is close to the top-eigenvector of $P\\mathbb{E}[xx^{\\top}]P$.\n    * To the best of our knowledge, **this is the first work to apply deflation in a DP context**. We do this by introducing the stronger but sufficient concept of stochastic ePCA oracle. \n    * We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)\n    \n2. Having identified what is sufficient for the problem, we next construct a DP algorithm that implements this stronger oracle. Starting from Liu et. al.’s DP-PCA (which is itself a modification of the classical Oja’s method), we introduce the following important modifications\n    * Naively feeding $Pxx^{\\top}P^{\\top}$ into DP-PCA fails because the gaussian noise added in PRIVMEAN (for DP) pushes the iterate outside of $\\mathrm{Im}(P)$. Consequently successive outputs would not be orthogonal and deflation breaks. To fix this, we explicitly re-project back onto $\\mathrm{Im}(P)$ (Step 5 of ModifiedDP‑PCA). This ensures every eigenvector remains in the correct subspace, preserving orthogonality.\n    * Even with the projection, as mentioned above, existing analyses only shows closeness to the top eigenvector of $\\mathrm{E}[Pxx^{\\top}P^{\\top}]$, not to $P\\mathrm{E}[xx^{\\top}]P^{\\top}$. To solve this,\n        1. we first reduce the private updates of modified DP-PCA to a non-private (projected and noisy) Oja’s algorithm on $P\\tilde{A}P^{\\top}$ where $\\tilde{A}$ is a \"noisy\" version of $xx^{\\top}$  (Theorem 9) and \n        2. prove a new utility bound for this projected and noisy version of Oja’s algorithm showing that its output indeed aligns with the top eigenvector of $P\\mathrm{E}[xx^{\\top}]P^{\\top}$ (Theorem 8).\n\n    * Lastly we had to control the error terms resulting from a single call of ModifiedDP-PCA. To the best of our knowledge Jambulapati et al considered 1-PCA oracles whose utility guarantees do not contain constants affected by the projection matrix P. The utility guarantee of ModifiedDP-PCA (Theorem 9) however, depends on several constants originating from constraints on the data (see Assumption A). If we replace $\\{ x_i x_i^{\\top}\\}$ the input to ModifiedDP-PCA with $\\{ Px_i x_i^{\\top}P\\}$, we need to control how these constants change. We show that most of the constants will not incur a cumulative error (see Lemma 10, 11 and 13), except for $\\kappa = \\frac{\\lambda_1}{\\lambda_1 - \\lambda_2}$ (= eigengap). The eigengap will indeed incur a cumulative error due to deflation (as at every step i we need to account for how far the top eigenvector of $P\\Sigma P$ is removed from the true ith eigenvector of $\\Sigma$). In Lemma 23, we characterize how to control this error. This might be of independent interest when using 1-PCA algorithms whose utility depends on the eigengap ($\\kappa$) with the deflation method, as it was shown that the eigengap can play an important role in the performance of PCA algorithms.\n3. Lastly we derive an information-theoretic lower bound for differentially private PCA under our setting.\n\nTaken together, these yield the first deflation-based DP-PCA algorithm for $k>1$ with near-optimal utility. Some of the new tools that we introduce e.g. stochastic-ePCA oracles, deflation with stochastic methods, as well as the new Oja’s analyses, may well be of independent interest outside DP.\nApart from this we note that our proof strategy immediately gives us two additional insights:\n1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.\n2. Our proof strategy generalizes beyond ModifiedDP-PCA to any stochastic ePCA oracle, leading to our second algorithm, k-DP-Oja (via the Meta Theorem) but can also be used for non-DP randomized PCA algorithms."}, {"review_id": "w51v0lYyVB", "reviewer": "Reviewer_Ekub", "summary": "The paper tackles differentially-private stochastic k-PCA. It combines a deflation (Algorithm 1 k-DP-PCA) with a new 1-PCA oracle (MODIFIEDDP-PCA). Under a sub-Gaussian data model, they authors prove $(\\epsilon,\\delta)$-DP and show that with only $n = \\tilde{O}(d)$ samples their estimator recovers a $k$-dimensional subspace whose retained variance has near-optimal dependence on $k, n$. An information-theoretic lower bound for the case of the spiked covariance model matches dependence on factors except $k$. The authors further supplement their theoretical results with experiments to show the linear-scaling of the error with data dimension $d$.", "questions": "Please see weaknesses section above.", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "Strengths :\n\nA clear rigorous proof of differential privacy and utility for k-PCA with a nearly tight lower bound and efficient implementation. Nice combination and generalization of the ideas of Jambulapati et al. (2024) and Liu et al (2022). I have been keeping up with the literature and I think the paper is overall well-written and a nice contribution to the privacy and PCA literature.\n\nWeaknesses/Questions : \n\nI don't see any obvious weaknesses apart from the ones the authors acknowledged in Section 6, so I will ask state some questions/suggestions instead.\n\n1. I would appreciate it if, apart from the lower bound, the authors could bring out their contributions over Jambulapati et al. (2024) and Liu et al (2022) and mention novel parts of their analysis, even as a sketch, as compared to these existing analysis.        \n\n2. Line 198-199 : The authors mention that Jambulapati et al's ePCA oracle definition doesn't extend to the stochastic case. However, based on my understanding, Jambulapati et al. do provide bounds for robust k-PCA where $1-\\epsilon$ fraction of the data is drawn iid from some distribution. Therefore, I am a little confused as to what the authors meant with this claim.\n\n3. Regarding dependence on $k$ : Again referencing Jambulapati et al., based on my understanding, for the case of robust heavy-tailed data, they show that in fact a union bound over the $k$ deflation steps is not necessary and a stability result in the first stage implies stability for the subsequent stages due to the nature of the deflation. This helps them save a $k$ factor in the sample complexity. \n\nI am wondering if such a trick would work in the DP case as well? \n\n4. Notion of $k$-PCA : The authors consider energy k-PCA. Another notion of PCA convergence is the correlation k-PCA which measures mis-alignment between estimated and true eigenspaces. I am just wondering if the authors believe that their results provide near-optimal guarantees for such a case as well.", "was_revised": true, "final_justification": "I thank the authors for their detailed explanations. I think my questions have been answered. I trust the authors will incorporate the explanation of challenges in their proof setting in the final revision. I would be happy to increase my score. I think extending Liu et al's work to k-PCA using deflation is an interesting line of work and this paper presents a good contribution.", "rebuttal": "We thank the reviewer for their comments. We will address them in order:\n\n> I would appreciate it if, apart from the lower bound, the authors could bring out their contributions over Jambulapati et al. (2024) and Liu et al (2022) and mention novel parts of their analysis, even as a sketch, as compared to these existing analysis.\n\nOur algorithm indeed combines the DP-PCA method by Liu et al. with the deflation strategy from Jambulapati et al. Algorithmically, our techniques are reminiscient of these methods. However, the main contribution of our work lies in the theoretical arguments showing that this combination indeed leads to a working DP algorithm with a utility guarantee in the stochastic setting.\n\nBelow we outline why this is not a straightforward result and what technical challenges we encountered. \n1. Standard 1-PCA oracles (e.g. Liu et. al. 2021) guarantee that their (randomised) output eigenvector $u$ is close to the top eigenvector of the population covariance $\\mathbb{E}[xx^\\top] = \\Sigma$. In deflation, one sets $P=I-u_1u_1^\\top$ and runs the oracle on the residual data $Px$, hoping to approximate the top eigenvector of the residual covariance $P\\Sigma P^{\\top}$. However, because P itself is not only random but also correlated to the data (due to both the adaptive privacy noise and the randomness in the data used to construct $u_1$), the stochastic 1-PCA oracle only guarantees that $u_2$ is close to the top eigenvector of $\\mathbb{E}[Pxx^tP]$, which is too weak for deflation (deflation needs closeness to the top eigenvector of $P\\,\\mathrm{E}[xx^t]\\,P^\\top$).\nTo avoid this and apply DP to the deflation approach, we introduce the **stochastic ePCA oracle** (Definition 3), which by design (1) inputs a random projector $P$ and (2) outputs a vector $u$ guaranteeing that with high probability $u$ is close to the top-eigenvector of $P\\mathbb{E}[xx^{\\top}]P$.\n    * To the best of our knowledge,this is the first work to apply deflation in a DP context. We do this by introducing the stronger but sufficient concept of stochastic ePCA oracle. \n    * We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)\n    \n2. Having identified what is sufficient for the problem, we next construct a DP algorithm that implements this stronger oracle. Starting from Liu et. al.’s DP-PCA (which is itself a modification of the classical Oja’s method), we introduce the following important modifications\n    * Naively feeding $Pxx^{\\top}P^{\\top}$ into DP-PCA fails because the gaussian noise added in PRIVMEAN (for DP) pushes the iterate outside of $\\mathrm{Im}(P)$. Consequently successive outputs would not be orthogonal and deflation breaks. To fix this, we explicitly re-project back onto $\\mathrm{Im}(P)$ (Step 5 of ModifiedDP‑PCA). This ensures every eigenvector remains in the correct subspace, preserving orthogonality.\n    * Even with the projection, as mentioned above, existing analyses only shows closeness to the top eigenvector of $\\mathrm{E}[Pxx^{\\top}P^{\\top}]$, not to $P\\mathrm{E}[xx^{\\top}]P^{\\top}$. To solve this, \n        1. we first reduce the private updates of modified DP-PCA to a non-private (projected and noisy) Oja’s algorithm on $P\\tilde{A}P^{\\top}$ where $\\tilde{A}$ is a \"noisy\" version of $xx^{\\top}$  (Theorem 9) and \n       2. prove a new utility bound for this projected and noisy version of Oja’s algorithm showing that its output indeed aligns with the top eigenvector of $P\\mathrm{E}[xx^{\\top}]P^{\\top}$ (Theorem 8).\n    * Lastly we had to control the error terms resulting from a single call of ModifiedDP-PCA. To the best of our knowledge Jambulapati et al considered 1-PCA oracles whose utility guarantees do not contain constants affected by the projection matrix P. The utility guarantee of ModifiedDP-PCA (Theorem 9) however, depends on several constants originating from constraints on the data (see Assumption A). If we replace $\\{ x_i x_i^{\\top}\\}$ the input to ModifiedDP-PCA with $\\{ Px_i x_i^{\\top}P\\}$, we need to control how these constants change. We show that most of the constants will not incur a cumulative error (see Lemma 10, 11 and 13), except for $\\kappa = \\frac{\\lambda_1}{\\lambda_1 - \\lambda_2}$ (= eigengap). The eigengap will indeed incur a cumulative error due to deflation (as at every step i we need to account for how far the top eigenvector of $P\\Sigma P$ is removed from the true ith eigenvector of $\\Sigma$). In Lemma 23, we characterize how to control this error. This might be of independent interest when using 1-PCA algorithms whose utility depends on the eigengap ($\\kappa$) with the deflation method, as it was shown that the eigengap can play an important role in the performance of PCA algorithms.\n\nTaken together, these yield the first deflation-based DP-PCA algorithm for $k>1$ with near-optimal utility. Some of the new tools that we introduce e.g. stochastic-ePCA oracles, deflation with stochastic methods, as well as the new Oja’s analyses, may well be of independent interest outside DP.\n\nApart from this we note that our proof strategy immediately gives us two additional insights:\n1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.\n2. Our proof strategy generalizes beyond ModifiedDP-PCA to any stochastic ePCA oracle, leading to our second algorithm, k-DP-Oja (via the Meta Theorem) but can also be used for non-DP randomised PCA algorithms.\n\n> Line 198-199 : The authors mention that Jambulapati et al's ePCA oracle definition doesn't extend to the stochastic case.\n\nWe thank the reviewer for bringing this to our attention and we were indeed a bit unclear. To the best of our understanding Jambulapati et al show that 1pca robust algorithms need the input dataset to contain a stable set and this stability is preserved under projections. While this stability condition i) is sufficient for robust-PCA ii) is preserved under projection and iii) (on a high level) leads to not having to worry about the dependence between $P $and $x_i$, it is unclear wether the same technique can be applied in our stochastic DP setting. We will make this clearer in our updated draft.\n\n> Regarding dependence on k:\n\nJambulapati et al. show that by reusing the whole matrix $A = \\sum_{i=1}^n a_i a_i^{\\top}$ at every deflation step, we can obtain a bound independent of $k$ (without privacy). The first immediate observation is that as we protect the privacy of each $a_i a_i^{\\top}$, reusing them would require adaptive composition resulting in a factor of $\\sqrt{k}$. Thus, even if we were able to use their proof, using the deflation method with privacy would incur an inevitable $\\sqrt{k}$ factor. Our paper incurs a factor of $k$ due to the fact that our analysis requires the projections $P_{i-1}$ at step $i$ of the deflation method to be independent of the matrices we pass at step $i$. To achieve this we split the data into $k$ equal subsets, resulting in the factor $k$ in our utility guarantee.\nSecondly, as mentioned in the answer above, their notion of stable set is uniquely suitable for the robust-PCA problem and it is not clear whether doing our DP-PCA algorithm as the inner sub-routine is also amenable to the stable set property. We think it is interesting future work to see whether we can get the $\\sqrt(k)$ factor using the techniques from Jambulapati et. al. or using our analysis but with “slightly” correlated data.\n\n> Another notion of PCA convergence is the correlation k-PCA : \n\nOur notion of utility is denoted as energy PCA (ePCA) in Jambulapati et al, further they denote correlation k-PCA with cPCA (correlation PCA) and indeed show that any ePCA guarantee can be converted into a cPCA guarantee (see Lemma 12 in Jambulapati et al). However, to the best of our knowledge, a correlation k-PCA guarantee only gives an energy k-PCA in the case of $k=1$."}, {"review_id": "iHd6kU6gL3", "reviewer": "Reviewer_cGF1", "summary": "The paper consider differentialy private $k$-PCA, where the goal is to privately estimate the $k$ leading eigenvectors of the covariance matrix of data. The method and analysis is tailored to the stochastic setting, where the data vectors are drawn from a given distribution. The paper makes improvements over the prior works in essentially two ways: first, it improves the baseline method and analysis by Liu et al. (2022) which is for eastimating the leading eigenvectors of the covariance matrix, and second, the paper applies the deflation techniques presented by Jalumbati et al. (2024) to apply the single vector estimator $k$ times and carrying out deflation. Numerical comparisons to the baseline method by Liu et al. (2022) and also to the Analyze Gauss (Dwork et al., 2014) which works in the data-deterministic setting and where the whole covariance matrix is pertubed verify the effectiveness of the proposed method.", "questions": "- Can you comments on how the deflation method would compare to block iteration methods such as the noisy power method (Hardt and Price, 2014, Balcan et al., 2016) ? Both theoretically and numerically? As that is fundamentally a different approach (deflation vs. block iteration), I think it would be important to mention that approach.\n\n- Why did you not consider other baselines than Analyze Gauss and the method by Liu et al. ?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n- Improvement of the single vector method by Liu et al. (2022)\n\n- Novel analysis based on a novel analysis of the non-private method by Jain et al. (2016)\n\n- Clear novelty: method to estimate $k$ leading vectors, enabled by the deflation (Jalumbati, 2024)\n\n- The paper is very well written, it is nice that there are examples of data distributions that satisfy the assumptions of the analysis vs. exaples that do not satisfy.\n\n\nWeaknesses:\n\n- The experimental section is limited, as there are two examples with synthetic data and in both cases $k=2$. Comparisons with some real-world data with larger $k$ would strengthen the experimental section.\n\n- The selection of baseline methods is limited. The method by [Cai et al. (2024)](https://arxiv.org/pdf/2401.03820) is not considered in the baselines. But most importantly, the noisy power iteration is not considered at all. There are recent works, e.g.\n\n[Nicolas, J., Sabater, C., Maouche, M., Mokhtar, S. B., & Coates, M. (2024). Differentially private and decentralized randomized power method.](https://arxiv.org/pdf/2411.01931)\n\nthat are block iterations and consider computing simultaneously the leading $k$-eigensubspace for the covariance matrix. There is also the analysis of \n\n[Balcan, M. F., Du, S. S., Wang, Y., & Yu, A. W. An improved gap-dependency analysis of the noisy power method. In Conference on Learning Theory 2016](http://proceedings.mlr.press/v49/balcan16a.pdf)\n\nwhich gives an error analysis for the noisy power method, that could be directly compared to the results presented here.\n\nThe existing methods and analyses for the noisy power iteration, to the best of my knowledge, are for the data-deterministic setting. However, you could compare to that method using similar modifications that you make for the Analyze Gauss.", "was_revised": true, "final_justification": "This is a well-written and solid paper making clear contributions to DP PCA in the stochastic setting, including improvements over Liu et al. (2022) via application of deflation techniques to estimate multiple leading eigenvectors. The rebuttal addressed concerns about baselines by providing additional experiments with larger $k$ and by including comparisons to noisy power methods, supporting the claimed advantages of the proposed method. While the experimental section remains limited in scope (authors promise more experiments for the final version), the theoretical contributions seem sound.", "rebuttal": "We thank the reviewer for their comments. We will address them in order:\n\n> The experimental section is limited:\n\nThe primary focus of the paper was on theoretical results for the problem of stochastic k-DP-PCA for $k >1$. However, we do appreciate the reviewers' concerns and during the rebuttal, we repeated our spiked data experiments on larger $d$ and $k$ as well as on different baselines and report the results below. We observe the same trends as highlighted in the paper. We show one of the experiments in the ASCII plot below and report the rest in tables.\n\n```\n                            Mean Distance vs. Sample Size (k=10, d=450)                   \n    ┌──────────────────────────────────────────────────────────────────────────┐\n0.98┤ •• DP-Gauss-1       ♰                    ♰                               │\n    │ ♰♰ DP-Gauss-2                                                      ♰     │\n0.82┤ pp DP-Power-Method                                                       │\n    │ cc k-DP-Ojas                                                             │\n    │ ss k-DP-PCA                           c                                  │\n0.66┤                                                                          │\n    │                                                                          │\n0.50┤                                                                          │\n    │                    p                                                     │\n0.34┤                   •                                             c        │\n    │                                                                          │\n    │                                                                          │\n0.18┤    s                                   •p                                │\n    │                 s                                                •p      │\n0.03┤                                      s                         s         │\n    └┬─────────────────┬──────────────────┬─────────────────┬─────────────────┬┘\n  1995.0            12746.2            23497.5           34248.8        45000.0 \ndistance                            sample size n                               \n\n```\n\n|    Algorithm    |  $n$  |  $d$  |  $k$  |  distance  |\n|-----------------|-------|-------|-------|------------|\n|   DP-Gauss-1    | 20000 |  200  |   5   |   0.043    |\n|   DP-Gauss-2    | 20000 |  200  |   5   |   0.138    |\n| DP-Power-Method | 20000 |  200  |   5   |   0.068    |\n|    k-DP-Ojas    | 20000 |  200  |   5   |    0.1     |\n|   **k-DP-PCA**      | 20000 |  200  |   5   |   0.002    |\n|-----------------|-------|-------|-------|------------|\n|   DP-Gauss-1    | 20000 |  200  |  15   |   0.104    |\n|   DP-Gauss-2    | 20000 |  200  |  15   |   0.885    |\n| DP-Power-Method | 20000 |  200  |  15   |   0.246    |\n|    k-DP-Ojas    | 20000 |  200  |  15   |   0.666    |\n|    **k-DP-PCA**      | 20000 |  200  |  15   |   0.003    |\n|-----------------|-------|-------|-------|------------|\n|   DP-Gauss-1    | 40000 |  450  |  15   |   0.072    |\n|   DP-Gauss-2    | 40000 |  450  |  15   |   0.933    |\n| DP-Power-Method | 40000 |  450  |  15   |   0.099    |\n|    k-DP-Ojas    | 40000 |  450  |  15   |    0.57    |\n|    **k-DP-PCA**      | 40000 |  450  |  15   |    0.02    |\n\n> The selection of baseline methods is limited (why did you not consider Cai et al, noisy power method and other baselines than Analyze Gauss)\n\n* Cai et al. :  We note that the DP guarantees of Cai et al  are conditional on the data coming from a spiked covariance distribution. So, **if the data comes from a different distribution, Cai. et. al.'s algorithm is non-private**. Our algorithm is private for any dataset. Nevertheless, for spiked covariance data our algorithm performs similarly to Cai et al. (see table above)\n    \n* Noisy power method: The original noisy power method paper (Hardt et al.) only gives DP guarantees in terms of a change in a single entry by 1 or a spectral change of norm 1. Whereas our algorithm gives DP guarantees for an arbitrarily large change of an entire row, which is a strictly stronger DP guarantee. When we converted their adjacency notion to ours via clipping and increasing the noise with a multiplicative factor (similarly to what we did for Analyze Gauss) their utility guarantee ended up being worse than Analyze Gauss, which is why we do not add it to the baseline.\n\n* Improved noisy power method: We do thank the reviewer for bringing the paper by Nicolas et al to our attention. We were not aware of this paper and plan to mention the Nicoals et al. as well as Balcan et al. in the final version of our paper. They give a stronger privacy guarantee than the original noisy power method paper, by defining the adjacency as $A' = A + C$, for $\\sqrt{\\sum_{i=1}^n \\| C_{i,:} \\|_1^2} \\leq 1$. If we convert this to our setting (similarly to what we did for Analyze Gauss as suggested by the reviewer), by defining $A' = A + a a^{\\top}$, then $C = a a^{\\top}$ and the ith row of $C$ is equal to $| a_i | || a ||_1$ which results in the requirement that $|| a ||_2 || a ||_1 \\leq 1$. We know $|| a ||_1 > || a||_2$ so simply clipping the matrices to $|| a ||_2 \\leq \\beta$ and then scaling accordingly, we add even less noise than we need to. Nevertheless, this makes their algorithm comparable to AnalyzeGauss in terms of utility guarantees with respect to k and d. We conducted experiments with their algorithm and reported it above. As the results show, our method outperforms them.\n\n> Can you comment on how the deflation method would compare to block iteration methods such as the noisy power method \n\nThe deflation method is not inherently a DP method so we cannot directly compare it to the noisy power method. But we can compare block iteration methods such as the noisy power method to k-DP-PCA and k-DP-Ojas\n1. Theoretically: \n    * **different notion of neighboring (for DP)**: as mentioned above the noisy power method considers a different notion of neighboring. If we modify it to comply with our notion this would lead to an additional $\\sqrt{d}$ factor in the utility guarantee, and therefore would make their utility guarantee scale by $\\sqrt{d}$ worse than k-DP-PCA and k-DP-Ojas\n    * **The privacy noise of k-DP-PCA adapts to the randomness in the data**: one problem we wanted to solve with our algorithm is that many DP algorithms introduce excessive noise for DP even when the intrinsic randomness within the data samples $A_i$ is small. Modified DP-PCA adapts to the data and hence allows us to add very little noise in data regimes such as the spiked data model. \n2. Experimentally: The error of the original noisy power methods algorithm scales considerably worse than Analyze Gauss with respect to growing dimension d. The newer analysis of Nicolas et al. and Balcan et al. show that we can add less noise, which leads to an error scaling similar to Analyze Gauss for the neighboring definition we are considering."}]

Author rebuttal:

Meta-review: Overall, the reviewers agree that this is a nice result on DP k-PCA problem, extending the work of Liu et al. [2022a] from k=1 to general k, and leveraging various techniques including the reduction in Jambulapati et al. [2024]. The concerns about the novelty of the paper compared with Liu et al. [20222a] and Jambulapati et al. [2024] were addressed in the rebuttal, but the authors are expected to add these discussions to the main paper. Also, the additional experimental results provided in the rebuttal are expected to be added to the camera ready.
Decision: Accept (poster)