Characterizing Private Clipped Gradient Descent on Convex Generalized Linear Problems

By Shuang Song, Om Thakkar, Abhradeep Thakurta. 2020

51 citations recorded by the source corpus.

Differentially private gradient descent (DP-GD) has been extremely effective both theoretically, and in practice, for solving private empirical risk minimization (ERM) problems. In this paper, we focus on understanding the impact of the clipping norm, a critical component of DP-GD, on its convergence. We provide the first formal convergence analysis of clipped DP-GD. More generally, we show that the value which one sets for clipping really matters: done wrong, it can dramatically affect the resulting quality; done properly, it can eliminate the dependence of convergence on the model dimensionality. We do this by showing a dichotomous behavior of the clipping norm. First, we show that if the clipping norm is set smaller than the optimal, even by a constant factor, the excess empirical risk for convex ERMs can increase from $O(1/n)$ to $\Omega(1)$, where $n$ is the number of data samples. Next, we show that, regardless of the value of the clipping norm, clipped DP-GD minimizes a well-defined convex objective over an unconstrained space, as long as the underlying ERM is a generalized linear problem. Furthermore, if the clipping norm is set within at most a constant factor higher than the optimal, then one can obtain an excess empirical risk guarantee that is independent of the dimensionality of the model space. Finally, we extend our result to non-convex generalized linear problems by showing that DP-GD reaches a first-order stationary point as long as the loss is smooth, and the convergence is independent of the dimensionality of the model space.

Subfields: Artificial Intelligence, Statistics and Probability

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

Citations in the corpus

Tempered Sigmoid Activations for Deep Learning with Differential Privacy (2020, methodology): “According to (Song, Thakkar, and Thakurta 2020; Chen, Wu, and Hong 2020), gradient clipping can introduce bias that significantly affect model utility.”
Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification (2020, background): “More recently, [32] show that, for a class of generalized linear problems, DP gradient descent (without any projection) achieves an excess empirical risk bound depending on the rank of the feature matrix instead of the ambient dimension.”