Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This paper addresses learning rule set models for binary classification, ie combinations of logical rules on features to classify a positive class. Since learning rule sets requires selection of features over which the logical rules are applied and selection of the rules themselves, the subset selection problem is exponential. This paper formulates the task loss as a supermodular function comprised of a constant term (ignored in the optimization), a modular function term and a submodular function term. The paper outlines an optimization algorithm that contains a subproblem that is not computationally feasible except for small problems. Thus, it outlines an approximate solution to the subproblem.
main_review: The main contribution of the work is in the specific formulation of the rule set learning problem as a regularized submodular loss function and then applying the optimization algorithm of [2] to solve it. However the subproblem introduced in that algorithm cannot be solved exactly for larger problems, so the paper proposes an approximate solution to the difference of submodular functions. Thus, the optimization does not have any approximation guarantees. The method may be useful in it's formulation, though the optimization of the loss is less compelling without real 'nice' properties beyond the results that can be seen empirically, ie it seems to work in practice. Without more data on running time, both on the proposed optimization and the baselines, the empirical analysis is still lacking. 

Clarity: The work is generally well presented and the paper is mostly clear. One exception is the discussion of related work. Section 4 does not go into enough detail of the cited work to place this work into the context of the field. The introduction section even provides more information on some of these works. Can these be combined or reorganized to better contextualize the contribution of the current work as well as the existing work of the relevant literature that is already cited?
Experiments: It’s not clear why an alternative (light) implementation of the Column Generation (CG) [1] method was used. While the beam search alternative may be more comparable in that it is an approximate algorithm, the full method can be evaluated against the proposed method both on accuracy and speed, for example. Is a full implementation not available? In any case, the running time of the proposed and baseline methods should be reported as well, especially since some methods were excluded based on a running-time cut-off. 
[1] Harshaw, C., Feldman, M., Ward, J. and Karbasi, A. "Boolean decision rules via column generation." Proceedings of the 32nd International Conference on Neural Information Processing Systems. 2018.
[2] Harshaw, Chris, et al. "Submodular maximization beyond non-negativity: Guarantees, fast algorithms, and applications." International Conference on Machine Learning. PMLR, 2019.



Post rebuttal comments:
The new results and clarifications from the authors have strengthened the experimental components of the submission, which I believe are the main contribution of the work. Thus, I am updating my score to recommend acceptance.
limitations_and_societal_impact: Limitations of the method are not extensively addressed, especially since the approximate solution loses the approximation guarantees admitted by exactly solving the marginal gain maximization subproblem, which can only be computed for small problems. For a small problem like COMPAS-binary with 24 features or other small datasets, the solution could be compared to the exact subproblem solving both in accuracy and running time to investigate some of the gaps in the approximation.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes an approach for learning decision rule sets that combines both rule generatino and rule selection. this is accomplished by formulating the an outer subproblem as regularized submodular maximization and an inner problem as maximizing the difference of two submodular functions. Experimental results show that the method has improved test performance with less overlap among decision rules.

main_review: Originality: Interesting but straightforward combination of previous work on submodular maximization (distorted greedy, majorize-maximization) to a new domain.

Quality:
- The authors should discuss how the rule set compares to the true optimal rule set, since two solutions with similar values could be differ in their interpretability.
- While test accuracy is impressive (Table 1), the results in Table 2 are much more impressive for Overlap percentage, which makes sense because the proposed algorithm is admittedly the only one to minimize that explicitly (line 276). Since #Rules and #Literals are often much worse than baselines, it would be good to argue strongly that overlap is a much more important interpretability measure than either of those.

Clarity: Paper is clear, well-organized, and generally a pleasure to read

Methodology: 
- Why set $\beta_o = \beta_1 = 1$? Why fix the number of trees in the RF to be 100? 
- What was the problem with running [27]? Since references [14, 27] are discussed in related work and appear to be very relevant, the paper would be improved if it added these works as baselines.
- Figure 1 (scalability) should include other algorithms as well

Quality/Significance: If the inner subproblem is solved with an approximate local search heuristic, then the theoretical guarantee of Proposition 2, which assumes the inner subproblem is solved to exact optimality, is not relevant. The paper does not address this fully, and would benefit from identifying how much is lost to this approximate inner subproblem either theoretically (assume an approximate inner maximization oracle) or empirically (ablation on different inner subproblem methods).

Questions:
- Do other approaches require binarizing the features? If not, how do they scale with d?

---
EDIT: The authors addressed my main concerns with additional experiments showing the optimality gap with respect to a branch and bound method. I am increasing my score to 6, although the paper would be further strengthened by studying the sensitivity to inner subproblem solver in even greater detail.

limitations_and_societal_impact: No explicit discussion of limitations or negative social impact. The authors could discuss that in general interpretable classification methods need not be more fair or accurate than large neural networks.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This submission addresses learning interpretable rule sets for binary classification problems. The approach is based on using submodular optimization, and the authors come up with a learning algorithm that uses approximation properties from DS optimization. The exact solution of the subproblems are NP-hard, and hence, the authors propose solving the subproblems via heuristic approaches. This is supported by local search operators. Some theoretical results are presented. The computational experiments show the effectiveness of their approach in terms of accuracy. The contribution of this work is an algorithm that works very well on binary classification and manages to find interpretable decision rules.
main_review: Major Comments:
- How do you define small dataset and large dataset? Check lines 258, 262.
- Interpretability analysis: The number of rules and number of literals are significantly different than the
work by Dash et al. (2018) for CG and CART. Why? For RIPPER this is not the case and good. It would be
better to include the outcome of BRS in Table 2. Now the analysis looks incomplete.
- Limitations of this study are not discussed.

Minor Comments:
- 22-23: “Black box models are particularly problematic here because they are hard to audit and to diagnose.” => Sentence needs rewording, very informal.
- 77: one-versus-one or one-versus-all?
- 154: Missing a space after “cases,”.
- 218: “Decision lists are special cases of decision trees that grows only in one branching direction, and
the root-to-leaf paths of a decision tree form a rule set without overlap.” => Sentence needs rewording,
not clear.
- 220: “However, the learning of decision lists and trees are inherently much”
- 221: “harder because of their combinatorial structure is more complex than rule sets.”
- 251: “For BRS, the maximum”
- Very briefly, there are spelling mistakes in the document and the usage of language can be improved significantly...
limitations_and_societal_impact: The reasoning behind solving the subproblem via heuristic approaches is understandable. Nevertheless, the running times of the algorithms are not discussed/reported. 

The experiments are given only for binary classification. The other missing point is details about generalization to multi-class classification.
review_title: null

Meta-review: The authors provide an interesting connection between an interpretable decision rule set and submodular optimization. Technically, they either consider regularized submodular maximization framework or the difference of two submodular functions. 

I found the formalization very interesting. Also, the authors had a successful rebuttal and convincing new set of experiments.  Regarding scaling up the experiments, the authors may look at a recent ICML paper on "Regularized Submodular Maximization at Scale" by Kazemi et al. Also, there is a related paper on interpretability using submodularity that the authors may consider looking into "Streaming Weak Submodularity: Interpreting Neural Networks on the Fly" by Elenberg et al. 

All in all, this is an interesting paper and I suggest acceptance. 
Decision: Accept (Spotlight)