Discrete Lossy Gray-Wyner Revisited: Second-Order Asymptotics, Large and Moderate Deviations

Lin Zhou, Vincent Y. F. Tan, Mehul MotaniIEEE Trans. Information Theory 2017 · OpenReview

TL;DR

This paper provides a comprehensive analysis of the discrete lossy Gray-Wyner source coding problem, deriving precise characterizations for its second-order coding rate region, error exponent, and moderate deviations constant. These results offer a deeper understanding of the performance limits for this complex multi-terminal source coding scenario, particularly in finite blocklength regimes.

What Problem Does This Paper Address?

The Gray-Wyner problem is a fundamental model in information theory that deals with encoding a pair of correlated sources (X, Y) for multiple decoders, where each decoder aims to reconstruct one of the sources with a certain fidelity. While the first-order asymptotic performance (i.e., the optimal rate region) was characterized decades ago, understanding the finer details of performance, such as how quickly the system approaches its ideal rate (second-order asymptotics), the probability of error (error exponent), and deviations from typical behavior (moderate deviations), has remained a significant challenge. This paper revisits this problem to provide these crucial second-order characterizations, which are essential for designing practical and efficient compression systems, especially when dealing with finite resources or strict performance requirements.

Methods

The authors employ a combination of advanced information-theoretic tools:

  • Second-Order Asymptotics: They extend techniques from prior work on similar problems, particularly leveraging a generalized "conditional distortion-tilted information density." The achievability proofs rely on novel "type covering lemmas" and demonstrate the uniform continuity of the conditional rate-distortion function. The converse proofs utilize perturbation arguments and strong converses.
  • Error Exponent: The achievability uses the same generalized type covering lemma, while the converse relies on strong converses and change-of-measure techniques.
  • Moderate Deviations: This analysis applies the moderate deviations theorem to probabilities defined using information spectrum quantities.

A key methodological contribution is a unified approach for all three asymptotic regimes, hinged on a single generalized type covering lemma.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of a source coding model rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Unified Framework: The paper demonstrates that a single generalized type covering lemma can be instrumental in deriving results for second-order asymptotics, error exponents, and moderate deviations, highlighting a powerful unifying principle in information theory.
  • Tilted Information Density: The introduction and careful analysis of a "tilted information density" (specifically, a generalized version for the lossy Gray-Wyner problem) proves crucial for characterizing the performance limits.
  • Importance of Uniform Continuity: Establishing the uniform continuity of the conditional rate-distortion function with respect to both the source distribution and distortion level is identified as a critical step for the achievability proofs.
  • Pangloss Plane Analysis: The paper simplifies calculations for specific rate triplets on the "Pangloss plane," a concept related to cooperative decoding in the Gray-Wyner problem.
  • Relaxed Moderate Deviations Condition: For moderate deviations, the authors remove a previously required condition on the rate of convergence, making the results more broadly applicable.

Key Results

The paper provides precise characterizations for:

  • Second-Order Coding Region: A detailed formula for the optimal second-order coding region is derived, expressed in terms of a "rate-dispersion function" (variance of the tilted information density).
  • Error Exponent: An expression for the optimal error exponent is established, which quantifies the rate at which the probability of error decreases with blocklength.
  • Moderate Deviations Constant: The paper derives the moderate deviations constant, which governs the speed of convergence of the excess-distortion probability to zero, also shown to depend on the rate-dispersion function.

The results are presented as theorems and lemmas, providing rigorous mathematical bounds and characterizations. An example for a doubly symmetric binary source is computed to illustrate the findings.

Limitations and Future Work

  • Mild Conditions: The results are derived under "mild conditions on the source," implying that further research might be needed for more general source distributions.
  • Correlated Gaussian Sources: The authors explicitly state their future aim to solve the second-order asymptotics for correlated Gaussian sources with a quadratic distortion measure.
  • Exact Asymptotics: Extending the analysis to derive "exact asymptotics" for the problem is also mentioned as a future research direction.
  • Discrete vs. Continuous: The current work focuses on discrete sources. Extending these results to continuous sources would be a natural next step.

Summary updated

Abstract

In this paper, we revisit the discrete lossy Gray-Wyner problem. In particular, we derive its optimal second-order coding rate region, its error exponent (reliability function), and its moderate deviations constant under mild conditions on the source. To obtain the second-order asymptotics, we extend some ideas from Watanabe's work. In particular, we leverage the properties of an appropriate generalization of the conditional distortion-tilted information density, which was first introduced by Kostina and Verdú. The converse part uses a perturbation argument by Gu and Effros in their strong converse proof of the discrete Gray-Wyner problem. The achievability part uses two novel elements: 1) a generalization of various type covering lemmas and 2) the uniform continuity of the conditional rate-distortion function in both the source (joint) distribution and the distortion level. To obtain the error exponent, for the achievability part, we use the same generalized type covering lemma, and for the converse, we use the strong converse together with a change-of-measure technique. Finally, to obtain the moderate deviations constant, we apply the moderate deviations theorem to probabilities defined in terms of information spectrum quantities.
BibTeX
@article{zhou2017discrete,
  author = {Lin Zhou and Vincent Y. F. Tan and Mehul Motani},
  title = {{Discrete Lossy Gray-Wyner Revisited: Second-Order Asymptotics, Large and Moderate Deviations}},
  journal = {IEEE Trans. Information Theory},
  year = {2017},
  url = {https://openreview.net/forum?id=pa59Sr_ZOvp},
}
Figure