Near-Optimal Stochastic Approximation for Online Principal Component Estimation

Abstract

Principal component analysis (PCA) has been a prominent tool for high-dimensional data analysis. Online algorithms that estimate the principal component by processing streaming data are of tremendous practical and theoretical interests. Despite its rich applications, theoretical convergence analysis remains largely open. In this paper, we cast online PCA into a stochastic nonconvex optimization problem, and we analyze the online PCA algorithm as a stochastic approximation iteration. The stochastic approximation iteration processes data points incrementally and maintains a running estimate of the principal component. We prove for the first time a nearly optimal finite-sample error bound for the online PCA algorithm. Under the subgaussian assumption, we show that the finite-sample error bound closely matches the minimax information lower bound.

Finalized version (bib and typos updated). To appear in Mathematical Programming

References in corpus (7)

• Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes
• Finite sample approximation results for principal component analysis: a matrix perturbation approach
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• Randomized Block Krylov Methods for Stronger and Faster Approximate Singular Value Decomposition
• Fast and Simple PCA via Convex Optimization
• Nonconvex Statistical Optimization: Minimax-Optimal Sparse PCA in Polynomial Time
• Stochastic Compositional Gradient Descent: Algorithms for Minimizing Compositions of Expected-Value Functions

Cited by in corpus (20)

• SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path Integrated Differential Estimator
• On the diffusion approximation of nonconvex stochastic gradient descent
• Subspace Estimation from Incomplete Observations: A High-Dimensional Analysis
• Sharp Analysis for Nonconvex SGD Escaping from Saddle Points
• AdaOja: Adaptive Learning Rates for Streaming PCA
• History PCA: A New Algorithm for Streaming PCA
• Nearly Optimal Stochastic Approximation for Online Principal Subspace Estimation
• On Landscape of Lagrangian Functions and Stochastic Search for Constrained Nonconvex Optimization
• Semi-groups of stochastic gradient descent and online principal component analysis: properties and diffusion approximations
• Streaming k-PCA: Efficient guarantees for Oja's algorithm, beyond rank-one updates
• On the Optimality of the Oja's Algorithm for Online PCA
• ODE-Inspired Analysis for the Biological Version of Oja's Rule in Solving Streaming PCA
• On the Regret Minimization of Nonconvex Online Gradient Ascent for Online PCA
• Online Factorization and Partition of Complex Networks From Random Walks
• A Brief Introduction to Manifold Optimization
• A note on concentration inequality for vector-valued martingales with weak exponential-type tails
• Dropping Convexity for More Efficient and Scalable Online Multiview Learning
• Bootstrapping the error of Oja's algorithm
• A General Framework for Analyzing Stochastic Dynamics in Learning Algorithms
• Stochastic Approximation for Online Tensorial Independent Component Analysis