CS Paper Radar

A Poisson Transition and Bias Law for KSG Mutual-Information Estimation

Abhiram Gorle, Tsachy Weissman

cs.IT ·submitted 2026-10-27 20:28 UTC · v1
theory

Abstract

We quantify the error of the strict-radius Kraskov--Stögbauer--Grassberger (KSG-1) mutual-information estimator on a Gaussian channel as the sample size \(n\) grows and the channel becomes nearly deterministic. For fixed dimension \(p\) and neighbor index \(k\), we define the resolution parameter \(u_n=ne^{-I_n}\), where \(I_n\) is the true mutual information in nats. When \(u_n\to u\in(0,\infty)\), we prove that the estimation error converges in mean square to a computable deterministic bias \(B_{p,k}(u)\). Sampling fluctuations therefore vanish, while an additive bias can persist. We derive this bias from an explicit marked-Poisson law for the neighborhood counts, characterize its small-\(u\) asymptotics, and show that it tends to zero as \(u\to\infty\). The same law describes how often neighborhoods saturate, meaning that they make the largest possible contribution to the estimate. The limiting saturation probability decreases continuously and strictly from one to zero, allowing a Gaussian-model bias correction on fixed critical intervals. Finite-sample experiments show substantial bias even when the true information lies below the estimator's logarithmic ceiling and saturated neighborhoods are rare. Saturation-based correction reduces estimation error in these experiments, though recovering the resolution parameter from the observed saturation fraction can remain difficult when saturation is rare.

Closest papers

Nearest neighbours by meaning across the whole index.

Exact Sampling Under Campbell Cost via Rényi Channel Simulation Divergence

cs.IT ·2026-10-11 ·Yijun Fan, Aaron B. Wagner
similarity 0.62
Abstract

We study the communication cost of exact sampling under Campbell's exponential coding criterion. Given a target distribution $P$ and a proposal distribution $Q$, the sender and receiver share i.i.d. $Q$-distributed samples, and the sender communicates an index so that the selected sample has distribution exactly $P$. We introduce a new information measure Rényi channel simulation divergence $R_α(P\Vert Q)$, a Rényi generalization of the channel simulation divergence. We then show that it lower bounds the Campbell cost of every exact sampler and is achievable, via a new layered sampling scheme, within an additive constant depending only on the Campbell parameter. This yields a tighter one-shot characterization than previous bounds based on Rényi divergences of different orders. For i.i.d. product distributions, under suitable non-degeneracy and moment conditions, we further show that the gap beyond the leading Rényi-divergence term is $\frac{1}{2}\log n+O(1)$.

0.20

A Sharp Mutual Information Bound for Binary Pairs

cs.IT ·2026-11-02 ·Qianmian Guo
theory similarity 0.60
Abstract

We prove a sharp upper bound on the mutual information between two binary random variables in terms of their distribution-dependent KL contraction coefficient. This resolves the binary-pair conjecture of Anantharam, Gohari, Kamath, and Nair. Equality holds if and only if the variables are independent or form a doubly symmetric binary source. The proof uses supporting tangents of an entropy curve to vary the input distribution and the channel while preserving the contraction coefficient. Together with tensorization and data processing, the result also bounds the mutual information between binary outputs obtained separately from two correlated observation sequences. When the observation pairs are independent copies of a finite-alphabet pair, this bound depends only on the law of one pair and not on the number of observations.

0.24

Information, Estimation, and Prediction for Discrete Memoryless Channels via Poissonization

cs.IT ·2026-10-20 ·Abhiram Gorle, Tsachy Weissman
similarity 0.59
Abstract

We develop information--estimation relations for an arbitrary discrete memoryless channel with finite input and output alphabets by varying the expected number of observations while keeping the channel fixed. A single hidden input is observed through a \textit{Poisson} number of conditionally independent channel uses, whose mean specifies the observation budget. The derivative of mutual information with respect to this budget equals the minimum expected relative-entropy loss for estimating the input's output distribution. The posterior average of the channel's output distributions achieves this minimum and is the Bayesian predictor for the next observation. When the input distribution, the channel, or both are misspecified, the relative entropy between the true and assumed observation laws is the integral of the excess prediction loss over the budget. We also extend these relations to finite-state processes taking values in the input alphabet and observed through the channel at independent Poisson sampling times. Both in the matched setting and under model mismatch, the expected prediction loss accumulated over time using past observations equals the corresponding loss using the full observation record (noncausal estimation), averaged over lower sampling rates. We also characterize how redundancy between two outputs selects among input distributions that achieve one-use capacity. For the coupon-collector channel, where each observation is sampled uniformly from an unknown subset, we derive the exact capacity loss of any input distribution. In particular, balanced subset families can substantially reduce the input alphabet while preserving the leading capacity terms.

0.22

Fisher Information and Support Complexity of Gaussian Mixtures

cs.IT ·2026-10-15 ·Luca Barletta, Alex Dytso
theory similarity 0.59
Abstract · 24 pages, single-column

We study lower bounds on the Fisher information of Gaussian location mixtures and their applications to estimation problems. First, for a discrete mixing distribution, we derive a universal positive-semidefinite lower bound on the Fisher information matrix in terms of the Rényi entropy of order two. For a mixing distribution supported on $K$ points, this bound scales as $\log(K)/K^2$, improving by a logarithmic factor on the support-size dependence obtained from Stam's inequality. We then develop dimension-aware trace bounds using classical Sobolev inequalities. These bounds are expressed in terms of Sibson's $α$-mutual information and yield the scaling $K^{-2/n}$ in dimension $n$. A complementary bound involving the $α$-mutual information of order $1/2$ is obtained using the sharp Young convolution inequality. The derived inequalities are further specialized to rotationally invariant mixing distributions supported on discrete spherical shells. In this setting, an intrinsic-dimensional bound on Sibson mutual information leads to lower bounds on the Fisher information in terms of the number of occupied shells. As applications, we study least favorable priors for bounded Gaussian mean estimation. In the scalar case, we show that the least favorable prior on $[-R,R]$ has at least $Ω(R\sqrt{\log R})$ support points and that each of its probability masses is of order at most $1/R$. In the vector case, we show that the number of occupied shells grows at least linearly with $R$. Finally, Brown's identity and the I-MMSE relationship are used to translate the Fisher-information inequalities into upper bounds on the MMSE and mutual information.

0.28

Mutual Information Constrained Chernoff Bottleneck

cs.IT cs.LGmath.OCmath.ST+1 ·2026-09-29 ·Dier Tang, Guangyue Han
similarity 0.59
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.40

Finite-Sample Binary Hypothesis Testing via Rényi Divergences: Strong Converse and Local Privacy

cs.IT math.ST ·2026-09-23 ·Roberto Bruno, Adrien Vandenbroucque, Amedeo Roberto Esposito
published similarity 0.59
Abstract · Extended version of a paper presented at the 2026 IEEE International Symposium on Information Theory (ISIT). Submitted to the IEEE Transacti…

We study asymmetric simple binary hypothesis testing between $H_0:P_0^{n}$ and $H_1:P_1^{n}$, based on $n$ independent and identically distributed observations. Leveraging a variational representation of Rényi divergence of order $α$, we derive our main result: a finite-sample converse with $α>1$. The bound uses both directions of the divergence $D_α(P_1\|P_0)$ and $D_α(P_0\|P_1)$, tensorises under product measures, and contains familiar data-processing converses as boundary cases. For comparison, we apply the same variational approach to general $f$-divergences and specialise it to total variation, $E_γ$, Hellinger, and Kullback Leibler divergences, thereby recovering familiar converses within a unified framework. Together with an achievability bound involving Rényi divergence with $α\in (0,1)$, the main converse recovers the phase transition of the optimal Type II error under the exponentially decaying Type I error constraint $\varepsilon_n=e^{-nr}$. Under regularity conditions, the optimal Type II error vanishes exponentially when $r<D(P_1\|P_0)$ and converges exponentially fast to one when $r>D(P_1\|P_0)$. We also derive sample-complexity bounds and extend both the converse and achievability analyses to locally differentially private observations, quantifying the cost of privacy and recovering the non-private achievability bound as the privacy constraint vanishes.

0.34

Conditional Fisher-Information Central Limit Theorems under Log-Concavity with Information-Theoretic Consequences

cs.IT math.PR ·2026-09-07 ·Tong Ye, Liu-Quan Yao
benchmarktheory similarity 0.58
Abstract · 47 pages

We establish conditional central limit theorems in Fisher information under log-concavity in every fixed dimension. For conditionally centered normalized sums, after whitening by the averaged conditional covariance, the averaged conditional Fisher information converges to the dimension if and only if it is finite at one convolution level. The scalar criterion follows as the one-dimensional case; we also provide an independent scalar proof based on a second-order continuity theorem for Fisher production on Gaussian-smoothed, tail-controlled classes. For the original sums, the averaged Fisher information matrix converges in operator norm to the inverse averaged conditional covariance. Consequently, the conditional relative Fisher information with respect to the limiting Gaussian law vanishes, and the Gaussian logarithmic Sobolev inequality yields convergence in conditional relative entropy and conditional entropy. We give two operational consequences. For any fixed finite-constellation low-power input, the first-order conditional mutual-information slope converges to the Gaussian-noise benchmark. For Gaussian signaling at any fixed signal covariance, the mutual-information gap from that benchmark is bounded by the conditional relative Fisher deficit and hence vanishes asymptotically.

0.38

The Sample Complexity of Channel Coding

cs.IT math.ST ·2026-11-16 ·Terence Viaud, Ioannis Kontoyiannis
similarity 0.58
Abstract · 31 pages, 3 figures

We introduce a new framework for the study and evaluation of the fundamental limits of channel coding, emphasizing genuinely nonasymptotic results. The {\em channel coding sample complexity} $n^*({\cal W},ε)$ of a channel ${\cal W}$ is defined as the smallest blocklength at which it is possible to transmit information through that channel with error probability below $ε$ and at a rate at least as high as that given by an appropriate constraint also in terms of $ε$. This formulation follows analogous developments in statistics, computer science and, more recently, in lossless source coding. For any discrete memoryless channel we derive nonasymptotic bounds on the sample complexity, with explicit constants. These bounds show that the sample complexity is characterized not by the usual channel capacity, but by the channel's Augustin--Csiszár capacity of order $1/2$, which coincides with the cutoff rate as well as with the channel's Sibson capacity of order $1/2$. The proof is partly based on a new channel-coding one-shot converse in terms of hypothesis testing. We also examine extensions of the sample complexity framework to general target rates. Moreover, we derive corresponding results for the sample complexity of the additive white Gaussian noise channel with a quadratic power constraint. Their proof relies on new, explicit upper bounds on the best achievable error probability, which may be of independent interest.

0.17