Provable Submodular Minimization using Wolfe's Algorithm

Deeparnab Chakrabarty, Prateek Jain, Pravesh Kothari

This paper, "Provable Submodular Minimization using Wolfe’s Algorithm," bridges a long-standing gap between the practical success and theoretical understanding of one of the most popular algorithms in discrete optimization.

TL;DR

The authors provide the first convergence analysis for Wolfe’s minimum norm algorithm, proving it achieves an $O(1/t)$ approximation in $t$ iterations. By combining this with a new "robust" version of Fujishige’s theorem, they establish the first pseudo-polynomial time guarantee for the Fujishige-Wolfe algorithm, explaining why this "practitioner's favorite" works so well for submodular function minimization.

What Problem Does This Paper Address?

Submodular Function Minimization (SFM) is a cornerstone of machine learning and computer vision, appearing in tasks like image segmentation and sensor placement. A function is submodular if it satisfies the "diminishing marginal returns" property: adding an element to a small set increases the function value more than (or equal to) adding it to a larger set.

While SFM can be solved in polynomial time using the Ellipsoid method or complex combinatorial algorithms, these are often too slow or numerically unstable for real-world use. In practice, researchers use the Fujishige-Wolfe algorithm, which treats the discrete problem as a geometric one: finding the point in a specific polytope (the "base polytope") closest to the origin.

Despite being the fastest algorithm in empirical tests, Wolfe’s algorithm only had an exponential-time theoretical bound for decades. This paper addresses the mystery: Can we prove that Wolfe’s algorithm is actually efficient?

Methods

The authors’ approach is two-pronged, combining geometric convergence with discrete stability:

  1. Convergence of Wolfe’s Algorithm: Wolfe’s algorithm is an iterative procedure that maintains a "simplex" (a generalized triangle) of vertices and moves toward the origin. The authors prove that after $t$ iterations, the algorithm finds a point whose distance-squared from the origin is within $O(1/t)$ of the true minimum.
  2. Robust Fujishige’s Theorem: Fujishige’s original theorem states that if you find the exact minimum norm point of the base polytope, you can immediately identify the subset that minimizes the submodular function. The authors prove a "robust" version: you only need an approximate minimum norm point (specifically within $O(1/n^2)$) to recover the exact discrete minimizer.
  3. The "Good" Major Cycle: A technical hurdle in analyzing Wolfe's algorithm is the "minor cycles"—internal steps that simplify the current simplex. The authors introduce the concept of a "good major cycle" to prove that the algorithm makes significant, quantifiable progress toward the origin frequently enough to guarantee convergence.

Datasets

The authors evaluated their theoretical findings against empirical performance using:

  • Synthetic s-t Mincut Problems: Generated on Erdos-Renyi graphs ($p=0.8$).
  • Iwata’s "3 Groups" Function: A standard benchmark for testing the limits of SFM algorithms.
  • Simple Path Graphs: Used specifically to test how the algorithm scales as the range of function values ($F$) increases.

Key Insights and Ideas

  • Geometry Meets Combinatorics: The core "aha moment" is realizing that we don't need the geometric algorithm to be perfect. Because the underlying problem is discrete (integer-valued), once the geometric approximation is "close enough," the discrete solution snaps into place perfectly.
  • The $1/t$ Rate: The paper establishes that Wolfe’s algorithm behaves similarly to Frank-Wolfe (a popular first-order optimization method) in terms of convergence rates, despite Wolfe's algorithm being significantly more complex due to its vertex-deletion steps.
  • Theory vs. Practice Gap: The authors note that while their bound is pseudo-polynomial (it depends on the maximum value of the function, $F$), empirical tests show the algorithm often performs as if it were independent of $F$. This suggests that Wolfe's algorithm is even more robust than the current proof shows.

Key Results

  • Theoretical Bound: The Fujishige-Wolfe algorithm is proven to run in $O((n^5 EO + n^7)F^2)$ time, where $n$ is the number of elements, $EO$ is the time for one function evaluation, and $F$ is the maximum value change of the function.
  • First of its Kind: This is the first maiden convergence analysis for Wolfe’s algorithm since its inception in 1976.
  • Empirical Superiority: In head-to-head tests, the Fujishige-Wolfe algorithm significantly outperformed the best-known "strongly polynomial" combinatorial algorithm (Iwata-Orlin), especially as the problem size grew.
Empirical performance of Wolfe's algorithm vs. Iwata-Orlin, and iterations vs. F.

Limitations and Future Work

  • Pseudo-polynomial vs. Strongly Polynomial: The current proof depends on $F$ (the function values). In the world of optimization, a "strongly polynomial" bound (depending only on $n$) is the gold standard. The authors' experiments suggest a strongly polynomial bound might exist, but they haven't proven it yet.
  • High Power of $n$: The $n^7$ term in the complexity is quite high. While this is a common feature of "first" proofs for complex algorithms, refining this to a lower power of $n$ remains an open challenge.
  • Vertex Complexity: The analysis relies on the number of vertices in the polytope, which can be huge. Finding a way to bypass this dependence could lead to even tighter bounds.

Summary updated

Abstract

Owing to several applications in large scale learning and vision problems, fast submodular function minimization (SFM) has become a critical problem. Theoretically, unconstrained SFM can be performed in polynomial time (Iwata and Orlin 2009), however these algorithms are not practical. In 1976, Wolfe proposed an algorithm to find the minimum Euclidean norm point in a polytope, and in 1980, Fujishige showed how Wolfe's algorithm can be used for SFM. For general submodular functions, the Fujishige-Wolfe minimum norm algorithm seems to have the best empirical performance. Despite its good practical performance, theoretically very little is known about Wolfe's minimum norm algorithm -- to our knowledge the only result is an exponential time analysis due to Wolfe himself. In this paper we give a maiden convergence analysis of Wolfe's algorithm. We prove that in t iterations, Wolfe's algorithm returns a O(1/t)-approximate solution to the min-norm point. We also prove a robust version of Fujishige's theorem which shows that an O(1/n^2)-approximate solution to the min-norm point problem implies exact submodular minimization. As a corollary, we get the first pseudo-polynomial time guarantee for the Fujishige-Wolfe minimum norm algorithm for submodular function minimization. In particular, we show that the min-norm point algorithm solves SFM in O(n^7F^2)-time, where $F$ is an upper bound on the maximum change a single element can cause in the function value.
BibTeX
@inproceedings{chakrabarty2014provable,
  author = {Deeparnab Chakrabarty and Prateek Jain and Pravesh Kothari},
  title = {{Provable Submodular Minimization using Wolfe's Algorithm}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2014},
  url = {https://openreview.net/forum?id=y4qSvU1Mkwv},
}
Figure