{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T05:15:23Z","timestamp":1755839723139,"version":"3.44.0"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2024,5,29]],"date-time":"2024-05-29T00:00:00Z","timestamp":1716940800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF grant and the Industry-University Cooperative Research Center on Pervasive Personalized Intelligence","award":["CNS-1941892"],"award-info":[{"award-number":["CNS-1941892"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,5,29]]},"abstract":"<jats:p>Real-world data is often incomplete and contains missing values. To train accurate models over real-world datasets, users need to spend a substantial amount of time and resources imputing and finding proper values for missing data items. In this paper, we demonstrate that it is possible to learn accurate models directly from data with missing values for certain training data and target models. We propose a unified approach for checking the necessity of data imputation to learn accurate models across various widely-used machine learning paradigms. We build efficient algorithms with theoretical guarantees to check this necessity and return accurate models in cases where imputation is unnecessary. Our extensive experiments indicate that our proposed algorithms significantly reduce the amount of time and effort needed for data imputation without imposing considerable computational overhead.<\/jats:p>","DOI":"10.1145\/3654929","type":"journal-article","created":{"date-parts":[[2024,5,30]],"date-time":"2024-05-30T09:44:53Z","timestamp":1717062293000},"page":"1-25","source":"Crossref","is-referenced-by-count":2,"title":["Certain and Approximately Certain Models for Statistical Learning"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-0560-8926","authenticated-orcid":false,"given":"Cheng","family":"Zhen","sequence":"first","affiliation":[{"name":"Oregon State University, Corvallis, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0006-9673-9492","authenticated-orcid":false,"given":"Nischal","family":"Aryal","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-2213-6303","authenticated-orcid":false,"given":"Arash","family":"Termehchy","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, USA"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-5435-0598","authenticated-orcid":false,"given":"Amandeep Singh","family":"Chabada","sequence":"additional","affiliation":[{"name":"Oregon State University, Corvallis, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,5,30]]},"reference":[{"key":"e_1_2_1_1_1","unstructured":"2023. COVID-19 Reported Patient Impact and Hospital Capacity. https:\/\/catalog.data.gov\/dataset\/covid-19-reportedpatient-impact-and-hospital-capacity-by-state-timeseries-cf58c. Accessed on 01-01--2024."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1186\/s40537-021-00444--8"},{"key":"e_1_2_1_3_1","unstructured":"Peter Bodik Wei Hong Carlos Guestrin Sam Madden Mark Paskin and Romain Thibaux. 2004. Intel Berkley Research Lab Data. https:\/\/db.csail.mit.edu\/labdata\/labdata.html"},{"key":"e_1_2_1_4_1","volume-title":"Malware Dataset Generation and Evaluation. In 2020 IEEE 4th Conference on Information and Communication Technology (CICT). IEEE, 1--6.","author":"Borah Parthajit","year":"2020","unstructured":"Parthajit Borah, DK Bhattacharyya, and JK Kalita. 2020. Malware Dataset Generation and Evaluation. In 2020 IEEE 4th Conference on Information and Communication Technology (CICT). IEEE, 1--6."},{"key":"e_1_2_1_5_1","unstructured":"Yuri Burda Roger Grosse and Ruslan Salakhutdinov. 2016. Importance Weighted Autoencoders. arXiv:1509.00519 [cs.LG]"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589302"},{"key":"e_1_2_1_7_1","volume-title":"Kernel methods for deep learning. Advances in neural information processing systems 22","author":"Cho Youngmin","year":"2009","unstructured":"Youngmin Cho and Lawrence Saul. 2009. Kernel methods for deep learning. Advances in neural information processing systems 22 (2009)."},{"key":"e_1_2_1_8_1","volume-title":"Analysis and extension of arc-cosine kernels for large margin classification. arXiv preprint arXiv:1112.3712","author":"Cho Youngmin","year":"2011","unstructured":"Youngmin Cho and Lawrence K Saul. 2011. Analysis and extension of arc-cosine kernels for large margin classification. arXiv preprint arXiv:1112.3712 (2011)."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3385412.3385975"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICDT.2022.6"},{"key":"e_1_2_1_11_1","volume-title":"Sparse Linear regression with missing data. arXiv preprint arXiv:1503.08348","author":"Ganti Ravi","year":"2015","unstructured":"Ravi Ganti and Rebecca M Willett. 2015. Sparse Linear regression with missing data. arXiv preprint arXiv:1503.08348 (2015)."},{"key":"e_1_2_1_12_1","volume-title":"K Warmuth","author":"Gentile Claudio","year":"1998","unstructured":"Claudio Gentile and Manfred K. K Warmuth. 1998. Linear Hinge Loss and Average Margin. In Advances in Neural Information Processing Systems, M. Kearns, S. Solla, and D. Cohn (Eds.), Vol. 11. MIT Press."},{"key":"e_1_2_1_13_1","volume-title":"Detailed NFL Play-by-Play Data","author":"Horowitz Max","year":"2015","unstructured":"Max Horowitz. 2015. Detailed NFL Play-by-Play Data 2015. Kaggle. https:\/\/www.kaggle.com\/datasets\/maxhorowitz\/ nflplaybyplay2015"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","unstructured":"Isabelle Guyon Steve Gunn Asa Ben-Hur Gideon Dror. 2003. Gisette. https:\/\/doi.org\/10.24432\/C5HP5B","DOI":"10.24432\/C5HP5B"},{"key":"e_1_2_1_15_1","unstructured":"Aditya Kadiwal. 2021. Water Potability. Kaggle. https:\/\/www.kaggle.com\/datasets\/adityakadiwal\/water-potability"},{"key":"e_1_2_1_16_1","volume-title":"Xu Chu, Wentao Wu, and Ce Zhang.","author":"Bojan","year":"2020","unstructured":"Bojan Karla?, Peng Li, Renzhi Wu, Nezihe Merve G\u00fcrel, Xu Chu, Wentao Wu, and Ce Zhang. 2020. Nearest neighbor classifiers over incomplete information: From certain answers to certain predictions. arXiv preprint arXiv:2005.05117 (2020)."},{"key":"e_1_2_1_17_1","unstructured":"Sanjay Krishnan Michael J. Franklin Ken Goldberg and Eugene Wu. 2017. BoostClean: Automated Error Detection and Repair for Machine Learning. arXiv:1711.01299 [cs.DB]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/2994509.2994514"},{"key":"e_1_2_1_19_1","unstructured":"Krishnan Sanjay and Wang Jiannan and Wu Eugene and Franklin Michael J and Goldberg Ken. 2018. Cleaning for Data Science. https:\/\/activeclean.github.io\/"},{"key":"e_1_2_1_20_1","volume-title":"Wortman Vaughan (Eds.)","volume":"34","author":"Morvan Marine Le","year":"2021","unstructured":"Marine Le Morvan, Julie Josse, Erwan Scornet, and Gael Varoquaux. 2021. What's a good imputation to predict with missing values?. In Advances in Neural Information Processing Systems, M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (Eds.), Vol. 34. Curran Associates, Inc., 11530--11540. https:\/\/proceedings.neurips.cc\/ paper_files\/paper\/2021\/file\/5fe8fdc79ce292c39c5f209d734b7206-Paper.pdf"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"R.J.A. Little and D.B. Rubin. 2002. Statistical analysis with missing data. Wiley. http:\/\/books.google.com\/books?id= aYPwAAAAMAAJ","DOI":"10.1002\/9781119013563"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3450980.3450989"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research","volume":"4423","author":"Mattei Pierre-Alexandre","year":"2019","unstructured":"Pierre-Alexandre Mattei and Jes Frellsen. 2019. MIWAE: Deep Generative Modelling and Imputation of Incomplete Data Sets. In Proceedings of the 36th International Conference on Machine Learning (Proceedings of Machine Learning Research, Vol. 97), Kamalika Chaudhuri and Ruslan Salakhutdinov (Eds.). PMLR, 4413--4423. https:\/\/proceedings.mlr. press\/v97\/mattei19a.html"},{"key":"e_1_2_1_24_1","first-page":"24","article-title":"From Cleaning before ML to Cleaning for ML","volume":"44","author":"Neutatz Felix","year":"2021","unstructured":"Felix Neutatz, Binger Chen, Ziawasch Abedjan, and Eugene Wu. 2021. From Cleaning before ML to Cleaning for ML. IEEE Data Eng. Bull. 44, 1 (2021), 24--41.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389708"},{"key":"e_1_2_1_26_1","unstructured":"Michael Redmond. 2009. Communities and Crime. UCI Machine Learning Repository."},{"key":"e_1_2_1_27_1","unstructured":"Ricardo P Pinheiro Sidney M. L. Lima S\u00e9rgio M. M. Fernandes E. D. Q. Albuquerque S. Medeiros Danilo Souza T. Monteiro Petr\u00f4nio Lopes Rafael Lima Jemerson Oliveira Sth\u00e9fano Silva. 2019. REJAFADA. https:\/\/doi.org\/10.24432\/ C5HG8D"},{"key":"e_1_2_1_28_1","volume-title":"Inference and missing data. Biometrika 63, 3 (12","author":"DONALD B. RUBIN.","year":"1976","unstructured":"DONALD B. RUBIN. 1976. Inference and missing data. Biometrika 63, 3 (12 1976), 581--592. https:\/\/doi.org\/10.1093\/ biomet\/63.3.581 arXiv:https:\/\/academic.oup.com\/biomet\/article-pdf\/63\/3\/581\/756166\/63--3--581.pdf"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/17.6.520"},{"volume-title":"Flexible imputation of missing data","author":"Buuren Stef Van","key":"e_1_2_1_30_1","unstructured":"Stef Van Buuren. 2018. Flexible imputation of missing data. CRC press."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2641190.2641198"},{"key":"e_1_2_1_32_1","unstructured":"Saverio Vito. 2016. Air Quality. UCI Machine Learning Repository."},{"key":"e_1_2_1_33_1","unstructured":"Yining Wang and Aarti Singh. 2015. Column subset selection with missing data via active sampling. In Artificial Intelligence and Statistics. PMLR 1033--1041."},{"key":"e_1_2_1_34_1","unstructured":"William Wolberg. 1992. Breast Cancer Wisconsin (Original). UCI Machine Learning Repository."},{"key":"e_1_2_1_35_1","volume-title":"Certain and Approximately Certain Models for Statistical Learning. arXiv preprint arXiv:2402.17926","author":"Zhen Cheng","year":"2024","unstructured":"Cheng Zhen, Nischal Aryal, Arash Termehchy, and Amandeep Singh Chabada. 2024. Certain and Approximately Certain Models for Statistical Learning. arXiv preprint arXiv:2402.17926 (2024)."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654929","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3654929","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T14:41:58Z","timestamp":1755787318000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3654929"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5,29]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5,29]]}},"alternative-id":["10.1145\/3654929"],"URL":"https:\/\/doi.org\/10.1145\/3654929","relation":{},"ISSN":["2836-6573"],"issn-type":[{"type":"electronic","value":"2836-6573"}],"subject":[],"published":{"date-parts":[[2024,5,29]]}}}