Reflection methods for user-friendly submodular optimization
Recently, it has become evident that submodularity naturally captures widely occurring concepts in machine learning, signal processing and computer vision. Consequently, there is need for efficient optimization procedures for submodular functions, especially for minimization problems. While general submodular minimization is challenging, we propose a new method that exploits existing decomposability of submodular functions. In contrast to previous approaches, our method is neither approximate, nor impractical, nor does it need any cumbersome parameter tuning. Moreover, it is easy to implement and parallelize. A key component of our method is a formulation of the discrete submodular minimization problem as a continuous best approximation problem that is solved through a sequence of reflections, and its solution can be easily thresholded to obtain an optimal discrete solution. This method solves both the continuous and discrete formulations of the problem, and therefore has applications in learning, inference, and reconstruction. In our experiments, we illustrate the benefits of our method on two image segmentation tasks.
Summary of ideas: There is a previously known 
      proximal problem, whose minimization gives at least as much information 
      than minimizing the Lovasz extension. When a submodular function is 
      written as a sum of submodular functions, each relatively easy to solve, 
      solving the dual for the proximal problem can be done in terms of 
      projections, rather than posing non-smooth functions as previous methods 
      do. Evaluation: The paper presents a refined way of 
      dealing with submodular functions that are additively decomposable into 
      simpler functions, by novel dual decompositions of a less well known use 
      of the Lovasz extension. These allow the decomposition to proceed 
      without some of the complications arising due to non-smoothness in 
      previous approaches. The empirical evaluation using examples from image 
      processing shows promising results. The paper is very clear in 
      describing its predecessors; unfortunately, this seems to leave 
      insufficient space to be more than sketchy about the novel techniques. 
      For example, one of the important technical contributions is to show 
      how the DR variant of reference [5] is applicable to dual (9), which is 
      specialized for a sum of 2 functions; but [5] focuses on two functions as 
      well, and how exactly to apply these algorithms for r > 2 is not clear 
      to me, despite such results being reported as useful in the experimental 
      evaluation section under the name DR-para. We certainly do not know 
      iteration complexity depends of r. In another example, any detailed 
      description of the third main contribution is essentially deferred to the 
      supplementary material (which formally states neither an algorithm nor a 
      theorem). Pros: - Decomposable submodular functions arise in 
      applications, and more appropriate ways to minimize them are useful. - 
      The novel duals might spur further work on algorithms for their solution, 
      beyond the algorithms proposed here. Cons: - While iteration and 
      computational complexity bounds are treated as limitations of previous 
      results, the novel optimization problems and algorithms are not 
      accompanied by corresponding iteration complexity results. While a full 
      analysis can be deferred to future work, some understanding of how r 
      affects complexity under the different algorithms is missing. - The 
      presentation of the algorithms (as opposed to duals) is not clear enough. 
      Detailed comments: - 072 "the level set {k, x_k^* \ge 0} of 
      ... x^*" is not very clear, is {k | x_k^* \ge 0} meant? Ref [2] refers to 
      many different problems, a more specific reference for the fact being 
      mentioned would be useful. - 088 Should reference section 3 where you 
      give some examples in which this decomposition holds, and an idea of what 
      types of "simplicity" we might encounter for the summand functions would 
      be nice. - 116 The notation a(A) where a\in R^n and A\subseteq V does 
      not seem to be introduced anywhere. - 117 This is misleading: Section 
      2 punts to the Supplementary material, which also skimps on explicit 
      detail. - 138 computed the -> computed by the - 156 The term 
      "discrete gaps" are used here and elsewhere but not clearly defined. The 
      duality gaps of F(A) and a particular dual problem? Similarly for smooth 
      gaps. - 170 "In the appendix.." An explicit algorithm should be 
      accompanied by a lemma and proof giving its complexity. Neither is 
      present, in the paper nor in the supplementary material. - "problems 
      have size 640x427. Hence ... have r = 640 + 247" either there is a typo 
      (427 to 247), or the relationship is not clear enough. Also, it is worth 
      explaining how and why you "solve as r=2/3". - Figure 2: - 
      Inconsistencies of vertical and horizontal axes makes comparisons 
      difficult. - "From top to bottom: four different images" presumably 2 
      different images. A wider benchmark - Figure 3: - Does "non-smooth 
      problems" not correspond to the previously existing duals? the legends 
      suggest that the new duals are being used. - Empirical evaluation in 
      general: comparisons of convergence in terms of iteration counts are 
      informative only when iteration costs are roughly comparable. Are they?