Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This work tries to produce robust decision stump ensembles against feature perturbation. To achieve this, the authors propose DeRandomized Smoothing (DRS), which can help provide a robust certificate. Moreover, the authors propose a robust MLE optimality criterion for individual stumps and two boosting schemes for whole ensembles. The experimental results look promising and demonstrate the effectiveness of the proposed method.
strengths_and_weaknesses: Strength:

1. The writing and figure presentation are very good.
2. The PDF computation via dynamic programming looks novel.
3. There are substantial improvements on experimental results, and the code is attached as part of the submission.

Weakness:

1. One part I would like to see better is I wish the authors could conduct experiments comparing the baseline [23] and the proposed work on more tabular data. Breastcancer and Diabetes seem not sufficient to me in Table 2. Moreover, results for the baseline [23] are directly copied from [23]. I would like to see more experimental results on more datasets to assess the effectiveness of the proposed method.

2. The other thing I'm concerned about is that all results reported in Table 2 have no standard deviations. It is not clear for me how the training and test set split was done or whether there is any overfitting.
questions: 1. Since you already have the code and the pipeline, do you mind comparing the baseline [23] and your proposed method on more tabular data during the rebuttal? Can you produce a table similar to Table 2 for datasets "mammo", "mushroom", "bank marketing", and "spambase"?

2. How did you do the train-test set split? Have you performed 5-fold cross validation? Could you conduct 5-CV on Table 2 and report the mean and standard deviation of both the baseline [23] and your proposed method? 
limitations: The authors have addressed the limitations in Section 7.
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: The paper focuses on the problem of certifying ensembles of decision stumps efficiently and deterministically. By leveraging discretization and piecewise-constant nature of decision stumps, the paper presents a way to compute the output distribution (PDF and CDF) efficiently in a closed form for standard input randomizations without requiring any sampling. This paper also discusses the joint certification over numerical and categorical features and demonstrates how the proposed scheme can be extended to handle categorical features. Consequently, using the deterministic certification scheme, the paper proposes a novel way to construct robust decision tree stumps that can then be used to build ensembles through bagging or gradient boosting and adaptive boosting. The empirical evaluations demonstrate the improved robust predictive performance of the proposed schemes over existing baselines and the ability of the proposed schemes to provide joint certificates. 

strengths_and_weaknesses: Strengths:

- This paper handles the robustness certification of a very widely used class of models -- ensembles of decision tree (stumps) -- and hence has the potential of significant impact given the wide use of such models in practical applications.

- The paper provides a concise but sufficient background on randomized smoothing that allows the reader to understand the challenges that the proposed de-randomized smoothing is able circumvent.

- It is very intuitive how the authors leverage the piecewise-constant structure in decision stump ensembles and the input randomization (independent across dimensions) to efficiently compute the output distribution. This is a great example of leveraging structure in the problem for efficient and accurate solutions. This efficient solution also allows the authors to develop a novel constructiion of robust decision tree stumps which would not have been possible without such an efficient computation of the output distribution.


Weaknesses:

- One weakness of the proposed scheme is the focus on decision stumps, which facilitates the creation of the per-feature meta-stumps, that are critical in the efficient computation. It is not clear how this technique would transfer to deeper decision trees since it is not clear to me how the meta-stumps could be created for such trees.


questions: - One question is if the authors can provide some intuition behind the dynamic programming based update in Algorithm 1. For example, why would the update of $\text{\tt pdf}[i][t + \Gamma_{ij}]$ need $\text{\tt pdf}[i-1][t]$? This could use a better explanation.

- In the learning via minimizing $H_{\text{entropy}}$ for $v_m$, it seems that the values $p^y$ would need to be constantly updated when performing the line search. Is that correct? This is not clear from the notation.

- The overall algorithm relies on the discretization level $\Delta$ (selected as 100). What is effect of this size of discretization $\Delta$ on the natural accuracy or certified accuracy? There must be a non-trivial tradeoff since a granular discretization would probably lead to a very noisy pdf while a coarser discretization would lead to a smoother one. Moreover, does the best level of discretization depend on the data (and if so how) or is a choice of discretization quite stable across datasets?


- How is the proposed PDF computation extensible to arbitrary decision trees? It is mentioned in the discussion of limitations.

limitations: The authors explicitly address limitations and potential negative societal impact. One of the limitations (being unable to "handle arbitrary ensembles of decision trees") is related to the weakness I listed above. The authors claim that it is possible to extend to decision trees, but the extension seems non-trivial. However, the authors are upfront with this limitation.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper deterministic smoothing for decision stump ensembles, and derive an MLE-optimal training method for smoothed decision stumps under randomization.
strengths_and_weaknesses: Strengths:
1. Good presentation 

Weaknesses:

1.  The necessity of using randomized smoothing to provide the robustness guarantee for Decision Stump Ensemble. 

2. The contribution is incremental.

questions: 1. The necessity of using randomized smoothing to provide the robustness guarantee for such a simple tree-based classifier, Decision Stump Ensembles. I think this paper might solve a simple problem (endowing Decision Stump Ensemble with certified robustness) in an overly complex way (randomized smoothing).

2. Is the comparison to [Wang et al. 2020] in Table 2 is fair?  I think comparing smoothed decision stump ensemble (linear classifier) to naive decision stump ensemble (non-linear classifier) is unfair. It is unclear whether the improvement is for the superior performance of non-linear classifier or the certification method.


[Wang et al. 2020] On lp-norm robustness of ensemble decision stumps and trees，ICML 2020.
limitations: The contribution of this paper is incremental. The paper just applies randomized smoothing to decision stump ensemble, and derives the robustness certificate for such a special classifier. The key contribution, deterministic certificate, is because of the overly simple structure of the base classifier (decision stump ensemble), instead of some new smoothing distributions (e.g., splitting noise [Levine et al., 2021]). We can also easily compute deterministic certificates for some other simple classifiers. For instance, we can derive the deterministic certificates for linear classifiers. The reason why we compute the probabilistic certificates for randomized smoothing is, the complex structure (almost black-box) of the neural network classifier. Moreover, I think the randomized smoothing for decision stump ensemble is only a simplified verison of the general problems studied in [Cohen et al., 2019] [Yang et al., 2020].

[Levine et al., 2021] Improved, Deterministic Smoothing for L_1 Certified Robustness, ICML 2021.

[Cohen et al., 2019] Certified adversarial robustness via randomized smoothing, ICML 2019.

[Yang et al., 2020] Randomized smoothing of all shapes and sizes, ICML 2020.
review_title: null

Meta-review: metareview: There were substantial discussions around this paper and its contributions. The authors did a good job of explaining and interacting with reviewers (with, as a consequence, a substantial raise of scores). To prepare the camera-ready version, it is strongly suggested to include the material introduced at discussion time, including the experimental results (K1dy) and use the intuitive explanation provided for the dynamic programming approach (7Kxj) to revamp a section / paragraph on a high-level explanation of the approach.
confidence: Less certain
Decision: Accept