Skip to content (access key 's')
Logo of Technion
Logo of CS Department


Theory Seminar: Nearly Instance-Optimal Mechanisms in Differential Privacy
event speaker icon
Hilal Asi (Stanford University)
event date icon
Wednesday, 8.1.2020, 12:30
event location icon
Taub 201 Taub Bld.
We develop differentially private mechanisms that achieve nearly instance-optimal losses, achieving lower loss than all appropriately unbiased mechanisms for any possible instance. We show that our mechanisms, with a modest increase in sample size (logarithmic or constant), are instance-optimal for a large family of functions. In contrast to existing mechanisms, which use the global or local sensitivity of the function being estimated, and so are necessarily instance suboptimal, the key to our construction is to use the inverse of the sensitivity. This allows a simple instance-optimal algorithm, and we develop several representative private mechanisms, including for the median and regression problems.
[Back to the index of events]