Year: 2018

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.

heading: 1 INTRODUCTION
text: 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.

heading: 2 GENERATIVE ADVERSARIAL NETWORKS AND MIN-MAX PROBLEMS
text: 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.

heading: 2.1 GANS
text: 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 {yi} ny i=1 ⊂ Rd and the random seed x (a random variable in Rk) of the generative model by Py and Px 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
min G∈G max F∈F {E(F (y))−E(F (G(x)))}, (2)
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 (Mü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
min G∈G max ψ,φ {E(ψ(y)) + E(φ(G(x)) | ψ(y) + φ(x) ≤ c(x, y), ∀x, y}. (3)
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.

heading: 2.2 NONCONVEX MIN-MAX PROBLEMS
text: 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 αF1 + βF2 in the coupling term E(F (G(x))) yields
E(F (G(x))) = E((αF1 + βF2)(G(x))) = αE(F1(G(x))) + βE(F2(G(x))).
This structure motivates us to study the following min-max primal-dual optimization problem
min X∈X max Y ∈Y
h(X) + 〈g(X), Y 〉 − l(Y ) (4)
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.

heading: 2.2.1 WASSERSTEIN GAN IN LQG SETTING
text: 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, Ik), G(x) = θx.
It can be shown that it suffice to consider discriminator of the form
φ(x) = 1 2 ‖x‖2 − 1 2 xTAx, ψ(y) = 1 2 ‖y‖2 − 1 2 yTBy
with A,B being positive definite.
The constraint φ(x) + ψ(y) ≤ 12‖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
min θ∈Rd×k max A 0
Tr(Σy) + Tr(θθ T )− Tr(AθθT )− Tr(A−1Σy), (5)
which is apparently in the form of equation 4. When only samples {xi}ni=1, {yi}ni=1 of x,y are available, this becomes
min θ∈Rd×k max A 0
1
n n∑ i=1 ( 1 2 ‖yi‖2 − 1 2 yTi A −1yi) + 1 n n∑ i=1 ( 1 2 ‖θxi‖2 − 1 2 xTi θ TAθxi). (6)

heading: 2.2.2 GANS WITH DISCRIMINATORS LINEAR ON FEATURES
text: 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 {Fi}ni=1 be the basis functions, and F = ∑ αiFi with some constraint on α, then the above formulation becomes
min G∈G max α∈Rn { n∑ i=1 αiE(Fi(y))− n∑ i=1 αiE(Fi(G(x))− λ‖α‖2 } . (7)
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}ni=1 and {ψi}ni=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
min G∈G max α,β { n∑ i αiE{φi(G(x))}+ n∑ i βiE{ψi(y)} − l(α, β) } . (8)
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.

heading: 3 ALGORITHM DESIGN AND CONVERGENCE ANALYSIS
text: 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 (hi(X) + 〈gi(X), Y 〉 − li(Y )) (9)
where X is a convex and compact set and the size of ‖X‖ is upper bounded by σX ; hi(X) : Rd → R,∀i is a non-convex function and has Lipschitz continuous gradient with constant LX ;
li(Y ) : Rd → R,∀i are strongly convex with modulus γ > 0 and Lipschitz gradient constant LY ; the matrix function gi(X) : X → dim(Y ) can also be non-convex, and it is assumed to be Lipschitz and Lipschitz gradient continuous with constants Lg,1 and Lg,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 1n ∑n i=1 (hi(X) + 〈gi(X), Y 〉 − li(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 hi, gi, li 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.

heading: 3.1 ALGORITHM DESCRIPTION
text: 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 :
Xr+1 = arg min X∈X
〈 1
n n∑ i=1
(∇Xhi(Xr) +∇X Tr(gi(Xr)Y r)) , X −Xr 〉 + β
2 ‖X −Xr‖2,
(10)
Y r+1 = arg max Y ∈Y 〈 − 1 n n∑ i=1 ∇Y li(Y r) + gi(Xr+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 Xr and Y r can be written down in closed form using the following alternating projected gradient descent/ascent steps:
Xr+1 = projX
( Xr − 1
β
( 1
n n∑ i=1 (∇Xhi(Xr) +∇X Tr(gi(Xr)Y r))
)) ,
Y r+1 = projY
( Y r + ρ ( 1
n n∑ i=1 ∇Y li(Y r) + gi(Xr+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.

heading: 3.2 CONVERGENCE ANALYSIS
text: 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 (Xr, Y r) be a sequence generated by equation 10. The descent of the objective function can be quantified by
f(Xr+1, Y r+1)− f(Xr, Y r) ≤ − ( β
2 − LX 2
) ‖Xr+1 −Xr‖2
+ 1
2
( LY + Lg,1 + 1
ρ
) ‖Y r+1 − Y r‖2 + LX + 1 ρ
2 ‖Y r − Y r−1‖2. (11)
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,
ρ < γ
L2Y , β ≥ max
{ Lg,1 + (LY + Lg,1 + 1 ρ )((6σY + 1)LX + Lg,2 + 2ρL 2 g,1)
γ − ρL2Y , LX + σY Lg,2 } (12)
then there exist c1, c2, c3, d > 0 such that potential function will monotonically decrease, i.e.,
Pr+1 − Pr ≤ −c1‖Xr+1 −Xr‖2 − c2‖Y r+1 − Y r‖2 − c3‖Y r − Y r−1‖2 (13)
where Pr+1 , f(Xr+1, Y r+1) + dQr+1 and Qr+1 , ( LX(σY + 1)
2β +
1
2
) ‖Xr+1 −Xr‖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 ∇L(X,Y ) , [ X − projX [X −∇Xf(X,Y )] Y − projY [Y +∇Y f(X,Y )] ] (14)
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 (Xr, 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
T ( ) , min{r | ‖∇L(Xr, Y r)‖2 ≤ , r ≥ 1}. (15) Then there exists some constant C > 0 such that
≤ C(P 1 − P) T ( )
(16)
where P denotes the lower bound of Pr.
The above result shows that our proposed algorithm converges to the first-order stationary point of the original problem in a sublinear rate.

heading: 4 EXPERIMENTS
text: 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.

heading: 4.1 GAN IN LQG SETTING
text: In the LQG setting, as discussed in Section 2.2.1, the generator is modeled by a linear mapG(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.

heading: 4.2 GANS WITH DISCRIMINATORS LINEAR ON FEATURES
text: 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.

heading: 5 CONCLUSION
text: 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.

heading: A ROBUST MULTI-TASK MACHINE LEARNING
text: 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{f1(x1,W )}, · · · , min W E{fn(xn,W )}
be n supervised learning problems, then a multi-task formulation is
min W n∑ i=1 piE{fi(xi,W )}, (17)
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
min W max p { n∑ i=1 piE{fi(xi,W )} − λD(p, p̄) + h(W )}, (18)
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
min W max p∈P n∑ i=1 pif(xi,W ), (19)
where P is a subset of the space of probability vectors. Relaxing the hard constraint on p points to a regularized version
min W max p n∑ i=1 pif(xi,W )− λD(p, p̄). (20)
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 pif(xi,W ) denotes the loss given by data xi 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.

heading: A.1 NUMERICAL EXAMPLE
text: 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.

heading: B CONVERGENCE ANALYSIS OF THE PRIMAL DUAL ALGORITHM
text: In our convergence analysis of the primal-dual algorithm, we use the optimality conditions of Xrand Y r-subproblems repeatedly so that the quantities of measuring the size of the difference of the iterates, e.g., ‖Xr+1 − Xr‖ and ‖Y r+1 − Y r‖, can be obtained. Also, for the simplicity of the notation, we have the following definitions:
h(X) , 1
n n∑ i=1 hi(X), g(X) , 1 n n∑ i=1 gi(X), l(Y ) , 1 n n∑ i=1 li(Y ). (21)
Then, we give the optimality condition of Xr-subproblem and Y r-subproblem as follows,〈 ∇h(Xr) +
∑ j,k ∇Xgj,k(Xr)Y rj,k + β(Xr+1 −Xr), Xr+1 −X
〉 ≤ 0,∀X ∈ X , (22)
Y r+1 = Y r + ρ r+1 + ρ ( g(Xr+1)−∇Y l(Y r) ) . (23)
where − r+1 denotes the subgradient of the convex indicator function 1(yr+1 ∈ Y), Y rj,k denotes the entry at the j row and kth column of Y r, and gj,k(Xr) denotes the matrix value function mapping fromXr to the value at the jth row and kth column of g(Xr). Note that equation 23 is also equivalent to 〈
−∇Y l(Y r) + g(Xr+1)− 1
ρ (Y r+1 − Y r), Y r+1 − Y
〉 ≥ 0, ∀Y ∈ Y. (24)
Before going to the details, we will first introduce the following lemma that characterizes the upper bound of ‖Y r‖. Lemma 3. Let (Xr, 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:
Y ∗1 , arg min Y ∈Y ζ(X1, Y ) Y ∗ 2 , arg min Y ∈Y ζ(X2, Y ) (25)
From the optimality conditions, we know that
〈∇Y ζ(X1, Y ∗1 ), Y ∗2 − Y ∗1 〉 ≥ 0 〈∇Y ζ(X2, Y ∗2 ), Y ∗1 − Y ∗2 〉 ≥ 0. (26)
Adding these two inequalities, we have
〈∇Y ζ(X1, Y ∗1 )−∇Y ζ(X2, Y ∗2 ), Y ∗2 − Y ∗1 〉 ≥ 0, (27)
which implies that
Lg,1‖X1 −X2‖‖Y ∗1 − Y ∗2 ‖ ≥ 〈g(X2)− g(X1), Y ∗1 − Y ∗2 〉 = 〈∇Y ζ(X2, Y ∗2 )−∇Y ζ(X1, Y ∗2 ), Y ∗1 − Y ∗2 〉 ≥ 〈∇Y ζ(X1, Y ∗1 )−∇Y ζ(X1, 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
‖Y ∗1 − Y ∗2 ‖ ≤ Lg,1 γ ‖X1 −X2‖. (28)
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 2Lg,1σX/γ. In other words, Y ∗ Xr ,∀Xr ∈ X are within a compact sets, where Y ∗Xr , arg minY ∈Y ζ(X r, Y ) and the radius of the set is upper bounded by 2Lg,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 Xr+1. Because the dual problem is strongly convex, it is standard to show that
‖Y r+1 − Y ∗Xr+1‖ ≤ ‖Y r − Y ∗Xr+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 |Yi,j |. Note that ‖Y ‖1 ≥ ‖Y ‖F . Based on this definition and the previous lemma, it is easy to check that the following holds
‖∇f(X,Y )−∇f(Z, Y )‖ ≤ (LX + σY Lg,2)‖X − Z‖ (30)
where LX and Lg,2 are two constants defined after equation 4.

heading: B.1 PROOF OF LEMMA 1

heading: B.1.1 PRIMAL PROBLEM
text: Define f(X,Y ) , h(X)− l(Y ) + 〈g(X), Y 〉. (31)
First, suppose that we choose β large enough such that β ≥ LX + σY Lg,2. Then we have the following estimate of the descent of the objective value:
f(Xr+1, Y r)− f(Xr, Y r) =h(Xr+1) + 〈g(Xr+1), Y r〉 − h(Xr)− 〈g(Xr), Y r〉 (32) (a)
≤〈∇Xh(Xr) + ∑ i,j ∇Xgi,j(Xr)Y rj,k, Xr+1 −Xr〉+ LX + σY Lg,2 2 ‖Xr+1 −Xr‖2
(b) ≤ − β 2 ‖Xr+1 −Xr‖2
when in (a) we used the equation 30; In (b) wej used the optimality condition equation 22, and we choose β ≥ LX + σY Lg,2.

heading: B.1.2 DUAL PROBLEM
text: For the dual problem, we have
f(Xr+1, Y r+1)− f(Xr+1, Y r) = −l(Y r+1) + 〈g(Xr+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(Xr+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(Xr+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
(( LY + Lg,1 − 1
ρ
) ‖Y r+1 − Y r‖2
+ Lg,1 2 ‖Xr+1 −Xr‖2 + 1 2
( LY + 1
ρ
) ‖Y r − Y r−1‖2 ) = 1
2
(( LY + Lg,1 + 1
ρ
) ‖Y r+1 − Y r‖2 + Lg,1
2 ‖Xr+1 −Xr‖2
+ 1
2
( LY + 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(Y r+1) + 1(Y r+1 ∈ Y)− (l(Y r) + 1(Y r ∈ Y) ≥ 〈∇Y l(Y r)− r, Y r+1 − Y r〉, in (b) we used equation 23 and (c) is true because the following relations:
1. First, from equation 23 we have
Y r+1 =Y r + ρ(g(Xr+1)−∇l(Y r) + r+1), (33) Y r =Y r−1 + ρ(g(Xr)−∇l(Y r−1) + r), (34)
which imply
r+1− r = 1 ρ
(Y r+1−Y r−(Y r−Y r−1))− ( g(Xr+1)− g(Xr) ) +∇l(Y r)−∇l(Y r−1).
(35)
2. Second, we have
〈 r+1 − r, Y r+1 − Y r〉
= 1
ρ 〈V r+1, Y r+1 − Y r〉 − 〈g(Xr+1)− g(Xr), 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 (LY + Lg,1)‖Y r+1 − Y r‖2
− 1 2 Lg,1‖Xr+1 −Xr‖2 − 1 2 LY ‖Y r − Y r−1‖2
≥− 1 2
(( LY + Lg,1 − 1
ρ
) ‖Y r+1 − Y r‖2 − Lg,1
2 ‖Xr+1 −Xr‖2
− 1 2
( LY + 1
ρ
) ‖Y r − Y r−1‖2 ) where in (a) we used Cauchy–Schwarz inequality.
Finally, combing the above results, we have f(Xr+1, Y r+1)− f(Xr, Y r)
≤−β 2 ‖Xr+1 −Xr‖2︸ ︷︷ ︸ primal descent + 1 2
( LY + Lg,1 + 1
ρ
) ‖Y r+1 − Y r‖2
+ Lg,1 2 ‖Xr+1 −Xr‖2 + 1 2
( LY + 1
ρ
) ‖Y r − Y r−1‖2. (36)

heading: B.2 PROOF OF LEMMA 2
text: Proof. Let W r+1 , (Xr+1 −Xr)− (Xr −Xr−1). Subtracting equation 22 at iteration r− 1 from itself at the rth iteration, we have the successive difference of equation 23, i.e.,〈 ∇Xh(Xr)−∇Xh(Xr−1)
+ ∑ j,k ∇gj,k(Xr)Y rj,k − ∑ j,k ∇gj,k(Xr−1)Y r−1j,k  ︸ ︷︷ ︸
,Ar
+βW r+1, Xr+1 −Xr 〉 ≤ 0. (37)
Similarly, from equation 23, we also have
Y r+1 − Y r − (Y r − Y r−1)︸ ︷︷ ︸ ,V r+1
= ρ ( r+1 − r ) + ρ ( g(Xr+1)− g(Xr) ) − ρ ( ∇l(Y r)−∇l(Y r−1) ) . (38)
B.2.1 INDUCTION OF THE SIZE OF THE SUCCESSIVE ITERATES
First, we note the following key inequality
〈W r+1, Xr+1 −Xr〉 = 1 2 ‖Xr+1 −Xr‖2 − 1 2 ‖Xr −Xr−1‖2 + 1 2 ‖W r+1‖2. (39)
Second, we can get the lower bound of 〈Ar, Xr+1 −Xr〉 as follows:〈∑ j,k ∇Xgj,k(Xr)Y rj,k − ∑ j,k ∇gj,k(Xr−1)Y r−1j,k , X r+1 −Xr 〉 (40)
= 〈∑ j,k ∇gj,k(Xr) ( Y rj,k − Y r−1j,k ) , Xr+1 −Xr 〉
+ 〈∑ j,k ( ∇gj,k(Xr)−∇gj,k(Xr−1) ) Y r−1j,k , X r+1 −Xr 〉
(41)
= ∑ m,n ∑ j,k ∇Xm,ngj,k(Xr) ( Y rj,k − Y r−1j,k ) (Xr+1m,n −Xrm,n)
+ ∑ m,n ∑ j,k ( ∇Xm,ngj,k(Xr)−∇Xm,ngj,k(Xr−1) ) Y r−1j,k (X r+1 m,n −Xrm,n) (42)
= ∑ j,k 〈∇Xgj,k(Xr), Xr+1 −Xr〉 ( Y rj,k − Y r−1j,k ) ︸ ︷︷ ︸
,Ar1 + ∑ j,k 〈 ∇Xgj,k(Xr)−∇Xgj,k(Xr−1), Xr+1 −Xr 〉 Y r−1j,k︸ ︷︷ ︸
,Ar2
. (43)
In the above derivation, we basically changed the order of summations.
From the mean value theorem, we know that there exits X̃r+1(m,n) ∈ [X r, Xr+1] such that
gm,n(X r+1)− gm,n(Xr) = 〈 ∇Xgm,n(X̃r+1(m,n)), X r+1 −Xr) 〉 . (44)
Hence, Ar1 becomes
∑ j,k 〈∇Xgj,k(Xr), Xr+1 −Xr〉(Y rj,k − Y r−1j,k )
= ∑ j,k 〈∇Xgj,k(Xr)−∇Xgj,k(X̃r+1), Xr+1 −Xr〉(Y rj,k − Y r−1j,k ) (45)
+ ∑ j,k 〈∇Xgj,k(X̃r+1), Xr+1 −Xr〉(Y rj,k − Y r−1j,k )
= ∑ j,k 〈∇Xgj,k(Xr)−∇Xgj,k(X̃r+1), Xr+1 −Xr〉(Y rj,k − Y r−1j,k )
+ ∑ j,k (gj,k(X r+1)− gj,k(Xr))(Y rj,k − Y r−1j,k )
≥− ‖Y r − Y r−1‖1‖X̃r+1 −Xr‖‖Xr+1 −Xr‖Lg,2
+
〈 V r+1
ρ +∇Y l(Y r)−∇Y l(Y r−1), Y r − Y r−1
〉 − 〈 r+1 − r, Y r − Y r−1〉
(a) ≥ − ‖Y r − Y r−1‖1‖Xr+1 −Xr‖2Lg,2 + 〈 V r+1
ρ +∇Y l(Y r)−∇Y l(Y r−1), Y r − Y r−1 〉 − 〈 r+1 − r, Y r − Y r−1〉
where in (a) we used Cauchy–Schwarz inequality.
Combining Ar1 and A r 2, we can get the lower bound of 〈Ar, Xr+1 −Xr〉, i.e.,
〈Ar, Xr+1 −Xr〉 ≥ − ‖Y r − Y r−1‖1‖Xr+1 −Xr‖2Lg,2 + 〈 V r+1
ρ +∇Y l(Y r)−∇Y l(Y r−1), Y r − Y r−1 〉 − 〈 r+1 − r, Y r − Y r−1〉+
∑ j,k 〈∇Xgj,k(Xr))−∇Xgj,k(Xr−1)), Xr+1 −Xr〉Y r−1j,k
≥− ‖Y r − Y r−1‖1‖Xr+1 −Xr‖2Lg,2 + 〈 V r+1
ρ − r+1 − r, Y r − Y r−1 〉 + 〈∇Y l(Y r)−∇Y l(Y r−1), Y r − Y r−1〉
− 1 2 ‖Y r−1‖1LX
( ‖Xr −Xr−1‖2 + ‖Xr+1 −Xr‖2 ) .
To further bound the above terms, we will give the upper bound of〈 Y r − Y r−1, V r+1/ρ− ( r+1 − r) 〉 and 〈∇Y l(Y r) − ∇Y l(Y r−1), Y r − Y r−1〉 separately in the following two steps.
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 − 12ρ ∥∥Y r+1 − Y r∥∥2 + 12ρ ∥∥Y r − Y r−1∥∥2 (49)
where in (a) we used
〈− r+1 − (− r), Y r+1 − Y r〉 ≥ 0 (50)
due to the fact that − r+1 is the subgradient of the convex indicator function 1(yr+1 ∈ Y), and also the equality
〈Y r − Y r−1, V r+1〉 = 1 2 ‖Y r+1 − Y r‖2 − 1 2 ‖Y r − Y r−1‖2 − 1 2 ‖V r+1‖2. (51)
Further, from the optimality condition of the Y r subprolbem shown in equation 23, we know
V r+1
ρ − ( r+1 − r) = g(Xr+1)− g(Xr)− (∇Y l(Y r)−∇Y l(Y r−1)), (52)
which gives
ρ
2 ∥∥∥∥V r+1ρ − ( r+1 − r) ∥∥∥∥2 ≤ ρL2g,1‖Xr+1 −Xr‖2 + ρL2Y ‖Y r − Y r−1‖2 (53)
where we used the Lipschitz continuity.
Step 2). Next, we need to quantify the lower bound of 〈∇Y l(Y r)−∇Y l(Y r−1), Y r−Y r−1〉. Since l(Y ) is strongly convex, we have
〈∇Y l(Y r)−∇Y l(Y r−1), Y r − Y r−1〉 ≥ γ‖Y r − Y r−1‖2. (54)
Combining step 1 and step 2 and equation 46, we have the lower bound of 〈Ar, Xr+1 −Xr〉
〈Ar, Xr+1 −Xr〉 ≥ −‖Y r − Y r−1‖1Lg,2‖Xr+1 −Xr‖2 − 1
2 ‖Y r−1‖1LX‖Xr+1 −Xr‖2
− 1 2 ‖Y r−1‖LX‖Xr −Xr−1‖2 + 1 2ρ ‖Y r+1 − Y r‖2 − 1 2ρ ‖Y r − Y r−1‖2
− ρL2g,1‖Xr+1 −Xr‖2 − ρL2Y ‖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 ‖Xr+1 −Xr‖2 + 1 2ρβ ‖Y r+1 − Y r‖2 (56)
≤1 2 ‖Xr −Xr−1‖2 + 1 2ρβ ‖Y r − Y r−1‖2 − 1 2 ‖W r+1‖2
+ 2Lg,2‖Y r − Y r−1‖1 + LX‖Y r−1‖1 + LX + 2ρL2g,1
2β ‖Xr+1 −Xr‖2
+ LX‖Y r−1‖1 + LX 2β ‖Xr −Xr−1‖2 − γ − ρL 2 Y β ‖Y r − Y r−1‖2
(a) ≤ 1 2 ‖Xr −Xr−1‖2 + 1 2ρβ ‖Y r − Y r−1‖2−γ − ρL 2 Y
β ‖Y r − Y r−1‖2︸ ︷︷ ︸
dual descent
+ 5σY LX + Lg,2 + 2ρL
2 g,1
2β ‖Xr+1 −Xr‖2 + LX(σY + 1) 2β ‖Xr −Xr−1‖2 (57)
where in (a) we used σY ≥ ‖Y r‖1,∀r.

heading: B.2.2 POTENTIAL FUNCTION
text: Rearranging equation 57, we have
Qr+1 , ( LX(σY + 1)
2β +
1
2
) ‖Xr+1 −Xr‖2 + ( 1
2ρβ − γ − ρL 2 Y 2β
) ‖Y r+1 − Y r‖2
≤ ( LX(σY + 1)
2β +
1
2
) ‖Xr −Xr−1‖2 + ( 1
2ρβ − γ − ρL 2 Y 2β
) ‖Y r − Y r−1‖2
− γ − ρL 2 Y
2β ‖Y r+1 − Y r‖2 +
(6σY + 1)LX + Lg,1 + 2ρL 2 g,1
2β ‖Xr+1 −Xr‖2
=Qr + (6σY + 1)LX + Lg,2 + 2ρL
2 g,1
2β ‖Xr+1 −Xr‖2
− γ − ρL 2 Y 2β ‖Y r+1 − Y r‖2 − γ − ρL 2 Y 2β ‖Y r − Y r−1‖2. (58)
Define a potential function Pr+1 , (Xr+1, Y r+1) + dQr+1. We can obtain
Pr+1 − Pr ≤− β2 − Lg,12 − d((6σY + 1)LX + Lg,2 + 2ρL2g,1)2β︸ ︷︷ ︸ ,c1  ‖Xr+1 −Xr‖2
− d(γ − ρL2Y )2β − LY + Lg,1 + 1 ρ
2︸ ︷︷ ︸ ,c2
 ‖Y r+1 − Y r‖2
− d(γ − ρL2Y )2β − LY + 1 ρ
2︸ ︷︷ ︸ ,c3
 ‖Y r − Y r−1‖2. (59)

heading: B.2.3 CONVERGENCE CONDITIONS
text: If the following conditions hold, i.e., c1, c2, c3 > 0, then the potential function has a sufficient decrease at each iteration.
β 2 − Lg,1 2 − d(6σY + 1)LX + Lg,2 + 2ρL2g,1) 2β >0, (60)
d β (γ − ρL2Y )− (LY + Lg,1 + 1 ρ ) >0. (61)
To show that ∃d ≥ 0 such that[ β − Lg,1 0
0 LY + Lg,1 + 1 ρ
] +d [ − 1β ((6σY + 1)LX + Lg,2 + 2ρL2g,1) 0
0 1β (γ − ρL 2 Y )
] 0
by S-procedure it is sufficiently to show the set X̃ = {x| (β − Lg,1)x2 < LY + Lg,1 + 1ρ , ((6σY + 1)LX + Lg,2 + 2ρL 2 g,1)x
2 > (γ − ρL2Y )} is empty. Hence, we require that
1. γ − ρL2Y > 0, (62)
which gives ρ < γ
L2Y ; (63)
2. β ≥ Lg,1;
3. and we also need
β ≥ Lg,1 + (LY + Lg,1 +
1 ρ )((6σY + 1)LX + Lg,2 + 2ρL 2 g,1)
γ − ρL2y . (64)
Note that we need 1ρβ − γ−ρL2Y
2β ≥ 0, since the potential function should be greater than 0, meaning that
L2Y ρ 2 − γρ+ 2 ≥ 0, (65)
which is actually satisfied automatically by checking the two roots of the equation L2Y ρ 2 − γρ+ 2 (note that LY ≥ γ). 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.

heading: B.3 PROOF OF THEOREM 1
text: Proof. First, we can get the upper bound of ‖∇L(Xr, Y r)‖, which is ‖∇L(Xr, Y r)‖ ≤‖Xr+1 −Xr‖+ ‖Xr+1 − projX (Xr −∇Xf(Xr, Y r))‖
+ ‖Y r+1 − Y r‖+ ‖Y r+1 − projY(Y r +∇Y f(Xr, Y r))‖ (a) ≤‖Xr+1 −Xr‖+ ‖projX (Xr+1 −∇Xf(Xr+1, Y r))− projX (Xr −∇Xf(Xr, Y r))‖ + ‖Y r+1 − Y r‖+ ‖projY(Y r+1 +∇Y f(Xr+1, Y r+1))− projY(Y r +∇Y f(Xr, Y r))‖
(b) ≤‖Xr+1 −Xr‖+ ‖∇Xf(Xr+1, Y r))−∇Xf(Xr, Y r))‖ + ‖Y r+1 − Y r‖+ ‖∇Y f(Xr+1, Y r+1))−∇Y f(Xr, Y r))‖ (66)
(c) ≤‖Xr+1 −Xr‖+ ‖∇Xh(Xr+1)−∇Xh(Xr)‖+ σY ‖∇Xg(Xr+1)− g(Xr)‖ + ‖∇Y l(Y r+1)−∇Y l(Y r)‖
d) ≤(1 + LX + σY Lg,2)‖Xr+1 −Xr‖+ (1 + LY ) ‖Y r+1 − Y r‖
where in (a) we used the optimality condition of Xr-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 Xr, Y r are within compact sets, the sizes of Xr, Y r are bounded, which implies that there exits σ1 such that
‖∇L(Xr, Y r)‖2 ≤ σ1(‖Xr+1 −Xr‖2 + ‖Y r+1 − Y r‖2︸ ︷︷ ︸ ,Cr ). (67)
From equation 59, we also know that there exits a constant σ2 , min{c1, c2} such that
Pr − Pr+1 ≥ σ2Cr. (68)
Combining equation 67, we have
‖∇L(Xr, Y r)‖2 ≤ σ1 σ2
( Pr − Pr+1 ) . (69)
Summing both sides of the above inequality over r = 1, . . . , T , we have
T∑ r=1 ‖∇L(Xr, Y r)‖2 ≤ σ1 σ2 (P1 − PT+1) ≤ σ1 σ2 (P1 − P) (70)
where in the last inequality we have used the fact that Pr is decreasing and lower bounded by P since Xr, Y r are within the compact sets. By utilizing the definition T ( ), the above inequality becomes
T ( ) ≤ σ1 σ2 (P1 − P). (71)
Dividing both sides by T ( ), and by setting C , σ1/σ2, the desired result is obtained

Review summaries:
This paper analyses the learning dynamics of GANs by formulating the problem as a primal-dual optimisation problem. This formulation assumes a limited class of models -- Wasserstein GANs with discriminators using linear combinations of base functions. Although this setting is limited, it advanced our understanding of a central problem related to GANs, and provides intuition for more general cases. The paper further shows the same analysis can be applied to multi-task learning and distributed learning.