详细内容或原文请订阅后点击阅览
分布式估计的通信复杂性
我们研究标准两方通信模型的扩展，其中 Alice 和 Bob 分别在 XXX 和 YYY 域上持有概率分布 ppp 和 qqq。他们的目标是估计 Ex∼p,y∼q[f(x,y)]\mathbb{E}_{x \sim p, y \sim q}[f(x, y)]Ex∼p,y∼q[f(x,y)] 到双方已知的有界函数 fff 的加性误差 ε\varepsilonε 内。我们将此称为分布式估计问题。这个问题的特殊情况出现在各个领域，包括草图、数据库和学习。我们的目标是了解所需的沟通如何与......
来源:Apple机器学习研究我们研究标准两方通信模型的扩展，其中 Alice 和 Bob 分别在 XXX 和 YYY 域上持有概率分布 ppp 和 qqq。他们的目标是估计
Ex∼p,y∼q[f(x,y)]\mathbb{E}_{x \sim p, y \sim q}[f(x, y)]Ex∼p,y∼q[f(x,y)]
到双方已知的有界函数 fff 的加性误差 ε\varepsilonε 内。我们将此称为分布式估计问题。这个问题的特殊情况出现在各个领域，包括草图、数据库和学习。我们的目标是了解所需的通信如何随着 fff 的通信复杂性和误差参数 ε\varepsilonε 的变化而变化。
随机抽样方法 - 通过平均 O(1/ε2)O(1/\varepsilon^2)O(1/ε2) 个随机样本来估计平均值 - 需要 O(R(f)/ε2)O(R(f)/\varepsilon^2)O(R(f)/ε2) 总通信量，其中 R(f)R(f)R(f) 是 fff 的随机通信复杂度。我们设计了一种新的去偏协议，它将 1/ε1/\varepsilon1/ε 的依赖性提高为线性而不是二次。此外，我们还展示了几种特殊函数类别的更好上限，包括等于函数和大于函数。我们引入了基于谱方法和差异的下界技术，并展示了我们许多协议的最优性：去偏协议对于一般函数是严格的，并且我们的相等和大于函数协议也是最优的。此外，我们还表明，在全秩布尔函数中，Equality 本质上是最简单的。