Forward Super-Resolution: How Can GANs Learn Hierarchical Generative Models for Real-World Distributions
Authors: Zeyuan Allen-Zhu
Yuanzhi Li
Venue: ICLR 2023 poster (2023)

Abstract: Generative adversarial networks (GANs) are among the most successful models for learning high-complexity, real-world distributions. However, in theory, due to the highly non-convex, non-concave landscape of the minmax training objective, GAN remains one of the least understood deep learning models. In this work, we formally study how GANs can efficiently learn certain hierarchically generated distributions that are close to the distribution of real-life images. We prove that when a distribution has a structure that we refer to as \emph{forward super-resolution}, then simply training generative adversarial networks using stochastic gradient descent ascent (SGDA) can learn this distribution efficiently, both in sample and time complexities.
We also provide empirical evidence that our assumption ``forward super-resolution'' is very natural in practice, and the underlying learning mechanisms that we study in this paper (to allow us efficiently train GAN via GDA in theory) simulates the actual learning process of GANs on real-world problems.


FORWARD SUPER-RESOLUTION: How CAN GANS LEARN HIERARCHICAL GENERATIVE MODELS FOR
REAL-WORDE DISTRIBUTIONS
Zeyuan Allen-Zhu Allen-Zhi Research
Yuanzhi Li
Mohamed bin Zayed University of AI Yuanzhi Li Li@mbzuai. ac ae
2eyuan2222@@lleen-thh com
ABSTRACT
Generative adversarial networks (GANs) are among the most successful models for learning high-complexity. real-world distributions. However, in theory, due to the highly non-convex, non-coneave landscape of the minmax training objective, GAN remains one of the least understood deep learning models. In this work, we formally study how GANs can efficiently learn certain hierarchically generated distributions that are close to the distribution of real-life images. We prove that when a distribution has structure that we refer to as forward super-resolution. then simply training generative adversarial networks using stochastic gradient de- scent ascent (SGDA) can learn this distribution efficiently, both in sample and time complexities. We also provide empirical evidence that assumption "forward super-resolution" is very natural in practice, and the underlying learning mecha- nisms that we study in this paper (to allow us efficiently train GAN via SGDA theory) simulates the actual learning process of GANs on real-world problems.
INTRODUCTION
Generative adversarial networks (GANs) (Goodfellow et al. 2014) are among the successful models for learning high-complexity, real-world distributions. In practice, by training a min-max objective with respect to generator and a discriminator consisting of multi-layer neural networks, using simple local search algorithms such as stochastic gradient descent ascent (SGDA), the generator can be trained efficiently to generate samples from complicated distributions (such as the distribution of images). But, from theoretical perspective, how can GANs learn these distributions efficiently given that learning much simpler ones are already computationally hard (Chen et al. 2022a)?
Answering this in full can be challenging. However, following the tradition of learning theory, one may hope for discovering some concept class consisting of non-trivial target distributions, and min-max ceneratoo-discriming showing that using SGDA trainability), but more importantly, the generator learns the target converges in poly-time (a.kaa distribution good accuracy (a.k.a. learnability). To this extent, believe prior theory works studying GANS may still be somewhat inadequate.
objective, not only the training
Some existing theories focus on properties of GANs at the global-optimum (Arora et al., 2017, 2018. Bai al.) 2018, Unterthiner al. 2017);; while it remains unclear how the training process can find such global optimum efficiently.
Some theories focus on the trainability of GANs, in the case when the loss function is convex- concave (so a global optimum can be reached), point (Daskalakis & Panageas, 2018a b. Gidel et al. 220T8; Heusel al., 2017 Liang & Stokes, 2018 Lin et al. 2019, Mescheder et al., 2017; Mokhtari et al., 2019; Nagarajan & Kolter, 2017). Due to non-linear neural networks used practical GANs, it highly unlikely that the min-max training objective is convex-concave. Also, it is unclear whether such critical points correspond to learning certain non-trivial distributions (like image distributions).
when the goal is only to find critical
Full version of this paper be found http:://aarsv..orr/ass////

---

Even if the generator and the discriminator are linear functions over prescribed feature mappings such as the neural tangent kernel (NTK) feature mappings - see (Allen-Zhh et al. 2019b;
Arora et al. 2019; Daniely et al. 2016, Du et al., 2018, Jacot al. 2018 Zou al. 2018) and the references therein- - the training objective can still be non-convex-concav.
Some other works introduced notions such proximal equilibria (Farnia & Ozdaglar 2020) or added gradient penalty (Mescheder et al. 2018) to improve training convergence. Once again, they do not study the "Icarnability" aspect of GANs. In particular, Chen et al. (2022b) even plicitly argue that min-max optimality may not directly imply distributional learning for GANs.
Even worse, unlike supervised learning where some non-convex learning problems can be shown to haveno bad local minima (Ge al., 2016), to the best of our knowledge, it still remains unclear what the qualities are of those critical points in GANs except in the most simple setting when the generator is one-layer neural network (Feizi et al., 2017 Lei et al. 2019).
(We discuss some other related works in distributional learning in the full version.)
Motivate by this huge gap between theory and practice, in this work, we make a preliminary step by showing that, when an image-like like distribution hierarchically generated (using an unknown (1)) layered target generator) with a structural property that we refer to forward super-resolution,, then under certain mild regularity conditions, such distribution can efficiently learned - both in sample and time complexity by applying SGDA on GAN objective, Moreover, to justify the scope of our theorem, we provide empirical evidence that forward super-resolution holds for practical image distributions, and most of our regularity conditions hold in practice as well.
We believe our work extends the scope of traditional distribution learning theory to the regime of learning continuous, complicated real-world distributions such the distribution of images, which are often generated through some hierarchical generative models. We draw connections between tra- ditional distribution learning techniques such as method of moments to the generator-discriminator framework in GANs, and shed lights on what GANs are doing beyond these techniques.
1.1 FORWARD LUPER-RESOLUTION A SPECIAL PROPERTY OF IMAGES
Real images can be viewed in multiple resolutions without losing the semantics. In other words, the resolution of an image can be greatly reduced (c.g. by taking the average of nearby pixels), while still keeping the structure of the image. Motivated by this observation, the seminal work of Karras al. (2018) proposes to train generator progressively: the lower levels of the generator are trained first to generate the rnwer-resolution version of images, and then the higher levels are gradually trained to generate higher and higher resolution images. In our work, we formulate this property of images as what we call forward super-resolution:
Forward super-resolution property (mathematical statement see Section 2.1):
There exists a generator G' as an T--idden-layye neural network with ReLU activation, where each Ge represent the hidden neuron values at layer f, and there exists matrices W. such that
the distribution of images at resolution level e is given by WeGr
and the randomness taken over the randomness of the input to G (usually standard Gaussian).
In plain words, we assume there is an (unknown) neural network G' whose hidden layer G2 can be used to generate images of resolution level e (larger means better resolution) via a linear transfor- mation, typically deconvolution. We illustrate that this assumption holds on practical GAN training in Figure I. This assumption is also made in the practical work (Karras et al., 2018). Moreover, there body of works that directly use GANs or deconvolution networks for super-resolution (Bulat & Tzimiropoulos, 2018, Ledig et al. 2017, Lim et al. 2017. Wang et al., 2018; Zhang et al., 2018).
2 PROBLEM SETUP
Throughout this paper, use a poly(b) for 0,b to denote that there absolute constants C₁ > C2 > such that 80: < a < b0, For a target learning error e E [g-t poly J.
Plus simple SVD warmup initialization that is casily computable from the covariance of image patches.
2

---

resolution 64x64
resolution 32x32
resolution 16x16
resolution 8x8
64x6x6x3
deconvolution
64x6x6x3
deconvolution
64x6x613
deconvolution
64x6x6x3
64 channels
1x100
standard Gaussian
64 channels
64 channels
channels
4x4
16x16
32433
deconvolution
deconvolution
ReLU
ReLU
deconvolution
ReLU
deconvolution
ReLU
Figure 1: Illustration of the forward super-resolution structure. Church images generated by 4-hidden- layer deconvolution network (DCGAN), trained LSUN Church data using multi-scaled gra- dient (Karnewar & Wang 2019). The structure generator is shown above, and there ReLU activation between each layers. We use simple average pooling to construct low resolution images from the original training images.
we use "w.h.p." to indicate with probability 2 (d/e) Recall ReLU(2) = max(2, 0}. In
this paper, for theoretical purpose we consider smoothed version ReLU(z) and leaky version LeakyReLU(z)). We give their details in the full version, and they are different from ReLU(z) only by a sufficiently small quantity 1/poly(d/e).
2.1 THE TARGET DISTRIBUTION: FORWARD SUPER-RESOLUTIEE STRUCTURE
We consider outputs (think of them as images) {X] where Xī, is the final output, and Xi the "low resolution" version of Xi, with X; having the lowest resolution. We think of each f-resolution image X consists of de patches (for example, an image of size 36 x 36 contains 36 patches of size 6 x 6), where X; (X (iE((a) and each X2, Rd Typically, such "resolution reduction" from X to Xī can be given by sub-sampling, average pooling, Laplacian smoothing, etc.. but we do not consider any specific form of resolution reduction in this work, as does not matter for our main result to hold.
Formally, we define the forward super-resolution property as follows. We are given samples of the form (²) = (Xi, Xž, xx2), where each X; is generated by an unknown target neural network (z) at layer f, with respect to standard Gaussian z ~ N(00, Impxmo)
The basic resolution: for every j E (di).
Xi, Si, E dd for = ReLU bi.)) E R
where Vi,, E 1 jgm: xmo, bi.j m and we assume Wi.; E [Rdxm is column orthonormal.
For every 8 > 1, the image patches at resolution level are given as: for every j E [de].
X7 = Wi, E Rdd for ST = ReLU (Eyepe, Via b E R
where Visi.' E R.mexm--,, b2g E R and we assume Wi, E Rdxme column orthonormal.
Here, Pr.j C [de-1] can be any subset of [dg-1] to describe the connection graph.
Remark. For every layer f E [de), [me]. one should view of each )r as the r-th channel the j-th patch at layer l. One should think of Eyep, V Vis. as the linear "deconvo- lution" operation over hidden layers. When the network is a deconvolutional network such as in DCGAN (Radford al. 2015), we have all W W but we do not restrict ourselves this case. As illustrated in Figure 2, we should view W as matrix consisting of the "edge-color" fea- tures generate image patches. Crucially, when we get data sample G* G*(2) (X1, ..,... Xi))
3

---

the learning algorithm does not know the underlying used for this sample.
[Wa.}}
{W2,)
[Wa,)
[Wa,)
= examples of patches dominated by edge features
= examples of patches dominated by color features
Figure 2: Visualization of the edge-color features learned in the output layers of G". Each We is of dimen- sion my d x 108 64 (6 x 3). The network is trained as in Figure Note: For deconvolutional output layer, all W are equal for all j [me]-
Although our analysis holds many settings, for simplicity, in this paper we focus on the following parameter regime (for instance, de can be d'):
Setting 2.1. L == 0(1,, each me poly(d), each de poly(d), and each Visss S poly(d).
To efficient learn distribution with the "forward super-resolution" structure, assume that the true distribution in each layer of G satisfies the following "sparse coding" structure:
Assumption 2.2 (sparse coding structure). For every é [L],] E [de]. E [me]] there exists some kg & me with kig [2i( me), m o such that recalling St, 2 0 is non-negative vector.
Prz~A((o.)) [1S 0] s polv(ke)) me
EzaN(a.)) [[ 2 poly(He)yme
w.h.p. over 2: ||S 11.0 I poly(ke), ||57, S ke
Moreover, we within the same patch, the channels are pair-wise and three-wise "nol-too-positively correlated": ; Vp, q, v. E [me)) p & #
Prz [S > 0, |1 > 0 Si
poly(ke) m
Pr. [S 0, [5 0, 0, 00 S
Remark 2.3. Although have borrowed the notion of sparse coding, task is very different from traditional sparse coding. We discuss more in the full version.
Sparse coding structure in practice. The sparse coding structure is very natural in practice for generating images (Gu et al., 2015; Zheng et al., 2010). As illustrated Figure 2, typically, after training, the output layer of the generator network Wr.j forms edge-color features. It is known that such edge-color features are indeed a (nearly orthogonal) basis for images, under which the coefficients are indeed very sparse. We refer to (Allen-Zhu & Li 2021) for concrete measurement of the sparsity and orthogonality. The noo--ooo-positive correlation' property also very natural: for instance, in image patch if edge feature is used, it is less likely that color feature shall be used (see Figure 2). In Figure 3, we demonstrate that for some learned generator networks, the activations indeed become sparse and "nol-too-positively correlated" after training.
Crucially, we have only assumed that channels are not-too-positively correlated within single patch, and channels across different patches (e.g Si and S),2) can be arbitrarily dependent. This makes the global structure of the images can still be quite arbitrary, so Assumption 2.2 can indeed be reasonable
Here, poly (kz) can be an arbitrary polynomial such as (kz) and our final thcorem holds for sufficiently large because d²(1) > poly(kz).
"Within patch, it is natural that the activations not-too-positively correlated: for example, once patch chooses horizontal edge feature, it less likely that will pick up another vertical edge feature.
4

---

400
25000
15:000
300
20000
10000
15:000
200
trained
init
trained
trained
10000
100
5000
5000
Init
1.0
0.3
0.1
0.3
histogram
Pr[[S > 0] of Pr[[S,, (, > 0]
histegram Pe((S plo
0.15%, gla
0. 0111,, Ir 0]
Figure 3: Histograms at random init vs. after training for layer = 2 of the architecture in Figure 1 Exper- iments for other layers he found in Figure 6 shows the learned network has sparse, not-too- positively correlated hidden activations (we did not regularize sparsity or correlation during training). Thus, it can be reasonable to assume that the activations of the target network are also sparse
Missing details. We also make very mild non-degeneracy and contiiioncnttationn assumptions, and give examples for networks satisfying our assumptions. We defer them to the full version.
2.2 LEARNER NETWORK (GENERATOR)
We use a learner network (generator) that has the same structure as the (unknown) target network:
The image of the first resolution is given by:
X1 W1,5 S1.5 E Rd for S1,j = LeakyReLU( - b1.5) E T
for W1.j E d V1 E R with mb 2 2d
The image of higher resolution is given by:
Xz. WeySe, E Rd for St, LeakyReLU (E,'p,,, V bes) E m
for We, E Rdxms and Vej E Bmexm--..
One can view St as the l-th hidden layer. We use Ge(2) to denote (XtJ))E(aL)- We point out both the target and the learner network study here can be standard deconvolution networks.
2.3 THEOREM STATEMENT
This papers proves that by applying SGDA on a generator-discrinne discriminator objective (algorithm to be learn the target distribution using the above generator network.
described in Section 3),
Theorem E.1. For every d every La-ty, 1 letting G(=) (X.()),..., Xx(z)) be the generator learned after running Algorithm 6 (which in time/sample complexity poly(d/e)), xmm such that
then w.h.p. there column orthonormal matrix U m
Prz-N(O.T mb)mm))) ((C((Uz)G(()))) SE 21 (dfe)-03
In particular, this implies the 2- Wasserstein distance W2(G(.),G* Se.
LEARNING ALGORITHM
In this section, define the learning algorithm using min-max optimization. We assume one access polynomially many (i.e., poly(d/e) i.i.d. samples from the true distribution X* Xx .X)). generated by the (unknown) target network defined in Section 2.1
To begin with, we use a simple SVD warm start to initialize (only) the output layers W., of the network. It merely involves simple estimator of certain truncated covariance of the data. We defer
We also point that if [87,]''s are all independent, then Pr[[ST,]p 0, 0,[87,,l 0 # S and
Pr[[S7,]p > 0, [Si 0, [S > 0] m & E2.
5

---

it to the full paper. Also, we refer stochastic gradient descent ascent SGDA (on the GAN objective)
to an algorithm to optimize min, max, f(z y), where the inner maximization is trained at a faster frequency. We call it Algorithm 4 and include its pseudocode in the full paper.
To make the learning process more clear, we break the learning into multiple parts and introduce
them separately in this section:
GAN LANtuur to learn output matrices {We,) | per layer.
CAN_FirstHiddens to learn hidden matrices { (Vi.) for the first layer.
GAN FowardSuperResolution to learn higher-level hidden layers {Veid.)
We use different discriminators different parts for our theory analysis, and shall characterize what discriminator does and how the generator can leverage the discriminator to learn the target distribution. We point out, although one can add up and mix those discriminators to make it single one, how to use same discriminator across the entire algorithm remains open.
At the end of this section, we shall explain how they are combined to give the final training process. Remark 3.1. Although we apply an SVD algorithm to get warm start on the output matrices Wi,j. the majority of the learning of We, gradient descent ascent. We point out that the seminal work neurally plausible dictionary learning also considers such a warm start (Arora et al. 2015a).
t.j (e.g.. to any small poly[a] error) is still done through
3.1 LEARN THE OUTPUT LAYER
We first introduce the discriminator for learning the output layer. For each resolution & E and patch j E [de). we consider a one-hidden-layer discriminator
Dr) = = ([eLU TT, - bY V2
where the input is either Y = X (from the true distribution) or = X2 (from the generator).
Above, on the discriminator side, we have default parameter W b and trainable parameters V2 = (V2g where each V...r E Rdd On the generator side, we have trainable param- eters We, (which are used calculate X₂). (We use superscript to emphasize W are the parameters for the discriminator, distinguish from Wey.)
In pseudocode GAN JAN.OutputLayerr (see Algorithm 1), for fixed W2,, b, perform gradient descent ascent the GAN objective with discriminator D minimize over V2 and maximize over W Wey-- In our final training process (to be given in full in Algorithm 6), shall start with some b < 1 and periodically decrease it; and we shall periodically set W WeJ to be the same as the generator from a previous check point.
Simply setting w E.j Wej involves no additional learning, as all the learning is still being
done using gradient descent ascent.
practice, the first hidden layer of the discriminator indeed learns the edge-color detectors (see Figure 8 in the full paper), similar to the edge-color features in the output layer of the generator. Thus, setting WP: We, is a reasonable approximation. As we pointed out, how to analyze a discriminator that exactly matches practice is an important open theory direction.
INTUITION:
WHAT DOES THE DISCRIMINATOR DO? To further understand the algorithm, can see that for each V.D,r. when its norm is fixed, then the maximizer is obtained at
Veg.r [E(ReLU'([[W3 E.4) X2 b)X2, - E[ReLU ((((( T Xe,])- - b),))))
Thus, for the generator to further minimize the objective, the generator will learn match the moments of the true distribution. In other words, generator wants to ensure
E|ReLU' P2) Xe,lt b), 1 ([RRLLU([(WA)) T Xish- b)X2
In this paper, we prove that such a truncated moment can be matched efficiently simply by running gradient descent ascent. Moreover, empirically observe (see Figure 4) that GANs indeed do

---

Algorithm (GAN_ Outputlaa))) method of moments
Input: W (0)
Ej b,l,
1: Set W W b bm.2, N poly(d/s) 7 poly(dje)) T poly(d/e)
Ej
2: Set initialization We, f w and V +0
3: Apply SGDA (Algorithm 4) with N samples, learning rate v) for T steps on the following GAN objective (with being small constant such as 0.001):
minwey maxyo (EID (x (x TE ( - Ere(ma) (mmd)
I1 2.j.
11
II is an analog of the weight
4:
[e.jjp f- W We.llp// e.ppl
2
100%
100%
100%
BbBl
15436
60%
60%
60%
0%
0%
0%
50
30
40
20
30
apech
opoch
opoch
1 order matching
2nd order moment matching
3 order moment matching
100%
100%
50%
---16x
80%
-.-16x16
50%
-6cc1
60%
60%
30%
10
20%
20%
0%6
30
40
50
20
30
40
50
10
20
30
40
4th order moment matching
5th order moment matching
6th order moment matching
Figure 4: Difference between the moments of generator's output and the true distribution. The z-axis number of epochs and the y-axis quantifies how close the moments are (the smaller the closer). Details are in Figure 9 One can see that the moments begin to match after epoch 10.
moment matching within each patch even at the earlier stage of training.
3.2 LEARN THE FIRST HIDDEN LAYER
Due to space limitation defer the pseudocode and algorithm details of GAN.FirstHidden to the full version of this paper. However, we give the high level intuitions below.
HIGH-LEVEL INTUITIONS. In the process of learning the lowest-resolution images Xi, one cannot hope for (even approximately) learning the exact matrices Vi. or the exact function that maps from X (because is unknown during the training). Instead, the task is for learning the distribution bi,))-
of Xix =
Suppose for moment that Wi,; are already fully learned; then, it is perhaps surprising that for the remaining part Si ReLU(Vi,, bi.)), if we can somehow
1. learn the marginal distribution of [Si,)]- for each j. and 2. lear the joint distribution of [St.), for each pair (j.r) * (j', r'))
then, we can recover the joint distribution of ([St,lrri..- (As analogy, for joint Gaussian, it suffices to learn the pair-wise correlation.) To achieve this, we design discriminators (44) and ()5)
(4) discriminates the mismatch from single neurons by ensuring
ReLú (I(W))) T Xi,IIr b) b) E ReLú (I(WP)) Xi,h-- -6)
$Like in the previous subsection, shall periodically set WD We, to be the same as the generator from previous check point; and the bias h 1.

---

1x100
4n4o54
Exthvi4
10415
32x32
USS
Figure 5: Forward super-resolution is local operation; more details in Figure
E ReLÚ (I(WP)) X1,,lr b) ~ ReLU (I(WP))T Xi,,++ - b)
Furthermore, long as WP, I.f is moderately learned, the sparse coding structure shall ensure (WP)) X1J S1,5 and (WP,)) T.P.) Xi,
Si.y For such reason, and using < 1, applying gradient descent ascent using discriminator D(4), in fact guarantees
ReLÚ ((S1)))) s ReLú (1S1,1+)) and ERLLÜ ([S1,]=) E ReLÚ ([St.yle) Recall ار behaves as RgLU(g) for ~ ((-,, 0²) and has only 2 degrees of freedom; thus, matching moments on ReLU and ReLU learn the distribution of single neuron [St,y]r.
(5) discriminates the mismatch from the moments across two neurons, by ensuring
E ReLÚ (I(WP)) Xi.)r- b) ReLú (I(WP,) X1 - b)
E ReLU (I(WP)) T Xi,] b) ReLú (I(WP,)) xi bb]
For similar reason, gradient descent ascent learns to match moments on the cross terms:
E ReLU ((Sr,))) ReLÚ ((81,))))) E ReLU ((St,)+) ReLU ((st.))))) We show this corresponds to learning ([Vi.,lr. (Vi moderate accuracy.
In sum, if we apply SGDA on (44) and (5) together, we can hope for learning V1 up to a unitary transformation (see Lemma 1,18). This ensures that we learn the distribution of Xi.
3.3 LEARN HIGHER HIDDEN LAYERS
For resolution >>> 1, patch j E [de], channel r E [mæ]. to learn [Vigle. we introduce discriminator E.j.r (Yi, Y2). It takes as input images of two resolutions: one should think of either (Yi, Y2) XXixXt comes from the true distribution, or (Y1, Y2) = (X,, Xe-1) from the generator.
(2) L.j (Y1, Y2) = abs (s, LeakyReLU(s,)))
where abs(r) = ReLŪ - b) ReRRR b)
= (IW2)) (T,T)
5, EEye,,, LeakyReL (IW21g.1 TT2,)) 6P,)
Above, again W
are default parameters (changed only periodically).
On the discriminator side, ([Vp brbrer,,,,, [6 are the actual trainable parameters; on the gen- erator side, v. hye:,, , [be, as the trainable parameters. We note this discriminator (?) a three-hidden layer neural network. Yet, we show that such an network (together with the generator) still be trained efficiently using gradient descent ascent.
8

---

Algorithm 2 (GANN www..FooaardSupeRRRssluiiii using super-resolution to learn higher hidden layers
Input: w (0) w 2-11 b,
1: Set default parameters WhJ t W W 1-1 f (0) 1-1
poly|d/e3 17 poly(d/e) f poly(d/c), AG,AD poly(d/e)
2: N f
3: Initialize Vt.jj' = VD "., = I for one of j' E Pt.j and setting others as zero. Initialize br. = 0.
4: for E [me]] do
5: Apply SGDA with N samples, learning rate 1 for steps on the following GAN objective
min ([V) (IP.yyyl-- -bP (Ve.s.leee
max
[E (2)
[R. E ( (Xt, Xi-1)) EID (Xe, Xe-1)))
[be,le
- -Vell V
6: 11 + + poly(k1)6.
INTUITION: WHAT DOES THE DISCRIMINATOR DO? In this case, applying gradient descent ascent on 22 actually learns how to "super-resolute" the image from resolution level e to level t. In particular, the discriminator wants to find way where the patches (, X(-1.3) ) differ statistically from the patches (Xi,, - (g)). For example, it can discriminate when - U2, but 1, = v1, Xe, A U2. In essence, it is discriminating the way where the generator super- resolutes patch Xł, from lower resolution differently from that of the true distribution.
= Xi
As demonstrate in Figure 5| such "super-resolution" operation is local, meaning that the learning process can be separated to learning over individual patches. The global structure across different patches of the images are learned in lower resolutions. This makes the learning process much simpler comparing to learning the full image from scratch. 6 We also provide empirical justification of the power of this "forward super-resolutionn, indeed learn to super-resolute from the lower resolution images, which makes the learning much easier comparing learning from scratch.
in Figure 10(top) of the full paper: higher layers can
3.4 FINAL ALGORITHM
We implement our full algorithm in Algorithm (see full paper). It performs layer-wise training. In each outer loop E 1,2..... weights are still very inaccurate Next, for this layer L, Algorithm 6 alternatively:
..... L, it first warm-starts the output layer (We,) [iy))eeaa)) note those
uses the current output layer Wej to learn the hidden variables St,, (or equivalently the weights Ve.j,be.) to some accuracy
by applying GAN_FirstHidden if or if 2 2; and
GAN M.AN.ooaarSSupeRRsolitti
uses the current hidden variables St,j to learn the output layer W even better accuracy
- by applying GAN_OutputLayer
This alternating process repeats for T = Ō(1) stages. Once again, we have broken the learning into multiple parts for analysis purpose, so it becomes clear how the generator can leverage the dis- criminator at different stages to learn the target distribution. (With more careful choices of learning rates, one can also combine them altogether.) Please note besides simple SVD warm-start that called only once per output layer We,j. all the learning is done using minmax optimization cenerator-discriminato objective.
What's in Full Paper. We encourage readers to our full paper https: /ttss://arxivv org/ abs/2106 02619 the full version, we includes more related works and missing figures to better support the connection between
theory and practice. We also includes missing details for our technical assumptions from Section 2, and pseudocodes from Section 3) We restate our main theorem and the high level proof plan, and shall also discuss limitations and open directions there.
At resolution the learning is global: in this case the one- mee-hidden-lann layer generator be trained via SGDA capture the "global structure" of images (see Section and Figure 1). with the help from properties of Gaussian random variable.
Since the hidden variables St, this layer é- which depend on weights (Ve, learned, this point, the best can do is to look the data covariance and give ,, very rough estimate.
still not

---

REFERENCES
Zeyuan Allen-Zhu and Yuanzhi Li. LazySVD: Even Faster SVD Decomposition Yet Without Agonizing Pain.
In NewrlPS. pp. 974-982, 2016. Full version available at /aatt:://aaat v. httptp:://aaiv..g///aaa///////// 600. 033463)
Zeyuan Allen-Zhu and Yuanzhi Li. What Can ResNet Learn Efficiently. Going Beyond Kernels? In NewrIPS,
2019a. Full version available at http:p:/aaxxx...ro../.
1
Zeyuan Allen-Zhu and Yuanzhi Li. Can SGD Learn Recurrent Neural Networks with Provable Generalization?
In NewrIPS, 2019h. Full version available at httpt::://// pestt://arxinn or abs/ 1902.0101111 0108
Zeyuan All and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning.
arXiv preprint arXiv:2001. 1.04000..413,.000 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learn-
ing. In FOCS. 2021. Full version available at atthtp::// //wpiv/aavvvv///////////a. crgg wttgg/bbs/2033 10190
Zeyuan Allen-Zhu and Lorenzo Orecchia. Linear Coupling: An Ultimate Unification of Gradient and Mirror Descent. In Proceedings of the 8th Innovations in Theoretical Computer Science, ITCS '17 2017. Full version available at htt::: / /ttp/arxvvv/.. crg/ abs/ 1407.11 1537
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and Generalization in Overparameterrized Neural Networks, Going Beyond Two Layers. In NeurlPS, 2019a. Full version available at http://arxiv.
org/abs/18 aataaa///111.... 04918
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. convergence theory for deep learning via over- parameterization. In ICMI,, 2019b. Full version available at http:://arxiv.. org/ ht/g//b//11 181 12111.033 03962
Sanjeev Arora, Rong Ge, Tengyu Ma, and Ankur Moitra. Simple, efficient, and neural algorithms for sparse coding. Journal of Machine Learning Research, 40(2015), 2015a.
Sanjeev Arora, Rong Ge, Ankur Moitra, and Sushant Sachdeva. Provable ica with unknown gaussian noise, and implications for gaussian mixtures and autoencoders. Algorithmica, 72(1):215-236, 2015b.
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and equilibrium in gen- erative adversarial nets (gans). In Proceedings of the 34th International Conference on Machine Learning- Volume 70. pp. 224 232. JMLR. org, 2017.
Sanjeev Arora, Andrej Risteski, and Yi Zhang. Do gans Iearn the distribution? some theory and empirics. 2018.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. CoRR, abs/1901 abs/1901.08884, 2019. URL
901 http: wwtpwxwwwwwggaaa////p/p 1901 08584
Francis Bach and Michael Jordan. Learning graphical models with mercer kernels. Advances in Neural Infor-
mation Processing Systems, 15:1033 -040,, 2002.
Yu Bai, Tengyu Ma, and Andrej Risteski. Approximability of discriminators implies diversity in gans, arXiv preprint arXiv:/806. 10586, 2018.
Ainesh Bakshi, Rajesh Jayaram, and David P Woodruff. Learning two layer rectified neural networks in poly- nomial time. arXiv preprint 18110088 2018.
Mikhail Belkin and Kaushik Sinha. Polynomial learning of distribution families. SIAM Journal on Computing,
44(4):889 9119 2015.
Stefano Beretta, Mauro Castelli, Ivo Gonçalves, Roberto Henriques, and Daniele Ramazzotti, Learning the structure of bayesian networks: A quantitative assessment of the effect of different algorithmic schemes. Complexiry, 2018
Quentin Berthet, Philippe Rigollet, and Piyush Srivastava. Exact recovery in the ising blockmodel. Annals of Statistics, 47(4):8805- 1834, 2019.
David M Blei, Andrew Y Ng, and Michael Jordan. Latent dirichlet allocation, Journal of machine Learning research, 3(Jan):933-0022, 2003.
Digvijay Boob and Guanghui Lan. Theoretical properties of the global optimizer of two layer neural network. arXiv preprint arXiv: 12411, 2017.
Guy Bresler. Efficiently learning ising models on arbitrary graphs. In Proceedings of the sevte- annual
ACM symposium on Theory of computing, pp. 771-782, 2015.
Guy Bresler, Frederic Koehler, Ankur Moitra, and Elchanan Mossel. Learning restricted boltzmann machines influence maximization. arXiv,, pp. arXiv-1805, 2018.
Alon Brutzkus and Amir Globerson. Globally optimal gradient descent for a convnet with gaussian inputs.
arXiv preprini 1xX.::1002.07666 2017.
Adrian Bulat and Georgios Tzimiropoulos. Super-fan: Integrated facial landmark localization and super- resolution of real-world low resolution faces in arbitrary poses with gans. In Proceedings of the IEFE Conference on Computer Vision and Pattem Recognition, pp. 109-117, 2018.
10

---

Sitan Chen, Jerry Li, and Yuanzhi Li. Learning (very) simple generative models is hard. arXiv preprint arXiv:2205. /6003, 2022a.
Sitan Chen, Jerry Li, Yuanzhi Li, and Raghu Meka. Minimax optimality (probably) doesn't imply distribution learning for gans. arXiv preprint vrXiv:2201.07206 2022b.
Dario Cordero-Erausquin, Matthieu Fradelizi, and Bernard Maurey. The (b) conjecture for the gaussian measure of dilates of symmetric convex and related problems. Journal of Functional Analysis, 214:410-427, 09
2004. doi: ffa166jjaa.2033... 12.001.
Rónán Daly, Qiang Shen, and Stuart Aitken. Learning bayesian networks: approaches and issues. The knowl- edge engineering review, 26(2):99, 2011.
Amit Daniely, Roy Frostig, and Yoram Singer. Toward deeper understanding of neural networks: The power
of initialization and dual view on expressivity. In Advances Neural Information Processing Systems (NIPS), pp. 2253- 22.1. 2016.
Sanjoy Dasgupta. Learning mixtures of gaussians. In 40th Annual Symposium on Foundations of Computer Science (Cat. No. 99CB37039), pp. 634-644, IEEE, 1999.
Constantinos Daskalakis and Toannis Panageas. Last-iterate convergence: 7ero-sum games and constrained min-max optimization. arXiv preprint arXiv: 000500020.222.... 2018a.
Constantinos Daskalakis and loannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236 9246, 2018b.
Mathias Drton and Marloes H Maathuis. Structure learning in graphical modeling. Annual Review of Statistics and Its Application, 4:365-393, 2017.
Simon S Du, Xiyu Zhai Barnabas Paczos, and Aarti Singh. Gradient descent provably optimizes over- parameterized neural networks. arXiv preprint arXiv:1810.0200 2018.
Farzan Farnia and Asuman Ozdaglar. Do gans always have nash equilibria? In International Conference on Machine Learning, pp. 3029-3039, 2020.
Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse. Understanding gans: the lag setting, arXiv preprint 17.0. 107993 2017.
Rong Ge, Furong Huang, Chi Jin, and Yang Yuan. Escaping from saddle points?online stochastic gradient for Conference on Learning Theory, pp. 797-842, 2015.
tensor decomposition.
Rong Ge, Jason D Lee, and Tengyu Ma. Matrix completion has no spurious local minimum. In Advances in Neural Information Processing Systems, pp. 2973-2981, 2016.
Rong Ge, Jason D Lee, and Tengyu Ma. Learning one-hidden-layer neural networks with landscape design.
arXiv preprint arXiv:1711.0053
2017.
Rong Ge, Rohith Kuditipudi, Zhize Li, and Xiang Wang. Learning two-layer neural networks with symmetric inputs. arXiv preprint Xiv: /ix::vvv:..... /8/0.0693, 2018.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Remi Lepriol, Gabriel Huang, Simon Lacoste- Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. arXiv preprint 1vXiv:180.0047440 2018
Ian Goodfellow. Jean Poudet-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair. Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural information process- ing systems, pp. 2672-2680, 2014.
Shuhang Gu, Wangmeng Zuo, Qi Xie, Deyu Meng, Xiangehu Feng, and Lei Zhang. Convolutional sparse coding for image super-resolution. Vision, pp. 1823-1831, 2015.
Proceedings of the IEFE International Conference on Computer
David Heckerman. A tutorial on learning with bayesian networks. In Innovations in Bayesian networks, pp. 33 82. Springer, 2008
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Berhard Nessler, and Scpp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in neural information processing systems, pp. 6626-6637, 2017.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018.
Chi Jin, Rong Gc, Pranecth Netrapalli, Sham Kakade, and Michael I Jordan. How escape saddle points efficiently. In International Conference on Machine Learning, pp. 1724-1732, 2017.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael I. Jordan, On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. arXiv preprint 1902::1902.04883 2019. Animesh Kamewarr and Oliver Wang. Msg-gan: multi-scale gradient gan for stable image synthesis. arXiv preprint arXiv:1903 06048, 2019.
11

---

Tero Karras, Timo Aila, Samuli Laine, and Jaakko Lehtinen. Progressive growing of gans for improved quality, stability, and variation. International Conference on Learning Representations, 2018.
Kenji Kawaguchi. Deep learning without poor local minima. In Advonces in Neural Information Processing Systems, pp. 586-544, 2016.
Adam Klivans and Raghu Meka. Learning graphical models using multiplicative weights. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pp. 343-354. IEEE, 2017.
Christian Ledig, Lucas Theis, Ferenc Huszár, Jose Caballero, Andrew Cunningham, Alejandro Acosta, Andrew Aitken, Alykhan Tejani, Johannes Totz, Zehan Wang, et al. Photo-realistic single image super-resolution using a generative adversarial network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 4681-4690, 2017.
Qi Lei, Jason D Lee, Alexandros G Dimakis, and Constantinos Daskalakis, Sgd learns one-layer networks in wgans, arXiv preprint arXiv:1910.07000, 2019.
Yuanzhi Li and Zehao Dou. When can wasserstein gans minimize wasserstein distance? arXiv preprint arXiv:2003.04000 2020.
Yuanzhi Li and Yingyu Liang. Provable alternating gradient descent for non-negative matrix factorization with strong correlations. In Proceedings of the 34th International Conference on Machine Learning Volumm 70, pp. 2062-20770. JMLR. org, 2017.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Ad- vances in Neural Information Processing Systems, pp. 597-607. http::/arxii..// http://arxxv.orr/abb//// wrw//b// 705 000809986, 2017.
Yuanzhi Li, Yingyu Liang, and Andrej Risteski. Recovery guarantee of non-negative matrix factorization via alternating updates. In Advances neural information processing systems, pp. 4987-4995. 2016.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over seer-aaameterized matrix sens- ing and neural networks with quadratic activations. In COLT, 2018.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over- per-pparamtrriee two-layer neural networks beyond ntk. In Conference on Learning Theory, pp. 2613-2682, 2020.
Tengyuan I Liang and James Stokes. Interaction matters: A note non-asymptotic local convergence of gener- ative adversarial networks. arXiv preprint urXiv:1802.061:3 2018.
Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lec. Enhanced deep residual networks for single image super-resolution. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pp. 136-144, 2017.
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-coneave minimax prob- lems. arXiv preprint urXiv:1906.003: 00031, 2019.
Andrey Y Lokhov, Mare Vuffray, Sidhant Misra, and Michael Chertkov. Optimal structure and parameter learning of ising models. Science advances, 4(3) 2018.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, pp. 1825-1835, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually con- verge? In International conference on machine learning, pp. 3481-3490, 2018.
Ankur Moitra and Gregory Valiant. Settling the polynomial Icarnability of mixtures of gaussians. In 2010 IEEE
51st Annual Symposium Foundations of Computer Science, pp. 93-102. IEEE, 2010.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil, A unified analysis of extra-gradient and optimistic gradient methods for saddle point prohlems: Proximal point approach. arXiv preprint 10Xiv:9900.085. 2019.
Vaishnavh Nagarajan and J Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in neural information processing systems, pp. 5585 5595, 2017.
Richard E Neapolitan et al. Learning bayesian networks, volume 38. Pearson Prentice Hall Upper Saddle River, NJ, 2004.
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization:: global convergence guar- antees for training shallow neural networks. arXiv preprint arXiv: 2019.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint 11114:1511.06434 2015.
Mahdi Soltanolkotabi, Adel Javanmard, and Jason Lee. Theoretical insights into the optimization landscape of pver-parameterized shallow neural networks. arXiv preprint arXiv: (e07:077999 2017.
Daniel Soudry and Yair Carmon. No bad local minima: Data independent training error guarantees for multi- layer neural networks, arXiv preprint arXiv:1605.00 08361, 2016.
Ju Sun, Qing Qu, and John Wright. Complete dictionary recovery over the sphere. In 2015 International Conference on Sampling Theory and Applications (SampTA), pp. 407-410. IEFF, 2015.
12

---

Yuandong Tian. An analytical formula of population gradient for two-layered relu network and its applications convergence and critical point analysis. arXiv preprint arXiv:1703, 005600 2017.
Thomas Unterthiner, Bernhard Nessler, Calvin Seward, Günter Klambauer, Martin Heusel, Hubert Ramsauer, and Sepp Hochreiter, Coulomb gans: Provably optimal nash equilibria via potential fields. arXiv preprint arXiv: 178.8/9708.888/9 2017.
Santosh Vempala and John Wilmes. Polynomial convergence of gradient descent for training mee-hidde--layr neural networks. arXiv preprint arXiv:1805.022: 02277777.. 2018.
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 European Conference on Computer Vision (ECCV), pp. 0-0, 2018.
Bo Xie, Yingyu Liang, and Le Song. Diversity leads to generalization in neural networks. arXiv preprint Arxiv:161..0313.. 2016.
Gilad Ychudai and Ohad Shamir. On the power and limitations random features for understanding neural networks. arXiv preprint arXiv: 2019.
Xiao Zhang. Yaodong Yu, Lingxiao Wang. and Quanquan Gu. Learning one-hidden-layer relu networks via gradient descent. arXiv preprint arXiv:1806.07800 pp. 3262-3271, 2018.
Miao Zheng, Jiajun Bu, Chun Chen, Can Wang. Lijun Zhang, Guang Qiu, and Deng Cai. Graph regularized sparse coding for image representation. IEEE transactions on image processing. 20K5):1327- -136, 2010.
Kai Zhong, Zhao Song, Prateck Jain, Peter I. Bartlett, and Inderjit $ Dhillon. Recovery guarantees for one- hidden-layer neural networks. arXiv preprint arXiv: 1706.03175, 2017.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes parameterized deep relu networks. arXiv preprint arXiv:1811.0880 2018
13


Reviews:
[{"review_id": "s3uuJuJL7GK", "reviewer": "Reviewer_2F3d", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "The paper proposes the distribution structure called “forward super-resolution” (forward super-resolution assumes that for image resolution at level $L$ is represented by $G_l*W_l$, where $G_l$ is hidden neuron at layer l of neural network $G$ (with RELU activation) and $W_l$ is certain matrix), which is hierarchically generated, which can be learnt effectively by GAN using stochastic gradient de- scent ascent (SGDA) under certain conditions. In particular, to learn the forward-super resolution, the authors assumes that the true distribution of layers in neural network G follows sparse structure and “not-too-positively correlated” at patch level. With this assumption, the authors provide the theoretical capability and the convergence of the generator and design the learning algorithms for it.  The algorithm breaks the learning into multiple parts (GAN OutputLayer, GAN FirstHidden, GAN FowardSuperResolution) and show how the training of each part is formed and converged. The main idea of the convergence theory showing the generator will learn to match the moments of the true distribution. ", "summary_of_the_review": "Overall, the high-level idea is interesting and novel to me. Indeed, empirically looks like learning via hierarchical approach in GAN seems more effective as shown in some existing works. However, this is too dense theoretical paper up to 71 pages, challenging for me to verify the correctness of the proofs in limited time. I have a few questions regarding the empirical evidence and main assumptions that hopefully the authors can clarify in the rebuttal. ", "strength_and_weaknesses": "Strengths:\n\n1. The theory about the “forward super-resolution” is new to me.\n\n2. The few proofs in the paper looks correct, but most of them cannot be verified due to the limited time. \n\n3. The new learning algorithm for GAN with the theoretical supports. \n\nWeaknesses:\n\n1. The paper aims to discuss assumption “forward super-resolution” holds in practice and show the proposed underlying training mechanism simulates the actual learning process of GANs on real-world problems. However, excepts some examples which was developed in some existing GANs, I cannot find anywhere in the paper. Can the author point to where this is discussed? Seems to me if most of them only with discussion rather than theoretical or empirical evidence which is not convincing to me enough. \n\n2. Moreover, can the authors details how to design the empirical experiments for Figs 2, 3, 4?  In Fig. 3, it is not convincing to me that the learned of network is really sparse (it may be depends on how we design sparsity) but to me it is more on the long-tail distribution since most of columns have the value. Also, the sparsity assumption may depend on the network capacity and how much knowledge of the data needs to be encoded into the networks. For example, can the authors reduce the network at different sizes to see whether it still learn the sparse structure?\n\n3. One suggestion is designing the toy examples to show the learning capability of proposed algorithm as claimed by the authors it is natural in real-world, designing such toy examples may not difficult?", "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": "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": "aO75wAHtdQ0", "reviewer": "Reviewer_okYU", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "The paper provides a theoretical model of *how* GANs might learn to generate images. The paper defers most of the work to the 71 page appendix, but if I understood it correctly, they model GAN training as iteratively learning \"linear\" (as in generalised linear model,i.e. including a single nonlinearity ala logistic regression) discriminator/generator layers on objectives at the given resolution, assuming that such a generator can generate the data (with additional sparse basis, non concentration and a couple of other assumptions).\n\nThe main theorem is a high probability statement about the trained generator being able to match the true generator (up to a transformation by a column orthonormal basis in the latent state) with high probability.", "summary_of_the_review": "I applaud the authors for what attempting to fit what appears to be a very good 80 page paper into a 13 page conference format, but I am unsure whether it was a good idea. I lean towards a marginal accept because I could not do the required level of verification to stand behind the results stronger and I find a paper which relies almost exclusively on the appendix for verification to be problematic. Again, a journal venue or conference with different constraints might have fit better. However, what I could verify seems correct and I understand the challenge of presenting a work as involved  as this. Hence, marginal accept.", "strength_and_weaknesses": "Strengths of the paper:\n\n- while the appendix is quite overwhelming in size, it *is* quite clearly written and legible. Overall, I applaud the authors for attempting to make such an involved work readable within the constraints of ICLR\n- I could not verify the proofs in detail, but they seem reasonable to me as far as I could check. If it holds, the work could be the opening gate to a theory of GANs (albeit a very specific type which reminds me a lot of diffusion models in small local changes over multiple layers and relying on supervision in what will be latent stages)\n\n\nWeaknesses\n\n- the paper is very ambitious with just how much it is trying to present and I'm not sure it is the best way of doing things. A journal submission might have been a better fit, alternatively putting more emphasis on the interpretation and leaning *even more* on the already exhaustive appendix might have been a better move. However, it is difficult to thread this needle, and despite the reviewer guidance I cannot give actionable feedback on *how* to do this rewrite. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "WOlstqfiA8", "reviewer": "Reviewer_EgRr", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "The paper presents a theoretical analysis of GANs and shows how GANs can learn hierarchically generated distributions. Here hierarchical generation means that the distribution comes from an unknown generator that follows a forward super-resolution structure where each successive layer gives a higher resolution image (somewhat similar to progressively growing GANs). It is further assumed the learned generator also follows a similar structure. A learning algorithm is then presented using 3 types of discriminators (for the output layers, for the first hidden layers, and for remaining hidden layers) and it is shown that the generator trained using this algorithm learns the target distribution.", "summary_of_the_review": "Overall, this paper presents an interesting theoretical analysis of GANs. However, there is a clear disparity between the model and learning algorithm studied in this paper vs. what's used in practice. Therefore, I am unsure about the significance of the results. It also appears that 9 pages are too few to properly explain the ideas presented in this work and a long-form journal submission may be a better choice. \n\nNote: I do not have background in learning theory, so I am unable to provide an in-depth review of the analysis and proofs.", "strength_and_weaknesses": "[Strengths]\n* The paper presents an interesting analysis of a version of GANs.\n* The paper is well-written (given the space limit) and the authors have made attempts to give intuitions and visuals to explain the results.\n\n[Weaknesses]\n* The analysis is done on a model/network that is not close to practice. Specifically, the discriminator is awkwardly split up into 3 parts which is not seen in practice, as the authors have themselves acknowledged. Some kind of empirical justification for the proposed learning algorithm is also missing.\n* Overall, it seems like a conference paper (with a page limit) is not enough to properly explains the ideas presented in this work. The frequent references to the appendix break the reading flow. Therefore, in my subjective opinion, this work is more suitable for a longer format journal. ", "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": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Accept: poster