{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,4]],"date-time":"2026-03-04T17:20:43Z","timestamp":1772644843345,"version":"3.50.1"},"reference-count":113,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"3","license":[{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2021,3,1]],"date-time":"2021-03-01T00:00:00Z","timestamp":1614556800000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"DOI":"10.13039\/100006785","name":"Google and Microsoft Research Fellowships as part of the Simons-Berkeley Research Fellowship Program","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google Faculty Research Award","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"name":"J.P. Morgan Faculty Award"},{"DOI":"10.13039\/100005801","name":"Facebook Research Award","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005801","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006112","name":"Microsoft Research, Redmond, and the Simons Institute for the Theory of Computing at UC Berkeley","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2021,3]]},"DOI":"10.1109\/tit.2021.3049802","type":"journal-article","created":{"date-parts":[[2021,1,10]],"date-time":"2021-01-10T06:22:05Z","timestamp":1610259725000},"page":"1981-2000","source":"Crossref","is-referenced-by-count":12,"title":["Private Hypothesis Selection"],"prefix":"10.1109","volume":"67","author":[{"given":"Mark","family":"Bun","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0048-2559","authenticated-orcid":false,"given":"Gautam","family":"Kamath","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Thomas","family":"Steinke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhiwei Steven","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"263","reference":[{"key":"ref39","article-title":"The right complexity measure in locally private estimation: It is not the Fisher information","author":"duchi","year":"2018","journal-title":"arXiv 1806 05756"},{"key":"ref38","first-page":"1120","article-title":"Hadamard response: Estimating distributions privately, efficiently, and with little communication","author":"acharya","year":"2019","journal-title":"Proc 22nd Int Conf Artif Intell Statist"},{"key":"ref33","first-page":"30","article-title":"Inspectre: Privately estimating the unseen","author":"acharya","year":"2018","journal-title":"Proc 35th Int Conf Mach Learn"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.29012\/jpc.v7i2.648"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591877"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065184"},{"key":"ref37","first-page":"2436","article-title":"Discrete distribution estimation under local privacy","author":"kairouz","year":"2016","journal-title":"Proc 33rd Int Conf Mach Learn"},{"key":"ref36","article-title":"Mutual information optimally local private discrete distribution estimation","author":"wang","year":"2016","journal-title":"arXiv 1607 08025"},{"key":"ref35","first-page":"429","article-title":"Local privacy and statistical minimax rates","author":"duchi","year":"2013","journal-title":"Proc Annu IEEE Symp Foundations Comput Sci"},{"key":"ref34","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993743"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/ITA50056.2020.9244945"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.45"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.66"},{"key":"ref22","first-page":"819","article-title":"Differentially private feature selection via stability arguments, and the robustness of the lasso","author":"thakurta","year":"2013","journal-title":"Proc 26th Annu Conf Learn Theory"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316336"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188946"},{"key":"ref101","doi-asserted-by":"publisher","DOI":"10.1109\/ITA.2016.7888199"},{"key":"ref26","article-title":"The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy","author":"tony cai","year":"2019","journal-title":"arXiv 1902 04495"},{"key":"ref100","doi-asserted-by":"crossref","first-page":"347","DOI":"10.1007\/978-3-319-57048-8_7","article-title":"The complexity of differential privacy","author":"vadhan","year":"2017","journal-title":"Tutorials on the Foundations of Cryptography Dedicated to Oded Goldreich"},{"key":"ref25","first-page":"44:1","article-title":"Finite sample differentially private confidence intervals","author":"karwa","year":"2018","journal-title":"Proc 9th Conf Innov Theor Comput Sci"},{"key":"ref50","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00036"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.108"},{"key":"ref59","doi-asserted-by":"crossref","first-page":"458","DOI":"10.1007\/11503415_31","article-title":"On spectral learning of mixtures of distributions","author":"achlioptas","year":"2005","journal-title":"Proc 18th Annu Conf Learn Theory"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181888"},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380808"},{"key":"ref56","first-page":"152","article-title":"A two-round variant of EM for Gaussian mixtures","author":"dasgupta","year":"2000","journal-title":"Proc 16th Conf Uncertainty Artif Intell"},{"key":"ref55","doi-asserted-by":"publisher","DOI":"10.1109\/SFFCS.1999.814639"},{"key":"ref54","first-page":"3577","article-title":"Optimal testing for properties of distributions","author":"acharya","year":"2015","journal-title":"Adv Neural Inf Process Syst"},{"key":"ref53","first-page":"1844","article-title":"Near-optimal density estimation in near-linear time using variable-width histograms","author":"chan","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591848"},{"key":"ref40","first-page":"2980","article-title":"Locally private Gaussian estimation","author":"joseph","year":"2019","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4613-0125-7","author":"devroye","year":"2001","journal-title":"Combinatorial Methods in Density Estimation"},{"key":"ref3","doi-asserted-by":"crossref","first-page":"2626","DOI":"10.1214\/aos\/1030741088","article-title":"Nonasymptotic universal smoothing factors, kernel complexity and yatracos classes","volume":"25","author":"devroye","year":"1997","journal-title":"Ann Statist"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214042"},{"key":"ref5","first-page":"503","article-title":"Density estimation in linear time","author":"mahalanabis","year":"2008","journal-title":"Proc of the 21st Annual Conference on Learning Theory"},{"key":"ref8","first-page":"1395","article-title":"Near-optimal-sample estimators for spherical Gaussian mixtures","author":"suresh","year":"2014","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897552"},{"key":"ref7","first-page":"1183","article-title":"Faster and sample near-optimal algorithms for proper learning mixtures of Gaussians","author":"daskalakis","year":"2014","journal-title":"Proc 27th Annu Conf Learn Theory"},{"key":"ref9","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875120"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897519"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.77"},{"key":"ref48","first-page":"850","article-title":"Properly learning Poisson binomial distributions in almost polynomial time","author":"diakonikolas","year":"2016","journal-title":"Proc 29th Annu Conf Learn Theory"},{"key":"ref47","first-page":"831","article-title":"Optimal learning via the Fourier transform for sums of independent integer random variables","author":"diakonikolas","year":"2016","journal-title":"Proc 29th Annu Conf Learn Theory"},{"key":"ref42","first-page":"2545","article-title":"Locally private confidence intervals: Z-test and tight confidence intervals","author":"gaboardi","year":"2019","journal-title":"Proc 22nd Int Conf Artif Intell Statist"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2018.2809790"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195155"},{"key":"ref43","article-title":"A primer on private statistics","author":"kamath","year":"2020","journal-title":"arXiv 2005 00010"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591881"},{"key":"ref72","first-page":"1135","article-title":"The more, the merrier: The blessing of dimensionality for learning large Gaussian mixtures","author":"anderson","year":"2014","journal-title":"Proc 27th Annu Conf Learn Theory"},{"key":"ref71","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422439"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.16"},{"key":"ref76","first-page":"2676","article-title":"Global analysis of expectation maximization for mixtures of two Gaussians","author":"xu","year":"2016","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref77","first-page":"704","article-title":"Ten steps of EM suffice for mixtures of two Gaussians","author":"daskalakis","year":"2017","journal-title":"Proc 30th Annu Conf Learn Theory"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746579"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746616"},{"key":"ref78","first-page":"3412","article-title":"Nearly tight sample complexity bounds for learning mixtures of Gaussians via sample compression schemes","author":"ashtiani","year":"2018","journal-title":"Adv Neural Inf Process Syst"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1007\/11776420_5"},{"key":"ref60","first-page":"9","article-title":"Learning mixtures of product distributions using correlations and independence","author":"chaudhuri","year":"2008","journal-title":"Proc 21st Annu Conf Learn Theory"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"ref61","first-page":"21","article-title":"Beyond Gaussians: Spectral methods for learning mixtures of heavy-tailed distributions","author":"chaudhuri","year":"2008","journal-title":"Proc 21st Annu Conf Learn Theory"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-32512-0_4"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.17"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188758"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806765"},{"key":"ref2","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1032181164"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.15"},{"key":"ref1","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176349553"},{"key":"ref109","doi-asserted-by":"publisher","DOI":"10.1016\/j.jet.2014.02.002"},{"key":"ref95","first-page":"263","article-title":"Rényi differential privacy","author":"mironov","year":"2017","journal-title":"Proc IEEE 30th Comput Secur Found Symp (CSF)"},{"key":"ref108","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.84"},{"key":"ref94","first-page":"635","article-title":"Concentrated differential privacy: Simplifications, extensions, and lower bounds","author":"bun","year":"2016","journal-title":"Proc 14th Amer Control Conf"},{"key":"ref107","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.31"},{"key":"ref93","article-title":"Concentrated differential privacy","author":"dwork","year":"2016","journal-title":"arXiv 1603 01887"},{"key":"ref106","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-014-0582-8"},{"key":"ref92","article-title":"The limits of pan privacy and shuffle privacy for learning and estimation","author":"cheu","year":"2020","journal-title":"arXiv 2009 08000"},{"key":"ref105","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536427"},{"key":"ref91","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.151"},{"key":"ref104","article-title":"The total variation distance between high-dimensional gaussians","author":"devroye","year":"2018","journal-title":"arXiv 1810 08693"},{"key":"ref90","first-page":"375","article-title":"Distributed differential privacy via shuffling","author":"cheu","year":"2019","journal-title":"Proc 38th Annu Int Conf Theory Appl Cryptograph Techn"},{"key":"ref103","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(94)00008-2"},{"key":"ref102","article-title":"A CLT and tight lower bounds for estimating entropy","volume":"17","author":"valiant","year":"2010","journal-title":"Electron Colloq Comput Complex"},{"key":"ref111","doi-asserted-by":"publisher","DOI":"10.1137\/0523054"},{"key":"ref112","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316312"},{"key":"ref110","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1941-0005942-4"},{"key":"ref98","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806786"},{"key":"ref99","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-013-5404-1"},{"key":"ref96","author":"vapnik","year":"1974","journal-title":"Theory of Pattern Recognition"},{"key":"ref97","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176988847"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.85"},{"key":"ref11","first-page":"2427","article-title":"Maximum selection and sorting with adversarial comparators","volume":"19","author":"acharya","year":"2018","journal-title":"J Mach Learn Res"},{"key":"ref12","first-page":"318","article-title":"The optimal approximation factor in density estimation","author":"bousquet","year":"2019","journal-title":"Proc 32nd Annu Conf Learn Theory"},{"key":"ref13","first-page":"265","article-title":"Calibrating noise to sensitivity in private data analysis","author":"dwork","year":"2006","journal-title":"Proc Conf Theory of Cryptography"},{"key":"ref14","year":"2017","journal-title":"Learning With Privacy at Scale"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"ref16","article-title":"The modernization of statistical disclosure limitation at the U.S. Census Bureau","author":"dajani","year":"0"},{"key":"ref82","article-title":"On the sample complexity of privately learning unbounded high-dimensional Gaussians","author":"aden-ali","year":"2021","journal-title":"Proc 32nd Int Conf Algorithmic Learn Theory"},{"key":"ref17","first-page":"1853","article-title":"Privately learning high-dimensional distributions","author":"kamath","year":"2019","journal-title":"Proc 32nd Annu Conf Learn Theory"},{"key":"ref81","first-page":"1302","article-title":"Robust proper learning for mixtures of Gaussians via systems of polynomial inequalities","author":"li","year":"2017","journal-title":"Proc 30th Annu Conf Learn Theory"},{"key":"ref18","first-page":"2566","article-title":"Differentially private learning of structured discrete distributions","author":"diakonikolas","year":"2015","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref84","article-title":"Learning discrete distributions: User vs item-level privacy","author":"liu","year":"2020","journal-title":"Proc Adv Neural Inf Process Syst"},{"key":"ref19","first-page":"1278","article-title":"Sample-optimal density estimation in nearly-linear time","author":"acharya","year":"2017","journal-title":"Proceedings of the 5th Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"ref83","first-page":"2204","article-title":"Private mean estimation of heavy-tailed distributions","author":"kamath","year":"2020","journal-title":"Proc 33rd Annu Conf Learn Theory"},{"key":"ref113","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a001"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1137\/060670705"},{"key":"ref89","first-page":"66","article-title":"Pan-private streaming algorithms","author":"dwork","year":"2010","journal-title":"Proc 1st Conf Innov Comput Sci"},{"key":"ref85","first-page":"1785","article-title":"Locally private hypothesis selection","author":"gopi","year":"2020","journal-title":"Proc 33rd Annu Conf Learn Theory"},{"key":"ref86","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"ref87","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773174"},{"key":"ref88","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx7\/18\/9356438\/09316923.pdf?arnumber=9316923","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,8,22]],"date-time":"2024-08-22T03:50:28Z","timestamp":1724298628000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/9316923\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,3]]},"references-count":113,"journal-issue":{"issue":"3"},"URL":"https:\/\/doi.org\/10.1109\/tit.2021.3049802","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,3]]}}}