Self-Certifying Transport MCMC via Dual Spectral-Gap Certificates

Resumo Técnico: MCMC de Transporte Autocertificável via Certificados de Gap Espectral Duplo

1. Declaração do Problema

O método de Monte Carlo via Cadeias de Markov (MCMC) continua sendo o padrão para computação Bayesiana, mas verificar a convergência permanece um desafio em aberto. Os praticantes dependem de diagnósticos heurísticos (ex: $\hat{R}$, gráficos de traço, estimativas de tamanho de amostra efetivo) que podem detectar patologias, mas não podem certificar rigorosamente a convergência. Embora os limites de gap espectral forneçam, teoricamente, tais certificados, eles raramente foram práticos porque exigem o controle rigoroso de quantidades (como a oscilação de pesos de importância) que dependem da distribuição alvo desconhecida.

Este problema é exacerbado pelo surgimento de propostas aprendidas e adaptativas, especificamente aquelas que utilizam fluxos de normalização para Metropolis–Hastings de Independência (IMH). Embora esses fluxos melhorem a mistura empírica, o próprio núcleo de transição torna-se um objeto aprendido de alta dimensão, tornando a auditabilidade difícil. A questão central abordada é: Pode uma proposta aprendida certificar sua própria convergência?

2. Metodologia: O Framework CerT-MCMC

Os autores propõem o CerT-MCMC, um framework que equipa o MCMC de transporte aprendido com certificados de convergência automáticos e rigorosos derivados do próprio fluxo de normalização usado como a proposta de IMH.

Mecanismo Central:
Um fluxo de normalização $T_\phi$ mapeia uma referência Gaussiana $q_0$ para uma aproximação da posterior alvo $\pi$. No espaço latente $z$, a probabilidade de aceitação do IMH depende da razão de peso de importância $w(z) = \pi_z(z)/q_0(z) = e^{r(z)}$, onde $r(z)$ é o resíduo do log-peso. Se $T_\phi$ for perfeito, $r(z)$ é constante; caso contrário, a oscilação de $r(z)$ mede a qualidade do transporte. O teorema de Mengersen–Tweedie estabelece que o gap espectral $\gamma$ do núcleo IMH é limitado inferiormente por $2/(1 + e^C)$, onde $C = \text{osc}(r)$ é a oscilação do log-peso sobre o suporte da proposta.

O framework desenvolve dois certificados complementares para limitar essa oscilação:

Certificado I: O Certificado de Cobertura (Covering Certificate)

• Abordagem: Limita a oscilação sobre todo o suporte da proposta usando um argumento de cobertura de amostra finita. Ele adiciona um termo de correção Lipschitz à amplitude observada das amostras para contabilizar as lacunas entre os pontos amostrais.
• Escalabilidade: O raio de correção escala como $O(n^{-1/D})$, onde $n$ é o número de amostras de certificação e $D$ é a dimensão.
• Limitação: Devido à maldição da dimensionalidade, este certificado torna-se vácuo (não fornece um limite útil) para dimensões moderadas ($D \gtrsim 6$) em tamanhos de amostra práticos. Os autores provam um limite inferior mostrando que nenhum algoritmo de avaliação pontual pode certificar a oscilação de suporte total mais rápido que $\Omega(n^{-1/D})$.

Certificado II: O Certificado de Núcleo de Quantil (Quantile-Core Certificate)

• Abordagem: Reconhece que, para fluxos bem treinados, o resíduo $r(z)$ é altamente concentrado, com a oscilação total sendo impulsionada por outliers raros nas bordas. Este certificado restringe a atenção a um "núcleo de resíduo definido pelos dados" $\tilde{G}_\rho$, contendo a massa central $(1-2\rho)$ da proposta, definida por quantis empíricos de $r(z)$.
• Escalabilidade: A folga de probabilidade de amostra finita para a estimativa do quantil é $O(n^{-1/2})$, derivada da desigualdade de Dvoretzky–Kiefer–Wolfowitz, que é independente da dimensão ambiente $D$.
• Resultado: Fornece um limite inferior de gap espectral computável e de alta confiança para o núcleo do IMH restrito. As constantes de normalização para os pesos restritos se cancelam exatamente, permitindo que o teorema de Mengersen–Tweedie seja aplicado diretamente.

Framework de Certificado Duplo:
Os dois certificados são complementares. O Certificado I oferece uma garantia de pior caso sobre o suporte total onde é tratável ($D \lesssim 5$). O Certificado II oferece uma garantia de núcleo de alta massa em todas as dimensões, reportando honestamente a fração da cauda não certificada. Juntos, eles formam uma taxonomia de diagnóstico distinguindo entre:

1. Sucesso de certificado total: Ambos não são vácuos.
2. Sucesso de certificado de núcleo: Certificado II não é vácuo, Certificado I é vácuo (o fluxo é bom; o gargalo é a prova de cobertura).
3. Degradação de transporte: Certificado II é não vácuo, mas fraco (declínio genuíno na qualidade do fluxo).
4. Falha de transporte: Certificado II é vácuo (fluxo ruim).

3. Principais Contribuições

1. Framework CerT-MCMC: Um sistema que fornece certificados de gap espectral automáticos e rigorosos para MCMC de transporte aprendido usando o próprio fluxo de proposta.
2. Certificado de Cobertura (I): Formaliza a barreira de cobertura, provando um limite inferior de pior caso de $\Omega(n^{-1/D})$ para certificação de suporte total pontual, motivando a necessidade de uma abordagem diferente em dimensões mais altas.
3. Certificado de Núcleo de Quantil (II): Desenvolve um certificado independente da dimensão ($O(n^{-1/2})$ de folga) que limita a oscilação em um núcleo de alta probabilidade usando quantis empíricos.
4. Validação Empírica: Demonstra que o proxy de gap espectral do Certificado II acompanha a eficiência de mistura real (Tamanho de Amostra Efetivo) dentro de 7% em regressão logística Bayesiana ($D=20$).
5. Poder Discriminativo: Mostra via experimentos de controle negativo que o Certificado II discrimina a qualidade do fluxo por um fator superior a $10\times$, enquanto as taxas de aceitação padrão diferem em apenas $1.15\times$.

4. Resultados Experimentais

O framework foi avaliado em:

• Alvos Sintéticos: Alvos "Banana" ($D=2$ a $20$). O Certificado I tornou-se vácuo em $D \ge 6$, enquanto o Certificado II permaneceu não vácuo e estável até $D=10$, e forneceu um limite não vácuo em $D=20$ mesmo quando a capacidade do fluxo degradou.
• Posteriores de Engenharia Estrutural: Modelos Sailboat ($D=6$) e Shear building ($D=8$). O Certificado I foi vácuo para ambos, mas o Certificado II revelou que o fluxo aprendeu o alvo $D=8$ melhor que o alvo $D=6$, uma distinção que o Certificado I perdeu.
• Regressão Logística de Dados Reais: Conjunto de dados Heart Disease ($D=13$). O Certificado II produziu um forte gap espectral ($\gamma \approx 0.64$), enquanto o Certificado I permaneceu fraco.
• Controle Negativo: Comparação de fluxos bem treinados, subtreinados e mal especificados no alvo banana ($D=10$). O Certificado II identificou com sucesso os fluxos ruins (baixo $\gamma$) apesar de taxas de aceitação semelhantes.

5. Significância e Alegações

O artigo alega fornecer o primeiro framework de certificado duplo para MCMC de transporte aprendido que oferece certificados de convergência automáticos e conscientes da dimensão. Sua principal significância reside em:

• Computação Bayesiana Auditável: Transformar o transporte aprendido de um "acelerador de caixa-preta" em um objeto auditável onde o mesmo mapa que propõe movimentos também expõe a geometria do resíduo para certificação de convergência.
• Distinção de Modos de Falha: Separar explicitamente as "limitações da técnica de prova" (a barreira de cobertura em dimensões altas) da "falha genuína de transporte". Diagnósticos padrão não conseguem fazer essa distinção.
• Utilidade Prática: Fornecer um limite de gap espectral computável que acompanha a eficiência de mistura empírica, oferecendo uma alternativa rigorosa aos diagnósticos heurísticos para problemas de dimensão moderada.

Os autores mantêm modéstia quanto às limitações: o certificado aplica-se ao núcleo restrito em vez da cadeia completa (embora o núcleo capture a vasta maioria da massa), e o framework é atualmente específico para Metropolis–Hastings de Independência. Eles observam que para alvos de dados reais de altíssima dimensão ($D \ge 30$), o pré-condicionamento padrão geralmente é necessário antes que o fluxo possa aproximar a geometria de forma eficaz.