Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 
strengths_and_weaknesses: Strengths:
- The notion of the monotonicity ratio is novel and interesting for submodular maximization.
- The analysis of greedy-based algorithms is solid and convinces the reasonability of the monotonicity ratio.
- 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.
- The writing is nice, including a detailed discussion of the novelties and applications.

Weaknesses:
- It will be better if this paper can propose an algorithm that beats greedy w.r.t. the monotonicity ratio.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Thanks 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.
questions: - This paper mainly considers greedy-based algorithms. Why not also considers local search-based algorithms?
limitations: Yes
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: 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.
strengths_and_weaknesses: Strengths:
- First work that tries to extend the binary property of monotonicity of submodular functions to continuous properties.
- The bounds for monotonicity ratio in the motivating applications (particularly movie recommendation and personalized image summarization) are interesting.
- The inapproximability result for unconstrained submodular maximization (Theorem 3.1) is novel and significant.

Weaknesses:
- 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.
- 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.
- 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.
- 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.
questions: I've already mentioned a few questions earlier. Below are a few more questions and comments:
- 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.
- 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.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

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

Finally, the authors run experiments for personalized movie recommendation and quadratic programming. 
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. 

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

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

questions: No questions
limitations: Other comment to the authors: 
- line 10, continuous is misspelled
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: 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. 

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

However, 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.

I believe that this paper is overall a good submission. If the authors address my concerns, I am willing to raise my score. 

-------------------- After the rebuttal:

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

questions: - Can you please describe technical challenges/contributions of this paper?
- 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.
review_title: null

Meta-review: metareview: This paper introduces a new notion of partial monotonicity in submodular maximization that is interesting and relevant. The authors derive approximation ratios for existing algorithms that are as a function of a monotonicity ratio. This new notion is likely to be studied and relevant in future work. 

One concern raised by a reviewer is regarding the fact that the monotonicity ratio of a function is hard to compute. However, this is also the case for other properties of submodular functions and this concern is adequately discussed in the paper.
confidence: Certain
Decision: Accept