{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:34:22Z","timestamp":1740123262492,"version":"3.37.3"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T00:00:00Z","timestamp":1661385600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T00:00:00Z","timestamp":1661385600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"publisher","award":["18H05291"],"award-info":[{"award-number":["18H05291"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001691","name":"Japan Society for the Promotion of Science","doi-asserted-by":"crossref","award":["20H05965"],"award-info":[{"award-number":["20H05965"]}],"id":[{"id":"10.13039\/501100001691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100002241","name":"Japan Science and Technology Agency","doi-asserted-by":"crossref","award":["JPMJER1903"],"award-info":[{"award-number":["JPMJER1903"]}],"id":[{"id":"10.13039\/501100002241","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Oper Res"],"published-print":{"date-parts":[[2023,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We present a polynomial-time online algorithm for maximizing the conditional value at risk (CVaR) of a monotone stochastic submodular function. Given<jats:italic>T<\/jats:italic>i.i.d. samples from an underlying distribution arriving online, our algorithm produces a sequence of solutions that converges to a (<jats:inline-formula><jats:alternatives><jats:tex-math>$$1-1\/e$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>1<\/mml:mn><mml:mo>-<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mi>e<\/mml:mi><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>)-approximate solution with a convergence rate of<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(T^{-1\/4})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>T<\/mml:mi><mml:mrow><mml:mo>-<\/mml:mo><mml:mn>1<\/mml:mn><mml:mo>\/<\/mml:mo><mml:mn>4<\/mml:mn><\/mml:mrow><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>for monotone continuous DR-submodular functions. Compared with previous offline algorithms, which require<jats:inline-formula><jats:alternatives><jats:tex-math>$$\\Omega (T)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>\u03a9<\/mml:mi><mml:mo>(<\/mml:mo><mml:mi>T<\/mml:mi><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>space, our online algorithm only requires<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{T})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msqrt><mml:mi>T<\/mml:mi><\/mml:msqrt><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>space. We extend our online algorithm to portfolio optimization for monotone submodular set functions under a matroid constraint. Experiments conducted on real-world datasets demonstrate that our algorithm can rapidly achieve CVaRs that are comparable to those obtained by existing offline algorithms.<\/jats:p>","DOI":"10.1007\/s10479-022-04835-9","type":"journal-article","created":{"date-parts":[[2022,8,25]],"date-time":"2022-08-25T20:02:31Z","timestamp":1661457751000},"page":"393-414","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online risk-averse submodular maximization"],"prefix":"10.1007","volume":"320","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9519-2487","authenticated-orcid":false,"given":"Tasuku","family":"Soma","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8919-8479","authenticated-orcid":false,"given":"Yuichi","family":"Yoshida","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,8,25]]},"reference":[{"key":"4835_CR1","unstructured":"Anari, N., Pokutta, S., & Tech, G. et\u00a0al. (2019). Structured robust submodular maximization: Offline and online algorithms. In AISTATS."},{"key":"4835_CR2","unstructured":"Bian, A. A., Mirzasoleiman, B., Buhmann, J. et\u00a0al. (2017). Guaranteed non-convex optimization: Submodular maximization over continuous domains (pp. 111\u2013120)."},{"key":"4835_CR3","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., & Feldman, M. (2018). Submodular functions maximization problems. In: Gonzalez, T. F. (Ed.), Handbook of approximation algorithms and metaheuristics (2nd ed., chap\u00a042).","DOI":"10.1201\/9781351236423-42"},{"issue":"6","key":"4835_CR4","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., P\u00e1l, M., et al. (2011). Maximizing a monotone submodular function subject to a matroid constraint. SIAM Journal on Computing, 40(6), 1740\u20131766.","journal-title":"SIAM Journal on Computing"},{"key":"4835_CR5","unstructured":"Cardoso, A. R., & Xu, H. (2019). Risk-averse stochastic convex bandit. In AISTATS (pp. 39\u201347)."},{"key":"4835_CR6","doi-asserted-by":"crossref","unstructured":"Cesa-Bianchi, N., Conconi, A., & Gentile, C. (2002). On the generalization ability of on-line learning algorithms. In NIPS (pp. 359\u2013366).","DOI":"10.7551\/mitpress\/1120.003.0051"},{"key":"4835_CR7","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Vondr\u00e1k, J., & Zenklusen, R. (2010). Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS (pp. 575\u2013584).","DOI":"10.1109\/FOCS.2010.60"},{"key":"4835_CR8","unstructured":"Chen, L., Hassani, H., & Karbasi, A. (2018). Online continuous submodular maximization. In AISTATS (pp. 1896\u20131905)."},{"key":"4835_CR9","unstructured":"Chen, R., Lucier, B., & Singer, Y. et\u00a0al. (2017). Robust optimization for non-convex objectives. In NIPS (pp. 4705\u20134714)."},{"key":"4835_CR10","unstructured":"Cohen, A., & Hazan, T. (2015). Following the perturbed leader for online structured learning. In ICML (pp. 1034\u20131042)."},{"key":"4835_CR11","unstructured":"Fujishige, S. (2005). Submodular functions and optimization (2nd ed.). Elsevier."},{"key":"4835_CR12","doi-asserted-by":"crossref","unstructured":"Golovin, D., Krause, A., & Streeter, M. (2014). Online submodular maximization under a matroid constraint with application to learning assignments. arXiv.","DOI":"10.1017\/CBO9781139177801.004"},{"key":"4835_CR13","unstructured":"Hassani, H., Soltanolkotabi, M., & Karbasi, A. (2017). Gradient methods for submodular maximization. In NIPS (pp. 5841\u20135851)."},{"key":"4835_CR14","doi-asserted-by":"crossref","unstructured":"Hazan, E. (2016). Introduction to online convex optimization. Foundations and Trends\u00ae in Optimization, 2(3\u20134), 157\u2013325.","DOI":"10.1561\/2400000013"},{"key":"4835_CR15","unstructured":"Karbasi, A., Hassani, H., & Mokhtari, A. et\u00a0al. (2019). Stochastic continuous greedy++: When upper and lower bounds match. In NeurIPS (pp. 13087\u201313097)."},{"key":"4835_CR16","unstructured":"Karimi, M. R., Lucic, M., & Hassani, H. et\u00a0al. (2017). Stochastic submodular maximization: The case of coverage functions. In NIPS."},{"key":"4835_CR17","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., & Tardos, \u00c9. (2003). Maximizing the spread of influence through a social network. In KDD (pp. 137\u2013146).","DOI":"10.1145\/956750.956769"},{"key":"4835_CR18","doi-asserted-by":"crossref","unstructured":"Krause, A., & Golovin, D. (2014). Submodular function maximization. In Tractability: Practical Approaches to Hard Problems (pp. 71\u2013104). Cambridge University Press.","DOI":"10.1017\/CBO9781139177801.004"},{"key":"4835_CR19","first-page":"2761","volume":"9","author":"A Krause","year":"2008","unstructured":"Krause, A., McMahan, B., Guestrin, C., et al. (2008). Robust submodular observation selection. Journal of Machine Learning Research, 9, 2761\u20132801.","journal-title":"Journal of Machine Learning Research"},{"key":"4835_CR20","doi-asserted-by":"publisher","first-page":"43","DOI":"10.21314\/JOR.2002.057","volume":"4","author":"P Krokhmal","year":"2002","unstructured":"Krokhmal, P., Palmquist, J., & Uryasev, S. (2002). Portfolio optimization with conditional value-at-risk objective and constraints. Journal of Risk, 4, 43\u201368.","journal-title":"Journal of Risk"},{"key":"4835_CR21","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Krause, A., & Guestrin, C. et\u00a0al (2007). Cost-effective outbreak detection in networks. In KDD (pp. 420\u2013429).","DOI":"10.1145\/1281192.1281239"},{"issue":"5","key":"4835_CR22","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1016\/j.orl.2015.08.001","volume":"43","author":"T Maehara","year":"2015","unstructured":"Maehara, T. (2015). Risk averse submodular utility maximization. Operations Research Letters, 43(5), 526\u2013529.","journal-title":"Operations Research Letters"},{"issue":"1","key":"4835_CR23","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1007\/s10479-006-0142-4","volume":"152","author":"R Mansini","year":"2007","unstructured":"Mansini, R., Ogryczak, W., & Speranza, M. G. (2007). Conditional value at risk and related linear programming models for portfolio optimization. Annals of Operations Research, 152(1), 227\u2013256.","journal-title":"Annals of Operations Research"},{"key":"4835_CR24","unstructured":"Mokhtari, A., Hassani, H., & Karbasi, A. (2018). Conditional gradient method for stochastic submodular maximization: Closing the gap. In AISTATS (pp. 1886\u20131895)."},{"key":"4835_CR25","doi-asserted-by":"crossref","unstructured":"Ohsaka, N., & Yoshida, Y. (2017). Portfolio optimization for influence spread. In WWW (pp. 977\u2013985).","DOI":"10.1145\/3038912.3052628"},{"issue":"6","key":"4835_CR26","doi-asserted-by":"publisher","first-page":"556","DOI":"10.1061\/(ASCE)0733-9496(2008)134:6(556)","volume":"134","author":"A Ostfeld","year":"2008","unstructured":"Ostfeld, A., Uber, J. G., Salomons, E., et al. (2008). The battle of the water sensor networks (BWSN): A design challenge for engineers and algorithms. Journal of Water Resources Planning and Management, 134(6), 556\u2013568.","journal-title":"Journal of Water Resources Planning and Management"},{"key":"4835_CR27","doi-asserted-by":"publisher","first-page":"21","DOI":"10.21314\/JOR.2000.038","volume":"2","author":"RT Rockafellar","year":"2000","unstructured":"Rockafellar, R. T., & Uryasev, S. (2000). Optimization of conditional value-at-risk. Journal of Risk, 2, 21\u201342.","journal-title":"Journal of Risk"},{"key":"4835_CR28","unstructured":"Roughgarden, T., & Wang, J. R. (2018). An optimal algorithm for online unconstrained submodular maximization. In COLT (pp. 1307\u20131325)."},{"key":"4835_CR29","doi-asserted-by":"crossref","unstructured":"Shapiro, A., Dentcheva, D., & Ruszczy\u0144ski, A. (2014). Lectures on stochastic programming: Modeling and theory. SIAM.","DOI":"10.1137\/1.9781611973433"},{"key":"4835_CR30","unstructured":"Soma, T. (2019). No-regret algorithms for online $$k$$-submodular maximization. In AISTATS (pp. 1205\u20131214)."},{"key":"4835_CR31","unstructured":"Soma, T., & Yoshida, Y. (2015). A generalization of submodular cover via the diminishing return property on the integer lattice. In NIPS (pp. 847\u2013855)."},{"key":"4835_CR32","doi-asserted-by":"publisher","unstructured":"Soma, T., & Yoshida, Y. (2021). Online risk-averse submodular maximization. In Proceedings of the 30th international joint conference on artificial intelligence (IJCAI) (pp. 2988\u20132994). https:\/\/doi.org\/10.24963\/ijcai.2021\/411","DOI":"10.24963\/ijcai.2021\/411"},{"key":"4835_CR33","unstructured":"Staib, M., Wilder, B., & Jegelka, S. (2019). Distributionally robust submodular maximization. In AISTATS (pp. 506\u2013516)."},{"key":"4835_CR34","doi-asserted-by":"crossref","unstructured":"Streeter, M., & Golovin, D. (2008). An online algorithm for maximizing submodular functions. In NIPS (pp. 1577\u20131584).","DOI":"10.21236\/ADA476748"},{"key":"4835_CR35","unstructured":"Streeter, M., Golovin, D., & Krause, A. (2009). Online learning of assignments. In NIPS (pp. 1794\u20131802)."},{"key":"4835_CR36","doi-asserted-by":"crossref","unstructured":"Suehiro, D., Hatano, K., & Kijima, S. et\u00a0al. (2012). Online prediction under submodular constraints. In International conference on algorithmic learning theory (pp. 260\u2013274). Springer.","DOI":"10.1007\/978-3-642-34106-9_22"},{"key":"4835_CR37","doi-asserted-by":"crossref","unstructured":"Tamar, A., Glassner, Y., & Mannor, S. (2015). Optimizing the CVaR via sampling. In AAAI.","DOI":"10.1609\/aaai.v29i1.9561"},{"issue":"1","key":"4835_CR38","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1137\/110832318","volume":"42","author":"J Vondr\u00e1k","year":"2013","unstructured":"Vondr\u00e1k, J. (2013). Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1), 265\u2013304.","journal-title":"SIAM Journal on Computing"},{"key":"4835_CR39","doi-asserted-by":"crossref","unstructured":"Wilder, B. (2018). Risk-sensitive submodular optimization. In AAAI (pp. 6451\u20136458).","DOI":"10.1609\/aaai.v32i1.12121"},{"issue":"1","key":"4835_CR40","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1016\/j.ijpe.2010.10.007","volume":"134","author":"S Yau","year":"2011","unstructured":"Yau, S., Kwon, R. H., Rogers, J. S., et al. (2011). Financial and operational decisions in the electricity sector: Contract portfolio optimization with the conditional value-at-risk criterion. International Journal of Production Economics, 134(1), 67\u201377.","journal-title":"International Journal of Production Economics"},{"key":"4835_CR41","unstructured":"Zhang, M., Chen, L., & Hassani, H. et\u00a0al. (2019). Online continuous submodular maximization: From full-information to bandit feedback. In NeurIPS (pp. 9210\u20139221)."}],"container-title":["Annals of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-022-04835-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10479-022-04835-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10479-022-04835-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,11,26]],"date-time":"2023-11-26T05:38:18Z","timestamp":1700977098000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10479-022-04835-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,25]]},"references-count":41,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["4835"],"URL":"https:\/\/doi.org\/10.1007\/s10479-022-04835-9","relation":{},"ISSN":["0254-5330","1572-9338"],"issn-type":[{"type":"print","value":"0254-5330"},{"type":"electronic","value":"1572-9338"}],"subject":[],"published":{"date-parts":[[2022,8,25]]},"assertion":[{"value":"13 June 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}