An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function

Area of Science:

• Optimization Theory
• Convex Analysis
• Machine Learning Algorithms

Background:

• Convex-concave saddle point problems are fundamental in optimization and game theory.
• Existing algorithms often struggle with nonsmoothness in coupling functions and regularizers.
• Efficiently solving these problems is crucial for applications like machine learning.

Purpose of the Study:

• To develop and analyze a novel algorithm, OGAProx, for a class of nonsmooth convex-concave saddle point problems.
• To investigate the algorithm's performance under different convexity assumptions (convex-concave, convex-strongly concave, strongly convex-strongly concave).
• To establish theoretical convergence rates for both iterates and function values.

Main Methods:

• Proposed OGAProx algorithm combines optimistic gradient ascent for the smooth variable with proximal steps for nonsmooth components.
• Analyzed convergence properties for different problem settings.
• Validated theoretical findings through applications in nonsmooth-linear problems, multi-kernel SVM training, and minimax group fairness classification.

Main Results:

• Achieved (weak) convergence for iterates.
• Established convergence rates of O(1/K) and linear convergence O(θ^K) for iterates.
• Demonstrated ergodic convergence rates of O(1/K), O(1/K^2), and O(θ^K) for function values.

Conclusions:

• OGAProx is an effective algorithm for solving nonsmooth convex-concave saddle point problems.
• The theoretical convergence guarantees are validated by practical applications.
• The algorithm shows promise for various machine learning tasks requiring saddle point optimization.