Metraipolis › archive › dc_3289fc5d3d77
Optimal Communication for Distributed Sparse Histogram Aggregation — arXiv:2611.04285
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.04285
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T19:01:50.072Z
- SHA-256 of the archived text
51edb75fc950acd2d616f4ae1e8bfecde1810a794656e065b0c7f24da5b852dd- Stable URL of this page
https://metraipolis.com/documento/dc_3289fc5d3d77
How to cite
Optimal Communication for Distributed Sparse Histogram Aggregation — arXiv:2611.04285 — arXiv (en), https://arxiv.org/abs/2611.04285 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_3289fc5d3d77 (Metraipolis archive dc_3289fc5d3d77, sha256 51edb75fc950acd2d616f4ae1e8bfecde1810a794656e065b0c7f24da5b852dd)
BibTeX
@misc{dc3289fc5d3d77,
title = {Optimal Communication for Distributed Sparse Histogram Aggregation — arXiv:2611.04285},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.04285},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_3289fc5d3d77; sha256 51edb75fc950acd2d616f4ae1e8bfecde1810a794656e065b0c7f24da5b852dd},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.04285. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Histogram estimation is a fundamental primitive in distributed data analysis, with applications in counting queries and federated learning. In many settings, the universe of categories is enormous, yet each user's data involves only a small subset, yielding sparse local histograms. This raises a natural question: To what extent can local sparsity reduce the communication needed to estimate the global histogram? We answer this question by characterizing the communication complexity of distributed sparse histogram estimation under prescribed $\ell_1$ distortion and failure probability constraints. Our upper bound is achieved by a randomized covering scheme that optimizes how accurately each user represents its local histogram to reduce communication. By exploiting the distortion budget directly rather than imposing unbiasedness, the scheme achieves lower communication costs than standard unbiased sampling and hashing constructions. We establish the scheme's first-order optimality through a lower bound based on local support identification. The key step is to relate communication cost directly to the number of active coordinates revealed by each user's message, rather than to bound information about the aggregate via distance-based Fano's inequalities. This characterization further quantifies how the communication advantage of heterogeneous over homogeneous encoders varies across parameter regimes. Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.IT, nuovi lavori del giorno). Categorie arXiv: Information Theory (cs.IT). Pagina del lavoro: https://arxiv.org/abs/2611.04285 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-11-04T18:38:39.754Z dalla pagina https://arxiv.org/list/math.IT/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).