Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis

• 成果类型: Article
• 署名作者: Zhang, Junyu; Ma, Shiqian; Zhang, Shuzhong
• 署名单位: University of Minnesota System; University of Minnesota Twin Cities; University of California System; University of California Davis; The Chinese University of Hong Kong, Shenzhen
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-019-01418-8
• 发表日期: 2020
• 页码: 445-490
• 关键词: nonconvex; approximation; SPARSE; CONVERGENCE; selection

摘要

In this paper we study nonconvex and nonsmooth multi-block optimization over Euclidean embedded (smooth) Riemannian submanifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. By utilizing the embedding structure, we develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings, where the duality is with respect to the embedded Euclidean spaces. First, we introduce the optimality conditions for the afore-mentioned optimization models. Then, the notion of epsilon-stationary solutions is introduced as a result. The main part of the paper is to show that the proposed algorithms possess an iteration complexity ofO(1/epsilon 2)to reach an epsilon-stationary solution. For prohibitively large-size tensor or machine learning models, we present a sampling-based stochastic algorithm with the same iteration complexity bound in expectation. In case the subproblems are not analytically solvable, a feasible curvilinear line-search variant of the algorithm based on retraction operators is proposed. Finally, we show specifically how the algorithms can be implemented to solve a variety of practical problems such as the NP-hard maximum bisection problem, thelq regularized sparse tensor principal component analysis and the community detection problem. Our preliminary numerical results show great potentials of the proposed methods.