arXiv:2206.01552v1 [cs.LG] 3 Jun 2022

Is an encoder within reach?
Helene Hauschultz
Department of Mathematics,
Aarhus University
hhauschultz@math.au.dk

Rasmus Berg Palm
rasmusbergpalm@gmail.com

Pablo Moreno-Muñoz
Technical University ofDenmark, DTU Computepabmo@dtu.dk

Nicki Skafte Detlefsen
Technical University ofDenmark, DTU Computensde@dtu.dk

Andrew Allan du Plessis
Department of Mathematics,
Aarhus University
matadp@math.au.dk

Søren Hauberg
Technical University ofDenmark, DTU Computesohau@dtu.dk

Abstract
The encoder network of an autoencoder is an approximation of the nearest point
projection onto the manifold spanned by the decoder. A concern with this approximation is that, while the output of the encoder is always unique, the projection canpossibly have infinitely many values. This implies that the latent representations
learned by the autoencoder can be misleading. Borrowing from geometric measure
theory, we introduce the idea of using the reach of the manifold spanned by the
decoder to determine if an optimal encoder exists for a given dataset and decoder.
We develop a local generalization of this reach and propose a numerical estimator
thereof. We demonstrate that this allows us to determine which observations canbe expected to have a unique, and thereby trustworthy, latent representation. As
our local reach estimator is differentiable, we investigate its usage as a regularizer
and show that this leads to learned manifolds for which projections are more often
unique than without regularization.

1

Encoders as projectors

A good learned representation has many desiderata (Bengio et al., 2013). The perhaps most elementary constraint placed over most learned representations is that a given observation x should have aunique representation z, at least in distribution. In practice this is ensured by letting the representation
be given by the output of a function, z = g(x), often represented with a neural network. Having
a unique representation for a given observation is important for downstream tasks, as otherwise
the downstream loss function is complicated by having to be defined on sets (Zaheer et al., 2018).
Uniqueness of representation is also important when a human investigator seeks information about thephenomenon underlying data, e.g. through visualizations, as uniqueness is a ubiquitous assumption.
The autoencoder (Rumelhart et al., 1986) is an example where uniqueness of representation is
explicitly enforced, even if its basic construction does not suggest unique representations. In themost elementary form, the autoencoder consists of an encoder gψ : RD → Rd and a decoder
fφ : Rd → RD , parametrized by ψ and φ, respectively. These are trained by minimizing thereconstruction error of the training data {x1 , . . . , xN },ψ ∗ , φ∗ = argmin
ψ,φPreprint. Under review.

N
X
n=1

kf (g(xn )) − xn k2 .

(1)

Figure 1: Left: The projection of a point (yellow) onto a nonlinear manifold can take unique (green)or multiple values (red) depending on the reach of the manifold. When training data is inside thereach, the encoder can match the projection resulting in more trustworthy representations. Right: The
global reach defines a region around the manifold M consisting of all points below a certain distanceto M. This captures both local manifold curvature as well as global shape.
Here d is practically always smaller than D, such that the output of the encoder is a low-dimensional
latent representation of high-dimensional data. The data is assumed to lie near a d-dimensional
manifold M spanned by the decoder.
For a given decoder, we see that the optimal choice of encoder is the projection onto M, i.e.
goptimal (x) = projM (x) = argmin kx − f (z)k2 .

(2)z

For any nonlinear choice of decoder f , this optimal encoder does not exists everywhere. That is,multiple best choices of latent representation may exist for a given point, as the projection is notunique everywhere. As the learned encoder enforces a unique representation, it will choose arbitrarily
among the potential representations. In this case, any analysis of the latent representations can bemisleading, as it does not contain the information that another choice of representation would beequally as good.
In this paper we investigate the reach of the manifold M spanned by the decoder f . This concept,
predominantly studied in geometric measure theory, informs us about regions of observation space
where the projection onto M is unique, such that trustworthy unique representations exist. If training
data resides inside this region we may have hope that a suitable encoder can be estimated, leading totrustworthy representations. The classic reach construction is global in nature, so we develop a local
generalization that gives a more fine-grained estimate of the uniqueness of a specific representation.
We provide a new local, numerical, estimator of this reach, which allows us to determine whichobservations can be expected to have unique representations, thereby allowing investigations of
the latent space to disregard observations with non-unique representations. Empirically we findthat in large autoencoders, practically all data is outside the reach and risk not having a uniquerepresentation. To counter this, we design a reach-based regularizer that penalizes decoders forwhich unique representations of given data do not exist. Empirically, this significantly improves theguaranteed uniqueness of representations with only a small penalty in reconstruction error.

2

Reach and uniqueness of representation

Our starting question is which observations x have a unique representation z for a given decoder f ?
To answer this, we first introduce the reach (Federer, 1959) of the manifold spanned by decoder f .
This is a global scalar that quantifies how much points can deviate from the manifold while having aunique projection. Secondly, we contribute a generalization of this classic geometric construct tocharacterize the local uniqueness properties of the learned representation.
2.1

Defining reach

The nearest point projection projM is a well-defined function on all points for which there exists a
unique nearest point. We denote this set
Unp(M) = {x ∈ RD : x has a unique nearest point in M},
where M = f (Rd ) is the manifold spanned by mapping the entire latent space through the decoder.
Observations that lie within Unp(M) are certain to have a unique optimal representation, but there is
no guarantee that the encoder will recover this. With the objective of characterizing the uniqueness of2

representation, the set Unp(M) is a good starting point as here the encoder at least has a chance offinding a representation that is similar to that of a projection. However, for an arbitrary manifold M it
is generally not possible to explicitly find the set Unp(M). Introduced by Federer (1959), the reachof M provides us with an implicit way to understand which points are in and outside Unp(M).
Definition 2.1. The global reach of a manifold M isreach(M) = inf rmax (x),(3)

rmax (x) = sup{r > 0 : Br (x) ⊂ Unp(M)}.

(4)

x∈M

where
Here Br denotes the open ball of radius r.
Hence, reach(M) is the greatest radius r such that any open r-ball centered on the manifold lies in
Unp(M). In the existing literature, the global reach is referred to as the reach; we emphasize theglobal nature of this quantity as we will later develop local counterparts.
Definition 2.1 does not immediately lend itself to computation. Fortunately, Federer (1959) provides
a step in this direction, through the following result.
Theorem 2.2 (Federer (1959)). Suppose M is a manifold, then2reach(M) =

inf

x,y∈M
y−x∈T
/ xM

kx − yk,
2 kPNx M (y − x)k(5)

where PNx M is the orthogonal projection onto the normal space of M at x. If y − x ∈ Tx M for all
pairs x, y ∈ M we let reach(M) = ∞, as M will be flat and the projection unique everywhere.
For our objective of understanding which observations have a unique representation, i.e. are inside
Unp(M), the global reach provides some information. Specifically, the set
Mr = x| inf ky − xk < reach(M)(6)
y∈M

is a subset of Unp(M). This implies that observations x that are inside Mr will have a uniqueprojection, such that we can expect the representation to be unique. The downside is that sincereach(M) is a global quantity, Mr is an overly restrictive small subset of Unp(M). Fig. 1(right)
illustrates this issue. Note how the global reach in the example is determined by the bottleneck1 ofthe manifold. Even if this bottleneck only influences the uniqueness of projections of a single point,
it determines the global reach of the entire manifold. This implies that many points exist outside thereach which nonetheless has a unique projection.
2.2

Pointwise normal reachIn order to get a more informative notion of reach, we now develop a
local version, which we, for reasons that will be clear, call the pointwise
normal reach. For ease of notation denote
2

R(x, y) =kx − yk
2 kPNx M (y − x)k(7)

for x, y with y − x ∈/ Tx M, else we let R(x, y) = ∞. We then define Figure 2: Notation forthe proof of theorem 2.4.
the pointwise normal reach as the local infimum of eq. 5.
Definition 2.3 (Pointwise normal reach). At a point x ∈ M, the pointwise normal reach isrN (x) = inf R(x, y).
y∈M

(8)

In theorem 2.4 below we prove that the local estimate rN (x) describes how far we can move along anormal vector at x and still stay within Unp(M). This is useful as we know that x will lie in thenormal space of M at projM (x) (Federer (1959) Thm. 4.8).
1

Not to be confused with bottleneck network architectures or the information bottleneck.

3

Theorem 2.4. For all x ∈ M
BrN (x) (x) ∩ Nx M ⊂ Unp(M),where Nx M denotes the normal space at x.

(9)
Proof. Suppose for the sake of contradiction that there exists w ∈ BrN (x) (x) ∩ Nx M ∩Unp(M)c .
That is, there exists y1 , y2 ∈ M such thatd(w, M) = ky1 − wk = ky2 − wk ,(10)
where d(w, M) = inf x∈M kx − wk. In particular, we know there exists y ∈ M such thatky − wk ≤ kx − wk < rN (x).
(11)
Now, let θ1 denote the (acute) angle between Tx M and y − x, and let θ2 denote the angle between
y − x and w − x. The sum of θ1 and θ2 is a right angle, see Fig. 2. Let t be the distance from x to y.
The altitude through the vertex w divides y − x into two line segments. Denote the length of thesegment from the foot of the altitude to x, t1 , and the length of the segment from the foot to y, t2 .
Note, t2 will always be less or equal to t1 , as ky − wk ≤ kx − wk.
t/2
t1
By the definition of cosine, cos θ2 = kw−xk≥ kw−xk. At the same time cos θ2 = cos(π/2 −θ1 ) = sin θ1 = dt , where d = kPw−x (y − x)k, and as w − x ∈ Nx M, d ≤ kPNx M (y − x)k.
kP(y−x)kt/2Thus, we have kw−xk< dt < Nx Mt, implying R(x, y) ≤ kw − xk, which contradictsrN (x) ≤ R(x, y).

In lemma 2.6 below we show that the pointwise normal reach bounds the reach. For this, we needtheorem 4.8(7) from Federer (1959)
Lemma 2.5 (Federer (1959)). Let x, y be points on M with rmax (x) > 0, and let n be a normal
vector in Nx M, then2hn, y − xi ≤ky − xk knk
2rmax (x)(12)

Lemma 2.6. For all x ∈ M we have thatinfrN (y) ≤ rmax (x) ≤ rN (x).
y∈B2rN (x) (x)∩M

Proof.

P

(13)

(y−x)

Nx M
Applying the result from Federer to the vector n = kPNgives
M (y−x)kx2

rmax (x) ≤kx − yk knk,
2 knk kx − yk cos θ

where θ is the angle between x − y and n. Hence, cos θ =(14)kPNx M (y−x)k. Thus, for all y ∈ M
ky−xk

2

kx − yk,(15)
2 kPNx M (y − x)kproving the right inequality. Consider B = BrN (x) (x). Suppose there exists w ∈ B with w ∈/Unp(M). Then w ∈/ Nx M. Hence there exists y1 , y2 ∈ M such that d(w, M) = ky1 − wk =ky2 − wk < rN (x). From Federer (1959) theorem 4.8 we know that w ∈ Ny1 M, Ny2 M. Combining this with lemma 2.4 gives that rN (y1 ), rN (y2 ) ≤ d(w, M) and that d(x, M) < kw − xk. We
also have that ky1 − xk , ky2 − xk ≤ 2rN (x). Combining these inequalities gives us that the distance from x to any point not in Unp(M) is greater than inf y∈B2rN (x) (x)∩M rN (y), which implies
that
inf
rN (y) ≤ rmax (x).
rmax (x) ≤y∈B2rN (x) (x)∩M

We presented the theoretical analysis under the assumption that M = f (Rd ) is a manifold. Although
the theoretical results can be extended to arbitrary subsets of Euclidean space, the experimental
setup requires the Jacobian to span the entire tangent space. This might not be the case if M has
self-intersections. The theory can be extended to handle such self-intersections, but this significantly
complicates the algorithmic development. See the appendix for a discussion.
4

2.3

Estimating the pointwise normal reachThe definition of rN , prompts us to minimize R(x, y) over all of M, which is generally infeasible
and approximations are in order. As a first step towards an estimator, assume that we are givena finite sample S of points on the manifold. We can then replace the infimum in definition 2.3
with a minimization over the samples. Using that the projection matrix onto Nx M is given by
PNx M = I − J(J| J)−1 J| , we get the following estimator2ky − xk,y∈S 2 k(I − J(J| J)−1 J| )(y − x)kr̂N (x) = min(16)

where J ∈ RD×d is the Jacobian matrix of f at x. Note that since we replace the infimum with aminimization over a finite set, we have that r̂N (x) ≥ rN (x).
There are different choices of sampling sets S. Given a trained autoencoder, a cheap way to obtainsamples is to use the reconstructed training data as the sampling set. This will generally be sufficientif the training data is dense on the manifold, but this is rarely the case in high data dimensions. The
following lemma provides us a way to restrict the area over which we must minimize.
Lemma 2.7. For any x, y ∈ M
R(x, y) ≥1
kx − yk .
2(17)

Proof. Recall that y − x = PNx M (y − x) + PTx M (y − x), as RD = Tx M ⊕ Nx M. Henceky − xk ≥ kPNx M (y − x)k. The statement, thus, follows from the definition of R.
The lemma points towards a simple compu- Algorithm 1 Sampling-based reach estimator
tational procedure for numerically estimatradius ← r0
ing the pointwise normal reach, which is exreach ← ∞plicated in algorithm 1. Here reach_est
for i ← 1, . . . , num_batches dorefers to the application of eq. 16. The alsamples ← sample_ball(x, radius, batch_size)
gorithm samples uniformly inside a ballprojected← decode(encode(samples))centered on x and repeatedly shrinks the
reach
←
min
(reach, reach_est(x, projected))radius of the ball as tighter estimates of theradius ← 2· reach
reach are recovered. We further use theend forautoencoding reconstruction as an approximation to the projection of x onto M.
2.4

Is a point within reach?

Suppose that a point x ∈ RD is represented by a point on the manifold f (z). From definition 2.1 weknow that x has a unique nearest point on the manifold if
kx − f (z)k < rmax (f (z)).

(18)

A point x which does not satisfy this inequality risks not having a unique nearest point, and hence nounique representation. From lemma 2.6 we know that rmax (f (z)) ≤ rN (f (z)). So x risks not having
a unique nearest point if
kx − f (z)k ≥ rN (f (z)) ≥ rmax (f (z)).

(19)

We note that to show that kx − f (z)k ≥ rN (f (z)), it is enough to computer̂N (f (z)) =infy∈M∩B2kx−f (z)k (f (z))
y6=f (z)R(f (z), y),(20)i.e. limit the search to a ball of radius 2 kx − f (z)k. Thus, when we only need to determine if a point
is inside the pointwise normal reach, we can pick r0 = 2 kx − f (z)k in Algorithm 1.
Notice that given any set of points on the manifold, the resulting estimation of rN will always belarger than the true value. It means that any point which lies outside the estimated normal reach, willin fact lie outside the true normal reach. However, a point which lies inside the estimated normal
reach, risks lying outside the true normal reach, and thus not having a unique projection.
5

Figure 3: Left: An autoencoder trained on noisy
points scattered along a circular arc. Right: The manifold spanned by the decoder of an autoencoder
trained with reach regularization. In both panels, thegray circles illustrates theestimated pointwise normal
reach at points along the autoencoder curve.
2.5

Regularizing for reach

The autoencoder minimizes an l2 error which is directly comparable to the pointwise normal reach.
This suggests a regularizer that penalizes if the l2 error is larger than the pointwise normal reach. In
practice, we propose to use
R(x) = Softplus (kf (g(x)) − xk − r̂N (f (g(x)))) .

(21)

The reach-regularized autoencoder then minimizes
L=NX

kf (g(xn )) − xn k2 + λ

n=1

N
X

R(xn ),(22)n=1

where we in practice use λ = 1. We also experimented with a ReLU activation instead of Softplus,
but found the latter to yield more stable training. When estimating the pointwise normal reach, r̂N ,we apply Algorithm 1 with an initial radius of r0 = 2kf (g(xn )) − xn k.

3

Experiments

Having established a theory and algorithm for determining when a representation can be expected to
be unique, we next investigate its use empirically. We first compute the pointwise local reach across aselection of models to see if it provides useful information. We then carry on to investigate the use ofreach regularization. 2
3.1

Analysing reach

3.1.1

Toy circle

We start our investigations with a simple toy example to get an intuitive understanding. We generate
observations along a circular arc with added Gaussian noise of varying magnitude. Specifically, we
generate approximately 400 points as z 7→ t (sin(z), − cos(z)) + 1.5 cos(z), where  ∼ N (0, 1).
On this, we train an autoencoder with a one-dimensional latent space. The encoder and decoder bothconsist of linear layers, with three hidden layers with 128 nodes and with ELU non-linearities.
Figure 3(left) shows the data alongside the estimated manifold and its pointwise normal reach. We
observe that the manifold spanned by the decoder has areas with small reach, where the manifold
curves to fit the noisy data. The pointwise normal reach seems to well-reflect the curvature of theestimated manifold. The plot illustrates how some of the points end up further away from the manifold
than the reach. For some of the points, this is not a problem, as they still have a unique projection
onto the manifold. However, some of the points are equally close to different points on the manifold,such that their representation cannot be trusted.
3.1.2

CelebATo investigate the reach on a non-toy dataset, we train a deep autoencoder on the CelebA face dataset(Liu et al., 2015). The dataset consists of approximately 200 000 images of celebrity faces.
2

The code is available at https://github.com/HeleneHauschultz/is_an_encoder_within_reach.

6Figure 4: CelebA validation set reconstructions.

Figure 5: Left: Estimated reach for CelebA validation samples plotted against the L2 error. Samples
below the diagonal red line does not have a unique encoder. Center: Normalized reach as a functionof batches used to estimate the reach. The normalized reach is the estimated pointwise normal reachdivided by the estimated pointwise normal reach after the first batch. The hyperball sampling reachestimator quickly converges. Right: Sensitivity analysis of the hyperball sampling reach estimator to
the initial hyperball radius. The reach of CelebA validation samples are estimated with initial radiir0 = 1.0 and r0 = 0.01 respectively and their final reach after 100 batches are plotted against eachother.
We train a symmetric encoder-decoder pair that maps the 64 × 64 × 3 images to a 128 dimensional
latent space, and back. The encoder consists of a single 2d convolution operation without stride
followed by six convolution operations with stride 2, resulting in a 1 × 1 × C image. We use
C = 128 channels for all convolutional operations, a filter size of 5 and Exponential Linear Unit
(ELU) non-linearities. The decoder is symmetric, using transpose convolutions with stride 2 to
upsample and ending with a convolution operation mapping to 64 × 64 × 3. The model is trainedfor 1M gradient updates on the mean square error loss, with a batch size of 128, using the Adam
optimizer with a learning rate of 10−4 . Example reconstructions on the validation set are provided inFig. 4.
After training we estimate the reach of the validation set using the sampling based approach (Alg. 1).
Fig. 5(left) plots the reconstruction error kx − f (z)k versus the pointwise normal reach. We observethat almost all observations lie outside the pointwise normal reach, implying that we cannot guarantee
a unique representation. This is a warning sign that our representations need not be trustworthy.
Next we analyze the empirical convergence properties of our estimator on the CelebA autoencoder.
Fig. 5(center) shows the average pointwise normal reach over the validation set as a function of thenumber of iterations in the sampling based estimator. We observe that the estimator converges after
just a few iterations, suggesting that the estimator is practical.
The estimator relies on an initial radius for its search. Fig. 5(right) shows the estimated pointwise
normal reach on the validation set, plotted for two different initial radii. We observe that the estimator
converges to approximately the same value in both cases, suggesting that the method is not sensitive
to this initial radius. However, initializing with a tight radius will allow for faster convergence.
3.2

Reach regularization

Having established that the pointwise normal reach provides a meaningful measure of uniqueness,
we carry on to regularize accordingly.
7

Figure 6: The effect of reach regularization on an MNIST model. Left: The plot shows that thepercentage of points within reach increases, while the l2 -loss is nearly unchanged. We plot the loss
curve from the initial 5000 epochs without regularization, to show how the l2 -loss behaves whenregularizing. Center & right: Latent representations of the MNIST autoencoder before and after
the reach regularization. The red numbers are outside the reach, while green are within. Reachregularization smoothens the decoder to increase reach with minimal changes to both reconstructions
and latent configuration.
3.2.1

Toy circle

Returning to the example from section 3.1.1, we train an autoencoder of the same architecture withthe reach regularization. We pretrain the network 100 epochs without regularization, and then 2000
iterations with reach regularization.
Fig. 3(right) shows that reach regularization gives a significantly smoother manifold than without
regularization (left panel). The gray circles on the plot indicate that almost all the points are now within
the pointwise normal reach, and arguably the associated representations are now more trustworthy.
3.2.2

MNIST

Next we train an autoencoder on 5000 randomly chosen images from the classes 2, 4 and 8 fromMNIST (LeCun et al., 1998). We use a symmetric architecture reducing to two dimensional representation through a sequence of 784 → 500 → 250 → 150 → 100 → 50 → 2 linear layers with
ELU non-linearities. We pretrain 5000 epochs without any regularization, and proceed with reachregularization enabled. Fig. 6(left) shows the percentage of points which lies within reach of theestimated manifold. We observe that reach regularization slightly increases the reconstruction error,
as any regularization would, while significantly increasing the percentage of points that are known
to have a unique representation. This suggests that reach regularization only minimally changes
reconstructions while giving a significantly more smooth model, which is more reliable.
Figure 6(center) shows the latent representations given by the pretrained autoencoder without regularization, while Fig 6(right) shows the latent representations after an additional 200 epochs withreach regularization. The latent representations with corresponding data points outside reach, that is,where the reconstruction error is greater than the pointwise normal reach at the reconstructed pointis plotted in red. The points inside reach are plotted in green. We observe that after regularization,
significantly more points can be expected to be unique and thereby trustworthy. Note that the latentconfiguration is only changed slightly after reach regularization, which suggests that the expressive
power of the model is largely unaffected by the reach regularization.

4

Related work

Representation learning is a foundational aspect of current machine learning, and the discussion paper
by Bengio et al. (2013) is an excellent starting point. As is common, Bengio et al. (2013) defines a
representation as the output of a function applied to an observation, implying that a representation is
unique. In the specific context of autoencoders, we question this implicit assumption of uniquenessas many equally good representations may exist for a given observation. While only studied here
for autoencoders, the issue applies more generally when representations span submanifolds of theobservation space.
8

In principle, probabilistic models may place multimodal distributions over the representation of anobservation in order to reflect lack of uniqueness. In practice, this rarely happens. For example,
the highly influential variational autoencoder (Kingma and Welling, 2014; Rezende et al., 2014)
amortizes the estimation of p(z|x) such that it is parametrized by the output of a function. Alternatives
relying on Monte Carlo estimates of p(z|x) do allow for capturing non-uniqueness (Hoffman, 2017),
but this is rarely done in practical implementations. That Monte Carlo estimates provide state-ofthe-art performance is perhaps indicative that coping with non-unique representations is important.
Our approach, instead, aim to determine which observations can be expected to have a uniquerepresentation, which is arguably simpler than actually finding the multiple representations.
Our approach relies on the reach of the manifold spanned by the decoder. This quantity is traditionallystudied in geometric measure theory as the reach is informative of many properties of a given
manifold. For example, manifolds which satisfy that reach(M) > 0 are C 1,1 , i.e. the transition
functions are differentiable with Lipschitz continuous derivatives. In machine learning, the reach is,
however, a rarely used concept. Fefferman et al. (2016) investigates if a manifold of a given reachcan be fitted to observed data, and develops the associated statistical test. Further notable exceptions
are the multichart autoencoder by Schonsheck et al. (2020), and the adaptive clustering of Besold andSpokoiny (2020). Both works rely on the reach as a tool of derivation. Similarly, Chae et al. (2021)
relies on the assumption of positive reach when deriving properties of deep generative models. These
works all rely on the global reach, while we have introduced a local generalization.
The work closest to ours appears to be that of Aamari et al. (2019) which studies the convergenceof an estimator of the global reach (5). This only provides limited insights into the uniqueness ofa representation as the global reach only carries limited information about the local properties ofthe studied manifold. We therefore introduced the pointwise normal reach alongside an estimator
thereof. This gives more precise information about which observations can be expected to have aunique representation.

5

Discussion

The overarching question driving this paper is when can representations be expected to be unique?
Though commonly assumed, there is little mathematical reason to believe that the choice of optimal
representation is generally unique. The theoretical implications of this is that enforcing uniquenesson non-unique representations leads to untrustworthy representations.
We provide a partial answer for the question in the context of autoencoders, through the introductionof the pointwise normal reach. This provides an upper bound for a radius centered around eachpoint on the manifold spanned by the decoder, such that any observation within the ball has a uniquerepresentation. This bound can be directly compared to the reconstruction error of the autoencoding
to determine if a given observation might not have a unique representation. This is a step towards asystematic quantification of the reliability and trustworthiness of learned representations.
Empirically, we generally find that most trained models do not ensure that representations are unique.
For example, on CelebA we found that almost no observations were within reach, suggesting thatuniqueness was not ensured. This is indicative that the problem of uniqueness is not purely an
academic question, but one of practical importance.
We provide a Monte Carlo estimator of the pointwise normal reach, which is guaranteed to upperbound the true pointwise normal reach. The estimator is easy to implement, with the main difficulty
being the need to access the Jacobian of the decoder. This is readily accessible using forward-mode
automatic differentiation, but it can be memory-demanding for large models.
It is easy to see that the sample-based pointwise normal reach estimator converges to the correct value
in the limit of infinitely many samples. We, however, have no results on the rate of convergence. In
practice we observe that the estimator converges in a few iterations for most models, suggesting theconvergence is relatively fast. In practice, the estimator, however, remains computationally expensive.
While we can estimate the pointwise normal reach quite reliably even for large models withinmanageable time, the estimator is currently too expensive to use for regularization of large models. On
small models, we observe significant improvements in the uniqueness properties of the representations
at minimal cost in terms of reconstruction error. This is a promising result and indicative that it
may be well-worth using this form of regularization. While more work is needed to speed up theestimating of pointwise normal reach, our work does pave a path to follow.
9

Acknowledgments and Disclosure of Funding
This work was supported by research grants (15334, 42062) from VILLUM FONDEN. This project
has also received funding from the European Research Council (ERC) under the European Union’s
Horizon 2020 research and innovation programme (grant agreement 757360). This work was fundedin part by the Novo Nordisk Foundation through the Center for Basic Machine Learning Researchin Life Science (NNF20OC0062606). Helene Hauschultz is partly financed by Aarhus University
Centre for Digitalisation, Big Data and Data Analytics (DIGIT)

References
E. Aamari, J. Kim, F. Chazal, B. Michel, A. Rinaldo, and L. Wasserman. Estimating the reach of a manifold,2019.
Y. Bengio, A. Courville, and P. Vincent. Representation learning: A review and new perspectives. IEEE
transactions on pattern analysis and machine intelligence, 35(8):1798–1828, 2013.
F. Besold and V. Spokoiny. Adaptive manifold clustering, 2020.
M. Chae, D. Kim, Y. Kim, and L. Lin. A likelihood approach to nonparametric estimation of a singular
distribution using deep generative models, 2021.
H. Federer. Curvature measures. Transactions of the American Mathematical Society, 93(3):418–491, 1959.
ISSN 0002-9947.
C. Fefferman, S. Mitter, and H. Narayanan. Testing the manifold hypothesis. Journal of the American
Mathematical Society, 29(4):983–1049, 2016. ISSN 0894-0347.
M. D. Hoffman. Learning deep latent Gaussian models with Markov chain Monte Carlo. In D. Precup andY. W. Teh, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 ofProceedings of Machine Learning Research, pages 1510–1519. PMLR, 06–11 Aug 2017.
D. P. Kingma and M. Welling. Auto-Encoding Variational Bayes. In Proceedings of the 2nd International
Conference on Learning Representations (ICLR), 2014.
Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition.
Proceedings of the IEEE, 86(11):2278–2324, 1998.
Z. Liu, P. Luo, X. Wang, and X. Tang. Deep learning face attributes in the wild. In Proceedings of International
Conference on Computer Vision (ICCV), December 2015.
D. J. Rezende, S. Mohamed, and D. Wierstra. Stochastic Backpropagation and Approximate Inference in Deep
Generative Models. In Proceedings of the 31st International Conference on Machine Learning (ICML), 2014.
D. E. Rumelhart, G. E. Hinton, and R. J. Williams. Learning representations by back-propagating errors. nature,323(6088):533–536, 1986.
S. Schonsheck, J. Chen, and R. Lai. Chart auto-encoders for manifold structured data, 2020.
M. Zaheer, S. Kottur, S. Ravanbakhsh, B. Poczos, R. Salakhutdinov, and A. Smola. Deep sets, 2018.

10

A

Appendix

A.1

Extending the pointwise normal reach to the non-manifold settingFederer (1959) introduces reach for arbitrary subsets of Euclidean space. In this situation Tx M and Nx M
denote the tangent- and normal cone.
Definition A.1. Let M ⊂ RD denote an arbitrary subset and let x ∈ M. Then v ∈ RD is a tangent vector for
M at x if either v = 0 or if for every ε > 0 exists y ∈ M with
0 < ky − xk < ε

y−x
v
−
< ε.
ky − xk
kvk

and

(23)

Let Tx M denote the set of tangent vectors for M at x. A vector w ∈ RD is a normal vector for M at x if
hw, vi ≤ 0 for all v ∈ Tx M.

(24)

Let Nx M denote the set of all normal vectors for M at x.
We can extend theorem 2.4 and Lemma 2.6 to the general situation as defined by Federer. To extend Theorem 2.4
it is sufficient to prove that for any v ∈ Nx M and u ∈ RD , kPv (u)k ≤ d(u, Tx M).
Lemma A.2. For any v ∈ Nx M and u ∈ RD with hv, ui ≥ 0, kPv (u)k ≤ d(u, Tx M).
Proof. For a subset A ⊂ RD , dual(A) = {v ∈ RD : ha, vi ≤ 0 for all a ∈ A}. First we prove thatd(u, dual(v)) = kPv (u)k. Note that we can write u = uv + uv⊥ , where uv = Pv (u) and uv⊥ ∈ v ⊥ . Thend(u, dual(v)) ==infku − wk =inf

kuv + uv⊥ − wkw∈dual(v)w∈dual(v)infkuv k + kuv⊥ − wk − 2 huv , wi .

w∈dual(v)(25)

As huv , wi ≤ 0, it follows that the infimum is achieved when w = uv⊥ . By the definition of thedual it follows that dual(v) ⊃ dual(Nx M) ⊃ Tx M. Hence d(u, Tx M) = inf w∈Tx M ku − wk ≥inf w∈dual(v) ku − wk = kPu (v)k.
To extend lemma 2.6 note that if rmax (x) > 0, then Tx M is convex (Federer, 1959, Thm 4.8 (12)). Let y ∈ M.
If y − x ∈ Tx M then R(x, y) = ∞. Otherwise, as Tx M is a convex cone, there exists n ∈ Nx M such thathn, y − xi ≥ 0. In that case hn, x − yi = kPn (y − x)k, so applying Lemma 2.5 gives the result.
Though the theory can be extended to general subspaces, the manifold assumption is important for the experimental setup. An important assumption for the estimator (16) is that the Jacobian spans the entire tangent
space. If this is not the case, this estimator does not estimate the pointwise normal reach. The reason being, thelength of the projection onto the orthogonal complement of the Jacobian is not necessarily the distance to thetangent space. It is clear that when we want to study the uniqueness of latent representations, if the decoder is
not injective, it automatically has areas without unique representations. So if the decoder is not injective, weshould already be wary about trusting the latent representations.

11