Timezone: »

 
Poster
Subset-Based Instance Optimality in Private Estimation
Travis Dick · Alex Kulesza · Ziteng Sun · Ananda Suresh

Thu Jul 27 04:30 PM -- 06:00 PM (PDT) @ Exhibit Hall 1 #330
in Poster Session 6 »
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.
[ PDF] 

Author Information

Travis Dick (Google)
Alex Kulesza (Google)
Ziteng Sun (Google Research)
Ananda Suresh (Google Research)

More from the Same Authors