Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains, and applications - Université de Lyon Access content directly
Preprints, Working Papers, ... Year : 2020

Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains, and applications

Abstract

We prove a new concentration inequality for U-statistics of order two for uniformly ergodic Markov chains. Working with bounded π-canonical kernels, we show that we can recover the convergence rate of Arcones and Gine (1993) who proved a concentration result for U-statistics of independent random variables and canonical kernels. Our proof relies on an inductive analysis where we use martingale techniques, uniform ergodicity, Nummelin splitting and Bernstein's type inequality where the spectral gap of the chain emerges. Our result allows us to conduct three applications. First, we establish a new exponential inequality for the estimation of spectra of trace class integral operators with MCMC methods. The novelty is that this result holds for kernels with positive and negative eigenvalues, which is new as far as we know. In addition, we investigate generalization performance of online algorithms working with pairwise loss functions and Markov chain samples. We provide an online-to-batch conversion result by showing how we can extract a low risk hypothesis from the sequence of hypotheses generated by any online learner. We finally give a non-asymptotic analysis of a goodness-of-fit test on the density of the invariant measure of a Markov chain. We identify the classes of alternatives over which our test based on the L2 distance has a prescribed power.
Fichier principal
Vignette du fichier
main.pdf (708.68 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-03014763 , version 1 (20-11-2020)
hal-03014763 , version 2 (17-02-2021)
hal-03014763 , version 3 (28-05-2021)
hal-03014763 , version 4 (16-03-2022)

Identifiers

Cite

Quentin Duchemin, Yohann de Castro, Claire Lacour. Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains, and applications. 2020. ⟨hal-03014763v1⟩
495 View
298 Download

Altmetric

Share

Gmail Facebook X LinkedIn More