Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proves that log-concave distributions can be approximated by normalizing flows defined by affine-coupling models and starting from Gaussian distributions. The special feature of the result, distinguishing it from earlier universal approximation results for this type of flows, is that the constructed map is well-conditioned. The proof first approximates the target distribution using a Langevin dynamics, and then shows that this dynamics can be approximated by affine-coupling models. 
main_review: This is an interesting and technically complex paper that reveals some interesting connections between normalizing flows, Langevin evolution, and earlier research on Hénon maps as universal approximators for symplectic diffeomorphisms. While there are already several papers on universal approximation with normalizing flows, this paper poses and resolves the question of finding a well-conditioned flow (albeit under relatively restrictive conditions on the target distribution - log-concavity and Gaussian padding). The proposed (rather complex, two-stage) construction combines ideas of the Langevin evolution and earlier research on approximating Hamiltonian flows. The paper is clearly written and includes a sketch of the proof that explains its main points rather well. I think that the paper brings some novel ideas to the study of approximation properties of normalizing flows.     

If I understand correctly, the well-conditioning in the paper refers only to the full flow map, so that the elementary affine-coupling layers comprising the flow can potentially be ill-conditioned (or ill-conditioning can accumulate because of the large number of these layers)? 

I didn't quite understand at which point the Gaussian padding is used in the proof. Is it used in the Langevin convergence result (Lemma 1), because the target velocity distribution needs to be Gaussian?

Probable typos: the minus sign in the first equation in system (1), missing $\gamma$ in the covariance of $\xi_t$ in line 250.

Post-rebuttal: I thank the authors for answering my questions.




limitations_and_societal_impact: -
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proves a universal approximation theorem of well-conditioned affine coupling flows for log-concave probability distributions. This extends previous approximation results with ill-conditioned flows. The paper takes a different proof approach with previous works: it constructs an underdampled Langevin dynamics, which is a well-conditioned pushforward between the Gaussian-augmented data distribution and standard Gaussian. Then, the paper shows that affine coupling blocks can simulate the Langevin dynamic.
main_review: The most significant contribution of this paper is it brings in the powerful SDE tool to study affine coupling flows. The proof technique is novel. It's the first time I have seen such an approach. I think the method can be used for analyzing other problems, e.g., extended beyond log-concave distributions. I didn't check the proof in detail, but the idea seems valid. The quality of the work is good. The theorems and background knowledge are nicely organized. The presentation is clear.

In terms of significance, one limitation of the proposed approach is it seems to be limited to affine coupling flows, since the construction of underdamped Langevin dynamics is specially designed to meet the two-part structure of affine coupling flows. It would be more interesting if the authors can demonstrate the idea for other types of flows, e.g., residual flows.

Another result I would like to see is the practical implications of the theoretical result. Currently it is not discussed in the paper. For example, can the theoretical result guides us to improve the conditioning of affine coupling flows, or can the Langevin dynamics be used to construct more efficient flows?

The idea of ODEs and SDEs are also extensively used in Neural ODE, FFJord, residual flow, etc.. It is also interesting to see the connection between the proposed method and the neural ode family of methods. Can we compare their representation capacity / efficiency ?

Post rebuttal: I am satisfied with the authors' feedback regarding to the necessity of log-concavity and applicability to other types of flows. I'm increasing my score to 7.
limitations_and_societal_impact: This work does not have foreseeable negative societal impact.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: The authors study universal approximation with well-conditioned affine coupling networks. They proved that the log-concave distributions can be approximated by an affine coupling flow with a well-conditioned Jacobian. To prove this argument, they study the connections between stochastic differential equations, dynamical systems and affine coupling flows. In their construction, Gaussian padding was adopted, as suggested by the empirical observation from [Koehler et al., 2020]. 
main_review: Originality: The related works are adequately cited. The novelty of this paper is high. The universal approximation results in this paper, as mentioned in the above summary part, will certainly help us have a better understating of affine coupling networks from a theoretical way. I have checked the technique parts and find that the proofs are solid. I think this is a significant contribution to machine learning immunity. My only concern is that, the authors only consider the universal approximation for log-concave distributions, which make the contribution of this paper limited. It will be interesting to explore the universal approximation of affine coupling networks for more general distributions in the future.

Quality: This paper is technically sound.

Clarity: This paper is clearly written and well organized. I find it easy to follow.

Significance: I think the results in this paper are significant, as explained above.   
limitations_and_societal_impact: Yes, the authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, authors provide the first proof that well conditioned affine coupling flows can approximate any log concave distribution.The authors employ stochastic differential equations and structured dynamical systems to construct their proof, uncovering some unknown connections. 
main_review: Coupling flows have been one of the most widespread used members of the flow family; due to the easy of implementation and computation, they have attracted more attention than other variants. However, as mentioned elsewhere and pointed out by authors, the theoretical understanding of their representation capabilities have been limited. This paper provide the first satisfactory result to that front: well conditioned affine coupling flows can represent any log-concave density. 

Overall, the paper is very well written. I applaud the authors for their efforts to make a paper that is basically a long proof to be so readable. Clearly, the paper has been tailored to be as accessible to computer scientists as possible; I commend the authors for their efforts. 

I believe the paper has sufficient merit; a valid justification for the use of affine coupling flows is a welcome addition to the literature. Moreover, the proof technique and potentially help future analysis. 

limitations_and_societal_impact: I don't think this applies.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper proves that _well-conditioned_ affine-coupling-based normalizing flows can approximate any _log-concave_ distribution. The proof techinques used in this paper combine underdamped Langevin dynamics and methods from dynamical systems in a novel way. The actual result in this paper involves approximating, to arbitrary precision, a joint distribution comprised of the original target padded with Gaussian noise of the same dimension. Then, universality is implied by the fact that the marginal along the dimensions of the original target distribution must be equal.
main_review: Overall, I found this paper to be an interesting read and would recommend it for inclusion in the conference. I'll provide further details along the standard review axes below.

### Originality

Studying the approximation properties of $d$-dimensional normalizing flows by embedding in a $2d$-dimensional space is not entirely novel, but the result achieved and the techniques used to do so appear original as far as I am aware. I will note a couple omissions in the related work, however:
1. The term "normalizing flow" was actually coined in _Density estimation by dual ascent of the log-likelihood_  [Tabak & Vanden-Eijnden, 2010], with normalizing flows being further developed in the follow-up _A family of nonparametric density estimation algorithms_ [Tabak & Turner, 2013]. Although Rezende & Mohamed, 2015 and Dinh et al., 2014 may have popularized the notion of flows in the machine learning community, it would be remiss to say that the inception of the ideas were in these papers alone.
2. Two recent works, _Relaxing bijectivity constraints with continuously-indexed normalizing flows_ [Cornish et al., 2020] and _Understanding and mitigating exploding inverses in invertible neural networks_ [Behrmann et al., 2021] study the theoretical and empirical pitfalls, respectively, of using ill-conditioned normalizing flows. The former in particular notes that the (Bi-)Lipschitz constant of a normalizing flow -- and therefore its condition number -- must necessarily approach infinity if the flow distribution is to approximate a distribution with non-trivial topology to arbitrary precision. The latter provides a complementary empirical view of the matter, demonstrating that normalizing flows quite often display numerical non-invertibility when fully trained. Including these results in the related work may help bolster your motivation even further.

### Quality

Although I did not check this closely, the mathematical results in the paper appear to be correct. This paper does a good job of bringing together ideas from different fields to produce a proof. My one criticism here though is that the result is not looked at critically - it is only mentioned that the result is limited to log-concave distributions, without further discussions of the limitations of the paper overall which I've included in the Significance section of the review.

### Clarity

I found the paper to be clearly written, and I very much appreciated the intuitive proof sketches provided throughout.

### Significance

I think that demonstrating how to show the main result is the most important part of the paper, as opposed to the result itself. What I mean is that the combination of techniques provided in this work may allow others to prove stronger results about the approximation properties of certain classes of flows. I do not find the result itself to be particularly shocking, as log-concave distributions do not appear to be a particularly difficult class of distributions to approximate. Furthermore, this work does not really consider the practical implications of using normalizing flows for generic distributions, only noting that they can approximate log-concave distributions without blowing up. I would have liked to see some study or discussion on the practical implications of this result, as for now I cannot really think of any besides this paper possibly inspiring future works with its mathematical techniques.

### Miscellaneous Comments

- How restrictive is the condition $I_d \leq - \nabla^2 \log p(x) \leq \kappa I_d$? What happens if $-\nabla^2 \log p(x)$ has eigenvalues between $0$ and $1$, and how often might we expect this to occur?
- I find it quite counterintuitive that $\mathcal C$ can be made arbitrarily large by making $\epsilon$ arbitrarily small - can you comment on this further?
- Is it required, strictly speaking, to pass the proof to a $2d$-dimensional space instead of the original $d$-dimensional space, and why? Is there some smaller dimension where things might still work properly?
limitations_and_societal_impact: I think there could have been more discussion about the practical implications of the results beyond just stating that likelihood-based training requires stability in the flow. How can we use the insights here to train flows better? Can we make some recommendations for generic distributions, or can we only say that normaliizing flows can stably approximate log-concave distributions?

I have no concerns about the societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper gives a proof of universal approximation by well-conditioned (affine-coupling) normalizing flows of arbitrary log-concave distribution. The main difference from previous results on universal approximation by such flows is that transformation is well-conditioned. The proof is constructive and potentially allows to extract the number of flow layers required to achieve given accuracy.
main_review: The paper considers the question of  universal approximation property of affine-coupling normalizing flows. Previous results on this subject established universal approximation for ill-conditioned flows that have their condition number diverge with approximation quality. The authors attack the problem by restricting the target distribution to be log-concave with bounded log-probability Hessian. Using SDE convergence results they define an ODE (equivalent to Langevine SDE), that provides approximate distribution via a well-conditioned transform. Further, they extend a known equivalence (Henon map <-> Simplectic flow) to recast previous approximation into the form of a generalized Henon map. The discrete version of this map has the form of a sequence of (pairs of) affine-coupling flows. This allows the authors to establish the universal approximation property of affine-coupling normalizing flows.


The contribution is original and very relevant for practical applications. The paper gives theoretical grounds for using padding of data distribution with Gaussians for the purpose of approximating it with well-conditioned NF.
The paper is well written, giving most definitions and qualitative proofs in the main text, which makes it easy to follow. The authors did a really good job in presenting the complex proofs in a very limited space.


Remarks:
1. in line 174 the equation U(x) >=	\lambda I is a bit confusing, because U is scalar and I is a unit matrix
2.  Even though it may be not physically possible given space constraints, but it would be helpful to add a diagram, representing different pieces that were used in the proof, with e.g. arrows showing connections/equivalences.
3. I found it hard (not being as expert in the material) to track the connection between "condition parameters" k (line 107), lambda (line 174) and rho (eq (2)): may be adding remarks on how they connect to each other around the places where they are used could help with that.
4. Finally, even though the number of flow layers required to achieve given accuracy can be extracted from the proof, having an explicit formula would be helpful for practitioners.


****************************************************
Post-rebuttal

I'd like to thank the authors for their response and will keep my already high score the same.

limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: Authors answer the question: "Can well-behaved distributions be approximated by an afﬁne coupling ﬂow with a well-conditioned Jacobian?" They answer by the affirmative, proving that log-concave distributions belong the the class of distributions that can be approximated by such flows, if the input distribution is padded with independent Gaussians.
main_review: 
## Strengths
The main strength of this work is its theoretical soundness and the ability to overcome the limitations of previous work, namely the ill-conditioned Jacobian yielded by their assumptions. 
The bound only depends on properties of the distribution (and does not worsen as epsilon gets small, as opposed to Koehler et al., 2020), which is satisfying.
Additionally, the independent Gaussian padding assumption that is made backs previous empirical results that have shown their usefulness in terms of conditioning of the flow.

## Weaknesses
Perhaps that are two minor limitations in this work that could potentially be alleviated.
1/ Relation with practical use of affine-coupling flows. This entire approach is based on augmenting the space with an auxiliary variable $v$ (via padding). It has apparently been shown that in practice it does indeed help with the conditioning of the flow (Koehler et al., 2020), yet I don't believe that it is a common practice. It would be nice to remind us what does better conditioning brings for practitioners. Is this work claiming that we should in practice pad the input?
2/ Discussion of other normalizing flows. I may be missing something, but it seems that From Equation 11 a similar result could be proved for continuous normalizing flows and similarly for Equation 12 and residual flows.
3/ Relationship with optimal transport map.
If I understand correctly, this work is claiming that afﬁne coupling ﬂows are universal approximator of the flow-map from underdamped Langevin dynamics. Why are underdamped Langevin dynamics a natural choice? As opposed to the optimal transport map for instance, which seems quite natural as Theorem 1 is stated in terms of an upper bound on the Wasserstein distance. Is it the same map with some assumptions? Is there any empirical evidence that in practice afﬁne coupling ﬂow approximate this Langevin flow-map?

## Clarity
The paper is rigorously written and quite well organized. I believe nonetheless that the flow could still improved to expand the audience of the work. In particular, Theorem 2 could need a bit more background or explanation. Also it is a bit unclear why and where we need Hénon maps. More generally, as Section 5 is a sketch of proof (the full proof being in the appendix), it would be worth appealing perhaps a bit more to the intuition of the reader at times (even though I acknowledge there are already some good effort on that regard).

## Relation to prior work
It would be perhaps relevant to mention theoretical work on the representational capacity of other class of normalizing flows (e.g. Huang et al. 2020).

## Additional feedback
89: Not clear how `underdamped Langevin dynamics' relates to log-concave distribution from this sentence.
142: "don't"
166: Shouldn't this be stated as a proper result?
168-169: This intuition is useful. The connection with the Gaussian padding (as a Gaussian prior for the velocity) could be stressed.
183: It would be useful to briefly explain why L is an upper bound of the KL divergence.
282: Is there a practical way to compute the value of $\tau$? That can be useful as it informs us on the number of layers required.
297: Why are these functions polynomial in $\cos(\Omega t)$ and $\sin(\Omega t)$?
306: Would be quite useful to write explicitly the associated non-linearities $s,t$ for both layers. Is appears that $s$ is always of the form $s=(I_d + \tilde{s})$ due to the Euler discretization. 

limitations_and_societal_impact: I wouldn't say that the limitations of this work are clearly discussed.
review_title: null

Meta-review: The paper demonstrates that log-concave distributions can be well approximated by well-conditioned affine-coupling flows with Gaussian base density.

This paper is clearly written and technically sound. It provides novel insights and interesting connections between normalising flows, Langevin diffusions, Hénon maps and their (universal) approximation properties.
Decision: Accept (Poster)