How Well Can Differential Privacy Be Audited in One Run?

1. El Problema: Limitaciones de la Auditoría de Privacidad Diferencial (DP)

La Privacidad Diferencial (DP) es el estándar para proteger datos en el aprendizaje automático. Sin embargo, las garantías teóricas (límites superiores de los parámetros de privacidad, $\epsilon$) a menudo son demasiado laxas o incorrectas debido a errores en la implementación o el análisis. Por ello, se han desarrollado métodos de auditoría empírica para establecer límites inferiores reales de la privacidad.

• Auditoría Clásica: Requiere ejecutar el algoritmo cientos o miles de veces con pares de conjuntos de datos que difieren en un solo elemento. Es precisa (asintóticamente ajustada) pero computacionalmente prohibitiva.
• Auditoría en Una Ejecución (ORA - One-Run Auditing): Propuesta recientemente por Steinke et al., permite auditar múltiples elementos simultáneamente en una sola ejecución del algoritmo. Aunque es eficiente y válida (los límites inferiores son correctos), la pregunta abierta es: ¿Qué tan cerca está el límite inferior de ORA del verdadero parámetro de privacidad?

El artículo investiga si ORA puede ser asintóticamente ajustada (es decir, si sus límites convergen al verdadero $\epsilon$) y, de no ser así, identifica las barreras fundamentales que impiden esta precisión.

2. Metodología y Marco Teórico

Los autores utilizan un marco de auditoría basada en conjeturas (guessing-based auditing).

• El Juego: El auditor tiene un vector de pares de opciones para cada entrada del conjunto de datos. Se selecciona aleatoriamente un conjunto de datos real basado en bits aleatorios ($S \in \{-1, 1\}^n$). El algoritmo $M$ se ejecuta una vez, produciendo una salida $O$.
• El Adivino (Guesser): Basándose en $O$, el auditor intenta adivinar los bits aleatorios $S$. Puede abstenerse de adivinar en ciertos puntos (valor 0).
• Métrica de Eficacia: Se define como la relación esperada entre aciertos y conjeturas tomadas ($E[V/R]$). La precisión de la auditoría depende de esta eficacia.

Los autores analizan la eficacia óptima de ORA utilizando conceptos de Privacidad Distribucional (DDP) y sus variantes relajadas, comparándolas con la definición estándar de DP.

3. Contribuciones Clave

El trabajo identifica y formaliza tres brechas fundamentales (gaps) que limitan la eficacia de ORA, incluso con un adversario óptimo:

A. Las Tres Brechas Fundamentales

1. Privacidad No-Peor Caso para Elementos (Non-worst-case privacy for elements):

   • DP se define por el peor caso de pérdida de privacidad de cualquier elemento.
   • En ORA, para obtener suficientes conjeturas, el auditor debe hacer conjeturas sobre elementos que no están experimentando su peor caso de pérdida de privacidad en esa ejecución específica.
   • Ejemplo: El algoritmo "Name and Shame" expone un elemento aleatorio. La mayoría de los elementos no se ven afectados, diluyendo la eficacia global de la auditoría.

2. Salidas No-Peor Caso (Non-worst-case outputs):

   • DP considera el peor caso sobre todas las posibles salidas.
   • ORA ejecuta el algoritmo una sola vez. Si la salida resultante es "segura" (no revela mucha información), la auditoría fallará en detectar la verdadera privacidad, incluso si el algoritmo es inherentemente inseguro en otros casos.
   • Ejemplo: El algoritmo "All or Nothing" solo expone datos con probabilidad $p$. Si $p$ es bajo, la auditoría en una sola ejecución probablemente verá una salida segura.

3. Interferencia (Interference Gap):

   • Este es el hallazgo más crítico. En ORA, el auditor debe adivinar múltiples elementos simultáneamente sin conocer los valores de los otros elementos (a diferencia del modelo de amenaza de DP, donde el adversario conoce todo menos un elemento).
   • Si la salida del algoritmo es una agregación de múltiples entradas (ej. una suma o XOR), la incertidumbre sobre los otros elementos impide aislar el efecto de uno solo.
   • Ejemplo: El algoritmo XOR. Sin conocer los otros bits, la salida no revela nada sobre un bit individual específico, reduciendo la eficacia al azar (50%), aunque el algoritmo no sea privado.

B. Caracterización Teórica

• Teorema 5.2: Caracteriza la eficacia óptima de ORA. Demuestran que la eficacia está acotada por la Privacidad Distribucional Promedio-Elemento Promedio-Caso (AE-AC-DDP), que es estrictamente menor que el $\epsilon$ real de DP debido a las tres brechas mencionadas.
• Teorema 5.3 (Condición de Ajuste Asintótico): ORA es asintóticamente ajustada si y solo si el número de elementos que experimentan una pérdida de privacidad distribucional cercana al peor caso ($\epsilon$) tiende a infinito.
  • Esto implica que ORA funciona bien para algoritmos locales (donde cada elemento se procesa independientemente, como Local Randomized Response), pero falla para algoritmos que agregan información globalmente.

C. Nuevos Enfoques para Mitigar la Interferencia

Para abordar la brecha de interferencia, especialmente en DP-SGD (el algoritmo estándar para aprendizaje privado), proponen:

1. Múltiples Elementos por Coordenada: En lugar de asignar un solo elemento de auditoría por dimensión del modelo (como hacían trabajos anteriores), proponen asignar múltiples elementos. Esto aumenta el número de conjeturas potenciales, aunque aumenta la interferencia. Los experimentos muestran un punto óptimo donde el beneficio de más conjeturas supera el costo de la interferencia.
2. Adaptive ORA (AORA): Una variante donde el adivino puede usar los valores reales de los elementos que ya ha adivinado correctamente para mejorar las conjeturas de los elementos restantes.
   • Valididad: Demuestran teóricamente que AORA sigue siendo válida (los límites inferiores son correctos) a pesar de la información adicional.
   • Eficacia: AORA reduce drásticamente la brecha de interferencia, permitiendo una auditoría mucho más precisa en algoritmos como DP-SGD y Count-In-Sets.

4. Resultados Empíricos

Los autores validan sus teorías mediante experimentos en DP-SGD:

• Efecto de la Interferencia: Confirman que a medida que aumenta el número de elementos por coordenada, la eficacia de ORA estándar disminuye debido a la interferencia, mientras que la estimación de $\epsilon$ se vuelve menos precisa.
• Superioridad de AORA: En comparación con ORA estándar, AORA produce límites inferiores más altos (más ajustados) y es capaz de mantener una alta eficacia incluso con muchos elementos por coordenada.
• Algoritmos Sintéticos: En algoritmos como XOR y Count-In-Sets, ORA estándar falla completamente (eficacia cercana a 0.5), mientras que AORA logra una eficacia perfecta o cercana a ella, demostrando su capacidad para resolver la interferencia.

5. Significado e Impacto

Este trabajo es fundamental para el campo de la privacidad en el aprendizaje automático por varias razones:

1. Límites Fundamentales: Establece que la auditoría en una sola ejecución tiene límites teóricos inherentes que no pueden superarse simplemente mejorando el algoritmo de ataque; depende de la estructura del algoritmo auditado.
2. Interpretación de Resultados: Advierte que un límite inferior bajo obtenido por ORA no necesariamente significa que el algoritmo sea inseguro, sino que podría ser un artefacto de las brechas de interferencia o de salidas no peores.
3. Mejora de la Práctica: Introduce AORA y la estrategia de múltiples elementos por coordenada como métodos superiores para auditar algoritmos modernos como DP-SGD, ofreciendo una herramienta más potente y precisa para validar implementaciones de privacidad en la industria.
4. Validación de Valididad: Proporciona la prueba formal de que la adaptividad (usar información previa para conjeturas futuras) no viola la validez estadística de la auditoría, abriendo la puerta a métodos de auditoría más sofisticados.

En resumen, el paper demuestra que, aunque ORA es eficiente, su precisión está limitada por la interferencia entre elementos. Sin embargo, mediante la adaptación (AORA) y una selección estratégica de datos, es posible mitigar estas limitaciones y obtener auditorías mucho más cercanas a la realidad de la privacidad del algoritmo.