{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T05:55:19Z","timestamp":1775109319259,"version":"3.50.1"},"reference-count":66,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2017,1,9]],"date-time":"2017-01-09T00:00:00Z","timestamp":1483920000000},"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":["J. ACM"],"published-print":{"date-parts":[[2017,2,9]]},"abstract":"<jats:p>\n            We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and we demonstrate its effectiveness by designing algorithms with improved noise tolerance guarantees for learning linear separators. We consider both the malicious noise model of Valiant [1985] and Kearns and Li [1988] and the adversarial label noise model of Kearns, Schapire, and Sellie [1994]. For malicious noise, where the adversary can corrupt both the label and the features, we provide a polynomial-time algorithm for learning linear separators in \u211c\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            under isotropic log-concave distributions that can tolerate a nearly information-theoretically optimal noise rate of \u03b7 = \u03a9(\u03f5), improving on the \u03a9 (\u03f5\n            <jats:sup>3<\/jats:sup>\n            \/log\n            <jats:sup>2<\/jats:sup>\n            (\n            <jats:italic>d\/\u03f5<\/jats:italic>\n            )) noise-tolerance of Klivans et al. [2009a]. In the case that the distribution is uniform over the unit ball, this improves on the \u03a9 (\u03f5\/\n            <jats:italic>d<\/jats:italic>\n            <jats:sup>1\/4<\/jats:sup>\n            ) noise-tolerance of Kalai et al. [2005] and the \u03a9 (\u03f5\n            <jats:sup>2<\/jats:sup>\n            \/log(d\/\u03f5)) of Klivans et al. [2009a]. For the\n            <jats:italic>adversarial label noise<\/jats:italic>\n            model, where the distribution over the feature vectors is unchanged and the overall probability of a noisy label is constrained to be at most \u03b7, we also give a polynomial-time algorithm for learning linear separators in \u211c\n            <jats:sup>\n              <jats:italic>d<\/jats:italic>\n            <\/jats:sup>\n            under isotropic log-concave distributions that can handle a noise rate of \u03b7 = \u03a9(\u03f5). In the case of uniform distribution, this improves over the results of Kalai et al. [2005], which either required runtime super-exponential in 1\/\u03f5 (ours is polynomial in 1\/\u03f5) or tolerated less noise.\n            <jats:sup>1<\/jats:sup>\n            Our algorithms are also efficient in the active learning setting, where learning algorithms only receive the classifications of examples when they ask for them. We show that, in this model, our algorithms achieve a label complexity whose dependence on the error parameter \u03f5 is polylogarithmic (and thus exponentially better than that of any passive algorithm). This provides the first polynomial-time active learning algorithm for learning linear separators in the presence of malicious noise or adversarial label noise. Our algorithms and analysis combine several ingredients including aggressive localization, minimization of a progressively rescaled hinge loss, and a novel localized and soft outlier removal procedure. We use localization techniques (previously used for obtaining better sample complexity results) to obtain better noise-tolerant polynomial-time algorithms.\n          <\/jats:p>","DOI":"10.1145\/3006384","type":"journal-article","created":{"date-parts":[[2017,1,10]],"date-time":"2017-01-10T15:41:17Z","timestamp":1484062877000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":15,"title":["The Power of Localization for Efficiently Learning Linear Separators with Noise"],"prefix":"10.1145","volume":"63","author":[{"given":"Pranjal","family":"Awasthi","sequence":"first","affiliation":[{"name":"Rutgers University, Piscataway, NJ"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Maria Florina","family":"Balcan","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, PA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Philip M.","family":"Long","sequence":"additional","affiliation":[{"name":"Sentient Technologies, San Francisco, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2017,1,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"M. Anthony and P. L. Bartlett. 1999. Neural Network Learning: Theoretical Foundations. Cambridge University Press.   M. Anthony and P. L. Bartlett. 1999. Neural Network Learning: Theoretical Foundations. Cambridge University Press.","DOI":"10.1017\/CBO9780511624216"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103439"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366815"},{"key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","unstructured":"P. Awasthi M.-F. Balcan N. Haghtalab and R. Urner. 2015. Efficient learning of linear separators under bounded noise. In COLT.  P. Awasthi M.-F. Balcan N. Haghtalab and R. Urner. 2015. Efficient learning of linear separators under bounded noise. In COLT."},{"key":"e_1_2_1_6_1","unstructured":"P. Awasthi M.-F. Balcan N. Haghtalab and H. Zhang. 2016. Learning and 1-bit compressed sensing under asymmetric noise. In COLT.  P. Awasthi M.-F. Balcan N. Haghtalab and H. Zhang. 2016. Learning and 1-bit compressed sensing under asymmetric noise. In COLT."},{"key":"e_1_2_1_7_1","unstructured":"P. Awasthi A. Blum and O. Sheffet. 2010. Improved guarantees for agnostic learning of disjunctions. In COLT.  P. Awasthi A. Blum and O. Sheffet. 2010. Improved guarantees for agnostic learning of disjunctions. In COLT."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1143844.1143853"},{"key":"e_1_2_1_9_1","unstructured":"M.-F. Balcan A. Broder and T. Zhang. 2007. Margin based active learning. In COLT.   M.-F. Balcan A. Broder and T. Zhang. 2007. Margin based active learning. In COLT."},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"M.-F. Balcan and V. Feldman. 2013. Statistical active learning algorithms. In NIPS.   M.-F. Balcan and V. Feldman. 2013. Statistical active learning algorithms. In NIPS.","DOI":"10.1007\/978-3-642-27848-8_769-1"},{"key":"e_1_2_1_11_1","unstructured":"M.-F. Balcan and S. Hanneke. 2012. Robust interactive learning. In COLT.  M.-F. Balcan and S. Hanneke. 2012. Robust interactive learning. In COLT."},{"key":"e_1_2_1_12_1","unstructured":"M.-F. Balcan S. Hanneke and J. Wortman. 2008. The true sample complexity of active learning. In COLT.  M.-F. Balcan S. Hanneke and J. Wortman. 2008. The true sample complexity of active learning. In COLT."},{"key":"e_1_2_1_13_1","volume-title":"Conference on Learning Theory.","author":"Balcan M.-F."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1214\/009053605000000282"},{"key":"e_1_2_1_15_1","unstructured":"A. Beygelzimer D. Hsu J. Langford and T. Zhang. 2010. Agnostic active learning without constraints. In NIPS.   A. Beygelzimer D. Hsu J. Langford and T. Zhang. 2010. Agnostic active learning without constraints. In NIPS."},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"D. Bienstock and A. Michalka. 2014. Polynomial solvability of variants of the trust-region subproblem. In SODA.   D. Bienstock and A. Michalka. 2014. Polynomial solvability of variants of the trust-region subproblem. In SODA.","DOI":"10.1137\/1.9781611973402.28"},{"key":"e_1_2_1_17_1","unstructured":"A. Birnbaum and S. Shalev-Shwartz. 2012. Learning halfspaces with the zero-one loss: Time-accuracy tradeoffs. In NIPS.   A. Birnbaum and S. Shalev-Shwartz. 2012. Learning halfspaces with the zero-one loss: Time-accuracy tradeoffs. In NIPS."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00013833"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 13th Annual International Cryptology Conference on Advances in Cryptology.","author":"Blum Avrim"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1051\/ps:2005018"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2009.01.003"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/180139.181176"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"R. Castro and R. Nowak. 2007. Minimax bounds for active learning. In COLT.   R. Castro and R. Nowak. 2007. Minimax bounds for active learning. In COLT.","DOI":"10.1109\/TIT.2008.920189"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-010-5191-x"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1022673506211"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"N. Cristianini and J. Shawe-Taylor. 2000. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press.   N. Cristianini and J. Shawe-Taylor. 2000. An Introduction to Support Vector Machines and Other Kernel-based Learning Methods. Cambridge University Press.","DOI":"10.1017\/CBO9780511801389"},{"key":"e_1_2_1_27_1","unstructured":"A. Daniely. 2015. A PTAS for agnostically learning halfspaces. In COLT. See also Arxiv paper arXiv:1410.7050.  A. Daniely. 2015. A PTAS for agnostically learning halfspaces. In COLT. See also Arxiv paper arXiv:1410.7050."},{"key":"e_1_2_1_28_1","unstructured":"S. Dasgupta. 2005. Coarse sample complexity bounds for active learning. In NIPS.   S. Dasgupta. 2005. Coarse sample complexity bounds for active learning. In NIPS."},{"key":"e_1_2_1_29_1","volume-title":"Active learning. Encyclopedia of Machine Learning","author":"Dasgupta S.","year":"2011"},{"key":"e_1_2_1_30_1","unstructured":"S. Dasgupta D. J. Hsu and C. Monteleoni. 2007. A general agnostic active learning algorithm. In NIPS.   S. Dasgupta D. J. Hsu and C. Monteleoni. 2007. A general agnostic active learning algorithm. In NIPS."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/2503308.2503327"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"I. Diakonikolas G. Kamath D. Kane J. Li A. Moitra and A. Stewart. 2016. Robust estimators in high dimensions without the computational intractability. ArXiv e-prints (April 2016).  I. Diakonikolas G. Kamath D. Kane J. Li A. Moitra and A. Stewart. 2016. Robust estimators in high dimensions without the computational intractability. ArXiv e-prints (April 2016).","DOI":"10.1109\/FOCS.2016.85"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.51"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1007330508534"},{"key":"e_1_2_1_35_1","volume-title":"Johnson","author":"Garey Michael R.","year":"1990"},{"key":"e_1_2_1_36_1","unstructured":"A. Gonen S. Sabato and S. Shalev-Shwartz. 2013. Efficient pool-based active learning of halfspaces. In ICML.  A. Gonen S. Sabato and S. Shalev-Shwartz. 2013. Efficient pool-based active learning of halfspaces. In ICML."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993742"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.33"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/070685798"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1273496.1273541"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOS843"},{"key":"e_1_2_1_42_1","volume-title":"Theory of Disagreement-Based Active Learning. Foundations and Trends in Machine Learning","author":"Hanneke S."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-24486-0_10"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(78)90006-3"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.13"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62238"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00993468"},{"key":"e_1_2_1_48_1","doi-asserted-by":"crossref","unstructured":"M. Kearns and U. Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press Cambridge MA.   M. Kearns and U. Vazirani. 1994. An Introduction to Computational Learning Theory. MIT Press Cambridge MA.","DOI":"10.7551\/mitpress\/3897.001.0001"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1577069.1755877"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_44"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1953014"},{"key":"e_1_2_1_52_1","unstructured":"P. M. Long and R. A. Servedio. 2006. Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions. NIPS (2006).   P. M. Long and R. A. Servedio. 2006. Attribute-efficient learning of decision lists and linear threshold functions under unconcentrated distributions. NIPS (2006)."},{"key":"e_1_2_1_53_1","unstructured":"P. M. Long and R. A. Servedio. 2011. Learning large-margin halfspaces with more malicious noise. In NIPS.   P. M. Long and R. A. Servedio. 2011. Learning large-margin halfspaces with more malicious noise. In NIPS."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v30:3"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/11776420_47"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","volume-title":"Convergence of Stochastic Processes","author":"Pollard D.","DOI":"10.1007\/978-1-4612-5254-2"},{"key":"e_1_2_1_57_1","unstructured":"M. Raginsky and A. Rakhlin. 2011. Lower bounds for passive and active learning. In NIPS.   M. Raginsky and A. Rakhlin. 2011. Lower bounds for passive and active learning. In NIPS."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060603"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/648300.755336"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.2.246.14485"},{"key":"e_1_2_1_61_1","volume-title":"Proceedings of the 9th International Joint Conference on Artificial Intelligence.","author":"Valiant L. G.","year":"1985"},{"key":"e_1_2_1_62_1","volume-title":"Statistical Learning Theory","author":"Vapnik V."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/1857914.1857916"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2021072"},{"key":"e_1_2_1_65_1","unstructured":"C. Zhang and K. Chaudhuri. 2014. Beyond disagreement-based agnostic active learning. In NIPS.   C. Zhang and K. Chaudhuri. 2014. Beyond disagreement-based agnostic active learning. In NIPS."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.864439"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3006384","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3006384","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T03:39:38Z","timestamp":1750217978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3006384"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,1,9]]},"references-count":66,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2017,2,9]]}},"alternative-id":["10.1145\/3006384"],"URL":"https:\/\/doi.org\/10.1145\/3006384","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,1,9]]},"assertion":[{"value":"2015-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-10-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2017-01-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}