Size-Noise Tradeoffs in Generative Networks
This paper investigates the ability of generative networks to convert their input noise distributions into other distributions. Firstly, we demonstrate a construction that allows ReLU networks to increase the dimensionality of their noise distribution by implementing a "space-filling" function based on iterated tent maps. We show this construction is optimal by analyzing the number of affine pieces in functions computed by multivariate ReLU networks. Secondly, we provide efficient ways (using polylog(1/ ) nodes) for networks to pass between univariate uniform and normal distributions, using a Taylor series approximation and a binary search gadget for computing function inverses. Lastly, we indicate how high dimensional distributions can be efficiently transformed into low dimensional distributions.
This paper examines the approximation of uniform and normal distributions using neural networks provided with a uniform or normal distribution at its input. The paper's main contributions are   1. the upper- and lower-bound for approximating higher dimensional uniform distributions with a lower dimensional one. The main idea is the use of an affine space-filling curve, which has been examined in a similar context before. 2. providing a neural network transformation to go from a uniform distribution to a normal and vice-versa.  Overall, the paper is a pleasure to read and tackles the important question of the required size/depth required for a neural network to approximate a given distribution.  Some minor notes:  Section 2.2 is not an easy read without delving into the appendix. Perhaps some intuition can be provided for the statement in line 138. Lines 145-148 are also a bit terse. An added explanation of how the lower and upper-bound compare (as is done in line 33 of the intro) would make the strength of this section more apparent.  Section 4 is somewhat trivial as it is stated. I would suggest adding a few sentences making the comparison with the result of Section 3.2 more explicit, so that the added benefit of more dimensions of uniform noise to approx. a normal becomes clear.  If more space is required, perhaps consider reducing the size of Figure 1 or placing proof of Th. 11 in the appendix.  Some typos:  l 53 This idea [h]as l 104 How easy [is it] to l 190 good behavior 
		
	
		
Reviewer 3
This paper is a joy to read. It addresses question whether GANs can map between simpler standard distributions and how well, and the role of width and depth of the neural net in the approximation. The paper is very well organized. Deep down, the argument boils down to that the ReLU neural network can divide the input space into small convex open subsets that are locally uniform and then map them  (via affine transformations) to another small locally uniform set of the output. The measure remains the same after the mapping. The dificulty is: how small should these sets be? And how well can a given neural network do this task? I think the authors did a great job explaining the task.  It was disapointing that there was no empirical results trying to validate the bounds. I have a personal bias against papers with theoretical bounds that show no empirical evidence of their results. Specifically in this case, where the examples are simple and concrete.              Please also cite Egoroff’s theorem [Folland, 2013, Theorem 2.33] as Egorov's theorem [Kolmogorov and Fomin, 1975, pp. 290, Theorem 12]. The different spellings of the name tend to confuse readers familiar only with Kolmogorov's book. A. N. Kolmogorov and S. V. Fomin. Introductory Real Analysis. Dover, 1975.                The statement that "It stands to reason that larger neural networks or networks with more noise given as input can represent more". As R (real set) has the same cardinality as R^n, n finite, the statement seems to be connected to a notion of smoothness in the measure. It reads a little odd and a small discussion on the reason why the input needs to be high-dimensional noise could help.  ---------  Read the rebuttal and the other two reviews. This is a good contribution.