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 epsilon-Riemannian game stationary point and an epsilon-Riemannian optimization stationary point within O(epsilon-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.

Publication:

MATHEMATICS OF OPERATIONS RESEARCH

http://dx.doi.org/10.1287/moor.2025.1055

Author:

Xu, Meng

Chinese Acad Sci, Acad Math & Syst Sci, Beijing 100190, Peoples R China

Univ Chinese Acad Sci, Beijing 101408, Peoples R China

Email address:xumeng22@mails.ucas.ac.cn

Jiang, Bo (corresponding author)

Nanjing Normal Univ, Sch Math Sci, Key Lab Numer Simulat Large Scale Complex Syst, Minist Educ, Nanjing 210098, Peoples R China

Email address:jiangbo@njnu.edu.cn

Liu, Ya-Feng

Beijing Univ Posts & Telecommun, Sch Math Sci, Key Lab Math & Informat Networks, Minist Educ, Beijing 100876, Peoples R China

Email address: yafengliu@bupt.edu.cn

So, Anthony Man-Cho

Chinese Univ Hong Kong, Dept Syst Engn & Engn Management, Hong Kong, Peoples R China

Email address: manchoso@se.cuhk.edu.hk