CS Paper Radar

Breakdown of Edgeworth Expansion in Finite-Blocklength Regime and Exact Absorption via $q$-Deformation

Hiroki Suyari

cs.IT cond-mat.stat-mechmath.PR ·submitted 2026-08-24 14:27 UTC · v2
publishedtheory

Abstract

This paper addresses the structural breakdown of the Edgeworth expansion in the finite-blocklength (FBL) regime, where conventional asymptotic approximations yield unphysical negative probabilities in the deep-tail region. We propose a $q$-deformed framework that resolves this inconsistency by replacing additive polynomial perturbations with a geometric deformation of the information density space. Motivated by the linearization of nonlinear dynamics, we prove that dynamically scaling the $q$-logarithmic parameter exactly absorbs the third-order skewness while preserving global nonnegativity. We establish a universal asymptotic matching, demonstrating that the framework encapsulates higher-order asymptotic scales. Numerical results confirm that the proposed method matches the state-of-the-art precision of the Cornish-Fisher bound without the risk of negative probabilities. The framework offers a robust and computationally stable foundation for evaluating operational limits in ultra-reliable communications such as 6G and URLLC.

Comment
7 pages, 4 figures. Extended version of the paper accepted for ISITA 2026 (the concise version will appear in IEEE Xplore). Updated figures and added discussions

Closest papers

Nearest neighbours by meaning across the whole index.

Chi-Squared Geometry for Robust Finite-Blocklength Information and Dispersion Analysis

cs.IT ·2026-08-18 ·Hassan Tavakoli, Thinh Nguyen, Bella Bose
theory similarity 0.62
Abstract · Accepted for publication at Information Theory Workshop 2026, ITW 2026

We develop a column-wise chi-squared geometry for discrete memoryless channels (DMCs) yielding tight, logarithm-free bounds on mutual information, channel dispersion, and finite-blocklength coding rates without evaluating logarithms of the channel matrix. The key parameter is~\(η\)---the worst-case relative deviation of a transition probability from its output marginal, which is small precisely when the channel is close to the fully noisy channel $t_{ij}=s_j$. We prove three main results: (1) a third-order ratio expansion showing \(I(X;Y)/χ^2(X;Y)\to 1/2\) as \(η\to 0\) with an \(O(η)\) skewness correction; (2) a two-sided dispersion equivalence bounding \(V(X;Y)\) above and below by \(χ^2(X;Y)\) with explicit constants \(c_{\pm}(η)\to 1\); and (3) a certified robust design rate \(R_{\mathrm{cert}}(n,\varepsilon)\) with total certification gap \(O(η)+O(η/\sqrt{n})+O(\log n/n)\). The certified bounds on \(I\) and \(V\) require only addition, multiplication, division, and square roots; the final rate also uses \(Q^{-1}(\varepsilon)\).

0.52

Third-Order Asymptotics for Fixed-Length Lossy Compression of Discrete Memoryless Sources

cs.IT ·2026-11-10 ·Vincent Y. F. Tan
hot direction similarity 0.58
Abstract · 16 pages, 2 figures

This paper determines the third-order asymptotics of the logarithm of the minimum codebook size for fixed-length lossy compression of discrete memoryless sources. For an excess-distortion probability constraint $\varepsilon\in(0,1)$ and every interior distortion level, we establish a third-order correction of $\frac12\log n+O(1)$, where $n$ is the blocklength. This sharpens the general bounds of Kostina and Verdú [IEEE Trans. Inf. Theory, 2012]. The main technical innovation lies in the converse for positive dispersion. Under a reverse change of measure, we retain the exponential weights associated with tilted information and distortion slack and control them jointly using the multivariate weighted-strip estimate of Scarlett, Martinez, and Guillén i Fàbregas [Proc. IEEE ISIT, 2015]. A pairing argument verifies the required covariance nondegeneracy uniformly over all reconstruction words whose distortion balls meet a typical set, yielding the matching converse.

0.31

Geometric mean quantization via adaptive approximation

cs.IT math.PRmath.OC ·2026-09-22 ·Marc Kesseböhmer, Aljoscha Niemann
similarity 0.57
Abstract · 36 pages

Let $ν$ be a compactly supported Borel probability measure on $\mathbb R^{d}$ with $ν(B(x,r))\leq Cr^{a}$ for some $a>0$. Refine a dyadic cube exactly when its mass is at least $t$, and let $\mathcal{L}_ν(t)$ be the mean depth at which this refinement stops. We show that the lower and upper geometric-mean quantization dimensions of $ν$ are the lower and upper limits of $\log(1/t)/\mathcal{L}_ν(t)$. The dimension exists precisely when $(q-1)\sum_{Q}ν(Q)^{q}$, summed over all dyadic cubes, converges as $q\downarrow1$, and it is then determined by this limit. The mass-threshold formula yields harmonic integral bounds in terms of the local dimensions and encloses entropy and quantization dimensions in a common spectral interval. Convergence in law of the local information rates is equivalent to convergence of the rescaled spectra in a window of width $1/k$ around $q=1$; the two dimensions are then the arithmetic and the harmonic mean of the limit law, and we quantify their difference by sharp bounds and variance identities. Without any convergence assumption, vanishing threshold variance still forces equality of the corresponding lower and upper dimensions. Bernoulli mixtures realise every local-dimension law with compact support in $(0,1]$, and a regime-switching example separates convergence in law from almost-everywhere convergence.

0.21

Lower Bounds for Adaptive Relaxed Locally Decodable Codes via the Capped Horvitz--Thompson Estimator

cs.CC cs.IT ·2026-11-03 ·Guy Goldberg, Tom Gur, Sidhant Saraogi
theory similarity 0.53
Abstract

We prove a nearly optimal lower bound on the blocklength of general relaxed locally decodable codes (RLDCs), extending the result of [GGS26] to nonlinear encodings and adaptive decoders with two-sided error. Namely, we show that any $q$-query RLDC $C\colon \{0,1\}^k \to \{0,1\}^n$ must satisfy $n = k^{1+Ω(1/q)}$, closely matching the upper bound of $n = k^{1+O(1/q)}$ by Ben-Sasson, Goldreich, Harsha, Sudan, and Vadhan (STOC 2004). Our proof reduces showing RLDC lower bounds to estimating the output distribution of adaptive decoders. To this end, we introduce a capped Horvitz--Thompson estimator with uniformly bounded discrete derivatives on the $p$-biased cube. We establish its concentration of measure via self-bounding inequalities and control the downward bias induced by capping through a spreadness argument.

0.22

Small-Space Streaming Hamming Approximation

cs.DS ·2026-11-18 ·Przemyslaw Uznanski
similarity 0.52
Abstract

For a preprocessed pattern of length $m$ and a streaming text, we give two algorithms that estimate the Hamming distance at every alignment to relative error $\varepsilon$. They use $\varepsilon^{-8/5}m^{2/5+o(1)}$ and $\varepsilon^{-1} m^{1/2+o(1)}$ words of space, respectively, including all retained pattern information. Each estimate is reported as soon as its window ends, and all estimates are simultaneously correct with high probability. The prior space bounds are $\widetilde{O}(\varepsilon^{-3/2}\sqrt{m})$, due to Chan et al. [CGK+20], and $\widetilde{O}((m/\varepsilon)^{2/3})$, a consequence of their results and those of Clifford, Kociumaka, and Porat [CKP18]. For $\varepsilon=Θ(m^{-a})$, the better of our two bounds improves on both prior space exponents for every fixed $0<a<1/2$. A Fourier matcher uses $\widetilde{O}(\varepsilon^{-2}(m/K)^2)$ words to estimate each distance $d$ within $\varepsilon(d+K)$, giving relative error at most $2\varepsilon$ for $d\ge K$. A threshold matcher based on random-prime residue refinements and the multi-stream dictionary matching algorithm of Golan, Kopelowitz, and Porat [GKP18] gives our second space bound directly. Combining it with the Fourier matcher gives the first. Both space bounds extend to $L_1$ matching over polynomially bounded integer symbols.

0.23

Uniform Statistical Convergence of Empirical Sinkhorn Potentials with Exponential and Polynomial Dependence on the Regularization Parameter

cs.LG stat.MLmath.OC ·2026-08-29 ·Denis Belomestny
theory similarity 0.52
Abstract

We study the empirical Sinkhorn estimator of the entropic optimal transport potentials under the uniform loss. Since the potentials are only unique up to additive constants, we measure the error using the quotient supremum norm, defined as $d_\infty([u],[v]) = \inf_{a\in\mathbb{R}}\|u-v-a\|_\infty$. For a fixed regularization parameter $\varepsilon>0$, we establish a non-asymptotic statistical rate of $n^{-1/2}$. This is achieved by combining the Birkhoff-Hopf contraction theorem with entropy bounds on normalized kernel sections. However, the constant in this bound grows exponentially with $1/ε$. To improve this, we isolate geometric conditions under which the empirical estimator maintains the $n^{-1/2}$ rate but features polynomial dependence on $1/\varepsilon$. The key requirement is a polynomial residual-stability estimate for the population Sinkhorn map. We provide sufficient criteria for this, including a polynomial contraction property and a local inverse estimate. Furthermore, we introduce two rigorously verifiable model classes an $\varepsilon$-weak residual-interaction class obtained after separable centering and another based on connected tight-edge graphs for fixed discrete costs where the polynomial rate is guaranteed without relying on abstract resolvent assumptions. Finally, we establish matching minimax lower bounds demonstrating that the $\varepsilon n^{-1/2}$ rate cannot be uniformly improved in the bounded-interaction regime.

0.34

A Tight Second-Order Converse Bound for Variable-Length Feedback Codes

cs.IT ·2026-09-10 ·Recep Can Yavas
similarity 0.52
Abstract · 26 pages, submitted to Information Theory Transactions

We study variable-length feedback (VLF) codes over a discrete memoryless channel under average decoding-time and error-probability constraints. In the non-vanishing error probability regime, Polyanskiy, Poor, and Verdú (2011) derive achievability and converse bounds on the logarithm of the maximum achievable codebook size. These bounds establish the $ε$-capacity but leave an order-$\log N$ gap in the second-order expansion, where $N$ is the average decoding time. Yavas and Tan (2025) improve the coefficient of $\log N$ in the achievability bound from $-1$ to $-\frac{C}{C_1}$, where $C$ is the channel capacity and $C_1$ is the largest Kullback--Leibler divergence between two conditional output distributions. We derive a converse with the same coefficient, establishing the second-order fundamental limit for every positive-capacity discrete memoryless channel with finite $C_1$. The result also covers the moderate-deviations and error-exponent regimes, including polynomially decaying error probabilities. The converse uses Rényi entropy and the extrinsic Jensen--Shannon divergence. We also derive necessary properties of asymptotically optimal VLF codes. First-order-optimal codes must have an early-stopping branch, and second-order-optimal codes must additionally exhibit communication and confirmation behavior. Finally, for the binary erasure channel, we determine the exact minimum expected decoding time for every message-set size and admissible error probability.

0.11

Sharp Minimax Limits and Compatibility Spectra for Critical Near-DFT Index-Only Frequency Estimation

eess.SP ·2026-09-01 ·Armon Rasooli, Mohammad Sadegh Narimani
similarity 0.51
Abstract

An $M$-channel discrete Fourier transform (DFT) channelizer routes an on-grid sinusoid to a single output. When each frame reports only one energy-proportional channel index, signed sub-bin frequency estimation becomes nonregular: dark-channel probability is quadratic in the offset, whereas orientation enters cubically. We study $N$ independent labeled reports under a known uniform-replacement probability $ε_N$ and a single deterministic unitary shared by all frequencies and frames, constrained to routing defect $τ/N$. If $\sqrt{N}ε_N \to λ< \infty$, we establish an attained global-in-frequency minimax limit at the critical scales $N^{-1/4}$ for frequency offset, $N^{-1/2}$ for unitary perturbation and replacement, and $N^{-1}$ for routing defect. The effective unitary tangent is a symmetric complete-graph edge field modulo one centering nuisance, and its first variation is a radius-dependent weighted divergence. For $λ>0$, evaluation at $k$ distinct normalized offset magnitudes yields an exact Fourier-Cauchy nullity spectrum: $\lfloor(M-1)/2\rfloor$ evaluations are necessary and sufficient, for every choice of distinct magnitudes, to certify neutrality at all magnitudes. The terminal nullspace has a greatest-common-divisor dimension formula and positive-definite aggregate curvature. Consequently, exact DFT routing is uniquely minimax within the complete critical tangent class for $M=3$, whereas every positive critical defect budget strictly improves the minimax constant for $M\geq4$. The analysis also yields a smallest-prime curvature-visibility law and, for $M\geq5$, discontinuous compatibility geometry but a continuous minimax value at the zero critical replacement floor $λ=0$.

0.24