Distribution Testing Lower Bounds via Reductions from Communication Complexity

By Eric Blais, Clément Louis Canonne, Tom Gur. 2019

59 citations recorded by the source corpus.

We present a new methodology for proving distribution testing lower bounds, establishing a connection between distribution testing and the simultaneous message passing (SMP) communication model. Extending the framework of Blais, Brody, and Matulef [15], we show a simple way to reduce (private-coin) SMP problems to distribution testing problems. This method allows us to prove new distribution testing lower bounds, as well as to provide simple proofs of known lower bounds. Our main result is concerned with testing identity to a specific distribution, p, given as a parameter. In a recent and influential work, Valiant and Valiant [55] showed that the sample complexity of the aforementioned problem is closely related to the ℓ2/3-quasinorm of p. We obtain alternative bounds on the complexity of this problem in terms of an arguably more intuitive measure and using simpler proofs. More specifically, we prove that the sample complexity is essentially determined by a fundamental operator in the theory of interpolation of Banach spaces, known as Peetre’s K-functional. We show that this quantity is closely related to the size of the effective support of p (loosely speaking, the number of supported elements that constitute the vast majority of the mass of p). This result, in turn, stems from an unexpected connection to functional analysis and refined concentration of measure inequalities, which arise naturally in our reduction.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Electrical and Electronic Engineering

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 Electrical and Electronic Engineering

Citations in the corpus

Inference Under Information Constraints II: Communication Constraints and Shared Randomness (2019, background): “Interestingly, a different instanceoptimal characterization due to [13] admits such a reduction, enabling us to obtain the analogue of Proposition 1 for this massively parameterized setting.”
Inference Under Information Constraints III: Local Privacy Constraints (2021, background): “[46], [19] also study the “instance-optimal” variant of the problem, introduced in [46].”
A Survey on Distribution Testing: Your Data is Big. But is it Blue? (2020, background): “Blais, Canonne, and Gur [26] obtain the distribution testing analogue of the communication complexity framework of [25]; and leverage it to revisit the “instance-optimal” identity testing bound of Theorem 5.”
Distributed Uniformity Testing (2018, methodology): “This lower bound is shown using the reduction from the 2-party Equality function given in [5]:”
Locally private non-asymptotic testing of discrete distributions is faster using interactive mechanisms (2020, background): “For a general (finite) alphabet size, Duchi et al. [2013] derive upper and lower bounds on the minimax estimation risk in this more general problem for both the L1 and L2 metrics, and, in particular, show that a generalization of the randomized response algorithm is rate-optimal in certain regimes.”
Minimax optimal conditional independence testing (2020, background): “This also highlights an important difference from the goodness-of-fit problem considered in [5, 10, 40].”