Logconcave Functions: Geometry and Efficient Sampling Algorithms

The class of logconcave functions in R/sup 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 an analysis technique for "smoothing" them out. This leads to efficient sampling algorithms with no assumptions on the local smoothness of the density function. After appropriate preprocessing, both the ball walk (with a Metropolis filter) and a generalization of hit-and-run produce a point from approximately the right distribution in time O*(n/sup 4/), and in amortized time O*(n/sup 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). The bounds are optimal in terms of a "roundness" parameter and match the best-known bounds for the special case of the uniform density over a convex set.

Authors

• László Lovász 0001
• Santosh S. Vempala

Keywords

• Sampling methods
• Density functional theory
• Filters
• Lattices
• Mathematics
• Gaussian processes
• Geometry
• Engineering profession
• Probability distribution
• Stochastic processes
• Log-concavity
• Smooth Function
• Convex Set
• Covariance Matrix
• Value Function
• Random Number
• Random Walk
• Random Points
• Current Point
• Space Transformation
• Ball Of Radius
• Total Variation Distance
• Random Walk Method