TL;DR
This paper tackles the challenge of estimating linear queries from sensitive data while preserving local differential privacy (LDP). They introduce novel algorithms for both fixed (offline) and adaptive (online) query settings, achieving near-optimal accuracy that's surprisingly independent of the number of queries in high-dimensional scenarios. This work pushes the boundaries of what's possible in private data analysis, especially when dealing with large datasets and complex query structures.
What Problem Does This Paper Address?
The core problem is estimating the values of a set of linear queries applied to an unknown data distribution, all while adhering to Local Differential Privacy (LDP). In LDP, each individual locally randomizes their data before sending it to a central server. This is a stronger privacy guarantee than traditional centralized differential privacy, as it doesn't rely on a trusted curator.
The authors focus on estimating linear queries, which are functions defined by vectors $q \in \mathbb{R}^J$. Estimating a set of $d$ such queries can be represented by a matrix $A \in \mathbb{R}^{d \times J}$. This general framework encompasses important tasks like estimating the underlying data distribution (when $d=J$) and estimating the mean of a $d$-dimensional random variable.
A key challenge they address is the "high-dimensional setting," where the number of queries $d$ or the domain size $J$ can be much larger than the number of users $n$. Existing LDP methods often suffer from estimation errors that grow polynomially with $d$ or $J$, making them impractical in these scenarios. The paper aims to develop algorithms whose error is less dependent on these dimensions.
Methods
The paper proposes new algorithms for two settings:
- Offline (Non-adaptive) Setting: Here, all $d$ queries are determined before the data collection begins.
- For general linear queries, they combine ideas from Gaussian mechanisms (for noise perturbation) and projection techniques (similar to those used in centralized differential privacy) to transform an $(\epsilon, \delta)$-LDP protocol into a pure $\epsilon$-LDP protocol using rejection sampling. This approach achieves an $L_2$ estimation error that is independent of $d$ in high-dimensional settings.
- For the specific case of distribution estimation, they extend the Hadamard-Response protocol by projecting its output onto the probability simplex. This projection step is crucial for achieving sub-logarithmic dependence on $J$ in the $L_2$ error.
- Adaptive Setting: In this more challenging setting, queries are chosen one by one over $d$ rounds, and each query can depend on the history of previous queries and responses.
- They propose a protocol that partitions users into $d$ disjoint subsets, with each subset responsible for answering one query. This "sample splitting" technique, while sometimes suboptimal in centralized settings, is shown to be optimal for adaptive linear queries in the LDP model. The protocol achieves an optimal $L_\infty$ estimation error.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis and algorithmic constructions for estimating properties of an unknown distribution $p$ over a domain $\mathcal{J}=[J]$, rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- Dimensionality Independence is Possible: The most striking insight is that for offline linear queries, it's possible to achieve $L_2$ estimation error that is independent of the number of queries $d$ in high-dimensional settings ($n \lesssim d^2/\log(J)$). This is a significant departure from previous work where error often scaled with $d$.
- Projection is Powerful: For distribution estimation, projecting the output of an existing algorithm onto the probability simplex dramatically improves the $L_2$ error, making it sub-logarithmically dependent on the domain size $J$. This highlights the utility of geometric constraints in private data analysis.
- Adaptivity Doesn't Hurt $L_\infty$ Error: In the local model, adaptivity in query selection does not increase the worst-case $L_\infty$ estimation error for linear queries compared to the non-adaptive setting. This is a notable contrast to the centralized model, where adaptivity can sometimes lead to worse generalization bounds.
- Rejection Sampling for Pure $\epsilon$-LDP: The paper demonstrates a practical way to transform $(\epsilon, \delta)$-LDP protocols into pure $\epsilon$-LDP protocols using rejection sampling, maintaining similar accuracy guarantees.
Key Results
- Offline Linear Queries (L2 Error):
- Achieved an $L_2$ estimation error of $r \cdot \min\left(\left(\frac{32 \log(J)\log(2/\delta)}{n\epsilon^2}\right)^{1/4}, \left(\frac{2d\log(2/\delta)}{n\epsilon^2}\right)^{1/2}\right)$ for $(\epsilon, \delta)$-LDP.
- In the high-dimensional regime ($n \lesssim d^2/\log(J)$), the error is independent of $d$ and is tight up to a factor of $\tilde{O}(\log^{1/4}(J))$.
- Developed a pure $\epsilon$-LDP protocol with similar accuracy guarantees.
- Distribution Estimation (L2 Error):
- Achieved an $L_2$ error of $\min\left(\left(\frac{256 c \log(J)}{n}\right)^{1/4}, \frac{4cJ}{n}\right)$ for pure $\epsilon$-LDP, where $c$ depends on $\epsilon$. This error is sub-logarithmically dependent on $J$ for $n \lesssim J^2/\log(J)$.
- Adaptive Linear Queries ($L_\infty$ Error):
- Achieved an optimal $L_\infty$ estimation error of $4r \frac{c\epsilon \log(d)}{n}$ for pure $\epsilon$-LDP, where $c$ depends on $\epsilon$.
- This bound matches known lower bounds for the non-adaptive setting, demonstrating that adaptivity doesn't incur an extra penalty in the local model for this problem.
Limitations and Future Work
- Tightness of Bounds: While the bounds are shown to be near-optimal, there remains a gap between the upper and lower bounds for the offline linear queries problem, particularly concerning the $\log^{1/4}(J)$ factor. The authors conjecture this factor is necessary and leave tightening this gap as an open problem.
- Communication/Computational Efficiency: For the general offline linear queries, the focus was on improving estimation error, not necessarily optimizing communication or computational efficiency per user. The paper suggests that providing a succinct description of the queries matrix (under more assumptions) is an interesting future direction.
- Centralized vs. Local Model Comparison: The paper highlights that adaptivity's impact on error differs between the local and centralized models. Further investigation into these differences, especially for other privacy models or problem settings, is warranted.
Summary updated