IDEAS home Printed from https://ideas.repec.org/a/inm/orijoc/v33y2021i2p531-550.html
   My bibliography  Save this article

On the Solution of ℓ 0 -Constrained Sparse Inverse Covariance Estimation Problems

Author

Listed:
  • Dzung T. Phan

    (IBM T.J. Watson Research Center, Yorktown Heights, New York 10598)

  • Matt Menickelly

    (Argonne National Laboratory, Lemont, Illinois 60439)

Abstract

The sparse inverse covariance matrix is used to model conditional dependencies between variables in a graphical model to fit a multivariate Gaussian distribution. Estimating the matrix from data are well known to be computationally expensive for large-scale problems. Sparsity is employed to handle noise in the data and to promote interpretability of a learning model. Although the use of a convex ℓ 1 regularizer to encourage sparsity is common practice, the combinatorial ℓ 0 penalty often has more favorable statistical properties. In this paper, we directly constrain sparsity by specifying a maximally allowable number of nonzeros, in other words, by imposing an ℓ 0 constraint. We introduce an efficient approximate Newton algorithm using warm starts for solving the nonconvex ℓ 0 -constrained inverse covariance learning problem. Numerical experiments on standard data sets show that the performance of the proposed algorithm is competitive with state-of-the-art methods. Summary of Contribution: The inverse covariance estimation problem underpins many domains, including statistics, operations research, and machine learning. We propose a scalable optimization algorithm for solving the nonconvex ℓ 0 -constrained problem.

Suggested Citation

  • Dzung T. Phan & Matt Menickelly, 2021. "On the Solution of ℓ 0 -Constrained Sparse Inverse Covariance Estimation Problems," INFORMS Journal on Computing, INFORMS, vol. 33(2), pages 531-550, May.
  • Handle: RePEc:inm:orijoc:v:33:y:2021:i:2:p:531-550
    DOI: 10.1287/ijoc.2020.0991
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/ijoc.2020.0991
    Download Restriction: no

    File URL: https://libkey.io/10.1287/ijoc.2020.0991?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. William W. Hager & Dzung T. Phan & Jiajie Zhu, 2016. "Projection algorithms for nonconvex minimization with application to sparse principal component analysis," Journal of Global Optimization, Springer, vol. 65(4), pages 657-676, August.
    2. Zou, Hui, 2006. "The Adaptive Lasso and Its Oracle Properties," Journal of the American Statistical Association, American Statistical Association, vol. 101, pages 1418-1429, December.
    Full references (including those not matched with items on IDEAS)

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Tutz, Gerhard & Pößnecker, Wolfgang & Uhlmann, Lorenz, 2015. "Variable selection in general multinomial logit models," Computational Statistics & Data Analysis, Elsevier, vol. 82(C), pages 207-222.
    2. Xu, Yang & Zhao, Shishun & Hu, Tao & Sun, Jianguo, 2021. "Variable selection for generalized odds rate mixture cure models with interval-censored failure time data," Computational Statistics & Data Analysis, Elsevier, vol. 156(C).
    3. Emmanouil Androulakis & Christos Koukouvinos & Kalliopi Mylona & Filia Vonta, 2010. "A real survival analysis application via variable selection methods for Cox's proportional hazards model," Journal of Applied Statistics, Taylor & Francis Journals, vol. 37(8), pages 1399-1406.
    4. Li, Chunyu & Lou, Chenxin & Luo, Dan & Xing, Kai, 2021. "Chinese corporate distress prediction using LASSO: The role of earnings management," International Review of Financial Analysis, Elsevier, vol. 76(C).
    5. Mkhadri, Abdallah & Ouhourane, Mohamed, 2013. "An extended variable inclusion and shrinkage algorithm for correlated variables," Computational Statistics & Data Analysis, Elsevier, vol. 57(1), pages 631-644.
    6. Yanlin Tang & Xinyuan Song & Zhongyi Zhu, 2015. "Variable selection via composite quantile regression with dependent errors," Statistica Neerlandica, Netherlands Society for Statistics and Operations Research, vol. 69(1), pages 1-20, February.
    7. Gustavo Peralta, 2016. "The Nature of Volatility Spillovers across the International Capital Markets," CNMV Working Papers CNMV Working Papers no. 6, CNMV- Spanish Securities Markets Commission - Research and Statistics Department.
    8. Bakalli, Gaetan & Guerrier, Stéphane & Scaillet, Olivier, 2023. "A penalized two-pass regression to predict stock returns with time-varying risk premia," Journal of Econometrics, Elsevier, vol. 237(2).
    9. Chuliá, Helena & Garrón, Ignacio & Uribe, Jorge M., 2024. "Daily growth at risk: Financial or real drivers? The answer is not always the same," International Journal of Forecasting, Elsevier, vol. 40(2), pages 762-776.
    10. Philippe Goulet Coulombe & Maxime Leroux & Dalibor Stevanovic & Stéphane Surprenant, 2022. "How is machine learning useful for macroeconomic forecasting?," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 37(5), pages 920-964, August.
    11. Wongsa-art, Pipat & Kim, Namhyun & Xia, Yingcun & Moscone, Francesco, 2024. "Varying coefficient panel data models and methods under correlated error components: Application to disparities in mental health services in England," Regional Science and Urban Economics, Elsevier, vol. 106(C).
    12. Andrea Bucci, 2020. "Realized Volatility Forecasting with Neural Networks," Journal of Financial Econometrics, Oxford University Press, vol. 18(3), pages 502-531.
    13. Christopher J Greenwood & George J Youssef & Primrose Letcher & Jacqui A Macdonald & Lauryn J Hagg & Ann Sanson & Jenn Mcintosh & Delyse M Hutchinson & John W Toumbourou & Matthew Fuller-Tyszkiewicz &, 2020. "A comparison of penalised regression methods for informing the selection of predictive markers," PLOS ONE, Public Library of Science, vol. 15(11), pages 1-14, November.
    14. Jun Zhu & Hsin‐Cheng Huang & Perla E. Reyes, 2010. "On selection of spatial linear models for lattice data," Journal of the Royal Statistical Society Series B, Royal Statistical Society, vol. 72(3), pages 389-402, June.
    15. Norman R. Swanson & Weiqi Xiong, 2018. "Big data analytics in economics: What have we learned so far, and where should we go from here?," Canadian Journal of Economics/Revue canadienne d'économique, John Wiley & Sons, vol. 51(3), pages 695-746, August.
    16. Dong, C. & Li, S., 2021. "Specification Lasso and an Application in Financial Markets," Cambridge Working Papers in Economics 2139, Faculty of Economics, University of Cambridge.
    17. Lam, Clifford, 2008. "Estimation of large precision matrices through block penalization," LSE Research Online Documents on Economics 31543, London School of Economics and Political Science, LSE Library.
    18. Ping Wu & Xinchao Luo & Peirong Xu & Lixing Zhu, 2017. "New variable selection for linear mixed-effects models," Annals of the Institute of Statistical Mathematics, Springer;The Institute of Statistical Mathematics, vol. 69(3), pages 627-646, June.
    19. Giraud Christophe & Huet Sylvie & Verzelen Nicolas, 2012. "Graph Selection with GGMselect," Statistical Applications in Genetics and Molecular Biology, De Gruyter, vol. 11(3), pages 1-52, February.
    20. Yu Zheng & Tianxi Cai, 2017. "Augmented estimation for t‐year survival with censored regression models," Biometrics, The International Biometric Society, vol. 73(4), pages 1169-1178, December.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:orijoc:v:33:y:2021:i:2:p:531-550. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.