{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,15]],"date-time":"2026-05-15T01:18:24Z","timestamp":1778807904700,"version":"3.51.4"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2013,9,18]],"date-time":"2013-09-18T00:00:00Z","timestamp":1379462400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Mach Learn"],"published-print":{"date-parts":[[2014,3]]},"DOI":"10.1007\/s10994-013-5404-1","type":"journal-article","created":{"date-parts":[[2013,9,17]],"date-time":"2013-09-17T19:36:05Z","timestamp":1379446565000},"page":"401-437","source":"Crossref","is-referenced-by-count":36,"title":["Bounds on the sample complexity for private learning and private data release"],"prefix":"10.1007","volume":"94","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hai","family":"Brenner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shiva Prasad","family":"Kasiviswanathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kobbi","family":"Nissim","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,9,18]]},"reference":[{"key":"5404_CR1","series-title":"LNCS","first-page":"437","volume-title":"TCC","author":"A. Beimel","year":"2010","unstructured":"Beimel, A., Kasiviswanathan, S. P., & Nissim, K. (2010). Bounds on the sample complexity for private learning and private data release. In D. Micciancio (Ed.), LNCS: Vol.\u00a05978. TCC (pp. 437\u2013454). Berlin: Springer."},{"key":"5404_CR2","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1145\/2422436.2422450","volume-title":"ITCS","author":"A. Beimel","year":"2013","unstructured":"Beimel, A., Nissim, K., & Stemmer, U. (2013). Characterizing the sample complexity of private learners. In ITCS (pp. 97\u2013110)."},{"key":"5404_CR3","first-page":"128","volume-title":"PODS","author":"A. Blum","year":"2005","unstructured":"Blum, A., Dwork, C., McSherry, F., & Nissim, K. (2005). Practical privacy: the SuLQ framework. In PODS (pp. 128\u2013138). New York: ACM."},{"key":"5404_CR4","first-page":"609","volume-title":"STOC","author":"A. Blum","year":"2008","unstructured":"Blum, A., Ligett, K., & Roth, A. (2008). A learning theory approach to non-interactive database privacy. In STOC (pp. 609\u2013618). New York: ACM."},{"issue":"2","key":"5404_CR5","doi-asserted-by":"crossref","first-page":"12","DOI":"10.1145\/2450142.2450148","volume":"60","author":"A. Blum","year":"2013","unstructured":"Blum, A., Ligett, K., & Roth, A. (2013). A learning theory approach to non-interactive database privacy. Journal of the ACM, 60(2), 12.","journal-title":"Journal of the ACM"},{"issue":"4","key":"5404_CR6","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. K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4), 929\u2013965.","journal-title":"Journal of the ACM"},{"key":"5404_CR7","first-page":"155","volume":"19","author":"K. Chaudhuri","year":"2011","unstructured":"Chaudhuri, K., & Hsu, D. (2011). Sample complexity bounds for differentially private learning. Journal of Machine Learning Research, 19, 155\u2013186.","journal-title":"Journal of Machine Learning Research"},{"key":"5404_CR8","volume-title":"NIPS","author":"K. Chaudhuri","year":"2008","unstructured":"Chaudhuri, K., & Monteleoni, C. (2008). Privacy-preserving logistic regression. In D. Koller, D. Schuurmans, Y. Bengio, & L. Bottou (Eds.), NIPS, Cambridge: MIT Press."},{"key":"5404_CR9","first-page":"1069","volume":"12","author":"K. Chaudhuri","year":"2011","unstructured":"Chaudhuri, K., Monteleoni, C., & Sarwate, A. D. (2011). Differentially private empirical risk minimization. Journal of Machine Learning Research, 12, 1069\u20131109.","journal-title":"Journal of Machine Learning Research"},{"key":"5404_CR10","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1214\/aoms\/1177729330","volume":"23","author":"H. Chernoff","year":"1952","unstructured":"Chernoff, H. (1952). A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23, 493\u2013507.","journal-title":"The Annals of Mathematical Statistics"},{"key":"5404_CR11","series-title":"LNCS","first-page":"496","volume-title":"TCC","author":"C. Dwork","year":"2009","unstructured":"Dwork, C. (2009). The differential privacy frontier. In O. Reingold (Ed.), LNCS: Vol.\u00a05444. TCC (pp. 496\u2013502). Berlin: Springer."},{"issue":"1","key":"5404_CR12","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1145\/1866739.1866758","volume":"54","author":"C. Dwork","year":"2011","unstructured":"Dwork, C. (2011). A firm foundation for private data analysis. Communications of the ACM, 54(1), 86\u201395.","journal-title":"Communications of the ACM"},{"key":"5404_CR13","series-title":"LNCS","first-page":"265","volume-title":"TCC","author":"C. Dwork","year":"2006","unstructured":"Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006). Calibrating noise to sensitivity in private data analysis. In S. Halevi & T. Rabin (Eds.), LNCS: Vol.\u00a03876. TCC (pp. 265\u2013284). Berlin: Springer."},{"key":"5404_CR14","first-page":"381","volume-title":"STOC","author":"C. Dwork","year":"2009","unstructured":"Dwork, C., Naor, M., Reingold, O., Rothblum, G., & Vadhan, S. (2009). On the complexity of differentially private data release. In STOC (pp. 381\u2013390). New York: ACM."},{"issue":"3","key":"5404_CR15","doi-asserted-by":"crossref","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. (1989). A general lower bound on the number of examples needed for learning. Information and Computation, 82(3), 247\u2013261.","journal-title":"Information and Computation"},{"key":"5404_CR16","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of cryptography, volume basic tools","author":"O. Goldreich","year":"2001","unstructured":"Goldreich, O. (2001). Foundations of cryptography, volume basic tools. Cambridge: Cambridge University Press."},{"issue":"301","key":"5404_CR17","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1080\/01621459.1963.10500830","volume":"58","author":"W. Hoeffding","year":"1963","unstructured":"Hoeffding, W. (1963). Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301), 13\u201330.","journal-title":"Journal of the American Statistical Association"},{"key":"5404_CR18","volume-title":"Projective planes","author":"D. R. Hughes","year":"1973","unstructured":"Hughes, D. R., & Piper, F. C. (1973). Projective planes (Vol.\u00a06). Berlin: Springer."},{"issue":"3","key":"5404_CR19","doi-asserted-by":"crossref","first-page":"793","DOI":"10.1137\/090756090","volume":"40","author":"S. P. Kasiviswanathan","year":"2011","unstructured":"Kasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2011). What can we learn privately? SIAM Journal on Computing, 40(3), 793\u2013826.","journal-title":"SIAM Journal on Computing"},{"issue":"6","key":"5404_CR20","doi-asserted-by":"crossref","first-page":"983","DOI":"10.1145\/293347.293351","volume":"45","author":"M. J. Kearns","year":"1998","unstructured":"Kearns, M. J. (1998). Efficient noise-tolerant learning from statistical queries. Journal of the ACM, 45(6), 983\u20131006. Preliminary version in proceedings of STOC\u201993.","journal-title":"Journal of the ACM"},{"key":"5404_CR21","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3897.001.0001","volume-title":"An introduction to computational learning theory","author":"M. J. Kearns","year":"1994","unstructured":"Kearns, M. J., & Vazirani, U. V. (1994). An introduction to computational learning theory. Cambridge: MIT Press."},{"key":"5404_CR22","first-page":"25","volume":"23","author":"D. Kifer","year":"2012","unstructured":"Kifer, D., Smith, A. D., & Thakurta, A. (2012). Private convex optimization for empirical risk minimization with applications to high-dimensional regression. Journal of Machine Learning Research, 23, 25.","journal-title":"Journal of Machine Learning Research"},{"key":"5404_CR23","first-page":"94","volume-title":"FOCS","author":"F. McSherry","year":"2007","unstructured":"McSherry, F., & Talwar, K. (2007). Mechanism design via differential privacy. In FOCS (pp. 94\u2013103). New York: IEEE Press."},{"key":"5404_CR24","first-page":"143","volume-title":"PODS","author":"N. Mishra","year":"2006","unstructured":"Mishra, N., & Sandler, M. (2006). Privacy via pseudorandom sketches. In PODS (pp. 143\u2013152). New York: ACM."},{"issue":"4","key":"5404_CR25","doi-asserted-by":"crossref","first-page":"965","DOI":"10.1145\/48014.63140","volume":"35","author":"L. Pitt","year":"1988","unstructured":"Pitt, L., & Valiant, L. G. (1988). Computational limitations on learning from examples. Journal of the ACM, 35(4), 965\u2013984.","journal-title":"Journal of the ACM"},{"key":"5404_CR26","doi-asserted-by":"crossref","first-page":"1134","DOI":"10.1145\/1968.1972","volume":"27","author":"L. G. Valiant","year":"1984","unstructured":"Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27, 1134\u20131142.","journal-title":"Communications of the ACM"},{"key":"5404_CR27","doi-asserted-by":"crossref","first-page":"264","DOI":"10.1137\/1116025","volume":"16","author":"V. N. Vapnik","year":"1971","unstructured":"Vapnik, V. N., & Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability and Its Applications, 16, 264.","journal-title":"Theory of Probability and Its Applications"}],"container-title":["Machine Learning"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-013-5404-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10994-013-5404-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10994-013-5404-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,24]],"date-time":"2019-07-24T05:00:46Z","timestamp":1563944446000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10994-013-5404-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,18]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,3]]}},"alternative-id":["5404"],"URL":"https:\/\/doi.org\/10.1007\/s10994-013-5404-1","relation":{},"ISSN":["0885-6125","1573-0565"],"issn-type":[{"value":"0885-6125","type":"print"},{"value":"1573-0565","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,18]]}}}