Learning Markov Models Via Low-Rank Optimization

Ziwei Zhu (), Xudong Li (), Mengdi Wang () and Anru Zhang ()
Additional contact information
Ziwei Zhu: Department of Statistics, University of Michigan, Ann Arbor, Michigan 48109
Xudong Li: School of Data Science, Fudan University, Shanghai 200433, China; Shanghai Center for Mathematical Sciences, Fudan University, Shanghai 200433, China
Mengdi Wang: Department of Electrical Engineering, Princeton University, Princeton, New Jersey 08544; Center for Statistics and Machine Learning, Princeton University, Princeton, New Jersey 08544
Anru Zhang: Department of Statistics, University of Wisconsin-Madison, Madison, Wisconsin 53706; Department of Biostatistics and Bioinformatics, Duke University, Durham, North Carolina 27710

Operations Research, 2022, vol. 70, issue 4, 2384-2398

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.

Keywords: Machine Learning and Data Science; Markov model; DC programming; non-convex optimization; rank constrained likelihood (search for similar items in EconPapers)
Date: 2022
References: Add references at CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2021.2115 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:70:y:2022:i:4:p:2384-2398

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().