Improved Analysis of the Accelerated Noisy Power Method with Applications to Decentralized PCA

We analyze the Accelerated Noisy Power Method, an algorithm for Principal Component Analysis in the setting where only inexact matrix-vector products are available, which can arise for instance in decentralized PCA. While previous works have established that acceleration can improve convergence rates compared to the standard Noisy Power Method, these guarantees require overly restrictive upper bounds on the magnitude of the perturbations, limiting their practical applicability. We provide an improved analysis of this algorithm, which preserves the accelerated convergence rate under much milder conditions on the perturbations. We show that our new analysis is worst-case optimal, in the sense that the convergence rate cannot be improved, and that the noise conditions we derive cannot be relaxed without sacrificing convergence guarantees. We demonstrate the practical relevance of our results by deriving an accelerated algorithm for decentralized PCA, which has similar communication costs to non-accelerated methods. To our knowledge, this is the first decentralized algorithm for PCA with provably accelerated convergence.

A fundamental task in data science is Principal Component Analysis, or PCA. PCA asks a simple question: given a dataset, what are the main patterns or trends hidden in the data? For example, in medical records, one may want to identify the most important factors that explain differences between patients; in a social network, one may want to detect the main structures in how people interact. Over the past decades, an important research goal has been to design algorithms that can find these trends efficiently, especially when the datasets are very large. Our paper studies how to perform PCA when perfectly accurate computations are not available. This situation appears, for example, when the data is spread across several computers and these computers can only exchange a limited amount of information. In that case, each computer may only have an approximate view of the full dataset, rather than exact access to all the data. We show that PCA can still be performed reliably in this imperfect setting, provided that the errors made during the computations remain small enough. Moreover, we prove that one can still recover the patterns at essentially the same speed as the fastest algorithms that assume complete access to the data.