An official website of the United States government
Abstract We study optimal transport for stationary stochastic processes taking values in finite spaces. In order to reflect the stationarity of the underlying processes, we restrict attention to stationary couplings, also known as joinings. The resulting optimal joining problem captures differences in the long-run average behavior of the processes of interest. We introduce estimators of both optimal joinings and the optimal joining cost, and establish consistency of the estimators under mild conditions. Furthermore, under stronger mixing assumptions we establish finite-sample error rates for the estimated optimal joining cost that extend the best known results in the iid case. We also extend the consistency and rate analysis to an entropy-penalized version of the optimal joining problem. Finally, we validate our convergence results empirically as well as demonstrate the computational advantage of the entropic problem in a simulation experiment.
more »
« less
Bicausal Optimal Transport for Markov Chains via Dynamic Programming
n this paper we study the bicausal optimal transport problem for Markov chains, an optimal transport formulation suitable for stochastic processes which takes into consideration the accumulation of information as time evolves. Our analysis is based on a relation between the transport problem and the theory of Markov decision processes. This way we are able to derive necessary and sufficient conditions for optimality in the transport problem, as well as an iterative algorithm, namely the value iteration, for the calculation of the transportation cost. Additionally, we draw the connection with the classic theory on couplings for Markov chains, and in particular with the notion of faithful couplings.
more »
« less
- Award ID(s):
- 1816861
- PAR ID:
- 10379277
- Date Published:
- Journal Name:
- 2021 IEEE International Symposium on Information Theory (ISIT)
- Page Range / eLocation ID:
- 1688 to 1693
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Suppose an online platform wants to compare a treatment and control policy (e.g., two different matching algorithms in a ridesharing system, or two different inventory management algorithms in an online retail site). Standard experimental approaches to this problem are biased (due to temporal interference between the policies), and not sample efficient. We study optimal experimental design for this setting. We view testing the two policies as the problem of estimating the steady state difference in reward between two unknown Markov chains (i.e., policies). We assume estimation of the steady state reward for each chain proceeds via nonparametric maximum likelihood, and search for consistent (i.e., asymptotically unbiased) experimental designs that are efficient (i.e., asymptotically minimum variance). Characterizing such designs is equivalent to a Markov decision problem with a minimum variance objective; such problems generally do not admit tractable solutions. Remarkably, in our setting, using a novel application of classical martingale analysis of Markov chains via Poisson's equation, we characterize efficient designs via a succinct convex optimization problem. We use this characterization to propose a consistent, efficient online experimental design that adaptively samples the two Markov chains.more » « less
-
null (Ed.)Path integral quantum Monte Carlo (PIMC) is a method for estimating thermal equilibrium properties of stoquastic quantum spin systems by sampling from a classical Gibbs distribution using Markov chain Monte Carlo. The PIMC method has been widely used to study the physics of materials and for simulated quantum annealing, but these successful applications are rarely accompanied by formal proofs that the Markov chains underlying PIMC rapidly converge to the desired equilibrium distribution.In this work we analyze the mixing time of PIMC for 1D stoquastic Hamiltonians, including disordered transverse Ising models (TIM) with long-range algebraically decaying interactions as well as disordered XY spin chains with nearest-neighbor interactions. By bounding the convergence time to the equilibrium distribution we rigorously justify the use of PIMC to approximate partition functions and expectations of observables for these models at inverse temperatures that scale at most logarithmically with the number of qubits.The mixing time analysis is based on the canonical paths method applied to the single-site Metropolis Markov chain for the Gibbs distribution of 2D classical spin models with couplings related to the interactions in the quantum Hamiltonian. Since the system has strongly nonisotropic couplings that grow with system size, it does not fall into the known cases where 2D classical spin models are known to mix rapidly.more » « less
-
For two measures that are in convex-decreasing order, Nutz and Stebegg (Canonical supermartingale couplings, Ann. Probab. 46(6) 3351–3398, 2018) studied the optimal transport problem with supermartingale constraints and introduced two canonical couplings, namely the increasing and decreasing transport plans, that are optimal for a large class of cost functions. In the present paper we provide an explicit construction of the decreasing coupling by establishing a Brenier-type result: (a generalised version of) this coupling concentrates on the graphs of two functions. Our construction is based on the concept of the supermartingale shadow measure and requires a suitable extension of the results by Juillet (Stability of the shadow projection and the left-curtain coupling, Ann. Inst. H. Poincaré Probab. Statist. 52(4) 1823–1843, November 2016) and Beiglböck and Juillet (Shadow couplings, Trans. Amer. Math. Soc. 374 4973–5002, 2021) established in the martingale setting. In particular, we prove the stability of the supermartingale shadow measure with respect to initial and target measures introduce an infinite family of lifted supermartingale couplings that arise via shadow measure, and show how to explicitly determine the martingale points of each such coupling.more » « less
-
Abstract Let G be a finite group. Let $H, K$ be subgroups of G and $$H \backslash G / K$$ the double coset space. If Q is a probability on G which is constant on conjugacy classes ( $$Q(s^{-1} t s) = Q(t)$$ ), then the random walk driven by Q on G projects to a Markov chain on $$H \backslash G /K$$ . This allows analysis of the lumped chain using the representation theory of G . Examples include coagulation-fragmentation processes and natural Markov chains on contingency tables. Our main example projects the random transvections walk on $$GL_n(q)$$ onto a Markov chain on $$S_n$$ via the Bruhat decomposition. The chain on $$S_n$$ has a Mallows stationary distribution and interesting mixing time behavior. The projection illuminates the combinatorics of Gaussian elimination. Along the way, we give a representation of the sum of transvections in the Hecke algebra of double cosets, which describes the Markov chain as a mixture of Metropolis chains. Some extensions and examples of double coset Markov chains with G a compact group are discussed.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Conference Paper:
- https://doi.org/10.1109/ISIT45174.2021.9517977
