Privacy Amplification by Iteration

Vitaly Feldman; Ilya Mironov; Kunal Talwar; Abhradeep Thakurta

Source-linked AI summary

Privacy Amplification by Iteration

Vitaly Feldman, Ilya Mironov, Kunal Talwar, Abhradeep Thakurta

arXiv:1808.06651v2Aug 20, 2018cs.LGcs.CRcs.DSstat.ML

TL;DR

The paper asks how to analyze privacy for iterative learning algorithms without paying composition costs for released intermediate states. It introduces amplification by iteration for contractive noisy processes and applies it to noisy stochastic gradient descent. The results include privacy advantages without random or hidden sampling order and show that ˜O(d) public data points can make privacy error comparable to statistical error.

Problem
Existing composition analyses assume intermediate outputs are revealed, while sampling-based amplification requires random and secret participation that may be impractical in distributed learning.
Method
The paper introduces amplification by iteration, analyzing contractive maps with additive Gaussian noise through a theorem that tracks shrinking Rényi divergence.
Results
˜O(d) public data points can make the additional privacy error comparable to statistical error in convex optimization, while distributed applications do not require random or hidden participation order.
Takeaways & Limitations
Contractive noisy iterations can provide useful privacy amplification in distributed and convex-optimization settings where privacy amplification by sampling cannot be applied.

Abstract

from arXiv · show

Many commonly used learning algorithms work by iteratively updating an intermediate solution using one or a few data points in each iteration. Analysis of differential privacy for such algorithms often involves ensuring privacy of each step and then reasoning about the cumulative privacy cost of the algorithm. This is enabled by composition theorems for differential privacy that allow releasing of all the intermediate results. In this work, we demonstrate that for contractive iterations, not releasing the intermediate results strongly amplifies the privacy guarantees. We describe several applications of this new analysis technique to solving convex optimization problems via noisy stochastic gradient descent. For example, we demonstrate that a relatively small number of non-private data points from the same distribution can be used to close the gap between private and non-private convex optimization. In addition, we demonstrate that we can achieve guarantees similar to those obtainable using the privacy-amplification-by-sampling technique in several natural settings where that technique cannot be applied.

1 Introduction

The paper introduces amplification by iteration: contractive noisy processes can provide stronger privacy when only the final output is released. It applies this analysis to noisy stochastic gradient descent, including settings where sampling-based amplification is unavailable.

1 Introduction: Amplification by iteration analyzes contractive iterative algorithms without releasing intermediate outputs, rather than composing privacy guarantees for every revealed step.The paper presents this as an alternative to privacy amplification by sampling in suitable settings.
1 Introduction: A general theorem shows that contractive iterations shrink Rényi divergence between output distributions, using Gaussian noise and contractive maps as the basic setting.The analysis interpolates initial metric distance and final information-theoretic divergence through shifted divergence.
1 Introduction: In an n-step mechanism, the first processed record incurs privacy loss equal to 1/n of the last record’s loss, without requiring the processing order to be random or secret.The comparison applies when only the final step is measured and intermediate steps are not revealed.
1 Introduction: The approach supports distributed learning without random or hidden participation order, allowing communication proportional to mini-batch size and privacy amplification with arbitrarily small per-step noise.Smaller noise can permit smaller mini-batches, further reducing communication costs.
1 Introduction: The analysis also supports solving ˜Ω(n) convex optimization problems over n parties at the same privacy cost as answering one problem.The approach gives stronger privacy to earlier participants while offering guarantees similar to the last participant.
1 Introduction: With ˜O(d) public data points, convex optimization under mild smoothness assumptions can achieve privacy-induced error comparable to statistical error.Public samples can be used in later iterations, reducing the error from noise by a factor of √m when m public samples are available.

2 Preliminaries

The preliminaries establish the notation for convex learning problems and the privacy divergences used throughout the paper. They introduce shifted Rényi divergence and its key composition and post-processing properties.

Problem setup: The paper studies convex loss minimization over a convex model set K, using data sampled independently from a distribution P.The loss is convex in the model parameter, while dependence on each data point may be arbitrary.
Problem setup: L-Lipschitz continuity bounds loss changes by L times the Euclidean distance between model points.
Problem setup: β-smoothness bounds gradient changes by β times the Euclidean distance between model points.
Privacy tools: Rényi divergence measures distinguishability between distributions, is additive on product distributions, and cannot increase under deterministic post-processing.
Privacy tools: Shifted Rényi divergence combines divergence with a bounded coupling shift, providing a norm-aware distance used to analyze privacy under iterative updates.The paper also defines noise sensitivity through the largest Rényi divergence between a noise distribution and bounded shifts of itself.
Privacy tools: Standard RDP composition adds the per-mechanism privacy parameters when all intermediate outputs are revealed.RDP can also be converted into (ε, δ)-differential privacy.

3 Coupled Descent

The coupled-descent analysis tracks two contractive noisy iterations through shifted Rényi divergence. Its central conclusion is that later noise reduces divergence between final outputs even when intermediate states remain unreleased.

Iteration framework: Contractive noisy iterations begin from nearby states and repeatedly apply contractive maps followed by noise, producing final distributions whose Rényi divergence can be bounded.
Iteration framework: The main theorem improves standard one-step reasoning because subsequent noise decreases Rényi divergence despite arbitrary contractive steps between noise additions.
Proof strategy: The proof uses shifted Rényi divergence to represent bounded state differences and reduce the shift parameter when noise is added.
Proof strategy: Contractive maps preserve the relevant shifted-divergence bound, using post-processing and a coupling whose distance increases only by the maps’ discrepancy.
Main theorem: The general theorem handles changes in several iterative maps, enabling analyses of algorithms that access data points more than once.

4 Privacy Guarantees for Noisy Stochastic Gradient Descent

The paper applies amplification by iteration to noisy stochastic gradient descent and its variants. Contractivity makes privacy stronger for earlier records, while public data and distributed execution yield practical benefits under stated smoothness and noise conditions.

Baseline PNSGD: PNSGD updates a projected model using one data point, a gradient step, and fresh Gaussian noise at every iteration.The update uses learning rate η, noise scale σ, and projection onto the convex set K.
Baseline PNSGD: Gradient steps are contractive under mild smoothness, projections are contractive, and final projection is post-processing, making PNSGD a contractive noisy iteration.
Baseline PNSGD: Earlier-used records receive stronger privacy because noise injected in subsequent steps further obscures their influence.
Algorithm variants: Skip-PNSGD randomly skips an initial segment of records and retains privacy guarantees at least as good as baseline PNSGD.
Algorithm variants: Stop-PNSGD randomly chooses a stopping time and outputs the corresponding iterate, with its analysis relying on a weak convexity property of Rényi divergence.

5 Applications

The applications use amplified privacy from contractive iterations to improve privacy and utility in distributed, multi-query, and public-data convex optimization settings. The analysis also extends to non-smooth objectives through Gaussian smoothing.

Distributed optimization: Distributed optimization cannot generally use privacy amplification by sampling when communication reveals party participation, so the iteration-based approach supplies stronger global privacy.Applying sampling amplification would require concealing participation; an untrusted channel could therefore force all parties to communicate in every step.
Stochastic convex optimization: The noisy projected stochastic-gradient process uses unbiased stochastic subgradients and projection onto K to optimize a convex population objective.The baseline utility analysis bounds expected objective values averaged over the iterates, including a randomly stopped execution.
Per-index privacy: Per-index privacy improves for records processed earlier: Skip-PNSGD provides (ε/√(n−t+1), δ)-DP at index t while retaining overall (ε, δ)-DP.The stated guarantee assumes convex L-Lipschitz, β-smooth losses and a learning rate satisfying the contractivity condition.
Public data: Θ(d ln(1/δ)/ε^2) non-private samples from the same distribution suffice for utility guarantees matching non-private learning up to a constant factor.Public samples are used at the end of training, where the corresponding data points incur no privacy cost.
Multiple queries: For multiple convex optimization tasks, the analysis bounds the joint output’s privacy while allowing stronger privacy for early users and direct (ε, δ)-DP accounting.For k≤n, the cited comparison states that competing multiplicative-weights bounds are worse, while they can be better when k≫n and d is small.
Removing smoothness: Gaussian convolution effectively removes the smoothness assumption in several applications by producing a convex, Lipschitz, smooth approximation with controlled error.The approximation retains L-Lipschitzness and has smoothness L/λ, while its pointwise error is bounded by Lλ.

A Contractivity of Gradient Descent for Smooth Functions

Gradient descent on a convex β-smooth function is contractive when the learning rate is below 2/β. This contractivity underlies the paper’s iterative privacy analysis.

A Contractivity of Gradient Descent for Smooth Functions: A gradient-descent map for a convex, twice-differentiable, β-smooth function is contractive when η < 2/β.The proof uses Hessian eigenvalues lying in [0, β] along the segment between the two input points.

B Analyzing Multiple-Epoch SGD

The multiple-epoch analysis applies amplification by iteration to projected noisy SGD with a fixed data ordering and n passes. It derives privacy for the final iterate using contractive updates rather than releasing intermediate states.

B Analyzing Multiple-Epoch SGD: Projected noisy multiple-epoch SGD makes n passes over a fixed ordering of the dataset and returns the final iterate w_n^2.Each update includes projection onto K, and the twice-differentiability condition used in the proof is technically unnecessary.
B Analyzing Multiple-Epoch SGD: The final algorithm satisfies (ε, δ)-DP for a Gaussian noise scale established by the theorem, with contractivity requiring η ≤ 2/β.The paper states that the bound follows directly from the general iteration theorem and gives a cleaner proof than the sampling-amplification approach.
B Analyzing Multiple-Epoch SGD: The privacy proof models neighboring executions as contractive noise iterations whose data-dependent map differences are nonzero only when the differing example is processed.The resulting distance profile grows during affected epochs and is controlled through the induction-based iteration theorem.
B Analyzing Multiple-Epoch SGD: The fixed-ordering algorithm differs from prior sampling-based analysis, which uses n^2 steps with uniformly random data points.Utility can be obtained from standard online-learning regret bounds.

C Smoothing via Convolution with the Gaussian Kernel

Gaussian convolution extends a convex Lipschitz objective beyond its original domain and smooths it while preserving convexity and Lipschitzness. The approximation error is controlled by the kernel variance parameter.

C Smoothing via Convolution with the Gaussian Kernel: For every λ>0, a convex L-Lipschitz function on K has a convex extension that is L-Lipschitz, L/λ-smooth, and within Lλ pointwise.The theorem constructs the approximation by first forming a convex Lipschitz extension and then convolving it with a Gaussian kernel.
C Smoothing via Convolution with the Gaussian Kernel: The extension h(w)=min_v∈K f(v)+L∥w−v∥2 makes the objective well-defined on all of R^d before Gaussian convolution.Convexity and L-Lipschitzness of h transfer to the convolved function.
C Smoothing via Convolution with the Gaussian Kernel: The proof controls the convolution difference using total variation and Pinsker’s inequality for shifted Gaussian distributions.The Gaussian divergence is bounded in terms of the squared shift distance divided by 2λ^2.