{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,13]],"date-time":"2026-10-13T17:12:21Z","timestamp":1791911541618,"version":"4.3.4"},"reference-count":125,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T00:00:00Z","timestamp":1687392000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,6,22]],"date-time":"2023-06-22T00:00:00Z","timestamp":1687392000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1910077"],"award-info":[{"award-number":["1910077"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["grant No. 447\/20"],"award-info":[{"award-number":["grant No. 447\/20"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s10107-023-01976-y","type":"journal-article","created":{"date-parts":[[2023,6,23]],"date-time":"2023-06-23T02:10:05Z","timestamp":1687486205000},"page":"203-268","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization"],"prefix":"10.1007","volume":"205","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-6725-9231","authenticated-orcid":false,"given":"Jun-Kun","family":"Wang","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jacob","family":"Abernethy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Kfir Y.","family":"Levy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,6,22]]},"reference":[{"key":"1976_CR1","first-page":"372","volume":"27","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method of solving a convex programming problem with convergence rate O$$(1\/k^2)$$. Sov. Math. Doklady 27, 372\u2013376 (1983)","journal-title":"Sov. Math. Doklady"},{"key":"1976_CR2","first-page":"543","volume":"269","author":"Y Nesterov","year":"1983","unstructured":"Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence O$$(1\/k^2)$$. Doklady an ussr 269, 543\u2013547 (1983)","journal-title":"Doklady an ussr"},{"key":"1976_CR3","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127\u2013152 (2005)","journal-title":"Math. Program."},{"key":"1976_CR4","first-page":"509","volume":"24","author":"Y Nesterov","year":"1988","unstructured":"Nesterov, Y.: On an approach to the construction of optimal methods of minimization of smooth convex functions. Ekonom. i. Mat. Metody 24, 509\u2013517 (1988)","journal-title":"Ekonom. i. Mat. Metody"},{"key":"1976_CR5","volume-title":"Introductory Lectures on Convex Optimization: A basic course","author":"Y Nesterov","year":"2003","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A basic course, vol. 87. Springer, Berlin (2003)"},{"issue":"1\u20132","key":"1976_CR6","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1002\/nav.3800030109","volume":"3","author":"M Frank","year":"1956","unstructured":"Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1\u20132), 95\u2013110 (1956)","journal-title":"Nav. Res. Logist. Q."},{"issue":"1","key":"1976_CR7","doi-asserted-by":"crossref","first-page":"183","DOI":"10.1137\/080716542","volume":"2","author":"A Beck","year":"2009","unstructured":"Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183\u2013202 (2009)","journal-title":"SIAM J. Imaging Sci."},{"key":"1976_CR8","first-page":"6584","volume":"30","author":"JD Abernethy","year":"2017","unstructured":"Abernethy, J.D., Wang, J.-K.: On Frank\u2013Wolfe and equilibrium computation. Adv. Neural. Inf. Process. Syst. 30, 6584\u20136593 (2017)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR9","unstructured":"Abernethy, J., Lai, K.A., Levy, K.Y., Wang, J.-K.: Faster rates for convex-concave games. In: Conference on Learning Theory, pp. 1595\u20131625 (2018)"},{"key":"1976_CR10","first-page":"3828","volume":"31","author":"J-K Wang","year":"2018","unstructured":"Wang, J.-K., Abernethy, J.D.: Acceleration through optimistic no-regret dynamics. Adv. Neural. Inf. Process. Syst. 31, 3828\u20133838 (2018)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR11","volume-title":"Convex Analysis and Optimization","author":"D Bertsekas","year":"2003","unstructured":"Bertsekas, D., Nedic, A., Ozdaglar, A.: Convex Analysis and Optimization, vol. 1. Athena Scientific, Nashua (2003)"},{"key":"1976_CR12","doi-asserted-by":"crossref","DOI":"10.1137\/1.9780898718829","volume-title":"Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. SIAM, Cham (2001)"},{"key":"1976_CR13","volume-title":"Convex Analysis and Minimization Algorithms I: Fundamentals","author":"J-B Hiriart-Urruty","year":"2013","unstructured":"Hiriart-Urruty, J.-B., Lemar\u00e9chal, C.: Convex Analysis and Minimization Algorithms I: Fundamentals, vol. 305. Springer, Berlin (2013)"},{"key":"1976_CR14","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1997","unstructured":"Rockafellar, R.T.: Convex Analysis, vol. 11. Princeton University Press, Princeton (1997)"},{"key":"1976_CR15","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"SP Boyd","year":"2004","unstructured":"Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"1976_CR16","volume-title":"Convex Analysis and Nonlinear Optimization Theory and Examples","author":"J Borwein","year":"2006","unstructured":"Borwein, J., Lewis, A.S.: Convex Analysis and Nonlinear Optimization Theory and Examples. Springer, Berlin (2006)"},{"issue":"5","key":"1976_CR17","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0041-5553(66)90114-5","volume":"6","author":"ES Levitin","year":"1966","unstructured":"Levitin, E.S., Polyak, B.T.: Constrained minimization methods. USSR Comput. Math. Math. Phys. 6(5), 1\u201350 (1966)","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"1976_CR18","unstructured":"N\u00e9giar, G., et al.: Stochastic Frank\u2013Wolfe for constrained finite-sum minimization. In: International Conference on Machine Learning, pp. 7253\u20137262 (2020)"},{"issue":"1","key":"1976_CR19","first-page":"44","volume":"59","author":"H Bauschke","year":"2012","unstructured":"Bauschke, H., Lucet, Y.: What is a Fenchel conjugate. Notices AMS 59(1), 44\u201346 (2012)","journal-title":"Notices AMS"},{"key":"1976_CR20","unstructured":"Kakade, S., Shalev-Shwartz, S., Tewari, A.: On the duality of strong convexity and strong smoothness: learning applications and matrix regularization. Unpublished Manuscript (2009)"},{"key":"1976_CR21","unstructured":"Garber, D., Hazan, E.: Faster rates for the Frank\u2013Wolfe method over strongly-convex sets. In: International Conference on Machine Learning, pp. 541\u2013549 (2015)"},{"key":"1976_CR22","doi-asserted-by":"crossref","unstructured":"Freund, Y., Schapire, R.E.: Game theory, on-line prediction and boosting. In: Conference on Learning Theory, pp. 325\u2013332 (1996)","DOI":"10.1145\/238061.238163"},{"issue":"1","key":"1976_CR23","doi-asserted-by":"crossref","first-page":"1","DOI":"10.2140\/pjm.1956.6.1","volume":"6","author":"D Blackwell","year":"1956","unstructured":"Blackwell, D.: An analog of the minimax theorem for vector payoffs. Pac. J. Math. 6(1), 1\u20138 (1956)","journal-title":"Pac. J. Math."},{"key":"1976_CR24","first-page":"97","volume":"39","author":"J Hannan","year":"1957","unstructured":"Hannan, J.: Approximation to Bayes risk in repeated play. Contrib. Theory Games 39, 97 (1957)","journal-title":"Contrib. Theory Games"},{"key":"1976_CR25","first-page":"3066","volume":"26","author":"S Rakhlin","year":"2013","unstructured":"Rakhlin, S., Sridharan, K.: Optimization, learning, and games with predictable sequences. Adv. Neural. Inf. Process. Syst. 26, 3066\u20133074 (2013)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR26","first-page":"6.1","volume":"23","author":"C-K Chiang","year":"2012","unstructured":"Chiang, C.-K., et al.: Online optimization with gradual variations. Conf. Learn. Theory 23, 6.1-6.20 (2012)","journal-title":"Conf. Learn. Theory"},{"issue":"1","key":"1976_CR27","doi-asserted-by":"crossref","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":"2\u20133","key":"1976_CR28","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s10107-006-0034-z","volume":"109","author":"Y Nesterov","year":"2007","unstructured":"Nesterov, Y.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109(2\u20133), 319\u2013344 (2007)","journal-title":"Math. Program."},{"key":"1976_CR29","unstructured":"Syrgkanis, V., Agarwal, A., Luo, H., Schapire, R.E.: Fast convergence of regularized learning in games. Adv. Neural Inf. Process. Syst. 28 (2015)"},{"key":"1976_CR30","doi-asserted-by":"crossref","first-page":"205","DOI":"10.1007\/s10957-009-9522-7","volume":"142","author":"A Nedi\u0107","year":"2009","unstructured":"Nedi\u0107, A., Ozdaglar, A.: Subgradient methods for saddle-point problems. J. Optim. Theory Appl. 142, 205\u2013228 (2009)","journal-title":"J. Optim. Theory Appl."},{"key":"1976_CR31","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/s10107-004-0568-x","volume":"104","author":"A Auslender","year":"2005","unstructured":"Auslender, A., Teboulle, M.: Interior projection-like methods for monotone variational inequalities. Math. Program. 104, 39\u201368 (2005)","journal-title":"Math. Program."},{"key":"1976_CR32","doi-asserted-by":"crossref","first-page":"293","DOI":"10.1007\/BF01581204","volume":"55","author":"J Eckstein","year":"1992","unstructured":"Eckstein, J., Bertsekas, D.P.: On the Douglas\u2013Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293\u2013318 (1992)","journal-title":"Math. Program."},{"issue":"4","key":"1976_CR33","doi-asserted-by":"crossref","first-page":"1779","DOI":"10.1137\/130919362","volume":"24","author":"Y Chen","year":"2014","unstructured":"Chen, Y., Lan, G., Ouyang, Y.: Optimal primal-dual methods for a class of saddle point problems. SIAM J. Optim. 24(4), 1779\u20131814 (2014)","journal-title":"SIAM J. Optim."},{"key":"1976_CR34","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s10107-017-1161-4","volume":"165","author":"Y Chen","year":"2017","unstructured":"Chen, Y., Lan, G., Ouyang, Y.: Accelerated schemes for a class of variational inequalities. Math. Program. 165, 113\u2013149 (2017)","journal-title":"Math. Program."},{"issue":"1","key":"1976_CR35","doi-asserted-by":"crossref","first-page":"29","DOI":"10.1137\/14096757X","volume":"26","author":"Y He","year":"2016","unstructured":"He, Y., Monteiro, R.D.: An accelerated HPE-type algorithm for a class of composite convex\u2013concave saddle-point problems. SIAM J. Optim. 26(1), 29\u201356 (2016)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1976_CR36","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1287\/10-SSY011","volume":"1","author":"A Juditsky","year":"2011","unstructured":"Juditsky, A., Nemirovski, A., Tauvel, C.: Solving variational inequalities with stochastic mirror-prox algorithm. Stoch. Syst. 1(1), 17\u201358 (2011)","journal-title":"Stoch. Syst."},{"issue":"2","key":"1976_CR37","doi-asserted-by":"crossref","first-page":"431","DOI":"10.1137\/S0363012998338806","volume":"38","author":"P Tseng","year":"2000","unstructured":"Tseng, P.: A modified forward\u2013backward splitting method for maximal monotone mappings. SIAM J. Control. Optim. 38(2), 431\u2013446 (2000)","journal-title":"SIAM J. Control. Optim."},{"key":"1976_CR38","doi-asserted-by":"crossref","first-page":"383","DOI":"10.1007\/s10107-019-01416-w","volume":"184","author":"Y Malitsky","year":"2020","unstructured":"Malitsky, Y.: Golden ratio algorithms for variational inequalities. Math. Program. 184, 383\u2013410 (2020)","journal-title":"Math. Program."},{"issue":"1","key":"1976_CR39","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1137\/17M1144799","volume":"29","author":"AN Iusem","year":"2017","unstructured":"Iusem, A.N., Jofr\u00e9, A., Oliveira, R.I., Thompson, P.: Extragradient method with variance reduction for stochastic variational inequalities. SIAM J. Optim. 29(1), 175\u2013206 (2017)","journal-title":"SIAM J. Optim."},{"key":"1976_CR40","first-page":"62:1","volume":"185","author":"MB Cohen","year":"2021","unstructured":"Cohen, M.B., Sidford, A., Tian, K.: Relative lipschitzness in extragradient methods and a direct recipe for acceleration. Innov. Theor. Comput. Sci. Conf. 185, 62:1-62:18 (2021)","journal-title":"Innov. Theor. Comput. Sci. Conf."},{"key":"1976_CR41","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s10107-019-01420-0","volume":"185","author":"Y Ouyang","year":"2021","unstructured":"Ouyang, Y., Xu, Y.: Lower complexity bounds of first-order methods for convex\u2013concave bilinear saddle-point problems. Math. Program. 185, 1\u201335 (2021)","journal-title":"Math. Program."},{"key":"1976_CR42","doi-asserted-by":"crossref","first-page":"901","DOI":"10.1007\/s10107-021-01660-z","volume":"194","author":"J Zhang","year":"2022","unstructured":"Zhang, J., Hong, M., Zhang, S.: On lower iteration complexity bounds for the convex concave saddle point problems. Math. Program. 194, 901\u2013935 (2022)","journal-title":"Math. Program."},{"issue":"1","key":"1976_CR43","doi-asserted-by":"crossref","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\u2013dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120\u2013145 (2011)","journal-title":"J. Math. Imaging Vis."},{"key":"1976_CR44","doi-asserted-by":"crossref","unstructured":"Pock, T., Cremers, D., Bischof, H., Chambolle, A.: An algorithm for minimizing the mumford-shah functional. In: International Conference on Computer Vision, pp. 1133\u20131140 (2009)","DOI":"10.1109\/ICCV.2009.5459348"},{"issue":"4","key":"1976_CR45","doi-asserted-by":"crossref","first-page":"1015","DOI":"10.1137\/09076934X","volume":"3","author":"E Esser","year":"2010","unstructured":"Esser, E., Zhang, X., Chan, T.F.: A general framework for a class of first order primal\u2013dual algorithms for convex optimization in imaging science. SIAM J. Imaging Sci. 3(4), 1015\u20131046 (2010)","journal-title":"SIAM J. Imaging Sci."},{"key":"1976_CR46","doi-asserted-by":"crossref","unstructured":"Chambolle, A., Pock, T.: On the ergodic convergence rates of a first-order primal\u2013dual algorithm. Math. Program. 159 (2016)","DOI":"10.1007\/s10107-015-0957-3"},{"key":"1976_CR47","unstructured":"Zhu, M., Chan, T.: An efficient primal-dual hybrid gradient algorithm for total variation image restoration. In: UCLA CAM Reports (2008)"},{"issue":"2","key":"1976_CR48","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/j.orl.2015.02.001","volume":"43","author":"Y Drori","year":"2015","unstructured":"Drori, Y., Sabach, S., Teboulle, M.: A simple algorithm for a class of nonsmooth convex\u2013concave saddle-point problems. Oper. Res. Lett. 43(2), 209\u2013214 (2015)","journal-title":"Oper. Res. Lett."},{"key":"1976_CR49","doi-asserted-by":"crossref","unstructured":"Combettes, P.L., Condat, L., Pesquet, J.-C., V\u0169, B.: A forward\u2013backward view of some primal\u2013dual optimization methods in image recovery. In: International Conference on Image Processing, pp. 4141\u20134145 (2014)","DOI":"10.1109\/ICIP.2014.7025841"},{"key":"1976_CR50","doi-asserted-by":"crossref","first-page":"443","DOI":"10.1007\/s10107-022-01779-7","volume":"198","author":"DH Gutman","year":"2022","unstructured":"Gutman, D.H., Pe\u00f1a, J.F.: Perturbed Fenchel duality and first-order methods. Math. Program. 198, 443\u2013469 (2022)","journal-title":"Math. Program."},{"issue":"1","key":"1976_CR51","doi-asserted-by":"crossref","first-page":"162","DOI":"10.1137\/18M1164329","volume":"29","author":"DH Gutman","year":"2019","unstructured":"Gutman, D.H., Pena, J.F.: Convergence rates of proximal gradient methods via the convex conjugate. SIAM J. Optim. 29(1), 162\u2013174 (2019)","journal-title":"SIAM J. Optim."},{"issue":"1\u20132","key":"1976_CR52","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/s10107-018-1262-8","volume":"177","author":"N Ho-Nguyen","year":"2019","unstructured":"Ho-Nguyen, N., K\u0131l\u0131n\u00e7-Karzan, F.: Exploiting problem structure in optimization under uncertainty via online convex optimization. Math. Program. 177(1\u20132), 113\u2013147 (2019)","journal-title":"Math. Program."},{"issue":"2","key":"1976_CR53","doi-asserted-by":"crossref","first-page":"284","DOI":"10.1109\/LCSYS.2018.2831721","volume":"2","author":"N Ho-Nguyen","year":"2018","unstructured":"Ho-Nguyen, N., K\u0131l\u0131n\u00e7-Karzan, F.: Primal\u2013dual algorithms for convex optimization via regret minimization. IEEE Control Syst. Lett. 2(2), 284\u2013289 (2018)","journal-title":"IEEE Control Syst. Lett."},{"issue":"19","key":"1976_CR54","doi-asserted-by":"crossref","first-page":"5149","DOI":"10.1109\/TSP.2015.2449255","volume":"63","author":"A Koppel","year":"2015","unstructured":"Koppel, A., Jakubiec, F.Y., Ribeiro, A.: A saddle point algorithm for networked online convex optimization. IEEE Trans. Signal Process. 63(19), 5149\u20135164 (2015)","journal-title":"IEEE Trans. Signal Process."},{"key":"1976_CR55","first-page":"2503","volume":"13","author":"M Mahdavi","year":"2012","unstructured":"Mahdavi, M., Jin, R., Yang, T.: Trading regret for efficiency: online convex optimization with long term constraints. J. Mach. Learn. Res. 13, 2503\u20132528 (2012)","journal-title":"J. Mach. Learn. Res."},{"key":"1976_CR56","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization\u20142020\/2021\/2022\/2023. Unpublished Manuscript"},{"key":"1976_CR57","unstructured":"Orabona, F.: A modern introduction to online learning. arXiv:1912.13213 (2019)"},{"key":"1976_CR58","unstructured":"Rakhlin, A., Sridharan, K.: Statistical learning theory and sequential prediction. Unpublished Manuscript (2016)"},{"key":"1976_CR59","volume-title":"Introduction to Online Convex Optimization","author":"E Hazan","year":"2022","unstructured":"Hazan, E.: Introduction to Online Convex Optimization, 2nd edn. MIT Press, Cambridge (2022)","edition":"2"},{"key":"1976_CR60","doi-asserted-by":"crossref","unstructured":"Shalev-Shwartz, S. et\u00a0al.: Online learning and online convex optimization. Found. Trends\u00ae Mach. Learn. 4(2), 107\u2013194 (2012)","DOI":"10.1561\/2200000018"},{"issue":"3","key":"1976_CR61","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1016\/j.jcss.2004.10.016","volume":"71","author":"A Kalai","year":"2005","unstructured":"Kalai, A., Vempala, S.: Efficient algorithms for online decision problems. J. Comput. Syst. Sci. 71(3), 291\u2013307 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"145","key":"1976_CR62","first-page":"1","volume":"18","author":"R Huang","year":"2017","unstructured":"Huang, R., Lattimore, T., Gy\u00f6rgy, A., Szepesvari, C.: Following the leader and fast rates in linear prediction: curved constraint sets and other regularities. J. Mach. Learn. Res. 18(145), 1\u201331 (2017)","journal-title":"J. Mach. Learn. Res."},{"issue":"88","key":"1976_CR63","first-page":"2543","volume":"11","author":"L Xiao","year":"2010","unstructured":"Xiao, L.: Dual averaging methods for regularized stochastic learning and online optimization. J. Mach. Learn. Res. 11(88), 2543\u20132596 (2010)","journal-title":"J. Mach. Learn. Res."},{"key":"1976_CR64","unstructured":"Shalev-Shwartz, S.: Online learning: theory, algorithms, and applications. In: The Hebrew University of Jerusalem. Ph.D. Thesis (2007)"},{"key":"1976_CR65","first-page":"1477","volume":"28","author":"T Koren","year":"2015","unstructured":"Koren, T., Levy, K.: Fast rates for exp-concave empirical risk minimization. Adv. Neural. Inf. Process. Syst. 28, 1477\u20131485 (2015)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR66","unstructured":"Tseng, P.: On accelerated proximal gradient methods for convex\u2013concave optimization. Unpublished Manuscript (2008)"},{"key":"1976_CR67","first-page":"993","volume":"30","author":"A Rakhlin","year":"2013","unstructured":"Rakhlin, A., Sridharan, K.: Online learning with predictable sequences. Conf. Learn. Theory 30, 993\u20131019 (2013)","journal-title":"Conf. Learn. Theory"},{"key":"1976_CR68","first-page":"1001","volume":"29","author":"D Garber","year":"2016","unstructured":"Garber, D., Meshi, O.: Linear-memory and decomposition-invariant linearly convergent conditional gradient algorithm for structured polytopes. Adv. Neural. Inf. Process. Syst. 29, 1001\u20131009 (2016)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR69","doi-asserted-by":"crossref","unstructured":"Combettes, C.\u00a0W., Pokutta, S.: Complexity of linear minimization and projection on some sets. arXiv:2101.10040 (2021)","DOI":"10.1016\/j.orl.2021.06.005"},{"key":"1976_CR70","volume-title":"Approximate Methods in Optimization Problems","author":"VF Demyanov","year":"1970","unstructured":"Demyanov, V.F., Rubinov, A.M.: Approximate Methods in Optimization Problems. Elsevier Publishing Company, Amsterdam (1970)"},{"issue":"2","key":"1976_CR71","doi-asserted-by":"crossref","first-page":"187","DOI":"10.1137\/0317015","volume":"17","author":"JC Dunn","year":"1979","unstructured":"Dunn, J.C.: Rates of convergence for conditional gradient algorithms near singular and nonsingular extremals. SIAM J. Control. Optim. 17(2), 187\u2013211 (1979)","journal-title":"SIAM J. Control. Optim."},{"key":"1976_CR72","doi-asserted-by":"crossref","first-page":"317","DOI":"10.1007\/s10107-020-01480-7","volume":"187","author":"H Lu","year":"2020","unstructured":"Lu, H., Freund, R.M.: Generalized stochastic Frank\u2013Wolfe algorithm with stochastic substitute gradient for structured convex optimization. Math. Program. 187, 317\u2013349 (2020)","journal-title":"Math. Program."},{"key":"1976_CR73","unstructured":"Jaggi, M.: Revisiting Frank\u2013Wolfe: projection-free sparse convex optimization. In: International Conference on Machine Learning, pp. 427\u2013435 (2013)"},{"key":"1976_CR74","unstructured":"Clarkson, K.: Coresets, sparse greedy approximation, and the Frank\u2013Wolfe algorithm. In: Symposium on Discrete Algorithms, SODA, pp. 922\u2013931 (2008)"},{"issue":"3","key":"1976_CR75","doi-asserted-by":"crossref","first-page":"1493","DOI":"10.1137\/140985366","volume":"26","author":"D Garber","year":"2016","unstructured":"Garber, D., Hazan, E.: A linearly convergent conditional gradient algorithm with applications to online and stochastic optimization. SIAM J. Optim. 26(3), 1493\u20131528 (2016)","journal-title":"SIAM J. Optim."},{"key":"1976_CR76","first-page":"496","volume":"28","author":"S Lacoste-Julien","year":"2015","unstructured":"Lacoste-Julien, S., Jaggi, M.: On the global linear convergence of Frank\u2013Wolfe optimization variants. Adv. Neural. Inf. Process. Syst. 28, 496\u2013504 (2015)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR77","doi-asserted-by":"crossref","first-page":"199","DOI":"10.1007\/s10107-014-0841-6","volume":"155","author":"RM Freund","year":"2016","unstructured":"Freund, R.M., Grigas, P.: New analysis and results for the Frank\u2013Wolfe method. Math. Program. 155, 199\u2013230 (2016)","journal-title":"Math. Program."},{"key":"1976_CR78","unstructured":"Braun, G., Pokutta, S., Tu, D., Wright, S.: Blended conditonal gradients. In: ICML (2019)"},{"key":"1976_CR79","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s10107-014-0778-9","volume":"152","author":"Z Harchaoui","year":"2015","unstructured":"Harchaoui, Z., Juditsky, A., Nemirovski, A.: Conditional gradient algorithms for norm-regularized smooth convex optimization. Math. Prog. Ser. A 152, 75\u2013112 (2015)","journal-title":"Math. Prog. Ser. A"},{"key":"1976_CR80","doi-asserted-by":"crossref","unstructured":"Lan, G., Zhou, Y.: Conditional gradient sliding for convex optimization. SIAM J. Optim. (2016)","DOI":"10.1137\/140992382"},{"issue":"3\u20134","key":"1976_CR81","doi-asserted-by":"crossref","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"S Bubeck","year":"2015","unstructured":"Bubeck, S.: Convex optimization: algorithms and complexity. Found. Trends Mach. Learn. 8(3\u20134), 231\u2013357 (2015)","journal-title":"Found. Trends Mach. Learn."},{"issue":"9","key":"1976_CR82","doi-asserted-by":"crossref","first-page":"2050","DOI":"10.1109\/TIT.2004.833339","volume":"50","author":"N Cesa-Bianchi","year":"2004","unstructured":"Cesa-Bianchi, N., Conconi, A., Gentile, C.: On the generalization ability of on-line learning algorithms. IEEE Trans. Inf. Theory 50(9), 2050\u20132057 (2004)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1976_CR83","first-page":"1613","volume":"30","author":"K Levy","year":"2017","unstructured":"Levy, K.: Online to offline conversions, universality and adaptive minibatch sizes. Adv. Neural. Inf. Process. Syst. 30, 1613\u20131622 (2017)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR84","unstructured":"Korpelevich, G.M.: The extragradient method for finding saddle points and other problems. Matecon (1976)"},{"issue":"4","key":"1976_CR85","doi-asserted-by":"crossref","first-page":"3230","DOI":"10.1137\/19M127375X","volume":"30","author":"A Mokhtari","year":"2020","unstructured":"Mokhtari, A., Ozdaglar, A.E., Pattathil, S.: Convergence rate of O(1\/k) for optimistic gradient and extragradient methods in smooth convex\u2013concave saddle point problems. SIAM J. Optim. 30(4), 3230\u20133251 (2020)","journal-title":"SIAM J. Optim."},{"key":"1976_CR86","unstructured":"Mertikopoulos, P. et\u00a0al.: Optimistic mirror descent in saddle-point problems: going the extra (gradient) mile. In: International Conference on Learning Representations (ICLR) (2018)"},{"key":"1976_CR87","first-page":"6936","volume":"32","author":"Y-G Hsieh","year":"2019","unstructured":"Hsieh, Y.-G., Iutzeler, F., Malick, J., Mertikopoulos, P.: On the convergence of single-call stochastic extra-gradient methods. Adv. Neural. Inf. Process. Syst. 32, 6936\u20136946 (2019)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR88","first-page":"845","volume":"28","author":"LD Popov","year":"1980","unstructured":"Popov, L.D.: A modification of the Arrow\u2013Hurwicz method for search of saddle points. Math. Notes Acad. Sci. USSR 28, 845\u2013848 (1980)","journal-title":"Math. Notes Acad. Sci. USSR"},{"key":"1976_CR89","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 (ICLR) (2019)"},{"key":"1976_CR90","unstructured":"Daskalakis, C., Ilyas, A., Syrgkanis, V., Zeng, H.: Training GANs with optimism. In: International Conference on Learning Representations (ICLR) (2018)"},{"issue":"5","key":"1976_CR91","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1080\/10556788.2020.1754414","volume":"35","author":"W Peng","year":"2020","unstructured":"Peng, W., Dai, Y.-H., Zhang, H., Cheng, L.: Training GANs with centripetal acceleration. Optim. Methods Softw. 35(5), 955\u2013973 (2020)","journal-title":"Optim. Methods Softw."},{"key":"1976_CR92","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-82118-9","volume-title":"Minimization Methods for Non-Differentiable Functions Vol.\u00a03 of Springer Series in Computational Mathematics","author":"NZ Shor","year":"1985","unstructured":"Shor, N.Z.: Minimization Methods for Non-Differentiable Functions Vol.\u00a03 of Springer Series in Computational Mathematics. Springer, Berlin (1985)"},{"key":"1976_CR93","unstructured":"Boyd, S.: Subgradient methods. In: Notes for EE364b (2014)"},{"key":"1976_CR94","unstructured":"Cutkosky, A.: Anytime online-to-batch, optimism and acceleration. In: International Conference on Machine Learning, pp. 1446\u20131454 (2019)"},{"key":"1976_CR95","first-page":"2510","volume":"27","author":"W Su","year":"2014","unstructured":"Su, W., Boyd, S., Candes, E.: A differential equation for modeling Nesterov\u2019s accelerated gradient method: theory and insights. Adv. Neural. Inf. Process. Syst. 27, 2510\u20132518 (2014)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"issue":"5","key":"1976_CR96","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/0041-5553(64)90137-5","volume":"4","author":"B Polyak","year":"1964","unstructured":"Polyak, B.: Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4(5), 1\u201317 (1964)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"3","key":"1976_CR97","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1561\/2400000003","volume":"1","author":"N Parikh","year":"2014","unstructured":"Parikh, N., Boyd, S.: Proximal algorithms. Found. Trends Optim. 1(3), 127\u2013239 (2014)","journal-title":"Found. Trends Optim."},{"issue":"1","key":"1976_CR98","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1137\/15M1009597","volume":"26","author":"L Lessard","year":"2016","unstructured":"Lessard, L., Recht, B., Packard, A.: Analysis and design of optimization algorithms via integral quadratic constraints. SIAM J. Optim. 26(1), 57\u201395 (2016)","journal-title":"SIAM J. Optim."},{"key":"1976_CR99","unstructured":"Hu, B., Lessard, L.: Dissipativity theory for Nesterov\u2019s accelerated method. In: International Conference on Machine Learning, pp. 1549\u20131557 (2017)"},{"key":"1976_CR100","unstructured":"Bubeck, S., Lee, Y.T., Singh, M.: A geometric alternative to Nesterov\u2019s accelerated gradient descent. arXiv:1506.08187 (2015)"},{"issue":"1","key":"1976_CR101","doi-asserted-by":"crossref","first-page":"251","DOI":"10.1137\/16M1072528","volume":"28","author":"D Drusvyatskiy","year":"2018","unstructured":"Drusvyatskiy, D., Fazel, M., Roy, S.: An optimal first order method based on optimal quadratic averaging. SIAM J. Optim. 28(1), 251\u2013271 (2018)","journal-title":"SIAM J. Optim."},{"key":"1976_CR102","first-page":"658","volume":"40","author":"N Flammarion","year":"2015","unstructured":"Flammarion, N., Bach, F.: From averaging to acceleration, there is only a step-size. Conf. Learn. Theory 40, 658\u2013695 (2015)","journal-title":"Conf. Learn. Theory"},{"key":"1976_CR103","first-page":"3:1","volume":"67","author":"Z Allen-Zhu","year":"2017","unstructured":"Allen-Zhu, Z., Orecchia, L.: Linear coupling: an ultimate unification of gradient and mirror descent. Innov. Theor. Comput. Sci. Conf. 67, 3:1-3:22 (2017)","journal-title":"Innov. Theor. Comput. Sci. Conf."},{"key":"1976_CR104","unstructured":"Diakonikolas1, J., Orecchia, L.: Accelerated extra-gradient descent: a novel accelerated first-order method. Innov. Theor. Comput. Sci. Confe. 94, 23:1\u201323:19 (2018)"},{"issue":"1","key":"1976_CR105","doi-asserted-by":"crossref","first-page":"660","DOI":"10.1137\/18M1172314","volume":"29","author":"J Diakonikolas","year":"2019","unstructured":"Diakonikolas, J., Orecchia, L.: The approximate duality gap technique: a unified theory of first-order methods. SIAM J. Optim. 29(1), 660\u2013689 (2019)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"1976_CR106","doi-asserted-by":"crossref","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":"2\u20133","key":"1976_CR107","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1007\/s10107-006-0034-z","volume":"109","author":"Y Nesterov","year":"2007","unstructured":"Nesterov, Y.: Dual extrapolation and its applications to solving variational inequalities and related problems. Math. Program. 109(2\u20133), 319\u2013344 (2007)","journal-title":"Math. Program."},{"issue":"47","key":"1976_CR108","doi-asserted-by":"crossref","first-page":"E7351","DOI":"10.1073\/pnas.1614734113","volume":"113","author":"A Wibisono","year":"2016","unstructured":"Wibisono, A., Wilson, A.C., Jordan, M.I.: A variational perspective on accelerated methods in optimization. Proc. Natl. Acad. Sci. 113(47), E7351\u2013E7358 (2016)","journal-title":"Proc. Natl. Acad. Sci."},{"key":"1976_CR109","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/s10107-021-01681-8","volume":"195","author":"B Shi","year":"2022","unstructured":"Shi, B., Du, S.S., Jordan, M.I., Su, W.J.: Understanding the acceleration phenomenon via high-resolution differential equations. Math. Program. 195, 79\u2013148 (2022)","journal-title":"Math. Program."},{"key":"1976_CR110","first-page":"2845","volume":"28","author":"W Krichene","year":"2015","unstructured":"Krichene, W., Bayen, A., Bartlett, P.L.: Accelerated mirror descent in continuous and discrete time. Adv. Neural. Inf. Process. Syst. 28, 2845\u20132853 (2015)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1976_CR111","first-page":"1109","volume":"30","author":"D Scieur","year":"2017","unstructured":"Scieur, D., Roulet, V., Bach, F., d\u2019Aspremont, A.: Integration methods and optimization algorithms. Adv. Neural. Inf. Process. Syst. 30, 1109\u20131118 (2017)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"issue":"113","key":"1976_CR112","first-page":"1","volume":"22","author":"AC Wilson","year":"2021","unstructured":"Wilson, A.C., Recht, B., Jordan, M.I.: A Lyapunov analysis of accelerated methods in optimization. J. Mach. Learn. Res. 22(113), 1\u201334 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"1976_CR113","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/s10107-016-0992-8","volume":"168","author":"H Attouch","year":"2018","unstructured":"Attouch, H., Chbani, Z., Peypouquet, J., Redont, P.: Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Math. Program. 168, 123\u2013175 (2018)","journal-title":"Math. Program."},{"key":"1976_CR114","doi-asserted-by":"crossref","unstructured":"d\u2019Aspremont, A., Scieur, D., Taylor, A.: Acceleration methods. arXiv:2101.09545 (2021)","DOI":"10.1561\/9781680839296"},{"key":"1976_CR115","unstructured":"Wang, J.-K., Lin, C.-H., Wibisono, A., Hu, B.: Provable acceleration of Heavy Ball beyond quadratics for a class of Polyak\u2013Lojasiewicz functions when the non-convexity is averaged-out. In: International Conference on Machine Learning (ICML), pp. 22839\u201322864 (2022)"},{"issue":"1\u20132","key":"1976_CR116","first-page":"167","volume":"171","author":"G Lan","year":"2017","unstructured":"Lan, G., Zhou, Y.: An optimal randomized incremental gradient method. Math. Program. 171(1\u20132), 167\u2013215 (2017)","journal-title":"Math. Program."},{"key":"1976_CR117","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-39568-1","volume-title":"First-order and Stochastic Optimization Methods for Machine Learning","author":"G Lan","year":"2020","unstructured":"Lan, G.: First-order and Stochastic Optimization Methods for Machine Learning. Springer, Berlin (2020)"},{"issue":"2","key":"1976_CR118","doi-asserted-by":"crossref","first-page":"557","DOI":"10.1137\/100818327","volume":"22","author":"A Beck","year":"2012","unstructured":"Beck, A., Teboulle, M.: Smoothing and first order methods: a unified framework. SIAM J. Optim. 22(2), 557\u2013580 (2012)","journal-title":"SIAM J. Optim."},{"key":"1976_CR119","doi-asserted-by":"crossref","unstructured":"Lu, H., Freund, R.M., Nesterov, Y.: Relatively-smooth convex optimization by first-order methods and applications. SIAM J. Optim. (2018)","DOI":"10.1137\/16M1099546"},{"issue":"1","key":"1976_CR120","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1007\/BF02591851","volume":"38","author":"RM Freund","year":"1987","unstructured":"Freund, R.M.: Dual gauge programs, with applications to quadratic programming and the minimum-norm problem. Math. Program. 38(1), 47\u201367 (1987)","journal-title":"Math. Program."},{"issue":"4","key":"1976_CR121","doi-asserted-by":"crossref","first-page":"1999","DOI":"10.1137\/130940785","volume":"24","author":"MP Friedlander","year":"2014","unstructured":"Friedlander, M.P., Macedo, I., Pong, T.K.: Gauge optimization and duality. SIAM J. Optim. 24(4), 1999\u20132022 (2014)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"1976_CR122","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1070\/SM1996v187n02ABEH000111","volume":"187","author":"ES Polovinkin","year":"1996","unstructured":"Polovinkin, E.S.: Strongly convex analysis. Sbornik: Math. 187(2), 259 (1996)","journal-title":"Sbornik: Math."},{"issue":"2","key":"1976_CR123","doi-asserted-by":"crossref","first-page":"865","DOI":"10.1287\/moor.2022.1285","volume":"48","author":"M Molinaro","year":"2022","unstructured":"Molinaro, M.: Strong convexity of feasible sets in off-line and online optimization. Math. Oper. Res. 48(2), 865\u2013884 (2022)","journal-title":"Math. Oper. Res."},{"issue":"284","key":"1976_CR124","first-page":"1","volume":"22","author":"T Kerdreux","year":"2021","unstructured":"Kerdreux, T., Roux, C., d\u2019Aspremont, A., Pokutta, S.: Linear bandits on uniformly convex sets. J. Mach. Learn. Res. 22(284), 1\u201323 (2021)","journal-title":"J. Mach. Learn. Res."},{"key":"1976_CR125","doi-asserted-by":"crossref","unstructured":"Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis. Springer, Berlin (1998)","DOI":"10.1007\/978-3-642-02431-3"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01976-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-01976-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-01976-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,6]],"date-time":"2024-04-06T14:15:15Z","timestamp":1712412915000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-01976-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,22]]},"references-count":125,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1976"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-01976-y","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,6,22]]},"assertion":[{"value":"22 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 April 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 June 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}