Submodular Functions: from Discrete to Continous Domains

Abstract

Submodular set-functions have many applications in combinatorial optimization, as they can be minimized and approximately maximized in polynomial time. A key element in many of the algorithms and analyses is the possibility of extending the submodular set-function to a convex function, which opens up tools from convex optimization. Submodularity goes beyond set-functions and has naturally been considered for problems with multiple labels or for functions defined on continuous domains, where it corresponds essentially to cross second-derivatives being nonpositive. In this paper, we show that most results relating submodularity and convexity for set-functions can be extended to all submodular functions. In particular, (a) we naturally define a continuous extension in a set of probability measures, (b) show that the extension is convex if and only if the original function is submodular, (c) prove that the problem of minimizing a submodular function is equivalent to a typically non-smooth convex optimization problem, and (d) propose another convex optimization problem with better computational properties (e.g., a smooth dual problem). Most of these extensions from the set-function situation are obtained by drawing links with the theory of multi-marginal optimal transport, which provides also a new interpretation of existing results for set-functions. We then provide practical algorithms to minimize generic submodular functions on discrete domains, with associated convergence rates.

References in corpus (2)

• On the Global Linear Convergence of Frank-Wolfe Optimization Variants
• Scalable Variational Inference in Log-supermodular Models

Cited by in corpus (17)

• Quantum machine learning: a classical perspective
• Guaranteed Non-convex Optimization: Submodular Maximization over Continuous Domains
• Online Continuous Submodular Maximization
• Gradient Methods for Submodular Maximization
• Projection-Free Online Optimization with Stochastic Gradient: From Convexity to Submodularity
• Near-Optimal Discrete Optimization for Experimental Design: A Regret Minimization Approach
• Decentralized Submodular Maximization: Bridging Discrete and Continuous Settings
• One Sample Stochastic Frank-Wolfe
• Optimal DR-Submodular Maximization and Applications to Provable Mean Field Inference
• Continuous DR-submodular Maximization: Structure and Algorithms
• Conditional Gradient Method for Stochastic Submodular Maximization: Closing the Gap
• Structured Optimal Transport
• Efficient Algorithms for Non-convex Isotonic Regression through Submodular Optimization
• Submodularity on Hypergraphs: From Sets to Sequences
• Submodular Norms with Applications To Online Facility Location and Stochastic Probing
• Adaptive Sequence Submodularity
• Distributed Submodular Minimization And Motion Coordination Over Discrete State Space