Sampling and integration of near log-concave functions

By David L. Applegate, R. Kannan. 1991

Sampling and Integration of Near Log-Concave Functions David Applegate* Ravi Kannan* An important class of functions that arise in statistics and other areas are the log-concave functions. Here we provide the first polynomial time algorithm to generate samples from a given log-concave distribution. The algorithm is fairly simple and natural; it is the proof of its fast convergence that is new. To this end, we prove a general isoperimetric inequality for convex sets and use this together with recent developments in the theory of rapidly mixing Markov chains. We use our sampling algorithm to develop an algorithm for integrating log-concave functions. As one application, we are able to develop an algorithm for approximating the volume of convex bodies given by an oracle; we do so by enclosing the given body in a cube, defining a log-concave function that is 1 on the body and exponentially falls off outside, and integrating this function. This a.llo ws us to avoid one of the complications in prior algorithms for computing volumes – dealing with sharp corners – and results in an algorithm which is faster than previous algorithms.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “We use the grid-walk algorithm of [2] for sampling from a logconcave distribution defined over a cube as a building block.”
Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo (2015, background): “A more general result in Applegate & Kannan (1991) suggests that we can get a sample with arbitrarily close approximation in polynomial time for a class of near log-concave distributions.”
Learning with Differential Privacy: Stability, Learnability and the Sufficiency and Necessity of ERM Principle (2015, methodology): “The Markov chain sampling algorithm in Applegate and Kannan (1991) is guaranteed to produce a sample from a distribution that is arbitrarily close to the target distribution (in the total variation sense) in polynomial time.”
Simulated annealing in convex bodies and an O*(n/sup 4/) volume algorithm (2003, background): “Since the paper of Applegate and Kannan [1], the flexibility obtained by extending the problem to the integration of special kinds of functions (mostly logconcave) has been exploited in several papers.”
An Introduction to MCMC for Machine Learning (2004, unknown): “2. Sampling from log-concave distributions ( Applegate & Kannan, 1991 ).”
The Geometry of Logconcave Functions and Sampling Algorithms ∗ (2003, methodology): “First note that for t ∈ [1, 3] the bound follows using Chebychev’s inequality: We have E(X(2)) ≥ t2P(|X| > t), and so P(|X| > t) ≤ 1/t(2).”
Active and passive learning of linear separators under log-concave distributions (2012, background): “ Nearly log-concave distributions We also extend our results both for passive and active learning to deal with nearly log-concave distributions; this is abroader class of distributions introduced by (Applegate and Kannan, 1991), which contains mixtures of (not too separated) log-concave distribution”
Simulated annealing in convex bodies and an O*(n4) volume algorithm (2006, background): “Since the paper of Applegate and Kannan [1], the flexibility obtained by extending the problem to the integration of special kinds of functions (mostly logconcave) has been exploited in several papers.”
Private Empirical Risk Minimization, Revisited (2014, methodology): “Our analysis is based on the grid random walk of [2], and a discussion with the second author of this paper.”
Adiabatic quantum state generation and statistical zero knowledge (2003, methodology): “Using the same ideas we can also generate all linear extensions of partial orders using Bubley and Dyer algorithm [12], all lattice points in a convex body satisfying certain restrictions using Applegate-Kannan technique [9] and many more states.”
Random Walks on Graphs: A Survey (2001, background): “One notable exception is the work of Applegate and Kannan [8], who proved that random walks on the lattice points in a convex body, filtered by a smooth log-concave function, mix essentially as fast as the corresponding unfiltered walk.”
Rapid Convergence of the Unadjusted Langevin Algorithm: Isoperimetry Suffices (2019, background): “It is of great interest to extend these results to non-logconcave densities ⌫, where existing results require strong assumptions with bounds that grow exponentially with the dimension or other parameters [2, 18, 45, 49].”
Tractability of Multivariate Problems (2008, background): “Here a ∈ [1, 2) and Ca is a positive number depending only on a, see again [275].”
Simulated Annealing in Convex Bodies and an O ( n 4 ) Volume Algorithm (2007, background): “The first polynomial time randomized algorithm to compute the volume of a convex body in Ê Ò was given by Dyer, Frieze and Kannan in their pathbreaking paper [3].”
Geometric Random Walks: a Survey (2007, methodology): “When is this method efficient? In [3] and [14] respectively, it is shown that the ball walk and the lattice walk are rapidly mixing from a warm start, provided that the density is logconcave and it does not vary much locally, i.”
Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds (2014, methodology): “To the best of our knowledge, this task has not been explicitly worked out before, nevertheless, all the ingredients needed to accomplish it are present in the literature, mainly [2].”