Resumo Técnico: Aprendizado de Modos Não Paramétrico com Privacidade Diferencial com Aplicações em Regressão e Agrupamento

Declaração do Problema

A estimativa de modos de densidade — maximizadores locais de uma função de densidade de probabilidade — é um problema fundamental em estatística, oferecendo resumos localizados e interpretáveis de distribuições multimodais complexas. Ao contrário de resumos globais (ex: média ou mediana), os modos revelam subpopulações heterogêneas e são críticos em aplicações que variam desde agrupamento (clustering) e classificação até visão computacional e regressão não paramétrica. No entanto, recuperar modos é inerentemente não regular; pequenas perturbações na densidade podem criar ou destruir pontos críticos, tornando a estimativa sensível à suavidade local, curvatura e separação.

Embora exista uma pesquisa significativa sobre métodos de privacidade diferencial (DP) para médias, regressão e agrupamento, a estimativa privada de modos permanece amplamente inexplorada. Abordagens existentes, como o método baseado em vizinhos mais próximos de Pacchiano et al. (2021), são limitadas a configurações de modo único ou carecem de garantias de otimalidade dependentes de suavidade. Este artigo aborda o desafio de recuperar múltiplos modos de densidade a partir de dados sensíveis, fornecendo garantias rigorosas de privacidade $(\varepsilon, \delta)$.

Metodologia: DP-GRAMS

Os autores propõem o DP-GRAMS (Differentially Private GRadient Ascent for Mode Seeking), um algoritmo de múltiplos estágios que adapta o procedimento clássico de mean-shift para um cenário de privacidade diferencial. O método aproveita a equivalência entre o mean shift e o gradiente ascendente no log-densidade (função de pontuação/score).

1. Estimativa de Pontuação Estabilizada

Para garantir a privacidade, o algoritmo não opera diretamente no gradiente da log-densidade bruta $\nabla \log \hat{p}(x)$, que pode ser altamente sensível a observações extremas. Em vez disso, ele emprega um estimador de pontuação estabilizado:
$$\hat{s}_{A, p_{floor}}(x) = \frac{\text{clip}_A(\nabla \hat{p}(x))}{\max\{\hat{p}(x), p_{floor}\}}$$
onde $\hat{p}(x)$ é um Estimador de Densidade Kernel (KDE). O numerador é limitado (clipped) a um nível $A$ para restringir a sensibilidade, e o denominador é limitado por um piso $p_{floor}$ para evitar a divisão por valores próximos de zero.

2. Pipeline de Três Estágios

O algoritmo procede em três fases distintas:

• Inicialização Privada Sensível à Densidade (DAP):
  Encontrar modos requer uma boa inicialização. Os autores introduzem um esquema DAP que amostra pontos iniciais de uma grade pública. Ele utiliza o mecanismo exponencial com uma função de utilidade baseada na massa empírica local (aproximando a densidade local). Crucialmente, emprega uma regra de supressão local: após selecionar uma âncora, todos os pontos da grade dentro de um raio $\rho_{init}$ são removidos do conjunto de candidatos. Isso garante uma cobertura diversificada de regiões de alta densidade (bacias modais) sem selecionar repetidamente a mesma vizinhança, alcançando cobertura de alta probabilidade de todos os verdadeiros modos com $k \asymp M \log n$ sorteios.

• Ascensão de Gradiente Ruidosa Correlacionada:
  A partir de cada inicialização, o algoritmo realiza uma ascensão de gradiente estocástica no estimador de pontuação estabilizada. Para satisfazer a privacidade:

  • Corte de Gradiente (Gradient Clipping): As contribuições de pontuação são limitadas.
  • Ruído Correlacionado: Como múltiplas trajetórias partem de pontos diferentes, mas podem convergir para o mesmo modo, adicionar ruído independente a cada trajetória incorreria em um custo de privacidade proibitivo. Em vez disso, o DP-GRAMS adiciona ruído Gaussiano correlacionado em cada iteração. A estrutura de correlação é induzida por um kernel exponencial baseado na proximidade espacial das iterações atuais. Isso permite a liberação conjunta de múltiplas trajetórias sob um único orçamento de privacidade.

• Fusão (Merging):
  A etapa final funde candidatos a modos próximos produzidos pelas trajetórias de ascensão. Se o número de modos for desconhecido, utiliza-se uma fusão baseada em raio; se conhecido, aplica-se o agrupamento de ligação de Ward (Ward-linkage agglomerative clustering). Esta etapa de pós-processamento é determinística e não consome orçamento de privacidade adicional.

3. Extensões

O framework é estendido para duas tarefas subsequentes:

• DP-PMS: Um método de regressão modal privado que atualiza na direção da resposta para estimar modos condicionais.
• DP-GRAMS-C: Um pipeline de agrupamento que libera centros modais privados e atribui pontos de dados deterministicamente.

Contribuições Teóricas

O artigo estabelece garantias estatísticas e de privacidade rigorosas sob a premissa de que a densidade verdadeira pertence localmente a uma classe de Hölder com parâmetro de suavidade $\beta > 2$.

Garantias de Privacidade

O pipeline completo do DP-GRAMS satisfaz $(\varepsilon, \delta)$-privacidade diferencial. O orçamento de privacidade é dividido entre a inicialização ($\varepsilon_{init}$) e os estágios de ascensão ($\varepsilon_{modes}$). O uso do mecanismo exponencial para inicialização e do mecanismo Gaussiano correlacionado para a ascensão garante que o custo de privacidade escale eficientemente com o número de modos e iterações.

Taxas de Erro e Otimalidade

Os autores derivam limites superiores para o erro quadrático médio (MSE) dos modos estimados. A taxa de erro assume a forma:
$$O\left( \left(\frac{\log n}{n}\right)^{\frac{2(\beta-1)}{d+2\beta}} \right) + O\left( \left(\frac{\text{polylog}(n, \delta)}{n^2 \varepsilon^2}\right)^{\frac{\beta-1}{d+\beta}} \right)$$

• O primeiro termo representa o erro estatístico não privado, correspondendo às taxas minimax conhecidas para estimativa de modo (ex: Tsybakov, 1990).
• O segundo termo captura a degradação devido às restrições de privacidade.

Além disso, o artigo deriva limites inferiores minimax para estimativa de modo privada, mostrando que os estimadores propostos são quase minimax ótimos, até fatores logarítmicos no MSE. Este é um resultado significativo, pois demonstra que o custo de privacidade não altera fundamentalmente a dependência da taxa de convergência em relação ao tamanho da amostra $n$ e dimensão $d$, desde que a densidade seja suficientemente suave.

Resultados Experimentais

Experimentos extensos em conjuntos de dados sintéticos e do mundo real validam as descobertas teóricas:

• Dados Sintéticos: Em misturas Gaussianas bivariadas e misturas $t$ de cauda pesada, o DP-GRAMS recupera com sucesso múltiplos modos. As curvas de troca entre privacidade e utilidade mostram que o método é competitivo com o mean shift não privado, especialmente conforme o tamanho da amostra $n$ e o orçamento de privacidade $\varepsilon$ aumentam.
• Regressão Modal: Em dados de mistura sinusoidais e de constante por partes, a regressão modal privada (DP-PMS) rastreia com sucesso estruturas condicionais multimodais que métodos baseados em média (como LOWESS) falham em capturar.
• Agrupamento (Clustering): Nos conjuntos de dados MNIST e Cancer RNA-Seq, o DP-GRAMS-C demonstra desempenho superior em Índice de Rand Ajustado (ARI) e Informação Mútua Normalizada (NMI) comparado ao $k$-means privado (DP-$k$-Means), particularmente em orçamentos de privacidade moderados. O método preserva efetivamente a geometria do agrupamento em espaços reduzidos de alta dimensão.

Significância e Alegações

O artigo afirma fornecer o primeiro framework abrangente para estimativa de modo não paramétrica com privacidade diferencial que:

1. Lida com Múltiplos Modos: Ao contrário de trabalhos anteriores focados em modos únicos ou abordagens de vizinhos mais próximos, este método é projetado para recuperar um conjunto de modos separados.
2. Alcança Quase-Otimalidade: Ao utilizar kernels de ordem superior e aproveitar a suavidade ($\beta > 2$), o método atinge taxas de erro que são quase minimax ótimas, superando as limitações de estimadores de vizinhos mais próximos que não conseguem explorar a suavidade de ordem superior.
3. Mecanismos de Privacidade Práticos: A introdução da inicialização DAP e dos mecanismos de ruído correlacionado oferece uma solução prática para a tensão entre a necessidade de granularidade da distribuição de dados (para encontrar modos) e o requisito de proteger pontos de dados individuais.
4. Utilidade de Fluxo de Trabalho (Downstream Utility): O framework se estende naturalmente para regressão modal e agrupamento, fornecendo uma abordagem unificada para tarefas não paramétricas sob restrições de privacidade.

Os autores concluem que, embora o problema da estimativa de modo privada seja desafiador devido à natureza não regular dos pontos críticos, o algoritmo DP-GRAMS proposto oferece uma solução estatisticamente sólida e praticamente implementável com trocas favoráveis entre privacidade e utilidade.