Resumo Técnico: Fatorabilidade de Parâmetro Fixo da Geração de Dados Sintéticos Privados

Definição do Problema

O artigo aborda o problema da Geração de Dados Sintéticos Privados. Dado um conjunto de dados sensíveis $X$ sobre um domínio $D = \{0, 1\}^d$ e uma família de consultas de contagem $\mathcal{F}$ (funções $f: D \to \{0, 1\}$), o objetivo é gerar um conjunto de dados sintéticos $X'$ que preserve as propriedades estatísticas de $X$ em relação a $\mathcal{F}$ enquanto satisfaz a Privacidade Diferencial (DP).

O erro é medido como o desvio máximo entre as respostas das consultas nos dados originais e nos dados sintéticos: $\max_{f \in \mathcal{F}} |f(X) - f(X')|$. Embora as taxas de erro ótimas para dados sintéticos DP sejam conhecidas teoricamente (dependendo do regime do tamanho do domínio $|D|$, do tamanho da família de consultas $|\mathcal{F}|$ e do tamanho do conjunto de dados $n$), os algoritmos existentes que alcançam essas taxas tipicamente operam em tempo exponencial na dimensão $d$. Por outro outro lado, sob suposições criptográficas padrão, produzir dados sintéticos precisos para famílias de consultas gerais (por exemplo, marginais de 2 vias) é computacionalmente difícil.

Os autores investigam se a Fatorabilidade de Parâmetro Fixo (FPT) pode ser alcançada ao identificar um parâmetro estrutural da família de consultas que permita algoritmos eficientes, mesmo quando $d$ é grande.

Metodologia

O artigo propõe duas abordagens algorítmicas distintas, ambas unificadas por um arcabouço de programação dinâmica sobre uma decomposição de árvore do grafo de incidência da família de consultas. O principal parâmetro estrutural identificado é a largura de árvore ($tw(\mathcal{F})$) do grafo de incidência $G(\mathcal{F})$, um grafo bipartido conectando variáveis $[d]$ e consultas $\mathcal{F}$.

1. Abordagem de Programação Linear (LP) (Regime de Pequena Família de Consultas)

Para regimes onde o tamanho da família de consultas $|\mathcal{F}|$ é pequeno, os autores formulam o problema como um Programa Linear (LP) para encontrar um histograma fracionário $h$ consistente com estimativas de contagem ruidosas.

• Problema Primal: Minimizar o desvio máximo $\alpha$ sujeito a restrições que correspondam às contagens ruidosas.
• Problema Dual: O LP dual possui $2|\mathcal{F}|$ variáveis e $2^d$ restrições. Resolver isso via o método do Elipsoide requer um oráculo de separação.
• Contribuição FPT: O oráculo de separação reduz-se a maximizar uma função linear sobre o hipercubo Booleano. Os autores mostram que este problema de maximização é FPT em termos de $tw(\mathcal{F})$ usando programação dinâmica. Isso permite que o LP dual seja resolvido em tempo polinomial em $d$ e $|\mathcal{F}|$, mas exponencial apenas em $tw(\mathcal{F})$.
• Saída: Uma vez resolvido o dual, um solução primal (histograma fracionário) com suporte pequeno é extraída, e um conjunto de dados sintéticos é gerado via amostragem.

2. Atualização de Pesos Multiplicativos Privada Subamostrada (PMWU) (Regime Esparso)

Para regimes onde o tamanho do conjunto de dados $n$ é pequeno (o cenário esparso), os autores adaptam o arcabouço de Atualização de Pesos Multiplicativos Privada (PMWU).

• Desafio: O PMWU padrão mantém uma distribuição sobre todo o domínio $D$ (tamanho $2^d$), o que é intratável.
• Solução: Em vez de manter a distribuição completa explicitamente, o algoritmo a mantém implicitamente como uma distribuição de Gibbs. Em cada etapa, ele amostra um conjunto de dados subamostrado desta distribuição.
• Contribuição FPT: O principal obstáculo técnico é a amostragem da distribuição de Gibbs definida pelos pesos atuais. Os autores provam que a amostragem de tais distribuições é FPT em $tw(\mathcal{F})$. Eles alcançam isso:
  1. Computando a função de partição (constante de normalização) da distribuição de Gibbs usando o mesmo arcabouço de programação dinâmica usado para o oráculo de separação do LP.
  2. Usando a função de partição computada e pontuações locais para realizar a amostragem de Gibbs perfeita via uma travessia recursiva da decomposição de árvore (da raiz para as folhas), amostrando probabilidades condicionais em cada etapa.
• Saída: O algoritmo atualiza iterativamente os pesos com base nos erros de consulta ruidosos e fornece o conjunto de dados subamostrado final.

Principais Contribuições

1. Parametrização Estrutural: O artigo identifica a largura de árvore do grafo de incidência da família de consultas como o parâmetro crítico para alcançar FPT na geração de dados sintéticos privados. Este parâmetro não cresce necessariamente com o tamanho do escopo da consulta, permitindo tratabilidade polinomial em casos como consultas hierárquicas.
2. Arcabouço Unificado: Ambas as abordagens (o método baseado em LP para pequeno $|\mathcal{F}|$ e o método baseado em PMWU para pequeno $n$) dependem de um arcabouço unificado de programação dinâmica sobre uma decomposição de árvore para resolver problemas de otimização (oráculo de separação) e inferência (função de partição/amostragem).
3. Taxas de Erro Ótimas: Os algoritmos propostos atingem as taxas de erro ótimas conhecidas para dados sintéticos DP em todos os regimes (pequeno $|D|$, pequeno $|\mathcal{F}|$ e pequeno $n$), mas com tempos de execução que são exponenciais apenas na largura de árvore, em vez da dimensão $d$.
4. Amostragem FPT: O artigo estabelece que a amostragem de distribuições de Gibbs associadas a famílias de consultas de largura de árvore limitada é um problema FPT, um resultado de interesse independente para modelos gráficos probabilísticos e física estatística.

Resultados

O artigo fornece as seguintes garantias teóricas:

• Complexidade: Ambos os algoritmos rodam em tempo $\text{poly}(d, |\mathcal{F}|, n, 2^{tw(\mathcal{F})}, \text{size}(\mathcal{F}))$.
• Precisão:
  • Para Pequeno $|\mathcal{F}|$ (abordagem LP): O erro corresponde ao limite ótimo $\Theta(\min(\frac{\sqrt{|D| \ln |\mathcal{F}|}}{n\varepsilon}, \frac{\sqrt{|\mathcal{F}| \log(1/\delta)}}{n\varepsilon}, \dots))$.
  • Para Pequeno $n$ (abordagem PMWU): O erro corresponde ao limite ótimo para o regime esparso, especificamente $O((\frac{d \ln(|\mathcal{F}| d n \varepsilon)}{n \varepsilon})^{1/3})$ para DP puro e $O((\frac{\sqrt{d \ln(1/\delta)} \ln(|\mathcal{F}| d n \varepsilon)}{n \varepsilon})^{1/2})$ para DP aproximada.
• Aplicações: O arcabouço é aplicado a famílias de consultas específicas:
  • Consultas Hierárquicas: A largura de árvore é limitada pela profundidade da hierarquia, recuperando a tratabilidade polinomial para consultas do tipo Censo dos EUA.
  • Consultas de Marginais Particionadas: Demonstra a superioridade da abordagem PMWU em regimes esparsos comparada a abordagens densas.
  • MRFs de Estrutura de Árvore e Famílias Geométricas: Mostra largura de árvore constante ou baixa para consultas originadas de modelos gráficos de estrutura de árvore e consultas de rede espacial (lattice).

Significância

O artigo afirma fornecer uma abordagem unificada que lida com cargas de trabalho de consultas gerais e distingue claramente entre instâncias "fáceis" e "difíceis" com base na complexidade estrutural (largura de árvore) da família de consultas.

Ao estabelecer o FPT, os autores preenchem a lacuna entre a possibilidade teórica de taxas de erro ótimas e as restrições práticas de eficiência computacional. Eles demonstram que, para muitas classes naturais e importantes de consultas (como consultas hierárquicas usadas em censos nacionais ou consultas em dados com estrutura de árvore), dados sintéticos privados precisos podem ser gerados eficientemente, superando a barreira de "exponencial em $d$" que assola os algoritmos de caso geral. O trabalho estende métodos existentes (como o algoritmo TopDown do Censo) ao fornecer um mecanismo geral que se adapta a cargas de trabalho fornecidas pelo analista sem exigir a materialização explícita de histogramas de alta dimensão.