{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T11:14:10Z","timestamp":1772882050201,"version":"3.50.1"},"reference-count":41,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T00:00:00Z","timestamp":1702944000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T00:00:00Z","timestamp":1702944000000},"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"],"award-info":[{"award-number":["12131003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11771386"],"award-info":[{"award-number":["11771386"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12271278"],"award-info":[{"award-number":["12271278"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12131003"],"award-info":[{"award-number":["12131003"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["12001335"],"award-info":[{"award-number":["12001335"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Major Key Project of PCL","award":["PCL2022A05"],"award-info":[{"award-number":["PCL2022A05"]}]},{"name":"Major Key Project of PCL","award":["PCL2022A05"],"award-info":[{"award-number":["PCL2022A05"]}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["283106"],"award-info":[{"award-number":["283106"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s00453-023-01195-z","type":"journal-article","created":{"date-parts":[[2023,12,19]],"date-time":"2023-12-19T20:02:30Z","timestamp":1703016150000},"page":"1335-1364","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Stochastic Variance Reduction for DR-Submodular Maximization"],"prefix":"10.1007","volume":"86","author":[{"given":"Yuefang","family":"Lian","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xiao","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yang","family":"Zhou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,12,19]]},"reference":[{"key":"1195_CR1","unstructured":"Allen-Zhu, Z., Hazan, E.: Variance reduction for faster non-convex optimization. In: ICML, pp. 699\u2013707 (2016)"},{"key":"1195_CR2","doi-asserted-by":"publisher","first-page":"419","DOI":"10.1007\/s10107-018-1248-6","volume":"175","author":"Francis Bach","year":"2019","unstructured":"Bach, Francis: Submodular functions: from discrete to continuous domains. Math. Program. 175, 419\u2013459 (2019)","journal-title":"Math. Program."},{"key":"1195_CR3","unstructured":"Bian, A.A., Mirzasoleiman, B., Buhmann, J., Krause, A.: Guaranteed non-convex optimization: submodular maximization over continuous domains. In: AISTATS, pp. 111\u2013120 (2017)"},{"key":"1195_CR4","first-page":"487","volume":"30","author":"A Bian","year":"2017","unstructured":"Bian, A., Levy, K., Krause, A., Buhmann, J.M.: Continuous DR-submodular maximization: structure and algorithms. Adv. Neural. Inf. Process. Syst. 30, 487\u2013497 (2017)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"issue":"6","key":"1195_CR5","doi-asserted-by":"publisher","first-page":"1740","DOI":"10.1137\/080733991","volume":"40","author":"G Calinescu","year":"2011","unstructured":"Calinescu, G., Chekuri, C., Pal, M., Vondr\u00e1k, J.: Maximizing a monotone submodular function subject to a matroid constraint. SIAM J. Comput. 40(6), 1740\u20131766 (2011)","journal-title":"SIAM J. Comput."},{"key":"1195_CR6","doi-asserted-by":"crossref","unstructured":"Chekuri, C., Jayram, T., Vondr\u00e1k, J.: On multiplicative weight updates for concave and submodular function maximization. In: ITCS, pp. 201\u2013210 (2015)","DOI":"10.1145\/2688073.2688086"},{"issue":"6","key":"1195_CR7","doi-asserted-by":"publisher","first-page":"1831","DOI":"10.1137\/110839655","volume":"43","author":"Chandra Chekuri","year":"2014","unstructured":"Chekuri, Chandra, Vondr\u00e1k, Jan, Zenklusen, Rico: Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM J. Comput. 43(6), 1831\u20131879 (2014)","journal-title":"SIAM J. Comput."},{"key":"1195_CR8","first-page":"15157","volume":"32","author":"A Cutkosky","year":"2019","unstructured":"Cutkosky, A., Orabona, F.: Momentum-based variance reduction in non-convex SGD. Adv. Neural. Inf. Process. Syst. 32, 15157\u201315166 (2019)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1195_CR9","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, pp. 1\u20138 (2022)"},{"key":"1195_CR10","unstructured":"Du, D.: Lyapunov function approach for approximation algorithm design and analysis: with applications in submodular maximization. arXiv:2205.12442, pp. 1\u201330 (2022)"},{"key":"1195_CR11","doi-asserted-by":"crossref","unstructured":"D\u00fcrr, C., Thang, N.K., Srivastav, A., Tible, L.: Non-monotone DR-submodular maximization over general convex sets. In: IJCAI, pp. 2148\u20132154 (2021)","DOI":"10.24963\/ijcai.2020\/297"},{"key":"1195_CR12","first-page":"4045","volume":"30","author":"E Elenberg","year":"2017","unstructured":"Elenberg, E., Dimakis, A.G., Feldman, M., Karbasi, A.: Streaming weak submodularity: interpreting neural networks on the fly. Adv. Neural. Inf. Process. Syst. 30, 4045\u20134055 (2017)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1195_CR13","first-page":"689","volume":"31","author":"C Fang","year":"2018","unstructured":"Fang, C., Li, C.J., Lin, Z., Zhang, T.: Spider: near-optimal non-convex optimization via stochastic path-integrated differential estimator. Adv. Neural. Inf. Process. Syst. 31, 689\u2013699 (2018)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1195_CR14","doi-asserted-by":"crossref","unstructured":"Feldman, M., Naor, J., Schwartz, R.: A unified continuous greedy algorithm for submodular maximization. In: FOCS, pp. 570\u2013579 (2011)","DOI":"10.1109\/FOCS.2011.46"},{"issue":"3","key":"1195_CR15","doi-asserted-by":"publisher","first-page":"853","DOI":"10.1007\/s00453-020-00757-9","volume":"83","author":"Moran Feldman","year":"2021","unstructured":"Feldman, Moran: Guess free maximization of submodular and linear sums. Algorithmica 83(3), 853\u2013878 (2021)","journal-title":"Algorithmica"},{"key":"1195_CR16","doi-asserted-by":"crossref","unstructured":"Fisher, M.L., Nemhauser, G.L., Wolsey, L.A.: An analysis of approximations for maximizing submodular set functions\u2014II, pp. 73\u201387. Springer, Berlin, Heidelberg (1978)","DOI":"10.1007\/BFb0121195"},{"issue":"1\u20132","key":"1195_CR17","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. Log. 3(1\u20132), 95\u2013110 (1956)","journal-title":"Nav. Res. Log."},{"key":"1195_CR18","doi-asserted-by":"crossref","unstructured":"Guestrin, C., Krause, A., Singh, A.P.: Near-optimal sensor placements in Gaussian processes. In: ICML, pp. 265\u2013272 (2005)","DOI":"10.1145\/1102351.1102385"},{"key":"1195_CR19","first-page":"5842","volume":"30","author":"H Hassani","year":"2017","unstructured":"Hassani, H., Soltanolkotabi, M., Karbasi, A.: Gradient methods for submodular maximization. Adv. Neural. Inf. Process. Syst. 30, 5842\u20135852 (2017)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"issue":"4","key":"1195_CR20","doi-asserted-by":"publisher","first-page":"3315","DOI":"10.1137\/19M1304271","volume":"30","author":"H Hassani","year":"2020","unstructured":"Hassani, H., Karbasi, A., Mokhtari, A., Shen, Z.: Stochastic conditional gradient++: (non) convex minimization and continuous submodular maximization. SIAM J. Optim. 30(4), 3315\u20133344 (2020)","journal-title":"SIAM J. Optim."},{"key":"1195_CR21","unstructured":"Jaggi, M.: Revisiting Frank\u2013Wolfe: projection-free sparse convex optimization. In: ICML, pp. 427\u2013435 (2013)"},{"key":"1195_CR22","first-page":"315","volume":"26","author":"R Johnson","year":"2013","unstructured":"Johnson, R., Zhang, T.: Accelerating stochastic gradient descent using predictive variance reduction. Adv. Neural. Inf. Process. Syst. 26, 315\u2013323 (2013)","journal-title":"Adv. Neural. Inf. Process. Syst."},{"key":"1195_CR23","doi-asserted-by":"crossref","unstructured":"Kempe, D., Kleinberg, J., Tardos, \u00c9.: Maximizing the spread of influence through a social network. In: KDD, pp. 137\u2013146 (2003)","DOI":"10.1145\/956750.956769"},{"key":"1195_CR24","unstructured":"Les Mis\u00e9rables network dataset\u2014KONECT (2017). http:\/\/konect.cc\/networks\/moreno_lesmis"},{"key":"1195_CR25","doi-asserted-by":"crossref","unstructured":"Lian, Y., Xu, D., Du, D., Zhou, Y.: A stochastic non-monotone DR-submodular maximization problem over a convex set. In: COCOON, pp. 1\u201311 (2023)","DOI":"10.1007\/978-3-031-22105-7_1"},{"key":"1195_CR26","unstructured":"Lin, H., Bilmes, J.: A class of submodular functions for document summarization. In: ACL-HLT, pp. 510\u2013520 (2011)"},{"issue":"105","key":"1195_CR27","first-page":"1","volume":"21","author":"A Mokhtari","year":"2020","unstructured":"Mokhtari, A., Hassani, H., Karbasi, A.: Stochastic conditional gradient methods: from convex minimization to submodular maximization. J. Mach. Learn. Res. 21(105), 1\u201349 (2020)","journal-title":"J. Mach. Learn. Res."},{"issue":"1","key":"1195_CR28","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/BF01588971","volume":"14","author":"GL Nemhauser","year":"1978","unstructured":"Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions\u2014I. Math. Program. 14(1), 265\u2013294 (1978)","journal-title":"Math. Program."},{"key":"1195_CR29","unstructured":"Nguyen, L.M., Liu, J., Scheinberg, K., Tak\u00e1\u010d, M.: Sarah: a novel method for machine learning problems using stochastic recursive gradient. In: ICML, pp. 2613\u20132621 (2017)"},{"issue":"1","key":"1195_CR30","first-page":"4937","volume":"21","author":"Rad Niazadeh","year":"2020","unstructured":"Niazadeh, Rad, Roughgarden, Tim, Wang, Joshua R.: Optimal algorithms for continuous non-monotone submodular and DR-submodular maximization. J. Mach. Learn. Res. 21(1), 4937\u20134967 (2020)","journal-title":"J. Mach. Learn. Res."},{"key":"1195_CR31","doi-asserted-by":"crossref","unstructured":"Reddi, S.J., Hefny, A., Sra, S., P\u00f3czos, B., Smola, A.: Stochastic variance reduction for nonconvex optimization. In: ICML, pp. 314\u2013323 (2016)","DOI":"10.1109\/ALLERTON.2016.7852377"},{"key":"1195_CR32","unstructured":"Soma, T., Kakimura, N., Inaba, K., Kawarabayashi, K.-i.: Optimal budget allocation: theoretical guarantee and efficient algorithm. In: ICML, pp. 351\u2013359 (2014)"},{"key":"1195_CR33","doi-asserted-by":"crossref","unstructured":"Soma, T., Yoshida, Y.: Non-monotone DR-submodular function maximization. In: AAAI, vol. 31 (2017)","DOI":"10.1609\/aaai.v31i1.10653"},{"key":"1195_CR34","unstructured":"Staib, M., Jegelka, S.: Robust budget allocation via continuous submodular functions. In: ICML, pp. 3230\u20133240 (2017)"},{"issue":"1","key":"1195_CR35","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/S0167-6377(03)00062-2","volume":"32","author":"M Sviridenko","year":"2004","unstructured":"Sviridenko, M.: A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett. 32(1), 41\u201343 (2004)","journal-title":"Oper. Res. Lett."},{"key":"1195_CR36","unstructured":"Train bombing network dataset\u2014KONECT (2017). http:\/\/konect.cc\/networks\/moreno_train"},{"issue":"2","key":"1195_CR37","doi-asserted-by":"publisher","first-page":"1005","DOI":"10.1007\/s10107-020-01583-1","volume":"191","author":"Q Tran-Dinh","year":"2022","unstructured":"Tran-Dinh, Q., Pham, N.H., Phan, D.T., Nguyen, L.M.: A hybrid stochastic optimization framework for composite nonconvex optimization. Math. Program. 191(2), 1005\u20131071 (2022)","journal-title":"Math. Program."},{"key":"1195_CR38","doi-asserted-by":"crossref","unstructured":"Vondr\u00e1k, J.: Optimal approximation for the submodular welfare problem in the value oracle model. In: STOC, pp. 67\u201374 (2008)","DOI":"10.1145\/1374376.1374389"},{"key":"1195_CR39","unstructured":"Windsurfers network dataset\u2014KONECT (2017). http:\/\/konect.cc\/networks\/moreno_beach"},{"key":"1195_CR40","unstructured":"Zhang, Q., Deng, Z., Chen, Z., Hu, H., Yang, Y.: Stochastic continuous submodular maximization: boosting via non-oblivious function. In: ICML, pp. 26116\u201326134 (2022)"},{"key":"1195_CR41","unstructured":"Zhang, M., Shen, Z., Mokhtari, A., Hassani, H., Karbasi, A.: One sample stochastic Frank\u2013Wolfe. In: AISTATS, pp. 4012\u20134023 (2020)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01195-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01195-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01195-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,21]],"date-time":"2024-04-21T03:02:01Z","timestamp":1713668521000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01195-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,12,19]]},"references-count":41,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1195"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01195-z","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,12,19]]},"assertion":[{"value":"30 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 December 2023","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 known competing financial, non-financial interests or personal relationships that could have appeared to influence the work reported in this paper.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}