Rademacher complexity for Markov chains: applications to kernel smoothing and Metropolis-Hastings

DOI10.3150/19-BEJ1115zbMATH Open1431.60080arXiv1806.02107OpenAlexW2976436354MaRDI QIDQ2325397FDOQ2325397

Authors: Patrice Bertail, François Portier 

Publication date: 25 September 2019

Published in: Bernoulli (Search for Journal in Brave)

Abstract: Following the seminal approach by Talagrand, the concept of Rademacher complexity for independent sequences of random variables is extended to Markov chains. The proposed notion of "block Rademacher complexity" (of a class of functions) follows from renewal theory and allows to control the expected values of suprema (over the class of functions) of empirical processes based on Harris Markov chains as well as the excess probability. For classes of Vapnik-Chervonenkis type, bounds on the "block Rademacher complexity" are established. These bounds depend essentially on the sample size and the probability tails of the regeneration times. The proposed approach is employed to obtain convergence rates for the kernel density estimator of the stationary measure and to derive concentration inequalities for the Metropolis-Hasting algorithm.

Full work available at URL: https://arxiv.org/abs/1806.02107

Recommendations

• Local Rademacher complexities
• Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms
• On the convergence of the Metropolis-Hastings Markov chains
• Necessary conditions for geometric and polynomial ergodicity of random-walk-type Markov chains
• Complexity bounds for Markov chain Monte Carlo algorithms via diffusion limits

zbMATH Keywords

kernel smoothingMarkov chainsconcentration inequalitiesRademacher complexityMetropolis Hastings

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Density estimation (62G07)

Cites Work

• Weak convergence and empirical processes. With applications to statistics
• Asymptotic Statistics
• Rates of strong uniform consistency for multivariate kernel density estimators. (Vitesse de convergence uniforme presque sûre pour des estimateurs à noyaux de densités multivariées)
• Stability bounds for stationary \(\varphi \)-mixing and \(\beta \)-mixing processes
• Markov Chains and Stochastic Stability
• Title not available (Why is that?)
• An adaptive Metropolis algorithm
• Uniform in bandwidth consistency of kernel-type function estimators
• Empirical Processes with Applications to Statistics
• Mathematical foundations of infinite-dimensional statistical models
• UNIFORM CONVERGENCE RATES FOR KERNEL ESTIMATION WITH DEPENDENT DATA
• Concentration inequalities. A nonasymptotic theory of independence
• Empirical processes indexed by estimated functions
• U-processes: Rates of convergence
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• On the central limit theorem for stationary mixing random fields
• Geometric ergodicity of Metropolis algorithms
• Geometric convergence and central limit theorems for multidimensional Hastings and Metropolis algorithms
• Title not available (Why is that?)
• Oracle inequalities in empirical risk minimization and sparse recovery problems. École d'Été de Probabilités de Saint-Flour XXXVIII-2008.
• General state space Markov chains and MCMC algorithms
• Basic properties of strong mixing conditions. A survey and some open questions
• Sharper bounds for Gaussian and empirical processes
• Rates of convergence of the Hastings and Metropolis algorithms
• Local Rademacher complexities and oracle inequalities in risk minimization. (2004 IMS Medallion Lecture). (With discussions and rejoinder)
• Local Rademacher complexities
• Non-parametric estimation of the residual distribution
• General Irreducible Markov Chains and Non-Negative Operators
• Title not available (Why is that?)
• Regenerative stochastic processes
• 10.1162/153244303321897690
• Title not available (Why is that?)
• An empirical process approach to the uniform consistency of kernel-type function estimators
• On consistency of kernel density estimators for randomly censored data: Rates holding uniformly over adaptive intervals
• Uniform central limit theorems for kernel density estimators
• A tail inequality for suprema of unbounded empirical processes with applications to Markov chains
• Limit theorems for functionals of ergodic Markov chains with general state space
• Advanced Lectures on Machine Learning
• Properties of uniform consistency of the kernel estimators of density and regression functions under dependence assumptions
• Uniform limit theorems for Harris recurrent Markov chains
• Nonasymptotic bounds on the estimation error of MCMC algorithms
• A splitting technique for Harris recurrent Markov chains
• Contributions to Doeblin's theory of Markov processes
• Curvature, concentration and error estimates for Markov chain Monte Carlo
• Regenerative block-bootstrap for Markov chains
• Nonparametric Bayesian posterior contraction rates for discretely observed scalar diffusions
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Probability density estimation using delta sequences
• Sharp bounds for the tails of functionals of Markov chains
• A law of the logarithm for kernel density estimators
• A New Approach to the Limit Theory of Recurrent Markov Chains
• Quantitative bounds on convergence of time-inhomogeneous Markov chains
• Title not available (Why is that?)
• Bounds on regeneration times and limit theorems for subgeometric Markov chains
• A regeneration proof of the central limit theorem for uniformly ergodic Markov chains
• On the weak convergence of the empirical conditional copula under a simplifying assumption
• Edgeworth expansions of suitably normalized sample mean statistics for atomic Markov chains
• The Berry-Esseen theorem for functionals of discrete Markov chains
• Subgaussian concentration inequalities for geometrically ergodic Markov chains
• Title not available (Why is that?)
• Limit Theorems for Harris Markov Chains, II
• Exponential inequalities for unbounded functions of geometrically ergodic Markov chains: applications to quantitative error bounds for regenerative Metropolis algorithms
• Integral estimation based on Markovian design
• On martingale extensions of Vapnik-Chervonenkis theory with applications to online learning
• On the asymptotics of \(Z\)-estimators indexed by the objective functions

Cited In (5)

• High dimensional regression for regenerative time-series: an application to road traffic modeling
• Exponential inequalities for nonstationary Markov chains
• Safe adaptive importance sampling: a mixture approach
• Rademacher Chaos Complexities for Learning the Kernel Problem
• A maximum likelihood and regenerative bootstrap approach for estimation and forecasting of INAR( p ) processes with zero-inflated innovations

This page was built for publication: Rademacher complexity for Markov chains: applications to kernel smoothing and Metropolis-Hastings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2325397)