Weakly Convex Optimization over Stiefel Manifold Using Riemannian Subgradient-Type Methods

Abstract

We consider a class of nonsmooth optimization problems over the Stiefel manifold, in which the objective function is weakly convex in the ambient Euclidean space. Such problems are ubiquitous in engineering applications but still largely unexplored. We present a family of Riemannian subgradient-type methods -- namely Riemannain subgradient, incremental subgradient, and stochastic subgradient methods -- to solve these problems and show that they all have an iteration complexity of $\mathcal{O}({\epsilon }^{-4})$ for driving a natural stationarity measure below $\epsilon$. In addition, we establish the local linear convergence of the Riemannian subgradient and incremental subgradient methods when the problem at hand further satisfies a sharpness property and the algorithms are properly initialized and use geometrically diminishing stepsizes. To the best of our knowledge, these are the first convergence guarantees for using Riemannian subgradient-type methods to optimize a class of nonconvex nonsmooth functions over the Stiefel manifold. The fundamental ingredient in the proof of the aforementioned convergence results is a new Riemannian subgradient inequality for restrictions of weakly convex functions on the Stiefel manifold, which could be of independent interest. We also show that our convergence results can be extended to handle a class of compact embedded submanifolds of the Euclidean space. Finally, we discuss the sharpness properties of various formulations of the robust subspace recovery and orthogonal dictionary learning problems and demonstrate the convergence performance of the algorithms on both problems via numerical simulations.

arXiv comment30 pages. Accepted to SIAM Journal on Optimization

References in corpus (19)

• Generalized power method for sparse principal component analysis
• Global rates of convergence for nonconvex optimization on manifolds
• Complete Dictionary Recovery over the Sphere I: Overview and the Geometric Picture
• Complete Dictionary Recovery over the Sphere II: Recovery by Riemannian Trust-region Method
• An Overview of Robust Subspace Recovery
• A Novel M-Estimator for Robust PCA
• A Second Order Non-Smooth Variational Model for Restoring Manifold-Valued Images
• Majorization for Changes in Angles Between Subspaces, Ritz Values, and Graph Laplacian Spectra
• Subgradient Descent Learns Orthogonal Dictionaries
• The proximal point method revisited
• A Well-Tempered Landscape for Non-convex Robust Subspace Recovery
• Incremental Methods for Weakly Convex Optimization
• A Nonconvex Approach for Exact and Efficient Multichannel Sparse Blind Deconvolution
• Composite optimization for robust blind deconvolution
• Vector Transport-Free SVRG with General Retraction for Riemannian Optimization: Complexity Analysis and Practical Implementation
• Complete Dictionary Learning via ${\ell }^4$-Norm Maximization over the Orthogonal Group
• Efficient Dictionary Learning with Gradient Descent
• Manifold Gradient Descent Solves Multi-Channel Sparse Blind Deconvolution Provably and Efficiently
• Unique Sharp Local Minimum in ${\ell }_1$-minimization Complete Dictionary Learning

Cited by in corpus (8)

• Blind Data Detection in Massive MIMO via ${\ell }_3$-norm Maximization over the Stiefel Manifold
• Finding the Sparsest Vectors in a Subspace: Theory, Algorithms, and Applications
• Riemannian Stochastic Proximal Gradient Methods for Nonsmooth Optimization over the Stiefel Manifold
• Decentralized Riemannian Gradient Descent on the Stiefel Manifold
• Riemannian Perspective on Matrix Factorization
• A Manifold Proximal Linear Method for Sparse Spectral Clustering with Application to Single-Cell RNA Sequencing Data Analysis
• Understanding Notions of Stationarity in Non-Smooth Optimization
• Boosting RANSAC via Dual Principal Component Pursuit