Online Distribution Learning with Local Privacy Constraints

Jin Sima, Changlong Wu, Olgica Milenkovic, Wojciech SzpankowskiAISTATS 2024 · OpenReview

Abstract

We study the problem of online conditional distribution estimation with unbounded label sets under local differential privacy (LDP). Given a distribution-valued function class $\mathcal{F}$ with an unbounded label set, our goal is to estimate an unknown function $f \in \mathcal{F}$ in an online fashion. At each time step $t$, we generate an estimate of $f(\mathbf{x}_t)$ using only a privatized version of the true labels. We show that under $(\epsilon, 0)$-LDP, the cumulative KL-risk is $\tilde{\Theta}(\frac{1}{\epsilon}\sqrt{KT})$, where $K=|\mathcal{F}|$. This represents a significant shift from the $\tilde{\Theta}(\sqrt{T\log K})$ bound known for bounded label sets. As a side-result, our approach recovers a nearly tight upper bound for the hypothesis selection problem, which has previously only been established for the batch setting.

Introduction

In modern machine learning, the ability to learn from user data while maintaining strict privacy is paramount. Local Differential Privacy (LDP) has emerged as a gold standard, ensuring that sensitive information—such as a user's specific action or label—is never shared in its raw form. Instead, the learner only receives a noisy, privatized version of the data.

While online distribution learning is well-understood in non-private settings or private settings with small, bounded label sets, a significant gap exists when the label set is "unbounded" (e.g., real numbers, natural language, or high-dimensional vectors). This paper addresses this gap, establishing the fundamental limits of online distribution estimation under LDP when the label space is arbitrarily large.

The Problem: Unbounded Labels and Privacy

The problem is modeled as a game between Nature, the User, and the Learner. At each time $t$:

  1. Nature selects a feature $\mathbf{x}_t$.
  2. The Learner provides an estimate $p_t$ of the true distribution $f(\mathbf{x}_t)$.
  3. A label $y_t$ is sampled from $f(\mathbf{x}_t)$.
  4. The User privatizes $y_t$ and sends the noisy version to the Learner.
  5. The Learner updates its model based on the privatized feedback.

The objective is to minimize the cumulative Kullback-Leibler (KL) risk over a horizon $T$. Previous research found that for bounded label sets, the risk scales slowly with $\sqrt{T \log K}$, where $K$ is the number of hypotheses. However, when the label set is unbounded, existing algorithms often yield "vacuous" bounds—mathematical guarantees that are less informative than a random guess. This paper seeks to find the fundamental limits of learning in this unbounded, private, online world.

Algorithmic Framework

To overcome the challenges of unbounded labels, the authors introduce two primary mechanisms:

1. Log-Likelihood Clipping

In distribution estimation, the loss function is typically the negative log-likelihood. With unbounded labels, these values can become infinitely large, making them impossible to privatize directly without introducing infinite noise. The authors employ a "clipping" technique that maps these log-likelihoods into a bounded range. This ensures the sensitivity of the data is controlled, allowing for effective privatization while preserving the underlying learning signal.

2. Modified EXP3 for Pure LDP

Standard private algorithms often add noise to the entire loss vector of all $K$ hypotheses at every step. In an LDP setting, this consumes the "privacy budget" $\epsilon$ too quickly, leading to high error. The authors adapt the EXP3 (Exponential-weight for Exploration and Exploitation) algorithm. Instead of revealing a privatized version of the entire loss vector, the mechanism reveals only one randomly selected component. This trick significantly reduces the noise required to maintain "pure" $\epsilon$-differential privacy, making the algorithm independent of the label set size $|Y|$.

Key Results: The $\sqrt{KT}$ Complexity

The paper's most striking insight is the jump in complexity when moving from bounded to unbounded label sets.

  • The Lower Bound: The authors prove that for any algorithm, the cumulative KL-risk must be at least $\Omega(\frac{1}{\epsilon} \sqrt{KT})$. This establishes the fundamental "speed limit" for private online distribution learning and shows that the dependence on $K$ shifts from logarithmic to square-root when labels are unbounded.
  • The Upper Bound: The proposed algorithm achieves a risk of $O(\frac{1}{\epsilon} \sqrt{KT} \text{ poly-log}(KT))$. Because the upper and lower bounds both scale with $\sqrt{KT}$, the algorithm is considered nearly optimal.
  • Independence of Label Size: Unlike previous work, these bounds do not contain a term for $|Y|$, meaning the algorithm works just as well for an infinite number of labels as it does for a small set.

Discussion and Future Directions

This research highlights a phase transition in private learning: the transition from bounded to unbounded label sets necessitates a change in algorithmic strategy. While this work provides a nearly tight bound for finite hypothesis classes, several challenges remain:

  • Infinite Hypothesis Classes: Extending these results to infinite classes (like all possible neural network weights) using measures like the Littlestone dimension is a natural next step.
  • Total Variation (TV) Risk Gap: The authors provide a bound for Average TV risk but acknowledge it might not be tight, leaving this as an open challenge for the community.
  • Computational Efficiency: While mathematically sound, the clipping and sampling process for complex, high-dimensional distributions could be computationally expensive in practice. Future work could look at more efficient approximations of these functions.

Summary updated

Abstract

We study the problem of online conditional distribution estimation with \emph{unbounded} label sets under local differential privacy. The problem may be succinctly stated as follows. Let $\mathcal{F}$ be a distribution-valued function class with an unbounded label set. Our aim is to estimate an \emph{unknown} function $f\in \mathcal{F}$ in an online fashion. More precisely, at time $t$, given a sample ${\mathbf{x}}_t$, we generate an estimate of $f({\mathbf{x}}_t)$ using only a \emph{privatized} version of the true \emph{labels} sampled from $f({\mathbf{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 $\tilde{\Theta}(\frac{1}{\epsilon}\sqrt{KT}),$ up to poly-logarithmic factors, where $K=|\mathcal{F}|$. This result significantly differs from the $\tilde{\Theta}(\sqrt{T\log K})$ bound derived in Wu et al., (2023a) for \emph{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 \emph{batch} setting.
BibTeX
@inproceedings{sima2024online,
  author = {Jin Sima and Changlong Wu and Olgica Milenkovic and Wojciech Szpankowski},
  title = {{Online Distribution Learning with Local Privacy Constraints}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=ePdg41EYUj},
}
Figure