Representational aspects of depth and conditioning in normalizing flows
Authors: Frederic Koehler
Viraj Mehta
Andrej Risteski
Venue:  (2021)
Keywords: normalizing flows
representational power
conditioning
depth
theory

Abstract: Normalizing flows are among the most popular paradigms in generative modeling, especially for images, primarily because we can efficiently evaluate the likelihood of a data point. This is desirable both for evaluating the fit of a model, and for ease of training, as maximizing the likelihood can be done by gradient descent. However, training normalizing flows comes with difficulties as well: models which produce good samples typically need to be extremely deep -- which comes with accompanying vanishing/exploding gradient problems. A very related problem is that they are often poorly \emph{conditioned}: since they are parametrized as invertible maps from $\mathbb{R}^d \to \mathbb{R}^d$, and typical training data like images intuitively is lower-dimensional, the learned maps often have Jacobians that are close to being singular. 

In our paper, we tackle representational aspects around depth and conditioning of normalizing flows---both for general invertible architectures, and for a particular common architecture---affine couplings. 

For general invertible architectures, we prove that invertibility comes at a cost in terms of depth: we show examples where a much deeper normalizing flow model may need to be used to match the performance of a non-invertible generator. 

For affine couplings, we first show that the choice of partitions isn't a likely bottleneck for depth: we show that any invertible linear map (and hence a permutation) can be simulated by a constant number of affine coupling layers, using a fixed partition. This shows that the extra flexibility conferred by 1x1 convolution layers, as in GLOW, can in principle be simulated by increasing the size by a constant factor. Next, in terms of conditioning, we show that affine couplings are universal approximators -- provided the Jacobian of the model is allowed to be close to singular. We furthermore empirically explore the benefit of different kinds of padding -- a common strategy for improving conditioning.

Under review as a conference paper at ICLR 2021
REPRESENTATIONAL ASPECTS OF DEPTH AND CONDI- TIONING IN NORMALIZING FLOWS
Anonymous authors Paper under double-blind review
ABSTRACT
Normalizing flows are among the most popular paradigms in generative modeling, especially for images, primarily because we can efficiently evaluate the likelihood of data point. This is desirable both for evaluating the fit of model. and for ease of training, as maximizing the likelihood can be done by gradient descent. However, training normalizing flows comes with difficulties as well: models which produce good samples typically need to be extremely deep which comes with accompanying vanishing/exploding gradient problems. A very related problem is that they are often poorly conditioned: since they are parametrized as invertible maps from R + Rd, and typical training data like images intuitively is lower- dimensional, the learned maps often have Jacobians that are close to being singular.
In our paper, we tackle representational aspects around depth and conditioning of normalizing blows-both for general invertible architectures, and for a particular common architecture- affine couplings.
For general invertible architectures, we prove that invertibility comes at cost in terms of depth: we show examples where a much deeper normalizing flow model may need to be used to match the performance of a non-invertible generator.
For affine couplings, we first show that the choice of partitions isn't likely bottle- neck for depth: we show that any invertible linear map (and hence a permutation) can be simulated by constant number of affine coupling layers, using fixed partition. This shows that the extra flexibility conferred by 1x1 convolution layers, as in GLOWW can in principle simulated by increasing the size by a constant factor. Next, in terms of conditioning, approximators provided the Jacobian of the model allowed to be close to singu- lar. We furthermore empirically explore the benefit of different kinds of padding a common strategy for improving conditioning.
show that affine couplings
universal
INTRODUCTION
Deep generative models of the lynchpins of unsupervised learning, underlying tasks spanning distribution learning, feature extraction and transfer learning. Parametric familics of neutol-network based models have been improved to the point of being able model complex distributions like images of human faces. One paradigm that has received a lot attention normalizing flows, which model distributions as pushforwards of standard Gaussian (or other simple distribution) through an invertible neural network G. Thus, the likelihood has an explicit form via the change of variables formula using the Jacobian of G. Training normalizing flows is challenging due to a couple of main issues. Empirically. these models seem to require a much larger size than other generative models (e.g. GANs) and most notably, much larger depth. This makes training challenging due to vanishing/exploding gradients. A very related problem is conditioning, more precisely the smallest singular value of the forward map G. It's intuitively clear that natural images will have low-dimensional structure, thus close-to pose-to-singg to-singular G might be needed. On the other hand, the laange-of-varialle formula involves the determinant of the Jacobian of G-1, which grows larger the more singular G is.
While recently, the universal approximation power of various types of invertible architectures has been studied (Dupont et al., 2019: Huang al. (020) if the input is padded with sufficiently large number of all-O coordinates, precise quantification of the cost of invertibility in terms of the depth required and the conditioning of the model has not been fleshed out.

---

Under review as a conference paper at ICLR 2021
In this paper, study both mathematically and empirically representational aspects of depth and conditioning in normalizing flows and answer several fundamental questions.
OVERVIEW OF RESULTS
2.1 RESULTS ABOUT GENERAL ARCHITECTURES
In order to guarantee that the network is invertible, normalizing flow models place significant restrictions on the architecture of the model. The most basic question we can ask is how this restriction affects the expressive power of the model in particular, how much the depth must increase to compensate.
More precisely, we ask:
Question 1: is there a distribution over I which can be written as the pushforward of a Gaussian through small, shallow generator, which cannot be approximated by the pushforward of Gaussian through a small. shallow layerwise invertible neural network?
Given that there is great latitude in terms of the choice of layer architecture, while keeping the network invertible, the most general way to pose this question is to require each layer to be a function of p parameters i.e. f = f1 foo--.off where denotes function composition and each fi Rdd IRd is an invertible function specified by a vector 0: E IR" of parameters. This framing is extremely general: for instance it includes layerwise invertible feedforward networks which fi = 2d (A + b.). is invertible, A; E Rdxd is invertible, 0; (Ai, b;) and díd + 1). It also includes popular architectures based on affine coupling blocks (e.g. Dinh et al. (2014) 2016); Kingma & Dhariwal (2018) where each fi has the form ( F[d SC which we revisit in more detail in the following subsection.
( Ii,), O ( h,(xs))) for some
We answer this question in the affirmative: namely, we show for any ls that there is a distribution over Rd which can be expressed as the pushforward of network with depth O(1) and size O(k) that cannot be (even very approximately) expressed as the pushforward of a Gaussian through a Lipschitz layerwise invertible network of depth smaller than k/p.
Towards formally stating the result, let 0 (f1..... 0τ) e C Rd be the vector of all parameters (e.g. weights, biases) in the network, where 8, E IR" are the parameters that correspond to layer i, and let Rdd d denote the resulting function. Define R so that O is contained in the Euclidean ball of radius R.
We say the family fo is I--Lipschitz with respect its parameters and imputs, if
v0.6' ④ 1B llf for (a:) - L l'll
and Va, E (z) fo(W)l < L| - y|1 We will discuss the reasonable range for L in terms of the weights after the Theorem statement. We show ?
Theorem 1. For any k exp(o(d)), L large and any 7 > 0 there exists neural network g Rd+1 - R2d with O(k) parameters and depth O(1), s.t. for any family {fa. 8 θ} of layerwise invertible networks that are L-Lipschitz with respect to its parameters and inputs, have parameters per layer and depth at most k/p we have
exp(o(d)) (d)), -
R= exp(o(d)), we have that for d sufficiently
AO O, W.(()
10y2d
Furthermore, for all 0 O, KI((Jo) #N (WN) 2 1/10 and KILgHN, (fo)#N) 2
10-2d 12-
First, note that while the number of parameters in both networks is comparable (i.e. it's O(k)), the invertible network is deeper, which usually is accompanied with algorithmic difficulties for training, due vanishing and exploding gradients. For layerwise invertible generators, if we assume that the nonlincarity o is - 1-Lipschitz and each matrix the network has operator norm at most M,
Remark 1:
Note for architectures having trainable biases in the input layer, these two notions of Lipschitzness should be expected to behave similarly.
"In this Theorem and throughout, we use the standard asymptotic notation f(d) = o(g(d) to indicate f(d)
that lim sup, g(a) = 0. For example, the assumption k, L, R = exp(o(d)) means that for any sequence max(log log log R,) the result holds true.
(ha; Ted, Ra) such that lim 4-p
2

---

Under review as a conference paper at ICLR 2021
then depth network will have L = OM and p ( For affine coupling network with g. h parameterized by H-layer networks with p/2 parameters each, 1-Lipschitz activations and weights bounded by M above, we would similarly have L = ((M*)).
Remark 2: We make a couple comments on the "hard" distribution g we construct, as well as the meaning of the parameter y and how interpret the various lower bounds in the different metrics. The distribution g for a given Y will in fact be close to a mixture of is Gaussians, each with mean on the sphere of radius 10y²d and covariance matrix 22Id. Ld. Thus this distribution has most of it's mass in sphere of radius (d) -so the Wasserstein guarantee gives close to a trivial approximation for g- The KI divergence bounds derived by so-called transport inequalities between KI. and Wasserstein for subgaussian distributions Bobkov & Götze (199).. The discrepancy between the two KL divergences comes from the fact that the functions 9, fe may have different Lipschitz constants, hence the tails of 9#N and f#N behave differently. In fact, if the function fo had the same Lipschitz constant as g, both KL lower bounds would be on the order of a constant.
2.2 RESULTS ABOUT AFFINE COUPLING ARCHITECTURES
Next, we prove several results for a particularly common normalizing flow architectures: those based on affine coupling layers (Dinh et al. 2014 2016 Kingma & Dhariwal 2018). The appeal of these architecture comes from training effecincy. Althouhh layerwise invertible neural networks (i.e. networks for which each layer consists of an invertible matrix and invertible pointwise nonlinearity) seem like natural choice, in practice these models have several disadvantages: for example, computing the determinant of the Jacobian is expensive unless the weight matrices restricted.
Consequently, it's typical for the transformations in a flow network to be constrained in a manner that allows for efficient computation of the Jacobian determinant. The most common building block is an affine coupling block, originally proposed by Dinh et al. (2014; 2016). A coupling block partitions the coordinates [d] into two parts: S and [d] S, for subset S with [S] containing around half the coordinates of d. The transformation then has the form:
Definition 1. An affine coupling block is a map f Rd Rd s.t. f(zs, (as. 2 sA.s ? s(rs) + f(xs))
Of course, the modeling power will be severely constrained if the coordinates in S never change: so typically, flow models either change the set in a fixed or learned way (e.g. alternating between different partitions of the channel in Dinh et al. (2016) applying a learned permutation in Kingma & Dhariwal 2018)). Of course, a permutation is a discrete object, so difficult to learn in a differentiable manner Kingma & Dhariwal (2018) simply learns invertible linear function (i.e. 1x1 convolution) as a differentiation -riendly relaxation thereof.
2.2.1 THE EFFECT OF CHOICE OF PARTITION ON DEPTH
The first question about affine couplings we ask how much saving in terms of the depth of the network can one hope to gain from using learned partitions (ala GLOW) as compared to fixed partition. More precisely:
Can models like Glow (Kingma & Dhariwal 2018) be simulated by sequence of affine blocks with a fixed partition without increasing the depth by much?
Question 2:
We answer this question in the affirmative at least for equally sized partitions (which is what is typically used in practice). We show the following surprising fact: consider an arbitrary partition (S, [2d] S) of [2d], such that S satisfies JS| d, for d E N. Then for any invertible matrix E R 2dxx2d the linear map T R2d - 2ddd can be exactly represented by a composition of ((1) affine coupling layers that are linear, namely have the form L, x(24)15) (æs, + or (, 2(24).s) (C,a + D, x(2)))s)) for matrices A,, A,, C, D; Bddd s.t. each B, C diagonal. For convenience of notation, without loss of generality let S [d] Then, each D,
I
of the layers L; is matrix of the form partitioned into blocks of size d.
where the rows and columns
A
B
0
1
With this notation in place, we show the following theorem:
Note, our theorem applies exponentially large Lipschitz constants.
3

---

Under review as a conference paper at ICLR 2021
Theorem 2. For all d 2 there exists k < 24 such that for any invertible T R with der(T) > 0, there exist matrices A,, Dj E Raaxd and diagonal matrices B5, Ci Rdxd for forall E [k] such that
0 B.
C:
D I
T
A
Note that the condition det( is required, since affine coupling networks are always orientation- preserving. Adding one diagonal layer with negative signs suffices to model general matrices. In particular, since permutation matrices are invertible, this means that any applications of permutations to achieve different partition of the inputs (e.g. like in Glow (Kingma & Dhariwal 2018) can in principle be represented as a composition of not-too-many affine coupling layers, indicating that the flexibility in the choice of partition is not the representational bottleneck.
It's a reasonable to ask how optimal the lo S 24 bound is we supplement our upper bound with lower bound, namely that & 2 3. This is surprising naive parameter counting would suggest k = might work. Namely, we show:
Theorem 3. For all 2 4 and S 2, there exists an invertible T E Id2dxxd with der(T) > 0, s.t.
for all A,, D; E [Rdxd and for all diagonal matrices Bi, C₁ E 20
IRddd i E [K] it holds that
C 0
D I
T
A
B
Beyond the relevance of this result in the context of how important the choice of partitions is, it also shows a lower bound on the depth for an equal number of nonlinear afline coupling layers (even with quite complex functions and in each layer) - since a nonlinear network can always be linearized about (smooth) point to give linear network with the same number of layers. In other words, studying linear affine coupling networks lets us prove depth lower boundldepth separation for nonlinear networks for free.
Finally, in Section 5.3 we include an empirical investigation of our theoretical results on synthetic data, by fitting random linear functions of varying dimensionality with linear affine networks of varying depths in order to see the required number of layers. The results there suggest that the constant in the upper bound is quite loose and the correct value for k is likely closer to the lower bound at least for random matrices.
2.2.2 UNIVERSAL APPROXIMATION WITH ILL- ALL-CONDTTIONED AFFINE COUPLING NETWORKS
Finally, turn to universal approximation and the close ties to conditioning. Namely, recent work (Theorem of Huang et al. (2020) showed that deep affine coupling networks are universal approximators if we allow the traming data to be padded with sufficiently many zeros. While zero padding is convenient for their analysis (in fact, similar proofs have appeared for other invertible architectures like Augmented Neural ODEs (Zhang et al.)). in practice models trained zero-padded data often perform poorly (see Appendix C
In fact, we show that neither padding depth is necessary representationaally: shallow models without zero padding are already universal approximators in Wasserstein.
Theorem 4 (Universal approximation without padding). Suppose that P is the standard Gaussian measure in R with n even and Q a distribution on I with bounded support and absolutely continuous with respect to the Lebesgue measure. Then for any >> 0, there exists depth-3 affine coupling network g. with maps s, t represented by feedforward ReLU networks such that W2(g P.Q)== e.
Remark 1: A shared caveat of the universality construction in Theorem with the construction in Huang et al. (2020) is that the resulting network is poorly conditioned. In the case of the construction in Huang et al. (2020), this is obvious because they pad the d-dimensional training data with d additional zeros, and a network that takes as input a Gaussian distribution 2d (i.e. has full support)
and outputs data d-dimensional manifold (the space of zero padded data) must have singular
4

---

Under review as a conference paper at ICLR 2021
Jacobian almost everywhere In the case of Theorem 4 the condition number of the network blows up at least as quickly as 1/c as we take the approximation error e + O, so this network is also ill-conditioned if we aiming for very accurate upproximation.
Remark 2: Based on Theorem the condition number blowup of either the Jacobian or the Hessian is necessary for a shallow model to be universal, even when approximating cell-conditioned linear maps (see Remark (7). The network constructed in Theorem is also consistent with the lower bound from Theorem [ because the network we construct in Theorem 4 is highly non-Lipschitz and uses many parameters per layer.
3 RELATED WORK
On the empirical side, flow models were first popularized by Dinh et al. (2014), who introduce the NICE model and the idea of parametrizing a distribution as a sequence of transformations with triangular Jacobians, that maximum likelihood training is tractable. Quickly thereafter, Dinh ct al. (2016) improved the affine coupling block architecture they introduced to allow non-volume- preserving (NVP) transformations, Papamakarios et al. (2017) introduced an autoregressive version, and finally Kingma& & Dhariwal (2018) introduced 1x convolutions in the architecture, which they view as relaxations of permutation
allowing learned partitions for the affine blocks. Subsequently, there have been variants on these ideas: (Grathwohl et al. 2018 Dupont et al., 2019 Behrrann al., 2018) viewed these models as discretizations of ODEs and introduced ways to approximate determinants of non- -onttriang Jacobians, though these models still don't 't scale beyond datasets the size of CIFARIO. The conditionin//iveetilliii of trained models was experimentally studied in (Behrmann et al.) 2019), along with some "adversarial vulnerabilities" of the conditioning. Mathematically understanding the relative representational power and statistical/algorthnni implica- tions thereof for different types of generative models is still however a very poorly understood and nascent area of study.
Most closely related to our results are the recent works of Huang et al. (2020) and Zhang et al. Both prove universal approximation results for invertible architectures (the former affine couplings, the latter neural ODEs) if the input is allowed to be padded with zeroes. As already expounded upon in the previous sections our results prove universal approximation even without padding, but we focus on more fine-grained implications to depth and conditioning of the learned model. Another work (Kong& & Chaudhuri] 2020) studies the representational power of Sylvester and Householder flows, normalizing flow architectures which are quite different from affine coupling networks. In particular, they prove a depth lower bound for local planar flows with bounded weights; for planar flows, our general Theorem can also be applied, but the resulting lower bound instances are very different (ours targets mulumodality, theirs targets tail behavior).
More generally, there are various classical results that show a particular family of generative models can closely approximate most sufficiently regular distributions over some domain. Some examples are standard results for mixture models with very mild conditions on the component distribution (e.g. Gaussians, see (Everiti 2014)); Restricted Boltzmann Machines and Deep Belief Networks (Montúfar et al. 2011 Montufar Ay 201T); GANs (Bailey & Telgarsky 2018).
4 PROOF SKETCH OF THEOREM 1: DEPTH LOWER BOUNDS ON INVERTIBLE MODELS
In this section we sketch the proof of Theorem 1 The intuition behind the k/p bound on the depth relies on parameter counting: a depth k/p invertible network will have k parameters in total (p per layer) is the size of the network we are trying to represent. Of course, the difficulty is that we need more than fe. g simply not being identical: we need a quantitative bound in various probability metrics.
The proof will proceed as follows. First, we will exhibit a large family of distributions (of size exp(kd)), s.t. each pair of these distributions has large pairwise Wasserstein distance between them. Moreover, each distribution in this family will be approximately expressible as the wushforward of
Alternatively, we could feed a degenerate Gaussian supported on d-dimensional subspace into the network as input, but there is no way to train such model using maximum-likellhoog training, since the prior is degenerate.
5

---

Under review as a conference paper at ICLR 2021
the Gaussian through small neural network. Since the family of distributions will have large pairwise Wasserstein distance, by the triangle inequality, no other distribution can be close to two distinct members of the family.
Second, we can count the number of "approximately distinct" invertible networks of depth I: each layer is described by p weights, hence there are ip parameters in total. The Lipschitzness of the neural network in terms of its parameters then allows to argue about discretizations of the weights.
Formally, show the following lemma:
Lemma 1 (Large family of well-separated distributions), For every k = (eeppp(d)) for d sufficiently large and y there exists a family D of distributions, s.t. [D] 2 exp(kd/20) and:
1. Each distribution p E D is mixture of l Gaussians with means (pili ||:ll22 207 d and covariance x² La-
Vp 'D and Vc > O, we have Wi(p, (#N) S 6 ffrr a neural network g with at most ( parameters
For any p.p' DD, Wi(P.p') 2 20
The proof of this lemma will rely on two ideas: first, we will show that there is a family of distributions consisting of mixtures of Gaussians with & components - s.t. each pair of members of this family is far in W1 distance, and each member in the family can be approximated by the pushforward of network of size (k)).
The reason for choosing mixtures is that it's easy to lower bound the Wasserstein distance between two mixtures with equal weights and covariance matrices in terms of the distances between the means. We show this Lemma in Appendix A
Given this, to design a family of mixtures of Gaussians with large pairwise Wasserstein distance, it suffices to construct large family of k-tuples for the means, s.t. for each pair of k-tuples (fp,)) ) (p:))m)) there exists a set S S [k],]s] 2 k/10, s.t. Vi E S, mimiggggs || /; 20. We do this by leveraging ideas from coding theory (the Gilbert- Varbbrt--arshmmov bound Gilbert (1952); ; Varshamov 1957)). Namely, we first pick set of exp(I((d) vectors of norm 20y²d, each pair of which has a large distance; second, we pick a large number (exp of k-tuples from this set at random, and show with high probability, no pair of tuples intersect in more than k/10 elements. This is subsumed by Lemmas ( in Section A
Gilbert
To handle part 2 of Lemma 1
also show that mixture of & Gaussians can be approximated the pushforward of a Gaussian through a network of size Ok)). The idea is rather simple: the network will use sample from standard Gaussian in Rd+1, We will subsequently use the first coordinate to implement "mask" that most of the time masks all but one randomly chosen coordinate in [&]. The remaining coordinates are used to produce sample from each of the components in the Gaussian, and the mask is used to select only one of them. For details, see Section A
With this lemma in hand, we finish the Wasserstein lower bound with a standard epsilon- net argument, using the parameter Lipschitzness of the invertible networks by showing the number of "different"
invertible neural networks is on the order of O (LR))") This is Lemma 8 in Appendix A The proof of Theorem 0 can then be finished by triangle inequality: since the family of distributions has large Wasserstein distance, by the triangle incquality, no other distribution can be close to two distinct members of the family. Finally, KL divergence bounds can be derived from the Bobkov-Götze inequality Bobkov& & Götze (1999), which lower bounds KL divergence by the squared Wasserstein distance. The details are in Section
PROOF SKETCH OF THEOREMS AND 3 SIMULATING LINEAR FUNCTIONS WITH AFFINE COUPLINGS
In this section, we will prove Theorems 3 and 2 Before proceeding to the proofs, we will introduce
bit of helpful notation. We let GL+ (2d, R.) denote the group of 2d x 2d matrices with positive
'The size of g doesn't indeed depend The weights in the networks will simply grow as becomes small.

---

Under review as a conference paper at ICLR 2021
determinant (see Artin (2011) ) for reference group theory). The lower triangular linear affine coupling layers are the subgroup Ag C GL (2d, R) of the form
{
0 B
Ac
A E Rddd B is diagonal with positive entries
and likewise the upper triangular linear affine coupling layers are the subgroup Au C Gl.+t2d, of the form
Au = {[00
D P DE gaxd C' diagonal with positive entries
Finally, define A= = Ag U Au C (2d, under multiplication. Let A denote the kth power of A, i.c. all elements the form 01 ... ag for a, E A.
R). This set is not subgroup because it is not closed
5.1
UPPER BOUND
The main result of this section is the following:
Theorem (Restatement Theorem 2}. There exists an absolute constant K S 47 such that for any d 2 1, GL (2d, R) = A
In other words, any linear map with positive determinant serrentation-ppeservinng can be imple- mented using bounded number of linear affine coupling layers. Note that there is difference in a factor of two between the counting of layers in the statement of Theorem 2 and the counting of matrices in Theorem because each layer is composed of two matrices.
In group-theoretic language, this says that A generates GL+ G2d, I)) and furthermore the diameter of the corresponding (uncountably infinite) Cayley graph is upper bounded by constant independent of d. The proof relies on the following two structural results. The first one is about representing permutation matrices, up sign, using a constant number of linear affine coupling layers:
Lemma 2. For any permulation matrix P E R24x2d, there exists P E A with P.yl IPig for all i.j.
The second one proves how to represent using a constant number of linear affine couplings matrices with special eigenvalue structure:
Lemma 3. Let be an arbitrary invertible x d matrix with distinct real eigenvalues and S be a d x d lower triangular matrix with the same eigenvalues M-1 Then
M
EAA
Given these Lemmas, we briefly describe the strategy to prove Theorem 5 Every matrix has an LUP factorization Horn & Johnson (2012) into lower-triangular, upper-triangular, and permutation matrix. Lemma 2 takes care of the permutation part, what remains is building an arbitrary lower/upper triangular matrix; because the eigenvalues loier-triangular matrices are explicit,
careful argument allows us to reduce this to Lemma 3 All the proofs are in Section B
5.2 LOWER BOUND
We proceed to the lower bound. Note, a simple parameter counting argument shows that for sufficienlly large d, at least four affine coupling layers needed to implement arbitrary linear map (each affine coupling layer has only d² + d parameters whereas GL,, (2d, R) is a Lie group of dimension 4d2). Perhaps surprisingly. it turns out that four affine coupling layers do suffice to construct an arbitrary linear map. We prove this in the following Theorem.
Theorem (Restatement of Theorem 3. For 4, A is a proper subset of GL, (2d, R). other words, there exists matrix T E GL,,
CL,(2dd, (2d, I) which is not in A3.
Again, this translates to the result Theorem because each layer corresponds to two matrices - so this shows two layers are not enough to get arbitrary matrices. The key observation is that matrices in AgArAgAA satisfy a strong algebraic invariant which is not true of arbitrary matrices. This invariant can be expressed in terms of the Schur complement Zhang (2006):
7

---

Under review as a conference paper at ICLR 2021
Y
Lemma 4. Suppose that T
an invertible 2d 2d matrix and suppose there exist
Z
W
matrices A, E E Bddxd D.H
H.H& E TRdxd and diagonal matrices B, F E Raxd C,G E Rdxd such that
C
DILE
D
D
I
0 P
G
H I
T
A
B
0
I
Then the Schur complement T/X W Zx-ly similar to X-1C: more precisely, if
Z - AX then T/X- =UX- UX-
The proof of this Lemma is presented in Appendix as well as the resulting proof of Theorem We remark that the argument in the proof is actually fairly general: it can be shown, for example, that for a random choice of X and W from the Ginibre ensemble, that T cannot typically expressed in A₁. So there significant restrictions on what matrices can be expressed even four affine coupling layers.
Remark 7 (Connection Universal Approximation). As mentioned earlier, this lower bound shows that the map computed by general 4-layer affine coupling networks is quite restricted in its local behavior (it's Jacobian cannot be arbitrary). This implies that smooth 4-layer affine coupling networks, where smooth means the Hessian (of each coordinate of the output) is bounded in spectral norm, cannot universal function approximators as they cannot even approximate some linear maps. In contrast, if we allow the computed function to be very jagged then three layers are universal (see Theorem
5.3 EXPERIMENTAL RESULTS
We also verify the bounds from this section. At least on randomly chosen matrices, the correct bound is closer to the lower bound. Precisely, we generate (synthetic) training data of the form Az, where = ~ No0, I) for a fixed d d square matrix A with random standard Gaussian entries and train a linear affine coupling network with
2, 4, 8, 16 layers by minimizing the loss Ez~N(o,1) [(ff(()) A= We are training this "supervised" regression loss instead of the standard unsupervised likelihood loss to minimize algorithmic (training) effects as the theorems are focusing on the representational aspects. The results for d = 16 are shown in Figure [ and more details are in Section[[] To test a different distribution other than the Gaussian ensemble, we also generated random Toeplitz matrices with constant diagonals by sampling the value for each diagonal from standard Gaussian and performed the same regression experiments. We found the same dependence on number of layers but overall higher eтror, suggesting that that this distribution is slightly 'harder'. We provide results in Section[[ C We also regress a nonlinear RealNVP architecture on the same problems and see similar increase representational power though the nonlinear models seem to require more training to reach good performance.
Additional Remarks Finally, we also note that there are some surprisingly simple functions that cannot be exactly implemented by finite affine coupling network. For instance, entrywise tanh function (i.e. an entrywise nonlinearity) cannot be exactly represented by any finite affine coupling network, regardless of the nonlinearity used. Details of this are in Appendix
6 PROOF SKETCH OF THEOREM 4 UNIVERSAL APPROXIMATION WITH ILL-CONDITIONED AFFINE COUPLING NETWORKS
In this section, we sketch the proof of Theorem to show how to approximate distribution in I using three layers of affine coupling networks, where the dimension = 2d is even. The partition in the affine coupling network is between the first coordinates and second d coordinates in Rd
The first element in the proof is well-known theorem from optimal transport called Brenier's theorem, which states that for Q a probability measure over 12 satisfying weak regularity conditions (see Theorem the pushforward 4 (X) is distributed according to Q.
9 in Section D). there exists map oo R -> R such that if X ~ N(0, Iaxu), then
The proof then proceeds by using lattice-based based encoding and decoding scheme. Concretely, let e > 0 be a small constant, to taking sufficiently small. Let e' E (0, e) be a further constant, taken sufficiently small with respect and similar for e" wrt é'. Let the input the affine coupling
8

---

Under review as a conference paper at ICLR 2021
layers layers layers beyen 7.6 lapers
10
10.2
10"5.
No padding
Zera
Goussion
Data distribttion
Jecobian Car dindinnnng Mattuee Gazazan Text Date
Padding
10
1071
0
500n 30000 E550n wito Pinco statn siono 00103
Moon
Figure 1: Fitting 32-dimensional linear maps on a using n-layer linear affine coupling networks. The squared Frobenius error is normalized by 1 1/d so it is independent of dimensionality. We shade the standard error regions of these losses across the seeds tried.
sucacons
Traninn bemanionn
Figure 2: Fitting 4-component mixture of Gaus- sians using a RealNVP model with no padding, zero padding and Gaussian padding.
network be X = (X,, X2) such that X2 NO, Iaxd) and X2 N(, Iaxa). Let fa:) be the map which rounds x E R to the closest grid point in the lattice cZd and define g(x) = x f(z). Note that for a point of the form
f(x) +'y for y which is not too large, we have that f(z) = f(x) and g(=) y. Suppose the optimal transportation map from Brenier's Theorem is yo(x) = (x)), yoa (a))
where f jP2 IRd - R² correspond to the two halves of the output. Now we consider the following sequence of maps, all which form an affine coupling layer:
Xx) + (X,,eX, + f(X1))
(1)
+ (f(a)(((X))) x +0(") e(2 + xx), + +()) + (x()
(2)
(3)
To explicitly see why the above are affine coupling layers, in the first step we take si (z) log(e'))
and L, (xx = f(x). the second step, we take (2 = log(e")T and la defined by 1/2 (ar)
(f g(z)) + (')2(f(x), g(x)). In the third step, we take s3(x) = log(e")ī and define (a(x)= g(a) er Taking sufficiently good approximations to all of the maps allows to approximate this map with neural networks, which we formalize in Appendix D
6.1 EXPERIMENTAL RESULTS
On the empirical side, we explore the effect that different types of padding has on the training on various synthetic datasets. For Gaussian padding, this means we add to the d-dimensional training data point, an additional d dimensions sampled from ((0, Ta). We consistently observe that zero padding has the worst performance and Gaussian padding has the best performance. On Figure we show the performance of a simple RealNVP architecture trained via max-likelihood on a mixture of 4 Gaussians, as well as plot the condition number of the Jacobian during training for each padding method. The latter gives support to the fact that conditioning is a major culprit for why zero padding provide figures from more synthetic datasets.
performs badly. In Appendix C.2
CONCLUSION
Normalizing flows are one of the most heavily used generative models across various domains, though we still have a relatively narrow understanding of their relative pros and cons compared to other models. In this paper, we tackled representational aspects of two issues that are frequent sources of training difficulties, depth and conditioning, We hope this work will inspire more theoretical study of fine-grained properties of different generative models.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang. Generalization and Equilibrium in Generative Adversarial Nets (GANs). 1703 703.00073 [cs, stat], August 2017. URL http:
//aaxiv.org//aaa.... wtwpg//bb///ooo 00573
arXiv: 1703.00573.
Michael Artin. Algebra. Pearson, 2011.
Bolton Bailey and Matus Telgarsky. Size-noise tradeoff's in generative networks. In Advances in Neural Information Processing Systems, pp. 6489-6499, 2018.
Jens Behrmann, Will Grathwohl, Ricky TQ Chen, David Duvenaud, and Jörn-Henrik Jacobsen. Invertible residual networks. arXiv preprint arXiv: 100999, 2018.
Jens Behrmann, Paul Vicol, Kuan-Chieh Wang, Roger B Grosse, and törn-Henrin Jacobsen, On the invertibility of invertible neural networks. 2019.
Sergej G Bobkov and Friedrich Götze. Exponential integrability and transportation cost related to logarithmic sobolev inequalities. Journal of Functional Analysis, 163(1):1-28, 1999.
Luis A Caffarelli. The regularity of mappings with a convex potential. Journal of the American Mathematical Society. 5(1):99-104, 1992.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components
estimation. arXiv preprint arXiv:1410.88 2014.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. arXiv preprint arXiv: 2016.
Emilien Dupont, Arnaud Doucet, and Yee Whye Teh, Augmented neural odes. In Advances in Neural Information Processing Systems, pp. 3134-3144, 2019.
Brian S Everitt. Finite mixture distributions. Wiley StaisRef: Statistics Reference Online, 2014.
Edgar N Gilbert. A comparison of signalling alphabets. The Bell system technical journal, 31(3): 504-50 522, 1952.
Will Grathwohl, Ricky TQ Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint arXiv:1810.01366. 2018.
Hans Grauert and Klaus Fritzsche. Several complex variables, volume 38. Springer Science Business Media, 2012.
Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
Chin-Wei Huang, Laurent Dinh, and Aaron Courville. Augmented normalizing flows: Bridging the gap between generative flows and latent variable models. arXiv preprint arXiv:2002.07101, 2020.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information Processing Systems, pp. 10215-10224, 2018.
Zhifeng Kong and Kamalika Chaudhuri. The expressive power of a class normalizing flow models.
arXiv preprint arXiv:2006.00:: 003992, 2020.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken. Multilayer feedforward networks with a nonpolynomial activation function can approximate any function. Neural networks, 6(6):861-867, 1993.
Guido Montufar and Nihat Ay. Refinements of universal approximation results for deep belief networks and restricted boltzmann machines. Neural computation, 23(5):300-11399 2011.
Guido F Montúfar, Johannes Rauh, and Nihat Ay. Expressive power and approximation errors of restricted boltzmann machines. In Advances in neural information processing systems, pp. 415-423, 2.1
10

---

Under review as a conference paper at ICLR 2021
George Papamakarios, Theo Pavlakou, and lain Murray. Masked autoregressive flow for density estimation. In Advances in Neural Information Processing Systems, pp. 2338 -347, 2017.
Satish Rao. Lecture notes for cs270: Algorithms. #sstissrr/ss270/ap///roo ottp:////ooooooooooooe///eeeeeea how.:a/eecooneee..aiiio.oooooo 2011.
http://pppppleeeeccccoooo www.:eeeeseseeeeeeeeeeeeee ey edu/
Vojtéch Rödl and Luboš Thoma. Asymptotic packing and the random greedy algorithm. Random
Structures & Algorithms, 8()):611-777, 1996.
Rom Rubenovich Varshamov. Estimate of the number of signals in error correcting codes. Docklady Akad. Nauk, SSSR, 117:739-741, 1957.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47, Cambridge university press, 2018.
Cédric Villani. Topies in optimal transportation. Number 58, American Mathematical Soc., 2003.
Fuzhen Zhang. The Schur complement and its applications, volume 4. Springer Science & Business Media, 2006.
Han Zhang, Xi Gao, Jacob Unterman, and Tom Arodz. Approximation capabilities of neural odes and invertible residual networks.

---

Under review as a conference paper at ICLR 2021
A MISSING PROOFS FOR SECTION 4
A.1 WASSERSTEIN DISTANCE FOR MIXTURES
Lemma 5. Let p and be two mixtures of spherical Gaussians d dimensions with mixing weights 1/k, means (F1, (21, .2......le .Pk) and (v1, (V1,V2,... ...,.... 12k) respectively, and with all of the Gaussians having spherical covariance matrix 2 some y > O. Suppose that there exists a set _ [k] with |S| k/10 such that for every E S,
min 11l4 111122 2 1SSS
Then Wi WI( = ((
Proof By the dual formulation of Wasserstein distance (Kantorovich-RRuiine Theorem) Villani (2003), we have (,, sup, [] pdl - ['ddv] where the supremum is taken all 1- Lipschitz functions yp. Towards lower bounding this, consider pp(x) = max(0, fy 2 | pall) and note that this function is 1-Lipschitz and always valued in [0, 2yv For single Gaussian
Z N/(, 2 Laxd), observe that
_z~N((0 (maxx (0, 2y [|Z111 > 2y
2rvd v EzzN [Z 2 rvd.
Therefore, we see that f ædd = ()(vvd) by combining the above calculation with the fact that at least 1/10 of the centers for ye are in S. On the other hand, for ~ (0. Taxa) we have
Pr(1 2 > 2 S 2e 10d
(e.g. by Bernstein's 's inequality Vershynin 2018). as || is a sum of squares of Gaussians, i.e. -2-random variable). In particular, since the points in do not have close point in {v: [v:]em we similarly have f lodv~ = O(e (f = o(rvd), since very little mass from each Gaussian in 1/ lands in the support of o by the separation assumption. Combining the bounds gives the result. A
A.2 CONSTRUCTING TUPLES OF WELL-SEPARATED MEANS
First, by elementary Chernoff bounds, we have the following result:
Lemma (Large family of well-separated points). Lei > 0. There exists set {or, U2 UN) of vectors U/ E Rd || with N exp(de² /4), s.t. ||u 12y12 2 2(1 - for all *
Proof. Recall that for random unit vector the sphere in d dimensions, Pr(u; t/vd) < 2/2
(This is basic fact about spherical caps, see e.g. Rao 2011)). ). By spherical symmetry and the union bound, this means for two unit vectors v, w sampled uniformly at random Pr(Ku, w) > t/vd) < 2e /222 Taking & = e evd gives that the probability is 2e de /2; therefore if draw N i.i.d. vectors, the probability that two have inner product larger than in absolute value is most N de /2 N ede?/ which in particular implies such a collection of vectors exists.
To construct tuples with small intersections,
the following result by Rödl:
Lemma Rödl Thoma 1996)). There exists a set consisting of (N )/10 subsets of size of [N],
s.1. no pair of subsets untersect in more than k/10 elements.
A.3 EETILON-NET COUNT
The following lemma is immediate:
Lemma 8. Suppose that ④ TR'd is contained in ball of radius R O and fo is family of invertible layerwise networks which is L.-Lipschitz with respect to its parameters. Then there exists a
set of neural networks S. {fi), s.t. |S.| = ((LR)d and for every 0 E θ there exists a ft E S.
s.t. (ox (x) f((x))l <.
12

---

Under review as a conference paper at ICLR 2021
A.4 SIMULATING MIXTURE WITH A NEURAL NETWORK
Lemma 9. Let p Rd + Rt be a mixture of k Gaussians with means {ui)iz ||uil - 20-2d and covariance Ia parameters [
La- Then, Ve
have Wi Wi(p: (p:9HN) S efoor a neural network with ((k)
Moreover, for every I-Lipschitz Φ RR R+ and X ~ 9#N, (XX is O subgausssnnn
(2017). Since the latent variable dimension is d + 1, the idea is to use the first variable, say h as imput to a "selector" circuit which picks one of the components of the mixture with approximately the right probability, then use the remaning dimensions say variable 2, to output a sample from the appropriate component.
Proof. We will use construction similar to Arora
For notational convenience, let M /2 Let { be real values that partition R into k intervals that have equal probability under the Gaussian measure. Then, the map
A = E1 (hi-1, hol)ps
1(h
exactly generates the desired mixture, where ho is understood to be -oo and h4 +o0.
To construct g. first we approximate the indicators using two ReLUs, s.t. we design for each interval (hi-1, hss] a function 1, s.t.:
(1) (h) = 1(h E (h;-1, h₂]) unless h E [ hs-1 + 5- U [hg ,h,, and the Gaussian measure of the union of the above two intervals 6.
(2) >; (h) = 1.
The constructions of the functions I, above can be found in Arora et al. (017)), Lemma 3. We
subsequently construct the neural network [h, 2) using ReI.Us defined as
f(h, (Rel.U(-M(1 - (i,))))))))))))))..))))())))))() + ps)
ReLUU-M(1 - i,(h)) v4)) (5)
Denoting
R-1
:: U 1=1
[he 57, hy + 55
note that if h & B, V2, f(h, 2) f(h, 2), desired. If h [h, 004-5,,44 8,, + 6 f(h,2) by
construction will be yz + Σm=1 w; (h))u for some wi(h) E [0 s.t. E. (h)
Denoting by @bh, 2) the joint pdf of h, z, by the coupling definition of Wi, we have
Wi(JnN.H) J [(h,2) 2) s(h, =) dø(h,))
Σ 1(h E (hi-1, - (RLLU(-M(1- (.(h)) + -4)
JNER
ReLU(-M - I.(h)) -mi))) dd(h) dbph))
1(h (hi=1, Σ wh(b)) de(h))
JEER
max m14 1sl)d bd 2M (ddd(h)
JNEB
KEB
2M edPr B)
2Mkd
'The size of g doesn't indeed depend The weights in the networks will simply grow with
13

---

Under review as a conference paper at ICLR 2021
So if choose 8 2M have the desired bound in W1- (We note, making 6 small only manifests in the size of the weights of the functions 1, and not in the size of the network itself. This obvious from construction in Lemma Arora et al. (2017).
Proceeding to subgaussianity, consider 1-L.pschitz function centered such that [e((po f) 0. Next, we'll show that (p #v is subgaussian with an appropriate constant. We can view f#N as the sum of two random variables: 72 and
(ReLU(-M(1 - i,(h)) + (4) MeL -x)))
y is a Gaussian with covariance I The other term is contained in an l2 hall of radius M. Using the Lipschitz property and Lipschitz concentration for Gaussians (Theorem 5.2.2 of Vershynin (2018))
that Pr[l(p f) 2 1] exp
(__-t_1))) ", By considering separately the cases |M| s 2M and
27
[t] 2MM we immediately see this implies that the pushforward is O( + -u?")ssubaussiin. Since
M = Od))d), the claim follows.
A.5 KL DIVERGENCE BOUNDS
In this section, we use the Bobkov-Goetze inequality to derive the KL. divergence bounds from the Wasserstein bounds.
Concretely:
Theorem 8 (Bobkov & Götze (1999) Lef p,q Rdd 1-Lipschitz W1 (p.
Tk+ be two distributions for every f(X) is c²-subgaussian. Then, we have KL(g, p) Z
R
7 R and X
Then, to finish the two inequalities in the statement of the main theorem, we will show that:
For any mixture of & Gaussians where the component means μ4 satisfy || s M, the condition of Theorem is satisfied with c² O(₂² + M2). (In fact, show this for the pushforward through g. the neural network which approximates the mixture, which poses some non-trivial technical challenges. See Appendix A Lemma
A pushforward of the standard Gaussian through a L-Lipschitz generator f satisfies the conditions of Theorem g with c² L2, which implies the second part of the claim. (Theorem 5.2.2 in Vershynin 2018).)
B MISSING PROOFS FOR SECTION 5
B.
UPPER BOUND
First, we recall a folklore result about permutations. Let S, denote the symmetric group on n elements, i.e. the set of permutations of (1....,7) n) equipped with the multiplication operation of composition. Recall that the order of a permutation æ is the smallest positive integer k such that z the identity permutation.
Lemma 10. For any permulation E Sn, there exists 0T, E Sn of order at most 2 such that
== 000..2
Proof. This result is folklore. We include proof of it for completenes!
- C₁ product of disjoint cycles. Therefore if we show the result for single cycle, so = 0:1022 for every i, then
First, recall that every permutation π has unique decomposition
TThi proof. given by HH Rugh, and some other
ways to prove this result
be found at htops://math Staechssttcciee http://www...ttceeeceeaeeeeeeeee owwp://hnnnnneeee/eusssiio/ooono
every-permutationn aet.ypammttttiiieeeerrooooooooee
14

---

Under review as a conference paper at ICLR 2021
taking 01 = II.-= du and 02 II 02 proves the desired result since d1 and 01, 02 both of order at most
It remains to prove the result for single cycle of length r. The cases Σ 2 are trivial. Without loss
of generality, we assume c = (1 (1....)) Let o (1) = 2. oj (2) = 1, and otherwise (1(s) = + s. Let (2(1) = (2 = 2, 02(3) 1, and otherwise (2(() definition that both of these elements are order at most 2.
It's easy to check from the
We now claim 02 o d1. To see this, consider the following cases:
1. (2(0)(1)) = (2) = 2.
2. 02(0i(2)) = 02(1) = 3.
3. (2(((r)) o3()) =
4. For all other s, (2(0](s)) = 02(r + 3 = = + 1.
In all cases see that c(s) (2 (s)) which proves the result.
Next, we supply the proof of Lemma
Proof of Lemma 2
It is easy to see that swapping two elements is possible in fashion that doesn't t affect other dimensions by the following 'signed swap' procedure requiring 3 matrices:
(x, v) - (x, x) + (v.v x) + (y. -x).
(6)
Next, let L (1.....d] d} and R {d 1..... 2d}. There will be an equal number of elements which in particular permutation will be permuted from L to R as those which will be permuted from R to L.. We can choose an arbitrary bijection between the two sets of elements and perform these "signed swaps' in parallel as they are disjoint, using total of 3 matrices. The result of this will be the elements partitioned into L and R that would need to be mapped there.
We can also (up to sign) transpose elements within given set L R via the following computation using our previous 'signed swaps' that requires one 'storage component" in the other set:
(Ix, 2), + ([z, vl, -z) + ([2,z),)) v) (ly. -2).
So, up to sign, we can matrices compute any transposition in L or separately. In fact, since any permutation can be represented as the product of two order-2 permutations (Lemma and any order-2 permutation is a disjoint union of transpositions, we can implement an order-2 permutation up sign using matrices and an arbitrary permutation up sign using 18 matrices.
In total, we used 3 matrices to move elements to the correct side and 18 matrices to move them to their correct position, for total of 21 matrices.
Lemma 11. Suppose A E Raxn is matrix with distinct real eigenvalues. Then there exists invertible matrix S E R"x= such that SDDS! where is a diagonal matrix containing the eigenvalues of A.
Proof. Observe that for every eigenvalue X; of A, the matrix (A - A₂4) has rank n by definition, hence there exists a corresponding real eigenvector v; by taking nonzero solution of the real linear system (A XL)e = 0. Taking S to be the linear operator which maps to standard basis vector v. and diag . >x.) proves the result.
Next, give the proof of Lemma
Proof of Lemma 3
Let
D (M T)F
(M 1 T)F²
F --MM,
15

---

Under review as a conference paper at ICLR 2021
where A is an invertible matrix that will be specified later. We multiply out with these values giving
T
0
I
D
I
0
I
H
A
1
0
1
E
1
0
1
I
0
I
(I
M
'A
I
[ (I-M 1-M- 'A'
A
7
I
AM
0
I
T
(M-1
T)A-1 -1
|
[
T
1
1
(1 -
M 1-A-1
11-1
A
AM-1A-
-AM
AM
1
0
1
M
(M-1
1A -1
|
(I-
M
)M -A--AA A--
O
AM-1A-
I
M
O
AM-1A-1
Here what remains is to guarantee AM-1A-1 S. Since and M have the same eigenvalues,
by Lemma 11 there exist real matrices U, V such that S = UXU and M-1 = VXV for the same diagonal matrix X, hence = UV 1 VU-U Therefore taking A UV -1 gives the result.
Now that we have the Lemmas, we prove the upper bound.
Proof of Theorem 5 Recall that our goal is to show that GL_ R) C AK for an absolute constant
K >> O. To show this, we consider an arbitrary matrix T E GL+ (2d, I), i.c. an arbitrary matrix T 2d x 2d with positive determinant, and show how to build as a product a bounded number of
elements from A. As T is square matrix, it admits an LUP decomposition Horn & Johnson (012): Le. a decomposition into the product of a lower triangular matrix L, an upper triangular matrix U. and permutation matrix P. This proof proceeds essentially by showing how to construct the L,, U, and P components in a constant number of our desired matrices.
By Lemma 2 we can produce a matrix P with det P > O which agrees with P up to the sign of its entries using (11) linear affine coupling layers. Then TP-1 is a matrix which admits an LU decomposition: for example, given that we know TP-1 has LU decomposition, we can modify flip the sign of some entries of U to get LU decomposition of TP-1 Furthermore, since det(Tpp-) > O, we can choose LU decomposition TP-1 LU such that det(L), det(U) 0 (for any decomposition which does not satisfy this, the two matrices L. and U must both have negative determinant as < dT = dct(L) det(U), In this case, we can flip the sign of column in L and row in U make the matrices positive determinant).
remains to show how to construct a lower/upper triangular matrix with positive determinant out of matrices. We show how to build such lower triangular matrix L building U is symmetrical.
A 0
At this point we have a matrix
where A and C' are lower triangular. We can use column
B
elimination to eliminate the bottom-left block:
A
0 C
0- A 0] C
0
B
C-IB
T
= 0
where A and C' are lower-triangular.
Recall from equation 6 that we can perform the signed swap operation in R² of taking (z, y) H (v, -x:) for x using 3 atfine coupling blocks. Therefore using 6 affine coupling blocks can perform a sign flip map (x. 3) + (-z. yy) Note that because det L) > O. the number of negative entries in the first diagonal entries has the same parity as the number of negative entries in the second d diagonal entries. Therefore, using these sign flips in parallel, we can ensure using affine coupling layers that that the first d and last d diagonal entries of L have the same number of negative elements. Now that the number of negative entries match, we can apply two diagonal rescalings to ensure that:
1. The first d diagonal entries of the matrix distinct.
16

---

H Under review as a conference paper at ICLR 2021
2. The last diagonal entries contain the multiplicative inverses of the first d entries up to reordering. Here we use that the number of negative elements in the first and last elements are the same, which ensured earlier.
At this point, we can apply Lemma 3 to construct this matrix from four of our desired matrices. Since this shows
build L and U, this shows
build any matrix with positive determinant.
Now, let's count the matrices we needed to accomplish this. In order to construct P. needed 21 matrices. To construct L, we needed for column elimination, for the sign flip. 2 for the rescaling of diagonal elements, and 4 for Lemma giving total of 13. So, need 21 + 13 + 13 47 total matrices to construct the whole LUP decomposition.
B.2 LOWER BOUND
Finally, we proceed to give the proof of Lemma
Proof of Lemma
4
We explicitly solve the block matrix equations. Multiplying out the LHS gives
C
D
G
CG+ ACG + ADEG + BEG
CH + DEH DF ACH + ADEH + ADF + BEH + BF
AC
AD+ B
EG
EH +
Say
X
Y
Z W
Starting with the top-left block gives that
X (C DEJG
D= (X6-1
(7)
Next, the top-right block gives that
Y = (C + DEJH + DF = XG- DF
H = GX (Y DF).
Equivalently,
D DY H)F-1
(9)
Combining equation 8 and equation 7 gives
H GX -CG-1-C)E-'P
GX G. - -1--
GX- -C
(10)
The bottom-left and equation
gives
2 ACG ADEG BEG
=C (AD+ B)F
E (AD B) AC)
(11)
E (A(XG-1 -10X----CC)"" C)E + AC)
E 1 = -A0-11
(ZG-1- AC) (A(XG-1-0) - +B) A(XG-1 C) + BE
= -2C - C))
E 6-B-12G---AGG-
(12)
Taking the bottom-right block and substituting equation gives
W ACH + (AD (EH + FF) AC'H + (ZG-1 - AC) (AD + B)F
W -G-1H ADF + BF.
(13)
17

---

Under review as a conference paper at ICLR 2021
Substituting equation into equation 13 gives
= 2G + A(Y - XG BP (2 (2 AY + BR.
Substituting equation I0 gives
W (Z -
+ BF
(Z - 10-1 AY BF.
Substituting equation 12 gives
W -Z - AX) -A1 + + BF
W - zx-Ly - -BF = -
(Z
(Z AX)X AX) BF
W x (2- '(( AXX
(14)
Here we notice that W - - is similar X-1C, where we get choose values along the diagonal of C. In particular, this means that W - - and X X-1C must have the same cigenvalues.
Proof of Theorem 6 First, note that element in A can be written in either the form L, R₂ L2 R2 R₂ L R2 for L1, Le E Ag and R1, R2 E Ax. We construct an explicit matrix which cannot be written in either form.
Consider an invertible matrix of the form
X
0 W
T
and observe that the Schur complement T/X is simply W. Therefore Lemma says that this matrix can only be ALARAAAA if W is similar X X- for some diagonal matrix C. Now consider the case where W is a permutation matrix encoding the permutation (1 ... d) and X is a diagonal matrix with nonzero entries. Then X X-IC is diagonal matrix as well, hence has real eigenvalues, while the eigenvalues of W are the d-roots of unity. (The latter claim follows because for any with nd 1, the vector (1. ç <d-1) is eigenvector of W with eigenvalue (). Since similar matrices must have the same eigenvalues, it is impossible that X and W are similar.
The remaining possibility we must consider is that this matrix in ARACARAC In this case by applying the symmetrical version of Lemma 3 (which follows by swapping the first and last coordinates), we see that W-1C and X must be similar. Since Tr(W-1C) = 0 and Tr(X) 0, this impossible.
C EXPERIMENTAL VERIFICATION
C.I PARTITIONED LINEAR NETWORKS
In this section, we will provide empirical support for Theorems and 3 More precisely, empirically, the number of required linear affine coupling layers least for random matrices seems closer to the lower bound - so it's even better than the upper bound we provide.
Setup We consider the following synthetic setup. We train n layers of affine coupling layers, namely networks of the form
n
C O
D. I
0
fa(2) =
A
B,
with E, Bg, C, diagonal. Notice the latter two follow the statement of Theorem 2 and the alternating order of upper vs lower triangular matrices can be assumed without loss generality, as a product of upper/lower triangular matrices results in upper/lower triangular matrix. The matrices F. tur
18

---

Under review as a conference paper at ICLR 2021
to be necessary for training they enable "renormalizing" the units in the network (in fact, Glow uses these and calls them actnorm layers; in older models like RealNVP, batchnorm layers are used instead).
The training data is of the form Az, where : ~ (V(0 1) for a fixed x d square matrix A with either random standard Gaussian entries in Figures 4 to g random standard Gaussian entries that diagonal-constant (that latter giving a natural random ensemble of Toeplitz matrices) in Figures to 13 This ensures that there is "ground" truth linear model that fits the data well. | We then train the affine coupling network by minimizing the loss (0.1) [z) A2)² and trained on a variety of values for n and in order to investigate how the depth of linear networks affects the ability fit linear functions of varying dimension.
Note, we are not training via maximum likelihood, but rather we are minimizing a "supervised" loss, wherein the network f.. "knows" which point x latent 2 is mapped to. This is intentional and is meant to separate the representational vs training aspect of different architectures. Namely, this objective is easier to train, and our results address the representational aspects of different architectures of flow networks- - so we wish our experiments to be confounded as little as possible by aspects of training dynamics.
We chose n 1, 2, 4, 8, 16 layers and = 4,8, 16, 32, 64 dimensions (here a layer is one matrix and not a flipped pair as in our theoretical results). We present the standard L2 training loss and the squared Frobenius error of the recovered matrix Å obtained by multiplying out the linear layers A Al. both normalized by 1/d so that they are independent of dimensionality. We shade the standard error regions of these losses across the seeds tried. All these plots are log-scale, so the noise seen lower in the charts is very small.
We initialize the E, C, B matrices with Is on the diagonal and A, D with random Gaussian elements with a 10-5 and train with Adam with learning rate 10-4, We train on 5 random seeds which affect the matrix A generated and the datapoints 2 sampled.
Finally, we also train similar RealNVP models on the same datasets, using a regression objective as done with the PLNs but and networks with two hidden layers with 128 units and the same numbers of couplings as with the PNN experiments.
Results The results demonstrate that the 1- and 2- layer networks fail fit even coarsely any of the linear functions we tried. Furthermore, the 4-layer networks consistently under-perform compared to the 8- and 16-layer networks. The 8- and 16-layer networks seem to perform comparably, though we note the larger mean eтror for d=64, which suggests that the performance can potentially be further improved (either by adding more layers, or improving the training by better choice of hyperparameters; even on this synthetic setup, we found training of very deep networks to be non- non-trivial).
These experimental results suggest that at least for random linear transformations T, the number of required linear layers is closer to the lower bound. Moreover, the error for the Toeplitz ensemble is slightly larger, indicating this distribution slightly harder. Closing this gap (both in a worst-case and distributional sense) is an interesting question for further work.
In our experiments with the RealNVP architecture, we observe more difficulty in fitting these linear maps, as they seem to need more training data to reach similar levels or error. We hypothesize this is due to the larger model class that comes with allowing nonlinear functions in the couplings.
C.2 ADDITIONAL PADDING RESULTS ON SYNTHETIC DATASETS
We provide further results on the performance of Real NVP models on datasets with different kinds of padding (no padding, zero-padding and Gaussian padding) on standard synthetic Batasets-Swissee 2 Moons and Checkerboard.
The results are consistent with the performance on the mixture of Gaussians: in Figures 24 25 and
26 we see that the zero padding greatly degrades the conditioning and somewhat degrades the visual quality of the learned distribution. On the other hand, Gaussian padding consistently performs best, both in terms of conditioning of the Jacobian, and in terms of the quality of the recovered distribution.
As side remark, this ground truth is only specified up to orthogona matrices U, AU is identically distributed Az, due to the rotational invariance of the standard Gaussian.
19

---

Under review as a conference paper at ICLR 2021
D UNIVERSAL APPROXIMATION WITH ILL-CONDITTION AFFINE COUPLING NETWORKS
D.1 SIMPLER UNIVERSALITY UNDER ZERO-PADDING.
First (as a warmup), we give much simpler proof than Huang et al. (2020) that affine coupling networks are universal approximators in Wasserstein under zero-padding, which moreover shows that only a small number of affine coupling layers are required. For Q probability measure over Tk satisfying weak regularity conditions (see Theorem Obelow) by Brenier's Theorem Villani (2003) there 222 optimal transport map
P:
IR"
such that X ~ [(0, Ixxn), then the pushforward y (X) is distributed according to Q, and a corresponding transport map in the opposite direction which we denote y- If we allow for arbitrary functions t in the affine coupling network, then we can implement the zero sero-padded transport map (X,0) + (xx(), 0) as follows:
(X,0) + (()) - (p(X) - (x)()),).
(15)
Explicitly, in the first layer the translation map is t1 (z) p(z). in the second layer the translation
map is t2(2) = x - 80 - (z). and in the third layer the translation map is tx(x) = -z. Note that no scaling maps are required: with rero-padding the basic NICE architecture can be universal, unlike in the unpadded case where NICE can only hope to implement volume preserving maps. This is because every map from zero-padded data to zero-padded data is volume preserving. Finally, if we are required to implement the translation maps using neural networks, we can use standard approximation -iieeortttoo-thooeetiicccc results for neural networks, combined with standard results from optimal transport, to show universality of affine coupling networks in Wasserstein. First, we recall the formal statement of Brenier's Theorem:
Theorem 9 (Brenier's Theorem, Theorem 2. of Villani (203)). Suppose that P and Q are probability measures on R" with densities with respect to the Lebesgue measure. Then Q = (V b for v a convex and moreover V the unique W Wp-optimal transport map from P to Q.
It turns out that the transportation map o V is not always continuous function, however there are simple sufficient conditions for the distribution Q under which the map is continuous (see e.g. [Caffarelli (1992)). From these results (or by directly smoothing the transport map), know any distribution with bounded support can be approached in Wasserstein distance by smooth pushforwards of Gaussians. So for simplicity, we state the following Theorem for distributions which are the pushforward of smooth maps.
Theorem 10 (Universal approximation with zero-pate arr--adding). Suppose that P is the standard Gaussian measure in Ih"" and Q U4 P is the pushforward of the Gaussian measure through y and yp is smooth map. Then for any e >> 0 there exists depth 3 affine coupling network with no scaling and feedforward ReLU net translation maps such that W2(9 (P x 8g ), Q x dg S.
Proof. For any M > O, let (z) = min(M, max ( M,))) be the 1- 1-dimensional truncation M, Mr be the result of applying far
map to M- M] and for a vector x E R" let fx(()) E [-M, coordinate-wise Note that fM can be implemented as a ReLU network with two hidden units per input dimension. Also, any continuous function on [-M, Mj" 7 by a sufficiently large ReLU neural network with one hidden layer Leshno et al. (1993). Finally, note that if |ff - g 1. < e then for any distribution P we have W2(f P. S by considering the natural coupling that feeds the same input into f and g.
can be approximated arbitrarily well in
Now we show how to approximate the construction of equation 15 using these tools. For any >> 0, if we choose M sufficiently large and then take S and - 1 to be sufficiently good approximations of ip and - on [-M, M)", we can construct an affine coupling network with ReLU feedforward network translation maps f, (x) fM(( (z))), fz( the output has W2 distance at most e from Q
(z). and tz(x) = -z, such that
Universality without padding. We now show that universality in Wasserstein can be proved even if we don't have zero-padding, using lattice-based encoding and decoding scheme. Let e > 0
20

---

More explicitly, in the first step we take $1 s1 log(())) and (1 (z). In the second step, we In the Under review as a conference paper at ICLR 2021
be small constant, be taking sufficiently small. Let é' E (0,c) be further constant, taken sufficienlly small with respect to e and similar for e" wrt Suppose the imput dimension is 2n, and let X (2) with independent X1 NO, Iaxu) and X₂ ~ [0, Inxn) be the input the the affine coupling network. Let I (a: be the map which rounds x E R to the closest grid point in eØ" f(a)). Note that for point of the form
fa) + c'y for y which is not too large, we have that f(z) f(z) and g(z) y. Let (1, P2 be the desired transportation maps guaranteed by Brenier's s theorem, so that the distribution of pi (X) the target distribution Q and P2(X is a standard Gaussian independent of (o (X). (In other words, (1, f2 correspond to the first half and second half of the output coordinates of the transport map from the 2n dimensional standard Gaussian to the desired padded distribution.) Now we consider the following sequence of maps:
and define g(x:)
X2) (X f(X))
(16)
- (f())(((x)))x) + +(0((((3),,, f(X))) (f(e((((())) - -<oo///1xxxx))))+))))) O((")))))))
(17)
(e)))e))
(18)
take 52(x) = log(e")] I and t2 is defined by (2(x) (f (())) + ('p2(f()), third step, we take sy(x) log(e")í and define tz aهع
Again, taking sufficiently good approximations to all of the maps allows to approximate this map with neural networks, which we formalize below.
into a universal approxi- mation theorem for ReLU-net based feedforward networks just requires to modify the proof of Theorem 10 for this scenario.
Proof of Theorem Turning equation equaatio 17 and equation 18
Fix > O, the above argument shows we can choose c, > O sufficiently small so that if h is map defined by composing equation equuttoon 17 and equation 18 then W2(hg P. Q) S c/4. The layers defining h may not be continuous, since / is only continuous almost everywhere. Using that continuous functions are dense in LZ" we can find a function fc which is continuous and such that we define he by replacing each application of by Se, then ( S t/2.
Finally, since Se an affine coupling network with continuous s and functions, we can use the same truncation-ande wnw-aaa-nnd--daaaaaaaaeeae appoxiiaiiinnnnonn argument from Theorem to approximate it by affine coupling network with ReLU feedforward s and t functions such that PP Q) S e, which proves the result.
E APPROXIMATING ENTRYWISE NONLINEARITY WITH AFFINE COUPLINGS
To show how surprisingly hard it may be to represent even simple functions using affine couplings, we show an example of very simple function-an an entrywise application of hyperbolic tangent, s.t. arbitrary depth/width sequence of affine coupling blocks with tanh nonlinearities cannot exactly represent it. Thus, even for simple functions, the affine-coupling structure imposes nontrivial restrictions. Note that in contrast to Theorem 4
we are considering exact representation here.
Precisely, we show:
Theorem 11. Let 2 and denote .dd - Rd, 9()) := (tanh 21,..., tanh 2d). Then, for any W. D,N E N and norm || ||. there exists an e(W, D. D)N)= > 0, s.t. for any network f consisting of sequence of at most N affine coupling layers of the form:
(ys, vs) + (ys, V3 3 a(ys) b(ys))
for in each layer arbitrary set S & [d] and a, arbitrary fordadd tanh neural networks of width at most W, depth at most D, and weight norm into each unit of at most R2 it holds that
E (1 ((>)) > <(W D. N. R).
21

---

Under review as a conference paper at ICLR 2021
The proof of the theorem is fairly unusual, it uses some tools from complex analysis in several variables (see Grauert & Fritzsche| (2012) for a reference) - though it's t's so short that we include here. The result also generalizes to other neural networks with analytic activations.
By compactness of the class of models bounded by W, W, R. it suffices to prove that there no way to exactly represent the function.
Proof of Theorem 77
Suppose for contradiction that f g on the entirety of [-1, Let 21..... 2 denote the d inputs to the function: we now consider the behavior of ʃ and g when we extend their defnnitio to Cd. From the definition, 9 extends to holomorphic function (of several variables)
all of Cd \ {= : 2j = in ( + 1/2) : E 2}, i.c. everywhere where tanh doesn't 't have a pole, Similarly, there exists an dense open subset D C Cd on which the affine coupling network is holomorphic, because it is formed by the addition, multiplication, and composition of holomorphic functions.
We next prove that = q on their complex extensions by the Identity Theorem (Theorem 4.1 of open subset of Cd. To prove
Grauert & Fritzsche )2122). We must first show that f = 9 this, observe that f is analytic at zero and its power series expansion is uniquely defined in terms of the values of f on Rd (for example, follows that the power series expansions of f and 9 are both equal at zero and convergent in an open neighborhood of in Cd, so can indeed apply the Identity Theorem; this shows that g wherever they are both defined.
compute the coefficients by taking partial derivatives).
From the definition tanh(z) = -प we can see that g is periodic in the sense that g(=+ (=))
=
for any zd. However, by construction the affine coupling network f is invertible whenever, at every layer, the output of the function is not equal to zero. By the identity theorem, the set of inputs where each a vanishes is nowhere dense otherwise, by continuity a vanishes on the open neighborhood of some point, so 0 by the Identity Theorem which contradicts the assumption. Therefore the union of inputs where a at any layer vanishes also nowhere dense. Consider the behavior of on open neighborhood of O and of im: have shown that f is invertible except nowhere dense set, and also that g = f wherever f is defined, but g(z) = g( + in)) so it impossible for f to be invertible on these neighborhoods except on nowhere dense subset. By contradiction, f on 1).
Finally, to give empirical evidence that the above is not merely a theoretical artifact, we regress an affine coupling architecture to fit entrywise tanh.
Specifically, we sample 10-dimensional vectors from a standard Gaussian distribution and train networks as in the padding section on squared error objective such that each input is regressed on its elementwise tanh. We train an affine coupling network with 5 pairs of alternating couplings with and h networks consisting of 2 hidden layers with 128 units each. For comparison, we also regress simple MLP with 2 hidden layers with 128 units in each layer, exactly one of the or h subnetworks from the coupling architecture, which contains 20 such subnetworks. For another comparison, also try this on the elementwise ReLU function, using affine couplings with tanh activations and the same small MLP.
As we see in Figure 3 the affine couplings fit the function substantially worse than a much smaller MLP corroborating our theoretical result.
22

---

Under review as a conference paper at ICLR 2021
Supervised Training Common Nonlinearities
tanh
ROUL
MLP
10
SLP
10"
10'
10a
5000
750
13002
15000
17500
20002
1900
12300
12585
15000
17500
2000
Tariin Steas
Tean og Staxs
Figure 3: The smaller MLPs are much better able to fit simple elementwise nonlincarities than the afline couplings.
Supervised 4. Dimmensional Linear Functions
layers layers
laaeers 16 laye's
1C-1
20-1
Parandeer rrobeius Erorr
L1 Loxs
5.
10
20-7
30
10-13
20-13
13000 20000 25000
10000 25000 20000 aCC0D
Berations
Rerations
Figure 4: Learning Partitioned Linear Networks on 4-D linear functions.
Supervised Dimensional Linear Functions
layers
laaoers
layers
10.
18 layers
20
Normalzze Pummmber mmr
10
Nevmoalood Thwiing Ince
10
20-4
10-
30
5000 20000 15000 20000 25000 30000
35003
40000
5000
10003 15000 20000 25000 30000 35000 #0000 Iterations
Borations
Figure 5: Learning Partitioned Linear Networks on 8-D linear functions.
23

---

Under review as a conference paper at ICLR 2021
Supervised 16-Dimensional Linear Functions
layrrs
layers
layers
layeers
layers
Nommaleee Thening Ince
No Nomaines Paraieter Frchemuss
5030 10000 15080 20c0n 2500n a000n 25003 40000
S00n
10603 15000 20000 25000 a0d0s 2sono 4CC0D Iteraions
Rerations
Figure 6: Learning Partitioned Linear Networks on 16-D linear functions.
Supervised 32-Dimensional Linear Functions
layess
layors
layers
108
20'
laye's
10-
Normal red Thwiiing 12 Iice
10
Nommaized Paraieter Rebernus
10-1
20-4
Ic-1
20-7
5030
20000 15080 28000 25000 30000
25003
40000
18003 13000 20000 25000 a0000 15000 #0C0D 5000
Reralions
Reralions
Figure 7: Learning Partitioned Linear Networks on 32-D linear functions.
24

---

Under review as a conference paper at ICLR 2021
Supervised 61-Dimensional Linear Functions
layers
layess
layers
layyers
layers
20"
4.
Nemmal Thening Inee
No maltsss Parameter Frchemus
20
30
10"1
10"
5030
10000 15080 20c0n 2500n ap00n 25003
40000
500n
18603 15060 20000 25000 andos 250n0 4CC00
Rerations
Rerations
Figure 8: Learning Partitioned Linear Networks on 64-D linear functions.
Supervised d.Dimensional Toeplitz Linear Functions
layess
layors
layers
laye's
309
10a
10
Nomaltted Parameter Rebrenus
Nomallzed Thaninng
10
5030
20000 15080 28000 25000
25003 Retalions
30000
40000
5000 10003 13000 20000 25000 30000 15000 4CC0D
Reralions
Figure 9: Learning Partitioned Linear Networks on 4-D Toeplitz functions.
25

---

Under review as a conference paper at ICLR 2021
Supervised B-Dimansional Troplitz Linear Functions
layers
layers
layers
layyers
layers
10.
No Parameter Frehenus
1c-1
Nomalize Training
20-1
16
5030 10000 15080 20c0n 2500n apcon 25003 40000
0.
500n
10003 15006 20000 25000 andos asóno 4cc00
Rerations
Rtertions
Figure 10: Learning Partitioned Linear Networks on 8-D Toeplitz functions.
Supervised 16-Dimensional Teeplitz Linear Funct
layers
layorr
layers
10a
laye's
30'
Nomallze "raiiing
20"1
Xc-1
5030 20000 15080 28008 25000 30000
25003 40000
5000 18003 13000 20000 25000 30000 15000 #CCED
Reralions
Reralions
Figure 11: Learning Partitioned Linear Networks on 16-D Toeplitz functions.
26

---

Under review as a conference paper at ICLR 2021
Supervised 32-Dimensional Treplitz Linear Funct
laerrs
layers
layers
layyers
10
layers
Nermaiie maaning tree
Perameter tretaenites
20
uc-1
10"2
5030 10000 15080 20c0n 2500n
apcon
35003 40000
900n 18603 15060 20000 25000 andos asono #CC0D
Rerations
Kerations
Figure 12: Learning Partitioned Linear Networks on 32-D Toeplitz functions.
Supervised 64-Dimensional Teeplitz Linear Funct
layers
layorr
layers
10.
laye's
20'
Nommallee "haining Iice
10-1
redrenitos
20"0
10-3
5000 18003 13000 20000 25003 30000 15000 RCCED 10
5030 20000 15080 28008 25000 30000
25003 40000
Retalions
Reralions
Figure 13: Learning Partitioned Linear Networks on 64-D Toeplitz functions.
27

---

Under review as a conference paper at ICLR 2021
Real NVP Regressed or 4-Cimersional Linear Functions
Real NVP Regressed en 3-D/mernional Linear Functions
10/
Nommetcal Tanity
167
Rayars
Nommitad Traning
byaors
layers
byyor
layers
16 layers
layers
10
2011-
10
10
20000
40000
80000
S3000
200020
20000
43000
B0000
50000
200000
Eerations
Eer2tions
Figure 14: Real NVP Regressed on 4-D Linear Functions
Figure 15: Real NVP Regressed on 8-D Linear Functions
Real NVP Regressed on 16. Dimensional Linear Functions
Real NVP Regressed on 32. Dimensional Linear Functions
107
30F
No malizze Tranngg uoos
No melmi baning
myyers
layers
layrrs
byyer
liyers
layors
10:2
10-4
10
10"0
20000
$0000
B0000
50000
200000
20000
43000
B0000
53000
200000
Rerations
terations
Figure 16: Real NVP Regressed on 16-D Linear Functions
Figure 17: Real NVP Regressed on 32-D Linear Functions
28

---

Under review as a conference paper at ICLR 2021
Real NVP Regressed on o4-Dimensional Linear Functions
Real NVP Regressed on memniiinnall Trepitz Functions
Norma Tsnnny
Rayars
Mommirrd Traning
byyors
byyrs
layers layers
16 layers
20m4
10-1
20000
40000
80000
53000
200020
20000
43000
B0000
50000
200000
Eerations
Eerations
Figure 18: Real NVP Regressed on 64-D Linear Functions
Figure 19: Real NVP Regressed on 4-D Toeplitz Functions
Real NVP Regressed on 8 mensional Taepiitz Functions
Real NVP Regressed on 16-Dimensional Teeplitz Functions
10P
No malizzz Taning uoos
107
No melrdd Banigg
myyer
layers
107
layers
byyes
10F
layers
layers
10
10m
10
20000
$0000
B0000
50000
200000
20000
43000
B0000
50003
200000
Rerations
terations
Figure 20: Real NVP Regressed on 8-D Toeplitz Functions
Figure 21: Real NVP Regressed on 16-D Toeplitz Functions
29

---

Under review as a conference paper at ICLR 2021
Real NVP Regressed on 32-0imemsional Toopl tz Functions
Real NVP Regressed en 58-Dimersional Theplitz Functions
107
Mormalized Taining L2 Los
Rayars
Ryars
layars
Mormattedd
16 lyyers
layers
10-4
20000
40000
50000
53000
300020
20000
43000
80000
50200
300000
Esrations
Esrations
Figure 22: Real NVP Regressed on 32-D Toeplitz Functions
Figure 23: Real NVP Regressed on 164-D Toeplitz Functions
30

---

Under review as a conference paper at ICLR 2021
Real NVP on Swissroll Dataset
Po Poaiin
Grlburan Tooklny
Figure 24: Real NVP on Swissroll Dataset
Real NVP Moons Dataset
Prddlin
Sandinng
Rodding
Bat
perbaan Condianingg Bott
Figure 25: Real NVP on Moons Dataset
Rool NVP on Checkerboard Datazet
hadding
fedding
Condi
Don Polking Goertten
Teanng Reorices.
Figure 26: Real NVP on Checkerboard Dataset
31


Reviews:
[{"review_id": "uykcNPW7ls1", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The normalizing flows (NF) are among popular generative models, as they have the capability of converting a simple base distribution to complex distributions by successively applying change of variable formula. More importantly, NFs let us do inference by maximizing exact likelihood functions instead of other approximate functions like ELBO in VAEs. NFs have the invertibility constraints which make the calculations of their Jacobean determinants computationally prohibitive and require some tricks that make them easier to compute. All these tricks, among them affine coupling layers are of great popularity, come at the price of losing expressiveness. Therefore, we might need more layers (deep) to compensate for that. However, we lack a theoretical understanding of how much deep is enough to guarantee best results.  \n\nThis paper provides many useful and insightful theorems which sheds light on these kind of questions in using NFs. It specifically studies the affine coupling layers and provides an upper bound and a lower bound on the depth of the layers required to achieve a good performance. Then it investigates the effects of zero padding in the inputs of the NFs and shows that the reason that the NFs cannot work well with zero padding is actually related to poor conditionings of Jacobeans during the trainings. \n\nAlthough this paper does not answers all the issues of the NFs, I think providing some interesting theorems on even simple questions, such as the effect of depth, could shed light on other questions in this field for other researchers. I have the following comments for this paper:\n\n1- I think the formatting of this paper is wider than usual ones, which makes the reading difficult and it seems more compact. I think the authors should double check it to make it coherent with the other papers. \n\n2- Although this is a theoretical paper, the number of experiments are limited. I believe that adding extra experiments can better reflect the value of the paper. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "lHiOj0RnFVJ", "reviewer": "AnonReviewer3", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "**Summary**\nThis paper studies theoretical properties of flow models, mainly focussing on affine coupling layers. The authors investigate several questions on the representational capacity of flow models, focusing on the role of flow depth and the regularity/conditioning of the flow model.\nTheir findings can be summarized as follows: 1) The authors show that an invertible flow model (not necessarily of the affine coupling form) that needs to match the generated data of a non-invertible generator needs to be substantially deeper than the non-invertible generator, while maintaining roughly the same amount of parameters as the non-invertible generator. 2) The authors show that any linear invertible map can be learned with a constant number of affine coupling layers with a fixed partitioning. Therefore, approximations for learnable permutation layers such as the 1x1 convolutions of GLOW can be replaced by increasing the size of the flow network with a constant factor. 3) The authors show that if the Jacobian of affine flow models can be arbitrarily close to singular, affine flow models are universal approximators for distributions with bounded support. This results requires no zero padding of the input, as was the case of previous work [1]. 4) Finally, the authors explore the effect of zero padding or gaussian padding on 2d toy examples, and find that gaussian padding leads to better matching of the data distribution and a better condition number.\n\n\n**Pros**\n* The paper presents interesting fundamental questions on the representational capacity of normalizing flows, which can help practitioners in their design choices of normalizing flows. \n* The authors clearly made an effort to try to make the proof sketches accessible. However, the proof sketches and the relation between theorems can be made much clearer. Improving along this axis would make the paper much more accessible to a wider audience.\n* The authors empirically validate some of their theoretical results.\n\n**Cons**\n* There is quite some room for improvement on the side of the empirical results. \n   - First, empirical results are obtained by optimizing with an objective that is not maximum likelihood but a regression objective. This makes the transferability of some of the results to flows trained with maximum likelihood (almost always the case) questionable. For instance, will the results on the different padding strategies in section 6.1 and appendix C2 still hold for maximum likelihood trained models? The argument for using the regression loss in 5.3 instead of maximum likelihood is also quite vague “...to minimize algorithmic (training) effects as the theorems are focusing on the representational aspects.” Does that mean that if you train with maximum likelihood you don’t obtain the same empirical results? \n   - Second, the results for learning an invertible linear mapping with affine flow models is only done for a very particular construction of invertible linear mappings: the elements of the invertible matrix are sampled from a standard Gaussian. For this particular case it indeed seems that the practical number of affine coupling layers needed to approximate an invertible linear mapping is lower than the suggested upper bound (of 47). However, it is unclear if this observation extends to other invertible mappings that are not random Gaussian matrices. \n   - Third, the empirical evaluation in section 5.3 could also be done with nonlinear affine coupling layers to show how this affects the practical results relative to the bounds that are claimed to also hold for this type of affine coupling layers.\n   - Finally, the conclusion that Gaussian padding works better in practice than zero padding is based only on experiments with two-dimensional toy examples. In higher dimensional cases such as image datasets it is unclear if this still holds, as dimensionality can potentially play an important role here. \n\n* The exposition and conditions for some of the theorems and how they relate to one another could be made clearer. For instance, how does the universal approximation without padding theorem (theorem 4) relate to the additional remark in section 5.3, where it is described that for a distribution generated by applying an elementwise tanh on a Gaussian random variable, this distribution cannot be modeled with a finite number of affine coupling layers? I appreciate that sections 4, 5, and 6 try to sketch the proofs of the theorems to give more insight to the reader. However, the proof sketches are not much clearer than the actual proofs in the appendices. I imagine some of the explanations could be made more accessible with visualizations. It would also be helpful for instance to relate theorem 1 and theorem 4 and their relationship. \n\nSome of the details of the theorems are a bit confusing:\n* In Theorem 2, why is only the case det(T)>0 considered? Could it also hold for invertible matrices with det(T)<0 such as a permutation with determinant equal to -1? Should in that case the diagonal matrices B and C have entries smaller than zero? \n* I don’t understand the paragraph directly below theorem 3. Nonlinear affine coupling layers (where the nonlinearity refers to the nonlinearity of the scale and translation networks) are more flexible than linear affine coupling layers, so I would expect that theorem 2 can indeed also hold for nonlinear affine coupling layers, but that in theorem 3 the bound could be different because the nonlinear version is more flexible. \n* The counting argument for the lower bound of K>=5 in theorem 3 is presented in a confusing way. In section 5.2, the number of parameters of a single coupling layer is indeed $d^2 + d$, so a product of $K$ coupling layers (either upper or lower triangular) is  $K(d^2 + d)$, and you would indeed expect 4 coupling layers to match the $4d^2$ parameters of the linear map. But the product terms in theorem 2 always consist of 2 coupling layers (one lower triangular $\\in \\mathcal{A_L}$ and one upper triangular coupling layer $\\in \\mathcal{A_U}$). So there the amount of parameters for a product of K terms would be $2K(d^2+d)$, leading to K=2 as an estimated sufficient amount based on parameter count alone, unless you assume that only one of the two coupling layers in each term is not the identity. I assume that the latter is the case as it would give you the freedom to represent the sequence of coupling layers as arbitrary combinations of upper and lower triangular coupling layers.\n* In Theorem 1, if g is not invertible, how can we be sure that the distribution induced by the non-invertible mapping g is a valid distribution?\n\nThe cons currently outweigh the pros for me, leading to the rating of 5, but I do think this paper could be a valuable contribution to the normalizing flow community. Therefore, I hope the exposition can be made a little clearer during the revision period so I can raise my score.\n\n**Minor comments/questions**\n* Normalizing flows don’t need to start from Gaussian latent distributions as stated in the first paragraph of the introduction.\n* Seems like $\\sigma$ is used both for the activation function of layerwise invertible feedforward networks as well as the standard deviation for the gaussian distributions in theorem 1. These type of double usages make the paper less readable.\n* Shouldn't the answer to question 1 be affirmative since you are confirming that such a distribution exists?\n* in the paragraph below theorem 1, should $\\Theta(k)$ and $\\Theta(d^2)$ be $O(k)$ and $O(d^2)$?\n* In definition 1, the scale and translation parameters of affine coupling layers are indicated with $g$ and $h$ respectively, but in some parts of the text, the authors refer to $s$ and $t$ for these factors (for instance just below theorem 3, and theorem 4). Please keep this consistent.\n* Please include masked autoregressive flows in related work on generative normalizing flows [2].\n* The related work in between the sections introducing the theorems and the proof sketches interrupts the flow of reading a little.\n* Second paragraph page 6: typo “stanard” → “standard”.\n* Just below lemma 6, should it be $\\mathcal{A_L A_U A_L A_U}$ instead of $\\mathcal{A_L A_R A_L A_R}$.\n* In appendix C2, the data distribution of the swiss roll is depicted as the two moons data distribution.\n\n\n[1] Huang et al. 2020, augmented normalizing flows: bridging the gap between generative flows and latent variable models. https://arxiv.org/abs/2002.07101\n[2] Papmakarios et al., masked autoregressive flow for density estimation. https://arxiv.org/abs/1705.07057", "extra_scores": {}, "extra_text": {}}, {"review_id": "GRNm3_tWGng", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "#### DESCRIPTION\nThis paper considers the representational ability of normalizing flows in terms of their overall size (depth, no. of parameters etc) and how they choose a partition for coupling layer transformations.\n\n#### DISCUSSION  \n\nWhile I think exploring explicit limitations of the representational ability of normalizing flows imposed by the invertible constraints and bipartite partitioning of coupling layers, I'm not sure that (i) the specifics discussed in this paper get to the heart of the matter, and (ii) the points that *are* made are hard to understand and stand behind. \n\nSpecifically, I have the following main concerns:\n\n\"Empirically, these models seem to require a much larger size than other generative models (e.g. GANs) and most notably, a much larger depth.\" -- what does it mean for one generative model to be \"bigger\" than another, or to have \"larger depth\"? Is it number of parameters, or memory cost? The number of transformations in a flow and the number of layers in a GAN are not really comparable. You could also argue that normalizing flows could be adapted to have a memory cost constant in their depth, since their activations can be reconstructed on the fly for backprop. \n\n\"Question 1\" -- the answer to this is yes, example: in R^2, the function f(x1, x2) = (x1, x1) (where x = (x1, x2) ~ N(O, I)) induces a distribution on the line x2 = x1 which cannot be represented by an invertible mapping. What you really mean to discuss is *to what extent* enforcing invertibility impacts representational ability, not *whether* enforcing invertibility impacts representational ability, because it does. \n\nI am finding it very difficult to understand what Theorem 1 is saying, other than that it's in some sense trying to formalize the fact the invertible functions impose representational constraints. Specifically: What does it mean for a network to have size O(k)? What is k? It seems to be defined as k = o(exp(d))? What does that mean? What does it mean for the depth to be k / p = o(exp(d)) / no. of parameters? Why is the number of parameters per layer p the same for every layer? It seems to me as if the statements here are vague and not well-defined.\n\n\"Question 2\" -- I don't understand the point of this question. Why is it worthwhile to have a result about how many affine coupling layers with a fixed partition are needed to compensate for the removal of a 1 x 1 convolution? From the Glow paper, the 1 x 1 convolution added increased the parameter count of their model by 0.2%, and the wallclock time for training increased by approximately 7%. Neither of these are prohibitive costs which would warrant careful examination of the necessity of the 1 x 1 convolution. \n\nLike Theorem 1, I'm also not sure of the meaning/point of Theorem 2. In particular, \"any applications of permutations to achieve a different partition of the inputs can in principle be represented as a composition of not-too-many affine coupling layers.\" How many is not-too-many? Even if we could be specific, why does it matter that we can compensate for the removal of 1 x 1 convolutions with more affine coupling layers? \n\nSections 4 & 5 & 6: I'm finding it very difficult to parse what's going on here. The sections are technically dense, draw on a wide range of formal results in passing, and it's hard for me to understand how the material is relevant or necessary. Moreover, why are there extensive proof 'sketches' in the main text at all? Where are the actual proofs?\n\nThe experimental results are toy, and I'm not entirely sure what they're trying to show. What exactly is happening with the padding? As in Huang et al (2020), are the authors now doing variational inference in an extended space? None of this is clear. \n\nIt would be remiss of me not to mention the fact that the paper has altered the margins of the ICLR template to increase the amount of material. For better or worse, an 8-page conference paper is the widely used format for machine learning publications. While I'm sympathetic that sometimes this can be an undue constraint, it provides a level playing field, and sharpening a message to fit within imposed limits is part of research. Deliberately altering the margins (i) makes the job of a reviewer more difficult because while reviewing they have to reason about which parts of the paper will be removed from the main text to fit in the final template, and (ii) removes the need for the authors to reflect on whether their message is focused enough. Content aside, the structure and layout of this paper could be significantly improved -- the abstract does not need to be multi-paragraph, the sweeping technical details are introduced quickly and poorly motivated, and I found the overall narrative confusing and difficult to follow.  \n\n#### EXTRA NOTES\n\n\"we can efficiently evaluate the likelihood of a data point\" -- the likelihood is a function of the parameters, not data.\n\n\"which model distributions as pushforwards of a standard Gaussian\" -- the base distribution in a normalizing flow is not necessarily Gaussian. \n\nIn section 2.2, computational constraints are not necessarily the reason for not using invertible weight matrices and invertible pointwise nonlinearities -- the O(d^3) determinant calculation can be sidestepped by parameterizing the weight matrix using e.g. an LU decomposition. \n\n#### CONCLUSION \n\nAs I mentioned at the beginning, I think an examination of the representational limitations of normalizing flows in terms of their overall size and how they are affected by a chosen partitioning may be worthwhile, but I feel as if this paper doesn't adequately address these questions, and what it does say is difficult to understand. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "1XNpk1hsHM", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper gives very thorough mathematical representation for two challenges related to normalization flows, namely model’s large depth and conditioning which relates to the smallest singular value of the forward map. Topic is presented in a very orderly and comprehensive manner. All variables and concepts are explained and presentation is clear. Text and appendices give proofs for everything that has been discussed and appendices extensive presentation of experiments. \n\nThe cons of the paper are that it positions itself for previous research quite loosely. The paper would be a good handbook on the mathematics of the subject, but it is unclear at which level the topic has been addressed in the previous research, although the related work is presented in a short section. Also, it would be interesting to discuss how the obtained results could be considered when e.g. modelling the complex distributions.     \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper studies three aspects of the representational capabilities of normalizing flows, with a particular focus on affine coupling layers. Normalizing flows are valuable generative-modelling tools, so advancing our understanding of their theoretical properties is an important research direction.

Reviewers #2 and #4 found the contribution of the paper significant without expressing major concerns, and so recommended acceptance.

Reviewer #3 reviewed the paper very thoroughly, and expressed some concerns mainly about the experimental evaluation. Most of their concerns were addressed in the rebuttal, so they recommended weak acceptance, recognizing the merits of the paper but also pointing out the potential for improvement.

Reviewer #1 was the most critical: they expressed major concerns regarding the significance of the contributions and the overall clarity of the exposition. Despite a long exchange between the reviewer and the authors, a consensus was not reached, so the concerns remain.

The discussion so far has led me to believe that there are potentially valuable theoretical contributions in the paper, however it's clear that there is significant room for improvement in getting the contributions across. Given the strong concerns expressed, the lack of consensus, and the clear potential for improvement, I'm unable to recommend acceptance of the paper in its current form. However, I do believe that the work has potential, and I hope that the discussion here will help improve the paper for a future submission.
Decision: Reject