Schrödinger Mechanisms: Optimal Differential Privacy Mechanisms for Small Sensitivity

We consider the problem of designing optimal differential privacy mechanisms with a favorable privacy-utility tradeoff in the limit of a large number n of compositions (i.e., sequential queries). Here, utility is measured by the average distance between the mechanism's input and output, evaluated by a cost function c. We show that if n is sufficiently large and the sensitivities of all queries are small, then the optimal additive noise …