Title: UNDERSTAND THE DYNAMICS OF GANS VIA PRIMAL-DUAL OPTIMIZATION

Abstract: Generative adversarial network (GAN) is one of the best known unsupervised learning techniques these days due to its superior ability to learn data distributions. In spite of its great success in applications, GAN is known to be notoriously hard to train. The tremendous amount of time it takes to run the training algorithm and its sensitivity to hyper-parameter tuning have been haunting researchers in this area. To resolve these issues, we need to first understand how GANs work. Herein, we take a step toward this direction by examining the dynamics of GANs. We relate a large class of GANs including the Wasserstein GANs to max-min optimization problems with the coupling term being linear over the discriminator. By developing new primal-dual optimization tools, we show that, with a proper stepsize choice, the widely used first-order iterative algorithm in training GANs would in fact converge to a stationary solution with a sublinear rate. The same framework also applies to multi-task learning and distributional robust learning problems. We verify our analysis on numerical examples with both synthetic and real data sets. We hope our analysis shed light on future studies on the theoretical properties of relevant machine learning problems.

1. INTRODUCTION:

Since it was first invented by Ian Goodfellow in his seminal work Goodfellow et al. (2014) , generative adversarial networks (GANs) have been considered as one of the greatest discoveries in machine learning community. It is an extremely powerful tool to estimate data distributions and generate realistic samples. To train its implicit generative model, GAN uses a discriminator since traditional Bayesian methods that require analytic density functions are no longer applicable. This novel approach inspired by zero sum game theory leads to a significant performance boost; GANs are able to generate samples in a fidelity level that is way beyond traditional Bayesian methods. During the last few years, there have been numerous research articles in this area aiming at improving its performance (Radford et al., 2015; Zhao et al., 2016; Nowozin et al., 2016; Arjovsky et al., 2017; Mao et al., 2017) . GANs have now become one of most recognized unsupervised learning techniques and have been widely used in a variety of domains such as image generation (Nguyen et al., 2017) , image super resolution (Ledig et al., 2017) , imitation learning (Ho & Ermon, 2016) .

Despite the great progress of GANs, many essential problems remain unsolved. Why is GAN so hard to train? How to tune the hyper-parameters to reduce instability in GAN training? How to eliminate mode collapse and fake images that show up frequently in training (Arjovsky & Bottou, 2017) ? Comparing with many other machine learning techniques, the properties of GANs are far from being well understood. It is quite likely that the theoretical foundation of GANs will become a longstanding problem. The theoretical difficulty of GANs mainly lies in the following several aspects. First, it is a non-convex optimization problem with a complicated landscape. It is unclear how to solve such optimization problems efficiently. The first-order method widely used in the literature via updating the generator and discriminator along descent/ascent direction does not seem to converge all the time. Although some techniques were proposed to stabilize the training performance of the network, e.g., spectral normalization Miyato et al. (2018) , in fact, there is no evidence that these algorithms guarantee even local optimality. Second, even if there were an efficient algorithm to solve this optimization problem, we do not know how well they generalize. After all, the optimization formulation is based only on the samples generated by the underlying distribution but our goal is to recover this underlying distribution. Of course, this is a problem faced by all machine learning techniques. Last, there are no reliable ways to evaluate the quality of trained models. There are a number of works in this topic (Salimans et al., 2016; Heusel et al., 2017) , but human eyes inspection remains the primary approach to judge a GAN model.

In the present work, we focus on the first problem and analyze the dynamics of GANs from an optimization point of view. More precisely, we study the convergence properties of the first-order method in GAN training. Our contributions can be summarized as follows. 1) We formulate a large class of GAN problems as a primal-dual optimization problem with a coupling term that is linear over discriminator (see Section 2 for the exact formulation); 2) We prove that the simple primal-dual first-order algorithm converges to a stationary solution with a sublinear convergent rate O(1/t).

There have been a number of papers that study the dynamics of GANs from an optimization viewpoint. These works can be roughly divided into three categories. In the first category, the authors focus on high level idea using nonparametric models. This includes the original GAN paper Goodfellow et al. (2014) , the Wasserstein GAN papers Arjovsky & Bottou (2017) ; Arjovsky et al. (2017) and many other works proposing new GAN structures. In the second category, the authors consider the unrolled dynamics (Metz et al., 2016) , that is, the discriminator remains optimal or almost optimal during the optimization processes. This is considerably different to the first-order iterative algorithm widely used in GAN training. Recent works Heusel et al. (2017) ; Li et al. (2017) ; Sanjabi et al. (2018) provide global convergence analysis for this algorithm.

The last category is on the first-order primal-dual algorithm, in which both the discriminator and the generator update via (stochastic) gradient descent. However, most of the convergence analysis are local (Daskalakis et al., 2017; Mescheder et al., 2017; Nagarajan & Kolter, 2017; Li et al., 2018) . Other related work including the following: In Qian et al. ( 2018) the authors consider a gradient descent/ascent algorithm for a special min-max problem arising from robust learning (min problem is unconstrained, max problem has simplex constraints); In Yadav et al. (2018) the GANs are treated as convex-concave primal-dual optimization problems. This formulation is considerably different to our setup where GANs, as they should be, are formulated as nonconvex saddle point problems. In Farnia & Tse (2018) , the authors investigated the properties of the optimal solutions, which is also different from our work focusing on convergence analysis of the first-order primal-dual algorithm. In Zhao et al. (2018) , some unified framework covering several generative models, e.g., VAE, infoGAN, were proposed in the Lagrangian framework. However, the dual variable in their problem is a Lagrangian multiplier, while in our problem, it is the discriminator of GAN. Besides, the focus of their paper is not the optimization algorithm. In Chen et al. (2018) , the authors related a class of GANs to constrained convex optimization problems. More specifically, such GANs can be viewed as Lagrangian forms of these convex optimization problems. The optimization variables in their formulation are the probability density of the generator and the function values of the discriminator. Many issues like nonconvexity do not show up. This is essentially a nonparametric model, which doesn't apply to cases when the discriminator and the generator are represented by parametric models. On the other hand, our analysis is carried out on the parametric models directly and we have to deal with the nonconvexity of neural networks. In Hajinezhad & Hong (2017) a primal-dual algorithm has been studied for a non-convex linearly constrained problem (which can be reformulated into a min-max problem, with the max problem being linear and unconstrained, and with linear coupling between variables); In Hamedani & Aybat (2018) , (Chen et al., 2013) and the references therein, first-order methods have been developed for convex-concave saddle point problems. Compared to these works, our considered problem is more general, allowing non-convexity and non-smoothness in the objective, non-convex coupling between variables, and can further include constraints. Moreover, we provide global convergence rate analysis, which is much stronger than the local analysis mentioned above.

It turns out that the primal-dual framework we study in this paper can also be applied to the distributional robust machine learning problems (Namkoong & Duchi, 2016) and the multi-task learning problems (Qian et al., 2018) . In multi-task learning, the goal is to train a single neural network that would work for several different machine learning tasks. Similarly, in distributional robust learning, the purpose is to have a single model that would work for a set of data distributions. In both problems, an adversarial layer is utilized to improve the worst case performance, which leads to a primal-dual optimization structure that falls into the scope of problems we consider.

The rest of the paper is structured as follows. In Section 2 we introduce GAN and its primal-dual formulation. We provide details of the algorithms with proof sketches in Section 3. The full proofs are relegated to the appendix. We highlight our theoretical results in Section 4 via several numerical examples, with both synthetic and real datasets.

2. GENERATIVE ADVERSARIAL NETWORKS AND MIN-MAX PROBLEMS:

GAN is a type of deep generative model with implicit density functions. It consists of two critical components: a generator and a discriminator. The generator takes random variables with known distribution as input and outputs fake samples. The discriminator is trained to distinguish real samples and fake samples.

2.1. GANS:

In the original form of GAN, the generator is a neural network and the discriminator is a standard classifier with cross entropy cost. Denote the underlying probability distributions of the data sample {y i } ny i=1 ⊂ R d and the random seed x (a random variable in R k ) of the generative model by P y and P x respectively. The original or vanilla GAN is of the form (Goodfellow et al., 2014) min

G∈G max F ∈F {E(log(F (y))) -E(log(1 -F (G(x))))}.

(1)

Here G stands for the set of possible generators and F the set of possible discriminators.

There have been numerous modifications of the original GAN, among which the Wasserstein GAN (Arjovsky et al., 2017) attracts a lot of attention. It has the form

EQUATION

where G is the set of parameterized generators and F is the set of Lipschitz functions with Lipschitz constant 1. This is a special case of a more general class of GANs with the same structure but different constraint set F. The inner maximization loop defines different notions of integral probability metrics (Müller, 1997) depending on the choices of F. Other than Wasserstein GAN, one interesting example with this structure is the generative moment matching networks (Li et al., 2015; Arjovsky et al., 2017) .

Wasserstein GAN can be extended to general optimal transport cost c(x, y), which results in saddle point formulation

EQUATION

Note that the discriminator now becomes two functions ψ, φ instead of one. When c(x, y) = x -y , the above reduces to the standard Wasserstein GAN in equation 2.

2.2. NONCONVEX MIN-MAX PROBLEMS:

We observe that, compared to vanilla GAN in equation 1, the Wasserstein GAN in equation 2 and equation 3 has a special structure. In the nonparametric form, the coupling between the generator G and the discriminator F is linear on F in Wasserstein GAN while nonlinear in vanilla GAN. Indeed, replacing F by αF 1 + βF 2 in the coupling term E(F (G(x))) yields

E(F (G(x))) = E((αF 1 + βF 2 )(G(x))) = αE(F 1 (G(x))) + βE(F 2 (G(x))).

This structure motivates us to study the following min-max primal-dual optimization problem

EQUATION

with l being strictly convex. the other two functions h and g can be non-convex. Here Y represents the discriminator F and X represents the generator G. Note that the coupling term g(X), Y is linear over the discriminator Y , but nonlinear in X.In real applications, we need to parameterize the discriminator and generator, which may lead to the loss of the property that the coupling is linear over discriminator. Next, we present several cases where this linear structure stays.

2.2.1. WASSERSTEIN GAN IN LQG SETTING:

Wasserstein GAN in linear quadratic Gaussian (LQG) setting was proposed in Feizi et al. (2017) to understand GAN. In this simplified case, the data distribution is Gaussian, the cost is quadratic and the generator is linear, namely,

c(x, y) = 1 2 x -y 2 , y ∼ N (0, Σ y ), x ∼ N (0, I k ), G(x) = θx.

It can be shown that it suffice to consider discriminator of the form

φ(x) = 1 2 x 2 - 1 2 x T Ax, ψ(y) = 1 2 y 2 - 1 2 y T By

with A, B being positive definite.

The constraint φ(x) + ψ(y) ≤ 1 2 x -y 2 implies that B A -1 . Consequently, the discriminator can be parametrized by a single variable A 0. Additionally, G(x) is a zero mean Gaussian random variable with covariance θθ T . Therefore, the Wasserstein GAN in equation 3 then reduces to

EQUATION

which is apparently in the form of equation 4. When only samples {x i } n i=1 , {y i } n i=1 of x, y are available, this becomes

EQUATION

2.2.2. GANS WITH DISCRIMINATORS LINEAR ON FEATURES:

In general quadratic discriminators are not sufficient to distinguish complicate high dimension distributions. In order to deal with more general data sets, we consider the setting where the discriminator is a linear combination of predefined basis functions. More specifically, let {F i } n i=1 be the basis functions, and F = α i F i with some constraint on α, then the above formulation becomes

EQUATION

)

Here the term λ α 2 with λ > 0 is used to regularize α, or equivalently, the discriminator.

Similarly, for GAN structure in equation 3, we can restrict our discriminators φ and ψ to be linear combinations of basis functions

{φ i } n i=1 and {ψ i } n i=1 , that is, φ = α i φ i , ψ = β i ψ i . The constraint φ(x) + ψ(y) ≤ c(x,

y) in equation 3 is difficult to impose precisely. Instead, we use a regularization term l and obtain

EQUATION

Clearly, both equation 7 and equation 8 are of the form equation 4. We remark that no constraint has been imposed on the generator G; it can be any general neural network. The requirement that the discriminator is a linear combination of predefined basis functions could be strong, but in principle, any function can be approximated to an arbitrary precision with large enough bases.

3. ALGORITHM DESIGN AND CONVERGENCE ANALYSIS:

In this work, we consider the following general min-max problem,

min X∈X max Y ∈Y f (X, Y ) 1 n n i=1 (h i (X) + g i (X), Y -l i (Y )) (9)

where X is a convex and compact set and the size of X is upper bounded by σ X ; h i (X) : R d → R, ∀i is a non-convex function and has Lipschitz continuous gradient with constant L X ; l i (Y ) : R d → R, ∀i are strongly convex with modulus γ > 0 and Lipschitz gradient constant L Y ; the matrix function g i (X) : X → dim(Y ) can also be non-convex, and it is assumed to be Lipschitz and Lipschitz gradient continuous with constants L g,1 and L g,2 . We note that regardless of whether Y is a bounded set or not, one can show that for all x ∈ X , the maximizer Y * for the maximization problem lies in a bounded set; see Lemma 3 in the appendix for proof.

We note that by allowing constraints in the form of x ∈ X , and y ∈ Y, one can also include nonsmooth regularizers in the formulation. As an example, if we add λ X 1 into the objective function, one can introduce a new variable z, and consider an equivalent problem with the constraints X 1 ≤ z, with the objective function changed to

1 n n i=1 (h i (X) + g i (X), Y -l i (Y )) + z.

The above formulation is quite general. Compared with the existing convex-concave saddle point literature (Hamedani & Aybat, 2018) , (Chen et al., 2013) , our formulation allows non-convexity in the minimization, which is essential to modelling the neural network structure of generators in GANs and general non-convex supervised tasks in multi-task learning; Compared with the non-convex linearly constrained problems considered in (Hajinezhad & Hong, 2017) , it further allows non-linear and non-convex function g(X) to couple with Y . Compared with the robust learning formulation given in equation 18, equation 9 can further include constraints and nonsmooth objective functions (thus can include nonsmooth regularizers such as 1 norm).

It is important to note that due to the generality of problem equation 9, developing performance guaranteed first-order method, which only utilizing the gradient information about functions h i , g i , l i is very challenging. To the best of our knowledge, there has been no such algorithm that can provably compute even first-order stationary solutions for problem equation 9.

3.1. ALGORITHM DESCRIPTION:

Our proposed gradient primal-dual algorithm of solving equation 9 is listed below, in which we alternatingly perform first-order optimization to update X and Y :

EQUATION

Y r+1 = arg max Y ∈Y - 1 n n i=1 ∇ Y l i (Y r ) + g i (X r+1 ), Y -Y r - 1 2ρ Y -Y r 2 .

To be consistent with the optimization literature, we will refer to the X-step the "primal step" and the Y -step as the "dual step". We note that 1/β and ρ are two positive parameters, that represent stepsizes of the two updates, and both of them should be small. A few remarks are ready.

Remark 1 (projected gradient). It can be easily verified that the updates of X r and Y r can be written down in closed form using the following alternating projected gradient descent/ascent steps:

X r+1 = proj X X r - 1 β 1 n n i=1 (∇ X h i (X r ) + ∇ X Tr(g i (X r )Y r )) , Y r+1 = proj Y Y r + ρ 1 n n i=1 ∇ Y l i (Y r ) + g i (X r+1

) .

Remark 2 (stochastic vs deterministic algorithm). This work will be focused on the deterministic algorithm given in equation 10, because such an algorithm is representative of the primal-dual first-order dynamics used in training GANs and optimizing robust ML problems, and it is already challenging to analyze. However, we do want to remark that, it is relatively straightforward to build upon our proof, by incorporating the standard technique in stochastic constrained optimization (Ghadimi et al., 2016 ) (such as using decreasing stepsizes, and certain randomization rule in picking the final solutions), to analyze the stochastic version of the algorithm, in which mini-batches of the component functions are randomly selected to update at each iteration. However, in order to keep the discussion of the paper simple, we choose not to present such results.

3.2. CONVERGENCE ANALYSIS:

In this section, we present our main convergence results for the primal-dual first-order algorithm given in equation 10. We first present a few necessary lemmas. Lemma 1. (Descent Lemma) Let (X r , Y r ) be a sequence generated by equation 10. The descent of the objective function can be quantified by

EQUATION

)

From Lemma 1, it is not clear whether the objective function is decreased or not, since the primal step will consistently decrease the objective value while the dual step will increase the objective value.

The key in our analysis is to identify a proper "potential function", which can capture the essential dynamics of the algorithm, and will be able to reduce in all iterations. Lemma 2. When the following conditions are satisfied,

ρ < γ L 2 Y , β ≥ max L g,1 + (L Y + L g,1 + 1 ρ )((6σ Y + 1)L X + L g,2 + 2ρL 2 g,1 ) γ -ρL 2 Y , L X + σ Y L g,2

(12) then there exist c 1 , c 2 , c 3 , d > 0 such that potential function will monotonically decrease, i.e.,

EQUATION

where P r+1 f (X r+1 , Y r+1 ) + dQ r+1 and

Q r+1 L X (σ Y + 1) 2β + 1 2 X r+1 -X r 2 + 1 2ρβ - γ -ρL 2 Y 2β Y r+1 -Y r 2 .

To state our main result, let us define the proximal gradient of the objective function as

EQUATION

where proj denotes the convex projection operator. Clearly, when ∇L(X, Y ) = 0, then a first-order stationary solution of the problem equation 4 is obtained.

Theorem 1. Suppose that the sequence (X r , Y r ) is generated by equation 10 and ρ, β satisfy the conditions equation 12. For a given small constant , let T ( ) denote the iteration index satisfying the following inequality

EQUATION

)

Then there exists some constant C > 0 such that

EQUATION

where P denotes the lower bound of P r .

The above result shows that our proposed algorithm converges to the first-order stationary point of the original problem in a sublinear rate.

4. EXPERIMENTS:

We conduct several experiments to illustrate our results. The first two examples are on GANs with both synthetic data and MNIST dataset, and the last one (supplemental material) is on multi-task learning with real data. Our intention is by no means to show our algorithm generates superior samples than other methods. Our main goal is to show that our first-order primal-dual algorithm would converge at least to a local solution. All experiments are implemented on a NVIDIA TITAN Xp. In the LQG setting, as discussed in Section 2.2.1, the generator is modeled by a linear map G(x) = θx with parameter θ and the discriminator is parametrized by a positive definite matrix A. The seed x is a zero-mean random variable with unit covariance. We randomly generate a positive definite matrix Σ y as our covariance of the data samples. The solution to this GAN problem satisfies A = I, θθ T = Σ y .

We implement our algorithm with different step-sizes. The results are shown in Figure 1 for 20 dimensional data, from which we see that the algorithm converges when the step-size is sufficiently small, while diverges for a large step-size. We also compare our algorithm with the one proposed in Sanjabi et al. (2018) , which requires solving the inner maximization problem in each iteration. As can be seen from the last plot of Figure 1 , while these two algorithms take a similar number of iterations to converge, the total time consumption is more for Sanjabi et al. (2018) as it takes more time to solve the maximization problem than to update the parameter one step along the gradient direction. A detailed comparison is given in Table 1 . To visualize the effectiveness of LQG GAN, we consider the problem in 2 and 3 dimensional spaces.

We plot the samples corresponding to both the learned and the real covariance matrices in Figure 2 . Clearly, the learned models match the underlying truth. We test the GANs framework with discriminators linear on features (discussed in Section 2.2.2) on the MNIST (LeCun et al., 1998) data of size 28 × 28. The network architecture of the generator is same as DCGAN (Radford et al., 2015) . To get the reasonable basis functions for the discriminator, we first train a Wasserstein GAN model with a subset of the MNIST data for a small number (5k) of iterations.

We then use the last hidden layer of the discriminator as our bases. We implement our algorithm with a different number of basis and the results are shown in Figures 3 and 4 . We have two major observations here: i) the GANs with discriminators linear on features generate reasonable samples and the performance improves as we increase the number of bases; ii) the algorithm converges with a small step-size while diverges for a large step-size. In this work, we presented a convergence result for a first-order algorithm on a class of non-convex max-min optimization problems that arise in many machine learning applications such as generative adversarial networks and multi-task learning. To the best of our knowledge, this is the first convergence result for this type of primal-dual algorithms. Our results allow us to analyze GANs with neural network generator as well as general multi-task non-convex supervised learning problems.

A critical assumption we made is that the inner maximization loop is a strictly convex problem.

For applications in GANs, our assumptions require the discriminator to be a linear combination of predefined basis functions. Extending this to the most general cases where the discriminator is a neural network requires further investigations and will be a future research topic.

A ROBUST MULTI-TASK MACHINE LEARNING:

Multi-task machine learning (Qian et al., 2018) aims at learning a single model that would work for several different machine learning tasks. Let

min W E{f 1 (x 1 , W )}, • • • , min W E{f n (x n , W )}

be n supervised learning problems, then a multi-task formulation is

EQUATION

)

where p is a probability vector to weight the tasks. A common choice is the uniform distribution p = [1/n, . . . , 1/n]. To improve the worst case performance, one can change p adaptively and attain the max-min formulation

EQUATION

)

where D is a distance function to regularize p. Here we have also added an regularization term on W .

A closely related topic is the distributional robustness (Namkoong & Duchi, 2016) problem

EQUATION

)

where P is a subset of the space of probability vectors. Relaxing the hard constraint on p points to a regularized version

EQUATION

)

While p represents weights on different tasks in multi-task learning, it describes data distribution in distributional robustness. It beautifully incorporates data uncertainties in the learning problems. This formulation has also applications in adversarial learning Madry et al. (2018) , where p i f (x i , W ) denotes the loss given by data x i after adversarial reweighing through the inner maximization problem. The goal of the outer minimization is to learn a model with parameters W such that the worst case loss is minimized.

A.1 NUMERICAL EXAMPLE:

We consider two supervised learning tasks with MNIST (LeCun et al., 1998) dataset and CIFAR10 (Krizhevsky & Hinton, 2009) data set. We seek a single neural network that works for these two completely unrelated problems (see Section A). First, we convert the MNIST data from 28 × 28 gray images to 32 × 32 color images so that it is in the same format as CIFAR10. We use a standard AlexNet (Krizhevsky et al., 2012) as our model. We train the model with the robust multi-task learning framework and compare it to the results from three other methods: train with MNIST only, train with CIFAR10 only and train with both data sets but with even weight [0.5, 0.5]. The batch size we use is 128.

The results are presented in Table 2 . The last row is the results for the robust multi-task learning, and the "even mixture" in the second last row standards for uniform weight [0.5, 0.5] between the two tasks. We see that the result of using robust multi-task learning framework is better than the one with even weight. Moreover, its performance on each task is comparable to that trained from a single data set alone. The optimal p is [0.205, 0.795], where the first value is for the MNIST dataset. We also implement our algorithm with different levels λ of regularizations. The results are shown in Figure 5 , where we display the loss functions in the first two plots and the weight for MNIST in the last plot. Even though changing λ doesn't affect the convergence rate that much, it changes the optimal p significantly. 

B CONVERGENCE ANALYSIS OF THE PRIMAL DUAL ALGORITHM:

In our convergence analysis of the primal-dual algorithm, we use the optimality conditions of X rand Y r -subproblems repeatedly so that the quantities of measuring the size of the difference of the iterates, e.g., X r+1 -X r and Y r+1 -Y r , can be obtained. Also, for the simplicity of the notation, we have the following definitions:

EQUATION

Then, we give the optimality condition of X r -subproblem and Y r -subproblem as follows,

EQUATION

EQUATION

where -r+1 denotes the subgradient of the convex indicator function 1(y r+1 ∈ Y), Y r j,k denotes the entry at the j row and kth column of Y r , and g j,k (X r ) denotes the matrix value function mapping from X r to the value at the jth row and kth column of g(X r ). Note that equation 23 is also equivalent to

EQUATION

Before going to the details, we will first introduce the following lemma that characterizes the upper bound of Y r . Lemma 3. Let (X r , Y r ) be a sequence generated by equation 10. The size of Y r is upper bounded by some constant number denoted by σ Y .

Proof. Let ζ(X, Y ) l(Y ) -g(X), Y . Define:

EQUATION

From the optimality conditions, we know that

EQUATION

Adding these two inequalities, we have

EQUATION

which implies that

L g,1 X 1 -X 2 Y * 1 -Y * 2 ≥ g(X 2 ) -g(X 1 ), Y * 1 -Y * 2 = ∇ Y ζ(X 2 , Y * 2 ) -∇ Y ζ(X 1 , Y * 2 ), Y * 1 -Y * 2 ≥ ∇ Y ζ(X 1 , Y * 1 ) -∇ Y ζ(X 1 , Y * 2 ), Y * 1 -Y * 2 = ∇l(Y * 1 ) -∇l(Y * 2 ), Y * 1 -Y * 2 ≥ γ Y * 1 -Y * 2 2

where in the first inequality we used the Lipschitz continuity; in the last inequality we used the strong convexity of function l(Y ). Therefore, we have

EQUATION

)

Since X ∈ X , with X bounded by σ X , we have the claim that the distance between any two Y * 1 and Y * 2 are bounded by 2L g,1 σ X /γ. In other words, Y * X r , ∀X r ∈ X are within a compact sets, where Y * X r arg min Y ∈Y ζ(X r , Y ) and the radius of the set is upper bounded by 2L g,1 σ X /γ.

Let Y r+1 denote the r + 1th iterate of the projected gradient descent method of solving the dual problem which is parameterized by X r+1 . Because the dual problem is strongly convex, it is standard to show that

Y r+1 -Y * X r+1 ≤ Y r -Y * X r+1 .

(29) This implies that the distance between the iterate and the set is not increasing. The proof is complete.

Throughout our analysis, we used σ Y ≥ Y r 1 , ∀r where Y 1 i,j |Y i,j |. Note that Y 1 ≥ Y F . Based on this definition and the previous lemma, it is easy to check that the following holds

EQUATION

where L X and L g,2 are two constants defined after equation 4.

B.1 PROOF OF LEMMA 1

EQUATION

First, suppose that we choose β large enough such that β ≥ L X + σ Y L g,2 . Then we have the following estimate of the descent of the objective value:

f (X r+1 , Y r ) -f (X r , Y r ) =h(X r+1 ) + g(X r+1 ), Y r -h(X r ) -g(X r ), Y r (32) (a) ≤ ∇ X h(X r ) + i,j ∇ X g i,j (X r )Y r j,k , X r+1 -X r + L X + σ Y L g,2 2 X r+1 -X r 2 (b) ≤ - β 2 X r+1 -X r 2

when in (a) we used the equation 30; In (b) wej used the optimality condition equation 22, and we choose β ≥ L X + σ Y L g,2 .

B.1.2 DUAL PROBLEM:

For the dual problem, we have

f (X r+1 , Y r+1 ) -f (X r+1 , Y r ) = -l(Y r+1 ) + g(X r+1 ), Y r+1 -Y r + l(Y r ) -(1(Y r+1 ∈ Y) -1(Y r ∈ Y)) (a) ≤ -∇ Y l(Y r ) -r , Y r+1 -Y r + g(X r+1 ), Y r+1 -Y r = -∇ Y l(Y r ) -r+1 , Y r+1 -Y r -r+1 -r , Y r+1 -Y r + g(X r+1 ), Y r+1 -Y r (b) = 1 ρ Y r+1 -Y r , Y r+1 -Y r -r+1 -r , Y r+1 -Y r (c) ≤ 1 ρ Y r+1 -Y r , Y r+1 -Y r + 1 2 L Y + L g,1 - 1 ρ Y r+1 -Y r 2 + L g,1 2 X r+1 -X r 2 + 1 2 L Y + 1 ρ Y r -Y r-1 2 = 1 2 L Y + L g,1 + 1 ρ Y r+1 -Y r 2 + L g,1 2 X r+1 -X r 2 + 1 2 L Y + 1 ρ Y r -Y r-1 2

where in (a) we used the convexity of both function l(X) and indicator function, i.e., l( 1. First, from equation 23 we have

EQUATION

EQUATION

Y r =Y r-1 + ρ(g(X r ) -∇l(Y r-1 ) + r ),

which imply

EQUATION

2. Second, we have

r+1 -r , Y r+1 -Y r = 1 ρ V r+1 , Y r+1 -Y r -g(X r+1 ) -g(X r ), Y r+1 -Y r -∇ Y l(Y r ) -∇ Y l(Y r-1 ), Y r+1 -Y r (a) ≥ - 1 2ρ ( Y r -Y r-1 2 -Y r+1 -Y r 2 ) - 1 2 (L Y + L g,1 ) Y r+1 -Y r 2 - 1 2 L g,1 X r+1 -X r 2 - 1 2 L Y Y r -Y r-1 2 ≥ - 1 2 L Y + L g,1 - 1 ρ Y r+1 -Y r 2 - L g,1 2 X r+1 -X r 2 - 1 2 L Y + 1 ρ Y r -Y r-1 2

where in (a) we used Cauchy-Schwarz inequality.

Finally, combing the above results, we have

EQUATION

)

B.2 PROOF OF LEMMA 2

Proof. Let W r+1 (X r+1 -X r ) -(X r -X r-1 ). Subtracting equation 22 at iteration r -1 from itself at the rth iteration, we have the successive difference of equation 23, i.e.,

∇ X h(X r ) -∇ X h(X r-1 ) +   j,k ∇g j,k (X r )Y r j,k - j,k ∇g j,k (X r-1 )Y r-1 j,k   A r +βW r+1 , X r+1 -X r ≤ 0. (37)

Similarly, from equation 23, we also have

EQUATION

B.2.1 INDUCTION OF THE SIZE OF THE SUCCESSIVE ITERATES:

First, we note the following key inequality

EQUATION

)

Second, we can get the lower bound of A r , X r+1 -X r as follows:

EQUATION

)

Step 1). First, we have

Y r -Y r-1 , V r+1 ρ -( r+1 -r ) (46) = Y r -Y r-1 -(Y r+1 -Y r ) + Y r+1 -Y r , V r+1 ρ -( r+1 -r ) (47) =ρ V r+1 ρ , V r+1 ρ -( r+1 -r ) -Y r+1 -Y r , V r+1 ρ -( r+1 -r ) (a) = ρ 2 V r+1 ρ 2 + V r+1 ρ -( r+1 -r ) 2 -r+1 -r 2 - 1 2ρ Y r+1 -Y r 2 -Y r -Y r-1 2 + V r+1 2 + Y r+1 -Y r , r+1 -r ≤0 (48) ≤ ρ 2 V r+1 ρ -( r+1 -r ) 2 - 1 2ρ Y r+1 -Y r 2 + 1 2ρ Y r -Y r-1 2 (49)

where in (a) we used

EQUATION

due to the fact that -r+1 is the subgradient of the convex indicator function 1(y r+1 ∈ Y), and also the equality

EQUATION

Further, from the optimality condition of the Y r subprolbem shown in equation 23, we know

EQUATION

which gives

ρ 2 V r+1 ρ -( r+1 -r ) 2 ≤ ρL 2 g,1 X r+1 -X r 2 + ρL 2 Y Y r -Y r-1 2 (53)

where we used the Lipschitz continuity.

Step 2). Next, we need to quantify the lower bound of

EQUATION

)

Combining step 1 and step 2 and equation 46, we have the lower bound

of A r , X r+1 -X r A r , X r+1 -X r ≥ -Y r -Y r-1 1 L g,2 X r+1 -X r 2 - 1 2 Y r-1 1 L X X r+1 -X r 2 - 1 2 Y r-1 L X X r -X r-1 2 + 1 2ρ Y r+1 -Y r 2 - 1 2ρ Y r -Y r-1 2 -ρL 2 g,1 X r+1 -X r 2 -ρL 2 Y Y r+1 -Y r 2 + γ Y r -Y r-1 2 . (55)

Therefore, dividing equation 37 by β and combining equation 39, equation 55, we have

1 2 X r+1 -X r 2 + 1 2ρβ Y r+1 -Y r 2 (56) ≤ 1 2 X r -X r-1 2 + 1 2ρβ Y r -Y r-1 2 - 1 2 W r+1 2 + 2L g,2 Y r -Y r-1 1 + L X Y r-1 1 + L X + 2ρL 2 g,1 2β X r+1 -X r 2 + L X Y r-1 1 + L X 2β X r -X r-1 2 - γ -ρL 2 Y β Y r -Y r-1 2 (a) ≤ 1 2 X r -X r-1 2 + 1 2ρβ Y r -Y r-1 2 - γ -ρL 2 Y β Y r -Y r-1 2 dual descent + 5σ Y L X + L g,2 + 2ρL 2 g,1 2β X r+1 -X r 2 + L X (σ Y + 1) 2β X r -X r-1 2 (57)

where in (a) we used σ Y ≥ Y r 1 , ∀r.

B.2.2 POTENTIAL FUNCTION:

Rearranging equation 57, we have

EQUATION

)

Define a potential function P r+1 (X r+1 , Y r+1 ) + dQ r+1 . We can obtain 3. and we also need

EQUATION

EQUATION

Note that we need 1 ρβ -

γ-ρL 2 Y 2β

≥ 0, since the potential function should be greater than 0, meaning that L 2 Y ρ 2 -γρ + 2 ≥ 0, (65) which is actually satisfied automatically by checking the two roots of the equation L 2 Y ρ 2 -γρ + 2 (note that L Y ≥ γ).

Combing the descent lemma shown in Lemma 1, we have the conditions of ρ, β shown in Lemma 2 so that the potential function can have a sufficient descent at each iteration.

B.3 PROOF OF THEOREM 1:

Proof. First, we can get the upper bound of ∇L(X r , Y r ) , which is ∇L(X r , Y r )

≤ X r+1 -X r + X r+1 -proj X (X r -∇ X f (X r , Y r )) + Y r+1 -Y r + Y r+1 -proj Y (Y r + ∇ Y f (X r , Y r )) (a) ≤ X r+1 -X r + proj X (X r+1 -∇ X f (X r+1 , Y r )) -proj X (X r -∇ X f (X r , Y r )) + Y r+1 -Y r + proj Y (Y r+1 + ∇ Y f (X r+1 , Y r+1 )) -proj Y (Y r + ∇ Y f (X r , Y r )) (b) ≤ X r+1 -X r + ∇ X f (X r+1 , Y r )) -∇ X f (X r , Y r )) + Y r+1 -Y r + ∇ Y f (X r+1 , Y r+1 )) -∇ Y f (X r , Y r )) (66) (c) ≤ X r+1 -X r + ∇ X h(X r+1 ) -∇ X h(X r ) + σ Y ∇ X g(X r+1 ) -g(X r ) + ∇ Y l(Y r+1 ) -∇ Y l(Y r ) d) ≤(1 + L X + σ Y L g,2 ) X r+1 -X r + (1 + L Y ) Y r+1 -Y r

where in (a) we used the optimality condition of X r -subproblem; in (b) we used nonexpansiveness of the projection operator; in (c) we take the gradient of f (X, Y ); in (d) we used the Lipschitz continuous of function h(X) and l(Y ).

Since X r , Y r are within compact sets, the sizes of X r , Y r are bounded, which implies that there exits σ 1 such that

∇L(X r , Y r ) 2 ≤ σ 1 ( X r+1 -X r 2 + Y r+1 -Y r 2 C r

).

(67)

From equation 59, we also know that there exits a constant σ 2 min{c 1 , c 2 } such that

EQUATION

)

Combining equation 67, we have

EQUATION

)

Summing both sides of the above inequality over r = 1, . . . , T , we have

EQUATION

where in the last inequality we have used the fact that P r is decreasing and lower bounded by P since X r , Y r are within the compact sets. By utilizing the definition T ( ), the above inequality becomes

EQUATION

Dividing both sides by T ( ), and by setting C σ 1 /σ 2 , the desired result is obtained

:



Figures and Tables:

Figure 1: (a) converge and (b) diverge show the effect of step-sizes; (c) is based on the algorithm in Sanjabi et al. (2018).

Figure 2: Real (green) vs generated (red) samples

Figure 3: Generated samples with different number (a) 128, (b) 1024, and (c) 4096 of basis functions.

Figure 5: Effect of regularization. Here p is the weight, W is the parameter and λ is the regularization constant. The regularizer D is taken to be the Kullback-Leibler divergence.

b) we used equation 23 and (c) is true because the following relations:

Comparison of time elapsed (in seconds) for different dimensions.

Table content: <table><tr><td/><td>5D</td><td>10D</td><td>20D</td><td>50D</td></tr><tr><td>ours</td><td colspan="4">130.27 134.76 135.47 380.98</td></tr><tr><td colspan="5">Sanjabi et al. 524.00 543.52 545.18 1603.68</td></tr><tr><td>4.1 GAN IN LQG SETTING</td><td/><td/><td/></tr></table>

Multi-task Learning: Comparison of Accuracies

Table content: <table><tr><td>Method</td><td/><td/><td colspan="2">Training</td><td>MNIST Test</td><td>Training</td><td>CIFAR10 Test</td></tr><tr><td>MNIST</td><td/><td/><td colspan="2">99.98</td><td>99.33</td><td>9.24</td><td>9.16</td></tr><tr><td colspan="2">CIFAR10</td><td/><td colspan="2">10.25</td><td>10.10</td><td>99.75</td><td>76.59</td></tr><tr><td colspan="2">Even Mixture</td><td/><td colspan="2">99.96</td><td>99.40</td><td>99.42</td><td>74.97</td></tr><tr><td colspan="2">OPT Mixture</td><td/><td colspan="2">99.98</td><td>99.35</td><td>99.85</td><td>76.29</td></tr><tr><td>0</td><td>100</td><td>200</td><td>300</td><td>400</td></tr><tr><td colspan="4">Number of iterations (x 100)</td><td/></tr></table>

) B.2.3 CONVERGENCE CONDITIONSIf the following conditions hold, i.e., c 1 , c 2 , c 3 > 0, then the potential function has a sufficient decrease at each iteration.by S-procedure it is sufficiently to show the setX = {x| (β -L g,1 ) x 2 < L Y + L g,1 + 1 ρ , ((6σ Y + 1)L X + L g,2 + 2ρL 2 g,1 )x 2 > (γ -ρL 2 Y )} is empty.

Table content: <table><tr><td/><td>β 2</td><td>-</td><td colspan="2">L g,1 2</td><td>-</td><td colspan="2">d(6σ Y + 1)L X + L g,2 + 2ρL 2 g,1 ) 2β</td><td>&gt;0,</td><td>(60)</td></tr><tr><td/><td/><td/><td/><td/><td/><td>d β</td><td>(γ -ρL 2 Y ) -(L Y + L g,1 +</td><td>1 ρ</td><td>) &gt;0.</td><td>(61)</td></tr><tr><td colspan="4">To show that ∃d ≥ 0 such that</td><td/><td/><td/></tr><tr><td>β -L g,1 0</td><td colspan="3">0 L Y + L g,1 + 1 ρ</td><td colspan="2">+d</td><td/><td>-1 β (6σ Y + 1)L X + L g,2 + 2ρL 2 g,1 0</td><td>0 β (γ -ρL 2 1 Y )</td><td>0</td></tr><tr><td colspan="2">Hence, we require that</td><td/><td/><td/><td/><td/></tr><tr><td>1.</td><td/><td/><td/><td/><td/><td/><td>γ -ρL 2 Y &gt; 0,</td><td>(62)</td></tr><tr><td colspan="2">which gives</td><td/><td/><td/><td/><td/><td>ρ &lt;</td><td>γ Y L 2</td><td>;</td><td>(63)</td></tr></table>

Peer review (iclr2019):
 This paper studies the convergence of a primal-dual algorithm on a certain min-max problem and experimentally shows that it works in GANs and multi-task learning. This paper is clear and well-written. The convergence guarantee looks neat, and convergence to stationary points is a sensible thing on non convex-concave problems. I am not super familiar with the literature of saddle-point optimization and may not have a good sense about the significance of the theoretical result. My main concern is that the assumptions in the theory are rather over-restrictive and it’s not clear what intuitions or new messages they bring in for the practice of GANs. The convergence theorem requires the maximization problem (over discriminators) to be strictly concave. On GANs, this assumption is not (near) satisfied beyond the simple case of the LQG setting (PSD quadratic discriminators). On the other hand, the experiments on GANs just seem to say that the algorithm works but not much more beyond that. There is a brief discussion about the improvement in time consumption but it doesn’t have a report a quantitative comparison in the wall time. On multi-task learning, the proposed algorithm shows improvement over the baseline. However it is also unclear whether it is the *formulation* (12) that brings in the improvement, or it is the actual primal-dual *algorithm*. Perhaps it might be good to try gradient descent on (12) and see if it also works well. In general, I would recommend the authors to have a more convincing demonstration of the strength of this algorithm over baseline methods on min-max problems, either theoretical or empirical.