Universal Shuffle Asymptotics, Part III: Dominant-Block Quotient Geometry and Hybrid Gaussian–Compound-Poisson Limits in Finite-Alphabet Shuffle Privacy
Alex Shvets · 2026
Read Universal Shuffle Asymptotics, Part III: Dominant-Block Quotient Geometry and Hybrid Gaussian–Compound-Poisson Limits in Finite-Alphabet Shuffle Privacy by Alex Shvets (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-13407.txt.
Introduction
Alex Shvets computes the exact leading term of Le Cam deficiency for shuffled histograms. Deficiency is the largest rise in Bayes risk caused by keeping only a retained statistic. Shvets works with growing shuffle models that have finite hypothesis families. For a bounded correlated message bundle, the coefficient comes out as a convex program with Gaussian-polynomial scores. Which moment degree first differs between the families fixes the order of the term. Kernels that preserve tags can be suboptimal, he also shows.
Catalog record
| CREATOR | Alex Shvets |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100765 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2603.13407
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Universal Shuffle Asymptotics, Part III: Dominant-Block Quotient Geometry and Hybrid Gaussian–Compound-Poisson Limits in Finite-Alphabet Shuffle Privacy Alex Shvets Abstract Part I of this series [ 1 ] establishes a sharp Gaussian (LAN/GDP, in the sense of [ 12 ] ) limit theory for neighboring shuffle experiments in the fixed full-support regime. Part II [ 2 ] identifies the first universality-breaking frontier: when the local randomizer becomes increasingly concentrated, the Gaussian limit fails and the neighboring shuffle experiment enters critical Poisson, Skellam, and multivariate compound-Poisson regimes. The present paper completes the finite-alphabet weak-limit theory by identifying the dominant-block quotient geometry that governs neighboring shuffle experiments. We treat dominant blocks of arbitrary finite size, allow overlap between the dominant output sets under the two neighboring hypotheses, and show that the limiting experiment decomposes according to this geometry: projecting onto the sum of the dominant tangent spaces yields a Gaussian factor, while quotienting by those same tangent spaces isolates a compound-Poisson jump field in the rare block, recovering the critical Poisson, Skellam, and multivariate compound-Poisson regimes of Part II in the projected quotient block. We also identify the regimes in which this quotient description determines the full privacy-curve , as well as the obstruction that appears when projected jump limits alone do not suffice. Two further sections sharpen the rate picture and the boundary interface. First, we show that the O ( n − 1 / 2 ) O(n^{-1/2}) rate for the full hybrid experiment is sharp in general, by an explicit binomial-plus-Bernoulli calculation, and we identify a compatibility condition under which the sharper O ( n − 1 ) O(n^{-1}) rate is restored. Second, we prove a boundary Berry–Esseen theorem showing that the critical Poisson-shift experiment is within O ( c ) O(c) in Le Cam distance of the Gaussian shift experiment as the critical scale parameter c ↓ 0 c\downarrow 0 , with a matching privacy-curve corollary. We also record a strong-boundary obstruction showing that, without an additional structural hypothesis, projected jump limits need not determine the full privacy-curve . Together with Parts I–II, this yields a three-regime universality picture and a precise finite-alphabet Lévy–Khintchine layer for shuffle privacy. MSC 2020: 62B15 (statistical experiments and information); 68P27 (privacy); 60F05 (central limit and other weak theorems); 60E07 (infinitely divisible distributions). Keywords: shuffle model, differential privacy, Le Cam distance, Lévy–Khintchine formula, compound Poisson, multinomial normal approximation. 1 Introduction Part I [ 1 ] develops the Gaussian regime for neighboring shuffle experiments: for a fixed finite-output local randomizer with full support bounded away from zero, the released histogram admits a complete conditional-expectation linearization, the neighboring experiment is asymptotically Gaussian in the sense of Le Cam, and the privacy-curve converges to the GDP curve [ 12 ] with Berry–Esseen control. Part II [ 2 ] shows that this Gaussian picture breaks at the critical concentration threshold. In the canonical one-dominant setting the neighboring experiment converges to a Poisson-shift limit; for proportional compositions it converges to a Skellam-shift limit; and for general finite alphabets in the sparse-error regime the released histogram converges, after centering, to a multivariate compound-Poisson law. The shuffle model was initiated by [ 13 , 14 ] and further developed in [ 15 , 16 , 17 ] . For background on Le Cam theory and asymptotic statistics, see [ 3 , 4 ] ; for Poisson approximation tools used repeatedly below, see [ 8 , 9 ] . The remaining gap is structural rather than scalar. Part II isolates the first hybrid weak limit in the special two-dominant disjoint case, where the dominant block carries a Gaussian factor and the rare block carries a compound-Poisson factor, but it does not cover overlapping dominant sets, dominant blocks of size larger than two, or the general quotient geometry induced by several comparable dominant outputs. This paper closes that gap at the level of weak limits and projected experiments. The central theorem identifies the dominant tangent space M=M_{0}+M_{1}, projects the released histogram onto the Gaussian block M , quotients out the same tangent directions to the rare block M^{\perp} , and proves a general finite-alphabet Lévy–Khintchine limit (G,J)\quad\text{versus}\quad(G,J+\Delta) for the neighboring shuffled experiment. The overlap case does not require a different limiting object: the same hybrid limit persists, but the deterministic quotient shift \Delta may collapse to zero. The main results are Theorem 3.1 , which gives weak convergence of the full hybrid statistic, O(n^{-1}) total-variation and Le Cam convergence for the projected jump experiment, and privacy-curve convergence for the full experiment in the interior regime, in the weak boundary regime, and in the regular strong-boundary cases in which no unsmoothed finite minority tangent block remains. A short counterexample shows that no fully general strong-boundary privacy-curve theorem is possible: a bounded minority block can retain dominant internal geometry that vanishes weakly but remains visible to exact histogram tests. The theorem specializes back to the single-dominant multivariate compound-Poisson limit of Part II and to the two-dominant disjoint hybrid limit of Part II, Appendix B. At the level of general theory, the abstract existence of infinitely divisible limit experiments is classical. Strasser’s scale-invariance theorem [ 5 ] and the monograph of Janssen, Milbrodt, and Strasser [ 6 ] develop a general Lévy–Khintchine theory for statistical experiments with independent increments. What is new here is the explicit finite-alphabet shuffle geometry: the dominant tangent space, the quotient by the dominant hypergraph, the compound-Poisson jump field attached to rare outputs, and the accompanying privacy-curve statements. On the Gaussian side, Carter’s deficiency bound between multinomial and multivariate normal experiments [ 7 ] is a central precursor, but it treats the dense regime in which all relevant cell probabilities stay bounded away from zero; our setting contains genuinely rare O(n^{-1}) cells and therefore falls outside that framework. At the level of shuffle privacy, Takagi and Liew [ 18 ] obtain asymptotic privacy amplification bounds beyond pure local differential privacy, while Daskalakis, Kamath, and Tzamos [ 10 ] give a structural Gaussian-plus-sparse decomposition for Poisson multinomial distributions. The present paper is complementary to both lines: it works at the level of neighboring binary experiments, explicit Le Cam limits, and sharp privacy-curve asymptotics for shuffled histograms. 2 Model and notation 2.1 Shuffle mechanism, transcript laws, and privacy curves Fix a population size n\geq 1 . Each user i\in\{1,\dots,n\} holds a private datum x_{i}\in\{0,1\} . A (possibly n -dependent) local randomizer is a Markov kernel W^{(n)}:\{0,1\}\to\Delta(\mathcal{Y}),\qquad b\mapsto W_{b}^{(n)}, where \mathcal{Y} is a finite output alphabet and \Delta(\mathcal{Y}) denotes the simplex of probability measures on \mathcal{Y} . Given an input dataset x^{n}=(x_{1},\dots,x_{n}) , users apply W^{(n)} independently to produce messages Y_{i}\sim W^{(n)}_{x_{i}} . The shuffle mechanism outputs the multiset of messages, equivalently its histogram N(y):=\sum_{i=1}^{n}\mathbf{1}\{Y_{i}=y\}\in\mathbb{Z}^{\mathcal{Y}},\qquad\sum_{y\in\mathcal{Y}}N(y)=n. For k\in\{0,\dots,n\} , let T_{n,k} denote the law of the released histogram when the dataset has exactly k ones and n-k zeros. The neighboring shuffle experiment associated with k versus k+1 ones is the binary experiment \mathcal{E}_{n,k}:=(P_{n,k},Q_{n,k}),\qquad P_{n,k}:=T_{n,k},\qquad Q_{n,k}:=T_{n,k+1}. For a binary experiment (P,Q) on any measurable space, the one-sided privacy curve is \delta_{Q\|P}(\varepsilon):=\sup_{A}\bigl\{Q(A)-e^{\varepsilon}P(A)\bigr\},\qquad\varepsilon\geq 0, where the supremum ranges over all measurable sets A . Lemma 2.1 (Contraction of total variation under measurable maps) . Let \mu,\nu be probability measures on (\mathcal{X},\mathcal{F}) and let f:\mathcal{X}\to\mathcal{Z} be measurable. Then \mathrm{TV}(\mu\circ