Source-linked AI summary
Concentrated Differentially Private Gradient Descent with Adaptive per-Iteration Privacy Budget
Jaewoo Lee, Daniel Kifer
TL;DR
The paper addresses the limitations of fixed iteration counts and evenly split privacy budgets in private gradient descent. It adaptively allocates zCDP budget using noisy gradient quality and line search, with gradient averaging to reuse earlier estimates. The resulting method is reported effective for private model fitting across privacy levels, though iteration tuning and SVM accuracy instability remain documented limitations.
Problem
Fixed iteration counts and evenly divided privacy budgets can either stop optimization early or swamp gradients with noise, despite gradients needing greater accuracy near the optimum.
Method
The algorithm dynamically selects per-iteration zCDP budget and step size from noisy-gradient utility, while recycling inadequate gradient estimates through averaging.
Results
The method is empirically effective across a wide range of privacy levels on real-dataset ERM tasks, and UCI Adult logistic regression maintained decreasing objective values despite noisy gradients.
Takeaways & Limitations
Runtime privacy-budget adaptation provides a general framework for selecting budget shares from the utility of intermediate privacy-preserving statistics.
Takeaways & Limitations
The iteration count remains heuristically set as T=c·(n·ε), requiring careful tuning because it depends on c.
Abstract
from arXiv · showhide
Iterative algorithms, like gradient descent, are common tools for solving a variety of problems, such as model fitting. For this reason, there is interest in creating differentially private versions of them. However, their conversion to differentially private algorithms is often naive. For instance, a fixed number of iterations are chosen, the privacy budget is split evenly among them, and at each iteration, parameters are updated with a noisy gradient. In this paper, we show that gradient-based algorithms can be improved by a more careful allocation of privacy budget per iteration. Intuitively, at the beginning of the optimization, gradients are expected to be large, so that they do not need to be measured as accurately. However, as the parameters approach their optimal values, the gradients decrease and hence need to be measured more accurately. We add a basic line-search capability that helps the algorithm decide when more accurate gradient measurements are necessary. Our gradient descent algorithm works with the recently introduced zCDP version of differential privacy. It outperforms prior algorithms for model fitting and is competitive with the state-of-the-art for $(ε,δ)$-differential privacy, a strictly weaker definition than zCDP.
1 INTRODUCTION
Private gradient descent traditionally fixes the iteration count and splits privacy budget evenly, although gradient magnitudes typically decline during optimization. The paper proposes adaptive zCDP budget allocation, noisy line search, and gradient reuse to improve private model fitting.
- Motivation: Prior private iterative algorithms fix the number of iterations and evenly split the total privacy budget across them.This can make accuracy depend heavily on the preset iteration count and increase gradient noise when too many iterations are used.
- Motivation: As optimization approaches the optimum, gradients decrease and require more accurate measurement, motivating adaptive rather than fixed privacy allocation.Large early gradients can support useful updates despite less accurate measurement.
- Contribution: The proposed zCDP strategy assigns smaller budget shares to large-norm gradients and larger shares to small-norm gradients.It can run more iterations when gradients are large and fewer, more accurate iterations when gradients are small.
- Empirical motivation: On UCI Adult logistic regression, the true gradient magnitude fell from approximately 0.7 to 0.05 while the noisy gradient declined only from 0.91 to approximately 0.516.Despite the larger noisy-gradient norm, the objective continued decreasing because the noisy gradient remained a descent direction.
- Contribution: A noisy line search uses part of each iteration’s budget to select a step size that approximately minimizes the next objective value.The method evaluates predefined step sizes, including zero, with a differentially private noisy-min procedure.
- Contribution: When a noisy gradient is insufficient for an update, the algorithm increases the next budget share and merges a new measurement with the previous estimate.This recycles information rather than discarding the earlier noisy gradient.
- Evaluation: Experiments on real datasets report effectiveness across a wide range of privacy levels against recently proposed empirical risk minimization algorithms.The paper positions the algorithm as a zCDP method for private model fitting.
2 RELATED WORK
Prior work includes objective perturbation, iterative gradient perturbation, stochastic-gradient methods, variance reduction, and evolutionary candidate search. These iterative approaches use predetermined privacy-budget sequences rather than runtime adaptation.
- Objective perturbation: Objective perturbation adds a linear noise term to the ERM objective and solves the perturbed problem with a non-private optimizer.Its privacy guarantee assumes the optimization problem is solved exactly, whereas practical optimization is usually approximate.
- Gradient perturbation: Iterative gradient perturbation methods add noise to gradients, including Gaussian-noise SGD under (ε,δ)-differential privacy.Related work also combines gradient perturbation with stochastic variance reduction and derives near-optimal utility results in some settings.
- Evolutionary search: PrivGene uses a fixed total iteration count, generates candidate solutions through an evolutionary procedure, and selects among them with the exponential mechanism.This differs in approach from gradient-based iterative methods.
- Gap: All the discussed iterative algorithms use predetermined privacy-budget sequences.The paper’s central distinction is runtime adaptation based on the utility of intermediate statistics.
3 BACKGROUND
The paper reviews differential privacy, sensitivity, composition, zCDP, and private selection mechanisms used to construct its algorithm. zCDP composes additively and includes a Gaussian-mechanism guarantee.
- Differential privacy: Differential privacy compares randomized outputs on neighboring datasets that differ by one observation.Pure differential privacy has δ=0, while approximate differential privacy has δ>0.
- Sensitivity: The L1 and L2 sensitivities measure the maximum query-output change over neighboring datasets when one individual’s data changes.The Gaussian mechanism calibrates noise to L2 sensitivity.
- Composition: Under basic composition, sequentially applying a mechanism k times yields a privacy loss that grows linearly to (kε,kδ)-differential privacy.Advanced composition can provide sublinear growth in the privacy loss.
- zCDP: zCDP requires the privacy-loss random variable to be concentrated around zero through a bound involving its moment generating function.The paper uses Rényi-divergence-based zCDP composition results.
- zCDP: Two zCDP facts support the method: privacy costs compose additively, and a Gaussian mechanism satisfies ∆2(q)^2/(2σ^2)-zCDP.These results connect gradient-noise variance and per-iteration privacy allocation.
- Private selection: NoisyMax adds independent Laplace noise scaled by sensitivity and privacy budget, then returns the candidate with the largest noisy value.NoisyMin is obtained by applying NoisyMax to the negated objective.
4 GRADIENT AVERAGING FOR ZCDP
The gradient-averaging technique improves a noisy gradient estimate when the algorithm increases its per-iteration zCDP budget. It reuses the first estimate and adds an independent measurement using only the incremental budget.
- Initial estimate: At iteration t, the algorithm measures a noisy gradient using a zCDP budget share ρ_t and gradient L2 sensitivity ∆2(∇f).The resulting estimate has noise determined by the allocated privacy share.
- Adaptive reuse: If the estimate is not accurate enough, the algorithm raises the next privacy share to ρ_t+1 and takes another independent measurement using ρ_t+1−ρ_t.The earlier estimate is retained rather than discarded.
- Privacy accounting: Computing the initial and additional measurements uses a total privacy cost of ρ_t+1.Thus, recycling the estimate reaches the next budget level without exceeding that level’s total cost.
5 ALGORITHM
DP-AGD combines private gradient approximation, noisy step-size selection, and adaptive noise reduction under zCDP. It dynamically spends privacy budget during execution while controlling step sizes and preserving formal privacy guarantees.
- DP-AGD has three main components: private gradient approximation, step-size selection, and adaptive noise reduction.
- Step size selection: The algorithm tests noisy gradient directions by evaluating candidate step sizes and selecting among their noisy objective values with NoisyMax.The candidate set includes the current objective value, allowing the algorithm to reject directions that do not produce a decrease.
- Adaptive noise reduction: When a noisy direction is judged poor, DP-AGD increases the gradient privacy budget and uses gradient averaging to improve that estimate.The budget increase is multiplicative in 1 + γ, and the additional cost is the difference between the new and old gradient budgets.
- Privacy accounting: The algorithm dynamically computes and deducts zCDP costs during execution instead of allocating all per-iteration budgets in advance.Its primitive operations include noisy gradient measurement, NoisyMax, and gradient averaging when needed.
- Adjusting step sizes: DP-AGD adapts the candidate step-size range using recently selected step sizes to control update variance and accommodate smaller effective moves.Every τ iterations, it updates αmax from the largest recent selected step size, scaled by 1 + η.
- Privacy guarantee: Algorithm 2 satisfies ρ-zCDP and (ϵtot,δtot)-differential privacy.The guarantee follows from accounting for the privacy costs of the algorithm’s primitive operations and composing their zCDP guarantees.
6 EXPERIMENTAL RESULTS
The experiments evaluate DP-AGD on five real datasets against seven baseline methods using classification accuracy and final objective value. Additional experiments examine parameter robustness, finding that performance is relatively robust to internal settings and splits when privacy is less restrictive.
- Datasets: DP-AGD is evaluated on five real datasets: Adult, BANK, IPUMS-BR, IPUMS-US, and KDDCup99.The datasets contain census, banking, and network-packet attributes, with Adult containing 48,842 records and IPUMS-BR and IPUMS-US containing 38,000 and 40,000 records.
- Baselines: The comparison includes seven baselines: ObjPert, OutPert, PrivGene, SGD-Adv, SGD-MA, NonPrivate, and Majority.The baselines cover objective perturbation, output perturbation, private optimization methods, a non-private optimizer, and a majority-class predictor.
- Evaluation: Reported metrics are classification accuracy and final objective value, averaged over 20 repetitions of 5-fold cross-validation.
- Parameter robustness: DP-AGD’s internal-parameter performance is described as relatively robust in logistic-regression experiments on the Adult dataset.
- Parameter robustness: The experiments fix splits=60, and Figure 1a reports that DP-AGD is relatively less affected by splits when ϵ is large.The passage notes that excessively small splits can matter when ϵ = 0.1, but the supplied text does not complete that result.
(d) Effect of Cobj (left: accuracy, right: obj. value)
DP-AGD’s performance is sensitive to threshold settings and privacy level, while its broader experiments show competitive classification and objective values across privacy budgets. The method can be unstable on the BANK SVM task, and baseline iteration counts require tuning.
- Effect of Cobj: Moderate Cobj values between 2 and 8 have little impact on accuracy or final objective value, whereas excessively small or large values degrade performance.The paper attributes this trade-off to information loss at low thresholds and excessive sensitivity, hence more noise, at high thresholds.
- Logistic regression: DP-AGD consistently outperforms or matches other algorithms across privacy levels, especially at ϵ = 0.05 except on BANK.The method checks whether noisy statistics can decrease the objective before using them, avoiding unhelpful updates.
- Baseline limitations: Baseline accuracies depend heavily on a pre-specified iteration count T, which must be tuned before execution and may consume additional privacy budget.PrivGene uses T = c · (n · ϵ), but T still requires careful tuning because it depends on c.
- SVM: DP-AGD achieves competitive SVM accuracies across a wide range of ϵ values.This result is reported for comparisons against baseline algorithms in the SVM experiments.
- SVM: BANK SVM accuracy can decrease as privacy budget increases, although its objective value consistently decreases with ϵ.For example, accuracy at ϵ = 0.4 is lower than at ϵ = 0.1.
7 CONCLUSION
The paper develops an iterative differential privacy algorithm that adaptively determines each iteration’s privacy budget from the utility of privacy-preserving statistics. Although demonstrated for private ERM, the framework may extend to other problems.
- The algorithm adaptively determines the per-iteration privacy budget based on the utility of privacy-preserving statistics.
- The framework addresses existing private algorithms’ lack of runtime adaptivity to intermediate statistical utility.
- The proposed method is demonstrated for private empirical risk minimization and may be applicable to other problems.