Convex Analysis and Optimization with Submodular Functions: a Tutorial

Abstract

Set-functions appear in many areas of computer science and applied mathematics, such as machine learning, computer vision, operations research or electrical networks. Among these set-functions, submodular functions play an important role, similar to convex functions on vector spaces. In this tutorial, the theory of submodular functions is presented, in a self-contained way, with all results shown from first principles. A good knowledge of convex analysis is assumed.

References in corpus (2)

• Near-optimal Nonmyopic Value of Information in Graphical Models
• Network Flow Algorithms for Structured Sparsity

Cited by in corpus (12)

• Structured sparsity-inducing norms through submodular functions
• Provable Submodular Minimization using Wolfe's Algorithm
• A Convex Formulation for Learning Scale-Free Networks via Submodular Relaxation
• Tight Bounds for Approximate Carathéodory and Beyond
• Stochastic Submodular Maximization: The Case of Coverage Functions
• Structured Sparse Regression via Greedy Hard-Thresholding
• Polynomial-Time Algorithms for Submodular Laplacian Systems
• A Submodularity-based Agglomerative Clustering Algorithm for the Privacy Funnel
• Quantifying and Reducing Bias in Maximum Likelihood Estimation of Structured Anomalies
• Developing Non-Stochastic Privacy-Preserving Policies Using Agglomerative Clustering
• Basic facts concerning supermodular functions
• An Algorithmic Theory of Dependent Regularizers, Part 1: Submodular Structure