NeurIPS 2020

Instance-optimality in differential privacy via approximate inverse sensitivity mechanisms

Meta Review

A very solid contribution to a very new line of work initiated by Asi & Duchi (2020) on instance-optimal mechanisms in DP. Where many popular mechanisms in DP such as Laplace, Gaussian leverage global sensitivity as a worst-case calibration of privacy-producing randomisation, Asi & Duchi developed the inverse-sensitivity mechanism as an approach to reducing noise from worst case to instance specific. The reviewers and this AC appreciated the paper's contributions to this thread. A local sensitivity approximation to the (sometimes intractable) inverse-sensitivity mechanism potentially broaden the practicality of these ideas, with utility analysis and lower bounds rounding out the theoretical treatment nicely. Focus on vector-valued functions continues in the vein of making the general approach more versatile. For these reasons of potential practicality, I felt like any limited novelty in proof techniques as highlighted by reviews are not of significant concern. I encourage the authors to adopt the key reviewer suggestions for improvement in the camera ready: discussing efficiency in the experiments to lend credence to the prime motivation of the paper; improvements to accessible exposition; a new section expounding connections to smooth sensitivity; and further discussion on the motivation of unbiasedness as suggested by R3.