In this talk, I will review private procedures (typically called mechanisms) for releasing functions of a sample, focusing on differential privacy and related strong definitions of privacy. I will describe mechanisms that enjoy instance-optimal — meaning that in a strong sense, they achieve the best possible behavior for the given problem instance — guarantees. On the methodological side, I will highlight a few examples, including median estimation and statistical risk minimization. On the more theoretical side, I will describe techniques for giving such instance-optimal bounds, highlighting the desiderata I believe one must satisfy for an optimality result to truly mean optimal.
This is based on joint work with Hilal Asi and Feng Ruan.