Change-point computation for large graphical models: a scalable algorithm for Gaussian graphical models with change-points. (English) Zbl 1444.62077

Bybee, Leland; Atchadé, Yves

J. Mach. Learn. Res. 19, Paper No. 11, 38 p. (2018).

Summary: Graphical models with change-points are computationally challenging to fit, particularly in cases where the number of observation points and the number of nodes in the graph are large. Focusing on Gaussian graphical models, we introduce an approximate majorize-minimize (MM) algorithm that can be useful for computing change-points in large graphical models. The proposed algorithm is an order of magnitude faster than a brute force search. Under some regularity conditions on the data generating process, we show that with high probability, the algorithm converges to a value that is within statistical error of the true change-point. A fast implementation of the algorithm using Markov Chain Monte Carlo is also introduced. The performances of the proposed algorithms are evaluated on synthetic data sets and the algorithm is also used to analyze structural changes in the S&P 500 over the period 2000–2016.

MSC:

62H22	Probabilistic graphical models
62G10	Nonparametric hypothesis testing
62L20	Stochastic approximation
62P20	Applications of statistics to economics

Keywords:

change-points; Gaussian graphical models; proximal gradient; simulated annealing; stochastic optimization

Software:

wbs; changepointsHD

References:

[1]	Y. F. Atchad´e, R. Mazumder, and J. Chen. Scalable Computation of Regularized Precision Matrices via Stochastic Optimization. ArXiv e-prints, September 2015.
[2]	Y. F. Atchade, G. Fort, and E. Moulines. On stochastic proximal gradient algorithms. Journal of Machine Learning Research, 18:1–33, 2017. 36 · Zbl 1433.90199
[3]	Alexander Aue, Siegfried Hormann, Lajos Horv´ath, and Matthew Reimherr. Break detection in the covariance structure of multivariate time series models. Ann. Statist., 37(6B):4046–4087, 12 2009. · Zbl 1191.62143
[4]	Jushan Bai. Estimation of a change point in multiple regression models. The Review of Economics and Statistics, 79(4):551–563, 1997.
[5]	Anindya Banerjee and Giovanni Urga. Modelling structural breaks, long memory and stock market volatility: an overview. Journal of Econometrics, 129(1):1–34, 2005. · Zbl 1335.00139
[6]	Onureena Banerjee, Laurent El Ghaoui, and Alexandre d’Aspremont. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. J. Mach. Learn. Res., 9:485–516, 2008. · Zbl 1225.68149
[7]	Andrea Beltratti and Claudio Morana. Breaks and persistency: macroeconomic causes of stock market volatility. Journal of econometrics, 131(1):151–177, 2006. · Zbl 1337.62343
[8]	Peter J. Bickel and Elizaveta Levina. Covariance regularization by thresholding. Ann. Statist., 36 (6):2577–2604, 2008. · Zbl 1196.62062
[9]	Leland Bybee.changepointsHD: Change-Point Estimation for Expensive and High-Dimensional Models, 2017. R package version 0.3.0.
[10]	Hao Chen and Nancy Zhang. Graph-based change-point detection. Ann. Statist., 43(1):139–176, 02 2015. · Zbl 1308.62090
[11]	Haeran Cho and Piotr Fryzlewicz. Multiple-change-point detection for high dimensional time series via sparsified binary segmentation. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 77(2):475–507, 2015.
[12]	Kyongwook Choi, Wei-Choun Yu, and Eric Zivot. Long memory versus structural breaks in modeling and forecasting realized volatility. Journal of International Money and Finance, 29(5):857–875, 2010.
[13]	Jerome Friedman, Trevor Hastie, Holger H¨ofling, and Robert Tibshirani. Pathwise coordinate optimization. Ann. Appl. Stat., 1(2):302–332, 2007. · Zbl 1378.90064
[14]	Piotr Fryzlewicz. Wild binary segmentation for multiple change-point detection. Ann. Statist., 42 (6):2243–2281, 12 2014. · Zbl 1302.62075
[15]	Samet G¨unay. Long memory property and structural breaks in volatility: Evidence from turkey and brazil. International Journal of Economics and Finance, 6(12):119, 2014.
[16]	T. Hastie, R Tibshirani, and M. Wainwright. Statistical Learning with Sparsity: The Lasso and Generalizations. Chapman and Hall/CRC, 2015. ISBN 978-1-4987-1216-3. · Zbl 1319.68003
[17]	Holger H¨ofling and Robert Tibshirani. Estimation of sparse binary pairwise Markov networks using pseudo-likelihoods. J. Mach. Learn. Res., 10:883–906, 2009. · Zbl 1245.62121
[18]	M. Kolar, L. Song, A. Ahmed, and E. Xing. Estimating time-varying networks. Ann. Appl. Statist., 4(1):94–123, 2010. · Zbl 1189.62142
[19]	Mladen Kolar and Eric P. Xing. Estimating networks with jumps. Electron. J. Statist., 6:2069–2106, 2012. · Zbl 1295.62032
[20]	John Lafferty, Han Liu, Larry Wasserman, et al. Sparse nonparametric graphical models. Statistical Science, 27(4):519–537, 2012. 37 · Zbl 1331.62219
[21]	B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Ann. Statist., 28(5):1302–1338, 2000. · Zbl 1105.62328
[22]	F. Leonardi and P. B¨uhlmann. Computationally efficient change point detection for high-dimensional regression. ArXiv e-prints, 2016.
[23]	C´eline L´evy-Leduc and Franois Roueff.Detection and localization of change-points in highdimensional network traffic data. Ann. Appl. Stat., 3(2):637–662, 06 2009. · Zbl 1166.62094
[24]	Song Liu, John A. Quinn, Michael U. Gutmann, and Masashi Sugiyama. Direct learning of sparse changes in markov networks by density ratio estimation. In Hendrik Blockeel, Kristian Kersting, Siegfried Nijssen, and Filip ˇZelezn´y, editors, Machine Learning and Knowledge Discovery in Databases, pages 596–611, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
[25]	N. Meinshausen and P. Buhlmann. High-dimensional graphs with the lasso. Annals of Stat., 34: 1436–1462, 2006. · Zbl 1113.62082
[26]	Sahand N. Negahban, Pradeep Ravikumar, Martin J. Wainwright, and Bin Yu. A unified framework for high-dimensional analysis of m-estimators with decomposable regularizers. Statistical Science, 27(4):538–557, 11 2012. doi: 10.1214/12-STS400. · Zbl 1331.62350
[27]	Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1 (3):123–231, 2013.
[28]	Pradeep Ravikumar, Martin J. Wainwright, and John D. Lafferty. High-dimensional Ising model selection using ‘1-regularized logistic regression. Ann. Statist., 38(3):1287–1319, 2010. · Zbl 1189.62115
[29]	Pradeep Ravikumar, Martin J. Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covariance estimation by minimizing ‘1-penalized log-determinant divergence. Electron. J. Stat., 5: 935–980, 2011. · Zbl 1274.62190
[30]	Benjamin Rolfs, Bala Rajaratnam, Dominique Guillot, Ian Wong, and Arian Maleki.Iterative thresholding algorithm for sparse inverse covariance estimation. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 1574–1582. Curran Associates, Inc., 2012.
[31]	Sandipan Roy, Yves Atchad´e, and George Michailidis. Change point estimation in high dimensional markov random-field models. Journal of the Royal Statistical Society: Series B (Statistical Methodology), pages 1187–1206, 2017. · Zbl 1373.62260
[32]	Tong Tong Wu and Kenneth Lange. The mm alternative to em. Statist. Sci., 25(4):492–505, 11 2010. · Zbl 1329.62106
[33]	Ming Yuan and Yi Lin. Model selection and estimation in the Gaussian graphical model. Biometrika, 94(1):19–35, 2007. · Zbl 1142.62408
[34]	S. Zhou, J. Lafferty, and L. Wasserman. Time-varying undirected graphs. In Rocco A. Dervedio and Tong Zhang, editors, Conference on learning Theory, pages 455–466, 2009.