Finite Blocklength Converses in Point-to-Point and Network Information Theory: A Convex Analytic Perspective

The finite blocklength coding problem is a highly complex combinatorial optimization over functions, and one of its traditional challenges has been getting lower bounds or converses. While several finite blocklength converses have been discovered for several loss criteria using a variety of arguments, what is perhaps unsatisfactory is the absence of a common framework using which converses can be found for any loss criterion. We present a linear programming basedframework for obtaining converses for finite blocklength lossy joint source-channel coding problems. The framework applies for any loss criterion, generalizes previously known converses, and also extends to multi-terminal settings. The finite blocklength problem is posed equivalently as a nonconvex optimization problem and using a lift-and-project-like method, a close but tractable LP relaxation of this problem is derived. Lower bounds on the original problem are obtained by the construction of feasible points for the dual of this LP relaxation. A particular application of this approach leads to new converses that improve on the converses of Kostina and Verdu ́ for joint source-channel coding and lossy source-coding, and imply the converse of Polyanksiy, Poor and Verdu for channel coding. Another construction leads to a new general converse for finite blocklength joint source-channel coding that shows that the LP is tight for all blocklengths for the “matched setting” of minimization of the expected average bit-wise Hamming distortion of a q-ary uniform source over a q-ary symmetric memoryless channel.

The tightness of the LP relaxation for canonical problems in information theory shows that optimal coding in these problems shows that the finite blocklength problem is really a LP in disguise. Moreover, it has an associated “dual” viewpoint: namely, the optimal packing of “source flows” and “channel flows” that are throttled by an error density bottleneck. In the multi-terminal setting, using the language of these flows we derive improvements to converses of Miyake and Kanaya for Slepian-Wolf coding, the converse of Zhou et al for the successive refinement problem, new tight converses for compound and averaged channels and the asymmetric multiple access channel. These results provide a unified convex-analytic understanding of tractability of stochastic control problems with various information structures.

This is joint work with Ph.D. student Sharu Theresa Jose.