# American Institute of Mathematical Sciences

• Previous Article
Approach to the consistency and consensus of Pythagorean fuzzy preference relations based on their partial orders in group decision making
• JIMO Home
• This Issue
• Next Article
The optimal solution to a principal-agent problem with unknown agent ability
September  2021, 17(5): 2607-2614. doi: 10.3934/jimo.2020085

## Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization

 1 Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, P.R. China 2 School of Mathematics and Statistics, Shandong Normal University, Jinan 250014, P.R. China 3 Department of Operations Research and Scientific Computing, Beijing University of Technology, Beijing 100124, P.R. China 4 School of Computer Science and Technology, Shandong Jianzhu University, Jinan 250101, P.R. China

* Corresponding author: Dongmei Zhang

Received  October 2019 Revised  January 2020 Published  September 2021 Early access  April 2020

The problem of maximizing a given set function with a cardinality constraint has widespread applications. A number of algorithms have been provided to solve the maximization problem when the set function is monotone and submodular. However, reality-based set functions may not be submodular and may involve large-scale and noisy data sets. In this paper, we present the Stochastic-Lazier-Greedy Algorithm (SLG) to solve the corresponding non-submodular maximization problem and offer a performance guarantee of the algorithm. The guarantee is related to a submodularity ratio, which characterizes the closeness of to submodularity. Our algorithm also can be viewed as an extension of several previous greedy algorithms.

Citation: Lu Han, Min Li, Dachuan Xu, Dongmei Zhang. Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial and Management Optimization, 2021, 17 (5) : 2607-2614. doi: 10.3934/jimo.2020085
##### References:
 [1] A. Dasgupta, R. Kumar and S. Ravi, Summarization through submodularity and dispersion, Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, (2013), 1014–1022. [2] A. Das and D. Kempe, Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection, Proceedings of the 28th International Conference on International Conference on Machine Learning, (2011), 1057–1064. [3] K. El-Arini and C. Guestrin, Beyond keyword search: Discovering relevant scientific literature, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2011), 439–447. [4] U. Feige, A threshold of $\ln n$ for approximating set cover, Journal of the ACM, 45 (1998), 634-652.  doi: 10.1145/285055.285059. [5] D. Golovin and A. Krause, Adaptive submodularity: Theory and applications in active learning and stochastic optimization, Journal of Artificial Intelligence Research, 42 (2011), 427-486. [6] R. Gomes and A. Krause, Budgeted nonparametric learning from data streams, Proceedings of the 27th International Conference on International Conference on Machine Learning, (2010), 391–398. [7] A. Guillory and J. Bilmes, Active semi-supervised learning using submodular functions, Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, (2011), 274–282. [8] A. Hassidim and Y. Singer, Robust guarantees of stochastic greedy algorithms, Proceedings of the 34th International Conference on Machine Learning, (2017), 1424–1432. [9] D. Kempe, J. Kleinberg and É. Tardos, Maximizing the spread of influence through a social network, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2003), 137–146. [10] Khanna, E. Elenberg, A. Dimakis, S. Negahban and J. Ghosh, Scalable greedy feature selection via weak submodularity, Artificial Intelligence and Statistics, (2017), 1560–1568. [11] A. Krause, H. B. McMahan, C. Guestrin and A. Gupta, Robust submodular observation selection, Journal of Machine Learning Research, 9 (2008), 2761-2801. [12] A. Krause, A. Singh and C. Guestrin, Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies, Journal of Machine Learning Research, 9 (2008), 235-284. [13] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, Cost-effective outbreak detection in networks, Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2007), 420–429. [14] H. Lin and J. Bilmes, Multi-document summarization via budgeted maximization of submodular functions, Proceedings of the 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, (2010), 912–920. [15] A. Miller, Subset Selection in Regression, Second edition. Monographs on Statistics and Applied Probability, 95. Chapman & Hall/CRC, Boca Raton, FL, 2002. doi: 10.1201/9781420035933. [16] M. Minoux, Accelerated greedy algorithms for maximizing submodular set functions, Optimization Techniques, 7 (1978), 234-243. [17] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák and A. Krause, Lazier than lazy greedy, Proceedings of the 29th AAAI Conference on Artificial Intelligence, (2015), 1812–1818. [18] G. L. Nemhauser and L. A. Wolsey, Best algorithms for approximating the maximum of a submodular set function, Mathematics of Operations Research, 3 (1978), 177-188.  doi: 10.1287/moor.3.3.177. [19] G. L. Nemhauser, L. A. Wolsey and M. L. Fisher, An analysis of approximations for maximizing submodular set functions - I, Mathematical Programming, 14 (1978), 265-294.  doi: 10.1007/BF01588971. [20] C. Qian, Y. Yu and K. Tang, Approximation guarantees of stochastic greedy algorithms for subset selection, International Joint Conferences on Artificial Intelligence Organization, (2018), 1478–1484. [21] R. Sipos, A. Swaminathan, P. Shivaswamy, and T. Joachims, Temporal corpus summarization using submodular word coverge, Proceedings of the 21st ACM International Conference on Information and Knowledge Management (2012), 754–763.

show all references

##### References:
 [1] A. Dasgupta, R. Kumar and S. Ravi, Summarization through submodularity and dispersion, Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics, (2013), 1014–1022. [2] A. Das and D. Kempe, Submodular meets spectral: Greedy algorithms for subset selection, sparse approximation and dictionary selection, Proceedings of the 28th International Conference on International Conference on Machine Learning, (2011), 1057–1064. [3] K. El-Arini and C. Guestrin, Beyond keyword search: Discovering relevant scientific literature, Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2011), 439–447. [4] U. Feige, A threshold of $\ln n$ for approximating set cover, Journal of the ACM, 45 (1998), 634-652.  doi: 10.1145/285055.285059. [5] D. Golovin and A. Krause, Adaptive submodularity: Theory and applications in active learning and stochastic optimization, Journal of Artificial Intelligence Research, 42 (2011), 427-486. [6] R. Gomes and A. Krause, Budgeted nonparametric learning from data streams, Proceedings of the 27th International Conference on International Conference on Machine Learning, (2010), 391–398. [7] A. Guillory and J. Bilmes, Active semi-supervised learning using submodular functions, Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, (2011), 274–282. [8] A. Hassidim and Y. Singer, Robust guarantees of stochastic greedy algorithms, Proceedings of the 34th International Conference on Machine Learning, (2017), 1424–1432. [9] D. Kempe, J. Kleinberg and É. Tardos, Maximizing the spread of influence through a social network, Proceedings of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2003), 137–146. [10] Khanna, E. Elenberg, A. Dimakis, S. Negahban and J. Ghosh, Scalable greedy feature selection via weak submodularity, Artificial Intelligence and Statistics, (2017), 1560–1568. [11] A. Krause, H. B. McMahan, C. Guestrin and A. Gupta, Robust submodular observation selection, Journal of Machine Learning Research, 9 (2008), 2761-2801. [12] A. Krause, A. Singh and C. Guestrin, Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies, Journal of Machine Learning Research, 9 (2008), 235-284. [13] J. Leskovec, A. Krause, C. Guestrin, C. Faloutsos, J. VanBriesen and N. Glance, Cost-effective outbreak detection in networks, Proceedings of the 13th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, (2007), 420–429. [14] H. Lin and J. Bilmes, Multi-document summarization via budgeted maximization of submodular functions, Proceedings of the 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics, (2010), 912–920. [15] A. Miller, Subset Selection in Regression, Second edition. Monographs on Statistics and Applied Probability, 95. Chapman & Hall/CRC, Boca Raton, FL, 2002. doi: 10.1201/9781420035933. [16] M. Minoux, Accelerated greedy algorithms for maximizing submodular set functions, Optimization Techniques, 7 (1978), 234-243. [17] B. Mirzasoleiman, A. Badanidiyuru, A. Karbasi, J. Vondrák and A. Krause, Lazier than lazy greedy, Proceedings of the 29th AAAI Conference on Artificial Intelligence, (2015), 1812–1818. [18] G. L. Nemhauser and L. A. Wolsey, Best algorithms for approximating the maximum of a submodular set function, Mathematics of Operations Research, 3 (1978), 177-188.  doi: 10.1287/moor.3.3.177. [19] G. L. Nemhauser, L. A. Wolsey and M. L. Fisher, An analysis of approximations for maximizing submodular set functions - I, Mathematical Programming, 14 (1978), 265-294.  doi: 10.1007/BF01588971. [20] C. Qian, Y. Yu and K. Tang, Approximation guarantees of stochastic greedy algorithms for subset selection, International Joint Conferences on Artificial Intelligence Organization, (2018), 1478–1484. [21] R. Sipos, A. Swaminathan, P. Shivaswamy, and T. Joachims, Temporal corpus summarization using submodular word coverge, Proceedings of the 21st ACM International Conference on Information and Knowledge Management (2012), 754–763.
Illustration of the function $1-e^{-\frac{s}{n}x}$
 [1] Xin Sun, Dachuan Xu, Dongmei Zhang, Yang Zhou. An adaptive algorithm for maximization of non-submodular function with a matroid constraint. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022031 [2] Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu, Tanmay Choudhury. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2021, 15 (2) : 365-386. doi: 10.3934/amc.2020071 [3] Fengmin Wang, Dachuan Xu, Donglei Du, Chenchen Wu. Primal-dual approximation algorithms for submodular cost set cover problems with linear/submodular penalties. Numerical Algebra, Control and Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91 [4] Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial and Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 [5] Laetitia Paoli. A proximal-like algorithm for vibro-impact problems with a non-smooth set of constraints. Conference Publications, 2011, 2011 (Special) : 1186-1195. doi: 10.3934/proc.2011.2011.1186 [6] Rodolfo Mendoza-Gómez, Roger Z. Ríos-Mercado, Karla B. Valenzuela-Ocaña. An iterated greedy algorithm with variable neighborhood descent for the planning of specialized diagnostic services in a segmented healthcare system. Journal of Industrial and Management Optimization, 2020, 16 (2) : 857-885. doi: 10.3934/jimo.2018182 [7] Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems and Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 [8] Nguyen Duc Vuong, Tran Ngoc Thang. Optimizing over Pareto set of semistrictly quasiconcave vector maximization and application to stochastic portfolio selection. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022029 [9] Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Constraint algorithm for singular field theories in the k-cosymplectic framework. Journal of Geometric Mechanics, 2020, 12 (1) : 1-23. doi: 10.3934/jgm.2020002 [10] Tibor Krisztin. The unstable set of zero and the global attractor for delayed monotone positive feedback. Conference Publications, 2001, 2001 (Special) : 229-240. doi: 10.3934/proc.2001.2001.229 [11] Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial and Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142 [12] Feng-Yu Wang. Exponential convergence of non-linear monotone SPDEs. Discrete and Continuous Dynamical Systems, 2015, 35 (11) : 5239-5253. doi: 10.3934/dcds.2015.35.5239 [13] Gabriela Kováčová, Birgit Rudloff, Igor Cialenco. Acceptability maximization. Frontiers of Mathematical Finance, , () : -. doi: 10.3934/fmf.2021009 [14] Sanyi Tang, Wenhong Pang. On the continuity of the function describing the times of meeting impulsive set and its application. Mathematical Biosciences & Engineering, 2017, 14 (5&6) : 1399-1406. doi: 10.3934/mbe.2017072 [15] Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417 [16] Xavier Gràcia, Xavier Rivas, Narciso Román-Roy. Erratum: Constraint algorithm for singular field theories in the $k$-cosymplectic framework. Journal of Geometric Mechanics, 2021, 13 (2) : 273-275. doi: 10.3934/jgm.2021007 [17] Binghai Zhou, Yuanrui Lei, Shi Zong. Lagrangian relaxation algorithm for the truck scheduling problem with products time window constraint in multi-door cross-dock. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021151 [18] Yuxiang Zhang, Shiwang Ma. Invasion dynamics of a diffusive pioneer-climax model: Monotone and non-monotone cases. Discrete and Continuous Dynamical Systems - B, 2021, 26 (9) : 4767-4788. doi: 10.3934/dcdsb.2020312 [19] Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial and Management Optimization, 2020, 16 (4) : 1571-1584. doi: 10.3934/jimo.2019018 [20] Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial and Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585

2020 Impact Factor: 1.801