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 opti- mization problems in machine learning are related to convex minimization problems un- der 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 submod- ular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse op- timization methods, in which the proposed methods are effective. Additionally, we eval- uate 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 opti- mization problems in machine learning are related to convex minimization problems un- der 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 submod- ular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse op- timization methods, in which the proposed methods are effective. Additionally, we eval- uate 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 opti- mization problems in machine learning are related to convex minimization problems un- der 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 submod- ular optimization methods by a reduction to a maximum flow problem. Furthermore, we give some applications, including sparse op- timization methods, in which the proposed methods are effective. Additionally, we eval- uate 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