Venue: NeurIPS 2022 Conference

Reviews:

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: In this work, the authors extend the idea of randomized smoothing (used to tackle adversarial perturbations) to the paradigm of metric-learning based few-shot learning algorithms (e.g. Prototypical Networks). In particular, they propose an algorithm regarding how randomized smoothing can be used with vector-valued functions (e.g. the ones that compute the embeddings) which are used in Prototypical Networks to compute the distances of each query samples against the prototypes. Authors provide theoretical justification regarding their proposed algorithm. Empirical validation is also performed using multiple datasets. 
strengths_and_weaknesses: Strengths
------------
* The contribution in terms of the proposed algorithm to extend randomized smoothing to metric-learning based algorithms seems novel. Authors also provided theoretical justification to show that the proposed method can be provably used as a defense against adversarial attacks.
* The proposed algorithm is clearly explained, intuitively makes sense and also computationally cheap - thereby having a higher potential of being adopted in the community.
*  Experiments have been performed on multiple datasets from different domains and the method works consistently across these tasks.

Weaknesses
---------------
* The proposed algorithm is not compared against any other method from the literature. I understand it's a new problem area (randomized smoothing for vector-valued function) but I wonder if any other adversarial robustness algorithm(s) can be used to understand the relative performance gain obtained by this method.
* Although the paper mentions working in a few-shot learning setup, I do not see a clear reason why the method needs to be restricted to few-shot. The approach should work with most metric-learning algorithms and should be evaluated on those to understand how it works with those methods. 
questions: * For theorem 1, one of the assumptions is that $\lVert f(x) \rVert_2 = 1$ - is this assumption true because the embeddings are normalized to unit norm before computing the L2 distance? 
* For Mini-ImageNet, the experiments section mentions using 80 classes for training whereas in the official benchmark, there are 64 classes for training and 16 for validation. Was the model trained on the combined train + val set? I am asking this because for CIFAR-FS, it seems like the model was trained only on the 64 train classes (which is the common practice in few-shot learning literature).
limitations: Same as my comments on weaknesses above. I will consider changing my vote if authors can provide comparisons against existing methods from the literature or convince me why this method can not compared against any other method.
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: This paper proposes a certified robustness method for few-shot classification based on randomized smoothing. The paper focuses on prototypical classifiers where the classification is done based on the distance to the closest class prototype and class prototypes are the average of the features of class samples. Section 3 proposes two Theorems that guarantee the minimum perturbation size to change the label for a prototypical classifier to be proportional to the relative distance between the smoothed predicted features and two class prototypes. Section 4 proposes the estimation of the smooth prediction using finite samples and discusses a method based on confidence intervals to adaptively increase the number of samples until an acceptable confidence level is reached. Section 5 evaluates the effectiveness of the method on various few-shot learning benchmarks and shows improved certified accuracy for non-zero perturbation size.

strengths_and_weaknesses: Strengths:
- Theoretical results and empirical evaluations successfully demonstrate the robustness of the method and provide a practical algorithm for robust few-shot learning.
- The paper is easy to read.
- To the extent that I know, the idea is novel for certified robustness in few-shot learning.
- To the extent that I checked, the theoretical results are correct and the algorithm follows the theory.

Weaknesses:
- It is important to verify the certificates by empirically attacking a model within the certified radius. It would be interesting to see if the certificate radius is tight by attacking the model with slightly larger perturbations.
- Related work is missing other methods common in few-shot learning and a discussion on whether randomized smoothing could be extended beyond prototypical networks. For example see methods evaluated in [1].

[1] Triantafillou, E., Zhu, T., Dumoulin, V., Lamblin, P., Evci, U., Xu, K., ... & Larochelle, H. (2019). Meta-dataset: A dataset of datasets for learning to learn from few examples. arXiv preprint arXiv:1903.03096.

questions: - Complementary to Tables 2-3, can you include the distribution of the smallest sample size at which the confidence level is reached on each test dataset?
limitations: N/A
review_title: null

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: Applying randomized smoothing to few shot tasks is challenging since it heavily exploits the fact that classifiers are restricted to map an input to a fixed number of class probabilities. Previous work rely on improvement of empirical robustness or probabilistic guarantees of robustness. There is yet no theoretical guarantee on worst-case model behavior. The authors generalize and theoretically justify the idea of randomized smoothing to few-shot learning. Provable certification needs to be obtained not in the space of output class probabilities, but in the space of descriptive embeddings. Specifically, the authors generalize the analysis of Lipschitz-continuity to the case of vector functions and provide robustness guarantees for classification performed in the space of prototypical embeddings. This involves some adjustments to ensure the estimate of the Lipschitz constant is not simply an estimate of the norm of the multivariate Gaussian. 

To provide certification, the authors define the adversarial embedding risk, which is the minimum L2 distortion in the embedding space required to change the prediction of $g$ (distance of the embedding $g(x)$ to the nearest decision boundary between nearest two class prototypes). In practice, the authors compute an estimate of the distance to the closest decision boundary from $g(x)$ as two-sided confidence intervals for each class prototype nearest to the embedding (and in practice the distance is estimated by computing confidence intervals for the dot product of those prototypes). It can be shown from Theorem 1 that the lower confidence bound gives the certified radius for the embedded sample. The authors provide an analysis of the failure rate for the practical implementation, as well showing that the approach achieves a reasonable certified accuracy and abstain rate. 
strengths_and_weaknesses: Strengths:
-  The problem of performing certified robustness in the few-shot learning setting is presented in an intuitive way, primarily motivated by the difficulty of providing certified radius for samples embedded in a metric space, rather than fixed class probabilities. In this sense the problem the authors tackle is original and would be useful for the broader community. 
- The authors provide an analysis of the Lipschitz-continuity of vector functions, which enables the lifting of previous results to the novel context of few-shot embedding and offers a significant contribution. 
- A variety of experimental settings are studied, including CUB200, CIFAR-FS, and miniImagenet data. The results are structured similar to previous work and study the certified accuracy with respect to certification parameters, abstain rate, and runtime of the inference algorithm. 


Weaknesses:
- The certified accuracy is quite low and seems to decrease linearly with $\epsilon$ despite the data augmentation. It is difficult to visualize the presented certified accuracy without the baseline comparisons (e.g., standard uncertified model with $\epsilon$ random noise added, and certified model without data augmentation). 
- Unlike the previous techniques for certified robustness, the proposed method places some constraint on the underlying model, e.g., the assumption that the model performs prototypical learning. The authors do not discuss possible steps to generalize the proposed method to other few-shot techniques, e.g., model-agnostic meta-learning (MAML) or matching networks.  
- Some issues with the organization prevent the reader from fully appreciating the content. For example, the proof for Theorem 1 is labeled as Theorem 4 in the Appendix, likewise the proof for Theorem 2 is labeled as Theorem 5. A full text revision would be necessary to fix some content issues, such as streamlining the introduction and Section 4 to improve clarity. 
questions: - How can the approach be generalized for other few-shot learning schemes? 
- As previously stated, the proposed technique relies on prototypical learning embeddings (i.e., Theorem 1). In order to obtain a confidence interval for the distance between prototypes, the authors propose to compute confidence intervals for the dot product of vectors. Does this impose additional constraints on the posterior distribution of the embedding function? In practice the embedding function's posterior may not be well behaved, e.g,. is not centered at zero (all directions point towards same part of latent space) or has an elongated distribution (i.e., class centers are not decorrelated). Can the authors clarify these constraints?
limitations: - The authors have presented a first look at the certified robustness of few-shot learning models, although the treatment is limited to the context of prototypical learning. Some discussion of adaptation to other few-shot learning schemes would be helpful. 
- The results should be fleshed out to compare against baseline natural model (no certified radius) and the certified model without data augmentation.
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 modifies the randomized smoothing robustness approach to a setting where a DNN computes an embedding and the classification is done via nearest neighbor approach to a class prototype. The paper derives a robustness guaranteed bound, and a way to estimate it with high probability. 
strengths_and_weaknesses: Main strengths:
- The paper tackles the significant problem of robust learning in the few-shot case. 
- While the paper builds on Cohen et al, it uses the properties on this specific case to get a simple bound. The contribution is somewhat novel.
- Quality of writing is mostly good

Main weaknesses:
- The paper does not compare his results on others, e.g. Kumar & Goldstein, so it is hard to know if the paper has any empirical significance. The theoretical contribution is not significant enough to carry this paper by itself. 
- The confidence bound uses the Hoeffding inequality, but you use it to bound several estimations. In that case you need the union bound (or something better) to get a high-probability bound on all distances jointly. 
- One main limitation is runtime as it can can reach 5 seconds for a single predictions. As the runtime is dynamic, it would be useful to show a breakdown of runtimes on the datasets.

Other remarks:
- You use $n$ with two different meanings which is confusing (the dimension $\mathbb{R}^n$ and the number of MC samples in eq. 10). Should change to avoid confusion.
- The algorithms written aren't accurate. You use set notation but it isn't correct the way you write it down.
- First paragraph isn't well-written and I would recommend editing it.
- Line 19 "This shows how easy..." needs rewriting
- Line 166 use $g_1,g_2$ without defining them.
questions: The main issue for me is the lack of any comparison. Secondary is fixing the confidence intervals to take into account that there are multiple estimations

It would also be beneficial to estimate the empirical robustness and see how tight the bounds are. I think this will improve the paper but isn't requires as the previous remark.
limitations: While the authors have a section on limitations, I don't think the discussion was on the real limitations of paper. The main limitation that I see is runtime and it should be investigated more thoroughly.
review_title: null

Meta-review: metareview: This paper proposes a certified robustness method for few-shot learning classification based on randomized smoothing. The reviewers found the theoretical results and empirical evaluations successful in demonstrating the robustness of the method, providing a practical algorithm for robust few-shot learning problem. There were some concerns about the lack of comparison against other methods from the literature. But the authors addressed the issue in the rebuttal by running some additional experiments. The reviewers suggested that the authors motivate the use of FGSM and evaluate their method against other attacks as well. 
confidence: Certain
Decision: Accept