Distributionally robust weighted k-nearest neighbors
Authors: Shixiang Zhu
Liyan Xie
Minghe Zhang
Rui Gao
Yao Xie
Venue: NeurIPS 2022 Accept (2022)

Abstract: Learning a robust classifier from a few samples remains a key challenge in machine learning. A major thrust of research has been focused on developing k-nearest neighbor (k-NN) based algorithms combined with metric learning that captures similarities between samples. When the samples are limited, robustness is especially crucial to ensure the generalization capability of the classifier. In this paper, we study a minimax distributionally robust formulation of weighted k-nearest neighbors, which aims to find the optimal weighted k-NN classifiers that hedge against feature uncertainties. We develop an algorithm, Dr.k-NN, that efficiently solves this functional optimization problem and features in assigning minimax optimal weights to training samples when performing classification. These weights are class-dependent, and are determined by the similarities of sample features under the least favorable scenarios. When the size of the uncertainty set is properly tuned, the robust classifier has a smaller Lipschitz norm than the vanilla k-NN, and thus improves the generalization capability. We also couple our framework with neural-network-based feature embedding. We demonstrate the competitive performance of our algorithm compared to the state-of-the-art in the few-training-sample setting with various real-data experiments.

Distributionally Robust Weighted k-Nearest Neighbors
Shixiang Zhu Carnegie Mellon University shi shixinnzaaddrev. cmu edu
Liyan Xie
The Chinese University of Hong Kong, Shenzhen xieliyan@cuhk.c edu.c..... cn
Minghe Zhang
Rui Gao
Georgia Institute of Technology minghe_ zhang@gatech. edu
University of Texas at Austin
rui mai.ggo@@ccooms.oom utexas. edu
Yao Xie
Georgia Institute of Technology yao. xie@isye
gatech. xieeiisy..gatech.... edu
Abstract
Learning a robust classifier from a few samples remains key challenge in machine learning. A major thrust of research has been focused developing k-nearest neighbor (k-NN) based algorithms combined with metric learning that captures similarities between samples. When the samples are limited, robustness espe- cially crucial to ensure the generalization capability of the classifier, In this paper, we study a minimax distributionally robust formulation of weighted k-nearest neighbors, which aims to find the optimal weighted k-NN classifiers that hedge against feature uncertainties. We develop an algorithm, Dr k-N,, that efficiently solves this functional optimization problem and features in assigning minimax optimal weights training samples when performing classification. These weights are class-dependent, and are determined by the similarities of sample features under the least favorable scenarios. The proposed framework can be shown be equivalent to a Lipschitz norm regularization problem. We also couple our framework with neural-network-basse competitive performance of our algorithm compared the state-of-the-arr in the New-training-sane sample setting with various real-data experiments.
feature embedding. We demonstrate the
Introduction
Machine learning has been proven successful in data-intensive applications but is often hampered when the data set is small. For example, in breast mammography diagnosis for breast cancer screening [5). the diagnosis the type of breast cancer requires specialized analysis by pathologists in a highly time- and cost-consuming task and often leads to non-consensual results. As result, labeled data in digital pathology are generally very scarce; so do many other applications.
In this paper, we aim to tackle the general multi-class classification problem when only very few training samples available for each class 4 Evidently, k-Nearest Neighbor (k-NN) algorithm 3 is a natural idea to tackle this problem and shows promising empirical performances. Notable contributions, including seminal work (19) and the follow-up non-linear version 6B] go beyond the
vanilla k-NN and propose neighborhood component analysis (NCA), NCA learns a distance metric that minimizes the expected leave-one-out classification error the training data using stochastic neighbor selection rule. Some recent studies in few-shot learning utilize the limited training data using similar idea, such as matching network and prototypical network [39]. They are primarily based on distance- -eianhee k-NN, which classifies an unseen sample (aka. query) by weighted
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Label: Mop
Label Kemondor
Label Komondor
Training set
A Komondor dressing up mop
Query
Motivating example: a small training set of three image-label pairs: the first image is a mop; the second image a dog: the third image looks like mop but is, in fact, dog (dressing up as a mop). The query (the last image) is "closer" to the third one and more likely to be misclassified as a dog if we use tistance-weightee k-NN.
Figure I:
vote of its neighbors and uses the distance between two data points in the embedding space as their weights.
The classification performance of weighted k-NN critically depends on the choice of weighting scheme. The distance measuring the similarity between samples is typically chosen by metric learning, where a task-specific distance metric is automatically constructed from supervised data However, it has been recognized that they may be not robust to the few-training samples scenario, where an "outlier" may greatly deteriorate the performance. An example illustrate this issue is shown in Figure 0 The training set with only three labeled samples includes two categories we want classify: mop and Komondor. As we can see, the query image is visually closer to the third sample and thus more likely to be misclassified as Komondor. Here the third sample in the training set is an "outlier", since it is Komondor dressing up as a mop, and misleads the metric learning model to capture irrelevant details (e.g.. the bucket and the mop handle) for the Komondor category. Such a problem can become even severe when the sample size is small.
22 4T.
The discussion above highlights the importance of choosing a good weighting scheme in weighted k-NN. To develop algorithms that are more robust in the www-trainnn-saaplll settings, we propose a new formulation of distributionally robust weighted k-nearest neighbors. More specifically, for given set of features of training samples, we solve a Wasserstein distributionally robust optimization problem that finds the minimax optimal weight functions for the k-nearest neighbors. This infinite- dimensional functional optimization over weight functions presents a unique challenge for which existing literature on distributionally robust optimization do not consider. To tackle this challenge, we first consider a relaxed problem that optimizes over all randomized classifiers, which turns out to admit finite-dimensional convex programming reformulation in spite of being infinite-dimenss (Theorem D. Next, we show that there weighted K-NN classifier achieving the same risk and shares the same least favorable distributions (LFDs) the robust classifier (Theorem 2 Thereby prove the optimality of such weighted k-NN classifier for the original distributionally robust weighted prove the equivalence between the proposed robust k-nearest neighbors problem. Furthermore, regularization problem (Theorem 3 which provides weighted k-NN classifier with a Lipschitz norm promising insights on the generalization property of the robust classifier.
Based on these theoretical results, we proposed a novel algorithm called Dr. KNN.. Unlike the traditional distance-weighted k-NN that uses the same weight for all label classes, our algorithm introduces a vector of weights, one for each class, for each sample in k-NN and performs a weighted majority vote. These weights are determined from the LFDs and reveal the significance of each sample in the worst case, thereby contributing effectively to final decision making. An example is illustrated in Figure 2 Further, using differentiable optimization 4 21, we incorporate neural network into the minimax classifier that jointly learns the feature embedding and the minimax optimal classifier. Numerical experiments show that our algorithm can effecttvvly improve the multi-class classification performance with few training samples on various data sets.
Related work Recently, there has been much interest in multi-class classification with few training samples, see BI [ for a survey. The main idea of our work is related to metric learning [19 22
R4 R2,,
which essentially translates the hidden information carried by the limited data into distance metric, and has been widely adopted few-shot learning and meta learning 155
300
However, unlike few-shot and meta learning, where the goal is to acquire meta knowledge from
2

---

Decision Boundary
Timorraaa Distribttions Komondor
Mop
Komondor
Mop
Dit K-NN
P
Pi
Decidon Belimdary
Samples
Sumples
Wesglt
Weight per sample
per
3
(a) Vanilla K-NN
(b) Dr k-NN
Figure 2: An illustrative comparison Dr N-NN and vanilla k-NN. Each colored dot is training sample, where the color indicates its glass-membership The horizontal/verrtial bar represents the probability mass of one training sample under the distribution Pl. P2, respectively.
large number of observed classes and then predict examples from unobserved classes, focus attacking specific general classification problem where the number of categories fixed but labeled data scarce. In this paper, take different probabilistic approach to exploit information from the data: we construct an uncertainty set for distributions of each class based on the Wasserstein distance.
Wasserstein distributionally robust optimization 10
is an emerging paradigm for statistical learning; see [26] for recent survey. Our work is mostly related to [18], framework for Wasserstein robust hypothesis testing, but is different in three important ways. First, we focus multi-class classification, while [18] only studied two hypotheses. Second, we focus on directly minimizing the mis-classification error while [8] used a convex relaxation for 0-1 loss. Third, analyze the generalization bound while |8 does not. Fourth, while [[S] requires sample features as an input, we develop a scalable algorithmic framework simultancously learn the optimal feature extractor parameterized by neural networks and robust classifier to achieve the best performance. A recent work g studies distributionally robust k-NN regression. Note that regression and classification objective is to minimize the mean square error, whereas in our work we minimize classification errors. Last but least, our minimax formulation is similar [. which introduces a generalization of the maximum entropy principle and aims to address different supervised learning problem. worth noting that the paper considers another type of ambiguity defined via cross-moment constraints. In contrast, we adopt Wasserstein sets our formulation, leading to different tractable optimization reformulations and regularization terms.
fundamentally different different performance metrics used. In Y the
assigns one weight to each sample; the optimal weights minimize asymptotic expansion for the excess risk (regret). In contrast, we consider minimax robust multi-class classification, each training sample associated with different weights for different classes, and we consider the few sample regime instead of the asymptotic regime in 355
Another well-known work on optimal weighted nearest neighbor binary classifier 35
Distributionally Robust k-NN
In this section, we present our model. We first define weighted k-NN classifier in Section 2.1 then present the proposed framework of distributionally robust k-NN problem Section 2.2
2.1 Weighted i-NN classifier
Let ((x), y²),, ..., ... (x" } be a set of training samples, where & denotes the i-th data sample in the observation space X' and y¹ E Y Let E feature extractor that embeds samples to the feature space 3 (in Section we will train neural network to learn Φ). Denote the sample feature vectors and the empirical support
(1...,, denotes the class (label) of the i-th data sample.

---

as:
:= )(x), ,,,.,,n. = {st .s".....
Let
= ((5) ,y²), "y",,..... ,,",,,55 y"))
Define empirical distributions:
Pm:
Se = m). m = 1...., ......... M,
Hi: y² m
where 8 denotes the Dirac point mass, function.
denotes the cardinality of a set, and Il denotes the indicator
Let πT E + Ass be a randomized classifier that assigns class m E (1.....,M M) with probability Tm (E) to query feature vector E, where AM the probabilistic simplex Am - {- R2 Em sm=i Tm -.. It is worth mentioning that the randomized test is more general than the commonly seen deterministic test. In particular, the random classifier æ reduces to the deterministic test if for any e, there exists m such that nm (E) 1. Suppose the features in each class m follows a distribution Pm. We define the risk of a classifier ı as the total error probabilitie<]
(T; P1 PM))
Σ Ee Tm (m)))..
Recall that the vanilla h-NN is performed as follows. Let x - R. be metric on E that measures distance between features. For any given query point ç. let TC) T (c) be
reordering of {1,.... n according to their distance to i.e., e(g, (T))) < c(E, ((.n for all i < n, where the tie is broken arbitrarily. Here the superscript indicates the dependence on the sample S. In vanilla K-NN, we compute the votes
Pro (E)
Σ
M m). m 1,..,,
M.
The vanilla k-NN decides the class for by the majority vote, i.e., accept the class arg max (E).
To define a weighted k-NN, let us replace the equal weights in by an arbitrary weight function Wm E x = + R2 for each class m 1, ,.....Me. M:
Pm (E)
Σ wm Wm (E, (E))
and use a shorthand notation == (w) [w]...., war). In the sequel, we define general tie-breaking rule as follows. For any ç, denote Mo(E)= == arg max Pm(E). When [Mo(E)) > 1, there is
a tie at E. We denote (E) as the probability of accepting class m for m E <Mo(E) and we have EmeMote) (m)()=
We define a weighted k-NN classifier π knn (E: kt w): EE AM as:
Tm (E), vn E Mo(E), otherwise.
knn (E: k, w)
(4)
0,
weighted k--N classifier involves two parameters: number of nearest neighbors and weighting scheme u. Particularly, (E, = 1(y" = m recovers the vanilla k-NN, and (m.(E = H2y
m)/c(E, ( recovers the distance-based weighted k-NN. Note that our definition ( allows different weighting schemes for different classes, which is more general than the standard weighted k--N
The goal is find the optimal weighted k-NN classifier k (:: k, w) such that the risk V as defined in is minimized. Since the underlying true distributions are unknown, the commonly used loss
"To ease the exposition we consider only equal weights over the error probabilities, but our results can be easily generalized to any weighted average of emor probabilities.

---

function is the empirical loss, i.e., substitute the empirical distributions Pm,. into the risk function ① This leads the following optimization problem:
min SS
Le ( knn (;kk Pı. Paa).
(5)
1m RR_., ISMEM
It is worth mentioning that this minimization problem is an infmiiteddimensioonal functional optimiza- tion, since the weighting schemes w is function on x E.
2.2 Distributionally robust k-NN
For few-training trraiinn-ssappe setting, the empirical distributions might not be good estimates for the true distribution since the sample size is small. To hedge against distributional uncertainty, propose distributionally robust counterpart of the weighted k-NN problem defined in the previous subsection. Specifically, suppose each class m associated with distributional uncertainty set P which will be specified shortly. Given , PM, define the worst-case risk of a classifier и as the worst-case total error probabilities
max P. EP Pm..
(T; PI PMs),
where is defined in
We consider the following distributionally robust k-NN problem that finds the optimal weighted k-NN classifier minimizing the worst-case risk:
min ICAEn EX5-RR 15m5M
max P.EPP ISMSM
(T P1. PM).
(6)
m
Here the optimal solution . PM to the inner maximization problem is also called favorable distributions (LFD) in statistics literature 21 We summarize the architecture of the proposed distributionally robust k-NN framework in Figure more details are provided in Section
Now we describe the uncertainty set Pm. First, since we are going re-weight the training samples to build the classifier, we restrict the support of every distribution in Pm to E, the set of empirical points. Second, the uncertainty set data-driven, containing the empirical distribution Pn, and distributions surrounding its neighborhood. Third, to measure the eloseness between distributions, we choose the Wasserstein metric of order 40) defined as
W(P, = min ((E,e)))
for any two distributions P and P on E, where the minimization of is taken over the set of all probability distributions on E x E with marginals P and P'. The main advantage of using Wasserstein metric that it takes account of the geometry of the feature space by incorporating the metric c(..) in its definition. Given the empirical distribution Pm, for m = = we define
Pm PP E ( W(P P.)) $ smm}
where (P) denotes the set of all probability distributions on E; 9m 2 0 specifies the size of the uncertainty set for the m-th class that specifies the amount of deviation we would like to control.
3 Theoretical Properties
In this section, we analyze the computational tractability and statistical properties of the proposed distributionally robust weighted k--N classifier found in 6 proofs are delegated to Appendix B
3.1 Robust Classification
Observe that similar to ( the formulation is also an anfinite-dimessionne functional optimization. Let us first relate it to relaxed robust classification problem, which turns out to be more tractable.
Consider the following minimax robust classification problem over all randomized classifiers ı (recalling AM is the probability simplex in R4
min AA
max P.,, EP P.. MM
(TT; Pl....,, PM).
(8)
5

---

Testing
sumples
Netwooka CNN)
Framework)
project to
Slamese cat
DR I-NN
Triining samplees
yield (P,(o)) P((o))
X
Convex
Solver
yield (P) (O), (()))
(w))
Figure An overview of the end-to-end learning framework, which consists of two cohesive components: (1) an architecture that is able to produce feature embedding and least favorable distributions p. for training set; (2) an Dr K-NN makes decisions for any unseen sample based on the estimated weight vector Pm (E) (probability mass least favorable distributions).
Yet still, an
functional optimization, since we are optimizing over the set of all randomized classifiers. We establish the following theorem stating a finite-dimensional convex programming reformulation for the problem
Theorem 1. For the uncertainty sets defined in can be obtained by solving the following problem:
77. the least favorable distribution of problem
min PlomPar ER.
Σ
ISMSM Pm
TM ER
subject to
Σ
I' o(5 (2) S Om.
1=1 j=1
Σ fo = Pm)(())
Σ
Tm
Pm
1=1
1=1
V1 < j,j < N, 1 m M.
The decision variable Yim RT can be viewed as joint distribution on empirical points with marginal distributions P.,. and Pm. represented by a vector Pm. E R.. The inequality constraint controls the Wasserstein distance between Pm. and P...
Below we give an intuitive explanation for the objective function in Note that max S'n M Pmn p'm measures the margin between the maximum likelihood of & among all classes and the likelihood of the m-th class. Thus, the objective 2 can be equivalently rewritten as minimization total margin:
max ISm''SM
P'm P'm
m=1
When M = 2, the total margin reduces to the total variation distance. Also, let vin. E {0, 1 be the class indicator variable of sample ç², observe that
m
M
yin log exp(Ip'm)
Σ max P'm lim 15mS M t-
Σ
Σm=1 exp(lpin)
1=1
where the second term the right side represents the cross-entropy (or negative log-likelihood).
Therefore, problem perturbs (P), PM)) to LFDs (Pi, PM)) so to minimize the total margin as well as an upper bound on cross-yntropy of LFDs; the smaller the margin (or cross-entropy) is, the more similar between classes and thus the harder to distinguish among them.
3.2 Expressiveness of Weighted k-NN
In this subsection study the expressive power of the class of weighted k-NN classifiers
{n knn (; w): 1 < k < nm
E x x R 1 < < M}

---

defined in Section 2.
The following theorem establishes the equivalence between the original problem (6 and the relaxed robust classification problem S
studied in Section 3.1
Theorem 2. For the uncertainty set defined in 7. formulations 6 and @ have identical optimal
values. In addition, there exists optimal solutions of (6 and that share common LFDs that are optimal to y
Theorem implies that the set of weighted k-NN classifiers is exhaustive, in the that it achieves the same optimal robust risk as optimizing over the set of all randomized classifiers. In our proof, we show that the weighted I-NN classifier, with weights equal the LFDs (). is an optimal solution to Therefore, instead of solving O directly, by Theorem I we can solve the convex program
for the LFDs, based on which we construct robust k-NN classifier. This justifies the Dr k-NN algorithm to be described in Section 4
3.3 Lipschitz Regularization
Next, we discuss the connection between the proposed distributional robust k--N framework in and an equivalent Lipschitz regularization problem.
Using duality for Wasserstein DRO problem
is equivalent to
min B-A
Am Dm
max {1 [E
--mmmm (5) An Amo((s
(10)
20.m
m==1
Then by [16,, this problem upper bounded by the following Lipschitz regularized classification problem
M B Be- [1 1- (m) + 0m
min
m [mmppppppppp
(11)
m=1
where
Jm (5) num (E)
Jm 1t
max S
C)
is the Lipschitz norm of the function Tm for each I,..., M. Perhaps surprisingly, the next
result shows that (1O) and [1] are actually equivalent (thus by Theorem 2 are both equivalent to 6
despite that the loss function does not satisfy existing criteria ensuring the equivalence
[13 36 [6]
Theorem 3. Formulations 10 and are equivalent, and there exists optimizer " of
satisfying lt X; m I,..., M, where (Nm)) is the optimizer of (10) when π
The theorem is proved by using c-transform 40 to show that any optimizer nh be modified into a X,, -Lipschitz classifier while maintaining the optimality. Note that Lipschitz classifiers are known to enjoy good generalization property [4 20), thus the equivalence provides promising insights for the generalization property of the robust classifier.
4 Proposed Algorithm Dr kNNNN
In this section, present the Distributional robust k-Nearest Neighbor (KNN) algorithm, which a direct consequence of the theoretical justifications in Section
4.1 K-NN algorithm
Based on Theorem
g our algorithm contains two steps.
Step 1. [Sample re-weighting] For each class m, re-weight samples using distribution P where
(Pr (P.....,PM)) Pr)) is the p-component of the minimizer
Step 2. [K-NN] Given a query point &, ordering the training samples according to their distance to
c(E, 5 (() (9) c(E))r < ...S.. (T())) Compute the weighted A-NN votes, define
Pm (E)
p (E m 1, I,...,M.
(12)
7

---

(a) PT
(6) PI
(c) PS
(d) x
Figure 4: An example of the weights Pf. P2. P3 yielding from 9 and the corresponding results of
Dr k-NN using small subset of MNIST (digit 4 (red), (blue), 9 (green) and & = 5). Raw samples are projected on 2D feature space (d 2), with the color indicating their true class-membership. In (c), shaded areas indicate the kernel smoothing of PT P2 P3 defined in
(3). In (d), big dots represent the training points and small dots represent the query points, and their color depth suggests how likely the sample is being classified into the true category.
Table 1: Comparison of classification accuracy in the few- New-training-sample setting
NISST
Chadge:
Lany
COMENIICT
Mestads
3F-22
1376
0.755
0.83
0.28
0381
0385
0534
Macking Net
6132
08855
8335
0073
3.47
8
0.88
0363
E881
038
8.3
0775
1.46
0833
8853
0531
11210
07.0
6.235
8156
0.99
335
0.61
0.35
0333
0.0
6315
0351
8.36
070
0.63
053
0662
020)
0356
Sand Sewwkiig
0377
01313
1391
0UT1
339
0A68
0.72
0336
0343
1861
0.71
8350
1300
(34)
1.20
0357
0330
0.00
196
1.94
1.166
1031
1342
0.554
630
1358
6.111
0461
6447
0131
Decide the class for a query feature point & as arg max g Pm (E), where the tie is broken according the rule
Figure f gives an illustration showing the probabilistic weights P2,,P, P3) for three classes and its corresponding decision boundary yielding from the weighted k-NN.
For the sake of completeness, which is referred to as truncated Dr k-NN. The key idea is to keep the training samples that are important in deciding the decision boundary based on the maximum entropy principle [[]] This can be particularly useful for the general classification problem with an arbitrary size of training set. An illustration (Figure and more details can be found in Appendix
also extend our algorithm non-few-trainieee training-sample setting,
4.2 Joint learning framework
In this section, we propose a framework that jointly learns the feature mapping and the robust classifier. the feature mapping db( 0) be neural network parameterized by whose input is batch of training samples (Figure 3). and then compose it with an optimization layer that packs the convex problem g as an output layer that outputs the LFDs of ( The optimization layer is adopted from differentiable optimization [!] 2), in which the optimization problem is integrated as an individual layer an end-to-end trainable deep networks and the solution of the problem can be backpropagated through neural networks.
To apply the mini-batch stochastic gradient descent, we need ensure that each batch comprises of multiple "mini-sets", one for each class, containing at least one training sample from each class fed into the convex optimization layer. In light of Pb. the objective of our joint learning framework is ming [0; Pt ....... P where
n
[0; Pr Pr.... PT)
Σ
max Px (o(x';
ISmSAr
and (Pt: (o(::)))) are the LFDs generated by the convex solver defined in 9 given input variables {g' (e)ssss)s The algorithm is summarized in Algorithm I
(Appendix A

---

Accunscy
Ansiray-
Accuscy
Aceuary 0.507
(a) Dr K-NN
(b) PCA + A-NN
(c) SVD A-NN
(d) NCA.
Figure 5: A comparison of the learned feature spaces and the corresponding decision boundaries. There are 10 training samples from two categories of MNIST identified as large dots and 1,000 query samples identified as small dots. The color of dots shows their true categories. The color of the region shows the decisions made by corresponding methods.
Experiments
In this section, we evaluate our method and eight alternative approaches on four commonly-used image data sets: MNIST 28 CIFAR-10 25 Omniglot [27]. and present of comprehensive numerical examples.
We also test our method two medical diagnosis data sets: Lung Cancer
12 and COVID-19
CT [4), where very few data samples are available for study, due to privacy concerns and high costs associated with harvesting data. Specifically, Lung Cancer data record 56 attributes for only 32 patients who have been diagnosed with three types of pathological lung cancers; COVID-19 Computed Tomography (CT) data contain 349 COVID-19 CT images from 216 patients and 463 non-COVID-19 CTs. Here, we present a few examples of COVID-19 CT images and non-COVID-19 CT images in Appendix
Experiment set-up. We compare our method including Dr k-NN and its truncated version with the following baselines: (1) k-NN based methods with different dimension reduction techniques, including Principal Component Analysis (PCA+k-NO) NN), Singular Value Decomposition (SVD+k-NM) Neighbourhood Components Analysis (NCA+K-NN) [9]. and feature embeddings generated by Dr.k- NN (Feature embedding k--NN) as sanity check; (2) matching networks [11; (3) prototypical networks 69); ; (4) MetaOptNet [2)]. To make these methods comparable, we adopt the same naive neural network with single CNN layer on matching network, prototypical network, and our model, respectively, where the kernel size is 3, the stride is and the width of the output layer is d = 400.
In our experiments, we focus on an M-class K-s K-sample (K training samples for each class) learning task. To generate the training data set, we randomly select M classes and for each class we take K random samples. So our training data set contains M K samples overall. We then aim to classify disjoint batch of unseen samples into one of these M classes. Thus random performance on this task stands at I/M. We test the average performance of different methods using 1, 000 unseen samples from the same M classes. To obtain reliable results, we repeat each test 10 times and calculate the average accuracy.
Other experimental configurations are described as follows: The Adam optimizer 2 is adopted for all experiments conducted in this paper, where learning rate is 10-2 The mini-batch size is 32. The hyper-parameter 9m chosen by cross-validation, which varies from application to application. The differentiable convex optimization layer we adopt is from 2 To make all approaches comparable, we use the same network structure in matching network, prototypical network, and MetaOptNet as we described above. We use the Euclidean distance c(E, E') | E'll2 throughout our experiment. All experiments are performed on Google Colaboratory (Pro version) with 12GB RAM and dual-core Intel processors, which speed up to 2.3 GHz (without GPU).
Results. We present the average test accuracy in Table | for the unseen samples with different
M 2, and K = 5, 10 on small subsets of MNIST, mini ImageNet, CIFAR-10. 10, Omniglot, and
with . = 3 and K 5, 8 on lung cancer data. Note that random performance for two-class and five-class classifications are 0.5 and 0.2, respectively. The figures in Table T show that Dr NN
(It 5) outperforms other baselines in terms of the average test accuracy on all data sets. We note

---

that 95% confidence interval of our method's performance on all the data sets is smaller than 0.08. The truncated Dr -NNNN also yields competitive results using only 20% training samples (T 0.9). compared to standard Dr ...NN.
To confirm that the proposed learning framework will affect the distribution of hidden representation of data points, we show the training and query samples in a 2D feature space and the corresponding decision boundary in Figure 5 turns out our framework finds a better feature representation in the 2D space with a smooth decision boundary and a reasonable decision confidence map (indicated by the color depth in Figure (a)).
Comparison to kernel smoothing. We also compare with approach using kernel-smoothing of the LFDs (in contrast to using k--NN for performing classification. Consider a Gaussian kernel k(x)= = | 1//l k( H -/2//x). Ir), where H₁ = hTp is the isotropical kernel with bandwidth h. Then we replace Pm (5) in Step 2 of Dr K-NN with the following
Pm (m)
Σ PM(EE)N(E-
- E"), VE, m I...., M.
(13)
We evaluate both methods subset of MNIST, which contains 1,000 testing samples (small dots) and 20 training samples (large dots) from two categories (indexed by blue and red, respectively).
As shown in Figure 7 and Figure (Appendix D) experimental results have shown the importance of using k-NN in our proposed algorithm, where the Dr kNN significantly outperforms the parallel version using kernel smoothing (even after the kernel bandwidth being optimized), We find that the performance when using kernel smoothing bandwidth h as illustrated by Figure g
13 heavily depends on selecting an appropriate kernel
Moreover, the best kernel bandwidth may vary from one dataset another. Therefore, the cross- validation is required to be carried out to find the best kernel bandwidth in practice, which is quite time-consuming. In contrast, choosing the hyper-paranee arper-parameter limited choices of & in www-traiiig-ssmpp scenario and the performance of Dr. k-NN is insensitive to the choices of (see Figure
an easy task, since we only have
6 Conclusion
We propose distributionally robust k-NN classifier (Dr k-NN) for tackling the multi-class classifica- tion problem with few training samples. To make a decision, each neighboring sample weighted according to least favorable distributions resulting from a distributionally robust problem. As shown in the thcoretical results and demonstrated by experiments, our methods achieve outstanding per- formance in classification accuracy compared with other baselines using minimal resources. The robust classifier layer serves an alternative to the usual softmax layer in a neural network for classification, and we believe it is promising for other machine learning tasks.
References
[1] Soroosh Shafieezadeh Abadeh, Peyman Mohajerin Mohajerin Esfahani, and Daniel Kuhn. Distributionally robust logistic regression. In Advances Neural Information Processing Systems, pages 1576 1576-1584, 2015.
[2] Akshay Agrawal, Brandon Amos, Shane Barratt, Stephen Boyd, Steven Diamond, and J Zico Kolter. Differentiable convex optimization layers. In Advances in Neural Information Processing Systems, pages 9558 00789997,2001 2019.
[3] Naomi Altman. An introduction kernel and nearest-neighhor nonparametric regression. The American Statistician, 46(3):175-185, 1992.
[4] Brandon Amos and J Zico Kolter. Optnet: Differentiable optimization layer in neural networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 136-145. JMLR. org, 2017.
[5] Guilherme Aresta, Teresa Araújo, Scotty Kwok, Sai Saketh Chennamsetty, Mohammed Safwan, Varghese Alex, Bahram Marami, Marcel Prastawa, Monica Chan, Michael Donovan, Gerardo
10

---

Fernandez, Jack Zeineh, Matthias Kohl, Christoph Walz, Florian Ludwig, Stefan Braunewell, Maximilian Baust, Quoc Dang Vu, Minh Nguyen Nhat To, Eal Kim, Jin Tae Kwak, Sameh Galal, Veronica Sanchez-Freire, Nadia Brancati, Maria Frucci, Daniel Riccio, Yagi Wang. Lingling Sun, Kaiqiang Ma, Jiannan Fang, Ismael Kone, Lahsen Boulmane, Aurélio Campilho, Catarina Eloy, António Polónia, and Paulo Aguiar. Bach: Grand challenge on breast cancer histology images. Medical Image Analysis, 56:122 139, 2019.
[6] Jose Blanchet, Yang Kang, and Karthyek Murthy. Robust Wasserstein profiee inference and applications to machine learning. Journal of Applied Probability, 56(3):830-857, 2019.
[7] Jose Blanchet, Yang Kang, Fan Zhang, Fei Hc, and Zhangyi Hu. Doubly robust data-driven distributionally robust optimization. arXiv preprint arXiv: 1Xtv:1705.07168. 2017.
[8] Jose Blanchet and Karthyek Murthy. Quantifying distributional model risk via optimal transport. Mathematics of Operations Research, 44(2):565 600, 2019.
[9] Ruidi Chen and Ioannis Paschalidis. Selecting optimal decisions via distributionally robust nearest-neighhor regression. In H. Wallach, H. Larochelle, A. Beygelzimer, F. dAlché Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 749-759. Curran Associates, Inc., 2019.
[10] Ruidi Chen, Joannis Ch Paschalidis, et al. Distributionally robust learning. Foundations and Trends(R) in Optimization, 4(1-2))1-243, 2020.
[11] Thomas M. Cover and Joy A. Thomas. Elements of Information Theory (Wiley Series in Telecommunications and Signal Processing). Wiley-Interscience, USA, 2006.
[12] Dheeru Dua and Casey Graff. UCI machine learning repository: Lung cancer data set, 2017.
[13] Peyman Mohajerin Esfahani and Daniel Kuhn. Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations. Mathemati- cal Programming. 171 15--16666,, 2018.
[14] Farzan Farnia and David Tse. A minimax approach to supervised learning. In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29, Curran Associates, Inc., 2016
[15] Chelsea Finn, Picter Abbecl, and Sergey Levine. Model-agnostic meta-learning for fast adapta- tion of deep networks. In Doina Precup and Yee Whye Tch, editors, Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Research, pages 1 126 1135, International Convention Centre, Sydney, Australia, 06-11 Aug 2017. PMLR.
[16] Rui Gao, Xi Chen, and Anton J Kleywegt. Wasserstein distributional robustness and regulariza- tion in statistical learning. arXiv preprint arXiv:1712.000550 2017.
[17] Rui Gao and Anton J Kleywegt. Distributionally robust stochastic optimization with Wasserstein distance. arXiv preprint arXiv:1604.0 021.9.21999 199, 2016.
[18] Rui Gao, Liyan Xie, Yao Xie, and Huan Xu. Robust hypothesis testing using Wasserstein uncertainty sets. In Proceedings the 32nd International Conference on Neural Information Processsig Systems, NIPS' 18, page 7913-7923, Red Hook, NY, USA, 2018. Curran Associates Inc.
[19] Jacob Goldberger, Geoffrey E Hinton, Sam T. Roweis, and Russ R Salakhutdinov, Neighbour- hood components analysis. In L. K. Saul, Y. Weiss, and L. Bottou, editors, Advances in Neural Information Processing Systems 17, pages 513-520. MIT Press, 2005.
[20] Lee-Ad Gottlieb, Aryeh Kontorovich, and Robert Krauthgamer. Efficient classification for metric data. IEEE Transactions Information Theory, 600))5575-55 2014.
[21] Peter Huber. A robust version of the probability ratio test. Annals of Mathematical Statistics, 1656)_175311758, 1965.

---

[22] Wen Jiang, Kai Huang, Jie Geng, and Xinyang Deng. Multi-scale metric learning for feotshot learning. IEEE Transactions on Circuits and Systems for Video Technology, 311)):091-1112. 2021.
[23] Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 2014.
[24] Gregory Koch, Richard Zemel, and Ruslan Salakhutdinov. Siamese neural networks for one-shot image recognition. In ICML deep learning workshop, volume 2. Lille, 2015.
[25] Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar- 10 (canadian institute for advanced research). 2020.
[26] Daniel Kuhn, Peyman Mohajerin Esfahani, Viet Anh Nguyen, and Soroosh Shafieezadeh- Abadeh. Wasserstein distributionally robust optimization: Theory and applications in machine learning. In Operations Research & Management Science in the Age of Analytics, pages 130-166. INFORMS, 2019.
[27] Brenden M Lake, Ruslan Salakhutdinov, and Joshua B Tenenbaum. Human-level concept learning through probabilistic program induction. Science, 350062666:1332-1333 2015.
[28] Yann LeCun and Corinna Cortes. MNIST handwritten digit database. 2010.
[29] Kwonjoon Lee. Subhransu Maji, Avinash Ravichandran, and Stefano Soatto. Meta-learning with differentiable convex optimization. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 10657-10665, 2019.
[30] Fei-Fei Li, R. Fergus, and P. Perona. One-shot learning of object categories. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2844):594-611, 2006.
[31] Xiaoxu Li, Xiaochen Yang, Zhanyu Ma, and Hin Xue. Deep metric learning for few-shot image classification: A selective review. arXiv preprint arXiv:2105.08144 2021.
[32] Tingting Liao, Zhen Lei, Tianqing Zhu, Shan Zeng, Yaqin Li, and Cao Yuan. Deep metric learning for k nearest neighbor classication. IEEE Transactions on Knowledge and Data Engineering, 2021.
[33] Tobias Plötz and Stefan Roth. Neural nearest neighbors networks. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, page 1095-1106, Red Hook, NY, USA, 2018. Curran Associates Inc.
[34] Ruslan Salakhutdinov and Geoff Hinton. Learning a nonlinear embedding by preserving class neighbourhood structure. In Marina Meila and Xiaotong Shen, editors, Proceedings of the Eleventh International Conference on Artificial Intelligence and Statistics, volume 2 of Proceedings of Machine Learning Research, pages 412-419, San Juan, Puerto Rico, 21-24 Mar 2007. PMLR.
[35] Richard J Samworth. Optimal weighted nearest neighbour classifiers. The Annals of Statistics, 40(5):2733-2763. 2012.
[36] Soroosh Shafeeraadeh-Abadeh, Daniel Kuhn, and Peyman Mohajerin Esfahani. Regularization via mass transportation. Journal of Machine Learning Research, 20(103):1-68 2019.
[37] Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczyáski. Lectures on stochastic programming: modeling and theory. SIAM, 2014.
[38] Aman Sinha, Hongseok Namkoong, and John Duchi. Certifying some distributional robustness with principled adversarial training. arXiv preprint arXiv:1710.10577 2017.
[39] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. In
I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems 30, pages 4077-4087. Curran Associates, Inc., 2017.
12

---

[40] Cédric Villani. Optimal transport: old and new, volume 338. Springer Science & Business Media, 2008.
[41] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Matching networks for one shot learning. In Proceedings of the 30th International Conference Red Hook. NY, USA,
on Neural Information Processing Systems, NIPS' 16. page
2016. Curran Associates Inc.
[42] Ulrike Luxburg and Olivier Bousquet. Distance- based classification with lipschitz functions.
J. Mach. Learn. Res., 5(Jun)6669665, 2004.
[43] Yaqing Wang, Quanming Yao, James Kwok, and Lionel M. Ni. Generalizing from a few examples: survey on few-shot learning, 2019.
[44] Xingyi Yang, Xuehai He, Jinyu Zhao, Yichen Zhang, Shanghang Zhang, and Pengtao Xie. COViD-CT--Datase:: A CT scan dataset about COVID-19, 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]
(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 to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect 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]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [Yes]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [Yes]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "ja_j8YtT0d", "reviewer": "Reviewer_67DR", "summary": "This paper studies the k-NN algorithm when applied to multiclass classification with a few samples. The authors develop algorithms by formulating a  distributionally robust variant of k-NN where each nearest neighbor is weighted based on least favorable distribution. \n \t\t\t\t\t\t\t\n", "questions": "NA", "limitations": "The paper lacks novelty and empirical evaluation does not strongly support the superior performance of the proposed method.\n", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is well-written, and the proposed algorithm is supported by theoretical results and empirical evaluation. However, it lacks novelty and empirical evaluation does not convey the superior performance of the proposed method. For example, the authors discuss the success of metric learning in kNN but exclude it in the experiments. I understand that in small per-class setting, the similar and dissimilar sets for learning the distance metric would be very imbalance, but it would interesting to see to what extent the proposed algorithm improves upon it (by making tweaks to metric learning such as hard negative sampling etc to overcome the imbalance ness issue). Overall, while the paper is very well-written and enjoyable to read, the lack of novelty and aforementioned issue on empirical evaluations prevents me from giving it a high score.\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": ["I don’t know"]}, "extra_text": {}}, {"review_id": "_JkIv_KW62a", "reviewer": "Reviewer_PP67", "summary": "The authors take the generalization of the K-NN method for the multi-label classification problem, which lifts the samples to feature spaces and replaces the distance weights with more general weight functions. The distributionally robust formulation of this well-known generalization is defined and shown to be equivalent to a much simpler problem when the ambiguity sets comprise Wasserstein balls. Thanks to this equivalence, the authors show that the worst-case distributions are characterized by the solution of a convex optimization problem. There is further a solution algorithm proposed, and thanks to this, the authors compare the performance of Wasserstein DRO weighted K-NN with benchmark algorithms on well-known classification datasets.", "questions": "I would like to ask the following questions:\n\n- The authors find that their approach is identical to Lipschitz regularization. To what extent is this finding in line with your citation [30]? It is already known that Wasserstein DRO is identical to regularization in general classification settings. Specifically: (i) if the authors believe this finding is novel and not directly applicable from [30] (e.g., because here we optimize a probability vector) could they please discuss this (ii) if it indeed follows from [30], it is still interesting, because [30] shows equivalence with *a* regularizer, but here the authors show a specific one.\n\n- Page 3: randomized \"test\" -> what does 'test' mean?\n\n- Page 3, line 128: Suppose the features in each class $m$ follows a distribution $P_m$ -> could the authors please state this more formally?\n\n- Page 4, lines 160-161, the optimization problem is written in a way that it looks like $m$ is also an optimization variable.\n\n- Could the authors please explain the derivation of (8) intuitively -> i.e., by restricting problem (6) via extra constraints (which is then shown to be redundant in terms of the optimal solution)\n\n- Page 6, line 212 states usage of \"duality for Wasserstein DRO\" -> this does not always hold and there needs to be some structure for duality. Could the authors please mention them?", "limitations": "Overall, I am positive about the paper. I would like to clarify the questions I asked above, as well as the weaknesses mentioned.\n\nMy biggest concern (or question that I would like to clarify) is that the authors constrain the ambiguity sets to include distributions that are supported only on the training instances. In general, in most Wasserstein classification settings, the most useful results are thanks to the fact that we do *not* have such constraints. It can be seen from the literature that the worst-case distributions are (typically supported on at most $n+1$ atoms -- please also check if this holds here) characterized by a weighted mixture of training points, as well as a point that is extremely far away from the training points, though with a negligibly small weight. This is how the Wasserstein methods coincide with regularization techniques. Would it be possible for the authors to compare their method with a brute-force method that solves the Wasserstein DRO problem where the ball's support points are unconstrained?\n\nI am also wondering whether the equivalence between (6) and (8) works because of such an assumption. If my concern is not valid, I would appreciate an explanation from the authors. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThe paper is written extremely well. It is very easy (and fun) to follow. The motivation is clear. The proofs are correct and they follow a modern set of techniques. The numerical experiments are very thorough and interesting. \n\nWeaknesses:\n- There are some missing discussions about the Wasserstein DRO side of the paper. Especially, recently, there is a strong focus on the structure of the worst-case distributions, finite sample guarantees, and asymptotic consistencies. These are not mentioned in this paper, and except for defining and solving the problem, there is not much focus on the properties that come thanks to the Wasserstein formulation. \n- The ambiguity sets (that said, the authors call those uncertainty sets, which I believe should be named ambiguity sets) are restricted to distributions supported on training points. I have never seen this, and this may be a dangerous approach. I would like to see more discussions on this. If I am wrong, then seeing further references would be great.\n\nFurther details are in the \"Limitations\" section.", "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": "2PKxr5PP0HU", "reviewer": "Reviewer_Spo7", "summary": "This paper aims to developing a distributionally robust KNN classifier for multiclass few shot scenario to mitigate those weaknesses of existing similar methods, it essentially learns the class-dependent metrics to build corresponding optimal weighted k-NN classifiers, , so-designed algorithm Dr. KNN is able to hedge against feature uncertainties.so-reported comparison results show relatively favorable performance to SOTAs..", "questions": "1.Existing works should NOT be omitted in the following aspects\nIn few-shot metric learning:\n[m1]Wen Jiang, et al, Multi-Scale Metric Learning for Few-Shot Learning, IEEE Transactions on Circuits and Systems for Video Technology, 2021,Page(s):1091 - 1102.\n[m2] Zheren Fu, etal, \"Self-Supervised Synthesis Ranking for Deep Metric Learning\", IEEE Transactions on Circuits and Systems for Video Technology, vol.32, no.7, pp.4736-4750, 2022.\n[m3]X Li, etal, Deep metric learning for few-shot image classification: A selective review,  arXiv preprint arXiv:2105.08149, 2021.\nIn robust metric learning:\n[m4]K Huang, et al, Robust metric learning by smooth optimization, arXiv preprint arXiv:1203.3461, 2012.\n[m5] L Wang, et al, Provably robust metric learning, NerISP2020.\n[m6]Blanchet, et al, Doubly robust data-driven distributionally robust optimization,J  arXiv preprint arXiv:1705.07168, 2017.\n\n2' \"the importance of choosing a good weighting scheme in weighted k-NN\" is natural, however, In an example in Figure 1, whether do the colors and shapes of samples also play some crucial roles in classifying them?\nEspecially for a few shot scenario, if we do NOT take these, including disentanglement for the building blocks of samples, into account but just learning some metric, how far can we go? implying just doing these seems NOT far enough, for example, one can simply change the color of test samples with the same training class to outside those of theirs, is it still robust?\nthus the distributions you assume will significantly introduce bias to learning, which, undoubtedly, also brings robustness in other sense!\n\n3. Can the method or designed algorithm handle imbalanced or/and large classes? In your experiments, you just adopt the maximal class number M=5, suggesting to increase it for more comparison!\n\n", "limitations": "Though the formulation or definition in this manu. is somewhat trivial, but its highlight lies in optimization and theoretical property analysis from which some conclusions or insights can be gained.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1.For multi-class few shot metric learning, the authors develop the optimal weighted k-NN classifiers by using the proposed Dr. KNN algorithm to optimize a defined distributionally robust formulation, including the class-dependent weights in classification.\n2.Theoretically proving the formulation equivalent to a Lipschitz norm regularization problem and analyzing a few properties to justify their algorithm;\n3.Empirically, confirming the proposed algorithm to have competitive performance compared to the SOTAs in the same setting with various real-data sets.\n\nWeaknesses\n1.The proposed formulation lacks a sufficient clarification about the uniqueness, including, essential difference in principle from existing DRO formulation.\n2.the problem under study involves distributional robustness and metric learning, thus the authors should NOT overlook some existing works in the two aspects, at least being mentioned to make differences, especially those appeared in 2021 and 2022.\n3.The assumption among classes is NOT practice.\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": "-GAb_eiAMVD", "reviewer": "Reviewer_PjNq", "summary": "This paper proposes a distributionally robust version of k-nearest neighbors (k-NN) classifier that can perform well in a small-sample regime, especially for a multiclass setting.\nThe authors propose to consider a minimax optimization problem for a distributionally robust classification, and show that this infinite-dimensional problem can be indeed solved by a finite-dimensional convex problem.\nIts connection to the Lipschitz regularization framework is also established.\nThey then propose the Dr. k-NN algorithm and show that it can be seamlessly used with learning neural features jointly.\nThe experiments show that the proposed algorithm can beat the existing baselines as well as other neural network based approaches.", "questions": "- In line 139, after \"In the sequel, we deﬁne a general tie-breaking rule as follows.\" I do not find a tie-breaking rule. \n- In Table 1, in the column for Omniglot, $M=2$, $K=5$, Prototypical Net achieves 0.769, which is the highest, but it's not highlighted.\n- In line 101, it is claimed that \"we analyze the generalization bound.\" Is the connection to the Lipschitz regularization problem the referred \"analysis\" of the generalization bound? If that is the case, I would suggest to clarify the sentence to avoid any misunderstanding.\n- A closely related work of a similar flavor missed in the current paper is:\n    - Farzan Farnia and David Tse, \"A Minimax Approach to Supervised Learning,\" NeurIPS 2016.\n\n   This paper also studied the same minimax optimization framework with a similar motivation, but under a different form of the candidate set of distributions. It would be helpful to discuss the similarities and differences.", "limitations": "It is indicated in Checklist that limitations are mentioned in Section 6, but I cannot find any. \nIs there any limitation of this framework?", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This is a solid and well-written paper. \nThe mathematical formulation and the technical results are well motivated and very elegant based on the convex optimization theory. \nThe presentation is also very clear except that the notation is a bit heavy.\nThe experiments are well designed and executed to corroborate the power of the theoretical framework.\n\nWeaknesses are hard to find.", "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