An Iterative Algorithm for Differentially Private $k$-PCA with Adaptive Noise

We thank the reviewer for their comments. We will address them in order:

The experimental section is limited:

The 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.

                            Mean Distance vs. Sample Size (k=10, d=450)                   
    ┌──────────────────────────────────────────────────────────────────────────┐
0.98┤ •• DP-Gauss-1       ♰                    ♰                               │
    │ ♰♰ DP-Gauss-2                                                      ♰     │
0.82┤ pp DP-Power-Method                                                       │
    │ cc k-DP-Ojas                                                             │
    │ ss k-DP-PCA                           c                                  │
0.66┤                                                                          │
    │                                                                          │
0.50┤                                                                          │
    │                    p                                                     │
0.34┤                   •                                             c        │
    │                                                                          │
    │                                                                          │
0.18┤    s                                   •p                                │
    │                 s                                                •p      │
0.03┤                                      s                         s         │
    └┬─────────────────┬──────────────────┬─────────────────┬─────────────────┬┘
  1995.0            12746.2            23497.5           34248.8        45000.0 
distance                            sample size 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)

• 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)

• 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.

• 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.

Can you comment on how the deflation method would compare to block iteration methods such as the noisy power method

The 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

1. Theoretically:
   • 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
   • 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.
2. 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.

Thank you for the reply, this clarifies. I am still slightly suprised, that the noisy power iteration would not compete with Analyze Gauss. Notice that you don't need to have the same adjacency notion as Hardt et al., you can pick any adjacency notion like change of one row where each step of the noisy power method has the privacy guarantees of a Gaussian mechanism and you get the total privacy guarantees via composition analysis. The privacy analysis is independent of the results by Hardt et al. Anyhow, I trust these results are correct, and I believe the ordering must depend on the data as well.

We thank the reviewer for their comments. We will address them in order:

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.

Our 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.

Below we outline why this is not a straightforward result and what technical challenges we encountered.

1. 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$). To 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$.

   • 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.
   • We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)

2. 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

   • 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.
   • 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,
     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
     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).
   • 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.

Taken 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.

Apart from this we note that our proof strategy immediately gives us two additional insights:

1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.
2. 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.

Line 198-199 : The authors mention that Jambulapati et al's ePCA oracle definition doesn't extend to the stochastic case.

We 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.

Regarding dependence on k:

Jambulapati 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. Secondly, 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.

Another notion of PCA convergence is the correlation k-PCA :

Our 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$.

We thank the reviewer for their comments. We address each of them below:

In the experimental part, only k=2 was set to compare with other algorithms, and the advantages of the algorithm can not be demonstrated.

The 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):

             Mean Distance vs. Sample Size (k=10, d=450)
    ┌────────────────────────────────────────────┐
0.98┤ •• DP-Gauss-1   ♰           ♰              │
0.82┤ ♰♰ DP-Gauss-2                              │
    │ pp k-DP-Ojas                               │
0.66┤ cc k-DP-PCA           p                    │
0.50┤                                            │
    │                                            │
0.34┤             •                        p     │
0.18┤                                            │
    │ c       c                •                 │
0.03┤                     c              c    •  │
    └┬──────────┬──────────┬─────────┬──────────┬┘
  1995.0     12746.2    23497.5   34248.8 45000.0 
distance             sample size n                

"However, for other cases such as sub-Gaussian data we expect them to perform similarly.” This conclusion has not been verified

We also ran our experiments on gaussian-data and observed the same trends.

             Mean Distance vs. Sample Size (k=10, d=200)       
    ┌────────────────────────────────────────────┐
1.00┤ •• DP-Gauss-1                              │
0.86┤ ♰♰ DP-Gauss-2   •  ♰          •   ♰        │
    │ pp k-DP-Ojas                p             p│
0.73┤ cc k-DP-PCA                                │
0.60┤                                            │
    │                                            │
0.46┤                                            │
0.33┤      c                                     │
    │             c                              │
0.19┤                           c             c  │
    └┬──────────┬──────────┬─────────┬──────────┬┘
    100       11325      22550     33775    45000 
distance             sample size n                                        

We 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.

The essence of the paper can be regarded as an expansion of Liu et al. [2022a].

While 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.

Below we outline why this is not a straightforward result and what technical challenges we encountered.

1. 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$). To 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$.

   • 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.
   • We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)

2. 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

   • 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.

   • 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,

     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
     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).

   • 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.

3. Lastly we derive an information-theoretic lower bound for differentially private PCA under our setting.

Taken 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. Apart from this we note that our proof strategy immediately gives us two additional insights:

1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.
2. 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.

We thank the reviewer for their comments. We hope our responses below answers the reviewer's concerns.

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?

While, 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.

However, 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.

“It is not clear there is significant technical novelty or contribution”

We 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.

Below we outline why this is not a straightforward result and what technical challenges we encountered.

1. 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$). To 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$.

   • 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.
   • We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)

2. 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

   • 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.
   • 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,
     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
     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).
   • 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.

3. Lastly we derive an information-theoretic lower bound for differentially private PCA under our setting.

Taken 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.

Apart from this we note that our proof strategy immediately gives us two additional insights:

1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.
2. 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.

You are right about the statistical object $P\Sigma P^t$. At step i, the projection matrix P is fixed from prior data, and the new data batch A is independent. The statistical object for this step is indeed the eigenspace of P\SigmaP^T. The issue is not one of statistical bias, and we will edit the manuscript to ensure this is clear.

The main analytical challenge arises because the utility guarantee of any 1-PCA oracle is a function of its input distribution's properties (see Assumption A). Consequently, the error bound at step i depends on $P_{i-1}$, making that error bound itself a random variable. From the perspective of an analyst proving the final utility guarantee, $P_{i-1}$ is a random variable, and they must account for all randomness up to that point.

First we establish a conditional guarantee for our subroutine ModifiedDP-PCA this is not a given from Liu et al., because of the additional projection at step 5. As mentioned in our previous answer, this required a new utility analysis, specifically we gave a reduction of ModifiedDP-PCA to a projected and noisy version of non-private Oja’s method (Theorem 9). This gives us a utility result for ModifiedDP-PCA where all the parameters in Assumption A are accounted for. While other paths to constructing a stochastic ePCA oracle from existing work might exist, they would still require a similar, non-trivial proof.

Second, having established a reliable subroutine, we then analyze the entire $k$-step algorithm. This requires treating $P$ as a random variable to bound the total accumulated error (Theorem 1). The error bound at step i is a function of the random eigengap of $P_{i-1}\Sigma P_{i-1}^T$. The core of this stage is proving that these intertwined errors do not blow up catastrophically (see specifically Lemma 23, Lemma 10, Lemma 11, Lemma 13). Our analysis provides, to our knowledge, the first such bounds for a stochastic DP deflation method, ensuring the global stability (not just per-iteration) of the final estimate.

In short, our contribution is in navigating these analytical challenges to obtain the first computationally efficient, iterative, deflation-based DP algorithm for stochastic PCA with a noise-adaptive guarantee.

We thank the reviewer for their comments. We address their perceived weaknesses below.

Gap in the k-dependence:

We 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.

Technical contributions and challenges:

Our 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.

Below we outline why this is not a straightforward result and what technical challenges we encountered.

1. 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$). To 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$.

   • 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.
   • We prove that such an oracle with adaptive noise can yield the required adaptive utility bound. (Theorem 3)

2. 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

   • 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.

   • 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,

     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
     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)

   • 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.

3. Lastly we derive an information-theoretic lower bound for differentially private PCA under our setting.

Taken 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.

Apart from this we note that our proof strategy immediately gives us two additional insights:

1. We can swap in different mean/range estimation subroutines and via our Meta Theorem obtain utility guarantees for k>1 DP PCA straight away.
2. 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.

We 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.