mlsanityData to 14 Oct 2026

Privately Estimating Black-Box Statistics

arXiv 2510.00322 ↗First posted 30 Sep 2025cs.CR cs.CC cs.DScited by 1

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 42 of its 69 references that are in the map. First posted on arXiv 30 Sep 2025.

Builds on

42 of 69 references.

References · 42

  1. 2016Semi-supervised Knowledge Transfer for Deep Learning from Private Training Datacited by 348
  2. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 346
  3. 2018Scalable Private Learning with PATEcited by 269
  4. 2016Concentrated Differential Privacycited by 144
  5. 2017Finite Sample Differentially Private Confidence Intervalscited by 104
  6. 2018Privately Learning High-Dimensional Distributionscited by 104
  7. 2021Hyperparameter Tuning with Renyi Differential Privacycited by 104
  8. 2018Private Selection from Private Candidatescited by 75
  9. 2018Private PAC learning implies finite Littlestone dimensioncited by 74
  10. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  11. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  12. 2021Robust and Differentially Private Mean Estimationcited by 66
30 more
  1. 2021Differential privacy and robust statistics in high dimensionscited by 64
  2. 2015Differentially Private Release and Learning of Threshold Functionscited by 60
  3. 2015Between Pure and Approximate Differential Privacycited by 56
  4. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  5. 2021Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Datacited by 47
  6. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  7. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  8. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  9. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  10. 2023From Robustness to Privacy and Backcited by 27
  11. 2020Near Instance-Optimality in Differential Privacycited by 23
  12. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  13. 2020Differentially Private Confidence Intervalscited by 20
  14. 2020Propose, Test, Release: Differentially private estimation with high probabilitycited by 15
  15. 2020A bounded-noise mechanism for differential privacycited by 15
  16. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  17. 2024A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacycited by 11
  18. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  19. 2015Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributionscited by 8
  20. 2018Individual Sensitivity Preprocessing for Data Privacycited by 8
  21. 2021Non-parametric Differentially Private Confidence Intervals for the Mediancited by 7
  22. 2022Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regressioncited by 6
  23. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  24. 2024Private Mean Estimation with Person-Level Differential Privacycited by 6
  25. 2020On Avoiding the Union Bound When Answering Multiple Differentially Private Queriescited by 5
  26. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  27. 2024Exactly Minimax-Optimal Locally Differentially Private Samplingcited by 5
  28. 2020Privately Answering Counting Queries with Generalized Gaussian Mechanismscited by 4
  29. 2025Privately Evaluating Untrusted Black-Box Functionscited by 1
  30. 2025Necessity of Block Designs for Optimal Locally Private Distribution Estimationcited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Privately Estimating Monotone Statistics in Polynomial Timecited by 0