Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds
This work addresses minimax problems in machine learning on curved spaces, offering improved efficiency for tasks like robust training, though it is incremental as it extends existing gradient methods to Riemannian settings.
The authors tackled minimax optimization on Riemannian manifolds by proposing Riemannian gradient descent ascent algorithms, achieving sample complexities of O(κ²ε⁻²) for deterministic cases and O(κ⁴ε⁻⁴) for stochastic cases, with an accelerated version reducing it to Õ(κ⁴ε⁻³).
In the paper, we study a class of useful minimax problems on Riemanian manifolds and propose a class of effective Riemanian gradient-based methods to solve these minimax problems. Specifically, we propose an effective Riemannian gradient descent ascent (RGDA) algorithm for the deterministic minimax optimization. Moreover, we prove that our RGDA has a sample complexity of $O(κ^2ε^{-2})$ for finding an $ε$-stationary solution of the Geodesically-Nonconvex Strongly-Concave (GNSC) minimax problems, where $κ$ denotes the condition number. At the same time, we present an effective Riemannian stochastic gradient descent ascent (RSGDA) algorithm for the stochastic minimax optimization, which has a sample complexity of $O(κ^4ε^{-4})$ for finding an $ε$-stationary solution. To further reduce the sample complexity, we propose an accelerated Riemannian stochastic gradient descent ascent (Acc-RSGDA) algorithm based on the momentum-based variance-reduced technique. We prove that our Acc-RSGDA algorithm achieves a lower sample complexity of $\tilde{O}(κ^{4}ε^{-3})$ in searching for an $ε$-stationary solution of the GNSC minimax problems. Extensive experimental results on the robust distributional optimization and robust Deep Neural Networks (DNNs) training over Stiefel manifold demonstrate efficiency of our algorithms.