Diffusion Approximations for Online Principal Component Estimation and Global Convergence
In this paper, we propose to adopt the diffusion approximation tools to study the dynamics of Oja's iteration which is an online stochastic gradient descent method for the principal component analysis. Oja's iteration maintains a running estimate of the true principal component from streaming data and enjoys less temporal and spatial complexities. We show that the Oja's iteration for the top eigenvector generates a continuous-state discrete-time Markov chain over the unit sphere. We characterize the Oja's iteration in three phases using diffusion approximation and weak convergence tools. Our three-phase analysis further provides a finite-sample error bound for the running estimate, which matches the minimax information lower bound for principal component analysis under the additional assumption of bounded samples.
This work analyses the classical Oja iteration for finding the first principal component. They show it can be approximated using a stochastic process and provide global convergence guarantees which match the optimal .
Although the related work section is very dense, it is well organized and serves as a good starting point for the non-expert reader.
As a non expert in this area I find it quite hard to judge the merits of this paper in detail. Having said that it seems that providing the first global convergence guarantees for Oja’s rule ought to be of interest.
The analysis seems to thoroughly explain the different phases in the optimization procedure which perhaps could be useful as a diagnostic tool.
The analysis only considers the standard Oja rule which obtains the leading eigenvector. This is perhaps of limited use, but I appreciate the difficulty in extending this to the entire prinicpal subspace.
Line 27. A point which is tangential to the direction of a paper but still I believe a mischaracterization: We don’t need to compute the covariance matrix. Computing the SVD suffices and can be sped up using randomized techniques. At the very least, we don’t require O(d^2) storage.
There are plenty of typos and ungrammatical sentences throughout and should be proofread more thoroughly. E.g.
145: using an inﬁnitesimal generator analysis results
160: is name the generalized logistic curves.
165: for more on basic concepts and relates topics of SDE
171: a local maximizers that has negative curvatures in every direction.
171: In below, we consider