Year: 2021

Abstract:
Variational Autoencoders (VAEs) are one of the most commonly used generative models, particularly for image data. A prominent difficulty in training VAEs is data that is supported on a lower dimensional manifold. Recent work by Dai and Wipf (2019) suggests that on low-dimensional data, the generator will converge to a solution with 0 variance which is correctly supported on the ground truth manifold. In this paper, via a combination of theoretical and empirical results, we show that the story is more subtle. Precisely, we show that for linear encoders/decoders, the story is mostly true and VAE training does recover a generator with support equal to the ground truth manifold, but this is due to the implicit bias of gradient descent rather than merely the VAE loss itself. In the nonlinear case, we show that the VAE training frequently learns a higher-dimensional manifold which is a superset of the ground truth manifold.

heading: 1 INTRODUCTION
text: Variational autoencoders (VAEs) have recently enjoyed a revived interest, both due to architectural choices that have led to improvements in sample quality (Oord et al., 2017; Razavi et al., 2019b; Vahdat & Kautz, 2020) and due to algorithmic insights (Dai et al., 2017; Dai & Wipf, 2019). Nevertheless, fine-grained understanding of the behavior of VAEs is lacking, both on the theoretical and empirical level.
In our paper, we study a common setting of interest where the data is supported on a low-dimensional manifold — often argued to be the setting relevant to real-world image and text data due to the manifold hypothesis (see e.g. Goodfellow et al. (2016)). In this setting, Dai & Wipf (2019) proposed a two-stage training process for VAEs, based on a combination of empirical and theoretical arguments suggesting that for standard VAE training with such data distributions: (1) the generator’s covariance will converge to 0, (2) the generator will learn the correct manifold, but not the correct density on the manifold (3) the number of approximately 0 eigenvalues in the encoder covariance will equal the intrinsic dimensionality of the manifold (see also Dai et al. (2017)).
In this paper, we revisit this setting and explore the behaviour of both the VAE loss, and the training dynamics. Through a combination of theory and experiments we show that:
• In the case of the data manifold being linear (i.e. the data is Gaussian, supported on a linear subspace—equivalently, it is produced as the pushforward of a Gaussian through a linear map), and the encoder/decoder being parametrized as linear maps, we show that: a) the set of optima includes parameters for which the generator’s support is a strict superset of the data manifold; b) the gradient descent dynamics are such that they converge to generators with support equal to the support of the data manifold. This provides a full proof of the conjecture in Dai & Wipf (2019), albeit we show the phenomenon is a combination of both the location of the minima of the loss as well as an implicit bias of the training dynamics.
• In the case of the data manifold being nonlinear (i.e. the data distribution is the pushforward of the Gaussian through a nonlinear map f : Rr → Rd, r ≤ d), the gradient descent dynamics from a random start often converges to generators G whose support strictly contains the support of the underlying data distribution, while driving reconstruction error to 0 and driving the VAE loss to
−∞. This shows that the conjecture in Dai & Wipf (2019) does not hold for general nonlinear data manifolds and architectures for the generator/encoder.
Organization: We will provide an informal overview of our findings in Section 3. The rigorous discussion on the VAE landscape are in Section 4 and on the implicit bias of gradient descent in Section 5.

heading: 2 SETUP
text: We will study the behavior of VAE learning when data lies on a low-dimensional manifold—more precisely, we study when the generator can recover the support of the underlying data distribution. In order to have a well-defined “ground truth”, both for our theoretical and empirical results, we will consider synthetic dataset that are generated by a “ground truth” generator as follows.
Data distribution: To generate a sample point x for the data distribution, we will sample z ∼ N(0, Ir), and output x = f(z), for a suitably chosen f . In the linear case, f(z) = Az, for some matrix A ∈ Rd×r. In the nonlinear case, f(z) will be a nonlinear function f : Rr → Rd. We will consider several choices for f .
Parameterization of the trained model: For the model we are training, the generator will sample z ∼ N(0, Ir) and output x ∼ N(f(z), I), for trainable f, ; the encoder given input x will output z ∼ N(g(x), D), where D ∈ Rr×r is a diagonal matrix, and g,D are trainable. In the linear case, f, g will be parameterized as matrices Ã, B̃; in the nonlinear case, several different parameterizations will be considered. In either case the VAE Loss will be denoted by L(·), see (3).

heading: 3 OUR RESULTS
text: Linear VAEs: the correct distribution is not recovered. Recall in the linear case, we train a linear encoder and decoder to learn a Gaussian distribution consisting of data points x ∼ N(0,Σ) — equivalently, the data distribution is the pushforward of a standard Gaussian z ∼ N(0, Ir) through a linear generator x = Az with AAT = Σ; see also Section 2 above. In Theorem 1 of Lucas et al. (2019), the authors proved that in a certain probabilistic PCA setting where Σ is full-rank, the landscape of the VAE loss has no spurious local minima: at any global minima of the loss, the VAE decoder exactly matches the ground truth distribution, i.e. ÃÃT + 2I = Σ.
We revisit this problem in the setting where Σ has rank less than d so that the data lies on the lowerdimensional manifold/subspace spanned by the columns of A or equivalently Σ, denoted span(A). We show empirically (i.e. via simulations) in Section 6 that when Σ is rank-degenerate the VAE actually fails to recover the correct distribution. More precisely, the recovered Ã has the correct column span but fails to recover the correct density — confirming predictions made in Dai & Wipf (2019). We then explain theoretically why this happens, where it turns out we find some surprises.
Landscape Analysis: Linear and Nonlinear VAE. Dai & Wipf (2019) made their predictions on the basis of the following observation about the loss landscape: there can exist sequences of VAE solutions whose objective value approaches −∞ (i.e. are asymptotic global minima), for which the generator has the correct column span, but does not recover the correct density on the subspace. They also informally argued that these are all of the asymptotic global minima of loss landscape (Pg 7 and Appendix I in Dai & Wipf (2019)), but did not give a formal theorem or proof of this claim.
We settle the question by showing this is not the case:1 namely, there exist many convergent sequences of VAE solutions which still go to objective value −∞ but also do not recover the correct column span — instead, the span of such Ã is a strictly larger subspace. More precisely, we obtain a tight characterization of all asymptotic global minima of the loss landscape:
Theorem 1 (Optima of Linear VAE Loss, Informal Version of Theorem 3). Suppose that Ã, B̃ are fixed matrices such that A = ÃB̃A and suppose that #{i : Ãi = 0} > r − d, i.e. the number
1They also argued this would hold in the nonlinear case, but our simulations show this is generally false in that setting, even for the solutions chosen by gradient descent with a standard initialization — see Section 6.
of zero columns of Ã is strictly larger than r − d. Then there exists ̃t → 0 and positive diagonal matrices D̃t such that limt→∞ L(Ã, B̃, D̃t, ̃t) = −∞. Also, these are all of the asymptotic global minima: any convergent sequence of points (Ãt, B̃t, D̃t, ̃t) along which the loss L goes to −∞ satisfies Ãt → Ã, B̃t → B̃ with A = ÃB̃A such that #{i : Ãi = 0} > r − d.
To interpret the constraint #{i : Ãi = 0} > r − d, observe that if the data lies on a lowerdimensional subspace of dimension r∗ < d (i.e. r∗ is the rank of Σ), then there exists a generator which generates the distribution with r − r∗ > r − d zero columns by taking an arbitrary lowrank factorization LLT = Σ with L : d × r∗ and defining A : d × r by A = [L 0d×r−r∗ ]. The larger the gap is between the manifold/intrinsic dimension r∗ and the ambient dimension d, the more flexibility we have in constructing asymptotic global minima of the landscape. Also, we note there is no constraint in the Theorem that r − d ≥ 0: the assumption is automatically satisfied if r < d.
To summarize, the asymptotic global minima satisfy A = ÃB̃A, so the column span of Ã contains that of A, but in general it can be a higher dimensional space. For example, if d, r ≥ r∗ + 2 and and the ground truth generator is A = [ Ir∗ 0 0 0 ] , then Ã = [ Ir∗+1 0 0 0 ] and B̃ = [ Ir∗+1 0 0 0 ] is a perfectly valid asymptotic global optima of the landscape, even though decoder Ã generates a
different higher-dimensional Gaussian distribution N ( 0, [ Ir∗+1 0
0 0
]) than the ground truth. In
the above result we showed that there are asymptotic global minima with higher dimensional spans even with the common restriction that the encoder variance is diagonal; if we considered the case where the encoder variance is unconstrained, as done in Dai & Wipf (2019), and/or can depend on its input x, this can only increase the number of ways to drive the objective value to −∞. We also consider the analogous question in the nonlinear VAE setting where the data lies on a lowdimensional manifold. We prove in Theorem 6 that even in a very simple example where we fit a VAE to generate data produced by a 1-layer ground truth generator, there exists a bad solution with strictly larger manifold dimension which drives the reconstruction error to zero (and VAE loss to −∞). The proof of this result does not depend strongly on the details of this setup and it can be adapted to construct bad solutions for other nonlinear VAE settings.
We note that the nature both of these result is asymptotic: that is, they consider sequences of solutions whose loss converges to −∞— but not the rate at which they do so. In the next section, we will consider the trajectories the optimization algorithm takes, when the loss is minimized through gradient descent.
Linear VAE: implicit regularization of gradient flow. The above theorem indicates that studying the minima of the loss landscape alone cannot explain the empirical phenomenon of linear VAE training recovering the support of the ground truth manifold in experiments; the only prediction that can be made is that the VAE will recover a possibly larger manifold containing the data.
We resolve this tension by proving that gradient flow, the continuous time version of gradient descent, has an implicit bias towards the low-rank global optima. Precisely, we measure the effective rank quantitatively in terms of the singular values: namely, if σk(Ã) denotes the k-th largest singular value of matrix Ã, we show that all but the largest dim(spanA) singular values of Ã decay at an exponential rate, as long as: (1) the gradient flow continues to exist2 , and (2) the gradient flow does not go off to infinity, i.e. neither Ã or ̃ go to infinity (in simulations, the decoder Ã converges to a bounded point and ̃ → 0 so the latter assumption is true). To simplify the proof, we work with a slightly modified loss which “eliminates” the encoder variance by setting it to its optimal value: L1(Ã, B̃, ̃) := minD̃ L(Ã, B̃, ̃, D̃); this loss has a simpler closed form, and we believe the theorems should hold for the standard loss as well. (Generally, gradient descent on the original loss L will try to optimize D̃ in terms of the other parameters, and if it succeeds to keep D̃ well-tuned in terms of Ã, B̃, ̃ then L will behave like the simplified loss L1.)
2We remind the reader that the gradient flow on loss L(x) is a differential equation dx/dt = −∇L(x). Unlike discrete-time gradient descent, gradient flow in some cases (e.g. dx/dt = x2) has solutions which exist only for a finite time (e.g. x = 1/(1 − t)), which “blows up” at t = 1), so we need to explicitly assume the solution exists up to time T .
Theorem 2 (Implicit Bias of Gradient Flow, Informal version of Theorem 5). Let A : d × r be arbitrary and define W to be the span of the rows of A, let Θ̃(0) = (Ã(0), B̃(0), ̃(0)) be an arbitrary initialization and define the gradient flow Θ̃(t) = (Ã(t), B̃(t), ̃(t)) by the ordinary differential equation (ODE)
dΘ̃(t)
dt = −∇L1(Θ̃(t)) (1)
with initial condition Θ0. If the solution to this equation exists on the time interval [0, T ] and satisfies maxt∈[0,T ] maxj [‖(Ãt)j‖2 + ̃2t ] ≤ K, then for all t ∈ [0, T ] we have
d∑ k=dim(W )+1 σ2k(Ã(t)) ≤ C(A, Ã) e−t/K (2)
where C(A, Ã) := ‖PW⊥ÃT (0)‖2F and PW⊥ is the orthogonal projection onto the orthogonal complement of W .
Together, our Theorem 1 and Theorem 2 show that if gradient descent converges to a point while driving the loss to −∞, then it successfully recovers the ground truth subspace/manifold spanA. This shows that, in the linear case, the conjecture of Dai & Wipf (2019) can indeed be validated provided we incorporate training dynamics into the picture. The prediction of theirs we do not prove is that the number of zero entries of the encoder covariance D converges to the intrinsic dimension; as shown in Table 1, in a few experimental runs this does not occur — in contrast, Theorem 2 implies that Ã should have the right number of nonzero singular values and our experiments agree with this.
Nonlinear VAE: Dynamics and Simulations. In the linear case, we showed that the implicit bias of gradient descent leads the VAE training to converge to a distribution with the correct support. In the nonlinear case, we show that this does not happen—even in simple cases.
Precisely, in the setup of the one-layer ground truth generator, where we proved (Theorem 6) there exist bad global optima of the landscape, we verify experimentally (see Figure 1) that gradient descent from a random start does indeed converge to such bad asymptotic minima. In particular, this shows that whether or not gradient descent has a favorable implicit bias strongly depends on the data distribution and VAE architecture.
More generally, by performing experiments with synthetic data of known manifold dimension, we make the following conclusions: (1) gradient descent training recovers manifolds approximately containing the data, (2) these manifolds are generally not the same dimension as the ground truth manifold, but larger (this is in contrast to the conjecture in Dai & Wipf (2019) that they should be equal) even when the decoder and encoder are large enough to represent the ground truth and the reconstruction error is driven to 0 (VAE loss is driven to −∞), and (3) of all manifolds containing the data, gradient descent still seems to favor those with relatively low (but not always minimal) dimension. Further investigating the precise role of VAE architecture and optimization algorithm, as well as the interplay with the data distribution is an exciting direction for future work.

heading: 3.1 RELATED WORK
text: Implicit regularization. Interestingly, the implicit bias towards low-rank solutions in the VAE which we discover is consistent with theoretical and experimental results in other settings, such as deep linear networks/matrix factorization (e.g. Gunasekar et al. (2018); Li et al. (2018); Arora et al. (2019); Li et al. (2020); Jacot et al. (2021)), although it seems to be for a different mathematical reason — unlike those settings, initialization scale does not play a major role. Similar to the setting of implicit margin maximization (see e.g. Ji & Telgarsky (2018); Schapire & Freund (2013); Soudry et al. (2018)), in our VAE setting the optima are asymptotic (though approaching a finite point, not off at infinity) and the loss goes to −∞. Kumar & Poole (2020); Tang & Yang (2021) also explore some implicit regularization effects tied to the Jacobian of the generator and the covariance of the Gaussian noise.
Architectural and Algorithmic Advances for VAEs. There has been a recent surge in activity with the goal of understanding VAE training and improving its performance in practice. Much of the work has been motivated by improving posterior modeling to avoid problems such as “posterior
collapse”, see e.g. (Dai et al., 2020; Razavi et al., 2019a; Pervez & Gavves, 2021; Lucas et al., 2019; He et al., 2019; Oord et al., 2017; Razavi et al., 2019b; Vahdat & Kautz, 2020). Most relevant to the current work are probably the works Dai & Wipf (2019) and Lucas et al. (2019) discussed earlier. A relevant previous work to these is Dai et al. (2017); one connection to the current work is that they also performed experiments with a ground truth manifold, in their case given as the pushforward of a Gaussian through a ReLU network. In their case, they found that for a certain decoder and encoder architectures that they could recover the intrinsic dimension using a heuristic related to the encoder covariance eigenvalues from Dai & Wipf (2019); our results are complementary in that they show that this phenomena is not universal and does not hold for other natural datasets (e.g. manifold data on a sphere fit with a standard VAE architecture).

heading: 4 VAE LANDSCAPE ANALYSIS
text: In this section, we analyze the landscape of a VAE, both in the linear and non-linear case.
Preliminaries and notation. We use a VAE to model a datapoint x ∈ Rd as the pushforward of z ∼ N(0, Ir). We have the following standard VAE architecture:
p(x|z) = N(f(z), 2I), q(z|x) = N(g(x), D) where 2 > 0 is the decoder variance, D is a diagonal matrix with nonnegative entries, and f, g,D, are all trainable parameters. (For simplicity, our D does not depend on x; this is the most common setup in the linear VAE case we will primarily focus on.) The VAE objective (see Appendix A for explicit derivation) is to minimize:
L(f, g,D, ) := Ex∼p∗Ez′∼N(0,Ir) [ 1
2 2 ‖x− f(g(x) +D1/2z′)‖2 + ‖g(x)‖2/2 ] + d log( ) + Tr(D)/2− 1
2 ∑ i logDii. (3)
We also state a general fact about VAEs for the case that the objective value can be driven to −∞, which was observed in (Dai & Wipf, 2019): they must satisfy → 0 and achieve perfect limiting reconstruction error. The first claim in this Lemma is established in the proof of Theorem 4 and the second claim is Theorem 5 in Dai & Wipf (2019). For completeness, we include a self-contained proof in Appendix B.1. Lemma 1 (Theorems 4 and 5 of Dai & Wipf (2019)). Suppose ft, gt, Dt, t for t ≥ 1 are a sequence such that limt→∞ L(ft, gt, Dt, t) = −∞. Then: 1) limt→∞ t = 0 and 2) limt→∞ Ex∼p∗Ez′∼N(0,Ir)‖x− ft(gt(x) +D 1/2 t z ′)‖2 = 0.
In fact, the reconstruction error and are closely linked in a simple way: Lemma 2. If f, g,D are fixed, then the optimal value of to minimize L is given by =√
1 dEx∼p∗Ez′∼N(0,Ir)
[ ‖x− f(g(x) +D1/2z′)‖2 ] .

heading: 4.1 LINEAR VAE
text: Setup: In the linear VAE case, we assume the data is generated from the model x = Az with A ∈ Rd×r∗ and z ∼ N (0, Ir∗). We will denote the training parameters by Ã ∈ Rd×r, B̃ ∈ Rr×d, D̃ ∈ Rr×r, and ̃ > 0, where r ≥ 1 is a fixed hyperparameter which corresponds to the latent dimension in the trained generator, and we assume D̃ is a diagonal matrix. With this notation in place, the implied VAE has generator/decoder x̃ ∼ N (Ãz, ̃2Id) and encoder z̃ ∼ N (B̃x, D̃). The VAE objective as a function of parameters Θ̃ = (Ã, B̃, D̃, ̃) is (see Appendix A):
L(Θ̃) = 1
2̃2 ‖A− ÃB̃A‖2F +
1 2 ‖B̃A‖2F + d log ̃+ 1 2 ∑ i ( D̃ii‖Ãi‖2/̃2 + D̃ii − log D̃ii ) (4)
Our analysis makes use of a simplified objective L1, which “eliminates” D out of the objective by plugging in the optimal value of D for a choice of the other variables. We use this as a technical tool when analyzing the landscape of the original loss L.
Lemma 3 (Deriving the simplified loss L1). Suppose that Ã, B̃, ̃ are fixed. Then the objective L is minimized by choosing for all i that D̃ii = ̃ 2
‖Ãi‖2+̃2 where Ãi is column i of Ã, and for
L1(Ã, B̃, ̃) := minD̃ L(Ã, B̃, D̃, ̃) it holds that
L1(Ã, B̃, ̃) = 1
2̃2 ‖A− ÃB̃A‖2F +
1 2 ‖B̃A‖2F + (d− r) log ε̃+ ∑ i
1 + log ( ‖Ãi‖2 + ̃2 ) 2 . (5)
Taking advantage of this simplified formula, we can then identify (for the original lossL) simple sufficient conditions on Ã, B̃ which ensure they can be used to approach the population loss minimum by picking suitable ̃t, D̃t and prove matching necessary conditions.
Theorem 3. First, suppose that Ã : d × r, B̃ : r × d are fixed matrices such that A = ÃB̃A and suppose that #{i : Ãi = 0} > r − d, i.e. the number of zero columns of Ã is strictly larger than r− d. Then for any sequence of positive ̃t → 0 there exist a sequence of positive diagonal matrices D̃t such that:
1. For every i such that Ãi 6= 0, i.e. column i of Ã is nonzero, we have (D̃t)ii → 0.
2. limt→∞ L(Ã, B̃, D̃t, ̃t) = −∞.
Conversely, suppose that that Ãt, B̃t, D̃t, ̃t is an arbitrary sequence such that limt→∞ L(Ãt, B̃t, D̃t, ̃t) = −∞. Then as t→∞, we must have that:
1. ̃t → 0 and ‖A− ÃtB̃tA‖2F → 0.
2. maxi(D̃t)ii‖(Ãt)i‖2F → 0 where (Ãt)i denotes the i-th column of Ãt.
3. For any δ > 0, lim inft→∞#{i : ‖(Ãt)i‖22 < δ} > r − d, i.e. asymptotically Ãt has strictly more than r − d columns arbitrarily close to zero.

heading: In particular, if (Ãt, B̃t, D̃t, ̃t) converge to a point (Ã, B̃, D̃, ̃) then ̃ = 0, A = ÃB̃A, D̃ii = 0
text: for every i such that Ãi 6= 0, and #{i : Ãi = 0} > r − d.
For the sufficiency direction, we observe that in (5) the first term is zero if A = ÃB̃A and the sum of the last two terms goes to −∞ if ̃ → 0 and enough columns of Ã are zero. Based upon similar reasoning combined with Lemma 1, we show necessity. The full proof is in the Appendix.

heading: 4.2 NONLINEAR VAE
text: In this section, we give a simple example of a nonlinear VAE architecture which can represent the ground truth distribution perfectly, but has another asymptotic global minimum where it outputs data lying on a manifold of a larger dimension (r∗ + s instead of r∗ for any s ≥ 1). The ground truth model is a one-layer network (“sigmoid dataset” in Section 6) and the bad decoder we construct outputs a standard Gaussian in r∗ + s dimensions padded with zeros. Theorem 4 (Theorem 6 in Appendix). Let s ≥ 1 be arbitrary and consider the sigmoid setup from Section 6. There exists Ã1, Ã2, B̃ s.t. for ̃t → 0 there exists D̃t s.t. (1) the VAE loss L(Ã1, Ã2, B̃, D̃t, ̃t) → −∞; (2) The output of the decoder x̃ = Ã1z̃ + σ(Ã2z̃), z̃ ∼ N(0, Ir) is a standard Gaussian in the first r∗ + s coordinates and zero in the remaining ones.
Thus, the generator constructed has as support a manifold of larger dimension (r∗ + s). Moreover, in Section 6, we show that this is not merely a theoretical possibility: we show through simulations that gradient descent from a random initialization often converges to similar minima.

heading: 5 IMPLICIT BIAS OF GRADIENT DESCENT IN LINEAR VAE
text: In this section, we prove that even though the landscape of the VAE loss contains generators with strictly larger support than the ground truth, the gradient flow is implicitly biased towards low-rank
solutions. We prove this for the simplified loss L1(Ã, B̃, ̃) = minD̃ L1(Ã, B̃, ̃, D̃), which makes the calculations more tractable, though we believe our results should hold for the original loss L as well. The main result we prove is as follows: Theorem 5 (Implicit bias of gradient descent). LetA : d×r be arbitrary and defineW to be the span of the rows ofA, let Θ̃(0) = (Ã(0), B̃(0), ̃(0)) be an arbitrary initialization and define the gradient flow Θ̃(t) = (Ã(t), B̃(t), ̃(t)) by the differential equation (1). with initial condition Θ̃0. If the solution to this equation exists on the time interval [0, T ] and satisfies maxt∈[0,T ] maxj [‖(Ãt)j‖2 + ̃2t ] ≤ K, then for all t ∈ [0, T ] we have
d∑ k=dim(W )+1 σ2k(Ã(t)) ≤ ‖PW⊥ÃT (t)‖2F ≤ e−t/K‖PW⊥ÃT (0)‖2F (6)
where PW⊥ is the orthogonal projection onto the orthogonal complement of W .
Towards showing the above result, we first show how to reduce to matrices where A has d − dim(rowspan(A)) rows that are all-zero. To do this, we observe that the linear VAE objective is invariant to arbitrary rotations in the output space (i.e. x-space), so the gradient descent/flow trajectories transform naturally under rotations. Thus, we can “rotate” the ground truth parameters as well as the training parameters.
This is formally captured as Lemma 6 in the Appendix. Recall that by the singular value decomposition A = USV T for some orthogonal matrices U, V and diagonal matrix S, and rotation invariance in the x-space lets us reduce to analyzing the case where U = I , i.e. A = SV T . This matrix has a zero row for every zero singular value.
Analysis when A has zero rows. Having reduced our analysis to the case where A has zero rows, the following key lemma shows that for every i such that row i of A (denoted A(i)) is zero, the gradient descent step−∇L or−∇L1 will be negatively correlated with the corresponding row Ã(i). Lemma 4 (Gradient correlation). If row i of A is zero, then
r∑ j=1 Ãij ∂L ∂Ãij ≥ r∑ j=1 D̃jjÃ 2 ij/̃ 2,
r∑ j=1 Ãij ∂L1 ∂Ãij ≥ r∑ j=1
Ã2ij
‖Ãj‖2 + ̃2 .
The way we use it is to notice that since the negative gradient points towards zero, gradient descent will shrink the size of Ã(i). Since the size of the matrix Ã stays bounded, this should mean that for small step sizes the norm of row i of Ã shrinks by a constant factor at every step of gradient descent on loss L1. We formalize this in continuous time for the gradient flow, i.e. the limit of gradient descent as step size goes to zero: for the special case of Theorem 2 in the zero row setting, the corresponding rows of Ã decay exponentially fast.
Lemma 5 (Exponential decay of extra rows). LetA be arbitrary, and let Θ̃(0) = (Ã(0), B̃(0), ̃(0)) be an arbitrary initialization and define the gradient flow Θ̃(t) = (Ã(t), B̃(t), ̃(t)) to be a solution of the differential equation (1) with initial condition Θ̃(0). If the solution exists on the time interval [0, T ] and satisfies maxt∈[0,T ] maxj [‖(Ã(t))j‖2 + ̃(t)2] ≤ K for some K > 0, then for all i such that row i of A is zero we have ‖Ã(i)(t)‖2 ≤ e−t/K‖Ã(i)(0)‖2 for all t ∈ [0, T ].

heading: 6 SIMULATIONS
text: In this section, we provide extensive empirical support for the questions we addressed theoretically. In particular we investigate the kinds of minima VAEs converge to when optimized via gradient descent over the course of training.
Linear VAEs: First, we investigate whether linear VAEs are able to find the correct support for a distribution supported over a linear subspace. The setup is as follows. We choose a ground truth linear transformation matrix A by concatenating an r∗ × r∗ matrix consisting of iid standard Gaussian entries with a zero matrix of dimension (d − r∗) × r∗; the data is generated as Az, z ∼ N (0, Ir∗). Thus the data lies in a r∗-dimensional subspace embedded in a d-dimensional space.
We ran the experiment with various choices for r∗, d as well as the latent dimension of the trained decoder (Table 1). Every result is the mean over three experiments run with the same dimensionality and setup but a different random seed.
Results: From Table 1 we can see that the optima found by gradient descent capture the support of the manifold accurately across all choices of d, r, with the correct number of nonzero decoder rows. We also almost always see the correct number of zero dimensions in the diagonal matrix corresponding to the encoder variance.
However, gradient descent is unable to recover the density of the data on the learned manifold in the linear setting — in sharp contrast to the full rank case (Lucas et al., 2019). We conclude this by comparing the eigenvalues of the data covariance matrix and the learned generator covariance matrix. In order to understand whether the distribution on the linear subspace has the right density, we compute the eigenvalue error by forming matrices X, X̂ with n rows, for which each row is sampled from the ground truth and learned generator distribution respectively. We then compute the vector of eigenvalues λ, λ̂ for the ground truth covariance matrix AAT and empirical covariance matrix (1/n)X̂T X̂ respectively and compute the normalized eigenvalue error ||λ̂− λ||/||λ||. In no case does the density of the learned distribution come close to the ground truth.
Nonlinear Dataset In this section, we investigate whether VAEs are able to find the correct support in nonlinear settings. Unlike the linear setting, there is no “canonical” data distribution suited for a nonlinear VAE, so we explore two setups:
• Sphere dataset: The data are generated from the unit sphere concatenated with zero padding at the end. This can be interpreted as a unit sphere embedded in a higher dimensional space. We used 3 layers of 200 hidden units to parameterize our encoder and decoder networks. To measure how well the VAE has learnt the support of the distribution, we evaluate the average of (‖x̃:(r+1)‖2 − 1)2, where x̃ are generated by the learnt generator. We will call this quantity manifold error. We have also evaluated the padding error, which is defined as ‖x̃r+2:‖22. • Sigmoid Dataset: Let z ∼ N (0, Ir), the sigmoid dataset concatenates z with σ(〈a∗, z〉) where a∗ ∈ Rr is generated according to N (0, Ir). We add additional zero paddings to embed the generated data in a higher dimensional ambient space. The decoder is parameterized by a nonlinear function f(z) = Ãz + σ(C̃z) and the encoder is parameterized by a linear function g(x) = B̃x . The intrinsic dimension of the dataset is r. To measure how well the VAE has learnt the support of the distribution, we evaluate the average of (σ(〈a∗, x̃:r〉)− x̃r+1)2, where x̃ are generated by the learnt decoder. We will call this quantity manifold error. The padding error is defined as similarly as the sphere dataset.
Results: Due to space constraints, results for the sphere dataset (Table 3 and Figure 3) are in Appendix D. In both of the nonlinear dataset experiments, we see that the number of zero entries in the diagonal encoder variance is less reflective of the intrinsic dimension of the manifold than the linear dataset. It is, however, at least as large as the intrinsic dimension (Table 3, 2). We consider a coordinate to be 0 if it’s less than 0.1. We found that the magnitude of each coordinate to be well separated, i.e. the smaller coordinates tend to be smaller than 0.1 and the larger tend to be bigger than 0.5. Thus the threshold selection is not crucial. We did not include padding error in the tables because it reaches zero in all experiments
We show the progression of manifold error, decoder variance and VAE loss during training for the sphere data in Figure 3 and for the sigmoid data in Figure 2, which are included in Appendix D due to space constraints. Datasets of all configurations of dimensions reached close to zero decoder variances, meaning the VAE loss is approaching−∞. To demonstrate Theorem 6, we took examples from both datasets to visualize their output.
For the sphere dataset, we visualize the data generated from the model, with 8 latent dimensions, trained on unit sphere with 2 intrinsic dimensions and 16 ambient dimensions (Column 2 in Table 3). Its training progression is shown as the orange curve in Figure 3 . We create a histogram of the norm of its first 3 dimensions (Figure 1 (a)) and found that more than half of the generated data falls inside of the unit sphere. The generated data has one intrinsic dimension higher than its training data, despite its decoder variance approaching zero, which is equivalent to its reconstruction error approaching zero by Lemma 2.
In the sigmoid dataset, the featured model has 24 latent dimension, and is trained on a 7-dimensional manifold embedded in a 28-dimensional ambient space. We produced a scatter plot given 1000 generated data points x̃r+1 from the decoder. The x-axis in the Figure 1(b) is 〈a∗, x̃:r〉 and the y-axis is x̃r+1. In contrast to the groundtruth data, whose scatter points roughly form a sigmoid function, the scatter points of the generate data resemble a gaussian distribution. This closely resembles the example provided in Theorem 6. Hence, despite its decoder variance and reconstruction error both approaching zero and loss consistently decreasing, the generated data do not recover the training data distribution and the data distribution recovered has higher intrinsic dimensions than the training data. We also investigated the effect of lower bounding the decoder variance as a possible way to improve the VAE performance (details are given in Appendix E). This enabled the VAE to recover the correct manifold dimension in the sigmoid example, but not the sphere example; methods of improvements to the VAE’s manifold recovery is an important direction for future work.

heading: A DERIVATIONS OF VAE LOSSES
text: We have (for some constants C1, C2, C3):
log p(x|z) = − 1 2 2 ‖x− f(z)‖2 − d log( ) + C1
log p(z) = −‖z‖2/2 + C2
log q(z|x) = −1 2 〈z − g(x), D−1(z − g(x)〉 − log
√ detD + C3
where the first line uses that log √ det 2I = log √ 2d = d log( ). The VAE objective is to maximize the expectation of log p(x|z) + log p(z) − log q(z|x) for x from the data p∗ and z ∼ q(z|x). This means that explicitly the objective is to maximize
Ex∼p∗Ez∼q(z|x) [log p(x|z) + log p(z)− log q(z|x)]− C = Ex∼p∗Ez∼q(z|x) [ − 1
2 2 ‖x− f(z)‖2 − d log( )− ‖z‖2/2 + 1 2 〈z − g(x), D−1(z − g(x)〉+ log
√ detD ] = Ex∼p∗Ez′∼N(0,Ir) [ − 1
2 2 ‖x− f(g(x) +D1/2z′)‖2 − d log( )− ‖g(x) +D1/2z′‖2/2
+ 1
2 〈z′, z′〉+ log
√ detD ] which simplifies to (up to additive constant)
Ex∼p∗Ez′∼N(0,Ir) [ − 1
2 2 ‖x− f(g(x) +D1/2z′)‖2 − ‖g(x)‖2/2
] − d log( )− Tr(D)/2 + 1
2 ∑ i logDii.
and converting this to minimization form gives the VAE Loss (3).
Linear VAE derivation. Plugging in the linear VAE parameters into the loss function, we get L(Ã, B̃, D̃, ̃) := Ex∼p∗Ez′∼N(0,Ir̃) [ 1
2̃2 ‖x− Ã(B̃x+ D̃1/2z′)‖2 + ‖B̃x‖2/2
] (7)
+ d log(̃) + Tr(D̃)/2− 1 2 ∑ i log D̃ii (8)
We can write out the expectation as: Ez∼N(0,I)Ez′∼N(0,Ir̃) [ 1
2̃2 ‖Az − Ã(B̃Az + D̃1/2z′)‖2 + ‖B̃Az‖2/2 ] = Ez∼N(0,I)Ez′∼N(0,Ir̃) [ 1 2̃2 ‖(A− ÃB̃A)z − ÃD̃1/2z′‖2 + ‖B̃Az‖2/2
] = 1
2̃2 ‖A− ÃB̃A‖2F +
1
2̃2 ‖ÃD̃1/2‖2F +
1 2 ‖B̃A‖2F
where we used that z, z′ are independent and the identity Ez∼N(0,I)‖Mz‖2 = 〈MMT , I〉 = ‖M‖2F . Next, we can observe that
‖ÃD̃1/2‖2F = ∑ i D̃ii‖Ãi‖2
where Ãi is the i-th column of the matrix Ã. Therefore we recover (4).

heading: B DEFERRED PROOFS FROM SECTION 4
text: B.1 GENERAL FACTS
Proof of Lemma 1. For completeness, we include the proof of these claims; they are similar to the proofs of Theorems 4 and 5 in Dai & Wipf (2019).
First, consider the objective for fixed f, g,D, and omit the subscript t. We have Ex∼p∗Ez′∼N(0,Ir) [ 1
2 2 ‖x− f(g(x) +D1/2z′)‖2 + ‖g(x)‖2/2
] ≥ 0
and Tr(D)/2− 1
2 ∑ i logDii = 1 2 ∑ i (Dii − logDii) ≥ r/2
from the inequality x − log x ≥ 1 for x ≥ 0. Since these terms are both bounded above, the only way the objective goes to negative infinity is if d log → −∞ which means → 0.
Now that we know t → 0, we claim that limt→∞ Ex∼p∗Ez′∼N(0,Ir)‖x−ft(gt(x)+D 1/2 t z ′)‖2 = 0. Suppose otherwise: then this for infinitely many t this quantity is lower bounded by some constant c > 0, hence the objective for those t is lower bounded by c/ 2 + d log( ) + r/2 and this goes to +∞ as → 0, instead of −∞.
Proof of Lemma 2. Taking the partial derivative of (3) with respect to and setting it to zero gives
0 = − 1 3 Ex∼p∗Ez′∼N(0,Ir)‖x− f(g(x) +D 1/2z′)‖2 + d
and solving for gives the result.
B.2 LINEAR VAE
Proof of Lemma 3. Taking the partial derivative with respect to D̃ii gives 0 = ‖Ãi‖2/̃2+1−1/D̃ii which means
D̃ii = 1
‖Ãi‖2/̃2 + 1 =
̃2
‖Ãi‖2 + ̃2
hence
D̃ii‖Ãi‖2/̃2 + D̃ii − log D̃ii = 1− log ̃2
‖Ãi‖2 + ̃2 .
It follows that the objective value at the optimal D is
L1(Ã, B̃, ̃) = 1
2̃2 ‖A− ÃB̃A‖2F +
1 2 ‖B̃A‖2F + d log ̃+ 1 2 ∑ i ( 1− log ̃ 2 ‖Ãi‖2 + ̃2 ) = 1
2̃2 ‖A− ÃB̃A‖2F +
1 2 ‖B̃A‖2F + (d− r) log ε̃+ 1 2 ∑ i ( 1− log 1 ‖Ãi‖2 + ̃2 ) .
Proof of Theorem 3. First we prove the sufficiency direction, i.e. that if A = ÃB̃A and there exists i such that Ãi = 0 then we show how to drive the loss to−∞. By Lemma 3, if we make the optimal choice of D (which clearly satisfies the conditions on D described in the Lemma) the objective simplifies to
L1(Ã, B̃, ̃) = 1
2̃2 ‖A− ÃB̃A‖2F +
1 2 ‖B̃A‖2F + (d− r) log ε̃+ 1 2 ∑ i ( 1 + log ( ‖Ãi‖2 + ̃2 )) = 1
2 ‖B̃A‖2F + (d− r) log ε̃+
1
2 ∑ i ( 1 + log ( ‖Ãi‖2 + ̃2 ))
where in the second line we used the assumptionA = ÃB̃A. Note that for each zero column Ãi = 0 we have (1/2) log(‖Ãi‖2 + ̃2) = log ̃ so the objective will go to −∞ provided (d − r + #{i : Ãi = 0}) log ̃→ −∞. Since ̃→ 0 this is equivalent to asking d− r+ #{i : Ãi = 0} > 0, which is exactly the assumption of the Theorem.
Next we prove the converse direction, i.e. the necessary conditions. Note: we split the first item in the lemma into two conclusions in the proof below (so there are four conclusions instead of three). The first conclusion follows from the first conclusion of Lemma 1. The second conclusion of Lemma 1 tells us that
0 = lim t→∞
Ez∼N(0,I)Ez′∼N(0,Ir̃)‖Az−Ãt(B̃tAz+D̃ 1/2 t z ′)‖2 = lim t→∞ ‖A−ÃtB̃tA‖2F+‖ÃtD̃ 1/2 t ‖2F
which gives us the second and third conclusions above. For the fourth conclusion, since L1(Ãt, B̃t, D̃t) ≤ L(Ãt, B̃t, D̃t, ̃t) we know that limt→∞ L1(Ãt, B̃t, D̃t) = −∞ and recalling
L1(Ã, B̃, ̃) = 1
2̃2 ‖A− ÃB̃A‖2F +
1 2 ‖B̃A‖2F + (d− r) log ̃+ 1 2 ∑ i ( 1 + log ( ‖Ãi‖2 + ̃2 )) we see that, because the first two terms are nonnegative, this is possible only if the sum of the last two terms goes to −∞. Based on similar reasoning to the sufficiency case, this is only possible if strictly more than r − d of the columns of (Ãt) become arbitrarily close to zero; precisely, if there exists δ such that at most r − d of the columns of Ãt have norm less than δ, then
(d− r) log ̃+ 1 2 ∑ i ( 1 + log ( ‖Ãi‖2 + ̃2 )) ≥ 1
2 ∑ i:‖Ãi‖≥δ ( 1 + log ( ‖Ãi‖2 + ̃2 )) ≥ 1
2 ∑ i:‖Ãi‖≥δ ( 1 + log ( δ2 + ̃2 )) which does not go to −∞ as ̃→ 0 (and the other terms of L1 are nonnegative).
B.3 NONLINEAR VAE
We give the full details of the construction of the bad nonlinear VAE optimum and prove that it is an asymptotic global minimum. (Note: in the notation of Section 6 we are considering a∗ with 0/1 entries, but the proof generalizes straightforwardly for arbitrary a∗ with the correct support.)
Setup: Suppose s ≥ 1 is arbitrary and the ground truth x ∈ Rd with d > r∗+s is generated in the following way: (x1, . . . , xr∗) ∼ N(0, Ir∗), xr∗+1 = σ(x1 + · · ·+xr∗) for an arbitrary nonlinearity σ, and xr∗+2 = · · · = xd = 0. Furthermore, suppose the architecture for the decoder with latent dimension r > r∗ + 1 is
fÃ1,Ã2(z) := Ã1z + σ ( Ã2z ) where σ(·) is applied as an entrywise nonlinearity, and the encoder is linear, g(x) := B̃x.
Observe that the ground truth decoder can be expressed by taking Ã2 to have a single nonzero row in position r + 1 with entries (1, . . . , 1, 0, . . . , 0),
Ã1 = [ Ir∗ 0 0 0 ] , B̃ = [ Ir∗ 0 0 0 ] .
where B̃ is a ground truth encoder which achieves perfect reconstruction.
On the other hand, the following VAE different from the ground truth achieves perfect reconstruction:
Ã1 =
[ Ir∗+s 0
0 0
] , Ã2 = 0, B̃ = [ Ir∗+1 0
0 0
] (9)
The output of this decoder is a Gaussian N ( 0, [ Ir∗+s 0
0 0
]) , which means it is strictly higher-
dimensional than the ground truth dimension r∗. (This also means that if we drew the corresponding plot of to Figure 1 (b) for this model, we would get something that looks just like the experimentally obtained result.) We prove in the Appendix that it this is an asymptotic global optima: Theorem 6. Let s ≥ 1 be arbitrary and the ground truth and VAE architecture is as defined as above. For any sequence ̃t → 0, there exist diagonal matrices D̃t such that:
1. the VAE loss L(Ã1, Ã2, B̃, D̃t, ̃t)→ −∞ where Ã1, Ã2, B̃ are defined by (9)
2. The number of coordinates of D̃t which go to zero equals r∗ + s.
Proof. We show how to pick D̃t as a function of ̃t and that if ̃t → 0, the loss goes to −∞. From now on we drop the subscripts.
With these parameters, the VAE loss is Ex∼p∗Ez′∼N(0,Ir) [ 1
2̃2 ‖x− f(g(x) + D̃1/2z′)‖2 + ‖g(x)‖2/2
] + d log(̃) + Tr(D̃)/2− 1
2 ∑ i log D̃ii
= (1/2̃2) r∗+1∑ i=1 D̃ii + Ex∼p∗ [ ‖x1:r∗+1‖2/2 ] + d log(̃) + Tr(D̃)/2− 1 2 ∑ i log D̃ii.
Taking the partial derivative with respect to D̃ii for i ≤ r∗ + s and optimizing gives 0 = (1/̃2) + 1− 1/D̃ii i.e.
D̃ii = 1
1 + 1/̃2 =
̃2
̃2 + 1 and plugging this into the objective gives
(1/2̃2) r∗+1∑ i=1 D̃ii + Ex∼p∗ [ ‖x1:r∗+1‖2/2 ] + d log(̃) + Tr(D̃)/2− 1 2 ∑ i log D̃ii
= (1/2) r∗+1∑ i=1 1 ̃2 + 1 + Ex∼p∗ [ ‖x1:r∗+1‖2/2 ] + (d− r∗ − s) log(̃)
+ Tr(D̃)/2 + r∗ + 1
2 log(1 + 2) +
1
2 r∑ i=r∗+2 log D̃ii.
Setting the remaining D̃ii to 1, we see that using d > r∗ + s that the loss goes to −∞ provided ̃→ 0, proving the result.

heading: C DEFERRED PROOFS FROM SECTION 5
text: First, we formalize the rotation invariance of the objective. Lemma 6 (Rotational Invariance of Gradient Descent on Linear VAE). Let LA(Ã, B̃, D̃, ̃) denote the VAE population loss objective (4). Then for an arbitrary orthogonal matrix U , we have
LA(Ã, B̃, D̃, ̃) = LUA(UÃ, B̃U T , D̃, ̃).
Furthermore, U∇ÃLA(Ã, B̃, D̃, ̃) = ∇UÃLUA(UÃ, B̃U T , D̃, ̃) and (∇B̃LA(Ã, B̃, D̃, ̃))U T = ∇UB̃LUA(UÃ, B̃U T , D̃, ̃). As a consequence, if for any η ≥ 0 we define (Ã1, B̃1, D̃1, ̃1) = (Ã, B̃, D̃, ̃)− η∇LA(Ã, B̃, D̃, ̃) then
(UÃ1, B̃1U T , D̃1, ̃1) = (UÃ, B̃U T , D̃, ̃)− η∇(UÃ,B̃UT ,D̃,̃)LUA(UÃ, B̃U T , D̃, ̃),
i.e. gradient descent preserves rotations by U . The same result holds for the gradient flow (i.e. continuous time gradient descent), or replacing everywhere the loss L by the simplified loss L1.
Proof of Lemma 6. We give the proof for L as stated, but it is exactly the same for the simplified loss L1.
From the objective function (4) and UT = U−1 observe that
LUA(UÃ, B̃U T , D̃, ̃)
= 1
2̃2 ‖UA− UÃB̃U−1UA‖2F +
1 2 ‖B̃U−1UA‖2F + d log ̃+ 1 2 ∑ i ( D̃ii‖UÃi‖2/̃2 + D̃ii − log D̃ii ) = 1
2̃2 ‖A− ÃB̃A‖2F +
1 2 ‖B̃A‖2F + d log ̃+ 1 2 ∑ i ( D̃ii‖Ãi‖2/̃2 + D̃ii − log D̃ii ) = LA(Ã, B̃, D̃, ̃).
Then from the above and the multivariate chain rule have
∇ÃLA(Ã, B̃, D̃, ̃) = ∇ÃLUA(UÃ, B̃U T , D̃, ̃) = UT ( ∇UÃLUA(UÃ, B̃U −1, D̃, ̃) )
so multiplying both sides on the left byU and usingUT = U−1 gives the second claim, and similarly
∇B̃LA(Ã, B̃, D̃, ̃) = ∇B̃LUA(UÃ, B̃U T , D̃, ̃) = (∇B̃UTLUA(UÃ, B̃U T , D̃, ̃))U
gives the third claim. Then the gradient descent claim follows immediately.
Proof of Lemma 4. First we prove the conclusion for the original loss L. Since (ÃB̃A)i` =∑ j,k ÃijB̃jkAk` we have that
∂‖A− ÃB̃A‖2F ∂Ãij = ∂ ∂Ãij ∑ ` Ai` −∑ j′,k Ãij′B̃j′kAk` 2 = ∑ ` 2 Ai` −∑ j′,k Ãij′B̃j′kAk` (−∑ k B̃jkAk` ) and if we know the corresponding row i in A is zero then this simplifies to
∂‖A− ÃB̃A‖2F ∂Ãij = ∑ ` 2 ∑ j′,k Ãij′B̃j′kAk` (∑ k B̃jkAk` ) which means that∑
j
Ãij ∂‖A− ÃB̃A‖2F ∂Ãij = ∑ ` 2 ∑ j,k ÃijB̃jkAk` 2 = 2‖(ÃB̃A)(i)‖2 where the notation A(i) denotes row i of matrix A. Thus, for this term the gradient with respect to row Ã(i) has nonnegative dot product with row Ã(i).
Also, ∂
∂Ãij (1/2) ∑ i D̃jj‖Ãj‖2/̃2 = D̃jjÃij/̃2
and so ∑ j Ãij ∂ ∂Ãij (1/2) ∑ j D̃j‖Ãj‖2/̃2 = ∑ j D̃jjÃ 2 ij/̃ 2
which gives the first result.
For the second result with the simplified loss L1, observe that
∂
∂Ãij ∑ k log(‖Ãk‖2 + ̃2) = 2Ãij ‖Ãj‖2 + ̃2
so ∑ j Ãij ∂ ∂Ãij ∑ k log(‖Ãk‖2 + ̃2) = ∑ j
2Ã2ij
‖Ãj‖2 + ̃2
and the other terms in the loss behave the same in the case of L. Including the factor of 1/2 from the loss function gives the result.
Proof of Lemma 5. From Lemma 4 we have that for any such row i,
d dt ‖Ã(i)(t)‖2 = 2〈Ã(i)(t), d dt Ã(i)(t)〉
= 2〈Ã(i)(t),−∇Ã(t)(i)L1(Θt)〉 ≤ − r∑ j=1
(Ã(t))2ij
‖(Ã(t))j‖2 + ̃2t ≤ −(1/K)‖Ã(i)(t)‖2
which by Gronwall’s inequality implies ‖Ã(i)(t)‖2 ≤ e−t/K‖Ã(i)(0)‖2 as desired.
Proof of Theorem 5. Before proceeding, we observe that the first inequality in (6) is a consequence of the general min-max characterization of singular values, see e.g. Horn & Johnson (2012). We now prove the rest of the statement.
As explained at the beginning of the section, we start by taking the Singular Value Decomposition A = USV T where S is the diagonal matrix of singular values and U, V are orthogonal. We assume the diagonal matrix S is sorted so that its top-left entry is the largest singular value and its bottomright is the smallest. Note that this means the first dim(W ) rows of U are an orthonormal basis for W . Note that for any time t, ‖PW⊥ÃT (t)‖2F = ∑d i=dim(W )+1 ‖(UÃ(t)T )i‖2 because the rows (Udim(W )+1, . . . , Ud) are an orthonormal basis for W⊥. Therefore we have that
‖PW⊥ÃT (t)‖2F = d∑
i=dim(W )+1
‖(UÃ(t)T )i‖2
≤ e−t/K d∑
i=dim(W )+1
‖(UÃ(0)T )i‖2 = e−t/K‖PW⊥ÃT (0)‖2F ,
proving the result, provided we justify the middle inequality. Define A∗ := UTA = SV T , which has a zero row for every zero singular value ofA, and apply Lemma 5 (using that the definition ofK is invariant to left-multiplication of Ã by an orthogonal matrix) and Lemma 6 to conclude that the rows of UT Ã(t), i.e. the columns of UÃ(t)T , corresponding to zero rows of A∗ shrink by a factor of e−t/K . This directly gives the desired inequality, completing the proof.

heading: D DEFERRED FIGURES AND PLOTS FROM SECTION 6
text: Eigenvalues of Linear Data. As we’ve discussed, in our linear setting the VAE does not recover the ground truth data density. Since our generative process for ground-truth data is x = Az for a matrix A and z normally distributed, we can characterize the density function by the eigenvalues of the true or estimated covariance matrix. We give figures for the normalized error of these eigenvalues between the learned generator and the ground truth in Table 1. A concrete example of eigenvalue mismatch for a problem with 6 nonzero dimensions is a ground-truth set of covariance eigenvalues
λ = [0.001 0.156 1.54 5.06 9.55 16.4]
while the trained linear VAE distribution has covariance eigenvalues
λ̂ = [0.035 0.166 1.49 4.24 5.97 7.85] .
Here, the VAE was easily able to learn the support of the data but clearly is very off when it comes to the structure of the covariances.

heading: E EXPERIMENTS WITH DECODER VARIANCE CLIPPING
text: As was suggested by an anonymous ICLR 2022 reviewer, one potential way to evade the results in our paper is to restrict the decoder variance from converging to 0. In this section, we examine (empirically) the impact of clipping the decoder variance during training. We caveat though, that our paper does not analyze the landscape of the resulting constrained optimization problem, so our results don’t imply anything about this regime.
We conduct the same nonlinear experiments described in Section 6 where we fit VAEs to data generated from spheres and linear sigmoid functions. The only change is to clip the decoder variance when it goes below a certain threshold. In the figures below, the chosen threshold is e−4 ≈ 0.018, though we tried also e−2 and e−3, with similar outcomes. We initialize the decoder variance with e−3 for this set of experiments, so the optimization still can decrease it.
With this change, the optimization process on the sigmoid dataset does yield encoder variances with their number of zeros reflective of their intrinsic dimensions as in Table 4. For the sphere experiment, this still does not happen, as in Table 5. In fact, the model consistently recovers one more dimension than the true intrinsic dimension of the manifold and the smaller encoder variances can be as large as 0.1. We also provide a figure (Figure 4) in the same style as Figure 1. We see that training with a clipped decoder variance allows the model to better capture the general shape of the sigmoid function, though the variance of the generated points is high for both of the sphere and sigmoid datasets. Other training details, such as the general trend of manifold error, encoder variance and VAE loss, can be referred to in Figure 5 and 6.
Overall, the benefit of clipping the decoder variance during training is inconclusive as we see inconsistent results in the sphere and sigmoid datasets. Designing more algorithms to improve the ability of VAE’s to recover data supported on a low dimensional manifold is an important direction for future work—both empirical and theoretical.

Review summaries:
This paper builds on a recent theoretical work by Dai & Wipf [1]. Dai & Wipf analyze the *optimal* behavior of VAEs, when applied to manifold-valued data. This work analyzes the *training* behavior of VAEs, when applied to manifold-valued data. Both consider the non-trivial case where the manifold’s intrinsic dimension is lower than the ambient dimension. Dai & Wipf considers VAEs with arbitrarily complex encoders and decoders. The present work considers VAEs with linear encoders and linear/single-hidden layer nonlinear decoders.  [1] Bin Dai and David Wipf. Diagnosing and enhancing vae models. arXiv preprint arXiv:1903.05789, 2019.

The authors study further on the conjectures of Dai & Wipf (2019). For the linear case, they provide the proof that the conjecture is true. For the non-linear case, the paper disagrees with the conjecture, and they argue that the VAE training frequently learns a higher-dimensional manifold which is a superset of the ground truth manifold.   

This paper examines the conjecture given in (Dai & Wipf; 2019) on the support of distribution that VAE learns.  The contributions are listed as follows:  - For the linear case where the data is Gaussian with rank-degenerate covariance, and encoder/decoder are both linear, this paper proves that VAE captures the intrinsic dimension of data distribution correctly by analyzing the objective and its gradient-flow dynamics.  - For nonlinear cases, the paper shows a counterexample to the conjecture in (Dai & Wipf; 2019) where the support of VAE generators is a superset of that of data distribution.  - Numerical experiments are presented to support the theory.