Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy -- Poisson, Skellam, and Compound-Poisson Regimes
This work addresses foundational limits in differential privacy for shuffled data, providing a three-regime classification that is incremental but crucial for theoretical understanding.
The paper tackles the problem of characterizing non-Gaussian limits for shuffle privacy when local randomizers become increasingly concentrated, proving convergence to Poisson, Skellam, and compound-Poisson shift experiments for specific scaling regimes, with explicit limiting privacy curves.
Part I of this series (arXiv:2602.09029) develops a sharp Gaussian (LAN/GDP) limit theory for neighboring shuffle experiments when the local randomizer is fixed and has full support bounded away from zero. The present paper characterizes the first universality-breaking frontier: critical sequences of increasingly concentrated local randomizers for which classical Lindeberg conditions fail and the shuffle score exhibits rare macroscopic jumps. For shuffled binary randomized response with local privacy $\varepsilon_0 = \varepsilon_0(n)$, we prove experiment-level convergence (in Le Cam distance) to explicit shift limit experiments: a Poisson-shift limit for the canonical neighboring pair when $\exp(\varepsilon_0(n))/n \to c^2$, and a Skellam-shift limit for proportional compositions $k/n \to π\in (0,1)$ in the same scaling, including an explicit disappearance of the two-sided $δ$-floor away from boundary compositions. For general finite alphabets, we introduce a sparse-error critical regime and prove a multivariate compound-Poisson / independent Poisson vector limit for the centered released histogram, yielding a multivariate Poisson-shift experiment and an explicit limiting $(\varepsilon, δ)$ curve as a multivariate Poisson series. Together with Part I, these results yield a three-regime picture (Gaussian/GDP, critical Poisson/Skellam/compound-Poisson, and super-critical no privacy) under convergent macroscopic scalings.