The Geometry of Logconcave Functions and an O* (n3) Sampling Algorithm

The class of logconcave functions in R n is a common generalization of Gaussians and of indicator functions of convex sets. Motivated by the problem of sampling from a logconcave density function, we study their geometry and introduce a technique for “smoothing” them out. This leads to an efficient sampling algorithm (by a random walk) with no assumptions on the local smoothness of the density function. After appropriate preprocessing, the algorithm produces a point from approximately the right distribution in time O* ( n 4 ), and in amortized time O* ( n 3 ) if many sample points are needed (where the asterisk indicates that dependence on the error parameter and factors of log n are not shown).