The Price of Uncertain Priors in Source Coding

Mark Braverman, Brendan Juba

TL;DR

This paper quantifies the "price of uncertainty" in communication: how many extra bits must a sender use when the receiver doesn't know the exact probability distribution of the messages? The authors prove that for error-free communication, you need an overhead of roughly $2 \log \alpha$ bits (where $\alpha$ is the uncertainty factor), and they show that allowing a small probability of error $\epsilon$ reduces this cost to approximately $\log \alpha + \log(1/\epsilon)$ bits.

What Problem Does This Paper Address?

In classical Shannon information theory, we assume the sender and receiver perfectly agree on the probability distribution ($P$) of the messages being sent. This allows them to use optimal codes (like Huffman or Arithmetic coding) where frequent messages get short codewords and rare ones get long ones.

But what if they don't agree? In the real world, "shared context" is often imperfect. Perhaps the sender uses a distribution $P$, but the receiver expects a distribution $Q$. If $Q$ is "close" to $P$, can we still communicate efficiently?

The authors use a model of "$\alpha$-closeness," where the ratio of the two distributions is bounded: $\frac{1}{\alpha} Q(m) \le P(m) \le \alpha Q(m)$. The central question is: What is the minimum redundancy (extra bits beyond the entropy $H(P)$) required to guarantee successful decoding under this uncertainty?

Methods

The paper is a theoretical study that employs techniques from communication complexity and information theory.

To prove lower bounds (the minimum bits required), the authors construct a "hard" family of distributions. They use a reduction to a one-way communication game: Alice gets a message, Bob gets a set of possible messages, and Alice must send enough information so Bob can pick the right one. By applying Von Neumann’s Min-max Theorem to a zero-sum game between a "coding scheme" player and an "input" player, they show that no scheme can beat their calculated limits.

To prove upper bounds (the bits achieved by a specific strategy), they analyze a randomized coding scheme where Alice and Bob share an infinite random string. Alice sends a prefix of this string that is unique to her message under the receiver's likely distribution.

Datasets

Theoretical work; no empirical datasets were used. The results are mathematical proofs applicable to any discrete message space.

Key Insights and Ideas

  • The "Price" is Logarithmic: The overhead doesn't depend on the size of the message universe, but rather on the degree of uncertainty ($\alpha$).
  • Error-Free vs. Error-Tolerant: There is a significant "jump" in efficiency if you allow a tiny bit of error.
  • In the error-free setting, the sender must account for all possible $\alpha$-close distributions simultaneously. This "worst-case" requirement forces a redundancy of $2 \log \alpha$.
  • In the positive-error setting (allowing failure with probability $\epsilon$), the sender only needs to be "unique enough" for the most likely candidates, dropping the cost to $\log \alpha + \log(1/\epsilon)$.
  • Computational Asymmetry: The authors point out that error-tolerant schemes are not just shorter; they are computationally easier for the sender to encode. In the error-free version, the sender has to check many more potential "collisions" before sending the message.

Key Results

The paper successfully "brackets" the redundancy for both major variants of the problem, showing that previous upper bounds were nearly optimal:

  1. Error-Free Coding: The redundancy must be at least $2 \log \alpha - O(\log \log \alpha)$. This matches the known upper bound of $2 \log \alpha + 2$, settling the first-order cost of error-free uncertain communication.
  2. Positive-Error Coding:
    • Upper Bound: They present a scheme achieving $H(P) + \log \alpha + \log(1/\epsilon) + 1$ bits.
  3. Lower Bound: They prove a minimum redundancy of $\log \alpha + \log(1/\epsilon) - O(\log \log \alpha)$.
  4. This shows that the "price of uncertainty" is essentially halved if you can tolerate a small error rate.

Limitations and Future Work

  • The $\log \log$ Gap: There remains a small gap in the lower-order terms (the $O(\log \log \alpha)$ parts). Tightening these to constant terms remains an open problem.
  • Decoding Complexity: While the encoding for the error-tolerant scheme is efficient, the decoding still requires the receiver to potentially examine $1/Q(m)$ messages, which can be computationally expensive if the message is very rare.
  • Multi-Message Communication: The paper focuses on sending a single message. If multiple messages are sent from the same source, the receiver could theoretically "learn" the distribution $P$ over time, eventually reducing the redundancy to zero. The authors suggest exploring the transition point where learning makes these "uncertain prior" schemes unnecessary.
  • Deterministic Schemes: The results here rely on Alice and Bob sharing a random string. The bounds for deterministic schemes (no shared randomness) are expected to be much worse, potentially depending on the total number of possible messages.

Summary updated

Abstract

We consider the problem of one-way communication when the recipient does not know exactly the distribution that the messages are drawn from, but has a “prior” distribution that is known to be close to the source distribution, a problem first considered by Juba et al. We consider the question of how much longer the messages need to be in order to cope with the uncertainty about the receiver's prior and the source distribution, respectively, as compared with the standard source coding problem. We consider two variants of this uncertain priors problem: the original setting of Juba et al. in which the receiver is required to correctly recover the message with probability 1, and a setting introduced by Haramaty and Sudan, in which the receiver is permitted to fail with some probability ∈. In both settings, we obtain lower bounds that are tight up to logarithmically smaller terms. In the latter setting, we furthermore present a variant of the coding scheme of Juba et al. with an overhead of log α + log 1/∈ + 1 bits, thus also establishing the nearly tight upper bound.
BibTeX
@article{braverman2019price,
  author = {Mark Braverman and Brendan Juba},
  title = {{The Price of Uncertain Priors in Source Coding}},
  journal = {IEEE Trans. Information Theory},
  year = {2019},
  url = {https://openreview.net/forum?id=TMl30X7iwc7},
}

Loading related content...

Figure