{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:23:45Z","timestamp":1787340225251,"version":"build-2736575974"},"reference-count":47,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","funder":[{"name":"Research Intern at Google"},{"DOI":"10.13039\/100012950","name":"Institut national de recherche en informatique et en automatique","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100012950","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002850","name":"Fondo Nacional de Desarrollo Cient\u00edfico y Tecnol\u00f3gico","doi-asserted-by":"publisher","award":["1210362"],"award-info":[{"award-number":["1210362"]}],"id":[{"id":"10.13039\/501100002850","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Agencia Nacional de Investigacion y Desarrollo","award":["ACT210005"],"award-info":[{"award-number":["ACT210005"]}]},{"name":"National Center for Artificial Intelligence","award":["FB210017"],"award-info":[{"award-number":["FB210017"]}]},{"DOI":"10.13039\/501100003151","name":"Fonds de Recherche du Qu\u00e9bec - Nature et Technologies","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100003151","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>Abstract.<\/jats:p>\n                  <jats:p>We study the problem of differentially-private (DP) stochastic (convex-concave) saddle-points in the [Formula: see text] setting. We propose [Formula: see text]-DP algorithms based on stochastic mirror descent that attain nearly dimension-independent convergence rates for the expected duality gap, a type of guarantee that was known before only for bilinear objectives.\u00a0For convex-concave and first-order-smooth stochastic objectives, our algorithms attain a rate of [Formula: see text], where [Formula: see text] is the dimension of the problem and [Formula: see text] the dataset size. Under an additional second-order-smoothness assumption, we show that the duality gap is bounded by [Formula: see text] with high probability, by using bias-reduced gradient estimators. This rate provides evidence of the near-optimality of our approach, since a lower bound of [Formula: see text] exists. Finally, we show that combining our methods with acceleration techniques from online learning leads to the first algorithm for DP stochastic convex optimization in the [Formula: see text] setting that is not based on Frank\u2013Wolfe methods. For convex and first-order-smooth stochastic objectives, our algorithms attain an excess risk of [Formula: see text], and when additionally assuming second-order-smoothness, we improve the rate to [Formula: see text]. Instrumental to all of these results are various extensions of the classical Maurey sparsification lemma [ 34 ], which may be of independent interest.<\/jats:p>","DOI":"10.1137\/24m1697268","type":"journal-article","created":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T08:42:07Z","timestamp":1771576927000},"page":"233-262","source":"Crossref","is-referenced-by-count":0,"title":["Mirror Descent Algorithms with Nearly Dimension-Independent Rates for Differentially-Private Stochastic Saddle-Point Problems"],"prefix":"10.1137","volume":"36","author":[{"given":"Tom\u00e1s","family":"Gonz\u00e1lez","sequence":"first","affiliation":[{"name":"Machine Learning Department, Carnegie Mellon University, Pittsburgh, PA 15213 USA."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1498-2055","authenticated-orcid":true,"given":"Crist\u00f3bal","family":"Guzm\u00e1n","sequence":"additional","affiliation":[{"name":"Institute for Mathematical and Computational Engineering, Faculty of Mathematics and School of Engineering, Pontificia Universidad Cat\u00f3lica de Chile and Google Research, Regi\u00f3n Metropolitana, Chile."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-5470-6249","authenticated-orcid":true,"given":"Courtney","family":"Paquette","sequence":"additional","affiliation":[{"name":"Department of Mathematics and Statistics, McGill University and Google DeepMind, Quebec H3A 0G4, Canada."}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2026,2,20]]},"reference":[{"key":"ref1","unstructured":"J. Acharya, C. De Sa, D. Foster, and K. Sridharan, Distributed learning with sublinear communication, in International Conference on Machine Learning, PMLR, 2019, pp. 40\u201350."},{"key":"ref2","volume-title":"Advances in Neural Information Processing Systems","author":"Asi H.","year":"2021"},{"key":"ref3","unstructured":"H. Asi, V. Feldman, T. Koren, and K. Talwar, Private stochastic convex optimization: Optimal rates in l1 geometry, in International Conference on Machine Learning, PMLR, 2021, pp. 393\u2013403."},{"key":"ref4","doi-asserted-by":"publisher","DOI":"10.1109\/18.256500"},{"key":"ref5","volume-title":"Advances in Neural Information Processing Systems","author":"Bassily R.","year":"2019"},{"key":"ref6","volume-title":"Advances in Neural Information Processing Systems","author":"Bassily R.","year":"2021"},{"key":"ref7","unstructured":"R. Bassily, C. Guzm\u00e1n, and M. Menart, Differentially private algorithms for the stochastic saddle point problem with optimal rates for the strong gap, in Proceedings of Thirty Sixth Annual Conference on Learning Theory, PMLR, 2023, pp. 2482\u20132508."},{"key":"ref8","unstructured":"R. Bassily, C. Guzman, and A. Nandi, Non-euclidean differentially private stochastic convex optimization, in Proceedings of Thirty Fourth Conference on Learning Theory, PMLR, 2021, pp. 474\u2013499."},{"key":"ref9","doi-asserted-by":"crossref","unstructured":"R. Bassily, C. A. Guzm\u00e1n, and M. Menart, Private algorithms for stochastic saddle points and variational inequalities: Beyond euclidean geometry, in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.","DOI":"10.52202\/079017-4085"},{"key":"ref10","first-page":"464","volume-title":"FOCS","author":"Bassily R.","year":"2014"},{"key":"ref11","doi-asserted-by":"crossref","unstructured":"J. H. Blanchet and P. W. Glynn, Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization, in Proceedings of the 2015 Winter Simulation Conference, IEEE\/ACM, 2015, pp. 3656\u20133667.","DOI":"10.1109\/WSC.2015.7408524"},{"key":"ref12","volume-title":"Advances in Neural Information Processing Systems","author":"Blondel M.","year":"2022"},{"key":"ref13","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-023-01953-5"},{"key":"ref14","doi-asserted-by":"crossref","unstructured":"M. Bun, J. Ullman, and S. Vadhan, Fingerprinting codes and the price of approximate differential privacy, in Proceedings of Symposium on Theory of Computing, ACM, 2014, pp. 1\u201310.","DOI":"10.1145\/2591796.2591877"},{"key":"ref15","doi-asserted-by":"crossref","unstructured":"C. Carath\u00e9odory, \u00dcber den variabilit\u00e4tsbereich der fourier\u2019schen konstanten von positiven harmonischen funktionen, Rendiconti del Circolo Matematico di Palermo (1884-1940), 32 (1911), pp. 193\u2013217.","DOI":"10.1007\/BF03014795"},{"key":"ref16","unstructured":"A. Cutkosky, Anytime online-to-batch, optimism and acceleration, in International Conference on Machine Learning, PMLR, 2019, pp. 1446\u20131454."},{"key":"ref17","doi-asserted-by":"publisher","DOI":"10.1137\/17M1116842"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1561\/0400000042"},{"key":"ref19","doi-asserted-by":"crossref","unstructured":"B. Ghazi, C. Guzm\u00e1n, P. Kamath, R. Kumar, and P. Manurangsi, Differentially private optimization with sparse gradients, in The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.","DOI":"10.52202\/079017-2025"},{"key":"ref20","unstructured":"G. Gidel, T. Jebara, and S. Lacoste-Julien, Frank\u2013Wolfe algorithms for saddle point problems, in Proceedings of International Conference on Artificial Intelligence and Statistics, PMLR, 2017, pp. 362\u2013371."},{"key":"ref21","unstructured":"Y. Han, Z. Liang, Z. Liang, Y. Wang, Y. Yao, and J. Zhang, Private streaming SCO in \\(\\ell_p\\) geometry with applications in high dimensional online decision making, in Proceedings of International Conference on Machine Learning, PMLR, 2022, pp. 8249\u20138279."},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.85"},{"key":"ref23","doi-asserted-by":"crossref","unstructured":"J. Hsu, A. Roth, and J. Ullman, Differential privacy for the analyst via private equilibrium computation, in Proceedings of Symposium on Theory of Computing, ACM, 2013, pp. 341\u2013350.","DOI":"10.1145\/2488608.2488651"},{"key":"ref24","unstructured":"M. Jagielski, M. Kearns, J. Mao, A. Oprea, A. Roth, S. Sharifi-Malvajerdi, and J. Ullman, Differentially private fair learning, in Proceedings of International Conference on Machine Learning, PMLR, 2019, pp. 3000\u20133008."},{"key":"ref25","unstructured":"P. Jain and A. G. Thakurta, (Near) dimension independent risk bounds for differentially private learning, in Proceedings of International Conference on Machine Learning, PMLR, 2014, pp. 476\u2013484."},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1287\/10-SSY011"},{"key":"ref27","unstructured":"Y. Kang, Y. Liu, J. Li, and W. Wang, Stability and Generalization of Differentially Private Minimax Problems, arXiv:2204.04858, 2022."},{"key":"ref28","unstructured":"T. Li, M. Sanjabi, A. Beirami, and V. Smith, Fair Resource Allocation in Federated Learning, arXiv:1905.10497, 2019."},{"key":"ref29","unstructured":"A. Lowy, D. Gupta, and M. Razaviyayn, Stochastic differentially private and fair learning, in The Eleventh International Conference on Learning Representations, 2023."},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1172-1"},{"key":"ref31","doi-asserted-by":"publisher","DOI":"10.1137\/070704277"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1017\/S096249291300007X"},{"key":"ref33","unstructured":"F. Orabona, A Modern Introduction to Online Learning, arXiv:1912.13213, 2019."},{"key":"ref34","unstructured":"G. Pisier, Remarques sur un r\u00e9sultat non publi\u00e9 de B. Maurey, S\u00e9minaire Analyse fonctionnelle (dit \u201cMaurey-Schwartz\u201d), (1980-1981), pp. 1\u201312."},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781316480588"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1090\/pspum\/018.1\/0285942"},{"key":"ref37","volume-title":"Advances in Neural Information Processing Systems","author":"Talwar K.","year":"2015"},{"key":"ref38","unstructured":"K. Talwar, A. Thakurta, and L. Zhang, Private Empirical Risk Minimization Beyond the Worst Case: The Effect of the Constraint Set Geometry, arXiv:1411.5417, 2014."},{"key":"ref39","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref40","doi-asserted-by":"crossref","unstructured":"B. Waggoner, Lp testing and learning of discrete distributions, in Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ACM, 2015, pp. 347\u2013356.","DOI":"10.1145\/2688073.2688095"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177731235"},{"key":"ref42","unstructured":"J. Whitehouse, A. Ramdas, R. Rogers, and S. Wu, Fully-adaptive composition in differential privacy, in Proceedings of International Conference on Machine Learning, PMLR, 2023, pp. 36990\u201337007."},{"key":"ref43","unstructured":"Z. Yang, S. Hu, Y. Lei, K. R. Vashney, S. Lyu, and Y. Ying, Differentially private sgda for minimax problems, in Proceedings of the Thirty-Eighth Conference on Uncertainty in Artificial Intelligence, PMLR, 2022, pp. 2192\u20132202."},{"key":"ref44","volume-title":"Advances in Neural Information Processing Systems","author":"Zhang L.","year":"2022"},{"key":"ref45","volume-title":"Advances in Neural Information Processing Systems","author":"Zhang Q.","year":"2022"},{"key":"ref46","first-page":"527","author":"Zhang T.","year":"2002","journal-title":"J. Mach. Learn. Res."},{"key":"ref47","unstructured":"X. Zhou and R. Bassily, Differentially private worst-group risk minimization, in Proceedings of International Conference on Machine Learning, PMLR, 2024, pp. 61783\u201361803."}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/24M1697268","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:25:44Z","timestamp":1787336744000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/24M1697268"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,2,20]]},"references-count":47,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1137\/24M1697268"],"URL":"https:\/\/doi.org\/10.1137\/24m1697268","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,2,20]]}}}