Year: 2021

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 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 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.

heading: 1 INTRODUCTION
text: In the past several years, invertible flow networks emerged as powerful deep learning models to learn maps between distributions (Durkan et al., 2019a; Grathwohl et al., 2018; Huang et al., 2018; Jaini et al., 2019; Kingma et al., 2016; Kingma & Dhariwal, 2018; Kobyzev et al., 2020; Kruse et al., 2019; Papamakarios et al., 2019). 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 a 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-theoretic properties of injective flows whose architecture combines bijective flows and expansive, injective layers, with an emphasis on approximating measures 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.

heading: 1.1 PRIOR WORK
text: The idea to combine invertible (coupling) layers with expansive layers has been explored by Brehmer & Cranmer (2020) and Kothari et al. (2021). Brehmer & Cranmer (2020) combine two flow networks with a simple expansive element (in the sense made precise in Section 2.1) and obtain 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 results. We discuss in detail the connection between these two empirical works and the approximation results derived here in Appendix B.1.
Kothari et al. (2021) propose expansive coupling layers and build networks similar to that of Brehmer & Cranmer (2020) but with an arbitrary number of expressive and expansive elements. They observe that the resulting network trains much faster with a smaller memory footprint, while producing high-quality samples on a variety of benchmark datasets.
While to the best of our knowledge, there are no approximation-theoretic 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 are 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 et 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 Arridge et al. (2019). Bora et al. (2017) 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 models gives an algorithmic projection1 on the range, which facilitates implementation of reconstruction algorithms. An alternative approach is Bayesian, where flows are used to obtain tractable variational approximations of posterior distributions over parameters of interest, via supervised training on labeled input-output data pairs. Ardizzone et al. (2018) encode the dimension-reducing forward process by an 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 generative model. They train a normalizing flow which produces samples from the posterior, with the prior and the noise model given implicitly by the regularized misfit functional. In Kothari et al. (2021) this procedure is adapted to priors specified by injective flows which yields significant improvements in computational efficiency.

heading: 1.2 OUR CONTRIBUTION
text: We derive new approximation results for neural networks composed of bijective flows and injective 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 et al. (2020) and develop a new theoretical device which we refer to as the embedding gap. This gap is a measure of how nearly a mapping from Ro → Rm embeds an n-dimensional manifold in Rm, where n ≤ o. We find a natural relationship between the embedding gap and the problem of approximating probability measures with low-dimensional support.
We then relate the embedding gap to a relaxation of universality we call manifold embedding property. We show that this property captures the essential geometric aspects of universality and uncover important topological restrictions on the approximation power of these networks, to our knowledge, heretofore unknown in the literature. We give an example of an absolutely continuous measure µ and embedding f : R2 → R3 such that f#µ can not be approximated with combinations of flow layers and linear expansive layers. This may be surprising since it was previously thought that networks such as those of Brehmer & Cranmer (2020) can approximate any “nice” density supported on a “nice” manifold. We establish universality for manifolds with suitable topology, described in terms of extendable embeddings. Our proof shows that optimality of the approximating network can be established in reverse: optimality of a given layer can be established without optimality of preceding layers. This settles a (generalization of a) conjecture posed for a two-layer case in (Brehmer & Cranmer, 2020). Finally, we show that these universal architectures are also practical and admit exact layer-wise projections, as well as other properties discussed in Section 3.4.

heading: 2 DESCRIPTION OF THE ARCHITECTURE
text: Let C(X,Y ) denote the space of continuous functions X → Y . We study networks in F ⊂ C(X,Y ) that are of the form:
F = T nLL ◦ R nL−1,nL L ◦ · · · ◦ T n11 ◦ Rn0,n11 ◦ T n00 (1)
1Idempotent but in general not orthogonal.
whereRn`−1,n`` ⊂ C(Rn`−1 ,Rn`), T n`` ⊂ C(Rn` ,Rn`), L ∈ N is the number of networks, n0 = n, nL = m, and n` ≥ n`−1 for ` = 1, . . . , L. We introduce a well-tuned shorthand notation and write H ◦ G := {h ◦ g : h ∈ H, g ∈ G} throughout the paper. We identify R with the expansive layers and T with the bijective flows. Loosely speaking, the purpose of the expansive layers is to allow the network to parameterize high-dimensional functions by low-dimensional coordinates in an injective way. The flow networks give the network the expressivity necessary for universal approximation of manifold-supported distributions.

heading: 2.1 EXPANSIVE LAYERS
text: The expansive elements transform an n-dimensional manifoldM embedded in Rn`−1 , and embed it in a higher dimensional space Rn` . 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 Rn`−1,n`` be a family of functions from Rn`−1 → Rn` . Rn`−1,n`` is a family of expansive elements if every R ∈ R n`−1,n` ` is injective and Lipschitz.
Examples of expansive elements include
(R1) Zero padding: R(x) = [ xT ,0(m−n) ]T where 0(m−n) is the zero vector (Brehmer & Cran-
mer, 2020).
(R2) Multiplication by an arbitrary full-rank matrix, or one-by-one convolution:
R(x) = Wx, or R(x) = w ? x (2)
where W ∈ Rm×n and rank(W ) = n (Cunningham et al., 2020), and w is a convolution kernel ? denotes convolution Kingma & Dhariwal (2018).
(R3) Injective ReLU layers: R = ReLU(Wx), W = [ BT ,−DBT ,MT ]T , R(x) =
ReLU ([ wT ,−wT ] ? x )
for matrix B ∈ GLn(R), positive diagonal matrix D ∈ Rn×n, and arbitrary matrix M ∈ R(m−2n)×n (Puthawala et al., 2020).
(R4) Injective ReLU networks (Puthawala et al., 2020, Theorem 15). These are functions R : Rn → Rm of the formR(x) = WL+1 ReLU(. . .ReLU(W1x+b1) . . . )+bL whereW` are n`+1 × n` matrices and b` are the bias vectors in Rn`+1 . The weight matrices WL satisfy the Directed Spanning Set (DSS) condition for ` ≤ L (that make all layers injective) and WL+1 is a generic matrix which makes the mapR : Rn → Rm injective. Note that the DSS condition requires that n` ≥ 2n`−1 + 1 for ` ≤ L and we have n1 = n and nL+1 = m.

heading: 2.2 BIJECTIVE FLOW NETWORKS
text: 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, . . . , L be given and let T n`` ⊂ C(Rn` ,Rn`). T n`` is a family of bijective flow networks if every T ∈ T n`` is Lipschitz continuous and bijective.
Examples of bijective flow networks include
(T1) Coupling flows, introduced by Dinh et al. (2014) consider R(x) = Hk ◦ · · · ◦H1(x) where
Hi(x) =
[ hi ( [x]1:d , gi ( [x]d+1:n )) [x]d+1:n ] . (3)
In Eqn. 3, hi : Rd × Re → Rd is invertible w.r.t. the first argument given the second, and gi : Rn−d → Re is arbitrary. Typically in practice the operation in Eqn. 3 is combined with additional invertible operations such as permutations, masking or convolutions Dinh et al. (2014; 2016); Kingma & Dhariwal (2018).
(T2) Autoregressive flows, introduced by Kingma et al. (2016) are generalizations of triangular flows A : Rn → Rn where for i = 1, . . . , n the i’th value of A is given by of the form
[A]i (x) = hi ( [x]i , gi ( [x]1:i−1 )) (4)
In Eqn. 4, hi : R × Rm → R where again hi is invertible w.r.t. the first argument given the second, and gi : Ri−1 → Rm is arbitrary except for g1 = 0. In Huang et al. (2018), the authors choose hi(x,y), where y ∈ Rm, to be a multi-layer perceptron (MLP) of the form
hi(x,y) = φ ◦Wp,y ◦ · · · ◦ φ ◦W1,y(x) (5) where φ is a sigmoidal increasing non-linear activation function.

heading: 3 MAIN RESULTS

heading: 3.1 EMBEDDING GAP
text: We call a function f an embedding and denote it by f ∈ emb(X,Y ) if f : X → Y is continuous, injective, and f−1 : f(X)→ X is continuous2. Also we denote embk(Rn,Rm) = emb(Rn,Rm)∩ Ck(Rn,Rm). In order to set up our result concerning embedding of manifolds, we first need a way to measure the degree to which a mapping g ∈ emb(Ro,Rm) nearly embeds a manifoldM = f(K) for compact K ⊂ Rn and f ∈ emb(K,Rm). With this in mind we introduce embedding gap BK,W (f, g), a 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 be the approximator.
Definition 3 (Embedding Gap). Let K ⊂ Rn be compact and non-empty, W ⊂ Ro contain the closure of set U which is open in the subspace topology of some vector subspace V of dimension p, where n ≤ p ≤ o ≤ m, f ∈ emb(K,Rm), and g ∈ emb(W,Rm). Then we define the Embedding Gap between f and g on sets K and W as
BK,W (f, g) = inf r∈emb(f(K),g(W ))
‖I − r‖L∞(f(K)) (6)
where I : f(K)→ f(K) is the identity function and ‖h‖L∞(X) = ess supx∈X ‖h(x)‖2 for h : X → Y . We refer to the embedding gap between f and g without specifying K and W when it is clear from context.
Remark 1. As W ⊂ Ro contains U , an open set in V , there is an affine map A : Rn → V such that A(K) ⊂W . Then, the map r0 = g ◦A ◦ f−1 : f(K)→ g(W ) is an injective continuous map from a compact set to its range and hence r0 ∈ emb(f(K), g(W )) . Thus, in the above infimum the set emb(f(K), g(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 functions is small, then g is nearly an embedding of the range of f into Ro. BK,W (f, g) is constructed expressly to serve as an upper bound
inf µo∈P(W )
W2 (f#µn, g#µo) ≤ BK,W (f, g)
where µn ∈ P(K) is given, and W2 (ν1, ν2) denotes the Wasserstein-2 distance with `2 ground metric (Villani, 2008), as shown in Lemma 7 part 5. The above result has a 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 low-dimensional support, by applying g to samples from a base distribution µo. Suppose further that ν is a pushforward of some (known or unknown) distribution µn via f . The embedding gap BK,W (f, g) then upper bounds the 2-Wasserstein distance between ν and g#µ0 for the best possible choice of µo.3
2Note that if X is a compact set, then continuity of the of f−1 : f(X) → X is automatic, and need not be assumed (Sutherland, 2009, Cor. 13.27). Moreover, if f : Rn → Rm is a continuous injective map that satisfies |f(x)| → ∞ as |x| → ∞, then by (Mukherjee, 2015, Cor. 2.1.23) the map f−1 : f(Rn) → Rn is continuous.
3The choice of p-Wasserstein distance is suitable for measures with mismatched low-dimensional support; this has been widely exploited in training generative models (Arjovsky et al., 2017).
The embedding r can be interpreted as a candidate transport map from any measure pushed forward by f , that can be pulled back through g. Loosely speaking, for µ′o = g
−1 ◦ r ◦ f#µn, r is a valid Wasserstein transport map that transports f#µn to g#µ′o with cost no more than ‖I − r‖L∞(f(K)). See Fig. 1 for a visualization of the embedding gap between two toy functions. Further, the embedding gap satisfies inequalities useful for studying networks of the form of Eqn. 1, see Lemma 7.

heading: 3.2 MANIFOLD EMBEDDING PROPERTY
text: We now introduce a central concept, the manifold embedding property (MEP). A family of networks satisfies the MEP if it nearly embeds a large class of manifolds of certain dimension and regularity, as measured by the embedding gap. The MEP is a property of a family of functions Eo,m ⊂ emb(W,Rm) where W ⊂ Ro. For this manuscript, Eo,m will always be formed by taking Eo,m := T m ◦ Ro,m. We note here that the MEP is closely related to the question of whether or not a given n-dimensional manifoldM that is an image of an embedding f : K → Rm, that is,M = f(K), K ⊂ Rn, can be approximated by the images of neural networks E : K → Rm of a given type. In particular, we will consider neural networks that are compositions where R : Ro → Rm are ‘simple’ non-universal functions, and flow-maps T : Rm → Rm that are diffeomorphism. This choice of applying nonuniversal expansive layers, and then diffromorphisms has some topological consequences, which we discuss below.

heading: TOPOLOGICAL OBSTRUCTIONS TO MANIFOLD LEARNING WITH NEURAL NETWORKS
text: We find that using non-universal expansive layers, followed by layers imposes some topological conditions on what can be approximated. We illustrate this with the following problem. When n = 2, m = 3, and K = S1 ⊂ R2 is the circle. We consider maps E = T ◦ R : Rn → Rm where R : Rn → Rm is, e.g., a linear map of rank n, and T : Rm → Rm is a coupling flow which is a homeomorphism. Let f ∈ emb(K,R3) be an embedding that mapsK to a trefoil knotM = f(S1), see Fig. 2. Such a function f can not be written as a restriction T ◦ R on S1. In Sec. C.2.2 we prove this fact and build a related example where a measure, µ ∈ P(R2), supported on an annulus is pushed forward to a measure supported on a knotted ribbon in R3 by an embedding g : R2 → R3. For this measure, there are no E := T ◦ R, with linear injective R and embedding T , such that g#µ = E#µ.
To sidestep this fundamental difficulty, we define the MEP property for a certain subclass of manifolds {f(K) : f ∈ F}. Finally, when considering flow networks which are universal approximators of C2 diffeomorphisms, we restrict the class of manifolds to be approximated even further. This is because manifolds that are homeomorphic are not necessarily diffeomorphic; for example exotic spheres. These are topological structures that are homeomorphic, but not diffeomorphic, to the sphere Milnor (1956). Moreover, it is known that general homeomorphisms F : Rm → Rm can
↑
1
Figure 2: An illustration of the case when n = 2, m = 3, and K = S1 is the circle. Here f : S1 → R3 is an embedding such that the curveM = f(S1) is a trefoil knot. Due to knot theoretical reasons, there are no map E = T ◦ R : R2 → R3 such that E(S1) = M, where R : R2 → R3 is a full rank linear map and T : R3 → R3 is 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(Rn,Rm) of extendable embeddings f . A similar 2-dimensional example can be obtained to a knotted ribbon, see Sec. C.2.2.
not be approximated in C0-topology by C2-smooth diffeomorphisms T : Rm → Rm. See Müller (2014) for a precise statement. However, all C1-smooth diffeomorphims F : Rm → Rm can be approximated in the strong topology of C1 by C2-smooth diffeomorphims F̃ : Rm → Rm, ` ≥ k, see Hirsch (2012), Ch. 2, Theorem 2.7. Because of this, we have to pay attention to the smoothness of the maps in the subset F ⊂ emb(K,Rm). For these reasons, when we refer to the MEP, we consider it with respect to a class of functions F ⊂ emb(Rn,Rm). The MEP can be interpreted as a density statement, saying that our networks Eo,m are dense in the ‘BK,W distance’ in the set F ⊂ emb(Rn,Rm). Two examples we are particularly interested in are the following. First, when F = Φ ◦A where A : Rn → Rm are linear maps of rank n and Φ : Rm → Rm are Ck diffeomorphisms with k ≥ 1. Second, when F ∈ emb(Rn,Rm). Definition 4. Let Eo,m ⊂ emb(Ro,Rm) and Fn,m ⊂ emb(Rn,Rm) be two families of functions. We say that Eo,m has the m,n, o Manifold Embedding Property (MEP) w.r.t. Fn,m if for every compact non-empty set K ⊂ Rn, f ∈ Fn,m, and > 0, there is an E ∈ Eo,m and a compact set W ⊂ Ro such that the restriction of f in K and the restriction of E in W satisfy
BK,W (f,E) < . (7)
When it is clear from the context, we abbreviate the m,n, o MEP w.r.t. Fn,m simply by the m,n, o MEP, or simply the MEP.
We also note here that if a model from Ro → Rm is a uniform universal approximator of Fo,m = C0(Rn,Rm) on compact sets, such as those considered in Yarotsky (2017; 2018), then it has the m,n, o MEP w.r.t Fn,mfor any n ≤ o. Thus, networks that are uniform universal approximators automatically possess the MEP, as shown in Lemma 1. However, we have a result that applies to network which are uniform universal approximators. Definition 5 (Uniform Universal Approximator). For a non-empty subset Fn,m ⊂ C(Rn,Rm), a family En,m ⊂ C(Rn,Rm) is said to be a uniform universal approximator of Fn,m if for every f ∈ Fn,m, every non-empty compact K ⊂ Rn, and each > 0, there is an E ∈ En,m satisfying:
sup x∈K ‖f(x)− E(x)‖2 < . (8)
We also have the following function class, which is key to our analysis. Definition 6 (Extendable Embeddings). Let I(Rn,Rm) be the set of functions F : Rn → Rm that are compositions F = Φ ◦ R where R : Rn → Rm is a linear map of rank n and Φ : Rm → Rm is a C1-smooth diffeomorphism. We call I(Rn,Rm) be the set of extendable embeddings. We also denote Ik(Rn,Rm) = I(Rn,Rm) ∩ Ck(Rn,Rm). We observe that I(Rn,Rm) ⊂ emb(Rn,Rm). Lemma 1. (i) IfRo,m is a universal approximator of C(Rn,Rm) and I ∈ T m where I is the
identity map, then Eo,m := T m ◦ Ro,m has the MEP w.r.t. emb(Rn,Rm). (ii) IfRo,m is such that there is an injective R ∈ Ro,m and open set U ⊂ Ro such that R ∣∣ U
is linear, and T m is a sup universal approximator in the space of Diff2(Rm,Rm), in the sense of Teshima et al. (2020), of the C2-smooth diffeomorphisms, then Eo,m := T m ◦Ro,m has the MEP w.r.t. F = I(Rn,Rm).
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 E := T m ◦ Ro,m, then
(i) If T m is either (T1) or (T2) and Ro,m is (R4), then Eo,m has the m,n, o MEP w.r.t. emb(Rn,Rm).
(ii) If T m is (T2) with sigmoidal activations Huang et al. (2018), then if Ro,m is any of (R1), ..., (R4), then Eo,m has the m,n, o MEP w.r.t. I(Rn,Rm).
The proof of Example 1 is in Appendix C.2.3.
We add a remark here showing that if m is sufficiently larger than n, and subject to some regularity assumptions, The two classes considered in Example 1 coincide.
Lemma 2. When m ≥ 3n+ 1 and k ≥ 1, for any Ck embedding f ∈ embk(Rn,Rm) and compact set K ⊂ Rn, there is a map in the closures of the flow type neural network E ∈ Ik(Rn,Rm) such that E(K) = f(K). Moreover,
Ik(K,Rm) = embk(K,Rm) (9)
This means that the topological structure of a manifold to approximateM in Rm is diffeomorphic to the set K ⊂ Rn, and thus some flow type network can approximateM. The proof of Lemma 2 in Appendix C.2.4.
We finally have two more lemmas to present before moving on to our discussion of universality as it ties to the MEP. Lemma 3. Let Fn,o ⊂ emb(Rn,Ro) and Fo,m ⊂ emb(R0,Rm) Ep,o1 ⊂ emb(Rp,Ro) have the o, n, p MEP w.r.t. Fn,o ⊂ emb(Rn,Ro) and Eo,m2 ⊂ emb(Ro,Rm) have the m, o, o MEP w.r.t. Fo,m ⊂ emb(Ro,Rm). If each Eo,m2 ∈ Eo,m2 is locally Lipschitz, then Eo,m2 ◦ Ep,o1 has the m,n, p MEP w.r.t. Fo,m ◦ Fn,o.
The proof of Lemma 3 is in Appendix C.2.5.
We note that when the elements of Eo,m2 are differentiable, local Lipschitzness is automatic, and need not be assumed, see e.g. (Tao, 2009, Ex. 10.2.6). We also record a near-converse (proved in C.2.6) of Lemma 3 that shows that if Eo,m2 ◦ Ep,o1 has the m,n, p MEP, then Eo,m2 has the m,n, o MEP. Lemma 4. Let F ⊂ emb(Rn,Rm). Let Ep,o1 ⊂ emb(Rp,Ro) and Eo,m2 ⊂ emb(Ro,Rm) be such that Eo,m2 ◦Ep,o1 has the m,n, p MEP with respect to family F . Then Eo,m2 has the m,n, o MEP with respect to family F .

heading: 3.3 UNIVERSALITY
text: We now present our universal approximation result for networks given in Eqn. Eq. 1 and a decoupling property. Theorem 1 (Qualitative Universality for Embeddings). Let n0 = n, nL = m, µ ∈ P(K) be an absolutely continuous measure w.r.t. Lebesgue measure. Further let, for each ` = 1, . . . , L, En`−1,n`` := T n`` ◦R n`−1,n` ` whereR n`−1,n` ` is a family of injective expansive elements that contains a linear map, and T n`` is a family of bijective family networks. Finally let T n0 be distributionally universal, i.e. for any absolutely continuous µ ∈ P(Rn) and ν ∈ P(Rn), there is a {Ti}∞i=1 such that Ti#µ→ ν in distribution. Suppose that one of the following two cases hold: (i) Let F ∈ FnL−1,mL ◦ · · · ◦Fn,n11 and E n`−1,n` ` have the the n`, n, n`−1 MEP for ` = 1, . . . , L with respect to Fn`−1,n`` . (ii) Let F ∈ emb1(Rn,Rm) be a C1-smooth embedding, and assume that for ` = 1, . . . , L it holds that n` ≥ 3n`−1 + 1 and the families T n`` are dense in the space of C2-diffeomorphism Diff2(Rn`). Then, there is a sequence of {Ei}i=1,...,∞ ⊂ E nL−1,m L ◦ · · · ◦ En1,n1 ◦ T n0 such that
lim i→∞ W2 (F#µ,Ei#µ) = 0. (10)
The proof of Theorem 1 is in Appendix C.3.1. As discussed in above and in Figure 2, there are topological obstructions for Theorem 1 with a general embedding F : Rn → Rm. When n = 2,
m = 3, L = 1, and µ is the uniform measure on an annulus K ⊂ R2 target measure F#µ is the uniform measure on a knotted ribbon M = F (K) ⊂ R3. There are no injective linear maps R : R2 → R3 and diffeomorphisms T : R3 → R3 such that E = T ◦ R would satisfyM = E(K) and E#µ = F#µ. This happen even though the set of diffeomorphism T : R3 → R3 are universal distributional approximators. In this case the condition m = n1 ≥ 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 are 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 En,m = Ho,m ◦Gn,o, thenHo,m must have the m,n, o MEP if En,m is universal. Lemma 5. Suppose that En,m = Ho,m ◦ Gn,o where En,m ⊂ emb(Rn,Rm), Ho,m ⊂ emb(Ro,Rm), and Gn,o ⊂ emb(Rn,Ro). If Ho,m does not have the m,n, o MEP w.r.t. F , then there exists a f ∈ F , compact K ⊂ Rn and > 0 such that for all E ∈ En,m, and r ∈ emb(f(K), E(W ))
‖I − r‖L∞(K) ≥ . (11)
The proof of Theorem 1 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 is end-to-end optimal.
Corollary 1. Let Fn,o ⊂ emb(Rn,Ro),Fo,m ⊂ emb(Ro,Rm), and let Eo,m ⊂ emb(Ro,Rm) have the m,n, o MEP w.r.t. Fo,m ◦ Fn,o. For every F ∈ Fo,m ◦ Fn,o then there is a compact K ⊂ Rn and {Ei}∞i=1 ⊂ Eo,m such that
lim i→∞ BK,W (F,Ei) = 0. (12)
Further, if En,o ⊂ emb(W ′,Ro) has the o, n, n MEP w.r.t. Fn,o, and T n is a universal approximator for distributions, then for any µ ∈ P(K) where K ⊂ Rn is compact, there is a sequence {E′i}i=1,...,∞ ⊂ En,o and {Ti}i=1,...,∞ ⊂ T n so that
lim i→∞
W2 (F#µ,Ei ◦ E′i ◦ Ti#µ) = 0. (13)
The proof of Corollary 1 is in Appendix C.3.3. Approximation results for neural networks are typically given in terms of the network end-to-end. Corollary 1 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 & Cranmer, 2020, Section B) about training strategies, where the authors remark that they ‘expect faster and more robust training of a network’ of the form in Eqn. 1 when L = 1, that is F = T m1 ◦Rn,m1 ◦T n0 . Corollary 1 shows that there exists a minimizing sequence in T m1 that need only minimize Eqn. 12; the T n0 layers can be minimized after. We can further combine Lemma 5 and Cor. 1 to prove that not only can the network from Brehmer & Cranmer (2020) be trained layerwise, but that any universal network can necessarily be trained layerwise in reverse order, provided that it can be written as a composition of two smaller layers.

heading: 3.4 LAYER-WISE INVERSION, UNCERTAINTY QUANTIFICATION AND RECOVERY OF WEIGHTS
text: In this subsection, we describe how our network can be augmented with more useful properties if the architecture satisfies a few more assumptions without affecting universal approximation. We focus on a new layerwise projection result, with a further discussion of Bayesian uncertainty quantification, and black-box recovery of our network’s weights in Appendices D.2 & D.3.
Given a point y ∈ Rm that does not lie in the range of the network, projecting y onto the range of the network is a practical problem without an obvious answer. The crux of the problem is inverting the injective (but non-invertible)R layers whenR. WhenR contains only full-rank matrices as in (R1) or (R2) then we can compute a least-squares solution. If, however,R contains layers which are only piecewise linear, as in (R3), then the problem of computing a least squares solution is more difficult, see Fig. 3. Nevertheless, we find that ifR is (R3) we can still compute a least-squares solution.
Figure 3: A schematic showing that, for a toy problem, the least-squares projection to a piecewise affine range can be discontinuous. Left: A partitioning of R2 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, y2 and y3 are each projected to the closest three points on R(R) yielding ỹ1, ỹ2 and ỹ3. Note that the projection operation is continuous within each section, but discontinuous across gray boundaries between section.
Assumption 1. LetR be given by one of (R1) or (R2), or 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 = In×n and M is an empty matrix.
Definition 7. Let W = [ Bt −DBt ]t ∈ R2n×n and y ∈ R2n be given, and let R(x) = ReLU(Wx). Then define
c(y) ∈ R2n c(y) := max ([
In×n −In×n −In×n In×n
] y, 0 ) (14)
∆y ∈ Rn×n [∆y]i,i := {
0 if [c(y)]i+n = 0 1 if [c(y)]i+n > 0 [∆y]ij = 0 if i 6= j (15)
My ∈ Rn×2n My := [ (In×n −∆y) ∆y ] (16)
where the max in Eqn. 14 is taken element-wise.
Theorem 2. Let y ∈ R2n. If for i = 1, . . . , n, [y]i 6= [y]i+n then
R†(y) := (MyW ) −1 Myy = argmin x∈Rn ‖y −R(x)‖2 . (17)
Further, if there is a i ∈ {1, . . . , n} such that [y]i = [y]i+n, then there are multiple minimizers of ‖y −R(x)‖2, one of which is R†(y).
The proof of Theorem 2 is given in Appendix D.1. Remark 2. We note that Theorem 2 is different from many of the existing work on inverting expansive layers, e.g. Aberdam et al. (2020); Bora et al. (2017); Lei et al. (2019), our result gives a direct inversion algorithm that is provably the least-squares minimizer. Further, if each expansive layer is any combination of (R1), (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.

heading: 4 CONCLUSION
text: Bijective flow networks are a powerful tool for learning a push-forward mappings in a 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 introducing 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, we can also use specific expansive layers with a new layerwise projection result. Moreover, we show that the studied networks provide Bayesian uncertainty quantification and allow black-box recovery of their weights.

heading: APPENDIX A SUMMARY OF NOTATION
text: Throughout the paper we make heavy use of the following notation.
1. Unless otherwise stated, X and Y always refer to subsets of Euclidean space, and K and W always refer to compact subsets of Euclidian space.
2. f ∈ C(X,Y ) means that f : X → Y is continuous. 3. For families of functions F and G where each F 3 f : X → Y and G 3 g : Y → Z, then
we define G ◦ F = {g ◦ f : X → Z : f ∈ F , g ∈ G}. 4. f ∈ emb(X,Y ) means that f ∈ C(X,Y ) is continuous and injective on the range of f ,
i.e. an embedding, and furthermore that f−1 : f(X)→ X is continuous. 5. µ ∈ P(X) means that µ is a probability measure over X . 6. W2 (µ, ν) for µ, ν ∈ P(X) refers to the Wasserstein-2 distance, always with `2 ground
metric.
7. ‖·‖Lp(X) refers to the Lp norm of functions, from X to R. 8. For vector-valued f : X → Y , ‖f‖L∞(X) = ess supx∈X ‖f‖2. Note that Y is always finite
dimensional, and so all discrete 1 ≤ q ≤ ∞ norms are equivalent. 9. Lip(g) refers to the Lipschitz constant of f .
10. For x ∈ Rn, [x]i ∈ R is the i’th component of x. Similarly, for matrix A ∈ Rm×n, [A]ij refers to the j’th element in the i’th column.

heading: APPENDIX B DETAILED COMPARISON TO PRIOR WORK

heading: B.1 CONNECTION TO BREHMER & CRANMER (2020)
text: In Brehmer & Cranmer (2020), the authors introduce manifold-learning flows as an invertible method for learning probability density supported on a low-dimensional manifold. Their model can be written as
F = T m1 ◦ Rn,m ◦ T n0 (18)
where T m1 ⊂ C(Rm,Rm), T m0 ⊂ C(Rn,Rn), and R = {[ In×n
0(m−n)×n
]} is a zero-padding (R1).
They invert F ∈ F in two different ways. For manifold-learning flows (M-flows) they restrict T m1 to be an invertible flow, and for manifold-learning flows with separate encoder (Me-flows) they place no such restrictions on T m1 and instead train a separate neural network e to invert elements of T m1 . Our results apply out-of-the-box to the architectures used in Experiment A of Brehmer & Cranmer (2020). The architecture described in Eqn. 18 is of the form of Eqn. 1 where L = 1. Further, although they are not studied here, our analysis can also be applied to quadratic flows.
The network used in (Brehmer & Cranmer, 2020, Experiment 4.A) uses coupling networks, (T1), where T m1 and T n0 are both 5 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 T m1 and T n0 . In Experiment 4.B they let T1 and T0 again be 5 layers deep, and in 4.C they again let T1 by 20 layers deep and T0 15 layers. For the final experiment, 4.D, the choose more complicated expressive elements that combine Glow Kingma & Dhariwal (2018) and Real NVP Dinh et al. (2016) architectures. These elements include the actnorm, 1 × 1 convolutions and rational-quadratic coupling transformations along with a multi-scale transformation.
The authors mention universality of their network without our proof, but our universality results in Theorem 1 apply to their networks from Experiment A wholesale. Further in their work the authors describe how training can be split into a manifold phase and density phase, wherein the manifold phase T m1 is trained to learn the manifold, and in the density phase T m1 if fixed and T n0 is trained to learn the density thereupon. This statement is made formal and proven by our Cor. 1.

heading: B.2 CONNECTION TO KOTHARI ET AL. (2021)
text: 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 lowdimensional early stages of the network, which gives the architecture a shape similar to the titular instrument.
The architecture studied in Kothari et al. (2021) is precisely of the form of Eqn. 1, where the bijective flow networks are revnets Gomez et al. (2017); Jacobsen et al. (2018) architecture, and the expansive elements are 1 × 1 convolutions, as in (R2). To out knowledge, there are no results that show that the revnets used are universal approximators, but if they revnets are substituted with either (T1) or (T2), then the, we could apply Theorem 1 to the resulting architecture.
The authors of Kothari et al. (2021) also remark that their entire network can be designed in order to facilitate uncertainty quantification, a remark that we too can apply to our networks, as discussed further in Section D.2.

heading: APPENDIX C PROOFS

heading: C.1 MAIN RESULTS

heading: C.1.1 HELPER LEMMA
text: Before presenting the proof of Lemma 7, we present the following three helper inequalities
Lemma 6. For all of the following results, f ∈ emb(K,Rm) and g ∈ emb(W,Rm) and n ≤ o ≤ m.
1.
BK,W (f, g) ≥ sup xn∈K inf xo∈W ‖g(xo)− f(xn)‖2 . (19)
2. Let X,Y ⊂ W , let g be Lipschitz on W , and r ∈ emb(X,Y ). Then, there is a r′ ∈ emb(g(X), g(Y )) such that g ◦ r = r′ ◦ g and ‖I − r′‖L∞(g(X)) ≤ ‖I − r‖L∞(X) Lip(g).
3.
‖I − r‖L∞(K) = ∥∥I − r−1∥∥ L∞(r(K)) (20)
4. Let K ⊂ Rn, X ⊂ Rp and W ⊂ Ro be compact sets. Also, let f ∈ emb(K,W ) and h ∈ emb(X,W ), and let g ∈ emb(W,Rm) be a Lipschitz map. Then
BK,X(g ◦ f, g ◦ h) ≤ Lip(g)BK,X(f, h). (21)
Proof. 1. Let r ∈ C(f(K), g(W )), then ‖I − r‖L∞(f(K)) = sup
xn∈K ‖(I − r)f(xn)‖2 = sup xn∈K ‖f(xn)− r ◦ f(xn)‖2
= sup xn∈K
‖f(xn)− g(xo)‖2 where xo = g−1 ◦ r ◦ f(xn)
≥ sup xn∈K inf xo∈W ‖f(xn)− g(xo)‖2 .
2. g is injective onX , hence we can define r′ such that r′ = g ◦r ◦g−1 : g(X)→ g(r(X)) ⊂ g(Y ) such that r′ ∈ emb(g(X), g(Y )), and thus ∀x ∈ X ,
‖(I − r′) ◦ g(x)‖2 = ‖g(x)− g ◦ r(x)‖2 ≤ Lip(g) ‖I − r‖L∞(X) (22)
where we have used ‖r(x)− x‖2 ≤ ‖I − r‖L∞(X).
3. For every x ∈ r(K), we have a y ∈ K such that x = r(y), thus ∀x ∈ r(K),∥∥(I − r−1) (x)∥∥ 2
= ‖(r − I) (y)‖2 . (23) But r is clearly surjective onto it’s range, hence taking the supremum over all x ∈ X yields∥∥I − r−1∥∥
L∞(r(K)) = ‖I − r‖L∞(K) (24)
4. As g ∈ emb(W,Rm), the map g : W → g(W ) is a homeomorphism and there is g−1 ∈ emb(g(W ),W ). For a map r ∈ emb(g ◦ f(K), g ◦ h(X)), we see that r̂ = g−1 ◦ r ◦ g ∈ emb(f(K), h(X)). Also, the opposite is valid as if r̂ ∈ emb(f(K), h(X)) then r = g ◦ r̂ ◦ g−1 ∈ emb(g ◦ f(K), g ◦ h(X)). Thus
BK,X(g ◦ f, g ◦ h) = inf r∈emb(g◦f(K),g◦h(X)) ‖I − r‖L∞(g◦f(K))
= inf r=g◦r̂◦g−1∈emb(g◦f(K),g◦h(X))
‖I − g ◦ r̂ ◦ g−1‖L∞(g◦f(K))
= inf r̂∈emb(f(K),h(X))
‖g ◦ (I − r̂) ◦ g−1‖L∞(g◦f(K))
≤ Lip(g) inf r̂∈emb(f(K),h(X)) ‖(I − r̂) ◦ g−1‖L∞(g◦f(K))
≤ Lip(g) inf r̂∈emb(f(K),h(X)) ‖I − r̂‖L∞(f(K))
≤ Lip(g)BK,X(f, h)

heading: C.1.2 LEMMA 7, USEFUL EMBEDDING GAP INEQUALITIES
text: Lemma 7. Let f ∈ emb(K,Rm) and g ∈ emb(W,Rm) and n ≤ o ≤ m. Then the following hold:
1. BK,W (f, g) ≤ supx∈K ‖g ◦ h(x)− f(x)‖2 where h ∈ emb(K,Ro) is a map satisfying h(K) ⊂W .
2. For any X that is the closure of an open set , if h ∈ emb(X,W ) then BK,W (f, g) ≤ BK,X(f, g ◦ h) (25)
3. For any r ∈ emb(f(K),Rm), BK,W (f, g) ≤ ‖I − r‖L∞(f(K)) +BK,W (r ◦ f, g). (26)
4. For any r ∈ emb(f(K), g(W )) and h ∈ emb(X,W ) where X ⊂ Rp is the closure of a compact set where n ≤ p ≤ o we have that
BK,X(f, g ◦ h) ≤ ‖I − r‖L∞(f(K)) + Lip(g)BK,X(g−1 ◦ r ◦ f, h) (27) where Lip(g) denotes the Lipschitz constant of g.
5. For any µn ∈ P(K), there is a µo ∈ P(W ) such that W2 (f#µn, g#µo) ≤ BK,W (f, g). (28)
The proof of Lemma 7. 1. If we let r := g ◦ h ◦ f−1, then r ∈ emb(f(K), g(W )), and BK,W (f, g) ≤ ‖‖(I − r) ◦ f(x)‖2‖L∞(K) (29)
= ∥∥∥∥f(x)− g ◦ h ◦ f−1 ◦ f(x)∥∥
2 ∥∥ L∞(K)
≤ sup x∈K ‖f(x)− g ◦ h(x)‖2 .
(30)
2. Given that g ◦ h(X) ⊂ g(W ), we have that emb(f(K), g ◦ h(X)) ⊂ emb(f(K), g(W )), thus the infimum in Eqn. 6 is taken over a smaller set, thus BK,W (f, g) ≤ BK,X(f, g ◦ h).
3. Note that for any r′ ∈ emb(r ◦ f(K), g(W )), r′ ◦ r ∈ emb(f(K), g(W )), and so we have BK,W (f, g) ≤ ‖I − r′ ◦ r‖L∞(f(K)) ≤ ‖I − r‖L∞(f(K)) + ‖r − r′ ◦ r‖L∞(f(K)) (31)
= ‖I − r‖L∞(f(K)) + ‖I − r′‖L∞(r◦f(K)) (32) where we have used that r is injective for the final equality. This holds for all possible r′, hence we have the result.
4. Recall that f ∈ emb(K,W ), g ∈ emb(W,Rm), h ∈ emb(X,W ) and r ∈ emb(f(K), g(W )). Then g−1 ∈ emb(g(W ),W ). As r ◦ f(K) ⊂ g(W ), we see that
r ◦ f = g ◦ g−1 ◦ r ◦ f. This, Lemma 7, point 3 and Lemma 6, point 4 yield that
BK,X(f, g ◦ h) ≤ ‖I − r‖L∞(f(K)) +BK,X(r ◦ f, g ◦ h) ≤ ‖I − r‖L∞(f(K)) +BK,X(g ◦ g−1 ◦ r ◦ f, g ◦ h) ≤ ‖I − r‖L∞(f(K)) + Lip(g)BK,X(g−1 ◦ r ◦ f, h),
which proves the claim.
5. Let r ∈ emb(f(K), g(W )) be such that ‖I − r‖L∞(Range(f)) ≤ BK,W (f, g) + for some > 0, then for every x ∈ K, there exists y ∈ W such that g(y) = r ◦ f(x). From injectivity of g, we have that y = g−1◦r◦f(x). Note that g−1◦r◦f ∈ emb(K,W ), hence K ′ := g−1◦r◦f(K) is compact. Define µ′ := (g−1 ◦ r ◦ f)#µ. Clearly g#µ′ = r ◦ f#µ, and thus
W2 (g#µ ′, f#µ) ≤W2 (g#µ′, r ◦ f#µ) + W2 (r ◦ f#µ, f#µ) (33)
but W2 (g#µ′, r ◦ f#µ) = 0 and
W2 (r ◦ f#µ, f#µ) ≤ (∫
K
‖I − r‖22 df#µ )1/2 ≤ BK,W (f, g) + . (34)
This is true for every > 0, hence taking the infimum over all r ∈ emb(f(K), g(K)) establishes W2 (g#µ′, f#µ) ≤ BK,W (f, g) + for every > 0, and thus we have that W2 (g#µ ′, f#µ) ≤ BK,W (f, g).

heading: C.2 MANIFOLD EMBEDDING PROPERTY

heading: C.2.1 THE PROOF OF LEMMA 1
text: The proof of Lemma 1. (i) Let us consider > 0, a compact set K ⊂ Rn and f ∈ emb(Rn,Rm). Let W = K × {0}o−n and F : Ro → Rm be the map given by F (x, y) = f(x), (x, y) ∈ Rn × Ro−n. Because Ro,m is a uniform universal approximator of C(Rn,Rm), there is an R ∈ Ro,m such that ‖F −R‖L∞(W ) < . Then for the map E = I ◦ R we have that BK,W (f,E) < . This is true for every > 0, and so Eo,m has the MEP property w.r.t. the family emb(Rn,Rm).
(ii) Recall that f := Φ0 ◦ R0 for Φ0 ∈ Diff1(Rm,Rm) and linear R0 : Rn → Rm, and that R ∈ R is such that R ∣∣ U
is linear for open U . We present the proof in the case when n = o, and we make the assumption that R ∣∣ K
is linear. In this case, we have the existence of an affine map A : Rm → Rm so that R0 = A ◦ R so that K̃ := R0(K) = A(R(K)). Let > 0 be given. By (Hirsch, 2012, Chapter 2, Theorem 2.7), the space Diff2(Rm,Rm) is dense in the space Diff1(Rm,Rm), and so there is some Φ1 ∈ Diff2(Rm,Rm) such that
‖Φ1|K̃ − Φ0|K̃‖L∞(K̃;Rm) <
2 .
Then, let T ∈ T m be such that ‖T − Φ1 ◦A‖L∞(R(K);Rm) < 2 . Then we have that ‖T ◦R− f‖L∞(K) = ‖T ◦R− Φ0 ◦R0‖L∞(K)
≤ ‖T ◦R− Φ1 ◦A ◦R‖L∞(K) + ‖Φ1 ◦A ◦R− Φ0 ◦R0‖L∞(K) ≤ ‖T − Φ1 ◦A‖L∞(R(K)) + ‖Φ1 ◦A ◦R− Φ0 ◦A ◦R‖L∞(K) <
2 + 2 = .
Hence, if we let r = T ◦R◦f−1 ∈ emb(f(K), T ◦R(K)) then we obtain thatBK,K(f, T ◦ R) < . This holds for any , and hence we have that T ◦ R has the MEP for I(Rn,Rm). The proof in the case that o ≥ n follows with minor modification, and applying Lemma 7 point 1.

heading: C.2.2 S1 CAN NOT BE MAPPED EXTENDABLY TO THE TREFOIL KNOT
text: We first show that there are no maps E := T ◦ R where R : R2 → R3 such that T is a homeomorphism and E(S1) is a trefoil knot. We use the fact that the trivial knot S1 and the trefoil knot M = f(S1) are not equivalent, that is, there are no homeomorphisms in R3 that map S1 toM. Indeed, by (Murasugi, 2008, Section 3.2), the trefoil knotM and its mirror image are not equivalent, whereas the trivial knot S1 and its mirror image are equivalent. Hence,M andR(S1) are not equivalent 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 : R3 → R3 such that T (R3 \ R(S1)) = R3 \M. As the orientation of the map T can be changed by composing T with the reflection J : R3 → R3 across the plane Range(R) that defines a homeomorphim J : R3 \ R(S1) → R3 \ R(S1), we see that there is no homeomorphism T : R3 → R3 such that T (R3 \R(S1)) = R3 \M. This example shows that the composition E = T ◦ R of a linear map R and a coupling flow T cannot have the property that E(S1) = f(S1) for this embedding f . Moreover, the complement R3 \ E(S1) is never homeomorphic to R3 \ f(S1) for any such map E. We now construct another example, similar to Figure 2, where an annulus that is mapped to a knotted ribbon in R3. To do this, replace the circle S1 by an annulus K = {x ∈ R2 : 1/2 ≤ |x| ≤ 3/2}, that in the polar coordinates is {(r, θ) : 1/2 ≤ r ≤ 3/2} and define a map F : K → R3 by defining in the polar coordinates F (r, θ) = f(θ) + a(r − 1)v(θ) where f : S1 → Σ1 ⊂ R3 is an smooth embedding of S1 to a trefoil knot Σ1 and v(θ) ∈ R3 is a unit vector normal to Σ1 at the point f(θ) such that v(θ) is a smooth function of θ, and a > 0 is
a small number. In this case, M1 = F (K) is a 2-dimensional submanifold of R3 with boundary, which can visualizes M1 as a knotted ribbon.
We now show that there are no maps E = T ◦R such that E(K) = F (K) where T : R3 → R3 is an embedding, and R : R2 → R3 injective and linear. The key insight is that if such a T existed, then this implies that the trefoil knot is equivalent to S1 in R3, which is known to be false.
Let Uρ(A) denote the ρ-neighborhood of the set A in R3. It is easy to see that R2 \ ({0} × [−1, 1]) is homeomorphic to R2 \ BR2(0, 1), which is further homeomorphic to R2 \ {0}. Thus, using tubular coordinates near Σ1 and a sufficiently small ρ > 0, we see that R3 \M1 is homeomorphic to R3 \ Uρ(Σ1), which is further homeomorphic to R3 \ Σ1. Also, when R : R2 → R3 is an injective linear map, we see that M2 = R(K) is a un-knotted band in R3 and R3 \M2 is homeomorphic to R3 \ Σ2. If R3 \ M1 and R3 \ M2 would be homeomorphic, then also R3 \ Σ1 and R3 \ Σ2 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 R : R2 → R3 and homeomorphisms Φ : R3 → R3 such that (Φ ◦R)(K) = M1. Similar examples can be obtained in a higher dimensional case by using a knotted torus Séquin (2011)4 and their Cartesian products.

heading: C.2.3 THE PROOF OF EXAMPLE 1
text: Proof. (i) From (Puthawala et al., 2020, Theorem 15) we have that Ro,m can approximate any continuous function f ∈ emb(Rn,Rm). Further, clearly (T1) and (T2) both contain the identity map, thus Lemma 1 (i) applies.
(ii) Let T m be the family autoregressive flows with sigmoidal activations defined in (Huang et al., 2018). By (Teshima et al., 2020, App. G, Theorem 1 and Proposition 7), T m are sup-universal approximators in the space Diff2(Rm,Rm) of C2-smooth diffeomorphisms Φ : Rm → Rm. WhenRo,m is one of (R1) or (R2) the network is always linear, hence the conditions are satisfied. If Ro,m is (R4), then Ro,m contains linear mappings, and if (R3), then we can shift the origin, so that R(x) is linear on K. In all cases, Lemma 1 part (ii) applies.

heading: C.2.4 THE PROOF OF LEMMA 2
text: Given an f ∈ emb∞(K,Rm) we first show that form ≥ 2n+1 there are always a diffeomorphisms Ψ: Rm → Rm so that Ψ ◦ f : Rn → {0}n ×Rm−n. The existence of such a Ψ borrows ideas from Whitney’s embedding theorem (Hirsch, 2012, Theorems 3.4 & 3.5) and is constructed by iteratively constructing an injective projection.
Next if m−n ≥ 2n+ 1, then we can apply (Madsen et al., 1997, Lemma 7.6), a consequence of the Tietze extension theorem, to show that Ψ: M→ {0}n×Rm−n can be extended to a diffeomorphism on the entire space, h : Rm → Rm. Hence f(x) = Ψ−1 ◦ h ◦ R(x) for diffeomorphism Ψ−1 ◦ h : Rm → Rm and zero-padding operator R : Rn → Rm, and thus f ∈ I∞(K,Rm). This fact that for m sufficiently large compared to n such a diffeomorphism can always be extended is related to the fact that in 4-dimensions, all knots can be opened. This can be contrasted with the case in Figure 2.
Now we present our proof.
Proof. Let use next prove Eq. 9 when m ≥ 3n+ 1.Let
f ∈ embk(Rn,Rm) (35)
be a Ck map andM = f(Rn) be an embedded submanifold of Rm. 4On the knotted torus, see http://gallery.bridgesmathart.org/exhibitions/ 2011-bridges-conference/sequin.
We have that m ≥ 3n+ 1 > 2n+ 1. Let Sm−1 be the unit sphere of Rm and let SRm = {(x, v) ∈ Rm × Rm : ‖v‖ = 1}
be the sphere bundle of Rm that is a manifold of dimension 2m − 1. By the proof’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 ⊂ Sm−1 of Hausdorff dimension 2n such that for all w ∈ Rm \ H1 the orthogonal projection Pw : Rm → {w}⊥ = {y ∈ Rm : y ⊥ w} has a restriction Pw|M onM defines an injective map
Pw|M :M→ {w}⊥. Moreover, let TxM be the tangent space of manifoldM at the point x and let us define another set of ‘problem points’ as H2 = {v ∈ Sm−1 : ∃x ∈M, v ∈ TxM}. For w ∈ Sm−1 \H2 the map Pw|M :M→ {w}⊥ ⊂ Rm is an immersion, that is, it has an injective differential. The sphere tangent bundle SM ofM 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 − 1 and hence the set Sm−1 \ H is non-empty. For w ∈ Sm−1 \H the map Pw|M :M→ {w}⊥ is a Ck injective immersion and thus
Ñ = Pw(M) ⊂ {w}⊥
is a Ck submanifold.
Let Z : Pw(M)→M be the Ck function defined by Z(y) ∈M, Pw(Z(y)) = y,
that is it is the inverse of Pw|M :M→ Pw(M), where Pw(M) ⊂ {w}⊥. Let g : Ñ = Pw(M)→ R be the function g(y) = (Z(y)− y) · w, y ∈ Pw(M). Then Ñ is a n-dimensional Ck submanifold of (m − 1)-dimensional Euclidean space H = {w}⊥ and g is a Ck function defined on it. By definition of a Ck submanifold of H , any point x ∈ Ñ has a neighborhood U ⊂ H with local Ck coordinates ψ : U → Rm such that ψ(Ñ ∩ U) = ({0}m−1−n×Rn)∩ψ(U). Using these coordinates, we see that g can be extended to a Ck function in U . Using a suitable partition of unity, we see that there is a Ck map G : {w}⊥ → R that a Ck extension of g that is, G|Ñ = g. Then the map Φ1 : Rm → Rm, Φ1(x) = x−G(Pw(x))w is a Ck diffeomorphism of Rm that mapsM to m− 1 dimensional space {w}⊥, that is
Φ1(M) ⊂ {w}⊥. In the case when m ≥ 3n+ 1, we can repeat this construction n times. This is possible as m− n ≥ 2n + 1. Then we obtain Ck diffeomorphisms Φj : Rm → Rm, j = 1, . . . , n such that their composition Φn ◦ · · · ◦ Φ1 : Rm → Rm is a Ck-diffeomorphism such that which
Φn ◦ · · · ◦ Φ1(M) ⊂ Y ′, where Y ′ ⊂ Rm is a m − n dimensional linear space. By letting Ψ = Q ◦ Φn ◦ · · · ◦ Φ1 for rotation matrix Q ∈ Rm×m, we have that Y := Q(Y ′) = {0}n × Rm−n. Also, letting φ : X = Rn × {0}m−n → Rm be the map
φ(x, 0) = Ψ(f(x)) ∈ Y, where f is the function given in Eq. 35, we have that φ : X → Y is a Ck-diffeomorphism. We observe that m− n ≥ 2n+ 1 and so we can apply (Madsen et al., 1997, Lemma 7.6) to extend φ to a Ck-diffeomorphism
h : Rm → Rm
such that h|X = φ. Note that (Madsen et al., 1997, Lemma 7.6) concerns an extension of a homeomorphism, but as the extension h is given by an explicit formula which is locally a finite sum of Ck functions, the same proof gives a Ck-diffeomorphic extension h to a diffeomorphism φ. This technique is called the ‘clean trick’.
Finally, to obtain the claim, we observe that when R : Rn → Rm, R(x) = (x, 0) ∈ {0}n × Rm−n is the zero padding operator, we have
f(x) = Ψ−1(φ(R(x))), x ∈ Rn. As h|X = φ and R(x) ∈ X , this yields
f(x) = Ψ−1(h(R(x))), x ∈ Rn, that is, f = E ◦R where E = Ψ−1 ◦ h : Rm → Rm is a Ck diffeomorphism. Thus f ∈ Ik(Rn,Rm). This proves Eq. 9 when m ≥ 3n+ 1.

heading: C.2.5 THE PROOF OF LEMMA 3
text: The proof of Lemma 3. Let f = F2 ◦ F1 where F2 ∈ Fo,m and F1 ∈ Fn,o and > 0 be given, and let Eo,m. Clearly, BK,W (f,E) ≤ BK,W (F2, E) and so by the m, o, o MEP of Eo,m with respect to Fo,m, we have the existence of an rm ∈ emb(f(K), Eo,m) such that ‖I − r‖L∞(f(K)) < . Ko := (E o,m) −1 ◦ r ◦ f(K) is compact, hence Eo,m is Lipschitz on Ko, so we can apply Lemma 7 point 4, so
BK,W (f,E o,m ◦ Ep,o) ≤ ‖I − r‖L∞(f(K)) + Lip(Eo,m)BK,W ((Eo,m)
−1 ◦ r ◦ f,Ep,o). (36)
But, because f ∈ Fo,m◦Fn,o, we can choose aEp,o ∈ Ep,o1 so thatBK,W ((Eo,m)−1◦r◦f,Ep,o) ≤ 2 Lip(E o,m) which, combined with Eqn. 36, proves the result.

heading: C.2.6 THE PROOF OF LEMMA 4
text: The proof of Lemma 4. Recall that F ⊂ emb(Rn,Rm). Suppose that Eo,m2 does not have the m,n, o MEP with respect to F , then there are some > 0 and f ∈ F so that
∀Eo,m ∈ Eo,m2 ∀W1 ⊂⊂ Ro, BK,W1(f,Eo,m2 ) ≥ . (37) From Lemma 7 point 2, we have that
≤ BK,W1(f,Eo,m2 ) ≤ BK,W (f,Eo,m2 ◦ Ep,o1 ) (38) for all Ep,o1 ∈ Ep,o1 and for all compact sets W ⊂ Rp that satisfy Ep,o1 (W1) ⊂ W . We observe that if W ′ ⊂ Rp is a compact set such that W ′ ⊂W , we have
BK,W (f,E o,m 2 ◦ Ep,o1 ) ≤ BK,W ′(f,Eo,m2 ◦ Ep,o1 )
Thus, inequality Eq. 38 holds for all Ep,o1 ∈ Ep,o1 and for all compact sets W ⊂ Rp. Summarising, we have seen that there are f ∈ F and > 0 such that for all Ep,o1 ∈ Ep,o1 and for all compact sets W ⊂ Rp we have ≤ BK,W (f,Eo,m2 ◦ Ep,o1 ). Hence Eo,m2 does not have the m,n, o MEP with respect to F , and we have obtained a contradiction, which proves the result.

heading: C.3 UNIVERSALITY

heading: C.3.1 THE PROOF OF THEOREM 1
text: The proof of Theorem 1. First we prove the claim under the assumptions (i).
First we prove the claim under assumption (i).
Let W ⊂ Rn be an open relatively compact set. From Lemma 3 we have that En,m := EnL−1,mL ◦ · · · ◦ En,n11 (39)
has them,n, n MEP w.r.t. F := FnL−1,mL ◦ · · · ◦Fn,n11 . Thus for any 1 > 0, we have an Ẽ ∈ En,m s.t. BK,W (F, Ẽ) < 1.
From Lemma 7 point 5, we have the existence of a µ′ ∈ P(W ) so that W2 ( F#µ, Ẽ#µ ′ ) < 1. By convolving µ′ with a suitable mollifier φ, we can obtain a measure µ′′ = µ′ ∗ φ ∈ P(W ) that is absolutely continuous with respect to the Lebesgue measure so that
W2 (µ ′, µ′′) <
1
1 + Lip(Ẽ) ,
see (Ambrosio et al., 2008, Lemma 7.1.10.), and so W2 ( Ẽ#µ ′, Ẽ#µ ′′ ) < 1. Hence,
W2 ( F#µ, Ẽ#µ ′′ ) < 2 1. (40)
Next, from universality of T n0 for any 2 > 0, we have the existence of a T0 ∈ T n0 so that W2 (µ ′′, T0#µ) < 2. From Lemma 7 points 3 and 4 we have that
W2 ( F#µ, Ẽ ◦ T0#µ ) ≤ 2 1 + 2 Lip(Ẽ). (41)
For a given > 0, choosing 1 < 4 and 2 < 2(1+Lip(Ẽ)) yields that the map E = Ẽ ◦ T0 ∈ E is such that W2 (F#µ,E#µ) < . This yields the result.
Next we prove the claim under the assumptions (ii). By our assumptions, in the weak topology of the space C2(Rnj ,Rnj ), the closure of the set T nj ⊂ C2(Rnj ,Rnj ) contains the space of Diff2(Rnj ,Rnj ). Moreover, by our assumptions Rnj−1,nj contains a linear map R. We observe that as Rnj−1,nj is a space of expansive elements, the map R is injective. and hecne by Lemma 1, the family
Enj−1,njj = T nj ◦ Rnj−1,nj
has the MEP w.r.t. F = I1(Rn,Rm). By Lemma 2, we have that I1(Rn,Rm) coincides with the space emb1(Rn,Rm). Finally, by the assumption that T n00 is dense in the space of C2diffeomorphism Diff2(Rn`) implies that T n00 is a Lp-universal approximator for the set of C∞smooth triangular maps for all p <∞. Hence by Lemma 3 in Appendix A of Teshima et al. (2020), T n00 is a distributionally universal. From these the claim in the case (ii) follows in the same way as the case (i) using the family F = emb1(Rn,Rm).

heading: C.3.2 THE PROOF OF LEMMA 5
text: 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 BK,W (f,E) is never smaller than > 0 for all E ∈ E . Applying the definition of BK,W (f,E) from Eqn. 6 yields the result.

heading: C.3.3 THE PROOF OF COR. 1
text: The proof of Cor. 1. The proof of Eqn 12 follows from the definition of the MEP.
The proof of Eqn. 13 follows from applying Lemma 7 point 4, and applying the same arguments as in the proof of Theorem 1 so that limi→∞ 1Lip(Ei)BK,W (E −1 i ◦ r ◦ f,E′i) → 0, and so that W2 (F#µ,Ei ◦ E′i#µ′) = i where i → 0 as i→∞.. From the distributional universality of T n0 , and continuity of Ei ◦E′i we have the existence of a Ti ∈ T n0 so that W2 (F#µ,Ei ◦ E′i ◦ Ti#µ) = 2 i. Choosing i so that limi→∞ i yields the result.

heading: APPENDIX D ADDITIONAL PROPERTIES

heading: D.1 LAYER-WISE PROJECTION
text: 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
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 a standard least-squares solver.
The second step is always straight-forward to analyze, but the first is more complicated. The key step in our algorithm is the fact that for the specific choice of weight matrix W = [
B −DB
] ,
given any y ∈ R2n, we can always solve the least-squares inversion problem exactly. We prove this result in several parts given below.
1. For any y ∈ R2n, MyW ∈ Rn×n is full-rank. 2. If [y]i 6= [y]i+n for each i = 1, . . . , n, then the argmin in Eqn. 17 is well defined, i.e. that
there is a unique minimizer. Otherwise there are 2I minimizers, where I is the number of distinct i such that [y]i = [y]i+n.
3. If M̃y = [ ∆y (I n×n −∆y) ] , then
min x∈Rn ‖y −R(x)‖22 = minx∈Rn ‖My (y −Wx)‖ 2 2 + ∥∥∥M̃yy∥∥∥2 2 . (42)
4. We verify Eqn. 17.
The proof of Theorem 2. 1. Using the definition of My , we have,
My [ B −DB ] = ( In×n −∆y ) B −∆yDB = ( In×n −∆y −∆yD ) B. (43)
But, (In×n −∆y −∆yD) is a full-rank diagonal matrix (with entries either 1 or [D]i,i), and B is full rank by assumption, hence My [ B −DB ] is too.
2. Because B is square and full rank there exists a basis5 { b̂i } i=1,...,n of Rn such that
〈 b̂j , bi 〉 = { 1 if i = j 0 if i 6= j . (44)
For an x ∈ Rn, let αi = 〈x, bi〉 for i = 1, . . . , n be the expansion of x in the b̂i basis.
min x∈Rn ‖y −R(x)‖22 = minx∈Rn 2n∑ i=1 [y −R(x)]2i (45)
= n∑ i=1 min xi∈R ([y]i −max(〈x, bi〉 , 0)) 2 + ( [y]i+n −max(〈x,− [D]ii bi〉 , 0) )2 (46)
We now consider minizing Eqn. 46 by minimizing the basis expansion in terms of αi, n∑ i=1 min αi∈R ([y]i −max(αi, 0)) 2 + ( [y]i+n −max(− [D]ii αi, 0) )2 (47)
Eqn. 47 is clearly minimized by minizing each term in the sum, hence we search for a minimizer of the i’th term
min αi∈R
([y]i −max(αi, 0)) 2 + ( [y]i+n −max(− [D]ii αi, 0) )2 (48)
5Namely the columns of the matrix B−1
Noting f(αi) as the quantity inside the minimum of Eqn. 48, we consider the positive, negative and zero αi cases of Eqn. 48 separately and we get
min αi∈R+ f(αi) = min αi∈R+
([y]i − αi) 2 + [y] 2 i+n = [y] 2 i+n (49)
min αi∈R− f(αi) = min αi∈R+
[y] 2 i + ( [y]i+n + [D]ii αi )2 = [y] 2 i (50)
f(0) = [y] 2 i + [y] 2 i+n . (51)
If [y]i+n > [y]i, then the minimizer of Eqn. 48 is αi = − [y]2i+n [D]ii
< 0. Conversely if [y]i+n < [y]i then the minimzer of Eqn. 48 is αi = [y]i > 0. This argument applies all i = 1, . . . , n, and hence if [y]i 6= [y]i+1 for all i = 1, . . . , n then the minimizing x is unique.
If [y]i = [y]i+1 then there are exactly two minimizers of f(αi), − [y]2i+n [D]ii and [y]i, for both of which f(αi) = [y] 2 i = [y] 2 i+n.
3. If we suppose that [y]i+n − [y]i > 0, then [c(y)]i = 0 and [c(y)]i+n > 0, thus [∆y]ii = 1, hence if we let xmin be the minimizing x from part 1, then
([y]i −max(〈xmin, bi〉 , 0)) 2 + ( [y]i+n −max(〈xmin,− [D]ii bi〉 , 0) )2 (52)
= [y] 2 i + ( [y]i+n −max(〈xmin,− [D]ii bi〉 , 0) )2 (53)
= [ M̃yy ]2 i + [My (y −Wxmin)]2i (54)
If [y]i+n − [y]i ≤ 0 then we have
([y]i −max(〈xmin, bi〉 , 0)) 2 + ( [y]i+n −max(〈xmin,− [D]ii bi〉 , 0) )2 (55)
= ([y]i −max(〈xmin, bi〉 , 0)) 2 + [y] 2 i+n (56) = [My (y −Wxmin)]2i + [ M̃yy ]2 i . (57)
Thus combining Eqn.s 45, 46, 54 and 57 for each i = 1, . . . , n, we have that
min x∈Rn ‖y −R(x)‖22 = minx∈Rn ‖My (y −Wx)‖ 2 2 + ‖Myy‖ 2 2 . (58)
4. For the final point, combining all of the above points we have
min x∈Rn ‖y −R(x)‖22 = minx∈Rn ‖My (y −Wx)‖ 2 2 . (59)
Further we have from Point 1 that MyW is full rank, hence (MyW ) −1 Myy = R †(y) is a minimizer of Eqn. 59. If [y]i 6= [y]i+n for all i = 1, . . . , n then Part 2 applies, and R†(y) is the unique minimizer of ‖y −R(x)‖22. In either case, we have that R†(y) is a minimizer.

heading: D.2 BAYESIAN UNCERTAINTY QUANTIFICATION
text: We now discuss the process for making the network amenable to Bayesian Uncertainty Quantification (Bayesian UQ).
Assumption 2. Let y0 ∈ Rn be given, let y1 = T0y0 and for each ` = 2, . . . , L, then let y` := R`(y`−1/2) and y`−1/2 := T`−1(y`−1). We assume that for ` = 1, . . . , L − 1, T`(y`), R`(y`−1/2) and T0(y0) are differentiable.
Lemma 8. If a network F of the form of Eqn. 1 satisfies Assumption 2, then we have the following upper bound on the log-likelihood,
log py(y0) ≤ log pz(F−1(y0)) + 1
2 L∑ `=1 log ∣∣∣∣∣det ∂R`∂y`−1/2 T (y`−1/2) ∂R` ∂y`−1/2 (y`−1/2) ∣∣∣∣∣ +
L∑ `=0 log ∣∣∣∣det ∂T`∂y` (y`) ∣∣∣∣ . (60)
Proof. The proof of Lemma 8 follows from computing the log of,
py(y0) = pz(F −1(y0)) ∣∣∣∣∣det ∂F−1∂y0∣∣F (Rn) ∣∣∣∣∣ (61)
and then applying definition 1 and expanding term using the laws of logarithms we obtain.
log py(y) ≤ log pz(F−1(y)) + 1
2 L∑ `=1 log ∣∣∣∣∣det ∂R`∂y`−1/2 T (y`−1/2) ∂R` ∂y`−1/2 (y`−1/2) ∣∣∣∣∣︸ ︷︷ ︸ R
+ L∑ `=0 log ∣∣∣∣det ∂T`∂y` (y`) ∣∣∣∣︸ ︷︷ ︸
T
. (62)
for ` = 1, . . . , 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, as the flow-layers are all endomorphisms, i.e. Rn` → Rn` . We now remark on the ease of approximating, or at least bounding, T and R in Eqn. 62.
Values for R whenR is (R1) or (R2) are straightforward to compute or approximate6. WhenRn,m is (R3), R ∈ R are not differentiable, but are differentiable a.e.. Further, ∇R`(xn`) can a.e. be computed by applying a simple mask 0 and 1 mask to the weight matrices for an exact computation of R . Additionally, from Hutchinson (1989); Kothari et al. (2021) we have the following formula that approximates R ,
log ∣∣∣∣∣det ∂R`∂y` T ∂R` ∂y` ∣∣∣∣∣ = −Tr 1 k ∞∑ k=1 ( I − β ∂R` ∂y` T ∂R` ∂y` )k− d log β ≈ −Eν 1 k ∞∑ k=1 νT ( I − β ∂R` ∂y` T ∂R` ∂y` )k ν
− d log β. (63) where η ∈ Rn` . Computation of the T term is often easier, comparatively. This is because these networks are often designed to make this value as easy to 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.

heading: D.3 BLACK-BOX RECOVERY
text: We now discuss assumptions that enable black-box recovery of the weights of our entire network post-training.
Assumption 3. For each ` = 1, . . . , L, R` is an affine ReLU layer. Each T` and T0 is constructed from a finite number of affine ReLU layers.
6for example from a LU decomposition, see (Golub, 1996, Section 3.2)
Remark 3. If a network F of the form of Eqn. 1 satisfies Assumption 3, then given the range of the network, the range of the network can be recovered exactly.
Further, if the linear region assumption from Rolnick & Kö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 gi are given by layers of affine ReLU’s.
In Rolnick & Kö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 a 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 as well.
The works of Rolnick & Körding (2020); Bui Thi Mai & Lampert (2020) imply that provided the activation functions of the expressive elements are ReLU then the entire network can be recovered in a black-box way. Further, provided that either the ‘linear region assumption’ from Rolnick & Körding (2020) or the generality assumption from Bui Thi Mai & Lampert (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
f(x) = W2φ(W1x) (64)
where φ is coordinate-wise homogeneous degree 1 (such as ReLU) and W1 ∈ Rn1×n2 and W2 ∈ Rn2×n3 . If we let P ∈ Rn2×n2 be any permutation matrix, and D+ be a diagonal matrix with strictly positive elements, then we can write
f(x) = W2P ′D−1+ φ(D+PW1x) (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 & Körding (2020), the authors describe how all parameters of a ReLU network can be recovered uniquely (called reverse engineered in Rolnick & Körding (2020)), subject to the so called ‘linear7 region assumption’, LRA.
The input space Rn can be partitioned into a finite number of open {Si}nii=1, where for each k, F (x) = Wki + bi, i.e. the network corresponds to an affine polyhedron in the output space. The algorithms (Rolnick & Körding, 2020, Alg.s 1 & 2) are roughly described below.
First, identify at least one point within each affine polyhedra {Hj}njj=1. Then identify the boundaries between polyhedra. The boundaries between sections are always one affine ‘piece’ of piecewise hyperplanes {Hj}njj=1. These {Hj} nj j=1 are the central objects which indicate the (de)activation of an element of a ReLU somewhere in the network. If the Hj are full hyperplanes, then the ReLU that is (de)activates occurs in the first layer of the network. If Hj is not a full hyperplane, then it necessarily has a bend where it intersects another hyperplane Hj′ . Further, except for a Lebesgue measure 0 set, when Hj intersects Hj′ the latter does not have a bend. If this is the case, then Hj′ corresponds to a ReLU (de)activation in an earlier layer than Hj . 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 row-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 if for every distinct Si and Si′ , either Wi 6= Wi′ or bi 6= bi′ . That is, different sign patterns produce different affine sections in the output space. This is a 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 & Körding (2020) show that if it is satisfied,
7The 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 Rolnick & Körding (2020) would use ‘linear’ to preserve mathematical meaning.
then unique recovery follows. Nevertheless recovery of the range of the entire network is possible, but this recovery may not be unique.
In Bui Thi Mai & Lampert (2020) the authors also consider the problem of recovering weights of a ReLU neural network, however the authors therein study the question of 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 En0,nL be a ReLU network that is L layers deep and non-increasing. Suppose that E1, E2 ∈ En0,nL , E1 and E2 are general8 and for all x ∈ Rn0 E1(x) = E2(x), then E1 is parametrically identical to E2 subject to the two natural isometries.
This work provides the stronger result, however does not apply to the networks that we consider out of the box. It does apply to our expressive elements (provided that they use ReLU activation functions, and are non-increasing), but not necessarily apply to the network on the whole.
8A set it in a topology is general if it’s complement is closed and nowhere dense.

Review summaries:
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).

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.