The geometry of logconcave functions and sampling algorithms

DOI10.1002/rsa.20135zbMath1122.65012OpenAlexW4252213128WikidataQ90907554 ScholiaQ90907554MaRDI QIDQ3437021

László Lovász, Santosh Vempala

Publication date: 11 May 2007

Published in: Random Structures and Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/rsa.20135

zbMATH Keywords

Metropolis algorithmsampling algorithmslog-concave densityball walkMarkov Chain Monte Carlo methodhit and run walk

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Numerical analysis or methods applied to Markov chains (65C40) Random number generation in numerical analysis (65C10)

Related Items (60)

Rapid mixing of geodesic walks on manifolds with positive curvature ⋮ Concentration inequalities for log-concave distributions with applications to random surface fluctuations ⋮ Oracle lower bounds for stochastic gradient sampling algorithms ⋮ Stochastic zeroth-order discretizations of Langevin diffusions for Bayesian inference ⋮ Thin shell implies spectral gap up to polylog via a stochastic localization scheme ⋮ Unnamed Item ⋮ On the computational complexity of MCMC-based estimators in large samples ⋮ Sampling from a log-concave distribution with projected Langevin Monte Carlo ⋮ Simulated annealing for convex optimization: rigorous complexity analysis and practical perspectives ⋮ On Condorelli inequality for log-concave demand ⋮ Oracle Estimation of a Change Point in High-Dimensional Quantile Regression ⋮ Unnamed Item ⋮ Hit-and-Run for Numerical Integration ⋮ Complexity Analysis of a Sampling-Based Interior Point Method for Convex Optimization ⋮ Anti-concentration of polynomials: dimension-free covariance bounds and decay of Fourier coefficients ⋮ Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume ⋮ A multivariate Gnedenko law of large numbers ⋮ Convex set of quantum states with positive partial transpose analysed by hit and run algorithm ⋮ Tyler's and Maronna's M-estimators: non-asymptotic concentration results ⋮ Finite sample complexity of sequential Monte Carlo estimators on multimodal target distributions ⋮ Pointwise estimates for marginals of convex bodies ⋮ The Core of the Participatory Budgeting Problem ⋮ John’s walk ⋮ The floating body and the hyperplane conjecture ⋮ Inference for High-Dimensional Censored Quantile Regression ⋮ Computational results of an \(O^{\ast }(n^{4})\) volume algorithm ⋮ Convergence of Gibbs sampling: coordinate hit-and-run mixes fast ⋮ Finite-sample complexity of sequential Monte Carlo estimators ⋮ Correction of AI systems by linear discriminants: probabilistic foundations ⋮ A Generalized Central Limit Conjecture for Convex Bodies ⋮ Two-Sided Estimates for Order Statistics of Log-Concave Random Vectors ⋮ Worst-Case Convergence Analysis of Inexact Gradient and Newton Methods Through Semidefinite Programming Performance Estimation ⋮ Comparison of hit-and-run, slice sampler and random walk Metropolis ⋮ Error bounds for Metropolis-Hastings algorithms applied to perturbations of Gaussian measures in high dimensions ⋮ Gibbs/Metropolis algorithms on a convex polytope ⋮ A remark on approximating permanents of positive definite matrices ⋮ A central limit theorem for convex sets ⋮ Log-concavity and strong log-concavity: a review ⋮ A simplified proof of CLT for convex bodies ⋮ Exploratory distributions for convex functions ⋮ Concentration of the empirical level sets of Tukey's halfspace depth ⋮ Local continuity of log-concave projection, with applications to estimation under model misspecification ⋮ On the symmetry function of a convex set ⋮ Approximate Spectral Gaps for Markov Chain Mixing Times in High Dimensions ⋮ Dispersion of mass and the complexity of randomized geometric algorithms ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Stability of the Prékopa-Leindler inequality for log-concave functions ⋮ The accessibility of convex bodies and derandomization of the hit and run algorithm ⋮ On the integrality gap of binary integer programs with Gaussian data ⋮ On randomized fictitious play for approximating saddle points over convex sets ⋮ Projective re-normalization for improving the behavior of a homogeneous conic linear system ⋮ On Sampling from Multivariate Distributions ⋮ Ulam floating bodies ⋮ A lower-bound on monopoly profit for log-concave demand ⋮ Unadjusted Langevin algorithm for sampling a mixture of weakly smooth potentials ⋮ Unnamed Item ⋮ Fast multivariate log-concave density estimation ⋮ Unnamed Item ⋮ Statistical active learning algorithms for noise tolerance and differential privacy

This page was built for publication: The geometry of logconcave functions and sampling algorithms