# Learning with Submodular Functions: A Convex Optimization Perspective

@article{Bach2013LearningWS, title={Learning with Submodular Functions: A Convex Optimization Perspective}, author={Francis R. Bach}, journal={ArXiv}, year={2013}, volume={abs/1111.6453} }

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… Expand

#### Supplemental Video

#### Figures, Tables, and Topics from this paper

figure 11.1 figure 12.1 figure 12.10 figure 12.11 figure 12.12 figure 12.2 figure 12.3 figure 12.4 figure 12.5 figure 12.6 figure 12.7 figure 12.8 figure 12.9 figure 2.1 figure 2.2 figure 2.3 figure 3.2 figure 3.3 figure 3.4 figure 4.1 figure 4.2 figure 5.1 figure 5.2 figure 5.3 figure 5.4 figure 5.5 figure 5.6 figure 6.1 figure 6.10 figure 6.11 figure 6.2 figure 6.3 figure 6.4 figure 6.5 figure 6.6 figure 6.7 figure 6.8 figure 6.9 figure 7.1 figure 7.2 figure 7.3 figure 7.4 figure 7.5 figure 8.1 figure 8.2 figure 9.1 figure 9.2 figure A.1 table A.1 figure A.2

#### Paper Mentions

#### 362 Citations

Learning and Optimization with Submodular Functions

- Mathematics, Computer Science
- ArXiv
- 2015

The formal definition of submodularity is reviewed; the optimization of sub modular functions, both maximization and minimization are reviewed; and some applications in relation to learning and reasoning using submodular functions are discussed. Expand

Convex Analysis for Minimizing and Learning Submodular Set Functions

- Mathematics
- 2013

The connections between convexity and submodularity are explored, for purposes of minimizing and learning submodular set functions. First, we develop a novel method for minimizing a particular class… Expand

Submodular functions: from discrete to continuous domains

- Computer Science, Mathematics
- Math. Program.
- 2019

This paper shows that most results relating submodularity and convexity for set-functions can be extended to all submodular functions, and provides practical algorithms which are based on function evaluations, to minimize generic sub modular functions on discrete domains, with associated convergence rates. Expand

Quadratic Decomposable Submodular Function Minimization: Theory and Practice

- 2020

We introduce a new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs. The… Expand

Quadratic Decomposable Submodular Function Minimization: Theory and Practice

- Computer Science, Mathematics
- J. Mach. Learn. Res.
- 2020

A new convex optimization problem, termed quadratic decomposable submodular function minimization (QDSFM), which allows to model a number of learning tasks on graphs and hypergraphs and two new applications of QDSFM are described: hypergraph-adapted PageRank and semi-supervised learning. Expand

Active-set Methods for Submodular Minimization Problems

- Mathematics, Computer Science
- J. Mach. Learn. Res.
- 2017

A new active-set algorithm for total variation denoising with the assumption of an oracle that solves the corresponding SFM problem is proposed, which performs local descent over ordered partitions and its ability to warm start considerably improves the performance of the algorithm. Expand

Distributed Submodular Minimization And Motion Coordination Over Discrete State Space

- Mathematics
- 2017

We develop a framework for the distributed minimization of submodular functions. Submodular functions are a discrete analog of convex functions and are extensively used in large-scale combinatorial… Expand

High-performance submodular function minimization

- Computer Science
- 2012

A highperformance submodular function minimization (HPSFO) algorithm that reaches up to 90% of Vector peak performance, offers parallel speed up and outperforms all the existing tested implementations by not one but several orders of magnitude and for the three workload applications the authors implemented and that scales reasonably well with respect to the problem sizes. Expand

Submodular Optimization and Machine Learning: Theoretical Results, Unifying and Scalable Algorithms, and Applications

- Computer Science
- 2015

This dissertation explores a class of unifying and scalable algorithms for a number of submodular optimization problems, and connects them to several machine learning applications, and empirically demonstrates the applicability of these techniques on several synthetic and real world problems. Expand

Maximizing submodular functions using probabilistic graphical models

- Computer Science, Mathematics
- ArXiv
- 2013

This paper proposes a novel convex relaxation which is based on the relationship between submodular functions, entropies and probabilistic graphical models, and presents extensions to constrained problems and maximizing the difference of submodularity functions, which include all possible set functions. Expand

#### References

SHOWING 1-10 OF 246 REFERENCES

Structured sparsity-inducing norms through submodular functions

- Computer Science, Mathematics
- NIPS
- 2010

This paper shows that for nondecreasing submodular set-functions, the corresponding convex envelope can be obtained from its Lovasz extension, a common tool in sub modular analysis, and defines a family of polyhedral norms, for which it provides generic algorithmic tools and theoretical results. Expand

Efficient Minimization of Decomposable Submodular Functions

- Computer Science, Mathematics
- NIPS
- 2010

This paper develops an algorithm, SLG, that can efficiently minimize decomposable submodular functions with tens of thousands of variables, and applies it to synthetic benchmarks and a joint classification-and-segmentation task, and shows that it outperforms the state-of-the-art general purpose sub modular minimization algorithms by several orders of magnitude. Expand

Maximizing submodular functions using probabilistic graphical models

- Computer Science, Mathematics
- ArXiv
- 2013

This paper proposes a novel convex relaxation which is based on the relationship between submodular functions, entropies and probabilistic graphical models, and presents extensions to constrained problems and maximizing the difference of submodularity functions, which include all possible set functions. Expand

Approximating submodular functions everywhere

- Computer Science, Mathematics
- SODA
- 2009

The problem of approximating a non-negative, monotone, submodular function f on a ground set of size n everywhere is considered, after only poly(n) oracle queries, and it is shown that no algorithm can achieve a factor better than Ω(√n/log n), even for rank functions of a matroid. Expand

Shaping Level Sets with Submodular Functions

- Computer Science, Mathematics
- NIPS
- 2011

By selecting specific submodular functions, this work gives a new interpretation to known norms, such as the total variation, and defines new norms, in particular ones that are based on order statistics with application to clustering and outlier detection, and on noisy cuts in graphs withApplication to change point detection in the presence of outliers. Expand

Submodularity Cuts and Applications

- Computer Science, Mathematics
- NIPS
- 2009

This work presents a novel algorithm for maximizing a submodular set function under a cardinality constraint based on a cutting-plane method and implemented as an iterative small-scale binary-integer linear programming procedure. Expand

A Submodular-supermodular Procedure with Applications to Discriminative Structure Learning

- Computer Science, Mathematics
- UAI
- 2005

This paper presents an algorithm for minimizing the difference between two submodular functions using a variational framework which is based on (an extension of) the concave-convex procedure, and gives a polynomial time heuristic for it. Expand

Learning submodular functions

- Computer Science, Mathematics
- STOC '11
- 2011

This paper considers PAC-style learning of submodular functions in a distributional setting and uses lossless expanders to construct a new family of matroids which can take wildly varying rank values on superpolynomially many sets; no such construction was previously known. Expand

Maximizing a class of submodular utility functions

- Mathematics, Computer Science
- Math. Program.
- 2011

This paper performs a polyhedral analysis of a relevant mixed-integer set and exploits the structure of the utility function h to strengthen the standard submodular formulation significantly, and shows the effectiveness of the new formulation on expected utility maximization in capital budgeting. Expand

Optimization with Sparsity-Inducing Penalties (Foundations and Trends(R) in Machine Learning)

- Mathematics
- 2011

Sparse estimation methods are aimed at using or obtaining parsimonious representations of data or models. They were first dedicated to linear variable selection but numerous extensions have now… Expand