Phase Transitions in Rate Distortion Theory and Deep Learning
- Author(s)
- Philipp Grohs, Andreas Klotz, Felix Voigtlaender
- Abstract
Rate distortion theory is concerned with optimally encoding a given signal class $\mathcal{S}$ using a budget of $R$ bits, as $R\to\infty$. We say that $\mathcal{S}$ can be compressed at rate $s$ if we can achieve an error of $\mathcal{O}(R^{-s})$ for encoding $\mathcal{S}$; the supremal compression rate is denoted $s^\ast(\mathcal{S})$. Given a fixed coding scheme, there usually are elements of $\mathcal{S}$ that are compressed at a higher rate than $s^\ast(\mathcal{S})$ by the given coding scheme; we study the size of this set of signals. We show that for certain "nice" signal classes $\mathcal{S}$, a phase transition occurs: We construct a probability measure $\mathbb{P}$ on $\mathcal{S}$ such that for every coding scheme $\mathcal{C}$ and any $s >s^\ast(\mathcal{S})$, the set of signals encoded with error $\mathcal{O}(R^{-s})$ by $\mathcal{C}$ forms a $\mathbb{P}$-null-set. In particular our results apply to balls in Besov and Sobolev spaces that embed compactly into $L^2(\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\in\mathcal{S}$ can be encoded to within accuracy $\varepsilon$ using $R$ bits. This result is applied to the problem of approximately representing $f\in\mathcal{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(\mathcal{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 $\min\big\{1,2^{C\cdot W\lceil\log_2(1+W)\rceil^2 -c\cdot\varepsilon^{-1/s}}\big\}$.
- Organisation(s)
- Department of Mathematics, Research Network Data Science
- External organisation(s)
- Technische Universität München
- Journal
- Foundations of Computational Mathematics
- Volume
- 23
- Pages
- 329-392
- No. of pages
- 64
- ISSN
- 1615-3375
- DOI
- https://doi.org/10.1007/s10208-021-09546-4
- Publication date
- 08-2020
- Peer reviewed
- Yes
- Austrian Fields of Science 2012
- 101032 Functional analysis
- Keywords
- ASJC Scopus subject areas
- Computational Mathematics, Analysis, Applied Mathematics, Computational Theory and Mathematics
- Portal url
- https://ucris.univie.ac.at/portal/en/publications/phase-transitions-in-rate-distortion-theory-and-deep-learning(5d9924fe-c0c2-4adf-9680-41b0aaccd129).html