acceptodds
Under review as a conference paper at ICLR 2027

Gap-Free Streaming PCA Beyond Rank-One Updates: Near-Optimal Rates and Applications to Differential Privacy

46 views

Abstract

Streaming principal component analysis (PCA) seeks to recover a leading spectral subspace in a single pass over a data stream. We give a new analysis of the ubiquitous Oja’s algorithm (Oja, 1982) for the most general, gap-free variant of this problem, where no eigengap assumptions are made on the underlying mean matrix, complemented by a nearly matching lower bound. Prior works achieving near-optimal rates for streaming PCA either required gap assumptions (Jain et al., 2016; Huang et al., 2021) or were limited to rank-one updates (Allen-Zhu and Li, 2017; Liang, 2023). Our proof only uses a second-moment bound on the individual stochastic updates, bypassing the almost-sure bounds needed by prior near-optimal analyses and the analogous offline matrix Bernstein bound. We also extend our result to a Rayleigh quotient notion of approximate PCA, addressing an open question of Jain et al. (2016). As our main application, we give gap-free differentially private PCA guarantees for sub-Gaussian data, settling Conjecture 1.1 of Brown (2026) up to logarithmic factors.

Primary area:
optimization
Keywords:
Principal component analysis, Oja’s algorithm, streaming algorithms, gap-free analysis, energy PCA, differential privacy, high-dimensional statistics

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_nAfVOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper develops a new analysis of Oja's algorithm for top-one streaming PCA with i.i.d., arbitrary-rank matrix updates, a positive-semidefinite population mean, and only a matrix second-moment bound. Without assuming a leading eigengap, it obtains a cPCA sample complexity of O~(V/(λ12γ2Δ)+1/γ)\widetilde{O}(V/(\lambda_1^2\gamma^2\Delta)+1/\gamma) at constant confidence, together with a lower bound matching the leading statistical term. A shared-sketch aggregation procedure improves the confidence dependence. A refined multiscale analysis also establishes the ePCA rate O~(V/(λ12α2)+1/α)\widetilde{O}(V/(\lambda_1^2\alpha^2)+1/\alpha). Finally, these tools yield gap-free private PCA guarantees for mean-zero sub-Gaussian data with public scale parameters. In the Gaussian setting with known λ1\lambda_1, the private ePCA bound becomes O~(d/α2+d/(εα))\widetilde{O}(d/\alpha^2+d/(\varepsilon\alpha)).

Critical strengths
  1. A substantive theoretical gap is addressed. Theorem 1 permits general, potentially nonsymmetric updates under Model 1. Theorem 4 supports the optimality of the leading dependence on V,λ1,γ,V,\lambda_1,\gamma, and Δ\Delta, up to logarithmic factors.

  2. The proof techniques are useful beyond a single rate statement. Trace control of the stochastic matrix products and shared-sketch aggregation address difficulties that arise when several top directions are equally valid. The ePCA analysis retains spectral information across thresholds and improves on the lossy black-box cPCA-to-ePCA conversion.

  3. The private application gives the general-update theory a concrete use. The coupling between the clipped private iteration and Gaussian matrix perturbations produces a meaningful gap-free result. The manuscript states the public-scale assumptions and separates distribution-free privacy from model-dependent utility.

Critical weaknesses
  1. The regime interpretation following Equation (6) is not supported by the displayed rates. The relative size of the privacy term decreases as γ\gamma or Δ\Delta decreases, with other parameters fixed. This affects the explanation of the claimed advantage over AnalyzeGauss, although it does not by itself invalidate the sample-complexity theorems.

  2. The practical cost and implementation of the private experiments need clarification. The full-batch design is acknowledged, but the paper gives little information about implementing it at d=5000d=5000 and nn up to 10810^8. Sample complexity alone does not establish a computational advantage.

  3. The empirical settings are only loosely connected to the guarantees. The choices R=3R=3, T=500T=500, and the grid-searched step sizes are not accompanied by sensitivity results or a sufficiently explicit tuning protocol. Figure 2 includes uncertainty intervals, but its 20-trial results establish neither uniform superiority nor uniformly high success probability. The experiments also do not directly illustrate exact top-eigenvalue multiplicity.

Questions for authors
  1. Interpretation of the comparison in Equation (6). In Section 4.2, lines 421--423, smaller γ,Δ\gamma,\Delta are described as favoring the improvement over AnalyzeGauss. However, the ratio of its privacy term to the shared statistical term is
{d/(\gamma^2\Delta)} =\frac{\sqrt d\,\gamma\sqrt{\Delta}}{\varepsilon}.$$ At the displayed-rate level, decreasing $\gamma$ or $\Delta$ makes the shared term more dominant. Could the authors reconcile this with lines 421--423 and 468--474, distinguishing an empirical observation from a prediction of Equation (6)? Hidden constants and logarithms may affect the crossover, but the stated inference from the displayed polynomial terms appears reversed. 2. Actual implementation and computational cost. How were the Section 4.2 experiments implemented at the reported scale? A literal execution of Algorithm 2 performs $RT=1500$ dataset traversals; processing the runs together could reduce physical scans. Please describe the actual data-access strategy and give representative runtime and peak-memory figures for both methods. If covariance caching or a Gaussian/Wishart simulator was used, please explain whether it implements the adaptive clipping exactly or approximates the unclipped process, and how that experiment relates to Algorithm 2's guarantee. A pointer to the corresponding experimental code would help. 3. Practical parameters and noise calibration. How were $R=3$ and $T=500$ selected, and how sensitive are the results to modest changes in these values? A small sensitivity check at fixed $(\varepsilon,\delta)$, recalibrating the noise through Lemma 13, would be informative. Please also specify whether the noise uses $\delta$ directly or the smaller $\delta_*$ in Equation (33). The larger sufficient constants in Appendix G do not make the experimental choices invalid, but these choices should be clearly distinguished from settings certified by the utility theorem, especially given the low success rates at $\gamma=0.05$ in Figure 2. 4. Tuning protocol and scope of the privacy claim. Were the step sizes selected on independent synthetic trials and then fixed before evaluation? Figure 1 mentions fresh paired trials; please make the protocol equally explicit for Figure 2, including whether tuning used the known population eigenspace and whether settings varied with $n$ or $\gamma$. Tuning on independent public synthetic data is reasonable, but selection using the private evaluation dataset would require additional privacy accounting. Since $\nu$ and $\lambda_1$ are explicitly public in the theory, please also distinguish this oracle-scale evaluation from deployment when those quantities are unavailable. 5. A focused check of the gap-free setting. Section 4.1 already uses dense, generally nonsymmetric Gaussian matrix updates, which is appropriate for the general-update claim. Could the authors add a small controlled example with exactly repeated leading eigenvalues, evaluating leakage outside the permitted spectral subspace rather than alignment with one arbitrarily chosen eigenvector? This would illustrate the distinction between gap-free cPCA and conventional leading-eigenvector recovery directly. I regard this as a useful validation of the existing claim, not a request for a broad new benchmark suite or a prerequisite for acceptance. 6. The results concern top-one PCA. The optimality statements match leading statistical terms rather than every logarithmic or additive term. The private application is multi-pass and assumes public scale information; its relationship to Brown's conjecture should retain the known-$\lambda_1$ qualification stated in Remark 1. The experiments are illustrative Gaussian studies and do not establish a general runtime advantage. Finite-variance heavy-tailed updates are permitted by Model 1 but not explored experimentally. These boundaries are compatible with a valuable theoretical contribution.
1 comment

We thank the reviewer for the detailed comments and for recognizing the theoretical contributions of our work, particularly the general-update analysis, the nearly matching lower bound, and the multiscale ePCA guarantee. We address the questions below. We hope that our response clarifies your concerns, and elevates your opinion of our paper.

1. Interpretation of Equation (6): Please see our general comment.

2. Computational cost and implementation: We thank the reviewer for suggesting a more explicit computational comparison. We note that all code for our experiments is provided in the supplementary material. Algorithm 2 requires O(ndR2T)O(ndR^2 T) arithmetic operations and O(dR2)O(dR^2) auxiliary memory, where Theorem 2 chooses

T=O\left(\frac{\log(dR/\Delta)}{\gamma}\right).$$ The $R$ runs can be processed jointly in $T$ dataset passes. Thus, for constant accuracy and failure probability parameters, the arithmetic complexity is $\widetilde O(nd)$, compared with $O(nd^2)$ for explicitly constructing the empirical covariance in AnalyzeGauss. Our algorithm also avoids storing the full $dxd$ covariance matrix. We additionally benchmarked both methods at $d=5000, R = 3$, and $T = 500$ on an AMD EPYC CPU with one BLAS thread. At $n=10000$, Algorithm 2 took $63.96$ seconds with $1074$ MiB peak process memory, compared with $8.79$ seconds and $1464$ MiB for AnalyzeGauss. These smaller-sample measurements illustrate the computational tradeoff associated with multiple full-batch iterations and an improved convergence rate. The implementation computes the adaptive clipped queries directly from the observations, including both clipping operations and Gaussian perturbations, as specified in Algorithm 2. We will include the computational bounds and benchmarking details in the revision. **3. Experimental parameters and privacy calibration**: For Figure 2, we use $R=3, T=500$, and $$\eta_t=\frac{32}{100+t}, \qquad \tau=\frac18\sqrt{\frac{\Delta}{R}}.$$ We picked $R=3$ since it gives a majority for aggregation without huge private queries. As for $T$, we sweep over ${100,250,500,1000}$, and we found $500$ gives the most success for Oja’s method. The clipping thresholds $R_1, R_2$ are chosen according to Equation (32), with $\nu = \lambda_1 = 1$ and $\zeta = 0.1$. The Gaussian noise is calibrated according to Lemma 13, $$\sigma^2= \frac{12RT R_1R_2}{n^2\varepsilon^2} \log\frac1\delta,$$ which guarantees $(\varepsilon, \delta)$-DP. The smaller $\delta_*$ in Equation (33) is used in the utility analysis to control adaptive clipping events and is not required for the privacy guarantee itself. The experimental parameters were selected independently of the sufficient parameter choices used in the proof of Theorem 2. We will clarify this distinction and the noise calibration in the revised manuscript. **4. Hyperparameter tuning and experimental evaluation**: The learning rates were selected using independent synthetic pilot trials and fixed before the reported evaluations. In particular, Figure 2 uses the same learning-rate schedule across all sample sizes and both values of $\gamma$. The known population covariance was used to evaluate cPCA error in the synthetic experiments, and tuning did not use the private evaluation samples. We will clarify this in the revision. The experiments are intended to illustrate our theoretical guarantees. Figure 2 reports mean errors and empirical success rates with confidence intervals, rather than claiming uniform superiority across all parameter settings. **5. Exact leading-eigenvalue multiplicity**: We thank the reviewer for this helpful suggestion. We have conducted an additional controlled experiment with exactly repeated leading eigenvalues, $\lambda_1=\lambda_2=\lambda_3=1$, and the remaining eigenvalues drawn from $\operatorname{Unif}(0,0.95)$. We use the same setup as in Section 4.1. Over 100 independent trials at $d = 50$, $\Delta$ decreases from approximately $0.126$ at $n=200$ to $0.0031$ at $n=8000$. This directly illustrates gap-free convergence in the presence of exact leading-eigenvalue multiplicity. We will include this experiment in the revision. **6. Public covariance scale and scope of the results**: Please see our general comment.
Reviewer_y6eAOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper gives a gap-free analysis of Oja’s algorithm for i.i.d. matrix updates with PSD mean and bounded matrix variance, without rank, symmetry, or almost-sure norm assumptions on individual updates. It obtains cPCA sample complexity O~(V/(λ12γ2Δ)+1/γ)\widetilde O(V/(\lambda_1^2\gamma^2\Delta)+1/\gamma), complemented by a lower bound matching the leading term. A refined analysis gives the near-optimal α−2\alpha^{-2} dependence for ePCA. The paper also applies these results to differentially private PCA for sub-Gaussian data. For Gaussian data with publicly known λ1\lambda_1, the ePCA sample complexity is O~(d/α2+d/(εα))\widetilde O(d/\alpha^2+d/(\varepsilon\alpha)).

Critical strengths

I think the main contribution is Lemma 2 and the resulting analysis under Model 1. The proof uses weak majorization to bound E∥Bt∥F2\mathbb E\|B_t\|_F^2 in terms of ∥Ct∥F2\|C_t\|_F^2, using only the two matrix variance bounds. Together with EBt=Ct\mathbb E B_t=C_t, this gives a bound on E∥Bt−Ct∥F2\mathbb E\|B_t-C_t\|_F^2. This leads to the near-optimal gap-free guarantee for general updates, without the almost-sure norm bound required in JJKNS16 (COLT 2016). I found this proof quite nice, the argument is short, and it handles updates that are neither rank-one nor symmetric.

I also like the ePCA analysis. Setting γ=Δ=α/2\gamma=\Delta=\alpha/2 in the cPCA guarantee would give an α−3\alpha^{-3} sample bound. Lemma 9 gets the α−2\alpha^{-2} dependence by keeping track of how the noise from each update is reduced by the subsequent iterations, separately for each spectral threshold. This is the additional argument needed beyond the integral identity in Proposition 2. It addresses the Rayleigh-quotient question in JJKNS16 and gives the private ePCA application a better dependence on α\alpha as well.

Critical weaknesses

My main reservation is the known-scale assumption in the private application. The result assumes publicly known λ1\lambda_1 and ν\nu, and the authors already note that privately estimating λ1\lambda_1 remains open. What is the main obstacle to removing the assumption that λ1\lambda_1 is publicly known while keeping the sample complexity in Theorem 3?

The comparison with LKJO22 (NeurIPS 2022) could also say more about computation. Algorithm 2 uses multiple full-batch passes, while LKJO22 is single-pass. The paper explains this difference, but only gives the sample bounds in the main theorem statements. Reporting the number of passes and total running time would make the comparison more useful maybe?

Questions for authors

Could the authors explicitly state the number of passes Algorithm 2 requires to achieve the guarantees in Theorems 2 and 3, and include this in the comparison with LKJO22? In particular, I would like to understand the runtime cost of using full-batch iterations to improve the dependence on γ\gamma.

2 comments

We thank the reviewer for the positive assessment and thoughtful discussion of our theoretical contributions, particularly Lemmas 2 and 9. We also view the relative simplicity of our proof strategy to be a significant bonus of our theoretical results.

1. Removing the public-scale assumption: Please see our general comment.

2. Computational cost and number of passes: We thank the reviewer for this comment. Algorithm 2 requires O(ndR2T)O(ndR^2T) arithmetic operations and (OdR2)(OdR^2) auxiliary memory, where Theorem 2 chooses

T=O\left(\frac{\log(dR/\Delta)}{\gamma}\right).$$ The $R$ runs can be processed jointly, requiring $T$ passes over the dataset. Thus, for constant accuracy and failure probability parameters, the runtime is $\widetilde O(nd)$. For the ePCA guarantee in Theorem 3, we take $R=1$ and $$T=O\left(\frac{\log(d/\alpha)}{\alpha}\right).$$ Our use of full-batch iterations improves the sample-complexity dependence on $\gamma$, but you are correct that our algorithm requires multiple passes compared with the single-pass algorithm of Liu et al. (2022). Obtaining a single-pass algorithm with the improved sample complexity is an interesting open question that we will mention in the revision. We will also make these computational bounds and pass counts explicit in the revision.

Thanks for the response! I think you have answered my main questions. Just a small suggestion: perhaps you could mention the result from Liu et al. (2022) in the next version, and briefly clarify how the public ν\nu assumption works for general sub-Gaussian data. Overall, I still think the main theoretical results are strong, especially the gap-free analysis for general matrix updates. I will keep my rating at 4.

Reviewer_K6Q5OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper analyzes Oja’s algorithm for gap-free streaming PCA with unrestricted-rank, potentially nonsymmetric updates under only a matrix second-moment bound. It establishes nearly matching upper and lower sample-complexity bounds, extends the analysis to the Rayleigh-quotient objective, and develops confidence amplification that accommodates nonunique leading eigenspaces. It also applies these results to differentially private PCA with public covariance-scale parameters and evaluates the algorithms on synthetic Gaussian problems.

Critical strengths

Overall, the paper strengths in my opinion are as follows,

  • Substantive generalization of streaming-PCA theory. Theorem 1 combines gap-free guarantees, unrestricted-rank updates, and second-moment assumptions, supported by a nontrivial matrix-product argument rather than a change to the underlying algorithm.
  • Sharp guarantees with meaningful extensions. The lower bounds support the principal parameter dependence, while the energy-PCA analysis addresses the direct Rayleigh-quotient question explicitly raised by Jain et al.
  • Technically careful privacy application; through Theorems 2 & 3 they translate the general-update analysis into useful gap-free private-PCA rates, with the coupling argument handling adaptive subspaces and full-batch reuse explicitly.
Critical weaknesses

However, I noticed several weaknesses within the paper,

  • The conjecture-resolution claim is overstated. Brown’s original Conjecture 1.1 supplies samples from an unknown covariance without public �0��0�, whereas Theorem 3 requires this information and the manuscript leaves its private estimation open, which the authors note. However, the result therefore establishes a known-scale version, which should qualify the abstract’s claim to settle the conjecture.
  • Empirical validation is narrow and its computational cost is unclear. The experiments use Gaussian data, one spectral family, and grid-searched step sizes, without testing heavy-tailed updates or clearly separating tuning from evaluation.
  • The experimental rate interpretation is inconsistent with equation (6). AnalyzeGauss’s privacy-to-statistical sample-complexity ratio is �1��1�, so decreasing �2��2� or �3��3� makes the common statistical term more dominant. Consequently, equation (6) does not seem to justify the claimed greater relative advantage at smaller �4��4�.
Questions for authors

I would appreciate if the authors could answer the following,

  • Can you supply a private scale-estimation reduction with its sample and privacy costs, or explicitly restrict the conjecture-resolution claim to publicly known �0��0�
  • Were hyperparameters selected on independent public synthetic trials and frozen before evaluation?
  • How do you reconcile the discussion following equation (6) with the ratio above, and what explains the observed dependence on $(\gamma)$?
2 comments

We thank the reviewer for the positive assessment and constructive suggestions. We hope that our response clarifies your concerns, and raises your opinion of our paper.

1. Publicly known covariance scale: Please see our general comment.

2. Experimental evaluation and hyperparameter selection: We thank the reviewer for the suggestions. As this paper’s contributions are primarily theoretical, our experiments were mainly intended to validate our theoretical guarantees. Section 4.1 uses dense, generally nonsymmetric Gaussian matrix updates, directly demonstrating the general-update setting of Theorem 1. Yes, the learning rates were selected using independent synthetic pilot trials and fixed before the reported evaluations. In particular, Figure 2 uses the same learning rate schedule across all sample sizes and both values of γ\gamma. The known population covariance was used to evaluate cPCA error on synthetic data, and tuning did not use the private evaluation samples. We will clarify the tuning protocol and implementation details in the revision. If the reviewer’s opinion would be affected by any additional experiments, we are happy to provide them.

3. Interpretation of Equation (6) :Please see our general comment.

Reviewer_K6Q5OpenReview ↗

read your comments & rebuttal.

Thanks for your comments and clarifications. Taking everything into account including the rest of the discussion I feel that my current score is satisfactory, therefore I'll keep it as-is.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General Comment

We thank all reviewers for their careful reading and constructive feedback. We summarize the key points from our rebuttal here.

Our main contribution is to close a line of work on streaming PCA. K6Q5 and nAfV’s weaknesses center on our DP-PCA application. While their concerns hold merit and we respond to them in our individual comments, we would like to remind the reviewers that our main contribution is to close a long line of work on streaming PCA, see Table 1.

  • Prior analyses of Oja's algorithm either required an eigengap or only applied to rank-one updates, which are both substantial restrictions. Our results bypass both, and also use only a minimal statistical assumption of a bounded second moment.
  • We strengthen our result by providing both cPCA and ePCA guarantees, a high-probability result, and nearly matching lower bounds. In particular, our sharper ePCA analysis closes an open question of Jain et al. (2016).

The requirement of public scale parameters is without loss of generality. All three reviewers asked about the restrictiveness of knowing λ1\lambda_1 and ν\nu in our DP-PCA application. For Gaussian data, ν=O(λ12)\nu = O(\lambda_1^2), so the question is really about knowing λ1\lambda_1. Further, Liu et al. (2022a, Theorem 6.1 and Appendix E.2) already provided an algorithm to estimate λ1\lambda_1 under DP, with no gap assumption. Adapting this to Model 2 yields a constant-factor estimate of λ1\lambda_1 using O~(dν2ελ1)=O~(dε)\widetilde O\left(\frac{d\nu^2}{\varepsilon\lambda_1}\right) = \widetilde{O}\left(\frac{d}{\varepsilon}\right) additional samples, which is low-order compared to the sample complexity of Theorem 3. The rest of the proof of Theorem 3 goes through after adjusting constant factors in the learning rate. The obstacles from Liu et al. towards closing Brown’s conjecture were (1) removing the gap assumption on the actual PCA method, (2) removing the extra 1/γ1/\sqrt{\gamma} lossiness in the sample complexity, and (3) converting their cPCA result to an ePCA one. Our paper closes all three issues. We apologize for not making this clear, and will explicitly state the eigenvalue approximation result from Liu et al. in our revision.

Interpretation of Equation (6). K6Q5 and nAfV brought up that we mistakenly stated that (6) is favorable for our algorithm in the small γ\gamma, Δ\Delta regime. We apologize and agree with the reviewers; we will remove this sentence from the revision. This does not hinder our interpretations of our empirical findings. Indeed, our interpretation on Lines 468-478 correctly states that by rearranging (6) to express Δ\Delta as a function of nn, the dominant 1/n1/n term is shared by both methods, and our method (which improves only the 1/n21/n^2 term) has smaller benefits as nn increases.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.