The geometry of logconcave functions and sampling algorithms
The geometry of logconcave functions and sampling algorithms
复制标题
DOI：
10.1002/rsa.v30:3
复制
发表时间：
2007-05
影响因子：
1
通讯作者：
L. Lovász;S. Vempala
中科院分区：
文献类型：
--
作者：
L. Lovász;S. Vempala
logconcave函数的类别是高斯人的常见概括，以及来自logconcave密度函数的凸面集的指标函数应用于从n维的logconcave分布中分析两个有效的算法，而没有对两个算法的局部平滑度，没有任何假设。步行和撞击行走，使用随机步行（马尔可夫链）生成一个随机点，它们在适当的预处理后，产生一个大约在时间o*（n4）和摊销时间o*的点。 （n3）如果需要n个或更多样品点（星号表示对误差参数的依赖性和log n的因子不显示这些边界的符合先前的界限Body
The class of logconcave functions in ℝn is a common generalization of Gaussians and of indicator functions of convex sets. Motivated by the problem of sampling from logconcave density functions, we study their geometry and introduce a technique for “smoothing” them out. These results are applied to analyze two efficient algorithms for sampling from a logconcave distribution in n dimensions, with no assumptions on the local smoothness of the density function. Both algorithms, the ball walk and the hit‐and‐run walk, use a random walk (Markov chain) to generate a random point. After appropriate preprocessing, they produce a point from approximately the right distribution in time O*(n4) and in amortized time O*(n3) if n or more sample points are needed (where the asterisk indicates that dependence on the error parameter and factors of log n are not shown). These bounds match previous bounds for the special case of sampling from the uniform distribution over a convex body.© 2006 Wiley Periodicals, Inc. Random Struct. Alg., 2007