Optimal prediction of Markov chains with and without spectral gap
Authors: Yanjun Han, Soham Jana, Yihong Wu
NeurIPS 2021 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the following learning problem with dependent data: Observing a trajectory of length n from a stationary Markov chain with k states, the goal is to predict the next state. For 3 k O( n), using techniques from universal compression, the optimal prediction risk in Kullback-Leibler divergence is shown to be Θ( k2 k2 ), in contrast to the optimal rate of Θ( log log n n ) for k = 2 previously shown in [FOPS16]. |
| Researcher Affiliation | Academia | Yanjun Han Simons Institute for the Theory of Computing University of California, Berkeley Berkeley, CA 94720 EMAIL Soham Jana Department of Statistics and Data Science Yale University New Haven, CT 06520 EMAIL Yihong Wu Department of Statistics and Data Science Yale University New Haven, CT 06520 EMAIL |
| Pseudocode | No | The paper does not contain any structured pseudocode or algorithm blocks clearly labeled as such. |
| Open Source Code | No | The paper is theoretical and does not mention releasing any source code for its methodology. |
| Open Datasets | No | The paper is theoretical and does not conduct empirical studies using datasets. |
| Dataset Splits | No | The paper is theoretical and does not conduct empirical studies, thus no dataset splits are discussed. |
| Hardware Specification | No | The paper is theoretical and does not conduct empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not conduct empirical experiments, therefore no specific software dependencies with version numbers are mentioned. |
| Experiment Setup | No | The paper is theoretical and does not conduct empirical experiments, therefore no experimental setup details or hyperparameters are mentioned. |