{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,19]],"date-time":"2025-11-19T07:11:58Z","timestamp":1763536318127,"version":"3.41.0"},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2025,1,11]],"date-time":"2025-01-11T00:00:00Z","timestamp":1736553600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2025,2,28]]},"abstract":"<jats:p>\n            Frequency estimation plays a critical role in many applications involving personal and private categorical data. Such data are often collected sequentially over time, making it valuable to estimate their distribution online while preserving privacy. We propose AdOBEst-LDP, a new algorithm for adaptive, online Bayesian estimation of categorical distributions under local differential privacy (LDP). The key idea behind AdOBEst-LDP is to enhance the utility of future privatized categorical data by leveraging inference from previously collected privatized data. To achieve this, AdOBEst-LDP uses a new adaptive LDP mechanism to collect privatized data. This LDP mechanism constrains its output to a\n            <jats:italic>subset<\/jats:italic>\n            of categories that \u201cpredicts\u201d the next user\u2019s data. By adapting the subset selection process to the past privatized data via Bayesian estimation, the algorithm improves the utility of future privatized data. To quantify utility, we explore various well-known information metrics, including (but not limited to) the Fisher information matrix, total variation distance, and information entropy. For Bayesian estimation, we utilize\n            <jats:italic>posterior sampling<\/jats:italic>\n            through stochastic gradient Langevin dynamics, a computationally efficient approximate Markov chain Monte Carlo (MCMC) method.\n          <\/jats:p>\n          <jats:p>We provide a theoretical analysis showing that (i) the posterior distribution of the category probabilities targeted with Bayesian estimation converges to the true probabilities even for approximate posterior sampling, and (ii) AdOBEst-LDP eventually selects the optimal subset for its LDP mechanism with high probability if posterior sampling is performed exactly. We also present numerical results to validate the estimation accuracy of AdOBEst-LDP. Our comparisons show its superior performance against non-adaptive and semi-adaptive competitors across different privacy levels and distributional parameters.<\/jats:p>","DOI":"10.1145\/3706584","type":"journal-article","created":{"date-parts":[[2024,12,3]],"date-time":"2024-12-03T14:41:21Z","timestamp":1733236881000},"page":"1-40","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Bayesian Frequency Estimation under Local Differential Privacy with an Adaptive Randomized Response Mechanism"],"prefix":"10.1145","volume":"19","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5248-3161","authenticated-orcid":false,"given":"Soner","family":"Aydin","sequence":"first","affiliation":[{"name":"Faculty of Engineering and Natural Sciences, Sabanc\u0131 University, \u0130stanbul, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-7980-8990","authenticated-orcid":false,"given":"Sinan","family":"Y\u0131ld\u0131r\u0131m","sequence":"additional","affiliation":[{"name":"Faculty of Engineering and Natural Sciences, Sabanc\u0131 University, \u0130stanbul, Turkey"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,1,11]]},"reference":[{"key":"e_1_3_3_2_2","first-page":"51133","volume-title":"Advances in Neural Information Processing Systems","volume":"36","author":"Acharya Jayadev","year":"2023","unstructured":"Jayadev Acharya, Cl\u00e9ment L. Canonne, Ziteng Sun, and Himanshu Tyagi. 2023. Unified lower bounds for interactive high-dimensional estimation under information constraints. In Advances in Neural Information Processing Systems. A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (Eds.), Vol. 36, Curran Associates, Inc., New Orleans, US, 51133\u201351165. Retrieved from https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2023\/file\/a07e87ecfa8a651d62257571669b0150-Paper-Conference.pdf"},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11222-022-10129-8"},{"key":"e_1_3_3_4_2","doi-asserted-by":"publisher","DOI":"10.1109\/JSAIT.2020.3039461"},{"key":"e_1_3_3_5_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978032.1"},{"key":"e_1_3_3_6_2","first-page":"1420","volume-title":"Proceedings of the International Conference on Artificial Intelligence and Statistics","author":"Cormode Graham","year":"2022","unstructured":"Graham Cormode and Akash Bharadwaj. 2022. Sample-and-threshold differential privacy: Histograms and applications. In Proceedings of the International Conference on Artificial Intelligence and Statistics. PMLR, 1420\u20131431."},{"key":"e_1_3_3_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196906"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1007\/11787006_1"},{"key":"e_1_3_3_9_2","unstructured":"James Foulds Joseph Geumlek Max Welling and Kamalika Chaudhuri. 2016. On the theory and practice of privacy-preserving Bayesian data analysis. arXiv:1603.07294. Retrieved from https:\/\/arxiv.org\/abs\/1603.07294"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.2307\/3318681"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2019.8737527"},{"key":"e_1_3_3_12_2","volume-title":"Advances in Neural Information Processing Systems","author":"Joseph Matthew","year":"2019","unstructured":"Matthew Joseph, Janardhan Kulkarni, Jieming Mao, and Steven Z. Wu. 2019. Locally private gaussian estimation. In Advances in Neural Information Processing Systems. H. Wallach, H. Larochelle, A. Beygelzimer, F. d\u2019Alch\u00e9-Buc, E. Fox, and R. Garnett (Eds.), Vol. 32, Curran Associates, Inc. Retrieved from https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2019\/file\/a588a6199feff5ba48402883d9b72700-Paper.pdf"},{"key":"e_1_3_3_13_2","doi-asserted-by":"publisher","DOI":"10.5555\/2946645.2946662"},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-11257-2_12"},{"key":"e_1_3_3_15_2","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"e_1_3_3_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00362-009-0203-2"},{"key":"e_1_3_3_17_2","doi-asserted-by":"publisher","DOI":"10.3390\/math10224216"},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.1088\/1402-4896\/ad1c29"},{"key":"e_1_3_3_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3559613.3563194"},{"key":"e_1_3_3_20_2","first-page":"11","volume-title":"Proceedings of the 37th International Conference on Machine Learning (ICML\u201920)","author":"Mazumdar Eric","year":"2020","unstructured":"Eric Mazumdar, Aldo Pacchiano, Yi-An Ma, Peter L. Bartlett, and Michael I. Jordan. 2020. On approximate Thompson sampling with langevin algorithms. In Proceedings of the 37th International Conference on Machine Learning (ICML\u201920). JMLR.org, Article 631, 11 pages."},{"key":"e_1_3_3_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00009-017-1043-2"},{"key":"e_1_3_3_22_2","doi-asserted-by":"crossref","unstructured":"Daniel Russo Benjamin Van Roy Abbas Kazerouni Ian Osband and Zheng Wen. 2018. A tutorial on Thompson sampling. Foundations and Trends in Machine Learning 11 1 (2018) 1\u201396. Retrieved from http:\/\/dblp.uni-trier.de\/db\/journals\/ftml\/ftml11.html#RussoRKOW18","DOI":"10.1561\/2200000070"},{"key":"e_1_3_3_23_2","unstructured":"Lukas Steinberger. 2024. Efficiency in local differential privacy. arXiv:2301.10600. Retrieved from https:\/\/arxiv.org\/abs\/2301.10600"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2023.3320669"},{"key":"e_1_3_3_25_2","unstructured":"Shaowei Wang Liusheng Huang Pengzhan Wang Yiwen Nie Hongli Xu Wei Yang Xiang-Yang Li and Chunming Qiao. 2016. Mutual information optimally local private discrete distribution estimation. arXiv:1607.08025. Retrieved from https:\/\/arxiv.org\/abs\/1607.08025"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1109\/TMC.2023.3342056"},{"key":"e_1_3_3_27_2","first-page":"729","volume-title":"Proceedings of the 26th USENIX Security Symposium (USENIX Security \u201917)","author":"Wang Tianhao","year":"2017","unstructured":"Tianhao Wang, Jeremiah Blocki, Ninghui Li, and Somesh Jha. 2017. Locally differentially private protocols for frequency estimation. In Proceedings of the 26th USENIX Security Symposium (USENIX Security \u201917), 729\u2013745."},{"key":"e_1_3_3_28_2","doi-asserted-by":"publisher","DOI":"10.14722\/ndss.2020.24157"},{"key":"e_1_3_3_29_2","first-page":"36748","volume-title":"Proceedings of the International Conference on Machine Learning.","author":"Waudby-Smith Ian","year":"2023","unstructured":"Ian Waudby-Smith, Steven Wu, and Aaditya Ramdas. 2023. Nonparametric extensions of randomized response for private confidence sets. In Proceedings of the International Conference on Machine Learning. PMLR, 36748\u201336789."},{"key":"e_1_3_3_30_2","unstructured":"Fei Wei Ergute Bao Xiaokui Xiao Yin Yang and Bolin Ding. 2024. AAA: An adaptive mechanism for locally differential private mean estimation. arXiv:2404.01625. Retrieved from https:\/\/arxiv.org\/abs\/2404.01625"},{"key":"e_1_3_3_31_2","first-page":"681","volume-title":"Proceedings of the 28th International Conference on International Conference on Machine Learning (ICML\u201911)","author":"Welling Max","year":"2011","unstructured":"Max Welling and Yee Whye Teh. 2011. Bayesian learning via stochastic gradient langevin dynamics. In Proceedings of the 28th International Conference on International Conference on Machine Learning (ICML\u201911). Omnipress, Madison, WI, 681\u2013688."},{"key":"e_1_3_3_32_2","volume-title":"Advances in Neural Information Processing Systems","volume":"23","author":"Williams Oliver","year":"2010","unstructured":"Oliver Williams and Frank Mcsherry. 2010. Probabilistic inference and differential privacy. In Advances in Neural Information Processing Systems. J. Lafferty, C. Williams, J. Shawe-Taylor, R. Zemel, and A. Culotta (Eds.), Vol. 23, Curran Associates, Inc. Retrieved from https:\/\/proceedings.neurips.cc\/paper\/2010\/file\/fb60d411a5c5b72b2e7d3527cfc84fd0-Paper.pdf"},{"key":"e_1_3_3_33_2","doi-asserted-by":"publisher","DOI":"10.55730\/1300-0632.4054"},{"key":"e_1_3_3_34_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11390-023-1346-7"},{"key":"e_1_3_3_35_2","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2023.3324726"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3706584","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3706584","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:56:51Z","timestamp":1750298211000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3706584"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,11]]},"references-count":34,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,2,28]]}},"alternative-id":["10.1145\/3706584"],"URL":"https:\/\/doi.org\/10.1145\/3706584","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2025,1,11]]},"assertion":[{"value":"2024-05-11","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2024-11-21","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-01-11","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}