Geometric Algorithms for $k$-NN Poisoning
This work addresses security vulnerabilities in k-NN classification for geometric data, presenting a novel attack method with theoretical guarantees.
The authors tackled the problem of label poisoning attacks on geometric datasets for k-nearest neighbor classification by developing an algorithm that computes an εn-additive approximation of the optimal poisoning in n·2^{2^{O(d+k/ε)}} time, using multi-scale random partitions.
We propose a label poisoning attack on geometric data sets against $k$-nearest neighbor classification. We provide an algorithm that can compute an $\varepsilon n$-additive approximation of the optimal poisoning in $n\cdot 2^{2^{O(d+k/\varepsilon)}}$ time for a given data set $X \in \mathbb{R}^d$, where $|X| = n$. Our algorithm achieves its objectives through the application of multi-scale random partitions.