Anchored Likelihood-Ratio Geometry of Anonymous Shuffle Experiments: Exact Privacy Envelopes and Universal Low-Budget Design

Resumo Técnico: Geometria da Razão de Verossimilhança Ancorada em Experimentos de Shuffle Anônimo

1. Problema e Contexto

O artigo aborda o modelo de shuffle (shuffle model) de Privacidade Diferencial (DP), que ocupa um espaço intermediário entre o modelo local (LDP) e o modelo centralizado (curator). Neste modelo, os usuários privatizam seus dados localmente através de um canal $W$, e um "shuffler" (misturador) anonimiza as mensagens enviadas, entregando ao observador apenas uma coleção desordenada (histograma) das mensagens, sem rótulos de origem.

O objetivo central do trabalho é resolver dois problemas fundamentais de forma exata e não assintótica (para $n$ finito):

1. Envelope de Privacidade Exato: Determinar os limites exatos de privacidade (envoltórias de divergência $f$-convexa e perfis de "hockey-stick") para qualquer mecanismo local sob uma restrição $\epsilon_0$-LDP, após o processo de shuffle.
2. Design Canônico de Mecanismos: Encontrar o mecanismo ótimo para estimação de frequência (minimização de risco quadrático) sob orçamentos de privacidade específicos (orçamento $\chi^*$ canônico e limite local bruto $\epsilon_0$).

O autor argumenta que as matrizes de canal tradicionais ou o alfabeto de saída não são as variáveis de estado corretas para esses problemas exatos. Em vez disso, ele propõe uma nova variável de estado: uma lei de razão de verossimilhança afim ancorada (anchored affine likelihood-ratio law).

2. Metodologia e Estrutura Teórica

A metodologia baseia-se em uma reformulação geométrica rigorosa dos experimentos de shuffle:

• Lei Ancorada ($\rho$): O autor define um poliedro regular simplesx $X_d$ em $\mathbb{R}^{d-1}$. Um "canal $d$-ário de saída finita" é representado, de forma única (a menos de refinamentos condicionalmente idênticos), por uma medida de probabilidade $\rho$ com média zero sobre $X_d$.

  • A representação é dada por: $W(B|i) = \int_B (1 + \gamma_i^\top x) \rho(dx)$, onde $\gamma_i$ são vértices do simplex centrado.
  • Isso transforma o problema de design de canais em um problema de momentos para a matriz de covariância $\Sigma(\rho) = \int xx^\top \rho(dx)$.

• Redução Projetiva e Fibras:

  • A privacidade pareada (entre duas linhas $i$ e $j$) no modelo shuffle é reduzida exatamente a sombras unidimensionais de "fibras projetivas".
  • Define-se uma fibra projetiva $\eta_h$ para um ponto base $h$. A razão de verossimilhança entre duas composições de entrada torna-se uma projeção escalar dessa fibra.
  • Isso permite analisar a privacidade do shuffle como um problema de convolução de variáveis aleatórias unidimensionais.

• Simetrização Global:

  • O autor demonstra que, para problemas de design canônico, pode-se restringir a busca a leis trocáveis (exchangeable), ou seja, leis invariantes sob permutação das coordenadas. A simetrização nunca aumenta o risco canônico nem o orçamento de privacidade.

3. Principais Contribuições e Resultados

O artigo apresenta cinco contribuições teóricas principais:

A. Envelopes de Privacidade Universais e Rigidez

• Resultado: Sob uma restrição local comum $\epsilon_0$-LDP, o mecanismo de Resposta Aleatória Binária (Binary Randomized Response - BRR) é universalmente ótimo.
• Detalhe: O BRR maximiza todas as divergências $f$-convexas e ambos os perfis de privacidade "hockey-stick" (direitos e esquerdos) após o shuffle, para qualquer tamanho de alfabeto $d$ e qualquer $n$.
• Conversa de Rigidez: Se os envelopes de privacidade hockey-stick direcionados são saturados simultaneamente para um $n$ finito, então o mecanismo subjacente deve ser exatamente o BRR (ou uma refinamento condicionalmente idêntico dele). Isso é provado usando a teoria de funções características e o teorema da identidade para funções analíticas.

B. Design Canônico sob Orçamento $\chi^*$ (Baixo Orçamento)

• Orçamento $\chi^*$: Define-se um orçamento de privacidade baseado na divergência $\chi^2$ direcionada máxima entre pares de linhas.
• Resultado: No regime de baixo orçamento, o mecanismo Resposta Aleatória Augmentada (Augmented Randomized Response - ARR) é o otimizador canônico único.
• Fórmulas Exatas: O autor deriva fórmulas exatas para o risco canônico (i.i.d. e composição fixa) e prova um Teorema do Teto de Traço (Trace Cap), que limita a matriz de covariância $\Sigma(\rho)$ em função do orçamento $\chi^*$.
• Redução a Dois Órbitas: O fronte global de otimização (a curva de Pareto entre risco e orçamento) é a envoltória côncava superior de uma curva paramétrica $\Gamma_d$. O autor prova que qualquer ponto neste fronte é realizado por uma mistura de no máximo duas leis de órbita trocáveis.

C. Design Canônico sob Limite Local Bruto ($\epsilon_0$)

• Diferente do orçamento $\chi^*$, sob o limite estrito de LDP $\epsilon_0$, o otimizador não é o ARR, mas sim um mecanismo de Seleção de Subconjuntos (Subset Selection).
• O autor fornece uma formulação exata ancorada para este problema, determinando o tamanho ótimo do subconjunto $s^*$ através de uma maximização unidimensional explícita.
• O tamanho ótimo é dado por $s^* \approx \lfloor d / (e^{\epsilon_0} + 1) \rfloor$ ou o inteiro adjacente, generalizando resultados assintóticos anteriores para $n$ finito.

D. Otimização Minimax Assintótica Universal

• O artigo prova que, no regime de baixo orçamento, o ARR é minimax-ótimo assintoticamente (com a constante líder exata) sobre todos os canais e todos os estimadores (não apenas os canônicos) no modelo i.i.d. multinomial.

E. Distinção Estrutural

• O trabalho esclarece que a geometria da lei ancorada é a linguagem correta para envelopes de privacidade exatos e design canônico de baixo orçamento, mas não subsume as assintóticas não-Gaussianas de composição fixa estudadas em trabalhos anteriores do autor (a "trilogia"). As fibras projetivas são limitadas no interior, forçando um comportamento Gaussiano local, enquanto regimes não-Gaussianos exigem uma geometria de quociente diferente.

4. Significado e Impacto

• Unificação Exata: O trabalho fornece uma estrutura unificada e exata para problemas de privacidade e estimação no modelo de shuffle, eliminando a necessidade de aproximações assintóticas para obter limites de privacidade rigorosos.
• Novos Limites de Otimização: Estabelece limites inferiores exatos para o risco de estimação e limites superiores exatos para a privacidade, provando que mecanismos simples (como BRR e Seleção de Subconjuntos) são ótimos em contextos específicos, mas que a escolha do mecanismo depende criticamente da métrica de orçamento utilizada ($\chi^*$ vs. $\epsilon_0$).
• Ferramentas Geométricas: Introduz conceitos geométricos novos (fibras projetivas, leis ancoradas) que simplificam a análise de experimentos complexos de shuffle, reduzindo problemas multidimensionais a problemas unidimensionais ou de momentos.
• Aplicabilidade Prática: As fórmulas exatas para risco e privacidade permitem o dimensionamento preciso de sistemas de privacidade diferencial em cenários reais com $n$ finito, onde aproximações assintóticas podem ser imprecisas.

Em suma, o artigo estabelece que a lei de razão de verossimilhança ancorada é a variável de estado fundamental para o design e análise exata de mecanismos de shuffle, oferecendo soluções completas e ótimas para os problemas de privacidade e estimação de frequência sob restrições locais.