PaperlayerView exact revision on arXiv

Source-linked AI summary

Utility-Optimized Local Differential Privacy Mechanisms for Distribution Estimation

Takao Murakami, Yusuke Kawamoto

arXiv:1807.11317v7cs.DBcs.CRcs.ITmath.IT

TL;DR

LDP protects users without a trusted third party, but treats all personal data as equally sensitive, limiting utility. The paper introduces ULDP mechanisms for shared and user-specific sensitivity distinctions. It reports higher utility than LDP when non-sensitive data are abundant, and near non-private utility in a stated low-privacy regime when most data are non-sensitive.

  • Problem

    LDP treats all personal data as equally sensitive, leaving room to improve utility when many values are non-sensitive.

    Source: §1 · p. 1

  • Method

    The paper introduces ULDP mechanisms for shared sensitivity distinctions and a personalized semantic-tag mechanism for user-specific distinctions.

    Source: §1 · p. 2, §5.1 · p. 8

  • Results

    When non-sensitive data are abundant, the mechanisms provide much higher utility than state-of-the-art LDP; when most data are non-sensitive, they nearly match non-private utility at ε = ln |X| in the low privacy regime.

    Source: §1 · p. 2

  • Takeaways & Limitations

    ULDP protects sensitive data while allowing non-sensitive values to remain invertible, which the paper identifies as key to high-utility local distribution estimation.

    Source: §3.1 · p. 4

    ULDP is not applicable when users cannot decide what is sensitive; the paper says LDP can be applied in that scenario.

    Source: §1 · p. 2

Abstract

from arXiv · show

LDP (Local Differential Privacy) has been widely studied to estimate statistics of personal data (e.g., distribution underlying the data) while protecting users' privacy. Although LDP does not require a trusted third party, it regards all personal data equally sensitive, which causes excessive obfuscation hence the loss of utility. In this paper, we introduce the notion of ULDP (Utility-optimized LDP), which provides a privacy guarantee equivalent to LDP only for sensitive data. We first consider the setting where all users use the same obfuscation mechanism, and propose two mechanisms providing ULDP: utility-optimized randomized response and utility-optimized RAPPOR. We then consider the setting where the distinction between sensitive and non-sensitive data can be different from user to user. For this setting, we propose a personalized ULDP mechanism with semantic tags to estimate the distribution of personal data with high utility while keeping secret what is sensitive for each user. We show theoretically and experimentally that our mechanisms provide much higher utility than the existing LDP mechanisms when there are a lot of non-sensitive data. We also show that when most of the data are non-sensitive, our mechanisms even provide almost the same utility as non-private mechanisms in the low privacy regime.

1. INTRODUCTION

LDP protects data without a trusted administrator, but treats all values as equally sensitive, limiting utility. The paper introduces ULDP mechanisms for shared and user-specific sensitivity, with higher reported utility when much data is non-sensitive.

1. INTRODUCTION

  • The paper introduces ULDP, which provides a privacy guarantee equivalent to LDP only for sensitive data in discrete distribution estimation.It targets local obfuscation mechanisms that improve utility while retaining privacy for sensitive values.Source: §1 · p. 2
  • When non-sensitive data are abundant, ULDP mechanisms provide much higher utility than state-of-the-art LDP mechanisms; when most data are non-sensitive, they nearly match non-private utility at ε = ln |X| in the low privacy regime.The paper also reports that experiments on two large-scale datasets demonstrate the mechanisms’ effectiveness.Source: §1 · p. 2
  • For users sharing the same sensitivity distinction, the paper proposes utility-optimized randomized response and utility-optimized RAPPOR.These mechanisms are compared with RR for multiple alphabets and RAPPOR.Source: §1 · p. 2
  • For user-specific sensitivity distinctions, the PUM uses semantic tags to keep each user’s sensitive values secret while enabling distribution estimation using tag-conditioned background knowledge.The paper also theoretically analyzes PUM’s data utility.Source: §1 · p. 2
  • The stated scope assumes users can identify what is sensitive; when they cannot, the paper says ULDP cannot be used and LDP can be applied instead.The paper also assumes one datum per user and independent personal data, noting that correlated data may require further work.Source: §1 · p. 2

2. PRELIMINARIES

The preliminaries establish the data and privacy setting, utility measures, candidate obfuscation mechanisms, and estimation procedures used in the paper.

2.1 Notations

  • The setup distinguishes common sensitive values from user-specific sensitive values and considers common or personalized mechanisms; users’ data are i.i.d. from distribution p, and the collector estimates p from obfuscated reports.Continuous data are discretized into bins, and the setup assumes each user sends a single datum.Source: §2.1 · p. 3

2.2 Privacy Measures

  • ε-LDP bounds output-probability ratios across any input pair, and smaller ε provides stronger privacy by making inputs more equally likely given an output.The preliminaries define ε-LDP for an obfuscation mechanism from X to Y.Source: §2.2 · p. 3

2.3 Utility Measures

  • Utility is measured using l1 and l2 losses between estimated and true distributions; experiments report total variation from sample-mean l1 loss and also evaluate MSE.The theoretical analysis takes expectation over obfuscated data realizations.Source: §2.3 · p. 3

2.4 Obfuscation Mechanisms

  • Generalized RAPPOR maps each input category to a one-hot vector and probabilistically flips its bits; randomized response outputs within the input alphabet, and both are presented as LDP mechanisms.For generalized RAPPOR, θ is the probability of keeping a 1 unchanged, while ψ is computed from θ and ε.Source: §2.4 · p. 3

2.5 Distribution Estimation Methods

  • Empirical estimation recovers p from the empirical distribution of obfuscated data, while EM estimates p within the probability simplex and therefore keeps estimates non-negative.Empirical estimates can be negative with few users; the paper uses empirical estimation in theory and empirical, thresholded, and EM methods in experiments.Source: §2.5 · p. 4

3. UTILITY-OPTIMIZED LDP (ULDP)

ULDP applies an LDP-equivalent privacy guarantee to sensitive data while allowing invertible outputs for non-sensitive data. Its definition supports composition and post-processing, and its estimation-loss bounds depend on the sensitive-data domain.

3.1 Definition

  • Sensitive inputs map only to protected outputs, while invertible outputs can reveal non-sensitive inputs to improve estimation accuracy.The mechanism provides an ε-LDP guarantee over protected outputs for sensitive inputs.Source: §3.1 · p. 4
  • ULDP provides no privacy guarantee for non-sensitive data, whose inputs may be revealed by invertible outputs.The paper frames protecting only the minimum necessary data as key to high-utility local distribution estimation.Source: §3.1 · p. 4

3.2 Basic Properties of ULDP

  • Sequential composition adds privacy parameters: mechanisms with ε0- and ε1-ULDP guarantees compose to an (ε0 + ε1)-ULDP guarantee.The protected output set for the composition consists of pairs whose component outputs are both protected.Source: §3.2 · p. 5
  • Post-processing preserves ULDP when it preserves protected and invertible data types, with invertible outputs remaining invertible for utility.The privacy guarantee for protected outputs is preserved by any post-processing algorithm.Source: §3.2 · p. 5
  • ULDP outputs can be integrated with LDP-obfuscated data from another collector for analysis under LDP.Source: §3.2 · p. 5
  • In the high-privacy regime, utility-optimized RAPPOR achieves ULDP's l1 and l2 lower bounds.Source: §3.2 · p. 5

4. UTILITY-OPTIMIZED MECHANISMS

The utility-optimized mechanisms outperform standard RR and RAPPOR when non-sensitive data are plentiful, and approach non-private utility in the low-privacy regime under the stated conditions. They adapt RR and RAPPOR by applying privacy protection to sensitive data while permitting more informative outputs for non-sensitive data.

4.1 Utility-Optimized Randomized Response

  • Utility-optimized RR generalizes Mangat’s randomized response to |X|-ary alphabets with |XS| sensitive symbols.It applies ε-RR to sensitive symbols and can map non-sensitive inputs into the protected set or leave them unchanged.Source: §4.1 · p. 5

4.2 Utility-Optimized RAPPOR

  • Utility-optimized RAPPOR applies generalized RAPPOR to sensitive inputs and probabilistically maps non-sensitive inputs into protected outputs.Its output alphabet is {0, 1}|X|, and its protected outputs have zeros in the positions corresponding to non-sensitive symbols.Source: §4.2 · pp. 5–6, Figure 3 · p. 6

4.3 Utility Analysis

  • The analysis uses empirical estimation, and the authors note that other mechanisms might achieve better utility with a different estimator.Source: §4.3 · p. 6
  • In the high-privacy regime, uRAP’s worst-case expected l1 loss is order-optimal among mechanisms with the same ULDP guarantee.The paper reports the rate Θ(|XS|/(nε^2)) for that loss.Source: §4.3 · p. 7
  • When |XS| ≪ |X|, uRR and uRAP provide much higher utility than RR and RAPPOR; in the low-privacy regime they approach non-private utility under the stated conditions.For uRR, the condition is ε = ln |X|; for uRAP, it is ε = ln |X| and |XS| ≪ |X|^4.Source: §4.3 · pp. 6–7

5. PERSONALIZED ULDP MECHANISMS

For user-specific sensitive sets, PUM hides what is sensitive while enabling distribution estimation through a user-specific preprocessor, a shared utility-optimized mechanism, and tag-conditioned background knowledge. The section establishes its privacy properties, a distribution estimator, and an l1 error bound that weights tag-prior error by estimated bot mass.

5.1 PUM with κ Semantic Tags

  • Each user's preprocessor maps sensitive values into one of κ tag-associated bots and leaves other values unchanged, then shared Qcmn obfuscates the intermediate data.The user keeps the preprocessor secret because its leakage can reveal which values map to each bot.Source: §5.1 · p. 8
  • Keeping each preprocessor secret hides what is sensitive, while tag-conditioned background knowledge lets the collector estimate p from obfuscated data Y.The common mechanism is available to the data collector; the user-specific preprocessor is not.Source: §5.1 · p. 8

5.2 Privacy Properties

  • For protected outputs YP, PUM provides ULDP and DP across users' mechanisms, so outputs reveal almost no information about sensitive inputs or which user's mechanism was used.The collector cannot infer either the sensitive input or its intermediate representation from protected output.Source: §5.2 · p. 8
  • Invertible outputs reveal a non-sensitive value and that it is not sensitive; in the 625-region location setting, one disclosure still leaves 624 possible homes.The paper notes that the remaining candidates are still numerous, and the common mechanism cannot further narrow them.Source: §5.2 · pp. 8–9

5.3 Distribution Estimation

  • The estimator first recovers intermediate-data distribution r from Y using Qcmn, then estimates p using background estimates πk conditioned on each bot's tag.Without background estimates for some bots, it uses r over non-sensitive values proportionally; without any, it discards bot estimates and renormalizes.Source: §5.3 · p. 9

5.4 Utility Analysis

  • The l1 error bound adds intermediate-distribution error to tag-prior errors weighted by estimated bot mass; accurate tag priors make the second term small.That term can also be small when bot mass is low, even without background knowledge; systematic bias in πk can increase its estimation error.Source: §5.4 · p. 9

6. EXPERIMENTAL EVALUATION

Experiments on Foursquare and US Census data evaluate common and personalized mechanisms using total variation. Utility-optimized mechanisms generally outperform existing LDP methods, with performance varying by sensitive-data prevalence, attribute count, and personalized background knowledge.

6.1 Experimental Set-up

  • The evaluation uses Foursquare check-ins and US Census responses, estimates distributions from sampled users, and measures total variation over repeated obfuscation realizations.The common-mechanism experiments compare RR, RAPPOR, uRR, and uRAP using empirical, thresholded empirical, and EM estimation.Source: §6.1 · pp. 9–10, §6.2 · p. 10

6.2 Experimental Results

  • The utility-optimized mechanisms outperform existing methods by one or two orders of magnitude; at ǫ = ln |X|, uRR nearly matches the non-private mechanism.The gains are especially pronounced on Foursquare, where sensitive regions are 15/625 of the alphabet.Source: Figure 5 · p. 10, §6.2 · p. 10
  • At ǫ = 0.1, uRAP performs best, while at ǫ = ln |X|, uRR performs best; uRR approaches non-private performance below 100 sensitive values, and uRAP below 20.uRAP performance worsens rapidly as the number of sensitive values increases.Source: §6.2 · p. 10, Figure 6 · p. 11
  • As attributes increase, total variation generally rises, but uRAP remains effective; with nine attributes at ǫ = 0.1, uRAP stays well below 1 while RR, RAPPOR, and uRR are nearly 1.For ǫ = 1.0 or 6.0, uRAP is robust to increasing attribute count at the same privacy budget.Source: §6.2 · pp. 10–11, Figure 7 · p. 11
  • For the personalized mechanism, POI-based background knowledge yields performance between having no knowledge and using the true distribution; below ǫ = 1, all three perform almost identically.The POI distributions are venue data used as estimates of the user-specific bot distributions.Source: Figure 8 · p. 11, §6.2 · p. 11
  • In every evaluated method, the empirical l1 loss is below the sum of the two terms in Theorem 1’s bound.The table reports the l1 loss and both bound terms for ǫ = ln |X| with EM reconstruction.Source: §6.2 · p. 11, Table 1 · p. 11

7. DISCUSSIONS

The discussion extends ULDP to users sending multiple data and examines how that affects utility and secrecy. It also identifies limits involving correlations among data and attributes.

On the case of multiple data per user

  • With t reports, composing mechanisms at privacy budget ǫ/t yields (XS, (YP)t, ǫ)-ULDP, but the lower bound on estimation loss increases with t.The authors therefore note that t cannot be large in practice for distribution estimation.Source: §7 · p. 12
  • A collector learns at most tI distinct invertible values and, for a user's possible-value set T(i), no more than |T(i)| non-sensitive values.The home remains strongly secret if either tI or |T(i)| is much smaller than |X|.Source: §7 · p. 12
  • Protected reports reveal almost no information about sensitive data, while Qcmn reveals none; together they cannot reduce home candidates below max{|X| − tI, |X| − |T(i)|}.The text also states that the home is strongly secret when either tI or |T(i)| is small.Source: §7 · p. 12

On the correlation between XS and XN

  • If a disclosed non-sensitive region is near a sensitive one, an adversary may infer approximate location, but not the exact location when regions are large enough.The experiments used regions about 400m × 450m; exact-location protection can also mark regions near sensitive locations as sensitive.Source: §7 · p. 12
  • For the US Census experiments, combining four category IDs into one per user and assuming independent user data removes within-user attribute correlation.The authors consequently conclude that sensitive data are strongly protected in both their Foursquare and US Census experiments.Source: §7 · p. 12
  • Total category IDs grow exponentially with the number of attributes, and correlated users may require incorporating Pufferfish privacy into ULDP.For many attributes, the authors suggest independently obfuscating each attribute while accounting for inter-attribute correlation.Source: §7 · p. 12

8. CONCLUSION

The conclusion presents ULDP as LDP-equivalent protection for sensitive data and reports theoretical and experimental utility evaluation. The appendix states core ULDP properties, including sequential composition.

8. CONCLUSION

  • ULDP provides privacy equivalent to LDP only for sensitive data, and the paper proposes common and personalized mechanisms evaluated theoretically and experimentally.The paper's basic notation is collected in Table 2.Source: §8 · p. 12, A. NOTATIONS · p. 14

B. PROPERTIES OF ULDP

  • The appendix states that ULDP has adaptive sequential composition, post-processing, and compatibility with LDP, and that utility-optimized RR and RAPPOR provide ULDP.The supplied sequential-composition proposition gives the composed-budget guarantee.Source: B. PROPERTIES OF ULDP · p. 14, §B.1 · p. 14

B.1 Sequential Composition

  • Sequentially composing mechanisms with privacy budgets ε0 and ε1 yields ULDP with total budget ε0 + ε1.The second mechanism may depend on the first output.Source: §B.1 · p. 14

B.2 Post-processing

The appendix establishes that type-preserving post-processing preserves ULDP, and that combining ULDP with LDP gives a summed privacy budget. It also states ULDP guarantees for utility-optimized RR and RAPPOR.

B.2 Post-processing

  • Post-processing preserves ULDP when the randomized algorithm preserves protected and invertible data types.The composite mechanism retains ε-ULDP for the resulting protected outputs.Source: §B.2 · pp. 14–15

B.3 Compatibility with LDP

  • Combining an (XS, YP, ǫA)-ULDP mechanism with an ǫB-LDP mechanism protects sensitive data under (ǫA + ǫB)-LDP after data integration.The proposition bounds the likelihood ratio for paired outputs from both mechanisms.Source: §B.3 · p. 15

B.4 ULDP of the utility-optimized RR

  • The utility-optimized RR provides (XS, XS, ǫ)-ULDP.Source: §B.4 · p. 15

B.5 ULDP of the utility-optimized RAPPOR

  • The utility-optimized RAPPOR provides (XS, YP, ǫ)-ULDP, with YP defined by equation (7).Source: §B.5 · p. 15

C. RELATIONSHIP BETWEEN LDP, ULDP AND OSLDP

This section relates LDP, ULDP, and OSLDP, describing ULDP’s protection for sensitive data and its utility advantages when the sensitive domain is small. It also compares utility-optimized and standard RR across privacy regimes and characterizes l1 loss for utility-optimized RR and RAPPOR.

C. RELATIONSHIP BETWEEN LDP, ULDP AND OSLDP

D. L1 LOSSOF THEUTILITY-OPTIMIZED MECHANISMS

D.1 l1 loss of the utility-optimized RR

  • For uRR, the authors derive expected l1 loss under empirical estimation, with the expression parameterized by ε, |XS|, and e^ε − 1.Source: §D.1 · p. 18

D.1.1 Maximum of the l1 loss

  • For 0 < ε < ln(|XN| + 1) and |XS| ≤ |XN|, worst-case uRR l1 loss occurs at the uniform distribution over XN; for ε ≥ ln(|XN| + 1), it occurs at a mixture of uniform distributions over XS and XN.Source: §D.1.1 · pp. 18, 20

D.1.2 l1 loss in the high privacy regime

  • In the high-privacy regime ε ≈ 0, uRR’s worst-case l1 loss is analyzed separately for |XS| ≤ |XN|, where pUN maximizes it, and |XS| > |XN|, where p* maximizes it.Source: §D.1.2 · p. 20
  • When ǫ ≈ 0 and |XS| ≪ |X|, the expected l1 loss of utility-optimized RR is much smaller than that of ǫ-RR.Source: §D.1.2 · p. 21

D.1.3 l1 loss in the low privacy regime

  • When ǫ = ln |X| and |XS| ≪ |X|, utility-optimized RR achieves almost the same utility as non-private estimation, while ǫ-RR has twice the non-private expected l1 loss [29].Source: §D.1.3 · p. 21

D.2 l1 loss of the utility-optimized RAPPOR

  • Proposition 7 gives the expected l1 loss of the (XS, ǫ)-uRAP mechanism.Source: §D.2 · p. 21

D.2.1 Maximum of the l1 loss

For utility-optimized RAPPOR, the worst-case l1 loss occurs for a uniform distribution over non-sensitive data under the stated privacy condition. In the high-privacy regime its loss is much smaller than standard RAPPOR when the sensitive set is small, and in the low-privacy regime its utility approaches the non-private mechanism.

D.2.1 Maximum of the l1 loss

  • The l1 loss is maximized by the uniform distribution pUN over XN; the passage identifies the maximizing condition as p(XS)=0 with p ∈ CSN.Source: §D.2.1 · pp. 21–22
  • In the high-privacy regime, utility-optimized RAPPOR has much smaller expected l1 loss than ε-RAPPOR when |XS| ≪ |X|.The comparison applies irrespective of whether |XS| ≤ |XN|.Source: §D.2.1 · p. 23
  • When ε = ln |X| and |XS| ≪ |X|, utility-optimized RAPPOR achieves almost the same data utility as the non-private mechanism.The expected l1 loss of ε-RAPPOR is |X| times larger than that of the non-private mechanism.Source: §D.2.1 · p. 23

E.1 l2 loss of the utility-optimized RR

  • Proposition 15 gives the expected l2 loss of utility-optimized RR using the frequencies of the obfuscated data.Those frequencies have binomial variance nm(x)(1 − m(x)).Source: §E.1 · p. 23

E.1.1 Maximum of the l2 loss

The analysis identifies distributions that maximize l2 loss for utility-optimized RR and characterizes its behavior across privacy regimes. It also introduces the expected l2-loss analysis for utility-optimized RAPPOR.

E.1.1 Maximum of the l2 loss

  • For 0 < ε < ln(|XN| + 1), utility-optimized RR’s l2 loss is maximized by the uniform distribution over XN.For ε ≥ ln(|XN| + 1), the maximizer is a mixture of the uniform distributions over XS and XN.Source: §E.1.1 · pp. 24–25

E.1.2 l2 loss in the high privacy regime

  • In the high-privacy regime, utility-optimized RR has much smaller expected l2 loss than ε-RR when |XS| ≪ |X|.The comparison is stated for ε ≈ 0.Source: §E.1.2 · p. 25

E.1.3 l2 loss in the low privacy regime

  • When ε = ln |X| and |XS| ≪ |X|, utility-optimized RR achieves almost the same data utility as the non-private mechanism.The passage compares the expected l1 loss of ε-RR as four times larger than that of the non-private mechanism.Source: §E.1.3 · p. 25

E.2 l2 loss of the utility-optimized RAPPOR

  • Proposition 18 gives the expected l2 loss of utility-optimized RAPPOR, with obfuscated-bit probabilities specified by the underlying data distribution.The passage distinguishes coordinates in XS from those in XN.Source: §E.2 · pp. 25–26

E.2.1 Maximum of the l2 loss

The analysis characterizes worst-case l2 loss for utility-optimized RAPPOR and its behavior in high- and low-privacy regimes. When the sensitive set is small, its low-privacy utility approaches that of a non-private mechanism.

E.2.1 Maximum of the l2 loss

  • For 0 < ε < 2 ln(|XN| + 1), utility-optimized RAPPOR’s l2 loss is maximized by the uniform distribution over XN.The result follows from maximizing the loss at zero probability mass on XS and a uniform distribution within XN.Source: §E.2.1 · pp. 26–27
  • In the high-privacy regime, utility-optimized RAPPOR’s expected l2 loss is much smaller than ε-RAPPOR’s when |XS| ≪ |X|.Its worst-case loss is also described as order-optimal among ULDP mechanisms.Source: §E.2.1 · p. 27
  • When ε = ln |X| and |XS| ≪ |X|, utility-optimized RAPPOR achieves almost the same data utility as the non-private mechanism.The expected l2 loss of ε-RAPPOR is √|X| times larger than that of the non-private mechanism.Source: §E.2.1 · p. 27

E.3 Experimental Results of the MSE

The MSE experiments show a tendency similar to the total-variation results, indicating effectiveness for both l1 and l2 losses.

E.3 Experimental Results of the MSE

  • The MSE results show a tendency similar to the total-variation results, with the proposed methods effective for both l1 and l2 losses.Figures 10–13 report the MSE results corresponding to Figures 5–8.Source: §E.3 · p. 27

F.1 Privacy Analysis of PUMs

The privacy analysis proves that the personalized mechanism satisfies its stated ULDP conditions. The utility analysis derives an l1-loss upper bound by comparing the estimate with one that assumes the exact conditional distributions are known.

F.1 Privacy Analysis of PUMs

  • The personalized mechanism satisfies the stated ULDP conditions, with its proof relying on the preprocessor mapping sensitive inputs to intermediate data and the common mechanism’s ULDP guarantee.The proof uses these properties to establish conditions (4) and (5).Source: §F.1 · p. 27

F.2 Utility Analysis of PUMs

  • Theorem 1 gives an l1-loss bound for the PUM, derived by comparing its estimate with one based on known conditional distributions and applying the triangle inequality.The proof bounds the error of the known-distribution estimate, then bounds the difference between that estimate and the PUM estimate.Source: §F.2 · p. 29
Loading 1807.11317v7…