Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studied the expressive power of models composed of invertible flows and injective embeddings. First, this paper defined the concept of the Embedding Gap as the measure by which a model can approximate an embedding with low-dimensional support. Then, this paper defined the concept of MEP as the ability to approximate the target embedding arbitrarily small in terms of the Embedding Gap. This paper showed that when invertible layers have the MEP properties and the first layer is a distributively universal approximator (and some additional assumptions), the model is a universal approximator in terms of 2-Wasserstein distance (Theorem 1). Finally, this paper gave a method to compute the inverse transformation of an injective layer with a special form of linear transformation and ReLU nonlinearity. (Theorem 2).
main_review: # Post-rebuttal comments (11/29/2021)

I am pleased by the authors that they considered my comments sincerely and revised the manuscript. The updated paper improved the readability. Still, I feel the organization of this paper would have room for improvement. Regarding Lemma 2, I think it improved the applicability of the main theorem.

# Initial Review
【Strength】
- [1] A new measure MEP is proposed for evaluating how much a model can approximate distributions with support in low dimensional manifolds.
- [2] This paper used the concept of MEP to derive the universality of many existing models in a unified manner.

【Weakness】
- [1] I have several questions about the correctness of the statements and proof of the theorems.
- [2] Discussions related to topological obstructions might be hard to follow for those unfamiliar with the (differential) topology.

【Correctness】
- [1] I have several questions about the statements and proof of the theorems.
  - Theorem 1, Cororally 1
    - [1-1] If we read the statement literally, the statement trivially holds by setting $F_i = F$ for all $i$.
    - [1-2] I think this theorem has two definitions of $\mathcal{F}$: the class defined in Lemma 2 and the set of networks of the form Eqn.1 satisfying Point 1--3. Are two $\mathcal{F}$'s different?
    - [1-3] The output dimension of functions in $\mathcal{T}_{\ell}^{n_\ell}$  looks inconsistent. On one hand, according to (1), $\mathcal{T}_{\ell}^{n_\ell} \subset C(\mathbb{R}^{n_\ell}, \mathbb{R}^{n_{\ell}})$ . On the other hand, according to Point 2, $\mathcal{T}_{\ell}^{n_\ell}$ has the $n_{\ell + 1}, n, n_\ell$ MEP, which implies that $\mathcal{T}_{\ell}^{n_\ell} \subset \mathrm{emb}(\mathbb{R}^{n_\ell}, \mathbb{R}^{n_{\ell+1}})$. 
    - [1-4] Similar inconsistency happens to $W$ in Cororally 1. The definition of $B_{K, W}(F, E_i)$ implies $W\subset \mathbb{R}^{o}$, while $\mathcal{E}^{n, o} \subset \mathrm{emb}(W, \mathbb{R}^o)$ implies $W\subset \mathbb{R}^{n}$.
    - [1-5] P.17, Proof of Theorem 1: The proof picks $\mu'$ such that $W_2(F_{\#}\mu, E_{\#}\mu') < \epsilon_1 / 2$ . However, I think it is not possible in general. From Lemma 1 Point 5, we only know that $\inf_{\mu'} W_2(F_{\#}\mu, E_{\#}\mu') \leq \epsilon_1$. There is possibility that $\inf_{\mu'} W_2(F_{\#}\mu, E_{\#}\mu') > \epsilon_1 / 2$.
  - Lemma 2
    - [1-6] P.15: According to Definition 3, $W$ must be the closure of an open set of $\mathbb{R}^o$. Therefore, as long as $W$ is non-empty, there exists $w \in W$ and a ball $B$ centered at $w$ such that $B \subset W$. However, $W = K \times \{0\}^{o-n}$ does not satisfy the condition when $K\not = \empty$  and $o > n$.
  - Lemma 7
    - [1-7] P.18, (62): What is the definition of $\nu$?
    - [1-8] P.19: I want to clarify what does Assumption 2 mean. Does it mean there exist calculation procedures for computing the quantities $\log |\det \nabla R_\ell (x_{n_\ell})|$ and $\log |\det \nabla T_\ell (x_{n_{\ell+1}})|$ ? Or does it assume the existence of these quentities (e.g., differentiability of $R_\ell$ and $T_\ell$ and $\det \nabla R_\ell >0$) ?

【Technical Novelty And Significance】
- [1] This paper defined a new measure for measuring the ability of a model for approximating a distribution with support in a low-dimensional manifold. In this respect, the paper is novel. In addition, using this measure, this paper showed the distributional universality of several existing models. Therefore, I think this measure is useful, and introducing it is significant.

【Empirical Novelty And Significance】
- [1] This paper is does not have numerical experiements.

【Detailed Comments】
- [1] P.3: The family of functions $\mathcal{R}_l^{n_{\ell-1}, n_\ell}$ from $\mathbb{R}^{n_{\ell-1}}\to \mathbb{R}^{n_{\ell}}$. : I think this sentence is not a complete sentence and needs rewriting.
- [2] P.3 (R2):  ... , and $W$ is a convlution kernel ... : $W$ → $w$
- [3] P.4: We call a function $f$ an embedding and denote if by $f$ ... → denote it by $f$
- [4] P.4, Definition 3: $\|h\|_{L^\infty(X)} =\mathrm{esssup}_{x\in X} \|h\|_2$ → $\|h\|_{L^\infty(X)} =\mathrm{esssup}_{x\in X} \|h(x)\|_2$
- [5] P.4: When I read the paper for the first time, I could not understand why the inequality $\inf_{\mu_0 \mathcal{P}(W)} W_2 (f_{\#}\mu_n , g_{\#}\mu _o) ≤ B_{K,W} (f, g)$ in P.4 is true. If I understand correctly, it is later shown as Lemma 1 Point 5. So, I would suggest referring to the Lemma when it first appears in P.4.
- [6] P.5: I think it is better to write the definition of equivalent.
- [7] P.5: This is because ... consider for example the exotic spheres from MIlnor (1956): I think those who are not familiar with differential topology may find it difficult to understand this sentence. It would be better to write that what the exotic sphere is (i.e., a topological space that is homomorhpic to but not diffeomorhic to the (hyper)shpere).
- [8] P.4, Definition 3, P.6, Definition 4: In the definition of $B_{K, W}$, $W$ is assumed to be the closure of an open set. However, Definition 4 does not assume so. I am wondering why we need this assumption.
- [9] P.7: This paper used both $\subset$ and $\subseteq$. Does $\subset$ mean $\varsubsetneq$? Or are they just notational inconsistency?
- [10] P.7, Lemma 2: I guess the $\sup$-universal approximator is the concept defined in Techima et al., (2020). So, we need the reference to it.
- [11] P.7, Theorem 1: The definition of distributionally universal is not presented.
- [12] P.8, Lemma 5: universalif → universal if (add a space)
- [13] P.8, Lemma 5: there exists a $f\in \mathcal{F}$ → I think we do not need the indefinite article "a" here.
- [14] P.8, (17): $E_i \circ E_i' \circ T_{i\#}\mu$ → $E_i \circ E_i' \circ T_{i\#}\mu'$.
- [15] P.8: The crux of the problem is ... $\mathcal{R}$ layers when $\mathcal{R}$. → Remove the last "when $\mathcal{R}$" 
- [16] P.8: a least squares solution → a least-squares solution
- [17] P.9: For (R3) we have the following result ... : I have a question about this sentence. Since the definition of $R$ in Definition 6 and Theorem 2 is different from (R3), results here are not directly related to (R3).
- [18] P.9: Write the $B$ and $D$ in Definition 6 (I guess it is the same as those in (R3)).
- [19] P.13: The architecture described in Eqn. 22 ... which are not studied here.: I am afraid I could not understand this sentence, especialy the part after "applies to ...". Could you reconsider the sentence?
- [20] P.20: The authors shows that this is possible ... → The authors show ...
- [21] P.20: Further, provided that ... is satisfied, than the entire network can be ... → then
summary_of_the_review: I set the Correctness score to 2 as I have several questions about the correctness of the theoretical part of this paper (see【Correctness】Section). If these questions are solved, I will increase my Correctness score. Regarding technical novelty, I think this paper gave novel tools for analyzing the expressive power of flow models. Introducing these tools is significant as they encompass many existing models.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: In this paper, the authors studies flow models by a newly developed approximation measure when the data is on a low-dimensional manifold. Specifically, they consider an architecture that alternates a bijective function with the same input and output dimensions, and a function with a larger dimension at the output. There are several successful methods for this, but the globally invertible flow is not well understood. To address this problem, this work shows the approximate properties of the flow architecture. Specifically, they show the approximation accuracy of the models with distributions that have a certain manifold as their support. In doing so, they proposed a new notion of embedding gap to evaluate the manifold embedding. This may allow them to represent cases that cannot be represented by existing topologies. In addition, they defined a value of MEP, which allows us to evaluate the approximation capability under different topologies. This establishes the validity of evaluating the performance for each layer.
main_review: The paper proposes the concept of an embedding measure reflecting the different topologies, then studies an approximation property of the flow models with distributions with low dimensional support under it. On the positive side, the paper is written in detail, with plenty of examples and discussion.

One question is that it seems to me that it could be written more clearly what kind of problem was being tackled. The motivation for wanting to deal with different topologies is explained, but it seems unclear to me what difficulties were solved as a result. For example, what conclusions can be drawn compared to simply using the Wasserstein distance? Is it possible to construct a mathematical statement whose universal approximability is compromised when existing measures or topology are used? Moreover, it is possible to show that the topology and measure developed in this paper are convincing phenomena, which can be validated by experiments with real data?
summary_of_the_review: Well written. But the contribution could be clearer.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper analyzes some theoretical properties of injective normalizing flows. In particular, it focuses on universal approximation and (to a lesser extent), layer-specific projections, bayesian uncertainty quantification, and black-box recovery of network weights.
main_review: ## Strengths

* The paper makes good strides in the understanding of injective normalizing flows.

## Weaknesses

* The results feel weak. This is best exemplified by the class $\mathcal{I}(X, Y)$, which is a very strong assumption to make on our target embedding. This class is **very** close to the core construction in Brehmer and Cranmer 2020, so a result showing universal approximation does not feel particularly illuminating. In particular, since members of $\mathcal{I}(X, Y)$ are $\Phi \circ R$, where $R$ is affine and $\Phi$ is a normalizing flow, do the results not follow simply by approximating both? This feels rather straightforward. Furthermore, while the paper claims that it has to account for just topological obstructions, this class of functions limits for more than just that. For example, a map from $\mathbb{R}^n \to B_0^n(1) \subset \mathbb{R}^m$ is correct topologically but it is not considered in the proofs. 
* The paper heavily invokes the universality and other properties of its constituent neural networks in the proofs. In particular, most of the proofs are simple applications of universality, follow directly from definitions, and/or rely on canonical tricks in the field (e.g. convolution with a mollifier). Along with the above observation, this lack of depth in the proof gives me the impression that not much real insight is being gained.
* The paper, as written, is very confusing. This is important as these issues significantly hamper the accessibility of the paper. I would suggest that the authors make a thorough pass through the paper to clear up these issues. I included some of the major ones, but there are certainly others.
    * There are many typos throughout, even in the abstract.
    * There are very poor notational conventions. For example, in Theorem 1 the $\mathcal{F}$ is overloaded.
    * The paper could be better structured. For example, the purpose for the embedding gap and MEP are not made clear; in particular, they are introduced with almost no motivation. Explaining why one has to leverage these constructions would help readers make sense of why they are introduced this way. Other sections are introduced rather strangely (e.g. the topological obstruction section is motivated before the section and leads directly into the definition of MEP without pause).
    * Most of the intermediate lemmas used to prove the theorem have little reason for being in the main paper. For example, Lemma 1 just proves basic properties of the definition and is unused except for in the appendix; it is not a main result and its purpose can not be understood unless one dives into the details of all proofs.
    * I was also confused about the previous work section. In particular, it seems very strange to me that the discussion about the core architectures that the paper prove are universal were moved to the appendix, while general inverse problem applications were given several paragraphs.
* The other results are very ancillary and oftentimes not explored/explained thoroughly. In particular, the last three results seem unrelated (and furthermore do not provide any more real insight). In particular, Section 3.4 (the results on layerwise projection) should be tested empirically. Appendix D.2 (on bayesian uncertainty quantification) is a straightforward application of standard log probability arguments. Finally, Appendix D.3 (the results on black box estimation) seems incomplete. There is no proof for Lemma 8, and I found the last paragraph, which is also one of the few that talks about the current work rather than Rolnick & Kording (2020), to be very confusing.

## Small Stuff

* The links to the lemmas are broken.
summary_of_the_review: While I believe the core idea and motivation are strong, I found the execution to be rather lackluster. In particular, I have questions about the core result (universality); in particular the function class they approximate seems very weak. I also found the presentation very confusing and hard to follow. Finally, the other experiments do not fit the overall narrative and are often underdeveloped.

UPDATE
----------
Lemma 2 alleviates my main concerns. I am greatly pleased by the author response.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper analyzes neural networks composed of bijective flows and injective expansive elements and showed that they are universal approximators of a large class of manifolds. A new mathematical notion called the embedding gap is proposed, which measures how far one continuous manifold is from embedding another. 
main_review: The paper is theoretical and mathematically fruitful. The embedding property discussed here is an important geometric property and should be useful in understanding the structure of neural networks. The write-up is a little bit too abstract and mathematical. It would be great if the authors can use a more understandable way to present their results in order that the work can reach a larger audience. 
summary_of_the_review: (1) Good work. Mathematically profound and results may have potential applications;
(2) Presentation too mathematical and might reach a larger audience if it can be revised to be more understandable.
review_title: null

Meta-review: First this is the seed for a  very good paper on approximating manifolds and densities using injective flows.

Reviewers have done an admirable effort reviewing the paper giving detailed reviews and suggestions to improve the theory and  corrections  that resulted in an improvement of the paper during the rebuttal/ revision phase.

Unfortunately the paper still needs major rewriting and organization to be accessible by other readers, and should undergo another round of review in its last polished version to further vet the correctness of some of its claims as explained below .

The paper was discussed at length among reviewers and the AC and here are the suggestions to improve the paper. 

* Implementing Reviewer 4sjW suggestion w.r.t  to the narrative and adding explanations to improve the readability and accessibility  of the paper. 

* Another concerns were raised by reviewer eR1p  in the discussion  regarding the correctness of Theorem 1 and Corollary 1. " The proof of Corollary 1 is so rough that I could not confirm its correctness. For example, the functions $r$ and  $f$ are undefined."  Please revisit the proof of this Corollary. Theorem 1 builds on Lemma 7 point 5.  In point 5 of Lemma 7 :"The embedding  $r$ depends on $\epsilon$ , hence so is the measure $\mu$.Therefor the statement  $W_2(g \mu',f \mu)< B_{K,W}(f,g) + \epsilon$ for all $\epsilon$, does not imply that  $W_2(g \mu',f \mu)< B_{K,W}(f,g)$. One solution can be by  building a sequence of measures that would converge to that measure and see if the argument goes through. 

 We encourage the authors to implement all the feedback  and suggestions of the reviewers and to submit this interesting work to an upcoming venue.
Decision: Reject