  We propose a novel Bayesian approach for the adaptive and online estimation
of the frequency distribution of a finite number of categories under the local
differential privacy (LDP) framework. The proposed algorithm performs Bayesian
parameter estimation via posterior sampling and adapts the randomization
mechanism for LDP based on the obtained posterior samples. We propose a
randomized mechanism for LDP which uses a subset of categories as an input and
whose performance depends on the selected subset and the true frequency
distribution. By using the posterior sample as an estimate of the frequency
distribution, the algorithm performs a computationally tractable subset
selection step to maximize the utility of the privatized response of the next
user. We propose several utility functions related to well-known information
metrics, such as (but not limited to) Fisher information matrix, total
variation distance, and information entropy. We compare each of these utility
metrics in terms of their computational complexity. We employ stochastic
gradient Langevin dynamics for posterior sampling, a computationally efficient
approximate Markov chain Monte Carlo method. We provide a theoretical analysis
showing that (i) the posterior distribution targeted by the algorithm converges
to the true parameter even for approximate posterior sampling, and (ii) the
algorithm selects the optimal subset with high probability if posterior
sampling is performed exactly. We also provide numerical results that
empirically demonstrate the estimation accuracy of our algorithm where we
compare it with nonadaptive and semi-adaptive approaches under experimental
settings with various combinations of privacy parameters and population
distribution parameters.
