Privacy guarantees improve for gradient descent on noisy objectives
Differential Privacy of Gradient Descent on Perturbed Objectives
Machine LearningCryptography and Security
Summary
When machines learn from private data, they need to keep individual data points safe. This paper looks at a way to do this by adding random noise to the learning process and releasing the results after some steps of a common training method called gradient descent. The authors show conditions when this process keeps privacy well and how the privacy improves as the training progresses. They also explain how this method keeps the learning accurate while still protecting data.
What this means in practice
- •For machine learning engineers: Provide privacy guarantees when running gradient descent on sensitive datasets using noisy objective perturbations with explicit iteration counts.
- •For data privacy teams: Assess privacy risks more accurately for gradient descent algorithms applied to generalized linear models in privacy-sensitive environments.
A theory result. No direct application yet.
Authors
Austin Watkins, Raman Arora
Abstract
Objective perturbation adds a random linear term to a regularized empirical risk and releases the exact perturbed minimizer. We study the finite computation obtained by releasing the $N$-th iterate of deterministic gradient descent on $w\mapsto F(w;S)+\langle z,w\rangle$, where $z\sim\mathcal N(0,σ^2I_d)$ is drawn once before optimization. For strongly convex and smooth objectives with Lipschitz Hessian, we prove an explicit condition under which the map $z\mapsto w_N$ is a $C^1$-diffeomorphism on the bounded domains used in the privacy argument, with a quantitative lower bound on the smallest singular value of its Jacobian. This permits a direct change-of-variables analysis of the finite iterate. For generalized linear models, the resulting privacy-profile bound has no explicit ambient-dimension factor once the iteration condition holds, and its finite-iteration correction decreases geometrically. By letting the free truncation parameter grow slowly with $N$, we recover the corresponding exact-minimizer certificate in the limit. We also bound the expected excess empirical risk by $dσ^2/(2μ)$ plus a geometrically decreasing optimization term, and transfer the result to population risk without an additional multiplicative condition-number factor in the leading statistical terms.