Skip to main content

Near-optimal stochastic approximation for online principal component estimation

Author(s): Li, CJ; Wang, Mengdi; Liu, Han; Zhang, T

Download
To refer to this page use: http://arks.princeton.edu/ark:/88435/pr1wf8x
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.
Publication Date: 2018
Citation: Li, Chris Junchi, Mengdi Wang, Han Liu, and Tong Zhang. "Near-optimal stochastic approximation for online principal component estimation." Mathematical Programming 167, no. 1 (2018): 75-97. doi:10.1007/s10107-017-1182-z
DOI: doi:10.1007/s10107-017-1182-z
ISSN: 0025-5610
EISSN: 1436-4646
Pages: 75 - 97
Type of Material: Journal Article
Journal/Proceeding Title: Mathematical Programming
Version: Author's manuscript



Items in OAR@Princeton are protected by copyright, with all rights reserved, unless otherwise indicated.