Smoothed Differential Privacy
arXiv:2107.01559
Abstract
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.
arXiv comment16 Page main text + Appendix
References in corpus (13)
- Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations
- Renyi Differential Privacy
- Binarized Neural Networks
- Fixed Point Quantization of Deep Convolutional Networks
- Incremental Network Quantization: Towards Lossless CNNs with Low-Precision Weights
- A Survey on Methods and Theories of Quantized Neural Networks
- Scalable Methods for 8-bit Training of Neural Networks
- WRPN: Wide Reduced-Precision Networks
- Bitwise Neural Networks
- High-Dimensional Stochastic Gradient Quantization for Communication-Efficient Edge Learning
- Gaussian Differential Privacy
- The Smoothed Possibility of Social Choice
- How Private Are Commonly-Used Voting Rules?