Rosenthal-type inequalities for linear statistics of Markov chains

• URL: http://arxiv.org/abs/2303.05838v2
• Date: Wed, 28 Jun 2023 08:56:53 GMT
• Title: Rosenthal-type inequalities for linear statistics of Markov chains
• Authors: Alain Durmus, Eric Moulines, Alexey Naumov, Sergey Samsonov, Marina Sheshukova
• Abstract summary: We establish novel deviation bounds for additive functionals of geometrically ergodic Markov chains. We pay special attention to the dependence of our bounds on the mixing time of the corresponding chain.
• Score: 20.606986885851573
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we establish novel deviation bounds for additive functionals of geometrically ergodic Markov chains similar to Rosenthal and Bernstein inequalities for sums of independent random variables. We pay special attention to the dependence of our bounds on the mixing time of the corresponding chain. More precisely, we establish explicit bounds that are linked to the constants from the martingale version of the Rosenthal inequality, as well as the constants that characterize the mixing properties of the underlying Markov kernel. Finally, our proof technique is, up to our knowledge, new and based on a recurrent application of the Poisson decomposition.

Related papers

• Ito Diffusion Approximation of Universal Ito Chains for Sampling, Optimization and Boosting [64.0722630873758]
  We consider rather general and broad class of Markov chains, Ito chains, that look like Euler-Maryama discretization of some Differential Equation. We prove the bound in $W_2$-distance between the laws of our Ito chain and differential equation.
  arXiv  Detail & Related papers  (2023-10-09T18:38:56Z)
• Covariate shift in nonparametric regression with Markovian design [0.0]
  We show that convergence rates for a smoothness risk of a Nadaraya-Watson kernel estimator are determined by the similarity between the invariant distributions associated to source and target Markov chains. We extend the notion of a distribution exponent from Kpotufe and Martinet to kernel transfer exponents of uniformly ergodic Markov chains.
  arXiv  Detail & Related papers  (2023-07-17T14:24:27Z)
• Spectrum of localized states in fermionic chains with defect and adiabatic charge pumping [68.8204255655161]
  We study the localized states of a generic quadratic fermionic chain with finite-range couplings. We analyze the robustness of the connection between bands against perturbations of the Hamiltonian.
  arXiv  Detail & Related papers  (2021-07-20T18:44:06Z)
• R\'enyi divergence inequalities via interpolation, with applications to generalised entropic uncertainty relations [91.3755431537592]
  We investigate quantum R'enyi entropic quantities, specifically those derived from'sandwiched' divergence. We present R'enyi mutual information decomposition rules, a new approach to the R'enyi conditional entropy tripartite chain rules and a more general bipartite comparison.
  arXiv  Detail & Related papers  (2021-06-19T04:06:23Z)
• Deviation inequalities for stochastic approximation by averaging [0.5586191108738562]
  We introduce a class of Markov chains, that contains the model of approximation by averaging and non-averaging. We establish various deviation inequalities for separately Lipschitz functions of such a chain, with different moment conditions on some dominating random variables of martingale differences.
  arXiv  Detail & Related papers  (2021-02-17T10:57:37Z)
• Some Hoeffding- and Bernstein-type Concentration Inequalities [47.24550702683417]
  We prove concentration inequalities for functions of independent random variables under sub-gaussian and sub-exponential conditions. The utility of the inequalities is demonstrated by an extension of the now classical method of Rademacher complexities to Lipschitz function classes and unbounded sub-exponential distribution.
  arXiv  Detail & Related papers  (2021-02-11T23:09:13Z)
• The Connection between Discrete- and Continuous-Time Descriptions of Gaussian Continuous Processes [60.35125735474386]
  We show that discretizations yielding consistent estimators have the property of invariance under coarse-graining' This result explains why combining differencing schemes for derivatives reconstruction and local-in-time inference approaches does not work for time series analysis of second or higher order differential equations.
  arXiv  Detail & Related papers  (2021-01-16T17:11:02Z)
• Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains [0.0]
  We prove a concentration inequality for U-statistics of order two for uniformly ergodic Markov chains. We show that we can recover the convergence rate of Arcones and Gin'e who proved a concentration result for U-statistics of independent random variables and canonical kernels.
  arXiv  Detail & Related papers  (2020-11-20T15:14:34Z)
• 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)
• Convergence of Recursive Stochastic Algorithms using Wasserstein Divergence [4.688616907736838]
  We show that convergence of a large family of constant stepsize RSAs can be understood using this framework. We show that convergence of a large family of constant stepsize RSAs can be understood using this framework.
  arXiv  Detail & Related papers  (2020-03-25T13:45:16Z)
• Empirical and Instance-Dependent Estimation of Markov Chain and Mixing Time [5.167069404528051]
  We address the problem of estimating the mixing time of a Markov chain from a single trajectory of observations. Unlike most previous works which employed Hilbert space methods to estimate spectral gaps, we opt for an approach based on contraction with respect to total variation. This quantity, unlike the spectral gap, controls the mixing time up to strong universal constants and remains applicable to non-reversible chains.
  arXiv  Detail & Related papers  (2019-12-14T13:38: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.