A Few Interactions Improve Distributed Nonparametric Estimation, Optimally
share
Consider the problem of nonparametric estimation of an unknown β-Hölder smooth density p_XY at a given point, where X and Y are both d dimensional. An infinite sequence of i.i.d. samples (X_i,Y_i) are generated according to this distribution, and Alice and Bob observe (X_i) and (Y_i), respectively. They are allowed to exchange k bits either in oneway or interactively in order for Bob to estimate the unknown density. For β∈(0,2], we show that the minimax mean square risk is order (k/log k)^-2β/d+2β for one-way protocols and k^-2β/d+2β for interactive protocols. The logarithmic improvement is nonexistent in the parametric counterparts, and therefore can be regarded as a consequence of nonparametric nature of the problem. Moreover, a few rounds of interactions achieve the interactive minimax rate: we show that the number of rounds can grow as slowly as the super-logarithm (i.e., inverse tetration) of k.
READ FULL TEXT