Globally Injective ReLU networks
Authors: Michael Puthawala
Konik Kothari
Matti Lassas
Ivan Dokmanić
Maarten V. de Hoop
Venue:  (2021)
Keywords: Generative models
injectivity of neural networks
universal approximation
inference
compressed sensing with generative priors
well-posedness
random projections

Abstract: Injectivity plays an important role in generative models where it enables inference; in inverse problems and compressed sensing with generative priors it is a precursor to well posedness. We establish sharp characterizations of injectivity of fully-connected and convolutional ReLU layers and networks. First, through a layerwise analysis, we show that an expansivity factor of two is necessary and sufficient for injectivity by constructing appropriate weight matrices. We show that global injectivity with iid Gaussian matrices, a commonly used tractable model, requires larger expansivity between 3.4 and 10.5. We also characterize the stability of inverting an injective network via worst-case Lipschitz constants of the inverse. We then use arguments from differential topology to study injectivity of deep networks and prove that any Lipschitz map can be approximated by an injective ReLU network. Finally, using an argument based on random projections, we show that an end-to-end---rather than layerwise---doubling of the dimension suffices for injectivity. Our results establish a theoretical basis for the study of nonlinear inverse and inference problems using neural networks.

Under review as a conference paper at ICLR 2021
GLOBALLY INJECTIVE RELU NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Injectivity plays an important role in generative models where it enables inference; in inverse problems and compressed sensing with generative priors it precursor to well posedness. We establish sharp characterizations of injectivity of fully- connected and convolutional ReLU layers and networks. First, through a layerwise analysis, show that an expansivity factor of two is necessary and sufficient for injectivity by constructing appropriate weight matrices. We show that global injectivity with iid Gaussian matrices, commonly used tractable model, requires larger expansivity between 3.4 and 10.5. We also characterize the stability inverting an injective network via worst-case Lipschitz constants of the inverse. We then use arguments from differential topology to study injectivity of deep networks and prove that any Lipschitz map can be approximated by an injective ReLU network. Finally, using an argument based on random projections, we show that an and-to-end-ratiee for injectivity. Our results establish a theoretical basis for the study of nonlinear inverse and inference problems using neural networks.
than layerwise-doubling of the dimension suffices
INTRODUCTION
Many applications of deep neural networks require inverting them on their range. Given a neural network N 2 X, where X' is often the Fuclidean space Rmm and 2 is lower-dimensional space, the map N : (Z) + Z is only well-defined when N is injective. The issue of injectivity is particularly salient two applications: generative models and (nonlinear) inverse problems.
Generative networks model a complicated distribution over X' as a pushforward of a simple distribution pz through N. Given an the range of N, inference requires computing pz (N- (x)) which is well-posed only when N is injective. In the analysis of inverse problems (Arridge et al., 2019), uniqueness a solution a key concern; it is tantamount to injectivity the forward operator. Given forward model that is known to yield uniqueness, natural question is whether we can design a neural network that approximates arbitrarily well while preserving uniqueness. Similarly, in compressed sensing with generative prior N and possibly nonlinear forward operator A injective on the range N, we seek a latent code z such that A(N (z)) is close to some measured y = A(x). This is again only well-posed when N can be inverted its range (Balestriero et al., 2020). Beyond these motivations, injectivity is a fundamental mathematical property with numerous implications. We mention notable example: certain injective generators be trained with sample complexity that is polynomial in the image dimension (Bai et al., 20.
1.1 OUR RESULTS
In this paper we study injectivity of neural networks with ReLU activations. Our contributions can be divided into layerwise results and multilayer results.
Layerwise results. For a ReLU layer f g" - R we derive sufficient and necessary conditions for invertibility on the range. For the first time, we construct deterministic injective ReLU layers with minimal expansivity m = 2n. We then derive specialized results for convolutional layers which are given in terms of filter kernels instead of weight matrices. We also prove upper and lower bounds minimal expansivity of globally injective layers with iid Gaussian weights. This generalizes certain existing pointwise results (Theorem and Appendix A.2). We finally derive the worst-case inverse

---

Under review as a conference paper at ICLR 2021
Lipschitz constant for an injective ReLU layer which yields stability estimates in applications to inverse problems.
Multilayer results. A natural question is whether injective models are sufficiently expressive. Using techniques from differential topology we prove that injective networks are universal in the following sense: if neural network N1 2 - 1 models the data, 2 C IR",, then we can approximate N1 by an injective neural network N2 : 2 - 1R2++1 As N2 is injective, the image set (2(Z) is a Lipschitz manifold. We then use argument based on random projections to show that an end-to-end expansivity by a factor of s is enough for injectivity in ReLU networks, as opposed to layerwise 2-expansivity implied by the layerwise analysis.
We conclude with preliminary numerical experiments to show that imposing injectivity improves inference in GANs while preserving expressivity.
1.2 WHY GLOBAL INJECTIVITY?
The attribute "global" relates to global injec- tivity of the map N Z + RRM on the low- dimensional latent space Z, but it does not im- ply global invertibility over RR", only on the range 22) C Rmm. If we train a GAN gen- erator map iid normal latent vectors to real images from a given distribution, we expect that any sampled latent vector generates a plausible image. We thus desire that any (z) be pro- duced by a unique latent code 2 E Z. This is equivalent to global injectivity, or invertibility on the range. Our results relate to the growing literature using neural generative models for compressed sensing (Bora et al., 2017). They parallel the related guarantees for sparse recov- ery where the role of the low-dimensional latent space is played by the set of all k-sparse vec- tors. One then looks for matrices which map all k-sparse vectors to distinct measurements (Foucart & Rauhut, 2013). As an example, in the illustration in Figure images coresponding to latent codes in orange, brown, and violet wedges cannot be compressively sensed. Finally, a neural network is often trained to directly reconstruct an image x from its (compressive) low-dimensional measurements y A(z) without introducing any generative models. In this case, whenever A is Lipschitz, it is immediate that the learned inverse must be injective.
[2, ReLU((ur w2, wal" |l 22)")
Figure 1: An illustration of a ReLU layer N R² + R3, tive. Differently colored regions in the z-space are mapped to regions of the same color in the s-spcee. While is locally injective in the pink, blue and green wedges in 2-space, the orange, brown, and violet wedges are mapped to coordinate axes. N is thus not injective these wedges. This prevents construction of an inverse in the range of N.
N=),, that is not globally injec-
1.3 RELATED WORK
Closest to our work are the papers of Bruna et al. (2013), Hand al. (2018) and Lei al. (2019). Bruna et al. (2013) study injectivity of pooling motivated by the problem of signal recovery from feature representations. They focus on e pooling layers; their Proposition 2.2 gives a criterion similar to the DSS (Definition 1) and bi- bi-Lipschitz bounds for a ReLU layer (similar to our Theorem 3). Unlike Theorems 1 and 3, their criterion and Lipschitz bound are in some cases not precisely aligned with injectivity; see Appendix E.
Compressed sensing with GAN priors requires inverting the generator on its range (Bora et al., 2017: Shah & Hegde, 2018; Wu et al., 2019; Mardani et al., 2018; Hand et al., 2018). Lei et al. (2019) replace the end-to-end inversion by the faster and more accurate layerwise inversion when each layer is injective. They show that with high probability a ReLU layer with an iid normal weight matrix can be inverted about a fixed point if the layer expands at least by a factor of 2.1. This result is related to our Theorem 2 which gives conditions for global injectivity Hand & Voroninski (2017) show that when the weights a ReLU network obey a certain weighted distribution condition, the loss function for the inversion has strict descent direction everywhere
layers with random matrices.
2

---

Under review as a conference paper at ICLR 2021
except in a small set. The condition is in particular satisfied by random matrices with expansivity n, = --nn(nnn log 1)-1), where n, is the output dimension of layer j.
A continuous analogy of our convolutional construction (Definition 3) was considered by Mallat et al. (2018). They show that ReLU acts as a phase filter and that the layer is bi-Lipschitz and hence injective when the filters have diverse phase and form frame. Discretizing their model gives statement related to Corollary and Theorem 4.
Injectivity is automatic in invertible neural networks such normalizing flows (Grover et al., 2018; Kingma & Dhariwal, 2018; Grathwohl et al., 2018), 8).. Specialized architectures with simple Jacobians give easy access to the likelihood (Dinh et al., 2014; 2016; Gomez al., 2017), which facilitates application to inverse problems (Ardizzone et al., 2018). Inference with GANs can be achieved by jointly training generative network and its inverse (Donahue et al., 2016; Dumoulin al., 2016), which is well-defined when the generator is injective. Relaxed injective probability flows resemble GAN generators but are trained via approximate maximum likelihood (Kumar et al., 2020). Injectivity is promoted by keeping the smallest singular value of the Jacobian away from zero at the training examples, a necessary but not sufficient condition. In general, Jacobian conditioning improves GAN performance (Heusel et al., 2017; Odena et al., 2018). Finally, lack of injectivity interferes with disentanglement (Chen et al., 2016; Lin et al., 2019). In this context, injectivity seems to be a natural heuristic to increase latent space capacity without increasing its dimension (Brock et al., 2016).
Notation. Given a matrix W E Rmxx" we define the notation w E W to mean that w E IR" a row vector of W. For matrix W E mmxx with rows {w, } and R", write
S(x, W) (j E [[m]] (wj, > 0}
and (x; W) for its complement, with [mm]]] = (1....,m). We let (n,, m, L, m) be the family of functions No I=" + R Th of the form
(=) = WL+10L
(2 (W1= + b1) + b2) bz)
(2)
Indices l L...., ... L index the network layers, be Re are the bias vectors, We 1 are the weight matrices with n1 = n. n. m, and de are the nonlinear activation func- tions. We will denote ReLU(x) = max(x, 0). We write n (M1, n2,,.. (2.....u-1)) and 0 = (W1, NN m, L) = UNEzI-INNNnn m, L, n) and NN (N, = Ur.n-NN m, L).
for the parameters that determine the function No. We also write
2 LAYERWISE INJECTIVITY OF RELU NETWORKS
For a one-to-one activation function such as leaky ReLU or tanh, it easy to see that injectivity of x + W, implies the injectivity of the layer. We therefore focus on non-injective ReLU activations.
2.1 DIRECTED SPANNING SET
Unlike in the case of one-to-one activation, when d(x) ReLU(z), x + <(x) cannot be injective for all x E R if W is a square matrix. Noninjectivity of ReLU(Wz)) occurs in some simple situations, for example if Wx is not full rank or if Wr < 0 element-wise for a nonzero x, but these two conditions their own not sufficient characterize injectivity. Figure 2 gives an example of a weight matrix that yields a noninjective layer that passes these two tests. In order to facilitate the full characterization of injectivity of ReLU layers, we define a useful theoretical device:
Definition 1 (Directed Spanning Set). Let W E Raxm, We say that W has directed spanning set (DSS) of Ω C g" with respect to a vector E _ if there exists a W., such that each row vector of W₂ is vector of W,
(x. w/) 2 0 for all w E W..
(3)
and Ω span(W>.. When omitted Ω is understood to be R".
For a particular & E RD, it is not hard to verify if a given W = (wi) has a DSS of Ω. One can simply let W = {wy E IR: (I, w.) > 0}. Then, W has DSS for Ω with respect to if and only if W is basis of 2 which can be checked efficiently. Note that having full rank is necessary for it
3

---

Under review as a conference paper at ICLR 2021
(2) migy"
11
(1,2,4)
(1,2)
(144)
(2,8)
[[Rel.D
(
Wsy
M/s 201
= wt
(3)
(3,4)
(1,3,4)
(3.4)
Figure 2: Illustration of the DSS definition. Left: A configuration of 4 vectors in IR that do not have a DSS w.r.t all x I In this case, the vectors do not generate an injective layer. The set of labels indicate which w have positive inner product with vectors in the wedge; there are two wedges with only one such {w) Y; we have ReLU((Wz1) = ReLU(WWx2) x2). Center: A configuration where four vectors have DSS for x E IR2. These vectors correspond to a minimally-expan
injective layer; see Corollary 2. Right: A plot of ||ReLU(Wa)) | where W is given as in the left figure. Note that x + ReLU(Way x) is linear in every wedge.
to have DSS for any RR. It is however not sufficient. For example, Id, _2x= the identity matrix in R", is clearly full rank, but doesn't 't have a DSS R² w.r.t. x = (-1,0, 0...,.,.,000 E RR..
To check whether W has DSS for all E R", note that W partitions R into open wedges Sk. R" ="=u, Sk. with constant sign patterns. That is, for #1, 22 E Sg, sign x1) ) sign (Wzy). (See also proof of Theorem in Appendix A.2.2.) Checking whether W has DSS for all is equivalent to checking that for every wedge there are at least n vectors Wa C W with positive sign, (we, x) > 0 for x S₁. and that We spans R" Since the number of wedges can be exponential in and (Winder, 1966) this suggests an exponential time algorithm. We also note the connection between DSS and spark in compressed sensing (Foucart & Rauhut, 2013), defined as the size of the smallest set of linearly dependent vectors in W. If every wedge has n or more positive signs, then full spark + 1 is sufficient for W have a DSS w.r.t all z R". Computing spark is known be NP-hard (Tillmann & Pfetsch, 2013); whether one can do better for DSS remains open question.
2.2 FULLY CONNECTED LAYER
The notion DSS immediately leads to our main result for fully connected layers.
Theorem (Conditions for Injectivity of ReL)( Let W R=xx where n >> 1 be a matrix with row vectors { [w; Ji=1, and ReLU(y) = max (v. 0). The function (+)U(W())): R - R is injective if and only if W has DSS w.r. every R...
The question of injectivity in the when O and when b are very similar and, Lemma 1 shows, the latter question is equivalent to the former on a restricted weight matrix.
Lemma (Injectivity of ReLU(Wr++h bb). Let W mm b E R The function ReLU(W(())
b): Ra - Inm is injective if and only ReLUUW)l2o)) is injective, where W Wla2u E mmxx is row- wise the same as where b; 2 and a row of zeroes when b; <
Remark 1 (Injectivity of RcLU(Wx2) 2). Positive r). Without normalization strategies, inputs of all but the first layer are element-wise non-negative. One can ask whether ReLU(War x)) is injective when x restricted to be element-wise non-negative. Following the same argument in Theorem find that W must have a DSS w.r.t. x R" for every that is element- wise non-negative. With normalizations strategies however (for example batch renormalization (Ioffe, 2017)) the full power of Theorem 1 and Lemma may be necessary. In Appendix B we show that common normalization strategies such as batch, layer, or group normalization do not interfere with injectivity.
Remark 2 (Global vs Restricted Injectivity). Even when the conditions of Theorem and Lemma satisfied the network might be injective in some X' C R Indeed, N(x) ReLU(Id,,)) is in general not injective, but is injective in X' = {x E R" x; > 0 for 1,...,n] n..,. J. a convex and open set. Theorem and Lemma are the precise criteria for single-layer injectivity for all x E IR..
4

---

Under review as a conference paper at ICLR 2021
The above layerwise results imply a sufficient condition for injectivity of deep neural networks. Corollary (layerwise Injectivity Implies End-to-End Injectivity). Let N: IR" - Rm be deep neural network of the form (2). If each layer de(We +bb): T + +**+ is injective, then so is N.
Note that Corollary is sufficient but not necessary for injectivity of the entire network. Consider for example an injective layer ReLU(W), and (x) ReLUU(Im. ReLU(((x))) (x))), where I is the identity matrix. Clearly,
(Idm ReLU (z))) = ReLU (2))) ReLU(((x))
(4)
so N is injective, but it fails the criterion of Corollary 1 (at the ReLU(I-)) layer).
An important implication of Theorem is the following result on minimal expansivity.
Corollary (Minimal Expansivity). For any W Rmx*, ReLU(W--) non-injective if m < W E I 122xx satisfies Theorem and Lemma 1, than up row rearrangement W can be written as
B -DB
W
where B,D E 12 and B is basis and D a diagonal matrix with strictly positive diagonal entries.
While m < 2n immediately precludes injectivity, Corol- lary 2 gives simple recipe for the construction of cemimmlll--xxpasiiii injective layers with m 2n. To the best of our knowledge this is the first such result. Further, we can also use Corollary 2 to build weight matrices for which > 2n. For example, the matrix
unknown
injective whp
m, number of rows
no injoctvvt whpp
B
m 5.79
W
- DB M
km
ez
where E RRax has full rank, D E RR is positive diagonal matrix, and M E mRm-2nxn is arbitrary, has DSS w.r.t every E IR". This method can be used in practice generate injective layers by using standard spectral regularizers to ensure that B is basis (Cisse al., 2017). In Section 3 will show that, in fact, an end-to-end rather than layerwise doubling of dimension sufficient for injectivity.
70
non-injective
m
n, number of columns
Figure visualization of regions where asymptotics of I(m, in The- orem are valid.
Previous work that sought injectivity uses random-weight models. Lei et (2019) show that a layer invertible
about point in the range provided that 2 2.1n and W is iid Gaussian. In Appendix A.3 show that m 2. not enought to guarantee injectivity. fact, we show that with high probability an iid Gaussian weight matrix W yields globally invertible ReLU layer, when W is sufficiently expansive, and conversely does not satisfy Theorem if is not expansive by at least a factor of 3.4:
Theorem (Injectivity for Gaussian Weights). Let I(m,n) n) Pf ReLU(Wx)) is injective) with the entries of W iid standard normal and c = m/n fixed. Then as n 00,
I(m,n) n) + if 10.5 and I(m, n) > if 3.4.
The parameter regions defined Theorem 2 are illustrated in Figure
We note that the study of neural networks with random weights is an important recent research direction (Pennington & Worah, 2017: Benigni & Péché, 2019). Pennington Worah (2017) articulate this clearly, arguing that large complex systems, of which deep networks are certainly an example, can be profitably studied by approximating their constituent parts as random variables.
2.3 INVERSE LIPSCHITZ CONSTANT FOR NETWORKS
Because [ReLL(W>)) ReLU(Wy)) < W| æ yll. it is clear that ReLU(W-)) is Lipschitz with constant ||| || whether the inverse is Lipschitz, and if so, with what Lipschitz constant, less obvious. We prove the following result (see Appendix C.
5

---

Under review as a conference paper at ICLR 2021
Theorem (Global Inverse Lipschitz Constant). Let W E Rmxx have DSS w.E.t every x E IR". There exists a C(W) > such that for any Tu, 21 E R".
[ReT.U(ass)) mb) ReLUU 11)ll C(W) |20 21ll2
where C(W)
min.eR= o (Wls(z,w)) and a denotes the smallest singular value.
V2m
This result immediately yields stability estimates when solving inverse problems by inverting (injec- tive) generative networks. We note that the (2m)-1/2 factor is essential; the naive "smallest singular value" estimate is too optimistic.
2.4 CONVOLUTIONAL LAYER
Since convolution is linear operator we could simply ap- ply Theorem and Lemma turns out, however, that there exists result specialized to convolution that is much simpler to verify. In this section, capital letters such I, and K denote multi-indexes; the same holds for their flement-wisee limits such as N and M. Nj refers the jth index in the multi-index N. We the shorteuts and Σ C ΣX, 21,=1 ch...pp for (L1,...,Ip Ip). The symbol 1 can refer to number or a p-tuple (1,..., 1). Further, the notation / < J means that I $ Jk for all k = I.....P and likewise for 2, < and > I J, then there is at least one k such that I4 > Jj.
convolution matrix. It
D1
01
P1
N₁
RN for RN: X Np
RN,,
P2
Definition 2 (Convolution Operator). Let E RO. We say that cs a convolution kernel of width O Given e and E R we define the convolution operator C' E R RNXN with stride as,
Figure 4: A visualization of the indices in (8) in dimensions. The blue re- gion is a kernel of width O the pink region the zero-padded box of width P. and D is the offset of the kernel c in the pink box. The entire signal the (7) green box of width N.
O+J Σ 1=1+
(Cx), Σ -0-14133+1
C0+J-14121.
When 1 K K 0 we will ex O. We do specify the boundary condition (zero-padded, periodic, or otherwise), as our results hold generally.
Definition (Convolutional Layer). We say that matrix W E MRN a convolution operator, with nQ convolutions, provided that W can be written (up to row rearrangement) in the form W [CT C7 ... C 1a where each Cg is a convolution operator for t = .Q....nq. A neural network layer for which W a convolution operator is called convolution layer.
Definitions 2 and 3 automatically model the standard multi-channel convolution used in practice. For 2D images of size 512 x 512, ne input channels, and 3 x 3 convolutions, we simply let x E RRN with N (512, 512, n.) and TOO with O = (3, n.))
To state our main result for convolutions we also need to define the set of zero sero-padded kernels for E R Think of multi-index box (or hyperrectangle). Let P be multi-index such that O "fits" in P. Then we define
Zr(c) (D R.. is shift of within the box P).
Theorem (Sufficient Condition for Injectivity of Convolutional Layer). Suppose that W E M is convolution layer with convolutions {CA k= and corresponding kernels {cx 19 for any P.
W = U Zp(ck)
(9)
k=1
has DSS for P with respect to all E R.P then ReLU(W-) satisfies Theorem 1.

---

Under review as a conference paper at ICLR 2021
Theorem 4 applies to multi-channel convolution of width (O, (O1..... Opp, ne) provided that we choose a (P, ne) such that O S P. This theorem shows that if a convolution operator W has DSS w.r.t. vectors with support in the pink region in Figure 4, then it has DSS w.r.t vectors supported on the green region as well.
3 UNIVERSALITY AND EXPANSIVITY OF DEEP INJECTIVE NETWORKS
We now consider general properties of deep injective networks. Note that a neural network No E (n, m) Lipschitz smooth: there is Lo > such that [No(z)) No [v)] - Lo| - y| for all E E R". If Ng R" + m is also injective, results of basic topology imply that for any bounded and closed set the sets B and its image No B) are homeomorphic. Thus, for example, if 2 is random variable supported on the cube [0, 1J C IR" the sphere g C IR" or the torus T C RR", we see that No ()) is random variable supported on a set in T that is homeomorphic to an n-dimensional cube or an n - dimensional sphere or a torus, respectively. This means that injective neural networks can model random distributions surfaces with prescribed topology. Moreover, if Nę RR - R a decoder, all objects x: E (RR" correspond to the unique code 2 such that x = No(2).
R the map No
No Na(B) has continuous inverse No NB(
B and
A fundamental property of neural networks is that they can uniformly approximate any continuous function f Z - R" defined in a bounded set Z C R". For general dimensions n and m, the injective neural networks do not have an analogous property. For instance, if ʃ [- x] - IR is the trigonometric function f(x) = sin(z), ( it is easy to see that there is no injective neural network (or any other injective function) Ng [[ - IR such that (f(x)) Ny(x)) 1. Consider, however, the following trick: add two dimensions in the output vector and consider the map F [-x, π] + R given by F(x) one-dimensional, non-injective ReLU network fo [- - IR and a > 0 is small, then the neural network (z) (aι(z), ad( fo())) is an injective map that approximates F.
sin))) E Rs, When f is approximated by
In general, as ReLU networks are piecewise affine maps, it follows in the case m = that if a ReLU network N₂- T - Th is injective, it has to be surjective (Scholtes, 1996, Thm. 2.1). This is a limitation of injective neural networks when m n. Building on these ideas we show that when the dimension of the range space is sufficiently large, m 2 2n + 1, injective neural networks become sufficiently expressive to universally model arbitrary continuous maps.
Theorem 5 (Universal Approximation with Injective Neural Networks). Let f R - I be continuous function, where m 2 2n + 1, and L, 2 Then for any > and compact subser Z C R there exists neural network No E NN m) of depth L such that Ng IR" + IRm is injective and
If(z) No(x)) Se, for all Z.
(10)
Before describing the proof, note that this result also holds for leaky ReLU networks with modification. The key fact used in the proof is that the network is a piecewise affine function.
To prove this result, we combine the approximation results for neural networks (e.g., Pinkus's density result for shallow networks (Pinkus, 1999, Theorem 3.1) or Yarotsky's 's result for deep neural networks (Yarotsky, 2017)), with the Lipschitz-smooth version of the generic projector technique. This technique from differential topology is used for example to prove the easy version of the Whitney's embedding theorem (Hirsch, 2012, Chapter 2, Theorem 3.5). Related random projection techniques have been used earlier in machine learning and compressed sensing (Broomhead & Kirby, 2000; 2001: Baraniuk Wakin, 2009; Hegde et al., 2008; Iwen& & Maggioni, 2013).
The proof of Theorem 5 is based on applying the above classical results to locally approximate the function : R - Rm by some (possibly non-injective) ReI. neural network Fg RR" -> Rm and augment it by adding additional variables, so that Ho(x) (x, (x)) is an injective map Ha : IR + gu+m, The image of this map, M = Hg (IK), is an n-dimensional, Lipschitz-smooth submanifold of p=+m The dimension of m + is larger than 2n + 1, which implies that for randomly chosen projector P1 that maps R= yn++m to a subspace of dimension m + n - 1, the restriction of P1 the submanifold M, that is, P1 M + P. is injective. By applying random ,,.,,,,
projectors, PI...., Pn. we have that No = P, Pn-1 .... o P1 H, is an injective map whose image is in dimensional linear space. These projectors can be multiplied together, but
7

---

Under review as a conference paper at ICLR 2021
generated sequentially. By choosing the projectors Py in suitable way, the obtained neural network No upproximates the map f.
We point out that in the proof of Theorem 5 it is crucial that we first approximate function f by neural network and then apply to it a generic projection to make the neural network injective. Indeed, doing this in the opposite order may fail an arbitrarily small deformation (in C(R")) of injective map may produce a map that is non-injective.
The proof of Theorem 5 implies the following corol- lary on cascaded neural networks where the dimen- sions of the hidden layers can both increase and de- crease (see Figure 5):
Corollary 3. Let n. m, dj E 22, j 0,1,.... 2k
1 E R
be such that do = n, d2k = m 2 2n + and dg 2
f (1)
B2
Bg
B
No(a) E
2n + f.rrr even indexes j 2 Let
F2 = BB o 15 B 10 (k-1) .... B1 f/
where 5(5) .Rdds 2 + Rdb; are injective neu- ral networks and Bj E Rd + Ruaa are ran- dom matrices whose joint distribution is absolutely continuous with respect to the Lebesgue measure of II IT,=, (Rde, xd2)-)). x Then the neural network Fx: R + Rm is injective almost surely.
An illustration of an injective deep neural network that avoids expansivity as de- scribed by Corollary 3. White trapezoids are expansive weight matrices satisfying Theo- rem 1, and the blue trapezoids are random projectors that reduce dimension while pre- serving injectivity.
Figure 5:
Observe that in Corollary 3 the weight matrices B3 and By may not be independent. Moreover, the dis- tribution of the matrices B, may be supported in an arbitrarily small set, that is, small random perturba- tion of the weight matrices make the function Fy injective. Corollary characterizes deep globally injective networks, while avoiding the exponential growth in dimension indicated by Corollary 2.
4 NUMERICAL EXPERIMENTS INJECTIVE GANS IMPROVE INFERENCE
We devise simple experiment to demonstrate that 1) one can construct injective networks using Corollary 2 that 2) perform as well as the corresponding non-injective networks, while 3) being better at inference problems. One way to do inference with GANs is to train so-called inference network Tuet: : X - 2 jointly with the generator G - X' so that T T((()) R (Donahue et al., 2016; Dumoulin et al., 2016); Luet is trained to invert G on its range. This is used to evaluate the likelihood of an image x in the range of G as pz (nner( (x)). However, for pz (nne ( (G(z)) = pz pz(2) to hold, G must be injective otherwise the distribution of Tuee (G(2)) will be different from that of One would thus hope that the distribution of net (G(z)) will be closer to that of 2 if we enforce injectivity. If that is the case and the sample quality is comparable, then have practical tool to improve inference.
We the DCGAN (Radford al., 2015) architecture with the same hyperparameters, layer sizes and normalization strategies for the regular GAN and the injective GAN; see Appendix F. Note that the original DCGAN uses several ReLU conv layers with an expansivity of 2 per layer. By Corollary 2 these layers are non-injective. Therefore, the filters of the DCGAN are modified to be of the form IC:- s² in order to build an injective GAN. We train the networks to generate 64 64 x images and draw the latent code 2 E 2256 iid from a standard normal distribution. We test on CelebA (Liu et al., 2015) and FFHQ (Karras et al., 2019) datasets. To get a performance metric, we fit Gaussian distributions A (n,, Σ) and ((rimj Emm) to G(z) and (z) We then compute the Wasserstein-2 distance W2 between the distribution of z ~ Ao(,, T250) and the two fitted Gaussians using the closed-form expression for Wi between Gaussians, W/NNN (M1, N (H2 E2)) = ||и4 #2ll + + Ee - 2( Σ2) )22). We summarize the results in Table 1. Despite the restrictions on the weights of injective generators, their performance on popular GAN metrics Fréchee inception distance (FID) (Heusel et al., 2017) and inception score (IS) (Salimans et al., 2016)-is comparable to the standard GAN while inference improves. That the generated samples are indeed comparable to the standard GAN can be also gleaned from the from the figure in Appendix F.
8

---

Under review as a conference paper at ICLR 2021
Table 1: Injectivity improves inference without sacrificing performance.
Dataset
Type of G
Inception Scoret
Fréchet Inception Distance.
WIP P=)
Injective
2.24 0.09
39.33 = 0.41 50.56 = 0.52
18.59
CelebA
Regular
2.22 - 0.16
33.85
Injective
2.56 - 0.15
61.22 = 0.51
9.87
FFHQ
Regular
47.23 = 0.90
19.63
CONCLUSION
We derived and explored conditions for injectivity of ReLU neural networks. In contrast prior work which looks at random weight matrices, our characterizations are deterministic and derived from first principles. They are also sharp in that they give sufficient and necessary conditions for layerwise injectivity. Our results apply to any network of the form (2)-they only involve weight matrices but make no assumptions about the architecture. We included explicit constructions for minimally expansive networks that are injective; interestingly, this simple criterion already improves inference our preliminary experiments. The results on universality of injective neural networks further justify their use in applications; they also implicitly justify the various Jacobian conditioning strategies when learning to generate real-world data. Further, injective neural networks are topology-prn prreeeriig homeomorphisms which opens applications in computational topology and establishes connections to tools such as self-organizing maps. Analysis of deep neural networks has an analogue in the analysis of inverse problems where studies uniqueness, stability and reconstruction. Uniqueness coincides with injectivity, quantitative stability with the Lipschitz constant the inverse, and, following Lei et al. (2019), from linear program get reconstruction in the range.
ACKNOWLEDGMENTS
We are grateful to Daniel Paluka and Charles Clum for pointing out problem with the bound on the sum of binomial coefficients used to prove Theorem

---

Under review as a conference paper at ICLR 2021
REFERENCES
Robert A. Adams. Sobolev spaces. Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1975. Pure and Applied Mathematics, Vol. 65.
Lynton Ardizzone, Jakob Kruse, Sebastian Wirkert, Daniel Rahner, Eric W Pellegrini, Ralf's S Klessen, Lena Maier-Hein, Carsten Rother, and Ullrich Köthe. Analyzing inverse problems with invertible neural networks. arXiv preprint /808.
2018.
Simon Arridge, Peter Maass, Ozan Öktem, and Carola-Bibiane Schönlieb. Solving inverse problems using data-driven models. Acta Numerica, 28:1-174, 2019.
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint arXiv: 1607.06450, 2016.
Yu Bai, Tengyu Ma. and Andrej Risteski. Approximability of discriminators implies diversity in gans. arXiv preprint arXiv: 10586 2018.
Randall Balestriero, Sebastien Paris, and Richard Baraniuk. Max-affine spline insights into deep generative networks. arXiv preprint arXiv:2002. 1912, 2020.
Richard G. Baraniuk and Michael B. Wakin. Random projections of smooth manifolds. Found. Comput. Math., 91):511777, 2009, ISSN 1615-3375 doi: 10.10077/1000080007-90000 1-z. URL.
htttss://dof /10 1007/s10208-000-00000
Lucas Benigni and Sandrine Péché. Eigenvalue distribution nonlinear models of random matrices.
arXiv preprint arXiv:1904.03090 2019.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros G Dimakis. Compressed sensing using generative models. In Proceedings of the 34th International Conference on Machine Koarring-VVlummee 70, pp. 537-546. JMLR. org, 2017.
Andrew Brock, Theodore Lim, James M Ritchie, and Nick Weston. Neural photo editing with introspective adversarial networks. arXiv preprint arXiv: 16Xiv:6609.000000 07000,00799,,, 2016.
D. S. Broomhead and M. Kirby. A new approach to dimensionality reduction: theory and algorithms.
SIAM Math., 204))2114-2222, 2000. 2000. ISSN 0006-1399 doi: 10. 10.1137/S0336111999833333 URL hwtpt::pp//.... / htt//ooo.orroo wro./..gg.00oo /te.//////0003399993300
D. S. Broomhead and M. J. Kirby. The whitney reduction network: A method for computing autoassociative graphs. 13(11), 2001. ISSN 0899-7667, doi: 10.1 10.1699779766617711999944 URL
https://doi..
Joan Bruna, Arthur Szlam, and Yann LeCun. Signal recovery from pooling representations. arXiv preprint arXiv:1311.4022 2013.
Peter Bürgisser and Felipe Cucker. Condition: The geometry of numerical algorithms, volume 349. Springer Science & Business Media, 2013.
Xi Chen, Yan Duan, Rein Houthooft, John Schulman, Ilya Sutskever, and Pieter Abbeel. Infogan: Interpretable representation learning by information maximizing generative adversarial nets. In Advances in neural information processing systems, pp- 2172-2180. 2016.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. arXiv preprint 1xXiv:170.008844 2017.
Ştefan Cobzaş, Radu Miculescu, and Adriana Nicolae. Lipschitz functions, volume 2241 of Lecture Notes in Mathematics. Springer, Cham, 2019. ISBN 978-3-033--16488-11 978-3- URL https: /tttps://doi..or/10...1111
030-16489-8.
doi: 10. 1111079978-3-000-16488- 978-3- 118-3-030-110 100-0001-119--...
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components
estimation. arXiv preprint arXiv: 14.0.5 16, 2014.
10

---

Under review as a conference paper at ICLR 2021
Laurent Dinh, Jascha Sohl-Dicksteli and Samy Bengio. Density estimation using real nyp. arXiv preprint
2016.
Jeff Donahue, Philipp Krähenbühl, and Trevor Darrell. Adversarial feature learning. arXiv preprint 1605:0660500782 2016.
Vincent Dumoulin, Ishmael Belghazi, Ben Poole, Olivier Mastropietro, Alex Lamb, Martin Arjovsky, and Aaron Courville. Adversarially learned inference. arXiv preprint arXiv: 1rxxiv:606.007000 6006000044 2016.
Simon Foucart and Holger Rauhut. A Mathematical Introduction to Compressive Sensing. Birkhäuser Basel, 2013. ISBN 081 0817649476.
Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger B Grosse. The reversible residual network: Backpropagation without storing activations. In Advances in neural information processing systems, pp. 2214-2224, 2017.
Will Grathwohl, Ricky TQ Chen, Jesse Bettencourt, Ilya Sutskever, and David Duvenaud. Ffjord: Free-form continuous dynamics for scalable reversible generative models. arXiv preprint arXiv:1810.01367, 2018.
Aditya Grover, Manik Dhar, and Stefano Ermon. Flow-gan: Combining maximum likelihood and adversarial learning in generative models. In Thirly-Second AAAI Conference on Artificial Intelligence, 2018.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. In Advances in neural information processing systems, pp. 5767-5777, 2017.
Paul Hand and Vladislav Voroninski. Global guarantees for enforcing deep generative priors by empirical risk. arXiv preprint 1705.0770. 2017.
Paul Hand, Oscar Leong, and Vlad Voroninski. Phase retrieval under generative prior. In Advances in Neural Information Processing Systems, pp. 9136 91469916,226 2018.
Chinmay Hegde, Michael Wakin, and Richard Baraniuk. Random projections for manifold learning. In C. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems 20, pp. 641-648. Curran Associates, Inc., 2008. URL http: /ptppaa....eee//e/ nips. cc/ http:/appppr/eee 31 1111111a1ddorrrrrm random-pro jectiens-
pdf.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by two time-scale update rule converge local nash equilibrium. In Advances in neural information processing systems, pp. 6626-6637, 2017.
Morris W Hirsch. Differential topology, volume 33. Springer Science & Business Media, 2012.
Kurt Hornik. Approximation capabilities of multilayer feedforward networks. Neural networks, 4(2): 251-257, 1991.
Sergey loffe. Batch renormalization: Towards reducing minibatch dependence in batch normalzord models. In Advances in neural information processing systems, pp. 1945-1955 2017.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. arXiv preprint arXiv: 2015.
Mark A. Iwen and Mauro Maggioni. Approximation of points on low-dimensional manifolds via random linear projections. Inf. Inference, 2(1):1-31, 2013, ISSN 2049-8764, doi: 10. iat001. URL petttp:://oi..oee
10. 10011093//10 1wt.///mmaa//aattmmeea
Tero Karras, Samuli Laine, and Timo Aila. style-based generator architecture for generative adversarial networks. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 4401-4410, 2019.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible Ix1 convolutions, In Advances in Neural Information Processing Systems, pp. 10215-10224, 2018.
11

---

Under review as a conference paper at ICLR 2021
Abhishek Kumar, Ben Poole, and Kevin Murphy. Regularized autoencoders via relaxed injective probability flow. arXiv preprint arXiv:2002.08927 2020.
Qi Lei, Ajil Jalal, Inderjit S Dhillon, and Alexandros Dimakis. Inverting deep generative models, one layer at time. In Advances in Neural Information Processing Systems, pp. 13910-13919, 2019.
Moshe Leshno, Vladimir Ya Lin, Allan Pinkus, and Shimon Schocken, Multilayer feedforward networks with nonpolynomial activation function approximate any function. Neural networks, 6(6):861-867, 1993.
Zinan Lin, Kiran Koshy Thekumparampil, Giulia Fanti, and Sewoong Oh. Infogan-cr: Disentangling generative adversarial networks with contrastive regularizers. arXiv preprint arXiv:/906.0m (aoo:::90000644 2019.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes in the wild. In Proceedings of International Conference Computer Vision (ICCV), 12 2015.
J. Luukkainen and J. Väisälä. Elements of Lipschitz topology. Ann. Acad. Sci. Fenn. Ser. A I Math., 3(1):85-122, 1977. ISSN 0066- 1953. doi: 00.5166/ansfm.1177.035. URL https: //doi . orgg 10.
/aaasfm 1977. 0315.
Stéphane Mallat, Sixin Zhang, and Gaspar Rochette. Phase harmonic correlations and convolutional neural networks. arXiv preprint arXiv: 12136, 2018.
Morteza Mardani, Enhao Gong. Joseph Cheng, Shreyas S Vasanawala, Greg Zaharchuk, Lei Xing, and John M Pauly. Deep generative adversarial neural networks for compressive sensing mri. IEFE transactions on medical imaging, 38(1) 18(1):667-179 2018.
Pertti Mattila. Geometry of sets and measures in Euclidean spaces, volume 44 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1995. ISBN 0-521-65595-1. doi: 10. (0.1017/C0997805 1623813. URL https: / wtwp:i..oog/..1110 CB09780511623811 Fractals and rectifiability.
John W. Milnor and James D. Stasheff. Characteristic classes. Princeton University Press, Princeton, N. J.; University of Tokyo Press, Tokyo, 1974. Annals of Mathematics Studies, No. 76.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprint arXiv:180..05955 2018.
Frank Morgan. Geometric measure theory: a beginner's guide. Academic press, 2016.
Augustus Odena, Jacob Buckman, Catherine Olsson, Tom B Brown, Christopher Olah, Colin Raffel, and lan Goodfellow. Is generator conditioning causally related to gan performance? arXiv preprins arXiv: (t02:/802.0766 2018.
Jeffrey Pennington and Pratik Worah. Nonlinear random matrix theory for deep learning. In Advances in Neural Informatinn Processing Systems, pp. 2637-2646, 2017.
Allan Pinkus. Approximation theory of the mlp model in neural networks. Acta numerica, 8:143-195, 1999.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXiv preprint arXiv: 1511:64111 2015.
Tim Salimans and Durk Kingma. Weight normalization: A simple reparametetization to accelerate training of deep neural networks. In Advances in neural information processing systems, pp. 901-909, 2016.
Tim Salimans, Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in neural information processing systems, pp. 2244-2242, 2016.
Stefan Scholtes. Homeomorphism conditions for coherently oriented piecewise affine mappings. Mathematics of operations research, 21(4):955-978, 1996.
12

---

Under review as a conference paper at ICLR 2021
Viraj Shah and Chinmay Hegde. Solving linear inverse problems using gan priors: An algorithm with provable guarantees. In 2018 JEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 4609 4613. IEEE, 2018.
Andreas M Tillmann and Marc E Pfetsch. The computational complexity of the restricted isometry property, the nullspace property, and related concepts in compressed sensing. IEEE Transactions on Information Theory, 60(2):1248-1255 2013.
Dmitry Ulyanov, Andrea Vedaldi, and Victor Lempitsky. Instance normalization: The missing ingredient for fast stylization. arXiv preprint arXiv: 2016.
RO Winder. Partitions of n-space by hyperplanes. SIAM Journal Applied Mathematics, 14(4): 81 211-818, 1966.
Yan Wu, Mihacla Rosca, and Timothy Lillicrap. Deep compressed sensing. arXiv preprint 2019.
Yuxin Wu and Kaiming He. Group normalization. Proceedings of the European Conference on Computer Vision (ECCV), pp. 3-19, 2018.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
13


Reviews:
[{"review_id": "ngECdGZUB24", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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. \n\n\nPros: \n- This paper established a mathematically rigorous framework to study the injectivity of fully-connected and convolutional ReLU networks. \n- 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. \n\n\nCons: \n- Would like to see an experiment for inverse problem applications, though this is rather minor. \n\n\nTypos: \n- In **Notation.**, do you mean $ \\mathcal{NN}(n, m, L, \\mathbf{n}) $ instead of $ \\mathcal{NN}(n, m, L, \\mathbf{m}) $?\n- In (2), $ b_L $ instead of $ b_\\ell $? Should there be $ b_{L+1} $ as well? \n- Should the constant $ C(W) $ appear in (6)?\n- Page 6, line 3: do you mean $ c \\in \\mathbb{R}^{N_1} \\times \\cdots \\times \\mathbb{R}^{N_p} $ instead?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "WUWAU6OZ3-", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary \n\nThis 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).\n\nOverall Assessment\n\nI’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. \n\nIt 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.\n\nDetailed Comments\n\nThe 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.\n\nGiven 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?\n\nAlso, 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.\n\nIn 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:\n\n- 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.\n\n- 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?\n\n- 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.\n\n- 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}}$.\n\n- In the beginning of Section 2.3, $\\| {\\rm ReLU}(x) - {\\rm ReLU}(y) \\|$ should be corrected to $\\| {\\rm ReLU}(Wx) - {\\rm ReLU}(Wy) \\|$.\n\n- In Section 2.4, the notation $I$ for a multi-index overloads with the identity matrix $I$.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RiagbmZxW7s", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe paper has abundant theoretical results that cover different perspectives on understanding the role of injectivity in generative models. \n\n\n1. 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. \nThe paper further shows some sufficient property that grants an injective multi-layer generative model with a reasonable architecture.   \n\n\nHowever, I also have some concerns about the paper.\n\n2. 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. \n\n\n3. 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. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "JVz4AQrLQRr", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: \nInverting 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. \n \nStrengths: \n+ Injectivity produces invertibility for ReLU networks. The paper defines the directed spanning set (DSS) to construct layerwise injectivity, which is very useful. \n+ Some conditions for injective networks are presented. \n\nWeaknesses: \n- 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. \n- 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). \n- 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?\n- It is better to test with some real problems, e.g., denoising. \n\nMinor comments:\n1.\tIn the first paragraph of subsection 2.3, ||ReLU(x)-ReLU(y)|| should be ||ReLU(Wx)-ReLU(Wy)||.\n2.\tWhat do C(W) and S(x,W) mean in Theorem 3? ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

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