{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,12]],"date-time":"2026-05-12T05:55:09Z","timestamp":1778565309804,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,6,4]],"date-time":"2022-06-04T00:00:00Z","timestamp":1654300800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,4]],"date-time":"2022-06-04T00:00:00Z","timestamp":1654300800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["P 29809-N32"],"award-info":[{"award-number":["P 29809-N32"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002428","name":"Austrian Science Fund","doi-asserted-by":"publisher","award":["W 1260"],"award-info":[{"award-number":["W 1260"]}],"id":[{"id":"10.13039\/501100002428","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Austrian Science Fund"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2023,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this work we aim to solve a convex-concave saddle point problem, where the convex-concave coupling function is smooth in one variable and nonsmooth in the other and <jats:italic>not<\/jats:italic> assumed to be linear in either. The problem is augmented by a nonsmooth regulariser in the smooth component. We propose and investigate a novel algorithm under the name of <jats:italic>OGAProx<\/jats:italic>, consisting of an <jats:italic>optimistic gradient ascent<\/jats:italic> step in the smooth variable coupled with a proximal step of the regulariser, and which is alternated with a <jats:italic>proximal step<\/jats:italic> in the nonsmooth component of the coupling function. We consider the situations convex-concave, convex-strongly concave and strongly convex-strongly concave related to the saddle point problem under investigation. Regarding iterates we obtain (weak) convergence, a convergence rate of order <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\frac{1}{K})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mi>K<\/mml:mi>\n                    <\/mml:mfrac>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and linear convergence like <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\theta ^{K})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>\u03b8<\/mml:mi>\n                      <mml:mi>K<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\theta &lt; 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b8<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively. In terms of function values we obtain ergodic convergence rates of order <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\frac{1}{K})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mi>K<\/mml:mi>\n                    <\/mml:mfrac>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\frac{1}{K^{2}})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mfrac>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:msup>\n                        <mml:mi>K<\/mml:mi>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:msup>\n                    <\/mml:mfrac>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\theta ^{K})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>\u03b8<\/mml:mi>\n                      <mml:mi>K<\/mml:mi>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\theta &lt; 1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b8<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, respectively. We validate our theoretical considerations on a nonsmooth-linear saddle point problem, the training of multi kernel support vector machines and a classification problem incorporating minimax group fairness.<\/jats:p>","DOI":"10.1007\/s10589-022-00378-8","type":"journal-article","created":{"date-parts":[[2022,6,4]],"date-time":"2022-06-04T10:02:31Z","timestamp":1654336951000},"page":"925-966","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["An accelerated minimax algorithm for convex-concave saddle point problems with nonsmooth coupling function"],"prefix":"10.1007","volume":"86","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4469-314X","authenticated-orcid":false,"given":"Radu Ioan","family":"Bo\u0163","sequence":"first","affiliation":[]},{"given":"Ern\u00f6 Robert","family":"Csetnek","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Sedlmayer","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,6,4]]},"reference":[{"key":"378_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4419-9467-7","volume-title":"Convex analysis and monotone operator theory in Hilbert spaces","author":"HH Bauschke","year":"2011","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in Hilbert spaces. Springer, New York (2011)"},{"key":"378_CR2","unstructured":"Bo\u0163, R.I., B\u00f6hm, A.: Alternating proximal-gradient steps for (stochastic) nonconvex-concave minimax problems (2020). arXiv:2007.13605"},{"key":"378_CR3","unstructured":"B\u00f6hm, A., Sedlmayer, M., Csetnek, E.R., Bo\u0163, R.I.: Two steps at a time\u2013taking GAN training in stride with Tseng\u2019s method (2020). arXiv:2006.09033"},{"key":"378_CR4","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/s10851-010-0251-1","volume":"40","author":"A Chambolle","year":"2011","unstructured":"Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40, 120\u2013145 (2011)","journal-title":"J. Math. Imaging Vis."},{"key":"378_CR5","unstructured":"Daskalakis, C., Ilyas, A., Syrgkanis, V., Zeng, H.: Training GANs with optimism. In: International conference on learning representations (2018). https:\/\/openreview.net\/forum?id=SJJySbbAZ"},{"key":"378_CR6","first-page":"9236","volume":"31","author":"C Daskalakis","year":"2018","unstructured":"Daskalakis, C., Panageas, I.: The limit points of (optimistic) gradient descent in min-max optimization. Adv. Neural Inf. Process. Syst. 31, 9236\u20139246 (2018)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"378_CR7","doi-asserted-by":"crossref","unstructured":"Diana, E., Gill, W., Kearns, M., Kenthapadi, K., Roth, A.: Minimax group fairness: algorithms and experiments (2020). arXiv:2011.03108","DOI":"10.1145\/3461702.3462523"},{"key":"378_CR8","unstructured":"Dua, D., Graff, C.: UCI machine learning repository. School of Information and Computer Science, University of California (2019). http:\/\/archive.ics.uci.edu\/ml"},{"key":"378_CR9","unstructured":"Gidel, G., Berard, H., Vignoud, G., Vincent, P., Lacoste-Julien, S.: A variational inequality perspective on generative adversarial networks. In: International conference on learning representations (2019). https:\/\/openreview.net\/forum?id=r1laEnA5Ym"},{"key":"378_CR10","first-page":"2672","volume":"27","author":"I Goodfellow","year":"2014","unstructured":"Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversarial nets. Adv. Neural Inf. Process. Syst. 27, 2672\u20132680 (2014)","journal-title":"Adv. Neural Inf. Process. Syst."},{"issue":"2","key":"378_CR11","doi-asserted-by":"publisher","first-page":"1299","DOI":"10.1137\/18M1213488","volume":"31","author":"EY Hamedani","year":"2021","unstructured":"Hamedani, E.Y., Aybat, N.S.: A primal-dual algorithm with line search for general convex-concave saddle point problems. SIAM J. Optim. 31(2), 1299\u20131329 (2021)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"378_CR12","first-page":"747","volume":"12","author":"GM Korpelevich","year":"1976","unstructured":"Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Ekonomika i Matematicheskie Metody 12(4), 747\u2013756 (1976)","journal-title":"Ekonomika i Matematicheskie Metody"},{"key":"378_CR13","first-page":"27","volume":"5","author":"GR Lanckriet","year":"2004","unstructured":"Lanckriet, G.R., Cristianini, N., Bartlett, P., Ghaoui, L.E., Jordan, M.I.: Learning the kernel matrix with semidefinite programming. J. Mach. Learn. Res. 5, 27\u201372 (2004)","journal-title":"J. Mach. Learn. Res."},{"key":"378_CR14","unstructured":"Liang, T., Stokes, J.: Interaction matters: a note on non-asymptotic local convergence of generative adversarial networks. In: Chaudhuri, K., Sugiyama, M. (eds.) The 22nd international conference on artificial intelligence and statistics, proceedings of machine learning research, vol. 89, pp. 907\u2013915 (2019)"},{"issue":"2","key":"378_CR15","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1137\/18M1207260","volume":"30","author":"Y Malitsky","year":"2020","unstructured":"Malitsky, Y., Tam, M.K.: A forward-backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30(2), 1451\u20131472 (2020)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"378_CR16","first-page":"1","volume":"23","author":"OL Mangasarian","year":"1990","unstructured":"Mangasarian, O.L., Wolberg, W.H.: Cancer diagnosis via linear programming. SIAM News 23(5), 1\u201318 (1990)","journal-title":"SIAM News"},{"key":"378_CR17","unstructured":"Martinez, N., Bertran, M., Sapiro, G.: Minimax pareto fairness: a multi objective perspective. In: International conference on machine learning, pp. 6755\u20136764 (2020)"},{"key":"378_CR18","unstructured":"MOSEK ApS: The MOSEK optimization toolbox for MATLAB manual. Version 9.0 (2019). http:\/\/docs.mosek.com\/9.0\/toolbox\/index.html"},{"issue":"1","key":"378_CR19","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/S1052623403425629","volume":"15","author":"A Nemirovski","year":"2004","unstructured":"Nemirovski, A.: Prox-method with rate of convergence $$O(1\/t)$$ for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1), 229\u2013251 (2004)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"378_CR20","doi-asserted-by":"publisher","first-page":"591","DOI":"10.1090\/S0002-9904-1967-11761-0","volume":"73","author":"Z Opial","year":"1967","unstructured":"Opial, Z.: Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Am. Math. Soc. 73(4), 591\u2013597 (1967)","journal-title":"Bull. Am. Math. Soc."},{"key":"378_CR21","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T.: Monotone operators associated with saddle-functions and minimax problems. In: Browder, F.E. (ed.) Nonlinear functional analysis, proceedings of symposia in pure mathematics, vol. 18, pp. 241\u2013250 (1970)","DOI":"10.1090\/pspum\/018.1\/0285942"},{"issue":"1","key":"378_CR22","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1137\/0329006","volume":"29","author":"P Tseng","year":"1991","unstructured":"Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control Optim. 29(1), 119\u2013138 (1991)","journal-title":"SIAM J. Control Optim."},{"key":"378_CR23","volume-title":"Theory of games and economic behavior","author":"J Von Neumann","year":"1944","unstructured":"Von Neumann, J., Morgenstern, O.: Theory of games and economic behavior. Princeton University Press, Princeton (1944)"},{"key":"378_CR24","unstructured":"Zhang, G., Wang, Y., Lessard, L., Grosse, R.: Near-optimal local convergence of alternating gradient descent-ascent for minimax optimization (2021). arXiv:2102.09468"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00378-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-022-00378-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-022-00378-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,13]],"date-time":"2023-11-13T12:11:49Z","timestamp":1699877509000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-022-00378-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,4]]},"references-count":24,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2023,12]]}},"alternative-id":["378"],"URL":"https:\/\/doi.org\/10.1007\/s10589-022-00378-8","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,6,4]]},"assertion":[{"value":"29 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 May 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 August 2022","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}