# Learning Overcomplete HMMs

arXiv: https://arxiv.org/abs/1711.02309 · HTML: https://mlsanity.com/paper/1711.02309/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 7 Nov 2017.

## Built on by (most cited first, 9 of 9)

- [POPGym: Benchmarking Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2303.01859/) (2023)
- [Schema-learning and rebinding as mechanisms of in-context learning and emergence](https://mlsanity.com/paper/2307.01201/) (2023)
- [Learning Hidden Markov Models Using Conditional Samples](https://mlsanity.com/paper/2302.14753/) (2023)
- [Causal Inference Despite Limited Global Confounding via Mixture Models](https://mlsanity.com/paper/2112.11602/) (2021)
- [Model Stealing for Any Low-Rank Language Model](https://mlsanity.com/paper/2411.07536/) (2024)
- [Graph schemas as abstractions for transfer learning, inference, and planning](https://mlsanity.com/paper/2302.07350/) (2023)
- [Differentiable Filtering for Learning Hidden Markov Models](https://mlsanity.com/paper/2511.10571/) (2025)
- [Toward Learning POMDPs Beyond Full-Rank Actions and State Observability](https://mlsanity.com/paper/2601.18930/) (2026)
- [Fast exploration and learning of latent graphs with aliased observations](https://mlsanity.com/paper/2303.07397/) (2023)

## Abstract (arXiv)

We study the problem of learning overcomplete HMMs---those that have many hidden states but a small output alphabet. Despite having significant practical importance, such HMMs are poorly understood with no known positive or negative results for efficient learning. In this paper, we present several new results---both positive and negative---which help define the boundaries between the tractable and intractable settings. Specifically, we show positive results for a large subclass of HMMs whose transition matrices are sparse, well-conditioned, and have small probability mass on short cycles. On the other hand, we show that learning is impossible given only a polynomial number of samples for HMMs with a small output alphabet and whose transition matrices are random regular graphs with large degree. We also discuss these results in the context of learning HMMs which can capture long-term dependencies.