CS Paper Radar

Exact Second-Order Asymptotics for the Wyner--Ahlswede--Körner Problem

Daming Cao

cs.IT ·submitted 2026-08-22 14:49 UTC · v2

Abstract

We determine the exact local second-order rate region of the finite-alphabet Wyner--Ahlswede--Körner problem under full support, at informative boundary points exposed by a finite supporting slope. The characterization permits nonunique optimizing test channels with unequal information variances and requires no neighborhood smoothness of the optimized first-order value. The optimal success function is a conditional Gaussian envelope averaged over the fluctuation of the helper's observed source type. For each type, the helper selects the minimum or maximum conditional variance according to the remaining description budget, while preserving both first-order rates. The converse follows from a uniform Gaussian bound for ordinary channel images. An exact posterior score decomposition separates a common source score, a nonnegative optimality gap, a negligible source residual on low-cost histories, and a conditionally independent channel fluctuation. Conditional-type covering with two endpoint optimizers and one common binning map attains the bound. Under a strict first-order benefit from the helper, a separate limiting-rate argument also gives the unrestricted weighted second-order optimum. A strictly positive finite source exhibits a strict gain over every fixed-optimizer Gaussian expression, and an exact binary image calculation illustrates the limiting coefficient.

Comment
Draft manuscript

Closest papers

Nearest neighbours by meaning across the whole index.

Second-Order Asymptotics for the Gaussian Multiple-Access Channel at Corner Points

cs.IT ·2026-08-18 ·Vincent Y. F. Tan
theory similarity 0.60
Abstract · 28 pages, 4 figures

We establish exact second-order coding rate regions at the two corner points of the capacity region of the two-user Gaussian multiple-access channel. For any average error probability $\varepsilon\in(0,1)$, we characterize the $n^{-1/2}$-scale fluctuations of achievable rates around each corner point, proving a converse that matches the previously known achievability bound. The proof first extracts a rectangular subcode that preserves the independence of the two transmitted codewords. The Polyanskiy--Verdú good-code output distribution theorem then yields log-determinant constraints that induce a spectral decomposition of a trimmed codebook into diffuse and exceptional subspaces. An entropic Brascamp--Lieb projection inequality controls the codeword inner product on the diffuse subspace, while variance-inflated Gaussian output distributions handle the low-dimensional exceptional subspace. Combining these two treatments yields the joint Gaussian limit required for the matching second-order converse.

0.51

Exact Rate Exponent Tradeoff for New Classes of Distributed Hypothesis Testing Problems

cs.IT ·2026-08-24 ·Zhenduo Wen, Amin Gohari, Michèle Wigger
theory similarity 0.59
Abstract

We study the optimal Stein error exponent for one-way distributed hypothesis testing under a communication rate constraint. We establish exact rate-exponent tradeoffs for new classes of finite-alphabet sources, including a complete single-letter characterization for every pair of strictly positive binary joint distributions as well as testing-against-dependence. Our converse analysis refines the auxiliary-receiver method through three complementary steps. First, we establish an information-projection identity that identifies the posterior-divergence optimization in an existing converse with Han's exponent functional. Second, we obtain an additional excess-rate branch by retaining a mutual-information term discarded in the usual rate relaxation. Third, we develop a two-telescope upper bound whose auxiliary variables are coupled through a joint rate constraint. Combining these bounds with information-geometric matching conditions yields exact exponents for three classes of sources by matching the achievable bounds of Han and Shimokawa-Han-Amari.

0.36

Exact Second-Order Asymptotics for the Discrete Wyner--Ziv Problem

cs.IT ·2026-10-08 ·Lin Zhou
similarity 0.59
Abstract

We revisit the discrete Wyner--Ziv problem and establish exact second-order asymptotics. Our main contribution is a second-order converse bound, which is derived using posterior decomposition, concentration inequalities, and a conditional Gaussian approximation for martingales. Furthermore, we extend the previous best known achievability result of Li and Li (arXiv 2025) by allowing the test channel to depend on the type of the observed source sequence. Exact second-order asymptotics are established by combining our achievability and converse bounds. In particular, we show that the achievability bound of Li and Li (arXiv 2025) is not optimal in general. Specifically, we provide two numerical examples to illustrate our results: a binary asymmetric source and a quaternary source. For the first example, the achievability bound of Li and Li (arXiv 2025) achieves the optimal second-order asymptotics. However, in the second example, we show that our achievability result is optimal, which reduces the second-order coding rate of Li and Li (arXiv 2025) by $10.77\%$ at the excess-distortion probability of $0.1$ and by $21.35\%$ at the excess-distortion probability of $0.2$.

0.43

Second-Order Asymptotics for the Scalar Gaussian Broadcast Channel

cs.IT ·2026-11-01 ·Vincent Y. F. Tan
similarity 0.59
Abstract · 34 pages, 9 figures

This paper characterizes the second-order coding region of the scalar Gaussian broadcast channel along the curved boundary of its capacity region. The characterization holds under both average and maximal error criteria and allows correlation between the receiver noises. At each interior point of this boundary, the second-order region is a halfspace, as in the work of Scarlett and the author on Gaussian multiple-access channels with degraded message sets. Achievability follows from spherical superposition coding with a blocklength-dependent power allocation. The main innovation lies in the converse. Using Ornstein--Uhlenbeck entropy dissipation and Gaussian functional inequalities, we construct an auxiliary observation through an additive Gaussian noise channel and establish quantitative relative entropy bounds for the channel output distributions conditioned on this observation. The strong functional representation lemma of Li and El Gamal then allows us to select a realization of its independent random seed to obtain a deterministic partition of the retained receiver-1 message set. The component label plays a role analogous to the auxiliary random variable in the capacity characterization, while providing the distributional control needed at the second-order scale. These properties guide the construction of auxiliary output measures whose likelihood ratios admit the cancellations and normal approximation needed to evaluate an information spectrum converse.

0.38

Exact Common Information and Exact Channel Synthesis for Correlated Gaussian Sources

cs.IT ·2026-08-26 ·Lei Yu
similarity 0.58
Abstract · 16 pages, 2 figures

In this paper, we resolve two conjectures posed by Yu and Tan in 2020 (in two separate papers published in the IEEE Trans. Inf. Theory). Specifically, we establish that: 1) the exact common information for a pair of $ρ$-correlated Gaussian sources is given by the conjectured expression $\frac{1}{2}\log\frac{1+ρ}{1-ρ}+\fracρ{1+ρ}$; and 2) the admissible region for the shared randomness rate and the communication rate in exact channel synthesis is exactly the conjectured one. These results yield two important consequences. First, for any $ρ>0$, the exact common information of a correlated Gaussian pair strictly exceeds Wyner's common information. Second, for $ρ>0$, the exact channel synthesis of such a pair requires strictly higher rates than the total-variation version. The proof combines an exact optimal-transport representation of the worst-case Gaussian cross-entropy, Fathi's Gaussian transport inequality, and a determinant inequality arising from the covariance structure of the conditional means.

0.36

Mutual Information Constrained Chernoff Bottleneck

cs.IT cs.LGmath.OCmath.ST+1 ·2026-09-29 ·Dier Tang, Guangyue Han
similarity 0.58
Abstract · 35 pages, 4 figures, 3 tables. Feedback and comments are welcome!

The classical information bottleneck (IB) measures the relevance of a representation $U$ of $X$ to a target $Y$ by $I(U;Y)$, which does not directly characterize the error of downstream decisions. For a binary hypothesis $Y$ inferred from many separately encoded observations, the optimal error exponent is the Chernoff information between the two conditional distributions of $U$ given $Y$. We study the mutual information constrained Chernoff bottleneck, which seeks an encoder that maximizes this Chernoff information subject to a rate constraint $I(U;X) \leq R$. We show that its optimal value $C(R)$ increases strictly up to $R = H(V)$, where $V$ merges the symbols of $X$ with equal likelihood ratio, remains at the uncompressed exponent beyond, and, unlike the IB curve, need not be concave. We further show that $k+1$ outputs suffice to attain $C(R)$, where $k$ is the cardinality of $V$. We propose an alternating algorithm that updates the encoder via a generalized Blahut--Arimoto algorithm and the Chernoff parameter $s$ via a nonlinear equation, and prove that its iterates remain feasible, with nondecreasing and convergent Chernoff information. Comparing with the classical IB for $n$ samples, we show that, whenever the two objectives disagree, the IB encoder has the smaller equivocation $H(Y|U^{n})$ at $n = 1$, whereas the Chernoff bottleneck has the smaller error probability and equivocation for all large $n$. Numerical experiments confirm the theory, and on real topic-detection data from the 20 Newsgroups corpus, compressing each word to only $17\%$ of its entropy retains $90\%$ of the error exponent and nearly the accuracy of the uncompressed classifier.

0.39

Beyond Gaussian Assumptions: Distribution-Aware Channel Capacity for Effective Connectivity

cs.LG q-bio.NC ·2026-09-26 ·Jianan Jian, Jacob Kang, Nurahmed Multezem, Benjamin Li, Nan Xu
similarity 0.56
Abstract · 31 pages, 9 figures, 5 tables

Effective-connectivity estimation from brain signals often relies on Gaussian residual modeling, which enables tractable estimation but can discard informative distributional structure and distort inferred directed interactions when empirical residuals are non-Gaussian. We show across multiple modalities, species, and experimental conditions that both brain signals and fitted channel residuals frequently deviate from Gaussianity. We therefore introduce a distribution-aware, information-theoretic measure of effective connectivity based on channel capacity under general residual distributions. To estimate the resulting capacity from empirical, potentially non-Gaussian residuals, we develop a dual-flow min-max estimator based on normalizing flows, in which a generator searches over admissible input distributions under a power constraint while an observer estimates output entropy. We provide a theoretical characterization of the estimator, showing that the observer objective recovers differential entropy up to a KL approximation term, that the formulation reduces to classical Gaussian capacity as a special case, and that residual entropy can alter achievable information rates beyond variance; game-gap and error analyses further characterize optimization and approximation sources. In brain-like simulations with known directed connectivity, Dual-flow achieves the highest AUROC and AUPRC across ten conditions spanning diverse network topologies, hidden drivers, feedback, and heterogeneous hemodynamics, compared with Gaussian capacity, Granger causality, VAR-LiNGAM, and GIMME. Applied to multimodal brain signals, the method reveals time- and condition-resolved directed interactions consistent with known neurobiological circuitry. Together, these results establish a principled distribution-aware framework for effective-connectivity estimation beyond Gaussian residual modeling.

0.32

Second-Order Image Characterization with Distortion and Secrecy

cs.IT ·2026-10-07 ·Cao Daming
theory similarity 0.56
Abstract · Draft manuscript

Image characterization relates coding budgets to the probability carried by source cells and their output images. At second order, refining a cell can reveal unavailable information, while a change of reference measure can alter the relevant likelihood fluctuations. We establish image bounds that account for both effects. A finite-block partition theorem bounds the cost of merging component images by the joint conditional information spectrum of their label. It preserves continuous second-order profiles when that cost is negligible on the square-root blocklength scale. For reconstruction constraints, cell-dependent reference measures retain the actual distortion deficits in a single likelihood. A Gaussian evaluation gives matching second-order rates for Heegard--Berger coding with one uninformed decoder in the strict both-active regime, common reconstruction under a joint agreement and distortion criterion, and two-stage refinement with side information absent at the first decoder. A structured binary source illustrates partition stability even when its global density and conditional-divergence deficits are linear in blocklength. Posterior-mass images also sharpen extraction after a public refinement by charging its residual information rather than its alphabet size. These results preserve the joint constraints and the observations available for choosing the local coding experiment.

0.47