Extension of the PAC framework to finite and countable Markov chains

DOI10.1109/TIT.2002.806131MaRDI QIDQ4679911zbMATH OpenFDO

Authors David Gamarnik

Publication date 31 May 2005

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/TIT.2002.806131

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Computational learning theory (68Q32) Learning and adaptive systems in artificial intelligence (68T05)

Recommendations

• A Markovian extension of Valiant's learning model
• Results on learnability and the Vapnik-Chervonenkis dimension
• Learning probabilistic automata and Markov chains via queries
• Learning from uniformly ergodic Markov chains
• Global PAC bounds for learning discrete time Markov chains

Cited in

(11)

• A Markovian extension of Valiant's learning model
• On biased random walks, corrupted intervals, and learning under adversarial design
• Global PAC bounds for learning discrete time Markov chains
• Mixing time estimation in reversible Markov chains from a single sample path
• Learning from non-irreducible Markov chains
• ONLINE LEARNING WITH MARKOV SAMPLING
• Generalization bounds of ERM algorithm with Markov chain samples
• Robustness and generalization
• Generalization bounds of ERM algorithm with \(V\)-geometrically ergodic Markov chains
• Generalization performance of least-square regularized regression algorithm with Markov chain samples
• Rademacher learning rates for iterated random functions

This page was built for publication: Extension of the PAC framework to finite and countable Markov chains

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