Geometric Algorithms For \(k\)-nn Poisoning
Diego Ihara Centurion, Karine Chubarian, Bohan Fan, Francesco Sgherzi, Thiruvenkadam S Radhakrishnan, Anastasios Sidiropoulos, Angelo Straight . Arxiv 2023 – 0 citations
We propose a label poisoning attack on geometric data sets against (k)-nearest neighbor classification. We provide an algorithm that can compute an (\epsilon n)-additive approximation of the optimal poisoning in (n\cdot 2^{2^{O(d+k/\epsilon)}}) 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.