CS Paper Radar

A local-to-global principle for $f$-divergence homogenization

Aryeh Kontorovich

cs.IT math.PR ·submitted 2026-10-22 12:22 UTC · v1

Abstract

We study the effect of replacing a family of independent statistical experiments by independent repetitions of their average. We give a simple, complete characterization of the $f$-divergences for which this operation increases divergence by at most a constant depending only on the generator, uniformly in the number of observations and the underlying measurable space. The characterization is governed by a local-to-global principle: a comparison restricted to two observations on a binary alphabet already determines the validity of the general inequality. It admits an explicit scalar formulation, which simplifies further for symmetric divergences. The result applies to arbitrary convex generators and requires no differentiability or symmetry assumptions. It recovers the homogenization inequality for total variation and identifies exactly the admissible members of the power-divergence family. In particular, whenever uniform homogenization fails, the obstruction is already present in a family of binary experiments with two observations. Moreover, the global comparison constant is controlled uniformly over generators with a common bound in the local inequality.

Closest papers

Nearest neighbours by meaning across the whole index.

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

Generalization Bounds via Vector-Valued $L_p$ Correlation $V_α$

cs.LG cs.IT ·2026-10-21 ·Mohammad Hossein Momeni Hamaneh, Mohammad Mahdi Mojahedian, Mohammad Hossein Yassaee
similarity 0.60
Abstract

Understanding generalization of randomized learning algorithms remains a central challenge. Mutual-information and total-variation bounds provide complementary ways to quantify data--hypothesis dependence, but they can behave quite differently in high-dimensional regimes. We study a one-parameter family of dependence measures, the vector-valued $L_p$-norm correlation $V_α$, and derive generalization bounds whose dependence terms interpolate between total variation (TV) at $α=1$ and variance and $χ^2$ related behavior at $α=2$. For $α>2$, the Hölder-conjugate loss moment is below two, yielding heavy-tailed specializations that can remain finite even when the loss variance is infinite. A particularly interpretable specialization occurs at $α=2$, where the bound can be expressed in terms of the variability of the algorithm's output density across datasets, $\int \sqrt{\mathrm{Var}_S[p(w\mid S)]}~ dw$. We show that the entire $V_α$ family is invariant under smooth bijective reparameterizations of the hypothesis space. We also introduce an adaptive density stability (ADS) condition that implies explicit control of $V_2$, and we verify it for Gibbs-type posteriors under bounded losses (yielding rates that depend on the inverse temperature and sample size). To address scaling, we extend the framework to a conditional formulation using supersamples, analogous in spirit to conditional mutual information (CMI), and discuss evaluations in the output space as a practical surrogate for estimating dependence. Simulations on Bayesian linear regression illustrate how tuning $α$ can change the tightness of the resulting bounds across regimes. Additional supersample experiments on noisy MNIST and on a pretrained ResNet-50 for CIFAR-10 show similar behavior of the projected loss-space bounds beyond the original clean-MNIST setting.

0.32

On the Subadditivity of Mutual f-Information

cs.IT ·2026-10-15 ·Hamidreza Abin, Amin Gohari
similarity 0.58
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

An information identity reveals the geometry of deviation events

cs.IT ·2026-09-29 ·Akshay Balsubramani
similarity 0.58
Abstract

In a deviation event, the empirical measure of $n$ independent draws lands in a set of distributions. The exponent of its probability splits, at every $n$, into two nonnegative terms. The first is the rate: $n$ times the relative entropy, from the population, of the distribution of a typical draw under the event. The second is the dependence that conditioning induces among the draws, measured by their total correlation. Their relative sizes depend on the geometry of the set. This paper focuses on this exact split and on the geometry that the interplay of its two terms reveals. The dependence vanishes exactly when the event confines every draw to a single set, and the classical rate of that constraint is exact. On a set invariant under a compact group that fixes the population and leaves no invariant set of intermediate probability, the rate vanishes; uniform convergence over a hypothesis class that such a group permutes is one. On a half-space whose threshold sits a fixed number of standard errors above the mean, the fraction of the exponent that is dependence tends to a function of the event's probability alone. On a set split into pieces, the dependence is the pieces' average plus $n$ times the Jensen-Shannon divergence of their marginals, minus the entropy of their weights. The split extends to a general reference law. When the information projection is such a law, the split gives the exact value of the expectation in the exponential change of measure to the projection.

0.22

A Complete Characterization of Tensorizable $f$-divergences

cs.IT math.PRmath.ST ·2026-08-28 ·Rodrigo Cruz, Flavio P. Calmon, Qian Yu
similarity 0.57
Abstract

Csiszar's formulation of the $f$-divergence introduced a vast family of functionals for quantifying dissimilarity between probability distributions. However, many applications in statistics and information theory rely only on a few $f$-divergences, such as the Kullback-Leibler divergence, the $χ^2$-divergence, and the squared Hellinger distance. These divergences are especially useful because they admit simple compositional formulas under product measures, a property sometimes referred to as tensorization. In this work, we refine a formalism of tensorization previously introduced in the literature. Then, we show that any possible tensorization formula has a multi-affine form characterized by a single parameter, and identify all tensorizable $f$-divergences under our adopted notion of tensorization.

0.45

Classical and Quantum Information Measures Characterizing Convertibility: An Axiomatic Approach

cs.IT quant-phmath-phmath.PR ·2026-10-12 ·Frits Verhagen
similarity 0.56
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

A Structural Characterization of Entropy Functionals

cs.IT math.ST ·2026-08-14 ·Daniel Lazarev
similarity 0.56
Abstract · 31 pages, 1 figure

Entropy functionals and their associated divergences underlie many statistical methods, including maximum entropy inference, minimum divergence estimation, and goodness-of-fit testing, yet choosing among Shannon, Rényi, Tsallis, and more general entropies is often a matter of convention rather than structural principle. We introduce a measure theoretic framework in which admissibility requires the entropy of an input measure to be bounded above by that of its reference measure whenever the former is absolutely continuous with respect to the latter. Under generalized mean-value composition, we characterize all such entropy functionals and obtain a four-level hierarchy determined successively by the mean generator, entropy scale, and additivity assumptions. A continuous strictly monotone generator $g$ is admissible exactly when $t\mapsto g(1/t)$ is strictly convex for increasing $g$, or strictly concave for decreasing $g$. This resolves a question posed by Rényi (Proc. 4th Berkeley Sympos. Math. Statist. Prob., 1961) concerning which generalized means may replace the arithmetic mean in his entropy axiomatization. The same criterion is equivalent to strict convexity of an associated Csiszár $f$-divergence generator and therefore yields data processing under Markov kernels with an exact equality condition. Within this hierarchy, product additivity singles out the Rényi family, while internal additivity, or product additivity together with arithmetic mean-value composition, singles out Shannon entropy. The characterization is constructive and yields new admissible entropy and divergence families, including integral-transform examples.

0.10

Second-Order Expansion of Privacy Amplification Under f-Divergence Criteria

cs.IT ·2026-09-10 ·Mario Berta, Hao-Chung Cheng, Marco Tomamichel
similarity 0.55
Abstract

We derive the second-order asymptotics of randomness extraction from memoryless sources with side information under security criteria based on a broad class of Csiszàr f-divergences, treating both a fixed reference side-information marginal and optimization over that marginal. The conditional varentropy decomposes into fluctuations of the conditional entropy across different values of the side information and the average variance of the conditional surprisal for each value. Without marginal optimization, these contributions yield a Gaussian-mixture second-order profile. With marginal optimization, they combine into the total conditional varentropy, yielding a single Gaussian profile. As corollaries, we obtain second-order expansions for Rényi-entropy criteria of all orders $α\in (0,1)$ and recover the known expansion for total variation distance.

0.30