{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,17]],"date-time":"2026-04-17T14:32:52Z","timestamp":1776436372817,"version":"3.51.2"},"reference-count":51,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T00:00:00Z","timestamp":1569369600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T00:00:00Z","timestamp":1569369600000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1350888"],"award-info":[{"award-number":["CCF-1350888"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2020,6]]},"DOI":"10.1007\/s00454-019-00134-6","type":"journal-article","created":{"date-parts":[[2019,9,25]],"date-time":"2019-09-25T18:04:27Z","timestamp":1569434667000},"page":"867-887","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":14,"title":["Near-Optimal Coresets of Kernel Density Estimates"],"prefix":"10.1007","volume":"63","author":[{"given":"Jeff M.","family":"Phillips","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4933-7299","authenticated-orcid":false,"given":"Wai Ming","family":"Tai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,9,25]]},"reference":[{"key":"134_CR1","first-page":"43","volume":"17","author":"E Arias-Castro","year":"2016","unstructured":"Arias-Castro, E., Mason, D., Pelletier, B.: On the estimation of the gradient lines of a density and the consistency of the mean-shift algorithm. J. Mach. Learn. Res. 17, 43 (2016)","journal-title":"J. Mach. Learn. Res."},{"issue":"3","key":"134_CR2","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1090\/S0002-9947-1950-0051437-7","volume":"68","author":"N Aronszajn","year":"1950","unstructured":"Aronszajn, N.: Theory of reproducing kernels. Trans. Am. Math. Soc. 68(3), 337\u2013404 (1950)","journal-title":"Trans. Am. Math. Soc."},{"key":"134_CR3","unstructured":"Bach, F., Lacoste-Julien, S., Obozinski, G.: On the equivalence between herding and conditional gradient algorithms. In: Proceedings of the 29th International Coference on International Conference on Machine Learning (ICML\u201912), pp. 1355\u20131362. Omnipress (2012)"},{"issue":"4","key":"134_CR4","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1002\/(SICI)1098-2418(199807)12:4<351::AID-RSA3>3.0.CO;2-S","volume":"12","author":"W Banaszczyk","year":"1998","unstructured":"Banaszczyk, W.: Balancing vectors and Gaussian measures of $$n$$-dimensional convex bodies. Random Struct. Algorithms 12(4), 351\u2013360 (1998)","journal-title":"Random Struct. Algorithms"},{"key":"134_CR5","doi-asserted-by":"crossref","unstructured":"Bansal, N., Dadush, D., Garg, S., Lovett, S.: The Gram\u2013Schmidt walk: a cure for the Banaszczyk blues (STOC\u201918). In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 587\u2013597. ACM, New York (2018)","DOI":"10.1145\/3188745.3188850"},{"key":"134_CR6","first-page":"4","volume":"1","author":"JL Bentley","year":"1980","unstructured":"Bentley, J.L., Saxe, J.B.: Decomposable searching problems I: static-to-dynamic transformations. J. Algorithms 1, 4 (1980)","journal-title":"J. Algorithms"},{"issue":"1","key":"134_CR7","doi-asserted-by":"publisher","first-page":"288","DOI":"10.3150\/15-BEJ744","volume":"23","author":"O Bobrowski","year":"2017","unstructured":"Bobrowski, O., Mukherjee, S., Taylor, J.E.: Topological consistency via kernel estimation. Bernoulli 23(1), 288\u2013328 (2017)","journal-title":"Bernoulli"},{"key":"134_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511626371","volume-title":"The Discrepancy Method","author":"B Chazelle","year":"2000","unstructured":"Chazelle, B.: The Discrepancy Method. Cambridge University Press, Cambridge (2000)"},{"issue":"3","key":"134_CR9","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1006\/jagm.1996.0060","volume":"21","author":"B Chazelle","year":"1996","unstructured":"Chazelle, B., Matou\u0161ek, J.: On linear-time deterministic algorithms for optimization problems in fixed dimensions. J. Algorithms 21(3), 579\u2013597 (1996)","journal-title":"J. Algorithms"},{"key":"134_CR10","unstructured":"Chen, Y., Welling, M., Smola, A.: Super-samples from kernel hearding. In: Proceedings of the 26th Conference on Uncertainty in Artificial Intelligence (UAI\u201910), pp. 109\u2013116. AUAI Press, Arlington (2010)"},{"issue":"6","key":"134_CR11","first-page":"63","volume":"4","author":"K Clarkson","year":"2010","unstructured":"Clarkson, K.: Coresets, sparse greedy approximation, and the Frank\u2013Wolfe algorithm. ACM Trans. Algorithms 4(6), 63 (2010)","journal-title":"ACM Trans. Algorithms"},{"issue":"5","key":"134_CR12","doi-asserted-by":"publisher","first-page":"1310","DOI":"10.1109\/TSP.2016.2628353","volume":"65","author":"EC Cort\u00e9s","year":"2016","unstructured":"Cort\u00e9s, E.C., Scott, C.: Sparse approximation of a kernel mean. IEEE Trans. Signal Process. 65(5), 1310\u20131323 (2016)","journal-title":"IEEE Trans. Signal Process."},{"key":"134_CR13","volume-title":"Nonparametric Density Estimation: The $$L_1$$ View. Wiley Series in Probability and Mathematical Statistics: Tracts on Probability and Statistics","author":"L Devroye","year":"1985","unstructured":"Devroye, L., Gy\u00f6rfi, L.: Nonparametric Density Estimation: The $$L_1$$ View. Wiley Series in Probability and Mathematical Statistics: Tracts on Probability and Statistics. Wiley, New York (1985)"},{"key":"134_CR14","first-page":"2153","volume":"6","author":"P Drineas","year":"2005","unstructured":"Drineas, P., Mahoney, M.W.: On the Nystr\u00f6m method for approximating a Gram matrix for improved kernel-based learning. J. Mach. Learn. Res. 6, 2153\u20132175 (2005)","journal-title":"J. Mach. Learn. Res."},{"issue":"5","key":"134_CR15","doi-asserted-by":"publisher","first-page":"473","DOI":"10.1137\/0318035","volume":"18","author":"JC Dunn","year":"1980","unstructured":"Dunn, J.C.: Convergence rates for conditional gradient sequences generated by implicit step length rules. SIAM J. Control Optim. 18(5), 473\u2013489 (1980)","journal-title":"SIAM J. Control Optim."},{"key":"134_CR16","volume-title":"Local Polynomial Modelling and Its Applications. Monographs on Statistics and Applied Probability","author":"J Fan","year":"1996","unstructured":"Fan, J., Gijbels, I.: Local Polynomial Modelling and Its Applications. Monographs on Statistics and Applied Probability, vol. 66. Chapman & Hall, London (1996)"},{"issue":"6","key":"134_CR17","doi-asserted-by":"publisher","first-page":"2301","DOI":"10.1214\/14-AOS1252","volume":"42","author":"BT Fasy","year":"2014","unstructured":"Fasy, B.T., Lecci, F., Rinaldo, A., Wasserman, L., Balakrishnan, S., Singh, A.: Confidence sets for persistence diagrams. Ann. Stat. 42(6), 2301\u20132339 (2014)","journal-title":"Ann. Stat."},{"issue":"1\u20132","key":"134_CR18","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10107-014-0841-6","volume":"155","author":"RM Freund","year":"2016","unstructured":"Freund, R.M., Grigas, P.: New analysis and results for the Frank\u2013Wolfe method. Math. Program. 155(1\u20132), 199\u2013230 (2016)","journal-title":"Math. Program."},{"key":"134_CR19","doi-asserted-by":"crossref","unstructured":"G\u00e4rtner, B., Jaggi, M.: Coresets for polytope distance. In: Proceedings of the 25th Annual Symposium on Computational Geometry (SCG\u201909), pp. 33\u201342. ACM, New York (2009)","DOI":"10.1145\/1542362.1542370"},{"key":"134_CR20","unstructured":"Glaun\u00e8s, J.: Transport par diff\u00e9omorphismes de points, de mesures et de courants pour la comparaison de formes et l\u2019anatomie num\u00e9rique. PhD thesis, Universit\u00e9 Paris 13 (2005)"},{"issue":"2\u20133","key":"134_CR21","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0304-3975(85)90224-5","volume":"38","author":"TF Gonzalez","year":"1985","unstructured":"Gonzalez, T.F.: Clustering to minimize the maximum intercluster distance. Theoret. Comput. Sci. 38(2\u20133), 293\u2013306 (1985)","journal-title":"Theoret. Comput. Sci."},{"key":"134_CR22","first-page":"723","volume":"13","author":"A Gretton","year":"2012","unstructured":"Gretton, A., Borgwardt, K.M., Rasch, M.J., Sch\u00f6lkopf, B., Smola, A.: A kernel two-sample test. J. Mach. Learn. Res. 13, 723\u2013773 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"134_CR23","unstructured":"Harvey, N., Samadi, S.: Near-optimal herding. In: Proceedings of the 27th Conference on Learning Theory vol. 35, pp. 1165\u20131183 (2014)"},{"key":"134_CR24","unstructured":"Hein, M., Bousquet, O.: Hilbertian metrics and positive definite kernels on probability measures. In: Proceedings of the International Conference on Artificial Intelligence and Statistics, pp. 136\u2013143 (2005)"},{"issue":"3","key":"134_CR25","doi-asserted-by":"publisher","first-page":"1171","DOI":"10.1214\/009053607000000677","volume":"36","author":"T Hofmann","year":"2008","unstructured":"Hofmann, T., Sch\u00f6lkopf, B., Smola, A.J.: Kernel methods in machine learning. Ann. Stat. 36(3), 1171\u20131220 (2008)","journal-title":"Ann. Stat."},{"key":"134_CR26","unstructured":"Jaggi, M.: Revisiting Frank\u2013Wolfe: projection-free sparse convex optimization. In: Proceedings of the 30th International Conference on Machine Learning, vol 28(1), pp. 427\u2013435 (2013)"},{"key":"134_CR27","unstructured":"Jaggi, M., Lacoste-Julien, S.: On the global linear convergence of Frank\u2013Wolfe optimization variants. In: Advances in Neural Information Processing Systems, vol. 28 (2015)"},{"key":"134_CR28","doi-asserted-by":"crossref","unstructured":"Joshi, S., Kommaraji, R.V., Phillips, J.M., Venkatasubramanian, S.: Comparing distributions and shapes using the kernel distance. In: Proceedings of the 27th Annual Symposium on Computational Geometry (SoCG\u201911), pp. 47\u201356. ACM, New York (2011)","DOI":"10.1145\/1998196.1998204"},{"key":"134_CR29","unstructured":"Lacoste-Julien, S., Lindsten, F., Bach, F.: Sequential kernel herding: Frank\u2013Wolfe optimization for particle filtering. In: Proceedings of the 18th International Conference on Artificial Intelligence and Statistics, pp. 544\u2013552 (2015)"},{"issue":"3","key":"134_CR30","doi-asserted-by":"publisher","first-page":"516","DOI":"10.1006\/jcss.2000.1741","volume":"62","author":"Y Li","year":"2001","unstructured":"Li, Y., Long, P.M., Srinivasan, A.: Improved bounds on the samples complexity of learning. J. Comput. Syst. Sci. 62(3), 516\u2013527 (2001)","journal-title":"J. Comput. Syst. Sci."},{"key":"134_CR31","unstructured":"Lopaz-Paz, D., Muandet, K., Sch\u00f6lkopf, B., Tolstikhin, I.: Towards a learning theory of cause-effect inference. In: Proceedings of the 32nd International Conference on Machine Learning, vol. 37, pp. 1452\u20131461 (2015)"},{"key":"134_CR32","volume-title":"Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics","author":"J Matou\u0161ek","year":"2010","unstructured":"Matou\u0161ek, J.: Geometric Discrepancy: An Illustrated Guide. Algorithms and Combinatorics, vol. 18, 2nd edn. Springer, Berlin (2010)","edition":"2"},{"key":"134_CR33","doi-asserted-by":"publisher","unstructured":"Matou\u0161ek, J., Nikolov, A., Talwar, K.: Factorization norms and hereditary discrepancy. Int. Math. Res. Not. https:\/\/doi.org\/10.1093\/imrn\/rny033","DOI":"10.1093\/imrn\/rny033"},{"key":"134_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000060","volume":"10","author":"K Muandet","year":"2017","unstructured":"Muandet, K., Fukumizu, K., Sriperumbudur, B.K., Sch\u00f6lkopf, B.: Kernel mean embedding of distributions: a review and beyond. Found. Trends Mach. Learn. 10, 1\u2013141 (2017)","journal-title":"Found. Trends Mach. Learn."},{"issue":"2","key":"134_CR35","doi-asserted-by":"publisher","first-page":"429","DOI":"10.2307\/1428011","volume":"29","author":"A M\u00fcller","year":"1997","unstructured":"M\u00fcller, A.: Integral probability metrics and their generating classes of functions. Adv. Appl. Probab. 29(2), 429\u2013443 (1997)","journal-title":"Adv. Appl. Probab."},{"key":"134_CR36","doi-asserted-by":"crossref","unstructured":"Phillips, J.M.: Algorithms for $$\\varepsilon $$-approximations of terrains. In: ICALP (2008)","DOI":"10.1007\/978-3-540-70575-8_37"},{"key":"134_CR37","doi-asserted-by":"crossref","unstructured":"Phillips, J.M.: $$\\varepsilon $$-Samples for kernels. In: Proceedings of the 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201913), pp. 1622\u20131632. SIAM, Philadelphia (2013)","DOI":"10.1137\/1.9781611973105.116"},{"key":"134_CR38","doi-asserted-by":"crossref","unstructured":"Phillips, J.M., Tai, W.M.: Improved coresets for kernel density estimates. In: Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA\u201918), pp. 2718\u20132727. SIAM, Philadelphia (2018)","DOI":"10.1137\/1.9781611975031.173"},{"key":"134_CR39","unstructured":"Phillips, J.M., Tai, W.M.: Near-optimal coresets for kernel density estimates. In: Proceedings 34th International Symposium on Computational Geometry (SoCG\u201918), pp. 66:1\u201366:13. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2018)"},{"key":"134_CR40","unstructured":"Phillips, J.M., Venkatasubramanian, S.: A gentle introduction to the kernel distance. arXiv:1103.1625 (2011)"},{"key":"134_CR41","unstructured":"Phillips, J.M., Wang, B., Zheng, Y.: Geometric inference on kernel density estimates. In: Proceedings 31th International Symposium on Computational Geometry (SoCG\u201915). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2015)"},{"issue":"5","key":"134_CR42","doi-asserted-by":"publisher","first-page":"2678","DOI":"10.1214\/10-AOS797","volume":"38","author":"A Rinaldo","year":"2010","unstructured":"Rinaldo, A., Wasserman, L.: Generalized density clustering. Ann. Stat. 38(5), 2678\u20132722 (2010)","journal-title":"Ann. Stat."},{"issue":"4","key":"134_CR43","doi-asserted-by":"publisher","first-page":"811","DOI":"10.2307\/1968466","volume":"39","author":"IJ Schoenberg","year":"1938","unstructured":"Schoenberg, I.J.: Metric spaces and completely monotone functions. Ann. Math. 39(4), 811\u2013841 (1938)","journal-title":"Ann. Math."},{"key":"134_CR44","volume-title":"Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond","author":"B Sch\u00f6lkopf","year":"2002","unstructured":"Sch\u00f6lkopf, B., Smola, A.J.: Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. MIT Press, Cambridge (2002)"},{"key":"134_CR45","doi-asserted-by":"crossref","unstructured":"Schubert, E., Zimek, A., Kriegel, H.P.: Generalized outlier detection with flexible kernel density estimates. In: Proceedings of the SIAM International Conference on Data Mining, pp. 542\u2013550 (2014)","DOI":"10.1137\/1.9781611973440.63"},{"key":"134_CR46","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316849","volume-title":"Multivariate Density Estimation: Theory, Practice, and Visualization","author":"DW Scott","year":"1992","unstructured":"Scott, D.W.: Multivariate Density Estimation: Theory, Practice, and Visualization. Wiley, New York (1992)"},{"key":"134_CR47","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-3324-9","volume-title":"Density Estimation for Statistics and Data Analysis","author":"BW Silverman","year":"1986","unstructured":"Silverman, B.W.: Density Estimation for Statistics and Data Analysis. Chapman & Hall\/CRC, London (1986)"},{"key":"134_CR48","doi-asserted-by":"crossref","unstructured":"Song, L., Zhang, X., Smola, A., Gretton, A., Sch\u00f6lkopf, B.: Tailoring density estimation via reproducing kernel moment matching. In: Proceedings of the 25th International Conference on Machine Learning (ICML\u201908), pp. 992\u2013999. ACM, New York (2008)","DOI":"10.1145\/1390156.1390281"},{"key":"134_CR49","first-page":"1517","volume":"11","author":"BK Sriperumbudur","year":"2010","unstructured":"Sriperumbudur, B.K., Gretton, A., Fukumizu, K., Sch\u00f6lkopf, B., Lanckriet, G.R.G.: Hilbert space embeddings and metrics on probability measures. J. Mach. Learn. Res. 11, 1517\u20131561 (2010)","journal-title":"J. Mach. Learn. Res."},{"key":"134_CR50","doi-asserted-by":"crossref","unstructured":"Wahba, G.: Support vector machines, reproducing kernel Hilbert spaces, and randomized GACV. In: Advances in Kernel Methods\u2014Support Vector Learning, pp. 69\u201388. MIT Press, Cambridge (1999)","DOI":"10.7551\/mitpress\/1130.003.0009"},{"key":"134_CR51","doi-asserted-by":"crossref","unstructured":"Zheng, Y., Phillips, J.M.: L$$_{\\infty }$$ error and bandwidth selection for kernel density estimates of large data. In: Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD\u201915), pp. 1533\u20131542. ACM, New York (2015)","DOI":"10.1145\/2783258.2783357"}],"container-title":["Discrete &amp; Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00134-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-019-00134-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-019-00134-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,9,20]],"date-time":"2023-09-20T21:57:21Z","timestamp":1695247041000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-019-00134-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,25]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,6]]}},"alternative-id":["134"],"URL":"https:\/\/doi.org\/10.1007\/s00454-019-00134-6","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"value":"0179-5376","type":"print"},{"value":"1432-0444","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,25]]},"assertion":[{"value":"22 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 August 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2019","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 September 2019","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}