Local Sensitivity in Exponential Selection: Failure Modes and Valid Calibrations
The paper investigates when using data-dependent sensitivity can safely replace global sensitivity in private selection tasks where one chooses an element from a finite range to maximize a score. It demonstrates that naive applications of local or smooth sensitivities fail because neighboring datasets can have arbitrarily different local sensitivities, leading to poor privacy guarantees.