The Geometry of Differential Privacy: the Sparse and Approximate Cases

Aleksandar Nikolov, Kunal Talwar, Li Zhang

Abstract

In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries, and has been a focus of a long line of work. For a set of $d$ linear queries over a database $x \in \mathbb{R}^N$, we seek to find the differentially private mechanism that has the minimum mean squared error. For pure differential privacy, an $O(\log^2 d)$ approximation to the optimal mechanism is known. Our first contribution is to give an $O(\log^2 d)$ approximation guarantee for the case of $(\epsilon,\delta)$-differential privacy. Our mechanism is simple, efficient and adds correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of Muthukrishnan and Nikolov, using tools from convex geometry. We next consider this question in the case when the number of queries exceeds the number of individuals in the database, i.e. when $d > n \triangleq \|x\|_1$. It is known that better mechanisms exist in this setting. Our second main contribution is to give an $(\epsilon,\delta)$-differentially private mechanism which is optimal up to a $\text{polylog}(d,N)$ factor for any given query set $A$ and any given upper bound $n$ on |x|_1. This approximation is achieved by coupling the Gaussian noise addition approach with a linear regression step. We give an analogous result for the $\epsilon$-differential privacy setting. We also improve on the mean squared error upper bound for answering counting queries on a database of size $n$ by Blum, Ligett, and Roth, and match the lower bound implied by the work of Dinur and Nissim up to logarithmic factors. The connection between hereditary discrepancy and the privacy mechanism enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix $A$.

Introduction

Differential Privacy (DP) serves as the standard framework for protecting individual privacy in statistical databases. A fundamental task in this field is answering a set of $d$ linear queries—such as "How many individuals in the dataset possess specific attributes?"—while minimizing the mean squared error (MSE) of the responses. While previous research has largely focused on "pure" $\epsilon$-DP and "dense" databases (where the number of individuals $n$ is much larger than the number of queries $d$), real-world applications often demand different approaches.

Specifically, $(\epsilon, \delta)$-differential privacy (approximate privacy) is frequently preferred for its ability to utilize more accurate mechanisms, such as Gaussian noise addition. Furthermore, many databases are "sparse," meaning the number of queries $d$ or the universe size $N$ significantly exceeds the number of individuals $n$. This paper addresses these gaps by providing near-optimal algorithms for linear queries under $(\epsilon, \delta)$-DP, particularly in the sparse regime.

Geometric Mechanisms and Methodology

The authors propose a framework that leverages the inherent geometry of the query set. The core idea is that the "shape" of the query workload—defined by the convex hull of its columns—determines the optimal privacy-accuracy trade-off.

Base Decomposition and Correlated Noise

The mechanism begins by decomposing the query matrix into orthogonal subspaces. This is achieved by recursively identifying the minimum volume enclosing ellipsoid (MEE) for the columns of the query matrix. Instead of adding independent noise to each query, the algorithm adds correlated Gaussian noise tailored to the geometry of these subspaces. This approach ensures privacy is maintained while minimizing the impact on accuracy.

Least Squares Projection for Sparse Databases

In the sparse case, where $n < d$, the true answer vector is constrained to lie within an $L_1$ ball of radius $n$. The authors introduce a post-processing step that projects the noisy answers back onto this feasible region $L$.

Geometric projection of noisy answers back into the feasible set $L$ to reduce error.

As shown in Figure 1, the noisy answer $\tilde{y}$ is projected to $\hat{y}$ within the feasible set $L$. Because the "shadow" of the feasible region on the noise vector is often much smaller than the noise itself, this projection significantly reduces the expected error without compromising privacy.

Hereditary Discrepancy

To establish optimality, the authors link the minimum error of any private mechanism to the hereditary discrepancy of the query matrix. This combinatorial measure quantifies how well the matrix columns can be balanced. By showing that their algorithms achieve error rates within polylogarithmic factors of this lower bound, the authors provide the first near-optimal guarantees for these settings.

Key Results

The paper establishes several significant theoretical bounds:

  • Dense Case: For $(\epsilon, \delta)$-DP, the authors provide an $O(\log^2 d)$ approximation to the optimal mechanism.
  • Sparse Case: They achieve polylogarithmic approximations for both $(\epsilon, \delta)$-DP and pure $\epsilon$-DP when $n < d$.
  • Counting Queries: For any set of counting queries, they demonstrate an $\epsilon$-DP mechanism with expected error $\tilde{O}(\sqrt{n})$ per query, matching known lower bounds up to logarithmic factors and improving upon the previous best of $\tilde{O}(n^{2/3})$.
  • Algorithmic Efficiency: All proposed mechanisms, including the geometric decomposition and the least-squares projection, are computable in polynomial time.

Discussion and Future Directions

The primary insight of this work is that "geometry is destiny" in differential privacy. By using standard tools from convex geometry, such as MEEs, the authors simplify the analysis of private mechanisms and reveal deep connections to discrepancy theory.

However, challenges remain. While the polylogarithmic guarantees are theoretically strong, the associated constants (e.g., $\log^2 d$) may be large in practical implementations. Future work could focus on tightening these constants or extending these geometric bounds to error metrics beyond $L_2^2$, such as $L_\infty$ error in the sparse regime. Additionally, while the algorithms are polynomial-time, the computational cost of finding MEEs for very high-dimensional query sets may require further optimization for large-scale systems.

Summary updated

Abstract

In this work, we study trade-offs between accuracy and privacy in the context of linear queries over histograms. This is a rich class of queries that includes contingency tables and range queries, and has been a focus of a long line of work. For a set of $d$ linear queries over a database $x \in \R^N$, we seek to find the differentially private mechanism that has the minimum mean squared error. For pure differential privacy, an $O(\log^2 d)$ approximation to the optimal mechanism is known. Our first contribution is to give an $O(\log^2 d)$ approximation guarantee for the case of $(\eps,\delta)$-differential privacy. Our mechanism is simple, efficient and adds correlated Gaussian noise to the answers. We prove its approximation guarantee relative to the hereditary discrepancy lower bound of Muthukrishnan and Nikolov, using tools from convex geometry. We next consider this question in the case when the number of queries exceeds the number of individuals in the database, i.e. when $d > n \triangleq \|x\|_1$. It is known that better mechanisms exist in this setting. Our second main contribution is to give an $(\eps,\delta)$-differentially private mechanism which is optimal up to a $\polylog(d,N)$ factor for any given query set $A$ and any given upper bound $n$ on $\|x\|_1$. This approximation is achieved by coupling the Gaussian noise addition approach with a linear regression step. We give an analogous result for the $\eps$-differential privacy setting. We also improve on the mean squared error upper bound for answering counting queries on a database of size $n$ by Blum, Ligett, and Roth, and match the lower bound implied by the work of Dinur and Nissim up to logarithmic factors. The connection between hereditary discrepancy and the privacy mechanism enables us to derive the first polylogarithmic approximation to the hereditary discrepancy of a matrix $A$.
BibTeX
@inproceedings{nikolov2013geometry,
  author = {Aleksandar Nikolov and Kunal Talwar and Li Zhang},
  title = {{The Geometry of Differential Privacy: the Sparse and Approximate Cases}},
  booktitle = {STOC},
  year = {2013},
  url = {https://openreview.net/forum?id=wvNJfZvAd0N},
}
Figure