1
$\begingroup$

Consider a standard supervised machine learning problem on private data. Instead of using DPSGD, suppose that one uses a non-private SGD scheme to produce optimal model parameters $\theta$ (done in the private data enclave, as with DPSGD), and releases publicly $\theta + \eta$, with $\eta \sim$ Laplace$(0, \varepsilon)$ (meaning choose variance so we get $\varepsilon-$DP).

Is this a valid method of differentially private machine learning? (I think it is).

If so, how does it compare in terms of accuracy and privacy to DPSGD? I don't recall seeing it in any papers, in particular not in the original paper of Abadi et al.

$\endgroup$

2 Answers 2

2
$\begingroup$

Yes, this (can be) valid. In particular, if one views the function

$$ D\mapsto F(D) := \theta $$ that maps a dataset to model parameters as a mechanism, you can apply standard techniques to post-process this mechanism with Laplace noise and achieve differential privacy. To do this though, one needs a bound on what is known as the ($\ell_1$) sensitivity of the function. See section 3.2 for context, but this is defined as

$$ \Delta F = \sup_{D\sim D'}\lVert F(D) - F(D')\rVert_1 $$ Here, $D\sim D'$ means the set of all pairs of databases $(D, D')$ that differ in a single entry. If you can compute/bound $\Delta F$, then releasing $F(D)+e$ for $e\gets\mathsf{Lap}(\Delta F/\epsilon)$ will be $\epsilon$-DP.

As for whether this works well, I do not personally know the practical numbers. I imagine it is worse though. This is for the simple reason that it ignores the impact of privacy amplification. Privacy amplification (roughly) is the idea that for some mechanism of independent interest $F$, one can often factor it into $F = G\circ H$, where $H$ has some incidental differentially private properties. For example, perhaps during training one subsamples the data (for efficiency purposes). This also has privacy benefits. The naive analysis you suggest ignores these privacy benefits, and therefore achieves a higher amount of privacy than required, likely leading to worse performance.

$\endgroup$
1
  • $\begingroup$ thanks. I figured it out at the same time! Glad to see that you confirmed my thoughts. Thanks for the links to the subsampling to get amplification. $\endgroup$ Commented Feb 29 at 18:32
1
$\begingroup$

The method of adding noise to $\theta$ produced from a (non-private) SGD scheme (or any optimization algorithm) will provide differential privacy if we can can compute the sensitivity of $\theta$.

Suppose our loss function is $L(\theta, X) = \sum_{X,Y} l(x,y)$ (so $l$ is a per-data-point loss). Using regular gradient descent, we would initialize $\theta_0$, then for $K$ steps perform $\theta_{k+1} \leftarrow \theta_k -\alpha \nabla L(\theta_k, X, y)$

We wish to release the final $\theta_K$ with the Laplace mechanism. We must compute its sensitivity to get the variance of the Laplace distribution. Let $(X_1, Y_1)$, $(X_2, Y_2)$ be our neighboring datasets with lone different row denoted $(x_1, y_1), (x_2, y_2)$. Then $L(X_1, Y_1, \theta) - L(X_2, Y_2, \theta) = l(x_1, y_1, \theta) - l(x_2, y_2, \theta)$, and we see the difference in gradients is $\nabla L(X_1, Y_1, \theta) - \nabla L(X_2, Y_2, \theta) = \nabla l(x_1, y_1, \theta) - \nabla l(x_2, y_2, \theta)$ is the difference of the per-data-point loss across the lone row of differing values.

So estimating the sensitivity $\sup |\theta_K(X_1,Y_1) - \theta_K(X_2, Y_2)|$ is hard, even in this simplified case with identical fixed starting position, learning rate using basic gradient descent. It can be thought of as considering two ODEs with the same initial condition $\theta_0$ where the update is slightly different. Comparing the updat steps:

  1. $\dot{\theta} = \theta_{k+1} - \theta_k = -\alpha \nabla L(\theta_k, X_1, Y_1) $
  2. $\dot{\theta} = \theta_{k+1} - \theta_k = -\alpha \nabla L(\theta_k, X_2, y_2) = -\alpha \nabla L(\theta_k, X_1, Y_1) + \alpha \nabla l(x_1, y_1, \theta_k) -\alpha \nabla l(x_2, y_2, \theta_k)$.

We know that in many quite simple ODE systems, minor differences in the first few steps can lead to large differences as time progresses.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.