Inference under Information Constraints: Lower Bounds from ChiSquare Contraction
[edit]
Proceedings of the ThirtySecond Conference on Learning Theory, PMLR 99:317, 2019.
Abstract
Multiple users getting one sample each from an unknown distribution seek to enable a central server to conduct statistical inference. However, each player can only provide limited amount of information about its sample to the server. We propose a unified framework to study such distributed inference problems under local information constraints. We model the local information constraints by a set of channels $\mathcal{W}$: each player chooses a channel from $\mathcal{W}$, and then passes their data through this channel before transmitting the output to the server. The goal in this distributed setting is to understand the blowup in data requirement imposed by the information constraints, compared to the centralized setting where all data samples are available to the server. We introduce two notions of \emph{chisquare fluctuations} which provide bounds for the average distance and the distance to the average of a local perturbation. When information constraints are imposed, by the standard dataprocessing inequality, pairwise distances contract and so do our chisquare fluctuations. We provide a precise characterization of this contraction for discrete $k$ary distributions and use it to obtain to general lower bounds for distribution learning and testing under information constraints. Our results involve notions of minmax and maxmin chisquare fluctuations, where the maximum is over the choice of channels and the minimum is over perturbations. The former emerges when considering publiccoin protocols for testing and is bounded in terms of Frobenius norm of a positive semidefinite matrix $H$, a function of the channel family $\mathcal{W}$. The latter appears for privatecoin protocols and is bounded by the nuclear norm of $H$ which is smaller than its Frobenius norm, establishing a separation between the sample complexity of testing using public and private coins.
Related Material


