Low Rank Mechanism for Optimizing Batch Queries under Differential Privacy

Conclusion

This paper presented the Low Rank Mechanism (LRM), an optimization framework that minimizes the overall error in the results of a batch of linear queries under $\epsilon$-differential privacy. LRM is the first practical method for a large number of linear queries, with an efficient and effective implementation using well established optimization techniques. Experiments show that LRM significantly outperforms other state-of-the-art differentially private query processing mechanisms, often by orders of magnitude. The current design of LRM focuses on exploiting the correlations between different queries. One interesting direction for future work is to further optimize LRM by utilizing also the correlations between data values, e.g., as is done in .

Acknowledgments

Yuan and Hao are supported by NSF-China (61070033, 61100148), NSF-Guangdong (9251009001000005, S2011040004804) and Key Technology Research and Development Programs of Guangdong Province (2010B050400011). Zhang, Winslett, Xiao and Yang are supported by SERC 102-158-0074 from Singapore’s A*STAR. Xiao is also supported by SUG Grant M58020016 and AcRF Tier 1 Grant RG 35/09 from Nanyang Technological University.

References

Appendix A Proofs

Based on the definition of the mechanism in Eq. (LABEL:eqn:part_mech), the residual of the noisy result with respect to the exact result, i.e. $Q(D)-M_{P}(Q,D)$, is $B\cdot Lap\left(\frac{\Delta(B,L)}{\epsilon}\right)^{r}$. The expected squared error is thus $\sum_{ij}B^{2}_{ij}\frac{2(\Delta(B,L))^{2}}{\epsilon^{2}}$. Since $\Phi(B,L)=\sum_{ij}B^{2}_{ij}$, the expected error of the mechanism is $2\phi(B,L)(\Delta(B,L))^{2}/\epsilon^{2}$.

Based on the definition of sensitivity, we have $\Delta(B^{\prime},L^{\prime})$ $=\max_{j}\sum_{i}|L^{\prime}_{ij}|=\max_{j}\sum_{i}|L_{ij}/\alpha|=\alpha^{-1}\Delta(B,L)$.

The last equality holds because $\alpha$ is a positive constant. On the other hand, the scales of the decompositions follow a similar relationship:

Therefore, $\Phi(B^{\prime},L^{\prime})(\Delta(B^{\prime},L^{\prime})^{2}=\Phi(B,L)(\Delta(B,L))^{2}$. Finally, since $B^{\prime}L^{\prime}=BL=W$, we reach the conclusion of the lemma.

Assume that $(B^{*},L^{*})$ is the best matrix decomposition for minimizing the expected squared error for $M_{P}(Q,D)$. In the following, we prove that $(B^{*},L^{*})$ is optimal, if and only if it also minimizes the program in Formula (LABEL:eqn:opt-problem).

(if part): If $(B,L)$ minimizes Formula (LABEL:eqn:opt-problem) but $(B,L)$ incurs more expected error than $(B^{*},L^{*})$, implying that

By applying Lemma LABEL:lem:rescale, we can construct another decomposition $B^{\prime}=\Delta(B^{*},L^{*})B^{*}$ and $L^{\prime}=\Delta(B^{*},L^{*})^{-1}L^{*}$, such that $\Phi(B^{\prime},L^{\prime})(\Delta(B^{\prime},L^{\prime}))^{2}<\Phi(B,L)(\Delta(B,L))^{2}$. On the other hand, since $\Delta(B^{\prime},L^{\prime})\leq 1$, we have $\max_{j}\sum_{i}|L^{\prime}_{ij}|=1$. Therefore, we can derive the following inequalities.

Finally, since $\Phi(B^{\prime},L^{\prime})=\mbox{tr}(B^{\prime T}B^{\prime})$ and $\Phi(B,L)=\mbox{tr}(B^{T}B)$, it leads to a contradiction if $\mbox{tr}(B^{\prime T}B^{\prime})<\mbox{tr}(B^{T}B)$.

(only if part): If $(B^{*},L^{*})$ is not the optimal solution to the program in Formula (LABEL:eqn:opt-problem), the optimal solution $(B,L)$ must incur less expected error, using a similar strategy. This completes the proof of the theorem.

To prove the lemma, we aim to artificially construct a workload decomposition $W=BL$ satisfying the constraints of the optimization formulation. If the error of this artificial decomposition is no larger than the upper bound, the exact optimal solution must render results with less error.

Recall that $W$ has a unique SVD decomposition $W=U\Sigma V$ such that $\Sigma$ is a diagonal matrix of size $r\times r$. We thus build a decomposition $B=\sqrt{r}U\Sigma$ and $L=\frac{1}{\sqrt{r}}V$, in which $r$ is the rank of the matrix $W$. First, we will show such $(B,L)$ satisfies the constraints in Formula (LABEL:eqn:opt-problem). It is straightforward to show it satisfies the first constraint: $BL=\sqrt{r}U\Sigma\frac{1}{\sqrt{r}}V=U\Sigma V=W$.

Regarding the second constraint, since $V$ only contains orthogonal vectors, every column $j$ must have $\|V_{:j}\|_{2}=\|v\|_{2}=1$. By the norm triangle inequality, $\|v\|_{2}\leq\|v\|_{1}\leq\sqrt{r}\|v\|_{2}$, and we obtain $\frac{1}{\sqrt{r}}\sum_{i}|V_{ij}|\leq 1$. Therefore, such $(B,L)$ must be a valid solution to the program.

The expected squared error of the artificial decomposition $W=BL$ is at most

This proves that $\sum^{r}_{k=1}\lambda^{2}_{k}r/\epsilon^{2}$ is an upper bound for the noise of our decomposition-based scheme.

In Corollary 3.4 in , Hardt and Talwar proved that any $\epsilon$-differential privacy mechanism incurs expected squared error no less than used absolute error in the paper, which we change to squared error here. $\Omega(r^{3}\left(Vol(PWB^{n}_{1})\right)^{2/r}/\epsilon^{2})$.

To prove the theorem, we investigate the ratio of the upper bound to the lower bound.

The last inequality holds due to the fact that $r!<\left(\frac{r}{2}\right)^{r}$ when $r>5$. Note that all the inequalities above are tight, and the equalities hold when $C=1$, i.e. $\lambda_{1}=\lambda_{2}=\ldots=\lambda_{r}$. Thus, we prove that the approximation factor of our decomposition scheme is $\mathcal{O}(C^{2}r)$.

When $W\neq BL$, the error has two parts. The first part is the noises due to the Laplace random variables. Using Lemma LABEL:lem:decomp_error, the incurred error is at most $\frac{2}{\epsilon^{2}}\Phi(B,L)(\Delta(B,L))^{2}\leq\frac{2}{\epsilon^{2}}\mbox{tr}(B^{T}B)$.

The second part of the error is the structural error on the results. The expected squared error is measured as

The inequality is due to the Cauchy Schwartz inequality. By linearity of expectation, the expected squared errors can be simply summed up. This leads to the conclusion of the theorem.

We use ${B^{(k)}}^{*}$ to denote the optimal solution of the Lagrangian sub-problem in $k^{th}$ iteration. Note the following inequality on the sequence of the Lagrangian subproblems:

Based on the above inequality, we derive the following inequality:

The third equality holds because of the Lagrangian multiplier update rule:

Since ${{\pi^{(k)}}^{*}}$ is always bounded, we conclude that

Appendix B Implementation of the Matrix Mechanism

In , Li et al. propose the Matrix Mechanism. The core of their method is finding a matrix $A$ to minimize the following the program.

Li et al. present a complicated implementation that may not be practical due to its high complexity. We hereby present a simpler and more efficient solution to their optimization program. Here $\|A\|_{2,\infty}^{2}$ denotes the maximum $\mathcal{L}_{2}$ norm of column vectors of $A$, therefore $\|A\|_{2,\infty}^{2}=\max(\mbox{diag}(A^{T}A))$. Since $(A^{T}A)^{-1}=(A^{T}A)^{{\dagger}}$ ($A$ has full column rank), we let $M=A^{T}A$, and reformulate Formula (1) as the following semidefinite programming problem:

$A$ is given by $A=\sum_{i}^{n}\sqrt{\lambda_{i}}v_{i}v_{i}^{T}$, where $\lambda_{i},v_{i}$ are the $i$th eigenvalue and eigenvector of $M$, respectively. Calculating the second term $\mbox{tr}(W^{T}WM^{-1})$ is relatively straightforward. Since it is smooth, its gradient can be computed as $-M^{-1}W^{T}WM^{-1}$. However, calculating the first term $\max(\mbox{diag}(M))$ is harder since it is non-smooth. Fortunately, inspired by , we can still use a logarithmic and exponential function to approximate this term.

Approximate the maximum positive number: Since $M$ is positive definite, $v=\mbox{diag}(M)>0$. we let $\mu>0$ and define:

We then have ${\max}(v)\leq f_{\mu}\left(v\right)\leq{\max}(v)+\mu\log n$. If we set $\mu=\frac{\epsilon}{\log n}$, this becomes a uniform $\epsilon$-approximation of ${\max}(v)$ with a Lipschitz continuous gradient with constant $\omega=\frac{1}{\mu}=\frac{\log n}{\epsilon}$. The gradient of the objective function with respect to $v$ can be computed as:

To mitigate the problems with large numbers, using the property of the logarithmic and exponential functions, we can rewrite Eq.(2) and Eq. (3) as:

This formulation allows us to run the non-monotone projected gradient descent algorithm and iteratively improves the result.