The Binary Tree Mechanism is Optimal for Approximate Differentially Private Continual Counting

Resumo Técnico: O Mecanismo de Árvore Binária é Ótimo para Contagem Contínua com Privacidade Diferencial Aproximada

Enunciado do Problema
O artigo aborda o problema fundamental da contagem contínua privada. Neste cenário, uma organização observa um fluxo binário $x \in \{0, 1\}^n$ de comprimento $n$, onde um '1' no passo de tempo $i$ indica que um evento foi contribuído por um único indivíduo. O objetivo é liberar as contagens acumuladas (somas de prefixo) $Ax$ em cada passo de tempo $i \in [n]$, satisfazendo a privacidade diferencial (DP) $(\epsilon, \delta)$. Aqui, $A$ é a matriz de soma de prefixo triangular inferior de $n \times n$. A métrica primária de precisão é o erro esperado $\ell_\infty$, definido como $\mathbb{E}[\|M(x) - Ax\|_\infty]$, que representa o erro de pior caso em todos os passos de tempo.

Embora o mecanismo de árvore binária seja o algoritmo padrão para esta tarefa, sua otimalidade no cenário de DP aproximada ($\delta > 0$) era uma questão em aberto. Análises anteriores mostraram que o mecanismo de árvore binária alcança um erro $\ell_\infty$ de $O(\log^{3/2} n \cdot \sqrt{\log(1/\delta)}/\epsilon)$. No entanto, o melhor limite inferior conhecido era apenas $\Omega(\log n / \epsilon)$ (especificamente para a raiz quadrada do erro quadrático esperado do pior caso), deixando uma lacuna sobre se a dependência $\log^{3/2} n$ em relação ao comprimento do fluxo $n$ é necessária.

Metodologia e Visão Geral da Prova
Os autores provam que o mecanismo de árvore binária é assintoticamente ótimo ao estabelecer um limite inferior correspondente de \Omega(\log^{3/}^{3/2} n / \max\{\epsilon, \delta\}). A prova procede através de várias etapas técnicas fundamentais:

1. Redução a Mecanismos Oblívios: Seguindo trabalhos anteriores, os autores reduzem o problema à análise de mecanismos oblívios da forma $M(x) = Ax + z$, onde $z$ é um vetor de ruído independente do dado de entrada $x$. O objetivo torna-se limitar inferiormente $\mathbb{E}[\|z\|_\infty]$.
2. Decomposição de Base de Árvore: Em vez de analisar o ruído diretamente na base padrão, os autores decompõem o vetor de ruído $z$ em uma base induzida por uma árvore binária perfeita. Especificamente, eles definem vetores $\chi_u$ correspondentes a subárvores (indicadores de folhas em uma subárvore). Nesta base, o ruído em qualquer folha $i$ é a soma dos coeficientes $b_u$ ao longo do caminho da raiz até a folha $i$. Isso transforma o problema de limitar o erro máximo de coordenada no problema de limitar a acumulação de ruído ao longo dos caminhos da raiz até as folhas.
3. Acumulação de Ruído e Incerteza Residual: A prova introduz o conceito de "ruído residual" $\sigma_u$. Os autores argumentam que, se o ruído em um nó $u$ puder ser previsto com alta precisão a partir do ruído em suas subárvores, a privacidade será violada. Os autores definem $\sigma_u$ como o erro absoluto esperado na previsão do coeficiente de ruído em um nó dado o ruído nas subárvores abaixo dele. Eles mostram que o erro $\ell_\infty$ esperado é limitado inferiormente por uma soma ponderada dessas incertezas residuais ao longo de caminhos aleatórios da raiz até as folhas.
4. Superando o Obstáculo da "Previsão": Um grande desafio é que um adversário não pode observar diretamente o ruído da subárvore para prever o ruído do nó atual porque o dado de entrada $x$ é desconhecido. Para contornar isso, os autores utilizam uma estratégia de "netos". Eles mostram que, ao restringir a atenção a subárvores específicas e utilizar três cópias independentes do mecanismo (aproveitando propriedades de composição de DP), um adversário pode usar um truque da mediana de três para reduzir a variância do ruído. Isso permite a construção de um mecanismo derivado onde o adversário pode computar medições lineares da forma $x_i \nu_i + q$, onde $q$ possui variância controlada.
5. Medições Lineares e Wavelets de Haar: A etapa final constrói um adversário usando medições lineares inspiradas na base de wavelets de Haar. Ao escolher vetores de medição ortogonais, os autores relacionam a soma dos erros quadráticos das estimativas do adversário com a norma $\ell_2$ do ruído residual. Eles demonstram que, se o ruído residual $\sigma_u$ fosse pequeno, o adversário poderia distinguir entradas vizinhas com alta probabilidade, violando a privacidade diferencial. Isso força o ruído residual a ser grande, especificamente $\sigma_u = \Omega(\sqrt{\log n} / \max\{\epsilon, \delta\})$.
6. Sumação: Somar essas incertezas residuais ao longo do caminho resulta no limite inferior final de $\Omega(\log^{3/2} n)$.

Principais Contribuições e Resultados

• Otimalidade do Mecanismo de Árvore Binária: O artigo prova que, para DP aproximada, qualquer mecanismo para contagem contínua deve incorrer em um erro $\ell_\infty$ esperado de $\Omega(\log^{3/2} n / \max\{\epsilon, \delta\})$. Isso coincide com o limite superior do mecanismo de árvore binária (salvo constantes multiplicativas), resolvendo o problema em aberto sobre se a dependência $\log^{3/2} n$ é necessária.
• Estreitamento de Limites de DP Pura: Para DP pura ($\delta = 0$), o resultado estreita a lacuna entre o limite superior conhecido de $O(\log^2 n / \epsilon)$ e o limite inferior, mostrando um limite inferior de $\Omega(\log^{3/2} n / \epsilon)$.
• Separação da Discrepância Hereditária: Como um corolário, os autores derivam a maior separação possível entre a discrepância hereditária e o erro de consultas lineares privadas. Eles mostram que o limite superior geral $err_{\epsilon, \delta}^\infty(A) = O(\log^{3/2} m \cdot \text{herdisc}_\infty(A))$ é apertado em sua dependência do número de consultas $m$, pois a matriz de soma de prefixo possui discrepância hereditária 1, mas requer um erro de $\Omega(\log^{3/2} n)$.

Significado
O artigo afirma resolver um problema central em privacidade diferencial ao provar que o mecanismo de árvore binária é assintoticamente ótimo para contagem contínua no cenário de DP aproximada. As técnicas desenvolvidas, particularmente a combinação de decomposição de ruído baseada em árvores, análise de ruído residual e o uso do truque da mediana de três para lidar com ataques de medição linear, são apresentadas como ideias inovadoras que podem encontrar aplicações futuras na prova de limites inferiores para privacidade diferencial. O resultado confirma que os algoritmos de estado da arte atuais não podem ser significativamente melhorados em termos de sua dependência do comprimento do fluxo $n$.