{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,18]],"date-time":"2025-11-18T23:15:46Z","timestamp":1763507746438},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>Noisy Max and Sparse Vector are selection algorithms for differential privacy and serve as building blocks for more complex algorithms. In this paper we show that both algorithms can release additional information for free (i.e., at no additional privacy cost). Noisy Max is used to return the approximate maximizer among a set of queries. We show that it can also release for free the noisy gap between the approximate maximizer and runner-up. This free information can improve the accuracy of certain subsequent counting queries by up to 50%. Sparse Vector is used to return a set of queries that are approximately larger than a fixed threshold. We show that it can adaptively control its privacy budget (use less budget for queries that are likely to be much larger than the threshold) in order to increase the amount of queries it can process. These results follow from a careful privacy analysis.<\/jats:p>","DOI":"10.14778\/3368289.3368295","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:17:35Z","timestamp":1599794255000},"page":"293-306","source":"Crossref","is-referenced-by-count":8,"title":["Free gap information from the differentially private sparse vector and noisy max mechanisms"],"prefix":"10.14778","volume":"13","author":[{"given":"Zeyu","family":"Ding","sequence":"first","affiliation":[{"name":"Pennsylvania State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yuxin","family":"Wang","sequence":"additional","affiliation":[{"name":"Pennsylvania State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Danfeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"Pennsylvania State University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Daniel","family":"Kifer","sequence":"additional","affiliation":[{"name":"Pennsylvania State University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2019,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3226070"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3158146"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934554"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2016.v012a001"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1835804.1835869"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132747.3132769"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53641-4_24"},{"key":"e_1_2_1_9_1","unstructured":"U. S. C. Bureau. On the map: Longitudinal employer-household dynamics. https:\/\/lehd.ces.census.gov\/applications\/help\/onthemap.html#!confidentiality_protection.  U. S. C. Bureau. On the map: Longitudinal employer-household dynamics. https:\/\/lehd.ces.census.gov\/applications\/help\/onthemap.html#!confidentiality_protection."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 27th International Conference on Neural Information Processing Systems -","volume":"1","author":"Chaudhuri K.","year":"2014"},{"key":"e_1_2_1_11_1","unstructured":"K. Chaudhuri C. Monteleoni and A. D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research 12(Mar):1069--1109 2011.  K. Chaudhuri C. Monteleoni and A. D. Sarwate. Differentially private empirical risk minimization. Journal of Machine Learning Research 12(Mar):1069--1109 2011."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2016.0019"},{"key":"e_1_2_1_13_1","volume-title":"Advances in Neural Information Processing Systems (NIPS)","author":"Ding B.","year":"2017"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Z. Ding Y. Wang D. Zhang and D. Kifer. Free gap information from the differentially private sparse vector and noisy max mechanisms. arXiv preprint arXiv:1904.12773 2019.  Z. Ding Y. Wang D. Zhang and D. Kifer. Free gap information from the differentially private sparse vector and noisy max mechanisms. arXiv preprint arXiv:1904.12773 2019.","DOI":"10.14778\/3368289.3368295"},{"key":"e_1_2_1_15_1","first-page":"1","volume-title":"Proceedings of the 33rd International Conference on Automata, Languages and Programming -","author":"Dwork C."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/11761679_29"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536466"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"issue":"34","key":"e_1_2_1_19_1","first-page":"211","article-title":"The algorithmic foundations of differential privacy","volume":"9","author":"Dwork C.","year":"2014","journal-title":"Foundations and Trends in Theoretical Computer Science"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019","author":"Feldman V.","year":"2019"},{"key":"e_1_2_1_21_1","first-page":"1054","volume-title":"Proceedings of the 2014 ACM SIGSAC conference on computer and communications security","author":"Pihur V.","year":"2014"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2018.00111"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875258"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536464"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035940"},{"key":"e_1_2_1_26_1","volume-title":"NIPS","author":"Hardt M.","year":"2012"},{"issue":"5","key":"e_1_2_1_27_1","first-page":"526","article-title":"Towards practical differential privacy for sql queries","volume":"11","author":"Johnson N.","year":"2018","journal-title":"PVLDB"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3035918.3035945"},{"key":"e_1_2_1_29_1","volume-title":"Springer Verlag","author":"Lehmann E.","year":"1998"},{"key":"e_1_2_1_30_1","volume-title":"NIPS","author":"Ligett K.","year":"2017"},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"J. Liu and K. Talwar. Private selection from private candidates. arXiv preprint arXiv:1811.07971 2018.  J. Liu and K. Talwar. Private selection from private candidates. arXiv preprint arXiv:1811.07971 2018.","DOI":"10.1145\/3313276.3316377"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.14778\/3055330.3055331"},{"key":"e_1_2_1_33_1","first-page":"277","volume-title":"Proceedings of the IEEE International Conference on Data Engineering (ICDE)","author":"Machanavajjhala A.","year":"2008"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.41"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559850"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2017.11"},{"key":"e_1_2_1_37_1","volume-title":"International Conference on Learning Representations (ICLR)","author":"Papernot N.","year":"2018"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.60"},{"key":"e_1_2_1_39_1","volume-title":"3rd Workshop on the Theory and Practice of Differential Privacy at CCS","author":"Tang J.","year":"2017"},{"issue":"8","key":"e_1_2_1_40_1","article-title":"Learning with privacy at scale","volume":"1","author":"Team A. D. P.","year":"2017","journal-title":"Apple Machine Learning Journal"},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 26th Annual Conference on Learning Theory","author":"Thakurta A. G.","year":"2013"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3314221.3314619"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/3009837.3009884"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196921"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3368289.3368295","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:41:30Z","timestamp":1672220490000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3368289.3368295"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.14778\/3368289.3368295"],"URL":"https:\/\/doi.org\/10.14778\/3368289.3368295","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}