{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,19]],"date-time":"2026-10-19T10:58:46Z","timestamp":1792407526283,"version":"4.4.0"},"reference-count":39,"publisher":"Institute of Mathematical Statistics","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2010,6,1]]},"abstract":"<jats:p>We consider the problem of estimating the graph associated with a binary Ising Markov random field. We describe a method based on \u21131-regularized logistic regression, in which the neighborhood of any given node is estimated by performing logistic regression subject to an \u21131-constraint. The method is analyzed under high-dimensional scaling in which both the number of nodes p and maximum neighborhood size d are allowed to grow as a function of the number of observations n. Our main results provide sufficient conditions on the triple (n, p, d) and the model parameters for the method to succeed in consistently estimating the neighborhood of every node in the graph simultaneously. With coherence conditions imposed on the population Fisher information matrix, we prove that consistent neighborhood selection can be obtained for sample sizes n=\u03a9(d3log\u2009p) with exponentially decaying error. When these same conditions are imposed directly on the sample matrices, we show that a reduced sample size of n=\u03a9(d2log\u2009p) suffices for the method to estimate neighborhoods consistently. Although this paper focuses on the binary graphical models, we indicate how a generalization of the method of the paper would apply to general discrete Markov random fields.<\/jats:p>","DOI":"10.1214\/09-aos691","type":"journal-article","created":{"date-parts":[[2010,3,8]],"date-time":"2010-03-08T08:57:33Z","timestamp":1268038653000},"page":"1287-1319","source":"Crossref","is-referenced-by-count":552,"title":["High-dimensional Ising model selection using \u21131-regularized logistic regression"],"prefix":"10.1214","volume":"38","author":[{"given":"Pradeep","family":"Ravikumar","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Martin J.","family":"Wainwright","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John D.","family":"Lafferty","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"15","doi-asserted-by":"publisher","unstructured":"[15] Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. <i>J. Amer. Statist. Assoc.<\/i> <b>58<\/b> 13\u201330.","DOI":"10.2307\/2282952"},{"key":"1","unstructured":"[1] Abbeel, P., Koller, D. and Ng, A. Y. (2006). Learning factor graphs in polynomial time and sample complexity. <i>J. Mach. Learn. Res.<\/i> <b>7<\/b> 1743\u20131788."},{"key":"2","unstructured":"[2] Banerjee, O., Ghaoui, L. E. and d\u2019Aspr\u00e9mont, A. (2008). Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data. <i>J. Mach. Learn. Res.<\/i> <b>9<\/b> 485\u2013516."},{"key":"5","doi-asserted-by":"publisher","unstructured":"[5] Candes, E. and Tao, T. (2007). The Dantzig selector: Statistical estimation when <i>p<\/i> is much larger than <i>n<\/i> (with discussion). <i>Ann. Statist.<\/i> <b>35<\/b> 2313\u20132351.","DOI":"10.1214\/009053606000001523"},{"key":"6","doi-asserted-by":"crossref","unstructured":"[6] Chickering, D. (1995). Learning Bayesian networks is NP-complete. In <i>Learning from Data: Artificial Intelligence and Statistics V<\/i> (D. Fisher and H. Lenz, eds.). <i>Lecture Notes in Statistics<\/i> <b>112<\/b> 121\u2013130. Springer, New York.","DOI":"10.1007\/978-1-4612-2404-4_12"},{"key":"7","doi-asserted-by":"publisher","unstructured":"[7] Chow, C. and Liu, C. (1968). Approximating discrete probability distributions with dependence trees. <i>IEEE Trans. Inform. Theory<\/i> <b>14<\/b> 462\u2013467.","DOI":"10.1109\/TIT.1968.1054142"},{"key":"8","doi-asserted-by":"crossref","unstructured":"[8] Cross, G. and Jain, A. (1983). Markov random field texture models. <i>IEEE Trans. PAMI<\/i> <b>5<\/b> 25\u201339.","DOI":"10.1109\/TPAMI.1983.4767341"},{"key":"9","doi-asserted-by":"publisher","unstructured":"[9] Csisz\u00e1r, I. and Talata, Z. (2006). Consistent estimation of the basic neighborhood structure of Markov random fields. <i>Ann. Statist.<\/i> <b>34<\/b> 123\u2013145.","DOI":"10.1214\/009053605000000912"},{"key":"11","doi-asserted-by":"publisher","unstructured":"[11] Davidson, K. R. and Szarek, S. J. (2001). Local operator theory, random matrices, and Banach spaces. In <i>Handbook of the Geometry of Banach Spaces<\/i> <b>1<\/b> 317\u2013336. Elsevier, Amsterdam.","DOI":"10.1016\/S1874-5849(01)80010-3"},{"key":"12","doi-asserted-by":"publisher","unstructured":"[12] Donoho, D. and Elad, M. (2003). Maximal sparsity representation via <i>\u2113<\/i><sub>1<\/sub> minimization. <i>Proc. Natl. Acad. Sci. USA<\/i> <b>100<\/b> 2197\u20132202.","DOI":"10.1073\/pnas.0437847100"},{"key":"13","doi-asserted-by":"publisher","unstructured":"[13] Geman, S. and Geman, D. (1984). Stochastic relaxation, Gibbs distributions, and the Bayesian restoration of images. <i>IEEE Trans. PAMI<\/i> <b>6<\/b> 721\u2013741.","DOI":"10.1109\/TPAMI.1984.4767596"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] Hassner, M. and Sklansky, J. (1980). The use of Markov random fields as models of texture. <i>Comp. Graphics Image Proc.<\/i> <b>12<\/b> 357\u2013370.","DOI":"10.1016\/0146-664X(80)90019-2"},{"key":"17","doi-asserted-by":"crossref","unstructured":"[17] Ising, E. (1925). Beitrag zur theorie der ferromagnetismus. <i>Zeitschrift f\u00fcr Physik<\/i> <b>31<\/b> 253\u2013258.","DOI":"10.1007\/BF02980577"},{"key":"18","unstructured":"[18] Kalisch, M. and Buhlmann, P. (2007). Estimating high-dimensional directed acyclic graphs with the pc-algorithm. <i>J. Mach. Learn. Res.<\/i> <b>8<\/b> 613\u2013636."},{"key":"19","unstructured":"[19] Kim, Y., Kim, J. and Kim, Y. (2005). Blockwise sparse regression. <i>Statist. Sinica<\/i> <b>16<\/b> 375\u2013390."},{"key":"20","unstructured":"[20] Koh, K., Kim, S. J. and Boyd, S. (2007). An interior-point method for large-scale <i>\u2113<\/i><sub>1<\/sub>-regularized logistic regression. <i>J. Mach. Learn. Res.<\/i> <b>3<\/b> 1519\u20131555."},{"key":"23","doi-asserted-by":"publisher","unstructured":"[23] Meinshausen, N. and B\u00fchlmann, P. (2006). High dimensional graphs and variable selection with the lasso. <i>Ann. Statist.<\/i> <b>34<\/b> 1436\u20131462.","DOI":"10.1214\/009053606000000281"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] Rothman, A., Bickel, P., Levina, E. and Zhu, J. (2008). Sparse permutation invariant covariance estimation. <i>Electron. J. Stat.<\/i> <b>2<\/b> 494\u2013515.","DOI":"10.1214\/08-EJS176"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[31] Srebro, N. (2003). Maximum likelihood bounded tree-width Markov networks. <i>Artificial Intelligence<\/i> <b>143<\/b> 123\u2013138.","DOI":"10.1016\/S0004-3702(02)00360-0"},{"key":"32","doi-asserted-by":"publisher","unstructured":"[32] Tropp, J. A. (2006). Just relax: Convex programming methods for identifying sparse signals. <i>IEEE Trans. Inform. Theory<\/i> <b>51<\/b> 1030\u20131051.","DOI":"10.1109\/TIT.2005.864420"},{"key":"33","doi-asserted-by":"publisher","unstructured":"[33] Wainwright, M. J. (2009). Sharp thresholds for high-dimensional and noisy sparsity recovery using <i>\u2113<\/i><sub>1<\/sub>-constrained quadratic programming (Lasso). <i>IEEE Trans. Inform. Theory<\/i> <b>55<\/b> 2183\u20132202.","DOI":"10.1109\/TIT.2009.2016018"},{"key":"37","doi-asserted-by":"crossref","unstructured":"[37] Woods, J. (1978). Markov image modeling. <i>IEEE Trans. Automat. Control<\/i> <b>23<\/b> 846\u2013850.","DOI":"10.1109\/TAC.1978.1101866"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[38] Yuan, M. and Lin, Y. (2006). Model selection and estimation in regression with grouped variables. <i>J. R. Stat. Soc. Ser. B Stat. Methodol.<\/i> <b>68<\/b> 49\u201367.","DOI":"10.1111\/j.1467-9868.2005.00532.x"},{"key":"39","unstructured":"[39] Zhao, P. and Yu, B. (2007). On model selection consistency of lasso. <i>J. Mach. Learn. Res.<\/i> <b>7<\/b> 2541\u20132567."},{"key":"3","unstructured":"[3] Bertsekas, D. (1995). <i>Nonlinear Programming<\/i>. Athena Scientific, Belmont, MA."},{"key":"4","unstructured":"[4] Bresler, G., Mossel, E. and Sly, A. (2009). Reconstruction of Markov random fields from samples: Some easy observations and algorithms. Available at http:\/\/front.math.ucdavis.edu\/0712.1402."},{"key":"10","unstructured":"[10] Dasgupta, S. (1999). Learning polytrees. In <i>Proceedings of the Fifteenth Conference on Uncertainty in Artificial Intelligence (UAI-99)<\/i>. Morgan Kaufmann, San Francisco, CA."},{"key":"16","unstructured":"[16] Horn, R. A. and Johnson, C. R. (1985). <i>Matrix Analysis<\/i>. Cambridge Univ. Press, Cambridge."},{"key":"21","unstructured":"[21] Manning, C. D. and Schutze, H. (1999). <i>Foundations of Statistical Natural Language Processing<\/i>. MIT Press, Cambridge, MA."},{"key":"22","unstructured":"[22] Meier, L., van de Geer, S. and B\u00fchlmann, P. (2007). The group lasso for logistic regression. Technical report, Mathematics Dept., Swiss Federal Institute of Technology Z\u00fcrich."},{"key":"24","unstructured":"[24] Ng, A. Y. (2004). Feature selection, <i>\u2113<\/i><sub>1<\/sub> vs. <i>\u2113<\/i><sub>2<\/sub> regularization, and rotational invariance. In <i>Proceedings of the Twenty-First International Conference on Machine Learning (ICML-04)<\/i>. Morgan Kaufmann, San Francisco, CA."},{"key":"25","doi-asserted-by":"publisher","unstructured":"[25] Obozinski, G., Wainwright, M. J. and Jordan, M. I. (2008). Union support recovery in high-dimensional multivariate regression. Technical report, Dept. Statistics, Univ. California, Berkeley.","DOI":"10.1214\/09-AOS776"},{"key":"26","doi-asserted-by":"crossref","unstructured":"[26] Ripley, B. D. (1981). <i>Spatial Statistics<\/i>. Wiley, New York.","DOI":"10.1002\/0471725218"},{"key":"27","doi-asserted-by":"crossref","unstructured":"[27] Rockafellar, G. (1970). <i>Convex Analysis<\/i>. Princeton Univ. Press, Princeton.","DOI":"10.1515\/9781400873173"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] Santhanam, N. P. and Wainwright, M. J. (2008). Information-theoretic limits of high-dimensional graphical model selection. In <i>International Symposium on Information Theory<\/i>. Toronto, Canada.","DOI":"10.1109\/ISIT.2008.4595367"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] Spirtes, P., Glymour, C. and Scheines, R. (2000). <i>Causation, Prediction and Search<\/i>. MIT Press, Cambridge, MA.","DOI":"10.7551\/mitpress\/1754.001.0001"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] Wainwright, M. J. and Jordan, M. I. (2003). Graphical models, exponential families, and variational inference. Technical Report 649, Dept. Statistics, Univ. California, Berkeley.","DOI":"10.1561\/2200000001"},{"key":"35","doi-asserted-by":"crossref","unstructured":"[35] Wainwright, M. J., Ravikumar, P. and Lafferty, J. D. (2007). High-dimensional graphical model selection using <i>\u2113<\/i><sub>1<\/sub>-regularized logistic regression. In <i>Advances in Neural Information Processing Systems<\/i> (B. Sch\u00f6lkopf, J. Platt and T. Hoffman, eds.) <b>19<\/b> 1465\u20131472. MIT Press, Cambridge, MA.","DOI":"10.7551\/mitpress\/7503.003.0188"},{"key":"36","doi-asserted-by":"crossref","unstructured":"[36] Welsh, D. J. A. (1993). <i>Complexity: Knots, Colourings, and Counting<\/i>. Cambridge Univ. Press, Cambridge.","DOI":"10.1017\/CBO9780511752506"}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1268056617","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,9]],"date-time":"2026-10-09T21:58:23Z","timestamp":1791583103000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-38\/issue-3\/High-dimensional-Ising-model-selection-using-%E2%84%931-regularized-logistic-regression\/10.1214\/09-AOS691.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,6,1]]},"references-count":39,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2010,6,1]]}},"URL":"https:\/\/doi.org\/10.1214\/09-aos691","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,6,1]]}}}