Reflection methods for user-friendly submodular optimization

By Stefanie Sabrina Jegelka, Francis R. Bach, Suvrit Sra. 2013

80 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Graphics and Computer-Aided Design, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Graphics and Computer-Aided Design

In Optimization & Training

Citations in the corpus

Minding the Gaps for Block Frank-Wolfe Optimization of Structured SVMs (2016, background): “B) or structured submodular optimization (Jegelka et al., 2013), among others.”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “In [109], it is assumed that one may compute efficiently the unique minimizer of 1 2‖w − z‖2 + fi(w) for any z ∈ Rp, which is equivalent to efficient orthogonal projections on the base polytope B(Fi).”
Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems (2014, background): “In general, besides tree-structured subgraphs, other types of decompositions or subproblems can be used as well (such as binary planar problems, or problems on loopy subgraphs with small tree-wi dth, for which MRF optimization can still be solved efficiently), which can lead to even tighter relaxati”
Approximation Guarantees for Adaptive Sampling (2018, background): “More broadly, there has been recent interest in machine learning to scale submodular optimization algorithms for applications over large datasets (Jegelka et al., 2011; 2013; Wei et al., 2014; Nishihara et al., 2014; Pan et al., 2014).”
TEASER: Fast and Certifiable Point Cloud Registration (2020, background): “Algorithm 3 looks for such a matrix (M̄ (t) L̄ in line (3)) using (DRS) [36], [110]–[114] (line 11-13), starting from a cleverly chosen initial guess (line 3).”
Let's Make Block Coordinate Descent Go Fast: Faster Greedy Rules, Message-Passing, Active-Set Complexity, and Superlinear Convergence (2017, background): “Other scenarios where coordinate descent and BCD methods have proven useful include matrix and tensor factorization methods [98, 96], problems involving log-determinants [82, 36], and problems involving convex extensions of sub-modular functions [37, 22].”
Parallel and Distributed Block-Coordinate Frank-Wolfe Algorithms (2014, background): “, 2012), and structured submodular minimization (Jegelka et al., 2013), among others.”