-

 

 

 




Optimization Online





 

Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation

Bo Jiang (jiangbo***at***njnu.edu.cn)
Shiqian Ma (sqma***at***se.cuhk.edu.hk)
Anthony Man-Cho So (manchoso***at***se.cuhk.edu.hk)
Shuzhong Zhang (zhangs***at***umn.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/2017
Entry Accepted: 05/25/2017
Entry Last Modified: 05/26/2017

Modify/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
Mathematical Optimization Society