Linear Queries Estimation with Local Differential Privacy

Raef Bassily

Abstract

We study the problem of estimating a set of $d$ linear queries with respect to some unknown distribution $p$ over a domain $[J]$ based on a sensitive data set of $n$ individuals under the constraint of local differential privacy (LDP). We provide new, near-optimal algorithms for both offline and adaptive query settings, demonstrating that high-dimensional estimation is possible with errors independent of the number of queries in certain regimes.

Introduction

In the landscape of data privacy, the Local Differential Privacy (LDP) model stands as the "gold standard" for user trust. Unlike centralized models where a central aggregator is trusted with raw data, LDP requires data to be randomized on the user's device before transmission. However, this privacy comes at a cost to accuracy, particularly when estimating multiple linear queries—such as "What is the average age?" and "How many people live in Ohio?"—simultaneously.

In high-dimensional settings, where the number of queries ($d$) or the domain size ($J$) exceeds the number of users ($n$), traditional LDP methods often suffer from noise accumulation that renders the data unusable. This paper addresses this challenge by providing new algorithmic frameworks for both offline (non-adaptive) queries, where all queries are known upfront, and adaptive queries, where queries are generated sequentially based on previous answers.

Methodology

The authors propose three primary algorithmic frameworks to tackle these challenges:

  1. Gaussian Mechanism with Projection (Offline): For $(\epsilon, \delta)$-LDP, users apply Gaussian noise to their data. The server then projects the noisy aggregate onto a specific convex polytope (the $L_1$ ball). This projection step is critical for reducing error in high-dimensional regimes.
  2. Rejection Sampling Transformation: To satisfy the stricter "pure" $\epsilon$-LDP guarantee, a rejection sampling technique is employed to mimic the accuracy of the Gaussian mechanism.
  3. Projected Hadamard-Response (Distribution Estimation): For estimating probability distributions, the authors extend the Hadamard-Response protocol with a projection step onto the probability simplex, ensuring efficiency and accuracy even with massive data domains.
  4. Sample Splitting (Adaptive): For adaptive queries, the algorithm partitions the $n$ users into $d$ groups, using each group to answer a single query. While often considered sub-optimal in centralized privacy, this work proves its optimality in the local model.

As a theoretical contribution, the performance of these algorithms is validated through rigorous mathematical proofs and minimax rate analysis rather than empirical datasets.

Key Insights

  • Geometric Projection: Projecting noisy estimates back into the feasible space (e.g., the probability simplex) can eliminate the error's dependence on the number of queries $d$, enabling accurate estimation even when $d \gg n$.
  • Adaptivity in LDP: Unlike centralized differential privacy, where adaptive queries are significantly more costly, this work shows that in the local model, the error for adaptive queries can match the lower bounds for offline queries.
  • Optimality of Sample Splitting: The authors prove that for adaptive linear queries under LDP, splitting the user base into smaller chunks actually achieves the optimal $L_\infty$ error.

Key Results

The paper establishes new upper bounds that significantly improve upon or fill gaps in previous literature. These results are summarized in the table below, highlighting the near-optimal performance across different query types and error metrics.

Comparison of error bounds for linear query estimation under LDP.

Specifically:

  • Offline Queries: The $L_2$ error is reduced to roughly $r \cdot (\frac{\log J \log n}{n\epsilon^2})^{1/4}$, removing the dependence on $d$ in high-dimensional regimes.
  • Distribution Estimation: The proposed protocol provides the first non-trivial $L_2$ error bound for the regime where $n < J/\epsilon^2$.
  • Adaptive Queries: The algorithm achieves an $L_\infty$ error of $r \sqrt{\frac{c_{\epsilon}^2 d \log d}{n}}$, which is proven to be mathematically optimal.

Limitations and Future Work

While the results are groundbreaking, some challenges remain. The general offline linear query algorithm involves projecting onto complex polytopes, which may be computationally intensive for very large domains ($J$). Additionally, a small gap of $(\log J)^{1/4}$ exists between the new upper bounds and known theoretical lower bounds; the authors conjecture this factor is necessary but leave the formal proof for future study. Finally, exploring whether specific query structures, such as range queries, can further improve error rates remains an open area for research.

Summary updated

Abstract

We study the problem of estimating a set of d linear queries with respect to some unknown distribution p over a domain $[J]$ based on a sensitive data set of n individuals under the constraint of l...
BibTeX
@inproceedings{bassily2019linear,
  author = {Raef Bassily},
  title = {{Linear Queries Estimation with Local Differential Privacy}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2019},
  url = {https://openreview.net/forum?id=nLTHmurMJm6},
}
Figure