Distributed Simulation and Distributed Inference

By Jayadev Acharya, Clément Louis Canonne, Himanshu Tyagi. 2018

26 citations recorded by the source corpus.

Independent samples from an unknown probability distribution $\bf 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 model of communication to help the referee infer a property of the unknown $\bf 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 "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 a Las Vegas algorithm that simulates a single sample from the unknown distribution using $O(k/2^\ell)$ samples in expectation. As an immediate corollary, we get that simulate-and-infer attains the optimal sample complexity of $\Theta(k^2/2^\ell\epsilon^2)$ for learning the unknown distribution to total variation distance $\epsilon$. For the prototypical testing problem of identity testing, simulate-and-infer works with $O(k^{3/2}/2^\ell\epsilon^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 performs identity testing using $O(k/\sqrt{2^\ell}\epsilon^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 independent interest.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Statistics and Probability, ML Systems & Hardware

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 Statistics and Probability

In ML Systems & Hardware

Citations in the corpus

Geometric Lower Bounds for Distributed Parameter Estimation Under Communication Constraints (2018, methodology): “The second result is established using the same arguments as (Acharya et al., 2018, Theorem 4.7), while replacing one sensor by two sensors if necessary.”
Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication (2018, background): “Communication limited distributed distribution estimation has been studied in the non-private setting(e.g., [48, 4, 19, 2, 28]).”
Communication Complexity in Locally Private Distribution Estimation and Heavy Hitters (2019, background): “…inference tasks under limited communication, where the users do not have enough communication to even transmit their data [19, 20], and recent works have established optimal bounds, and algorithms for fundamental problems such as distribution estimation and hypothesis testing [21, 22, 23, 24].”
Distributed Uniformity Testing (2018, methodology): “The focus in [1] is on the trade-off between number of players (which controls the number of samples) and communication per player.”
Fisher Information Under Local Differential Privacy (2020, background): “Other works such as [13], [17], [18] have also noted the connection between communication and privacy constraints in statistical estimation.”
Minimax Bounds for Distributed Logistic Regression (2019, background): “In other works, the statistical task of interest is estimating a high-dimensional discrete distribution (Diakonikolas et al., 2017; Han et al., 2018a) or distributed property testing (Acharya et al., 2018a,b).”
Test without Trust: Optimal Locally Private Distribution Testing (2018, methodology): “Our lower bounds rely on the approach proposed in [2] (see [3] for more general results) to analyze the contractions in chi-square distance due to such constraints.”
Lower Bounds for Learning Distributions under Communication Constraints via Fisher Information (2019, background): “The high-dimensional discrete distribution estimation problem is studied in [7], [8], where extensions to distributed property testing are studied in [9], [10].”
Two Party Distribution Testing: Communication and Security (2018, background): “For testing problems, see the recent (independent) manuscript [ACT18], who studies testing of one distribution, and focuses on reducing the communication per sample (from a max of O (log n )).”