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.
Introduces BWMD, a new distance measure for DNA and malware clustering.
problem Shortcomings of previous compression-based distance metrics.
method Embeds sequences into a fixed-length feature vector.
result Significantly improved clustering performance on larger malware corpora.
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.
Develops robust MDPs for unknown disturbances with performance guarantees.
problem Unknown disturbance distribution in MDPs.
method Empirical distribution, sublevel set of distance function, weak convergence, concentration inequality.
result Robust optimal value function converges to true optimal value function with increasing sample sizes.
In this paper, we present a simple non-parametric method for learning the structure of undirected graphs from data that drawn from an underlying unknown distribution. We propose to use Brownian distance covariance to estimate the conditional independences between the random variables and encodes pairwise Markov graph. …
New framework for efficient optimal transport distances between Markov chains.
problem Efficient computation of optimal transport distances between Markov chains.
method Developed a new perspective on optimal transport distances using discounted occupancy couplings and linear programming.
result Introduced Sinkhorn Value Iteration (SVI) for efficient calculation of optimal transport distances.
New algorithm samples from log-concave distributions with high accuracy in polynomial time.
problem Sampling from log-concave distributions with high accuracy in infinity distance.
method Directly converts continuous samples from K K K with total-variation bounds to samples with infinity bounds. result Output a point ε ε ε -close to π π π in infinity distance with runtime bounds that depend on polylogarithmic and polynomial factors of 1 / ε 1/ε 1/ ε . 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.
New measures assess differences in causal graphs' separations.
problem Evaluating causal discovery algorithms' output.
method Proposes new distance measures capturing causal graphs' separations.
result Proposed distances assess differences in causal graphs' separations.
Study evaluates initialization strategies for infinite hidden Markov models.
problem Limited attention to initialization in infinite hidden Markov models.
method Systematically evaluated distance-based clustering, model-based, and uniform initializations.
result Distance-based clustering initializations consistently outperform other methods.
The paper proposes methods to estimate MCMC quality with couplings, bounding Wasserstein distance.
problem Improving MCMC efficiency without sacrificing asymptotic consistency.
method Estimators based on couplings of Markov chains to assess quality of asymptotically biased sampling methods.
result Empirical upper bounds of Wasserstein distance for assessing MCMC quality.
Introduces MSW distances to improve SW metrics.
problem Redundant projections in SW distance.
method Imposes Markov structure on projecting directions.
result MSW distances improve SW metrics.
A new growth model for dynamic networks using Markovian latent points.
problem Modeling temporal dynamic networks with latent points and distances.
method Markovian latent space dynamic with Euclidean Sphere sampling and connection probabilities based on geodesic distances.
result Theoretical guarantees for non-parametric estimation of the latitude and envelope functions.
Study non-negative curvature Markov chains, proving entropy contraction.
problem Prove entropy contraction for Markov chains with non-negative curvature.
method Prove 1-step contraction in Wasserstein distance implies 1-step contraction in relative entropy.
result Prove MLSI with constant equal to minimal rate increment for mean-field zero-range process.
Proposes a Riemannian optimization for policy improvement in MDPs.
problem Optimizing policy functions in Markov decision processes (MDPs).
method Riemannian proximal optimization algorithm with Gaussian mixture model (GMM).
result Guaranteed convergence and efficacy demonstrated in preliminary experiments.
A new eigenvalue-based method speeds up Monte Carlo simulations.
problem Reducing the number of paths needed for accurate Monte Carlo simulations.
method Eigenvalue-based approximation of Markov Chain Monte Carlo.
result Significant variance reduction and comparable results to traditional Monte Carlo.
MC-MCL improves MCL for nonlinear clustering.
problem Nonlinear clustering in data science.
method MC-MCL combines MCL with Minimum Curvilinearity for nonlinear distances.
result MC-MCL outperforms classical MCL and baseline clustering algorithms in nonlinear datasets.
Paper studies CLT rates for dependent data in Wasserstein-p distance.
problem CLT rates for multivariate dependent data in Wasserstein-p distance.
method Analyzes locally dependent sequences and geometrically ergodic Markov chains.
result Establishes optimal W 1 W_1 W 1 CLT rates and W p W_p W p ( p ≥ 2 p\ge 2 p ≥ 2 ) rates for dependent data. This paper analyzes the bias of inexact MCMC methods in high dimensions.
problem Understanding the bias of inexact MCMC methods in high-dimensional spaces.
method Establishing bounds on Wasserstein distances between inexact MCMC methods and target distributions.
result The asymptotic bias of ULA and uHMC depends on key quantities related to the target distribution or the stationary probability measure of the scheme.
Bayesian inference typically requires the computation of an approximation to the posterior distribution. An important requirement for an approximate Bayesian inference algorithm is to output high-accuracy posterior mean and uncertainty estimates. Classical Monte Carlo methods, particularly Markov Chain Monte Carlo, rem…
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.
Paper introduces a new sampler for simulation-based inference using Gromov-Monge distance.
problem Simulation-based inference for multi-dimensional probability distributions.
method Proposes Reversible Gromov-Monge (RGM) distance and sampler for alignment and inference.
result RGM sampler can estimate optimal alignments and push measures between spaces.
Algorithm learns mixtures of Markov chains and MDPs from short trajectories.
problem Learning mixtures of Markov chains and MDPs from short unlabeled trajectories.
method Subspace estimation, spectral clustering, EM algorithm, model estimation, classification.
result 96.6% average accuracy on a mixture of two MDPs in gridworld, outperforming EM algorithm with random initialization.
Estimates bisimulation metrics from sample streams, not full transition models.
problem Estimating Markov chain metrics from limited sample data.
method Stochastic optimization using linear programming and primal-dual method.
result Validated through empirical evaluations, providing sample complexity guarantees.
Due to the popularity of the Internet and smart mobile devices, more and more financial transactions and activities have been digitalized. Compared to traditional financial fraud detection strategies using credit-related features, customers are generating a large amount of unstructured behavioral data every second. In …
SGD converges to an invariant distribution with sub-Gaussian or sub-exponential properties.
problem Optimizing smooth and strongly convex objectives using SGD.
method Analysis through Markov chains, focusing on convergence and concentration properties.
result SGD iterates and their invariant limit distribution inherit sub-Gaussian or sub-exponential concentration properties.
Markov chain decoders improve generative models' ability to produce heavy-tailed data.
problem Generative models struggle with heavy-tailed distributions.
method Replaced Gaussian decoder with Markov chain-based Phase-Type distributions.
result Significantly reduced tail Kolmogorov-Smirnov distance and extreme quantile error.
We propose a framework, named Aggregated Wasserstein, for computing a dissimilarity measure or distance between two Hidden Markov Models with state conditional distributions being Gaussian. For such HMMs, the marginal distribution at any time position follows a Gaussian mixture distribution, a fact exploited to softly …
In this paper a new dissimilarity measure to identify groups of assets dynamics is proposed. The underlying generating process is assumed to be a diffusion process solution of stochastic differential equations and observed at discrete time. The mesh of observations is not required to shrink to zero. As distance between…
Paper calculates KL divergence for isotropic Gaussian-Markov fields.
problem Measuring divergence between isotropic Gaussian-Markov fields.
method Derives closed-form KL divergence expressions.
result Develops new similarity measures in image processing.
New algorithm reduces privacy breach in posterior sampling.
problem Combining pure DP with MCMC for efficient sampling.
method ASAP algorithm that perturbs MCMC samples with Wasserstein-infinity noise.
result First nearly linear-time algorithm achieving optimal DP-ERM rates.
Generative models using PDMPs with explicit jump rates and kernels.
problem Creating efficient generative models for complex data distributions.
method Piecewise deterministic Markov processes (PDMPs) with explicit expressions for jump rates and kernels.
result Efficient training and simulation methods for PDMP-based generative models.
Adaptive KL-UCB algorithm for Markov and i.i.d. rewards.
problem Regret minimization for Markovian and i.i.d. rewards in MAB problems.
method Identifies Markovian vs. i.i.d. rewards, switches between KL-UCB variants.
result Logarithmic regret for both i.i.d. and Markovian settings.
Graph curvature measured by inverse resistance distance.
problem Defining and analyzing curvature in graphs.
method Defining curvature via inverse resistance distance and proving properties.
result Graphs with positive curvature have controlled diameter and spectral properties.
Causal inference relies on the structure of a graph, often a directed acyclic graph (DAG). Different graphs may result in different causal inference statements and different intervention distributions. To quantify such differences, we propose a (pre-) distance between DAGs, the structural intervention distance (SID). T…
This paper analyzes speculative decoding, a method to speed up large language model inferences.
problem Theoretical understanding of speculative decoding is lacking.
method Conceptualizes speculative decoding as a markov chain problem and studies its key properties.
result Reveals fundamental connections between LLM components and their impact on decoding efficiency.
We exhibit an efficient procedure for testing, based on a single long state sequence, whether an unknown Markov chain is identical to or ε \varepsilon ε -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…
HMC improves Gaussian sampling efficiency with long, random steps.
problem Efficiently sampling from high-dimensional Gaussian distributions.
method Hamiltonian Monte Carlo with long and random integration times.
result HMC achieves ε \varepsilon ε -closeness in total variation distance with O ~ ( κ d 1 / 4 log ( 1 / ε ) ) \widetilde{O}(\sqrt{\kappa} d^{1/4} \log(1/\varepsilon)) O ( κ d 1/4 log ( 1/ ε )) gradient queries. New method uses Cantor embeddings and Wasserstein distances to analyze predictive states in time series data.
problem Analyzing predictive states in stochastic processes using time series data.
method Wasserstein distances for detecting predictive equivalences in symbolic data, using Cantor embeddings for finite-dimensional representation.
result Exploratory analysis of temporal structure in various processes reveals insights.
Hidden Markov Model helps track asymptomatic carriers in pandemic.
problem Tracking spread of asymptomatic carriers (super-spreaders) during pandemic.
method Applied Hidden Markov Model to analyze COVID-19 data.
result Better assessment of spread extent for calibrated interventions.
Paper analyzes Scaffold algorithm for federated learning, proving linear speed-up with stochastic gradients.
problem Understanding the impact of stochastic gradients on the Scaffold algorithm's performance.
method Proved linear speed-up in the number of clients using a Markov chain analysis of global parameters and control variates.
result Scaffold achieves linear speed-up in the number of clients up to higher-order terms in the step size, but retains a higher-order bias.
Latent feature models are widely used to decompose data into a small number of components. Bayesian nonparametric variants of these models, which use the Indian buffet process (IBP) as a prior over latent features, allow the number of features to be determined from the data. We present a generalization of the IBP, the …
The study proves inequalities and curvature properties for Markov chains.
problem Isoperimetric and concentration inequalities for Markov chains.
method Laplacian separation principle for eikonal equation; modified log-Sobolev constant; Ollivier curvature.
result Affirmative answers to open questions and new inequalities.
New analysis for learning and applying preconditioners in MCMC improves efficiency.
problem Improving efficiency of MCMC algorithms by modifying them with preconditioners.
method Analyzes and compares computational costs of MCMC schemes with and without preconditioners.
result Establishes non-asymptotic guarantees for MCMC algorithms that learn and use preconditioners.
Great computational effort is invested in generating equilibrium states for molecular systems using, for example, Markov chain Monte Carlo. We present a probabilistic model that generates statistically independent samples for molecules from their graph representations. Our model learns a low-dimensional manifold that p…
Novel bounds improve TD learning consistency in RL.
problem Analyzing Temporal Difference learning's performance.
method High-dimensional concentration inequalities and Berry-Esseen bounds for Markov chain induced martingales.
result Sharp high-probability consistency guarantee for TD learning, matching asymptotic variance up to logarithmic factors.
Discrete diffusion models improve data generation for discrete data like language and graphs.
problem Adapting diffusion models to discrete state spaces for better data generation.
method Formulated as CTMCs, used uniformization of continuous Markov chains for sampling.
result Derive guarantees for sampling from any distribution on a hypercube, aligning with state-of-the-art achievements.
Paper proposes a distributed sampling method for Bayesian inference.
problem Privacy and communication constraints in spatially distributed datasets.
method Alternating Direction Method of Multipliers for distributed sampling.
result Algorithm converges to target distribution in Wasserstein distance.