It is well-known that classifiers are vulnerable to adversarial perturbations. To defend against adversarial perturbations, various certified robustness results have been derived. However, existing certified robustnesses are limited to top-1 predictions. In many real-world applications, top-k predictions are more relevant. In this work, we aim to derive certified robustness for top-k predictions. In particular, our certified robustness is based on randomized smoothing, which turns any classifier to a new classifier via adding noise to an input example. We adopt randomized smoothing because it is scalable to large-scale neural networks and applicable to any classifier. We derive a tight robustness in 2 norm for top-k predictions when using randomized smoothing with Gaussian noise. We find that generalizing the certified robustness from top-1 to top-k predictions faces significant technical challenges. We also empirically evaluate our method on CIFAR10 and ImageNet. For example, our method can obtain an ImageNet classifier with a certified top-5 accuracy of 62.8% when the 2 -norms of the adversarial perturbations are less than 0.5 (=127/255).
This paper builds upon the random smoothing technique for top-1 prediction proposed by Cohen et al. for certifying top-k predictions with probabilistic guarantees, which enjoys good scalability to large neural networks and in principle can be applied to any classifier. 
- Contributions:
1. The authors aim to provide (probabilistic) certification on top-k predictions, which to my knowledge is the first work to consider this setup. Many applications such as recommendation systems indeed use top-k predictions as a performance measure. The problem setup is new and important in the research of robustness certification.
2. In terms of technical contributions, the authors identify the difficulty of extending top-1 prediction to top-k prediction, due to the requirement of simultaneous confidence interval estimation of the bounds on the actual class predictions. To cope with this difficulty, the authors proposed simultaneous confidence interval estimation based on Clopper-Pearson method and Bonferroni correction. However, I am not sure the difficulty is caused by the necessity of estimating multiple probability bounds, or simply the limitation of the proposed algorithm. I hope the authors can address my concerns in the Questions below. 
3. Experimental results on Cifar-10 and ImageNet showed improved lower bound on certified L2-norm radius when increasing k. The authors also performed an ablation study of different parameters in the proposed algorithm.
- Questions:
1. Intuitively, when extending top-1 certification to top-k certification, one would expect using ordered statistics of the prediction outputs from the randomly perturbed inputs. As long as the original label's prediction probability is in the top-k label set, the smoothed classifier is directly certified. Instead of ordered statistics, the authors tackle this problem by considering estimating upper and lower bounds of each class prediction probability. Therefore, the problem becomes more difficult as k increases, since this indirect approach needs to simultaneous estimate those probability bounds. I wonder the current approach will be suboptimal when compared to the ordered statistics approach. I would like to know the authors thoughts on this regard. That is, is the claimed difficulty an outcome when using the proposed indirect bound estimation for certification, or it's provably more difficult?
2. The discussion on Fig.3 says "We observe that  \sigma controls a trade-off between normal accuracy under no attacks and robustness. Specifically, when  is larger, the accuracy under no attacks (i.e., the accuracy when radius is 0) is larger, but the certified top-k accuracy drops more quickly as the radius increases." However, it seems that larger \sigma actually gives lower accuracy under no attacks in Figure 3. Please clarify.
Overall, this paper brings some new insights and results in robustness certification, but some claims and statements need to be further justified. I am happy to increase my rating if my concerns are addressed.