Learning Markov Models Via Low-Rank Optimization

References

• Anandkumar A, Ge R, Hsu D, Kakade SM, Telgarsky M (2014) Tensor decompositions for learning latent variable models. J. Mach. Learn. Res. 15(1):2773–2832.Google Scholar
• Azizzadenesheli K, Lazaric A, Anandkumar A (2016) Reinforcement learning in rich-observation MDPs using spectral methods. Preprint, submitted November 11, 2016, https://arxiv.org/abs/1611.03907.Google Scholar
• Benson AR, Gleich DF, Lim LH (2017) The spacey random walk: A stochastic process for higher-order data. SIAM Rev. 59(2):321–345.Crossref, Google Scholar
• Bertsekas DP (1995) Dynamic Programming and Optimal Control, vol. 1. (Athena Scientific, Belmont, MA).Google Scholar
• Bertsekas DP, Tsitsiklis JN (1995) Neuro-dynamic programming: an overview. Proceedings of the 34th IEEE Conference on Decision and Control, vol. 1 (IEEE), 560–564.Google Scholar
• Brémaud P (1999) Markov Chains: Gibbs fields, Monte Carlo Simulation, and Queues, vol. 31. (Springer Science & Business Media, Berlin, Germany).Crossref, Google Scholar
• Buchholz P (1994) Exact and ordinary lumpability in finite Markov chains. J. Appl. Probab. 31(1):59–75.Crossref, Google Scholar
• Cao Y, Xie Y (2016) Poisson matrix recovery and completion. IEEE Trans. Signal Process. 64(6):1609–1620.Crossref, Google Scholar
• Chen L, Sun D, Toh KC (2017) An efficient inexact symmetric Gauss–Seidel based majorized ADMM for high-dimensional convex composite conic programming. Math. Program. 161(1-2):237–270.Crossref, Google Scholar
• Chen C, He B, Ye Y, Yuan X (2016) The direct extension of admm for multi-block convex minimization problems is not necessarily convergent. Math. Program. 155(1-2):57–79.Crossref, Google Scholar
• Chodera JD, Singhal N, Pande VS, Dill KA, Swope WC (2007) Automatic discovery of metastable states for the construction of Markov models of macromolecular conformational dynamics. J. Chem. Phys. 126(15), 155101.Crossref, Google Scholar
• Coifman RR, Kevrekidis IG, Lafon S, Maggioni M, Nadler B (2008) Diffusion maps, reduction coordinates, and low dimensional representation of stochastic systems. Multiscale Model. Simul. 7(2):842–864.Crossref, Google Scholar
• Deng K, Huang D (2012) Model reduction of Markov chains via low-rank approximation. American Control Conference (ACC), 2012, 2651–2656.Google Scholar
• Deng K, Mehta PG, Meyn SP (2011) Optimal Kullback-Leibler aggregation via spectral theory of Markov chains. IEEE Trans. Automat. Control. 56(12):2793–2808.Crossref, Google Scholar
• Ferreira JFB, Khoo Y, Singer A (2018) Semidefinite programming approach for the quadratic assignment problem with a sparse graph. Comput. Optim. Appl. 69:677–712.Crossref, Google Scholar
• Fill JA (1991) Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Probab. 1(1):62–87.Crossref, Google Scholar
• Gao Y, Sun D (2010) A majorized penalty approach for calibrating rank constrained correlation matrix problems. Technical Report.Google Scholar
• Hall EC, Raskutti G, Willett R (2016) Inference of high-dimensional autoregressive generalized linear models. Preprint, Submitted May 9, 2016, https://arxiv.org/abs/1605.02693.Google Scholar
• Han Y, Jiao J, Weissman T (2015) Minimax estimation of discrete distributions under ℓ1 loss. IEEE Trans. Inform. Theory. 61(11):6343–6354.Crossref, Google Scholar
• Hao Y, Orlitsky A, Pichapati V (2018) On learning Markov chains. Adv. Neural Inf. Process. Syst. Preprint, Submitted October 28, 2018, https://arxiv.org/abs/1810.11754.Google Scholar
• Hsu D, Kakade SM, Zhang T (2012) A spectral algorithm for learning hidden Markov models. J. Comput. System Sci. 78(5):1460–1480.Crossref, Google Scholar
• Huang Q, Kakade SM, Kong W, Valiant G (2016) Recovering structured probability matrices. Preprint, Submitted February 21, 2016, https://arxiv.org/abs/1602.06586.Google Scholar
• Jiang B, Fan J, Sun Q (2018) Bernstein’s inequality for general markov chains. Preprint, Submitted May 28, 2018, https://arxiv.org/abs/1805.10721.Google Scholar
• Jiang X, Raskutti G, Willett R (2015) Minimax optimal rates for poisson inverse problems with physical constraints. IEEE Trans. Inform. Theory. 61(8):4458–4474.Crossref, Google Scholar
• Jiang K, Sun D, Toh KC (2014) A partial proximal point algorithm for nuclear norm regularized matrix least squares problems. Math. Program. Comput. 6(3):281–325.Crossref, Google Scholar
• Keshavan RH, Montanari A, Oh S (2010) Matrix completion from a few entries. IEEE Trans. Inform. Theory. 56(6):2980–2998.Crossref, Google Scholar
• Koltchinskii V, Lounici K, Tsybakov AB (2011) Nuclear-norm penalization and optimal rates for noisy low-rank matrix completion. Ann. Statist. 39(5):2302–2329.Crossref, Google Scholar
• Kontorovich L (2007) Measure concentration of strongly mixing processes with applications. Ph.D. thesis, Carnegie Mellon University, School of Computer Science, Machine Learning.Google Scholar
• Kontorovich LA, Ramanan K (2008) Concentration inequalities for dependent random variables via the martingale method. Ann. Probab. 36(6):2126–2158.Crossref, Google Scholar
• Lam XY, Marron JS, Sun D, Toh KC (2018) Fast algorithms for large-scale generalized distance weighted discrimination. J. Comput. Graph. Stat. 27(2):368–379.Crossref, Google Scholar
• Le Thi HA, Pham Dinh T (2018) DC programming and DCA: thirty years of developments. Math. Program. 169:5–68.Crossref, Google Scholar
• Le Thi HA, Pham Dinh T, Van Ngai H (2012) Exact penalty and error bounds in DC programming. J. Global Optim. 52(3):509–535.Crossref, Google Scholar
• Le Thi HA, Le HM, Phan DN, Tran B (2017) Stochastic DCA for the large-sum of non-convex functions problem and its application to group variable selection in classification. International Conference on Machine Learning, 33 94–34 03.Google Scholar
• Lehmann EL, Casella G (2006) Theory of Point Estimation. (Springer Science & Business Media, Berlin, Germany).Google Scholar
• Li M, Sun D, Toh KC (2016a) A majorized ADMM with indefinite proximal terms for linearly constrained convex composite optimization. SIAM J. Optim. 26(2):922–950.Crossref, Google Scholar
• Li X, Sun D, Toh KC (2016b) A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions. Math. Program. 155(1-2):333–373.Crossref, Google Scholar
• Liu Y, Kang C, Gao S, Xiao Y, Tian Y (2012) Understanding intra-urban trip patterns from taxi trajectory data. J. Geogr. Syst. 14(4):463–483.Crossref, Google Scholar
• Loh PL, Wainwright MJ (2015) Regularized m-estimators with nonconvexity: Statistical and algorithmic theory for local optima. J. Mach. Learn. Res. 16(1):559–616.Google Scholar
• Marton K (1996) Bounding d¯-distance by informational divergence: A method to prove measure concentration. Ann. Probab. 24(2):857–866.Crossref, Google Scholar
• Moore AW (1991) Variable resolution dynamic programming: Efficiently learning action maps in multivariate real-valued state-spaces. Machine Learn. Proc. 1991:333–337.Google Scholar
• Negahban S, Oh S, Shah D (2016) Rank centrality: Ranking from pairwise comparisons. Oper. Res. 65(1):266–287.Link, Google Scholar
• Negahban S, Wainwright MJ (2011) Estimation of (near) low-rank matrices with noise and high-dimensional scaling. Ann. Statist. 39(2):1069–1097.Crossref, Google Scholar
• Newman ME (2013) Spectral methods for community detection and graph partitioning. Phys. Rev. E. 88(4):042822.Crossref, Google Scholar
• Paulin D (2015) Concentration inequalities for markov chains by Marton couplings and spectral methods. Electron. J. Probab. 20:1–32.Google Scholar
• Pham DT, Ha LT (1997) Convex analysis approach to DC programming: Theory, algorithms and applications. Acta Math. Vietnam. 22(1):289–355.Google Scholar
• Pham DT, Ha LT (2005) The DC (difference of convex functions) programming and DCA revisited with DC models of real world nonconvex optimization problems. Ann. Oper. Res. 133(1-4):23–46.Crossref, Google Scholar
• Rockafellar RT (2015) Convex Analysis (Princeton University Press, Princeton, NJ).Google Scholar
• Rohrdanz MA, Zheng W, Maggioni M, Clementi C (2011) Determination of reaction coordinates via locally scaled diffusion map. J. Chem. Phys. 134(12):124116.Crossref, Google Scholar
• Singh SP, Jaakkola T, Jordan MI (1995) Reinforcement learning with soft state aggregation. Tesauro G, Touretzky D, Leen T, eds. Advances in Neural Information Processing Systems 7 (MIT Press, Cambridge, MA) 361–368.Google Scholar
• Steinhaus H (1957) The problem of estimation. Ann. Math. Statist. 28(3):633–648.Crossref, Google Scholar
• Sutton RS, Barto AG (1998) Reinforcement Learning: An Introduction, vol. 1 (MIT Press, Cambridge, MA).Google Scholar
• Tropp JA (2011) Freedman’s inequality for matrix martingales. Electron. Commun. Probab. 16:262–270.Crossref, Google Scholar
• Van Dinh B, Kim DS, Jiao L (2015) Convergence analysis of algorithms for DC programming. Preprint, Submitted August 17, 2015, https://arxiv.org/abs/1508.03899.Google Scholar
• Wang B, Zou H (2018) Another look at distance-weighted discrimination. J. R. Stat. Soc. Ser. B. Stat. Methodol. 80(1):177–198.Crossref, Google Scholar
• Watson G (1993) On matrix approximation problems with Ky Fank norms. Numer. Algorithms. 5(5):263–272.Crossref, Google Scholar
• Wen B, Chen X, Pong TK (2018) A proximal difference-of-convex algorithm with extrapolation. Comput. Optim. Appl. 69:297–324.Crossref, Google Scholar
• Wolfer G, Kontorovich A (2019a) Estimating the mixing time of ergodic Markov chains. Conf. Learn. Theory.Google Scholar
• Wolfer G, Kontorovich A (2019b) Minimax learning of ergodic Markov chains. International Conference on Algorithmic Learning Theory.Google Scholar
• Yang LF, Braverman V, Zhao T, Wang M (2017) Dynamic partition of complex networks. Preprint, Submitted May 23, 2017, arXiv:1705.07881.Google Scholar
• Zhang A, Wang M (2019) Spectral state compression of markov processes. IEEE Trans. Inform. Theory. 66:3202–3231.Google Scholar