A stochastic variance reduction method for PCA by an exact penalty approach
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
For principal component analysis (PCA) to efficiently analyze large scale matrices, it is crucial to find a few singular vectors in cheaper computational cost and under lower memory requirement. To compute those in a fast and robust way, we propose a new stochastic method. Especially, we adopt the stochastic variance reduced gradient (SVRG) method \cite{JZ} to avoid asymptotically slow convergence in stochastic gradient descent methods. For that purpose, we reformulate the PCA problem as a unconstrained optimization problem using a quadratic penalty. In general, increasing the penalty parameter to infinity is needed for the equivalence of the two problems. However, in this case, exact penalization is guaranteed by applying the analysis in \cite{WYLZ}. We establish the convergence rate of the proposed method to a stationary point and numerical experiments illustrate the validity and efficiency of the proposed method.
Abstract
For principal component analysis (PCA) to efficiently analyze large scale matrices, it is crucial to find a few singular vectors in cheaper computational cost and under lower memory requirement. To compute those in a fast and robust way, we propose a new stochastic method. Especially, we adopt the stochastic variance reduced gradient (SVRG) method \cite{JZ} to avoid asymptotically slow convergence in stochastic gradient descent methods. For that purpose, we reformulate the PCA problem as a unconstrained optimization problem using a quadratic penalty. In general, increasing the penalty parameter to infinity is needed for the equivalence of the two problems. However, in this case, exact penalization is guaranteed by applying the analysis in \cite{WYLZ}. We establish the convergence rate of the proposed method to a stationary point and numerical experiments illustrate the validity and efficiency of the proposed method.
참고문헌 (27)
- Z. Allen-Zhu, "Variance Reduction for Faster Non-Convex Optimization", ~ (2016)
- Z. Allen-Zhu, "LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain", ~ (2017)
- Z. Allen-Zhu, "Improved SVRG for Non-Strongly-Convex or Sum-of-NonConvex Objectives", ~ (2016)
- J. Barzilai, "Two-point step size gradient methods", IMA J. Numer. Anal., 8(1), pp.141~148 (1988)[DOI]
- L. Bottou, "Optimization Methods for Large-Scale Machine Learning", ~ (2016)
- J. P. Cunningham, "Linear dimensionality reduction: survey, insights, and generalizations", J. Mach. Learn. Res., 16, pp.2859~2900 (2015)
- D. Garber, "Fast and Simple PCA via Convex Optimization", ~ (2015)
- G. H. Golub, "Matrix Computations, fourth edition, Johns Hopkins Studies in the Mathematical Sciences" (2013), Johns Hopkins University Press
- R. A. Horn, "Matrix Analysis, second edition" (2013), Cambridge University Press
- B. Jiang, "Unconstrained optimization models for computing several extreme eigenpairs of real symmetric matrices", Pac. J. Optim., 10(1), pp.53~71 (2014)
- R. Johnson, "Accelerating stochastic gradient descent using predictive variance reduction", Advances in Neural Information Processing Systems, pp.315~323 (2013)
- I. T. Jolliffe, "Principal Component Analysis, second edition, Springer Series in Statistics" (2002), Springer-Verlag
- H. Kasai, "Riemannian stochastic variance reduced gradient on Grassmann manifold", ~ (2017)
- Y. LeCun, "Gradient-based learning applied to document recognition", Proceedings of the IEEE, 86(11), pp.2278~2324 (1998)[DOI]
- X. Liu, "Limited memory block Krylov subspace optimization for computing dominant singular value decompositions", SIAM J. Sci. Comput., 35(3), pp.A1641~A1668 (2013)[DOI]
- S. J. Reddi, "Poczos, Stochastic Variance Reduction for Nonconvex Optimization", ~ (2016)
- Y. Saad, "Numerical methods for large eigenvalue problems, revised edition of the 1992 original, Classics in Applied Mathematics, 66" (2011)
- M. Schmidt, "Minimizing finite sums with the stochastic average gradient", Math. Program., 162(1-2), pp.83~112 (2017)[DOI]
- S. Shalev-Shwartz, "Stochastic dual coordinate ascent methods for regularized loss minimization", J. Mach. Learn. Res., 14, pp.567~599 (2013)
- O. Shamir, "A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate", The 32nd International Conference on Machine Learning (ICML 2015) (2015)
- O. Shamir, "Fast stochastic algorithms for SVD and PCA: convergence properties and convexity", ~ (2015)
- C. Tan, "Barzilai-Borwein step size for stochastic gradient descent", ~ (2016)
- D. S. Watkins, "The Matrix Eigenvalue Problem" (2007)
- Z. Wen, "Trace-penalty minimization for large-scale eigenspace computation", J. Sci. Comput., 66(3), pp.1175~1203 (2016)[DOI]
- J. H. Wilkinson, "The Algebraic Eigenvalue Problem, Monographs on Numerical Analysis" (1988), The Clarendon Press, Oxford University Press
- Z. Xu, "Stochastic variance reduced Riemannian eigensolver", ~ (2016)
- H. Zhang, "Fast stochastic optimization on Riemannian manifolds", Advances in Neural Information Processing Systems 29 (NIPS 2016) (2017)