title: Gradient Perturbation is Underrated for Differentially Private Convex Optimization
abstract: 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 \emph{expected curvature} rather than the minimum curvature. The \emph{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 \emph{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.
authors: Da Yu Huishuai Zhang Wei Chen Tie-yan Liu Jian Yin
hIndex: Tie-yan Liu 68