Minimax Learning of Ergodic Markov Chains

Geoffrey Wolfer, Aryeh Kontorovich
Proceedings of the 30th International Conference on Algorithmic Learning Theory, PMLR 98:904-930, 2019.

Abstract

We compute the finite-sample minimax (modulo logarithmic factors) sample complexity of learning the parameters of a finite Markov chain from a single long sequence of states. Our error metric is a natural variant of total variation. The sample complexity necessarily depends on the spectral gap and minimal stationary probability of the unknown chain, for which there are known finite-sample estimators with fully empirical confidence intervals. To our knowledge, this is the first PAC-type result with nearly matching (up to logarithmic factors) upper and lower bounds for learning, in any metric, in the context of Markov chains.

Cite this Paper

BibTeX
@InProceedings{pmlr-v98-wolfer19a, title = {Minimax Learning of Ergodic Markov Chains}, author = {Wolfer, Geoffrey and Kontorovich, Aryeh}, booktitle = {Proceedings of the 30th International Conference on Algorithmic Learning Theory}, pages = {904--930}, year = {2019}, editor = {Garivier, Aurélien and Kale, Satyen}, volume = {98}, series = {Proceedings of Machine Learning Research}, month = {22--24 Mar}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v98/wolfer19a/wolfer19a.pdf}, url = {https://proceedings.mlr.press/v98/wolfer19a.html}, abstract = {We compute the finite-sample minimax (modulo logarithmic factors) sample complexity of learning the parameters of a finite Markov chain from a single long sequence of states. Our error metric is a natural variant of total variation. The sample complexity necessarily depends on the spectral gap and minimal stationary probability of the unknown chain, for which there are known finite-sample estimators with fully empirical confidence intervals. To our knowledge, this is the first PAC-type result with nearly matching (up to logarithmic factors) upper and lower bounds for learning, in any metric, in the context of Markov chains.} }
Endnote
%0 Conference Paper %T Minimax Learning of Ergodic Markov Chains %A Geoffrey Wolfer %A Aryeh Kontorovich %B Proceedings of the 30th International Conference on Algorithmic Learning Theory %C Proceedings of Machine Learning Research %D 2019 %E Aurélien Garivier %E Satyen Kale %F pmlr-v98-wolfer19a %I PMLR %P 904--930 %U https://proceedings.mlr.press/v98/wolfer19a.html %V 98 %X We compute the finite-sample minimax (modulo logarithmic factors) sample complexity of learning the parameters of a finite Markov chain from a single long sequence of states. Our error metric is a natural variant of total variation. The sample complexity necessarily depends on the spectral gap and minimal stationary probability of the unknown chain, for which there are known finite-sample estimators with fully empirical confidence intervals. To our knowledge, this is the first PAC-type result with nearly matching (up to logarithmic factors) upper and lower bounds for learning, in any metric, in the context of Markov chains.
APA
Wolfer, G. & Kontorovich, A.. (2019). Minimax Learning of Ergodic Markov Chains. Proceedings of the 30th International Conference on Algorithmic Learning Theory, in Proceedings of Machine Learning Research 98:904-930 Available from https://proceedings.mlr.press/v98/wolfer19a.html.

Related Material