Resumo Técnico: Ordenação, Partição, Randomização: Teste de Hipótese Binária Ótimo sob Privacidade Diferencial Local

1. Configuração do Problema

O artigo aborda o problema de projetar mecanismos $\epsilon$-localmente diferenciais privados (LDP) ótimos para teste de hipótese binária. O cenário envolve uma observação $X$ extraída de uma das duas distribuições conhecidas, $P_0$ ou $P_1$, definidas sobre um alfabeto finito $\mathcal{X}$ de tamanho $k$. Antes da divulgação, cada amostra é privatizada por um canal $Q$ que satisfaz a restrição $\epsilon$-LDP:
$$Q(y|x) \leq e^\epsilon Q(y|x') \quad \forall x, x' \in \mathcal{X}, y \in \mathcal{Y}$$
O objetivo é projetar $Q$ para maximizar uma métrica de utilidade definida por uma $f$-divergência entre as distribuições de saída induzidas $M_0 = Q^\top P_0$ e $M_1 = Q^\top P_1$. A função de utilidade é:
$$D_f(M_0 \| M_1) = \sum_{y \in \mathcal{Y}} M_1(y) f\left(\frac{M_0(y)}{M_1(y)}\right)$$
onde $f$ é uma função convexa com $f(1)=0$. Este framework abrange divergência de Variação Total (TV), divergência de Kullback-Leibler (KL) e divergência $E_\gamma$ (hockey-stick). O problema também é considerado sob uma restrição de comunicação, onde o tamanho do alfabeto de saída é limitado a $\ell$ ($\ell \leq k$).

2. Metodologia e Caracterização Estrutural

Trabalhos anteriores estabeleceram que os mecanismos ótimos são do tipo "escada" (as probabilidades assumem apenas dois valores, $\theta$ e $e^\epsilon \theta$), mas dependiam de programas lineares com $2^k$ variáveis, tornando-os computacionalmente intratáveis para $k$ moderados. Este artigo introduz uma caracterização estrutural nítida para reduzir o espaço de busca.

A Classe Sort-Partition-Randomize (SPR)

Os autores provam que, após ordenar o alfabeto de entrada pela razão de verossimilhança $r_i = P_0(x_i)/P_1(x_i)$, existe um mecanismo ótimo que segue uma estrutura de três etapas específica:

1. Ordenar (Sort): Ordenar as entradas de modo que $r_1 < r_2 < \dots < r_k$.
2. Particionar (Partition): Dividir o alfabeto ordenado em blocos contíguos (intervalos) $\pi = (B_1, \dots, B_s)$.
3. Randomizar (Randomize): Aplicar Resposta Aleatória (RR) $s$-ária ao rótulo do bloco. Especificamente, se a entrada $x$ cai no bloco $B_j$, a saída é $j$ com probabilidade $\frac{e^\epsilon}{e^\epsilon + s - 1}$ e qualquer outro bloco $j' \neq j$ com probabilidade $\frac{1}{e^\epsilon + s - 1}$.

Estratégia de Prova Geométrica

A otimalidade dos mecanismos SPR é derivada da geometria do polítopo de intervalo conjunto $\mathcal{R}_\ell(p, q)$, que representa todos os pares de distribuições de saída $(M_0, M_1)$ alcançáveis sob a restrição LDP. A prova procede em três etapas:

1. Refinamento: Qualquer ponto extremo do intervalo conjunto pode ser realizado por um canal de escada cujas colunas ativas possuem conjuntos altos LR-contíguos (conjuntos de entradas que mapeiam para uma saída específica que formam um intervalo contíguo na ordem ordenada).
2. Decomposição Convexa: Qualquer canal de escada tal que possua conjuntos altos LR-contíguos reside no envelope convexo de mecanismos SPR.
3. Não-Extremidade do Refinamento (Coarsening): A fusão determinística das saídas de um mecanismo SPR (a menos que resulte em uma única saída) não produz um novo ponto extremo.

Como as $f$-divergências são convexas no par de saída $(M_0, M_1)$, o máximo é atingido em um ponto extremo do intervalo conjunto. Portanto, um mecanismo ótimo é sempre um mecanismo SPR.

3. Principais Contribuições

1. Algoritmo Exato de Tempo Polinomial

O artigo fornece o primeiro algoritmo de tempo polinomial para computar o mecanismo exato ótimo para qualquer $f$-divergência.

• Saída Sem Restrição: Um programa de programação dinâmica (DP) exato executa em $O(k^3)$ de tempo.
• Saída Com Restrição ($\ell$ saídas): O DP executa em $O(\ell k^2)$ de tempo.
• Mecanismo: O DP explora a decomponibilidade aditiva das $f$-divergências sobre blocos contíguos. Ele computa pontuações de intervalo $\mu[a:b]$ e encontra a partição de $[1:k]$ em $s$ blocos que maximiza a pontuação total, normalizada pelo fator RR.

2. Solução de Forma Fechada para a Divergência $E_\gamma$

Para o caso específico da divergência $E_\gamma$ (que inclui Variação Total para $\gamma=1$), o mecanismo ótimo colapsa para uma Resposta Aleatória Binária Generalizada.

• A estratégia ótima é definir um conjunto de limiar $S_\gamma = \{x : P_0(x) \geq \gamma P_1(x)\}$.
• O mecanismo aplica resposta aleatória binária ao bit indicativo $\mathbb{1}\{X \in S_\gamma\}$.
• Este resultado mantém-se para qualquer $\epsilon$ e qualquer tamanho de alfabeto $k$, recuperando e estendendo limites superiores anteriores conhecidos como apertados apenas para entradas binárias.

3. Extensão para Outros Objetivos

• Divergências de Rényi: A otimalidade SPR e o DP $O(\ell k^2)$ aplicam-se às divergências de Rényi via uma redução monótona para $f$-divergências.
• Distância $\ell_r$: Mostra-se que o mecanismo ótimo para a distância $\ell_r$ é o mecanismo SPR binário (equivalente ao mecanismo ótimo para TV).

4. Resultados e Ilustração Numérica

Os autores validam suas descobertas teóricas através de experimentos numéricos:

• $k$ pequeno ($k=6$): O programa dinâmico SPR coincide com os resultados do programa linear de tempo exponencial de Kairouz-Oh-Viswanath (KOV) até a precisão de máquina ($\leq 6.1 \times 10^{-14}$), confirmando empiricamente o teorema estrutural.
• $k$ grande ($k=100$): O LP de KOV é inviável (possuindo $2^{100}$ variáveis), enquanto o DP SPR computa o ótimo exato em menos de 20 segundos em um laptop padrão.
• Desempenho: O mecanismo SPR supera significativamente os baselines simples, como o mecanismo binário (que apresenta um platô precoce) e a resposta aleatória $k$-ária (que é pouco informativa para $\epsilon$ pequenos), em todo o intervalo de privacidade.

5. Significância e Alegações

O artigo afirma resolver um gargalo computacional de longa data no design de mecanismos de privacidade diferencial local.

• Eficiência: Transforma um problema de busca de tempo exponencial em uma otimização exata de tempo polinomial, permitindo o design de mecanismos ótimos para tamanhos de alfabeto anteriormente considerados computacionalmente inviáveis.
• Interpretabilidade: A estrutura SPR fornece uma descrição simples e interpretável da privatização ótima: "agregue símbolos com razões de verossimilhança semelhantes, então privatize o rótulo grosseiro".
• Generalidade: Os resultados aplicam-se a toda a gama de orçamentos de privacidade $\epsilon$ e vários objetivos de utilidade, indo além de regimes assintóticos ou casos especiais.
• Limitações: Os autores notam explicitamente que sua caracterização é específica para teste de hipótese binária simples sob $\epsilon$-LDP pura e não interativa em um alfabeto finito. Extensões para testes de hipótese múltipla, LDP aproximada ou protocolos interativos permanecem em aberto. Além disso, o DP atual depende da estrutura aditiva das $f$-divergências, e algoritmos eficientes para objetivos mais amplos de quase-convexidade (como informação de Chernoff) ainda não foram fornecidos.