Efficient Propose-Test-Release for Optimal Differentially Private Estimation

Differential privacy (DP) is a rigorous framework that protects the participation of individuals in a dataset by controlling information leakage through released estimators. It brings a challenge for statisticians: DP uniformly considers all possible datasets, whereas statistical practice often downweights atypical or rare outcomes. The conceptual challenge is especially pronounced in sensitivity analysis, where atypical datasets introduces markedly high sensitivity, even for a basic estimator such as ordinary least square. Standard DP recipe adds a noise governed by this large overall sensitivity, which causes excessive loss in accuracy. We introduce an efficient Propose-Test Release (ePTR) pipeline, which tests the dataset via a user-designed Safety Lower Bound, and then probabilistically releases the estimator based on local sensitivity level. This flexible pipeline enables substantially simple DP mechanisms for many problems. To illustrate, we study basic estimators for Bayes classification, linear regression, and kernel regression. Each estimator can be highly sensitive to atypical datasets, yet admits simple ePTR-based algorithms that achieve minimax optimality. In numerical studies, these ePTR estimators demonstrate improved accuracy against popular DP baselines under privacy guarantees.