# Certifiable Robustness for Nearest Neighbor Classifiers

arXiv: https://arxiv.org/abs/2201.04770 · HTML: https://mlsanity.com/paper/2201.04770/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 29 references that are in the map.
- First posted on arXiv 13 Jan 2022.

## Builds on (most cited first, 9 of 9)

- [Certified Adversarial Robustness via Randomized Smoothing](https://mlsanity.com/paper/1902.02918/) (2019)
- [Certified Defenses for Data Poisoning Attacks](https://mlsanity.com/paper/1706.03691/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Certified Robustness to Label-Flipping Attacks via Randomized Smoothing](https://mlsanity.com/paper/2002.03018/) (2020)
- [HoloClean: Holistic Data Repairs with Probabilistic Inference](https://mlsanity.com/paper/1702.00820/) (2017)
- [Curse of Dimensionality on Randomized Smoothing for Certifiable Robustness](https://mlsanity.com/paper/2002.03239/) (2020)
- [Certified Robustness for Top-k Predictions against Adversarial Perturbations via Randomized Smoothing](https://mlsanity.com/paper/1912.09899/) (2019)
- [Nearest Neighbor Classifiers over Incomplete Information: From Certain Answers to Certain Predictions](https://mlsanity.com/paper/2005.05117/) (2020)
- [Computing Optimal Repairs for Functional Dependencies](https://mlsanity.com/paper/1712.07705/) (2017)

## Built on by (most cited first, 3 of 3)

- [Explaining k-Nearest Neighbors: Abductive and Counterfactual Explanations](https://mlsanity.com/paper/2501.06078/) (2025)
- [Naive Bayes Classifiers over Missing Data: Decision and Poisoning](https://mlsanity.com/paper/2303.04811/) (2023)
- [Certain and Approximately Certain Models for Statistical Learning](https://mlsanity.com/paper/2402.17926/) (2024)

## Abstract (arXiv)

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 either admits a polynomial time algorithm, or it is coNP-hard. Additionally, we exhibit a similar dichotomy for the counting version of the problem, where the goal is to count the number of possible worlds that predict a certain label. As a byproduct of our study, we also establish the complexity of a problem related to finding an optimal subset repair that may be of independent interest.