{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,5]],"date-time":"2026-10-05T23:08:31Z","timestamp":1791241711328,"version":"4.1.0"},"reference-count":29,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2011,1]]},"abstract":"<jats:p>We describe and analyze a new algorithm for agnostically learning kernel-based halfspaces with respect to the 0-1 loss function. Unlike most of the previous formulations, which rely on surrogate convex loss functions (e.g., hinge-loss in support vector machines (SVMs) and log-loss in logistic regression), we provide finite time\/sample guarantees with respect to the more natural 0-1 loss function. The proposed algorithm can learn kernel-based halfspaces in worst-case time poly$(\\exp(L\\log(L\/\\epsilon)))$, for any distribution, where L is a Lipschitz constant (which can be thought of as the reciprocal of the margin), and the learned classifier is worse than the optimal halfspace by at most $\\epsilon$. We also prove a hardness result, showing that under a certain cryptographic assumption, no algorithm can learn kernel-based halfspaces in time polynomial in L.<\/jats:p>","DOI":"10.1137\/100806126","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T18:27:16Z","timestamp":1323800836000},"page":"1623-1646","source":"Crossref","is-referenced-by-count":14,"title":["Learning Kernel-Based Halfspaces with the 0-1 Loss"],"prefix":"10.1137","volume":"40","author":[{"given":"Shai","family":"Shalev-Shwartz","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ohad","family":"Shamir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Karthik","family":"Sridharan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2011,12,13]]},"reference":[{"key":"R1","unstructured":"C. Thomas-Agnan and A. Berlinet,\n                      Reproducing Kernel Hilbert Spaces in Probability and Statistics\n                      , Springer, Berlin, New York, 2003."},{"key":"R2","unstructured":"N. I. Achieser,\n                      Theory of Approximation\n                      , Frederick Ungar Publishing, New York, 1956."},{"key":"R3","unstructured":"P. L. Bartlett,\n                      For valid generalization, the size of the weights is more important than the size of the network\n                      , in Advances in Neural Information Processing Systems 9, MIT Press, Cambridge, MA, 1997, pp. 134\u2013140."},{"key":"R4","doi-asserted-by":"publisher","DOI":"10.1198\/016214505000000907"},{"key":"R5","first-page":"463","volume":"3","author":"Bartlett P. L.","year":"2002","journal-title":"J. Mach. Learn. Res.","ISSN":"https:\/\/id.crossref.org\/issn\/1532-4435","issn-type":"print"},{"key":"R6","doi-asserted-by":"crossref","unstructured":"S. Ben-David,\n                      Alternative measures of computational complexity with applications to agnostic learning\n                      , in Theory and Applications of Models of Computation, Lecture Notes in Comput. Sci. 3959, Springer, Berlin, 2006, pp. 231\u2013235.","DOI":"10.1007\/11750321_22"},{"key":"R7","unstructured":"S. Ben-David and H. Simon,\n                      Efficient learning of linear perceptrons\n                      , in Advances in Neural Information Processing Systems 13, MIT Press, Cambridge, MA, 2000, pp. 189\u2013195."},{"key":"R8","unstructured":"E. Blais, R. O'Donnell, and K. Wimmer,\n                      Polynomial regression under arbitrary product distributions\n                      , in Proceedings of the 21st Annual Conference on Learning Theory, R. Servedio and T. Zhang, eds., Omnipress, Madison, WI, 2008, pp. 193\u2013204."},{"key":"R9","unstructured":"L. Bottou and O. Bousquet,\n                      The tradeoffs of large scale learning\n                      , in Advances in Neural Information Processing Systems 20, MIT Press, Cambridge, MA, 2008, pp. 161\u2013168."},{"key":"R10","unstructured":"O. Bousquet,\n                      Concentration Inequalities and Empirical Processes Theory Applied to the Analysis of Learning Algorithms\n                      , Ph.D. thesis, \u00c9cole Polytechnique, Palaiseau, France, 2002."},{"key":"R11","doi-asserted-by":"crossref","unstructured":"N. Cristianini and J. Shawe-Taylor,\n                      Kernel Methods for Pattern Analysis\n                      , Cambridge University Press, Cambridge, UK, 2004.","DOI":"10.1017\/CBO9780511809682"},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1964-0166903-7"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"V. Feldman, P. Gopalan, S. Khot, and A. K. Ponnuswami,\n                      New results for learning noisy parities and halfspaces\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2006, pp. 563\u2013574.","DOI":"10.1109\/FOCS.2006.51"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"V. Guruswami and P. Raghavendra,\n                      Hardness of learning halfspaces with noise\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2006, pp. 543\u2013552.","DOI":"10.1109\/FOCS.2006.33"},{"key":"R15","unstructured":"S. Kakade, K. Sridharan, and A. Tewari,\n                      On the complexity of linear prediction: Risk bounds, margin bounds, and regularization\n                      , in Advances in Neural Information Processing 21, MIT Press, Cambridge, MA, 2009, pp. 793\u2013800."},{"key":"R16","doi-asserted-by":"crossref","unstructured":"A. Kalai, A. R. Klivans, Y. Mansour, and R. Servedio,\n                      Agnostically learning halfspaces\n                      , in Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS), IEEE Press, Piscataway, NJ, 2005, pp. 11\u201320.","DOI":"10.1109\/SFCS.2005.13"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"R18","doi-asserted-by":"crossref","unstructured":"A. Klivans and A. Sherstov,\n                      Cryptographic hardness for learning intersections of halfspaces\n                      , in Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, IEEE Press, Piscataway, NJ, 2006, pp. 553\u2013562.","DOI":"10.1109\/FOCS.2006.24"},{"key":"R19","unstructured":"N. N. Lebedev,\n                      Special Functions and Their Applications\n                      , Dover, New York, 1972."},{"key":"R20","unstructured":"J. Mason,\n                      Chebyshev Polynomials\n                      , CRC Press, Boca Raton, FL, 2003."},{"key":"R21","doi-asserted-by":"crossref","unstructured":"D. McAllester,\n                      Simplified PAC-Bayesian margin bounds\n                      , in Proceedings of the 16th Annual Conference on Computational Learning Theory (COLT), Lecture Notes in Comput. Sci. 2777, Springer, Berlin, New York, 2003, pp. 203\u2013215.","DOI":"10.1007\/978-3-540-45167-9_16"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1007\/BF00116037"},{"key":"R23","doi-asserted-by":"crossref","unstructured":"B. Sch\u00f6lkopf and A. Smola,\n                      Learning with Kernels: Support Vector Machines, Regularization, Optimization and Beyond\n                      , MIT Press, Cambridge, MA, 2002.","DOI":"10.7551\/mitpress\/4175.001.0001"},{"key":"R24","doi-asserted-by":"crossref","unstructured":"S. Shalev-Shwartz and N. Srebro,\n                      SVM optimization: Inverse dependence on training set size\n                      , in Proceedings of the 25th International Conference on Machine Learning, Helsinki, Finland, 2008, pp. 928\u2013935.","DOI":"10.1145\/1390156.1390273"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1214\/009053606000001226"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1079120131"},{"key":"R27","unstructured":"V. N. Vapnik,\n                      Statistical Learning Theory\n                      , John Wiley, New York, 1998."},{"key":"R28","doi-asserted-by":"crossref","unstructured":"G. Wahba,\n                      Spline Models for Observational Data\n                      , CBMS-NSF Reg. Conf. Ser. Appl. Math. 59, SIAM, Philadelphia, 1990.","DOI":"10.1137\/1.9781611970128"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1079120130"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/100806126","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:33:03Z","timestamp":1787337183000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/100806126"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1]]},"references-count":29,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,1]]}},"alternative-id":["10.1137\/100806126"],"URL":"https:\/\/doi.org\/10.1137\/100806126","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,1]]}}}