The Noisy Power Method: A Meta Algorithm with Applications
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 spaceefficient 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.
The paper conveys a broad analysis of the convergence of the pertubed power method, called noisy power method (NPM), recently applied in a number of applications, which subsume computation of singular vectors of a matrix in a presence of noise. The authors infer and state an explicit general convergence rate of NPM subject to the noise of a bounded magnitude. Thereby, they ensure a global convergence of NPM, only local convergence of NPM being previously claimed for the matrix completion application. In the case of the streaming PCA, the generality of the estimates allows to extend the model to arbitrary distributions. Regarding the privacy-preserving spectral analysis, a fast NPM based algorithm is elaborated, which keeps a nearly optimal accuracy.Quality and Clarity: The paper is technically sound. The presentation of the developed theory is clear and cohesive.Originality: This work extends and extensively generalizes earlier applications of NPM imposing new theoretical findings regarding the convergence of the method.Significance: The work develops an important and valuable theory that has already shown to advance the applications of NPM.