{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:52:41Z","timestamp":1781077961635,"version":"3.54.1"},"reference-count":23,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2012,10,1]],"date-time":"2012-10-01T00:00:00Z","timestamp":1349049600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["810\/11"],"award-info":[{"award-number":["810\/11"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2012,10]]},"abstract":"<jats:p>In this article we describe and analyze sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Our algorithms can be extended to some kernelized versions of these problems, such as SVDD, hard margin SVM, and<jats:italic>L<\/jats:italic><jats:sub>2<\/jats:sub>-SVM, for which sublinear-time algorithms were not known before. These new algorithms use a combination of a novel sampling techniques and a new multiplicative update algorithm. We give lower bounds which show the running times of many of our algorithms to be nearly best possible in the unit-cost RAM model.<\/jats:p>","DOI":"10.1145\/2371656.2371658","type":"journal-article","created":{"date-parts":[[2012,11,13]],"date-time":"2012-11-13T15:03:58Z","timestamp":1352819038000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Sublinear optimization for machine learning"],"prefix":"10.1145","volume":"59","author":[{"given":"Kenneth L.","family":"Clarkson","sequence":"first","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Elad","family":"Hazan","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of technology, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David P.","family":"Woodruff","sequence":"additional","affiliation":[{"name":"IBM Almaden Research Center, San Jose, CA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2012,11,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Blum A. Frieze A. M. Kannan R. and Vempala S. 1998. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica 22 1\/2 35--52. Blum A. Frieze A. M. Kannan R. and Vempala S. 1998. A polynomial-time algorithm for learning noisy linear threshold functions. Algorithmica 22 1\/2 35--52.","DOI":"10.1007\/PL00013833"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/180139.181176"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.833339"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the Annual Conference on Learning Theory (COLT), A. T. Kalai and M. Mohri, Eds. Omnipress, 218--230","author":"Cesa-Bianchi N.","unstructured":"Cesa-Bianchi , N. , Shalev-Shwartz , S. , and Shamir , O . 2010. Online learning of noisy data with kernels . In Proceedings of the Annual Conference on Learning Theory (COLT), A. T. Kalai and M. Mohri, Eds. Omnipress, 218--230 . Cesa-Bianchi, N., Shalev-Shwartz, S., and Shamir, O. 2010. Online learning of noisy data with kernels. In Proceedings of the Annual Conference on Learning Theory (COLT), A. T. Kalai and M. Mohri, Eds. Omnipress, 218--230."},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Proc. 19th ACM-SIAM Symposium on Discrete Algorithms. SIAM","author":"Clarkson K. L.","year":"2008","unstructured":"Clarkson , K. L. 2008 . Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm . In Proceedings of the Proc. 19th ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, 922--931. Clarkson, K. L. 2008. Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. In Proceedings of the Proc. 19th ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia, PA, 922--931."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Cover T. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications. Cover T. and Thomas J. A. 1991. Elements of Information Theory. Wiley Series in Telecommunications.","DOI":"10.1002\/0471200611"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176994663"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007404"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030109"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(95)00032-0"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Hazan E. 2011. The convex optimization approach to regret minimization. Optimiz. Mach. Learn. 1. Hazan E. 2011. The convex optimization approach to regret minimization. Optimiz. Mach. Learn. 1.","DOI":"10.7551\/mitpress\/8996.003.0012"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-007-5016-8"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.16"},{"key":"e_1_2_1_14_1","volume-title":"Perceptrons: An Introduction to Computational Geometry","author":"Minsky M.","year":"1988","unstructured":"Minsky , M. and Papert , S . 1988 . Perceptrons: An Introduction to Computational Geometry . MIT Press Cambridge , MA. Minsky, M. and Papert, S. 1988. Perceptrons: An Introduction to Computational Geometry. MIT Press Cambridge, MA."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms.","author":"Monemizadeh M.","unstructured":"Monemizadeh , M. and Woodruff , D . 2010. 1-pass relative error lp-sampling with applications . In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms. Monemizadeh, M. and Woodruff, D. 2010. 1-pass relative error lp-sampling with applications. In Proceedings of the 21st ACM-SIAM Symposium on Discrete Algorithms."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press. Motwani R. and Raghavan P. 1995. Randomized Algorithms. Cambridge University Press.","DOI":"10.1017\/CBO9780511814075"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the Symposium on the Mathematical Theory of Automata.","volume":"12","author":"Novikoff A. B.","year":"1963","unstructured":"Novikoff , A. B. 1963 . On convergence proofs for perceptrons . In Proceedings of the Symposium on the Mathematical Theory of Automata. Vol. 12 ., 615--622. Novikoff, A. B. 1963. On convergence proofs for perceptrons. In Proceedings of the Symposium on the Mathematical Theory of Automata. Vol. 12., 615--622."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793250767"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185411"},{"key":"e_1_2_1_20_1","unstructured":"Saha A. and Vishwanathan S. 2009. Efficient approximation algorithms for minimum enclosing convex shapes. arXiv:0909.1062v2. Saha A. and Vishwanathan S. 2009. Efficient approximation algorithms for minimum enclosing convex shapes. arXiv:0909.1062v2."},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Sch\u00f6lkopf B. and Smola A. J. 2003. A Short Introduction to Learning with Kernels. Springer New York. Sch\u00f6lkopf B. and Smola A. J. 2003. A Short Introduction to Learning with Kernels. Springer New York.","DOI":"10.1007\/3-540-36434-X_2"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/307400.307474"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 20th International Conference on Machine Learning (ICML). 928--936","author":"Zinkevich M.","year":"2003","unstructured":"Zinkevich , M. 2003 . Online convex programming and generalized infinitesimal gradient ascent . In Proceedings of the 20th International Conference on Machine Learning (ICML). 928--936 . Zinkevich, M. 2003. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML). 928--936."}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371658","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2371656.2371658","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T09:21:18Z","timestamp":1750238478000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2371656.2371658"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,10]]},"references-count":23,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2012,10]]}},"alternative-id":["10.1145\/2371656.2371658"],"URL":"https:\/\/doi.org\/10.1145\/2371656.2371658","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,10]]},"assertion":[{"value":"2011-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}