Structured Convex Optimization under Submodular Constraints

Kiyohito Nagano, Yoshinobu Kawahara
Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, PMLR R11:569-578, 2013.

Abstract

A number of discrete and continuous optimization problems in machine learning are related to convex minimization problems under submodular constraints. In this paper, we deal with a submodular function with a directed graph structure, and we show that a wide range of convex optimization problems under submodular constraints can be solved much more efficiently than general submodular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse optimization methods, in which the proposed methods are effective. Additionally, we evaluate the performance of the proposed method through computational experiments.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR11-nagano13a, title = {Structured Convex Optimization under Submodular Constraints}, author = {Nagano, Kiyohito and Kawahara, Yoshinobu}, booktitle = {Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence}, pages = {569--578}, year = {2013}, editor = {Nicholson, Ann and Smyth, Padhraic}, volume = {R11}, series = {Proceedings of Machine Learning Research}, month = {12--14 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r11/main/assets/nagano13a/nagano13a.pdf}, url = {https://proceedings.mlr.press/r11/nagano13a.html}, abstract = {A number of discrete and continuous optimization problems in machine learning are related to convex minimization problems under submodular constraints. In this paper, we deal with a submodular function with a directed graph structure, and we show that a wide range of convex optimization problems under submodular constraints can be solved much more efficiently than general submodular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse optimization methods, in which the proposed methods are effective. Additionally, we evaluate the performance of the proposed method through computational experiments.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Structured Convex Optimization under Submodular Constraints %A Kiyohito Nagano %A Yoshinobu Kawahara %B Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2013 %E Ann Nicholson %E Padhraic Smyth %F pmlr-vR11-nagano13a %I PMLR %P 569--578 %U https://proceedings.mlr.press/r11/nagano13a.html %V R11 %X A number of discrete and continuous optimization problems in machine learning are related to convex minimization problems under submodular constraints. In this paper, we deal with a submodular function with a directed graph structure, and we show that a wide range of convex optimization problems under submodular constraints can be solved much more efficiently than general submodular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse optimization methods, in which the proposed methods are effective. Additionally, we evaluate the performance of the proposed method through computational experiments. %Z Reissued by PMLR on 04 October 2026.
APA
Nagano, K. & Kawahara, Y.. (2013). Structured Convex Optimization under Submodular Constraints. Proceedings of the 29th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R11:569-578 Available from https://proceedings.mlr.press/r11/nagano13a.html. Reissued by PMLR on 04 October 2026.

Related Material