A Fast, Robust Elliptical Slice Sampling Implementation for Linearly Truncated Multivariate Normal Distributions

• URL: http://arxiv.org/abs/2407.10449v1
• Date: Mon, 15 Jul 2024 05:40:11 GMT
• Title: A Fast, Robust Elliptical Slice Sampling Implementation for Linearly Truncated Multivariate Normal Distributions
• Authors: Kaiwen Wu, Jacob R. Gardner,
• Abstract summary: slice sampling is a rejection-free Markov chain Monte Carlo method. The main novelty of this paper is an algorithm that computes an intersection in $mathcalO(m log m)$ time. We show that an implementation based on this algorithm enhances numerical stability, speeds up running time, and is easy to parallelize for launching multiple Markov chains.
• Score: 12.800664845601197
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Elliptical slice sampling, when adapted to linearly truncated multivariate normal distributions, is a rejection-free Markov chain Monte Carlo method. At its core, it requires analytically constructing an ellipse-polytope intersection. The main novelty of this paper is an algorithm that computes this intersection in $\mathcal{O}(m \log m)$ time, where $m$ is the number of linear inequality constraints representing the polytope. We show that an implementation based on this algorithm enhances numerical stability, speeds up running time, and is easy to parallelize for launching multiple Markov chains.

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)
• Faster Sampling from Log-Concave Densities over Polytopes via Efficient Linear Solvers [29.212403229351253]
  We present a nearly-optimal implementation of this Markov chain with per-step complexity which is roughly the number of non-zero entries of $A$ while the number of Markov chain steps remains the same. Key technical ingredients are 1) to show that the matrices that arise in this Dikin walk change slowly, 2) to deploy efficient linear solvers that can leverage this slow change to speed up matrix inversion by using information computed in previous steps, and 3) to speed up the computation of the determinantal term in the Metropolis filter step via a randomized Taylor series-based estimator.
  arXiv  Detail & Related papers  (2024-09-06T14:49:43Z)
• Finite-time High-probability Bounds for Polyak-Ruppert Averaged Iterates of Linear Stochastic Approximation [22.51165277694864]
  This paper provides a finite-time analysis of linear approximation (LSA) algorithms with fixed step size. LSA is used to compute approximate solutions of a $d$-dimensional linear system.
  arXiv  Detail & Related papers  (2022-07-10T14:36:04Z)
• 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)
• 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)
• Unfolding Projection-free SDP Relaxation of Binary Graph Classifier via GDPA Linearization [59.87663954467815]
  Algorithm unfolding creates an interpretable and parsimonious neural network architecture by implementing each iteration of a model-based algorithm as a neural layer. In this paper, leveraging a recent linear algebraic theorem called Gershgorin disc perfect alignment (GDPA), we unroll a projection-free algorithm for semi-definite programming relaxation (SDR) of a binary graph. Experimental results show that our unrolled network outperformed pure model-based graph classifiers, and achieved comparable performance to pure data-driven networks but using far fewer parameters.
  arXiv  Detail & Related papers  (2021-09-10T07:01:15Z)
• Nonparametric Extrema Analysis in Time Series for Envelope Extraction, Peak Detection and Clustering [0.0]
  We propose a nonparametric approach that can be used in envelope extraction, peak-burst detection and clustering in time series. Our problem formalization results in a naturally defined splitting/forking of the time series.
  arXiv  Detail & Related papers  (2021-09-05T14:21:24Z)
• Linear-Sample Learning of Low-Rank Distributions [56.59844655107251]
  We show that learning $ktimes k$, rank-$r$, matrices to normalized $L_1$ distance requires $Omega(frackrepsilon2)$ samples. We propose an algorithm that uses $cal O(frackrepsilon2log2fracepsilon)$ samples, a number linear in the high dimension, and nearly linear in the matrices, typically low, rank proofs.
  arXiv  Detail & Related papers  (2020-09-30T19:10:32Z)
• Sample Complexity of Asynchronous Q-Learning: Sharper Analysis and Variance Reduction [63.41789556777387]
  Asynchronous Q-learning aims to learn the optimal action-value function (or Q-function) of a Markov decision process (MDP) We show that the number of samples needed to yield an entrywise $varepsilon$-accurate estimate of the Q-function is at most on the order of $frac1mu_min (1-gamma)5varepsilon2+ fract_mixmu_min (1-gamma)$ up to some logarithmic factor.
  arXiv  Detail & Related papers  (2020-06-04T17:51:00Z)
• On Linear Stochastic Approximation: Fine-grained Polyak-Ruppert and Non-Asymptotic Concentration [115.1954841020189]
  We study the inequality and non-asymptotic properties of approximation procedures with Polyak-Ruppert averaging. We prove a central limit theorem (CLT) for the averaged iterates with fixed step size and number of iterations going to infinity.
  arXiv  Detail & Related papers  (2020-04-09T17:54:18Z)
• SURF: A Simple, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  SURF is an algorithm for approximating distributions by piecewises. It outperforms state-of-the-art algorithms in experiments.
  arXiv  Detail & Related papers  (2020-02-22T01:03:33Z)

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.