Resumen Técnico: Funciones de Compensación para DP-SGD con Muestreo Basado en Mezcla Aleatoria

Enunciado del Problema

El Descenso de Gradiente Estocástico con Privacidad Diferencial (DP-SGD) es el mecanismo estándar para entrenar modelos de aprendizaje profundo bajo restricciones de privacidad. Si bien el marco de Privacidad Diferencial $f$ ($f$-DP) proporciona la caracterización más ajustada posible de las garantías de privacidad a través de funciones de compensación entre las tasas de falsos positivos y falsos negativos, los análisis existentes se han centrado predominantemente en el muestreo de Poisson (donde los puntos de datos se incluyen independientemente en mini-lotes con una probabilidad fija).

Sin embargo, las implementaciones prácticas de DP-SGD y la optimización estocástica suelen emplear mezcla aleatoria, donde el conjunto de datos se permuta una vez por época y se divide en mini-lotes de tamaño fijo. Esta discrepancia entre el algoritmo analizado (Poisson) y el algoritmo desplegado (mezcla) ha dejado las garantías de privacidad de los sistemas del mundo real caracterizadas de manera imprecisa. Trabajos anteriores sobre DP-SGD con mezcla han proporcionado únicamente cotas superiores para la función de compensación (cotas inferiores para la pérdida de privacidad) mediante eventos adversarios explícitos o evaluaciones numéricas, careciendo de expresiones cerradas y transparentes. Además, resultados recientes de imposibilidad indican que para multiplicadores de ruido bajos ($\sigma \le 1/\sqrt{2 \ln M}$), la función de compensación está acotada de manera demostrable lejos de la diagonal ideal de adivinanza aleatoria ($1-a$), pero el comportamiento en el régimen de alto ruido seguía siendo una pregunta abierta que requería un análisis ajustado y en forma cerrada.

Metodología

Los autores derivan un análisis ajustado y en forma cerrada de la función de compensación para DP-SGD con mezcla aleatoria dentro del marco $f$-DP. La metodología procede a través de las siguientes etapas:

1. Reducción Adversaria: El problema se reduce a un problema de prueba de hipótesis escalar. Bajo el modelo de adversario de peor caso (que puede aislar la contribución de un único registro diferente), el adversario observa $M$ rondas. Bajo la hipótesis nula ($H_0$), todas las observaciones son ruido puro $N(0, 1)$. Bajo la hipótesis alternativa ($H_1$), exactamente una ronda (elegida uniformemente al azar por la permutación de mezcla) contiene una observación desplazada $N(1/\sigma, 1)$, mientras que el resto permanece como ruido.
2. Prueba de Razón de Verosimilitud: Por el lema de Neyman-Pearson, la prueba óptima umbraliza la razón de verosimilitud, lo que se reduce a umbralizar el promedio muestral de variables lognormales $Y_j = \exp(X_j/\sigma - 1/(2\sigma^2))$, donde $X_j \sim N(0, 1)$.
3. Análisis No Asintótico (Berry-Esseen): Para una sola época, los autores aplican el teorema de Berry-Esseen para acotar la tasa de convergencia de la media muestral de estas variables lognormales hacia una distribución normal. Esto produce una cota inferior concreta y no asintótica para la función de compensación $f(a)$ en el régimen $\sigma \ge \sqrt{3/\ln M}$. La cota se expresa como $f(a) \ge 1 - a - \delta$, donde $\delta$ es una función explícita del multiplicador de ruido $\sigma$ y del número de rondas $M$.
4. Análisis Asintótico (Desarrollo de Edgeworth): Para mejorar las cotas de Berry-Esseen, que están limitadas por un término de error de $O(1/\sqrt{M})$, los autores introducen una técnica de demostración basada en un desarrollo de Edgeworth de dos términos. Esta generalización del Teorema del Límite Central permite una estimación asintótica más fina de la distribución de la suma de variables lognormales. Este enfoque establece el comportamiento asintótico de la función de compensación cuando $M \to \infty$ con el número de épocas $E$ escalando como $E = c_M^2 M$ donde $c_M \to 0$.

Contribuciones Clave

1. Cota Inferior en Forma Cerrada para una Sola Época: El artículo proporciona la primera cota inferior ajustada y en forma cerrada para la función de compensación de DP-SGD con mezcla en el régimen de alto ruido ($\sigma \ge \sqrt{3/\ln M}$). La cota viene dada por:
   $$f(a) \ge 1 - a - \delta$$
   donde $\delta$ se define explícitamente en términos de $\sigma$ y $M$ (Teorema 4.1). Este resultado es ajustado hasta factores constantes dentro del marco de demostración de Berry-Esseen.
2. Recomendaciones Concretas de Parámetros: Los autores derivan configuraciones específicas de parámetros para privacidad diferencial significativa. Para una sola época ($E=1$) con $\sigma=1$ y $\delta=10^{-2}$, muestran que un tamaño de conjunto de datos de $N \approx 1.14 \times 10^7$ dividido en $M \approx 1.14 \times 10^6$ rondas es suficiente. Esto demuestra que es posible lograr privacidad significativa en configuraciones de aprendizaje federado con conjuntos de datos grandes y una sola época.
3. Caracterización Asintótica de DP Gaussiana: Utilizando desarrollos de Edgeworth, el artículo establece que para $\sigma$ fijo, a medida que $M \to \infty$ y $E = c_M^2 M$ con $c_M \to 0$, la función de compensación compuesta $E$ veces converge uniformemente a la diagonal de adivinanza aleatoria ($1-a$). Esto mejora la dependencia del número de épocas de la penalización lineal $O(E)$ sugerida por la composición ingenua a una separación asintótica de $O(\sqrt{E})$ (Corolario 5.3).
4. Comparación con Muestreo de Poisson: Los autores comparan sus resultados asintóticos con el asintótico correspondiente del muestreo de Poisson. Descubren que en el límite de bajo ruido ($\sigma \to 0$), la mezcla aleatoria es asintóticamente un factor de $\sqrt{2}$ más cercana a la diagonal ideal de adivinanza aleatoria que el muestreo de Poisson, mientras que los dos regímenes se vuelven equivalentes en el límite de alto ruido ($\sigma \to \infty$).

Resultados

• Validez del Régimen: El análisis es válido para $\sigma \ge \sqrt{3/\ln M}$. Este régimen es complementario al resultado de imposibilidad de Ertan y van Dijk [12], que muestra que para $\sigma < 1/\sqrt{2 \ln M}$, la función de compensación está acotada lejos de $1-a$. Juntos, estos resultados mapean el panorama de privacidad de DP-SGD con mezcla.
• Cotas de Composición:
  • No Asintóticas: Iterar la cota de una sola época produce $f^{\otimes E}(a) \ge (1-\delta)^E - a$, lo que implica una dependencia lineal de $E$ para la pérdida de privacidad.
  • Asintóticas: El análisis basado en Edgeworth sugiere una dependencia más ajustada, donde la separación de la diagonal escala como $O(\mu \sqrt{E})$ en lugar de $O(\mu E)$, siempre que $E$ escale sub-linealmente con $M$.
• Implicaciones Prácticas: El artículo identifica el régimen de una sola época como el "punto óptimo práctico" para DP-SGD con mezcla. En escenarios de aprendizaje federado donde los clientes participan en pocas épocas, es posible lograr garantías de privacidad significativas ($\delta \approx 0.01$) con tamaños de conjunto de datos realistas. Por el contrario, el artículo destaca una "explosión multi-época" donde aumentar $E$ bajo la cota de composición lineal hace rápidamente impráctico el tamaño de conjunto de datos $N$ requerido (por ejemplo, requiriendo $N \sim 10^{11}$ para $E=100$).

Significado y Afirmaciones

El artículo afirma proporcionar un análisis ajustado y en forma cerrada que resuelve la discrepancia entre los algoritmos analizados en la literatura (Poisson) y los desplegados en la práctica (mezcla aleatoria). Al derivar cotas transparentes e interpretables, los autores permiten a los practicantes leer directamente los requisitos de parámetros sin depender de herramientas numéricas opacas.

La importancia del trabajo radica en:

1. Conectar Teoría y Práctica: Validar que la mezcla aleatoria, el estándar en los marcos de aprendizaje automático, admite un análisis riguroso de privacidad que a menudo es más favorable que el muestreo de Poisson en regímenes de bajo ruido.
2. Definir el Panorama de Privacidad: Complementar los resultados de imposibilidad existentes para definir los umbrales de ruido precisos requeridos para una privacidad significativa en DP-SGD con mezcla.
3. Guiar la Selección de Parámetros: Ofrecer fórmulas concretas para seleccionar $M$, $N$ y $\sigma$ para lograr presupuestos de privacidad específicos, particularmente relevantes para aplicaciones de aprendizaje federado.

Los autores mantienen una postura modesta respecto al trabajo futuro, señalando que, aunque los resultados asintóticos sugieren una dependencia mejorada de $\sqrt{E}$ para múltiples épocas, derivar una demostración concreta y en forma cerrada de esta dependencia (en contraste con el límite asintótico) sigue siendo un problema abierto. Además, se identifica como una dirección para futuras investigaciones hacer explícitas las secuencias $\delta_M$ y $\gamma_M$ en el desarrollo de Edgeworth para obtener una cota concreta multi-época.