Privately Estimating Black-Box Statistics

Günter Steinke, Thomas Steinke
Proceedings of Thirty Ninth Conference on Learning Theory, PMLR 336:6029-6074, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v336-steinke26a, title = {Privately Estimating Black-Box Statistics}, author = {Steinke, G\"unter and Steinke, Thomas}, booktitle = {Proceedings of Thirty Ninth Conference on Learning Theory}, pages = {6029--6074}, year = {2026}, editor = {Hanneke, Steve and Lattimore, Tor}, volume = {336}, series = {Proceedings of Machine Learning Research}, month = {29 Jun--03 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v336/main/assets/steinke26a/steinke26a.pdf}, url = {https://proceedings.mlr.press/v336/steinke26a.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T Privately Estimating Black-Box Statistics %A Günter Steinke %A Thomas Steinke %B Proceedings of Thirty Ninth Conference on Learning Theory %C Proceedings of Machine Learning Research %D 2026 %E Steve Hanneke %E Tor Lattimore %F pmlr-v336-steinke26a %I PMLR %P 6029--6074 %U https://proceedings.mlr.press/v336/steinke26a.html %V 336 %X 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.
APA
Steinke, G. & Steinke, T.. (2026). Privately Estimating Black-Box Statistics. Proceedings of Thirty Ninth Conference on Learning Theory, in Proceedings of Machine Learning Research 336:6029-6074 Available from https://proceedings.mlr.press/v336/steinke26a.html.

Related Material