Gradient Descent Ascent for Minimax Problems on Riemannian Manifolds.

Area of Science:

• Optimization
• Machine Learning
• Differential Geometry

Background:

• Minimax optimization problems are prevalent in machine learning and optimization theory.
• Solving these problems on Riemannian manifolds presents unique challenges due to the curved geometry.
• Existing methods often lack efficiency or theoretical guarantees for complex manifold structures.

Purpose of the Study:

• To develop effective Riemannian gradient-based methods for solving minimax problems on Riemannian manifolds.
• To analyze the theoretical performance, specifically sample complexity, of the proposed algorithms.
• To demonstrate the practical applicability of these methods on challenging tasks like robust optimization and deep learning.

Main Methods:

• Proposed a Riemannian Gradient Descent Ascent (RGDA) algorithm for deterministic minimax optimization.
• Developed a Riemannian Stochastic Gradient Descent Ascent (RSGDA) algorithm for stochastic settings.
• Introduced an Accelerated Riemannian Stochastic Gradient Descent Ascent (Acc-RSGDA) algorithm utilizing variance-reduction techniques.

Main Results:

• RGDA achieves a sample complexity of O(κ²ϵ⁻²) for Geodesically-Nonconvex Strongly-Concave (GNSC) problems.
• RSGDA achieves a sample complexity of O(κ⁴ϵ⁻⁴) for stochastic GNSC problems.
• Acc-RSGDA improves sample complexity to ~O(κ⁴ϵ⁻³) for stochastic GNSC problems.

Conclusions:

• The proposed Riemannian gradient-based methods are effective for solving challenging minimax problems on manifolds.
• The algorithms demonstrate improved theoretical sample complexity compared to existing approaches.
• Experimental validation on robust optimization and DNN training confirms the practical efficiency of the developed methods.