article

Free access

Change-point computation for large graphical models: a scalable algorithm for Gaussian graphical models with change-points

Authors:

Yves AtchadéAuthors Info & Claims

The Journal of Machine Learning Research, Volume 19, Issue 1

Pages 440 - 477

Published: 01 January 2018 Publication History

PDF eReader Publisher Site

Abstract

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 majorizeminimize (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.

References

[1]

Y. F. Atchadé, 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.

[3]

Alexander Aue, Siegfried Hormann, Lajos Horváth, and Matthew Reimherr. Break detection in the covariance structure of multivariate time series models. Ann. Statist., 37(6B):4046-4087, 12 2009.

[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.

[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.

Digital Library

[7]

Andrea Beltratti and Claudio Morana. Breaks and persistency: macroeconomic causes of stock market volatility. Journal of econometrics, 131(1):151-177, 2006.

[8]

Peter J. Bickel and Elizaveta Levina. Covariance regularization by thresholding. Ann. Statist., 36 (6):2577-2604, 2008.

[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.

[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öfling, and Robert Tibshirani. Pathwise coordinate optimization. Ann. Appl. Stat., 1(2):302-332, 2007.

[14]

Piotr Fryzlewicz. Wild binary segmentation for multiple change-point detection. Ann. Statist., 42 (6):2243-2281, 12 2014.

[15]

Samet Günay. 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.

[17]

Holger Höfling and Robert Tibshirani. Estimation of sparse binary pairwise Markov networks using pseudo-likelihoods. J. Mach. Learn. Res., 10:883-906, 2009.

Digital Library

[18]

M. Kolar, L. Song, A. Ahmed, and E. Xing. Estimating time-varying networks. Ann. Appl. Statist., 4(1):94-123, 2010.

[19]

Mladen Kolar and Eric P. Xing. Estimating networks with jumps. Electron. J. Statist., 6:2069-2106, 2012.

[20]

John Lafferty, Han Liu, Larry Wasserman, et al. Sparse nonparametric graphical models. Statistical Science, 27(4):519-537, 2012.

[21]

B. Laurent and P. Massart. Adaptive estimation of a quadratic functional by model selection. Ann. Statist., 28(5):1302-1338, 2000.

[22]

F. Leonardi and P. Bühlmann. Computationally efficient change point detection for high-dimensional regression. ArXiv e-prints, 2016.

[23]

Céline Lévy-Leduc and Franois Roueff. Detection and localization of change-points in high-dimensional network traffic data. Ann. Appl. Stat., 3(2):637-662, 06 2009.

[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 Železný, 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.

[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.

[27]

Neal Parikh and Stephen Boyd. Proximal algorithms. Foundations and Trends in Optimization, 1 (3):123-231, 2013.

Digital Library

[28]

Pradeep Ravikumar, Martin J. Wainwright, and John D. Lafferty. High-dimensional Ising model selection using l₁-regularized logistic regression. Ann. Statist., 38(3):1287-1319, 2010.

[29]

Pradeep Ravikumar, Martin J. Wainwright, Garvesh Raskutti, and Bin Yu. High-dimensional covariance estimation by minimizing l₁-penalized log-determinant divergence. Electron. J. Stat., 5: 935-980, 2011.

[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é, 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.

[32]

Tong Tong Wu and Kenneth Lange. The mm alternative to em. Statist. Sci., 25(4):492-505, 11 2010.

[33]

Ming Yuan and Yi Lin. Model selection and estimation in the Gaussian graphical model. Biometrika, 94(1):19-35, 2007.

[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.

Cited By

Cui XGeng HWang ZZou C(2024)Robust Estimation of High-Dimensional Linear Regression With ChangepointsIEEE Transactions on Information Theory10.1109/TIT.2024.342332570:10(7297-7319)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3423325
Le Bars BHumbert PKalogeratos AVayatis NDaumé HSingh A(2020)Learning the piece-wise constant graph structure of a varying Ising modelProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525001(675-684)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525001

Change-point computation for large graphical models: a scalable algorithm for Gaussian graphical models with change-points
1. Computing methodologies

Recommendations

Sequential change-point detection in high-dimensional Gaussian graphical models

High dimensional piecewise stationary graphical models represent a versatile class for modelling time varying networks arising in diverse application areas, including biology, economics, and social sciences. There has been recent work in offline detection ...
Learning Gaussian graphical models with latent confounders
Abstract
Gaussian Graphical models (GGM) are widely used to estimate network structure in domains ranging from biology to finance. In practice, data is often corrupted by latent confounders which biases inference of the underlying true ...
Multi-stage change-point detection scheme for large-scale simultaneous events

Change-point detection schemes, which represent one type of anomaly detection schemes, are a promising approach for detecting network anomalies, such as attacks and epidemics by unknown viruses and worms. These events are detected as change-points. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image The Journal of Machine Learning Research

The Journal of Machine Learning Research Volume 19, Issue 1

January 2018

3249 pages

ISSN:1532-4435

EISSN:1533-7928

Editors:
Francis Bach
INRIA
,
Blei David
Columbia University
,
Bernhard Schölkopf
MPI for Intelligent Systems

Issue’s Table of Contents

Publisher

JMLR.org

Publication History

Revised: 01 March 2018

Published: 01 January 2018

Published in JMLR Volume 19, Issue 1

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
121
Total Downloads

Downloads (Last 12 months)45
Downloads (Last 6 weeks)4

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cui XGeng HWang ZZou C(2024)Robust Estimation of High-Dimensional Linear Regression With ChangepointsIEEE Transactions on Information Theory10.1109/TIT.2024.342332570:10(7297-7319)Online publication date: 1-Oct-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3423325
Le Bars BHumbert PKalogeratos AVayatis NDaumé HSingh A(2020)Learning the piece-wise constant graph structure of a varying Ising modelProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525001(675-684)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525001

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents