Resumo Técnico: AdaPrivate-TS

Definição do Problema

Sistemas de recomendação online enfrentam uma tensão fundamental entre aprender as preferências dos usuários a partir de dados comportamentais privados e fornecer garantias rigorosas de privacidade. Embora a Privacidade Diferencial (DP) ofereça proteção forte, ela tipicamente introduz ruído que degrada o desempenho do aprendizado. Algoritmos existentes de bandidos contextuais privados frequentemente tratam o ruído de DP como pura corrupção, levando a um regret significativo. Além disso, muitas abordagens dependem de DP conjunta (protegendo toda a sequência de ações) ou composição sequencial, o que resulta em altos custos de privacidade (por exemplo, regret de $O(T^{3/4})$) ou exige um curador central confiável.

Este artigo aborda o desafio de projetar um algoritmo de bandido contextual diferencialmente privado que opere sob DP de nível de evento (protegendo pares individuais de usuário-recompensa) com contextos estocásticos, visando minimizar o regret enquanto mantém uma privacidade rigorosa sem uma entidade central confiável.

Metodologia: AdaPrivate-TS

Os autores propõem o AdaPrivate-TS, um novo algoritmo que integra a Amostragem de Thompson (TS) com a DP de concentração zero em lotes (zCDP).

Insight Central: Ruído como Incerteza

A principal contribuição teórica é a observação de que o ruído de DP, quando adicionado às estatísticas suficientes de um bandido linear, não apenas corrompe a estimativa, mas infla estruturalmente a covariância posterior.

• No Thompson Sampling padrão, a distribuição posterior é $\theta | H_t \sim \mathcal{N}(\hat{\theta}_t, v^2 A_t^{-1})$.
• Quando o ruído Gaussiano $\eta \sim \mathcal{N}(0, \sigma^2 I)$ é adicionado à estatística suficiente $b_t$ para fins de privacidade, a distribuição de amostragem resultante torna-se:
  $$\tilde{\theta}_t \sim \mathcal{N}\left(\hat{\theta}_t, v^2 A_t^{-1} + \sigma^2 A_t^{-2}\right)$$
• Ao contrário dos métodos de Upper Confidence Bound (UCB), que tratam este ruído como erro, o Thompson Sampling interpreta naturalmente a covariância inflada ($v^2 A_t^{-1} + \sigma^2 A_t^{-2}$) como aumento de incerteza. Isso induz o algoritmo a explorar mais em direções onde o ruído de privacidade é dominante, convertendo efetivamente a "corrupção" em um sinal de exploração benéfico.

Componentes Algorítmicos

1. Composição zCDP em Lotes: O algoritmo processa interações em lotes. Ele libera estatísticas suficientes ruidosas (especificamente o vetor $b$) ao final de cada lote. Ao usar composição paralela, o custo total de privacidade é determinado pelo custo máximo de um único lote ($\max_k \rho_k = \rho$) em vez da soma dos custos, permitindo que o custo de privacidade permaneça logarítmico em $T$.
2. Amplificação de Privacidade: Para reduzir ainda mais o ruído em orçamentos de privacidade rigorosos ($\epsilon \leq 1$), os autores empregam subamostragem de Poisson. Ao incluir cada recompensa na soma do lote com probabilidade $q$, o custo de privacidade efetivo é reduzido por um fator de aproximadamente $2q^2$ sem reescalar a sensibilidade, aproveitando a análise de Privacidade Diferencial de Rényi (RDP).
3. Exploração Adaptativa: O algoritmo decai o parâmetro de exploração $v_k$ ao longo do tempo ($v_k = v_0 \cdot \gamma^{k-1}$) para equilibrar uma exploração agressiva inicial com uma explotação refinada conforme o modelo converge.

Modelo de Privacidade

O algoritmo satisfaz a DP de nível de evento, onde conjuntos de dados adjacentes diferem em exatamente um par usuário-recompensa $(u_t, r_t)$. As ações são tratadas como saídas do algoritmo, não como entradas privadas. O mecanismo utiliza zCDP para limites de composição mais estreitos, convertendo para $(\epsilon, \delta)$-DP via fórmulas de conversão padrão.

Principais Contribuições

1. Thompson Sampling Privado: O artigo prova que adicionar ruído de DP às estatísticas suficientes resulta em uma inflação específica da covariância posterior ($v^2 A^{-1} + \sigma^2 A^{-2}$). Isso permite que o TS interprete o ruído como incerteza.
2. Limite de Regret Estrito: Sob contextos estocásticos com DP de nível de evento, os autores provam um limite de regret onde o custo de privacidade é $O(\sqrt{d} \cdot \log T / \sqrt{\rho})$. Este é logarítmico em $T$, uma melhoria significativa sobre os custos de $O(\sqrt{T})$ ou $O(T^{3/4})$ associados à composição sequencial ou DP conjunta.
3. Análise de Amplificação de Privacidade: Uma análise rigorosa baseada em RDP para subamostragem de Poisson em bandidos é fornecida, demonstrando ganhos de 2–4% em valores baixos de $\epsilon$.
4. Avaliação Abrangente: Experimentos extensos em conjuntos de dados sintéticos e do mundo real (MovieLens-25M, Jester) validam as afirmações teóricas.

Resultados Experimentais

• Desempenho vs. Não-Privado: O AdaPrivate-TS atinge 93–99% do desempenho do Thompson Sampling não-privado em orçamentos de privacidade $\epsilon \in [0.5, 5]$.
• Comparação com UCB: O algoritmo supera as bases de comparação de UCB privado por 0.5–3.7% em média. Com exploração adaptativa ajustada, a vantagem cresce para até 18% em configurações de privacidade extrema.
• Dados do Mundo Real: Nos conjuntos de dados MovieLens e Jester, o AdaPrivate-TS alcança o melhor desempenho geral entre as bases de comparação de nível de evento, dominando particularmente em $\epsilon \geq 2$.
• Privacidade de Atributos: Quando os atributos são privatizados usando DP-SVD, a vantagem do TS sobre o UCB aumenta para +11%, confirmando que o mecanismo de "ruído como incerteza" se estende além da privacidade de recompensa para a privacidade de atributos.
• Ablação: A análise de componentes mostra que a combinação de TS, amplificação de privacidade e exploração adaptativa gera um ganho cumulativo de +6.3% sobre uma base de comparação de UCB privado com ruído.

Significância e Alegações

O artigo afirma que o Thompson Sampling é inerentemente mais adequado que o UCB para bandidos contextuais privados porque pode aproveitar as propriedades estruturais do ruído de DP como uma fonte de exploração, em vez de uma fonte de erro.

As principais alegações de significância incluem:

• Eficiência: O uso de composição paralela com processamento em lotes permite que o custo de privacidade seja logarítmico no horizonte de tempo $T$, evitando as severas penalidades da composição sequencial.
• Praticidade: O algoritmo opera sem um curador central confiável, baseando-se apenas na privacidade de nível de evento, o que é apropriado para cenários onde os usuários contribuem com poucas interações.
• Robustez: O método permanece estável sob atributos privados (DP-SVD) e oferece uma maneira fundamentada de estreitar os orçamentos de privacidade via subamostragem de Poisson sem sacrificar a qualidade da recomendação.
• Novidade Teórica: A identificação da inflação de covariância induzida pelo ruído como um mecanismo para "ruído como incerteza" fornece uma nova perspectiva para o design de algoritmos de aprendizado privados, indo além do paradigma de tratar o ruído de privacidade meramente como corrupção.

Os autores concluem que o AdaPrivate-TS oferece uma ferramenta fundamentada para profissionais que precisam equilibrar requisitos estritos de privacidade com alto desempenho de recomendação, particularmente em cenários com contextos estocásticos e restrições de privacidade de nível de evento.