Supermodular Rank: Set Function Decomposition and Optimization

A main weakness is that the paper is not well-written. The structure is quite confusing. The formal definitions of the considered models are not provided until section 4. Several new definitions are introduced before Section 4. However, the absence of any intuitive explanations renders the paper less accessible to readers.

We thank the reviewers for their comments. We have updated the manuscript to add more explanatory examples to improve the paper’s readability. The changes are highlighted in blue.

(1) Could you give some intuition about the elementary-submodular-rank-based trick used in the paper?

The intuition might be more apparent if we think of continuous functions. The idea behind the elementary rank can be thought of (not strictly true, but ok for intuition reasons) as determining the number of coordinate directions in which the function is non-convex. Once we have determined these directions, we decompose our function into convex orthogonal functions. Then, we independently optimize these functions.

The presentation of this work is poor. It seems that the authors ran out of space and moved a lot of background knowledge to the appendix. Without this knowledge, it's hard to get the definition of \pi-supermodular. After moving, it seems that the authors didn't do careful proofreading. For example, R(alpha, gamma) in Theorem 25 is not defined. This significantly impairs readability. I appreciate that the authors also try to explain their ideas with some examples, and I also understand that the space issue is not the authors' fault, but it is a fact that the paper does need a better presentation.

We thank the reviewers for their comments. We have updated the manuscript to add more explanatory examples to improve the paper’s readability. The changes are highlighted in blue.

To my understanding of Table 2, the proposed algorithm improves the previous ratio only in the case where the elementary submodular rank is a constant. If this is true, it’s not clear how important this improvement is. Because the paper didn't include a discussion about whether there exists some famous functions with a constant submodular rank. Besides this, the paper only includes an upper bound on the rank of a function but excludes the way to compute the rank of a function. Maybe I missed something, and such a computation is trivial, but this should be stated explicitly.

Computing the rank of a function (unless we know something about the function) is not easy. We do not have a simple method for doing so. However, we can provide examples of functions that have low submodular rank.

RBM

The first example comes from Restricted Boltzmann Machines (RBMs). These are graphical models for modeling probability distributions on $\{0,1\}^n$. They have a hyperparameter $m$, the number of hidden nodes. Prior work (See references [Allman et al., 2015]) has shown that when $m=1$, this model can represent distributions $f(x)$ if and only if $\log f$ is $\pi$-supermodular and satisfies certain polynomial equality constraints. Then, when we move to more significant values of $m$, it can be shown that the model can model distribution $f(x)$ only if $\log f$ is rank-$m$ supermodular. Thus log RBM distributions are functions with bounded supermodular rank. In this case, the optimization problem would correspond to finding modes of the distribution.

One hidden layer neural networks

Building on this, we have the following.

Proposition: Let $f$ be a real-valued function on $\{0,1\}^n$ that is the composition of an affine function and a convex function. That is, $f(x) = \phi(wx + c)$ where $w$ is a vector of length $1 × n$ and $c$ is a scalar and $\phi : \mathbb{R} \to \mathbb{R}$ is convex. Then $f$ is sign(w)-supermodular.

Proof:We show that the elementary imset inequalities are satisfied. Such an inequality involves four vectors on a two-dimensional face of the cube $\{0, 1\}^n$. We have two indices $x_i,x_j$ that vary and a fixed value of $x_{[n]\setminus\{i,j\}}$, the vector $x$ restricted to the set $[n]\setminus\{i,j\}$. Let $y$ be the entry of the face where $x_i = x_j = 0$. Letting $c' = c + Ay$, we seek to compare $\phi(c' + w_i) + \phi(c' + w_j)$ with $\phi(c') + \phi(c' + w_i + w_j)$. By the definition of ${\rm sign}(w)$-supermodularity, if both entries $w_i$ and $w_j$ have the same sign, we require $\phi(c' + w_i) + \phi(c' + w_j) \leq \phi(c') + \phi(c' + w_i + w_j)$ while if $w_i w_j \leq 0$, we require $\phi(c' + w_i) + \phi(c' + w_j) \geq \phi(c') + \phi(c' + w_i + w_j) .$ The inequalities hold by the fact that $\phi$ is convex. For example, if $w_i,w_j\geq0$, then $c\leq c+w_i, c+w_j\leq c+w_i+w_j$, and we apply the definition of convexity as applied to a comparison of four points.

Thus, in particular, a one-hidden layer ReLU neural network, when restricted to $\\{0,1\\}^n$ with $k$ hidden nodes with positive outer weights, is rank-$k$ supermodular.

The theoretical contribution of this work seems to be very weak. In particular, the elementary rank r basically says that the function becomes submodular for all assignments to a subset of the variables, which leads to an exhaustive search for this subset.

As the reviewer pointed out, the notion of supermodular rank is novel and interesting. Please see the general response for an explanation of our contributions.

The elementary supermodular rank is a particular case where we restricted the types of permutations that were allowed. Here, apriori, there is no reason that this notion would simplify to such an elementary property, but the fact that it does is quite interesting.

Building on this, since the idea of supermodular rank is novel, this gradation of the space of set functions is new. It provides a valuable way to think about the complexity of set function optimization.

Regarding the complexity of our algorithms, recall that there is no free lunch in optimization. Our paper provides a lower bound that says that set function optimization for a rank $r$ function necessarily requires $2^r$ function evaluations. Our algorithms can maintain a low complexity for optimizing functions with low elementary supermodular rank. By necessity, the complexity of optimizing general objective functions, or functions that have a high elementary supermodular rank, is high. To illustrate this more concretely, we can provide examples that serve as a lower bound as follows.

Let $\hat{f}$ be your favorite submodular function on a set of size $n-r$, and define $f$ to be an elementary rank-$r$ submodular function with pieces given by $\hat{f}+c_k$. All of the pieces of $f$ are just shifts of $\hat{f}$. To get an $O(1)$ approximation algorithm for general $c_k$'s, at the very minimum, we need to evaluate the function $f$ once at each of the $2^r$ shifts. Thus, we will always need at least $\Omega(2^r)$ time. As mentioned in Remark 27, if the decomposition is known, which is the case for the lower bound, the only exponential term in the time complexity for R-split is $2^r$. Thus, the algorithm achieves the complexity lower bound.

We would also like to highlight that our algorithm is different from other methods. In particular, typically, algorithms for submodular optimization, such as the plain greedy, are analyzed for things like weak submodularity, but no changes are made to the algorithm to deal with the lack of submodularity. We exploit the non-submodularity structure by providing gradation on the space of functions.

In light of the above strengths, the fact our algorithm is additionally simple is an additional strength.

Hence, demonstrated by the complexity of the algorithmic part, the contribution of this work does not meet the bar of top-tier conferences such as ICLR.

The primary contribution of the paper is not algorithmic but theoretical. The main contributions are

1. The definition of rank
2. The proof of the maximal rank
3. The gradation of the space set functions
4. The results show that theoretical guarantees obtained for submodular functions can be lifted to higher ranks but with a necessary penalty. That is, this penalty cannot be avoided in some cases.

The current paper is very tough to read.

We thank the reviewers for their comments. We have updated the manuscript to add more explanatory examples to improve the paper’s readability. The changes are highlighted in blue.

The empirical evaluation is not convincing.

We kindly disagree. The experimental results show a consistent and significant improvement in the performance compared to Greedy. For example,

1. Figure 1a shows that the theoretical bound improves by 400% in one instance.
2. Figure 1b shows orders of magnitude decrease in the error
3. Figure 2a shows a consistent improvement as well.
4. Figure 2b shows that in most cases, going from greedy to 1-split greedy, the percentage of times we find the optimal set more than doubles.
5. Figure 2c shows that it scales to large problems, and we consistently have over 5% improvement.

Seems like when the submodular rank $r$ is high, the algorithms are impractical.

Yes, but we provide an impossibility result in approximating the solution to a related problem with less work.

We thank the reviewer for their feedback.

​> Complex and Notation-Heavy The paper is noted as being quite complex and filled with notation, making it challenging to follow. Simplifying the presentation or providing additional explanations could enhance the accessibility of the material.

We thank the reviewers for their comments. We have updated the manuscript to add more explanatory examples to improve the paper’s readability. The changes are highlighted in blue.

Lack of Clarity on Performance Improvement: The paper's comparison to existing solutions, particularly in Table 2, is mentioned as lacking clarity. It is not immediately clear how the proposed algorithm outperforms existing solutions. The authors should elaborate on the additional benefit brought by the proposed algorithm's computational overhead.

The table should be read not as saying that we improve the performance of the method (which we do show happens empirically), but in a different manner. Specifically, prior work showed that for a family of functions $\mathcal{F}$, we can prove that we have a good approximation rate. With our framework, we can show that this approximation rate can be lifted to a larger family of functions $\mathcal{G}$ such that $\mathcal{F} \subset \mathcal{G}$. Table 1 shows that the size of $\mathcal{G}$ can be significantly bigger than $\mathcal{F}$.