Online Distribution Learning with Local Private Constraints
Jin Sima Changlong Wu Olgica Milenkovic Wojciech Szpankowski
We study the problem of online conditional distribution estimation with
\emph{unbounded} label sets under local differential privacy. Let $\mathcal{F}$
be a distribution-valued function class with unbounded label set. We aim at
estimating an \emph{unknown} function $f\in \mathcal{F}$ in an online fashion
so that at time $t$ when the context $\boldsymbol{x}_t$ is provided we can
generate an estimate of $f(\boldsymbol{x}_t)$ under KL-divergence knowing only
a privatized version of the true labels sampling from $f(\boldsymbol{x}_t)$.
The ultimate objective is to minimize the cumulative KL-risk of a finite
horizon $T$. We show that under $(\epsilon,0)$-local differential privacy of
the privatized labels, the KL-risk grows as
$\tilde{\Theta}(\frac{1}{\epsilon}\sqrt{KT})$ upto poly-logarithmic factors
where $K=|\mathcal{F}|$. This is in stark contrast to the
$\tilde{\Theta}(\sqrt{T\log 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.