Local differential privacy (LDP) is a strong notion of privacy for individual
users that often comes at the expense of a significant drop in utility. The
classical definition of LDP assumes that all elements in the data domain are
equally sensitive. However, in many applications, some symbols are more
sensitive than others. This work proposes a context-aware framework of local
differential privacy that allows a privacy designer to incorporate the
application's context into the privacy definition. For binary data domains, we
provide a universally optimal privatization scheme and highlight its
connections to Warner's randomized response (RR) and Mangat's improved
response. Motivated by geolocation and web search applications, for $k$-ary
data domains, we consider two special cases of context-aware LDP:
block-structured LDP and high-low LDP. We study discrete distribution
estimation and provide communication-efficient, sample-optimal schemes and
information-theoretic lower bounds for both models. We show that using
contextual information can require fewer samples than classical LDP to achieve
the same accuracy.

本文提出了一个上下文感知的局部差分隐私框架，允许隐私设计者将应用程序的上下文纳入到隐私定义中。针对二进制数据域，我们提供了一种普遍最优的隐私方案，并且针对 $k$-ary 数据域，我们研究了两种特殊情况下的局部差分隐私。我们研究了离散分布估计，并提供了通信效率高、样本最优的方案和信息论下界。我们展示了使用上下文信息可以比经典局部差分隐私更少地使用样本来达到相同的准确度。

上下文感知的本地差分隐私

Context-Aware Local Differential Privacy

We analyze the problem of discrete distribution estimation under $\ell_1$
loss. We provide non-asymptotic upper and lower bounds on the maximum risk of
the empirical distribution (the maximum likelihood estimator), and the minimax
risk in regimes where the alphabet size $S$ may grow with the number of
observations $n$. We show that among distributions with bounded entropy $H$,
the asymptotic maximum risk for the empirical distribution is $2H/\ln n$, while
the asymptotic minimax risk is $H/\ln n$. Moreover, Moreover, we show that a
hard-thresholding estimator oblivious to the unknown upper bound $H$, is
asymptotically minimax. However, if we constrain the estimates to lie in the
simplex of probability distributions, then the asymptotic minimax risk is again
$2H/\ln n$. We draw connections between our work and the literature on density
estimation, entropy estimation, total variation distance ($\ell_1$ divergence)
estimation, joint distribution estimation in stochastic processes, normal mean
estimation, and adaptive estimation.

该研究分析了离散分布估计问题，并提供了最大风险和最小极小风险的上下界，进而得出在特定条件下最大风险极小风险的渐近性能。通过该研究可得出在经验分布估计中的渐近最大风险和最小极小风险，并且通过对概率分量估计确定了渐近最小极小风险。