Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper answers the question how complex inference models need to be to accurately estimate posterior distributions. The conclusion is when a latent Gaussian model with N parameters satisfies (1) strong invertibility, (2) 3-th smoothness, the posterior can be approximated by a deep latent Gaussian model with O(N) parameters. A special case is also given to show that strong invertibility is necessary to the conclusion.
main_review: This is a purely theoretical paper trying to solve a very interesting and important question, which is generally a good paper.  However, I still have some concerns and questions about it.

Pros:
1. This paper is well-written and intuitive. It's difficult to achieve that for a purely theoretical paper.
2. The proofs are reasonable. Sorry I only checked the main theorem and some lemmas and didn't find the time to delve into the proofs in the appendix.

Concerns and Questions:
1. The inference model is assumed to be a deep latent Gaussian model, which is not the case for VAEs. The structure looks similar to some hierarchical VAE but it's not the same. This heavily limits the usage of the conclusion in usual VAEs.
2. In remark 3, the authors mention that the case for layerwise invertible models is very simple. They argue that some convolutional NN contains operations that increase and then decrease the dimensions, which makes layers not invertible and necessitates the invertible rather than the layerwise invertible assumption. But why not regard the two layers as a single layer, which becomes invertible again? I guess it is not difficult to get a reverse of such a layer.
3. The paper mentions that Learning deep generative models more generally is harder for data on low-dimensional manifolds. This paper (https://arxiv.org/abs/2106.13746) gives some explanation why deep generations models can deal with some manifolds easily but fail on others. Can we use the method in your paper to analyze the problem as well?
summary_of_the_review: The paper is well-written and the conclusions are reasonable. But I still have some concerns about the too strong assumptions of the main theorem, which might limit the usage of the conclusion.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This purely mathematical paper investigates the important question of how does the necessary level of complexity of an inference subnetwork depend on the the complexity of the corresponding generative subnetwork, in a VAE model. The paper introduces a specific measure of invertibility, and uses it to show that a generative subnetwork that is sufficiently strongly invertible only requires an inference model at similar complexity, while some "non-invertible" generative subnetworks will require an exponentially more complex inference subnetwork. The paper provides a lengthy and comprehensive proof of both.
main_review: Pros:
- The idea of using Boolean permutations as a proof method in network analysis context in the presented manner appears novel to me.
- The said idea might well be useful to prove other network properties.
- The mathematics, to the extent that I could follow it, seems correct.
- The paper does seem to prove the claimed complexity properties of inference models in the "approximately invertible" and the "non-invertible" cases.
- The paper puts together an impressive amount of math to prove the points, with extensive details in the supplement (the latter of which, however, I did not have time to evaluate in detail)

Cons:
- The paper suffers from confusing structure and sloppy language at critical points. It starts with sweeping questions such as 'How to choose the architecture' and 'When is inference (much) harder than generation', but then actually focuses only on very specific and narrow parts of those wide questions. The wide questions are then followed by a moderately heavy load of math. The paper reads as a string of theorems and remarks, where the reader has to jump around to understand how the theorems relate to the overall points of the paper. The proof is somewhat complicated and it is difficult to confirm the derivation holds at every step (though I admit this final point may be a failure from my side).
- VAE basics, for example, are given considerable amount of space, but there is no ending summary or Conclusion to draw things together, which adds to the impression that the ultimate significance of the work is not clear.
- There is no empirical part nor clear indication of empirical usefulness of the results. Both theorem 1 and theorem 2 prove the *existence* of networks that satisfy the conditions. Could the authors help me to understand the connection to empirical significance, or should we simply approach this as a mathematical exercise?
- The final sweeping claim in the introduction, namely that the paper lends theoretical support to the idea that "learning deep generative models more generally is harder when data lies in a low-dimensional manifold" just seems inappropriate to me. I'm not sure the whole notion of 'learning more generally when data lies in a low-dimensional manifold' makes sense as an expression. Being familiar with the cited (Arjovsky, 2017), I believe I understand what the authors mean, but I don't see how their results really lend the said support to that idea. Could the authors explain this, or point to where is this explained?
- In terms of impact, first, it is not surprising that the complexity requirements of inference and generative subnetworks are similar in the typical case, and in fact, the authors acknowledge this, but present the value in this work for providing theoretical foundation for this "empirical wisdom". I find this work somewhat valuable in this regard, but I did not quite understand, do the theorems actually give us a way of telling, for a given network, whether it has the strongly invertible nature or not?
- Some of the citations are not entirely appropriate. E.g. in the first paragraph, the ideas cited for both (Betherlot,2018) and (Shen,2020) have certainly been presented before those papers came out; e.g., the modification of latent space has been investigated at least since [1] in a similar context.
- The very place in the text that could illuminate the significance of the results (Sec. 1) reads as "We identify...an aspect...: a notion of approximate bijectivity of the mean of the generative direction. We prove that under this assumption..." Forgive me, but what does it mean that one 'identifies an aspect' which turns into 'notion', and then 'proves [things] under this assumption'? This is just unnecessarily fuzzy, in striking contrast with the mathematical precision shown in some other parts of the paper.
- The results of Lipton & Tripathi (2017) do not show that "these architectures are invertible in practice" as the authors state. What they may have shown is that those architectures are *sometimes* invertible in practise. E.g. in GAN context, AFAIK the general inversion of CNNs is an open research problem. If I am wrong, I ask the authors to explain why.

[1] Salimans et al. 2016, Improved Techniques for Training GANs.


summary_of_the_review: The proofs in the paper appear correct, and at first glance, they appear relevant to generative models research community.
However, upon closer look, despite the commendable theoretical work, the paper seems to amount to proving the *existence* of a network of certain complexity, in the invertible case, and the *existence* of a generative subnetwork that only allows inference networks with pathological (exponentially growing) complexity. Without any guidance of how one could construct the networks under the said conditions, or measure how far we are from meeting those conditions, I am worried that the paper boils down into a mathematical exercise without considerable impact in this line of research.

I also had concerns about the sloppy wording of the claims in the introductory section, and the structure of the paper in terms of the order of how things are presented, and the lack of clear bottom line.

In combination, I lean towards rejection, but I may improve my score if the authors can convince me of the significance of the theorems, and if they manage a considerable rewrite of the introduction section. Given the considerable theoretical weight and intellectual import of the paper, I would encourage the authors to do so.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The authors of the paper start from a great initial question that connects the complexity of the encoder and generator of a VAE. It is reasonable to suspect that the complexity of one mapping would have an effect on the complexity of the other mapping.
main_review: Unfortunately, the exploration made appears to me mostly about something else. This whole paper doesn’t read like a paper about VAEs, or about DL, but rather about applying a conjecture by Katz & Lindell (2020), having to do with Boolean circuits, to the situation of VAEs.

In that regard, the situation studied about VAEs feels rather artificial because in practice we never deal with random mappings or with worst-case distributions. The whole edifice of deep learning is predicated upon assumption that patterns in the experimental data will play nicely with the inductive bias of neural networks. This does not invalidate the study of worst-case scenarios, but it makes it less interesting.

In fact, the whole paper rests upon the aforementioned conjecture coming from the world of cryptography, for which not much background is given. For all the reader can tell, that conjecture cited with reference to a book that came out in 2020, could be false. That would make this very paper completely void.

After having said all that, I’ll admit to my lack of familiarity with some of the techniques used by the authors despite being knowledgeable about VAEs.
summary_of_the_review: The paper starts with a good inquiry, but the answer provided is unsatisfying. It relies on a conjecture from another field which, even if proven true, would not make it all that useful.
review_title: null

Meta-review: All three reviewers viewed this paper as marginally above the acceptance threshold (6).

Most of the initial concerns of reviewers were around (a) the applicability of the theory to actual practical use cases and networks, and (b) the presentation and framing of the work, and scope of its results. There were fairly detailed responses from the authors: two of the three reviewers increased their scores after the author response. There's still some lingering questions as to how "real-world" relevant the theory is, but the consensus at this point is to accept the paper.

My primary concern for acceptance would be that the proofs techniques are based on Boolean circuits, and none of the reviewers (nor the AC) are particularly familiar with this, and thus the proofs in the appendix have been only lightly reviewed. The "impression" of all reviewers is of correctness.
Decision: Accept (Poster)