  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
$\ell_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.
