1
$\begingroup$

As far as I understand, the Gaussian Mechanism uses the sensitivity of the input function to determine the right amount of noise. In DP-SGD, said input function is taking the gradient and clipping it to some norm C. Then the Gaussian Mechanism is used with C as the noise-determining parameter. this should mean the sensitivity of gradient clipping is C, i.e. the maximum distance that two clipped gradients obtained from neighboring data sets can have is C. But the gradient computation can yield arbitrarily different vectors from neighboring inputs, and the maximum (L2-)distance two arbitrary vectors of (L2-)norm 1 can have is 2! What am I not seeing?

$\endgroup$

1 Answer 1

1
$\begingroup$

The notion of sensitivity is relative to the definition of adjacency. Sensitivity is the maximum of the absolute distance $|f(d) − f(d)|$ where $d$ and $d'$ are adjacent inputs. Adjacency may be defined in slightly different ways. In Abadi et al. 2016 it is defined as:

we say that two of these sets are adjacent if they differ in a single entry, that is, if one image-label pair is present in one set and absent in the other

It is also the definition used in Dwork and Roth 2014 (Definition 2.3).

But it is true that some authors define adjacency of $D$ and $D'$ by the fact it is sufficient to change one observation in $D$ to get $D'$. Which can be confusing.

In the case of DP-SGD (Abadi et al. 2016), this means that among all possible observations in your universe you add one (one gradient appears) or remove one (one gradient disappears), so 2 outputs from adjacent datasets will differ by $C$ at most (not $2C$).

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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