Skip to yearly menu bar Skip to main content


Poster

Pointwise Bounds for Distribution Estimation under Communication Constraints

Wei-Ning Chen · Peter Kairouz · Ayfer Ozgur

Keywords: [ ]


Abstract: We consider the problem of estimating a d-dimensional discrete distribution from its samples observed under a b-bit communication constraint. In contrast to most previous results that largely focus on the global minimax error, we study the local behavior of the estimation error and provide \emph{pointwise} bounds that depend on the target distribution p. In particular, we show that the 2 error decays with O(p1/2n2b1n) when n is sufficiently large, hence it is governed by the \emph{half-norm} of p instead of the ambient dimension d. For the achievability result, we propose a two-round sequentially interactive estimation scheme that achieves this error rate uniformly over all p. Our scheme is based on a novel local refinement idea, where we first use a standard global minimax scheme to localize p and then use the remaining samples to locally refine our estimate.We also develop a new local minimax lower bound with (almost) matching 2 error, showing that any interactive scheme must admit a Ω(p(1+δ)/2n2b) 2 error for any δ>0 when n is sufficiently large. The lower bound is derived by first finding the best parametric sub-model containing p, and then upper bounding the quantized Fisher information under this model. Our upper and lower bounds together indicate that the H1/2(p)=log(p1/2) bits of communication is both sufficient and necessary to achieve the optimal (centralized) performance, where H1/2(p) is the R\'enyi entropy of order 2. Therefore, under the 2 loss, the correct measure of the local communication complexity at p is its R\'enyi entropy.

Chat is not available.