{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,23]],"date-time":"2026-08-23T15:29:55Z","timestamp":1787498995401,"version":"build-2736575974"},"publisher-location":"New York, NY, USA","reference-count":40,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384335","type":"proceedings-article","created":{"date-parts":[[2020,6,6]],"date-time":"2020-06-06T21:45:25Z","timestamp":1591479925000},"page":"439-449","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":34,"title":["Private stochastic convex optimization: optimal rates in linear time"],"prefix":"10.1145","author":[{"given":"Vitaly","family":"Feldman","sequence":"first","affiliation":[{"name":"Google Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tomer","family":"Koren","sequence":"additional","affiliation":[{"name":"Tel Aviv University, Israel \/ Google, Israel"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kunal","family":"Talwar","sequence":"additional","affiliation":[{"name":"Google Research, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2976749.2978318"},{"key":"e_1_3_2_1_2_1","volume-title":"Private Stochastic Convex Optimization with Optimal Rates. CoRR abs\/","author":"Bassily Raef","year":"1908","unstructured":"Raef Bassily , Vitaly Feldman , Kunal Talwar , and Abhradeep Thakurta . 2019. Private Stochastic Convex Optimization with Optimal Rates. CoRR abs\/ 1908 .09970 ( 2019 ). arXiv: 1908.09970 http:\/\/arxiv.org\/abs\/ 1908.09970 Extended abstract in Proceedings of NeurIPS 2019. Raef Bassily, Vitaly Feldman, Kunal Talwar, and Abhradeep Thakurta. 2019. Private Stochastic Convex Optimization with Optimal Rates. CoRR abs\/ 1908.09970 ( 2019 ). arXiv: 1908.09970 http:\/\/arxiv.org\/abs\/ 1908.09970 Extended abstract in Proceedings of NeurIPS 2019."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.56"},{"key":"e_1_3_2_1_4_1","unstructured":"Olivier Bousquet and Andr\u00e9 Elisseef. 2002. Stability and generalization. JMLR ( 2002 ).  Olivier Bousquet and Andr\u00e9 Elisseef. 2002. Stability and generalization. JMLR ( 2002 )."},{"key":"e_1_3_2_1_5_1","first-page":"635","article-title":"Concentrated Diferential Privacy: Simplifications, Extensions, and Lower Bounds. In Theory of Cryptography-14th International Conference, TCC 2016-B","author":"Bun Mark","year":"2016","unstructured":"Mark Bun and Thomas Steinke . 2016 . Concentrated Diferential Privacy: Simplifications, Extensions, and Lower Bounds. In Theory of Cryptography-14th International Conference, TCC 2016-B , Part I. 635 - 658 . Mark Bun and Thomas Steinke. 2016. Concentrated Diferential Privacy: Simplifications, Extensions, and Lower Bounds. In Theory of Cryptography-14th International Conference, TCC 2016-B, Part I. 635-658.","journal-title":"Part"},{"key":"e_1_3_2_1_6_1","volume-title":"Privacy-preserving logistic regression","author":"Chaudhuri Kamalika","unstructured":"Kamalika Chaudhuri and Claire Monteleoni . 2008. Privacy-preserving logistic regression . In NIPS, Daphne Koller, Dale Schuurmans, Yoshua Bengio, and L\u00e9on Bottou (Eds.). MIT Press . Kamalika Chaudhuri and Claire Monteleoni. 2008. Privacy-preserving logistic regression. In NIPS, Daphne Koller, Dale Schuurmans, Yoshua Bengio, and L\u00e9on Bottou (Eds.). MIT Press."},{"key":"e_1_3_2_1_7_1","unstructured":"Kamalika Chaudhuri Claire Monteleoni and Anand D Sarwate. 2011. Diferentially private empirical risk minimization. Journal of Machine Learning Research 12 Mar ( 2011 ) 1069-1109.  Kamalika Chaudhuri Claire Monteleoni and Anand D Sarwate. 2011. Diferentially private empirical risk minimization. Journal of Machine Learning Research 12 Mar ( 2011 ) 1069-1109."},{"key":"e_1_3_2_1_8_1","volume-title":"Local Privacy and Statistical Minimax Rates. In IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). 429-438","author":"Duchi John C.","unstructured":"John C. Duchi , Michael I. Jordan , and Martin J. Wainwright . 2013 . Local Privacy and Statistical Minimax Rates. In IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). 429-438 . John C. Duchi, Michael I. Jordan, and Martin J. Wainwright. 2013. Local Privacy and Statistical Minimax Rates. In IEEE 54th Annual Symposium on Foundations of Computer Science (FOCS). 429-438."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"crossref","unstructured":"Cynthia Dwork. 2006. Diferential Privacy.. In ICALP.  Cynthia Dwork. 2006. Diferential Privacy.. In ICALP.","DOI":"10.1007\/11787006_1"},{"key":"e_1_3_2_1_10_1","volume-title":"Our Data","author":"Dwork Cynthia","unstructured":"Cynthia Dwork , Krishnaram Kenthapadi , Frank McSherry , Ilya Mironov , and Moni Naor . 2006. Our Data , Ourselves : Privacy Via Distributed Noise Generation .. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006. Our Data, Ourselves: Privacy Via Distributed Noise Generation.."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11681878_14"},{"key":"e_1_3_2_1_12_1","first-page":"3","article-title":"The Algorithmic Foundations of Diferential Privacy","volume":"9","author":"Dwork Cynthia","year":"2014","unstructured":"Cynthia Dwork and Aaron Roth . 2014 . The Algorithmic Foundations of Diferential Privacy . Found. Trends Theor. Comput. Sci. 9 , 3 - 4 ( Aug. 2014 ), 211-407. Cynthia Dwork and Aaron Roth. 2014. The Algorithmic Foundations of Diferential Privacy. Found. Trends Theor. Comput. Sci. 9, 3-4 ( Aug. 2014 ), 211-407.","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"e_1_3_2_1_13_1","volume-title":"Rothblum","author":"Dwork Cynthia","year":"2016","unstructured":"Cynthia Dwork and Guy N . Rothblum . 2016 . Concentrated Diferential Privacy. CoRR abs\/1603. 01887 ( 2016 ). arXiv:1603. 01887 http:\/\/arxiv.org\/abs\/1603.01887 Cynthia Dwork and Guy N. Rothblum. 2016. Concentrated Diferential Privacy. CoRR abs\/1603. 01887 ( 2016 ). arXiv:1603. 01887 http:\/\/arxiv.org\/abs\/1603.01887"},{"key":"e_1_3_2_1_14_1","first-page":"3576","article-title":"Generalization of ERM in stochastic convex optimization: The dimension strikes back","author":"Feldman Vitaly","year":"2016","unstructured":"Vitaly Feldman . 2016 . Generalization of ERM in stochastic convex optimization: The dimension strikes back . In Advances in Neural Information Processing Systems. 3576 - 3584 . Vitaly Feldman. 2016. Generalization of ERM in stochastic convex optimization: The dimension strikes back. In Advances in Neural Information Processing Systems. 3576-3584.","journal-title":"Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_15_1","volume-title":"Privacy Amplification by Iteration. CoRR abs\/1808 ( 2018 ). Extended abstract in Proceedings of FOCS","author":"Feldman Vitaly","year":"2018","unstructured":"Vitaly Feldman , Ilya Mironov , Kunal Talwar , and Abhradeep Thakurta . 2018. Privacy Amplification by Iteration. CoRR abs\/1808 ( 2018 ). Extended abstract in Proceedings of FOCS 2018 . Vitaly Feldman, Ilya Mironov, Kunal Talwar, and Abhradeep Thakurta. 2018. Privacy Amplification by Iteration. CoRR abs\/1808 ( 2018 ). Extended abstract in Proceedings of FOCS 2018."},{"key":"e_1_3_2_1_16_1","volume-title":"High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. arXiv preprint arXiv","author":"Feldman Vitaly","year":"1902","unstructured":"Vitaly Feldman and Jan Vondrak . 2019. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. arXiv preprint arXiv : 1902 . 10710 ( 2019 ). Vitaly Feldman and Jan Vondrak. 2019. High probability generalization bounds for uniformly stable algorithms with nearly optimal rate. arXiv preprint arXiv: 1902. 10710 ( 2019 )."},{"key":"e_1_3_2_1_17_1","unstructured":"Moritz Hardt Benjamin Recht and Yoram Singer. 2015. Train faster generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv:1509.01240 ( 2015 ).  Moritz Hardt Benjamin Recht and Yoram Singer. 2015. Train faster generalize better: Stability of stochastic gradient descent. arXiv preprint arXiv:1509.01240 ( 2015 )."},{"key":"e_1_3_2_1_18_1","unstructured":"Nicholas Harvey. 2019. ( 2019 ). Personal communication.  Nicholas Harvey. 2019. ( 2019 ). Personal communication."},{"key":"e_1_3_2_1_19_1","first-page":"1579","article-title":"Tight analyses for non-smooth stochastic gradient descent","author":"Harvey Nicholas J. A.","year":"2019","unstructured":"Nicholas J. A. Harvey , Christopher Liaw , Yaniv Plan , and Sikander Randhawa . 2019 . Tight analyses for non-smooth stochastic gradient descent . In COLT. 1579 - 1613 . http:\/\/proceedings.mlr.press\/v99\/harvey19a.html Nicholas J. A. Harvey, Christopher Liaw, Yaniv Plan, and Sikander Randhawa. 2019. Tight analyses for non-smooth stochastic gradient descent. In COLT. 1579-1613. http:\/\/proceedings.mlr.press\/v99\/harvey19a.html","journal-title":"COLT."},{"key":"e_1_3_2_1_20_1","article-title":"Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization","volume":"15","author":"Hazan Elad","year":"2014","unstructured":"Elad Hazan and Satyen Kale . 2014 . Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization . The Journal of Machine Learning Research 15 , 1 ( 2014 ), 2489-2512. Elad Hazan and Satyen Kale. 2014. Beyond the regret minimization barrier: optimal algorithms for stochastic strongly-convex optimization. The Journal of Machine Learning Research 15, 1 ( 2014 ), 2489-2512.","journal-title":"The Journal of Machine Learning Research"},{"key":"e_1_3_2_1_21_1","volume-title":"Towards Practical Diferentially Private Convex Optimization","author":"Iyengar Roger","unstructured":"Roger Iyengar , Joseph P Near , Dawn Song , Om Thakkar , Abhradeep Thakurta , and Lun Wang . 2019. Towards Practical Diferentially Private Convex Optimization . In IEEE S and P (Oakland) . Roger Iyengar, Joseph P Near, Dawn Song, Om Thakkar, Abhradeep Thakurta, and Lun Wang. 2019. Towards Practical Diferentially Private Convex Optimization. In IEEE S and P (Oakland)."},{"key":"e_1_3_2_1_22_1","volume-title":"Diferentially Private Online Learning. In 25th Annual Conference on Learning Theory (COLT). 24","author":"Jain Prateek","year":"2012","unstructured":"Prateek Jain , Pravesh Kothari , and Abhradeep Thakurta . 2012 . Diferentially Private Online Learning. In 25th Annual Conference on Learning Theory (COLT). 24 . 1-24. 34. Prateek Jain, Pravesh Kothari, and Abhradeep Thakurta. 2012. Diferentially Private Online Learning. In 25th Annual Conference on Learning Theory (COLT). 24. 1-24. 34."},{"key":"e_1_3_2_1_23_1","first-page":"1752","article-title":"Making the Last Iterate of SGD Information Theoretically Optimal","author":"Jain Prateek","year":"2019","unstructured":"Prateek Jain , Dheeraj Nagaraj , and Praneeth Netrapalli . 2019 . Making the Last Iterate of SGD Information Theoretically Optimal . In COLT. 1752 - 1755 . http:\/\/proceedings.mlr.press\/v99\/jain19a.html Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. 2019. Making the Last Iterate of SGD Information Theoretically Optimal. In COLT. 1752-1755. http:\/\/proceedings.mlr.press\/v99\/jain19a.html","journal-title":"COLT."},{"key":"e_1_3_2_1_24_1","unstructured":"Prateek Jain and Abhradeep Thakurta. 2014. (Near) Dimension Independent Risk Bounds for Diferentially Private Learning. In ICML.  Prateek Jain and Abhradeep Thakurta. 2014. (Near) Dimension Independent Risk Bounds for Diferentially Private Learning. In ICML."},{"key":"e_1_3_2_1_25_1","volume-title":"Conference on Learning Theory. 25-1.","author":"Kifer Daniel","year":"2012","unstructured":"Daniel Kifer , Adam Smith , and Abhradeep Thakurta . 2012 . Private convex empirical risk minimization and high-dimensional regression . In Conference on Learning Theory. 25-1. Daniel Kifer, Adam Smith, and Abhradeep Thakurta. 2012. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory. 25-1."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSF.2017.11"},{"key":"e_1_3_2_1_27_1","volume-title":"Introductory Lectures on Convex Optimization. A Basic Course","author":"Nesterov Yurii","unstructured":"Yurii Nesterov . 2004. Introductory Lectures on Convex Optimization. A Basic Course . Springer US. Yurii Nesterov. 2004. Introductory Lectures on Convex Optimization. A Basic Course. Springer US."},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the 5th International Conference on Learning Representations (ICLR).","author":"Papernot Nicolas","year":"2017","unstructured":"Nicolas Papernot , Mart\u00edn Abadi , \u00dalfar Erlingsson , Ian Goodfellow , and Kunal Talwar . 2017 . Semi-supervised knowledge transfer for deep learning from private training data . In Proceedings of the 5th International Conference on Learning Representations (ICLR). Nicolas Papernot, Mart\u00edn Abadi, \u00dalfar Erlingsson, Ian Goodfellow, and Kunal Talwar. 2017. Semi-supervised knowledge transfer for deep learning from private training data. In Proceedings of the 5th International Conference on Learning Representations (ICLR)."},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the 6th International Conference on Learning Representations (ICLR).","author":"Papernot Nicolas","year":"2018","unstructured":"Nicolas Papernot , Shuang Song , Ilya Mironov , Ananth Raghunathan , Kunal Talwar , and \u00dalfar Erlingsson . 2018 . Scalable Private Learning with PATE . In Proceedings of the 6th International Conference on Learning Representations (ICLR). Nicolas Papernot, Shuang Song, Ilya Mironov, Ananth Raghunathan, Kunal Talwar, and \u00dalfar Erlingsson. 2018. Scalable Private Learning with PATE. In Proceedings of the 6th International Conference on Learning Representations (ICLR)."},{"key":"e_1_3_2_1_30_1","first-page":"547","volume-title":"Proceedings of the fourth Berkeley symposium on mathematical statistics and probability","volume":"1","author":"R\u00e9nyi Alfr\u00e9d","year":"1961","unstructured":"Alfr\u00e9d R\u00e9nyi . 1961 . On measures of entropy and information . In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability , Vol. 1 . 547 - 561 . Alfr\u00e9d R\u00e9nyi. 1961. On measures of entropy and information. In Proceedings of the fourth Berkeley symposium on mathematical statistics and probability, Vol. 1. 547-561."},{"key":"e_1_3_2_1_31_1","volume-title":"COLT","author":"Shalev-Shwartz Shai","unstructured":"Shai Shalev-Shwartz , Ohad Shamir , Nathan Srebro , and Karthik Sridharan . 2009. Stochastic Convex Optimization . In COLT . http:\/\/eprints.pascal-network.org\/ archive\/00005408\/ Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. 2009. Stochastic Convex Optimization. In COLT. http:\/\/eprints.pascal-network.org\/ archive\/00005408\/"},{"key":"e_1_3_2_1_32_1","unstructured":"S. Shalev-Shwartz O. Shamir N. Srebro and K. Sridharan. 2010. Learnability stability and uniform convergence. JMLR ( 2010 ).  S. Shalev-Shwartz O. Shamir N. Srebro and K. Sridharan. 2010. Learnability stability and uniform convergence. JMLR ( 2010 )."},{"key":"e_1_3_2_1_33_1","first-page":"71","article-title":"Stochastic Gradient Descent for Non-smooth Optimization","author":"Shamir Ohad","year":"2013","unstructured":"Ohad Shamir and Tong Zhang . 2013 . Stochastic Gradient Descent for Non-smooth Optimization : Convergence Results and Optimal Averaging Schemes. In ICML. 71 - 79 . Ohad Shamir and Tong Zhang. 2013. Stochastic Gradient Descent for Non-smooth Optimization: Convergence Results and Optimal Averaging Schemes. In ICML. 71-79.","journal-title":"Convergence Results and Optimal Averaging Schemes. In ICML."},{"key":"e_1_3_2_1_34_1","volume-title":"Conference on Learning Theory (COLT). 819-850","author":"Smith Adam","year":"2013","unstructured":"Adam Smith and Abhradeep Thakurta . 2013 . Diferentially Private Feature Selection via Stability Arguments, and the Robustness of the LASSO . In Conference on Learning Theory (COLT). 819-850 . Adam Smith and Abhradeep Thakurta. 2013. Diferentially Private Feature Selection via Stability Arguments, and the Robustness of the LASSO. In Conference on Learning Theory (COLT). 819-850."},{"key":"e_1_3_2_1_35_1","first-page":"58","article-title":"Is interaction necessary for distributed private learning?","author":"Smith Adam","year":"2017","unstructured":"Adam Smith , Abhradeep Thakurta , and Jalaj Upadhyay . 2017 . Is interaction necessary for distributed private learning? . In IEEE Security & Privacy. 58 - 77 . Adam Smith, Abhradeep Thakurta, and Jalaj Upadhyay. 2017. Is interaction necessary for distributed private learning?. In IEEE Security & Privacy. 58-77.","journal-title":"IEEE Security & Privacy."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/GlobalSIP.2013.6736861"},{"key":"e_1_3_2_1_37_1","first-page":"3025","volume-title":"Proceedings of the 28th International Conference on Neural Information Processing Systems","volume":"2","author":"Talwar Kunal","year":"2015","unstructured":"Kunal Talwar , Abhradeep Thakurta , and Li Zhang . 2015 . Nearly optimal private LASSO . In Proceedings of the 28th International Conference on Neural Information Processing Systems , Vol. 2 . 3025 - 3033 . Kunal Talwar, Abhradeep Thakurta, and Li Zhang. 2015. Nearly optimal private LASSO. In Proceedings of the 28th International Conference on Neural Information Processing Systems, Vol. 2. 3025-3033."},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2745754.2745755"},{"key":"e_1_3_2_1_39_1","first-page":"2722","article-title":"Diferentially private empirical risk minimization revisited: Faster and more general","author":"Wang Di","year":"2017","unstructured":"Di Wang , Minwei Ye , and Jinhui Xu . 2017 . Diferentially private empirical risk minimization revisited: Faster and more general . In Advances in Neural Information Processing Systems. 2722 - 2731 . Di Wang, Minwei Ye, and Jinhui Xu. 2017. Diferentially private empirical risk minimization revisited: Faster and more general. In Advances in Neural Information Processing Systems. 2722-2731.","journal-title":"Advances in Neural Information Processing Systems."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"crossref","unstructured":"Xi Wu Fengan Li Arun Kumar Kamalika Chaudhuri Somesh Jha and Jefrey Naughton. 2017. Bolt-on diferential privacy for scalable stochastic gradient descent-based analytics. In SIGMOD. ACM.  Xi Wu Fengan Li Arun Kumar Kamalika Chaudhuri Somesh Jha and Jefrey Naughton. 2017. Bolt-on diferential privacy for scalable stochastic gradient descent-based analytics. In SIGMOD. ACM.","DOI":"10.1145\/3035918.3064047"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384335","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384335","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T18:32:57Z","timestamp":1750185177000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384335"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":40,"alternative-id":["10.1145\/3357713.3384335","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384335","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}