Communication with Contextual Uncertainty

Badih Ghazi, Ilan Komargodski, Pravesh Kothari, Madhu SudanSODA 2016 · DOI · OpenReview

TL;DR

This paper introduces a novel model for communication complexity where one party (Alice) has an imperfect understanding of the communication goal, which is known to the other party (Bob). They show that this "contextual uncertainty" can significantly increase communication costs, but surprisingly, not as much as one might fear, especially when the underlying data distribution is simple. They also demonstrate that this uncertainty is fundamental and cannot be overcome by simply trying to resolve it first.

What Problem Does This Paper Address?

Imagine two people, Alice and Bob, trying to communicate to achieve a specific task. In many scenarios, they share a common understanding of the task's goal – this is the "context." However, in real-world situations, this shared context might not be perfect. Alice might have a slightly different idea of what Bob wants to achieve than Bob actually does. This paper tackles this problem by formalizing "contextual uncertainty" in communication.

Specifically, they consider a setting where Bob knows the exact function he wants to compute, say $g(x, y)$, where $x$ and $y$ are private inputs. Alice, however, only knows an approximation of this function, say $f(x, y)$, which is close to $g$ but not identical. The challenge is to design communication protocols that allow Alice and Bob to compute $g(x, y)$ reliably, despite Alice's imperfect knowledge of the target function. This is a departure from traditional communication complexity, where both parties are assumed to know the function perfectly. The authors aim to quantify how much this uncertainty impacts the communication cost and to understand the fundamental limits imposed by this scenario.

Methods

The paper introduces a new model called "Contextually Uncertain Communication Complexity." Here's a breakdown of their approach:

  • Formalizing Uncertainty: They define the problem where Alice knows $(f, x)$ and Bob knows $(g, y)$, with $f$ being an approximation of $g$. The pair $(x, y)$ is drawn from a distribution $\mu$, and $f$ and $g$ are chosen such that they are "close" under this distribution.
  • Upper Bounds: They derive an upper bound on the communication complexity. A key result (Theorem 1.1) shows that if a function $g$ has a one-way communication protocol of complexity $k$ in the standard setting, then in the uncertain setting, a protocol exists with complexity $O(k \cdot (1 + I(X; Y)))$, where $I(X; Y)$ is the mutual information between the inputs $x$ and $y$. This means the communication cost increases, but not drastically, especially when $I(X; Y)$ is small.
  • Product Distributions: A particularly interesting case is when the input distribution $\mu$ is a product distribution (i.e., $x$ and $y$ are independent). In this scenario, $I(X; Y) = 0$, and the communication complexity only incurs a constant factor blow-up compared to the standard setting (Corollary 1.2).
  • Lower Bounds: To show that the dependence on mutual information is necessary, they construct a scenario (Theorem 1.3) where the standard communication complexity is just 1 bit, but under contextual uncertainty with a non-product distribution, the complexity can be as high as $\Omega(\sqrt{n})$.
  • Hardness of Agreement: They also prove that a naive approach of first trying to "resolve the uncertainty" by agreeing on a common function $q$ is computationally expensive. They show that this "agreement problem" itself can require significant communication, demonstrating that a direct approach to computing $g$ is more efficient.
  • Correlated Sampling: For the upper bound, they leverage a technique called "correlated sampling" from information theory, adapting it to their one-way communication setting.

Datasets

Not discussed in the paper. The paper focuses on theoretical communication complexity and does not involve empirical evaluation on datasets.

Key Insights and Ideas

  • Uncertainty is Quantifiable and Manageable: The paper shows that contextual uncertainty doesn't necessarily lead to an exponential communication explosion. There are structured ways to handle it, especially when the data distribution is simple.
  • Mutual Information is Key: The dependence on mutual information $I(X; Y)$ in the upper bound is not just a theoretical artifact; it's shown to be necessary for non-product distributions, highlighting the role of input correlations in mitigating uncertainty.
  • "Resolve Uncertainty First" is Inefficient: The authors demonstrate that trying to perfectly align on the communication goal before proceeding is a suboptimal strategy, often requiring much more communication than a direct approach.
  • Canonical Form of Protocols: The proof of the upper bound relies on the idea that low-communication one-way protocols have a specific structure, which helps in designing a protocol that works even with uncertainty.

Key Results

  • Upper Bound (Theorem 1.1): For a function $g$ with standard one-way communication complexity $k$, the contextually uncertain communication complexity is $O(k \cdot (1 + I(X; Y)))$.
  • Product Distribution Case (Corollary 1.2): When the input distribution is a product distribution, the complexity is $O(k)$, meaning only a constant factor increase.
  • Lower Bound (Theorem 1.3): There exist scenarios where standard communication is 1 bit, but contextually uncertain communication is $\Omega(\sqrt{n})$ bits, demonstrating the necessity of the $I(X; Y)$ term.
  • Hardness of Agreement (Theorem 3.2): The problem of agreeing on a common function can require communication polynomial in the size of the domain, even for simple functions.

Limitations and Future Work

  • Two-Way Protocols: The current results focus on one-way communication. Extending these findings to two-way protocols is a significant open question. The authors suggest that finding a "canonical form" for two-way protocols that gracefully handles uncertainty is key.
  • Notions of Distance: The paper uses Hamming distance to quantify the gap between Alice's estimate and Bob's true goal. Exploring other distance metrics that might better capture real-world uncertainty is suggested.
  • Mixture of Adversarial and Probabilistic Elements: The model combines adversarial choices (of functions $f, g$) with probabilistic inputs $(x, y)$. The authors believe that exploring richer mixtures of these elements could lead to more general and realistic uncertainty models.
  • Exponent of Mutual Information: Determining the precise exponent of $I(X; Y)$ in the upper bound is an open question, with current results suggesting it's between 1/2 and 1.

Summary updated

Abstract

We introduce a simple model illustrating the role of context in communication and the challenge posed by uncertainty of knowledge of context. We consider a variant of distributional communication complexity where Alice gets some information x and Bob gets y, where (x, y) is drawn from a known distribution, and Bob wishes to compute some function g(x, y) (with high probability over (x, y)). In our variant, Alice does not know g, but only knows some function f which is an approximation of g. Thus, the function being computed forms the context for the communication, and knowing it imperfectly models (mild) uncertainty in this context. A naive solution would be for Alice and Bob to first agree on some common function h that is close to both f and g and then use a protocol for h to compute h(x, y). We show that any such agreement leads to a large overhead in communication ruling out such a universal solution. In contrast, we show that if g has a one-way communication protocol with complexity k in the standard setting, then it has a communication protocol with complexity O(k · (1 + I)) in the uncertain setting, where I denotes the mutual information between x and y. In the particular case where the input distribution is a product distribution, the protocol in the uncertain setting only incurs a constant factor blow-up in communication and error. Furthermore, we show that the dependence on the mutual information I is required. Namely, we construct a class of functions along with a non-product distribution over (x, y) for which the communication complexity is a single bit in the standard setting but at least bits in the uncertain setting.
BibTeX
@inproceedings{ghazi2016communication,
  author = {Badih Ghazi and Ilan Komargodski and Pravesh Kothari and Madhu Sudan},
  title = {{Communication with Contextual Uncertainty}},
  booktitle = {SODA},
  year = {2016},
  doi = {10.1137/1.9781611974331.ch144},
}

Loading related content...

Figure