Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: 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. 
 							

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.

questions: NA
limitations: The paper lacks novelty and empirical evaluation does not strongly support the superior performance of the proposed method.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: 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.
The 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.
Its connection to the Lipschitz regularization framework is also established.
They then propose the Dr. k-NN algorithm and show that it can be seamlessly used with learning neural features jointly.
The experiments show that the proposed algorithm can beat the existing baselines as well as other neural network based approaches.
strengths_and_weaknesses: This is a solid and well-written paper. 
The mathematical formulation and the technical results are well motivated and very elegant based on the convex optimization theory. 
The presentation is also very clear except that the notation is a bit heavy.
The experiments are well designed and executed to corroborate the power of the theoretical framework.

Weaknesses are hard to find.
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. 
- 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.
- 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.
- A closely related work of a similar flavor missed in the current paper is:
    - Farzan Farnia and David Tse, "A Minimax Approach to Supervised Learning," NeurIPS 2016.

   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. 
Is there any limitation of this framework?
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The 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.
strengths_and_weaknesses: Strengths:
The 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. 

Weaknesses:
- 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. 
- 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.

Further details are in the "Limitations" section.
questions: I would like to ask the following questions:

- 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.

- Page 3: randomized "test" -> what does 'test' mean?

- Page 3, line 128: Suppose the features in each class $m$ follows a distribution $P_m$ -> could the authors please state this more formally?

- Page 4, lines 160-161, the optimization problem is written in a way that it looks like $m$ is also an optimization variable.

- 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)

- 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.

My 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?

I 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.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: 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..
strengths_and_weaknesses: Strengths:
1.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.
2.Theoretically proving the formulation equivalent to a Lipschitz norm regularization problem and analyzing a few properties to justify their algorithm;
3.Empirically, confirming the proposed algorithm to have competitive performance compared to the SOTAs in the same setting with various real-data sets.

Weaknesses
1.The proposed formulation lacks a sufficient clarification about the uniqueness, including, essential difference in principle from existing DRO formulation.
2.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.
3.The assumption among classes is NOT practice.

questions: 1.Existing works should NOT be omitted in the following aspects
In few-shot metric learning:
[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.
[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.
[m3]X Li, etal, Deep metric learning for few-shot image classification: A selective review,  arXiv preprint arXiv:2105.08149, 2021.
In robust metric learning:
[m4]K Huang, et al, Robust metric learning by smooth optimization, arXiv preprint arXiv:1203.3461, 2012.
[m5] L Wang, et al, Provably robust metric learning, NerISP2020.
[m6]Blanchet, et al, Doubly robust data-driven distributionally robust optimization,J  arXiv preprint arXiv:1705.07168, 2017.

2' "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?
Especially 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?
thus the distributions you assume will significantly introduce bias to learning, which, undoubtedly, also brings robustness in other sense!

3. 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!


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.
review_title: null

Meta-review: metareview: The reviewers conclude on an interesting paper (especially PjNq) with substantial results that justify its acceptance. I can only recommend to include all of the discussion parts in the camera ready version.
confidence: Less certain
Decision: Accept