Channel simulation involves generating a sample$Y$from the conditional distribution$P_{Y\vert X}$, where$X$is a remote realization sampled from$P_{X}$. This paper introduces a novel approach to approximate Gaussian channel simulation using dithered quantization. Our method concurrently simulates$n$channels, reducing the upper bound on the excess information by half compared to one-dimensional methods. When used with higher-dimensional lattices, our approach achieves up to six times reduction on the upper bound. Furthermore, we demonstrate that the KL divergence between the distributions of the simulated and Gaussian channels decreases with the number of dimensions at a rate of$O(n^{-1})$.

In this work, we study the problem of communicating multiple samples from an unknown probability distribution using as few bits as possible. This is a generalization of the channel simulation problem, which has recently found applications and achieved state of the art results in realistic image compression, neural network compression, and communication-efficient federated learning. In this problem, the transmitter wants the receiver to generate multiple independent and identically distributed (i.i.d.) samples from a target distribution $P$, while the transmitter and the receiver have access to independent samples from a reference distribution $Q$. The core idea is to employ channel simulation in multiple rounds while updating the reference distribution $Q$ after each round in order to reduce the KL-divergence between $P$ and $Q$, thereby reducing the communication cost in subsequent rounds. We derive a lower bound on the expected communication cost and construct a practical algorithm that achieves the lower bound up to a multiplicative constant. We then employ this algorithm in communication-efficient federated learning, in which model updates correspond to samples from a distribution, and achieve a 37% reduction in the communication load. To further highlight the potential of sample communication for generative models, we show that the number of bits needed to communicate samples from a large language model can be reduced by up to 16 times, compared to entropy-based data compression.

Consider an agent/decoder placed at a fixed vertex of a known directed weighted graph. The controller/encoder observes the location of a target placed at another random vertex of the graph, and its goal is to help the agent to reach this target with the minimal total cost, dictated by the weights of the edges traversed on the way. The encoder can transmit only a limited number of bits to the decoder at each step of the algorithm. Our goal is to identify the optimal trade-off between the available communication budget and the average total cost. We formulate this problem as a goal-oriented compression problem with decoder constraints, which generalizes classical lossless compression problems. We show that this problem is in general NP-complete, and construct several suboptimal algorithms for solving it in polynomial-time with bounds on their suboptimality gap. We also show a lower bound on the expected cost for any coding scheme, assuming unit cost for each transition.

We consider the problem of communicating a sequence of concepts, i.e., unknown and potentially stochastic maps, which can be observed only through examples, i.e., the mapping rules are unknown. The transmitter applies a learning algorithm to the available examples, and extracts knowledge from the data by optimizing a probability distribution over a set of models, i.e., known functions, which can better describe the observed data, and so potentially the underlying concepts. The transmitter then needs to communicate the learned models to a remote receiver through a rate-limited channel, to allow the receiver to decode the models that can describe the underlying sampled concepts as accurately as possible in their semantic space. After motivating our analysis, we propose the formal problem of communicating concepts, and provide its rate-distortion characterization, pointing out its connection with the concepts of empirical and strong coordination in a network. We also provide a bound for the distortion-rate function.

We propose a novel formulation of the “effectiveness problem” in communications, put forth by Shannon and Weaver in their seminal work “The Mathematical Theory of Communication”, by considering multiple agents communicating over a noisy channel in order to achieve better coordination and cooperation in a multi-agent reinforcement learning (MARL) framework. Specifically, we consider a multi-agent partially observable Markov decision process (MA-POMDP), in which the agents, in addition to interacting with the environment, can also communicate with each other over a noisy communication channel. The noisy communication channel is considered explicitly as part of the dynamics of the environment, and the message each agent sends is part of the action that the agent can take. As a result, the agents learn not only to collaborate with each other but also to communicate “effectively” over a noisy channel. This framework generalizes both the traditional communication problem, where the main goal is to convey a message reliably over a noisy channel, and the “learning to communicate” framework that has received recent attention in the MARL literature, where the underlying communication channels are assumed to be error-free. We show via examples that the joint policy learned using the proposed framework is superior to that where the communication is considered separately from the underlying MA-POMDP. This is a very powerful framework, which has many real world applications, from autonomous vehicle planning to drone swarm control, and opens up the rich toolbox of deep reinforcement learning for the design of multi-user communication systems.