Universal Shuffle Asymptotics, Part III: Dominant-Block Quotient Geometry and Hybrid Gaussian--Compound-Poisson Limits in Finite-Alphabet Shuffle Privacy

Titel en Context

Dit artikel is het derde deel van een serie die de asymptotische theorie van het "shuffle model" voor differentieel privacy (DP) bestudeert. Het bouwt voort op Deel I (Gaussian-regime bij volledige steun) en Deel II (kritieke Poisson-regimes bij geconcentreerde local randomizers). Dit deel vult de theorie aan voor het algemene geval van eindige alfabetten met meerdere dominante blokken, overlappende sets en complexe geometrieën.

1. Het Probleem

Het shuffle model is een privacyversterkend protocol waarbij gebruikers hun data eerst lokaal randomiseren en vervolgens naar een onbetrouwbare aggregator sturen, die de berichten "shuffle" (vermengt) voordat ze worden vrijgegeven.

• Achtergrond: Deel I toonde aan dat bij vaste, volledige steun de histogrammen asymptotisch Gaussisch zijn (GDP). Deel II toonde aan dat bij zeldzame fouten (concentratie) de limiet overgaat in Poisson- of Compound-Poisson-verdelingen.
• De Gaten: Er bestond geen volledige theorie voor het hybride regime waarin:
  1. Er meerdere "dominante" outputsets zijn (niet slechts één).
  2. Deze dominante sets overlappen ($D_0 \cap D_1 \neq \emptyset$).
  3. De geometrie van de "zeldzame" (rare) fouten en de "dominante" blokken gecombineerd moet worden beschouwd.
  4. De privacy-curve (de exacte privacy-garantie) moet worden gekwantificeerd in deze complexe scenario's, inclusief de randgevallen (boundary regimes).

2. Methodologie en Kader

De auteur gebruikt een combinatie van asymptotische statistiek, Le Cam-theorie (voor vergelijking van experimenten) en de theorie van oneindig deelbare verdelingen (Lévy-Khintchine).

• Model: Een populatie van $n$ gebruikers met binaire data ($0$ of $1$). Elke gebruiker past een lokale randomizer $W^{(n)}$ toe op een eindig alfabet $\mathcal{Y}$.
• Regime: Het "general finite-dominant sparse-error regime". Hierbij bestaan er dominante sets $D_b$ met waarschijnlijkheden $p_b(y) > 0$ en zeldzame intensiteiten $\alpha_b(y)$ voor $y \notin D_b$.
• Geometrische Decompositie:
  • De auteur introduceert een dominante raakruimte $M = M_0 + M_1$, waar $M_b$ de ruimte is van nul-som vectoren over de dominante set $D_b$.
  • De histogrammen worden geprojecteerd op $M$ (Gaussisch deel) en op de orthogonale kwotiëntruimte $M^\perp$ (Compound-Poisson deel).
  • De structuur van $M^\perp$ wordt bepaald door de hypergraaf van de dominante sets. Als $D_0$ en $D_1$ overlappen, collapseert de deterministische verschuiving in de kwotiëntruimte.

3. Belangrijkste Bijdragen en Resultaten

A. Algemene Lévy-Khintchine Limietstelling (Theorema 3.1)

De kern van het artikel is een stelling die de limiet van het buren-experiment (neighboring experiment) karakteriseert als een hybride verdeling:

• De Limiet: Het experiment convergeert naar een paar $(G, J)$ versus $(G, J + \Delta)$.
  • $G \sim \mathcal{N}(0, \Sigma)$: Een Gaussisch proces op de dominante raakruimte $M$.
  • $J$: Een onafhankelijke Compound-Poisson vector op de kwotiëntruimte $M^\perp$, met Lévy-maat $\nu$ bepaald door de zeldzame intensiteiten.
  • $\Delta = \Pi_J(\mu_1 - \mu_0)$: Een deterministische verschuiving in de kwotiëntruimte.
• Overlappende Sets: Als de dominante sets overlappen ($D_0 \cap D_1 \neq \emptyset$), dan is $\Delta = 0$. Dit betekent dat de deterministische verschuiving verdwijnt en de limiet onder beide hypothesen identiek is ($P_\infty = Q_\infty$), wat impliceert dat de privacy-curve naar nul convergeert in de limiet.

B. Convergentie van Privacy-curves

Het artikel bewijst convergentie van de privacy-curve $\delta_{Q_n \| P_n}(\varepsilon)$ naar de limiet $\delta_{Q_\infty \| P_\infty}(\varepsilon)$ in drie regimes:

1. Interieur-regime: $\pi \in (0, 1)$ (gemengde populatie).
2. Zwakke rand: Eén groep wordt klein maar groeit nog steeds ($k_n \to \infty, k_n/n \to 0$).
3. Sterke rand (met regulariteit): Eén groep is begrensd ($k_n = O(1)$), mits de dominante blokken van de minderheid worden "geabsorbeerd" door de meerderheid of als de minderheid slechts één punt heeft.

C. Sharpness van Convergentiesnelheden

• O(n⁻¹/²) Barrière: De auteur toont aan dat de convergentiesnelheid van de totale variatieafstand in het hybride experiment in het algemeen scharp is op $O(n^{-1/2})$. Dit komt door de moeilijkheid om de dominante blokken te "gladstrijken" (smoothing) wanneer er kruisende berichten zijn tussen de dominante sets.
• O(n⁻¹) Herstel: Er wordt een compatibiliteitsvoorwaarde geïdentificeerd (Theorema 7.3). Als de verdeling van de "kruisende" berichten (van de ene groep naar de dominante set van de andere) asymptotisch overeenkomt met de native verdeling van die set, dan wordt de snellere $O(n^{-1})$ snelheid hersteld.

D. Rand-Berry-Esseen Theorema (Theorema 8.1)

Het artikel bewijst dat het kritieke Poisson-shift experiment (uit Deel II) binnen een afstand van $O(c)$ van het Gaussische shift experiment ligt wanneer de schaalparameter $c \downarrow 0$. Dit verbindt de Poisson- en Gaussische regimes naadloos aan de grens.

E. Obstructie voor Algemene Rand-resultaten (Propositie 6.1)

De auteur presenteert een tegenvoorbeeld dat laat zien dat zonder extra structurele aannames (zoals absorptie van de minderheid), de geprojecteerde limiet niet de volledige privacy-curve bepaalt. Een begrensd minderheidsblok kan interne geometrie behouden die in de zwakke limiet verdwijnt, maar zichtbaar blijft voor exacte histogramtests, waardoor de privacy-curve niet naar nul convergeert terwijl de limiettheorie dat wel voorspelt.

4. Technische Details en Bewijstechnieken

• Karakteristieke Functies: Uitbreiding van de karakteristieke functie van de histogrammen in een driehoeksarray (triangular array) om de Lévy-Khintchine vorm af te leiden.
• Coupling en Total Variation: Gebruik van koppelingen (couplings) en "telescoping" argumenten om de afstand tussen de echte verdeling en een surrogaat-verdeling (met vervangen van kruisende berichten door native berichten) te begrenzen.
• Multinomial Smoothing: Toepassing van lemma's over de Total Variation afstand tussen multinomiale verdelingen die verschuiven door één extra observatie (Lemma A.5), wat essentieel is voor het bewijzen van de $O(n^{-1/2})$ snelheid.
• Quotient Geometry: Het gebruik van projecties op $M$ en $M^\perp$ om de Gaussische en Poisson-componenten te scheiden, waarbij de overlap van sets leidt tot een degeneratie van de verschuiving $\Delta$.

5. Betekenis en Impact

Dit artikel voltooit de asymptotische theorie voor shuffle privacy in eindige alfabetten.

• Unificatie: Het verenigt de Gaussische en Poisson-regimes in één raamwerk (Lévy-Khintchine) dat de volledige overgang beschrijft.
• Precisie: Het biedt exacte snelheidsresultaten ($O(n^{-1/2})$ vs $O(n^{-1})$) en identificeert wanneer de privacy-curve volledig wordt bepaald door de geprojecteerde limiet en wanneer niet.
• Praktische Implicatie: Voor ontwerpers van shuffle-protocollen geeft het inzicht dat overlapping van dominante outputsets de privacy drastisch kan verbeteren (door $\Delta=0$ te maken), maar dat de convergentie naar deze limiet traag kan zijn als de "kruisende" verdelingen niet goed gematcht zijn.
• Toekomstige Richtingen: Het artikel markeert de grenzen van de huidige theorie, met name voor countable alfabetten en niet-gecombineerde (unbundled) mechanismen, en stelt vragen over de optimale snelheid in overlappende regimes.

Kortom, dit werk levert de wiskundige fundamenten voor het begrijpen van de privacy-grenzen van shuffle-systemen in het meest algemene en realistische regime van eindige alfabetten met zeldzame fouten.