Differential privacy surprises: utility is not (always) monotonic on epsilon

In the literature on differential privacy it is usually taken for granted that increasing privacy causes a decrease in utility, a behaviour known as the privacy-utility trade-off. In this talk we present a surprising result that sometimes privacy and utility can both increase (or decrease) when differential privacy mechanisms are incorporated into complex pipelines, such as those used in machine learning. We characterise this non-monotonic behaviour and provide conditions on exactly when privacy and utility behave “predictably” (that is, monotonically). Privacy experiments conducted on the COMPAS dataset demonstrate this non-monotonic behaviour in a practical setting.