Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 6: Marginally above acceptance threshold
review_content: Summary

This paper proposes the conditions for the invertibility of deep generative models, and two pursuit algorithms for inverting them. The idea is based on sparse representation theory, applied on layer-by-layer inversion. The authors claim this to be the first work that provides provable guarantees of inversion for general non-random neural networks.

This is a very solid piece of work, with significant contributions on both the theoretical and practical sides. However, the impact of this work might be limited by the sparsity assumption, which is central to this work. It is unclear whether this holds in more general settings, especially for very deep models trained on large scale datasets.

Pros
1. It is overall clearly written and well-structured.
2. This work is built on a solid theoretical foundation. It provides interesting connections between neural networks and signal processing / convex optimisation.
3. This work relaxes the assumptions in previous work [1], which makes it more relevant in practice.

Cons
1. It is unclear how well does the sparsity assumption in theorem 1 hold in practice for trained models, which may limit the impact of this work.
2. The claims of provable guarantees for inversion is exaggerated, as it only applies to Algorithm 1, which relies on an oracle to provide the true supports of all hidden layers. There is no such guarantee for the more general Algorithm 3.
3. The experiments are limited to toyish and simple dataset. They are unlikely to capture the statistics of e.g., natural images that are practically more relevant.

Other comments and questions:

1. How to reconcile the difference between the special case of theorem 1 with random matrices (the paragraph above theorem 2) and theorem 2?
2. At the end of page 2, the complementary S^c_{i+1} is used before it is defined after eq. 5.
3. What is the distribution of the random input signal used in section 6.1? How is it chosen?
4. It might be helpful to summarise the sparsity assumptions from theorem 1 in the abstract or introduction, so that the limitation of the analysis and method is more clear for readers.
5. For gradient descent baselines, it worth considering (at least discussing) algorithms that jointly train the model with gradient descent (e.g.,  [2], [3]).

[1] Inverting Deep Generative models, One layer at a time, Lei et al. 2019
[2] Optimizing the Latent Space of Generative Networks, Bojanowski et al. 2017
[3] Deep Compressed Sensing, Wu et al. 2019

review_title: Review

final_score: rating: 3: Clear rejection
review_content: Clarity:
The paper is relatively clearly written except for the experimental section. 

Originality:
The content of this paper is not novel. 

Significance:
The claimed contribution of this paper is not significant. 

Cons:

This work tries to rigorously characterize the conditions for a rather intuitive task (reconstruction). There are a few serious issues around it. 

First, without having the learned weights satisfying certain conditions exactly, the theorems (e.g. Thm1) are way too conservative, i.e. the bounds are too loose in order to catch all corner cases. In addition, in reality, the activations are not necessarily sparse, especially for generative models. The combination of these caveats make these theorems' indications of little meaning. 

Second, in reality, we use much more complex architecture (CNN, attention, ReLU, Normalization) but these theoretical works can't easily go beyond simple MLP with ReLU, making these results even less meaningful. 

Thirdly, despite all the above, it is hard for me to reason why the theorems are significant in anyway in the context of ML, e.g. why uniqueness is important. I can understand the significance of existence and uniqueness in the context of differential equation but not ML. 

Other comments:
What is "sparse representation theory"? I know "sparse representation", and "representation theory", but not sure about "sparse representation theory".

Lack of novelty: the proofs are direct extensions of existing compress sensing literature. 

Experiments: 
-the experimental setups are quite contrived and not optimized for model performance but for the papers' plots. E.g. a larger scale b etter designed MLP can model MNIST dataset quite well (e.g. 4 layers of 1024x1024 with LeakyReLU)
-the evaluation metric is suboptimal. Eventually, we want to measure the recovered signal, not the latent code error. 
review_title: A theorem providing sufficient conditions of NN invertibility and a pursuit inversion method on top. 

final_score: rating: 7: Good paper, accept
review_content: In this submission, the authors study the inversion of ReLU networks (where the output of the network is subject to an invertible activation function).  This is an important task, for example for inverse problems using generative priors.  The authors introduce spark-based conditions for the invertibility of each layer of the network, leveraging sparsity that is induced by ReLUs.  The authors also introduce a novel layer wise inversion algorithm and provide provable recovery guarantees in both noisy and noiseless settings.  Empirical results demonstrate the superiority of the proposed algorithm relative to baselines for inversion in particular parameter regimes.  

Theorem 1 on invertibility/uniqueness is a significant contribution in that it permits an invertibility guarantee for neural networks without random weight assumptions.  Previous works involved weights coming from particular distributions.  Theorem 3 is significant because it establishes exact-noiseless recovery or stable-noisy recovery of an inversion algorithm without assuming random wights or growth rates on the network widths.  The authors present a clear and sophisticated algorithmic implementation, where different numerical approaches are used at each layer of an inversion process.  

There are a few minor issues the authors should fix upon revision:
(1) In Section 2, the authors should state that n_{L+1}=n.  
(2) It is not clear whether the authors are simply restating Theorem 2 from Foucart and Rauhut or whether this is a novel contribution.  The connection between the Theorem and the preceding paragraph needs to be clarified.  It appears to the reviewer that Theorem 1's conditions in the random case are more restrictive than Theorem 2's conditions (by a factor of 2).  
(3) In Section 1.1 paragraph 2, the authors write that they relax expansion assumptions as to rely only on the expansion of the number of non-zero elements.  The commentary on this point during the results sections could be more thorough.  The lines above Theorem 2 indicate that in the random case, the sparsity levels must grow by approximately a factor of two at each layer.  The paper does not say so, but this condition requires that the network widths are larger than a particular geometric sequence with growth rate 2.  I believe this statement also holds true in the non-random case as well.  Please add commentary to this effect after Theorem 1. 
(4) Defn 3: coherent -> coherence
(5) Theorem 3: epsilon_i isn't defined. It is defined within Algorithm 1, but this should be clearly pointed out.

review_title: Theoretical Recovery Results for ReLU network inversion without random weight assumptions

Meta-review: The reviews are a bit mixed, so the AC independently examined the submission as well. While the authors' response helped clarifying some issues, the draft would still need some major revision, especially the motivation and the experiment part. Here are some concrete suggestions:

(a) The problem definition in Eq (1) is already problematic, as the authors term the least squares reconstruction as an "inversion." When exact reconstruction is not possible, one needs to question the choice of the 2-norm here: why 2-norm and what happens if we change the norm? How does this choice of norm enter the proof and the theorem statements? The uniqueness, as pointed out by one of the reviewers, requires further elaborations: It is not clear that for applications like image denoising or impainting it is necessary to have a unique latent vector, if all one cares about is good reconstruction.

(b) The authors need to explain the motivation of the "inversion" problem better, in the context of generative models. In generative models, G pushes a distribution p on R^{n_0} to q on R^n. If both p and q have nontrivial support and n_0 < n, the map G can be highly irregular and the reconstruction problem can be very ill-conditioned. Putting assumptions on G (such as incoherence) might heavily constrain what kind of distributions q we can learn. This trade-off was hardly discussed. In fact, if we take n_0 = n, then there exist normalizing flows that can learn any distribution q and that can be trivially inverted. If one is interested in inversion, why not use a universal normalizing flow? 

(c) The authors mentioned a few possible applications (image denoising, compressed sensing, image inpainting) of the inversion problem, but none of them (to my best knowledge) relies on modelling the underlying distribution. There are also classic algorithms for each of these applications. It would be much more convincing if the authors could explain why a deep generative model is advantageous for these applications and compare the proposed algorithms on standard benchmarks of these applications. The AC agrees with the reviewers that the current experiments are a bit toy-ish (which is not wrong by itself but does require a bit more elaboration when the motivation is in question).

(d) The significance of Theorem 1 requires further elaboration. How does one verify its conditions? How often does a trained network satisfy these conditions? How do these conditions restrict the expressiveness of the underlying model? Some of these questions were asked in the reviews but regrettably the authors largely dismissed them. Results like Theorem 2 also require further clarification: what does random weight mean for a generative model? The authors seemed to only care about inversion while completely ignored the expressiveness of a generative model. As a trivial example, one could take a linear network, with regularization we can always invert (in the sense of the authors' definition) the signal. Why is this any different from (if not better than) the authors' results?
Decision: Reject