Certifiable Robustness For Nearest Neighbor Classifiers

Abstract

ML models are typically trained using large datasets of high quality. However, training datasets often contain inconsistent or incomplete data. To tackle this issue, one solution is to develop algorithms that can check whether a prediction of a model is certifiably robust. Given a learning algorithm that produces a classifier and given an example at test time, a classification outcome is certifiably robust if it is predicted by every model trained across all possible worlds (repairs) of the uncertain (inconsistent) dataset. This notion of robustness falls naturally under the framework of certain answers. In this paper, we study the complexity of certifying robustness for a simple but widely deployed classification algorithm, \(k\)-Nearest Neighbors (\(k\)-NN). Our main focus is on inconsistent datasets when the integrity constraints are functional dependencies (FDs). For this setting, we establish a dichotomy in the complexity of certifying robustness w.r.t. the set of FDs: the problem

Stats

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

Related papers

• Distributionally Robust Weighted \(k\)-nearest Neighbors (2020)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
• On High-dimensional Modifications Of The Nearest Neighbor Classifier (2024)0.00
• Consistency Of The \(k\)-nearest Neighbor Regressor Under Complex Survey Designs (2026)0.00
• An Adaptive Nearest Neighbor Rule For Classification (2019)0.00
• Online Nearest Neighbor Classification (2023)0.00
• A Theory-based Evaluation Of Nearest Neighbor Models Put Into Practice (2018)0.00