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
Memory-Efficient Backpropagation for Fine-Tuning LLMs on Resource-Constrained Mobile Devices
Fine-tuning large language models (LLMs) with backpropagation — even for a subset of parameters such…
PrimeX: A Dataset of Worldview, Opinion, and Explanation
As the adoption of language models advances, so does the need to better represent individual…
Fixing Enterprise Apps with AI: The T+n Problem
We’ve been watching enterprises struggle with the same customer service paradox for years: They have…