Convergence rate analysis of the gradient descent-ascent method for convex-concave saddle-point problems

2022/09/02 by Moslem Zamani, Zamani, Moslem, Hadi Abbaszadehpeivasti +3 · 3 citations
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #FOS: Mathematics #Optimization and Control (math.OC) #Optimization and Variational Analysis #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.2209.01272

openalex publication_date 2022/09/02 · openalex created_date 2022/09/08 · openalex updated_date 2026/07/28

Abstract

In this paper, we study the gradient descent-ascent method for convex-concave saddle-point problems. We derive a new non-asymptotic global convergence rate in terms of distance to the solution set by using the semidefinite programming performance estimation method. The given convergence rate incorporates most parameters of the problem and it is exact for a large class of strongly convex-strongly concave saddle-point problems for one iteration. We also investigate the algorithm without strong convexity and we provide some necessary and sufficient conditions under which the gradient descent-ascent enjoys linear convergence.

Cited by

• Stackelberg Learning from Human Feedback: Preference Optimization as a Sequential Game
• Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
• On the convergence rate of the Douglas-Rachford splitting algorithm

Related

• Convergence Rate of O(1/k) for Optimistic Gradient and Extra-gradient Methods in Smooth Convex-Concave Saddle Point Problems
• Alternating Proximal Point Algorithm with Gradient Descent and Ascent Steps for Convex-Concave Saddle-Point Problems
• Linear Convergence of a Unified Primal--Dual Algorithm for Convex--Concave Saddle Point Problems with Quadratic Growth
• An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function
• Last Iterate is Slower than Averaged Iterate in Smooth Convex-Concave Saddle Point Problems