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

1.3 Related work

• Prior near-optimal guarantees either assume an eigengap or restrict updates to rank one, while this paper’s scope remains 1-PCA rather than k-PCA.The paper identifies analogous gap-free k-PCA guarantees for k > 1 as an open question.Source: §1 · p. 3, §1.3 · p. 7

1.1 Our results

• Oja’s algorithm achieves a gap-free cPCA guarantee with a nearly matching lower bound for its leading-order rate.The guarantee uses online samples; its second rate term follows from the offline power method in the deterministic setting.Source: §1.1 · pp. 3–4
• The main guarantee requires only a matrix variance bound, but has constant success probability; geometric aggregation improves failure-probability dependence at additional space cost.The aggregated block-matrix method has a polylog(1/ζ) sample-complexity overhead and requires d · polylog(1/ζ) auxiliary space.Source: §1.1 · p. 4
• A multiscale reduction gives an α-ePCA guarantee with a nearly matching lower bound, addressing an open question from [JJK+16].The approach avoids the suboptimal 1/α factor from a black-box cPCA-to-ePCA conversion.Source: §1.1 · p. 4
• For gap-free private PCA, the paper gives an (ε, δ)-DP cPCA guarantee for publicly known ν and λ1 under sub-Gaussianity.For Gaussian data with publicly known λ1 and ν2 = O(λ1), its sample complexity matches ’s conjectured rate up to logarithmic factors.Source: §1.1 · p. 4

1.2 Our techniques

• The proof controls the expected trace using only matrix variance, comparing the random Oja product with its population counterpart.For gap-free probability boosting, independent streams share a Gaussian initialization so their outputs can be geometrically aggregated without directly aggregating potentially orthogonal solutions.Source: §1.2 · pp. 5–6

2.1 Notation

• The preliminaries establish notation and basic tools, including a sign-invariant distance for unit vectors that satisfies the triangle inequality.The distance is used in the subsequent analysis.Source: §2.1 · p. 8

2.2 Main problem

• Streaming cPCA seeks a unit vector with little mass on eigenspaces whose eigenvalues are below (1 − γ)λ1(Σ), avoiding reliance on an eigengap.The formulation addresses the ill-conditioning of leading-eigenvector recovery when leading eigenvalues are equal or nearly equal.Source: §2.2 · p. 8
• Under Model 1, the i.i.d. matrix samples have mean Σ and a matrix-variance bound; the goal is cPCA using a one-pass stream that discards each sample after its update.The streaming algorithm considered is Oja’s algorithm, with low external memory as the goal.Source: §2.2 · p. 9

2.3 Baseline via matrix Bernstein

• In the batch baseline, matrix Bernstein transfers an approximate cPCA of the empirical covariance to the population under Model 2’s almost-sure sample bound.The proposition gives a high-probability guarantee under that strengthened assumption.Source: §2.3 · pp. 9–10

3 Oja’s Algorithm

• A one-step Gaussian projection bound controls the ratio of projected mass to total mass for a nonzero matrix iterate.The proof uses Gaussian anti-concentration for the denominator and chi-squared concentration for the numerator.Source: §3 · pp. 10–11
• The analysis tracks a trace-based potential and bounds the iterate’s mass in the eigenspace below (1 − γ)λ1(Σ), controlling the ratio needed for cPCA.The bounds use independence and a matrix-variance assumption in Model 1.Source: §3 · pp. 11–13
• With an appropriate constant and parameter choices, Oja’s algorithm outputs a (γ, ∆)-cPCA with probability at least 1 − ζ.The stated step-size schedule is η_t = γλ1/(β+t), for an appropriate β.Source: §3 · p. 13

4 PCA Lower Bound

• The lower bound matches the leading-order parameter dependence of Theorem 1 qualitatively, for any choice of V and λ1.The hard instances are stated under Model 1 and are positive semidefinite.Source: §4 · p. 14
• Theorem 2 rules out a (γ, ∆)-cPCA algorithm succeeding with probability at least 2/3 for every fixed λ1, V, γ, and ∆ in its stated ranges, when the sample count is too small.The impossibility still holds when every sample matrix is positive semidefinite.Source: §4 · p. 14
• The constructed pair of sample laws has KL divergence O(γ²λ1²∆/V), yielding the lower-bound scale through two-point testing.The argument uses product distributions and a testing-error bound based on total variation.Source: §4 · pp. 14, 16

5 High-Probability Guarantees

• The confidence-amplification procedure adds only polylogarithmic overhead without worsening dependence on the cPCA parameters γ and ∆.This upgrades Theorem 1’s low-confidence guarantee, whose failure-probability dependence is polynomial in 1/ζ.Source: §5 · p. 16
• Direct geometric aggregation of cPCA outputs fails when the leading eigenvalue has multiplicity, since exact solutions can be orthogonal.Instead, the method aggregates sketches of unnormalized Oja products, using their closeness to a shared population sketch.Source: §5 · p. 16
• A shared Gaussian matrix makes the population center common across independent runs, enabling geometric aggregation to boost the guarantee.The algorithm is online without knowing the horizon and uses O(d log^2(1/ζ)) space by storing only the sketches.Source: §5 · p. 18
• For an appropriate constant, there exist choices of inputs R, τ, and {η_t}_{t≥1} such that Algorithm 2 outputs a (γ, Δ)-cPCA of Σ with probability at least 1 − ζ.Source: §5 · p. 19

6 Energy PCA Guarantees

• Energy PCA requires a unit vector w with w⊤Σw ≥ (1 − α)λ1(Σ), capturing nearly the largest possible variance.The section extends the analysis to this alternative gap-free objective.Source: §6 · p. 20
• A direct cPCA-to-ePCA conversion gives suboptimal sample complexity by a factor of 1/α, so the analysis instead uses a multiscale reduction.The reduction retains threshold-dependent bounds and integrates them before controlling normalization, avoiding a simultaneous union bound over all thresholds.Source: §6 · pp. 20–21
• For each fixed u, the energy-error bound holds with constant probability but need not hold simultaneously across all u.Integrating the bound therefore requires a sharper argument than simply combining the fixed-threshold guarantees.Source: §6 · p. 21
• The section states an Oja energy-PCA guarantee for a decreasing step-size schedule and also gives a matching lower bound up to logarithmic factors.The supplied passages identify the guarantee and lower-bound results, but do not provide their complete sample-complexity expressions.Source: §6 · pp. 22–23

7 Application to Differentially Private PCA

• For i.i.d. sub-Gaussian samples, the application seeks cPCA or ePCA of the covariance while satisfying differential privacy.The privacy guarantee applies regardless of the input dataset, while utility is guaranteed under the stated sub-Gaussian model.Source: §7 · p. 24
• Algorithm 3 clips the dataset and adds Gaussian perturbations to full-batch empirical power-method iterates, without minibatching.The paper reports that avoiding minibatches shaves a roughly γ^-1/2 factor from the final sample complexity.Source: §7 · p. 24

7.2 Utility

• Theorem 5 gives an (ε, δ)-DP algorithm returning a (γ, ∆)-cPCA of Σ with probability at least 1 − ζ under Model 3.The utility analysis couples private updates to Oja updates and transfers the empirical-covariance cPCA guarantee to Σ.Source: §7.2 · pp. 27–28

7.3 Private energy PCA

• Theorem 6 gives a private α-ePCA guarantee, and for Gaussian data with publicly known λ1 its sample complexity matches Brown’s Conjecture 1.1 up to logarithmic factors.The Gaussian specialization uses ν^2 = λ1.Source: §7.3 · pp. 29–30

8.1 Oja’s algorithm

• The Oja experiment uses synthetic streams with nearly tied leading eigenvalues, including the first three population eigenvalues 1, 0.99, and 0.98.The setup uses d = 50 and compares against the empirical covariance’s top principal component, which is an offline baseline rather than a streaming method.Source: §8.1 · pp. 30–31
• Oja’s algorithm with tuned step sizes achieves results comparable to offline empirical PCA while operating in the streaming setting.The comparison uses 100 fresh paired trials; the figure reports cPCA error and the fraction of trials with error at most ∆= 0.1.Source: §8.1 · p. 31, Figure 1 · p. 31

8.2 Private PCA

• The private-PCA experiment varies sample size and γ on synthetic Gaussian samples, using d = 5000 and privacy parameters ε = 1 and δ = 10^-6.It runs 20 trials per sample size and compares Algorithm 3 against AnalyzeGauss, which adds symmetric Gaussian noise to the clipped empirical covariance.Source: §8.2 · pp. 31–32
• Algorithm 3 achieves lower mean cPCA error than AnalyzeGauss under the tested parameters, with a stronger advantage at smaller γ that becomes less drastic for very large n.The paper expects improved performance over AnalyzeGauss mainly when d is moderately large and γ and ∆ are small; at large n, error decay matches AnalyzeGauss.Source: §8.2 · p. 32
• At d = 3000, AnalyzeGauss achieves lower error than Algorithm 3, showing that the observed private-PCA advantage does not hold at every dimension.Source: §8.2 · p. 32

• ChatGPT 5.5 and 5.6 Pro were used to explore approaches for Theorem 1, primarily strategies for proving Lemma 3, while the authors developed the final proof strategy.Source: AI Disclosure · p. 33
• After learning of Conjecture 1.1 in, the authors found a reduction in conversations with ChatGPT 5.6 Pro that extended their cPCA results to ePCA.Source: AI Disclosure · p. 33
• The authors state that they alone wrote the manuscript and take full responsibility for its organization and presentation.Source: AI Disclosure · p. 33

A Deferred Proofs from Section 6

• The proof of Lemma 9 establishes a multiscale cPCA guarantee for Algorithm 1 under Model 1 and step sizes bounded by 1/λ1.Source: A Deferred Proofs from Section 6 · p. 37
• The recurrence proof separates the initial contribution from variance added at each update, divides by Zn, and combines the bounds with Lemma 3.It takes a trace against Pu and uses the Model 1 variance bound.Source: A Deferred Proofs from Section 6 · p. 37
• Lemma 15 controls the normalized output by bounding the numerator and denominator using Bn, then applying Gaussian quadratic-form bounds after conditioning on Bn.The stated probability is at least 3/4 when qn is sufficiently small.Source: A Deferred Proofs from Section 6 · pp. 38–39
• The Lemma 9 proof rewrites the integral as a quadratic form, bounds it through an expected trace, and integrates Lemma 14’s terms to obtain (19).Source: A Deferred Proofs from Section 6 · p. 39