The geometry of logconcave functions and sampling algorithms

• Published in: Random structures & algorithms 2007-05, Vol.30 (3), p.307-358
• Main Authors: Lovász, László, Vempala, Santosh
• Format: Article
• Language: English
• ISSN: 1042-9832; 1098-2418
• DOI: 10.1002/rsa.20135

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