Research map / Learning theory and algorithms / Matrix and tensor methods
Learning Overcomplete HMMs
Vatsal Sharan, Sham M. Kakade, Percy Liang, Gregory Valiant
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use tensor-decomposition method of moments under sparse, well-conditioned transitions with few short cycles and random small-support outputs | Overcomplete HMMs · HMMs satisfying the stated assumptions | sample complexity: \poly{n,1/\epsilon} | Improved |
| Use a transition support containing a permutation whose cycles are at least 2⌈log_m n⌉ states | Sparse HMMs · Sparse HMM identifiability | identifiability window length: 4\lceil \log_m n\rceil +1 | Improved |
| Use a window length of 2⌈log_m n⌉ + 1 for generic HMMs | Generic HMMs · Generic HMM identifiability | identifiability window length: 2\lceil \log_m n\rceil +1 | Improved |
| Increase the probability mass on short cycles | Transition matrix and likelihood matrix A · Simulation with n=128 | conditioning of likelihood matrix A | Hurt |
| Increase transition degree or probability mass on the dense transition component | Transition matrix and likelihood matrix A · Simulation with n=128 | conditioning of likelihood matrix A | Hurt |
Closest papers by meaning
- Frontiers to the learning of nonparametric hidden Markov models (JMLR 2025 · similarity 0.87)
- Learning HMMs with Nonparametric Emissions via Spectral Decompositions of Continuous Matrices (NeurIPS 2016 · similarity 0.86)
- Linear approximations to HMM filtering (NeurIPS 2026 · similarity 0.85)
- Infinite Factorial Unbounded-State Hidden Markov Model (TPAMI 2016 · similarity 0.85)
- Learning Hidden Markov Models When the Locations of Missing Observations are Unknown (ICML 2023 · similarity 0.85)
- Learning Juntas under Markov Random Fields (NeurIPS 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
