The Noisy Power Method: A Meta Algorithm with Applications

2013/11/11 by Hardt, Moritz, Price, Eric · 7 citations
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG)

paper · doi:10.48550/arxiv.1311.2495

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.

Cited by

• Beyond Centralization: Provable Communication Efficient Decentralized Multi-Task Learning
• Black-Box Differentially Private Nonparametric Confidence Intervals Under Minimal 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

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