  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.
