Algorithms for Optimizing the Ratio of Submodular Functions

Wenruo Bai, Rishabh Iyer, Kai Wei, Jeff Bilmes
Proceedings of The 33rd International Conference on Machine Learning, PMLR 48:2751-2759, 2016.

Abstract

We investigate a new optimization problem involving minimizing the Ratio of Submodular (RS) functions. We argue that this problem occurs naturally in several real world applications. We then show the connection between this problem and several related problems, including minimizing the difference of submodular functions, and to submodular optimization subject to submodular constraints. We show RS that optimization can be solved within bounded approximation factors. We also provide a hardness bound and show that our tightest algorithm matches the lower bound up to a \log factor. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.

Cite this Paper

BibTeX
@InProceedings{pmlr-v48-baib16, title = {Algorithms for Optimizing the Ratio of Submodular Functions}, author = {Bai, Wenruo and Iyer, Rishabh and Wei, Kai and Bilmes, Jeff}, booktitle = {Proceedings of The 33rd International Conference on Machine Learning}, pages = {2751--2759}, year = {2016}, editor = {Balcan, Maria Florina and Weinberger, Kilian Q.}, volume = {48}, series = {Proceedings of Machine Learning Research}, address = {New York, New York, USA}, month = {20--22 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v48/baib16.pdf}, url = {https://proceedings.mlr.press/v48/baib16.html}, abstract = {We investigate a new optimization problem involving minimizing the Ratio of Submodular (RS) functions. We argue that this problem occurs naturally in several real world applications. We then show the connection between this problem and several related problems, including minimizing the difference of submodular functions, and to submodular optimization subject to submodular constraints. We show RS that optimization can be solved within bounded approximation factors. We also provide a hardness bound and show that our tightest algorithm matches the lower bound up to a \log factor. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.} }
Endnote
%0 Conference Paper %T Algorithms for Optimizing the Ratio of Submodular Functions %A Wenruo Bai %A Rishabh Iyer %A Kai Wei %A Jeff Bilmes %B Proceedings of The 33rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2016 %E Maria Florina Balcan %E Kilian Q. Weinberger %F pmlr-v48-baib16 %I PMLR %P 2751--2759 %U https://proceedings.mlr.press/v48/baib16.html %V 48 %X We investigate a new optimization problem involving minimizing the Ratio of Submodular (RS) functions. We argue that this problem occurs naturally in several real world applications. We then show the connection between this problem and several related problems, including minimizing the difference of submodular functions, and to submodular optimization subject to submodular constraints. We show RS that optimization can be solved within bounded approximation factors. We also provide a hardness bound and show that our tightest algorithm matches the lower bound up to a \log factor. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms.
RIS
TY - CPAPER TI - Algorithms for Optimizing the Ratio of Submodular Functions AU - Wenruo Bai AU - Rishabh Iyer AU - Kai Wei AU - Jeff Bilmes BT - Proceedings of The 33rd International Conference on Machine Learning DA - 2016/06/11 ED - Maria Florina Balcan ED - Kilian Q. Weinberger ID - pmlr-v48-baib16 PB - PMLR DP - Proceedings of Machine Learning Research VL - 48 SP - 2751 EP - 2759 L1 - http://proceedings.mlr.press/v48/baib16.pdf UR - https://proceedings.mlr.press/v48/baib16.html AB - We investigate a new optimization problem involving minimizing the Ratio of Submodular (RS) functions. We argue that this problem occurs naturally in several real world applications. We then show the connection between this problem and several related problems, including minimizing the difference of submodular functions, and to submodular optimization subject to submodular constraints. We show RS that optimization can be solved within bounded approximation factors. We also provide a hardness bound and show that our tightest algorithm matches the lower bound up to a \log factor. Finally, we empirically demonstrate the performance and good scalability properties of our algorithms. ER -
APA
Bai, W., Iyer, R., Wei, K. & Bilmes, J.. (2016). Algorithms for Optimizing the Ratio of Submodular Functions. Proceedings of The 33rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 48:2751-2759 Available from https://proceedings.mlr.press/v48/baib16.html.

Related Material