# Phase Transitions in Rate Distortion Theory and Deep Learning

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Aug 2020.

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

- [Deep Ridgelet Transform and Unified Universality Theorem for Deep and Shallow Joint-Group-Equivariant Machines](https://mlsanity.com/paper/2405.13682/) (2024)
- [Sen2Pro: A Probabilistic Perspective to Sentence Embedding from Pre-trained Language Model](https://mlsanity.com/paper/2306.02247/) (2023)
- [Universal Consistency of Wide and Deep ReLU Neural Networks and Minimax Optimal Convergence Rates for Kolmogorov-Donoho Optimal Function Classes](https://mlsanity.com/paper/2401.04286/) (2024)
- [Tighter Learning Guarantees on Digital Computers via Concentration of Measure on Finite Spaces](https://mlsanity.com/paper/2402.05576/) (2024)
- [The Information-Theoretic Benefit of Shared Representations under Orthogonality Constraints](https://mlsanity.com/paper/2606.16028/) (2026)

## Abstract (arXiv)

Rate distortion theory is concerned with optimally encoding a given signal class S using a budget of R bits, as R→∞. We say that S can be compressed at rate s if we can achieve an error of O(R-s) for encoding S; the supremal compression rate is denoted s^ast(S). Given a fixed coding scheme, there usually are elements of S that are compressed at a higher rate than s^ast(S) by the given coding scheme; we study the size of this set of signals. We show that for certain "nice" signal classes S, a phase transition occurs: We construct a probability measure mathbbP on S such that for every coding scheme C and any s >s^ast(S), the set of signals encoded with error O(R-s) by C forms a mathbbP-null-set. In particular our results apply to balls in Besov and Sobolev spaces that embed compactly into L2(Omega) for a bounded Lipschitz domain Omega. As an application, we show that several existing sharpness results concerning function approximation using deep neural networks are generically sharp. We also provide quantitative and non-asymptotic bounds on the probability that a random f∈S can be encoded to within accuracy varepsilon using R bits. This result is applied to the problem of approximately representing f∈S to within accuracy varepsilon by a (quantized) neural network that is constrained to have at most W nonzero weights and is generated by an arbitrary "learning" procedure. We show that for any s >s^ast(S) there are constants c,C such that, no matter how we choose the "learning" procedure, the probability of success is bounded from above by minbig1,2^C· Wlceillog2(1+W)rceil2 -c·varepsilon-1/sbig.