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:
- Submodular Function Minimization (SFM): A discrete problem of finding a set that minimizes the function.
- 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.
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).
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