We study the role of interactivity in distributed statistical inference under information constraints, e.g., communication constraints and local differential privacy. We focus on the tasks of goodness-of-fit testing and estimation of discrete distributions. From prior work, these tasks are well understood under noninteractive protocols. Extending these approaches directly for interactive protocols is difficult due to correlations that can build due to interactivity; in fact, gaps can be found in prior claims of tight bounds of distribution estimation using interactive protocols. We propose a new approach to handle this correlation and establish a unified method to establish lower bounds for both tasks. As an application, we obtain optimal bounds for both estimation and testing under local differential privacy and communication constraints. We also provide an example of a natural testing problem where interactivity helps.
翻译:我们研究在信息限制(例如通信限制和当地差异隐私)下,互动在分布统计推断中的作用。我们注重于适当测试和估计离散分布的任务。从先前的工作来看,这些任务在非互动协议下是完全理解的。由于互动关系,很难直接为互动协议推广这些方法;事实上,在先前关于使用互动协议进行分配估算的严格界限的主张中,可以发现差距。我们提出了处理这一相关性的新办法,并制定了为这两项任务设定较低界限的统一方法。作为一种应用,我们获得了在地方差异隐私和通信限制下进行估算和测试的最佳界限。我们还提供了一个实例,说明在互动有助于的自然测试问题上存在的问题。