{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T19:48:15Z","timestamp":1770752895827,"version":"3.50.0"},"reference-count":109,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T00:00:00Z","timestamp":1727308800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T00:00:00Z","timestamp":1727308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000143","name":"Division of Computing and Communication Foundations","doi-asserted-by":"publisher","award":["1718477"],"award-info":[{"award-number":["1718477"]}],"id":[{"id":"10.13039\/100000143","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000144","name":"Division of Computer and Network Systems","doi-asserted-by":"publisher","award":["1824418"],"award-info":[{"award-number":["1824418"]}],"id":[{"id":"10.13039\/100000144","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Comput Optim Appl"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper presents a subgradient-based algorithm for constrained nonsmooth convex optimization that does not require projections onto the feasible set. While the well-established Frank\u2013Wolfe algorithm and its variants already avoid projections, they are primarily designed for smooth objective functions. In contrast, our proposed algorithm can handle nonsmooth problems with general convex functional inequality constraints. It achieves an <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\epsilon $$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>\u03f5<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>-suboptimal solution in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {O}(\\epsilon ^{-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:msup>\n                      <mml:mi>\u03f5<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mo>-<\/mml:mo>\n                        <mml:mn>2<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> iterations, with each iteration requiring only a single (potentially inexact) Linear Minimization Oracle call and a (possibly inexact) subgradient computation. This performance is consistent with existing lower bounds. Similar performance is observed when deterministic subgradients are replaced with stochastic subgradients. In the special case where there are no functional inequality constraints, our algorithm competes favorably with a recent nonsmooth projection-free method designed for constraint-free problems. Our approach utilizes a simple separation scheme in conjunction with a new Lagrange multiplier update rule.<\/jats:p>","DOI":"10.1007\/s10589-024-00607-2","type":"journal-article","created":{"date-parts":[[2024,9,26]],"date-time":"2024-09-26T15:42:32Z","timestamp":1727365352000},"page":"927-975","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Nonsmooth projection-free optimization with functional constraints"],"prefix":"10.1007","volume":"89","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2399-6432","authenticated-orcid":false,"given":"Kamiar","family":"Asgari","sequence":"first","affiliation":[]},{"given":"Michael J.","family":"Neely","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,9,26]]},"reference":[{"key":"607_CR1","doi-asserted-by":"publisher","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004). https:\/\/doi.org\/10.1017\/CBO9780511804441","DOI":"10.1017\/CBO9780511804441"},{"key":"607_CR2","doi-asserted-by":"publisher","unstructured":"Palomar, D.P., Eldar, Y.C.: Convex Optimization in Signal Processing and Communications. Cambridge University Press, Cambridge (2009). https:\/\/doi.org\/10.1017\/CBO9780511804458","DOI":"10.1017\/CBO9780511804458"},{"key":"607_CR3","volume-title":"Optimization for Machine Learning","author":"S Sra","year":"2012","unstructured":"Sra, S., Nowozin, S., Wright, S.J.: Optimization for Machine Learning. The MIT Press, Cambridge (2012)"},{"key":"607_CR4","doi-asserted-by":"publisher","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1994). https:\/\/doi.org\/10.1137\/1.9781611970791","DOI":"10.1137\/1.9781611970791"},{"key":"607_CR5","doi-asserted-by":"publisher","unstructured":"Nesterov, Y.: Lectures on Convex Optimization, 2nd ed. 2018. edn. Springer Optimization and Its Applications, 137. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-91578-4","DOI":"10.1007\/978-3-319-91578-4"},{"key":"607_CR6","doi-asserted-by":"publisher","unstructured":"Beck, A.: First-order Methods in Optimization. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2017). https:\/\/doi.org\/10.1137\/1.9781611974997","DOI":"10.1137\/1.9781611974997"},{"key":"607_CR7","doi-asserted-by":"publisher","unstructured":"Lan, G.: First-order and Stochastic Optimization Methods for Machine Learning vol. 1. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-39568-1","DOI":"10.1007\/978-3-030-39568-1"},{"key":"607_CR8","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2022.103683","volume":"306","author":"G Perez","year":"2022","unstructured":"Perez, G., Ament, S., Gomes, C., Barlaud, M.: Efficient projection algorithms onto the weighted $$l1$$ ball. Artif. Intell. 306, 103683 (2022)","journal-title":"Artif. Intell."},{"issue":"4","key":"607_CR9","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). https:\/\/doi.org\/10.1016\/j.orl.2021.06.005","journal-title":"Oper. Res. Lett."},{"key":"607_CR10","unstructured":"Combettes, C.W.: Frank-Wolfe Methods for Optimization and Machine Learning. PhD thesis, Georgia Institute of Technology (2021)"},{"issue":"1\u20132","key":"607_CR11","doi-asserted-by":"publisher","first-page":"221","DOI":"10.1007\/s10107-015-0876-3","volume":"156","author":"A Juditsky","year":"2016","unstructured":"Juditsky, A., Nemirovski, A.: Solving variational inequalities with monotone operators on domains given by linear minimization oracles. Math. Program. 156(1\u20132), 221\u2013256 (2016)","journal-title":"Math. Program."},{"key":"607_CR12","unstructured":"Jaggi, M.: Revisiting Frank-Wolfe: Projection-free sparse convex optimization. In: Dasgupta, S., McAllester, D. (eds.) Proceedings of the 30th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 28, pp. 427\u2013435. PMLR, Atlanta, Georgia, USA (2013)"},{"issue":"1\u20132","key":"607_CR13","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. Naval Res. Logist Q. 3(1\u20132), 95\u2013110 (1956). https:\/\/doi.org\/10.1002\/nav.3800030109","journal-title":"Naval Res. Logist Q."},{"key":"607_CR14","unstructured":"Argyriou, A., Signoretto, M., Suykens, J.: Hybrid Conditional Gradient\u2013Smoothing Algorithms with Applications to Sparse and Low Rank Regularization (2014)"},{"issue":"5","key":"607_CR15","doi-asserted-by":"publisher","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). https:\/\/doi.org\/10.1016\/0041-5553(66)90114-5","journal-title":"USSR Comput. Math. Math. Phys."},{"key":"607_CR16","unstructured":"Yurtsever, A., Fercoq, O., Locatello, F., Cevher, V.: A Conditional Gradient Framework for Composite Convex Minimization with Applications to Semidefinite Programming (2018)"},{"key":"607_CR17","unstructured":"Lan, G.: The Complexity of Large-scale Convex Programming under a Linear Optimization Oracle (2014)"},{"key":"607_CR18","unstructured":"Nemirovskij, A.S., Yudin, D.B.: Problem complexity and method efficiency in optimization (1983)"},{"key":"607_CR19","doi-asserted-by":"crossref","unstructured":"Bubeck, S., et al.: Convex optimization: algorithms and complexity. Foundations and Trends\u00ae in Machine Learning 8(3-4), 231\u2013357 (2015)","DOI":"10.1561\/2200000050"},{"key":"607_CR20","unstructured":"Nemirovski, A.: Information-based complexity of convex programming. Lecture Notes 834 (1995)"},{"key":"607_CR21","unstructured":"Lacoste-Julien, S., Jaggi, M., Schmidt, M., Pletscher, P.: Block-coordinate Frank-Wolfe optimization for structural SVMs. In: Dasgupta, S., McAllester, D. (eds.) Proceedings of the 30th International Conference on Machine Learning. Proceedings of Machine Learning Research, vol. 28, pp. 53\u201361. PMLR, Atlanta, Georgia, USA (2013)"},{"key":"607_CR22","doi-asserted-by":"crossref","unstructured":"Jing, N., Fang, E.X., Tang, C.Y.: Robust matrix estimations meet frank\u2013wolfe algorithm. Machine Learning, 1\u201338 (2023)","DOI":"10.1007\/s10994-023-06325-w"},{"issue":"5","key":"607_CR23","doi-asserted-by":"publisher","first-page":"3291","DOI":"10.1137\/15M101628X","volume":"38","author":"C Mu","year":"2016","unstructured":"Mu, C., Zhang, Y., Wright, J., Goldfarb, D.: Scalable robust matrix recovery: frank-wolfe meets proximal methods. SIAM J. Sci. Comput. 38(5), 3291\u20133317 (2016)","journal-title":"SIAM J. Sci. Comput."},{"issue":"1","key":"607_CR24","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1007\/s10107-021-01735-x","volume":"197","author":"CW Combettes","year":"2023","unstructured":"Combettes, C.W., Pokutta, S.: Revisiting the approximate carath\u00e9odory problem via the frank-wolfe algorithm. Math. Program. 197(1), 191\u2013214 (2023)","journal-title":"Math. Program."},{"key":"607_CR25","unstructured":"Hazan, E., Kakade, S.M., Singh, K., Soest, A.V.: Provably Efficient Maximum Entropy Exploration (2019)"},{"key":"607_CR26","unstructured":"Lin, J.-L., Hung, W., Yang, S.-H., Hsieh, P.-C., Liu, X.: Escaping from Zero Gradient: Revisiting Action-Constrained Reinforcement Learning via Frank-Wolfe Policy Optimization (2021)"},{"key":"607_CR27","unstructured":"Garber, D.: Faster Projection-free Convex Optimization over the Spectrahedron (2016)"},{"issue":"1","key":"607_CR28","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(1), 311\u2013330 (2018). https:\/\/doi.org\/10.1007\/s10107-017-1188-6","journal-title":"Math. Program."},{"issue":"2","key":"607_CR29","doi-asserted-by":"publisher","first-page":"283","DOI":"10.1007\/BF00939671","volume":"78","author":"DJ White","year":"1993","unstructured":"White, D.J.: Extension of the frank-wolfe algorithm to concave nondifferentiable objective functions. J. Optim. Theory Appl. 78(2), 283\u2013301 (1993). https:\/\/doi.org\/10.1007\/BF00939671","journal-title":"J. Optim. Theory Appl."},{"key":"607_CR30","unstructured":"Ravi, S.N., Collins, M.D., Singh, V.: A Deterministic Nonsmooth Frank Wolfe Algorithm with Coreset Guarantees (2017)"},{"key":"607_CR31","doi-asserted-by":"crossref","unstructured":"Cheung, E., Li, Y.: Solving separable nonsmooth problems using frank-wolfe with uniform affine approximations. In: IJCAI, pp. 2035\u20132041 (2018)","DOI":"10.24963\/ijcai.2018\/281"},{"key":"607_CR32","doi-asserted-by":"publisher","unstructured":"Moreau, J.J.: Proximit\u00e9 et dualit\u00e9 dans un espace hilbertien. Bulletin de la Soci\u00e9t\u00e9 Math\u00e9matique de France 93, 273\u2013299 (1965) https:\/\/doi.org\/10.24033\/bsmf.1625","DOI":"10.24033\/bsmf.1625"},{"issue":"1","key":"607_CR33","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). https:\/\/doi.org\/10.1007\/s10107-004-0552-5","journal-title":"Math. Program."},{"key":"607_CR34","doi-asserted-by":"publisher","unstructured":"Parikh, N., Boyd, S.: Proximal algorithms. Foundations and Trends\u00aein Optimization 1(3), 127\u2013239 (2014) https:\/\/doi.org\/10.1561\/2400000003","DOI":"10.1561\/2400000003"},{"key":"607_CR35","unstructured":"Yurtsever, A., Tran\u00a0Dinh, Q., Cevher, V.: A universal primal-dual convex optimization framework. Adv. Neural Inform. Process. Syst.28 (2015)"},{"issue":"2","key":"607_CR36","doi-asserted-by":"publisher","first-page":"674","DOI":"10.1137\/110831659","volume":"22","author":"JC Duchi","year":"2012","unstructured":"Duchi, J.C., Bartlett, P.L., Wainwright, M.J.: Randomized smoothing for stochastic optimization. SIAM J. Optim. 22(2), 674\u2013701 (2012). https:\/\/doi.org\/10.1137\/110831659","journal-title":"SIAM J. Optim."},{"key":"607_CR37","unstructured":"Hazan, E., Kale, S.: Projection-free online learning. In: Proceedings of the 29th International Coference on International Conference on Machine Learning. ICML\u201912, pp. 1843\u20131850. Omnipress, Madison, WI, USA (2012)"},{"key":"607_CR38","first-page":"12211","volume":"33","author":"KK Thekumparampil","year":"2020","unstructured":"Thekumparampil, K.K., Jain, P., Netrapalli, P., Oh, S.: Projection efficient subgradient method and optimal nonsmooth frank-wolfe method. Adv. Neural. Inf. Process. Syst. 33, 12211\u201312224 (2020)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"issue":"1","key":"607_CR39","doi-asserted-by":"publisher","first-page":"42","DOI":"10.1016\/0041-5553(74)90004-4","volume":"13","author":"V Polyak","year":"1973","unstructured":"Polyak, V., Tret\u2019yakov, N.: The method of penalty estimates for conditional extremum problems. USSR Comput. Math. Math. Phys. 13(1), 42\u201358 (1973)","journal-title":"USSR Comput. Math. Math. Phys."},{"issue":"2","key":"607_CR40","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/s10589-020-00179-x","volume":"76","author":"G Lan","year":"2020","unstructured":"Lan, G., Zhou, Z.: Algorithms for stochastic optimization with function or expectation constraints. Comput. Optim. Appl. 76(2), 461\u2013498 (2020). https:\/\/doi.org\/10.1007\/s10589-020-00179-x","journal-title":"Comput. Optim. Appl."},{"key":"607_CR41","unstructured":"Lin, Q., Ma, R., Yang, T.: Level-set methods for finite-sum constrained convex optimization. In: International Conference on Machine Learning, pp. 3112\u20133121 (2018). PMLR"},{"issue":"4","key":"607_CR42","doi-asserted-by":"publisher","first-page":"3290","DOI":"10.1137\/17M1152334","volume":"28","author":"Q Lin","year":"2018","unstructured":"Lin, Q., Nadarajah, S., Soheili, N.: A level-set method for convex optimization with a feasible solution path. SIAM J. Optim. 28(4), 3290\u20133311 (2018)","journal-title":"SIAM J. Optim."},{"issue":"2","key":"607_CR43","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."},{"key":"607_CR44","volume-title":"Nonlinear Programming","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Raleigh (1999)","edition":"2"},{"key":"607_CR45","doi-asserted-by":"publisher","first-page":"199","DOI":"10.1007\/s10107-019-01425-9","volume":"185","author":"Y Xu","year":"2021","unstructured":"Xu, Y.: Iteration complexity of inexact augmented lagrangian methods for constrained convex programming. Math. Program. 185, 199\u2013244 (2021)","journal-title":"Math. Program."},{"key":"607_CR46","volume-title":"Lagrangian Methods for $${\\cal{O} }(1\/t)$$ Convergence in Constrained convex programs","author":"MJ Neely","year":"2019","unstructured":"Neely, M.J., Yu, H.: Lagrangian Methods for $${\\cal{O} }(1\/t)$$ Convergence in Constrained convex programs. Theory, Methods, and Applications, edited by Arto Ruud, Nova Publishers, Convex Optimization (2019)"},{"issue":"1\u20132","key":"607_CR47","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s10107-015-0861-x","volume":"155","author":"G Lan","year":"2016","unstructured":"Lan, G., Monteiro, R.D.: Iteration-complexity of first-order augmented lagrangian methods for convex programming. Math. Program. 155(1\u20132), 511\u2013547 (2016)","journal-title":"Math. Program."},{"key":"607_CR48","unstructured":"Wei, X., Yu, H., Ling, Q., Neely, M.J.: Solving Non-smooth Constrained Programs with Lower Complexity than $${\\cal{O}}(1\/\\epsilon )$$: a Primal-Dual Homotopy Smoothing Approach (2018)"},{"key":"607_CR49","doi-asserted-by":"publisher","unstructured":"Yu, H., Neely, M.J.: A primal-dual type algorithm with the $${\\cal O\\it }(1\/t)$$ convergence rate for large scale constrained convex programs. In: 2016 IEEE 55th Conference on Decision and Control (CDC), pp. 1900\u20131905 (2016). https:\/\/doi.org\/10.1109\/CDC.2016.7798542","DOI":"10.1109\/CDC.2016.7798542"},{"key":"607_CR50","unstructured":"Yu, H., Neely, M., Wei, X.: Online convex optimization with stochastic constraints. Adv. Neural Inform. Process. Syst. 30 (2017)"},{"key":"607_CR51","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/BF01585555","volume":"69","author":"C Lemar\u00e9chal","year":"1995","unstructured":"Lemar\u00e9chal, C., Nemirovskii, A., Nesterov, Y.: New variants of bundle methods. Math. Program. 69, 111\u2013147 (1995)","journal-title":"Math. Program."},{"issue":"1","key":"607_CR52","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1007\/s10107-007-0123-7","volume":"116","author":"E Karas","year":"2009","unstructured":"Karas, E., Ribeiro, A., Sagastiz\u00e1bal, C., Solodov, M.: A bundle-filter method for nonsmooth convex constrained optimization. Math. Program. 116(1), 297\u2013320 (2009)","journal-title":"Math. Program."},{"issue":"1","key":"607_CR53","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/s10107-021-01742-y","volume":"197","author":"D Boob","year":"2023","unstructured":"Boob, D., Deng, Q., Lan, G.: Stochastic first-order methods for convex and nonconvex functional constrained optimization. Math. Program. 197(1), 215\u2013279 (2023)","journal-title":"Math. Program."},{"key":"607_CR54","unstructured":"Wei, X., Neely, M.J.: Primal-Dual Frank-Wolfe for Constrained Stochastic Programs with Convex and Non-convex Objectives (2018)"},{"issue":"3","key":"607_CR55","doi-asserted-by":"publisher","first-page":"2307","DOI":"10.1137\/20M1352788","volume":"31","author":"G Lan","year":"2021","unstructured":"Lan, G., Romeijn, E., Zhou, Z.: Conditional gradient methods for convex optimization with general affine and nonlinear constraints. SIAM J. Optim. 31(3), 2307\u20132339 (2021)","journal-title":"SIAM J. Optim."},{"key":"607_CR56","unstructured":"Lee, D., Ho-Nguyen, N., Lee, D.: Projection-Free Online Convex Optimization with Stochastic Constraints (2023)"},{"key":"607_CR57","unstructured":"Mahdavi, M., Yang, T., Jin, R., Zhu, S., Yi, J.: Stochastic gradient descent with only one projection. Adv. Neural Inform. Process. Syst. 25 (2012)"},{"key":"607_CR58","unstructured":"Levy, K., Krause, A.: Projection free online learning over smooth sets. In: The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1458\u20131466 (2019). PMLR"},{"key":"607_CR59","unstructured":"Lee, Y.T., Sidford, A., Vempala, S.S.: Efficient convex optimization with membership oracles. In: Conference On Learning Theory, pp. 1292\u20131294 (2018). PMLR"},{"key":"607_CR60","unstructured":"Mhammedi, Z.: Efficient projection-free online convex optimization with membership oracle. In: Conference on Learning Theory, pp. 5314\u20135390 (2022). PMLR"},{"key":"607_CR61","unstructured":"Garber, D., Kretzu, B.: New projection-free algorithms for online convex optimization with adaptive regret guarantees. In: Conference on Learning Theory, pp. 2326\u20132359 (2022). PMLR"},{"key":"607_CR62","unstructured":"Lu, Z., Brukhim, N., Gradu, P., Hazan, E.: Projection-free adaptive regret with membership oracles. In: International Conference on Algorithmic Learning Theory, pp. 1055\u20131073 (2023). PMLR"},{"key":"607_CR63","unstructured":"Garber, D., Kretzu, B.: New Projection-free Algorithms for Online Convex Optimization with Adaptive Regret Guarantees (2023)"},{"key":"607_CR64","unstructured":"Gatmiry, K., Mhammedi, Z.: Projection-Free Online Convex Optimization via Efficient Newton Iterations (2023)"},{"key":"607_CR65","unstructured":"Garber, D., Kretzu, B.: Projection-free online exp-concave optimization. In: The Thirty Sixth Annual Conference on Learning Theory, pp. 1259\u20131284 (2023). PMLR"},{"key":"607_CR66","unstructured":"Grimmer, B.: Radial Duality Part II: Applications and Algorithms (2022)"},{"key":"607_CR67","doi-asserted-by":"crossref","unstructured":"Grimmer, B.: Radial Duality Part I: Foundations (2023)","DOI":"10.1007\/s10107-023-02006-7"},{"key":"607_CR68","doi-asserted-by":"crossref","unstructured":"Combettes, C.W., Pokutta, S.: Complexity of Linear Minimization and Projection on Some Sets (2021)","DOI":"10.1016\/j.orl.2021.06.005"},{"key":"607_CR69","volume-title":"Convex Optimization Theory","author":"D Bertsekas","year":"2009","unstructured":"Bertsekas, D.: Convex Optimization Theory, vol. 1. Athena Scientific, Raleigh (2009)"},{"key":"607_CR70","volume-title":"Convex Optimization Algorithms","author":"D Bertsekas","year":"2015","unstructured":"Bertsekas, D.: Convex Optimization Algorithms. Athena Scientific, Raleigh (2015)"},{"issue":"3","key":"607_CR71","doi-asserted-by":"publisher","first-page":"237","DOI":"10.1057\/palgrave.jors.2600523","volume":"49","author":"FP Kelly","year":"1998","unstructured":"Kelly, F.P., Maulloo, A.K., Tan, D.K.H.: Rate control for communication networks: shadow prices, proportional fairness and stability. J. Oper. Res. Soc. 49(3), 237\u2013252 (1998)","journal-title":"J. Oper. Res. Soc."},{"key":"607_CR72","volume-title":"Linear Network Optimization: Algorithms and Codes","author":"DP Bertsekas","year":"1991","unstructured":"Bertsekas, D.P.: Linear Network Optimization: Algorithms and Codes. MIT press, Cambridge (1991)"},{"issue":"4","key":"607_CR73","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1287\/trsc.19.4.445","volume":"19","author":"LJ LeBlanc","year":"1985","unstructured":"LeBlanc, L.J., Helgason, R.V., Boyce, D.E.: Improved efficiency of the frank-wolfe algorithm for convex network programs. Transp. Sci. 19(4), 445\u2013462 (1985)","journal-title":"Transp. Sci."},{"key":"607_CR74","volume-title":"Netw. Optim. Contin. Discrete Models","author":"DP Bertsekas","year":"1998","unstructured":"Bertsekas, D.P.: Netw. Optim. Contin. Discrete Models. Athena Scientific, Raleigh (1998)"},{"issue":"1","key":"607_CR75","first-page":"1","volume":"3","author":"MJ Neely","year":"2010","unstructured":"Neely, M.J.: Stochastic network optimization with application to communication and queueing systems. Synth. Lect. Commun. Netw. 3(1), 1\u2013211 (2010)","journal-title":"Synth. Lect. Commun. Netw."},{"key":"607_CR76","doi-asserted-by":"crossref","unstructured":"Hazan, E.: Sparse approximate solutions to semidefinite programs. In: Latin American Symposium on Theoretical Informatics, pp. 306\u2013316 (2008). Springer","DOI":"10.1007\/978-3-540-78773-0_27"},{"key":"607_CR77","doi-asserted-by":"crossref","unstructured":"Hampel, F.R., Ronchetti, E.M., Rousseeuw, P.J., Stahel, W.A.: Robust statistics. Wiley Series in Probability and Statistics (2005)","DOI":"10.1002\/9781118186435"},{"key":"607_CR78","doi-asserted-by":"publisher","unstructured":"Huber, P.J.: In: Kotz, S., Johnson, N.L. (eds.) Robust Estimation of a Location Parameter, pp. 492\u2013518. Springer, New York, NY (1992). https:\/\/doi.org\/10.1007\/978-1-4612-4380-9_35","DOI":"10.1007\/978-1-4612-4380-9_35"},{"key":"607_CR79","unstructured":"Lerasle, M.: Selected topics on robust statistical learning theory. Lecture Notes (2019)"},{"key":"607_CR80","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/BF00994018","volume":"20","author":"C Cortes","year":"1995","unstructured":"Cortes, C., Vapnik, V.: Support-vector networks. Mach. Learn. 20, 273\u2013297 (1995)","journal-title":"Mach. Learn."},{"key":"607_CR81","doi-asserted-by":"publisher","unstructured":"Hastie, T., Tibshirani, R., Wainwright, M.: Statistical Learning with Sparsity: the Lasso and Generalizations. CRC press, Boca Raton, Florida (2015).https:\/\/doi.org\/10.1201\/b18401","DOI":"10.1201\/b18401"},{"key":"607_CR82","doi-asserted-by":"publisher","DOI":"10.23635\/LMCS-16(1:18)2020","author":"I Petrakis","year":"2020","unstructured":"Petrakis, I.: McShane-Whitney extensions in constructive analysis. Logical Methods Comput. Sci. (2020). https:\/\/doi.org\/10.23635\/LMCS-16(1:18)2020","journal-title":"Logical Methods Comput. Sci."},{"issue":"3","key":"607_CR83","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1137\/0803026","volume":"3","author":"G Chen","year":"1993","unstructured":"Chen, G., Teboulle, M.: Convergence analysis of a proximal-like minimization algorithm using bregman functions. SIAM J. Optim. 3(3), 538\u2013543 (1993)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"607_CR84","doi-asserted-by":"publisher","first-page":"1574","DOI":"10.1137\/070704277","volume":"19","author":"A Nemirovski","year":"2009","unstructured":"Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19(4), 1574\u20131609 (2009)","journal-title":"SIAM J. Optim."},{"key":"607_CR85","unstructured":"Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Submitt. SIAM J. Optim. 2(3) (2008)"},{"key":"607_CR86","doi-asserted-by":"crossref","unstructured":"Borchani, H., Varando, G., Bielza, C., Larranaga, P.: A survey on multi-output regression. Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery 5(5), 216\u2013233 (2015)","DOI":"10.1002\/widm.1157"},{"issue":"12","key":"607_CR87","doi-asserted-by":"publisher","first-page":"5586","DOI":"10.1109\/TKDE.2021.3070203","volume":"34","author":"Y Zhang","year":"2021","unstructured":"Zhang, Y., Yang, Q.: A survey on multi-task learning. IEEE Trans. Knowl. Data Eng. 34(12), 5586\u20135609 (2021)","journal-title":"IEEE Trans. Knowl. Data Eng."},{"key":"607_CR88","doi-asserted-by":"crossref","unstructured":"Anderson, T.W.: Estimating linear restrictions on regression coefficients for multivariate normal distributions. The Annals of Mathematical Statistics, 327\u2013351 (1951)","DOI":"10.1214\/aoms\/1177729580"},{"key":"607_CR89","unstructured":"Fazel, M.: Matrix Rank Minimization with Applications. PhD thesis, PhD thesis, Stanford University (2002)"},{"issue":"4","key":"607_CR90","doi-asserted-by":"publisher","first-page":"901","DOI":"10.1093\/biomet\/ast036","volume":"100","author":"K Chen","year":"2013","unstructured":"Chen, K., Dong, H., Chan, K.-S.: Reduced rank regression via adaptive nuclear norm penalization. Biometrika 100(4), 901\u2013920 (2013)","journal-title":"Biometrika"},{"key":"607_CR91","doi-asserted-by":"crossref","unstructured":"Ding, C., Zhou, D., He, X., Zha, H.: R 1-pca: rotational invariant l 1-norm principal component analysis for robust subspace factorization. In: Proceedings of the 23rd International Conference on Machine Learning, pp. 281\u2013288 (2006)","DOI":"10.1145\/1143844.1143880"},{"key":"607_CR92","doi-asserted-by":"crossref","unstructured":"Ming, D., Ding, C., Nie, F.: A probabilistic derivation of lasso and l12-norm feature selections. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 33, pp. 4586\u20134593 (2019)","DOI":"10.1609\/aaai.v33i01.33014586"},{"key":"607_CR93","unstructured":"Thekumparampil, K.K.: Optimal nonsmooth frank-wolfe method for stochastic regret minimization. (2020). https:\/\/api.semanticscholar.org\/CorpusID:229347497"},{"issue":"2","key":"607_CR94","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1002\/net.3230030202","volume":"3","author":"L Fratta","year":"1973","unstructured":"Fratta, L., Gerla, M., Kleinrock, L.: The flow deviation method: an approach to store-and-forward communication network design. Networks 3(2), 97\u2013133 (1973)","journal-title":"Networks"},{"issue":"4","key":"607_CR95","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1002\/net.3230040406","volume":"4","author":"RW Klessig","year":"1974","unstructured":"Klessig, R.W.: An algorithm for nonlinear multicommodity flow problems. Networks 4(4), 343\u2013355 (1974)","journal-title":"Networks"},{"key":"607_CR96","doi-asserted-by":"publisher","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT press, Cambridge, MA (2022). https:\/\/doi.org\/10.5555\/1614191","DOI":"10.5555\/1614191"},{"issue":"1","key":"607_CR97","doi-asserted-by":"publisher","first-page":"94","DOI":"10.1080\/10556788.2014.895828","volume":"30","author":"P Kov\u00e1cs","year":"2015","unstructured":"Kov\u00e1cs, P.: Minimum-cost flow algorithms: an experimental evaluation. Optim. Methods Softw. 30(1), 94\u2013127 (2015)","journal-title":"Optim. Methods Softw."},{"key":"607_CR98","doi-asserted-by":"publisher","unstructured":"Blair, C.: Problem complexity and method efficiency in optimization (a. s. nemirovsky and d. b. yudin). SIAM Review 27(2), 264\u2013265 (1985) https:\/\/doi.org\/10.1137\/1027074","DOI":"10.1137\/1027074"},{"issue":"3","key":"607_CR99","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1016\/S0167-6377(02)00231-6","volume":"31","author":"A Beck","year":"2003","unstructured":"Beck, A., Teboulle, M.: Mirror descent and nonlinear projected subgradient methods for convex optimization. Oper. Res. Lett. 31(3), 167\u2013175 (2003)","journal-title":"Oper. Res. Lett."},{"key":"607_CR100","unstructured":"Bach, F., Moulines, E.: Non-strongly-convex smooth stochastic approximation with convergence rate $${\\cal O\\it }(1\/n)$$ (2013)"},{"key":"607_CR101","unstructured":"Hazan, E., Minasyan, E.: Faster projection-free online learning. In: Conference on Learning Theory, pp. 1877\u20131893 (2020). PMLR"},{"key":"607_CR102","doi-asserted-by":"publisher","unstructured":"Tao, W., Pan, Z., Wu, G., Tao, Q.: The strength of nesterov\u2019s extrapolation in the individual convergence of nonsmooth optimization. IEEE Transactions on Neural Networks and Learning Systems, 1\u201312 (2019) https:\/\/doi.org\/10.1109\/tnnls.2019.2933452","DOI":"10.1109\/tnnls.2019.2933452"},{"key":"607_CR103","doi-asserted-by":"publisher","unstructured":"Golub, G.H., Van\u00a0Loan, C.F.: Matrix Computations. JHU press, Baltimore (2013). https:\/\/doi.org\/10.56021\/9781421407944","DOI":"10.56021\/9781421407944"},{"issue":"1","key":"607_CR104","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1137\/18M1233170","volume":"31","author":"D Garber","year":"2021","unstructured":"Garber, D.: On the convergence of projected-gradient methods with low-rank projections for smooth convex minimization over trace-norm balls and related problems. SIAM J. Optim. 31(1), 727\u2013753 (2021)","journal-title":"SIAM J. Optim."},{"key":"607_CR105","doi-asserted-by":"crossref","unstructured":"Lanczos, C.: An iteration method for the solution of the eigenvalue problem of linear differential and integral operators (1950)","DOI":"10.6028\/jres.045.026"},{"issue":"4","key":"607_CR106","doi-asserted-by":"publisher","first-page":"1094","DOI":"10.1137\/0613066","volume":"13","author":"J Kuczy\u0144ski","year":"1992","unstructured":"Kuczy\u0144ski, J., Wo\u017aniakowski, H.: Estimating the largest eigenvalue by the power and lanczos algorithms with a random start. SIAM J. Matrix Anal. Appl. 13(4), 1094\u20131122 (1992)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"3\u20134","key":"607_CR107","doi-asserted-by":"publisher","first-page":"193","DOI":"10.1080\/02331939208843789","volume":"24","author":"F Dragomirescu","year":"1992","unstructured":"Dragomirescu, F., Ivan, C.: The smallest convex extensions of a convex function. Optimization 24(3\u20134), 193\u2013206 (1992)","journal-title":"Optimization"},{"issue":"4","key":"607_CR108","first-page":"965","volume":"21","author":"M Yan","year":"2014","unstructured":"Yan, M.: Extension of convex function. J. Convex Anal. 21(4), 965 (2014)","journal-title":"J. Convex Anal."},{"key":"607_CR109","volume-title":"Variational Analysis","author":"RT Rockafellar","year":"2009","unstructured":"Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis, vol. 317. Springer, Heidelberg, Berlin, New York (2009)"}],"container-title":["Computational Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00607-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10589-024-00607-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10589-024-00607-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,15]],"date-time":"2024-11-15T13:13:31Z","timestamp":1731676411000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10589-024-00607-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,26]]},"references-count":109,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["607"],"URL":"https:\/\/doi.org\/10.1007\/s10589-024-00607-2","relation":{},"ISSN":["0926-6003","1573-2894"],"issn-type":[{"value":"0926-6003","type":"print"},{"value":"1573-2894","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,26]]},"assertion":[{"value":"18 November 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 September 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 September 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}