Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary: 
Inverting a deep generative model with the ReLU activation function is very important. The paper studies injectivity of neural networks, which improves inference in GANs. Notably, the paper presents the directed spanning set (DSS), which is the core of all theoretical results. Some conditions for layerwise injectivity are also presented. Experiments verify that injective GANs improve inference. 
 
Strengths: 
+ Injectivity produces invertibility for ReLU networks. The paper defines the directed spanning set (DSS) to construct layerwise injectivity, which is very useful. 
+ Some conditions for injective networks are presented. 

Weaknesses: 
- The paper is not clearly written, making it is hard to follow. There are two main reasons. First, the motivation of directed spanning set (DSS) is not clear. When Wx=y has multiple solutions or Wx<0 has solutions, ReLU(Wx) will precludes injectivity, where y>=0 is a constant. Are the two cases related to DSS? Second, the notations are confusing. For example, W is a matrix and is also a set. w is a row vector, while z and b are column vectors. I is an identity matrix and is also an inference network. 
- The main theoretical results (i.e., Corollary 2 and Theorem 2) are highly related to (Lei et al., 2019). However, the paper did not compare with (Lei et al., 2019). What is the advantage of the proposed results over those in (Lei et al., 2019)? It seems that the result in (Lei et al., 2019) (i.e., m>=2.1n) is tighter than the presented one (m>=5.7n). 
- Injectivity for Gaussian weights should be tested by comparing with gradient descent and (Lei et al., 2019). Also, how to use Corollary 2 and Theorem 2 to construct W in practice?
- It is better to test with some real problems, e.g., denoising. 

Minor comments:
1.	In the first paragraph of subsection 2.3, ||ReLU(x)-ReLU(y)|| should be ||ReLU(Wx)-ReLU(Wy)||.
2.	What do C(W) and S(x,W) mean in Theorem 3? 
review_title: The proposed directed spanning set (DSS) for injective ReLU networks is very useful. However, its advantage over prior work (e.g., Lei et al., 2019) is not well tested.

final_score: rating: 8: Top 50% of accepted papers, clear accept
review_content: This paper studies injective ReLU networks, motivated by various applications such as generative modeling, inverse problems and compressed sensing with generative priors. The authors fully characterize injectivity of fully-connected and convolutional layers and networks. They provide layerwise and multilayer results, characterizing the stability of inverting an injective network, and using tools from differential topology to study injectivity of deep networks. They also prove a sufficient condition for injectivity, which is an end-to-end doubling of the dimension. 

The overall writing is clear and the use of pictorial illustration is helpful for less mathematically mature readers. Despite not being an expert in this area, I acknowledge the signifcance of exploring the properties and theories of injective (ReLU) neural networks, particularly for the study of inverse problems and generative modeling. The authors performed a comprehensive study of this subject in this paper, developing theories which allow deeper understanding of injective ReLU networks and their applications to nonlinear inverse and inference problems. 


Pros: 
- This paper established a mathematically rigorous framework to study the injectivity of fully-connected and convolutional ReLU networks. 
- Substantial and careful discussion of common operations in fully-connected and convolutional neural networks, such as normalization strategies and pooling operations, regarding their effects on the injectivity of networks with their presence. 


Cons: 
- Would like to see an experiment for inverse problem applications, though this is rather minor. 


Typos: 
- In **Notation.**, do you mean $ \mathcal{NN}(n, m, L, \mathbf{n}) $ instead of $ \mathcal{NN}(n, m, L, \mathbf{m}) $?
- In (2), $ b_L $ instead of $ b_\ell $? Should there be $ b_{L+1} $ as well? 
- Should the constant $ C(W) $ appear in (6)?
- Page 6, line 3: do you mean $ c \in \mathbb{R}^{N_1} \times \cdots \times \mathbb{R}^{N_p} $ instead?

review_title: Comprehensive study of injective ReLU networks

final_score: rating: 5: Marginally below acceptance threshold
review_content: Summary 

This paper studies injectivity of fully-connected and convolutional ReLU networks. The paper studies conditions under which each layer of the ReLU network becomes injective for all possible inputs (hence making the entire network injective). Achieving injectivity requires that the output dimension of the layer is wider than input dimension at least by an expansion factor of 2 (Theorem 1, Corollary 2). Moving on to the injectivity of the entire network, the paper also shows that injective neural networks can universally approximate any continuous function $f : \mathbb R^n \to \mathbb R^m$ on a compact set $\mathcal Z \subset \mathbb R^n$ if $m \geq 2n+1$ (Theorem 3). Also, by applying random projections between hidden layers to reduce dimensions without losing injectivity, the paper shows that global injectivity of the network can be achieved (almost surely) with an input-output expansion factor of $\approx 2$ (Corollary 3).

Overall Assessment

I’m completely new to this topic of injective neural networks, and I’m not so familiar with application areas such as compressed sensing or inverse problems mentioned in this paper. So please take my words with a grain of salt. 

It looks to me that the paper investigates a topic of interest, but at the same time, I question if this investigation can yield any fruitful outcome in practice. Also, I think the theory part of the paper has room for improvement in terms of clarity. For these reasons, I’m slightly leaning towards rejection at the moment, but I’m happy to raise my score after discussions with authors and other reviewers.

Detailed Comments

The paper puts extensive efforts to characterize injectivity on ReLU networks. Preliminary experiments look promising, but a more thorough experimental investigation in the application areas would have been a great addition to the paper.

Given all the theoretical results I have some fundamental questions on how to apply these ideas to practice. First of all, the paper analyzes the condition for ReLU layers to be injective. However, given that the DSS condition takes exponential time to check, how do you check for injectivity of a given network?

Also, a good portion of the paper deals with randomly sampled or generic matrices, but after you train a network using some training dataset, these matrices are no longer random or generic. How do you ensure that the network is still injective? Does the paper provide any method that makes sure that the network stays injective even after training? I see that the experiments in the paper used a convnet counterpart of Corollary 2, but Corollary 2 only holds if the expansion factor is exactly two.

In addition, I think the paper has several typos in notation as well as unclear points in theorem statements. It’d be great to fix/clarify the following issues:

- The statements around Theorem 4 are not clear enough to me. The term “shift” in Eq (8) is not defined precisely. In Theorem 4, does “for any $P$” mean “for all $P$” or “there exists any $P$”? How do you define DSS for multi-indices in $\mathbb R^P$? I didn’t get what Theorem 4 is trying to deliver.

- A dumb clarification question: it looks to me that Theorem 5 holds for any depth $L \geq 1$. So if $L=1$, a model $W_2\phi (W_1 x)$ (omitting bias terms) will represent $(x, F_{\theta} (x))$, where $F_{\theta}(x)$ approximates the target function $f(x)$. But after that, the construction requires $n$ projections $P_1, \dots, P_n$ from $\mathbb R^{n+m}$ to $\mathbb R^{m}$, which may sound like “multiple layers.” Are you viewing these projections as a single layer because the matrices $W_2, P_1, \dots, P_n$ can be multiplied all together?

- In the Notation paragraph in Section 1.3, the vector $m = (m_1, \dots, m_{L-1})$ is never used in the definition. Also, Eq (2) has $W_{L+1}$ in its definition which should be of dimension $\mathbb R^{n_{L+2} \times n_{L+1}}$. But two lines below that we have $n_L = m$, suggesting that the indices are off by one or two. Also, Eq (2) has a bias term $b_\ell$ which should be a typo.

- Corollary 1 states $\phi_\ell(W_{\ell} \cdot + b_\ell) : \mathbb R^{n_{i+1}} \to \mathbb R^{n_i}$ which should be corrected to $\mathbb R^{n_i} \to \mathbb R^{n_{i+1}}$.

- In the beginning of Section 2.3, $\| {\rm ReLU}(x) - {\rm ReLU}(y) \|$ should be corrected to $\| {\rm ReLU}(Wx) - {\rm ReLU}(Wy) \|$.

- In Section 2.4, the notation $I$ for a multi-index overloads with the identity matrix $I$.

review_title: Review

final_score: rating: 5: Marginally below acceptance threshold
review_content: This paper studies some conditions when a ReLU network is injective. For a single ReLU layer, it derives sufficient and necessary conditions for a deterministic function. To verify this condition may take exponential time, but it gives quantitative expansivity results for random nets. Then the paper shows the universal approximation power for injective network and verify empirically that by enforcing a special structure that guarantees injectivity, they could improve the normal DCGAN training with better inception distance. 

The paper has abundant theoretical results that cover different perspectives on understanding the role of injectivity in generative models. 


1. The research problem on when a multilayer ReLU network is injective is mathematically interesting and sound. The paper has some though understanding of a single-layer case followed by some discussions of multi-layered settings. One main result of the paper is some sufficient and necessary condition of whether a single-layer ReLU network is injective, together with a lower bound for random net. 
The paper further shows some sufficient property that grants an injective multi-layer generative model with a reasonable architecture.   


However, I also have some concerns about the paper.

2. The considered problem seems not very useful to the ML community. It is not exactly true that global injectivity is important to the studies of inverse problems with generative models. The success of CSGM is from the fact that natural images lie in a small dimensional latent space. With leaky ReLU or flow model, global injectivity is automatically satisfied for non-degenerate weight matrices, and in most applications, we don't see much difference. With the ReLU network, I agree it was not clear whether a naturally trained generative model is injective or not, but the paper has not given a formative answer either. It is unclear to me how to interpret the results and how to make them useful in general. 


3. The empirical study is quite interesting. However, it doesn't necessarily show that enforcing injectivity improves the quality of the generative model unless you could prove that the original DCGAN generates a network that doesn't satisfy injectivity. (Also, if you believe naturally trained generative model doesn't satisfy injectivity property, it again means that injectivity is not important to inverse problems since it works anyway and overruled the overall intuition of the paper). Also, the generated images w/o enforcing the structure doesn't seem to have any visual difference to me. Plus, the paper did not verify if the newly generated network has improved its performance on compressed sensing. If so, it could be an enlightening result and an interesting direction to explore. 
review_title: The paper studies some mathematically sound problems but not necessarily useful for the ML community

Meta-review: The average review ratings for this paper is somewhat borderline. The paper provides mathematical characterizations on when ReLU neural networks are injective. The paper has very nice ideas, but the reviewers also pointed out several key concerns: 

1. “Given that the DSS condition takes exponential time to check, how do you check for injectivity of a given network?”
2. “But after you train a network using some training dataset, these matrices are no longer random or generic. How do you ensure that the network is still injective?”
3. “With leaky ReLU or flow model, global injectivity is automatically satisfied for non-degenerate weight matrices, and in most applications, we don't see much difference”

I think points 2&3 are particularly important here. It seems that for practitioners, if injectivity is a key concern, then one can just use leaky-relu with well-conditioned weight matrices that guarantee injectivity. Note that well-conditioning is easy to check and relatively easy to enforce. It’s unclear to the AC why one has to stick to particularly the relu activation and the recipe provided by corollary 2 and the paragraphs below Corollary 2. (It also seems to the AC that Corollary 2’s construction is fundamentally similar to the using leaky-relu, but the AC is not quite sure.) Given that a much easier workaround (using leaky-relu and full-rank matrices) is available and is widely used in prior works (when it’s necessary), the AC, unfortunately, does not see that the paper could have a strong impact on the ML community and does not think the experimental results are sufficient to justify that this is a better idea than using leaky-relu. In the AC’s opinion, the paper might be more compelling in a math venue. 


Decision: Reject