# Three rates of convergence or separation via U-statistics in a dependent framework

arXiv: https://arxiv.org/abs/2106.12796 · HTML: https://mlsanity.com/paper/2106.12796/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 74 references that are in the map.
- First posted on arXiv 24 Jun 2021.

## Builds on (most cited first, 11 of 11)

- [A Kernelized Stein Discrepancy for Goodness-of-fit Tests and Model Evaluation](https://mlsanity.com/paper/1602.03253/) (2016)
- [Online Learning: A Comprehensive Survey](https://mlsanity.com/paper/1802.02871/) (2018)
- [A Kernel Test of Goodness of Fit](https://mlsanity.com/paper/1602.02964/) (2016)
- [Measuring Sample Quality with Kernels](https://mlsanity.com/paper/1703.01717/) (2017)
- [On the Generalization Ability of Online Learning Algorithms for Pairwise Loss Functions](https://mlsanity.com/paper/1305.2505/) (2013)
- [Unregularized Online Learning Algorithms with General Loss Functions](https://mlsanity.com/paper/1503.00623/) (2015)
- [A maximum-mean-discrepancy goodness-of-fit test for censored data](https://mlsanity.com/paper/1810.04286/) (2018)
- [Online Learning with Pairwise Loss Functions](https://mlsanity.com/paper/1301.5332/) (2013)
- [Consistent estimation of the spectrum of trace class data augmentation algorithms](https://mlsanity.com/paper/1711.00572/) (2017)
- [Markov Random Geometric Graph (MRGG): A Growth Model for Temporal Dynamic Networks](https://mlsanity.com/paper/2006.07001/) (2020)
- [Concentration inequality for U-statistics of order two for uniformly ergodic Markov chains](https://mlsanity.com/paper/2011.11435/) (2020)

## Abstract (arXiv)

Despite the ubiquity of U-statistics in modern Probability and Statistics, their non-asymptotic analysis in a dependent framework may have been overlooked. In a recent work, a new concentration inequality for U-statistics of order two for uniformly ergodic Markov chains has been proved. In this paper, 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. 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 some classes of alternatives over which our test based on the L2 distance has a prescribed power.