Convergence Rates of Gradient Descent-Ascent Dynamics Under Delays in Solving Nonconvex Min-Max Optimization
Duy Anh, Thinh T. Doan · 2024
In this paper, we study the so-called two-time-scale gradient descent-ascent method for solving min-max optimization problem. Our focus is to characterize the performance of this method, in particular, its continuous-time variant, under delays in gradient computation. Delays are common issues in large-scale optimization problems, which if not properly addressed, can lead to the instability of gradient methods. Unlike the classic gradient methods where theoretical guarantees for their performance under delays are well-studied, similar results for the gradient descent-ascent algorithms are very sparse. To address this gap, we provide a new analysis to characterize the convergence rates of the two-time-scale gradient descent-ascent dynamics under delays in solving nonconvex min-max optimization under the two-sided Polyak-Lojasiewicz conditions. Our results show that these dynamics converge exponentially to the optimal solution of the problem even under the impact of delays. The key idea in our analysis is to utilize the classic singular perturbation approach to design a coupling Lyapunov function to address the interaction between the gradient descent and ascent dynamics and the effect of delays. Finally, we provide a number of numerical simulations to illustrate our theoretical results.