An Improved Gap-Dependency Analysis of the Noisy Power Method

Abstract

We consider the noisy power method algorithm, which has wide applications in machine learning and statistics, especially those related to principal component analysis (PCA) under resource (communication, memory or privacy) constraints. Existing analysis of the noisy power method shows an unsatisfactory dependency over the "consecutive" spectral gap $({\sigma }_k-{\sigma }_{k+1})$ of an input data matrix, which could be very small and hence limits the algorithm's applicability. In this paper, we present a new analysis of the noisy power method that achieves improved gap dependency for both sample complexity and noise tolerance bounds. More specifically, we improve the dependency over $({\sigma }_k-{\sigma }_{k+1})$ to dependency over $({\sigma }_k-{\sigma }_{q+1})$, where $q$ is an intermediate algorithm parameter and could be much larger than the target rank $k$. Our proofs are built upon a novel characterization of proximity between two subspaces that differ from canonical angle characterizations analyzed in previous works. Finally, we apply our improved bounds to distributed private PCA and memory-efficient streaming PCA and obtain bounds that are superior to existing results in the literature.

References in corpus (2)

• Improved Distributed Principal Component Analysis
• Optimal Principal Component Analysis in Distributed and Streaming Models

Cited by in corpus (8)

• First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time
• AdaOja: Adaptive Learning Rates for Streaming PCA
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• Communication-Efficient Distributed SVD via Local Power Iterations
• NEON+: Accelerated Gradient Methods for Extracting Negative Curvature for Non-Convex Optimization
• Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation
• On the Optimality of the Oja's Algorithm for Online PCA
• Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates