Missing Mass for Differentially Private Domain Discovery

Resumo Técnico: Missing Mass for Differentially Private Domain Discovery

1. O Problema

O artigo aborda o desafio da descoberta de domínio em contextos de Privacidade Diferencial (DP). Em muitas aplicações modernas de análise de dados (como consultas, avaliações e históricos de compras), o domínio dos itens (o conjunto de todas as possíveis strings ou IDs) é desconhecido a priori ou impraticavelmente grande.

O objetivo fundamental é extrair um subconjunto informativo de itens de um conjunto de dados distribuído entre vários usuários, onde cada usuário possui um subconjunto de itens, sem revelar informações sensíveis sobre os dados individuais.

• Desafio Principal: A maioria dos algoritmos existentes para união de conjuntos (set union) e seleção de top-k em domínio desconhecido carece de garantias teóricas de utilidade rigorosas. A métrica tradicional de cardinalidade (número de itens únicos recuperados) muitas vezes não reflete a utilidade real para aplicações downstream, especialmente quando a distribuição de frequência dos itens segue leis de potência (como a Lei de Zipf).
• Métrica Proposta: Os autores propõem focar na "Massa Ausente" (Missing Mass), definida como a fração da frequência total dos itens que não foi recuperada pelo algoritmo, em vez de apenas contar o número de itens.

2. Metodologia

A abordagem central do trabalho baseia-se no uso do Mecanismo Gaussiano Ponderado (Weighted Gaussian Mechanism - WGM) como um precursor para a descoberta de domínio, seguido por algoritmos existentes para problemas específicos.

• Mecanismo Gaussiano Ponderado (WGM):

  • O WGM é um mecanismo simples e escalável que adiciona ruído gaussiano a um histograma ponderado das contribuições dos usuários.
  • Ele opera em três etapas: (1) Subamostragem das contribuições de cada usuário para limitar a norma $\ell_2$; (2) Construção de um histograma ponderado; (3) Adição de ruído gaussiano e aplicação de um limiar para selecionar os itens.
  • O WGM garante a propriedade de "sonoridade" (soundness): um item só aparece na saída se estiver presente na entrada.

• Abordagem em Duas Etapas (Meta-Algoritmo):
  Para problemas como Top-k e k-Hitting Set em domínio desconhecido, os autores propõem um meta-algoritmo:

  1. Descoberta de Domínio: Executar o WGM com metade do orçamento de privacidade para obter um domínio candidato $D$ (um subconjunto de itens prováveis).
  2. Seleção no Domínio Conhecido: Executar um algoritmo privado padrão para domínio conhecido (como o Mecanismo Exponencial de Descascamento ou algoritmos greedy para submodularidade) sobre o domínio $D$ com a outra metade do orçamento.

• Análise de Distribuição:

  • Para o problema de união de conjuntos, os autores analisam a utilidade sob a suposição de que os dados seguem uma distribuição Zipfiana (Lei de Potência), onde a frequência dos itens decai polinomialmente.
  • Eles provam limites superiores para a massa ausente ($\ell_1$) e para a massa ausente máxima ($\ell_\infty$) sem assumir Zipfianidade para o caso $\ell_\infty$.

3. Contribuições Principais

1. Garantias de Utilidade para WGM:

   • Demonstram que o WGM possui uma garantia de massa ausente $\ell_1$ quase ótima para dados Zipfianos.
   • Provam uma garantia de massa ausente $\ell_\infty$ livre de distribuição (distribution-free), que é crucial para problemas de seleção de top-k e hitting set.
   • Estabelecem limites inferiores (lower bounds) que mostram que a dependência linear em $k/\epsilon$ para a massa ausente é inevitável para algoritmos que satisfazem a restrição de saída no domínio de entrada.

2. Novos Algoritmos para Domínio Desconhecido:

   • Privacidade Top-k: Apresentam um algoritmo que combina WGM com o Mecanismo Exponencial de Descascamento (Peeling Exponential Mechanism), provando garantias de utilidade para a massa ausente top-k.
   • Privacidade k-Hitting Set: Adaptam o algoritmo greedy para maximização submodular privada (User Peeling Mechanism) para o cenário de domínio desconhecido, provando que a solução obtida se aproxima do ótimo com um erro aditivo controlado.

3. Análise Teórica Rigorosa:

   • São, até onde se sabe, os primeiros a provar garantias de utilidade absolutas (não relativas a outros algoritmos) para união de conjuntos em DP.
   • Mostram que a restrição de não gerar itens fora do domínio observado (Assunção 1) impõe limites fundamentais na precisão, mas que o WGM atinge esses limites de forma eficiente.

4. Resultados Experimentais

Os autores avaliaram seus métodos em seis conjuntos de dados reais (Reddit, Amazon Games, Movie Reviews, Steam Games, etc.) com orçamentos de privacidade $(\epsilon=1, \delta=10^{-5})$ e $(\epsilon=0.1, \delta=10^{-5})$.

• União de Conjuntos (Set Union): O WGM obteve uma massa ausente dentro de 5% dos mecanismos de política (Policy Mechanisms) mais complexos e sequenciais, mas com escalabilidade significativamente superior.
• Top-k: O método proposto (WGM + Top-k) superou consistentemente o mecanismo de domínio limitado de Durfee & Rogers (2019), especialmente à medida que $k$ aumentava. A vantagem cresceu com o tamanho de $k$.
• k-Hitting Set: O método performou comparável ou superior a algoritmos base line que assumem conhecimento público do domínio total (o que não é realista em cenários privados). O WGM conseguiu filtrar o domínio para itens de alta qualidade, facilitando a segunda etapa do algoritmo.

5. Significado e Impacto

• Ponte entre Teoria e Prática: O trabalho preenche uma lacuna crítica entre a teoria da Privacidade Diferencial e a prática industrial, fornecendo garantias matemáticas para algoritmos que já são usados em frameworks como OpenDP e LinkedIn.
• Mudança de Paradigma na Métrica: Ao focar na "Massa Ausente" em vez da cardinalidade, o paper alinha melhor a avaliação de algoritmos de privacidade com a utilidade real para tarefas de análise de dados (onde recuperar itens frequentes é mais importante do que recuperar muitos itens raros).
• Escalabilidade: A demonstração de que um mecanismo simples e não sequencial (WGM) pode competir ou superar métodos sequenciais complexos em termos de utilidade, mantendo alta escalabilidade, é um avanço significativo para a implementação em larga escala.
• Fundação para Futuros Trabalhos: O estabelecimento de limites inferiores e superiores para problemas de domínio desconhecido abre caminho para o fechamento de lacunas teóricas e o desenvolvimento de estratégias de subamostragem mais sofisticadas.

Em resumo, o paper estabelece o WGM como uma ferramenta fundamental e teoricamente fundamentada para a descoberta de domínio em privacidade diferencial, oferecendo garantias de utilidade robustas e desempenho empírico superior em cenários de dados reais.