{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T16:05:20Z","timestamp":1774627520723,"version":"3.50.1"},"publisher-location":"New York, NY, USA","reference-count":37,"publisher":"ACM","funder":[{"name":"DFF","award":["1051-00106B"],"award-info":[{"award-number":["1051-00106B"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718180","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"2019-2030","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Almost Optimal PAC Learning for \ud835\udc58-Means"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0779-8962","authenticated-orcid":false,"given":"Vincent","family":"Cohen-Addad","sequence":"first","affiliation":[{"name":"Google Research, Grenoble, France"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3502-7559","authenticated-orcid":false,"given":"Silvio","family":"Lattanzi","sequence":"additional","affiliation":[{"name":"Google, Barcelona, Spain"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-9114-0661","authenticated-orcid":false,"given":"Chris","family":"Schwiegelshohn","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0144013"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263927"},{"key":"e_1_3_2_1_3_1","volume-title":"Bartlett","author":"Anthony Martin","year":"2002","unstructured":"Martin Anthony and Peter L. Bartlett. 2002. Neural Network Learning - Theoretical Foundations. Cambridge University Press. isbn:978-0-521-57353-5 http:\/\/www.cambridge.org\/gb\/knowledge\/isbn\/item1154061\/?site_locale=en_GB"},{"key":"e_1_3_2_1_4_1","unstructured":"Gautier Appert and Olivier Catoni. 2021. New bounds for k -means and information k -means. arXiv preprint arXiv:2101.05728."},{"key":"e_1_3_2_1_5_1","first-page":"1","article-title":"Fat-Shattering Dimension of k-fold Aggregations","volume":"25","author":"Attias Idan","year":"2024","unstructured":"Idan Attias and Aryeh Kontorovich. 2024. Fat-Shattering Dimension of k-fold Aggregations. Journal of Machine Learning Research, 25, 144 (2024), 1\u201329. http:\/\/jmlr.org\/papers\/v25\/21-1193.html","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00106"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.705560"},{"key":"e_1_3_2_1_8_1","first-page":"463","article-title":"Rademacher and Gaussian Complexities: Risk Bounds and Structural Results","volume":"3","author":"Bartlett Peter L.","year":"2002","unstructured":"Peter L. Bartlett and Shahar Mendelson. 2002. Rademacher and Gaussian Complexities: Risk Bounds and Structural Results. J. Mach. Learn. Res., 3 (2002), 463\u2013482. http:\/\/jmlr.org\/papers\/v3\/bartlett02a.html","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.913516"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.159"},{"key":"e_1_3_2_1_11_1","volume-title":"On Generalization Bounds for Projective Clustering. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023","author":"Bucarelli Maria Sofia","year":"2023","unstructured":"Maria Sofia Bucarelli, Matilde Fjelds\u00f8 Larsen, Chris Schwiegelshohn, and Mads Toftrup. 2023. On Generalization Bounds for Projective Clustering. In Advances in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine (Eds.). http:\/\/papers.nips.cc\/paper_files\/paper\/2023\/hash\/e30bf4765ae6b16a87fb4d7b0b3b3dec-Abstract-Conference.html"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.1994.395072"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC). 205\u2013214","author":"Kenneth","unstructured":"Kenneth L. Clarkson and David P. Woodruff. 2009. Numerical linear algebra in the streaming model. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC). 205\u2013214."},{"key":"e_1_3_2_1_14_1","volume-title":"Advances in Neural Information Processing Systems","author":"Clemen\u00e7con Stephan","year":"2011","unstructured":"Stephan Clemen\u00e7con. 2011. On U-processes and clustering performance. In Advances in Neural Information Processing Systems, J. Shawe-Taylor, R. Zemel, P. Bartlett, F. Pereira, and K.Q. Weinberger (Eds.). 24, Curran Associates, Inc.. https:\/\/proceedings.neurips.cc\/paper\/2011\/file\/a1d0c6e83f027327d8461063f4ac58a6-Paper.pdf"},{"key":"e_1_3_2_1_15_1","volume-title":"David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar.","author":"Cohen-Addad Vincent","year":"2022","unstructured":"Vincent Cohen-Addad, Kasper Green Larsen, David Saulpic, Chris Schwiegelshohn, and Omar Ali Sheikh-Omar. 2022. Improved Coresets for Euclidean k-Means. In NeurIPS. http:\/\/papers.nips.cc\/paper_files\/paper\/2022\/hash\/120c9ab5c58ba0fa9dd3a22ace1de245-Abstract-Conference.html"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00040"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00066"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/852"},{"key":"e_1_3_2_1_19_1","volume-title":"Foster and Alexander Rakhlin","author":"Dylan","year":"2019","unstructured":"Dylan J. Foster and Alexander Rakhlin. 2019. \u2113 _\u221e Vector Contraction for Rademacher Complexity. CoRR, abs\/1911.06468 (2019), arXiv:1911.06468. arxiv:1911.06468"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00118"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(92)90010-D"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.178042"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80062-5"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1214\/20-AOS2033"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.850705"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.340451"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188828"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316350"},{"key":"e_1_3_2_1_29_1","unstructured":"Pascal Massart. 2007. Concentration inequalities and model selection."},{"key":"e_1_3_2_1_30_1","volume-title":"Mitter","author":"Narayanan Hariharan","year":"2010","unstructured":"Hariharan Narayanan and Sanjoy K. Mitter. 2010. Sample Complexity of Testing the Manifold Hypothesis. In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010. Proceedings of a meeting held 6-9 December 2010, Vancouver, British Columbia, Canada, John D. Lafferty, Christopher K. I. Williams, John Shawe-Taylor, Richard S. Zemel, and Aron Culotta (Eds.). Curran Associates, Inc., 1786\u20131794. https:\/\/proceedings.neurips.cc\/paper\/2010\/hash\/8a1e808b55fde9455cb3d8857ed88389-Abstract.html"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316307"},{"key":"e_1_3_2_1_32_1","volume-title":"The","author":"Pisier Gilles","unstructured":"Gilles Pisier. 1999. The volume of convex bodies and Banach space geometry.. Cambridge Tracts in Mathematics. 94."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1214\/aos"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056481"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808710"},{"key":"e_1_3_2_1_37_1","volume-title":"Chervonenkis","author":"Vapnik Vladimir N.","year":"2013","unstructured":"Vladimir N. Vapnik and Alexey Y. Chervonenkis. 2013. On the uniform convergence of the frequencies of occurrence of events to their probabilities. Empirical Inference: Festschrift in Honor of Vladimir N. Vapnik, 7\u201312."}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","location":"Prague Czechia","acronym":"STOC '25","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718180","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:42:17Z","timestamp":1750693337000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718180"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":37,"alternative-id":["10.1145\/3717823.3718180","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718180","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}