Abstract
Local differential privacy (LDP) enables private data sharing and analytics without the need for a trusted data collector. Error-optimal primitives (for, e.g., estimating means and item frequencies) under LDP have been well studied. For analytical tasks such as range queries, however, the best known error bound is dependent on the domain size of private data, which is potentially prohibitive. This deficiency is inherent as LDP protects the same level of indistinguishability between any pair of private data values for each data owner. In this paper, we utilize an extension of $\epsilon$-LDP called Metric-LDP or $E$-LDP, where a metric $E$ defines heterogeneous privacy guarantees for different pairs of private data values and thus provides a more flexible knob than $\epsilon$ does to relax LDP and tune utility-privacy trade-offs. We show that, under such privacy relaxations, for analytical workloads such as linear counting, multi-dimensional range counting queries, and quantile queries, we can achieve significant gains in utility. In particular, for range queries under $E$-LDP where the metric $E$ is the $L^1$-distance function scaled by $\epsilon$, we design mechanisms with errors independent on the domain sizes; instead, their errors depend on the metric $E$, which specifies in what granularity the private data is protected.
Introduction: The Utility Problem in LDP
Local Differential Privacy (LDP) has emerged as the gold standard for collecting telemetry and user data without a trusted third party. By perturbing data locally on a user's device, LDP ensures that the collector never sees raw sensitive information. However, standard $\epsilon$-LDP faces a significant "utility problem" in range queries. It requires that any two values in a dataset—such as ages 25 and 26, or ages 25 and 90—be equally indistinguishable.
This "one-size-fits-all" privacy budget is often overkill. Users may care deeply about distinguishing between adjacent values but less about distinguishing between distant ones. Because standard LDP is so strict, the error in range queries (e.g., "How many users are between 20 and 30?") grows with the size of the data domain $m$. For large or high-dimensional datasets, this error can render the collected data useless.
Metric-LDP: A Flexible Privacy Framework
To bridge this gap, we utilize Metric-LDP (or $E$-LDP). Instead of a single privacy parameter $\epsilon$, we use a distance metric $E(x, x')$ to define privacy requirements. The closer two values are, the harder they are to distinguish; as the distance increases, the privacy constraint relaxes, allowing for higher utility.
We adapt the LDP Matrix Mechanism to this setting, formulating an optimization problem to find the best way to perturb data (encoding) and reconstruct answers (decoding) to minimize error. For multi-dimensional data, we introduce a Threshold Encoding scheme that transforms data into vectors of 1s and -1s, alongside a recursive estimation method to handle high-dimensional bias-correction efficiently.
Breaking the "Domain Size Curse"
A primary contribution of this work is demonstrating that under Metric-LDP—specifically using the $L^1$ distance—the error for range queries becomes independent of the domain size $m$. In standard LDP, the error grows with $\log m$; under $E$-LDP, it remains flat regardless of data granularity. This is achieved through an encoding design where random noise added by individual users largely cancels out during aggregation.
Metric-LDP provides a "knob" for practitioners: by defining exactly how much protection is needed at different levels of granularity, one can achieve a much finer trade-off between privacy and utility. As shown in the figure above, $E$-LDP offers significantly lower error than standard $\epsilon$-LDP when the set of sensitive values is restricted, converging to standard LDP levels only as the sensitive set grows to cover the entire domain.
Key Results and Empirical Validation
Our theoretical analysis shows that for multi-dimensional range queries, the proposed mechanism achieves an error bound of $O(n(2/\epsilon)^{2D})$, which is independent of the domain size $m$. Furthermore, by using our range query method as a building block for binary search, we improve the accuracy of quantile queries (like finding the median) by a factor of $O(\log m)$ compared to the best-known standard LDP methods. Simulations on synthetic Zipf-distributed datasets confirm these findings, with empirical squared errors consistently lower than theoretical upper bounds.
Conclusion
Metric-LDP provides a robust framework for high-utility data analytics under local privacy constraints. By relaxing the indistinguishability requirements for distant values, we can overcome the "domain size curse" inherent in standard LDP. This approach is particularly effective for ordinal and multi-dimensional data, and we encourage its adoption for practical analytical tasks where standard LDP utility is insufficient.
Summary updated