{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,1]],"date-time":"2026-06-01T23:34:51Z","timestamp":1780356891910,"version":"3.54.1"},"reference-count":52,"publisher":"Association for Computing Machinery (ACM)","issue":"8","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2024,4]]},"abstract":"<jats:p>\n            <jats:italic>Local differential privacy<\/jats:italic>\n            (\n            <jats:italic>LDP<\/jats:italic>\n            ) is a strong privacy standard that has been adopted by popular software systems, including Chrome, iOS, MacOS, and Windows. The main idea is that each individual perturbs their own data locally, and only submits the resulting noisy version to a data aggregator. Although much effort has been devoted to computing various types of aggregates and building machine learning applications under LDP, research on fundamental perturbation mechanisms has not achieved significant improvement in recent years. Towards a more refined result utility, existing works in the literature mainly focus on improving the\n            <jats:italic>worst-case<\/jats:italic>\n            guarantee. However, this approach does not necessarily promise a better\n            <jats:italic>average<\/jats:italic>\n            performance given the fact that the data in practice obey a certain distribution, which is not known beforehand.\n          <\/jats:p>\n          <jats:p>\n            In this paper, we propose the\n            <jats:italic>advanced adaptive additive<\/jats:italic>\n            (\n            <jats:italic>AAA<\/jats:italic>\n            ) mechanism, which is a distribution-aware approach that addresses the average utility and tackles the classical\n            <jats:italic>mean estimation<\/jats:italic>\n            problem. AAA is carried out in a two-step approach: first, as the global data distribution is not available beforehand, the data aggregator selects a random subset of individuals to compute a (noisy) quantized data descriptor; then, in the second step, the data aggregator collects data from the remaining individuals, which are perturbed in a distribution-aware fashion. The perturbation involved in the latter step is obtained by solving an optimization problem, which is formulated with the data descriptor obtained in the former step and the desired properties of task-determined utilities. We provide rigorous privacy proofs and utility analyses, as well as extensive experiments comparing AAA with state-of-the-art mechanisms. The evaluation results demonstrate that the AAA mechanism consistently outperforms existing solutions with a clear margin in terms of result utility, on a wide range of privacy constraints and real-world and synthetic datasets.\n          <\/jats:p>","DOI":"10.14778\/3659437.3659442","type":"journal-article","created":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T16:22:27Z","timestamp":1717172547000},"page":"1843-1855","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["AAA: An Adaptive Mechanism for Locally Differentially Private Mean Estimation"],"prefix":"10.14778","volume":"17","author":[{"given":"Fei","family":"Wei","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ergute","family":"Bao","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaokui","family":"Xiao","sequence":"additional","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yin","family":"Yang","sequence":"additional","affiliation":[{"name":"Hamad Bin Khalifa University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bolin","family":"Ding","sequence":"additional","affiliation":[{"name":"Alibaba Group"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,5,31]]},"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":"Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication. In AISTATS.","author":"Acharya Jayadev","year":"2018","unstructured":"Jayadev Acharya, Ziteng Sun, and Huanyu Zhang. 2018. Hadamard Response: Estimating Distributions Privately, Efficiently, and with Little Communication. In AISTATS."},{"key":"e_1_2_1_3_1","volume-title":"2022 IEEE International Symposium on Information Theory (ISIT). IEEE","author":"Alghamdi Wael","year":"2022","unstructured":"Wael Alghamdi, Shahab Asoodeh, Flavio P Calmon, Oliver Kosut, Lalitha Sankar, and Fei Wei. 2022. Cactus mechanisms: Optimal differential privacy mechanisms in the large-composition regime. In 2022 IEEE International Symposium on Information Theory (ISIT). IEEE, 1838--1843."},{"key":"e_1_2_1_4_1","volume-title":"Retrieved","year":"2016","unstructured":"Apple. 2016. Differential Privacy Overview. (2016). Retrieved December 21, 2020 from https:\/\/www.apple.com\/privacy\/docs\/Differential_Privacy_Overview.pdf"},{"key":"e_1_2_1_5_1","unstructured":"Raef Bassily Kobbi Nissim Uri Stemmer and Abhradeep Guha Thakurta. 2017. Practical Locally Private Heavy Hitters. In NeurIPS."},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Raef Bassily and Adam Smith. 2015. Local Private Efficient Protocols for Succinct Histograms. In STOC. 127--135.","DOI":"10.1145\/2746539.2746632"},{"key":"e_1_2_1_7_1","volume-title":"Prochlo: Strong Privacy for Analytics in the Crowd. SOSP","author":"Bittau Andrea","year":"2017","unstructured":"Andrea Bittau, \u00dalfar Erlingsson, Petros Maniatis, Ilya Mironov, Ananth Raghunathan, David Lie, Mitch Rudominer, Ushasree Kode, Julien Tinn\u00e9s, and Bernhard Seefeld. 2017. Prochlo: Strong Privacy for Analytics in the Crowd. SOSP (2017), 441--459."},{"key":"e_1_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Keith Bonawitz Vladimir Ivanov Ben Kreuter Antonio Marcedone H. Brendan McMahan Sarvar Patel Daniel Ramage Aaron Segal and Karn Seth. 2017. Practical Secure Aggregation for Privacy-Preserving Machine Learning. In CCS. 1175--1191.","DOI":"10.1145\/3133956.3133982"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660345"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3344722"},{"key":"e_1_2_1_11_1","unstructured":"Mark Bun and Thomas Steinke. 2019. Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation. In Advances in Neural Information Processing Systems. 181--191."},{"key":"e_1_2_1_12_1","volume-title":"Shiva Prasad Kasiviswanathan, and Hongxia Jin","author":"Chen Rui","year":"2016","unstructured":"Rui Chen, Haoran Li, A. Kai Qin, Shiva Prasad Kasiviswanathan, and Hongxia Jin. 2016. Private spatial data aggregation in the local setting. In ICDE. 289--300."},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Graham Cormode Tejas Kulkarni and Divesh Srivastava. 2018. Marginal Release Under Local Differential Privacy. In SIGMOD. 131--146.","DOI":"10.1145\/3183713.3196906"},{"key":"e_1_2_1_14_1","first-page":"10","article-title":"Answering Range Queries under Local Differential Privacy","volume":"12","author":"Cormode Graham","year":"2019","unstructured":"Graham Cormode, Tejas Kulkarni, and Divesh Srivastava. 2019. Answering Range Queries under Local Differential Privacy. PVLDB 12, 10 (jun 2019), 1126--1138.","journal-title":"PVLDB"},{"key":"e_1_2_1_15_1","first-page":"11","article-title":"Frequency Estimation under Local Differential Privacy","volume":"14","author":"Cormode Graham","year":"2021","unstructured":"Graham Cormode, Samuel Maddock, and Carsten Maple. 2021. Frequency Estimation under Local Differential Privacy. Proc. VLDB Endow. 14, 11 (oct 2021), 2046--2058.","journal-title":"Proc. VLDB Endow."},{"key":"e_1_2_1_16_1","unstructured":"Bolin Ding Janardhan Kulkarni and Sergey Yekhanin. 2017. Collecting Telemetry Data Privately. In NeurIPS. 3574--3583."},{"key":"e_1_2_1_17_1","volume-title":"Wainwright","author":"Duchi John C.","year":"2013","unstructured":"John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013. Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation. In NeurIPS. 1529--1537."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.2017.1389735"},{"key":"e_1_2_1_19_1","volume-title":"Theory of cryptography conference","author":"Dwork Cynthia","unstructured":"Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006. Calibrating noise to sensitivity in private data analysis. In Theory of cryptography conference. Springer, 265--284."},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"\u00dalfar Erlingsson Vitaly Feldman Ilya Mironov Ananth Raghunathan Kunal Talwar and Abhradeep Thakurta. 2019. Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity. In SODA. 2468--2479.","DOI":"10.1137\/1.9781611975482.151"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660267.2660348"},{"key":"e_1_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Alexandre V. Evfimievski Ramakrishnan Srikant Rakesh Agrawal and Johannes Gehrke. 2002. Privacy preserving mining of association rules. In KDD. 217--228.","DOI":"10.1145\/775047.775080"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1515\/popets-2016-0015"},{"key":"e_1_2_1_24_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16--18","author":"Gaboardi Marco","year":"2019","unstructured":"Marco Gaboardi, Ryan Rogers, and Or Sheffet. 2019. Locally Private Mean Estimation: \u017d-test and Tight Confidence Intervals. In The 22nd International Conference on Artificial Intelligence and Statistics, AISTATS 2019, 16--18 April 2019, Naha, Okinawa, Japan. 2545--2554."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/JSTSP.2015.2425831"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875258"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2504967"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536464"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1969.10500991"},{"key":"e_1_2_1_30_1","unstructured":"Matthew Joseph Janardhan Kulkarni Jieming Mao and Zhiwei Steven Wu. 2019. Locally Private Gaussian Estimation."},{"key":"e_1_2_1_31_1","volume-title":"The Role of Interactivity in Local Differential Privacy. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS)","author":"Joseph Matthew","year":"2019","unstructured":"Matthew Joseph, Jieming Mao, Seth Neel, and Aaron Roth. 2019. The Role of Interactivity in Local Differential Privacy. 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS) (2019), 94--105."},{"key":"e_1_2_1_32_1","article-title":"Exponential Separations in Local Privacy","volume":"18","author":"Joseph Matthew","year":"2022","unstructured":"Matthew Joseph, Jieming Mao, and Aaron Roth. 2022. Exponential Separations in Local Privacy. ACM Trans. Algorithms 18, 4, Article 32 (oct 2022), 17 pages.","journal-title":"ACM Trans. Algorithms"},{"key":"e_1_2_1_33_1","volume-title":"Retrieved","year":"2020","unstructured":"Kaggle. 2020. San Francisco Employee Compensation. (2020). Retrieved Feb 21, 2023 from https:\/\/www.kaggle.com\/datasets\/san-francisco\/sf-employee-compensation"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"S. P. Kasiviswanathan H. K. Lee K. Nissim S. Raskhodnikova and A. Smith. 2008. What Can We Learn Privately?. In FOCS. 531--540.","DOI":"10.1109\/FOCS.2008.27"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Zitao Li Tianhao Wang Milan Lopuha\u00e4-Zwakenberg Ninghui Li and Boris \u0160koric. 2020. Estimating Numerical Distributions under Local Differential Privacy. In SIGMOD. 621--635.","DOI":"10.1145\/3411497.3420215"},{"key":"e_1_2_1_36_1","volume-title":"A practical application of differential privacy to personalized online advertising. Cryptology ePrint Archive","author":"Lindell Yehuda","year":"2011","unstructured":"Yehuda Lindell and Eran Omri. 2011. A practical application of differential privacy to personalized online advertising. Cryptology ePrint Archive (2011)."},{"key":"e_1_2_1_37_1","doi-asserted-by":"crossref","unstructured":"Zhan Qin Yin Yang Ting Yu Issa Khalil Xiaokui Xiao and Kui Ren. 2016. Heavy Hitter Estimation over Set-Valued Data with Local Differential Privacy. In CCS. 192--203.","DOI":"10.1145\/2976749.2978409"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.18128\/D010.V9.0"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2017.35"},{"key":"e_1_2_1_40_1","unstructured":"Amazon Staff. 2018. Protecting data privacy. https:\/\/www.aboutamazon.com\/news\/amazon-ai\/protecting-data-privacy. (2018)."},{"key":"e_1_2_1_41_1","volume-title":"Retrieved","author":"Taxi and Limousine Commission (TLC).","year":"2022","unstructured":"Taxi and Limousine Commission (TLC). 2022. New York Taxi Dataset. (2022). Retrieved Feb 21, 2023 from https:\/\/www.nyc.gov\/site\/tlc\/about\/tlc-trip-record-data.page"},{"key":"e_1_2_1_42_1","unstructured":"Differential Privacy Team. 2018. Learning with privacy at scale. https:\/\/machinelearning.apple.com\/research\/learning-with-privacy-at-scale. (2018)."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2019.00063"},{"key":"e_1_2_1_44_1","unstructured":"Tianhao Wang Jeremiah Blocki Ninghui Li and Somesh Jha. 2017. Locally Differentially Private Protocols for Frequency Estimation. In USENIX Security. 729--745."},{"key":"e_1_2_1_45_1","doi-asserted-by":"crossref","unstructured":"Tianhao Wang Bolin Ding Jingren Zhou Cheng Hong Zhicong Huang Ninghui Li and Somesh Jha. 2019. Answering Multi-Dimensional Analytical Queries under Local Differential Privacy. In SIGMOD. 159--176.","DOI":"10.1145\/3299869.3319891"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2018.00035"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1965.10480775"},{"key":"e_1_2_1_48_1","volume-title":"AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation (Technical report). (2023). Retrieved","author":"Wei Fei","year":"2023","unstructured":"Fei Wei, Ergute Bao, Xiaokui Xiao, Yin Yang, and Bolin Ding. 2023. AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation (Technical report). (2023). Retrieved August 1, 2023 from https:\/\/github.com\/adaptiveldpmechanism\/vldb_2024_submission\/blob\/main\/technical_report.pdf"},{"key":"e_1_2_1_49_1","unstructured":"N.A. Weiss P.T. Holmes and M. Hardy. 2006. A Course in Probability. Pearson Addison Wesley."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.14778\/3407790.3407859"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.14778\/3352063.3352085"},{"key":"e_1_2_1_52_1","volume-title":"CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy. In CCS. 212--229.","author":"Zhang Zhikun","year":"2018","unstructured":"Zhikun Zhang, Tianhao Wang, Ninghui Li, Shibo He, and Jiming Chen. 2018. CALM: Consistent Adaptive Local Marginal for Marginal Release under Local Differential Privacy. In CCS. 212--229."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3659437.3659442","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,31]],"date-time":"2024-05-31T16:26:37Z","timestamp":1717172797000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3659437.3659442"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,4]]},"references-count":52,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2024,4]]}},"alternative-id":["10.14778\/3659437.3659442"],"URL":"https:\/\/doi.org\/10.14778\/3659437.3659442","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2024,4]]},"assertion":[{"value":"2024-05-31","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}