Dobrushin Coefficients of Private Mechanisms Beyond Local Differential Privacy

Resumo Técnico: Coeficientes de Dobrushin de Mecanismos Privados Além da Privacidade Diferencial Local

Definição do Problema
O artigo aborda as limitações no uso da Privacidade Diferencial Local (LDP) como a única métrica para quantificar a privacidade em núcleos de Markov discretos (mecanismos de privacidade). Embora a LDP seja amplamente adotada, os autores observam dois problemas principais:

1. Restritividade excessiva: Em aplicações estatísticas como a estimativa de parâmetros, alcançar garantias de LDP rigorosas ($\epsilon$ pequeno) pode levar a uma degradação extrema no desempenho da estimativa (alto risco minimax).
2. Comportamento contraintuitivo com probabilidades zero: A definição padrão de LDP produz um custo de privacidade infinito se um mecanismo atribui probabilidade zero a qualquer saída para um determinado dado de entrada ($K_{Y|X=x}(y) = 0$). Isso trata mecanismos com significativa randomização (ex: $K_1$ no exemplo do artigo) de forma idêntica a mapeamentos de identidade ou mecanismos triviais (ex: $K_2$) se ambos contiverem entradas zero, falhando em distinguir comportamentos de "ruído" e "determinísticos" em termos de vazamento de privacidade.

Para abordar esses problemas, os autores investigam os coeficientes de Dobrushin (coeficientes de contração da distância de Variação Total) para mecanismos que satisfazem o Vazamento Máximo Pontual (PML) em vez da LDP estrita. O PML é uma adaptação pontual do vazamento máximo que depende da distribuição dos dados $P_X$. Os autores analisam especificamente mecanismos onde a distribuição de entrada $P_X$ possui uma massa de probabilidade mínima limitada por um valor constante $c > 0$ (ou seja, $\min_x P_X(x) \geq c$). Este arcabouço permite a análise de mecanismos com atribuições de probabilidade zero que seriam considerados "infinitamente privados" (ou infinitamente vazantes) sob a LDP.

Metodologia
O artigo utiliza ferramentas de teoria da informação para derivar limites na contração de $f$-divergências através de mecanismos de privacidade.

• Definições: Os autores definem $(\epsilon, c)$-PML como uma restrição onde o PML é limitado por $\epsilon$ para todas as distribuições de entrada no conjunto $Q_X(c) = \{P_X : \min_x P_X(x) \geq c\}$. Isso generaliza a LDP, pois a LDP corresponde ao limite $c \to 0$.
• Coeficientes de Contração: O objeto central de estudo é o coeficiente de Dobrushin $\eta_{TV}(\epsilon, c)$, definido como o supremo da contração da distância de Variação Total (TV) sobre todos os núcleos que satisfazem $(\epsilon, c)$-PML.
• Redução para Saídas Binárias: Os autores provam que, para encontrar o coeficiente de Dobrushin máximo, é suficiente considerar mecanismos com espaços de saída binários ($|Y|=2$). Isso simplifica significamente o problema de otimização.
• Desigualdades: A derivação utiliza a desigualdade de Binette (uma generalização da desigualdade reversa de Pinsker) para estender os limites de TV para $f$-divergências gerais (como Entropia Relativa e divergência de Hellinger).

Principais Contribuições e Resultados

1. Limites Alcançáveis para Coeficientes de Dobrushin:
   O artigo deriva um limite superior apertado para o coeficiente de Dobrushin $\eta_{TV}(\epsilon, c)$ para qualquer núcleo que satisfaça $(\epsilon, c)$-PML. O limite é dado por:
   $$\eta_{TV}(\epsilon, c) \leq \min\left( \frac{e^\epsilon - 1}{e^\epsilon(1 - Nc) + 1}, 1 \right)$$
   onde $N$ é o tamanho do alfabeto de entrada.

   • Análise de Regimes: Os autores mostram que, se $\epsilon \geq \log(2/Nc)$, o coeficiente de contração é 1 (não ocorre contração). Se $\epsilon < \log(2/Nc)$, o coeficiente é estritamente menor que 1, indicando contração induzida pela privacidade.
   • Recuperação da LDP: Conforme $c \to 0$, o limite recupera o resultado conhecido para $\epsilon$-LDP: $\eta_{TV} \leq \frac{e^\epsilon - 1}{e^\epsilon + 1}$.
   • Construção de Mecanismos: O artigo fornece construções explícitas de mecanismos (especificamente mecanismos de saída binária) que alcançam esses limites, demonstrando que os limites são alcançáveis.

2. Extensão para $f$-Divergências Gerais:
   Usando a desigualdade de Binette, os autores estendem os limites de TV para $f$-divergências gerais. Eles derivam fortes desigualdades de processamento de dados (SDPIs) para Entropia Relativa e divergência de Hellinger sob restrições $(\epsilon, c)$-PML. Esses limites dependem do fator de contração de TV e das razões extremas das distribuições de saída.

3. Aplicação ao Risco Minimax:
   Os limites derivados são aplicados ao risco de estimativa minimax privado. Usando o método de dois pontos de Le Cam e a propriedade de tensorização de $f$-divergências, os autores mostram que a complexidade de amostragem necessária para atingir um certo nível de risco aumenta por um fator proporcional ao inverso do coeficiente de Dobrushin privado. Especificamente, se o coeficiente for 1, a complexidade de amostragem corresponde ao cenário não privado; se for menor que 1, o tamanho efetivo da amostra é reduzido.

Significância e Alegações
O artigo afirma fornecer um arcabouço mais matizado para analisar mecanismos de privacidade do que apenas a LDP. Ao introduzir o parâmetro $c$, os autores podem quantificar o vazamento de privacidade para mecanismos que contêm entradas de probabilidade zero, que são excluídos ou tratados patologicamente sob a LDP padrão.

• Limites Mais Apertados: Para mecanismos que satisfazem LDP, os limites propostos são mais apertados ou mais adaptáveis do que resultados anteriores quando a distribuição de entrada possui uma massa mínima $c$ conhecida.
• Além da LDP: O arcabouço estende a análise de coeficientes de contração para toda a classe de núcleos discretos, incluindo aqueles que não satisfazem nenhuma garantia de LDP finita.
• Interpretação Operacional: Os resultados ligam os coeficientes de contração teóricos diretamente à degradação do desempenho da estimativa estatística, oferecendo uma ferramenta para quantificar o "custo" da privacidade em termos de aumento de risco ou complexidade de amostragem.

Os autores enfatizam que seu trabalho recupera os resultados existentes de LDP como um caso especial, oferecendo uma interpolação contínua entre restrições de distribuição uniforme e o regime total de LDP, abordando assim a natureza "restritiva demais" da LDP em contextos estatísticos específicos.