Efficient Minimization of Decomposable Submodular Functions

Abstract

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.

Expanded version of paper for Neural Information Processing Systems 2010

References in corpus (1)

• Structured sparsity-inducing norms through submodular functions

Cited by in corpus (28)

• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Fast Semidifferential-based Submodular Function Optimization
• Provable Submodular Minimization using Wolfe's Algorithm
• Fast Exact Inference for Recursive Cardinality Models
• Deep Submodular Functions
• Discrete Signal Processing with Set Functions
• Structured Convex Optimization under Submodular Constraints
• On the Convergence Rate of Decomposable Submodular Function Minimization
• Random Coordinate Descent Methods for Minimizing Decomposable Submodular Functions
• Scalable Variational Inference in Log-supermodular Models
• Maximizing Submodular or Monotone Functions under Partition Matroid Constraints by Multi-objective Evolutionary Algorithms
• Revisiting Decomposable Submodular Function Minimization with Incidence Relations
• Computing exact minimum cuts without knowing the graph
• Convex Optimization for Parallel Energy Minimization
• Structured Optimal Transport
• Minimizing a sum of submodular functions
• Distributed Submodular Minimization And Motion Coordination Over Discrete State Space
• Fast Decomposable Submodular Function Minimization using Constrained Total Variation
• Active-set Methods for Submodular Minimization Problems
• Graph Cuts with Interacting Edge Costs - Examples, Approximations, and Algorithms
• Quadratic Decomposable Submodular Function Minimization: Theory and Practice (Computation and Analysis of PageRank over Hypergraphs)
• Subquadratic Submodular Function Minimization
• Augmented Sparsifiers for Generalized Hypergraph Cuts with Applications to Decomposable Submodular Function Minimization
• An Efficient Decomposition Framework for Discriminative Segmentation with Supermodular Losses
• Subadditive Load Balancing
• Distributed control and game design: From strategic agents to programmable machines
• Approximate Decomposable Submodular Function Minimization for Cardinality-Based Components
• Pareto Optimization for Subset Selection with Dynamic Partition Matroid Constraints