Constrained Robust Submodular Partitioning
Authors: Shengjie Wang
Tianyi Zhou
Chandrashekhar Lavania
Jeff Bilmes
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Submodular Optimization

Abstract: In the robust submodular partitioning problem, we aim to allocate a set of items into $m$ blocks, so that the evaluation of the minimum block according to a submodular function is maximized. Robust submodular partitioning promotes the diversity of every block in the partition. It has many applications in machine learning, e.g., partitioning data for distributed training so that the gradients computed on every block are consistent. We study an extension of the robust submodular partition problem with additional constraints (e.g., cardinality, multiple matroids, and/or knapsack) on every block. For example, when partitioning data for distributed training, we can add a constraint that the number of samples of each class is the same in each partition block, ensuring data balance. We present two classes of algorithms, i.e., Min-Block Greedy based algorithms (with an $\Omega(1/m)$ bound), and Round-Robin Greedy based algorithms (with a constant bound) and show that under various constraints, they still have good approximation guarantees. Interestingly, while normally the latter runs in only weakly polynomial time, we show that using the two together yields strongly polynomial running time while preserving the approximation guarantee. Lastly, we apply the algorithms on a real-world machine learning data partitioning problem showing good results.

Constrained Robust Submodular Partitioning
Shengjie Wang"., 11 Tianyi Zhou*:12, Chandrashekhar Lavania & Jeff A. Bilmes
University of Washington, Seattle University of Maryland, College Park? {wangsj, tianyizh, lavaniac, bilmes)uuu....m....
Abstract
In the robust submodular partitioning problem, we aim to allocate a set of items into m blocks, so that the evaluation of the minimum block according to a submodular function is maximized. Robust submodular partitioning promotes the diversity of every block in the partition. has many applications machine learning, c.g.. partitioning data for distributed training so that the gradients computed on every block are consistent. We study an extension of the robust submodular partition problem with additional constraints (e.g.. cardinality, multiple matroids, and/or knapsack) on every block. For example, when partitioning data for distributed training, we add constraint that the number of samples of each class is the same in each partition block, ensuring data balance. We present two classes of algorithms, i.e., Min Block Greedy based algorithms (with an (2(1/m) bound), and Round-Robin Greedy based algorithms (with a constant bound) and show that under various constraints, they still have good approximation guarantees. Interestingly while normally the latter runs in only weakly polynomial time, we show that using the two together yields strongly polynomial running time while preserving the approximation guarantee. Lastly, we apply the algorithms on a real-world machine learning data partitioning problem showing good results.
Introduction
The problem partitioning given set V of items into m blocks, where any two blocks share no items in common, arises in many real-world scenarios and machine learning applications. As optimization problem, partitioning aims to generate the blocks so that the utilities of the blocks, as measured by given function,
rich family of set functions that naturally captures diversity of a given set of items. They have been applied in many real- world problems (26] 30 21
good. Submodular functions
18 28 By maximizing submodular utility function for each partitioned block, we encourage each block to be representative of the ground set V. Many algorithms have been proposed for various submodular partitioning problems with approximation guarantees.
13
For the submodular welfare problem submodular evaluations of every block is maximized. Such an objective promotes the overall utility of the entire partition but some blocks may still have small function values. The robust submodular partitioning problem 12 20 (often called "submodular fair allocation with indivisible goods") aims block in the partition is maximized according to the submodular function. The robust objective optimizes the worst block in the partition that all blocks are minimally "good." In the general setting, every block in the partition may have a different submodular function (the heterogeneous case) although for this work, we study only the restricted setting where all blocks share the same submodular function (the homogeneous case). The robust submodular partitioning problem has many applications. Given as the training dataset for a machine learning task, Wei et al. 29 finds a partition of V for distributed training: every block of partitioned data is sent single machine for parallel gradient computations, and the gradients
! we aim to find a partition such that the sum of the
to find the partition such that the minimum-valuue
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

are aggregated over all the blocks in the partition for model updates. Since we enforce each block to be representative of V, the gradients computed across distributed machines are consistent, resulting in reduced variance and improved convergence for the aggregation step. Using a similar idea, Wang et al. [25] partitions the training data into mini-batches so that every mini-batch is as representative as possible, therefore reducing the variance during mini-batch gradient-based training.
In this work, we explore two different algorithmic approaches, Min-Block Greedy and Round-Robin Greedy, for our partitioning problem but under various constraints, newly applied to this problem. For Min-Block Greedy based algorithms, we first show that the 1 bound for the unconstrained case is tight. We then modify the algorithm to allow general down-closed constraint C, and prove an approxima- tion bound of om++1' where a is the bound for solving the submodular maximization problem under constraint using a greedy based algorithm. For example, for a cardinality constraint, a 1 1/e (9] and the bound for constrained robust submodular partitioning is (m + 1-17a)= Similarly, for C as an intersection-ol ofaprectioooo---mmaaiiiii p-matroids constraint, a = (1 + p) [0), and the bound is (m + +p- + 1)-1; for knapsack constraint, 0.5(1 1/)e 1/e) [6]. and the bound is (m + 1-17e) 1-1 For Round-Robin
m
Greedy based algorithms, when C is a cardinality constraint, we get bound of (2-1/e)" and when C is a matroid constraint, we get a bound of 1-1/e. The Min-Block Greedy approach gives a weaker bound, and since the 1 bound for the unconstrained case is tight, we cannot improve upon the 1 factor for the mi
3
Tn constrained case. The Round-Robin Greedy approach gives a constant bound, but its rumning time is worse. The running time for Min-Block Greedy is O(n"), where n is the ground set size. For Round- Robin Greedy under matroid constraint, the rumning time is (n (log log m + log })), as it needs to use binary search to find the optimal solution value to the given problem over an exponentially decreas- ing sequence, with L (6 > 0) as the multiplicative factor. In all cases, we assume an oracle model, 1-8
and the running time is in terms of the number of submodular evaluations. An important contribution our work shows is that by utilizing the Min- Block Greedy algorithm result as input, our Round Robin Greedy algorithm attains strongly polynomial running time- all previous results the uncon- strained case using a Round- -ocdd--ooiiiiiiii algorithm have only weakly polynomial running time B..
The various constraints (e.g., cardinality, matroids, and knapsack) we study greatly improves the applicability of robust submodular partitioning. Several applications that benefit from the constraints include: (1) Partition a training data for machine learning models in distributed training or forming deterministic mini-batcio
(29 25 The additional constraint can be the number of samples from each class to be no more than a certain value. If there are enough samples in the training data, every resulting block will have the same number of samples for each class, which avoids imbalance, further promoting each block's 'ss diversity, and improving the gradients' consistency. (2) Given undirected graph, we partition the edges into subgraphs so that each subgraph is representative based on the submodular evaluation, and we also constrain each subgraph to have no cycles (a cycle matroid). A practical scenario is that we wish to send information efficiently over a graph of devices. We partition the graph that information can be sent in parallel, and the constraint to have cycles enforces that information is not redundantly sent twice to the same device, leading to improved communications efficiency. (3) Again, for an undirected and connected graph, we partition the edges into subgraph blocks such that if we were to remove any block of the partition from the original graph, the remaining graph remains connected (which can be done via a bond matroid, where min-cuts are cycles and anything not a cut is independent). In practice, this functions as a form of reliability insurance. For a graph of devices, we partition the graph to perform computation in parallel, so that if the connections in one block fail, the other blocks can still operate and communicate since the graph remains connected.
2 Related Work
Golovin 12 introduces robust submodular partitioning (i.e., submodular fair allocation of indivisible goods), and proposes matching- baaed algorithm with a bound of n-m++T Khot & Ponnuswami [E]
proposes binary search based algorithm and gives improved bound of 2m-J Asadpour & Saberi
2 uses an ellipsoid approximation approach and gives a bound of ( Vim log n 20g m Wei et al.
20 gives a simple Min- Block Greedy algorithm and proves a 1 bound. A Round-Robin Greedy ap-
proach is given in t with bound of 1-e 3 Ghodsi et al. [ proposes a local search algorithm with a bound of 1 Both 3 and [ requires guessing of the optimal solution value from an exponentially decreasing sequence of values, so strictly speaking, they lose an extra (1 + -fattr in the approxima-
2

---

tion bound where (1 + 6) is the exponential factor for the guessing sequence. We can set the d value small get close to the constant bounds shown above at the costs of computation. Wang et al. [25]
extends the Min-Block Greedy algorithm with a cardinality constraint, and also shows a hierarchical
partitioning framework to reduce the memory costs. We adapt the Min-Block Greedy approach [29] and the Round-Robin Robin Greedy approach [ to the constrained case. To the best of our knowledge this work is the first (as far as we know) to study the robust submodular partitioning problem under all of the various constraints (cardinality. intersection of matroid, knapsack). Wang et al. [25 is special case of our work as it only studies the cardinality constraint. Cotter et al. [ studies (as well as allow- ing multiple blocks to be jointly scored) a matroid constrained "groupings" (ive..coverings, packings, or partitions) problem but only a fractional subset of groups (rather than the minimum of the groups), is guaranteed to have values larger than the bounded max-min OPT, while our bound compares the min block evaluation to the optimal max-min value. Another line of related research is the submodular load balancing problem, which minimizes the maximum-valuee block in the partition according the submodular evaluations. In contrast to promoting diversity of each block for the robust submodular partition problem, submodular load balancing encourages every block to contain redundant items, similar to standard clustering objectives. Theoretically, this problem has been shown to be much harder as Svitkina & Fleischer
( shows a information theoretical lower bound of o( log 72 and
also gives sampling algorithm to match the lower bound up constant factors. Similar to the max-min case, Ghodsi et al. [ uses the ellipsoidal approximation to get a bound of O (Vvn /n log n).
Wei al.
20
gives Lovász extension based relaxation algorithm and achieves bound of m.
3 Preliminaries and Formulation
With a ground set V of n items, a submodular function f is a set function 2V + R that satisfies the property: ((A) + (B) 2 S(AU B) + s(An B), where A, B C V. Equivalently, submodular function is characterized by diminishing returns: f(v A) 2 [v] Vu & B and A C B C V. where f(u f(vr U B) - fBB. Submodular functions naturally deseribe the diversity or representa- tiveness of given set of items. Many simple preedy-based algorithms have been developed to solve optimization problems involving submodular functions, giving both theoretical approximation guar- antees, as well as good empirical performance. We restrict the submodular functions discussed in this paper to be monotone non-decreasing and normalized, i.e., (B) 2 f(A) AA S B S V. f(0) O.
A matroid MM- = (V,I) is a set system that describes the independence relationships among the subsets of the ground set V. is set of subsets of V and every S E I is considered an independent subset. The matroid rank function is defined as T (A) = max [|S] : S C A, S E Z}. (V) indicates the maximum size of a subset that may be independent according subsets of cardinality S k with some integer k > 0 form a aniform matroid, which we denote by M partition matroid is one where we partition the ground set into blocks, and a set is independent if it intersects each block by no more than a block-specific limit. We define a particularly useful partition matroid on an expanded ground set V as follows: We first duplicate the ground set m times, creating 1/1 V/2 = Vm = V. which are ground set copies. We create an expanded ground set V =1= Vj as the disjoint union. A subset S C V is independent in Mr if for every element E V, let its m copies in V be (V1, U2,.... J. contains at most one copy of element v. Apart from the uniform matroid and this particular partition matroid, there are many other matroids reflecting a natural notion of independence. for example, the inearly-independent set of real vectors and the spanning trees in a graph. In the below, we use both S E . and, when clear, S E I, to indicate that S is independent in the matroid M = (V,I).
the matroid M. All
we have |S {V1, Ugy..., J < 1, i.e., S
Matroids are often used as constraints in submodular optimization problems: max (SS with a matroid M = (V,I). When M is uniform matroid MY this reduces to the cardinality submodular max and the greedy algorithm gives e bound [. For general constraint with the intersection of matroids, the simple greedy algorithm gives a I+ bound 10. Suppose we represent a set S as a
binary indicator vector xs E {0. 1)" i.e., vi E for all the independent sets of matroid M = (V,I). the convex hull over all the xs. S E I forms a polytope, which is called the matroid polytope PM of matroid M (9). Based on the convex property of the matroid polytope, algorithms K i have been proposed to firstly solve a continuous extension of the submodular optimization problem under the matroid polytope constraint, which generates a fractional solution in [0, 1)m,, and then round the fractional solution to an integral solution to get the resulting set. The continuous greedy algorithm 4 gives e guarantee under single
xs]]] = if u; E S or otherwise z [t] = 0. Then
-1
3

---

matroid constraint using pipage rounding 0 Interestingly, running the continuous greedy under a partition matroid constraint (submodular welfare problem) gives a uniform fractional solution, i.e. on the expanded ground set V, the fractional solution x = ( ........ m) (i.e., assigning m of every element to each block) leads to each element in V uniformly to one of the m blocks. This observation also constitutes the basic idea of Round-Robin Greedy for solving the robust submodular partition problem
e bound in expectation for an integral solution that assigns
K which we will
discuss in more detail later.
For a submodular function f on ground set V, the robust submodular partition problem (submodular fair allocation) defined as:
max min (AA,, em) AE#
(1)
where m is the number of blocks in partition, we denote all possible partitions with m blocks of ground set V as IT(V, m)) and one partition и with |x| = m is collection of m disjoint sets. Equiva-
lently, we can represent the partition using partition matroid constraint on the expanded ground set V:
max min f(S f()) SEM, jE(m)
(2)
Intuitively, the above optimization for robust submodular partitioning encourages the minimum- valued block to have high submodular evaluation. Compared to the submodular welfare problem, the robust submodular partition promotes fairness for every one of the partition blocks.
There have been three recent approximation algorithms developed to solve Eq. ( Particularly, Wei et al. 20 uses a Min-Block Greedy algorithm, which greedily adds the element with the largest gain to the block with the minimum evaluation. Barman & Krishna Murthy 3 propose a found-Robin Greedy algorithm, which iteratively traverses all the blocks in a fixed order, and greedily adds an element with the largest gain to each block. Ghodsi et al. [I] applies a local search approach, which starts with an arbitrary partition and keeps moving an element from a non-m minimum block to the minimum block if this relocation improves the objective by certain threshold until no such element can be found.
For B and [Л]. they both require guessing the optimal solution's 's value, and they need to run multiple instances of their algorithms with the guessed optimal values as an exponentially decreasing sequence from the maximal possible value f(V) to the optimal solution value μ max minses f(S). With the exponential decreasing factor as + 8, the running time (in terms of submodular function calls) is J 1 log ((V) for E. and Onn'm² 8 log I(V)) ) for [.]. BinnBlock Greedy, a much simpler algorithm. has running time of O(n)). Note that the settings of [3] and [ are slightly
more general than Eq. (I as the submodular function for each block can be different. But it's not the
heterogeneous case either as they focus on a different notion of optimality.
3.1 Discussions about the Optimality in 3 and the Heterogeneous Case
The works S [ both study the partitioning problem in the economics context of fair allocation of indivisible goods. In such a setting, every block an agent, and we want to find an allocation of the goods to each agent in a fair manner, so that each agent's evaluation of the allocated goods to himself is optimized. Each agent can have different evaluations for the goods, which means that the submodular function for each block can be different. Taking guarantee they prove is
[3] as an example, the theoretical
Lemma (Theoretical Guarantee in 3. Let AI, A2...., , Am be the solution to the Round-Roid Robin Greedy algorithm for the unconstrained problem, and given m submodular functions for the m blocks as for j = 1.2....m.. for for every agent j we have f,,)) 2 1-e maxren(y:.)) minser fy))).
Intuitively, the bound guarantees that based on each agent's evaluation fz. the goods allocated to himself is not bad compared to the worst block in the allocation. When all the f3 's are the same, the bound reduces the bound for the homogeneous case of robust submodular partitioning, which is the focus of this paper. The heterogeneous case for robust submodular partitioning is different, as it requires to show a bound like (suppose the algorithm solution A, for j E (m))
f5(4)) Z min j ml
max min
(S).
(3)
TElI(V.m) Sen

---

We give an example of the m functions so that the two guarantees vary. Say we have a predefined partition over the ground set V into m blocks as C₁, Cz...... Cn and Uje = V. =V,,,, C,n.C
[CJ] = Cyrl (assume |V] is multiple of m). Let fy( = IS n Cjl. The optimal solution to the heterogeneous case mVX minje[m] (A2) is to assign the items in the same way as the predefined partition Ci, C2.... Cm. and the optimal solution value is C3pl- However, for the bound in 3 II) the optimal solution {Oi, O2...., 0m argmax
min (A) is intersect each predefined block equally, i.e., |O, n Cyyl = |cpl vj.J" E El,..., Therefore, the optimal solution value is then IC1l XM
In this work, we study the constrained case for the submodular robust partition problem in the homogencous setting (submodular functions for all blocks are the same). We extend Min-Block Greedy algorithm [29] and BounddRRbinn Greedy algorithm [3] to adapt to various constraints, e.g., cardinality, matroid, and intersection of matroids.
4 Min-Block Greedy Based Algorithms
Wei et al. and at every iteration, for the minimum-values block A,- E argmin, [(A,), it finds the element with the largest gain [(v] Ay-). Wei et (29 proves 1/m bound of Min-Block Greedy. In fact, their proof works for simpler algorithm, Min-Block Streaming Algorithm D which assumes that the algorithm accesses elements from the ground set in an arbitrary order as stream V = and it assigns the incoming element to the block with the least evaluation. We denote
24 proposes a Min-Block Greedy Algorithm 2 for Eq. ①.. which loops over n iterations,
(V1, .., v,)). the optimal partition to Eq. ① as π = (0,,02..... Jm.
Lemma 2 (Unconstrained Min-Block Streaming (29).. For a ground set and its elements (v), u2..... ... (n) coming in an arbitrary streaming order, the output solution of Alg. ! has minze[m] [(A,) 2 i -miije[m] f(O,))
Corollary 1 (Unconstrained Min-Block Greedy 29)). The output solution of Alg. has minje[m] f(A,) 2 I minjeemm f(O,) since the order of adding elements in Min-Block Greedy is one possible order of the ground set elements.
mn
Intuitively, Alg. 2 optimizes the objective Eq. ① greedily, i.e., it always increases the current value (the minimum- block evaluation) with the largest possible gain, while the performance of Alg. T greatly depends on the order of elements, so it might seem that the bound for Min-Block Greedy should improve upon the current bound. However, as shown in our new result in the following lemma, the bound in Corollary D is tight.
Lemma 3 (Tightness of Corollary ). We > 0, 3 a submodular function f such that the output solution of Alg 2 miny=1m f f(A)) minj=1:m f(O,) +
Algorithm 1: Min Min-Block Streaming
Algorithm 2: Min-Block Greedy
input submodular function f, ground set as a stream
input submodular function f, ground set V. number of blocks m
V (U1, ..,..., Un), number of blocks m
R V:
2 Let A = A2 = =..= = Am = 0:
R V:
while R + do
2 Let A A2 ..... Am =0: 0:
j E argmin, f(A;);
for i =1:: 1:n do
v² E argmax,en fullAy-);
j E argmin, (AA);
A,- = Ap U ((')):
A5- = Ay. U {us): 6 return (Ai, A2,......... Am)
:= = R (v*):
8 return (A1, A2,..., Am)
We elaborate on how to construct the submodular function in Appendix A The key idea is that we can find set-cover function where even though Min-Block Greedy selects the element with the largest gain, the element can still be quite redundant with the current minimum block. Say the current minimum block is A, and the maximum-gain element is v chosen by the greedy step, meaning (vlA) is larger than ((*|AA) for r' E R v. However, A(vlA)
F(o)" can still be very small, i.e., the area covered by v according to the set-cover function is already mostly covered by A. On the
5

---

other hand, the optimal solution can fully utilize f() thus making a more lonesome U cover much larger area overall. Note that Lemma B also serves as the tightness for Lemma. 2
since the order
of adding elements in Min-Block Greedy follows streaming order.
More generally, given constraint C, define the constrained robust submodular partition
max min [(A, TEII(K,m.C) Ae
where II(V, m, C) is the set of all possible partitions on set V into blocks such that for every partition π E [V, m, C), every block A E x should satisfy the constraint A E C. We denote the optimal partition in Eq. 4 Fc {Of. 0 ..... O }. We remark that due to the constraints, some elements might not be assigned to a partition block, so strictly speaking the solution is an allocation (or "grouping" Cotter et al. R ) of elements rather than partition.
For now, we will take as any down-closed constraint: Let C be collection of subsets of the ground set V, and by satisfying the constraint, we require the solution A to be one of the subsets in C. The
down-closed property means that if A E C we have B E C for any C A. Following Eq. 4 we can define the constrained problem in terms of the expanded subset V:
max SCV, (...
min S(S n Vg).
(5)
Based on the Min-Block Greedy algorithm for the unconstrained case, we propose a natural extension to the constrained case (Alg. B where at every iteration, for the minimum minimum-valued valued block A,,, greedily find the best element e that retains block feasibility under the constraint C, i.e., {x" A. E add to the current minimum block,
C. If we cannot find any element in the remaining remove the current block from the candidate blocks and move to the next smallest valued block.
In Line 6 of Alg.
call subroutine GreedyStep( Rt, C, A,,) ) to greedily find feasible ele- ment. The subroutine varies according to the type of constraint C. Particularly, for the constrained submodular maximization problem defined as
max
f(S).
SCV.SEC
GreedyStep(-) is shared by Alg. 3 and Alg. and if Alg. is an approximation algorithm of solving Eq. (6) with some bound
prove the following result for Alg.
Algorithm 3: Constrained Min-Block Greedy
Algorithm 4: Constrained Submodular Greedy Max input
input submodular function f. ground set V, number of blocks constraint C Am = 0:
submodular function f. ground set V, constraint C
1 Let A1 = A
Let J [m]]
V;
R V:
3 while R R and J + 0 do
j argmin,e.J f(A));
Let 5 0:
while R + do
if 3v S.t. Aj- U fo) E then
if 3u E R s.t.
AJ- U fu) E then V² = (t.edd
8" = GreedyStepl R, A,));
A R R {o*):
S 5 S
else
R R (v*):
a" E argmax A,A,
A.AUR un f((a));
else
10
if f((a") }) f(A,) then A = {a* R R (a*):
Break;
11
10 a* E argmax f({a)); return argmax Ae(Sa,(a' ((A)
12
Let J=
13 return (A1, A2, .... Am)
Theorem 1 (Constrained Min-block Greedy). Given a constraint C, if the greedy solution to problem maxsec f(S) using Alg. f has a bound of a, i.e., f(S9) Z a maxsec f(S), then the solution of Alg. 3 has minje(m] f(A,) Z amt minje(m] f(O9). Assuming GreedyStep(-) takes (1) oracle calls, the time complexity of of Alg. is (n²)
a
The general idea of the proof (details Appendix A is that we divide the ground set V into two disjoint parts V V'u U R', where the min block in the output solution A intersecting V corresponds

---

to the min block solution of an instance of unconstrained robust partition problem (Eq. ( defined
on the ground set V", and A n R' with the other part corresponds to the solution of an instance of submodular maximization (Eq. (6 under the constraint C defined on the ground set A U Rt. We bound the two parts separately and combine them to obtain the above bound.
Corollary 2 (Cardinality Constrained Min-block Greedy). For C as cardinality constraint, the output Alg 3 has minj=1:m [(A,) 2 T- minj-11mm ((09)
Corollary (Matroid Constrained Min-block Greedy), For C as an intersection of matroids constraint, the output of Alg 3 has minj=1.m f(A)) 2 m+p+I minj=1mm f(O,).
Corollary 4 (Knapsack Constrained Min-block Greedy). For C as a knapsack constraint, the output of Alg 3 has minj=1:m f(A)) 2 1-1 (00]==1..(00)
For as cardinality constraint, GreedyStep(.) just picks the element with the largest gain assuming the block has not yet reached the cardinality limit k. For C as an intersection of p matroid constraints, GreedyStep(-) finds the element v" that has the largest gain [(v'| [('*|A)-) assuming the block can be kept feasible, i.e., v² U Ay+ E C. For C as a knapsack constraint with the weight of each element as w()), GreedyStep(.)) finds the element ot with the largest ratio /(v")Ay)) assuming the sum of weights can be kept below the given budget. In line 9-11 of Alg. 3 and line 10-11 of Alg. 4 we include an extra step of comparing with the largest singleton value. Such step is redundant when C is an intersection of matroid constraints, but is essential for the knapsack constraint case, as the modified greedy algorithm for the knapsack problem [16] requires this extra step or otherwise a is unbounded. Due to the tightness of the 1 bound we have proved for the unconstrained case, the 1 m dependence in the constrained bound cannot be improved.
w(e)
Round-Robin Greedy Based Algorithms
Barman & Krishna Murthy 3 propose a round-robin style algorithm for the unconstrained robust
submodular partition problem (Eq. (1) and gives constant bound of 1-e-! with weakly polynomial running time. Compared to Min-Block Greedy, Round-Robin Greedy requires guessing the optimal values by an exponentially decreasing sequence, and for each guessed value, runs one instance of the round-robin subroutine. Specifically, suppose μ = min, [em] f(O)), i.e., μ is the optimal solution value for the unconstrained case, then for a parameter 5 O. Round-Robin Greedy runs the
round-robin subroutine with the guessed optimal values from a sequence (f(V), T+6 (1+65......) and ends when the guessed value is no larger than The running time of each round-robin subroutine is (nn)), as it greedily finds the element with the largest gain by iterating over all the
f(V) f(V)
remaining elements. There are log f(V) guessed values in the exponentially decreasing sequence,
so the overall running time is log14 {(Y)) = On 1 log 1(11). Note that since we use a (1 + 8) factor exponentially decreasing sequence, lose (1 + 8) factor in the approximation bound, which can be improved arbitrarily by using a smaller d value but with a cost of running more instances of the round-robin subroutine.
The major idea behind Round-Robin Greedy comes from the solution of Continuous Greedy for the submodular welfare problem, which is an uniform fractional vector x = ( m. ....... S with the
length of æ equal to the size of the expanded ground set | Let F be the multilinear extension 4 of f.
Continuous Greedy gives a bound that Fiz) = EE R~ f(R)= > (1 - e- max ΣAET f(A). where Ex~z f'( (R) takes the expectation of f(R) on a random set R with each element sampled independently according to the probability in the fractional vector æ. Note that the hardness for submodular optimization under a matroid constraint is 1 - e -1 which means that the random assignment strategy achieves the best possible theoretical bound on the submodular welfare problem.
Round-Red Robin Greedy can be thought as a rounding mechanism for the fractional solution x. The round-robin style iteration is similar to the uniform random assignment in deterministic manner, and by greedily finding the element, the value of every block can be bounded against that for the random assignment. In fact, Round-Re Robinn Greedy bounds every block A, to be f(A,) 2 3 F(x) and since the welfare solution bounds the robust solution in terms of the sum: eax.) ΣAe f f(A) 2 Eje()) Oj 2 mu, get the desired bound for the robust partition problem.
7

---

We extend Round-Robin Greedy to the constrained case (Eq. 4 firstly with C as cardinality constraint This is a relatively simple case due the nature of Moondd-Robin Greedy that every block gets assigned with the same number of elements at the end of every round-robin iteration. We present the modified algorithm in Alg. 5 which also helps to explain the essential ideas of the original Round- Robin Greedy as we describe below.
Lemma 4 (Cardinality Constrained Round-Robin). For the problem in Eq. with as cardinality constraint k, Alg. gives a solution min f(A,) 2 (1 1)2
3 minje[m] f(0)).
Algorithm 5: Cardinality Round-Robin Greedy
input f. V. m, cardinality constraint k, discounting factor for guessing optimal ò Let be the solution value of Alg.
B
Let high = [log]+>(m + 2)}, low 0:
Create sequence of guessed values: (r, (1 + 6)7, (1 (1+)) 8).......
....... (1
5) r))
Create an empty solution (0 for each block in the partition) for each guessed value
To. mi..... Thigh
5 while high 2 low do
Let idr [hhgg + l/ow Let A A2 = Am = 0:
Let V = -(rlu E V. (v) & 1)- (1 8) r): Let G = V VW; Assign G to A |G| Am-
Am with one element per block;
Let m' m G|;
10
Let A1, Al..... A'm' be the solution to max EsEr ((S) using continuous greedy and swap rounding; Let V UselmpA' Let (Ai, A2...., Am = RR(S, V", "m',, [m']):
11
if ((A)) 2 ----1 (1 + d) Vj E [mm] then
12
Let Tud {A1, . Am ); Let low idr + 1;
13
14
else
15
Let high- idx 1; return best of To. 11, high:
16
Here is how we achieve Different from the original Round-Robin Greedy, which performs a grid search over guessed optimal values, we perform a binary search over the sequence of values and therefore the number of outer iterations is reduced. Most importantly, we use the M Greedy solution's value as the minimum guessed? 2 value Because of the
time.
Algorithm 6: Round-Roooo Robin Greedy Itera- tions (RR(J, R,m', J),
input : 5. Rt m', matroid constraint M, .set of block indices
while J ( and R o 0 do
for j E [m'] do
bound of the -in
if j E J then
m i7e
17e
if 3v E R.s.t. A, AUU
Block Greedy solution, the maximum guessed value is thus bounded by (m + 2)r. We then create a 1 + 6-5 factor exponential decreasing sequence between т and (m++)) to binary search for the optimal solution value. This improves the number of outer iterations of the algorithm to (log log1+5 m) Olog log m +7
then
0" E
argmax f(ulA,); vER.A,UDEM
A, == A, U {v*}:
: R \ {or);
log }.. which is pooyyoiappolynomiall while the num-8
else
ber of outer iterations (logi+ I()) for the origi- 9 nal unconstrained case is only it has a log dependence on the function value.
Let J = J j:
return (A,, Ag ... Am!)
In every outer iteration (Line 12-15), Alg Jcheeks the round-robin solution based on the guessed optimal value (1 + 6)5dz satisfy the approximation bound, i.e., f(A,) > [1-1/e]² (1 + 8ydde, Vj E [m]'. If the bound is (not) satisfied, the guessed value is large (small) and we move to an increased (decreased) search value. Within every outer iteration, we perform round-robin greedy (iterate over every block in some fixed order and greedily add to the block the element with the largest gain). Line 10 of Alg. is the major change to mound-Robin Greedy specifically for the cardinality constraint case, where we first find the solution to the cardinality constrained submodular
8

---

welfare problem mVX Esen f(S), and then only apply Round-Robin Greedy to the union V of the solution A1. A/. A2. A'm.
The running time of Alg. 5 is similar to Round- Greedy, with additional costs caused by Line 10, which solves a cardinality constrained submodular welfare problem. Using Continuous Greedy and swap rounding / for Line 10 can be quite costly (O(n)) for the inner loop), which may improve in the future by a better algorithm. In Alg. D we propose another algorithm that addresses the constrained robust submodular problem with C as any matroid constraint M and incurs no additional computation costs compared to Round-Robin Greedy.
Theorem 2 (Matroid Constrained Round-
For the problem in Eq. with C as any matroid constraint M, Alg 7 gives a solution minze(m) [(A,) 2 (1-e-t) minje(m] (O0M). The
time complexity of of Alg. (n (log log m + log 8) })).
Algorithm 7: Matroid Round- Greedy
input f. V. m, matroid constraint M,, discounting factor for guessing optimal 5 Let be the solution value of Alg.
Let high = [log
+ 2)}, low = O:
Create sequence of guessed values: (r, (1 (1++6) 6)7, (1 ..... (1 8) r)
Create an empty solution (0 for each block in the partition) for each guessed value
To, Ti...., highh while high 2 low do
5
Let idr [hhigh + low) Let A A2 = Am = 0;
Let V' = =fole E V, f(u) < 1 (1 + 7); Let G = V V';
7
8
Assign G to A A Am Am Am with one element per block;
Let m = m - G|;
10
Let {A1, A2,..., Am)) } RR(S V", m M, [m]]):
if (AA) (1-e-1) 3
) (1 + 8) idp Vij [m'] then
12
Let Tids = {A1 A2, }; Let low = idr + 1:
13
else
14
Let high = idæ 1;
15 return best of Tu, T1,..... T Tighh:
Comparing to Alg. 5 the major change in Alg. f is (1) we do not need to run the costly Continuous Greedy and swap rounding to get a solution to the constrained welfare problem, which makes the algorithm applicable in practice; (2) for the RR(-) subroutine, we find a feasible element and add it to the current block, and we remove block from the candidate set J if there are no element in the remaining set that can be added to the block without violating the matroid constraint. Note for the cardinality constraint case, we can always find feasible element until every block has & elements. The overall running time is (n (log log m + log 4)). The general idea of proving Theorem 2 is to bound the solution to the fractional solution of the continuous relaxation. For every block in the solution, inspect the elements that have been evaluated during the greedy step. For those elements with large gains when being evaluated but not added due the violation of the matroid constraint, their gains as submodular maximization with a matroid constraint on a reduced ground set. For the remaining elements, we bound their gains by the greedy step and together we get the desired bound.
bound
6 Experiments
We empirically test Algs. andd 7 on the CIFAR-1O training set 19 (VI== = 50000). We use facility location our submodular function, i.e., S(S) Evev max sim v'), where sim(v, v') measures the affinity between elements and v'. This function is widely used and naturally describes a subset's s diversity via its similarities//distanes, to all other points in the ground set, and it has achieved much practical success [27 26 23 For similarity, we use a Gaussian kernel with L.2 distances. i.e.,
sim(t: v. 0') ezp( -1le- i.e., o Everev ||u a
where o is the bandwidth of the kernel, set to the average L2 distance. v'llz/n?. The features used to calculate the L2 distance is the bottleneck layer's outputs generated by a deep auto-encoder model (details are in Appendix D).

---

We test the algorithms and compare their objective values (Eq. + with
Matrold Constraints Total samples.
matroid constraint where we limit
3500
3243
MinBlockGreedy (Alg.3)
RounddlokinCreedy (Aig.7)
the number of samples selected for each class in CIFAR-10 for each block
Sln-Block Funcioo Value
3000
33255
23510
Random
(CIFAR-10 has 10 classes). We com- pare the two algorithms with random
2500
2466:
2015
selection baseline - we randomly sample from each class and assign to each block with the constrained number of clements. Hence, the random selec- tion results satisfy the constraints. report the results for different
2000
1223.
1500
1122
1000
Fig. [ matroid constraints with various block sizes. The random baseline results are reported with means and standard- deviations over 10 runs. For all cases, we see that both Alg. and Alg. / significantly outperform the baselines. Although Alg. 7 has a better theoretical bound, Alg. 3 consistently gives better performance. Intuitively, Alg. 3 directly optimizes the objective as it greedily adds elements to the minimum-valued block. We expect Alg. to perform better in practice compared to Alg. 7 as Alg. 7 has a fixed ordering of the blocks, and the minimum-valle valued block tends to the last block in the ordering, in which case it does not get to select samples that have already been selected by prior blocks in the ordering. In Fig. 2 we use the partitioned blocks as minibatches train a ResNet-9 model and compare their performance on the test set. We observe that the blocks with higher submodular evaluations tend generate better performance for the trained model. We also provide results on synthetic data in Appendix Section
500
Motrold Constraint Parameters
Figure 1: Matroid Constrained results. The x-axis denotes the number of samples per class for the matroid. A total of 2000 samples are selected for each case.
CIFAR-10 Matroid Constraint Test Acc
Blot
Fandon
Figure 2: Training ResNet-9 (Myrtle Al) on partitioned mini-
batches under matroid constraints with various parameters. The y-axis denotes the test set accuracy. The z-axis denotes the num- ber of samples per class for the matroid.
7 Conclusions
We study the problem of constrained submodular robust partitioning. We propose two classes of algorithms, Min-Block Greedy and Round-Robin Greedy based, and prove approximation bounds under various constraints. This improves the applicability of the robust partitioning framework different scenarios. In future work, we wish to extend the current approach to the heterogeneous submodular partitioning setting where each block may be evaluated by different submodular function. Given the good performance of Alg. 3 in practice, it is worth investigating if further conditions or modifications Alg. 3 yield improved thcoretical bounds.
This work was supported in part by the CONIX Research Center, one of six centers in JUMP, a Semiconductor Research Corporation (SRC) program sponsored by DARPA.
10

---

References
[1] Alexander A Ageev and Maxim Sviridenko. Pipage rounding: A new method of constructing algorithms with proven performance guarantee. Journal of Combinatorial Optimization, 8(3): 307-328, 2004.
[2] Arash Asadpour and Amin Saberi. An approximation algorithm for max-min fair allocation of indivisible goods. In SICOMP, 2010.
[3] Siddharth Barman and Sanath Kumar Krishna Murthy. Approximation algorithms for maximin fair division. In Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 647-664, 2017.
[4] G. Calinescu, C. Chekuri, M. Pal, and Vondrák. Maximizing monotone submodular function under matroid constraint. IPCO, 2007.
[5] C. Chekuri, J. Vondrák, and R. Zenklusen. Submodular function maximization via the mul- tilinear relaxation and contention resolution schemes. Proceedings of the 43rd annual ACM symposium on Theory of computing, 2011.
[6] Chandra Chekuri and Alina Ene. Approximation algorithms for submodular multiway partition. In FOCS, 2011.
[7] Chandra Chekuri, Jan Vondrak, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In 2010 IEEE 5 Annual Symposium on Foundations of Computer Science, pp. 575-584. IEEE, 2010.
[8] Andrew Cotter, Mahdi Milani Fard, Seungil You, Maya Gupta, and Jeff Bilmes. Constrained interacting submodular groupings. In International Conference on Machine Learning, pp- PMLR, 2018.
[9] Edmonds. Submodular functions, matroids and certain polyhedra. Combinatorial structures and their Applications, 1970.
[10] M.L. Fisher, G.L. Nembauser, and L.A. Wolsey, An analysis of approximations for maximizing submodular set functions II. Polyhedral combinatorics, 1978.
[11] Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 539-556, 2018.
[12] Daniel Golovin. Max-min fair allocation of indivisible goods. Technical Report CMU-CS-05- 144, 2005.
[13] S. Jegelka and J. Bilmes. Submodularity beyond submodular energies: coupling edges in graph cuts. In CVPR, 2011.
[14] Subhash Khot and Ashok Ponnuswami. Approximation algorithms for the max-min allocation problem. In APPROX, 2007.
[15] Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.660 2014.
[16] A. Krause and C. Guestrin. A note the budgeted maximization of submodular functions, 2005. URL http:// ist. www.ss..u...............e....... wwtppppp....eeweeeeoeeeeeeeeeeee pttpp//ahh....ceee/////mm///o//a 3314
[17] A. Krause, A. Singh, and C. Guestrin. Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical studies. JMLR, 2008
[18] Andreas Krause, Brendan McMahan, Carlos Guestrin, and Anupam Gupta. Robust submodular observation selection. In JMLR, 2008.
[19] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, University of Toronto, 2009.

---

[20] Chandrashekhar Lavania and Jeff Bilmes. suttosuumaiiztoion:: A step towards unsupervised learning of submodular mixture. In Proceedings of the 2019 SIAM International Conference on Data Mining, pp. 396-404. SIAM, 2019.
[21] Kiyohito Nagano, Yoshinobu Kawahara, and Satoru Iwata. Minimum average cost clustering. In Advances in Neural Information Processing Systems, pp. 7759-1767, 2010.
[22] Z. Svitkina and L. Fleischer. Submodular approximation: Sampling- based algorithms and lower bounds. In FOCS, 2008
[23] Ivor W Tsang, James T Kwok, and Pak-Ming Cheung. Core vector machines: Fast svm training on very large data sets. In JMLR, 2005.
[24] Jan Vondrák. Optimal approximation for the submodular welfare problem in the value oracle model. In STOC, 2008.
[25] Shengjie Wang, Wenruo Bai, Chandrashekhar Lavania, and Jeff Bilmes. Fixing mini-batch sequences with hierarchical robust partitioning. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 225.3-3362,,2115
[26] Kai Wei, Yuzong Liu, Katrin Kirchhoff, and Jeff Bilmes. Using document summarization techniques for speech data subset selection. In North American Chapter of the Association for Computational Linguistics/Humun Language Technology Conference (NAAC1/)LT-20133) Atlanta, GA, June 2013.
[27] Kai Wei, Yuzong Liu, Katrin Kirchhoff, Chris Bartels, and Jeff Bilmes. Submodular subset selection for large-scale speech training data. In Proc. IEEE Intl. Conf. on Acoustics, Speech, and Signal Processing. Florence, Italy, 2014.
[28] Kai Wei, Rishabh Iyer, and Jeff Bilmes. Submodularity in data subset selection and active learning. In ICML, 2015.
[29] Kai Wei, Rishabh K Iyer, Shengjie Wang, Wenruo Bai, and Jeff A Bilmes. Mixed robust/average submodular partitioning: Fast algorithms, guarantees, and applications. In Advances Neural Information Processing Systems, pp. 2233-2241, 2015.
[30] Jingjing Zheng, Zhuolin liang. Rama Chellappa, and Jonathon P Phillips. Submodular attribute selection for action recognition in video. In NIPS, 2014.
12


Reviews:
[{"review_id": "sxX02t9-Iz4", "reviewer": "Reviewer_SBUL", "summary": "The focus of this work is constraint robust submodular maximization. In this problem, the goal is to find $m$ sets maximizing the minimum value of a given submodular function $f$ over these sets. This problem has attracted attention recently and  algorithms are designed for offline and streaming setting. In this work, author consider this problem subject to three famous constraint and provide two type of algorithms.\n\n1- Min-block greedy algorithms: This algorithm has been used before for non-constraint version robust submodular maximization and provides a $1/m$ approximate solution.  In this work they extend it to the constrained version and achieve $\\frac{\\alpha}{\\alpha m+1}$ approximation algorithm, where $\\alpha$ is the approximation guarantee of the greedy offline algorithm for that constraint. Intuitively this result is very close to being tight with respect to the unconstrained for large $m$ values.\n\n2- Round Robin greedy algorithm: They present a $\\frac{(1-e^{-1})^2}{3}$-approximation algorithm for the cardinality constraint and  $\\frac{1-e^{-1}}{5}$ for the matroid constraint.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I have mostly positive comments for this work. The results are interesting and ideas used are novel. At the first glance it might look like that the contribution is marginal given that their approach is similar to the unconstrained algorithm. Extending those ideas to constraint setting is non-trivial and requires work. The paper is in great shape, it is easy to follow and the similarity with the previous work is clearly stated.  The algorithms are explained step by step which makes it even more understandable. The experimental setting is also clearly stated and the results are promising.  The authors have only compared their approach against random solution, which is expected as to the best of my knowledge there are no such algorithms known before. I enjoyed Lemma 2, when reading the paper it came to my mind and I was happy to see that the authors have considered it. Assuming that I am not missing any previous work on this paper, I recommend this paper to be accepted.\n\nA few minor comments:\n- I recommend the authors to extend the theorems  to mention the number of oracle calls as well. It gives another reason why the algorithm in section 4 is interesting when compared to section 5.\n\n- The plots are hard to read, enlarging the font improves readability.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6 hours"}, "extra_text": {}}, {"review_id": "axol7c-iMG", "reviewer": "Reviewer_JRJn", "summary": "This paper focuses on the problem of finding an allocation of $n$ items in $m$ blocks that maximizes the minimum of the block valuations, where each block has the same monotone submodular objective (homogeneous case) and the subset allocated to each block has to satisfy a feasibility constraint. The model allows allocations that do not necessarily assign every item, since each block allocation needs to be feasible.\n\nThe authors first studied the Min-Block Greedy (introduced in [29]) which in each iteration selects the block of minimum value and greedily assigns a new element. They show that the $(1/m)$-guarantee (proved in [29]) of this algorithm is tight. Then, they extended this algorithm to the constrained version and prove a $\\alpha/(m\\alpha+1)$ factor, where $\\alpha$ is the factor for the vanilla constrained submodular maximization problem. In the second part, the authors give a Round-Robin Greedy algorithm (which is adapted from the algorithm in [3]) that achieves a $(1-1/e)^2/3$ factor for the cardinality constrained case. This algorithm is later extended to the matroid case for which it achieves a $(1-1/e)/5$ guarantee. Finally, they present computational experiments to compare the proposed algorithms.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "To the best of my knowledge, this work is the first to provide constant factors for the model with more general constraints. The unconstrained homogenous case was previously studied in [3] in which they obtained a (1-1/e)/3 factor. This work adapted the algorithm in [3] to obtain constant guarantees for the constrained version of the problem. The paper is overall well written. The proofs are correct, I carefully checked most of them. In particular, the proof of Lemma 3 follows from the result in [3] plus the fact that Algorithm 5 uses the continuous greedy. The proof of Theorem 2 seems to be an adaptation of the proof in [3]. The authors should emphasize the differences with [3] or the challenges in the analysis for matroid constraints.\n\nSome comments/questions:\n-\tThe authors should comment that [3] and [11] focus on a different type of guarantee. Specifically, they consider the maximin share as a benchmark which differs from the one considered in this paper in the heterogenous case, but it coincides in the homogenous case. This is crucial since certain parts of the proofs rely on the results obtained in [3], for example, (32) in the Appendix. Part of the discussion in Section C in the Appendix could be in the main body as well.\n-\tIn Section 6 (page 9 line 373), the authors say that the performance of Algorithm 7 is affected by the ordering of the blocks. Is there a way to heuristically optimize this or via preprocessing?\n\nMinor comments:\n-\tPage 3 line 120: properties of matroid are missing.\n-\tPage 4 line 157: Where -> where\n-\tPage 5 eq (5):  period instead of comma.\n-\tPage 6 Corollary 2: this should be appropriately cited since it was already proved in [25]\n-\tPage 7 line 288: $f(O_j)$\n-\tPage 7 Algorithm 5: line 11 $A_{m’}$\n-\tPage 8 Algorithm 6: lines 8 and 9 outside the if? Also, line 10 should be $A_{|J|}$ which is not necessarily $A_m$.\n-\tPage 8 Algorithm 7: $R=V’’$ not used, in the input of RR is V’ instead of V’’. Line 10 should be $A_{m’}$.\n-\tPage 9 line 361: is it a cardinality constraint?\n-\tPage 9 Figure 1: legend should say Alg 7?\n-\tAppendix line 660: We assume. Same in line 749\n-\tAppendix lines 702-721: it would be good to comment on this in the main body\n-\tAppendix: Algorithms are renumbered.\n-\tAppendix line 853: $\\{1,\\ldots,m\\}$\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "the authors address the limitations and potential negative societal impacts", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "15"}, "extra_text": {}}, {"review_id": "Mt_1QfnZYM4", "reviewer": "Reviewer_VawE", "summary": "This paper studies constrained robust submodular partitioning. Given a submodular function $f$, a constraint set family $\\\\mathcal{C}$, and the number $m$ of blocks, we are to find an $m$-partition $(X_1, \\\\dots, X_m)$ of the ground set that maximizes $\\\\min_{i=1}^m f(X_i)$ subject to $X_i \\\\in \\\\mathcal{C}$.\n\nThe main contributions of this paper are two algorithms called Min-Block Greedy and Round-Robin Greedy:\n- Min-Block Greedy achieves $\\\\alpha/(\\\\alpha m + 1)$-approximation for a general down-closed $\\\\mathcal{C}$, given an $\\\\alpha$-approximation algorithm for submodular function maximization on $\\\\mathcal{C}$.  Furthermore, the authors proved that the analysis is tight for the unconstrained case.\n- Round-Robin Greedy achieves $(1-1/e)^2/3$-approximation when $\\\\mathcal{C}$ is a cardinality constraint. It also achieves $(1-1/e)/5$-approximation when $\\\\mathcal{C}$ is a matroid.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I enjoyed reading this paper. It is surprising (to me) that this max-min type problem under a matroid constraint still admits a constant-factor approximation. Furthermore, very simple algorithms surprisingly work! I think the main results are significant.\n\nOn the other hand, the writing is not so clear in several places. I have a technical question for Algorithm 5; see below. I found several typos around the description of Round-Robin Greedy, so possibly my questions are just due to the typo.\nAnother minor complaint is: there was only a sketch of the proof rather than a formal proof for Round-Robin Greedy with the cardinality constraint. The authors should fix these issues in a future version.\n\nOverall, I believe the paper has significant contributions to submodular function maximization. But I would like to hear the authors' response before giving a high score.\n\n## Technical comment\nAlgorithm 5, line 10: Should $\\\\max_{\\\\pi \\\\in \\\\Pi(V', m', k)}$ be $\\\\max_{\\\\pi \\\\in \\\\Pi(V', m')}$? Swap rounding only applies to a single matroid constraint. However, $\\\\Pi(V', m', k)$ is not a single matroid but the intersection of two matroids.\n\n## Minor comments\n- Algorithm 6, line 4: It seems that you need to require $v \\\\in R$.\n- Algorithm 7, line 9: $V''$ is not defined. Is it the same as Algorithm 5?\n- Algorithm 7, line 10: Should $RR(f, V'', m', \\\\mathcal{M}, [m'])$ be $RR(f, R, m', \\\\mathcal{M}, [m'])$?\n- Appendix B: Proof of Round-Robin Greedy for the cardinality case is a sketch rather than a proof. You should formally prove a version of Lemma 3 of [3] involving $\\\\gamma$.\n- Appendix B, eq (55): Why do you have $F(y^0) \\\\leq \\\\frac{1-1/e}{5}OPT$ when every singleton gain is small?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "3BZxRGNhdH", "reviewer": "Reviewer_cEdN", "summary": "Provides constant approximation algorithms for certain \"robust\" or min-max submodular maximization problems. They consider cardinality and matroid constraints. Also provide good experimental results on partitioning a training dataset. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The paper is on a “robust” submodular maximization problem. There is a monotone submodular function f and matroid C on items. Allocate items to m blocks so that the items in each block are independent in C, and maximize the minimum f(S) over all blocks. \n\nThe results in the paper are-\n1)\tIf C is a cardinality constraint, there is a (1-1/e)^2/3 approximation.\n2)\tIf C is any matroid, there is a (1-1/e)/5 approximation.\n3)\tIf C is more general (with any A-approximation for submod max under C) then there is ~ A/m approximation.\n4)\tExperiments on a real-world training data set with classes, that corresponds to C = partition matroid. The proposed algorithms achieve much better objective than a random solution. They also train the partitioned data and report the test accuracy- solutions with high objective have better accuracy.\n\nI found results 1 & 2 theoretically interesting. It relies heavily on ideas for the unconstrained problem from [3] where a (1-1/e)/3 approximation was obtained. However, there are some non-trivial technical issues to deal with for the matroid constraint. The authors also emphasize that they get a strongly polynomial runtime- this just seems to use standard techniques. \n\nI do not find result 3 (in sec 2) interesting. The theoretical bound is weak (linear in #blocks), although it applies to any constraint. \n\nWhy don’t you focus on results 1-2 and provide more details in the main body? Also, does the matroid analysis extend to p-matroid intersection? \n--\nAfter the response, I still think this is a good paper.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers find that the theoretical results in this paper are strong and that there are interesting novel ideas. In particular, the reviewers agree that adding constraints to the robust submodular partitioning problem introduces significant technical challenges. Overall, this paper makes significant progress to the area of robust submodular maximization.
Decision: Accept (Spotlight)