Decomposable Submodular Function Minimization via Maximum Flow (Kyriakos Axiotis)

Submodular function minimization is a primitive that is extensively used in a lot of ML applications, including MAP inference in MRFs, image segmentation, and clustering. Although polynomial-time algorithms for this problem exist, their runtime is prohibitive for large scale applications. Fortunately, in practice it is often the case that the function can be decomposed as a sum of r simpler functions, each acting on a small number of elements, k. We present an algorithm that can solve this problem (as well as the more general parametric problem) in time O((n+r)^(1.497) poly(k)), where n is the number of elements in the ground set. Perhaps surprisingly, we achieve this by O~(poly(k)) calls to a maximum flow oracle, thus reducing a problem that is unrelated to graphs to a graph problem. In fact, if max flow is solvable in near-linear time and k=O(1), our algorithm runs in near-linear time. At a technical level, we develop a dual iterative method that computes each step by approximating the submodular base polytope by a graph cut polytope. To solve the resulting graph problem, we develop an efficient algorithm for the parametric min cut problem, which might also be of independent interest.
Joint work with Adam Karczmarz, Anish Mukherjee, Piotr Sankowski, and Adrian Vladu