Constrained Robust Submodular Partitioning
Year: 2022

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 ⌦(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.

heading: 1 Introduction
text: The problem of partitioning a 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 an optimization problem, partitioning aims to generate the blocks so that the utilities of the blocks, as measured by a given set function, are good. Submodular functions are a rich family of set functions that naturally captures diversity of a given set of items. They have been applied in many realworld problems [26, 30, 21, 17, 13, 18, 28]. By maximizing a 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.
For the submodular welfare problem [24], we aim to find a partition such that the sum of the 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, 29] (often called “submodular fair allocation with indivisible goods”) aims to find the partition such that the minimum-valued block in the partition is maximized according to the submodular function. The robust objective optimizes the worst block in the partition so 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 V 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 to a single machine for parallel gradient computations, and the gradients
35th Conference on Neural Information Processing Systems (NeurIPS 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
m bound for the unconstrained case is tight.
We then modify the algorithm to allow a general down-closed constraint C, and prove an approximation bound of ↵
↵m+1 , where ↵ is the bound for solving the submodular maximization problem under constraint C using a greedy based algorithm. For example, for a cardinality constraint, ↵ = 1 1/e [9], and the bound for constrained robust submodular partitioning is (m+ 11 1/e )
1. Similarly, for C as an intersection-of-p-matroids constraint, ↵ = (1 + p) 1 [10], and the bound is (m+ p+ 1) 1; for C as a knapsack constraint, ↵ = 0.5(1 1/e) [16], and the bound is (m+ 21 1/e ) 1. For Round-Robin Greedy based algorithms, when C is a cardinality constraint, we get a bound of (1 1/e) 2
3 , and when C is a matroid constraint, we get a bound of 1 1/e5 . The Min-Block Greedy approach gives a weaker bound, and since the 1
m bound for the unconstrained case is tight, we cannot improve upon the 1 m factor for the
constrained case. The Round-Robin Greedy approach gives a constant bound, but its running time is worse. The running time for Min-Block Greedy is O(n2), where n is the ground set size. For RoundRobin Greedy under a matroid constraint, the running time is O(n2(log logm+log 1 )), as it needs to use binary search to find the optimal solution value to the given problem over an exponentially decreasing sequence, with 11+ ( > 0) as the multiplicative factor. In all cases, we assume an oracle model, 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 on the unconstrained case using a Round-Robin-like algorithm have only weakly polynomial running time [3].
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-batches [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 diversity, and improving the gradients’ consistency. (2) Given an 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 so that information can be sent in parallel, and the constraint to have no 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.

heading: 2 Related Work
text: Golovin [12] introduces robust submodular partitioning (i.e., submodular fair allocation of indivisible goods), and proposes a matching-based algorithm with a bound of 1
n m+1 . Khot & Ponnuswami [14] proposes a binary search based algorithm and gives an improved bound of 12m 1 . Asadpour & Saberi [2] uses an ellipsoid approximation approach and gives a bound of ⌦( 1p
nm1/4 logn log3/2 m ). Wei et al.
[29] gives a simple Min-Block Greedy algorithm and proves a 1 m bound. A Round-Robin Greedy approach is given in [3] with a bound of 1 e 1
3 . Ghodsi et al. [11] proposes a local search algorithm with a bound of 13 . Both [3] and [11] requires guessing of the optimal solution value from an exponentially decreasing sequence of values, so strictly speaking, they lose an extra (1+ )-factor in the approxima-
tion bound where (1 + ) is the exponential factor for the guessing sequence. We can set the value small to 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 Greedy approach [3] 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 a special case of our work as it only studies the cardinality constraint. Cotter et al. [8] studies (as well as allowing multiple blocks to be jointly scored) a matroid constrained “groupings” (i.e.,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-valued block in the partition according to 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 [22] shows a information theoretical lower bound of o( q n
logn ), and also gives a sampling algorithm to match the lower bound up to constant factors. Similar to the max-min case, Ghodsi et al. [11] uses the ellipsoidal approximation to get a bound of O( p n log n). Wei et al. [29] gives a Lovász extension based relaxation algorithm and achieves a bound of m.

heading: 3 Preliminaries and Formulation
text: With a ground set V of n items, a submodular function f is a set function 2V ! R that satisfies the property: f(A) + f(B) f(A [ B) + f(A \ B), where A,B ✓ V . Equivalently, a submodular function is characterized by diminishing returns: f(v|A) f(v|B) 8v /2 B and A ⇢ B ✓ V , where f(v|B) = f({v} [B) f(B). Submodular functions naturally describe the diversity or representativeness of a given set of items. Many simple greedy-based algorithms have been developed to solve optimization problems involving submodular functions, giving both theoretical approximation guarantees, as well as good empirical performance. We restrict the submodular functions discussed in this paper to be monotone non-decreasing and normalized, i.e., f(B) f(A) 8A ✓ B ✓ V , f(;) = 0.
A matroid M = (V, I) is a set system that describes the independence relationships among the subsets of the ground set V . I is a set of subsets of V and every S 2 I is considered an independent subset. The matroid rank function is defined as rM(A) = max{|S| : S ✓ A,S 2 I}. rM(V ) indicates the maximum size of a subset that may be independent according to the matroid M. All subsets of cardinality  k with some integer k > 0 form a uniform matroid, which we denote by Mu
k .
A 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 V1 = V2 = . . . Vm = V , which are ground set copies. We create an expanded ground set V̄ = ]j=1:mVj as the disjoint union. A subset S ✓ V̄ is independent in Mpm if for every element v 2 V , let its m copies in V̄ be {v1, v2, . . . , vm}, we have |S \ {v1, v2, . . . , vm}|  1, i.e., S 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 linearly-independent set of real vectors and the spanning trees in a graph. In the below, we use both S 2 M and, when clear, S 2 I, to indicate that S is independent in the matroid M = (V, I).
Matroids are often used as constraints in submodular optimization problems: maxS2I f(S) with a matroid M = (V, I). When M is a uniform matroid Mu
k , this reduces to the cardinality submodular
max and the greedy algorithm gives a 1 e 1 bound [9]. For a general constraint with the intersection of p matroids, the simple greedy algorithm gives a 1
p+1 bound [10]. Suppose we represent a set S as a binary indicator vector xS 2 {0, 1}n, i.e., 8i 2 [n], xS [i] = 1 if vi 2 S or otherwise xS [i] = 0. Then for all the independent sets of a matroid M = (V, I), the convex hull over all the xS , S 2 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 [4–6, 24] 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]n, and then round the fractional solution to an integral solution to get the resulting set. The continuous greedy algorithm [4] gives a 1 e 1 guarantee under a single
matroid constraint using pipage rounding [1, 4]. 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 = ( 1
m , 1 m , . . . , 1 m ) (i.e., assigning 1 m of every
element to each block) leads to a 1 e 1 bound in expectation for an integral solution that assigns 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 [3], which we will discuss in more detail later.
For a submodular function f on a ground set V , the robust submodular partition problem (submodular fair allocation) [12] is defined as:
max ⇡2⇧(V,m) min A2⇡ f(A), (1)
where m is the number of blocks in a partition, we denote all possible partitions with m blocks of ground set V as ⇧(V,m), and one partition ⇡ with |⇡| = m is a collection of m disjoint sets. Equivalently, we can represent the partition using a partition matroid constraint on the expanded ground set V̄ :
max S✓V̄ ,S2Mpm min j2[m] f(S \ Vj). (2)
Intuitively, the above optimization for robust submodular partitioning encourages the minimumvalued block to have a 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. (1). Particularly, Wei et al. [29] 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 Round-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. [11] applies a local search approach, which starts with an arbitrary partition and keeps moving an element from a non-minimum block to the minimum block if this relocation improves the objective by certain threshold until no such element can be found.
For [3] and [11], they both require guessing the optimal solution’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⇡2⇧(V,m) minS2⇡ f(S). With the exponential decreasing factor as 1 + , the running time (in terms of submodular function calls) is O(n2 1 log f(V )
µ ) for [3], and O(n2m2 1 log f(V ) µ ) for [11]. Min-Block Greedy, a much
simpler algorithm, has a running time of O(n2). Note that the settings of [3] and [11] are slightly more general than Eq. (1) 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.

heading: 3.1 Discussions about the Optimality in [3, 11] and the Heterogeneous Case
text: The works [3, 11] both study the partitioning problem in the economics context of fair allocation of indivisible goods. In such a setting, every block is 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 [3] as an example, the theoretical guarantee they prove is Lemma 1 (Theoretical Guarantee in [3]). Let A1, A2, . . . , Am be the solution to the Round-Robin Greedy algorithm for the unconstrained problem, and given m submodular functions for the m blocks as fj for j = 1, 2, . . .m, for every agent j we have fj(Aj) 1 e 1
3 max⇡2⇧(V,m) minS2⇡ fj(S).
Intuitively, the bound guarantees that based on each agent’s evaluation fj , the goods allocated to himself is not bad compared to the worst block in the allocation. When all the fj’s are the same, the bound reduces to 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 is Aj for j 2 [m])
min j2[m] fj(Aj) max ⇡2⇧(V,m) min S2⇡ fj(S). (3)
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 C1, C2, . . . , Cm and [j2[m]Cj = V , Cj \ Cj0 = ;, |Cj | = |Cj0 | (assume |V | is a multiple of m). Let fj(S) = |S \ Cj |. The optimal solution to the heterogeneous case max⇡2⇧(V,m) minj2[m] fj(Aj) is to assign the items in the same way as the predefined partition C1, C2, . . . Cm, and the optimal solution value is |Cj |. However, for the bound in [3, 11], the optimal solution {O1, O2, . . . , Om} 2 argmax⇡2⇧(V,m) minA2⇡ fj(A) is to intersect each predefined block equally, i.e., |Oj \ Cj0 | = |Cj0 | m 8j, j 0 2 1, . . . ,m. Therefore, the optimal solution value is then |Cj | m .
In this work, we study the constrained case for the submodular robust partition problem in the homogeneous setting (submodular functions for all blocks are the same). We extend Min-Block Greedy algorithm [29] and Round-Robin Greedy algorithm [3] to adapt to various constraints, e.g., cardinality, matroid, and intersection of matroids.

heading: 4 Min-Block Greedy Based Algorithms
text: Wei et al. [29] proposes a Min-Block Greedy Algorithm 2 for Eq. (1), which loops over n iterations, and at every iteration, for the minimum-valued block Aj⇤ 2 argminj f(Aj), it finds the element with the largest gain f(v|Aj⇤). Wei et al. [29] proves a 1/m bound of Min-Block Greedy. In fact, their proof works for a simpler algorithm, Min-Block Streaming Algorithm 1, which assumes that the algorithm accesses elements from the ground set in an arbitrary order as a stream V = (v1, v2, . . . , vn), and it assigns the incoming element to the block with the least evaluation. We denote the optimal partition to Eq. (1) as ⇡⇤ = {O1, O2, . . . , Om}. Lemma 2 (Unconstrained Min-Block Streaming[29]). For a ground set V and its elements (v1, v2, . . . , vn) coming in an arbitrary streaming order, the output solution of Alg. 1 has minj2[m] f(Aj) 1 m minj2[m] f(Oj).
Corollary 1 (Unconstrained Min-Block Greedy[29]). The output solution of Alg. 2 has minj2[m] f(Aj) 1 m minj2[m] f(Oj) since the order of adding elements in Min-Block Greedy is one possible order of the ground set elements.
Intuitively, Alg. 2 optimizes the objective Eq. (1) greedily, i.e., it always increases the current value (the minimum-block evaluation) with the largest possible gain, while the performance of Alg. 1 greatly depends on the order of elements, so it might seem that the bound for Min-Block Greedy should improve upon the current 1
m bound. However, as shown in our new result in the following
lemma, the bound in Corollary 1 is tight. Lemma 3 (Tightness of Corollary 1 ). 8✏ > 0, 9 a submodular function f such that the output solution of Alg 2 minj=1:m f(Aj) = 1m minj=1:m f(Oj) + ✏.
Algorithm 1: Min-Block Streaming input : submodular function f , ground
set as a stream V = (v1, v2, . . . , vn), number of blocks m
1 R := V ; 2 Let A1 = A2 = . . . = Am = ;; 3 for i = 1 : n do 4 j⇤ 2 argminj f(Aj); 5 Aj⇤ := Aj⇤ [ {vi} ; 6 return (A1, A2, . . . , Am)
Algorithm 2: Min-Block Greedy input : submodular function f , ground
set V , number of blocks m 1 R := V ; 2 Let A1 = A2 = . . . = Am = ;; 3 while R 6= ; do 4 j⇤ 2 argminj f(Aj); 5 v⇤ 2 argmaxv2R f(v|Aj⇤); 6 Aj⇤ := Aj⇤ [ {v⇤} ; 7 R := 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 a 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 f(v|A) is larger than f(v0|A) for v0 2 R \ v. However, f(v|A)
f(v) 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
other hand, the optimal solution can fully utilize f(v) thus making a more lonesome v cover a much larger area overall. Note that Lemma 3 also serves as the tightness for Lemma. 2 since the order of adding elements in Min-Block Greedy follows a streaming order.
More generally, given a constraint C, we define the constrained robust submodular partition as:
max ⇡2⇧(V,m,C) min A2⇡ f(A), (4)
where ⇧(V,m, C) is the set of all possible partitions on set V into m blocks such that for every partition ⇡ 2 ⇧(V,m, C), every block A 2 ⇡ should satisfy the constraint A 2 C. We denote the optimal partition in Eq. (4) as ⇡⇤
C = {OC1 , O C 2 , . . . , O C m }. 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. [8]) of elements rather than a partition.
For now, we will take C as any down-closed constraint: Let C be a 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 2 C we have B 2 C for any B ✓ A. Following Eq. (4), we can define the constrained problem in terms of the expanded subset V̄ :
max S✓V̄ ,S2Mpm,8j:(S\Vj)2C min j2[m] f(S \ Vj). (5)
Based on the Min-Block Greedy algorithm for the unconstrained case, we propose a natural extension to the constrained case (Alg. 3), where at every iteration, for the minimum-valued block Aj⇤ , we greedily find the best element v⇤ that retains block feasibility under the constraint C, i.e., {v⇤}[Aj⇤ 2 C. If we cannot find any element in the remaining set to add to the current minimum block, we remove the current block from the candidate blocks and move to the next smallest valued block.
In Line 6 of Alg. 3, we call a subroutine GreedyStep(R, C, Aj⇤) to greedily find a feasible element. The subroutine varies according to the type of constraint C. Particularly, for the constrained submodular maximization problem defined as
max S✓V,S2C f(S). (6)
GreedyStep(·) is shared by Alg. 3 and Alg. 4, and if Alg. 4 is an approximation algorithm of solving Eq. (6) with some bound ↵, we can prove the following result for Alg. 3.
Algorithm 3: Constrained Min-Block Greedy input : submodular function f , ground set V ,
number of blocks m, constraint C 1 Let A1 = A2 = ... = Am = ;; 2 Let J = [m], R = V ; 3 while R 6= ; and J 6= ; do 4 j⇤ 2 argminj2J f(Aj); 5 if 9v 2 R s.t. Aj⇤ [ {v} 2 C then 6 v⇤ := GreedyStep(R, C, Aj⇤); 7 Aj⇤ := Aj⇤ [ {v⇤}, R := R \ {v⇤}; 8 else 9 a⇤ 2 argmaxa2Aj⇤[R f({a});
10 if f({a⇤}) f(Aj⇤) then 11 Aj⇤ := {a⇤}, R := R \ {a⇤} ; 12 Let J = J \ j⇤; 13 return (A1, A2, ..., Am)
Algorithm 4: Constrained Submodular Greedy Max input : submodular function f , ground
set V , constraint C 1 R := V ; 2 Let Sg = ;; 3 while R 6= ; do 4 if 9v 2 R s.t. Aj⇤ [ {v} 2 C then 5 v⇤ := GreedyStep(R, C, Sg) ; 6 Sg := Sg [ {v⇤} ; 7 R := R \ {v⇤}; 8 else 9 Break;
10 a⇤ 2 argmaxa2V f({a}); 11 return argmaxA2{Sg,{a⇤}} f(A)
Theorem 1 (Constrained Min-block Greedy). Given a constraint C, if the greedy solution Sg to problem maxS2C f(S) using Alg. 4 has a bound of ↵, i.e., f(Sg) ↵maxS2C f(S), then the solution of Alg. 3 has minj2[m] f(Aj) ↵↵m+1 minj2[m] f(O C j ). Assuming GreedyStep(·) takes O(1) oracle calls, the time complexity of of Alg. 4 is O(n2).
The general idea of the proof (details in Appendix A) is that we divide the ground set V into two disjoint parts V = V 0 [R0, where the min block in the output solution A intersecting V 0 corresponds
to the min block solution of an instance of unconstrained robust partition problem (Eq. (1)) defined on the ground set V 0, and A \ R0 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 [ R0. We bound the two parts separately and combine them to obtain the above bound. Corollary 2 (Cardinality Constrained Min-block Greedy). For C as a cardinality constraint, the output of Alg 3 has minj=1:m f(Aj) 1
m+ 1 1 e 1
minj=1:m f(OCj ).
Corollary 3 (Matroid Constrained Min-block Greedy). For C as an intersection of p matroids constraint, the output of Alg 3 has minj=1:m f(Aj) 1m+p+1 minj=1:m f(O C j ).
Corollary 4 (Knapsack Constrained Min-block Greedy). For C as a knapsack constraint, the output of Alg 3 has minj=1:m f(Aj) 1
m+ 21 1/e minj=1:m f(OCj ).
For C as a 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 f(v⇤|Aj⇤) assuming the block can be kept feasible, i.e., v⇤ [Aj⇤ 2 C. For C as a knapsack constraint with the weight of each element v as w(v), GreedyStep(·) finds the element v⇤ with the largest ratio f(v
⇤|Aj⇤ ) w(v) 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 ↵ is unbounded. Due to the tightness of the 1
m bound we have proved for the unconstrained case, the 1 m
dependence in the constrained bound cannot be improved.

heading: 5 Round-Robin Greedy Based Algorithms
text: Barman & Krishna Murthy [3] propose a round-robin style algorithm for the unconstrained robust submodular partition problem (Eq. (1)) and gives a constant bound of 1 e 1
3 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, it runs one instance of the round-robin subroutine. Specifically, suppose µ = minj2[m] f(Oj), i.e., µ is the optimal solution value for the unconstrained case, then for a parameter > 0, Round-Robin Greedy runs the round-robin subroutine with the guessed optimal values from a sequence (f(V ), f(V )1+ , f(V ) (1+ )2 , . . .) and ends when the guessed value is no larger than µ. The running time of each round-robin subroutine is O(n2), as it greedily finds the element with the largest gain by iterating over all the remaining elements. There are log1+ f(V ) µ guessed values in the exponentially decreasing sequence, so the overall running time is O(n2 log1+ f(V ) µ ) = O(n2 1 log f(V ) µ ). Note that since we use a (1 + ) factor exponentially decreasing sequence, we lose a (1 + ) factor in the approximation bound, which can be improved arbitrarily by using a smaller 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 = ( 1
m , 1 m , . . . , 1 m ) with the
length of x equal to the size of the expanded ground set |V̄ |. Let F be the multilinear extension [4] of f , Continuous Greedy gives a bound that F (x) = ER⇠x f(R) (1 e 1)max⇡2⇧(V,m) P A2⇡ f(A), where ER⇠x 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 x. 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-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 a 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-Robin Greedy bounds every block Aj to be f(Aj) 13 F (x) m
, and since the welfare solution bounds the robust solution in terms of the sum: max⇡2⇧(V,m) P A2⇡ f(A) P
j2[m] Oj mµ, we get the desired bound for the robust partition problem.
We extend Round-Robin Greedy to the constrained case (Eq. (4)) firstly with C as a cardinality constraint k. This is a relatively simple case due to the nature of Round-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. (4), with C as a cardinality constraint k, Alg. 5 gives a solution minj2[m] f(Aj) (1 e 1)2 3 minj2[m] f(O k j ).
Algorithm 5: Cardinality Round-Robin Greedy input : f , V , m, cardinality constraint k, discounting factor for guessing optimal 1 Let ⌧ be the solution value of Alg. 3; 2 Let high = dlog1+ (m+ 2)e, low = 0; 3 Create a sequence of guessed values: (⌧, (1 + )⌧, (1 + )2⌧, . . . , (1 + )high⌧); 4 Create an empty solution (; for each block in the partition) for each guessed value
⇡0,⇡1, . . . ,⇡high ; 5 while high low do 6 Let idx = b(high + low)/2c; Let A1 = A2 = . . . = Am = ;; 7 Let V 0 = {v|v 2 V, f(v)  (1 e 1)2
3 (1 + ) idx ⌧}; Let G = V \ V 0; 8 Assign G to Am |G|+1, Am |G|+2, . . . , Am with one element per block; 9 Let m0 = m |G|;
10 Let A01, A02, . . . , A0m0 be the solution to max⇡2⇧(V 0,m0,k) P
S2⇡ f(S) using continuous greedy and swap rounding; Let V 00 = [j2[m]0A0j ;
11 Let {A1, A2, . . . , Am0} = RR(f, V 00,m0,Muk , [m 0]); 12 if f(Aj) (1 e 1)2 3 (1 + ) idx
⌧ 8j 2 [m0] then 13 Let ⇡idx = {A1, A2, . . . , Am}; Let low = idx + 1; 14 else 15 Let high = idx 1; 16 return best of ⇡0,⇡1, . . . ,⇡high ;
Algorithm 6: Round-Robin Greedy Iterations (RR(f,R,m0,M, J)) input : f , R, m0, matroid constraint M,
set of block indices J 1 while J 6= ; and R 6= ; do 2 for j 2 [m0] do 3 if j 2 J then 4 if 9v 2 R s.t. Aj [ {v} 2 M then 5 v⇤ 2
argmax v2R,Aj[v2M f(v|Aj);
6 Aj := Aj [ {v⇤} ; 7 R := R \ {v⇤}; 8 else 9 Let J = J \ j;
10 return (A1, A2, . . . , Am0)
Here is how we achieve strongly-polynomial time. 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 Min-Block Greedy solution’s value as the minimum guessed value ⌧ . Because of the 1
m+ 11 1/e bound of the Min-
Block Greedy solution, the maximum guessed value is thus bounded by (m+2)⌧ . We then create a 1+ - factor exponential decreasing sequence between ⌧ and (m+2)⌧ to binary search for the optimal solution value. This improves the number of outer iterations of the algorithm to O(log log1+ m) = O(log logm + log 1 ), which is strongly-polynomial while the num-
ber of outer iterations O(log1+ f(V ) µ ) for the original unconstrained case is only weakly-polynomial as it has a log dependence on the function value.
In every outer iteration (Line 12-15), Alg 5 checks if the round-robin solution based on the guessed optimal value (1 + )idx ⌧ satisfy the approximation bound, i.e., f(Aj) (1 1/e)2 3 (1 + ) idx ⌧ 8j 2 [m]0. 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. 5 is the major change to Round-Robin Greedy specifically for the cardinality constraint case, where we first find the solution to the cardinality constrained submodular
welfare problem max⇡2⇧(V 0,m0,k) P
S2⇡ f(S), and then only apply Round-Robin Greedy to the union V 00 of the solution A01, A02, . . . , A0m0 .
The running time of Alg. 5 is similar to Round-Robin Greedy, with additional costs caused by Line 10, which solves a cardinality constrained submodular welfare problem. Using Continuous Greedy and swap rounding [7] for Line 10 can be quite costly (O(n5) for the inner loop), which may improve in the future by a better algorithm. In Alg. 7, 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-Robin). For the problem in Eq. (4), with C as any matroid constraint M, Alg 7 gives a solution minj2[m] f(Aj) (1 e 1) 5 minj2[m] f(O M j
). The time complexity of of Alg. 7 is O(n2(log logm+ log 1 )).
Algorithm 7: Matroid Round-Robin Greedy input : f , V , m, matroid constraint M, discounting factor for guessing optimal
1 Let ⌧ be the solution value of Alg. 3; 2 Let high = dlog1+ (m+ 2)e, low = 0; 3 Create a sequence of guessed values: (⌧, (1 + )⌧, (1 + )2⌧, . . . , (1 + )high⌧); 4 Create an empty solution (; for each block in the partition) for each guessed value
⇡0,⇡1, . . . ,⇡high ; 5 while high low do 6 Let idx = b(high + low)/2c; Let A1 = A2 = . . . = Am = ;; 7 Let V 0 = {v|v 2 V, f(v)  1 e 1
5 (1 + ) idx ⌧}; Let G = V \ V 0; 8 Assign G to Am |G|+1, Am |G|+2, . . . , Am with one element per block; 9 Let m0 = m |G|;
10 Let {A1, A2, . . . , Am0} = RR(f, V 0,m0,M, [m0]); 11 if f(Aj) (1 e 1) 5 (1 + ) idx ⌧ 8j 2 [m0] then 12 Let ⇡idx = {A1, A2, . . . , Am}; Let low = idx + 1; 13 else 14 Let high = idx 1; 15 return best of ⇡0,⇡1, . . . ,⇡high ;
Comparing to Alg. 5, the major change in Alg. 7 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 a 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 a feasible element until every block has k elements. The overall running time is O(n2(log logm+log 1 )). 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, we inspect the elements that have been evaluated during the greedy step. For those elements with large gains when being evaluated but not added due to the violation of the matroid constraint, we bound 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.

heading: 6 Experiments
text: We empirically test Algs. 3 and. 7 on the CIFAR-10 training set [19] (|V | = 50000). We use facility location as our submodular function, i.e., f(S) = P v2V maxv02S sim(v, v
0), where sim(v, v0) measures the affinity between elements v and v0. This function is widely used and naturally describes a subset’s diversity via its similarities/distances 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 L2 distances, i.e., sim(v, v0) = exp( ||v v 0||2
), where is the bandwidth of the kernel, set to the average L2 distance, i.e., = P v,v02V ||v v 0 ||2/n
2. 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. (4)) with a matroid constraint where we limit the number of samples selected for each class in CIFAR-10 for each block (CIFAR-10 has 10 classes). We compare the two algorithms with a random selection baseline — we randomly sample from each class and assign to each block with the constrained number of elements. Hence, the random selection results satisfy the constraints. In Fig. 1, we report the results for different matroid constraints with various block sizes. The random baseline results are reported with means and standarddeviations over 10 runs. For all cases, we see that both Alg. 3 and Alg. 7 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. 3 to perform better in practice compared to Alg. 7 as Alg. 7 has a fixed ordering of the blocks, and the minimum-valued block tends to be 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 to train a ResNet-9 model and compare their performance on the
test set. We observe that the blocks with higher submodular evaluations tend to generate better performance for the trained model. We also provide results on synthetic data in Appendix Section C.

heading: 7 Conclusions
text: 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 to 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 a different submodular function. Given the good performance of Alg. 3 in practice, it is worth investigating if further conditions or modifications to Alg. 3 yield improved theoretical 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.

Review summaries:
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. 

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}$.  The main contributions of this paper are two algorithms called Min-Block Greedy and Round-Robin Greedy: - 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. - 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.

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.  The 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. 

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.  1- 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.  2- 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.