A Maximum Entropy Implementation of Differential Privacy Under Linear Invariants

Resumen Técnico: Una Implementación de Máxima Entropía de la Privacidad Diferencial bajo Invariantes Lineales

Planteamiento del Problema
La privacidad diferencial (DP, por sus siglas en inglés) es el estándar para la privacidad de datos, implementada típicamente mediante la adición de ruido Gaussiano o de Laplace independiente a las consultas de bases de datos. Sin embargo, en aplicaciones como el Censo Decenal de EE. UU., ciertas consultas agregadas (por ejemplo, totales de población a nivel estatal) están sujetas a "invariantes"—restricciones lineales impuestas por ley o política que no pueden ser perturbadas. Los mecanismos estándar de DP, que añaden ruido independiente, violan estas restricciones porque la suma de los términos de ruido independientes rara vez es cero.

Aunque existen técnicas de post-procesamiento para forzar a los agregados a coincidir con los invariantes, tales métodos alteran la distribución del ruido, lo que puede modificar las garantías de privacidad y la interpretación del mecanismo de DP. Además, proyectar el ruido no restringido sobre el espacio de los invariantes a menudo resulta en una solución con menor entropía, reduciendo la utilidad de los datos publicados. El desafío central es diseñar un mecanismo de adición de ruido que:

1. Mantenga las distribuciones marginales especificadas (por ejemplo, Laplace o Gaussiana) al nivel granular.
2. Satisfaga las restricciones de agregación lineal (invariantes) con probabilidad uno.
3. Maximice la entropía del vector de ruido dentro del subespacio restringido para asegurar que el ruido sea "lo más independiente posible" dadas las restricciones.

Metodología
Los autores proponen un mecanismo de Privacidad Diferencial de Agregación Invariante (AI-DP). El enfoque trata tanto al ruido Gaussiano como al de Laplace como mezclas de escalas de distribuciones normales. La metodología procede en tres etapas principales:

1. Formalización del Universo de Datos Invariante:
   Los autores redefinen la estructura de la base de datos vecina para las garantías de DP. En lugar del intercambio de una sola entrada estándar, las bases de datos vecinas en el universo invariante ($D_{Q,A,c}$) deben diferir de una manera que preserve las restricciones lineales $AQ(D) = c$. Esto a menudo requiere intercambiar múltiples entradas simultáneamente. Las garantías de privacidad se evalúan entonces dentro de este universo restringido.

2. Construcción de la Matriz de Correlación vía POCS:
   Para satisfacer las restricciones $AX = 0$ manteniendo marginales específicos, el vector de ruido $X$ se modela como una normal multivariante $N(0, \Sigma)$ donde $\Sigma = DRD$. Aquí, $D$ es una matriz diagonal de escalas (derivada de la distribución de mezcla) y $R$ es una matriz de correlación que satisface $RB = 0$ (donde $B = AD$).
   Encontrar tal $R$ se formula como un Problema de Factibilidad Convexa (CFP): encontrar una matriz en la intersección de tres conjuntos convexos:

• $C_1$: El cono de matrices semidefinidas positivas.
• $C_2$: El subespacio afín de matrices con entradas diagonales unitarias (matrices de correlación).
• $C_3$: El subespacio de matrices donde $RB = 0$.
  Los autores emplean el algoritmo de Proyección Cíclica sobre Conjuntos Convexos (POCS) para encontrar una solución $R$ en esta intersección.

3. Optimización de Máxima Entropía:
   La solución POCS proporciona una matriz de correlación válida, pero no garantiza la máxima entropía. Para satisfacer el requisito de maximizar la entropía (Requisito [R3]), los autores formulan un problema de optimización:
   $$R_{opt} = \min_{R \in C_n} \left[ \text{Tr}(B^T R B) - \tau \log \det(K^T R K) \right]$$
   donde el primer término impone la restricción (idealmente cero) y el segundo término (con el parámetro de ajuste $\tau$) penaliza la baja entropía. Esto se resuelve utilizando un Algoritmo de Gradiente Proyectado.

Contribuciones Clave

• Garantías Teóricas de Privacidad: El artículo deriva garantías de $(\epsilon, \delta)$-DP para el mecanismo propuesto bajo el universo de datos invariante. Demuestra que el mecanismo satisface estas garantías para bases de datos que difieren por entradas que preservan los invariantes.
• Teoría de Matrices de Correlación: El trabajo contribuye con nuevos resultados a la literatura sobre matrices de correlación, específicamente respecto al espacio nulo de las matrices de correlación.
  • Proporciona una condición necesaria y suficiente para la existencia de una matriz de correlación $R$ tal que $RB=0$ para una matriz de restricción de rango-$k$ $B$.
  • Caracteriza el conjunto de soluciones como caras del eliptope (el conjunto de matrices de correlación) e identifica la solución de máximo rango como situada en el interior relativo de este conjunto.
• Marco Algorítmico: El artículo presenta un algoritmo práctico (Algoritmo 1 y 2) para muestrear ruido de mezclas de normales bajo restricciones de igualdad lineal, utilizando POCS y descenso de gradiente proyectado.
• Manejo de Restricciones Jerárquicas: Se muestra que la metodología es adaptable a estructuras jerárquicas anidadas (por ejemplo, bloques $\to$ condados $\to$ estados), asegurando la consistencia en todos los niveles mientras se preservan los invariantes de alto nivel.

Resultados

• Ilustraciones Numéricas:
  • Agregación Simple: Para el caso donde el vector de restricción es un vector de unos (sumando a un total), los autores muestran que una matriz de correlación intraclase específica (rango $n-1$) es la solución única de máximo rango y máxima entropía, eliminando la necesidad de optimización iterativa en este caso específico.
  • Mecanismo de Laplace: Representando el ruido de Laplace como una mezcla de escalas gaussianas, los autores generaron con éxito 100 muestras de ruido distribuido de Laplace que satisfacen una única restricción lineal. Los gráficos Q-Q confirmaron la distribución marginal, y las violaciones de la restricción fueron insignificantes (orden de $10^{-6}$).
  • Convergencia: El algoritmo de gradiente proyectado demostró convergencia en la minimización de la función de pérdida mientras mantenía el término de penalización por entropía.
• Probabilidad de Violación: El artículo analiza la probabilidad de que un vector de restricción aleatorio no sea "balanceado" (una condición requerida para la existencia de una matriz de correlación nuladora). Proporciona un límite de cola que muestra que para vectores con entradas de cola pesada, la probabilidad de inviabilidad es exponencialmente pequeña.

Significancia y Reivindicaciones
Los autores afirman que este trabajo proporciona una manera fundamentada de abordar las restricciones de agregación en la implementación de DP sin sacrificar la interpretación estándar de la privacidad diferencial. Al asegurar que el vector de ruido tenga la máxima entropía dentro de las restricciones, el método minimiza la distorsión de las propiedades estadísticas de los datos más allá de lo necesario para satisfacer los invariantes.

El artículo establece explícitamente que contribuye a la discusión sobre cómo analizar los datos publicados e interpretar la semántica de DP en presencia de invariantes, un vacío identificado en la literatura previa de implementación del censo (Abowd et al., 2022). La metodología se presenta como poseedora de una utilidad general más allá de los datos del censo, aplicable a cualquier entorno que involucre el muestreo de modelos de mezcla normales bajo restricciones de igualdad lineal, como los datos de medidores inteligentes o dispositivos portátiles (wearables).

Los autores mantienen la modestia respecto al alcance, señalando que el presente trabajo se centra en restricciones de igualdad lineal y que se requiere trabajo futuro para abordar sistemas más generales de restricciones de igualdad e desigualdad lineal (por ejemplo, no negatividad). También observan que la prueba teórica relativa al espacio nulo de las matrices de correlación es una solución parcial a una pregunta abierta en ese campo.