Why should autoencoders work?
Authors: Matthew Kvalheim
Eduardo Sontag
Venue: Accepted by TMLR ()

Abstract: Deep neural network autoencoders are routinely used computationally for model reduction. They allow recognizing the intrinsic dimension of data that lie in a $k$-dimensional subset $K$ of an input Euclidean space $\mathbb{R}^n$. The underlying idea is to obtain both an encoding layer that maps $\mathbb{R}^n$ into $\mathbb{R}^k$ (called the bottleneck layer or the  space of latent variables) and a decoding layer that maps $\mathbb{R}^k$ back into $\mathbb{R}^n$, in such a way that the input data from the set $K$ is recovered when composing the two maps. This is achieved by adjusting parameters (weights) in the network to minimize the discrepancy between the input and the reconstructed output. Since neural networks (with continuous activation functions) compute continuous maps, the existence of a network that achieves perfect reconstruction would imply that $K$ is homeomorphic to a $k$-dimensional subset of $\mathbb{R}^k$, so clearly there are topological obstructions to finding such a network. On the other hand, in practice the technique is found to ``work'' well, which leads one to ask if there is a way to explain this effectiveness. We show that, up to small errors, indeed the method is guaranteed to work. This is done by appealing to certain facts from differential topology. A computational example is also included to illustrate the ideas.

Published in Transactions on Machine Learning Research (02/2024)
Why should autoencoders work?
Matthew D. Kvalhcim
kvalheim@umbc..cmm eduu
Deportment of Mathematics and Statistics
University of Moryland, Boltimore County, MD, United States.
Eduardo D. Sontag
sontag@soontglabb.og
Departments of Electrical and Computer Engineering and Bioengineering Northeastern University, Boston, MA, United States.
Reviewed on OpenReview: Atips: // openreview. net/ met/ forum? id= uGVFtjuI3u
Abstract
Deep neural network autoencoders are routincly used computationally for model reduction. They allow recognizing the intrinsic dimension of data that lie in a k-dimensional subset K of an imput Euclidean space R". The underlying idea is to obtain both an encoding layer that maps R" into R& (called the bottleneck layer or the space of latent variables) and decoding layer that maps I² back into R", in such way that the input data from the set K is recovered when composing the two maps. This is achieved by adjusting pa- rameters (weights) in the network to minimize the discrepancy between the input and the rected output. Since neural networks (with continuous activation functions) com- pute continuous maps, the existence of a network that achieves perfect reconstruction would imply that K is homcomorphic to k-dimensional subset of R² so clearly there are topo- logical ructions to finding such a nelwork. On the other hand, in practice the technique is found to "work" well, which leads one to ask if there is way to explain this effectiveness. We show that, up to small errors, indeed the method is guaranteed to work. This is done by appealing to certain facts from differential topology. A computational example is also included to illustrate the ideas.
1 Introduction
Many real-world problems require the analysis of large numbors of data points inhabiting some Euclidean space Rt. The "manifold hypothesis" (Felferman et al. 2016) postulates that these points lie on some k-dimensional submanifold with (or without) boundary K C R", so can be described locally by < n parameters. When K a linear submanifold, classical approaches like principal component analysis and multidimensional scaling are effective ways to learn these parameters. But when K is nonlinear, learning these parameters is the more challenging "manifold learning" problem studied in the rapidly developing literature on "geometric deep learning" (Bronstein et al. 2017
One popular approach to this problem relies on deep neural network autoencoders (also called "replicators" (Hecht-Nielsen) 1995)) of the form Go F, where the output of the encoder F: R -> R&* is the desired k < n parameters, G: R R is the decoder, and and G are continuous. See Figure 1 for an illustration. The goal is learn F, G create perfect autoeneoder, one such that G(F(z)) = x for all x E K. The latter condition implies that F| K F(K) C R$ is homeomorphism, since it is a continuous map with a continuous inverse G: F(K) + K. Thus, perfect autoencoder F, G exists if and only if the k-dimensional K is homeomorphic to a subset of R* so there are topological obstructions making this goal impossible in general, as observed in Batson et al. (201) /.
And yet, the wide practical applicability of the method evidences remarkable empirical success from au- toencoders even when K not homcomorphic to such a subset of R$ (We give an illustrative numerical experiment in 3 How can this be?

---

Published in Transactions on Machine Learning Research (02/2024)
encoder F
decoder G
Figure 1: An autoencoder consists of an encoding layer, which maps inputs that lie in a subset K of R" (n= = 12 in this illustration) into a hidden or latent layer of points in R& (here = 4), followed by a decoding layer mapping R& back into R", The goal is to make the decoded vectors (in red) match the data vectors for all in K. Due to topological obstructions, a more realistic goal is to achieve G(F(x)) = x for all in large subset of K.
(in blue). In a perfect autoencoder, G(F(x))
This apparent paradox is resolved by the following Theorem [ which asserts that the set of x E K for which (()( & x can be made arbitrarily small with respect to the "intrinsic measures" 0j and μ (defined in (B. on ŌK and generalizing length and surface area. For the statement, Ft.m denotes any set of continuous functions R' R" with the "universal approximation" property that any continuous function H: R Rn can be uniformly approximated arbitrarily closely on any compact set L S E by some EEF
Theorem 1. Let k N and K C R" be a union of finitely many disjoint compact smoothly embedded submanifolds with boundary each having dimension less than or equal to k. For each 8 >> 0 and finite set S S K, there is closed set Kn S K disjoint from S with intrinsic measures ju(o) < 5, 0u(( n nkk) < 5 such that M \ Ko is connected for each component M of K, and the following property holds. For each there are functions F E F.,,k, G E Flin such that
sup [[G((z)) - x1| <E *
(1)
In this paper, we adopt the standard convention that manifolds are the special case of manifolds with boundary for which the boundary is empty.
Theorem may be interpreted as a "probably approximately correct (PAC)" theorem for autoencoders complemenaary to recent PAC theorems obtained in the manifold learning literature (Felferman el al., 2016 2018 2023). Our theorem asserts that, for any finite training set S of data points in K, there is an autocncoder Go F with error smaller than on S such that the "generalization error" will also be uniformly smaller than E any test data in K Ko-
Remark 1. In particular, Theorem applics when Ft. is collection of possible functions R - R that can be produced by neural networks. Neural networks, particularly in the context of deep learning, have been extensively studied for their ability to approximate continuous functions. Specifically, the Universal Approximation Theorem states that feedforward networks (even with just one hidden layer) can approximate scalar continuous functions on compact subsets of E' (and thus, componentwise, can approximate vector functions as well), under mild assumptions on the activation function. This result was proved for sigmoidal activation functions in [Cybenko (1989) and generalized in Hornik al. (1989). Upper bounds on the num- bers of units required (in single-hidden layer architectures) were given independently in Jones (1992) and Barron (193) for approximating functions whose Fourier transforms satisfy certain integrability condition, providing a Icast-squares error rate O12,//2,, where n is the number of neurons in the hidden layer, and similar results were provided in Donahue et al. (1997) for (more robust. to outliers) approximations in LP spaces with 1 < < so. Although these theorems show that hinglehiddee layer networks are sufficient for universal approximation of continuous functions, it known from practical experience that deeper architoc- tures are often necessary or at least more efficient. There are thcoretical results justifying the advantages of deeper networks. For example, (onnag (1992) showed that the approximation of feedback controllers
2

---

Published in Transactions on Machine Learning Research (02/2024)
for non-holonomic control systems and more generally for inverse problems requires more than one hidden layer, and deeper networks (those with more layers) can represent certain functions more efficiently than shallow networks, in the sense that they require exponentially fewer parameters to achieve given level of approximation (Eldan & Shamir 2016 Telgarsky 2016).
While the intrinsic measures 14, Ojc are a convenient choice for the statement of Theorem I Theorem I still holds verbatim if μ., Ou are replaced by any finite Borel measures v, dv that absolutely continuous with respect to μ. Öp, respectively. Moreover, Dr. Joshua Batson suggested to us the observation that Theorem implies that the (v) loss
Remark 2.
J [[((F()) - ==1² (x)))
can always be made arbitrarily small (this includes the case v/ = pu). See Remarks
7
S in $2 for a detailed
explanation of these observations and their implications for autoencoder training.
Remark 3. The fact that one can pick M \ Ko to be connected for each component M of K, which implies particularly informative and
that also each encoded "good set" F(M) \ Ko) is connected, makes Theorem | interesting. For example, suppose that our data manifold K is connected. Then Theorem [ guarantees that K. \ Ko is connected. In particular, this property implies the ability to "walk along" K \ Ko (e.g., for interpolation of images represented by points in K) using the latent space, since for each x, y E K \ Ko it implies the existence of a smooth path + (t) from F(x) to F(y) in F(K' \ Ku) such that, up E-small errors, the decoded path G()(()) goes from x: to y while staying in K. Also, if this property were not claimed, then a much simpler proof could be based on splitting up K (up to a set of measure zero) into a potentially large number of submanifolds and patching logether autoencoders for each piece.
Remark 4. One should emphasize that Theorem [ is a statement about the fundamental capabilities of autocncoders, but it does not imply that numerical learning algorithms will always succeed finding autoencoder that satisfies the connectedness constraint. (or the desired bounds, for that matter). Our numerical experiments illustrate this phenomenon. For example, Figure 5 shows a learning run in which the encoded good set is (up to sampling resolution) connected, but Figure shows learning instance in which it is not.
The remainder of the paper is organized as follows. Theorem 1 proved in $2 The numerical experiments are in g3 A result ruling out certain extensions of Theorem | proved in $ includes further discussion and directions for future work. An appendix contains the implementation code for these experiments. Another appendix reviews some notions of lopology and related concepts that are used in the paper.
2 Proof of Theorem
In this section we prove Theorem 1 See Appendix B (B.3) for a description of the notions of "intrinsic measure" and "measure zero" discussed herein. An outline of our strategy for the proof is as follows.
First (Lemma D. when K consists of a single k-dimensional component, that C is closed and has measure zero in K, C n 0K has measure zero in aK, and K \ C is connected and admits smooth embedding K \ C > A We next show (Lemma 2 that C can additionally be chosen disjoint from any given finite subset S C K. Successive application of these results extend them to the case that K consists of at most finitely many components, each having dimension less than or equal to k. We then construct (Temma 3 a suitable "thickening" Ko C K of C' that has arbitrarily small positive intrinsic mcasure, but otherwise satisfics the same propertics as C. This thickening is such that the restriction of the smooth embedding K' \ C + R* to K \ Ko extends to a smooth "encoder" map F: R2 + R* Defining the smooth "decoder" map G: _ + Rm to be any smooth extension of the inverse (F)x) -1 F(K) - K Ç R" yields an autocncoder with perfect reconstruction on K \ Ko. i.c., G(F(x)) = for all x E Ko- Finally, since we consider neural network (or other) function approximators that can uniformly approximate but not exactly reproduce all such functions on compact sets, we prove (Theorem T that sufficiently close approximations F, G of F, G will make [[G(F(z)) - x|| arbitrarily uniformly small for all x E K Kg-
construct subset C C K such
The proof of Lemma 1 constructs as a union of "stable manifolds" W*(g) of equilibria g of a certain gradient vector field ( B.3 Such stable manifolds are fundamental in Morse theory Pajiinny 2006
3

---

Published in Transactions on Machine Learning Research (02/2024)
Lemma 1. Let M be a k-dimensional connected compact smooth manifold with boundary. There exists set C C M such that C' is closed and has measure zero in M, Cn&M has measure zero in aM, and M \ C is connected and admits a smooth embedding into IR*
Remark 5. If 0M 2, an alternative proof equips M with any Riemannian metric, fixes E M, and defines C' S M to be the cut locus (Sakai 1996, Def. III.4.3) with respect to p and the metric. This C is closed and has measure zero, and M C is diffeomorphic to IR* (akai 1996 Lem. ITI.4.4..
Proof. Step (setup). Fix any E (M) and Riemannian metric on M. There is a smooth function ş: .M + [0, 1] such that all equilibria of the negative gradient vector field V are hyperbolic ($333 and belong to in), {p} = x (0) the unique local minimum, and 0M = y +1) (Koditschek & Rimon 1990. Thm 3).
Step 2 (construction of о). Define
C= C=W(W(()): Vp(()) = 0, p),
where (q) S M is the set of points whose (-Ve)-trajecctorics converge to the equilibrium E int(MM) as
- 00.
Step 3 (C closed and connected). The complement W*(p) M \C of C' is open and connected since it is the basin of attraction of for V (B..)) so C is closed.
Step 4 (C has measure zero). Since C S M is a union of smoothly embedded submanifolds with boundary N satisfying dim N < dim M and ON = N A aM (Pajitnov 2006 Prop. 1.3.2.13), C and CnêM have measure zero in M and OM, respectively.
Step& (C admits a smooth embedding into R*). Finally, since int( \ C is the basin of attraction of p for the rescaled vector field -11-))
there diffeomorphism F: int im) \ C C' R (Wilson) 1967
Thm 3.4), if Φ': M int(M) is the smooth embedding sending points x<0) E M to the values x(1) of their (- -rajeetttccssssiis z(f), then F Fo M M + R is the desired smooth embedding.
The proof of Lemma 2 constructs a "diffeotopy" smooth 1-parameter family of diffeomorphismss, that moves C' to subset disjoint from S satisfying the same properties C. The use of diffeotopies (or "ambient isotopics") is standard technique in differential topology (Hirsch) 1994 Ch. 8).
Lemma 2. In the setting of Lemma I C can be chosen disjoint from any finite subset S M.
Proof. If M is diffcomorphic to point an interval, then C can be taken to be the empty set. If M is diffeomorphic to circle, then C can be taken to be any point disjoint from S. It remains only to consider the case that dim M 2 2 (Lee) 2013] Ex. 15-13). Since Lemma [ implies that C' does not contain any component of 0M, there is a diffcotopy ÖJ, of 0M, i E [o, 1]. such that the image of S aM under the diffeomorphism 0J1: aM + OM does not intersect C, that is, satisfies 0J1(S n 0M) n Ø (Hirsch 1994. p. 186), (Michor & Vizman 1994). The diffeotopy aJ, extends to one generating a diffeotopy Jr of M, f (0, 1), such that the diffeomorphism J1: M + N satisfies (S) nc = (Michor & Vizman 1994), Hirsch 1994 Thm 8.1.3, Thm 8.1.4) Hence the image Č = J. of C under the diffcomorphism J is a closed measure zero set disjoint from S, M C' connected, and CnaM has measure zero in 0M. Morcover, F: M C + N C R is the smooth embedding from the statement of Lemma 1 then Fod:: M is smooth embedding. Upon replacing C' with Ò, this finishes the proof.
Lemma 3 mmakes use of the "intrinsic measure" d ( B.3 on any union K of smoothly embedded submanifolds of a Euclidean space that is induced by the Riemannian densily [Lee] 2013 p. 428) of the restriction of the Euclidean metric to each component K. We use the notation 0p for the intrinsic measure of ŌK. Any mcasure zero subset C of K in the sense of Loe| (2013) p. 128) has intrinsic measure (cC) = 0, and similarly @p(C n 0K) 0 when C O has measure zero in ŌK.
If 0M Ø, then JJ: the empty diffeotopy, so any diffeotopy automatically an extension of 0J:. Less pedantically, in the case that 0M Ø, there are simply fewer constraints on J..
4

---

Published in Transactions on Machine Learning Research (02/2024)
Remark 6. If A is measurable subset (sB.2) of an é-dimensional component M of K, then p(A) is simply the E-dimensional volume of A. For example, (a(A) is the length of A when k = 1, the surface area. of A when k = 2, the volume of A when Ao = 3, and so on.
The proof of Lemma 3 follows the outline at the beginning of this section. To ensure that the complements M \ Ko of the "thickening" Ko of C' within each component M of K are connected, we construct each M Ko as a connected component of a sufficiently big sublevel set of a suitable function h: K X.C - 0. See Appendix B B.3) for a discussion of the smooth extension lemma used in the proof of Lemina 3
Lemma 3. Let k E N and K C R" be a union of finitely many disjoint compact smoothly embedded submanifolds with boundary each having dimension less than or equal to k. For each 8 > 0 and finite set
5 _ K, there are smooth functions F: RR + R*, G: R* + R" and a closed set Ko S K disjoint from S such that p(Ka) < 6, 0p(Ko 0K) < 8, M \ Kg is connected for each component M of K, and
GoFlRyK, = =io
Proof. Each component M of K is connected compact smooth manifold with boundary of dimension less than or equal to k. Applying Lemmas 2 to each such component yields the existence of a closed set C K disjoint from S such that C' has measure zero in K, Cnok has measure zero in 0K, and M \ C' is connected and admits a smooth embedding into IR* for each component M of K. Compressing the images of these smooth embeddings into arbitrarily small disjoint disks by post-composing each with a suitable diffoomorphism of R produces smooth embedding Fo: K C R
Let h: K) C + oo) be any continuous function such that {h S rr] is compact for every r 2 0 Lee 2013 Prop. 2.28). Arbitrarily select one point in each component of K, and let U3 S K be the open set equal to the union of the components of (h < <}} containing each of these points. The properties of h imply that the increasing union UJEN U, = K \C. Thus, finiteness of S, compactness of K; and outer regularity of the
intrinsic measures B imply the existence of N E N such that K, = K AUN satisfies K = Ø, K, 2 C, p(Ko)= < and (y(Ko n aK)
< 8.
Defining F: I= + R and G: I= + R" respectively to be any smooth extensions LLee 2013 Lem. 2.26) of Fold(Ux) and (Fola(os)) Fo(c)(UN)) - cl(Un) C R completes the proof.
Assune given for each f.m E N a collection F of continuous functions RC + Rm with the following "universal approximation" property: for any E > 0, compact subset L S R', and continuous function H: T + Rmm there is A E Ft.m such that max [(x) - Hx)]l < Equivalently, Frl is any collection of continuous functions R² + Rm that is dense in the space of contimuous functions R - R" with the compact-open topology (Hirsch 1994 Sec. 2.4) discussed in Appendix B B.3). We now restale and prove Theorem
Let k n. E N and K I" be a union of finitely many disjoint compact smoothly embedded submanifolds with boundary each having dimension less than or equal to k. For each 8 > and finite set S C K, there is a closed set Kn C K disjoint from S with intrinsic measures p(Ko) < 5, Opp( Ko n @k)= < 8 such that M Ko is connected for each component M of K, and the following property holds. For each there are functions F E Fn.k, G E Fkin such that
Theorem 1.
sup |I(((()) - -|| KE. *EK'Ko
(1)
Proof. Fix a finile set S C K and >>> 0. Lemma 3 implies the existence of smooth functions F: IR" + R* G: R* + R" and a closed set Ko S K disjoint from S such that μ(Ko) < 6, au(Ko n akk) < 6, M \ Ko is connected for each component M of K, and Go FlAYKo = idx
Fix s > 0. Since K is compact, and by the density of Fr.kk, Joh. and continuity of the composition map (G, + Go o F in the compact-open topologies (Hirsch) 1994. p. 64, Ex. 10(a)), there exist F E Fri.t GE Fkn such that G F is uniformly E-close to G F on K. Since G(F(z)) = z for all x E K \ Ko. the functions F, G satisfy (1) This completes the proof.
5

---

Published in Transactions on Machine Learning Research (02/2024)
Remark 7. The intrinsic measures Jl, du are convenient choice for the statement of Theorem 1 but Theorem 1 still holds verbatim if μ. Op are replaced by any finite Borel measures v, dv that are absolutely continuous with respect to μ4, 0μ, respectively. This is because such measures have the property that for each 61 > O there is 82 > 0 such that v(A), (B( < 51 whenever ((A)),u(BB) < 62 (Folland 1999 Thm 3.5).
Remark 8. Many practical algorithms for autoencoders, such as the one used to compute the example in $ altempt. to minimize a least-squares loss, in contrast to the supremum norm loss that Theorem guarantees. In private communication, Dr. Joshua Batson pointed out to us that, as a corollary of Theorem ! also guarantee a global L loss. We next develop the argument sketched by Dr. Batson.
one can
Theorem | implies that, for any finite Borel measures v and dv that are absolutely continuous with respect to j and 0p, respectively, the (v) and (3vv)) losses
J K
[G((F()) 211 dv(x) and / [[G(F(z)) =1|² ddv(x) J8
can be made arbitrarily small. To see this, first note that G can be modified off of F(K) \ Ko) so that the modified G maps IR* into the convex hull of {a R"; dist(z, K) < 28}, and the diameter of this convex hull is smaller than the diameter of K plus 4s. Thus, the 7 loss
max [G(F(z)) x|| < diam K + 4s
(2)
zEK
is smaller than diam K + 4s. This and imply the pair of inequalities
[[G(F(x)) x11² dv(x)) < (diam K + (<)o)((K)))))) + +²²v(K)
Jak [[G(F())) - =11 ddv(x) < (diam K + 0v) n OK) + =OOv(OK).
Since both right sides + 0 as d,s 0 by the same measure theory fact in Remark 7 Folland 1999
Thm 3.5),
this establishes the claim. The claim seems interesting in part because the loss N Cisi ((F(),)) - xx| typically used to train autocncoders converges to the (²² loss N + with probability under certain assumptions on the dala ,I,...,INN E K. Namely, convergence occurs if the dała are drawn from Borel probability measure y and satisfy a strong law of large numbers, which occurs under fairly general assumptions on the data (they need not be independent) (Doob) 1990. Thm X.2.1), (Andrews) 1987 p. 1466),
Poötscher & Prucha, 1989 Thm 1, Thm 2). However, Theorem 2 in $ implies that the L loss cannot be made arbitrarily small in general.
3 Numerical illustration
We next illustrate the results through the numerical learning of deep neural network autoencoder. In our example, inputs and outputs of the network three-dimensional, and the set K is taken to be the union of two smoothly embedded submanifolds of R3, The first manifold is unit circle centered at x y = 0 and lying in the plane 0. The second manifold is a unit circle centered at = 1, z = 0 and contained in the plane = 0. See Figure 2 (left).
The choice of suitable neural net architecture "hyperparameters" (number of layers, number of units in each layer, activation function) is a bit of an art, since in thcory just single-hidden layer architectures (with enough "hidden units" or "neurons") can approximate arbitrary continuous functions on compacts. After some experimentation, we settled each, and similarly for the decoding layers. The activation functions functions, except for the bottleneck and output layers, where we pick simply lincar functions. Graphically this is shown in Figure 3 An appendix lists the Python code used for the implementation. We generated 500 points in each of the circles, and used 5000 epochs with a batch size of 20. We used Python's TensorFlow with Adaptive Moment Estimation (Adam) optimizer and a mean squared error loss function. The resulting decoded vectors are shown in Figure right).. Observe how the circles have been broken to make possible their embedding into 1
architecture with three hidden layers of encoding with 128 units
ReLU (Rectified Linear Unit)

---

Published in Transactions on Machine Learning Research (02/2024)
1
1
0.5
0.5
0
0
-0.5
5
005
-1
z
55 200
5
0.5
1
-1
0
-0.5
-0.5
0.5
0
H
0
0.5
5
0.5
15
X
1
1
Figure 2: Left: Two interlaced unit circles, one centered at = y 0 in the plane 0 (blue), and another centered at 1, 0 in the plane and x0))= = (1 + cos( 0, sin())) respectively, with 0 E [0, 2T). Right: The output of the autoencoder for the two interlaced unit circles, one centered at I = 0 in the plane = 0 (blue), and another centered at 2 = 1, 2 = 0 in the plane y = (red). The network learning algorithm automatically picked the points at which the circles should be "opened up" to avoid the topological obstruction.
(red). The circles are parameterized as xx() (cos((),sin(()) sin(
Figure 3: The architecture used in the computational example. For clarity in the illustration, only 6 units are depicted in each layer of the encoder and decoder, but the number used was 128.
The errors [[G(F(z)) æ|| on the two circles are plotted in Figure Observe that this error is relatively
small except in two small regions.
Component
Component
1.30
0.0
623
130
200
403
500
100
330
400
550
Figure 4: The errors [[G((())) - x|| on the two cirles. The z-axis shows the index k representing the kth point in the respective circle, where 0 = 2/000
In Figure we show the image of the encoder layer mapping as a subset of R2 as well as the encoding map F.
It important to observe that most neural net learning algorithms, including the one that we employed, are stochastic, and different executions might give different results or simply not converge. As an illustration of how results may differ, see Figures and

---

Published in Transactions on Machine Learning Research (02/2024)
0.24
Ectienacc Appat
Ectienec: Ponts
Betronnce Nob
barkrech Parts
-03
0.00
-15
Excoded
The bottleneck layer, showing the images of the blue and red circles. Middle and Right: The encoding maps for the two circles. The x-axis is the angle in a 2 parametrization of the unit circles. The y-axis is the coordinate in the one-dimensional bottleneck layer.
Figure 5: Left:
1
0.5
0.5
0
0
00.
5
005
-1
z
005
1
0.5
0.5
005
0.5
0
1.5 1
0
0.5
0.5
1.5
x
1
Figure 6: Left: Showing again the two interlaced unit circles. Right: For different run of the algorithm, shown is the output of the autoencoder.
Componen: ennr
Component eetor
3.5
186
1.0
0.50
w
008
30
Figure 7: Result from another run algorithm. The errors [G(F(z)) æ|1 on the two circles. The æ-axis shows the index i representing the kth point the respective circle, where f 2xk/500.
4 Theorem 1 cannot be made global
Theorem 1 asserts that arbitrarily accurate autoencoding is always possible the complement of closed subset Ko C K having arbitrarily small positive intrinsic measure. This leads to ask whether that result can be improved by imposing further "smallncss" conditions on Ky- For example, rather than small positive measure, can one require that Ko has measure zero? Alternatively, can one require that Ko is small in the Baire sense, i.e. meager (BB3) In either case, the complement K Ko of Ko ability to arbitrarily accurately autoencode K ( Kn as in Thoorem [ would imply the same for all of K. This is because continuity implics that the incquality (1] also holds with Ko replaced by its closure cl(K') Ko), and cl(K) \ Kn) K if K Kn is dense in K.
would be dense, so the
8

---

Published in Transactions on Machine Learning Research (02/2024)
Betllernck
Lettenak Aone
auttered Pains
0.3
Betbvesk Nat.
Croske Crocann tbs con.orrrees
1.4
0.30
4.00
Aggl
agga
Figure 8: Result from another run of algorithm. Left: The bottleneck layer, showing the images of the blue and red circles. Middle and Right: The encoding maps for the two circles. The r-axis is the angle 0 in 2x parametrization of the unit circles. The y-axis is the coordinate in the one-dimensional bottleneck layer.
The following Theorem eliminates the possibility of such extensions by showing that, for broad class of K, the maximal autoencoder error on K bounded below by the reach rxK 2 0 of K, a constant depending only on K. Here тк is defined to be the largest number such that any x R" satisfying dist(x, K) < тK has unique nearest point on K (Federer) 1959 Aamari 2016 2018 Figure illustrates this concept.
2019 Berenfeld et al. 2022 Fefferman et al.
Figure 9: Left: Illustration of reach. A one-dimensional submanifold K of R² shown in blue. Two segments are drawn normal to K, starting at points P and Q in a non-convex high-curvature region. These segments intersect at a point R and have length тк. If perturbations of P and Q lead to R, then there is way to recover P and Q unambiguously as the unique point nearest to R. The dotted line represents points at distance тK from K. Right: Illustration of "dewrinkled" reach: here K (in green) is a "dimpled circle" of radius 1, with a "dimple" which is a semicircle of radius E = O, and L is the "ironed circle" of radius 1 in which the wrinkle has been removed. The mapping T - K is the obvious projection. In this example, TK = E but Fk 11-811
Remark 9. The example K = (0) (1/n: n E N) C R shows that compact subset of Faclidean space need not have a positive reach rk 2 O. However, rK > 0 if K is compact smoothly embedded submanifold (cf. below).
Theorem 2. Let k E N and K C R. be k-dimensional compact smoothly embedded submanifold. For any continuous functions F: R - & and G: R - IR"
max [G((())) - x 0. иEK
(3)
Remark 10. The ability to make Ko small in Theorem relics on an autocncoder's ability to produce functions G that change rapidly over small regions. E.g., if G o F is Lipschitz then Theorem implies a lower bound on the size of Kg in terms of тK and the Lipschitz constant.
To prove Theorem 2 we instcad prove the following more general Theorem 3. because the proof the same. Here H₂ Zz) denotes the k-th singular homology of a topological space S with coefficients in the abelian group Z2 = 2.27 (Hatcher) 2002 p. 153). Upon taking I. = R$ for the latent space, the statement. implies
9

---

Published in Transactions on Machine Learning Research (02/2024)
Theorem 2 since H,(K; 22) Zn + 0 when K is compact manifold (Hatcher 2002 p. 236). Recall that 7
denotes the reach of K _ IR.. See Appendix B B.4 for discussion of the topological concepts and results used in the following proof.
Theorem 3. Let k n N. K C R be compact subset, and L be noncompact manifold of dimension less than or equal to k. If (x(K; + O, then for any continuous maps F: K + and G: R";
max [G(F(z)) - 21| zrk. JEK
(4)
Proof. Let K S R" be compact subset and L be noncompact manifold of dimension most k. Since holds automatically if rx 0, assume TK > 0. We prove the contrapositive statement that failure of (4) for some F, G implies that Hz(K; = 0. Thus, assume there are continuous maps F, G such that
max [IG(F())) - æ|| < rrk.
This implies that
G(F(K)) (K) = {a R"; dist(x, K) < Trg.
Since for each I E Nrx the optimization problem mingek dist(r, v) has a unique minimizer y, = p(x); p: New (K) - K is a contimuus retraction (plx = idx). The line segment from x E to G(F(x)) is contained Nrx (K); since for L E [0,
(ist((G(F())) + (1-,), s [IG(F())) + (1 --==)(=)))) =l1 s [[G(P()) - xl1 < rk-
Thus,
(t, ((G(((()))))))))))))))))
t)x)
defines homotopy [0, K K from idx to (p G F)lx: K K. Defining the open set U R containing F(K) to be the preimage U = G rk (K)), homotopy invariance (Hatcher 2002 Thm 2.10,
p. 153) implics that the induced homomorphism Hatcher 2002. p. 111)
(ooGoFlk). = p. (Glu), o F.: (k(K:2)) - Hx(K;
is equal to the identity homomorphism (idx). induced by idg. On the other hand, the homomorphism (Glu),: (U;) - H& (K):
is zero, since U is a noncompact manifold of dimension S k, and (U; = 0 for any such U (Hatcher 2002 Prop. 3.29, Prop. 2.6). Thus, H2 Z2) = O. This completes the proof by contrapositive.
The reach is globally defined parameter, and thus our lower bound on approximation error may underesti- mate the minimal possible error. In a private communication, Dr. Joshua Batson suggested that the authors consider an example such as the one shown in Figure 9 righht) and attempt to prove a better lower bound for such an example, which led us to improve the necessary statement as follows.
For any compact subsets K and L of R", denote by C(K, L) the set of continuous mappings T: K, and define the maximum deviation of T E C(K, L) from the identity
5(T)
max [Ty) -V1
DEL
We denote by Mn,k the set of all compact smoothly embedded k-dimensional submanifolds L of R". For any compact subset K C R", and any ls E N, we define the k-dimensional dewrinkled reach as
rkk =
sup LEMa TEC(KL))
{rl-8(1) - ((T))
When K Mn,k, we have that rk. 2 Fk (use L K and T identity). However, rk may be much larger than rx (see Figure g right))).
10

---

Published in Transactions on Machine Learning Research (02/2024)
Corollary 1. Let n N and K _ R" compact subset. For any continuous functions F; R" - R and G: R + R"
max TER
max]|G(F[a)) x|| 2 Tk
(5)
Proof. Pick L E Ma and T E C(K,L) and consider the composition F; F FoTT - RR k - F(T(v))
--
Applying Theorem 3 to L and the maps F: + F and G: R + R", we may pick a n L so that ||v - G(F())) 2 TL. Let { : T(n), so G(F(n) G(F(T()) = G(F(E)). Then
- G- = G(F(E)) = - T())) + G(F(e))
so
Tz S 1n1 G 1n
- T())l - G - 8(T) + G(F(E))
and hence
max (Fx[ =11 2 l|g G(F(E)) n 8(T)
=EK
This is valid for all (L, and thus max,ek (G(F(z)) - | rk as claimed.
Remark 11. All the results in this section were stated for manifolds, meaning (recall our convention) manifolds with empty boundary. Clearly, the same results cannot be valid for manifolds with non-empty boundary. For example, the submanifold with boundary of I consisting of a one-dimensional segment in the z-axis has infinite reach yet can be perfectly reconstructed (project onz-axis and then include in R?)..
5 Discussion
Our main representation result is Theorem ! This theorem theoretically insures that data points lying in submanifold K (or even in a finite union of submanifolds) of given dimension & can be encoded through a bottleneck layer of the same dimension k, up to an arbitrarily small uniform reconstruction error Moreover, the generalization error will also be uniformly smaller than e, with arbitrarily high probability 1-8, when points are randomly sampled from K. Our main necessity result is Theorem 2 This theorem complements the representability result by providing a lower bound for global uniform reconstruction. On the other hand, as discussed in Remark one can guarantee global reconstruction with error less than in a mean least squares sense.
There is a vast amount of experimental work using auloencoders for dimension reduction, but comparatively few papers focus on a theoretical basis for such reductions. One theoretical result is given (with no proof) in Hicht-Niclsen (1995), in which a thcorem is stated for replicator neural networks (with quantized middle hidden layer activations approximating the function 0(r) for r < O, 0(r) = for r > and 0(r) = r for r E [0, 1]). Using our notation, the theorem claims roughly that if data belongs to set K which is the image of smooth embedding of a k-dimensional unit cube, and probability measure is given on K, then, in the limit of high dimensions (A + oo) and large number of quantization levels, replicator networks trained to compute optimal encodings will recover the natural (entropy) coordinates in the data manifold. Our Theorem I in contrast, studies representations of data lying in rather arbitrary manifolds (and would indeed be quite trivial if K was already assumed to be diffeomorphic to a cube), and is valid for arbitrary k, not merely asymptotically.
Regarding the limitations of autocncoders as reflected in our lower bounds for global reconstruction, the authors of [atson al. (2021), in the context of anomaly detection in high-energy physies, argue that autoencoders might miss falsely detect anomalies due to the topological shape of the phase space. Our necessity result Theorem serves to quantify these obstructions.
Theorem provides an existence result. As is often the case with results regarding the expressive power of neural networks, effective learning during training involves overcoming numerous challenges. This is because the landscape of the loss function (whether I or any other criterion) typically highly non-convex and irregular, presenting spurious local minima, plateaus, and potentially steep ravines, leading gradient- based optimization methods to converge to local minima or navigate through saddle points inefficiently, thus
11

---

Published in Transactions on Machine Learning Research (02/2024)
failing to find a low-error autoencoder. Moreover, the choice of optimizer and network architecture and hyperparameters will affect the success of numerical methods. Finally, for sparse training samples from K there is little hope of effective generalization to the full manifold K in the absence of proper regularization of the loss function.
There are many possible directions in which we will be expanding our study. One of them is the extension to model reduction for time series data, for which there are many existing approaches including for example dynamic mode decomposition (Kutz et al. 2016) and deep learning dynamic mode decomposition (Alford- Lago et al. 2022). Specifically, one may assume that a vector field, the data manifold K. The objective then becomes that of dcfining a dynamics in the bottleneck layer that intertwines with the original dynamics in K, thus providing a reduced-order representation of the original dynamics, in the spirit of the computational approach in Baig et al. (2023). . Further along this direction, one may consider control systems (thought of as families of vector fields), and the reduction to lower-dimensional control problems in the same fashion.
iteration in cescrete-time, exists
A related direction of study concerns representation of dynamics through the "Koopman" approach, in which the middle-layer dynamics are linearized. Theoretical results characterizing the limitations as well as possibilities of Koopman embeddings are given in Liu et al. (2023); Kvalheim & Arathoon (2023). In this context, the middle dimension is often larger than the input dimension, rather than smaller, but on the other hand linearity imposes a different type of simplification. Autoencoder realizations of Koopman embeddings
have been suggested in the literature, see for instance Otto & Rowley (2019); Azencot et al. (2020). We will extend the theory to establish when Koopman autoencoders exist, and their limitations. In parallel or in combination with these dynamics ideas, if our manifold K comes endowed with particular probability measure, we may ask to represent this measure through the bottleneck, as a distribution on latent variables, which is a topic closely related to variational autoencoders.
Yet another direction of research is that of understanding to what extent latent representations can mirror, or not, global topological, metric, and combinatorial features of data manifolds, adapting and extending the recent work Wang el al. (2023) that dealt with the unavoidable distortions that arise from low-dimensional representations, especially in the context of systems biology single cell data.
Finally, another direction of study concerns the generalization of our representation result Theorem from unions K of submanilolds with boundary to unions of more general stratified sets [Trotman 2020 Def. 1.11).
A manifold with boundary is an example of a stratified set with two strata, namely, the codimension-0 interior and codimension-1 boundary. Most of the conclusions of Theorem [ are "stratified" in the sense that the conclusion 0p(K, (āK) < 8 for the codimension-1 stratum the analog of the conclusion μu( (()))= < 8 for the codimension-O stratum, and the conclusion (1) directly implics the analogous conclusion with K replaced by 0K. However, Theorem ] contains no statement on connectedness of (0M) \ Ko analogous to the conclusion of Theorem | that M \ Ko is connected for each component M of K. It seems interesting to know whether this analogous statement generally holds, and moreover whether Theorem generalizes to useful class of stratified sets in "fully stratified" way. For example, suitable genoralization of Theorem to Whitney stratified sets (Trotman 2020 Def. 1.2.3) would imply a representation theorem for auloencoding of algebraic varieties and more generally subanalytic sets, since these admit Whitney stratifications (Trotmann 2020) p. 5). Algebraic varioties arise naturally as the sets of stcady states of mass-action biological systems, and finding parametrizations of steady states is a key problem in fitting models to data. In the special case of varieties defined by toric ideals, global parametrizations are possible (Chaves et al., 2004]; but in more general cases, particularly when analyzing single-cell data, equilibrium sets are only known numerically (Wang et al. and autoencoders might provide a useful approach to the estimation of dimension.
2019
Acknowledgments
EDS's work was partially supported by grants ONR N00014-21-1-2431 and AFOSR FA9550-21-1-0288) The authors thank the reviewers for insightful comments, and especially thank Dr. Joshua Batson for his obser- vations that led to Remark g and to Corollary I
12

---

Published in Transactions on Machine Learning Research (02/2024)
References
E Aamari, J Kim, F Chazal, B Michel, A Rinaldo, and L Wasserman. Estimating the reach of a manifold. Electron. J. Stat., 13(1):1359-1399 2019. ISSN 1935-7524. doi: 10.1214/19-cjs1551 URL httpp:://dooi
D. J. Algord-Lago, C. W. Curtis, A. T. Ihler, and O. Issan. Deep learning enhanced dynamic mode decompo- sition. Chaos: An Interdisciplinary Journal of Nonlineur Science, 32(3))03311 03 2022. TSSN 1054-1500. URL
doi:
1003/00000003000 1008/
D W K Andrews. Consistency in nonlinear econometric models: generic uniform law of large numbers. Econometrica, 35(6):1465-1471, 1987. ISSN 0012-99622,1488-2222. doi: 10.2307/1913560 URL https:
7/doi org/10 2307/1913568
O Azencot, N Erichson, Lin, and M Mahoncy. Forceasting sequential data using consistent Koopman auloencoders. In Hal Daumé III and Aarti Singh (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 475 485. PMLR, 13-18 Jul 2020. URL https: https::/ http:s:://ppoceedngg.... .ml. /ttp://oeaiiig.......rrre///////
html Y. Baig, H. R. Ma, H. Xu, and L. You. Autoencoder neural networks enable low dimensional structure analyses of microbial growth dynamics. Nalure Commumications,, 14(1): Dec 2023. ISSN 2041-1723. doi: 11008//44467-0222 023-4445--0. URL https::/ 1ttp:///1111001//1116660-2222220 43455-0
A Barron. Universal approximation bounds for superpositions of sigmoidal function. JEEE Transactions on Information Theory, 39(3):930 945, 1993. doi: 10.1109/18.256500.
Batson, C G Haaf, Y Kahn, and D A Roberts. Topological obstructions to autoencoding. Journal of High Energy Physics, (4) Apr 2021. ISSN 1029-8479. doi: 10.1007/JHHP00((222)330 URL bttpss//dol org/ 10. 1007/ (2220)))))44422))20200
C. Berenfeld, J Harvey, M Hoffmaan, and K Shankar. Estimating the reach of manifold via its convexity defect function. Discrete Compul. Geom., 67(2):403 438, 2022. ISSN 0179-5376, 1432--444,, doi: 10.1007/ 5004544-021-00290-8 &. URL httpss://oii 000000000000000000000000000---00
M M Bronstein, J Bruna, Y LeCun, A Szlam, and P Vandergheynst. Geometric deep learning: going beyond Euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
M Chaves, E D Sontag, and R J Dinerstein. Steady-states of receptor-ligand dynamies: A theoretical framework. J. Theoret, Biol. 227(3):413 428, 2004.
G Cybenko. Approximation by superpositions of sigmoidal function. Mathematics of control, signals and systems, pp. 303 314, 1989.
M Donahue, Gurvits, C Darken, and E D Sontag. Rates of convex approximation in non-Hilbert spaces. Constr. Approz., 13(2):187 220, 1997.
J L. Doob. Stochastic processes. Wiley Classics Library. John Wiley & Sons, Inc., New York, 1990. ISBN 0-471-52369-0. Reprint of the 1953 original, A Intes--nte Publication.
R Eldan and O Shamir. The power of depth for feedforward neural networks. In V Feldman, A Rakhlin, and O Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Tearning Reseorch, pp. 907-940 940, Columbia University, New York, New York, USA, 23-26 Jun 2016. PMI.R URL https://proceedinng mlr press/v49/eldanil html
H Federer. Curvature measures. Trans. Amer. Math. Soc., 93:418 491, 1959. ISSN 0002-9944,10888-65557 doi: 10.2307/1993504 URL https://aoi.org/// http///0..377/993300
C Fefferman, Mitter, and H Narayanan. Testing the manifold hypothesis. Amer. Math. Soc., 29(4): 083-1048 2016. ISSN 1894-0347.1088-6887 doi: 10.1090/jams/852. URL lnttps://ooi. :ttts:://ao..or/1o...o
j jams/852
13

---

Published in Transactions on Machine Learning Research (02/2024)
C Fefferman, S Ivanov, Y Kurylev, M Lassas, and H Narayanan. Fitting putative manifold to noisy data. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 688 720. PMLR, 06 09 Jul 2018. URL
mlr. wttp://////fffffermmmaa hhmml
C Fefferman, S Ivanov, M Lassas, and H Narayanan. Fitting manifold of large reach to noisy data. Journal of Topology and Analysis, pp. 82, 2023. doi: 10.1422517755252300001
G B Folland. Real analysis. Pure and Applied Mathematics (New York). John Wiley & Sons, Inc., New York, second edition, 1999. ISBN 0-471-31716-0. Modern techniques and their applications, A Wiley-Interscience Publication.
A Hatcher. Algebraic topology. Cambridge University Press, Cambridge, 2002. ISBN 0-521-79160-X, 0-521- 79540-0.
R Hecht-Nielsen. Replicator neural networks for universal optimal source coding. Science, 269 (5232):1180 1863, 1995. doi: 10.1126/sei 10.1126/scciece.222 26tp://eccce.....3655... 1860. URL science wtriccee.69...0 1860
M W Hirsch. Differential topology, volume 33 of Graduate Teats in Mathematics. Springer-Verlag New York, 1994. ISBN 0-387-90148-5. Corrected reprint of the 1976 original.
K Hornik, M Stinchcombe, and H White. Multilayer feedforward networks are universal approximators. Newral networks, pp. 359-366, 1989.
L K Jones. A simple lemma on greedy approximation in Hilbert space and convergence rates for projection pursuit regression and neural network training. Ann. Statist., (0(1):608-613, 1992. URL http://dm dml
mathdoc. frrrbo..fr/ttemm/176445553
D E Koditschek and E Rimon. Robot navigation functions manifolds with boundary. Adv. in Appl. Math., 1144)4412-44, 1990. ISSN 1199-8888,1090-2200 doi: (0000000000110000055000000000090 (000//011..-888800090001... URL https: //doi.org/10 1011://1111000016--88888000 (8))
J. N. Kutz, S. L. Brunton, B. W. Brunton, and J. L. Proctor. Dynamic Mode Decomposilion. Sociely for Industrial and Applied Mathematics, Philadelphia, PA, 2016. doi: 10.1137/19781611974550
M D Kvalheim and P Arathoon. Linearizability of flows by embeddings. orXiv preprint arXiv:2305.18288 pp. 1-20, 2023.
M Lee. Introduction to smooth manifolds, volume 218 of Graduate Texts in Mathematics. Springer, New York, second edition, 2013. ISBN 978-1-4419-9981-8.
M Lee. Corrections to introduction to smooth manifolds (second edition). 2024. Accessed: 2024-01-23.
https://sites. math.
washington. http://atweeeeeee/o////////////e
Liu, Ozay, and E Sontag, On the non-existence of immersions for systems with multiple omega-limit sets. In 22nd IFAC World Congress, IFAC-PapersOnIiine, volume 56, pp. 60 60-64, 2023.
P W Michor and C Vizman. n-transitivity of certain diffeomorphism groups. Acta Math. Univ. Comenionae, 63(2):221-22 225, 1994.
F. Otto and C W Rowley. Linearly recurrent autoencoder networks for learning dynamics. STAM Journal on Applied Dynamical Systems, 18(1):558 593, 2019. doi: 10.1137/18M117788
A V Pajitnov. Circle-valued Morse theory, volume 32 of De Gruyter Studies in Mathematics. Walter de Gruyter Co., Berlin, 2006. ISBN 978-3-11-015887-6;; 3-11-015807-8 doi: 10.1115/0783110197777 URL https://doi. 10. http///0..111////1110999999
B M Pötscher and R Prucha. A uniform law of large numbers for dependent and heterogencous data processes. Econometrica, 57(3):675-683) 683, 1989. ISSN 2012-9682,1468-02222 doi: 10.2307 0-23077/9110558 19110858. URL
http:://bbl.orr//0.20////111111
14

---

Published in Transactions on Machine Learning Research (02/2024)
T Sakai. Riemannian geometry, volume 149 of Tronslations of Mathematical Monographs. American Mathematical Society, Providence, RT. 1996. ISBN 0-8218-0284-4. doi: 10.1090/mmoon /mm//o/mmm/..9 URL
Translated from the 1992 Japanese original by the author.
E D Sontag. Feedback stabilization using two-hidden-layer nets. IEEE Trans. Newral Networks, 3:981-990, 1992.
Telgarsky. Benefits of depth in neural networks. In V Feldman, A Rakhlin, and O Shamir (eds.), 29th Annual Conference on Learning Theory, volume 49 of Proceedings of Machine Learning Research, pp. 1517-1539, Columbia University, New York, New York, USA, 2016. PMLR.
D Trotman. Stratification theory. In Handbook of geometry and lopology of singularities. 1, pp. 243 273. Springer, Cham, 2020. ISBN 978-3-030-53060-0 978-3-030-53061-7 doi: 1111007/978--000-530000 __ URL https://doi.org 10. 0000100777777---0---------------
S Wang, J-R Lin, E D Sontag, and P K Sorger. Inferring reaction network structure from single-cell, multiplex data, using toric systems theory. PLoS Compulational Biology, 15:e1007311, 2019.
S Wang, ED Sontag, and D A Lauffenburger. What cannot be seen correctly in 2D visualizations of singlo-cell 'omics data? Cell Systems, 14:723 731, 2023. URL https:///6o..rr//10..0
cels. 2023. 07.007.00000 002
F W Wilson, Jr. The structure of the level surfaces of Lyapunov function. J. Differential Equations, 3:323 329, 1967. ISSN 0022-0396. doi: (016/0022-0399(67)))))))) 90035--)
URL http: dtoddxxxoooiii.///oooooooooo.doo org/10.
15

---

Published in Transactions on Machine Learning Research (02/2024)
A Appendix: Code used for implementation
Doomany_points 500
epochs 5000
batch_size sich_sizee_ 20
import matplotlib. pyplot as plt import plotly graph_objects go import pandas as pd import numpy np
import acipy as
import tensorflow from tensorflow. keras layers import Input, Dense from tensorflon.... keras models import Model
Define the parametric equations for the circles def circle_xy(t, h, r):
+ ct)
k sin(in(t)
2 0 opes_ieeeike x, y,
def circle_yz(t, h, r): x h + * sin(in(t) y np. op.ones_like (t) k cos(((
return x, y.
np. lipepacaccee (0, np.pi, howmany_pointa
x1, yl, 21 circleexy(e xt,,, 0, 0, 1)
x2, y2, circle_yz(t, 0, 1)
input_daaa data np. www.sttakkkkk (mp. collun_stacceeeeeccoooooooooacce column stack((x2, (ol.unn_tttcc((122 y2, 22))))
y1, z1)),
Build the autoencoder architecture with bottleneck layer of dimension input_data dataaatstttttaaaeeeeaaeeesaaaaae vptackac
( (wpp.olumm, sttssttttc(xtttt,. yitest, zitest)), A np. colcmmmmn stack stack (x2test, y2test, 22test))))
input dim
Encoder model
input_layer Input (shape=
encoded Dense "etivationn'relu")) (encoded)
'rrivattionnrelu')) (input_layer) _laeer)
encoded Dense (128,
encoded Dense (128, activation='relu)) (encoded)
encoded (ense(1, activation='linear (encoded) Bottleneck layer with dimension
encoder Model (inputttt----ppttlllyyr outputs=encoded)
Decoder model
decoded input Input (shape=(1,)) (1,))
decoded Dense (128, activation='relus (decoded, input)
decoded D128e(128, activatioo='reelu") (decoded)
decoded Dense(128, activation='relu! (decoded)
decoded Dense
inlivattoon'linnar (decoded)
decoder Model (inpute-decoded input, outputs=decoded)
Autoencoder model
autoencoder Model (inputs=input_layy layer, (utp
16

---

Published in Transactions on Machine Learning Research (02/2024)
autoencoder wwwp:lcmmpiiccccccccc cotpp/ddee...mpppilppppppiiiiioo 'ddmm', loss= mean, meas=rreanssuuureddee squaredderroo error')
autoencoder.fitt(iuuuu _ata, input_datas data, epochs=epochs, batch_aize-batthh.e sizeeebbhccchhizze shuffle=True)
Test the autoencoder on the training data
encoded_vecten vectors encoder prediit
secoded_vectors = decoder, (rnoodrr.pprddccctcmcdddddddddd
secooed_vecttore =
decoded_vectorse woreetttrrrotoooomaaooooiiittttt
seroodedveector.... decoded _ecctdr wtwommmay_ooottss.._...
aacoded_vectorse = encoded_vectaie vectors [0: pootaayyppointss
encoded_ vectorr__ aucoded_vectore
Create the 3D plot of data vectors in plotly figl Fo.urer
Add circles to the plot
tigl. trace (o..eeggg.ctteerddd.......
y=yl, z=z1, mode= "aide''
name='unit circle centered at x=0, y=0 in the plane z=0', 1ineddictwwidthhe) figi. teacetracceeee (ra (gg.Scaatterd(xxxx) yry2, z=z2, mode='lines', umit umit circle centered at x=1, z=0 in the plane y=0', limendict () Setting the axis labels zoom 2.5
figl.update laleeallatttt (scene_ aatpameccccceredccoooooorrtttea y=zoom, )==oom))) zoom plot fits figl.shov() htgg../rttt...maeppstaaaaaaaaaee
iit.riiiggnnntaaaarrrrrrrriiaaaa #this works with plotly
serrit_imaaeeee
fig2 Figure)
(ewrraerrrddddddeeeeeeeeerrs__sd 0], prdecoded_vectorr___ vectors__l; 1], z=decoded_ vectors_ttrsieeeee 1[;,2],
mode- 'makerrs' (sizoro name- decoded unit circle centered at x-0, y-0 in the plane z=0'))
arg bra.cegg..Scatteeeacceeaoao
Scatter3d veectteeeeddodeeeeeeeeeetorrorss rectors_2[i, o], y=decoded, seeeoode_eeettrr...oo vectors__2e 1], z=decoded_vectors vectors 2[: 2],
mode='markers' (arzer=)icttsize=:)) name='decodesr unit circle centered at x=0, y=0 in the plane z=0)))
zoom
wwwpuuppdaappeeeee fig2.show()
http::/wwppooooaocccmcccacaccaaa (x=zoom, y=zoom, 2=zoom))) # zoom plot fits
fig2. write, sesste_imaeeepee .maaggoppttatriiveedddooddddl png") #this works with plotly
fig2. wwwtwwiiteeeee. caceeeimageeee
Create again the 3D plot of data vectors in plotly but use different view in 3 and 4 belor: fig3 Figure))
Add circles to the plot
fig3, trace trace (gw.....teerddxeett..... y=y1, z=z1, mode= mode='lines' lines', A name=/umit circle centered at x=0, y=0 in the plane z=0', linerdict (ine-dict(riidt==e))
fig3.add, trace Scatterttrrrd (x=x2, y=y2, z=22, mode='lines', name=Punis circle centered at x=1, z=0 the plane y=0', line=dict (width==))) Setting the axis labels
(scene=dict (xaxis titlssttttee''' yaxis_ Y zaxis zaxis_titlin firia_tttle=/Z')
fig3.updee
to convert spherical elev=30, azim=65 to cartesian, one uses
math. cos (azim_rad)) = math. cich.cos(elee_rral math. (azim_rad)
math.cos(elev_ei)
math. sech.sin(elevrrar
so I get with r=1: 0-6.66 786, 2=0.5 zoom
fig3 update_ (scene (ct.eeeecccmmrrrrddcceepeeeeedee 2=20om+0.5))
y=zoom=0.785,
17

---

Published in Transactions on Machine Learning Research (02/2024)
different view angle zoom ao plot fits
fig3 write cetstte_mmgeepattte htwpg//gppaaaiiieooorrrraiaaaaaa #this works with plotly
fig3.write perite_magee hwwpa//mmggggpaaahaar/rorrrraaaa
fig4 Figure aud__dd___ree wow. Scatter3 weg.eatttrrrrrddddddddoeooooooss 0], y=decoded_ veltorrsl 1
z=decoded_ vectors_1l 2] mode='markers', (siter-= \\ decoded
name= decoded unit circle centered x-0, y=0 in the plane 2=0²)) fig4.add agg_.add_trace(gg Scatter3d (xxotereeeededdddeeeeeeoeooo vectorr__ettt._... 0], y=decoded_ 1
(sieerd name- + decoded unit circle centered x=0, y=0 in the plane z=0²))
z=decoded_ vectors_2[: ,
figa.update,
ueddutt_t___ayoutttoooo layout (sceme=dict (xtitteeeetttti.iiittttttteee fiitl==''' Doxis_title='yy Y maxis_title== (Z))
layout cameeeearrrrdddcccyyeeee (x=zoom#0. y y=20om+0.785, 2=20om+0.5)) zoom out so plot fits
fig4. show((
fig4. wwrit__imgeepaatdriiii
png") #this works with plotly
fig4. write_ crrite_imaeeie weg.iiiagggaaete (wwthhddiee=""dccodeeeeee
Plot the bottleneck points
vectorss__ mp. ap-zeros_like (eroo__ottccccdddddeeecorr__
marker='o', Iobtl='oott Points', color='b')
up.zeros_lie _ike (encoded_ vecooddd__eetttr________
marker='x', label="Bottleneck Points', color='r') plt.xlabel (waaabee((Ennoooa Encoded Dimension')
Stt.cittle/Bottteeeeek Points*)
plt.legend
plt.grid()
plt. wwt.aaviiiicttttrrreeooooteeeeeo aat.tiiht_layoute plt.
# this works with matplotlib but before show
compute matrix norm along second "axis", i.e. along "y axis", i.e. each delta_1 mp.linalg. norm (arpuut____dae data [0 wethhooanppointee :] feadedd_ecttr___, _1, axis 1) delta_2 np. linalg norm (input_ddr))) data [-howmany, poinatss :] ricoded_vectors axis 1)
ptt.ploatdeeta_..
plt. plt. sat.saveiig (parefig(patdriveett "errrriieteerrrtt "error"...
error')
this works with matplotlib but before show sht.show()
plt, plt.plor (delta___
plt. title (' Component error') plt. tet..aaeeiigpathdrvee=eeeree (pathhrrvee"errrr...p.. sho.s
plot the encoded function the angle parameter
plt. scatterrtt pacoded_vectors.. marker='o', label= label='Bottlen Botttennec Points', color='b') xlabel Annlle'
plt.ylabel ( Encoded Dimension (first component) 2)
pit.cittlePBottleneee Points*)
(
plt.grid()
plt,
pht.show()
18

---

Published in Transactions on Machine Learning Research (02/2024)
plt,scatter(t, pacoode__ecttrs_22 2, marker='x', 1abel="Bottleneck Points', color='r')
plt.xlabel (' 'Angle')
plt. ( E'ccoddd Dimension (second component))) ')
tit.titlee Points')
plt.legend
plt.grid()
plt. wawaaaiii(paaatiiieeeeeedoiiaaia
sho.show()
19

---

Published in Transactions on Machine Learning Research (02/2024)
B Appendix: Review of some basic concepts and results in topology
In this appendix we review basic concepts and results in topology that are used in this paper. We discuss general topology in BB. finite Borel measures in B.2 differential topology in $B.3. and algebraic topology in
B.44
B.1 General topology
A topology on set X is a collection of subsets of X, called open, satisfying the following three properties 596):
Lee
2013
X and Ø open.
The union of any family of open sets is open.
The intersection of any finite family of open sets is open.
A set X equipped with a topology is called a topological space.
A subset C S X is closed if its complement X \ C is open (Lee) 2013 p. 596). The closure cI(S) of
subset. S [ X of topological space X is the intersection of all closed sets containing S (Lee 2013 p. 597). Thus, S S X is closed if and only if cl(5) S. A subset $ C X is dense if cl(S) X.
A topological space X is connected if it is not the union of any two disjoint non-empty open sets (Lee 2013, 607). topological space X is compact if, for any collection of open sets whose union is X, there is a finite subcollection whose union is X Lee 2013 p. 608).
Given a subset S S X of a topological space, the subspace topology is the topology on S that declares a subset U S to be open in S if and only if there is subset V X open in X such that U = V V n (Leo 2013 p. 601). A subset S C X is connected if it is connected in the subspace topology, and compact if it is compact in the subspace topology
Lee 2013 pp. 607-608). A (connected) component of X is a connected subset of X that is not a proper subset of any larger connected subset (Lee 2013 607).
A topological space is Hausdorff if any pair of distinct points in X are contained in some pair disjoint open sets, and is second-countable there is countable collection open sets such that every open set in X is union of some open sets from the countable collection (Lee) 2013 p. 600). Every subset of Hausdorff space is Hausdorff in the subspace topology, and every subset of sccond-countable space is second-countable in the subspace topology (Lee) 2013 Prop. A.17). Only second-countable Hausdorff topological spaces appear in the body of this paper.
Example 1 Lee 2203 Ex. A.6)). The standard topology Euclidean space E is defined as follows, A subset U C R" is declared to be open if for cach point E U there is some > 0 such that the ball N,(x) = (y E R": | yll < r is a subset of U. These open sets can be checked to satisfy the three properties above, so they define a topology on R", This topology is Hausdorff since any pair points are contained in disjoint balls with positive radii, and is second-countable, as follows from the fact that every real number may be approximated by rational numbers. The Heine-Borel theorem asserts that a subset of T is compact if and only if it is closed and has bounded diameter [Tee 2013 p. 608).
A map F: X + between topological spaces is continuous if the preimage
F-1 = {ir E X: F(x) E U}
of any open subset of Y is open a homeomorphism if the inverse map F- continuous map F: X + Y is topological embedding if the codomaii--retrricted map F: X F(X) is homeomorphism when the image
X Lee
2013 p. 597). A bijective continuous map F: X - Y is + X is continuous (Lee) 2013 p. 597). An injective
F(X) (F()) CY
20

---

Published in Transactions on Machine Learning Research (02/2024)
of F is given the subspace topology inherited from Y Lee 2013 p. 601).
The product topology on the Cartesian product X x Y of topological spaces X and Y is defined by declaring subset S S X x Y to be open if, for each (x, v) E S, there are open sets U C X and V S Y respectively containing x and y such that x V.
B.2 Finite Borel measures
A subset S S X of a topological space X is Borel set if it can be formed from open subsets via the operations of taking countable unions, taking countable intersections, and taking complements within X (Folland 1999 p. 22). A finite Borel mcasure μ on X is a map from the Borel sets to the nonnegative real numbers such that μ((2 = and v(U=11 S2) = Σ p((},) for any countable family of pairwise disjoint Borel sets S1, ...... S X (Folland 1999 pp. 24 25). A finite Borel measure p on X is a probability measure if ((X) 1.
A map F: X + Y between topological spaces is Borel measurable if (S) is Borel set in X for any Borel set S in Y. For any Borel measurable function f: X + 10, oc) and finite Borel measure on X, there is a well-defined integral fx (x) du((r) E [0, oo] (Folland 1999 50).
A finite Borel measure y on X is absolutely continuous with respect to a finite Borel measure μ on if v(S) = whenever yuS)= = 0 (Folland 1999 p. 88). In this case, the Radon-Nikodym theorem asserts the existence of Borel measurable function f: X + oo) such that
v(S) = { f(x)) f(z) du(z) / (s())(())dp(()
for each Borel set S, where 1s(x) if x S and 1s(x) otherwise Folland 1999 p. 91).
A finite Borel measure on X is outer regular if
p(S) in(() U SUU is open}
for all Borel sets S C X Folland 1999 p. 212).
B.3 Differential topology
A topological space M is an n-dimensional (topological) manifold with boundary if is second- countable, HausdorfT, and for each point x E M there an open set. U S M containing x that homeo- morphic to an open subset (with the subspace topology) of the closed n-dimensional upper half-space Lee 2013 p. 25)
H (101,..., . vn) E R²: In 1 0).
A choice of homcomorphism sp: U + ((U) C H" is called chart (U, for M. We say that the chart (U,4) contains the point x E M if x E U. A point I E M is called interior point if the n-th coordinate of (p() E H" is positive for some chart (U,sp) containing I, and boundary point otherwise. The collection of boundary points is called the (manifold) boundary of M, denoted by 0M, and the complement int(M) = M MM is called the (manifold) interior of M. We say that M is an n-dimensional (topological) manifold if ØM = Ø. (Equivalently, one can define n-dimensional manifolds by replacing H by R" in the definition of n-dimensional manifolds with boundary (Lee) 2013 pp. 2 3).)
A map between open subsets of Euclidean spaces is smooth if it has continuous partial derivatives of all orders. Given an arbitrary subset A C R map F: A - RT is smooth if for each E A there is an open set U C RR" and a smooth map F: U + Rd whose restriction Fluna coincides with Flons (Lee) 2013 p. 645). Given a subset B C TR. we say that F: A + is smooth if F is smooth when viewed as a map into _
Let M be an n-dimensional manifold with boundary. Two charts (U,+), (V. are called smoothly com- patible if either U UnV- Ø the transition map s -t: (UnnV) ((U C RD is smooth (in the
21

---

Published in Transactions on Machine Learning Research (02/2024)
sense of the previous paragraph). A smooth atlas for M is collection of smoothly compatible charts such that the union of chart domains is M. A smooth atlas for M is maximal if it is not properly contained in any larger smooth atlas. A smooth structure on M is a maximal smooth atlas (Lee) 2013 p. 28).
An n-dimensional smooth manifold with boundary is an n-dimensional manifold with boundary M equipped with a choice of smooth structure (Tee] 2013] p. 28). Such an M is an n-dimensional smooth manifold if 0M = Ø. (Equivalently, one can define n-dimensional smooth manifolds by replacing H" by R" in the definition of n-dimensional smooth manifolds with boundary (Lee 2013 pp. 4, 12-13).)
Example 2. Euclidean space R is an n-dimensional manifold. Every I E R" is contained in the domain of the chart (IK", idg=) defined by the identity map. The union of this chart with all charts smoothly compatible with it defines the standard smooth structure R" making it smooth manifold (Lee) 2013 Ex 1.22). Similarly, H" is an n-dimensional manifold with boundary, and a smooth manifold with boundary when equipped with the standard smooth structure consisting of of all charts smoothly compatible with idg.).
Let M, N be smooth manifolds with boundary and A be an arbitrary subset of M. A map F: A - N is smooth if for each I E A there is chart (U, containing x and a chart (V,b) containing F(x) such that F(U) C V and 3 o F Fo o (U n AA) + vV) is a smooth map between subsets of Euclidean spaces in the sense defined above (Lee, 2013 p. 45), (Loo. 2024, p. 1). When N = R and is closed, such an always admits a smooth extension F: M + R", meaning that F is smooth and FlA- = F (Loc 2013 Lom. 2.26).
A smooth map F: M + N is smooth embedding if it is topological embedding and the inverse F-1: F F(M) + N is smooth. (This is equivalent to the usual definition (Lee 2013 p. 85) by the chain rule Lee 2013 Prop. 3.6(b))). A diffcomorphism is a bijective smooth embedding (Lee 2013 p. 38).
Let x be a point in an n-dimensional smooth manifold with boundary M, and consider smooth curves y: J4 + M that are defined on some interval Jr S R containing 0 and satisfy 700) = x. A tangent vector at x M is an equivalence class of such curves, where curves 71. 72 are called equivalent if d (()(()))) = ae (t))ll for some smooth chart (U,4p containing x (Leo 2013 pp. 70, 72). The tangent space T.M at x E M is an n-dimensional vector space that consists of all tangent vectors at x. The tangent bundle of M is the disjoint union TM- == U.eN T&M of all tangent spaces, and it has a canonical topology and smooth structure making it into a 2n-dimensional smooth manifold with boundary
(Lee) 2013 pp. 66 66-67).
A smooth vector field Y satisfying (x)) E T.M for each I E M (Lee 2013 p. 175). A point E M such that (p) = 0 is called an equilibrium (or zero) of Y. A smooth vector field is inward- praardpoinning if for each x E 0M there is a curve in the equivalence class defining (x) that is defined on an interval of the form [0,e) Leo 2013 p. 118).
smooth manifold with boundary M is a smooth map Y: M + TM
When M is compact, an inward-pointing smooth vector field Y on M canonically determines a smooth map @: [0, oo) x M + M such that the time-t maps d' = (t,--) are (dimension peariiioonnpeeeeiigggg smooth embeddings satisfying Φ0 = idas and g++s = Φh t- for all t, 2 0. This semiflow & is the unique such map with the property that each trajectory + (x))(x) belongs to the equivalence class Y( (z)). (One constructs t
by repeating, mutatis mutandis, the proof of Lee 2013 Thm 9.16) for the case δM = Ø; cf. Lee 2011 Thm 9.34)).
When p E . is an equilibrium of an inward-pointing smooth vector field Y with solution map $ ('(p) = for all 2 The cquilibrium p is called hyperbolic if none of the cigenvalues of the Jacobian matrix D(po ((po@boop-))( ((((() have complex modulus equal to 1, where (U,yp is a chart containing p. The equilibrium p is called asymptotically stable if for every open set V S M containing p there is an open set U C V containing p such that, for each g E U, the the trajectory f ('()) takes values in V and converges to p as Pajitnov 2006 p. 74). The basin of attraction of an asymptotically stable equilibrium E M is a connected open set consisting of all E M such that the trajectory (+ t' (q) converges to p.
+ 0
A Riemannian metric g on smooth manifold with boundary M an inner product (Y,, Z,) + (V,, Z,) on each tangent space T.M such that + gY (z), (z)) is a smooth map for any smooth vector fields Y, Prop. 12.19, pp. 327-328). Tn particular, Riemannian metric determines smooth
Z on M. (Lee 2013
22

---

Published in Transactions on Machine Learning Research (02/2024)
gradient vector field Vp for each smooth function yp: M - R Lee 2013 P. 342). If : M - [0,1] is
smooth and aM = (1), then Vy is invard-pointing.
A Riemannian metric on a compact smooth manifold with boundary M also determines an entity, called the Riemannian density [ee 2013 Prop. 16.45), that can be integrated over Borel measurable subsets of M (cf. Lee (2013 p. 431)) to define finite Borel measure yu on M that is outer regular (9..2), Folland (1999) Thm 7.8). A Borel set A S M is called measure zero if μ(A) = O. By construction, changing the Riemannian metric changes μ to finite Borel measure such that μ., V/ are absolutely continuous with respect to each other, the property of being measure zero is well-defined independent of the choice of Riemannian metric. Alternatively, one can define "measure zero" without referring to any Riemannian metric (Lee) 2013 p. 128). If F: M + N is a smooth map between n-dimensional smooth manifolds with boundary and AC M has measure zero, then F(A) S N is also measure zero (Lee 2013 Thm 5.9).
"Measure zero" provides one notion of what mcans for subset of a smooth manifold with boundary M to be "small". An alternative topological "smallness" nolion for subsets is "meager" A subset 5 C M is nowhere dense if M \ cl(S) is dense, and is meager if it is a countable union of nowhere dense sets (Folland 1999 p. 161). The Baire category theorem asserts that the complement M \ S of any meager Thm A.58), (Folland 1999. Thm 5.9).
set S is dense Lee
2013
A diffeotopy (or ambient isotopy) of smooth manifold with boundary M is a smooth map J: [0, 1] + M such that each time-t map Jr := .t, is a diffeomorphism and Jo = idar (Hirsch 1994 p. 178). The support of a diffeotopy J of M is the closure in M of the set
{ar M: J((x) # x for some E 1)..
Given a diffeotopy AJ of θM and a diffeotopy J of in) with compact support S C int the isotopy extension theorems assert the existence of diffeotopy J of M such that Jılaw OJ,, and Jtls Jtls for each i E [0. 1] (Hirsch 1994. Thm 8.1.3, 8.1.4).
Let M be a k-dimensional smooth manifold with boundary that is subset of an n-dimensional smooth manifold with boundary N, such that the topology on M is the subspace topology inherited from N. If the inclusion map M + N is a smooth embedding, then M is called a smoothly embedded submanifold with boundary of N Lec, 2013 p. 120). When ON = 2, such an M has the property that each x e M is contained a chart (U, s)) for N such that (UUnM is an open subset of the intersection of a k-dimensional affine subspace with H (Lee 2013 Thm 5.51). Conversely, if ON Ø and M C N is any subset of N with this property, then with the subspace topology, M has smooth structure making it into k-dimensional
smoothly embedded submanifold with boundary of N [Lee] 2013
Thm 5.51).
If M. is a smoothly embedded submanifold with boundary of a smooth manifold with boundary N, then any Riemannian metric on N canonically induces a Riemannian metric on N (Lee 2013, p. 333). Thus, if = R", a smoothly embedded submanifold with boundary M C N canonically inherits a Riemannian metric from the Euclidean inner product, since the latter is a Riemannian metric on R called the Euclidean metric (Lee 2013 Ex. 13.1). In this case, we refer to the finite Borel measure μ on M determined from the Euelidean-indueee metric as the intrinsic measure. If such an M is k-dimensional, then j(S) is simply the k-dimensional volume of S. In particular, s(S) is the length of S when k = 1, the surface area of S when k= = 2, the volume of S when k = 3, and so on.
Given Euclidean spaces R' and RTT, the compact-open topology on the space C(R" of continuous maps ge + _ is defined as follows. A subset S C (I""" is open if, for each f E S, there a compact set K C Rd and > such that any g E C(R"", R$) satisfying max [lf(x) - g(x)] < E belongs to S
Hirsch 1994 p. 58). The composition map
C(RR, (("", x C(I ,R²) + (IRT,
(g.f)
is continuous with respect to the compact-open topologies (and the product topology on the domain) 1994. p. 64, Fx. 10(a)..
HHrschh
23

---

Published in Transactions on Machine Learning Research (02/2024)
B.4 Algebraic topology
The standard n-simplex A C R=+1 is the convex hull of the standard basis vectors for Ra+1, equipped with the subspace topology (Hatcher 2002 103).
Let X be a topological space. A singular n-simplex X a continuous map a: A + X Hatcher 2002, p. 108). singular n-chain with coefficients the abelian group 22 = 2/22 a finite formal linear combination E; n, where each n, Eg and each 0, singular n-simplex in (Hatcher 2002 pp. 153, 108). The of all singular n-chains in X an abelian group Cx(X; (Hatcher 2002 p. 153). There are well-defined group homomorphisms 0, C, (X; satisfy 0n o 0x+1 = (Hatcher) 2002 pp- 153, 108). Thus, the image B, (X; of 0.+1 is contained in the
Cx-1(X; Z2). called boundary operators, that
kernel (X; E2) of On,, s0 the 7-th singular homology group with coefficients in Ze is well-defined as
the quotient group (Hatcher 2002 pp. 153, 108)
Hn Hx; = (2 (X;
From certain point of view, Hn (x; E2) counts the number of "n-dimensional holes" in X (cf. Hatcher 2002 p. 100, Thm 2.27, p. 153)).
Let X a k-dimensional manifold (i.e., without boundary). Tt fact that H, (X; (2 = for all n 2 k
when X noncompact, and that (,,(X; 22) for all when is compact (Hatcher 2002 p. 236, Prop. 3.29). Unlike the noncompact case, Hu (x; 22 f 0 when X compact (Hatcher 2002 p. 236).
Any continuous map f: X Y between topological spaces induces a well-defined homomorphism f.: (X; + ZY( for cach integer n by sending the equivalence class of an n-chain Σ, n;0; 111).
to the equivalence class of the n-chain Σ, n.J o oa (Hatcher 2002
A homotopy continuous map h: 00, 1] X + Y, and a homotopy from f:X x to g: X + Y if f = -(0,-) and g h(1,-) (Hatcher 2002 p. 3). Two maps f.g: + Y are homotopic there is a homotopy from to g (Hatcher 2002 p. 3).
A fundamental result called homotopy invariance asserts that homotopic maps f,g: X Y induce the same homomorphisms on homology, i.c., f.: H, (X::))2) + ZY; coincides with H Hx( +
H Z2) for each integer n (Hatcher 2002 Thm 2.10, p. 153).
24


Reviews:
[{"review_id": "zKlMJkwEC5", "reviewer": "Reviewer_XucU", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n* The main theorem is very solid. Although it could be intuitive that autoencoders may connect disjoint submanifolds together by creating break points and adding something among them, it is not a very easy task to make it completely rigorous in math. This paper uses several tools from differential geometry to establish their claim.\n* A simple example/experiment is provided in Section 3 to illustrate the idea.\n\nWeaknesses:\n* For readers with limited knowledge about differential geometry, the proof may be a bit hard to read. If the authors are willing to improve the readability, I would suggest adding a preliminary section to elaborate on the concepts/theorems to be used in the proof, e.g., cut locus, the identification used in Lemma 1, intrinsic measure, Sard's theorem, the extension theorems used in Lemma 2, compact-open topology, etc.\n* As a common limitation of all other papers studying the expressiveness of neural networks, it remains a challenging task to prove that neural networks can indeed fully utilize their expressive power and learn the constructed function via gradient-based training methods.\n\nTypo:\n* Lemma 2: In Line 4 of Paragraph 2, is F a smooth extension of F_0 or F itself?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Autoencoder is an important class of neural networks in deep learning, which aims to capture data with $G(F(x)) = x$ with encoder $F: \\mathbb{R}^n \\to \\mathbb{R}^k$ and decoder $G: \\mathbb{R}^k \\to \\mathbb{R}^n$. Since $F$ and $G$ are always continuous, there could be topological obstructions making this goal impossible: the support of data may not be homeomorphic to a k-dimensional submanifold in general. Still, autoencoders work well in practice.\n\nThis paper provides an approximation theorem to explain this apparent paradox. In particular, they show that autoencoders are actually capable of approximately representing data even if the data is supported on a union of compact submanifolds having dimension less than or equal to $k$.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* The paper title \"Why do autoencoders work?\" seems to suggest that the paper would provide an extensive study on why autoencoders work, but the paper's content is limited to the expressive power of autoencoders and does not provide much insight into the training dynamics. Also no experiments are conducted in a real-world setting. I would suggest changing the title to more accurately reflect the paper's essence. For example, \"How do autoencoders represent discontinuously distributed data?\" could be a good title.\n* It would be nice if the authors could add a conclusion section to summarize the main results and propose some future directions.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "ipBsjKZbQS", "reviewer": "Reviewer_rGgR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: The approximation property of auto-encoder underpinnings many applications in machine learning. Therefore studying the UAP property is certainly of great importance.  The main result shows that auto-encoder defined by the composition of two continuous functions with the latent dimension $k$ less than the input dimension $n$ can approximate the identity map on $R^n$ on the whole manifold expect an arbitrary small set.\n\nWeakness: My major concern is the novelty of the paper. The proofs of the main results are merely a convex combination of some facts from differential geometry and topology. Also, practical auto-encoders make use of deep neural networks in encoders and decoders. The current paper only discussed the general composition of continuous maps, rather than the neural auto-encoders, which make the paper less interesting to the ML community. The paper would have been significantly improved if a proof of UAP property for neural network-based auto-encoders is included.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proves a universal approximation theorem of auto-encoder  for approximating continuous maps between general manifolds with possibly different dimensions.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "No", "audience_explanation": "", "requested_changes": "As mentioned above, the novelty of the paper is low. I suggest adding a proof of UAP property for neural network-based auto-encoders in the new version.", "broader_impact_concerns": "oNone.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "rWuTlucrMg", "reviewer": "Reviewer_LRt6", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths:**\n- Concise\n- Supported by an intuitive and effective example\n\n**Weaknesses:**\n- The theoretical insights rest of technical results that aren't made digestible for the broad audience.\n  - The authors may be targeting a different audience, which is fine. Though it's certainly a loss to miss out on teaching something to the greater ML community.\n  - Just a couple references to where I'm coming from:\n    - [On Proof and Progress in Mathematics](https://www.ams.org/journals/bull/1994-30-02/S0273-0979-1994-00502-6/?active=current),\n    - [Why Mathematical Proof Is a Social Compact](https://www.quantamagazine.org/why-mathematical-proof-is-a-social-compact-20230831)\n- Indeed, the proofs lean on being a bit too terse.\n- While conciseness is appreciated, it leaves a lot unsaid. An extra section with conclusions and open questions would be great.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors offer a theoretical justification to the observed success of deep NN auto-encoders (AEs) despite known topological obstructions in regards to the underlying (or assumed) data manifold. In summary, the authors appeal to known results in differential geometry substantiating the existence of continuous maps, e.g., an encoder (F) and a decoder (G), that yield the desired AE for all but a subset of *small measure*. This subset of small measure, where the AE does not preserve the data manifold, allow flexibility against the topological obstructions mentioned earlier. The derivations are supported by a simple numerical example of two interlocked 1D circles in 3D, where the learned AE effectively ends up cutting both circles, destroying the input topology.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "**Technical issues:**\n- Please (**T1**) add a conclusions sections where lingering theoretical and practical issues are clearly outlined.\n  - For one thing, many approaches use the latent embeddings to *walk* along the *learned manifold*, e.g., generating/interpolating new samples. It would be interesting to (**T2**) discuss the implication of the implicit cutting performed by the AE as in the example shown.\n  - I can offer some more suggestions in a follow up comment.\n- Section 3:\n  - Please (**T3**) indicate that the ADAM optimizer was used. It would help to further highlight this choice, as well as any other insights/challenges from trying different architecture as alluded to in the text, in the future work section.\n    - **most neural net training algorithms, including the one that we employ (TensorFlow) are stochastic** -- I would not call TF a training algorithm per se; please revise.\n- Surfacing some presentation issues that are potentially more serious.\n  - Page 2:\n    - **It** *asserts that [..] with error smaller than $\\varepsilon$ on S*\n      - Please (**T4**) clarify that **it** refers to the PAC theorems cited, and not Theorem 1.\n    - *A related idea seems to have appeared in (Hecht-Nielsen, 1995, Fig. 4)*\n      - Please (**T5**) briefly describe the idea and how it's related to the discussion.\n    - Around Lemma 2\n      - Please (**T6**) double-check where the requirement of a finite-union is needed. If there's no need to speak of *any union* or *countable* union, then it's better to stick to one form. Specifically, Theorem 1 is stated for finitely-many submanifolds. On the other hand, the proof of Lemma 2 starts by countability as an implication. It would help to simplify this so long as it does not impact the main results.\n      - Please (**T7**) define the reach before Lemma 2, as later used Section 4. A brief definition and forward reference could be enough.\n      - Please (**T8**) add an adequate description of the outer regularity criterion, before engaging in the proof of Lemma 2.\n  - Proof of Theorem 1\n    - Please (**T9**) state clearly the properties assumed and implied on the first line of the proof. It is unnecessarily confusing to refer to sentences on different pages.\n  - Theorem 3: seeing that the proof is by contradiction, it would help to still (**T10**) provide intuition as to why the result is optimal.\n\n**Presentation issues:**\n- I'm pointing out locations where a typical ML reader may have a hard time following (i.e., speaking on behalf of your readers):\n- To avoid repetition, please note:\n  - IMHO, adding a reference to an entire chapter (or an exercise) in an advanced math textbook may serve as evidence enough for an expert, but is not helpful to the non-expert or beginner.\n  - See also **Tell them what you'll tell them** from [Ten Simple Rules for Mathematical Writing](https://www.mit.edu/~dimitrib/Ten_Rules.html)\n- Page 1:\n  - *Clearly such F, G exist if and only if K is homeomorphic to a k-dimensional submanifold*\n    - Please (**P1**) add 1-2 sentences gently defining homeomorphism, explaining the iff intuitively.\n- Page 2:\n  - *Recall that there is an intrinsic notion of “measure zero” subsets of a smooth manifold with boundary*\n    - Please (**P2**) add 1-2 sentences gently defining the intrinsic measure and measure zero subsets. \n  - Please (**P3**) add 1-2 sentences gently defining the cut locus and a diffeomorphism (explaining the $H: M \\setminus C_0 \\approx \\mathbb{R}^k$ notation), before engaging in the proof of Lemma 1.\n  - Proof of Lemma 1\n    - Please (**P4**) state in plain language what the guarantee $J(S) \\cap C_0 = \\emptyset$ means.\n    - Please (**P5**) state in plain language what the solution $C = J^{-1}(C_0)$ means.\n      - It would help to inform the reader of the intended plan of defining the desired $C$ by mapping a cut locus $C_0$.\n    - Please (**P6**) add 1-2 sentences gently defining the double $DM$.\n    - Please (**P7**) add 1-2 sentences gently defining what it means to be a diffeomorphism *onto* a given set.\n- Page 3:\n  - Please (**P8**) add an adequate description of Sard's theorem before engaging in the proof of Lemma 2.\n  - Please (**P9**) add 1-2 sentences gently defining the smooth extensions used in the proof of Lemma 2.\n- Proof of Theorem 1:\n  - Please (**P10**) add 1-2 sentences gently defining density in the compact-open topology, and inform the user of its role in the proof, before engaging in the proof.\n- Section 4:\n  - Please (**P11**) add 1-2 sentences gently defining smallness in the Baire sense (meagre), and how that enables the conclusion on the following sentence *by continuity*.\n  - Please (**P12**) add an adequate definition of Cech cohomology, how the choice of the Abelian group matters, why we're only interested in the $k$-th cohomology group, what it means when it's not $0$, and why this is all showing up here in this discussion of manifolds and diffeomorphisms (see next point).\n  - Please (**P13**) add 1-2 sentences gently defining homotopy and homotopy invariance, before engaging in the proof of Theorem 3.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the expressive power of autoencoders, highlighting topological obstructions to perfect reconstruction, and then proving with techniques from differential topology that these obstructions can be made to have a negligibly small effect. The reviewers found the results to be rigorous, and, after revision, the proofs to be reasonably approachable for a machine learning audience.

The reviewers' main concerns relate to the practical utility and significance of the results, as the analysis does not address the question of whether the autoencoding functions can actually be learned. I agree with the authors that answering this question is out of scope but would be an interesting future direction. On the other hand, some aspects of the paper's messaging (primarily the title) seem to suggest that this paper might in fact address practical aspects of autoencoder training, including this question. As such, I would encourage the authors to consider a slightly more conservative title, though ultimately the decision is theirs.
Decision: Accept (poster)