DP-SPRT: Differentially Private Sequential Probability Ratio Tests

Resumen Técnico: DP-SPRT: Pruebas de Razón de Probabilidad Secuencial con Privacidad Diferencial

Planteamiento del Problema

Las pruebas de hipótesis secuenciales, específicamente la Prueba de Razón de Probabilidad Secuencial (SPRT) de Wald, son un método fundamental para la toma de decisiones con un mínimo de datos al detener la recolección tan pronto como la evidencia estadística es suficiente. Sin embargo, aplicar SPRT a datos sensibles (por ejemplo, ensayos clínicos, registros financieros) plantea riesgos significos de privacidad. La naturaleza adaptativa de las pruebas secuenciales significa que la decisión de detener la recolección de datos puede filtrar información sobre las observaciones recientes. Aunque la Privacidad Diferencial (DP) es el marco estándar para proteger datos en entornos de muestra fija, los mecanismos de DP existentes (por ejemplo, AboveThreshold) no son directamente óptimos para las pruebas secuenciales, que requieren monitorear simultáneamente tanto los límites superiores como los inferiores. Los intentos previos de privatizar SPRT dependían de nociones de privacidad más débiles, carecían de un método para calibrar los umbrales para tasas de error específicas, o requerían simulaciones de Monte Carlo que filtraban la privacidad para su ajuste.

Metodología

Los autores proponen DP-SPRT, un marco general para pruebas de razón de probabilidad secuencial con privacidad diferencial. El núcleo de la metodología involucra dos innovaciones principales:

1. El Mecanismo OutsideInterval:
   Para abordar la necesidad de monitorear simultáneamente dos umbrales (para aceptar $H_0$ o $H_1$), los autores introducen un nuevo mecanismo llamado OutsideInterval. A diferencia de las composiciones ingenuas de técnicas existentes como AboveThreshold (que requeriría dos instancias separadas y duplicaría el costo de privacidad), OutsideInterval procesa una secuencia de consultas y se detiene cuando el resultado de una consulta cae fuera de un intervalo predefinido $[T_0, T_1]$.

   • Añade ruido tanto a los resultados de las consultas como a los umbrales.
   • Crucialmente, utiliza la misma realización de ruido para ambas comparaciones de umbral, lo que estrecha el análisis de privacidad.
   • Este mecanismo logra una mejora de un factor de 2 en las garantías de privacidad en comparación con la composición de dos instancias separadas de AboveThreshold.

2. Marco DP-SPRT:
   Los autores adaptan el SPRT clásico inyectando ruido cuidadosamente calibrado tanto en el estadístico de la prueba (media empírica) como en los umbrales de decisión.

   • Asignación de Ruido: El marco admite diversas distribuciones de ruido, analizando específicamente el ruido de Laplace (para $\epsilon$-DP puro) y el ruido Gaussiano (para la Privacidad Diferencial de Rényi, RDP).
   • Control de Error: Se introducen una función de corrección $C(n, \delta)$ y un parámetro de asignación de error $\gamma$ para descomponer el error total entre el error estadístico del SPRT y el error introducido por el ruido de privacidad. Esto permite que la prueba se calibre para alcanzar tasas prescritas de Error Tipo I ($\alpha$) y Tipo II ($\beta$) sin ajuste empírico.
   • Submuestreo: Para regímenes de alta privacidad, los autores proponen una variante que utiliza el submuestreo para calcular la media empírica, lo que amplifica la privacidad y reduce la magnitud del ruido requerido.

Contribuciones Clave

1. Marco General: Introducción de DP-SPRT, un envoltorio (wrapper) que soporta varios mecanismos de ruido mientras proporciona garantías de privacidad rigurosas y control de error para pruebas de hipótesis secuenciales.
2. Mecanismo OutsideInterval: Un nuevo mecanismo privado para comparar una secuencia de consultas contra dos umbrales simultáneamente. Ofrece una mejora de privacidad de un factor de 2 sobre la composición ingenua y es aplicable a otros problemas de monitoreo continuo.
3. Límites Teóricos:
   • Límites Superiores: Se derivan límites superiores genéricos sobre el error y la complejidad de la muestra para DP-SPRT para observaciones de Bernoulli, acomodando tanto el ruido de Laplace como el Gaussiano.
   • Límites Inferiores: Los autores demuestran un límite inferior en la complejidad de la muestra para cualquier prueba $\epsilon$-DP con errores prescritos. Esto revela dos regímenes: uno donde la privacidad tiene un impacto mínimo en el tamaño de la muestra, y otro donde los requisitos de alta privacidad aumentan significativamente el tamaño de muestra esperado.
   • Cercanía a la Optimalidad: Al comparar sus límites superiores con los límites inferiores derivados, los autores muestran que DP-SPRT con ruido de Laplace es casi óptimo cuando las tasas de error son pequeñas y las dos hipótesis están cerca.
4. Calibración Práctica: A diferencia del trabajo previo (por ejemplo, PrivSPRT) que depende de simulaciones de Monte Carlo para determinar los umbrales (un proceso que puede filtrar la privacidad), DP-SPRT proporciona umbrales teóricamente calibrados que garantizan el control del error.

Resultados

• Rendimiento Teórico: El análisis demuestra que DP-SPRT con ruido de Laplace alcanza una complejidad de muestra casi óptima en el régimen de errores pequeños e hipótesis cercanas, coincidiendo con el límite inferior derivado hasta un constante multiplicativo.
• Rendimiento Experimental: Experimentos con datos de Bernoulli simulados ($p_0=0.3, p_1=0.7$) con errores objetivo $\alpha=\beta=0.05$ muestran:
  • Eficiencia: Las variantes de DP-SPRT (Laplace, Gaussiano y Laplace con submuestreo) requieren consistentemente menos muestras (tiempos de parada más pequeños) que el método PrivSPRT existente a través de varios niveles de privacidad ($\epsilon$).
  • Precisión: Las tasas empíricas de Error Tipo I para DP-SPRT permanecen por debajo del $\alpha$ objetivo en todos los niveles de privacidad. En contraste, PrivSPRT ocasionalmente excede la tasa objetivo, atribuido al ruido introducido durante su calibración de Monte Carlo.
  • Beneficios del Submuestreo: La variante de submuestreo de DP-SPRT muestra mejoras sustanciales en los regímenes de alta privacidad (bajo $\epsilon$), validando el efecto de amplificación de la privacidad.

Significado y Reivindicaciones

El artículo afirma llenar un vacío significativo en la literatura al proporcionar la primera prueba secuencial $\epsilon$-DP que puede calibrarse teóricamente para alcanzar los errores Tipo I y Tipo II prescritos sin ajuste de hiperparámetros o simulaciones que filtren la privacidad. Los autores enfatizan que su trabajo:

• Establece un compromiso (trade-off) estricto entre privacidad y utilidad para las pruebas secuenciales, particularmente para distribuciones de Bernoulli.
• Demuestra que el ruido de Laplace, previamente considerado inadecuado para pruebas secuenciales por algunos, es en realidad casi óptimo en regímenes específicos cuando se usa con su marco.
• Introduce el mecanismo OutsideInterval como una contribución potencialmente independiente para cualquier aplicación que requiera el monitoreo simultáneo de dos umbrales bajo privacidad diferencial.
• Proporciona un límite inferior riguroso que caracteriza el costo fundamental de la privacidad en las pruebas secuenciales, mostrando que, si bien la privacidad aumenta la complejidad de la muestra, el algoritmo propuesto minimiza este costo de manera efectiva.

Los autores mantienen un tono modesto respecto a su alcance, señalando que sus garantías de optimalidad están establecidas actualmente para observaciones de Bernoulli e hipótesis simples, con extensiones a hipótesis compuestas y otras distribuciones identificadas como trabajo futuro.