Differential Privacy of Gradient Descent on Perturbed Objectives
Proves explicit privacy bounds for finite gradient-descent iterates on perturbed objectives, removing ambient-dimension factors for generalized linear models.
The paper studies releasing the N-th iterate of deterministic gradient descent on a strongly convex, smooth objective perturbed by a once-drawn Gaussian linear term. The authors prove the noise-to-iterate map is a C^1-diffeomorphism with a quantitative lower bound on the Jacobian's smallest singular value, enabling direct change-of-variables privacy analysis. For generalized linear models, the privacy-profile bound has no explicit ambient-dimension factor once the iteration condition holds, and the finite-iteration correction decreases geometrically, recovering the exact-minimizer certificate in the limit. Expected excess empirical risk is bounded by d*sigma^2/(2*mu) plus a geometrically decreasing optimization term, with transfer to population risk.
- Diffeomorphism proof with Jacobian singular-value bound enables change-of-variables DP analysis
- GLM privacy bound removes explicit ambient-dimension dependence
- Finite-iteration correction decays geometrically toward the exact-minimizer certificate
- Excess risk bounded by d*sigma^2/(2*mu) plus geometric optimization term
From the original article
1 min read at arxiv.orgObjective 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.
By Austin Watkins · arxiv.org
A short excerpt; the article and its images belong to the publisher. Summary, key facts and assessment above are AI-written from the article and can be wrong.