Decomposable Submodular Function Minimization via Maximum Flow

Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, Adrian Vladu
Proceedings of the 38th International Conference on Machine Learning, PMLR 139:446-456, 2021.

Abstract

This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of calls to a maximum flow oracle. When each function in the decomposition acts on O(1) elements of the ground set V and is polynomially bounded, our running time is up to polylogarithmic factors equal to that of solving maximum flow in a sparse graph with O(|V|) vertices and polynomial integral capacities. We achieve this by providing a simple iterative method which can optimize to high precision any convex function defined on the submodular base polytope, provided we can efficiently minimize it on the base polytope corresponding to the cut function of a certain graph that we construct. We solve this minimization problem by lifting the solutions of a parametric cut problem, which we obtain via a new efficient combinatorial reduction to maximum flow. This reduction is of independent interest and implies some previously unknown bounds for the parametric minimum s,t-cut problem in multiple settings.

Cite this Paper

BibTeX
@InProceedings{pmlr-v139-axiotis21a, title = {Decomposable Submodular Function Minimization via Maximum Flow}, author = {Axiotis, Kyriakos and Karczmarz, Adam and Mukherjee, Anish and Sankowski, Piotr and Vladu, Adrian}, booktitle = {Proceedings of the 38th International Conference on Machine Learning}, pages = {446--456}, year = {2021}, editor = {Meila, Marina and Zhang, Tong}, volume = {139}, series = {Proceedings of Machine Learning Research}, month = {18--24 Jul}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v139/axiotis21a/axiotis21a.pdf}, url = {https://proceedings.mlr.press/v139/axiotis21a.html}, abstract = {This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of calls to a maximum flow oracle. When each function in the decomposition acts on O(1) elements of the ground set V and is polynomially bounded, our running time is up to polylogarithmic factors equal to that of solving maximum flow in a sparse graph with O(|V|) vertices and polynomial integral capacities. We achieve this by providing a simple iterative method which can optimize to high precision any convex function defined on the submodular base polytope, provided we can efficiently minimize it on the base polytope corresponding to the cut function of a certain graph that we construct. We solve this minimization problem by lifting the solutions of a parametric cut problem, which we obtain via a new efficient combinatorial reduction to maximum flow. This reduction is of independent interest and implies some previously unknown bounds for the parametric minimum s,t-cut problem in multiple settings.} }
Endnote
%0 Conference Paper %T Decomposable Submodular Function Minimization via Maximum Flow %A Kyriakos Axiotis %A Adam Karczmarz %A Anish Mukherjee %A Piotr Sankowski %A Adrian Vladu %B Proceedings of the 38th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Marina Meila %E Tong Zhang %F pmlr-v139-axiotis21a %I PMLR %P 446--456 %U https://proceedings.mlr.press/v139/axiotis21a.html %V 139 %X This paper bridges discrete and continuous optimization approaches for decomposable submodular function minimization, in both the standard and parametric settings. We provide improved running times for this problem by reducing it to a number of calls to a maximum flow oracle. When each function in the decomposition acts on O(1) elements of the ground set V and is polynomially bounded, our running time is up to polylogarithmic factors equal to that of solving maximum flow in a sparse graph with O(|V|) vertices and polynomial integral capacities. We achieve this by providing a simple iterative method which can optimize to high precision any convex function defined on the submodular base polytope, provided we can efficiently minimize it on the base polytope corresponding to the cut function of a certain graph that we construct. We solve this minimization problem by lifting the solutions of a parametric cut problem, which we obtain via a new efficient combinatorial reduction to maximum flow. This reduction is of independent interest and implies some previously unknown bounds for the parametric minimum s,t-cut problem in multiple settings.
APA
Axiotis, K., Karczmarz, A., Mukherjee, A., Sankowski, P. & Vladu, A.. (2021). Decomposable Submodular Function Minimization via Maximum Flow. Proceedings of the 38th International Conference on Machine Learning, in Proceedings of Machine Learning Research 139:446-456 Available from https://proceedings.mlr.press/v139/axiotis21a.html.

Related Material