Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 3: Clear rejection
review_content: #### DESCRIPTION
This 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.

#### DISCUSSION  

While 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. 

Specifically, I have the following main concerns:

"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. 

"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. 

I 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.

"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. 

Like 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? 

Sections 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?

The 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. 

It 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.  

#### EXTRA NOTES

"we can efficiently evaluate the likelihood of a data point" -- the likelihood is a function of the parameters, not data.

"which model distributions as pushforwards of a standard Gaussian" -- the base distribution in a normalizing flow is not necessarily Gaussian. 

In 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. 

#### CONCLUSION 

As 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. 
review_title: A potentially worthwhile topic, but questionable execution. 

final_score: rating: 7: Good paper, accept
review_content: 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. 

The 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.     

review_title: The paper gives very thorough mathematical representation for two challenges related to normalization flows,but it is a bit unclear at which level the topic has been addressed in the previous research.

final_score: rating: 7: Good paper, accept
review_content: 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.  

This 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. 

Although 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:

1- 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. 

2- 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. 
review_title: This paper studies theoretically the effects of depth and conditioning in normalizing flows. 

final_score: rating: 6: Marginally above acceptance threshold
review_content: **Summary**
This 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.
Their 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.


**Pros**
* The paper presents interesting fundamental questions on the representational capacity of normalizing flows, which can help practitioners in their design choices of normalizing flows. 
* 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.
* The authors empirically validate some of their theoretical results.

**Cons**
* There is quite some room for improvement on the side of the empirical results. 
   - 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? 
   - 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. 
   - 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.
   - 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. 

* 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. 

Some of the details of the theorems are a bit confusing:
* 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? 
* 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. 
* 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.
* 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?

The 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.

**Minor comments/questions**
* Normalizing flows don’t need to start from Gaussian latent distributions as stated in the first paragraph of the introduction.
* 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.
* Shouldn't the answer to question 1 be affirmative since you are confirming that such a distribution exists?
* in the paragraph below theorem 1, should $\Theta(k)$ and $\Theta(d^2)$ be $O(k)$ and $O(d^2)$?
* 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.
* Please include masked autoregressive flows in related work on generative normalizing flows [2].
* The related work in between the sections introducing the theorems and the proof sketches interrupts the flow of reading a little.
* Second paragraph page 6: typo “stanard” → “standard”.
* 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}$.
* In appendix C2, the data distribution of the swiss roll is depicted as the two moons data distribution.


[1] Huang et al. 2020, augmented normalizing flows: bridging the gap between generative flows and latent variable models. https://arxiv.org/abs/2002.07101
[2] Papmakarios et al., masked autoregressive flow for density estimation. https://arxiv.org/abs/1705.07057
review_title: review of Representational aspects of depth and conditioning in normalizing flows

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