Resumen Técnico: Filtros de Privacidad f-Diferencial: Validez y Soluciones Aproximadas

Declaración del Problema

El artículo aborda el desafío de contabilizar la pérdida de privacidad bajo composición totalmente adaptativa en privacidad diferencial (DP). En entornos totalmente adaptativos, la elección de los mecanismos y sus parámetros de privacidad puede depender del historial de salidas anteriores, un escenario común en algoritmos iterativos como el descenso de gradiente estocástico con privacidad diferencial (DP-SGD).

Aunque existen filtros de privacidad (reglas de parada) para $(\epsilon, \delta)$-DP y Privacidad Diferencial de Rényi (RDP), la validez de los filtros basados en Privacidad f-Diferencial (f-DP) sigue sin estar clara. La f-DP caracteriza el alcance completo de la prueba de hipótesis adversaria mediante funciones de compromiso y recupera la $(\epsilon, \delta)$-DP a través de funciones de compromiso por partes lineales. Se sabe que los productos tensoriales de f-DP proporcionan los resultados de composición más ajustados para entornos no adaptativos. La pregunta central es si un filtro "natural" de f-DP, que rastrea el producto tensorial acumulativo de funciones de compromiso y se detiene cuando se cruza una curva prescrita, sigue siendo válido bajo adaptatividad total.

Metodología y Marco Teórico

1. Análisis de la Validez del Filtro Natural de f-DP

Los autores investigan el filtro "natural" de f-DP, definido como continuar mientras el producto tensorial de las funciones de compromiso realizadas $f_1 \otimes \dots \otimes f_t$ permanezca por encima de una curva de presupuesto $f_B$.

• Construcción de un Contraejemplo: El artículo demuestra que este enfoque es fundamentalmente inválido en el entorno totalmente adaptativo. Incluso si los mecanismos individuales son válidos y la función de compromiso compuesta nunca supera el umbral a lo largo de un historial específico, la composición adaptativa puede violar el presupuesto.
• Mecanismo de Fallo: El fallo surge porque el producto adaptativo de funciones de compromiso depende de la realización específica de las salidas, lo cual determina la selección de los mecanismos subsiguientes. Si una familia de funciones de compromiso futuras potenciales contiene un "punto de calibración" (donde las funciones se intersecan), la selección adaptativa puede explotar esto para lograr un perfil de pérdida de privacidad estrictamente peor (función de compromiso más baja) que el límite inferior del producto tensorial de las ramas individuales. Este fenómeno ocurre incluso para mecanismos gaussianos muestreados, el caballo de batalla del aprendizaje automático privado.

2. Caracterización de las Condiciones de Validez

Los autores establecen condiciones necesarias y suficientes para que el filtro natural de f-DP sea válido:

• Cadenas de Blackwell: El filtro es válido si y solo si la familia de funciones de compromiso disponibles (y sus productos tensoriales) forma una cadena de Blackwell. Una familia es una cadena de Blackwell si cualesquiera dos funciones en la familia están totalmente ordenadas (una domina a la otra punto a punto).
• Implicación: Esto explica por qué RDP y GDP (Privacidad Diferencial Gaussiana) admiten filtros simples y válidos: sus garantías son de valor escalar (o forman cadenas de Blackwell como las funciones de compromiso gaussianas $G_\mu$ donde $\mu$ es un escalar), asegurando la comparabilidad. En contraste, las funciones de compromiso generales de f-DP no siempre están ordenadas de Blackwell, lo que conduce al fallo del filtro natural.

3. Teorema del Límite Central (CLT) Totalmente Adaptativo

Para evitar la invalidez de los filtros exactos de f-DP, el artículo demuestra un Teorema del Límite Central (CLT) de f-DP totalmente adaptativo.

• Enfoque: Los autores modelan la pérdida de privacidad como un proceso estocástico de Variables Aleatorias de Pérdida de Privacidad (PLRV). Utilizando una variante de martingala del límite de Berry–Esseen (Fan, 2019), demuestran que bajo condiciones de regularidad específicas (medias y varianzas condicionales acotadas, y momentos de orden superior controlados), la pérdida de privacidad acumulada converge a una distribución gaussiana.
• Resultado: Esta convergencia permite la construcción de filtros GDP aproximados. En lugar de rastrear la función de compromiso completa, se pueden rastrear las medias y varianzas condicionales acumulativas de las PLRV. El error de esta aproximación se cuantifica mediante el término de error del CLT $\Delta$.

4. Filtro GDP Aproximado para Mecanismos Gaussianos Muestreados

Como una instancia concreta, los autores derivan aproximaciones de momentos en forma cerrada para mecanismos gaussianos muestreados en dos regímenes asintóticos:

• Muestreo bajo ($q \ll 1$): La media y la varianza de la PLRV se aproximan utilizando expansiones de Taylor.
• Muestreo alto ($q \approx 1$): Se derivan aproximaciones similares para el límite donde la tasa de muestreo se acerca a 1.
• Algoritmo: Proponen un algoritmo que rastrea estas aproximaciones de momentos para hacer cumplir un presupuesto. Este filtro evita rastrear la función de compromiso completa, ofreciendo una alternativa computacionalmente eficiente a la contabilidad basada en FFT numérica.

Resultados Clave

1. Invalidez de los Filtros Naturales: El filtro natural de f-DP es inválido para composiciones totalmente adaptativas de mecanismos gaussianos muestreados. Contraejemplos explícitos muestran que la composición adaptativa puede violar el presupuesto incluso cuando todas las ramas no adaptativas lo satisfacen.
2. Caracterización de la Validez: El filtro natural es válido si y solo si la familia de funciones de compromiso forma una cadena de Blackwell. Esto proporciona un límite teórico preciso para cuándo es posible la contabilidad basada en funciones de compromiso bajo adaptatividad total.
3. Aproximación Basada en CLT: El CLT totalmente adaptativo establece que las pérdidas de privacidad acumuladas convergen a distribuciones gaussianas. Esto permite la construcción de filtros GDP aproximados que son demostrablemente válidos en regímenes asintóticos.
4. Comparación de Rendimiento:
   • En regímenes asintóticos ($q \ll 1$ y $q \approx 1$), el filtro GDP aproximado propuesto produce garantías de privacidad estrictamente más ajustadas que la contabilidad RDP totalmente adaptativa (específicamente el filtro de RDP de orden único $(1, B)$).
   • El artículo señala que, aunque se sabe que la contabilidad basada en RDP es holgada, esta holgura se demuestra que proviene de la reducción con pérdida a las divergencias de Rényi y no de una barrera fundamental en la composición adaptativa.
   • Sin embargo, la aproximación basada en CLT se sabe que es optimista (subestimando la pérdida de privacidad) en tasas de muestreo realistas y moderadas (por ejemplo, $q=0.1$), una limitación compartida con las aproximaciones CLT no adaptativas.

Significado y Afirmaciones

El artículo afirma resolver una pregunta abierta central sobre los filtros de f-DP:

• Resolución Teórica: Muestra definitivamente que la extensión intuitiva de la composición estándar de f-DP a filtros adaptativos falla, aclarando por qué las nociones basadas en divergencia (RDP) tienen éxito donde las nociones basadas en funciones de compromiso (f-DP general) fallan sin restricciones estructurales.
• Contribución Constructiva: Al demostrar el CLT totalmente adaptativo, el artículo proporciona una metodología general para construir filtros GDP aproximados para cualquier familia de mecanismos donde los momentos de las PLRV puedan aproximarse analíticamente.
• Implicación Práctica: Para mecanismos gaussianos muestreados, el filtro propuesto ofrece una alternativa en forma cerrada y eficiente a la contabilidad numérica. En regímenes de muestreo extremo, proporciona garantías que son estrictamente más ajustadas que los filtros basados en RDP más avanzados actuales, demostrando que la "holgura" en RDP es un artefacto de la representación y no un costo inherente de la adaptatividad.

Los autores permanecen modestos respecto a las limitaciones, reconociendo que el enfoque basado en CLT es optimista en tasas de muestreo realistas y que cerrar la brecha en tasas moderadas sigue siendo un desafío abierto. También señalan que la validez del filtro natural está restringida a condiciones estructurales específicas (cadenas de Blackwell) que no se cumplen generalmente por mecanismos de f-DP arbitrarios.