{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,29]],"date-time":"2026-07-29T14:56:53Z","timestamp":1785337013132,"version":"3.55.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2024,3,12]],"date-time":"2024-03-12T00:00:00Z","timestamp":1710201600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Hong Kong Research Grants Council","award":["16201819, 16205420, 16205422"],"award-info":[{"award-number":["16201819, 16205420, 16205422"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,3,12]]},"abstract":"<jats:p>Random sampling is an effective tool for reducing the computational costs of query processing in large databases. It has also been used frequently for private data analysis, in particular, under differential privacy (DP). An interesting phenomenon that the literature has identified, is that sampling can amplify the privacy guarantee of a mechanism, which in turn leads to reduced noise scales that have to be injected.<\/jats:p>\n          <jats:p>All existing privacy amplification results only hold in the standard, record-level DP model. Recently, user-level differential privacy (user-DP) has gained a lot of attention as it protects all data records contributed by any particular user, thus offering stronger privacy protection. Sampling-based mechanisms under user-DP have not been explored so far, except naively running the mechanism on a sample without privacy amplification, which results in large DP noises. In fact, sampling is in even more demand under user-DP, since all state-of-the-art user-DP mechanisms have high computational costs due to the complex relationships between users and records. In this paper, we take the first step towards the study of privacy amplification by sampling under user-DP, and give the amplification results for two common user-DP sampling strategies: simple sampling and sample-and-explore. The experimental results show that these sampling-based mechanisms can be a useful tool to obtain some quick and reasonably accurate estimates on large private datasets.<\/jats:p>","DOI":"10.1145\/3639289","type":"journal-article","created":{"date-parts":[[2024,3,26]],"date-time":"2024-03-26T18:51:32Z","timestamp":1711479092000},"page":"1-26","source":"Crossref","is-referenced-by-count":5,"title":["Privacy Amplification by Sampling under User-level Differential Privacy"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9038-0585","authenticated-orcid":false,"given":"Juanru","family":"Fang","sequence":"first","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2178-3716","authenticated-orcid":false,"given":"Ke","family":"Yi","sequence":"additional","affiliation":[{"name":"Hong Kong University of Science and Technology, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,3,26]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning","volume":"97","author":"Amin Kareem","year":"2019","unstructured":"Kareem Amin, Alex Kulesza, Andres Mu\u00f1oz Medina, and Sergei Vassilvitskii. 2019. Bounding user contributions: A bias-variance trade-off in differential privacy. In Proceedings of the 36th International Conference on Machine Learning, Vol. 97. PMLR, 263--271."},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 32nd International Conference on Neural Information Processing Systems. Curran Associates Inc.","author":"Balle Borja","year":"2018","unstructured":"Borja Balle, Gilles Barthe, and Marco Gaboardi. 2018. Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences. In Proceedings of the 32nd International Conference on Neural Information Processing Systems. Curran Associates Inc., Red Hook, NY, USA, 6280--6290."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/3454287.3455478"},{"key":"e_1_2_1_5_1","volume-title":"Automata, Languages, and Programming","author":"Barthe Gilles","unstructured":"Gilles Barthe and Federico Olmedo. 2013. Beyond Differential Privacy: Composition Theorems and Relational Logic for f-divergences between Probabilistic Programs. In Automata, Languages, and Programming. Springer Berlin Heidelberg, Berlin, Heidelberg, 49--60."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2422436.2422449"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188946"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465304"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2926745"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3514221.3517844"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Wei Dong and Ke Yi. 2022. A Nearly Instance-optimal Differentially Private Mechanism for Conjunctive Queries. In PODS.","DOI":"10.1145\/3517804.3524143"},{"key":"e_1_2_1_12_1","volume-title":"Foundations and Trends in Theoretical Computer Science","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth. 2014. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, Vol. 9 (2014)."},{"key":"e_1_2_1_13_1","unstructured":"Alessandro Epasto Mohammad Mahdian Jieming Mao Vahab Mirrokni and Lijie Ren. 2020. Smoothly bounding user contributions in differential privacy. In Advances in Neural Information Processing Systems."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3548606.3560567"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00096"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch181"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00056"},{"key":"e_1_2_1_18_1","volume-title":"Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery","author":"Peter","unstructured":"Peter J. Haas and Joseph M. Hellerstein. 1999. Ripple Joins for Online Aggregation. In Proceedings of the 1999 ACM SIGMOD International Conference on Management of Data. Association for Computing Machinery, New York, NY, USA, 287--298."},{"key":"e_1_2_1_19_1","volume-title":"SNAP datasets: Stanford large network dataset collection","author":"Jure Leskovec","year":"2014","unstructured":"Leskovec Jure and Krevl Andrej. 2016. SNAP datasets: Stanford large network dataset collection (2014). URL http:\/\/snap. stanford. edu\/data (2016), 49."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/3402707.3402749"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.27"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-36594-2_26"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the VLDB Endowment.","author":"Kotsogiannis Ios","year":"2018","unstructured":"Ios Kotsogiannis, Yuchao Tao, Xi He, Maryam Fanaeepour, Ashwin Machanavajjhala, Michael Hay, and Gerome Miklau. 2018. PrivateSQL: a differentially private SQL query engine. In Proceedings of the VLDB Endowment."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2882903.2915235"},{"key":"e_1_2_1_25_1","volume-title":"R\u00e9nyi Differential Privacy of the Sampled Gaussian Mechanism. arxiv","author":"Mironov Ilya","year":"1908","unstructured":"Ilya Mironov, Kunal Talwar, and Li Zhang. 2019. R\u00e9nyi Differential Privacy of the Sampled Gaussian Mechanism. arxiv: 1908.10530 [cs.LG]"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250803"},{"key":"e_1_2_1_27_1","volume-title":"Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 495--504","author":"Raskhodnikova Sofya","year":"2016","unstructured":"Sofya Raskhodnikova and Adam Smith. 2016. Lipschitz Extensions for Node-Private Graph Statistics and the Generalized Exponential Mechanism. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). 495--504."},{"key":"e_1_2_1_28_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. URL https:\/\/networkrepository.com."},{"key":"e_1_2_1_29_1","volume-title":"Kolda","author":"Seshadhri C.","year":"2013","unstructured":"C. Seshadhri, Ali Pinar, and Tamara G. Kolda. 2013. Triadic Measures on Graphs: The Power of Wedge Sampling. In Proceedings of the 2013 SIAM International Conference on Data Mining. Society for Industrial and Applied Mathematics."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3389762"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1557019.1557111"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.151"},{"key":"e_1_2_1_33_1","volume-title":"Proc. VLDB Endow.","volume":"8","author":"Vengerov David","year":"2015","unstructured":"David Vengerov, Andre Cavalheiro Menck, Mohamed Zait, and Sunil P. Chakkappen. 2015. Join Size Estimation Subject to Filter Conditions. Proc. VLDB Endow., Vol. 8 (2015)."},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. 1226--1235","author":"Wang Yu-Xiang","year":"2019","unstructured":"Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. 2019. Subsampled R\u00e9nyi Differential Privacy and Analytical Moments Accountant. In Proceedings of the Twenty-Second International Conference on Artificial Intelligence and Statistics. 1226--1235."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.2478\/popets-2020-0025"},{"key":"e_1_2_1_36_1","volume-title":"Counting Triangles in Large Graphs by Random Sampling","author":"Wu Bin","year":"2013","unstructured":"Bin Wu, Ke Yi, and Zhenguo Li. 2016. Counting Triangles in Large Graphs by Random Sampling. In IEEE Transactions on Knowledge and Data Engineering. 2013--2026."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2737785"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 36th International Conference on Machine Learning. 7634--7642","author":"Zhu Yuqing","year":"2019","unstructured":"Yuqing Zhu and Yu-Xiang Wang. 2019. Poission Subsampled R\u00e9nyi Differential Privacy. In Proceedings of the 36th International Conference on Machine Learning. 7634--7642."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639289","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3639289","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T15:16:40Z","timestamp":1755789400000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3639289"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,3,12]]},"references-count":38,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,3,12]]}},"alternative-id":["10.1145\/3639289"],"URL":"https:\/\/doi.org\/10.1145\/3639289","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,3,12]]}}}