Online Distribution Learning with Local Private Constraints

We study the problem of online conditional distribution estimation with unbounded label sets under local differential privacy. Let F be a distribution-valued function class with unbounded label set. We aim at estimating an unknown function f∈ F in an online fashion so that at time t when the context boldsymbolxt is provided we can generate an estimate of f(boldsymbolxt) under KL-divergence knowing only a privatized version of the true labels sampling from f(boldsymbolxt). The ultimate objective is to minimize the cumulative KL-risk of a finite horizon T. We show that under (ε,0)-local differential privacy of the privatized labels, the KL-risk grows as tildeTheta(frac1ε√KT) upto poly-logarithmic factors where K=|F|. This is in stark contrast to the tildeTheta(√Tlog K) bound demonstrated by Wu et al. (2023a) for bounded label sets. As a byproduct, our results recover a nearly tight upper bound for the hypothesis selection problem of gopi et al. (2020) established only for the batch setting.