Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis

Abstract

In this paper we study nonconvex and nonsmooth multi-block optimization over Riemannian manifolds with coupled linear constraints. Such optimization problems naturally arise from machine learning, statistical learning, compressive sensing, image processing, and tensor PCA, among others. We develop an ADMM-like primal-dual approach based on decoupled solvable subroutines such as linearized proximal mappings. 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 enjoy an iteration complexity of $O(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, the ${\ell }_q$ regularized sparse tensor principal component analysis and the community detection problem. Our preliminary numerical results show great potentials of the proposed methods.

References in corpus (13)

• Fast community detection by SCORE
• Global rates of convergence for nonconvex optimization on manifolds
• Global Convergence of ADMM in Nonconvex Nonsmooth Optimization
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• Detecting Overlapping Communities in Networks Using Spectral Methods
• First-order Methods for Geodesically Convex Optimization
• Decomposing Linearly Constrained Nonconvex Problems by a Proximal Primal Dual Approach: Algorithms, Convergence, and Applications
• Convergence of multi-block Bregman ADMM for nonconvex composite problems
• Structured Nonconvex and Nonsmooth Optimization: Algorithms and Iteration Complexity Analysis
• Quadratic Optimization with Orthogonality Constraints: Explicit Lojasiewicz Exponent and Linear Convergence of Line-Search Methods
• Riemannian stochastic variance reduced gradient on Grassmann manifold
• MADMM: a generic algorithm for non-smooth optimization on manifolds
• A Sparse Completely Positive Relaxation of the Modularity Maximization for Community Detection

Cited by in corpus (8)

• Proximal Gradient Method for Nonsmooth Optimization over the Stiefel Manifold
• Simple algorithms for optimization on Riemannian manifolds with constraints
• Total Variation of the Normal Vector Field as Shape Prior
• A Brief Introduction to Manifold Optimization
• An inexact augmented Lagrangian method for nonsmooth optimization on Riemannian manifold
• A new numerical scheme for constrained total variation flows and its convergence
• A Riemannian Primal-dual Algorithm Based on Proximal Operator and its Application in Metric Learning
• Managing Randomization in the Multi-Block Alternating Direction Method of Multipliers for Quadratic Optimization