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 is an element of 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 (epsilon, 0)-local differential privacy for the labels, the KL-risk equals (Theta) over tilde (1/epsilon root KT), up to poly-logarithmic factors, where K = vertical bar F vertical bar. This result significantly differs from the (Theta) over tilde(root T logK) 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.