# Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 48 references that are in the map.
- First posted on arXiv 7 Feb 2024.

## Builds on (most cited first, 28 of 28)

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Neural Discrete Representation Learning](https://mlsanity.com/paper/1711.00937/) (2017)
- [End-to-end Optimized Image Compression](https://mlsanity.com/paper/1611.01704/) (2016)
- [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)
- [Soft-to-Hard Vector Quantization for End-to-End Learning Compressible Representations](https://mlsanity.com/paper/1704.00648/) (2017)
- [SGD learning on neural networks: leap complexity and saddle-to-saddle dynamics](https://mlsanity.com/paper/2302.11055/) (2023)
- [The merged-staircase property: a necessary and nearly sufficient condition for SGD learning of sparse functions on two-layer neural networks](https://mlsanity.com/paper/2202.08658/) (2022)
- [Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks](https://mlsanity.com/paper/1904.13262/) (2019)
- [Saddle-to-Saddle Dynamics in Deep Linear Networks: Small Initialization Training, Symmetry, and Sparsity](https://mlsanity.com/paper/2106.15933/) (2021)
- [The staircase property: How hierarchical structure can guide deep learning](https://mlsanity.com/paper/2108.10573/) (2021)
- [Learning time-scales in two-layers neural networks](https://mlsanity.com/paper/2303.00055/) (2023)
- [Saddle-to-Saddle Dynamics in Diagonal Linear Networks](https://mlsanity.com/paper/2304.00488/) (2023)
- [Transformers learn through gradual rank increase](https://mlsanity.com/paper/2306.07042/) (2023)
- [A unifying tutorial on Approximate Message Passing](https://mlsanity.com/paper/2105.02180/) (2021)
- [Loss Landscapes of Regularized Linear Autoencoders](https://mlsanity.com/paper/1901.08168/) (2019)
- [On the Stepwise Nature of Self-Supervised Learning](https://mlsanity.com/paper/2303.15438/) (2023)
- [Incremental Learning in Diagonal Linear Networks](https://mlsanity.com/paper/2208.14673/) (2022)
- [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)
- [Approximate Message Passing with Spectral Initialization for Generalized Linear Models](https://mlsanity.com/paper/2010.03460/) (2020)
- [High-dimensional Asymptotics of Denoising Autoencoders](https://mlsanity.com/paper/2305.11041/) (2023)
- [Estimation in Rotationally Invariant Generalized Linear Models via Approximate Message Passing](https://mlsanity.com/paper/2112.04330/) (2021)
- [Analysis of feature learning in weight-tied autoencoders via the mean field lens](https://mlsanity.com/paper/2102.08373/) (2021)
- [A General Derivative Identity for the Conditional Mean Estimator in Gaussian Noise and Some Applications](https://mlsanity.com/paper/2104.01883/) (2021)
- [Implicit Regularization in Deep Tensor Factorization](https://mlsanity.com/paper/2105.01346/) (2021)
- [Fundamental Limits of Two-layer Autoencoders, and Achieving Them with Gradient Methods](https://mlsanity.com/paper/2212.13468/) (2022)
- [Learning from higher-order statistics, efficiently: hypothesis tests, random features, and neural networks](https://mlsanity.com/paper/2312.14922/) (2023)

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

- [On the Feature Learning in Diffusion Models](https://mlsanity.com/paper/2412.01021/) (2024)
- [A theory of learning data statistics in diffusion models, from easy to hard](https://mlsanity.com/paper/2603.12901/) (2026)
- [Distributional simplicity bias and effective convexity in Energy Based Models](https://mlsanity.com/paper/2605.07844/) (2026)
- [A Fourier perspective on the learning dynamics of neural networks: from sample complexities to mechanistic insights](https://mlsanity.com/paper/2605.16913/) (2026)
- [Beyond Linear and Overcomplete Regimes: A Mean-Field Analysis of Bottleneck Autoencoders](https://mlsanity.com/paper/2606.07120/) (2026)

## Abstract (arXiv)

Autoencoders are a prominent model in many empirical branches of machine learning and lossy data compression. However, basic theoretical questions remain unanswered even in a shallow two-layer setting. In particular, to what degree does a shallow autoencoder capture the structure of the underlying data distribution? For the prototypical case of the 1-bit compression of sparse Gaussian data, we prove that gradient descent converges to a solution that completely disregards the sparse structure of the input. Namely, the performance of the algorithm is the same as if it was compressing a Gaussian source - with no sparsity. For general data distributions, we give evidence of a phase transition phenomenon in the shape of the gradient descent minimizer, as a function of the data sparsity: below the critical sparsity level, the minimizer is a rotation taken uniformly at random (just like in the compression of non-sparse data); above the critical sparsity, the minimizer is the identity (up to a permutation). Finally, by exploiting a connection with approximate message passing algorithms, we show how to improve upon Gaussian performance for the compression of sparse data: adding a denoising function to a shallow architecture already reduces the loss provably, and a suitable multi-layer decoder leads to a further improvement. We validate our findings on image datasets, such as CIFAR-10 and MNIST.