A Geometric Reduction Approach for Identity Testing of Reversible Markov Chains

• URL: http://arxiv.org/abs/2302.08059v1
• Date: Thu, 16 Feb 2023 03:41:39 GMT
• Title: A Geometric Reduction Approach for Identity Testing of Reversible Markov Chains
• Authors: Geoffrey Wolfer and Shun Watanabe
• Abstract summary: We consider the problem of testing the identity of a reversible Markov chain against a reference from a single trajectory of observations. We show that, at least in a mildly restricted setting, testing identity to a reversible chain reduces to testing to a symmetric chain over a larger state space.
• Score: 25.33133112984769
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of testing the identity of a reversible Markov chain against a reference from a single trajectory of observations. Employing the recently introduced notion of a lumping-congruent Markov embedding, we show that, at least in a mildly restricted setting, testing identity to a reversible chain reduces to testing to a symmetric chain over a larger state space and recover state-of-the-art sample complexity for the problem.

Related papers

• A Unified Theory of Stochastic Proximal Point Methods without Smoothness [52.30944052987393]
  Proximal point methods have attracted considerable interest owing to their numerical stability and robustness against imperfect tuning. This paper presents a comprehensive analysis of a broad range of variations of the proximal point method (SPPM)
  arXiv  Detail & Related papers  (2024-05-24T21:09:19Z)
• Stochastic Gradient Descent under Markovian Sampling Schemes [3.04585143845864]
  We study a variation of vanilla gradient descent where the only has access to a Markovian sampling scheme. We focus on obtaining rates of convergence under the least restrictive assumptions possible on the underlying Markov chain.
  arXiv  Detail & Related papers  (2023-02-28T09:18:00Z)
• Reversibility of elliptical slice sampling revisited [1.0923877073891446]
  We extend elliptical slice sampling to infinite-dimensional separable Hilbert spaces and discuss its well-definedness. Crucial within the proof of the formerly mentioned results is the analysis of a shrinkage Markov chain that may be interesting on its own.
  arXiv  Detail & Related papers  (2023-01-06T09:14:16Z)
• Vector-Valued Least-Squares Regression under Output Regularity Assumptions [73.99064151691597]
  We propose and analyse a reduced-rank method for solving least-squares regression problems with infinite dimensional output. We derive learning bounds for our method, and study under which setting statistical performance is improved in comparison to full-rank method.
  arXiv  Detail & Related papers  (2022-11-16T15:07:00Z)
• Offline Estimation of Controlled Markov Chains: Minimaxity and Sample Complexity [8.732260277121547]
  We develop sample complexity bounds for the estimator and establish conditions for minimaxity. We show that achieving a particular statistical risk bound involves a subtle and interesting trade-off between the strength of the mixing properties and the number of samples.
  arXiv  Detail & Related papers  (2022-11-14T03:39:59Z)
• Optimal variance-reduced stochastic approximation in Banach spaces [114.8734960258221]
  We study the problem of estimating the fixed point of a contractive operator defined on a separable Banach space. We establish non-asymptotic bounds for both the operator defect and the estimation error.
  arXiv  Detail & Related papers  (2022-01-21T02:46:57Z)
• On the $\alpha$-lazy version of Markov chains in estimation and testing problems [4.594159253008449]
  We show that for some results, we can omit the aperiodicity requirement by simulating an $alpha$-lazy version of the original process. In particular, we show that for some of the aforementioned results, we can omit the aperiodicity requirement by simulating an $alpha$-lazy version of the original process.
  arXiv  Detail & Related papers  (2021-05-20T06:26:13Z)
• Identity testing of reversible Markov chains [4.594159253008449]
  We consider the problem of identity testing of Markov chains based on a single trajectory of observations. We relax the symmetry assumption to the more natural assumption of reversibility, still assuming that both the reference and the unknown Markov chains share the same stationary distribution.
  arXiv  Detail & Related papers  (2021-05-13T15:03:27Z)
• MCMC-Interactive Variational Inference [56.58416764959414]
  We propose MCMC-interactive variational inference (MIVI) to estimate the posterior in a time constrained manner. MIVI takes advantage of the complementary properties of variational inference and MCMC to encourage mutual improvement. Experiments show that MIVI not only accurately approximates the posteriors but also facilitates designs of gradient MCMC and Gibbs sampling transitions.
  arXiv  Detail & Related papers  (2020-10-02T17:43:20Z)
• Non-equilibrium non-Markovian steady-states in open quantum many-body systems: Persistent oscillations in Heisenberg quantum spin chains [68.8204255655161]
  We investigate the effect of a non-Markovian, structured reservoir on an open Heisenberg spin chain. We establish a coherent self-feedback mechanism as the reservoir couples frequency-dependent to the spin chain.
  arXiv  Detail & Related papers  (2020-06-05T09:16:28Z)
• The Simulator: Understanding Adaptive Sampling in the Moderate-Confidence Regime [52.38455827779212]
  We propose a novel technique for analyzing adaptive sampling called the em Simulator. We prove the first instance-based lower bounds the top-k problem which incorporate the appropriate log-factors. Our new analysis inspires a simple and near-optimal for the best-arm and top-k identification, the first em practical of its kind for the latter problem.
  arXiv  Detail & Related papers  (2017-02-16T23:42:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.