Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

Resumen Técnico: Coeficientes de Dobrushin de Mecanismos Privados Más Allá de la Privacidad Diferencial Local

Planteamiento del Problema
El artículo aborda las limitaciones del uso de la Privacidad Diferencial Local (LDP, por sus siglas en inglés) como la única métrica para cuantificar la privacidad en núcleos de Markov discretos (mecanismos de privacidad). Aunque la LDP es ampliamente adoptada, los autores señalan dos problemas principales:

1. Excesiva restrictividad: En aplicaciones estadísticas como la estimación de parámetros, lograr garantías de LDP estrictas (un $\epsilon$ pequeño) puede conducir a una degradación extrema en el rendimiento de la estimación (alto riesgo minimax).
2. Comportamiento contraintuitivo con probabilidades cero: La definición estándar de LDP produce un costo de privacidad infinito si un mecanismo asigna probabilidad cero a cualquier salida para un dato de entrada dado ($K_{Y|X=x}(y) = 0$). Esto trata a mecanismos con una aleatorización significativa (por ejemplo, $K_1$ en el ejemplo del artículo) de manera idéntica a mapeos de identidad o mecanismos triviales (por ejemplo, $K_2$) si ambos contienen entradas de cero, fallando al distinguir entre comportamientos "ruidosos" y "deterministas" en términos de filtración de privacidad.

Para abordar estos problemas, los autores investigan los coeficientes de Dobrushin (coeficientes de contracción de la distancia de Variación Total) para mecanismos que satisfacen la Filtración Máxima Puntual (PML, por sus siglas en inglés) en lugar de la LDP estricta. La PML es una adaptación puntual de la filtración máxima que depende de la distribución de los datos $P_X$. Los autores analizan específicamente mecanismos donde la distribución de entrada $P_X$ tiene una masa de probabilidad mínima acotada por debajo de cero por una constante $c > 0$ (es decir, $\min_x P_X(x) \geq c$). Este marco permite el análisis de mecanismos con asignaciones de probabilidad cero que, de otro modo, serían considerados "infinitamente privados" (o infinitamente filtrados) bajo la LDP.

Metodología
El artículo emplea herramientas de la teoría de la información para derivar límites sobre la contracción de las $f$-divergencias a través de mecanismos de privacidad.

• Definiciones: Los autores definen $(\epsilon, c)$-PML como una restricción donde la PML está acotada por $\epsilon$ para todas las distribuciones de entrada en el conjunto $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$. Esto generaliza la LDP, ya que la LDP corresponde al límite cuando $c \to 0$.
• Coeficientes de Contracción: El objeto central de estudio es el coeficiente de Dobrushin $\eta_{TV}(\epsilon, c)$, definido como el supremo de la contracción de la distancia de Variación Total (TV) sobre todos los núcleos que satisfacen $(\epsilon, c)$-PML.
• Reducción a Salidas Binarias: Los autores demuestran que para encontrar el coeficiente de Dobrushin máximo, es suficiente considerar mecanismos con espacios de salida binarios ($|Y|=2$). Esto simplifica significamente el problema de optimización.
• Desigualdades: La derivación utiliza la desigualdad de Binette (una generalización de la desigualdad inversa de Pinsker) para extender los límites de TV a las $f$-divergencias generales (como la Entropía Relativa y la divergencia de Hellinger).

Contribuciones Clave y Resultados

1. Límites Alcanzables en los Coeficientes de Dobrushin:
   El artículo deriva un límite superior ajustado para el coeficiente de Dobrushin $\eta_{TV}(\epsilon, c)$ para cualquier núcleo que satisfaga $(\epsilon, c)$-PML. El límite viene dado por:
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   donde $N$ es el tamaño del alfabeto de entrada.

• Análisis de Regímenes: Los autores muestran que si $\epsilon \geq \log(2/Nc)$, el coeficiente de contracción es 1 (no ocurre contracción). Si $\epsilon < \log(2/Nc)$, el coeficiente es estrictamente menor que 1, lo que indica una contracción inducida por la privacidad.
• Recuperación de LDP: A medida que $c \to 0$, el límite recupera el resultado conocido para $\epsilon$-LDP: $\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$.
• Construcción de Mecanismos: El artículo proporciona construcciones explícitas de mecanismos (específicamente mecanismos de salida binaria) que alcanzan estos límites, demostrando que los límites son alcanzables.

2. Extensión a $f$-Divergencias Generales:
   Utilizando la desigualdad de Binette, los autores extienden los límites de TV a las $f$-divergencias generales. Derivan desigualdades de procesamiento de datos fuertes (SDPIs) para la Entropía Relativa y la divergencia de Hellinger bajo restricciones de $(\epsilon, c)$-PML. Estos límites dependen del factor de contracción de TV y de las razones extremas de las distribuciones de salida.

3. Aplicación al Riesgo Minimax:
   Los límites derivados se aplican a la estimación de riesgo minimax privada. Utilizando el método de dos puntos de Le Cam y la propiedad de tensorización de las $f$-divergencias, los autores muestran que la complejidad de muestra requerida para alcanzar un cierto nivel de riesgo aumenta por un factor proporcional al inverso del coeficiente de Dobrushin privado. Específicamente, si el coeficiente es 1, la complejidad de muestra coincide con el entorno no privado; si es menor que 1, el tamaño de muestra efectivo se reduce.

Significancia y Reivindicaciones
El artículo afirma proporcionar un marco más matizado para analizar mecanismos de privacidad que la LDP por sí sola. Al introducir el parámetro $c$, los autores pueden cuantificar la filtración de privacidad para mecanismos que contienen entradas de probabilidad cero, las cuales son excluidas o tratadas patológicamente bajo la LDP estándar.

• Límites más Ajustados: Para mecanismos que satisfacen LDP, los límites propuestos son más ajustados o más adaptables que los resultados previos cuando la distribución de entrada tiene una masa mínima $c$ conocida.
• Más allá de la LDP: El marco extiende el análisis de los coeficientes de contracción a toda la clase de núcleos discretos, incluyendo aquellos que no satisfacen ninguna garantía de LDP finita.
• Interpretación Operacional: Los resultados vinculan los coeficientes de contracción teóricos directamente con la degradación del rendimiento de la estimación estadística, ofreciendo una herramienta para cuantificar el "costo" de la privacidad en términos de aumento de riesgo o complejidad de muestra.

Los autores enfatizan que su trabajo recupera los resultados existentes de LDP como un caso especial, ofreciendo al mismo tiempo una interpolación continua entre las restricciones de distribución uniforme y el régimen completo de LDP, abordando así la naturaleza "excesivamente restrictiva" de la LDP en contextos estadísticos específicos.