Source-linked AI summary
Submodular Functions: from Discrete to Continous Domains
Francis Bach
TL;DR
The paper asks whether the convexity-based theory of submodular set-functions extends to functions on finite and continuous ordered domains. It constructs probability-measure extensions using optimal transport and derives convex formulations and minimization algorithms. The resulting framework covers generic submodular functions, while practical continuous-domain use requires discretization and some related strategies introduce additional parameters.
Problem
Existing convex extensions and minimization results are established mainly for submodular set-functions, motivating their extension to broader finite and continuous domains.
Method
The paper replaces variables with probability measures, optimizes over cumulative distributions, and uses multi-marginal optimal transport to construct convex extensions and algorithms.
Results
The framework shows that the convex envelope can be computed for submodular functions and provides equivalent convex minimization formulations, including a strongly convex alternative.
Takeaways & Limitations
The algorithms apply to submodular functions on products of subsets of R, covering finite and continuous domains and defining a class that can be minimized in polynomial time.
Takeaways & Limitations
Continuous-domain algorithms rely on discretizing the sets, while an alternative bounded strategy can require extra, often unknown parameters.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper extends the relationship between submodularity and convexity from set-functions to functions on products of ordered subsets of R. It introduces probability-measure extensions, convex optimization formulations, polyhedral links, and algorithms for minimization.
- Submodularity is important in combinatorial optimization and has applications in machine learning, computer vision, and signal processing.
- The paper extends set-function results to submodular functions defined on products of subsets of R, including finite and continuous domains.
- A probability-measure extension is convex if and only if the original function is submodular, and minimizing it is equivalent to minimizing the original function.
- The analysis relies on optimal transport and assumes basic knowledge of convex analysis, with relevant submodular-analysis and optimal-transport concepts rederived as needed.
- Adding a separable convex function yields a strongly convex optimization problem equivalent to minimizing a series of submodular functions, potentially facilitating Frank-Wolfe methods.
- The paper extends links with base polytopes and greedy maximization algorithms, while providing nonsmooth and smooth minimization algorithms for finite domains.
2 Submodular functions
Submodular functions on ordered product domains generalize set-functions through a lattice inequality and, on continuous domains, nonpositive cross-effects. They include diverse examples and retain useful closure, minimizer, and algorithmic properties.
- A function is submodular when H(x)+H(y) is at least H(min{x,y})+H(max{x,y}), with min and max applied component-wise.
- For discrete domains, submodularity is equivalently expressed through diminishing returns when two coordinates are increased.
- Modular functions are exactly separable functions, while sums, positive scaling, and restrictions preserve submodularity.
- The minimizers of a submodular function form a sublattice, and strict submodularity makes them a totally ordered chain.
- Submodular examples include pairwise convex differences, concave functions of nonnegative weighted sums, spectral functions, and extensions of submodular set-functions.
- For binary domains, the multi-linear extension remains submodular, enabling globally precise polynomial-time mean-field inference in the stated setting.
- For twice-differentiable functions on intervals, submodularity is characterized by nonpositive cross-second-order derivatives.
- These functions can have multiple local minima, local maxima, and saddle points while remaining efficiently minimizable.
3 Extension to product probability measures
The paper extends submodular-function analysis from discrete domains to product probability measures using cumulative-distribution and convex-closure constructions. For submodular functions, these extensions coincide, are convex exactly under submodularity, and preserve equivalent minimization and duality properties.
- Probability-measure extensions: The extension represents each coordinate value through a probability measure, recovering the original function when all measures are Dirac masses.For finite domains, the measures form simplices; cumulative distributions provide a convenient representation.
- Cumulative extension: The cumulative extension applies one shared threshold to all inverse cumulative distribution functions, producing a value by integrating H over the resulting coupled points.This construction recovers the Choquet or Lovász extension for set-functions.
- Convex closure: The convex-closure extension is convex, admits an optimal-transport formulation with attained infimum and dual representation, and has equivalent minimization value to the original function.These properties hold for continuous H independently of submodularity.
- Equivalence of extensions: For continuous submodular H on compact one-dimensional coordinate domains, the cumulative and convex-closure extensions are equal through one-dimensional multi-marginal optimal transport.The monotone transport plan couples coordinates by thresholding inverse cumulative distributions.
- Convexity and submodularity: The cumulative extension is convex if and only if H is submodular, generalizing the corresponding set-function relationship.The result applies to continuous functions on products of compact subsets of the real line.
- Minimization and duality: Minimizing a submodular H is equivalent to minimizing its convex extension, and minimizers can be recovered by inverse cumulative distributions for almost every threshold.The associated minimizer paths are non-increasing in the threshold parameter, and the framework also yields a dual problem for optimality certificates.
4 Discrete sets
For finite domains, the paper extends measure-based and greedy constructions from set-functions to non-increasing cumulative-distribution vectors. These extensions yield convex optimization, polyhedral representations, and reductions for submodular minimization.
- Measure representation: Finite-domain measures are represented by non-increasing truncated cumulative distributions ρi, which are extended beyond the [0,1] range.Each ρi has ki−1 components, with ρi(0)=1 omitted.
- Extended function: The extended function h↓ is defined through the map θ(ρi,t), which converts threshold intervals of ρi into domain values.For binary domains, θ simply thresholds t at ρi.
- Extended function: If ρi is the cumulative distribution of μi, then h(μ)=h↓(ρ), linking the probability-measure extension to the finite-domain construction.The same representation also supports extension beyond probability vectors.
- Greedy algorithm: For submodular H, h↓ is convex, and its greedy evaluation orders all ρi(xi) values before accumulating successive coordinate increments.The greedy output expresses h↓ as H(0) plus weighted increments of H.
- Base polyhedron: The generalized base-polyhedral theory produces two objects, W(H) and B(H), which coincide for set-functions but differ when coordinate monotonicity matters.B(H) is a bounded polytope, whereas W(H) is generally unbounded and retains the non-increasing-vector constraint in its support function.
- Minimization: Thresholding solutions of the convex formulation yields minimizers of H, while ring-family formulations reduce finite-domain minimization to submodular set-function minimization.The thresholding result directly extends the set-function case.
5 Optimization for discrete sets
The paper develops two optimization approaches for finite-domain submodular functions: projected subgradient descent for a non-smooth formulation and Frank-Wolfe methods for a smooth strongly convex formulation. Both use greedy subgradients and provide primal-dual certificates, while the smooth approach performs better empirically.
- Setup: The algorithms assume function-value access and bounded coordinate differences, and their complexity remains polynomial with weak dependence on the finite-domain sizes.They can also be applied to continuous domains after discretizing each coordinate set.
- Non-smooth optimization: Projected subgradient descent computes subgradients by the greedy algorithm and projects independently through n isotonic regressions.The greedy step is identified as the bottleneck.
- Certificates: The method supports primal-dual certification by combining primal candidates from thresholded solutions with dual candidates formed from greedy outputs.A dual candidate in B(H) can provide an optimality certificate.
- Continuous domains: For Lipschitz-continuous functions on [0,B]^n, discretization adds an error of at most GB/k to the optimization bound.The grid uses k values per coordinate.
- Smooth optimization: Frank-Wolfe methods optimize a smooth dual problem over a compact set, using line search or fixed step sizes and obtaining primal candidates at comparable convergence rates.Warm restarts can help when solving a sequence of related discretized problems.
- Comparison: The smooth approach has no complexity-bound improvement over subgradient descent, but its empirical performance is significantly better.The comparison is stated after combining the Frank-Wolfe convergence rate with the resulting minimization bound.
6 Experiments
The experiment applies the algorithms to one-dimensional signal denoising with smooth and sparse priors, including a nonconvex submodular objective. Frank-Wolfe methods achieve smaller certified duality gaps than projected subgradient descent on the reported discretization.
- Denoising problem: The denoising objective combines a smooth quadratic prior with a sparse prior that is submodular but not convex.For α<1, the resulting optimization problem is nonconvex.
- Denoising problem: The algorithms solve this nonconvex denoising problem globally to arbitrary precision for any α>0.The paper presents this as an application of the discrete optimization algorithms.
- Algorithm comparison: On a discretization with 50 grid elements for each of n=50 variables, Frank-Wolfe methods produce better certified duality-gap performance than projected subgradient descent.The pairwise-Frank-Wolfe method performs particularly well.
- Dual solutions: The estimated dual vectors are nearly threshold functions for the non-smooth formulation but contain more information for the smooth formulation.The smooth case reflects its series of submodular minimization problems.
7 Discussion
The discussion frames measure-based convex relaxations as a general solution framework for submodular optimization, while identifying extensions toward adaptive discretization and broader algorithmic settings.
- Replacing variables with probability measures and optimizing cumulative distributions yields convex relaxations and algorithms for submodular functions on finite or continuous product domains.
- The convex envelope can be computed for submodular functions, unlike in the general case, making the resulting relaxation a practical alternative.
- Submodular relaxations: Submodular relaxations can represent functions as differences of submodular functions, but the resulting optimization problem is generally non-convex.
- Further extensions: The paper also identifies extensions involving submodular maximization, sums of simple submodular functions, and active-set methods.
- Divide-and-conquer algorithm: For discrete domains, a divide-and-conquer procedure extends the set-function algorithm and solves the separable optimization problem through at most n submodular optimizations.
- Adaptive discretization schemes: On continuous domains, the current strategy is discretization, motivating adaptive schemes based on duality-gap criteria.
A.1 Submodularity of the Lov´asz extension of a submodular set-function
The Lovász extension inherits submodularity from the original submodular set-function through a level-set argument.
- The proof tests infinitesimal displacements along two basis directions and uses whether the coordinates lie in the same level set.
- When the extension is written through cumulative distributions, its convexity supplies another proof of submodularity.
A.2 Submodularity of the multi-linear extension of a submodular set-function
The multi-linear extension is submodular because its two-variable cross-term is nonpositive, reflecting the original set-function's submodularity.
- The multi-linear extension uses independent Bernoulli variables and is verified by reducing the argument to the quadratic two-variable case.
- In the two-variable case, the cross-term is nonpositive because the original set-function is submodular.
B Divide-and-conquer algorithm for separable optimization
The appendix extends a set-function divide-and-conquer method to discrete general submodular functions by recursively splitting domains and recombining optimal solutions.
- The optimization problem has a dual formulation under strict convexity and differentiability assumptions, and it can be reduced to a sequence of submodular minimization problems.
- The recursive procedure solves restricted problems on complementary domains and concatenates their solutions into the optimal vector.
- Correctness follows because the optimum on a wider domain lies in the admissible set, while the optimal weights share a common threshold parameter.
- The two decoupled solutions satisfy the required ordering, so separately minimizing the restricted problems recovers the global solution.