arXiv preprint ·
Optimal Communication for Distributed Sparse Histogram Aggregation
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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 $\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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Information Theory
Hardware-Efficient Reinforcement-Learned Scheduling for Quantum LDPC Decoders
Hotplug Coded Caching: Embedding the YMA and Interference Elimination Schemes via Reed--Muller Codes
Functional inequalities from the fundamental limits of Bayesian estimation
Pairwise Distortion Distribution with Graph-Based Importance Sampling for Quantization Error and Intrinsic Dimension Estimation
A Complete Characterization of $q$-Ary $2$-Designs in Doubly-Extended Reed-Solomon Codes
Get the few papers worth your time in Information Theory every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.