Reflection methods for user-friendly submodular optimization


October 15, 2013


Francis Bach


ENS Paris, France


Recently, it has become evident that submodularity naturally captures widely occurring concepts in machine learning, signal processing and computer vision. In consequence, there is need for efficient optimization procedures for submodular functions, in particular for minimization problems. While general submodular minimization is challenging, we propose a new approach 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 approach is a formulation of the discrete submodular minimization problem as a continuous best approximation problem. It is solved through a sequence of reflections and its solution can be automatically thresholded to obtain an optimal discrete solution. Our method solves both the continuous and discrete formulations of the problem, and therefore has applications in learning, inference, and reconstruction. In our experiments, we show the benefits of our new algorithms for two image segmentation tasks (joint work with Stefanie Jegelka and Suvrit Sra)


Francis Bach

A graduate of Ecole Polytechnique and an engineering graduate of X-Mines, Francis Bach has a M.Phil. in applied mathematics from the Ecole normale supérieure (ENS) in Cachan. He wrote an award-winning thesis on machine learning at the computer science department of the University of California (Berkeley). In 2005, he joined the Ecole des Mines, then in 2007 the ENS in Paris, from which he is seconded to Inria Paris – Rocquencourt and its Willow project team. In 2011, he created his own team, Sierra. He is a member of the peer-review committees of prestigious international journals. His numerous articles are considered references in the field.