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

1. Problématique et Contexte

Ce travail constitue la troisième partie d'une série visant à établir une théorie asymptotique complète pour les expériences de « shuffling » (brouillage) dans le modèle de confidentialité différentielle, spécifiquement pour des alphabets finis.

• Contexte : Le modèle de shuffling (introduit par [13, 14]) permet d'amplifier la confidentialité en mélangeant les messages sortis par des randomisateurs locaux.
• État de l'art (Parties I et II) :
  • La Partie I a établi une limite Gaussienne (LAN/GDP) lorsque le randomisateur local a un support complet et borné loin de zéro.
  • La Partie II a identifié la rupture de cette limite Gaussienne lorsque le randomisateur devient très concentré (régime « rare »), menant à des limites de type Poisson, Skellam ou Poisson composé multivarié.
• Le problème résolu ici : Il existait une lacune structurelle pour les régimes hybrides où plusieurs blocs dominants (ensembles de sorties probables) interagissent, notamment dans les cas de chevauchement (overlap) entre les ensembles dominants des deux hypothèses voisines, ou lorsque la taille des blocs dominants est arbitraire. L'objectif est de caractériser la géométrie limite exacte de l'expérience de shuffling voisine dans ces configurations complexes.

2. Méthodologie

L'auteur développe une approche basée sur la géométrie des espaces tangents dominants et la théorie des expériences statistiques (distance de Le Cam, courbes de confidentialité).

• Décomposition de l'espace d'état :
  • Soit $Y$ l'alphabet de sortie. L'auteur définit des ensembles dominants $D_0$ et $D_1$ pour les hypothèses $0$ et $1$.
  • Il introduit un espace tangent dominant $M = M_0 + M_1$, où $M_b$ est l'espace des vecteurs à somme nulle sur $D_b$.
  • L'espace est décomposé en deux parties orthogonales :
    1. $M$ (Partie Gaussienne) : Projeter l'histogramme sur $M$ capture la variabilité des blocs dominants, qui converge vers un processus Gaussien.
    2. $M^\perp$ (Partie Quotient/Rare) : Le quotient par $M$ isole les sorties rares et les composantes structurelles des blocs dominants qui ne sont pas capturées par la somme. Cette partie converge vers un champ de sauts de type Poisson composé.
• Géométrie du quotient :
  • L'auteur utilise une structure d'hypergraphe pour analyser la connectivité entre $D_0$ et $D_1$.
  • Si $D_0 \cap D_1 = \emptyset$, les composantes sont disjointes. Si elles se chevauchent, la géométrie du quotient change : le décalage déterministe dans l'espace quotient peut s'annuler ($\Delta = 0$).
• Outils techniques :
  • Convergence faible vers des lois de Lévy-Khintchine.
  • Approximation de Poisson pour les catégories rares.
  • Couplages et bornes de variation totale (TV) pour comparer les lois finies aux lois limites.
  • Théorèmes de Berry-Esseen aux limites (boundary) pour quantifier la transition Poisson $\to$ Gaussien.

3. Contributions Clés et Résultats Principaux

Le résultat central est le Théorème 3.1, qui décrit la limite faible de l'expérience de shuffling voisine comme un produit de deux composantes indépendantes :

A. Convergence Faible Hybride (Théorème 3.1(i))

Sous des hypothèses générales de régimes dominants finis, la statistique normalisée $S_n$ converge faiblement vers une paire $(G, J)$ :

• $G$ (Gaussien) : Une variable aléatoire normale multivariée $N(0, \Sigma)$ vivant sur l'espace tangent dominant $M$. Ce terme est commun aux deux hypothèses voisines (pas de décalage Gaussien).
• $J$ (Poisson Composé) : Un vecteur aléatoire de sauts vivant sur l'espace quotient $M^\perp$, suivant une loi de Poisson composé avec une mesure de Lévy $\nu$.
• Le Décalage ($\Delta$) : Toute la différence entre les deux hypothèses voisines est portée par un décalage déterministe $\Delta \in M^\perp$.
  • Si les ensembles dominants se chevauchent ($D_0 \cap D_1 \neq \emptyset$), alors $\Delta = 0$, et les limites sous les deux hypothèses sont identiques ($P_\infty = Q_\infty$).
  • Si elles sont disjointes, $\Delta \neq 0$, créant un décalage de type Poisson.

B. Convergence en Variation Totale et Le Cam (Théorème 3.1(ii))

Pour la partie projetée sur l'espace quotient (le bloc de sauts), l'auteur prouve une convergence forte en variation totale à un taux $O(n^{-1})$ sous des conditions de régularité quantitative. Cela signifie que l'expérience projetée est très proche de sa limite Poisson composée.

C. Convergence de la Courbe de Confidentialité (Théorème 3.1(iii))

La courbe de confidentialité $\delta(\varepsilon)$ de l'expérience complète converge vers celle de la limite hybride $(G, J)$ dans plusieurs régimes :

• Régime intérieur : $\pi \in (0, 1)$.
• Régime de frontière faible : Un groupe est très petit mais tend vers l'infini.
• Régime de frontière forte (régulier) : Un groupe est borné, mais seulement si le bloc minoritaire est « absorbé » par le bloc majoritaire ou s'il est trivial.

D. Obstruction et Sharpness (Proposition 6.1 & Théorèmes 7.1-7.3)

• Obstruction : Sans hypothèse structurelle supplémentaire (régularité forte), la limite projetée (sauts) ne détermine pas toujours la courbe de confidentialité complète. Un bloc minoritaire borné peut conserver une géométrie interne visible par des tests exacts, même si elle disparaît faiblement.
• Taux de convergence : Le taux de convergence global pour l'expérience hybride est généralement $O(n^{-1/2})$. Ce taux est optimal (sharp) et provient de la difficulté à coupler les blocs dominants lorsque les lois de répartition conditionnelle des messages croisés diffèrent.
• Condition de compatibilité : Si les lois de répartition des messages croisés (minoritaires dans un bloc dominant) coïncident asymptotiquement avec les lois natives, le taux de convergence s'améliore à $O(n^{-1})$.

E. Théorème de Berry-Esseen aux Limites (Théorème 8.1)

L'auteur prouve que lorsque le paramètre d'échelle critique $c \to 0$, l'expérience de Poisson critique est à une distance de Le Cam de $O(c)$ de l'expérience Gaussienne. Cela établit une transition continue entre les régimes Poisson et Gaussien.

4. Signification et Impact

Ce papier complète la théorie asymptotique du shuffling pour les alphabets finis en fournissant une décomposition de Lévy-Khintchine explicite :

1. Unification des régimes : Il unifie les régimes Gaussiens (Partie I) et Poissoniens (Partie II) en un cadre unique où l'expérience limite est un produit d'une composante Gaussienne (dominante) et d'une composante de sauts (rare/quotient).
2. Géométrie du chevauchement : Il résout le problème des ensembles dominants chevauchants, montrant que cela ne change pas la structure de la limite, mais annule simplement le décalage déterministe, conduisant à une perte de confidentialité asymptotique dans la limite.
3. Limites de la confidentialité : Il identifie précisément les conditions sous lesquelles la confidentialité peut être entièrement décrite par la composante de sauts projetée, et met en évidence les cas pathologiques où des détails fins (bloc minoritaire) échappent à l'analyse asymptotique standard.
4. Précision des taux : Il affine la compréhension des taux de convergence ($n^{-1/2}$ vs $n^{-1}$), crucial pour les applications pratiques où $n$ est fini.

En résumé, cette série de travaux établit que la confidentialité différentielle dans le modèle de shuffling est gouvernée par une géométrie de quotient qui sépare la variabilité « lisse » (Gaussienne) de la variabilité « rare » (Poisson), offrant ainsi une carte complète des limites de confidentialité pour tout alphabet fini.