Resumen Técnico: AdaPrivate-TS

Planteamiento del Problema

Los sistemas de recomendación en línea se enfrentan a una tensión fundamental entre el aprendizaje de las preferencias del usuario a partir de datos de comportamiento privados y la provisión de garantías de privacidad rigurosas. La Privacidad Diferencial (DP) ofrece una protección sólida, pero típicamente introduce ruido que degrada el rendimiento del aprendizaje. Los algoritmos de bandidos contextuales privados existentes suelen tratar el ruido de privacidad como pura corrupción, lo que genera un regret significativo. Además, muchos enfoques dependen de la DP conjunta (protegiendo toda la secuencia de acciones) o de la composición secuencial, lo que resulta en altos costos de privacidad (por ejemplo, un regret de $O(T^{3/4})$) o requiere un curador central de confianza.

Este artículo aborda el desafío de diseñar un algoritmo de bandido contextual diferencialmente privado que opere bajo DP a nivel de evento (protegiendo pares individuales de usuario-recompensa) con contextos estocásticos, con el objetivo de minimizar el regret manteniendo una privacidad rigurosa sin una entidad central de confianza.

Metodología: AdaPrivate-TS

Los autores proponen AdaPrivate-TS, un nuevo algoritmo que integra el Muestreo de Thompson (TS) con la DP de concentración cero por lotes (zCDP).

Percepción Central: El Ruido como Incertidumbre

La contribución teórica central es la observación de que el ruido de DP, cuando se añade a las estadísticas suficientes de un bandido lineal, no solo corrompe la estimación, sino que infla estructuralmente la covarianza posterior.

• En el Muestreo de Thompson estándar, la distribución posterior es $\theta | H_t \sim \mathcal{N}(\hat{\theta}_t, v^2 A_t^{-1})$.
• Cuando se añade ruido gaussiano $\eta \sim \mathcal{N}(0, \sigma^2 I)$ a la estadística suficiente $b_t$ para la privacidad, la distribución de muestreo resultante se convierte en:
  $$\tilde{\theta}_t \sim \mathcal{N}\left(\hat{\theta}_t, v^2 A_t^{-1} + \sigma^2 A_t^{-2}\right)$$
• A diferencia de los métodos de Límite de Banda Superior (UCB), que tratan este ruido como un error, el Muestreo de Thompson interpreta naturalmente la covarianza inflada ($v^2 A_t^{-1} + \sigma^2 A_t^{-2}$) como un aumento de la incertidumbre. Esto impulsa al algoritmo a explorar más en direcciones donde el ruido de privacidad es dominante, convirtiendo efectivamente la "corrupción" en una señal de exploración beneficiosa.

Componentes Algorítmicos

1. Composición zCDP por Lotes: El algoritmo procesa las interacciones en lotes. Libera las estadísticas suficientes ruidosas (específicamente el vector $b$) al final de cada lote. Al utilizar la composición paralela, el costo total de privacidad está determinado por el costo máximo de un solo lote ($\max_k \rho_k = \rho$) en lugar de la suma de los costos, lo que permite que el costo de privacidad permanezca logarítmico en $T$.
2. Amplificación de Privacidad: Para reducir aún más el ruido ante presupuestos de privacidad estrictos ($\epsilon \leq 1$), los autores emplean el submuestreo de Poisson. Al incluir cada recompensa en la suma del lote con una probabilidad $q$, el costo de privacidad efectivo se reduce por un factor de aproximadamente $2q^2$ sin reescalar la sensibilidad, aprovechando el análisis de la Privacidad Diferencial de Rényi (RDP).
3. Exploración Adaptativa: El algoritmo decae el parámetro de exploración $v_k$ a lo largo del tiempo ($v_k = v_0 \cdot \gamma^{k-1}$) para equilibrar una exploración agresiva temprana con una explotación refinada a medida que el modelo converge.

Modelo de Privacidad

El algoritmo satisface la DP a nivel de evento, donde los conjuntos de datos adyacentes difieren en exactamente un par usuario-recompensa $(u_t, r_t)$. Las acciones se tratan como salidas del algoritmo, no como entradas privadas. El mecanismo utiliza zCDP para obtener límites de composición más ajustados, convirtiéndolos a $(\epsilon, \delta)$-DP mediante fórmulas de conversión estándar.

Principales Contribuciones

1. Muestreo de Thompson Privado: El artículo demuestra que añadir ruido de DP a las estadísticas suficientes resulta en una inflación específica de la covarianza posterior ($v^2 A^{-1} + \sigma^2 A^{-2}$). Esto permite que el TS interprete el ruido como incertidumbre en lugar de corrupción.
2. Límite de Regret Ajustado: Bajo DP a nivel de evento con contextos estocásticos, los autores demuestran un límite de regret donde el costo de privacidad es $O(\sqrt{d} \cdot \log T / \sqrt{\rho})$. Este es logarítmico en $T$, una mejora significativa sobre los costos de $O(\sqrt{T})$ o $O(T^{3/4})$ asociados con la composición secuencial o la DP conjunta.
3. Análisis de Amplificación de Privacidad: Se proporciona un análisis riguroso basado en RDP del submuestreo de Poisson para bandidos, demostrando ganancias de un 2 a 4% en valores bajos de $\epsilon$.
4. Evaluación Exhaustiva: Experimentos extensos en conjuntos de datos sintéticos y del mundo real (MovieLens-25M, Jester) validan las afirmaciones teóricas.

Resultados Experimentales

• Rendimiento vs. No Privado: AdaPrivate-TS logra entre el 93% y el 99% del rendimiento del Muestreo de Thompson no privado a través de presupuestos de privacidad $\epsilon \in [0.5, 5]$.
• Comparación con UCB: El algoritmo supera a las bases de comparación de UCB privados por un 0.5–3.7% en promedio. Con una exploración adaptativa ajustada, la ventaja crece hasta un 18% en configuraciones de privacidad extrema.
• Datos del Mundo Real: En los conjuntos de datos MovieLens y Jester, AdaPrivate-TS logra el mejor rendimiento general entre las bases de comparación de nivel de evento, dominando particularmente en $\epsilon \geq 2$.
• Privacidad de Características: Cuando las características se privatizan usando DP-SVD, la ventaja de TS sobre UCB aumenta a un +11%, confirmando que el mecanismo de "ruido como incertidumbre" se extiende más allá de la privacidad de la recompensa hacia la privacidad de las características.
• Ablación: El análisis de componentes muestra que la combinación de TS, amplificación de privacidad y exploración adaptativa produce una ganancia acumulada de +6.3% sobre un baseline de UCB privado con ruido.

Significado y Reivindicaciones

El artículo sostiene que el Muestreo de Thompson es inherentemente más adecuado que UCB para bandidos contextuales privados porque puede aprovechar las propiedades estructurales del ruido de DP como una fuente de exploración en lugar de una fuente de error.

Las afirmaciones clave sobre su importancia incluyen:

• Eficiencia: El uso de la composición paralela con procesamiento por lotes permite que el costo de privacidad sea logarítmico en el horizonte de tiempo $T$, evitando las severas penalizaciones de la composición secuencial.
• Practicidad: El algoritmo opera sin un curador central de confianza, basándose únicamente en la privacidad a nivel de evento, lo cual es apropiado para escenarios donde los usuarios contribuyen con pocas interacciones.
• Robustez: El método se mantiene estable bajo características privadas (DP-SVD) y ofrece una forma fundamentada de ajustar los presupuestos de privacidad mediante el submuestreo de Poisson sin sacrificar la calidad de la recomendación.
• Novedad Teórica: La identificación de la inflación de la covarianza inducida por el ruido como un mecanismo de "ruido como incertidumbre" proporciona una nueva perspectiva para el diseño de algoritmos de aprendizaje privados, yendo más allá del paradigma de tratar el ruido de privacidad únicamente como corrupción.

Los autores concluyen que AdaPrivate-TS ofrece una herramienta fundamentada para los profesionales que necesitan equilibrar requisitos de privacidad estrictos con un alto rendimiento de recomendación, particularmente en entornos con contextos estocásticos y restricciones de privacidad a nivel de evento.