In differentially private deep learning, the sensitivity is determined by clipping gradient norm (see Abadi et al.'s paper). In this paper, when the clipping gradient norm is $C$, the sensitivity is $C$. Why is the sensitivity $C$? I think the sensitivity should be $2C$.


This is because they're using a definition of adjacency where you only consider two pairs of inputs adjacent when one record has been added or removed, instead of arbitrarily changed.

(…) each training dataset is a set of image-label pairs; 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.

   Definition 1.  A randomized mechanism $\mathcal M: \mathcal D\to\mathcal R$ with domain $\mathcal D$ and range $\mathcal R$ satisfies $(\epsilon,\delta)$-differential privacy if for any two adjacent inputs $d,d'\in\mathcal D$ and for any subset of outputs $S\subseteq\mathcal R$ it holds that $$\Pr[\mathcal M(d)\in S]≤e^\epsilon\Pr[\mathcal M(d')\in S]+\delta.$$

Since each record contributes a value in $[-C,C]$ to the gradient, removing or adding a record will change the total by $C$. It would be $2C$ if the definition included "arbitrarily changing a record".


Your Answer

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.