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, 2020  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]

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

[6]

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

[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]

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

[19]

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

[20]

Fabián Crocce, Ernesto Mordecki. A non-iterative algorithm for generalized pig games. Journal of Dynamics & Games, 2018, 5 (4) : 331-341. doi: 10.3934/jdg.2018020

2019 Impact Factor: 1.366

Metrics

  • PDF downloads (24)
  • HTML views (145)
  • Cited by (0)

Other articles
by authors

[Back to Top]