A faster zigzag sampling algorithm for strongly log-concave distributions

Let UU satisfy Assumption, let μ\mu be the target distribution, let ρ(X)\rho(X) denote the law of an algorithm's output XX, let μ0\mu_0 be the initial distribution, let κ\kappa be the relevant condition parameter, and let ε>0\varepsilon>0. Assume that κ\kappa and log(1/ε)\log(1/\varepsilon) are both smaller than some algebraic power of dd. Zigzag sampling complexity conjecture. There exists an algorithm producing a random variable XX such that

χ2(ρ(X)μ)ε.\chi^2(\rho(X) \,\Vert\, \mu)\leq \varepsilon.

Moreover, with high probability, the algorithm requires

O(dκlogd(log1ε+logχ2(μ0μ)))O\Bigl(d\kappa\log d\bigl(\log\frac{1}{\varepsilon}+\log\chi^2(\mu_0\,\Vert\,\mu)\bigr)\Bigr)

evaluations of partial derivatives of UU. This would improve the computational complexity of the proposed zigzag sampling method by avoiding the extra O(d)O(\sqrt{d}) factor in the bouncing-rate control; the conjecture remains unproved in the source.

Sources & referencesView supporting material

Primary source

Jianfeng Lu and Lihan Wang, “Complexity of zigzag sampling algorithm for strongly log-concave distributions”, arXiv:2012.11094 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.