Not All Learnable Distribution Classes are Privately Learnable

Resumo Técnico: "Nem Todas as Classes de Distribuições Aprendíveis são Privadamente Aprendíveis"

Declaração do Problema
O artigo aborda uma questão fundamental na interseção entre a teoria do aprendizado estatístico e a privacidade diferencial (DP): toda classe de distribuições que é aprendível no cenário padrão (não privado) também é aprendível sob as restrições de privacidade diferencial $(\varepsilon, \delta)$?

Embora seja estabelecido que a privacidade diferencial pura ($\varepsilon$-DP, onde $\delta=0$) impõe separações estritas entre classes aprendíveis e privadamente aprendíveis (frequentemente caracterizadas por números de cobertura/packing), o status da privacidade diferencial aproximada ($(\varepsilon, \delta)$-DP) permanecia uma questão em aberto. A literatura recente produziu frameworks cada vez mais gerais para aprendizado de distribuição privado, levando Ashtiani [Ash22] a conjecturar que a resposta à questão acima é afirmativa: que toda classe de distribuição aprendível é privadamente aprendível.

Metodologia e Construção
Os autores refutam essa conjectura construindo uma classe específica de distribuições, denotada como $\mathcal{H}_w$, que serve como contraexemplo. A construção utiliza um mecanismo de "porta dos fundos" envolvendo misturas de distribuições:

1. Estrutura da Classe: A classe $\mathcal{H}_{w,d}$ consiste em misturas sobre $d+1$ componentes que compartilham um vetor de parâmetros comum $\mathbf{p} \in [0,1]^d$.
   • Componente "Chave": Uma distribuição produto binária sobre $\{0,1\}^d$ com peso de mistura $w$. Uma única amostra deste componente revela informações sobre todo o vetor de parâmetros $\mathbf{p}$.
   • Componentes "Difíceis": $d$ componentes adicionais, cada um suportado em $\{\pm j\}$ para $j \in \{1, \dots, d\}$, com peso de mistura $(1-w)/d$. Uma amostra de qualquer um destes revela informações sobre apenas uma coordenada de $\mathbf{p}$.
2. A Porta dos Fundos: O peso de mistura $w$ é definido como $1/(2\alpha)$ (onde $\alpha$ é o erro alvo). Isso garante que os componentes "difíceis" dominem a mistura (alta probabilidade de amostragem deles), enquanto o componente "chave" é raro.
3. O Truque da Dimensionalidade: A classe $\mathcal{H}_w$ é definida como a união dessas classes sobre todas as dimensões $d \ge 2$. A construção garante que, embora a dimensão $d$ não seja fixa a priori, a dificuldade de aprendizado escala com $d$.

Resultados e Provas Principais
O artigo estabelece uma separação entre aprendibilidade não privada e privada para a classe $\mathcal{H}_w$ em relação à distância de Variação Total (TV):

1. Aprendibilidade Não Privada (Amostras Finitas):
   Os autores demonstram que $\mathcal{H}_w$ é aprendível com um número constante de amostras (independente de $d$) até um erro constante.

   • Mecanismo: Como o componente "chave" aparece com probabilidade $w$, um algoritmo não privado pode coletar amostras suficientes para observar o componente chave. Uma vez observado, a dimensão $d$ é identificada e o vetor de parâmetros $\mathbf{p}$ pode ser estimado via média amostral da distribuição produto binária.
   • Complexidade: A complexidade de amostragem é $O(1/\alpha^3 \cdot \log(1/\beta))$, que é constante em relação à dimensão $d$.

2. Não Aprendibilidade Privada (Amostras Infinitas Requeridas):
   Os autores provam que nenhum mecanismo $(\varepsilon, \delta)$-DP pode aprender esta classe com a mesma garantia de erro usando um número finito de amostras.

   • Redução: Eles constroem uma redução do problema de estimação de densidade em $\mathcal{H}_{w,d}$ para o problema de estimação de parâmetro $\ell_1$ para distribuições produto binárias.
   • Limite Inferior: Aproveitando limites inferiores conhecidos para estimação de média privada de distribuições produto binárias (especificamente de [KLSU19]), eles mostram que a complexidade de amostragem para aprender $\mathcal{H}_{w,d}$ sob DP escala como $\Omega(\sqrt{d}/(\sqrt{\alpha}\varepsilon))$.
   • Contradição: Como a classe $\mathcal{H}_w$ inclui distribuições para qualquer $d \ge 2$, e o tamanho de amostra necessário cresce com $\sqrt{d}$, nenhum tamanho de amostra finito $n$ é suficiente para aprender toda a classe $\mathcal{H}_w$ sob DP. À medida que $d \to \infty$, o tamanho de amostra necessário tende ao infinito.

Contribuições Principais

• Refutação da Conjectura: O artigo fornece um contraexemplo explícito à conjectura de Ashtiani de que toda classe de distribuição aprendível é privadamente aprendível sob $(\varepsilon, \delta)$-DP.
• Separação de Aprendibilidade: Demonstra uma separação estrita onde uma classe é aprendível com $O(1)$ amostras de forma não privada, mas requer um número infinito de amostras para ser aprendida de forma privada.
• Construção de Porta dos Fundos: Os autores introduzem uma construção específica de "porta dos fundos" onde um componente raro atua como uma chave para um parâmetro de alta dimensão, que é de outra forma obscurecido por um componente dominante e difícil de aprender. Essa estrutura impede que mecanismos privados acessem a "chave" sem violar restrições de privacidade ou exigir tamanhos de amostra proibitivos.

Significado e Alegações
O artigo alega "refutar fracamente" a conjectura. Os autores notam explicitamente que uma "refutação forte" exigiria mostrar que a classe é aprendível para qualquer erro alvo (não apenas erro constante) com amostras finitas de forma não privada, o que eles não provam. No entanto, seu resultado é significativo porque mostra que, mesmo para garantias de erro constante, o cenário do aprendizado de distribuição privado é fundamentalmente diferente do aprendizado não privado.

O trabalho destaca que frameworks gerais para aprendizado privado não podem simplesmente depender de reduções de caixa-preta de aprendedores não privados sem suposições estruturais adicionais. Estabelece que a existência de um componente "chave" que é raro, mas essencial para o aprendizado, pode criar uma barreira intransponível para algoritmos privados, mesmo quando o algoritmo não privado é eficiente.

Conclusão
O artigo conclui que a agenda de projetar algoritmos gerais de aprendizado privado que funcionem para todas as classes de distribuição aprendíveis não pode ser totalmente realizada. Existem classes aprendíveis onde a restrição de privacidade altera fundamentalmente a complexidade de amostragem de finita para infinita, independentemente da tolerância a erro específica (dentro do regime constante considerado).