{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:41:09Z","timestamp":1787341269277,"version":"build-2736575974"},"reference-count":51,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"name":"National Science Foundation Graduate Research Fellowship","award":["1122374"],"award-info":[{"award-number":["1122374"]}]},{"name":"TwoSigma PhD Fellowship"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2024,8,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>A central issue in machine learning is how to train models on sensitive user data. Industry has widely adopted a simple algorithm: Stochastic Gradient Descent (SGD) with noise (a.k.a. Stochastic Gradient Langevin Dynamics). However, foundational theoretical questions about this algorithm\u2019s privacy loss remain open\u2014even in the seemingly simple setting of smooth convex losses over a bounded domain. Our main result resolves these questions: for a large range of parameters, we characterize the differential privacy up to a constant factor. This result reveals that all previous analyses for this setting have the wrong qualitative behavior. Specifically, while previous privacy analyses increase ad infinitum in the number of iterations, we show that after a small burn-in period, running SGD longer leaks no further privacy. Our analysis departs from previous approaches based on fast mixing, instead using techniques based on optimal transport (namely, Privacy Amplification by Iteration) and the Sampled Gaussian Mechanism (namely, Privacy Amplification by Sampling). Our techniques readily extend to other settings, e.g., strongly convex losses, nonuniform stepsizes, arbitrary batch sizes, and random or cyclic choice of batches.<\/jats:p>","DOI":"10.1137\/23m1556538","type":"journal-article","created":{"date-parts":[[2024,7,19]],"date-time":"2024-07-19T05:00:01Z","timestamp":1721365201000},"page":"969-1001","source":"Crossref","is-referenced-by-count":2,"title":["On the Privacy of Noisy Stochastic Gradient Descent for Convex Optimization"],"prefix":"10.1137","volume":"53","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7367-0097","authenticated-orcid":true,"given":"Jason M.","family":"Altschuler","sequence":"first","affiliation":[{"name":"Department of Statistics and Data Science, UPenn, Philadelphia, PA 19104 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jinho","family":"Bok","sequence":"additional","affiliation":[{"name":"Department of Statistics and Data Science, UPenn, Philadelphia, PA 19104 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[{"name":"Apple, Cupertino, CA 95014 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2024,7,19]]},"reference":[{"key":"ref1","unstructured":"M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean, M. Devin, S. Ghemawat, G. Irving, M. Isard, et\u00a0al., TensorFlow: A system for large-scale machine learning, in Proceedings of the Symposium on Operating Systems Design and Implementation, 2016, pp. 265\u2013283."},{"key":"ref2","doi-asserted-by":"crossref","unstructured":"M. Abadi, A. Chu, I. Goodfellow, H. B. McMahan, I. Mironov, K. Talwar, and L. Zhang, Deep learning with differential privacy, in Proceedings of the Conference on Computer and Communications Security, 2016, pp. 308\u2013318.","DOI":"10.1145\/2976749.2978318"},{"key":"ref3","volume-title":"Proceedings of NeurIPS","author":"Altschuler J. M.","year":"2022"},{"key":"ref4","unstructured":"J. M. Altschuler and K. Talwar, Resolving the mixing time of the Langevin algorithm to its stationary distribution for log-concave sampling, in Proceedings of the Conference on Learning Theory, 2023, pp. 2509\u20132510."},{"key":"ref5","first-page":"6277","volume-title":"Advances in Neural Information Processing Systems","volume":"31","author":"Balle B.","year":"2018"},{"key":"ref6","first-page":"11282","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Bassily R.","year":"2019"},{"key":"ref7","unstructured":"R. Bassily, C. Guzman, and A. Nandi, Non-Euclidean differentially private stochastic convex optimization, in Proceedings of the Conference on Learning Theory, PMLR, 2021, pp. 474\u2013499."},{"key":"ref8","doi-asserted-by":"crossref","unstructured":"R. Bassily, A. Smith, and A. Thakurta, Private empirical risk minimization: Efficient algorithms and tight error bounds, in Symposium on Foundations of Computer Science, IEEE, 2014, pp. 464\u2013473.","DOI":"10.1109\/FOCS.2014.56"},{"key":"ref9","unstructured":"J. Bradbury, R. Frostig, P. Hawkins, M. J. Johnson, C. Leary, D. Maclaurin, G. Necula, A. Paszke, J. VanderPlas, S. Wanderman-Milne, and Q. Zhang, JAX: Composable Transformations of Python+NumPy Programs, 2018, http:\/\/github.com\/google\/jax."},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1561\/2200000050"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-018-9992-1"},{"key":"ref12","first-page":"1069","volume":"12","author":"Chaudhuri K.","year":"2011","journal-title":"J. Mach. Learn. Res."},{"key":"ref13","unstructured":"S. Chewi, M. A. Erdogdu, M. B. Li, R. Shen, and M. Zhang, Analysis of Langevin Monte Carlo from Poincar\u00e9 to log-Sobolev, in Proceedings of the Conference on Learning Theory, 2022, pp. 1\u20132."},{"key":"ref14","first-page":"14771","volume-title":"Advances in Neural Information Processing Systems","volume":"34","author":"Chourasia R.","year":"2021"},{"key":"ref15","doi-asserted-by":"publisher","DOI":"10.1111\/rssb.12183"},{"key":"ref16","volume":"30","author":"Ding B.","year":"2017","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.3150\/18-BEJ1073"},{"key":"ref18","doi-asserted-by":"crossref","unstructured":"C. Dwork, F. McSherry, K. Nissim, and A. Smith, Calibrating noise to sensitivity in private data analysis, in Proceedings of the Conference on Theory of Cryptography, 2006, pp. 265\u2013284.","DOI":"10.1007\/11681878_14"},{"key":"ref19","unstructured":"C. Dwork and G. N. Rothblum, Concentrated Differential Privacy, preprint, arXiv:1603.01887, 2016."},{"key":"ref20","doi-asserted-by":"crossref","unstructured":"\u00da. Erlingsson, V. Pihur, and A. Korolova, Randomized aggregatable privacy-preserving ordinal response, in Proceedings of the Conference on Computer and Communications Security, 2014, pp. 1054\u20131067.","DOI":"10.1145\/2660267.2660348"},{"key":"ref21","doi-asserted-by":"crossref","unstructured":"V. Feldman, T. Koren, and K. Talwar, Private stochastic convex optimization: Optimal rates in linear time, in Proceedings of the Symposium on the Theory of Computing, 2020, pp. 439\u2013449.","DOI":"10.1145\/3357713.3384335"},{"key":"ref22","doi-asserted-by":"crossref","unstructured":"V. Feldman, I. Mironov, K. Talwar, and A. Thakurta, Privacy amplification by iteration, in Proceedings of the Symposium on Foundations of Computer Science, IEEE, 2018, pp. 521\u2013532.","DOI":"10.1109\/FOCS.2018.00056"},{"key":"ref23","unstructured":"A. Ganesh and K. Talwar, personal communication, 2022."},{"key":"ref24","first-page":"7222","volume-title":"Advances in Neural Information Processing Systems","volume":"33","author":"Ganesh A.","year":"2020"},{"key":"ref25","unstructured":"A. Ganesh, A. Thakurta, and J. Upadhyay, Universality of langevin diffusion for private optimization, with applications to sampling from rashomon sets, in Conference on Learning Theory, PMLR, 2023, pp. 1730\u20131773."},{"key":"ref26","unstructured":"S. Gopi, Y. T. Lee, and D. Liu, Private convex optimization via exponential mechanism, in Proceedings of the Conference on Learning Theory, PMLR, 2022, pp. 1948\u20131989."},{"key":"ref27","unstructured":"M. Hardt, B. Recht, and Y. Singer, Train faster, generalize better: Stability of stochastic gradient descent, in Proceedings of the International Conference on Machine Learning, 2016, pp. 1225\u20131234."},{"key":"ref28","unstructured":"P. Jain and A. G. Thakurta, (Near) dimension independent risk bounds for differentially private learning, in Proceedings of the International Conference on Machine Learning, PMLR, 2014, pp. 476\u2013484."},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1137\/090756090"},{"key":"ref30","unstructured":"D. Kifer, A. Smith, and A. Thakurta, Private convex empirical risk minimization and high-dimensional regression, in Proceedings of the Conference on Computational Learning Theory, 2012, pp. 25\u201321."},{"key":"ref31","doi-asserted-by":"crossref","unstructured":"J. Liu and K. Talwar, Private selection from private candidates, in Proceedings of the Symposium on Theory of Computing, 2019, pp. 298\u2013309.","DOI":"10.1145\/3313276.3316377"},{"key":"ref32","doi-asserted-by":"crossref","unstructured":"F. McSherry and K. Talwar, Mechanism design via differential privacy, in Proceedings of the Symposium on Foundations of Computer Science, 2007, pp. 94\u2013103.","DOI":"10.1109\/FOCS.2007.66"},{"key":"ref33","volume-title":"Advances in Neural Information Processing Systems","volume":"29","author":"Minami K.","year":"2016"},{"key":"ref34","doi-asserted-by":"crossref","unstructured":"I. Mironov, R\u00e9nyi differential privacy, in Proceedings of the Computer Security Foundations Symposium, IEEE, 2017, pp. 263\u2013275.","DOI":"10.1109\/CSF.2017.11"},{"key":"ref35","unstructured":"I. Mironov, K. Talwar, and L. Zhang, R\u00e9nyi Differential Privacy of the Sampled Gaussian Mechanism, preprint, arXiv:1908.10530, 2019."},{"key":"ref36","volume-title":"Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis","author":"Mitzenmacher M.","year":"2017"},{"key":"ref37","series-title":"Appl. Optim. 87","volume-title":"Introductory Lectures on Convex Optimization: A Basic Course","author":"Nesterov Y.","year":"2003"},{"key":"ref38","unstructured":"Apple Previews IOS 10, the Biggest IOS Release Ever, 2016, https:\/\/www.apple.com\/pr\/library\/2016\/06\/13Apple-Previews-iOS-10-The-Biggest-iOS-Release-Ever.html."},{"key":"ref39","volume":"11","author":"Rogers R.","year":"2021","journal-title":"J. Priv. Confidentiality"},{"key":"ref40","unstructured":"T. Ryffel, F. Bach, and D. Pointcheval, Differential Privacy Guarantees for Stochastic Gradient Langevin Dynamics, arXiv:2201.11980, 2022."},{"key":"ref41","unstructured":"S. Shalev-Shwartz, O. Shamir, N. Srebro, and K. Sridharan, Stochastic convex optimization, in Proceedings of the Conference on Computational Learning Theory, 2009."},{"key":"ref42","unstructured":"S. Song, T. Steinke, O. Thakkar, and A. Thakurta, Evading the curse of dimensionality in unconstrained private GLMs, in Proceedings of the International Conference on Artificial Intelligence and Statistics, PMLR, 2021, pp. 2638\u20132646."},{"key":"ref43","first-page":"3025","volume-title":"Advances in Neural Information Processing Systems","volume":"28","author":"Talwar K.","year":"2015"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2320500"},{"key":"ref45","first-page":"8092","volume-title":"Advances in Neural Information Processing Systems","volume":"32","author":"Vempala S.","year":"2019"},{"key":"ref46","unstructured":"H. Wang, For the U.S. Census, Keeping Your Data Anonymous and Useful Is a Tricky Balance, 2021, https:\/\/www.npr.org\/2021\/05\/19\/993247101\/for-the-u-s-census-keeping-your-data-anonymous-and-useful-is-a-tricky-balance."},{"key":"ref47","doi-asserted-by":"crossref","unstructured":"Y.X. Wang, B. Balle, and S. P. Kasiviswanathan, Subsampled R\u00e9nyi differential privacy and analytical moments accountant, in Proceedings of the International Conference on Artificial Intelligence and Statistics, PMLR, 2019, pp. 1226\u20131235.","DOI":"10.29012\/jpc.723"},{"key":"ref48","unstructured":"M. Welling and Y. W. Teh, Bayesian learning via stochastic gradient Langevin dynamics, in Proceedings of the International Conference on Machine Learning, 2011, pp. 681\u2013688."},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511813658"},{"key":"ref50","doi-asserted-by":"crossref","first-page":"703","DOI":"10.52202\/068431-0051","volume":"35","author":"Ye J.","year":"2022","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"ref51","unstructured":"A. Yousefpour, I. Shilov, A. Sablayrolles, D. Testuggine, K. Prasad, M. Malek, J. Nguyen, S. Ghosh, A. Bharadwaj, J. Zhao, et\u00a0al., Opacus: User-Friendly Differential Privacy Library in PyTorch, preprint, arXiv:2109.12298, 2021."}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/23M1556538","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:12:03Z","timestamp":1787339523000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/23M1556538"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,19]]},"references-count":51,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,8,31]]}},"alternative-id":["10.1137\/23M1556538"],"URL":"https:\/\/doi.org\/10.1137\/23m1556538","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,19]]}}}