Privately Estimating Black-Box Statistics
This work addresses the challenge of applying differential privacy to complex, real-world functions where traditional methods fail, offering a practical solution for data analysts and privacy researchers.
The paper tackled the problem of differentially private estimation for arbitrary black-box functions where sensitivity bounds are unknown, by presenting a scheme that balances statistical efficiency and oracle efficiency, with near-optimality shown through lower bounds.
Standard techniques for differentially private estimation, such as Laplace or Gaussian noise addition, require guaranteed bounds on the sensitivity of the estimator in question. But such sensitivity bounds are often large or simply unknown. Thus we seek differentially private methods that can be applied to arbitrary black-box functions. A handful of such techniques exist, but all are either inefficient in their use of data or require evaluating the function on exponentially many inputs. In this work we present a scheme that trades off between statistical efficiency (i.e., how much data is needed) and oracle efficiency (i.e., the number of evaluations). We also present lower bounds showing the near-optimality of our scheme.