# Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methods

arXiv: https://arxiv.org/abs/2212.13468 · HTML: https://mlsanity.com/paper/2212.13468/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 76 references that are in the map.
- First posted on arXiv 27 Dec 2022.

## Builds on (most cited first, 30 of 36)

- [Neural Tangent Kernel: Convergence and Generalization in Neural Networks](https://mlsanity.com/paper/1806.07572/) (2018)
- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [End-to-end Optimized Image Compression](https://mlsanity.com/paper/1611.01704/) (2016)
- [On Lazy Training in Differentiable Programming](https://mlsanity.com/paper/1812.07956/) (2018)
- [Learned Image Compression with Discretized Gaussian Mixture Likelihoods and Attention Modules](https://mlsanity.com/paper/2001.01568/) (2020)
- [Surprises in High-Dimensional Ridgeless Least Squares Interpolation](https://mlsanity.com/paper/1903.08560/) (2019)
- [Lossy Image Compression with Compressive Autoencoders](https://mlsanity.com/paper/1703.00395/) (2017)
- [Understanding Straight-Through Estimator in Training Activation Quantized Neural Nets](https://mlsanity.com/paper/1903.05662/) (2019)
- [Coordinate Descent Algorithms](https://mlsanity.com/paper/1502.04759/) (2015)
- [Expectation Propagation for approximate Bayesian inference](https://mlsanity.com/paper/1301.2294/) (2013)
- [Lossy Image Compression with Conditional Diffusion Models](https://mlsanity.com/paper/2209.06950/) (2022)
- [Soft-to-Hard Vector Quantization for End-to-End Learning Compressible Representations](https://mlsanity.com/paper/1704.00648/) (2017)
- [Nonlinear Transform Coding](https://mlsanity.com/paper/2007.03034/) (2020)
- [Recent Advances in Autoencoder-Based Representation Learning](https://mlsanity.com/paper/1812.05069/) (2018)
- [Learning curves of generic features maps for realistic datasets with a teacher-student model](https://mlsanity.com/paper/2102.08127/) (2021)
- [Phase Retrieval via Wirtinger Flow: Theory and Algorithms](https://mlsanity.com/paper/1407.1065/) (2014)
- [Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks](https://mlsanity.com/paper/1904.13262/) (2019)
- [Generalized Denoising Auto-Encoders as Generative Models](https://mlsanity.com/paper/1305.6663/) (2013)
- [The Gaussian equivalence of generative models for learning with shallow neural networks](https://mlsanity.com/paper/2006.14709/) (2020)
- [Lossy Compression with Gaussian Diffusion](https://mlsanity.com/paper/2206.08889/) (2022)
- [The Landscape of Empirical Risk for Non-convex Losses](https://mlsanity.com/paper/1607.06534/) (2016)
- [An Introduction to Neural Data Compression](https://mlsanity.com/paper/2202.06533/) (2022)
- [Universality of empirical risk minimization](https://mlsanity.com/paper/2202.08832/) (2022)
- [Loss Landscapes of Regularized Linear Autoencoders](https://mlsanity.com/paper/1901.08168/) (2019)
- [Overparameterized Neural Networks Implement Associative Memory](https://mlsanity.com/paper/1909.12362/) (2019)
- [The dynamics of representation learning in shallow, non-linear autoencoders](https://mlsanity.com/paper/2201.02115/) (2022)
- [Regularized linear autoencoders recover the principal components, eventually](https://mlsanity.com/paper/2007.06731/) (2020)
- [Analysis of feature learning in weight-tied autoencoders via the mean field lens](https://mlsanity.com/paper/2102.08373/) (2021)
- [Towards Empirical Sandwich Bounds on the Rate-Distortion Function](https://mlsanity.com/paper/2111.12166/) (2021)
- [Inference in Deep Networks in High Dimensions](https://mlsanity.com/paper/1706.06549/) (2017)

## Built on by (most cited first, 3 of 3)

- [High-dimensional Asymptotics of Denoising Autoencoders](https://mlsanity.com/paper/2305.11041/) (2023)
- [Approaching Rate-Distortion Limits in Neural Compression with Lattice Transform Coding](https://mlsanity.com/paper/2403.07320/) (2024)
- [Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth](https://mlsanity.com/paper/2402.05013/) (2024)

## Abstract (arXiv)

Autoencoders are a popular model in many branches of machine learning and lossy data compression. However, their fundamental limits, the performance of gradient methods and the features learnt during optimization remain poorly understood, even in the two-layer setting. In fact, earlier work has considered either linear autoencoders or specific training regimes (leading to vanishing or diverging compression rates). Our paper addresses this gap by focusing on non-linear two-layer autoencoders trained in the challenging proportional regime in which the input dimension scales linearly with the size of the representation. Our results characterize the minimizers of the population risk, and show that such minimizers are achieved by gradient methods; their structure is also unveiled, thus leading to a concise description of the features obtained via training. For the special case of a sign activation function, our analysis establishes the fundamental limits for the lossy compression of Gaussian sources via (shallow) autoencoders. Finally, while the results are proved for Gaussian data, numerical simulations on standard datasets display the universality of the theoretical predictions.