The Noisy Power Method: A Meta Algorithm with Applications

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.

NIPS 2014

References in corpus (1)

• Memory Limited, Streaming PCA

Cited by in corpus (54)

• Low-tubal-rank Tensor Completion using Alternating Minimization
• Efficient Second Order Online Learning by Sketching
• Near-Optimal Stochastic Approximation for Online Principal Component Estimation
• Federated Principal Component Analysis
• A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
• CoinPress: Practical Private Mean and Covariance Estimation
• Rivalry of Two Families of Algorithms for Memory-Restricted Streaming PCA
• Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
• Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients
• Streaming Batch Eigenupdates for Hardware Neuromorphic Networks
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• Robust estimation via generalized quasi-gradients
• AdaOja: Adaptive Learning Rates for Streaming PCA
• MOSES: A Streaming Algorithm for Linear Dimensionality Reduction
• An Improved Gap-Dependency Analysis of the Noisy Power Method
• History PCA: A New Algorithm for Streaming PCA
• Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm
• Batch Stationary Distribution Estimation
• DeEPCA: Decentralized Exact PCA with Linear Convergence Rate
• Wishart Mechanism for Differentially Private Principal Components Analysis
• Exponentially convergent stochastic k-PCA without variance reduction
• First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate
• Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis
• Convergence of Stochastic Gradient Descent for PCA
• Communication-Efficient Distributed SVD via Local Power Iterations
• Affine Invariant Covariance Estimation for Heavy-Tailed Distributions
• Fast and Sample Efficient Inductive Matrix Completion via Multi-Phase Procrustes Flow
• The gradient complexity of linear regression
• INSPECTRE: Privately Estimating the Unseen
• k-variates++: more pluses in the k-means++
• Nonconvex One-bit Single-label Multi-label Learning
• Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
• ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA
• Optimal Gradient-based Algorithms for Non-concave Bandit Optimization
• Memory-efficient training with streaming dimensionality reduction
• Statistical Inference in the Differential Privacy Model
• Stochastic Variance-Reduced Heavy Ball Power Iteration
• Privacy Preserving Machine Learning: Threats and Solutions
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation
• Global Convergence of Triangularized Orthogonalization-free Method
• On Low-Space Differentially Private Low-rank Factorization in the Spectral Norm
• A note on privacy preserving iteratively reweighted least squares
• The Price of Differential Privacy for Low-Rank Factorization
• Embedding Principal Component Analysis for Data Reductionin Structural Health Monitoring on Low-Cost IoT Gateways
• A Framework for Private Matrix Analysis
• AgFlow: Fast Model Selection of Penalized PCA via Implicit Regularization Effects of Gradient Flow
• On the Second-order Convergence Properties of Random Search Methods
• Tensor Canonical Correlation Analysis with Convergence and Statistical Guarantees
• Reduced-Rank Regression with Operator Norm Error
• Bootstrapping the error of Oja's algorithm
• On the Approximation of Toeplitz Operators for Nonparametric ${\mathcal{H}}_{\infty }$-norm Estimation
• Faster Kernel Matrix Algebra via Density Estimation
• Gen-Oja: A Two-time-scale approach for Streaming CCA
• Practical and Fast Momentum-Based Power Methods