Supermodular Rank: Set Function Decomposition and Optimization
We define the supermodular rank of a function on a lattice. This is the smallest number of terms needed to decompose it into a sum of supermodular functions. The supermodular summands are defined with respect to different partial orders. We characterize the maximum possible value of the supermodular rank and describe the functions with fixed supermodular rank. We analogously define the submodular rank. We use submodular decompositions to optimize set functions. Given a bound on the submodular rank of a set function, we formulate an algorithm that splits an optimization problem into submodular subproblems. We show that this method improves the approximation ratio guarantees of several algorithms for monotone set function maximization and ratio of set functions minimization, at a computation overhead that depends on the submodular rank.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Supermodularity and valid inequalities for quadratic optimization with indicators
We study the minimization of a rank-one quadratic with indicators and show that the underlying set function obtained by projecting out the continuous variables is supermodular. Although supermodular minimization is, in g…
validCorporate Needs You to Find the Difference: Revisiting Submodular and Supermodular Ratio Optimization Problems
We study the problem of minimizing or maximizing the average value $ f(S)/|S| $ of a submodular or supermodular set function $ f: 2^V \to \mathbb{R} $ over non-empty subsets $ S \subseteq V $. This generalizes classical …
An Efficient Decomposition Framework for Discriminative Segmentation with Supermodular Losses
Several supermodular losses have been shown to improve the perceptual quality of image segmentation in a discriminative framework such as a structured output support vector machine (SVM). These loss functions do not nece…
Computational EfficiencyImage SegmentationSegmentationSemantic SegmentationA Convex Surrogate Operator for General Non-Modular Loss Functions
Empirical risk minimization frequently employs convex surrogates to underlying discrete loss functions in order to achieve computational tractability during optimization. However, classical convex surrogates can only tig…
A Note on Optimizing the Ratio of Monotone Supermodular Functions
We show that for the problem of minimizing (or maximizing) the ratio of two supermodular functions, no bounded approximation ratio can be achieved via polynomial number of queries, if the two supermodular functions are b…