Resumen Técnico: Contabilidad de Privacidad sin Muestreo para Mecanismos de Matriz bajo Asignación Aleatoria

Enunciado del Problema

El artículo aborda el desafío de calcular garantías de privacidad deterministas y ajustadas para el entrenamiento de modelos con privacidad diferencial que utiliza mecanismos de factorización de matrices combinados con asignación aleatoria (también conocido como el esquema de "bolas en contenedores" o muestreo de iteraciones equilibradas).

Si bien la amplificación de la privacidad mediante muestreo es una técnica estándar para reducir el ruido en el Descenso de Gradiente Estocástico con Privacidad Diferencial (DP-SGD), el esquema de "bolas en contenedores" se prefiere sobre el muestreo de Poisson para el entrenamiento a gran escala debido a su eficiencia computacional y cobertura uniforme de los datos. Sin embargo, cuando se combina con la factorización de matrices (que introduce ruido correlacionado entre iteraciones para mejorar la utilidad), los métodos existentes de contabilidad de privacidad enfrentan limitaciones significativas:

1. Dependencia de Monte Carlo: Los enfoques recientes (por ejemplo, Choquette-Choo et al., 2025) dependen del muestreo de Monte Carlo para estimar los parámetros de amplificación. Este enfoque es computacionalmente costoso, particularmente en regímenes de alta privacidad donde el número de muestras requerido escala inversamente con $\delta$ (por ejemplo, demostrar que $(\epsilon, 10^{-8})$-DP es $10^5$ veces más costoso que $(\epsilon, 10^{-3})$-DP).
2. Garantías Probabilísticas: Estos métodos basados en muestreo a menudo producen garantías que solo se cumplen con alta probabilidad o requieren que el mecanismo emplee abstención aleatoria, en lugar de proporcionar cotas deterministas de $(\epsilon, \delta)$-DP.
3. Intratabilidad Computacional: La distribución de la pérdida de privacidad para los mecanismos de matriz bajo asignación aleatoria implica mezclas de alta dimensión, lo que hace que la evaluación exacta de la divergencia de hockey-stick sea intratable sin muestreo.

Metodología

Los autores proponen dos procedimientos de contabilidad distintos, sin muestreo, que calculan cotas deterministas explícitamente, aprovechando la estructura del esquema de asignación aleatoria y las correlaciones introducidas por la factorización de matrices.

1. Contador de Divergencia de Rényi (Programación Dinámica)

Este método calcula una cota superior sobre la divergencia de Rényi, que luego se convierte en $(\epsilon, \delta)$-DP utilizando teoremas de conversión estándar.

• Insight Central: La distribución de la pérdida de privacidad para la dirección "eliminar" (donde un punto de datos se elimina del conjunto de datos) puede expresarse como una suma sobre una matriz de Gram $G$ derivada de la matriz de estrategia $C$.
• Reducción de Complejidad: Para matrices generales, se ha demostrado que calcular esta suma es #P-completa. Sin embargo, para matrices estructuradas (por ejemplo, matrices banda donde la matriz de estrategia $C$ tiene ancho de banda $p$), la matriz de Gram $G$ hereda una estructura cíclicamente banda.
• Algoritmo: Los autores formulan un enfoque de programación dinámica para calcular la suma exactamente para matrices banda de ancho $p$.
  • Complejidad: El tiempo de ejecución se reduce de exponencial $O(2^\alpha)$ (en el orden $\alpha$) a polinomial $O(b p \alpha^{2p})$, donde $b$ es el número de lotes por época.
  • Truncamiento: Para matrices que no son estrictamente banda pero tienen entradas de decaimiento rápido (por ejemplo, matrices inversas banda), el método trunca la matriz de Gram y añade un término de corrección aditivo computable para asegurar que la cota permanezca válida.
• Dirección "Añadir": Se deriva una cota superior analítica ajustada separada para la dirección "añadir" utilizando la desigualdad media aritmética-media geométrica (AM-GM).

2. Contador de Composición Condicional

Este método aborda el régimen de "$\epsilon$ pequeño" (alta privacidad) donde las fórmulas de conversión de Rényi pueden ser laxas. Supera la interdependencia de los pasos causada por la correlación del ruido y los conteos de participación fijos.

• Concepto: En lugar de asumir pasos independientes, el método utiliza composición condicional. Identifica resultados "buenos" donde las distribuciones condicionales del mecanismo en el paso $n$ están dominadas por un par de distribuciones fijas y factorizables $(P^{(n)}, Q^{(n)})$.
• Eventos "Malos": El método contabiliza los resultados "malos" (donde falla la dominancia) acotando su probabilidad $\delta_E$. La pérdida de privacidad total es la composición de los pasos independientes más $\delta_E$.
• Criterio de Dominancia: Los autores derivan un criterio basado en funciones de riesgo inverso de los pesos de mezclas gaussianas. Demuestran que si la función de riesgo inverso posterior es puntualmente menor que la función de riesgo inverso de una distribución objetivo, se cumple la dominancia.
• Cotas de Cola: Para determinar los parámetros de las distribuciones dominantes, los autores derivan cotas analíticas de cola sobre la pérdida de privacidad de mezclas gaussianas ternarias. Utilizan una familia variacional de distribuciones para estrechar estas cotas, optimizando sobre parámetros de temperatura para minimizar la desviación estándar de la cota de cola.
• Eficiencia: Si bien la evaluación inicial es $O(N^2 b^2)$, las evaluaciones posteriores para diferentes multiplicadores de ruido $\sigma$ pueden amortizarse a $O(N b^2)$, haciéndolo eficiente para la calibración del mecanismo.

Contribuciones Clave

1. Contabilidad Determinista: El artículo introduce los primeros métodos sin muestreo para calcular garantías deterministas de $(\epsilon, \delta)$-DP para mecanismos de matriz bajo asignación aleatoria, eliminando la necesidad de estimación de Monte Carlo.
2. Mejora de Complejidad para DP-SGD: Para el caso especial de ruido no correlacionado (DP-SGD estándar), el contador de Rényi propuesto mejora la complejidad computacional de la contabilidad exacta bajo asignación aleatoria de exponencial $O(2^\alpha)$ a polinomial $O(b \alpha^2)$, superando significativamente a los métodos exactos anteriores.
3. Generalización a Ruido Correlacionado: El marco se extiende a mecanismos de matriz arbitrarios banda y no banda (incluyendo Raíz Cuadrada Banda, Inversa Banda y Toeplitz Lineal Amortiguado), manejando las complejas correlaciones entre pasos inherentes a estos mecanismos.
4. Ajuste Dual de Regímenes: La combinación del contador de Rényi (fuerte en el régimen de baja privacidad/gran $\epsilon$) y el contador de composición condicional (más ajustado en el régimen de alta privacidad/pequeño $\epsilon$) proporciona una solución de contabilidad integral.

Resultados

Los autores evalúan sus métodos contra el contador de Monte Carlo más avanzado a través de varios mecanismos de matriz (DP-SGD, BSR, BISR, BandMF, BandInvMF, BLT) y configuraciones (época única y múltiple).

• Precisión: En el régimen de baja privacidad ($\epsilon \ge 2$), el contador de Rényi coincide estrechamente con la referencia de Monte Carlo. En el régimen de alta privacidad ($\epsilon \le 1$), el contador de composición condicional produce cotas más ajustadas, permitiendo multiplicadores de ruido calibrados $\sigma$ más pequeños en comparación con las estimaciones de Monte Carlo.
• Robustez: El rendimiento se mantiene a través de diferentes anchos de banda ($p$) y números de lotes ($b$).
• Utilidad: Los experimentos en CIFAR-10 demuestran que los multiplicadores de ruido derivados de estas garantías sin muestreo preservan los beneficios de utilidad de usar ruido correlacionado sobre ruido no correlacionado.
• Tiempo de Ejecución: Los métodos superan la dependencia $O(\delta^{-1})$ del muestreo de Monte Carlo. Si bien el contador de composición condicional tiene un costo inicial más alto para $N$ grande, su costo amortizado para la calibración es significativamente menor que el de Monte Carlo para presupuestos de privacidad estrictos.

Significado y Afirmaciones

El artículo afirma proporcionar la primera contabilidad de privacidad sin muestreo para mecanismos con gradientes y participaciones correlacionados. Su importancia radica en:

• Habilitar Garantías Deterministas: Elimina la dependencia de cotas probabilísticas o abstención aleatoria, que a menudo son poco prácticas o teóricamente más débiles para sistemas de producción.
• Escalabilidad: Al reducir la complejidad de la contabilidad exacta de Rényi para asignación aleatoria de exponencial a polinomial, hace viable la contabilidad de privacidad precisa para ejecuciones de entrenamiento a gran escala donde el muestreo de Monte Carlo sería computacionalmente prohibitivo.
• Calibración Práctica: La capacidad de calcular eficientemente cotas ajustadas en un amplio rango de $\epsilon$ y $\delta$ facilita una mejor calibración de los multiplicadores de ruido, mejorando directamente la compensación utilidad-privacidad en el aprendizaje profundo con privacidad diferencial.

Los autores reconocen limitaciones, señalando que la complejidad del contador de Rényi sigue siendo exponencial en el ancho de banda $p$ (aunque polinomial en $\alpha$), y que el método de composición condicional depende de una partición gruesa de resultados que puede ser pesimista. Sugieren que el trabajo futuro podría explorar particiones más finas y una inferencia variacional más eficiente para estrechar aún más las cotas.