Provable Submodular Minimization using Wolfe's Algorithm
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 [10,11]. However, these algorithms are typically not practical. In 1976, Wolfe [21]  proposed an algorithm to find the minimum Euclidean norm point in a polytope, and in 1980, Fujishige [3]  showed how Wolfe's algorithm can be used for SFM. For general submodular functions, this Fujishige-Wolfe minimum norm algorithm seems to have the best empirical performance.
Despite its good practical performance, very little is known about Wolfe's minimum norm algorithm theoretically. To our knowledge, the only result is an exponential time analysis due to Wolfe [21]  himself. In this paper we give a maiden convergence analysis of Wolfe's algorithm. We prove that in t iterations, Wolfe's algorithm returns an O(1/t)-approximate solution to the min-norm point on any polytope. 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 on the base polytope implies exact submodular minimization. As a corollary, we get the first pseudo-polynomial time guarantee for the Fujishige-Wolfe minimum norm algorithm for unconstrained submodular function minimization.
The present paper gives a version of the Fujishige-Wolfealgorithm for submodular function minimization and shows itspseudo-polynomial time complexity.The Fujishige-Wolfe algorithm has been widely used and runsefficiently in practice, but the problem of determining itsalgorithmic complexity has been open until now.The pseudo-polynomiality result of the present paper is thefirst big step toward determining its exact complexity.Comments (mostly minor ones) are listed below.Major ones are Comments 11 and 13. Comments 1 and 8 are medium.(Three-digit numbers denote the corresponding lines in thetext.)----------------------------------------------1. 055-056: Iwata and Orlin's algorithm [11] is not thefastest. Orlin's algorithm published in MathematicalProgramming, Ser.A, Vol.118 (2009), pp.237-251 is currently thefastest and runs in O(n^5EO + n^6) time where EO denotes thetime for the function evaluation oracle.2. 066: Here should be mentioned the relation between $n$ and$X$, which will appear on Line 105.3. 093: $F$ should be defined here.4. 095: `the Wolfe's' should be read `the Wolfe' or  `Wolfe's.'5. 107: `for any two' should be read `for all two' (within the``if'' clause).6. 109: `to find the set' should be read `to find a set.'7. 138: `for a subset' should be read `for an affinelyindependent subset.'8. 176: The inequality at the end of this line can be  $N_{\rm min} \le N_{\rm maj}$ without factor $n$,   since $N_{\rm maj}-N_{\rm min} \ge {\rm the dimension of the final $S$}.9. 178: The factor $n$ can be removed (due to the previouscomment).10. 213-214: The comment starting with ``Observe that …'' is not precise (or invalid), which should be removed. It is actuallyirrelevant to the present proof.11. 263: I cannot see $t=32Q^2/\epsilon^2$, but can only see$t=32Q^4/\epsilon^4$, which is much larger than the former.(Please check it carefully. I could be wrong. Any short proofof it would be useful for readers.) This would affect thecomplexity estimation all through the rest.Also the present $t$ and the one appearing before havedifferent meanings; the two should be distinguished.12. 316: `(abusing notation) is' should be read `(abusingnotation) that is.'13. 359 (Theorem 7): When $2n\epsilon < 1$, we can finda set $S$ in Theorem 7 without any oracle call by setting$S=\{ i \mid x_i < -1/(2n) \}$.(Compare the rounding technique proposed in Fujishige andIsotani's paper [7]. (See the remark below Theorem 3.3 andequations (3.11) and (3.12) on Page 7 in [7]. Note that we alsohave $||x - x_*|| \le \epsilon$.)Theorem 7 itself is still correct.14. 375: `at least $\epsilon^2$' should be read `at least$-\epsilon^2$.'15. 409: Check the complexity. See Comment 11.----------------------------------------------------------------