A Riemannian Alternating Descent Ascent Algorithmic Framework for Nonconvex-Linear Minimax Problems on Riemannian Manifolds

2024/09/29 by Meng Xu, Xu, Meng, Bo Jiang +5 · 6 citations
Computer Science · Engineering · Mathematics · #3D Shape Modeling and Analysis #Advanced Mathematical Modeling in Engineering #FOS: Mathematics #Numerical methods in inverse problems #Optimization and Control (math.OC)

paper · pdf · doi:10.48550/arxiv.2409.19588

openalex publication_date 2024/09/29 · openalex created_date 2024/10/28 · openalex updated_date 2026/07/28

Abstract

In this paper, we consider a class of nonconvex-linear minimax problems on Riemannian manifolds, which find wide applications in machine learning and signal processing. For solving this class of problems, we develop a flexible Riemannian alternating descent ascent (RADA) algorithmic framework. Within this framework, we propose two easy-to-implement yet efficient algorithms that alternately perform one or multiple projected/Riemannian gradient descent steps and a proximal gradient ascent step at each iteration. We show that the proposed RADA algorithmic framework can find both an ε-Riemannian-game-stationary point and an ε-Riemannian-optimization-stationary point within O(ε^-3) iterations, achieving the best-known iteration complexity. We also reveal intriguing similarities and differences between the algorithms developed within our proposed framework and existing algorithms, thus providing important insights into the improved efficiency of the former. Lastly, we present numerical results on sparse principal component analysis (PCA), fair PCA, and sparse spectral clustering to demonstrate the superior performance of the proposed algorithms.

Cited by

• A Single-loop Stochastic Riemannian ADMM for Nonsmooth Optimization
• A Retraction-free Method for Nonsmooth Minimax Optimization over a Compact Manifold
• Adaptive Riemannian ADMM for Nonsmooth Optimization: Optimal Complexity without Smoothing
• An Inexact Proximal Framework for Nonsmooth Riemannian Difference-of-Convex Optimization
• A New Inexact Manifold Proximal Linear Algorithm with Adaptive Stopping Criteria
• An inexact variable metric proximal linearization method for composite optimization over embedded submanifolds

Related

• Proximal Gradient Descent Ascent Methods for Nonsmooth Nonconvex-Concave Minimax Problems on Riemannian Manifolds
• Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds
• A Riemannian ADMM
• Primal-Dual Optimization Algorithms over Riemannian Manifolds: an Iteration Complexity Analysis
• First-Order Algorithms for Min-Max Optimization in Geodesic Metric Spaces