Majorisation-minimisation algorithms for minimising the difference between lattice submodular functions
arXiv:1905.13492
Abstract
We consider the problem of minimising functions represented as a difference of lattice submodular functions. We propose analogues to the SupSub, SubSup and ModMod routines for lattice submodular functions. We show that our majorisation-minimisation algorithms produce iterates that monotonically decrease, and that we converge to a local minimum. We also extend additive hardness results, and show that a broad range of functions can be expressed as the difference of submodular functions.
arXiv comment13 pages
References in corpus (5)
- Non-monotone submodular maximization under matroid and knapsack constraints
- Learning Mixtures of Submodular Shells with Application to Document Summarization
- Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications
- A submodular-supermodular procedure with applications to discriminative structure learning
- A Reduction for Optimizing Lattice Submodular Functions with Diminishing Returns