Efficient approximate minimum-Rényi entropy couplings (Q6912508)

The manuscript sits squarely at the interface of information theory, discrete probability, and optimal transport, addressing approximation algorithms for the minimum-Rényi-entropy coupling of two discrete distributions under fixed marginals on the transport polytope \(C(p,q)\).\N\NThe authors prove that the classical greedy coupling achieves a uniform additive approximation to the optimal Rényi entropy across all \(\alpha>0\), \(\alpha\neq 1\), namely\N\[\N\frac{1}{1-\alpha}\,\log G\!\bigl(f_S,\alpha\bigr)\;\le\;\inf_{P\in C(p,q)} H_\alpha(P)\;\le\;\frac{1}{1-\alpha}\,\log G\!\bigl(f_S,\alpha\bigr)+g(\alpha),\N\]\Nwhere \(H_\alpha(P)=\dfrac{1}{1-\alpha}\log\!\sum_{i,j}P_{ij}^{\,\alpha}\) (logarithms base \(2\)), \(f_S(x)=\max\{f_p(x),f_q(x)\}\) with \(f_p(x)=\sum_{j\ge1}p_j\,\mathfrak{1}\{p_j\le x\}\), and \(G(f,\alpha)=f(1)-(\alpha-1)\!\int_0^1 x^{\alpha-2}f(x)\,dx\).\N\NConceptually, the paper extends to the full Rényi family the additive guarantees that were previously known for Shannon entropy, recovering in the limit \(\alpha\to 1\) the celebrated constant \(\log_2(e)/e\approx 0.53\) while showing that \(g(\alpha)\le 1\) for \(\alpha\ge 0.3644\) and that \(g(\alpha)\to 0\) as \(\alpha\to\infty\). Methodologically, it refines the ``profile-function'' approach that lower-bounds the optimum via \(G(f_S,\alpha)\) and upper-bounds it via an explicit greedy construction, dovetailing with recent work on minimum-entropy couplings, majorization barriers for concave costs, and the broader transport-polytope viewpoint in information theory.\N\NAdditive-gap certificates for \(H_\alpha\) couplings are directly useful whenever one seeks extremal dependence consistent with fixed marginals but cannot solve the exact (NP-hard) minimization: they yield computable surrogates for bounding mutual information through couplings, plug into entropic causal-inference pipelines as a robust extreme-dependence baseline, and support learning or privacy analyses that tune tail sensitivity by varying \(\alpha\) (from collision entropy at small \(\alpha\) toward Shannon as \(\alpha\to 1\)). In practice, the greedy scheme becomes especially attractive in regimes where \(g(\alpha)\) is small, providing a near-exact proxy while retaining simplicity and speed.\N\NThe analytic guarantees would be complemented by a more systematic empirical study on larger supports and diverse marginal shapes, clarifying typical (as opposed to worst-case) gaps and numerical stability near \(\alpha\approx 1\). It would also be valuable to examine the tightness of the bound by constructing near-matching hard instances across \(\alpha\), to compare the greedy coupling against alternative heuristics under identical constraints, and to sharpen the discussion around multi-marginal extensions (for which the Rényi case remains open): adapting the profile method or devising Rényi-specific lower bounds beyond majorization could significantly broaden impact. Finally, an explicit account of computational complexity and implementation details for evaluating \(G(f_S,\alpha)\) across \(\alpha\) would ease adoption in applied toolchains that rely on coupling-based information bounds.