arXiv research

Stochastic kernel based dimensionality reduction approaches have become popular in the last decade. The central component of many of these methods is a symmetric kernel that quantifies the vicinity between pairs of data points and a kernel-induced Markov chain on the data. Typically, the Markov chain is fully specified…

New method trains Markov kernels for efficient sampling.

New concentration inequality for U-statistics of Markov chains.

Study Markov chain gradient descent in Hilbert spaces for quadratic loss.

The paper analyzes covariate shift in nonparametric regression with Markovian data.

The paper develops new inequalities for Markov chain sums, linking them to mixing time.

New density estimator from Markov Chains outperforms KDE.

We introduce a new geometric approach that constructs a transition kernel of Markov chain. Our method always minimizes the average rejection rate and even reduce it to zero in many relevant cases, which cannot be achieved by conventional methods, such as the Metropolis-Hastings algorithm or the heat bath algorithm (Gib…

Paper improves generalization bounds for multi-kernel learning with mixed datasets.

Extended elliptical slice sampling for infinite-dimensional spaces, proving reversibility.

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…

A new method calculates intrinsic effective sample size for manifold-valued data.

We investigate the statistical complexity of estimating the parameters of a discrete-state Markov chain kernel from a single long sequence of state observations. In the finite case, we characterize (modulo logarithmic factors) the minimax sample complexity of estimation with respect to the operator infinity norm, while…

New algorithm clusters trajectories from multiple Markov chains with near-optimal error.

New bounds for SMC show its advantage over MCMC in multimodal distributions.

Transformers with multiple layers learn to estimate bigram distributions, while single-layer models often get stuck in unigram local minima.

This paper develops tools for nonreversible MCMC with convergence guarantees.

We consider the problem of learning low-dimensional representations for large-scale Markov chains. We formulate the task of representation learning as that of mapping the state space of the model to a low-dimensional state space, called the kernel space. The kernel space contains a set of meta states which are desired …

A new sampling method using log-concave Markov chains.

BARK optimizes black-box functions using Bayesian Additive Regression Trees.

Let K be an irreducible and reversible Markov kernel on a finite set X. We construct a metric W on the set of probability measures on X and show that with respect to this metric, the law of the continuous time Markov chain evolves as the gradient flow of the entropy. This result is a discrete counterpart of the Wassers…

Model detects market anomalies using a Hawkes process with hidden Markov chain.

In this contribution, we propose a new computationally efficient method to combine Variational Inference (VI) with Markov Chain Monte Carlo (MCMC). This approach can be used with generic MCMC kernels, but is especially well suited to \textit{MetFlow}, a novel family of MCMC algorithms we introduce, in which proposals a…

Stein importance sampling is a widely applicable technique based on kernelized Stein discrepancy, which corrects the output of approximate sampling algorithms by reweighting the empirical distribution of the samples. A general analysis of this technique is conducted for the previously unconsidered setting where samples…

Kernel-based methods improve policy evaluation in MRP models.

Adapts flow matching for MCMC to improve sampling efficiency.

We propose kernel sequential Monte Carlo (KSMC), a framework for sampling from static target densities. KSMC is a family of sequential Monte Carlo algorithms that are based on building emulator models of the current particle system in a reproducing kernel Hilbert space. We here focus on modelling nonlinear covariance s…

Bootstrap method for Markov chains in reinforcement learning.

KSD Thinning uses KSD to thin MCMC samples efficiently.

HDT improves MCMC on graphs with history-dependent sampling.

We introduce a conceptually novel structured prediction model, GPstruct, which is kernelized, non-parametric and Bayesian, by design. We motivate the model with respect to existing approaches, among others, conditional random fields (CRFs), maximum margin Markov networks (M3N), and structured support vector machines (S…

Optimizes MCMC output compression by selecting a subset of states.

New method reduces computational cost for Bayesian inference.

New method decomposes Markov chain rewards into persistent and transient components.

Compress++ speeds up distribution compression to near-linear time.

The paper provides concentration inequalities for Markov chain variance estimators.

A new method simulates a lazy version of a Markov chain for empirical inference.

Study online learning in RKHS with dependent processes, focusing on \(β\)- and \(φ\)-mixing.

Particle Markov chain Monte Carlo (PMCMC) is a systematic way of combining the two main tools used for Monte Carlo statistical inference: sequential Monte Carlo (SMC) and Markov chain Monte Carlo (MCMC). We present a novel PMCMC algorithm that we refer to as particle Gibbs with ancestor sampling (PGAS). PGAS provides t…

Reduces identity testing of reversible Markov chains to simpler symmetric chain tests.

Kernel methods summarize and integrate posterior similarity matrices from Bayesian clustering.

Develops a new risk measure for Markov chains' asymptotic behavior.

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…

Study nonparametric estimator for Markov chain transition matrices in offline setting.

New compression methods handle biased input sequences for more accurate posterior summaries.

The paper advances U-statistics in dependent settings, improving spectral estimation and goodness-of-fit tests.

Enhanced Markov chain sampler learns network statistics faster.

Proposes a new model for joint probability distributions in computer vision.