The sensitivity in differential privacy with deep learning
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 &quot;arbitrarily changing a record&quot;.