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