Supermodular Rank: Set Function Decomposition and Optimization

The gist: We define the supermodular rank of a function on a lattice as the smallest number of terms needed to decompose it into a sum of supermodular functions, and we use this notion to develop algorithms for constrained set function optimization and ratio minimization with improved approximation guarantees.

Supermodular Rank Definition and Characterization

The paper introduces the concept of supermodular rank, defined as the smallest number of terms needed to decompose it into a sum of supermodular functions (Page 1). This is characterized by defining the supermodular rank as the smallest number of terms in a decomposition into a sum of functions that are π-supermodular, where π is a partial order on the domain (Page 2). The functions with at most rank r are characterized as a union of Minkowski sums of at most r supermodular cones (Page 2). The supermodular cone is defined by linear inequalities called imset inequalities in the study of conditional independence structures and graphical models (Page 2).

Key Structural Results on Cones

The paper establishes fundamental properties for these cones, including their Minkowski sums. Theorem 8 states that the Minkowski sum of supermodular cones Lπ(1) + · · · + Lπ(m) is a convex polyhedral cone whose facet inequalities are the facet defining inequalities common to all m cones Lπ(i) (Page 4). Furthermore, the maximum supermodular rank of a function on two variables is shown to be ⌈log2 n⌉ + 1 for n ≥ 3, and submodular functions in the interior of −L(1,……1) have rank ⌈log2 n⌉ (Page 4). The maximum elementary supermodular rank is shown to be "n," and a supermodular function in the interior of L(1,……1) has this rank (Page 4).

Optimization Algorithms via Rank Decomposition

The core contribution involves using the rank decomposition to improve optimization guarantees. The paper proposes the R-SPLIT and R-SPLIT RATIO algorithms for monotone set function and ratio of set functions optimization (Page 2). The key insight is that a function with elementary submodular rank r can be split into 2 r submodular pieces (Page 2). Theorem 25 provides guarantees for the R-SPLIT algorithm, showing that it returns a solution with approximation ratio max[R(α, γ), R(αr, 1)] (Page 6).

Guarantees for Constrained Maximization

For constrained set function maximization, the paper presents results based on the elementary submodular rank. Corollary 64 states that if a function has elementary submodular rank r + 1, then the approximation ratio for the R SPLIT GREEDY is max(R(α, γ), (1 − αeˆ−1) − O(ϵ)) (Page 26). This demonstrates how the decomposition allows trading off computational cost and accuracy with theoretical guarantees.

Guarantees for Ratio Minimization

For minimizing ratios of set functions, the R-SPLIT GREEDY subroutine is applied in Algorithm 4. Theorem 31 shows that when both numerator f and denominator g have elementary submodular ranks rf + 1 and rg + 1, the algorithm achieves an approximation ratio of 1 / (1 − e αˆf −1) (Page 27). This improves on previous guarantees for non-submodular functions by leveraging the rank decomposition.

Experimental Validation

Experiments are conducted across four function types: DETERMINANTAL, BAYESIAN, COLUMN, and RANDOM (Page 28). The results illustrate that the approximation ratio guarantee can increase quickly with higher values of r (Figure 1a) for DETERMINANTAL functions (Page 29). Furthermore, the R-SPLIT GREEDY algorithm outperforms GREEDY in finding optimal solutions on several datasets for small n, such as n = 20 (Figure 2a) (Page 30). The volume of the supermodular cone is shown to decrease at least with quadratic rate as n increases (Page 31).

Conclusion

The paper concludes by showing that the rank decomposition provides a grading of set functions that is useful for obtaining optimization guarantees (Page 2). While determining the cones in the decomposition remains an open problem, the work suggests that this approach significantly improves approximation ratios for constrained set function maximization and ratio minimization (Page 10). The theoretical complexity and practical approaches for computing rank decompositions remain open problems with interesting consequences (Page 10). The paper also discusses connections between supermodularity inequalities and probabilistic graphical models like Restricted Boltzmann machines (Page 32).

--- Page 1 ---

Supermodular Rank: Set Function Decomposition and Optimization

Rishi Sonthalia, UCLA, Anna Seigal, Harvard University, Guido Montufar, UCLA and MPI MiS. Abstract. 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. Keywords: supermodular cone, imset inequality, set function optimization, greedy algorithm, approximation ratio

--- Page 2 ---

1 Introduction We study the optimization of set functions – functions that are defined over families of subsets. The optimization of set functions is encountered in image segmentation (Boykov and Kolmogorov [7]), clustering (Narasimhan, Jojic, and Bilmes [39]), feature selection (Song et al. [47]), and data subset selection (Wei, Iyer, and Bilmes [54]). Brute force optimization is often not viable since the individual function evaluations may be expensive and the search space has exponential size. Therefore, one commonly relies on optimization heuristics that work for functions with particular structure. A classic function structure is supermodularity, which for a function on a lattice1 requires that f(x) + f(y) ≤ f(x ∧ y) + f(x ∨ y). Supermodularity can be regarded as a discrete analogue of convexity. A function is submodular if its negative is supermodular. Submodularity is interpreted as a “diminishing returns” property. Sub- and supermodularity can be used to obtain guarantees for greedy optimization of functions on a lattice, in a similar way as convexity and concavity are used in iterative local optimization of functions on a vector space. Well-known examples are the results of Nemhauser, Wolsey, and Fisher [40] for greedy maximization of a monotone submodular set function subject to cardinality constraints and those of Calinescu et al. [10] for arbitrary matroid ˘ constraints. Refinements have been obtained using gradations such as total curvature (Conforti and Cornuejols [12], Filmus and Ward [18], and Sviridenko, Vondrak, and Ward [52]). As many set functions of interest are not sub- or supermodular, relaxations have been considered, such as the submodularity ratio (Das and Kempe [14]), generalized curvature (Bian et al. [5], Buchbinder et al. [9], Conforti and Cornuejols [12], and Gatmiry and Gomez-Rodriguez ´ [20]), weak submodularity (Chen, Feldman, and Karbasi [11] and Halabi and Jegelka [23]), ϵsubmodularity (Krause, Singh, and Guestrin [27]), submodularity over subsets (Du et al. [15], or 1 I.e. a poset where any two elements x, y have a greatest lower bound x ∧ y and a least upper bound x ∨ y.) Preprints. Under review. arXiv:2305.14632v1 [math.CO] May 24

--- Page 3 ---

bounds by submodular functions (Horel and Singer [25]). We will discuss some of these works in more detail in Section 4. We propose a new approach to grade the space of functions on a lattice. We define the supermodular rank of a function to be the smallest number of terms in a decomposition into a sum of functions that are π-supermodular, where π is a partial order on the domain. The partial order π differs between summands. We define the submodular rank analogously. We consider multivariate functions with partial orders that are products of arbitrary linear orders. We focus on set functions that are realvalued on 2 [n] ∼= (0, 1) n, with partial order defined by an order on the values of each input coordinate. We refine submodular rank to elementary partial orders, restricted to vary from a reference order by a transpositions in one input coordinate. We optimize set functions via submodular decompositions. The key insight for our optimization algorithms is that a function with elementary submodular rank r can be split into 2 r submodular pieces (Page 2).

--- Page 4 ---

The supermodular functions are defined by linear inequalities, hence they comprise a polyhedral cone, which is called the supermodular cone.

1. Improved constrained optimization for set functions by using R-SPLIT algorithms to split an optimization problem into submodular subproblems based on elementary supermodular rank. This allows for obtaining approximation ratio guarantees that improve on previous guarantees for greedy algorithms based on approximate submodularity.

2. Enhanced analysis of monotone set function maximization by providing a new approach to grade the space of functions using supermodular rank, which is useful for obtaining improved optimization guarantees.

3. Developed an algorithm called R-SPLIT RATIO to minimize ratios of set functions, improving approximation guarantees for the ratio problem compared to prior work by showing that this improves the approximation ratio guarantee of Wang et al. [53] to that of Bai et al. [4].

4. Created low elementary submodular rank approximations using PROJECT AND FORGET, which can be used in conjunction with R-SPLIT GREEDY to improve the quality of solutions obtained upon optimization by leveraging submodular functions with bounded elementary submodular rank.

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.