Optimal Communication for Distributed Sparse Histogram Aggregation
Abstract
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 ℓ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.
Related
- Topology Design for Distributed Consensus with Relay-Assisted Communication
- A Bilevel Neurodynamic Approach for Distributed SCAD-Regularized Sparse Least Squares
- Projection-Free Gradient Tracking Neurodynamic for Distributed Nonnegative Sparse Optimization
- Communication-Efficient Differentially Private Gradient Tracking for Distributed Optimization via Local Updates
- Communication and Privacy Trade-Offs in Distributed Storage With Shared Secret Keys
BibTeX
@misc{ye2026optimal,
title = {{Optimal Communication for Distributed Sparse Histogram Aggregation}},
author = {Fangwei Ye and Yijun Fan},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.04285},
eprint = {2611.04285},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.04285},
}
RIS
TY - UNPB
TI - Optimal Communication for Distributed Sparse Histogram Aggregation
AU - Fangwei Ye
AU - Yijun Fan
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.04285
UR - https://arxiv.org/abs/2611.04285
AB - 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 ℓ_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.
ER -