Learning Markov models via low-rank optimization
From MaRDI portal
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 of 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 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.
Recommendations
- A low-rank spectral method for learning Markov models
- Adaptive low-nonnegative-rank approximation for state aggregation of Markov chains
- Optimal Kullback-Leibler approximation of Markov chains via nuclear norm regularisation
- Learning parametric policies and transition probability models of Markov decision processes from data
- Learning low-complexity autoregressive models via proximal alternating minimization
Cites work
- A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization
- A partial proximal point algorithm for nuclear norm regularized matrix least squares problems
- A proximal difference-of-convex algorithm with extrapolation
- A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions
- A spectral algorithm for learning hidden Markov models
- An efficient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming
- Another look at distance-weighted discrimination
- Bounding \(\bar d\)-distance by informational divergence: A method to prove measure concentration
- Concentration inequalities for dependent random variables via the martingale method
- Concentration inequalities for Markov chains by Marton couplings and spectral methods
- Convex analysis approach to d. c. programming: Theory, algorithms and applications
- DC programming and DCA: thirty years of developments
- Diffusion Maps, Reduction Coordinates, and Low Dimensional Representation of Stochastic Systems
- Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process
- Estimation of (near) low-rank matrices with noise and high-dimensional scaling
- Exact and ordinary lumpability in finite Markov chains
- Exact penalty and error bounds in DC programming
- Fast Algorithms for Large-Scale Generalized Distance Weighted Discrimination
- Freedman's inequality for matrix martingales
- scientific article; zbMATH DE number 1095138 (Why is no real title available?)
- Markov Chains
- Matrix Completion From a Few Entries
- Minimax Estimation of Discrete Distributions Under <inline-formula> <tex-math notation="LaTeX">$\ell _{1}$ </tex-math></inline-formula> Loss
- Minimax Optimal Rates for Poisson Inverse Problems With Physical Constraints
- Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion
- On matrix approximation problems with Ky Fan \(k\) norms
- Optimal Kullback-Leibler Aggregation via Spectral Theory of Markov Chains
- Poisson Matrix Recovery and Completion
- Rank Centrality: Ranking from Pairwise Comparisons
- Regularized \(M\)-estimators with nonconvexity: statistical and algorithmic theory for local optima
- Semidefinite programming approach for the quadratic assignment problem with a sparse graph
- Spectral State Compression of Markov Processes
- Tensor decompositions for learning latent variable models
- The DC (Difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems
- The direct extension of ADMM for multi-block convex minimization problems is not necessarily convergent
- The Problem of Estimation
- The Spacey Random Walk: A Stochastic Process for Higher-Order Data
Cited in
(12)- Learning low-complexity autoregressive models via proximal alternating minimization
- Recovering Markov models from closed-loop data
- A low-rank spectral method for learning Markov models
- Optimal Kullback-Leibler approximation of Markov chains via nuclear norm regularisation
- Recursive learning for sparse Markov models
- Adaptive low-nonnegative-rank approximation for state aggregation of Markov chains
- Coherent set identification via direct low rank maximum likelihood estimation
- Semidefinite programming approximation for a matrix optimization problem over an uncertain linear system
- Online statistical inference in decision-making with matrix context
- CP factor model for dynamic tensors
- Detection and evaluation of clusters within sequential data
- Low-Rank Contextual Reinforcement Learning from Heterogeneous Human Feedback
This page was built for publication: Learning Markov models via low-rank optimization
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5106374)
