Resumo Técnico: Maximização Submodular com Privacidade Diferencial sob uma Restrição de Mochila

1. Definição do Problema

O artigo aborda o problema de Maximização Submodular sujeita a uma Restrição de Mochila (SMK) sob o framework de Privacidade Diferencial (DP).

• Contexto SMK: Dado um conjunto fundamental $N$ de $n$ elementos, uma função objetivo submodular $f: 2^N \to \mathbb{R}$, uma função de custo $c: N \to \mathbb{R}_{>0}$ e um orçamento $B$, o objetivo é encontrar um subconjunto $S \subseteq N$ tal que $\sum_{v \in S} c(v) \leq B$ e $f(S)$ seja maximizado. Este problema é NP-difícil e onipresente em aplicações de aprendizado de máquina, como seleção de características, sumarização de dados e maximização de influência.
• Configuração de Privacidade: A função objetivo $f_D$ depende de um conjunto de dados sensível $D$. O algoritmo deve produzir uma solução $S$ enquanto satisfaz a privacidade diferencial $(\epsilon, \delta)$, garantindo que a distribuição da saída mude de forma desprezível quando os dados de um único indivíduo em $D$ é modificado.
• Escopo: O trabalho considera funções objetivo tanto monótonas quanto não-monótonas.

2. Metodologia e Desafios Técnicos

Os autores identificam que as técnicas padrão para maximização submodular com DP (frequentemente projetadas para restrições de cardinalidade) são subótimas para restrições de mochila devido a dois desafios principais:

1. Variabilidade da Sensibilidade dos Scores de Densidade: Em configurações de mochila, algoritmos tipicamente selecionam elementos baseados em "densidade" (ganho marginal dividido pelo custo). Ao contrário das restrições de cardinalidade, onde a sensibilidade é uniforme, a sensibilidade de um score de densidade $f(u|S)/c(u)$ depende inversamente do custo do elemento $c(u)$. Uma aplicação ingênua de mecanismos de seleção padrão (como o Mecanismo Exponencial) incorreria em um erro aditivo proporcional a $\Delta f \cdot (B/c_{\min})$, levando a uma dependência subótima do tamanho máximo da solução viável $k$.

   • Resolução: Os autores empregam o mecanismo Generalized Report Noisy Max (GRNM) (Raskhodnikova & Smith, 2016). Este mecanismo se adapta às sensibilidades individuais dos candidatos, garantindo que o erro aditivo escale com a sensibilidade específica do candidato selecionado, em vez do limite de pior caso.

2. Gargalo de Composição: Algoritmos de estado da arte para SMK monotônica não-privada (ex: Two-Guess-Greedy) exigem $O(n^2)$ iterações para adivinhar elementos ótimos. Teoremas de composição avançada padrão resultariam em um termo de erro escalando polinomialmente com $n$, anulando os benefícios da privacidade.

   • Resolução: Os autores utilizam o framework de Seleção Privada Generalizada (Cohen et al., 2023). Ao randomizar o número de vezes que cada etapa de enumeração é invocada, eles desacoplam a perda de privacidade do número total de sub-rotinas, alcançando um erro aditivo com dependência polilogarítmica de $n$.

3. Contribuições Principais e Algoritmos

A. Funções Objetivo Monótonas

O artigo propõe dois algoritmos para o caso monotônico:

1. DP-2GG (Algoritmo 2): Uma adaptação diferencialmente privada do algoritmo "Two-Guess-Greedy" (Feldman et al., 2023).

   • Mecanismo: Ele itera sobre todos os subconjuntos $Y \subseteq N$ de tamanho no máximo 2. Para cada $Y$, ele executa uma sub-rotina de densidade-gulosa privatizada (Algoritmo 1) na instância residual. A solução final é selecionada a partir das saídas ruidosas dessas sub-rotinas usando o framework de Seleção Generalizada.
   • Garantias: Alcança uma aproximação de $(1 - 1/e)$.
   • Complexidade: $O(\beta^{-1} n^3 k)$ consultas de oráculo.
   • Erro: O erro aditivo escala como $O(\frac{\Delta k^{1.5}}{\epsilon} \sqrt{\log n} \dots)$, superando trabalhos anteriores ao remover a dependência polinomial de $n$ e $1/c_{\min}$.

2. DP-DG+ (Algoritmo 7): Um algoritmo de passagem única mais rápido baseado em Density-Greedy+.

   • Mecanismo: Executa uma passagem de densidade-gulosa privatizada uma única vez e seleciona a melhor solução entre as soluções parciais e suas extensões de elemento único viáveis usando Report Noisy Max (RNM).
   • Garantias: Alcança uma aproximação de $1/2$.
   • Complexidade: $O(nk)$ consultas de oráculo.
   • Erro: Erro aditivo melhorado comparável ao caso monotônico.

B. Funções Objetivo Não-Monótonas

O artigo introduz o primeiro algoritmo diferencialmente privado com garantias prováveis para SMK não-monotônica.

• Algoritmo: DP-SDG (Algoritmo 3), uma adaptação privatizada do algoritmo SmkRan não-privado (Han et al., 2021).
• Mecanismo: Realiza seleções baseadas em densidade usando GRNM. Elementos selecionados são adicionados à solução com probabilidade $1/2$ (descarte randomizado) para lidar com a não-monotonicidade. Crucialmente, ele continua iterando mesmo se os ganhos marginais se tornarem negativos (dev devido ao ruído) e usa RNM para selecionar a melhor solução observada de todas as soluções parciais e suas extensões.
• Análise de Privacidade: Para lidar com a incerteza no número de etapas de seleção, os autores derivam um limite de concentração mostrando que o total de iterações é estocasticamente dominado por uma soma de variáveis aleatórias geométricas, concentrando-se em torno de $O(k)$.
• Garantias: Alcança uma aproximação de $1/4$ em expectativa.
• Complexidade: $O(nk)$ consultas de oráculo.
• Erro: Erro aditivo comparável ao caso monotônico.

4. Resultados e Avaliação Empírica

Resultados Teóricos

Os autores comparam seus resultados com trabalhos anteriores (especificamente Sadeghi & Fazel, 2021) na Tabela 1. As principais melhorias incluem:

• Razões de Aproximação: Igualando as melhores razões conhecidas não-privadas ($(1-1/e)$ para monotônica, $1/4$ para não-monotônica).
• Erro Aditivo: Dependência significativamente melhorada do tamanho do conjunto fundamental $n$ (polilogarítmica vs. polinomial) e do tamanho máximo da solução viável $k$ (escalando com $k^{1.5}$ vs. $k$ ou pior em trabalhos anteriores).
• Complexidade de Consulta: Polinomial em $n$ e $k$, enquanto o trabalho anterior para SMK monotônica dependia da avaliação exata da extensão multilinear exigindo $O(2^n)$ consultas.

Resultados Empíricos

Os algoritmos foram avaliados em uma tarefa de otimização de transporte por aplicativo usando um conjunto de dados de 100.000 locais de embarque da Uber em Manhattan.

• Utilidade: Para $\epsilon \geq 0.1$, os algoritmos DP (DP-2GG, DP-DG+, DP-SDG) alcançam utilidade comparável aos seus equivalentes não-privados (2GG, DG+, SmkRan), superando substancialmente um baseline aleatório. Em $\epsilon=0.2$, o DP-2GG está a 2% do 2GG não-privado.
• Escalabilidade: DP-DG+ e DP-SDG exibem crescimento linear em consultas de oráculo em relação ao tamanho do conjunto fundamental $n$, confirmando sua eficiência prática em comparação ao mais intensivo em consultas, DP-2GG.

5. Significância e Alegações

O artigo afirma preencher lacunas críticas na literatura de otimização combinatória com privacidade diferencial:

1. Primeira SMK Não-Monotônica Provável: Estabelece as primeiras garantias prováveis para SMK não-monotônica sob privacidade diferencial.
2. Melhores Limites Monotônicos: Melhora tanto a utilidade (erro aditivo) quanto a complexidade de consulta dos algoritmos de SMK monotônica, afastando-se da complexidade de consulta exponencial de abordagens anteriores.
3. Lidando com Restrições de Mochila: Demonstra que os desafios específicos das restrições de mochila (variabilidade de sensibilidade e gargalos de composição) podem ser superados usando mecanismos de seleção generalizados e limites de concentração, alcançando resultados que igualam a eficiência das configurações de restrição de cardinalidade.

Os autores observam que, embora sua dependência de erro aditivo em $k$ coincida com a melhor conhecida para algoritmos de tempo polinomial em configurações de cardinalidade, a questão de se uma dependência melhor de $k$ é alcançável sob sensibilidade limitada permanece aberta. Eles também sugerem estender essas técnicas para combinações de restrições de mochila e matróide como uma direção para trabalhos futuros.