Learning with Submodular Functions: A Convex Optimization Perspective

By Francis R. Bach. 2011

530 citations recorded by the source corpus.

Submodular functions are relevant to machine learning for at least two reasons: (1) some problems may be expressed directly as the optimization of submodular functions and (2) the Lovsz extension of submodular functions provides a useful set of regularization functions for supervised and unsupervised learning. In Learning with Submodular Functions: A Convex Optimization Perspective, the theory of submodular functions is presented in a self-contained way from a convex analysis perspective, presenting tight links between certain polyhedra, combinatorial optimization and convex optimization problems. In particular, it describes how submodular function minimization is equivalent to solving a wide variety of convex optimization problems. This allows the derivation of new efficient algorithms for approximate and exact submodular function minimization with theoretical guarantees and good practical performance. By listing many examples of submodular functions, it reviews various applications to machine learning, such as clustering, experimental design, sensor placement, graphical model structure learning or subset selection, as well as a family of structured sparsity-inducing norms that can be derived and used from submodular functions. Learning with Submodular Functions: A Convex Optimization Perspective is an ideal reference for researchers, scientists, or engineers with an interest in applying submodular functions to machine learning problems.

Subfields: Artificial Intelligence, Computational Mechanics, Computational Theory and Mathematics, Mathematical Optimization

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 Mechanics

In Computational Theory and Mathematics

In Mathematical Optimization

Citations in the corpus

On the Equivalence between Herding and Conditional Gradient Algorithms (2012, neutral): “Finally, in order to minimize the number of iterations, a variant known as the minimum-norm-point algo-rithm will ﬁnd g t +1 that minimizes J on the convex hull of all previously visited points, using a speciﬁc active-set algorithm (see Bach, 2011, Sec.”
Machine Teaching: An Inverse Problem to Machine Learning and an Approach Toward Optimal Education (2015, methodology): “Discrete optimization methods, such as those based on submodularity, may be applicable here (Krause and Golovin 2014; Iyer and Bilmes 2013; Bach 2013; Feige 1998; Krause and Guestrin 2005; Nemhauser, Wolsey, and Fisher 1978).”
On the Global Linear Convergence of Frank-Wolfe Optimization Variants (2015, methodology): “We clarify several variants of the Frank-Wolfe algorithm and show that they all converge linearly for any strongly convex function optimized over a polytope domain, with a constant bounded away from zero that only depends on the geometry of the polytope.”
Fast and Flexible Monotonic Functions with Ensembles of Lattices (2016, background): “A long-standing challenge in machine learning is to learn flexible monotonic functions [1] for classification, regression, and ranking problems.”
Structured sparsity through convex optimization (2011, methodology): “This idea can be further extended to symmetric, submodular set-functions of the level sets of w, that is, w 7→ maxν∈R F ({j ∈ J1; pK; wj ≥ ν}), thus leading to different types of structures (Bach, 2011), allowing to shape the level sets of w rather than its support.”
Revisiting Frank-Wolfe: Projection-Free Sparse Convex Optimization (2013, methodology): “Submodular optimization is currently gaining increased interest as a more general way to relate combinatorial problems to convexity, such as for example for structured sparsity, see e.g. (Bach, 2011).”
Unsupervised Image Matching and Object Discovery as Optimization (2019, methodology): “Once the dual problem is solved, as argued by Nedić & Ozdaglar [35] and Bach [3], an approximate solution of the primal problem can be found as a running average of the primal sequence (xt, et) generated as a by-product of the sub-gradient method: x̂ = 1 T T−1∑ t=0 xt, ê = 1 T T−1∑ t=0 et (11) aft”
Taking Human out of Learning Applications: A Survey on Automated Machine Learning (2018, background): “s the global optimum in a reasonable time cost. Besides, such good empirical performance is also theoretically justiﬁed in many applications, e.g., feature selection [125] and submodular optimization [126]. candidate decisions optimizer generate candidate decisions evaluator evaluate candidate decis”
Reflection methods for user-friendly submodular optimization (2013, unknown): “A longer list of examples may be found in [1].”
Fast Differentiable Sorting and Ranking (2020, unknown): “The polytope is defined as (see, e.g., Bach (2013)) B(F ) := { µ ∈ Rn : ∑ i∈S µi ≤ F (S) ∀S ⊆ [n], n∑ i=1 µi = F ([n]) } .”