A Proximal Algorithm for Sampling from Non-convex Potentials

• URL: http://arxiv.org/abs/2205.10188v1
• Date: Fri, 20 May 2022 13:58:46 GMT
• Title: A Proximal Algorithm for Sampling from Non-convex Potentials
• Authors: Jiaming Liang, Yongxin Chen
• Abstract summary: We consider problems with non-smooth potentials that lack smoothness. Rather than smooth, the potentials are assumed to be semi-smooth or multiple multiplesmooth functions. We develop a special case Gibbs sampling known as the alternating sampling framework.
• Score: 14.909442791255042
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study sampling problems associated with non-convex potentials that meanwhile lack smoothness. In particular, we consider target distributions that satisfy either logarithmic-Sobolev inequality or Poincar\'e inequality. Rather than smooth, the potentials are assumed to be semi-smooth or the summation of multiple semi-smooth functions. We develop a sampling algorithm that resembles proximal algorithms in optimization for this challenging sampling task. Our algorithm is based on a special case of Gibbs sampling known as the alternating sampling framework (ASF). The key contribution of this work is a practical realization of the ASF based on rejection sampling in the non-convex and semi-smooth setting. This work extends the recent algorithm in \cite{LiaChe21,LiaChe22} for non-smooth/semi-smooth log-concave distribution to the setting with non-convex potentials. In almost all the cases of sampling considered in this work, our proximal sampling algorithm achieves better complexity than all existing methods.

Related papers

• A Sample Efficient Alternating Minimization-based Algorithm For Robust Phase Retrieval [56.67706781191521]
  In this work, we present a robust phase retrieval problem where the task is to recover an unknown signal. Our proposed oracle avoids the need for computationally spectral descent, using a simple gradient step and outliers.
  arXiv  Detail & Related papers  (2024-09-07T06:37:23Z)
• 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)
• 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)
• PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [62.51015395213579]
  We consider the non-AL equilibrium nonconptotic objective function in two-player zero-sum continuous games. The proposed algorithm employs the movements of particles to represent the updates of random strategies for the $ilon$-mixed Nash equilibrium.
  arXiv  Detail & Related papers  (2023-03-02T05:08:15Z)
• Improved dimension dependence of a proximal algorithm for sampling [16.147290924171692]
  We propose a sampling algorithm that achieves superior complexity bounds in all the classical settings. Our algorithm is based on the proximal sampler introduced incitetlee 2021. For strongly log-concave distributions, our method has complexity bound $tildemathcalO(kappa d1/2)$ without warm start. For distributions satisfying the LSI, our bound is $tilde mathcalO(hat kappa d1/2)$ where $hat kappa$ is the ratio between smoothness and
  arXiv  Detail & Related papers  (2023-02-20T16:44:48Z)
• A Proximal Algorithm for Sampling [14.909442791255042]
  We study problems associated with potentials that lack smoothness. The potentials can be either convex or non-smooth. Our algorithm is based on a special case of rejection sampling.
  arXiv  Detail & Related papers  (2022-02-28T17:26:09Z)
• A Proximal Algorithm for Sampling from Non-smooth Potentials [10.980294435643398]
  We propose a novel MCMC algorithm for sampling from non-smooth potentials. Our method is based on the proximal bundle method and an alternating sampling framework. One key contribution of this work is a fast algorithm that realizes the restricted Gaussian oracle for any convex non-smooth potential.
  arXiv  Detail & Related papers  (2021-10-09T15:26:07Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  It is essential to theoretically guarantee that algorithms provide small objective residual with high probability. Existing methods for non-smooth convex optimization have complexity bounds with dependence on confidence level. We propose novel stepsize rules for two methods with gradient clipping.
  arXiv  Detail & Related papers  (2021-06-10T17:54:21Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  We investigate the problem of best-policy identification in discounted Markov Decision (MDPs) when the learner has access to a generative model. The advantages of state-of-the-art algorithms are discussed and illustrated.
  arXiv  Detail & Related papers  (2020-09-28T15:22:24Z)
• Stochastic Saddle-Point Optimization for Wasserstein Barycenters [69.68068088508505]
  We consider the populationimation barycenter problem for random probability measures supported on a finite set of points and generated by an online stream of data. We employ the structure of the problem and obtain a convex-concave saddle-point reformulation of this problem. In the setting when the distribution of random probability measures is discrete, we propose an optimization algorithm and estimate its complexity.
  arXiv  Detail & Related papers  (2020-06-11T19:40:38Z)

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.