# Differential Privacy with Random Projections and Sign Random Projections

arXiv: https://arxiv.org/abs/2306.01751 · HTML: https://mlsanity.com/paper/2306.01751/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 99 references that are in the map.
- First posted on arXiv 22 May 2023.

## Builds on (most cited first, 30 of 38)

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [Reading Wikipedia to Answer Open-Domain Questions](https://mlsanity.com/paper/1704.00051/) (2017)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [Federated Learning with Differential Privacy: Algorithms and Performance Analysis](https://mlsanity.com/paper/1911.00222/) (2019)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Failing Loudly: An Empirical Study of Methods for Detecting Dataset Shift](https://mlsanity.com/paper/1810.11953/) (2018)
- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [FetchSGD: Communication-Efficient Federated Learning with Sketching](https://mlsanity.com/paper/2007.07682/) (2020)
- [cpSGD: Communication-efficient and differentially-private distributed SGD](https://mlsanity.com/paper/1805.10559/) (2018)
- [Compressing Neural Networks with the Hashing Trick](https://mlsanity.com/paper/1504.04788/) (2015)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Federated Reconstruction: Partially Local Federated Learning](https://mlsanity.com/paper/2102.03448/) (2021)
- [DEMO-Net: Degree-specific Graph Neural Networks for Node and Graph Classification](https://mlsanity.com/paper/1906.02319/) (2019)
- [Graph Embedding for Recommendation against Attribute Inference Attacks](https://mlsanity.com/paper/2101.12549/) (2021)
- [Differential Privacy: An Economic Method for Choosing Epsilon](https://mlsanity.com/paper/1402.3329/) (2014)
- [SoK: Differential Privacies](https://mlsanity.com/paper/1906.01337/) (2019)
- [Experiments with Random Projection](https://mlsanity.com/paper/1301.3849/) (2013)
- [Dynamic Malware Analysis with Feature Engineering and Feature Learning](https://mlsanity.com/paper/1907.07352/) (2019)
- [Privacy-Aware Recommendation with Private-Attribute Protection using Adversarial Learning](https://mlsanity.com/paper/1911.09872/) (2019)
- [FedSKETCH: Communication-Efficient and Private Federated Learning via Sketching](https://mlsanity.com/paper/2008.04975/) (2020)
- [The Impact of the U.S. Census Disclosure Avoidance System on Redistricting and Voting Rights Analysis](https://mlsanity.com/paper/2105.14197/) (2021)
- [Sparse Projection Oblique Randomer Forests](https://mlsanity.com/paper/1506.03410/) (2015)
- [One-bit compressive sensing with norm estimation](https://mlsanity.com/paper/1404.6853/) (2014)
- [OPORP: One Permutation + One Random Projection](https://mlsanity.com/paper/2302.03505/) (2023)
- [In Defense of MinHash Over SimHash](https://mlsanity.com/paper/1407.4416/) (2014)
- [Individual Differential Privacy: A Utility-Preserving Formulation of Differential Privacy Guarantees](https://mlsanity.com/paper/1612.02298/) (2016)
- [Differentially Private Linear Sketches: Efficient Implementations and Applications](https://mlsanity.com/paper/2205.09873/) (2022)
- [Marginal Release Under Local Differential Privacy](https://mlsanity.com/paper/1711.02952/) (2017)
- [Coding for Random Projections](https://mlsanity.com/paper/1308.2218/) (2013)

## Built on by (most cited first, 5 of 5)

- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [Private Collaborative Edge Inference via Over-the-Air Computation](https://mlsanity.com/paper/2407.21151/) (2024)
- [Differentially Private One Permutation Hashing and Bin-wise Consistent Weighted Sampling](https://mlsanity.com/paper/2306.07674/) (2023)

## Abstract (arXiv)

In this paper, we develop a series of differential privacy (DP) algorithms from a family of random projections (RP) for general applications in machine learning, data mining, and information retrieval. Among the presented algorithms, iDP-SignRP is remarkably effective under the setting of ``individual differential privacy'' (iDP), based on sign random projections (SignRP). Also, DP-SignOPORP considerably improves existing algorithms in the literature under the standard DP setting, using ``one permutation + one random projection'' (OPORP), where OPORP is a variant of the celebrated count-sketch method with fixed-length binning and normalization. Without taking signs, among the DP-RP family, DP-OPORP achieves the best performance. Our key idea for improving DP-RP is to take only the signs, i.e., sign(xj) = signleft(sumi=1p ui wijright), of the projected data. The intuition is that the signs often remain unchanged when the original data (u) exhibit small changes (according to the ``neighbor'' definition in DP). In other words, the aggregation and quantization operations themselves provide good privacy protections. We develop a technique called ``smooth flipping probability'' that incorporates this intuitive privacy benefit of SignRPs and improves the standard DP bit flipping strategy. Based on this technique, we propose DP-SignOPORP which satisfies strict DP and outperforms other DP variants based on SignRP (and RP), especially when ε is not very large (e.g., ε = 5~10). Moreover, if an application scenario accepts individual DP, then we immediately obtain an algorithm named iDP-SignRP which achieves excellent utilities even at small~ε (e.g., ε<0.5).