{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,18]],"date-time":"2026-09-18T19:40:23Z","timestamp":1789760423039,"version":"4.0.1"},"reference-count":63,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","funder":[{"name":"NRF-AI Fellowship","award":["R-252-100-B13-281"],"award-info":[{"award-number":["R-252-100-B13-281"]}]},{"name":"Amazon Research Award"},{"DOI":"10.13039\/501100001403","name":"Indian Institute of Technology Kanpur","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100001403","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1751040"],"award-info":[{"award-number":["CCF-1751040"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-184908"],"award-info":[{"award-number":["CCF-184908"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["HDR:TRIPODS-1934884"],"award-info":[{"award-number":["HDR:TRIPODS-1934884"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2023,6,30]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We provide finite sample guarantees for the classical Chow\u2013Liu algorithm [Chow and Liu, IEEE Trans. Inform. Theory, 14 (1968), pp. 462\u2013467] to learn a tree-structured graphical model of a distribution. For a distribution [Formula: see text] on [Formula: see text] and a tree [Formula: see text] on [Formula: see text] nodes, we say [Formula: see text] is an [Formula: see text]-approximate tree for [Formula: see text] if there is a [Formula: see text]-structured distribution [Formula: see text] such that [Formula: see text] is at most [Formula: see text] more than the best possible tree-structured distribution for [Formula: see text]. We show that if [Formula: see text] itself is tree-structured, then the Chow\u2013Liu algorithm with the plug-in estimator for mutual information with [Formula: see text] independent and identically distributed samples outputs an [Formula: see text]-approximate tree for [Formula: see text] with constant probability. In contrast, for a general [Formula: see text] (which may not be tree-structured), [Formula: see text] samples are necessary to find an [Formula: see text]-approximate tree. Our upper bound is based on a new conditional independence tester that addresses an open problem posed by Canonne et al. [ Proceedings of the 50 th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 735\u2013748]: we prove that for three random variables [Formula: see text] each over [Formula: see text], testing if [Formula: see text] is 0 or [Formula: see text] is possible with [Formula: see text] samples. Finally, we show that for a specific tree [Formula: see text], with [Formula: see text] samples from a distribution [Formula: see text] over [Formula: see text], one can efficiently learn the closest [Formula: see text]-structured distribution in KL divergence by applying the add-1 estimator at each node.<\/jats:p>","DOI":"10.1137\/22m1489678","type":"journal-article","created":{"date-parts":[[2023,6,15]],"date-time":"2023-06-15T05:49:34Z","timestamp":1686808174000},"page":"761-793","source":"Crossref","is-referenced-by-count":3,"title":["Near-Optimal Learning of Tree-Structured Distributions by Chow and Liu"],"prefix":"10.1137","volume":"52","author":[{"given":"Arnab","family":"Bhattacharyya","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3300-1627","authenticated-orcid":true,"given":"Sutanu","family":"Gayen","sequence":"additional","affiliation":[{"name":"Department of Computer Science and Engineering, Indian Institute of Technology Kanpur, Kanpur, UP, 208016, India."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eric","family":"Price","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Texas at Austin, Austin, TX 78712 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5008-4527","authenticated-orcid":true,"given":"Vincent Y. F.","family":"Tan","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"N. V.","family":"Vinodchandran","sequence":"additional","affiliation":[{"name":"School of Computing, University of Nebraska-Lincoln, Lincoln, NE 68588-0115 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2023,6,15]]},"reference":[{"key":"ref1","first-page":"1743","volume":"7","author":"Abbeel P.","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"ref2","unstructured":"J. Acharya , \nC. Daskalakis , and \nG. Kamath , Optimal testing for properties of distributions, in Proceedings of Advances in Neural Information Processing Systems, 2015."},{"key":"ref3","unstructured":"A. Anandkumar , \nD. J. Hsu , \nF. Huang , and \nS. M. Kakade , Learning mixtures of tree graphical models, in Proceedings of Advances in Neural Information Processing Systems, 2012, pp. 1052\u20131060."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10019"},{"key":"ref5","doi-asserted-by":"crossref","unstructured":"T. Batu , \nL. Fortnow , \nE. Fischer , \nR. Kumar , \nR. Rubinfeld , and \nP. White , Testing random variables for independence and identity, in Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001.","DOI":"10.1109\/SFCS.2001.959920"},{"key":"ref6","unstructured":"A. Bhattacharyya , \nS. Gayen , \nK. S. Meel , and \nN. V. Vinodchandran , Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning, https:\/\/arxiv.org\/abs\/2002.05378, 2020."},{"key":"ref7","doi-asserted-by":"crossref","unstructured":"A. Bhattacharyya , \nS. Gayen , \nE. Price , and \nN. V. Vinodchandran , Near-optimal learning of tree-structured distributions by Chow-Liu, in Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2021, pp. 147\u2013160, https:\/\/doi.org\/10.1145\/3406325.3451066.","DOI":"10.1145\/3406325.3451066"},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"E. Boix-Adser\u00e0 , \nG. Bresler , and \nF. Koehler , Chow-Liu++: Optimal prediction-centric learning of tree Ising models, in Proceedings of the 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), 2022, pp. 417\u2013426, https:\/\/doi.org\/10.1109\/FOCS52979.2021.00049.","DOI":"10.1109\/FOCS52979.2021.00049"},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"G. Bresler , Efficiently learning Ising models on arbitrary graphs, in Proceedings of the 47th Annual ACM Symposium on Theory of Computing, 2015, pp. 771\u2013782.","DOI":"10.1145\/2746539.2746631"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1214\/19-AOS1808"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"G. Bresler  and \nM. Karzand , Minimax prediction in tree Ising models, in Proceedings of the IEEE International Symposium on Information Theory (ISIT), 2020, pp. 1325\u20131330, https:\/\/doi.org\/10.1109\/ISIT44484.2020.9174341.","DOI":"10.1109\/ISIT44484.2020.9174341"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1137\/100796029"},{"key":"ref13","doi-asserted-by":"crossref","unstructured":"J. Brustle , \nY. Cai , and \nC. Daskalakis , Multi-item mechanisms without item-independence: Learnability via robustness, in Proceedings of the 21st ACM Conference on Economics and Computation, 2020, pp. 715\u2013761.","DOI":"10.1145\/3391403.3399541"},{"key":"ref14","first-page":"63","author":"Canonne C. L.","year":"2015","journal-title":"Electronic Colloquium on Computational Complexity"},{"key":"ref15","unstructured":"C. L. Canonne ,\n                      private communication\n                      , 2020."},{"key":"ref16","doi-asserted-by":"crossref","unstructured":"C. L. Canonne , \nI. Diakonikolas , \nD. M. Kane , and \nA. Stewart , Testing conditional independence of discrete distributions, in Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, ACM, 2018, pp. 735\u2013748, https:\/\/doi.org\/10.1145\/3188745.3188756.","DOI":"10.1145\/3188745.3188756"},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2020.2971625"},{"key":"ref18","unstructured":"A. Chechetka  and \nC. Guestrin , Efficient principled learning of thin junction trees, in Proceedings of Advances in Neural Information Processing Systems, 2008, pp. 273\u2013280."},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"D. M. Chickering , Learning Bayesian networks is NP-complete, in Proceedings of Learning from Data: The 5th International Workshop on Artificial Intelligence and Statistics, \nD. Fisher  and \nH. Lenz , eds. 1995.","DOI":"10.1007\/978-1-4612-2404-4_12"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1973.1055013"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(97)00013-1"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007417612269"},{"key":"ref24","unstructured":"S. Dasgupta , Learning Polytrees, http:\/\/arxiv.org\/abs\/1301.6688, 2013."},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2932255"},{"key":"ref26","unstructured":"C. Daskalakis  and \nQ. Pan , Square Hellinger subadditivity for Bayesian networks and its applications to identity testing, in Proceedings of the 30th Conference on Learning Theory, \nS. Kale  and \nO. Shamir , eds. 2017."},{"key":"ref27","unstructured":"C. Daskalakis  and \nQ. Pan , Tree-Structured Ising Models Can Be Learned Efficiently, https:\/\/arxiv.org\/abs\/2010.14864, 2020."},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-5320-4"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1214\/20-EJS1721"},{"key":"ref30","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas , \nT. Gouleakis , \nD. M. Kane , \nJ. Peebles , and \nE. Price , Optimal Testing of Discrete Distributions with High Probability, https:\/\/arxiv.org\/abs\/2009.06540, 2021.","DOI":"10.1145\/3406325.3450997"},{"key":"ref31","unstructured":"I. Diakonikolas , \nT. Gouleakis , \nJ. Peebles , and \nE. Price , Sample-optimal identity testing with high probability, in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018."},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas  and \nD. M. Kane , A new approach for testing properties of discrete distributions, in Proceedings of the 57th Annual Symposium on Foundations of Computer Science, \nI. Dinur , ed. IEEE, 2016.","DOI":"10.1109\/FOCS.2016.78"},{"key":"ref33","unstructured":"S. Goel , Learning Ising and Potts models with latent variables, in Proceedings of the International Conference on Artificial Intelligence and Statistics, Proc. Mach. Learn. Res. 108, pp. 3557\u20133566."},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1017\/9781108135252"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-22670-0_9"},{"key":"ref36","doi-asserted-by":"crossref","unstructured":"K.U. H\u00f6ffgen , Learning and robust learning of product distributions, in Proceedings of the 6th Annual Conference on Computational Learning Theory, 1993, pp. 77\u201383.","DOI":"10.1145\/168304.168314"},{"key":"ref37","unstructured":"S. Kamath , \nA. Orlitsky , \nD. Pichapati , and \nA. T. Suresh , On learning distributions from their samples, in Proceedings of The 28th Conference on Learning Theory, 2015."},{"key":"ref38","unstructured":"D. R. Karger  and \nN. Srebro , Learning Markov networks: Maximum bounded tree-width graphs, in Proceedings of the 12th Annual Symposium on Discrete Algorithms, Washington, DC, \nS. R. Kosaraju , ed. 2001, pp. 392\u2013401."},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80062-5"},{"key":"ref40","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022615600103"},{"key":"ref41","doi-asserted-by":"crossref","unstructured":"A. R. Klivans  and \nR. Meka , Learning graphical models using multiplicative weights, in Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, \nC. Umans , ed. 2017.","DOI":"10.1109\/FOCS.2017.39"},{"key":"ref42","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"Koller D.","year":"2009"},{"key":"ref43","doi-asserted-by":"publisher","DOI":"10.1109\/18.910572"},{"key":"ref44","unstructured":"P. Laplace , Philosophical Essays on Probabilities, 1825."},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1093\/oso\/9780198522195.001.0001"},{"key":"ref46","first-page":"907","volume":"12","author":"Liu H.","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1613\/jair.914"},{"key":"ref48","unstructured":"M. Meila , An accelerated Chow and Liu algorithm: Fitting tree distributions to high-dimensional sparse data, in Proceedings of the 16th International Conference on Machine Learning, Bled, Slovenia, \nI. Bratko  and \nS. Dzeroski , eds. Morgan Kaufmann, Burlington, MA, 1999, pp. 249\u2013257."},{"key":"ref49","first-page":"1","volume":"1","author":"Meila M.","year":"2000","journal-title":"J. Mach. Learn. Res."},{"key":"ref50","unstructured":"M. Narasimhan  and \nJ. Bilmes , PAC-learning bounded tree-width graphical models, in Proceedings of the 20th Conference on Uncertainty in Artificial Intelligence, 2004, pp. 410\u2013417."},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOS2030"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1162\/089976603321780272"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1145\/2331042.2331052"},{"key":"ref54","doi-asserted-by":"publisher","DOI":"10.1016\/S0004-3702(02)00360-0"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2104513"},{"key":"ref56","doi-asserted-by":"crossref","unstructured":"A. Tandon , \nV. Y. Tan , and \nS. Zhu , Exact Asymptotics for Learning Tree-Structured Graphical Models with Side Information: Noiseless and Noisy Samples, preprint, arXiv:2005.04354, 2020.","DOI":"10.1109\/JSAIT.2020.3040552"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1145\/1968.1972"},{"key":"ref58","unstructured":"T. Verma  and \nJ. Pearl , Equivalence and synthesis of causal models, in Proceedings of the 6th Annual Conference on Uncertainty in Artificial Intelligence, Elsevier, New York, 1990, pp. 255\u2013270."},{"key":"ref59","first-page":"1829","volume":"7","author":"Wainwright M. J.","year":"2006","journal-title":"J. Mach. Learn. Res."},{"key":"ref60","doi-asserted-by":"crossref","DOI":"10.1561\/2200000001","volume-title":"Graphical Models, Exponential Families, and Variational Inference","author":"Wainwright M. J.","year":"2008"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1287\/12-SSY073"},{"key":"ref62","unstructured":"S. Wu , \nS. Sanghavi , and \nA. G. Dimakis , Sparse logistic regression learns all discrete pairwise graphical models, in Proceedings of Advances in Neural Information Processing Systems, 2019, pp. 8071\u20138081."},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2857763"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/22M1489678","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:19:41Z","timestamp":1787339981000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/22M1489678"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,15]]},"references-count":63,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,6,30]]}},"alternative-id":["10.1137\/22M1489678"],"URL":"https:\/\/doi.org\/10.1137\/22m1489678","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,15]]}}}