Dissipative Gradient Descent Ascent Method: A Control Theory Inspired Algorithm for Min-max Optimization

Before we dive into our algorithm, we would like to illustrate our key insight from control theory about how to characterize the energy stored in the system and how to introduce friction to dissipate energy and drive the system toward equilibrium. To get started, consider the following motivating example with a simple bilinear objective function:

We seek to analyze the behavior of (a possibly controlled) vanilla GDA algorithm applied to the above simple bilinear objective function, that is:

where $z_{k}=(x_{k},y_{k})\in\mathbb{R}^{2}$ represent the system state, $u_{k}\in\mathbb{R}^{2}$ a controlled input, and $M:=[\,0\,\,1\,;-1\,\,0\,]$. In the absence of control ($u_{k}=0$, $\forall k$), the algorithm diverges as illustrated by the upper subplot of Figure 1. To understand this unstable process, we keep track of the system’s energy, expressed as the square 2-norm distance to the unique saddle point $(0,0)$, $V(z_{k})=\|z_{k}\|^{2}=x_{k}^{2}+y_{k}^{2}$. A simple algebraic manipulation shows that

Notably, (5) shows how, without control, the energy grows exponentially with each iteration.

We to choose $u_{k}$ so that the right-hand side of (5) is upper-bounded by $\alpha^{2}V(z_{k})$, with $|\alpha|<1$. However, it is usually difficult to do without knowledge of the equilibrium.

The proposed approach uses state augmentation to incorporate a dissipation component that receives some external input $\hat{u}_{k}$ and filters its fluctuations, i.e.,

The dissipation interpretation of (6) can be readily seen, again, by looking at the evolution of its energy

which has the natural tendency to dissipate energy when $|1-\rho|<1$ and $\hat{u}_{k}=0$, $\forall k$.

The key innovation of the proposed approach is to combine (4) and (6) with a proper choice of $u_{k}$ and $\hat{u}_{k}$ that satisfies:

• •

  The combined energy $V(\xi_{k})=\|z_{k}\|^{2}+\|\hat{z}_{k}\|^{2}$ decreases, i.e., there is $|\alpha|<1$ such that:

  $$V(\xi_{k+1})\leq\alpha^{2}V(\xi_{k})\,.$$

  (8)

• •

  The iterates $u_{k}\rightarrow u^{*}=0$, so that the equilibrium of (4), that is, the saddle point does not change.

To achieve these goals we select

thus leading to the combined algorithm

The choice of $\hat{u}_{k}$ ensures that $\hat{z}_{k}$ acts as a filtering process of $z_{k}$. Further, since for constant $z_{k}=\bar{z}$, $\hat{z}_{k}\rightarrow\bar{z}$, the choice of $u_{k}$ ensures that the equilibrium of (4) remains unchanged. We will show in Section IV that one can choose $\eta$ and $\rho$ so that (8) holds. We refer to the bottom of Figure 1 for an illustration of its effectiveness.

In the previous section, we showed how to design a dissipative component (6) to stabilize the GDA updates on a simple bilinear objective. Since the design approach is independent of the particular saddle function $f(x,y)=xy$, it can be readily applied in more general settings. The algorithm presented below seeks to incorporate a similar friction component into a standard GDA update. This modification addresses the inherent limitation of the GDA update when applied to general bilinear problems.

Dissipative gradient descent ascent (DGDA):

Particularly, for $f$ as in (1), in (12) we introduce two new sets of variables $\hat{x}\in\mathbb{R}^{n}$ and $\hat{y}\in\mathbb{R}^{m}$ and a damping parameter $\rho>0$. One important observation is that, once the system reaches equilibrium, i.e., $x_{k+1}=x_{k},y_{k+1}=y_{k},\hat{x}_{k+1}=\hat{x}_{k},\hat{y}_{k+1}=\hat{y}_{k}$, one necessarily has $\hat{x}_{k}=x_{k}$ and $\hat{y}_{k}=y_{k}$, which ensures that the fixed point is necessarily a critical point of the saddle function.

In the remaining part of this section, we will first provide several key observations and properties of the proposed DGDA updates. Then, in the next section, we will formally prove that the proposed DGDA algorithm provides a linear convergence guarantee for both bilinear and strongly convex-strongly concave functions. Mainly, we will show that by simply adding a friction or damping term, the DGDA updates succeed in dissipating the energy of the system even in cases where GDA does not.

The first important observation is that the above DGDA update could be considered as applying a vanilla GDA update to the following regularized surrogate for $f(x,y)$:

Note that this is different from the Proximal Point Method [21, 25] or introducing a $L_{2}$ regularization [26, 27].

Differences with $L_{2}$ regularization  A commonly used method to ensure convergence is to introduce a $L_{2}$ regularization term in $x$ and $y$ [26, 27]:

Although the augmented objective function becomes strongly convex-strongly concave and the vanilla GDA updates will converge, this regularization changes the saddle points. While our algorithm also introduces two regularizing terms, the following Lemma verifies the fixed positions of saddle points between $f(x,y)$ and $f(x,y,\hat{x},\hat{y})$ with virtual variables aligned with original variables.

More interestingly, the regularization terms, $\frac{\rho}{2}\|x-\hat{x}\|^{2}$ and $\frac{\rho}{2}\|y-\hat{y}\|^{2}$, do not introduce extra strong convexity-stong concavity to the original problem. Precisely, the augmented problem $f(x,y,\hat{x},\hat{y})$ is neither strongly convex on ($x,\hat{x}$) nor strongly concave on $(y,\hat{y})$. Indeed, on the hyperplane of $x=\hat{x}$ and $y=\hat{y}$, the augmented problem recovers the original problem $f(x,y,\hat{x},\hat{y})=f(x,y)$. Additionally, the introduced regularization terms of the DGDA method are separable and local, thus preserving the distributed structure that original systems may have. Consequently, it can be seamlessly integrated into a fully distributed approach.

Differences with Proximal Point Method The Proximal Point Method for saddle point problems [21] shares a similar structure with DGDA algorithm. In the proximal method, the next iterates $(x_{k+1},y_{k+1})$ is the unique solution to the saddle point problem

Using the optimality conditions of (15), the update of the Proximal Point method can be written as:

This expression shows that the Proximal Point method is an implicit method. Although Implicit methods are known to be more stable and to benefit from better convergence properties [25, 6], implementing the above updates requires computing the operators $(I+\eta\nabla_{x}f)^{-1}$ and $(I+\eta\nabla_{y}f)^{-1}$, and therefore may be computationally intractable. In contrast, the DGDA algorithm is an explicit algorithm, which applies a vanilla GDA update to the augmented objective function $\eqref{eq:augmented saddle flow}$. Thus, as shown in Table I and II, and in the next section, we choose to compare the convergence of DGDA only with other explicit algorithms for saddle point problems, such as the GDA, Extra-Gradient (EG), and Optimistic GDA (OGDA) methods which have comparable per-iteration computational requirements; although the DGDA algorithm has twice as many state variables, it only requires a single gradient computation per update. Moreover, there is no need for retaining and reemploying the extrapolated gradient, which also sets it apart from the OGDA method.

We finalize this section comparing DGDA with recent efforts leveraging Moreau-Yosida smoothing techniques to solve nonconvex-concave [28, 29, 30], nonconvex-nonconcave [31] min-max optimization problems.

Smoothed-GDA method The Smoothed-GDA consists of the following updates

where $K(x,z;y)=f(x,y)+\frac{p}{2}\|x-z\|^{2}.$ Smoothed-GDA was independently introduced by [32]. It was originally motivated as an ADMM algorithm to solve the linearly constrained nonconvex differentiable minimization problem [32]. The algorithm has been further extended to consider nonconvex-concave min-max optimization problems [28]. Despite its similarities with DGDA, the iterates of smoothed-GDA are sequential, requiring first updates in $x$ and subsequently in $(y,z)$, whereas DGDA updates are fully parallel or synchronized. Unfortunately, the setting where such algorithm has been studied is different from the one considered in this paper, which difficult the comparison with the present work. A thorough comparison of DGDA with (LABEL:eq:_SGDA) is subject of current research.

When applied to the bilinear min-max optimization problem $f(x,y)=x^{T}Ay$, the DGDA update (12) is equivalent to a linear dynamical system. Specifically, denote $z=[x,y]^{T},\hat{z}=[\hat{x},\hat{y}]^{T}$ yields:

where $M=\begin{bmatrix}\mathbf{0}&A\\ -A^{T}&\mathbf{0}\\ \end{bmatrix}.$ As a result, the linear convergence of DGDA, as well as its convergence rate can be derived from the analysis of the spectrum of the associated matrix that defines the DGDA update in (18). This yields the following theorem.

We remark that linear convergence requires $\rho>0$. This is not surprising since GDA, which is known to diverge for bilinear functions, can be interpreted as DGDA method when $\rho=0$. More importantly, by choosing the optimal step size $\rho=1/2,\eta=1/\sigma_{\max}(A)$, DGDA method achieves a better linear convergence rate than the EG and OGDA methods (see Table I).

We now consider the case of strongly convex-strongly concave min-max problems. Let $F(z_{k}):=(\nabla_{x}f(x_{k},y_{k}),-\nabla_{y}f(x_{k},y_{k}))$. The DGDA updates can be written as follows:

Because of the existence of the nonlinear term $F(z_{k})$, we cannot analyze the spectrum as in the previous bilinear case. This is indeed a common challenge in analyzing most optimization algorithms beyond a neighborhood of the fixed point. We circumvent this problem by leveraging recent results on the analysis of variational mappings as $F(\cdot)$ via integral quadratic constraint [18, 16, 17]. More details can be found in the Appendix where we prove the following theorem.

Similarly, as in the bilinear case, we remark on the importance of the dissipation component. When $\rho=0$, a similar analysis as in the proof of the theorem recovers the lower bound of the convergence rate of GDA $(1-\kappa^{-2})$ as shown in [19, 3.1]. Thus, our DGDA method provides a better convergence rate estimate than GDA, since clearly $\kappa\in[1,\infty)$, and therefore $\kappa^{-2}\leq\kappa^{-1}$.

We remark that while the rate obtained in Theorem 3 is clearly better than those of the EG and OGDA methods for large condition numbers $\kappa$ (see Table II), the theorem fails to quantify the comparative performance of DGDA for small values of $\kappa$. The following corollary shows that indeed, the rate of DGDA is provably better for all $\kappa\geq 2$.

We first consider the following bilinear min-max optimization problem: $\min_{x\in\mathbb{R}^{n}}\max_{y\in\mathbb{R}^{m}}x^{T}Ay$, where $A\in\mathbb{R}^{m\times n}$ is full-rank. The simulation results are illustrated in Figure 2 and Figure 3. In this experiment, we set the dimension of the problem to $m=n=10$ and the iterates are initialized at $x_{0},y_{0}$, which are randomly drawn from the uniform distribution on the open interval $(0,1)$.

We plot the errors (distance to saddle points) of DGDA, EG, and OGDA versus the number of gradient evaluations for this problem in Figure 2. The solid line and grey-shaded error bars represent the average trajectories and standard deviations of 20 trials, where in each trial the randomly generated matrix $A$ has a fixed condition number, i.e., $\kappa=\sigma^{2}_{\max}(A)/\sigma^{2}_{\min}(A)=25$. The key motivation is that all three algorithms’ convergence rates critically depend on $\kappa^{-1}$, and by fixing the condition number, we provide an explicit comparison of their convergence speed.

We pick the step size for different methods according to theoretical findings. That is, we select $\rho=1/2$ and $\eta=1/\sigma_{\max}(A)$ for DGDA (Theorem 2), $\eta=1/4L=1/4\sigma_{\max}(A)$ for EG and OGDA (Theorem 6&7 [2] and Theorem 4&7 [1]). In Figure 2, we do not show the error of GDA since it diverges for this bilinear saddle point problem. All other three algorithms converge linearly, with the DGDA method providing the best performance.

Finally, to provide a qualitative demonstration of how DGDA fares with other existing algorithms, we further plot the sample trajectories of GDA, EG, OGDA, and EGDA on a simple 2D bilinear min-max problem, with $m=n=1$. In Figure 3, we observe that while GDA diverges, the trajectories of all other three algorithms converge linearly to the saddle point $(x^{*},y^{*})=(0,0)$. Interestingly, our proposed algorithm (DGDA) despite taking larger steps, exhibits faster linear convergence.

In the second numerical example, we focus on a strongly convex-strongly strongly-concave quadratic problem of the following form:

where the matrices satisfy $\mu_{A}I\preceq A\preceq L_{A}I$, $\mu_{B}I\preceq B\preceq L_{B}I$, $\mu_{c}^{2}I\preceq C^{T}C\preceq L_{c}^{2}I$. As a result, the problem (22) satisfy Assumption 1. In this experiment, we set the dimension of the problem to $n=50,m=10$, and the iterates are initialized at $x_{0},y_{0}$, which are randomly drawn from the uniform distribution on the open interval $(0,1)$. We plot the errors (distance to saddle points) of GDA, DGDA, EG, and OGDA versus the number of gradient evaluations for this problem in Figure 4. Again, the solid line and grey-shaded error bars represent the average trajectories and standard deviations of 20 trials, where in each trial the randomly generated matrix $\begin{bmatrix}A&C\\ -C^{T}&B\end{bmatrix}$ is chosen such that the condition number of (22) remains constant, i.e., $\kappa=L/\mu=31$. Similarly as in the bilinear problem in Section V-A, we pick the step size for the DGDA method according to our theoretical finding in Theorem 3. The step size of the GDA method is selected as $\eta=\mu/L^{2}$ (Theorem 5 [33]). The step sizes for EG and OGDA methods are selected as $\eta=1/4L$ (Theorem 6&7 [2] and Theorem 4&7 [1]). According to the plots, all algorithms converge linearly, and the DGDA method has the best performance.