On the $\alpha$-lazy version of Markov chains in estimation and testing problems

• URL: http://arxiv.org/abs/2105.09536v1
• Date: Thu, 20 May 2021 06:26:13 GMT
• Title: On the $\alpha$-lazy version of Markov chains in estimation and testing problems
• Authors: Sela Fried, Geoffrey Wolfer
• Abstract summary: 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.
• Score: 4.594159253008449
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We formulate extendibility of the minimax one-trajectory length of several statistical Markov chains inference problems and give sufficient conditions for both the possibility and impossibility of such extensions. We follow up and apply this framework to recently published results on learning and identity testing of ergodic Markov chains. 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, and quantify the incurred cost of removing this assumption.

Related papers

• Step-by-Step Reasoning for Math Problems via Twisted Sequential Monte Carlo [55.452453947359736]
  We introduce a novel verification method based on Twisted Sequential Monte Carlo (TSMC) We apply TSMC to Large Language Models by estimating the expected future rewards at partial solutions. This approach results in a more straightforward training target that eliminates the need for step-wise human annotations.
  arXiv  Detail & Related papers  (2024-10-02T18:17:54Z)
• Testing the Feasibility of Linear Programs with Bandit Feedback [53.40256244941895]
  We develop a test based on low-regret algorithms and a nonasymptotic law of iterated logarithms. We prove that this test is reliable, and adapts to the signal level,' $Gamma,$ of any instance. We complement this by a minimax lower bound $(Omegad/Gamma2)$ for sample costs of reliable tests.
  arXiv  Detail & Related papers  (2024-06-21T20:56:35Z)
• Language Model Cascades: Token-level uncertainty and beyond [65.38515344964647]
  Recent advances in language models (LMs) have led to significant improvements in quality on complex NLP tasks. Cascading offers a simple strategy to achieve more favorable cost-quality tradeoffs. We show that incorporating token-level uncertainty through learned post-hoc deferral rules can significantly outperform simple aggregation strategies.
  arXiv  Detail & Related papers  (2024-04-15T21:02:48Z)
• On Learning Latent Models with Multi-Instance Weak Supervision [57.18649648182171]
  We consider a weakly supervised learning scenario where the supervision signal is generated by a transition function $sigma$ labels associated with multiple input instances. Our problem is met in different fields, including latent structural learning and neuro-symbolic integration.
  arXiv  Detail & Related papers  (2023-06-23T22:05:08Z)
• A Robustness Analysis of Blind Source Separation [91.3755431537592]
  Blind source separation (BSS) aims to recover an unobserved signal from its mixture $X=f(S)$ under the condition that the transformation $f$ is invertible but unknown. We present a general framework for analysing such violations and quantifying their impact on the blind recovery of $S$ from $X$. We show that a generic BSS-solution in response to general deviations from its defining structural assumptions can be profitably analysed in the form of explicit continuity guarantees.
  arXiv  Detail & Related papers  (2023-03-17T16:30:51Z)
• A Geometric Reduction Approach for Identity Testing of Reversible Markov Chains [25.33133112984769]
  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.
  arXiv  Detail & Related papers  (2023-02-16T03:41:39Z)
• 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)
• Comparison of Markov chains via weak Poincar\'e inequalities with application to pseudo-marginal MCMC [0.0]
  We investigate the use of a certain class of functional inequalities known as weak Poincar'e inequalities to bound convergence of Markov chains to equilibrium. We show that this enables the derivation of subgeometric convergence bounds for methods such as the Independent Metropolis--Hastings sampler and pseudo-marginal methods for intractable likelihoods.
  arXiv  Detail & Related papers  (2021-12-10T15:36:30Z)
• Three rates of convergence or separation via U-statistics in a dependent framework [5.929956715430167]
  We put this theoretical breakthrough into action by pushing further the current state of knowledge in three different active fields of research. First, we establish a new exponential inequality for the estimation of spectra of trace class integral operators with MCMC methods. In addition, we investigate generalization performance of online algorithms working with pairwise loss functions and Markov chain samples.
  arXiv  Detail & Related papers  (2021-06-24T07:10:36Z)
• Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
  We investigate the active pure exploration problem in Markov Decision Processes. Agent sequentially selects actions and, from the resulting system trajectory, aims at the best as fast as possible.
  arXiv  Detail & Related papers  (2021-06-05T09:16:28Z)
• 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)

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.