Event Date
Speaker: Krishna Balasubramanian, Associate Professor, Statistics, UC Davis
Title: " Recent results on the complexity of non-log-concave and heavy-tailed sampling"
Abstract: In this talk, we will discuss two results on the complexity of sampling established using optimization-inspired analysis.
First, we show that for the task of sampling from a density $\pi \propto \exp(-V)$ on $\R^d$, where $V$ is possibly non-convex but has $L$-Lipschitz gradients, (averaged) Langevin Monte Carlo outputs a sample with $\varepsilon$-relative Fisher information after $O( L^2 d^2/\varepsilon^2)$ iterations. This is the sampling analogue of complexity bounds for finding an $\varepsilon$-approximate first-order stationary points in non-convex optimization and constitutes a first step towards a general theory of non-log-concave sampling.
Next, we compare proximal samplers that are based on Gaussian versus stable oracles and prove a separation result. We show that proximal samplers based on the Gaussian oracle have a fundamental barrier in that they necessarily achieve only low-accuracy guarantees (i.e., poly(1/\varepsilon) guarantees) when sampling from a class of heavy-tailed targets. In contrast, proximal samplers based on the stable oracle exhibit high-accuracy guarantees (i.e., log(1/\varepsilon)), thereby overcoming the aforementioned limitation.
Seminar Date/Time: Thursday April 4th, 2024, at 4:10pm (Refreshments 3:30pm)
Location: MSB 1147 (Colloquium Room)