Spectral Guarantees for Adversarial Streaming PCA

In streaming PCA, we see a stream of vectors x₁, , xₙ ∈ Rᵈ and want to estimate the top eigenvector of their covariance matrix. This is easier if the spectral ratio R = λ₁ / λ₂ is large. We ask: how large does R need to be to solve streaming PCA in O(d) space? Existing algorithms require R = Ω(d). We show: (1) For all mergeable summaries, R = Ω(√d) is necessary. (2) In the insertion-only model, a variant of Oja's algorithm gets $o(1)$ error for R = O(log n log d). (3) No algorithm with o(d²) space gets $o(1)$ error for $R = O(1)$. Our analysis is the first application of Oja's algorithm to adversarial streams. It is also the first algorithm for adversarial streaming PCA that is designed for a spectral, rather than Frobenius, bound on the tail; and the bound it needs is exponentially better than is possible by adapting a Frobenius guarantee.