Optimal prediction of Markov chains with and without spectral gap
Authors: Yanjun Han, Soham Jana, Yihong Wu
NeurIPS 2021 | Conference 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 yjhan@berkeley.edu Soham Jana Department of Statistics and Data Science Yale University New Haven, CT 06520 soham.jana@yale.edu Yihong Wu Department of Statistics and Data Science Yale University New Haven, CT 06520 yihong.wu@yale.edu |
| 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. |