Online Distribution Learning with Local Privacy Constraints

We study the problem of online conditional distribution estimation with unbounded label sets under local differential privacy. The problem may be succinctly stated as follows. Let F be a distribution-valued function class with an unbounded label set. Our aim is to estimate an unknown function f ∈ F in an online fashion. More precisely, at time t, given a sample x_t, we generate an estimate of f(x_t) using only a privatized version of the true labels sampled from f(x_t). The objective is to minimize the cumulative KL-risk of a finite horizon T. We show that under (ϵ, 0)-local differential privacy for the labels, the KL-risk equals Θ̃(¹_ϵ^√KT), up to poly-logarithmic factors, where K = |F|. This result significantly differs from the Θ̃(√T log K) bound derived in Wu et al. (2023a) for bounded label sets. As a side-result, our approach recovers a nearly tight upper bound for the hypothesis selection problem of Gopi et al. (2020), which has only been established for the batch setting.