Preserving Target Distributions With Differentially Private Count Mechanisms

Resumen Técnico: Preservación de Distribuciones Objetivo con Mecanismos de Conteo Privados Diferencialmente

1. Planteamiento del Problema

En el análisis de datos poblacionales, la información a menudo se organiza en tablas de conteo (donde cada fila representa una categoría y su valor es el número de individuos). Existe una tensión entre publicar estos datos para investigación y proteger la privacidad individual mediante Privacidad Diferencial (DP).

El problema central identificado por los autores es que los mecanismos estándar de DP (como Laplace, Geométrico o Gaussiano) están diseñados para minimizar el error en conteos individuales (precisión de conteo), pero a menudo distorsionan la distribución global de los conteos.

• Pregunta de distribución: Muchas preguntas de política pública no dependen de categorías específicas, sino de la forma de la distribución (ej. "¿Qué fracción de los vuelos tiene cero escoltas aéreas?" o "¿Qué porcentaje de empresas tienen más de 2 mujeres en su junta directiva?").
• Sesgo: Los mecanismos estándar introducen sesgos estadísticos en la distribución (por ejemplo, inflando artificialmente el número de ceros), lo que hace que las respuestas a preguntas basadas en la distribución sean inexactas.
• Inconsistencia: Crear dos productos de datos separados (uno para conteos y otro para distribuciones) rompe la consistencia estadística, un requisito fundamental para el análisis integrado.

El objetivo es diseñar un mecanismo unificado que produzca una tabla de conteos privatizada que sea precisa tanto para preguntas basadas en categorías como para preguntas basadas en la distribución de los conteos.

2. Metodología: Marco de Dos Etapas

Los autores proponen un marco de trabajo de dos etapas para privatizar tablas de conteos, equilibrando tres criterios de rendimiento: precisión de distribución, precisión de conteo y tiempo de ejecución.

Etapa 1: Privatizador de Distribución

• Objetivo: Generar una estimación privada ($z$) de la verdadera distribución de conteos ($\zeta$) sin revelar la distribución real.
• Innovación: Introducen el Mecánico Laplace Cíclico (Cyclic Laplace Mechanism).
  • A diferencia del Laplace estándar que añade ruido independiente a cada bin, este mecanismo añade ruido correlacionado cíclicamente ($L_i - L_{i+1}$).
  • Esto preserva mejor la estructura de la distribución (especialmente la suma acumulada) y reduce el error de distribución en comparación con métodos generales de histogramas.

Etapa 2: Algoritmo Constructor

• Objetivo: Construir un mecanismo de conteo (matriz de transición $T$) que tenga a $z$ como su punto fijo (es decir, si la distribución de entrada es $z$, la distribución de salida esperada también es $z$).
• Teoría Matemática:
  • Definen el conjunto de mecanismos válidos como un poliedro convexo ($F$) restringido por la privacidad y el punto fijo.
  • Introducen el concepto de $\epsilon$-escalas ($\epsilon$-scales): vectores de probabilidad donde la restricción de privacidad es "activa" (se cumple con igualdad) para cada par de posiciones adyacentes.
  • Demuestran que cualquier mecanismo en $F$ puede representarse como una combinación cónica de estas $\epsilon$-escalas.
  • Desarrollan un poliedro de representación ($R_F$) que mapea las matrices de transición a coeficientes de escalas, permitiendo caracterizar los puntos extremos del espacio de soluciones.

Algoritmos Propuestos:

1. Constructor Heurístico (Algoritmo 1): Un algoritmo greedy que construye la matriz de transición columna por columna utilizando escalas de un solo pico (single-peaked scales).
   • Ventaja: Complejidad temporal $O(n^2)$, lo que lo hace escalable para grandes $n$ (número de conteos posibles), a diferencia de la programación lineal estándar que es impráctica para $n$ grandes.
2. Constructor Óptimo No Fijo (Algoritmo 2): Una línea base que minimiza el error de conteo sin la restricción de punto fijo, adaptando resultados de trabajos previos (Ghosh et al.) para un marco de dos etapas.

3. Contribuciones Clave

1. Mecanismo de Privatización de Distribución: El Cyclic Laplace Mechanism, que supera a los mecanismos de histograma existentes en la preservación de la forma de la distribución.
2. Teoría de Mecanismos con Punto Fijo: Una descripción algebraica compacta de los mecanismos de conteo privados con punto fijo utilizando $\epsilon$-escalas y poliedros de representación. Esto proporciona una nueva intuición sobre la estructura de estos mecanismos.
3. Algoritmos Eficientes:
   • Un constructor heurístico que encuentra un punto extremo del poliedro de soluciones en tiempo polinomial ($O(n^2)$).
   • Un constructor óptimo no fijo eficiente para comparación.
4. Análisis Empírico: Una evaluación exhaustiva de las compensaciones (trade-offs) entre precisión de distribución, precisión de conteo y tiempo de ejecución.

4. Resultados Experimentales

Los autores evaluaron sus métodos en tres conjuntos de datos (conteos sintéticos, homicidios por condado y profesores en escuelas) bajo diferentes presupuestos de privacidad ($\epsilon$).

• Precisión de Distribución:
  • La inclusión de la restricción de punto fijo mejora drásticamente la precisión de la distribución.
  • En escenarios de bajo presupuesto de privacidad (ej. $\epsilon_t = 0.48$), el error de distribución (medido por distancia de Wasserstein) se redujo hasta un 94% en comparación con las líneas base sin punto fijo.
• Precisión de Conteo:
  • Como era de esperar, imponer la restricción de punto fijo aumenta ligeramente el error de conteo individual (al restringir el espacio de soluciones a un subconjunto estricto).
  • Sin embargo, el aumento es moderado (a menudo unos pocos puntos porcentuales), lo que se considera un costo aceptable dado el beneficio en la distribución.
• Tiempo de Ejecución:
  • Los métodos de programación lineal estándar (Simplex, Punto Interior) son demasiado lentos para $n$ grandes.
  • El constructor heurístico propuesto es altamente eficiente, logrando tiempos de ejecución comparables a las líneas base no fijas, incluso para $n=2000$ (menos de 10 segundos).
• Asignación de Presupuesto:
  • Proponen una "regla empírica" para dividir el presupuesto de privacidad total ($\epsilon_t$) entre la etapa de distribución ($\epsilon_1$) y la de conteo ($\epsilon_2$), basada en una función exponencial que depende del valor de $\epsilon_t$.

5. Significado e Impacto

Este trabajo es significativo porque:

• Cierra la brecha de utilidad: Permite que los datos privatizados sean útiles para un tipo de preguntas (basadas en distribución) que anteriormente requerían productos de datos separados o sufrían de grandes sesgos.
• Viabilidad práctica: Demuestra que es posible preservar la distribución objetivo sin sacrificar excesivamente la precisión de los conteos ni la eficiencia computacional, gracias a la teoría de $\epsilon$-escalas y los algoritmos heurísticos.
• Aplicabilidad: Ofrece un marco robusto para agencias gubernamentales (como el censo), organizaciones humanitarias y departamentos de salud que necesitan publicar estadísticas agregadas manteniendo la integridad de las tendencias poblacionales y la privacidad individual.

En conclusión, el estudio demuestra que un enfoque de punto fijo en la privatización de conteos ofrece un compromiso favorable, permitiendo una alta fidelidad en la distribución de los datos con pérdidas mínimas en la precisión individual y la velocidad de procesamiento.