Resumo Técnico: Privacidade Diferencial Métrica ao Nível do Usuário via Distância do Transportador de Terra (Earth Mover's Distance)

Declaração do Problema

A Privacidade Diferencial (DP) tornou-se o padrão para análise de dados, oferecendo tradicionalmente garantias de privacidade uniformes onde cada par de conjuntos de dados de entrada é tratado como igualmente sensível. No entanto, em muitas aplicações práticas, os dados exibem heterogeneidade; por exemplo, revelar a cidade exata de residência de um usuário é mais sensível do que revelar seu país. A Privacidade Diferencial Métrica (Metric DP) aborda isso degradando a garantia de privacidade linearmente com a distância entre os pares de entrada, permitindo melhor utilidade quando os inputs são similares.

Embora trabalhos anteriores em Metric DP tenham se concentrado no cenário de nível de item (onde cada usuário contribui com um único item de dado), cenários do mundo real frequentemente envolvem contribuições de nível de usuário, onde um único usuário fornece uma coleção de itens (por exemplo, um histórico de localizações ou um conjunto de palavras). As estruturas existentes de DP de nível de usuário dependem da DP padrão, tratando todas as mudanças ao conjunto de dados de um usuário como igualmente sensíveis, independentemente da magnitude ou da natureza da mudança. Este artigo inicia o estudo da Metric DP ao nível do usuário, especificamente utilizando a Distância do Transportador de Terra (dEM) como a métia subjacente. O objetivo é definir uma noção de privacidade onde a sensibilidade da contribuição de um usuário depende tanto da fração de dados alterados quanto da distância dessas mudanças, capturando uma semântica de privacidade mais matizada do que a DP de nível de usuário padrão.

Metodologia

1. Definindo dEM-DP

Os autores definem dEM-DP medindo a distância entre dois conjuntos de dados de usuários $K$ e $K'$ usando a Distância do Transportador de Terra (também conhecida como distância 1-Wasserstein).

• Métrica: $d_{EM}(\tilde{K}, \tilde{K}')$ representa o custo mínimo de transportar a distribuição de probabilidade do conjunto de dados $K$ para $K'$, onde o custo é a quantidade de dados movidos multiplicada pela distância $d_X$ entre os itens.
• Garantia de Privacidade: Um mecanismo $M$ satisfaz $(\alpha, \delta)$-bounded dEM-DP para quaisquer conjuntos de dados $K, K'$ do mesmo tamanho:
  $$\Pr[M(K) \in O] \le e^{\alpha \cdot d_{EM}(\tilde{K}, \tilde{K}')} \Pr[M(K') \in O] + \delta$$
  Aqui, o parâmetro de privacidade escala com a distância. Se $d_{EM}$ for pequeno (conjuntos de dados similares), a garantia de privacidade é mais forte (menor $\epsilon$ efetivo) comparada à DP padrão, que aplicaria um $\epsilon$ uniforme.

2. Design de Mecanismo

O artigo propõe dois novos mecanismos para liberar consultas sob dEM-DP tanto no Modelo Local (usuários privatizam os dados antes de enviar) quanto no Modelo Central (agregador confiável detém os dados).

A. Consultas Lineares (PrivEMDLinear)

Para consultas lineares da forma $F\tilde{K}$, os autores analisam a sensibilidade sob dEM.

• Análise de Sensibilidade: Ao contrário da DP padrão, que exige que a função de consulta seja limitada, a análise de dEM-DP exige que a função $f$ (representando a consulta) seja Lipschitz contínua.
• Resultado: Os autores provam que a sensibilidade de uma consulta linear sob dEM é limitada superiormente pela constante de Lipschitz da função da consulta. Isso permite a adição de ruído calibrado (por exemplo, usando o mecanismo K-norm ou o mecanismo Gaussiano) que é proporcional à constante de Lipschitz em vez de um limite global de pior caso, melhorando a utilidade.

B. Consultas de Itens Não Ordenados (PrivEMDItemWise)

Para liberar um conjunto de saídas ruidosas para cada item em um conjunto de dados de usuário (por exemplo, um histograma), o mecanismo aplica um mecanismo de DP de nível de item base $A$ a cada item e, em seguida, embaralha (shuffles) os resultados.

• Amplificação de Privacidade por Embaralhamento: Os autores generalizam o resultado de "amplificação de privacidade por embaralhamento" para o cenário de DP métrica. Como a saída é uma lista não ordenada, um adversário não pode vincular saídas específicas a índices de entrada específicos.
• Inovação Técnica: Eles provam que o embaralhamento de $m$ itens reduz o custo de privacidade de $O(m\alpha)$ (via composição) para $O(\alpha\sqrt{m})$. Este resultado é derivado analisando o acoplamento entre vetores de entrada e aproveitando as propriedades do modelo de embaralhamento.

3. Extensão para Dados Não Limitados (Unbounded)

Conjuntos de dados do mundo real frequentemente têm tamanhos variados por usuário (cenário não limitado), o que complica a análise de dEM porque o próprio tamanho do conjunto de dados torna-se uma preocupação de privacidade.

• Redução: Os autores propõem uma redução black-box de dEM-DP não limitado para limitado.
• Mecanismo: Eles utilizam amostragem com reposição para projetar qualquer conjunto de dados de usuário em um tamanho fixo $s$. Eles provam que essa projeção é "suave", o que significa que a distância dEM entre os conjuntos de dados projetados é próxima da distância dEM entre os conjuntos de dados originais (até um pequeno fator aditivo).
• dEM-DP Discreta: Para lidar com o erro aditivo da amostragem, eles introduzem uma definição "discreta" de dEM-DP onde mudanças com distância $\le r$ são protegidas uniformemente. Eles mostram que, para tamanhos de amostra suficientemente grandes, o dEM-DP não limitado pode ser reduzido ao dEM-DP limitado com perda negligenciável na semântica de privacidade.

Principais Contribuições

1. Definição de Metric DP ao Nível do Usuário: O artigo estabelece uma definição formal de Metric DP ao nível do usuário usando a Distância do Transportador de Terra, capturando tanto os aspectos espaciais quanto os de magnitude das mudanças de dados.
2. Novos Mecanismos:
   • PrivEMDLinear: Um mecanismo para consultas lineares que aproveita a continuidade de Lipschitz para limitar a sensibilidade, oferecendo melhor utilidade do que a DP de nível de usuário padrão para tipos específicos de consultas.
   • PrivEMDItemWise: Um mecanismo geral para consultas de nível de item que utiliza embaralhamento. Os autores fornecem uma análise de ampliação de privacidade generalizada mostrando uma melhoria de $\sqrt{m}$ sobre os limites de composição padrão.
3. Redução para Não Limitados: Uma técnica de redução black-box que converte mecanismos de dEM-DP limitados em não limitados via amostragem, permitindo a aplicação desses mecanismos a conjuntos de dados com tamanhos variáveis de contribuição do usuário.
4. Melhorias de Utilidade: A análise teórica demonstra que os mecanismos de dEM-DP podem alcançar estritamente melhor utilidade (menor erro) do que os baselines de DP de nível de usuário padrão para:
   • Consultas de Embedding Linear: Tanto nos modelos central quanto local, particularmente quando o parâmetro de privacidade $\alpha$ pode ser maior que o $\epsilon$ padrão para inputs dissimilar.
   • Estimativa de Frequência: No modelo local, o erro é melhorado quando o tamanho do domínio e os parâmetros de privacidade satisfazem condições específicas, aproveitando o fato de que apenas itens "próximos" (dentro de clusters) exigem privacidade forte.

Resultados e Significância

O artigo afirma que o dEM-DP oferece uma definição de privacidade mais refinada que se alinha melhor com as semânticas de privacidade do mundo real.

• Semântica de Privacidade: Na DP padrão, mudar os dados de um usuário por um mês inteiro é tratado com a mesma sensibilidade que mudar um único dia de dados. No dEM-DP, a mudança de um único dia é considerada menos sensível (menor $d_{EM}$), permitindo menos ruído e maior utilidade, enquanto uma mudança de um mês recebe uma garantia mais forte.
• Ganhos de Utilidade: Limites teóricos mostram que os mecanismos de dEM-DP podem superar a DP de nível de usuário padrão em termos de utilidade. Por exemplo, na estimativa de frequência, a dependência do erro em relação ao tamanho do domínio $k$ e ao parâmetro de privacidade é melhorada sob dEM-DP quando os dados exibem estrutura (por exemplo, métricas agrupadas/clustered).
• Generalização: A redução para cenários limitados e a análise de embaralhamento geral sugerem que essas técnicas podem ser aplicadas amplamente a vários espaços métricos e tipos de consulta além dos exemplos específicos (localização, texto, grafos) fornecidos.

Os autores posicionam este trabalho como o primeiro a propor uma definição geral de Metric DP ao nível do usuário via dEM, indo além de aplicações específicas baseadas em texto para um framework aplicável a espaços métricos gerais. Eles enfatizam que, embora o dEM-DP seja uma relaxação da DP padrão, ele fornece um trade-off mais prático para aplicações onde a similaridade dos dados correlaciona-se com a sensibilidade.