# Subset-Based Instance Optimality in Private Estimation

arXiv: https://arxiv.org/abs/2303.01262 · HTML: https://mlsanity.com/paper/2303.01262/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 25 references that are in the map.
- First posted on arXiv 1 Mar 2023.

## Builds on (most cited first, 15 of 15)

- [Improving the Gaussian Mechanism for Differential Privacy: Analytical Calibration and Optimal Denoising](https://mlsanity.com/paper/1805.06530/) (2018)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Learning with User-Level Privacy](https://mlsanity.com/paper/2102.11845/) (2021)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Instance-optimal Mean Estimation Under Differential Privacy](https://mlsanity.com/paper/2106.00463/) (2021)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Towards Instance-Optimal Private Query Release](https://mlsanity.com/paper/1811.03763/) (2018)
- [Instance-Optimal Differentially Private Estimation](https://mlsanity.com/paper/2210.15819/) (2022)
- [The Laplace Mechanism has optimal utility for differential privacy over continuous queries](https://mlsanity.com/paper/2105.07176/) (2021)

## Built on by (most cited first, 3 of 3)

- [Mean estimation in the add-remove model of differential privacy](https://mlsanity.com/paper/2312.06658/) (2023)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [The importance of feature preprocessing for differentially private linear optimization](https://mlsanity.com/paper/2307.11106/) (2023)

## Abstract (arXiv)

We propose a new definition of instance optimality for differentially private estimation algorithms. Our definition requires an optimal algorithm to compete, simultaneously for every dataset D, with the best private benchmark algorithm that (a) knows D in advance and (b) is evaluated by its worst-case performance on large subsets of D. That is, the benchmark algorithm need not perform well when potentially extreme points are added to D; it only has to handle the removal of a small number of real data points that already exist. This makes our benchmark significantly stronger than those proposed in prior work. We nevertheless show, for real-valued datasets, how to construct private algorithms that achieve our notion of instance optimality when estimating a broad class of dataset properties, including means, quantiles, and ℓp-norm minimizers. For means in particular, we provide a detailed analysis and show that our algorithm simultaneously matches or exceeds the asymptotic performance of existing algorithms under a range of distributional assumptions.