Active-set Methods for Submodular Minimization Problems

K.s. Kumar, Francis BacharXiv 2015 · DOI · arXiv

Abstract

We consider the submodular function minimization (SFM) and the quadratic minimization problems regularized by the Lovász extension of the submodular function. These optimization problems are intimately related; for example, min-cut problems and total variation denoising problems, where the cut function is submodular and its Lovász extension is given by the associated total variation. We propose a new active-set algorithm for total variation denoising with the assumption of an oracle that solves the corresponding SFM problem. This can be seen as a local descent algorithm over ordered partitions with explicit convergence guarantees. It is more flexible than existing algorithms, offering the ability for warm-restarts using the solution of a closely related problem. Further, we consider decomposable submodular functions and propose a new active-set algorithm for total variation denoising that performs local descent over ordered partitions, significantly improving performance through warm-starts.

Introduction

Submodular functions are mathematical structures that capture the "diminishing returns" property, making them ubiquitous in machine learning, computer vision, and signal processing. They appear in diverse applications such as image segmentation (graph cuts) and document summarization.

Optimization typically involves two related problems:

  1. Submodular Function Minimization (SFM): A discrete problem of finding a set that minimizes the function.
  2. Total Variation (TV) Denoising: A continuous problem where a quadratic loss is regularized by the Lovász extension of the submodular function.

While these problems are theoretically linked, existing algorithms often lack flexibility. Generic solvers can be slow, and specialized algorithms for decomposable problems (where a complex function is a sum of simpler ones) often require expensive "TV oracles." This work bridges the gap by introducing a fast, flexible active-set algorithm that solves the continuous TV problem using only simpler, discrete SFM oracles.

Methodology

The core of the proposed approach lies in exploiting the geometric structure of the base polytope $B(F)$ associated with a submodular function $F$. The TV denoising problem is treated as an orthogonal projection of a vector $u$ onto this polytope.

Geometry and Ordered Partitions

The algorithm maintains an "ordered partition" of the ground set. Geometrically, an ordered partition defines a specific face or a tangent cone of the base polytope. Instead of searching the exponential space of all possible constraints, the algorithm navigates these partitions.

The base polytope $B(F)$ and its vertices labeled with corresponding ordered partitions.

Active-set Algorithm

The algorithm performs a local descent over these partitions. At each step, it projects the target vector onto the tangent cone defined by the current ordered partition. This projection step is computationally efficient and can be solved in linear time using isotonic regression (specifically the Pool-Adjacent Violators Algorithm).

Projections onto different tangent cones defined by ordered partitions.

If the current projection is not optimal, an SFM oracle is called to identify "violating constraints." These constraints are then used to refine the partition, splitting sets to move closer to the optimal solution. For decomposable functions $F = F_1 + F_2$, the authors utilize a "translated Dykstra" approach, alternating projections between translated polytopes. This framework significantly benefits from the active-set method's ability to handle warm-starts.

Experimental Evaluation

The algorithms were evaluated on standard benchmarks, including 2D image grids (up to 20 million pixels), 3D volumetric data (the "Stanford Bunny"), and synthetic decomposable problems.

Key Results

  • Oracle Efficiency: In 2D image experiments, the proposed method required significantly fewer SFM oracle calls than the standard Chambolle and Darbon (2009) algorithm as pixel counts increased.
  • Warm-Start Advantages: A unique feature of this method is the ability to start from a previously found solution. When solving for a range of regularization weights $\lambda$, warm-starting reduced iterations by 60-70% compared to starting from scratch.
  • Decomposable Performance: On the 3D Stanford Bunny dataset, the active-set method (ACTIVE) converged much faster and with orders of magnitude fewer oracle calls than standard subgradient descent (SGD-P) or basic alternating reflections (AAR).

Conclusion

This paper presents a novel active-set framework for submodular minimization that effectively bridges discrete and continuous optimization. By leveraging the geometry of ordered partitions and enabling efficient warm-starts, the method offers superior performance in terms of oracle call efficiency. While the primary bottleneck remains the inversion of Laplacian matrices in decomposable cases, the flexibility and speed of this approach make it a powerful tool for large-scale submodular optimization problems.

Summary updated

Abstract

We consider the submodular function minimization (SFM) and the quadratic minimization problemsregularized by the Lov'asz extension of the submodular function. These optimization problemsare intimately related; for example,min-cut problems and total variation denoising problems, wherethe cut function is submodular and its Lov'asz extension is given by the associated total variation.When a quadratic loss is regularized by the total variation of a cut function, it thus becomes atotal variation denoising problem and we use the same terminology in this paper for "general" submodularfunctions. We propose a new active-set algorithm for total variation denoising with theassumption of an oracle that solves the corresponding SFM problem. This can be seen as localdescent algorithm over ordered partitions with explicit convergence guarantees. It is more flexiblethan the existing algorithms with the ability for warm-restarts using the solution of a closely relatedproblem. Further, we also consider the case when a submodular function can be decomposed intothe sum of two submodular functions F1 and F2 and assume SFM oracles for these two functions.We propose a new active-set algorithm for total variation denoising (and hence SFM by thresholdingthe solution at zero). This algorithm also performs local descent over ordered partitions and itsability to warm start considerably improves the performance of the algorithm. In the experiments,we compare the performance of the proposed algorithms with state-of-the-art algorithms, showingthat it reduces the calls to SFM oracles.
BibTeX
@misc{kumar2015active,
  author = {K.S. Kumar and Francis Bach},
  title = {{Active-set Methods for Submodular Minimization Problems}},
  year = {2015},
  eprint = {1506.02852},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1506.02852},
}
Figure