Communication complexity of two-party nonparametric estimation

Jingbo Liu (UIUC)

In recent years, fundamental limits of distributed learning have been studied under many statistical models, but often with horizontal partitioning, where data sets share the same feature space but differ in samples. Nevertheless, vertical distributed learning, where data sets differ in features, has been in use in finance and medical care. In this talk, we consider a natural distributed nonparametric estimation problem with vertically partitioned datasets. Under a given budget of communication cost or information leakage constraint, we determine the minimax rates for estimating a Holder-smooth density at a given point, which reveals that interactive protocols strictly improve upon one-way protocols. Our novel estimation scheme in the interactive setting is constructed by carefully identifying a set of auxiliary random variables. The result also implies that interactive protocols strictly improve over one-way for biased binary sequences in the Gap-Hamming problem. For global estimation of a Holder-smooth density, we characterize the minimax rates up to logarithmic factors.

Paper Links:,

Recorded Talk

Coming soon!