Year: 2021

Abstract:
Generative Adversarial Networks (GANs) are commonly used for modeling complex distributions of data. Both the generators and discriminators of GANs are often modeled by neural networks, posing a non-transparent optimization problem which is non-convex and non-concave over the generator and discriminator, respectively. Such networks are often heuristically optimized with gradient descentascent (GDA), but it is unclear whether the optimization problem contains any saddle points, or whether heuristic methods can find them in practice. In this work, we analyze the training of Wasserstein GANs with two-layer neural network discriminators through the lens of convex duality, and for a variety of generators expose the conditions under which Wasserstein GANs can be solved exactly with convex optimization approaches, or can be represented as convex-concave games. Using this convex duality interpretation, we further demonstrate the impact of different activation functions of the discriminator. Our observations are verified with numerical results demonstrating the power of the convex interpretation, with applications in progressive training of convex architectures corresponding to linear generators and quadratic-activation discriminators for CelebA image generation.

heading: 1 INTRODUCTION
text: Generative Adversarial Networks (GANs) have delivered tremendous success in learning to generate samples from high-dimensional distributions (Goodfellow et al., 2014; Cao et al., 2018; Jabbar et al., 2021). In the GAN framework, two models are trained simultaneously: a generator G which attempts to generate data from the desired distribution, and a discriminator D which learns to distinguish between real data samples and the fake samples generated by generator. The GAN training problem is typically posed as a zero-sum game for which the generator and discriminator compete to optimize certain objective f
p∗ = min G max D f(G,D).
The ultimate goal of the GAN training problem is thus to find a saddle point (also called a Nash equilibrium) of the above optimization problem over various classes of (G,D). By allowing the generator and discriminator to be represented by neural networks, great advances have been made in generative modeling and signal/image reconstruction (Isola et al., 2017; Karras et al., 2019; Radford et al., 2015; Wang et al., 2018; Yang et al., 2017). However, GANs are notoriously difficult to train, for which a variety of solutions have been proposed; see e.g., (Nowozin et al., 2016; Mescheder et al., 2018; Metz et al., 2016; Gulrajani et al., 2017).
One such approach pertains to leveraging Wasserstein GANs (WGANs) (Arjovsky et al., 2017), which utilize the Wasserstein distance with the `1 metric to motivate a particular objective f . In particular, assuming that true data is drawn from distribution px, and the input to the generator is drawn from distribution pz , we represent the generator and discriminator with parameters θg and θd respectively, to obtain the WGAN objective
p∗ = min θg max θd Ex∼px [Dθd(x)]− Ez∼pz [Dθd(Gθg (z))]. (1)
When G and D are neural networks, neither the inner max, nor, the outer min problems are convex, which implies that min and max are not necessarily interchangeable. As a result, first, there is no
guarantees if the saddle points exists. Second, it is unclear to what extent heuristic methods such as Gradient Descent-Ascent (GDA) for solving WGANs can approach saddle points.
This lack of transparency about the loss landscape of WGANs and their convergence is of paramount importance for their utility in sensitive domains such as medical imaging. For instance, WGANs are commonly used for magnetic resonance image (MRI) reconstruction (Mardani et al., 2018; Han et al., 2018), where they can potentially hallucinate pixels and alter diagnostic decisions. Despite their prevalent utilization, GANs are not well understood.
To shed light on explaining WGANs, in this work, we analyze WGANs with two-layer neural network discriminators through the lens of convex duality and affirm that many such WGANs provably have optimal solutions which can be found with convex optimization, or can be equivalently expressed as convex-concave games, which are well studied in the literature (Žaković & Rustem, 2003; Žaković et al., 2000; Tsoukalas et al., 2009; Tsaknakis et al., 2021). We further provide interpretation into the effect of various activation functions of the discriminator on the conditions imposed on generated data, and provide convex formulations for a variety of generator-discriminator combinations (see Table 1). We further note that such shallow neural network architectures can be trained in a greedy fashion to build deeper GANs which achieve state-of-the art for image generation tasks (Karras et al., 2017). Thus, our analysis can be extended deep GANs as they are used in practice, and motivates further work into new convex optimization-based algorithms for more stable training.
Contributions. All in all, the main contributions of this paper are summarized as follows:
• For the first time, we show that WGAN can provably be expressed as a convex problem (or a convex-concave game) with polynomial-time complexity for two-layer discriminators and two-layer generators under various activation functions (see Table 1).
• We uncover the effects of discriminator activation on data generation through moment matching, where quadratic activation matches the covariance, while ReLU activation amounts to piecewise mean matching.
• For linear generators and quadratic discriminators, we find closed-form solutions for WGAN training as singular value thresholding, which provides interpretability.
• Our experiments demonstrate the interpretability and effectiveness of progressive convex GAN training for generation of CelebA faces.

heading: 1.1 RELATED WORK
text: The last few years have witnessed ample research in GAN optimization. While several divergence measures (Nowozin et al., 2016; Mao et al., 2017) and optimization algorithms (Miyato et al., 2018; Gulrajani et al., 2017) have been devised, GANs have not been well interpreted and the existence of saddle points is still under question. In one of the early attempts to interpret GANs, (Feizi et al., 2020) shows that for linear generators with Gaussian latent code and the 2nd order Wasserstein distance objective, GANs coincide with PCA. Others have modified the GAN objective to more implicitly enforce matching infinite-order of moments of the ground truth distribution (Li et al., 2017; Genevay et al., 2018). Further explorations have yielded specialized generators with layer-wise subspaces, which automatically discover latent “eigen-dimensions" of the data (He et al., 2021). Others have proposed explicit mean and covariance matching GAN objectives which provide stable training (Mroueh et al., 2017).
Regarding convergence of Wasserstein GANs, under the fairly simplistic scenario of linear discriminator and a two-layer ReLU-activation generator with sufficiently large width, saddle points exist and are achieved by GDA (Balaji et al., 2021). Indeed, linear discriminators are not realistic as then simply match the mean of distributions. Moreover, the over-parameterization is of high-order polynomial compared with the ambient dimension. For more realistic discriminators, (Farnia & Ozdaglar, 2020) identifies that GANs may not converge to saddle points, and for linear generators with Gaussian latent code, and continuous discriminators, certain GANs provably lack saddle points (e.g., WGANs with scalar data and Lipschitz discriminators). The findings of (Farnia & Ozdaglar, 2020) raises serious doubt about the existence of optimal solutions for GANs, though finite parameter discriminators as of neural networks are not directly addressed.
Convexity has been seldomly exploited for GANs aside from (Farnia & Tse, 2018), which studies convex duality of divergence measures, where the insights motivate regularizing the discriminator’s Lipschitz constant for improved GAN performance. For supervised two-layer networks, a recent of line of work has established zero-duality gap and thus equivalent convex networks with ReLU activation that can be solved in polynomial time for global optimality (Pilanci & Ergen, 2020; Sahiner et al., 2020a; Ergen & Pilanci, 2021a; Sahiner et al., 2020b; Bartan & Pilanci, 2021; Ergen et al., 2021). These works focus on single-player networks for supervised learning. However, extending those works to the two-player GAN scenario for unsupervised learning is a significantly harder problem, and demands a unique treatment, which is the subject of this paper.

heading: 1.2 NOTATION
text: Throughout the paper, we denote matrices and vectors as uppercase and lowercase bold letters, respectively. We use 0 (or 1) to denote a vector or matrix of zeros (or ones), where the sizes are appropriately chosen depending on the context. We also use In to denote the identity matrix of size n. For matrices, we represent the spectral, Frobenius, and nuclear norms as ‖ · ‖2, ‖ · ‖F , and ‖ · ‖∗, respectively. Lastly, we denote the element-wise 0-1 valued indicator function and ReLU activation as 1[x ≥ 0] and (x)+ = max{x, 0}, respectively.

heading: 1.3 PRELIMINARIES
text: In this paper, we consider the WGAN training problem as expressed in equation 1. We consider the case of a finite real training dataset X ∈ Rnr×dr which represents the ground truth data from the distribution we would like to generate data. We also consider using finite noise Z ∈ Rnf×df as the input to the generator as fake training inputs. The generator is given as some function Gθg : Rdf → Rdr which maps noise from the latent space to attempt to generate realistic samples using parameters θg, while the discriminator is given by Dθd : Rdr → R which assigns values depending on how realistically a particular input models the desired distribution, using parameters θd. Then, the primary objective of the WGAN training procedure is given as
p∗ = min θg max θd 1>Dθd(X)− 1>Dθd(Gθg (Z)) +Rg(θg)−Rd(θd), (2)
whereRg andRd are convex regularizers on the generator and discriminator parameters, respectively. We will subsequently analyze various realizations of discriminators and generators, and analyze the saddle point problem via convex duality. In particular, one such architecture is that of the two-layer neural network with md neurons and activation function σ, given by
Dθd(X) = md∑ j=1 σ(Xuj)vj 1.
Two activation functions that we will analyze in this work include polynomial activation σ(t) = at2 + bt+ c (of which quadratic and linear activations are special cases where (a, b, c) = (1, 0, 0) and (a, b, c) = (0, 1, 0) respectively), and ReLU activation σ(t) = (t)+.
As a crucial part of our convex analysis, we first need to obtain a convex representation for the ReLU activation. Therefore, we introduce the notion of hyperplane arrangements similiar to (Pilanci & Ergen, 2020).
1In the case of networks with bias, one can write Dθd(X) = ∑m j=1 σ(Xuj + 1bj)vj .
Hyperplane arrangements. We define the set of hyperplane arrangements asHx := {diag(1[Xu ≥ 0]) : u ∈ Rdr}, where each diagonal matrix Hx ∈ Hx encodes whether the ReLU activation is active for each data point for a particular hidden layer weight u. Therefore, for a neuron u, the output of the ReLU activation can be expressed as (Xu)+ = HxXu, with the additional constraint that (2Hx − Inr ) Xu ≥ 0. Further, the set of hyperplane arrangements is finite, i.e. |Hx| ≤ O(r(nr/r)r), where r := rank(X) ≤ min(nr, dr) (Stanley et al., 2004; Ojha, 2000). Thus, we can enumerate all possible hyperplane arrangements and denote them asHx = {H(i)x }|Hx|i=1 . Similarly, one can consider the set of hyperplane arrangements from the generated data as {H(i)g }|Hg|i=1 , or of the noise inputs to the generator: {H(i)z }|Hz|i=1 . With these notions established, we now present the main results2.

heading: 2 OVERVIEW OF MAIN RESULTS
text: As a discriminator, we consider a two-layer neural network with appropriate regularization, md neurons, and arbitrary activation function σ. We begin with the regularized problem
p∗ = min θg max vj ,‖uj‖2≤1 md∑ j=1 [ 1>σ(Xuj)− 1>σ(Gθg (Z)uj) ] vj +Rg(θg)− βd md∑ j=1 |vj | (3)
with regularization parameter βd > 0. This problem represents choice of Rd corresponding to weight-decay regularization in the case of linear or ReLU activation, and cubic regularization in the case of quadratic activation (see Appendix) (Neyshabur et al., 2014; Pilanci & Ergen, 2020; Bartan & Pilanci, 2021). Under this model, our main result is to show that with two-layer ReLU-activation generators, the solution to the WGAN problem can be reduced to convex optimization, or, in the most complex form a convex-concave game. Theorem 2.1. Consider a two-layer ReLU-activation generator of the form Gθg (Z) = (ZW1)+W2 with mg ≥ nfdr + 1 neurons, where W1 ∈ Rdf×mg and W2 ∈ Rmg×dr . Then, for appropriate choice of regularizer Rg = ‖Gθg (Z)‖2F , for any two-layer discriminator with linear or quadratic activations, the WGAN problem equation 3 is equivalent to the solution of two successive convex optimization problems, which can be solved in polynomial time in all dimensions for noise inputs Z of a fixed rank. Further, for a two-layer ReLU-activation discriminator, the WGAN problem is equivalent to a convex-concave game with coupled constraints.
In practice, GANs are often solved with low-dimensional noise inputs Z, limiting rank(Z) and enabling polynomial-time trainability. A particular example of the convex formulation of the WGAN problem in the case of a quadratic-activation discriminator can be written as
G∗ = arg min G ‖G‖2F s.t. ‖X>X−G>G‖2 ≤ βd (4)
W∗1,W ∗ 2 = arg min
W1,W2
‖W1‖2F + ‖W2‖2F s.t. G∗ = (ZW1)+W2, (5)
where the solution G∗ to equation 4 can be found in polynomial-time via singular value thresholding, formulated exactly as G∗ = L(Σ2 − βdI)1/2+ V> for any orthogonal matrix L, where X = UΣV> is the SVD of X. While equation 5 does not appear convex, it has been shown that its solution is equivalent to a convex program (Ergen & Pilanci, 2020; Sahiner et al., 2020a), which for convex sets Ki := conv{ug> : (2H(i)z − Inf )Zu ≥ 0, ‖g‖2 ≤ 1} is expressed as
{V∗i } |Hz| i=1 = arg min
Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi, (6)
The optimal solution to equation 6 can be found in polynomial-time in all problem dimensions when Z is fixed-rank, and can construct the optimal generator weights W∗1,W ∗ 2 (see Appendix C.1). This WGAN problem can thus be solved in two steps: first, it solves for the optimal generator output; and second, it parameterizes the generator with ReLU weights to achieve the desired generator output. In the case of ReLU generators and ReLU discriminators, we find equivalence to a convex-concave game with coupled constraints, which we discuss further in the Appendix (Žaković & Rustem, 2003). For certain simple cases, this setting still reduces to convex optimization.
2All the proofs and some extensions are presented in Appendix.
Theorem 2.2. In the case of 1-dimensional (dr = 1) data {xi}ni=1 where nr = nf = n, a two-layer ReLU-activation generator, and a two-layer ReLU-activation discriminator with bias, with arbitrary choice of convex regularizerRg(w), the WGAN problem can be solved by first solving the following convex optimization problem
w∗ = arg min w∈Rn Rg(w) s.t. ∣∣∣∣∣∣ 2n∑ i=j si(x̃i − x̃j) ∣∣∣∣∣∣ ≤ βd, ∣∣∣∣∣ j∑ i=1 si(x̃j − x̃i) ∣∣∣∣∣ ≤ βd,∀j ∈ [2n] (7) and then the parameters of the two-layer ReLU-activation generator can be found via
{(u∗i ,v∗i )} |Hz| i=1 = arg min
ui,vi∈Ci |Hz|∑ i=1 ‖ui‖2 + ‖vi‖2 s.t. w∗ = |Hz|∑ i=1 H(i)z Z(ui − vi),
where
x̃i =
{ xb i+12 c
, if i is odd w i
2 , if i is even
, si = { +1, if i is odd −1, if i is even , ∀i ∈ [2n]
for convex sets Ci, given that the generator hasmg ≥ n+1 neurons and βd ≤ mini,j∈[n]:i 6=j |xi−xj |.
This demonstrates that even the highly non-convex and non-concave WGAN problem with ReLUactivation networks can be solved using convex optimization in polynomial time when Z is fixed-rank.
In the sequel, we provide further intuition about the forms of the convex optimization problems found above, and extend the results to various combinations of discriminators and generators. In the cases that the WGAN problem is equivalent to a convex problem, if the constraints of the convex problem are strictly feasible, the Slater’s condition implies Lagrangian of the convex problem provably has a saddle point. We thus confirm the existence of equivalent saddle point problems for many WGANs.

heading: 3 TWO-LAYER DISCRIMINATOR DUALITY
text: Below, we provide novel interpretations into two-layer discriminator networks through convex duality.
Lemma 3.1. The two-layer WGAN problem equation 3 is equivalent to the following optimization problem
p∗ = min θg Rg(θg) s.t. max ‖u‖2≤1 |1>σ(Xu)− 1>σ(Gθg (Z)u)| ≤ βd. (8)
One can enumerate the implications of this result for different discriminator activation functions.

heading: 3.1 LINEAR-ACTIVATION DISCRIMINATORS MATCH MEANS
text: In the case of linear-activation discriminators, the expression in equation 8 can be greatly simplified.
Corollary 3.1. The two-layer WGAN problem equation 3 with linear activation function σ(t) = t is equivalent to the following optimization problem
p∗ = min θg Rg(θg) s.t. ‖1>X− 1>Gθg (Z)‖2 ≤ βd. (9)
In other terms, linear-activation discriminators seek to merely match the means of the generated data Gθg (Z) and the true data X, where regularization parameter βd controls how strictly the two must match. However, the exact form of the generated data depends on the specific parameterization of the generator, and the choice of regularization.

heading: 3.2 QUADRATIC-ACTIVATION DISCRIMINATORS MATCH COVARIANCES
text: For a quadratic-activation network, we have the following simplification.
Corollary 3.2. The two-layer WGAN problem equation 3 with quadratic activation function σ(t) = t2 is equivalent to the following optimization problem
p∗ = min θg Rg(θg) s.t. ‖X>X−Gθg (Z)>Gθg (Z)‖2 ≤ βd. (10)
In this case, rather than an Euclidean norm constraint, the quadratic-activation network enforces fidelity to the ground truth distribution with a spectral norm constraint, which effectively matches the empirical covariance matrices of the generated data and the ground truth data. To combine the effect of the mean-matching of linear-activation discriminators and covariance-matching of quadratic-activation discriminators, one can consider a combination of the two. Corollary 3.3. The two-layer WGAN problem equation 3 with quadratic activation function σ(t) = t2 with an additional unregularized linear skip connection is equivalent to the following problem
p∗ = min θg Rg(θg) s.t. ‖X>X−Gθg (Z)>Gθg (Z)‖2 ≤ βd 1>X = 1>Gθg (Z) . (11)
This network thus forces the empirical means of the generated and true distribution to match exactly, while keeping the empirical covariance matrices sufficiently close. Skip connections therefore provide additional utility in WGANs, even in the two-layer discriminator setting.

heading: 3.3 RELU-ACTIVATION DISCRIMINATORS MATCH PIECEWISE MEANS
text: In the case of the ReLU activation function, we have the following scenario. Corollary 3.4. The two-layer WGAN problem equation 3 with ReLU activation function σ(t) = (t)+ is equivalent to the following optimization problem
p∗ = min θg Rg(θg) s.t. max
‖u‖2≤1 (2H(j1)x −Inr )Xu≥0
(2H(j2)g −Inf )Gθg (Z)u≥0 ∣∣∣(1>H(j1)x X− 1>H(j2)g Gθg (Z))u∣∣∣ ≤ βd, ∀j1, j2. (12)
The interpretation of the ReLU-activation discriminator relies on the concept of hyperplane arrangements. In particular, for each possible way of separating the generated and ground truth data with a hyperplane u (which is encoded in the patterns specified byHx andHg), the discriminator ensures that the means of the selected ground truth data and selected generated data are sufficiently close as determined by βd. Thus, we can characterize the impact of the ReLU-activation discriminator as piecewise mean matching. Thus, unlike linear- or quadratic-activation discriminators, two-layer ReLU-activation discriminators can enforce matching of multi-modal distributions.

heading: 4 GENERATOR PARAMETERIZATION AND CONVEXITY
text: Beyond understanding the effect of various discriminators on the generated data distribution, we can also precisely characterize the WGAN objective for multiple generator architectures aside from the two-layer ReLU generators discussed in Theorem 2.1, such as for linear generators. Theorem 4.1. Consider a linear generator of the form Gθg (Z) = ZW. Then, for arbitrary choice of convex regularizerRg(W), the WGAN problem for two-layer discriminators can be expressed as a convex optimization problem in the case of linear activation, as well as in the case of quadratic activation provided rank(Z) is sufficiently large andRg = βg2 ‖Gθg (Z)‖ 2 F . In the case of a two-layer discriminator with ReLU activation, the WGAN problem with arbitrary choice of convex regularizer Rg(W) is equivalent to a convex-concave game with coupled constraints.
We can then discuss specific instances of the specific problem at hand. In particular, in the case of a linear-activation discriminator, the WGAN problem with weight decay on both discriminator and generator is equivalent to the following convex program
p∗ = min W βg 2 ‖W‖2F s.t. ‖1>X− 1>ZW‖2 ≤ βd. (13)
In contrast, for a quadratic-activation discriminator with regularized generator outputs,
p∗ ≥ d∗ = min G βg 2 ‖G‖2F s.t. ‖X>X−G>G‖2 ≤ βd, (14)
where G = ZW, with p∗ = d∗ under the condition that rank(Z) is sufficiently large. In particular, allowing the SVD of X = UΣV>, we define k = maxk:σ2k≥βd k, and note that if rank(Z) ≥ k, equality holds in (14) and a closed-form solution for the optimal generator weights exists, given by
W∗ = (Z>Z)− 1 2 (Σ2 − βdI) 1 2 +V >. (15)
Lastly, for arbitrary convex regularizer Rg, the linear generator, ReLU-activation discriminator problem can be written as the following convex-concave game
p∗ =min W
max rj1,j2 ,r ′ j1j2 Rg(W)− βd ∑ j1,j2 (‖rj1j2‖2 + ‖r ′ j1j2‖2) (16)
+ ∑ j1,j2 ( 1>H(j1)x X− 1>H(j2)g ZW ) (rj1j2 − r ′ j1j2)
s.t. (2H(j1)x − In)Xrj1j2 ≥ 0, (2H (j2) g − In)ZWrj1j2 ≥ 0
(2H(j1)x − In)Xr′j1j2 ≥ 0, (2H (j2) g − In)ZWr′j1j2 ≥ 0
, ∀j1 ∈ [|Hx|], ∀j2 ∈ [|Hg|],
where we see there are bi-linear constraints which depend on both the inner maximization and the outer minimization decision variables. We now move to a more complex form of generator, which is modeled by a two-layer neural network with general polynomial activation function.
Theorem 4.2. Consider a two-layer polynomial-activation generator of the form Gθg (Z) = σ(ZW1)W2 for activation function σ(t) = at2 + bt + c with fixed a, b, c ∈ R. Define z̃i = [ vec(ziz > i ) > bz>i c ]> as the lifted noise data points, in which case Gθg (Z) = Z̃W. Then, for arbitrary choice of convex regularizerRg(W), the WGAN problem for two-layer discriminators can be expressed as a convex optimization problem in the case of linear activation, as well as in the case of quadratic activation provided rank(Z̃) is sufficiently large andRg = ‖Gθg (Z)‖2F . In the case of a two-layer discriminator with ReLU activation, the WGAN problem with arbitrary choice of convex regularizerRg(W) is equivalent to a convex-concave game with coupled constraints.
Under the parameterization of lifted noise features, a two-layer polynomial-activation generator behaves entirely the same as a linear generator. The effect of a polynomial-activation generator is thus to provide more heavy-tailed noise as input to the generator, which provides a higher dimensional input and thus more degrees of freedom to the generator for modeling more complex data distributions.

heading: 5.1 RELU-ACTIVATION DISCRIMINATORS

heading: 5 NUMERICAL EXAMPLES
text: We first verify Theorem 2.2 to elucidate the power of the convex formulation of two-layer ReLU discriminators and two-layer ReLU generators in a simple setting. Let us consider a toy dataset with the data samples x = [−1, 1]T 3. Then, the convex program can be written as
min w∈R2
Rg(w) s.t. ∣∣∣∣∣∣ 4∑ i=j si(x̃i − x̃j) ∣∣∣∣∣∣ ≤ βd, ∣∣∣∣∣ j∑ i=1 si(x̃j − x̃i) ∣∣∣∣∣ ≤ βd,∀j ∈ [4]. Substituting the data samples, the simplified convex problem becomes
min w∈R2
Rg(w) s.t. |w1 + w2| ≤ βd, |w2 − 1| ≤ βd, |w1 + 1| ≤ βd. (17)
As long asRg(w) is convex in w, this is a convex optimization problem. We can numerically solve this problem with various convex regularization functions, such asRg(w) = ‖w‖pp for p ≥ 1. We visualize the results in Figure 1. Here, we observe that when βd = 0.1, the constraint set is a convex polyhedron and the optimal generator outputs are at the boundary of the constraint set, i.e., w1 = (−1 + βd) and w2 = 1− βd. However, selecting βd = 1 enlarges the constraint set such that the origin becomes a feasible point. Thus, due to havingRg(w) = ‖w‖22 in the objective, both outputs get the same value w1 = w2 = 0, which demonstrates the mode collapse issue.

heading: 5.2 PROGRESSIVE TRAINING OF LINEAR GENERATORS AND QUADRATIC DISCRIMINATORS
text: Here, we demonstrate a proof-of-concept example for the simple covariance-matching performed by a quadratic-activation discriminator for modeling complex data distributions. In particular, we consider the task of generating images from the CelebFaces Attributes Dataset (CelebA) (Liu et al., 2015), using only a linear generator and quadratic-activation discriminator. We compare the generated faces from our convex closed-form solution in equation 15 with the ones generated using the original non-convex and non-concave formulation. GDA is used for solving the non-convex problem.
We proceed by progressively training the generators layers. This is typically used for training GANs for high-resolution image generation (Karras et al., 2017). The training operates in stages of successively increasing the resolution. In the first stage, we start with the Gaussian latent code Z ∈ Rnf×df and locally match the generator weight W1 to produce samples from downsampled distribution of images X1. The second stage then starts with latent code Z2, which is the upsampled version of the network output from the previous stage ZW∗1 . The generator weight W2 is then trained to match higher resolution X2. The procedure repeats until full-resolution images are obtained. Our approach is illustrated in Figure 2. The optimal solution for each stage can be found in closed-form using equation 15; we compare using this closed-form solution, which we call Progressive Convex GAN (ProCoGAN), to training the non-convex counterpart with Progressive GDA.
3See Appendix for derivation, where we also provide an example with the data samples x = [−1, 0, 1]T .
In practice, the first stage begins with 4×4 resolution RGB images, i.e. X1 ∈ Rnr×48, and at each successive stage we increase the resolution by a factor of two, until obtaining the final stage of 64× 64 resolution. For ProCoGAN, at each stage i, we use a fixed penalty β(i)d for the discriminator, while GDA is trained with a standard Gradient Penalty (Gulrajani et al., 2017). At each stage, GDA is trained with a sufficiently wide network with m(i)d =(192, 192, 768, 3092, 3092) neurons at each stage, with fixed minibatches of size 16 for 15000 iterations per stage. As a final post-processing step to visualize images, because the linear generator does not explicitly enforce pixel values to be feasible, for both ProCoGAN and the baseline, we apply histogram matching between the generated images and the ground truth dataset (Shen, 2007). For both ProCoGAN and the baseline trained on GPU, we evaluate the wall-clock time for three runs. While ProCoGAN trains for only 153 ± 3 seconds, the baseline using Progressive GDA takes 11696 ± 81 seconds to train. ProCoGAN is much faster than the baseline, which demonstrates the power of the equivalent convex formulation.
We also visualize representative freshly generated samples from the generators learned by both approaches in Figure 3. We keep (β(1)d , β (2) d , β (3) d ) fixed, and visualize the result of training two different sets of values of (β(4)d , β (5) d ) for ProCoGAN. We observe that ProCoGAN can generate reasonably realistic looking and diverse images. The trade off between diversity and image quality can be tweaked with the regularization parameter βd. Larger βd generate images with higher fidelity but with less degree of diversity, and vice versa (see more examples in Appendix B.2). Note that we are using a simple linear generator, which by no means compete with state-of-the-art deep face generation models. The interpretation of singular value thresholding per generator layer however is insightful to control the features playing role in face generation. Further evidence and more quantitative evaluation is provided in Appendix B.2. We note that the progressive closed-form approach of ProCoGAN may also provide benefits in initializing deep non-convex GAN architectures for improved convergence speed, which has precedence in the greedy layerwise learning literature (Bengio et al., 2007).

heading: 6 CONCLUSIONS
text: We studied the WGAN training problem under the setting of a two-layer neural network discriminator, and found that for a variety of activation functions and generator parameterizations, the solution can be found via either a convex program or as the solution to a convex-concave game. Our findings indicate that the discriminator activation directly impacts the generator objective, whether it be mean matching, covariance matching, or piecewise mean matching. Furthermore, for the complex setting of ReLU activation in both two-layer generators and discriminators, we establish convex equivalents for one-dimensional data. To the best of our knowledge, this is the first work providing theoretically solid convex interpretations for non-trivial WGAN training problems, and even achieving closed-form solutions in certain relevant cases. In the light of our results, we conjecture that a similar analysis can also be applied to deeper networks and other GANs.

heading: 7 ETHICS AND REPRODUCIBILITY STATEMENTS
text: This paper aims to provide a complete theoretical characterization for the training of Wasserstein GANs using convex duality. Therefore, we believe that there aren’t any ethical concerns regarding our paper.
For the sake of reproducibility, we provide all the experimental details (including preprocessing, hyperparameter optimization, extensive ablation studies, hardware requirements, and all other implementation details) in Appendix B as well as the source (attached as a supplementary material) to reproduce the experiments in the paper. Similarly, all the proofs and explanations regarding our theoretical analysis and additional supplemental analyses can be found in Appendices C, D, E, and F.

heading: Appendix

heading: Table of Contents

heading: A Notation Summary 14

heading: B Experimental Details and Additional Numerical Examples 14
text: B.1 ReLU-activation Discriminators . . . . . . . . . . . . . . . . . . . . . . . . . . 14 B.2 Progressive Training of Linear Generators and Quadratic Discriminators . . . . . 16

heading: C Additional Theoretical Results 20
text: C.1 Convexity and Polynomial-Time Trainability of Two-Layer ReLU Generators . . 20 C.2 Norm-Constrained Discriminator Duality . . . . . . . . . . . . . . . . . . . . . 22 C.3 Generator Parameterization for Norm-Constrained Discriminators . . . . . . . . 24

heading: D Overview of Main Results 25
text: D.1 Derivation of the Form in equation 3 . . . . . . . . . . . . . . . . . . . . . . . 25 D.2 Proof of Theorem 2.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 D.3 Note on Convex-Concave Games with Coupled Constraints . . . . . . . . . . . 28 D.4 Proof of Theorem 2.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

heading: E Two-Layer Discriminator Duality 30
text: E.1 Proof of Lemma 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 E.2 Proof of Corollary 3.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 E.3 Proof of Corollary 3.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 E.4 Proof of Corollary 3.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 E.5 Proof of Corollary 3.4 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

heading: F Generator Parameterization and Convexity 31
text: F.1 Proof of Theorem 4.1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 F.2 Proof of Theorem 4.2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

heading: A NOTATION SUMMARY
text: Here, we provide a table summarizing the notation used in this paper for clarity.

heading: B EXPERIMENTAL DETAILS AND ADDITIONAL NUMERICAL EXAMPLES

heading: B.1 RELU-ACTIVATION DISCRIMINATORS
text: We first provide some non-convex experimental results to support our claims in Theorem 2.2. For this case, we use a WGAN with two-layer ReLU network generator and discriminator with the parameters (mg,md, βd, µ) = (150, 150, 10
−3, 4e− 6). We then train this architecture on the same dataset in Figure 1. As illustrated in Figure 4, depending on the initialization seed, the training performance for the non-convex architecture might significantly change. However, whenever the non-convex approach achieves a stable training performance its results match with our theoretical predictions in Theorem 2.2.
In order to illustrate how the constraints in Theorem 2.2 change depending on the number of data samples, below, we analyze a case with three data samples.
Let us consider a toy dataset with the data samples x = [−1, 0, 1]T . Then, the convex program can be written as
min w∈R3
Rg(w) s.t. ∣∣∣∣∣∣ 6∑ i=j si(x̃i − x̃j) ∣∣∣∣∣∣ ≤ βd, ∣∣∣∣∣ j∑ i=1 si(x̃j − x̃i) ∣∣∣∣∣ ≤ βd,∀j ∈ [6]. (18) Substituting the data samples, the simplified convex problem admits
min w∈R3 Rg(w) s.t. |w1 + w2 + w3| ≤ βd, |1− (w2 + w3)| ≤ βd, |w1 + w2 + 1| ≤ βd |w3 − 1| ≤ βd, |w1 + 1| ≤ βd , (19)
which exhibits similar trends (compared to the case with two samples in Figure 1) as illustrated in Figure 5.
Proof. To derive the convex form, we begin with equation 18 and simplify to: j = 1 | − (w1 + 1) + 1− (w2 + 1) + 2− (w3 + 1)| ≤ βd 0 ≤ βd j = 2 | − w1 − (w2 − w1) + (1− w1)− (w3 − w1)| ≤ βd |w1 + 1| ≤ βd j = 3 | − w2 + 1− w3| ≤ βd |1 + w1| ≤ βd j = 4 |(1− w2)− (w3 − w2)| ≤ βd |w2 − (w2 − w1) + (w2 + 1)| ≤ βd j = 5 |w3 − 1| ≤ βd |2− (1− w1) + 1− (1− w2)| ≤ βd j = 6 0 ≤ βd |(w3 + 1)− (w3 − w1) + w3
− (w3 − w2) + (w3 − 1)| ≤ βd. Simplifying the constraints above yield
j = 1 |w1 + w2 + w3| ≤ βd 0 ≤ βd j = 2 |1− (w2 + w3)| ≤ βd |w1 + 1| ≤ βd j = 3 |1− (w2 + w3)| ≤ βd |w1 + 1| ≤ βd j = 4 |w3 − 1| ≤ βd |w1 + w2 + 1| ≤ βd j = 5 |w3 − 1| ≤ βd |w1 + w2 + 1| ≤ βd j = 6 0 ≤ βd |w1 + w2 + w3| ≤ βd.
which can further be simplified to the expression in equation 19.

heading: B.2 PROGRESSIVE TRAINING OF LINEAR GENERATORS AND QUADRATIC DISCRIMINATORS
text: The CelebA dataset is large-scale face attributes dataset with 202599 RGB images of resolution 218 × 178, which is allowed for non-commercial research purposes only. For this work, we take the first 50000 images from this dataset, and re-scale images to be square at size 64 × 64 as the high-resolution baseline X5 ∈ R50000×12288. All images are represented in the range [0, 1]. In order to generate more realistic looking images, we subtract the mean from the ground truth samples prior to training and re-add it in visualization. The inputs to the generator network Z ∈ R50000×48 are sampled from i.i.d. standard Gaussian distribution.
For the Progressive GDA baseline, we train the networks using Adam (Kingma & Ba, 2014), with α = 1e − 3, β1 = 0, β2 = 0.99 and = 10−8, as is done in (Karras et al., 2017). Also following (Karras et al., 2017), we use WGAN-GP loss with parameter λ = 10 and an additional penalty driftEx∼px [D(x)2], where drift = 10−3. Also following (Karras et al., 2017), for visualizing the generator output, we use an exponential running average for the weights of the generator with decay 0.999. For progressive GDA, similar to the ProCoGAN formulation, we penalize the outputs of the generator G with penalty βg‖G‖2F for some regularization parameter βg. For the results in the main paper, we let β (i) g = 100/d (i) r where d (i) r is the dimension of the real data at each stage i. At each stage of the progressive process, the weights of the previous stages are held constant and not fine-tuned, so as to match the architecture of ProCoGAN. We plot the loss curves of the final stage of the baseline in Figure 6 to demonstrate convergence.
We emphasize that the results of Progressive GDA as shown in this paper are not identical to the original progressive training formulation of (Karras et al., 2017), with many key differences which prevent our particular architecture from generating state-of-the-art images on par with (Karras et al., 2017). Many key aspects of (Karras et al., 2017) are not captured by the architecture studied in this work, including: using higher-resolution ground truth images (up to 1024 × 1024),
progressively growing the discriminator as well as the generator, using convolutional layers rather than fully-connected layers, using leaky-ReLU activation rather than linear or quadratic-activation, fusing the outputs of different resolutions, and fine-tuning the weights of previous stages when a new stage is being trained. The objective of this experiment is not to replicate (Karras et al., 2017) exactly with a convex algorithm, but rather to simply demonstrate a proof-of-concept for the effectiveness of our equivalent convex program as an alternative to standard GDA applied to the non-concave and non-convex original optimization problem, when both approaches are applied to the same architecture of a linear generator and quadratic-activation two-layer discriminator.
For ProCoGAN, for both of the sets of faces visualized in the main paper, we arbitrarily choose (β
(1) d , β (2) d , β (3) d ) = (206, 1.6 × 103, 5.9 × 103). β (i) d are in general chosen to truncate ki singular
values of Xi = UiΣiVi, where ki can be varied.
Both methods are trained with Pytorch (Paszke et al., 2019), where ProCoGAN is trained with a single 12 GB NVIDIA Titan Xp GPU, while progressive GDA is trained with two of them. For numerical results, we use Fréchet Inception Distance (FID) as a metric (Heusel et al., 2017), generated from 1000 generated images from each model compared to the 50000 ground-truth images used for training, reported over three runs. We display our results in Table 3. We find that low values of βd seem to improve the FID metric for ProCoGAN, and these greatly outperform the baseline in terms of FID in both cases. In addition, to show further the progression of the greedy training, for both ProCoGAN and Progressive GDA in the settings described in the main paper, we show representative outputs of each trained generator at each stage of training in Figures 7, 8, 9, and 10.
Further, we ablate the values of β(i)d for ProCoGAN to show in an even more extreme case the tradeoff between smoothness and diversity, and ablate β(i)g in the case of ProgressiveGDA, which provides a similar tradeoff, as we show in Figure 11.

heading: C ADDITIONAL THEORETICAL RESULTS

heading: C.1 CONVEXITY AND POLYNOMIAL-TIME TRAINABILITY OF TWO-LAYER RELU GENERATORS
text: In this section, we re-iterate the results of (Sahiner et al., 2020a) for demonstrating an equivalent convex formulation to the generator problem equation 5:
W∗1,W ∗ 2 = arg min
W1,W2
‖W1‖2F + ‖W2‖2F s.t. G∗ = (ZW1)+W2.
In the case of ReLU-activation generators, this form appears in many of our results and proofs. Thus, we establish the following Lemma. Lemma C.1. The non-convex problem equation 5 is equivalent to the following convex optimization problem
{V∗i } |Hz| i=1 = arg min
Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi
for convex sets Ki := conv{ug> : (2H(i)z − Inf )Zu ≥ 0, ‖g‖2 ≤ 1}, provided that the number of neurons mg ≥ nfdr + 1. Further, this problem has complexity O(nrf (nfdf )
3rf ), where rf := rank(Z).
Proof. We begin by re-writing equation 5 in terms of individual neurons:
min uj ,vj mg∑ j=1 ‖uj‖22 + ‖vj‖22 s.t.G∗ = mg∑ j=1 (Zuj)+v > j . (20)
Then, we can restate the problem equivalently as (see D.1):
min ‖uj‖2≤1,vj mg∑ j=1 ‖vj‖2 s.t.G∗ = mg∑ j=1 (Zuj)+v > j . (21)
Then, we take the dual of this problem as in (Ergen & Pilanci, 2020; Sahiner et al., 2020a). First, form the Lagrangian
min ‖uj‖2≤1,vj max R mg∑ j=1 ‖vj‖2 + tr(R>G∗)− mg∑ j=1 tr(R>(Zuj)+v > j ). (22)
Then, by Sion’s minimax theorem, we can exchange the minimum over v and maximum over R, to obtain
min ‖uj‖2≤1 max R min vj mg∑ j=1 ‖vj‖2 + tr(R>G∗)− mg∑ j=1 tr(R>(Zuj)+v > j ). (23)
Minimizing this over v, we obtain the equivalent problem
min ‖uj‖2≤1 max R
tr(R>G∗) s.t.‖R>(Zuj)+‖2 ≤ 1 ∀j ∈ [mg]. (24)
Under the condition mg ≥ nfdr + 1, we obtain the equivalent semi-infinite strong dual problem
max R
tr(R>G∗) s.t.‖R>(Zu)+‖2 ≤ 1 ∀‖u‖2 ≤ 1. (25)
This over-parameterization requirement arises from the argument that this semi-infinite dual constraint can be supported by at most m∗g ≤ nfdr + 1 neurons u, and thus if mg ≥ m∗g, strong duality holds (see Lemma 5 of (Sahiner et al., 2020a), Section 3 of (Shapiro, 2009)). This problem can further be re-written as
max R tr(R>G∗) s.t. max ‖u‖2≤1 ‖R>(Zu)+‖2 ≤ 1. (26)
Using the concept of dual norm, we introduce the variable w to obtain the equivalent problem
max R tr(R>G∗) s.t. max ‖u‖2≤1 ‖w‖2≤1 w>R>(Zu)+ ≤ 1. (27)
Then, we enumerate over all potential sign patterns to obtain
max R tr(R>G∗) s.t. max ‖u‖2≤1 ‖w‖2≤1 i∈[|H(i)z |]
(2H(i)z −Inf )Zu≥0
w>R>H(i)z Zu ≤ 1, (28)
which we can equivalently write as
max R tr(R>G∗) s.t. max ‖u‖2≤1 ‖w‖2≤1 i∈[|H(i)z |]
(2H(i)z −Inf )Zu≥0
〈R,H(i)z Zuw>〉 ≤ 1, (29)
which can further be simplified as
max R tr(R>G∗) s.t. max ‖Vi‖∗≤1 Vi∈Ki 〈R,H(i)z ZVi〉 ≤ 1 ∀i ∈ [|Hz|]. (30)
We note that unlike the set of rank-one matrices satisfying the affine constraint when parameterized by uw>, the matrices Vi ∈ Ki are not necessarily rank-one, and can in fact be full-rank. In particular, Ki is the convex hull of rank-one matrices for which the left factors satisfy the ith affine ReLU constraint. We then take the Lagrangian problem
max R min λ≥0
tr(R>G∗) + |Hz|∑ i=1 λi(1− max ‖Vi‖∗≤1 Vi∈Ki 〈R,H(i)z ZVi〉), (31)
or equivalently
max R min λ≥0 min ‖Vi‖∗≤1 Vi∈Ki
tr(R>G∗) + |Hz|∑ i=1 λi − λi〈R,H(i)z ZVi〉. (32)
By Sion’s minimax theorem, we can change the order of the maximum and minimum. Then, maximizing over R leads to
min λ≥0 min ‖Vi‖∗≤1 Vi∈Ki |Hz|∑ i=1 λi s.t. G ∗ = |Hz|∑ i=1 λiH (i) z ZVi. (33)
Lastly, we note that this is equivalent to
arg min Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi (34)
as desired. The computational complexity of this problem is given as O(nrf (nfdf ) 3rf ), where rf := rank(Z) (see Table 1 of (Sahiner et al., 2020a)). The general intuition behind this complexity is that this problem can be solved with a Frank-Wolfe algorithm, each step of which requires the solution to |Hz| ≤ O(rf (nrf /df )rf ) subproblems, each of which has complexity O(nrf ). To obtain the weights to the original problem equation 5, we factor V∗i = ∑dr j=1 h ∗ ijg ∗ ij where (2H (i) z − Inf )Zh∗ij ≥ 0 and ‖g∗ij‖2 = 1, and then form
(w∗1ij ,w ∗ 2ij) =  h∗ij√ ‖h∗ij‖2 ,g∗ij √ ‖h∗ij‖2  , i ∈ [|Hz|], j ∈ [dr] as the ijth row of W∗1 and ijth column of W ∗ 2 , respectively. Re-substituting these into equation 5 obtains a feasible point with the same objective as the equivalent convex program equation 6.

heading: C.2 NORM-CONSTRAINED DISCRIMINATOR DUALITY
text: In this section, we consider the discriminator duality results in light of weight norm constraints, rather than regularization, and find that many of the same conclusions hold. In order to model a 1-Lipschitz constraint, we can use the constraint { ∑ j |vj | ≤ 1, ‖uj‖2 ≤ 1}. Then, for a linear-activation discriminator, for any data samples a, b, we have
| m∑ j=1 a>ujvj − m∑ j=1 b>ujvj | = | m∑ j=1 [ a>uj − b>uj ] vj |
≤ max ‖uj‖2≤1
[ a>uj − b>uj ] = ‖a− b‖2.
Thus, { ∑ j |vj | ≤ 1, ‖uj‖2 ≤ 1} implies 1-Lipschitz for linear-activation discriminators. For discriminators with other activation functions, we use the same set of constraints as well. Lemma C.2. A WGAN problem with norm-constrained two-layer discriminator, of the form
p∗ = min θg max∑ j |vj |≤1,‖uj‖2≤1 m∑ j=1 [ 1>σ(Xuj)− 1>σ(Gθg (Z)uj) ] vj +Rg(θg)
with arbitrary non-linearity σ, can be expressed as the following:
p∗ = min θg max ‖u‖2≤1 ∣∣∣1>σ(Xu)− 1>σ(Gθg (Zu))∣∣∣+Rg(θg) Proof. We first note that by the definition of the dual norm, we have
max∑ j |vj |≤1 m∑ j=1 cjvj = max ‖v‖1≤1 cTv = ‖c‖∞ = max j∈[m] |cj |.
Using this observation, we can simply maximize with respect to vj to obtain
p∗ = min θg max j∈[m],‖uj‖2≤1
∣∣∣1>σ(Xuj)− 1>σ(Gθg (Z)uj)∣∣∣+Rg(θg)
which we can then re-write as
p∗ = min θg max ‖u‖2≤1 ∣∣∣1>σ(Xu)− 1>σ(Gθg (Z)u)∣∣∣+Rg(θg) as desired.
Corollary C.1. A WGAN problem with norm-constrained two-layer discriminator with linear activations σ(t) = t can be expressed as the following:
p∗ = min θg ‖1>X− 1>Gθg (Z)‖2 +Rg(θg).
Proof. Start with the following
p∗ = min θg max ‖u‖2≤1 ∣∣∣1>Xu− 1>Gθg (Z)u∣∣∣+Rg(θg). Solving over the maximization with respect to u obtains the desired result:
p∗ = min θg ‖1>X− 1>Gθg (Z)‖2 +Rg(θg).
Corollary C.2. A WGAN problem with norm-constrained two-layer discriminator with quadratic activations σ(t) = t2 can be expressed as the following:
p∗ = min θg ‖X>X−Gθg (Z)>Gθg (Z)‖2 +Rg(θg).
Proof. Start with the following
p∗ = min θg max ‖u‖2≤1 ∣∣∣1>(Xu)2 − 1>(Gθg (Z)u)2∣∣∣+Rg(θg), which we can re-write as
p∗ = min θg max ‖u‖2≤1 ∣∣∣u>[X>X−Gθg (Z)>Gθg (Z)]u∣∣∣+Rg(θg). Solving the maximization over u obtains the desired result
p∗ = min θg ‖X>X−Gθg (Z)>Gθg (Z)‖2 +Rg(θg).
Corollary C.3. A WGAN problem with norm-constrained two-layer discriminator with ReLU activations σ(t) = (t)+ can be expressed as the following:
p∗ = min θg
max j1∈[|Hx|] jw∈[|Hg|] ‖u‖2≤1
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )Gθg (Z)u≥0
∣∣∣1>H(j1)x Xu− 1>H(j2)g Gθg (Z)u∣∣∣+Rg(θg).
Proof. We start with
p∗ = min θg max ‖u‖2≤1 ∣∣∣1>(Xu)+ − 1>(Gθg (Z)u)+∣∣∣+Rg(θg). Now, introducing sign patterns of the real data and generated data, we have
p∗ = min θg
max j1∈[|Hx|] j2∈[|Hg|] ‖u‖2≤1
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )Gθg (Z)u≥0
∣∣∣1>H(j1)x Xu− 1>H(j2)g Gθg (Z)u∣∣∣+Rg(θg)
as desired.

heading: C.3 GENERATOR PARAMETERIZATION FOR NORM-CONSTRAINED DISCRIMINATORS
text: Throughout this section, we utilize the norm constrained discriminators detailed in Section C.2.
C.3.1 LINEAR GENERATOR (σ(t) = t)
Linear-activation discriminator. For a linear generator and linear-activation norm-constrained discriminator (see Corollary C.1 for details), we have
p∗ = min W max ‖u‖2≤1
( 1>X− 1>ZW ) u +Rg(W)
= min W ‖1>X− 1>ZW‖2 +Rg(W).
For arbitrary choice of convex regularizerRg(W), this problem is convex.
Quadratic-activation discriminator (σ(t) = t2). For a linear generator and quadratic-activation norm-constrained discriminator (see Corollary C.2 for details), we have
p∗ = min W ‖X>X− (ZW)>ZW‖2 +Rg(W). (35)
If rank(Z) ≥ rank(X), with appropriate choice ofRg(W) = βg‖ZW‖2F , we can write this as
p∗ = min G ‖X>X−G‖2 + βg‖G‖∗, (36)
which is convex. With a symmetric solution G∗ to the above, we can factor it into G∗ = H>H, and solve the system H = ZW∗ to find the optimal original generator weight W∗, which when substituted into the original objective in equation 35 will obtain the same objective value. We note that if rank(X) > rank(Z), a valid solution W∗ is not guaranteed because the linear system H = ZW∗ has no solutions if rank(H) > rank(Z). However, since rank(H) ≤ rank(X), as long as rank(Z) ≥ rank(X), we will be able to exactly find original weights W∗ from G∗, and the two problems are equivalent.
ReLU-activation discriminator (σ(t) = (t)+).For a linear generator and ReLU-activation normconstrained discriminator (see Corollary C.3 for details), we have
p∗ = min W
max j1∈[|Hx|] jw∈[|Hg|] ‖u‖2≤1
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )ZWu≥0
∣∣∣1>H(j1)x Xu− 1>H(j2)g ZWu +Rg(W)
For arbitrary choice of convex regularizerRg(W), this is a convex-concave problem with coupled constraints, as in the weight-decay penalized case.

heading: C.3.2 POLYNOMIAL-ACTIVATION GENERATOR
text: All of the results of the linear generator section hold, with lifted features (see proof of Theorem 4.2).

heading: C.3.3 RELU-ACTIVATION GENERATOR
text: Linear-activation discriminator (σ(t) = t). With standard weight decay, we have
p∗ = min W1,W2 ‖1>X− 1>(ZW1)+W2‖2 + βg 2
( ‖W1‖2F + ‖W2‖2F ) .
We can write this as a convex program as follows. For the output of the network (ZW1)+W2, the fitting term is a convex loss function. From (Sahiner et al., 2020a), we know that this is equivalent to the following convex optimization problem
p∗ = min Vi∈Ki ∀i∈[|Hz|] ‖1>X− 1> |Hz|∑ i=1 H(i)z ZVi‖2 + βg |Hz|∑ i=1 ‖Vi‖∗,
where Ki := conv{ug> : (2H(i)z − Inf )Zu ≥ 0, ‖g‖2 ≤ 1}.
Quadratic-activation discriminator (σ(t) = t2). We have
p∗ = min W1,W2 ‖X>X− ((ZW1)+W2)>(ZW1)+W2‖2 +Rg(W1,W2).
For appropriate choice of regularizer Rg(W1,W2) = βg2 ‖(ZW1)+W2‖ 2 F and mg ≥ nfdr + 1, we can write this as G∗ = arg min
W1,W2
‖X>X−G>G‖2 + βg 2 ‖G‖2F
W∗1,W ∗ 2 = arg min
W1,W2
‖W1‖2F + ‖W2‖2F s.t. G∗ = (ZW1)+W2.
The latter of which we can re-write in convex form as shown in Lemma C.1:
{V∗i } |Hz| i=1 = arg min
Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi
for convex setsKi := conv{ug> : (2H(i)z −Inf )Zu ≥ 0, ‖g‖2 ≤ 1}. Thus, the quadratic-activation discriminator, ReLU-activation generator problem in the case of a norm-constrained discriminator can be written as two convex optimization problems, with polynomial time trainability for Z of a fixed rank.
ReLU-activation discriminator (σ(t) = (t)+). In this case, we have
arg min W1,W2
max j1∈[|Hx|] jw∈[|Hg|] ‖u‖2≤1
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )(ZW1)+W2u≥0
∣∣∣1>H(j1)x Xu− 1>H(j2)g (ZW1)+W2u∣∣∣+Rg(W1,W2).
Then, for appropriate choice of Rg(W1,W2) = βg2 ‖(ZW1)+W2‖ 2 F , assuming mg ≥ nfdr + 1, this is equivalent to
G∗ = arg min G
max j1∈[|Hx|] jw∈[|Hg|] ‖u‖2≤1
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )Gu≥0
∣∣∣1>H(j1)x Xu− 1>H(j2)g Gu∣∣∣+ βg2 ‖G‖2F
W∗1,W ∗ 2 = arg min
W1,W2
‖W1‖2F + ‖W2‖2F s.t. G∗ = (ZW1)+W2.
The latter of which we can re-write in convex form as shown in Lemma C.1:
{V∗i } |Hz| i=1 = arg min
Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi
for convex sets Ki := conv{ug> : (2H(i)z − Inf )Zu ≥ 0, ‖g‖2 ≤ 1}. Thus, the ReLU-activation discriminator, ReLU-activation generator problem in the case of a norm-constrained discriminator can be written as a convex-concave game in sequence with a convex optimization problem.

heading: D OVERVIEW OF MAIN RESULTS

heading: D.1 DERIVATION OF THE FORM IN EQUATION 3
text: Let us consider a positively homogeneous activation function of degree one, i.e., σ (tx) = tσ (x) , ∀t ∈ R+. Note that commonly used activation functions such as linear and ReLU satisfy this assumption. Then, weight decay regularized training problem can be written as
p∗ = min θg max θd m∑ j=1 ( 1>σ(Xuj)− 1>σ(Gθg (Z)uj) ) vj +Rg(θg)− βd m∑ j=1 (‖uj‖22 + v2j ).
Then, we first note scaling the discriminator parameters as ūj = αjuj and v̄j = vj/αj does not change the output of the networks as shown below
m∑ j=1 σ(Xūj)v̄j = m∑ j=1 σ(Xαjuj) vj αj = m∑ j=1 σ(Xuj)vj
m∑ j=1 σ(Gθg (Z)ūj)v̄j = m∑ j=1 σ(Gθg (Z)αjuj) vj αj = m∑ j=1 σ(Gθg (Z)uj)vj .
Moreover, we have the following AM-GM inequality for the weight decay regularization m∑ j=1 (‖uj‖22 + v2j ) ≥ 2 m∑ j=1 (‖uj‖2|vj |),
where the equality is achieved when the scaling factor is chosen as αj = ( |vj | ‖uj‖2 )1/2 . Since the scaling operation does not change the right-hand side of the inequality, we can set ‖uj‖2 = 1,∀j. Thus, the right-hand side becomes ‖v‖1 = ∑m j=1 |vj |.
We also note that this result was previously derived for linear (Ergen & Pilanci, 2021b) and ReLU (Pilanci & Ergen, 2020; Ergen & Pilanci, 2021a). Similarly, the extensions to polynomial and quadratic activations were presented in (Bartan & Pilanci, 2021).

heading: D.2 PROOF OF THEOREM 2.1
text: Linear-activation discriminator (σ(t) = t). The regularized training problem for two-layer ReLU networks for the generator can be formulated as follows
p∗ = min W1,W2 Rg(W1,W2) s.t. max ‖u‖2≤1 |1>σ(Xu)− 1>σ((ZW1)+W2)u)| ≤ βd
σ(t)=t =⇒ p∗ = min W1,W2 Rg(W1,W2) s.t. ‖1>X− 1>(ZW1)+W2)‖2 ≤ βd.
Assume that the network is sufficiently over-parameterized (which we will precisely define below). Then, we can write the problem
p∗ = min G ‖G‖2F s.t. ‖1>X− 1>G‖2 ≤ βd,
where the solution G∗ is given by a convex program. Then, to find the optimal generator weights, one can solve
min W1,W2
‖W1‖2F + ‖W2‖2F s.t. G∗ = (ZW1)+W2, (37)
which can be solved as a convex optimization problem in polynomial time for Z of a fixed rank, as shown in Lemma C.1, given by
{V∗i } |Hz| i=1 = arg min
Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi
for convex sets Ki := conv{ug> : (2H(i)z − Inf )Zu ≥ 0, ‖g‖2 ≤ 1}, provided that the generator has mg ≥ nfdr+1 neurons, and we can further find the original optimal generator weights W∗1,W∗2 from this problem.
Quadratic-activation discriminator (σ(t) = t2). Based on the derivations in Section E.3, we start with the problem
p∗ = min W1,W2 Rg(W1,W2) s.t. ‖X>X− ((ZW1)+W2)>(ZW1)+W2)‖2 ≤ βd.
Assume that the network is sufficiently over-parameterized (which we will precisely define below). Then, we can write the problem
p∗ = min G ‖G‖2F s.t. ‖X>X−G>G‖2 ≤ βd,
where the solution G∗ is given by G = L(Σ2 − βdI)1/2+ V> for any orthogonal matrix L. Then, to find the optimal generator weights, one can solve
min W1,W2
‖W1‖2F + ‖W2‖2F s.t. G∗ = (ZW1)+W2, (38)
which can be solved as a convex optimization problem in polynomial time for Z of a fixed rank, as shown in Lemma C.1, given by
{V∗i } |Hz| i=1 = arg min
Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi
for convex sets Ki := conv{ug> : (2H(i)z − Inf )Zu ≥ 0, ‖g‖2 ≤ 1}, provided that the generator has mg ≥ nfdr+1 neurons, and we can further find the original optimal generator weights W∗1,W∗2 from this problem.
ReLU-activation discriminator (σ(t) = (t)+). We start with the following problem, where the ReLU activations are replaced by their equivalent representations based on hyperplane arrangements (see Section E.5),
p∗ = min W1,W2 Rg(W1,W2)
s.t. max ‖u‖2≤1 j1∈[|Hx|] j2∈[|Hg|]
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )(ZW1)+W2u≥0
∣∣∣(1>H(j1)x X− 1>H(j2)g (ZW1)+W2)u∣∣∣ ≤ βd .
Assume that the generator network is sufficiently over-parameterized, with mg ≥ nfdr + 1 neurons. Then, we can write the problem as
G∗ = arg min G ‖G‖2F
s.t. max ‖u‖2≤1 j1∈[|Hx|] j2∈[|Hg|]
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )Gu≥0
∣∣∣(1>H(j1)x X− 1>H(j2)g G)u∣∣∣ ≤ βd
and min
W1,W2 ‖W1‖2F + ‖W2‖2F s.t. G∗ = (ZW1)+W2
the latter of which can be solved as a convex optimization problem in polynomial time for Z of a fixed rank, as shown in Lemma C.1, given by
{V∗i } |Hz| i=1 = arg min
Vi∈Ki |Hz|∑ i=1 ‖Vi‖∗ s.t. G∗ = |Hz|∑ i=1 H(i)z ZVi
for convex sets Ki := conv{ug> : (2H(i)z − Inf )Zu ≥ 0, ‖g‖2 ≤ 1}, provided that the generator has mg ≥ nfdr + 1 neurons, and we can further find the original optimal the generator weights W∗1,W ∗ 2 from this problem.
The former problem is a convex-concave problem. We begin with by forming the Lagrangian of the constraints: p∗ = min
G ‖G‖2F
s.t. min αj1≥0 γj2≥0
∀j1∈[|Hx|], j2∈[|Hg|]
∥∥∥(1>H(j1)x X− 1>H(j2)g G)+ α>j1 (2H(j1)x − Inr)X + γ>j2 (2H(j2)g − Inf)G∥∥∥ 2 ≤ βd
min α′j1 ≥0 γ′j2 ≥0
∀j1∈[|Hx|], j2∈[|Hg|]
∥∥∥−(1>H(j1)x X− 1>H(j2)g G)+ α′j1> (2H(j1)x − Inr)X + γ′j2> (2H(j2)g − Inf)G∥∥∥ 2 ≤ βd
Then, forming the Lagrangian, we have p∗ = min
G max λ,λ′≥0
αj1≥0, α ′ j1 ≥0, γj2≥0, γ ′ j2 ≥0,
∀j1∈[|Hx|], j2∈[|Hg|]
‖G‖2F
− ∑ j1j2 λj1j2 ( βd − ∥∥∥(1>H(j1)x X− 1>H(j2)g G)+ α>j1 (2H(j1)x − Inr)X + γ>j2 (2H(j2)g − Inf)G∥∥∥ 2 ) − ∑ j1j2 λ′j1j2 ( βd − ∥∥∥−(1>H(j1)x X− 1>H(j2)g G)+ α′j1> (2H(j1)x − Inr)X + γ′j2> (2H(j2)g − Inf)G∥∥∥ 2
) We can then re-write this as p∗ = min
G max
‖rj1j2‖2≤1, ‖r ′ j1j2 ‖2≤1
λ,λ′≥0 αj1≥0, α ′ j1 ≥0, γj2≥0, γ ′ j2 ≥0,
∀j1∈[|Hx|], j2∈[|Hg|]
‖G‖2F
− ∑ j1j2 λj1j2
( βd − (( 1>H(j1)x X− 1>H(j2)g G ) + α>j1 ( 2H(j1)x − Inr ) X + γ>j2 ( 2H(j2)g − Inf ) G ) rj1j2 )
− ∑ j1j2 λ′j1j2
( βd − ( − ( 1>H(j1)x X− 1>H(j2)g G ) + α′j1 > ( 2H(j1)x − Inr ) X + γ′j2 > ( 2H(j2)g − Inf ) G ) r′j1j2 ) maximizing over α, α′,γ, γ′, we have
p∗ = min G
max ‖rj1j2‖2≤1, ‖r ′ j1j2 ‖2≤1
λ,λ′≥0
‖G‖2F − βd ∑ j1j2 (λj1j2 + λ ′ j1j2) + ∑ j1j2 ( 1>H(j1)x X− 1>H(j2)g G ) (λj1j2rj1j2 − λ′j1j2r ′ j1j2)
s.t.(2H(j1)x − In)Xrj1j2 ≥ 0, (2H(j2)g − In)Grj1j2 ≥ 0, (2H(j1)x − In)Xr′j1j2 ≥ 0, (2H (j2) g − In)Gr′j1j2 ≥ 0 We can then re-parameterize this problem by letting rj1j2 = λj1j2rj1j2 and r ′ j1j2 = λ′j1j2r ′ j1j2
to obtain the final form: p∗ = min
G max
rj1j2 ,r ′ j1j2 ‖G‖2F − βd ∑ j1j2 (‖rj1j2‖2 + ‖r′j1j2‖2) + ∑ j1j2 ( 1>H(j1)x X− 1>H(j2)g G ) (rj1j2 − r′j1j2)
s.t.(2H(j1)x − In)Xrj1j2 ≥ 0, (2H(j2)g − In)Grj1j2 ≥ 0, (2H(j1)x − In)Xr′j1j2 ≥ 0, (2H (j2) g − In)Gr′j1j2 ≥ 0 which is a convex-concave game with coupled constraints, as desired.

heading: D.3 NOTE ON CONVEX-CONCAVE GAMES WITH COUPLED CONSTRAINTS
text: We consider the following convex-concave game with coupled constraints:
p∗ = min G
max rj1j2 ,r ′ j1j2 ‖G‖2F − βd ∑ j1j2 (‖rj1j2‖2 + ‖r′j1j2‖2) + ∑ j1j2 ( 1>H(j1)x X− 1>H(j2)g G ) (rj1j2 − r′j1j2)
s.t.(2H(j1)x − In)Xrj1j2 ≥ 0, (2H(j2)g − In)Grj1j2 ≥ 0, (2H(j1)x − In)Xr′j1j2 ≥ 0, (2H (j2) g − In)Gr′j1j2 ≥ 0 Here, we say the problem has “coupled constraints" because some of the constraints jointly depend on G and rj1j2 , r ′ j1j2
. The existence of saddle points for this problem, since the constraint set is not jointly convex in all problem variables, is not known (Žaković & Rustem, 2003).
However, if all the constraints are strictly feasible, then by Slater’s condition, we know the Lagrangian of the inner maximum has a saddle point. Therefore, in the case of strict feasibility, we can write the problem as
p∗ = min G
max rj1j2 ,r ′ j1j2 min λj1j2 , λ ′ j1j2 ≥0 ‖G‖2F − βd ∑ j1j2 (‖rj1j2‖2 + ‖r′j1j2‖2) + ∑ j1j2 ( 1>H(j1)x X− 1>H(j2)g G ) (rj1j2 − r′j1j2)
+ ∑ j1j2 λ>j1j2(2H (j2) g − In)Grj1j2 + ∑ j1j2 λ′j1j2 > (2H(j2)g − In)Gr′j1j2
s.t.(2H(j1)x − In)Xrj1j2 ≥ 0, (2H(j1)x − In)Xr′j1j2 ≥ 0
which by Slater’s condition is further identical to
p∗ = min λj1j2 , λ ′ j1j2 ≥0
[ min G
max rj1j2 ,r ′ j1j2 ‖G‖2F − βd ∑ j1j2 (‖rj1j2‖2 + ‖r′j1j2‖2) + ∑ j1j2 ( 1>H(j1)x X− 1>H(j2)g G ) (rj1j2 − r′j1j2)
+ ∑ j1j2 λ>j1j2(2H (j2) g − In)Grj1j2 + ∑ j1j2 λ′j1j2 > (2H(j2)g − In)Gr′j1j2 ] s.t.(2H(j1)x − In)Xrj1j2 ≥ 0, (2H(j1)x − In)Xr′j1j2 ≥ 0
For a fixed outer values of λj1j2 , λ ′ j1j2 , the inner min-max problem no longer has coupled constraints, and has a convex-concave objective with convex constraints on the inner maximization problem. A solution for the inner min-max problem can provably be found with a primal-dual algorithm (Chambolle & Pock, 2011), and we can tune λj1j2 , λ ′ j1j2
as hyper-parameters to minimize the solution of the primal-dual algorithm, to find the global objective p∗.

heading: D.4 PROOF OF THEOREM 2.2
text: Let us first write the training problem explicitly as
min θg∈Cg max uj ,bj ,vj∈R 1T md∑ j=1 ( (xuj + bj)+ − ( Gθg (z)uj + bj ) + ) vj + βd md∑ j=1 (u2j + v 2 j ) +Rg(θg).
After scaling, the problem above can be equivalently written as
min θg∈Cg Rg(θg) s.t. max |u|≤1,b ∣∣∣1T (xu+ b)+ − 1T (Gθg (z)u+ b)+∣∣∣ ≤ βd. By the overparameterization assumption, we have ( Gθg (z)u+ b ) +
= (wu+ b)+. Hence, the problem reduces to
min w∈Rn Rg(w) s.t. max |u|≤1,b ∣∣1T (xu+ b)+ − 1T (wu+ b)+∣∣ ≤ βd. (39) Now, let us focus on the dual constraint and particularly consider the following case
max b ∣∣∣∣∣∣ ∑ i∈S1 (xi + b)− ∑ j∈S2 (wj + b) ∣∣∣∣∣∣ ≤ βd, s.t. (xi + b) ≥ 0, ∀i ∈ S1, (xl + b) ≤ 0, ∀l ∈ S c 1 (wj + b) ≥ 0, ∀j ∈ S2, (wk + b) ≤ 0, ∀k ∈ Sc2 ,
(40)
where we assume u = 1 and S1 and S2 are a particular set of indices of the data samples with active ReLUs for the data and noise samples, respectively. Also note that Sc1 and Sc2 are the corresponding complementary sets, i.e., Sc1 = [n]\S1 and Sc2 = [n]\S2. Thus, the problem reduces to finding the optimal bias value b. We first note that the constraint can be compactly written as
min { min l∈Sc1 −xl, min k∈Sc2 −wk } ≥ b ≥ max { max i∈S1 −xi,max j∈S2 −wj } .
Since the objective is linear with respect to b, the maximum value is achieved when bias takes the value of either the upper-bound or lower-bound of the constraint above. Therefore, depending on the selected indices in the sets S1 and S2, the bias parameter will be either −xk or − wk for a certain index k. Since the similar analysis also holds for u = −1 and the other set of indices, a set of optimal solution in general can be defined as
(u∗, b∗) = (±1, ±xk/wk). Now, due to the assumption βd ≤ mini,j∈[n]:i6=j |xi − xj |, we can assume that x1 ≤ w1 ≤ x2 ≤ . . . ≤ xn ≤ wn without loss of generality. Note that equation 39 will be infeasible otherwise. Then, based on this observation above, the problem in equation 39 can be equivalently written as
w∗ = arg min w∈Rn Rg(w) s.t. ∣∣∣∣∣∣ 2n∑ i=j si(x̃i − x̃j) ∣∣∣∣∣∣ ≤ βd, ∣∣∣∣∣ j∑ i=1 si(x̃j − x̃i) ∣∣∣∣∣ ≤ βd,∀j ∈ [2n] (41)
where
x̃i =
{ xb i+12 c
, if i is odd w i
2 , if i is even
, si = { +1, if i is odd −1, if i is even , ∀i ∈ [2n].
After solving the convex optimization problem above for w, we need to find a two-layer ReLU network generator to model the optimal solution w∗ as its output. Therefore, we can directly use the equivalent convex formulations for two-layer ReLU networks introduced in (Pilanci & Ergen, 2020). In particular, to obtain the network parameters, we solve the following convex optimization problem
{(u∗i ,v∗i )} |Hz| i=1 = arg min
ui,vi∈Ci |Hz|∑ i=1 ‖ui‖2 + ‖vi‖2 s.t. w∗ = |Hz|∑ i=1 H(i)z Z(ui − vi),
where Ci = {u ∈ Rdf : (2H(i)z − In)Zu ≥ 0} and we assume that mg ≥ n+ 1.

heading: E TWO-LAYER DISCRIMINATOR DUALITY

heading: E.1 PROOF OF LEMMA 3.1
text: We start with the expression from equation 3
p∗ = min θg max vj ,‖uj‖2≤1 m∑ j=1 [ 1>σ(Xuj)− 1>σ(Gθg (Z)uj) ] vj +Rg(θg)− βd m∑ j=1 |vj |.
We now solve the inner maximization problem with respect to vj , which is equivalent to the minimization of an affine objective with `1 penalty:
p∗ = min θg Rg(θg) s.t. max ‖u‖2≤1 |1>σ(Xu)− 1>σ(Gθg (Z)u)| ≤ βd.

heading: E.2 PROOF OF COROLLARY 3.1
text: We simply plug in σ(t) = t into the expression of equation 8:
p∗ = min θg Rg(θg) s.t. max ‖u‖2≤1 | ( 1>X− 1>Gθg (Z) ) u| ≤ βd.
Then, one can solve the maximization problem in the constraint, to obtain
p∗ = min θg Rg(θg) s.t. ‖1>X− 1>Gθg (Z)‖2 ≤ βd
as desired.

heading: E.3 PROOF OF COROLLARY 3.2
text: We note that for rows of X given by {xi}nri=1,
1>(Xu)2 = nr∑ i=1 (x>i u) 2 = nr∑ i=1 u>xix > i u = u >X>Xu
Then, substituting into equation 8, we have:
p∗ = min θg Rg(θg) s.t. max ‖u‖2≤1 |u>
( X>X−Gθg (Z)>Gθg (Z) ) u| ≤ βd.
Then, solving the inner maximization problem over u, we obtain
p∗ = min θg Rg(θg) s.t. ‖X>X−Gθg (Z)>Gθg (Z)‖2 ≤ βd
as desired.

heading: E.4 PROOF OF COROLLARY 3.3
text: When there is a linear skip connection, we can write the problem as
p∗ = min θg max vj ,w,‖uj‖2≤1 m∑ j=1 [ 1>σ(Xuj)−1>σ(Gθg (Z)uj) ] vj+ ( 1>X−1>Gθg (Z) ) w+Rg(θg)−βd m∑ j=1 |vj |,
where σ(t) = t2. Solving over w yields the constraint that 1>X = 1>Gθg (Z). Then, following through the minimization over vj as in Lemma 3.1 and substitution of the non-linearity as in 3.3, we obtain the desired result.

heading: E.5 PROOF OF COROLLARY 3.4
text: We start with the problem equation 8, and substitute the ReLU non-linearity
p∗ = min θg Rg(θg) s.t. max ‖u‖2≤1 |1>(Xu)+ − 1>(Gθg (Z)u)+| ≤ βd.
Then, we can introduce hyper-plane arrangements as described in Section 1.3 over both X and Gθg (Z) to obtain the desired result.
p∗ = min θg Rg(θg)
s.t. max ‖u‖2≤1 j1∈[|Hx|] j2∈[|Hg|]
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )Gθg (Z)u≥0
∣∣∣(1>H(j1)x X− 1>H(j2)g Gθg (Z))u∣∣∣ ≤ βd .

heading: F GENERATOR PARAMETERIZATION AND CONVEXITY

heading: F.1 PROOF OF THEOREM 4.1
text: We will analyze individual cases of various discriminators in the case of a linear generator.
Linear-activation discriminator (σ(t) = t). We start from the dual problem (see Section E.2 for details):
p∗ = min W Rg(W) s.t. max ‖u‖2≤1 1>σ(Xu)− 1>σ(ZWu) ≤ βd
= min W Rg(W) s.t. max ‖u‖2≤1 (1>X− 1>ZW)u ≤ βd
= min W Rg(W) s.t. ‖1>X− 1>ZW)‖2 ≤ βd.
Clearly, the objective and constraints are convex, so the solution can be found via convex optimization. Slater’s condition states that a saddle point of the Lagrangian exists, and only under the condition that the constraint is strictly feasible. Given βd > 0, as long as 1>Z 6= 0, we can choose a W such that 1>X = 1>ZW, and a saddle point exists. The Lagrangian is given by
p∗ = min W max λ≥0 Rg(W) + λ(‖1>X− 1>ZW‖2 − βd).
Introducing additional variable r, we have also
p∗ = min W
max λ≥0 ‖r‖2≤1
Rg(W) + λ ( (1>X− 1>ZW)r− βd ) .
Now, v = λr, where λ = ‖v‖2
p∗ = min W max v Rg(W) + (1>X− 1>ZW)v − βd‖v‖2.
From Slater’s condition, we can change the order of min and max without changing the objective, which proves there is a saddle point:
p∗ = max v min W Rg(W) + (1>X− 1>ZW)v − βd‖v‖2.
The inner problem is convex and depending on choice ofRg(W) can be solved for W∗ in closed form, and subsequently the outer maximization is convex as well. Thus, for a linear generator and linear-activation discriminator, a saddle point provably exists and can be found via convex optimization.
Quadratic-activation discriminator (σ(t) = t2). We start from the following dual problem (see Section E.3 for details)
p∗ = min W Rg(W) s.t. ‖X>X− (ZW)>(ZW)‖2 ≤ βd.
This can be lower bounded as follows:
p∗ ≥ d∗ = min G βg 2 ‖G‖2F s.t. ‖X>X−G>G‖2 ≤ βd. (42)
Which can further be written as:
d∗ = min G̃ βg 2 ‖G̃‖∗ s.t. ‖X>X− G̃‖2 ≤ βd.
This is a convex optimization problem, with a closed-form solution. In particular, if we let X>X = VΣ2V> be the eigenvalue decomposition of the covariance matrix, then the solution to equation 42 is found via singular value thresholding:
G∗ = V(Σ2 − βdI)+V>. This lower bound is achievable if ∃W : (ZW)>(ZW) = G∗. A solution is achieved by allowing W = (Z>Z)−1/2(Σ2 − βdI)1/2+ V>, where computing (Z>Z)−1/2 requires inverting only the first k eigenvalue directions4, where k := maxk:σ2k≥βd k. Thus given that rank(Z) ≥ k, the solution of the linear generator, quadratic-activation discriminator can be achieved in closed-form.
In the case that rank(Z) ≥ k + 1, strict feasibility is obtained, and by Slater’s condition a saddle point of the Lagrangian exists. One can form the Lagrangian as follows:
p∗ = min G max R 0 βg 2 ‖G‖∗ + tr(RX>X)− tr(RG)− βdtr(R).
This is a convex-concave game, and from Slater’s condition we can exchange the order of the minimum and maximum without changing the objective:
p∗ = max R 0 min G βg 2 ‖G‖∗ + tr(RX>X)− tr(RG)− βdtr(R).
ReLU-activation discriminator (σ(t) = (t)+). We again start from the dual problem (see Section E.5 for details)
p∗ = min W Rg(W)
s.t. max ‖u‖2≤1 j1∈[|Hx|] j2∈[|Hg|]
(2H(j1)x −Inr )Xu≥0 (2H(j2)g −Inf )ZWu≥0
∣∣∣(1>H(j1)x X− 1>H(j2)g ZW)u∣∣∣ ≤ βd .
We can follow identical steps of the proof of Theorem 2.1 (see Section D.2), with ZW instead of G, obtain
p∗ = min W
max rj1j2 ,r ′ j1j2 Rg(W)− βd ∑ j1j2 (‖rj1j2‖2 + ‖r′j1j2‖2) + ∑ j1j2 ( 1>H(j1)x X− 1>H(j2)g ZW ) (rj1j2 − r′j1j2)
s.t.(2H(j1)x − In)Xrj1j2 ≥ 0, (2H(j2)g − In)ZWrj1j2 ≥ 0, (2H(j1)x − In)Xr′j1j2 ≥ 0, (2H (j2) g − In)ZWr′j1j2 ≥ 0 as desired. Thus, as long as Rg is convex in W, we have a convex-concave game with coupled constraints.
4For instance, letting Z = QΛQ>, we can use (Z>Z)−1/2 = Q[:k]Λ−1[:k], where ·[:k] indicates taking the first k columns/diagonal entries respectively.

heading: F.2 PROOF OF THEOREM 4.2
text: We note that for a polynomial-activation generator with m neurons and corresponding weights w(1)j , w (2) j , for samples {zi} nf i=1:
Gθg (zi) = m∑ j=1 σ(z>i w (1) j )w (2) j >
= m∑ j=1 ( a(z>i w (1) j ) 2 + b(z>i w (1) j ) + c)w (2) j >
= m∑ j=1 ( a〈ziz>i ,w (1) j w (1) j > 〉+ b(z>i w (1) j ) + c)w (2) j >
= m∑ j=1 avec(ziz>i )bzi c >  vec(w (1) j w (1) j > )w (2) j > w (1) j w (2) j >
w (2) j
>  =
m∑ j=1 z̃>i wj
=  z̃>1 z̃>2 · · · z̃>nf W = Z̃W
for z̃i := avec(ziz>i )bzi c  as the lifted features of the inputs, and a re-parameterized weight matrix wj :=  vec(w (1) j w (1) j > )w (2) j > w (1) j w (2) j >
w (2) j
>  (Bartan & Pilanci, 2021). Thus, any two-layer polynomialactivation generator can be re-parameterized as a linear generator, and thus after substituting Z̃ as Z for Theorem 4.1, we can obtain the desired results.

Review summaries:
 +++ After Rebuttal +++ I updated my rating to accept after reading the author(s)'s rebuttal and other reviews. +++++++++++++++++  This paper reformulates WGAN as a convex (or convex-concave) game under restricting neural architectures and convex regularizers. An efficient algorithm based on matrix factorization is proposed to solve the problem analytically. 

In this paper, novel theoretical results that express two-layer WGAN training as convex-concave games are established. Ample theoretic theorems and propositions, as well as insightful interpretations, are given under various activation function settings, including linear, quadratic, and ReLU. Finally, proof-of-concept experiments are conducted to verify the theoretic results, where the proposed method that utilizes the explicit convex-concave game solutions are shown to generate better visual quality images than traditional non-convex trained results.   The main novelty of the paper comes from the theoretic results of the convex interpretation of the non-trivial WGAN training problem. Novel closed forms are given for certain training settings. The proposed ProCoGAN model based on the theoretic results is also novel. 

In this paper, the authors analyzed the training of Wasserstein GANs with two-layer neural network discriminators.  They showed that WGAN can provably be expressed as a convex problem (or a convex-concave game) with polynomial-time complexity for two-layer discriminators and two-layer generators under various activation functions.   They uncovered the effects of discriminator activation on data generation through moment matching, where quadratic activation matches the covariance, while ReLU activation amounts to piecewise mean matching. They found closed-form solutions for WGAN training as singular value thresholding, which provides interpretability. Their experiments demonstrate the interpretability and effectiveness of progressive convex GAN training for generation of CelebA faces.