Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This work provides an algorithm to ensure robust training of an ML model with just black-box knowledge of it i.e., input and output access. The algorithm relies on using Denoised Smoothing with zeroth-order optimization where the gradients are estimated using random perturbations (finite-differencing). They avoid the computational burden and high variance of these estimates by first training an auto-encoder to reduce the inputs to a low-dimensional subspace. They show over different architectures and multiple datasets (Cifar10, STL10, image reconstruction over MNIST) that the proposed algorithm performs better than the baseline which is the Denoised Smoothing algorithm by Salman et al.
main_review: Strengths:
- They show comparison with the baselines over a sufficiently wide range of experiments.
- The argument for the use of the Autoencoder is intuitive and clearly works. The algorithm itself is simple, building on tools that have been known to work.
- The algorithm itself is truly black-box in that it does not require knowledge of the model that is being robustified.

Concerns/Comments:
- Though it is fair that the algorithm is only compared against other black-box algorithms, it would be useful to show the certified accuracy(CA) of a whitebox algorithm like (Cohen et al., Madry et al.) as a comparison. This would illustrate the gap between the two regimes.
- While the autoencoder reduces the variance of the gradient estimates, the fact that $2q$ forward passes need to be made for every gradient computation, should indicate that turning this method into a ZO-method increases the computational burden. I did not see this discussed in the paper. A comparison would be useful.
- I believe there is a typo on page 4 where $\mathcal{A}_2$ is used when it should be $\mathcal{R}_2$. Either choice of nomenclature is fine as long as it is consistent.
- Is there any justification for choosing $q=192$ in the experiments on Cifar10?
- The authors mention that pre-training $D_{\theta}$ causes it to get stuck at a local optima. However, this doesn't seem to happen to $\theta_{ENC}$. I was also curious to see if any experiments were conducted where the autoencoder was fixed after pre-training and only $\theta$ was trained. Does this perform poorly?
- Is my understanding correct in that the accuracies reported in Table 2 are over different sets of data? It seems like the algorithm outputs a certified radius for each point and we compute the CA over only points which have a certified radius greater than $r$. I find this confusing because Salman et al. report a SA for every $r$ while in this setting SA only makes sense for $r=0$. Can you clarify?
- In Table 2, RGE and CGE for $q=192$ are quite different. However, if the AE converges correctly then the random directions in RGE should all be linearly independent and provide an equivalent estimate to the standard basis directions. Is there any intuition for this difference?
summary_of_the_review: Overall, I find the algorithm to make sense intuitively and the experiments are quite thorough. The results are superior to the current baselines and therefore I am satisfied with this paper.

~However, I have a few concerns and clarifications. If they are resolved, I would recommend the paper to be accepted.~
[Update]: I am satisfied with the author's response. I am increasing my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a novel approach to robustify black-box models to address the problem of black-box defense, which arises due to the concerns of privacy. The approach proposed by the authors essentially incorporates zero-order optimization on a prepended denoising smoothing(DS) module, with an autoencoder connecting the DS and model, termed as “ZO-AE-DS”, which the authors claim that it can robustify models using only model queries.
main_review: Strength:
The the proposed ZO-AE-DS paradigm is novel to me. The idea of black-box defense is very interesting, which is actually a very important real-world application scenario. Compared to the competing method FO-DS, the authors eliminate the need for white-box model by applying zero-order optimization, and also use an autoencoder to avoid dimension issues for calculation. Then they demonstrate it with experiments that AE can also improve robustness. The paper is overall easy to follow, and clearly written. Experiments are thorough and well organized.

Weakness:
The performance of ZO-AE-DS (zero-order) does not outperform FO-AE-DS (first-order) since the latter needs a surrogate model whereas ZO only requires access to model’s queries. The question is that it is not too hard to obtain a surrogate model if we have queries access. This paper can be further strengthened if benefit of avoiding surrogate models are articulated. 

Typo: “a recently-developed A2-type approach (Salman et al., 2020),” should be “R2-type”

summary_of_the_review: Question: Both ZO-AE-DS and FO-AE-DS outperforms their counterparts without AE module. Considering the denoising nature of AE, the DS+AE can be viewed as a type of stacked DS. Have the authors tried other combinations of stacked DS? Is it possible to also increase the performance like inserting AE to FO-DS? Overall I think the proposed zero-order optimization for black-box defense is a very promising application scenario. Although the method seems doesn’t outperform FO version with surrogates, I think it has broader applicability owning to its minimum assumptions.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors formulate the problem of black-box defense and propose a novel black-box defense approach called the Zero Order AutoEncoder-based Denoised Smoothing (ZO-AE-DS). Black-box defense corresponds to situations in which the defense model information cannot be obtained due to privacy protection in real scenarios. ZO-AE-DS introduces zero-order optimization on the structure of denoised smoothing (DS) to estimate the gradient and uses an Autoencoder (AE) to connect the denoiser with the model so that zero-order optimization can be conducted in a (low-dimension) feature embedding space.
main_review: Pros:
1.	The concept of black-box defense is novel and interesting, and this paper is the first work to tackle the problem of query-based black-box defense.
2.	The author shows the idea of how to solve the black-box defense step by step. The paper ingeniously applies the zero-order optimization method to the DS method and leverages autoencoder to bridge the gap between first-order and zero-order optimization.
3.  The paper is clearly written and easy to follow.


Cons:
1.	The experiments are conducted on CIFAR-10 and STL-10. Also, It can be observed that the larger the picture, the worse the defense effect. Is this method still effective on ImageNet? If ZO-AE-DS cannot be applied to ImageNet, then the method is of little significance. After all, black-box defense is designed to solve the problem in real-world scenes.
2.	The references are all before 2020. The authors should add more recent works. 
3.	The baselines are not strong enough. The experiments are all compared with DS and its variants.

summary_of_the_review: Overall, this paper formulates the problem of black-box defense and provides a feasible black-box defense framework. It is clearly written and easy to follow.The updated experiments are comprehensive and convincing.

[Update]: Though the method still can not really handle ImageNet, the authors' rebuttal addresses most of my concerns. Also, the setting of black-box defenses is novel and should be encouraged. Hence, I am increasing my score to 8.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper explores an exciting direction, i.e., black-box defense, where defense methods cannot access parameters of the target model when endowing the target model with certified adversarial robustness. However, the black-box defense setting considered in this paper has been studied in [1]. 
main_review: The contribution of this work may be relatively incremental. This is because the black-box defense setting has been considered in [1]. The differences between this work and [1] are: 1) query-based black-box defense is studied in this work 2) the authors introduce an AutoEncoder to reduce the variance of gradient estimation. Moreover, introducing AutoEncoder to promote gradient estimation has been studied in [2].

Maybe, above comments are somewhat harsh. In fact, I have felt that. Thus, if the authors can highlight the contribution of this work, especially compared with [1], I am willing to raise my rating.

I guess one contribution of this work may be that the authors have shown that query-based black-box defense is simple yet effective and improving the efficiency of gradient estimation is a good strategy for the query-based black-box defense setting.

[1] Denoised Smoothing: A Provable Defense for Pretrained Classifiers. NeurIPS2020.
[2] AutoZOOM: Autoencoder-based Zeroth Order Optimization Method for Attacking Black-box Neural Networks. AAAI2019.

summary_of_the_review: I like this work, but I do hope the authors can further highlight the contribution, especially when comparing this work with [1].
review_title: null

Meta-review: All reviewers have converged to an unanimous rating of the paper, highlighting, in the paper or during the discussion, many strengths, including a compelling approach clearly relevant to applications and its solid range of experiments. 

A clear accept, and I would encourage the authors to push in the final version the experiments and discussions following the threads with reviewers (in particular, Vo8C and ULvk).

Thanks also to authors and reviewers for a thorough discussion which helped to strengthen further the paper's content.

AC.
Decision: Accept (Spotlight)