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