Second-order converses via reverse hypercontractivity

Markov semigroups and applications to diffusion processes (47D07) Applications of operator theory in probability theory and statistics (47N30) Inequalities; stochastic orderings (60E15) Statistical aspects of information-theoretic topics (62B10) Statistical aspects of big data and data science (62R07) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Information theory (general) (94A15) Coding theorems (Shannon theory) (94A24)

Abstract: A strong converse shows that no procedure can beat the asymptotic (as blocklength

n o i n f t y

) fundamental limit of a given information-theoretic problem for any fixed error probability. A second-order converse strengthens this conclusion by showing that the asymptotic fundamental limit cannot be exceeded by more than

O (f r a c 1 s q r t n)

. While strong converses are achieved in a broad range of information-theoretic problems by virtue of the "blowing-up method"---a powerful methodology due to Ahlswede, G'acs and K"orner (1976) based on concentration of measure---this method is fundamentally unable to attain second-order converses and is restricted to finite-alphabet settings. Capitalizing on reverse hypercontractivity of Markov semigroups and functional inequalities, this paper develops the "smoothing-out" method, an alternative to the blowing-up approach that does not rely on finite alphabets and that leads to second-order converses in a variety of information-theoretic problems that were out of reach of previous methods.

Review text

Summary: A strong converse shows that no procedure can beat the asymptotic (as blocklength \(n\to\infty\) fundamental limit of a given information-theoretic problem for any fixed error probability. A second-order converse strengthens this conclusion by showing that the asymptotic fundamental limit cannot be exceeded by more than \(O(\frac{1}{\sqrt{n}})\). While strong converses are achieved in a broad range of information-theoretic problems by virtue of the ``blowing-up method -- a powerful methodology due to Ahlswede, Gács and Körner [\textit{R. Ahlswede} et al., Z. Wahrscheinlichkeitstheor. Verw. Geb. 34, 157--177 (1976; Zbl 0349.94038)] based on concentration of measure -- this method is fundamentally unable to attain second-order converses and is restricted to finite-alphabet settings. Capitalizing on reverse hypercontractivity of Markov semigroups and functional inequalities, this paper develops the ``smoothing-out method, an alternative to the blowing-up approach that does not rely on finite alphabets and that leads to second-order converses in a variety of information-theoretic problems that were out of reach of previous methods.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Second-order converses via reverse hypercontractivity

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778887)