Smoothed Embeddings for Certified Few-Shot Learning
Authors: Mikhail Pautov
Olesya Kuznetsova
Nurislam Tursynbek
Aleksandr Petiushko
Ivan Oseledets
Venue: NeurIPS 2022 Accept (2022)
Keywords: Certified robustness
randomized smoothing
few-shot learning

Abstract: Randomized smoothing is considered to be the state-of-the-art provable defense against adversarial perturbations. However, it heavily exploits the fact that classifiers map input objects to class probabilities and do not focus on the ones that learn a metric space in which classification is performed by computing distances to embeddings of class prototypes. In this work, we extend randomized smoothing to few-shot learning models that map inputs to normalized embeddings. We provide analysis of the Lipschitz continuity of such models and  derive a robustness certificate against $\ell_2$-bounded perturbations that may be useful in few-shot learning scenarios. Our theoretical results are confirmed by experiments on different datasets.

Smoothed Embeddings for Certified Few-Shot Learning
Mikhail Pautov
Olesya Kuznetsova"
Skolkovo Institute of Science and Technology
Skolkovo Institute of Science and Technology
Nurislam Tursynbek
Aleksandr Petiushko
The University of North Carolina at Chapel Hill
Moscow State University, Nuro, Inc.
Ivan Oseledets
Skolkovo Institute of Science and Technology, AIRI
Abstract
Randomized smoothing is considered to be the state-of-the-art provable defense against adversarial perturbations. However, it heavily exploits the fact that clas- sifiers map input objects class probabilities and do not focus the ones that learn a metric space in which classification is performed by computing distances to embeddings of class prototypes. In this work, extend randomized smoothing to few-shot learning models that map inputs to normalized embeddings. We pro- vide analysis of the Lipschitz continuity of such models and derive robustness certificate against fz-bounded perturbations that may be useful in few-shot learn- ing scenarios. Our theoretical results confirmed by experiments on different datasets.
Introduction
Few-shot learning is a setting in which classification model is evaluated on the classes not seen during the training phase. Nowadays quite few few-shot learning approaches based on neural networks are known. Unfortunately, neural network-based classifiers are intimately vulnerable to adversarial perturbations [41] IQ accurately crafted small modifications of the input that may significantly alter the model's prediction. This vulnerability poses a restriction the deployment of such approaches in safety-crie critical scenarios, so the research interest the field of attacks on neural networks has been great in recent years.
Several works studied this phenomena in different practical applications image classification
semantic segmentation These studies show that is easy to force a model to behave in the desired way by applying an imperceptible change to its input. As result, defenses, both empirical
2
R4
3
40
object detection 17
26
4%
50,, face recognition 1S
5 54
50
55
14 and
provable [1] 21
1S 46 351 were proposed recently. Although empirical ones can (and often are) broken by more powerful attacks, the provable ones are of a big interest since they make it possible to provide guarantees of the correctness the work of a model under certain assumptions, and, thus, possibly broaden the scope of tasks which may be trusted to the neural networks.
22
Randomized smoothing [21 3 2 is the state-of-e tfetthe-art approach used for constructing classification models provably robust against small-none additive adversarial perturbations. This approach is scalable to large datasets and can be applied to any classifier since does not use any assumptions
'The code for this paper is available at htttpe////htbbocm////////eeeeeee
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Certify
Noisy images
Lipschitz constant L
Yes
Image
Smoothed embeddings [(+te)
1 Σ f(+t))
6||2
7.?
No
Abstain from classification
Model f(-)
Adversarial embedding risk
Figure 1: Illustration of certification pipeline for single image Given model f(.) and realisations of zero-mean Gaussian noise E1. En ~ NO, x2)), an estimate g(x) = 2i- f(x Ex) of g(x) 2 f(x + a) is computed. Note that g(z) is L-Lipschitz with L 22/To², according to the Theorem [ The number samples is increased until adversarial embedding risk y from the Theorem 2 is computed with Algorithms 2 and certified radius Z is determined. The model g(-) is treated as certified at x for all additive perturbations 5 ||ó < r.
about the model's architecture. Generally, the idea the following. Suppose, we are given a base neural network classier f: R.D -> j0, 1] that maps an input image to a fixed number of K class probabilities. Its smoothed version with the standard Gaussian distribution is:
g
E f(r +
fx)
e~N((0,))
As shown in 33, the new (smoothed) classifier is provably robust at x to fz-bounded perturbations if the base classifier f confident enough at x. However, the proof certification heavily exploits the fact that classifiers are restricted to mapping input to fixed number of class probabilities. Thus, directly applying randomized smoothing to classifiers in metric space, such as in few-shot learning, is a challenging task.
There are several works that aim at improving the robustness for few-shot classification A0 However, the focus in such works is either on the improvement of empirical robustness or probabilistic guarantees of certified robustness; none of them provide theoretical guarantees on the worst-case model behavior.
In this work, fill this gap, by generalizing and theoretically justifying the idea of randomized smoothing to few-shot learning. In this scenario, provable certification needs to be obtained not the space of output class probabilities, but in the space of descriptive embeddings. This work is the first, to our knowledge, where the theoretical robustness guarantees for few-shot scenario are provided.
Our contributions summarized follows:
We provide the first theoretical robustness guarantee for few-shot learning classification.
Analysis of Lipschitz continuity of such models and providing the robustness certificates against lg bounded perturbations for few-shot learning scenarios.
We propose estimate confidence intervals not for distances between the approximation of smoothed embedding and class prototype but for the dot product of vectors which has expectation equal the distance between actual smoothed embedding and class prototype.
Problem statement
2.1 Notation
We consider few-shot classification problem where we are given set of labeled objects (x1, bi),.... (Fm, ym) where x; RDD and y/i E [1,...,K) K} are corresponding labels. We fol- low the notation from [39] and denote S₁ as the set of objects of class k.

---

2.2 Few-shot learning classification
Suppose we have function f RD R that maps input objects to the space of normalized embeddings. Then, d-dimensional prototypes of classes are computed as follows (expression is given for the prototype of class k):
1
Σ f(x). RES
C₁:
Sk
In order classify a sample, one should compute the distances between its embedding and class prototypes sample is assigned to the class with the closest prototype. Namely, given a distance function p IRd IRd >> [0, +oo), the class e of the sample computed as below:
arg min (f()) k)
Given an embedding function f. our goal is to construct a classifier g provably robust to additive perturbations A of small norm. In other words, want to find norm threshold such that equality
arg min p (g(z), kE(
min p(g( 8x,
kE(1.....K
will be satisfied for all 8: 1001l L.
In this paper, the solution to problem of constructing a classifier that satisfies the condition in is approached by extending the analysis of the robustness of smoothed classifiers described in to the case of vector functions. The choice of the distance metric in 4 is motivated by analysis of Lipschitz-continiity given in the next section.
Randomized smoothing
3.1 Background
Randomized smoothing 21 8 is described as technique of convolving a base classifier f with an isotropic Gaussian noise such that the new classifier g(x) returns the most probable prediction of of random variable ş ~~ ~~x(x [2],, where the choice of Gaussian distribution is motivated by the restriction on g to be robust against additive perturbations of the bounded norm. this case, given classifier f IR + [0, 1] and smoothing distribution I2I), the classifier looks as follows:
g(x) (2m02) [ f(x +)
(-1
||=113 20
de.
One can show by Stein's Lemma that given the fact that the function in Vx E D(F), (f()) I 1), then the function g is LLpischitz:
5 is bounded (namely,
v' E D(g), l19(x) g(x') l12 s L|x 2'112,
(6)
with L
T what immediately produce theoretical robustness guarantee on
Although this approach is simple and effective, it has serious drawback: in practice, it is impossible to compute the expectation in (5) exactly and, thus, impossible to compute the prediction of the smoothed function g at any point. Instead the integral is computed with the use of Monte-Carlo approximation with n samples to obtain the prediction with an arbitrary level confidence. Notably, to achieve appropriate accuracy of the Monte-Cau approximation, the number of samples should be large enough that may dramatically affect inference time.
In this work, we generalize the analysis of Lipschiiz-coninuiity the case of vector functions g : D >> Rd and provide robustness guarantees for classification performed the space of embeddings. The certification pipeline is illustrated in Figure

---

3.2 Randomized smoothing for vector functions
Lipschitz-continuity of vector function. In the work of B8 the robustness guarantee from proved by estimating the Lipschitz constant of smoothed classifier. Unfortunately, straightforward generalization of this approach to the case of vector functions leads to the estimation the expectation of the norm of multivariate Gaussian which is known to depend on the number of dimensions of the space. Instead, we show that a simple adjustment to this technique may be done such that the estimate of the Lipschitz constant is the same as for the function in (50. Our results are formulated in the theorems below proofs of which are moved to the Appendix order not distract the reader.
Theorem 1. (Lapschitz-confimitty of smoothed vector function) Suppose that TR. IRd is deterministic function and g(x) = 1B5=~N(0.001)) f - + E) is continuously differentiable for all x. If for all x, (=) = 1, then g(x) is L- Lipschitz 12 nono with L
zO²
Remark 1. We perform the analysis of distance metric in is di-tance We do not consider other norms in this paper.
in the Theorem
7 in 12 --norm, so the
Robust classification in the space of embeddings. To provide certification for a classifica- tion in the space of embeddings, one should estimate the maximum deviation of the classi- fied embedding that does not change the closest class prototype. In the Theorem 2 we show how this deviation is connected with the mutual arrangement of embedding and class prototype.
Theorem 2. (Adversarial embedding risk) Given input image R and the embed- ding g Rd + Rd the closest point on to de- cision boundary in the embedding space (see Figure 2) is located at a distance (defined as adversarial embedding risk):
g(x)
Ci
C2 g(x)))
||0 (x)
7 ||
2 C2
1
(7) where C₁ E d and 02 E d2d are the closest prototypes. The value of is the distance be- tween classifying embedding and the decision boundary between classes represented by 01 and c2. Note that this is the minimum l2 disitorrio in the embedding space required to change the prediction of g-
C2
Figure 2: Illustration of the Theorem one-shot case. The direction of adversarial risk the space of embeddings is always parallel to the vector C2. This also true for the case ||e l|2 * ||a2||2-
Two theorems combined result in an robusstsss guarantee for few-shot classification as:
Theorem 3. (Robustness guarantee) Lobrustsss guarantee r for an input image x in the di-immnsional inpul metric space under classificution by classifier g from the Theorem D is r r= 7. where is the Lipschitz constant from the Theorem and Jand y is the udversarial risk from the Theorem 2 The value of r is the certified radius of g at or, in other words, minimum l 1 distortioonn in the input space required to change the prediction of g. The proof of this fact straightforwardly follows from the definition 66) and results from Theorems 7
4 Certification protocol
In this section, we describe the numerical implementation our approach and estimate its failure probability.
4.1 Estimation of prediction of smoothed classifier
As mentioned previously, the procedure of few-shot classification performed by assigning an object to the closest class prototype. Unfortunately, given the smoothed function in the form from the Theorem I and class prototype e₁ from ( it is impossible to compute the value p(g(x), ex) explicitly well to determine the closest prototype, since it is in general unknown how does g(x) look like.

---

We propose both to estimate the closest prototype for classification and to estimate the distance to the closest decision boundary y from Theorem 2 as the largest class- preserving perturbation in the embedding space by computing two-sided confidence intervals for random variables
& = 11)(2)) c1
ξK [0((=) - cx 1l
(8)
where = f(x + ) is the estimation of ((x) computed as empirical mean by samples of noise, and one-sided confidence interval for from the Theorem respectively. Pseudo-code for both procedures is presented in Algorithms 1
Algorithm Closest prototype computation algorithm.
GIVEN: base classifier f. noise object æ, number of samples n for ((x), class prototypes {c {qhen. maximum number of samples I' and confidence level a, RETURNS: index A of the closest prototype.
Function CLOSEST( x, n, {G) T,
fs+ 1-4-0 0 i nin
while n < do
Ei...., En NN0,
((x) + Σ i= (or (a +2)
fs + (g())())
for all [1...., K] do
C= C dsToC + p(fs, C)
(lc, uc) + TwSSi
4 1 loo U4 + uc
end for
A < arg min (
if us < min( (=))4)) then
Return A, fs
else
n - n+ [Increase number of samples used for computing an approximation ((x) until the number of observations is large enough to determine two leftmost intervals or until end if end while EndFunction
The Algorithm describes an inference procedure for the smoothed classifier from the Theorem T the Algorithm uses Algorithm and, given input parameters, estimates an adversarial risk from
the Theorem 2 it determines two closest to the smoothed embedding g(x) prototypes A and B and produces the lower confidence bound for the distance between gxx) and the decision boundary between A and B. Combined with analysis from the Theorem I it provides the certified radius for sample the smallest value of l2 -eroorm of perturbation in the imput space required change the prediction of the smoothed classifier. In the next subsection, we discuss in detail the procedure of computing confidence intervals in Algorithms
4.2 Applicability of algorithms
The computations of smoothed function and distances to class prototypes and decision boundary in Algorithms 2 are based on the estimations of corresponding random variables, thus, is necessary to analyze the applicability of the algorithms. In this section, we propose a way to compute confidence intervals for squares of the distances between the estimates of embeddings and class prototypes.
Computation confidence intervals for the squares distances. Recall that one way to estimate the value of parameter of a random variable is to compute confidence interval for the corresponding statistic. this work, we construct intervals by applying well-known Hoeffding inequality [K3 in the form
5

---

2
P (IX - B()) 2 1) S 2 2xxp
(9)
a,)
where X and B(X) sample mean and population mean of random variable X, respectively, is the number of samples and numbers a; b, are such that P(X; E (a,, b;)) =
Algorithm Adversarial embedding risk computation algorithm. GIVEN: base classifier f. noise object æ, number of samples n for (xx), class prototypes {c) maximum number of samples for ((x) and confidence level a lower bound for the adversarial risk
RETURNS:
Function EMBEDDING-RIKKG a, { T,
B, f3g +- CLOSEST( 0, 1e a.))
A, [SΛ + a, n. {4]
[s + [8A f8B
< 0
for all E
1eB-911
-call
78 < 78 (7)
end for + LoverConf
Return 1 EndFunction
However, a confidence interval for the distance [lğ(x) cs l|2 with certain confidence covers an expectation of distance (((l)(()) e* (22), not the distance for expectation [[E()(()) cx cx)ll2 [lo(x) - 1ull2)
To solve this problem, propose to compute confidence intervals for the dot product of vectors. Namely, given quantity Ex.k = (g(x) Cx, g(x) - cx), we sample its unbiased estimate with at maximum 2n samples of noise (here we have mention that the number of samples n from Algorithm| actually doubles since we need a pair of estimates ((x) of smoothed embeddings):
2
Ex
f(z +
Σ
f(x -
(10)
j=n+1
and compute confidence interval (Le,k k) such that given
21 x Σラ (b: a;)2
2exp
(-EX
(11)
the population mean E(E,,k) is most probably located within it, or, equivalently, (1akk I B(E,,)) < Mg,k) 2 - a. We have to mention that there are three confidence inter- vals for three terms (one with quadratic number of samples and two with the linear numbers of samples) in the expression I0 that is why there fraction & in the equation III.
Also note that the population mean B(E,.A) ) is exactly [19(x)) call3. since
2n
E(E,,)) E
f(x e.) cki
Σ
f(x f(x+ Cb =10)()) cx112
(12)
since f(x + Ex) and f(r Eÿ) independent random variables for * j. Finally, note that the confidence interval (ln,k, Uz for the quantity [lg(z) cs 1l implies confidence interval

---

Centhred sccurnyy
Certified
2
Attckk roduus
Attack roclis
Ribck rolus
(a) Cub-200-2011
(b) CIFAR-FS
mindmageNeet
Figure 3: Dependency of certified accuracy on attack radius & for different o, 1-shot case, n = 1000.
Certffed sccumnyy
Certifed sccumee
Contiifee
Attack rooMs
Attack roctus
Kibck roous
(a) Cub-200-2011
(b) CIFAR-FS
mindmageNeet
Figure 4: Dependency of certified accuracy on attack radius for different a, 5-shot case, = 1000.
(V v Ug,kk
(13)
for the quantity [[g(z) - cx Thus, the procedures TwoSidedConf Int and LowerConfBound from algorithms return interval from (13) and its left bound for the random variable representing corresponding distance, respectively.
Experiments
5.1 Datasets
For the experimental evaluation of our approach we use several well-known datasets for few-shot learning classification. Cub-200-201/ [45] is dataset with 11, 788 images of 200 bird species, where 5864 images of 100 species are in the train subset and 5924 images of other 100 species are in the test subset. It is notable that lot species presented dataset have degree of visual similarity, making classification of ones a challenging task even for humans. månilmageNee 44] is substet of images from ILSVRC 2015 (37] dataset with images categories train subset, categories validation subset and 20 categories in test subset with 600 images of size 84 x 84 in each category. CIFAR FS same way as minilmageNet and contains 37800 images of 64 categories in the train set and 11400 images of 20 categories in the test set. Experimental setup all the datasets is presented in the next section.
M is subset of CIFAR 100 [99] dataset which was generated
5.2 Experimental settings and computation cost
we compute approximate certified test set accuracy to estimate the performance of the and embedding risk computation with the Algorithm The baseline model we used for experiments is a prototypical network introduced in [39 with original architecture, an additional fully-connected layer was added in the tail of the network to map embeddings to 51 512-dimensional vector space. The model was trained solve --shot and 5-shot classification tasks on each dataset, with 5-way classification on each iteration.
Following
+
smoothed model prediction with the Algorithm |
2.
ConvNet-4 backbone. Compared

---

Parameters of expeiments. For data augmentation, we applied Gaussian noise with zero mean, unit variance and probability 0.3 of augmentation. Each dataset was certified on subsample of 500 images with default parameters for the Algorithm D number of samples
1000, confidence level = 0.001 and variance = 1.0, unless stated otherwise. For our settings, may be shown from simple geometry that values (a,, b,) from (9) are such that by a4 I 4 so we use b, a, = 4. The maximum number of samples in the Algorithm | is set to be T x 10
Computation cost. In the table below, we report the computation time of the certification procedure per image on Tesla V100 GPU for Cub-200-2011 dataset. Standard deviation in seconds appears to be significant because the number of main loop iterations required to separate the two leftmost confidence intervals varies from image image in the test set.
Table I: Computation time per image of implementation of the Algorithm
Cub-200-2011.
10a
10
10s
I, sec
0.044 + 0.030
0.509 0.403
4.744 + 2.730
5.3 Results of experiments
In this section, we report the results of our experiments. In our evaluation protocol, we compute
approximate certified test accuracy, C.A. Given sample H, a smoothed classifier g() from the
Algorithm with an assigned classification rule h(x) = arg minke(L.....K) (l9(2) c2 threshold value e for 12 norm of additive perturbation and the robustness guarantee r = r(x) from the Algorithm compute CAA test set S as follows:
CA(S,e) (c.,)) v) E S: (::((z) e h(x) vl
(14)
S
In other words, we treat the model g(-) as certified at point x under perturbation of norm e if x is correctly classified by s(-) (what means that the procedure of classification described in the Algorithm D does not abstain from classification of x) and g(-) has the value of certified radius r(x) > 6.
Visualization of results. The figures represent dependencies of certified accuracy the value of norm of additive perturbation for different learning settings (1-shot and 5-shot learning). The value of the attack radius corresponds to the threshold from (1... For Cub-200-201 dataset we provide dependency of certified accuracy for different sample size n for the Algorithm | (in the Figure 5
Limitations
In this section, we provide failure probability of Algorithms 2 discuss abstains from classification in the Algorithm and speculate on the application of our method other few-shot scenarios.
6.1 Estimation of errors of algorithms
Note that the value of a from is the probability of the value of Pa. (19(x) cx|12 not to belong to the corresponding interval the form from (3). Given a sample x, the procedure the Algorithm returns two closest prototypes to the g(x). To determine two leftmost confidence intervals, all the distances Pz.k have to located within corresponding intervals, thus, according to the independence of computing these two intervals, the error probability for the Algorithm iis 91 Ka, where K the number of classes. Similarly, the procedure in the Algorithm 2 outputs the lower bound for the adversarial risk with coverage least 1 and depend
the output of the Algorithm I inside, and, thus, has error probability 42 = 1 (1 - a) - Ka) = a + Ka Ko² that corresponds to returning overestinated lower bound for the adversarial risk from the Theorem
6.2 Abstains from classification and extension to other few-shot approaches
crucial to note that the procedure in the Algorithm D may require lot of samples to distin- guish two lefumost confidence intervals and sometimes does not finish before reaching threshold

---

value T for sample size. As result, there may be input objects at which the smoothed classi- fier can be neither evaluated nor certified. In this subsection, we report the fraction of objects in which the Algorithm D abstains from determining the closest class prototype (see Tables 23
0.6
... Row
Table 2: Percentage of non-certified objects in test subset, 1-shot case.
11
Cartffed accurccy
#1
a = 10
a a= 10
a = 10
0.4
Cub-200-2011
1.6%
1.6%
1.6%
CIFAR-FS
2.2%
2.2%
2.4%
0.2
minilmageNet
1.9%
2.2%
2.4%
0.0
0.00
0,25
0.50
0.25
1.00
1.25
1,50
1.25
2.00
Attack
Table 3: Percentage of non-certified objects in
Figure 5: Dependency of certified accuracy on attack radius ε for different number of samples of the Algorithm D CIFAR-FS dataset, 5- shot case. notable that relatively small number of samples may be used to achieve satisfactory level of certified accuracy.
test subset, 5-shot case.
a 10-2
10-3
10-4
Cub-200-2011
1.2%
1.2%
1.4%
CIFAR-FS
3.0%
3.4%
3.8%
minilmageNet
2.9%
2.9%
3,0%
Since our method is based on randomized smoothing, among the approaches presented in 43 is applicable for matching networks and some extent MAML networks. In the case of matching networks, the new sample is labeled as weighted cosine distance to support samples, so it is easy to transfer guarantees for l2 distance to the ones for cosine distance in case of normalized embeddings. For MAML, smoothing may be applied to the embedding function as well, but theoretical derivations of certificates are required.
7 Related work
Breaking neural networks with adversarial attacks and empirical defending from them have a long history of cat-and-mouse game. Namely, for particular proposed defense against existing adversarial perturbations, new more aggressive attack found. This motivated researchers to find defenses that mathematically provable and certifiably robust to different kinds of input manipulations. Several works proposed exactly verified neural networks based on Satisfiability Modulo Theories solvers These methods are found to be computationally inefficient, although they guarantee to find adversarial examples, in the case they exist. Another line of works use more relaxed certification 47
[6 6 or mixed-integer linear programming 30 B
Although these methods aim to guarantee that an adversary does not exist a certain region around a given input, they suffer from scalability to big networks and large datasets. The only scalable to large datasets provable defense against adversarial perturbations is randomized smoothing. Initially, was found as an empirical defense to mitigate Later several works showed its mathematical proof of certified robustness 21 5) Lecuyer et al (2 first provided proof of certificates against adversarial examples using differential privacy. Later, Cohen al [3] provided the tightest bound using Neyman-Pearee lemma. Interestingly, alternative proof using Lipschitz continuity was found
36
adversarial effects in neural networks 29
40
The scalability and simplicity of randomized smoothing attracted significant attention, and
was extended beyond 12 perteuururati
22
32
Conclusion and future work
In this work, we extended randomized smoothing as defense against additive norm-bount bounddddded adversarial attacks the case of classification in the embedding space that is used in few-shot learning scenarios. We performed an analysis of Lipschitz continuity of smoothed normalized embeddings and derived robustness certificate against /a-attacks. Our theoretical findings are supported experimentally on several datasets. There are several directions for future work: our approach can possibly be extended to other types of attacks, such as semantic transformations; also, it is important to reduce the computational complexity of the certification procedure.

---

9 Acknowledgements
The work was supported by Ministry of Science and Higher Education grant No. 075- 175-10-2021-068.
References
[1] Luca Bertinetto, Joao Henriques, Philip HS Torr, and Andrea Vedaldi. Meta-learning with differentiable closed-form solvers. arXiv preprint /805.0816, 2018.
[2] Nicholas Carlini and David Wagner. Towards evaluating the robustness of neural networks. In 2017 ieee symposium on security and privacy (sp). pages 39-57. IEEE, 2017.
[3] Jeremy Cohen, Elan Rosenfeld, and Zico Kolter. Certified adversarial robustness via randomized smoothing, In International Conference Machine Learning, pages 13 1310-1320. PMLR, 2019.
[4] Guneet S. Dhillon, Kamyar Azizzadenesheli, Zachary C. Lipton, Jeremy Bernstein, Jean Kossaifi, Aran Khanna, and Anima Anandkumar. Stochastic activation pruning for robust adversarial defense, 2018.
[5] Yinpeng Dong, Hang Su, Baoyuan Wu, Zhifeng Li, Wei Liu, Tong Zhang, and Jun Zhu. Efficient decision-based black-box adversarial attacks on face recognition. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 7714-7722, 2019.
[6] Ruediger Ehlers. Formal verification of piece-wise linear feed-forward neural networks. In International Symposium on Automated Technology for Verification and Analysis, pages 269- 286. Springer, 2017.
[7] Volker Fischer, Mummadi Chaithanya Kumar, Jan Hendrik Metzen, and Thomas Brox. Adver- sarial examples for semantic image segmentation. arXiv preprint arXiv:1703.00 2017.
[8] Matteo Fischetti and Jason Deep neural networks as 0-1 mixed integer linear programs: feasibility study. arXiv preprint /7/.. 2017.
[9] Micah Goldblum, Liam Fowl, and Tom Goldstein. Adversarially robust few-shot learning: A
meta-learning approach. Advances Neural Information Processing Systems, 33, 2020.
[10] Ian Goodfellow, Jonathon Shlens, and Christian Szegedy. Explaining and harnessing adversar- ial examples. arXiv preprint arXiv:1412.6553 2014.
[11] Sven Gowal, Krishnamurthy Dvijotham, Robert Stanforth, Rudy Bunel, Chongli Qin, Jonathan Uesato, Relja Arandjelovic, Timothy Mann, and Pushmeet Kohli. On the effectiveness of interval bound propagation for training verifiably robust models. arXiv preprint 11xiv:1810012711:: 2018.
[12] Jan Hendrik Metzen, Mummadi Chaithanya Kumar, Thomas Brox, and Volker Fischer. Universal adversarial perturbations against semantic image segmentation. In Proceedings of the IEEE international conference on computer vision, pages 2755-2764, 2017.
[13] Wassily Hoeffding. Probability inequalities for sums of bounded random variables. In The collected works of Wassily Hoeffding, pages 409-426. Springer, 1994.
[14] Yunseok Jang, Tianchen Zhao, Seunghoon Hong, and Honglak Lee. Adversarial defense via learning to generate diverse attacks. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 2740-2749, 2019.
[15] Jinyuan Jia, Xiaoyu Cao, Binghui Wang, and Neil Zhenqiang Gong, Certified robustness for top-k predictions against adversarial perturbations via randomized smoothing. arXiv preprint arXiv: 029999 2019.
[16] Guy Katz, Clark Barrett, David Dill, Kyle Julian, and Mykel J Kochenderfer. Reluplex: An efficient smt solver for verifying deep neural networks. In International Conference on Computer Aided Verification, pages 97-117. Springer, 2017.
[17] Edgar Kaziakhmedov, Klim Kireev, Grigorii Melnikov, Mikhail Pautov, and Aleksandr Petiushko. Real-world attack on mtenn face detection system. In 2019 International Multi- Conference on Engineering, Computer and Information Sciences (SIBIRCON), pages 04222 0427. IEEE, 2019.
10

---

[18] Stepan Komkov and Aleksandr Petiushko. Advhat: Real-world adversarial attack on areface face id system. In 2020 25th International Conference on Pattern Recognition (ICPR), pages 819-826. IEFE, 2021.
[19] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[20] Aounon Kumar and Tom Goldstein. Center smoothing: Certified robustness for networks with structured outputs. Advances in Neural Information Processing Systems, 34, 2021.
[21] Mathias Lecuyer, Vaggelis Atlidakis, Roxana Geamhasu, Daniel Hsu, and Suman Jana. Certified robustness adversarial examples with differential privacy. In 2019 IEEE Symposium on Security and Privacy (SP), pages 656-672. IEEE, 2019.
[22] Guang-He Lee, Yang Yuan, Shiyu Chang, and Tommi S Jaakkola. Tight certificates of ad- versarial robustness for randomly smoothed classifiers. arXiv preprint arXiv: (ete::996609990 2019.
[23] Alexander Levine and Soheil Feizi. Robustness certificates for sparse adversarial attacks by randomized ablation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 4585-4593, 2020.
[24] Alexander Levine and Soheil Feizi, Wasserstein smoothing: Certified robustness against wasserstein adversarial attacks. In International Conference Artificial Intelligence and Statistics, pages 9938-9977. PMLR, 2020.
[25] Bai Li, Changyou Chen, Wenlin Wang, and Lawrence Carin. Certified adversarial robustness with additive noise. arXiv preprint 1009:008800033111 2018.
[26] Debang Li, Junge Zhang, and Kaiqi Huang. Universal adversarial perturbations against object detection. Pattern Recognition, 110: 110: 107584, 2021.
[27] Linyi Li, Maurice Weber, Xiaojun Xu, Luka Rimanic, Bhavya Kailkhura, Tao Xie, Ce Zhang, and Bo Li. Tss: Transformation-speccff smoothing for robustness certification, 2021.
[28] Fan Liu, Shuyu Zhao, Xuelong Dai, and Bin Xiao, Long-term cross adversarial training: A robust meta-learning method for few-shot classification tasks. arXiv preprint arXiv:2106. 129000. 2021.
[29] Xuanqing Liu, Minhao Cheng, Huan Zhang, and Cho-Jui Hsich. Towards robust neural networks via random self-ensemble. In Proceedings of the European Conference on Computer Vision (ECCV), pages 369-385, 2018.
[30] Alessio Lomuscio and Lalit Maganti. An approach to reachability analysis for feed-forward relu neural networks. arXiv preprint arXiv:1706.073:: 073511 2017.
[31] Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. arXiv preprint arXiv:1706.00833
2017.
[32] Jeet Mohapatra, Ching-Yun Yun Ko, Tsui-Wei Weng. Pin- Yu Chen, Sijia Liu, and Luca Daniel. Higher-order certification for randomized smoothing. arXiv preprint (xXi:2001000665) 2020.
[33] Seyed- Seyed-Mohsen Moosavi-Dezfoolli, Alhussein Fawzi, Omar Fawzi, and Pascal Frossard. Univer- sal adversarial perturbations. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1765-1773, 2017.
[34] Seyed-Mohsed Moosavi- -Deaooll,,,, Alhussein Fawzi, and Pascal Frossard. Deepfool: a simple and accurate method to fool deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 2574-2582, 2582, 2016.
[35] Mikhail Pautov, Nurislam Tursynbek, Marina Munkhoeva, Nikita Muravev, Aleksandr Petiushko, and Ivan Oseledets. CC-Cert: A probabilistic approach to certify general robustness of neural networks. arXiv preprint 109.v92009.00666 2021.
[36] Aditi Raghunathan, Jacob Steinhardt, and Percy Liang. Certified defenses against adversarial examples. arXiv preprint 1rXiv:1801.09: 093444, 2018
[37] Olga Russakovsky, Jia Deng. Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journal of computer vision, 1 11-22) 2015.
11

---

[38]
Hadi Salman, Greg Yang, Jerry Li, Pengchuan Zhang, Huan Zhang, Ilya Razenshteyn, and Sebastien Bubeck. Provably robust deep learning via adversarially trained smoothed classifiers. arXiv preprini arXiv: 196.0444000444444 2019.
[39]
Jake Snell, Kevin Swersky, and Richard S Zemel. Prototypical networks for few-shot learning.
arXiv preprint arXiv: 10X3,057703 2017.
[40] Jiawei Su, Danilo Vasconcellos Vargas, and Kouichi Sakurai. One pixel attack for fooling deep neural networks. IEEE Transuctions on Evolutionary Computation, 23(5):828- 141888888111188 2019.
[41] Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, Ian Goodfel- low, and Rob Fergus. Intriguing properties of neural networks. arXiv preprini 1rXiv:1312.61999 2013.
[42] Jiaye Teng, Guang-He Lee, and Yang Yuan. f_ adversarial robustness certificates: a randomized smoothing approach. 2019.
[43] Eleni Triantafillou, Tyler Zhu, Vincent Dumoulin, Pascal Lamblin, Utku Evci, Kelvin Xu, Ross Goroshin, Carles Gelada, Kevin Swersky, Pierre-Antoine Manzagol, et al. Meta-dataset: A dataset of datasets for learning to learn from few examples. arXiv preprint arXiv: 1rXiv:1903.03000 2019.
[44] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29:3630-3638. 2016.
[45] Catherine Wah, Steve Branson, Peter Welinder, Pietro Perona, and Serge Belongie. The caltech-uesd birds-200-2011 dataset. 2011.
[46] Lily Weng, Pin-Yu Yu Chen, Lam Nguyen, Mark Squillante, Akhilan Boopathy, Ivan Oseledets, and Luea Daniel. Proven: Verifying robustness of neural networks with a probabilistic approach. In International Conference on Machine Learning, pages 6727-6736. PMLR, 2019.
[47] Eric Wong and Zico Kolter. Provable defenses against adversarial examples via the convex outer adversarial polytope. In International Conference on Machine Learning, pages 5286-5295. PMLR, 2018.
[48] Zuxuan Wu, Ser-Nam Lim, Larry S Davis, and Tom Goldstein. Making an invisibility cloak: Real world adversarial attacks object detectors. In European Conference Computer Vision, pages 1-17. Springer, 2020.
[49] Cihang Xie, Jianyu Wang. Zhishuai Zhang, Zhou Ren, and Alan Yuille. Mitigating adversarial effects through randomization. arXiv preprint arXiv: 171.1119911111 2017.
[50] Cihang Xie, Jianyu Wang, Zhishuai Zhang, Yuyin Zhou, Lingxi Xie, and Alan Yuille. Adver- sarial examples for semantic segmentation and object detection. In Proceedings of the IEEE International Conference on Computer Vision, pages 1369-1378, 2017.
[51] Greg Yang, Tony Duan, J Edward Hu, Hadi Salman, Ilya Razenshteyn, and Jerry Li. Randomized smoothing of all shapes and sizes. In International Conference on Machine Learning, pages 10693-10705. PMLR, 2020.
[52] Dinghuai Zhang, Mao Ye, Chengyue Gong, Zhanxing Zhu, and Qiang Liu. Black-box certifica- tion with randomized smoothing: A functional optimization based framework. arXiv preprint arXiv:2002.09166 2020.
[53] Hongyang Zhang, Yaodong Yu, Jiantao Jiao, Eric Xing, Laurent El Ghaoui, and Michael Jordan. Theoretically principled trade-off between robustness and accuracy. International Conference on Machine Learning, pages 7472-7482. PMLR, 2019.
[54] Yaoyao Zhong and Weihong Deng. Towards transferable adversarial attack against deep face recognition. IEEE Transactions on Information Forensics and Security, 14:1446-1466, 2020.
[55] Jianli Zhou, Chao Liang, and Jun Chen. Manifold projection for adversarial defense on face recognition. In European Conference on Computer Vision, pages 288-305. Springer, 2020.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
12

---

(b) Did you describe the limitations of your work? [Yes] See Section 6
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full of assumptions all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] The proofs are included in the supplementary material.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or URL)? [Yes] The code with instructions is included the supplementary material.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] Applicable training details are described Section 5.2.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5.2.
4. If you are using existing assets (e.g., code, data, models) or curating/reelasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] See Sections and
5.2
(b) Did you mention the license of the assets? [No]
(c) Did you include any new assets either in the supplemental material or as URL? [No]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] The datasets and models publicly available.
(e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "mfiWo3ppK5", "reviewer": "Reviewer_1EMm", "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.\n", "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", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Theoretical results and empirical evaluations successfully demonstrate the robustness of the method and provide a practical algorithm for robust few-shot learning.\n- The paper is easy to read.\n- To the extent that I know, the idea is novel for certified robustness in few-shot learning.\n- To the extent that I checked, the theoretical results are correct and the algorithm follows the theory.\n\nWeaknesses:\n- 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.\n- 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].\n\n[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.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "hOkVT2Vtdin", "reviewer": "Reviewer_JtzZ", "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. ", "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? \n* 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. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n------------\n* 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.\n* The proposed algorithm is clearly explained, intuitively makes sense and also computationally cheap - thereby having a higher potential of being adopted in the community.\n*  Experiments have been performed on multiple datasets from different domains and the method works consistently across these tasks.\n\nWeaknesses\n---------------\n* 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.\n* 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "AKEKssFPk7", "reviewer": "Reviewer_EGnM", "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. \n\nTo 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. ", "questions": "- How can the approach be generalized for other few-shot learning schemes? \n- 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. \n- The results should be fleshed out to compare against baseline natural model (no certified radius) and the certified model without data augmentation. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n-  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. \n- 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. \n- 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. \n\n\nWeaknesses:\n- 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). \n- 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.  \n- 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. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "6sxtJQrsK4n", "reviewer": "Reviewer_d5wK", "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. ", "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\n\nIt 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.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Main strengths:\n- The paper tackles the significant problem of robust learning in the few-shot case. \n- 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.\n- Quality of writing is mostly good\n\nMain weaknesses:\n- 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. \n- 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. \n- 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.\n\nOther remarks:\n- 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.\n- The algorithms written aren't accurate. You use set notation but it isn't correct the way you write it down.\n- First paragraph isn't well-written and I would recommend editing it.\n- Line 19 \"This shows how easy...\" needs rewriting\n- Line 166 use $g_1,g_2$ without defining them.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept