Convergence Rates of Gradient Descent-ascent Dynamics under Computation Constraints in Solving Min-max Optimization

Abstract

This thesis is dedicated to providing a new analysis of the convergence rates of the Gradient Descent-ascent (GDA) method for solving the Min-max optimization (MMO) problems under computation constraints. In particular, we focus our study on two main classes of MMO: a continuous-time variant of the centralized Min-max problem where the GDA update only has access to the gradients of the objective function after some delay, as well as the Federated Min-max Learning (FML) problem, a special setting within the family of decentralized MMO under quantization constraints. Also known as the saddle point problem due to its objective being to find a saddle point of a function, the MMO problem, as well as its decentralized counterpart, has received wide attention due to its significant impact in different fields such as stochastic control and training generative adversarial networks. The GDA method is one of the most celebrated algorithms to find the saddle point of such functions, due to its computational efficiency and ease of implementation. Therefore, it is important that we delve into the analysis of the GDA approach in the MMO problem, not only in the traditional settings where information can be readily and perfectly available to the computation units but also under more practical scenarios. In this thesis, we focus our study on two special types of constraints. Firstly, understanding that calculating gradients of a function instantly is practically impossible, we tackle the continuous-time variant of centralized GDA under delayed gradients. We utilize the singular perturbation approach to obtain convergence rates in two non-convex settings of the objective function, namely, the two-sided and one-sided Polyak - Lojasiewicz (PL) conditions, by designing a coupling Lyapunov function to capture the interaction between the gradient descent and ascent dynamics subject to asynchronous gradients. Secondly, we study an important framework within decentralized MMO named Federated Min-max Learning, in which limited communication bandwidth requires information exchanged to be quantized. We apply a similar two-time-scale GDA technique to obtain convergence rates in three different settings, namely, the strongly-convex-strongly-concave case, and when it is subject to the two-sided and one-sided PL conditions. Finally, we provide numerical simulations to demonstrate the efficiency of our theoretical results.