Randomized Midpoint Method for Log-Concave Sampling under Constraints

• URL: http://arxiv.org/abs/2405.15379v2
• Date: Sat, 24 May 2025 11:14:07 GMT
• Title: Randomized Midpoint Method for Log-Concave Sampling under Constraints
• Authors: Yifeng Yu, Lu Yu,
• Abstract summary: We study the problem of sampling from log-concave distributions supported on convex, compact sets.<n>We propose a unified proximal framework for handling constraints via a broad class of projection operators.
• Score: 5.548787731232499
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we study the problem of sampling from log-concave distributions supported on convex, compact sets, with a particular focus on the randomized midpoint discretization of both vanilla and kinetic Langevin diffusions in this constrained setting. We propose a unified proximal framework for handling constraints via a broad class of projection operators, including Euclidean, Bregman, and Gauge projections. Within this framework, we establish non-asymptotic bounds in both $\mathcal{W}_1$ and $\mathcal{W}_2$ distances, providing precise complexity guarantees and performance comparisons. In addition, our analysis leads to sharper convergence guarantees for both vanilla and kinetic Langevin Monte Carlo under constraints, improving upon existing theoretical results.

Related papers

• High-accuracy sampling from constrained spaces with the Metropolis-adjusted Preconditioned Langevin Algorithm [12.405427902037971]
  We propose a first-order sampling method for approximate sampling from a target distribution whose support is a proper convex subset of $mathbbRd$.<n>Our proposed method is the result of applying a Metropolis-Hastings filter to the Markov chain formed by a single step of the preconditioned Langevin algorithm.
  arXiv  Detail & Related papers  (2024-12-24T23:21:23Z)
• Constrained Sampling with Primal-Dual Langevin Monte Carlo [15.634831573546041]
  This work considers the problem of sampling from a probability distribution known up to a normalization constant.<n>It satisfies a set of statistical constraints specified by the expected values of general nonlinear functions.<n>We put forward a discrete-time primal-dual Langevin Monte Carlo algorithm (PD-LMC) that simultaneously constrains the target distribution and samples from it.
  arXiv  Detail & Related papers  (2024-11-01T13:26:13Z)
• Tamed Langevin sampling under weaker conditions [27.872857402255775]
  We investigate the problem of sampling from distributions that are not log-concave and are only weakly dissipative. We introduce a taming scheme which is tailored to the growth and decay properties of the target distribution. We provide explicit non-asymptotic guarantees for the proposed sampler in terms of the Kullback-Leibler divergence, total variation, and Wasserstein distance to the target distribution.
  arXiv  Detail & Related papers  (2024-05-27T23:00:40Z)
• Proximal Oracles for Optimization and Sampling [18.77973093341588]
  We consider convex optimization with non-smooth objective function and log-concave sampling with non-smooth potential. To overcome the challenges caused by non-smoothness, our algorithms employ two powerful proximal frameworks in optimization and sampling.
  arXiv  Detail & Related papers  (2024-04-02T18:52:28Z)
• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Sampling and estimation on manifolds using the Langevin diffusion [45.57801520690309]
  Two estimators of linear functionals of $mu_phi $ based on the discretized Markov process are considered.<n>Error bounds are derived for sampling and estimation using a discretization of an intrinsically defined Langevin diffusion.
  arXiv  Detail & Related papers  (2023-12-22T18:01:11Z)
• Improving Gradient-guided Nested Sampling for Posterior Inference [47.08481529384556]
  We present a performant, general-purpose gradient-guided nested sampling algorithm, $tt GGNS$. We show the potential of combining nested sampling with generative flow networks to obtain large amounts of high-quality samples from the posterior distribution.
  arXiv  Detail & Related papers  (2023-12-06T21:09:18Z)
• Gaussian Cooling and Dikin Walks: The Interior-Point Method for Logconcave Sampling [8.655526882770742]
  In the 1990s Nester and Nemirovski developed the Interior-Point Method (IPM) for convex optimization based on self-concordant barriers. In 2012, Kannan and Narayanan proposed the Dikin walk for uniformly sampling polytopes. Here we generalize this approach by developing and adapting IPM machinery together with the Dikin walk for poly-time sampling algorithms.
  arXiv  Detail & Related papers  (2023-07-24T17:15:38Z)
• Sample Complexity for Quadratic Bandits: Hessian Dependent Bounds and Optimal Algorithms [64.10576998630981]
  We show the first tight characterization of the optimal Hessian-dependent sample complexity. A Hessian-independent algorithm universally achieves the optimal sample complexities for all Hessian instances. The optimal sample complexities achieved by our algorithm remain valid for heavy-tailed noise distributions.
  arXiv  Detail & Related papers  (2023-06-21T17:03:22Z)
• Learning Rate Free Sampling in Constrained Domains [21.853333421463603]
  We introduce a suite of new particle-based algorithms for sampling in constrained domains which are entirely learning rate free. We demonstrate the performance of our algorithms on a range of numerical examples, including sampling from targets on the simplex.
  arXiv  Detail & Related papers  (2023-05-24T09:31:18Z)
• Plug-and-Play split Gibbs sampler: embedding deep generative priors in Bayesian inference [12.91637880428221]
  This paper introduces a plug-and-play sampling algorithm that leverages variable splitting to efficiently sample from a posterior distribution. It divides the challenging task of posterior sampling into two simpler sampling problems. Its performance is compared to recent state-of-the-art optimization and sampling methods.
  arXiv  Detail & Related papers  (2023-04-21T17:17:51Z)
• Kinetic Langevin MCMC Sampling Without Gradient Lipschitz Continuity -- the Strongly Convex Case [0.0]
  We consider sampling from log concave distributions in Hamiltonian setting, without assuming that the objective is globally Lipschitz. We propose two algorithms based on polygonal gradient (tamed) Euler schemes, to sample from a target measure, and provide non-asymptotic 2-Wasserstein distance bounds between the law of the process of each algorithm and the target measure.
  arXiv  Detail & Related papers  (2023-01-19T12:32:41Z)
• Distributed Sketching for Randomized Optimization: Exact Characterization, Concentration and Lower Bounds [54.51566432934556]
  We consider distributed optimization methods for problems where forming the Hessian is computationally challenging. We leverage randomized sketches for reducing the problem dimensions as well as preserving privacy and improving straggler resilience in asynchronous distributed systems.
  arXiv  Detail & Related papers  (2022-03-18T05:49:13Z)
• An Analysis of Ensemble Sampling [28.18592417451813]
  Ensemble sampling serves as a practical approximation to Thompson sampling when maintaining an exact posterior distribution over model parameters is computationally intractable. We establish a Bayesian regret bound that ensures desirable behavior when ensemble sampling is applied to the linear bandit problem.
  arXiv  Detail & Related papers  (2022-03-02T18:41:22Z)
• Robust Estimation for Nonparametric Families via Generative Adversarial Networks [92.64483100338724]
  We provide a framework for designing Generative Adversarial Networks (GANs) to solve high dimensional robust statistics problems. Our work extend these to robust mean estimation, second moment estimation, and robust linear regression. In terms of techniques, our proposed GAN losses can be viewed as a smoothed and generalized Kolmogorov-Smirnov distance.
  arXiv  Detail & Related papers  (2022-02-02T20:11:33Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  We introduce the expected co-coercivity condition, explain its benefits, and provide the first last-iterate convergence guarantees of SGDA and SCO. We prove linear convergence of both methods to a neighborhood of the solution when they use constant step-size. Our convergence guarantees hold under the arbitrary sampling paradigm, and we give insights into the complexity of minibatching.
  arXiv  Detail & Related papers  (2021-06-30T18:32:46Z)
• Revisiting the Sample Complexity of Sparse Spectrum Approximation of Gaussian Processes [60.479499225746295]
  We introduce a new scalable approximation for Gaussian processes with provable guarantees which hold simultaneously over its entire parameter space. Our approximation is obtained from an improved sample complexity analysis for sparse spectrum Gaussian processes (SSGPs)
  arXiv  Detail & Related papers  (2020-11-17T05:41:50Z)
• Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust Algorithms [91.96505642426833]
  This paper focuses on the distributed optimization of saddle point problems.<n>In particular, we show the effectiveness of our method in training GANs in a distributed manner.
  arXiv  Detail & Related papers  (2020-10-25T13:13:44Z)
• Non-Adaptive Adaptive Sampling on Turnstile Streams [57.619901304728366]
  We give the first relative-error algorithms for column subset selection, subspace approximation, projective clustering, and volume on turnstile streams that use space sublinear in $n$. Our adaptive sampling procedure has a number of applications to various data summarization problems that either improve state-of-the-art or have only been previously studied in the more relaxed row-arrival model.
  arXiv  Detail & Related papers  (2020-04-23T05:00:21Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.