The Tractability Landscape of Sampling with Inexact Scores

Technische Samenvatting: Het Tractabiliteitslandschap van Sampling met Inexacte Scores

Probleemstelling
Dit artikel onderzoekt de fundamentele limieten van het samplen uit een doelverdeling $\pi$ op $\mathbb{R}^d$ wanneer het algoritme alleen toegang heeft tot een benaderde scorefunctie $s \approx s_\pi := \nabla \log \pi$. De centrale vraag (Probleem 1) is: Onder welke foutaannames op het paar $(s, \pi)$ is het mogelijk om samples te genereren met een verwaarloosbare totale variatie (TV) afstand tot $\pi$ naarmate de foutgrens naar nul nadert?

De auteurs richten zich op een standaard, goed gedefinieerde doelverdelingsfamilie: distributies die log-glad zijn (de ware score is Lipschitz) en voldoen aan een Log-Sobolev Ongelijkheid (LSI). Deze klasse omvat sterk log-concaaf verdelingen en wordt breed beschouwd als het regime waarin sampling tractabel is.

Methodologie en Preliminairen
Het artikel vestigt een theoretisch kader door twee primaire klassen van scorefoutaannames te definiëren:

1. $L_p$ Fout: Het $p$-de moment van de foutnorm is begrensd door $\epsilon$.
2. MGF (Momentgenererende Functie) Fout: Een sterkere conditie die de verwachting van de exponent van de foutnorm betreft, geparametriseerd door $\beta$ en $r$. Dit generaliseert sub-Gaussische fout waarbij $\beta=2$.

De auteurs bewijzen dat MGF-fout impliceert dat er een $L_p$-fout aanwezig is (Lemma 1), waarmee vaststaat dat onder MGF-aannames afgeleide ondergrenzen automatisch ook gelden voor $L_p$-aannames.

Belangrijkste Bijdragen en Resultaten
De primaire bijdrage van het artikel is een nauwkeurige karakterisering van de foutcondities die vereist zijn voor tractabele sampling. De hoofdresultaat (Theorem 2) toont aan dat de sub-Gaussische foutaanname gebruikt in eerder werk [YW26] niet slechts voldoende, maar noodzakelijk is voor onbevooroordeelde (unbiased) sampling binnen deze doelverdelingsfamilie.

• Intractabiliteit van Zwakkere Fouten: De auteurs bewijzen dat elke foutconditie die kwalitatief zwakker is dan de sub-Gaussische aanname gebruikt door [YW26], onbevooroordeelde sampling onmogelijk maakt. Specifiek is sampling naar een verwaarloosbare TV-afstand onmogelijk als de fout voldoet aan:

  • Sub-Weibull fouten: MGF-fouten met $\beta \in (0, 2)$.
  • Begrensde momenten: Standaard $L_p$ foutaannames voor elke $p > 0$.
  • Strakke sub-Gaussische parameters: Zelfs binnen het sub-Gaussische regime ($\beta=2$), als de parameter $r$ te klein is (specifiek $r < 1/18$), is sampling intractabel.

• Het Tegenvoorbeeld (Proposition 1): Het bewijs steunt op een eenvoudig, geometrisch tegenvoorbeeld bestaande uit twee goed gescheiden Gaussische verdelingen, $\pi_1 = \mathcal{N}(0, 1)$ en $\pi_2 = \mathcal{N}(R, 1)$, waarbij $R$ groot is.

  • De auteurs construeren een enkele benaderde scorefunctie $s_\epsilon$ die interpoleert tussen de ware scores van $\pi_1$ en $\pi_2$.
  • Deze $s_\epsilon$ komt overeen met de ware score van $\pi_1$ in de linkerstaart en $\pi_2$ in de rechterstaart, en verschilt alleen in de gebied met een lage waarschijnlijkheid tussen hen in.
  • Cruciaal is dat omdat de verdelingen een verwaarloosbare massa toekennen aan het gebied waar $s_\epsilon$ incorrect is, het paar $(s_\epsilon, \pi_i)$ de zwakkere foutaannames (sub-Weibull of begrensde momenten) vervult voor een willekeurig kleine $\epsilon$.
  • Echter, omdat de ware verdelingen ver uit elkaar liggen in TV-afstand ($> 2/3$), kan geen enkel algoritme dat enkel $s_\epsilon$ bevraagt, onderscheid maken tussen $\pi_1$ en $\pi_2$, wat het onmogelijk maakt om met verwaarloosbare bias uit de correcte doelverdeling te samplen.

Betekenis en Relatie tot Voorgaand Werk
Het artikel beweert de conclusies van recent werk door [CCSW26] op twee specifieke punten te versterken:

1. Algoritme-Agnostisch: Terwijl [CCSW26] enkel de convergentie van inexacte Langevin-dynamica ontkende, sluit dit resultaat elk algoritme uit dat de score-oracle bevraagt, ongeacht de specifieke samplingmethode.
2. Breder Bereik: Het sluit een breder scala aan foutbegrippen uit, waardoor het in essentie het gehele spectrum van foutaannames dekt dat onder de sub-Gaussische drempel van [YW26] ligt.

De auteurs benadrukken dat hun resultaat "nauwkeurig tot aan constante factoren" is. De parameters die vereist zijn voor de sub-Gaussische aanname in [YW26] zijn aangetoond noodzakelijk te zijn; het versoepelen hiervan leidt tot intractabiliteit.

Beperkingen en Reikwijdte
Het artikel merkt expliciet op dat dit intractabiliteitsresultaat niet van nature uitbreidt naar de Denoising Diffusion Probabilistic Model (DDPM) setting. In DDPM's wordt aangenomen dat er toegang is tot benaderde scores op alle convolutieschalen, inclus\n bij schalen waar de scheiding tussen de Gaussische verdelingen ($R$) naar nul krimpt. In dat specifieke regime is bekend dat $L_2$ fout volstaat voor TV-convergentie, een conditie die niet wordt voldaan door het tegenvoorbeeld met een vaste scheiding dat hier wordt gebruikt.

Samenvattend stelt het artikel vast dat voor log-gladde, LSI-voldoende verdelingen, de sub-Gaussische foutaanname de exacte drempel is voor tractabiliteit. Elke zwakkere aanname staat de constructie toe van "moeilijke" instanties waarbij de score-oracle misleidend is in gebieden met een lage waarschijnlijkheid, wat onbevooroordeelde sampling onmogelijk maakt.