Technical Summary: Stable Source Coding

Problem Statement

This paper investigates the fundamental limits of lossless source coding under an explicit stability constraint. While classical information theory (Shannon's framework) allows for arbitrary encoders, modern machine learning-based compressors often exhibit "algorithmic stability," where small perturbations in the input lead to small changes in the output. The authors argue that this stability property conflicts with classical coding techniques like random binning, which map nearby source sequences to completely unrelated codewords.

The core problem is defined as follows: Given an i.i.d. source $X^n$ with distribution $P_X$, an encoder $f_n: \mathcal{X}^n \to \{0,1\}^{nR}$ is $(D_n, D'_n)$-stable if for any two source sequences $x^n, \tilde{x}^n$:
$$d_I(x^n, \tilde{x}^n) \le D_n \implies d_H(f_n(x^n), f_n(\tilde{x}^n)) \le D'_n$$
where $d_I$ is a source distance metric (Hamming distance in the binary case) and $d_H$ is the Hamming distance on the binary codewords. The goal is to characterize the minimum achievable compression rate $R$ as a function of the stability parameters $\{(D_n, D'_n)\}_{n \ge 1}$, subject to the requirement that the decoding error probability vanishes as $n \to \infty$.

Methodology

The authors derive converse bounds (necessary conditions) on the achievable rate by reducing the stability-constrained coding problem to a graph homomorphism problem. The methodology proceeds through the following steps:

1. Restriction to Type Classes: Using the method of types, the analysis is restricted to a specific type class $T(\pi_n)$ (sequences with empirical distribution $\pi_n$) that contains almost all the probability mass of the source. Within this class, the encoder must be injective on a large subset of sequences to ensure lossless decoding.
2. Graph Construction:
   • Source Graph ($G_n$): Vertices represent sequences in the type class. An edge exists between two vertices if their Hamming distance is $\le D_n$. This graph is a union of generalized Johnson graphs.
   • Codeword Graph ($H_n$): Vertices represent binary strings of length $nR$. An edge exists if their Hamming distance is $\le D'_n$. This is the $D'_n$-th power of the Hamming graph.
3. Homomorphism Constraint: The stability condition implies that the encoder induces an injective graph homomorphism from a large induced subgraph of $G_n$ to $H_n$.
4. Combinatorial Bounds: The existence of such a homomorphism necessitates that the structural properties of the source graph cannot exceed those of the codeword graph. Specifically, the authors utilize:
   • Maximum Degree ($\Delta$): The maximum degree of the source subgraph must be less than or equal to that of the codeword graph.
   • Maximum Clique Size ($\omega$): The maximum clique size of the source subgraph must be less than or equal to that of the codeword graph.
5. Asymptotic Analysis: The authors compute the asymptotic growth rates of these graph parameters (degrees and clique sizes) for both linear regimes ($D_n, D'_n = \Theta(n)$) and sublinear regimes ($D_n, D'_n = o(n)$) to derive explicit inequalities involving the rate $R$.

Key Contributions and Results

1. Graph-Theoretic Reduction

The primary contribution is the formulation of stable source coding as a graph homomorphism problem. This approach translates the stability constraint into combinatorial limits on graph invariants (degree and clique size), allowing for the derivation of information-theoretic converse bounds.

2. Converse Bounds in the Linear Regime

For the case where $D_n = n d_1$ and $D'_n = n d_2$, the paper establishes two necessary conditions for a rate $R$ to be achievable:

• Degree Bound (Theorem 1):
  $$F(d_1, p) \le G(d_2, R)$$
  Where $F$ and $G$ are functions derived from binary entropy terms involving the source probability $p$ and the normalized distances. This bound arises from comparing the maximum degrees of the source and codeword graphs.

• Clique Size Bound (Theorem 2):
  $$h_2(d_1/2) \le \Psi(d_2, R)$$
  Where $\Psi$ is a function related to the volume of Hamming balls. This bound is derived using the Ahlswede-Khachatrian theorem on the maximum size of $t$-intersecting families (cliques in the source graph) and Kleitman's theorem for the codeword graph. The authors show that for certain parameters, this bound simplifies to a constraint independent of the source distribution $p$.

3. Converse Bounds in the Sublinear Regime

For $D_n = o(n)$ and $D'_n = o(n)$, the authors derive a specific inequality (Proposition 1) relating the parameters. A significant corollary is that if $D_n$ and $D'_n$ are fixed constants ($D, D'$), then $D \le D'$ must hold, regardless of the compression rate $R$. This implies that if the encoder must preserve the exact distance between inputs (i.e., $D=D'$), the output length cannot be compressed below the input length in a way that violates this distance preservation, even if $R > 1$ (expansion).

Significance and Claims

The paper claims to bridge a gap between classical information theory and the behavior of modern learned compressors (e.g., ANN-based). While Shannon's achievability results assume arbitrary, potentially discontinuous encoders, the authors demonstrate that imposing a stability constraint (continuity-like behavior) fundamentally alters the achievable rate-distortion trade-off.

• Theoretical Insight: The work provides the first information-theoretic limits for lossless coding under explicit stability constraints, showing that stability imposes a "cost" on the compression rate.
• Connection to Learning: The results offer a theoretical explanation for why neural network-based compressors might underperform on tasks requiring discontinuous partitions; the stability inherent in gradient-based training prevents the encoder from utilizing the highly discontinuous mappings required for optimal compression in the classical sense.
• Methodological Novelty: By reducing the coding problem to graph homomorphisms and leveraging deep results from extremal combinatorics (Ahlswede-Khachatrian, Kleitman), the paper establishes a new framework for analyzing stability-constrained coding.

The authors remain modest regarding future directions, suggesting that further bounds could be derived using independence numbers and the no-homomorphism lemma, but do not propose specific new applications or experimental validations within this work.