On Approximate Non-submodular Minimization via Tree-Structured Supermodularity

Yoshinobu Kawahara, Rishabh K. Iyer, Jeff A. BilmesAISTATS 2015 · OpenReview

Abstract

Minimizing non-submodular functions is a fundamental challenge in discrete optimization, often proving NP-hard and inapproximable. This paper identifies a tractable "sweet spot": problems where supermodular terms are restricted to a tree structure. By leveraging this structure, we evaluate four algorithmic frameworks—Alternating Minimization (AM), Dual Decomposition (DD), Continuous Relaxation (CR), and the Submodular-Supermodular Procedure (SSP). Our results demonstrate that these methods provide tight upper and lower bounds, leading to significant improvements in complex computer vision tasks such as image segmentation.

Introduction

In discrete optimization, submodular functions are highly valued for their polynomial-time minimizability, typically used to model "smoothness" or attractive forces in data. However, many real-world applications require modeling "repulsive" forces, which introduce supermodular terms. The combination of submodular and supermodular components generally makes the objective function inapproximable. This work explores the restriction of supermodularity to pairs of variables forming a tree structure, a constraint that remains NP-hard but allows for much more effective approximation than the general case.

Tree-Structured Supermodularity

The core insight of this research is the "Power of Trees." While general supermodularity is computationally prohibitive, tree-structured pairwise terms can be solved exactly and efficiently using dynamic programming. This allows the most difficult part of the objective to be handled as a manageable sub-problem. In image segmentation, while submodularity enforces smoothness (neighboring pixels having the same label), adding supermodular terms on specific edges can encourage pixels to have different labels, which is crucial for capturing thin structures or background gaps.

Illustration of tree-structured supermodular terms on a pixel grid.

Methods

The authors developed four distinct frameworks to attack the problem:

  1. Alternating Minimization (AM): Introduces an auxiliary variable and a penalty for the two variables being different. By alternating between minimizing the submodular part and the tree-structured part, it provides an upper bound. A "Greedy Scheduling" for the penalty parameter helps avoid poor local minima.
  2. Dual Decomposition (DD): Uses Lagrangian relaxation to split the problem into two sub-problems: one purely submodular and one purely tree-structured. This provides a lower bound, allowing researchers to calculate a "tightness gap."
  3. Continuous Relaxation (CR): Employs the Lovász extension to transform the discrete submodular function into a continuous convex one, solved using the Alternating Direction Method of Multipliers (ADMM).
  4. Submodular-Supermodular Procedure (SSP): A heuristic approach that iteratively replaces parts of the function with modular (linear) upper or lower bounds.

Key Results

The algorithms were evaluated on synthetic data and the MSRC image segmentation dataset. AM-Greedy and Dual Decomposition emerged as the most robust performers. In image segmentation, the proposed model successfully segmented complex objects, such as park benches, where standard submodular-only models failed by over-smoothing.

Convergence of objective values over time for various algorithms.

As shown in the performance plots, AM-Greedy consistently found superior objective values compared to simpler scheduling methods. While Continuous Relaxation is theoretically robust, it proved significantly slower and sometimes failed to converge on larger instances. By providing both upper (AM, SSP) and lower (DD, CR) bounds, the proposed frameworks allow practitioners to "sandwich the truth" and quantify the error of their approximations.

Conclusion

By focusing on tree-structured supermodularity, this work provides a practical path forward for non-submodular minimization. The ability to provide both upper and lower bounds gives practitioners a reliable way to measure performance in complex tasks. Future work may extend these techniques to higher-order structures and further optimize the computational efficiency for large-scale applications.

Summary updated

BibTeX
@inproceedings{kawahara2015approximate,
  author = {Yoshinobu Kawahara and Rishabh K. Iyer and Jeff A. Bilmes},
  title = {{On Approximate Non-submodular Minimization via Tree-Structured Supermodularity}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2015},
  url = {https://openreview.net/forum?id=AXh43c2ccW},
}
Figure