The Noisy Power Method: A Meta Algorithm with Applications

2013/11/11 by Moritz Hardt, Eric Price, Hardt, Moritz +1 · 25 citations
Computer Science · Engineering · Mathematics · #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Random Matrices and Applications #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #cs.DS #cs.LG

paper · pdf · doi:10.48550/arxiv.1311.2495

NIPS 2014

openalex publication_date 2013/11/11 · arxiv created 2015/02/03 · arxiv updated 2015/02/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We provide a new robust convergence analysis of the well-known power method for computing the dominant singular vectors of a matrix that we call the noisy power method. Our result characterizes the convergence behavior of the algorithm when a significant amount noise is introduced after each matrix-vector multiplication. The noisy power method can be seen as a meta-algorithm that has recently found a number of important applications in a broad range of machine learning problems including alternating minimization for matrix completion, streaming principal component analysis (PCA), and privacy-preserving spectral analysis. Our general analysis subsumes several existing ad-hoc convergence bounds and resolves a number of open problems in multiple applications including streaming PCA and privacy-preserving singular vector computation.

Citations

• The Rotation of Eigenvectors by a Perturbation. III
• Robust principal component analysis?

Cited by

• Beyond Centralization: Provable Communication Efficient Decentralized Multi-Task Learning
• Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions
• Spectral Perturbation Bounds for Low-Rank Approximation with Applications to Privacy
• Low-Precision Streaming PCA
• Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency
• An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noise
• Decentralized Differentially Private Power Method
• The gradient complexity of linear regression
• Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
• Wishart Mechanism for Differentially Private Principal Components Analysis
• Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
• k-variates++: more pluses in the k-means++
• Differentially Private and Scalable Estimation of the Network Principal Component
• INSPECTRE: Privately Estimating the Unseen
• ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models
• Memory-efficient training with streaming dimensionality reduction
• Batch Stationary Distribution Estimation
• Privacy-preserving federated tensor decomposition of single-cell immune data: recovering multicellular programs across institutions
• An Improved Gap-Dependency Analysis of the Noisy Power Method
• Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation
• AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimization
• Stochastic Variance-Reduced Heavy Ball Power Iteration
• Exponentially convergent stochastic k-PCA without variance reduction

Related

• An Improved Gap-Dependency Analysis of the Noisy Power Method
• Practical and Fast Momentum-Based Power Methods
• Simple exponential acceleration of the power iteration algorithm
• Multiplication-Avoiding Variant of Power Iteration with Applications
• Beyond Worst-Case Analysis in Private Singular Vector Computation