标题：On the query complexity of sampling from non-log-concave distributions

报告时间：2025年3月7日 （星期五） 09:30-11:00

报告地点：净月大街校区信息科学与技术学院楼324会议室

主讲人：张驰豪

报告内容简介：

We will talk about the problem of sampling from a $d$-dimensional distribution with density $p(x)\propto e^{-f(x)}$, which does not necessarily satisfy good isoperimetric conditions. We will show that for any $L,M$ satisfying $LM\ge d\ge 5$, $\eps\in \tp{0,\frac{1}{32}}$, and any algorithm with query accesses to the value of $f(x)$ and $\grad f(x)$, there exists an $L$-log-smooth distribution with second moment at most $M$ such that the algorithm requires $\tp{\frac{LM}{d\eps}}^{\Omega(d)}$ queries to compute a sample whose distribution is within $\eps$ in total variation distance to the target distribution. We complement the lower bound with an algorithm requiring $\tp{\frac{LM}{d\eps}}^{\+O(d)}$ queries, thereby characterizing the tight (up to the constant in the exponent) query complexity for sampling from the family of non-log-concave distributions.

We will further discuss the connection between our work and some recent work of sampling with reverse diffusion process which can achieve quasi-polynomial query complexity under stronger conditions. Finally, we will conclude with some open problems about non-log-concave sampling.

主讲人简介：

Chihao Zhang is an associate professor in John Hopcroft Center for Computer Science at Shanghai Jiao Tong University. He obtained his Ph.D. degree from Shanghai Jiao Tong University in 2016. He mainly works in the area of theoretical computer science.