On the Convergence Rate of Decomposable Submodular Function Minimization
Submodular functions describe a variety of discrete problems in machine learning, signal processing, and computer vision. However, minimizing submodular functions poses a number of algorithmic challenges. Recent work introduced an easy-to-use, parallelizable algorithm for minimizing submodular functions that decompose as the sum of "simple" submodular functions. Empirically, this algorithm performs extremely well, but no theoretical analysis was given. In this paper, we show that the algorithm converges linearly, and we provide upper and lower bounds on the rate of convergence. Our proof relies on the geometry of submodular polyhedra and draws on results from spectral graph theory.
Eq. (3): what if the maximization problem is unbounded?Line 216: the phrase "intimately related" suggests that $\kappa^*$ completely determines the convergence rate. But what Theorem 2 shows is that $\kappa^*$ only upper bounds the convergence rate, which is a weaker property.Line 324: "the analysis in this case subsumes the analysis in the general case". Can you elaborate this argument?I am curious, would you get better bounds if you assumed that functions F_i depend only on variables in some small subset of V?Suggestions on the presentation:- you use the word "subspace" throughout the paper. This is a very general term, I would suggest to use "linear subspace" to remove potential ambiguities.- in Corollary 8 you could add that this set can be equivalently described by equalities $s(A_i)=0$, then you wouldn't need matrix T'.- In lines 305 and 310 you use aff(A_x). It could be better to use aff_0(A_x), since that's how the convergence results (e.g. Corollary 5) are formulated.I think it is important to state in the abstract which specific method you analyze (with a reference), and your main result, i.e. the convergence rate that you obtain.