The Noisy Power Method: A Meta Algorithm with Applications

By Moritz Hardt, Eric Price. 2013

228 citations recorded by the source corpus.

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: Streaming PCA. A recent work of Mitliagkas et al. (NIPS 2013) gives a space-efficient algorithm for PCA in a streaming model where samples are drawn from a gaussian spiked covariance model. We give a simpler and more general analysis that applies to arbitrary distributions confirming experimental evidence of Mitliagkas et al. Moreover, even in the spiked covariance model our result gives quantitative improvements in a natural parameter regime. It is also notably simpler and follows easily from our general convergence analysis of the noisy power method together with a matrix Chernoff bound. Private PCA. We provide the first nearly-linear time algorithm for the problem of differentially private principal component analysis that achieves nearly tight worst-case error bounds. Complementing our worst-case bounds, we show that the error dependence of our algorithm on the matrix dimension can be replaced by an essentially tight dependence on the coherence of the matrix. This result resolves the main problem left open by Hardt and Roth (STOC 2013). The coherence is always bounded by the matrix dimension but often substantially smaller thus leading to strong average-case improvements over the optimal worst-case bound.

Subfields: Artificial Intelligence, Computational Mechanics, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Mechanics

In Statistics and Probability

Citations in the corpus

Batch Stationary Distribution Estimation (2020, methodology): “Many existing works have focused on the ﬁnite-dimension setting (Balsubramani et al., 2013; Hardt and Price, 2014; Yang et al., 2017), while Kim et al. (2005) and Xie et al. (2015) have extended the power method to the inﬁnite-dimension case using RKHS.”
Gradient Descent Learns One-hidden-layer CNN: Don't be Afraid of Spurious Local Minima (2017, methodology): “See Lemma 2.5 of [Hardt and Price, 2014] for example.”
First-order Stochastic Algorithms for Escaping From Saddle Points in Almost Linear Time (2017, methodology): “, Hardt and Price (2014)), the iteration complexity depends on the eigen-gap ∆k of A in an order of Õ(1/∆k), where the eigen-gap is defined as the difference between the k-th largest eigen-value of A and the (k+1)-th largest eigen-value of A.”
Privacy-Preserving Machine Learning: Threats and Solutions (2018, methodology): “Hardt and Price 19 proposed adding Gaussian noise in each iteration of the algorithm which operates on the non-perturbed covariance matrix, leading to DP-PCA.”
Streaming PCA: Matching Matrix Bernstein and Near-Optimal Finite Sample Guarantees for Oja's Algorithm (2016, methodology): “Finally, consider a block-power method (BPM) [16, 8] which divides samples into different blocks and applies power iteration to the empirical estimate from each block.”
Fast low-rank estimation by projected gradient descent: General statistical and algorithmic guarantees (2015, background): “It is also worth noting that other types of algorithms for nonconvex problems have also been analyzed, including alternating minimization [37, 32, 34], EM algorithms [4, 63] and power methods [33], various hard-thresholding and singular value projection [36, 53, 38, 9], gradient descent for nonconve”
Streaming PCA and Subspace Tracking: The Missing Data Case (2018, methodology): “Block Oja’s methods have also been studied in [37], [56], but the analysis is done under a model much more general than (31): the data vectors xn are assumed to be drawn i.”
K-variates++: More Pluses in the K-means++ (2016, unknown): “Examples abound (Hardt & Price, 2014; Kalai & Vempala, 2005; Chaudhuri et al., 2011; Chichignoud & Lousteau, 2014), etc.”
Follow the Compressed Leader: Faster Online Learning of Eigenvectors and Faster MMWU (2017, background): “In the stochastic setting, the two papers [8, 21] achieve a variant of goal (G2) for ﬁnding the top k eigenvectors; however, their techniques are very diﬀerent from ours and do not imply our results anyways.”
INSPECTRE: Privately Estimating the Unseen (2018, background): “A number of other problems have been studied with privacy requirements, including clustering [WWS15, BDL + 17], principal component analysis [CSS13, KT13, HP14], ordinary least squares [She17], and much more.”
Rademacher Observations, Private Data, and Boosting (2015, methodology): “One popular mechanism is the Gaussian mechanism [12, 16], which convolutes data with independent Gaussian random variables N(0, ς2I), whose standard deviation ς depends on the DP requirement ( , δ).”
Scale Up Nonlinear Component Analysis with Doubly Stochastic Gradients (2015, methodology): “The noisy power method presented in [7] provided linear convergence for a subspace, although it only converges linearly to a constant error level.”
Online and Differentially-Private Tensor Decomposition (2016, background): “This is because the problem of tensor decomposition is NP-hard, and if a large amount of arbitrary noise is added to an orthogonal tensor, the decomposition can again become intractable.”