Differentially Private Best-Arm Identification

1. Problema e Motivação

O artigo aborda o problema de Identificação do Melhor Braço (BAI - Best Arm Identification) no contexto de Bandits Multi-Armed Estocásticos, com foco no cenário de Confiança Fixa (Fixed-Confidence). O objetivo é identificar o braço com a maior recompensa esperada ($a^*$) com uma probabilidade de erro no máximo $\delta$, minimizando o número de amostras (complexidade de amostragem) necessárias.

A motivação central surge da aplicação de algoritmos de BAI em domínios sensíveis, como:

• Ensaios clínicos adaptativos (dosagem de medicamentos).
• Ajuste de hiperparâmetros em modelos de aprendizado de máquina.
• Estudos de usuários e redes de comunicação.

Nesses cenários, os dados de recompensa podem conter informações pessoais sensíveis. O artigo investiga o custo da Privacidade Diferencial (DP) na eficiência do algoritmo de BAI, analisando dois modelos de confiança:

1. Privacidade Diferencial Local ($\epsilon$-LDP): O usuário não confia no curador de dados; a perturbação ocorre localmente antes do envio.
2. Privacidade Diferencial Global ($\epsilon$-GDP): O curador centralizado é confiável e possui acesso aos dados brutos, mas deve garantir que a saída do algoritmo não revele informações sobre indivíduos específicos.

2. Metodologia

Os autores utilizam uma abordagem baseada em Limites Inferiores (Lower Bounds) e Algoritmos de Top Two (algoritmos que selecionam iterativamente um "líder" e um "desafiante").

2.1 Limites Inferiores de Complexidade de Amostragem

O trabalho deriva limites inferiores teóricos para a complexidade de amostragem esperada $E[\tau_\delta]$ de qualquer algoritmo $\delta$-correto que satisfaça as restrições de DP.

• Regimes de Privacidade: Os limites revelam a existência de dois regimes distintos dependendo do orçamento de privacidade $\epsilon$:
  • Regime de Baixa Privacidade ($\epsilon$ alto): A complexidade de amostragem coincide com o limite não privado. A privacidade pode ser alcançada "de graça".
  • Regime de Alta Privacidade ($\epsilon$ baixo): A complexidade aumenta significativamente, dependendo de novas quantidades teórico-informacionais.
• Métricas de Distância:
  • Para $\epsilon$-LDP, o limite depende de uma combinação entre a Divergência de Kullback-Leibler (KL) e o quadrado da Distância de Variação Total (TV), escalada por um termo de privacidade $c(\epsilon)$. O limite é governado por $T^*_{TV2}(\nu)$.
  • Para $\epsilon$-GDP, o limite depende do mínimo entre a complexidade baseada em KL e uma complexidade baseada em TV escalada por $1/\epsilon$. O limite é governado por $T^*_{TV}(\nu)$.
• Técnica de Prova: Para o caso global, os autores desenvolvem uma versão privada do "Lema de Mudança de Medida" (Change-of-Measure Lemma) utilizando argumentos de acoplamento (coupling) sequencial para limitar a KL entre as marginais das saídas.

2.2 Proposta de Algoritmos

Os autores propõem variantes privadas do algoritmo meta TTUCB (Top Two UCB), que é conhecido por seu bom desempenho empírico e baixo custo computacional.

A. Para $\epsilon$-LDP: Algoritmo CTB-TT

• Estimador: Utiliza o estimador CTB (Convert-To-Bernoulli), baseado no mecanismo de Resposta Aleatorizada (Randomised Response).
• Mecanismo: Transforma as recompensas contínuas ou discretas em variáveis Bernoulli perturbadas para garantir LDP.
• Propriedade: O algoritmo é equivalente a rodar TTUCB não privado em uma instância de bandito modificada ($\nu_\epsilon$), recuperando limites assintóticos ótimos.

B. Para $\epsilon$-GDP: Algoritmos AdaP-TT e AdaP-TT*

• Estimador: Introduzem o estimador DAF (Doubling-And-Forgetting).
  • Doubling: Atualizações de fase ocorrem apenas quando o número de extrações de um braço dobra.
  • Forgetting: Descarta observações antigas, calculando a média apenas sobre a fase atual.
  • Privacidade: Adiciona ruído Laplaciano calibrado apenas no final de cada fase. Devido ao "esquecimento" e à não sobreposição das fases, evita-se a composição sequencial de privacidade, garantindo $\epsilon$-GDP global.
• AdaP-TT (Abordagem Plug-in): Insere o estimador DAF no TTUCB padrão, ajustando apenas o limiar de parada (stopping threshold) para compensar o ruído.
  • Limitação: Não é assintoticamente ótimo em todos os casos, especialmente quando os gaps de média variam muito, pois usa custos de transporte não privados.
• AdaP-TT* (Abordagem Baseada no Limite Inferior): Adapta os custos de transporte (transportation costs) e o limiar de parada para refletir o limite inferior derivado para o regime de alta privacidade.
  • Usa uma métrica de distinção que considera o mínimo entre o gap real e $\epsilon/2$.
  • É assintoticamente ótimo no regime de alta privacidade (até uma constante multiplicativa).

3. Principais Resultados

1. Caracterização da Dureza: O trabalho estabelece que a dificuldade do problema de BAI com privacidade é caracterizada pela Distância de Variação Total (TV), e não apenas pela Divergência KL, especialmente em regimes de alta privacidade.
2. Limites Inferiores:
   • LDP: $E[\tau_\delta] \gtrsim \max(T^*_{KL}, \epsilon^{-2} T^*_{TV2})$.
   • GDP: $E[\tau_\delta] \gtrsim \max(T^*_{KL}, \epsilon^{-1} T^*_{TV})$.
3. Limites Superiores e Otimidade:
   • CTB-TT: Alcança o limite inferior assintótico para LDP com um fator multiplicativo constante (fator 4 quando $\epsilon \to 0$).
   • AdaP-TT*: Alcança o limite inferior assintótico para GDP no regime de alta privacidade com um fator multiplicativo de 48 (para distribuições Gaussianas/Bernoulli), fechando a lacuna deixada por abordagens simples de "plug-in".
4. Análise Empírica:
   • Experimentos em instâncias Bernoulli confirmam a existência dos dois regimes de privacidade.
   • No regime de baixa privacidade, os algoritmos propostos performam quase tão bem quanto o TTUCB não privado.
   • No regime de alta privacidade, o AdaP-TT* supera significativamente o AdaP-TT e o algoritmo de referência DP-SE (Successive Elimination), exigindo menos amostras para atingir a mesma confiança.

4. Significado e Contribuições

• Preenchimento de Lacuna Teórica: Antes deste trabalho, não existiam limites inferiores explícitos de complexidade de amostragem para BAI com privacidade diferencial, nem algoritmos que fossem assintoticamente ótimos em ambos os regimes (local e global).
• Novas Métricas de Distinção: A introdução de tempos característicos baseados em TV ($T^*_{TV}$ e $T^*_{TV2}$) como a medida fundamental de dificuldade para problemas de privacidade em BAI é uma contribuição teórica significativa.
• Eficiência Prática: A proposta de algoritmos baseados em "Top Two" com estimadores de média adaptativos (DAF) oferece uma solução prática e computacionalmente eficiente, superando métodos baseados em eliminação sucessiva (como DP-SE) que são menos adaptativos e mais lentos.
• Trade-off Privacidade-Utilidade: O trabalho quantifica precisamente o custo da privacidade, mostrando que, para orçamentos de privacidade suficientemente altos, a privacidade pode ser obtida sem custo adicional de amostragem, enquanto para orçamentos baixos, o custo escala com $1/\epsilon$ (GDP) ou $1/\epsilon^2$ (LDP).

Em resumo, o artigo fornece a primeira análise completa e algoritmos otimizados para a identificação do melhor braço sob restrições rigorosas de privacidade diferencial, estabelecendo novos padrões teóricos e práticos para aplicações sensíveis em aprendizado de máquina.