Autoencoders

An autoencoder is a feedforward network trained to approximate the identity function $x \mapsto x$, but constrained so that it cannot simply copy input to output. It is composed of two parts sharing no direct connection except through a latent code. The encoder $f_\theta : \mathbb{R}^n \to \mathbb{R}^d$ maps an input $x$ to a latent representation (also called the code or bottleneck) $z = f_\theta(x)$. The decoder $g_\phi : \mathbb{R}^d \to \mathbb{R}^n$ maps $z$ back to a reconstruction $\hat{x} = g_\phi(z)$. Training minimizes a reconstruction loss $L(x, \hat{x})$ averaged over the training set, typically squared error for continuous data or binary cross-entropy for data in $[0,1]$. The crucial design choice is the capacity of the bottleneck relative to the data. If $d < n$ (an undercomplete autoencoder) and the network is otherwise limited — for instance linear, or nonlinear but not overly deep or wide — then it is mathematically impossible for $z$ to retain all information in $x$ for generic data. The network is forced to discard redundancy and noise, keeping only the statistically dominant structure. This is precisely analogous to classical dimensionality reduction: a linear autoencoder with squared error recovers the same subspace as Principal Component Analysis, though not necessarily the same orthonormal basis or ordering of directions. If instead $d \ge n$ or the encoder/decoder are unconstrained and highly expressive, the autoencoder can in principle learn the identity map exactly — copying each input to a unique code and back — without learning anything about the data distribution. This degenerate solution has zero training loss but zero generalization value; it is the central danger that all practical autoencoder variants (sparse, denoising, contractive, variational) are designed to prevent, a topic taken up in the study of Undercomplete and Regularized Autoencoders. The healthy autoencoder occupies a middle ground: enough capacity to reconstruct well, not enough to memorize trivially, so that the code $z$ captures a useful, compressed, often disentangled summary of the data manifold.

Architecture. The encoder and decoder are each ordinary feedforward stacks (dense layers for vector data, convolutional stacks for images, recurrent or transformer stacks for sequences). A common convention mirrors the encoder architecture in reverse for the decoder, so that layer widths shrink from the input dimension down to $d$, then grow symmetrically back up to $n$. Weights may or may not be tied ($W_{\text{decoder}} = W_{\text{encoder}}^\top$), which halves the parameter count and acts as a mild regularizer.

Loss. For real-valued inputs, mean squared error is standard:

For inputs interpretable as independent probabilities (e.g. normalized pixel intensities), binary cross-entropy is common:

Training. The whole network — encoder and decoder together — is trained end-to-end by ordinary backpropagation and stochastic gradient descent (or a variant like Adam), exactly as with any supervised feedforward network, except the "label" for each input is the input itself. No annotation pipeline is needed, which is the practical appeal: any unlabeled corpus becomes training data. ``` Algorithm: Train-Autoencoder Input: dataset X = {x_1, ..., x_N}, encoder f_theta, decoder g_phi, learning rate eta, batch size B, epochs T Output: trained parameters theta, phi 1 initialize theta, phi (e.g. small random weights) 2 for epoch = 1 to T: 3 shuffle X 4 for each minibatch {x_1, ..., x_B} drawn from X: 5 for each x_i in the minibatch: 6 z_i <- f_theta(x_i) # encode 7 xhat_i <- g_phi(z_i) # decode 8 loss_i <- L(x_i, xhat_i) # e.g. squared error 9 batch_loss <- (1 / B) sum(loss_i) 10 g_theta, g_phi <- backprop(batch_loss, theta, phi) # gradients 11 theta <- theta - eta g_theta # gradient step 12 phi <- phi - eta * g_phi 13 end for 14 end for 15 return theta, phi ``` At inference time, three distinct usages are possible: (a) run only the encoder to obtain a compressed embedding $z$ for downstream tasks; (b) run the full pipeline to denoise or reconstruct a corrupted input; (c) run only the decoder on a chosen or sampled $z$ to generate new outputs (though vanilla autoencoders offer no guarantee that arbitrary $z$ decode to realistic data — that guarantee is added later by variational autoencoders).

Time complexity. Let the encoder and decoder each be feedforward stacks with total parameter count $P$ (sum of weight matrix sizes across all layers). A single forward pass through the whole autoencoder costs $O(P)$ multiply-adds, since each weight is used exactly once per example (dominant cost in dense layers is $O(\text{layer}_{\text{in}} \times \text{layer}_{\text{out}})$, summed over layers). Backpropagation costs the same order, $O(P)$, because the backward pass mirrors the forward pass computation with an additional constant factor. Training for $T$ epochs over $N$ examples with minibatch size $B$ performs $T \cdot N / B$ gradient steps, each costing $O(B \cdot P)$, giving total training time

This is identical in form to training any feedforward network of the same size — an autoencoder is not more expensive per example than a supervised network with matching architecture; the only difference is the loss target.

Space complexity. Storing the parameters requires $O(P)$ memory. Storing activations for backpropagation across $L$ layers with maximum width $W$ requires $O(L \cdot W)$ per example (or $O(B \cdot L \cdot W)$ if a full minibatch's activations are cached simultaneously, as is standard). The bottleneck itself needs only $O(d)$ space, which is the entire point — once trained, a dataset of $N$ items can be stored as $N$ codes of size $d$ plus one decoder, versus $N$ items of size $n$ each, giving a storage ratio of roughly $d/n$ for the compressed representation (ignoring the fixed decoder cost, amortized over large $N$).

Correctness — what "correct" means here. There is no external ground truth to check the autoencoder against, so correctness must be argued at the level of the loss and the capacity constraint, not as convergence to a known function. Two claims need justification. Claim 1: the training loop is a valid instance of standard supervised learning. Because the target for each input $x$ is $x$ itself, the entire apparatus of gradient descent on a differentiable loss composed with differentiable layers applies unchanged. The gradient $\nabla_\theta L$ and $\nabla_\phi L$ are computed by the ordinary chain rule through both decoder and encoder; nothing about self-targets breaks backpropagation's correctness, since backpropagation only requires that the loss be a differentiable function of the parameters through the computational graph, and $L(x, g_\phi(f_\theta(x)))$ is exactly such a function. Claim 2: an undercomplete, capacity-limited bottleneck cannot achieve zero loss on generic data, and thus is forced toward compression rather than memorization. Consider the noiseless linear case: encoder and decoder are linear maps $z = Wx$, $\hat x = W'z$, with $W \in \mathbb{R}^{d\times n}$, $d < n$. The composite map $\hat x = W'Wx$ has rank at most $d < n$. If the data $\{x_i\}$ spans a subspace of dimension greater than $d$ (true for generic real data with more than $d$ independent directions of variance), no choice of $W, W'$ can make $\hat x_i = x_i$ for all $i$ simultaneously — the reconstruction is confined to a $d$-dimensional subspace. Minimizing squared reconstruction error under this rank constraint is a classical low-rank approximation problem, and the Eckart–Young theorem tells us the global minimum is achieved by projecting onto the top-$d$ principal subspace of the data covariance — exactly the PCA solution. This proves, for the linear case, that the bottleneck provably cannot memorize and instead is mathematically driven toward the directions of maximal variance. Nonlinear autoencoders relax the rank restriction (a nonlinear decoder can in principle reconstruct a curved lower-dimensional manifold exactly, called a nonlinear generalization of PCA), so the guarantee weakens to "generically cannot achieve exact reconstruction from an information-theoretically too-small code" rather than a clean rank bound — this is why regularization (sparsity penalties, added noise, weight tying, small width) remains necessary in the nonlinear, high-capacity regime, motivating the regularized variants covered next in this sequence.

Honest tradeoffs. A larger bottleneck $d$ reduces reconstruction error but risks approaching the identity map and yields less useful, less compressed features; a smaller $d$ forces more aggressive compression but increases reconstruction error and can discard information needed downstream. There is no closed-form optimal $d$ in the nonlinear case — it is a hyperparameter tuned against a downstream validation criterion (reconstruction quality, or performance of a classifier trained on the codes).

Take four toy 2D points designed so that one direction carries all the variance and the other is (nearly) constant noise:

Feature 2 hovers around $5.0$ with tiny noise; feature 1 varies meaningfully from 1 to 4. A linear autoencoder with bottleneck $d=1$ should discover this: it needs only feature 1 (plus the constant offset $5.0$ for feature 2) to reconstruct nearly everything. Suppose after mean-centering ($\bar{x} = (2.5, 5.0)$) and training the linear encoder $z = w^\top(x - \bar{x})$, decoder $\hat{x} = \bar{x} + w z$, gradient descent converges to (up to sign) the top principal direction:

Trace it through example $x^{(1)} = (1.0, 5.02)$: 1. Center: $x - \bar{x} = (1.0 - 2.5,\ 5.02 - 5.0) = (-1.5,\ 0.02)$. 2. Encode: $z = w^\top(x-\bar x) = (1.0)(-1.5) + (0.0)(0.02) = -1.5$. 3. Decode: $\hat{x} - \bar x = w z = (1.0)(-1.5), (0.0)(-1.5)) = (-1.5, 0.0)$. 4. Un-center: $\hat{x} = \bar x + (-1.5, 0.0) = (1.0, 5.0)$. 5. Reconstruction error: $\|x^{(1)} - \hat x^{(1)}\|^2 = (1.0-1.0)^2 + (5.02-5.0)^2 = 0.0004$. Repeating for all four points gives reconstructions $(1.0,5.0), (2.0,5.0), (3.0,5.0), (4.0,5.0)$ — feature 1 recovered exactly, feature 2's tiny noise discarded, average squared error $\approx 0.0003$. A single scalar $z$ per point (plus the shared decoder direction $w$ and offset $\bar x$) reconstructs the whole dataset almost perfectly: the bottleneck learned that feature 1 is the informative axis and feature 2's fluctuation is noise not worth spending code capacity on. This is the compression-by-necessity argument from the correctness section made concrete: with $d=1 < n=2$ and data whose dominant variance lies along one axis, the optimal linear autoencoder is forced to discover exactly that axis, matching the PCA solution predicted by the Eckart–Young argument.

The autoencoder's mathematical ancestor is the linear least-squares compression problem solved by principal component analysis, but the neural, nonlinearly-trained version arose from the self-organization and backpropagation research of the 1980s.

Autoencoders and their descendants are embedded throughout modern machine learning systems. Anomaly and fraud detection pipelines train an autoencoder on "normal" transactions or sensor readings and flag high reconstruction error as anomalous, since the network has only learned to compress typical patterns well. Recommender systems and search engines use encoder-derived embeddings for nearest-neighbor retrieval and collaborative filtering. Denoising autoencoders underlie image and audio restoration tools, and the same corruption-and-reconstruct principle scaled up into masked-token pretraining objectives used across modern self-supervised language and vision models. Generative modeling descends directly from this lineage: variational autoencoders impose a probabilistic structure on the latent space to enable controlled sampling and interpolation, and diffusion models' encoder-decoder ("U-Net") backbones and latent-space compression stages borrow the same compress-then-reconstruct skeleton. Medical imaging pipelines use autoencoders to compress scans for storage and to detect abnormal tissue via poor reconstructions. In every case, the underlying mechanism — force a bottleneck, minimize reconstruction error, read out the bottleneck as a representation — is the one built up in this article, and it is the direct on-ramp to the more constrained and structured variants studied under Undercomplete and Regularized Autoencoders and to the general study of learned representations in Embeddings and Representation Learning.

Ask the tutor: How does adding noise to the input during training (a denoising autoencoder) change the mathematical guarantee that the network cannot simply memorize its inputs?