Research map / Architectures and efficiency / RNNs and normalization
Compression of Structured Data with Autoencoders: Provable Benefit of Nonlinearities and Depth
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows gradient descent on a two-layer sign-activation autoencoder ignores sparsity of Gaussian-masked data, and that adding a learned nonlinear output function and a multi-layer AMP-inspired decoder provably beats the Gaussian compression loss.
Problem
Whether shallow autoencoders trained by gradient descent capture the sparse structure of data in 1-bit compression, and how decoder nonlinearity and depth affect performance.
Approach
Analyzes a two-layer sign-activation autoencoder by treating the Bernoulli mask as concentrating to its mean, showing GD trajectory matches Gaussian data; then adds a component-wise nonlinear decoder function (provably better MSE) and a multi-layer residual decoder derived from RI-GAMP iterates.
Key results
- Gradient descent on a two-layer sign autoencoder with sparse Gaussian data converges to the Gaussian MSE 1 - 2r/pi, ignoring sparsity.
- Adding a learned nonlinear output function f gives MSE strictly below the Gaussian loss for any sparsity p in (0,1).
- A three-layer residual decoder approaches the Bayes-optimal MSE for sparse Gaussian data (p=0.3, d=500).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train a two-layer autoencoder with a linear decoder on sparse Gaussian data | Two-layer autoencoder · Sparse Gaussian compression | MSE | No clear effect |
| Add an output nonlinearity to the linear decoder | Shallow autoencoder on sparse Gaussian data · Sparse Gaussian compression | MSE | Helped |
| Use a three-layer RI-GAMP-inspired decoder instead of a shallow decoder | Autoencoder with fixed rotationally invariant encoder · Sparse Gaussian compression, p=0.3, d=500 | MSE | Helped |
| Use a deep fully-connected decoder in place of the RI-GAMP-inspired decoder (ablation) | Sparse Gaussian autoencoder · Sparse Gaussian compression | MSE | No clear effect |
| Use a Haar rotation rather than an identity decoder | Linear-decoder autoencoder on sparse Rademacher data · Sparse Rademacher compression, p > 2/\pi | MSE: 1-2r/\pi -> 1-r\cdot p | Hurt |
| Use an identity decoder rather than a Haar rotation | Linear-decoder autoencoder on sparse Rademacher data · Sparse Rademacher compression, p < 2/\pi | MSE: 1-r\cdot p -> 1-2r/\pi | Hurt |
| Add an output nonlinearity to the linear decoder | Autoencoder on whitened, masked CIFAR-10 dog images · CIFAR-10 dog images, masked p=0.4 | MSE | Helped |
| Train the linear-decoder autoencoder on whitened, masked CIFAR-10 dog images | Two-layer autoencoder with linear decoder · CIFAR-10 dog images, masked p=0.7 | MSE | No clear effect |
Surprising findings
- Standard two-layer sign autoencoder trained with GD cannot exploit data sparsity at all, matching Gaussian performance exactly.
- Deeper fully-connected decoders do not improve over the shallow nonlinear decoder due to training difficulties.
Limitations
- Theory covers i.i.d. components and a Haar/bi-rotationally invariant encoder; general data results are conjectured from numerics.
- Escape time from the plateau in staircase dynamics is not characterized theoretically.
Experimental setup
Datasets: CIFAR-10 MNIST
Benchmarks: CIFAR-10 MNIST
Metrics: mean squared error
Baselines: Gaussian-data compression (R_Gauss) linear decoder autoencoder Bayes-optimal MSE
Builds on: RI-GAMP 1-bit compressed sensing approximate message passing
Closest papers by meaning
- Sparse Autoencoders, Again? (ICML 2025 · similarity 0.87)
- Compute Optimal Inference and Provable Amortisation Gap in Sparse Autoencoders (ICML 2025 · similarity 0.87)
- Scaling and evaluating sparse autoencoders (ICLR 2025 · similarity 0.86)
- Auto-Compressing Networks (NeurIPS 2025 · similarity 0.86)
- Unified Scaling Laws for Compressed Representations (NeurIPS 2025 · similarity 0.86)
- Be a Goldfish: Forgetting Bad Conditioning in Sparse Linear Regression via Variational Autoencoders (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.