R$^2$DP: A Universal and Automated Approach to Optimizing the Randomization Mechanisms of Differential Privacy for Utility Metrics with No Known Optimal Distributions

Differential privacy (DP) has emerged as a de facto standard privacy notion\nfor a wide range of applications. Since the meaning of data utility in\ndifferent applications may vastly differ, a key challenge is to find the\noptimal randomization mechanism, i.e., the distribution and its parameters, for\na given utility metric. Existing works have identified the optimal\ndistributions in some special cases, while leaving all other utility metrics\n(e.g., usefulness and graph distance) as open problems. Since existing works\nmostly rely on manual analysis to examine the search space of all\ndistributions, it would be an expensive process to repeat such efforts for each\nutility metric. To address such deficiency, we propose a novel approach that\ncan automatically optimize different utility metrics found in diverse\napplications under a common framework. Our key idea that, by regarding the\nvariance of the injected noise itself as a random variable, a two-fold\ndistribution may approximately cover the search space of all distributions.\nTherefore, we can automatically find distributions in this search space to\noptimize different utility metrics in a similar manner, simply by optimizing\nthe parameters of the two-fold distribution. Specifically, we define a\nuniversal framework, namely, randomizing the randomization mechanism of\ndifferential privacy (R$^2$DP), and we formally analyze its privacy and\nutility. Our experiments show that R$^2$DP can provide better results than the\nbaseline distribution (Laplace) for several utility metrics with no known\noptimal distributions, whereas our results asymptotically approach to the\noptimality for utility metrics having known optimal distributions. As a side\nbenefit, the added degree of freedom introduced by the two-fold distribution\nallows R$^2$DP to accommodate the preferences of both data owners and\nrecipients.\n