acceptodds
Under review as a conference paper at ICLR 2027

Differentially Private Preconditioned Power Iteration Method for Principal Component Analysis that Adapts to the Coherence

Abstract

In Principal Component Analysis (PCA), we are given as input a matrix and an integer , and the goal is to find the top right-singular vectors of . We consider the setting where each row of is the private data of an individual, and we design an -differentially private algorithm whose utility guarantee improves with the coherence of the input matrix. Prior works were either restricted to the case or ensured significantly weaker privacy protections. Our algorithm is based on a preconditioned variant of the power iteration method that is designed to significantly reduce the noise needed to ensure privacy.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
principal component analysis, differential privacy

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_pgF4OpenReview ↗
Rating
4
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies differentially private Principal Component Analysis, proposing a coherence-adaptive algorithm for estimating the top-k right singular subspace under row-level differential privacy. The authors extend previous results from the leading singular vector to the top-k subspace, using a preconditioned and clipped variant of block power iteration to reduce the noise required for privacy. The proposed algorithm provides improved utility for low-coherence inputs.

Critical strengths

The paper provides a clear and well-structured presentation of the problem and the relevant prior work, making it easy to understand the motivation and contributions. The proposed techniques are clearly explained and appear technically sound.

Critical weaknesses

I find the separate related work section somewhat redundant, as the introduction already provides a comprehensive overview of the relevant literature. I believe the paper would benefit more from using this space to provide a more detailed technical analysis or to discuss potential directions for future research.

Questions for authors

First of all, the footnotes at the bottom of page 2 are excessively long and somewhat disrupt the flow of the paper. I suggest shortening them or incorporating the relevant details into the main text or appendix to improve readability.

Additionally, from the comparison with prior work, it is not entirely clear in which way the proposed algorithm improves upon the rank-k guarantees of Dwork et al. (2014). Could the authors clarify what does small k \sigma_k^2 |U|_\infty^2 mean?

1 comment
AuthorsOpenReview ↗

Author response

We thank the reviewer for their hard work and helpful suggestions.

  1. We have shortened the table notes.
  2. When both guarantees apply, Analyze Gauss gives a sin⁡2\sin^2 error bound of O~(dϵ2Δk2)\widetilde{O}\left(\frac{d}{\epsilon^2\Delta^2_k}\right), whereas our bound is O~(dkσk2Umax⁡2+1ϵ2Δk2)\widetilde{O}\left(\frac{dk\sigma^2_k U^2_{\max}+1}{\epsilon^2\Delta^2_k}\right), where Umax⁡U_{\max} is the coherence parameter. Our bound improves on that rate when O~(kσk2Umax⁡2+1/d)≤1\widetilde{O}\left(k\sigma^2_k U^2_{\max}+1/d\right)\leq1. This is what we meant by small kσk2Umax⁡2k\sigma^2_k U^2_{\max}.
Reviewer_MecpOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies rank-�0��0� PCA under differential privacy for replacement of individual rows with bounded �1��1� norm, seeking accuracy that improves with the input’s coherence. Its method combines privately computed preconditioning, clipped block power iterations and private selection of the clipping radius and iteration count. Under explicit eigengap conditions, it proves squared principal-angle error approximately �2��2�, without requiring coherence or the eigengap as inputs; the contribution is entirely theoretical.

Critical strengths

In my view, here are some strengths of the paper,

  • The paper addresses general rank-�0��0� coherence-adaptive PCA under row-level privacy, extending beyond the leading-vector setting of the closely related Nguyen et al. method. This is a substantive change in scope rather than a direct substitution of scalar quantities by matrices.
  • The preconditioner normalizes contributions within the leading subspace, allowing the analysis to depend on �1��1� rather than �2��2�. The accompanying row-wise clipping analysis and stopped-martingale argument provide substantial technical support for this idea
  • It is appreciated that the analysis charges for the noisy preconditioner, clipped updates and private candidate scores, while reusing the initialization appropriately. Privacy holds on the stated input domain independently of the coherence and eigengap assumptions required for utility
Critical weaknesses

It also has some weakenesses which - in my opinion - are as follows,

  • Section 1.2 claims improvement whenever �0��0�, but this paper uses full-SVD coherence �1��1�, whereas Nguyen et al. use only �2��2�. A localized trailing singular vector can make the new bound worse despite that gap condition, so the comparison requires an additional coherence qualification.
  • Table 1 seems to omits the �3��3� selection-error term present in Theorem 1, which need not be dominated under the stated assumptions. The claim of near-optimality across all spectral-ratio regimes also lacks a matching lower bound and must respect the coherence-independent initialization requirement �4��4�.
  • The algorithm cost is a bit unclear. More concretely, Appendix C requires �5��5� candidate runs and a spectral comparison score involving �6��6�, without an end-to-end computational bound. Its public grid and noise calibration also contain mutually dependent definitions that should be replaced by an explicit construction.
Questions for authors

I would appreciate if the authors could answer the following questions,

  • Can you revise the rank-one comparison using the distinct leading-vector and full-SVD coherence parameters, and state precisely when your guarantee improves on Nguyen et al.?
  • Would it be possible for Table 1 to retain the adaptive-selection error term, and can you identify the precise regime and supporting lower bound for the near-optimality claim?
  • It would be highly appreciated if you could provide a complete, noncircular public parameter calibration and expected or high-probability runtime bounds, including initialization, all candidate runs and score evaluation?
2 comments
AuthorsOpenReview ↗

Author response

We thank the reviewer for their hard work and helpful feedback.

  1. We have revised Section 1.2 to address the difference in coherence parameters.
  2. We have added the missing term to the table. Lower bounds are not the focus of our work but we have added a lower bound to the revision (Section D) to support the optimality of our results for all r=σ22/σ12∈[1/(d+1),1)r=\sigma^2_2/\sigma^2_1\in [1/(d+1),1). In the construction, we can choose e.g. r=1/2r=1/2, then the gap Δ1=σ12−σ22=Θ(n/d)\Delta_1=\sigma^2_1-\sigma^2_2=\Theta(n/d). For n≫d3/2/ϵn\gg d^{3/2}/\epsilon, we have Δ1≫d1/2/ϵ\Delta_1\gg d^{1/2}/\epsilon.
  3. We have revised the hyperparameter search in Section C to provide non-circular parameter choices. We have added the running time analysis to Section C.4.
Reviewer_MecpOpenReview ↗

read your rebuttal

Thanks a lot for the clarifications provided. Taking into consideration the rest of the discussion I feel the current score is reflective. Therefore, I'll keep it as is.

Reviewer_ko4TOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the problem of differentially private PCA when each row of the input matrix represents an individual’s record and has bounded L_2 norm. It proposes a preconditioned and clipped block power method for estimating the top-k right singular subspace. The algorithm combines a private Gaussian initialization with private selection of the clipping radius and iteration count. The main result is a coherence-dependent bound on the squared maximum principal-angle error under an eigengap condition.

Critical strengths
  1. The paper addresses a interesting problem under a reasonable privacy model. Protecting an entire bounded L_2 row is reasonable when each row represents an individual.

  2. The preconditioning idea addresses a important challenge in the rank-k setting. In a direct block power method, the sensitivity can depend on sigma_1, while convergence depends on sigma_k and sigma_{k+1}. The proposed preconditioner approximately whitens the projected data and removes this mismatch.

Critical weaknesses
  1. The comparison with Nguyen et al. needs correction or further justification. Table 1 attributes a gap requirement with (2/3)-power terms to Nguyen et al. However, their Theorem 1.1 states the condition κ>4(KΥϵσ1+K2ϵσ12)\kappa>4\left(\frac{K\Upsilon}{\epsilon\sigma_1}+\frac{K^2}{\epsilon\sigma_1^2}\right), where Υ=max⁡i∣Ui1∣\Upsilon=\max_i|U_{i1}| and KK is logarithmic. Equivalently, this requires Δ1>4Kσ1Υ+4K2ϵ\Delta_1>\frac{4K\sigma_1\Upsilon+4K^2}{\epsilon}. This can be substantially weaker than the condition reported in Table 1.

  2. The rank-one superiority claim does not account for the different coherence parameters. Nguyen et al.’s guarantee depends on the leading left singular vector, through |u_1|_infty, whereas the proposed guarantee depends on |U|_infty, the maximum entry across all left singular vectors. Footnote 3 acknowledges this distinction, but the claim on Page 3 that the new bound is better whenever Δ1<σ12/d\Delta_1<\sigma_1^2/d does not account for it. A matrix can have a diffuse leading singular vector and a highly localized trailing singular vector with a small singular value. In such a case, the earlier bound can be substantially smaller, even when the stated gap relation holds.

  3. The claim of near-optimality is not established by the results presented. The introduction states that the algorithm remains near optimal for all regimes of σk+12/σk2\sigma_{k+1}^2/\sigma_k^2. I could not identify a matching lower bound under the same privacy model, coherence definition, and parameter regime. The improved eigengap dependence is useful, but it does not by itself establish near-optimality.

Questions for authors

See weaknesses

1 comment
AuthorsOpenReview ↗

Author response

We thank the reviewer for their hard work and helpful feedback.

  1. There is a typo in Corollary 1.1 and the table in the prior work of Nguyen et al. In their algorithm and analysis shown in Section B, ϵ\epsilon is the per-iteration privacy parameter whereas in Corollary 1.1 ϵ\epsilon is the overall privacy parameter for the entire algorithm. Letting ϵiter\epsilon_{\mathrm{iter}} and ϵtot=Θ~(ϵiterT)=Θ~(ϵiter/κ)\epsilon_{\mathrm{tot}}=\widetilde{\Theta}(\epsilon_{\mathrm{iter}}\sqrt{T})=\widetilde{\Theta}(\epsilon_{\mathrm{iter}}/\sqrt{\kappa}) denote the per-iteration and overall parameter and Umax⁡=max⁡i∣Ui,1∣U_{\max} = \max_i |U_{i,1}|, their analysis (Lemma B.11) requires Δ1≥Ω~(σ1Umax⁡+1ϵiter)=Ω~(σ1Umax⁡+1ϵtotκ)\Delta_{1}\geq\widetilde{\Omega}\left(\frac{\sigma_{1} U_{\max} +1}{\epsilon_{\mathrm{iter}}}\right)=\widetilde{\Omega}\left(\frac{\sigma_{1} U_{\max}+1}{\epsilon_{\mathrm{tot}}\sqrt{\kappa}}\right) which, after substituting κ=Δ1/σ12\kappa=\Delta_{1}/\sigma^{2}_{1} and rearranging, we obtain the condition stated in our table.
  2. We have revised the comparison in Section 1.2 and changed the coherence parameter to $ \max_i |U_{i,1}|$ in the table entry.
  3. Lower bounds are not the focus of our work but we have added a lower bound to the revision (Section D) to support the optimality of our results for all σ22/σ12∈[1/(d+1),1)\sigma^2_2/\sigma^2_1\in [1/(d+1),1).

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of the revision

We thank the reviewers for their helpful feedback and suggestions. We uploaded a revised pdf that incorporates the reviewers' suggestions. We revised the table and the comparison in Section 1.2. We revised the hyperparameter search in Section C and added a running time analysis to Section C.4. We added a lower bound in Section D to support the optimality of our result. The changes are shown in blue.

Area_Chair_ttuGOpenReview ↗

Reviewer–Author Discussion Period Ending Soon

Dear Reviewers,

With the discussion period coming to a close, I encourage you to revisit the authors’ responses and let us know if you have any further comments.

Thank you for your careful reviews and engagement in the discussion!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.