Computationally tractable robust differentially private mean estimation

Resumo Técnico: Estimativa de Média com Privacidade Diferencial Robusta e Computacionalmente Tratável

Definição do Problema
O artigo aborda o desafio de estimar a média de uma distribuição de alta dimensão sob duas restrições simultâneas: privacidade diferencial (DP) e robustez a valores atípicos (outliers). O cenário envolve uma amostra de $n$ vetores em $\mathbb{R}^d$ extraídos de uma distribuição elíptica desconhecida $\nu = EC(\mu, \Sigma, F)$, que está sujeita a uma contaminação de $\eta$. Neste modelo, um adversário substitui até $\lfloor \eta n \rfloor$ observações por valores arbitrários que podem depender da amostra original. O objetivo é estimar a média populacional $\mu$ satisfazendo a privacidade diferencial de concentração zero (zCDP) e mantendo a precisão estatística, apesar de distribuições de cauda pesada e contaminação adversária.

Métodos existentes neste domínio enfrentam trade-offs significativos. Muitos estimadores privados robustos dependem de técnicas computacionalmente intensivas, como MCMC (Markov Chain Monte Carlo), relaxações de soma de quadrados ou otimização baseada em gradiente, tornando-os impraticáveis para dados de alta dimensão. Outros, embora eficientes, frequentemente dependem de privacidade diferencial aproximada ou carecem de garantias de robustez sob noções de privacidade mais fortes, como DP pura ou de concentração zero. Além disso, muitos métodos existentes exigem o ajuste de parâmetros que são difícecidos de interpretar ou que escalam mal com a dimensão.

Metodologia: A Média de Balão (Balloon Mean)
Os autores propõem um novo estimador, a média de balão, que evita sub-rotinas de otimização complexas em favor de operações algébricas lineares simples. O algoritmo opera iterativamente, alternando entre duas etapas:

1. Atualização da Média (Projeção e Média com Ruído): Dado um centro atual estimado $\tilde{\mu}_{m-1}$ e um raio $\tilde{R}_{m-1}$, o algoritmo projeta todos os pontos de dados sobre a bola de Mahalanobis $B_{\tilde{R}_{m-1}, \Sigma}(\tilde{\mu}_{m-1})$. Em seguida, calcula a média amostral dessas projeções e adiciona ruído Gaussiano calibrado para a sensibilidade da projeção (que depende do raio). Isso gera uma nova estimativa privada da média $\tilde{\mu}_m$.
2. Atualização do Balão (Expansão Privada do Raio): O algoritmo "infla" a bola centrada na nova estimativa $\tilde{\mu}_m$ até que ela contenha uma fração alvo $\tau_m$ dos dados. Isso é alcançado usando uma versão privada do algoritmo AboveThreshold. O algoritmo consulta uma sequência de raios definidos por uma grade geométrica ($R_{min} + \beta^i - 1$) e conta privadamente quantos pontos caem dentro de cada raio. Ele para no primeiro raio onde a contagem ruidosa excede um limiar ruidoso correspondente à fração alvo $\tau_m$.

O processo se repete por $M$ iterações. A estimativa final é a média das projeções sobre o balão final. O método baseia-se em alguns parâmetros de ajuste interpretáveis: o raio inicial, o fator de expansão da grade $\beta$, o número de iterações $M$ e a fração alvo $\tau$.

Principais Contribuições

1. Inovação Algorítmica: A introdução da média de balão, um estimador computacionalmente eficiente que localiza iterativamente a média ao identificar privadamente as bolas de Mahalanobis que contêm o grosso dos dados. Ela evita MCMC, soma de quadrados e gradiente descendente.
2. Garantias Teóricas: O artigo fornece limites de erro de amostra finita para a média de balão tanto em modelos de cauda pesada (onde apenas o segundo momento existe) quanto em modelos elípticos adversariamente contaminados. A análise assume uma matriz de covariância $\Sigma$ conhecida (embora os autores observem que uma estimativa privada robusta de $\Sigma$ pode ser substituída).
3. Privacidade e Complexidade: O estimador satisfaz a privacidade diferencial de concentração $\rho$-zero (zCDP), com uma extensão natural para DP pura. A complexidade computacional é $O(d^3 + nd^2 + Mnd + Mn \log n)$, que se reduz a $O(nd^2)$ sob suposições padrão ($n > d$ e $M < \log n$).

Resultados Teóricos
O principal resultado teórico (Teorema 4.4) estabelece um limite superior para o erro de Mahalanobis $|\tilde{\mu}_M - \mu|_\Sigma$. Com alta probabilidade, o erro escala como:
$$\sqrt{\frac{d}{n(\rho_- \wedge 1)}} + \sqrt{d\eta} + \sqrt{\frac{\log(\dots)}{n}}$$
onde $\rho_-$ é o orçamento de privacidade mínimo alocado por iteração.

• Cenário de Cauda Pesada ($\eta=0$): O estimador atinge a taxa de convergência minimax até fatores logarítmicos.
• Contaminação Adversária ($\eta > 0$): O erro inclui um termo que escala como $\sqrt{d\eta}$. Os autores observam que, embora limites inferiores existentes sugiram que uma dependência de $\sqrt{\eta}$ (independente de $d$) possa ser alcançável, a dependência atual de $\sqrt{d}$ é provavelmente estrutural devido à incapacidade do algoritmo de lidar explicitamente com contaminantes posicionados ao longo de uma única direção em cascas de alta dimensão. Eles reconhecem essa lacuna, mas enfatizam que nenhum algoritmo existente alcança simultaneamente a dependência ótima de contaminação, privacidade forte e eficiência computacional.

Avaliação Empírica
Simulações extensas através de dimensões ($d \in \{2, \dots, 128\}$), tamanhos de amostra e orçamentos de privacidade ($\rho \in \{0.01, 1\}$) demonstram o desempenho do método:

• Robustez: A média de balão supera significativamente outros estimadores privados computacionalmente tratáveis (como COINPRESS, estimadores M de Huber privados e médias de instância ótima) em cenários contaminados e de cauda pesada.
• Sensibilidade de Parâmetros: O método apresenta baixa sensibilidade à estimativa inicial da média, ao raio inicial e ao tamanho da grade $\beta$. O parâmetro $\tau$ atua como um controle de robustez; valores menores de $\tau$ (excluindo menos dados) melhoram o desempenho em cenários contaminados, mas podem aumentar ligeiramente o erro em cenários limpos.
• Contagem de Iterações: O erro estabiliza após 3–4 iterações, sugerindo que $M=4$ é suficiente para a maioria das aplicações práticas.

Significância e Alegações
O artigo posiciona a média de balão como uma solução prática para o "trilema" da robustez, privacidade e tratabilidade computacional. Os autores alegam que, embora o método possa não atingir a dependência teórica ótima de contaminação para cenários adversários (devido a limitações estruturais), ele oferece uma combinação única de:

1. Simplicidade Computacional: É implementável em alta dimensão sem otimizações complexas.
2. Privacidade Forte: Satisfaz zCDP, uma noção de privacidade mais forte do que a DP aproximada frequentemente usada em contextos robustos.
3. Otimalidade Estatística: Atinge taxas minimax no cenário de cauda pesada e fornece desempenho robusto em cenários contaminados onde outros métodos eficientes falham.

Os autores concluem que a média de balão é uma ferramenta viável para a estimativa de média privada em cenários do mundo real envolvendo dados de alta dimensão, potencialmente de cauda pesada e contaminados, oferecendo um equilíbrio entre garantias teóricas e viabilidade prática.