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

1. Problema y Contexto

El artículo cierra la teoría de límites débiles para experimentos de privacidad diferencial en el modelo de mezcla (shuffle model) con alfabetos finitos. Este trabajo es la tercera parte de una serie:

• Parte I: Estableció un límite Gaussiano (LAN/GDP) para el régimen de soporte completo fijo.
• Parte II: Identificó la frontera donde el límite Gaussiano falla (cuando el randomizador local se concentra), dando lugar a límites de Poisson, Skellam y compuestos-Poisson multivariados.
• Parte III (Actual): Aborda la brecha estructural restante. El objetivo es caracterizar el comportamiento asintótico cuando existen múltiples bloques dominantes (con conjuntos de salida superpuestos o de tamaños arbitrarios) y cuando los bloques dominantes y raros interactúan.

El problema central es determinar la geometría del límite para experimentos de vecinos (neighboring experiments) en el régimen de error escaso general, donde la histograma liberada converge a una mezcla de un factor Gaussiano (en el espacio tangente dominante) y un campo de saltos compuesto-Poisson (en el espacio cociente de los eventos raros).

2. Metodología

El autor utiliza una combinación de teoría de experimentos estadísticos (Le Cam), teoría de probabilidad (teoremas de límite central y aproximación de Poisson) y geometría algebraica lineal aplicada a espacios de vectores de conteo.

A. Geometría de Bloques Dominantes y Cociente

Se define una descomposición del espacio de histogramas $\mathbb{R}^Y$ basada en los conjuntos dominantes $D_0$ y $D_1$ (los soportes de las probabilidades dominantes bajo las hipótesis $0$y$1$):

1. Espacio Tangente Dominante ($M$): Se define como la suma de los subespacios tangentes de los bloques dominantes: $M = M_0 + M_1$. Este espacio captura la variabilidad "suave" o Gaussiana.
2. Espacio Cociente ($M^\perp$): Es el complemento ortogonal de $M$. Este espacio captura las desviaciones de los eventos raros y la estructura de los saltos.
3. Proyecciones: Se utilizan proyecciones ortogonales $\Pi_G$ (sobre $M$) y $\Pi_J$ (sobre $M^\perp$) para separar la estadística híbrida en dos componentes independientes asintóticamente.

B. Hipótesis de Régimen

Se asume un régimen de error escaso general:

• Para cada hipótesis $b \in \{0, 1\}$, existe un conjunto dominante $D_b$ con leyes $p_b$.
• Las probabilidades de salida en $D_b$ son $p_b(y) + O(n^{-1})$.
• Las probabilidades de salida en $Y \setminus D_b$ son de orden $O(n^{-1})$, convergiendo a intensidades $\alpha_b(y)$.

C. Herramientas de Prueba

• Convergencia de Funciones Características: Se utiliza el teorema de continuidad de Lévy para demostrar la convergencia débil de la estadística híbrida normalizada.
• Acoplamiento y Descomposición Condicional: Para probar la convergencia de las curvas de privacidad, se descompone la estadística completa en una parte condicional (dominante) y una parte proyectada (rara). Se utilizan acoplamientos para suavizar las distribuciones condicionales dominantes (reemplazando mensajes cruzados por nativos).
• Teoremas de Berry-Esseen en la Frontera: Se analizan las tasas de convergencia cuando los parámetros críticos tienden a cero, conectando los límites de Poisson con los Gaussianos.

3. Contribuciones Clave y Resultados Principales

A. Teorema de Límite Lévy-Khintchine General (Teorema 3.1)

El resultado central establece que, bajo el experimento de mezcla de vecinos, la estadística normalizada $S_n$ converge débilmente a un par $(G, J)$:

• $G \sim \mathcal{N}(0, \Sigma)$: Un vector Gaussiano en el espacio tangente dominante $M$. La covarianza $\Sigma$ es una combinación convexa de las covarianzas de los bloques dominantes.
• $J$: Un vector aleatorio de tipo Poisson Compuesto en el espacio cociente $M^\perp$, independiente de $G$.
• Estructura de la Hipótesis Alternativa: Bajo la hipótesis alternativa (vecina), la distribución límite es $(G, J + \Delta)$, donde $\Delta = \Pi_J(\mu_1 - \mu_0)$ es un desplazamiento determinista en el espacio cociente.
  • Nota crucial: Si los conjuntos dominantes se superponen ($D_0 \cap D_1 \neq \emptyset$), el desplazamiento $\Delta$ puede colapsar a cero, haciendo que las distribuciones límite sean idénticas ($P_\infty = Q_\infty$), aunque la privacidad finita pueda no ser cero.

B. Convergencia de la Curva de Privacidad

El paper demuestra la convergencia de la curva de privacidad $\delta_{Q_n \| P_n}(\varepsilon)$ hacia la curva del experimento límite $\delta_{Q_\infty \| P_\infty}(\varepsilon)$ en varios regímenes:

1. Régimen Interior: Cuando la proporción de usuarios de cada grupo es estrictamente positiva.
2. Régimen de Frontera Débil: Cuando un grupo es pequeño pero su tamaño tiende a infinito ($k_n \to \infty, k_n/n \to 0$).
3. Régimen de Frontera Fuerte Regular: Cuando el grupo minoritario es acotado ($O(1)$) y su bloque dominante está "absorbido" por el mayoritario o es un solo punto.

C. Obstáculos y Tasas de Convergencia

• Obstáculo de Frontera Fuerte (Proposición 6.1): Se demuestra que sin condiciones estructurales adicionales, la distribución límite proyectada no determina la curva de privacidad completa. Un bloque minoritario acotado puede retener una geometría interna que es invisible en el límite débil (donde $\Delta=0$) pero visible en pruebas exactas de histograma, manteniendo una privacidad finita positiva.
• Tasa Óptima $O(n^{-1/2})$: Se prueba que la tasa de convergencia para el experimento híbrido completo es agudamente $O(n^{-1/2})$ en general (debido a la comparación binomial-Bernoulli de los bloques dominantes).
• Condición de Compatibilidad (Teorema 7.3): Se identifica una condición bajo la cual la tasa se mejora a $O(n^{-1})$: cuando las leyes de división cruzada (cuando un usuario de un grupo cae en el dominio del otro) coinciden asintóticamente con las leyes nativas dominantes.

D. Teorema de Frontera Berry-Esseen (Sección 8)

Se establece que el experimento de desplazamiento Poisson crítico converge al experimento de desplazamiento Gaussiano a una tasa $O(c)$ en distancia de Le Cam cuando el parámetro crítico $c \downarrow 0$. Esto conecta suavemente los regímenes de Parte II con el régimen Gaussiano de Parte I.

4. Significado e Impacto

1. Unificación de la Teoría: Este trabajo completa la teoría de universalidad para el modelo de mezcla con alfabetos finitos. Proporciona una "capa Lévy-Khintchine" precisa que unifica los regímenes Gaussiano, Poisson y Compuesto-Poisson bajo una sola geometría de cociente.
2. Geometría de la Privacidad: Revela que la privacidad en el modelo de mezcla no depende solo de la magnitud del ruido, sino de la geometría de la intersección entre los soportes de los randomizadores locales. La superposición de dominantes puede anular el desplazamiento determinista en el límite, pero no necesariamente garantiza privacidad perfecta en el caso finito.
3. Límites de la Aproximación: El artículo pone límites claros a la utilidad de los límites asintóticos simples. Muestra que en ciertos regímenes de frontera, la aproximación Gaussiana o Poisson proyectada es insuficiente para predecir la privacidad exacta, requiriendo un análisis de la geometría interna de los bloques minoritarios.
4. Aplicabilidad: Los resultados son fundamentales para el diseño y análisis de protocolos de privacidad diferencial en aplicaciones reales (como encuestas, aprendizaje federado) donde los alfabetos son finitos y las distribuciones de datos pueden ser altamente concentradas o desbalanceadas.

En resumen, el artículo proporciona el marco matemático definitivo para entender cómo la estructura de los datos y la geometría de los randomizadores locales dictan los límites fundamentales de la privacidad en el modelo de mezcla, yendo más allá de las aproximaciones puramente Gaussianas o Poissonianas para ofrecer una teoría híbrida completa.