Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
Authors: Qixin Zhang
Wei Huang
Can Jin
Puning Zhao
Yao Shu
Li Shen
Dacheng Tao
Venue: ICML 2025 poster (2025)
Keywords: Subset Selection
Weakly Submodular Maximization
Partition Matroid
Continuous Relaxation
Lossless Rounding
Primary area: optimization->discrete_and_combinatorial_optimization

Abstract: Identifying the most representative subset for a close-to-submodular objective while satisfying the predefined partition constraint is a fundamental task with numerous applications in machine learning.  However, the existing  distorted local-search methods are often hindered by their prohibitive query complexities and the rigid requirement for prior knowledge of difficult-to-obtain structural parameters. To overcome these limitations, we introduce a novel algorithm titled **Multinoulli-SCG**, which not only is parameter-free, but also can achieve the same approximation guarantees as the distorted local-search methods 
with significantly fewer function evaluations. The core of our **Multinoulli-SCG** algorithm is an innovative continuous-relaxation framework named Multinoulli Extension(***ME***), which can effectively convert the discrete subset selection problem subject to partition constraints into a solvable continuous maximization focused on learning the optimal multinoulli priors across the considered partition. In sharp contrast with the well-established multi-linear extension for submodular subset selection, a notable advantage of our proposed ***ME*** is its intrinsic capacity to provide a lossless rounding scheme for any set function. Finally, we validate the practical efficacy of our proposed algorithms by applying them to video summarization, bayesian A-optimal design and coverage maximization.

Multinoulli Extension:
A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
Qixin Zhang' Wei Huang? Can Jin
Puming Zhao
Yao Shu
Li Shen' Dacheng Tao
Abstract
1. Introduction
Subset selection aims to identify small group of repre- sentative items from a vast ground set, which finds numer- ous real-world applications in the fields of machine learn- ing, operations research and statistics, including feature selection (Das & Kempe, 2008; 2011; Qian et al., 2015; 2017), data summarizarion (Lin & Bilmes, 2010; 2011; Wei et al., 2015; Mirzasoleiman et al., 2016), product market- ing (Kempe et al., 2003; Tang et al., 2018; Han et al., 2021) sensor placement (Krause al., 2008; Hashemi et al.. 2019; De al., 2023) and in-context learning (Kumari et al., 2024a;b; Fan et al., 2025). Beyond the aforementioned rep- resentational capacity, ensuring the diversity and fairness of the chosen subset is of significant importance. For instance, in various marketing scenarios, it is essential to equitably allocate free products across different communities (Tsang et al., 2019). To this end, partition constraints are often imposed in the process of subset selection, which involves dividing the entire set into non-overlapping sub-classes and then fairly distributing the total budget among them. Mo- tivated by these findings, this paper explores the subset selection problem under partition constraints.
Identifying the most representative subset for a tosssoo--uub objective while satisfying the predefined partition constraint is fundamen- tal task with numerous applications in machine learning. However, the existing distorted local- search methods are often hindered by their pro- hibitive query complexities and the rigid require- ment for prior knowledge of structural parameters. To overcome these lim- itations, we introduce novel algorithm titled Multinoulli-SCG, which not only is parameter- free, but also can achieve the same approximation guarantees as the distorted local-search methods with significantly fewer function evaluations. The core of our Multinoulli-SCC algorithm is an in- framework named
novative contnuuus--reaxatte Multinoulli Extension(ME),, which can effectively convert the discrete subset selection problem sub- ject to partition constraints into solvable continu- ous maximization focused on learning the optimal multinoulli priors across the considered partition. In sharp contrast with the well-established multi- linear extension for submodular subset selection, a notable advantage of our proposed ME is its intrinsic capacity provide lossless rounding scheme for any set function. Finally, we vali- date the practical efficacy of our proposed algo- rithms by applying them to video summarization. A-optimal design and coverage maximization.
Broadly speaking, the subset selection problem is NP- hard (Natarajan, 1995; Feige, 1998), implying that no polynomial-time algorithms can solve optimally. In light of this hurdle, many studies have focused on designing efficient approximation algorithms to address the subset selection problem. Especially when the utility function as- sociated with the subset selection problem is submodular, plethora of effective and practical algorithms have been proposed for maximizing this type of functions subject to partition constraints (Fisher et al., 1978; Calinescu al., 2011; Filmus & Ward, 2012b; 2014). Additionally, it has been frequently observed that there are also many scenarios inducing utility functions that are "close-to- so-uoooodll""" but not strictly submodular. Examples include variable se- lection for regression (Das & Kempe, 2018; Elenberg et al., 2018), video summarization (Chen et al., 2018a), neural network pruning (El Halabi et al., 2022) and sparse optimal transport (Manupriya et al., 2024).
Nanyang Technological University, Singapore" RIKEN Cen- ter for Advanced Intelligence Project(AIP) Rutgers University Shenzhen Campus of Sun Yat-sen University Hong Kong Uni- versity of Science and Technology (Guangzhou). Email to: Qixin Zhang <qixin zhang ntu.edu.sg> Correspondence Li Shen <mathshenlic @ gomi
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
Compared to the extensive literature on submodular func- tions, there is limited amount of research exploring the

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
maximization of ""dose-to-submmdulaar" objectives under partition constraints. Notably, Thiery & Ward (2022) re- cently proposed distorted local-search algorithm to maxi- mize an important class of cilos--to-sumoddutee functions named (7: -Weekly submodular functions and demon-
Table I. Comparison of theoretical guarantees for a-weakly DR- submodular maximization over partition constraints. Note that Parr-frree' indicates whether the method does not rely on prior knowledge of o, 'OPT" represents the optimal value of the subset selection problem (1), 'Distorted-LLS' is the abbreviation for the distorted local-search method, 'Distorted-LS- the distorted bocal-search method with LSu-Gussingg denotes the rank of partition constraint, e.g.. r Σ B, in problem (1), and rt is the size of the ground set, namely, n = | in problem (1).
strated that this approach can secure 2011- )
#(1-))+7²
guesses, r is
approximation under partition constraints, where y and & represent the lower and upper submocularity ratio respec- tively. Subsequently, Lu et al. (2022) extended this local search to another class of "close-to felose-to-submene "o-sumoouular" functions known as o-weakly DR- DR-submodular functions and also con- firmed a (1 -e - ) >approximation guarantee under partition constraints, where a is the Siminishing-returnnD ratio.
Method Standard Greedy
Para-free? Querles
Utility
O(wrr
(1
(Khashayar& & Manuel, 2019)
Distoried-LS (Lu et ul., 2022)
x
M(rr2")
9JOPT
Despite the superior theoretical guarantees of distorted local- search methods, their practical implementation often faces two significant challenges: i) Reliance on Unknown Pa- rameters: Distorted local search generally requires prior knowledge of specific structural parameters regarding the objective functions, such as the submodularity ratio and taniniishing-rttun())))) ratio. However, in practice, accu- rately estimating these parameters can incur exponential computations. ii) Prohibitive Query Complexity: Due to the absence of necessary structural parameters, Lu et al. (2022) and Thiery & Ward (2022) have to adopt a brute- force O(lfe)-round guesses of these unknown parameters to approximate the distorted local-search methods, which will result in an extremely high ((1/c)) and ((1/))) num- ber of value queries to the objective function, respectively. Thus, a natural question arises:
Distorted-LS-GGeesee
(Lu et ul., 2022)
Ó (=ce)) >
(1 cm c)PPT
Multinouli--SCC (Theorem 4&Remark 8)
o p
(1 - e ")PPT-
that the objective set function is submodular.
Our Contributions. i): This paper introduces a novel prob- abilistic framework for the subset selection problem under partition constraints, which we refer to as the Multinoulli Extension(ME). Furthermore, we conduct an in-depth explo- ration of the differentiability, smoothness and monotonicity regarding the ME. More importantly, we establish an up- per bound for the gap between the function value of our proposed ME and that of the original set function. ii): We propose novel algorithm named Multinoulli-SCG. which effectively integrates the concept of continuous greedy, the path- anth-integrated differential estimator and the relationship between our proposed ME and its original set function. More- over, we prove that, when the objective function is mono- tone a- ae-eeklly DR-suboodular or (7, -weeakl submod- ular, our Multinoulli-SCC algorithm can attain value of
Is it possible to develop a parameter- and query- efficient algorithm for the "close-to-submad" submodular" subset selection problems under partition constraints while keeping strong approximation guarantees?
(1 - JOPT or (2² (P( -112))
#(1-))+ JOPT with only 0(1/²) function evaluations, where OPT denotes the optimal value. These results not only significantly improve the previous 5(1 and ((1/c²) number of function eval- uations associated with the distorted local-search methods, but also match the iiformation-thhoretii (11/e) lower bound (Karbasi et al., 2019; Hassani et al., 2020). iii): We demonstrate the practical efficacy of our proposed algo- rithms by applying them to video summarization, bayesian A-optimal design and maximum coverage.
In this paper, we will provide an affirmative answer to this question by presenting an effective algorithm titled Multinoulli-SGG, which not only reduces the strict require- ment for the exact knowledge of both submodularity ra- tio and DR ratio, but also can attain the same approxima- tion guarantees as the aforementioned distorted local-search methods with only O(1/²) function evaluations. The cor- nerstone of our Multinoulli-SGG algorithm is an innovative continuous-relaxation framework termed as the Multinoulli Extension(ME). which aims to learn a multinoulli distribu- tion for each community within the partition constraints and subsequently leverage these distributions to make selection. In sharp contrast with the well-established multi-linear ex- tension (Calinescu et al., 201 a notable advantage of our proposed ME is its inherent capability to provide a lossless rounding scheme for any set function. Instead, all known lossless rounding schemes for -intir extension require
Due to space limits, we primarily focus on the most relevant studies, with a more comprehensive discussion provided in Appendix A. Chen et al. (2018a) was the first to investigate weakly submodular maximization beyond simple cardinality constraints, which pointed out that the Residual Random Greedy method of (Buchbinder 7²
Related Work.
et al., 2014) can achieve an approximation ratio of (1.55 for the problem of maximizing a monotone y-weakly sub-
2

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
0, Vi E [m]] Especially, the symbol 'Multi(p)' denotes a multinoulli distribution with (m + 1) possible states where P E Am- Note that the multinoulli distribution is also known as the categorical distribution (Murphy, 2012).
Table Comparison of theoretical guarantees for (7, -)-weklly submodular maximization over partition constraints. Note that o(7, (3- = 01- ( and Para-freee' means whether B(1 3(1-7)++>²
the method does not rely on prior knowledge of y and B
Partition of A Set: Given a finite ground set V, we say (Vi.... Vx} } is a partition of set V if and only i) V; n
Method
Para-free?
Queries
Utility
Residual Random Greedy
O(nr)
(1+pp) OPP
V = 0 for any i + j E [K]] ii) V = UK Vk.
(Chen et al., 2018a)
Standard Greedy
O(nr)
v9 OPPT
0.4y²
Subset Selection under Partition Constraints: Let f 2 + R2 be a set function that maps any subset of V to a
(Khashuyar & Manuel, 2019)
Residual Random Greedy
(Thiery & Ward. 2022)
((rr)
(177))PT
non-negative utility. Given a partition (Vi...., Vx} of V and collection of budgets (B, ........ Bx) where 0 < B₁ S V&l Vk E [K], the goal of the subset selection problems subject to partition constraints is aimed at finding a subset S from V such that the utility set function f is maximized within the constraints |S n Vil S BN for any k E [K], i.e.
Distorted-T.S
x
2(nr2")
(C,,)OPT
(Thiery & Ward, 2022)
Distorted-LS- S-Guuessig
(6(7.3) -(POPT
(Thiery & Ward, 2022)
Multinouli-SCGG
o <(1, ()OPT=
(Theorem R&Remark 8)
max f(S) S.t. |S VAl S B& Ak E [K]. SCV
(1)
modular functions subject a matroid constraint. Note that matroid constraint is a natural generalization of the partition constraints considered in this paper. Subsequently, Khashayar& & Manuel (2019) examined the approximation performance of standard greedy algorithm on both 7-weakly submodular and a-weakly DR-submodular maximization over a matroid constraint. Next, in order to improve the ap- proximation performance of the Residual Random Greedy method, Thiery & Ward (2022) introduced the notion of upper submodularity ratio 3 and developed more powerful distorted -earch algorithm for (7, B) -weakly submod- ular maximization. Concurrently, Lu et al. (2022) also pro- posed a similar local-search method to maximize a- a-weakkly -ussubmod functions. A detailed comparison of our proposed Multinoulli-SCG algorithm with existing studies is presented in Table and Table 2.
We say that set function f:2 R4 is monotone if and only if f(A) S (BB for any A C B S V.
Monotonicity:
Weak Submodularity: Given a set function f - R. and any two subsets A, B C V. we denote by f(BlA) the marginal contribution of adding the elements of B to A, i.e., f f(B44) := f(A B) fA). For simplicity, when B is a singleton set (v), we also use (v) represent / [(v)]/4) Therefore, we say that set function f ; :2 - R_ is 7- weakly submodular from below for some 7 E (0, 1] if and only if, for any two subsets A S B CV.
Σ f(ulA) 2 (1(B)-
(2)
BEBIA
where we denote y as the lower submodularity ratio. Simi- larly, we also can define the weak submodularity from above,
Remark on Table 2: Thiery & Ward (2022) has demon- strated that when 7 < $. the approximation guarantee of Residual Random Greedy method (Chen et al., 201 8a), namely مرحي will surpass the ratio o(7, B). To overcome this drawback, Thiery & Ward (2022) initializes their dis- torted local-search method by the returned subset of the Residual Random Greedy method. Similarly, when 7 < $. we also can produce better subset by comparing the re- tumedd subset of our proposed Multinoulli-CGG algorithm with that of the Residual Random Greedy method.
that is, a set function f 2² + TR,, is B-weakly submodular from above for some 3 Z iff, B
Σ VEBIA
(o)) s (F(D)-
(3)
where /3 is called as the upper submodularity ratio. When set function f satisfies both Eq.(2) and E3) we say it is (y, B...kly submodular (Thiery & Ward, 2022).
Weak DR-submodularity: A set function f 2 - R4 is a-weakly DR-submodular for some a E (0, 1] iff [(v) Z a (v for any two subsets A S B S V and E VB B. In particular, a is often called as the diminishingg-retu((RR))) ratio (Kuhnle al., 2018). Note that, from Eq.(2) and (3),,), we can infer that an a-weakly DR-subnodular func- tion automatically satisfies the conditions for being (a, 4)- weakly submodular. Moreover, when a = 1, weakly DR- submodular objectives will reduce to the standard submodu- lar functions (Nemhauser et al., 1978; Fujishige, 2005)
2. Preliminaries
In this section we present several important notations and concepts that we will frequently use throughout this paper.
For any positive integer K, [K] stands for the set {1...., K}. The symbol (, denotes the inner prod- uct. Moreover, Am represents the standard m-dimensional
Notations:
simplex, i.e., the set ((1,...,, xm)) Em Fz S and v; 2
3

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
selected within its own community V2 for any m E [mg]] and k [K] Subsequently, ME, employs each prior distribution 'Multi(pa)' to conduct B3 independent random selections for every community Vg. which can ultimately yield a subset that adheres to the partition constraint of problem (1). In Figure I, we present a three-community example of ME. is noteworthy that, with the probability - _m=11 PV the multinoulli prior 'Multi(ps)' won't pick any member from Vy- In other words, sometimes we might end up with no selection, i.e., 0. Formally, we can define the ME as: Definition 1 (Multinoulli Extension). Given a set function [ 22 + R.,, its Multinoulli Extension F I Ang + R. for problem (1) can be defined as:
A A.
Selection
Mattinull Extension
Pri
Pri
A A
X
X
R. A
R.R.R.
Figure 1. Diagram of Multinoulli Extension.
3. Multinoulli Extension
F(p PK) = Muuuutttppe)) (F(UÆ
Bh K b=1
(
Generally speaking, the discrete nature of subset selection problem (1) poses significant challenge in finding effective solutions. In recent years, compared to discrete optimiza- tion, continuous optimization developed an array of efficient and advanced algorithmic tools. Thus, an alternative strat- egy to address the subset selection problem (1) is to bring it into the world of continuous optimization via relaxation- rounding frameworks, which typically involve three critical stages: first, converting the problem (1) into solvable con- tinuous optimization; second, applying the gradient-basee methods to output high-qualij continuous solution; and third, rounding the previous continuous solution back to the partition constraint of (1) without any loss in terms of the function value. In the subsequent part of this section, we will present a novel aalaxatttoo-oounding framework named the Multinoulli (X)) for problem (1).
K Be
Σ (S(UR) U k= 0=1 (c))
IIII
Pr( (P));
where each of denotes the element chosen at the b-th random trail of community Vi vb E [Bg]. vk E [K]. P& = (nt..... .p.....PPP .P. "() E Ang is the probability vector for the community V/+ Vk- E [K], Pr(uTIPPp = Vm E
[ng]. vk E [K] and Pr(O)p;) = 1 E% PT vk E [X]. Remark 1. The introduction of ME is aimed at converting the general subset selection problem (1) into continuous maximization task focused on identifying the optimal multi-
noulli priors across the partition (Vi,..., Vx J. Specifically, we hope to address the following continuous optimization:
Prior to this, Calinescu et al. (2011) proposed continuous relaxation technique known as the multi-linear extension for submodular subset selection problems. Unfortunately, this extension cannot be directly applied to the general subset se- lection problem (I) because most known lossless rounding schemes for multi-linear extension, such as pipage round- ing (Ageev & Sviridenko, 2004), swap rounding (Chekuri et al., 2010) and contention resolution (Chekuri et al., 2014), are heavily dependent on the submodular assumption. Up to now, how to losslessly round the lunti--inearreee extension of non non-submodular set functions, e.g. (7, -wekkl submod- ular and a- e-weakly DR- submodula functions, still remains an open question (Thiery & Ward, 2022). Given the un- solved rounding challenge of multi- linear extension, this paper choose to introduce a new relaxation technique named Multinoulli Extension(ME) to address the problem (1).
max F'P Pk) s.t. PE 20
Te Pk LL [K].
(4)
m==1
Remark 2. In comparison with the multi-linear exten- sion (Calinescu et al., 2011), a notable advantage of our ME is that it does not assign probabilities to any subsets that are out of the partition constraint of problem (I). This means that, for any set function f 2 - E4 and any given (Pi,..., PK) E TT Ang. we can, through the definition of ME, easily produce subset that conforms to the partition constraint of problem (1) without any loss in terms of the expected function value F F(PI... p.). For more details about multi-linear extension, please refer to Appendix A.
A Although the ME is naturally endowed with a lossless round- ing scheme for any set function, there are two crucial ques- tions that must be answered in order leverage this tool to tackle the subset selection problem (1) : i): What is the relationship between the function value of our proposed Multinoulli Extension F and the original set function f? ii): How to solve the relaxed problem (4)? For the rest of this section, we will focus on the first question. The exploration of the second question will be presented in Section 4.
To provide a clearer exposition of our proposed ME, we first make some assumptions regarding the problem (1): we define V/=- := .e.,..., 744 for any i: E [K] and set | = n, i.c., n = 2 nig. More specifically, the core idea of our ME is to learn a prior multinoulli distribution 'Multi(pa) for each community Vk. where P := (pk...., .P." mhx E Ane and each ptch denotes the probability that element of is
4

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
3.1. The Properties of Multinoulli Extension
Next, we uncover the relationship between the function value of our proposed ME. F and that of the original f. To be more precise, we have the following theorem:
In this subsection, we will concentrate on characterizing several important properties about our proposed ME. Specif- ically, we have the following theorem:
Theorem 2 (Proof provided in Appendix C.2). When the set function S 2 - R is monotone and a-weakly DR-submodular, for any subset S within the partition con- straint of problem (1) and any point x == (Di....,PK' E I Any the following inequality holds:
Theorem (Proof provided in Appendix C.1). For set function f 2 + IR+,, its Multinoulli Extension F: [ Anz - IR+ for problem (1), as described in the Definition I, satisfies the following properties:
1): The first-onler partial derivative of F at any point (PI....,Pk) E =II Any can be written as follows:
a (((S))F(x)) S Σ 1 Isni vF(x))
BB
OF 0pk
= BB B BeggMMatiipe) (1 (ardam (o (of)))
where the symbol 1s is the indicator function over the set S, meaning that, for any element va E S, the corresponding coordinate of its probability PK in 1s is set to 1: other- wise, O. Similarly, when the set function f 22 - RR+ is monotone and (7,, () -weekly submodular, for any subset S within the partition constraint of problem (1) and any point x == (PI..... PK) E II Ang. we can infer that
for any l E [K] and m E [ms]]
2): !f f is monotone, then BF
2 0, Ak E [K], E [mn]; Ty
3): If f is a-weakly DR- DR-submodular, then F is a-weakly con- tinuous DR-submodular (Hassani et al., 2017; Zhang el al., 2022; 2024) over the domain IIk=1 Any. that is, for any two point (pI,...,P.) pK) E =I Any and (pi,..., px) E Any Pf 2 for any ls E [K], we have that
K
(355)
S
1sny, B&
VF(X))
Remark 5. Theorem 2 implies that when f monotone and a-weakly DR-submodular, for any S within the partition constraint of problem (1) and any point x E II Any. the discrepancy between f(S) and F(x) can be bounded by the inner product <ΣK- 1 1snv, VF(x)). Similarly, B,
V PK) 2 aVF(D...... PK);
4) If f is "--eaklly submodular from below, then F is coper-linearizable (Pedramfar & Aggarwal, 2024) over the domain I Any. that is, for any two point x := (PI..... .P...... .P)) E II Ane and & == (pI...., .p)) E I Ann is pb= 2 P& for any k E [K], we have that (F(x)
if f is monotone and (7, - submodular, this inner product (EK- BE sny, VF(x)) also can bound the gap between TSS(S) and (3(1-1 7) + Fx))(
(x-x, x, VF(x).
4. Approximation Algorithms for Subset Selection over Partition Constraints
Remark 3. The first point of Theorem 1 provides a specific form about the first-order derivative of our proposed ME. The second point indicates that the mononicity of the set function can be inheritable by its ME. Furthermore, the third and fourth points reveal that when the set function f exhibits the weak DR -ubboouuuyy or weak submodularity, its corresponding ME is weakly continuous DR-submodular or
In this section, we delve into the development of efficient ap- proximation algorithms for the subset selection problem (1) based on our introduced Multinoulli Extension F.
4.1. Stochastic Variant of Continuous Greedy Algorithm
over the domain II Any.
This subsection aims to present an effective method named Multinouli--SGG to maximize our introduced ME, which is primarily inspired by the continuous greedy(CG) algorithm for the multi-linear extension (Calinescu et al., 201 1; Bian et al., 30; 2020; Mokhtari al., 2018a; 2020).
Remark 4. Note that both upper- linee--lncarizable and weakly continuous Dussuonodular functions defined over the box constraint [o, 1]" have been extensively studied by (Hassani et al., 2017; 2020; Zhang et al., 2024; Wan et al., 2023: Pedramfar& & Aggarwal, 2024). However, is crucial em- phasize that these former results cannot be directly applied to our ME. This is because all of them require the domain of objective functions to be closed under the coordinate-we maximum operation V, i.e., x V y = max(x, (x, y). Unfortu- nately, the domain of our ME does not meet this requirement. For further details, please refer to Appendix A.3.
The CG algorithm typically comprises two critical steps: First, it begins with x(1) O and then, at each iteration E [7], the algorithm identifies the optimal ascent direction v(t) = arg max (v. (x((t))) to update the current variable x(t) according to the rule x(t + 1) = x(t) + fv(t) where is the multi-linea extension of set function
5

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Algorithm Stochastic Continuous Greedy Algorithm for Multinoulli Aitension(MulltioolliSSS
as: Diff, = So (s)(x (((s) x(s) - x(s -1)) where x*)) ax(s) + (1 a)x(s-)xxxxxp_ 1), Va E [o, and V² is the Hessian of F. Hence, if we uniformly sample the pa- rameter a from [0, 1], the difference Diff, can be unbiasedly
Input: Batch size L, number of iterations T, set function f
and partition (V1,.... .y...... Vx} of set V
1: Initialize: x(1) = (P1 (1)....... (((]).......(( = 0:
estimated by e, == Fxx (s)) x(s) x(s (0--)))). 1)) where
2: for / ===1,- 1,...., T do
3: it't then Difffrrnnial Estimator(Lines 3-12)
Vº F is an unbiased estimator of V F. Following this idea, we proceed to demonstrate how to estimate the second-order derivative of our proposed ME, that is to say,
4: Compute g11) : (0) based on Theorem I;
5: else
6: Sample (a(1))...., (T.) uniformly from [0, 1];
Theorem 3 (Proof provided in Appendix C.3). For a set function f 2 - R+, the second-order derivative of its Multinoulli Extension F at any point (PI...., PK)
7:
(t) = ((xx((+(==a()x((((-))))))==)))))
vT E [4];
8:
Compute the Hessian estimator (x)(t)) based
on Remark 6 for any E [Z];
K Ang can be written as follows:
Compute 7 = 1 E (x)())):
9:
I): If + h2 for any mi E [mxn]] and m2 [mazl
10:
Compute & =- (x(() - x(1 1));
11:
Aggregate the estimator g(1) = g((- - Es:
FFF BAr Bag E ((( SU m3
s));
12:
end if >> Stochastic Continuous Greedy(Lines 13-14)
OPk 8pk
S(I) = arg max snvulss. (g((): Ex= S. Invv. ):
13:
where S = == (kbb)) (kk, 02.022113 {e,} and each of is drawn from the multinoulli distribution Multi(pa):
14:
Update x(t + 1) = x(t) + T Eken B. sscomi
L
15:
end for
2): As k = l/2 = k E [K], if B₂ = for any mi, 12 E
16: Return S by rounding x(T + 1);
[ng], we have m1 m2
0² F
O; Moreover, when BB 2 2,
Dp.
0pp
OFF
(B2 Ba) E ( COT (SU())
5
(s)
and C is a convex domain. The motivation behind the CG algorithm is that when f is submodular, the inequality (y, VG(x)) 2 G(y) G(x) holds for any feasible y. Note that, in Theorem 2, we establish a similar relationship between our proposed ME F and its original set function f. that is the inner product (ΣK=1 Br 1snv. VF(x)) can bound a specific form of weighted discrepancy between ((S) and F(x), when f is monotone a-weakly DR-submodular or -weakly submodular. Motivated by these findings, we naturally consider a two-step variant of CG algorithm to maximize our proposed ME: Initially, we set x(1) = O, and then, at each iteration & E [T], we find the optimal subset S(1) := (VF(x(t),, ΣK_ 1 ((sma))
0y Th 0p
where S = ( lek) and each ef is indepen- dently drawn from the multinoulli distribution Mulri(p;).
Remark 6. Theorem provides a detailed characterization of the second-order derivative of our proposed ME F, which implies that we can estimate the Hessian of F by sampling sequence of random elements. Specifically, when each is independently drawn from the multinoulli distribution k "Mult(p;)) for any ie E [K] and b [Bg], we can estimate 82F my (P Px) as: when ki + h2 [K],
0Pe1 OP
F2F
BR, Bxg (f(1ZT) (U - 5 ( ((( (s))
arg max snals to update the current variable x(t) according to the rule x(t + := x(t) + + Σ B (s())))))
The
Opk. 0pm ma
where S = ((b.)) fah): As for hn = 12 =
e [K] and B₁ 2 2,
However, the implementation of the aforementioned two- step algorithm requires accurately computing the gradi- ents of our proposed ME. F, which is typically computa- tionally intensive. To circumvent this obstacle, we adopt the stochastic path-integrated differential estimator (Fang et al., 2018; Yurtsever et al., 2019; Hassani et al., 2020), namely, for a sequence of iterations (x(t))+++ we es- timate each gradient VF(x(t)) by the following path- integral form: Fx(((t) == (x(())) + > E.. where each E, is an unbiased estimator for the difference Diff, := Fx(x())) - V - 1)). Note that, for any 2 S s S T, the difference Diff, can be rewritten
F2F
= (B%- -B) (f(
Su(uro)) (vr))s)s)
dy my 80
where S S= (2.,)) (cf))
Incorporating this second-order approximation and the idea of differential estimator into the previously mentioned two- step algorithm, we can develop stochastic algorithm for maximizing our ME, as detailed in Algorithm 1.
Furthermore, based on the results of Theorem I and Theo- rem 2, we can show that
6

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
Theorem 4 (Proof provided in Appendix D.1). When the set function f : 2 4 is monotone and o--weakly DR- submodular, if we set the batch size L = O(T), the subset S output by Algorithm 1 satisfies:
& Lan, 2013; Lacoste-Julien, 2016; Allen-Zhu, 2018; Drori & Shamir, 2020; Lan, 2020). Regrettably, we observe that, compared to the previously proposed Multinouli-SCG al- gorithm, the stationary points of our ME only can guarantee a sub-optimal approximation to the maximum value of the subset selection problem (1). Before going into the details, we firstly revisit the definition of stationary points, that is,
B(f(s)) 2 (1-6-9) (TVYT)
TV")
where S is the optimal solution of problem (1), is the rank of partition constraint, i.e., r = > Bs and n = | Similarly, if the set function f 2 - R4 is (r, 3)-eadl monotone submodular and I. = (T), the subset S output by Algorithm I satisfies:
Definition Given a differentiable objective function G K + R and a domain C S K, point x E C is called as a stationary point for the function G over the domain C if and only if maxyec x, VG(x)) S O.
Next, we will detail the specific performance of the sta- tionary points of the Multinoulli Extension relative to the maximum value of problem (1). Specifically, we have that Theorem 5 (Proof provided in Appendix E.1). If the set function f : 2 + R is monotone and a-weakly DR- submodular, then any stationary point (P) (PI..... .......PPK... PK)) of its Multinoulli Extension F over the domain I Ang the following inequality holds:
B(J(S)) 2 (2 (F(1-6-00--)Ht)))
(Vv T
3(1 3(1-2) 722
Remark 7. Theorem 4 implies that, when the set function f is a-weakly monotone DR-submodular, we set T = (11cc,, the subset yielded by our proposed Algorithm 2 can secure value of (1 "PPT e, where OPT is the maximum value of problem (1). Moreover, when is (7; 3)- weakly monotone submodular, Algorithm 2 also can achieve
i ) )(5),
a²
(2 (2'0---<00---) OPP after O(1/e) iterations. Note 8(1-5)+7'
F(PI, TIP..---PAA PKP
that, during the process of (1/cc) iterations, Algorithm 2 only requires evaluating the set function ((1/e²) times.
where S* is the optimal solution of problem (1). Similarly, when the set function f: f + R4 is monotone and (7, B)- weakly submodular, for any stationary point (Pi..... Pk)
Remark 8. From Line 13, we know that each S(t) has at most non-zero entries, where r = E Bg. Hence, in Line 10, the computation of &, only utilizes O (nr) entries in the Hessian estimation ? This implies that it is sufficient to estimate up to (nr) second-order partial derivatives for each point (t) at Line 8.
over the domain I Ang. we also can show that
72
F(PI...... ........ppp>> 2 B + 3(1 7) +)+ 1(5))
Remark 10. Theorem 5 suggests that when the set func- tion f is monotone a-weakly DR-submodular (7, B)- weakly submodular, the direct application of gradient-based methods that aim for stationary points, such as gradient ascent, into the relaxed problem (4) only can ensure a I+t=/ )-approximation or (3+80-~)+=" )-approximation to the maximum value of the subset selection problem (1).
Remark Note that, in Line 16, when rounding x(T + 1) based on the definition of ME, there a risk that two distinct random selections may yield the same element. To avoid this issue for monotone set functions, present an effective roundingwwitoouttrellaaee without--eplaaemeen method in Appendix D.2.
a²
Compared to the local-search methods (Thiery & Ward, 2022; Lu et al., 2022), our Algorithm I not only climinates the need for prior knowledge of parameters a, Y, and 3, but can achieve the same worst-case approximation guarantees with fewer (LL/²² value queries to the set function f.
Despite these limited theoretical approximation guarantees regarding the stationary points of our proposed ME, we have found that gradient-based methods targeting stationary points, such as the stochastic gradient ascent, can achieve remarkable empirical performance across numerous real- world subset selection problems (See Section 5). Due to space limitations, an in in-depth analysis of the stochastic gra- dient ascent method presented in Appendix E.2.
4.2. Stationary Point and Stochastic Gradient Ascent
Furthermore, an alternative solution for the subset selection problem (1) is to initially apply the off off-tffesseef gradient- based methods, like gradient ascent (Nesterov, 2013; Bert- sekas, 2015), to maximize our proposed ME F, and subse- quently, to finalize our selection by rounding the resulting continuous solution. As is well known, under mild con- ditions, a broad range of first-order gradient algorithms, including the aforementioned gradient ascent, will converge to the stationary points of their target objectives (Ghadimi
5. Numerical Experiments
In this section, we empirically compare the performance of our proposed Multinouli--SGG and Multinouli-SGA against the standard greedy method (Khashayar & Manuel, 2019) and the residual random greedy method (Chen et al.,
7

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Table 3. Results on video summarization. Note that 'obj' denotes the utility function value, where higher value is preferable, and "queries" represents the magnitude of the total number of function evaluations, that is the logio of the total number of value queries to the set objective function, with smaller value being more favorable. Distorted-LS-G is the abbreviation for the distorted local-searce method with ((1/e) guesses, namely, Algorithm B. in (Thiery & Ward, 2022). Both V1 and V2 are sourced from websites, which are related with Cooking and Animation, respectively. V3-V7 are derived from the VSUMM dataset and encompass topics such as Soccer, Live news, Broadcast, Concert as well as TV Show. The time following the name of each video indicates the video duration. In each column of 'obj' , indicates ranking the 1st and stands for the 2nd.
Video
V1(3min33ss
V2(7min415s)
V3(2min37s)
V4(2min17ss)
V5(2min58s)
V6<4min42s)
V7(2min52s)
Method
ohj
queries
obj
queries
obj
queries
ohj
queries
ohj
queries
ahj
queries
obj
queries
Standard Greedy
46.48
3.85
79.25
3.95
47.64
3.61
19.55
3.48
52.39
3.73
96.33
4.11
44.85
3.73
Residual Greedy
48.45
3.85
75.58
3.95
48.65
3.61
18.84
3.48
52.02
3.73
92.37
4.11
44.94
3.73
DSstorted-LS-G
50.08
10.40
79.25
10.50
551.71
10.17
19:56
10.02
54.36
10.26
98.73
10.70
46.79
10.27
Multinoulli-SCC
50.17
6.53
79.57
6.58
51.77
6.41
19.59
6.35
54.44
6.46
98.81
6.66
47.06
6.46
MultinoulI-SCG 350.17
8.59
179.50
8.68
51.77
8.34
19.59
8.21
54.44
8.46
98.80
8.84
47.200
8.46
2018a) as well as the distorted local search (Thiery & Ward, 2022) across three distinct applications: video summariza- tion, bayesian A-optimal design and maximum coverage. Note that Multinoulii-SGA represents the stochastic gra- dient ascent applied to our proposed ME, as detailed in Ap- pendix E.2. Due to the space limits, here we only show the results on video summarization. More discussions about the experiment setup and the results on both maximum coverage and bayesian optimal design are presented in Appendix B.
quently, we choose to create a summary of each video by extracting one representative frame from every 25 frames, that is, we consider the following partition constraint:
|s n [25(i- - 1) + 1, 25:] < 1 V S i S [n/25].
1)
Table 3 illlustrates the performance of our proposed Multinoull--SCG and Multinouli-SGA algorithms against three benchmark methods, namely, 'Standard Greedy', 'Residull-Greedy" and 'Distorted-LS-G". It is quite easy to observe that our Multinouli-SCG and Multinoulli-SGA algorithms produce summaries with higher diversity than the other three baselines. Specifically, Multinoulli-SCG achieves Top-1 performance on out of the 7 videos, while Multinoulli-SGA attains Top-1 performance on 6 out of the videos. Furthermore, the number of function evaluations required by our Multinouli-SCGG and Multinoulli-SG. is 2 and 4 orders of magnitude lower than that of the state- of-the-art 'Distorted-LS-Gi respectively. This result aligns well with our previous theoretical findings in Section 4.
5.1. Video Summarization
The objective of video summarization is aimed at picking a few representative frames from a given video such that these frames can capture as much content as possible. To achieve this, common strategy is to formulate the frame selection problem as the maximization of a Determinantal Point Process(DPP) objective function (Gong et al., 2014; Mirzasoleiman et al., 2018; Chen et al., 2018 DPP has recently emerged as a powerful tool that favors subsets of a ground set of items with higher diversity (Kulesza et al., 2012). More specifically, for an n-frame video, we represent each frame by a p-dimensional vector. Then, we compute the Gramian matrix X of the resulting vectors by setting each Xij as the Gaussian kernel between the i-th and j-th vectors. With this matrix X, the DPP objective function can be defined as f(S)= = det(T 7 + Xs) where $ C [n). X is the principal submatrix of X indexed by S and is a [S|- dimensional identity matrix. Note that Bian et al. (2017a)
6. Conclusion
This paper introduces a novel continuous-relaxxtion frame- work named Multinoulli Extension(ME) for the subset se- lection problem under partition constraint. In contrast to the well-known multi-linear extension for submodular subset selection, a notable advantage of our ME is that it can provide a lossless round scheme for any set objective function. Subsequently, base on ME, we develop an efficient algorithm titled Multinoulli-SGG, which can achieve a
has proven that this set functionn f is monotone and weakly submodular from below. Moreover, Nguyen & Thai (2022)
also verified the weak DR subbuoundylartty of S.
value of (1- ( (? (900--(0(0-)--)))) OPPT- -c
#(1-)++>2
For our experiments, we use five videos from the VSUMM dataset (De Avila et al., 2011) and two videos about 'An- imation' and 'Cooking' from websites like Yubeub. Ad- ditionally, we utilize the method described in (Gong et al., 2014) to prune each video, namely, for long videos(> 5min), uniformly sampled one frame per second, and for short videos, we sampled one frame every half second. Subse-
with only 0(1/²) function evaluations for monotone a- weakly subuoouua or (y,3))-eakk)) submodular ob- jective functions. This result significantly improves the pre- vious ((L/E5) and O(L/e²) number of function evaluations associated with the distorted local-search methods. Finally, extensive empirical evaluations have been conducted to val- idate the effectiveness of our proposed algorithms.
8

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Impact Statement
Buchbinder, N. and Feldman, M. Constrained submodular maximization via a nonsymmetric technique. Mathemat- ics of Operations Research, 44(3):98--0055 2019.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Buchbinder, N. and Feldman, M. Constrained submodular maximization via new bounds for dr-submodular func- tions. In Proceedings of the 56th Annual ACM Symposium Theory of Computing, pp. 1820-1831, 2024.
Acknowledgment
Buchbinder, N., Feldman, M., Naor, J., and Sehwartz, Submodular maximization with cardinality constraints. In Proceedings of the twenty-ffth annual ACM-SIAM sym- posium on Discrete algorithms, pp. 1433-1452. SIAM, 2014.
This project is supported by the National Research Foun- dation, Singapore, under its NRF Professorship Award No. NRF-P2024-001.
References
Calineseu, G., Chekuri, C., Pal, M., and Vondrák, Max- imizing a monotone submodular function subject matroid constraint. SIAM Journal Computing, 40(6): 1740-1766, 2011.
Ageev, A. and Sviridenko, M. Pipage rounding: A new method of constructing algorithms with proven perfor- mance guarantee. Journal of Combinatorial Optimization, 8:307-328, 2004.
Chekuri, C., Vondrak, J., and Zenklusen, R. Dependent randomized rounding via exchange properties of combi- natorial structures. In 2010 IEEE 51st Annual Symposium Foundations of Computer Science, pp. 575-584, 2010. doi: 10.1109/FOCS.200 2010.60.
Allen-Zhie Zhu, Z. How to make the gradients small stochasti- cally: Even faster convex and nonconvex sgd. Advances in Neural Information Processing Systems, 31, 2018.
Bach, F. et al. Learning with submodular functions: A con- vex optimization perspective. Foundations and Trends@ in machine learning, 6(2-3):145-373, 2013.
Chekuri. C., Vondrák, J., and Zenklusen, R. Submodular function maximization via the multilinear relaxation and contention resolution schemes. SIAM Journal on Com- puting, (3((6)18311110 2014.
Bertsekas, D. Convex optimization algorithms. Athena Scientific, 2015.
Bian, A. A., Buhmann, J. M., Krause, A., and Tschi- atschek, S. Guarantees for greedy maximization of non- submodular functions with applications. In International conference on machine learning, pp. 498-507. PMLR, 2017a.
Chen, L.,, Feldman, M., and Karbasi. A. Weakly submod- ular maximization beyond cardinality constraints: Does randomization help greedy? In International Conference on Machine Learning, pp. 804-813. PMLR, 201 8a.
Chen, L.,, Hassani, H., and Karbasi, Online continuous submodular maximization. In International Conference Artificial Intelligence and Statistics, pp. 1896-1905. PMLR, 2018b.
Bian, A. A., Mirzasoleiman, B., Buhmann, J., and Krause, A. Guaranteed non-convex optimization: Submodular maximization over continuous domains. In Artificial Intelligence and Statistics, pp. 111-120. PMLR, 2017b.
Chen, L.,, Zhang, M., Hassani, H., and Karbasi, A. Black box submodular maximization: Discrete and continuous settings. In International Conference on Artificial Intelli- gence and Statistics, pp. 1058-1070. PMLR, 2020.
Bian, Y., Buhmann, J. M., and Krause, A. Continuous submodular function maximization, 2020. URL https:
/ //arxxa //arxivvors wtwp/ivoorrr/.oo abs/ /ta./20000 2006. 13474.
Bogunovic, I., Zhao, J., and Cevher, V. Robust maximiza- tion of non-submodular objectives. International Con- ference on Artificial Intelligence and Statistics, pp. 890- 899. PMLR, 2018
Das, A. and Kempe, Algorithms for subset selection in linear regression. In Proceedings of the fortieth annual ACM symposium Theory of computing, pp. 45-54, 2008.
Borsos, 7.,, Mutny, M., and Krause, A. Coresets via bilevel optimization for continual learning and streaming. Ad- vances in neural information processing systems, 33: 14879-14890, 2020.
Das, A. and Kempe, D. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In International Conference on Machine Learning, pp. 1057-1064, 2011.
Borsos, Z., Mutný, M., Tagliasacchi, M., and Krause, A.
Data summarization via bilevel optimization. Journal of Machine Learning Research, 25(73): 2024.
Das, A. and Kempe, D. Approximate submodularity and its applications: Subset selection, sparse approximation

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
and dictionary selection. Journal of Machine Learning Research, 19(3):1-34, 2018.
Fisher, M. L., Nemhauser, G. L., and Wolsey, L. A. An analysis of approximations for maximizing submodular set functions-ii. In Polyhedral Combinatorics, pp. 73- 87. Springer, 1978.
De Avila, S. E. F., Lopes, A. P. B., da Luz. Jr, A., and de Al- buquerque Araūjo, A. Vsumm: A mechanism designed to produce static video summaries and a novel evaluation method. Pattern recognition letters, 32(1):56-66) 68, 2011.
Fujishige, S. Submodular functions and optimization. Else- vier, 2005.
DeValve, L., Pekec, S., and Wei, Y. Approximate submodu- larity in network design problems. Operations Research, 71(4):00111139, July 2023. ISSN 0030-364X.
Gao, H., Xu, H., and Vucetic, S. Sample efficient decen- tralized stochastic Trank-wolff methods for continuous dr-submodular maximization. In Proceedings of the Thir- tieth International Joint Conference on Artificial Intelli- gence, IJCAI-21, pp. 3501-3507, 2021.
Drori, Y. and Shamir, O. The complexity of finding station- ary points with stochastic gradient descent. In Interna- tional Conference on Machine Learning, pp. 2658-2667. PMLR, 2020.
Ghadimi, S. and Lan, G. Stochastic first-and zeroth-order methods for nonconvex stochastic programming. SIAM journal on optimization, 23(4):23311235) 2013.
El Halabi, M., Srinivas, S., and Lacoste-Julien, S. Data- efficient structured pruning via submodular optimization. Advances in Neural Information Processing Systems, 35: 36613-36626, 2022.
Gong, B., Chao, W.-L., Grauman, K., and Sha, F. Diverse se- quential subset selection for supervised video summariza- tion. Advances in neural information processing systems, 27, 2014.
Elenberg, R., Khanna, R., Dimakis, A. G., and Negahban, S. Restricted strong convexity implies weak submodular- ity. The Annals of Statistics, 46(6B):3539 3368, 2018.
Gong, S., Nong, Q. Liu, W., and Fang. Q. Paramet- ric monotone function maximization with matroid con- straints. Journal of Globul Optimization, 75(3):833-849,
Fan, z., Du, S., Hu, S., Wang, P., Shen, L., Ya, Z., Tao,
D., and Wang. Y. Combatting dimensional collapse in IIm pre-training data via diversified file selection. In The Thirteenth International Conference on Learning Representations, 2025.
November 2019. ISSN 0925-5001.
Gong, S., Nong, Q. Sun, T., Fang, Q., Du, D., and Shao, X. Maximize a monotone function with generic submod- ularity ratio. Theoretical Computer Science, 853:16-24, 2021.
Fang, C., Li, C. J., Lin, Z., and Zhang, T. Spider: Near- optimal non-convex optimization via stochastic path- integrated differential estimator. Advances neural in- formation processing systems, 31, 2018.
Grant, M. and Boyd, S. Cvx: Matlab software for disci- plined convex programming, version 2.1, 2014.
Feige, U. A threshold of In n for approximating set cover. Journal of the ACM, 45(4))6346652 1998.
Han, K., Wu, B., Tang, J., Cui, S., Aslay, C., and Lak- shmanan, L. V. Efficient and effective algorithms for revenue maximization in social advertising. In Proceed- ings of the 2021 international conference on management of data, pp. 671-684, 2021.
Feldman, M., Naor, J., and Schwartz, R. A unified continu- ous greedy algorithm for submodular maximization. In 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science, pp. 570-579, IEEE, 2011.
Harrison Jr. D. and Rubinfeld, D. Hedonic housing prices and the demand for clean air. Journal of environmental economics and management, 5(1):81-102, 1978.
Filmus, Y. and Ward, The power of local search: Max- imum coverage over matroid. In 29th Symposium on Theoretical Aspects of Computer Science, volume 14, pp- 601-612. LIPIcs, 2012a.
Harshaw, C., Feldman, M., Ward, J., and Karbasi, A. Sub- modular maximization beyond non-negativity: Guar- antees, fast algorithms, and applications. In Interna- tional Conference on Machine Learning, pp. 2634-2643. PMLR, 2019.
Filmus, Y. and Ward, J. tight combinatorial algorithm for submodular maximization subject matroid constraint. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pp. 659. IEEE, 2012b.
Hashemi, A., Ghasemi, M., Vikalo, H., and Topcu, U. Sub- modular observation selection and information gathering for quadratic models. In International Conference on Machine Learning, pp. 2653-2662, PMIR, 2019.
Filmus, and Ward, J. Monotone submodular maximiza- tion over a matroid via non-oblivious local search. SIAM Journal on Computing, 43(2):514-542) 2014.
10

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Hassani, H., Soltanolkotabi, M., and Karbasi, A. Gradient methods for submodular maximization. In Advances in Neural Information Processing Systems, pp. 5841-5851, 2017.
Kumari, L.,, Wang, S., Zhou, T., Sarda, N., Rowe, A., and Bilmes, J. Bumblehee: Dynamic KV-cache streaming submodular summarization for infinite-context transform- ers. In First Conference on Language Modeling, 2024b.
Hassani, H., Karbasi, A., Mokhtari, A., and Shen, Z. Stochastic conditional gradient++::non) convex min- imization and continuous submodular maximization.
Lacoste-Julien, S. Convergence rate of frank-wolfe for non-convex objectíves. arXiv preprint arXiv: 2016.
SIAM Journal on Optimization, 30(4):3315-3344 2020.
Lan, G. First-order and stochastic optimization methods for machine learning, volume 1. Springer, 2020.
Jin, C., Che. T., Peng, H., Li, Y., Metaxas, D., and Pavone, M. Learning from teaching regularization: Generalizable correlations should be easy to imitate. Advances in Neural Information Processing Systems, 37:966-994 2024.
Lin, H. and Bilmes, J. Multi-document summarization via budgeted maximization of submodular functions. In Human Language Technologies: The 2010 Annual Con- ference of the North American Chapter of the Association for Computational Linguistics, pp. 912-920, 2010.
Jin, C., Peng, H., Zhang, Q., Tang, Y., Metaxas, D. N., and Che, T. Two heads are better than one: Test-time scaling of multi-agent collaborative reasoning. arXiv preprint arXiv:2504.09772. 2025.
Lin, H. and Bilmes, J. A class of submodular functions for document summarization. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies, pp. 510- 520, 2011.
Karbasi, A., Hassani, H., Mokhtari, A., and Shen, Z. Stochastic continuous greedy ++: When upper and lower bounds match. In Wallach, H., Larochelle, H., Beygelz- imer, A., d' d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, vol- ume 32, Curran Associates, Inc., 2019.
Lu, C., Yang, W., Yang, R., and Gao, S. Maximizing a non- decreasing non-submodular function subject to various types of constraints. Journal of Global Optimization, 83 (4):727-751, August 2022. ISSN 0925-5001.
Kempe, D., Kleinberg, J., and Tardos, É. Maximizing the spread of influence through a social network. In Proceed- ings of the ninth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 137-146, 2003.
Manupriya, P., Jawanpuria, P., Gurumoorthy, K. S., Jagar- lapudi, S., and Mishra, B. Submodular framework for structured-sparse optimal transport. In Forty-first Inter- national Conference on Machine Learning, 2024.
Khashayar, G. and Manuel, G. R. Non-submodular function maximization subject to a matroid constraint, with ap- plications, 2019. URL https: httppss///axvv../// org/ abs/ 1811.0788
Mirzasoleiman, B., Karbasi, A., Sarkar, R., and Krause, A. Distributed submodular maximization. The Journal of Machine Learning Research, 17(1):8330 8373, 2016.
Mirzasoleiman, B., Jegelka, S., and Krause, A. Streaming non-monotone submodular maximization: Personalized video summarization on the fly. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Krause, A., Singh, A., and Guestrin, C. Near-optimal sen- sor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Journal of Machine Learning Research, 9(2), 2008.
Kuhnle, A., Smith, J. D., Crawford, V. and Thai, M. Fast maximization of submuubmo, monotonic functions on the integer lattice. In International Conference Machine Learning, pp. 2786-2795. PMLR, 2018
Mokhtari, A., Hassani, H., and Karbasi, A. Conditional gradient method for stochastic submodular maximization: Closing the gap. In International Conference on Artificial Intelligence and Statistics, pp.
PMLR, 201 Sa.
Kulesza, A., Taskar, B., et al. Determinantal point pro- cesses for machine learning. Foundations and Trends@ in Machine Learning, 5(2-3)):23-205) 2012.
Mokhtari, A., Hassani, H., and Karbasi, A. Decentralized submodular maximization: Bridging discrete and contin- uous settings. In International conference on machine learning, pp. 3616-36265 3625. PMLR, 2018b.
Kumari, L., Wang, S., Das, A., Zhou, T., and Bilmes, J. An end-to-end submodular framework for data-efficient in-context learning. In Findings of the Association for Computational Linguistics: NAACL 2024, pp. 32.3293-333 3293-3308, 2024a.
Mokhtari, A., Hassani, H., and Karbasi, A. Stochastic con- ditional gradient methods: From convex minimization to submodular maximization. Journal of Machine Learning Research, 2020.

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Murphy, K. P. Machine Learning: A Probubilistic Perspec- five. The MIT Press, 2012. ISBN 026201 8020.
with bounded curvature. Mathematics of Operations Re-
search, 42(4):1197-1218, 2017.
Natarajan, B. K. Sparse approximate solutions to linear systems. SIAM journal on computing, 24(2):227-234, 1995.
Tang, J., Tang, X., Xiao, X., and Yuan, Online processing algorithms for influence maximization. In Proceedings of the 2018 international conference on management of data, pp. 991-1005, 2018.
Nemhauser, G. L., Wolsey, L. A., and Fisher, M. L. An analysis of approximations for maximizing submodular set functions i, Mathematical Programming, 14(1):265- 294, 1978.
Thiery, T. and Ward, J. Two-sided weak submodularity for matroid constrained optimization and regression. In Loh, P.-L. and Raginsky, M. (eds.), Proceedings of Thirty Fifth Conference Learning Theory, volume 178, pp. 3605-3634. PMLR, 02-05 Jul 2022.
Nesterov, Y. Introductory Lectures on Convex Optimization: A Basic Course, volume 87. Springer Science & Business Media, 2013.
Tsang, A., Wilder, B., Rice, E.,, Tambe, M., and Zick, Y. Group-fairness in influence maximization. In Proceed- ings of the Twenty-Eightt International Joint Conference on Artificial Intelligence, IJCAI-19, pp. 5997-6005. In- ternational Joint Conferences on Artificial Intelligence Organization, 2019.
Nguyen, L. N. and Thai, M. T. Efficient algorithms for monotone non non-submodulla maximization with partition matroid constraint. In Raedt, L.. D. (ed.), Proceedings of the Thirty-Firss International Joint Conference on Artifi- cial Intelligence, IJCAI-22, pp. 4807-4813. International Joint Conferences on Artificial Intelligence Organization, 7 2022. Main Track.
Vondrák, J. Submodularity and curvature: The optimal algorithm (combinatorial optimization and discrete algo- rithms). RIMS Kokyuroku Bessatsu B, 23:253-266, 23: 253-266, 2010.
Pardalos, P. M. and Kovoor, N. An algorithm for a singly constrained class of quadratic programs subject to upper and lower bounds. Mathematical Programming. 46:321- 328, 1990.
Wan, Z., Zhang, J., Chen, W., Sun, X., and Zhang, Z. Ban- dit multi-linear dr-submodular maximization and its ap- plications on adversarial submodular bandits. In Inter- national Conference on Machine Learning, pp. 35491- 35524. PMLR, 2023.
Pedramfar, M. and Aggarwal, V. From linear to linearizable optimization: A novel framework with applications to stationary and -tatioationayy DR-submodular optimiza- tion. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
Wei, K., Iyer, R., and Bilmes, Submodularity data subset selection and active learning. In International conference on machine learning, pp. 1954-1963. PMLR, 2015.
Pedramfar, M., Quinn, C., and Aggarwal, V. A unified approach for maximizing continuous dr-submodular func- tions. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 61103- 61114, 2023.
Xie, J., Zhang, C.,, Shen, Z., Mi, C., and Qian, H. Decen- tralized gradient tracking for continuous dr-submodular maximization. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 2897-2906. PMLR, 2019.
Pedramfar. M., Nadew, Y. Y., Quinn, C. J., and Aggarwal, V. Unified projection-free algorithms for adversarial dr- submodular optimization. In The Twelfth International Conference on Learning Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024, 2024.
Yu, Y., Wang, Y., Xia, S., Yang, W., Lu, S., Tan, Y.-.., and Kot, A. Purify unlearnable examples via rate-constrained variational autoencoders. In International Conference on Machine Learning, pp. 57678-57702. PMLR, 2024a.
Qian, C., Yu, Y., and Zhou, Z. Subset selection by pareto optimization. Advances in neural information processing systems, 28, 2015.
Yu, Y., Wang, Y., Yang, W., Guo, L., Lu, S., Duan, L.- Y., Tan, Y.-P., and Kot, A. C. Robust and transferable backdoor attacks against deep image compression with selective frequency prior. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2024b.
Qian, C. Shi, J.-C., Yu, Y., Tang, K., and Zhou, Z.-H. Subset selection under noise. Advances in neural information processing systems, 30, 2017.
Yurtsever, A., Sra, S., and Cevher, V. Conditional gradient methods via stochastic path-integrated differential estima- tor. In International Conference on Machine Learning, pp. 7282-7291. PMLR, 2019.
Sviridenko, M., Vondrák, J., and Ward, J. Optimal approx- imation for submodular and supermodular optimization
12

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Zhang, M., Chen, L.,, Hassani, H., and Karbasi, A. On- line continuous submodular maximization: From full- information to bandit feedback. In Advances in Neural Information Processing Systems, Pp. 1006-921,, 2019.
Zhang, Q. Deng, Z., Chen, Z., Hu, H., and Yang. Y. Stochas- tic continuous submodular maximization: Boosting via non-oblivious function. In International Conference Machine Learning, Pp. 261 16 2-266-24444--1 PMLR, 2022.
Zhang. Q.. Deng, Z., Chen, Z., Zhou, K., Hu, H., and Yang. Y. Online learning for non-monotone dr-submodular max- imization: From full information bandit feedback. In International Conference Artificial Intelligence and Statistics, pp. 3515-3537. PMLR, 2023a.
Zhang, Q.. Deng, Z., Jian, X., Chen, Z.,, Hu, H., and Yang. Y. Communication -effriiionneffinnnnneeee decentralized online continu- ous dr-submodular maximization. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, pp. 5330-3339. 2023b.
Zhang, Q. Wan, Z., Deng, Z., Chen, Z., Sun, X., Zhang, J., and Yang. Y. Boosting gradient ascent for con- tinuous dr-submodular maximization. arXiv preprint arXiv:2401.08330 2024.
Zhang, Q.. Wan, Z.. Yang, Y., Shen, L.,, and Tao, D. Near- optimal online learning for multi-agent submodular ordination: Tight approximation and communication ef- ficiency. In The Thirteenth International Conference on Learning Representations, 2025.
Zhao, P. and Lai, L. Minimax optimal q learning with nearest neighbors. IEEE Transactions on Information Theory, 2024.
Zhao, P., Fan, R., Wang, S., Shen, L., Zhang, Q., Ke, 7.,, and Zheng, T. Contextual bandits for unbounded context distributions. In International Conference on Machine Learning, 2025.
Zhou, X., Pi, R., Zhang, W., Lin, Y., Chen, Z., and Zhang, T. Probabilistic bilevel coreset selection. In International Conference on Machine Learning, pp. 27287-27302. PMLR, 2022.
Zhu, J., Wu, Q.. Zhang, M., Zheng, R., and Li, K. Projection- free decentralized online learning for submodular maxi- mization over time-varying networks. Journal of Machine Learning Research, 22(51):1-422 2021.
13

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
A. Additional Related Work
A.I. Submodular Maximization
Submodularity (Fujishige, 2005; Bach et al., 2013) is a fundamental concept, which widely exists in various disciplines, including combinatorial optimization, economics, and machine learning. To be more precise, a set function f 22 + R+ called submodular if and only if it satisfies the diminishing-retum property, namely, for any two subsets A C B V and
E V B, f(A U (b)) S(A) 2 f(BU) {x}) S(B). In other words, the marginal benefit of adding an element set diminishes the set becomes larger.
Generally speaking, the maximization of submodular functions is NP-hard, implying that no polynomial-ting algorithms can solve optimally. To overcome this challenge, Nemhauser et al. (1978) proposed a greedy algorithm for solving the monotone submodular maximization problem under a cardinality constraint and demonstrated that this greedy algorithm can achieve an approximation ratio of (1 (1-e-1) Furthermore, Feige (1998) showed that this (1 - "a)'-apprxiimattion guarantee tight for monotone submodular maximization under reasonable complexity-thene thhorreti assumptions. After that, Fisher et al. (1978) extended the greedy algorithm to the general matroid constraint and proved that the greedy algorithm only can guarantee sub-optimal approximation ratio of 1/2 under matroid constraint. To achieve the tight (1 appproxiiiii under matroid constraint, Calinescu et al. (2011) 1) introduced a continuous greedy algorithm for submodular functions. The core of this continuous greedy algorithm a novel aantinuous-relxatiin technique known as the multi-linear extension. The problem of maximizing submodular functions also has been studied for the non-monotone case (Feldman et al., 2011; Chekuri et al., 2014; Buchbinder & Feldman, 2019; 2024).
Before delving into the details of other related studies, we introduce the multi-linear extension of (Calinescu et al., 201 1) for submodular maximization and simultaneously compare it with proposed Multinoulli Extension(ME) in Section 3. In order to better illustrate the multi-linear extension, this subsection supposes |V] = and set V = [n] (I,....n) nn.
Definition 3. For a set function f + RR,, we define its multi-linear extension as
G(x) = Σ II Fa ACV
(1-1=a)) x.)) = =ER~x =IR)))
(5)
aEA
agA
where x = (x1, (x1,,..,, F.) E [0. 11"h and R C V is a random set that contains each element a E V independently with probability Ha and excludes it with probability 1 - Ta. We write R ~ x to denote that R S V is a random set sampled according to x.
From the (5), we can view multi-linear extension G at any point x E [0, 1jm as the expected utility of independently selecting each action a E V with probability ra. With this tool, we can cast the previous discrete subset selection problem (1) into a continuous maximization which learns the independent probability for each element a E V. that is, we consider the following continuous optimization:
max G(x), s.t. Σ na S Bz, Vk E [K]
(6)
xE|o,1|"
oEVi
where G(x) is the multi-linear extension of
It important to note that, if we round any point included into the constraint of problem (6) by the definition of multi-linear extension, i.c., E5,( there is certain probability that the resulting subset will violate the partition constraint of the subset selection problem (1). Therefore, for multi-linear extension, we need to specifically design the rounding methods based on the properties of the set objective functions. However, current known lossless rounding schemes for multi-linear extension, such as pipage rounding (Ageev & Sviridenko, 2004), swap rounding (Chekuri et al., 2010) and contention resolution (Chekuri al., 2014), are heavily dependent on the submodular assumption. Moreover, how to losslessly round the multi-linear extension of sun-uuuaad set functions, e.g. (7, -weakly submodular and a-weakly DR-submodular functions, still remains an open question (Thiery & Ward, 2022).
In contrast, our ME does not assign probabilities to any subsets that are out of the partition constraint of problem (1), which means that, for any set function f: 2 + R, and any given (p)...., Px) E I Anc, we can, through the definition of ME, casily produce a subset that conforms to the partition constraint of problem (1) without any loss in terms of the expected function value F(p1....,PPi
14

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
A.2. Closetto-Submodular Function Maximization
Weakly Submodular Maximization: A particularly important class of "close-to-submoddlaa" functions is known as y-weakly submodular functions. Specifically, for set function f : 2 ,,, it is called y-wekkly submodular if and only if, for any two subsets A S B _ V. the following inequality holds: Σ LEEBrA f(v A) 2 (f((B) f(A)). The 7-weakly submodular functions were originally introduced by work of (Das & Kempe, 2011), which also demonstrated that the standard greedy algorithm achieves a good approximation ratio of (1-el (1- for the problem of maximizing such functions subject to a cardinality constraint. On the inapproximability side, Harshaw et al. (2019) proved that no polynomial time algorithm achieves (1 - - + +)-approximation for the problem of maximizing a 7-weakly submodular function subject to a cardinality constraint, for any > O. Subsequently, Chen et al. (2018a) investigate weakly submodular maximization beyond simple cardinality constraints and pointed out that the Residual Random Greedy method of (Buchbinder et al., x²2
2014) can achieve an approximation ratio of (1+7)² for the problem of maximizing a monotone y-weakly submodular functions subject to a matroid constraint. After that, Khashayar& & Manuel (2019) examined the approximation performance of standard greedy algorithm on 7-weakly submodular maximization over matroid constraints, which showed that the standard greedy algorithm can offer an approximation factor of 0.1-² where is the rank of the matroid. It is important to -P++I
note that this approximation ratio 0.47² -FJ+T is not a constant guarantee and highly depends on the matroid rank r. In order to improve the approximation performance of these greedy-based algorithms, Thiery & Ward (2022) introduced the notion of upper submodularity ratio 3. defined as Eq. (3). Moreover, Thiery & Ward (2022) also developed more powerful distorted local-search algorithm for (7. ---ellllly submodular maximization, which is inspired by the non non-oblivious search (Filmus &
Ward, 2012b; 2014) for submodular maximization and can guarantee 22(1-e (0000)))1))))
-(1-7)+>* approximaaion for the problem of maximizing a monotone (y, -wekkly submodular functions subject to a matroid constraint. Note that, when the (7, B)-
weakly submodular function is closer to being submodular, namely, 7, 3 + 1, the approximation ratio 201--- ((I-
72 will approach the tight (1 11-1//1 1/e)). Conversely, when 7: 3 + 1, the approximation guarantee [+-3z of the Residual Random Greedy method (Chen et al., 2018a) will trends toward the sub-optimal 1/4.
Weakly DR-Submodular Maximization: Another significant class of "close-to-suune to-submodular" functions is known as a-weakly DR-submodular functions, where a is variously referred to as the Liminishing-retur(ODB ratio (Kuhnle et al., 2018), the generalized curvature (Bogunovic et al., 2018) or the generic submodularity ratio (Gong et al., 2021). The work of Khashayar & Manuel (2019) is the first to give study of maximizing a o-weakly DR-submodular maximization subject general matroid constraints. Specifically, Khashayar & Manuel (2019) proved that the greedy algorithm achieves a-weakly DR-submodular maximization. After that, Gong
approximation ratios of I+a for the et al. (2021) extended this result to p-matroid constraints. Moreover, Nguyen & Thai (2022) also considered the impact of curvature (Vondrák, 2010; Sviridenko et al., 2017) on the standard greedy algorithm for a-weakly DR-subnodular maximization under partition matroid. Recently, Gong et al. (2019) showed that the continuous greedy combined with the contention resolution scheme (Chekuri et al., 2014) can obtain a sub-optimal approaximation ratio of a(1 - 1/e) e -=) for the problem of maximizing monotone a--eakll subuuuuodll functions subject a matroid constraint. To achieve appproximation guarantee, Lu et al. (2022) recently have proposed novel distorted local-search method, which is also motivated via the non-oblivious search (Filmus& & Ward, 2014).
the tight (1
A.3. Monotone Continuous DR-submodular Maximization
Submodularity can be naturally extended to continuous domains. Generally speaking. differentiable function F 10, + R, is DR-submodular if Fx(x) < VF(y) ) for any x 2 y. In deterministic setting, Bian et al. (2017b) first proposed a variant of Frank- for continuous DR submodulal maximization problem with (1 11/e- e) approximmaionn guarantee after (11/c) iterations. When considering the stochastic gradient oracle, Hassani et al. (2017) proved that the stochastic gradient ascent can guarantee a 11/22-aaprrxximation after ((1/e) iterations. Then, Mokhtari et al. (2018a) proposed the stochastic continuous greedy algorithm, which achieves a (1 - 1/e - e) --aaproxximation after (11/e² iterations. Moreover, by assuming the Hessian of objective is Lipschitz continuous and considering non-oblivious stochastic noise, Hassani et al. (2020) proposed the stochastic continuous greedy++ algorithm, which can guarantee a (1 1/c c) apapproxinotionn after ((1/e²) iterations. After that, Zhang et al. (2022; 2024) proposed non-oblivious auxiliary function for continuous DR-submodular functions, which can efficiently improve the approximation ratio of stochastic gradient ascent (Hassani et al., 2017) from 1/2 to (1 - 1/e). In addition, numerous variants of continuous DR-summodular maximization have been extensively studied, for instance, online scenarios (Chen et al., 2018b; Zhang et al., 2019; Pedramfar et al., 2023; 2024;
15

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Zhang al., 2023a), decentralized environments (Mokhtari et al., 2018b; Xie al., 2019; Zhu et al., 2021; Gao et al., 2021; Zhang et al., 2023b; 2025), and bandit scenarios (Chen al., 2020; Zhang et al., 2019; Wan al., 2023; Pedramfar et al., 2024; Zhao et al., 2025; Zhao & Lai, 2024; Yu et al., 2024a;b; Jin et al., 2024; 2025).
We need to emphasize that, when the set function f is monotone submodular, Theorem 2 implies that our proposed Multinoulli Extension also monotone continuous DR-submodular over the domain I An,- However, it is worth noting that these former results about continuous DR-submodular maximization cannot be directly applied to our ME and the relaxed problem (4). This is because all of them highly rely on the following inequality: G is monotone continuous DR-submodular function,
yy - x, Vx)))) 2 V x, VG(x)) 2 -x()) - G(x),
where V is the coordinate wise maximum operation, i.e., x V = max(x.y).
Note that the second inequality in Eq.(7) requires that the vector y V x is included into the domain of objective function G. In other words, the domain of objective function G should be closed under the wvordinate-wise maximum operation However, the domain [l An, of our ME does not meet this requirement. Similarly, the best of our knowledge, the latest research on both upper- linearriieerizable and weakly continuous DR-submodular maximization also requires the domain of the objective function to be closed under the coordinate- wise maximum operation V. (See (Hassani et al., 2017; Zhang et al.,
2022; Pedramfar & Aggarwal, 2024))
B. Additional Experimental Results
B.1. More Discussions on Experiment Setup
In this subsection, we highlight some additional details about the experiments. At first, we describe the parameter setups regarding our proposed 'Multinouli-SGA' 'Multinoull--CG'' and 'Distorted-LS-G.. More specifically, we consider the following parameter configurations:
Distorted-LS- Algorithm B. in (Thiery & Ward, 2022) where we set the number of guesses L = 1+ [og -)) 3 )1 the total number of improvements M = 5, the number of samples N = z/2 and = 0.01 where r is the rank of the partition constraint, namely, =Σ B, in problem (1);
Multinoulli-SGA': Algorithm is implemented with batch size L 20, the step size n /T and the number of iterations T = 167. Moreover, we round each continuous solution via Algorithm 2. As for the Fuclidean projection of Step 6 in Algorithm 3, we utilize the CVX optimization tool (Grant & Boyd, 2014). efficient algorithms for handling the projection over partitions if we view as multiple independent singly constrained quadratic programmings problems(See (Pardalos & Kovoor, 1990) or Appendix B in (Zhou al., 2022));
worth noting that there exists
Multinoulli-SCG': Algorithm is implemented with batch size L [ and the number of iterations T= 167. Furthermore, in order to obtain a high-quality subset, we apply Algorithm 2 to round the x(T + 1) total of T times and then select the best one among these resulting subsets.
Note that, when = 0.01, the number of guesses = 1 + [og(1-e) P 167 in 'Distorted-LS-G such that we set the total of iterations = 167 in both 'Multinouli-SG.A' and 'Multinouli-SCGG: Given the long runtimes of 'Multinouli- SCG' and 'Distorted-LS-G", we report their average results in Table based on 5 repeated experiments. In contrast, 'Multinoulli-GA. and 'Residual- Greedy" algorithms are repeated 10 times. Finally, all experiments are performed in Python 3.6.5 on MacBook Pro with Apple MI Pro and 16GB RAM.
B.2. Maximum Coverage
In the tasks of video summarization, it is easily observed that our Multinoulli-SGA algorithm exhibits exceptional empirical performance. However, according to both Theorem 5 and Theorem 9, we know that our Multinoulli-GGA only can ensure a sub-optimal approximation guarantee in the worst case. To verify the theoretical correctness of our proposed Multinoulli-GG. algorithm, we consider special maximum coverage problem as discussed in (Filmus & Ward, 2012a).
Let the universe set consist of n - elements { 2n-1} and n - k elements [yI..... vn-k J. all of weight 1, and n elements (c1,-.., (--1) of arbitrarily small weight e > Then, we define two different set A, and B, for any i [n].
16

---

soorithm,whichh highlights the efficiency Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Table Results on coverage maximization((nd--in columns) and bayesian A-optimal (the final column). Note that 'obj' denotes the utility function value, where a higher value is preferable, and 'queries' represents the magnitude of the total number of function evaluations, that is log1o of the total number of value queries to the set objective function, with a smaller value being more favorable. 'Distorted-LS-G" is the abbreviation for the distorted local-search method with O /e)orundd guesses, namely, Algorithm B.1 in (Thiery Ward, 2022). each column of 'obj', indicates ranking the 1st and stands for the 2nd.
Setting
n=15,
n=20,
n=30,,
k=6
n=40, k=8
5=
k=10
Housing
Mothod
obj
queries
obj
queries
obj
queries
obj
queries
obj
queries
obj
queries
Standard Greedy
14.14
2.65
19.19
2,90
29.29
3.26
39,39
3.51
49.49
3,70
61.295
3.70
Residual-Gredd
21.04
2.65
32.52
2.90
48.25
3.26
64.67
3,51
77.13
3.70
61.104
3.70
Distorted LS G
24.00
9.06
34.00
9.44
53.00
9.98
71.00
10.36
89.00
10.65
61.285
10.26
Slultinouli-SGa
14.14
5.45
19.18
5,56
29.26
5.72
39.34
5.83
49.43
5.92
61.745
6.61
Multinoulli-SCG
24.00
7.39
34.00
7.64
53.00
7.99
71.00
8.24
89.00
61.456
8.44
that is to say.
A = {f} for 1 sinn-1,
Aa = {I1,
In
In
B; = (1i) for sisn-1.
Bn = (yr..... Un Un-k)-
After that, we define a coverage set function/ f:2²= + R4 over these 2n distinct set (.i..... An, BI,... Bod where [2n]. More specifically, we have that, for any subset F V.
1(5) = Σ
w(v),
(8)
vEU
where w(v) is the weight of element v, Sg AA when 1 j < n and Sj- = Bj-n as for n + J j S 2n.
Moreover, we consider a partition constraint that contains at most one of (A.B,) for any i E [n]. If we set V2 =
[li+n](> Uvein V; = [2n]), we naturally obtain the following coverage maximization problem:
max ((F) s.t. | Vi S 1 Vi E [n]. FCV
From the result of (Filmus& & Ward, 2012a), we know that the problem (9) is a submodular maximization problem subject to partition matroid constraint, namely, a = 3 = 7 1. A key feature of this coverage maximization problem that Filmus& & Ward (2012a) found that the standard greedy (Nemhauser al., 1978) will be stuck at a local maximum subset {A 3 where F = [m]] and ((F) = (1 + e)n. In contrast, when is very small, the optimal subset for problem (9) is {BI,... B,} where F= = {n + 1,...,22 .2] and ((F) = 2n - k- 1. Note that lim lime k-+0 2n-k-1 2-
(1+e)m
Motivated by this finding of (Filmus & Ward, 2012a) and the correspondence between the set [n] and {A A, in
problem (9). we conjecture that the point 1/r) may be local stationary point of the Multinoulli Extension of the set function in (8). Before showing the rigorous proof of the previous conjecture, we firstly compare the empirical performance of our proposed Multinoulli-SCG and Multinoulli-SC. against the standard greedy method and the residual random greedy method as well as the distorted local search across distinct coverage maximization (9) with different n and k, where we uniformly set the weight = 0.01.
From the results in Table 4, we found that both our proposed 'Multinoulli-SCG' and 'Distorted-LS-G" algorithm eventually select the optimal subset, i.e.. { }. In contrast, in all settings of maximum coverage problems, 'Multinoulli-GA'' and "Standard-Greddy algorithm are trapped around the local-optimal set (AI..... A..). Moreover, the 'Residual-Greedy method oscillates between the optimal subset {B B, and the local maximum set (A,...,,A., Similar to the video summarization in Section 5. Table 4 also demonstrated that the number of function evaluations required by our Multinoulli-SCC is 2 orders of magnitude lower than that of the 'Distorted-LS-G" and effectiveness of Multinoulli-SCG algorithm.
Now, we show that the point 1 [n] is a stationary point for the ME of the set function f in (8). Before that, we detail the ME F' of the function of EQ,(8), that is,
(1US (ett) I P((e)
F F(p ...........>> === Σ Σ
(10)
d=l c)
17

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
where we set P: (vt. Pr(ilp.) - p.. Pr(n ilp)) = 1 and Pr(O)p.) pt - 12.
From Theorem I, we know that,
aF
OF a(ph)
(mm)) for 1 n
(1(x) 1,
p(p))
0F
OF
(1m)) 0 for 1 sisn
0(vg) (1 = - k.
0(p?)
As a result, for any (PI..... .p). E II>=1 42, we have
PI....., P..) [m]. (.)))
0F
OF
Pi {(p))
(1 (mn) + p 013;) (1mm1) - (1 () 1)
p + (n - 1)ph + (n - k)p² (1 + +c(nn- 1) 1)
(pt - 1) + (m (1pn + (n k)p² - (n - 1)
Σ (pl 1) + ((n k) - (n 1)) (n 1)(1 phh -p:) S O.
As result, 1[s] is a stationary point of the ME F. Note that pm
(++ + when k + 0, e + 0 and 2n-1-k
(.......).))))
n + oo, which implies that the approximation guarantee of Theorem 5 is tight when a == = 1.
B.3. Bayesian A-Optimal Design
In this subsection, we consider a classical subset selection problem in experimental design (Hashemi al., 2019; Borsos et al., 2020; 2024), namely, bayesian A-optimal design.
We first describe the details of the bayesian A-optimal design. Suppose that 0 Ed is unknown parameter vector that we wish to estimate from noisy linear measurements using least squares regression. Our goal is to choose a set S of linear measurements (the so-called experiments) which have low cost and also maximally reduce the variance of our OLS estimate. More precisely, let = [=i,..., E Rdxa be a matrix including n different measurements. Given a set of measurement vectors S S [n]. we may run the experiments and obtain the noisy linear observations ys X + es. where es N(0, o2 N( [1s))- We estimate using the OLS Ô = (XxXf)- ys. After assuming a normal Bayesian prior distribution on the unknown parameter 0 ~ NN Σ), we can compute the sum of the variance of the coefficients as r(S) = tr(E + X where tr(-) is the trace of matrix. If we redefine the g(S) = r(0) - r(S) tr(E) tr + 27 X -1, we can reformulate the bayesian A-optimal design as a (7,3)-weakly submodular maximization problem (Thiery & Ward, 2022) with 3 1/7-
In our experiment, we use the Boston Housing dataset (Harrison Jr & Rubinfeld, 1978), a standard benchmark dataset containing d = 14 features of n = 506 Boston homes, including average number of rooms per dwelling, proximity to the Charles River, and crime rate per capita. Like Harshaw et al. (2019), we preprocessed the data by normalizing the features to have a zero mean and a standard deviation of 1. After that, we set o = 1/Vd and randomly generated a normal prior with covariance Σ- ADAT where ~ N(0, /) and D is a diagonal matrix with D.,- = (i/d)2. As for the partition constraint, we randomly cut the all 506 data points into 10 different groups and then select at most one element from each group. Then, we present the results of bayesian A-optimal design in the final column in Table 4.
From the final column in Table 4, the performance of our proposed Multinoulli-SCC and Multinoulli-SGA algorithms sur- passes that of three benchmark methods, namely, 'Standard Greedy', 'Residual-Greedy" and 'Distorted-LS-G" Furthermore. like the previous experiments about video summarization and maximum coverage, the number of value queries to the set function required by our Multinouli-SCG and Colltinoulli-G-... is 2 and 4 orders of magnitude lower than that of the IDistorted-LS--G respectively.
18

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
C. The Properties of Multinoulli Extension
C.1. Proof of Theorem
In this section, we prove the Theorem 1.
Proof. 1): At first, we review the definition of Multinoulli Extension. For any given set function f: 2" + R4 and any point (Pi....) pk) I Anx. we define its Multinoulli Extension for the subset selection problem (1) as:
B I
F(p . Pk)
Σ
(s(U
u E (2)
(11)
k=1b=1
where Pr(v (Pp) = P and Pr(0 =
Em=i Pk for any m E [ng] and & [K].
From (11(, for any parameter pk where m [mx] and & E [K]. we have the following equality:
8
1 Pr(e p2)))
aF (P....... Pk)
E
(f(U B
k= (efl)
(12)
0p
Opk
Then, according to the definition of Pr(e Pí). we can show that, if l: + k
OPr(e
0 for any of E V/8 U (0). When
Opp"
aPrie
oPr(g(pE)
1: k.
we also can show that, ch = o/
Opt = and if cf =
= -1 As for of & (uE, 0), when
0pp"
(Pp( O. As result, we can rewrite the Eq. as: Opf."
i.
aF
Σ
U Be (S(UKL
(2())
Σ
(Q
II
Pr(e pp))
OPr(ek (px)
2
0pg
Opk
Σ
Σ
Be (F(UÆ
U b=1 (
OPr(e pp))
II (R,
Pr(e D& pa)))
Op
bLE(BA)
= Σ
Σ
E
E cfEnautO)
T3 ((UK / ((()))
OPr(ez b
(ps)
II Pr(e (pk) ))
Opk
(LE(BA)
(k.b)
Pr(ef1p2) )
= Σ
E
((ofIUEE (e(t)
II
(k,6))((),8)))
(1(PE ((R (et))
= B
Σ
II Pr(c(1p2))
(R.6)
(1(1)) (1 ((TIA (eft)
II P((efIPS)) )
Br
Σ
Pr(ef(pa))
E
(R,6))(0.1)
(1(:1144 (1(F111R0SHA (eft)
Σ
II II Pr(e pa)
of V
kE(K)] dE(Ba]
B B.g-Maniies (5 (1(zz)
URbdra (e))))
Bb
(13)
19

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
bj is independently drawn the same multinoulli distribution where the fifth equality comes from that each random element eg Multi(pa) for any b E [B&] and the sixth equality follows from Eveuga) Pr(e p&] 1.
2): Next, we prove the second point of Theorem 1, At first, the monotonicity
implies that for any two subsets A B C V. f(A) S (B) such that we know that f ( ( (R..)) {c)) 2 0 for any random elements & vb E [By], Ak [K].
As result, we have If f is monotone, then
aF 3pt
2 O, vk E [K], m E [mx]-
3): As for the third point, we firstly unify the process of generating random elements regarding two different multinoulli distributions with parameters Pa = (P......PP." E Ang and Px (p)- .......... Pk x Ang where Pk 2 Pk for any
m [ng] and & E [K]. More specifically, we will transform the sampling process from each multinoulli distribution Multi(pa) Multi(pa) into function of two independent uniform random variables on the interval [0, 1]. Namely, for any two independent uniform random variables X, Y on the interval [0, 11. we define that
If E (0.pk)
Uk
uk
If
Σ
T
Σ
Pk pk) for some integer E [2, m4]
m=1
m=1
If Z
Pk
m==1
We can easily check that, when X and Y are uniform random variables over the interval [0, 1], the random element e(X, Pk, Pk)) follows the multinoulli distribution Multi(p:) over the community V4: := {ot...., ox }. where p = (pk.-.., nk E An, and (r(e(X,> Y, Pt. p&) = ) = Similarly, we also can generate a random element 2 from the community V& according to the multinoulli distribution Multi(px) we set
n
e
If
Pk
m=l
Pk
Pk
0k
If X
Pk and Y E [0,
> Ti
m= Pk
ē(X, Y, Pk. Pa)
Σ cc-
(Pk 12
(
Σ c
pk
2
If X
Pk and Y
m=
m=
for E [2, mz]
2m Pk
m=
Pk
m0
0
X
>
Pk
m
and Y
cm
PE
m=l
m=
From the definition of e(X, Y. P& Pk) and e(X, Y, fe(X, Y, Pk. p. Thus, if we generate multiple independent pairs (X), yi) for any b [Bg] and E [K], from the first point of Theorem 1, we have that,
Y. Pk. P&), show that, for any fixed X, Y, fe(X, Pk. Px)) S
OF
E BBS(U))) U(B.yaaa. tef yd Pa. Pa)) Pa.Pe)))))
P
Pk) = BB
3pm
OF
E ((F(rz) U(BB)) 16( yi Pa. px))))))
(p.....,,pu = Bk
3pm
Due to (x dd k
E Pk, pk)} S (x) y Pk. PR. ph)), we can show that,
(U(Rb)A (ef yi pP....)) C (U.R.)AAR. 12 yh pa. (n.))))))
As result, from the definition of weakly DR-submodularity, know that if f is a-weakly DR-submodular, have OF
Bp (P....., Px) 2 5 (p...... Px) such that VF .P)) 2 aVF(p..... Px).
OF
20

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
4): We prove the fourth point of Theorem 1. From the definition of Multinoulli Extension and previous definitions of <Xx, Y, Pt, P&) and eeX, Y, Pk, P&), we can infer that the Multinoulli Extension F of set function f satisfies the following relationships:
k k= 1 ye, Pa. Ps))) pK) = 5(
F(p.....,pk) = -f x pk. bu)))
As a result, we have
T(Pi......R PK) - F(PI..... ..D.........>> = R (S(UK Uf tef vg, pa.
Pt.a. ba)))) - - ( y (ef yi. Pk.
If f is y-wakly submodular from below and Pk 2 py for any E [K], we have that
7 (F(i...... .k) - - pk)) = = (al/s((S (S( UR
U ben 12 y Pk. Pe)))) - 1( (UR Up le y Pa. Pwll))
(( yr Pk De) u U lef (X y Ps, .on))a)))
E
where the final inequality follows from the 7-weakly submodular property of f. namely, for any two subsets A C BCV. Even (cl EnEmA f(v A) 2 7 (F(B) - f(A))
Then, if x Emi pha we know that (x k. yg, Pes Pp) = (x
ks K Pr. P&) such that f ( ko y P P&) U
k. xg. P&. (.)))) = 0. As for the case that x 2 Em ph: namely, of (x2. y P P3) = 0. which means that we have the following equality:
R (x
( yd. PE. Po) u u le (x y Pk. Dull)
(14)
= f 2 x rl P&: U (x ye, Pk. P+)))
Therefore, we have
(PP....... .Pk) F(pI.....PP. .k))
K
B3
(X yy Pa. P&) UK U (x vh pk. pc. Dall))
E
R=1 6=1
K
B3
Pa Px) uK Up fch (x r Pa: Da))) (x vi),, (kt, + (R. (2.5))
E
E
(xb bt
y
k=1
b=1
K
B3
E
E
Pa. kt y
px)
u 1 (x r Pa. Pb)) 1(x
p
(x ko vb) (k. + (k. b)
m=1
K Bi
mag
E
(X
r
PR.
pa)
uk
U fot y Pa. Px)) 1(x
pk
(X (k. + (k.
k=1
m==1
K
Bg
E
E
ke y PA. Px) u U fet (x rd, pk. pb)) 1(x} 2
p
r2) ( (k. b)
kr k
k=1 b=1
m=1
where the final equality comes from / (x Yp p&. Px) pk u le y pa. p.))))))) = 0 when x < E Pk
21

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Then, from (q.(14), we also can show that
E
k PE. P
U Un
(e R
Pk: Pa)) 1(X
Σ P (X (B, (X (k,
ng
Σ Pr
c
(X
re
Pk. PR. x
Σ m=1
pt (oE
U(RB)AIRED) fef px. px)1)
p&.
(15)
c=1
P
(0)
UADAAD (x y P&. Dall).
where the equality comes from that
Pr eb (x xb PE)
x k ko PE.
= o
x
ni
Pk
= Pr xb 2 Σ
Pk
th
2m
(P
m=
Pk
P
(
m==
THE
P
P
m
mm1
10 - pxt
As a result, we have
F(
.........................
PK)
F(I....... .P.))))))
K
B
n
PE f pf (o (IR.))AARDD tex( y Pk. Pa)t)
E
Pp
m=1
K
BC
Pk )f (o U(RDD) (x re pa. Dall)
Pp%
b=1
m=1
K Thg
10%
Pk m.
BBE
f 5(xx]
U(R (x y pa. bx)))
1=
m=1
Σ
Σ
Pk
)
OF 0pp
(Pi.
........pp>== (ID)...... (fI......PP. px) (PI, pk), VP(pI. ... .pppp)......)......))>>>))))..
k= m=1
where the second equality follows from the independence of ef for any E [Bq] and k E [K].
C.2. Proof of Theorem 2
In this section, we verify the Theorem 2.
Proof. At first, we recall that V& == fuk..... ,,k } for any le E [K]. Therefore, for any subset S within the partition constraint of problem (1), we assume |S n Val 88 S B5 and we can represent each n V4 as
S V4- = {ux my
..... uk
where m by m E [nx) for any b1, b2 E [sx] for any ls [K].
As result, we can rewrite that
1sn VF(P...... Pk)
K
OF
(Pi
Pk)
Bx
Bi Opk. m
k= b=1
E Maltiip (1(1F2)
mil
U(R.D)S((R))) (e(1)
(16)
K
E Mallitps) (f(0 mil
km 1
22

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
where the final equality follows from that, for any fixed & [K], the elements of Ab [Bg]] are independently drawn from the same multinoulli distribution Multi(pi)
When the set function is a-weakly monotone DR-submodular, we can show that
1snvs VF(PI.....PP. ........PP Pk) Bx
B Muliipp (1(55t) (CR.)) feb3))
K
Mathitp! (s( f U (ct) U (U (URAD)rca to (omt)) ())))
00
(17)
1=
b=1
(S(VÆS t mi }/ U - (et)))
a
Mulittp
(f(U Use 10 }) 5( fl ( - (ctt)) (Monotonicity)
2 a
B. Mutiii
= =a [(S) F( F((p....,pk))) pK))
where the first inequality follows from the a-weakly DR DR-submodularity. namely, [[v] A) 2 af(o for any two subsets C S V and the partially ordered set {(k, b) < (k. b)} = {(k b){k < or < 6 when k = k}.
As for the settings that the function f is (). 3--allllyyyyyy monotone submodular, we firstly can show that for any two elements e 62 E V and the subset B C V, have that
BU (U(e) (
[(e]]B)+[(ee)) [(e2)B),
such that
(18)
From (18), we can show that
K
1snv
VF(DI.....
Pk)
E c Multipp (5(1)" (c/z UERDDSACRD tef)))
(19)
k= b=1
(a5 (1 (15(112t)
mi Up U (c1)) - (1 - >>s (>) (((BU (e (ef)))
E 2 Mutorige
Then, from the 7-weakly submodularity,
E e Mullipa (f(ppt) uK Ufth (c ((t))))
2 7 B Mudripp (f(vkS u (omr) U [
(20)
2 ((S) F(p F(p......pk)
where the final inequality follows from the monotonicity.
23

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Furthermore, from the 8-weakly upper submodularity.we we also have,
E & (5(el) ((.))) (c (c3)))
K B2
B Mulifii (f(e)) ((B.))(())) (e tett)))
(21)
Bx ( (( (())) - s ,
< BE
M
%
where the second inequality follows from the definition of B-upper submodularity, namely, Eq.(3). Merging (q.(2 and (20) into (q.(19), we have that
1snve
VP VP'P......PPi .P)
K 8k
B. Reg (75 (v5(12)) mmb)
| 1 Be (c)) - -(1-2)((c))
Uab (2)00222( (e))))
k= b=1
2 (f(S)
F(P ... -(1 ((1)))(1)) Px) = -(²)(8) - -(8(1 - - - Pk).
C.3. Proof of Theorem 3
In this section, we verify the Theorem
Proof. Firstly, from the fifth equality in Eq.(13), we know that
Pr(e(pps)) )
OF .I, .KK) Bb
Σ
(((F)URADAAA (c)t)
II
Opm
(k,6)
Therefore, if 1 * 12 E [K], for any my [na,] and m2 [nazll
F
(PI.... (Pi....,PR' .p))
Oph. Opk2
ma
a Ha Pr(e (pa)
(1(17 U (ch))
=Bki
Σ
Öp
Bk
Σ
( (c))
Σ
OPr(c bu
|ead]
II (1)
Pr(egIps)
Opki
(1( (1 (ch)
(1(Z))
OPr(e (ptz)
=Bxi
Σ
E
II (())
Pr(ckIps)
Oph.
brelBegl
(1I
OPr(eh, |paz) 1912
BB, Bkg
Σ
Σ
( (c)))
II ((r.))
Pr(e ((ce(l:)))
Opki
((h
co EVey 1003
Due to that Pr( P+i pd and Pr(0)p:) = =1 "1
Pk we can show that
OPr(et (PEs)
Σ
1 (0 ((R (
et, EVa, U(0)
= - U ( Ulomaa) - -((%)) (EBDUAAAAAAA (e))).
24

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Therefore, if set (1b.))) fe we can show that
8 F
Pp....., Pl....,pk) PK)
Opk1
m1 mz
Opk2
OPr(ek, piz))
Ba, Baz
Σ
Σ
1 { ( f0(3)
II (H..))(
Pr(e((pa))
=Ba, Bes
E
(1 (1 -f (sT
II (4.5))((0h,)))02.))1)
Pr(e(lps))
(1(17188 (
(1
BR, Bug E Mils(pe))
where the final equality comes from that the subset S () ((1,)) leh] is unrelated with the random elements ej, and eky.
When K1 = k2 = k [K] and B3 1, it is easy to verify that
82F "p."1 mz (PI.... PK) = 0. As for B₁ 2 2, we have that
ōv 0pp
F²F
0pp Opk mg (pI....,PA) .P)
@ (Iabas Pr(ek(ps))
Bu
Σ
(( telt)
07%
(1(7)) (CR (c())
@Pr(e hi
ppt)
By
Σ
II ((.
Opk T0
25b15BB
(1(77)
OPr(ek \pt)
= B
Σ
(UPUUA (ch1)
II (6.6))(((
p((e(lp)))
Op. 1912
2gh, BB
(( (c))
aPr(e Pk)
BB - 1)
Σ
II ((..))(((
Pr(ef p&)
192 Opp
(B 1)
Σ
Σ
( (ct))
OPr(e Ipa)
II (k.6)((
Prie
Oy
((.
Also, because Pr(vplp; P and Pr(M1 P;) Emi P we can show that
@Pr(e Px)
Σ
Oyh
(0 | (e Ulof1))) (100" (1 telt).
As result, if we set = U( (efp we have that
8F
(P1, [p....,ppk PK)
Op Op
Ba
Σ (1(00))5 (122)) (1
II
Pr(cf Pp:) P())(P)))
(((o))/ ( (,m3)) - ( (1(01s))
=(B} B& Muta(pe)
25

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
where the final equality comes from that the subset S ((.,))((( (ef) unrelated with the random elements cj and ex
D. Stochastic Variant of Continuous Greedy Method for Mutinoulli Extension
D.1. Proof of Theorem
In this section, we prove the Theorem 4.
Before going into the details, firstly bound each second-order derivative of our proposed ME. F, that is to say, Lemma 1. Given monotone set function J 2 - IR.,, if we denote the maximum marginal value of f as My maxsgv,eevis (fels))) we have that, for any k1, h2 E [K], mi E [mx,] and m2 E [n
OFF
(PI P ........) BB,
Opk, mhi
0pk2
where (PI.... (Pi...... PK) II An and B max Bg the maxinum budger over the communities (Vi...., Vk3.
Proof. From the Theorem know that, If 11 hi [K] the second-order derivative of the Multinoulli Extension F any point (Pi...., pk) E II Ang can be written as follows:
O²F
Opk 0phy m2 (PI..... .P)) = BR, BRo (S (1 -
1f f(g (u 1s))
where S U ((), 1) {e and each of is drawn from the multinoulli distribution Multi(p,). Furthermore, for any monotone set function J and any subset S V, we can easily know that:
-M, 5 (F S (0h IS (u f (x,) S f f(2h IS (v S M,
such that, when kn + h2 E [K].
8 F
(P1..... Pk]l S Bkg Bkz My S By.
0pk Opmz
[nxi] and m2 E [muz] we have that Similarly, we also can verify that when kn lo k E [K], for any my
8p 1."8pp Bp (PI,...,PP pK) B²M
F
Similarly, we also can verify that the estimations of the second-order derivative of Multinoulli Extension F in Remark 6 are also bounded by 8 My, that is to say.
Lemma 2. Given a monotone set function f 2 + R4, if we denote the maximum marginal value of f as My maxscvieevis (f())))). we can infer that each second-order estimators in Remark also bounded by B3 M. ie., for any k1, l2 [K]. my E [n and m2 [nwz]] we have that
O2F
((P ((P..... ........ .K))) B2 B2M
Op mi Oym
where (p1... (PI....,PP' PK) -I And and B max B& the maximum budget over the communities (Vi..., Vx
As result, we also show that Lemma 3. Given a monotone set function f 2 + R4,, if we denote the maximum marginal value of f as
M, = maxscv,eevs (F(e(S)). we can infer that each Hessian approximation & == E FxF((((t) in Line of Algorithm I satisfies that,
1 < <BB2M
where+ t E [T], n = [/. L a positive integer, B max By is the maximum budget over the K communities (Vi,...,Vy, Vx).
26

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Remark 11. For any matrix Rex", the (2, on)-m of is defined ||Al|,, sup([|Ax|| x R", ||||| 1} where || -I denotes the 1.2 norm.
Proof. From the definition of the norm || 11,,,000 can show that
1 max
(i. S nB
(E(n)
where (i,)) is the i-th line of the Hessian approximation
? and the final inequality follows from the Lemma 2.
With the Lemma 3, we next verify the gap between our gradient estimator g(t) and the exact gradient VF(((t)), that is, Lemma 4. Given a monotone set function f : 2 + R+, if we denote the maximum marginal value of f as My maxssv,eevys (f(els)), we can show that each gradient estimator g(t) in Line 11 of Algorithm I satisfies that, for any
t t [T]
E E(IB5(1) VF((()))
NEP BrM
<
LT
where L is the batch size, (V], B max B& is the maximum budget over the K communities (Vi...., VK} and the
rank r = >k= Bx.
Proof. Note that in Lines of Algorithm 1, we compute the exact gradient our proposed Multinoulli Extension the point O and then assign this value g(1). Therefore, know that when / 1,
(lg(1) (F(((1)) (g((1) VF(O) = = nur Ba M
LT
When > 1, we have that
E (le(()) VF(((t))1
E ((lg(( 1) + &. vF(((())
B(1B(11 - 1) - vF(x(1 - 1))1() + +B( -1) VV(XI-)
+ E (g(t - 1) VF(x(t 1)), (VF(((())) 1)))
Note that
(g 1 - -(V(5,((VVV)(())) - ((((()))V((((())))]
E
E
R (0((( VF(X(1- 1)), 1)))E:-(VVF((()) -VP(X()-VV(X((11))) (x(1))
(F(x(1-1))
= H ((g(t- -1) VF(x(t 1)). (sxxx(()) - (VF(x(t)) -VFIx(t)-VVix(t-1)))
0.
27

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Therefore, have
E (I((t) VF((
E (Ig(( 1) VF(x(( 1))1B) +B (IE,
- (VFIx))-VV((((-1)) 1)))
E (Ig(tt 1) VF(x(t- 1))113) B ([((()) - x(t - 1)) (VF((x(()) -
( (x)) x((- x((-1)))= - -(VF(x(()) VF((((- 11
(1g(( 1) VF(((L 1))118)
+ 1 (1((((((())))))000)) -x x(((x(()) -1)) -
= =I((((( - 1) VF(X(1 19)13)
SB lgg(t VF((xt 1))113
1
E
[1**F(x (f) x(t ((--))]lB 1))
L
SE (lg(t 1) VF(x(t 1))113
E
( (t) (x(t) x((t 1)113
L
K
= -B(I8(1 - 1) VF(((1- 1))113
+ B
(x (0)) + Σ
1 s 1ynee 112
B
km
B,
x ς < 1) VF(x(t- - 1))113
LT
S [g()) - + nrB²M,
nr B
(t 1) S
LT
LT
where the first inequality follows from E(X - B(X))* < 2 for any random variable X; the second inequality comes from the definition of the norm ||
12,0: the third inequality follows from the Lemma and the ascent direction ΣK 1 1s(st- 1)m,, has at most non-zero elements.
Now, we verify the Theorem 4.
Proof. From calculus, we know that, there exist a constant a E [0, 1] such that
F(x(t+ + 1)) - F(x(tt) x((( x(t - -)) = 2
1 (V))(x(())
(x(())))x((()
x(t)) x(t + 1)
- x(t)).
where (t) ax(()= + (1- a)x(t - 1). Therefore, we can show that
F(x(t+11) 1))
2 F(x(t)) (VF(x()), x(t) ! ( ((*)
(x -x)()(+)))))+---..))))) x(( 1) -x(t))
[ ||x(t+ -x(1))
(22)
2 (VF()))((F((())))...)))))))
x(t)
2
Bv/MM
2 F(x(t)) + (VF(((())) -)) -
1) -
2
where the final inequality follows from Lemma 3.
28

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
With (22) and x(| +1/ = x Fv(), we also have fhat,for any subset S within the partition constraint of problem (1),
F(x(t+ + 1))
B B
2 F(((1) + (VF(x(I), 1()+ -(())
|xx(t +
+1)-x(111
2
K
B BynMs
K
= =(((1)) + T VF(((())
Σ
12
ss
Bk
2T
B₁
k=1
k=1
F(x(t)) + 1
K
1
1
B B
K
1
g(t),
+T T
+
VF(((t)) g(t),
1s
1 1s
T
B&
BR
21
BR
k=1
k=1
km1
= F(x(t)
g(t).
K
1snv'
+ T
VF(x(t)) g(t), Σ
s
B ByMM
K
1
11
T
B
27
B
k=1
where the final inequality follows from problem (I) and Line 13 in Algorithm
ER=1
K
isnve
Il Ang the subset included into the partition constraint of
k=1
B.
As a result, we can show that, in expectation,
B(F(x(++1))
2 B(P(x(())) + 1 BB g(t),
1snve
) (VF(X(0) -((), Σ
1
Iscerva)
Be
BB
BVnMi
K Σ
1synn
E(11
11²)
2T
kmm1
K Σ
K Σ
=E(((((I)) T
E(((U))
1sme
)
+
7
1
(FF(x()) 9().
Ba
(23)
1=
k=1
BVnM
K Σ
Is
E(11
12)
21
Be
-F(F(x(()) + (F(((t))
1 T
Σ
1snve
+ 1 1 (F(x((1) -(())
Σ
1
(semm))) )
Bu
h=1
k=1
BVTM
E(II
Σ
K
Is
1(),
2T
B₁
#=1
where the final equality follows from g(x(t)) is the unbiased estimator of (x(())) for any t E [T]. 1): When the set function f 22 + R,+ is monotone and a-weakly DR-submodular, from Theorem 2, we can show that
E(F(x(1+ + 1)))
=(F(x(()) 1 VF(x(t)),
-
K Σ
1snvz
+ F
VF(x(t)) g(t),
Σ
1scervee B
B BynM
TE(1
Σ
K
1scem
(13)
B₁
27
B
k=1
A=1
k=1
E(F(x(()) a T (F(S) E(F(x(())) + + (FF((())) g(t).
K Σ
1s
B B/NMy
(E(
K
Lscesmva
11
B+
2T
B₁
k=1
2 B(F(x(t)) + 0 (F(S) - E(P(x(t)) T
2B /nM, ((IF(x(0)) - -(0))1)))(00)))
BVM, T
B
E(I Σ
K
1
ssoon l15))
B
km
TB BB/nM
TB rBVMM
2 E(F(x(0)) a (f()) ((F))E((((())))
2LT
T
(24)
where the second inequality follows from the Young's inequality.
29

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
By rearranging the (24), we show that
((S) ((F(x(t++1))
BBMnMj
rB rBynM,
5 - ( s...
2L.
T2
(TBYUM,
rB
( ) (f(S) - -(((((()))
E
2LT
T
(1 4) (I(S)) - E(F(X()) + (TB
rB ~BBYMM
2LT
T2
S - -(((s + rBynM rBy
20L of
Finally, we have that
B(F(x(T + 1))
BB/nM, TB TMM 20l
2 (1 (1- (1 (1- (1)
[(()
of 01) 1($) rB rBynM, rBVnMM
201. aT
where the final inequality follows from (1 -)T² $ e when 233. Therefore, when L = T 2.
we have that
B(F(x(T + 1)) 2 (1-6 ((S)) (1-)-) 2rB 2rBynAM nMy aT
2: When the set function f + R2 is monotone and (7, -weakly submodular, from the Theorem 2, we can show that
E(F(x(t+ 1))) E(F(x(t)) + 2. 1(() 3(1 7) + + E(F(x(t)) rB rBV rB rB/MM
(25)
T
2LT
By rearranging the (25), have that
(7²((S) (8(1 7)
) E (((((t++1)))
(1 8(1 ((1-))++} -1) (7²](S) (B(1-)) (0(1-))+ + (T (TBY
TB ~BM T
(3(1 (8(1- 101--) 7) + +22)
T
2LT
S..
$ (1 B(1 (11-))++]
+ (BB/nMM
rB /B/rMM T(3(1 - + +
2LT
T
< (1 3(1 - 7) + 72 f())
rBvrMM,
+BBnMMs
T
2L
T
Finally, we have that
(8(1 7)) + (F( +1)
2 (1 (1- (1 3(1 7) 2
TBVnM TB BBMMM,
(r) (²)2)(()++
T
2L
T
rB nMM
TB rBM
- (801)))))) ((S)
21.
where the final inequality follows from (1 8(1-7)+7² f - when T 7 3.
30

---

Nt Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
Algorithm 2 Rounding Without Replacement
Input: Point (PI,...,PP' PK) I An, where Ps: (vk.... ........Pi. P and Σ Pk for any E [K], Partition
(Vi...., Dx) of set where V4 == {u ( , for any [K], Budget {BI,..., B8k
1: Initialize S = 0:
2: for i .,..... K do
3: P
4: for i 1...., Bg do
5: if 6 then
6: Sampling number N1 from [mx] according to the probability Pr(NN m) P% for any [ngl:
7: else
8:
Sampling number Ng from [л*] - ..1....,NN..11 according to the probability Pr(NV = m)
T-P for any
PC
m [mg] (Ni....,NN-1)) 12-1)):
9:
end if
10: Set = S u fu6 No and = P P p/
No.
11:
end for
end for
Return S;
Therefore, when L T 2. we have that
(2 (2(1---((0-))++ 7(1 - B) + 72
Br /nAd 1(5) T(>(1 - (3) -3)+ +2)
((((x(++1))
Remark 12. IfT = L O and S is the optimal subset of problem (1), we can show that, when the objective function monotone a- weeklly DR-submodular or (7, (7.3)-weake wweklly submodular, our Multinouli-SCG algorithm can attain value of
(1-e ((() - e or (220---000~> ((1-))+
((()) Note that, during the process of O (v iterations, if L - O O Tv
due to Remark 8, Multinoulli-SCG only requires evaluating the set function O n times.
D.2. Rounding Without Replacement
In this section, aim present effective rounding method for proposed Multinoulli Extension F when its original set function f is monotone.
Given the second point of Theorem I, we know that when the set function f exhibits monotonicity, its Multinoulli Extension F is also monotone. Therefore, it can be deduced that the optimal value of the relaxed problem (4) must be attained at the boundary of II Ang. Therefore, this section primarily concentrates on how design more effective rounding method for the points the boundary of II Any The specific details presented in Algorithm 2.
The core of our our proposed Algorithm 2 lies in the Line 8, that is, instead of independently sampling according to each probability vector Pí.- we take into account the elements previously selected within the same community, namely, (u:h1 ..... U '3. As a result, we can prove that
Theorem 6. For any point (Pi,..., pK) at the boundary of the domain I Ang, ie., ||al]] for any k [K], if the set function f is monotone, we can show that the subset S returned by Algorithm 2 satisfies:
for any le E [K], [S] BB;
E{((S)) 2 F(p...... .Pk) where F is the Multinoulli Extension of f-
Proof. The first point Theorem easy to verify. We mainly focus on the second point.
31

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
At first, fixing a [K] and a [ng]. we firstly prove that, when S (1f (k, < (k: b)}, the following inequality holds:
E No (f(S () 1){$) 2 Ee-Muniiss) (F(SU
(26)
In order to verify (26), we first show that
(A(SU tok ))
N
"
(1
E
(--p((S
me(n)]- (Ni..nNb_1)
P
E
(PF((( +
E
(EES(SU((T)))
1 1- mElugl-fe -NN
(27)
melngl-(NN...nl (Ni...N
P
Σ
(1))())) +
E
1 P
mE[ng] - -Ni
(NN.l..
PP((S) +
E
((S((()t))))
me[na]-
1
where the first inequality from the monotonicity of f. Then, also have that
(F(SU(e))/5
Ee-Muli(ps))
Σ
(SSU
mE|ngl
Σ
(pm (())())
mE(Mel (N-1) (SSU
E
(28)
(E(NI
= =Pf(S) +
Σ
(ox (SU
m (N
With (27) and (28), get the result of (26) Therefore, if we start by the final subset S and recurrently apply the (26), we can get E ((()) F(pI....,kkk)
E. Stationary-Point Strategy for Mutinoulli Extension
E.1. Proof of Theorem 5
In this section, we prove the Theorem 5. Firstly, we prove lower bound about (PP.....,PPA PK), VF(p..... .F.......,PP .Px))) for any point (pi....,PP) PK) I1 Any that is to say,
Theorem 7. When the set function f 2 R4 a-weakly DR-submodular, for any point (Pi...., .P) E I Any the following inequality holds:
(PI (P.....Kk) VF
..... Pk) 2 F(pp....,,Pe
(29)
where a E (0, 1). Similarly, when the set function f 2 + R4 is B-weakly submodular from above, for any point (pi....,Pk) E I Anw we also can infer that
(P PK), WF 2 .F......... .P),,
where 3 2
32

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
for any & [K]. Then, from the first point of Theorem and the fifth Proof. At first, assume each P& = (p -. .P equality in Eq.(13), we have that
OF k
E of Mutii (I(vF) ((b te()))
(P . pk)
Bb
(1(131 ((FI) (6)))
Pi(ef(pa) ))
Bk
Σ
II (kk))
As result, have that
(pI,....PPk)) .K), VF(P...... pk)
nk
OF
Pk
(P1 (PI..... Pk)
Opk
K nie
E ol Mptiitpp (f(vF) U(BBYAA fc)1))
th B
1=1 mml
(1OF11ADHH te)1)
II Pr(e prte((ps) )
Pk Bu
Σ
k=1 m=
(EV
n1
(1 fel))
II Pr(e)(pp) )
Pr(ek P4 BB
Σ
(R.6))(().1)
K
B
Pr(uf Th p
E
(F(FIURRAMM 1cf1)
II Pr(ef(pp))
m=l
BB
Σ
Σ
(1 (
((.D)) (eft Pr(u)"lss)
II Pr(e (ps) (k.
k=1
m=1
of (E
K
K Br (Ced (c))
Bb
Σ
II Pr(e k=1d=1
km
((c2) UARADAAA
(ABAeaa fd11)
B&E Muln(pp!
(((b) tef))
Muttipp))
where the fourth equality follows from Pr(v [p)) = pi the seventh equality comes from et Multi(pa) and f(0 0 for any B C V as well as the final equality follows from that each et, is independently drawn from the multinoulli distribution Multi(ps).
f is 3-weakly submodular from above, we can show that
K
(0f)) s <<(1(U 1 -
( ((bb))))))))))))
s <Bf( U -
where the final inequality follows from f(0) (Note that we define f:2º RR))
33

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
As result, when is f-weakly submodular from above, have that
(pI..... (PI....,Pkk) VF(p....... ........)))
(
(RBD))AA (elt)
E Muntrtps
k= b=1
(5 (UUEE)) upi (F
S 3B Multi(pp
Note that a a-weakly DR-submodular function automatically satisfies the conditions for being -weakly submodular from above. Thus, we get the (29).
Merging Theorem into Theorem also can get that
Theorem 8. When the set function f 2 + R is monotone and o--weakly DR-submodular, for any subset S within the partition constraint of problem (1) and any point (pi...., ...))) E II Any the following inequality holds:
k Σ
Isnv - (pp......Pxk VF (P ........p) 2 af(()) -aa+ B
Similarly, when the set function f 2 + 1R is monotone and (7/ wwekkly submodular, for any subset S within the purtition constraint of problem (1) and any point (PI....,PK' II Anw also can infer that
K 1
........pp)))........)) 1snve - (pp.....pkk) ......PP)) VF VF
.i...... Pk) 2 - (1
P1 . pk).
A=1
From the definition of stationary point, we know that if (PI,...., PK) E II A., is the stationary point the domain I Any for any point E II Ann.
(P (y- PK). VF Pp........KK' .K) 5o.
(30)
Also, for any S within the partition constraint of problem (1), we can easily show that Σk= 1 Isni E II An. such that we know that, for any S within the partition constraint of problem (1),
B,
1sny (pi..... pK) VF VF PI......P Bu
S 5.
Therefore, when the set function 2 - R4 is monotone and a-weakly DR-submodular, we have that af(SS)
(a + 2)F (pI.....
PK) < 0 such that F [I..... .p.....,pk) 2 a² f(S) where S* is the optimal solution of problem (1). Similarly, when the set function f 2 + R2, is monotone and (7, weakkl submodular, we have that 7² (8 +
3(1 -1) ((1-7)++²)) +>2)
(p....., (p)) .p....,p)) < such that F (pI....,Pk)) F
> 3+3 - f(S*).
E.2. Stochastic Gradient Ascent for Multinoulli Extension
In general, a simple strategy is to initially apply the well-established Gradient Ascent (GA) method to maximize our proposed Multinoulli Extension F, and subsequently, to finalize our selection by rounding the resulting continuous solution. However, the implementation of GA often requires accurately computing the gradients of F, which typically computationally intensive. Fortunately, the first point of Theorem 1 indicates that it is feasible to sample a sequence of random elements to construct an unbiased estimator for each Of 8p (p....., Px) where (P....., Px) E k== An. Specifically, when each
34

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Selection over Partition Constraints
Algorithm 3 Stochastic Gradient Ascent for Mutinoulli Exxennson(Mutttioolll-SAAAA
Input: Batch size L, step size number of iterations T, partition (Vi..... Vk} of set V where V\ (u...... 2 and
the set function ʃ
1: Initialize x(1) = (I) Px (1)) E I Anii
2: for .. do
3: Generate subset St by rounding x(t);
4: Compute the estimator V Fx((()) based on (q.(31);
5: Set y(t + = x(t + (x(()t))));
6: x(t 1) = arg mi = Amk || y(t 1)
7: end for
8: Return = arg max f(S:):
(1) is independently drawn from the multinoulli distribution Multi(p;) for any le [K], [ng] and I [L), we estimate 8F 3pt .Pi,....Pa.. as:
OF
B L
(1(WF) E=1
Ua. te)()))
P Opk m
PK)
=
(31)
By merging this stochastic gradient (31) into the standard GA method, we can derive a stochastic variant of gradient ascent method for our proposed ME, as detailed in Algorithm Furthermore, based on the previous results of Theorem and Theorem we also can verify that:
Theorem 9, When the set function f 2 + 1 is monotone and a-weakly DR-submodular, if we set the batch size = (1), the subset S output by Algorithm satisfies:
a² ) 1(5))
K nB²M²
E(f(S))
nT
where S* is the optimal solution of problem (1),B max BR is the maximum budget over the K communities VKk and M maxscv,evvis (f(e)S)). Similarly, the function f 2 - RR+ is (7, -weekly monotone
submodular and L = (1), the returned subset S of Algorithm 3 satisfies:
72
8K 7 1
2nB²M²
B(f(S)) 2 (3
13+3(1 3( -) +72 f(5*) )
Remark 13. Theorem 5 shows that, when the set function f is monotone and a-weakly DR-submodular, if we set O vTT the subset S output by Algorithm 3 satisfies:
a² E B(f(s)) 2 1 a f(S") 0 V
where S* is the optimal solution of problem (1), which implies that after (L)/²² iterations, the subset output by our proposed Algorithm can attain T OPP - where OPT is the maximum value of problem (1). Similarly, when f is (% Bewkelllyy monotone submodular, if we set O v the subset S output by Algorithm 3 satisfies:
E(f(S)) 2 3+ 3(1 7)
F(S*) 0
which also means that, after O(+) iterations. Algorithm also can achieve
) OPT e. Note that, during
the process of ((1) iterations, Algorithm only requires evaluating the set function O ( times we set the step size T= 0(1.
35

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
In the following part, we prove the Theorem 9. At first, we give easy-to-verify lemma about the upper bound of gradients of our proposed Multinoulli Extension F.
Lemma Given a monotone set function f 2 - RR+, if we denote the maximum marginal value of f as Mf maxscv,evvss (f(el))). we have that, for any [K], m [nc]]
OF 0p%
(pI
pk) S BMf
where (Pi...... pK) E II Ang and = max By is the maximum budget over the K communities (M...., VK}- Similarly, we also can infer that the gradient estimation (11) also can be bounded by f..., any positive integer L,
OF 0pp
(PI.... pk) & BM,
With this Lemma 5, we then prove the Theorem 9.
Proof. Let S denote the optimal subset of problem 1. Then, from the Line 6 in Algorithm 3, we know that
K 1 S-
K
1s-
x(t + 1) -
< y(t
+
Bx
k=1
1 1s
x(t
F
k=
K
xt)
1
+ +
FF(((t)),
Σ
n²
[F(x(())|
Bb
Bb
2
k=1
K
K
<
xtt)
19-ri
+2n
(F((((t),,(
Σ
1s-nvz
+ +nmnB2M3
Bb
Bb
where the first inequality follows from As a result, we have that
Σ
k=
18+nve Be
E
l===
Any and the final inequality comes from Lemma 5.
K.
E
x(1 1)
1 1v
5 E
x(1)
1s
21BB
FF(x()),x()
- Σ
18-0vz
+ +nInBBM?
Bg
B&
2
1s
( (B((F(((0))(()) x(1) - Σ
1s
)) + +
x(1)
+ 27/
B
Bk
1=1
k=1
x(t)
K
1s
+ 2
VF(((t),x()) - Σ ) +
K
1s-mi
+
B
BB
(32)
Then, if 1): the set function f 2 + R4 is monotone and w-weakly DR DR-submodular, from Theorem 8 and (32), we have that
E
x(t
(1++1)
Σ
K
1s
E E
(t)
K
1s
2
2nF
(
K VF(((()),
Σ
1s x(1)
12nBBM
B₁
Be
k=1
k=
2
k=1
K
2
$
E
x(t)
Σ
1snn
2n (0((((())
(a a ) + +1BBBBMG
By
k=
2
36

---

Multinoulli Extension: A Lossless Yet Effective Probabilistic Framework for Subset Sclection over Partition Constraints
As result, have that
r 2n Σ (ff(s)) (a - a
K
K
2 +Tn
F(((()) E
1
s-n
1s-nve
x +
1)
E
x(1)
+
Bn
Due to that ((f()))) = (E)()x())) from Algorithm infer that
Σ 1=
((F(x(t)))
E(f(s))
T
1 a ((8")
a²
E
+1) - E k=1
1s
Bx
1
nB²M3
2n/2(a + =
11 2(a + a/)
a²
K
nB²M3
1 + ((8*)
1|
1genve 2
where the final inequality follows from + 1
2 2 and
[T(++) -
S 2(|x(T + +1)12 +
Be 2
1genik Bu
[ -
<4K. 4K.
Lk=1
Furthermore, 2): if the set function f: + RR is monotone and (7,8) (7, ()eaklyy submodular, also can show that, from Theorem 8,
21 (2115)--00-00----22)000)))) S x(T + 1
Σ
1
1v By
-E
x(1)
Σ
1v.
+T nB M2.
By
k=1
Finally, we have that Due to that (E(((S))) E(F(x(()) from Algorithm 3, we can infer that
T
E(F (x)))
B(F(S)) 2
T
22
E X(T +1) -K
Σk=1
13 Bx
2
nB
8 + B(1 7) + +72
1(5)) (B + 3(1 7) + +22)
17
2(B + 3(1 +
22
8K
2nB32 M??
((S*)
3 + B( - +)+
TT/
1) 7
1g-ny l' S 2([|x(T + +1]1 1012+1/EX, +||EX= B2
1s 2
where the final inequality follows from
x(T + 1)
Σズ=
S
4K,
Br
2
2 and ((1 7) + 2 2 3 (Lemma B.1 in (Thiery & Ward, 2022)).
37


Reviews:
[{"review_id": "Nzf1Gc61P2", "reviewer": "Reviewer_ua4p", "summary": "This paper considers the problem of subset selection subject to partition constraints. The objective is not fully submodular, but instead displays some degree of submodularity, e.g. is weakly submodular. Existing work on this problem relies on distorted local search methods, but these works have some shortcomings because they rely on unknown parameters such as the weak submodularity ratio, and have high query complexity (depending on a paramter $\\epsilon$). To address these issues, this paper proposes the Multinoulli extension, which is a continuous extension of a submodular set function like the multilinear extension, but has some advantages for weakly-submodular objectives. The paper further proposes and analyzes algorithms for their problem using this extension.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for your careful reading and constructive feedback. We are grateful for the time and effort you have dedicated to reviewing our manuscript. In what follows, we will address some of your concerns in **Questions** and **Weaknesses**.\n\n--------------\n\n**Weaknesses**:\n\n--------------\n\n> **W1: The multinoulli extension is advantageous specifically for weakly submodular functions, and so doesn't seem useful to those who are primarily concerned with submodular objectives.**\n\nThank you very much for your question. \n\nFirst, it is important to note that when  $\\alpha=\\gamma=\\beta=1$, the $(\\gamma,\\beta)$-weakly submodular or $\\alpha$-weakly DR-submodular functions considered in this paper will degenerate into standard submodular functions. Thus, the class of set functions we study is a broader category that includes standard submodular functions as a special case.\n\nMoreover, when $\\alpha=\\gamma=\\beta=1$, the approximation ratio $(1-e^{-\\alpha})$ or $(\\frac{\\gamma^{2}(1-e^{-(\\beta(1-\\gamma)+\\gamma^2)})}{\\beta(1-\\gamma)+\\gamma^2})$ yielded by **Multinoulli-SCG** will equal $(1-1/e)$. This means that our algorithm can guarantee an optimal $(1-1/e)$-approxiation for submodular maximization over partition constraints, which is consistent with the state-of-the-art algorithms for submodular maximization problems.  \n\nAs a result, our proposed **Multinoulli-SCG**  algorithm not only offers advantages for weakly submodular functions but also guarantees the same approximation performance as the best existing algorithms for submodular maximization.\n\n--------------\n\n**Questions**:\n\n--------------\n>**Q1:Could you give more detail about the issues with the multi-linear extension being used for weakly submodular functions?**\n\nThank you very much for your question.\n\nAt first, it is important to note that we have provided a detailed introduction to the multi-linear extension in Appendix A.1 (lines 680-714), where we also discussed the main challenges in applying the multi-linear extension to weakly submodular functions\n\nHere, we will briefly restate the key issue.\n\nBefore that, we call the defintion of multi-linear extension, that is,\n\nFor a set function $f:2^{V}\\rightarrow R_{+}$ where $|V|=n$ and $V:=[n]$, we define its multi-linear extension as \n\t\\begin{equation}\n\t\tG(x)=\\sum_{\\mathcal{A}\\subseteq V}\\Big(f(\\mathcal{A})\\prod_{a\\in\\mathcal{A}}x_{a}\\prod_{a\\notin\\mathcal{A}}(1-x_{a})\\Big)=E_{\\mathcal{R}\\sim x}\\Big(f(\\mathcal{R})\\Big),\n\t\\end{equation} where $x=(x_{1},\\dots,x_{n})\\in [0,1]^{n}$ and $\\mathcal{R}\\subseteq V$ is a random set that contains each element $a\\in V$ independently with probability $x_{a}$ and excludes it with probability $1-x_{a}$. We write $\\mathcal{R}\\sim x$ to denote that $\\mathcal{R}\\subseteq V$ is a random set sampled according to $ x$. \n\nFrom the previous definition, we can view multi-linear extension $G$ at any point $x\\in[0,1]^{n}$ as the expected utility of independently selecting each action $a\\in V$ with probability $x_{a}$.  With this tool, we can cast the previous discrete subset selection problem (1) into a continuous maximization which learns the independent probability for each element $a\\in V$, that is, we consider the following continuous optimization:\n\\begin{equation}\n\t\\max_{x\\in[0,1]^{n}} G(x),\\ \\ \\text{ s.t.}\\ \\  \\sum_{a\\in V_{k}}x_{a}\\le B_{k},\\forall k\\in[K]\n\\end{equation}where $G(x)$ is the multi-linear extension of $f$.\n\nIt is important to note that, if we round any point $x$ included into the constraint of the previous multi-linear maximization problem by the definition of multi-linear extension,  there is a certain probability that the resulting subset  will **violate** the partition constraint of the original discrete subset selection problem. \n\n-------------------------------\n> **Q2:  It was mentioned, and a citation was provided, that the multi-linear extension has issues when being used for weakly submodular objectives. Because this is an important problem that motivated the paper, I think that they should go in to further depth in the main paper about why this is the case.**\n\nThank you very much for your insightful question.\n\nIndeed, the limitation of the multi-linear extension when applied to weakly submodular functions is a significant motivation for our work. Due to space constraints, we have detailed these limitations in Appendix A.1, where we discuss the specific challenges in using the multi-linear extension for weakly submodular functions, as shown in the answers in **Q1**.\n\nGiven the importance of this issue, we will add a small subsection at the end of Section 3 to further discuss the limitations of the multi-linear extension and how our proposed multinoulli extension overcomes these challenges. This will provide a more detailed explanation directly within the main paper, addressing your concern more comprehensively.", "claims_and_evidence": "I did not notice any problematic claims.", "methods_and_evaluation_criteria": "Yes", "theoretical_claims": "I did not thoroughly check theoretical claims but I did not notice any problems.", "experimental_designs_or_analyses": "No issues", "relation_to_broader_scientific_literature": "This paper is of interest to those in the submodular optimization community. In particular, there are many papers exploring weakly-submodular optimization, and since this paper proposed a new continuous extension, members of that community could potentially also build upon the new extension.", "essential_references_not_discussed": "It was mentioned, and a citation was provided, that the multilinear extension has issues when being used for weakly submodular objectives. Because this is an important problem that motivated the paper, I think that they should go in to further depth in the main paper about why this is the case.", "other_strengths_and_weaknesses": "Strengths\n- Contributes to the area of weakly submodular optimization, which is of interest to the ML community\n- Proposes a new continuous extension of submodular functions, which may be of use in other problems.\n\nWeaknesses\n- The multinoulli extension is advantageous specifically for weakly submodular functions, and so doesn't seem useful to those who are primarily concerned with submodular objectives.", "other_comments_or_suggestions": "No", "questions_for_authors": "- Could you give more detail about the issues with the multilinear extension being used for weakly submodular functions?", "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": "WtvWFoU9Zq", "reviewer": "Reviewer_WbSo", "summary": "The paper considers maximization of a monotone close-to-sumodular objective $f$ over a partition matroid, where the notions of approximate submodularity considered are weak DR-submodularity and weak submodularity.  The authors introduce a novel continuous extension for this problem, called Multinoulli Extension (ME). They study its properties showing that it has similar nice properties as the well-known multilinear extension, but with the advantage that it allows lossless rounding on partition matroids for any set function. They also propose a novel variant of the continuous greedy algorithm, called Multinoulli-SCG, adapted to the proposed extension, and which employs the existing path-integrated differential estimator to estimate gradients of the ME. The resulting algorithm matches the best existing approximation guarantees for both classes of functions considered, with less function queries under some settings.  Experiments comparing the proposed method to existing ones are provided on video summarization, bayesian A-optimal design and coverage maximization applications.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful reviews. We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. In the following, we will address the concerns you have raised in **Questions**.\n\n---\n\n**Questions**:\n\n---\n\n>**Q3:Why can we assume that $x(T + 1)$ is on the boundary of the domain (see details in \"Theoretical claims\")?**\n\nThank you very much for your question. \n\nFirstly, this paper primarily focuses on monotone set functions $f$. Secondly, as noted in Theorem 1 (2), we have shown that when $f$ is monotone, its multinoulli extension is also monotone. Specifically, for any two feasible vectors $(x_{1},\\dots,x_{K})$ and $(y_{1},\\dots,y_{K})$, if $x_{i}\\ge y_{i},\\forall i\\in[K]$, then $F(x_{1},\\dots,x_{K})\\ge F(y_{1},\\dots,y_{K})$. Thus, for any feasible vector \n\n$(x_{1},\\dots, x_{K})$, we have  $F(\\frac{x_{1}}{u_{1}},\\dots,\\frac{x_{K}}{u_{K}})\\ge F(x_{1},\\dots, x_{K})$ \nwhere $u_{i}=||x_{i}||_1$ for any $i\\in[K]$. \n\nNote that ($\\frac{x_{1}}{u_{1}},\\dots,\\frac{x_{K}}{u_{K}}$) lies on the boundary of the constrained domain $\\prod_{k=1}^{K}\\Delta_{n_{k}}$. \n\nTherefore, even if the output of Algorithm 1 is not on the boundary, we can first normalize this output vector to the boundary and then use Algorithm 2 to round the normalized output vector. This process will not decrease the function value for the monotone set objective function $f$. This is  why we assume $x(T+1)$ is on the boundary-because we can always increase the function value by normalizing the output vector.\n\n> **Q2: Why is it an issue to select the same element when rounding as discussed in Remark 9? Isn't the resulting set simply a union of the elements obtained. What is the motivation for using a rounding-without-replacement method?**\n\nThank you very much for your question. we will explain Q2 with a simple example.\n\nConsidering $V=[3]$ and we will select at most 2 elements from $V$. Given $p=(1/3,1/3,1/3)$, if we use the definition of multinoulli extension to round\n$p$, we might end up selecting element 3 twice. This would result in a final subset containing only element 3. Since this paper focuses on monotone set functions $f$，we naturally know that randomly adding element 1 or element 2 to the resulting subset (which contains only element 3) will increase the function value without violating the constraints. This illustrates the issue of selecting the same element over multiple selections.\n\nTo address this, we propose a rounding-without-replacement method. This ensures that the final resulting subset contains the maximum number of distinct elements, thereby avoiding the pitfalls of multiple selections of the same element and maximizing the function value more effectively.\n> **Q1: Would using a similar implementation of the Hessian-vector product as the one described in Section 4.1 of (Karbasi et al., 2019) also lead to better computational and memory complexity for your proposed algorithm? If yes, what is the resulting complexity?**\n\nThank you very much for your suggestion. This is a very good question.\n\nWe have also considered the same question. However, we noticed that in Section 5 of (Karbasi et al., 2019), when dealing with discrete submodular maximization, they did not use the Hessian-vector product described in Section 4.1. Instead, they employed a Hessian estimation method similar to the one used in our paper. Therefore, we suspect that the Hessian estimation method in Section 4.1 of (Karbasi et al., 2019) may not be directly applicable to our multinoulli extension. \n\nThe primary issue with using the Hessian-vector product described in Section 4.1 of (Karbasi et al., 2019) is that it involves computing $\\nabla\\log(p(z;y))$, which may require differentiating some $log(p)$, where $p\\in(0,1)$  is a parameter of interest.  Note that $(log(p))^{'}=\\frac{1}{p}$ and $\\frac{1}{p}$ is unbounded on the interval $(0,1)$. Therefore, we thimnk directly applying the Hessian-vector product from Section 4.1 of (Karbasi et al., 2019) to our multinoulli extension might violate the bounded gradient and smoothness assumptions in (Karbasi et al., 2019).\n\n----\n\n**Other Comments Or Suggestions:**\n\n---\n\nThank you very much for your comments and suggestions. We will carefully address all the proposals and correct any typos in the final version.\n\n----\n\n**Claims And Evidence:**\n\n----\n* We will add a detailed remark after **Remark on Table 2**, specifically after line 153, to discuss the comparison of query complexities between multinoulli-SCG and distorted local search under different values of $n$. Moreover, in this additional remark, we will also explicitly point out that the query complexity of Distorted-LS-G uses a different error term $\\epsilon^{'}$, which is related to $\\epsilon$ of Multinoulli-SCG by the transformation $\\epsilon' = \\epsilon / OPT$.\n* We will **remove** the inappropriate claim from \"Our Contributions\" in RHS in line 94, i.e.,\" match the information-theoretic lower\"", "claims_and_evidence": "The following claims are inaccurate or require more evidence. \n\n1 - Claim: The proposed method uses $O(1/\\epsilon^2)$ function evaluations. The best existing method, Distorted Local Search with guessing (Distorted-LS-G), uses $\\tilde{O}(1/\\epsilon^6)$ and $\\tilde{O}(1/\\epsilon^3)$  for weakly DR-submodular and weakly submodular functions respectively. \n\nThese claims ignore other non-constant parameters of the problem such as the size of the ground set $n$, the rank of the matroid $r$, and the optimal value OPT, which can be larger than $O(1/\\epsilon)$ and should not be ignored. Moreover, the $\\epsilon$ appearing in the query complexity of Distorted-LS-G is not the same as the one for Multinoulli-SCG. The former is equal to $\\epsilon' = \\epsilon / OPT$. This should be clarified, e.g., by using a different notation $\\epsilon'$ for Distorted-LS-G.\n\n2 - Related claim: The query complexity of the proposed method is better than Distorted-LS-G.\n\nIt should be clarified that this is only true under some settings: if $n < r OPT^6/\\epsilon^4$ for $\\alpha$-weakly DR-submodular functions, and if $n < r OPT^3/\\epsilon$ for $(\\gamma, \\beta)$-weakly submodular functions. Both conditions are likely to hold in practice, but not always. It would be good to discuss also in each of the experiments presented if these conditions hold. \n\n3 - Claim: the number of function evaluations required by the proposed algorithm matches the information-theoretic $O(1/\\epsilon^2)$ lower bound given in (Karbasi et al., 2019; Hassani et al., 2020). \n\nThis claim is not correct. The lower bound given in (Karbasi et al., 2019; Hassani et al., 2020) is on the number stochastic gradient calls, not on the number of function calls. Either remove this claim, or show that this lower bound also applies to the number of function calls in your setting.", "methods_and_evaluation_criteria": "Yes, the proposed method makes sense and builds on well known techniques.\nThe evaluation based on approximation guarantee and query complexity are also the usual evaluation criteria for this problem. Applications are also standard applications for the problem.", "theoretical_claims": "I verified the proofs of Theorems 1 and 2 but did not check those of Theorems 3–6.\n\nThe main issue is that the cumbersome notation makes the proofs difficult to follow. I strongly encourage the authors to simplify the notation. \n\nAnother concern is the assumption in Theorem 6 that $p_k$ is at the boundary of the domain, i.e., $\\\\|p_k\\\\|_1 = 1$ for all $k$, which is not well justified. The input of Algorithm 2 is expected to satisfy this assumption. Algorithm 2 is used to round the solution $x(T + 1)$ at the end of Algorithm 1. I don't see why $x(T + 1)$ is necessarily at the boundary of the domain. When the function $f$ is monotone, the gradient of the ME is non-negative, but not necessarily the estimator $g(t)$, so it's possible that $|S(t) \\cap V_k| < B_k$ in some cases, and thus $x(T + 1)$ won't be at the boundary. \n\nOther minor typos/issues: \n- In the proof of Theorem 1, in the third equality in Eq. (13) (line 969-970), the third sum should be over $e_k^{\\hat{b}_1}$.\n- In the proof of Theorem 1, $e(X, Y, p_k, \\hat{p}_k)$ should be just a function of $X$ and $p_k$.\n- In the proof of Theorem 2, Eq. (20) is missing sums over $k$ and $b$.", "experimental_designs_or_analyses": "Yes I checked all experiments. The experiments are mostly well designed, cover three cases ($\\alpha$-weakly DR-submodular, $(\\gamma, \\beta)$-weakly submodular, and a submodular function). I like also that one of the experiments (maximum coverage) was specifically designed to show the case where Greedy and Multinoulli-SGA get stuck in a local minimum. \n\nIssues to address:\n\n- Residual Greedy and Multinoulli-SCG are repeated 10 times, while Multinoulli-SGA and Distorted-LS-G are repeated 5 times. Using different number of repetition for different methods is a not a fair comparison. \n\n- In the video summarization experiments, the DPP objective is defined as $f(S) = \\det(I + X_S)$. The DPP objective does not typically include identity, a small diagonal perturbation can be added to ensure\nstrict positive definiteness of the kernel matrix. Is there a missing scaling factor here, i.e., $f(S) = \\det(\\delta I + X_S)$ for some small $\\delta > 0$?\n\nOther minor issues/suggestions: \n- Include standard deviations for the reported results in Table 3 & 4, not just the average.\n- Include what are the parameters $\\alpha$ and $\\gamma, \\beta$ in each experiment. \n- For the maximum coverage experiment (Appendix B.2): \n\t- clarify what you mean by Residual Greedy oscillates between optimal solution and local maximum, is it across different runs?\n\t- use a different notation to denote the small weight for $A_i$'s to avoid confusion with $\\epsilon$ of the error in the optimization guarantee.\n\t- use a different table to present the results for the Bayesian optimal design experiment.", "relation_to_broader_scientific_literature": "Existing methods for solving the problem considered either have a worse approximation guarantee, or have a worse query complexity under some settings (see Tables 1 & 2 in the paper and \"Claims and Evidence\" above).\n\nThe proposed Multinoulli extension has similar nice properties as the well-known multilinear extension, but with the advantage that it allows lossless rounding on partition matroids for any set function. Its disadvantage is that unlike the multilinear extension, the ME is specific to partition matroids. Nevertheless, I think this might inspire the development of other continuous extensions that incorporates constraints within the extension to allow for lossless rounding. \n\nThe proposed algorithm is a variant of the continuous greedy algorithm, adapted to the proposed extension, and which uses the existing path-integrated differential estimator to estimate gradients of the ME.", "essential_references_not_discussed": "The main motivation of introducing the Multinoulli extension, instead of using multilinear extension, is that it allows for simple lossless rounding. To put things more in context, it would be good to mention that contention resolution, one of the rounding schemes for general matroid used with the multilinear extension, can still be used for $\\alpha$-weakly DR-submodular functions, but it loses a factor of  $\\alpha ( 1 - 1/e)$, as shown in (Gong et al., 2019).", "other_strengths_and_weaknesses": "Already highlighted above.\n\nOther weaknesses:\n- The code to reproduce experiments is not provided", "other_comments_or_suggestions": "- Clarify in the problem setup that the partition groups are assumed to be known, as opposed to the usual assumption in submodular optimization over matroids, that we have access to the matroid via oracle calls only.\n\n- As mentioned, the notation used is overly cumbersome. Simplifying it would significantly improve the readability of the paper. For example, why do you use $\\hat{k}$  and $\\hat{b}$ instead of simply $k$ and $b$ in the definition of the ME?\n\n- The definition of $\\Delta_m$ is not the standard definition of an $m$-dimensional simplex (the standard definition has $\\sum_i x_i = 1$). Similarly, calling $p_k$ a \"Multinoulli distribution\" is also inaccurate if $\\sum_m p_k^m \\not = 1$.  Either use different names for $\\Delta_m$  and $p_k$ or use the standard definitions for both and define $p_k$ to be the probability on $\\mathcal{V}_k \\cup \\\\{v_0\\\\}$, where $v_0$ is a dummy element that can be added to all groups, which corresponds to not selecting any element in the group.  I recommend the latter option, as it would simplify the notation elsewhere in the paper too.\n\n- Discuss the motivation for using the path-integrated differential estimator, instead of directly estimating the gradient itself. \n\n- Add a discussion on how challenging would it be to generalize the presented results to general matroids.\n\n- Explicitly explain in the main text the simple way to round $x(T + 1)$ based on the ME. \n\n- Use a different notation, e.g.,  $\\epsilon'$, instead of $\\epsilon$ for Distorted-LS-G. \n\n- Shorten the abstract. According to instructions, it should be ideally between 4-6 sentences long. \n\n- Use group or block to refer to $\\mathcal{V}_k$ instead of community, as these the standard names used in the literature.\n\n- One line 301-303, 1st col: the statement there is inaccurate; the inequality $\\langle y, \\nabla G(x) \\rangle \\geq G(y) - G(x)$ only holds for $y \\geq x$ for the multilinear extension. \n\n- Restate theorems in the appendix for convenience for the reader\n\n- In Remark 7, Algorithm 2 should be Algorithm 1.", "questions_for_authors": "1 - Would using a similar implementation of the Hessian-vector product as the one described in Section 4.1 of (Karbasi et al., 2019) also lead to better computational and memory complexity for your proposed algorithm? If yes, what is the resulting complexity?\n\nIf this can lead to an improved complexity for the proposed algorithm, for example by reducing the number of functions calls by a factor $n$ (as in the case in (Karbasi et al., 2019)), it would strengthen the results of this paper. \n\n2- Why is it an issue to select the same element when rounding as discussed in Remark 9? Isn't the resulting set simply a union of the elements obtained. What is the motivation for using a rounding-without-replacement method? \n\n3- Why can we assume that $x(T + 1)$ is on the boundary of the domain (see details in \"Theoretical claims\")?", "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": "XS7iQrfivv", "reviewer": "Reviewer_qooM", "summary": "The paper introduces a novel algorithm called Multinoulli-SCG for solving the subset selection problem under partition constraints, particularly focusing on close-to-submodular objective functions. The core of the Multinoulli-SCG algorithm is an innovative continuous-relaxation framework named Multinoulli Extension(ME). Unlike the traditional multi-linear extension, ME provides a lossless rounding scheme for any set function, not just submodular ones.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your detailed and insightful reviews. We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript. Your feedback is invaluable to us. Below, we will respond to the concerns you have raised in **Weaknesses**.\n\n------------------------\n\n**Weaknesses**:\n\n---------------------\n> **W1: The paper could benefit from a more thorough analysis of the scalability of the proposed algorithms. As the scalability of the algorithms are improved compared to prior continuous algorithms theoretically, evaluating the algorithms on larger datasets would provide deeper insights into their performance in practice.**\n\nThank you very much for your constructive suggestion.\n\nScaling up the proposed algorithms to larger datasets and a wider range of subset selection tasks is indeed one of our long-term goals.  For example, similar to [1,2], exploring how to use distributed architectures to accelerate our algorithms or handle extremely large-scale datasets is something we are actively considering.\n \nFurthermore, we would like to emphasize that the experiments conducted in this paper are highly representative:\n\nFirst, to demonstrate the scalability of our proposed algorithms, we have tested them on multiple datasets and various tasks, where they consistently show strong performance in terms of both efficiency and effectiveness compared to previous methods.\n\nSecond, it is worth noting that in the video summarization task, the scale of data we are dealing with is already significantly larger than that of most known subset selection tasks. For instance, in the **V2** video, which has a duration of 7 minutes and 45 seconds (465 seconds), with 30 frames per second, we have effectively selected 20 representative frames from nearly 13,900 frames. \n\n**References**\n\n[1] Mirzasoleiman, B., Karbasi, A., Sarkar, R., and Krause, A. Distributed submodular maximization. The Journal of Machine Learning Research, 17(1):8330–8373, 2016.\n\n[2] Mokhtari, A., Hassani, H., and Karbasi, A. Decentralized submodular maximization: Bridging discrete and continuous settings. In International conference on machine learning, pp. 3616–3625. PMLR, 2018b.", "claims_and_evidence": "The claims made in the submission are supported by clear and convincing evidence", "methods_and_evaluation_criteria": "Proposed methods and evaluation criteria make sense for the problem.", "theoretical_claims": "No apparent issue found.", "experimental_designs_or_analyses": "Empirical evaluation is conducted on video summarization, Bayesian A-optimal design, and maximum coverage. It is demonstrated that Multinoulli-SGA and Multinoulli-SCG outperform existing methods in terms of objective value.", "relation_to_broader_scientific_literature": "The paper provides a novel continuous-relaxation framework which provides a lossless rounding scheme for any set function. This gives new direction in the literature.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "The Multinoulli Extension is a novel and interesting framework that provides a fresh perspective on the subset selection problem under partition constraints. The Multinoulli-SCG and Multinoulli-SGA algorithms represent significant improvements over prior continuous algorithms, particularly in terms of query efficiency and parameter-free operation. These advancements make the proposed methods highly practical for real-world applications where computational efficiency and ease of implementation are critical.\n\nHowever, the paper could benefit from a more thorough analysis of the scalability of the proposed algorithms. As the scalability of the algorithms are improved compared to prior continuous algorithms theoretically, evaluating the algorithms on larger datasets would provide deeper insights into their performance in practice.", "other_comments_or_suggestions": "No", "questions_for_authors": "No", "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:

Meta-review: The paper consider the problem of maximizing a weakly submodular function subject to a partition constraint and its application to subset selection. The new algorithm attains a similar approximation factor as previous work by Thiery and Ward while having an incomparable runtime trading off the dependence on the ground set size and the error in the approximation factor. Note that the previous work is for all matroid whereas the current paper is only for partition matroid. In experiments, the new method seems to have a slight improvement in the quality while using fewer queries. All reviewers are positive about the paper. They appreciate the practical improvement from the new algorithm as well as the new theoretical perspective with a new continuous extension (though this extension is only for a partition matroid).
Decision: Accept (poster)