Using Partial Monotonicity in Submodular Maximization
Authors: Loay Mualem
Moran Feldman
Venue: NeurIPS 2022 Accept (2022)
Keywords: submodular maximization
non-convex optimization
monotonicity ratio
cardinality constraint
matroid constraint
movie recommendation
image summarization

Abstract: Over the last two decades, submodular function maximization has been the workhorse of many discrete optimization problems in machine learning applications. Traditionally, the study of submodular functions was based on binary function properties, but recent works began to consider continuous function properties such as the submodularity ratio and the curvature. The monotonicity property of set functions plays a central role in submodular maximization. Nevertheless, no continuous version of this property has been suggested to date (as far as we know), which is unfortunate since submoduar functions that are almost monotone often arise in machine learning applications. In this work we fill this gap by defining the monotonicity ratio, which is a continuous version of the monotonicity property. We then show that for many standard submodular maximization algorithms one can prove new approximation guarantees that depend on the monotonicity ratio; leading to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming, image summarization and ride-share optimization.

Using Partial Monotonicity in Submodular Maximization
Loay Mualem
Moran Feldman
Department of Computer Science
Department of Computer Science
University of Haifa
University of Haifa
Haifa 3303221, Israel
Haifa 3303221, Israel moranfeccs haifa. ac
loaymua@gmail.cmm
Abstract
Over the last two decades, submodular function maximization has been the workhorse of many discrete optimization problems in machine learning appli- cations. Traditionally, the study of submodular functions was based on binary function properties, but recent works began to consider continuous function proper- ties such as the submodularity ratio and the curvature. The monotonicity property of set functions plays central role in submodular maximization. Nevertheless, no continuous version of this property has been suggested to date (as far as we know), which is unfortunate since submoduar functions that almost monotone often arise in machine learning applications. In this work we this gap by defining the monotonicity ratio, which is continuous version of the monotonicity property. We then show that for many standard submodular maximization algorithms one can prove approximation guarantees that depend the monotonicity ratio; leading to improved approximation ratios for the common machine learning applications of movie recommendation, quadratic programming, image summarization and ride-share optimization.
Introduction
Over the last two decades, submodular function maximization has been the workhorse of many discrete optimization problems in machine learning applications such as data summarization [17
19
32
50 social graph analysis 45), adversarial attacks (36], dictionary learning [15],
sequence selection
42 51].
interpreting neural networks [18] and many more. Traditionally, the
study of submodular functions was based binary properties of functions. function can be either submodular or non-submodulaar, monotone or non- monoonnte,,, etc. Such properties are simple, but they have an inherit weakness- if algorithm assumes functions that have a particular property, then it provides no guarantee for functions that violate this property, even if the violation is slight.
Given the above situation, recent works began to consider continuous versions of function properties. Probably the most significant among these continuous versions so far are the submodularity ratio and the curvature. The submodularity ratio (originally defined by Das and Kempe (16) is parameter E [0, 1] replacing the binary submodularity property that a set function can either have or not have. A value of 1 corresponds to fully submodular function, and lower values represent some violation of submodularity (the worse the violation, the lower 7).. Similarly, the curvature (defined by Conforti and Cornuéjol (13) a parameter e e [0, 1] replacing the binary linearity property that a set function can either have or not have. A value of corresponds to a fully linear function, and lower values of represent some violation of linearity.
central conceptual contribution of Das and Kempe [16] was that they were able to demonstrate that continuous function properties further extend the usefulness of submodular maximization new
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

machine learning applications (such as subset selection for regression and dictionary selection). This 34 for a few examples), including works that combine both the submodularity ratio and the curvature (see, e.g.. ( However, to the best of our knowledge, no continuous version of the binary monotonicity property has been suggested so far See Appendix A for additional related work.
has motivated long list of works on such properties (see [ 23 26
29
We note that the monotonicity property of set functions plays a central role in submodular maximiza- tion, and basically every problem in this field has been studied for both monotone and non-monotone objective functions. Naturally, monotone objective functions enjoy improved approximation guaran- tees compared to general functions, and it is natural to ask how much of this improvement applies also to functions that are almost monotone (in some sense). Since such functions often arise in machine learning applications when a diversity promoting component is added to basic monotone objective, obtaining better guarantees for them should strongly enhance the usefulness of submodular maximization as a tool for many machine learning applications.
function f: 2 + R20 over ground set N is (increasingly) monotone if f(S) S f(T) for every S C ''" C N. Similarly, we define the monotonicity ratio of such function as the maximum value Equivalently, one can define the monotonicity ratio by m a minscrcx(f(T)//fe
Formally, a non-negative
[0, 1] such that m f(S) S f(T) for every two S T W.
where the ratio (S)) is assumed to be 1 whenever [(S = 0. Intuitively, the monotonicity ratio measures how much of the value of set can be lost when additional elements are added to S. One can view m as the distance of f from monotonicity. In particular, m = 1 if and only if f is monotone.
Our main contribution in this paper is demonstrating the usefulness of the monotonicity ratio in machine learning applications, which we do in two steps.
First, we show (in Sections 3 and 5) that for many standard submodular maximization algorithms one can prove new approximation guarantees that depend on the monotonicity ratio. These approximation guarantees interpolate between the known approximation ratios of these algorithms for monotone and non- monooone submodular functions.
Then, using the above new approximation guarantees, we derive new approximation ratios for the standard applications of movie recommendation, quadratic programming, image summarization and ride-share optimization. Our guarantees improve over the state-of-the-art for most values of the problems' parameters. See Section for more detail.
Remark. Computing the monotonicity ratio m of a given function seems to be difficult. Thus, the algorithms we analyze avoid assuming access to m, and the value of is only used in the analyses of these algorithms. Nevertheless, in the context of particular applications, we are able to bound m, and plugging this bound into our general results yields our improved guarantees for these applications.
1.1 Our Results
Given a ground set W, a set function f: 2 R is submodular if ((S) > S(TU {u)) /(T) for every two sets S C N and element u E N T. Submodular maximization problems ask to maximize such functions subject to various constraints. To allow for multiplicative approximation guarantees for these problems, it is usually assumed that the objective function is non-negative. Accordingly, we consider in this paper the following three basic problems.
Given a non-negative submodular function f: 2 + R, find a set S C W that (approxi- mately) maximizes f. This problem is termed "unconstrained submodular maximization", and is studied in Section K
Given non-negative submodular function f: 2 + R and integer parameter 0 < k < [V]. find set S C N of size at most & that (approximately) maximizes f among such sets. This problem termed "maximizing a submodular function subject to a cardinality constraint", and is studied in Section
Given non- non-negative submodular function f: 2 IR and a matroid M over the same ground set, find a set S C N that is independent in M and (approximately) maximizes f
Following the appearance of the pre print version of this paper, we learned that Iyer defined in his Ph.D. thesis (30) such property, which is identical to the one we define. However. Iyer only used this property to prove the result appearing below Theorem 4.1 thus, work is the first to systematically study this property.

---

among such sets. This problem is termed "maximizing submodular function subject to matroid constraint", and studied in Section (see Section for the definition of matroids).
(see
We present both algorithmic and inapproximability results for the above problems. Our algorithmic results reanalyze a few standard algorithms, and surprisingly show that almost all these algorithms guarantee an approximation ratio of m Ommn + (1 -1- -m) -nnon-mo-- where m is the monotonicity ratio, Omon is the approximation ratio known for the algorithm when f is monotone, and Ononn-mon is the approximation ratio known for the algorithm when f is general non-negative submodular function.
While the above mentioned algorithmic results lead to our improved guarantees for applications, inapproximability results represent our main technical contribution. In general, these results based on the symmetry gap framework of Vondrák [52]. The original version of this framework is able to deal both with the case of general (not necessarily monotone) submodular functions, and with the case of monotone submodular functions; which in our terms correspond to the cases of m 2 O and 2 1, respectively. However, to prove our inapproximability results, we had to show that the framework extends to arbitrary lower bounds on m, which was challenging because the original proof of the framework is highly based on derivatives of continuous functions. From this point of view, submodularity is defined as having non-positive second-order derivatives, and monotonicity is defined as having non-negative first-order derivatives, However, the definition of the monotonicity ratio cannot be easily restated in terms of derivatives? and thus, handling it required us to come up with a different proof approach.
Interestingly, our results for unconstrained submodular maximization proves that the optimal ap- proximation ratio for this problem does not exhibit linear dependence on m. Thus, the nice linear dependence demonstrated by almost all our algorithmic results is probably an artifact of looking at standard algorithms rather than representing the true nature of the monotonicity ratio, and we expect future algorithms tailored to take advantage of the monotonicty ratio to improve over this linear dependence. The reason that we concentrate in this work on reanalyzing standard submodular maximization algorithms rather than inventing new ones is that we want to stress the power obtained by using the new notion of monotonicity ratio, as opposed to power gained via new algorithmic innovations. This is in line with the research history of the submodularity ratio and the curvature. For both of these parameters, the original works concentrated on reanalyzed the standard greedy algorithm in view of the new suggested parameter; and the invention of algorithms tailored to the parameter was deferred to later works (see [49] and 12] for examples of such algorithms for the curvature and submodularity ratio, respectively).
Over the years, the standard submodular maximization algorithms have been extended and improved in various ways. Some works presented accelerated and/or parallelized versions of these algorithms, while other works generalized the algorithms beyond the realm of set functions (for example, to (R--)subooulla functions over lattices or continuous domains). Since our motivation in this paper is related to the monotonicity ratio, which is essentially independent of the extensions and improvements mentioned above, we mostly analyze the vanilla versions of all the algorithms considered. This keeps our analyses relatively simple. However, our experiments are based on more state-of-the-an versions of the algorithms. Similarly, many continuous properties (including the submodularity ratio) have weak versions that only depend on the behavior of the function for nearly feasible sets, and immediately enjoy most of the results that apply to the original strong property. The definition of such weak versions is useful for capturing additional application, but often add little from a theoretical perspective. Therefore, in the theoretical parts of this paper we consider only the monotonicity ratio as it is defined above; but for the sake of one of our applications we later define also the natural corresponding weak property.
2 Preliminaries and Basic Observations
In this section we define the notation used in this paper, and then state some useful basic observations. Given element E A and set S C N, we use S + and S - shorthands for S SU {u} and S {u]. Additionally, given set function f: 2N - R. we define f(u () A s(S +w) - (SS)tthis value is known as the marginal contribution of to S with respect to f. Similarly, given an additional
"To see why that is the case, notice that function can have monotonicity ratio close to 1, even in the presence of very negative derivatives, as long these derivatives do not occur over too long sections.
3

---

set T S ., we define f(T S) - f(SUT)- f(S). We also use 1ş to denote the characteristic vector of the set i.e.. a vector in [o, 1| that has 1 in the coordinates corresponding to elements that appear in S and 0 to the other coordinates. Finally, if f is non-negative, we say that it is m- m--monotone its monotonicity ratio is at least m; and given an event &, we denote by [[ the indicator of this event, i.e., a random variable that takes the value when the event happens, 0 otherwise.
Next, we present well-known continuous extension of set functions. Given set function f: 2 R. its multilinear extension is a function P: [0, 1 + I defined as follows. For every vector x e [0. 1|M,, let B(x) to random subset of N that includes every element u N with probability Tu. independently. Then, F(x)= [[ Another extension of set functions is central to the proof of the next lemma, which generalizes Lemma 2.2 of [6] see Appendix for the proof.
Lemma 2.1. Let f 2N + Rzz be a non-negative m-monntone submodular functttoo For every deterministic set O S N and random set D S N. BIJ(OU 2 (1 -1-0 -1 m) maxueN Pr|u DI) f(O).
We conclude this section with the following observation, which we view as evidence that the class of non-negative m-monotone functions is a natural class for every m E [0, 1].
Observation 2.2. For every two non-negative m-monotone functions f.g: 2N - RR>0 and constant e 2 O, the following functions are also m-monotone: (i) h(()) = f(S) + g(5), (ii) h(S) = f(S) + and (iii) h(S) c. ((S).
3 Unconstrained Maximization
Recall that in the unconstrained submodular maximization problem, we are given a non-negative submodular function f: 2 - R20. and the objective is to find set S C / that (approximately) maximizes f(S). Buchbinder et al. (7] gave the first 1/2-approximation algorithm for this problem, known as the (randomized) double greedy algorithm. As its name suggests, double greedy maintains two solutions: one starting as the empty set, and one starting as the entire ground set. Then, it considers all elements, and greedily decides for each element either to add to the originally empty set, or remove it from the other set. When the algorithm terminates, the two sets are identical, and their common value is the output of the algorithm. The 1/2-approximation guarantee of double greedy is known to be optimal in general due to matching inapproximability result due to Feige et al. [21]. Nevertheless, this section we determine the extent to which one can improve over this guarantee as a function of the monotonicity ratio m of
Theorem 3.1. The double greedy algorithm of Buchinder al. [Z] guarantees [1/(2 m)]- approximation for unconstrained submodular maximization, and no polynomial time algorithm obtains an approximation ratio of 1/(2 m) + for any constant 0F
Interestingly, Theorem 3.1 shows that the optimal approximation ratio for unconstrained submodular maximization does not have a linear dependence on m. The first part of Theorem 3.1 is proved in Appendix C. Below, we concentrate on proving the second part of Theorem 3.1 We do this using a generalization of the symmetry gap framework of Vondrák (52 that is informally stated as Theorem 3.2 (see Appendix C.2 for the formal statement of the theorem). The fractional solution mentioned in this informal statement is evaluate using the multilincar extension of the submodular objective function.
Theorem 3.2. Consider non-negative m-monotone submodular function f and a collection F C 2N of feasible sets such that the problem max(f [S F} is symmetric with respect to some group of permutations over N. If the best fractional solution for this problem which is symmetric with respect to G is worse by a factor o compared to the optimal solution, then we say that the problem has a symmetry gap of 7/. In this case, exponentially many value oracle queries are required to obtain (1 + app-opproxnnttion for the class of problems fax( S E F} in which is non negatiie m m-monotone submodular function, and F is some generalization of F (in particular, if F is a matroid/cardinalin constraint, then so is F).
"In the second part of Theorem 3.1 like in all the other inapproximability results in this paper, we make the standard assumption that the objective function f can be accessed only through value oracle that given set S A returns f(S).

---

To use Theorem 3.2
we need to define submodular maximization problem with a significant
symmetry gap. Let us choose N {u, 2) f(S) = m 1[ * +1 m)) (IS) mod 2) and F 2N, where is an arbitrary constant m E [o. 1]. One can verify that f is submodular and non-negative, that its monotonicity ratio is exactly m, and that the problem max( S E F} is symmetric with respect to the group G of the two possible permutations of N. The following lemma calculates the symmetry gap of this problem, and its proof can be found in Appendix part of Theorem 3.1 follows from this lemma and Theorem 3.2
CC3 C.3
The second
Lemma 3.3. The problem (f)( S E F} has symmetry gap of 2-m'
1
4 Maximization with Cardinality Constraint
In this section consider the problem of maximizing non-negative submodular function f: 2 Rs0 subject to a cardinality constraint. In other words, we are given an integer value 1 S k S [. and the objective is to output set S S A of size at most lo (approximately) maximizing f among such sets. A standard greedy algorithm for this problem starts with the empty set, and then iteratively adds elements to this set, choosing in each iteration the element whose addition increases the value of the set by the most. When the objective function f is guaranteed to be monotone, it is long known that this greedy algorithm guarantees (1 //)-apppoxiiaaoonn for the above problem [44], and that this is essentially the best possible for any polynomial time algorithm [43 However, the greedy algorithm has constant approximation guarantee when the objective function is not guaranteed to be monotone (see 4 for an example demonstrating this). In Appendix we prove Theorem 4. which generalizes the result of (44), and proves an approximation guarantee for the greedy algorithm that deteriorates gracefully with the monotonicity ratio m.
Theorem 4.1. The Greedy algorithm (Algorithm 2 has an approximation ratio of at least m(1 1/e) for the problem of maximizing non-negative m-monotone submodular function subject cardinality construint.
Following a long line of works 35 22
46
52
20 the state-of-the-art approximation guarantee
for the case in which the objective function f is not guaranteed to be monotone is currently 0.385 (5). However, the algorithm obtaining this approximation ratio is quite involved, which limits its prac- ticality. Arguably, the state-of- sfte-of-the--aee art approximation ratio obtained by a "simple" algorithm is the 1/e 0.367-approximmtion obtained by an algorithm called Random Greedy, which adds to its solution, in each iteration, uniformly random element out of the & elements that can (individually) add the most to the value of this solution. Random Greedy has the nice property that for monotone objective functions it recovers the optimal 1 - 1/e approximation guarantee. In Appendix D.2 we prove Theorem 4.2, which gives an approximation guarantee for Random Greedy that smoothly changes as a function of m and recovers both the above mentioned 1/e and 1 - 1/e guarantees.
Theorem 4.2. Random Greedy (Algorithm 3) has an approximation ratio of at least m(1 - 1/e)- (1- m) - (1/e) for the problem of maximizing non-negative m-monotone submodular function subject to cardinality constraint.
There is still a gap between the of-te-of-the--e D.p8S-approoinaation for non- monooone objectives and the state-of-the-art inapproximability result due to Oveis Gharan and Vondrák (46), which only shows that no polynomial time algorithm can guarantee a better than roughly appl-ipproii In Appendix [D.3 we give Theorem D.4] which uses Theorem 3.2 to prove an inapproximabillty result that smoothly depends on m and recovers the above mentioned inapproximability results for m = 0 and m 1.
To get an intuitive understanding of Theorem D.4 we numerically evaluated for various values of m. The plot obtained in this way appears in Figure Ta For context, this figure also includes all the other results proved in this section. As is evident from Figure Ia| Theorem imppovess over the 1- 1/e inapproximability result of Nemhauser and Wolsey 43 only for m that is smaller than roughly 0.56. This is surprising since, intuitively, one would expect the best possible approximation ratio to be strictly worse than 1 1/e for any < 1. However, we were unable to prove an inapproximability that is even slightly lower than - e for any m >> 0.56. Understanding whether this an artifact of our proof or a real phenomenon is an interesting question that we leave open.
5

---

Greedy
Messured Continuou Gready
Randenn Greedy for Matroids
Greedy
trupprocimbiliiy (Theseen
Random Groedy
lasproximabilitt (1 1/e)
Inspprosimaxility
apprxxnaaiion ratlo
approsmmation
0.6
0.6
0.4
0.4
01
0.8
0.4
(a) Results for cardinality constraint (Section
(b) Results for matroid constraint (Section
Figure I: Graphical representation of the results of Sections and
5 Maximization with Matroid Constraint
In this section we consider the problem of maximizing a non-negative submodular function subject to matroid constraint. A matroid M over the ground set A is defined as a pair M = (N. I), where I a non non-empty subset of 2 obeying two properties for every two sets S, T N (i if S T and T E I. then S E I; and (ii) if S, T I and [S] < [T), then there exists an element u E T S such that + u E A set C is called independent with respect a matroid A if belongs to (otherwise, we say that S is dependent with respect to M); and the matroid constraint corresponding to given matroid M allows only independent sets with respect to this matroid as feasible solutions. Hence, we can restate the problem we consider in this section in the following more formal way. Given a non-negative submodular function f: 2 + R20 and a matroid M = (W, I), output an independent set S E I (approximately) maximizing f among all such sets. It is also useful to note that an independent set S E I is called a base of M it is an inclusion-wise maximal independent set, i.e., S is not subset of any other independent set.
standard greedy algorithm for the above problem starts with the empty set, and then iteratively adds to it elements, choosing in each iteration the element that increases the value of the solution by the most among the elements whose addition to the solution does not violate the matroid constraint. When the objective function is guaranteed to be monotone, this greedy algorithm guarantees 1 1/2-approximation (24). Our first result for this section (proved in Appendix EE.1 shows how this approximation guarantee changes as function of m (the greedy algorithm has constant guarantee for non-monotone functions this case as well).
Theorem 5.1. The Greedy algorithm (Algorithm 4 has an approximation ratio of at least m/2 for maximizing a non-negative m-monotone submodular function subject to a matroid constraint.
The approximation ratio of the greedy algorithm was improved over by the seminal work of Cälinescu et al. [9], who described the Continuous Greedy algorithm whose approximation ratio is 1 1/c when f is monotone; matching the inapproximability result of Nemhauser and Wolsey 43 In contrast, when f is not guaranteed to be monotone, the approximability of the problem is less well-understood.
On the one hand, after a long line of works 335 22 46 52 20 the state-of-the-an approximation ratio for the problem is 0.385 [5), but the other hand, it is only known that polynomial time algorithm for the problem can guarantee 0.478-approximation [4)..
Unfortunately, the above mentioned state-of-the-art 0 0.387-approximation algorithm is quite involved. Therefore, we chose to consider in this work two other algorithms. The first algorithm is Measure Continuous Greedy (due to (22) which guarantees approximation ratio of 1/c o(1) 0.367. This algorithm performs only slightly worse than the above state-of trrt and is a central component of all the currently known algorithms achieving better than 1/ 1/e-approximation. Measured Continuous Greedy is also known to guarantee (1 -1/e o(1) ((1)))apppp -approximation when the objective f is monotone, and the next theorem (proved in Appendix E.2) shows that its approximation guarantee changes smoothly with the monotonicity ratio of f.

---

Theorem 5.2. Measured Continuous Greedy (Algorithm()) 5 has an approximation ratio of at least
mm(-1/e)) + (1 m) (1/e) o(1 for maximizing a nton-negative m-monotone submodular
function subject to a matroid constraint, where the o(1) term diminishes with the ground set's 's size
The other algorithm we consider is an algorithm called Random Greedy for Matroids (due to [6]. Unlike Measured Continuous Greedy and almost all the other algorithms suggested for non-monotone objectives to date, this algorithm is combinatorial, which makes it appealing in practice. It starts with a base solution consisting of dummy elements representing empty slots, and iteratively performs swaps on this base solution in the following way. In each iteration, the algorithm picks base M maximizing the (individual) marginal value of the elements within it with respect to the current base solution. For every element in M. the algorithm identifies distinet element of the current base solution with which it can be swapped, and then for a uniformly random element of M such a swap is indeed done. Buchbinder et al. [6] proved an approximation ratio of roughly (1+ for Random Greedy for Matroids. The next theorem shows how this approximation guarantee improves as a function of the monotonicity ratio. In this theorem we refer to the rank i of the matroid constraint M. which is the size of the largest independent set with respect to this matroid. We also note that the algorithm we analyze is identical to the algorithm of 66 up to two modifications: our algorithm makes more iterations, and it updates the solution in an iteration only when this increases the solution's value.
Theorem 5.3. For every E E (0, 1), Random Greedy for Matroids (Algorithm 6 has an approximation (1₂(1) for the problem of maximizing non-negative m-- monotone submodular function subject to a matroid construint (except in the case of m = 1 in which the approximation ratio is 1/2
ratio of at least 1+m+te22(1-m)
on (1)) where (1( represents ferm that diminishes with k.
Theorem 5.3 is proved in Appendix
Let us also mention Theorem E.8
which appears in
Appendix E.4 and uses Theorem 3.2 to generalize the 0.478 inapproximability result of Oveis Gharan and Vondrák [46]. To get an intuitive understanding of Theorem E.8 we numerically evaluated it for various values of m, and depict the results in Figure lb For context, this figure also includes all the other results proved in this section. Somewhat surprisingly. Figure [b] shows that Theorem E. does not generalize the 1 1/e inapproximability result of Nemhauser and Wolsey (43) for monotone functions despite the fact that this inapproximability result holds for every monotonicity ratio m E [0, 1]. This resembles the inability of Theorem D.4 to improve over the same inapproximability result for large values of m.
Applications and Experiment Results
Many machine learning applications require optimization of non-monotone submodular functions subject some constraint. Unfortunately, such functions enjoy relatively low approximation guaran- tees. Nevertheless. in many cases the non-monotone objective functions have a significant monotone component that can be captured by the monotonicity ratio. In this section, we discuss two concrete applications with non-monotone submodular objective functions. For each application we provide a lower bound on the monotonicity ratio m of the objective function, which translates via our results from the previous sections into an improved approximation guarantee for the application.
To demonstrate the value of our improved guarantees in experiments, we took the following approach. The output of an approximation algorithm provides an upper bound on the value of the optimal solution for the problem (formally, this upper bound is the value of the output over the approximation ratio of the algorithm). Thus, we plot in each experiment the upper bound on the value of the optimal solution obtained with and without taking into account the monotonicity ratio, which gives a feeling of how the magnitude of our improvements compare to other values of interest (such as the gaps between the performances of the algorithms considered). In Appendix IF we give third application (Image summarization) that we study in the same way; and in Appendix G we lower bound the monotonicity ratio of fourth application (Ride-Shan Optimization).
*Technically, Measured Continuous Greedy an algorithm for maximizing the multilinear extesnion of a non non-negative negative submodular function subject to a general solvable down-closed convex body P' constraint, and we prove in Appendix E.2 that it guarantees the approximation ratio stated in Theorem for this setting. However, this implies the result stated in Theorem 5.2 using standard reduction (see Appendix f.2 further detail).
7

---

XBV
XB
Graady
Objective Value
Objective Value
Ranken
Objective Value
Recken
Powcet Usoe Bound
Piw Upper Bound
Our Upper Beand
Upprr Beard
62
À value
Number Movies
Number Movies
(a) Results when up to 10 movies can be selected for varying X.
(b) Results for 0.55 when
(c) Results for A = 0.85 when the number movies in the solution varies.
the number movies in the solution varies.
Function value
Previsa Usper Beand Upper norotsee FW
M
Function value
Function
Dimensionality
value
value
(d) Varying the dimensionality for Varying for fixed 0.2 and fixed a 0.3 and | 0.2.
( Varying 3 for fixed 0.5 and
Figure 2: Experimental results for Personalized Movie Recommendation a and Quadratic Pro- gramming ( Each plot includes the output of the algorithms we consider as well the previous and improved upper bounds the optimal value (the area between these two bounds is shaded).
6.1 Personalized Movie Recommendation
The first application we consider Personalized Movie Recommendation. Consider a movic recommendation system where each user specifies what genres she is interested in, and the system has to provide a representative subset of movies from these genres. Assume that each movic is represented vector consisting of users' ratings for the corresponding movie. One challenge here that each user does not necessarily rate all the movies, hence, the vectors representing the movies do not necessarily have similar sizes. To overcome this challenge, low-rank matrix completion techniques [10] can be performed on the matrix with missing values in order to obtain a complete rating matrix. Formally, given few ratings from & users movies obtain in this way rating matrix M of size k x n. Following [40] to score the quality of a selected subset of movies, we the function S(S) E.EN Eves 8u,v A EvES Eves 8u.e- Here, N is the set of movies, X E [0, 1] is parameter and Su,v denotes the similarity between movies and (the similarity 8a.v can calculated based on the matrix M in multiple ways: cosine similarity, inner product, etc). Note that the first term in f's definition captures coverage, while the second term captures diversity. Thus, the parameter À denotes the importance of diversity in the returned subset.
One can verify that the above defined function is non-negative and submodular. The next theorem, proved in Appendix [..]] analyzes monotonicity ratio of this function. In this theorem we assume that the similarity scores Su,v that the above mentioned ways to define these scores have these properties. Interestingly, it turns out that the function is monotone when À is small enough despite the fact that this function is traditionally treated as non-monotone (e.g., in 40 231). This nice unexpected result of the use of the monotonicity ratio, which required to really understand the degree of non-mone oonmmonttonicity represented by the objective function.
-egaaveae and obey $a.r Su.u for every u, E N. Note
Theorem 6.1. The objective function f monotone for 0 s X S 1/2 and 2(1 X)-monotone for 1/2 < X 1.
To demonstrate the value of our lower bound on the monotonicity ratio, we followed the experimental setup of [40] and used subset of movies from the MovieLens data set 28 which includes 10,437

---

movies. Each movie in this data set is represented by 25 dimensional feature vector calculated using user ratings, and we used inner products to obtain the similarity values $t,j based on these vectors.
In our experiment we employed accelerated versions of the algorithms analyzed in Section 4 for a cardinality constraint. Specifically, instead of the Greedy algorithm we used Threshold Greedy [ and Sample Greedy [39]; and instead of Random Greedy we used a threshold based version of this algorithm due to S that we refer as Threshold Random Greedy (Algorithm 6 in (8). All three
algorithms had almost identical performance in our experiments (see Appendix D]. thus, to avoid
confusion, in Figure we draw only the output of Threshold Random Greedy.
Each plot of Figure depicts the outputs of Threshold Random Greedy and a scarecrow algorithm called Random that simply outputs random subset of movies of the required size. Each point in the plots represents the average value of the outputs of 10 executions of these algorithms. We also depict in each plot the upper bound on the value of the optimal solution based on the general approximation ratio of Random Greedy and the improved approximation ratio implied by Theorems (. an.
the area between the two upper bounds is shaded. In Figure 2a we plot these values for the case in which we asked the algorithms to pick at most 10 movies, and we vary the parameter A. In Figures 2bb amd [2 we plotted the same values for fixed parameter A. while varying the maximum cardinality (number of movies) allowed for the output set. Since the height of the shaded area is on the same order of magnitude as the values of the solutions produced by Threashold Random Greedy (especially when À is close to 1/2), our results demonstrate that the improved upper bound we are able to prove much tighter than the state-of-the-
Furthermore, our improved upper bound shows that the gap between the empirical outputs of Threshold Random Greedy and Random is much more significant as a percentage of the value of the optimal solution than one could believe based on the weaker bound.
6.2 Quadratic Programming
Consider the function
F(x) xxx x Hx + h'x+c
(I)
By choosing appropriate matrix H. vector h and scalar c, this function can be made to have var- ious properties. Specifically, we would like to make it non-negative and DR-submodular (DR- submodularity is an extension of submodularity more detail). Our goal in this section is to maximize F under a polytope constraint given by R2 Ax < b, u, Rmxx b 20) for some dimensions n. and m.
continuous functions-sec Appendix for
{x p=
n. choose the matrix H E Rax= to be a randomly generated symmetric matrix whose entries are drawn uniformly at random (and independently) from [-1, Oj. and choose A E Rx* to be a randomly generated matrix whose entries are drawn uniformly at random from [t, + 1] for = 0.01 (this choice of guarantees that the entries of A are strictly positive). We also set b- I (i.e., is the all ones vector), and u to be the upper bound on / given by u₃ = mim] b At.j for every j E [n). Finally, we set h = -B H u for a parameter / > 0.
Following Bian al. 22, we
The non-positivity of H guarantees that is DR-submodular. To make sure that f is also non-negative, the value of e should be at least mināsxgu u x Hx + h² x (where 0 is the all zeros vector). This value can be approximately obtained by using Q [53]. Let the value of this minimum be M: then we set
-M + MM for some parameter
O.
The definition of the monotonicity ratio can be extend to the continuous setting we consider in this section using the formula
F(y). infösxsygu F(x). where the ratio F(y)/ Fxx) is understood as 1 whenever F' x 0. The following theorem analyzes the monotonicity ratio of the function given in Equation based on this definition. The proof of this theorem can be found in Appendix H.2
Theorem 6.2. For 10,1/2), the objective function F given by Equation [ Furthermore, when minggrsul (+Xx x Hx + hx) 2 0, F is even (1 223) 233)mmonooone.
(1-28) -monotone.
1ta
We applied the Non-monotone Frank-Wolfe algorithm of Bian al. 22 to the above defined op- timization problem (we refer the reader to Appendix [ for further detail about this algorithm and
'We have used IBM CPLEX optimization studio https://ww// https://www.bb..cmm// http://wwwbbb.oooooorrrttt//////
optimization-studioo

---

its analysis). Figures 2d 2e and 2i depict the results we obtained. Specifically, Figure 2d shows the value of the solution obtained by Hon-monotone Frank-Wolfe for 0.3 and B 0.2 as
the dimensionality varies. The shaded area is the area between the previous upper bound on the optimal value, and our upper bound that takes advantage on the monotonicity ratio bound given by Theorem 6.2 Figures _ and 2 are similar, but they fix the dimensionality to be 4, and vary or / instead. Let us discuss now some properties of Figures 2d 2e and 2f (i) Each data point in these figures corresponds to single instance drawn from the distribution described above. This implies that the plots in these figures vary for different runs of our experiment, but the plots that we give represent (single) typical run. (ii) The size of the the shaded area depends
and 3, but also on the sign of minjsx (2x Hx hx). This is the reason that this size behaves somewhat non-continuously in Figure 21 Interestingly, the sign of this minimum is mostly function of B. In other words, there are values of 3 for which the minimum is non-negative with high probability, and other values for which the minimum is negative with high probability. (iii) One of the monotonicity ratio significantly improves the upper bound on the optimal value, especially when minögxgul? Hx + hx) happens to be non-negative.
(xx"HXx
that the
Conclusion
In this paper we have defined the monotonicity ratio, analyzed how the approximation ratios of standard submodular maximization algorithms depend on this ratio, and then demonstrated that this leads to improved approximation guarantees for the applications image summarization and quadratic programming. We believe that the monotonicity ratio is a natural parameter of submodular maximization problems, refining the binary distinction between monotone and non-monotone objective functions and improving the power of submodular maximization tools in machine learning applications. Thus, we hope to see future work towards understanding the optimal dependence on of the approximation ratios of various submodular maximization problems.
movie recommendation,
important take-home message from our work that, least in the unconstrained submodular maximization case, the optimal algorithm has an approximation ratio whose dependence on m is non-linear. Such algorithms are rarely obtained using current techniques, which might one of the reasons why these techniques have so far failed to obtain tight approximation guarantees for constrained non-monotone submodular maximization.
Funding Transparency Statement
Funding in direct support of this work: Foundation (ISF) grant no. 459/20.
This research was supported in part by Israel Science
Additional revenues related to this work: None
References
[1] Ashwinkumar Badanidiyuru and Jan Vondrák. Fast algorithms for maximizing submodular functions, In SODA, pages 1497-1514, 2014. doi: 10.1137719981161117440... URL https://doi.org /tt////.000000011111117777717110 117.1117771.97111117770000 110
[2] An Bian, Kfir Yehuda Levy, Andreas Krause, and Joachim M. Buhmann. Non- monotone continuous DR-submodular maximization: Structure and algorithms. NeurIPS, pages 486-496, 2017. URL https://proceedding www.neuuii... pttppppp..ppppppp/////////////
[3] Andrew An Bian, Joachim M. Buhmann, Andreas Krause, and Sebastian Tschiatschek. Guaran- tees for greedy maximization of non-submodular functions with applications. In ICML, pages 498-507, 507,507,222 2017. URL httt::://prroeediinggtt/ mlr wwwss//e/s///oooe http://////aaaaaaaaaa.a..
[4] Niv Buchbinder and Moran Feldman. Submodular functions maximization problems. In Teofilo F. Gonzalez, editor, Handbook of Approximation Algorithms and Metaheuristics, Second Edition, Volume 1: Methologies and Traditional Applications, pages 753-788. Chapman and
10

---

Hall/CRC, 2018. doi: 10.1201/9781331224424422 9781361236423-42
URL attps://doi.org:
[5] Niv Buchbinder and Moran Feldman. Constrained submodular maximization via nonsymmet- ric technique. Math. Oper. Res., 44(3)9988-0055 2019.
doi: 10.1287/moo:22018 0.055. URL
ftttpp://doi.rgg//// 1287 20000//mor.00 20077/0000.2188.9555 2018.0955
[6] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. Submodular maximization with cardinality constraints. In Chandra Chekuri, editor, SODAA pages 1433-1452. SIAM, 2014. doi: 10.1137/1.97811111773499 106
URL htttp::///oi..... org 1tt.://///1111111111171111111111
[7] Niv Buchbinder, Moran Feldman, Joseph Naor, and Roy Schwartz. tight linear time (1/2)- approximation for unconstrained submodular maximization. SIAM J. Comput. 43(5):1384
1402, 2015. doi: 10.1137/130922205 URL httpss:/dooi..ortteeeooo org/ 100//////1..//
[8] Niv Buchbinder, Moran Feldman, and Roy Schwartz. Comparing apples and oranges: Query trade-off in submodular maximization. Math. Oper. Res., 42(2))308-322 2017. doi: 10.1287/
moor:2016.086 08099. htt/httss:///oi..orr
1287 1 moor 2016 0809
[9] Gruia Cälinescu, Chandra Chekuri, Martin Pál. and Jan Vondrák. Maximizing monotone submodular function subject to a matroid constraint. SIAM J. Comput., 4016):1740-1766, 2011. doi: 10.1 177/80733399 Jattss:/:////i org 10. 1177/0073318/
[10] Emmanuel J Candès and Benjamin Recht. Exact matrix completion via convex optimization. Foundations of Computational mathematics, 7677717-77 2009.
[11] Chandra Chekuri, Jan Vondrák, and Rico Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures. In FOCS. pages 575-584, 2010. doi: 10.1109/ FOCS.2010.64 URL httpt:ttt//.ii.... org/10 11w.:1...11F....11 2010.
[12] Lin Chen, Moran Feldman, and Amin Karbasi. Weakly submodular maximization beyond cardinality constraints: Does randomization help greedy? In ICML, pages 802-812, 2018. URL
http:://proceeding:. mlr. hrtp:/edddnaa.l...ppereree/////a chen
http://veo//eee18.b.btcc html
[13] Michele Conforti and Gérard Cornuéjols. Submodular set functions, matroids and the greedy Tight worst-case bounds and some generalizations of the rado-edmonds theorem. URL https
algorithm:
Discret. Appl. Math., 7(3)2511-274, 1984. doi:
7/doi. oropi..ogg110. 1016/ 0166 218X (B4
[14] Min Cui, Donglei Du, Dachuan Xu, and Ruiqi Yang. Approximation algorithm for maximizing nonnegative weakly monotonic set functions. In CSoNel, pages 50-58, 2021. doi: 10. 1007/977 3-030-91434-9))3
htttihtts:///dol orgpii..rg/000 10. 1000000077778 --07788-3-00---- 91434-9_5
[15] Abhimanyu Das and David Kempe. Submodular meets spectral: greedy algorithms for subset selection, sparse approximation and dictionary selection. In /CML, pages 1057-1064, 201
[16) Abhimanyu Das and David Kempe. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. J. Mach. Learn. Res., 19:3:1-3:34 2018. URL http:://jmmr wwwp://ppp//s////////// /111ee/////911113//// html hhtmmlmmmm
[17] Anirban Dasgupta, Ravi Kumar, and Sujith Ravi. Summarization through submodularity and dispersion. In ACL, pages 1014-1022. The Association for Computer Linguistics, 2013. URL https://aclanthool.g
[18] Ethan R. Elenberg, Alexandros G. Dimakis, Moran Feldman, and Amin Karbasi. Streaming weak submodularity: interpreting neural networks the fly. In NeurIPS, pages 4047-4057, 2017.
[19] Ehsan Elhamifar and M Clara De Paolis Kaluza, Online summarization via submodular and convex optimization. In CVPR, pages 1783-1791, 2017.
[20] Alina Ene and Huy L. Nguyen. Constrained submodular maximization: Beyond 1/e. In Irit Dinur, editor, FOCS, pages 248-257 IEEE Computer Society, 2016. doi: 10. F01 34. URL https: //oii org/ 10 1 2016..
11

---

[21] Uriel Feige, Vahab S. Mirrokni, and Jan Vondrák. Maximizing non non- monotone submodular functions. SIAM Comput, 40(4):1133-115533 2011. doi: 10.1137/090779346. URL https //doi.org/10 1137 01337/900779444
[22] Moran Feldman, Joseph (Seffi) Naor, and Roy Schwartz. A unified continuous greedy algorithm for submodular maximization. In Rafail Ostrovsky, editor, FOCS, pages 570-579, IEEE Computer Society, 2011. doi: 10.1009/FOCS 201 1.111.4.. URL httpp:////ooo org/ 10. 1109/
FOCS 2011.46
[23] Moran Feldman, Christopher Harshaw, and Amin Karbasi. Greed good: Near-optimal submodular maximization via greedy optimization. In COLT, pages 758-784, 2017. URL
http:://proceedingg. mlr. wtt.ggg...........s..mmme pwwpp/ee//feeee/eeeeee http://////elddma/77/m htmm
[24] M. Fisher, G. Nemhauser, and L. Wolsey, An analysis of approximations for maximizing submodular set functions-II. Mathematical Programming, 8:73-87, 1978.
[25] Mehrdad Ghadiri, Richard Santiago, and F. Bruce Shepherd. A parameterized family of meta- submodular functions. CoRR, abs/2006. 13754, 2020. URL
13754
[26] Mehrdad Ghadiri, Richard Santiago, and F. Bruce Shepherd. Beyond submodular maximization via one-sided smoothness. Dániel Marx, editor, SODA, pages 1006-1025, SIAM, 2021. doi: (0.1137//97811111976666
URL https:://oi..ooooo 1ttp://////.11111111911111111161 97111999997111119666 63
10. 1137/1111111
[27] Anupam Gupta, Aaron Roth, Grant Schoenebeck, and Kunal Talwar. Constrained non-monotone submodular maximization: Offline and secretary algorithms. In WINE, pages 246-257, 2010. doi:
20. URL https://doi org/ 10. 1007/978-
642-17572-5_20
[28] Maxwell Harper and Joseph A. Konstan. The movielens datasets: History and context, Acm transactions interactive intelligent systems (TiiS), 5(4):1-19, 2015.
[29] Rishabh K. Iyer, Stefanie Jegelka, and Jeff A. Bilmes. Curvature and optimal algorithms for learning and minimizing submodular functions. In Christopher J. C. Burges, Léon Botton, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems (NeurIPS), pages 2742-2750, 2013.
[30] Rishabh Krishnan lyer. Submodular optimization and machine learning: Theoretical results, unifying and scalable algorithms, and applications. PhD thesis, University of Washington, 2015.
[31] Ehsan Kazemi, Shervin Minaee, Moran Feldman, and Amin Karbasi. Regularized submodular maximization at scale. In ICML, pages 5356-5366. PMLR, 2021.
[32] Katrin Kirchhoff and Jeff Bilmes. Submodularity for data selection in machine translation. In EMNLP, pages 131-141, 2014.
[33] Alex Krizhevsky. Learning multiple layers of features from tiny images, Technical report, University of Toronto, 2009.
[34] Alan Kuhnle, J. David Smith, Victoria Crawford, and My T. Thai. Fast maximization of non-submodulaar, monotonic functions on the integer lattice. In Jennifer G. Dy and Andreas Krause, editors. ICML, pages 2791 PMLR, 2018. URL http://pproceedings mlr press//80/kuuhleele html
[35] Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, and Maxim Sviridenko. Non-monotone submodular maximization under matroid and knapsack constraints. In Michael Mitzenmacher, editor, STOC, pages 332. ACM, 2009, doi: (0.1145515364144155664 URL https 7/doi.org/10. 1145/ 53444.4444414 1536459
[36] Qi Lei, Lingfei Wu, Pin- Yu Chen, Alex Dimakis, Inderjit S. Dhillon, and Michael J. Witbrock. Discrete adversarial attacks and submodular optimization with applications to text classification. In Ameet Talwalkar, Virginia Smith, and Matei Zaharia, editors, My. mlsys.org. 2019. URL https: attps://proceedingg. www.yy/.rggooo/////ooo 28.ooo//284.po
12

---

[37] Hui Lin and Jeff Bilmes.
summarization via budgeted maximization of submodular functions. In Human Language Technologies (HLT), pages 912-920, 2010.
[38] László Lovász. Submodular functions and convexity. In A. Bachem, M. Grötschel, and B. Korte, editors, Mathematical Programming: the State of the Art, pages 235-257. Springer, 1983.
[39] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, Amin Karbasi, Jan Vondrák, and Andreas Krause. Lazier than lazy greedy. In AAAI, pages 1812-1818, 2015. URLhttp: //wttp://www. aaai org/ocs/indess wwt.iindwpppp.ppp.eeeeeeeee AAAT /ttp///AAAAAAAS/ppp/rrrrra//////
[40] Baharan Mirzasoleiman, Ashwinkumar Badanidiyuru, and Amin Karbasi. Fast constrained submodular maximization: Personalized data summarization. In ICML, pages 1358-1367.
PMLR, 2016.
[41] Marko Mitrovic, Ehsan Kazemi, Morteza Zadimoghaddam, and Amin Karbasi. Data sum- marization at scale: A two-stage submodular approach. In ICML, pages 3596-3605. PMLR, 2018.
[42] Marko Mitrovic, Ehsan Kazemi, Moran Feldman, Andreas Krause, and Amin Karbasi. Adaptive sequence submodularity. NeurlPS, 32:5352-5366 2019.
[43] G. L. Nemhauser and L. A. Wolsey. Best algorithms for approximating the maximum of submodular set function. Mathematics of Operations Research, 3(3):177-188, 1978.
[44] G. Nemhauser, A. Wolsey, and M. L. Fisher. An analysis of approximations for maximizing submodular set functions I. Mathematical Programming, 14:265-299 1978.
[45] Ashkan Norouzi-Fard. Jakub Tarnawski, Slobodan Mitrovic, Amir Zandich, Aidasadat Mousav- ifar, and Ola Svensson. Beyond /2-approximatiin for submodular maximization massive data streams. ICML, pages 3829-3838. PMLR, 2018
[46] Shayan Oveis Gharan and Jan Vondrák. Submodular maximization by simulated annealing, In Dana Randall, editor, SODA, pages 1098-1116. SIAM, 2011. doi: 11111///..7811199999 83. URL httpt:ttt///o...o///////////// 110.....1111111 htt.://w.................111111.
[47] Benjamin Qi. On maximizing sums of non-monotone submodular and linear functions. CoRR, hbs/2205.118774 2022. doi: (0.48550/a2Xi.22255.555 URL/ttps:///oii org/ 48550/
arXiv 2205. 15874
To appear in ISAAC 2022.
[48] Alexander Schrijver. Combinatorial Optimization: Polyhedra and Efficiency. Springer, 2003.
[49] Maxim Sviridenko, Jan Vondrák, and Justin Ward. Optimal approximation for submodular and supermodular optimization with bounded curvature. Math. Oper: Res., 42(4): (08(4):1197449 197-1218, 2017.
doi: 10.1287/moo:22016.8842 URL httt:p:://doiooooo org/ 10. 1287 / /ooor 2046.0842
[50] Sebastian Tschiatschek, Rishabh K Iyer. Haochen Wei, and Jeff Bilmes. Learning mixtures of submodular functions for image collection summarization. In NewrlPS, pages 1413-1421,
2014.
[51] Sebastian Tschiatschek, Adish Singla, and Andreas Krause. Selecting sequences items via submodular maximization. In Satinder P. Singh and Shaul Markovitch, editors, AAAI, pages 2673, AAAI Press, 2017. URL http: //aaai//aaa.../ org/ocs/index. paper/viest haper/view/14890
http::///aa..rrr/o////neex wwtp:ppIp//aaaaaa AAAA1// /ttpa/////////eeeeeeap///A/////
[52] Jan Vondrák. Symmetry and approximability of submodular maximization problems. SIAM Comput., 22(1):265-304 2013. doi: 10.1 10832318. URL https:://oi...oooo http://oo...g/....1111111 110832318
[53] Wei Xia, Cun-Carlos Vera, and Luis F. Zuluaga. Globally solving nonconvex quadratic programs via linear integer programming techniques. INFORMS J. Comput., 32(1))40-56, 2020. doi:
10. 227/2887..cc00 201.ee...21...... 8.8883. URL https://dos //t::://oooooo 11t/ 2018. 0883
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [No]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] Most of them in the supplementary material.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [No]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi-
ments multiple times)? [Yes] in the supplementary material.
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [No]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any assets either in the supplemental material URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you's 're using/curating? [No]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?
[No]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
14


Reviews:
[{"review_id": "mzb_emgM_6V", "reviewer": "Reviewer_rgKu", "summary": "This paper introduces the notion of monotonicity ratio $m\\in [0,1]$ for submodular functions. Submodular maximization has been widely studied in the literature under the assumption that the function is either monotone or non-monotone. The authors study various standard submodular maximization algorithms for either of these two settings and show that new guarantees could be obtained that depend on the monotonicity ratio of the function. Finally, this paper considers a number of applications, including movie recommendations, and obtains bounds for the monotonicity ratio of the objective function.", "questions": "I've already mentioned a few questions earlier. Below are a few more questions and comments:\n- In the personalized movie recommendation example, all the similarity scores need to be non-negative for the objective function to be submodular and non-negative, however, in the paper, it is mentioned that these scores are all non-positive.\n- Have you thought about alternative notions of monotonicity ratio that are also easy to compute? In that case, one can design algorithms that assume access to this parameter and can guarantee better results.", "limitations": "The limitations are addressed. The paper is mostly theoretical and does not need a discussion about potential negative societal impact.", "rating": 4, "confidence": 5, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- First work that tries to extend the binary property of monotonicity of submodular functions to continuous properties.\n- The bounds for monotonicity ratio in the motivating applications (particularly movie recommendation and personalized image summarization) are interesting.\n- The inapproximability result for unconstrained submodular maximization (Theorem 3.1) is novel and significant.\n\nWeaknesses:\n- The paper is extremely hard to read and follow even for someone who is familiar with the literature on submodular maximization. All the results in Sections 3-5 correspond to standard submodular maximization algorithms, however, none of these algorithms have been properly introduced in the paper. A brief discussion about each of these algorithms is missing.\n- Unlike the curvature, the monotonicity ratio of a submodular function is hard to compute, and therefore, obtaining bounds in terms of such a parameter may not be very useful. While the monotonicity ratio bounds provided for the motivating applications are interesting, such bounds could not be derived in general.\n- The inapproximability bound for matroid constraints for large values of $m$ (including $m=1$) seems to be larger than the known $1-\\frac{1}{e}$ bound for the monotone setting and this result is really surprising. The authors need to explain this result in more detail.\n- Besides the inapproximability result for unconstrained submodular maximization (Theorem 3.1), the other results of this paper seem to be a straightforward extension of prior works. The authors need to highlight the challenges faced when proving these more general results and specify how they managed to overcome the challenges.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "mjrILor_chd", "reviewer": "Reviewer_38EM", "summary": "This paper studies a new, continuous notion of (non-)monotonicity for submodular functions. The notion in question is called monotonicity ratio and is defined as the minimum $m$ such that $m \\cdot f(S) \\le f(T)$ for all $S \\subseteq T$. Clearly for $m=1$ we obtain the standard definition of monotonicity, while as m decreases, the more non-monotonicity the function exhibits. \n\nThe main contribution of the paper (apart from the definition in itself) is the analysis of well known algorithms for submodular maximization in terms of this new parameter. More precisely, the authors offer the following results: \n- Double greedy for unconstrained submodular maximization is proved to have an approximation factor of $\\max(m,(2+m)/4)$. The authors complement this result with a non tight lower bound that depends on m. \n- For cardinality constraints, it is shown that the approximation of greedy is $m(1-1/e)$, while for random greedy is $m (1-1/e) + (1-m)/e$\n- For matroid constraints, it is shown tha the approximation of greedy is m/2, for measured continuous greedy is approx $m (1-1/e) + (1-m)/e$. A result for random greedy is also provided. \n\nFinally, the authors run experiments for personalized movie recommendation and quadratic programming. ", "questions": "No questions", "limitations": "Other comment to the authors: \n- line 10, continuous is misspelled \n", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a good paper that closes an important gap in the understanding of submodular functions. Studying the degree of submodularity or linearity of a function has already been proved to be a fruitful field of study; studying the degree of non-monotonicity will probably be as important. \n\nAmong the many positive results, I particularly like the fact that this paper offers the first (to the best of my knowledge) formal justification of the good empirical performances of greedy on non-monotone instances. \n\nThe paper is well written and offers a clear introduction to the problem for non-expert readers. I have only two suggestions for the authors. First, it would be interesting to give at least an idea of techniques used in the vast appendix; in particular it is a bit strange to give the definition of continuous relaxation in the intro and never use it in the body of the paper. Second, it is important to give some more arguments to the actual applicability of the monotonicity ratio. Even though some examples of upper bounds have been given in the experiments, the paper would benefit from other examples and/or general routines to compute (even a rough upper bound to ) the monotonicity ratio. \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "YihL78fc0Hv", "reviewer": "Reviewer_8Qqa", "summary": "In this paper, the authors consider the problem of maximizing submodular functions that are non-monotone. Non-monotone submodular optimization is typically more challenging than monotone submodular maximization. Although several algorithms are known for non-monotone submodular maximization, they are typically slow and they yield poor approximation guarantees. The author(s) address this problem, by proposing the definition of \"m-monotonicity\". This definition generalizes monotonicity, by quantifying the degree to which a function is far from being monotone. \n\nThe author(s) propose to incorporate the notion of m-monotonicity in the analysis of common submodular maximization algorithms, to improve state-of-the-art guarantees. The author(s) demonstrate the applicability of their framework to two relevant applications, namely Movie Recommendation and Quadratic Programming. On this instances, the approximation guarantee achieved in this paper is better than the state-of-the art. ", "questions": "- Can you please describe technical challenges/contributions of this paper?\n- Do you think that your upper-bounds can be further improved? Do these problems admit a lower-bound parameterized by m?", "limitations": "The authors adequately addressed limitations, given that the contribution of this paper is mostly theoretical.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Maximizing non-monotone submodular functions is difficult in practice, particularly on large and heterogeneous datasets. Hence, this submission addresses a relevant research question. I think that the paper is overall well-written and easy to follow. The experiments show an improvement over the state-of-the art. \n\nHowever, this submission also has weaknesses. (i) The authors only use their definition to study pre-existing algorithms. This leads me to believe that the technical contribution is limited, despite the many theoretical results provided in the appendix. It seems to me that m-monotonicity offers a simple way to generalize many known results, without making significant changes to the original proofs. (ii) It is unclear to me if their bound admits a matching lower bound.\n\nI believe that this paper is overall a good submission. If the authors address my concerns, I am willing to raise my score. \n\n-------------------- After the rebuttal:\n\nI believe that the author(s) have addressed all my concerns and questions. It is clear that the contribution of this paper is novel and non-trivial. I believe that this submission is clearly written, and accessible to a broad audience. For these reasons, I am raising my score.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HYnL7SJ6KrG", "reviewer": "Reviewer_ZNvk", "summary": "This paper defines a new notion of the monotonicity ratio for submodular maximization. The authors analyze how the approximation ratios of standard submodular maximization algorithms (e.g., greedy) depend on this ratio under the unconstrained settings/cardinality constraints/matroid constraints, and then demonstrated that this leads to improved approximation guarantees for the applications of movie recommendation, image summarization, and quadratic programming. The authors also propose lower bounds depending on the monotonicity ratio. ", "questions": "- This paper mainly considers greedy-based algorithms. Why not also considers local search-based algorithms?", "limitations": "Yes", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The notion of the monotonicity ratio is novel and interesting for submodular maximization.\n- The analysis of greedy-based algorithms is solid and convinces the reasonability of the monotonicity ratio.\n- The lower bound analysis is interesting. Specifically, I like the conclusion that in the unconstrained submodular maximization case, the optimal algorithm has an approximation ratio whose dependence on the monotonicity ratio $m$ is non-linear.\n- The writing is nice, including a detailed discussion of the novelties and applications.\n\nWeaknesses:\n- It will be better if this paper can propose an algorithm that beats greedy w.r.t. the monotonicity ratio.\n\n---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------\nThanks for the response. Could you update the improved analysis of the double greedy algorithm for the unconstrained case in the revised pdf? This will make the paper stronger.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept