Universal Joint Approximation of Manifolds and Densities by Simple Injective Flows
Authors: Michael Anthony Puthawala
Matti Lassas
Ivan Dokmanić
Maarten V. de Hoop
Venue: ICLR 2022 Submitted (2022)
Keywords: Universality
Flow Networks
Manifold Learning
Density Estimation

Abstract: We analyze neural networks composed of bijective flows and injective expansive elements. We find that such networks universally approximate a large class of manifolds simultaneously with densities supported on them. Among others, our results apply to the well-known coupling and autoregressive flows. We build on the work of Teshima et al. 2020 on bijective flows and study injective architectures proposed in Brehmer et al. 2020 and Kothari et al. 2021. Our results leverage a new theoretical device called the \emph{embedding gap}, which measures how far one continuous manifold is from embedding another. We relate the embedding gap to a relaxation of universally we call the \emph{manifold embedding property}, capturing the geometric part of universality. Our proof also establishes that optimality of a network can be established ``in reverse,''  resolving a conjecture made in Brehmer et al. 2020 and opening the door for simple layer-wise training schemes. Finally, we show that the studied networks admit an exact layer-wise projection result, Bayesian uncertainty quantification, and black-box recovery of network weights.

Under review as a conference paper at ICLR 2022
UNIVERSAL JOINT APPROXIMATION OF MANIFOLDS AND DENSITIES BY SIMPLE INJECTIVE FLOWS
Anonymous authors Paper under double-blind review
ABSTRACT
We analyze neural networks composed of bijective flows and injective expansive elements. We find that such networks universally approximate a large class manifolds simultaneously with densities supported results apply to the well-known coupling and autoregressive flows. We build on the work of Teshima et al. 2020 bijective flows and study injective architectures proposed in Brehmer et al. 2020 and Kothari et al. 2021. Our results leverage a new theoretical device called the embedding gap, which measures how far one continuous manifold is from embedding another. We relate the embedding gap to a relaxation of universally we call the manifold embedding property, capturing the geometric part of universality. Our proof also establishes that optimality of a network can be established "in reverse," resolving conjecture made in Brehmer et al. 2020 and opening the door for simple layer-wise training schemes. Finally, we show that the studied networks admit an exact layer-widd wise projection result, Bayesian uncertainty quantification, and black-box recovery of network weights.
them. Among others,
INTRODUCTION
In the past several years, invertible flow networks emerged as powerful deep learning models to learn maps between distributions (Durkan al. 2019a Grathwohl et al. 2011 Huang et al. 2018 Jaini et al.] 2019) Kingma et al. Kingg & Dhariwal 2018 Kobyzee et al. 2020 Kruse et al.
2019 Papamakarios al. (019).. They generate excellent samples (Kingma & Dhariwal 2018 and
facilitate solving scientific inference problems (Brehmer & Cranmer 2020 Kruse et al. 2021).
By design, invertible flows are bijective and, hence, may not be natural choice when the target distribution has low-dimensional support. This problem can be overcome by combining bijective flows with expansive, injective layers, which map to higher dimensions (Brehmer & Cranmer 2020 Cunningham et al. 2020;; Kothari et al.) 2021). Despite their empirical success, the theoretical aspects of such globally injective architectures are not well understood.
In this work, we present approximation-thhorree combines bijective flows and expansive, injective layers, with an emphasis on approximating mea- sures with low-dimensional support. We state conditions under which these networks are universal approximators and describe how their design enables applications to inference and inverse problems.
properties of injective flows whose architecture
1.1
PRIOR WORK
The idea to combine invertible (coupling) layers with expansive layers has been explored by Brehmer & Cranmer (2200) and Kothari et al. (202T). Brehmer & Cranmer (2020) combine two flow networks with simple expansive element (in the sense made precise in Section 2.1 and ob- tain a network that paramterizes probability distributions supported on manifolds. They suggest that such constructions may be universal but neither they not Kothari et al. (2021) derive theoretical re- sults. We discuss in detail the connection between these two empirical works and the approximation results derived here in Appendix B.I
Kothari et al.) (2021) propose expansive coupling layers and build networks similar to that of Brehmer & Cranmer 20200) but with arbitrary number of expressive and expansive elements.
They observe that the resulting network trains much faster with smaller memory footprint, while producing high-quality samples variety of benchmark datasets.

---

Under review as a conference paper at ICLR 2022
While to the best of our knowledge, there no approximation-theorett results for injective flows, there exists a body of work on universality of invertible flows; see Kobyzev et al. (2020) for an overview. Several works show that certain bijective flow architectures distributionally universal. This was proved for autoregressive flows with sigmoidal activations by Huang et al. (2018) and for sum-of-squares polynomial flows by Jaini et al. (2019). Teshima al. (2020) show that several flow networks including those from Huang et al. (2018) and Jaini et al. (2019) are also universal approximators of diffeomorphisms.
The injective flows considered here have key applications in inference and inverse problems; for an overview of deep learning approaches to inverse problems, see |Aridge et al. (2019). Bora et al. (017)) proposed to regularize compressed sensing problems by constraining the recovery to the range of (pre-trained) generative models. Injective flows with efficient inverses as generative mod- els gives an algorithmic projectior[]nn the range, which facilitates implementation of reconstruction algorithms. An alternative approach is Bayesian, where flows are used to obtaín tractable varia- tional approximations of posterior distributions over parameters of interest, via supervised training on labeled input-output data pairs. Ardizzone et al. (2018) encode the dimension-reduuing forward process by invertible neural network (INN), with additional outputs used to encode posterior variability. Invertibility guarantees that a model of the inverse process is learned implicitly. For a given measurement, the inverse pass of the INN approximates the posterior over parameters. [Sun & Bouman (2020) propose variational approximations of the posterior using an untrained deep genera- tive model. They train normalizing flow which produces samples from the posterior, with the prior and the noise model given implicitly by the regularized misfit functional. In Kothaii et al. (2021) this procedure is adapted to priors specified by injective flows which yields significant improvements in computational efficiency.
1.2 OUR CONTRIBUTION
We derive new approximation results for neural networks composed of bijective flows and injec- tive expansive layers, including those introduced by Brehmer & Cranmer (2020) and Kothari et al. 2021). We show that these networks universally jointly approximate a large class of manifolds and densities supported on them.
We build on the results of Teshima al. (2020) and develop to as the embedding gap. This gap is measure how nearly a mapping from IR -+ R embeds an n--imensional manifold in R" where gap and the problem of approximating probability measures with wwwdimensional support.
theoretical device which we refer
We find natural relationship between the embedding
We then relate the embedding gap relaxation of universality we call manifold embedding prop- erty. We show that this property captures the essential geometric aspects of universality and uncover important topological restrictions the approximation power of these networks, heretofore unknown in the literature. We give an example of an absolutely continuous measure not be approximated with combinations of flow
knowledge,
and embedding f: 2² + I such that f # layers and linear expansive layers. This may be surprising since it was previously thought that net- works such as those of Brehmer Cranmer (2020) can approximate any "nice" density supported on "nice" manifold. We establish universality for manifolds with suitable topology, described in terms of extendable embeddings. Our proof shows that optimality the approximating network can be established in reverse: optimality of a given layer can be established without optimality of pre- ceding layers. This settles (generalization
a) conjecture posed for a two-layer case in (Brehmer & Cranmer, 2020). Finally, we show that these universal architectures also practical and admit exact layer-wise projections, as well as other properties discussed in Section 3.4
2 DESCRIPTION OF THE ARCHITECTURE
Let C(X,Y) denote the space of continuous functions X Y. We study networks in F C C(X, Y) that are of the form:
F F= The
R.d. 1 o o R o Too
(1)
Idemppoeen but in general not orthogonal.
2

---

Under review as a conference paper at ICLR 2022
where Rg R C C(R R")), Th" C(R",R"") N is the number of networks, ng n, T = m, and ne 2 nt-1 for ==r==1,.... ....,.. We introduce a well-tuned shorthand notation and write H. = [ g: h g. 9) throughout the paper.
We identify R with the expansive layers and T with the bijective flows. Loosely speaking, the pur- pose of the expansive layers is to allow the network parameterize high-dimensional functions by low-dimensional coordinates an injective way. The flow networks give the network the expressiv- ity necessary for universal approximation of hanifold-supported distributions.
2.1 EXPANSIVE LAYERS
The expansive elements transform n-dimensional manifold M embedded in R=--1, and embed it in a higher dimensional space R"v To preserve the topology of the manifold, this must be done injectively. We thus make the following assumptions about the expansive elements:
Definition 1 (Expansive Element). Let é = 1, ..... L, and R, R be family of functions from RM R" R, 1,ne is family of expansive elements if every R, 1,ne is injective and
Lipschitz.
Examples of expansive elements include
(R1) 7ero padding: R(x) = [x o(mm-n)] where (mm-x) is the zero vector Brehhee & Cran-
mer 2020).
(R2) Multiplication by arbitrary full-rank matrix, one-by-one convolution:
R(x) Wx, or R(x) x
(2)
where W mxxx and rank (W) = n (Cunningham et 2020). and is convolution
kernel denotes convolution Kingma & Dhariwal (2018).
(R3) Injective ReLU layers: R ReLU(Wx). W -DT MTJ R(x) ReLU [ww,-wt x) for matrix B GL, (R), positive diagonal matrix D R=*= and arbitrary matrix M E (m-mm2)x (Puthawala al. 2020).
(R4) Injective ReLU networks (Puthawala al. 2020 Theorem 15). These are functions
IR" + R of the form R(xx) WL+1 ReLU ReLUUWW bi)).).....) +b,, where W, are n1+1 ni matrices and b, are the bias vectors Ro+++ The weight matrices Wy. satisfy the Directed Spanning Set (DSS) condition for e < L (that make all layers injective) and WL+1 is generic matrix which makes the map R RR - R" injective. Note that the DSS condition requires that ng 2 2n,-1 + for é < L and we have n, and 71411
2.2 BUEETIVE FLOW NETWORKS
The bulk of our theoretical analysis is devoted to expressive elements. The expressive elements bend the range of the expansive elements into the correct shape. We make the following assumptions about the expressive elements:
Definition 2 (Bijective Flow Network). Let é. =0.-.... 0..... be given and let T c C( R.*).-
Tie is a family of bijective flow networks if every T E Tie Lipschitz continuous and bijective.
Examples of bijective flow networks include
(TI) Coupling flows, introduced by Dinh et al. (2014) consider R(x) HA ....o ... Hx(x) where
H+(x) hi ([x) 1 Is ([x)a41mn))
x x
Eqn. h;: Rd R + Rdd is invertible w.r.t the first argument given the second, and g: 1
- R is arbitrary. Typically in practice the operation in Eqn. 3 combined with additional invertible operations such as permutations, masking or convolutions Dinh et al.
(2014 2016); Kingma & Dhariwal 2018).
3

---

Under review as a conference paper at ICLR 2022
(T2) Autoregressive flows, introduced by Kingma al. (2016) are generalizations of triangular flows A: I=" - IR" where for = 1...., n the 1 I'th value of A is given by of the form
[A], (x) - hs ([x), 9e ((xl==-1)
In Eqn. h,: R R + R where again h2 is invertible w.r.t. the first argument given the second. and g: Pi + T is arbitrary except for 91 O. In Huang et al. (2018), the authors choose (r, y), where y E Iem, to be a multi-layer perceptron (MLP) of the form
y) = ø o P.y ..... o o (1)
(5)
where Φ is a sigmoidal increasing non-linear activation function.
3 MAIN RESULTS
3.1 EMBEDDING GAP
We call a function f an embedding and denote it by f emb(X,,) if X + Y is continuous, injective, and f===((x) f(X) + X is continuous Also we denote emb* & (R" RT) = emb(IR". IR² n O (IR", ,. In order to set up our result concerning embedding of manifolds, we first need way to measure the degree to which a mapping E emb( (Ro, I)" nearly embeds a manifold M = f(K for compact K C R and ff E cmb(K, K, "... With this mind we introduce embedding gap Bx.w(f. (f.g). g). non-symmetric notion of distance between f and g. Later in the paper, f will be the function to be approximated, and g a flow-network to the approximator.
Definition 3 (Embedding Gap). Let K C IR" be compact and non-empty, W RR contain the closure of set U which is open in the subspace topology of some vector subspace V of dimension p, where n S p S S m, I E emb(K, "R.",, and E emb IRT"). Then we define the Embedding Gap between f and y sets K and W as
inf Bk,((,9)) rEmmb(((K))a(w)
|| (((K))((K))
where 1: f(K) + S(K) the identity function and |||])==(x) ess se [1(x))]2 for h: X Y. We refer the embedding gap between ff and g without specifying K and W when it is clear from context.
Remark 1. As W C R' contains U, an open set in V. there is an affine map A R" + V such that A(K) W. Then, the map To = go A f- f(K) + g(W) an injective continuous map from compact set to its range and hence ro cmb(f(()) ((W)) Thus, in the above infimum the set (mb(f((), (W)) is non-empty.
Before giving properties of BK, w (f.g). we briefly describe its interpretation and meaning. We denote by P(X) the set of probability measures over X. If the embedding gap between two func- tions is small, then is nearly an embedding of the range of f into R Br, (f (f constructed expressly serve upper bound
inf PeEP(W)
We (f Pas P*n0) S Bk,W(s9)
where (he E PPK) is given, and W2 (M1 v2) denotes the Wasserstein-2 distance with e ground metric (Villani 2008), shown in Lemma part 5. The above result has simple meaning in the context of machine learning. Suppose we want to learn a generative model g to (approximately) sample from a probability measure with now-dimensional support, by applying g to samples from a base distribution 14o- Suppose further that v is a pushforward of some (known or unknown) dis- tribution Pn via f. The embedding gap Bx,w (f.g) g) then upper bounds the 2- Wasserstein distance between / and g# Ho for the best possible choice of p.
NNoe that if X is compact then continuity of the of f-1 f(X) X is automatic, and need not be assumed (Sutherland 2009 Cor. 13.27). Moreover, if RD R. is continuous injective map that satisfies [f(z)) + 2o as x Do, then by (Mukherjee) 2015 Cor. 2.1.23) the map f f(R") ) - R² is continuous.
"The choice of Wasserstein distance is suitable for measures with mismatched low-dimensional support;
this has been widely exploited in training generative models (Arjovsky et al. 2017).
4

---

Under review as a conference paper at ICLR 2022
Figure I: A visualization of the embedding gap. In all three figures we plot and gi for Left: 1, Center: = 2 and Right: i 333. Visually, we see that 9i approaches f' as increases, and we compute Br.w (f. Bx, (f.2)) (f O.
The embedding r can be interpreted candidate transport map from any measure pushed forward r o f is valid
by f. that can be pulled back through Loosely speaking, for μ4 Wasserstein transport map that transports f Pr, 9 9 with cost no more than || r (((()))))) See Fig.
[ for a visualization of the embedding gap between two toy functions. Further, the em- bedding gap satisfies incqualities useful for studying networks of the form of Eqn. [ see Lemma
3.2 MANIFOLD EMBEDDING PROPERTY
We introduce central concept, the manifold embedding property (MEP). A family of net- works satisfies the MEP if it nearly embeds large class of manifolds of certain dimension and regularity, as measured by the embedding gap. The MEP property of family of functions go C emb(W, (..b RT) where W C Ro. For this manuscript, go.m will always be formed by taking go.m 7 Ro.m
We note here that the MEP is closely related to the question of whether or not given n--dmmensiona manifold M that is an image of an embedding f K + Rm, that is, M = (K), C R", can be approximated by the images of neural networks E K + 1 of a given type. In particular, will consider neural networks that are compositions where R R >> R are 'simple' non-universal functions, and flow-maps T Rmm - I that are diffeomorphism. This choice of applying non- universal expansive layers, and then diffromorphisms has some topological consequences, which we discuss below.
TOPOLOGICAL OBSTRUCTIONS TO MANIFOLD LEARNING WITH NEURAL NETWORKS
We find that using non-universal expansive layers, followed by layers imposes conditions on what can be approximated. We illustrate this with the following problem. When
topological
and K S 2 the circle. We consider maps E T R R" - g. where R 12nh + RT is, e.g., a linear map of rank n, and T' T + RT is coupling flow which is homeomorphism. Let f E emb(K, (K, R2) be an embedding that maps K a trefoil knot M -(S)) see Fig. 2 Such function ff can not be written as restriction T o R on S'. In Sec. C.2.2 we prove this fact and build related example where a measure, μ E P(R2)). supported on an annulus is pushed forward to measure supported on knotted ribbon in R3 by embedding y: IR2 - RR3 For this measure, there are no F. == T o R, with linear injective R and embedding T, such that
2,
To sidestep this fundamental difficulty, we define the MEP property for certain subclass of mani- folds (f(K): E Finally, when considering flow networks which are universal approximators of C² diffeomorphisms, we restrict the class of manifolds to be approximated even further. This is because manifolds that are homeomorphic spheres. These are topological structures that are homeomorphic, but not diffcomorphic, to the sphere Milnor (1966). Moreover, it is known that general homeomorphisms F I R
not necessarily diffeomorphic; for example exotic

---

Under review as a conference paper at ICLR 2022
Figure 2:
An illustration of the case when n 2, m 3, and K 5 is the
circle. Here f S + I is embedding such that the curve M f(S²) is trefoil knot. Due to knot theoretical reasons, there are no map E = T o R
IR R such that ) map and T R + R
M, where R IR - R is a full rank linear a homeomorphism. This shows that a combination of linear maps and coupling flow maps can not represent all embedded manifolds. For this reason, we define the class I(R", IR"") of extendable embeddings f- A similar 2-dimensional example can be obtained knotted ribbon, see Sec.
C.2.2
not be approximated in -oooooology by C²-smooth diffeomorphisms T R I See Müller (0014) for a precise statement. However, all C"-smooth diffeomorphims F R" + R can be approximated in the strong topology of C2 by C2-sootth diffeomorphims F: Rm - Rm, l 2 k see Hirsch (2012), Ch. 2. Theorem 2.7. Because of this, we have to pay attention the smoothness of the maps in the subset JF C emb (K, ).)
For these reasons, when we refer the MEP, we consider it with respect to a class of functions F C emb(IR", ). The MEP can be interpreted as a density statement, saying that our networks go. are dense in the "Bx.w distance' in the set F C emb(R", R Two examples we are particularly interested in are the following. First, when F = oo A where A Ih" - R are linear maps of rank n and + : R. + T. are C* diffeomorphisms with k 2 1. Second, when F E emb((R", IR"".
Definition 4. Let Ed. C emb(R", RT)) and F emb((R", R.") be two families of functions. We say that ga.m has the m. n, o Manifold Embedding Property (MEP) w.r.t. Fa.m if for every compact non-empty set K C TR", / F..m and >> O, there an E go.m and compact set W C R' such that the restriction of f in K and the restriction of E' in W satisfy
Bk, E) <
When it is clear from the context, we abbreviate the m, o MEP w.r.t. Fu.m simply by the m, nt, MEP, or simply the MEP.
We also note here that if a model from R + R" is uniform universal approximator of Fo.m C CRRR", RT) on compact sets, such as those considered in Yarotsky (2017) 2018), then it has the m, n, MEP w.r.t For any S o. Thus, networks that are uniform universal approximators However, we have a result that applies to automatically possess the MEP, as shown in Lemma [ network which are uniform universal approximators.
Definition 5 (Uniform Universal Approximator). For a non-empty subset Fa,m C C(R", RT),, a family m C(R", ,"") is said be uniform universal approximator of JaHm if for every f E Fu.m every non-empty compact K C R", and each > 0, there is an E' E ga.m satisfying:
sup [ E( <.
zek
We also have the following function class, which is key to our analysis.
Definition 6 (Extendable Embeddings). Let I(R", , RT') be the set of functions F R + R. that are compositions F = & R where R R + Rm is a linear map of rank and & R + R is a C² -smoohh diffeomorphism. We call I denote I (R". PTT) I(R", RT) n O* (R" Rm). We observe that I(R", R!)) C cmb(RR", R")).
[(R n Im)) ) be the set of extendable embeddings. We also
Lemma 1.
(i) Rf is a universal approximator of C(B", RT") and 1 E T where I is the identity map, then go.m = T a Ro.. has the MEP w.E. (R",R")
(ii) R is such that there is an injective R E R and open set U C R. such that R| is linear, and T is sup universal approximator in the space of Diff (R.m RTT), in the sense Teshima et al. 22020), of the C2 Cm-smooth diffeomorphisms, then go.m = T Ro has the MEP w.r.. F I(2", (...
The proof of Lemma 1 is in Appendix C.2.1
It has the following implications for the architectures
studied in Section 2
Example 1. Let 3 = T o Romm then

---

Under review as a conference paper at ICLR 2022
(i) If T is either (T1) (T2) and Ram is (R4), then 8om has the MEP w.r.. emb(R" (n")
(ii) If Th th is (T2) with sigmoidal activations Huang et al. 2018), then if Rom is any (RI), (R4), then go has the m, n, MEP Z(R", "))).
The proof of Example D is in Appendix C.2.3
We add remark here showing that if m is sufficiently larger than n, and subject some regularity assumptions, The two classes considered in Example Coamppeeccoine coincide.
Lemma 2. When m 2 3n + 1 and k 2 for any C embedding f E emb (R" " R and compact set C RRn there is map in the closures of the flow rype neural network E I (R." Rm)) such that E K) [(K). Moreover,
1t (K, emb emb"(K, (K)
This means that the topological structure of manifold to approximate M in Ih" is diffeomorphic to the set K C R", and thus some flow type network can approximate M.
The proof of Lemma in Appendix C.2.4
We finally have two more lemmas to present before moving on to our discussion universality as it ties to the MEP.
Lemma 3. Let FF.00 C cmb(R" RR) and Fo.m emb(RR Rm) Ep C cmb(R" o.n.p MEP W.EL Fu. C RR" Ro) and Eq E.. emb(RR R'') have the m, 0,0 MEP w.r.t Fr.m C emb(Ro, R.m). each Eg E E is locally Lipschitz, then Ex.T o cp.o has the m, P.P MEP w.E. Fo.m Fn.o
(R,,, RR) have the
The proof of Lemma 3 is in Appendix
We note that when the elements of Co differentiable, local Lipschitzness is automatic, and need not be assumed, see e.g. (Tao 2009 Ex. 10.2.6). We also record near-converse (proved in C.2.6 of Lemma that shows that if Eo o E Ep.o has the m, n, MEP, then E gg. has the m, n, MЕP.
Lemma 4. Let C emb(R", R.)). Let ETt C emb(RR RR)) and g.. C emb(RR, R.)) be such that t. o EP. has the m, n, MEP with respect to family F. Then E has the m, n, MEP with respect to family F.
3.3 UNIVERSALITY
We present universal approximation result for networks given in Eqn. Eq. and decou- pling property.
n, m. 1 E P(K) be an absolutely continuous measure w.r.f. Lebesgue measure. Further let, for each = 1882
Theorem 1 (Qualitative Universality for Embeddings). Let no
Eg 101-1 = TTe R 1h where R 1:2e is a family of injective expansive elements that contains a linear map, and The is family of bijective family networks. Finally let To be distributionally universal, i.e. for any absolutely continuous μ E P(R)) and v E P(R"), there is {Tik 00 such that T1 - in distribution, Suppose that one of the following two cases hold:
(i) Let F FRL-1, o.... Fi and E 1. have the the Tig n,, ne-1 MEP respect F. 1
....., with
(ii) Let F emb (RR", ReT,, IRT")) be a -m-soh embedding, and assume that for E 1,..,, it holds that nı -----1+ +1 and the families T are dense the space of C² d--iffeommrrhism Diff (RTe).
Then, there is sequence of
C 1.
o eni To such that
lim We (F E O. 1-000
(10)
The proof of Theorem M is in Appendix C.3.I As discussed in above and Figure
there are topological obstructions for Theorem 1 with general embedding F R Rd When 2,

---

Under review as a conference paper at ICLR 2022
m 3, L 1, and j is the uniform measure an annulus K I2 target measure F# fs is the uniform measure on knotted ribbon M F(K) C R.. There are no injective linear maps R RR² - TR.3 and diffeomorphisms T: : TR3 + R such that F = R would satisfy M =(K) and E F# This happen even though the set of diffeomorphism T R + RR are universal distributional approximators. In this case the condition m = n1 2 3n + 1 is not valid.
We remark here that our networks are designed expressly to approximate manifolds, and hence injectivity is key. This separates our results from, e.g. (Lee et al. 2017 Theorem 3.1) or (Lu & Lu 2020 Theorem 2.1), where universality results of ReLU networks also obtained.
The previous theorem shows that the entire network is universalif it can be broken into pieces that have the MEP. The following lemma, proved in Appendix C.3.2 shows that if g. Hom gm. then Ho. must have the m, n, o MEP if g is universal.
Lemma 5. Suppose that m = H Gn where - C emb(R", ,R"). H C emb(RR" R.)",, and Gu. C emb(R" 12). If Hom does not have the m, MEP w.r.. F, then there exists a f E F, compact K C R" and e > such that for all E gn.m and E cmb(f(K),E(W))
|14 26.
(11)
The proof of Theorem I also implies that, loosely speaking, later layers decouple from earlier ones. That is, given a sequence of functions that has the MEP on the last L é layers, there are always functions in the first & layers so that the entire network end-to-end optimal.
Corollary 1. Let Fu. emb(R" RR), Fom C emb(RR, RT)). and let g emb(R R have the m, n,, m,n, O MEP w.rt. Fa.m Fu... For every F E Fo,m o Fu. then there is compact
K C Rn and (Fx) C C such that
lim BK, = O. 842
(12)
Further, if gno C emb(WW, (R)) has the o, n. n MEP w.r.t. Fhio, and T is a universal approx- imator for distributions, then for any p E P(K) where K C RR" is compact, there is a sequence (E [Biis......o C En.o and {Ti)
1ifiil,.,,. C TT" so that
lim W2 (F #1, E, o E Ti O. 1-000
(13)
Approximation results for neural networks are typi- cally given in terms of the network end-to-end. Corollary [ shows that the layers of approximating networks can in fact be built one at a time. It is related to an observation made in (Brehmer & Cran- mer 2020, Section B) about training strategies, where the authors remark that they "expect faster and more robust training of network' of the form in Eqn. when L = 1, that is F = -T," o R - T." Corollary shows that there exists minimizing sequence in T,M that need only minimize Eqn. T2] the To" layers can be minimized after. We can further combine Lemma and Cor. to prove that not only can the network from Brehmer & Cranmer (200)) be trained layerwise, but that any universal network can necessarily be trained layerwise in reverse order, provided that it can be written composition of two smaller layers.
The proof Corollary iis in Appendix C.3.3
|
3.4 LAYER-WEL WISE INVERSION, UNCERTAINTY QUANTIFICATION AND RECOVERY OF WEIGHTS
In this subsection, we describe how our network can be augmented with more useful properties if the architecture satisfies few more assumptions without affecting universal approximation. We focus on new layerwise projection result, with a further discussion of Bayesian uncertainty quantifica- tion, and black-box recovery of our network's 's weights in Appendices D.2 & D.3
Given point y E I. that does not lie the range of the network, projecting y onto the range of the network is practical problem without obvious answer. The crux of the problem is inverting the injective (but non-invertible) R layers when R. When R contains only full-rank matrices as in (R1) or (R2) then piecewise linear, as in (R3), then the problem of computing a least squares solution is more difficult, Fig. Nevertheless, we find that if R is (R3) we can still compute a least-squares solution.
compute a squares solution. If, however, R contains layers which are only
8

---

Under review as a conference paper at ICLR 2022
2/5
Figure 3: A schematic showing that, for toy problem, the least-squares projection to a piecewise affine range can be discontinuous. Left: A partitioning of IR into classes with gray boundaries. Two points y, y are in the same class if they are both closest to the same affine piece of R(R), the range of R. The three points y1, 3/2 and yo are each projected to the closest three points on R(R) yielding W1, f/2 and ø3. Note that the projection operation continuous within each section, but discontinuous across gray boundaries between section.
1/2
1/a
3/ 30>
Assumption 1. Let R. be given by one of (RI) (R2), else (R3) when m 2n.
If R. only contains linear operators, then the least-squares problem can be computed by solving the normal equations (see (Golub) 1996 Section 5.3).) This includes cases (R1) or (R2). For (R3) we have the following result for D Iaxn and M is an empty matrix.
Definition Let W
B -DB'' m and y E TR be given, and let R(x)
ReLU(Was x)) Then define
c(u) = max ( (-mxx
-nxxn
c(y) E 2n
naxn v2
(14)
(0 if [cly)linn
A, Rnxn AAp = {1 if [c(y))in >
[Aylis Oifi
(15)
My E B
My = [[rnx= - Au) Ay]
(16)
where the max Eqn. 14 taken element-wise.
Theorem 2. Lery E 2n for i = 1....,,,, n,, [yle * 1y then
(v) (M, M3y argmin lly R(x)l22- =ER"
(17)
Further, if there is aii fl.....my m) such that [y], Iu then there multiple minimizers of lly - R(x)l2, one of which Rt (y).
The proof Theorem is given in Appendix D.I
Remark 2. We note that Theorem is different from many of the existing work on inverting expan- sive layers, e.g. /Aberdam al. (200)): BBoa al.) (2117): Lei et al.) (2019), our result gives direct inversion algorithm that is provably the least-squares minimizer. Further, if each expansive layer is any combination of (RI), (R2), or (R3) then the entire network can be inverted end-to-end by using
either the above result or solving the normal equations directly.
4 CONCLUSION
Bijective flow networks a powerful tool for learning push-forward mappings space of fixed dimension. Increasingly, these flow networks have been used in combination with networks that increase dimension in order to produce networks which are purportedly universal.
In this work, we have studied the theory underpinning these flow and expansive networks by in- troducing two new notions, the embedding gap and the manifold embedding property. We show that these notions are both necessary and sufficient for proving universality, but require important topological and geometrical considerations which are, heretofore, under-explored in the literature. We also find that optimality of the studied networks can be established 'in reverse," by minimizing the embedding gap, which we expect opens the door to convergence of layer- wise training schemes. Without compromising universality,
can also wise projection result. Moreover, we show that the studied networks provide Bayesian uncertainty quantification and allow block-box recovery of their weights.
specific expansive layers with new layer-

---

Under review as a conference paper at ICLR 2022
REFERENCES
Aviad Aberdam, Dror Simon, and Michael Elad. When and how can deep generative models be inverted? arXiv preprint arXiv:2006.15555, 2020.
Luigi Ambrosio, Nicola Gigli, and Giuseppe Savaré. Gradient flows: in metric spaces and in the space of probability measures. Springer Science & Business Media, 2008
Lynton Ardizzone, Jakob Kruse, Sebastian Wirkert, Daniel Rahner, Eric W Pellegrini. Ralf
Klessen, Lena Maier-Hein, Carsten Rother, and Ullrich Köthe. Analyzing inverse problems with invertible neural networks. arXiv preprint arviv: 10X.vv1808.0440 1808004730 2018.
Martin Arjovsky, Soumith Chintala, and Léon Bottou.
Wasserstein gan.
arXiv preprint
arXiv:1701.0755 2017.
Simon Arridge, Peter Maass, Ozan Öktem, and Carola-Bibiane Schönlieb, Solving inverse problems using data-driven models. Acta Numerica, 28:1-174, 2019.
Ashish Bora, Ajil Jalal, Eric Price, and Alexandros Dimakis. Compressed sensing using genera- tive models. In Proceedings of the 34th International Conference on Machine Learning- Learning-Volume 70, pp. 537-546. JMLR. org, 2017.
Johann Brehmer and Kyle Cranmer. Flows for simultaneous manifold learning and density estima- tion. arXiv preprint arXiv:2003.13913. 2020.
Phuong Bui Thi Mai and Christoph Lampert. Functional vs. parametric equivalence of relu net- works. In 8th International Conference Learning Representations, 2020.
Edmond Cunningham, Renos Zabounidis, Abhinav Agrawal, Ina Fiterau, and Daniel Sheldon. Nor- malizing flows across dimensions. arXiv preprint arXiv:2006. 13070, 2020.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components esti- mation. arXiv preprint arXiv:1410.8511 2014.
Laurent Dinh, Jascha Sohl-Dickstein. and Samy Bengio. Density estimation using real nvp. arXiv preprint Xiv: 1 605.08803, 2016.
Conor Durkan, Artur Bekasov, lain Murray, and George Papamakarios. Cubic-spline flows. arXiv preprint Xiv: 196600245, 2019a.
Conor Durkan, Artur Bekasov, lain Murray, and George Papamakarios. Neural spline flows. Advances in Neural Information Processing Systems, 12:7511-75271 2019b.
Gene H Golub. Matrix computations. Johns Hopkins University Press, 1996.
Aidan N Gomez, Mengye Ren, Raquel Urtasun, and Roger Grosse. The reversible residual net- work: 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.
Morris W Hirsch. Differential topology, volume 33. Springer Science & Business Media, 2012.
Chin- Wei Huang, David Krueger, Alexandre Lacoste, and Aaron Courville. Neural autoregressive flows. In International Conference Machine Learning, pp.
PMLR, 2018.
Michael F Hutchinson. stochastic estimator of the trace of the influence matrix for laplacian smoothing splines. Communications in 1989.
and Computation. 18(3):1059-107,
Jörn Hörn-Henrik Jacobsen, Amold Smeulders, and Edouard Oyallon. i-revnet: Deep invertible networks.
arXiv preprint aiviv: 802.07088, 2018.
10

---

Under review as a conference paper at ICLR 2022
Priyank Jaini, Kira A Selby, and Yaoliang Yu. Sum-of-square polynomial flow. In International Conference on Machine Learning. pp. 3009-3018. PMLR, 2019.
Diederik Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, Πlya Sutskever, and Max Welling. Improving variational inference with inverse autoregressive flow. arXiv preprint arXiv:1606.0492. 2016.
Durk P Kingma and Prafulla Dhariwal. Glow: Generative flow with invertible Ixl convolutions. In Advances in Neural Information Processing Systems, pp. 10215-10224, 2018.
Ivan Kobyzev, Simon Prince, and Marcus Brubaker. Normalizing flows: An introduction and review of current methods. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2020.
Konik Kothari, AmirEhsan Khorashadizadeh, Maarten de Hoop, and Ivan Dokmanic. Trumpets: Injective flows for inference and inverse problems. arXiv preprint arXiv:2 102.11111, 2021.
Jakob Kruse, Gianluca Detommaso, Robert Scheichl, and Ullrich Köthe. Hint: Hierarchi- cal invertible neural transport for density estimation and bayesian inference. arXiv preprint arXiv:1905. 106877 2019.
Jakob Kruse, Lynton Ardizzone, Carsten Rother, and Ullrich Köthe. Benchmarking invertible archi- tectures on inverse problems. arXiv preprint urXiv:2101.10633 2021.
Holden Lee, Rong Ge, Tengyu Ma, Andrej Risteski, and Sanjeev Arora. On the ability of neural nets to express distributions. In Conference on Learning Theory, pp. 1271-1296. PMLR, 2017.
Qi Lei, Ajil Jalal, Inderjit S Dhillon, and Alexandros G Dimakis. Inverting deep generative models, one layer at a time. In Advances in Neural Information Processing Systems, pp. 13910-13919, 2019.
Yulong Lu and Jianfeng Lu. A universal approximation theorem of deep neural networks for ex- pressing distributions. arXiv preprint arXiv:2004.08867, 2020.
Madsen, Jxrgen Tornehave, et al. From calculus to cohomology: de Rham cohomology and characteristic classes. Cambridge university press, 1997.
John Milnor. On manifolds homeomorphic to the 7-sphere. Annals of Mathematics, pp. 399-405, 1956.
Amiya Mukherjee. BirkhääueerSSpriner,, Cham, second edition, 2015.
Differential topology.
Hindustan Book Agency, New Delhi; ISBN 978-3-319-1904400 978-3-319-
19045-7. doi: 10.1007/978-33319-99957.
URL
978- 378-3-319-19045-1
Stefan Müller. Uniform approximation of homeomorphisms by diffcomorphisms. Topology and its Applications, 178:315-319, 2014.
Kunio Murasugi. Knot theory & its applications. Modern Birkhäuser Classics. Birkhäuser Boston, Inc., Boston. MA. 2008. ISBN 978-0-8176-4718-6 doi: (007/978-0-8176-47777 Translated from the 1993
URL /tttps://A //doi. JJaaansse original by Bohdan Kurpita, Reprint of the 1996 translation [MR1391727].
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lak- shminarayanan. Normalizing flows for probabilistic modeling and inference. arXiv preprint arXiv:1912.02762. 2019.
Michael Puthawala, Konik Kothari, Matti Lassas, Ivan Dokmanić, and Maarten de Hoop. Globally injective relu networks. arXiv preprint arXiv:2006.08464, 2020.
David Rolnick and Konrad Körding. Reverss--nginnerring deep relu networks. In International Conference Machine Learning, pp. 8178 8187. PMLR, 2020.
Carlo H. Séquin. Tori story. In Reza Sarhangi and Carlo H. Séquin (eds.), Proceedings of Bridges 2011: Mathematics, Music, Art, Architecture, Culture, pp. 121-130. Tessellations Publishing, 2011. ISBN 978-0-9846042---5.

---

Under review as a conference paper at ICLR 2022
He Sun and Katherine L Bouman. Deep probabilistic imaging: Uncertainty quantification and multi- modal solution characterization for computational imaging. arXiv preprint ExXiv20010.14460 2020.
Wilson Sutherland. Introduction to metric and topological spaces. Oxford University Press, Oxford, 2009. ISBN 978-0-19- 19-956338-11 Second edition [of MR0442869), Companion web site:
Terence Tao. Analysis, volume 185. Springer, 2009.
Takeshi Teshima, Isao Ishikawa, Koichi Tojo, Kenta Oono, Masahiro Ikeda, and Masashi Sugiyama. Coupling- invertible neural networks are universal diffeomorphism approximators. arXiv preprint arXiv:2006.1 1469, 2020.
Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
Dmitry Yarotsky. Error bounds for approximations with deep relu networks. Neural Networks, 94: 103-114, 2017.
Dmitry Yarotsky. Optimal approximation of continuous functions by very deep relu networks. In Conference on Learning Theory, pp. 239-649. PMLR, 2018.
APPENDIX A SUMMARY OF NOTATION
Throughout the paper we make heavy use of the following notation.
1. Unless otherwise stated, X and Y always refer to subsets of Fuclidean space, and K and W always refer to compact subsets of Fuclidian space.
2. f E C(X,Y) Y) means that f: X
is continuous.
3. For families of functions FF and 9 where each F f X Y and = g: Y + Z, then we define G o F = {g o : X - Z: E F, gE
4. f E emb(X, Y) means that f C(X, Y) is continuous and injective on the range of f. is continuous.
i.e. an embedding, and furthermore that f f(X)
5. μ E P(X) means that f is probability measure over X.
6. W2 (1,,)) for Je, P(X) refers to the Wasserstein-2 distance, always with & ground
metric.
7. (1)l)z(() refers to the LP norm of functions, from to
8. For vector-valued f: X Y, [ ess csssup Ilfll22 Note that Y is always finite dimensional, and so all discrete S q S oo norms are equivalent.
9. Lip(g) refers to the Lipschitz constant of f.
10. For I", [x], E the i'th component æ. Similarly, for matrix Rax, [A] refers to the j "th element in the i'th column.
APPENDIX B DETAILED COMPARISON TO PRIOR WORK
B. CONNECTION TO BREHMER & CRANMER (2020)
In Brehmer & Cranmer (020). the authors introduce manifold-learning flows as an invertible method for learning probability density supported low-dimensional manifold. Their model can be written as
F= Th o Rmm To
(18)
12

---

Under review as a conference paper at ICLR 2022
{
nux O(m=n)xn
where 71 C C(R",, R,"),, TOth C C(R", and R.
a zero-padding (RI).
They invert F F in two different ways. For manifold-learmine flows (M-flows) they restrict 71" to be an invertible flow, and for manifold-lcarning flows with separate encoder (Ma-flow)) they place such restrictions 71th and instead train separate neural network to invert elements of TT"
Our results apply out-of-the-boo box the architectures used in Experiment A of Brehmer & Cranmer (2020). The architecture described in Eqn. [8] is of the form of Eqn. [ where L = 1. Further, although they are not studied here, our analysis can also be applied quadratic flows.
The network used in (Brehmer & Cranmer 2020 Experiment 4.A) uses coupling networks, (T1), where 71"H and To" are both layers deep. For (Brehmer Cranmer 2020 Experiments 4.B and 4.C) the authors choose expressive elements T that are rational quadratic flows Durkan et al. (2019b) for both 71 and To" they again let Ti by 20 layers deep and To 15 layers. For the final experiment, 4.D, the choose more complicated expressive elements that combine Glow Kingma Dhariwal (2018) and Real NVP et al. (2016) architectures. These elements include the actnorm, 1 x convolutions and rational-quadratic coupling transformations along with multi-scale transformation.
Experiment 4.B they let Tj and To again be layers deep, and 4.C
The authors mention universality of their network without our proof, but our universality results in Theorem
[ apply to their networks from Experiment A wholesale. Further in their work the authors describe how training can be split into manifold phase and density phase, wherein the manifold phase T is trained to learn the manifold, and in the density phase Ti if fixed and To" is trained to learn the density thereupon. This statement is made formal and proven by Cor.
B.2 CONNECTION TO KOTHARI ET AL. (2021)
In Kothari et al. (2021), the authors introduce the 'Trumpet' architecture, for it's architecture, which has many alternating flow networks & expansive layers with many flow-networks in the low- dimensional early stages of the network, which gives the architecture shape similar to the titular instrument.
The architecture studied in Kothari et al. (2021) is precisely of the form of Eqn. where the bijective flow networks are revnets Gomez et al. (2017) : Jacobsen al. (2018) architecture, and the expansive elements are x 1 convolutions, the revnets used are universal approximators, but if they revnets are substituted with either (T1) or (T2), then the, we could apply Theorem to the resulting architecture.
in (R2). To out knowledge, there are no results that show that
The authors of Kothari et al. (2021) also remark that their entire network can be designed in order to facilitate uncertainty quantification, remark that we too can apply to our networks, as discussed further in Section D.2
D.2
APPENDIX C PROOFS
C.I
MAIN RESULTS
C.1.1 HELPER LEMMA
Before presenting the proof of Lemma 7 we present the following three helper inequalities
Lemma 6. For all of the following results, f E emb(K,R*) R." and E emb(W, RR)) and n S 0 S m.
1.
B (f.g) 2 sup inf 119(x.) - f(xw)ll InEK N.EW
(19)
2. Let X,Y C W, let be Lipschitz on W. and r E emb(X, Y). Then, there is a r' e emb(g(X), (Y)) such that gor r' og and [ r' ((xx)))())) S || -l) Tip(g).
13

---

Under review as a conference paper at ICLR 2022
3.
|1 - (1) = -1----11 (1
(20)
4. Let K C RM X C R and W TR. be compact sets. Also, let e emb(K, W) and h E emb(X, W), and let g emb(W, be Lipschitz map. Then
B f.goh) & Lx, (x,x(,,)).
(21)
Proof.
1. Let E (()))) then
|I -1(
sup II -r)f((n)lll sup llf( f(zn)ll2
z, EK
znEK
= sup [lf(xx)) - g(xo)1l2 where To = 1 or f(In)
a,ck
2 sup inf [lf((.)) - g(xo)1l2-
zn B.EK
2. y is injective on X, hence we can define r' such that r'==''==' ggooogoroo-oo.o :(()) + s(r(X)) c
gYY) such that r' E emb(g(X).,g())) and thus Vx E E
|I
l1(x)) g gor(2)ll I Lip(g) || - -11-
(22)
where we have used ||<(x)) - x S r L=(x))
3. For every æ E r(K), we have y E K such that x = r(y), thus Vo E r(K).
[|(I - (z)]1, = (I(r- - (v)ll2
(23)
But is clearly surjective onto it's range, hence taking the supremum over all E yields
1 - r '1 (1( /|/ r ==()))
(24)
4. As g emb(W, R the map g W 9(W) is homeomorphism and there is g- E emb(g(W), W). For map r E emb(g e f(K), o h(X)), we see that g g emb(f(K), k(X)). Also, the opposite is valid as if f (Kb(f(K), then r r=gofog E emb(g f(K),g (())). Thus
BR,x f,goh)=
inf ((K)
inf -ogooog (kemblggs(())ggox))))
1| gorog (L
inf
11g (I - f) o --
< Lip(g)
inf (E)mb(((()).()))
||(I f) g ( '11.~(00/(K))
< Lip(g)
inf FE))b(((K)).(X))
||| i (](z=(((K))
< Lip(g) (f,x(f,h)
C.1.2 LEMMA 7 USEFUL. EMBEDDING GAP INEQUALITIES
Lemma 7. Let f emb(K, RT" and g E emb(W, R") and Sos Then the following hold:
1. Bk.w (f.g) S supzek llg o h(æ) f(x]ll2 where E emb(K,R") is map satisfying h(K) W.
2. For any X that the closure of an open set, if h E emb(X, W) then
Bk, S B Bk,x(J,gol)
(25)
14

---

Under review as a conference paper at ICLR 2022
3. For any emb(f(K), RT)),
Bk,w (J. S - + Bx,w(r f.9).
(26)
4. For any r E ( and E emb(X, W) where X C RP is the closure of compact set where S p S we have that
Bx. g h) S 1| ())) + oro where Lip(g) denotes the Lipschitz constant of g-
(27)
5. For any pn E P(K), there is a po E P(W) such that
W2 # I#1oo) & Bx,w (f.g).
(28)
The proof of Lemma 7
1. If we let = gohof then r eeb((((k), and
Bx.w(f.g) S III - r) (()))l)>>)))))
(29)
[ goho ff (-())
sup
[lf(z) gor()))
zek
(30)
2. Given that g (x) C ((W), we have that emb(J(K): h(X)) C emb(f((K) thus the infimum in Eqn. is taken over smaller set, thus Bx,w (f.9) (x.
3. Note that for any r' E emb(r ((K), r' or (mb([((). and we have
BR.w (f.g) & || - o (l1) $ || - r1l -11z=((())) + ||| - r' - r ()))))))))
(31)
|| -l) + /|/ r' -r(((=()))(()))
(32)
where we have used that is injective for the final equality. This holds for all possible r', hence we have the result.
4. Recall that S E emb(K,W), (mb(J(K),s(W)) Then g E emb(g(W)) W). Asro S(K) c (W), that
E emb(W, R"", h E emb(X, W) and E
ro f = ==f=oo0- orof.
This, Lemma 7 point and Lemma 6 point yield that
Br.x(f.goh) < || rl -l1,>(((1)) + Bx.x(rof.goh)
< || r(lz=()(k)) Bx. oro
x /| r111=(1115 ()(K)) + Lip(g) B Bxxx oro
which proves the claim.
5. Let r E (ab(f((),g(W)) be such that | - - 1ar-rlll-aRaaaa (Range())))))) < Bx.((ff)) + for 0, then for every I E K, there exists
W such that g(v) = ro f(z). From injectivity of g, we have that y = g prof(z) Note that g oro emb(K, W), hence K' g 1 oro f(K) is compact. Define μ = =gg orrorroo f) Clearly g #1,, and thus
We ( fw)) I W2 (awt' ro rofo#M sw + Wa (r o S#u,
(33)
but Wa (g r (H) and
1/2 < Bk. (f.9) tc.
We fu)) I (1L
(34)
This is true for every <> O, hence taking the infimum over all r E cmb(f(K) K)) establishes Wa (f & Bx,w(f.g) + for every 0, and thus have that W2 (g , s S (x.w(,gg.
15

---

Under review as a conference paper at ICLR 2022
C.2 MANIFOLD EMBEDDING PROPERTY
C.2.1 THE PROOF OF LEMMA 1
The proof of Lemmal 7
(i) Let us consider > 0, compact set K C R" and f e Let W K {0]o-n and R + Rm be the map given by
OR" R F(x,1) v) = f(x). v) E R" x R Because R is uniform universal approxi- mator of C(RR", IR",, there an R E Rom such that || Rll < E. Then for the
map E' = 1o o R we have that Bx,w(f, E) < This is true for every e > 0, and so go, has the MEP property w.r.t. the family emb(RR", I.
(ii Recall that f = Dp o Ro for Do E Diff'
and linear Rg: R" + R", and that E R is such that Ry is linear for open U. We present the proof in the case when n = o, and make the assumption that R| is linear. In this casc, we have the existence of an affine map A: RT + RT so that Rg = A o R so that K = Ro(K) = A(R(K)). Let e > 0 be given. By (Hirsch 2012 Chapter 2. Theorem 2.7), the space Diff (I8",, "R"" is dense in the space Diff' (R"". R"),, and so there is some $1 E Dift (I"", RT) such that
| IR Dol Polklle-(R:RR))
< 2'
Then, let T T be such that [ + o A..
Then we have that 1.
ITo R - (K)
IT R
20 o Rollo (x)
< I R 1 A R (1]) + 11 Ao R 2o (oll..
1
T
01 o o A (R(K)) + 1 Ao R
Po o A R (x())
E E
c.
2 2
Hence, if we let To Ro 8-1 E (m)( To R(K)) then we obtain that Bx. k (J, To R) < e. This holds for any e, and hence we have that T o R has the MEP for I(R", RR')
The proof in the case that 2 n follows with minor modification, and applying Lemma point 1.
C.2.2 S CAN NOT BE MAPPED EXTENDABLY TO THE TREFOIL KNOT
We first show that there are no maps E == T o R where R: R² + R3 such that T is a homeo- morphism and E(S²) is trefoil knot. We use the fact that the trivial knot S and the trefoil knot M =f("') are not equivalent, that is, there are no homeomorphisms in R that map S to M. In- deed, by (Murasugi 2008 Section 3.2), the trefoil knot M and its mirror image are not equivalent, whereas the trivial knot S and its mirror image are equivalent. Hence, M and R(S") are not equiv- alent knots in R3. Thus by (Murasugi 2008 Definition 1.3.1 and Theorem 1.3.1). we see that there is no orientation preserving homeomorphism T R R such that T(R R(S!)) )) R3 \ M.. As the orientation of the map T' can be changed by composing T with the reflection J : R + R3 across the plane Range( RR) that defines homeomorphim J : R3 R(S+) R R(S*), we see that there is no homeomorphism T R + R2 such that T T(R3 R(S") = R M.
This example shows that the composition E T of a linear map and a coupling flow T cannot have the property that E(S²) = f(S²) for this embedding f. Moreover, the complement R33 (S")) is never homeomorphic to R ((')) for any such map E.
We now construct another example, similar to Figure 2 where an annulus that is mapped to knotted ribbon in 3 To do this, replace the circle S' by an annulus K far R. 1/2 < |a| < 3/2), that in the polar coordinates is (r;,)) 1/2 < 3/2) and define map F: K + R3 by defining in the polar coordinates
F(r,0) 0) f()) + a(r ())(0)
where f: + Σj C R is an smooth embedding of S to a trefoil knot Σ, and v0) E R is a
unit vector normal to En at the point f(0) such that v()) is smooth function of 0, and >> is
16

---

Under review as a conference paper at ICLR 2022
small number. In this case, M1 F(K) is 2-dimensional submanifold of R2 with boundary, which can visualizes M1 as knotted ribbon.
We now show that there are no maps E = T R. such that E(K) = F(K) where T: RS R is an embedding, and R: R2² + R injective and linear. The key insight is that if such a T existed, then this implies that the trefoil knot is equivalent to 5 in RR, which is known be false.
Let (A) denote the p-neighborhood of the set in R is easy to see that R² \\ (f0) x [-), homeomorphic to IR2 \ Bga (0, 1), which is further homeomorphic to TR2 \ (0}. Thus, using tubular coordinates near 21 and a sufficiently small p > O, we see that R M1 is homeomorphic to R \ (21), which is further homcomorphic to I Σ1. Also, when R IR² + IR is an injective linear map, we see that M2 = R(K)) is a un-knotted band in R and R M2 is homeomorphic RS \ Σg. If R \ Mi and R$ \ M2 would be homeomorphic, then also R$ Ea would be homeomorphic that is not possible by knot theory, see (Murasugi 2008 Definition 1.3.1 and Theorem 1.3.1). This shows that there are no injective linear maps homeomorphisms 4 R2 + R such that ( o (K) = M1.
Σ, and R
R and
Similar examples can be obtained in a higher dimensional case by using a knotted torus Séquin 2011 and their Cartesian products.
C.2.3 THE PROOF OF EXAMPLE I
Proof.
ii) From (Puthawala al. 2020 Theorem 15) have that Ram can approximate
any continuous function J E emb(R" RT)). Further, clearly (T1) and (T2) both contain the identity map, thus Lemma ( applies.
(ii) Let T be the family autoregressive flows with sigmoidal activations defined in (Huang ct al. 2018). By (Teshima al. 2020) App. G, Theorem and Proposition 7), T are sup-universal approximators in the space Diff (IR".. ,R") of C²-smooth diffeomorphisms m is one of (R1) or (R2) the network is always linear, hence the + IR + T". When R
conditions are satisfied. If R is (R4), then Ram contains linear mappings, and if (R3), then we can shift the origin, so that R(x) linear on K. In all cases, Lemma part (ii) applies.
C.2.4 THE PROOF OF LEMMA 2
Given an f E emb (K, 1 we first show that for m 2 2n there are always a diffcomorphisms
V: IR' + _ so that V/ f: R" + (0) x R The existence of such V borrows ideas from
Whitney's s embedding theorem (Hissch 2012 Theorems 3.4 & 3.5) and is constructed by iteratively
constructing injective projection.
Next if m - n 2 2n + 1, then we can apply MMdsenn et al. 1997 Lemma 7.6), a consequence of the
Tietze extension theorem, to show that V .M - {0}" XR" can be extended to diffeomorphism on the entire space, h: IR + Rm Hence f(x) = 1- h a R(x) for diffeomorphism V--1
h: m + R. and zero-padding operator R: R - Th and thus f E T R"".
This fact that for m sufficiently large compared to n such a diffeommrphism can always be extended related the fact that in 4-dimensions, all knots can be opened. This can be contrasted with the case in Figure 2
Now present our proof.
Proof. Let use next prove Eq. when m 2 3n + L.L.tt
f emb (R.,, R"))
(35)
be a t map and M f(R") be an embedded submanifold of T
*On the knotted torus, www.erenceeceeeeeeeeoeee
2011-brion wwwrridgescoffeeeeeecee
17

---

Under review as a conference paper at ICLR 2022
We have that 2 3n 1>>>>> 2n + 1. Let 5mm be the unit sphere of R and let
STR m = {(2, u) E I x IR! | = 1}
be the sphere bundle of R that manifold of dimension 2m 1. By the proof's s of Whitney's embedding theorem, by Hirsch, (Hirsch) 2012 Chapter 1, Theorems 3.4 and 3.5), there is a set of "problem points' H1 C 5m-11 of Hausdorff dimension 2n such that for all w R H1 the orthogonal projection
P + [w] = {v E R". a W
has a restriction PulM on M defines an injective map
PolM: : M + {w}+.
Moreover, let M be the tangent space of manifold M the point and let define another set of "problem points" as
H₂ (u 5mm-: Rr M.M.TTMM
For w E 5m=11 H2 the map
PolM: : [w}- C R
an immersion, that is, it has an injective differential. The sphere tangent bundle SM of M has dimension 2n 1, and the set H2 has the Hausdorff dimension at most 2n 1. Thus H H1 H2 has Hausdorff dimension at most 2n < m and hence the set 5 И is non-empty, For E gm-11 \ H the map PulM M {w] is O injective immersion and thus
Ñ P (M) c {w)}
Ch submanifold.
Let Z (M + M be the O* function defined by
Z(y) M, Pu(Z(y)) y, that is it the inverse of PuelM M Pae (MM), where (MM [w]+ Le PM)(M) R be the function
g(y) (Z(y) 9) w, e (M
Then N is re-dimensional C submanifold of (m 1i-dimensional Euclidean space {w} and g is a O function defined on it. By definition of a C submanifold H, any point x E Ñ has a neighborhood U C H with local C* coordinates vb U + RT such that eNN n U) = ((0) ((0mm-1-n TR²) (U)).. Using these coordinates, in D. Using a suitable partition of unity, we see that there is a C* map G : {w]- R that a Ck extension of g that Gl
that be extended C* function
Then the map
Φ R R
& (I) ()P
is a O diffeomorphism of Rmm that maps M to dimensional space (w)+, that is
( C [w]+
In the case when m 2 3n + 1, we can repeat this construction n times. This is possible as m - n 2 2n + 1. Then obtain C diffeomorphisms +b Rm + R" 1,..., n such that their composition 4, o...o R - R is C diffcoommrphissm such that which
t o .... T (M) CY'
where Y C T m dimensional linear space. By letting v Q o D, o rotation matrix Q E Rmxmm we have that Y = Q(Y") (0) x gm--n Also. letting X
Φ1 for
1. (0) mmmm- m be the map
6(x, = v(f(z)) EY,
where f is the function given in Eq. 35 we have that Φ : X Y a Ch diffeomorphism. We apply Madsen al. 1997 Lemma 7.6) to extend o to
observe that 2n + 1 and a C diffccomoopphis
h R
R
18

---

Under review as a conference paper at ICLR 2022
such that h|x Φ. Note that (Madsen et al. 1997 Lemma 7.6) concerns extension of home- omorphism, but as the extension is given by an explicit formula which locally a finite sum of O functions, the same proof gives C* ("-diffeomorphic extension h to diffeomorphism ø. This technique is called the 'clean trick'.
Finally, obtain the claim, observe that when R R RR, R(x) (x, 0) {0)" x Rm- the zero padding operator, we have
((x) =
TER".
As h|x o and R(x)) X, this yields
[(x) V (((((())))), DER"
that is,
E=Eoft
where E 1 h R
1m is a C diffeomorphism. Thus f I I* "R",,""" R.).. This proves
Eq. 9 when m 2 3n + 1.
C.2.5 THE PROOF OF LEMMA
The proof of Lemma 3 L = Pg o Fi where F2 E F and F1 E Fu, and e > 0 be given, and let E Clearly, (k.((f.)) < Bx,w (F,,)) E) and so by the m, o, o MEP of go. with respect to Fu.m we have the existence of an Tm emb(f((), Eo:m) such that || - (((())((()))) < is compact, hence E Lipschitz on Ko, so we can apply Lemma f(K) o(o Kg = (Fo.m)- oro point 4,
BK.w E o E & | - r =((=)((())))) Lip(E B ((E oro f. (
(36)
But, because f E o we can choose a E E E so that Bx,w (FFa)(()))))oo)) oro, FPPO) S
Lip Lip(Fom)) Fo.m) which, combined with Eqn. 36 proves the result.
C.2.6
THE PROOF OF LEMMA
The proof of Lemma 4 Recall that F cmb(R", Rm)). Suppose that E.. does not have the m, n, o MEP with respect to F, then there are some > 0 and f E F so that
VF E E.. VW1 CC CR, BR.,, (S, F. 2
(37)
From Lemma point 2, have that
e BK, (f.E < B.. (f, Eg EP:0)
(38)
for all E E ET and for all compact sets W C R' that satisfy ( C W. We observe that W C R2 a compact set such that W" C W, we have
Bk,w (S, F2 FF.e)) < (,, E.
FT.0)
Thus, inequality Eq. 38 holds for all E. E ETo and for all compact sets W C RP. Summarising, we have seen that there are f E F and e > 0 such that for E E E and for all compact sets W c RP we have < Bx, E Ey."). Hence E does not have the m, n, MEP with respect to F,, and we have obtained a contradiction, which proves the result.
C.3 UNIVERSALITY
C.3.1 THE PROOF OF THEOREM I
The proof of Theorem
First we prove the claim under the assumptions (i).
First we prove the claim under assumption (i).
Let W C RR. be open relatively compact set. From Lemma 3
we have that
gn.m
(39)
19

---

Under review as a conference paper at ICLR 2022
has the m, n. MEP w.r.t. F= =====_11 of. Fi. Thus for any 61 0, we have an E gm.
s.t. BK. W..((s (F, E) E1.
From Lemma 7 point 5, have the existence of pl P(W) that Wz (F E#t1) C1-
By convolving n' with suitable mollifier é, can obtain measure μ p¹ Φ P(W) that is absolutely continuous with respect to the Lebesgue measure so that
W2 (1' 1 Lip(E)
61
Ambrosio al. 2008 Lemma 7.1.10.), and so W2 (Fat'' E++11") 61. Hence,
W2 (F F1 E+tl) < 2E1.
(40)
Next, from universality of TO" for any E2 O, we have the existence of To E To" so that W2 (4",, T) < 62. From Lemma 7 points 3 and 4 we have that
W2 #1 E To#m) 2el + +2 Lip((E).
(41)
For given > 0, choosing 61 < and 62 < 2(1+Lp((E)) yields that the map E = E To E & is such that W2 #1, Ex(1) < This yields the result.
Next prove the claim under the assumptions (ii). By our assumptions, in the weak topology of the space , )R";,, the closure of the set Th C C²(R",RR)) contains the space of Diff (TR", RP*)), ). Moreover, by our assumptions Ri--1 contains a linear map R. We observe that R is space of expansive elements, the map R is injective. and heene by Lemma T. the family
E En Th o R.1-1.93
has the MEP w.r.t F = (IR", (R",, By Lemma 2 we have that I (RR", RT)) coincides with the space emb' (R" ). Finally, by the assumption that Thue is dense in the space of C diffeomorphism Difr"(RR implies that To is LP-universal approximator for the set of C smooth triangular maps for all p < oc. Hence by Lemma in Appendix A of Teshima et al. (2020) To" is distributionally universal. From these the claim in the case (ii) follows in the same way as the case (i) using the family F emb (IR", R.
C.3.2 THE PROOF OF LEMMA 5
The proof of Lemma 5
The proof follows from taking the logical negation of the MEP for F. If the
MEP is not satisfied, then there is some f F so that Bx.w w (f. E) is never smaller than e > 0 for all E e E. Applying the definition of B,,w (f. E) from Eqn. yields the result.
C.3.3 THE PROOF OF COR.
The proof of Cor. 7 The proof of Eqn followws from the definition of the MEP.
The proof of Eqn. 13 follows from applying Lemma 7 point 4, and applying the same arguments
as the proof of Theorem so that lim L.p(E.] BR. (E, 10,++ o r o S, Et) - O, and so that
W2 (F, E; 11) & where 6; - 0 as i + co.. From the distributional universality of To. and continuity of E, o E, we have the existence
T, To" so that WN (F #/, E, o E¹ o Ti 26,. Choosing so that lim yields the result.
APPENDIX D ADDITIONAL PROPERTIES
D.1 LAYER-WISE PROJECTION
Here we provide the details of our closed-form layerwise projection algorithm The flow layers are injective, and are often implemented to be numerically easy to invert. Thus, the crux of the algorithm
20

---

Under review as a conference paper at ICLR 2022
comes from inverting the injective expansive layers, R. The range of the ReLU layer is piece- wise affine, hence the inversion follows a two-step program. First, identify which affine piece (described algebraically, onto which sign pattern) to project. Second, project to this point using standard least-squares solver.
The second step is always srraight-forware analyze, but the first is more complicated.
B - DDB
The key step in our algorithm is the fact that for the specific choice of weight matrix W given any E 2 we can always solve the least-squares inversion problem exactly. We prove this result in several parts given below.
1. For any R22", My W R"x" is full-rank.
2. If [b], * [y]sen for each I,....,,, then the argmin in Eqn. 17 is well defined, i.e. that there is unique minimizer. Otherwise there are 2 minimizers, where is the number of distinct i such that [b]: [u]
3. If M, = [A (nuxn Ay)] then
My (y -wr)ll + | sER"
min byy R(x) min
(42)
4. We verify Eqn.
17
The proof of Theorem
2
1. Using the definition of My, we have,
B
My
(I"Xn - B
- -, B.
(43)
-DB
But, (Inxa Ay D) is full-rank diagonal matrix (with entries either or (D],,),
B
and B is full rank by assumption, hence My
is too.
DB
2. Because B is square and full rank there exists basis 5 [b]
of
R" such that
f=1....
(b), {o
if i
(44)
For an x E R", let as = (x, bi) for I,..., n be the expansion of x in the by basis.
min [yy - 1[x) ZE3"
min 2
ly - R(x){
(45)
1=1
min ([v), max( (xx, b,) o))² + ((yk4n - max((x, [D], b.) 0))²
ZEER
(46)
We now consider minizing Eqn. by minimizing the basis expansion in terms os,
Σ min ([v), max(o;; 0))² (Iylet>- max((1()) on, 0))² ovER
(47)
Eqn. 47 is clearly minimized by minizing each term in the sum, hence search for minimizer of the i'th term
min (lv) max 0))² + (ly) - max(- [D] ass 0))²
(48)
0.E3
Namely the columns of the matrix B
21

---

Under review as a conference paper at ICLR 2022
Noting f f(a)) as the quantity inside the minimum of Eqn. negative and zero a, cases of Eqn. 488 separately and we get
48
consider the positive,
min f(as) = min (lul; -a,)² + Iylitn = [w]+4
(49)
a
a,ERt
min f(a;) min [u] (19litn + IDI ai) 2 [w]? o.eR
(50)
o.ERt
f(0) = [u] + [w]
(51)
If (yls > [B]] then the minimizer of Eqn. 48 a [D
Conversely if
Wlit < [w] then the minimzer of Eqn. 48 is [v], > 0. This argument applies all
= I,..., and hence if [u], * [v] for all i = I, then the minimizing x is unique.
W. and [y] for both [D],
If [yl: 1+l+1 then there are exactly two minimizers of f(a.). which f(as) = [ul = [wltt
3. If we suppose that [yl.4n lvl, > O, then [c(y),, = and [c(v)]<4n > 0, thus [Ayl = 1, hence if we let Fiin be the minimizing x from part 1, then
(ol, - max((Tminn .))² + (lv); - max( - [D] 6z), .0)
(52)
= 1wl? + (Ivlitn max max(((mmin - [D]i b.). .0))
(53)
/ 2 + [My (y Wxmin))?
(54)
If [ylt - [w] I then we have
(w), - max (XEmin b,), ,0)) + (lulitn - maxx(ammin: [D] bz). 00)2
(55)
([y), max(((min) 6.) 0)) + lyl
(56)
[M (y W Wxmin) )
Myy
(57)
Thus combining Eqn.s 45
46
54 and 57 for each i 1,...,7, n. we have that
min
yy
R(=)l1
min MM (y w ||M
(58)
ZER
zER
4. For the final point, combining all of the above points we have
min By R(x) min zE
My (yr - Wx)
(59)
EER
Further we have from Point that M, W is full rank, hence (M Myy = R (y) is minimizer of Eqn. 59 If [w], + [Ml+ for all = 1,..., n then Part 2 applies, and R (v) is the unique minimizer of [yy R(x) 12- In either case, we have that R$ (y) a minimizer.
D.2 BAYESIAN UNCERTAINTY QUANTIFICATION
We now discuss the process for making the network amenable to Bayesian Uncertainty Quantifica- tion (Bayesian UQ).
Assumption 2. Let yo E Rd be given, let y1 = Toyo and for each = 2...., L, then let = Re Re( and 31-1/22 == Te-1(8(-1). We assume that for f 1,... L 1, Te(y)), 11(2)-1/2)
and (y())) are differentiable.
22

---

Under review as a conference paper at ICLR 2022
Lemma 8. If network F of the form of Eqn. 7 upper bound on the tog-likelihood,
satisfies Assumption 2 then we have the following
1
RRe
dRe
Py (vo) S log Poggz((4 P (8o)) (0oo))+++ +
log det
(12-1/2) 01e-1112
(ye (96-1/2)
2
Qye-1122
1=1
θT, Öye
log
det
(we)
(60)
t=
Proof. The proof of Lemma follows from computing the log of,
(v0) pz (F-1 (g)o) det 0F
(61)
Oyo
F(R")
and then applying definition 1 and expanding term using the laws of logarithms we obtain.
logPy(U) S 1z (y)) + log det 2Re
(12-1/2) 0ye-1/2 1/2
(12-1/2)
091-1/2
aT: det
log
(ye)
(62)
Oye [
for ( = i,..., L, see (Kothari et al. 2021 Appendix B) for details.
We note here that in Equation 60 we have an inequality rather than an equality. The inequality comes from the expansive layers, the flow-layers are all endomorphisms, i.e. R Roc. We
now remark on the ease of approximating, or least bounding, T and R in Eqn. 62
Values for R when R. is (R1) (R2) straightforward to compute approximate When Rm.m is (R3), A E R are not differentiable, but are differentiable a.c.. Further, V (Tee can a.c. be computed by applying simple mask 0 and mask the weight matrices for an exact computation of R Additionally, from Hutchinson (189)) Kothari et (2021) have the following formula that approximates R
OR, T dR
20
T RRs aR. Oye
A
log det
Tr 1
d log B
Oye
Oy:
Oye
aRe T OR
-E
I
8
log B.
(63)
Oye
Oye
where 77 E R",, Computation of the [ term is often casier, comparatively. This is because these networks are often designed to make this value as easy compute as possible. For example the NICE Dinh et al. (2014), Real-NVP Dinh et al. (2016), and GLOW Kingma & Dhariwal (2018) architectures are all designed so that T can be computed form a short scalar product.
D.3 BLACK-BOX RECOVERY
We now discuss assumptions that enable black-box recovery of the weights of our entire network post-training.
For each e 1, 1,.... L, Re is affine RcLU layer. Each Te and To is constructed from a finite number of affine ReLU layers.
Assumption 3.
for example from LJ decomposition, see Golub 1996 Scction 3.2)
23

---

Under review as a conference paper at ICLR 2022
If a network F of the form of Eqn. D satisfies Assumption then given the range of the network, the range of the network can be recovered exactly.
Remark 3.
Further, if the linear region assumption from Rolnick & Körding 2020) is satisfied, then the exact weights are recovered, subject to two natural isometries discussed below.
Remark 4. The ReLU part of Assumption 3 is for all examples in Sec. 2.1 Further it is also
satisfied by both flows considered in Sec. 2.2 provided that the various 9i given by layers of affine ReLU's.
In Rolnick & Körding 2020), the authors show that, although ReLU networks depend on the value of their weight matrix in non-linear ways, it is still possible to recover the exact weights of given ReLU network in a black-box way, subject to natural isometrics. The authors show that this is possible not only in theory, but in numerical applications well.
The works of Rolnick& & Körding (2000); (ui Thi Mai & Lampert (2020) imply that provided the ac- tivation functions of the expressive elements are ReLU then the entire network can be recovered in black-box way. Further, provided that either the 'linear region assumption from Rolnick & Körding (2020) or the generality assumption from Bui Thi Mai & Lamperi (2020) is satisfied, then the entire network can be recovered uniquely modulo the natural isometries of rescaling and permutation of weight matrices.
First we describe the two natural isometries of scaling and permutation. Consider the following function
(xx = W20(Wiz)
(64)
where ø is coordinate- wise homogeneous degree 1 (such as ReLU) and W1 R" and W22 (2n2X*s, If we let P E R=axng Xn be any permutation matrix, and D+ be a diagonal matrix with strictly positive elements, then can write
f(x) W'P'' ('D,,))
(65)
as well. Thus ReLU networks can only ever be uniquely given subject to these two isometries. When describe unique recovery in the rest of this section, we mean modulo these two isometries.
In Rolnick Körding (2020), the authors describe how all parameters of a ReLU network can be recovered uniquely (called reverse engineered in Rolnick & Körding (202 ), subject to the called 'linear region assumption', LRA.
The input space IR" can be partitioned into a finite number of open {8.) where for each k, F(x) = Wsi + b, ie. the network corresponds to an affine polyhedron in the output space. The algorithms (Rolnick & Körding 2020 Alg.s 1 & 2) are roughly described below.
First, identify at least one point within each affine polyhedra (741)=2- Then identify the boundaries between polyhedra. The boundaries between sections are always one affine 'piece' of piecewise hyperplanes (HL 1 These (74 )" are the central objects which indicate the (de)activation of an element of a ReLU somewhere in the network. If the H. are full hyperplanes, then the ReLU that is (de)activates occurs in the first layer of the network. If H, is not a full hyperplane, then necessarily has bend where it intersects another hyperplane Hly Further, except for Lebesgue measure 0 set, when H, intersects Hy the latter does not have a bend. If this is the case, then Hy corresponds to ReLU (de)activation in an earlier layer than Hy. In this way the activation functions of every layer can be deduced. Once this is done, the normals of the hyperplanes can be used to infer the rew-vectors of the various weight matrices, letting one recover the entire network.
The above algorithm recovers all of the weights exactly provided that the LRA is satisfied. The LRA is satisfied for every distinct S, and Sy,, either W, * W. or b, * by. That is, different sign patterns produce different affine sections in the output space. This is natural assumption. as the algorithm as described above reconstruction works by first detecting the boundaries between adjacent affine polyhedra, which is only possible if the LRA holds.
Given the weights of a network there is currently no simple way to detect if the LRA is satisfied, to our knowledge. Nevertheless the authors of Rolnick & Körding (2020) show that if it is satisfied,
'The use of 'linear' in this context is somewhat non-standard, and instead means affine. In this section we use the term 'linear region assumption', but use 'affine' where where|Rolnick & Körding (2000 would use 'linear' to preserve mathematical meaning.
24

---

Under review as a conference paper at ICLR 2022
then unique recovery follows. Nevertheless recovery of the range of the entire network is possible, but this recovery may not unique.
In Bui Thi Mai & Lampert (2020) the authors also consider the problem of recovering weights of ReLU neural network, however the authors therein study the question when there exist isometries beyond the two natural ones described above. In particular the main result (Bui Thi Mai & Lampert 2020 Theorem 1) shows the following. Let _oo be ReLU network that is L layers deep and non-increasing. Suppose that E1, E2 E guo. Ei and E2 are genera X and for all Ei (1) = E2(r), then E1 is parametrically identical to E2 subject to the two natural isometries.
I
This work provides the stronger result, however does not apply the networks that consider out of the box. It does apply to our expressive elements (provided that they use ReLU activation functions, and non-increasing). but not necessarily apply to the network on the whole.
"A set it in topology is general if it's complement closed and nowhere dense.
25


Reviews:
[{"review_id": "k9HPLtf5P6A", "reviewer": "Reviewer_eR1p", "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": "# Post-rebuttal comments (11/29/2021)\n\nI am pleased by the authors that they considered my comments sincerely and revised the manuscript. The updated paper improved the readability. Still, I feel the organization of this paper would have room for improvement. Regarding Lemma 2, I think it improved the applicability of the main theorem.\n\n# Initial Review\n【Strength】\n- [1] A new measure MEP is proposed for evaluating how much a model can approximate distributions with support in low dimensional manifolds.\n- [2] This paper used the concept of MEP to derive the universality of many existing models in a unified manner.\n\n【Weakness】\n- [1] I have several questions about the correctness of the statements and proof of the theorems.\n- [2] Discussions related to topological obstructions might be hard to follow for those unfamiliar with the (differential) topology.\n\n【Correctness】\n- [1] I have several questions about the statements and proof of the theorems.\n  - Theorem 1, Cororally 1\n    - [1-1] If we read the statement literally, the statement trivially holds by setting $F_i = F$ for all $i$.\n    - [1-2] I think this theorem has two definitions of $\\mathcal{F}$: the class defined in Lemma 2 and the set of networks of the form Eqn.1 satisfying Point 1--3. Are two $\\mathcal{F}$'s different?\n    - [1-3] The output dimension of functions in $\\mathcal{T}_{\\ell}^{n_\\ell}$  looks inconsistent. On one hand, according to (1), $\\mathcal{T}_{\\ell}^{n_\\ell} \\subset C(\\mathbb{R}^{n_\\ell}, \\mathbb{R}^{n_{\\ell}})$ . On the other hand, according to Point 2, $\\mathcal{T}_{\\ell}^{n_\\ell}$ has the $n_{\\ell + 1}, n, n_\\ell$ MEP, which implies that $\\mathcal{T}_{\\ell}^{n_\\ell} \\subset \\mathrm{emb}(\\mathbb{R}^{n_\\ell}, \\mathbb{R}^{n_{\\ell+1}})$. \n    - [1-4] Similar inconsistency happens to $W$ in Cororally 1. The definition of $B_{K, W}(F, E_i)$ implies $W\\subset \\mathbb{R}^{o}$, while $\\mathcal{E}^{n, o} \\subset \\mathrm{emb}(W, \\mathbb{R}^o)$ implies $W\\subset \\mathbb{R}^{n}$.\n    - [1-5] P.17, Proof of Theorem 1: The proof picks $\\mu'$ such that $W_2(F_{\\#}\\mu, E_{\\#}\\mu') < \\epsilon_1 / 2$ . However, I think it is not possible in general. From Lemma 1 Point 5, we only know that $\\inf_{\\mu'} W_2(F_{\\#}\\mu, E_{\\#}\\mu') \\leq \\epsilon_1$. There is possibility that $\\inf_{\\mu'} W_2(F_{\\#}\\mu, E_{\\#}\\mu') > \\epsilon_1 / 2$.\n  - Lemma 2\n    - [1-6] P.15: According to Definition 3, $W$ must be the closure of an open set of $\\mathbb{R}^o$. Therefore, as long as $W$ is non-empty, there exists $w \\in W$ and a ball $B$ centered at $w$ such that $B \\subset W$. However, $W = K \\times \\{0\\}^{o-n}$ does not satisfy the condition when $K\\not = \\empty$  and $o > n$.\n  - Lemma 7\n    - [1-7] P.18, (62): What is the definition of $\\nu$?\n    - [1-8] P.19: I want to clarify what does Assumption 2 mean. Does it mean there exist calculation procedures for computing the quantities $\\log |\\det \\nabla R_\\ell (x_{n_\\ell})|$ and $\\log |\\det \\nabla T_\\ell (x_{n_{\\ell+1}})|$ ? Or does it assume the existence of these quentities (e.g., differentiability of $R_\\ell$ and $T_\\ell$ and $\\det \\nabla R_\\ell >0$) ?\n\n【Technical Novelty And Significance】\n- [1] This paper defined a new measure for measuring the ability of a model for approximating a distribution with support in a low-dimensional manifold. In this respect, the paper is novel. In addition, using this measure, this paper showed the distributional universality of several existing models. Therefore, I think this measure is useful, and introducing it is significant.\n\n【Empirical Novelty And Significance】\n- [1] This paper is does not have numerical experiements.\n\n【Detailed Comments】\n- [1] P.3: The family of functions $\\mathcal{R}_l^{n_{\\ell-1}, n_\\ell}$ from $\\mathbb{R}^{n_{\\ell-1}}\\to \\mathbb{R}^{n_{\\ell}}$. : I think this sentence is not a complete sentence and needs rewriting.\n- [2] P.3 (R2):  ... , and $W$ is a convlution kernel ... : $W$ → $w$\n- [3] P.4: We call a function $f$ an embedding and denote if by $f$ ... → denote it by $f$\n- [4] P.4, Definition 3: $\\|h\\|_{L^\\infty(X)} =\\mathrm{esssup}_{x\\in X} \\|h\\|_2$ → $\\|h\\|_{L^\\infty(X)} =\\mathrm{esssup}_{x\\in X} \\|h(x)\\|_2$\n- [5] P.4: When I read the paper for the first time, I could not understand why the inequality $\\inf_{\\mu_0 \\mathcal{P}(W)} W_2 (f_{\\#}\\mu_n , g_{\\#}\\mu _o) ≤ B_{K,W} (f, g)$ in P.4 is true. If I understand correctly, it is later shown as Lemma 1 Point 5. So, I would suggest referring to the Lemma when it first appears in P.4.\n- [6] P.5: I think it is better to write the definition of equivalent.\n- [7] P.5: This is because ... consider for example the exotic spheres from MIlnor (1956): I think those who are not familiar with differential topology may find it difficult to understand this sentence. It would be better to write that what the exotic sphere is (i.e., a topological space that is homomorhpic to but not diffeomorhic to the (hyper)shpere).\n- [8] P.4, Definition 3, P.6, Definition 4: In the definition of $B_{K, W}$, $W$ is assumed to be the closure of an open set. However, Definition 4 does not assume so. I am wondering why we need this assumption.\n- [9] P.7: This paper used both $\\subset$ and $\\subseteq$. Does $\\subset$ mean $\\varsubsetneq$? Or are they just notational inconsistency?\n- [10] P.7, Lemma 2: I guess the $\\sup$-universal approximator is the concept defined in Techima et al., (2020). So, we need the reference to it.\n- [11] P.7, Theorem 1: The definition of distributionally universal is not presented.\n- [12] P.8, Lemma 5: universalif → universal if (add a space)\n- [13] P.8, Lemma 5: there exists a $f\\in \\mathcal{F}$ → I think we do not need the indefinite article \"a\" here.\n- [14] P.8, (17): $E_i \\circ E_i' \\circ T_{i\\#}\\mu$ → $E_i \\circ E_i' \\circ T_{i\\#}\\mu'$.\n- [15] P.8: The crux of the problem is ... $\\mathcal{R}$ layers when $\\mathcal{R}$. → Remove the last \"when $\\mathcal{R}$\" \n- [16] P.8: a least squares solution → a least-squares solution\n- [17] P.9: For (R3) we have the following result ... : I have a question about this sentence. Since the definition of $R$ in Definition 6 and Theorem 2 is different from (R3), results here are not directly related to (R3).\n- [18] P.9: Write the $B$ and $D$ in Definition 6 (I guess it is the same as those in (R3)).\n- [19] P.13: The architecture described in Eqn. 22 ... which are not studied here.: I am afraid I could not understand this sentence, especialy the part after \"applies to ...\". Could you reconsider the sentence?\n- [20] P.20: The authors shows that this is possible ... → The authors show ...\n- [21] P.20: Further, provided that ... is satisfied, than the entire network can be ... → then", "summary_of_the_paper": "This paper studied the expressive power of models composed of invertible flows and injective embeddings. First, this paper defined the concept of the Embedding Gap as the measure by which a model can approximate an embedding with low-dimensional support. Then, this paper defined the concept of MEP as the ability to approximate the target embedding arbitrarily small in terms of the Embedding Gap. This paper showed that when invertible layers have the MEP properties and the first layer is a distributively universal approximator (and some additional assumptions), the model is a universal approximator in terms of 2-Wasserstein distance (Theorem 1). Finally, this paper gave a method to compute the inverse transformation of an injective layer with a special form of linear transformation and ReLU nonlinearity. (Theorem 2).", "summary_of_the_review": "I set the Correctness score to 2 as I have several questions about the correctness of the theoretical part of this paper (see【Correctness】Section). If these questions are solved, I will increase my Correctness score. Regarding technical novelty, I think this paper gave novel tools for analyzing the expressive power of flow models. Introducing these tools is significant as they encompass many existing models.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "a_kGTK8BcW", "reviewer": "Reviewer_4sjW", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "## Strengths\n\n* The paper makes good strides in the understanding of injective normalizing flows.\n\n## Weaknesses\n\n* The results feel weak. This is best exemplified by the class $\\mathcal{I}(X, Y)$, which is a very strong assumption to make on our target embedding. This class is **very** close to the core construction in Brehmer and Cranmer 2020, so a result showing universal approximation does not feel particularly illuminating. In particular, since members of $\\mathcal{I}(X, Y)$ are $\\Phi \\circ R$, where $R$ is affine and $\\Phi$ is a normalizing flow, do the results not follow simply by approximating both? This feels rather straightforward. Furthermore, while the paper claims that it has to account for just topological obstructions, this class of functions limits for more than just that. For example, a map from $\\mathbb{R}^n \\to B_0^n(1) \\subset \\mathbb{R}^m$ is correct topologically but it is not considered in the proofs. \n* The paper heavily invokes the universality and other properties of its constituent neural networks in the proofs. In particular, most of the proofs are simple applications of universality, follow directly from definitions, and/or rely on canonical tricks in the field (e.g. convolution with a mollifier). Along with the above observation, this lack of depth in the proof gives me the impression that not much real insight is being gained.\n* The paper, as written, is very confusing. This is important as these issues significantly hamper the accessibility of the paper. I would suggest that the authors make a thorough pass through the paper to clear up these issues. I included some of the major ones, but there are certainly others.\n    * There are many typos throughout, even in the abstract.\n    * There are very poor notational conventions. For example, in Theorem 1 the $\\mathcal{F}$ is overloaded.\n    * The paper could be better structured. For example, the purpose for the embedding gap and MEP are not made clear; in particular, they are introduced with almost no motivation. Explaining why one has to leverage these constructions would help readers make sense of why they are introduced this way. Other sections are introduced rather strangely (e.g. the topological obstruction section is motivated before the section and leads directly into the definition of MEP without pause).\n    * Most of the intermediate lemmas used to prove the theorem have little reason for being in the main paper. For example, Lemma 1 just proves basic properties of the definition and is unused except for in the appendix; it is not a main result and its purpose can not be understood unless one dives into the details of all proofs.\n    * I was also confused about the previous work section. In particular, it seems very strange to me that the discussion about the core architectures that the paper prove are universal were moved to the appendix, while general inverse problem applications were given several paragraphs.\n* The other results are very ancillary and oftentimes not explored/explained thoroughly. In particular, the last three results seem unrelated (and furthermore do not provide any more real insight). In particular, Section 3.4 (the results on layerwise projection) should be tested empirically. Appendix D.2 (on bayesian uncertainty quantification) is a straightforward application of standard log probability arguments. Finally, Appendix D.3 (the results on black box estimation) seems incomplete. There is no proof for Lemma 8, and I found the last paragraph, which is also one of the few that talks about the current work rather than Rolnick & Kording (2020), to be very confusing.\n\n## Small Stuff\n\n* The links to the lemmas are broken.", "summary_of_the_paper": "This paper analyzes some theoretical properties of injective normalizing flows. In particular, it focuses on universal approximation and (to a lesser extent), layer-specific projections, bayesian uncertainty quantification, and black-box recovery of network weights.", "summary_of_the_review": "While I believe the core idea and motivation are strong, I found the execution to be rather lackluster. In particular, I have questions about the core result (universality); in particular the function class they approximate seems very weak. I also found the presentation very confusing and hard to follow. Finally, the other experiments do not fit the overall narrative and are often underdeveloped.\n\nUPDATE\n----------\nLemma 2 alleviates my main concerns. I am greatly pleased by the author response.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TG3rcU6wTVA", "reviewer": "Reviewer_2dK9", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "The paper proposes the concept of an embedding measure reflecting the different topologies, then studies an approximation property of the flow models with distributions with low dimensional support under it. On the positive side, the paper is written in detail, with plenty of examples and discussion.\n\nOne question is that it seems to me that it could be written more clearly what kind of problem was being tackled. The motivation for wanting to deal with different topologies is explained, but it seems unclear to me what difficulties were solved as a result. For example, what conclusions can be drawn compared to simply using the Wasserstein distance? Is it possible to construct a mathematical statement whose universal approximability is compromised when existing measures or topology are used? Moreover, it is possible to show that the topology and measure developed in this paper are convincing phenomena, which can be validated by experiments with real data?", "summary_of_the_paper": "In this paper, the authors studies flow models by a newly developed approximation measure when the data is on a low-dimensional manifold. Specifically, they consider an architecture that alternates a bijective function with the same input and output dimensions, and a function with a larger dimension at the output. There are several successful methods for this, but the globally invertible flow is not well understood. To address this problem, this work shows the approximate properties of the flow architecture. Specifically, they show the approximation accuracy of the models with distributions that have a certain manifold as their support. In doing so, they proposed a new notion of embedding gap to evaluate the manifold embedding. This may allow them to represent cases that cannot be represented by existing topologies. In addition, they defined a value of MEP, which allows us to evaluate the approximation capability under different topologies. This establishes the validity of evaluating the performance for each layer.", "summary_of_the_review": "Well written. But the contribution could be clearer.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Mz4AyfO4J_d", "reviewer": "Reviewer_WKWr", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is theoretical and mathematically fruitful. The embedding property discussed here is an important geometric property and should be useful in understanding the structure of neural networks. The write-up is a little bit too abstract and mathematical. It would be great if the authors can use a more understandable way to present their results in order that the work can reach a larger audience. ", "summary_of_the_paper": "This paper analyzes neural networks composed of bijective flows and injective expansive elements and showed that they are universal approximators of a large class of manifolds. A new mathematical notion called the embedding gap is proposed, which measures how far one continuous manifold is from embedding another. ", "summary_of_the_review": "(1) Good work. Mathematically profound and results may have potential applications;\n(2) Presentation too mathematical and might reach a larger audience if it can be revised to be more understandable.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

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

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

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

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

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

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

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