Smooth Flipping Probability for Differential Private Sign Random Projection Methods
Main Conference Track
Authors: Ping Li, Xiaoyun Li

We develop a series of differential privacy (DP) algorithms from a family of random projection (RP) and sign random projection (SignRP) methods. We first show how to improve the previous DP-RP approach using the ``optimal Gaussian mechanism''. Then, we propose a series of DP-SignRP algorithms that leverage the robustness of the ``sign flipping probability'' of random projections. That is, given $x = \sum_{i=1}^p u_i w_{i}$ where $u$ is a $p$-dimensional data vector and $w$ is a symmetric random vector,  $sign(x)$ only has a fairly small probability to be flipped if there is a small modification on data $u$, depending on the specific distribution of $w$. This robustness leads to our novel design of ``smooth flipping probability'' for SignRP-type algorithms with better utility than using the standard randomized response mechanism. Retrieval and classification experiments demonstrate that,  among the presented DP-RP  algorithms,  \textbf{DP-SignOPORP} (where OPORP  is an improvement over the celebrated  count-sketch algorithms), performs the best in general.In the industrial practice, DP methods were not very popular for machine learning or search, largely because the performance typically would  drop substantially if DP is applied. Since our proposed new DP algorithms have significantly improved the  performance, it is anticipated that our work will motivate a wide adoption of DP in practice. Finally, we   stress that, since our  methods are applied to the original data (i.e., feature vectors), the privacy of  downstream tasks is naturally protected.