Near-optimal stochastic approximation for online principal component estimation

DOI10.1007/S10107-017-1182-ZMaRDI QIDQ681490zbMATH OpenOpenAlexFDO

Authors Chris Junchi Li, Mengdi Wang, Han Liu, Tong Zhang

Publication date 12 February 2018

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1603.05305

zbMATH Keywords

finite-sample analysishigh-dimensional datanonconvex optimizationonline algorithmprincipal component analysisstochastic approximationstochastic gradient method

Mathematics Subject Classification ID

Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Stochastic partial differential equations (aspects of stochastic analysis) (60H15) Factor analysis and principal components; correspondence analysis (62H25) Online algorithms; streaming algorithms (68W27)

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.

Recommendations

• Nearly optimal stochastic approximation for online principal subspace estimation
• On the optimality of the Oja's algorithm for online PCA
• Online principal components analysis
• Convergence analysis of Oja's iteration for solving online PCA with nonzero-mean samples
• Stochastic Gauss-Newton algorithms for online PCA

Cites work

• A simplified neuron model as a principal component analyzer
• Distributed asynchronous incremental subgradient methods
• Estimating the Largest Eigenvalue by the Power and Lanczos Algorithms with a Random Start
• Finite sample approximation results for principal component analysis: A matrix perturbation approach
• High-dimensional analysis of semidefinite relaxations for sparse principal components
• scientific article; zbMATH DE number 3886886 (Why is no real title available?)
• scientific article; zbMATH DE number 5348356 (Why is no real title available?)
• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 48727 (Why is no real title available?)
• scientific article; zbMATH DE number 51132 (Why is no real title available?)
• scientific article; zbMATH DE number 1149836 (Why is no real title available?)
• scientific article; zbMATH DE number 1972910 (Why is no real title available?)
• scientific article; zbMATH DE number 2237386 (Why is no real title available?)
• Incremental proximal methods for large scale convex optimization
• Incremental subgradient methods for nondifferentiable optimization
• Information-Theoretic Lower Bounds on the Oracle Complexity of Stochastic Convex Optimization
• Minimax sparse principal subspace estimation in high dimensions
• On consistency and sparsity for principal components analysis in high dimensions
• On stochastic approximation of the eigenvectors and eigenvalues of the expectation of a random matrix
• Optimal solutions for sparse principal component analysis
• Probability. Theory and examples.
• Random algorithms for convex minimization problems
• Sparse PCA: optimal rates and adaptive estimation
• Sparse principal component analysis and iterative thresholding
• Stability of the Lanczos method for matrix function approximation
• Stochastic compositional gradient descent: algorithms for minimizing compositions of expected-value functions
• Stochastic first-order methods with random constraint projection
• The Adaptive Lasso and Its Oracle Properties
• Truncated power method for sparse eigenvalue problems
• Weak convergence and empirical processes. With applications to statistics

Cited in

(20)

• Online Schatten quasi-norm minimization for robust principal component analysis
• A brief introduction to manifold optimization
• Widening the scope of an eigenvector stochastic approximation process and application to streaming PCA and related methods
• Online PCA with optimal regrets
• Randomized online PCA algorithms with regret bounds that are logarithmic in the dimension
• The dynamics of on-line principal component analysis
• A stochastic variance reduction method for PCA by an exact penalty approach
• A Stochastic Majorize-Minimize Subspace Algorithm for Online Penalized Least Squares Estimation
• Online Nonlinear Estimation via Iterative <inline-formula> <tex-math notation="LaTeX">$L^2$</tex-math> </inline-formula>-Space Projections: Reproducing Kernel of Subspace
• Error estimates for Euler discretization of high-index saddle dynamics
• Online principal components analysis
• Nearly optimal stochastic approximation for online principal subspace estimation
• Online Covariance Matrix Estimation in Stochastic Gradient Descent
• Stochastic Gauss-Newton algorithms for online PCA
• On the optimality of the Oja's algorithm for online PCA
• An efficient algorithm for Fantope-constrained sparse principal subspace estimation problem
• High-dimensional scaling limits and fluctuations of online least-squares SGD with smooth covariance
• Online kernel sliced inverse regression
• Incremental Aggregation on the Grassmannian for Asynchronous Eigenspace Computation
• Convergence analysis of Oja's iteration for solving online PCA with nonzero-mean samples

This page was built for publication: Near-optimal stochastic approximation for online principal component estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q681490)