Strong Converses Are Just Edge Removal Properties

Oliver Kosut, Jörg Kliewer

Abstract

This paper explores the relationship between two ideas in 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 2-user interference channel with strong interference, with only a small variation from traditional weak converse proofs.

Introduction

In network information theory, determining the exact capacity of a general network remains a formidable challenge. To understand the fundamental limits of communication, researchers often focus on two distinct properties: Edge Removal and Strong Converses.

Edge removal concerns the structural stability of a network: does the removal of a link with negligible capacity significantly alter the overall capacity region? If not, the network is considered stable. Strong converses, on the other hand, describe the sharpness of performance limits: if a transmission rate exceeds the capacity, does the probability of error necessarily approach unity as the blocklength increases?

Historically, these properties were studied in isolation. This work, published in IEEE Transactions on Information Theory, establishes a formal mathematical bridge between them, demonstrating that a network's failure behavior is intrinsically linked to its structural stability.

Notation and Definitions

To rigorously analyze these properties, the authors define finite blocklength rate regions and asymptotic capacity regions. The notation used throughout the paper is summarized in the following table, which defines the parameters for both the original network and modified versions used in the proofs.

Notation for finite blocklength and asymptotic capacity regions

The core of the paper's argument relies on comparing the capacity region of a network $\mathcal{N}$ with a modified version where an extra link $(a, b)$ with capacity $k$ is added, connecting nodes in the set $\mathcal{V}$.

Methodology

The authors categorize different "strengths" of both properties—Extremely Strong, Exponentially Strong, and Strong—and establish a hierarchy of implications. Their technical approach involves several key innovations:

  • Causal Blowing-up Lemma: They develop a new causal version of the classic blowing-up lemma. This is crucial for network settings where outputs at a given time depend only on past and current inputs, unlike the standard non-causal version typically used for point-to-point channels.
  • Network Stacking: This technique involves "stacking" $N$ independent copies of a code to transform a single-use scenario into a long-block scenario, facilitating the application of the Law of Large Numbers.
  • Reduction Proofs: The authors demonstrate how to convert a code designed for a network with an auxiliary link into a code for the original network, effectively "pricing" the value of the extra link in terms of increased error probability.

Key Insights and Results

The central "Aha!" moment of the paper is the realization that a strong converse is essentially a statement about the marginal value of a tiny amount of extra information. If a few extra bits from an "omniscient" helper do not significantly increase capacity, then the original network must exhibit a sharp failure boundary.

Universal Implications

The authors prove that a strong converse always implies an edge removal property across a wide range of network models, including noisy, deterministic, and memoryless systems. For deterministic networks, these two concepts are shown to be perfectly equivalent.

Exponential Equivalence

For discrete memoryless networks (DMNs), the paper establishes a landmark result: Weak Edge Removal is mathematically identical to an Exponentially Strong Converse. This equivalence provides a powerful tool for proving sharp failure bounds. By simply checking if a network's capacity is continuous with respect to edge removal, researchers can infer the existence of an exponentially strong converse.

Practical Applications

Using these equivalence theorems, the authors simplify proofs for complex scenarios. They successfully reproduce the strong converse for the cut-set bound and provide a new proof for the 2-user interference channel under strong interference conditions.

Limitations and Future Work

While the paper provides a comprehensive mapping for the "middle" (exponential) level of the hierarchy, some questions remain. The equivalence for the "lowest" level—Very Weak Edge Removal versus the standard Strong Converse—is currently proven only for deterministic networks and acyclic point-to-point links. The authors conjecture that this equivalence holds for all DMNs.

Furthermore, the current framework focuses on discrete systems and average error probability. Generalizing these results to continuous Gaussian channels or systems under maximal error criteria represents a significant direction for future research, as edge removal properties are known to behave differently under maximal error constraints.

Summary updated

Abstract

This paper explores the relationship between two ideas in 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 2-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},
}

Loading related content...

Figure