Information Constrained Optimal Transport: From Talagrand, to Marton, to Cover
This work addresses foundational problems in information theory and optimal transport, with applications in network information theory, though it builds on existing approaches like Marton's.
The paper introduces an information-constrained optimal transport problem, which strengthens and generalizes Talagrand's transportation cost inequality, and applies it to recover concentration of measure results and solve Cover's open problem on relay channel capacity.
The optimal transport problem studies how to transport one measure to another in the most cost-effective way and has wide range of applications from economics to machine learning. In this paper, we introduce and study an information constrained variation of this problem. Our study yields a strengthening and generalization of Talagrand's celebrated transportation cost inequality. Following Marton's approach, we show that the new transportation cost inequality can be used to recover old and new concentration of measure results. Finally, we provide an application of this new inequality to network information theory. We show that it can be used to recover almost immediately a recent solution to a long-standing open problem posed by Cover regarding the capacity of the relay channel.