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

Junyu Zhang, Shiqian Ma, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

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 ϵ-stationary solutions is introduced as a result. The main part of the paper is to show that the proposed algorithms possess an iteration complexity of O(1 / ϵ2) to reach an ϵ-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, the ℓq regularized sparse tensor principal component analysis and the community detection problem. Our preliminary numerical results show great potentials of the proposed methods.

Original languageEnglish (US)
Pages (from-to)445-490
Number of pages46
JournalMathematical Programming
Volume184
Issue number1-2
DOIs
StatePublished - Nov 1 2020

Bibliographical note

Funding Information:
The authors would like to thank the associate editor and two anonymous reviewers for insightful and constructive comments that helped improve the presentation of this paper. The work of S. Ma was supported in part by a startup package in the Department of Mathematics at University of California, Davis. The work of S. Zhang was supported in part by the National Science Foundation under Grant CMMI-1462408 and in part by the Shenzhen Fundamental Research Fund under Grant KQTD2015033114415450.

Publisher Copyright:
© 2019, Springer-Verlag GmbH Germany, part of Springer Nature and Mathematical Optimization Society.

Keywords

  • ADMM
  • Iteration complexity
  • Nonconvex and nonsmooth optimization
  • Riemannian manifold
  • ϵ-Stationary solution

Fingerprint

Dive into the research topics of 'Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis'. Together they form a unique fingerprint.

Cite this