Fast Algorithms for Logconcave Functions: Sampling, Rounding, Integration and Optimization

We prove that the hit-and-run random walk is rapidly mixing for an arbitrary logconcave distribution starting from any point in the support. This extends the work of Lovasz and Vempala (2004), where this was shown for an important special case, and settles the main conjecture formulated there. From this result, we derive asymptotically faster algorithms in the general oracle model for sampling, rounding, integration and maximization of logconcave functions, improving or generalizing the main results of Lovasz and Vempala (2003), Applegate and Kannan (1990) and Kalai and Vempala respectively. The algorithms for integration and optimization both use sampling and are surprisingly similar

Authors

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

Keywords

• Sampling methods
• Polynomials
• Ellipsoids
• Algorithm design and analysis
• H infinity control
• Gaussian processes
• Log-concavity
• Functional Integrity
• Random Walk
• Integration Algorithm
• Support Points
• Covariance Matrix
• Total Distance
• Simulated Annealing
• Distribution Of Points
• Random Points
• Uniform Density
• Convex Set
• Mixing Time
• Target Distribution
• Ball Of Radius
• Body Volume
• Probability Distance
• Total Variation Distance
• Uniform Point
• Warm Start