Gradient perturbation, widely used for differentially private optimization, injects noise at every iterative update to guarantee differential privacy. Previous work first determines the noise level that can satisfy the privacy requirement and then analyzes the utility of noisy gradient updates as in non-private case. In this paper, we explore how the privacy noise affects the optimization property. We show that for differentially private convex optimization, the utility guarantee of both DP-GD and DP-SGD is determined by an expected curvature rather than the minimum curvature. The expected curvature represents the average curvature over the optimization path, which is usually much larger than the minimum curvature and hence can help us achieve a significantly improved utility guarantee. By using the expected curvature, our theory justifies the advantage of gradient perturbation over other perturbation methods and closes the gap between theory and practice. Extensive experiments on real world datasets corroborate our theoretical findings.
This paper proposes a quantity called expected curvature to analyze the convergence of gradient perturbation based methods that achieves differential privacy. Comparing to minimum curvature, which was used in previous convergence analyses, expected curvature better captures the properties of the optimization problem, and thus offers an explanation for the advantage of gradient perturbation based methods over objective perturbation and output perturbation.
Using expected curvature is a pretty interesting idea, and having more refined convergence bound is useful. I have the following questions.
1. It seems to me that the convergence bound is similar to previous bound, except that \mu is replaced by \nu and one log(n) disappears. Could you explain more intuitively how hard the new analysis is? Is it similar to just replacing any \mu by \nu in the previous analysis? And why do they differ by log(n)?
2. How are the experiments (in terms of setup and results) differ from those in Iyengar et al? It seems to me the paper is proposing a method for convergence analysis and the DP algorithms remain the same. I feel like in Iyengar et al, there is no clear difference between gradient perturbation and objective perturbation. Maybe I was wrong about that, but could you elaborate more?
3. I agree that the expected curvature better captures the convergence of gradient-based DP methods. Yet I don’t see clearly how this can be used to show that they have more advantages than objective perturbation. Is it possible that the analyses of objective perturbation can also be improved (maybe with other techniques)? Since all we have are upper bounds, I feel like it is a bit early to conclude that it is less powerful. You mentioned that “That is because DP makes the worst-case assumption on query function and output/objective perturbation treat the whole learning algorithm as a single query to private dataset. ” I didn’t follow this part. I feel like DP is always making a worst-case assumption; even for gradient perturbation, you need to add noise to protect the worst case. Could you elaborate more on that?
4. My understanding is that for different dataset the curvatures would be different. I think it might be interesting if you plot something similar to Figure 1 for other datasets and compare how they match with the training curve. Do you expect them to look very different on different dataset / optimization problem?