Resumo Técnico: Shuffle and Joint Differential Privacy for Generalized Linear Contextual Bandits

1. O Problema

O artigo aborda o problema de Bandidos Contextuais de Modelos Lineares Generalizados (GLM Contextual Bandits) sob restrições de privacidade diferencial. Em problemas de bandidos contextuais, um agente deve selecionar uma ação (braço) com base em um vetor de características (contexto) para maximizar a recompensa acumulada.

Diferente dos modelos lineares tradicionais, onde existe uma solução analítica (estimador de Ridge) para encontrar os parâmetros, os GLMs (como a regressão logística) não possuem estimadores de forma fechada. Isso introduz três desafios fundamentais:

1. Otimização Privada: É necessário realizar otimização convexa iterativa, o que consome o orçamento de privacidade.
2. Matrizes de Design Evolutivas: A privacidade deve ser rastreada através de matrizes de design que mudam a cada rodada.
3. Erro de Otimização: O erro introduzido pela otimização privada deve ser explicitamente incorporado na análise de regret (arrependimento).

O autor estuda o problema sob dois modelos de privacidade:

• Shuffle Differential Privacy (Shuffle-DP): Para contextos estocásticos, onde os dados passam por um embaralhador (shuffler) que amplifica a privacidade local.
• Joint Differential Privacy (Joint-DP): Para contextos adversariais, onde a ação na rodada $t$ deve ser privada em relação aos pares contexto-recompensa de todas as outras rodadas.

2. Metodologia

O trabalho propõe dois algoritmos principais, adaptando técnicas de "pouca adaptatividade" (limited adaptivity) para o cenário de privacidade:

A. Para Contextos Estocásticos (Algoritmo 1 - Shuffle-DP)

O algoritmo divide o horizonte $T$ em lotes (batches).

• Design Ótimo: Utiliza o design $G$-ótimo para selecionar braços.
• Estimativa de Covariância: Usa um protocolo de soma de vetores embaralhado (shuffled vector summation) para agregar os produtos externos dos contextos ($x_t x_t^\top$) de forma privada.
• Estimativa de Parâmetros: Utiliza um otimizador convexo privado via shuffle (PGD - Projected Gradient Descent) para minimizar a perda de log-verossimilhança regularizada.

B. Para Contextos Adversariais (Algoritmo 2 - Joint-DP)

O algoritmo utiliza um mecanismo de árvore binária para liberar as matrizes de design de forma contínua.

• Critério I (Exploração): Quando a incerteza é alta, o algoritmo seleciona o braço mais incerto e atualiza a matriz de covariância $V$.
• Critério II (Atualização de Política): Utiliza um critério de "crescimento direcional" para decidir quando atualizar o estimador de parâmetros $\hat{\theta}$, evitando que o ruído da árvore binária quebre a monotonicidade necessária para a análise de regret.
• Otimização: Emprega o DP-SGD (Estocástico de Gradiente Descendente com Privacidade Diferencial) para atualizar os parâmetros.

3. Principais Contribuições

1. Primeiros Algoritmos para GLM sob Shuffle/Joint DP: É o primeiro trabalho a estender esses modelos de privacidade para bandidos GLM, superando a dependência de suposições espectrais restritivas de trabalhos anteriores.
2. Remoção do fator $\kappa$ no termo principal: Em GLMs, o parâmetro $\kappa$ (que mede a não-linearidade e pode crescer exponencialmente) costuma degradar o regret. Este trabalho consegue manter o termo principal de $\sqrt{T}$ livre de $\kappa$, mantendo-o apenas em termos de ordem inferior.
3. Novas Técnicas de Análise:
   • Demonstra que o conjunto de tempos de troca de política ($T_o$) é indistinguível sob privacidade.
   • Substitui o critério de "dobro do determinante" (que falha com ruído) por um critério de crescimento direcional.

4. Resultados (Bounds de Regret)

Os resultados mostram que a penalidade imposta pela privacidade é pequena em comparação ao cenário não-privado:

• Shuffle-DP (M1): O regret é $\tilde{O}\left(\frac{d^{3/2}\sqrt{T}}{\sqrt{\epsilon}}\right)$. A diferença para o caso não-privado é apenas um fator de $\sqrt{d/\epsilon}$.
• Joint-DP (M2): O regret é $\tilde{O}\left(\sqrt{d T} \log T + \text{correção aditiva}\right)$. O termo principal coincide com a taxa não-privada $\tilde{O}(d\sqrt{T} \log T)$, o que significa que a privacidade contribui apenas como uma correção aditiva.

5. Significância

Este trabalho é altamente significativo para áreas que utilizam dados sensíveis para recomendação e tomada de decisão, como saúde, educação e publicidade personalizada. Ele prova que é possível implementar sistemas de aprendizado por reforço (bandidos) que são robustos contra adversários e que protegem a privacidade dos usuários sem sacrificar drasticamente a performance (utilidade) do modelo, mesmo quando a relação entre contexto e recompensa é complexa e não-linear (GLM).