Figure 1.
Illustration of the function $ 1-e^{-\frac{s}{n}x} $
-
Previous Article
Finite horizon portfolio selection problems with stochastic borrowing constraints
- JIMO Home
- This Issue
-
Next Article
Relaxed successive projection algorithm with strong convergence for the multiple-sets split equality problem
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 |
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.
Keywords:
Set function maximization,
cardinality constraint,
non-submodular,
monotone,
greedy algorithm.
Mathematics Subject Classification:
Primary: 58F15, 58F17; Secondary: 53C35.
Citation:
Lu Han, Min Li, Dachuan Xu, Dongmei Zhang.
Stochastic-Lazier-Greedy Algorithm for monotone non-submodular maximization. Journal of Industrial & Management Optimization, 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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [8] |
A. Hassidim and Y. Singer, Robust guarantees of stochastic greedy algorithms, Proceedings of the 34th International Conference on Machine Learning, (2017), 1424–1432. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [11] |
A. Krause, H. B. McMahan, C. Guestrin and A. Gupta, Robust submodular observation selection, Journal of Machine Learning Research, 9 (2008), 2761-2801. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [8] |
A. Hassidim and Y. Singer, Robust guarantees of stochastic greedy algorithms, Proceedings of the 34th International Conference on Machine Learning, (2017), 1424–1432. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [11] |
A. Krause, H. B. McMahan, C. Guestrin and A. Gupta, Robust submodular observation selection, Journal of Machine Learning Research, 9 (2008), 2761-2801. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [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. Google Scholar |
| [1] |
Sumit Kumar Debnath, Pantelimon Stǎnicǎ, Nibedita Kundu, Tanmay Choudhury. Secure and efficient multiparty private set intersection cardinality. Advances in Mathematics of Communications, 2019, 0 (0) : 0-0. doi: 10.3934/amc.2020071 |
| [2] |
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 & Optimization, 2015, 5 (2) : 91-100. doi: 10.3934/naco.2015.5.91 |
| [3] |
Gaidi Li, Zhen Wang, Dachuan Xu. An approximation algorithm for the $k$-level facility location problem with submodular penalties. Journal of Industrial & Management Optimization, 2012, 8 (3) : 521-529. doi: 10.3934/jimo.2012.8.521 |
| [4] |
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 |
| [5] |
Yingying Li, Stanley Osher. Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm. Inverse Problems & Imaging, 2009, 3 (3) : 487-503. doi: 10.3934/ipi.2009.3.487 |
| [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 & Management Optimization, 2020, 16 (2) : 857-885. doi: 10.3934/jimo.2018182 |
| [7] |
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 |
| [8] |
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 |
| [9] |
Jianjun Liu, Min Zeng, Yifan Ge, Changzhi Wu, Xiangyu Wang. Improved Cuckoo Search algorithm for numerical function optimization. Journal of Industrial & Management Optimization, 2020, 16 (1) : 103-115. doi: 10.3934/jimo.2018142 |
| [10] |
Feng-Yu Wang. Exponential convergence of non-linear monotone SPDEs. Discrete & Continuous Dynamical Systems - A, 2015, 35 (11) : 5239-5253. doi: 10.3934/dcds.2015.35.5239 |
| [11] |
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 |
| [12] |
Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417 |
| [13] |
Zhiqing Meng, Qiying Hu, Chuangyin Dang. A penalty function algorithm with objective parameters for nonlinear mathematical programming. Journal of Industrial & Management Optimization, 2009, 5 (3) : 585-601. doi: 10.3934/jimo.2009.5.585 |
| [14] |
Maolin Cheng, Mingyin Xiang. Application of a modified CES production function model based on improved firefly algorithm. Journal of Industrial & Management Optimization, 2020, 16 (4) : 1571-1584. doi: 10.3934/jimo.2019018 |
| [15] |
Thorsten Hüls. A model function for non-autonomous bifurcations of maps. Discrete & Continuous Dynamical Systems - B, 2007, 7 (2) : 351-363. doi: 10.3934/dcdsb.2007.7.351 |
| [16] |
Sergiu Aizicovici, Simeon Reich. Anti-periodic solutions to a class of non-monotone evolution equations. Discrete & Continuous Dynamical Systems - A, 1999, 5 (1) : 35-42. doi: 10.3934/dcds.1999.5.35 |
| [17] |
Jun Chen, Wenyu Sun, Zhenghao Yang. A non-monotone retrospective trust-region method for unconstrained optimization. Journal of Industrial & Management Optimization, 2013, 9 (4) : 919-944. doi: 10.3934/jimo.2013.9.919 |
| [18] |
José Caicedo, Alfonso Castro, Arturo Sanjuán. Bifurcation at infinity for a semilinear wave equation with non-monotone nonlinearity. Discrete & Continuous Dynamical Systems - A, 2017, 37 (4) : 1857-1865. doi: 10.3934/dcds.2017078 |
| [19] |
Alfonso Castro, Benjamin Preskill. Existence of solutions for a semilinear wave equation with non-monotone nonlinearity. Discrete & Continuous Dynamical Systems - A, 2010, 28 (2) : 649-658. doi: 10.3934/dcds.2010.28.649 |
| [20] |
Robert Baier, Thuy T. T. Le. Construction of the minimum time function for linear systems via higher-order set-valued methods. Mathematical Control & Related Fields, 2019, 9 (2) : 223-255. doi: 10.3934/mcrf.2019012 |
2018 Impact Factor: 1.025
Tools
Metrics
Other articles
by authors
[Back to Top]