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.
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.
Proves limiting distributions for Markov chains in random environments.
problem Analyzing Markov chains in random environments.
method Proves existence of limiting distributions using drift and minorization conditions.
result Law of large numbers holds for bounded functionals of the process.
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
Extends inequalities to nonstationary Markov chains for better risk bounds.
problem Proving inequalities for nonstationary, non-i.i.d. Markov chains.
method Extends Dedecker and Fan's (2015) inequalities to nonstationary Markov chains.
result Provides a Bernstein-type inequality for periodic autoregressive processes.
The paper analyzes SGD and its convergence using Markov chain theory.
problem Analyzing the convergence of SGD with constant step-size.
method Integrates Markov chain theory into SGD analysis and uses Richardson-Romberg extrapolation.
result Provides an explicit asymptotic expansion of SGD iterates moments.
Unified framework for MCMC and machine learning problems.
problem Intersection of MCMC and machine learning problems.
method Unified framework integrating various MCMC and machine learning techniques.
result Translation and generalization of theory and methods.
Unified framework for analyzing convergence of RSAs using Wasserstein divergence.
problem Analyzing convergence of constant stepsize recursive stochastic algorithms (RSAs).
method Lifting RSA into a higher-dimensional space as a Markov chain and studying the distribution's contraction property with respect to Wasserstein divergence.
result RSAs' iterates' distribution converges to an invariant distribution under certain contraction properties.
New empirical PAC-Bayes bound for Markov chains with finite state space.
problem Lack of empirical bounds for Markov chains with temporal dependence.
method Proved a new PAC-Bayes bound for Markov chains, providing an empirical pseudo-spectral gap.
result First fully empirical PAC-Bayes bound for Markov chains with finite state space.
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.
This paper analyzes stability and generalization of Markov chain stochastic gradient methods.
problem Analyzing stability and generalization of Markov chain stochastic gradient methods.
method Algorithmic stability in statistical learning theory.
result Established optimal generalization bounds for both smooth and non-smooth cases.
New theory helps MCMC algorithms work well in parallel systems.
problem Proving convergence of asynchronous MCMC methods.
method Developed new convergence theory for asynchronous MCMC algorithms.
result Understood and provided guidelines for making asynchronous MCMC algorithms converge.
Regime-switching models, in particular Hidden Markov Models (HMMs) where the switching is driven by an unobservable Markov chain, are widely-used in financial applications, due to their tractability and good econometric properties. In this work we consider HMMs in continuous time with both constant and switching volati…
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.
Model credit ratings using economic states with Markov chains.
problem Credit rating migration influenced by economic state changes.
method Developed a Markov chain model for credit ratings conditional on economic states.
result Derived asymptotic behavior of the rating process using Markov theory.
Simplified proof shows SGD optimality for least squares.
problem Optimizing SGD for least squares efficiency.
method Analyzing SGD as a stochastic process, characterizing stationary covariance matrix.
result Statistical minimax optimality of SGD for least squares.
We systematically investigate the problem of representing Markov chains by families of random maps, and which regularity of these maps can be achieved depending on the properties of the probability measures. Our key idea is to use techniques from optimal transport to select optimal such maps. Optimal transport theory a…
LLMs are compared to Markov chains for natural language processing.
problem Theoretical analysis of LLMs' generalization capabilities.
method Equivalence between LLMs and Markov chains, studying multi-step inference.
result Derives generalization bounds for LLMs, capturing their behavior in practice.
New Markov chains defined on simplicial complexes for understanding their topology.
problem Understanding the topology of simplicial complexes and hypergraphs.
method Defining new Markov chains on simplicial complexes and studying their properties.
result The generator of the new Markov chain is the upper Laplacian, and the Markov chain is positive recurrent.
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.
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.
Enlargement of filtrations is a classical topic in the general theory of stochastic processes. This theory has been applied to stochastic finance in order to analyze models with insider information. In this paper we study initial enlargement in a Markov chain market model, introduced by R. Norberg. In the enlargened fi…
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.
New method adds user constraints to Markov chains for better data reduction.
problem No systematic framework to impose user-defined constraints on Markov chains.
method Path entropy maximization to derive transition probabilities with user constraints.
result Improved nonlinear dimensionality reduction with user-prescribed constraints.
A new metric based on hitting probabilities for directed graphs and Markov chains.
problem Lack of metrics specifically adapted to asymmetric structure of directed graphs and Markov chains.
method Metric based on hitting probabilities, insensitive to shortest and average walk distances.
result New structural theory of directed graphs and utility for various applications.
Optimizes MCMC chains with neural control variates.
problem Reducing variance in Markov Chain Monte Carlo (MCMC) simulations.
method Uses neural networks as control variates to minimize asymptotic variance.
result Derives optimal convergence rate under various ergodicity assumptions.
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.
The Viterbi process can be extended indefinitely in a pairwise Markov model.
problem Estimating hidden chains in pairwise Markov models.
method Construction of barriers to ensure Viterbi path goes through states.
result The Viterbi process is regenerative in the PMM.
The paper extends game theory using Hodge theory on graphs.
problem Generalizing Shapley's value allocation formula for cooperative games on graphs.
method Connecting stochastic path integrals to Hodge-theoretic Poisson's equations on graphs.
result The value allocation operator is the solution to Poisson's equation in combinatorial Hodge theory.
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.
Paper analyzes and accelerates Langevin Monte Carlo methods using large deviations theory.
problem High-dimensional sampling problems in machine learning.
method Unified approach using large deviations theory to study and accelerate Langevin dynamics variants.
result Efficiency of Langevin dynamics variants demonstrated through numerical experiments.
This paper compares HMC and RNN expressivity using SRT.
problem Comparing expressivity of HMC and RNN models.
method Embed HMC and RNN in a GUM, use SRT to compare structured covariance series.
result Conditions for realizing covariance series by GUM, HMC, or RNN.
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.
The paper tackles learning optimal predictions from a single trajectory of a stochastic dynamical system.
problem Learning from a single finite trajectory of an ergodic stochastic dynamical system.
method The approach involves estimating the optimal one-step prediction function using nonlinear least squares and deriving high-probability guarantees.
result The study provides high-probability guarantees for the optimal prediction function, accounting for the non-independent and non-identically distributed nature of trajectory data.
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…
Most previous contributions to BSDEs, and the related theories of nonlinear expectation and dynamic risk measures, have been in the framework of continuous time diffusions or jump diffusions. Using solutions of BSDEs on spaces related to finite state, continuous time Markov chains, we develop a theory of nonlinear expe…
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.
New algorithms learn Ising models from minimal observation of configuration changes.
problem Learning Ising models from the evolution of Markov chains with minimal observation.
method Developed algorithms that efficiently learn Ising models from minimal observation of configuration changes.
result First algorithms that efficiently learn Ising models in a more realistic observation model.
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. Novel CMG framework improves financial sentiment forecasting.
problem Challenges in short-term sentiment forecasting of financial OHLC data.
method Integrates chaos theory, Markov chains, and Gaussian processes with transformer models.
result Consistently outperforms traditional models in accuracy and efficiency.