Improved Approximation Algorithms for $k$-Submodular Maximization via Multilinear Extension

We thank the reviewer for their thoughtful feedback. We are encouraged by the recognization of the importance of the $k$-submodular maximization problem, the clarity of our proofs, and the unified algorithm achieving better approximation ratios. Below, we address the questions raised.

...the k-submodular functions can be reduced to general submodular functions under partition matroid. Given this reduction, the idea of defining the multi-linear extension for $k$-submodular functions is less novel

We believe it is non-trivial to reduce non-negative $k$-submodular functions to general non-negative submodular functions under a partition matroid. The statement in [Iwata et al., 2016]—"The $k$-submodular function maximization problem is closely related to the submodular function maximization with a partition matroid constraint"—does not imply such a reduction exists.

One possible attempt of reduction is as follows. We define the domain as $\\bar{\Delta}\_k\^n\subseteq \\{0,1\\}\^{nk}$ where $\bar{\Delta}\_k = \\{x \in \{0,1\}\^{k} : \sum\_{j=1}\^k x_j \leq 1\\}$, and define a function $\bar{f}: \bar{\Delta}\_k\^n\to \mathbb{R}$ as $\bar{f}(S) = f(\mathbf{s})$, where $\mathbf{s}$ is defined as $\mathbf{s}\_i = j$ if there exists a unique element $e\_{i,j} \in S$ and $\mathbf{s}_i = 0$ otherwise. However, we may not be able to extend the domain of such a submodular function to $\\{0,1\\}^{nk}$ without violating non-negativity or monotonicity, even for the simplest case of $k = 2$. Specifically:

1. As shown in Lemma 2 of [Singh et al., 2012], there exists a non-negative 2-submodular function, for which no extension is both non-negative and submodular.
2. Furthermore, Lemma 3 of [Singh et al., 2012] demonstrates that there exists a monotone, non-negative 2-submodular function, for which no extension is non-negative, monotone, and submodular.

These results highlight that $k$-submodular functions cannot generally be reduced to submodular functions under partition matroids, and the development of a multilinear extension tailored specifically for $k$-submodular functions remains new.

We have added this explaination in the revised version; see Appendix A.3 in our updated manuscript.

[Iwata et al., 2016] Improved Approximation Algorithms for k-Submodular Function Maximization, Satoru Iwata, Shin-ichi Tanigawa, Yuichi Yoshida.

[Singh et al., 2012] On Bisubmodular Maximization. Ajit P. Singh, Andrew Guillory, Jeff Bilmes.

...give some intuition of why the algorithm can't achieve a better bound (e.g. $1−1/e$) by explaining some key aspects of the proof in Lemma 3.3?

The main reason why the approximation ratio is not as good as $1−1/e$ for $k$-submodular maximization is due to the change of domain from cube $[0,1]^{nk}$ to a corner $\Delta_k^n$. To illustarte this, we first recap why FW can find $1-1/e$ approximate solution for submodular optimization. To prove the approximate ratio, we link the current solution $x^k$ and optimal solution $x^\star$ by auxillary point $x^\star \vee x^k$ by coordinate-wise maximum operation, then showing one step improvement as $F(x^{k+1}) - F(x^\star)\gtrsim (1-\delta)(F(x^k)- F(x^\star))$ with step-size $\delta$ and solution $x^k$ at $k$-step of FW method. By accumulation, we have $F(x^{K}) \gtrsim (1-1/e) F(x^\star)$. However, the function value of the auxillary point $x^\star \vee x^k$ by coordinate-wise maximum operation may not have definition for $k$-submodular. Instead, in the proof of Lemma 3.3, we use new auxilary point $o(t) = x(t) + (1 − t)o^\star$ that lies in domain $\Delta_k^n$, and show one step improvement $F(x(t + \delta)) − F(x(t)) \gtrsim F(o(t)) − F(o(t + \delta))$, which results in $F(x^{K}) \gtrsim 1/2 F(x^\star)$.

Would using a different concentration inequality, such as Hoeffding's inequality instead of the Chernoff bound, potentially improve the query complexity?

We agree that using alternative concentration inequalities, such as Hoeffding's inequality (instead of the Chernoff bound), might improve the query complexity during the first phase of maximizing the continuous function. However, the overall query complexity of the algorithm could be dominated by the rounding procedure, which remains polynomial even if we have an improved concentration. For instance, finding a continuous solution under a knapsack constraint requires $O(\frac{kn^6\log\frac{n\varepsilon}{\eta}}{\varepsilon^3})$ queries, while the rounding process to obtain a discrete solution necessitates an additional $O(k^{poly(1/\varepsilon)} n^{poly(1/\varepsilon)})$ queries. Additionally, our primary focus in this work is on achieving the best approximation ratio rather than minimizing query complexity. We believe that exploring such refinements to improve query complexity in the first phase will be an interesting direction if the first phase query becomes dominant in some future settings.

Thank you for reviewing our manuscript. We are encouraged by your recognition of the importance, novelty, and clarity of our work.

Is the definition of $k$-submodular presented in the paper the typical definition? And if it is not, is it clearly equivalent?

We appreciate the question regarding the definition of $k$-submodularity. Yes, both the definition in our paper (see Eq. (1)) and the one from [Sakaue (2017)] (as noted in the footnote on Page 1) are typical definitions for $k$-submodular and they are equivalent. To clarify, let us outline the equivalence with the definition on Page 2 of [Sakaue (2017)]:

Definition 1 (from [Sakaue (2017)])

• The domain is represented as $(k+1)^V := \{(X_1, \ldots, X_k) \mid X_i \subseteq V, X_i \cap X_j = \emptyset \text{ for } i \neq j\}$, where $V$ is a ground set.
• A function $f: (k+1)^V \to \mathbb{R}$ is called $k$-submodular if for any $x = (X_1, \ldots, X_k)$ and $y = (Y_1, \ldots, Y_k)$, it satisfies: $f(x) + f(y) \geq f(x \cap y) + f(x \cup y),$ where:
  • $(x \cap y)_i = X_i \cap Y_i$,
  • $(x \cup y)\_i = X_i \cup Y_i \setminus \bigcup_{j \neq i} (X_j \cup Y_j)$.

Definition 2 (from our paper)

• The domain is represented as $\{0, 1, \ldots, k\}^n$, where $0$ represents the null element and each element of the vector specifies a label for one of $k$ disjoint sets.
• A function $f: \{0, 1, \ldots, k\}^n \to \mathbb{R}_{\geq 0}$ is called $k$-submodular if for any $s, t \in \{0, 1, \ldots, k\}^n$, it satisfies: $f(s) + f(t) \geq f(\min_0(s, t)) + f(\max_0(s, t)),$ where:
  • $(\min_0(s, t))_i = \begin{cases} 0 & \text{if } s_i t_i \neq 0 \text{ and } s_i \neq t_i, \\\\ \min(s_i, t_i) & \text{otherwise}, \end{cases}$
  • $(\max_0(s, t))_i = \begin{cases} 0 & \text{if } s_i t_i \neq 0 \text{ and } s_i \neq t_i, \\\\ \max(s_i, t_i) & \text{otherwise}. \end{cases}$

Mapping Between Domains:

• In Definition 1, the domain is $(k+1)^V$, which represents $k$ disjoint subsets $X_1, \ldots, X_k$ of a ground set $V$.
• In Definition 2, the domain is $\{0, 1, \ldots, k\}^n$, where each element $i \in [n]$ belongs to one of $k$ disjoint sets, represented by its label $1, \ldots, k$, or is null ($0$).

The two domains are equivalent since labeling each element in $V$ corresponds directly to assigning it to a subset $X_i$ (or $0$ if it belongs to none).

Operations ($\cup, \cap$ vs. $\min_0, \max_0$):

• Intersection ($\cap$ in Definition 1 and $\min_0$ in Definition 2):

  • For Definition 1, $(x \cap y)_i = X_i \cap Y_i$.
  • For Definition 2, $(\min_0(s, t))_i = \min(s_i, t_i)$ when $s_i, t_i \in \{0, i\}$, which aligns with the intersection of sets for corresponding labels. If $s_i$ and $t_i$ are different and nonzero, the result is $0$, corresponding to the empty intersection.

• Union ($\cup$ in Definition 1 and $\max_0$ in Definition 2):

  • For Definition 1, $(x \cup y)\_i = X_i \cup Y_i \setminus \cup_{j \neq i}(X_j \cup Y_j)$, which ensures disjointness.
  • For Definition 2, $(\max_0(s, t))_i = \max(s_i, t_i)$ when $s_i, t_i \in \{0, i\}$, which aligns with the union of sets. If $s_i$ and $t_i$ are different and nonzero, the result is $0$, ensuring disjointness.

Submodular Inequality:

• Both definitions use the inequality: $f(x) + f(y) \geq f(x \cup y) + f(x \cap y),$ which holds in both formulations because the operations $\cup, \cap$ in Definition 1 are equivalent to $\max_0, \min_0$ in Definition 2, and the domains and function mappings are equivalent.

We have revised our manuscript (see revised manuscript), where we highlight the existence of this equivalent definition of $k$-submodular in the introduction section. We also add this definition and explain its equivalence to our definition (Eq. (1)) in the updated Appendix A.2.

Thank you for your positive and encouraging feedback. We appreciate the recognition of our work’s contribution and will address the questions raised in your comments.

It’s unclear how relevant this problem is for the ML community

While submodular maximization may be more famous in the ML community, many applications of it could be extended to $k$-submodular maximization. One example is diversity, where the selection needs to balance multiple sources.

• Feature selection: In machine learning, feature selection is the process of identifying a subset of features that are most relevant to a given task. $k$-submodular maximization can be used to find a diverse set of features that maximizes the performance of a model.
• Active learning: Active learning is a technique for selecting the most informative data points to label, which can help to reduce the cost of labeling data. $k$-submodular maximization can be used to select a diverse set of data points that are likely to provide the most information about the underlying model.
• Recommendation systems: Recommendation systems are used to provide personalized recommendations to users. $k$-submodular maximization can be used to select a diverse set of items that are likely to be of interest to a given user.

There are many other applications. When we mention sensor placement in the manuscript, this is related to data acquisition in machine learning. Determining the optimal placement of sensors to collect the most informative data for training a model. It is also useful in anomaly detection, where one trategically places monitoring agents within a network to maximize the chances of detecting anomalies. Meanwhile, $k$-submodular optimization is useful for resource allocation tasks, which is relevant in several ML senarios. In distributed computing, one may assign tasks to a limited number of computing nodes to optimize ML training performance and energy consumption. In cloud ML, one may allocate different types of virtual machines or containers to meet varying workloads while minimizing costs.

We have added this discussion in the revised version; see Appendix A.1 in revised manuscript.

Could you compare your results with those for submodular maximization to clarify the gap between this work and existing results for multilinear extension in submodular maximization?

Below we clarify the distinction between our work and existing results on the multilinear extension in submodular maximization, which we have addressed in lines 253–260.

Specifically, for submodular maximization, the results for monotone cases using multilinear extension-based algorithms are as follows:

1. A $(1-1/e-\varepsilon)$-approximation for $O(1)$ knapsacks;
2. A $(1-1/e-\varepsilon)$-approximation for a single matroid;
3. A $(0.6(1-1/e)/b - \varepsilon)$-approximation for the intersection of $O(1)$ knapsacks and $b$ matroids, all achievable in polynomial time with respect to $n$.

For non-monotone cases, these algorithms achieve:

1. A $(0.401-\varepsilon)$-approximation for $O(1)$ knapsacks;
2. A $(0.401-\varepsilon)$-approximation for a single matroid;
3. A $(0.24/b - \varepsilon)$-approximation for the intersection of $O(1)$ knapsacks and $b$ matroids, also in polynomial time with respect to $n$.

In comparison, for $k$-submodular maximization, multilinear extension-based algorithms yield the following results for monotone cases:

1. A $(1/2-\varepsilon)$-approximation for $O(1)$ knapsacks;
2. A $(1/2-\varepsilon)$-approximation for a single matroid;
3. A $(0.3/b - \varepsilon)$-approximation for the intersection of $O(1)$ knapsacks and $b$ matroids, all achievable in polynomial time with respect to $n$ and $1/\varepsilon$.

For non-monotone cases, the results are:

1. A $(1/3-\varepsilon)$-approximation for $O(1)$ knapsacks;
2. A $(1/3-\varepsilon)$-approximation for a single matroid;
3. A $(0.2/b - \varepsilon)$-approximation for the intersection of $O(1)$ knapsacks and $b$ matroids, also in polynomial time with respect to $n$.

Thank you for your positive feedback. We are glad that you appreciate the technical novelty of our work.

Notation departs substantially from most of the other $k$-submodular papers ...could have been introduced in a more intuitive way...

Thank you for the suggestion. It is indeed important to make the notations more friendly to the audience who are already familiar with the other definition of $k$-submodular functions (as noted in the footnote on Page 1). We have revised our manuscript (see revised version), where we highlight the existence of an equivalent definition of $k$-submodular in the introduction section. We also add this definition and explain its equivalence to our definition (Eq. (1)) in the updated Appendix A.2.

It seems like non-monotone $k$-submodular optimization just uses monotone methods with a partial monotonicity property implied by $k$-submodular. But these results don't appear to be tight, and the problem seems to be much less well understood. Can the authors shed any light on this?

It is indeed important to understand the gap between our result and negative results. We do have some intuitions for why the results for non-monotone $k$-submodular optimization are not tight.

• First, we note that even for $k=1$, there remains a longstanding open problem in closing the gap between the best known 0.401-approximation algorithm achieved by a variant of continuous greedy [Buchbinder et al., 2024] and the 0.478 inapproximability result for the non-monotone submodular optimization problem. Since $k$-submodular optimization generalizes submodular optimization, we anticipate that achieving tight results for the non-monotone $k$-submodular case will be at least equally (or even more) challenging.

• Second, most of the recent advances in continuous methods for submodular optimization concentrate on continnuous greedy and FW-type methods in the monotone case. In fact, FW acts as a continuous analogue of the greedy algorithm, mimicking its selection of high marginal gain directions and inheriting its tight $(1−1/e)$-approximation effectiveness. As a comparision, the marginal gain is hard to estimate for non-monotone case, and the linear surrogate often fails to capture the non-linear interactions between elements. This indicates that it is less likely to achieve tightness through FW-type algorithm.

[Buchbinder et al., 2024] Constrained Submodular Maximization via New Bounds for DR-Submodular Functions, Niv Buchbinder and Moran Feldman, STOC 2024.