Study nonparametric estimator for Markov chain transition matrices in offline setting.
problem Estimating transition matrices of finite controlled Markov chains from logged data.
method Developed sample complexity bounds and conditions for minimaxity.
result Achieving certain statistical risk requires balancing mixing properties and sample size.
Reduces identity testing of reversible Markov chains to simpler symmetric chain tests.
problem Testing identity of reversible Markov chains from a single trajectory.
method Using lumping-congruent Markov embeddings, the problem is simplified to testing symmetric chains over a larger state space.
result Achieves state-of-the-art sample complexity for identity testing.
The paper studies how quickly samples from Langevin dynamics become independent.
problem Understanding the dependence between samples along Langevin dynamics and related algorithms.
method Measures dependence via Φ-mutual information and proves strong data processing inequalities. result The Φ-mutual information between samples decreases exponentially to zero. Estimates covariance matrices using Markov chain Monte Carlo with improved sample complexity.
problem Complexity of covariance matrix estimation for Gibbs distributions.
method Uses Markov chain Monte Carlo with conditions on the chain's spectral gap and Poincaré inequality.
result Achieves similar sample complexity as i.i.d. samples with better query complexity.
New method trains Markov kernels for efficient sampling.
problem Efficient sampling from complex probability distributions.
method Adversarial learning of involutive Metropolis-Hastings kernels.
result Minimizes total variation distance to empirical data.
Study Markov chain gradient descent in Hilbert spaces for quadratic loss.
problem Approximating optimal solutions for quadratic loss functions.
method Developed a Markov chain-based stochastic gradient algorithm in Hilbert spaces.
result Established probabilistic upper bounds on convergence.
Extended elliptical slice sampling for infinite-dimensional spaces, proving reversibility.
problem Proving reversibility of elliptical slice sampling in infinite-dimensional spaces.
method Extended elliptical slice sampling to infinite-dimensional separable Hilbert spaces, providing an alternative proof of reversibility.
result The approach yields a positive semi-definite Markov operator, proving reversibility.
A new sampling method using log-concave Markov chains.
problem Sampling from unnormalized densities efficiently.
method Decomposes sampling into log-concave Markov chains with noisy measurements.
result Shows remarkable capacity to 'tunnel' between modes of a distribution.
We study the problem of learning the transition matrices of a set of Markov chains from a single stream of observations on each chain. We assume that the Markov chains are ergodic but otherwise unknown. The learner can sample Markov chains sequentially to observe their states. The goal of the learner is to sequentially…
Decentralized stochastic gradient method emerges as a promising solution for solving large-scale machine learning problems. This paper studies the decentralized Markov chain gradient descent (DMGD) algorithm - a variant of the decentralized stochastic gradient methods where the random samples are taken along the trajec…
The paper tackles learning from non-irreducible Markov chains, proving learnability and generalization bounds.
problem Learning from temporal dependent data with non-irreducible Markov chains.
method Uniform convergence and generalization bounds for sample error under uniform ergodicity.
result Learnability and generalization bounds for approximate sample error minimization algorithm.
The paper extends Hoeffding's inequality for Markov chains using a generalized concentrability condition.
problem Applying Hoeffding's inequality to non-ergodic Markov chains.
method Integrates generalized concentrability condition via IPM to extend traditional hypotheses.
result Demonstrates utility in machine learning applications such as empirical risk minimization and bandits.
We analyze a new Markov chain model for better sampling and optimization.
problem Developing a new Markov chain model for improved sampling and optimization.
method We introduce a new class of Ito chains with arbitrary noise and inexact drift/diffusion coefficients, proving a bound in W2-distance. result Our analysis provides improved or first results for various applications like SGLD, sampling, and boosting.
DCDC calculates convergence rates for Markov chains using neural networks.
problem Computing precise convergence rates for Markov chains is hard.
method Developed a neural network-based algorithm (DCDC) to bound convergence rates in Wasserstein distance.
result Demonstrated effective convergence bounds for real-world Markov chains.
Improved Bayesian regression for large datasets using multilevel Gibbs sampling.
problem Efficiently handling large-scale Bayesian regression with complex posterior distributions.
method Developed a multilevel Gibbs sampler for linear mixed models, incorporating data clustering and correlated samples for variance reduction.
result Significant speed-up achieved for Bayesian regression without sacrificing predictive performance.
Improved sampling for network community detection.
problem Inefficient sampling from network partition posterior distributions.
method Merge-split Markov chain Monte Carlo for efficient sampling.
result Significantly improved mixing time and correct sampling.
Matrix Chernoff bound for Markov chains applied to co-occurrence matrices.
problem Analyzing the behavior of co-occurrence statistics in sequential data.
method Proved a matrix Chernoff-type bound for sums of matrix-valued random variables sampled via a regular Markov chain.
result Achieved exponentially fast convergence rate and sample complexity analysis for co-occurrence matrices.
Stochastic gradient methods are the workhorse (algorithms) of large-scale optimization problems in machine learning, signal processing, and other computational sciences and engineering. This paper studies Markov chain gradient descent, a variant of stochastic gradient descent where the random samples are taken on the t…
Enhanced Markov chain sampler learns network statistics faster.
problem Learning network statistics efficiently.
method Integrates graph Forman curvature into Markov chain transition probabilities and stationary distribution.
result Curved Markov chain Monte Carlo achieves faster convergence.
The Riemannian barycentre is one of the most widely used statistical descriptors for probability distributions on Riemannian manifolds. At present, existing algorithms are able to compute the Riemannian barycentre of a probability distribution, only if i.i.d. samples of this distribution are readily available. However,…
We study the problem of hypothesis testing between two discrete distributions, where we only have access to samples after the action of a known reversible Markov chain, playing the role of noise. We derive instance-dependent minimax rates for the sample complexity of this problem, and show how its dependence in time is…
PL-MCMC samples from normalizing flows' conditional distributions.
problem Sampling from complex conditional distributions learned by normalizing flows.
method Metropolis-Hastings implementation of PL-MCMC.
result PL-MCMC asymptotically samples from exact conditional distributions.
Probabilistic models are conceptually powerful tools for finding structure in data, but their practical effectiveness is often limited by our ability to perform inference in them. Exact inference is frequently intractable, so approximate inference is often performed using Markov chain Monte Carlo (MCMC). To achieve the…
We exhibit an efficient procedure for testing, based on a single long state sequence, whether an unknown Markov chain is identical to or ε-far from a given reference chain. We obtain nearly matching (up to logarithmic factors) upper and lower sample complexity bounds for our notion of distance, which is bas…
Estimates Markov chain variance efficiently without storing samples.
problem Estimating the asymptotic variance of Markov chain functions.
method Linear stochastic approximation of Poisson equation solution.
result Optimal MSE convergence rate with finite sample guarantees.
Computing partition functions, the normalizing constants of probability distributions, is often hard. Variants of importance sampling give unbiased estimates of a normalizer Z, however, unbiased estimates of the reciprocal 1/Z are harder to obtain. Unbiased estimates of 1/Z allow Markov chain Monte Carlo sampling of "d…
A key task in Bayesian statistics is sampling from distributions that are only specified up to a partition function (i.e., constant of proportionality). However, without any assumptions, sampling (even approximately) can be #P-hard, and few works have provided "beyond worst-case" guarantees for such settings. For log-c…
New MCMC method corrects bias without extra cost.
problem Correcting bias in MCMC algorithms without additional computational cost.
method Generalized Markov Chain Importance Sampling methods.
result Proposed methods are more efficient than Metropolis-Hastings versions.
A new algorithm speeds up elliptical slice sampling for truncated multivariate normals.
problem Efficiently sampling from truncated multivariate normal distributions with linear constraints.
method Adapting elliptical slice sampling to linearly truncated multivariate normals, with an algorithm for ellipse-polytope intersection in O(m log m) time.
result The algorithm enhances numerical stability, speeds up running time, and is easy to parallelize.
New density estimator from Markov Chains outperforms KDE.
problem Density estimation from Markov Chains.
method Nonparametric density estimator based on Markov Chains.
result Consistent and outperforms KDE in large sample size and high dimensionality.
The paper establishes CLTs for Markov chains and improves sampling algorithms for heavy-tailed distributions.
problem Establishing central limit theorems for ergodic averages of Markov chains.
method Drift conditions to provide necessary and sufficient conditions for CLTs, including lower bounds on convergence rates.
result Sharp conditions and convergence rates for various MCMC algorithms on heavy-tailed targets.
The paper improves Stein importance sampling for Markov chain samples.
problem Improving the accuracy of sampling from complex distributions.
method Reproducing Stein kernels approach for post-hoc correction.
result Consistent estimators for target distributions using geometrically ergodic Markov chains.
Improves MCMC performance with adaptive affine transformations.
problem Improving the performance of Markov Chain Monte Carlo samplers.
method Adaptive learning of bijective affine transformations during sampling.
result Adaptive affine transformations improve the quality of samples at low computational cost.
This paper models time-series data with a mixture of Markov chains, automatically determining the number of components.
problem Tackles the inability of common Markov state modeling frameworks to discern heterogeneities in complex data.
method Uses a mixture of Markov chains and variational expectation-maximization algorithm for automatic component selection.
result Achieves performance consistent with theoretically optimal error scaling, identifying meaningful heterogeneities in various data sets.
Existing Markov Chain Monte Carlo (MCMC) methods are either based on general-purpose and domain-agnostic schemes which can lead to slow convergence, or hand-crafting of problem-specific proposals by an expert. We propose A-NICE-MC, a novel method to train flexible parametric Markov chain kernels to produce samples with…
Markov chain (MC) algorithms are ubiquitous in machine learning and statistics and many other disciplines. Typically, these algorithms can be formulated as acceptance rejection methods. In this work we present a novel estimator applicable to these methods, dubbed Markov chain importance sampling (MCIS), which efficient…
Elliptical slice sampling converges geometrically, providing reliable sampling for Bayesian learning.
problem Sampling from posterior distributions in Bayesian learning.
method Elliptical slice sampling, geometric ergodicity.
result Elliptical slice sampling yields geometric convergence guarantees under weak regularity assumptions.
Bayesian Context Trees improve change-point detection in discrete data.
problem Detecting and segmenting change-points in discrete time series data.
method Bayesian Context Trees framework, Markov chain Monte Carlo sampling.
result Effective sampling from posterior distribution of change-points.
A new sampler improves the inference of causal structures from observational data.
problem Inferring causal relationships from observational data when DAGs are Markov equivalent.
method Developed a non-reversible Markov chain, Causal Zig-Zag sampler, targeting Markov Equivalence Classes of DAGs.
result The sampler improves mixing and offers efficient algorithms for DAG inference.
This article provides the first procedure for computing a fully data-dependent interval that traps the mixing time tmix of a finite reversible ergodic Markov chain at a prescribed confidence level. The interval is computed from a single finite-length sample path from the Markov chain, and does not require t…
Efficiently implements polar slice sampling for high-dimensional distributions.
problem Sampling from difficult-to-implement distributions in high dimensions.
method Separates directional and radial components for efficient implementation.
result Outperforms related methods in various settings.
Uniform TD(0) bound derived for function approximation with Markov noise.
problem Uniform concentration bound for TD(0) with function approximation.
method Contractive stochastic approximation, martingale and Markov noises, Poisson equation, relaxed concentration inequalities.
result Uniform all-time concentration bound for TD(0) with linear function approximation.
Efficiently samples multimodal distributions using data-based initialization.
problem Sampling multimodal distributions with limited samples.
method Data-based initialization for Markov chains with spectral gap.
result Efficiently generates samples close to stationary distribution.
Estimating the entropy based on data is one of the prototypical problems in distribution property testing and estimation. For estimating the Shannon entropy of a distribution on S elements with independent samples, [Paninski2004] showed that the sample complexity is sublinear in S, and [Valiant--Valiant2011] showed…
New algorithms sample convex bodies using Markov chains and restricted Gaussian oracles.
problem Sampling uniformly from convex bodies efficiently.
method Markov chain Monte Carlo with proximal sampler and restricted Gaussian oracle.
result Efficient implementation of RGO for uniform sampling on convex bodies.
Proposes MIVI for efficient posterior estimation and design of MCMC transitions.
problem Efficiently estimating posterior distributions in constrained time.
method Combines variational inference and MCMC with a variational distribution and optimized Markov chain.
result Optimized Markov chain improves variational distribution and vice versa, leading to more accurate posteriors.
New bounds for SMC show its advantage over MCMC in multimodal distributions.
problem Estimating expectations under multimodal distributions with slow global mixing.
method Proves finite sample complexities for SMC with local mixing times, addressing bias through sequential resampling.
result SMC provides fully polynomial time approximation for multimodal problems.
We perform Markov chain Monte Carlo simulations for a Bayesian inference of the GJR-GARCH model which is one of asymmetric GARCH models. The adaptive construction scheme is used for the construction of the proposal density in the Metropolis-Hastings algorithm and the parameters of the proposal density are determined ad…