Decomposable Submodular Function Minimization via Maximum Flow

Kyriakos Axiotis, Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, Adrian Vladu

TL;DR

This paper presents a novel approach to optimize decomposable submodular functions by reducing the problem to maximum flow computations. The authors achieve significant improvements in running time, matching state-of-the-art maximum flow algorithms for certain problem settings, and introduce new bounds for parametric minimum cut problems.

What Problem Does This Paper Address?

Submodular function minimization is a fundamental problem with wide applications in machine learning (e.g., MAP inference, image segmentation) and combinatorial optimization. While efficient algorithms exist, the increasing scale of real-world problems necessitates further improvements. A key observation is that many practical submodular functions are "decomposable," meaning they can be expressed as a sum of simpler submodular functions. This structure, combined with recent advances in continuous optimization and maximum flow algorithms, raises the question: can we leverage these new techniques to achieve faster submodular minimization? This paper tackles this by bridging discrete and continuous optimization approaches for decomposable submodular functions, particularly in the more general parametric setting.

Methods

The core of the paper's contribution lies in a novel reduction from decomposable submodular function minimization to a series of maximum flow computations. Instead of directly applying existing maximum flow algorithms, the authors first tackle the problem in a more general parametric setting. This involves optimizing a function with an additional parameter-dependent penalty term. To solve this, they reduce it to a parametric minimum cut problem.

A key innovation is a new combinatorial algorithm for solving this parametric minimum cut problem. This algorithm efficiently uses a maximum flow oracle and provides improved bounds, even for specific graph structures like planar graphs. The authors then use this to optimize a convex function over a "submodular base polytope," which is a geometric representation of submodular functions. Their approach iteratively refines a solution by leveraging the structure of the problem and the efficiency of the parametric min-cut solver.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Bridging Discrete and Continuous Optimization: The paper successfully connects discrete combinatorial optimization (submodular minimization, max-flow) with continuous optimization techniques (convex optimization on polytopes).
  • Parametric Setting as a Key Enabler: By framing the problem in a parametric setting, the authors unlock new algorithmic possibilities and achieve stronger results than directly addressing the standard minimization problem.
  • Parametric Min-Cut as a Powerful Subroutine: The development of an efficient algorithm for the parametric minimum cut problem is a significant contribution in itself, with implications beyond submodular minimization.
  • Leveraging Graph Structure for Efficiency: The authors demonstrate how properties of specific graph structures (like planarity) can be exploited to achieve even better algorithmic bounds.

Key Results

The paper presents a new algorithm for decomposable submodular function minimization that, in certain settings (e.g., when decomposition functions act on O(1) elements), achieves running times comparable to state-of-the-art maximum flow algorithms. Specifically, for polynomially bounded functions acting on O(1) elements, the running time is polylogarithmic factors away from solving maximum flow in a sparse graph.

The authors also establish new bounds for the parametric minimum s,t-cut problem, including:

  • Near-optimal weakly-polynomial time algorithms.
  • Improved bounds for strongly polynomial and planar graph settings.
  • A strongly polynomial exact algorithm for planar graphs with linear capacity functions running in $O(n^{1.21875})$ time.

Limitations and Future Work

The authors acknowledge that their algorithm's performance depends on the efficiency of the maximum flow oracle and the complexity of evaluating the individual submodular functions. While they achieve significant improvements, further research could explore even faster maximum flow algorithms or specialized techniques for specific types of submodular functions. The paper also suggests that their parametric min-cut reduction could have broader applications in other combinatorial optimization problems.

Summary updated

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(\vert V \vert)$ 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.
BibTeX
@inproceedings{axiotis2021decomposable,
  author = {Kyriakos Axiotis and Adam Karczmarz and Anish Mukherjee and Piotr Sankowski and Adrian Vladu},
  title = {{Decomposable Submodular Function Minimization via Maximum Flow}},
  booktitle = {International Conference on Machine Learning},
  year = {2021},
  url = {https://openreview.net/forum?id=SM---wSVbc},
}
Figure