Differentially private convex optimization with piecewise affine objectives: some subgradient approaches

In this paper we propose two new private subgradient methods: the bootstrapped private subgradient method and the private weighted average subgradient method. These are compared via a simulation study with the Laplace mechanism, the exponential mechanism, the private subgradient method and random uniform variables. We find that the exponential mechanism and the private weighted average subgradient method perform best depending on the situation, as instances can be generated for both mechanisms in which one performs better than the other and vice versa. However, the exponential mechanism seems to outperform the private weighted subgradient method in most cases treated in this paper.