Privacy Amplification by Iteration

Abstract

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.

Extended abstract appears in Foundations of Computer Science (FOCS) 2018

References in corpus (5)

• Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data
• Privacy Amplification by Iteration
• Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo
• Subsampled Rényi Differential Privacy and Analytical Moments Accountant
• Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds

Cited by in corpus (34)

• Decentralized Federated Learning: A Survey on Security and Privacy
• How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
• Privacy Amplification by Iteration
• Differentially Private Learning Needs Better Features (or Much More Data)
• Local Differential Privacy and Its Applications: A Comprehensive Survey
• Secure Federated Submodel Learning
• Random Sampling Plus Fake Data: Multidimensional Frequency Estimates With Local Differential Privacy
• Differentially Private Synthetic Data: Applied Evaluations and Enhancements
• Improving Deep Learning with Differential Privacy using Gradient Encoding and Denoising
• Practical and Private (Deep) Learning without Sampling or Shuffling
• Bypassing the Ambient Dimension: Private SGD with Gradient Subspace Identification
• Pufferfish Privacy: An Information-Theoretic Study
• Differentially Private Federated Learning with Laplacian Smoothing
• Information-Theoretic Generalization Bounds for Stochastic Gradient Descent
• Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• Gradient Perturbation is Underrated for Differentially Private Convex Optimization
• Private Non-smooth Empirical Risk Minimization and Stochastic Convex Optimization in Subquadratic Steps
• Stability of SGD: Tightness Analysis and Improved Bounds
• Label differential privacy via clustering
• Node-Level Differentially Private Graph Neural Networks
• LazyDP: Co-Designing Algorithm-Software for Scalable Training of Differentially Private Recommendation Models
• Public Data-Assisted Mirror Descent for Private Model Training
• Local Differential Privacy in Decentralized Optimization
• Differential Privacy Dynamics of Langevin Diffusion and Noisy Gradient Descent
• Differential privacy with partial knowledge
• Privacy Amplification by Mixing and Diffusion Mechanisms
• Decentralized Differentially Private Without-Replacement Stochastic Gradient Descent
• Private Stochastic Convex Optimization: Efficient Algorithms for Non-smooth Objectives
• Muffliato: Peer-to-Peer Privacy Amplification for Decentralized Optimization and Averaging
• Improving Utility of Differentially Private Mechanisms through Cryptography-based Technologies: a Survey
• Privacy Amplification Via Bernoulli Sampling
• Amplifying Rényi Differential Privacy via Shuffling
• Privacy Amplification via Iteration for Shuffled and Online PNSGD
• Differentially Private Algorithms for Clustering with Stability Assumptions