Unlocking the Potential of Composition for General Neighborhood Definitions

The composability properties of differential privacy (DP) are key to the construction of most DP algorithms. However, the new neighborhood definitions and data domains in the literature are not covered by the original composition theorems. For instance, the parallel composition theorem does not translate well to general neighborhoods. These limitations make it difficult to compute accurate estimates of the privacy loss when composing DP mechanisms in new settings.

To overcome this problem, we prove a general composition theorem in a general framework, defined for any kind of data domain or neighborhood definition. We also study the hypothesis needed to obtain the best composition bounds. Our theorems cover both parallel and sequential composition settings, as well as any effect of preprocessing, allowing us to compute the final privacy loss of a composition with greatly improved accuracy.