{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T18:38:40Z","timestamp":1787510320581,"version":"build-2736575974"},"reference-count":50,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2014,11,11]],"date-time":"2014-11-11T00:00:00Z","timestamp":1415664000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2015,5]]},"DOI":"10.1007\/s00453-014-9954-9","type":"journal-article","created":{"date-parts":[[2014,11,14]],"date-time":"2014-11-14T15:29:46Z","timestamp":1415978986000},"page":"282-315","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Statistical Active Learning Algorithms for Noise Tolerance and Differential Privacy"],"prefix":"10.1007","volume":"72","author":[{"given":"Maria Florina","family":"Balcan","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vitaly","family":"Feldman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2014,11,11]]},"reference":[{"key":"9954_CR1","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Balcan, M.-F., Long, P.: The power of localization for efficiently learning linear separators with noise. In: Proceedings of the 46th ACM Symposium on Theory of Computing (2014)","DOI":"10.1145\/2591796.2591839"},{"key":"9954_CR2","first-page":"191","volume":"56","author":"J Aslam","year":"1998","unstructured":"Aslam, J., Decatur, S.: Specification and simulation of statistical query algorithms for efficiency and noise tolerance. JCSS 56, 191\u2013208 (1998)","journal-title":"JCSS"},{"key":"9954_CR3","first-page":"343","volume":"2","author":"D Angluin","year":"1988","unstructured":"Angluin, D., Laird, P.: Learning from noisy examples. Mach. Learn. 2, 343\u2013370 (1988)","journal-title":"Mach. Learn."},{"key":"9954_CR4","doi-asserted-by":"crossref","first-page":"323","DOI":"10.1051\/ps:2005018","volume":"9","author":"O Bousquet","year":"2005","unstructured":"Bousquet, O., Boucheron, S., Lugosi, G.: Theory of classification: a survey of recent advances. ESAIM Probab. Stat. 9, 323\u2013375 (2005)","journal-title":"ESAIM Probab. Stat."},{"key":"9954_CR5","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Beygelzimer, A., Langford, J.: Agnostic active learning. In: ICML (2006)","DOI":"10.1145\/1143844.1143853"},{"key":"9954_CR6","doi-asserted-by":"crossref","unstructured":"Balcan, M.-F., Broder, A., Zhang, T.: Margin based active learning. In: COLT, pp. 35\u201350 (2007)","DOI":"10.1007\/978-3-540-72927-3_5"},{"key":"9954_CR7","doi-asserted-by":"crossref","unstructured":"Beygelzimer, A., Dasgupta, S., Langford, J.: Importance weighted active learning. In: ICML, pp. 49\u201356 (2009)","DOI":"10.1145\/1553374.1553381"},{"key":"9954_CR8","doi-asserted-by":"crossref","unstructured":"Blum, A., Dwork, C., McSherry, F., Nissim, K.: Practical privacy: the SuLQ framework. In: Proceedings of PODS, pp. 128\u2013138 (2005)","DOI":"10.1145\/1065167.1065184"},{"issue":"4","key":"9954_CR9","doi-asserted-by":"crossref","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.: Learnability and the Vapnik\u2013Chervonenkis dimension. J. ACM 36(4), 929\u2013965 (1989)","journal-title":"J. ACM"},{"key":"9954_CR10","first-page":"359","volume":"2","author":"N Bshouty","year":"2002","unstructured":"Bshouty, N., Feldman, V.: On using extended statistical queries to avoid membership queries. JMLR 2, 359\u2013395 (2002)","journal-title":"JMLR"},{"key":"9954_CR11","doi-asserted-by":"crossref","unstructured":"Blum, A., Furst, M., Jackson, J., Kearns, M., Mansour, Y., Rudich, S.: Weakly learning DNF and characterizing statistical query learning using Fourier analysis. In: STOC, pp. 253\u2013262 (1994)","DOI":"10.1145\/195058.195147"},{"issue":"1\/2","key":"9954_CR12","first-page":"35","volume":"22","author":"A Blum","year":"1997","unstructured":"Blum, A., Frieze, A., Kannan, R., Vempala, S.: A polynomial time algorithm for learning noisy linear threshold functions. Algorithmica 22(1\/2), 35\u201352 (1997)","journal-title":"Algorithmica"},{"key":"9954_CR13","unstructured":"Balcan, M.-F., Hanneke, S.: Robust interactive learning. In: COLT (2012)"},{"key":"9954_CR14","unstructured":"Beygelzimer, A., Hsu, D., Langford, J., Zhang, T.: Agnostic active learning without constraints. In: NIPS (2010)"},{"key":"9954_CR15","unstructured":"Balcan, M.-F., Hanneke, S., Wortman, J.: The true sample complexity of active learning. In: COLT (2008)"},{"key":"9954_CR16","unstructured":"Balcan, M.-F., Long, P.M.: Active and passive learning of linear separators under log-concave distributions. In: COLT (2013)"},{"key":"9954_CR17","doi-asserted-by":"crossref","unstructured":"Bylander, T.: Learning linear threshold functions in the presence of classification noise. In: Proceedings of COLT, pp. 340\u2013347 (1994)","DOI":"10.1145\/180139.181176"},{"key":"9954_CR18","doi-asserted-by":"crossref","unstructured":"Cavallanti, G., Cesa-Bianchi, N., Gentile, C.: Learning noisy linear classifiers via adaptive and selective sampling. Mach Learn. 83, 71\u2013102 (2011)","DOI":"10.1007\/s10994-010-5191-x"},{"key":"9954_CR19","unstructured":"Chaudhuri, K., Hsu, D.: Sample complexity bounds for differentially private learning. In: JMLR COLT Proceedings, vol. 19, pp. 155\u2013186 (2011)"},{"key":"9954_CR20","doi-asserted-by":"crossref","unstructured":"Chu, C., Kim, S., Lin, Y., Yu, Y., Bradski, G., Ng, A., Olukotun, K.: Map-reduce for machine learning on multicore. In: Proceedings of NIPS, pp. 281\u2013288 (2006)","DOI":"10.7551\/mitpress\/7503.003.0040"},{"key":"9954_CR21","doi-asserted-by":"crossref","unstructured":"Castro, R., Nowak, R.: Minimax bounds for active learning. In: COLT (2007)","DOI":"10.1007\/978-3-540-72927-3_3"},{"key":"9954_CR22","unstructured":"Dasgupta, S.: Coarse sample complexity bounds for active learning. In: NIPS, vol. 18 (2005)"},{"key":"9954_CR23","doi-asserted-by":"crossref","unstructured":"Dasgupta, S.: Active learning theory. In: Sammut, C., Webb, G.I. (eds.) Encyclopedia of Machine Learning, pp. 14\u201319 (2010)","DOI":"10.1007\/978-1-4899-7687-1_7"},{"key":"9954_CR24","unstructured":"Dekel, O., Gentile, C., Sridharan, K.: Selective sampling and active learning from single and multiple teachers. J. Mach. Learn. Res. 13(1), 2655\u20132697 (2012)"},{"key":"9954_CR25","doi-asserted-by":"crossref","unstructured":"Dasgupta, S., Hsu, D.: Hierarchical sampling for active learning. In: ICML, pp. 208\u2013215 (2008)","DOI":"10.1145\/1390156.1390183"},{"key":"9954_CR26","unstructured":"Dasgupta, S., Hsu, D.J., Monteleoni, C.: A general agnostic active learning algorithm. In: NIPS (2011)"},{"key":"9954_CR27","first-page":"281","volume":"10","author":"S Dasgupta","year":"2009","unstructured":"Dasgupta, S., Tauman Kalai, A., Monteleoni, C.: Analysis of perceptron-based active learning. J. Mach. Learn. Res. 10, 281\u2013299 (2009)","journal-title":"J. Mach. Learn. Res."},{"key":"9954_CR28","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: TCC, pp. 265\u2013284 (2006)","DOI":"10.1007\/11681878_14"},{"key":"9954_CR29","doi-asserted-by":"crossref","unstructured":"Dunagan, J., Vempala, S.: A simple polynomial-time rescaling algorithm for solving linear programs. In: STOC, pp. 315\u2013320 (2004)","DOI":"10.1145\/1007352.1007404"},{"issue":"5","key":"9954_CR30","doi-asserted-by":"crossref","first-page":"1444","DOI":"10.1016\/j.jcss.2011.12.024","volume":"78","author":"V Feldman","year":"2012","unstructured":"Feldman, V.: A complete characterization of statistical query learning with applications to evolvability. J. Comput. Syst. Sci. 78(5), 1444\u20131459 (2012)","journal-title":"J. Comput. Syst. Sci."},{"key":"9954_CR31","doi-asserted-by":"crossref","unstructured":"Feldman, V., Grigorescu, E., Reyzin, L., Vempala, S., Xiao, Y.: Statistical algorithms and a lower bound for detecting planted cliques. In: ACM STOC (2013)","DOI":"10.1145\/2488608.2488692"},{"issue":"2\u20133","key":"9954_CR32","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1023\/A:1007330508534","volume":"28","author":"Y Freund","year":"1997","unstructured":"Freund, Y., Seung, H.S., Shamir, E., Tishby, N.: Selective sampling using the query by committee algorithm. Mach. Learn. 28(2\u20133), 133\u2013168 (1997)","journal-title":"Mach. Learn."},{"key":"9954_CR33","unstructured":"Gonen, A., Sabato, S., Shalev-Shwartz, S.: Efficient pool-based active learning of halfspaces. In: ICML (2013)"},{"key":"9954_CR34","doi-asserted-by":"crossref","unstructured":"Hanneke, S.: Theory of disagreement-based active learning. Found. Trends Mach. Learn. 7(2\u20133), 131\u2013309 (2014)","DOI":"10.1561\/2200000037"},{"key":"9954_CR35","doi-asserted-by":"crossref","unstructured":"Hanneke, S.: A bound on the label complexity of agnostic active learning. In: ICML (2007)","DOI":"10.1145\/1273496.1273541"},{"key":"9954_CR36","doi-asserted-by":"crossref","unstructured":"Jagannathan, G., Monteleoni, C., Pillaipakkamnatt, K.: A semi-supervised learning approach to differential privacy. In: Proceedings of the 2013 IEEE International Conference on Data Mining Workshops (ICDMW), IEEE Workshop on Privacy Aspects of Data Mining (PADM) (2013)","DOI":"10.1109\/ICDMW.2013.131"},{"issue":"6","key":"9954_CR37","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M Kearns","year":"1998","unstructured":"Kearns, M.: Efficient noise-tolerant learning from statistical queries. JACM 45(6), 983\u20131006 (1998)","journal-title":"JACM"},{"issue":"3","key":"9954_CR38","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1137\/090756090","volume":"40","author":"SP Kasiviswanathan","year":"2011","unstructured":"Kasiviswanathan, S.P., Lee, H.K., Nissim, K., Raskhodnikova, S., Smith, A.: What can we learn privately? SIAM J. Comput. 40(3), 793\u2013826 (2011)","journal-title":"SIAM J. Comput."},{"key":"9954_CR39","first-page":"2457","volume":"11","author":"V Koltchinskii","year":"2010","unstructured":"Koltchinskii, V.: Rademacher complexities and bounding the excess risk in active learning. JMLR 11, 2457\u20132485 (2010)","journal-title":"JMLR"},{"key":"9954_CR40","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An Introduction to Computational Learning Theory","author":"M Kearns","year":"1994","unstructured":"Kearns, M., Vazirani, U.: An Introduction to Computational Learning Theory. MIT Press, Cambridge, MA (1994)"},{"key":"9954_CR41","unstructured":"Kanade, V., Valiant, L.G., Wortman Vaughan, J.: Evolution with drifting targets. In: Proceedings of COLT, pp. 155\u2013167 (2010)"},{"issue":"6","key":"9954_CR42","doi-asserted-by":"crossref","first-page":"1556","DOI":"10.1109\/72.471352","volume":"6","author":"PM Long","year":"1995","unstructured":"Long, P.M.: On the sample complexity of PAC learning halfspaces against the uniform distribution. IEEE Trans. Neural Netw. 6(6), 1556\u20131559 (1995)","journal-title":"IEEE Trans. Neural Netw."},{"issue":"3","key":"9954_CR43","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1002\/rsa.20135","volume":"30","author":"L Lov\u00e1sz","year":"2007","unstructured":"Lov\u00e1sz, L., Vempala, S.: The geometry of logconcave functions and sampling algorithms. Random Struct. Algorithms 30(3), 307\u2013358 (2007)","journal-title":"Random Struct. Algorithms"},{"key":"9954_CR44","unstructured":"McCallum, A., Nigam, K.: Employing EM in pool-based active learning for text classification. In: ICML, pp. 350\u2013358 (1998)"},{"key":"9954_CR45","doi-asserted-by":"crossref","first-page":"386","DOI":"10.1037\/h0042519","volume":"65","author":"F Rosenblatt","year":"1958","unstructured":"Rosenblatt, F.: The perceptron: a probabilistic model for information storage and organization in the brain. Psychol. Rev. 65, 386\u2013407 (1958)","journal-title":"Psychol. Rev."},{"key":"9954_CR46","unstructured":"Raginsky, M., Rakhlin, A.: Lower bounds for passive and active learning. In: NIPS, pp. 1026\u20131034 (2011)"},{"issue":"11","key":"9954_CR47","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"LG Valiant","year":"1984","unstructured":"Valiant, L.G.: A theory of the learnable. Commun. ACM 27(11), 1134\u20131142 (1984)","journal-title":"Commun. ACM"},{"key":"9954_CR48","volume-title":"Statistical Learning Theory","author":"V Vapnik","year":"1998","unstructured":"Vapnik, V.: Statistical Learning Theory. Wiley-Interscience, New York (1998)"},{"key":"9954_CR49","unstructured":"Vempala, S.: Personal Communication (2013)"},{"key":"9954_CR50","unstructured":"Wang, L.: Smoothness, disagreement coefficient, and the label complexity of agnostic active learning. J. Mach. Learn. Res. 12, 2269\u20132292 (2011)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9954-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9954-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9954-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,18]],"date-time":"2023-07-18T01:09:32Z","timestamp":1689642572000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9954-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,11,11]]},"references-count":50,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2015,5]]}},"alternative-id":["9954"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9954-9","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,11,11]]}}}