{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T21:10:05Z","timestamp":1751663405476,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"PLDI","license":[{"start":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T00:00:00Z","timestamp":1718841600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2024,6,20]]},"abstract":"<jats:p>Data analyses are usually designed to identify some property of the population from which the data are drawn, generalizing beyond the specific data sample. For this reason, data analyses are often designed in a way that guarantees that they produce a low generalization error. That is, they are designed so that the result of a data analysis run on a sample data does not differ too much from the result one would achieve by running the analysis over the entire population.<\/jats:p>\n          <jats:p>An adaptive data analysis can be seen as a process composed by multiple queries interrogating some data, where the choice of which query to run next may rely on the results of previous queries. The generalization error of each individual query\/analysis can be controlled by using an array of well-established statistical techniques. However, when queries are arbitrarily composed, the different errors can propagate through the chain of different queries and bring to a high generalization error. To address this issue, data analysts are designing several techniques that not only guarantee bounds on the generalization errors of single queries, but that also guarantee bounds on the generalization error of the composed analyses. The choice of which of these techniques to use, often depends on the chain of queries that an adaptive data analysis can generate.<\/jats:p>\n          <jats:p>\n            In this work, we consider adaptive data analyses implemented as while-like programs and we design a program analysis which can help with identifying which technique to use to control their generalization errors. More specifically, we formalize the intuitive notion of\n            <jats:italic toggle=\"yes\">adaptivity<\/jats:italic>\n            as a quantitative property of programs. We do this because the adaptivity level of a data analysis is a key measure to choose the right technique. Based on this definition, we design a program analysis for soundly approximating this quantity. The program analysis generates a representation of the data analysis as a weighted dependency graph, where the weight is an upper bound on the number of times each variable can be reached, and uses a path search strategy to guarantee an upper bound on the adaptivity. We implement our program analysis and show that it can help to analyze the adaptivity of several concrete data analyses with different adaptivity structures.\n          <\/jats:p>","DOI":"10.1145\/3656414","type":"journal-article","created":{"date-parts":[[2024,6,20]],"date-time":"2024-06-20T16:27:20Z","timestamp":1718900840000},"page":"914-938","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Program Analysis for Adaptive Data Analysis"],"prefix":"10.1145","volume":"8","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-0900-9910","authenticated-orcid":false,"given":"Jiawen","family":"Liu","sequence":"first","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1027-6556","authenticated-orcid":false,"given":"Weihao","family":"Qu","sequence":"additional","affiliation":[{"name":"Monmouth University, West Long Branch, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5235-7066","authenticated-orcid":false,"given":"Marco","family":"Gaboardi","sequence":"additional","affiliation":[{"name":"Boston University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0888-3093","authenticated-orcid":false,"given":"Deepak","family":"Garg","sequence":"additional","affiliation":[{"name":"MPI-SWS, MPI-SWS, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0323-5564","authenticated-orcid":false,"given":"Jonathan","family":"Ullman","sequence":"additional","affiliation":[{"name":"Northeastern University, Boston, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2024,6,20]]},"reference":[{"key":"e_1_3_1_2_2","doi-asserted-by":"publisher","DOI":"10.1145\/3473598"},{"key":"e_1_3_1_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3133904"},{"key":"e_1_3_1_4_2","doi-asserted-by":"crossref","unstructured":"Aws Albarghouthi and Samuel Vinitsky. 2019. Fairness-aware programming. In Proceedings of the Conference on Fairness Accountability and Transparency. 211\u2013219.","DOI":"10.1145\/3287560.3287588"},{"key":"e_1_3_1_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69166-2_15"},{"key":"e_1_3_1_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15769-1_8"},{"key":"e_1_3_1_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/ISSRE.2012.25"},{"key":"e_1_3_1_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/139669.140395"},{"key":"e_1_3_1_9_2","doi-asserted-by":"crossref","unstructured":"Manuel Barbosa Gilles Barthe Benjamin Gr\u00e9goire Adrien Koutsos and Pierre-Yves Strub. 2021. Mechanized Proofs of Adversarial Complexity and Application to Universal Composability. IACR Cryptol. ePrint Arch. 2021 (2021) 156. https:\/\/eprint.iacr.org\/2021\/156","DOI":"10.1145\/3460120.3484548"},{"key":"e_1_3_1_10_2","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897566"},{"key":"e_1_3_1_11_2","unstructured":"Sklearn Benchmark. 2023. https:\/\/github.com\/scikit-learn\/scikit-learn\/tree\/main\/examples"},{"key":"e_1_3_1_12_2","doi-asserted-by":"crossref","unstructured":"Gianfranco Bilardi and Keshav Pingali. 1996. A framework for generalized control dependence. In Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation. 291\u2013300.","DOI":"10.1145\/231379.231435"},{"key":"e_1_3_1_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585226"},{"key":"e_1_3_1_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2866575"},{"key":"e_1_3_1_15_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32304-2_19"},{"key":"e_1_3_1_16_2","doi-asserted-by":"publisher","DOI":"10.1145\/115372.115320"},{"key":"e_1_3_1_17_2","first-page":"625","volume-title":"Conference on Learning Theory, 2-5 July 2022, London, UK (Proceedings of Machine Learning Research, Vol. 178)","author":"Dagan Yuval","year":"2022","unstructured":"Yuval Dagan and Gil Kur. 2022. A bounded-noise mechanism for differential privacy. In Conference on Learning Theory, 2-5 July 2022, London, UK (Proceedings of Machine Learning Research, Vol. 178), Po-Ling Loh and Maxim Raginsky (Eds.). PMLR, 625\u2013661. https:\/\/proceedings.mlr.press\/v178\/dagan22a.html"},{"key":"e_1_3_1_18_2","doi-asserted-by":"publisher","DOI":"10.1145\/359636.359712"},{"key":"e_1_3_1_19_2","unstructured":"Cynthia Dwork Vitaly Feldman Moritz Hardt Toniann Pitassi Omer Reingold and Aaron Roth. 2015. Generalization in Adaptive Data Analysis and Holdout Reuse. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015 December 7-12 2015 Montreal Quebec Canada Corinna Cortes Neil D. Lawrence Daniel D. Lee Masashi Sugiyama and Roman Garnett (Eds.). 2350\u20132358. https:\/\/proceedings.neurips.cc\/paper\/2015\/hash\/bad5f33780c42f2588878a9d07405083-Abstract.html"},{"key":"e_1_3_1_20_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.aaa9375"},{"key":"e_1_3_1_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746580"},{"key":"e_1_3_1_22_2","first-page":"728","volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017 (Proceedings of Machine Learning Research, Vol. 65)","author":"Feldman Vitaly","year":"2017","unstructured":"Vitaly Feldman and Thomas Steinke. 2017. Generalization for Adaptively-chosen Estimators via Stable Median. In Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017 (Proceedings of Machine Learning Research, Vol. 65), Satyen Kale and Ohad Shamir (Eds.). PMLR, 728\u2013757. http:\/\/proceedings.mlr.press\/v65\/feldman17a.html"},{"key":"e_1_3_1_23_2","doi-asserted-by":"publisher","DOI":"10.1145\/24039.24041"},{"key":"e_1_3_1_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12736-1_15"},{"key":"e_1_3_1_25_2","doi-asserted-by":"publisher","DOI":"10.1511\/2014.111.460"},{"key":"e_1_3_1_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/SP.1982.10014"},{"key":"e_1_3_1_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/1542476.1542518"},{"key":"e_1_3_1_28_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806630"},{"key":"e_1_3_1_29_2","doi-asserted-by":"publisher","DOI":"10.1145\/1111542.1111552"},{"key":"e_1_3_1_30_2","doi-asserted-by":"publisher","DOI":"10.1145\/1111542.1111552"},{"key":"e_1_3_1_31_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.55"},{"key":"e_1_3_1_32_2","doi-asserted-by":"crossref","unstructured":"John PA Ioannidis. 2005. Why most published research findings are false. PLoS medicine 2 8 (2005) e124.","DOI":"10.1371\/journal.pmed.0020124"},{"key":"e_1_3_1_33_2","unstructured":"Kevin G. Jamieson. 2015. The Analysis of Adaptive Data Collection Methods for Machine Learning."},{"key":"e_1_3_1_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2020.31"},{"key":"e_1_3_1_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3452096"},{"key":"e_1_3_1_36_2","doi-asserted-by":"publisher","DOI":"10.1002\/stvr.364"},{"key":"e_1_3_1_37_2","doi-asserted-by":"publisher","DOI":"10.1109\/32.58766"},{"key":"e_1_3_1_38_2","doi-asserted-by":"publisher","unstructured":"Weihao Qu Jiawen Liu and Marco Gaboardi. 2024. Adaptfun: Program analysis for Adaptive analysis. https:\/\/doi.org\/10.5281\/zenodo.10806763 10.5281\/zenodo.10806763 Accessed: 2024-05-26.","DOI":"10.5281\/zenodo.10806763"},{"key":"e_1_3_1_39_2","first-page":"2830","volume-title":"The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy] (Proceedings of Machine Learning Research, Vol. 108)","author":"Rogers Ryan","year":"2020","unstructured":"Ryan Rogers, Aaron Roth, Adam D. Smith, Nathan Srebro, Om Thakkar, and Blake E. Woodworth. 2020. Guaranteed Validity for Empirical Approaches to Adaptive Data Analysis. In The 23rd International Conference on Artificial Intelligence and Statistics, AISTATS 2020, 26-28 August 2020, Online [Palermo, Sicily, Italy] (Proceedings of Machine Learning Research, Vol. 108), Silvia Chiappa and Roberto Calandra (Eds.). PMLR, 2830\u20132840. http:\/\/proceedings.mlr.press\/v108\/rogers20a.html"},{"key":"e_1_3_1_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-08867-9_50"},{"key":"e_1_3_1_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-016-9402-4"},{"key":"e_1_3_1_42_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10817-016-9402-4"},{"key":"e_1_3_1_43_2","first-page":"3437","volume-title":"Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria] (Proceedings of Machine Learning Research, Vol. 125)","author":"Steinke Thomas","year":"2020","unstructured":"Thomas Steinke and Lydia Zakynthinou. 2020. Reasoning About Generalization via Conditional Mutual Information. In Conference on Learning Theory, COLT 2020, 9-12 July 2020, Virtual Event [Graz, Austria] (Proceedings of Machine Learning Research, Vol. 125), Jacob D. Abernethy and Shivani Agarwal (Eds.). PMLR, 3437\u20133452. http:\/\/proceedings.mlr.press\/v125\/steinke20a.html"},{"key":"e_1_3_1_44_2","unstructured":"Jonathan R. Ullman Adam D. Smith Kobbi Nissim Uri Stemmer and Thomas Steinke. 2018. The Limits of Post-Selection Generalization. In Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018 NeurIPS 2018 December 3-8 2018 Montr\u00e9al Canada Samy Bengio Hanna M. Wallach Hugo Larochelle Kristen Grauman Nicol\u00f2 Cesa-Bianchi and Roman Garnett (Eds.). 6402\u20136411. https:\/\/proceedings.neurips.cc\/paper\/2018\/hash\/77ee3bc58ce560b86c2b59363281e914-Abstract.html"},{"key":"e_1_3_1_45_2","doi-asserted-by":"publisher","DOI":"10.1145\/3110254"},{"key":"e_1_3_1_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2018.00027"},{"key":"e_1_3_1_47_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23702-7_22"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656414","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3656414","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,4]],"date-time":"2025-07-04T20:41:41Z","timestamp":1751661701000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3656414"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,20]]},"references-count":46,"journal-issue":{"issue":"PLDI","published-print":{"date-parts":[[2024,6,20]]}},"alternative-id":["10.1145\/3656414"],"URL":"https:\/\/doi.org\/10.1145\/3656414","relation":{},"ISSN":["2475-1421"],"issn-type":[{"type":"electronic","value":"2475-1421"}],"subject":[],"published":{"date-parts":[[2024,6,20]]},"assertion":[{"value":"2024-06-20","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}