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

1. Problema e Contesto

Il lavoro si inserisce nella teoria asintotica dei modelli di Shuffle (un modello di privacy differenziale che combina la randomizzazione locale con un canale di mescolamento anonimo). Le parti precedenti della serie (Part I e Part II) hanno stabilito:

• Part I: Un limite Gaussiano (LAN/GDP) quando i randomizzatori locali hanno supporto completo e non si concentrano eccessivamente.
• Part II: La rottura del limite Gaussiano quando i randomizzatori diventano "concentrati" (sparse-error regime), portando a limiti di tipo Poisson, Skellam o Compound-Poisson multivariato.

Il problema aperto affrontato in questa terza parte è di natura strutturale: come descrivere il limite asintotico quando si hanno blocchi dominanti di dimensioni arbitrarie (non solo singoli simboli), quando i set dominanti delle due ipotesi adiacenti si sovrappongono, e come caratterizzare la geometria del quoziente che governa l'esperimento di privacy. L'obiettivo è colmare il divario tra i regimi puramente Gaussiani e quelli puramente Poissoniani, fornendo una teoria unificata per il caso generale a alfabeto finito.

2. Metodologia

L'autore utilizza un approccio basato sulla teoria degli esperimenti statistici di Le Cam e sulla geometria degli spazi vettoriali associati agli istogrammi rilasciati.

• Geometria del Quoziente: Viene introdotta una decomposizione dello spazio degli istogrammi in due sottospazi ortogonali:
  1. Spazio Tangente Dominante ($M$): Generato dalle differenze tra i vettori di base dei simboli dominanti. Su questo spazio, il comportamento è asintoticamente Gaussiano.
  2. Spazio di Quoziente ($M^\perp$): Il complemento ortogonale che cattura le informazioni sui simboli "rari" (sparse) e sulle differenze strutturali tra i blocchi dominanti. Su questo spazio, il comportamento è governato da un campo di salti Compound-Poisson.
• Proiezione e Quoziente: L'istogramma centrato viene proiettato su $M$ (ottenendo il fattore Gaussiano) e poi "quozientato" rispetto a $M$ per isolare il comportamento sui blocchi rari (fattore Compound-Poisson).
• Analisi delle Sovrapposizioni: Viene analizzato il caso in cui i set dominanti $D_0$ e $D_1$ (per le ipotesi $x=0$ e $x=1$) non sono disgiunti. Si dimostra che la sovrapposizione non cambia la struttura del limite, ma può far collassare lo spostamento deterministico ($\Delta$) nel quoziente a zero.
• Stime di Velocità: Vengono utilizzati strumenti di approssimazione Poissoniana (teoremi di Berry-Esseen per processi di Poisson) e bound di variazione totale per multinomiali per quantificare la velocità di convergenza.

3. Contributi Chiave e Risultati Principali

A. Teorema del Limite di Lévy-Khintchine Generale (Teorema 3.1)

Il risultato centrale è la caratterizzazione dell'esperimento di shuffle adiacente come un limite ibrido:
$$(G, J) \quad \text{vs} \quad (G, J + \Delta)$$
Dove:

• $G \sim \mathcal{N}(0, \Sigma)$ è una variabile Gaussiana multivariata definita sullo spazio tangente dominante $M$.
• $J$ è un vettore aleatorio Compound-Poisson indipendente, definito sullo spazio di quoziente $M^\perp$, con misura di Lévy $\nu$ derivata dalle intensità rare.
• $\Delta \in M^\perp$ è uno spostamento deterministico che dipende dalla differenza tra le distribuzioni dominanti proiettate.
• Risultato cruciale: Se i set dominanti si sovrappongono ($D_0 \cap D_1 \neq \emptyset$), allora $\Delta = 0$, il che implica che il limite asintotico è identico sotto entrambe le ipotesi (il limite debole non distingue le ipotesi), anche se la privacy finita potrebbe non essere nulla.

B. Convergenza della Curva di Privacy

Il paper stabilisce condizioni precise in cui la curva di privacy dell'esperimento finito converge a quella del limite ibrido:

• Regime Interno: La convergenza vale quando la composizione dei gruppi è strettamente interna ($\pi \in (0,1)$).
• Regimi di Bordo: Viene trattata la convergenza ai bordi (es. un gruppo molto piccolo), ma con una distinzione fondamentale:
  • Se il gruppo minoritario è "assorbito" o ha una struttura semplice, la convergenza vale.
  • Ostacolo al Bordo Forte: Viene dimostrato un controesempio (Proposizione 6.1) che mostra come, senza ipotesi strutturali aggiuntive, il limite proiettato (Compound-Poisson) non determina la curva di privacy completa. Un blocco minoritario limitato può mantenere una geometria interna dominante che scompare debolmente ma rimane visibile ai test esatti sull'istogramma, causando una discrepanza tra il limite e la privacy reale.

C. Sharpness dei Tassi di Convergenza

• Tasso $O(n^{-1/2})$: Viene dimostrato che il tasso di errore $O(n^{-1/2})$ per l'esperimento ibrido completo è sharp (ottimale) in generale. Questo deriva dalla difficoltà di accoppiare i blocchi dominanti quando le distribuzioni di "cross-split" (messaggi di un gruppo che finiscono nel dominio dell'altro) non coincidono perfettamente con le distribuzioni native.
• Condizione di Compatibilità: Viene identificata una condizione specifica (uguaglianza asintotica delle distribuzioni di split incrociato e nativo) sotto la quale il tasso di errore migliora a $O(n^{-1})$.

D. Teorema di Berry-Esseen al Bordo

Viene provato un teorema che quantifica la distanza di Le Cam tra l'esperimento di Poisson critico (o Skellam) e l'esperimento Gaussiano quando il parametro di scala $c \to 0$. La distanza è dell'ordine di $O(c)$, fornendo una transizione continua e controllata tra i regimi Poissoniani e Gaussiani.

4. Significato e Implicazioni

1. Teoria Unificata: Questo lavoro completa la teoria asintotica per la privacy shuffle a alfabeto finito, fornendo una "stratificazione Lévy-Khintchine" precisa. Mostra che la privacy shuffle non è né puramente Gaussiana né puramente Poissoniana, ma una combinazione ibrida governata dalla geometria dei blocchi dominanti.
2. Limiti della Proiezione: La scoperta dell'ostacolo al bordo forte è fondamentale per la progettazione di protocolli. Avverte che approssimare la privacy basandosi solo sul limite debole (proiettato) può essere fuorviante in scenari con gruppi minoritari piccoli ma strutturalmente complessi.
3. Ottimizzazione dei Meccanismi: La distinzione tra il tasso $O(n^{-1/2})$ e $O(n^{-1})$ fornisce indicazioni pratiche su come progettare i randomizzatori locali: allineare le distribuzioni di errore incrociato con quelle native può migliorare drasticamente la precisione delle stime asintotiche della privacy.
4. Fondamenti Matematici: Estende la teoria degli esperimenti statistici con incrementi indipendenti (Le Cam, Strasser) a contesti di privacy differenziale con vincoli di alfabeto finito e mescolamento, collegando la teoria della probabilità (processi di Lévy) alla teoria dell'informazione.

In sintesi, il paper offre la mappa completa delle fasi asintotiche della privacy shuffle, definendo esattamente quando e perché i limiti Gaussiani falliscono, come gestire le sovrapposizioni complesse e quali sono i limiti fondamentali dell'approssimazione asintotica in scenari di dati reali con gruppi di dimensioni variabili.