Resumen Técnico: Tasas Óptimas para Pruebas de Hipótesis con Privacidad Diferencial mediante Valores-e

Enunciado del Problema

Este trabajo aborda el problema fundamental de la prueba de hipótesis simple bajo las restricciones de Privacidad Diferencial (DP) central. Específicamente, los autores investigan la prueba de un conjunto de datos $X \sim P^n$ (hipótesis nula) frente a $X \sim Q^n$ (hipótesis alternativa) utilizando valores-e.

En el contexto clásico, el rendimiento de una prueba se mide por su potencia (tasa de verdaderos positivos). En el marco de los valores-e, el rendimiento se mide mediante la potencia-e, definida como $\mathbb{E}_Q[\log E]$, donde $E$ es una variable aleatoria no negativa que satisface $\mathbb{E}_P[E] \le 1$. La pregunta central es: ¿Cuál es la máxima potencia-e alcanzable para un valor-e $\varepsilon$-DP al probar $P$ frente a $Q$?

Los autores consideran dos escenarios:

1. Escenario por Lotes: Todos los $n$ puntos de datos están disponibles simultáneamente.
2. Escenario Secuencial: Los datos llegan uno por uno, y el analista elige un tiempo de parada $N$ de forma adaptativa. El objetivo es minimizar el tiempo de parada esperado $\mathbb{E}_Q[N]$ requerido para alcanzar un nivel específico de evidencia estadística.

Aunque existe trabajo previo sobre pruebas de hipótesis con privacidad diferencial en el contexto de la teoría de decisiones (salidas binarias) y sobre valores-e bajo DP local, este artículo se centra en valores-e de DP central, un escenario donde solo existe trabajo previo limitado (específicamente Csillag y Mesquita [10], que estaba restringido a razones de verosimilitud acotadas).

Metodología

1. Caracterización de la Potencia-e Óptima (Escenario por Lotes)

Los autores desacoplan el mecanismo de privacidad de la construcción de la variable-e. Observan que para cualquier mecanismo $\varepsilon$-DP fijo $M$, el post-procesamiento óptimo para crear una variable-e es la razón de verosimilitud de las distribuciones de salida, $dM(Q^n)/dM(P^n)$. Por lo tanto, el problema se reduce a maximizar la divergencia de Kullback-Leibler (KL) entre las distribuciones de salida del mecanismo:
$$R_{\varepsilon}(Q \| P) = \lim_{n \to \infty} \sup_{M \in \varepsilon\text{-DP}} \frac{1}{n} KL(M(Q^n) \| M(P^n))$$

Para resolver esto, los autores introducen una distribución intermedia $\tilde{Q}$. Construyen $\tilde{Q}$ modificando la densidad de $Q$ relativa a $P$ en regiones específicas definidas por la razón de verosimilitud $q(x)/p(x)$:

• Región A (Razón de Verosimilitud Baja): $q(x) < c_1 p(x)$. Aquí, $\tilde{q}(x) = c_1 p(x)$.
• Región B (Razón de Verosimilitud Alta): $q(x) > c_2 p(x)$. Aquí, $\tilde{q}(x) = c_2 p(x)$.
• Región M (Intermedia): $\tilde{q}(x) = q(x)$.

Las constantes $c_1, c_2$ y las regiones se determinan mediante un multiplicador de Lagrange $\lambda^*$ que resuelve una ecuación implícita que garantiza que $\tilde{Q}$ sea una distribución de probabilidad válida. Esta construcción minimiza el funcional $KL(Q' \| P) + \varepsilon \cdot TV(Q', Q)$.

Los autores demuestran que la tasa óptima es exactamente:
$$R_{\varepsilon}(Q \| P) = KL(\tilde{Q} \| P) + \varepsilon \cdot TV(\tilde{Q}, Q)$$

A continuación, construyen una variable-e no privada $E^*$ basada en este $\tilde{Q}$ (específicamente, una razón de verosimilitud recortada) que tiene una sensibilidad logarítmica acotada de $\varepsilon$. Para privatizar esto, proponen una función de fusión $\Lambda_n$ basada en el trabajo de Vovk y Wang, añadiendo ruido Laplaciano con un compensador cuidadosamente calibrado para mantener la propiedad de variable-e mientras se preserva la optimalidad asintótica.

2. Escenario Secuencial y Tiempos de Parada

En el escenario secuencial, los autores definen un proceso-e $\varepsilon$-DP como una secuencia de valores-e generados por un mecanismo $\varepsilon$-DP. Establecen una cota inferior para el tiempo de parada esperado de cualquier proceso de este tipo.

Utilizando un argumento de función potencial que involucra un acoplamiento entre la distribución verdadera $Q$ y la distribución intermedia $\tilde{Q}$, demuestran que para cualquier tiempo de parada $N$:
$$\mathbb{E}_Q[\log E_N] \le \mathbb{E}_Q[N] \cdot R_{\varepsilon}(Q \| P)$$
Esto implica una cota inferior sobre la complejidad de la muestra requerida para lograr una cierta potencia.

Para igualar esta cota, proponen el Algoritmo 1, una "Conversión de Lotes a Proceso-e". Este algoritmo:

• Toma una variable-e no privada con sensibilidad logarítmica acotada.
• Procesa los datos en lotes de tamaño creciente.
• Aplica una función de fusión privatizada (similar al caso por lotes) al final de cada lote.
• Utiliza una relación de recurrencia específica para determinar los tamaños de los lotes, optimizando la compensación entre el tiempo inicial de "arranque" y la relación competitiva a largo plazo.

Contribuciones y Resultados Clave

1. Resultado de Dureza Específica de la Instancia (Teorema 2.2): El artículo proporciona una fórmula explícita y computable para la máxima potencia-e alcanzable bajo $\varepsilon$-DP. Esta tasa se caracteriza por la divergencia KL hacia una distribución intermedia $\tilde{Q}$ más una penalización de variación total.
2. Construcción de Algoritmo Óptimo (Teorema 2.4): Los autores construyen un valor-e $\varepsilon$-DP que alcanza esta tasa óptima asintóticamente. La construcción implica un recorte específico de la razón de verosimilitud seguido de un esquema de privatización que utiliza ruido Laplaciano y un término compensador.
3. Cota Inferior Secuencial (Teorema 3.1): Derivan una cota inferior universal para el tiempo de parada esperado de cualquier proceso-e $\varepsilon$-DP, mostrando que es inversamente proporcional a la tasa óptima de potencia-e $R_{\varepsilon}(Q \| P)$.
4. Algoritmo Secuencial Óptimo (Teorema 3.2): Presentan el Algoritmo 1, que convierte una variable-e no privada en un proceso-e $\varepsilon$-DP. Este algoritmo iguala la cota inferior teórica sobre los tiempos de parada hasta un factor multiplicativo constante (relación competitiva) para todos los tiempos de parada suficientemente grandes.
5. Alternativa Independiente de la Distribución (Apéndice C): Reconociendo que calcular el $\tilde{Q}$ óptimo puede ser intratable para distribuciones complejas, proponen una estadística de "razón de verosimilitud truncada y escalada" (tsLR). Esta estadística independiente de la distribución alcanza una tasa dentro de un factor constante de la tasa óptima.

Validación Experimental

Los autores realizaron experimentos numéricos comparando su Algoritmo 1 contra DP-SPRT (Prueba de Razón de Verosimilitud Secuencial con Privacidad Diferencial) propuesto por Michel et al. [25].

• Configuración: Prueba de $P = \text{Bernoulli}(0.3)$ frente a $Q = \text{Bernoulli}(q)$.
• Métrica: Funciones de Distribución Acumulada (CDF) empíricas de los tiempos de parada.
• Resultado: A través de diversos niveles de privacidad ($\varepsilon$) y distribuciones alternativas ($q$), el proceso-e privado propuesto se detuvo consistentemente antes que DP-SPRT. Cabe destacar que esta mejora en el rendimiento se logró incluso aunque el algoritmo propuesto no hace suposiciones paramétricas sobre los datos, mientras que DP-SPRT está diseñado específicamente para familias exponenciales.

Significado y Afirmaciones

El artículo afirma proporcionar una comprensión completa de los límites fundamentales de la prueba de hipótesis simple mediante valores-e bajo privacidad diferencial central.

• Fundamento Teórico: Al caracterizar la tasa óptima $R_{\varepsilon}(Q \| P)$ y proporcionar un algoritmo que la iguala, el trabajo establece una línea base para lo que es alcanzable en el análisis secuencial que preserva la privacidad.
• Utilidad Práctica: Los algoritmos propuestos requieren menos datos (menores tiempos de parada) que los métodos existentes de última generación (DP-SPRT) en una variedad de escenarios.
• Direcciones Futuras: Los autores sugieren que sus resultados de dureza y técnicas (específicamente el uso de pares menos favorables) pueden servir como base para extender estos resultados a la prueba de hipótesis compuesta y a la estimación DP óptima para instancias, de manera similar a cómo el trabajo fundamental en entornos no privados ha impulsado el progreso en esas áreas. También señalan que extender estos resultados a DP aproximada ($\delta > 0$) sigue siendo una pregunta abierta.