Privacy Amplification by Iteration

By Vitaly Feldman, Ilya Mironov, Kunal Talwar, Abhradeep Thakurta. 2018

205 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computer Science Applications, Privacy & Security

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Science Applications

In Privacy & Security

Citations in the corpus

The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks (2018, background): “Of course, these improved proof techniques often rely on additional (albeit realistic) assumptions, such as that random shuffling can be used to provide unlinkability [17] or that the intermediate model weights computed during training can be hidden from the adversary [18].”
Advances and Open Problems in Federated Learning (2019, background): “However, it is unclear whether or not the results in [163] can be carried over to the non-convex setting.”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “We do not consider privacy amplification by iteration (Feldman et al., 2018) in this paper, as it only applies to smooth convex functions.”
Privacy Amplification by Decentralization (2020, methodology): “Our theoretical analysis leverages recent results on privacy amplification by subsampling [2], shuffling [17, 11, 4] and iteration [18], drawing interesting connections with these schemes.”
Differentially Private Learning Needs Better Features (or Much More Data) (2020, methodology): “Here, we take a closer look at the “Privacy Amplification by Iteration” work of (Feldman et al., 2018).”
Privacy Amplification via Random Check-Ins (2020, background): “Lastly, privacy amplification by iteration [21] is another recent advancement that can be applied in an iterative distributed setting, but it is limited to convex objectives.”
Secure Federated Submodel Learning (2019, background): “[26] analyzed the detailed amplification effect of hiding intermediate results on differential privacy.”
The Privacy Blanket of the Shuffle Model (2019, methodology): “These include amplification by subsampling [22] and by iteration [16], and the recent seminal work on amplification via shuffling by Erlingsson et al.”
Differentially-Private "Draw and Discard" Machine Learning (2018, background): “Proof of Lemma 3: We rely on the result from concurrent and independent work of [19] obtained in a different context to analyze the privacy amplification in this case.”
BLENDER: Enabling Local Search with a Hybrid Differential Privacy Model (2017, background): “Works by [33] and [20] show that there is much to be gained by combining trusted curator data with public data, giving another example of a hybrid model that holds promise.”
Measuring Forgetting of Memorized Training Examples (2022, background): “[20]; improved bounds on privacy leakage for examples seen earlier in training also translate to additional robustness against concrete (empirical) adversaries.”
Improving Deep Learning with Differential Privacy using Gradient Encoding and Denoising (2020, background): “2 Deep Learning with Differential Privacy Several works have used differential privacy in traditional machine learning algorithms to protect the privacy of the training data [12, 6, 9, 21, 3].”
Adversary Instantiation: Lower Bounds for Differentially Private Machine Learning (2021, background): “In the special case of training convex models, it turns out there is a way to directly analyze the privacy of the final learned model [21].”
TAN without a burn: Scaling Laws of DP-SGD (2022, background): “Some works have successfully taken into account this “privacy amplification by iteration” idea (Feldman et al., 2018; Ye & Shokri, 2022) but results are so far limited to convex models.”
Automatic Discovery of Privacy–Utility Pareto Fronts (2019, methodology): “This choice is also aligned with recent uses of DP in machine learning where the privacy analysis is conducted under the framework of Rényi DP [39] and the reported privacy is obtained a posteriori by converting the guarantees to standard (ε, δ)-DP for some fixed δ [1, 18, 22, 38, 48].”
Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses (2020, methodology): “In particular, bounds on the uniform stability of SGD from [20] have been crucial in the design and analysis of new DP-SCO algorithms [36, 12, 17, 2, 16].”
Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification (2020, methodology): “To implement this subroutine, we follow a long line of work that studies private data analysis with access to an auxiliary public dataset Sh drawn from the same distribution P , for which we don’t need to provide formal privacy guarantee [2, 3, 5, 16, 28].”