Primal-dual optimization algorithms over Riemannian manifolds

an iteration complexity analysis

Junyu Zhang, Shiqian Ma, Shuzhong Zhang

Research output: Contribution to journalArticle

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)
JournalMathematical Programming
DOIs
StatePublished - Jan 1 2019

Fingerprint

Primal-dual Algorithm
Complexity Analysis
Riemannian Manifold
Optimization Algorithm
Tensor
Stationary Solutions
Tensors
Iteration
Machine Learning
Proximal Mapping
Learning systems
Multiblock
Community Detection
Statistical Learning
Compressive Sensing
Bisection
Retraction
Primal-dual
Stochastic Algorithms
Line Search

Keywords

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

Cite this

Primal-dual optimization algorithms over Riemannian manifolds : an iteration complexity analysis. / Zhang, Junyu; Ma, Shiqian; Zhang, Shuzhong.

In: Mathematical Programming, 01.01.2019.

Research output: Contribution to journalArticle

@article{9a6684cd99be461b801b8b71e9218fcc,
title = "Primal-dual optimization algorithms over Riemannian manifolds: an iteration complexity analysis",
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.",
keywords = "ADMM, Iteration complexity, Nonconvex and nonsmooth optimization, Riemannian manifold, ϵ-Stationary solution",
author = "Junyu Zhang and Shiqian Ma and Shuzhong Zhang",
year = "2019",
month = "1",
day = "1",
doi = "10.1007/s10107-019-01418-8",
language = "English (US)",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",

}

TY - JOUR

T1 - Primal-dual optimization algorithms over Riemannian manifolds

T2 - an iteration complexity analysis

AU - Zhang, Junyu

AU - Ma, Shiqian

AU - Zhang, Shuzhong

PY - 2019/1/1

Y1 - 2019/1/1

N2 - 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.

AB - 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.

KW - ADMM

KW - Iteration complexity

KW - Nonconvex and nonsmooth optimization

KW - Riemannian manifold

KW - ϵ-Stationary solution

UR - http://www.scopus.com/inward/record.url?scp=85070329439&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85070329439&partnerID=8YFLogxK

U2 - 10.1007/s10107-019-01418-8

DO - 10.1007/s10107-019-01418-8

M3 - Article

JO - Mathematical Programming

JF - Mathematical Programming

SN - 0025-5610

ER -