Document Open Access Logo

Weakly Submodular Function Maximization Using Local Submodularity Ratio

Authors Richard Santiago, Yuichi Yoshida

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2020.64.pdf
  • Filesize: 0.54 MB
  • 17 pages

Document Identifiers

Author Details

Richard Santiago
  • ETH Zürich, Switzerland
Yuichi Yoshida
  • National Institute of Informatics, Tokyo, Japan

Acknowledgements

Part of this work was conducted during the first author’s visit to the National Institute of Informatics in Tokyo. The second authors was supported by JSPS KAKENHI Grant Number 18H05291.

Cite As Get BibTex

Richard Santiago and Yuichi Yoshida. Weakly Submodular Function Maximization Using Local Submodularity Ratio. In 31st International Symposium on Algorithms and Computation (ISAAC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 181, pp. 64:1-64:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.ISAAC.2020.64

Abstract

Weak submodularity is a natural relaxation of the diminishing return property, which is equivalent to submodularity. Weak submodularity has been used to show that many (monotone) functions that arise in practice can be efficiently maximized with provable guarantees. In this work we introduce two natural generalizations of weak submodularity for non-monotone functions. We show that an efficient randomized greedy algorithm has provable approximation guarantees for maximizing these functions subject to a cardinality constraint. We then provide a more refined analysis that takes into account that the weak submodularity parameter may change (sometimes improving) throughout the execution of the algorithm. This leads to improved approximation guarantees in some settings. We provide applications of our results for monotone and non-monotone maximization problems.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • weakly submodular
  • non-monotone
  • local submodularity ratio

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Rakesh Agrawal, Sreenivas Gollapudi, Alan Halverson, and Samuel Ieong. Diversifying search results. In Proceedings of the second ACM international conference on web search and data mining, pages 5-14, 2009. Google Scholar
  2. Andrew An Bian, Joachim M Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guarantees for greedy maximization of non-submodular functions with applications. In Proceedings of the 34th International Conference on Machine Learning (ICML), pages 498-507, 2017. Google Scholar
  3. Benjamin Birnbaum and Kenneth J Goldman. An improved analysis for a greedy remote-clique algorithm using factor-revealing lps. Algorithmica, 55(1):42-59, 2009. Google Scholar
  4. Allan Borodin, Aadhar Jain, Hyun Chul Lee, and Yuli Ye. Max-sum diversification, monotone submodular functions, and dynamic updates. ACM Transactions on Algorithms (TALG), 13(3):1-25, 2017. Google Scholar
  5. Allan Borodin, Dai Le, and Yuli Ye. Proportionally submodular functions, 2015. Manuscript: URL: http://www.cs.toronto.edu/~bor/Papers/proportional-talg-submit.pdf.
  6. Allan Borodin, Dai Tri Man Le, and Yuli Ye. Weakly submodular functions. arXiv preprint, 2014. URL: http://arxiv.org/abs/1401.6697.
  7. Niv Buchbinder and Moran Feldman. Constrained submodular maximization via a nonsymmetric technique. Mathematics of Operations Research, 44(3):988-1005, 2019. Google Scholar
  8. Niv Buchbinder, Moran Feldman, Joseph Seffi Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Proceedings of the 25th annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1433-1452, 2014. Google Scholar
  9. Lin Chen, Moran Feldman, and Amin Karbasi. Weakly submodular maximization beyond cardinality constraints: Does randomization help greedy? In Proceedings of the 35th International Conference on Machine Learning (ICML), pages 803-812, 2018. Google Scholar
  10. Wei Chen, Shang-Hua Teng, and Hanrui Zhang. Capturing complementarity in set functions by going beyond submodularity/subadditivity. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  11. Abhimanyu Das and David Kempe. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In Proceedings of the 28th International Conference on Machine Learning (ICML), pages 1057-1064, 2011. Google Scholar
  12. Abhimanyu Das and David Kempe. Approximate submodularity and its applications: subset selection, sparse approximation and dictionary selection. The Journal of Machine Learning Research, 19(1):74-107, 2018. Google Scholar
  13. Marina Drosou and Evaggelia Pitoura. Search result diversification. ACM SIGMOD Record, 39(1):41-47, 2010. Google Scholar
  14. Ethan Elenberg, Alexandros G Dimakis, Moran Feldman, and Amin Karbasi. Streaming weak submodularity: Interpreting neural networks on the fly. In Advances in Neural Information Processing Systems (NIPS), pages 4044-4054, 2017. Google Scholar
  15. Ethan R Elenberg, Rajiv Khanna, Alexandros G Dimakis, Sahand Negahban, et al. Restricted strong convexity implies weak submodularity. The Annals of Statistics, 46(6B):3539-3568, 2018. Google Scholar
  16. Alina Ene and Huy L Nguyen. Constrained submodular maximization: Beyond 1/e. In Proceedings of the IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 248-257, 2016. Google Scholar
  17. Uriel Feige, Michal Feldman, Nicole Immorlica, Rani Izsak, Brendan Lucier, and Vasilis Syrgkanis. A unifying hierarchy of valuations with complements and substitutes. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence, pages 872-878, 2015. Google Scholar
  18. Uriel Feige and Rani Izsak. Welfare maximization and the supermodular degree. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 247-256, 2013. Google Scholar
  19. Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), pages 570-579, 2011. Google Scholar
  20. Khashayar Gatmiry and Manuel Gomez-Rodriguez. Non-submodular function maximization subject to a matroid constraint, with applications. arXiv preprint, 2018. URL: http://arxiv.org/abs/1811.07863.
  21. Mehrdad Ghadiri, Richard Santiago, and Bruce Shepherd. Beyond submodular maximization via one-sided smoothness. arXiv preprint, 2019. URL: http://arxiv.org/abs/1904.09216.
  22. Mehrdad Ghadiri, Richard Santiago, and Bruce Shepherd. A parameterized family of meta-submodular functions. arXiv preprint, 2020. URL: http://arxiv.org/abs/2006.13754.
  23. Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Proceedings of the 22nd annual ACM-SIAM symposium on Discrete Algorithms (SODA), pages 1098-1116, 2011. Google Scholar
  24. Jennifer Gillenwater, Alex Kulesza, and Ben Taskar. Near-optimal map inference for determinantal point processes. In Advances in Neural Information Processing Systems (NIPS), pages 2735-2743, 2012. Google Scholar
  25. Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: offline and secretary algorithms. In Proceedings of the 6th international conference on Internet and network economics (WINE), pages 246-257, 2010. Google Scholar
  26. Chris Harshaw, Moran Feldman, Justin Ward, and Amin Karbasi. Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications. In Proceedings of the 36th International Conference on Machine Learning (ICML), pages 2634-2643, 2019. Google Scholar
  27. Refael Hassin, Shlomi Rubinstein, and Arie Tamir. Approximation algorithms for maximum dispersion. Operations research letters, 21(3):133-137, 1997. Google Scholar
  28. Thibaut Horel and Yaron Singer. Maximization of approximately submodular functions. In Advances in Neural Information Processing Systems, pages 3045-3053, 2016. Google Scholar
  29. Rajiv Khanna, Ethan Elenberg, Alex Dimakis, Sahand Negahban, and Joydeep Ghosh. Scalable greedy feature selection via weak submodularity. In Proceedings of the 20th International Conference on Artificial Intelligence and Statistics (AISTATS), pages 1560-1568, 2017. Google Scholar
  30. Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Maximizing nonmonotone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics, 23(4):2053-2078, 2010. Google Scholar
  31. Maxwell W Libbrecht, Jeffrey A Bilmes, and William Stafford Noble. Choosing non-redundant representative subsets of protein sequence data sets using submodular optimization. In Proceedings of the 2018 ACM International Conference on Bioinformatics, Computational Biology, and Health Informatics (BCB), pages 566-566, 2018. Google Scholar
  32. Hui Lin and Jeff Bilmes. Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the Association for Computational Linguistics (NAACL-HLT), pages 912-920, 2010. Google Scholar
  33. Hui Lin and Jeff Bilmes. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies (ACL-HLT), pages 510-520, 2011. Google Scholar
  34. Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In Proceedings of the 33rd International Conference on Machine Learning (ICML), pages 1358-1367, 2016. Google Scholar
  35. Sekharipuram S Ravi, Daniel J Rosenkrantz, and Giri Kumar Tayi. Heuristic and special case algorithms for dispersion problems. Operations Research, 42(2):299-310, 1994. Google Scholar
  36. Richard Santiago and Yuichi Yoshida. Weakly submodular function maximization using local submodularity ratio. arXiv preprint, 2020. URL: http://arxiv.org/abs/2004.14650.
  37. Sebastian Tschiatschek, Rishabh K Iyer, Haochen Wei, and Jeff A Bilmes. Learning mixtures of submodular functions for image collection summarization. In Advances in neural information processing systems (NIPS), pages 1413-1421, 2014. Google Scholar
  38. Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Journal on Computing, 42(1):265-304, 2013. Google Scholar
  39. Ghahramani Zoubin. Scaling the indian buffet process via submodular maximization. In Proceedings of the 30th International Conference on Machine Learning (ICML), pages 1013-1021, 2013. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact