{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,24]],"date-time":"2025-12-24T06:27:07Z","timestamp":1766557627795,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":58,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3451074","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"161-168","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Learning Ising models from one or multiple samples"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7940-4002","authenticated-orcid":false,"given":"Yuval","family":"Dagan","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Constantinos","family":"Daskalakis","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Nishanth","family":"Dikkala","sequence":"additional","affiliation":[{"name":"Google, USA \/ Massachusetts Institute of Technology, USA"}]},{"given":"Anthimos Vardis","family":"Kandiros","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-EJP280"},{"key":"e_1_3_2_1_2_1","volume-title":"Spatial econometrics. A companion to theoretical econometrics, 310330","author":"Anselin Luc","year":"2001","unstructured":"Luc Anselin. 2001. Spatial econometrics. A companion to theoretical econometrics, 310330, 2001."},{"volume-title":"Spatial econometrics: methods and models. 4","author":"Anselin Luc","key":"e_1_3_2_1_3_1","unstructured":"Luc Anselin. 2013. Spatial econometrics: methods and models. 4, Springer Science & Business Media."},{"volume-title":"New directions in spatial econometrics","author":"Anselin Luc","key":"e_1_3_2_1_4_1","unstructured":"Luc Anselin and Raymond Florax. 2012. New directions in spatial econometrics. Springer Science & Business Media."},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.3150\/09-BEJ191"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1162\/003355300554971"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2517-6161.1974.tb00999.x"},{"key":"e_1_3_2_1_8_1","first-page":"3","article-title":"Statistical analysis of non-lattice data","volume":"24","author":"Besag Julian","year":"1975","unstructured":"Julian Besag. 1975. Statistical analysis of non-lattice data. Journal of the Royal Statistical Society: Series D (The Statistician), 24, 3, 1975. Pages 179\u2013195.","journal-title":"Journal of the Royal Statistical Society: Series D (The Statistician)"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.3150\/16-BEJ886"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jeconom.2008.12.021"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746631"},{"key":"e_1_3_2_1_12_1","volume-title":"Optimal single sample tests for structured versus unstructured network data. arXiv preprint arXiv:1802.06186","author":"Bresler Guy","year":"2018","unstructured":"Guy Bresler and Dheeraj Nagaraj. 2018. Optimal single sample tests for structured versus unstructured network data. arXiv preprint arXiv:1802.06186, 2018."},{"key":"e_1_3_2_1_13_1","volume-title":"Concentration inequalities with exchangeable pairs (Ph. D. thesis). arXiv preprint math\/0507526","author":"Chatterjee Sourav","year":"2005","unstructured":"Sourav Chatterjee. 2005. Concentration inequalities with exchangeable pairs (Ph. D. thesis). arXiv preprint math\/0507526, 2005."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053607000000109"},{"key":"e_1_3_2_1_15_1","volume-title":"How bad is worst-case data if you know where it comes from? arXiv, abs\/1911.03605","author":"Chen Justin Y.","year":"2019","unstructured":"Justin Y. Chen, Gregory Valiant, and Paul Valiant. 2019. How bad is worst-case data if you know where it comes from? arXiv, abs\/1911.03605, 2019."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1968.1054142"},{"key":"e_1_3_2_1_17_1","volume-title":"Social contagion theory: examining dynamic social networks and human behavior. Statistics in medicine, 32, 4","author":"Christakis Nicholas A","year":"2013","unstructured":"Nicholas A Christakis and James H Fowler. 2013. Social contagion theory: examining dynamic social networks and human behavior. Statistics in medicine, 32, 4, 2013. Pages 556\u2013577."},{"key":"e_1_3_2_1_18_1","volume-title":"Condition. In Conference on Learning Theory. Pages 914\u2013928","author":"Dagan Yuval","year":"2019","unstructured":"Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Siddhartha Jayanti. 2019. Learning from Weakly Dependent Data under Dobrushin\u2019s Condition. In Conference on Learning Theory. Pages 914\u2013928."},{"key":"e_1_3_2_1_19_1","volume-title":"Estimating ising models from one sample. arXiv preprint arXiv:2004.09370","author":"Dagan Yuval","year":"2020","unstructured":"Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, and Anthimos Vardis Kandiros. 2020. Estimating ising models from one sample. arXiv preprint arXiv:2004.09370, 2020."},{"key":"e_1_3_2_1_20_1","unstructured":"Constantinos Daskalakis Nishanth Dikkala and Gautam Kamath. 2017. Concentration of multilinear functions of the Ising model with applications to network data. In Advances in Neural Information Processing Systems. Pages 12\u201323."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316362"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-009-0246-2"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01011153"},{"key":"e_1_3_2_1_24_1","volume-title":"The role of information and social interactions in retirement plan decisions: Evidence from a randomized experiment. The Quarterly journal of economics, 118, 3","author":"Duflo Esther","year":"2003","unstructured":"Esther Duflo and Emmanuel Saez. 2003. The role of information and social interactions in retirement plan decisions: Evidence from a randomized experiment. The Quarterly journal of economics, 118, 3, 2003. Pages 815\u2013842."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.2307\/2951493"},{"key":"e_1_3_2_1_26_1","unstructured":"Joseph Felsenstein. 2004. Inferring Phylogenies. Sinauer Associates Sunderland."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2002.806131"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the International Congress of Mathematicians. American Mathematical Society. Pages 1496\u20131517","author":"Geman Stuart","year":"1986","unstructured":"Stuart Geman and Christine Graffigne. 1986. Markov Random Field Image Models and their Applications to Computer Vision. In Proceedings of the International Congress of Mathematicians. American Mathematical Society. Pages 1496\u20131517."},{"key":"e_1_3_2_1_29_1","volume-title":"Concentration inequalities for polynomials of contracting Ising models. arXiv preprint arXiv:1706.00121","author":"Gheissari Reza","year":"2017","unstructured":"Reza Gheissari, Eyal Lubetzky, and Yuval Peres. 2017. Concentration inequalities for polynomials of contracting Ising models. arXiv preprint arXiv:1706.00121, 2017."},{"key":"e_1_3_2_1_30_1","volume-title":"Joint estimation of parameters in Ising model. arXiv preprint arXiv:1801.06570","author":"Ghosal Promit","year":"2018","unstructured":"Promit Ghosal and Sumit Mukherjee. 2018. Joint estimation of parameters in Ising model. arXiv preprint arXiv:1801.06570, 2018."},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.2307\/2946686"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1214\/19-EJP338"},{"key":"e_1_3_2_1_33_1","unstructured":"Linus Hamilton Frederic Koehler and Ankur Moitra. 2017. Information theoretic properties of Markov random fields and their algorithmic applications. In Advances in Neural Information Processing Systems. Pages 2463\u20132472."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02980577"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.39"},{"volume-title":"Convexity and Concentration","author":"Kontorovich Aryeh","key":"e_1_3_2_1_36_1","unstructured":"Aryeh Kontorovich and Maxim Raginsky. 2017. Concentration of measure without independence: a unified approach via the martingale method. In Convexity and Concentration. Springer. Pages 183\u2013210."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOP384"},{"key":"e_1_3_2_1_38_1","unstructured":"Vitaly Kuznetsov and Mehryar Mohri. 2015. Learning theory and algorithms for forecasting non-stationary time series. In Advances in neural information processing systems. Pages 541\u2013549."},{"volume-title":"Graphical models. 17","author":"Lauritzen Steffen L","key":"e_1_3_2_1_39_1","unstructured":"Steffen L Lauritzen. 1996. Graphical models. 17, Clarendon Press."},{"key":"e_1_3_2_1_40_1","volume-title":"An introduction to spatial econometrics. Revue d'\u00e9conomie industrielle, 123","author":"LeSage James P","year":"2008","unstructured":"James P LeSage. 2008. An introduction to spatial econometrics. Revue d'\u00e9conomie industrielle, 123, 2008. Pages 19\u201344."},{"key":"e_1_3_2_1_41_1","first-page":"1","article-title":"Stability and generalization in structured prediction","volume":"17","author":"London Ben","year":"2016","unstructured":"Ben London, Bert Huang, and Lise Getoor. 2016. Stability and generalization in structured prediction. The Journal of Machine Learning Research, 17, 1, 2016. Pages 7808\u20137859.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_3_2_1_42_1","volume-title":"International Conference on Machine Learning. Pages 828\u2013836","author":"London Ben","year":"2013","unstructured":"Ben London, Bert Huang, Ben Taskar, and Lise Getoor. 2013. Collective stability in structured prediction: Generalization from one example. In International Conference on Machine Learning. Pages 828\u2013836."},{"key":"e_1_3_2_1_43_1","volume-title":"Identification of endogenous social effects: The reflection problem. The review of economic studies, 60, 3","author":"Manski Charles F","year":"1993","unstructured":"Charles F Manski. 1993. Identification of endogenous social effects: The reflection problem. The review of economic studies, 60, 3, 1993. Pages 531\u2013542."},{"key":"e_1_3_2_1_44_1","volume-title":"McDonald and Cosma Rohilla Shalizi","author":"Daniel","year":"2017","unstructured":"Daniel J. McDonald and Cosma Rohilla Shalizi. 2017. Rademacher complexity of stationary sequences. arXiv preprint arXiv:1106.0730, 2017."},{"key":"e_1_3_2_1_45_1","unstructured":"Mehryar Mohri and Afshin Rostamizadeh. 2009. Rademacher complexity bounds for non-iid processes. In Advances in Neural Information Processing Systems. Pages 1097\u20131104."},{"key":"e_1_3_2_1_46_1","article-title":"Stability bounds for stationary \\varphi -mixing and \\beta -mixing processes","volume":"11","author":"Mohri Mehryar","year":"2010","unstructured":"Mehryar Mohri and Afshin Rostamizadeh. 2010. Stability bounds for stationary \\varphi -mixing and \\beta -mixing processes. Journal of Machine Learning Research, 11, Feb, 2010. Pages 789\u2013814.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/GrC.2010.102"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1214\/09-AOS691"},{"key":"e_1_3_2_1_49_1","volume-title":"Peer effects with random assignment: Results for Dartmouth roommates. The Quarterly journal of economics, 116, 2","author":"Sacerdote Bruce","year":"2001","unstructured":"Bruce Sacerdote. 2001. Peer effects with random assignment: Results for Dartmouth roommates. The Quarterly journal of economics, 116, 2, 2001. Pages 681\u2013704."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2012.2191659"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1214\/13-AOP888"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02096629"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jhealeco.2008.05.003"},{"key":"e_1_3_2_1_54_1","unstructured":"Marc Vuffray Sidhant Misra Andrey Lokhov and Michael Chertkov. 2016. Interaction screening: Efficient and sample-optimal learning of Ising models. In Advances in Neural Information Processing Systems. Pages 2595\u20132603."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000001"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20073"},{"key":"e_1_3_2_1_57_1","unstructured":"Shanshan Wu Sujay Sanghavi and Alexandros G Dimakis. 2019. Sparse logistic regression learns all discrete pairwise graphical models. In Advances in Neural Information Processing Systems. Pages 8069\u20138079."},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988849"}],"event":{"name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Italy","acronym":"STOC '21"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451074","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3451074","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T21:24:53Z","timestamp":1750195493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3451074"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":58,"alternative-id":["10.1145\/3406325.3451074","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3451074","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}