Phase Transitions in Rate Distortion Theory and Deep Learning

Philipp Grohs, Andreas Klotz, Felix Voigtländer

TL;DR

This paper introduces the concept of a "compressibility phase transition" in rate distortion theory, showing that for certain signal classes, there's a sharp boundary between signals that can be compressed efficiently and those that cannot, even with optimal coding schemes. This theoretical insight is then applied to deep learning, providing new bounds on the approximation capabilities of neural networks and explaining why certain approximation results are "generically sharp."

What Problem Does This Paper Address?

Rate distortion theory aims to find the best way to compress signals (like images or audio) given a limited number of bits. The core question is: how well can we represent a signal from a given class using a fixed number of bits? This is often characterized by an "optimal compression rate," $s^*$. However, for any given compression method (a "codec"), some signals might be harder to compress than others, even if they belong to the same signal class. This paper tackles the question of how many signals are "hard to compress" and whether this difficulty exhibits a predictable pattern. Specifically, it investigates if there's a sharp transition: signals that are slightly harder to compress than the optimal rate $s^*$ are rare, or if there's a significant portion of signals that are fundamentally difficult to compress, regardless of the coding scheme. This problem is extended to the realm of deep learning, where the goal is to approximate complex functions using neural networks. The paper seeks to understand the fundamental limits of such approximations and why certain theoretical bounds on neural network performance are considered "sharp."

Methods

The paper's core contribution is the introduction and formalization of a "compressibility phase transition." For a given signal class $\mathcal{S}$ and an optimal compression rate $s^*$, they construct a probability measure $\mathbb{P}$ on $\mathcal{S}$. The key finding is that for any coding scheme $\mathcal{C}$, the set of signals that cannot be compressed at a rate $s > s^*$ (meaning they require more bits than theoretically optimal for that rate) is a $\mathbb{P}$-null set. This means that "almost all" signals in $\mathcal{S}$ (with respect to $\mathbb{P}$) can be compressed at rates slightly above $s^*$. Conversely, for rates $s < s^*$, there exist coding schemes that can compress all signals in $\mathcal{S}$ to that rate.

To achieve this, the authors leverage concepts from functional analysis, particularly Besov and Sobolev spaces, which are common models for signal classes. They construct specific probability measures with a "logarithmic growth order" that are critical for these spaces. The paper then uses abstract theorems (Theorem 2.2 and 2.6) to transfer these phase transition properties from abstract sequence spaces to concrete function spaces like Besov and Sobolev spaces.

For the deep learning application, they connect rate distortion theory to neural network approximation. They define a notion of "quantized" neural networks and use their rate distortion results to derive quantitative, non-asymptotic bounds on the probability of successfully approximating a function within a certain accuracy $\varepsilon$ using a neural network with a limited number of weights $W$.

Datasets

Not discussed in the paper. The paper focuses on theoretical signal classes (Besov and Sobolev spaces) rather than specific datasets.

Key Insights and Ideas

  • Compressibility Phase Transition: The most significant insight is the discovery of a sharp "phase transition" in compressibility. For a given signal class and optimal rate $s^*$, there's a clear distinction: signals that are "hard to compress" (require more bits than theoretically optimal for a given rate) are rare according to a specific probability measure. This implies that for most signals, the theoretical limits are achievable.
  • Universality of the Measure: The probability measure $\mathbb{P}$ that defines this phase transition is independent of the specific coding scheme used. This is crucial because it implies a fundamental property of the signal class itself, not just a quirk of a particular compression algorithm.
  • Deep Learning Limits: The paper provides a theoretical framework to understand the fundamental limits of function approximation by neural networks. It shows that for a given accuracy $\varepsilon$ and network size $W$, the probability of success is bounded, and this bound depends on the optimal compression rate $s^*$ of the function class.
  • Generically Sharp Approximation Results: The findings explain why many existing results on the sharpness of neural network approximation rates are indeed "generically sharp." This means that the theoretical bounds are not just worst-case scenarios but are often tight for "almost all" functions in a given class.

Key Results

  • Theorem 1.3 & 4.1 & 4.2: For unit balls in Besov and Sobolev spaces (which are common models for signals), the paper proves the existence of a probability measure $\mathbb{P}$ that exhibits a compressibility phase transition. This means that for any coding scheme, almost all signals in these spaces cannot be compressed at a rate $s > s^*$.
  • Theorem 1.5: Provides quantitative, non-asymptotic bounds on the probability of successfully encoding a random signal $f$ (drawn from $\mathbb{P}$) to within accuracy $\varepsilon$ using $R$ bits. This probability is bounded by $2R^{-c\varepsilon^{-1/s^*}}$.
  • Theorem 1.7: Applies these results to neural networks. It shows that for a function class $\mathcal{S}$ with optimal compression rate $s^*$, the probability of approximating a function $f \in \mathcal{S}$ to within accuracy $\varepsilon$ using a quantized neural network with $W$ weights is bounded by $\min\{1, 2^{C \cdot W \lceil \log_2(1+W) \rceil^2 - c \cdot \varepsilon^{-1/s^*}}\}$. This implies that the network size $W$ must scale roughly as $\varepsilon^{-1/s^*}$ to achieve high probability of success.

Limitations and Future Work

  • Specific Signal Classes: The theoretical results are proven for specific signal classes (Besov and Sobolev spaces). While these are important models, extending the phase transition concept to more general or complex signal classes could be a future direction.
  • "Nice" Signal Classes: The paper focuses on "nice" signal classes that embed compactly into $L^2(\Omega)$. The behavior for signal classes that do not satisfy these conditions is not addressed.
  • Case $s = s^*$: The theorems often leave open the behavior exactly at the optimal compression rate $s^*$. The paper notes that in this case, the behavior depends on the specific choices of the signal class and the measure.
  • Practical Implications: While the paper provides theoretical bounds for neural network approximation, translating these bounds into practical algorithmic improvements or architectural designs is a significant future challenge. The paper suggests that the sharpness of the bounds implies that "learning algorithms are fundamentally limited in their ability to exploit the structure of the data."

Summary updated

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\}$.
BibTeX
@article{grohs2023phase,
  author = {Philipp Grohs and Andreas Klotz and Felix Voigtländer},
  title = {{Phase Transitions in Rate Distortion Theory and Deep Learning}},
  journal = {Found. Comput. Math.},
  year = {2023},
  doi = {10.1007/s10208-021-09546-4},
}
Figure