A fast asynchronous MCMC sampler for sparse Bayesian inference

• URL: http://arxiv.org/abs/2108.06446v1
• Date: Sat, 14 Aug 2021 02:20:49 GMT
• Title: A fast asynchronous MCMC sampler for sparse Bayesian inference
• Authors: Yves Atchad\'e and Liwei Wang
• Abstract summary: We propose a very fast approximate Markov Chain Monte Carlo (MCMC) sampling framework that is applicable to a large class of sparse Bayesian inference problems. We show that in high-dimensional linear regression problems, the Markov chain generated by the proposed algorithm admits an invariant distribution that recovers correctly the main signal.
• Score: 10.535140830570256
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose a very fast approximate Markov Chain Monte Carlo (MCMC) sampling framework that is applicable to a large class of sparse Bayesian inference problems, where the computational cost per iteration in several models is of order $O(ns)$, where $n$ is the sample size, and $s$ the underlying sparsity of the model. This cost can be further reduced by data sub-sampling when stochastic gradient Langevin dynamics are employed. The algorithm is an extension of the asynchronous Gibbs sampler of Johnson et al. (2013), but can be viewed from a statistical perspective as a form of Bayesian iterated sure independent screening (Fan et al. (2009)). We show that in high-dimensional linear regression problems, the Markov chain generated by the proposed algorithm admits an invariant distribution that recovers correctly the main signal with high probability under some statistical assumptions. Furthermore we show that its mixing time is at most linear in the number of regressors. We illustrate the algorithm with several models.

Related papers

• von Mises Quasi-Processes for Bayesian Circular Regression [57.88921637944379]
  We explore a family of expressive and interpretable distributions over circle-valued random functions. The resulting probability model has connections with continuous spin models in statistical physics. For posterior inference, we introduce a new Stratonovich-like augmentation that lends itself to fast Markov Chain Monte Carlo sampling.
  arXiv  Detail & Related papers  (2024-06-19T01:57:21Z)
• Computational-Statistical Gaps in Gaussian Single-Index Models [77.1473134227844]
  Single-Index Models are high-dimensional regression problems with planted structure. We show that computationally efficient algorithms, both within the Statistical Query (SQ) and the Low-Degree Polynomial (LDP) framework, necessarily require $Omega(dkstar/2)$ samples.
  arXiv  Detail & Related papers  (2024-03-08T18:50:19Z)
• Closed-form Filtering for Non-linear Systems [83.91296397912218]
  We propose a new class of filters based on Gaussian PSD Models, which offer several advantages in terms of density approximation and computational efficiency. We show that filtering can be efficiently performed in closed form when transitions and observations are Gaussian PSD Models. Our proposed estimator enjoys strong theoretical guarantees, with estimation error that depends on the quality of the approximation and is adaptive to the regularity of the transition probabilities.
  arXiv  Detail & Related papers  (2024-02-15T08:51:49Z)
• Dynamical System Identification, Model Selection and Model Uncertainty Quantification by Bayesian Inference [0.8388591755871735]
  This study presents a Bayesian maximum textitaposteriori (MAP) framework for dynamical system identification from time-series data.
  arXiv  Detail & Related papers  (2024-01-30T12:16:52Z)
• Stable generative modeling using Schrödinger bridges [0.22499166814992438]
  We propose a generative model combining Schr"odinger bridges and Langevin dynamics. Our framework can be naturally extended to generate conditional samples and to Bayesian inference problems.
  arXiv  Detail & Related papers  (2024-01-09T06:15:45Z)
• Probabilistic Unrolling: Scalable, Inverse-Free Maximum Likelihood Estimation for Latent Gaussian Models [69.22568644711113]
  We introduce probabilistic unrolling, a method that combines Monte Carlo sampling with iterative linear solvers to circumvent matrix inversions. Our theoretical analyses reveal that unrolling and backpropagation through the iterations of the solver can accelerate gradient estimation for maximum likelihood estimation. In experiments on simulated and real data, we demonstrate that probabilistic unrolling learns latent Gaussian models up to an order of magnitude faster than gradient EM, with minimal losses in model performance.
  arXiv  Detail & Related papers  (2023-06-05T21:08:34Z)
• Approximate Gibbs Sampler for Efficient Inference of Hierarchical Bayesian Models for Grouped Count Data [0.0]
  This research develops an approximate Gibbs sampler (AGS) to efficiently learn the HBPRMs while maintaining the inference accuracy. Numerical experiments using real and synthetic datasets with small and large counts demonstrate the superior performance of AGS.
  arXiv  Detail & Related papers  (2022-11-28T21:00:55Z)
• Langevin Monte Carlo for Contextual Bandits [72.00524614312002]
  Langevin Monte Carlo Thompson Sampling (LMC-TS) is proposed to directly sample from the posterior distribution in contextual bandits. We prove that the proposed algorithm achieves the same sublinear regret bound as the best Thompson sampling algorithms for a special case of contextual bandits.
  arXiv  Detail & Related papers  (2022-06-22T17:58:23Z)
• Sampling Approximately Low-Rank Ising Models: MCMC meets Variational Methods [35.24886589614034]
  We consider quadratic definite Ising models on the hypercube with a general interaction $J$. Our general result implies the first time sampling algorithms for low-rank Ising models.
  arXiv  Detail & Related papers  (2022-02-17T21:43:50Z)
• Multilevel Gibbs Sampling for Bayesian Regression [6.2997667081978825]
  The level hierarchy of data matrices is created by clustering the features and/or samples of data matrices. The use of correlated samples is investigated for variance reduction to improve the convergence of the Markov Chain. Speed-up is achieved for almost all of them without significant loss in predictive performance.
  arXiv  Detail & Related papers  (2020-09-25T11:18:17Z)
• Learning Gaussian Graphical Models via Multiplicative Weights [54.252053139374205]
  We adapt an algorithm of Klivans and Meka based on the method of multiplicative weight updates. The algorithm enjoys a sample complexity bound that is qualitatively similar to others in the literature. It has a low runtime $O(mp2)$ in the case of $m$ samples and $p$ nodes, and can trivially be implemented in an online manner.
  arXiv  Detail & Related papers  (2020-02-20T10:50:58Z)

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.