{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:42Z","timestamp":1750694802819,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":57,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["DMS-2022448, CCF-2006664, CCF-1565235, CCF-1955217"],"award-info":[{"award-number":["DMS-2022448, CCF-2006664, CCF-1565235, CCF-1955217"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Big George Fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"name":"FINTECH@CSAIL","award":[""],"award-info":[{"award-number":[""]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585117","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1643-1656","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Testing Distributional Assumptions of Learning Algorithms"],"prefix":"10.1145","author":[{"given":"Ronitt","family":"Rubinfeld","sequence":"first","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Arsen","family":"Vasilyan","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/127787.127840"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250863"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(03)00359-4"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591839"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9265-8"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12176"},{"key":"e_1_3_2_1_7_1","volume-title":"Testing Random Variables for Independence and Identity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001","author":"Batu Tugkan","year":"2001","unstructured":"Tugkan Batu , Lance Fortnow , Eldar Fischer , Ravi Kumar , Ronitt Rubinfeld , and Patrick White . 2001 . Testing Random Variables for Independence and Identity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001 , 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, 442\u2013451. Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, and Patrick White. 2001. Testing Random Variables for Independence and Identity. In 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, 14-17 October 2001, Las Vegas, Nevada, USA. IEEE Computer Society, 442\u2013451."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796548"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2015.512"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5179-6"},{"key":"e_1_3_2_1_11_1","volume-title":"Conference on Learning Theory. 5030\u20135061","author":"Blanc Guy","year":"2022","unstructured":"Guy Blanc , Jane Lange , Ali Malik , and Li-Yang Tan . 2022 . On the power of adaptivity in statistical adversaries . In Conference on Learning Theory. 5030\u20135061 . Guy Blanc, Jane Lange, Ali Malik, and Li-Yang Tan. 2022. On the power of adaptivity in statistical adversaries. In Conference on Learning Theory. 5030\u20135061."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225125"},{"key":"e_1_3_2_1_13_1","first-page":"2359","article-title":"Optimal hypothesis testing for high dimensional covariance matrices","volume":"19","author":"Tony Cai T","year":"2013","unstructured":"T Tony Cai and Zongming Ma . 2013 . Optimal hypothesis testing for high dimensional covariance matrices . Bernoulli , 19 , 5B (2013), 2359 \u2013 2388 . T Tony Cai and Zongming Ma. 2013. Optimal hypothesis testing for high dimensional covariance matrices. Bernoulli, 19, 5B (2013), 2359\u20132388.","journal-title":"Bernoulli"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Cl\u00e9ment L. Canonne. 2022. Topics and Techniques in Distribution Testing: A Biased but Representative Sample. https:\/\/ccanonne.github.io\/files\/misc\/main-survey-fnt.pdf \t\t\t\t  Cl\u00e9ment L. Canonne. 2022. Topics and Techniques in Distribution Testing: A Biased but Representative Sample. https:\/\/ccanonne.github.io\/files\/misc\/main-survey-fnt.pdf","DOI":"10.1561\/0100000114"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2017.29"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.126"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.34"},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (JMLR Workshop and Conference Proceedings","volume":"502","author":"Daniely Amit","year":"2015","unstructured":"Amit Daniely . 2015 . A PTAS for Agnostically Learning Halfspaces . In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (JMLR Workshop and Conference Proceedings , Vol. 40). JMLR.org, 484\u2013 502 . http:\/\/proceedings.mlr.press\/v40\/Daniely15.html Amit Daniely. 2015. A PTAS for Agnostically Learning Halfspaces. In Proceedings of The 28th Conference on Learning Theory, COLT 2015, Paris, France, July 3-6, 2015, Peter Gr\u00fcnwald, Elad Hazan, and Satyen Kale (Eds.) (JMLR Workshop and Conference Proceedings, Vol. 40). JMLR.org, 484\u2013502. http:\/\/proceedings.mlr.press\/v40\/Daniely15.html"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897520"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.68"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3450997"},{"key":"e_1_3_2_1_22_1","unstructured":"Ilias Diakonikolas Themis Gouleakis John Peebles and Eric Price. 2016. Collision-based Testers are Optimal for Uniformity and Closeness. Electron. Colloquium Comput. Complex. 178. \t\t\t\t  Ilias Diakonikolas Themis Gouleakis John Peebles and Eric Price. 2016. Collision-based Testers are Optimal for Uniformity and Closeness. Electron. Colloquium Comput. Complex. 178."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806763"},{"key":"e_1_3_2_1_24_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas , Daniel Kane , and Nikos Zarifis . 2020 . Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals . In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). Ilias Diakonikolas, Daniel Kane, and Nikos Zarifis. 2020. Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.)."},{"key":"e_1_3_2_1_25_1","first-page":"2640","volume-title":"Proceedings of Thirty Fourth Conference on Learning Theory. PMLR, 1522\u20131551","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas , Daniel M. Kane , Vasilis Kontonis , Christos Tzamos , and Nikos Zarifis . 2021 . Agnostic Proper Learning of Halfspaces under Gaussian Marginals . In Proceedings of Thirty Fourth Conference on Learning Theory. PMLR, 1522\u20131551 . https:\/\/proceedings.mlr.press\/v134\/diakonikolas21b.html ISSN: 2640 - 3498 Ilias Diakonikolas, Daniel M. Kane, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. 2021. Agnostic Proper Learning of Halfspaces under Gaussian Marginals. In Proceedings of Thirty Fourth Conference on Learning Theory. PMLR, 1522\u20131551. https:\/\/proceedings.mlr.press\/v134\/diakonikolas21b.html ISSN: 2640-3498"},{"key":"e_1_3_2_1_26_1","volume-title":"Conference on Learning Theory, COLT 2021","volume":"1584","author":"Diakonikolas Ilias","year":"2021","unstructured":"Ilias Diakonikolas , Daniel M. Kane , Thanasis Pittas , and Nikos Zarifis . 2021 . The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model . In Conference on Learning Theory, COLT 2021 , 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research , Vol. 134). PMLR, 1552\u2013 1584 . Ilias Diakonikolas, Daniel M. Kane, Thanasis Pittas, and Nikos Zarifis. 2021. The Optimality of Polynomial Regression for Agnostic Learning under Gaussian Marginals in the SQ Model. In Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, Mikhail Belkin and Samory Kpotufe (Eds.) (Proceedings of Machine Learning Research, Vol. 134). PMLR, 1552\u20131584."},{"key":"e_1_3_2_1_27_1","volume-title":"Non-Convex SGD Learns Halfspaces with Adversarial Label Noise. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Diakonikolas Ilias","year":"2020","unstructured":"Ilias Diakonikolas , Vasilis Kontonis , Christos Tzamos , and Nikos Zarifis . 2020 . Non-Convex SGD Learns Halfspaces with Adversarial Label Noise. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/d785bf9067f8af9e078b93cf26de2b54-Abstract.html Ilias Diakonikolas, Vasilis Kontonis, Christos Tzamos, and Nikos Zarifis. 2020. Non-Convex SGD Learns Halfspaces with Adversarial Label Noise. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). https:\/\/proceedings.neurips.cc\/paper\/2020\/hash\/d785bf9067f8af9e078b93cf26de2b54-Abstract.html"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187701"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/2789272.2912108"},{"key":"e_1_3_2_1_31_1","first-page":"2640","volume-title":"International Conference on Algorithmic Learning Theory. PMLR, 540\u2013559","author":"Feldman Vitaly","year":"2017","unstructured":"Vitaly Feldman , Pravesh Kothari , and Jan Vondr\u00e1k . 2017 . Tight Bounds on $\\ ell_1$ Approximation and Learning of Self-Bounding Functions . In International Conference on Algorithmic Learning Theory. PMLR, 540\u2013559 . http:\/\/proceedings.mlr.press\/v76\/feldman17a.html ISSN: 2640 - 3498 Vitaly Feldman, Pravesh Kothari, and Jan Vondr\u00e1k. 2017. Tight Bounds on $\\ ell_1$ Approximation and Learning of Self-Bounding Functions. In International Conference on Algorithmic Learning Theory. PMLR, 540\u2013559. http:\/\/proceedings.mlr.press\/v76\/feldman17a.html ISSN: 2640-3498"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.61"},{"volume-title":"Proceedings of the fourth annual workshop on Computational learning theory (COLT \u201991)","author":"Furst Merrick L.","key":"e_1_3_2_1_33_1","unstructured":"Merrick L. Furst , Jeffrey C. Jackson , and Sean W. Smith . 1991. Improved learning of AC^ 0 functions . In Proceedings of the fourth annual workshop on Computational learning theory (COLT \u201991) . Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 317\u2013325. isbn:978-1-55860-213-7 Merrick L. Furst, Jeffrey C. Jackson, and Sean W. Smith. 1991. Improved learning of AC^ 0 functions. In Proceedings of the fourth annual workshop on Computational learning theory (COLT \u201991). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. 317\u2013325. isbn:978-1-55860-213-7"},{"key":"e_1_3_2_1_34_1","volume-title":"Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020","author":"Goel Surbhi","year":"2020","unstructured":"Surbhi Goel , Aravind Gollakota , and Adam R. Klivans . 2020. Statistical-Query Lower Bounds via Functional Gradients . In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020 , NeurIPS 2020 , December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.). Surbhi Goel, Aravind Gollakota, and Adam R. Klivans. 2020. Statistical-Query Lower Bounds via Functional Gradients. In Advances in Neural Information Processing Systems 33: Annual Conference on Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, Hugo Larochelle, Marc\u2019Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan-Tien Lin (Eds.)."},{"key":"e_1_3_2_1_35_1","unstructured":"Oded Goldreich and Dana Ron. 2000. On Testing Expansion in Bounded-Degree Graphs. Electron. Colloquium Comput. Complex.. \t\t\t\t  Oded Goldreich and Dana Ron. 2000. On Testing Expansion in Bounded-Degree Graphs. Electron. Colloquium Comput. Complex.."},{"key":"e_1_3_2_1_36_1","unstructured":"Shafi Goldwasser Guy N. Rothblum Jonathan Shafer and Amir Yehudayoff. 2020. Interactive Proofs for Verifying Machine Learning. Electron. Colloquium Comput. Complex. 58. \t\t\t\t  Shafi Goldwasser Guy N. Rothblum Jonathan Shafer and Amir Yehudayoff. 2020. Interactive Proofs for Verifying Machine Learning. Electron. Colloquium Comput. Complex. 58."},{"volume-title":"Proceedings of the 55th annual ACM symposium on Theory of computing (STOC 2023 (to appear)). Association for Computing Machinery.","author":"Gollakota Aravind","key":"e_1_3_2_1_37_1","unstructured":"Aravind Gollakota , Adam R. Klivans , and Pravesh K. Kothari . 2023. A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity . In Proceedings of the 55th annual ACM symposium on Theory of computing (STOC 2023 (to appear)). Association for Computing Machinery. Aravind Gollakota, Adam R. Klivans, and Pravesh K. Kothari. 2023. A Moment-Matching Approach to Testable Learning and a New Characterization of Rademacher Complexity. In Proceedings of the 55th annual ACM symposium on Theory of computing (STOC 2023 (to appear)). Association for Computing Machinery."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15369-3_44"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.33"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1996.0040"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806764"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.27"},{"key":"e_1_3_2_1_45_1","volume-title":"List-decodable Linear Regression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019","author":"Karmalkar Sushrut","year":"2019","unstructured":"Sushrut Karmalkar , Adam R. Klivans , and Pravesh Kothari . 2019 . List-decodable Linear Regression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019 , NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada. 7423\u20137432. Sushrut Karmalkar, Adam R. Klivans, and Pravesh Kothari. 2019. List-decodable Linear Regression. In Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada. 7423\u20137432."},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_51"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181894"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.64"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63537"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/130385.130391"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2006.25"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.APPROX-RANDOM.2018.54"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.928987"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00058680"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Lloyd N Trefethen. 2019. Approximation Theory and Approximation Practice Extended Edition. SIAM. \t\t\t\t  Lloyd N Trefethen. 2019. Approximation Theory and Approximation Practice Extended Edition. SIAM.","DOI":"10.1137\/1.9781611975949"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.17"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Orlando FL USA","acronym":"STOC '23"},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585117","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585117","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585117","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585117"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":57,"alternative-id":["10.1145\/3564246.3585117","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585117","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}