Text

Learning Markov Models Via Low-Rank Optimization

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.

Ketersediaan

Informasi Detail

Judul Seri

OPERATIONS RESEARCH; Vol.70 No.4 July-August 2022

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 2384-2398

Bahasa

English

ISBN/ISSN

-

Klasifikasi

NONE

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

MARKOV MODEL
NON-CONVEX OPTIMIZATION
DC PROGRAMMING
RANK CONSTRAINED LIKELIHOOD

Info Detail Spesifik

https://doi.org/10.1287/opre.2021.2115

Pernyataan Tanggungjawab

Ziwei Zhu, Xudong Li, Mengdi Wang, Anru Zhang

Versi lain/terkait

Lampiran Berkas

Komentar