Privately Estimating Black-Box Statistics

2025/09/30 by Günter F. Steinke, Thomas Steinke, Steinke, Günter F. +1 · 1 citation
Business, Management and Accounting · Mathematics · Social Sciences · #Census and Population Estimation #Computational Complexity (cs.CC) #Consumer Market Behavior and Pricing #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Names, Identity, and Discrimination Research

paper · pdf · doi:10.48550/arxiv.2510.00322

openalex publication_date 2025/09/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

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.

Citations

• Necessity of Block Designs for Optimal Locally Private Distribution Estimation
• Privately Evaluating Untrusted Black-Box Functions
• A short proof of the existence of designs
• Exactly Minimax-Optimal Locally Differentially Private Sampling
• Private Mean Estimation with Person-Level Differential Privacy
• A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy
• PLAN: Variance-Aware Private Mean Estimation
• A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions
• From Robustness to Privacy and Back
• A Bias-Accuracy-Privacy Trilemma for Statistical Estimation
• Near Optimal Private and Robust Linear Regression
• Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions
• Analyzing the Differentially Private Theil-Sen Estimator for Simple Linear Regression
• Private and polynomial time algorithms for learning Gaussians and beyond
• Differential privacy and robust statistics in high dimensions
• FriendlyCore: Practical Differentially Private Aggregation
• Hyperparameter Tuning with Renyi Differential Privacy
• Covariance-Aware Private Mean Estimation Without Private Covariance Estimation
• Non-parametric Differentially Private Confidence Intervals for the Median
• Improved Rates for Differentially Private Stochastic Convex Optimization with Heavy-Tailed Data
• Instance-optimal Mean Estimation Under Differential Privacy
• Robust and Differentially Private Mean Estimation
• On Avoiding the Union Bound When Answering Multiple Differentially Private Queries
• A bounded-noise mechanism for differential privacy
• Privately Answering Counting Queries with Generalized Gaussian Mechanisms
• CoinPress: Practical Private Mean and Covariance Estimation
• Near Instance-Optimality in Differential Privacy
• Private Mean Estimation of Heavy-Tailed Distributions
• Propose, Test, Release: Differentially private estimation with high probability
• Differentially Private Confidence Intervals
• Private Selection from Private Candidates
• Private PAC learning implies finite Littlestone dimension
• Privately Learning High-Dimensional Distributions
• Individual Sensitivity Preprocessing for Data Privacy
• Scalable Private Learning with PATE
• Finite Sample Differentially Private Confidence Intervals
• Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data
• Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
• Concentrated Differential Privacy
• Efficient Lipschitz Extensions for High-Dimensional Graph Statistics and Node Private Degree Distributions
• Differentially Private Release and Learning of Threshold Functions
• Between Pure and Approximate Differential Privacy
• Privacy and Statistical Risk: Formalisms and Minimax Bounds
• The existence of designs
• On the Geometry of Differential Privacy

Cited by

• Privacy by Postprocessing the Discrete Laplace Mechanism

Related

• Black-Box Differentially Private Nonparametric Confidence Intervals Under Minimal Assumptions
• The Cost of Privacy: Optimal Rates of Convergence for Parameter Estimation with Differential Privacy
• Instance-Specific Asymmetric Sensitivity in Differential Privacy
• Differentially private inference via noisy optimization
• Privately Evaluating Untrusted Black-Box Functions