Universal Quantile Estimation with Feedback in the Communication-Constrained Setting

We consider the following problem of decentralized-statistical inference: given i.i.d. samples from an unknown distribution, estimate an arbitrary quantile subject to limits on the number of bits exchanged. We analyze a standard fusion-based architecture, in which each of m sensors transmits a single bit to the fusion center, which in turn is permitted to send some number k bits of feedback. Supposing that each of m sensors receives n observations, the mean-squared error of the optimal centralized protocol decays as O(1/nm). First, we describe the decentralized protocol based on k = m bits of feedback that is strongly consistent, and achieves the same asymptotic MSE as the centralized optimum. Second, we describe and analyze a decentralized protocol based on only a single bit (k = 1) of feedback. For step sizes independent of m, it achieves an asymptotic MSE of order O(1/nradicm), whereas for step sizes decaying as m^-1/2, it achieves the same order of MSE - namely, O(1/nm) - as the centralized optimum. We discuss the tradeoffs between these different protocols