Extension of the PAC framework to finite and countable Markov chains

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Extension of the PAC framework to finite and countable Markov chains

Full text

Pdf (918 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the twelfth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 308 - 317

Year of Publication: 1999

ISBN:1-58113-167-4

Author

David Gamarnik

IBM T.J. Watson Research Center, PO Box 218, Yorktown Heights, NY

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
Univ. of California, : University of California at Santa Cruz

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 9, Citation Count: 2

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/307400.307478 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	D. Aldous and J. Fill. Reversible Markov Chains and Random Walks on Graphs. In preparation.
	2	D. Aidous and U. ~3.zirani. A Markovian extension of Valiant's learning model. Proc. 31st Symposium on 1990.
	3	Martin Anthony , Norman Biggs, Computational learning theory: an introduction, Cambridge University Press, New York, NY, 1992
	4	Peter L. Bartlett , Paul Fischer , Klaus-Uwe Höffgen, Exploiting random walks for learning, Proceedings of the seventh annual conference on Computational learning theory, p.318-327, July 12-15, 1994, New Brunswick, New Jersey, United States [doi>10.1145/180139.181167]
	5	D. Bertsimas, D. Gamarnik, and J. Tsitsiklis. Geometric bounds for stationary distribution of infinite Markov Chains via Lyapunov functions. Preprint, i 998.
	6	K.L. Buescher and P.R. Kumar. Learning by canoni- 1EEE Transactions on Automatic Control, 41:545-556, 1996.
	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.
	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.
	9	David Gillman, A Chernoff Bound for Random Walks on Expander Graphs, SIAM Journal on Computing, v.27 n.4, p.1203-1220, Aug. 1998 [doi>10.1137/S0097539794268765]
	10	Michael J. Kearns , Umesh V. Vazirani, An introduction to computational learning theory, MIT Press, Cambridge, MA, 1994
	11	Ron Meir, Performance bounds for nonlinear time series prediction, Proceedings of the tenth annual conference on Computational learning theory, p.122-129, July 06-09, 1997, Nashville, Tennessee, United States [doi>10.1145/267460.267488]
	12	S.P. Meyn. Computable bounds for geometric convergence rates of markov chains. Ann. ofAppl." ' ' rrou., ~, 1994.
	13	S.P. Meyn and R.L. Tweedie. MArkov Chains and Stochastie Stability. Springer-~erlag, 1993.
	14	A. Nobel. A counterexample concerning uniform ergodic theorems for a class of functions. Statistics and Probability Letters, 24:165-168, 1995.
	15	Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995

CITED BY 2

	Nader H. Bshouty , Elchanan Mossel , Ryan O'Donnell , Rocco A. Servedio, Learning DNF from random walks, Journal of Computer and System Sciences, v.71 n.3, p.250-265, October 2005
	Ariel Elbaz , Homin K. Lee , Rocco A. Servedio , Andrew Wan, Separating Models of Learning from Correlated and Uncorrelated Data, The Journal of Machine Learning Research, 8, p.277-290, 5/1/2007