Phase Transitions in Rate Distortion Theory and Deep Learning

DOI10.1007/S10208-021-09546-4MaRDI QIDQ6346400arXivFDO

Authors Philipp Grohs, Andreas Klotz, Felix Voigtlaender

Publication date 3 August 2020

Published in arXiv

Full work available at URL https://doi.org/10.1007/S10208-021-09546-4

Mathematics Subject Classification ID

Set functions and measures and integrals in infinite-dimensional spaces (Wiener measure, Gaussian measure, etc.) (28C20) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46) Artificial neural networks and deep learning (68T07) Rate-distortion theory in information and communication theory (94A34)

arXiv classification

cs.LGmath.FA

Abstract: Rate distortion theory is concerned with optimally encoding a given signal class $mathcalS$ using a budget of $R$ bits, as $Roinfty$. We say that $mathcalS$ can be compressed at rate $s$ if we can achieve an error of $mathcalO(R^{-s})$ for encoding $mathcalS$; the supremal compression rate is denoted $s^{a}st(mathcalS)$. Given a fixed coding scheme, there usually are elements of $mathcalS$ that are compressed at a higher rate than $s^{a}st(mathcalS)$ by the given coding scheme; we study the size of this set of signals. We show that for certain "nice" signal classes $mathcalS$, a phase transition occurs: We construct a probability measure $mathbbP$ on $mathcalS$ such that for every coding scheme $mathcalC$ and any $s>s^{a}st(mathcalS)$, the set of signals encoded with error $mathcalO(R^{-s})$ by $mathcalC$ forms a $mathbbP$-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 $finmathcalS$ can be encoded to within accuracy $varepsilon$ using $R$ bits. This result is applied to the problem of approximately representing $finmathcalS$ 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^{a}st(mathcalS)$ there are constants $c,C$ such that, no matter how we choose the "learning" procedure, the probability of success is bounded from above by $$.

This page was built for publication: Phase Transitions in Rate Distortion Theory and Deep Learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6346400)