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".