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 signals from a given signal class S using a budget of R bits, as R ->infinity. We say that S can be compressed at rate s if we can achieve an error of at most O(R-s) for encoding the given signal class; the supremal compression rate is denoted by s* (S). Given a fixed coding scheme, there usually are some elements of S that are compressed at a higher rate than s * (S) by the given coding scheme; in this paper, we study the size of this set of signals. We showthat for certain "nice" signal classes S, a phase transition occurs: We construct a probability measure P on S such that for every coding scheme C and any s > s * (S), the set of signals encoded with error O(R-s) by C forms a P-null-set. In particular, our results apply to all unit balls in Besov and Sobolev spaces that embed compactly into L-2(Omega) for a bounded Lipschitz domain O. As an application, we show that several existing sharpness results concerning function approximation using deep neural networks are in fact generically sharp. In addition, we provide quantitative and non-asymptotic bounds on the probability that a random f is an element of S can be encoded to within accuracy e using R bits. This result is subsequently applied to the problem of approximately representing f is an element of S to within accuracy e by a (quantized) neural network with at most W nonzeroweights. We showthat for any s > s * (S) there are constants c, C such that, no matter what kind of "learning" procedure is used to produce such a network, the probability of success is bounded from above by min {1, 2(C .W) inverted left perpendicularlog(2)(1+W)inverted right perpendicular2-c.epsilon(-1/s)}.
- 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://ucrisportal.univie.ac.at/en/publications/5d9924fe-c0c2-4adf-9680-41b0aaccd129