# Bayesian Frequency Estimation Under Local Differential Privacy With an Adaptive Randomized Response Mechanism

arXiv: https://arxiv.org/abs/2405.07020 · HTML: https://mlsanity.com/paper/2405.07020/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 36 references that are in the map.
- First posted on arXiv 11 May 2024.

## Builds on (most cited first, 15 of 15)

- [A Tutorial on Thompson Sampling](https://mlsanity.com/paper/1707.02038/) (2017)
- [On the Theory and Practice of Privacy-Preserving Bayesian Data Analysis](https://mlsanity.com/paper/1603.07294/) (2016)
- [Fisher information under local differential privacy](https://mlsanity.com/paper/2005.10783/) (2020)
- [Unified lower bounds for interactive high-dimensional estimation under information constraints](https://mlsanity.com/paper/2010.06562/) (2020)
- [Locally Differentially Private Frequency Estimation with Consistency](https://mlsanity.com/paper/1905.08320/) (2019)
- [Marginal Release Under Local Differential Privacy](https://mlsanity.com/paper/1711.02952/) (2017)
- [Differentially Private Exponential Random Graphs](https://mlsanity.com/paper/1409.4696/) (2014)
- [Locally Private Gaussian Estimation](https://mlsanity.com/paper/1811.08382/) (2018)
- [Nonparametric extensions of randomized response for private confidence sets](https://mlsanity.com/paper/2202.08728/) (2022)
- [Sample and Threshold Differential Privacy: Histograms and applications](https://mlsanity.com/paper/2112.05693/) (2021)
- [Local Differential Privacy in Graph Neural Networks: a Reconstruction Approach](https://mlsanity.com/paper/2309.08569/) (2023)
- [Calibrate: Frequency Estimation and Heavy Hitter Identification with Local Differential Privacy via Incorporating Prior Knowledge](https://mlsanity.com/paper/1812.02055/) (2018)
- [Statistic Selection and MCMC for Differentially Private Bayesian Estimation](https://mlsanity.com/paper/2203.13377/) (2022)
- [AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation](https://mlsanity.com/paper/2404.01625/) (2024)
- [Differentially Private Online Bayesian Estimation With Adaptive Truncation](https://mlsanity.com/paper/2301.08202/) (2023)

## Built on by (most cited first, 1 of 1)

- [An Analytical Approach to Privacy and Performance Trade-Offs in Healthcare Data Sharing](https://mlsanity.com/paper/2508.18513/) (2025)

## Abstract (arXiv)

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 subset of categories that `predicts' the next user's 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 posterior sampling through stochastic gradient Langevin dynamics, a computationally efficient approximate Markov chain Monte Carlo (MCMC) method. 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.