Better Privacy Guarantees for Larger Groups

Resumo Técnico: Garantias de Privacidade Melhores para Grupos Maiores

Declaração do Problema
Este artigo aborda um problema em aberto proposto por Pujol e Desfontaines [2023] relativo ao design de histogramas privados para grupos fixos e disjuntos. Mecanismos padrão de privacidade diferencial tipicamente adicionam ruído de uma magnitude fixa a cada contagem, fornecendo erro absoluto uniforme, mas resultando em erros relativos significativamente menores para grupos grandes em comparação com pequenos. A questão central é se é possível "gastar" esse excesso de precisão de forma diferente: permitindo que o erro de um grupo escale proporcionalmente à sua contagem ($x_i$) para fornecer garantias de privacidade mais fortes (um orçamento de privacidade menor) para os membros de grupos maiores.

O artigo investiga isso sob o modelo de adjacência adicionar-ou-remover-um. O objetivo é encontrar um mecanismo onde o orçamento de privacidade $v(n)$ dependa apenas da contagem do grupo, seja não crescente e satisfaça a privacidade diferencial de concentração zero (zCDP) por grupo dependente da contagem. Isso requer limitar a divergência de Rényi em ambas as direções para cada ordem $\alpha > 1$ entre conjuntos de dados vizinhos.

Um obstáculo técnico crítico identificado é a condição de contorno em zero. A formulação original exigia que o erro absoluto esperado fosse estritamente menor que $r x_i$. Em $x_i = 0$, isso implica $E|\hat{x}_i| < 0$, o que é impossível. Além disso, relaxar a desigualdade para $\leq$ mantendo a divergência de Rényi de dois lados finita através da aresta $0 \leftrightarrow 1$ leva a uma contradição (forçando a saída na contagem 1 a ser determinística, violando o limite de erro).

Metodologia e Formulação Reparada
Para resolver o problema da fronteira, os autores propõem um "requisito de utilidade reparado":
$$E|\hat{x}_i - x_i| < r \max\{x_i, 1\}$$
Isso mantém o alvo de erro relativo para todas as contagens positivas, introduzando uma tolerância absoluta fixa em zero, tornando o problema viável.

O artigo emprega duas abordagens metodológicas principais:

1. Viabilidade (Limite Superior): Os autores especializam um framework existente de "transformação com deslocamento" (Finley et al. [2026]). Eles transformam o espaço de contagem via um logaritmo com um deslocamento $c$ (ou seja, $\log(x_i + c)$), adicionam ruído Gaussiano de variância fixa e aplicam um drift determinístico antes de exponencializar e realizar o clipping.

   • Inovação Chave: Diferente dos mecanismos log-normais padrão que usam um drift de $-\sigma^2/2$ para garantir a ausência de viés na média, este mecanismo usa um drift de $-\sigma^2$. Este drift específico é escolhido para minimizar o erro multiplicativo absoluto esperado, o que se alinha com a métrica de utilidade do artigo.
   • Mecanismo de Privacidade: Ao trabalhar no espaço logarítmico com variância igual, o mecanismo garante que a divergência de Rényi entre contagens adjacentes seja finita para todas as ordens $\alpha$, evitando a "obstrução de cauda" onde variâncias desiguais causam divergência infinita em uma direção.

2. Impossibilidade (Limite Inferior): Os autores provam que nenhum mecanismo que satisfaça o requisito de utilidade reparado e os requisitos de zCDP dependente da contagem pode alcançar uma taxa de decaimento do orçamento de privacidade mais rápida que o inverso do quadrado da contagem.

   • Argumento de Duas Contagens: Um teste entre duas contagens específicas estabelece o expoente $n^{-2}$.
   • Argumento de Muitas Contagens: Utilizando uma variável aleatória de "offset oculto" e argumentos informacionais (relacionando o erro absoluto esperado à informação mútua), os autores derivam um limite inferior mais apertado no coeficiente principal do orçamento de privacidade.

Resultados Principais

• Taxa Assintótica Ótima: Para qualquer $0 < r < 1$ fixo, o orçamento de privacidade ótimo $v(n)$ decai como $\Theta_r(n^{-2})$.

  • Limite Superior: O mecanismo Gaussiano de log-deslocado alcança $v(n) = O_r(n^{-2})$. Especificamente, conforme $n \to \infty$, $v(n) \approx \frac{1}{2\sigma^2 n^2}$.
  • Limite Inferior: Qualquer mecanismo satisfazendo os requisitos deve ter $\liminf_{n \to \infty} n^2 v(n) \geq \frac{(1-r)^6}{128r^2(1+r)^2}$. Isso confirma que a taxa de inverso do quadrado é intrínseca e não um artefato da construção.

• Coeficientes Principais: O artigo estreita a lacuna entre os melhores limites superior e inferior para o coeficiente principal $C^*$ no limite de $r$ pequeno e $n$ grande:
  $$\frac{\pi}{4e^2} \leq C^* \leq \frac{1}{\pi}$$
  A razão entre esses limites é de aproximadamente 2,995, indicando que os limites estão dentro de um fator de três.

• Falha da Gaussiana de Variância Desigual: O artigo demonstra que um mecanismo ingênuo que libera $N(n, r^2 n^2)$ (ruído Gaussiano com variância proporcional ao quadrado da contagem) falha na definição de zCDP. Embora tenha a escala de erro correta, as variâncias desiguais entre contagens adjacentes fazem com que a divergência de Rényi em uma direção se torne infinita para ordens $\alpha$ suficientemente altas, violando o requisito de "todas as ordens" da zCDP.

• Caso Trivial: Em $r=1$, uma liberação independente de dados (por exemplo, sempre emitindo $0.5$) satisfaz o critério reparado com perda de privacidade zero ($v \equiv 0$).

Significância e Alegações
O artigo afirma fornecer a primeira prova independente de mecanismo de que a taxa de inverso do quadrado é ótima para esta formulação específica de privacidade de grupo.

• Viabilidade: Estabelece que a formulação "reparada" é solucionável e fornece um mecanismo concreto e composível (log-Gaussiano deslocado) que alcança a taxa ótima.
• Otimalidade: Prova que nenhum mecanismo, independentemente da complexidade ou estrutura de correlação, pode melhorar a taxa de decaimento $n^{-2}$.
• Precisão: Ao empregar argumentos de informação de muitas contagens, o artigo aperta significativamente os limites do coeficiente principal em comparação com análises anteriores de duas contagens, reduzindo a incerteza para um fator de menos de três.

Os autores afirmam explicitamente que determinar o valor exato do coeficiente ótimo $C^*$ permanece uma questão em aberto. Eles também observam que seus resultados se aplicam a grupos fixos e disjuntos; grupos sobrepostos ou dependentes de dados exigiriam uma análise de sensibilidade separada. O mecanismo é enviesado (devido ao drift $-\sigma^2$), mas é calibrado especificamente para minimizar o erro absoluto esperado, não para ser imparcial.