Strong Converses are Just Edge Removal Properties

Oliver Kosut, Jörg Kliewer

TL;DR

This paper establishes a deep connection between "edge removal properties" (how network capacity changes when an edge is removed) and "strong converses" (how error probability behaves at rates above capacity) in network information theory. The authors show that for many network types, these two concepts are surprisingly equivalent, providing a powerful new lens for understanding network capacity and error behavior.

What Problem Does This Paper Address?

Network information theory deals with how information can be reliably transmitted through complex networks. Two key concepts are:

  1. Edge Removal Properties: How does the capacity of a network change if we remove or reduce the capacity of a single edge? Intuitively, removing a small capacity edge shouldn't drastically alter the overall network capacity. Understanding this helps characterize network robustness and design.
  2. Strong Converses: These theorems state that if you try to transmit information at a rate above the network's capacity, the probability of error will eventually go to 1 as you increase the length of your messages (blocklength). This is crucial for defining capacity as a sharp threshold.

While these concepts are related, their precise connection, especially across different types of networks and different definitions of "small capacity" or "high error rate," was not fully understood. This paper aims to bridge this gap by formally defining various notions of edge removal and strong converses and proving their equivalences and implications.

Methods

The paper introduces a rich taxonomy of "strong converse" and "edge removal" properties, categorized by how edge capacity and error probability scale with blocklength. The core of their methodology involves:

  • Formal Definitions: Precisely defining multiple levels of strong converses (extremely strong, exponentially strong, strong) and edge removal properties (extremely weak, very weak, weak, strong).
  • Implication Proofs: Demonstrating that certain strong converses imply corresponding edge removal properties across a broad class of networks.
  • Equivalence Proofs: Proving that for specific network types (e.g., deterministic networks, discrete stationary memoryless networks), the implication holds in both directions, establishing equivalence.
  • Novel Techniques: A key technical contribution is a novel, "causal version of the blowing-up lemma," which is instrumental in proving the equivalence between the weak edge removal property and the exponentially strong converse for discrete stationary memoryless networks.
  • Network Equivalence: Leveraging the concept of network equivalence to relate properties of noisy networks to their noiseless counterparts, simplifying analysis.

Datasets

Not discussed in the paper. The paper is theoretical and focuses on abstract network models rather than empirical datasets.

Key Insights and Ideas

  • Strong Converses are Edge Removal Properties (in many cases): The most striking insight is that for a wide range of networks, the existence of a strong converse property is fundamentally equivalent to an edge removal property. This suggests that the "sharpness" of capacity as a threshold is deeply tied to how robust the network is to small perturbations in edge capacities.
  • Hierarchy of Properties: The paper carefully maps out a hierarchy of these properties, showing how stronger forms of converses imply stronger forms of edge removal, and vice-versa for certain network classes.
  • The Power of the Blowing-Up Lemma: A modified blowing-up lemma proves crucial for establishing equivalences, highlighting its continued importance in information theory.
  • Deterministic Networks as a Testbed: Deterministic networks serve as a key case where the equivalences are particularly strong, allowing for a deeper understanding of the fundamental relationships.
  • Practical Implications for Outer Bounds: The results suggest that many existing outer bounds (which provide upper limits on network capacity) can be strengthened to hold in an exponentially strong sense with relatively little effort, making them more powerful tools.

Key Results

  • General Implication: Every class of strong converse implies a specific class of edge removal property for any causal network channel.
  • Equivalence for Deterministic Networks: For deterministic networks, the implications hold in both directions, meaning strong converses and edge removal properties are equivalent.
  • Equivalence for Discrete Stationary Memoryless Networks: The weak edge removal property is shown to be equivalent to the exponentially strong converse for this broad class of networks. This is a major result, as it connects a "first-order" property (edge removal) to a "one-and-a-half-th order" property (exponentially strong converse).
  • Applications: The framework is applied to derive exponentially strong converses for problems like the cut-set bound, broadcast channels, and the 2-user interference channel with strong interference.

Limitations and Future Work

  • General Networks: While many results hold for general networks, the strongest equivalences (e.g., between weak edge removal and exponentially strong converse) are proven for specific classes like discrete stationary memoryless networks. The paper leaves open the question of whether these equivalences hold for all memoryless stationary networks.
  • Discrete vs. Continuous: Many results are presented for discrete (finite alphabet) networks. Generalizing these to continuous systems, channel cost constraints, or source coding contexts is suggested as future work.
  • Extremely Weak Edge Removal: The paper notes that the "extremely weak edge removal property" does not appear in their main results relating to strong converses, posing an open question about its potential converse equivalent.
  • Open Problems: The authors explicitly list several open problems, including the general validity of edge removal/strong converse properties, generalization to continuous systems, and finding a converse property equivalent to the extremely weak edge removal property.

Summary updated

Abstract

This paper explores the relationship between two ideas in the network information theory: edge removal and strong converses. Edge removal properties state that if an edge of small capacity is removed from a network, the capacity region does not change too much. Strong converses state that, for rates outside the capacity region, the probability of error converges to 1 as the blocklength goes to infinity. Various notions of edge removal and strong converse are defined, depending on how edge capacity and error probability scale with blocklength, and relations between them are proved. Each class of strong converse implies a specific class of edge removal. The opposite directions are proved for deterministic networks. Furthermore, a technique based on a novel, causal version of the blowing-up lemma is used to prove that for discrete memoryless networks, the weak edge removal property-that the capacity region changes continuously as the capacity of an edge vanishes-is equivalent to the exponentially strong converse-that outside the capacity region, the probability of error goes to 1 exponentially fast. This result is used to prove exponentially strong converses for several examples, including the discrete two-user interference channel with strong interference, with only a small variation from traditional weak converse proofs.
BibTeX
@article{kosut2019strong,
  author = {Oliver Kosut and Jörg Kliewer},
  title = {{Strong Converses are Just Edge Removal Properties}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=crPV86rBANx},
}
Figure