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  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 & 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.  Google Scholar

[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.   Google Scholar

[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. KrauseH. B. McMahanC. Guestrin and A. Gupta, Robust submodular observation selection, Journal of Machine Learning Research, 9 (2008), 2761-2801.   Google Scholar

[12]

A. KrauseA. 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.  Google Scholar

[16]

M. Minoux, Accelerated greedy algorithms for maximizing submodular set functions, Optimization Techniques, 7 (1978), 234-243.   Google Scholar

[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.  Google Scholar

[19]

G. L. NemhauserL. 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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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. KrauseH. B. McMahanC. Guestrin and A. Gupta, Robust submodular observation selection, Journal of Machine Learning Research, 9 (2008), 2761-2801.   Google Scholar

[12]

A. KrauseA. 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.  Google Scholar

[16]

M. Minoux, Accelerated greedy algorithms for maximizing submodular set functions, Optimization Techniques, 7 (1978), 234-243.   Google Scholar

[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.  Google Scholar

[19]

G. L. NemhauserL. 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.  Google Scholar

[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

Figure 1.  Illustration of the function $ 1-e^{-\frac{s}{n}x} $
[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

Metrics

  • PDF downloads (64)
  • HTML views (297)
  • Cited by (0)

Other articles
by authors

[Back to Top]