# Online Distribution Learning with Local Private Constraints

arXiv: https://arxiv.org/abs/2402.00315 · HTML: https://mlsanity.com/paper/2402.00315/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 26 references that are in the map.
- First posted on arXiv 1 Feb 2024.

## Builds on (most cited first, 13 of 13)

- [The Statistical Complexity of Interactive Decision Making](https://mlsanity.com/paper/2112.13487/) (2021)
- [Deep Learning with Label Differential Privacy](https://mlsanity.com/paper/2102.06062/) (2021)
- [The Power of Factorization Mechanisms in Local and Central Differential Privacy](https://mlsanity.com/paper/1911.08339/) (2019)
- [Label differential privacy via clustering](https://mlsanity.com/paper/2110.02159/) (2021)
- [Locally Private Hypothesis Selection](https://mlsanity.com/paper/2002.09465/) (2020)
- [Private Online Prediction from Experts: Separations and Faster Rates](https://mlsanity.com/paper/2210.13537/) (2022)
- [Expected Worst Case Regret via Stochastic Sequential Covering](https://mlsanity.com/paper/2209.04417/) (2022)
- [Sequential Probability Assignment with Binary Alphabets and Large Classes of Experts](https://mlsanity.com/paper/1501.07340/) (2015)
- [Does Label Differential Privacy Prevent Label Inference Attacks?](https://mlsanity.com/paper/2202.12968/) (2022)
- [Littlestone Classes are Privately Online Learnable](https://mlsanity.com/paper/2106.13513/) (2021)
- [Relaxing the I.I.D. Assumption: Adaptively Minimax Optimal Regret via Root-Entropic Regularization](https://mlsanity.com/paper/2007.06552/) (2020)
- [Smoothed Analysis of Sequential Probability Assignment](https://mlsanity.com/paper/2303.04845/) (2023)
- [On Differentially Private Online Predictions](https://mlsanity.com/paper/2302.14099/) (2023)

## Abstract (arXiv)

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.