Figure 1.
Illustration of the function $ 1-e^{-\frac{s}{n}x} $
-
Previous Article
Fuzzy event-triggered disturbance rejection control of nonlinear systems
- 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, 2021, 15 (2) : 365-386. doi: 10.3934/amc.2020071 |
| [2] |
Mohammed Abdulrazaq Kahya, Suhaib Abduljabbar Altamir, Zakariya Yahya Algamal. Improving whale optimization algorithm for feature selection with a time-varying transfer function. Numerical Algebra, Control & Optimization, 2021, 11 (1) : 87-98. doi: 10.3934/naco.2020017 |
| [3] |
Lingfeng Li, Shousheng Luo, Xue-Cheng Tai, Jiang Yang. A new variational approach based on level-set function for convex hull problem with outliers. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020070 |
| [4] |
Kateřina Škardová, Tomáš Oberhuber, Jaroslav Tintěra, Radomír Chabiniok. Signed-distance function based non-rigid registration of image series with varying image intensity. Discrete & Continuous Dynamical Systems - S, 2021, 14 (3) : 1145-1160. doi: 10.3934/dcdss.2020386 |
| [5] |
Jing Qin, Shuang Li, Deanna Needell, Anna Ma, Rachel Grotheer, Chenxi Huang, Natalie Durgin. Stochastic greedy algorithms for multiple measurement vectors. Inverse Problems & Imaging, 2021, 15 (1) : 79-107. doi: 10.3934/ipi.2020066 |
| [6] |
Jie Zhang, Yuping Duan, Yue Lu, Michael K. Ng, Huibin Chang. Bilinear constraint based ADMM for mixed Poisson-Gaussian noise removal. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2020071 |
| [7] |
Claudia Lederman, Noemi Wolanski. An optimization problem with volume constraint for an inhomogeneous operator with nonstandard growth. Discrete & Continuous Dynamical Systems - A, 2020 doi: 10.3934/dcds.2020391 |
| [8] |
Aihua Fan, Jörg Schmeling, Weixiao Shen. $ L^\infty $-estimation of generalized Thue-Morse trigonometric polynomials and ergodic maximization. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 297-327. doi: 10.3934/dcds.2020363 |
| [9] |
Yifan Chen, Thomas Y. Hou. Function approximation via the subsampled Poincaré inequality. Discrete & Continuous Dynamical Systems - A, 2021, 41 (1) : 169-199. doi: 10.3934/dcds.2020296 |
| [10] |
Wolfgang Riedl, Robert Baier, Matthias Gerdts. Optimization-based subdivision algorithm for reachable sets. Journal of Computational Dynamics, 2021, 8 (1) : 99-130. doi: 10.3934/jcd.2021005 |
| [11] |
Yantao Wang, Linlin Su. Monotone and nonmonotone clines with partial panmixia across a geographical barrier. Discrete & Continuous Dynamical Systems - A, 2020, 40 (6) : 4019-4037. doi: 10.3934/dcds.2020056 |
| [12] |
Mengyu Cheng, Zhenxin Liu. Periodic, almost periodic and almost automorphic solutions for SPDEs with monotone coefficients. Discrete & Continuous Dynamical Systems - B, 2021 doi: 10.3934/dcdsb.2021026 |
| [13] |
Lateef Olakunle Jolaoso, Maggie Aphane. Bregman subgradient extragradient method with monotone self-adjustment stepsize for solving pseudo-monotone variational inequalities and fixed point problems. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020178 |
| [14] |
Mahdi Karimi, Seyed Jafar Sadjadi. Optimization of a Multi-Item Inventory model for deteriorating items with capacity constraint using dynamic programming. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2021013 |
| [15] |
Huu-Quang Nguyen, Ya-Chi Chu, Ruey-Lin Sheu. On the convexity for the range set of two quadratic functions. Journal of Industrial & Management Optimization, 2020 doi: 10.3934/jimo.2020169 |
| [16] |
Bahaaeldin Abdalla, Thabet Abdeljawad. Oscillation criteria for kernel function dependent fractional dynamic equations. Discrete & Continuous Dynamical Systems - S, 2020 doi: 10.3934/dcdss.2020443 |
| [17] |
Liping Tang, Ying Gao. Some properties of nonconvex oriented distance function and applications to vector optimization problems. Journal of Industrial & Management Optimization, 2021, 17 (1) : 485-500. doi: 10.3934/jimo.2020117 |
| [18] |
Raimund Bürger, Christophe Chalons, Rafael Ordoñez, Luis Miguel Villada. A multiclass Lighthill-Whitham-Richards traffic model with a discontinuous velocity function. Networks & Heterogeneous Media, 2021 doi: 10.3934/nhm.2021004 |
| [19] |
Hassan Mohammad. A diagonal PRP-type projection method for convex constrained nonlinear monotone equations. Journal of Industrial & Management Optimization, 2021, 17 (1) : 101-116. doi: 10.3934/jimo.2019101 |
| [20] |
Fang-Di Dong, Wan-Tong Li, Shi-Liang Wu, Li Zhang. Entire solutions originating from monotone fronts for nonlocal dispersal equations with bistable nonlinearity. Discrete & Continuous Dynamical Systems - B, 2021, 26 (2) : 1031-1060. doi: 10.3934/dcdsb.2020152 |
2019 Impact Factor: 1.366
Tools
Metrics
Other articles
by authors
[Back to Top]