1
$\begingroup$

To use the Laplace mechanism, we have to get the global sensitivity of a query function. What do we do in the case where there is one huge outlier(or multiple outliers) in the dataset such that the global sensitivity gets too large and noise added results in query outputs that do not make sense anymore. In which case can we use the local sensitivity. Any ideas, papers, references will be appreciated.

New contributor
Tiana Johnson is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
0
$\begingroup$

There's really very little that can be done in this sort of situation. The noise is only parameterised by $\Delta f/\epsilon$ where $\Delta f$ precisely represents how much the function changes when such an outlier is added or removed from a queried set and $\epsilon$ precisely quantifies how hard it is for an adversary to detect a change. Your options are essentially one or more of the following

  • make it easier for outliers to be identified (by increasing $\epsilon$);
  • purge your data of outliers (thereby reducing $\Delta f$ by changing the permissible subsets, but putting data integrity into question);
  • change your query function to something smoother so that the effect of outliers is less extreme (reducing $\Delta f$ by changing the function, but potentially losing some of the information that is captured).

All of these have drawbacks.

$\endgroup$

Your Answer

Tiana Johnson is a new contributor. Be nice, and check out our Code of Conduct.

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.