On the Limits of Learning a Discrete Memoryless Communication Channel

This paper explores bounds on the minimum number of channel probes required to learn sufficient information to establish reliable communication at a given communication rate (below channel capacity) for a discrete memoryless channel. Given a set of discrete channel input-output sample pairs (where for each discrete input value, the associated aggregate set of discrete output values observations is multinomially distributed), we leverage a non-asymptotic probably approximately correct (PAC) bound on the mutual information (channel capacity) between the label (discrete) random variable (RV) and the observation RV to establish a convergence rate for the worst case channel. Previous bounds (such as those based on Sanov's Theorem) provide high probability (i.e. PAC) bounds on the true mutual information that converge with rate O(log(N)/root N), where N is the number of independent and identically distributed (i.i.d.) samples used to compute the empirical probability mass functions. Using an improved PAC sublevel-set bound, we sharpen the rate of convergence to O(root log(log(N)) log(N)/N).