Convergence of Stochastic Gradient Descent for PCA

2015/09/30 by Ohad Shamir, Shamir, Ohad · 2 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Optimization and Control (math.OC) #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1509.09002

openalex publication_date 2015/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider the problem of principal component analysis (PCA) in a streaming stochastic setting, where our goal is to find a direction of approximate maximal variance, based on a stream of i.i.d. data points in \reals^d. A simple and computationally cheap algorithm for this is stochastic gradient descent (SGD), which incrementally updates its estimate based on each new data point. However, due to the non-convex nature of the problem, analyzing its performance has been a challenge. In particular, existing guarantees rely on a non-trivial eigengap assumption on the covariance matrix, which is intuitively unnecessary. In this paper, we provide (to the best of our knowledge) the first eigengap-free convergence guarantees for SGD in the context of PCA. This also partially resolves an open problem posed in \citehardt2014noisy. Moreover, under an eigengap assumption, we show that the same techniques lead to new SGD convergence guarantees with better dependence on the eigengap.

Citations

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence\n Results and Optimal Averaging Schemes
• Analysis of a complex of statistical variables into principal components.
• Randomized Block Krylov Methods for Stronger and Faster Approximate\n Singular Value Decomposition
• Fast and Simple PCA via Convex Optimization

Cited by

• Low-Precision Streaming PCA
• Faster Eigenvector Computation via Shift-and-Invert Preconditioning

Related

• Stochastic Approximation Algorithms for Principal Component Analysis
• A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate
• Stochastic Variance-Reduced Heavy Ball Power Iteration
• Exponentially convergent stochastic k-PCA without variance reduction
• Robust Streaming PCA