Differentially Private Nonparametric Confidence Intervals Under Minimal Distributional Assumptions

Resumo Técnico: Intervalos de Confiança Não Paramétricos com Privacidade Diferencial Sob Assunções Distribucionais Mínimas

Enunciado do Problema
O artigo aborda o desafio de construir intervalos de confiança (IC) não paramétricos com privacidade diferencial (PD) para quantidades estatísticas arbitrárias. Embora os ICs sejam fundamentais para quantificar a incerteza na inferência estatística, os métodos existentes de PD enfrentam limitações significativas. As abordagens atuais frequentemente dependem de suposições fortes, como normalidade assintótica da estatística, ou estão vinculadas a mecanismos de privacidade específicos (por exemplo, adição de ruído Gaussiano). Além disso, métodos baseados em bootstrapping ou Bag-of-Little-Bootstrap (BLB) podem ser impraticáveis em regimes de amostras finitas, resultando frequentemente em intervalos que são inválidos (subcobertura) ou excessivamente conservadores (excessivamente largos). Os autores visam desenvolver um quadro geral que converta qualquer estimador de PD que satisfaça condições suaves em um IC não paramétrico válido, sem exigir distribuições limite específicas ou suposições de suavidade sobre o funcional alvo.

Metodologia: PrivSub (Subamostragem Privada)
A solução proposta, PrivSub, aproveita a técnica estatística de subamostragem em vez de bootstrapping. O algoritmo opera da seguinte forma:

1. Estimação Completa: Calcule uma estimativa com privacidade diferencial da quantidade alvo no conjunto de dados completo usando um mecanismo $M_{full}$.
2. Subamostragem: Extraia $T$ subconjuntos de tamanho $m$ do conjunto de dados sem reposição.
3. Subestimação Privada: Aplique um estimador com privacidade diferencial $M_{sub}$ a cada um dos $T$ subconjuntos.
4. Pós-processamento: Construa a Função de Distribuição Acumulada (FDA) empírica das estatísticas privadas centradas e reescaladas. Especificamente, o método centra as estimativas dos subconjuntos em torno da estimativa do conjunto de dados completo e as reescala pela razão das taxas de convergência $\tau_m / \tau_n$ (onde $\tau_n$ é a taxa de convergência da estatística).
5. Construção do Intervalo: O IC final é derivado tomando os quantis $\alpha/2$ e $1-\alpha/2$ desta FDA empírica.

O quadro é "caixa-preta", o que significa que não requer conhecimento da forma específica da distribuição limite, apenas a existência de uma e uma taxa de convergência conhecida. A garantia de privacidade é alcançada aplicando mecanismos padrão de PD aos cálculos dos subconjuntos e utilizando a amplificação de privacidade por subamostragem, seguida de composição sobre as $T$ iterações.

Principais Contribuições

• Quadro Geral: Os autores propõem um método que transforma qualquer estimador de PD em um IC não paramétrico sob assunções distribucionais mínimas. Não exige que a estatística seja assintoticamente normal ou que o funcional seja suave.
• Garantias Teóricas: O artigo prova que a FDA empírica induzida pelo PrivSub converge para a verdadeira distribuição amostral da estatística privada (Teorema 3.3). Consequentemente, o IC resultante é provado ser assintoticamente válido e preciso (Corolário 3.4), desde que o mecanismo de privacidade seja $\tau_n$-consistente (ou seja, o erro induzido pela privacidade seja de uma ordem inferior ao erro estatístico).
• Análise de Privacidade: Os autores fornecem limites rigorosos de privacidade para o algoritmo, considerando tanto PD pura ($\delta=0$) quanto PD aproximada ($\delta > 0$), utilizando amplificação por subamostragem e teoremas de composição avançada.
• Orientação Heurística: Embora os hiperparâmetros ótimos de amostra finita ($m$ e $T$) não possam ser derivados sob assunções mínimas, o artigo oferece orientação heurística. Sugere uma restrição $m \cdot T \gtrsim n$ para equilibrar o uso de dados e o custo de privacidade, e recomenda $m \propto n^{2/3}$ e $T=60$ para estabilidade prática.

Resultados Empíricos
Os autores avaliam o PrivSub contra métodos existentes de IC não paramétrico geral com PD, especificamente BLBquant (baseado em BLB) e PrivBoot (baseado em bootstrap privado), em três tarefas:

1. Estimação da Mediana: Sob uma distribuição normal truncada.
2. Estimação da Inclinação da Regressão Logística: Um cenário paramétrico com uma distribuição limite normal.
3. Estatística Kolmogorov-Smirnov (KS): Um funcional não suave com uma distribuição limite não normal.

Descobertas:

• Validade e Precisão: O PrivSub produz consistentemente ICs com cobertura próxima ao nível nominal (por exemplo, 90%). Em contraste, o BLBquant frequentemente apresenta subcobertura (inválido) em amostras finitas, enquanto o PrivBoot é consistentemente excessivamente conservador, produzindo intervalos significativamente mais largos.
• Robustez: O PrivSub desempenha bem em funcionais tanto suaves (mediana, regressão) quanto não suaves (KS). Destaca-se sobre os concorrentes no experimento KS, onde distribuições limite não normais desafiam outros métodos.
• Desempenho em Amostra Finita: O método alcança larguras competitivas com, e frequentemente menores que, as linhas de base não privadas correspondentes, enquanto os métodos privados concorrentes frequentemente sofrem de largura excessiva devido aos custos de composição de privacidade ou invalidade.

Significado e Alegações
O artigo afirma que o PrivSub oferece uma abordagem modular e geral para inferência estatística privada. Seu significado principal reside no relaxamento das assunções necessárias para ICs de PD válidos. Diferentemente de trabalhos anteriores que necessitam de normalidade assintótica ou mecanismos de ruído específicos, o PrivSub depende apenas da existência de uma distribuição limite e de uma taxa de convergência conhecida. Isso torna o quadro aplicável a uma classe mais ampla de problemas estatísticos, particularmente aqueles envolvendo funcionais não suaves ou distribuições complexas onde métodos tradicionais de bootstrap ou aproximação normal falham. Os autores enfatizam que suas garantias teóricas se traduzem em desempenho prático, oferecendo uma alternativa robusta para a quantificação de incerteza em análise de dados sensíveis à privacidade.