{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T10:00:55Z","timestamp":1775296855101,"version":"3.50.1"},"reference-count":53,"publisher":"Wiley","issue":"1","license":[{"start":{"date-parts":[[2018,12,5]],"date-time":"2018-12-05T00:00:00Z","timestamp":1543968000000},"content-version":"vor","delay-in-days":338,"URL":"http:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U1604155"],"award-info":[{"award-number":["U1604155"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61602155"],"award-info":[{"award-number":["61602155"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61871430"],"award-info":[{"award-number":["61871430"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61772477"],"award-info":[{"award-number":["61772477"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61572445"],"award-info":[{"award-number":["61572445"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004773","name":"Henan University","doi-asserted-by":"publisher","award":["19zx010"],"award-info":[{"award-number":["19zx010"]}],"id":[{"id":"10.13039\/501100004773","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004262","name":"Zhengzhou University of Light Industry","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004262","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006407","name":"Natural Science Foundation of Henan Province","doi-asserted-by":"publisher","award":["162300410322"],"award-info":[{"award-number":["162300410322"]}],"id":[{"id":"10.13039\/501100006407","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["onlinelibrary.wiley.com"],"crossmark-restriction":true},"short-container-title":["Complexity"],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>\n                    We consider a stochastic continuous submodular huge\u2010scale optimization problem, which arises naturally in many applications such as machine learning. Due to high\u2010dimensional data, the computation of the whole gradient vector can become prohibitively expensive. To reduce the complexity and memory requirements, we propose a stochastic block\u2010coordinate gradient projection algorithm for maximizing continuous submodular functions, which chooses a random subset of gradient vector and updates the estimates along the positive gradient direction. We prove that the estimates of all nodes generated by the algorithm converge to some stationary points with probability 1. Moreover, we show that the proposed algorithm achieves the tight ((\n                    <jats:italic>p<\/jats:italic>\n                    <jats:sub>min<\/jats:sub>\n                    \/2)\n                    <jats:italic>F<\/jats:italic>\n                    <jats:sup>\u204e<\/jats:sup>\n                    \u2212\n                    <jats:italic>\u03f5<\/jats:italic>\n                    ) approximation guarantee after\n                    <jats:italic>O<\/jats:italic>\n                    (1\/\n                    <jats:italic>\u03f5<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    ) iterations for DR\u2010submodular functions by choosing appropriate step sizes. Furthermore, we also show that the algorithm achieves the tight ((\n                    <jats:italic>\u03b3<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    \/(1 +\n                    <jats:italic>\u03b3<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    ))\n                    <jats:italic>p<\/jats:italic>\n                    <jats:sub>min<\/jats:sub>\n                    <jats:italic>F<\/jats:italic>\n                    <jats:sup>\u204e<\/jats:sup>\n                    \u2212\n                    <jats:italic>\u03f5<\/jats:italic>\n                    ) approximation guarantee after\n                    <jats:italic>O<\/jats:italic>\n                    (1\/\n                    <jats:italic>\u03f5<\/jats:italic>\n                    <jats:sup>2<\/jats:sup>\n                    ) iterations for weakly DR\u2010submodular functions with parameter\n                    <jats:italic>\u03b3<\/jats:italic>\n                    by choosing diminishing step sizes.\n                  <\/jats:p>","DOI":"10.1155\/2018\/2609471","type":"journal-article","created":{"date-parts":[[2018,12,5]],"date-time":"2018-12-05T18:30:36Z","timestamp":1544034636000},"update-policy":"https:\/\/doi.org\/10.1002\/crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Stochastic Block\u2010Coordinate Gradient Projection Algorithms for Submodular Maximization"],"prefix":"10.1155","volume":"2018","author":[{"given":"Zhigang","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2523-1089","authenticated-orcid":false,"given":"Mingchuan","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6411-7035","authenticated-orcid":false,"given":"Junlong","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0932-8788","authenticated-orcid":false,"given":"Ruijuan","family":"Zheng","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6117-5686","authenticated-orcid":false,"given":"Qikun","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1572-5293","authenticated-orcid":false,"given":"Qingtao","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"311","published-online":{"date-parts":[[2018,12,5]]},"reference":[{"key":"e_1_2_10_1_2","unstructured":"DjolongaJ.andKrauseA. From MAP to marginals: Variational inference in Bayesian submodular models Proceedings of the 28th Annual Conference on Neural Information Processing Systems 2014 NIPS 2014 December 2014 Canada 244\u2013252 2-s2.0-84937925250."},{"key":"e_1_2_10_2_2","unstructured":"IyerR.andBilmesJ. Submodular point processes with applications to machine learning Proceedings of the in Proceedings of the 18th International Conference on Artificial Intelligence and Statistics 2015 388\u2013397."},{"key":"e_1_2_10_3_2","unstructured":"SinglaA. BogunovicI. KarbasiA. andKrauseA. Near-optimally teaching the crowd to classify Proceedings of the 31st International Conference on Machine Learning 2014 154\u2013162."},{"key":"e_1_2_10_4_2","unstructured":"KimB. KhannaR. andKoyejoO. Examples are not enough learn to criticize! Criticism for interpretability Proceedings of the 30th Annual Conference on Neural Information Processing Systems NIPS 2016 December 2016 Spain 2288\u20132296 2-s2.0-85018898116."},{"key":"e_1_2_10_5_2","doi-asserted-by":"publisher","DOI":"10.1109\/jstsp.2011.2161862"},{"key":"e_1_2_10_6_2","unstructured":"MirzasoleimanB. KarbasiA. SarkarR. andKrauseA. Distributed submodular maximization: Identifying representative elements in massive data Proceedings of the 27th Annual Conference on Neural Information Processing Systems NIPS 2013 December 2013 USA 2-s2.0-84898931932."},{"key":"e_1_2_10_7_2","unstructured":"LinH.andBilmesJ. A class of submodular functions for document summarization Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies ACL-HLT 2011 June 2011 USA 510\u2013520 2-s2.0-84859070008."},{"key":"e_1_2_10_8_2","first-page":"2483","volume-title":"Advances in Neural Information Processing Systems","author":"Yue Y.","year":"2011"},{"key":"e_1_2_10_9_2","doi-asserted-by":"crossref","unstructured":"El-AriniK. VedaG. ShahafD. andGuestrinC. Turning down the noise in the blogosphere Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining KDD \u203209 July 2009 France 289\u2013297 2-s2.0-70350668602.","DOI":"10.1145\/1557019.1557056"},{"key":"e_1_2_10_10_2","unstructured":"MirzasoleimanB. BadanidiyuruA. andKarbasiA. FAst coNsTrained submodular maximization: Personalized data summarization Proceedings of the 33rd International Conference on Machine Learning ICML 2016 June 2016 USA 2042\u20132054 2-s2.0-84998704955."},{"key":"e_1_2_10_11_2","doi-asserted-by":"crossref","unstructured":"GuestrinC. KrauseA. andSinghA. P. Near-optimal sensor placements in gaussian processes Proceedings of the ICML 2005: 22nd International Conference on Machine Learning August 2005 265\u2013272 https:\/\/doi.org\/10.1145\/1102351.1102385 2-s2.0-31844450884.","DOI":"10.1145\/1102351.1102385"},{"key":"e_1_2_10_12_2","doi-asserted-by":"crossref","unstructured":"LeskovecJ. KrauseA. GuestrinC. FaloutsosC. VanbriesenJ. andGlanceN. Cost-effective outbreak detection in networks Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD \u203207) August 2007 New York NY USA 420\u2013429 https:\/\/doi.org\/10.1145\/1281192.1281239 2-s2.0-36849083014.","DOI":"10.1145\/1281192.1281239"},{"key":"e_1_2_10_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/2086737.2086741"},{"key":"e_1_2_10_14_2","first-page":"118","volume-title":"Advances in Neural Information Processing Systems","author":"Bach F.","year":"2010"},{"key":"e_1_2_10_15_2","unstructured":"NarasimhanM. JojicN. andBilmesJ. Q-clustering Proceedings of the 2005 Annual Conference on Neural Information Processing Systems NIPS 2005 December 2005 Canada 979\u2013986 2-s2.0-78649332845."},{"key":"e_1_2_10_16_2","unstructured":"DasA.andKempeD. Submodular meets spectral: Greedy algorithms for subset selection sparse approximation and dictionary selection Proceedings of the 28th International Conference on Machine Learning ICML 2011 July 2011 USA 1057\u20131064 2-s2.0-80053452142."},{"key":"e_1_2_10_17_2","first-page":"427","article-title":"Adaptive submodularity: theory and applications in active learning and stochastic optimization","volume":"42","author":"Golovin D.","year":"2011","journal-title":"Journal of Artificial Intelligence Research"},{"key":"e_1_2_10_18_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2014.2321683"},{"key":"e_1_2_10_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502096"},{"key":"e_1_2_10_20_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0189-2"},{"key":"e_1_2_10_21_2","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.1989"},{"key":"e_1_2_10_22_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.23.8.789"},{"key":"e_1_2_10_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/bf01588971"},{"key":"e_1_2_10_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/bfb0121195"},{"key":"e_1_2_10_25_2","doi-asserted-by":"publisher","DOI":"10.1137\/090779346"},{"key":"e_1_2_10_26_2","doi-asserted-by":"publisher","DOI":"10.1137\/110839655"},{"key":"e_1_2_10_27_2","doi-asserted-by":"publisher","DOI":"10.1137\/080733991"},{"key":"e_1_2_10_28_2","doi-asserted-by":"crossref","unstructured":"BachF. Submodular functions: from discrete to continuous domains https:\/\/arxiv.org\/abs\/1511.00394v2 https:\/\/doi.org\/10.1007\/s10107-018-1248-6.","DOI":"10.1007\/s10107-018-1248-6"},{"key":"e_1_2_10_29_2","unstructured":"BianA. MirzasoleimanB. BuhmannJ. andKrauseA. Guaranteed non-convex optimization: Submodular maximization over continuous domains https:\/\/arxiv.org\/abs\/1606.05615."},{"key":"e_1_2_10_30_2","first-page":"6853","volume-title":"Advances in Neural Information Processing Systems","author":"Karimi M.","year":"2017"},{"key":"e_1_2_10_31_2","unstructured":"HassaniH. SoltanolkotabiM. andKarbasiA. Gradient methods for submodular maximization https:\/\/arxiv.org\/abs\/1708.03949."},{"key":"e_1_2_10_32_2","volume-title":"Nonlinear Programming","author":"Bertsekas D. P.","year":"1999"},{"key":"e_1_2_10_33_2","first-page":"1369","article-title":"Coordinate descent method for large-scale L2-loss linear support vector machines","volume":"9","author":"Chang K.-W.","year":"2008","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"e_1_2_10_34_2","doi-asserted-by":"publisher","DOI":"10.1137\/100808563"},{"key":"e_1_2_10_35_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-007-0170-0"},{"key":"e_1_2_10_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-008-9458-3"},{"key":"e_1_2_10_37_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10589-009-9251-8"},{"key":"e_1_2_10_38_2","doi-asserted-by":"publisher","DOI":"10.1110\/ps.0242703"},{"key":"e_1_2_10_39_2","doi-asserted-by":"publisher","DOI":"10.1214\/07-AOAS147"},{"key":"e_1_2_10_40_2","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2009.3.487"},{"key":"e_1_2_10_41_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00939948"},{"key":"e_1_2_10_42_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017501703105"},{"key":"e_1_2_10_43_2","first-page":"1523","article-title":"Iteration complexity of feasible descent methods for convex optimization","volume":"15","author":"Wang P.-W.","year":"2014","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"e_1_2_10_44_2","doi-asserted-by":"publisher","DOI":"10.1137\/100802001"},{"key":"e_1_2_10_45_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-012-0614-z"},{"key":"e_1_2_10_46_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-014-0800-2"},{"key":"e_1_2_10_47_2","first-page":"285","article-title":"An asynchronous parallel stochastic coordinate descent algorithm","volume":"16","author":"Liu J.","year":"2015","journal-title":"Journal of Machine Learning Research (JMLR)"},{"key":"e_1_2_10_48_2","doi-asserted-by":"publisher","DOI":"10.1137\/140961134"},{"key":"e_1_2_10_49_2","series-title":"Annals of Discrete Mathematics","volume-title":"Submodular functions and optimization","author":"Fujishige S.","year":"2005"},{"key":"e_1_2_10_50_2","doi-asserted-by":"crossref","unstructured":"ChekuriC. JayramT. S. andVondrakJ. On multiplicative weight updates for concave and submodular function maximization Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science ACM 201\u2013210 MR3419010.","DOI":"10.1145\/2688073.2688086"},{"key":"e_1_2_10_51_2","volume-title":"Introduction to Optimization","author":"Polyak B. T.","year":"1987"},{"key":"e_1_2_10_52_2","doi-asserted-by":"crossref","unstructured":"SinghC. NedicA. andSrikantR. Random block-coordinate gradient projection algorithms Proceedings of the 2014 53rd IEEE Annual Conference on Decision and Control CDC 2014 December 2014 USA 185\u2013190 2-s2.0-84988227804.","DOI":"10.1109\/CDC.2014.7039379"},{"key":"e_1_2_10_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993740"}],"container-title":["Complexity"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2018\/2609471.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/downloads.hindawi.com\/journals\/complexity\/2018\/2609471.xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1155\/2018\/2609471","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T09:26:53Z","timestamp":1775294813000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1155\/2018\/2609471"}},"subtitle":[],"editor":[{"given":"Mahardhika","family":"Pratama","sequence":"additional","affiliation":[],"role":[{"role":"editor","vocabulary":"crossref"}]}],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":53,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1155\/2018\/2609471"],"URL":"https:\/\/doi.org\/10.1155\/2018\/2609471","archive":["Portico"],"relation":{},"ISSN":["1076-2787","1099-0526"],"issn-type":[{"value":"1076-2787","type":"print"},{"value":"1099-0526","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]},"assertion":[{"value":"2018-05-25","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-11-26","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-12-05","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}],"article-number":"2609471"}}