A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding

Rishabh Iyer, Stefanie Jegelka, Jeffrey Bilmes
Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, PMLR R12:431-440, 2014.

Abstract

It is becoming increasingly evident that many ma- chine learning problems may be reduced to sub- modular optimization. Previous work addresses generic discrete approaches and specific relax- ations. In this work, we take a generic view from a relaxation perspective. We show a relaxation formulation and simple rounding strategy that, based on the monotone closure of relaxed con- straints, reveals analogies between minimization and maximization problems, and includes known results as special cases and extends to a wider range of settings. Our resulting approximation factors match the corresponding integrality gaps. For submodular maximization, a number of relax- ation approaches have been proposed. A critical challenge for the practical applicability of these techniques, however, is the complexity of evaluat- ing the multilinear extension. We show that this extension can be efficiently evaluated for a num- ber of useful submodular functions, thus making these otherwise impractical algorithms viable for real-world machine learning problems.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR12-iyer14a, title = {A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding}, author = {Iyer, Rishabh and Jegelka, Stefanie and Bilmes, Jeffrey}, booktitle = {Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence}, pages = {431--440}, year = {2014}, editor = {Zhang, Nevin L. and Tian, Jin}, volume = {R12}, series = {Proceedings of Machine Learning Research}, month = {23--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r12/main/assets/iyer14a/iyer14a.pdf}, url = {https://proceedings.mlr.press/r12/iyer14a.html}, abstract = {It is becoming increasingly evident that many ma- chine learning problems may be reduced to sub- modular optimization. Previous work addresses generic discrete approaches and specific relax- ations. In this work, we take a generic view from a relaxation perspective. We show a relaxation formulation and simple rounding strategy that, based on the monotone closure of relaxed con- straints, reveals analogies between minimization and maximization problems, and includes known results as special cases and extends to a wider range of settings. Our resulting approximation factors match the corresponding integrality gaps. For submodular maximization, a number of relax- ation approaches have been proposed. A critical challenge for the practical applicability of these techniques, however, is the complexity of evaluat- ing the multilinear extension. We show that this extension can be efficiently evaluated for a num- ber of useful submodular functions, thus making these otherwise impractical algorithms viable for real-world machine learning problems.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding %A Rishabh Iyer %A Stefanie Jegelka %A Jeffrey Bilmes %B Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2014 %E Nevin L. Zhang %E Jin Tian %F pmlr-vR12-iyer14a %I PMLR %P 431--440 %U https://proceedings.mlr.press/r12/iyer14a.html %V R12 %X It is becoming increasingly evident that many ma- chine learning problems may be reduced to sub- modular optimization. Previous work addresses generic discrete approaches and specific relax- ations. In this work, we take a generic view from a relaxation perspective. We show a relaxation formulation and simple rounding strategy that, based on the monotone closure of relaxed con- straints, reveals analogies between minimization and maximization problems, and includes known results as special cases and extends to a wider range of settings. Our resulting approximation factors match the corresponding integrality gaps. For submodular maximization, a number of relax- ation approaches have been proposed. A critical challenge for the practical applicability of these techniques, however, is the complexity of evaluat- ing the multilinear extension. We show that this extension can be efficiently evaluated for a num- ber of useful submodular functions, thus making these otherwise impractical algorithms viable for real-world machine learning problems. %Z Reissued by PMLR on 04 October 2026.
APA
Iyer, R., Jegelka, S. & Bilmes, J.. (2014). A Unified Approach to Fast Algorithms for Submodular Optimization based on Continuous Relaxations and Rounding. Proceedings of the 30th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R12:431-440 Available from https://proceedings.mlr.press/r12/iyer14a.html. Reissued by PMLR on 04 October 2026.

Related Material