Multi-Terminal Remote Generation and Estimation Over a Broadcast Channel with Correlated Priors

Maximilian Egger, Rawad Bitar, Antonia Wachter-Zeh, Nir Weinberger, Deniz Gündüz

Abstract

In distributed systems, an encoder often needs to assist multiple remote decoders in estimating statistical properties of a target distribution. Traditional point-to-point methods, such as Minimal Random Coding (MRC), scale linearly with the number of decoders, leading to significant communication overhead. This paper proposes a hierarchical importance sampling framework that leverages Gács-Körner common information and broadcast channels to exploit correlations between decoders' prior distributions. By decomposing the communication into a shared coarse broadcast and individual unicast refinements, the proposed method achieves substantial gains in communication efficiency while maintaining rigorous error bounds.

Introduction

Modern machine learning and signal processing frequently involve scenarios where a central entity (the encoder) possesses a complex data distribution—such as the output of a high-dimensional generative model—while multiple remote users (decoders) seek to estimate specific functions or statistical properties of that distribution.

A primary bottleneck in these systems is the communication cost. While Minimal Random Coding (MRC) allows a decoder to generate samples using its own prior distribution and shared randomness, it is fundamentally a point-to-point solution. In a multi-terminal setting with $N$ decoders, the total communication cost typically scales as $N \times O(D_{KL})$, where $D_{KL}$ represents the Kullback-Leibler divergence between the target and the prior. This paper addresses the inefficiency of the point-to-point approach by asking: How can we utilize the inherent correlations between decoders' priors to reduce the total bandwidth required?

The Hierarchical Sampling Framework

The authors introduce a two-phase Hierarchical Sampling strategy designed for a broadcast channel environment. This framework moves away from independent transmissions by identifying and exploiting shared information structures.

1. Block (Coarse) Sampling via Broadcast

The first phase utilizes the Gács-Körner common information framework to identify the shared components of the decoders' correlated priors. The encoder performs a coarse version of MRC to select a "block" or high-level sample index that is relevant to the target distribution across all decoders. Because this information is common to the entire group, it is transmitted over a broadcast channel. This allows all $N$ decoders to receive the coarse index simultaneously, incurring the communication cost of only a single transmission.

2. Conditional (Refinement) Sampling via Unicast

Following the broadcast, each decoder possesses a coarse representation of the target. The encoder then provides a specific "refinement" index to each decoder via a unicast (point-to-point) link. This secondary index allows the decoder to select a high-precision sample from within the previously identified coarse block, tailored specifically to its individual prior distribution. This "successive refinement" for sampling mirrors techniques used in source coding, where a base layer is supplemented by enhancement layers.

Theoretical Foundations and Results

The paper provides a rigorous information-theoretic analysis of this hierarchical approach, focusing on three key areas: communication cost, estimation bias, and statistical validity.

Communication Efficiency

The total communication cost is shown to be the sum of the broadcast cost and the individual refinement costs: $$\text{Total Cost} \approx O(D_{KL}(\text{common})) + \sum_{i=1}^{N} O(D_{KL}(\text{refinement}))$$ In scenarios where decoders' priors are highly correlated, the $D_{KL}(\text{common})$ term captures the bulk of the information requirement, leading to a total cost significantly lower than the $N \times O(D_{KL}(\text{total}))$ cost of naive point-to-point methods.

Error and Convergence Bounds

The authors derive high-probability error bounds for the hierarchical estimate $I_{i,K}(f)$. They demonstrate that the estimate converges to the true value $I(f)$ as the number of samples increases. Furthermore, they provide bounds on the Total Variation (TV) distance between the distribution of the generated samples and the actual target distribution, ensuring that the remote generation process is statistically sound.

Function-Specific Gains

A notable insight from the research is that the hierarchical approach is particularly effective when the functions being estimated are "smooth" or exhibit low variance across the coarse blocks. In such cases, the hierarchical variant provides even tighter error bounds than standard MRC.

Discussion and Limitations

While the hierarchical framework offers clear advantages, its efficacy depends on the existence of Gács-Körner common information. In distributions where such commonality is minimal, the broadcast gains may be reduced. Additionally, the paper identifies the optimization of partitioning functions ($g_i$) as a critical factor for performance; determining the optimal way to map priors to coarse blocks remains an area for future algorithmic development.

Conclusion

This work extends the principles of remote sampling to the multi-terminal setting by treating the problem as a hierarchical communication task. By exploiting correlations in decoder priors through a combination of broadcast and unicast transmissions, the proposed method offers a scalable path for remote estimation in large-scale distributed systems, providing both theoretical guarantees and practical communication savings.

Summary updated

BibTeX
@inproceedings{egger2025multi,
  author = {Maximilian Egger and Rawad Bitar and Antonia Wachter-Zeh and Nir Weinberger and Deniz Gündüz},
  title = {{Multi-Terminal Remote Generation and Estimation Over a Broadcast Channel with Correlated Priors}},
  booktitle = {ISIT},
  year = {2025},
  doi = {10.1109/isit63088.2025.11195529},
}
Figure