- Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation Bo Jiang (jiangbonjnu.edu.cn) Shiqian Ma (sqmase.cuhk.edu.hk) Anthony Man-Cho So (manchosose.cuhk.edu.hk) Shuzhong Zhang (zhangsumn.edu) Abstract: In this paper, we propose a vector transport-free stochastic variance reduced gradient (SVRG) method with general retraction for empirical risk minimization over Riemannian manifold. Existing SVRG methods on manifold usually consider a specific retraction operation, and involve additional computational costs such as parallel transport or vector transport. The vector transport-free SVRG with general retraction we propose in this paper handles general retraction operations, and do not need additional computational costs mentioned above. As a result, we name our algorithm S-SVRG, where the first S" means simple. We analyze the iteration complexity of S-SVRG for obtaining an $\epsilon$-stationary point and its local linear convergence by assuming the \L ojasiewicz inequality, which naturally holds for PCA and holds with high probability for matrix completion problem. We also incorporate the Barzilai-Borwein step size and design a very practical S-SVRG-BB method. Numerical results on PCA and matrix completion problems are reported to demonstrate the efficiency of our methods. Keywords: Stochastic Variance Reduced Gradient, Riemannian Manifold, Orthogonality Constraints, Principal Component Analysis, Matrix Completion Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization ) Category 2: Stochastic Programming Citation: @article{jiang2017vector, author = {{Jiang}, Bo and {Ma}, Shiqian and {So}, Antony Man-Cho and {Zhang}, Shuzhong}, title = "{Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation}", journal = {arXiv: 1705.09059}, primaryClass = "math.OC", year = 2017, } Download: [PDF]Entry Submitted: 05/25/2017Entry Accepted: 05/25/2017Entry Last Modified: 05/26/2017Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Optmization Society.