Computationally tractable robust differentially private mean estimation

Resumen Técnico: Estimación de la Media con Privacidad Diferencial Robusta y Computacionalmente Tratable

Planteamiento del Problema
El artículo aborda el desafío de estimar la media de una distribución de alta dimensión bajo dos restricciones simultáneas: privacidad diferencial (DP) y robustez ante valores atípicos (outliers). El escenario involucra una muestra de $n$ vectores en $\mathbb{R}^d$ extraídos de una distribución elíptica desconocida $\nu = EC(\mu, \Sigma, F)$, la cual está sujeta a una contaminación de $\eta$. En este modelo, un adversario reemplaza hasta $\lfloor \eta n \rfloor$ observaciones con valores arbitrarios que pueden depender de la muestra original. El objetivo es estimar la media poblacional $\mu$ cumpliendo con la privacidad diferencial de concentración cero (zCDP) y manteniendo la precisión estadística a pesar de distribuciones de cola pesada y contaminación adversaria.

Los métodos existentes en este dominio enfrentan compromisos significativos. Muchos estimadores privados robustos dependen de técnicas computacionalmente intensivas como MCMC (Monte Carlo por Cadenas de Markov), relajaciones de suma de cuadrados o optimización basada en gradientes, lo que los hace impracticables para datos de alta dimensión. Otros, aunque eficientes, suelen depender de privacidad diferencial aproximada o carecen de garantías de robustez bajo nociones de privacidad fuertes como la DP pura o de concentración cero. Además, muchos enfoques actuales requieren el ajuste de parámetros que son difíciles de interpretar o que escalan mal con la dimensión.

Metodología: La Media del Globo (Balloon Mean)
Los autores proponen un nuevo estimador, la media del globo, que evita las subrutinas de optimización complejas en favor de operaciones algebraicas lineales simples. El algoritmo opera de forma iterativa, alternando entre dos pasos:

1. Actualización de la Media (Proyección y Promedio con Ruido): Dada una estimación actual del centro $\tilde{\mu}_{m-1}$ y un radio $\tilde{R}_{m-1}$, el algoritmo proyecta todos los puntos de datos sobre la bola de Mahalanobis $B_{\tilde{R}_{m-1}, \Sigma}(\tilde{\mu}_{m-1})$. Luego, calcula la media muestral de estas proyecciones y añade ruido gaussiano calibrado según la sensibilidad de la proyección (que depende del radio). Esto produce una nueva estimación privada de la media $\tilde{\mu}_m$.
2. Actualización del Globo (Expansión Privada del Radio): El algoritmo "infla" la bola centrada en la nueva estimación $\tilde{\mu}_m$ hasta que contenga una fracción objetivo $\tau_m$ de los datos. Esto se logra mediante una versión privada del algoritmo AboveThreshold. El algoritmo consulta una secuencia de radios definidos por una cuadrícula geométrica ($R_{min} + \beta^i - 1$) y cuenta de forma privada cuántos puntos caen dentro de cada radio. Se detiene en el primer radio donde el conteo con ruido supera un umbral con ruido correspondiente a la fracción objetivo $\tau_m$.

El proceso se repite durante $M$ iteraciones. La estimación final es la media de las proyecciones sobre el globo final. El método depende de unos pocos parámetros de ajuste interpretables: el radio inicial, el factor de expansión de la cuadrícula $\beta$, el número de iteraciones $M$ y la fracción objetivo $\tau$.

Contribuciones Clave

1. Innovación Algorítmica: La introducción de la media del globo, un estimador computacionalmente eficiente que localiza iterativamente la media identificando privadamente las bolas de Mahalanobis que contienen el grueso de los datos. Evita MCMC, suma de cuadrados y el descenso de gradiente.
2. Garantías Teóricas: El artículo proporciona límites de error de muestra finita para la media del globo tanto en modelos de cola pesada (donde solo existe el segundo momento) como en modelos elípticos contaminados adversariamente. El análisis asume una matriz de covarianza $\Sigma$ conocida (aunque los autores señalan que se puede sustituir por una estimación privada robusta de $\Sigma$).
3. Privacidad y Complejidad: El estimador satisface la privacidad diferencial de concentración cero ($\rho$-zCDP), con una extensión natural a la DP pura. La complejidad computacional es $O(d^3 + nd^2 + Mnd + Mn \log n)$, que se reduce a $O(nd^2)$ bajo supuestos estándar ($n > d$ y $M < \log n$).

Resultados Teóricos
El principal resultado teórico (Teorema 4.4) establece un límite superior en el error de Mahalanobis $|\tilde{\mu}_M - \mu|_\Sigma$. Con alta probabilidad, el error escala como:
$$\sqrt{\frac{d}{n(\rho_- \wedge 1)}} + \sqrt{d\eta} + \sqrt{\frac{\log(\dots)}{n}}$$
donde $\rho_-$ es el presupuesto de privacidad mínimo asignado por iteración.

• Configuración de Cola Pesada ($\eta=0$): El estimador alcanza la tasa de convergencia minimax óptima salvo por factores logarítmicos.
• Contaminación Adversaria ($\eta > 0$): El error incluye un término que escala como $\sqrt{d\eta}$. Los autores señalan que, aunque los límites inferiores existentes sugieren que podría lograrse una dependencia de $\sqrt{\eta}$ (independiente de $d$), la dependencia actual de $\sqrt{d}$ es probablemente estructural debido a la incapacidad del algoritmo para manejar explícitamente contaminantes colocados a lo largo de una única dirección en cáscaras de alta dimensión. Reconocen esta brecha, pero enfatizan que ningún algoritmo existente logra simultáneamente la dependencia óptima de la contaminación, una privacidad fuerte y la eficiencia computacional.

Evaluación Empírica
Simulaciones extensas a través de dimensiones ($d \in \{2, \dots, 128\}$), tamaños de muestra y presupuestos de privacidad ($\rho \in \{0.01, 1\}$) demuestran el rendimiento del método:

• Robustez: La media del globo supera significativamente a otros estimadores privados computacionalmente tratables (como COINPRESS, estimadores M de Huber privados y medias de instancia óptima) en entornos contaminados y de cola pesada.
• Sensibilidad de Parámetros: El método presenta una baja sensibilidad a la suposición inicial de la media, al radio inicial y al tamaño de la cuadrícula $\beta$. El parámetro $\tau$ actúa como un control de robustez; valores más pequeños de $\tau$ (que excluyen más datos) mejoran el rendimiento en entornos contaminados, pero pueden aumentar ligeramente el error en entornos limpios.
• Conteo de Iteraciones: El error se estabiliza tras 3–4 iteraciones, lo que sugiere que $M=4$ es suficiente para la mayoría de las aplicaciones prácticas.

Significado y Reivindicaciones
El artículo posiciona a la media del globo como una solución práctica al "trilema" de la robustez, la privacidad y la tratabilidad computacional. Los autores afirman que, si bien el método puede no alcanzar la dependencia teórica óptima de la contaminación para entornos adversarios (debido a limitaciones estructurales), ofrece una combinación única de:

1. Simplicidad Computacional: Es implementable en altas dimensiones sin optimizaciones complejas.
2. Privacidad Fuerte: Satisface zCDP, una noción de privacidad más fuerte que la DP aproximada utilizada a menudo en entornos robustos.
3. Optimalidad Estadística: Logra tasas minimax en el entorno de cola pesada y proporciona un rendimiento robusto en entornos contaminados donde otros métodos eficientes fallan.

Los autores concluyen que la media del globo es una herramienta viable para la estimación de la media con privacidad en escenarios del mundo real que involucran datos de alta dimensión, potencialmente de cola pesada y contaminados, ofreciendo un equilibrio entre las garantías teóricas y la viabilidad práctica.