Abstract
Universal source coding at short blocklengths is considered for an exponential family of distributions. The Type Size code has previously been shown to be optimal up to the third-order rate for universal compression of all memoryless sources over finite alphabets. The Type Size code assigns sequences ordered based on their type class sizes to binary strings ordered lexicographically. To generalize this type class approach for parametric sources, a natural scheme is to define two sequences to be in the same type class if and only if they are equiprobable under any model in the parametric class. This natural approach, however, is shown to be suboptimal. A variation of the Type Size code is introduced, where type classes are defined based on neighborhoods of minimal sufficient statistics. Asymptotics of the overflow rate of this variation are derived and a converse result establishes its optimality up to the third-order term. These results are derived for parametric families of $i.i.d.$ sources as well as Markov sources.
Introduction
In classical information theory, compression efficiency is typically analyzed in the asymptotic limit where the data length $n$ approaches infinity. However, modern delay-sensitive applications—such as IoT sensor networks and real-time web updates—require efficient compression for short data packets. In these "short blocklength" regimes, standard asymptotic formulas often fail to capture the nuances of performance.
The challenge is compounded when the source statistics are unknown, a scenario known as universal source coding. For finite alphabets, the Type Size (TS) code is optimal; it works by sorting sequences based on the size of their "type class" (the set of sequences sharing the same symbol frequencies). Extending this to parametric sources, such as those found in physics or finance, is non-trivial. This paper identifies the "fine asymptotics"—the precise mathematical cost of universality—and introduces a robust coding scheme for these complex sources.
Methodology: The Quantized Type Size Code
The authors focus on exponential families of distributions. Their primary innovation is the Quantized Type Size code, which addresses the suboptimality of traditional "point type" approaches.
Minimal Sufficient Statistics and Quantization
Instead of grouping sequences that have exactly the same statistics, the authors partition the space of minimal sufficient statistics into $d$-dimensional cuboids (grids). Minimal sufficient statistics are the condensed data points that contain all necessary information about the underlying model parameters.
As illustrated in the figure, two sequences are considered to be in the same "quantized type class" if their statistics fall into the same cuboid $G(\tau_c(x^n))$. The code then assigns shorter binary strings to sequences belonging to smaller type classes. This quantization "smooths" the statistical space, ensuring that compression performance depends on the stable parameter dimension $d$ rather than the more volatile lattice dimension $d'$, which can change drastically with minor parameter shifts.
Mathematical Framework
The authors utilize advanced tools such as the Berry-Esseen theorem for normal approximations and Laplace’s method for integral approximations on manifolds. These methods allow them to prove performance limits for both independent and identically distributed (i.i.d.) sources and Markov (memory-based) sources.
Key Results and Insights
The research derives a precise formula for the minimum number of bits required to compress a sequence of length $n$ with an error probability $\epsilon$:
$$R(n, \epsilon) \approx nH + \sigma \sqrt{n} Q^{-1}(\epsilon) + \left( \frac{d}{2} - 1 \right) \log n + O(1)$$
- $nH$: The first-order term, representing source entropy.
- $\sigma \sqrt{n} Q^{-1}(\epsilon)$: The second-order term (varentropy), representing fluctuations at finite lengths.
- $(\frac{d}{2} - 1) \log n$: The third-order term, which represents the specific "penalty" for the source being unknown.
The authors prove that their quantized TS code achieves this rate and that no other code can outperform it in the third-order term. A major insight is that approximate indistinguishability is superior to exact matching: by grouping sequences that are nearly indistinguishable, the code becomes more robust and efficient.
Conclusion
This work establishes that the overhead of universal compression is fundamentally determined by the model's parameter dimension $d$. While the mathematical limits are now clear, practical implementation remains an area for future study. Specifically, the algorithmic complexity of grid-based sorting and the extension of these "fine asymptotics" to lossy compression (like JPEG or MP3) are promising directions for subsequent research.
Summary updated