New method improves convergence of gradient descent for non-convex, non-reversible Markov chains.
problem Improving convergence of gradient descent for non-convex, non-reversible Markov chains.
method Introducing a new technique that varies the mixing levels of the Markov chains to establish non-ergodic convergence under wider step sizes.
result Established non-ergodic convergence for non-convex problems and non-reversible finite-state Markov chains.
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.
A new sampler speeds up Bayesian mixture models.
problem Sampling from Bayesian finite mixture models is slow and hard.
method Introduces a non-reversible sampling scheme for Bayesian finite mixture models.
result The new sampler outperforms classical samplers in many scenarios, especially during convergence.
Estimates Markov chain mixing time from a single trajectory.
problem Estimating mixing time of Markov chains from a single trajectory.
method Contraction with respect to total variation, inspired by Wolfer's contraction coefficient.
result Improved confidence intervals and instance-dependent rates for estimating Markov chains.
Estimates mixing time of non-reversible Markov chains from a single trajectory.
problem Estimating mixing time of non-reversible Markov chains from a single trajectory.
method Estimates pseudo-spectral gap instead of spectral gap, achieving polynomial dependence on minimal stationary probability and pseudo-spectral gap.
result Achieves polynomial dependence on minimal stationary probability and pseudo-spectral gap, overcoming the loss of symmetry.
The paper proves inequalities for Steklov eigenvalues on finite graphs.
problem Eigenvalues of Laplacians for reversible Markov chains and Steklov eigenvalues.
method Generalized Cheeger inequalities, convergence results, and resolvent convergence.
result Sharp estimate for the first non-trivial Steklov eigenvalue.
HDT improves MCMC on graphs with history-dependent sampling.
problem Efficient sampling from target distributions on general graphs with low computational overhead.
method History-driven target (HDT) framework that replaces the original target distribution with a history-dependent one.
result Near-zero variance performance and scalability to large graphs with memory-efficient implementation.
New algorithm speeds up sampling for complex statistical models.
problem Sampling parameters of high-dimensional CTMCs is challenging.
method Developed a local version of the Bouncy Particle Sampler (BPS) with exact event times.
result Algorithm achieves favorable computational efficiency for real-data scenarios.
The book covers scalable MCMC methods for Bayesian learning.
problem Scalability issues in Bayesian learning with large datasets.
method Advanced MCMC algorithms, including stochastic gradient, non-reversible, and continuous time methods.
result Substantial advances in practical and theoretical Bayesian computation.
New PDMP samplers tackle variable selection in models.
problem Jointly explore model space and parameter space.
method Develop reversible jump PDMP samplers.
result New samplers mix better and are more efficient.
New methods improve efficiency of sampling algorithms for complex systems.
problem Efficiently sampling from complex, high-dimensional probability distributions.
method Randomized Runge-Kutta-Nyström methods tailored for Hamiltonian flows.
result Quantitative 5/2-order L2-accuracy in approximating Hamiltonian flows. The paper estimates Betti numbers for graphs with specific curvatures, proving bounds and characterizing rigidity.
problem Estimating Betti numbers for graphs with non-negative curvatures.
method Establishing Betti number estimates for graphs with non-negative Ollivier and Bakry-Émery curvatures.
result Upper bounds on the first Betti number for graphs with non-negative curvatures, with characterizations of rigidity.
We introduce a novel class of labeled directed acyclic graph (LDAG) models for finite sets of discrete variables. LDAGs generalize earlier proposals for allowing local structures in the conditional probability distribution of a node, such that unrestricted label sets determine which edges can be deleted from the underl…
Blang simplifies Bayesian analysis for non-standard data types.
problem Bayesian inference for non-standard data structures.
method Bayesian declarative language, distribution continua, sequential Monte Carlo, non-reversible MCMC.
result Bayesian analysis on arbitrary data types is feasible and efficient.
This thesis tackles non-convex Bayesian learning via scalable dynamic importance sampling algorithms.
problem Non-convex Bayesian learning problem in deep neural networks.
method Replica exchange Langevin Monte Carlo, control variates method, population-chain replica exchange, scalable dynamic importance sampling.
result Control variates method reduces variance and accelerates convergence in non-convex Bayesian learning.
The Bouncy Particle Sampler is a novel rejection-free non-reversible sampler for differentiable probability distributions over continuous variables. We generalize the algorithm to piecewise differentiable distributions and apply it to generic binary distributions using a piecewise differentiable augmentation. We illust…
The paper provides concentration inequalities for Markov chain variance estimators.
problem Estimating the variance of Markov chains with concentration properties.
method Martingale decomposition method for uniformly geometrically ergodic Markov chains.
result Explicit control of the p-th moment of the OBM estimator difference and dependence on p and mixing time.
A new method simulates a lazy version of a Markov chain for empirical inference.
problem Estimating and testing unknown Markov chains with limited data.
method Simulates an α-lazy version of an unknown Markov chain, making it ergodic.
result The pseudo spectral gap can be applied to non-ergodic Markov chains.
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.
Algorithm learns transition matrices of multiple unknown Markov chains.
problem Learning transition matrices of multiple unknown Markov chains.
method Adaptive allocation of Markov chains for sequential learning.
result Algorithm efficiently balances exploration and exploitation, achieving optimal asymptotic loss.
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.
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.
This paper introduces a new method for optimizing large-scale problems using Markov chain block updates.
problem Optimizing large-scale problems with efficient and natural block selection.
method Markov chain block coordinate descent (BCD) for optimization.
result The method converges for minimizing Lipschitz differentiable functions, with sublinear and linear convergence rates for convex and strongly convex functions, respectively.
Theory of graphical models has matured over more than three decades to provide the backbone for several classes of models that are used in a myriad of applications such as genetic mapping of diseases, credit risk evaluation, reliability and computer security, etc. Despite of their generic applicability and wide adoptan…
Boundary rigidity proven for non-reversible Finsler metrics.
problem Recovering non-reversible Finsler metrics from boundary distance data.
method Sum of reversible Finsler norm and closed 1-form, boundary rigidity results.
result 1-form can be uniquely recovered from boundary distance data.
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.
Characterizes isometries between non-reversible Finsler manifolds.
problem Understanding isometries in non-reversible Finsler manifolds.
method Generalization of Myers-Nakai Theorem for Riemannian manifolds, modification of function spaces to accommodate asymmetric structure.
result Functional characterization of isometries between non-reversible Finsler manifolds.
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…
Procedure tests if unknown Markov chain matches a reference chain.
problem Testing if an unknown Markov chain matches a reference chain.
method An efficient procedure based on a single long state sequence.
result Nearly matching upper and lower sample complexity bounds for total variation distance.
New algorithm tests Markov chains without hitting.
problem Testing Markov chains with unknown transition matrix.
method Combining approximation algorithms and spectral analysis.
result Efficient testing of Markov chains without hitting time dependence.
Expands Hidden Markov Model to include Markov chain observations.
problem Handling Markov chain observations in Hidden Markov Models.
method Developed Expectation-Maximization algorithm and Viterbi algorithm analogs.
result Estimates transition probabilities for hidden states and observations.
In this paper we describe three stochastic models based on a semi-Markov chains approach and its generalizations to study the high frequency price dynamics of traded stocks. The three models are: a simple semi-Markov chain model, an indexed semi-Markov chain model and a weighted indexed semi-Markov chain model. We show…
New insights into Markov chain geometry via positive transition measures.
problem Lack of statistical meaning in the space of transition probabilities.
method Constructing an extension of the space of transition probabilities using Amari's theory of positive measures.
result Introduction of a new dually flat structure for the space of positive transition measures.
In his 2011 work, Maas has shown that the law of any time-reversible continuous-time Markov chain with finite state space evolves like a gradient flow of the relative entropy with respect to its stationary distribution. In this work we show the converse to the above by showing that if the relative law of a Markov chain…
New method estimates convergence bounds for nonlinear Markov chains.
problem Difficulty in describing properties of nonlinear Markov chains.
method Coupling Markov chains to reconstitute distribution relationships and estimate convergence bounds.
result Estimation of convergence bounds is more precise than existing results.
Elo ratings learn model parameters quickly using Markov chains.
problem Ranking players in online settings.
method Bradley--Terry--Luce model and Markov chain theory.
result Elo learns model parameters at a competitive rate.
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.
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. 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.
Method reconstructs hidden Markov chains from insurance data.
problem Recovering hidden Markov chains from incomplete insurance data.
method Neural architecture to explicitly provide transition probabilities.
result Neural model successfully validates decompression of insurance information.
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.
Identity testing for reversible Markov chains without symmetry assumption.
problem Identity testing of reversible Markov chains.
method Using distance notion from Daskalakis et al. [2018a], testing without symmetry assumption.
result It is possible to perform identity testing under weaker assumption of reversibility.
Unbiased gradient estimation for Markov chains
problem Estimating gradients of stationary means in Markov chains
method Propose new unbiased estimators
result Improves efficiency for slow mixing Markov chains
Study hypothesis testing for noisy Markov chain samples.
problem Hypothesis testing between two discrete distributions via noisy Markov chain samples.
method Derive instance-dependent minimax rates and analyze spectral properties of the Markov chain.
result Wide statistical window in sample complexity for different initial distributions.
Adaptive algorithm improves convergence rate of Langevin dynamics.
problem Improving convergence rate of Langevin dynamics.
method Adaptive non-reversible stochastic gradient Langevin dynamics algorithm.
result Improved convergence rate of the algorithm.
Efficient variance reduction for Markov chains using martingale representations.
problem Reducing variance in estimating additive functionals of Markov chains.
method A novel discrete time martingale representation approach for variance reduction.
result The proposed method achieves a lower cost-to-variance product than the naive approach.
New algorithm for Riemannian barycentre from Markov chain samples.
problem Computing Riemannian barycentre from non-i.i.d. Markov chain samples.
method Proposes a new Markov chain Monte Carlo algorithm for Riemannian barycentre computation.
result Algorithm converges to Riemannian barycentre of stationary distribution.
New framework improves variational inference with Markov chain methods.
problem Challenges of minimizing KL divergence with stochastic gradient descent.
method Markov chain score ascent (MCSA) methods, including parallel MCSA (pMCSA).
result Improved theoretical and empirical performance of MCSA methods.