Resumo Técnico: Privacidade Diferencial de Rényi com Foco em Precisão e Imunidade à Pós-processamento

Declaração do Problema

A Privacidade Diferencial (DP) é o padrão ouro para a análise de dados preservando a privacidade, mas suas definições estritas "ex-ante" exigem que um limite numérico fixo de privacidade ($\epsilon$) seja especificado antes da execução do algoritmo. Essa rigidez impede fluxos de trabalho onde analistas ajustam adaptativamente os limites de privacidade com base na sensibilidade dos dados ou nos requisitos de utilidade (por exemplo, reduzindo a proteção se os dados se tornarem menos sensíveis, ou aumentando-a se a utilidade estiver muito baixa).

A perspectiva "focada na precisão" (accuracy-first), proposta por Ligett et al. (2017), aborda isso permitindo que o limite de privacidade dependa dos dados privados, termo denominado "privacidade ex-post". Neste framework, um analista define um limiar mínimo de utilidade (precisão) e encontra o limite de privacidade mais forte que atende empiricamente a esse critimal. No entanto, as definições ex-post existentes negligenciaram uma propriedade crítica da DP padrão: a imunidade ao pós-processamento. Esta propriedade garante que um adversário não possa enfraquecer a garantia de privacidade simplesmente processando o resultado. Sem ela, uma garantia de privacidade poderia ser tornada mais fraca do que o prometido apenas transformando o output.

A literatura atual carece de uma análise abrangente de quais definições ex-post possuem imunidade ao pós-processamento, e a única definição comprovada de possuir tal imunidade (privacidade ex-post pura) carece de ferramentas práticas, como um análogo ex-post do mecanismo Gaussiano ou algoritmos para validar a precisão em conjuntos de dados privados separados.

Metodologia

1. Reformulação da Notação de Privacidade Ex-Post

Os autores identificam que a notação padrão para privacidade ex-post, onde o limite de privacidade $E$ é uma função do output $y$ ($E: \mathcal{Y} \to \mathbb{R}_{\geq 0}$), cria uma inconsistência lógica ao definir a imunidade ao pós-processamento. Se um mecanismo é pós-processado por uma função $f$, o domínio da função do limite de privacidade deve mudar, tornando difícil definir equivalência.

Para resolver isso, o artigo propõe uma nova notação onde o limite de privacidade é tratado como uma parte explícita do output do mecanismo. Um mecanismo $M$ é definido como uma função aleatória $M: \mathcal{X} \to \mathcal{Y} \times \mathbb{R}_{\geq 0}$, retornando um par $(y, \epsilon)$. O pós-processamento é definido como uma função aleatória $f$ aplicada ao par de saída, onde o limite de privacidade $\epsilon$ permanece inalterado (ou seja, $M'(X)_\epsilon = M(X)_\epsilon$).

2. Análise de Definições Existentes

Usando esta nova notação, os autores analisam as definições existentes:

• Privacidade Ex-Post Pura (Ligett et al., 2017): Provada possuir imunidade ao pós-processamento (para distribuições contínuas/discretas). No entanto, carece de ferramentas úteis para aplicações práticas, como um mecanismo Gaussiano ex-post.
• Privacidade Ex-Post Probabilística $\delta$ (Whitehouse et al., 2022): Provada não possuir imunidade ao pós-processamento quando $\delta > 0$. Os autores mostram que esta definição generaliza a DP probabilística $(\epsilon, \delta)$, que é conhecida por falhar na imunidade ao pós-processamento.

3. Proposta de Privacidade de Rényi Ex-Post (RDP)

Para preencher a lacuna entre a imunidade ao pós-processamento e a utilidade prática, os autores propõem uma nova definição baseada em Privacidade Diferencial de Rényi (RDP).

• Definição: Um mecanismo $M: \mathcal{X} \to \mathcal{Y} \times \mathbb{R}_{\geq 0}$ é $\alpha$-ex-post RDP se, para todos os conjuntos de dados vizinhos $X \sim X'$, a expectativa da função geradora de momentos da variável de perda de privacidade, ponderada pelo limite de privacidade retornado, for limitada por 1:
  $$\mathbb{E}_{(y, \epsilon) \sim M(X')} \left[ e^{(1-\alpha)\epsilon} \left( \frac{p_{M(X)}(y, \epsilon)}{p_{M(X')}(y, \epsilon)} \right)^\alpha \right] \leq 1$$
• Propriedades: Os autores provam que esta definição satisfaz a imunidade ao pós-processamento. Eles também estabelecem propriedades básicas, incluindo composição adaptativa e a capacidade de construir mecanismos com limites de privacidade totalmente adaptativos.

4. O Mecanismo Browniano

Os autores demonstram que o mecanismo browniano (Whitehouse et al., 2022), um análogo de precisão do mecanismo Gaussiano para o cenário de precisão-primeiro, satisfaz a $\alpha$-ex-post RDP.

• Mecanismo: Ele libera saídas ruidosas de uma função $f(X)$ com ruído Gaussiano correlacionado. Se o orçamento de privacidade for aumentado para uma liberação subsequente, a variância do ruído é reduzida. O output final é uma média ponderada pela precisão de todas as liberações intermediárias.
• Prova: Em vez de depender de processos estocásticos (movimento Browniano), os autores fornecem uma prova elementar modelando o mecanismo como um "mecanismo Gaussiano sequencial ponderado pela precisão" e mostrando sua equivalência ao mecanismo browniano sob a nova definição ex-post RDP.

5. Regras de Parada Dependentes de Dados

Uma contribuição teórica fundamental é um algoritmo (Algoritmo 1) para composição adaptativa com um critério de parada dependente de dados. Ao contrário de trabalhos anteriores que apenas verificavam a precisão no conjunto de treinamento, este algoritmo utiliza um conjunto de validação privado e distinto para determinar quando o limiar de precisão é atingido. Isso permite que o mecanismo pare antecipadamente, minimizando o orçamento de privacidade enquanto garante que a precisão de validação seja suficiente.

Principais Contribuições

1. Reformulação de Notação: Introduziu uma nova notação para privacidade ex-post onde o limite de privacidade é parte do output, permitindo uma definição rigorosa e elegante de imunidade ao pós-processamento.
2. Análise de Imunidade: Provou que a privacidade ex-post pura possui imunidade ao pós-processamento, enquanto a privacidade ex-post probabilística $\delta$ não possui.
3. Nova Definição: Propôs a $\alpha$-ex-post RDP, uma definição que possui imunidade ao pós-processamento e suporta o mecanismo browniano.
4. Ferramentas Teóricas: Desenvolveu teoria básica para ex-post RDP, incluindo teoremas de composição adaptativa e um método para construir mecanismos com regras de parada dependentes de dados usando conjuntos de validação privados.
5. Verificação de Mecanismo: Provou que o mecanismo browniano satisfaz a $\alpha$-ex-post RDP, fornecendo a primeira prova de imunidade ao pós-processamento para este mecanismo.
6. Aplicação Prática: Demonstrou o framework em duas aplicações:
   • Geração de Dados Sintéticos: Geração de dados tabulares onde o orçamento de privacidade é minimizado até que um classificador atinja uma precisão alvo em um conjunto de validação privado.
   • Ajuste Fino de Classificador de Imagem: Ajuste do limite de privacidade até que um limiar de precisão mínima seja atingido.

Resultados

• Limites Teóricos: Os autores compararam seu limite baseado em ex-post RDP para o mecanismo browniano contra os limites de privacidade ex-post probabilística de Whitehouse et al. (2022). Os resultados indicam que os limites são muito semelhantes (e potencialmente matematicamente iguais dentro do erro de ponto flutuante) quando os parâmetros livres são otimizados, sugerindo que ganhar imunidade ao pós-processamento não ocorre às custas da utilidade.
• Desempenho Experimental: Em experimentos usando o dataset UCI Adult para geração de dados sintéticos:
  • O mecanismo browniano conseguiu minimizar o custo de privacidade enquanto atendia aos limiares de precisão em um conjunto de validação privado.
  • O mecanismo utilizou uma lista de valores candidatos de $\epsilon$, começando pelo mais baixo e aumentando apenas se o limiar de precisão não fosse atingido.
  • Dois métodos para verificar o limiar de precisão sob DP foram testados: uma composição de mecanismos Gaussianos simples e a Técnica de Vetor Esparso (SVT). A SVT geralmente resultou em orçamentos de privacidade totais ($\epsilon$) menores, enquanto o método Gaussiano simples rendeu precisões de validação ligeiramente superiores.
  • O sistema conseguiu ajustar o limite de privacidade adaptativamente, demonstrando a praticidade da teoria.

Significância e Alegações

O artigo afirma preencher uma lacuna crítica na perspectiva de precisão-primeiro da privacidade diferencial. Ao identificar que as definições existentes ou carecem de imunidade ao pós-processamento ou carecem de ferramentas práticas, os autores fornecem um framework unificado que oferece ambos.

A significância reside em permitir fluxos de trabalho de privacidade adaptativos que anteriormente eram teoricamente incorretos ou praticamente difíceis. Especificamente:

• Permite que analistas reduzam a proteção de privacidade (aumentem $\epsilon$) apenas tanto quanto necessário para atingir um limiar de utilidade, sem comprometer a garantia contra ataques de pós-processamento.
• Fornece a primeira justificativa teórica para o uso do mecanismo browniano em um cenário ex-post com imunidade ao pós-processamento.
• Introduz um método para validar a precisão em conjuntos de validação privados em vez de conjuntos de treinamento, o que é crucial para prevenir o overfitting e garantir a generalização no aprendizado de máquina preservando a privacidade.

Os autores mantêm uma postura modesta, observando que, embora seu limite baseado em RDP ofereça flexibilidade e imunidade, ele herda as limitações de interpretabilidade do RDP em comparação com $f$-DP ou Gaussian DP. Eles sugerem que o desenvolvimento de versões ex-post dessas definições alternativas é uma direção promissora para pesquisas futuras.