The DOI matches its Crossref record; 50 of the 50 references it cites were found in a registry or an index.
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.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Also, without modifying the training approach, improved proof techniques have been able to improve guarantees by orders of magnitude, indicating that the analytic e is not a tight upper bound.”
From The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks (2018) · cites this paper as [18]
In the citing paper
“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].”
From The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks (2018) · cites this paper as [18]
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Communication-Efficient Learning of Deep Networks from Decentralized Data
McMahan, H. B., Moore, E., Ramage, D., Hampson, S., & Arcas, B. A. Y. (2016) · arXiv · doi:10.48550/arxiv.1602.05629 · Cited by 14,215
Calibrating Noise to Sensitivity in Private Data Analysis
Dwork, C., McSherry, F., Nissim, K., & Smith, A. (2006) · Lecture Notes in Computer Science · doi:10.1007/11681878_14 · Cited by 7,272
Deep Learning with Differential Privacy
Abadi, M., Chu, A., Goodfellow, I., McMahan, H. B., Mironov, I., Talwar, K., & Zhang, L. (2016) · Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2976749.2978318 · Cited by 6,578
Self-citationThe Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2014) · Foundations and Trends® in Theoretical Computer Science · doi:10.1561/0400000042 · Cited by 5,557
Dwork, C. (2006) · Lecture Notes in Computer Science · doi:10.1007/11787006_1 · Cited by 5,291
On Measures of Entropy and Information
Rényi, A. (1961) · Project Euclid (Cornell University) · Cited by 4,031
The Algorithmic Foundations of Differential Privacy
Dwork, C., & Roth, A. (2013) · doi:10.1561/9781601988195 · Cited by 3,856
Introductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Introductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
Smooth minimization of non-smooth functions
Nesterov, Y. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,455
Our Data, Ourselves: Privacy Via Distributed Noise Generation
Dwork, C., Kenthapadi, K., McSherry, F., Mironov, I., & Naor, M. (2006) · Lecture Notes in Computer Science · doi:10.1007/11761679_29 · Cited by 1,835
Self-citationRényi Divergence and Kullback-Leibler Divergence
van Erven, T., & Harremoes, P. (2014) · IEEE Transactions on Information Theory · doi:10.1109/tit.2014.2320500 · Cited by 1,555
Mironov, I. (2017) · 2017 IEEE 30th Computer Security Foundations Symposium (CSF) · doi:10.1109/csf.2017.11 · Cited by 1,255
Self-citationThe Enron Corpus: A New Dataset for Email Classification Research
Klimt, B., & Yang, Y. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-30115-8_22 · Cited by 1,157
Convex Optimization: Algorithms and Complexity
Bubeck, S. (2015) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000050 · Cited by 1,001
(2011) · PubMed · Cited by 990
Local Privacy and Statistical Minimax Rates
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · 2013 IEEE 54th Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.53 · Cited by 954
Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds
Bun, M., & Steinke, T. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-53641-4_24 · Cited by 584
Privacy-preserving logistic regression
Chaudhuri, K., & Monteleoni, C. (2008) · Cited by 525
Semi-supervised Knowledge Transfer for Deep Learning from Private Training Data
Papernot, N., Abadi, M., Erlingsson, Ú., Goodfellow, I., & Talwar, K. (2016) · arXiv · doi:10.48550/arxiv.1610.05755 · Cited by 492
Self-citationScalable Private Learning with PATE
Papernot, N., Song, S., Mironov, I., Raghunathan, A., Talwar, K., & Erlingsson, Ú. (2018) · arXiv · doi:10.48550/arxiv.1802.08908 · Cited by 373
Self-citationKasiviswanathan, S. P., Lee, H. K., Nissim, K., Raskhodnikova, S., & Smith, A. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.27 · Cited by 334
Preserving Statistical Validity in Adaptive Data Analysis
Dwork, C., Feldman, V., Hardt, M., Pitassi, T., Reingold, O., & Roth, A. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746580 · Cited by 296
Self-citationConcentrated Differential Privacy
Leeman, E., & Manurangsi, P. (2016) · arXiv (Cornell University) · doi:10.4230/lipics.forc.2026.4 · Cited by 271
Subsampled Rényi Differential Privacy and Analytical Moments Accountant
Wang, Y.-X., Balle, B., & Kasiviswanathan, S. P. (2020) · Journal of Privacy and Confidentiality · doi:10.29012/jpc.723 · Cited by 255
Subsampled Rényi Differential Privacy and Analytical Moments Accountant
Wang, Y.-X., Balle, B., & Kasiviswanathan, S. (2018) · arXiv · doi:10.48550/arxiv.1808.00087 · Cited by 224
Church, G. M. (2005) · Molecular Systems Biology · doi:10.1038/msb4100040 · Cited by 220
Local privacy and statistical minimax rates
Duchi, J. C., Jordan, M. I., & Wainwright, M. J. (2013) · 2013 51st Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2013.6736718 · Cited by 208
Bolt-on Differential Privacy for Scalable Stochastic Gradient Descent-based Analytics
Wu, X., Li, F., Kumar, A., Chaudhuri, K., Jha, S., & Naughton, J. F. (2017) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3035918.3064047 · Cited by 192
Randomized smoothing for stochastic optimizationPreprint
Duchi, J. C., & Wainwright, M. J. (2016) · Cited by 188
Algorithmic stability for adaptive data analysis
Bassily, R., Kobbi Nissim, B., Smith, A., Steinke, T., Stemmer, U., & Ullman, J. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897566 · Cited by 181
Private Convex Empirical Risk Minimization and High-dimensional Regression
Kifer, D., Smith, A., & Thakurta, A. (2012) · Cited by 180
Self-citationPrivacy for Free: Posterior Sampling and Stochastic Gradient Monte CarloPreprint
Wang, Y.-X., Fienberg, S. E., & Smola, A. J. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1502.07645 · Cited by 154
Differentially Private Online LearningPreprint
Jain, P., Kothari, P. K., & Thakurta, A. (2012) · Cited by 149
Self-citationTowards Practical Differentially Private Convex Optimization
Iyengar, R., Near, J. P., Song, D. X., Thakkar, O. D., Thakurta, A., & Wang, L. (2019) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2019.00001 · Cited by 145
Self-citationComposable and versatile privacy via truncated CDP
Bun, M., Dwork, C., Rothblum, G. N., & Steinke, T. (2018) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3188745.3188946 · Cited by 134
Differentially Private Feature Selection via Stability Arguments, and the Robustness of the Lasso
Thakurta, A., & Smith, A. (2013) · Conference on Learning Theory · Cited by 111
Self-citationIs Interaction Necessary for Distributed Private Learning?
Smith, A., Thakurta, A., & Upadhyay, J. (2017) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2017.35 · Cited by 105
Self-citationBounds on the Sample Complexity for Private Learning and Private Data Release
Beimel, A., Kasiviswanathan, S. P., & Kobbi Nissim, B. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-11799-2_26 · Cited by 95
Talwar, K., Thakurta, A., & Zhang, L. (2015) · neural information processing systems · Cited by 95
Self-citationDifferentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error BoundsPreprint
Bassily, R., Smith, A., & Thakurta, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1405.7085 · Cited by 87
Self-citationBounds on the sample complexity for private learning and private data release
Beimel, A., Brenner, H., Kasiviswanathan, S. P., & Kobbi Nissim, B. (2013) · Machine Learning · doi:10.1007/s10994-013-5404-1 · Cited by 79
Near) Dimension Independent Risk Bounds for Differentially Private Learning
Jain, P., & Thakurta, A. (2014) · Cited by 78
Self-citationSimultaneous Private Learning of Multiple Concepts
Bun, M., Kobbi Nissim, B., & Stemmer, U. (2016) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2840728.2840747 · Cited by 64
BLENDER: Enabling Local Search with a Hybrid Differential Privacy ModelPreprint
Avent, B., Korolova, A., Zeber, D., Hovden, T., & Livshits, B. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.00831 · Cited by 49
Private Multiplicative Weights Beyond Linear Queries
Ullman, J. (2015) · ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS) · doi:10.1145/2745754.2745755 · Cited by 35
Private Empirical Risk Minimization, Revisited.
Bassily, R., Smith, A., & Thakurta, A. (2014) · Cited by 31
Self-citationStatistical query algorithms for mean vector estimation and stochastic convex optimization
Feldman, V., Guzmán, C., & Vempala, S. (2017) · Symposium on Discrete Algorithms · doi:10.5555/3039686.3039768 · Cited by 29
Self-citationStatistical Query Algorithms for Stochastic Convex Optimization
Feldman, V., Guzmán, C., & Vempala, S. (2015) · Centrum Wiskunde & Informatica (CWI), the national research institute for mathematics and computer science in the Netherlands · doi:10.1137/1.9781611974782.82 · Cited by 11
Self-citationStatistical Query Algorithms for Mean Vector Estimation and Stochastic Convex OptimizationPreprint
Feldman, V., Guzmán, C., & Vempala, S. (2015) · arXiv (Cornell University) · doi:10.48550/arxiv.1512.09170 · Cited by 1
Self-citation
Research works printed but not linked: 1
- mironov, 2017, Rényi differential privacy, IEEE Computer Security Foundations Symposium (CSF), 263
Cited by
The Secret Sharer: Evaluating and Testing Unintended Memorization in Neural Networks
Carlini, N., Liu, C., Erlingsson, Ú., Kos, J., & Song, D. (2018) · arXiv · doi:10.48550/arxiv.1802.08232 · Cited by 629
Amplification by Shuffling: From Local to Central Differential Privacy via Anonymity
Erlingsson, Ú., Feldman, V., Mironov, I., Raghunathan, A., Talwar, K., & Thakurta, A. (2019) · Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms · doi:10.1137/1.9781611975482.151 · Cited by 264
Self-citationThe Privacy Blanket of the Shuffle Model
Balle, B., Bell, J., Gascón, A., & Nissim, K. (2019) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-26951-7_22 · Cited by 214
How to DP-fy ML: A Practical Guide to Machine Learning with Differential Privacy
Ponomareva, N., Hazimeh, H., Kurakin, A., Xu, Z., Denison, C., McMahan, H. B., Vassilvitskii, S., Chien, S., & Thakurta, A. G. (2023) · Journal of Artificial Intelligence Research · doi:10.1613/jair.1.14649 · Cited by 166
Self-citationZhou, J., Chen, S., Wu, Y., Li, H., Zhang, B., Zhou, L., Hu, Y., Xiang, Z., Li, Z., Chen, N., et al. (2024) · Science Advances · doi:10.1126/sciadv.adh8601 · Cited by 63
Metadata
- Authors
- Feldman, V., Mironov, I., Talwar, K., & Thakurta, A.
- Venue
- 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS)
- Publisher
- IEEE
- Published
- 2018-10
- Pages
- 521-532
- Cited by
- 80
- References
- 50
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.
