Communication Complexity of Two-party Nonparametric Global Density Estimation

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

Consider the problem of nonparametric estimation of an unknown β -Hölder smooth density function pXY with compact support, where X and Y are both d dimensional. An infinite sequence of i.i.d. samples Xi, Yi) are generated according to this distribution, and two terminals observe (Xi) and Yi), respectively. They are allowed to exchange $k$ bits either in oneway or interactively in order for Bob to estimate the unknown density. We show that the minimax mean integrated square risk is order (\frack{\log k})-\frac{β}{d+β}} for one-way protocols, and between (\frack{\log k})-\frac{β}{d+β} and k(\frack{\log k})-\frac{β}{d+β} for interactive protocols. These rates are different from the case of pointwise density estimation which we recently determined in another work. The interactive lower bound in this work used, among other things, a recent result of Ordentlich and Polyanskiy regarding the optimality of binary inputs in certain optimizations related to the strong data processing constant.

Original languageEnglish (US)
Title of host publication2022 56th Annual Conference on Information Sciences and Systems, CISS 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Pages292-297
Number of pages6
ISBN (Electronic)9781665417969
DOIs
StatePublished - 2022
Event56th Annual Conference on Information Sciences and Systems, CISS 2022 - Princeton, United States
Duration: Mar 9 2022Mar 11 2022

Publication series

Name2022 56th Annual Conference on Information Sciences and Systems, CISS 2022

Conference

Conference56th Annual Conference on Information Sciences and Systems, CISS 2022
Country/TerritoryUnited States
CityPrinceton
Period3/9/223/11/22

ASJC Scopus subject areas

  • Information Systems and Management
  • Artificial Intelligence
  • Computer Science Applications
  • Information Systems

Cite this