Hidden Convexity of Wasserstein GANs: Interpretable Generative Models with Closed-Form Solutions
Authors: Arda Sahiner
Tolga Ergen
Batu Ozturkler
Burak Bartan
John M. Pauly
Morteza Mardani
Mert Pilanci
Venue: ICLR 2022 Poster (2022)
Keywords: Wasserstein GAN
convex-concave game
saddle points
generative models
quadratic
polynomial activation
convex duality

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 descent-ascent (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 an application in progressive training of convex architectures corresponding to linear generators and quadratic-activation discriminators for CelebA image generation. The code for our experiments is available at https://github.com/ardasahiner/ProCoGAN.

Published as a conference paper at ICLR 2022
HIDDEN CONVEXITY OF WASSERSTEIN GANS: INTERPRETABLE GENERATIVE MODELS WITH CLOSED-FORM SOLUTIONS
Arda Sahiner, Tolga Ergen; Batu Ozturkler, Burak Bartan, John Pauly, Morteza Mardani & Mert Pilanci Department of Electrical Engineering
Stanford University Stanford, CA 94305, USA
(sahiner, ergen, ozt, bbartan, pauly, morteza, www.oorteaaaillaraaaa p @@stanford.edh
ABSTRACT
Generative Adversarial Networks (GANs) are commonly used for modeling com-- plex distributions of data. Both the generators and discriminators of GANs often modeled by neural networks, posing non-transparent optimization prob- lem which is non-convex and non-concave tor, respectively. Such networks are often heuristically optimized with gradi- ent descent-ascent (GDA), but it is unclear whether the optimization problem contains any saddle points, or whether heuristic methods can find them in prac- tice. In this work, we analyze the training of Wasserstein GANs with two-layer neural network discriminators through the lens of convex duality, and for va- riety of generators expose the conditions under which Wasserstein GANs can be solved exactly with convex optimization approaches, 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 the convex interpretation, with applications in progressive training of convex archi- discrimina-
the generator and discrimina-
can be represented
tectures corresponding to linear generators and quadratic- for CelebA image generation. The code for our experiments is available https::/gile com a www.aaaaaaaannneeeeaaa httpr/aaaaaaaeeeerroooaaaa
INTRODUCTION
Generative Adversarial Networks (GANs) have delivered tremendous success in learning 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 simultancously: generator G which attempts to generate data from the desired distribution, and a discriminator which learns to distinguish between real data samples and the fake samples generated by generator. This problem is typically posed as a zero-sum game for which the generator and discriminator compete to optimize objective f
min max ((G,))
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 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 8 Yang al.) (017). However, GANs are notoriously difficult to train, for which a variety of solutions have been proposed; see c.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 & metric to motivate particular objective f. In particular, assuming that true data is drawn from distribution Pz, and the input to the generator is
Equual Contribution

---

Published as a conference paper at ICLR 2022
Table I: Convex landscape and interpretation WGAN with two-layer discriminator under different criminator activation functions and generator architectures. Note that adding a linear skip connection to the discriminator imposes an additional mean matching constraint when using quadratic activation.
Discriminator
Linear Activation
Quadratic Activation
ReLU Activation
Generator
Linear
convex
convex, closed form convex, closed form convex covariance matching
convex-concave
2-layer (polynomial)
convex
convex-concave convex-comcave
2-layer (ReLU)
convex
Interpretation
mean matching
piecewise mean matching
drawn from distribution Ps. represent the generator and discriminator with parameters 0g and Oa respectively, to obtain the WGAN objective
min max Ex-p, (Do, (x)] Rezpp, [Do, (2)))
0g 84
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 Rescent-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 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 (Zaković & Rustem 2003 Zaković al., 2000; Tsoukalas et al., 2009 Tsaknakis 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 variety of cnnerator-discriminato combinations (see Table We further note that such shallow neural network architectures can be trained in a greedy fashion to build deeper GANs which achieve state-of-th the art for image generation tasks (Karras et al.) 2017). Thus, our analysis can be extended deep GANs 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-tima complexity for two-layer discriminators and two-layer generators under various activation functions (see Table [
We uncover the effects of discriminator activation on data generation through moment matching, where quadratic activation matches the covariance, while ReLU activation amounts 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.
1.1 RELATED WORK
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 al. [207)] 7) have been devised, GANs have not been well interpreted and the existence of saddle points is still under question. 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
2

---

Published as a conference paper at ICLR 2022
objective, GANs coincide with PCA. Others have modified the GAN objective to implicitly enforce matching infinite-oris fifiitt--rder of moments of the ground truth distribution (Li et al. 2017 Genevay et al.) 2018). Further explorations have yielded specialized generators with layer-wis 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 for stable training (Mroueh et al. 2017).
Regarding convergence of Wasserstein GANs, under the fairly simplistic scenario of linear discrimi- nator and two-layer ReLU-activation generator with sufficiently large width, saddle points exist and are achieved by GDA (Balaji et al. 202T). Indeed, linear discriminators are not realistic as then simply match the mean of distributions. Moreover, the over peer-aarmmterizationn 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 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, 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 iet al. 2020a; Ergen & Pilanci 2021d Sahiner et al. 2020b Bartan & Pilanci 2021 Ergen et al. 2021). These works focus on single-player networks for supervised learning. However, exlending
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.
1.2 PRELIMINARIES
Throughout the paper, we denote matrices and vectors as uppercase and lowercase bold letters, respectively. We use 0 (or 1) to denote a vector and matrix of zeros (or ones), where the sizes are appropriately chosen depending on the context. We also use I, to denote the identity matrix of size For matrices, we represent the spectral, Frobenius, and nuclear norms as || 1l2. || ||,, and || ||.. respectively. Lastly, we denote the element- wise 0-1 valued indicator function and ReLU activation as [z 2 0j and (x)+ = max (x. 0}, respectively.
In this paper, we consider the WGAN training problem as expressed in equation 1 the case of a finite real training dataset X E xd, which represents the ground truth data from the distribution we would like generate data. We also consider using finite noise Z E [2nyxd as the input to the generator as fake training inputs. The generator is given as some function Go, : Rdd + d which maps noise from the latent space attempt to generate realistic samples using parameters Og. while the discriminator is given by Do. : Rd + IR which assigns values depending on how realistically particular input models the desired distribution, using parameters 0g. Then, the primary objective of the WGAN training procedure is given as
We consider
p' min max 1 De 02 0g
1 D& (Go, (Z)) Rg((,) (aa))).
where Rg and R2 are regularizers for generator and discriminator, respectively. We will analyze realizations of discriminators and generators for the saddle point problem via convex duality. One such architecture is that of the two-layer network with my neurons and activation a, given by
(x)
Σ (Xu 3=1
Two activation functions that we will analyze in this work include polynomial activation (tt) at? + bt + e (of which quadratic and linear activations are special cases where (a, b, c) = 01, and (a, b, convex analysis, we first need to obtain a convex representation for the ReLU activation. Therefore,
(0, 1, O) respectively), and ReLU activation (t) (+)+. As crucial part of our
we introduce the notion of hyperplane arrangements similar (Pilanci Ergen 2020).
In the of networks with bias, one can write (x, En (Xu, + 16,)a--
3

---

Published as a conference paper at ICLR 2022
Hyperplane arrangements. We define the set of hyperplane arrangements H₂ := (diag(1[Xu 0)) : u E [. where each diagonal matrix H₂ E He encodes whether the ReLU activation is active for each data point for a particular hidden layer weight Therefore, for a neuron the output of the ReL.U activation can be expressed as (Xu)+ = Xu, with the additional constraint that (2H, In.) Xu 2 O. Further, the set of hyperplane arrangements is finite, i.e. 172=| & ((r(n//r)") where == rank I min(n,, d,) (Stanley et al., 2004 Ojha 2000). Thus, we can enumerate all possible hyperplane arrangements and denote them as Hr = (H == Similarly, one can consider the set of hyperplane arrangements from the generated data as {H) li=1 or of the noise inputs to the generator: { ( |Ptel,
(1 2
With these notions established, we now present the main results 2 T=ll
2 OVERVIEW OF MAIN RESULTS
As a discriminator, we consider a two-layer neural network with appropriate regularization, ma neurons, and arbitrary activation function a. We begin with the regularized problem
md
md
p' min 0g
max 1ll
Σ
(Xx,) - - (Z),,) by + (O,) 3d
by
(3)
with regularization parameter 3a >> O. This problem represents choice of R. corresponding to weight- decay regularization the case of linear or ReLU activation, and cubic regularization the case of quadratic activation (see Appendix) (Neyshabur et al., 2014 Pilanci & Ergen 2020 Bartan & Pilanci 202Th. Under this model, our main result is to show that with two-layer Rel. Reatiiaati generators, the solution to the WGAN problem can be reduced to convex optimization or a convex-concave game.
Theorem 2.1. Consider a two-layer Rel U-attivatioon generator of the form Gz,(Z) = (ZW1) W₂ with my 2 nyd, + neurons, where W1 E Rd xm and W2 E Rm xd._ Then, for appropriate choice of regularizer Rg = =Ga,, 3 IZ)
f. for any two-layer discriminator with linear or quadratic activations, the WGAN problem equation 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-activatie discriminator, the WGAN problem is equivalent to a comvex-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 quadratic-activatie discriminator can be written
G = arg min
1/ G s.t.
| X
G G S 3a
(4)
Wi. W = arg min
W1 P + W2 13 s.t. GO (ZW1), W2,
(5)
W,
where the solution Go to equation can be found in polynomial-tin -iatimmill--eeeeeeeeee via singular value thresholding.
formulated exactly as G L( 2/1) for any orthogonal matrix L, where X = UΣV the SVD of X. While equation 5 does not appear convex, has been shown that its solution is equivalent to convex program (Ergen & Pilanci, 2021a Sahiner et al. 2020a). which for the norm
[S]]|,, min t s.t. S e tconv (Z = hg" (2H. In, Yuu 2 O. IZ|- S 1) is expressed as
196.1
(V)) W
|Mal
= arg min
Σ 1=1
[V s.t. G = Σ
1 ZV.
(6)
V.
The optimal solution to equation can be found in polynomial-time in all problem dimensions when Z is fixed-rank, and can construct the optimal generator weights Wi, W (see Appendix C.I). 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 achieve the desired generator output. In the case of ReL.U generators and ReLU discriminators, we find equivalence to convex-concave game with coupled constraints, which we discuss further in the Appendix (Zaković & Rustem 2003). For certain simple cases, this setting still reduces to convex optimization.
2 All the proofs and some extensions are presented in Appendix.
4

---

Published as a conference paper at ICLR 2022
Theorem 2.2. In the case of I-dimensional (d, data { where Tor nn two-layer ReLU--ctivvtiin generator, and two-layer ReLU-activvtion discriminator with bias, with arbitrary choice of convex regularizer R.g (w), the WGAN problem can be solved by first solving the following convex optimization problem
2n
W = arg min R (w) s.f.
Σ
(
S Sd. Σ s - 24)
S Ba. [2n]
(7)
wER"
and then the parameters of the two-layer ReLU-activatie generator can be found via
HH
[Hg
{(u), W
arg min U.V.
|uu:le + lIvel12 s.t. w Z(u, -v))
where
L Dap
if is odd
81 +1, if is odd
7.
vi E [2m]
i is even
1, if is
for convex sets C,, given that the generator has mg 2 n n++1111 neurons and Ba S jelnaas [c; --y--
This demonstrates that even the highly non-convex and non-concave WGAN problem with ReLU- activation networks can be solved using convex optimization polynomial time when 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 discriminators and generators. the cases that the WGAN problem is equivalent to a convex problem, if the constraints of the convex problem are strictly feasible, Slater's s condition implies Lagrangian the convex problem provably has saddle point. We thus confirm the existence of equivalent saddle point problems for many WGANs.
3 TWO-LAYER DISCRIMINATOR DUALITY
Below, we provide novel interpretations into two-layer discriminator networks through convex duality, Lemma 3.1. The two-layer WGAN problem equation is equivalent to the following optimization problem
p" = min (0g) s.t. max [1 T (Xu) -1 (Ge, (Z)u) S Ba. ulla$1
(8)
6g
One can enumerate the implications of this result for different discriminator activation functions.
3.1 LINEAR-ACTIVATION DISCRIMINATORS MATCH MEANS
In the case of linear-activation discriminators, the expression in equation Cecation&caan can be greatly simplified.
Corollary 3.1. The two-layer WGAN problem equation with linear activation fanction (1) = l. is equivalent to the following optimization problem
p min R,, s.t. || - 1 1 Go, (2)l2 S Ba-
0g
Linear-action activation discriminators seek merely match the means of the generated data Go (Z) and the true data X, where parameter Pa controls how strictly the two must match. However, the exact form of the generated data depends on the parameterization of the generator and the regularization.
3.2 QUADRATTIC-ACTIVATIOO DISCRIMINATORS MATCH COVARIANCES
For iuaudraaii-actiattion network, have the following simplification. Corollary 3.2. The two-layer WGAN problem equation with quadratic activation function (t) = 12 is equivalent the following optimization problem
p* = min (0,,) S.I. X Go, (2) GG, (Z)ll2 E Ba-
(10)
0,
5

---

Published as a conference paper at ICLR 2022
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 consider combination of the two.
Corollary 3.3. The two-layer WGAN problem equation with quadratic activation function at) t² with an additional unregularized linear skip connection equivalent to the following problem
XX x - -G (Z)
Ba
p min (gy s.t. 8
(11)
1 1 = 1
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.
3.3 RELU-ACTIVATION DISCRIMINATORS MATCII PIECEWISE MEANS
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 functionn at) (f)+
is equivalent to the following optimization problem
p= min Rg (0g) s.t.
max 11|2
( HH Ga,
Go,()),) (2))ul S Ba, Vji,22.
0g
(2H In, Xu20
(2H(f2) , Go, (2)u20
(12)
The interpretation of the ReLU-activation discriminator relies on the concept of hyperplane arrange- ments. In particular, for each possible way of separating the generated and ground truth data with hyperplane u (which encoded in the patterns specified by Hz and Hy), the discriminator ensures that the means of the selected ground truth data and selected generated data are sufficiently close as determined by 3a. 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-moda distributions.
4 GENERATOR PARAMETERIZATION AND CONVEXITY
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 Thcorem 2.I, such as for linear generators.
Theorem 4.1. Consider linear generator of the form Go, (Z) ZW. Then, for arbitrary choice of convex regularizer (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) ) sufficiently large and R2 = 2 G Il) ... In the case of a two-layer discriminator with ReLU activation, the WGAN problem with arbitrary choice of convex regularizer R.y (W) is equivalent to a convex-concave game with coupled constraints.
We can then discuss specific instances of the specifie problem at hand. In particular, in the case of a linear- activation discriminator, the WGAN problem with weight decay on both discriminator and generator equivalent to the following convex program
Bn W 2 s.t. ||1 |
min 2
1 ZW 2 S Ba.
(13)
In contrast, for quadratic-actiiation discriminator with regularized generator outputs,
p" 2 d" = min & G s.t. X x - X G S 3a,
(14)
G
2

---

Published as a conference paper at ICLR 2022
where G ZW. with p' = d' under the condition that rank(Z)) is sufficiently large. In particular, allowing the SVD X = UEV", we define = maX k. and note that rank(Z) 2 k, equality holds in (4) and a closed-form solution for the optimal generator weights exists, given by
w = -
(15)
Lastly, for arbitrary convex regularizer Rg. the linear generator, Rel.U-activation discriminator problem can be written as the following convex-concan game
p' min max R((W) W
Ba Σ
(1 lla (11)
(16)
d2 1/12
21.22
+
Σ
(T (1 X (TH(aaZ) (In152 - -5
J1-22
(2H (1) - 1. Xr 51 2 0, (2H
(7s)
- Z
12 2 0
(2H (11) 1,. Xr J1J2 0, (2H U2) I.. Zrr J:32 2 Vii E 1| J. Via [|H
where we see there are bi-linear constraints which depend on both the inner maximization and the outer minimization decision variables. We now move more complex form of generator, which is modeled by a two-layer neural network with general polynomial activation function.
Theorem 4.2. Consider two-layer elyyomial-activatioo generator of the form Go (Z) =
a 1 W2 for activation function (t) at + bt + with fixed a, b. E R. Define [vec(z,z,)) bz c] as the lifted noise data points. in which case Go = Žw. Then, for arbitrary choice of convex regularizer Rg (W), the WGAN problem for two-layer discrimi- nators can be expressed as convex optimization problem in the case of linear activation, well as in the case of quadratic activation provided rank(Z) is sufficiently large and Rg =IGa (Z) In the case of two-layer discriminator with ReLU activation, the WGAN problem with arbitrary choice of convex regularizer (W) is equivalent to a convex-concave game with coupled constraints.
2, =
Under the parameterization of lifted noise features, two-layer polynomia--activati generator behaves entirely the same as linear generator. The effect of a polynomial-activaiie generator is thus to provide more heavy-taile -tiled noise as input to the generator, which provides higher dimensional input and thus more degrees of freedom to the generator for modeling more complex data distributions.
5 NUMERICAL EXAMPLES
5.1
RELU-ACTIVATION DISCRIMINATORS
0.5
25-
1.2
Combbait
Real data
135
55
06
(a) 34
0.1
Generator space
(c) 38
(d) Generator space
Figure 1: Numerical illustration of Theorem 2.2 for ReLU generator/discrimnnato with 1D data
x [[1, 1]" and R., w-= ||w 1/z. For 3a = O.I. we observe that the constraint set of the convex program in equation 17 is a convex polyhedron shown in (b) and the optimal generator output is the vertex wi (-1+ 3d) and w2
3z. In contrast, for 3a = 1, the constraint set in (d) is the larger scaled polyhedra and includes the origin. Therefore, the optimal generator output becomes Wi = W2 = 0, which corresponds to the overlapping points in (c) and demonstrates mode collapse.
We first verify Theorem 2.2 to elucidate the power of the convex formulation of two-layer ReLU discriminators and two-layer ReI.U generators in simple setting. Let us consider toy dataset with
7

---

Published as a conference paper at ICLR 2022
Z
Wi
ZWi
W 2
W 4
ZW1
W
W
W2
W 5
4 X
4 4
8 8
8 x 8
64 x 64
64 x 64
X1
X2 2
X
D1
D2
Ds
Figure 2: A modified architecture for progressive training of convex GANs (ProCoGAN), At each stage linear generator W. is used to model images given resolution X,, attempting fool quadratic-activation discriminator D.. which trained, the input to stage i + 1 is given as the output of the previous stage with learned weights W7, which is then used to model higher-resee resoluorooolution images X The procedure continues until nigh-resolution images can be generated from successive application of linear generators.
optimal solution can be found closed-form via equation [3 Once stage
the data samples [-1, 1 Then, the convex program can be written
Rg( s.t. WER?
min
Σ s; 85)
S 3d:
Σ (6 2.) S Ba, [4].
Substituting the data samples, the simplified convex problem becomes
min (w) s.t. |wi + w22l S Ba, Ww2 1| S Ba, |wi + 1 S Sa.
(17)
WER2
As long as (w) is convex in w, this is convex optimization problem. We can numerically solve this problem with various convex regularization functions, such as Ry (w) ||wl] I for p I.
We visualize the results in Figure | Here, we observe that when 8& = 0.1, the constraint set is convex polyhedron and the optimal generator outputs are at the boundary of the constraint set, iee, W1 = (-1+ Ba) and Wy = 1 - Sd. However, selecting 3g = 1 enlarges the constraint set such that the origin becomes feasible point. Thus, due having R, (w) = ||wl|2 in the objective, both outputs get the same value wi W2 O, which demonstrates the mode collapse issue.
5.2 PROGRESSIVE TRAINING OF LINEAR GENERATORS AND QUADRATIC DISCRIMINATORS
Here, we demonstrate proof-of-concept example for the simple covariance- performed by quadratic-activatee discriminator for modeling complex data distributions. In particular, we consider the task of generating images from the CelebFaces Attributes Dataset (CelebA) (Liu al., 2015). using only linear generator and quadratic-ate citttaiiiccavvatiionn 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-concan formulation. GDA is used for solving the non-convex problem.
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 Xdy and locally match the generator weight Wi to produce samples from downsampled distribution of images X,. The second stage then starts with latent code Ze, which is the upsampled version of the network output from the previous stage ZW The generator weight W, is then trained to match higher resolution X2. The procedure repeats until full-resolution images are obtained. Our approach is illustrated in Figure 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), training the non-convex counterpart with Progressive GDA.
See Appendix for derivation, where also provide an example with the data samples [-1,0, 1)7.
8

---

Published as a conference paper at ICLR 2022
(a) ProCoGAN (Ours). Top: ( ((0) ) (7.2x10), 1.0x10+)
Bottom: (o) 3(3) )= (1.9x10 3.3x101
(b) Progressive GDA (Baseline)
Figure 3: Representative generated faces from ProCoGAN and Progressive GDA with stagewise training of linear generators and quadratic-activatii discriminators on CelehA (Figure ProCoGAN only employs the closed-form expression equation 15 where Ba controls the variation and smoothness in the generated images.
In practice, the first stage begins with 4x4 resolution RGB images, i.e. X, E R* and at each successive stage we increase the resolution by a factor of two, until obtaining the final stage of 64 x 64 resolution. For ProCoGAN, at each stage i, we use fixed penalty 8. for the discriminator, while GDA is trained with a standard Gradient Penalty (Gulrajani et al. 2017). At each stage, GDA is trained with sufficiently wide network with ma stage, with fixed minibatches of size 16 for 15000 iterations per stage. As 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.
(6) = (192, 192, 768, 3092, 3092) neurons each
We also visualize representative freshly generated samples from the generators learned by both approaches in Figure 3 We keep (g( g(2) g(3)) fixed, and visualize the result of training two .
different sets of values of (s) (00) 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 Ba. Larger 3a generate images with higher fidelity but with less degree of diversity, and vice versa (see more examples in Appendix B.2) Note that we
using a simple linear generator, which by no means compete with state-of 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 face generation. Further evidence and more quantitative evaluation is provided in Appendix [..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
6 CONCLUSIONS
We studied 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 indicate that the discriminator activation directly impacts the generator objective, whether be mean matching, covariance matching, or piecewise mean matching. Furthermore, for the more complicated 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 and existing convex duality analysis for deeper networks, e.g., Ergen & Pilanci (2021b e); Wang et al. (202I) we conjecture that similar analysis can also be applied to deeper networks and other GANs.
game. Our findings

---

Published as a conference paper at ICLR 2022
7 ACKNOWLEDGEMENTS
This work was partially supported by the National Science Foundation under grants ECCS-2037920 DMS-2134248, the Army Research Office, and the National Institutes of Health under grants ROIEB009690 and U01EB029427.
ETHICS AND REPRODUCIBILITY STATEMENTS
This paper aims to provide complete theoretical characterization for the training of Wasser- stein GANs using convex duality. Therefore, we believe that there aren't any ethical con- cerns regarding our paper. For the sake of reproducibility, we provide all the experimental details (including preprocessing, hyperparameter optimization, extensive ablation studies, hard- ware requirements, and all other implementation details) Appendix B as well as the source to reproduce the experiments in the pa- per. Similarly, all the proofs and explanations regarding our theoretical analysis and additional supplemental analyses can be found in Appendices
(https://gi hhub...tttu......m com/ cettassainerrProCCC
and F
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pp. 214 423. PMLR, 2017.
Yogesh Balaji, Mohammadmahdi Sajedi, Neha Mukund Kalibhat, Mucong Ding, Dominik Stöger, Mahdi Soltanolkotabi. and Soheil Feizi. Understanding overparameteriiatioo in generative adver- sarial networks. arXiv preprint arXiv:2104.05605 2021.
Burak Bartan and Mert Pilanci. Neural spectrahedra and semidefinite lifts: Global convex op- timization of polynomial activation neural networks in fully polynomial-ting arXiv preprint arXiv:2101.02229, 2021.
Yoshua Bengio, Pascal Lamblin, Dan Popovici, and Hugo Larochelle. Greedy layer-wise training of deep networks. Advances in neural information processing systems, pp. 153-160, 2007.
Yang-Jie Cao, Li-Li Jia, Yong-Xin Xia Chen, Nan Lin, Cong Yang, Bo Zhang, Zhi Liu, Xue-X Que-Xiang Li, and Hong-Hua Dai. Recent advances of generative adversarial networks in computer vision. IEEE Access, 7:1 49855-5500006 2018.
Antonin Chambolle and Thomas Pock. A first-order primal- algorithm for convex problems with applications imaging. Journal of mathematical imaging and vision, 40(1):120-14) 2011.
Tolga Ergen and Mert Pilanci. Convex geometry of two-layer relu networks: Implicit autoencoding and interpretable models. Silvia Chiappa and Roberto Calandra (eds.), Proceedings of the Twenty Third International Conference Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 4024 4033. PMLR, 26-28 Aug 2020. URL htttps://proceddi: http:/ggssml....sssa..mmmm
ml pwe.s.press/eemm wtwreess/v10//eree///ie
.html
Tolga Ergen and Mert Pilanci. Convex geometry and duality of werrpaaramterrized neural networks.
Journal of Machine Learning Research, 22(212):1-63, 2021a. URL http://jmlr.org
papers/v22
htm]
Tolga Ergen and Mert Pilanci. Global optimality beyond two layers: Training deep relu networks via convex programs. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 Proceedings of Machine Learning Research, pp. 2993-3003. PMLR, 18-24 Jul 2021b. URL /tthtttpp.//prroeeiinng mor.s...rr.ppp hor.
ergen21a.htn html
Tolga Ergen and Mert Pilanci. Path regularization: A convexity and sparsity inducing regularization for parallel relu networks. CoRR, 10.0241, 2021c. URL https: awxiv. www.aii...og/...../ooooo 211 0. 09548
10

---

Published as a conference paper at ICLR 2022
Tolga Ergen and Mert Pilanci. of two-and three-layer networks in polynomial time. In International Conference on Learning Representations, 2021d.
Implicit convex regularizers of enn
Convex optimization
Tolga Ergen and Mert Pilanci. Revealing the structure of deep neural networks via convex duality. In Marina Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. -0104 PMLR, 18 24 Jul 2021e. URL
ing...in.s.mi.... r.r.ss.pp................. / htmml
Tolga Ergen, Arda Sahiner, Batu Ozturkler, John Pauly, Morteza Mardani, and Mert Pilanci. Demys- tifying batch normalization in relu networks: Equivalent convex optimization models and implicit regularization. arXiv preprint arXiv:2103.01 0199,, 2021.
Farzan Farnia and Asuman Ozdaglar. Do gans always have nash equilibria? In International Conference on Machine Learning, pp. 3029-3039. PMLR, 2020.
Farzan Farnia and David Tse. A convex duality framework for gans. arXiv preprint 18Xiv:1810.111 2018.
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding gans in the lag setting: Formulation, generalization and stability. IEEE Journal on Selected Areas in Information Theory, 1(1):304-31,, 2020.
Aude Genevay, Gabriel Peyré, and Marco Cuturi. Learning generative models with sinkhorn di- vergences. In International Conference on Artificial Intelligence and Statistics, pp. 1608-1617. PMLR, 2018.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. arXiv preprint 1406. 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. arXiv preprint arXiv: 1704.0000400 2017.
Changhee Han, Hideaki Hayashi, Leonardo Rundo, Ryosuke Araki, Wataru Shimoda, Shinichi Muramatsu, Yujiro Furukawa, Giancarlo Mauri, and Hideki Nakayama. Gan-based synthetic brain mr image generation. In 2018 IEEE 15th International Symposium on Biomedical Imaging (ISBI 2018), pp. 734-738. IEEE, 2018
Zhenliang He, Meina Kan, and Shiguang Shan. Eigengan: Layer-wise eigen-learning for gans. arXiv preprint arXiv:2 12476, 2021.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. arXiv preprint arXiv:1706.08500 085000 2017.
Phillip Isola, Yan Zhu, Tinghui Zhou, and Alexei A Efros. Image-to-image translation with conditional adversarial networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1125-1134, 2017.
Abdul Jabbar, Xi Li, and Bourahla Omar. A survey on generative adversarial networks: Variants, applications, and training. ACM Computing Surveys (CSUR), 54(8): 2021.
Tero Karras, Timo Aila. Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for improved quality, stability, and variation. arXiv preprint arXiv:1710.10190 2017.
Tero Karras, Samuli Laine, and Timo Aila. A style-based generator architecture for generative adversarial networks. Proceedings of the IÉEE/CVF Conference on Computer Vision and Pattern Recognition, pp.
2019.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
11

---

Published as a conference paper at ICLR 2022
Chun-Liang Li, Wei- Chang, Yu Cheng, Yiming Yang, and Barnabás Póczos. Mmd gan: Towards deeper understanding moment matching network. arXiv preprint arXiv: saee::105508888 2017.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedinggs of International Conference Computer Vision (ICCV), December 2015.
Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley. Least squares generative adversarial networks. In Proceedings of the IEEE international conference on computer vision, pp. 2794-2802, 2017.
Morteza Mardani, Enhao Gong, Joseph Y Cheng, Shreyas S Vasanawala, Greg Zaharchuk, Lei Xing, and John M Pauly. Deep generative adversarial neural networks for compressive sensing mri. IEEE transactions on medical imaging, 38(1):167-179, 2018.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International conference on machine learning, pp. 3481-3490, PMLR, 2018.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. arXiv preprint 1.10:1661.02213,, 2016.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint urXiv:1802.05955 2018.
Youssef Mroueh, Tom Sereu, and Vaibhava Goel. Mcgan: Mean and covariance feature matching gan. In International conference on machine learning, pp. 2527-2535. PMLR, 2017.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real inductive bias: On the role of implicit regularization in deep learning. arXiv preprint arXiv:
2014.
Sebastian Nowozin, Botond Cseke, and Ryota Tomioka. f-gan: Training generative neural samplers using variational divergence minimization. arXiv preprint wrXiv:6066.00799 2016.
Piyush C Ojha. Enumeration of linear threshold functions from the lattice of hyperplane intersections. IEEE Transactions on Neural Networks, 11(4):899-850, 2000.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. arXiv preprint arXiv:1912.01703. 2019.
Mert Pilanci and Tolga Ergen. Neural networks are convex regularizers: Exact polynomial-time convex optimization formulations for two-layer networks. In International Conference on Machine Learning, pp. 7695-7705. PMLR, 2020.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks, arXiv preprint arXiv:1511.0643: 2015.
Arda Sahiner, Tolga Ergen, John Pauly, and Mert Pilanci. Vector-output relu neural network problems copositive programs: Convex analysis of two layer networks and polynomial-tine algorithms. arXiv preprint 2rX 13322 2020a.
Arda Sahiner, Morteza Mardani, Batu Ozturkler, Mert Pilanci, and John Pauly. Convex regularization behind neural reconstruction. arXiv preprint arXiv:2012.05169 2020b.
Alexander Shapiro. Semi-infinite programming, duality, discretization and optimality conditions. Optimization, 1832)133-161,, 2009.
Dinggang Shen. Image registration by local histogram matching. Pattern Recognition, 40(4): 1161-1172, 2007.
Richard P Stanley et al. An introduction to hyperplane arrangements. Geometric combinatorics, 13: 389-496, 2004.
12

---

Published as a conference paper at ICLR 2022
Ioannis Tsaknakis, Mingyi Hong, and Shuzhong Zhang. Minimax problems with coupled lin- ear constraints: Computational complexity, duality and solution methods. arXiv preprint arXf::2110.11210, 2021.
Angelos Tsoukalas, Berç Rustem, and Efstratios N Pistikopoulos. A global optimization algorithm for generalized semi-infinite, continuous minimax with coupled constraints and bi-level problems. Journal of Global Optimization, 44(2)235-2250, 2009.
Xintao Wang, Ke Yu, Shixiang Wu, Jinjin Gu, Yihao Liu, Chao Dong, Yu Qiao, and Chen Change Loy. Esrgan: Enhanced super-resolution generative adversarial networks. In Proceedings of the Euro- pean Conference on Computer Vision (ECCV) Workshops, pp. 0-0, 2018.
Yifei Wang, Tolga Ergen, and Mert Pilanci. Parallel deep neural networks have zero duality gap. 06482
CoRR, abs/21 10.06482, 2021.
Guang Yang, Simiao Yu, Hao Dong. Greg Slabaugh, Pier Luigi Dragotti, Xujiong Ye, Fangde Liu, Simon Arridge, Jennifer Keegan, Yike Guo, et al. Dagan: Deep de-aliasing generative adversarial networks for fast compressed sensing mri reconstruction. IEEE transactions on medical imaging. 37(6):1310-132) 1321, 2017.
Stanislav Žaković and Bere Rustem. Semi-infinite programming and applications to minimax problems. Annals of Operations Research, 124(1):81-110, 2003.
Stanislav Zaković, Costas Pantelides, and Bere Rustem. An interior point algorithm for computing saddle points of constrained continuous minimax. Annals of Operations Research, 99(1):99-77, 2000.
13

---

Published as a conference paper at ICLR 2022
Appendix
Table of Contents
Notation Summary
15
B Experimental Details and Additional Numerical Examples
15
B
Rel.U-activation Discriminators)
15
B.2 Progressive Training of Lincar Generators and Quadratic Discriminators
17
Additional Theoretical Results
21
Convexity and Polynomial Time Trainability of Two-Layer ReLU Generators
21
Norm Constrantd Discriminator Duality
23
Generator Parameterization for
Discriminators
25
D Overview of Main Results
26
D.I
Derivation of the Form in equation
26
D.2 Proof of 12corem12.1
27
Note on Convex-Concan Games with Coupled Constraints
29
D.4
Proof Theorem 2.2
E
Two-Layer Discriminator Duality
31
E.1
Proof of Lemma 3.]
31
E.2
Proof of Corollary
31
E.3
Proof Corollary
31
E.4
Proof of Corollary
3.3
32
Proof Corollary
32
F
Generator Parameterization and Convexity
32
F1
Proof of Theorem 4.1
32
F2 Proof of Theorem
34
14

---

Published as a conference paper at ICLR 2022
A
NOTATION SUMMARY
Here, we provide a table summarizing the notation used this paper for clarity.
Table 2: Notation used throughout the paper.
Symbol
Meaning
6g
Generator parameters
a Go
Discriminator parameters
Generator function
Daa
Discriminator function Ground truth data
X
Z
Noise inputs to generator Generator regularization function Discriminator regularization function Generator regularization parameter Discriminator regularization parameter
Rg
Ra
Bg
Ba
nr
Number of samples from X Dimension of samples from X
dr
nf
Number of samples from Z
dz
Dimension of samples from Z
He
Hyperplane arrangements of X
Hz
Hyperplane arrangements of
rank(X)
Ts
rank
mg
Generator hidden layer neurons
ma
Discriminator hidden layer neurons
First-layer weight of discriminator neuron j Second- layer weight of discriminator neuron j
Wi
First-layer generator weight matrix Second-layer generator weight matrix
W
B EXPERIMENTAL DETAILS AND ADDITIONAL NUMERICAL EXAMPLES
B. RELU-ACTIVATION DISCRIMINATORS
We first provide some non-convex experimental results support our claims in Theorem 2.2 For this case, we use WGAN with two-layer ReLU network generator and discriminator with the parameters (mg. My, Pa. (1) = (150, 150, 10 3 4e - 6). We then train this architccture on the same dataset in Figure 1 As illustrated in Figure 4 depending
the initialization seed, the training performance for the non-convex architecture might significantly change. However, whenever the non-convex approach achieves stable training performance its results match with our theoretical predictions in Theorem
In order to illustrate how the constraints in Theorem 2.2 change depending the number of data samples, below, we analyze case with three data samples.
Let consider toy dataset with the data samples [-1, 1, 1]T. Then, the convex program be written as
min RS (w) s.t. W
Σ S
2z)
< 3a.
Σ
(ã,
5z)
$ Ba. Vj [6].
(18)
1=1
Substituting the data samples, the simplified convex problem admits
[u1 + w2 + wal < Ba,
min RS (w (w) s.t.
|1 (w22 + w3)l < 3a, |m] + w2 + 1 S Ba,
(19)
WER3
Jw's v 3a, w + 1 Ba
15

---

Published as a conference paper at ICLR 2022
2.0
Real
0.04
Generator output
Objective Value
10
0.02
0.5
0.0
0.00
X X
00.5
-0.02
-1.0
-1.5
Discriminator
-0.04
-2.0
Generator
5000
10000
15000 20000 25000
-2.5
-2.0
-1.5
-1.0
-0.5 0.0
1.0
Epoch
(a)
Trial#1 ID illustration
(b) Trial#1 Loss curves
0.5
0.04
Generator output
Real data
Objective Value
0.0
0.02
-0.5
0.00
x
*
-1.0
-0.02
-1.5
Discriminetor Generator
-0.04
-2.0
10000 15000 25000
-1.0
-0.5
0.0
0.5
1.0
Epoch
(c) T ID illustration
(d) Trial#2 Loss curves
Figure 4: Non-convex architecture trained on the dataset in Figure | using the Adam optimizer with (My. ma; fa, p)) (150, 150, 10-3, 4e 6). Unlike our stable convex approach, the non-convex training is unstable and leads to undamped oscillations depending on the initialization. In particular, for Trial#1 ((a) and (b)), we obtain unstable training so that the generator is unable to capture trend in the real data. However, in Trial#2 ((c) and (d)), the non-convex architecture is able match the real data as predicted our theory Theorem
which exhibits similar trends (compared to the case with two samples in Figure I as illustrated in Figure
Proof.
To derive the convex form, we begin with equation
18 and simplify to:
j 1
(w] + 1) + (w2 + 1) + (Wy
1) s 8a
S 3d
j = 2
-
(w2 w1) + (1 w1) (w's wr)l < 8a
[w] + 1 < Ba
j = 3
W2 + wzl S 38
|1 + wi S Aa
j = 4
[(1 (1)))) - (Wa w2)l )l < 3a
W22 (W2 wi + (w2 + 1)] S Ba
j = 5
WW3- 1 S 3a
2 (1 w1) + (1 w2) S 3a
j = 6
0 < 3a
(wss + 1) (W3 wi) + W3
(w3 - w2) + (wz 1)1 S Ba-
Simplifying the constraints above yield
j = [1 + W2 + w/l < 3a
0 < 8d
j = 1 (w2 + wz)l < 8g
[w) + 1| $ Ba
j 3
] (w2 + wa)l < 3a
[wn + 1| S Ba
j = [wg 1| S Ba
[w + w2 1| S 3a
j = 5 W33 1 < Ba
[w + w2 + 1 S 8a
j= 3a
[w w2 + W3 $ Ba-
which can further be simplified the expression in equation 19
16

---

Published as a conference paper at ICLR 2022
0.4
+ real
x fake
0.2
1.2
+*
1-
-0.2
0.8
-1.2
0.2
0.4
-1
-1.5
-0.5
0.5
M/
-0.8
8a
0.1
(b) Generator space
0.5
-1
0
0.5
-1.5
-1
-0.5
0.5
1.5
M/1
M/2
(c) 9a =
(d) Generator space
Figure 5: Numerical illustration of Theorem 2.2 for ReLU generatoorddiseriminaaoor with ID data
[-1,0, 11" and Rg (w) ||
B.2 PROGRESSIVE TRAINING OF LINEAR GENERATORS AND QUADRATIC DISCRIMINATORS
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 x 64 as the high-resolution baseline X; 5-0000x 12288 All images are represented in the range [0, 1). 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 E T 50000x are sampled from i.i.d. standard Gaussian distribution.
For the Progressive GDA baseline, we train the networks using Adam (Kingma & Ba
2014)
with = le 3, B, 0, B2 0.99 and
10-8 as is done in (Karras al. 2017
Also following (Karras et al. 2017). we use WGAN-GP loss with parameter A = and an additional penalty Ex (xx) where edint 10 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 the ProCoGAN formulation, penalize the outputs the generator with penalty G/ for some regularization parameter
3g. For the results in the main paper, we let .663) 100/d where d!a) 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 ProCo- GAN. We plot the loss curves of the final stage of the baseline in Figure 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
particular architecture from generating state-of state-of-the th-the-art images (Karras et al. 2017). Many key aspects (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),
par with
17

---

Published as a conference paper at ICLR 2022
Discriminator fake loss
Discriminator output penalty
Discriminator loss
800
2500
20
2000
600
15
1500
400
1000
200
5000
10000
15000
5000
10000
15000
5000
10000
15000
Number
iterations
Discriminator real loss
Discriminator gradient penalty
Generator loss
My Myt
100
2000
-100
1500
-100
-300
Mwmh
-400
500
-500
-500
5000
10000
15000
5000
10000
15000
5000
10000
15000
Number of iterations
Number iterations
Number iterations
Figure 6: Loss curves of the final 64 x 64 stage of training of the non-convex generator and non- concave discriminator as trained with the bascline Progressive GDA method as used the main paper, for images shown in Figure Discriminator fake loss corresponds to the total network output over the fake images, while real loss corresponds to the negative of the total network output over the real images, output penalty corresponds to the Exnpp [D ) penalty, gradient penalty refers to the GP loss with = 10, discriminator loss is the sum over all the discriminator losses, and generator loss corresponds to the negative of the discriminator fake loss.
18

---

Published as a conference paper at ICLR 2022
Table FID results of progressive training of linear generators and two-layer quadratic-activation discriminators using both the convex approach and the non-convex baseline. Results are reported over three runs.
Method
FID
Progressive GDA (Baseline)
194.1 + 4.5
ProCoGAN (Ours): (8) (44) (7.2x10², 1.0x10*)
128.4 + 0.4
ProCoGAN (Ours): (8)4) g(0)) (1.9x10*, 3.3x10*)
147.1 + 2.4
d
(a) ProCoGAN (Ours)
(b) Progressive GDA (Baseline)
Figure 7: Representative generated faces at 4 x resolution from ProCoGAN and Progressive GDA with stagewise training of linear generators and quadratic-activation discriminators on CelebA (Figure
progressively growing the diseriminator as well as the generator, using convolutional layers rather than fully-connected layers, using leaky-RelUU activation rather than linear or 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. (017)) exactly with a convex algorithm, but rather to simply demonstrate proof-of-concept for the effectiveness of our equivalent convex program and non-convex original optimization problem, when both approaches are applied to the same architecture of linear generator and quadratic-activation two-layer discriminator.
alternative to standard GDA applied the non-concave
For ProCoGAN, for both of the sets of faces visualized the main paper, we arbitrarily choose (8 Ad
(206, 1.6 x 109,5.9 5.9 values of X, = U,E,V,, where k; can be varied.
g(2) ,
10²). (3(0) are in general chosen truncate k; singular
Both methods are trained with Pytorch (Paske et al. 2019), where ProCoGAN trained with single 12 GB NVIDIA Titan Xp GPU, while progressive GDA is trained with of them. For numerical results, we use Fréchet Inception Distance (FID) as a metric (Heusel et al.) (017). generated from 1000 generated images from each model compared 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 Ba seem 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 the settings described in the main paper, we show representative outputs of each trained generator at each stage of training in Figures
and 10
Further, we ablate the values of ((() for ProCoGAN to show in an even more extreme case the tradeoff
between smoothness and diversity, and ablate a(i) in the case of ProgressiveGDA, which provides a similar tradeoff, show in Figure 11
19

---

Published as a conference paper at ICLR 2022
(a) ProCoGAN (Ours)
(b) Progressive GDA (Baseline)
Figure 8: Representative generated faces 8 resolution from ProCoGAN and Progressive GDA with stagewise training of linear generators and quadratic-activation discriminators on CelebA (Figure
(a) ProCoGAN (Ours)
(b) Progressive GDA (Baseline)
Figure 9: Representative generated faces 16 resolution from ProCoGAN and Progressive GDA with stagewise training of linear generators and quadratic- activatioon discriminators on CelebA (Figure 2
(a) ProCoGAN (Ours). Top: ( = 7.2x 1
Bottom: g = 1.9x 10
(b) Progressive GDA (Baseline)
Figure 10: Representative generated faces at 32 x 32 resolution from ProCoGAN and Progressive GDA with stagewise training of only employs the closed-form expression equation 15 where Ba controls the variation and smoothness in the generated images.
linear generators and quadratic-activation discriminators on CclcbA (Figure[). ProCoGAN
20

---

Published as a conference paper at ICLR 2022
(a) ProCoGAN (Ours). Top: 3 (1.3
10 2.7 10 9.0
10 2.6 10 6.4 x 10*)
Bottom: a = (51, 557,
2.9
10", 5.3
10 6.2 10
(b) Progressive GDA (Baseline). Top: 3/ 10/ (
Bottom: 260 - 1000/ (0)
Figure 11: Effect of ( on generated faces from ProCoGAN and effect of 3/ generated faces from Progressive GDA with stagewise training of linear generators and quadratic-activation discriminators CelebA (Figure ProCoGAN only employs the closed-form expression equation 15] where 3a controls variation and smoothness in the generated images, which can clearly be seen in the extreme example here. We also see that 9, has similar effect for Progressive GDA, where high values of B, make output images less noisy but also less diverse.
C ADDITIONAL THEORETICAL RESULTS
C.I CONVEXITY AND POLYNOMIAL-TIME TRAINABILITY OF TWO-LAYER RELU GENERATORS
In this section, we re-iterate the results of (Sahiner et al. 2020a) for demonstrating equivalent
convex formulation to the generator problem equation 5
W I W arg min ||W l ||W, 12 s.t. G* (ZW1)+ W2.
W,W,
In the case of ReL U-activaatio generators, this form appears in many of our results and proofs. Thus, establish the following Lemma.
Lemma C.1. The non-convex problem equation is equivalent to the following convex optimization problem
HH
H2 ZV;
[V:) [Htl
1 arg min
Vallk,. s.t. G
Σ
H
for |V := minggo V, E tconv hg" (2H " 0, ZZ/, 1}, provided that the number of neurons my 2 nydy + 1. Further, this problem has complexity O(n" (2/) ) where = rank(Z).
Proof. We begin by re-writing equation in terms of individual neurons:
my
min
22 + |V, 2 s.t.G" Σ (Zu,)
(20)
Then, we can restate the problem equivalently as (see D.I::
m
min |
Σ
Ivyll2s..tG.
Σ [Zu
(21)
21

---

Published as a conference paper at ICLR 2022
Then, take the dual of this problem as in (Ergen & Pilanci First, form the Lagrangian
2021a
2020
Sahiner et al.
2020a
mg Σ ==1
min M las
max tr
tr(R
(Zu,)+vz))
(22)
Then, by Sion's 's minimax theorem, we can exchange the minimum over v and maximum over R, to obtain
mg
min I 11
max min Vi
1lvslla+ tr ( G*) G
E
tr(R (Zu,)+v]).
(23)
Minimizing this over v, we obtain the equivalent problem
min maxtr(R T G s.t. R (Zu,)+lla $ 1 Vj E [mg].
(24)
I| I1 R
Under the condition my nyd, we obtain the equivalent semi-infinite strong dual problem
max tR T G*) s.t. at..||R (Zu)+ +112 s v/|ul22 s 1.
(25)
This over over-parame parameterization requirement arises from the argument that this semi-infinite dual constraint can be supported by most m < n ,d, + neurons u, and thus my 2 m. strong duality holds
(see Lemma 5 of (Sahiner et al. 2020a), Section 3 of (Shapiro 2009)). This problem can further be re- re-written as
max tr R G*) s.t. s.t. R
max || (Zu)+Ila S 1. Julas1
(26)
Using the concept of dual norm, we introduce the variable w to obtain the equivalent problem
max tr(R G*) s.t. max R (Zu)- S | j was
(27)
Then, enumerate over all potential sign patterns obtain
max tr(R G*) s.l.
max
R H O Zu 1,
(28)
R
W
(2
Zuzo
which we can equivalently write as
max tr R G s.t.
max
(R. HR Zuw 11
(29)
|ul|$51
|| 1
H
(2H J.. Zuz0
which can further be simplified
max Ir(R G*) s.t. max
(R, H. < SIVE [H.]]-
(30)
R
IVV
We note that unlike the of rank-one matrices satisfying the affine constraint when parameterized by uw the matrices V, E K, are not necessarily rank-one, and can in fact be full-rank. In particular, K, 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 tr R G*) +
Σ
A(1
max Vilk..
RR. ZV.
(31)
R X
$1
equivalently
H.1 G*) R
max min min
tr(R
R
(32)
R X
JIV,IIK,..1
i=l
22

---

Published as a conference paper at ICLR 2022
By Sion's minimax theorem, can change the order of the maximum and minimum. Then, maximizing over leads to
H.l G G²
H.l
min X
min &
Σ
S.t.
E
Σ
(33)
1=1
1=1
Lastly, note that this is equivalent to
H.. IV s.1. G
H. Σ
arg min V;
H zv.
(34)
desired. The computational complexity of this problem is given (2))))))))) where Ty == rZ) (see Table of (Sahiner et al. 2020a)). ). The general intuition behind this complexity be solved with Frank- Wolfe algorithm, each step of which requires
that this problem the solution to H22l & O(ry(n'/ /dy) subproblems, each of which has complexity O(n"r).
To obtain the weights to the original problem equation 5 factor V; - hi where 1, and then form
(2H! ( In Zhiz and ||B ||2
h
(Wisg) W2er)
Biy
E [[H]]], j E [d,]
as the ijth row of Wi and ijth column of W respectively, Re-substituting these into equation 5
obtains a feasible point with the same objective as the equivalent convex program equation 6
C.2 NORM-CONSTRAINE DISCRIMINATOR DUALITY
In this section, 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 I-Lipschitz constraint, we can use the constraint {E, l0yl I 1, ||y I 1}. Then, for linear-activation discriminator, for any data samples a, b, have
m
m
m
Σ a
E
bJu
b uj
= Σ
a aJa,, u u 0j
a T uj b bu, uj
< max
I| ||
la blla.
Thus, 10y1 1, 11111 1} implies 1-Lipschitz for linear-activation discriminators. For discriminators with other activation functions, the same set of constraints well.
Lemma C.2. A WGAN problem with norm-constrained two-layer discriminator, of the form
p' = min
max Σ, N S1,
( + Rg
1
with arbitrary non-linearity a, can be expressed as the following:
p" min max 0 [1|la1
[X(() 1 (Go, (Zui) + (,g(0g)
Proof. We first note that by the definition of the dual norm, we have
Σ 9.
max cTv =||c||.o max lcy1- jE[m]
max M, R
livis1
Using this observation, we can simply maximize with respect to vy to obtain
1 [o((Xu,) 1 (Go, (Z)u,) + *2
p' = min
max l
23

---

Published as a conference paper at ICLR 2022
which we can then re-write
p'
min max 0 |
1 (Xu) - 1 (Go, (Z)u) + R,,)
as desired.
Corollary C.1. A WGAN problem with norm-constrained two-layer discriminator with linear activa- tions (t) t can be expressed as the following:
pz
min 0g
111' (Z)ll2 (0g))
x
Proof. Start with the following
min max by 1
1 Xu Go, (Z)u + (g)0g).
Solving over the maximization with respect to u obtains the desired result:
min 0g
| X ToG, (Z)ll2 (0g)
Corollary C.2. A WGAN problem with norm-constraineet two-layer discriminator with quadratic
activations (t) = can be expressed as the following:
min
X X -aa T Go, + (9g))))
Proof. Start with the following
min max
- (2),)) + +R,(00))
which we can re-write as
min max O |1
u x Go, (Z) Go, (Z) u + (00)
Solving the maximization over u obtains the desired result
p min
X X
Go, (Z) Go, (Z)ll2 + (0g))))
8
Corollary C.3. A WCAN problem with norm-ccostrrained two-layer discriminator with ReLU activa- tions (t) = (1)+ can be expressed as the following:
HH HH 1o (Z)u (g))
min 0,
fi E
[
||u 1
(2H I,.. Xu20
(2H (o) I,n Gog (Z)u20
Proof. We start with
D = min max 2
(T(x))+ - (Z)u++ + R. (0,).
Now, introducing sign patterns of the real data and generated data, have
pd min 8,
max E |
1 (T 2
Xu (2())) Go, (Z)u + R.
Jo |H,
(2H(1) I.., Xu20
(2H
In, Go, (Z)
desired.
24

---

Published as a conference paper at ICLR 2022
C.3
GENERATOR PARAMETERIZATION FOR NORM- FORM-CONSTRAINED DISCRIMINATORS
Throughout this section, we utilize the norm constrained discriminators detailed in Section C.2
C.3.1 LINEAR GENERATOR (o
Linear-activation discriminator. For a linear generator and lincar-activation norm-constrained discriminator (see Corollary C.I for details), have
p min max
(1 X ZW) u+ R,R,
|ul2211
min 1 A ZZW 12 + R2 (W).
W
For arbitrary choice of convex regularizer R, (W), this problem is convex.
Quadratic-activation discriminator (a(t) = t²). For a linear generator and quadratic-activation norm-constrained discriminator (see Corollary C.2 for details), we have
p' min
| (ZW) T Zw 2 + (W,). W
(35)
If (Zank()) rank(X), with appropriate choice of R.g (W BBy|ZW]] f., we write this as
p' = min min X G 2 + 3, |
(36)
which is convex. With a symmetric solution GO the above,
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) (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 S rank(X), as long as rank Z) Z rank(X), we will be able to exactly find original weights W from G*, and the two problems are equivalent.
ReL.Uactivatiin discriminator (o(()= (1) ()....oor For a linear generator and Rel.U-activation norm- constrained discriminator (see Corollary for details), we have
p- min W
max EH
H 1 Xu 1 H ZWu R.y (W)
fu I 111
H.
22H (1)) I,,,
Xu20
(2H
-I.,
2Wu20
For arbitrary choice of convex regularizer Ry (W), this is convex-concave problem with coupled constraints, as in the weight-decay penalized case.
C.3.2 POLYNOMIAL-ACTIVATO GENERATOR
All of the results of the linear generator section hold, with lifted features (see proof of Theorem 4.2)
C.3.3 RELU-ACTIVATION GENERATOR
Linear-activation discriminator (a(t) t). With standard weight decay, we have
min - ----11 1---- (ZW,), Wall2 3g (|W] 11 + || W1. W
We can write this as a convex program follows. For the output of the network (ZW) 1)+ W2, the fitting term a convex loss function. From (Sahiner et al. 2020a), we know that this is equivalent to the following convex optimization problem
H.l Σ
p² =
min V
X
(1)
ZV.
+ Bg Σ
| Viilk
25

---

Published as a conference paper at ICLR 2022
where K == cog (2H In,) 0, ||g]|2 }} and |V mingo stt. V I/.
Quadratic-activation discriminator (o(1) (.). We have
p
min W
|X X Wa) (ZW1)+ W2ll2 + R2 (2).
For appropriate choice of regularizer R (W,, W we can write this as
2. [ZW 1)+ W2ll: and my 2 nfd,
X G TGG GGll2 + Bg |
G arg min
X
W,
2
W W arg min
|
W2
| s.t. G* (ZW W2.
W.W.
The latter of which wr-te in convex form as shown in Lemma C.I
122 Σ H ZV:
[V |M arg min V.
Σ
IV Ill, s.t. G²
for convex sets K;; conv(ug (2H I., /uu 1g < 13. and |
min & s.t. V, E ICc, Thus, the quadratic-activatio discriminator, ReL.U-activation generator
problem in the case of conntroontraieed discriminator can be written as two convex optimization problems, with polynomial time trainability for Z of a fixed rank.
ReLU-activation discriminator (o(t) (t) In this case, we have
arg min W.
max H
1 ( Xu Xu
( W2u R2 (W1, W2).
Jw H
2
Xu20
(2H I. (ZW,). +)+
Wan20
8
Then, for appropriate choice of R,(W1, W2) - (IW,)) W2ll3. assuming my 2 nyd, 1. this is equivalent to
1 H Xu 1 H Gu 8 |G
G arg min
G
H
|
(2H
I,, Xu20
(2 (/a) T.. Gu20
Wi. W = arg min || | 2 + W s.l. G* (ZW1)+ W2.
W,
The latter of which re-write in convex form as shown in Lemma C.I
Ia arg min V.
Σ
IVlk,, s.t. G = Σ H H zv:
for convex sets K,₃ conv {ug' min t s.t. V. E tK₁,. Thus, the lem the case of norm-conee nonm-constrained discriminator can be written as convex-concave game in sequence with convex optimization problem.
(2H
L, Zu l1lll 1) and norm ||l,l,..
discriminator, ReLU-activation generator prob-
D OVERVIEW OF MAIN RESULTS
D.1 DERIVATION OF THE FORM IN EQUATION
Let us consider positively homogeneous activation function of degree one, i.e., (Ix) to (x), E R,, Note that commonly used activation functions such as linear and ReLU sat- isfy this assumption. Then, weight decay regularized training problem can be written as
m
p" min max
(1 (X(,) 1 (Z))))))) os + (0,) 3a Σ
11 + 0z)
0g 0g
26

---

Published as a conference paper at ICLR 2022
Then, first note scaling the discriminator parameters u, ay and ög Uy/ag does not change the output of the networks as shown below
m
m
Σ
o (Xu,) ,0
Σ o (Xa,u,) 1/ Oj 5=1
-
=- [o(Xu))y
j=1
Σ (Ge, (Z)ū)J =
1 Σ (Ge, (Z)a, j=1
Co(Go, (Z),))))
jjj
Moreover, we have the following AM-GM inequality for the weight decay regularization
m
m ((l,lll)))))
+
1/2 Since the scaling operation does not change the right-hand side of the inequality, we can set ||u/||2 1, Vj.
where the equality is achieved when the scaling factor is chosen as a, |
Thus, the right-hand side becomes ||v||ı Σド= |dyl-
We also note that this result was previously derived for linear (Ergen & Pilanci 2021e) and ReLU (Pilanci & Ergen 2020, Ergen & Pilanci| 2021d). Similarly, the extensions to polynomial and quadratic activations were presented in (Bartan & Pilanci 2021).
D.2 PROOF OF THEOREM 2.1
Linear-activation discriminator (o = f). The regularized training problem for two-layer ReLU networks for the generator can be formulated as follows
p min (W W2) s.t. max |u
1 (Xu( -1---- ( (To((Z W2)u)1 5 Pa
W.
[t)=
min R2 (W1, W2) 1 1 ([WW)) (2)l) - Sa.
W.
Assume that the network is sufficiently over- parameterized (which will precisely define below). Then, we can write the problem
min
G s.t. || - - G - Ba.
where the solution G is given by convex program. Then, to find the optimal generator weights, one can solve
min W.
|ill + W s.t. G (W1)+W
(37)
which can be solved as convex optimization problem in polynomial time for Z of fixed rank, as shown in Lemma C.I given by
H.l
(V))
|N
arg min V.
VVlkk s.t. G
Σ
ZV,
1=1
for convex sets K2 conv (ug
1} and norm |VVllk,, min s.t. V, E tK,, provided that the generator has m, nyd, + 1 neu-
(2H
I. Zu
0, 1gll
rons, and we can further find the original optimal generator weights Wi, W from this problem.
Quadratic-activan discriminator (o(1) = t2). Based on the derivations in Section with the problem
E,3 we start
min Wi.Wo (W,, W2) s.t. X X (ZW))) W2) (ZW1)+ Wa)l S 8d.
Assume that the network sufficiently werrparameteriized (which we will precisely define below). Then, write the problem
n" min
| s.t. x < Ba,
27

---

Published as a conference paper at ICLR 2022
1/2 V2VT for any orthogonal matrix L. Then, to where the solution G* is given by G L( 3 find the optimal generator weights, one can solve
min W2
|Wil + W2ll s.t. G (2W1)+Wz
(38)
which can be solved as convex optimization problem in polynomial time for of fixed rank, as shown in Lemma C.I given by
(Vi) arg min V.
Σ
| s.t. G
Σ
ZV. ZV,
H
for convex sets K2 == conv
(2H I, Lu Zu
0, lgll2 I 1} and norm
||Vilk,, == min / s.t. V; E (K;, provided that the generator has my 2 nyd, + 1 neu- rons, and further find the original optimal generator weights Wi, W from this problem.
ReLU-activation discriminator (o(() (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
R 11, W2)
W,
H
(1) X 1 (ZW,)
(ZW1), W2)u s Ba
8.1.
max
||
d1 [
E 14g
( Tee Xu20
(2H -I., (2W1)) Wau20
Assume that the generator network is sufficiently werr-parameterized, with mg 2 njd, + neurons. Then, can write the problem
G arg min |G
( ( H S Ba
8.6.
max
|
J.E
PH
(2H(17- TT, Xu20
(2H(22) Lay Guz0
and
min W.
| 11 + [ s.t. G (ZW,). 1)+ W₂
the latter of which can be solved convex optimization problem in polynomial time for Z of fixed rank, as shown in Lemma C.I given by
Hal
H.
{V: [ [Mal arg min V.
IV s.t. G =
Σ H
ZV.
1=1
for convex sets K²: = conv conv(ug [|Vill... min s.t. V; E tK;, provided that the generator has mg nyd, 1 neu- rons, and we can further find the original optimal the generator weights W W; from this problem.
(2H I, Zu 0, Igll2
1} and norm
The former problem is a convex-concave problem. We begin with by forming the Lagrangian of the constraints:
p" min
2
G
(1TH)) x H + +aJ (2H - In..) x + to (2H In, I,,)
s.t.
min on
s Ba
20
VjJ ejHe [) H.
H x HH( + +a' T (2H(6)) In.) x + 1//2 (2H In. G// s Ba
min a',
20220
E)l H,
28

---

Published as a conference paper at ICLR 2022
Then, forming the Lagrangian, we have
p= = min G
max X,X
||G|
221 20, 3 20,
75g 20, E f211|H,1|
W/
Σ Ainia Ba - [| (H)))) X x-11 15-117 (H(LGG + +a (2H - -I..) x + T/z (2HÍ - In,) G (2)2)
(Ba-
j152
- - Vinda Ba - -11- H (i)) X - 1H + + T (2H6T)) In.) x 2//2 (NH( Ing G|(
jij2
We can then re-write this as
p-
min
max 11 I1 |G|
X,X'20 05 20, 2 20, Yog 20,71, 20,
Σ Asiaa
Ba -
( 11- - -aji (2H()) - -In.) x + +2 T (2H - -In,) ) G ())
J:52
Mnn Ba (a-(((11 1---- + +o'/ T (2H(/)) -I..) x + 1/2 (2H(ia) - In,) G G)rrn
5:52
maximizing over at a', 1. y', we have
p" minn
max
|GI - 3a E(sh + N11us) + Σ H X - 1 H
(1) G) (Abi2 - Niris
115
1251, 2,2
22 11
5122
3132
s.t. (2H ( Xr 2 0, (2H (1)) I,), 2 0, (2H( (1) Xr
jud 2 0, (2H Gr hu 20
We can then re- parameterizze this problem by letting 1j1d2 Ai and obtain the final form:
r'i132 X333 r 331 to
p" min max
|G
3a
> 21 + 111) + Σ (1 x 1 H 1 G
(I T((i))
Jija
J1ja
s.t. (2H()) - Xr 0, (2H I,, 2 0, (2H - I,, Xr Xr Sui 2 20, (2H(a)
I, Gr Jiia
which is a convex-concave game with coupled constraints, as desired.
D.3 NOTE ON CONVEX-CONCANE GAMES WITH COUPLED CONSTRAINTS
We consider the following convex-concave game with coupled constraints:
p² min max
|G Ba { (1risalll (12))2112) Σ
1 HOO 1 1 G) (Finia 1/122)
G 312
f:f2
J152
t. s. (2H(A) - Xr 2 0, (2H (b) I,,) 3.12 2 0, (2H Xr juda 20, (2H(())) - Gr -
3:50 2 0
Here, we say the problem has "coupled constraints" because some of the constraints jointly depend on G and Fj. T The existence of saddle points for this problem, since the constraint set is not
jointly convex in all problem variables, not known Zaković Rustem 2003
However, if all the constraints are strictly feasible, then by Slater's condition, we know the Lagrangian of the inner maximum has saddle point. Therefore, in the case of strict feasibility, we can write the problem as
p= = min max
min F Ansa X
GGI
Ba
> J132
1(1rs,ia (1 + Σ 1 [
1 1 H (rija - -1/0))
20
J152
Σ J1ja
12H (p) I G.)G Snja +
X/uia
((2H()) I,, Gr /
f122
(.H(())())) - I, Xr S1 0, (2H
(11)
Xr
2 0
29

---

Published as a conference paper at ICLR 2022
which by Slater's condition is further identical to
p=
min
min
max
||G|
pp
Ba
Σ
122 + 11 (hsalla) +
Σ
(1
(TH x 1 H
G)
(Tiis - T'1122
Ania 2112 20
G 1152
j1j2
21.2
+
Juda (2H (1) I.) Gr +
juj2
(2H In, Gn)
J132
$1.2
s.t. - J 2 O, (2H I,
Xr
Xr jıjı 2 0
For a fixed outer values of Aju X/1ja the inner min-max problem no longer has coupled constraints, and has convex-concave objective with convex constraints the inner maximization problem. solution for the inner min-max problem can provably be found with a primal-dual algorithm (Chambolle & Pock 2011), and we can tune Ajyúgo N/ hyper-parameters minimize the solution of the prima dual algorithm, to find the global objective p"
D.4 PROOF OF THEBREE 2.2
Let us first write the training problem explicitly as
mdd
E (xu; + bb))_ - (Ga, (z)u, + b))+ V/ + Ba 0g ECg PREER
min
max
1TT
Σ
(u} + +2) + (00(0)))
j=1
After scaling, the problem above can be equivalently written as
min Rg((g) s.t.
max S1i
T (xu + b)+ 1" (Go,(z)u b)+ Ba.
By the overparameterization assumption, we have (Go, (z) +b (wu + 4) Hence, the problem reduces to
min R2 (w) s.t. max [1" (xu + b)4 - 1s (wu + +))1 S Ba. S
(39)
wER"
Now, let us focus on the dual constraint and particularly consider the following case
(x: + b) > 0, Vi S1; (an + b) s VI Si
max
(x+ + b)
Σ JES
(my
b) S Ba, s.t. (w, bb) z 0, Vj E S2, (wk + b) S 0, Ak S
iES
(40)
where we assume u and S₁ and S2 are a particular set of indices the data samples with active ReLUs for the data and noise samples, respectively. Also note that Si and Sž are the corresponding complementary sets, i.c., Sf = [n]](S] and Sj = [n]],S,. Thus, the problem reduces to finding the optimal bias value b. We first note that the constraint can be compactly written
min min LESE
- 21, min - wkk KESS
b max
max Ij. max 1-Xx-U1 -wy iES:
JES,
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 S and S2, the bias parameter will be either -2 wy for a certain index Since the similar analysis also holds for - and the other set of indices, a set of optimal solution in general can be defined as
("" = (+1, +.I/WK).
Now, due to the assumption 8g & m(nn,) lar; l. we can assume that Φ1 S w S D2 S S Iy S 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 Rg (w) wER"
Σ
8: sa
3z))
< Ba,
Σ s(( 52) S
Ba, Vj
[2n]
(41)
30

---

Published as a conference paper at ICLR 2022
where
if is odd
[1,, if i is odd
vi [2n].
if á is even
1-1, if even
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, equivalent convex formulations for two-layer ReLU networks introduced (Pilanci Ergen, (200). In particular, to obtain the network parameters, solve the following convex optimization problem
directly the
HH
H.l
(uu) v
arg min U.,,EC,
Σ
|uulla + l|vel12 s.t. w
Σ
H
Z(u - vi).
where C₁ = {u Rdy (2H Lu 0} and we assume that my 2 n + 1.
E TWO-LAYER DISCRIMINATOR DUALITY
E. PROOF LEMMA 3.
We start with the expression from equation 3
min Og Uy 22
Σ
1
(0,) -B
byyl
We now solve the inner maximization problem with respect to v. which is equivalent to the mini- mization of an affine objective with & penalty:
p min (0,) s.t. max [Xuo(Xu) - T oGG,, (Z)u) s Ba.
0g
|Jl||aš1
E.2 PROOF COROLLARY 3.1
We simply plug in (t) t into the expression of equation 8
(1 x1 (Z) ul s Ba.
p' min Rg (fg) s.t. max ulla$1
"
Then, solve the maximization problem in the constraint, to obtain
p' min (8g) s.t. | Go, (Z)ll2 - 3a
6,
as desired.
E.3 PROOF OF COROLLARY
We note that for rows of X given by {
((u)²= = x 2) Σ
u x u= = u T Xu
Then, substituting into equation g we have:
p min Rg (0g) s.t. max |u |
X x Go Go, (Z))ui ul
Ba-
Then, solving the inner maximization problem over u, we obtain
p = min R, s.t. X Go, (Z) Go, (Z) $ 3a
desired.
31

---

Published as a conference paper at ICLR 2022
E.4 PROOF OF COROLLARY 3.3
When there is a linear skip connection, we can write the problem as
D- min
MIXX 8g By W. 1
Σ
(Xu:) (Ga, (2),)) 1it (1'-11 w w -0,)-Ba
l0yl
where (t) t.. Solving over w yields the constraint that 1 1 Go, (Z). Then, following
through the minimization over U as in Lemma and substitution of the non non-linearity in 3.3 obtain the desired result.
E.5 PROOF OF COROLLARY 3.4
We start with the problem equation g and substitute the ReLU non-linearity
p min (000 s.t. max Jillss
| ('(x))++ 1 (G,,, (Z)u)+| 8a
0g
Then, we can introduce hyper-plane arrangements as described in Section 1.2 over both X and Go,(( (Z) to obtain the desired result.
p" min (0g(g) 0g
(1TH 1 T Go,
(2)) S 3a
8.1.
max
||u 21
E
E Hl
(2H1(1)
Xu20
(2H
_I,, Go,,, (Z)u20
F GENERATOR PARAMETERIZATION AND CONVEXITY
F.1 PROOF OF THEOREM
We will analyze individual cases of various discriminators in the case of linear generator.
Linear-activation discriminator (o(t) = t). We start from the dual problem (see Section E.2 for details):
p min Rg W) s.t. max 1 TJ (Xu( - 1 (ZWu) S Ba |1||551
W
min RS () s.t. max (1 X 1 ZW)u - Pa ||]|
W
min R (W) s.t. 1 X
ZW) ||2 - Sa-
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 Ba > 0, as long as 1 Z O. can choose W such that 1 = 1 ZW, and a saddle point exists. The Lagrangian given by
min max R. (W) + 1 zw 1| - Ba). W X20
pd
Introducing additional variable we have also
p min max (W) + 1(11XXXXXXX 10L1x-1Tzwi) ZW)r 3a) W
A20
11
Now, v = Ar, where X = ||v||2
p"
min max R, (W) (1 -
W
32

---

Published as a conference paper at ICLR 2022
From Slater's condition, change the order of min and max without changing the objective, which proves there a saddle point:
pd max min (W) -1 ZwW' - Ballvi12. W
The inner problem is convex and depending on choice of R2 (W) can be solved for W in closed form, and subsequently the outer maximization is convex well. Thus, for linear generator and finear-activation discriminator, a saddle point provably exists and can be found via convex optimization.
Quadratic-activation discriminator (a(t) = t²). We start from the following dual problem (see Section E.3 for details)
min Rg () s.t. X (2W) (ZW)llz S Ba.
This can be lower bounded as follows:
Bg 2
2 d = min
G
p.
8.L.
X X G G $ Ba-
(42)
G
Which can further be written as:
3g G l s.t. |X X
min
G | S Ba-
G 2
This is a convex optimization problem, with closed-form solution. In particular, if we let V T be the eigenvalue decomposition of the covariance matrix, then the solution to equation 42 found via singular value thresholding:
GO V( - Bal)+ VT.
This lower bound is achievable if FW: (ZW) (ZW) G A solution is achieved by allowing W = (Z ZZ - ( Bg 122TT where computing (Z Z)-1/2 requires inverting only the first k eigenvalue directions o where == max k. Thus given that (Z)) 2 k, the solution of the linear generator, quadratic-activation discriminator can be achieved in closed-form.
In the case that rank(Z) 2 k 1, strict feasibility is obtained, and by Slater's condition saddle point of the Lagrangian exists. One can form the Lagrangian as follows:
Pg |||]| + tr x) tr(RG) Batr RR).
min max R
This is convex convex-concave game, and from Slater's condition we can exchange the order of the minimum and maximum without changing the objective:
$g ||| + tr((x x) tr( - Batr(R).
max min RZ0 G
ReLU-activation discriminator (a (t) We again start from the dual problem (see Section E.5 for details)
p" = min (W)
(W)
( (1THO) ( H zw) S 8a
s.l.
maxx
| 211
ji [M
(2() 11, Xu20
(2H -I, \Wu20
We can follow identical steps of the proof of Theorem 2.1 (see Section D.2 obtain
with ZW instead of G,
p min
W Ti 3132 max (W) Ba Σ (1IT (1rsnille 212 + (1))))1)2) +
Σ
X
1 H zw) (r - -1/1))
9
jido
S. (2H
L 0, (2H (1=) I,, WW 2 (2H(1) L,)rr 0, (2H (2)
I, /WW
as desired. Thus, as long as R2 is convex in W, we have a convex-concave game with coupled constraints.
Foor instance, letting Z = QAQ we can use (Z 1)/2 = Qua A Jap where ypa indicates taking the first columns/diagonal entries respectively.
33

---

Published as a conference paper at ICLR 2022
F.2 PROOF OF THEOREM 4.2
(1)
We note that for polynomial-activation generator with m neurons and corresponding weights wj w for samples {2:
Go, (zi) = Σ
(1) (2) (2, w w
==1
[(2 w, 11)2 + blzz blz,w,))) + c)w
Σ
aaziz w m. wn (1) + bl2z w + +c) (2)
vec(w, (1) W
(1)
)w/ (2)
avvec2zzz) 1 bz;
(1) w
T
2, w
2
2
W
ŽW
avee (202(2
for ū; =
bz
as the lifted features of the inputs, and re-parameterized weight ma-
c
(1)
(1)
(2) (2)
veel
trix Wj ==
W
Bartan & Pilanci 2021). Thus, any two-layer polynomial-
(2)
activation generator can be re- re-parameterized linear generator, and thus after substituting Ž as Z for Theorem 4.1 we can obtain the desired results.
34


Reviews:
[{"review_id": "y7_-c3T1wti", "reviewer": "Reviewer_RNn1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: \n1.  The first optimization related results on  WGAN  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.  \n2.  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.\n3. They found closed-form solutions for WGAN training as singular value thresholding, which provides interpretability.\n4. Their experiments demonstrate the interpretability and effectiveness of progressive convex\nGAN training for generation of CelebA faces.\n\nWeaknesses:\n1. It is unclear how the optimization related results on WGAN really improves our understanding WGAN. To this reviewer, knowing these results does not tell why WGAN really works as a good data generator method for many applications. ", "summary_of_the_paper": "In this paper, the authors analyzed the training of Wasserstein GANs with two-layer neural network\ndiscriminators.  They showed that WGAN can provably be expressed as a convex problem (or\na convex-concave game) with polynomial-time complexity for two-layer discriminators and\ntwo-layer generators under various activation functions.  \nThey uncovered the effects of discriminator activation on data generation through moment matching, where quadratic activation matches the covariance, while ReLU activation amounts to\npiecewise mean matching.\nThey found closed-form solutions for WGAN training as singular value thresholding, which provides interpretability.\nTheir experiments demonstrate the interpretability and effectiveness of progressive convex\nGAN training for generation of CelebA faces.", "summary_of_the_review": "Although there are some results on WGAN, knowing these results does not lead to any insights on why WGAN really works as a good data generator method for many applications. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "HLapMzT5o9u", "reviewer": "Reviewer_5mJ8", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This is an interesting paper. I like the idea of reformulating WGAN as a convex problem under a simplified two-layer architecture and then using matrix algebra to solve it analytically.\n\n**Strength** \n* Solid theoretical analysis. \n* Impressive experimental results\n\n**Weakness** \n* Lack of clarity articulating the theory and alogirthm\n\n**Detailed comments**\n\n* Some of the claims made by the author(s) are too strong. To the best of my knowledge, WGANs are only sparsely used in practical applications, yet the author(s) are making the impression that WGANs has become an integral part of standard CV tools, which is not the case. Such examples include: \n  * GANs have become arguably the workhorse of computer vision\n  * their (GANs') prevalent utilization\n\n* The author(s) claimed that: \"For the first time, we show that WGAN can provably be expressed as a convex problem (or a convex-concave game)\". I believe this statement is not entirely accurate. WGAN is the dual form of the optimal transport problem, and the entropy-regularized primal formulation is strictly convex and can be efficiently solved with Sinkhorn iterations. Note that this primal formulation is extensively used under the name earth moving distance [1,2].\n\n[1] M Cuturi. Sinkhorn Distances: Lightspeed Computation of Optimal Transport. NIPS 2013\n\n[2] L Chen, et al. Adversarial text generation via feature-mover's distance. NeurIPS 2018\n\n* This paper is about the hidden convexity of WGAN, but the related work section seems to solely focus on the discussion of GANs rather than WGANs. Also, despite claiming \"convexity has been seldomly exploited for GANs\", a long list of works has been discussed, which appeared contradictory. \n\n* The notations used for (matrix, function) dimensions are confusing. Try to avoid using subscripts for the variables defining dimensions $(n_f, n_r, d_f, d_r)$, just use lower case letters and be clear about what they mean. For functions, do not use the \"batch-level\" definition (e.g., $D: R^{nxd}->R^n$), because I believe each d-dimension vector is processed independently here. When applied to a tensor, the convention is that such a function will automatically consume the last dimension as inputs and return a reduced output tensor shaped the rest of the dimensions.\n\n* Theorem 2.1 is not clear, the statements are quite vague (e.g., \"for appropriate choice of regularizer $R_g$\", \"a series of convex optimization problems\", etc.) It is quite confusing to me what does \"in polynomial time in all dimensions for noise inputs $Z$ of a fixed rank\" mean? \n\n* It is still not clear from Eqns (4-6) how the optimal generator weights $W_1^*$, $W_2^*$ can be constructed. A related solution only appears in Sec 4. \n\n* Not enough intuitions are provided to help understand the solution. I stuck at Eqns (4-6) for quite a while trying to figure out what they mean intuitively. And some vague heuristic is only provided in a paragraph after that (e.g., \"first, it solves for the optimal generator output\"). \n\n* One major concern with the proposed solution is that the convex / convex-concave game only admits the full-batch optimization, but it does not appeal to the mini-batch optimization. This raises serious concerns about the scalability and practical applicability of the proposed solution. \n\n* The analyses only apply to the simple two-layer neural networks, for both discriminator and generator. Although more sophistication can be achieved by progressively 'stacking' the layers, still these architectural constraints exclude many modern architectures (e.g., attention, ResNet, etc.).  That said, I am still impressed with the results achieved with such simple architectures. \n\n* More details and discussions are needed on the numerical experiments. A few questions on top of my head include: (i) how do you pull-off the full-batch optimization with tens of thousands of images? (ii) matrix factorization is very sensitive to numerical precision, so are you using the standard float32 (which I consider problematic) or the double-precision float64?\n\n* Given the superior efficiency of convexity formulation, I think it is better to be used as an initialization scheme. What are the author's thoughts and can you add some discussions? Maybe further efficiency boosts can be expected using some matrix reduction schemes. \n\n* Finally, I think the result critically depends on the choice of convex regularization parameters (e.g., $\\beta_d$), yet there is no discussion on the practical guidelines for its choices. \n\n* The moment matching perspective heavily overlaps the idea of MMD-GAN. An important reference the author(s) should have discussed is [3]. \n\n[3] A Genevay, et al. Learning Generative Models with Sinkhorn Divergences. AISTATS 2018", "summary_of_the_paper": "\n+++ After Rebuttal +++\nI updated my rating to accept after reading the author(s)'s rebuttal and other reviews.\n+++++++++++++++++\n\nThis 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. ", "summary_of_the_review": "This is a well-crafted paper, with both strong theory and adequate empirical evidence to support the claims. My suggestion is to refine the presentation to highlight both the intuitions and more practical aspects. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "CbuRXs6QeG", "reviewer": "Reviewer_x4Dn", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I will only provide feedback for the theoretical part of the paper, as I do not have appropriate experience/exposure to the simulation side of GANs. However, as I read through the experimental results, it seems the author(s) are claiming that using only closed form equation (14) they can generate realistic images and can compete with the baseline progressive GDA. Also the architecture in Figure 2 looks interesting, but as I said I cannot judge the validity/novelty of this paper’s experimental results.\n\n1-\tThroughout the paper, you mention several times that your results hold when considering the Z matrix to be fixed rank, for example in Theorem 2.1 and discussion after that regarding equation (6). How/where do you justify that (theoretically and/or practically)?\n2-   In equation (6) you use convex sets K_i without defining them!\n3-\tSome parts of Lemma B.1 and especially its proof are not clear to me. As you use this Lemma multiple times in the proofs of other results, please explain the following:\n●\tWhere is the complexity analysis, which you mention at the end of your Lemma, in the proof? How does rank(Z) appear as an exponent in this bound? \n●\tIn the start of page 20, please provide more details on how you can get the dual form as claimed and how you derive the lower bound on generator hidden nodes count. Is this a novel result in this paper, or did you use the result from the mentioned 2 papers? \n●\tIt would be great if you can talk about the geometric properties of the convex sets Ki. For example as rank(Z) varies, what happens to these sets? How do you compare them to the set of all rank-1 matrices (as a subspace)?\n●\tWhen you write the Lagrangian in the middle of page 20 (you can add numbers to make referencing  these equations easy), why suddenly max over Ki changes to min? You should provide more details on deriving these Lagrangian in the paper.\n●\tTypo?: Then, “minimizing” over R leads to …. Is it maximizing or minimizing?\n●\tTypo: ijth column and row. Should be something like (i,j)th element of…\n4-\tAt the bottom of page 22, what do you mean by appropriate choice of regularizer? Which choice do you use?\n5-\tThe derivation at the bottom of page 22 requires more justification. How the 2 min problems are equivalent under the condition rank(Z)>= rank(X) \n6-\tIn deriving equation (3) in section C.1, it seems to me that actually by replacing weight decay regularization with 1-norm of v, as justified by AM-GM, we get a upper bound to p*. Is this correct? If not, please explain how we get the exact same min-max by using AM-GM (the scaling part is understood).\n7-\tTypo: after 3rd equation in page25, as well as page 26: the original optimal “the” generator weights.\n8-\tIn C.2, for the proofs, you should polish/remove/reorganize some arguments like “which we will precisely define below”\n9-\tIn the proofs of C.2, how do you suddenly replace objective Rg(W1,W2) with ||G||F ? Is it related to the assumption of overparameterizing the generator? I do not see any derivation of this sudden replacement which retains the same p*.\n10-\tError in dual variables of Lagrangian in page 26: It seems to me that {j}1{j}2 should not be used twice, as you are dealing with two different sets of constraints. I mean instead of 2 sets of dual vars, I think you should use 4; however it doesn’t seem to affect the final conclusion at page 27, and you implicitly correct it at the beginning of page 27.\n11-\tI would like to get more explanation/insight/intuition about the statement at the end of page 7, “The effect of a polynomial-activation generator is thus to provide more heavy-tailed noise as input to the generator, which provides more degrees of freedom to the generator for modeling more complex data distributions.”  \n12-\tIs there any high-level justification for the claim after equation (14) in page 7 where you say : with p∗ = d∗ under the condition that rank(Z) is sufficiently large \n13-\t Equations (14) and (25) do not match! (14) seems to be the correct one.\n14-\tsection C.3: please expand on the algorithm (Chambolle & Pock, 2011) that can solve the inner min-max. Is it computationally efficient? Do you show anywhere in your simulations that tuning , ’ is going to reach global p*? I urge you to provide more details/intuitions about min-max objectives with coupled constraints. Do they arise naturally in min-max literature? If yes please provide some references.\n15-\tIn the statements of your theorems you insist on using: “ for appropriate choice of regularizer”. I think the theorem should contain all the assumptions and choice of function/loss/regularizer. So please specify what type of regularizer you use in theorem statements.\n", "summary_of_the_paper": "Min-max optimization problems for WGANs do not necessarily have saddle points. This paper aims at providing insights into optimization tractability of WGANs in the two-layer discriminator case with different activation functions. ", "summary_of_the_review": "This paper tries to shed light on the optimization challenges of the popular WGAN formulation, and the simplified assumptions on discriminator/generator architecture look like valid ones to me. Although the authors use the previously established results in other works, gathering and presenting such results seems to be very important for less understood areas such as non-convex non-concave GAN scenarios, and I enjoyed reading through all theoretical parts of the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "4Uv7cFoqGmd", "reviewer": "Reviewer_Hxh6", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall the paper is well presented. The main results of interpreting the two-layer WGAN training problem as convex problems look solid to me. The experiments are well-conducted and the proposed method is consistently evaluated. The experiment results showed the efficiency and efficacy of the proposed method. \n\nSince under the original WGAN settings, the generator is required to be 1-Lip, so a minor concern is that how this would affect the feasibility of the convex problem. In particular, in section B.2, the 1-Lip constraints for linear activation functions are discussed, but not under other settings. I'm concerned about how this 1-Lip condition is guaranteed with other activation functions, and how this would affect the domain feasibility. ", "summary_of_the_paper": "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. \n\nThe 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. ", "summary_of_the_review": "This paper proposed for the first time the convex-concave game equivalence of 2-layer WGAN model training problem with general activation functions. Experiment results also favor the theoretic results. I would recommend accepting the paper. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors provide a convexification for the GAN training via integral probability metrics induced by two-layer neural networks. The exposition relies on the convexification tools recently proposed by the Pilanci et al., and provides interesting insights to follow up in the future.
Decision: Accept (Poster)