An Optimal Multistage Stochastic Gradient Method for Minimax Problems

Introduction

The minimax optimization problem has recently gained tremendous attention as the canonical problem formulation for robust training of machine learning models and Generative Adversarial Networks (GANs) (see Madry et al., (2018); Goodfellow et al., (2014); Arjovsky et al., (2017)). While many papers have studied the convergence of a broad range of algorithms in the deterministic setting, i.e., when the gradient information is exact, many aspects of this problem in the stochastic setting are yet to be explored. This is the main goal of our manuscript as we provide a framework for analyzing minimax optimization algorithms which can be used for both the deterministic and stochastic settings.

In solving the minimization problem in the stochastic setting, it is well-known that, for many algorithms, the squared distance of the iterates to the solution of the minimization problem can be bounded by the sum of two terms: bias and variance Bach and Moulines, (2013); Ghadimi and Lan, (2012); Aybat et al., (2019). The bias term captures the effect of the initialization expressed in terms of the distance of the initial point to the solution, and is independent of the noise parameters. The variance term depends on noise characteristics ($\sigma^{2}$ in our case) and is independent of the initialization error. For the minimization problem with strongly convex objective function, and in the noiseless case (with only the bias term), Nemirovsky and Yudin, (1983) have shown the lower bound of $\Theta\left(\exp(-\Theta(1)n/\sqrt{\kappa})\right)$ for the distance of the $n$-th iterate to the optimal solution. With noise Raginsky and Rakhlin, (2011) have shown the lower bound increases to $\Theta(\sigma^{2}/n)$. Several papers have highlighted the trade-off between bias and variance which arises in design of optimization algorithms Aybat et al., (2018) and tried to achieve both lower bounds simultaneously Ghadimi and Lan, (2013); Aybat et al., (2019).

In this paper, we highlight this bias-variance decomposition in evaluating the performance of algorithms that solve the minimax problem. For the bias term, i.e., the deterministic case, Ibrahim et al., (2019) have recently shown the lower bound $\mathcal{O}(1)\exp(-\Theta(1)n/\kappa)$ highlighting that the dependence on condition number increases from $\sqrt{\kappa}$ in minimization problems to $\kappa$ for minimax problems. For the variance term, since the minimax problem is a special case of the minimization problem, the lower bound $\mathcal{O}(\sigma^{2}/n)$ of the minimization problem is also valid for the minimax problem. While this lower bound for variance term has been obtained Hsieh et al., (2019); Rosasco et al., (2014) at the cost of making the bias term sublinear, the question of whether a linear rate $\mathcal{O}(1)\exp(-\Theta(1)n/\kappa)$ in bias and $\mathcal{O}(\sigma^{2}/n)$ in variance could be achieved simultaneously has not been addressed prior to this work.

In what follows, we first provide a summary of related works and then discuss the main contributions of our paper.

Many papers have studied the minimax problem when the exact gradient information is available. In the case of Gradient Descent Ascent (GDA) method, Du and Hu, (2019) analyzes its performance for the special case of bilinear coupling, i.e., when $f(x,y)=g(x)+y^{\top}Ax-h(y)$ where $g$ is smooth and convex, $h$ is smooth and strongly convex, and the matrix $A$ has full column rank. They show that running the GDA algorithm for $n$ steps on this problem reaches a point which is $\mathcal{O}(1)\left(1/n^{2}\right)$ close to the saddle point. In addition, when the function $g(\cdot)$ is assumed to be strongly convex, GDA reaches a point which is $\mathcal{O}(1)\text{exp}\left(-\Theta(1)n/\kappa^{2}\right)$ close to the saddle point after $n$ steps. Liang and Stokes, (2019) extend this result to a general function $f(x,y)$ which is strongly convex in $x$ and strongly concave in $y$ (achieving the same rate of convergence as Du and Hu, (2019)). Several other gradient based algorithms like the Optimistic Gradient Descent Ascent (OGDA) method (see Daskalakis et al., (2018)) and the Extragradient method Korpelevich, (1976) have been analyzed in recent papers including Mokhtari et al., 2019b ; Liang and Stokes, (2019); Gidel et al., (2019); Mokhtari et al., 2019a ; Hsieh et al., (2019). These papers analyze these algorithms in several settings including bilinear, strongly convex-strongly concave and convex-concave. More specifically, Gidel et al., (2019); Mokhtari et al., 2019b show that when the objective function is strongly convex-strongly concave, running the OGDA and Extragradient algorithms for $n$ steps reaches a point which is $\mathcal{O}(1)\exp(-\Theta(1)n/\kappa)$ close to the saddle point.

1.2 Stochastic Case

The papers which are closest to our results are Rosasco et al., (2014) and Hsieh et al., (2019). Rosasco et al., (2014) propose a forward-backward splitting algorithm to solve the stochastic minimax problem (they solve the more general problem of monotone inclusions). When the function is strongly convex-strongly concave, they show convergence at a rate of $\mathcal{O}(\|z_{0}-z^{*}\|^{2}/n^{p}+\sigma^{2}c^{p}/{n})$ to the saddle point, where $p$ is any constant greater than and $c$ is a constant larger than 1. Hsieh et al., (2019) show that the stochastic version of OGDA converges to the saddle point at a rate of $\mathcal{O}(\frac{1}{n})$ for both bias and variance when the objective function is strongly convex-strongly concave.

There are several papers which analyze the stochastic minimax problem when the objective function is convex-concave. Juditsky et al., (2011) propose the stochastic mirror-prox algorithm (a special case of which is the stochastic extragradient method) to solve the convex-concave saddle point problem with noisy gradients. They assume the constraint set is compact and show a convergence rate of $\mathcal{O}(1/\sqrt{n})$ (the result in this paper improves on the robust stochastic approximation algorithm proposed in Nemirovski et al., (2009)). Chen et al., (2014) proposes an accelerated primal dual algorithm which achieves a convergence rate of $\mathcal{O}(1/\sqrt{n})$. Recently, Mertikopoulos et al., (2018) analyzed the stochastic extragradient algorithm for coherent minimax problems (a condition slightly weaker than convex-concave assumption) and they show asymptotic convergence to a saddle point. Gidel et al., (2019) analyzed a single call version of extragradient (which corresponds to OGDA) when the function is convex-concave and they showed that in the stochastic setting, this algorithm converges to the saddle point at a rate of $\mathcal{O}(1/\sqrt{n})$.

Another line of work is the case where the objective function has a finite sum structure and the gradient of the entire function cannot be computed at each step. Several papers including Bot et al., (2019); Palaniappan and Bach, (2016); Chavdarova et al., (2019); Iusem et al., (2017) analyze this setting and apply variance reduction techniques (like SVRG and SAGA) to improve convergence rates to the saddle point.

2 Our Contribution

We first analyze GDA with constant stepsize (learning rate) where we build our analysis by casting it as a dynamical system, an approach that has gained attention in the optimization and machine learning literature recently Lessard et al., (2016); Hu and Lessard, (2017); Aybat et al., (2018, 2019). In particular, we show that GDA with any stepsize $\alpha\leq\mu/(4L^{2})$ converges to an $\mathcal{O}(\alpha)$ neighborhood of the optimal solution at a linear rate $\exp(-\alpha\mu k)$. Next, we propose a novel Multistage-Stochastic Gradient Descent Ascent scheme (inspired from Aybat et al., (2019)) which achieves a rate of $\mathcal{O}({\sigma^{2}}/{n})$ for the variance term (which is optimal in terms of $n$ dependence) and a rate of $\mathcal{O}(1)\exp(-\Theta(1)n/\kappa^{2})$ for the bias term, and we show that the $n$ and $\kappa$ dependence of the latter cannot be improved for GDA dynamics.

Next, we focus on the OGDA method which has gained widespread attention for solving minimax problems. We first highlight that OGDA also converges to an $\mathcal{O}(\alpha)$ neighborhood of the optimal solution with linear rate $\exp(-\alpha\mu k)$, but allows for a broader range of $\alpha\leq 1/(8L)$ for the stepsize. Then, we introduce the Multistage version of Stochastic Optimistic Gradient Descent Ascent (M-OGDA) which achieves the rate of $\mathcal{O}({\sigma^{2}}/{n})$ for the variance term and a rate of $\mathcal{O}(1)\exp(-\Theta(1)n/\kappa)$ for the bias term which improves on the $\mathcal{O}(1)\exp(-\Theta(1)n/\kappa^{2})$ decay of the bias term of GDA and matches the lower bound shown in Ibrahim et al., (2019).

3 Notation

Preliminaries

We first state formally the strong convexity(concavity) and smoothness properties of a function.

Further, $\phi(x)$ is $\mu$-strongly concave if $-\phi(x)$ is $\mu$-strongly convex.

For an $L-$smooth convex function $\phi(\cdot)$, we have the following characterization (see Theorem 2.1.5 in Nesterov, (2004)):

Throughout the paper, we assume the following:

In addition, we assume $\zeta$ and $\xi$ are independent from each other and previous iterates. Moreover, we assume

To simplify the notation, we suppress the $\zeta$ and $\xi$ dependence throughout the paper.

In addition, the gradient $\nabla_{x}f(x,y)$ is $L_{xy}$-Lipschitz in $y$, i.e.,

Similarly, the gradient $\nabla_{y}f(x,y)$ is $L_{yx}$-Lipschitz in $x$, i.e.,

Note that this assumption leads to the saddle point $(x^{*},y^{*})$ being unique and, in addition, we have $\nabla_{x}f(x^{*},y^{*})=0$ and $\nabla_{y}f(x^{*},y^{*})=0$.

Under Assumptions 2.3, we call the function $f(\cdot,\cdot)$ as $L$-smooth and $\mu$-strongly convex- strongly concave where $\mu=\min\{\mu_{x},\mu_{y}\}$ and $L=\max\{L_{x},L_{y},L_{xy},L_{yx}\}$. We define the condition number of the problem as $\kappa\triangleq L/\mu$.

We next present some key properties of smooth strongly convex-strongly concave functions that will be used in our analysis. Define:

Also, we define $z^{*}\triangleq({x^{*}}^{\top},{y^{*}}^{\top})^{\top}$ as the unique saddle point. The following lemma follows from the strong convexity and smoothness properties of $f$.

Using Lemma 2.5, we can prove the following result

Using Lemmas 2.5 and 2.6, we immediately obtain the following result which we state in the form of a matrix inequality since this form is more convenient for subsequent analysis.

Analysis of Stochastic Gradient Descent Ascent Method

In this section, we study the Stochastic Gradient Descent Ascent (GDA) algorithm, which is given by:

where $z_{k}=(x_{k}^{\top},y_{k}^{\top})^{\top}$ and

Using this notation, we can represent GDA as a dynamical system as follows:

Let $P=p\otimes I_{m+n}$ with $p\geq 0$ and consider the function $V_{p}(z)=(z-z^{*})^{\top}P(z-z^{*})$. Then we have

Next, using this lemma, we characterize the convergence of GDA.

Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Let $\{z_{k}\}$ be the iterates generated by GDA (12) with $0<\alpha\leq\frac{\mu}{4L^{2}}$. Then, for any $k\geq 1$, we have

As a result, the error of GDA after $k$ steps is bounded by

It is worth noting that the range for the stepsize $\alpha$ in Theorem 3.2 is upper bounded by $\mu/4L^{2}$ (as opposed to just a function of the Lipschitz parameter $L$, as is the case for Gradient Descent in minimization problems). This is consistent with the fact that GDA may diverge when the strong convexity parameter $\mu$ is 0, i.e., the function is convex-concave (see the Bilinear example in Daskalakis et al., (2018)).

In this subsection, we give an example of a function where after running GDA for $n$ iterations reaches a point which is $\mathcal{O}(1)\text{exp}\left(-\Theta(1)n/\kappa^{2}\right)$ close to the saddle point. Consider the function

Let $\{x_{k},y_{k}\}$ be the iterates generated by GDA for the objective function given in Equation (18). Then, (i) if the gradient at each step is exactly available (i.e. the updates reduce to the deterministic GDA updates), we have:

(ii) if at each step the gradients are corrupted by additive i.i.d. noise with a distribution $\mathcal{N}(0,\sigma^{2})$, we have

Example 3.4(i) shows that in order to find the saddle point of the function $f$ defined in equation (18), we need to run at least $\mathcal{O}(\kappa^{2}\log(1/\epsilon))$ steps of GDA (i.e. the deterministic case) to reach a point which is $\epsilon$-close to the solution, showing that this dependence on $\kappa$ cannot be improved. Example 3.4(ii) shows that when the gradients are corrupted by noise with variance $\sigma^{2}$, GDA reaches an $\mathcal{O}(\alpha)$ neighborhood of the saddle point and this dependence on $\alpha$ cannot be improved.

A Multistage Stochastic Gradient Descent Ascent Method (M-GDA)

Our result in Theorem 3.2 shows that for GDA with constant stepsize $\alpha$, the iterates converge to an $\mathcal{O}(\alpha)$ neighborhood of the saddle point. In this section, we introduce a new method which is a variant of GDA with progressively decreasing stepsize that converges to the exact unique saddle point of problem 1. Our proposed algorithm, Multistage Stochastic Gradient Descent Ascent (M-GDA), which is presented in Algorithm 1, runs in several stages where each stage is the GDA method with constant stepsize. In what follows, we show our multistage method with a carefully chosen learning rate and step length evolution achieves linear decay in the bias term as well as optimal variance dependence without any knowledge of the noise properties.

Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Let $\{(x_{m}^{k},y_{m}^{k})_{m=0}^{n_{k}}\}_{k=1}^{K}$ be the iterates generated by M-GDA (Algorithm 1) with the following parameters

where $p\geq 2$ is an arbitrary positive number. Then, for any $k\geq 1$, we have

where $z_{m}^{k}=((x_{m}^{k})^{\top},(y_{m}^{k})^{\top})^{\top}$ for any $0\leq m\leq n_{k}$.

First, and for $k=1$, note that, by using Theorem 3.2 along with the fact that $1-\alpha\mu\leq\exp(-\alpha\mu)$, we have:

where we plugged in $\alpha_{1}=\frac{\mu}{4L^{2}},n_{1}\geq 1$ to obtain the last equality. Hence, the result holds for $k=1$. Now, assume the result holds for $k$, and we show it for $k+1$. Note that, Theorem 3.2 for stage $k+1$ yields:

where we used $\alpha_{k+1}=\mu/(L^{2}2^{k+3})$ and $n_{k+1}\geq p2^{k+3}\kappa^{2}\log(2)$ to derive the last inequality. Now, note that, by induction hypothesis, we have

Substituting this bound in (23), we obtain

where the last bound follows from $p\geq 2$. This completes the proof. ∎

The above theorem provides an upper bound on the distance of the last iterate of each stage to the saddle point of problem (1). Using this result, and in the following corollary, we provide an upper bound on the distance of any iterate from the saddle point. Before stating this corollary, let $\{z_{n}\}_{n}$ be the sequence which is obtained by concatenating the $\{(x_{m}^{k},y_{m}^{k})_{m=0}^{n_{k}}\}_{k=1}^{K}$ sequences, i.e.,

Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Consider running M-GDA (Algorithm 1) with the parameters given in Theorem 4.1. Also, recall the definition of the concatenated sequence $\{z_{n}\}$ from (28). Then, for any $n>n_{1}$, we have

We interpret this result in two different regimes. First, we consider the case where we are given a fixed budget of $n$ iterations. In this case, the following corollary shows how we can tune the parameters to obtain linear decay in the bias term as well as $\mathcal{O}(1/n)$ reduction in the variance term. We omit the proof as it is an immediate application of Corollary 4.2.

Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Consider running M-GDA (Algorithm 1) with the parameters given in Theorem 4.1 and $p=2,n_{1}=\frac{n}{C}$ with $C\geq 2$. Also, recall the definition of the concatenated sequence $\{z_{n}\}$ from (28). Then, for any $n\geq 2\kappa^{2}$, we have

Finally, in the following corollary, we illustrate how our results can be applied to the case where we do not know the number of iterations in advance.

Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Consider running M-GDA (Algorithm 1) with the parameters given in Theorem 4.1 and $n_{1}=\lceil 4p\kappa^{2}\log(p\kappa^{2})\rceil$ for an arbitrary $p\geq 2$. Also, recall the definition of the concatenated sequence $\{z_{n}\}$ from (28). Then, for any $n\geq 2n_{1}$, we have

It is worth noting that the results in Corollaries 4.3 and 4.4 are presented in terms of the $n^{th}$ iterate $z_{n}$ which is obtained by concatenating the iterates of all stages, including inner iterations (as given in (28)). In fact, while it is true that the number of inner stage iterations increases, the bounds in Table 1 and Corollaries 4.3 and 4.4, are all based on the total number of iterations, and therefore, they take into account the inner stage iterations.

A Multistage Stochastic Optimistic Gradient Descent Ascent Method (M-OGDA)

As we showed in previous Section, M-GDA achieves the optimal variance rate $\mathcal{O}(\sigma^{2}/n)$ as well as linear decay $\mathcal{O}(1)\exp(-\Theta(1)n/\kappa^{2})$ in the bias term. However, the dependence of the latter to condition number $\kappa$ is suboptimal compared to the lower bound presented in Ibrahim et al., (2019). Therefore, a natural question is whether we can design an algorithm which matches the lower bound for the bias term while simultaneously enjoying the optimal variance decay. In this section, we show that this is possible, and we do so by applying the multistage machinery to the stochastic Optimistic Gradient Descent Ascent (OGDA) algorithm. In this section, we first revisit the existing results on convergence of stochastic OGDA method, and next, show how its multistage version (M-OGDA) can matches both lower bounds simultaneously.

Note that the difference from Extragradient (EG) is that in EG, the update for $z_{k+1}$ involves the gradient at $w_{k}$ whereas here we use the gradient at $z_{k}$ instead. We will use this form of the Stochastic OGDA updates for our analysis. From the analysis The analysis in Hsieh et al., (2019) is for the case of additive noise. However, it can be easily extended to our setting by conditioning and using the tower rule on the current iterate. of Theorem $5$ in Hsieh et al., (2019), we have the following result for Stochastic OGDA:

(Hsieh et al., (2019)) Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Let $\{z_{k},w_{k}\}_{k}$ be the iterates generated by Stochastic OGDA with $0<\alpha\leq\frac{1}{8L}$. Then, for any $k\geq 1$, we have

This is similar to Theorem 3.2 for GDA. However, we can see that for OGDA, the range of permissible stepsizes goes all the way up to $\mathcal{O}(1/L)$ whereas for GDA, the stepsizes are upper bounded by $\mathcal{O}(\mu/L^{2})$.

The result in Theorem 5.1 shows that for OGDA with constant stepsize $\alpha$, the iterates converge to an $\mathcal{O}(\alpha)$ neighborhood of the saddle point. Next, we analyze a multistage version of OGDA (M-OGDA) similar to the analysis of M-GDA in Section 4. We show that the iterates of M-OGDA converge to the unique saddle point at a rate where the variance decays as $\mathcal{O}(\sigma^{2}/n)$, which is optimal (and also achieved by M-GDA), but the bias term decays as $\mathcal{O}(1)\exp(-n/\Theta(\kappa))$, which "accelerates" GDA in terms of its dependence on $\kappa$. More formally, we state the following theorem which is analogous to Theorem 4.1 for M-GDA and present the convergence rate of M-OGDA (we omit the proof as it is very similar to that of Theorem 4.1):

Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Let $\{(w_{m}^{k},z_{m}^{k})_{m=0}^{n_{k}}\}_{k=1}^{K}$ be the iterates generated by M-OGDA (Algorithm 2) with the following parameters

where $p\geq 2$ is an arbitrary positive number. Then, for any $k\geq 1$, we have

Similar to the discussion in Section 4, we next state how our result leads to bounds on distance of each iterate to the saddle point of Problem 1. In addition, we propose proper choice of parameters in general as well as in the case that the iteration budget is known in advance, the results corresponding to Corollaries 4.2 and 4.4 for M-GDA. Before stating this corollary, we define $\{w_{n}\}_{n}$ to be the sequence which is obtained by concatenating the $\{(w_{m}^{k})_{m=0}^{n_{k}}\}_{k=1}^{K}$ sequences, i.e.,

Suppose that the conditions in Assumptions 2.2 and 2.3 are satisfied. Let $\{(w_{m}^{k},z_{m}^{k})_{m=0}^{n_{k}}\}_{k=1}^{K}$ be the iterates generated by M-OGDA (Algorithm 2) with the parameters given in Theorem 4.1. Also, recall the definition of the concatenated sequence $\{w_{n}\}$ from (35). Then, for any $n>n_{1}$, we have

In particular, assume choosing $n_{1}=\lceil 8p\kappa\log(p\kappa^{2})\rceil$. Then, for any $n\geq 2n_{1}$, we have

Also, when the number of iterations $n$ is known in advance, choosing $p=2,n_{1}=\frac{n}{C}$ with $C\geq 2$, implies

Once again, we would like to highlight that the results in Corollary 5.3 are presented in terms of the $n^{th}$ iterate $w_{n}$ which is obtained by concatenating the iterates of all stages, including inner iterations (as given in (35)). As a result, in comparing our results to other methods in Table 1, we take into account the inner stage iterations.

Conclusion

In this paper, we propose multistage versions of Gradient Descent Ascent (GDA) and Optimistic Gradient Descent Ascent (OGDA) algorithms to solve the stochastic minimax problems. In particular, these algorithms are the first to achieve linear rate in bias and optimal $\mathcal{O}(\sigma^{2}/n)$ rate in variance, simultaneously. We also show that Multistage OGDA improves the bias rate of Multistage GDA from $\mathcal{O}(\exp(-\Theta(1)n/\kappa^{2}))$ to $\mathcal{O}(\exp(-\Theta(1)n/\kappa))$ which is the best known rate in deterministic minimax optimization.

References

Appendix A Proof of Lemma 2.5

Adding equations (40) and (41), and noting that

we obtain the right hand side of (9). Similarly, we have:

Adding equations (44) and (45) we obtain the left hand side of (9).

Appendix B Proof of Lemma 2.6

Combining Equation (46) and (46), we have:

Appendix C Proof of Theorem 3.2

First, note that for $\rho^{2}=1-\alpha\mu$ and $P=p\otimes I_{m+n}$ with $p=1/\alpha$, we have

where the last inequality follows from the fact that $\alpha\leq\mu/(4L^{2})$. This result implies

Substituting left and right hand side by using Corollary 2.7 and Lemma 3.1, respectively, yields

Finally, dividing both sides by $p$ completes the proof (16). To show the second result, note that by using (16) sequentially, we have

Appendix D Proof of Example 3.4

The gradient at step $k$ is corrupted by noise $\xi_{k}^{x}$ and $\xi_{k}^{y}$ which we assume to be iid $\sim\mathcal{N}(0,\sigma)$. The GDA method when applied to this problems leads to:

which proves the first part of the lemma. Note that when the gradients are not corrupted by noise (i.e. when $\sigma=0$, we have)

The coefficient on the right side is minimized for $\alpha=\frac{\mu}{\mu^{2}+L^{2}}$. Substituting this in equation (52), we get:

Now, making the substitution $\kappa=\frac{L}{\mu}$, we have:

Therefore, for any other stepsize $\alpha>0$, we have:

Appendix E Proof of Corollary 4.2

Let us define $T(k):=\sum_{i=1}^{k}n_{i}$. Note that, for $k\geq 2$, the fact that $\lceil x\rceil\leq 2x$ for positive $x$ implies:

As a consequence, and using $\sum_{i=2}^{k}2^{i+2}=16(2^{k-1}-1)$, we have

Now, let $k$ be the largest number such that $T(k)<n$, i.e., $T(k)<n\leq T(k+1)$. Thus, using (58), we obtain

where the constants in $\Theta(1)$ are independent of problems’ parameters.

Also, by Theorem 3.2 for stage $k+1$, we have

where the last inequality follows from (61). Now, plugging in (60) in this bound completes the proof.