Resumo Técnico: Diversificação de Soma Máxima Rápida e Privada

Formulação do Problema

O artigo aborda o problema da Diversificação de Soma Máxima (MSD - Max-Sum Diversification) sob as restrições de Privacidade Diferencial (DP - Differential Privacy). A MSD é um problema fundamental de sumarização de dados e diversificação de resultados de consultas, visando selecionar um subconjunto de itens que equilibra relevância e diversidade.

Dado um conjunto fundamental $V$ de $n$ itens, um conjunto de dados sensíveis $D$, uma função de relevância submodular monótona $f_D$, e uma função de distância pseudométrica $d_D$, o objetivo é encontrar um subconjunto viável $S$ (sujeito a restrições) que maximize:
$$\phi_D(S) = f_D(S) + \lambda \cdot d_D(S)$$
onde $\lambda \geq 0$ controla o equilíbrio entre relevância e diversidade. O termo $d_D(S)$ representa a soma das distâncias par a par entre os itens em $S$.

O desafio surge porque a função objetivo $\phi_D$ não é submodular (pois a soma das distâncias par a par é supermodular), tornando as técnicas padrão de maximização de submodularidade DP inaplicáveis. Além disso, os dados subjacentes $D$ (por exemplo, históricos de compras de usuários ou logs de localização) são sensíveis, exigindo que o algoritmo de seleção forneça garantias formais de privacidade (especificamente $(\varepsilon, \delta)$-DP) para evitar o vazamento de informações individuais.

O artigo considera dois tipos primários de restrições:

1. Restrições de Cardinalidade: Seleção de um subconjunto de tamanho no máximo $k$.
2. Restrições de Matroide: Uma generalização que captura critérios de viabilidade mais complexos (ex: restrições de partição).

Metodologia

Os autores propõem um conjunto de algoritmos diferencialmente privados adaptados a essas restrições, utilizando o Mecanismo Exponencial (EM - Exponential Mechanism) para seleção privada e Amostragem de Subconjuntos (Subset Sampling) para melhorar a eficiência.

1. Algoritmos Gananciosos (Greedy) para Restrições de Cardinalidade

• DP-Greedy (Algoritmo 1): Uma adaptação direta do algoritmo ganancioso não-obliquo de Borodin et al. [8]. Ele seleciona iterativamente elementos usando o Mecanismo Exponencial baseado em uma função auxiliar $\phi'(S) = \frac{1}{2}f_D(S) + \lambda d_D(S)$.
  • Complexidade: $O(nk)$ chamadas de oráculo.
  • Garantia: Alcança uma aproximação de $1/2$ (em expectativa) com erro aditivo dependente da sensibilidade e dos parâmetros de privacidade.
• DP-NOSG (Algoritmo 2 - Non-Oblivious Sample Greedy): Para abordar o gargalo de $O(nk)$, este algoritmo emprega uma abordagem de "amostragem gananciosa". Em cada iteração, ele amostra um subconjunto menor de candidatos em vez de avaliar todo o conjunto fundamental.
  • Complexidade: $O(n \log k \log \gamma^{-1})$ chamadas de oráculo.
  • Garantia: Alcança uma aproximação de $(1/2 - \gamma)$.
• DP-OSG (Algoritmo 2 - Oblivious Sample Greedy): Uma variante que utiliza uma função objetivo oblíqua e uma estratégia de amostragem diferente para alcançar complexidade de tempo linear.
  • Complexidade: $O(n \log \gamma^{-1})$ chamadas de oráculo (independente de $k$).
  • Garantia: Alcança uma aproximação de $(1 - 2/e - \gamma - 1/k)$.

Melhorias de Privacidade: Para objetivos decomponíveis (onde a função pode ser expressa como uma soma de funções dependentes de registros únicos), os autores estendem técnicas de Gupta et al. [33] para fornecer garantias de privacidade mais fortes. Especificamente, para funções decomponíveis, a perda de privacidade não escala linearmente com $k da mesma maneira que a composição geral, permitindo uma injeção de ruído mais rigorosa e melhor utilidade.

2. Busca Local para Restrições de Matroide

• DP-SLS (Algoritmo 3 - Sample Local Search): Como as abordagens gananciosas falham em fornecer aproximações de fator constante para MSD sob restrições de matroide, os autores propõem um algoritmo de busca local privado.
  • Mecanismo: O algoritmo realiza um número fixo de iterações ($T'$). Em cada etapa, ele subamostra um conjunto de trocas candidatas (adicionando um elemento e removendo outro) e usa o Mecanismo Exponencial para selecionar uma troca. Inclui uma "troca fictícia" (dummy swap) para permitir que a solução permaneça inalterada se nenhuma troca de melhoria for encontrada. Finalmente, seleciona privadamente a melhor solução observada em todas as iterações.
  • Complexidade: $O(\gamma^{-1} n k \log k)$ chamadas de oráculo, uma melhoria significativa em relação aos $O(n^2 + \gamma^{-1} n k^2 \log k)$ da linha de base não-privada.
  • Garantia: Alcança uma aproximação de $(1/2 - \gamma)$ em expectativa.

Principas Contribuições

1. Iniciação do Estudo de DP-MSD: Este trabalho é o primeiro a estudar formalmente o problema de Diversificação de Soma Máxima sob privacidade diferencial, abordando a lacuna onde os métodos de submodularidade DP existentes não podem ser aplicados diretamente devido à natureza não-submodular do termo de diversidade.
2. Garantias de Utilidade Próximas ao Ótimo: Os algoritmos propostos alcançam razões de aproximação que igualam ou quase igualam os limites teóricos inferiores para MSD não-privado (ex: $1/2$ para restrições de cardinalidade) enquanto satisfazem garantias estritas de privacidade.
3. Eficiência Melhorada: Os autores projetam algoritmos que não são apenas privados, mas também mais rápidos que os métodos não-privados existentes.
   • Para restrições de cardinalidade, as abordagens baseadas em amostragem reduzem as chamadas de oráculo de $O(nk)$ para $O(n \log k)$ ou até $O(n)$.
   • Para restrições de matroide, a abordagem de busca local reduz a complexidade de $O(n^2)$ para $O(nk \log k)$.
4. Análise de Privacidade Decomponível: O artigo estende as técnicas de análise de privacidade para objetivos decomponíveis ao cenário de MSD, fornecendo limites de erro aditivo mais rigorosos e melhores parâmetros de privacidade em comparação com a composição geral.

Resultados Experimentais

Os autores avaliaram seus algoritmos em dois conjuntos de dados do mundo real: locais de embarque da Uber em Manhattan e avaliações de produtos da Amazon (categoria Health Care).

• Utilidade: Sob orçamentos de privacidade fortes (ex: $\varepsilon = 0.1$), os algoritmos DP propostos alcançam utilidade comparável às linhas de base não-privadas.
  • Para restrições de cardinalidade, o DP-Greedy e o DP-NOSG permanecem dentro de 1% da linha de base gananciosa não-privada.
  • Para restrições de matroide, o DP-SLS permanece dentro de 1% da linha de base de busca local não-privada.
  • Em contraste, as linhas de base que ignoram a diversidade (DP-RelG) ou que dependem de seleção aleatória apresentam desempenho significativamente inferior (17–30% menos utilidade).
• Eficiência:
  • Cardinalidade: DP-NOSG e DP-OSG demonstraram acelerações de 14x e 50x, respectivamente, em comparação com o algoritmo ganancioso não-privado em $k=100$, devido à redução de chamadas de oráculo.
  • Matroide: Embora o DP-SLS reduza o número total de chamadas de oráculo em comparação com a linha de base não-privada, o número fixo de iterações e o overhead do Mecanismo Exponencial resultam em tempos de execução até 2.2x mais lentos em alguns regimes. No entanto, ele apresenta melhor escalabilidade com o tamanho do conjunto fundamental $n$.

Significância e Alegações

O artigo afirma que a diversificação de resultados é crucial para resumos de dados informativos, mas frequentemente envolve dados sensíveis, necessitando de métodos que preservem a privacidade. Os autores afirmam que seu trabalho:

• Preenche uma lacuna crítica: Fornece o primeiro framework formal para MSD privado, permitindo aplicações como recomendações de produtos com preservação de privacidade e sumarização de localização.
• Oferece valor duplo: Os algoritmos propostos são valiosos mesmo em cenários não-privados, pois oferecem melhor complexidade de tempo (execução mais rápida) em comparação com métodos não-privados de última geração.
• Alcança equilíbrios próximos ao ótimo: Os algoritmos equilibram com sucesso o "trilema" de privacidade, utilidade e eficiência, alcançando utilidade comparável aos métodos não-privados enquanto reduzem significativamente o overhead computacional para grandes conjuntos de dados.

Os autores reconhecem limitações, observando que suas restrições de matroide atualmente se aplicam a funções $\Delta$-sensíveis gerais em vez de explorar a decomponibilidade para limites mais rigorosos, e que o algoritmo de tempo linear mais rápido ($O(n)$) ainda não alcança a razão de aproximação estrita de $1/2$. Eles identificam a extensão dessas garantias e a aceleração da execução prática como direções para trabalhos futuros.