Article

Free access

Non-monotone submodular maximization in exponentially fewer iterations

Authors:

Eric Balkanski,

Yaron SingerAuthors Info & Claims

NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems

Pages 2359 - 2370

Published: 03 December 2018 Publication History

PDF eReader Publisher Site

Abstract

In this paper we consider parallelization for applications whose objective can be expressed as maximizing a non-monotone submodular function under a cardinality constraint. Our main result is an algorithm whose approximation is arbitrarily close to 1/2e in O(log² n) adaptive rounds, where n is the size of the ground set. This is an exponential speedup in parallel running time over any previously studied algorithm for constrained non-monotone submodular maximization. Beyond its provable guarantees, the algorithm performs well in practice. Specifically, experiments on traffic monitoring and personalized data summarization applications show that the algorithm finds solutions whose values are competitive with state-of-the-art algorithms while running in exponentially fewer parallel iterations.

References

[1]

Arpit Agarwal, Shivani Agarwal, Sepehr Assadi, and Sanjeev Khanna. Learning with limited rounds of adaptivity: Coin tossing, multi-armed bandits, and ranking from pairwise comparisons. In COLT, pages 39-75, 2017.

[2]

Rafael da Ponte Barbosa, Alina Ene, Huy L Nguyen, and Justin Ward. A new framework for distributed submodular maximization. In FOCS, pages 645-654. Ieee, 2016.

[3]

Niv Buchbinder, Moran Feldman, Joseph Seffi Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1433-1452. Society for Industrial and Applied Mathematics, 2014.

[4]

Harry Buhrman, David García-Soriano, Arie Matsliah, and Ronald de Wolf. The non-adaptive query complexity of testing k-parities. arXiv preprint arXiv:1209.3849, 2012.

[5]

Guy E Blelloch. Programming parallel algorithms. Communications of the ACM, 39(3):85-97, 1996.

Digital Library

[6]

Mark Braverman, Jieming Mao, and S Matthew Weinberg. Parallel algorithms for select and partition with noisy comparisons. In STOC, pages 851-862, 2016.

Digital Library

[7]

Guy E Blelloch, Richard Peng, and Kanat Tangwongsan. Linear-work greedy parallel approximate set cover and variants. In SPAA, pages 23-32, 2011.

Digital Library

[8]

Guy E Blelloch and Margaret Reid-Miller. Fast set operations using treaps. In SPAA, pages 16-26, 1998.

Digital Library

[9]

Bonnie Berger, John Rompel, and Peter W Shor. Efficient nc algorithms for set cover with applications to learning and geometry. In FOCS, pages 54-59. IEEE, 1989.

Digital Library

[10]

Eric Balkanski, Aviad Rubinstein, and Yaron Singer. An exponential speedup in parallel running time for submodular maximization without loss in approximation. arXiv preprint arXiv:1804.06355, 2018.

[11]

Eric Balkanski and Yaron Singer. The adaptive complexity of maximizing a submodular function. In STOC, 2018.

Digital Library

[12]

Eric Balkanski and Yaron Singer. Approximation guarantees for adaptive sampling. ICML, 2018.

[13]

Guy E Blelloch, Harsha Vardhan Simhadri, and Kanat Tangwongsan. Parallel and i/o efficient set covering algorithms. In SPAA, pages 82-90. ACM, 2012.

Digital Library

[14]

CalTrans. Pems: California performance measuring system. http://pems.dot.ca.gov/ [accessed: May 1, 2018].

[15]

Clement Canonne and Tom Gur. An adaptivity hierarchy theorem for property testing. arXiv preprint arXiv:1702.05678, 2017.

[16]

Chandra Chekuri, TS Jayram, and Jan Vondrák. On multiplicative weight updates for concave and submodular function maximization. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, pages 201-210. ACM, 2015.

Digital Library

[17]

Flavio Chierichetti, Ravi Kumar, and Andrew Tomkins. Max-cover in map-reduce. In WWW, pages 231-240, 2010.

Digital Library

[18]

Richard Cole. Parallel merge sort. SIAM Journal on Computing, 17(4):770-785, 1988.

Digital Library

[19]

Xi Chen, Rocco A Servedio, Li-Yang Tan, Erik Waingarten, and Jinyu Xie. Settling the query complexity of non-adaptive junta testing. arXiv preprint arXiv:1704.06314, 2017.

[20]

Pavol Duris, Zvi Galil, and Georg Schnitger. Lower bounds on communication complexity. In STOC, pages 81-91, 1984.

Digital Library

[21]

Alina Ene and Huy L Nguyen. Constrained submodular maximization: Beyond 1/e. In Foundations of Computer Science (FOCS), 2016 IEEE 57th Annual Symposium on, pages 248-257. IEEE, 2016.

[22]

Alina Ene and Huy L Nguyen. Submodular maximization with nearly-optimal approximation and adaptivity in nearly-linear time. arXiv preprint arXiv:1804.05379, 2018.

[23]

Moran Feldman, Christopher Harshaw, and Amin Karbasi. Defining and evaluating network communities based on ground-truth. Knowledge and Information Systems 42, 1 (2015), 33 pages., 2015.

Digital Library

[24]

Uriel Feige, Vahab S Mirrokni, and Jan Vondrak. Maximizing non-monotone submodular functions. SIAM Journal on Computing, 40(4):1133-1153, 2011.

Digital Library

[25]

Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, pages 570-579. IEEE, 2011.

Digital Library

[26]

Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In International Workshop on Internet and Network Economics, pages 246-257. Springer, 2010.

Digital Library

[27]

Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete Algorithms, pages 1098-1116. Society for Industrial and Applied Mathematics, 2011.

[28]

Jarvis D Haupt, Richard G Baraniuk, Rui M Castro, and Robert D Nowak. Compressive distilled sensing: Sparse recovery using adaptivity in compressive measurements. In Signals, Systems and Computers, 2009 Conference Record of the Forty-Third Asilomar Conference on, pages 1551-1555. IEEE, 2009.

Digital Library

[29]

F. Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context. ACM Transactions on Interactive Intelligent Systems (TiiS) 5, 4, Article 19 (December 2015), 19 pages., 2015.

Digital Library

[30]

Jarvis Haupt, Robert Nowak, and Rui Castro. Adaptive sensing for sparse signal recovery. In Digital Signal Processing Workshop and 5th IEEE Signal Processing Education Workshop, pages 702-707. IEEE, 2009.

[31]

Piotr Indyk, Eric Price, and David P Woodruff. On the power of adaptivity in sparse recovery. In FOCS, pages 285-294. IEEE, 2011.

Digital Library

[32]

Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images, 2009.

[33]

Ravi Kumar, Benjamin Moseley, Sergei Vassilvitskii, and Andrea Vattani. Fast greedy algorithms in mapreduce and streaming. ACM Transactions on Parallel Computing, 2(3):14, 2015.

Digital Library

[34]

Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pages 323-332. ACM, 2009.

Digital Library

[35]

Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In ICML, pages 1358-1367, 2016.

Digital Library

[36]

Baharan Mirzasoleiman, Amin Karbasi, Rik Sarkar, and Andreas Krause. Distributed sub-modular maximization: Identifying representative elements in massive data. In NIPS, pages 2049-2057, 2013.

Digital Library

[37]

Vahab Mirrokni and Morteza Zadimoghaddam. Randomized composable core-sets for distributed submodular maximization. In STOC, pages 153-162, 2015.

Digital Library

[38]

Hongseok Namkoong, Aman Sinha, Steve Yadlowsky, and John C Duchi. Adaptive sampling probabilities for non-smooth optimization. In ICML, pages 2574-2583, 2017.

Digital Library

[39]

Noam Nisan and Avi Widgerson. Rounds in communication complexity revisited. In STOC, pages 419-429, 1991.

Digital Library

[40]

Christos H Papadimitriou and Michael Sipser. Communication complexity. Journal of Computer and System Sciences, 28(2):260-269, 1984.

[41]

Sridhar Rajagopalan and Vijay V Vazirani. Primal-dual rnc approximation algorithms for set cover and covering integer programs. SIAM Journal on Computing, 28(2):525-540, 1998.

Digital Library

[42]

Leslie G Valiant. Parallelism in comparison problems. SIAM Journal on Computing, 4(3):348-355, 1975.

Digital Library

Cited By

Banihashem KBiabani LGoudarzi SHajiaghayi MJabbarzade PMonemizadeh MOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Dynamic non-monotone submodular maximizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666883(17369-17382)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666883
Chekuri CQuanrud KCharikar MCohen E(2019)Parallelizing greedy for submodular set function maximization in matroids and beyondProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316406(78-89)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316406
Assadi SChen YKhanna SCharikar MCohen E(2019)Polynomial pass lower bounds for graph streaming algorithmsProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316361(265-276)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316361

Non-monotone submodular maximization in exponentially fewer iterations
1. Computing methodologies

Recommendations

Parallel algorithm for non-monotone DR-submodular maximization
ICML'20: Proceedings of the 37th International Conference on Machine Learning

In this work, we give a new parallel algorithm for the problem of maximizing a nonmonotone diminishing returns submodular function subject to a cardinality constraint. For any desired accuracy ε, our algorithm achieves a 1/e - ε approximation using O(log ...
Bandit multi-linear DR-submodular maximization and its applications on adversarial submodular bandits
ICML'23: Proceedings of the 40th International Conference on Machine Learning

We investigate the online bandit learning of the monotone multi-linear DR-submodular functions, designing the algorithm BanditMLSM that attains O(T^2/3 log T) of (1 – 1/e)-regret. Then we reduce submodular bandit with partition matroid constraint and ...
Dynamic non-monotone submodular maximization
NIPS '23: Proceedings of the 37th International Conference on Neural Information Processing Systems

Maximizing submodular functions has been increasingly used in many applications of machine learning, such as data summarization, recommendation systems, and feature selection. Moreover, there has been a growing interest in both submodular maximization ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

NIPS'18: Proceedings of the 32nd International Conference on Neural Information Processing Systems

December 2018

11021 pages

Publisher

Curran Associates Inc.

Red Hook, NY, United States

Publication History

Published: 03 December 2018

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
66
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)7

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Banihashem KBiabani LGoudarzi SHajiaghayi MJabbarzade PMonemizadeh MOh ANaumann TGloberson ASaenko KHardt MLevine S(2023)Dynamic non-monotone submodular maximizationProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3666883(17369-17382)Online publication date: 10-Dec-2023
https://dl.acm.org/doi/10.5555/3666122.3666883
Chekuri CQuanrud KCharikar MCohen E(2019)Parallelizing greedy for submodular set function maximization in matroids and beyondProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316406(78-89)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316406
Assadi SChen YKhanna SCharikar MCohen E(2019)Polynomial pass lower bounds for graph streaming algorithmsProceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing10.1145/3313276.3316361(265-276)Online publication date: 23-Jun-2019
https://dl.acm.org/doi/10.1145/3313276.3316361

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents