PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient Minimization of Decomposable Submodular Functions

Peter Stobbe, Andreas Krause

arXiv:1010.5511v1cs.LGmath.OC

TL;DR

Many machine-learning problems require discrete combinatorial optimization, while general submodular minimization can be impractical at scale. The paper develops SLG for decomposable submodular functions using smoothed convex minimization. On a large joint classification-and-segmentation task, SLG outperforms state-of-the-art general-purpose submodular minimizers by several orders of magnitude.

  • Problem

    Many machine-learning problems require discrete combinatorial optimization, and exact general submodular minimization can demand O(n^5) function evaluations, limiting practicality at scale.

    Source: §1 · p. 1

  • Method

    SLG minimizes decomposable submodular functions, sums of concave functions applied to modular functions, by applying smoothed convex minimization to the Lovász extension.

    Source: §1 · p. 1, §3 · p. 3

  • Results

    On joint classification-and-segmentation with tens of thousands of variables, SLG outperforms state-of-the-art general submodular minimization algorithms by several orders of magnitude.

    Source: §1 · p. 2

  • Takeaways & Limitations

    SLG offers a middle ground between fast, specific graph-cut methods and general combinatorial algorithms that are impractical at large scale.

    Source: §7 · p. 8

    The analyzed SLG setting assumes the objective is a nonnegative linear combination of threshold potentials and a modular function.

    Source: §4.2 · p. 5

Abstract

from arXiv · show

Many combinatorial problems arising in machine learning can be reduced to the problem of minimizing a submodular function. Submodular functions are a natural discrete analog of convex functions, and can be minimized in strongly polynomial time. Unfortunately, state-of-the-art algorithms for general submodular minimization are intractable for larger problems. In this paper, we introduce a novel subclass of submodular minimization problems that we call decomposable. Decomposable submodular functions are those that can be represented as sums of concave functions applied to modular functions. We develop an algorithm, SLG, that can efficiently minimize decomposable submodular functions with tens of thousands of variables. Our algorithm exploits recent results in smoothed convex minimization. We apply SLG to synthetic benchmarks and a joint classification-and-segmentation task, and show that it outperforms the state-of-the-art general purpose submodular minimization algorithms by several orders of magnitude.

1 Introduction

General submodular minimization is polynomial-time solvable, but exact methods can be impractical for large problems. The introduction presents SLG for decomposable functions and reports a large-scale classification-and-segmentation speed advantage.

1 Introduction

  • Exact submodular minimization can require O(n^5) function evaluations, making general-purpose algorithms impractical for many real-world problems.Source: §1 · p. 1
  • SLG targets decomposable submodular functions, sums of concave functions applied to modular functions, using smoothed convex minimization on the Lovász extension.Source: §1 · p. 1
  • On joint classification-and-segmentation with tens of thousands of variables, SLG outperforms state-of-the-art general submodular minimizers by several orders of magnitude.Source: §1 · p. 2

2 Background on Submodular Function Minimization

The background characterizes submodularity through diminishing returns and a set-function inequality, then connects submodular minimization to convex optimization through the Lovász extension. It motivates smoothing methods that use structural knowledge to improve optimization and permit early optimality checks.

2 Background on Submodular Function Minimization

  • A set function is submodular when f(A ∪ B) + f(A ∩ B) ≤ f(A) + f(B), equivalently expressing diminishing returns.Source: §2 · p. 2
  • The Lovász extension gives submodular functions a convex, efficiently evaluable extension, relating set minimization to convex minimization.Source: §2 · p. 2
  • For nondecreasing submodular functions under a cardinality constraint, greedy maximization gives a near-optimal solution.Source: §2 · p. 2
  • Direct subgradient minimization of the nonsmooth Lovász extension needs O(1/ε²) steps for O(ε) accuracy and is regarded as impractical.Source: §2 · p. 3
  • Structural knowledge can support smoothing with O(1/ε) running time; the paper exploits decomposable structure and discrete optimality certificates for early termination.Source: §2 · p. 3

3 The Decomposable Submodular Minimization Problem

The paper defines decomposable submodular functions as sums of concave functions applied to nonnegative modular functions, then focuses first on threshold potentials. It relates this class to pairwise and higher-order potentials and several application settings.

3 The Decomposable Submodular Minimization Problem

  • Decomposable submodular functions are sums of concave functions applied to nonnegative modular functions, with a modular term c · e_A.The paper states that functions of this form are submodular.Source: §3 · p. 3
  • Threshold potentials Ψ_w,y(A) = min(y, w · e_A) provide the initial special case, with each concave term of the form d_j min(y_j, ·).The paper says its approach is later generalized to arbitrary decomposable functions.Source: §3 · p. 3
  • A concave cardinality potential on a region can be expressed using modular and threshold terms; prior graph-cut reformulations cover a narrower class.The paper cites prior work using higher-order potentials for classification performance improvements.Source: §3 · p. 3
  • Nonuniformly weighted threshold potentials are strictly more general than concave cardinality potentials, although weighted combinations of set-cover functions can be expressed as threshold potentials.Source: §3 · p. 4
  • The paper also identifies multiclass queuing functions as decomposable and uses quadratic higher-order region potentials with TextonBoost in its classification-and-segmentation experiments.The region potential is smallest when a region is wholly in or out of A, and largest when half its elements are in A.Source: §3 · p. 4

4 The SLG Algorithm for Threshold Potentials

SLG minimizes sums of threshold potentials by smoothing the Lovász extension and applying accelerated gradient descent. It also uses discrete optimality certificates to stop before the continuous optimization has converged.

4.1 The Smoothed Extension of a Threshold Potential

  • For a threshold potential, SLG smooths its Lovász extension by restricting the dual variable to 0 ≤ v ≤ w with v · 1 = y, and the optimal v is the gradient.The algorithm computes this vector as the gradient of the smoothed extension.Source: §4.1 · p. 4

4.2 The SLG Algorithm for Minimizing Sums of Threshold Potentials

  • For sums of threshold potentials, SLG uses the smoothed objective's Lipschitz gradient in accelerated gradient descent and projects iterates onto the unit cube.The passage gives a Lipschitz bound based on the component potentials.Source: §4.2 · p. 5
  • SLG guarantees an ε-optimal solution to the continuous optimization problem, which can be rounded to an ε-optimal set for the original submodular function.The theorem passage gives a running-time bound beginning with O(D, but the supplied statement is incomplete.Source: §4.2 · pp. 5–6

4.3 Early Stopping based on Discrete Certificates of Optimality

  • When the candidate set's coordinates exceed all outside coordinates by at least 2µ, the smoothed gradient is a subgradient at the set's indicator vector and can provide an optimality gap.If needed, the coordinates can be separated by adding a positive multiple of the candidate set's indicator vector.Source: §4.3 · p. 6
  • SLG selects elements with nonpositive gradient components, shifts the iterate to separate the set's coordinates, and stops when the shift leaves gradient signs unchanged.The paper reports using this stopping criterion in all experiments.Source: §4.3 · p. 6

5 Extension to General Concave Potentials

The paper extends SLG from threshold potentials to arbitrary concave potentials by representing a concave function as an integral of threshold potentials. The algorithm and its optimality conditions remain essentially unchanged, though computing the smoothed gradient involves integrals.

5 Extension to General Concave Potentials

  • An arbitrary concave function can be expressed as an integral of threshold potential functions.The paper presents this as the basis for extending the algorithm beyond threshold potentials.Source: §5 · p. 7
  • For general concave potentials, SLG replaces threshold extensions with their integral-based extensions; its algorithm and optimality conditions remain essentially unchanged.Computing the smoothed gradient is more involved because it requires evaluating integrals.Source: §5 · p. 7
  • The integral can be evaluated by parts using the piecewise-linear dependence on y, requiring values of φ but not its derivatives.Source: §5 · p. 7

6 Experiments

SLG handles higher-order regularization in image segmentation at large problem sizes, while experiments compare it with MinNorm and earlier segmentation approaches. Synthetic results show SLG scales at least as well as MinNorm, though that comparison is inconclusive.

Synthetic Data

  • On synthetic minimum-cut problems, SLG scaled at least as well as MinNorm and handled sizes impractical for the combinatorial algorithms, but the MinNorm comparison was inconclusive.In some cases SLG was 6 times faster than MinNorm; the comparison used a faster machine for SLG but a simple MATLAB implementation.Source: §6 · p. 7

Image Segmentation Experiments

  • 71.4 seconds versus 6900 seconds: SLG and MinNorm produced the same result on a 10^4-variable problem with 90 concave potentials; SLG took roughly 1600 seconds on a 4 × 10^4-variable image.Figure 2 shows the classification outputs for the 10^4-variable problem.Source: §6 · p. 8, Figure 2 · p. 8
  • Higher-order regularization with SLG produced segmentation outputs after per-pixel scores and 2-potentials were tested as earlier approaches.The per-pixel scores captured the general object area but not its shape; 2-potential regularization improved performance but still classified boundaries poorly.Source: §6 · pp. 7–8

7 Conclusion

The conclusion presents threshold-potential decomposition and smoothing as a way to minimize a broad practical class of submodular functions, including functions beyond pairwise potentials. The appendices establish submodularity for decomposable functions and reformulate set cover in that form.

7 Conclusion

  • Threshold-potential sums have Lovász extensions suited to modern smoothing techniques, enabling minimization beyond pairwise potentials and creating a middle ground between graph cuts and general combinatorial algorithms.The authors report solving problems with thousands of variables.Source: §7 · p. 8

A Submodularity of Decomposable Functions

  • For concave φ and nonnegative weights, diminishing discrete derivatives show that f(A) = φ(w · e_A) is submodular.When A ⊆ B, the weight sum for A is no greater than for B, so adding an element has a no-greater discrete derivative at B.Source: A Submodularity of Decomposable… · p. 10

B Reformulation of Set Cover Functions

  • A set-cover function counts the union of selected sets and can be represented using vectors that indicate which sets contain each base-set element.Summing the resulting terms counts each element in the union once.Source: B Reformulation of Set Cover Functions · p. 10

C Strict Generality of Threshold Potentials

Concave cardinality functions can be represented as modular terms plus nonnegative combinations of threshold potentials, but this representation is not universal for submodular functions.

C Strict Generality of Threshold Potentials

  • Concave cardinality functions decompose into a modular function plus a nonnegative linear combination of threshold potentials.The coefficients are nonnegative because φ is concave.Source: C Strict Generality of Threshold… · p. 10
  • For n = 4, the representation test has 24 linear constraints, 4 unconstrained variables, and 19 nonnegative variables.The passage says feasibility can be checked with a linear algebra package.Source: C Strict Generality of Threshold… · p. 10
  • The threshold potential min(y, w · e_A), with w = [1, 2, 3, 4]/4 and y = 1, has no feasible representation under the stated constraints.Source: C Strict Generality of Threshold… · p. 10

D Reformulation of a Class of Functions

The appendix shows how a class of functions from prior work can be expressed in decomposable form through a constructed concave function and weight vectors.

D Reformulation of a Class of Functions

E Proof of Lemma 1

Under Lemma 1’s hypothesis, shifting x by a positive multiple of e_A leaves the smoothed gradient unchanged; the proof then uses scaling to obtain a subgradient limit.

E Proof of Lemma 1

  • Adding αe_A for α > 0 leaves the gradient unchanged under the lemma hypothesis.The proof checks this using the gradient formula.Source: E Proof of Lemma 1 · p. 11
  • In the gradient formula, t* either increases by α or remains unchanged, so the gradient itself is unchanged.Source: E Proof of Lemma 1 · p. 11
  • Combining this invariance with the scale relationship yields a right-hand side converging to a subgradient as α → ∞.Source: E Proof of Lemma 1 · p. 11

F Proof of Lemma 2

The proof of Lemma 2 motivates its identity through integration by parts; the general smoothed-gradient formula uses a piecewise-linear threshold-potential gradient and can be evaluated in O(n^2) operations.

F Proof of Lemma 2

  • The proof motivates its identity through integration by parts and the second derivative of min(x, y), which is −δ(x−y).Source: F Proof of Lemma 2 · p. 12

G General Smoothed Gradient Formula

  • For f(A) = φ(w · e_A), the smoothed-gradient formula uses the threshold-potential gradient g(y), which is piecewise linear.Its intervals are [y_i, y_i+1], with endpoint values θ_i = g(y_i).Source: G General Smoothed Gradient Formula · p. 12
  • At most 2n breakpoints can be found in O(n log n) time, and evaluating the formula takes O(n^2) operations.The evaluation adds O(n) vectors of dimension n.Source: G General Smoothed Gradient Formula · p. 12
Loading 1010.5511v1…