Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds

Abstract

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 <inline-formula><tex-math notation="LaTeX">$O(\kappa ^{2}\epsilon ^{-2})$</tex-math></inline-formula> for finding an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> -stationary solution of the Geodesically-Nonconvex Strongly-Concave (GNSC) minimax problems, where <inline-formula><tex-math notation="LaTeX">$\kappa$</tex-math></inline-formula> 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 <inline-formula><tex-math notation="LaTeX">$O(\kappa ^{4}\epsilon ^{-4})$</tex-math></inline-formula> for finding an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> -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 <inline-formula><tex-math notation="LaTeX">$\tilde{O}(\kappa ^{4}\epsilon ^{-3})$</tex-math></inline-formula> in searching for an <inline-formula><tex-math notation="LaTeX">$\epsilon$</tex-math></inline-formula> -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.

Topics & Concepts