Second-order converses via reverse hypercontractivity

DOI10.4171/MSL/13zbMATH Open1460.62208arXiv1812.10129MaRDI QIDQ778887FDOQ778887

Authors: Liu Jingbo, Ramon van Handel, Sergio Verdú 

Publication date: 20 July 2020

Published in: Mathematical Statistics and Learning (Search for Journal in Brave)

Abstract: A strong converse shows that no procedure can beat the asymptotic (as blocklength $noinfty$) 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(frac1sqrtn)$. 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.

Full work available at URL: https://arxiv.org/abs/1812.10129

Recommendations

• Quantum reverse hypercontractivity: its tensorization and application to strong converses
• The strong converse theorem for hypothesis testing
• On the converse to the coding theorem for discrete memoryless channels (Corresp.)
• Strong converse theorems using Rényi entropies
• Strong converse for identification via quantum channels

zbMATH Keywords

concentration of measureblowing-up lemmainformation-theoretic inequalitiesreverse hypercontractivitystrong converse

Mathematics Subject Classification ID

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

Cites Work

• Elements of Information Theory
• A Mathematical Theory of Communication
• Concentration inequalities. A nonasymptotic theory of independence
• The concentration of measure phenomenon
• A simple proof of the blowing-up lemma (Corresp.)
• Approximation theory of output statistics
• Title not available (Why is that?)
• Hypercontractivity of Hamilton-Jacobi equations.
• Asymptotic evaluation of certain Markov process expectations for large time—III
• Title not available (Why is that?)
• A user's guide to measure theoretic probability
• Asymptotic Estimates in Information Theory with Non-Vanishing Error Probabilities
• On source coding with side information at the decoder
• Information Spectrum Approach to Second-Order Coding Rate in Channel Coding
• Channel Coding Rate in the Finite Blocklength Regime
• Title not available (Why is that?)
• Information theory. Coding theorems for discrete memoryless systems
• Mutual Information and Minimum Mean-Square Error in Gaussian Channels
• Lower bounds to error probability for coding on discrete memoryless channels. I
• A general formula for channel capacity
• Positivity improving operators and hypercontractivity
• Non-interactive correlation distillation, inhomogeneous Markov chains, and the reverse Bonami-Beckner inequality
• A proof of Marton's coding theorem for the discrete memoryless broadcast channel (Corresp.)
• Title not available (Why is that?)
• Large-Sample Theory: Parametric Case
• On reverse hypercontractivity
• Concentration of measure inequalities in information theory, communications, and coding
• Approximate tensorization of entropy at high temperature
• Title not available (Why is that?)
• Title not available (Why is that?)
• Nonasymptotic and Second-Order Achievability Bounds for Coding With Side-Information
• Network information theory
• Certain results in coding theory for noisy channels
• Correction to bounds on conditional probabilities with applications
• The empirical distribution of good codes
• A Proof of the Strong Converse Theorem for Gaussian Broadcast Channels via the Gaussian Poincaré Inequality
• Hypothesis testing with communication constraints
• Smoothing Brascamp-Lieb Inequalities and Strong Converses of Coding Theorems
• Logarithmic Sobolev inequalities in discrete product spaces
• Fixed-Length Lossy Compression in the Finite Blocklength Regime
• Optimal Lossless Data Compression: Non-Asymptotics and Asymptotics
• Empirical Distribution of Good Channel Codes With Nonvanishing Error Probability
• Notes on a general strong converse
• Strong converse of the coding theorem for semicontinuous channels

Cited In (3)

• New mathematical techniques in information theory. Abstracts from the workshop held March 13--19, 2022
• Minoration via mixed volumes and Cover's problem for general channels
• On reverse hypercontractivity

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)