Improved Approximation Algorithms for $k$-Submodular Maximization via Multilinear Extension
Authors: Huanjian Zhou
Lingxiao Huang
Baoxiang Wang
Venue: ICLR 2025 Spotlight (2025)
Keywords: $k$-submodular maximization
approximation algorithm
$k$-multilinear extension
Primary area: optimization
TL;DR: We provide improved or optimal approximation algorithms for $k$-submodular maximization with various constraints, via a novel framework of multilinear extension.

Abstract: We investigate a generalized form of submodular maximization, referred to as $k$-submodular maximization, with applications across the domains of social networks and machine learning. In this work, we propose the multilinear extension of $k$-submodular functions and unified Frank-Wolfe-type frameworks based on that. This continuous framework accommodates 1) monotone or non-monotone functions, and 2) various constraint types including matroid constraints, knapsack constraints, and their combinations. Notably, we attain an asymptotically optimal $1/2$-approximation for monotone $k$-submodular maximization problems with knapsack constraints, surpassing previous $1/3$-approximation results, and a factor-$1/3$ approximation for non-monotone $k$-submodular maximization problems with knapsack constraints and matroid constraints which outperforms previous $0.245$-approximation results. The foundation for our analysis stems from new insights into specific linear and monotone properties pertaining to the multilinear extension.

Published as a conference paper at ICLR 2025
IMPROVED APPROXIMATION ALGORITHMS FOR k- SUBMODULAR MAXIMIZATION VIA MULTILINEAR EX- TENSION
Huanjian Zhou 1.2 Lingxiao Huang Baoxiang Wang**
1 The University of Tokyo 2 RIKEN AIP
8 State Key Laboratory of Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University
"The Chinese University Hong Kong Shenzhen
ABSTRACT
We investigate a generalized form of submodular maximization, referred to k-submodular maximization, with applications across the domains social net- works and machine learning. In this work, propose the multilinear extension k-submodular functions and unified Frank- Wolfe-type frameworks based on that. This continuous framework accommodates 1) monotone non-monotone functions, and 2) various constraint types including matroid constraints, knapsack constraints, and their combinations. Notably, we attain an asymptotically optimal 1 1/2-approximation for monotone k-submodular maximization problems with knap- sack constraints, surpassing previous 1/3-ap////////aaaaaaaa /3-aapprxximation results (Ha et al. 2024), and factor-1/ 1/3 approximation for non monotone k-submodular maximization problems with knapsack constraints and matroid constraints which outperforms previous 0. 0.245-aprrxximatoo results (Yu et al.) 2023). The foundation for our analysis stems from new insights into specific linear and monotone properties pertaining to the multilincar extension.
INTRODUCTION
Consider the following problems in machine learning and operations research: (i) identifying influen- tial individuals in a social network with topics to maximize the number individuals influenced by at least one topic (Qian et al.] 2017 Zhang et al. 2019), (ii) partitioning a set of features into + 1 subsets such that one feature can be used in at most one regression target (or none them) for k regression targets these features (Singh et al. 2012b Zhou al. 2019). and (iii) selecting small set of sensors from & types of sensors in an area to maximize the information obtained from the sensors (Ohsaka Yoshida 2015). These problems are often constrained, such selecting sensors with different costs within finite budget. More examples can be found in Appendix A.I
Solving these problems involves maximizing a k-submodular set function f (O,...,,k) k:)" R>0 subject to some constraints. Intuitively, the k-submodularity property captures the notion of diminishing returns. For instance, consider identifying influential individuals For fixed topic, the newly selected influential individuals will contribute less to the overall user coverage many influential individuals have already been selected, and more if only a few have been selected. Similarly, adding additional features in regression problems and placing additional sensors in an area also share such diminishing returns property.
social network.
Formally, for integer A > and finite nonempty set [m]. non-negative function f (O....,k) k3 + R20 called k-submodular if for all s and in {O...., k}", we have
((s + f(t) 2 (minns t)) + fmax(( t)),
(I)
"Corresponding Huanjian Zhou, I Lingxiao Huang, Baoxiang Wang

---

Published as a conference paper at ICLR 2025
where for every i [n]]
[0, min(s, t)); [min(s;, tz),
s,t, # 0 and s tt otherwise,
and
0
0, max(s, t): maxx(s; ti),
{o,
s;t, + 0 and s; 7 tz.
otherwise.
We provide an illustrative example of sensor placement for k-submodular: Suppose there are k ==3
types of sensors and n 4 different locations to deploy them. The vector (1, 2, 0,3) means placing type-1, type-2, no sensor, type-3 sensor, in locations 1, 2, 3, 4, respectively. The vector t (0, 1,3) means placing no sensor, type-2. type-1, type-3 sensor, in locations 1, 2. 3. 4, respectively. Then mino(s. t) = (0, 2, 0) and maxo = (1, 1,3). Intuitively, adding more sensors to single task does not yield proportional benefits compared to evenly distributing them across tasks. Such diminishing return property is deseribed by Eq. (I) that 21,,2.0,3)
2, 2, 2 [11,2, 1,3) ((0, 2, 1,).. In fact, the diminishing return applies every coordinate of the problem by the inequality. Our definition of k-submodular functions (Eq. (T), which is also employed in Ward & Zivný (2016), is equivalent to an alternative definition used in Iwata et al.) (2016); Sakauc (2117). h. In this paper, we use the definition of Eq. (I since it is more convenient to define and study the properties of multilinear extension. For completeness, we give the explicit form of the equivalent definition and show their equivalence in Appendix A.2
special case of the k-submodular maximization problem is the submodular maximization problem with & = 1. The techniques for submodular maximization problems can generally be classified into two main lines. The first line is combinatorial and is mostly based on greedy rules and local search. This approach has been applied to both monotone and non-monotone submodular objective functions under various constraints (Buchbinder et al., 2015 Feige et al. 2011 Filmus & Ward 2014: Lee al. 2010a b Nemhauser al.) 1978). In some cases, optimal al algorithms have been obtained using this line of approaches (Buchbinder et al. 2015 Sviridenko, 2004). The second line is a two-staged framework based on the multilinear extension. This line of methods involves identifying fractional solution for the relaxation of the problem and then rounding the fractional solution to obtain an integral one while incurring a bounded loss in the objective. This line of approaches achieves better
approximation ratios in most cases (Buchbinder & Feldman 2019 Calinescu et al. 2011 Chekuri
al. 2010a 2014 Feldman et al. 201 laj Kulik et | (013).
Previous works in constrained k-submodular function maximization were based on combinatorial
techniques, such as the greedy algorithm. However, compared with tight approximations of submodu- lar maximization with various constraints, previous combinatorial approaches have not been able to achieve asymptotically optimal approximation results in most cases. In fact, the only tight results available are the basic case of a single matroid constraint. For example, even for the important case of monotone k-submodular maximization with single knapsack constraint, the current best combinatorial method only obtains 1/3 1/3-approximation (Ha et al. 2024), leaving a large gap with the best known lower bound of k+1 (Iwata et al. 2016).. Also, existing combinatorial methods do not provide the flexibility to combine constrannt of diffcrent types, especially O(1) knapsack constraints.
1.1 OUR CONTRIBUTIONS
We propose generalization of multilinear extension for the case of k-submodular functions (Def- inition 2.4). which allows us to use continuous optimization methods for this class of problems. Using this new concept of multilinear extension, propose unified framework, that is capable of handling different types of constraints, as well as monotone and non-monotone cases (Problem 2.3 We study classic types of constraints: matroid constraints and knapsack constraints.
We first present the results when f is non- and monotone, i.e., if fs) S ft) holds for every pair of integral vectors s, E {0, .., k:)" satisfying that every non-zero coordinate of has the same value as that of t, i.e., 1) supp(s) C supp(t), where supp(s) == {e E [m] S, # 0} represents the support set, and 2) s. = t. for all e E supp(s).
Theorem 1.1 (Informal, see Theorem 3.1). For monotone constrained k-sumoodular maximization, there exists (randomized) polynomial-time time algorithm that returns 1) 1/2 approximation for (1) knapsacks: 2) 1/2 - E approximation for a single matroid: 3) 0.3/b approximation for the intersection of O(1) knapsacks and matroids.
2

---

Published as a conference paper at ICLR 2025
Problem type of k-submod. max.
Prior results
Our results
Ha et al.
2024
(d 1)
Monotone
(Gong et al. 2024
2
knapsacks (d = 0(1)
2d2d
Yu et al.
2023
(d = 1)
Non-monotone (k 2 2)
3+2d
8
(Gong et al.
2024
3
Monotone
1
Sakaue
2017
single matroid
2
2
Non-monotone (k 2 2)
I-e
Yu et al.
2023
1
3
b matroids
Monotone
1 c (6+2)
Yu et al.
2023
(d
= 1)
0.3
d knapsacks (d (d=(0 O(1)
Non-monotone (k: 2 2)
[6
Yu et al.
2023
(d=
0.2
6++
5
Table Comparison with previous work for constrained k-submodular maximization. e can be a constant arbitrarily close to O. Symbol represents that the results are asymptotically tight.
For single knapsack constraint, we achieve an approximation ratio of 1/2 E, which aligns with the established lower bound of k+1 (Iwata et al. 2016) and is thus asymptotically tight. This outcome represents an improvement over the prior 1/3 approximation for single knapsack (Ha et al. 20224). Additionally, we successfully extend this 1/2- - approximation ratio to scenarios with T(1) knapsack constraints, maintaining asymptotic tightness. Contrasting with a recent result by (Gong et al. 2024), which provides an approximation ratio 2+2d where d represents the number of knapsack constraints, our result eliminates the dependency factor of 2d, significantly enhancing the scalability as d increases. In the context of a single matroid constraint, we also secure an asymptotically optimal approximation ratio of 1/2 - E. corroborating the findings of previous studies (Sakaue 2017).
2
Furthermore, our algorithm adeptly handles intersections of (()) knapsacks and b matroids. achieving an approximation ratio of 0.3/b E. This extends beyond the capabilities Yf et al. (2023). which addresses only the intersection of single knapsack and b matroids. We remark that for single
knapsack case, their approximation ratio (b+-()+)) is better than our ratio 0.3/b-e e for any b. Notably, 6+2
the factor 1 1/b is justified by lower bound of O(log (Appendix G of these results is available in Table
A comprehensive summary
We then present results when ʃ is non-negative and non-monotone.
Theorem 1.2 (Informal, see Theorem F.I.. For non-monotone constrained k-submodular maxi- mization where 2 there exists a (randomized) polynomial-tine algorithm that returns 1) 1/3 approximation for O(1) knapsacks; 2) 1/3 33- approximation for single matroid 2) 0.2/b approximation for the intersection of (()) knapsacks and matroids.
The theorem presents enhanced approximation ratios for non-monotone objectives under knapsack and matroid constraints. Specifically, for single knapsack constraint single matroid constraint, we have improved the approximation ratio from (1 - - (approximately 0.25) as established by (Ha et al. 2024). 1/3 E (upproximately 0.33). Additionally, for scenarios involving d = (1) knapsack constraints, we maintain this improved ratio of 1/3 surpassing the recent result of 1/(3 + 2d) found in (Gong al., (024)) Our results eliminate the dependency factor of 2d, thereby significantly enhancing scalability as increases.
Furthermore, we extend the improvements beyond the framework of the intersection of a single knapsack and b matroids, as in Yu et al., 2023), to include intersections of O(1) knapsacks and b matroids, with only minimal reduction in the approximation ratio. See also Table for a summary.
1.2 TECHNICAL OVERVIEW
We adopt the idea of two-stage continuous methods of submodular maximization for k-submodular problems. Our techniques, however, depart crucially from the works of submodular maximization in the design of multilinear extension for k-submodular functions (Definition 2.4) and the utilization of its new properties (Lemma C.I). With the multilinear extension for k-submodular functions, further introduce Frank- Wolfe-type methods (Algorithms/ [ and 33 and a novel rounding scheme (Lemma 3.2 and F33) Below summarize these notion contributions and technical novelties.
3

---

Published as a conference paper at ICLR 2025
Recap of multilinear extension for submodular functions For submodular function f {0, 1)" + Rzo, its multilinear extension F : [0, 1|" - Ry0 provides a useful relaxation of f to the continuous space [0, 1]" Intuitively, for every item E [n], fractional value x; in the relaxed continuous space [0. 1] represents that the item is selected with probability x;. Hence, given fractional point [o, 1) F(x) is defined as the expected value of f(S) where each element i is included in the random set S with probability x, Such a formulation based on the expectation maintains coordinate linearity and specific submodular properties in continuous domain. The advantageous properties of multilinear extensions have been leveraged in numerous previous studies, such as Buchhiindrr & Feldman (2019); EEne Nguyen (2016); Calinescu et al. (201T): Chekuri et al. (2014), to develop continuous methodologies for constrained submodular maximization. This approach typically unfolds in two distinct phases.
In the continuous optimization stage, the process begins with an empty initial solution x(0) 0 and progressively updates this solution within the interval [0, 1]. Through continuous methods, a fractional solution x(1) E [0, 1]" is derived, which approximates the maximization of the extension F subject to certain combinatorial constraints. For example, the well-established Frank- Wolfe algorithm (Calinescu et al., 201T) iteratively updates the current solution by moving it in the direction of constrained vector v that maximizes the local gain, quantified by FV)()), v), where V F denotes the gradient vector of F at x. Each iteration aims enhance the value of F(x) by an amount proportional to F(o") - F(x), with o' E [o, 1j" being the vector that optimizes the multilinear extension F under the given constraints. Following the continuous optimization, the rounding stage involves converting the fractional solution x(1) into feasible integral solution. In this stage, each element i vies for inclusion based on its coordinate value x(1);. thereby rounding x(1) to an integral form that adheres to the problem's 's constraints. This two-stage framework not only facilitates the effective handling of combinatorial constraints but also optimizes the solution with respect to the submodular function's 's multilinear extension.
Notion contribution: multilinear extension of k-submodular functions. We introduce the concept of the k-multilinear extension for k-submodular functions (Definition 2.4 which serves as a natural extension to the multilinear extension for submodular functions. For an item E [n]. our goal is to represent probability distribution the set {0, 1...., ..) using fraction point x,, To achieve this, we specify the domain of each x; as 4 {y E 1] Eド y, S 1), where each coordinate Xs, indicates the probability of item i being assigned to state j. and 1 1 -) X represents the residual probability that item i being assigned to state 0. Subsequently, a k-multilinear extension F is defined over the domain Ag. where Fxx) (for Ag) computes the expected value of (s), with each S; = j occurring with probability Xi.j-
The k-multilinear extension exhibits several advantageous properties that facilitate the development of continuous optimization methods. These include multilincarity, element- non non-positive Hessian, pairwise monotonicity, approximate linearity, and the preservation of monotonicity as delineated in Lemma C.I The richness of these attributes makes the k-multilinear extension a compelling subject of study for k-submoddular functions and could potentially offer valuable insights independently.
Challenges of using k-multilinear extension. Similar to the submodular case, we aim to use the k-multilincar extension to design two-staged continuous methods. The extension of the rounding stage is rather straightforward, for both monotone and non-monotone cases (Lemmas 3.2 and F.3). The technical challenges come from the continuous optimization stage, which we summarize below.
Closure: The domain of submodular extension is [0, 1J", which benefits the closure of the coordinate-wise maximum operation, i.e., x V E [0. 1]" for all x,y E [0, 1]". This prop- erty is crucial in the analysis of the approximation ratio of the derived fractional solution x(1). However, the domain of k-submodular extension is the corner of the cube A rather than [0, 1nn Consequently, the closure property no longer holds.
Approximate linearity: Another advantageous property of submodular extensions is their approx- imate linearity, whereby the function F closely approximates a linear function along any given direction (Bian et al. 2017). This property significantly influences the value change each step in continuous optimization methods. However, it remains uncertain whether this property extends to k-submodular extensions, given the complex structure introduced by the & coordinates.
4

---

Published as a conference paper at ICLR 2025
Technical novelty. Our technical contributions lie in tackling these challenges by introducing auxiliary points for analysis and uncovering novel properties k-multilinear extension. We outline these approaches below.
To address the initial challenge about closure, we shift our focus to the operation of linear combination, which constructs ax + (1 a)y (for [0, 1)) for x Ag. rather than using the coordinate wise maximum for submodular. This operation benefits from closure within Ag thereby facilitating the construction of auxiliary points for analytical purposes. More specifically, we consider of as the optimal fractional solution for the k-submodular extension F. At each time step / E [0. 1], we We generate a pseudo-convex nonvex-combination point o
define xt) E AE as the current point | x(t) + (1 - t)o", an auxiliary point that is assuredly within Ag due to the set's 's closure properties. This method of using
points aligns with approaches previously explored in literature, such as Iwata et al. (2016). Ohsaka & Yoshida (2015), and Sakaue (2017). These studies have demonstrated the utility of such points in facilitating detailed and effective analysis.
Then we investigate the relation between ((x(t) and F(o(()), whose key is to address the afore- mentioned second challenge about approximate linearity. When / monotone, we demonstrate that (xx(1= (1 8))
F(o(L)) ((o(L + 8)), which directly leads to conclusion that F(x(1)) 2 2 F(o*) (Lemma 3.3 h. Theorem 1.1 is a direct corollary of this conclusion and the round-
(t)
>
ing guarantee (Lemma 3.2). we establish this result based extending the approximate linearity
property for submodular to k-submodular functions (Lemma C.I This property captures certain Lip- schitzness of k-multilinear extension F and allows us to estimate the increment ((x((++))-=F(x(( for sufficiently small values of 5.
When f is non-monotone, monotonicity (Lemma C.I which help reduce the problem to the monotone case. Utilizing pairwise monotonicity, we are able to obtain an approximation F(x(1)) 2 F(("") (Lemma F.2). Similarly, Theorem is direct corollary of this approximation and the rounding guarantee (Lemma 3.2
utilize new property of k-multilinear extension F, called pairwise
Comparison with existing combinatorial approaches. We demonstrate that our approach using continuous optimization methods yields improved approximations for knapsack constraints compared to prior combinatorial methods such as those presented in (Ha et al. [0244] Yu et al. (023). We offer intuitive explanations for this improvement and observe that similar conclusion holds for submodular maximization with ((1) knapsack constraints: to the best of our knowledge, combinatorial method achieves an optimal approximation, whereas an optimal approximation algorithm via multilinear extension has been presented by (Chekuri et al., 2014)). Our findings may suggest that the flexibility of continuous methods selecting stepsizes and update directions provides an advantage over combinatorial approaches for handling knapsack constraints.
1.3 OTHER RELATED WORKS
Submodular maximization, special case of k-submodular maximization, has rich line of research with numerous results. In the monotone case, ( aaprooximmaionnns have been proposed for various constraints, such as single matroid constraint and O(1) knapsacks constraint (Cälinescul et al. 2011 Chekuri et al.) 2014] Kulik et al. 2009)) Nemhauser et al. 1978). Furthermore, additional results have been developed for more complicated constraints, including the intersection of matroids and exchange systems (Feldman et al. 20116]] Lee et al. (010b). In the non-monotone case, the best- known approximation ratio for the single matroid or ((1) knapsack constraint 0.401 (Buchbinder & Feldman 2024) while the hardness of 0.478 holds for single matroid (Gharan & Vondrák][011]
-1-11
Concurrent work Recent developments in k-submodular maximization research have introduced new algorithms with varying approximation ratios. For single matroid constraints, the threshold- decreasing algorithm in Niu et al. (2023) achieves a 1 /22aapprxximation ratio for monotone objectives and a3-aapprxiimttion ratio for non monotonee cases. For single knapsack constraints, an alterna- tive greedy algorithm with 0.432- and 0.31 aapproxiiiiii ratios for monotone and non-monotone objectives, respectively, is presented (Xiao et al., 2023). In comparison, our algorithms outper- form these approaches by achieving better approximation ratios or allowing more general types of constraints. For instance, for the non-monotone case with a single constraint, our algorithm
1 AE is defined as (y E AE ty A
5

---

Published as a conference paper at ICLR 2025
achieves approximation ratio 1/3 instead of 0.317 in (Xiao et al. 2023). Our algorithms also offer greater flexibility across various constraints and achieve a tight 1/2 approximation ratio for monotone objectives and 1/3 approximation ratio for oo-monotonee objectives with ((1) knapsack constraints and single matroid constraints.
2 PROBLEM FORMULATION AND k- X-MULTILINEAR EXTENSION
In this section, we first define the constrained k-submodular maximization problem and then present the notion of k-multilinear extension. Let [n] be the ground set. Let f (0.I..... k}" - R20 be non-negative k-submodular function. Throughout this paper, we assume there exists a value oracle O that answers f(s) for any query s kk.".
k-submodular maximization with matroid and knapsack constraints. As outlined Section [ our study encompasses two classic types of constraints: matroid and knapsack constraints. In the context of submodular functions, these constraints are typically defined over the domain 2". Specifically, constraint for submodular functioon is represented by down-close collection I C 2", where "down-close" means that for any S E I and S S, T also belongs to I.
However, it is important note that the domain for k-submodular function is not 2" but {0.... k)m. Consequently, a é-submodular setting, it becomes necessary to adapt any given constraint the domain {0, .......... h : This adaptation involves defining the constraint based the support set supp s) of a vector s E {O..... k) k)"", where supp(s) is defined as the collection of indices corresponding to non-zero coordinates of s. Therefore, vector s {0, ..... k]" is deemed feasible with respect the constraint Z if and only if its support set, supp(s), is a member of Z. This redefinition ensures that the extended constraints
appropriately applied within the k-submodular context.
Using this idea of domain adaption, we provide the following notions of matroid constraints and knapsack constraints for k-submodular maximization.
Definition 2.1 (Matroid constraint for k-submodular maximization). Denote matroid by pair M = ([m], IM) where IM C 2", such that 1) AB E IM. A C = A E IMi 2) BA, IM. A < |B] + 3x B A s.t. AU {r} E IM. matroid constraint for k-submodular is defined to be the collection of all vectors S E k)....,kj" whose support set supp(s) s) IM, i.e., CM = {s E (O......A. ".]".......... supp(s) E IM}.
Definition 2.2 (Knapsack constraint for k-submodular maximization). Given non-negative vector a E 2 define Ix = (S a 1s < 1}, where ls is the indicator vector of set S [n]] A knapsack constraint is defined to be the collection of all vectors s E (o....,k] k} whose support set supp(s) Ix}.
supp(s) Ix, i.e., Cx = {s (0.....k)
kk)"
We now ready define the following problem.
Problem 2.3 (k-submodular maximization with matroid and knapsack constraints). Given
a k-submodular function f {0, 1, 1,...,k) - R2z, b matroid constraints C..,.... CM,, and knapsack constraints Ck,,.... CK.. the objective is identify vector E {0, 10.1,..., k) that
maximizes f(s) subject the constraint: E (Niefo; Cm.) n (Nietay Cx.).
Particularly, when b and d O, this scenario is termed k-submodular maximization with matroid constraint; conversely, when = 0 and d = 1, it is known as k-submodular maximization with knapsack constraint. To solve this problem, the idea is to design continuous methods, which are widely used for the submodular case. To this end, we extend the notion of multilinear extension of submodular functions to the k-submodular case.
Multilinear extension of k-submodular functions. The first step is to relax the domain of k- submodular functions. Recall that in the submodular context, the domain of multilinear extension is [0, 1]". which is relaxed from {0. 1)" For each item i [n)] fraction value E [0, 1] represents probability of selecting i. Now we tend to k-submodularr functions, whose domain is {0. 1.....,k] k}" The first idea is to relax this domain [0, k]" However, it is unclear how
fraction value x; E [0, k] to represent a probability (distribution) in [0, k)".. To address this issue, we utilize the idea of one-hot encoding that encodes value E (0. 1, 1,.... k) by k-dimensional vector

---

Published as a conference paper at ICLR 2025
b {0, 1 with by = = and b, otherwise. This encoding motivates us consider the
domain A = {y E [0, Σj= Yj I } to represent probability distributions on discrete values (0. k). To be specific, a vector x E A represents a probability distribution, where each j E [k]
assigned with probability Xj. Thus, the domain of the k-multilinear extension of k-submodular
function is defined to be the comerr of the cube 4 == x E [0, 1] Σن= X 1, [n]]
Note that & can be viewed a (partition) matroid polytope with rank 1 and nk elements. ready to propose the following notion of multilinear extension of k-submodularr functions.
- We
Definition 2.4 (k-multilinear extension). Given k-submodular function f: {o,...,,k. ,,,"" R20. the k-multilinear extension F: Ag R20 is defined as
(1
F(x) = E f(s) KE(.....k)"
II X
II =c(n]=:;=0
Σ Xi.) j=1
(2)
For every Ap, it follows that F(x) [s]( where E (0,..., 33""" denotes random vector: for each item i E [n], S, = for j E [k] with probability x, and otherwise, 8 = 0, which occurs independently across all items. Multilinear extension of submodular function special case of Definition 2.4 when A: = 1.
Designing continuous algorithms via multilinear extension typically necessitates computing the gradient of the function F. However, accurately calculating the gradient value FF(x) for a vector x AE involves an exponential number of queries to the value oracle O,, presenting a significant computational challenge. To mitigate this issue, we propose a method for constructing approximate gradient oracle, as outlined in the following lemma. The implementation details and proofs can be found in Appendix B
Lemma 2.5 (Existence of approximate oracle O ). Given E E (0, let F be the k- multilinear extension of f. There is an oracle (l that for any E AG. calls O, for at most
16kn log x2+1)
times and returns a stochastic estimate VF((x) of the gradient V Fx)) such that for all i E [m] and j E [k]. 0. F(x) - F(x) S
with probability at least 1 En nvk'
sM
x=
We find that k-multilinear extension enjoys several useful properties. We first note that the following preservation of monotonicity trivially holds: if a k-submodular function f is monotone, its k- multilinear extension F is also monotone.
Let := maxxmaxxx I (ex,s) - f(0), 0} be the maximum value of an element determined by J. where oi.j is basis vector Rank with only the (i.j)-th entry being 1. The following another useful property of F, called element-wise non non-positive Hessian:
==
i = i2.
(3)
[-
if + i2.
Furthermore, we observe the following approximate linearity property for F: for any points x, x' Ag satisfy that x' - x 5 Ag we have
F(x') - F(x)
(EEm),JE xi,) -.,, -2
(4)
As discussed in Section 1.2 this property is essential for the analysis of Wolfe type algorithm. These properties, together with other useful properties, are summarized in Lemma C. and their proof' can be found in Appendix
Continuous constraints for k-multilinear extension and membership oracle. In addressing the continuous domain Ag for k-multilinear extension, it becomes necessary to adapt both matroid and knapsack constraints to this continuous framework. Initially, we define polytopes that correspond to these constraints:
Despite the similarity in appearance, there is known reduction from k-submodular function to submodular function with partition matroid constraint. See Appendix A.3 for details.
7

---

Published as a conference paper at ICLR 2025
For a matroid constraint defined by collection IM. establish its corresponding polytope PM as conv(1, : 5 E ΣM}, where 1s denotes the indicator vector of set S. For a knap- sack constraint characterized by vector E RS define the corresponding polytope Px: a
as {x E [0, = x S 1]. Another important notion is how a fractional vector within A relates to polytope. Given vector E Ag. say x is consistent with a polytope P. denoted as x P. if [C) () X1,j..... Ej- Xn.) P. Additionally, we define membership oracle Op that, given a vector X E Ag determines whether x ~ P.
With these definitions in place, vectors in AE: vector x satisfies a matroid constraint if x ~ PM, and satisfies knapsack constraint if x Px. We further present lemma demonstrating the existence of membership oracle for these relaxed constraints.
illustrate how to relax matroid and knapsack constraints for
Lemma 2.6 (Existence of membership oracle (Cunningham, 1984)). For any constraint P (Niem)) P.M)) ) Pk.) of the intersection of matroid constraints and knapsack constraints, there exists an efficient membership oracle Op.
well-established that with access to membership oracle Op, linear optimization problems involving the function F can be efficiently addressed using Frank- Frank-Wolfe-tye methods, as noted by Lee et al. 2018). To address Problem 2.3 we frame a constrained optimization challenge within a continuous domain: We aim maximize k-multilinear extension F A 22 fractional point x E Ah. subject to the constraint x ~ P, where P is a down-closed convex polytope.
Define arg maXx~P Fxx as the optimal fractional solution for this continuous optimiza- tion scenario. We assume that for every i E [n). the unit vector e; is within P. If not, the i-th element irrelevant to the constrained k-submodular maximization problem and be excluded. With this premise, it follows that F(o") 2 F(e..) = f(eij). Recalling that M max (max.,; f(e..)) - f(0). 0}, we establish that F(o*) 2 M.
RESULTS FOR MONOTONE d-SUBMODULAR MAXIMIZATION
In this section, we consider the case that the objective k-submodular function f is monotone.
Theorem 3.1 (Main theorem monotone case). There exists a polynomial-time algorithm that given monotone k-submodular f {0, l.....,k] k}" and a constraint polytope P C A with probability at least т}, outputs a solution that is
G -'ppproxie under single matroid constraint, with calling O, at most times and calling Op at most O n log( for any fixed e > 0;
Knn log
( <) approximate under the intersection of (1) knapsack constraints, with calling O at most (:poly( poolv(t)) times and calling Op at most O (kpooytt) moolu()) ) any any
fixed 0:
(0.3 approximmaet under the intersection of matroid constraints and O(1) knapsack constraints, with calling Oy at most O poll(1) times and calling Op at most wewpooooiiiiiii for any fixed e O.
The difference in approximation guarantees and query complexity arises due to the rounding pro- cedure's 's impact under varying constraints. Our algorithm maintains consistent approximation ratio for the k-multilinear extension across down-closed constraints (Lemma 3.3). but the rounding effectiveness varies, leading different guarantees (Lemma 3.2
We remark that our query complexity is usually larger than existing combinatorial methods, e.g., a 0.432 -432-approximmte algorithm with a query complexity of O(k9n for single knapsack constraint NNuu et al.) 2023). Nevertheless, the focus of this paper is to improve the approximation ratio, specifically achieving (asymptotically) optimal approximation algorithms.
8

---

Published as a conference paper at ICLR 2025
In Section 3.1 we propose unified optimization framework thereof, and in Section
we analyze 3.2
the approximation ratio Theorem 3.1 The complete proof of Theorem 3.1 can be found in Appendix E We can also extend the result to non non-monotone case; see Appendix
3.1 THE ALGORITHM
In this section, propose the algorithm for Theorem 3.1 using k-multilinear extension. The algorithm consists of two stages: a continuous optimization stage and rounding stage.
The continuous optimization stage. In the first stage, we design a Frank-Wolfe method to approximately maximize the k-multilinear extension (Algorithm Dp
Algorithm 1: Frank-Wolfe algorithm for the monotone case, FW(J, 8,
Input: Oy. Op.Op and hyperparameters e, 1/ (0, 1).
Initialize: x(0) 0, t <- 0; stepsize 8 = N with N = [n 0(50)) by Lemma 2.5
while ( < do
find a direction v(t) = arg max va v- (V((x(t),,)
D By LP
x(t + 5) x(t) + 6v((), + return x(1).
The Frank- Wolfe algorithm terminates after the N-th iteration. During each iteration, the surrogate function (Vs(s)))) v()) is utilized identify the feasible direction that maximizes the improve- ment in the function value. This process involves maximizing a linear objective subject to constraints defined within a polytope in the positive coordinate space. The computational effort required per iteration is comparable to solving positive linear program (LP), for which a quadratic time solver is documented in Lee et al. (2018).
The Rounding Stage. Let x(1) represent the fractional solution obtained from Algorithm The subsequent stage involves rounding x(1) an integral solution. The performance of this rounding process is encapsulated in the following lemma.
Lemma 3.2 (Rounding scheme). Let e, 1 E (0, 1), and P be polytope. Suppose for any monotone k-submodular function f', Algorithm FW(f', F(x) maxyed y-p Fly). Then for any > 0, there exists a rounding scheme that outputs solution E {O....,k) k)" with ~ P, that is
7) outputs solution x E A that satisfies
a-approximate under single matroid construint, i.e., f(s) 2 with calling FW one time and calling Op at most O(Nn²) times;
((s),,
a<1 - -)ppproximeaee under O(1) knapsack constraints, with calling FW, Of, Op at most O (1:0ol((1/))) polyt//ee) times;
((66e -)- approximate under the intersection of b matroid constraints o knapsack constraints, with calling FW, Op most O (nnoky()))) times.
Our rounding scheme is extension of the approaches developed for submodular maximization. as detailed in works by (Cälinescu et al., 2011 Chekuri et al. 2014 2010b). Specifically, for a single matroid constraint, the rounding procedure directly applied the output of FW(J, P, n). necessitating only a single invocation of the FW algorithm. For knapsack constraints, where elements might exhibit large costs significantly influence the function value, enumeration stage akin to that used in submodular maximization (Chekuri et al.) 2014) is employed, resulting in complexity of (Loo))()))) This process is extended by first employing the continuous maximization algorithm FW(J". P', (P',,,7) 1)). where f' and P'' represent marginal function and a restricted polytope specifically for large elements. By enumerating all possible restrictions and selecting the optimal result, the complexity becomes (kpoov((1/)) poly (1/6)) given that the number of large elements is capped at O(poly(1/E) Each large element has & potential assignments, amplifying the complexity by factor of (LoE)))))))) Details and proofs provided in Appendix

---

Published as a conference paper at ICLR 2025
3.2 PERFORMANCE ANALYSIS OF ALGORITHM 1
We focus on proving the approximation ratio of Theorem in the main body. Recall that o*
:=
arg max max xx F(x). By Lemma 3.3 it suffices prove the following key lemma.
Lemma 3.3 (Analysis of the Frank- Wolfe algorithm). When I is monotone, then F(x(1)) 2
(5 2z) F(o"), with probability at least 17
Technical novelty in the proof of Lemma 3.3 As discussed in Section due the closure
challenge, we consider the following operation of linear combination: for each time step / E [0, 1,, we generate auxiliary point ol) = x(1) + (1 - -))o-. Since x(!) L. Ag. this auxiliary point
ot) must be within AE. We find that, to prove Lemma 3.3 it suffices to prove
F(x(t+ + 6)) ((x(()) > F(o(()) F(o(t + 6)) 3eM6, which lower-bounds the value gain of each iteration. Recall that M max m (maxi. ((e)))- ((), 0).
(5)
To see this, we note that by summing over all t,
F(x(1)) 2 F(x(1)) - F(x())) 2 F(o(0)) F(o(1)) 3: = F(o*) - F(x(1)) - 3. Rearranging this inequality, we obtain that F(x(1)) 2 ((0)) M. Recall that F(oo)= 2 M. Thus, we conclude that F(x(1)) 2 ( -2e) F(o*).
It remains to prove Ineq. (5) The key is to provide lower bound for F(x(t + 8)) - F(x(t))
and an upper bound for F [t)) - Flo(t + 6))). We first note that F(x(t + 8)) - F (x(()) 2
(VF(x(t)), o²)6 M6. To see this, using Ineq. 4 and the fact that 5 S 2 we have
F(x(t + 8)) - F(x(t))= 2 (VF(x(t)), v(t) n2 2 (VF(((t)), v(t)) eM (MM)
(6)
where v() is the local optimal direction obtained in Line 3 of Algorithm 1 Furthermore, using
the theoretical guarantee of approximate oracle ofF-r) stated in Lemma 2.5 we can conclude that
(VF(((()), v(t) > (V o*) 2rM. Combining with Ineq. (6) we can conclude that
F(x(t+ + 0)) - F(x(t) 2 (F)((()), 0*)6 M6.
Next, we show that (() F(o(( + 6)) S (VF(x(()), o*)0. This inequality, when combined with Ineq. (6). concludes Incq. (5) To derive this bound, we define the component-wise minimum 6) o". By analyzing the trajectory from o(t + 6) to o'(t) and then to o(t), we observe a decrease in each coordinate during the first transition and an increase during the second. Given the function's 's monotonicity, we infer that F(o(t)) - F(o(t+))) S F(o(t)) - F(o'). Furthermore, leveraging the concavity along the positive direction o(!) - o' = d0* as specified by Eq. (3). we deduce that (((( - F(o')= I (VF(o' ( o Finally, considering the non- non-innreaseeee increasing nature of the partial derivative (also confirmed by Eq. (3 and the fact that o e A
of (t) and ot + 8) as o' o'(t) x(t)
we establish that (o' (t)) o 0-)6 8 (VF(x(t)), o*) Thus, summarizing the above findings, we confirm that F(o(t)) Flo(t- + 6)) < (VF(((t)), o6)
The details of the proof of Lemma 3.3 can be found in Appendix
4 CONCLUSIONS AND FUTURE WORKS
We introduce a unified Frank-Wore Wolfe-type framework for addressing k-submodular maximization across various settings. Notably, we achieved an optimal 1 1/2-approximation for monotone k- submodular functions and 1 1/3-approximation for non-monotone functions under constraints of a single matroid and O(1) knapsacks. Our framework is adaptable to a broad range of constraints. including any combination of matroid and knapsack constraints.
The foundation of our frameworks is the multilinear extension of k-submodular functions, which facilitates the design of maximization algorithms that allow for flexible step sizes and update di- rections. Given the success of multilinear extensions in achieving optimal outcomes in numerous submodular maximization scenarios, approach to extending and rounding k-submodular functions may present novel avenues for further research and application.
There are several interesting directions for future exploration. Determining tight approximation ratios for non-monotone k-submodular maximization is an intriguing challenge that continues to be of significant academic interest. Furthermore, the potential to derandomize k-submodular maximization algorithms offers a valuable area of inquiry, particularly for applications that benefit from deterministic outputs, enhancing both reproducibility and consistency in practical deployments.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
HZ was supported by International Graduate Program of Innovation for Intelligent World and Next Generation Artificial Intelligence Research Center. LH has been supported by the New Cornerstone Science Foundation. BW was partially supported by the National Natural Science Foundation of China (62 (02106,13, 72394361), Longgang District Key Laboratory of Intelligent Digital Economy Security, and an extended support project from the Shenzhen Science and Technology Program.
REFERENCES
Noga Alon and Joel H Spencer. The probabilistic method, 3rd ed. John Wiley & Sons, 2008.
Andrew An Bian, Baharan Mirzasoleiman, Joachim Buhmann, and Andreas Krause. Guaranteed non- convex optimization: Submodular maximization over continuous domains. Artificial Intelligence and Statistics, pp. 111-120. PMLR, 2017.
Niv Buchbinder and Moran Feldman. Constrained submodular maximization via nonsymmetric technique. Mathematics of Operations Research, (113):9881005, 2019.
Niv Buchbinder and Moran Feldman. Constrained submodular maximization via new bounds for dr-submodular functions. In Symposium on Theory of Computing, STOC, 2024.
Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. A Tight Linear Time (1/2)- Approximation for Unconstrained Submodular Maximization. SIAM J. Comput., 4485):1384-1400 2015.
Gruia Cälineseu, Chandra Chekuri, Martin Pál, and Jan Vondrák. Maximizing a monotone submodular function subject to matroid constraint. SIAM J. Comput., 4066):7740-1766 2011.
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 51th Annual IEEE Symposium on Foundations of Computer Science, pp. 575 584. IEEE Computer Society, 2010a.
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 5 Annual Symposium Foundations of Computer Science, 2010b.
Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Submodular Function Maximization via the Multilinear Relaxation and Contention Resolution Schemes. SIAM J. Compur., 43(6):1831-1899, 2014.
Yixin Chen and Alan Kuhnle. Practical and parallelizable algorithms for non-monotone submodular maximization with size constraint. volume 79, 2024.
William H. Cunningham. Testing membership in matroid polyhedra. Comb. Theory, Ser. B, 36(2): 161-188, 1984.
Alina Ene and Huy L Nguyen. Constrained submodular maximization: Beyond 1/c. In 2016 IEEE 57th Anmual Symposium on Foundations of Computer Science (FOCS), pp. 248-257. IEEE, 2016.
Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non-monotone submodular functions. SIAM J. Comput., 40(4): 133- 1153, 2011.
Moran Feldman, Joseph Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 570-579. IEEE, 2011a.
Moran Feldman, Joseph Naor, Roy Schwartz, and Justin Ward. Improved approximations for exchange systems. In Algorithms ESA 2011: 19th Annual European Symposium, pp. 784-798. Springer, 2011b.
Yuval Filmus and Justin Ward. Monotone submodular maximization over a matroid via non-oblivious local search. SIAM Journal Computing, 534255514-542, 2014.
11

---

Published as a conference paper at ICLR 2025
Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing. In Dana Randall (ed.), Proceedings of the Twenty-Second Anmual ACM-SIAM Symposium on Discrete Algorithms, pp. 1098-1116. SIAM, 2011.
Shu-Fang Gong, Bin Liu, and Qi-Zhi Fang. Streaming algorithms for maximizing k-submodular functions with the multi-knapsack constraint. Journal of the Operations Research Society of China, 2024.
Dung Ha, Canh Pham, and Tan Tran. Improved approximation algorithms for k-submodular maxi- mization under knapsack constraint. Computers & Operations Research, 2024.
Elad Hazan, Shmuel Safra, and Oded Schwartz. On the complexity of approximating k-set packing. Comput. Complex. 15(1):20-39 2006.
Satoru Iwata, Shin-ichi Tanigawa, and Yuichi Yoshida. Improved approximation algorithms for k-submodular function maximization. In Proceedings of the twenty-seventh annual ACM-SIAM symposium on Discrete algorithms, pp. 404 413. SIAM, 2016.
Ariel Kulik, Hadas Shachnai, and Tami Tamir. Maximizing submodular set functions subject to multiple linear constraints. Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 545-554. SIAM, 2009.
Ariel Kulik, Hadas Shachnai, and Tami Tamir. Approximations for monotone and nonmonotone submodular maximization with knapsack constraints. Mathematics of Operations Research, 38(4): 729-739, 2013.
Jon Lee, Vahab S Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Maximizing nonmono- tone submodular functions under matroid or knapsack constraints. SIAM Journal on Discrete Mathematics, 23(4):2053-2078 2010a.
Jon Lee, Maxim Sviridenko, and Jan Vondrák. Submodular maximization over multiple matroids via generalized exchange properties. Math. Oper. Res., 35(4):795-806 2010b.
Yin Tat Lee, Aaron Sidford, and Santosh S Vempala. Efficient convex optimization with membership oracles. In Conference On Learning Theory, pp.
2018.
George Nemhauser, Laurence A Wolsey, and Marshall L Fisher. An analysis of approximations for maximizing submodular set functions-i. Mathematical programming, 14:265-294, 1978.
Shuxian Niu, Qian Liu, Yang Zhou, and Min Li. Fast algorithms for k-submodular maximization subject to matroid constraint. arXiv preprint arXiv:2307.13996 2023.
Naoto Ohsaka and Yuichi Yoshida. Monotone k-submodular function maximization with size constraints. In Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, pp. 694-702, 2015.
Chao Qian, Jing-Cheng Shi, Ke Tang, and Zhi-Hua Zhou. Constrained monotone k-submodular function maximization using multiobjective evolutionary algorithms with theoretical guarantee. IEEE Transactions on Evolutionary Computation, 22(4):595-608, 2017.
Shinsaku Sakaue. On maximizing monotone k-submodular function subject to matroid constraint.
Discrete Optimization, 23: 103,110--111111111111111 2017.
Ajit Singh, Andrew Guillory, and Jeff Bilmes. On bisubmodular maximization. In Artificial Intelligence and Statistics, pp. 1063. PMLR, 2012a.
Ajit P. Singh, Andrew Guillory, and Jeff A. Bilmes. On bisubmodular maximization. In Neil D. Lawrence and Mark A. Girolami (eds.), Proceedingy of the Fifteenth International Conference on Artificial Intelligence and Statistics, volume 22 of JMLR Proceedings. pp. 1055-1063. JMLR.org. 2012b.
Maxim Sviridenko. A note on maximizing a submodular set function subject to a knapsack constraint. Oper. Res. Lett., +2(1):41-44 2004.
12

---

Published as a conference paper at ICLR 2025
Justin Ward and Stanislav Zivný. Maximizing k-submodular functions and beyond. ACM Trans. Algorithms, 42::6, 2016.
Hao Xiao, Qian Liu, Yang Zhou, and Min Li. Approximation algorithms for k-submodular maxi- mization subject to knapsack constraint. arXiv preprint arXiv:2306.14522 2023.
Kemin Yu, Min Li, Yang Zhou, and Qian Liu. On maximizing monotone or non-monotone submodular functions with the intersection of knapsack and matroid constraints. Journal of Combinatorial Optimization, 45(3):1-21, 2023.
Yuhui Zhang, Ming Li, Dejun Yang, and Guoliang Xue. A budget feasible mechanism for k-topic influence maximization in social networks. In 20/9 IEEE Global Communications Conference (GLOBECOM), pp. 1-6, 2019.
Zhi-Hua Zhou, Yang Yu, and Chao Qian. Subset selection: k-submodular maximization. Evolutionary Learning: Advances in Theories and Algorithms, pp. 233-254, 2019.
13

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
Our contributions
Technical overview
Other related works
2
Problem formulation and k-multilinear extension
3
Results for monotone /-submodular maximization
3.1
The algorithm
3.2
Performance analysis Algorithm
10
4
Conclusions and future works
10
Additional discussion
15
A.1
More examples of k-submodular application in machine learning
15
A.2
An equivalent definition of k-submodular functions
15
A.3
Æ-submodular can not be reduced to submodular with a partition matroid
16
B
Proof of Lemma 2.5; Existence of an efficient oracle OF
16
Properties of k-multilinear extension
18
Proof of Lemmal 3.2; A novel rounding scheme
21
E Proof of Theorem 3.1 Performance analysis of Algorithm |
25
Results for non-monotone Assubouuuar maximization
27
Hardness for the intersection O(1) knapsacks and matroids
30
14

---

Published as a conference paper at ICLR 2025
A ADDITIONAL DISCUSSION
A.1 MORE EXAMPLES OF A-SUBMODULAR APPLICATION IN MACHINE LEARNING
While submodular maximization may be more famous in the MI. community, many applications of 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 a given task. k-submodular maximization can be used to find diverse set of features that maximizes the performance of a model.
Active learning: Active learning is technique for selecting the most informative data points to label, which can help to reduce the cost of labeling data. k-submodular maximization can 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 select diverse set of items that are likely to be of interest to given user.
There are many other applications. When mention sensor placement in Section I this is also 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 relevant in several MI. senarios. In distributed computing, one may assign tasks to limited number of computing nodes to optimize MI. training performance and energy consumption. In cloud MI., one may allocate different types of virtual machines or containers to meet varying workloads while minimizing costs.
A.2 AN EQUIVALENT DEFINITION OF Á-SUBMODULAR FUNCTIONS
In this subsection, demonstrate the equivalence between the definition of k-submodularity (Eq. ① and another definition (Definition II in the literature. We first recall another definition as follows.
Definition A.1 (Alterative definition of k-submodular Sakaue (2017)). Let (k 1)a
{(XI...... .x)) X; S [n] (i 1,.... k), x,nX, = 0 (i+ j)}. Then, a function J : 11) - TR
called k- submodulla if. for any X (XI..... Xx) and Y (Yy....,,, Ys) in (k + 1)", we have
+ f(x) + f(Y)= (X
where
Xny (XIN,, ...., NeNYa).
XUY : (XUMM (UX,U)) .... X.UYA
... (EUY((UX,Y)) (Ux.))))
We also recall our definition defined by Eq. I in Section !
Definition A.2 (Our definition of k-submodular). For an integer lo and a finite nonempty [n), a non-negative function f {o....,k. k)m" + Rzo is called k-submodular if for all s and t in k)", we have
((s) + f(t)= 2 [minns t)) + (max(ss t)),
(8)
where for every i E [n].
10. min(s, t); minss, t,), 0
s,t, + and s; + ti, otherwise,
and
s,t, # and s; + t., otherwise.
max(s, t)2 max t;),
We now show the equivalence of these two definitions.
15

---

Published as a conference paper at ICLR 2025
Equivalence of {O....,k') k)" and (k 1)a. It is straightforward to verify that the two sets equivalent: an element e belongs to S, if and only if se Furthermore, S. = 0 if and only if from the set [n] is not included in any of the sets Si.....
Equivalence of Eq. (7) and Eq. 88.
The equality of the left side is clear. For the right part, the
following claim is made:
Intersection (7 in Definition A. and min in Definition A.2)
0 A.1 (X nY)); N,nY,
For Definition
For Definition
A.2 (min(s, t)); - min(s; (s; t.) when 8;, l {0, aligning with the
intersection of sets for corresponding labels. If s; and t; are different and nonzero, the result representing the empty intersection.
Union (L in Definition and max in Definition A.2
For Definition
A.1
X LLY); X, X,UY, J (X,U))) which ensures disjointness.
For Definition A.2
(max(s, t)); = max(s; t.) when s,, t, E {0, i}. aligning with If S; and t; are different and nonzero, the result is 0, ensuring
the union of sets disjointness.
Both definitions use the inequality:
f(x) f(y) f(r f(z f(x
which holds in both formulations because the operations LJ, 71 in Definition A. are equivalent to max, min in Definition A.2 and the domains and function mappings are equivalent.
A.3 Ā-SUBMODULAR CAN NOT BE REDUCED TO SUBMODULAR WITH A PARTITION MATROID
this section, we revisit the findings of Singh et al. (2012a), which demonstrate that non-negative submodular functions (i.e., k = 2) cannot be universally reduced to general non-negative submodular functions within a partition matroid framework. Below we explain the reason.
One possible reduction is as follows. We define the domain as áø S {0, 1). where A {æ (0, 13* Σド= Vy 1). and define function f - - R as I(S) f(s), where defined as S; j j there exists unique element ei, E S and s; otherwise. However, we may not be able extend the domain of such a submodular function {0, 1) mm without violating non-negativity or monotonicity, even for the simplest case of k 2. Specifically:
As shown in Lemma 2 of (Singh et al. (2012a). there exists non-negative 2-submodular function, for which no extension is both non-negative and submodular.
Furthermore, Lemma of [Singh et al. (2012a) demonstrates that there exists a monotone, non-negative 2-submodular function, for which no extension is non-negative, monotone, and submodular.
B PROOF OF LEMMA 2.5 EXISTENCE OF AN EFFICIENT ORACLE OF
We recall Lemma 2.5 states that there exists (stochastic) gradient oracle ole,r) for V with parameters 8 (0, 1) where for any query Ag. offrr provides stochastic estimate VF(x) that is HeM kn2 -close" to the gradient F in terms of f -orms, with probability at least 1 n7-
Lemma B.1 (Existence of oracle (gr))) Given E E (0, 1), let F be the k-multilinear extension 16km log
n²+1
of f. There an algorithmm that for any point x E AG. calls O for most
times
c²
and returns stochastic estimate V F(() the gradient F(() such that for all E in] and j [k].
F(x) - 0., F(x)
EM
n/k
16

---

Published as a conference paper at ICLR 2025
with probability at least 1
en x
Proof. Given oracle access k-submodular function J. the Chernoff bounds (see Theorem 1.1.16 in (Alon & Spencer 2008 implies the following theorem which allows us to approximate the value of the k-multilinear extension F to arbitrary accuracy.
Lemma B.2. Assume F is the k-multilinear extension of f. Given a point x E A.. ifs'........................ E {O....,k) k are random vectors independently sampled as follows: for each I E for each item i E [n], s = for j E [k] with probability Xi,j and otherwise, s = 0, which occurs independently across all items; then for any ED E (0, 1), we have
Σ f(s)) - F(x) 1=1
8o max f(s)
SEAR
with probability at least e 1///4
For any partial derivative F (xx at point E AE and direction Ci construct its stochastic estimate Fx) as follows. Consider points x", x² Ag defined
0
If = i
0
p- and
x
p.u
Xp.9
Otherwise.
Xp.g
p = ffp=ię1- J Otherwise.
Xp.9
We observe that the Hessian elements of F satisfy the condition d2i,1 0e..2
0. for all i [n] and ji, E [6]. This implies that 0t,, Fxx)) = 0., Fxx). Leveraging the multilinearity of F, we deduce that
8FF
F(x+) Fxx") F(x") F(x)
We consider two sets of independent samples of random vectors, s ..... S.t and s ..... L.. which satisfy the property delineated in Lemma B.2 for the points x2 and x respectively. Define
F(xF(x) = > f(s))
Σ f(s)). Then by Lemma B.2 the concentration property holds as 1
1=1
)
O1 Fxx) -Oi F(x)
Σ f(s)) F(x!)
f(s)) -F(x2)
f(s)) F(x+)
+
i Σ f(s?) F(X²)
2eal max [()]
sEAt
2
16km log 2=11
with probability at least 1 - 2e - By setting ca 22172,3 and the lemma.
we prove
As direct corollary, we know that VF VF < EM holds for any point x E Ag. which is useful for our analysis.
For the general case of k-submodular function f. computing the k-multilinear extension F poses significant challenges. This computational challenge also appears for submodular functions (k: = 1). Nevertheless, we have identified instances, such as the MAX-k-CUT problem, where the k-multilinear extension F and its gradient V F can be explicitly caleulated. This extends the multilinear extension for the MAX-CUT problem, which is shown to have an efficient gradient oracle (Chen & Kuhnle 2024 Appendix G).
Given a weighted undirected graph G = (V, E) together with a weight function w on edges, the goal of the MAX-k-CUT problem is to partition the vertices into & distinct parts, such that the
17

---

Published as a conference paper at ICLR 2025
total weight of the edges across the parts is maximized, i.e., maximizing the cut value of partition s E {O,1....,k 1}", defined as
f(s)
Σ
Wa,r 1(s + se).
(u,1)EE
By lwata et al. (2016), this function f is a k-submodular function. In this case, we can verify that its k-multilinear extension is of the form:
k-1
F(x)
Σ
(1- (1 Σ
xu,)
(1
Σ
Xo.s
Σ
XuijXull
(u,0)E
j=1
==1
j=1
and its gradient is the form:
k-1
VuzF(x) = Σ Wa (1
Σ j=1
X
Xx.).
(u,D)E
The computation time for F(x) and its gradient VF(x) is O(n²k), which is efficient. For the
multilinear extension of submodular maximization, similar argument for MAX-CUT can be found in Appendix of Chen & Kuhnle (004)).
C PROPERTIES OF k- &-MULTILINEAR EXTENSION
The following lemma presents good properties for k- k-multilinear extension, which are useful for algorithm design.
Lemma C.1 (Properties of k-multilinear extension). Let f: (O....,k)" k}" + R20 be a k- submodular function. Then its multilinear extension F: A + Rzo satisfies the following properties:
(Preservation of monotonicity) If f is monotone, F is monotone, i.e., for any point x E A F()) 2 0 for all i [n]] and j E [k].
(Pairwise monotonicity) For all i [n], E [K], OF direction Ci.j + C1,2 the k-multilinear extension is non-decreasing.
OF 2 0, i.e., along any Ux..12
0x..21
(Multilinearitty) For every E [n], j [k] and E DE with x c- the equality F(x) F(x)) holds, ie., along every coordinate direction, the corresponding directional derivative remains constant.
(Element-wise non-positive Hessian) Let M = max/maxi, F(es.)) F(O), 0} be value determined by f. For all in, l2 E M1,.i,je J2 E [Rt).
F
=
if = i2,
0x Oxizala
E (-2M,,)]
if + ig.
(Approximate linearity) For any points x, E A satisfy that x' - E 8 Ai. then
F(x') F(x) 2
(x xx.)) Oi, F(x) 128M,
(E(N]JE(K)
i.e., the difference F(x') - F(x) can be approximated by the linear (first-order Taylor) expansion at x with error (n)28)).
As generalization of the multilinear extension of submodular functions, k-multilinear extension also exhibits multilincarity and non non-positive Hessian elements. Furthermore, monotonicity is preserved by the extension.
Several novel properties emerge due to the inherent partition property of k-submodular func- tions. First, the Hessian of our extension contains zero-value elements in the same i's blocks.
"eg the (i unit hasis vector in Ra*k
18

---

Published as a conference paper at ICLR 2025
Le. F/ 0222.12 0 if 11 12. which is useful in designing rounding schemes. Our extension also exhibits an exclusive pairwise monotone property, which allows us to handle the non-monotone case. More importantly,
demonstrate novel approximate linearity property for the k-submodular case, which allows us to estimate the increment of movement with a sufficient small stepsize in the analyses of the Frank- Frank-Wolfe type methods (Bian al., 2017). This property is analo- gous to the approximate linearity described in Equation (4) of Bian et al. (201)) for DR-submodular maximization, which arises from the Lipschitz continuity of the gradient of DR-submodular functions. Although our bound on the elements of the Hessian implies a Lipschitz constant for the gradient of the k-multilinear extension, this Lipschitz constant scales with x². However, our error in the approximate linearity is independent of k. This independence stems from the fact that any difference x x' lies within A
Proof of Lemma C.7
We first remind the definition of the multilinear extension of k-submodular
functions.
Definition C.2 (k-multilinear extension). Given k-submodular function f: {0....,k}'" - Rzo. we define its multilinear extension F: A
+ R20 as
F(x)= = Σ f(s)
X
II :E|n|s,.00
(1
Σ jml
X1.))
(9)
SE SE(U,....$)" k3"
vE(n]ss,50
Preservation of monotonicity. As
OF Σ
Oxi,j
f(s)
II te)
X
II te/m|
Σ I=
X1.1)
Σ
f(s)
II
Xt.sr
II
(1
Σ
X1.
sc (0)...A)) A) =0
==
1=1
for every vector such that S; = O, which is in the second term, we can find S" such that
2 = and s 8; for any Ai,
in the first term. When ff is monotone (assume that of is increasing without loss of generality), we have f(s') 2 f(s). Thus ãx; monotone desired.
of 2 0, for all i [n] and [A:], which indicates that F is also
Pairwise monotonicity. We first remind the (discrete) k-submodular function holds the pairwise monotone property.
Theorem C.3 (Theorem 7 of Ward & Zivný 2016 ). k-submodular function holds pairwise
monotone property, for any E [n), J1. E kk. s with s; O, we have
[(s + ee,) + [(: + 2₁,) 2 2f(s)-
Taking derivative of Eq.
9
aF
OF
Σ
f(s)
II (1)
Xt.s.
II tE|n]
(1
Σ
k
Xx.1
0xiji
Oxi.ja
*E tE(....,))> #;=
1=1
Σ
f(s)
II
X1,s
II
11
Σ x
@C (0.....))
+
Σ
f(s)
II
X
II
X1.1
EE tE|n|
1=1
Σ
f(s)
II 8
Xt.
II
(1
Σ 1=1
xx,)
(0.... 4)
=D
19

---

Published as a conference paper at ICLR 2025
For every vector with s; 0, which is in the second term and the fourth term, find set tuple s' such that
i and s 5 for any +
in the first term, and a set tuple s such that
sj j2 and s s; for any + i,
in the third term. By the (discrete) pairwise monotonicity of k-submodular functions, we have f(s') - f(s) + f(s") - f(s) 20.
Thus
OF
OF
2 0.
0xi,
oxi.j2
Multilinearity.
Taking derivative of Eq. with respect to X
OF Oxi,j
Σ f(s)
II tE/n|aa=00
Xt.s.
Xt.l
k)
f(s)
II
X
II ==
(1
x4.1
#C [0. A0 1,-00
1=1
As both the terms not depend on Tiij. the derivative constant when other coordinates are fixed.
Element-wise non- non-positive Hessian.
Taking the second-order derivative of Eq.
(9) with respect to
Xiydi and Xia
F2F
Σ
((s)
II (eln])/fi.aaaaae
Xt.
II (E|n)
(1
Σ
X1.1
Oxi ixig.h
., B1 mil #1g 322
Σ
f(s)
II te|n|)(fg)=xx
X1 (+
II
(1-
Σ
x1.1
ME(D.....
1=1
2i 9ig -32
(10)
Σ
f(s)
II (6
X
II
(1
Σ
X1,1
(D....))
1=1
*i FJL $12=0
f(s)
II X
II
(1
Σ
x1,1
(0 kjm "1 "ig
[E|n]ss,50
M
in # i2, for every vector s such that Si, and 8; which is in the fourth term, can find vector such that,
$ ji and s s; for any + it,
in the third sum, and vector s² such that,
S = j2 and 5e S; for any i # i2,
in the second sum, and a vector 3 such that,
$2. j1, $h ju and sp s; for any i & {11,22)
Thus we have ming ss2) and m s2) = =. Due to k-submodularity, we have
f(s") + f(s) - f(s²) f(s²) < 0,
which implies that
8 $ 0.
Oxi,,h, 8xiz.1
20

---

Published as a conference paper at ICLR 2025
On the other hand, due to submodularity, we have
[f($)) + f(s) f(st) f(s²) s (f(s)) + f(s) s 2M,
which implies that
O -2M.
0x 0x12.12
1 = i2 = i, by the multilinearity we have
8 0.
0x,,1. 0xi.22
Approximate linearity. Since F is polynomial in x, by the Lagrangian form of Taylor's Theorem, F(x') at F(x) can be expanded as
F(x) = -x' "X
where H() the Hessian matrix, and g is a point that lies on the line segment connecting points x and x', Now we consider an element 3x.1 0X12.32 non-positive Hessian, we have
0²F(E) in HE). By the property of Element-wise
O2F
$ 2M.
Üxi, 0xi1
Therefore, if E 6Ag i.e. for all E [n].
Σ
X1, Xi,j S ō, we have
jE(M)
1
(x' x)) H(E)(x - xx
2
F²F
Σ
Kenss xin 11/22 Xiz.aa
Ox Oxig..2
à (i( (n(())
$ Σ
Σ
2M X1, Xi.iillxiaat Xig
h
M Σ
|xhn Xinsil
Xlosa Xigizl
E (n)
(EE(K)
M Σ
Σ
8²
E[ [a
n² 8 M.
Therefore,
F())
2
Σ
(X -x,))-0,,
-0,, =2882 M.
iE(m]JE[[M]
D PROOF OF LEMMA 3.2: A NOVEL ROUNDING SCHEME
In this section, we prove Lemma 3.2 by describing and analyzing a rounding algorithm called KSUBROUND (Algorithm 2
Useful notations and facts for Lemma 3.2
We first recall the round procedure of submodular
functions (Calinescu et al.) 2011 Chekuri et al. 2014 2010b). For æ < 1/2 we say Pi is small- weighted, if its weight matrix A satisfies o.jj for all i
and [m].
21

---

Published as a conference paper at ICLR 2025
Lemma D.1 (Callnnescu et al. 2011
Chekuri al. 2014 2010b)). Assume P [0. 1|"h is down- closed polytope and G : [0, I - R20 is a multilinear extension of some submodular function
then there exists algorithm, that takes vector P and the function G as input and return set E 2 obeying 1 E P and
IE [G(1s)) 2 G(y), when is single matroid constraint with rank r, with calling Op at most N times if is convex combination of N bases;
E [G(1s)] 2 (1 - =)G(y), when P is l O(1) small-weighted knapsack constraints, with calling Op at most poly (n, 1 times, for any fixed 0;
IE [G([s)] 2 (% - =) G(y), when P is intersection of b matroid constraints and = O()) small-weighted knapsack constraints, with calling Op at most poly (n. 2) times, for any fixed O;
without calling to g. We refer this algorithm as SUBROUND(y, G.P).
Our approach uses the rounding procedures SUBROUND, which are applied after reducing the multilin- ear extension of the k-submodular function to the multilinear extension submodular function with index vector I E [1.....k]".
Definition D.2 (Reduced multilinear extension). Given multilinear extension of k-summodular function, A% + R20 for any index vector {I....,k)" we define a reduced function Fr: [0, 11th + R20
Fi(x)= = Fxx'),
where x E A defined
Xx j= - 00 otherwise.
Intuitively, we define reduced function by constraining x to only take non-zero values the coordi- nates specified by an index vector I E kl....,k)". Such reduced functions enjoy the submodularity shown in Claim [D.3]
Claim D.3. F is multilinear extension of the submodular function fi 2" - Rz0 defined as
F is multilinear extension the k-submodular function f. the reduced function Fr
fi(S) - s(St,,
where St (t.....,k ky" is defined as
[I, iES, 00 S
S
Proof. We first illustrate the function-extension correspondence in the following figure.
Multilineur
F
Extension
Multilinear Ft
Extension
We also illustrate the domain correspondence in the below figure.
[O.... k)n
Extension
2
[0, 1]"
Exteusion
22

---

Published as a conference paper at ICLR 2025
In the following, we complete the proof by showing the submodularity of fi and prove the multilinear extension relationship between fi and Fi (marked as in the first figure).
We obtain the submodularity of fi by the inequality that
[r(S) + (TT) S(S") S(T") 2 ['min(S', T))) + (mmax(s) ((SU))
By the definition of the reduced function, we have
Fr(x) = F(x*)
k
Σ
[(s)
II kE(n]:5:/00
II iE(n]:s;
(1-
1
1-Exx x
-
SE R),
j=l
E SE2n
f(St)
II +E|n]:S|
II
(1
Σ x
(E(n]:
j=1
E SE2"
f(S))
II
X
II s/
x,
Σ SE2"
f((S)
X II (1-x)
iES
Thus, Fi is the multilinear extension of fT.
The correspondence between the reduced function and the submodular function can also be understood through a probabilistic view. Specifically, we consider a random vector Š E {o,.... .......kk kj". where
each entry š; f 0 is drawn independently with probability X for each [n]], and we have
Σ Σx, = x1,, = x, 5; & 0 in this process, s; is assigned with value L, We can observe that this
probability- based definition of reduced function is equivalent to the probability- definition of the multilinear extension.
Now we are ready to use the rounding scheme for submodular maximization (Lemma D.1 a rounding scheme for k-submodular maximization (Lemma D.4.
to design
Lemma D.4. Given non-monoton k-submodular function f. its multilinear extension F, a support constraint P, a fractional solution x D2 with x P, there is an algorithm KSUBROUND(x. F, P) which runs in polynomial time and outputs an integral solution s E {O....,k] k}" with s ~ P such that
E [f)] 2 F Fxx), when P is single matroid constraint with rank r, with calling Op at most 2r² times x is convex combination of N bases;
1E [f()] Z (1 - F(x) when P is l O(1) small knapsack constraints, with calling Op most poly (n. times, for any fixed 0;
E [[()s)] > (() - =) when P is intersection of b matroid constraints and I = O(1) small-weighted knapsack constraints, with calling Op at most poly (n, 2) times, for any fixed 8 > 0.
Now we are ready introduce our rounding algorithm KSUBROUND (Algorithm 2 which consists of three phases: rounding from A to [0, 1]"h (Lines 1-7), rounding from [0, 1)ah to 2n (Line 8) and recovering from 2n (k + 1)" (Lines 9-12). In each phase, we preserve the feasibility and control the loss.
Algorithm for Lemma D.4
In the first phase (Line 1-7), for any i, we merge all non-zero values and assign value j to the i-th coordinate of the index vector I with categorical probability of the proportion. This merging process does not conflict with the support constraint because the sum Σ Xi,j remains constant.
23

---

Published as a conference paper at ICLR 2025
Furthermore, at each iteration i, by the definition of multilinear extension F, the function value is exactly the linear combination of function value at every vertex of the affined corner of cube, i.e.,
Er [Pr(y)] Er [F(y))
E
Σ
((s)
II Vis,
II ==(n]:s;=0
(1-
(1
E-EShh) vias) j=1
[0
NE
<E(n]s=;00
Σ
((s)
II vE[n]ss;00
X
II ic|n/a
Ex1s) Xi.J
(0,.....))
Fx)).
In the second phase (Line 14), we apply the rounding procedure SUBROUND which takes the fractional solution y - [0, 1J"d and the reduced function Fi input and returns an integer solution S 2". The loss of this rounding procedure is bounded by Lemma D.I
In the final phase (Lines 16-18), recover the solution Ag by setting s; I, if S. This recovery step incurs no loss since the recovery procedure and reducing procedure correspond to the same index vector
Algorithm 2: KSUBROUND(x x, F,P)
Input: :A fractional solution Ag with x P, OpvE, membership oracle Op.
0]T Initialize y + +0.,.... [O, [o, 1]" and I +- [0....,0] 0] [o....,k} for i E [n] do
k
+ Σ Xz.-
y, then
With Categorical Probability p Xi. Σ Xijz j.
==1
else
I 4- 0.
S + SUBROUND(y, Fi, P). Initialize [0......0 T] {O....,k)'
10 for i E [n] do
11 if then
12 + L.
13 Return:
Proof of Lemma D.4 We first analyze the feasibility and then prove the approximation performance.
k
Feasibility In Lines 1-7, since x ~ P XE
Σ
X
Xn.
E and the
will remains constant during the moving for any i, we have P. In Line 8, by have 1 P. In Line 9-12, by the definition of support constraint, have P. Approximation ratio of Algorithm 2 Line 1-7, by the definition F and FI, we conclude that
Sum
Xig
Lemma D.I
E (y)] = F(x).
(11)
We can also conclude the linearity by the zero value of the Hessian element at the same element i's block, of F O for any Jı E [A]]
i.c., Begg. Der..a
24

---

Published as a conference paper at ICLR 2025
In Lines 9-12, by the definition of Fi, we have
F(1g) Fi(ss).
(12)
Combine Eq. equation 11 and 12 and Lemma D.I we complete the proof.
Finally, we combine Lemma D.4 and standard enumeration tricks to prove the Lemma 3.2
Proof of Lemma 3.2 For the matroid constraint, we directly employ KSUBROUND(x, F, P) on the vector x, which is the output from FW( P, e, 0). We note the reduced vector x of the output from FW(f,P: 8) is convex combination of N bases.
In the case involving O(1) knapsack constraints (and possibly other constraints)), we implement an enumeration strategy for every subset A S [ni] with |A| < no where no = - Let A = n'.A. For each
{0,....) .......... 1: and S E (0...., ... KjA, we define the concatenate vector as (SSA, Sx) such that ((8A,88), = (SA); if E A, For each (sx)) if E A.
A, explore all potential vectors in {O..... ........ A.AA. For any SA E {0,
vector S E (O..... k}A A, we define the resident k-submodular maximization problem such that the objective function fex "O......ke the objective function S* still satisfies the k-submodularity. For the constraint, the vector s' is deemed feasible iff @( s') is feasible for P, and refer its conjunction constraint PsA- For each resident k-submodular maximization problem, we perform continuous problem and yields fractional solution x(sA). Then we perform rounding scheme KSUBROUND (s)) , )sa) to obtain solution (sA) E {O..... k}1; note that if the knapsack constraint is not small- weightd, we can still perform rounding scheme KSUBROUND but with weaker guarantee or without guarantee. Finally, we output the best solution overall cases by comparing all ((B(A)
Rz0 satisfies that fax (s') f(e(s..s') By definition,
Pe,, to solve the
Now we consider a special case of 8,. Select S greedily from the optimal solution, by picking elements as long as their marginal contribution is at least eOOPT; note that |A| < + For any i E A, we add it randomly to SA if its size for some knapsack constraint is more than ga i.e. arj 2 2 for some j E [t]. The number of such elements in a knapsack can be at most e and hence they can contribute at most EOPT, and the total lost value is at most LeOPT. For this SA. we obtain a (a(1 - (1 + approxxaate solution, when P ((1) knapsack constraints and (.Go (1+ -aprrxxmat solution, when P is the intersection of b matroid constraints and ((1) knapsack constraints. By rescale we obtain the result.
E PROOF OF THEOREM 3.1. PERFORMANCE ANALYSIS OF ALGORITHM
suffices to prove the following key lemma. By the selection of in Algorithm Theorem 3.1 is
direct corollary of Lemmas 3.2 and 3.3
Lemma F.1 (Restatement of Lemma 3.3 Let arg x F(x). I is monotone,
then F(x(1)) 2 ( 2s) F(o*), with probubility at least 1
The key idea of Lemma 3.3 is to analyze the value gain of each iteration. Following the commonly
used idea to k-submodular maximization (Iwata et al. 2016: Ohsaka & Yoshida 2015 Sakaue 2017
we construct an auxiliary sequence ott) = x(t) + (1 f)o" to linear combination of o' and x(t) such that ott) is still consistent to P. Such sequence satisties that o0)) = o and o(1) x(1).
Then it suffices to show the decrease of the auxiliary sequence F()(()) F'o(t + ō)) is smaller
than the increase of the solution sequence F F(x(t 8)) F(x(t)) with additional error bounded by (5).
Proof of Lemma E.I To obtain the guarantee, we construct the following auxiliary sequences. Let
o(t) x(t) + (1 - o)o"
o( 0) x(1) 5v(( 8)o",
25

---

Published as a conference paper at ICLR 2025
and
(t( = xx() + (1 - -
By definition, is clear that o(0) = o² and o(1) = x(1). By induction on and the definition of
x(t), we obtain xx()) = t// 4 (i). Thus, xx((t) can be expressed as a linear combination of
!
v(I)...., v(t.. Since v(t) P. it follows that x(t) P. which implies that o(t). of + 6) P.
By the definition of o' (t) and of + 5), we have
of + 5) o'()) 5v(t) [0, 1)*
Combining the monotonicity of F, we have
F(o'(tt) - F(o(t + +)) S 0.
(13)
We also bound the error caused by the stochastic estimate of gradient FF(x). Lemma E.2. For any direction y E A with P and any t, with probability least 1 (VF(x(t)) < (VF(((t)), v(t) + 2sM.
61
Proof. For any
(VF(x(t)),)) =
I (VF(X(()), v(() + (VP(x(()) VF(x(O),
(by choice of v(())
= (VF(X(()) (()) + (VF(x(1)) VF(x(O), + (VF(x(()) VF((()))
S (VF(X(I)), v()) + VF(((() - VF(((O) |
+ (F((((( - VF( -VF(())
v(1122
(by
inequality)
s (VF(x(t)), (())) cM Vn
|bvll2 + eM
Vn [l((1)122
(by Lemma 2.5
& (VF(((t)), 2
Now bound the improvement in every step.
F(o(t)) ((o(t+))))
= F(o(t)) +(o - F(o(t + 6))
+
I F(o(()) - F(o((t))
(by Eq.
13
(V)(o'()), 1 (0")
(with & o'(t) co'd and e 1)) (by element- wise non-positive Hessian)
s o8)
Σ (())oo
Σ F(
(by element-wise non-positive Hessian)
(VF(((t)). (FF(x(t), 2
(by Lemma E.2 (by approximate linearity) (by choice of 6) Thus, by union bound
F(x(t +0) -x))F(((())) + 1 28
< F(x(t + - F'x((t)) + 36
By Lemma E.2 the above inequality holds with probability at least -
over =
steps, we conclude that the following inequality holds
F(o(0) F(o(1) & F(x(1)) F(x(0)) M
26

---

times and calling Op at most Published as a conference paper at ICLR 2025
with probability at least 7. Thus
F(x(1)) 1 - -
1 -2 28 F(o").
2
Now we prove Theorem by combining with Lemma 3.2
Proof. Combining Lemma 3.3 and Lemma 3.2 we can show the approximation ratio part of Theorem
Now, we analyze the query complexity and success probability of Algorithm |
Algorithm I queries
OFF total of N [ times, which implies that the query complexity with respect to f is bounded as
n1² 1 #Calls O s 2
16kn log
nn²+1) 50
kn log(
1=
E
53
Also the query complexity of Op bounded
#Calls to Op S ( 16kn 4
log
n² +1
22 1 log(
O
c²
62
To obtain - success probability, we scale the success probability of the Frank-Wolfe algorithm FW, and the total query complexity is at most scaled by logarithmic factor by Lemma 2.5
F RESULTS FOR NON-MONOTONE A-SUBMODULAR MAXIMIZATION
In this section, present algorithm (Algorithm) 3) and its analysis (Theorem for the non- monotone k-submodular objective. Recall that M = max {max,,, F(e.,) F 0f.
Theorem F.1 (Main theorem 11, non-monotone case). There exists polynomial time algorithm that given non-monotone k-submodular f 1 10,,,...,ki with probability at least 1 outputs a solution that is
and a constraint polytope A..
3 E) apprrxximatee under a single matroid constraint, with calling O, at most
0 kn log
times and calling Op at most O R"n log[ Fm for any fixed > 0;
$ e) upproximmate under the intersection of O(1) knapsack constraints, with calling O at most O (.poy(tt times and calling Op at most O (kpol((t) for any fixed 0:
(2 -)-approximmtee under the intersection of matroid constraints and O(1) knapsack constraints, with calling O, at most
o ((pols(t) . any fixed & > 0.
27

---

Published as a conference paper at ICLR 2025
Algorithm 3: Frank-Wolfe algorithm for non-monotone case, NF NFW
Input Parameters E, E (0, 1); oracles O O (E-m)) Op. N with N = [m²]
Initialize: x(0) 0, +- 0; stepsize
while / < do
Find a direction vtt) arg max VF(x(t)). v).
b By LP
Initialize: vt) 0. for i E supp (v))) do
Order partial derivative as 0z,j, F(x(1)) 2 F(x(1)) ....2 ..ji F(x(1)).
if O..j F(x(1) 2 then
V. (1) (t) + SjEl (t)
V()) = 1/2 (v(t) (V))- x(t + = = + +v()),t++
10
11
return
Similar to Algorithm T Algorithm 3 is also A Frank-Wolfe-tyyp method that computes a fraction solution x(1) P. The main difference is in the first stage, where Algorithm 3 moves along the complemented direction v(t) as an average of the locally optimal direction v(t) and vector vt(t) depending on the signal of the second largest partial derivatives (x((t)) for every i E [m]. This construction is motivated by the pairwise monotonicity of F, which enables us to reduce the non-monotone case the monotone one in the analysis. Now we prove Theorem [F.] Similar to Lemma 3.3. we first summarize the quality of the fractional solution x(1) in the following lemma.
Lemma F22 Let o = arg max XEAx,xxxx>> x~p F(x). Then F(x(1)) 2 2c) F(o"), with probability al least - 1)-
Proof. To obtain the guarantee, we construct the following auxiliary sequences. Let o(t) = x(t) - o", oft + 5) = x(t) + dv(t) + (1 - t 8) o", and (t(t) x(t) + (1 t 8) Now we consider a fixed i [m]] in Line 6. Note that the feasibility of support constraint P is only affected by
Eyen (t) j= =j, by the definition of ji Next,
Σje(K) Vig. Hence, we have vi.(!)
0
we discuss two cases based on the signal of O..ja F(((() each step. We remind the concentration
property the gradient estimators: for all é [m] and j E [ki (Lemma 2.5
Fxx 0z, F())
s.M
and
|F[x) vF(x)
S eM Vn
(14)
nvk
with probability at least 1 n²+1"
Case 1: Oz (x(()) O. By submodularity, we have F.22 I 0, F(x(t)) < 0. Com-
bining Eq. [4 we have
EM S F0 + 2:.1 2nAl
O..j (t) s o. (t) +
nvK
nvK nvk
By pairwise monotonicity (Lemma
C.I have
0 F(o((t)) + 0r F Fo'(tt) 20.
Combining Eq. 14p we have
M
Oi (() + 0. ((o(((
nyk
Thus Ur, F(o'(t)) 2 4rM
Furthermore, we have (V.F (t)), v.(t)) 4rM
Moreover, due
nybk" the fact that Vi(t)= (t),,,, we have
((()()()), v.(()) = 2(V V.(1).
Griven the equivalency of the support constraint for all vt, there should only be one unique non-zero value ji, ensuring the auxiliary linear function achieves its maximum.
28

---

Published as a conference paper at ICLR 2025
Case 2: 2 F(x(1) 2 By the definition of (1) and v'(,,, we have
Σ rEM Vi.r
j1,
(v (t,
Σ SEW Visi(t)
j2,
otherwise.
Combining the pairwise monotonicity that 0z (t)) + P2.z F(o'(t)) 0. have (V,F(o (t)), (t)) 2
By the condition that Ös.j F(x(t)) 2 0 and Eq. 14 we have
EM
Di F(x(()) nvk
which implies that
EM
(V.F(x(1)), v((I)
nvk
Combining the fact that v,(1)= = vv. (1)))) we have
(v.F(x(t)) v.)) - (V.F(x(t)) v.()) + (VFF(())) v((t)) + cM 2(V)F((()), (())))
nvK
EM
n/k
Combining these two cases and the approximate linearity, we have
M
F(o'(t)) - F(o(t + 6)) < - (() +
+ n² n
(15)
Vk.
and
(VF(x(()), v(I) s 2(VF((()), v(1) + sM Vk"
(16)
By definition o(1) = x(1) and (0) o*. We bound the improvement in every step by the following
inequalities.
F(o(()) F(o(L + +))
= F(o(()) F(o((1) + ((o(()) - F(o(L - 6))
S F(o(()) - ((o()) + 4eô
+ n
(by Eq. (5)
Vi
(1) 1 (o") H(())' 82
4gd
2
Vi
< ()) M8 + 7
(by clement-wise non-positive Hessian)
Vi.
4=M6
< (VF(x()).0")) + 8
(by element-wise non-positive Hessian)
Vi
4sM8
(VF(x(()) v(1) 2
2
(by Lemma E.2
Vk.
5
< ((VF(x()). 0()) + 28M8 +
+ 2
(by Eq. (66
Vk
5e8
(by approximate lincarity) with probability at least 1 . To sum the above inequalities over t = 0, O......, 1 and apply the union bound on the probability. we conclude that
& (F + 6)) F(x(t))) + 28 +
+ 28 2 M.
Vi
F(o(0)) ((o(1) < 2 (F(((1)) F(x())) + 5.
with probability at least 7-
29

---

Published as a conference paper at ICLR 2025
Finally, the query complexity of Algorithm 3 is identical to that of Algorithm [ We complete the proof of Theorem F.1by by combining Lemma and the following ronding lemma which similar to F.
Lemma 3.2
Lemma F.3 (Rounding scheme for non-monotone case). Let e vl E (0. 1), and P be constant.
Suppose for any monotone k-submodular function I', Algorithm NFW( , ,,, 6,1]) outputs solution
A that satisfies Fxx) maxye44 y-P F(y) Then for any 0, there exists rounding scheme that outputs solution s E EÇO,.... , k) with s ~ P, that is
a-approximate when P is single matroid constraint, i.e., f(s) (0..) f(s)), with calling NEW one time and calling Op at most O
a
times;
a(1 - ((1-=))-apronnee -approxmmaaee when P is = O(1) knapsack constraints, with calling NEW, Of, Op most O (k times:
(u (1- (1) approximate when P is the intersection of matroid constraints and = O(1)
Inapsack constraints, with calling NEW, Oj, Op most (1e0ot((/E))ppbb(()))) times.
The proof is omitted as the proof of Lemma 3.2 does not require the monotonicity of the objective function. The only difference is that we use NEW for the non-monotone case.
G HARDNESS FOR THE INTERSECTION OF O(1) KNAPSACKS AND MATROIDS
Theorem G.1 (Hardness for the intersection of matroids). There exist instances of k-submodulla maximization with suppori constraints, max (f() P), where P is intersection of matroids, any algorithm with better than O(log b/b + E) approximation ratio for this problem would require exponentially many value queries for any > 0, unless P NP.
Proof. Consider the monotone k-submodular function g {0,1, - 12z. defined as
g(s) =
where f: 2 Rg is monotone submodular function, E E R S1 fi: s; 1} E 2" and
S2 = (i: 2) 2". We set to be sufficiently small such that
min S(N) - S(N \ (+)) 2 (max S(1) 5())
This ensures that the optimal solution E {0, 1, satisfies that o, E {0.1) for all [n]. Otherwise, we can improve the function value by changing the value from 2 to without conflict with the support constraint. In other words, maximizing the k-submodular function g subject to any support constraint is equivalent to maximizing the submodular function f with the same constraint.
well-known that unless P NP, there is no approximation algorithm better than O(log b/b) for b-dimensional matching (see (Hazan et al. (0066). Hence, there is no better approximation algorithm for submodular maximization subject to the intersection of matroids constraint (Lee ct al. 2010b). Therefore, the hardness result of Olog b/b) also holds for constrained k-submodular maximization.
30


Reviews:
[{"review_id": "P01Y3jFZb8", "reviewer": "Reviewer_Tvbp", "summary": "This paper studies monotone and non-monotone k-submodular maximization subject to various constraint systems. Prior work on this topic has studied combinatorial algorithms only -- this paper introduces a multilinear extension for k-submodular functions. Despite the power of the continuous approach for 1-submodular functions, it hasn't been applied to the k-submodular case. Via this method, the authors obtain improved approximation ratios in several constraint regimes, most notably O(1) knapsacks, where they achieve an asymptotically tight ratio.", "questions": "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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- In some sense, developing continuous algorithms for the k-submodular case seems like a natural generalization of the 1-submodular methods. However, there were a number of challenges the authors had to adress, which is likely why prior work had avoided this direction. Everything looks easy in hindsight.\n- Specifically, the way the authors addressed a certain feasibility issue (discussed on page 4) by shifting the optimization target from o^* is relatively novel. It is a little surprising to me, not that this method obtains a constant factor, but that it gets the optimal ratio in some settings (O(1) knapsacks). Other generalizations (such as rounding, approximate linearity, etc.) seem more straightforward.\n- For non-monotone functions, the ratios aren't tight, but significant improvements in state-of-the-art are obtained.", "weaknesses": "- Notation departs substantially from most of the other k-submodular papers I've seen. It took a bit of thought to see that everything is equivalent. Likely this could have been introduced in a more intuitive way that would make the paper more accessible.\n- The main text is really an extended abstract, with no proofs. And instead, arguments why the methods are interesting. In general, I would like to see at least some part of the technical arguments condensed in the main text -- but this is more a critique of the publication / reviewing model. Often, mistakes are found later (obviously didn't have time to check the 30-page appendix in full detail).\n- Algorithms are of theoretical interest only, of order n^{poly(1/\\epsi}. It is difficult to imagine a scenario where one would want to try to implement these algorithms. Thus, their ability to tackle big data k-submodular instances of problems relevant to the ML community is limited to non-existent.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "KsCJDtt5u1", "reviewer": "Reviewer_pvDA", "summary": "This paper addresses the k-submodular maximization problem under matroid and knapsack constraints. k-submodular maximization is a generalization of submodular maximization where each element of an n-dimensional vector can take values from {0, ..., k}. The objective is to maximize a submodular function defined on these vectors, subject to given constraints.\n\nThe authors apply the multilinear extension technique—previously used in submodular maximization but novel to k-submodular maximization—achieving an improved approximation factor for this problem, particularly under the d-knapsack constraint. They have improvements for other constraints too, but most improvements are minor except for this specific constraint.", "questions": "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?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The main strength lies in applying the multilinear extension to k-submodular maximization, which could inspire similar approaches in related problems. Additionally, the improvement in the approximation factor under the d-knapsack constraint is noteworthy.", "weaknesses": "Although the algorithm provides a good approximation factor, its practical applicability is limited due to potentially high running times, and no experimental results are provided to assess real-world performance. Additionally, while the first paragraph of introduction mentions applications, it’s unclear how relevant this problem is for the ML community, as it’s not as widely studied as submodular maximization, which may hold more appeal for ML research.\n\n## Minor comments:\n- On page 5, you mention that Niu et al. achieved a 1/3-approximation ratio for the non-monotone case under a single matroid constraint, but a worse result appears on page 2, Table 1.\n- On page 2, the notation for min_0 and max_0 is inconsistent—sometimes with 0 as a subscript, other times appearing below them. Please standardize.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Ms6hual895", "reviewer": "Reviewer_t6jy", "summary": "This paper considers the problem of maximization of $k$-submodular functions, where elements in the ground set can be selected into one of $k$ sets. $k$-submodular functions are a generalization of ordinary submodular set functions, which correspond to the special case $k=1$. For the maximization of ordinary submodular set functions, the continuous multilinear extension has been used in order to yield algorithms with better approximation guarantees compared to combinatorial approaches such as greedy algorithms. In contrast, only combinatorial approaches have previously been proposed for $k$-submodular function maximization. Inspired by the effectiveness of continuous approaches in the ordinary submodular function case, this paper extends the definition of multilinear extension to $k$-submodular functions, and proposes algorithms using this multilinear extension to achieve better approximation guarantees that those existing for a variety of constraints (see Table 1). Their algorithms use Frank-Wolfe types of methods, which is different than continuous algorithms used for ordinary submodular functions.", "questions": "* Is the definition of $k$-submodular presented in the paper the typical definition? And if it is not, is it clearly equivalent? I recall seeing different definitions of $k$-submodular in related work.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- $k$-submodular functions have been a topic of recent interest, and this paper makes an important contribution by introducing an extended multilinear extension and proposing algorithms which have better approximation guarantees using the multilinear extension.\n- They developed algorithms with theoretical performance guarantees stronger than those existing in the literature. Further, at least some of their guarantees matched the best known lower bound of Iwata et al. (2016). \n- They used Frank-Wolfe type of methods instead of simply extending the most standard algorithms using the multilinear extension for standard submodular functions such as that of Calinescu et al. [2011] (see reference below). They further explain the technical challenges that arise when simply trying to extend those standard approaches. They also had to use an alternative method of rounding. So their theoretical results do not seem trivial to me.\n- Paper is very well-written and clear.\n\nCalinescu, Gruia, et al. \"Maximizing a monotone submodular function subject to a matroid constraint.\" SIAM Journal on Computing 40.6 (2011): 1740-1766.", "weaknesses": "- There is no experimental evaluation of the algorithms, and in fact the algorithms might not be very practical to implement. Multilinear extension algorithms are often much slower and less practical compared to combinatorial ones for ordinary submodular functions, so one would probably expect that to also be the case in this setting.\n- This paper extends and combines ideas from many papers in the literature. For example, the ordinary submodular function multilinear extension is extended to the $k$-submodular case, and in addition Frank-Wolfe style algorithms have been used for ordinary submodular functions. One con then might be that there is not a huge amount of novelty, but I think it is still plenty sufficient for publication.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WiOxFlvz7B", "reviewer": "Reviewer_HNQi", "summary": "This paper addresses the problem of maximizing $k$-submodular functions under various constraints. By generalizing the multi-linear extension commonly used for standard submodular functions to apply to $k$-submodular functions, the authors introduce unified Frank-Wolfe-type frameworks to tackle these problems in a continuous domain. The proposed algorithm attains an approximation ratio of $1/2$ for monotone $k$-submodular optimization and $1/3$ for nonmonotone $k$-submodular optimization.", "questions": "The paper is clearly written. My main question concerns the proof of Lemma 3.3. I understand that the best-known lower bound for the monotone case is $1/2$, but could you please 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? Additionally, I noticed that the query complexity of the algorithm, even for the monotone case, is somewhat inefficient. Would using a different concentration inequality, such as Hoeffding's inequality instead of the Chernoff bound, potentially improve the query complexity?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "1. The problem of k-submodular maximization is important in many fields of machine learning and aligns well with the conference’s broader focus.\n2. The paper provides solid and clear proof analysis and proposes a unified algorithm that achieves better approximation ratios compared with the previous method.\n3. The proof sketch of Lemma 3.3 is presented clearly and highlights the technical novelty of the proof.", "weaknesses": "1. As has been highlighted in [1], 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. \n2. Since this is a theoretical work with no experimental results, the primary contributions should ideally lie in offering new technical skills or insights to the submodular optimization community. However, most of the proof analysis appears standard. \n\n-[1]. Satoru Iwata, Shin-ichi Tanigawa, and Yuichi Yoshida. Improved approximation algorithms for\nk-submodular function maximization.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)