CS Paper Radar

The marginal is pretty good

Lukas Schmitt, Gui-Long Jiang, Shi-Bing Li, Joseph M. Renes

cs.IT quant-ph ·submitted 2026-09-04 14:55 UTC · v2
theory

Abstract

One-shot information theory measures often require an optimization over states, but the form of these optimizers can be complicated or depend on the initial problem in nonlinear ways. In this note, we show that in many instances using the marginal instead of the optimal state is sufficiently good and only changes the result by a small factor. We prove that for the Petz--Rényi and sandwiched--Rényi divergences of order $α\in(0,1)$, replacing the optimizing state on $B$ by the marginal $ρ_B$ results in a multiplicative overhead of at most $1/α$.

Comment
12 pages, Gui-Long Jiang and Shi-Bing Li added as authors, Theorem 3.1 now holds for $α\in(0,1)$ (instead of $[1/2,1)$), Theorem 4.1 and 4.2 show the same statement for the sandwiched Rényi divergence. This generalizes the previous result that only worked for $α=1/2$ and special classes of states

Closest papers

Nearest neighbours by meaning across the whole index.

Mutual Information Constrained Chernoff Bottleneck

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

Classical and Quantum Information Measures Characterizing Convertibility: An Axiomatic Approach

cs.IT quant-phmath-phmath.PR ·2026-10-12 ·Frits Verhagen
similarity 0.61
Abstract · PhD thesis at the Centre for Quantum Technologies, National University of Singapore; contains corrections of some minor errors appearing in …

In this PhD thesis, we take an axiomatic approach to studying multivariate divergences, which are measures of the information content of a tuple of classical or quantum states. These divergences are studied in the context of large-sample and catalytic convertibility of tuples of states. This type of convertibility is characterized by the ordering of an axiomatically defined family of divergences. In this thesis, we identify this family of divergences explicitly for two scenarios, one classical and one quantum. In the classical setting, we show that the relevant divergences are certain generalizations of the bivariate Rényi divergences. Unlike previous studies, we do not require the distributions to have the same support, yielding interesting new divergences. In the quantum setting, we consider pairs of classical-quantum states with pure component states, and find that majorization is characterized by all $α$-$z$ relative entropies for $α<1$. This demonstrates the first operational interpretation of these relative entropies.

0.15

On the Cardinality of Optimal Representations in the Binary-Source Information Bottleneck

cs.IT cs.LGmath.OC ·2026-10-05 ·Dier Tang, Jun Chen
similarity 0.61
Abstract · 9 pages. Feedback and comments are welcome!

The information bottleneck (IB) seeks a representation $U$ of a source $X$ that retains as much information as possible about a target $Y$, subject to a constraint on $I(U;X)$. A classical argument shows that it suffices to consider representations with at most $|\mathcal{X}|+1$ symbols, and this bound is known to be tight whenever $|\mathcal{X}| \geq 3$. We show that the binary case behaves differently: if $X$ is binary and $Y$ is finite, then for every joint distribution of $(X,Y)$ and every rate constraint, the IB optimum is attained by a binary $U$. Hence the bound $|\mathcal{U}| \leq |\mathcal{X}|+1$ sharpens to $|\mathcal{U}| \leq |\mathcal{X}|$ for binary sources. The proof combines a separating hyperplane argument with the observation that, for a binary source, the ratio of the second derivatives of the two entropy functions involved is concave.

0.16

On the Subadditivity of Mutual f-Information

cs.IT ·2026-10-15 ·Hamidreza Abin, Amin Gohari
similarity 0.59
Abstract

We address an open problem raised by Polyanskiy and Wu in their textbook concerning the subadditivity of mutual \(f\)-information. We study two notions of generalized mutual information: mutual \(f\)-information, defined by \(\widetilde{I}_f(X;Y)=D_f(p_{XY}\|p_Xp_Y)\), and variational \((G,f)\)-information, obtained by minimizing an average of transformed \(f\)-divergences. For the first notion, we derive a sufficient condition on \(g(x)=x^2f''(x)\) that guarantees subadditivity under conditionally independent observations. This condition yields explicit families beyond the previously known examples generated by \(x\log x\) and \((x-1)\log x\). Our proof relies on the concavity of a generalized variance functional. For the variational notion, we extend existing sufficient conditions beyond the transforms \(G(x)\in\{x,\log(1+x),-\log(1-x)\}\). Using a comparison inequality for \(G^{-1}(G(A)+G(B))\), we obtain differential criteria for concave and convex transforms. Explicit constructions illustrate the resulting classes of subadditive information measures.

0.31

Strong Converse Exponent of Quantum State Merging

cs.IT quant-ph ·2026-08-27 ·Mario Berta, Hao-Chung Cheng, Roberto Rubboli, Marco Tomamichel
highly cited similarity 0.59
Abstract

We determine the strong converse exponent for the entanglement cost of quantum state merging, showing that it is characterized by the optimized $α$-$z$ conditional Rényi entropies with $z=α/2\in[1/2,1]$. This contrasts with the sandwiched conditional Rényi entropies that typically govern strong converse exponents in quantum information theory. As a consequence, we derive the strong converse exponent of the partially smoothed conditional min-entropy in purified distance. This exponent is governed by club-sandwiched conditional entropies, whereas global smoothing leads to a sandwiched expression.

0.61

Contraction of Rényi Divergences for Discrete Channels

cs.IT math.PR ·2026-09-28 ·Adrien Vandenbroucque, Amedeo Roberto Esposito, Michael Gastpar
highly cited similarity 0.59
Abstract

We investigate Strong Data-Processing Inequality (SDPI) constants for Rényi Divergences on finite spaces. We study their dependence on the Rényi order $α$, proving that they are non-decreasing and that their scaling by $(α-1)$ is convex for $α\geq1$. We also identify several support restrictions on the probability measures involved in determining these constants. In particular, in the distribution-independent setting, measures supported on a common set of at most two points suffice to evaluate the Rényi-SDPI constant. For $α\in[0,1]$, we further prove equality with the $χ^2$-SDPI constant, while at order infinity we obtain a closed-form expression. In order to link contraction over product spaces to contraction along individual coordinates, we provide tensorisation bounds for arbitrary product channels analogous to those known for $\varphi$-Divergences. At finite orders, the Rényi-SDPI constants are bounded above and below through comparisons with the $χ^2$-Divergence and Hellinger Divergences, with sharpness established in multiple cases. At order infinity, we instead relate these constants to the contraction of Total Variation Distance. Finally, our findings are applied to local differential privacy (LDP) and the analysis of Markov chains. This yields sharp contraction guarantees for pure-LDP mechanisms, and connects Rényi-LDP to Rényi-SDPI constants. For Markov chains, we derive finite-time convergence bounds and exhibit a family of chains for which Rényi-SDPIs improve on classical $χ^2$-based bounds by arbitrarily large factors.

0.34

What Should an Information Bottleneck Encoder Learn? Separating Representation Learning from Rate Control

cs.LG cs.IT ·2026-10-26 ·Hassan Tavakoli, Bella Bose
similarity 0.58
Abstract

The information bottleneck (IB) trades compression of an input $X$ against prediction of a target $Y$ through a multiplier $β=1/λ$, yet each operating point is usually served by training, or fully conditioning, a new encoder. For jointly Gaussian data, we show that the IB solution factorizes as $A(β)=D(β)W$: the information-bearing directions $W$ do not depend on $β$, and $β$ acts only through scalar gains. We ask whether this separation of \emph{representation} from \emph{rate control} survives beyond Gaussian models, treating the budget as a given operating parameter rather than a quantity to be optimized. For a budget-free representation \(F(X)\), the \emph{separation gap} is controlled by the \emph{sufficiency deficit} $ε_F=I(X;Y\mid F(X))$: We show there is at least $ε_F$ in the worst case for finite inputs, and it is bounded uniformly in $λ$ by a function of $ε_F$ for finite label alphabets. The same certificate extends to a new target distribution and to pooled multi-domain data, where a conditional-alignment term appears. On MNIST, SVHN, CIFAR-10 and STL-10 (10 seeds, eight prespecified budgets), a frozen CNN representation with one compressor--decoder pair per budget reduces estimated training multiply--accumulate operations (MACs) by $7.7\times$ and wall-clock time by about $2\times$ relative to end-to-end VIBs, and attains higher budget-averaged accuracy ($65.6\%$ versus $57.3\%$ per domain; $67.1\%$ versus $57.1\%$ pooled), with the advantage concentrated at strong compression, where the VIBs collapse. At weak compression ($λ\le0.036$), VIB has higher cross-entropy and ECE; its surrogate Lagrangian is higher per domain, indistinguishable from the pooled VIB in the macro average, and lower on the pooled test set.

0.10

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.58
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