{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:50Z","timestamp":1740109310889,"version":"3.37.3"},"reference-count":42,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T00:00:00Z","timestamp":1596412800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"name":"ISF","award":["544\/13 and 276\/12"],"award-info":[{"award-number":["544\/13 and 276\/12"]}]},{"DOI":"10.13039\/501100006245","name":"Ministry of Science and Technology, Israel","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100006245","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CNS-1237235"],"award-info":[{"award-number":["CNS-1237235"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Check Point Institute for Information Security"},{"name":"IBM PhD Fellowship Awards Program"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2021,1]]},"DOI":"10.1007\/s00453-020-00753-z","type":"journal-article","created":{"date-parts":[[2020,8,3]],"date-time":"2020-08-03T07:05:38Z","timestamp":1596438338000},"page":"177-215","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Learning Privately with Labeled and Unlabeled Examples"],"prefix":"10.1007","volume":"83","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kobbi","family":"Nissim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7584-8768","authenticated-orcid":false,"given":"Uri","family":"Stemmer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,8,3]]},"reference":[{"key":"753_CR1","doi-asserted-by":"publisher","unstructured":"Abadi, M., Chu, A., Goodfellow, I.J., McMahan, H.B., Mironov, I., Talwar, K., Zhang, L.: Deep learning with differential privacy. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, Vienna, Austria, October 24\u201328, 2016, pp. 308\u2013318. ACM (2016). https:\/\/doi.org\/10.1145\/2976749.2978318","DOI":"10.1145\/2976749.2978318"},{"issue":"4","key":"753_CR2","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1109\/TIT.1970.1054472","volume":"16","author":"A Agrawala","year":"1970","unstructured":"Agrawala, A.: Learning with a probabilistic teacher. IEEE Trans. Inf. Theory 16(4), 373\u2013379 (1970). https:\/\/doi.org\/10.1109\/TIT.1970.1054472","journal-title":"IEEE Trans. Inf. Theory"},{"key":"753_CR3","unstructured":"Alon, N., Beimel, A., Moran, S., Stemmer, U.: Closure properties for private classification and online prediction. In: COLT (2020)"},{"key":"753_CR4","doi-asserted-by":"publisher","unstructured":"Alon, N., Livni, R., Malliaris, M., Moran, S.: Private PAC learning implies finite littlestone dimension. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, June 23\u201326, 2019, pp. 852\u2013860. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316312","DOI":"10.1145\/3313276.3316312"},{"key":"753_CR5","unstructured":"Balcan, M.F., Feldman, V.: Statistical active learning algorithms. In: Advances in Neural Information Processing Systems, vol. 26, pp. 1295\u20131303 (2013)"},{"key":"753_CR6","unstructured":"Bassily, R., Feldman, V., Talwar, K., Thakurta, A.G.: Private stochastic convex optimization with optimal rates. In: Wallach, H.M. Larochelle, H. Beygelzimer, A., d\u2019Alch\u00e9-Buc, F., Fox, E.B., Garnett, R. (eds.) Advances in Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, 8\u201314 December 2019, Vancouver, BC, Canada, pp. 11279\u201311288 (2019). http:\/\/papers.nips.cc\/paper\/9306-private-stochastic-convex-optimization-with-optimal-rates"},{"key":"753_CR7","doi-asserted-by":"publisher","unstructured":"Bassily, R., Nissim, K., Smith, A.D., Steinke, T., Stemmer, U., Ullman, J.: Algorithmic stability for adaptive data analysis. In: Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2016, Cambridge, MA, USA, June 18\u201321, 2016, pp. 1046\u20131059 (2016). https:\/\/doi.org\/10.1145\/2897518.2897566","DOI":"10.1145\/2897518.2897566"},{"issue":"3","key":"753_CR8","doi-asserted-by":"publisher","first-page":"401","DOI":"10.1007\/s10994-013-5404-1","volume":"94","author":"A Beimel","year":"2014","unstructured":"Beimel, A., Brenner, H., Kasiviswanathan, S.P., Nissim, K.: Bounds on the sample complexity for private learning and private data release. Mach. Learn. 94(3), 401\u2013437 (2014)","journal-title":"Mach. Learn."},{"key":"753_CR9","doi-asserted-by":"crossref","unstructured":"Beimel, A., Nissim, K., Stemmer, U.: Characterizing the sample complexity of private learners. In: ITCS, pp. 97\u2013110. ACM (2013)","DOI":"10.1145\/2422436.2422450"},{"issue":"1","key":"753_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.4086\/toc.2016.v012a001","volume":"12","author":"A Beimel","year":"2016","unstructured":"Beimel, A., Nissim, K., Stemmer, U.: Private learning and sanitization: pure vs. approximate differential privacy. Theory Comput. 12(1), 1\u201361 (2016). https:\/\/doi.org\/10.4086\/toc.2016.v012a001","journal-title":"Theory Comput."},{"key":"753_CR11","doi-asserted-by":"crossref","unstructured":"Blum, A., Dwork, C., McSherry, F., Nissim, K.: Practical privacy: the SuLQ framework. In: Li, C. (ed.) PODS, pp. 128\u2013138. ACM (2005)","DOI":"10.1145\/1065167.1065184"},{"issue":"2","key":"753_CR12","doi-asserted-by":"publisher","first-page":"12","DOI":"10.1145\/2450142.2450148","volume":"60","author":"A Blum","year":"2013","unstructured":"Blum, A., Ligett, K., Roth, A.: A learning theory approach to noninteractive database privacy. J. ACM 60(2), 12 (2013)","journal-title":"J. ACM"},{"issue":"4","key":"753_CR13","doi-asserted-by":"publisher","first-page":"929","DOI":"10.1145\/76359.76371","volume":"36","author":"A Blumer","year":"1989","unstructured":"Blumer, A., Ehrenfeucht, A., Haussler, D., Warmuth, M.K.: Learnability and the Vapnik-Chervonenkis dimension. J. ACM 36(4), 929\u2013965 (1989)","journal-title":"J. ACM"},{"key":"753_CR14","doi-asserted-by":"crossref","unstructured":"Bun, M., Livni, R., Moran, S.: An equivalence between private classification and online prediction. CoRR arxiv:abs\/2003.00563 (2020)","DOI":"10.1109\/FOCS46700.2020.00044"},{"key":"753_CR15","doi-asserted-by":"crossref","unstructured":"Bun, M., Nissim, K., Stemmer, U.: Simultaneous private learning of multiple concepts. In: ITCS, pp. 369\u2013380. ACM (2016)","DOI":"10.1145\/2840728.2840747"},{"key":"753_CR16","doi-asserted-by":"crossref","unstructured":"Bun, M., Nissim, K., Stemmer, U., Vadhan, S.P.: Differentially private release and learning of threshold functions. In: FOCS, pp. 634\u2013649 (2015)","DOI":"10.1109\/FOCS.2015.45"},{"key":"753_CR17","doi-asserted-by":"publisher","unstructured":"Bun, M., Ullman, J., Vadhan, S.P.: Fingerprinting codes and the price of approximate differential privacy. In: Symposium on Theory of Computing, STOC 2014, New York, NY, USA, May 31\u2013June 03, 2014, pp. 1\u201310 (2014). https:\/\/doi.org\/10.1145\/2591796.2591877","DOI":"10.1145\/2591796.2591877"},{"key":"753_CR18","unstructured":"Chaudhuri, K., Hsu, D.: Sample complexity bounds for differentially private learning. In: Kakade, S.M., von Luxburg, U. (eds.) COLT, JMLR Proceedings, vol.\u00a019, pp. 155\u2013186. JMLR.org (2011)"},{"key":"753_CR19","unstructured":"Chaudhuri, K., Monteleoni, C.: Privacy-preserving logistic regression. In: Koller, D., Schuurmans, D., Bengio, Y., Bottou, L. (eds.) NIPS. MIT Press (2008)"},{"key":"753_CR20","unstructured":"Chaudhuri, K., Monteleoni, C., Sarwate, A.D.: Differentially private empirical risk minimization. J. Mach. Learn. Res. 12, 1069\u20131109 (2011). http:\/\/dl.acm.org\/citation.cfm?id=1953048.2021036"},{"key":"753_CR21","doi-asserted-by":"crossref","unstructured":"Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., Roth, A.L.: Preserving statistical validity in adaptive data analysis. In: STOC, pp. 117\u2013126. ACM (2015)","DOI":"10.1145\/2746539.2746580"},{"key":"753_CR22","doi-asserted-by":"crossref","unstructured":"Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., Naor, M.: Our data, ourselves: privacy via distributed noise generation. In: Vaudenay, S. (ed.) EUROCRYPT, Lecture Notes in Computer Science, vol. 4004, pp. 486\u2013503. Springer (2006)","DOI":"10.1007\/11761679_29"},{"key":"753_CR23","doi-asserted-by":"crossref","unstructured":"Dwork, C., McSherry, F., Nissim, K., Smith, A.: Calibrating noise to sensitivity in private data analysis. In: TCC, Lecture Notes in Computer Science, vol. 3876, pp. 265\u2013284. Springer (2006)","DOI":"10.1007\/11681878_14"},{"key":"753_CR24","doi-asserted-by":"crossref","unstructured":"Dwork, C., Rothblum, G.N., Vadhan, S.P.: Boosting and differential privacy. In: FOCS, pp. 51\u201360. IEEE Computer Society (2010)","DOI":"10.1109\/FOCS.2010.12"},{"issue":"3","key":"753_CR25","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1016\/0890-5401(89)90002-3","volume":"82","author":"A Ehrenfeucht","year":"1989","unstructured":"Ehrenfeucht, A., Haussler, D., Kearns, M.J., Valiant, L.G.: A general lower bound on the number of examples needed for learning. Inf. Comput. 82(3), 247\u2013261 (1989)","journal-title":"Inf. Comput."},{"key":"753_CR26","doi-asserted-by":"publisher","unstructured":"Feldman, V., Koren, T., Talwar, K.: Private stochastic convex optimization: optimal rates in linear time. In: Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. (eds.) Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22\u201326, 2020, pp. 439\u2013449. ACM (2020). https:\/\/doi.org\/10.1145\/3357713.3384335","DOI":"10.1145\/3357713.3384335"},{"issue":"6","key":"753_CR27","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/140991844","volume":"44","author":"V Feldman","year":"2015","unstructured":"Feldman, V., Xiao, D.: Sample complexity bounds on differentially private learning via communication complexity. SIAM J. Comput. 44(6), 1740\u20131764 (2015). https:\/\/doi.org\/10.1137\/140991844","journal-title":"SIAM J. Comput."},{"issue":"1","key":"753_CR28","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1109\/TIT.1967.1053952","volume":"13","author":"S Fralick","year":"2006","unstructured":"Fralick, S.: Learning to recognize patterns without a teacher. IEEE Trans. Inf. Theor. 13(1), 57\u201364 (2006). https:\/\/doi.org\/10.1109\/TIT.1967.1053952","journal-title":"IEEE Trans. Inf. Theor."},{"key":"753_CR29","doi-asserted-by":"crossref","unstructured":"Gupta, A., Hardt, M., Roth, A., Ullman, J.: Privately releasing conjunctions and the statistical query barrier. In: Fortnow, L., Vadhan, S.P. (eds.) STOC, pp. 803\u2013812. ACM (2011)","DOI":"10.1145\/1993636.1993742"},{"key":"753_CR30","doi-asserted-by":"crossref","unstructured":"Hardt, M., Ullman, J.: Preventing false discovery in interactive data analysis is hard. In: FOCS. IEEE (2014)","DOI":"10.1109\/FOCS.2014.55"},{"key":"753_CR31","unstructured":"Kaplan, H., Ligett, K., Mansour, Y., Naor, M., Stemmer, U.: Privately learning thresholds: closing the exponential gap. In: COLT (2020)"},{"issue":"3","key":"753_CR32","doi-asserted-by":"publisher","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."},{"issue":"6","key":"753_CR33","doi-asserted-by":"publisher","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"MJ Kearns","year":"1998","unstructured":"Kearns, M.J.: Efficient noise-tolerant learning from statistical queries. J. ACM 45(6), 983\u20131006 (1998)","journal-title":"J. ACM"},{"key":"753_CR34","unstructured":"McCallum, A., Nigam, K.: Employing em and pool-based active learning for text classification. In: Proceedings of the Fifteenth International Conference on Machine Learning, ICML\u201998, pp. 350\u2013358. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA (1998). http:\/\/dl.acm.org\/citation.cfm?id=645527.757765"},{"key":"753_CR35","doi-asserted-by":"crossref","unstructured":"McSherry, F., Talwar, K.: Mechanism design via differential privacy. In: FOCS, pp. 94\u2013103. IEEE Computer Society (2007)","DOI":"10.1109\/FOCS.2007.66"},{"key":"753_CR36","unstructured":"Papernot, N., Abadi, M., Erlingsson, \u00da., Goodfellow, I.J., Talwar, K.: Semi-supervised knowledge transfer for deep learning from private training data. In: 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24\u201326, 2017, Conference Track Proceedings. OpenReview.net (2017). https:\/\/openreview.net\/forum?id=HkwoSDPgg"},{"key":"753_CR37","unstructured":"Rubinstein, B.I.P., Bartlett, P.L., Huang, L., Taft, N.: Learning in a large function space: privacy-preserving mechanisms for svm learning. CoRR arXiv:abs\/0911.5708 (2009)"},{"issue":"1","key":"753_CR38","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1016\/0097-3165(72)90019-2","volume":"13","author":"N Sauer","year":"1972","unstructured":"Sauer, N.: On the density of families of sets. J. Comb. Theory Ser. A 13(1), 145\u2013147 (1972). https:\/\/doi.org\/10.1016\/0097-3165(72)90019-2","journal-title":"J. Comb. Theory Ser. A"},{"issue":"3","key":"753_CR39","doi-asserted-by":"publisher","first-page":"363","DOI":"10.1109\/TIT.1965.1053799","volume":"11","author":"H Scudder","year":"1965","unstructured":"Scudder, H.: Probability of error of some adaptive pattern-recognition machines. IEEE Trans. Inf. Theory 11(3), 363\u2013371 (1965). https:\/\/doi.org\/10.1109\/TIT.1965.1053799","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"11","key":"753_CR40","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1145\/1968.1972","journal-title":"Commun. ACM"},{"key":"753_CR41","volume-title":"Theory of Pattern Recognition [in Russian]","author":"V Vapnik","year":"1974","unstructured":"Vapnik, V., Chervonenkis, A.: Theory of Pattern Recognition [in Russian]. Nauka, Moscow (1974)"},{"issue":"2","key":"753_CR42","doi-asserted-by":"publisher","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"VN Vapnik","year":"1971","unstructured":"Vapnik, V.N., Chervonenkis, A.Y.: On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16(2), 264\u2013280 (1971)","journal-title":"Theory Probab. Appl."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00753-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-020-00753-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00753-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,8,2]],"date-time":"2021-08-02T23:15:18Z","timestamp":1627946118000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-020-00753-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,8,3]]},"references-count":42,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["753"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00753-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,8,3]]},"assertion":[{"value":"14 August 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 July 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 August 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}