{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T06:01:42Z","timestamp":1740808902777,"version":"3.38.0"},"reference-count":49,"publisher":"Association for Computing Machinery (ACM)","issue":"2","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,10]]},"abstract":"<jats:p>\n            The Sparse Vector Technique (SVT) is one of the most fundamental tools in differential privacy (DP). It works as a backbone for adaptive data analysis by answering a sequence of queries on a given dataset, and gleaning useful information in a privacy-preserving manner. Unlike the typical private query releases that directly publicize the noisy query results, SVT is less informative---it keeps the noisy query results to itself and only reveals a binary bit for each query, indicating whether the query result surpasses a predefined threshold. To provide a rigorous DP guarantee for SVT, prior works in the literature adopt a\n            <jats:italic>conservative<\/jats:italic>\n            privacy analysis by assuming the direct disclosure of noisy query results as in typical private query releases. This approach, however, hinders SVT from achieving higher query accuracy due to an overestimation of the privacy risks, which further leads to an excessive noise injection using the Laplacian or Gaussian noise for perturbation. Motivated by this, we provide a new privacy analysis for SVT by considering its less informative nature. Our analysis results not only broaden the range of applicable noise types for perturbation in SVT, but also identify the exponential noise as optimal among all evaluated noises (which, however, is usually deemed non-applicable in prior works). The main challenge in applying exponential noise to SVT is mitigating the sub-optimal performance due to the bias introduced by noise distributions. To address this, we develop a utility-oriented optimal threshold correction method and an appending strategy, which enhances the performance of SVT by increasing the precision and recall, respectively. The effectiveness of our proposed methods is substantiated both theoretically and empirically, demonstrating significant improvements up to 50% across evaluated metrics.\n          <\/jats:p>","DOI":"10.14778\/3705829.3705838","type":"journal-article","created":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:21:06Z","timestamp":1740784866000},"page":"187-199","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Unleash the Power of Ellipsis: Accuracy-Enhanced Sparse Vector Technique with Exponential Noise"],"prefix":"10.14778","volume":"18","author":[{"given":"Yuhan","family":"Liu","sequence":"first","affiliation":[{"name":"Renmin University of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sheng","family":"Wang","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yixuan","family":"Liu","sequence":"additional","affiliation":[{"name":"Renmin University of China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Feifei","family":"Li","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hong","family":"Chen","sequence":"additional","affiliation":[{"name":"Renmin University of China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,28]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557030"},{"key":"e_1_2_1_2_1","volume-title":"Model-agnostic private learning. Advances in Neural Information Processing Systems 31","author":"Bassily Raef","year":"2018","unstructured":"Raef Bassily, Om Thakkar, and Abhradeep Guha Thakurta. 2018. Model-agnostic private learning. Advances in Neural Information Processing Systems 31 (2018)."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.24432\/C5XW20"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974782.85"},{"key":"e_1_2_1_5_1","unstructured":"Craig Cahillane. 2024. Sum of Exponential and Laplace Distributions. https:\/\/ccahilla.github.io\/sum_exponential_and_laplace_distributions.pdf"},{"key":"e_1_2_1_6_1","volume-title":"Conference on Uncertainty in Artificial Intelligence. PMLR, 1109--1118","author":"Carvalho Ricardo Silva","year":"2020","unstructured":"Ricardo Silva Carvalho, Ke Wang, Lovedeep Gondara, and Chunyan Miao. 2020. Differentially private top-k selection via stability on unknown domain. In Conference on Uncertainty in Artificial Intelligence. PMLR, 1109--1118."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783379"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3197390"},{"key":"e_1_2_1_9_1","volume-title":"Collecting telemetry data privately. Advances in Neural Information Processing Systems 30","author":"Ding Bolin","year":"2017","unstructured":"Bolin Ding, Janardhan Kulkarni, and Sergey Yekhanin. 2017. Collecting telemetry data privately. Advances in Neural Information Processing Systems 30 (2017)."},{"key":"e_1_2_1_10_1","unstructured":"Zeyu Ding Daniel Kifer Thomas Steinke Yuxin Wang Yingtai Xiao Danfeng Zhang et al. 2021. The permute-and-flip mechanism is identical to report-noisy-max with exponential noise. arXiv preprint arXiv:2105.07260 (2021)."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-022-00728-2"},{"key":"e_1_2_1_12_1","volume-title":"Practical differentially private top-k selection with pay-what-you-get composition. Advances in Neural Information Processing Systems 32","author":"Durfee David","year":"2019","unstructured":"David Durfee and Ryan M Rogers. 2019. Practical differentially private top-k selection with pay-what-you-get composition. Advances in Neural Information Processing Systems 32 (2019)."},{"key":"e_1_2_1_13_1","volume-title":"International colloquium on automata, languages, and programming","author":"Dwork Cynthia","unstructured":"Cynthia Dwork. 2006. Differential privacy. In International colloquium on automata, languages, and programming. Springer, 1--12."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536467"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork Aaron Roth et al. 2014. The algorithmic foundations of differential privacy. Foundations and Trends\u00ae in Theoretical Computer Science 9 3--4 (2014) 211--407.","DOI":"10.1561\/0400000042"},{"key":"e_1_2_1_16_1","volume-title":"Boosting and differential privacy. In 2010 IEEE 51st annual symposium on foundations of computer science","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Guy N Rothblum, and Salil Vadhan. 2010. Boosting and differential privacy. In 2010 IEEE 51st annual symposium on foundations of computer science. IEEE, 51--60."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_18_1","volume-title":"Building a RAPPOR with the unknown: Privacy-preserving learning of associations and data dictionaries. arXiv preprint arXiv:1503.01214","author":"Fanti Giulia","year":"2015","unstructured":"Giulia Fanti, Vasyl Pihur, and \u00dalfar Erlingsson. 2015. Building a RAPPOR with the unknown: Privacy-preserving learning of associations and data dictionaries. arXiv preprint arXiv:1503.01214 (2015)."},{"key":"e_1_2_1_19_1","volume-title":"An introduction to ROC analysis. Pattern recognition letters 27, 8","author":"Fawcett Tom","year":"2006","unstructured":"Tom Fawcett. 2006. An introduction to ROC analysis. Pattern recognition letters 27, 8 (2006), 861--874."},{"key":"e_1_2_1_20_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 11--20","author":"Geng Quan","year":"2019","unstructured":"Quan Geng, Wei Ding, Ruiqi Guo, and Sanjiv Kumar. 2019. Optimal noise-adding mechanism in additive differential privacy. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 11--20."},{"key":"e_1_2_1_21_1","first-page":"11631","article-title":"Numerical composition of differential privacy","volume":"34","author":"Gopi Sivakanth","year":"2021","unstructured":"Sivakanth Gopi, Yin Tat Lee, and Lukas Wutschitz. 2021. Numerical composition of differential privacy. Advances in Neural Information Processing Systems 34 (2021), 11631--11642.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_22_1","first-page":"147","article-title":"Adversarially robust streaming algorithms via differential privacy","volume":"33","author":"Hasidim Avinatan","year":"2020","unstructured":"Avinatan Hasidim, Haim Kaplan, Yishay Mansour, Yossi Matias, and Uri Stemmer. 2020. Adversarially robust streaming algorithms via differential privacy. Advances in Neural Information Processing Systems 33 (2020), 147--158.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_23_1","volume-title":"International conference on machine learning. PMLR, 1376--1385","author":"Kairouz Peter","year":"2015","unstructured":"Peter Kairouz, Sewoong Oh, and Pramod Viswanath. 2015. The composition theorem for differential privacy. In International conference on machine learning. PMLR, 1376--1385."},{"key":"e_1_2_1_24_1","volume-title":"On Differentially Private Online Predictions. arXiv preprint arXiv:2302.14099","author":"Kaplan Haim","year":"2023","unstructured":"Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, and Uri Stemmer. 2023. On Differentially Private Online Predictions. arXiv preprint arXiv:2302.14099 (2023)."},{"key":"e_1_2_1_25_1","volume-title":"Conference on Learning Theory. PMLR, 2747--2776","author":"Kaplan Haim","year":"2021","unstructured":"Haim Kaplan, Yishay Mansour, and Uri Stemmer. 2021. The sparse vector technique, revisited. In Conference on Learning Theory. PMLR, 2747--2776."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623723"},{"key":"e_1_2_1_27_1","unstructured":"Yuhan Liu Sheng Wang Yixuan Liu Feifei Li and Hong Chen. 2024. Unleash the Power of Ellipsis: Accuracy-enhanced Sparse Vector Technique with Exponential Noise. arXiv:2407.20068 [cs.CR] https:\/\/arxiv.org\/abs\/2407.20068"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3381832"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00196"},{"key":"e_1_2_1_30_1","volume-title":"Echo of Neighbors: Privacy Amplification for Personalized Private Federated Learning with Shuffle Model. arXiv preprint arXiv:2304.05516","author":"Liu Yixuan","year":"2023","unstructured":"Yixuan Liu, Suyun Zhao, Li Xiong, Yuhan Liu, and Hong Chen. 2023. Echo of Neighbors: Privacy Amplification for Personalized Private Federated Learning with Shuffle Model. arXiv preprint arXiv:2304.05516 (2023)."},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the VLDB Endowment 10","author":"Lyu Min","year":"2017","unstructured":"Min Lyu, Dong Su, and Ninghui Li. 2017. Understanding the Sparse Vector Technique for Differential Privacy. Proceedings of the VLDB Endowment 10, 6 (2017)."},{"key":"e_1_2_1_32_1","first-page":"193","article-title":"Permute-and-Flip: A new mechanism for differentially private selection","volume":"33","author":"McKenna Ryan","year":"2020","unstructured":"Ryan McKenna and Daniel R Sheldon. 2020. Permute-and-Flip: A new mechanism for differentially private selection. Advances in Neural Information Processing Systems 33 (2020), 193--203.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_1_33_1","volume-title":"Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 247--264","author":"Meiser Sebastian","year":"2018","unstructured":"Sebastian Meiser and Esfandiar Mohammadi. 2018. Tight on budget? tight bounds for r-fold approximate differential privacy. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security. 247--264."},{"key":"e_1_2_1_34_1","unstructured":"Microsoft 2020. Putting differential privacy into practice to use data responsibly. Microsoft. https:\/\/blogs.microsoft.com\/ai-for-business\/differential-privacy\/."},{"key":"e_1_2_1_35_1","volume-title":"R\u00e9nyi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF)","author":"Mironov Ilya","unstructured":"Ilya Mironov. 2017. R\u00e9nyi differential privacy. In 2017 IEEE 30th computer security foundations symposium (CSF). IEEE, 263--275."},{"key":"e_1_2_1_36_1","volume-title":"The fast Fourier transform","author":"Nussbaumer Henri J","unstructured":"Henri J Nussbaumer and Henri J Nussbaumer. 1982. The fast Fourier transform. Springer."},{"key":"e_1_2_1_37_1","volume-title":"International Conference on Machine Learning. PMLR, 8672--8681","author":"Qiao Gang","year":"2021","unstructured":"Gang Qiao, Weijie Su, and Li Zhang. 2021. Oneshot differentially private top-k selection. In International Conference on Machine Learning. PMLR, 8672--8681."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806794"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","unstructured":"Omid Shakeri and Mir Pedram. 2012. QtyT40I10D100K. UCI Machine Learning Repository. 10.24432\/C5360W","DOI":"10.24432\/C5360W"},{"key":"e_1_2_1_40_1","volume-title":"Differentially Private Top-k Selection via Canonical Lipschitz Mechanism. arXiv preprint arXiv:2201.13376","author":"Shekelyan Michael","year":"2022","unstructured":"Michael Shekelyan and Grigorios Loukides. 2022. Differentially Private Top-k Selection via Canonical Lipschitz Mechanism. arXiv preprint arXiv:2201.13376 (2022)."},{"key":"e_1_2_1_41_1","volume-title":"Proceedings of the 22nd ACM SIGSAC conference on computer and communications security. 1310--1321","author":"Shokri Reza","year":"2015","unstructured":"Reza Shokri and Vitaly Shmatikov. 2015. Privacy-preserving deep learning. In Proceedings of the 22nd ACM SIGSAC conference on computer and communications security. 1310--1321."},{"key":"e_1_2_1_42_1","volume-title":"Differentially private algorithms for empirical machine learning. arXiv preprint arXiv:1411.5428","author":"Stoddard Ben","year":"2014","unstructured":"Ben Stoddard, Yan Chen, and Ashwin Machanavajjhala. 2014. Differentially private algorithms for empirical machine learning. arXiv preprint arXiv:1411.5428 (2014)."},{"key":"e_1_2_1_43_1","volume-title":"Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753","author":"Tang Jun","year":"2017","unstructured":"Jun Tang, Aleksandra Korolova, Xiaolong Bai, Xueqiang Wang, and Xiaofeng Wang. 2017. Privacy loss in apple's implementation of differential privacy on macos 10.12. arXiv preprint arXiv:1709.02753 (2017)."},{"key":"e_1_2_1_44_1","volume-title":"26th USENIX Security Symposium (USENIX Security 17)","author":"Wang Tianhao","year":"2017","unstructured":"Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In 26th USENIX Security Symposium (USENIX Security 17). 729--745."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1198\/jasa.2009.tm08651"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2019.00018"},{"key":"e_1_2_1_47_1","volume-title":"Wide network learning with differential privacy. arXiv preprint arXiv:2103.01294","author":"Zhang Huanyu","year":"2021","unstructured":"Huanyu Zhang, Ilya Mironov, and Meisam Hejazinia. 2021. Wide network learning with differential privacy. arXiv preprint arXiv:2103.01294 (2021)."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/502512.502572"},{"key":"e_1_2_1_49_1","first-page":"20249","article-title":"Improving sparse vector technique with renyi differential privacy","volume":"33","author":"Zhu Yuqing","year":"2020","unstructured":"Yuqing Zhu and Yu-Xiang Wang. 2020. Improving sparse vector technique with renyi differential privacy. Advances in Neural Information Processing Systems 33 (2020), 20249--20258.","journal-title":"Advances in Neural Information Processing Systems"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3705829.3705838","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,2,28]],"date-time":"2025-02-28T23:27:15Z","timestamp":1740785235000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3705829.3705838"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,10]]},"references-count":49,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2024,10]]}},"alternative-id":["10.14778\/3705829.3705838"],"URL":"https:\/\/doi.org\/10.14778\/3705829.3705838","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,10]]},"assertion":[{"value":"2025-02-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}