Better Privacy Guarantees for Larger Groups

Resumen Técnico: Mejores Garantías de Privacidad para Grupos Más Grandes

Declaración del Problema
Este artículo aborda un problema abierto planteado por Pujol y Desfontaines [2023] relativo al diseño de histogramas privados para grupos fijos y disjuntos. Los mecanismos estándar de privacidad diferencial suelen añadir ruido de una magnitud fija a cada conteo, proporcionando una privacidad absoluta uniforme pero resultando en errores relativos significativamente menores para grupos grandes en comparación con los pequeños. La cuestión central es si se puede "gastar" este excedente de precisión de manera diferente: permitiendo que el error en un grupo escale proporcionalmente con su conteo ($x_i$) para proporcionar garantías de privacidad más fuertes (un presupuesto de privacidad más pequeño) para los miembros de grupos más grandes.

El artículo investiga esto bajo el modelo de adyacencia "añadir o eliminar uno" (add-or-remove-one). El objetivo es encontrar un mecanismo donde el presupuesto de privacidad $v(n)$ dependa únicamente del conteo del grupo $n$, sea no creciente y satisfaga la privacidad diferencial de concentración cero (zCDP) por grupo dependiente del conteo. Esto requiere acotar la divergencia de Rényi en ambas direcciones para cada orden $\alpha > 1$ entre conjuntos de datos vecinos.

Un obstáculo técnico crítico identificado es la condición de contorno en cero. La formulación original requería que el error absoluto esperado fuera estrictamente menor que $r x_i$. Para $x_i = 0$, esto implica $E|\hat{x}_i| < 0$, lo cual es imposible. Además, relajar la desigualdad a $\leq$ manteniendo una divergencia de Rényi de dos lados finita a través del borde $0 \leftrightarrow 1$ conduce a una contradicción (forzando que la salida en el conteo 1 sea determinista, violando el límite de error).

Metodología y Formulación Reparada
Para resolver el problema de la condición de contorno, los autores proponen un "requisito de utilidad reparado":
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
Esto mantiene el objetivo de error relativo para todos los conteos positivos e introduce una tolerancia absoluta fija en cero, haciendo que el problema sea factible.

El artículo emplea dos enfoques metodológicos principales:

1. Factibilidad (Límite Superior): Los autores especializan un marco existente de "transformación con desplazamiento" (Finley et al. [2026]). Transforman el espacio de conteo mediante un logaritmo con un desplazamiento $c$ (es decir, $\log(x_i + c)$), añaden ruido gaussiano de varianza fija y aplican un desplazamiento determinista antes de la exponencial y el recorte (clipping).

   • Innovación Clave: A diferencia de los mecanismos log-normales estándar que utilizan un desplazamiento de $-\sigma^2/2$ para asegurar la ausencia de sesgo en la media, este mecanismo utiliza un desplazamiento de $-\sigma^2$. Este desplazamiento específico se elige para minimizar el error multiplicativo absoluto esperado, lo cual se alinea con la métrica de utilidad del artículo.
   • Mecanismo de Privacidad: Al trabajar en el espacio logarítmico con varianza igual, el mecanismo asegura que la divergencia de Rényi entre conteos adyacentes sea finita para todos los órdenes $\alpha$, evitando la "obstrucción de cola" donde las varianzas desiguales causan una divergencia infinita en una dirección.

2. Imposibilidad (Límite Inferior): Los autores demuestran que ningún mecanismo que satisfaga el requisito de utilidad reparada y los requisitos de zCDP dependientes del conteo puede lograr una tasa de decaimiento del presupuesto de privacidad más rápida que el inverso del cuadrado del conteo.

   • Argumento de Dos Conteos: Una prueba entre dos conteos específicos establece el exponente $n^{-2}$.
   • Argumento de Muchos Conteos: Utilizando una variable aleatoria de "desplazamiento oculto" y argumentos de teoría de la información (relacionando el error absoluto esperado con la información mutua), los autores derivan un límite inferior más ajustado sobre el coeficiente principal del presupuesto de privacidad.

Resultados Clave

• Tasa Asintótica Óptima: Para cualquier $0 < r < 1$ fijo, el presupuesto de privacidad óptimo $v(n)$ decae como $\Theta_r(n^{-2})$.

  • Límite Superior: El mecanismo gaussiano de log-desplazado logra $v(n) = O_r(n^{-2})$. Específicamente, cuando $n \to \infty$, $v(n) \approx \frac{1}{2\sigma^2 n^2}$.
  • Límite Inferior: Cualquier mecanismo que satisfaga los requisitos debe tener $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$. Esto confirma que la tasa de inverso del cuadrado es intrínseca y no un artefacto de la construcción.

• Coeficientes Principales: El artículo reduce la brecha entre los mejores límites superior e inferior para el coeficiente principal $C^*$ en el límite de $r$ pequeño y $n$ grande:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  La relación entre estos límites es aproximadamente de 2.995, lo que indica que los límites están dentro de un factor de tres.

• Fallo de la Gaussiana de Varianza Desigual: El artículo demuestra que un mecanismo ingenuo que libera $N(n, r^2 n^2)$ (ruido gaussiano con varianza proporcional al cuadrado del conteo) falla la definición de zCDP. Aunque tiene la escala de error correcta, las varianzas desiguales entre conteos adyacentes causan que la divergencia de Rényi en una dirección sea infinita para órdenes $\alpha$ suficientemente altos, violando el requisito de "todos los órdenes" de zCDP.

• Caso Trivial: En $r=1$, una liberación independiente de los datos (por ejemplo, siempre devolver $0.5$) satisface el criterio reparado con pérdida de privacidad cero ($v \equiv 0$).

Significancia y Reivindicaciones
El artículo afirma proporcionar el primer mecanismo-independiente de prueba de que la tasa de inverso del cuadrado es óptima para esta formulación específica de privacidad por grupo.

• Factibilidad: Establece que la formulación "reparada" es resoluble y proporciona un mecanismo concreto y composable (gaussiano de log-desplazado) que logra la tasa óptima.
• Optimidad: Demuestra que ningún mecanismo, independientemente de su complejidad o estructura de correlación, puede mejorar la tasa de decaimiento $n^{-2}$.
• Precisión: Al emplear argumentos de información de muchos conteos, el artículo ajusta significativamente los límites del coeficiente principal en comparación con los análisis previos de dos conteos, reduciendo la incertidumbre a un factor de menos de tres.

Los autores declaran explícitamente que determinar el valor exacto del coeficiente óptimo $C^*$ sigue siendo una cuestión abierta. También señalan que sus resultados se aplican a grupos fijos y disjuntos; los grupos superpuestos o dependientes de los datos requerirían un análisis de sensibilidad separado. El mecanismo está sesgado (debido al desplazamiento $-\sigma^2$) pero está calibrado específicamente para minimizar el error absoluto esperado, no para ser insesgado.