Abstract
Shallow autoencoders are fundamental to unsupervised feature learning, yet their training dynamics under gradient descent (GD) remain poorly understood theoretically. This paper presents the first rigorous proof that GD can successfully train weight-sharing autoencoders to recover underlying parameters in generative data models. By analyzing the interplay between activation functions, bias settings, and weight-sharing constraints, we demonstrate linear convergence to ground-truth parameters for Gaussian mixtures and sparse coding models.
Introduction
Autoencoders are a staple of unsupervised learning, yet theoretical understanding of their training dynamics has lagged behind supervised counterparts. While they excel at feature learning in practice, proving why gradient descent converges to meaningful solutions is challenging. The primary difficulty stems from the weight-sharing constraint, where the decoder's weights are the transpose of the encoder's. This coupling creates complex feedback loops in the gradient updates. This work addresses these challenges by providing provable guarantees for parameter recovery in three common statistical models: Gaussian mixtures, sparse coding, and non-negative sparse coding.
Methods
The study focuses on a shallow two-layer autoencoder architecture. The encoder is defined as $x = \sigma(W^T y + b)$ and the decoder as $\hat{y} = Wx$, where $\sigma$ represents either ReLU or Hard Thresholding activation functions.
The analytical framework involves two key stages:
- Code Consistency: Proving that if weights $W$ are sufficiently close to the ground truth, the encoder correctly identifies the "support" (non-zero feature indices) of the latent signal.
- Gradient Analysis: Analyzing an approximate gradient of the reconstruction loss. Since the true gradient is non-differentiable at certain points, an approximate version serves as a reliable proxy in expectation.
A significant technical discovery is the role of bias ($b$). For ReLU autoencoders, a fixed bias is insufficient for convergence. Instead, a diminishing bias sequence—starting negative and reducing in magnitude—is required to maintain code consistency and suppress noise during training.
Key Results
The authors prove that the distance between learned weights $W$ and ground truth $A$ decreases at a linear rate until reaching a small neighborhood of the truth. This recovery is guaranteed under specific conditions regarding data incoherence, sparsity, and noise levels.
Experimental validation using synthetic datasets (e.g., Gaussian mixtures with $m=10$ centers in $n=784$ dimensions) confirms these findings. While reconstruction loss may decrease even with random initialization, recovering the exact ground truth $A$ typically requires initialization via PCA or a small perturbation of the truth.
Discussion
While this work provides a rigorous foundation, several open questions remain. The current theory requires a "good" initialization; proving global convergence from random starts is a significant future challenge. Additionally, the analysis is restricted to shallow architectures and asymptotic data limits. Extending these proofs to deep, stacked autoencoders and finite-sample regimes will be essential for a complete theoretical understanding of autoencoder training in real-world scenarios.
Summary updated