This talk concerns online parameter estimation under data privacy constraints. In particular, local differential privacy (LDP) will be considered the definition of data privacy, and the main research question is how to do efficient online estimation of a categorical distribution under the LDP constraint.

He will introduce AdOBEst-LDP, a new algorithm for adaptive, online Bayesian estimation of categorical distributions under 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.

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.

(joint w. Soner Aydın)

Related Paper: https://dl.acm.org/doi/10.1145/3706584

Soner Aydin and Sinan Yıldırım. 2025. Bayesian Frequency Estimation under Local Differential Privacy with an Adaptive Randomized Response Mechanism. ACM Trans. Knowl. Discov. Data 19, 2, Article 28 (February 2025), 40 pages. https://doi.org/10.1145/3706584