Differential Privacy of Gradient Descent on Perturbed Objectives
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↦ F(w;S)+⟨ z,w⟩, where z∼𝒩(0,σ2Id) is drawn once before optimization. For strongly convex and smooth objectives with Lipschitz Hessian, we prove an explicit condition under which the map z↦ wN is a C1-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.
Related
- The Exact Time-Uniform Rate Frontier for Stochastic Gradient Descent on Smooth Convex Objectives
- Not All Objectives Are Born Equal: Priority-Constrained Descent for Hierarchical Multi-Objective Optimization
- Deflation-Based Spectral Preconditioning for the Conjugate Gradient Method on Perturbed Systems
- Finite-Sample Approximation of Hessian-Guided Perturbed Wasserstein Gradient Flows
- Prophet Inequalities under Local Differential Privacy
BibTeX
@misc{watkins2026differential,
title = {{Differential Privacy of Gradient Descent on Perturbed Objectives}},
author = {Austin Watkins and Raman Arora},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.02716},
eprint = {2610.02716},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.02716},
}
RIS
TY - UNPB
TI - Differential Privacy of Gradient Descent on Perturbed Objectives
AU - Austin Watkins
AU - Raman Arora
PY - 2026
DA - 2026/10/02
PB - arXiv
DO - 10.48550/arxiv.2610.02716
UR - https://arxiv.org/abs/2610.02716
AB - 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↦ F(w;S)+⟨ z,w⟩, where z∼𝒩(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↦ 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.
ER -