TOPICS
Search

Logarithmically Concave Sampling

Logarithmically concave sampling is the problem of generating a random vector whose law approximates a specified logarithmically concave distribution. One oracle model specifies a twice continuously differentiable potential V:R^d->R with V(0)=0, del V(0)=0, and

I_d<=del ^2V(x)<=2I_d.

Here d is a positive integer, I_d is the identity matrix, and del ^2V(x) is the Hessian of V. The relation A<=B means that B-A is a positive semidefinite matrix. The target probability density is Z_V^(-1)e^(-V(x)), with Z_V=int_(R^d)e^(-V(x))dx. An exact first-order oracle query returns V(x) and its gradient del V(x). Real random variables and unrestricted computation between queries are allowed.

See also

Logarithmically Concave Distribution, Oracle, Randomized Algorithm, Total Variation Distance

Explore with Wolfram|Alpha

References

Chewi, S.; de Dios Pont, J.; Li, J.; Lu, C.; and Narayanan, S. "Query Lower Bounds for Log-Concave Sampling." J. ACM 71, Article 29, 2024. https://doi.org/10.1145/3673651.

Cite this as:

Weisstein, Eric W. "Logarithmically Concave Sampling." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/LogarithmicallyConcaveSampling.html

Subject classifications