Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy -- Poisson, Skellam, and Compound-Poisson Regimes

Dieser zweite Teil der Serie charakterisiert die kritischen Regime des Shuffle-Modells, in denen lokale Randomizer stark konzentriert sind und die klassischen Gaußschen Grenzwertsätze durch nicht-gaußsche Verteilungen wie Poisson-, Skellam- und zusammengesetzte Poisson-Prozesse ersetzt werden.

Das Wesentliche

Stell dir vor, du bist der Organisator einer riesigen Umfrage unter einer Stadt von 10.000 Menschen. Jeder soll eine geheime Frage beantworten (z. B. „Hast du gestohlen?"). Um die Privatsphäre zu schützen, gibt es zwei Regeln:

1. Der lokale Zufall: Jeder Teilnehmer wirft vor dem Antworten einen fairen Münzwurf (oder einen Würfel). Wenn er „Kopf" zeigt, sagt er die Wahrheit. Wenn „Zahl", lügt er zufällig. Das ist die lokale Privatsphäre.
2. Der Mixer (Shuffle): Niemand weiß, wer was gesagt hat. Alle Antworten werden in einen Mixer geworfen, durcheinandergerührt und als ein großer Haufen (ein Histogramm) veröffentlicht. Niemand kann mehr zurückverfolgen, welche Antwort von wem kam.

Teil I dieser Forschungsreihe hat gezeigt: Wenn die Münze sehr fair ist (die Leute lügen oft), dann verhält sich der große Haufen der Antworten wie eine Glockenkurve (Gaußverteilung). Das ist das „normale" Verhalten, das wir aus der Statistik kennen.

Dieses Papier (Teil II) untersucht nun den kritischen Randfall: Was passiert, wenn wir die Münze so manipulieren, dass sie fast immer „Kopf" zeigt, aber gelegentlich (sehr selten!) „Zahl" wirft?

Hier ist die einfache Erklärung der neuen Entdeckungen, verpackt in Metaphern:

1. Das Problem: Der „Seltene Riese"

In der normalen Welt (Teil I) sind die Fehler der Teilnehmer klein und zahlreich. Wenn 10.000 Leute jeweils einen kleinen Fehler machen, heben sie sich gegenseitig auf, und das Ergebnis ist glatt und vorhersehbar (Gauß).

In diesem neuen Szenario (Teil II) machen die Teilnehmer fast gar keine Fehler. Aber wenn einer einen Fehler macht, ist es ein riesiger, lauter Knall.

• Die Analogie: Stell dir vor, du hörst in einem ruhigen Raum.
  • Normalfall: 10.000 Leute flüstern leise. Du hörst ein gleichmäßiges Rauschen (Gauß).
  • Kritischer Fall: 9.999 Leute sind absolut still. Aber plötzlich schreit eine Person laut auf. Oder zwei. Oder drei.
  • Das Ergebnis ist kein Rauschen mehr, sondern ein Pochen oder Pochen. Die Statistik ändert sich von einer glatten Kurve zu einer Reihe von plötzlichen Sprüngen.

2. Die drei neuen Welten (Die Regime)

Das Papier beschreibt drei verschiedene Welten, je nachdem, wie stark wir die „Lügen-Wahrscheinlichkeit" einstellen:

A. Die Poisson-Welt (Der „Einzelne Schuss")

• Szenario: Wir haben nur zwei Antwortmöglichkeiten (Ja/Nein). Die Wahrscheinlichkeit, dass jemand lügt, ist so klein, dass wir im Durchschnitt nur einen oder zwei Lügner in der ganzen Stadt erwarten.
• Das Ergebnis: Die Statistik verhält sich nicht mehr wie eine Glockenkurve, sondern wie ein Zufallsgenerator für seltene Ereignisse (Poisson-Verteilung).
• Die Überraschung: Es gibt eine „Bodenplatte" (Floor). Selbst wenn man versucht, die Daten perfekt zu analysieren, gibt es eine minimale Unsicherheit, die man nicht wegdrücken kann.
  • Metapher: Stell dir vor, du suchst nach einem Dieb in einer leeren Halle. Wenn du niemanden siehst, bist du dir zu 99% sicher, dass niemand da ist. Aber es gibt eine winzige Chance (z. B. 1%), dass der Dieb sich wirklich gut versteckt hat. Diese winzige Chance ist der „Boden", den man nicht ignorieren kann. In der alten Theorie (Gauß) wäre diese Chance theoretisch null gewesen.

B. Die Skellam-Welt (Der „Zug-und-Abzug")

• Szenario: Wir haben eine Mischung aus Ja- und Nein-Antworten (z. B. 50% Ja, 50% Nein).
• Das Ergebnis: Hier kämpfen zwei Arten von seltenen Fehlern gegeneinander. Ein paar Leute lügen „Ja" statt „Nein", ein paar lügen „Nein" statt „Ja".
• Die Metapher: Stell dir einen Zug vor, der auf einer Schiene steht. Manchmal springt ein Passagier nach vorne (Fehler A), manchmal springt einer nach hinten (Fehler B). Die Position des Zuges ist die Differenz dieser Sprünge. Diese Verteilung nennt man Skellam. Sie ist wie ein Tanz zwischen zwei Poisson-Verteilungen.
• Wichtig: Wenn die Mischung ausgewogen ist, gibt es keinen „Boden" mehr. Die Unsicherheit verschwindet, wenn man genau hinschaut, weil die Fehler sich gegenseitig aufheben können.

C. Die Compound-Poisson-Welt (Der „Bunte Haufen")

• Szenario: Wir haben mehr als zwei Antwortmöglichkeiten (z. B. Farben: Rot, Blau, Grün).
• Das Ergebnis: Hier wird es komplex. Es gibt viele verschiedene Arten von seltenen Fehlern.
• Die Metapher: Stell dir einen Regen vor, bei dem nicht nur Wassertropfen fallen, sondern auch kleine Kugeln, Stifte und Blätter. Jeder Gegenstand ist ein „Fehler". Die Verteilung dieses bunten Haufens ist eine verallgemeinerte Poisson-Verteilung.
• Das Papier zeigt, dass man auch hier eine exakte Formel für die Privatsphäre finden kann, die wie eine Summe aus vielen kleinen, seltenen Ereignissen aussieht.

3. Warum ist das wichtig?

Bisher dachten viele Forscher: „Wenn wir genug Leute haben, ist alles Gauß (normal) und wir können die alten Formeln benutzen."

Dieses Papier sagt: Nein!
Wenn wir die Privatsphäre-Einstellungen (den „Lügen-Parameter") genau an die Grenze bringen, wo die Fehler sehr selten, aber nicht unmöglich sind, brechen die alten Regeln.

• Die alten Formeln unterschätzen das Risiko.
• In der kritischen Zone gibt es eine harte Grenze (den „Boden"), unter die die Privatsphäre nicht fallen kann, egal wie sehr man versucht, die Daten zu schützen.

Zusammenfassung in einem Satz:

Dieses Papier zeigt uns, dass wenn wir Datenschutz so stark machen, dass Fehler extrem selten werden, die Statistik nicht glatt und vorhersehbar wird, sondern zu einem wilden Tanz aus seltenen, lauten Sprüngen (Poisson), die eine unvermeidbare minimale Unsicherheit hinterlassen.

Für den Praktiker: Wenn du ein Datenschutz-System baust, darfst du nicht einfach annehmen, dass „mehr Leute = mehr Sicherheit". Wenn du die Einstellungen zu weit in den kritischen Bereich schiebst, verlierst du plötzlich die Kontrolle über die Art der Unsicherheit, und die alten Schutzschilder funktionieren nicht mehr so, wie du denkst.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papiers „Universal Shuffle Asymptotics, Part II: Non-Gaussian Limits for Shuffle Privacy" von Alex Shvets (März 2026) auf Deutsch.

1. Problemstellung und Kontext

Das Papier ist der zweite Teil einer Serie, die sich mit der Shuffle-Modell-Differentialprivacy (DP) befasst. Während Teil I [1] eine scharfe gaußsche Grenzwerttheorie (LAN/GDP) für lokale Randomisierer mit festem, von Null entferntem Support entwickelte, adressiert Teil II die kritischen Übergangsbereiche, in denen die klassischen Annahmen (wie die Lindeberg-Bedingung) versagen.

Das Kernproblem:
In der Praxis wird der lokale Privatsphäre-Parameter $\varepsilon_0$ oft mit der Populationsgröße $n$ skaliert (z. B. um die Varianz von Schätzern zu reduzieren). Wenn $\varepsilon_0(n)$ so gewählt wird, dass $e^{\varepsilon_0(n)} \sim n$ gilt (kritische Skalierung), treten folgende Phänomene auf:

• Die lokalen Fehlerwahrscheinlichkeiten sind von der Ordnung $O(1/n)$.
• Die Gesamtzahl der „Fehler" (Abweichungen vom dominanten Ausgabewert) konvergiert nicht gegen Null, sondern gegen eine endliche Zufallsvariable.
• Die Log-Likelihood-Ratio erfährt makroskopische Sprünge, die durch eine Summe kleiner Inkremente (Gaußsche Approximation) nicht mehr beschrieben werden können.
• Das Ergebnis ist ein nicht-gaußscher Grenzwert, der durch Poisson-, Skellam- oder zusammengesetzte Poisson-Verteilungen charakterisiert wird.

Das Ziel des Papiers ist es, eine scharfe nicht-gaußsche Grenzwerttheorie auf Ebene der statistischen Experimente (Le Cam-Distanz) zu entwickeln und explizite Konvergenzraten sowie Grenzkurven für die Privatsphäre zu liefern.

2. Methodik

Die Autoren verwenden einen rigorosen mathematischen Rahmen, der auf der Theorie der statistischen Experimente und der Le Cam-Distanz basiert.

• Modell: Das Shuffle-Modell mit $n$ Benutzern, die lokale Randomisierer $W^{(n)}$ anwenden. Die Ausgabe ist ein Histogramm (Multimenge) der Nachrichten.
• Skalierungsregime: Die Analyse konzentriert sich auf das kritische Regime, definiert durch den Parameter $a_n = e^{\varepsilon_0(n)}/n \to c^2 \in (0, \infty)$.
• Approximationswerkzeuge:
  • Kopplung (Coupling): Um Total-Variations-Distanzen (TV) zwischen Binomial- und Poisson-Verteilungen sowie zwischen verschiedenen Poisson-Parametern zu schätzen (Lemma A.1, A.2).
  • Le Cam-Distanz: Zur Quantifizierung der Äquivalenz zwischen dem endlichen Shuffle-Experiment und dem asymptotischen Grenzexperiment.
  • Charakteristische Funktionen: Für die Herleitung von Grenzwerten bei gemischten Regimen (Gaußsch + zusammengesetzt-Poisson).
  • Bedingte Glättung: Um die Konvergenz der Privatsphäre-Kurven auch in Fällen zu beweisen, in denen die Total-Variations-Konvergenz für das gesamte Experiment nicht direkt gilt (Anhang B).

3. Schlüsselbeiträge und Ergebnisse

Das Papier identifiziert drei Hauptregime und liefert für die kritischen Fälle explizite Grenzwerte:

A. Kanonisches Nachbarn-Paar (Binär, $\pi = 0$ oder $1$)

Für den Fall, dass fast alle Benutzer denselben Eingabewert haben (z. B. alle 0, außer einer 1):

• Ergebnis: Das Grenzexperiment ist ein Poisson-Verschiebungs-Experiment (Poisson-shift limit).
• Theorem 3.1: Unter der Skalierung $e^{\varepsilon_0(n)} \approx c^2 n$ konvergiert das Experiment gegen $(P_\infty, Q_\infty) = (\text{Poi}(\lambda), 1 + \text{Poi}(\lambda))$ mit $\lambda = c^{-2}$.
• Konvergenzrate: Explizite $O(n^{-1})$-Schranken für die Total-Variations-Distanz.
• Wichtiges Phänomen: Eine $\delta$-Floor (Bodenschranke) entsteht. Da die Verteilung $Q_\infty$ den Wert 0 nicht unterstützt (da sie eine Verschiebung um 1 ist), aber $P_\infty$ dies tut, bleibt die gegenseitige Privatsphäre $\delta(\varepsilon)$ auch für $\varepsilon \to \infty$ strikt positiv ($\ge e^{-\lambda}$). Dies ist ein intrinsisches Merkmal des kritischen Regimes.

B. Proportionale Zusammensetzungen (Binär, $\pi \in (0, 1)$)

Wenn der Anteil der Benutzer mit Wert 1 gegen einen konstanten Wert $\pi$ konvergiert:

• Ergebnis: Das Grenzexperiment ist ein Skellam-Verschiebungs-Experiment.
• Theorem 4.1: Die zentrierte Histogramm-Differenz konvergiert gegen eine Skellam-Verteilung $D \sim \text{Skellam}(\lambda_0, \lambda_1)$, wobei $\lambda_0, \lambda_1$ von $\pi$ und $c$ abhängen. Das Grenzexperiment ist $(L(D), L(1+D))$.
• Kein $\delta$-Floor: Im Gegensatz zum kanonischen Fall haben beide Verteilungen vollen Support auf $\mathbb{Z}$, sodass keine Support-Mismatch-Bodenschranke existiert.
• Monotonie: Es wird gezeigt, dass eine stärkere Skalierung (kleineres $c$) zu besserer Privatsphäre führt.

C. Allgemeine Alphabete (Multivariat)

Für endliche Ausgabemengen $Y$ mit mehreren dominanten Ausgängen:

• Ergebnis: Ein multivariates zusammengesetztes Poisson-Grenzexperiment (Compound-Poisson).
• Theorem 5.8: Das zentrierte Histogramm konvergiert gegen einen Vektor $H_\infty$, der als Summe unabhängiger Poisson-Vektoren dargestellt werden kann.
• Hybrid-Regime (Proposition 5.4): Wenn die dominante Masse auf zwei Ausgänge aufgeteilt ist, entsteht ein hybrides Grenzexperiment: Ein Gaußscher Anteil (für die $\sqrt{n}$-Fluktuationen der dominanten Masse) plus ein unabhängiger zusammengesetzter Poisson-Anteil (für die seltenen $O(1/n)$-Fehler).
• Anhang B: Zeigt, dass trotz des Fehlens einer Total-Variations-Konvergenz für das hybride Experiment (wegen des kontinuierlichen Gauß-Anteils) die Privatsphäre-Kurven dennoch konvergieren, da der Gauß-Anteil unter beiden Hypothesen asymptotisch identisch ist.

4. Drei-Regime-Synthese (Abschnitt 6)

Das Papier fasst die Ergebnisse in einem umfassenden Phasendiagramm zusammen:

1. Sub-kritisches Regime ($a_n \to 0$):

   • Lokale Fehler sind sehr selten ($\varepsilon_0$ klein).
   • Grenzwert: Gaußsch / GDP (wie in Teil I).
   • Die Lindeberg-Bedingung gilt.

2. Kritisches Regime ($a_n \to c^2 \in (0, \infty)$):

   • Lokale Fehler sind selten, aber ihre Anzahl ist $O(1)$.
   • Grenzwert: Poisson / Skellam / Compound-Poisson.
   • Makroskopische Sprünge dominieren die Likelihood-Ratio.
   • Nicht-gaußsche Phänomene wie der $\delta$-Floor treten auf.

3. Super-kritisches Regime ($a_n \to \infty$):

   • Lokale Fehler sind häufig ($\varepsilon_0$ groß).
   • Grenzwert: Keine Privatsphäre (asymptotische Unterscheidbarkeit).
   • Die Total-Variations-Distanz geht gegen 1.

5. Bedeutung und Vergleich mit bestehender Literatur

• Gegenüber bestehender Amplifikation: Herkömmliche Amplifikations-Schranken (z. B. von Balle et al. oder Feldman et al.) basieren oft auf Annahmen, die im kritischen Regime nicht gelten (z. B. viele kleine Beiträge). Das Papier zeigt, dass diese Schranken im kritischen Fenster versagen oder keine endlichen Garantien liefern, da sie den Poisson-Floor nicht erfassen.
• Theoretische Lücke: Es schließt die Lücke zwischen der reinen LDP-Analyse und der Shuffle-DP, indem es die nicht-gaußschen Grenzfälle rigoros behandelt.
• Praktische Relevanz: Die Ergebnisse geben Protokoll-Designern Leitlinien:
  • Um moderate $\delta$-Werte zu erreichen, sollte man im sub-kritischen Regime bleiben.
  • Das Drängen an die kritische Grenze ($\varepsilon_0 \approx \log n$) erfordert eine Kalibrierung basierend auf Poisson/Skellam-Modellen, nicht auf Gauß-Modellen.
  • Die Zusammensetzung der Daten ($\pi$) muss stabil sein, da oszillierende Zusammensetzungen zu unterschiedlichen Grenzwerten führen können.

Fazit

Dieses Papier liefert eine vollständige und scharfe asymptotische Charakterisierung des Shuffle-Modells jenseits des gaußschen Regimes. Es etabliert, dass im kritischen Skalierungsbereich die Privatsphäre durch diskrete Sprungprozesse (Poisson/Skellam) bestimmt wird, was zu fundamental anderen Eigenschaften (wie einer nicht verschwindenden unteren Schranke für $\delta$) führt als in der klassischen Gauß-Näherung. Die Arbeit verbindet statistische Experimenttheorie, Wahrscheinlichkeitstheorie (unendliche Teilbarkeit) und Differentialprivacy auf innovative Weise.