Article

Free access

Extension of the PAC framework to finite and countable Markov chains

Author:

David GamarnikAuthors Info & Claims

COLT '99: Proceedings of the twelfth annual conference on Computational learning theory

Pages 308 - 317

https://doi.org/10.1145/307400.307478

Published: 06 July 1999 Publication History

PDF eReader

References

[1]

D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. In preparation.

Google Scholar

[2]

D. Aidous and U. ~3.zirani. A Markovian extension of Valiant's learning model. Proc. 31st Symposium on 1990.

Google Scholar

[3]

M_ Anthony and N_ Biggs Comnutational Learninp Theory. Cambridge University Press, 1992.

Digital Library

Google Scholar

[4]

P. Bartlett, P. Fischer, and K. Hoffgen. Exploiting random walks for learning. Proc. 7th ACM Conf. on Computational Learning Theory, 1994.

Digital Library

Google Scholar

[5]

D. Bertsimas, D. Gamarnik, and J. Tsitsiklis. Geometric bounds for stationary distribution of infinite Markov Chains via Lyapunov functions. Preprint, i 998.

Google Scholar

[6]

K.L. Buescher and P.R. Kumar. Learning by canoni- 1EEE Transactions on Automatic Control, 41:545-556, 1996.

Google Scholar

[7]

K.L. Buescher and P.R. Kumar. Learning by canonical smooth estimation, part II: Learning and model complexity. IEEE Transactions on Automatic Control, 41:557-569, 1996.

Crossref

Google Scholar

[8]

P. Diaconis, R. Graham, and J. Morrison. Asymptotic analysis of a random walk on a hypercube with many dimensions. Random Structures and Aigorithms, 1:51- 72, 1990.

Crossref

Google Scholar

[9]

D.Gillman. A Chernoff hbound for random walks on expander graphs. SIAM J. Compur, 27(4): 1203-1219, 1998.

Digital Library

Google Scholar

[10]

M. Kearns and U. Vazirani. An Introduction to ComputationalLearning Theory. MIT Press, 1994.

Digital Library

Google Scholar

[11]

R. Meir. Performance bounds for nonlinear time series prediction. Proc. lOth ACM Conf. on Computational Learning Theory, pages 122-130, 1997.

Digital Library

Google Scholar

[12]

S.P. Meyn. Computable bounds for geometric convergence rates of markov chains. Ann. ofAppl." ' ' rrou., ~, 1994.

Google Scholar

[13]

S.P. Meyn and R.L. Tweedie. MArkov Chains and Stochastie Stability. Springer-~erlag, 1993.

Google Scholar

[14]

A. Nobel. A counterexample concerning uniform ergodic theorems for a class of functions. Statistics and Probability Letters, 24:165-168, 1995.

Crossref

Google Scholar

[15]

V. Vapnik. The Nature of Statistical Learning Theory. Springer, 1995.

Digital Library

Google Scholar

Cited By

View all

Elbaz ALee HServedio RWan A(2007)Separating Models of Learning from Correlated and Uncorrelated DataThe Journal of Machine Learning Research10.5555/1248659.12486698(277-290)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.5555/1248659.1248669
Roch S(2007)On learning thresholds of parities and unions of rectangles in random walk modelsRandom Structures & Algorithms10.1002/rsa.2016231:4(406-417)Online publication date: 31-Jan-2007
https://doi.org/10.1002/rsa.20162
Bshouty NMossel EO'Donnell RServedio R(2005)Learning DNF from random walksJournal of Computer and System Sciences10.1016/j.jcss.2004.10.01071:3(250-265)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1016/j.jcss.2004.10.010
Show More Cited By

Index Terms

Extension of the PAC framework to finite and countable Markov chains
1. Mathematics of computing
  1. Probability and statistics
2. Theory of computation
  1. Logic
  2. Models of computation

Recommendations

Extension of the PAC framework to finite and countable Markov chains

We consider a model of learning in which the successive observations follow a certain Markov chain. The observations are labeled according to a membership to some unknown target set. For a Markov chain with finitely many states we show that, if the ...
Upper Bounds on Mixing Time of Finite Markov Chains

We provide a general framework for computing mixing times of finite Markov chains whose semigroup's minimal ideal is left zero. Our analysis is based on combining results by Brown and Diaconis with our previous work on stationary distributions of finite ...
An EM algorithm for continuous-time bivariate Markov chains

We study properties and parameter estimation of a finite-state, homogeneous, continuous-time, bivariate Markov chain. Only one of the two processes of the bivariate Markov chain is assumed observable. The general form of the bivariate Markov chain ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

COLT '99: Proceedings of the twelfth annual conference on Computational learning theory

July 1999

333 pages

ISBN:1581131674

DOI:10.1145/307400

Chairmen:
Shai Ben-David,
Phil Long

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 1999

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

COLT99

Sponsor:

SIGAI
Univ. of California,
SIGACT

COLT99: The 12th Annual Conference on Computation Learning Theory

July 7 - 9, 1999

California, Santa Cruz, USA

Acceptance Rates

COLT '99 Paper Acceptance Rate 35 of 71 submissions, 49%;

Overall Acceptance Rate 35 of 71 submissions, 49%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
386
Total Downloads

Downloads (Last 12 months)47
Downloads (Last 6 weeks)1

Reflects downloads up to 25 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Elbaz ALee HServedio RWan A(2007)Separating Models of Learning from Correlated and Uncorrelated DataThe Journal of Machine Learning Research10.5555/1248659.12486698(277-290)Online publication date: 1-May-2007
https://dl.acm.org/doi/10.5555/1248659.1248669
Roch S(2007)On learning thresholds of parities and unions of rectangles in random walk modelsRandom Structures & Algorithms10.1002/rsa.2016231:4(406-417)Online publication date: 31-Jan-2007
https://doi.org/10.1002/rsa.20162
Bshouty NMossel EO'Donnell RServedio R(2005)Learning DNF from random walksJournal of Computer and System Sciences10.1016/j.jcss.2004.10.01071:3(250-265)Online publication date: 1-Oct-2005
https://dl.acm.org/doi/10.1016/j.jcss.2004.10.010
Elbaz ALee HServedio RWan A(2005)Separating models of learning from correlated and uncorrelated dataProceedings of the 18th annual conference on Learning Theory10.1007/11503415_43(637-651)Online publication date: 27-Jun-2005
https://dl.acm.org/doi/10.1007/11503415_43
Bshouty NMossel EO'Donnell RServedio R(2003)Learning DNF from random walks44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings.10.1109/SFCS.2003.1238193(189-198)Online publication date: 2003
https://doi.org/10.1109/SFCS.2003.1238193

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Extension of the PAC framework to finite and countable Markov chains

Upper Bounds on Mixing Time of Finite Markov Chains

An EM algorithm for continuous-time bivariate Markov chains