The geometry of logconcave functions and sampling algorithms

Top Cited Papers
Publisher Website
Google Scholar
Abstract
The class of logconcave functions in ℝnis 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 inndimensions, 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 timeO*(n4) and in amortized timeO*(n3) ifnor more sample points are needed (where the asterisk indicates that dependence on the error parameter and factors of lognare 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

This publication has 17 references indexed in Scilit: