Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers the problem of adversarial robustness. For this problem the paper investigates the usefulness of randomized ensemble classifiers (REC) where one classifier is randomly selected from the ensemble during inference.  The main motivation behind considering RECs over deterministic ensembles is that the former has much smaller inference time than the latter. 

The paper makes two main contributions. The first contribution, which is on the theory front, involves careful characterization of the adversarial risk of RECs. In particular, the authors obtain reasonably tight upper and lower bounds for the adversarial risk of RECs that depend on the adversarial risks of the component classifiers in the ensemble. Based on these bounds, the authors provide some useful insights on how to design RECs with good adversarial risk guarantees. The second contribution is to provide a boosting style algorithm (BARRE) for constructing robust RECs that can tolerate adversarial attacks. The algorithm is mostly inspired by a recently proposed robust boosting technique called MRBoost.
strength_and_weaknesses: Strengths:
  *  Randomized ensembling is an interesting defense strategy that is under-explored in the literature. While there are some works that provide algorithms for building robust RECs, they are easily broken by adaptive defenses. So there is a need for better randomized ensembling strategies. The paper takes a step towards solving this problem. The theoretical results provided in the paper on bounding the adversarial risk of RECs, are novel and interesting. However, it is not immediately clear how the insights gained from these theoretical results can be used to develop a good algorithm (more on this below).
  *  The paper is easy to read. The clarity and presentation is good. The proofs are elementary and easy to follow.

Weaknesses:
  *  Motivation: 
      - The authors motivate the paper by saying that randomized ensembles can be computationally more efficient than deterministic ensembles. But there is a drawback of randomized ensembles that hasn't been brought up in the paper. In many application domains (e.g., healthcare), it is important to have deterministic predictions (otherwise it is hard to trust and understand these complex models). By moving to randomized ensembles, we lose this property. Can the authors provide some concrete use cases for randomized ensembles?
      -  Low compute resource devices also tend to have low memory. But RECs have high memory requirement ( same as deterministic ensembles). Given this, and the fact that deterministic ensembling techniques (like MRBoost) have better performance than BARRE, it is not entirely clear what the practical applications of RECs could be.  


  * Empirical results:  
     - the empirical results look weak. For example, in table 1, MRBoost has better performance than BARRE both in terms of robust and standard accuracy. This seems to be in contrast with the message one gets by reading the theory section in the paper. For example in page 6 (in paragraph titled "implications of upper bound"), it is mentioned that deterministic ensembles have much worse performance in the worst-case. Why is there this mismatch between theory and experiments? 
         - under what circumstances are deterministic ensembles better than RECs and vice-versa? 

 * BARRE: 
    - the algorithm looks almost identical to MRBoost, except for line 12 in Algorithm 2. In BARRE, the weights for each component classifier in the ensemble are recomputed after every boosting iteration. Whereas in MRBoost, all the component classifiers are given equal weights. Given this, why can't we simply add step 12 to MRBoost and get a randomized classifier out of it? How would the resulting algorithm compare with BARRE?
    - What is the computational overhead of BARRE over MRBoost?  It looks like computing weights (line 12) can be expensive, especially for large M.
    - In the introduction the authors claim that BARRE is based on the theoretical results in the paper (page 2). But I don't see any connection between the two. In particular, I don't see how the theoretical results in sections 3.2, 3.3 are used to derive this algorithm.  

 *  Theoretical Results: 
    -  A number of insights on how to obtain robust RECs have been provided in the discussion after theoretical results. Can these insights be used to derive a better algorithm than BARRE?

 * Minor comments:
    -  a more detailed explanation on why K=5 in section 3.2 would be helpful to the readers
    - 
clarity,_quality,_novelty_and_reproducibility: See comments above
summary_of_the_review: The clarity and presentation in the paper are good. The theoretical results are interesting and novel. But their usefulness is a little bit unclear. The empirical results look weak. Moreover, the proposed algorithm looks identical to MRBoost, except for a minor step which involves setting the weights of the component classifiers in the ensemble. Given this, I'm a little bit inclined towards rejecting the paper. But I'm happy to upgrade my score if the authors address my concerns.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: In this work, the authors analyze randomized ensembles through a theoretical perspective. A randomized ensemble classifier (REC) is an ensemble of classifiers where predictions are made using only one of the constituent models selected at random. The authors analyze this set up in an adversarial scenario and show a series of elementary facts about them including bounds on the worst-case risk of the REC and from these facts show how to set the probability that any one classifier is taken from the ensemble as the model from which a prediction is made. The primary motivations for this set up are claimed to be (1) greater computational complexity compared to ensembles (2) greater adversarial robustness compared to both ensembles and single models. 
strength_and_weaknesses: Strengths:

The authors provide promising empirical evidence that an REC can be made from an ensemble of classifiers such that one gets performance gains over the naive ensembling approach that would be typically taken.

Weaknesses: 

There are a couple of non-trivial drawbacks to this method that are not discussed. For the first contribution (having better computational complexity) the authors leave undiscussed the cost of this computational complexity. In particular, when using an REC one forfeits the uncertainty properties of an ensemble classifier (or Bayesian NN) which have been shown in many instances to help adversarial robustness and to aid in safety analysis. It feels like this is an important drawback: the computational gain here is not for free, you are sacrificing uncertainty. And this needs to be at the very least discussed if not empirically analyzed. 

The theoretical results themselves are also simplistic, bordering on trivial. I do note here that I am not an expert on RECs, so perhaps reviewers with more experience in these models will find these results more interesting than I. In addition to being very simplistic the claims about some of the theorems are not correct. Most glaring to me is the statement that "there are no worst-case performance guarantees with deterministic ensembling, even if all the classifiers are robust." This statement is either unqualified and therefore misleading or simply  incorrect. A deterministic ensemble (or BNN) is a single classifier: a model average. Therefore, they _do_ fit into Theorem 2 as there is only one model under consideration in these cases and therefore only one $\eta$ (risk value) and therefore they do have the same guarantees. Thus the statement regarding Theorem 2 is incorrect. This also points to the fact that Theorem 2 is bordering on trivial because it can be said of any classifier and is not unique to RECs. 

Finally, the results, while they do show a slight increase in performance, do not include any error bars. This seems a large omission given that the performance gains are ~1% in many cases and this is a randomized method so not reporting the variance is a red flag. 

Minor note:  I find the placement of the related works to be a bit jarring. If it could be placed in before the problem statement that might help the flow of the paper. But this is stylistic.
clarity,_quality,_novelty_and_reproducibility: The paper is relatively clear, but could be more notationally clear in a few sections. The provided intuitions are nice and help tho clearly understand what the authors mean. From the details in the paper the method would be reproducible, but one would need access to the code base to reproduce the exact numbers in this paper as there are inevitably hyper-parameters that are not reported here.
summary_of_the_review: Overall, I found the theory presented to be simplistic bordering on trivial. The claims are also incorrect in places (see the example in weaknesses).  The experimental analysis does not really report error bars which is also a red flag. Overall I think the work needs some further developments to be impactful.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The paper studies the limits of the adversarial robustness that can be obtained by combining $M$ different classifiers into one randomized classifier that at inference time, chooses one of the elements with certain probability. Some intermediate lower and upper bounds are presented that illustrate the main intuition behind the results. The main theorem is Theorem 2 which basically states that the randomized classifier in the worst case is as accurate as its worst component (trivial) and in the best case it can improve the robustness by a $1/M$ factor in the case where all classifiers have the same robustness (this is the interesting bound, and the result is stated in the more general case where each classifier might have a different robustness). Two algorithms are provided: the first obtains the best sampling probaility vector (assuming an oracle that obtains optimal adversarial perturbations) and the second is a boosting algorithm to obtain good classifiers to create the ensemble. In practical experiments it is shown that the second algorithm can lead to increased robustness against the state-of-the art ARC attack which was shown to break previous randomized ensemble defenses.

**After Rebuttal**
The authors have addressed some of my concerns. Despite not addressing the missing confidence intervals in the experiments, I am inclined to increase my score because of the following:

1. The method studied is interesting and significant, as there hasn't been an improvement in robust accuracy metrics from the single model paradigm in the last years. I believe most improvements have been on the training speed department rather than the robust accuracy metric. As such, exploring alternative paradigms like the randomized ensemble classifier studied here is one promising way forward.
2. A good amount of contributions are theoretical, and they provide guidance on how to develop better algorithms for building RECs. As such, I think it is possible to give the authors a pass regarding the fact that the improvements over the baseline are small and lack the confidence intervals. Focusing only on the experimental part would dismiss the interesting theoretical results which could be used or improved upon by others. Of course, after reflecting on the results presented, they appear quite intuitive, however, i think it is a stretch to call them 'trivial' as other reviewers have dismissed. To support such a statement they should have provided a simplified proof or argument, which I believe is not the case.
3. I disagree that not enjoying certain properties of BNNs would be a reason to dismiss researching RECs. Both are methods with pros and cons, and the goal of this paper as I understood was to advance the algorithmic and theoretical framework of RECs, rather than claim they are superior to BNNs in all aspects.
4. There are some concerns that this method is not suitable for some applications (like certain medical tasks). However, applications of ML have vastly different specifications and its hard to develop a one-size-fits-all method.

In the end, raising my score will not help much as there is still a big disagreement with two other reviewers. It would be most helpful if they re-evaluate their score after the author's rebuttal, and express if some of their concerns have been addressed.
strength_and_weaknesses: The main strength of this paper are the interesting theoretical bounds on the performance of randomized classifiers. This is important as the paradigm of training a single robust classifier appears to have hit a limit in terms of robustness, and the obtained lower bounds from Theorem 2 indicate that randomizing the classifier could lead to potentially big improvements. Of course, the lower bounds are only achieved when the classifiers at hand have the nice "incoherence" property where they don't share "vulnerable regions" where all are simultaneously mistaken by an adversary. The paper does a good job of presenting the case of two classifiers where the results are pretty straightforward and easy to understand, before presenting Theorem 2, which is the statement in full generality.

The math appears to be correct (I have checked some of the results in detail) and all the statements are clear, as well as the flow of the proofs is well organised. This is in contrast with the awful quality of the maths/proofs from average ICML/NeurIPS/ICLR submission, so this deserves a special mention. I would say however that some proofs are a bit more difficult than needed, for example in the proof of Lemma 5 in page 18, the items (1) and (2) are trivial. (1) simply follows from the fact that the sets are intersection of half-spaces and (2) follows from the well known equivalence between Vertex and Hyperplane descriptions of convex polytopes, see for example https://link.springer.com/content/pdf/bbm:978-0-387-46112-0/1.pdf

The theoretical results are not left without application, as they are used to define the algorithms 1 and 2, which builds a randomized classifier in stages, by adding robust classifiers while simultaneouly optimizing the sampling probabilities of the ensemble. Overall the theory justifies the design of the algorithm which is ideal.

The main weakness I see (unfortunately) is the empirical evaluation. Now, I think the settings studied are extensive, but the fact that there is randomness involved in the algorithm (through the use of SGD) means that one should provide some assessment of the confidence about the numbers stated in Table 1 and 2. The authors only provide a single number and it might be the case that the improvements are due to randomness. Hopefully this can be resolved simply by running multiple seeds and computing some confidence intervals. That would greatly improve the paper.

Finally another weakness is that the authors do not make an effort of presenting related results. I believe this topic should have been studied before at least in the context of clean accuracy (no adversary). The authors should comment on the relation to the papers:
1. https://aamas.csc.liv.ac.uk/Proceedings/aamas2014/aamas/p485.pdf
2. https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3156487/
3. https://www.cs.waikato.ac.nz/~ml/publications/2002/bounds.pdf
4. https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7044723

and cite them, as it seems they study a similar question (possibly in the non-adversarial setting). 
clarity,_quality,_novelty_and_reproducibility: Clarity: the paper is highly technical but it can be understood as the definitions/results are presented with care, and some particular cases are studied in detail first before presenting the more general results. Overall the paper makes pretty clear statements.

Quality: the technical quality is high. Some lemmas/theorems have easier proofs than others but overall I think the results are interesting and non-trivial. Some proofs could be simplified as I mentioned. However, the quality suffers in the experimental section due to the absence of confidence intervals. When there is some randomness in the algorithms this is a must, in order to be able to *bold* the results and claim that there is improvement over the baseline.

Novelty: this results seem natural in the context of clean accuracy, and I would say it is possible that similar questions have been studied before. Even though I cannot say the results are not novel, as I have stated before the authors should do a better job of finding and discussing some relevant results.

Reproducibility: the authors have provided the code for the experiments
summary_of_the_review: Upper and lower bounds for the robustness of ensemble classifiers are presented. The results are quite interesting and their presentation is clear despite being highly technical. The theory leads to the design of principled algorithms that are evaluated against strong baselines, showing promise for improvement. Overall the paper seems to make significant contributions. However two big issues remain: (1) lack of discussion regarding prior results in the context of (non-adversarial) accuracy of ensembles and (2) computation of confidence intervals for the numbers presented in the tables. These two last points prevent me from confidently recommending acceptance but I would increase my score if they are addressed.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper considers randomised ensemble classifiers (RECs) and study the problem of how to assign the probabilities to select each classifier to improve the adversarial robustness of the REC. The authors first show that minimising the adversarial risk is equivalent to minimising a piecewise linear function with linear constraints. Then, by relying on the convexity of the problem, they develop algorithms to solve the resulting optimisation problem first in the case of 2 classifiers and then they consider the general case.  Experimental analysis on CIFAR-10 and CIFAR-100 compare the proposed method with state-of-the-art approaches.
strength_and_weaknesses: Strength:

-Paper is well written

-The authors formally show that picking the optimal sampling probabilities for different classifiers is equivalent to optimising a piece-wise linear convex function over a convex set. This enables them to use tools from convex optimisation to solve this problem. I find this observation and the resulting algorithms interesting.


Weaknesses:

-Experimental results should be improved/clarified: 

a) Table 1 and 2 report different trends in the comparison with MRBoost. In fact, while in table 1 MRBoost almost always obtains better accuracy and robustness compared to BARRE (the method presented by the authors), the trend is reversed in Table 2. This is particularly confusing for the ResNEt-18 M=4 example, where while BARRE has same values in both Table 1 and 2, for MRBoost these are different.

b) Please, report computational times. Also, it would be interesting to also consider larger values of M.

c) FLOPs in Table 1 is not defined
 

-Theorem 1 guarantees that to improve the empirical risk of the ensemble compared to that of the individual classifiers, region $\mathcal{R}_1$ should contain large probability mass wrt the input distribution. However, a discussion on how often this condition is verified in practice is missing. Intuitively, I believe that, due to the transferability of adversarial examples, such region will not be large in general. Nevertheless, a possibly interesting direction could be to train the individual classifiers in the ensemble with different adversarial training techniques in order to enforce that $\mathcal{R}_1$ is large, while keeping each classifier accurate and robust to a particular class of attacks.

-The fact that randomized classifiers can improve the adversarial robustness wrt the individual classifiers is well known. Therefore, also considering the above comments on the experiments, the results of the paper feel a bit incremental.

-Finally, the comparison with the literature completely misses Bayesian ensembles, which have been already shown to be robust to adversarial examples, see e.g. [1]. 


[1]: Carbone, Ginevra, et al. "Robustness of bayesian neural networks to gradient-based attacks." Advances in Neural Information Processing Systems 33 (2020): 15602-15613.

clarity,_quality,_novelty_and_reproducibility: The paper is well written. However, I still have some doubts on the reproducibility of experiments and on the novelty (see the Strength and Weaknesses Section for detailed comments)
summary_of_the_review: The paper studies an important problem and presents an interesting new perspective that makes possible to use of tools from convex optimisation. However, experimental results do not seem to present a substantial improvement compared to state-of-the-art.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Interesting results on the quality of randomised ensemble classifiers (RECs). The paper has some nice observations about the piece-wise linearity of the risk, which leads to a few theoretical results and an algorithm. Under a certain viewpoint, results are not so sophisticated, but they may have good use. Impact may well depend on whether RECs are appropriate for a particular task, and this seems to be another discussion point too. There have been a few points of attention, and authors have tried to clarify them in the discussions. The paper is arguably heavy (even if the underlying results might not be so mathematically heavy) and it might not be trivial to follow the importance of the theoretical results without resorting to the appendices. Unfortunately this requires extra time that some might not have in a short and super-busy reviewing process. Initially reviewers were mostly negative, and during the reviewing process a couple of reviewers improved their scores and viewpoint about the submission. However, this has not resolved the split opinions about the submission. It is apparent from the discussion that some points have not been fully resolved.

justification_for_why_not_higher_score: There are still some open points and split opinions among reviewers. I personally think that doubts and some other issues would be fixed if this was a longer reviewing process of a journal, but this is a guesstimate. Given the information that I have at hand and the highly competitive nature of ICLR in terms of space for contributed work during the conference, this submission remains uncertain to me in order to give a more positive recommendation.
Decision: Reject