PAC Learnability for Reliable Communication over Discrete Memoryless Channels

In practical communication systems, knowledge of channel models is often absent, and consequently, transceivers need be designed based on empirical data. In this work, we study data-driven approaches to reliably choosing decoding metrics and code rates that facilitate reliable communication over unknown discrete memoryless channels (DMCs). Our analysis is inspired by the PAC (probably approximately correct) learning theory and does not rely on any assumptions on the statistical characteristics of DMCs. We show that a naive plug-in algorithm for choosing decoding metrics is likely to fail for finite training sets. We propose an alternative algorithm called the virtual sample algorithm and establish a non-asymptotic lower bound on its performance. The virtual sample algorithm is then used as a building block for constructing a learning algorithm that chooses a decoding metric and a code rate using which a transmitter and a receiver can reliably communicate at a rate arbitrarily close to the channel mutual information. Therefore, we conclude that DMCs are PAC learnable.