Universally Instance-Optimal Mechanisms for Private Statistical Estimation

We consider the problem of instance-optimal statistical estimation under the constraint of differential privacy where mechanisms must adapt to the difficulty of the input dataset. We prove a
new instance specific lower bound using a new divergence and show it characterizes the local minimax optimal rates for private statistical estimation. We propose two new mechanisms that are
universally instance-optimal for general estimation problems up to logarithmic factors. Our first
mechanism, the total variation mechanism, builds on the exponential mechanism with stable approximations of the total…