{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T14:26:47Z","timestamp":1750343207808,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T00:00:00Z","timestamp":1667779200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100006831","name":"U.S. Air Force","doi-asserted-by":"publisher","award":["AFOSR Grant No. FA9550-19-1-0240"],"award-info":[{"award-number":["AFOSR Grant No. FA9550-19-1-0240"]}],"id":[{"id":"10.13039\/100006831","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006919","name":"Massachusetts Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100006919","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2023,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We propose a simple variant of the generalized Frank\u2013Wolfe method for solving strongly convex composite optimization problems, by introducing an additional averaging step on the dual variables. We show that in this variant, one can choose a simple constant step-size and obtain a linear convergence rate on the duality gaps. By leveraging the convergence analysis of this variant, we then analyze the local convergence rate of the logistic fictitious play algorithm, which is well-established in game theory but lacks any form of convergence rate guarantees. We show that, with high probability, this algorithm converges locally at rate <jats:italic>O<\/jats:italic>(1\/<jats:italic>t<\/jats:italic>), in terms of certain expected duality gap.<\/jats:p>","DOI":"10.1007\/s11590-022-01951-0","type":"journal-article","created":{"date-parts":[[2022,11,7]],"date-time":"2022-11-07T14:02:32Z","timestamp":1667829752000},"page":"1595-1611","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["A generalized Frank\u2013Wolfe method with \u201cdual averaging\u201d for strongly convex composite optimization"],"prefix":"10.1007","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8226-9243","authenticated-orcid":false,"given":"Renbo","family":"Zhao","sequence":"first","affiliation":[]},{"given":"Qiuyun","family":"Zhu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,11,7]]},"reference":[{"issue":"1","key":"1951_CR1","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1137\/130941961","volume":"25","author":"F Bach","year":"2015","unstructured":"Bach, F.: Duality between subgradient and conditional gradient methods. SIAM J. Optim. 25(1), 115\u2013129 (2015)","journal-title":"SIAM J. Optim."},{"key":"1951_CR2","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1007\/s10107-017-1188-6","volume":"171","author":"Y Nesterov","year":"2018","unstructured":"Nesterov, Y.: Complexity bounds for primal-dual methods minimizing the model of objective function. Math. Program. 171, 311\u2013330 (2018)","journal-title":"Math. Program."},{"key":"1951_CR3","doi-asserted-by":"publisher","first-page":"431","DOI":"10.1007\/s10107-017-1225-5","volume":"173","author":"S Ghadimi","year":"2019","unstructured":"Ghadimi, S.: Conditional gradient type methods for composite nonlinear and stochastic optimization. Math. Program. 173, 431\u2013464 (2019)","journal-title":"Math. Program."},{"unstructured":"Pena, J.: Affine invariant convergence rates of the conditional gradient method. arXiv:2112.06727 (2021)","key":"1951_CR4"},{"issue":"1\u20132","key":"1951_CR5","doi-asserted-by":"publisher","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."},{"key":"1951_CR6","doi-asserted-by":"publisher","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."},{"doi-asserted-by":"crossref","unstructured":"Zhao, R., Freund, R.M.: Analysis of the Frank\u2013Wolfe method for convex composite optimization involving a logarithmically-homogeneous barrier. Math. Program. Accepted 2022","key":"1951_CR7","DOI":"10.1007\/s10107-022-01820-9"},{"issue":"3","key":"1951_CR8","doi-asserted-by":"publisher","first-page":"320","DOI":"10.1006\/game.1993.1021","volume":"5","author":"D Fudenberg","year":"1993","unstructured":"Fudenberg, D., Kreps, D.M.: Learning mixed equilibria. Games Econ. Behav. 5(3), 320\u2013367 (1993)","journal-title":"Games Econ. Behav."},{"unstructured":"Kakade, S. M., Shalev-Shwartz, S., Tewari, A.: On the duality of strong convexity and strong smoothness: learning applications and matrix regularization. Technical Report, TTIC. https:\/\/home.ttic.edu\/~shai\/papers\/KakadeShalevTewari09.pdf (2009)","key":"1951_CR9"},{"key":"1951_CR10","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-13710-0","volume-title":"Convex Optimization in Normed Spaces: Theory, Methods and Examples","author":"J Peypouquet","year":"2015","unstructured":"Peypouquet, J.: Convex Optimization in Normed Spaces: Theory, Methods and Examples. Springer, Berlin (2015)"},{"unstructured":"Ny, J.L.: On some extensions of fictitious play. Technical Report. MIT (2006)","key":"1951_CR11"},{"issue":"6","key":"1951_CR12","doi-asserted-by":"publisher","first-page":"2265","DOI":"10.1111\/1468-0262.00376","volume":"70","author":"J Hofbauer","year":"2002","unstructured":"Hofbauer, J., Sandholm, W.H.: On the global convergence of stochastic fictitious play. Econometrica 70(6), 2265\u20132294 (2002)","journal-title":"Econometrica"},{"issue":"1","key":"1951_CR13","doi-asserted-by":"publisher","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(1), 127\u2013152 (2005)","journal-title":"Math. Program."},{"unstructured":"Hunter, D.: Lecture notes in asymptotic tools, chapter 3. http:\/\/personal.psu.edu\/drh20\/asymp\/fall2006\/lectures\/ANGELchpt03.pdf (2006)","key":"1951_CR14"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01951-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-022-01951-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-022-01951-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,7,12]],"date-time":"2023-07-12T13:24:45Z","timestamp":1689168285000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-022-01951-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,11,7]]},"references-count":14,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2023,9]]}},"alternative-id":["1951"],"URL":"https:\/\/doi.org\/10.1007\/s11590-022-01951-0","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2022,11,7]]},"assertion":[{"value":"12 February 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 November 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}