Wei Ding
Research Areas
Authored Publications
Sort By
Optimal Noise-Adding Mechanism in Additive Differential Privacy
Quan Geng
Proceedings of the 22th International Conference on Artificial Intelligence and Statistics (AISTATS) (2019)
Preview abstract
We derive the optimal $(0, \delta)$-differentially private query-output independent noise-adding mechanism for single real-valued query function under a general cost-minimization framework. Under a mild technical condition, we show that the optimal noise probability distribution is a uniform distribution with a probability mass at the origin. We explicitly derive the optimal noise distribution for general $\ell^p$ cost functions, including $\ell^1$ (for noise magnitude) and $\ell^2$ (for noise power) cost functions, and show that the probability concentration on the origin occurs when $\delta > \frac{p}{p+1}$. Our result demonstrates an improvement over the existing Gaussian mechanisms by a factor of two and three for $(0,\delta)$-differential privacy in the high privacy regime in the context of minimizing the noise magnitude and noise power, and the gain is more pronounced in the low privacy regime. Our result is consistent with the existing result for $(0,\delta)$-differential privacy in the discrete setting, and identifies a probability concentration phenomenon in the continuous setting.
View details
Preview abstract
We characterize the minimum noise amplitude and power for noise-adding mechanisms in (epsilon, delta)-differential privacy for single real-valued query function. We derive new lower bounds using the duality of linear programming, and new upper bounds by proposing a new class of (epsilon, delta)-differentially private mechanisms, the \emph{truncated Laplacian} mechanisms. We show that the multiplicative gap of the lower bounds and upper bounds goes to zero in various high privacy regimes, proving the tightness of the lower and upper bounds and thus establishing the optimality of the truncated Laplacian mechanism. In particular, our results close the previous constant multiplicative gap in the discrete setting. Numeric experiments show the improvement of the truncated Laplacian mechanism over the optimal Gaussian mechanism in all privacy regimes.
View details
On the Capacity Region of Broadcast Packet Erasure Relay Networks With Feedback
Quan Geng
Hieu Do
Rui Wu
Mindi Yuan
Yun Li
IEEE International Conference on Communications, IEEE (2019)
Preview abstract
We derive a new outer bound on the capacity region of broadcast traffic in multiple input broadcast packet erasure channels with feedback, and extend this outer bound to packet erasure relay networks with feedback. We show the tightness of the outer bound for various classes of networks. An important engineering implication of this work is that for network coding schemes for parallel broadcast channels, the ``xor'' packets should be sent over correlated broadcast subchannels.
View details
