Improves sampling, rounding, and integration of logconcave functions.
problem Sampling, rounding, and integration of logconcave functions.
method Algorithmic diffusion approach.
result First complexity improvements in nearly two decades for general logconcave functions.
Unified complexity bound for sampling logconcave distributions
problem Sampling arbitrary logconcave distributions
method In-and-Out algorithm with exponential lifting
result Nearly tight convergence rate
Faster algorithm for sampling logconcave densities in high dimensions.
problem Cubic barrier in sampling logconcave densities from a cold start.
method Two key ingredients: weaker distance sampling and refined log-Sobolev inequality.
result First sub-cubic sampling algorithms for isotropic position.
HMC achieves optimal convergence rate for strongly logconcave distributions.
problem Sampling from strongly logconcave densities efficiently.
method Hamiltonian Monte Carlo (HMC) with an optimal ODE solver.
result HMC achieves an optimal convergence rate of O(κ) for sampling from strongly logconcave distributions. New algorithms sample structured logconcave families with improved efficiency.
problem Sampling structured logconcave families to high accuracy.
method Reduction framework inspired by proximal point methods, combined with restricted Gaussian oracles.
result Improved bounds for sampling structured distributions, matching or surpassing state-of-the-art results.
New algorithm speeds up sampling from logconcave densities.
problem Sampling from logconcave functions in statistics and ML.
method Solves ODEs to improve HMC and other sampling methods.
result Nearly linear runtime for polylogarithmic depth.
New method improves sampling from logconcave distributions truncated on polytopes.
problem Sampling from logconcave distributions with polytope constraints.
method Regularized Dikin walks, using Lewis weights.
result Improved mixing time guarantees for various distributions and polytopes.
Improved Metropolized HMC runtime for logconcave distributions.
problem Improving the runtime of Metropolized HMC for logconcave sampling.
method Gradient norm concentration and new mixing time analysis techniques.
result Metropolized HMC mixes in O~(κd) iterations, improving runtime by a factor of (κ/d)1/2. Algorithm samples composite logconcave densities efficiently.
problem Sampling from composite logconcave densities efficiently.
method Uses a restricted Gaussian oracle and gradient queries.
result Achieves strong total variation distance guarantees.
Study sampling from logconcave distributions with dependent data streams.
problem Sampling from logconcave distributions with biased gradient estimates.
method Euler discretization of Langevin SDEs with dependent data.
result Upper bound on Wasserstein-2 distance between iterates and target distribution.
Polynomial-time algorithm learns high-dimensional halfspaces without labels.
problem Learning high-dimensional halfspaces with margins in polynomial time.
method Contrastive moments and polynomial-time algorithm.
result Establishes the unique and efficient identifiability of the hidden halfspace.
New analysis of Langevin Monte Carlo via convex optimization.
problem Sampling from logconcave smooth and non-smooth target distributions.
method Formulation as a convex optimization problem, analysis using convex optimization techniques.
result Non-asymptotic analysis of Unadjusted Langevin Algorithm and new sampling methods.
New analysis for sampling from non-convex distributions with dependent data.
problem Sampling from non-logconcave distributions in stochastic optimization.
method Stochastic Gradient Langevin Dynamics (SGLD) with dependent data streams.
result Sharper and uniform convergence estimates in L1-Wasserstein distance. New Langevin algorithm works well even for rough distributions.
problem Sampling from non-smooth distributions.
method Simple Langevin algorithm without smoothness assumptions.
result Algorithm performs well even with discontinuous gradients.
MALA mixes efficiently under smoothness and isoperimetry assumptions.
problem Sampling from target densities efficiently.
method Metropolis-Adjusted Langevin algorithm (MALA) with smoothness and isoperimetry assumptions.
result MALA mixes in $O\left(\frac{(LΥ)^{\frac12}}{ψ_μ^2} \log\left(\frac{1}ε
ight)
ight)$ iterations.
Paper tackles sampling from non-log-concave distributions using denoising diffusion.
problem Sampling from non-log-concave distributions efficiently.
method DDMC framework, Zeroth-Order Diffusion Monte Carlo (ZOD-MC) algorithm.
result ZOD-MC achieves inverse polynomial dependence on sampling accuracy, efficient for low dimensions.
New schemes improve error estimates for sampling from non-log-concave distributions.
problem Improving sampling from non-log-concave distributions with super-linear drift growth.
method Developed tamed Euler and randomized Euler schemes with error estimates.
result Near-optimal error bounds for sampling and optimization problems.
Improved bounds for MALA in non-convex sampling problems.
problem Sampling from non-convex distributions in high dimensions.
method Metropolis-adjusted Langevin algorithm (MALA) with improved bounds.
result MALA is faster than competitors in many challenging scenarios.