Compression with distributional and sequential constraints
File(s)
Author(s)
Kobus, Szymon
Type
Thesis
Abstract
Classical data compression focuses on the most accurate reproduction of data. However, modern applications, particularly in artificial intelligence, increasingly impose new statistical or behavioral constraints. This thesis extends compression theory and practice to these new settings. Our main tool is channel simulation—a generalization of data compression for remotely generating samples from a specified distribution.
We first establish a framework for universal channel simulation, analogous to universal source coding for when the target distribution is unknown, and provide a provably near-optimal algorithm. We then develop a computationally efficient algorithm for simulating the Gaussian channel, a ubiquitous model for which no such practical method existed. In distributed learning, we formalize remote reinforcement learning under communication constraints and propose a general, highly efficient solution employing channel simulation. Furthermore, we uncover a fundamental connection between speculative decoding—a method to accelerate large language models—and channel simulation, yielding new algorithms and speed-up guarantees. Finally, we introduce a goal-oriented compression framework for agents whose actions and communications are concurrent, for which we derive performance bounds and design practical coding schemes. The contributions in this thesis highlight the fundamental nature of channel simulation as a novel and effective tool to address a variety of the challenges in federated learning, reinforcement learning, realistic image compression, and large language model inference.
We first establish a framework for universal channel simulation, analogous to universal source coding for when the target distribution is unknown, and provide a provably near-optimal algorithm. We then develop a computationally efficient algorithm for simulating the Gaussian channel, a ubiquitous model for which no such practical method existed. In distributed learning, we formalize remote reinforcement learning under communication constraints and propose a general, highly efficient solution employing channel simulation. Furthermore, we uncover a fundamental connection between speculative decoding—a method to accelerate large language models—and channel simulation, yielding new algorithms and speed-up guarantees. Finally, we introduce a goal-oriented compression framework for agents whose actions and communications are concurrent, for which we derive performance bounds and design practical coding schemes. The contributions in this thesis highlight the fundamental nature of channel simulation as a novel and effective tool to address a variety of the challenges in federated learning, reinforcement learning, realistic image compression, and large language model inference.
Version
Open Access
Date Issued
2025-09-05
Date Awarded
2026-02-01
Copyright Statement
Attribution-NonCommercial 4.0 International Licence (CC BY-NC)
License URL
Advisor
Gündüz, Deniz
Publisher Department
Department of Electrical and Electronic Engineering
Publisher Institution
Imperial College London
Qualification Level
Doctoral
Qualification Name
Doctor of Philosophy (PhD)