Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis

Abstract

This paper considers the problem of estimating the principal eigenvector of a covariance matrix from independent and identically distributed data samples in streaming settings. The streaming rate of data in many contemporary applications can be high enough that a single processor cannot finish an iteration of existing methods for eigenvector estimation before a new sample arrives. This paper formulates and analyzes a distributed variant of the classical Krasulina's method (D-Krasulina) that can keep up with the high streaming rate of data by distributing the computational load across multiple processing nodes. The analysis shows that---under appropriate conditions---D-Krasulina converges to the principal eigenvector in an order-wise optimal manner; i.e., after receiving $M$ samples across all nodes, its estimation error can be $O(1/M)$. In order to reduce the network communication overhead, the paper also develops and analyzes a mini-batch extension of D-Krasulina, which is termed DM-Krasulina. The analysis of DM-Krasulina shows that it can also achieve order-optimal estimation error rates under appropriate conditions, even when some samples have to be discarded within the network due to communication latency. Finally, experiments are performed over synthetic and real-world data to validate the convergence behaviors of D-Krasulina and DM-Krasulina in high-rate streaming settings.

37 pages, 11 figures; preprint of a journal submission

References in corpus (20)

• An overview of gradient descent optimization algorithms
• Accurate, Large Minibatch SGD: Training ImageNet in 1 Hour
• Searching for Exotic Particles in High-Energy Physics with Deep Learning
• HOGWILD!: A Lock-Free Approach to Parallelizing Stochastic Gradient Descent
• Optimal Distributed Online Prediction using Mini-Batches
• Better Mini-Batch Algorithms via Accelerated Gradient Methods
• The Noisy Power Method: A Meta Algorithm with Applications
• Fast and Simple PCA via Convex Optimization
• Stochastic Optimization of PCA with Capped MSG
• On Graduated Optimization for Stochastic Non-Convex Problems
• Natasha 2: Faster Non-Convex Optimization Than SGD
• Global Convergence of a Grassmannian Gradient Descent Algorithm for Subspace Estimation
• On the Computational Inefficiency of Large Batch Sizes for Stochastic Gradient Descent
• How To Make the Gradients Small Stochastically: Even Faster Convex and Nonconvex SGD
• Fast Stochastic Methods for Nonsmooth Nonconvex Optimization
• Communication-efficient Algorithms for Distributed Stochastic Principal Component Analysis
• AdaOja: Adaptive Learning Rates for Streaming PCA
• History PCA: A New Algorithm for Streaming PCA
• Exponentially convergent stochastic k-PCA without variance reduction
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA

Cited by in corpus (5)

• A Linearly Convergent Algorithm for Distributed Principal Component Analysis
• Distributed Principal Subspace Analysis for Partitioned Big Data: Algorithms, Analysis, and Implementation
• EigenGame: PCA as a Nash Equilibrium
• Communication-Efficient Distributed SVD via Local Power Iterations
• FedPower: Privacy-Preserving Distributed Eigenspace Estimation