Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a variant of interval bound propagation (IBP) for certified training using a small region around a preliminary center, e.g. from a PGD attack. Following a theoretical analysis of the employed box propagation, paying special attention to the role of ReLU activations, the authors present a set of experiments showing consistent improvements in terms of both the standard and robust accuracy, along with ablation studies concerning a number of related considerations.
strength_and_weaknesses: - Strengths
  - Introducing an auxiliary IBP problem admitting better approximations.
  - Theoretical analysis of hyperbox growth, with a detailed discussion of the role of ReLU activations following Shi et al. (2021).
  - Consistently improved accuracies corroborating the theory, in addition to a valuable ablation study.
- Weaknesses
  - The presentation deviates from professional technical writing in a number of critical parts. This leads to unnecessary confusion, as well as a couple inaccurate or unsubstantiated claims:
    - Improving on all SOTA methods
    - Promising to overcome the robustness-accuracy trade-off
clarity,_quality,_novelty_and_reproducibility: Clarity and quality are very good.

- Abstract
  - I strongly recommend that the authors refrain from prematurely framing their contribution as novel, as early as the fourth word in the abstract.
    - Such statements are extremely likely to end up harming the contribution. As other reviewers point out, the picture is not as clear cut with respect to randomized smoothing methods.
    - I would also recommend that the problem and method are described first, before how it compares to current SOTA.

- Section 1
  - What was meant to be conveyed through the statement "This yields networks with complex neuron interactions"? Is that about the ReLU activations? As it stands, it is rather vague and redundant.
  - Please spell out the main "commonly used settings" deferring further details to the experiments section.
- Section 3
  - First sentence: we address "this" challenge. What challenge?
  - It's not clear what the words "capture" and "actual" serve, and they appear more than once in the same paragraph.
  - I believe "often still captures the actual worst-case loss" was meant as "is a plausible approximation of the worst-case loss".
  - Expressing intuitions is okay, but there's no need to make inaccurate or unsupported claims in the process.
    - I strongly recommend that the authors rewrite the sentences following "Intuitively, often only small subsets of the input are misclassified and only a single point will realize the worst-case loss." Those statements almost surely don't hold in general, and need not be settled to communicate intuition in the first place.
  - It would help greatly to include rudimentary experiments to provide better intuitions and empirical evidence to support those motivating observations.
  - Second paragraph: we illustrate "this intuition".
  - I recommend to start a new paragraph at: "we tackle this problem", after clarifying in the first paragraph what the challenge/problem is.
  - This statement "leading to significantly reduced approximation errors and thus more precise, although not necessarily sound over-approximation of the loss" is rather too confounding.
    - Please define the propagation of the small region as a proxy or an auxiliary problem to the original problem of propagating the full region. Please include an equation similar to Eq.3 w.r.t. $B_p^{\tau_p}(x')$ or some other placeholder symbol.
    - Then, please explain why this new approximation problem admits a more precise solution, and why it can be understood as a regularization in-between the two extremes.
    - Then, please explain how it relates to the original approximation problem, clarifying what was meant by "not necessarily sound over-approximation".
  - The paragraph titled "Selecting the Propagation Region" is good enough. The leading paragraphs need not say as much, IMHO, and perhaps can be employed to better anticipate the theoretical analysis culminating in Theorem 4.1, and possibly other potential analyses going beyond BOX.

The rest of the paper looks good. Only that the repeated claim of overcoming the robustness-accuracy trade-off is too strong, and would at least requires demonstration on a range of learning problems, which the current work does not substantiate.
summary_of_the_review: ~~I'm assigning a score of 8 since 7 is no longer available.~~
The revised manuscript addressed my reservations.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper proposes a novel training method (SABR) that creates models balancing standard and certifiable accuracy. Conceptually, SABR combines the best of adversarial training (using strong heuristic attacks as a lower bound on the worst-case loss) and certified training (using overapproximations of the adversarial output region as an upper bound on the worst-case loss). In practice, SABR enables us to retain the high accuracy provided by adversarial training while producing networks that have a high certifiable accuracy using existing verification methods.

SABR uses a fast heuristic method (e.g. PGD) to find an adversarial example $x'$ within $\epsilon$ of the input $x$. Rather than propagating the entire input ball of radius $\epsilon$ to the output, SABR selects a ball of radius $\lambda \epsilon$ that 1) is contained within the original ball and 2) contains $x'$. This approach guarantees that the overapproximation from SABR 1) is contained in the overapproximation of the full adversarial input region while 2) likely contains regions of the output that are highly adversarial. While there are no theoretical guarantees that such an approach should provide any certifiable accuracy, the work demonstrates that SABR is on the Pareto frontier for standard and certifiable accuracy on $l_\infty$ networks.
strength_and_weaknesses: See the "Clarity, Quality, Novelty And Reproducibility" section below for strengths and weaknesses split by category.
clarity,_quality,_novelty_and_reproducibility: ### Quality
The idea behind SABR is straightforward, giving me the confidence that everything described is actually required to make things work. In addition, the SABR can be used with any combination of heuristic attack and propagation method; this enables future advances in the field (e.g. better heuristic attacks; more efficient propagation methods) to also improve the results from SABR.

Some suggestions and questions:

- Suggestion: I'd love to see an ablation study for the methodology described in Section 3. How would SABR perform if we ...
  - Used a weaker heuristic attack (e.g. FGSM)
  - Used a ball of size $\lambda \epsilon$ around the original input.
  - Used the ball around the preliminary centre x*
  - Used a different propagation method (does the 'well-behaved optimization' intuition from Jovanovic et al. still hold up here?)
  - Having said that, I understand that this all takes time, and I think this is already an excellent paper without that.


### Clarity
The attention to detail paid to the exposition of the paper (textual flow, choice of variables in equations, thoughtful use of color and symbols across text and figures) is remarkable, and makes understanding the contributions of the paper easy (which is how it should be)! Thanks for putting in the effort.

Some suggestions and questions:

- Suggestion: On Page 1, the paper states that “SABR, thus, achieves state-of-the-art standard and certified accuracies ... across all commonly used settings”. A casual reader might think this means that SABR achieves state-of-the-art standard accuracy as compared to neural networks _in general_ (or at least state-of-the-art standard accuracy as compared to neural networks with robustness claims that are not certified, like adversarially trained networks). More precise language would be helpful here. Some possibilities depending on what is true:
  - "SABR achieves state-of-the-art standard accuracy among all networks with non-trivial certifiable accuracy."
  - "SABR is on the Pareto frontier of standard and certified accuracy."
- Q: I'm unfamiliar with the formula for cross-entropy loss shown in Eq. 2 and Eq. 5. Would you point me to a reference? (Ok to not spend your rebuttal space explaining this to me ...)
- Minor Q: On Page 8, the paper states that "When propagating the full input region, the SABR trained network yields a much higher robust loss". Wouldn't the values be equal at $\lambda = 1$
- Minor Q: The paper is not clear on what happens if an adversarial example (i.e. one that is misclassified) is not found via PGD. Do we select an arbitrary propagation region, or do we simply select the x' that is closest to being misclassified (i.e. that with the smallest difference in logits between the correct label and the next label)
- Minor suggestion: Remembering which shade of blue corresponded to which accuracy was challenging. Maybe consider having standard / adversarial / certified be in different hues, with the three certified accuracies having the same hue and different luminances? (This is obviously up to you.)

### Novelty
The results presented represent the state-of-the-art in comparison to all existing non-probabilistic techniques. However, Salman et al. [1] seem to claim a certifiable and standard accuracy on $l_\infty$ CIFAR-10 networks of 68.2% and 86.2% respectively [2]. This is significantly better than the results reported in Table 1 (62.57% / 79.52%). Does this work explicitly exclude comparisons against randomized smoothing techniques (because of the probabilistic nature of the claim?) If so, that should be made clear in the abstract & introduction.

[1]: Salman, Hadi, et al. "Provably robust deep learning via adversarially trained smoothed classifiers." Advances in Neural Information Processing Systems 32 (2019). https://arxiv.org/pdf/1906.04584.pdf
[2]: See bottom of Page 8 for how they derive this from $l_2$ robustness.

### Reproducibility
The paper clearly describes details required to reproduce their results. (For example, the PGD attack used in their ablation study is clearly specified; no wondering on my part "how strong of a PGD attack did they use??)
summary_of_the_review: The paper presents a simple idea with a sound basis and strong empirical results which the field will be able to build on. The clarity and reproducibility of the paper is outstanding and represents a clear acceptance ( the failure to compare against results from randomized smoothing notwithstanding).
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work tries to improve certified training based on box propagation (DiffAI) / interval bound propagation (IBP). The proposed method tries to find a point with a high loss within the perturbation region by adversarial attack. Then box propagation is performed around the high-loss input point with a small box only, in contrast to the whole perturbation region used in previous IBP works. The goal of the modification is to improve both clean accuracy and certified robust accuracy. 
strength_and_weaknesses: Strength:
- This work proposes to combine adversarial attacks and box propagation / interval bound propagation such that the boxes used in box or interval bound propagation can be small.
- There is a theoretical analysis on the growth of boxes during interval bound propagation. The derivation has considered the imbalance between active and inactive ReLU neurons, compared to a previous work assuming symmetric input to ReLU activations at initialization only. 
- Compared to existing IBP-based works, this work has consistent improvement across different eps settings. 

Weaknesses:

- Although neither of IBP-R and IBP (Shi et al.’s version) achieve comparable performance on 2/255 and 8/255 at the same time compared to this work, this work relies on a careful choice of $\ell_1$ and $\lambda$ hyperparameters for each setting respectively (with values like 0.4, 0.6, 0.1, 0.7 in Table 5), while I don’t see a principled mechanism for setting these hyperparameters. It is unclear how sensitive the performance is w.r.t. different choice of hyperparameters. 
- MN-BaB (a much stronger verifier compared to IBP) is used for evaluating the models trained by this work, while previous works such as CROWN-IBP and IBP simply use IBP. Different methods in Table 1 were evaluated using different verifiers, and thus the comparison is not fair. This work spent a long time on verification (28h on CIFAR-10), while previous works using IBP at test time should be able to finish within a minute. It is unclear what the performance of previous works would be, if MN-BaB were used for those previous works (especially for CIFAR eps=2/255). 
- Compared to both IBP and IBP-R together, the improvement of the proposed work is marginal on robustness (on CIFAR 2/255, IBP-R has 78.19/61.97 clean/robust accuracy v.s. 79.52/62.57 by this work; on CIFAR 8/255, IBP (Shi et al.’s version) has 48.94/34.97 v.s. 52.00/35.25 by this work). 


clarity,_quality,_novelty_and_reproducibility: - Clarity and quality: The paper is mostly clear and well written. 
- Novelty: Using small boxes is novel
- Reproducibility: Code is provided.

summary_of_the_review: The method is sound and promising, and this work has demonstrated some improvement compared to previous works:
- Better clean accuracy
- More consistent performance across different perturbations.

However, experiments are not convincing enough:
- Improvement on robustness is not quite significant
- Different methods are evaluated using verifiers with significantly different strengths
- Slow verification at test time
- A lack of discussion on the choice of hyperparameters.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose a way to simultaneously increase both the certified and clean accuracy of certifiable networks by reducing the regularization that IBP training imposes at train time. They provide theoretical and empirical insights into why their method leads to good performance. 
strength_and_weaknesses: The paper has a clear motivation and is mostly well-written. The empirical results are good and the authors provide useful insights into why their method works well. The illustrations of IBP and SABR are very intuitive and helpful.

However, their final claim is much too strong ("Even more importantly, SABR lays the foundation for a new class of certified training methods promising to overcome the robustness-accuracy trade-off and enabling the training of networks that are both accurate and certifiably robust."). While it is true that their paper eases this tension, there is no reason to believe that this will lead to the elimination of the robustness-accuracy trade-off. Maybe it could be argued it would reduce the gap between certified-robustness and robustness.

The last sentence in the 2nd to last paragraph on page 3 ("Propagating a small region centred around the thus obtained adversarial example will then also capture the point inducing the actual worst-case loss.") is stated without justification. I am not aware of any work showing that this is true. If it exists, it should be cited. If it doesn't, then such a claim would require significant evidence.

I think the authors should be slightly more clear with the fact that the SABR loss does not provide an actual upper bound on the loss, i.e. it can only be used at train time. It would be quite helpful if they provided algorithm boxes for both train and test time in the appendix.

Minor points:
- I believe the $\epsilon$ in Figure 3 is drawn incorrectly - it should be the box's radius and not its diameter.
- In Figure 3, there is an $x_0^*$ that is never mentioned in the text.
- On page 5, the authors mention the typical magnitudes for growth rates in linear layers. Surely, these depend on how the model is trained? They should clarify if this holds for all training methods or only for theirs or what.
- Figure 6 is not great. Why are there no ticks on the x and y axes? 
clarity,_quality,_novelty_and_reproducibility: The paper is mostly written clearly and is easy to follow, despite some imprecise or misleading language in certain places (see above).

As far as I know, the method is novel.

The authors claim in the paper that they would provide anonymized code to reviewers, but as far as I can tell, they did not (in appendix nor via link). Therefore, it is hard to fully judge the paper's reproducibility.
summary_of_the_review: I think the paper presents a well-motivated method with strong results. If the authors slightly improve their presentation, I believe this paper will be of interest to the ICLR community.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors develop a novel approach for training networks to be certifiably robust against norm-bounded adversarial attacks. The key insight developed by 

Strengths:
1. The proposed technique is simple to implement and combines the strengths of adversarial training and certified training.
2. The paper achieves SOTA results relative to all prior deterministic certification/certified training methods.

Weakensses:
1. The paper does not outperform randomized smoothing as a certified defense. However, considering that randomized smoothing has other defects (only provides a probabilistic guarantee and requires significantly more inference time computation), the proposed techniques are certainly valuable. The initial version of the paper was not clear about this, but through the discussion phase the authors revised the paper to clarify this point.


justification_for_why_not_higher_score: The paper achieves SOTA results on deterministic certified robustness with a simple technique. However, the authors do not develop any significant theoretical insight or outperform SOTA certified robustness methods that use randomized smoothing. Hence, I would not recommend this paper to be accepted as an oral.
justification_for_why_not_lower_score: The paper achieves SOTA results on a hard problem (deterministically certified robustness to adversarial perturbations). This field has seen intense activity in recent years and being able to outperform the best techniques is indeed a significant achievement and deserves to be highlighted as a spotlight.
Decision: Accept: notable-top-25%