Pliable rejection sampling

Resumo Técnico: Pliable Rejection Sampling (PRS)

1. O Problema

A amostragem por rejeição (rejection sampling) é uma técnica fundamental para obter amostras de distribuições de densidade $f$ que são difíceis de amostrar diretamente. No entanto, o método clássico (SRS) sofre de uma baixa taxa de aceitação, o que resulta em um desperdício massivo de recursos computacionais, especialmente quando a avaliação da função $f$ é custosa.

Os métodos adaptativos existentes possuem limitações severas:

• ARS (Adaptive Rejection Sampling): Requer que a densidade seja log-côncava (unimodal), o que é uma restrição muito forte para aplicações práticas.
• Métodos de Cadeia de Markov (MCMC): Produzem amostras correlacionadas, em vez de amostras i.i.d. (independentes e identicamente distribuídas).
• $A^\star$ sampling: Embora eficiente, exige conhecimento prévio de uma decomposição da função ($f(x) \propto \exp(\phi(x))$), o que nem sempre é disponível.

2. Metodologia (PRS)

O Pliable Rejection Sampling (PRS) propõe uma abordagem não paramétrica para aprender uma distribuição de proposta ($g$) que se "ajusta" (ou se dobra, daí o termo pliable) à densidade alvo $f$.

A metodologia divide-se em três etapas principais:

1. Amostragem Inicial: Realiza-se uma amostragem uniforme no domínio $[0, A]^d$ para obter $N$ pontos e avaliar o valor de $f$ nesses pontos.
2. Estimativa de Densidade: Utiliza-se um estimador de kernel (como o kernel Gaussiano) para construir uma estimativa $\hat{f}$ baseada nas amostras coletadas.
3. Construção da Proposta "Pliável": Em vez de usar apenas a estimativa $\hat{f}$, o PRS constrói uma proposta $g^*$ que é um limite superior uniforme da densidade real. Isso é feito adicionando um termo de erro de confiança ($r_N$) à estimativa do kernel, garantindo que a proposta sempre envolva a função alvo.

O algoritmo utiliza propriedades de teoria de estimativa de densidade para garantir que, com alta probabilidade, a proposta seja uma cobertura válida de $f$.

3. Principais Contribuições

• Garantia de Desempenho: Diferente de outros métodos adaptativos, o PRS oferece uma garantia teórica sobre o número de amostras aceitas. O artigo prova que, assintoticamente, quase todas as chamadas à função $f$ resultam em uma amostra aceita.
• Flexibilidade de Suposições: O método não exige log-concavidade ou unimodalidade. Ele requer apenas propriedades suaves de Hölder (suavidade da função), o que é uma condição muito mais fraca e comum.
• Amostras i.i.d. Perfeitas: Como o método é baseado em rejeição, as amostras geradas são verdadeiramente i.i.d. com alta probabilidade, ao contrário dos métodos MCMC.
• Extensão para Alta Dimensão: O artigo propõe uma técnica de localização usando otimização convexa para lidar com o problema da "maldição da dimensionalidade", permitindo encontrar a massa da distribuição de forma polinomial em relação à dimensão $d$, em vez de exponencial.

4. Resultados Experimentais

Os autores compararam o PRS com o SRS e o $A^\star$ sampling em diversos cenários:

• Escalabilidade com "Peakiness" (Picos de densidade): Em distribuições muito concentradas (picos agudos), o PRS superou tanto o SRS quanto o $A^\star$ sampling, mostrando que sua taxa de aceitação melhora conforme o orçamento de avaliações de $f$ aumenta.
• Exemplo 2D: Em uma função senoidal complexa, o PRS apresentou uma taxa de aceitação comparável ao estado da arte ($A^\star$ sampling), mas sem a necessidade de decomposição prévia da função.
• Problema de Clutter (Outliers): Em problemas de inferência bayesiana bimodal, o $A^\star$ sampling ainda foi superior, mas o PRS manteve uma taxa de aceitação razoável e muito superior ao método clássico.

5. Significância

A importância do PRS reside na sua eficiência assintótica e robustez. Ele preenche uma lacuna entre os métodos de rejeição simples (ineficientes) e os métodos de amostragem complexos (que exigem conhecimento estrutural profundo da função). Ao transformar o problema de amostragem em um problema de estimativa de densidade com limites de confiança, o PRS oferece uma ferramenta poderosa para cientistas de dados que precisam amostrar de distribuições desconhecidas ou complexas de forma confiável e com custo computacional controlado.