mostly Monte Carlo [13/11]
The next episode of the mostly Monte Carlo seminar is this very Friday! At Paris Santé Campus as usual.
14h30 Simon Costes (Université Paris Cité)
The Wasserstein cost of Importance Sampling
Abstract: Importance sampling (IS) consists in biasing samples from a distribution f towards another distribution g. Concretely, given samples Xi from f, the IS measure is
\[
\hat g^n=\frac1{Z_n}\sum_{i=1}^n \frac{g(X_i)}{f(X_i)}\delta_{X_i},
\]
with \(Z_n=\sum_i g(X_i)/f(X_i)\). The random measure \(\hat g^n\) approximates g, and is used in many contexts ranging from Monte Carlo integration to Bayesian inference. We show that, in high dimension (d⩾3), the Wasserstein cost \(\cal W_p^p(g^n,g)\) has order \(n^{−p/d}\) in expectation, i.e.
\[
β_{p,d}^\text{low}\int gf^{−p/d} \le \lim \inf_{n\to\infty}n^{p/d}\mathbb E[\cal W_p^p(g^n,g)] \le \lim \inf_{n\to\infty}n^{p/d}\mathbb E[\cal W \le \beta{_p,d} \int gf^{−p/d}
\]
where \(β_{p,d}^\text{low},β_{p,d}\) are constants depending only on p and d, which are equal for \(p=2\) and conjectured to be equal for any \(p\ge 1\). Our results are valid for all \(p\ge 1\) and \(d\ge 3\).
In the case where \(β_{p,d}^\text{low}=β_{p,d}\), we show that the asymptotically optimal sampling distribution \(f^\star\) for importance sampling is not equal to g but to a tempered version of g, namely \(f^\star\propto g^{d/(p+d)}\), which is reminiscent of Zador’s theorem in the domain of measure quantization.
15h30 Tyler Farghly (INRIA/ENS)
Metropolis-Adjusted Diffusion Model
Abstract: Sampling from score-based diffusion models incurs bias due to both time discretisation and the approximation of the score function. A common strategy for reducing this bias is to apply corrector steps based on the unadjusted Langevin algorithm (ULA) at each noise level within a predictor-corrector framework. However, ULA is itself a biased sampler, as it discretises a continuous diffusion process. In this work, we consider adjusted Langevin correctors that employ Metropolis–Hastings (MH) or Barker’s accept-reject steps to correct for this bias. Since the target density ratio typically required by MH-based algorithms is unavailable, we propose methods that instead utilise the score function to compute the correct acceptance probability. We introduce the first exact method for adjusting Langevin corrections in diffusion models, based on a two-coin Bernoulli factory algorithm. We also propose an efficient approximation based on Simpson’s rule that achieves accuracy of order 5/2 in the step size at near-zero marginal cost. We demonstrate that these procedures improve sample quality on both synthetic and image datasets, yielding consistent gains in Fréchet Inception Distance (FID) on the latter.
Leave a Reply