Average-Case Averages: Private Algorithms for Smooth Sensitivity and\n Mean Estimation

The simplest and most widely applied method for guaranteeing differential\nprivacy is to add instance-independent noise to a statistic of interest that is\nscaled to its global sensitivity. However, global sensitivity is a worst-case\nnotion that is often too conservative for realized dataset instances. We\nprovide methods for scaling noise in an instance-dependent way and demonstrate\nthat they provide greater accuracy under average-case distributional\nassumptions.\n Specifically, we consider the basic problem of privately estimating the mean\nof a real distribution from i.i.d.~samples. The standard empirical mean\nestimator can have arbitrarily-high global sensitivity. We propose the trimmed\nmean estimator, which interpolates between the mean and the median, as a way of\nattaining much lower sensitivity on average while losing very little in terms\nof statistical accuracy.\n To privately estimate the trimmed mean, we revisit the smooth sensitivity\nframework of Nissim, Raskhodnikova, and Smith (STOC 2007), which provides a\nframework for using instance-dependent sensitivity. We propose three new\nadditive noise distributions which provide concentrated differential privacy\nwhen scaled to smooth sensitivity. We provide theoretical and experimental\nevidence showing that our noise distributions compare favorably to others in\nthe literature, in particular, when applied to the mean estimation problem.\n