{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:21:19Z","timestamp":1740122479503,"version":"3.37.3"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T00:00:00Z","timestamp":1718236800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12131003","12271278"],"award-info":[{"award-number":["12131003","12271278"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"the Major Key Project of PCL","award":["PCL2022A05"],"award-info":[{"award-number":["PCL2022A05"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Glob Optim"],"published-print":{"date-parts":[[2024,11]]},"DOI":"10.1007\/s10898-024-01413-0","type":"journal-article","created":{"date-parts":[[2024,6,13]],"date-time":"2024-06-13T02:01:22Z","timestamp":1718244082000},"page":"619-649","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Online non-monotone diminishing return submodular maximization in the bandit setting"],"prefix":"10.1007","volume":"90","author":[{"given":"Jiachen","family":"Ju","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3492-9235","authenticated-orcid":false,"given":"Xiao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,6,13]]},"reference":[{"issue":"2","key":"1413_CR1","doi-asserted-by":"publisher","first-page":"348","DOI":"10.1109\/18.485708","volume":"42","author":"TM Cover","year":"2006","unstructured":"Cover, T.M., Ordentlich, E.: Universal portfolios with side information. IEEE Trans. Inf. Theory 42(2), 348\u2013363 (2006). https:\/\/doi.org\/10.1109\/18.485708","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1\u20132","key":"1413_CR2","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1006\/game.1999.0740","volume":"29","author":"DP Foster","year":"1999","unstructured":"Foster, D.P., Vohra, R.: Regret in the on-line decision problem. Games Econ. Behav. 29(1\u20132), 7\u201335 (1999). https:\/\/doi.org\/10.1006\/game.1999.0740","journal-title":"Games Econ. Behav."},{"issue":"1","key":"1413_CR3","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1007\/s10994-005-0465-4","volume":"59","author":"G Stoltz","year":"2005","unstructured":"Stoltz, G., Lugosi, G.: Internal regret in on-line portfolio selection. Mach. Learn. 59(1), 125\u2013159 (2005). https:\/\/doi.org\/10.1007\/s10994-005-0465-4","journal-title":"Mach. Learn."},{"issue":"4","key":"1413_CR4","doi-asserted-by":"publisher","first-page":"1505","DOI":"10.1137\/16M1117317","volume":"47","author":"D Chakrabarty","year":"2018","unstructured":"Chakrabarty, D., Ene, A., Krishnaswamy, R., Panigrahi, D.: Online buy-at-bulk network design. SIAM J. Comput. 47(4), 1505\u20131528 (2018). https:\/\/doi.org\/10.1137\/16M1117317","journal-title":"SIAM J. Comput."},{"issue":"3","key":"1413_CR5","doi-asserted-by":"publisher","first-page":"3276","DOI":"10.1109\/TNSM.2022.3159670","volume":"19","author":"A Nouruzi","year":"2022","unstructured":"Nouruzi, A., Zakeri, A., Javan, M.R., Mokari, N., Hussain, R., Kazmi, S.M.A.: Online service provisioning in NFV-enabled networks using deep reinforcement learning. IEEE Trans. Netw. Service Manag. 19(3), 3276\u20133289 (2022). https:\/\/doi.org\/10.1109\/TNSM.2022.3159670","journal-title":"IEEE Trans. Netw. Service Manag."},{"key":"1413_CR6","unstructured":"Edmonds, J.: Submodular Functions, Matroids, and Certain Polyhedra, R. Guy, H. Hanani, N. Sauer, and J. Sch\u00f6nheim edn., pp. 69\u201387. Gordon and Breach, New York (1970)"},{"issue":"1","key":"1413_CR7","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1137\/110821433","volume":"28","author":"D Chakrabarty","year":"2014","unstructured":"Chakrabarty, D., Goel, G., Vazirani, V.V., Wang, L., Yu, C.: Submodularity helps in Nash and nonsymmetric bargaining games. SIAM J. Discret Math. 28(1), 99\u2013115 (2014). https:\/\/doi.org\/10.1137\/110821433","journal-title":"SIAM J. Discret Math."},{"key":"1413_CR8","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1016\/j.ress.2018.11.010","volume":"183","author":"C Malings","year":"2019","unstructured":"Malings, C., Pozzi, M.: Submodularity issues in value-of-information-based sensor placement. Reliab. Eng. Syst. Saf. 183, 93\u2013103 (2019). https:\/\/doi.org\/10.1016\/j.ress.2018.11.010","journal-title":"Reliab. Eng. Syst. Saf."},{"issue":"3","key":"1413_CR9","doi-asserted-by":"publisher","first-page":"420","DOI":"10.1007\/s10489-012-0336-1","volume":"37","author":"J Li","year":"2019","unstructured":"Li, J., Li, L., Li, T.: Multi-document summarization via submodularity. Appl. Intell. 37(3), 420\u2013430 (2019). https:\/\/doi.org\/10.1007\/s10489-012-0336-1","journal-title":"Appl. Intell."},{"issue":"2","key":"1413_CR10","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/s10898-021-01076-1","volume":"82","author":"C Gao","year":"2022","unstructured":"Gao, C., Gu, S., Yu, J., Du, H., Wu, W.: Adaptive seeding for profit maximization in social networks. J. Glob. Optim. 82(2), 413\u2013432 (2022). https:\/\/doi.org\/10.1007\/s10898-021-01076-1","journal-title":"J. Glob. Optim."},{"issue":"3","key":"1413_CR11","doi-asserted-by":"publisher","first-page":"1128","DOI":"10.1016\/j.ejor.2023.04.024","volume":"310","author":"TT Dam","year":"2023","unstructured":"Dam, T.T., Ta, T.A., Mai, T.: Robust maximum capture facility location under random utility maximization models. Eur. J. Oper. Res. 310(3), 1128\u20131150 (2023). https:\/\/doi.org\/10.1016\/j.ejor.2023.04.024","journal-title":"Eur. J. Oper. Res."},{"key":"1413_CR12","unstructured":"Bian, A.A., Mirzasoleiman, B., Buhmann, J., Krause, A.: Guaranteed non-convex optimization: submodular maximization over continuous domains. In: Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, pp. 111\u2013120 (2017). https:\/\/proceedings.mlr.press\/v54\/bian17a.html"},{"key":"1413_CR13","doi-asserted-by":"publisher","unstructured":"Bian, S., Guo, Q., Wang, S., Yu, J.X.: Efficient algorithms for budgeted influence maximization on massive social networks. In: Proceedings of the 46th International Conference on Very Large Data Bases, pp. 1498\u20131510 (2020). https:\/\/doi.org\/10.14778\/3397230.3397244","DOI":"10.14778\/3397230.3397244"},{"key":"1413_CR14","unstructured":"Bian, Y., Buhmann, J., Krause, A.: Optimal continuous DR-submodular maximization and applications to provable mean field inference. In: Proceedings of the 36th International Conference on Machine Learning, pp. 644\u2013653 (2019). https:\/\/proceedings.mlr.press\/v97\/bian19a.html"},{"key":"1413_CR15","doi-asserted-by":"publisher","unstructured":"Wu, H.-H., K\u00fc\u00e7\u00fckyavuz, S.: Probabilistic partial set covering with an oracle for chance constraints. SIAM J. Optim. 29(1), 690\u2013718 (2019). https:\/\/doi.org\/10.1137\/17M1141576","DOI":"10.1137\/17M1141576"},{"key":"1413_CR16","unstructured":"Chen, L., Hassani, H., Karbasi, A.: Online continuous submodular maximization. In: Proceedings of the 31st International Conference on Artificial Intelligence and Statistics, pp. 1896\u20131905 (2018). http:\/\/proceedings.mlr.press\/v84\/chen18f.html"},{"key":"1413_CR17","unstructured":"Th$${\\acute{\\breve{{\\rm a}}}}$$ng, N.K., Srivastav, A.: Online non-monotone DR-submodular maximization. arXiv:1909.11426 (2019) https:\/\/arxiv.org\/abs\/1909.11426"},{"key":"1413_CR18","doi-asserted-by":"publisher","unstructured":"Hazan, E.: Introduction to online convex optimization. Foundations and Trends\u00ae in Optimization 2(3-4), 157\u2013325 (2016). https:\/\/doi.org\/10.1561\/2400000013","DOI":"10.1561\/2400000013"},{"key":"1413_CR19","doi-asserted-by":"publisher","unstructured":"Bian, A., Levy, K.Y., Krause, A., Buhmann, J.M.: Continuous DR-submodular maximization: structure and algorithms. In: Proceedings of the 31st Conference on Neural Information Processing Systems, pp. 486\u2013496 (2017). https:\/\/doi.org\/10.5555\/3294771.3294818","DOI":"10.5555\/3294771.3294818"},{"key":"1413_CR20","unstructured":"Du, D., Liu, Z., Wu, C., Xu, D., Zhou, Y.: An improved approximation algorithm for maximizing a DR-submodular function over a convex set. arXiv:2203.14740 (2022)"},{"key":"1413_CR21","doi-asserted-by":"publisher","unstructured":"Streeter, M., Golovin, D.: An online algorithm for maximizing submodular functions. In: Proceedings of the 21st International Conference on Neural Information Processing Systems, pp. 1577\u20131584 (2008). https:\/\/doi.org\/10.5555\/2981780.2981977","DOI":"10.5555\/2981780.2981977"},{"key":"1413_CR22","doi-asserted-by":"publisher","unstructured":"Zhang, M., Chen, L., Hassani, H., Karbasi, A.: Online continuous submodular maximization: from full-information to bandit feedback. In: Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 9210\u20139221 (2019). https:\/\/doi.org\/10.5555\/3454287.3455113","DOI":"10.5555\/3454287.3455113"},{"key":"1413_CR23","unstructured":"Mualem, L., Feldman, M.: Resolving the approximability of offline and online non-monotone DR-submodular maximization over general convex sets. In: Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pp. 2542\u20132564 (2023). https:\/\/proceedings.mlr.press\/v206\/mualem23a.html"},{"key":"1413_CR24","doi-asserted-by":"publisher","unstructured":"Zhu, J., Wu, Q., Zhang, M., Zheng, R., Li, K.: Projection-free decentralized online learning for submodular maximization over time-varying networks. J. Mach. Learn. Res. 22(1), 2328\u20132369 (2021). https:\/\/doi.org\/10.5555\/3546258.3546309","DOI":"10.5555\/3546258.3546309"},{"key":"1413_CR25","unstructured":"Mokhtari, A., Hassani, H., Karbasi, A.: Decentralized submodular maximization: bridging discrete and continuous settings. In: Proceedings of the 35th International Conference on Machine Learning, pp. 3616\u20133625 (2018). http:\/\/proceedings.mlr.press\/v80\/mokhtari18a.html"},{"key":"1413_CR26","doi-asserted-by":"publisher","unstructured":"Flaxman, A.D., Kalai, A.T., McMahan, H.B.: Online convex optimization in the bandit setting: gradient descent without a gradient. In: Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 385\u2013394 (2005). https:\/\/doi.org\/10.5555\/1070432.1070486","DOI":"10.5555\/1070432.1070486"},{"key":"1413_CR27","unstructured":"Mokhtari, A., Hassani, H., Karbasi, A.: Conditional gradient method for stochastic submodular maximization: closing the gap. In: Proceedings of the 21st International Conference on Artificial Intelligence and Statistics, pp. 1886\u20131895 (2018). http:\/\/proceedings.mlr.press\/v84\/mokhtari18a.html"},{"key":"1413_CR28","doi-asserted-by":"publisher","unstructured":"Mokhari, A., Hassani, H., Karbasi, A.: Stochastic conditional gradient methods: from convex minimization to submodular maximization. J. Mach. Learn. Res. 21(1), 4232\u20134280 (2020). https:\/\/doi.org\/10.5555\/3455716.3455821","DOI":"10.5555\/3455716.3455821"},{"key":"1413_CR29","unstructured":"Zhang, Q., Deng, Z., Chen, Z., Zhou, K., Hu, H., Yang, Y.: Online learning for non-monotone submodular maximization: from full information to bandit feedback. In: Proceedings of the 26th International Conference on Artificial Intelligence and Statistics, pp. 3515\u20133537 (2023). https:\/\/proceedings.mlr.press\/v206\/zhang23f.html"},{"key":"1413_CR30","unstructured":"Nguyen, T.-A., Th$$\\acute{\\breve{{\\rm a}}}$$ng, N.K., Trystram, D.: One gradient Frank-Wolfe for decentralized online convex and submodular optimization. In: Proceedings of the 14th Asian Conference on Machine Learning, pp. 802\u2013815 (2023). https:\/\/proceedings.mlr.press\/v189\/nguyen23a.html"},{"key":"1413_CR31","doi-asserted-by":"publisher","unstructured":"Hassani, H., Soltanolkotabi, M., Karbasi, A.: Gradient methods for submodular maximization. In: Proceedings of the 31st International Conference on Neural Information Processing Systems, pp. 5843\u20135853 (2017). https:\/\/doi.org\/10.5555\/3295222.3295334","DOI":"10.5555\/3295222.3295334"},{"key":"1413_CR32","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Jayram, T.S., Vondr\u00e1k, J.: On multiplicative weight updates for concave and submodular function maximization. In: Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pp. 201\u2013210 (2015). https:\/\/doi.org\/10.1145\/2688073.2688086","DOI":"10.1145\/2688073.2688086"},{"key":"1413_CR33","doi-asserted-by":"publisher","unstructured":"Shalev-Shwartz, S.: Online learning and online convex optimization. Foundations and Trends\u00ae in Machine Learning 4(2), 107\u2013194 (2012). https:\/\/doi.org\/10.1561\/2200000018","DOI":"10.1561\/2200000018"},{"key":"1413_CR34","unstructured":"Chen, L., Zhang, M., Hassani, H., Karbasi, A.: Black box submodular maximization: discrete and continuous settings. In: Proceedings of the 23rd International Conference on Artificial Intelligence and Statistics, pp. 1058\u20131070 (2020). https:\/\/proceedings.mlr.press\/v108\/chen20c.html"}],"container-title":["Journal of Global Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01413-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10898-024-01413-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10898-024-01413-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,16]],"date-time":"2024-10-16T10:03:36Z","timestamp":1729073016000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10898-024-01413-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,13]]},"references-count":34,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,11]]}},"alternative-id":["1413"],"URL":"https:\/\/doi.org\/10.1007\/s10898-024-01413-0","relation":{},"ISSN":["0925-5001","1573-2916"],"issn-type":[{"type":"print","value":"0925-5001"},{"type":"electronic","value":"1573-2916"}],"subject":[],"published":{"date-parts":[[2024,6,13]]},"assertion":[{"value":"31 July 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 May 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 June 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaration"}},{"value":"This research was partially supported by the National Natural Science Foundation of China (Nos. 12131003, 12271278), the Major Key Project of PCL (No. PCL2022A05) and the Talent Program of Guangdong Province (No. 2021QN02X160). The authors have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Statements & Declarations"}}]}}