{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T05:26:35Z","timestamp":1787289995838,"version":"build-2736575974"},"reference-count":32,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T00:00:00Z","timestamp":1785456000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T00:00:00Z","timestamp":1785456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["EXC-2046\/1, ID 390685689"],"award-info":[{"award-number":["EXC-2046\/1, ID 390685689"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M14ZAM"],"award-info":[{"award-number":["05M14ZAM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002347","name":"Bundesministerium f\u00fcr Bildung und Forschung","doi-asserted-by":"publisher","award":["05M20ZBM"],"award-info":[{"award-number":["05M20ZBM"]}],"id":[{"id":"10.13039\/501100002347","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["NSF DMS 2532423"],"award-info":[{"award-number":["NSF DMS 2532423"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2026,8]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>We prove that the block-coordinate Frank-Wolfe (BCFW) algorithm converges with state-of-the-art rates in both convex and nonconvex settings under a very mild \u201cblock-iterative\u201d assumption. This appears to be the first result on BCFW addressing the setting of nonconvex objective functions with Lipschitz-continuous gradients and no additional assumptions. This analysis newly allows for (I) progress without activating the most-expensive linear minimization oracle(s), LMO(s), at every iteration, (II) parallelized updates that do not require all LMOs, and therefore (III) deterministic parallel update strategies that take into account the numerical cost of the problem\u2019s LMOs. Our results apply for short-step BCFW as well as an adaptive method for convex functions. New relationships between updated coordinates and primal progress are proven, and a favorable speedup is demonstrated using .<\/jats:p>","DOI":"10.1007\/s10957-026-03068-1","type":"journal-article","created":{"date-parts":[[2026,7,31]],"date-time":"2026-07-31T06:00:57Z","timestamp":1785477657000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Flexible Block-Iterative Analysis for the Frank-Wolfe Algorithm"],"prefix":"10.1007","volume":"210","author":[{"given":"G\u00e1bor","family":"Braun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jannis","family":"Halbey","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sebastian","family":"Pokutta","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0007-4532-2221","authenticated-orcid":false,"given":"Zev","family":"Woodstock","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,7,31]]},"reference":[{"key":"3068_CR1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-48311-5","volume-title":"Convex Analysis and Monotone Operator Theory in Hilbert Spaces","author":"HH Bauschke","year":"2017","unstructured":"Bauschke, H.H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert Spaces, 2nd edn. Springer (2017)","edition":"2"},{"issue":"4","key":"3068_CR2","doi-asserted-by":"publisher","first-page":"2024","DOI":"10.1137\/15M1008397","volume":"25","author":"A Beck","year":"2015","unstructured":"Beck, A., Pauwels, E., Sabach, S.: The cyclic block conditional gradient method for convex optimization problems. SIAM J. Optim. 25(4), 2024\u20132049 (2015). https:\/\/doi.org\/10.1137\/15M1008397","journal-title":"SIAM J. Optim."},{"issue":"4","key":"3068_CR3","doi-asserted-by":"publisher","first-page":"2037","DOI":"10.1137\/120887679","volume":"23","author":"A Beck","year":"2013","unstructured":"Beck, A., Tetruashvili, L.: On the convergence of block coordinate descent type methods. SIAM J. Optim. 23(4), 2037\u20132060 (2013)","journal-title":"SIAM J. Optim."},{"issue":"5","key":"3068_CR4","doi-asserted-by":"publisher","first-page":"2611","DOI":"10.1287\/ijoc.2022.1191","volume":"34","author":"M Besan\u00e7on","year":"2022","unstructured":"Besan\u00e7on, M., Carderera, A., Pokutta, S.: FrankWolfe.jl: a high-performance and flexible toolbox for Frank-Wolfe algorithms and conditional gradients. INFORMS J. Comput. 34(5), 2611\u20132620 (2022)","journal-title":"INFORMS J. Comput."},{"issue":"2","key":"3068_CR5","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10589-024-00585-5","volume":"91","author":"I Bomze","year":"2025","unstructured":"Bomze, I., Rinaldi, F., Zeffiro, D.: Projection free methods on product domains. Comput. Optim. Appl. 91(2), 511\u2013540 (2025)","journal-title":"Comput. Optim. Appl."},{"key":"3068_CR6","doi-asserted-by":"publisher","unstructured":"Braun, G., Carderera, A., Combettes, C.W., Hassani, H., Karbasi, A., Mokhtari, A., Pokutta, S.: Conditional gradient methods. Society for Industrial and Applied Mathematics, Philadelphia, PA (2025). https:\/\/doi.org\/10.1137\/1.9781611978568","DOI":"10.1137\/1.9781611978568"},{"key":"3068_CR7","doi-asserted-by":"publisher","unstructured":"Braun, G., Pokutta, S.: The matching polytope does not admit fully-polynomial size relaxation schemes. In: Proceeding of the 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 837\u2013846. SIAM (2015). https:\/\/doi.org\/10.1137\/1.9781611973730.57","DOI":"10.1137\/1.9781611973730.57"},{"key":"3068_CR8","unstructured":"Braun, G., Pokutta, S., Weismantel, R.: Alternating linear minimization: revisiting von Neumann\u2019s alternating projections. arXiv:2212.02933 (2022)"},{"key":"3068_CR9","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1007\/s10107-017-1221-9","volume":"173","author":"G Braun","year":"2019","unstructured":"Braun, G., Pokutta, S., Zink, D.: Affine reductions for LPs and SDPs. Math. Program. 173, 281\u2013312 (2019). https:\/\/doi.org\/10.1007\/s10107-017-1221-9","journal-title":"Math. Program."},{"issue":"3","key":"3068_CR10","doi-asserted-by":"publisher","first-page":"2231","DOI":"10.1137\/23M1616789","volume":"34","author":"A Carderera","year":"2024","unstructured":"Carderera, A., Besan\u00e7on, M., Pokutta, S.: Scalable Frank-Wolfe on generalized self-concordant functions via simple steps. SIAM J. Optim. 34(3), 2231\u20132258 (2024). https:\/\/doi.org\/10.1137\/23M1616789","journal-title":"SIAM J. Optim."},{"key":"3068_CR11","unstructured":"Combettes, C.W., Pokutta, S.: Boosting Frank-Wolfe by chasing gradients. In: Proceeding of the 37th International Conference on Machine Learning (ICML), pp. 2111\u20132121. PLMR (2020)"},{"issue":"4","key":"3068_CR12","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/j.orl.2021.06.005","volume":"49","author":"CW Combettes","year":"2021","unstructured":"Combettes, C.W., Pokutta, S.: Complexity of linear minimization and projection on some sets. Oper. Res. Lett. 49(4), 565\u2013571 (2021)","journal-title":"Oper. Res. Lett."},{"issue":"1","key":"3068_CR13","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1137\/21M1420368","volume":"15","author":"PL Combettes","year":"2022","unstructured":"Combettes, P.L., Woodstock, Z.C.: A variational inequality model for the construction of signals from inconsistent nonlinear equations. SIAM J. Imaging Sci. 15(1), 84\u2013109 (2022). https:\/\/doi.org\/10.1137\/21M1420368","journal-title":"SIAM J. Imaging Sci."},{"key":"3068_CR14","volume-title":"Approximate Methods in Optimization Problems","author":"VF Demyanov","year":"1970","unstructured":"Demyanov, V.F., Rubinov, A.M.: Approximate Methods in Optimization Problems. American Elsevier Publishing Company, New York (1970)"},{"key":"3068_CR15","unstructured":"Diakonikolas, J., Carderera, A., Pokutta, S.: Locally accelerated conditional gradients. In: Proceeding of the 23rd International Conference on Artificial Intelligence and Statistics (AISTATS), vol. 108, pp. 1737\u20131747. PMLR (2020)"},{"issue":"1","key":"3068_CR16","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1109\/TPAMI.2008.277","volume":"32","author":"CH Ding","year":"2008","unstructured":"Ding, C.H., Li, T., Jordan, M.I.: Convex and semi-nonnegative matrix factorizations. IEEE Trans. Pattern Anal. Mach. Intell. 32(1), 45\u201355 (2008)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"3068_CR17","unstructured":"Hazan, E., Luo, H.: Variance-reduced and projection-free stochastic optimization. In: Proceeding of the 33rd International Conference on Machine Learning (ICML), vol. 48, pp. 1263\u20131271. PMLR (2016)"},{"key":"3068_CR18","doi-asserted-by":"publisher","unstructured":"Kelley, C.T.: Iterative Methods for Linear and Nonlinear Equations. Frontiers in Applied Mathematics, vol. 20. SIAM, Philadelphia (1995). https:\/\/doi.org\/10.1137\/1.9781611970944","DOI":"10.1137\/1.9781611970944"},{"key":"3068_CR19","unstructured":"Lacoste-Julien, S., Jaggi, M., Schmidt, M., Pletscher, P.: Block-coordinate Frank-Wolfe optimization for structural SVMs. In: Dasgupta, S., McAllester, D. (eds.) Proceeding of the 30th International Conference on Machine Learning, vol. 28, pp. 53\u201361. PMLR, Atlanta, GA, USA (2013)"},{"key":"3068_CR20","unstructured":"Osokin, A., Alayrac, J.B., Lukasewitz, I., Dokania, P., Lacoste-Julien, S.: Minding the gaps for block Frank-Wolfe optimization of structured SVMs. In: Balcan, M.F., Weinberger, K.Q. (eds.) Proceeding of the 33rd International Conference on Machine Learning, vol. 48, pp. 593\u2013602. PMLR, New York, NY, USA (2016)"},{"key":"3068_CR21","doi-asserted-by":"publisher","first-page":"433","DOI":"10.1007\/BF00939552","volume":"56","author":"N Ottavy","year":"1988","unstructured":"Ottavy, N.: Strong convergence of projection-like methods in Hilbert spaces. J. Optim. Theory Appl. 56, 433\u2013461 (1988)","journal-title":"J. Optim. Theory Appl."},{"key":"3068_CR22","doi-asserted-by":"publisher","first-page":"5","DOI":"10.1023\/A:1018358602892","volume":"9","author":"M Patriksson","year":"1998","unstructured":"Patriksson, M.: Decomposition methods for differentiable optimization problems over cartesian product sets. Comput. Optim. Appl. 9, 5\u201342 (1998)","journal-title":"Comput. Optim. Appl."},{"key":"3068_CR23","unstructured":"Pedregosa, F., Negiar, G., Askari, A., Jaggi, M.: Linearly convergent Frank-Wolfe with backtracking line-search. In: International conference on artificial intelligence and statistics, pp. 1\u201310. PMLR (2020)"},{"issue":"1","key":"3068_CR24","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1365\/s13291-023-00275-x","volume":"126","author":"S Pokutta","year":"2024","unstructured":"Pokutta, S.: The Frank-Wolfe algorithm: a short introduction. Jahresber. Dtsch. Math.-Ver. 126(1), 3\u201335 (2024). https:\/\/doi.org\/10.1365\/s13291-023-00275-x","journal-title":"Jahresber. Dtsch. Math.-Ver."},{"issue":"6","key":"3068_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3127497","volume":"64","author":"T Rothvoss","year":"2017","unstructured":"Rothvoss, T.: The matching polytope has exponential extension complexity. J. ACM 64(6), 1\u201319 (2017). https:\/\/doi.org\/10.1145\/3127497","journal-title":"J. ACM"},{"issue":"1","key":"3068_CR26","first-page":"133","volume":"19","author":"VE Shamanskii","year":"1967","unstructured":"Shamanskii, V.E.: A modification of Newton\u2019s method. Ukran. Mat. Zh. 19(1), 133\u2013138 (1967)","journal-title":"Ukran. Mat. Zh."},{"key":"3068_CR27","unstructured":"Srebro, N., Rennie, J., Jaakkola, T.: Maximum-margin matrix factorization. In: Saul, L., Weiss, Y., Bottou, L. (eds.) Advances in Neural Information Processing Systems, vol. 17, pp. 1329\u20131336. MIT Press (2004)"},{"key":"3068_CR28","unstructured":"Taskar, B., Guestrin, C., Koller, D.: Max-margin markov networks. In: Thrun, S., Saul, L., Sch\u00f6lkopf, B. (eds.) Advances in Neural Information Processing Systems, vol.\u00a016. MIT Press (2003). https:\/\/proceedings.neurips.cc\/paper_files\/paper\/2003\/file\/878d5691c824ee2aaf770f7d36c151d6-Paper.pdf"},{"key":"3068_CR29","doi-asserted-by":"publisher","first-page":"307","DOI":"10.1007\/s10107-016-1009-3","volume":"161","author":"AB Taylor","year":"2017","unstructured":"Taylor, A.B., Hendrickx, J.M., Glineur, F.: Smooth strongly convex interpolation and exact worst-case performance of first-order methods. Math. Program. 161, 307\u2013345 (2017). https:\/\/doi.org\/10.1007\/s10107-016-1009-3","journal-title":"Math. Program."},{"key":"3068_CR30","doi-asserted-by":"publisher","first-page":"475","DOI":"10.1023\/A:1017501703105","volume":"109","author":"P Tseng","year":"2001","unstructured":"Tseng, P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109, 475\u2013494 (2001)","journal-title":"J. Optim. Theory Appl."},{"key":"3068_CR31","unstructured":"Wang, Y.X., Sadhanala, V., Dai, W., Neiswanger, W., Sra, S., Xing, E.: Parallel and distributed block-coordinate Frank-Wolfe algorithms. In: Balcan, M.F., Weinberger, K.Q. (eds.) Proceeding of The 33rd International Conference on Machine Learning, vol. 48, pp. 1548\u20131557. PMLR, New York, NY, USA (2016)"},{"issue":"1","key":"3068_CR32","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1137\/24M1638008","volume":"35","author":"Z Woodstock","year":"2025","unstructured":"Woodstock, Z., Pokutta, S.: Splitting the conditional gradient algorithm. SIAM J. Optim. 35(1), 347\u2013368 (2025)","journal-title":"SIAM J. Optim."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-03068-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10957-026-03068-1","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-026-03068-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T05:08:59Z","timestamp":1787288939000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10957-026-03068-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,7,31]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2026,8]]}},"alternative-id":["3068"],"URL":"https:\/\/doi.org\/10.1007\/s10957-026-03068-1","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,7,31]]},"assertion":[{"value":"21 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 July 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"31 July 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"37"}}