The Optimality of Correlated Sampling

By Mohammad Bavarian, Badih Ghazi, Elad Haramaty, Pritish Kamath, R. Rivest, Madhu Sudan. 2016

13 citations recorded by the source corpus.

In the "correlated sampling" problem, two players, say Alice and Bob, are given two distributions, say $P$ and $Q$ respectively, over the same universe and access to shared randomness. The two players are required to output two elements, without any interaction, sampled according to their respective distributions, while trying to minimize the probability that their outputs disagree. A well-known protocol due to Holenstein, with close variants (for similar problems) due to Broder, and to Kleinberg and Tardos, solves this task with disagreement probability at most $2 \delta/(1+\delta)$, where $\delta$ is the total variation distance between $P$ and $Q$. This protocol has been used in several different contexts including sketching algorithms, approximation algorithms based on rounding linear programming relaxations, the study of parallel repetition and cryptography. In this note, we give a surprisingly simple proof that this protocol is in fact tight. Specifically, for every $\delta \in (0,1)$, we show that any correlated sampling scheme should have disagreement probability at least $2\delta/(1+\delta)$. This partially answers a recent question of Rivest. Our proof is based on studying a new problem we call "constrained agreement". Here, Alice is given a subset $A \subseteq [n]$ and is required to output an element $i \in A$, Bob is given a subset $B \subseteq [n]$ and is required to output an element $j \in B$, and the goal is to minimize the probability that $i \neq j$. We prove tight bounds on this question, which turn out to imply tight bounds for correlated sampling. Though we settle basic questions about the two problems, our formulation also leads to several questions that remain open.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Distributed Simulation and Distributed Inference (2018, positive): “Starting with the works of Gács and Körner [GK73] and Wyner [Wyn75], these include among others correlated sampling [Bro97, KT02, Hol07, BGH + 16], where two players with shared randomness, and given the explicit description of two distributions p , q need to output, without communicating, samples x”
Multi-Agent Common Knowledge Reinforcement Learning (2018, methodology): “However, in Section 6.3 we show empirically that, using a naive correlated sampling protocol similar to the theoretically optimal Holenstein protocol (Holenstein, 2007; Bavarian et al., 2016), MACKRLcan still succeed in the presence of moderate sensor noise.”
Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “Starting with [25] and [47] where the problem of generating shared randomness from correlated randomness and vice-versa, respectively, were considered, several important variants have been studied such as correlated sampling [11], [16], [34], [38] and noninteractive simulation [20], [27], [36].”