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

Technische Samenvatting: Het vaststellen van een $\Omega(\sqrt{d})$ complexiteitsondergrens voor PDMP-samplers en een sub-$\sqrt{d}$ algoritme voor Gaussian-tailed targets

Probleemstelling
Piecewise Deterministic Markov Process (PDMP) samplers, zoals de Bouncy Particle Sampler (BPS) en het Zig-Zag proces, bieden een niet-reversibel alternatief voor traditionele Markov Chain Monte Carlo (MCMC) methoden. Ondanks hun theoretische aantrekkingskracht heeft echter geen enkele bestaande PDMP-sampler een computationele complexiteit getoond die beter schaalt dan $O(\sqrt{d})$ met betrekking tot de doeldimensie $d$. In contrast hiermee bereiken gradiëntgebaseerde reversibele methoden zoals Hamiltonian Monte Carlo (HMC) en het Metropolis-Adjusted Langevin Algorithm (MALA) superieure schaling van respectievelijk $O(d^{1/4})$ en $O(d^{1/3})$. De centrale vraag die dit werk adresseert, is of de $O(\sqrt{d})$ barrière een inherente beperking is van het PDMP-framework of louter een gevolg is van specifieke algoritmische ontwerpen.

Methodologie
Het artikel hanteert een tweeledige aanpak: een bewijs voor een theoretische ondergrens en de constructie van een nieuw algoritme dat standaardveronderstellingen versoepelt.

1. Theoretische Ondergrens:
   De auteur stelt een $\Omega(\sqrt{d})$ ondergrens vast voor de computationele complexiteit van een brede klasse van lokale PDMP-samplers. Het bewijs steunt op verschillende structurele aannames:

   • Target Onafhankelijkheid: De deterministische flow en de hulpruimte zijn niet afhankelijk van de specifieke targetdistributie $\pi$.
   • Lokale Sprongen: De sprongkern verandert de hulpvariabele maar niet de ruimtelijke positie, wat zorgt voor absoluut continue ruimtelijke trajecten.
   • Invariantie: De targetdistributie moet invariant blijven op alle continue tijdstippen, niet alleen op discrete steekproefpunten.

   Door i.i.d. targetdistributies te analyseren, toont het bewijs aan dat de verwachte sprongfrequentie $\mathbb{E}[\lambda]$ moet schalen als $\Omega(\sqrt{d})$ om aan de stationaire vergelijking $L^*\mu = 0$ te voldoen. Aangezien de afstand tussen effectief onafhankelijke steekproeven groeit als $\sqrt{d}$, en de gemiddelde snelheid begrensd is, schaalt het totale aantal sprongen vereist per onafhankelijke steekproef als $\Omega(\sqrt{d})$.

2. Algoritmische Innovatie (Het doorbreken van de barrière):
   Om deze limiet te omzeilen, stelt het papier voor om de aanname te versoepelen dat de targetdichtheid op alle continue tijdstippen invariant moet zijn. In plaats daarvan staat het algoritme toe dat de target alleen invariant is op discrete steekproeftijdstippen, vergelijkbaar met standaard MCMC.

   • Framework: De methode integreert het Metropolised NUTS-PDMP framework met een nieuwe Oscillating PDMP dynamiek, geïnspireerd door HMC leapfrog-integratie.
   • Dynamiek: Het proces wisselt af tussen positie-updates ($\dot{x} = v$) en snelheid-updates ($\dot{v} = -\nabla U(x)$) op willekeurige continue tijdstippen, in plaats van op vaste intervallen.
   • Pad-herweging (Path Re-weighting): Omdat het continue traject de targetmaat niet strikt behoudt, gebruikt het algoritme een pad-resamplingstrategie. Er wordt een traject gegenereerd met behulp van numerieke benaderingen van event-rates, waarna een toestand uit het traject wordt geresampled op basis van een conditionele waarschijnlijkheidsdichtheid. Deze dichtheid herweegt toestanden om de Hamiltonian-fluctuaties langs het pad te corrigeren, waardoor de uiteindelijke output een exacte steekproef uit de target is.
   • Adaptiviteit: Het algoritme maakt gebruik van de No-U-Turn (NUTS) criterion om de trajectlengtes adaptief te bepalen en gebruikt lokaal adaptieve stapgroottes voor de snelheid-updates, waardoor de noodzaak voor complexe globale afstemmingsstrategieën die vereist zijn door reversibele HMC, wordt vermeden.

Belangrijkste Bijdragen

• Complexiteitsondergrens: Het artikel levert een rigoureus bewijs dat standaard PDMP-samplers, die continue-tijd invariantie afdwingen, fundamenteel beperkt zijn tot $\Omega(\sqrt{d})$ complexiteit voor i.i.d. targets.
• Sub-$\sqrt{d}$ Algoritme: Een nieuw Metropolised PDMP-algoritme wordt geïntroduceerd dat afziet van continue-tijd invariantie. Door gebruik te maken van pad-herweging en numerieke benaderingen, bereikt het een computationele complexiteit van $O(d^\alpha)$ waarbij $\alpha \in [0.2, 0.3]$ voor Gaussian-tailed targets.
• Lokale Adaptiviteit: Het voorgestelde framework incorporeert van nature lokale adaptiviteit in zowel de trajectlengte als de afstand tussen snelheid-updates, een kenmerk dat moeilijk te implementeren is in reversibele HMC zonder complexe strategieën.

Empirische Resultaten
De auteur presenteert empirische schaleringsresultaten voor dimensies $d \in \{2, \dots, 128\}$ over vijf targetdistributies:

• Gaussian-Tailed Targets: Voor standaard Gaussische, Bayesian Logistic Regression en Gaussian Mixture targets, schaalt het aantal events per Effective Sample Size (ESS) tussen $O(d^{0.22})$ en $O(d^{0.29})$. Het aantal gradiënt-evaluaties schaalt tussen $O(d^{0.26})$ en $O(d^{0.31})$. Deze resultaten presteren significant beter dan de $O(\sqrt{d})$ limiet van traditionele PDMPs en benaderen de theoretische schaling van HMC.
• Niet-Gaussische Targets: Het algoritme vertoont robuustheid op zwaardere (Logistic) en lichtere (Quartic) tails, hoewel de schaleringsexponenten hoger zijn ($O(d^{0.43})$ tot $O(d^{0.64})$), wat de verhoogde moeilijkheidsgraad van deze targets weerspiegelt.

Betekenis en Claims
Het artikel claimt een fundamentele beperking in het standaard PDMP-framework te hebben geïdentificeerd: de vereiste van continue-tijd invariantie is de primaire flessenhals die een betere dimensionale schaling verhindert. Door deze beperking te versoepelen, demonstreert de auteur dat PDMPs een sub-$\sqrt{d}$ schaling kunnen bereiken, waarmee de prestatiekloof met HMC wordt overbrugd. Het werk suggereert dat de "sub-$\sqrt{d}$" prestatie geen artefact is van een specif으로 ontwerp, maar een gevolg is van het laten opereren van de sampler met een benaderde invariantie die gecorrigeerd wordt via Metropolis-Hastings herweging. De auteur concludeert dat terwijl de theoretische ondergrens voor standaard PDMPs is vastgesteld, het voorgestelde algoritme een praktisch pad biedt naar hogere-dimensie efficiëntie, met name voor Gaussian-tailed targets, terwijl de niet-reversibele voordelen van PDMPs behouden blijven.