Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #1 to TR18-079 | 11th August 2018 02:28

Distributed Simulation and Distributed Inference

Revision #1
Authors: Jayadev Acharya, Clement Canonne, Himanshu Tyagi
Accepted on: 11th August 2018 02:28
Keywords:

Abstract:

Independent samples from an unknown probability distribution $\textbf{p}$ on a domain of size $k$ are distributed across $\ns$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing model of communication to help the referee infer a property of the unknown $\textbf{p}$. What is the least number of players for inference required in the communication-starved setting of $\ell <\log k$? We begin by exploring a general \emph{simulate-and-infer} strategy for such inference problems where the center simulates the desired number of samples from the unknown distribution and applies standard inference algorithms for the collocated setting. Our first result shows that for $\ell<\log k$ perfect simulation of even a single sample is not possible. Nonetheless, we present next a Las Vegas algorithm that simulates a single sample from the unknown distribution using no more than $O(k/2^\ell)$ samples in expectation. As an immediate corollary, it follows that simulate-and-infer attains the optimal sample complexity of $\Theta(k^2/2^{\ell}\varepsilon^2)$ for learning the unknown distribution to an accuracy of $\varepsilon$ in total variation distance.

For the prototypical testing problem of identity testing, simulate-and-infer works with $O(k^{3/2}/2^{\ell}\varepsilon^2)$ samples, a requirement that seems to be inherent for all communication protocols not using any additional resources. Interestingly, we can break this barrier using public coins. Specifically, we exhibit a public-coin communication protocol that accomplishes identity testing using $O(k/\sqrt{2^{\ell}}\varepsilon^2)$ samples. Furthermore, we show that this is optimal up to constant factors. Our theoretically sample-optimal protocol is easy to implement in practice. Our proof of lower bound entails showing a contraction in $\chi^2$ distance of product distributions due to communication constraints and may be of interest beyond the current setting.

Changes to previous version:

- Added an alternative protocol for uniformity testing, the "smooth" protocol.
- Corrected some typos and improved the presentation of the appendix.

Paper:

TR18-079 | 19th April 2018 03:30

Distributed Simulation and Distributed Inference

TR18-079
Authors: Jayadev Acharya, Clement Canonne, Himanshu Tyagi
Publication: 25th April 2018 04:04
Keywords:

Abstract:

Independent samples from an unknown probability distribution $\mathbf{p}$ on a domain of size $k$ are distributed across $n$ players, with each player holding one sample. Each player can communicate $\ell$ bits to a central referee in a simultaneous message passing (SMP) model of communication to help the referee infer a property of the unknown $\mathbf{p}$. When $\ell\geq\log k$ bits, the problem reduces to the well-studied collocated case where all the samples are available in one place. In this work, we focus on the communication-starved setting of $\ell < \log k$, in which the landscape may change drastically. We
propose a general formulation for inference problems in this distributed setting, and instantiate it to two prototypical inference questions: Learning and uniformity testing.

One natural way to solve any distributed inference problem would be for the referee to simulate the distribution $\mathbf{p}$, i.e., generate enough samples from $\mathbf{p}$ using the players' messages, and then perform inference in a centralized fashion. This leads us to the following fundamental problem of distribution simulation, interesting in its own right: Can the referee simulate samples from $\mathbf{p}$ upon observing the messages from the players? Our first result shows that if $\ell<\log k$ perfect simulation of distribution is impossible for any finite number of players. This is perhaps surprising since $\log k$ bits from a single party would have sufficed. However, we provide next a Las Vegas protocol for distributed simulation that can generate a sample from the unknown distribution $\mathbf{p}$ using an expected $O(k/2^\ell)$ players, which we prove is optimal. It follows that any inference task can be solved in the distributed setting using a simulate-and-infer'' protocol with at most an $O(k/2^{\ell})$ multiplicative blow-up in the sample complexity compared to the collocated setting.

We then consider two core inference problems in the distributed setting: {Learning} and {uniformity testing} of $k$-ary distributions. The first is known to require $\Theta(k/\varepsilon^2)$ samples in the collocated setting, implying that the aforementioned simulate-and-infer protocol will work with $O(k^2/2^{\ell}\varepsilon^2)$-player protocol in the distributed setting. Furthermore, this number of players can be seen to be optimal using recent results, which in turn establishes that the simulate-and-infer'' approach is optimal for distribution learning.

The second inference problem of uniformity testing requires $\Theta(\sqrt{k}/\varepsilon^2)$ samples in the collocated setting [Paninski'08]. This leads to an $O(k^{3/2}/2^{\ell}\varepsilon^2)$-player protocol in the distributed setting using the simulate-and-infer scheme above. We show this is suboptimal if public randomness is allowed. Specifically, we provide a distributed uniformity testing protocol that requires only $O(\sqrt{k^2/2^\ell}/\varepsilon^2)$ players and prove that it is optimal up to constant factors.

ISSN 1433-8092 | Imprint