Missing Mass for Differentially Private Domain Discovery

Resumen Técnico: Missing Mass for Differentially Private Domain Discovery

1. El Problema: Descubrimiento de Dominio Privado

En el análisis de datos modernos (consultas, reseñas, historiales de compra), el dominio de los datos (el conjunto de todos los ítems posibles) suele ser desconocido a priori o inmensamente grande. El objetivo es realizar un análisis útil preservando la privacidad diferencial (DP).

El problema central abordado es el descubrimiento de dominio: dado un conjunto de datos donde cada usuario posee un subconjunto de ítems de un dominio global desconocido, el objetivo es extraer un subconjunto informativo de ítems que represente fielmente el dominio, sin revelar información sensible sobre los usuarios individuales.

Los desafíos específicos incluyen:

• Unión de Conjuntos (Set Union): Seleccionar tantos ítems como sea posible que aparezcan en los datos de los usuarios.
• Selección Top-k: Identificar los $k$ ítems más frecuentes.
• Conjunto de Golpeo $k$-hitting ($k$-hitting set): Seleccionar $k$ ítems que maximicen el número de usuarios cuyos subconjuntos intersectan con la selección.

El problema crítico es que la mayoría de los algoritmos existentes carecen de garantías de utilidad teóricas (es decir, no se puede cuantificar matemáticamente qué tan bien funcionan en términos de precisión y privacidad).

2. Metodología y Enfoque

Los autores proponen un cambio de paradigma en la métrica de evaluación: en lugar de medir la utilidad por la cardinalidad (número de ítems recuperados), utilizan el concepto de "Missing Mass" (Masa Perdida).

• Definición de Missing Mass ($MM$): Es la fracción de la frecuencia total de los ítems que no fueron recuperados. Minimizar la masa perdida significa capturar la mayor parte de la "masa" (frecuencia) de los datos.
• Mecanismo de Gaussiano Ponderado (WGM): El núcleo de la metodología es el uso del Weighted Gaussian Mechanism (WGM), un algoritmo escalable que:
  1. Realiza un muestreo de los ítems de cada usuario para limitar la contribución individual.
  2. Construye un histograma ponderado.
  3. Añade ruido gaussiano a las frecuencias ponderadas.
  4. Filtra los ítems cuya frecuencia ruidosa supera un umbral $T$.

Estrategia General:
Para problemas más complejos (Top-k y $k$-hitting set) con dominio desconocido, los autores proponen un algoritmo meta (Algoritmo 2) que divide el presupuesto de privacidad ($\epsilon$) en dos mitades:

1. Fase 1: Ejecutar WGM para descubrir un dominio aproximado $D$.
2. Fase 2: Ejecutar un algoritmo privado estándar de dominio conocido (como el mecanismo exponencial de "peeling") sobre el dominio $D$ para resolver el problema específico.

3. Contribuciones Clave

1. Garantías de Utilidad para la Unión de Conjuntos:

   • Demuestran que el WGM tiene una garantía de masa perdida $\ell_1$ casi óptima para datos que siguen una distribución Zipfiana (común en la realidad, donde unos pocos ítems son muy frecuentes y muchos son raros).
   • Proveen una garantía de masa perdida $\ell_\infty$ libre de distribución (no requiere suposiciones Zipfianas), acotando la frecuencia máxima de cualquier ítem perdido.

2. Extensión a Top-k y $k$-Hitting Set:

   • Utilizan las garantías de masa perdida $\ell_\infty$ del WGM para derivar nuevas garantías de utilidad para las variantes de dominio desconocido de los problemas Top-k y $k$-hitting set.
   • Proban que sus métodos logran aproximaciones cercanas a las óptimas, con errores que dependen de parámetros del problema ($\epsilon, \delta, k$) y la estructura de los datos.

3. Límites Inferiores (Lower Bounds):

   • Establecen límites inferiores teóricos que demuestran que ciertas dependencias en sus upper bounds (como la dependencia lineal en $k/\epsilon$) son inevitables para cualquier algoritmo privado que respete la restricción de solo devolver ítems presentes en los datos de entrada.

4. Validación Empírica:

   • Evalúan sus métodos en seis conjuntos de datos reales (Reddit, Amazon, MovieReviews, Steam, etc.).
   • Demuestran que sus métodos basados en WGM son competitivos o superan a las mejores técnicas existentes (como los mecanismos de política de Gopi et al. y Carvalho et al.), ofreciendo una utilidad teórica garantizada y una eficiencia computacional superior.

4. Resultados Principales

• Teóricos:

  • Para datos Zipfianos $(C, s)$, el error de masa perdida del WGM decae a medida que aumenta el número total de ítems $N$ y el parámetro de Zipf $s$.
  • Para Top-k, el error de masa perdida es del orden de $\tilde{O}\left(\frac{k}{N} \left( \frac{\max |W_i|}{\epsilon \sqrt{q^*}} + \frac{\sqrt{k} \log M}{\epsilon} \right)\right)$.
  • Para $k$-hitting set, el algoritmo logra una aproximación de $(1 - 1/e)$ del óptimo, con un término de error aditivo controlado.

• Empíricos:

  • Unión de Conjuntos: El WGM logra una masa perdida dentro del 5% de los mecanismos de política más complejos, pero con una escalabilidad mucho mayor.
  • Top-k: En conjuntos de datos pequeños, el método propuesto supera consistentemente a los baselines de dominio limitado (como el de Durfee & Rogers), especialmente a medida que aumenta $k$.
  • $k$-Hitting Set: El método propuesto iguala o supera a algoritmos que asumen conocimiento público del dominio, demostrando que descubrir el dominio de forma privada no degrada significativamente la utilidad final.

5. Significado e Impacto

Este trabajo es fundamental por varias razones:

1. Cierre de la Brecha Teórica: Es, hasta donde se sabe, el primer trabajo que proporciona garantías de utilidad absolutas (no relativas a otros algoritmos) para la unión de conjuntos bajo privacidad diferencial.
2. Marco General: Introduce el uso de la "masa perdida" como una métrica robusta para evaluar la calidad del descubrimiento de dominios, superando las limitaciones de contar simplemente el número de ítems.
3. Aplicabilidad Práctica: Proporciona una metodología modular (WGM + Algoritmo de Dominio Conocido) que puede aplicarse a diversos problemas de optimización combinatoria en entornos privados, facilitando su implementación en sistemas industriales reales.
4. Validación en Datos Reales: Confirma que los supuestos teóricos (como la distribución Zipfiana) se cumplen en datos del mundo real y que los algoritmos propuestos son prácticos y eficientes.

En resumen, el paper establece un nuevo estándar para el análisis de dominios desconocidos bajo privacidad diferencial, combinando rigor teórico con una fuerte validación empírica, demostrando que es posible obtener dominios útiles y representativos sin sacrificar la privacidad de los usuarios.