Distributionally Robust Weighted \(k\)-nearest Neighbors

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, \texttt\{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

Stats

• citations0
• S2 citations—
• github stars0
• HF likes0
• heat score0.00
• arxiv keyzhu2020distributionally

Related papers

• Minimax Optimal Algorithms With Fixed-\(k\)-nearest Neighbors (2022)0.00
• Certifiable Robustness For Nearest Neighbor Classifiers (2022)0.00
• Minimax Rate Optimal Adaptive Nearest Neighbor Classification And Regression (2019)8.35
• A Two-stage Active Learning Algorithm For \(k\)-nearest Neighbors (2022)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• Adaptive Nearest Neighbor: A General Framework For Distance Metric Learning (2019)0.00
• On The Resistance Of Nearest Neighbor To Random Noisy Labels (2016)0.00
• Leveraging Reinforcement Learning For Evaluating Robustness Of KNN Search Algorithms (2021)0.00