Learning Markov Models Via Low-Rank Optimization

Ziwei Zhu, Xudong Li, Mengdi Wang, Anru Zhang

Research output: Contribution to journalArticlepeer-review

8 Scopus citations

Abstract

Modeling unknown systems from data is a precursor of system optimization and sequential decision making. In this paper, we focus on learning a Markov model from a single trajectory of states. Suppose that the transition model has a small rank despite having a large state space, meaning that the system admits a low-dimensional latent structure. We show that one can estimate the full transition model accurately using a trajectory of length that is proportional to the total number of states. We propose two maximum-likelihood estimation methods: a convex approach with nuclear norm regularization and a nonconvex approach with rank constraint. We explicitly derive the statistical rates of both estimators in terms of the Kullback-Leiber divergence and the ℓ2 error and also establish a minimax lower bound to assess the tightness of these rates. For computing the nonconvex estimator, we develop a novel DC (difference of convex function) programming algorithm that starts with the convex M-estimator and then successively refines the solution till convergence. Empirical experiments demonstrate consistent superiority of the nonconvex estimator over the convex one.

Original languageEnglish (US)
Pages (from-to)2384-2398
Number of pages15
JournalOperations Research
Volume70
Issue number4
DOIs
StatePublished - Jul 1 2022

All Science Journal Classification (ASJC) codes

  • Computer Science Applications
  • Management Science and Operations Research

Keywords

  • DC programming
  • Markov model
  • non-convex optimization
  • rank constrained likelihood

Fingerprint

Dive into the research topics of 'Learning Markov Models Via Low-Rank Optimization'. Together they form a unique fingerprint.

Cite this