{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:40:06Z","timestamp":1750200006106,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":63,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,6,15]],"date-time":"2021-06-15T00:00:00Z","timestamp":1623715200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,6,15]]},"DOI":"10.1145\/3406325.3450998","type":"proceedings-article","created":{"date-parts":[[2021,6,16]],"date-time":"2021-06-16T01:26:13Z","timestamp":1623806773000},"page":"88-101","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Efficiently learning halfspaces with Tsybakov noise"],"prefix":"10.1145","author":[{"given":"Ilias","family":"Diakonikolas","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel M.","family":"Kane","sequence":"additional","affiliation":[{"name":"University of California at San Diego, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vasilis","family":"Kontonis","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christos","family":"Tzamos","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Nikos","family":"Zarifis","sequence":"additional","affiliation":[{"name":"University of Wisconsin-Madison, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"4","article-title":"1988","volume":"2","author":"Angluin D.","year":"1988","unstructured":"D. Angluin and P. Laird. 1988. Learning From Noisy Examples. Mach. Learn., 2, 4, 1988. Pages 343\u2013370.","journal-title":"Learning From Noisy Examples. Mach. Learn."},{"volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015. Pages 167\u2013190","author":"Awasthi P.","unstructured":"P. Awasthi, M. F. Balcan, N. Haghtalab, and R. Urner. 2015. Efficient Learning of Linear Separators under Bounded Noise. In Proceedings of The 28th Conference on Learning Theory, COLT 2015. Pages 167\u2013190.","key":"e_1_3_2_1_2_1"},{"volume-title":"Proceedings of the 29th Conference on Learning Theory, COLT 2016. Pages 152\u2013192","author":"Awasthi P.","unstructured":"P. Awasthi, M. F. Balcan, N. Haghtalab, and H. Zhang. 2016. Learning and 1-bit Compressed Sensing under Asymmetric Noise. In Proceedings of the 29th Conference on Learning Theory, COLT 2016. Pages 152\u2013192.","key":"e_1_3_2_1_3_1"},{"key":"e_1_3_2_1_4_1","first-page":"6","article-title":"2017","volume":"63","author":"Awasthi P.","year":"2017","unstructured":"P. Awasthi, M. F. Balcan, and P. M. Long. 2017. The Power of Localization for Efficiently Learning Linear Separators with Noise. J. ACM, 63, 6, 2017. Pages 50:1\u201350:27.","journal-title":"J. ACM"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_5_1","DOI":"10.5555\/1768841.1768848"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_6_1","DOI":"10.1214\/009053605000000282"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_7_1","DOI":"10.1198\/016214505000000907"},{"volume-title":"Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. Pages 280\u2013287","author":"Beigman E.","unstructured":"E. Beigman and B. B. Klebanov. 2009. Learning with annotation noise. In Proceedings of the Joint Conference of the 47th Annual Meeting of the ACL and the 4th International Joint Conference on Natural Language Processing of the AFNLP. Pages 280\u2013287.","key":"e_1_3_2_1_8_1"},{"key":"e_1_3_2_1_9_1","first-page":"338","volume-title":"37th Annual Symposium on Foundations of Computer Science, FOCS '96","author":"Blum A.","unstructured":"A. Blum, A. M. Frieze, R. Kannan, and S. Vempala. 1996. A Polynomial-Time Algorithm for Learning Noisy Linear Threshold Functions. In 37th Annual Symposium on Foundations of Computer Science, FOCS '96. Pages 330\u2013338."},{"key":"e_1_3_2_1_10_1","first-page":"9","article-title":"2005. Theory of Classification: a Survey of Some Recent Advances","author":"Boucheron S.","year":"2005","unstructured":"S. Boucheron, O. Bousquet, and G. Lugosi. 2005. Theory of Classification: a Survey of Some Recent Advances. ESAIM: Probability and Statistics, 9, 2005. Pages 323\u2013375.","journal-title":"ESAIM: Probability and Statistics"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_11_1","DOI":"10.1145\/180139.181176"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_12_1","DOI":"10.1109\/TIT.2008.920189"},{"unstructured":"S. Chen F. Koehler A. Moitra and M. Yau. 2020. Classification Under Misspecification: Halfspaces Generalized Linear Models and Connections to Evolvability. CoRR abs\/2006.04787 2020. arxiv:2006.04787","key":"e_1_3_2_1_13_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_14_1","DOI":"10.1080\/01621459.1984.10477109"},{"volume-title":"Machine Learning Challenges Workshop. Pages 177\u2013190","author":"Dagan I.","unstructured":"I. Dagan, O. Glickman, and B. Magnini. 2005. The PASCAL recognising textual entailment challenge. In Machine Learning Challenges Workshop. Pages 177\u2013190.","key":"e_1_3_2_1_15_1"},{"key":"e_1_3_2_1_16_1","volume-title":"Proceedings of The 28th Conference on Learning Theory, COLT 2015. Pages 484\u2013502","author":"Daniely A.","year":"2015","unstructured":"A. Daniely. 2015. A PTAS for Agnostically Learning Halfspaces. In Proceedings of The 28th Conference on Learning Theory, COLT 2015. Pages 484\u2013502."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_17_1","DOI":"10.1145\/2897518.2897520"},{"unstructured":"I. Diakonikolas T. Gouleakis C. Tzamos H. Wallach H. Larochelle A. Beygelzimer F. d'Alch\u00e9 Buc E. Fox and R. Garnett. 2019. Distribution-Independent PAC Learning of Halfspaces with Massart Noise. In Advances in Neural Information Processing Systems 32. Curran Associates Inc.. Pages 4751\u20134762.","key":"e_1_3_2_1_18_1"},{"key":"e_1_3_2_1_19_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning, ICML 2019. Pages 1596\u20131606","author":"Diakonikolas I.","year":"2019","unstructured":"I. Diakonikolas, G. Kamath, D. Kane, J. Li, J. Steinhardt, and Alistair Stewart. 2019. Sever: A Robust Meta-Algorithm for Stochastic Optimization. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019. Pages 1596\u20131606."},{"key":"e_1_3_2_1_20_1","first-page":"664","volume-title":"Proceedings of FOCS'16","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. 2016. Robust Estimators in High Dimensions without the Computational Intractability. In Proceedings of FOCS'16. Pages 655\u2013664."},{"volume-title":"Proceedings of the 34th International Conference on Machine Learning, ICML 2017. Pages 999\u20131008","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. 2017. Being Robust (in High Dimensions) Can Be Practical. In Proceedings of the 34th International Conference on Machine Learning, ICML 2017. Pages 999\u20131008.","key":"e_1_3_2_1_21_1"},{"key":"e_1_3_2_1_22_1","first-page":"2702","volume-title":"Efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA","author":"Diakonikolas I.","year":"2018","unstructured":"I. Diakonikolas, G. Kamath, D. M. Kane, J. Li, A. Moitra, and A. Stewart. 2018. Robustly Learning a Gaussian: Getting Optimal Error, Efficiently. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018. Pages 2683\u20132702."},{"unstructured":"I. Diakonikolas and D. M. Kane. 2019. Recent Advances in Algorithmic High-Dimensional Robust Statistics. CoRR abs\/1911.05911 2019. arxiv:1911.05911","key":"e_1_3_2_1_23_1"},{"unstructured":"I. Diakonikolas and D. M. Kane. 2020. Hardness of Learning Halfspaces with Massart Noise. CoRR abs\/2012.09720 2020. arxiv:2012.09720","key":"e_1_3_2_1_24_1"},{"doi-asserted-by":"crossref","unstructured":"I. Diakonikolas D. M. Kane V. Kontonis C. Tzamos and N Zarifis. 2020. A Polynomial Time Algorithm for Learning Halfspaces with Tsybakov Noise.","key":"e_1_3_2_1_25_1","DOI":"10.1145\/3406325.3450998"},{"volume-title":"Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018. Pages 1061\u20131073","author":"Diakonikolas I.","unstructured":"I. Diakonikolas, D. M. Kane, and A. Stewart. 2018. Learning geometric concepts with nasty noise. In Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2018. Pages 1061\u20131073.","key":"e_1_3_2_1_26_1"},{"unstructured":"I. Diakonikolas D. M. Kane and N. Zarifis. 2020. Near-Optimal SQ Lower Bounds for Agnostically Learning Halfspaces and ReLUs under Gaussian Marginals. CoRR abs\/2006.16200 2020. arxiv:2006.16200","key":"e_1_3_2_1_27_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_28_1","DOI":"10.1137\/1.9781611975482.170"},{"key":"e_1_3_2_1_29_1","first-page":"1513","volume-title":"Learning Halfspaces with Massart Noise Under Structured Distributions. In Conference on Learning Theory, COLT 2020. Proceedings of Machine Learning Research. 125","author":"Diakonikolas I.","year":"2020","unstructured":"I. Diakonikolas, V. Kontonis, C. Tzamos, N. Zarifis, Jacob D. Abernethy, and Shivani Agarwal. 2020. Learning Halfspaces with Massart Noise Under Structured Distributions. In Conference on Learning Theory, COLT 2020. Proceedings of Machine Learning Research. 125, PMLR. Pages 1486\u20131513."},{"doi-asserted-by":"crossref","unstructured":"I. Diakonikolas V. Kontonis C. Tzamos and N. Zarifis. 2020. Learning Halfspaces with Tsybakov Noise. arXiv preprint arXiv:2006.06467 2020.","key":"e_1_3_2_1_30_1","DOI":"10.1145\/3406325.3450998"},{"unstructured":"I. Diakonikolas V. Kontonis C. Tzamos and N. Zarifis. 2020. Non-Convex SGD Learns Halfspaces with Adversarial Label Noise. In NeurIPS.","key":"e_1_3_2_1_31_1"},{"volume-title":"Proc. FOCS. Pages 563\u2013576","author":"Feldman V.","unstructured":"V. Feldman, P. Gopalan, S. Khot, and A. Ponnuswami. 2006. New Results for Learning Noisy Parities and Halfspaces. In Proc. FOCS. Pages 563\u2013576.","key":"e_1_3_2_1_32_1"},{"doi-asserted-by":"crossref","unstructured":"B. Fr\u00e9nay and M. Verleysen. 2013. Classification in the presence of label noise: a survey. IEEE transactions on neural networks and learning systems 25 5 2013. Pages 845\u2013869.","key":"e_1_3_2_1_33_1","DOI":"10.1109\/TNNLS.2013.2292894"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_34_1","DOI":"10.1006\/jcss.1997.1504"},{"unstructured":"S. Goel A. Gollakota and A. Klivans. 2020. Statistical-Query Lower Bounds via Functional Gradients. CoRR abs\/2006.15812 2020. arxiv:2006.15812","key":"e_1_3_2_1_35_1"},{"volume-title":"Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS). Pages 543\u2013552","author":"Guruswami V.","unstructured":"V. Guruswami and P. Raghavendra. 2006. Hardness of learning halfspaces with noise. In Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS). Pages 543\u2013552.","key":"e_1_3_2_1_36_1"},{"key":"e_1_3_2_1_37_1","volume-title":"Rates of convergence in active learning. Ann. Statist., 39, 1, 2","author":"Hanneke S.","year":"2011","unstructured":"S. Hanneke. 2011. Rates of convergence in active learning. Ann. Statist., 39, 1, 2, 2011. Pages 333\u2013361."},{"key":"e_1_3_2_1_38_1","first-page":"16","article-title":"2015. Minimax analysis of active learning","author":"Hanneke S.","year":"2015","unstructured":"S. Hanneke and L. Yang. 2015. Minimax analysis of active learning. J. Mach. Learn. Res., 16, 2015. Pages 3487\u20133602.","journal-title":"J. Mach. Learn. Res."},{"key":"e_1_3_2_1_39_1","volume-title":"Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100","author":"Haussler D.","year":"1992","unstructured":"D. Haussler. 1992. Decision theoretic generalizations of the PAC model for neural net and other learning applications. Information and Computation, 100, 1992. Pages 78\u2013150."},{"unstructured":"M. Hopkins D. M. Kane S. Lovett and G. Mahajan. 2020. Noise-tolerant reliable active classification with comparison queries. In COLT.","key":"e_1_3_2_1_40_1"},{"key":"e_1_3_2_1_41_1","first-page":"6","article-title":"2008","volume":"37","author":"Kalai A.","year":"2008","unstructured":"A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. 2008. Agnostically Learning Halfspaces. SIAM J. Comput., 37, 6, 2008. Pages 1777\u20131805.","journal-title":"Agnostically Learning Halfspaces. SIAM J. Comput."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_42_1","DOI":"10.1007\/BF00993468"},{"key":"e_1_3_2_1_43_1","first-page":"4","article-title":"2009. From annotator agreement to noise models","volume":"35","author":"Klebanov B. B.","year":"2009","unstructured":"B. B. Klebanov and E. Beigman. 2009. From annotator agreement to noise models. Computational Linguistics, 35, 4, 2009. Pages 495\u2013503.","journal-title":"Computational Linguistics"},{"volume-title":"Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. Pages 438\u2013446","author":"Klebanov B. B.","unstructured":"B. B. Klebanov and E. Beigman. 2010. Some empirical evidence for annotation noise in a benchmarked dataset. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. Pages 438\u2013446.","key":"e_1_3_2_1_44_1"},{"volume-title":"Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. Pages 438\u2013446","author":"Klebanov B. B.","unstructured":"B. B. Klebanov and E. Beigman. 2010. Some empirical evidence for annotation noise in a benchmarked dataset. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics. Pages 438\u2013446.","key":"e_1_3_2_1_45_1"},{"doi-asserted-by":"crossref","unstructured":"A. Klivans P. Long and R. Servedio. 2009. Learning Halfspaces with Malicious Noise. 2009.","key":"e_1_3_2_1_46_1","DOI":"10.1007\/978-3-642-02927-1_51"},{"key":"e_1_3_2_1_47_1","first-page":"1430","volume-title":"Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory, COLT","author":"Klivans A. R.","year":"2018","unstructured":"A. R. Klivans, P. K. Kothari, and R. Meka. 2018. Efficient Algorithms for Outlier-Robust Regression. In Conference On Learning Theory, COLT 2018. Pages 1420\u20131430."},{"volume-title":"Proceedings of FOCS'16","author":"Lai K. A.","unstructured":"K. A. Lai, A. B. Rao, and S. Vempala. 2016. Agnostic Estimation of Mean and Covariance. In Proceedings of FOCS'16.","key":"e_1_3_2_1_48_1"},{"volume-title":"2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 998\u20131007","author":"Lee Y. T.","unstructured":"Y. T. Lee and S. S. Vempala. 2017. Eldan's Stochastic Localization and the KLS Hyperplane Conjecture: An Improved Lower Bound for Expansion. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Pages 998\u20131007.","key":"e_1_3_2_1_49_1"},{"unstructured":"W. Maass G. Turan S. Hanson G. Drastal and R. Rivest. 1994. How fast can a threshold gate learn? In Computational Learning Theory and Natural Learning Systems. MIT Press. Pages 381\u2013414.","key":"e_1_3_2_1_50_1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_51_1","DOI":"10.1214\/aos\/1017939240"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_52_1","DOI":"10.1214\/009053606000000786"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_53_1","DOI":"10.1007\/s10994-018-5715-3"},{"unstructured":"M. Minsky and S. Papert. 1968. Perceptrons: an introduction to computational geometry. MIT Press.","key":"e_1_3_2_1_54_1"},{"key":"e_1_3_2_1_55_1","volume-title":"Proceedings of the Symposium on Mathematical Theory of Automata. XII, Pages 615\u2013622","author":"Novikoff A.","year":"1962","unstructured":"A. Novikoff. 1962. On convergence proofs on perceptrons. In Proceedings of the Symposium on Mathematical Theory of Automata. XII, Pages 615\u2013622."},{"key":"e_1_3_2_1_56_1","volume-title":"The Perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65","author":"Rosenblatt F.","year":"1958","unstructured":"F. Rosenblatt. 1958. The Perceptron: a probabilistic model for information storage and organization in the brain. Psychological Review, 65, 1958. Pages 386\u2013407."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_57_1","DOI":"10.5555\/93025.93060"},{"key":"e_1_3_2_1_58_1","volume-title":"Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32, 1","author":"Tsybakov A.","year":"2004","unstructured":"A. Tsybakov. 2004. Optimal aggregation of classifiers in statistical learning. The Annals of Statistics, 32, 1, 2004. Pages 135\u2013166."},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_59_1","DOI":"10.1145\/800057.808710"},{"doi-asserted-by":"publisher","key":"e_1_3_2_1_60_1","DOI":"10.1007\/978-1-4757-3264-1"},{"key":"e_1_3_2_1_61_1","first-page":"1066","volume-title":"Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems","author":"Yan S.","year":"2017","unstructured":"S. Yan and C. Zhang. 2017. Revisiting Perceptron: Efficient and Label-Optimal Learning of Halfspaces. In Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017. Pages 1056\u20131066."},{"unstructured":"C. Zhang J. Shen and P. Awasthi. 2020. Efficient active learning of sparse halfspaces with arbitrary bounded noise. CoRR abs\/2002.04840 2020.","key":"e_1_3_2_1_62_1"},{"volume-title":"Proceedings of the 30th Conference on Learning Theory, COLT 2017. Pages 1980\u20132022","author":"Zhang Y.","unstructured":"Y. Zhang, P. Liang, and M. Charikar. 2017. A Hitting Time Analysis of Stochastic Gradient Langevin Dynamics. In Proceedings of the 30th Conference on Learning Theory, COLT 2017. Pages 1980\u20132022.","key":"e_1_3_2_1_63_1"}],"event":{"sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"acronym":"STOC '21","name":"STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing","location":"Virtual Italy"},"container-title":["Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3450998","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3406325.3450998","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:01:44Z","timestamp":1750197704000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3406325.3450998"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,15]]},"references-count":63,"alternative-id":["10.1145\/3406325.3450998","10.1145\/3406325"],"URL":"https:\/\/doi.org\/10.1145\/3406325.3450998","relation":{},"subject":[],"published":{"date-parts":[[2021,6,15]]},"assertion":[{"value":"2021-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}