# Smoothed Differential Privacy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 79 references that are in the map.
- First posted on arXiv 4 Jul 2021.

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

- [Deep Learning with Differential Privacy](https://mlsanity.com/paper/1607.00133/) (2016)
- [XNOR-Net: ImageNet Classification Using Binary Convolutional Neural Networks](https://mlsanity.com/paper/1603.05279/) (2016)
- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Certified Robustness to Adversarial Examples with Differential Privacy](https://mlsanity.com/paper/1802.03471/) (2018)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [Differential Privacy Has Disparate Impact on Model Accuracy](https://mlsanity.com/paper/1905.12101/) (2019)
- [The Composition Theorem for Differential Privacy](https://mlsanity.com/paper/1311.0776/) (2013)
- [Scalable Private Learning with PATE](https://mlsanity.com/paper/1802.08908/) (2018)
- [Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weights](https://mlsanity.com/paper/1702.03044/) (2017)
- [Towards Accurate Binary Convolutional Neural Network](https://mlsanity.com/paper/1711.11294/) (2017)
- [Concentrated Differential Privacy](https://mlsanity.com/paper/1603.01887/) (2016)
- [Fixed Point Quantization of Deep Convolutional Networks](https://mlsanity.com/paper/1511.06393/) (2015)
- [Scalable Methods for 8-bit Training of Neural Networks](https://mlsanity.com/paper/1805.11046/) (2018)
- [Towards Unified INT8 Training for Convolutional Neural Network](https://mlsanity.com/paper/1912.12607/) (2019)
- [A Survey on Methods and Theories of Quantized Neural Networks](https://mlsanity.com/paper/1808.04752/) (2018)
- [Differential Privacy and Machine Learning: a Survey and Review](https://mlsanity.com/paper/1412.7584/) (2014)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [WRPN: Wide Reduced-Precision Networks](https://mlsanity.com/paper/1709.01134/) (2017)
- [Smoothed Analysis of Online and Differentially Private Learning](https://mlsanity.com/paper/2006.10129/) (2020)
- [Privacy Loss in Apple's Implementation of Differential Privacy on MacOS 10.12](https://mlsanity.com/paper/1709.02753/) (2017)
- [High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning](https://mlsanity.com/paper/1910.03865/) (2019)
- [Bitwise Neural Networks](https://mlsanity.com/paper/1601.06071/) (2016)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [Smoothed Analysis of Tensor Decompositions](https://mlsanity.com/paper/1311.3651/) (2013)
- [Differential Privacy for Eye-Tracking Data](https://mlsanity.com/paper/1904.06809/) (2019)
- [The Smoothed Possibility of Social Choice](https://mlsanity.com/paper/2006.06875/) (2020)
- [How Likely Are Large Elections Tied?](https://mlsanity.com/paper/2011.03791/) (2020)
- [The Smoothed Likelihood of Doctrinal Paradox](https://mlsanity.com/paper/2105.05138/) (2021)

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

- [Differential privacy from axioms](https://mlsanity.com/paper/2511.21876/) (2025)

## Abstract (arXiv)

Differential privacy (DP) is a widely-accepted and widely-applied notion of privacy based on worst-case analysis. Often, DP classifies most mechanisms without additive noise as non-private (Dwork et al., 2014). Thus, additive noises are added to improve privacy (to achieve DP). However, in many real-world applications, adding additive noise is undesirable (Bagdasaryan et al., 2019) and sometimes prohibited (Liu et al., 2020). In this paper, we propose a natural extension of DP following the worst average-case idea behind the celebrated smoothed analysis (Spielman & Teng, May 2004). Our notion, smoothed DP, can effectively measure the privacy leakage of mechanisms without additive noises under realistic settings. We prove that any discrete mechanism with sampling procedures is more private than what DP predicts, while many continuous mechanisms with sampling procedures are still non-private under smoothed DP. In addition, we prove several desirable properties of smoothed DP, including composition, robustness to post-processing, and distribution reduction. Based on those properties, we propose an efficient algorithm to calculate the privacy parameters for smoothed DP. Experimentally, we verify that, according to smoothed DP, the discrete sampling mechanisms are private in real-world elections, and some discrete neural networks can be private without adding any additive noise. We believe that these results contribute to the theoretical foundation of realistic privacy measures beyond worst-case analysis.