We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions ppp and qqq over domains XXX and YYY, respectively. Their goal is to estimate
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)]
to within additive error εvarepsilonε for a bounded function fff, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the… Read More
The Communication Complexity of Distributed Estimation
We study an extension of the standard two-party communication model in which Alice and Bob hold probability distributions ppp and qqq over domains XXX and YYY, respectively. Their goal is to estimate
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)]
to within additive error εvarepsilonε for a bounded function fff, known to both parties. We refer to this as the distributed estimation problem. Special cases of this problem arise in a variety of areas including sketching, databases and learning. Our goal is to understand how the required communication scales with the…
Related Posts
Reasoning’s Razor: Reasoning Improves Accuracy but Can Hurt Recall at Critical Operating Points in Safety and Hallucination Detection
Reasoning has become a central paradigm for large language models (LLMs), consistently boosting accuracy across…
16 Google AI tips for stress-free holiday hosting in 2025
Use Gemini, Search, Pixel and more to make holiday planning feel effortless in 2025.
Barriers for Learning in an Evolving World: Mathematical Understanding of Loss of Plasticity
Deep learning models excel in stationary data but struggle in non-stationary environments due to a…