Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Autoencoders & Latent Spaces

Compression as a route to representation.

Squeeze data through a bottleneck and reconstruct it: what does the code learn? For linear maps the answer is exactly the principal subspace, with no bad local minima on the way there. Remove the bottleneck, corrupt the input with noise, and the reconstruction learns something stranger: the gradient of the data's log-density. This lesson proves both theorems, connects autoencoders to rate–distortion theory, and ends with a result that ruled out disentangling factors of variation without assumptions.

What you’ll learn

  • State the Baldi–Hornik theorem and sketch why every critical point other than the PCA solution is a saddle.
  • Prove Tweedie's formula and deduce that an optimal denoising autoencoder estimates σ2∇log⁡pσ\sigma^2\nabla\log p_\sigma.
  • Relate denoising to contractive penalties and sparse autoencoders to dictionary learning, and read autoencoders through rate–distortion theory.
  • State the Locatello et al. impossibility theorem for unsupervised disentanglement and the assumptions that restore identifiability.

The landscape of linear autoencoders

DerivationProof sketch (full-rank critical points)
  1. B=(A⊤A)−1A⊤⟹AB=PA  (orthogonal projector onto col⁡A)B=(A^\top A)^{-1}A^\top\quad\Longrightarrow\quad AB=P_A\ \ \text{(orthogonal projector onto }\operatorname{col}A)

    Expand E=Tr⁡Σ−2Tr⁡(ABΣ)+Tr⁡(ABΣB⊤A⊤)E=\Tr\Sigma-2\Tr(AB\Sigma)+\Tr(AB\Sigma B^\top A^\top). For a fixed decoder, EE is convex in BB, and the gradient 2A⊤(AB−I)Σ2A^\top(AB-I)\Sigma vanishes at the pseudoinverse: the best encoder projects orthogonally onto the decoder's column space.

  2. PAΣPA=ΣPAandPAΣPA=PAΣ⟹ΣPA=PAΣP_A\Sigma P_A=\Sigma P_A\quad\text{and}\quad P_A\Sigma P_A=P_A\Sigma\quad\Longrightarrow\quad\Sigma P_A=P_A\Sigma

    Stationarity in AA gives ABΣB⊤=ΣB⊤AB\Sigma B^\top=\Sigma B^\top. Substitute B=(A⊤A)−1A⊤B=(A^\top A)^{-1}A^\top, multiply on the right by A⊤A^\top and use B⊤A⊤=PAB^\top A^\top=P_A; then transpose:

  3. E=Tr⁡Σ−Tr⁡(PAΣ)=Tr⁡Σ−∑i∈IλiE=\Tr\Sigma-\Tr(P_A\Sigma)=\Tr\Sigma-\sum_{i\in I}\lambda_i

    So col⁡A\operatorname{col}A is an invariant subspace of Σ\Sigma; with distinct eigenvalues it is spanned by kk eigenvectors {ui}i∈I\{\mathbf u_i\}_{i\in I}, and the loss is the variance outside it:

  4. E(θ)=E(0)−(λj−λi)sin⁡2θ<E(0)E(\theta)=E(0)-(\lambda_j-\lambda_i)\sin^2\theta<E(0)

    If I≠{1,…,k}I\neq\{1,\dots,k\}, some i∈Ii\in I and j∉Ij\notin I have λj>λi\lambda_j>\lambda_i. Rotating ui\mathbf u_i toward uj\mathbf u_j by a small angle θ\theta keeps a kk-dimensional subspace and lowers the loss, so the point is not a local minimum:

Kawaguchi (2016) extended the conclusion to deep linear networks of any depth: every local minimum is global, although for depth above three some saddles have no direction of negative curvature, which slows gradient descent. The landscape result says nothing about the basis of the code, which stays arbitrary up to an invertible k×kk\times k map. Adding weight decay breaks that symmetry: the principal directions can then be read off the decoder's singular vectors (Kunin et al., 2019).

Check your understanding

With λ1>λ2>λ3\lambda_1>\lambda_2>\lambda_3 and k=2k=2, gradient descent reaches a critical point whose code spans {u1,u3}\{\mathbf u_1,\mathbf u_3\}. What is it?

  1. A saddle: rotating u3\mathbf u_3 toward u2\mathbf u_2 lowers the loss by (λ2−λ3)sin⁡2θ(\lambda_2-\lambda_3)\sin^2\theta
  2. A spurious local minimum, the reason linear autoencoders need restarts
  3. The global minimum, since u1\mathbf u_1 carries the most variance
  4. A local maximum
Show the answer

A. A saddle: rotating u3\mathbf u_3 toward u2\mathbf u_2 lowers the loss by (λ2−λ3)sin⁡2θ(\lambda_2-\lambda_3)\sin^2\theta

Its loss, λ2+λ4+…\lambda_2+\lambda_4+\dots, exceeds the optimum λ3+λ4+…\lambda_3+\lambda_4+\dots, and an arbitrarily small rotation toward u2\mathbf u_2 decreases it. Generic initializations escape such points: gradient descent converges to the PCA subspace.

Denoising autoencoders learn the score

A denoising autoencoder (Vincent et al., 2008) corrupts the input, x~=x+σε\tilde{\mathbf x}=\mathbf x+\sigma\boldsymbol\varepsilon with ε∼N(0,I)\boldsymbol\varepsilon\sim\mathcal N(\mathbf 0,I), and trains rr to minimize E∥r(x~)−x∥2\E\norm{r(\tilde{\mathbf x})-\mathbf x}^2. Over all functions, squared error is minimized by the conditional mean, r⋆(x~)=E[x∣x~]r^\star(\tilde{\mathbf x})=\E[\mathbf x\mid\tilde{\mathbf x}]. A classical identity says what that mean is.

DerivationProof
  1. pσ(x~)=∫p(x) φσ(x~−x) dx,∇φσ(u)=−uσ2 φσ(u)p_\sigma(\tilde{\mathbf x})=\int p(\mathbf x)\,\varphi_\sigma(\tilde{\mathbf x}-\mathbf x)\,d\mathbf x,\qquad\nabla\varphi_\sigma(\mathbf u)=-\frac{\mathbf u}{\sigma^2}\,\varphi_\sigma(\mathbf u)

    Write the noisy density as a convolution with the Gaussian kernel φσ\varphi_\sigma, whose gradient is explicit:

  2. ∇pσ(x~)=1σ2∫(x−x~) p(x) φσ(x~−x) dx\nabla p_\sigma(\tilde{\mathbf x})=\frac1{\sigma^2}\int(\mathbf x-\tilde{\mathbf x})\,p(\mathbf x)\,\varphi_\sigma(\tilde{\mathbf x}-\mathbf x)\,d\mathbf x

    Differentiate under the integral:

  3. ∇log⁡pσ(x~)=1σ2(E[x∣x~]−x~)■\nabla\log p_\sigma(\tilde{\mathbf x})=\frac1{\sigma^2}\big(\E[\mathbf x\mid\tilde{\mathbf x}]-\tilde{\mathbf x}\big)\qquad\blacksquare

    By Bayes' rule p(x)φσ(x~−x)/pσ(x~)=p(x∣x~)p(\mathbf x)\varphi_\sigma(\tilde{\mathbf x}-\mathbf x)/p_\sigma(\tilde{\mathbf x})=p(\mathbf x\mid\tilde{\mathbf x}), so dividing by pσ(x~)p_\sigma(\tilde{\mathbf x}) turns the integral into a conditional expectation:

  4. E∥r(x~)−x∥2=σ4 E∥s(x~)−∇log⁡pσ(x~)∥2+const\E\norm{r(\tilde{\mathbf x})-\mathbf x}^2=\sigma^4\,\E\norm{s(\tilde{\mathbf x})-\nabla\log p_\sigma(\tilde{\mathbf x})}^2+\text{const}

    Consequently minimizing the denoising loss over rr is least-squares regression of s(x~)=(r(x~)−x~)/σ2s(\tilde{\mathbf x})=(r(\tilde{\mathbf x})-\tilde{\mathbf x})/\sigma^2 onto the score: denoising score matching, the training objective of score-based diffusion models at each noise level (Diffusion Models).

Predict before you look

Data are 1-D Gaussian, x∼N(0,3)x\sim\mathcal N(0,3), and the noise has variance σ2=1\sigma^2=1. The optimal denoiser sees x~=2\tilde x=2. What is r⋆(2)=E[x∣x~=2]r^\star(2)=\E[x\mid\tilde x=2]?

Show the answer

1.5

pσ=N(0,4)p_\sigma=\mathcal N(0,4), so ∇log⁡pσ(x~)=−x~/4\nabla\log p_\sigma(\tilde x)=-\tilde x/4, and Tweedie gives 2+1⋅(−2/4)=1.52+1\cdot(-2/4)=1.5. Equivalently E[x∣x~]=33+1x~\E[x\mid\tilde x]=\frac{3}{3+1}\tilde x, the familiar Gaussian shrinkage: the denoiser pulls toward high density.

Geometrically, near data concentrated on a low-dimensional manifold, noise pushes points off it and r⋆r^\star pulls them back along the normal directions. For small σ\sigma, a Taylor expansion of the loss gives E∥r(x)−x∥2+σ2E∥Jr(x)∥F2\E\norm{r(\mathbf x)-\mathbf x}^2+\sigma^2\E\norm{J_r(\mathbf x)}_F^2: denoising is approximately reconstruction plus a contractive penalty on the reconstruction map, the explicit regularizer of contractive autoencoders (Rifai et al., 2011).

Sparse codes, latent spaces and rate–distortion

Sparse coding (Olshausen & Field, 1996) learns an overcomplete dictionary D∈Rd×mD\in\R^{d\times m}, m>dm>d, by min⁡D,z∑∥x−Dz∥2+λ∥z∥1\min_{D,\mathbf z}\sum\norm{\mathbf x-D\mathbf z}^2+\lambda\norm{\mathbf z}_1; on natural image patches its atoms are localized, oriented, bandpass filters resembling simple cells in visual cortex. A sparse autoencoder amortizes the inner optimization with an encoder z=ReLU(Wex+b)\mathbf z=\mathrm{ReLU}(W_e\mathbf x+\mathbf b), or keeps only the kk largest activations (Makhzani & Frey, 2013). Under incoherence and sparsity assumptions, overcomplete dictionaries are provably recoverable in polynomial time (Arora, Ge & Moitra, 2014). With dictionaries tens of times larger than the activation dimension, sparse autoencoders have become a main tool for decomposing language-model activations into interpretable features (Bricken et al., 2023; Cunningham et al., 2023; see Mechanistic Interpretability).

Why not sample new data by decoding random codes? The encoder maps the data onto an irregular, low-volume region of Rk\R^k, and decoding points outside it gives garbage. Variational autoencoders fix this by pulling the code distribution toward a prior (Variational Autoencoders & the ELBO). Masked autoencoders (He et al., 2022) took the opposite route, using reconstruction of 75% hidden image patches purely as a pretraining task.

Disentanglement and identifiability

A recurring hope is a code whose coordinates are the true factors of variation: x=g(z)\mathbf x=g(\mathbf z) with independent factors ziz_i (pose, lighting, identity), recovered one per latent unit. Methods such as the β-VAE (Higgins et al., 2017) push toward factorized codes. Can any unsupervised method guarantee success?

DerivationProof sketch, and the consequence
  1. h(z)i=Φ−1(Fi(zi)),f=h−1∘R∘hh(\mathbf z)_i=\Phi^{-1}\big(F_i(z_i)\big),\qquad f=h^{-1}\circ R\circ h

    For z∼N(0,I)\mathbf z\sim\mathcal N(\mathbf 0,I), any rotation RR preserves the distribution, and a rotation not aligned with the axes mixes every coordinate into every other. For a general factorized density, map each coordinate to a standard normal with its CDF, rotate, and map back:

  2. x=g(z)=(g∘f−1)(f(z)),f(z)=dz\mathbf x=g(\mathbf z)=\big(g\circ f^{-1}\big)\big(f(\mathbf z)\big),\qquad f(\mathbf z)\overset{d}{=}\mathbf z

    Now the data cannot tell the two models apart: the disentangled pair (g,z)(g,\mathbf z) and the entangled pair (g∘f−1,f(z))(g\circ f^{-1},f(\mathbf z)) generate exactly the same distribution of x\mathbf x. Any method that sees only x\mathbf x must treat them alike.

  3. identifiability ⟸ independence + non-Gaussianity, auxiliary variables or weak supervision\text{identifiability}\ \Longleftarrow\ \text{independence}\ +\ \text{non-Gaussianity, auxiliary variables or weak supervision}

    The Gaussian's rotation invariance is the crux. Linear ICA escapes it: independent non-Gaussian sources mixed linearly are identifiable up to permutation and scaling (Comon, 1994). Nonlinear ICA is not identifiable in general (Hyvärinen & Pajunen, 1999), but becomes identifiable with an auxiliary variable that modulates the factors, such as time or a class label (Hyvärinen, Sasaki & Turner, 2019; Khemakhem et al., 2020).

Locatello et al. also trained thousands of models across methods and datasets and found that differences between disentanglement methods were dominated by random seeds and hyperparameters, and that, without supervision, there was no reliable way to pick a well-disentangled model. Inductive biases and some supervision are not optional extras; they are what makes the problem well posed.

Key takeaways

  • Baldi–Hornik: for linear autoencoders the full-rank critical points are projections onto kk eigenvectors; only the top-kk subspace is a minimum, all others are saddles, and the code's basis stays arbitrary.
  • Tweedie: E[x∣x~]=x~+σ2∇log⁡pσ(x~)\E[\mathbf x\mid\tilde{\mathbf x}]=\tilde{\mathbf x}+\sigma^2\nabla\log p_\sigma(\tilde{\mathbf x}), so optimal denoisers estimate the score; this is denoising score matching, the basis of diffusion models.
  • Small-noise denoising approximates a contractive penalty; sparse autoencoders amortize sparse coding and now decompose language-model activations into features.
  • Rate–distortion theory bounds every autoencoder-as-compressor; for Gaussian data, reverse water-filling drops low-variance components, like PCA.
  • Locatello et al.: distribution-preserving entangling bijections make unsupervised disentanglement non-identifiable; non-Gaussianity, auxiliary variables or supervision restore identifiability.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

In a linear autoencoder, the decoder A∈Rd×kA\in\R^{d\times k} (full rank) is fixed. Which encoder minimizes the squared reconstruction error?

  1. B=A⊤B=A^\top
  2. B=(A⊤A)−1A⊤B=(A^\top A)^{-1}A^\top, so that ABAB projects orthogonally onto the column space of AA
  3. B=A⊤Σ−1B=A^\top\Sigma^{-1}
  4. Any BB with BA=IBA=I
Show the answer

B. B=(A⊤A)−1A⊤B=(A^\top A)^{-1}A^\top, so that ABAB projects orthogonally onto the column space of AA

The gradient 2A⊤(AB−I)Σ2A^\top(AB-I)\Sigma vanishes when A⊤AB=A⊤A^\top AB=A^\top. Then AB=A(A⊤A)−1A⊤AB=A(A^\top A)^{-1}A^\top, the orthogonal projector onto col⁡A\operatorname{col}A: each input is reconstructed by its closest point in the decoder's range.

Question 2

A denoising autoencoder is trained to optimality with small Gaussian noise of variance σ2\sigma^2. What does r(x)−xr(\mathbf x)-\mathbf x approximate?

  1. The noise vector that was added
  2. Zero, since the optimal reconstruction is the identity
  3. σ2∇log⁡p(x)\sigma^2\nabla\log p(\mathbf x), a vector pointing toward higher data density
  4. The first principal component of the data
Show the answer

C. σ2∇log⁡p(x)\sigma^2\nabla\log p(\mathbf x), a vector pointing toward higher data density

Tweedie's formula gives r⋆(x~)−x~=σ2∇log⁡pσ(x~)r^\star(\tilde{\mathbf x})-\tilde{\mathbf x}=\sigma^2\nabla\log p_\sigma(\tilde{\mathbf x}), and pσ→pp_\sigma\to p as σ→0\sigma\to0. This is why denoisers can serve as score estimators for diffusion models.

Question 3

A 3-D Gaussian source has covariance eigenvalues 44, 11 and 0.250.25. Reverse water-filling with level θ=0.5\theta=0.5 gives which rate, in bits per vector?

  1. 11 bit
  2. 33 bits
  3. 2.52.5 bits
  4. 22 bits
Show the answer

D. 22 bits

Components with λi>θ\lambda_i>\theta get 12log⁡2(λi/θ)\tfrac12\log_2(\lambda_i/\theta): 12log⁡28+12log⁡22=1.5+0.5=2\tfrac12\log_28+\tfrac12\log_22=1.5+0.5=2 bits. The third component (0.25<0.50.25<0.5) gets no bits and contributes distortion 0.250.25, for total distortion 0.5+0.5+0.25=1.250.5+0.5+0.25=1.25.

Question 4

Why can no purely unsupervised method guarantee disentangled codes when the true factors are independent?

  1. Current networks are too small to represent the true generator
  2. Entangling bijections preserve the factor distribution, so an entangled model generates exactly the same data distribution as the true one
  3. The factors are never truly independent in real data
  4. Disentanglement metrics are noisy
Show the answer

B. Entangling bijections preserve the factor distribution, so an entangled model generates exactly the same data distribution as the true one

With f(z)=dzf(\mathbf z)\overset{d}{=}\mathbf z, the models (g,z)(g,\mathbf z) and (g∘f−1,f(z))(g\circ f^{-1},f(\mathbf z)) are observationally equivalent, so the data alone cannot favor the disentangled one. Assumptions or supervision must break the tie.

Further reading

  • P. Baldi & K. Hornik, "Neural networks and principal component analysis: Learning from examples without local minima," Neural Networks 2, 53–58 (1989).
  • P. Vincent, H. Larochelle, Y. Bengio & P.-A. Manzagol, "Extracting and composing robust features with denoising autoencoders," ICML (2008).
  • G. Alain & Y. Bengio, "What regularized auto-encoders learn from the data-generating distribution," Journal of Machine Learning Research 15 (2014).
  • F. Locatello, S. Bauer, M. Lucic, G. Rätsch, S. Gelly, B. Schölkopf & O. Bachem, "Challenging common assumptions in the unsupervised learning of disentangled representations," ICML (2019).
  • I. Goodfellow, Y. Bengio & A. Courville, Deep Learning, ch. 14 "Autoencoders" (MIT Press, 2016).