Establishing an $\Omega(\sqrt{d})$ complexity lower bound for PDMP samplers and how to break it: a sub-$\sqrt{d}$ algorithm for Gaussian-tailed targets

Resumo Técnico: Estabelecendo um Limite Inferior de Complexidade $\Omega(\sqrt{d})$ para Amostradores PDMP e um Algoritmo Sub-$\sqrt{d}$ para Alvos de Cauda Gaussiana

Definição do Problema
Amostradores de Processos de Markov Determinísticos por Partes (PDMP), como o Bouncy Particle Sampler (BPS) e o processo Zig-Zag, oferecem uma alternativa não reversível aos métodos tradicionais de Monte Carlo via Cadeias de Markov (MCMC). No entanto, apesar de seu apelo teórico, nenhum PDMP existente demonstrou uma escala de complexidade computacional superior a $O(\sqrt{d})$ em relação à dimensão do alvo $d$. Em contraste, métodos baseados em gradiente reversíveis, como o Hamiltonian Monte Carlo (HMC) e o Metropolis-Adjusted Langevin Algorithm (MALA), alcançam escalas superiores de $O(d^{1/4})$ e $O(d^{1/3})$, respectivamente. A questão central abordada por este trabalho é se o limite de $O(\sqrt{d})$ é uma limitação inerente ao framework PDMP ou meramente uma consequência de designs algorítmicos específicos.

Metodologia
O artigo emprega uma abordagem de duas frentes: uma prova de limite inferior teórico e a construção de um novo algoritmo que relaxa suposições padrão.

1. Limite Inferior Teórico:
   O autor estabelece um limite inferior de $\Omega(\sqrt{d})$ na complexidade computacional para uma ampla classe de amostradores PDMP locais. A prova baseia-se em várias suposições estruturais:

   • Independência do Alvo: O fluxo determinístico e o espaço auxiliar não dependem da distribuição alvo $\pi$ específica.
   • Saltos Locais: O núcleo de salto altera a variável auxiliar, mas não a posição espacial, garantindo trajetórias espaciais absolutamente contínuas.
   • Invariância: A distribuição alvo deve permanecer invariante em todos os tempos contínuos, não apenas nos pontos de amostragem discretos.

   Ao analisar distribuições alvo i.i.d., a prova demonstra que a taxa de salto esperada $\mathbb{E}[\lambda]$ deve escalar como $\Omega(\sqrt{d})$ para satisfazer a equação estacionária $L^*\mu = 0$. Uma vez que a distância entre amostras efetivamente independentes cresce como $\sqrt{d}$, e a velocidade média é limitada, o número total de saltos necessários por amostra independente escala como $\Omega(\sqrt{d})$.

2. Inovação Algorítmica (Quebrando o Limite):
   Para contornar este limite, o artigo propõe relaxar a suposição de que a densidade do alvo deve ser invariante em todos os tempos contínuos. Em vez disso, o algoritmo permite que o alvo seja invariante apenas em tempos de amostragem discretos, de forma semelhante ao MCMC padrão.

   • Framework: O método integra o framework Metropolised NUTS-PDMP com uma nova dinâmica de PDMP Oscilante inspirada na integração leapfrog do HMC.
   • Dinâmica: O processo alterna entre atualizações de posição ($\dot{x} = v$) e atualizações de velocidade ($\dot{v} = -\nabla U(x)$) em tempos contínuos aleatórios, em vez de intervalos fixos.
   • Re-ponderação de Caminho: Como a trajetória contínua não preserva estritamente a medida do alvo, o algoritmo emprega uma estratégia de re-amostragem de caminho. Ele gera uma trajetória usando aproximações numéricas de taxas de eventos e, em seguida, reamostra um estado da trajetória com base em uma densidade de probabilidade condicional. Esta densidade re-pondera os estados para corrigir as flutuações Hamiltonianas ao longo do caminho, garantindo que o output final seja uma amostra exata do alvo.
   • Adaptatividade: O algoritmo utiliza o critério No-U-Turn (NUTS) para determinar adaptativamente os comprimentos das trajetórias e emprega tamanhos de passo localmente adaptativos para atualizações de velocidade, evitando a necessidade de estratégias de ajuste global complexas exigidas pelo HMC reversível.

Principais Contribuições

• Limite Inferior de Complexidade: O artigo fornece uma prova rigorosa de que os amostradores PDMP padrão, que impõem invariância em tempo contínuo, são fundamentalmente limitados a uma complexidade $\Omega(\sqrt{d})$ para alvos i.i.d.
• Algoritmo Sub-$\sqrt{d}$: Um novo algoritmo Metropolised PDMP é introduzido, que abdica da invariância em tempo contínuo. Ao utilizar re-ponderação de caminho e aproximações numéricas, ele alcança uma complexidade computacional de $O(d^\alpha)$, onde $\alpha \in [0.2, 0.3]$, para alvos de cauda Gaussiana.
• Adaptatividade Local: O framework proposto incorpora naturalmente a adaptatividade local tanto no comprimento da trajetória quanto na distância entre as atualizações de velocidade, uma característica difícil de implementar no HMC reversível sem estratégias complexas.

Resultados Empíricos
O autor apresenta resultados de escala empírica para dimensões $d \in \{2, \dots, 128\}$ através de cinco distribuições alvo:

• Alvos de Cauda Gaussiana: Para Gaussiana padrão, Regressão Logística Bayesiana e alvos de Mistura Gaussiana, o número de eventos por Tamanho de Amostra Efetiva (ESS) escala entre $O(d^{0.22})$ e $O(d^{0.29})$. O número de avaliações de gradiente escala entre $O(d^{0.26})$ e $O(d^{0.31})$. Estes resultados superam significativamente o limite de $O(\sqrt{d})$ dos PDMPs tradicionais e aproximam-se da escala teórica do HMC.
• Alvos Não-Gaussianos: O algoritmo demonstra robustez em distribuições de cauda mais pesada (Logística) e mais leve (Quártica), embora os expoentes de escala sejam maiores ($O(d^{0.43})$ a $O(d^{0.64})$), refletindo a maior dificuldade destes alvos.

Significância e Alegações
O artigo afirma identificar uma limitação fundamental no framework PDMP padrão: o requisito de invariância em tempo contínuo é o principal gargalo que impede uma melhor escala dimensional. Ao relaxar esta restrição, o autor demonstra que os PDMPs podem alcançar escala sub-$\sqrt{d}$, preenchendo a lacuna de desempenho com o HMC. O trabalho sugere que o desempenho "sub-$\sqrt{d}$" não é um artefato de um design específico, mas uma consequência de permitir que o amostrador opere com invariância aproximada corrigida via re-ponderação de Metropolis-Hastings. O autor conclui que, enquanto o limite inferior teórico para os PDMPs padrão é estabelecido, o algoritmo proposto oferece um caminho prático para eficiência em altas dimensões, particularmente para alvos de cauda Gaussiana, mantendo as vantagens de não-reversibilidade dos PDMPs.